SIMPLEX‎ > ‎

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
Comments