SIMPLEX METHOD [Maximization, Minimization]

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