Return to the
List of Activities This activity is designed to help you understand the process of solving linear programming problems algebraically by determining the extreme points of the feasible region and developing rules for searching for the optimal solution by moving to successively better solutions. We will use the underlying ideas in this process to build a matrix oriented solution process called the Simplex method. Later in the course we will see how this process can be automated and done on a computer in seconds.
| 1. Put in Standard Form | Add slack or subtract surplus variables to put the problem in the form: Minimize C'X subject to AX = b, X ò 0. |
| 2. Find Identity Basis <\TD> | Check that the Identity matrix is a submatrix of A. If not, stop! You cannot use this process. |
| 3. Choose Variable to become Basic | Find the objective function variable whose increase will cause the greatest decrease in the objective function. |
| 4. Solve for Basic Variables | Solve each of the constraints for its basic variable. |
| 5. Apply Minimum Ratio Rule | Divide the coefficient of the variable chosen in step 3 into the constant term in each step 4 equations and use the minimum quotient to find the variable to remove from the basis. |
| 6. Write new Basis Matrix | Replace the column corresponding to the variable leaving the basis with the column of A corresponding to the variable entering the basis to form a new basis matrix. Write its BFS. |
| 7. Repeat Steps 3-6 | Check objective function to find another variable to bring into the basis and repeat process. When there are no more variables that can be increased you are finished. The final basic feasible solution is optimal. |
Solve the following linear programming problem:
Minimize 3y1 - 4y2
subject to: 2y1 + y2 <= 4
y1 + y2 <= 3
y1 >= 0, y2 >= 0
The standard form is as follows: (See Activity 5) Note that x3 and x4 are slack variables.
minimize 3y1 - 4y2
subject to 2y1 + y2 + y3 = 4
y1 + y2 + y4 = 3
y1 >= 0, y2 >= 0, y3 >= 0, y4 >= 0
| 2 1 1 0 | | 4 | X = [y1 y2 y3 y4]'
A = | 1 1 0 1 | b = | 3 | C = [3 -4 0 0]'
The last two columns of A form the Identity matrix. Thus the basic variables are y3 and y4. The nonbasic variables are y1 and y2. The basic feasible solution is [0 0 4 3]'.
Increasing y2 in the objective function will decrease the objective function and so we choose to bring it into the basis.
The constraint equations become:
y3 = -2y1 - y2 + 4
y4 = -y1 - y2 + 3
The ratios are 4/1 and 3/1. The smallest of these is 3/1, the ratio from the second equation. Since the basic variable on the left of the second equation is y4, we remove it from the basis, replacing it by y2.
The new basis matrix is | 1 1 |
| 0 1 |
Augmenting this matrix and reducing it to Row Echelon Form we obtain the following basic feasible solution.
| 1 1 | 4 | | 1 0 | 3 | | 0 1 | 3 |--->| 0 1 | 3 |
The basic feasible solution is [ 0 3 1 0 ]'
Since the coefficient of y1 in the objective function is positive, we should not try to bring it into the basis since increasing y1 would increase the objective function. Since there are no more variables with negative coefficients in the objective function we are finished. The optimal solution to this problem is y1 = 0, y2 = 3, y3 = 1, y4 = 0. You should compare it to the graphic solution.
In order to solve a problem algebraically we must replace the constraint inequalities by equalities. This is what is done by converting the problem to standard form. Doing this increases the dimension of the feasible region, but there is a 1-1 correspondence between the extreme points of the original feasible region and those of the new feasible region. Thus, solutions to the problem in standard form yield solutions to the original problem.
To get started, we can set the slack variables to the right hand side constants and the other variables to zero and obtain a solution to the constraint equations. Since the right hand side constants must be non- negative, we are assured that this solution is feasible. Thus it is an initial basic feasible solution. If the coefficient matrix has no Identity submatrix, we cannot find this initial basis matrix and other solution methods must be found.
Our goal is to minimize the objective function, so we try to increase variables which have negative coefficients. Note: variables must be non-negative in a linear programming problem, so if they are already zero in a basic feasible solution we have no other choice but to increase them. The variable with the most negative coefficient is usually chosen because increasing its value will decrease the objective function the fastest.
This step is preliminary to choosing the basic variable which will become nonbasic. If a variable in an equation is increased, another (currently basic) must be decreased to maintain equality. But, we cannot decrease a variable below zero in an LP problem. Setting up the equations in this step makes it easier to watch for problems in the next.
If you replace the variable to be brought into the basis by the value obtained by dividing the negative of its coefficient into the constant term in each of the equations from step 4, the variables on the left will be forced to 0. We choose to replace in the basis the left-hand-side variable from the equation with the minimum ratio because otherwise we would force one of the variables on the left to become negative. Note that if the coefficient of the variable to be brought into the basis is positive in an equation after solving for the basic variables, we do not consider that equation when evaluating minimum ratios, since increasing this variable will increase, not decrease, the variable on the left.
We replace the column in the basis matrix corresponding to the variable being made nonbasic with the column in A corresponding to the variable we are bringing into the basis. Solving the new BX = b we obtain a new basic feasible solution. We will see later that it is important not to rearrange the columns of the basis matrix so they are in the same order as the coefficient matrix. Simply substitute one column for another.
Often, this new basic feasible solution, although it corresponds to an extreme point in the feasible region, is not the optimal solution. If there are negative coefficients on currently nonbasic variables in the objective function, we should bring one of these into the basis. The procedure we used above should be repeated until all variables with negative objective function coefficients are in the basis.
minimize -3x1 - 2x2 C = [-3 -2]'
subject to X = [x1 x2]'
2x1 + x2 <= 80 b = [80 50]'
x1 + x2 <= 50 | 2 1 |
x1 >= 0, x2 >= 0 A = | 1 1 |
| 2 1 1 0 | | 1 0 |
A^ = | 1 1 0 1 | Initial B = | 0 1 | X^ = [x1 x2 x3 x4]'
Note that the matrix forms for the standard form are given above.
minimize -3x1 - 2x2
subject to 2x1 + x2 + x3 = 80
x1 + x2 + x4 = 50
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0
The initial basic feasible solution is [0 0 80 50]T. The basic variables are x3 and x4 since the Identity submatrix of the coefficient matrix corresponds to these variables. The nonbasic variables are x1 and x2. The objective function value is 0 for this solution.
If we bring x2 into the basis we will increase its value and hence drive down the objective function value. Even though the coefficient of x1 is more negative than that of x2 it takes longer to find the optimal solution if we start with x1. There is no way you could know this at this point in the process, but I did it both ways and will show you the easiest way.
x3 = 80 - 2x1 - x2
x4 = 50 - x1 - x2
Note that x1 is nonbasic and thus has value 0. Therefore, the x1 terms do not enter into the computation when we attempt to increase x2.
We see that x2 can get no bigger than 50 without making one of the variables (x4) negative. The ratios are 50/1 and 80/1, so the minimum ratio 50/1 implies that we should make x4 nonbasic.
Thus the next B matrix becomes
| 1 1 | | 0 1 |
where the column corresponding to x4 in the previous B has been replaced by the column corresponding to x2. Solving the augmented matrix:
| 1 1 | 80 | | 1 0 | 30 | | 0 1 | 50 | ---> | 0 1 | 50 |
we get the new basic feasible solution [0 50 30 0]T with an objective function value -100.
We see that we can further reduce the objective function by increasing the value of x1 from 0, so we bring it into the basis. To determine which of the current basic variables we will take out of the basis we solve the standard form of the problem for the current basic variables and apply the minimum ratio rule:
x3 = 80 - 2x1 - x2 = 80 - 2x1 - 50 = 30 - 2x1
x2 = 50 - x1 - x4 = 50 - x1 - 0 = 50 - x1
We see that x1 can get no bigger than 15 without making one of the variables (x3) negative. The ratios are 30/2 and 50/1. Thus, we must replace x3 by x1 as a basic variable.
The next B matrix becomes
| 2 1 | | 1 1 |
where the column corresponding to x3 in the previous B has been replaced by the column corresponding to x1. Solving the augmented matrix:
| 2 1 | 80 | | 1 1 | 50 | | 1 0 | 30 | | 1 1 | 50 | ---> | 0 -1 |-20 | ---> | 0 1 | 20 |
we get the new basic feasible solution [30 20 0 0]' with an objective function value -130. Since we cannot increase x1 or x2 any further we have reached an optimal solution.
These will be provided in class.
Minimize C'X where AX <= b or A^X^ = b
Plot the feasible region. Also find the initial basis matrix B, identify the basic and nonbasic variables associated with B and write the initial basic feasible solution.
minimize x1 - 2x2
subject to
x1 + 5x2 <= 5
2x1 + x2 <= 4
x1 >= 0, x2 >= 0
Return to the
List of Activities