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.