Chapter 19 – Linear Programming
19–89
e. Determine values for new x2 row:
0
1
–0.3
0.1
0.3
–0.1
1.8
f. Determine new values for row Z:
Cost
x1
x2
s1
s2
a1
a2
Quantity
10
10(0)
10(1)
10(–0.3)
10(0.1)
10(0.3)
10(–0.1)
10(1.8)
12
12(1)
12(0)
12(0.2)
12(–0.4)
12(–0.2)
12(0.4)
12(0.8)
12
10
–0.6
–3.8
0.6
3.8
27.6
g. Determine values for the C – Z row:
x1
x2
s1
s2
a1
a2
C
12
10
0
0
999
999
Z
12
10
–0.6
–3.8
0.6
3.8
C – Z
0
0
0.6
3.8
998.4
995.2
h. Set up the next tableau. Since no C – Z values are negative, the solution is optimal. Hence,
x1 = 0.8, x2 = 1.8, and minimum cost is 27.60.
C
12
10
0
0
999
999
Variables
in solution
x1
x2
s1
s2
a1
a2
Quantity
10
x2
0
1
–0.3
0.1
0.3
–0.1
1.8
12
x1
1
0
0.2
–0.4
–0.2
0.4
0.8
Z
12
10
–0.6
–3.8
0.6
3.8
27.6
C – Z
0
0
0.6
3.8
998.4
995.2
Chapter 19 – Linear Programming
19–90
Problems for the enrichment module (simplex)
1. Given this information:
Maximize
Z = 10.50x + 11.75y + 10.80z
Subject to
Cutting
5x + 12y + 8z 1,400 minutes
Stapling
7x + 9y + 9z 1,250 minutes
Wrapping
4x + 3y + 6z 720 minutes
x, y, z 0
2. Use the simplex method to solve these problems:
a.
Minimize
Z = 21x1 + 18x2
Subject to
(1) 5x1 + 10x2 100
(2) 2x1 + 1x2 10
x1, x2 0
b.
Minimize
Z = 2x + 5y + 3z
Subject to
(1) 16x + 10y + 18z 340
(2) 11x + 12y + 13z 300
(3) 2x + 6y + 5z 120
x, y, z 0
3. Use the simplex method to solve the following problem.
Minimize Z = 3x1 + 4x2 + 8x3
4. Use the simplex method to solve the following problem.
Maximize Z = 8x1 + 2x2
Subject to 4x1 + 5x2 20
Chapter 19 – Linear Programming
19–91
Solutions-Enrichment Module (SIMPLEX)
1.
C
10.5
11.75
10.80
0
0
0
Var
x
y
z
S1
S2
S3
bi
ratio
0
S1
5
12
8
1
0
0
1,400
116.67
0
S2
7
9
9
0
1
0
1,250
138.89
4
S3
4
3
6
0
0
1
720
240
Z
0
0
0
0
0
0
0
C–Z
10.5
11.75
10.80
0
0
0
C
Var
x
y
z
S1
S2
S3
bi
ratio
11.45
y
5/12
1
2/3
1/12
0
0
1,400/12
280
0
S2
13/4
0
3
–3/4
1
0
200
61.54
0
S3
11/4
0
4
–1/4
0
1
370
134.54
Z
4.896
11.75
7.833
0.979
0
0
1,370.83
C–Z
5.604
0
2.967
–0.979
0
0
C
Var
x
y
z
S1
S2
S3
bi
ratio
11.75
y
0
1
11/39
7/39
–5/39
0
91.026
507.1
10.5
x
1
0
12/13
–3/13
4/13
0
61.54
0
S3
0
0
19/13
5/13
–11/13
1
2610/13
522
Z
10.5
11.75
13.01
–0.314
1.724
0
1,715.73
C–Z
0
0
–2.206
0.314
–1.724
0
C
Var
x
y
z
S1
S2
S3
bi
0
S1
0
39/7
11/7
1
–5/7
0
507.14
10.5
x
1
9/7
117/91
0
–1/7
0
178.57
0
S3
0
–15/7
78/91
0
–4/7
1
5.72
Z
10.5
13.5
13.5
0
1.5
0
1,874.99
C–Z
0
–1.75
–2.7
0
–1.5
0
Optimal solution is x = 178.57, y = 0, z = 0, and optimal solution = 1,874.99
Chapter 19 – Linear Programming
19–92
Solutions (continued)
2.
a.
Minimize Z =
21x1
+ 18x2
s.t.
5x1
+ 10x2
+ A1 – S1
= 100
2x1
+ 1x2
+ A2 – S2
= 10
C
21
18
M
0
M
0
I.
C
Var
x1
x2
A1
S1
A2
S2
bi
ratio
M
A1
5
10
1
–1
0
0
100
10
M
A2
2
1
0
0
1
–1
10
10
Z
7M
11M
M
–M
M
–M
110M
M
C–Z
[21–7M]
[18–11M]
–0
M
–0
M
C
21
18
M
0
M
0
II.
C
Var
x1
x2
A1
S1
A2
S2
bi
ratio
18
x2
0.5
1
0.1
–0.1
0
0
10
20
M
A2
1.5
0
–0.1
0.1
1
–1
0
0
Z
[1.5M+9]
18
[1.8–0.1M]
[0.1M–1.8]
M
–M
180
C–Z
[12–1.5M]
0
[1.1M–1.8]
[1.8–.1M]
–0
M
C
21
18
0
0
III.
C
Var
x1
x2
S1
S2
bi
18
x2
0
1
–0.1333
0.333
10
21
x1
1
0
+0.0667
–0.667
0
Z
21
18
–0.99999
–8.000
180
C–Z
0
0
0.99999
8.000
The optimal solution: x1 = 0; x2 = 10; Z = 180
Chapter 19 – Linear Programming
19–93
Solutions (continued)
2.
b.
I.
C
2
5
3
M
0
M
0
M
0
Var
x
y
z
A1
S1
A2
S2
A3
S3
bi
M
A1
16
10
18
1
–1
0
0
0
0
340
M
A2
11
12
13
0
0
1
–1
0
0
300
M
A3
2
6
5
0
0
0
0
+1
–1
120
Z
29M
28M
36M
M
–M
M
–M
M
–M
760M
C–Z
[–29M+2]
[–28M+5]
[–36M+3]
0
M
0
M
0
M
II.
C
Var
x
y
z
A1
S1
A2
S2
A3
S3
bi
3
Z
.8889
.5556
1
.0556
–.0556
0
0
0
0
18.89
M
A2
–.5556
4.778
0
–.722
.722
1
–1
0
0
54.44
M
A3
–2.444
3.222*
0
–.2778
.2778
0
0
1
–1
25.56
Z
[–3M+2.7]
[8M+1.7]
3
[–M+.17]
[M–.17]
M
–M
M
–M
80M+56.7
C–Z
[+3M+.7]
[–8M+3.3]
0
[2M–47]
[–M+.17]
0
M
0
M
III.
C
Var
x
y
z
S1
A2
S2
S3
bi
3
z
1.31
0
1
–.1034
0
0
.1724
14.48
M
A2
3.069*
0
0
.3103
1
–1
1.483
16.55
5
Y
–0.7586
1
0
0.08621
0
0
–0.3103
7.931
Z
[3M+.138]
5
3
[.3M+.121]
–M
[1.5M–1.03]
[16.55M+83.1]
C–Z
[–3.1M+1.86]
0
0
[–.3M–.121]
0
M
[–1.5M+1.03]
IV.
C
Var
x
y
z
S1
S2
S3
bi
3
z
0
0
1
–0.236
.427
–0.4607
7.416
2
x
1
0
0
.1011
–.3258
.4831
5.393
5
y
0
1
0
.1629
–.2472
.05618
12.02
Z
2
5
3
0.309
–0.6067
–0.1348
93.15
C–Z
0
0
0
–0.309
0.6067
0.1348
V.
C
Var
x
y
z
S1
S2
S3
bi
3
z
2.333
0
1
0
–0.3333
.6667
20
0
S1
9.889
0
0
1
–3.222
4.778
53.33
5
y
–1.611
1
0
0
.2778*
–0.7222
3.333
Z
–1.06
5
3
0
+0.3889
–1.6111
76.67
C–Z
3.056
0
0
0
–0.3889
1.6111
Chapter 19 – Linear Programming
19–94
Solutions (continued)
VI.
C
Var
x
y
z
S1
S2
S3
bi
3
z
.4
1.2
1
0
0
–0.200
24
0
S1
–8.8
11.6
0
1
0
–3.6
92
0
S2
–5.8
3.6
0
0
1
–2.6
23
Z
1.2
3.6
3
0
0
–0.6
72
C–Z
.8
1.4
0
0
0
.6
Optimal solution is: x = 0; y = 0; z = 24 and Z = 72.0
3.
C
3
4
8
0
0
M
M
Var
x1
x2
x3
S1
S2
A1
A2
bi
bi/aij
M
A1
2
1
0
–1
0
1
0
6
6/2 = 3
M
A2
0
1
2
0
–1
0
1
4
–
Zj
2M
2M
2M
–M
–M
M
M
10M
Cj–Zj
3–2M
4–2M
8–2M
M
M
0
0
C
3
4
8
0
0
Var
x1
x2
x3
S1
S2
bi
bi/aij
3
x1
1
½
0
–½
0
3
3 ½ = 6
M
A2
0
1
2
0
–1
4
4 1 = 4
Zj
3
M–3/2
2M
–3/2
–M
4M+9
Cj–Zj
0
5/2 –M
8–2M
3/2
M
C
3
4
8
0
0
Var
x1
x2
x3
S1
S2
bi
bi/aij
3
x1
1
½
0
–½
0
3
3 ½ = 6
8
x3
0
½
1
0
–½
2
2 ½ = 4
Zj
3
11/2
8
–3/2
–4
25
Cj–Zj
0
–3/2
0
3/2
4
C
3
4
8
0
0
Var
x1
x2
x3
S1
S2
bi
3
x1
1
0
–1
–½
½
1
4
x2
0
1
2
0
–1
4
Zj
3
4
5
–3/2
–5/2
19
Cj–Zj
0
0
3
3/2
5/2
The optimal solution is: x1 = 1; x2 = 4; x3 = 0 and Z = 19.
Chapter 19 – Linear Programming
19–95
Solutions (continued)
4.
Cj
8
2
0
0
Var
x1
x2
S1
S2
bi
0
S1
4
5
1
0
20
0
S2
2
6
0
1
18
Zj
0
0
0
0
0
Cj–Zj
8
2
0
0
Cj
Var
x1
x2
S1
S2
bi
8
x1
1
5/4
¼
0
5
0
S2
0
7/2
–1/2
1
8
Zj
8
10
2
0
40
Cj–Zj
0
–8
–2
0