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