Example of Phase 1 and Unboundedness

>	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<=-5, 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,-5],[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,2,6);

Continue pivoting to Phase 1 optimality.

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

The objective function is zero, so the LP is feasible.

Delete the artificial variable and replace the Phase 1 objective function with the Phase 2 objective function.

>	T3:=delcols(T2,6..6):T3[4,1]:=3:T3[4,2]:=-1:evalm(T3);

Perform the preliminary pivots to make the tableau basic again.

>	T4:=mypivot(T3,2,2);

Proceed with Phase 2 pivoting.

>	T5:=mypivot(T4,1,1);

>	T6:=mypivot(T5,3,4);

At this point we discover that the LP is unbounded.

>