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