Example of Phase 1 and Infeasibility

> with(plots): with(linalg):

Warning, the name changecoords has been redefined

Warning, the protected names norm and trace have been redefined and unprotected

Define and graph the region.  I include an objective function line as well.

> G1:=inequal( {x-2*y<=-4, y<=1, 2*x-y<=10, x>=0, y>=0}, x=-1..14, y=-1..14, optionsfeasible=(color=yellow), optionsexcluded=(color=white) ):

> G2:=implicitplot(3*x-y=20,x=-1..14,y=-1..14,color=black,thickness=3):

> display({G1,G2},scaling=constrained);


Define a simplex pivot function.

> mypivot:=(M,i,j)->pivot(mulrow(M,i,1/M[i,j]),i,j);

Set up the Phase 1 tableau.

> T0:=array([[1,-2,1,0,0,-1,0,-4],[0,1,0,1,0,-1,0,1],[2,-1,0,0,1,-1,0,10],[0,0,0,0,0,-1,1,0]]);

Perform the preliminary pivot to bring the tableau into feasible form.

> T1:=mypivot(T0,1,6);

Continue pivoting to Phase 1 optimality.

> T2:=mypivot(T1,2,2);


The objective function is positive, so the LP is infeasible.