EXERCISE 6-3 6-41
The simplex tableau for this problem is:
1
y1
x
2
x
3
x
P
10
1
10
1 000
36. The original problem must have two variables and any number of constraints.
40. Yes. No modifications are necessary.
42. (A) The matrices corresponding to the given problem and the dual problem are:
A =
318
14 4
and AT =
31 2
14 9
respectively.
44. (A) An equivalent minimization problem is: Minimize C = 25x1 + 30x2 + 50x3
(B) The matrices corresponding to this problem and the dual problem are:
1625
25 30 50 1 12 20 1
6-42 CHAPTER 6: SIMPLEX METHOD
Thus, the dual problem is: Maximize P = –12y1 – 20y2
Subject to: y1 – 6y2 ≤ 25
46. The dual problem is:
Maximize P = 6y1 + 4y2 + 8y3
Subject to: y1 + y2 + 2y3 ≤ 6
Introducing slack variables x1, x2, x3, we get the initial system.
–0y1 + 0y2 + 2y3 + x1 + x2 + x3 + P = 6
Simplex tableau:
y1y2y3 x1
x2 x3 P
1
1 1 21000 6
x
6/2 3
11
2
y1y2y3x1 x2 x3 P
1/21/2 11/2000 3
6-44 CHAPTER 6: SIMPLEX METHOD
–y1 + 00y2 + 00y3 +00 y4 + x1 + x2 + x3 + x4 + P = 4
–y1 + 00y2 +00 y3 + 00y4 + x1 + x2 + x3 + x4 + P = 7
–0y1 00 –y2 + 00y3 +00 y4 + x1 + x2 + x3 + x4 + P = 5
–0y1 00 –y2 + 00y3 + 00y4 + x1 + x2 + x3 + x4 + P = 6
3
4
0 1 0 1000106
1225 20 15000010
P
x
13 3
(1) ,
R
RR 55
1
20
R
RR
y1
y2
y3y4x1
x2 x3 x4 P
3
101 0 100004
y
2
42
(1) ,
R
RR 55
4
15
R
RR
y1y2
y3 y4 x1
x2 x3
x4
P
3
1 0 10 100 00 4
y
EXERCISE 6-3 6-45
31 1
,
R
RR 32 2
,
R
RR 55
3
8
R
RR
y1 y2 y3
y4 x1
x2 x3 x4 P
3
2
011000100 5
0 000 111 10 2
y
x
50. Let x1 = the number of hours the West Summit mine is operated,
x2 = the number of hours the North Ridge mine is operated.
The mathematical model for this problem is:
Minimize C = 400x1 + 600x2
Subject to: 2x1 + 2x2 ≥ 100
The matrices corresponding to the given problem and the dual problem are:
A =
22100
3160
and AT =
2 3 1 400
2 1 2 600
We introduce slack variables x1 and x2 to obtain the initial system:
2y1 + 3y2 + y3 + x1 = 400
6-46 CHAPTER 6: SIMPLEX METHOD
The simplex tableau for this problem is:
51
001 0100
22
52. In this case, the matrices for the given problem and the dual problem are:
22100
2 3 1 300
EXERCISE 6-3 6-47
The simplex tableau for this problem is:
311
100150
6-48 CHAPTER 6: SIMPLEX METHOD
54. In this case, the simplex tableau is:
56. Let x1 = the number of cubic yards of mix A,
x2 = the number of cubic yards of mix B,
x3 = the number of cubic yards of mix C.
EXERCISE 6-3 6-49
Copyright © 2019 Pearson Education, Inc.
A =
21248
11232
and AT =
21230
11336
y1, y2, y3 ≥ 0
We introduce slack variables x1, x2, and x3 to obtain the initial system:
2y1 + y2 + 2y3 + x1 = 30
The simplex tableau for this problem is:
11
1 1 00015
22
~
11
1 1 000 15
22
11
0210021
22
2
2
6-50 CHAPTER 6: SIMPLEX METHOD
1
2.5 R2 → R2
58. Let x1 = the number of students bused from North Division to Central,
x2 = the number of students bused from North Division to Washington,
x3 = the number of students bused from South Division to Central,
EXERCISE 6-3 6-51
We multiply the last two problem constraints by –1 so that all the constraints are of the ≥ type. The model
becomes:
Minimize C = 5x1 + 7x2 + 3x3 + 4x4
Subject to: x1 + x2 ≥ 300
The matrices for this problem and the dual problem are:
1100300
0011500
10 1 05
10 0 17
The dual problem is: Maximize P = 300y1 + 500y2 – 400y3 – 500y4
Subject to: y1 – y3 ≤ 5
y1–y4 ≤ 7
We introduce slack variables x1, x2, x3, and x4 to obtain the initial system:
y1–y3+x1 = 5
y1–y4+x2 = 7
6-52 CHAPTER 6: SIMPLEX METHOD
The simplex tableau for this problem is:
EXERCISE 6-4
2. (A) We introduce a slack variable s1 to convert the first inequality (≤) into an equation, and we
use a surplus variable s2 and an artificial variable a1 to convert the second inequality (≥)
into an equation.
The modified problem is: Maximize P = 3x1 + 7x2 – Ma1
Subject to: 2x1 + x2 + s1 = 16
EXERCISE 6-4 6-53
(B) The preliminary simplex tableau for the modified problem is:
x1x2s1s2a1P
21100016
110–1106
–M – 3 –M – 7 0 M01–6M
~
110–1106
–M – 3 –M – 7 0 M01–6M
(C) We use the simplex method to solve the modified problem.
x1x2 s1s2 a1 P
1
16 16
1
21100016
s
11 0 14 0 1 112
MM
Thus, the optimal solution of the modified problem is: max P = 112 at x1 = 0, x2 = 16,
6-54 CHAPTER 6: SIMPLEX METHOD
Copyright © 2019 Pearson Education, Inc.
(D) The optimal solution of the original problem is: max P = 112 at x1 = 0, x2 = 16.
4. (A) We introduce the slack variable s1 and the artificial variable a1 to obtain the modified problem:
Maximize P = 4x1 + 3x2 – Ma1
(B) The preliminary simplex tableau for the modified problem is:
x1x2s1a1P
1310024
–M – 4 –M – 3 0 0 1 -12M
Thus, the initial simplex tableau is:
s1
x1x2s1a1P
1 3 10024
(C) We use the simplex method to solve the modified problem.
EXERCISE 6-4 6-55
Copyright © 2019 Pearson Education, Inc.
(D) The optimal solution of the original problem is: max P = 48 at x1 = 12, x2 = 0.
6. (A) We introduce slack, surplus, and artificial variables to obtain the modified problem:
Maximize P = 3x1 + 4x2 – Ma1
(B) The preliminary simplex tableau for the modified problem is:
x1x2s1s2a1P
1–210002
1 –2 10002
–M – 3 –M – 4 0 M01–5M
Thus, the initial simplex tableau is:
x1x2s1s2a1P
1 –2 10002
s1
6-56 CHAPTER 6: SIMPLEX METHOD
(C) We use the simplex method to solve the modified problem:
(D) No optimal solution exists.
8. (A) We introduce slack, surplus, and artificial variables to obtain the modified problem:
Maximize P = 4x1 + 6x2 – Ma1
(B) The preliminary simplex tableau for the modified problem is:
x1x2s1s2a1P
1 110002
s1
1 1 1000 2
-3M – 4 -5M – 6 0 M01–15
M
EXERCISE 6-4 6-57
Thus, the initial simplex tableau is:
x1x2s1s2a1P
1 1 1000 2
s1
(C) Applying the simplex method to the initial tableau, we have:
22
1
1110002
15
x1
x2s1s2 a1
P
2
11 1 000 2
x
10. To minimize P = –4x1 + 16x2, we maximize T = –P = 4x1 – 16x2. Introducing slack, surplus, and
artificial variables, we obtain the modified problem:
Maximize T = 4x1 – 16x2 – Ma1
6-58 CHAPTER 6: SIMPLEX METHOD
EXERCISE 6-4 6-59
Subject to: 3x1 + x2 + s1 = 28
