- Haulwind - Linear Programming and Operations Research
- 04 Oct 2011 03:17:33 pm
- Last edited by Haulwind on 07 Oct 2011 07:48:40 pm; edited 7 times in total

Hello everyone,

Please use the following thread to review Haulwind's programs.

If you wish your improvements to be published along with your name, please let me know.

Optionally, you can show your own code on this thread as well RELATING TO linear pogramming or operations research; however, please specify IF you want Haulwind to publish it in its network AND whether improvements made in this thread should be included.

All the best,

ilia

Haulwind Team member

==================================================

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,

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

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

==================================================

The following contains the SIMPLEX METHOD (Linear Programming, Maximization, Minimization, and Excess Analysis). Using material from Frederick S. Hiller, Gerald J. Lieberman. Introduction to Operations Research. New York: McGraw Hill, 2005. Print.

maximize Z,

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

or minimize Z,

where Z = b * Y AND y * A ≥ C

where C,Y, and b are vectors; and A is a Matrix

e.g. max Z; b1Y1 + b2Y2 + b3Y3 = Z

A1Y1+ A3Y2+ A5Y3 ≥ C1

A2Y1+ A4Y2+ A6Y3 ≥ C2

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

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

==================================================

Please use the following thread to review Haulwind's programs.

If you wish your improvements to be published along with your name, please let me know.

Optionally, you can show your own code on this thread as well RELATING TO linear pogramming or operations research; however, please specify IF you want Haulwind to publish it in its network AND whether improvements made in this thread should be included.

All the best,

ilia

Haulwind Team member

==================================================

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,

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

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

**Code:**```
```

DIM(L1) -> N

DIM(L2) -> M

{1,1} -> DIM[B]

0 -> DIM(L5)

-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

[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

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

==================================================

The following contains the SIMPLEX METHOD (Linear Programming, Maximization, Minimization, and Excess Analysis). Using material from Frederick S. Hiller, Gerald J. Lieberman. Introduction to Operations Research. New York: McGraw Hill, 2005. Print.

maximize Z,

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

or minimize Z,

where Z = b * Y AND y * A ≥ C

where C,Y, and b are vectors; and A is a Matrix

e.g. max Z; b1Y1 + b2Y2 + b3Y3 = Z

A1Y1+ A3Y2+ A5Y3 ≥ C1

A2Y1+ A4Y2+ A6Y3 ≥ C2

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

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

**Code:**```
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(C) -> L2(C)

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

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

0 -> DIM(L5)

0 -> DIM(L6)

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 IS 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

==================================================