! Simple Simplex iterator exploiting the (Simplex.lg4)
  programming capabilites of a LINGO CALC section.
 Assumptions:
   First row of matrix is objective,
   Objective is MIN,
   Last column of matrix is RHS,
   Constraints are already in equality form,
   Initial tableau is feasible.
 Simplex iterations are performed until either:
   tableau is optimal, or
   entering column is unbounded, or
   iteration limit, ITERLIM, is exceeded;
! Keywords: Simplex method, Algorithm for LP, Primal simplex,
            Tableau, Pivoting;

SETS:
 ROW; 
 COL;
 RXC( ROW, COL): A;
ENDSETS
DATA: ! The Astro-Cosmo problem. Max = 20 A + 30 C + 47 D, A + D <= 60, C + D <= 50, A + 2 C + 3 D <= 120, The last three variables in the tableau, cols 4-6, are the slack variables; ! Names of columns; COL = A__ C__ D__ S_1 S_2 S_3 RHS; ! Names of rows; ROW = OBJ ALN CLN LAB; ! Matrix coefficients; A = -20 -30 -47 0 0 0 0 1 0 1 1 0 0 60 0 1 1 0 1 0 50 1 2 3 0 0 1 120 ; ! Some tolerances; BigM = 9999999; ! Infinity for our purposes; TOLRC = .000001; ! Entering variable reduced cost; TOLPIV = .000001; ! Minimum acceptable pivot size; ITERLIM = 10; ! Iteration limit; ENDDATA CALC: @SET('TERSEO', 2); ! Turn off default output; @SET('LINLEN', 80); ! Set line length for output; N = @SIZE( COL); M = @SIZE( ROW); ITER = 0; ! Number of iterations so far; ! Iterate while MORE = 1; MORE = 1; @WHILE( MORE: ! The major loop; @WRITE(@NEWLINE(1), ' Current tableau:', @NEWLINE(1),' '); @FOR( COL(j): @WRITE( ' ',COL(j))); @WRITE(@NEWLINE(1)); @FOR( ROW(i): @WRITE(' ',ROW(i),': '); @FOR( COL( j): @WRITE( @FORMAT(A(i,j),"9.4F"), ' '); ); @WRITE( @NEWLINE(1)); ); ! Find entering variable; JPIV = 0; RCBEST = - TOLRC; @FOR( COL(j) | j #LT# N: @IFC( A(1,j) #LT# RCBEST: JPIV = j; RCBEST = A(1,j); ); ); @IFC( JPIV #GT# 0: @WRITE( @NEWLINE(1),' Entering column= ', COL(JPIV), @NEWLINE(1)); @ELSE MORE = 0; ! Indicate we are done; @WRITE(@NEWLINE(1),' No more attractive pivots possible.', @NEWLINE(1)); ); ! Update iteration count; @IFC( JPIV #GT# 0: ITER = ITER + 1); @IFC( ITER #GT# ITERLIM: MORE = 0; @WRITE(@NEWLINE(1),' Exceeded iteration limit of ', ITERLIM, @NEWLINE(1)); ); ! Find a pivot row that maintains feasibility; @IFC( MORE: IPIV = 0; PIVBEST = BigM; @FOR( ROW(i) | i #GT# 1: @IFC( A(i,JPIV) #GT# TOLPIV: RATIO = A(i,N)/A(i,JPIV); @IFC( RATIO #LT# PIVBEST: PIVBEST = RATIO; IPIV = i; ); ); ! @IFC( A(i,JPIV)...; ); ! @FOR( ROW(i)...; @IFC( IPIV #GT# 0: @WRITE(' Pivot row= ', ROW(IPIV),', giving the new'); @ELSE MORE = 0; ! We are done flag; @WRITE(@NEWLINE(1),' No pivot row found. Entering column is unbounded.', @NEWLINE(1)); ); ! @IFC( IPIV...; ! Do the pivot, if allowed; @IFC(MORE: PIVOT = A( IPIV, JPIV); ! Update pivot row; @FOR( COL(j): A(IPIV,j) = A(IPIV,j)/ PIVOT; ); ! Update other rows; @FOR( ROW(i) | i #NE# IPIV: AIJP = A(i,JPIV); @FOR( COL(j): A(i,j) = A(i,j) - AIJP*A(IPIV,j); ); ); ! @FOR( ROW(i)...; ); ! @IFC(MORE ...; ); ! @IFC( MORE ...; ); ! @WHILE( MORE....; ENDCALC