Homework 4


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 = x
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 = x
-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.