SIMPLEX‎ > ‎

### SIMPLEX METHOD [Maximization]

 The following contains the SIMPLEX METHOD (Linear Programming, Maximization) Using material fromFrederick S. Hiller, Gerald J. Lieberman. Introduction to Operations Research. New York: McGraw Hill, 2005. Print.maximize Z, which is the objective functionwhere Z = C * X AND A * X ≤ bwhere C, X, and b are vectors; and A is a Matrixe.g. max Z; C1* X1 + C2* X2 = ZA1* X1 + A2* X2 ≤ b1A3* X1 + A4* X2 ≤ b2A5* X1 + A5* X2 ≤ b3INPUTC = { C1, C2 } = L1b = { b1, b2, b3 } = L2A = [ A1 A2           A3 A4           A5 A6 ] = [A]OUTPUTX = [ X1 X2 ] = LEZ = 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`