Solve the linear program
| x1 | x2 | x3 | x4 | 1 | Homework 4 |
| 1 | -1 | 0 | 2 | 0 | = x5 |
| -1 | 2 | 1 | -1 | 2 | = x6 |
| 0 | -1 | -1 | 1 | 1 | = x7 |
| 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 x2-column
(the pivot column). The pivot row is x5-row, the
maximal
ratio is 0 :
| x1 | x2 | x3 | x4 | 1 | |
| 1 | -1 | 0 | 2 | 0 | = x5 |
| -1 | 2 | 1 | -1 | 2 | = x6 |
| 0 | -1 | -1 | 1 | 1 | = x7 |
| 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
| x1 | x5 | x3 | x4 | 1 | |
| 1 | -1 | 0 | 2 | 0 | = x2 |
| 1 | -2 | 1 | 3 | 2 | = x6 |
| -1 | 1 | -1 | -1 | 1 | = x7 |
| -1 | 1 | 2 | -2 | 1 | -> min |
The pivot step gives
| x1 | x5 | x3 | x7 | 1 | |
| -1 | 1 | -2 | -2 | 2 | = x2 |
| -2 | 1 | -2 | -3 | 5 | = x6 |
| -1 | 1 | -1 | -1 | 1 | = x4 |
| 1 | -1 | 4 | 2 | -1 | -> min |
The objective function (on the basic solution) improved from 1 to -1.
The x5-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.