13.
14.
15. (A) The basic feasible solution is: x1 = 0, x2 = 2, s1 = 0, s2 = 5, P = 12. Additional pivoting is
required because the last row contains a negative indicator.
6-82 CHAPTER 6: SIMPLEX METHOD
16. The matrices corresponding to the given problem and the dual problem are:
1 3 15
125
T
17. Introduce the slack variables x1 and x2 to obtain the initial system:
18. The first simplex tableau for the dual problem, Problem 16, is:
19. Using the simplex method, we have:
21. Maximize P = 3x1 + 4x2
Subject to: 2x1 + 4x2 ≤ 24
3x1 + 3x2 ≤ 21
CHAPTER 6 REVIEW 6-83
The simplex tableau for this problem is:
22. Minimize C = 3x1 + 8x2
Subject to: x1 + x2 ≥ 10
The matrices corresponding to the given problem and the dual problem are:
1110
38 1
10 15 3 1
6-84 CHAPTER 6: SIMPLEX METHOD
23. Introduce the slack variables x1 and x2 to obtain the initial system:
y1 + y2 + x1 = 3
24. Introduce slack variables s1 and s2 to obtain the equivalent form:
x1 – x2 – 2x3 + s1 = 3
The simplex tableau for this problem is:
25. Introduce slack variables s1 and s2 to obtain the equivalent form:
x1 – x2 – 2x3 + s1 = 3
CHAPTER 6 REVIEW 6-85
The simplex tableau for this problem is:
26. The equation needed is 2x1 + x2 + 3x3 + s1 = 12.
27. 2 pivot operations
1231
xxxsP
2RR, 5R1 + R2R2
12 31
1
131
106
222
xx xsP
x
28. (A) We introduce a surplus variable s1 and an artificial variable a1 to convert the first inequality (≥)
into an equation; we introduce a slack variable s2 to convert the second inequality (≤) into an
equation.
x
1
x
2
x
3
s
1
P
= 10
x
1 + 7
x
2 + 8
x
3
0 0 0 12 0
0 0 4 0 32
6-86 CHAPTER 6: SIMPLEX METHOD
The modified problem is: Maximize P = x1 + 3x2 – Ma1
(B) The preliminary simplex tableau is:
CHAPTER 6 REVIEW 6-87
29. (A) We introduce a surplus variable s1 and an artificial variable a1 to convert the first inequality (≥)
into an equation; we introduce a slack variable s2 to convert the second inequality (≤) into an
equation.
The modified problem is: Maximize P = x1 + x2 – Ma1
(B) The preliminary simplex tableau is:
6-88 CHAPTER 6: SIMPLEX METHOD
(C)
30. Multiply the second inequality by –1 to obtain a positive number on the right-hand side. This yields the
problem:
Maximize P = 2x1 + 3x2 + x3
Subject to: x1 – 3x2 + x3 ≤ 7
31. The basic simplex method with slack variables solves standard maximization problems involving ≤
32. The dual method solves minimization problems with positive coefficients in the
33. The big M method solves any linear programming problem. (6-4)
CHAPTER 6 REVIEW 6-89
34. Introduce slack variables s1, s2, s3, and s4 to obtain:
Maximize P = 2x1 + 3x2
Subject to: x1 + 2x2 + s1 = 22
This system can be written in the initial form:
x1 + 2x2 + s1 = 22
The simplex tableau for this problem is:
6-90 CHAPTER 6: SIMPLEX METHOD
Optimal solution:
35. Multiply the first constraint inequality by –1 to transform it into a ≥ inequality. Now the problem is:
Minimize C = 3x1 + 2x2
Subject to: –2x1 – x2 ≥ –20
2x1 + x2 ≥ 9
The matrices corresponding to this problem and its dual are respectively:
2120
2213
CHAPTER 6 REVIEW 6-91
Thus, the dual problem is: Maximize P = –20y1 + 9y2 + 6y3
We introduce slack variables x1 and x2 to obtain the initial system for the dual problem:
–2
y1 + 2y2 + y3 + x1 = 3
The simplex tableau for this problem is:
36. First convert the problem to a maximization problem by seeking the maximum of P = –C = –3x1 – 2x2.
Next, introduce a slack variable s1 into the first inequality to convert it into an equation; introduce surplus
variables s2 and s3 and artificial variables a1 and a2 into the second and third inequalities to convert them
6-92 CHAPTER 6: SIMPLEX METHOD
The preliminary simplex tableau is: