Linear Inequalities and Linear Programming
Objectives
By the end of this article, you should be able to:
- Solve a system of linear inequalities
- Construct a linear programming model from a linear programming problem
- Solve linear programming model
- Identify special cases in linear programming model
Often, in real life situations, it is not possible to match the resources that we have (available resources) with the planned uses of the resources. For example, even though a commercial poultry farmer might have $5000.00 to buy two types of feed mixes, the total cost of the two feed mixes might not be exactly equal to the available resources (i.e $ 5000.00). This situation can be described in terms of “there is a maximum of $5000.00 available” or “the minimum quantities of each feed mix that can be bought”. This is an example of an area where inequalities rather than equations are used. Where as equations are two expressions joined by an “=” sign, inequalities are two expressions joined by one of the inequality signs. The inequality signs are: < (less than), > (greater than), ≤ (less than or equal to) and ≥ (greater than or equal to). An example of a system of inequalities in two variables is given as follows: 2x + 3y ≤ 18; 5x + 6y≥30; x<10; y>8.
The system of linear inequalities in two variables can be plotted on the x-y plane (a piece of graph paper on which an x-axis and y-axis are drawn). Linear inequalities define regions of the x-y plane. The procedure for graphing Linear Inequalities is as follows:
- First graph Ax + By = C as a dashed line if equality is NOT included in the original statement or as a solid line if equality is included.
- Choose a test point anywhere in the x-y plane not on the line (original [0,0] usually requires the least computation) and substitutes the coordinates into the inequality.
- The graph of the original inequality includes the half plane containing the test point if the inequality is satisfied by that point or the half plane not containing the test point if the inequality is not satisfied by that point.
Example: The region 2x + 3y > 6 is to the right and top of 2x + 3x = 6 since both a and b are positive.
The region 3x -10y <30 is to the left and top of 3x – 10y =30 since a is positive and b is negative. But how can you solve a system of linear inequalities? Solving a system of linear inequalities graphically means finding the graph of all ordered pairs or real numbers (x,y) that simultaneously satisfy all the inequalities in the system. When a system of linear inequalities is plotted on x-y plane, it defines or produces a feasible region or solution region. A feasible region or solution region is that region of the x-y plane which satisfies all of the inequalities under consideration. The solution region of a system of linear inequalities can be Bounded—if it can be enclosed within a circle or Unbounded—if it can not be enclosed within a circle. To find the solution region, graph each inequality in the system and then take intersection of all the graphs.
Example: Solve the following system of linear inequalities graphically, and find the corner points: 2x + y ≤ 22; x + y ≤ 13; 2x + 5y ≤50; x≥0; y≥0
Note that the corner point of a solution region is a point in the solution region that is the intersection of two boundary lines. This example gives the following corner points: (0,0); (0,10); (11,0); (9,4) and (5, 8).
Linear Programming
Linear Programming (LP) is a problem solving approach developed to help managers make decisions. It is concerned with the problem of maximising or minimising a linear function subject to a set of constraints in the form of a set of inequalities. There are numerous applications of Linear Programming in today’s competitive business environment: For instance, development of a production schedule and an inventory policy that will meet or satisfy demand in future periods and at the same time reduce or minimise total production and inventory costs; selecting an investment portfolio, from among the alternatives, that maximises return on investment; and determining the media mix (radio, newspaper, tv) that maximises advertising effectiveness. The most important properties of linear programming model are:
a) They all have the objective of maximisation or minimisation. For example, minimise cost; maximise return on investment; maximise advertising effectiveness; minimise total transportation cost.
b) They have restrictions or constraints that limit the degree to which the objective can be pursued.
For example: Maximise P = 50x + 80y {Objective function}
Subject to: x + 2y ≤32} Problem constraint
3x + 4y ≤ 84} Problem constraint
x, y ≥ 0} Nonnegative constraints
From this example, X and Y are the decision variables—number or quantity of X and Y that must be produced to maximise or optimise the Objective Function—e.g. maximising profit. The decision variables are the controllable inputs in the problem. Write the Objective Function in terms of the decision variables. The problem constraints indicate or show the limits in terms of available resources. Nonnegative constraints mean that its not possible to produce negative number or quantity of the decision variables. Write the constraints in terms of the decision variables.
Constructing a Linear Programming Model
The following steps may help you to construct a Linear Programming Model:
Step 1: Introduce decision variables
Step 2: Summarise relevant materials in table form, relating the decision variables with the columns in the table.
Step 3: Determine the objective and write a linear objective function.
Step 4: Write problem constraints using linear equations and/or inequalities.
Step 5: Write non negative constraints.
Note: Linear Programming has nothing to do with computer programming. The use of the word programming means choosing a course of action.
Solving Linear Programming Model With Two Decision Variables
To solve a linear programming model with two decision variables, follow these steps:
Step 1: Plot the lines corresponding to each of the given inequalities.
Step 2: Graph or define the feasible region and find the coordinates of each corner point. The optimal value will occur at one or more of the corner points of the feasible region if the optimal value of the objective function in a linear programming problem exists.
Step 3: Make a table listing the value of objective function at each corner point.
Step 4: Determine the optimal solution(s) from the table in step 3.
Step 5: For an applied problem, interpret the optimal solution (s) in terms of the original problem.
Example: A patient at Central hospital is required to have at least 84 units of Cotrimoxazole drug and 120 units of Paracetamol drug each day (assume that an overdose of either drug is harmless). Each gram of substance M contains 10 units of Cotrimoxazole drug and 8 units of Paracetamol drug. Each gram of substance N contains 2 units of Cotrimoxazole drug and 4 units of Paracetamol drug. Now, suppose that both M and N contain undesirable drug D, 3 units per gram in M and 1unit per gram in N.
a. How many grams of each of substances M and N should be mixed to meet the minimum daily requirements and at the same time minimise intake of drug D?
b. How many units of undesirable drug D will be in this mixture?
Solution:
- Let X = number of grams of substance M used and Y = number of grams of substance N used
Solving Linear Programming
- Minimize C = 3x + y} Objective function
Subject to: 10x + 2y ≥ 84 } Drug constraint
8x + 4y ≥ 120} Drug constraint
x, y ≥ 0} Non negative constraints
- After graphing and evaluation of the corner points of the Linear Programming model, the optimal solution was found to be C = 34 at the corner point (4, 22).
- If we use 4 grams of substance M and 22 grams of substance N, we will supply the minimum daily requirements for Cotrimoxazole and Paracetamol drugs and minimise the intake of the undesirable drug D at 34 units.
Take note of the following statements about the existence of Optimal Solutions for Linear programming problems:
a) If the feasible region for a Linear programming problem is bounded, then both the maximum value and the minimum value of the objective function always exist.
b) If the feasible region is unbounded and the coefficients of the objective function are positive, then the minimum value of the objective function exists, but the maximum value does not.
c) If the feasible region is empty—there are no points that satisfy all the constraints, then both the maximum and the minimum value of the objective function do not exist.
d) If two corner points are both optimal solutions to a linear programming problem, then any point on the line segment joining them is also an optimal solution.
Special Cases in Linear Programming
There are some special cases that you may encounter when handling linear programming problems.These include the following:
1. Alternative optimal solutions—whereby more than one solution provides the optimal value for the objective function. This happens where the optimal objective function line coincides with one of the binding constraint lines.
2. Infeasibility—means that no solution to the Linear Programming problem satisfies all constraints, including the non negativity constraints. This means that feasible region does not exist and no points satisfy all constraint equations and non negativity conditions simultaneously. The problem arises mainly because management’s expectations are too high or because too many restrictions have been placed on the problem.
3. Unbounded. The solution to a maximization Linear Programming is unbounded if the value of the solution may be made infinitely large without violating any of the constraints. For minimisation problem, the solution is unbounded if the value may be made infinitely small. The occurrence of an unbounded solution means that the problem has been improperly formulated (such as missing constraint). For example, its not possible to increase profits indefinitely.