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 optimal and has no bad columns
The only minus in the cpart 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.