SIMPLEX‎ > ‎

### SIMPLEX METHOD [Maximization, Minimization]

 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; C1X1 + C2X2 = ZA1X1+ A2X2 ≤ b1A3X1+ A4X2 ≤ b2A5X1+ A5X2 ≤ b3MAXIMIZATION INPUTC = {C1, C2}= L1b = {b1, b2,b3}= L2A = [ A1 A2             A3 A4             A5 A6 ]= [A]OUTPUTX = [X1 X2]= LEZ = Zminimize Z, which is the objective functionwhere Z = b * Y AND y * A ≥ Cwhere C, Y, and b are vectors; and A is a Matrixe.g. min Z; b1Y1 + b2Y2 + b3Y3 = ZA1Y1+ A3Y2+ A5Y3 ≥ C1A2Y1+ A4Y2+ A6Y3 ≥ C2 MINIMIZATION INPUTC = {C1, C2}= L2b = {b1, b2,b3}= L1A = [ A1 A3 A5            A2 A4 A6 ]= [A]OUTPUTY = [Y1 Y2 Y3]= LFZ = Z`DIM(L1)→ N`` DIM(L2) → M`` {1,1} → DIM[B]`` 0 → DIM(L5)` ` DISP “CHOOSE 1 FOR MAXIMIZATION SETUP OR 2 FOR MINIMIZATION SETUP ”`` INPUT X` ` IF X = 1`` THEN `` GOTO 2 `` ELSE`` FOR (A,1,N,1)`` L1(A)→ L5(A)`` END` ` 0→ DIM(L1)`` FOR (B,1,M,1)`` L2(B)→ L1(B)`` END` ` 0→ DIM(L2)`` FOR (C,1,N,1)`` L5©→ L2©`` END` ` {N,M}→ DIM([B])`` FOR (C,1,M,1)`` FOR (D,1,N,1)`` [A](C,D) → [B](D,C)`` END END` ` { 1,1 } → DIM( [A] )`` [B] → [A]`` END` ` LBL 2` ` DIM(L1) → N`` DIM(L2) → M`` -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` ` 1→ P`` 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` ` [B]-1→ [D]`` FOR (A,1,M,1)`` L6(L3(A))→ L5(A)`` END` ` L5 → LZ`` 0→ DIM(LC)` ` 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` ` N → 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`` 0→ DIM(L5)`` 0→ DIM(L6)` ` IF X = 2`` THEN`` DISP “THE OPTIMAL QUANTITY FOR EACH RESOURCE IS”`` DISP LF`` ELSE`` 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`` END` ` IF X = 1`` THEN`` FOR(B,1,M,1)`` FOR(A,1,N,1)`` LE(A)*[A](B,A) → L5(A)`` END`` SUM(L5)→ L6(B)`` END`` LD - L6 → L6`` 0→ DIM(L5)`` DISP “EXCESS RESOURCES: FIRST VALUE IS VECOR IS THE LINE, THE SECOND VALUE IS THE EXCESS AMOUNT”`` FOR(A,1,M,1)`` IF L6(A) > 0`` THEN`` A→ L5(1)`` L6(A)→ L5(2)`` DISP L5`` END END`` ELSE `` FOR(A,1,N,1)`` FOR(B,1,M,1)`` LF(B)*[A](B,A) → L5(B)`` END`` SUM(L5)→ L6(A)`` END`` L6+LX → L6`` 0→ DIM(L5)`` DISP “EXCESS RESOURCES: FIRST VALUE IN VECOR IS THE LINE, THE SECOND VALUE IS THE EXCESS AMOUNT”`` FOR (A,1,N,1)`` IF L6(A) > 0`` THEN`` A→ L5(1)`` L6(A)→ L5(2)`` DISP L5`` END END END` ` CLEARALLLISTS`