Simplex Method Exercises for Linear Programming
Translated by
ScribdTranslationsSimplex Method Exercises for Linear Programming
Translated by
ScribdTranslationsEXERCISES
SIMPLEX METHOD FOR SOLVING A LINEAR PROGRAM
1) Maximize Z = 4x1+ 3x2+ 2x3
s.a.
2x1+ x2+ x3 30
2x1+ x2+ 2x329 ………….. (2)
x1+ 2x2+ x3=19 ………….. (3)
xj 0, for j=1,2,3
Solution:
Transforming to standardized form:
Maximize Z = 4x1+ 3x2+ 2x3+ 0x4+ 0x5-Mx6Mx7
s.a.
2x1+ x2+ x3+ x4= 30 + VH
[2x1+ x2+ 2x3- x5+ x6= 29]x (-M) VE+ VA
[1+ 2x2+ x3 + x7= 19]x (-M) +VA
xj 0, paraj=1,2,3, ………….,7
Mx6and Mx7they influence the objective function, they need to be eliminated; it is necessary to rethink
the objective function:
Z-4x 1-3x2-2x3+0x4+0x5+Mx6+Mx7=0
-2Mx1-Mx2-2Mx3 +Mx5-Mx6 -29M
-Mx1-2Mx2-Mx3 -Mx7-19M
Z+(-4-3M)x1+(-3-3M)x2+(-2-3M)x3+0x4+Mx5+0x6+0x7-48M
Basic variables
Z X1 X2 X3 X4 X5 X6 X7 bi C.C. bi/aij
F1 Z 1 -4-3M -3-3M -2-3M 0 M 0 0 -48M -8-56M 1.1)F3/2
1.2) F1–F3(-4-3M)
F2 X40 2 1 1 1 0 0 0 30 35 30/2=15 2
1.3) F2–F3(2)
F3 X60 2 1 2 0 -1 1 0 29 34 29/2=14.5 2
F4 x70 1 2 1 0 0 0 1 19 24 19/1=19 1.4) F4–F3(1)
2
Z X1 X2 X3X4 X5 X6 X7 bi C.C. bi/aij
2.1)F4(3/2)
F1Z 1 0 -1-(3/2)M 2 0 -2-(½)M 2+(3/2)M 0 58 - (9/2)M 60-5M 2.2) F1-F4[-1-(3/2)M]
(3/2)
F2X40 0 0 -1 1 1 -1 0 1 1 1/0=
2.3) F2–F4(0)
F3X10 1 1/2 1 0 -½ ½ 0 29/2 17 29/2:1/2=29 (3/2)
2.4) F3–F4(1/2)
F4x70 0 3/2 0 0 ½ -½ 1 9/2 7 9/2:3/2=3 (3/2)
F1From 1 to 0 0 2 0 -5/3 5/3+M 2/3+M 61 (194/3)+2M 3.1)F2/1
3.2) F1–F2-5/3
F2X40 0 0 -1 1 1 -1 0 1 1 1/1=1 1
3.3) F3F2-2/3
F3X10 1 0 1 0 -2/3 2/3 -1/3 13 44/3 13:-2/3=-39/2 1
3.4) F4–F2(1/3)
F4x70 0 1 0 0 1/3 -1/3 2/3 3 14/3 3:1/3=9
1
F1From 1 to 0 0 1/35/3 0 M 2/3 + M 188 divided(199/3)+2M
by 3
F2X40 0 0 -1 1 1 -1 0 1 1 SOLUTION
OPTIMAL
F3X10 1 0 1/32/3 0 0 -1/3 41/3 46/3 UNIQUE
F4x70 0 1 1/3-1/3 0 0 2/3 8/3 13/3
Thus, the solution to this problem is:
Maximize Z = 188/3, for: x3= x4= x6= x7= 0
x1= 41/3; x2= 8/3 y x5= 1
Use the simplex algorithm to find the optimal solution for the following LP:
1) Maximize Z = 100x1+ 120x2
s.a.
4x1+ 8x2 480 …….…...(1)
5x1+ 6x2 600
12x1+ 8x2 540 ……….... (3)
x1,x2 0
2) Maximize Z = 2x1+ 6x2+ 5x3
s.a.
4x1+ 3x2+ x3 24
3x1+ 2x2+ 6x3 50…………. (2)
5x1+ 3x2+ 2x3 20
xj 0, for j=1,2,3
3) Maximize Z = 5x1+ 7x2 + 2x3
s.a.
x1+ x2+ 3x3 35 ………...(1)
2x1+ x2+ x3 40…………. (2)
x1+ 2x2+ x3 50........... (3)
xj 0, for j=1,2,3
4) Maximize Z = 2x1+ x2+ 3x3+ 2x4
s.a.
2x1+ x2+ x3 20
x1 + 2x3+ x4 24…………. (2)
2x2+ x3+ 3x4 30……….... (3)
xj 0, for j=1,2,3,4
5) Maximize Z = 4x1+ 3x2+ 2x3
s.a.
2x1+ x2+ x3 30 ………...(1)
2x1+ x2+ 2x3 29…………. (2)
x1+ 2x2+ x3=19 …..……....(3)
xj 0, for j=1,2,3
6) Maximize Z = 4x1+ 3x2+ 2x3
s.a.
2x1+ x2+ x3 30
x1+ 2x2+ x3 30........... (2)
2x1+ x2+ 2x3= 26……….... (3)
xj 0, for j=1,2,3
7) Minimize Z = 5x1+ 3x2+ 6x3
s.a.
2x1+ x2+ x3 30 …………...(1)
2x2+ x3 30 ........(2)
2x1+ x2+ 2x3 26
xj 0, for j=1,2,3
8) Minimize Z = 5x1+ 8x2
s.a.
8x1+ 4x2 24...... (1)
10x1+ 30x2 40............ (2)
x1,x2 0
Functional parallel to one side of the polygon
9) Maximize Z = 4x1+ 2x2
S.A.
x1+ 3x2 15000
2x1+ x2 10000…………...(2)
2x1+ 2x2 12000................(3)
x1+ x2 10000…………...(4)
x1,x2 0
Problem without solution (Infeasible Solution or Unsolvable Problem)
10) Maximize Z = 2x1+ 2x2
s.a.
x1+ x2 2........ (1)
x1+ x24.........(2)
x1, x2 0
Degeneration Case in Linear Programming
Number of Existing Variables in the Solution
DEGENERATION
11) Maximize Z = 3x1+ 9x2
s.a.
x1+ 4x2 8 …………...(1)
x1+ 2x2 4…………...(2)
x1x2 0
12) Maximize Z = 5x1+ 7x2+ 2x3
S.A.
x1+ x2+ 3x3 30
2x1+ x2+ x3 35………...(2)
x1+ 2x2+ x3 40
xj 0, for j=1,2,3
13) Maximize Z = 3x1+ 4x2+ 2x3+ 2x4
s.a.
x1+ 3x2 + x4 10…….…... (1)
2x2+ x3+ 3x4 26…….…...(2)
3x1+ 4x3+ x4 36…….…...(3)
xj 0, for j=1,2,3
14) Minimize Z = 7x1+ 5x2+ 8x3
s.a.
x1+ x2+ 2x3 20......... (1)
2x1+ x2+ x3 20...
2x1+ 3x2+ x3 30
xj 0, for j=1,2,3
15) Maximize Z = 5x1+ 7x2+ 2x3
s.a.
x1+ x2+ 3x3= 35…….…... (1)
2x1+ x2+ x3 40…….…... (2)
x1+ 2x2+ x3 50........ (3)
xj 0, for j=1,2,3
16) Minimize Z = x1- 2x2+ 2x3
s.a.
2x1- x2- x3 -20........... (1)
x1+ x2+ 2x3 30…….…...(2)
- x1+ 2x2+ x3= 24…….…...(3)
xj 0, for j=1,2,3
17) Maximize Z = 3x1+ 5x2+ 7x3
s.a.
2x1+ 3x2+ x3 30...
x1+ 2x2- 4x3= 18…….…... (2)
6 times1+ 9x2+ 3x3 50...
xj 0, for j=1,2,3
Functional parallel to one side of the polygon
Maximize Z = 4x1+ 14x2
s.a.
2x1+ 7x2 21...... (1)
7x1+ 2x2 21 …….…...(2)
x1x2 0
Parallel function to one side of the polygon
19) Maximize Z = 5x1+ 2x2
s.a.
6x1+ 10x2 30...... (1)
10x1+ 4x2 20…...… (2)
x1x2 0
Problem without solution
20) Maximize Z = 2x1+ x2
s.a.
- 2x1+ 3x2 6………... (1)
x2 3…….…...(2)
x1x2 0
Problem without solution
21) Maximize Z = 5x1+ 8x2
s.a.
2x1+ x2 6....... (1)
x1+ 3x2 4...... (2)
x1x2 0
Problem without solution
22) Maximize Z = 2x1+ x2
s.a.
x1- x2 10......... (1)
2x1- x2 40
x1x2 0
Problem without solution
23) Maximize Z = x1+ 2x2
s.a.
2x1+ 4x2 8...... (1)
x1+ 2x2 2...... (2)
x1,x2 0
Problem without solution
Maximize Z = 3x1+ 2x2
s.a.
2x1+ x2 2...... (1)
3x1+ 4x2 12 ....... (2)
x1x2 0
Problem without solution
25) Maximize Z = 2x1+ 3x2
s.a.
x1 -2…….…... (1)
2x1- 2x2 4...... (2)
x1x2 0
26) Maximize Z = 5x1- x2
s.a.
2x1+ x2 =6 …….…...(1)
x1+ x2 4 …….…... (2)
x1+ 2x2 5.........(3)
x1x2 0
Degeneration Case in Linear Programming
Number of Existing Variables in the Solution
DEGENERATION
27) Maximize Z = 6x1+ 4x2
s.a.
2x1+ x2 1...... (1)
6x1+ 8x2 3...... (2)
x1x2 0
Degeneration Case in Linear Programming
Number of Existing Variables in the Solution
DEGENERATION
28) Maximize Z = x1+ x2+ 2x3
s.a.
2x1+ x2+ 4x3 50 …...(1)
4x1+ 2x2+ x3 30 ....... (2)
x1+ 3x2+ 3x3 60 …….... (3)
x1,x2,x3 0
Degeneration Case in Linear Programming
Number of Existing Variables in the Solution
DEGENERATION
29) Maximize Z = 6x1+ 7x2+ 6x3
s.a.
2x1+ x2+ 2x3 20....…... (1)
x1+ 2x2+ 3x3 20...
2x1+ 2x2+ x3 20…….... (3)
x1x2,x3 0
30) Maximize Z = x1+ x2+ 2x3
s.a.
2x1+ x2+ 4x3 50
4x1+ 2x2+ x3 30 ....... (2)
x1+ 3x2+ 3x3 60 ...... (3)
x1,x2,x3 0