Solve the linear program
x_{1} | x_{2} | x_{3} | x_{4} | _{1} | Homework 4 |
1 | -1 | 0 | 2 | 0 | = x_{5} |
-1 | 2 | 1 | -1 | 2 | = x_{6} |
0 | -1 | -1 | 1 | 1 | = x_{7} |
0 | -1 | 2 | 0 | 1 | -> min |
Solution.
Simplex method: Phase 1. Feasible tableau.
Phase 2. Tableau is not optomal and has no bad columns
The only minus in the c-part is is in x_{2}-column
(the pivot column). The pivot row is x_{5}-row, the
maximal
ratio is 0 :
x_{1} | x_{2} | x_{3} | x_{4} | _{1} | |
1 | -1 | 0 | 2 | 0 | = x_{5} |
-1 | 2 | 1 | -1 | 2 | = x_{6} |
0 | -1 | -1 | 1 | 1 | = x_{7} |
0 | -1 | 2 | 0 | 1 | -> min |
The pivot step is degenerate and the new tableau is mot
optimal. Here it is with the next pivot entry indicated by
x_{1} | x_{5} | x_{3} | x_{4} | _{1} | |
1 | -1 | 0 | 2 | 0 | = x_{2 } |
1 | -2 | 1 | 3 | 2 | = x_{6} |
-1 | 1 | -1 | -1 | 1 | = x_{7} |
-1 | 1 | 2 | -2 | 1 | -> min |
The pivot step gives
x_{1} | x_{5} | x_{3} | x_{7} | _{1} | |
-1 | 1 | -2 | -2 | 2 | = x_{2 } |
-2 | 1 | -2 | -3 | 5 | = x_{6} |
-1 | 1 | -1 | -1 | 1 | = x_{4} |
1 | -1 | 4 | 2 | -1 | -> min |
The objective function (on the basic solution) improved from 1 to -1.
The x_{5}-column is bad,
so the problem is unbounded..
Another solution. By one pivot step (with pivot chosen not acording
the simplex method) we can obtain
a feasible tableau with a bad column.