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;
C1X1 + C2X2 = Z
A1X1+ A2X2 ≤ b1
A3X1+ A4X2 ≤ b2
A5X1+ A5X2 ≤ b3
MAXIMIZATION 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
minimize Z, which is the objective function
where Z = b * Y AND y * A ≥ C
where C, Y, and b are vectors; and A is a Matrix
e.g. min Z;
b1Y1 + b2Y2 + b3Y3 = Z
A1Y1+ A3Y2+ A5Y3 ≥ C1
A2Y1+ A4Y2+ A6Y3 ≥ C2
MINIMIZATION INPUT
C = {C1, C2}= L2
b = {b1, b2,b3}= L1
A = [ A1 A3 A5
A2 A4 A6 ]
= [A]
OUTPUT
Y = [Y1 Y2 Y3]= LF
Z = 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