# SIMPLEX METHOD [Maximization]

The following contains the SIMPLEX METHOD (Linear Programming, Maximization)

Using material from

Frederick S. Hiller, Gerald J. Lieberman. Introduction to Operations Research. New York: McGraw Hill, 2005. Print.

maximize Z, which is the objective function

where Z = C * X AND A * X ≤ b

where C, X, and b are vectors; and A is a Matrix

e.g. max Z;

C1* X1 + C2* X2 = Z

A1* X1 + A2* X2 ≤ b1

A3* X1 + A4* X2 ≤ b2

A5* X1 + A5* X2 ≤ b3

INPUT

C = { C1, C2 } = L1

b = { b1, b2, b3 } = L2

A = [ A1 A2

A3 A4

A5 A6 ] = [A]

OUTPUT

X = [ X1 X2 ] = LE

Z = Z

``DIM(L1) → N``
``DIM(L2) → M``
``{1,1} → DIM[B]``
``-L1 → L1``
``AUGMENT( [A], IDENTITY[M] ) → [C]``
``1 → K``
``WHILE L1(K) ≠ MIN(L1)``
``K+1 → K``
``END``
``0 → DIM(L4)``
``M → DIM(L4)``
``0 → DIM(L3)``
``0 → DIM(L5)``
``0 → DIM(LZ)``
``{1,1} → DIM([B])``
``L2 → LD``
``L1 → LX``
``FOR (A,1,M,1)``
``A+N → L3(A)``
``END``
``LBL 1``
``AUGMENT ( -LX, L4 )→ L6``
``0 → DIM(LK)``
``FOR(Q,1,M,1)``
``IF [A](Q,K) ≠ 0``
``THEN``
``L2(Q)/[A](Q,K) → LK(Q)``
``ELSE``
``MAX(L2) → LK(Q)``
``END END``
``1 → Y``
``FOR (Q,1,M,1)``
``IF [A](Q,K) ≠ 0``
``THEN``
``IF (L2(Q)/[A](Q,K)) = MIN(LK)``
``THEN``
``IF Y = 1``
``K → L3(Q)``
``Y+1 → Y``
``END END END END``
``{M,M} → DIM([B])``
``FOR(A,1,M,1)``
``FOR(B,1,M,1)``
``[C](B,L3(A)) → [B](B,A)``
``END``
``END``
``FOR (A,1,M,1)``
``L6(L3(A)) → L5(A)``
``END``
``L5 → LZ``
``0 → DIM(LC)``
``[B]-1 → [D]``
``FOR(A,1,M,1)``
``FOR(B,1,M,1)``
``[D](A,B)*LD(B) → L5(B)``
``END``
``SUM(L5) → LC(A)``
``END``
``LC → L2``
``N → DIM(LE)``
``0 → DIM(LF)``
``FOR(B,1,M,1)``
``FOR(A,1,M,1)``
``LZ(A)*[D](A,B) → L5(A)``
``END``
``SUM(L5) → LF(B)``
``END``
``0 → DIM(LY)``
``FOR(B,1,N,1)``
``FOR(A,1,M,1)``
``LF(A)*[A](A,B) → L5(A)``
``END``
``SUM(L5) → LY(B)``
``END``
``LY + LX → L1``
``IF MIN(L1) < 0``
``THEN``
``1 → K``
``WHILE L1(K) ≠ MIN (L1)``
``K+1 → K``
``END``
``GOTO 1``
``END``
``SUM (LZ*L2) → Z``
``DISP “THE OPTIMAL SOLUTION IS”``
``DISP Z``
``FOR(A,1,M,1)``
``FOR(B,1,N,1)``
``IF L1(B) = 0``
``THEN``
``IF L3(A) = B``
``THEN``
``L2(A) → LE(B)``
``END``
``ELSE``
``0 → LE(B)``
``END END END``
``DISP “THE OPTIMAL QUANTITY FOR EACH RESOURCE IS”``
``DISP LE``
``CLEARALLLISTS``