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 optimal 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.