Chapter 19 – Linear Programming
Material
100
90
80
70
60
50
B
Chapter 19 – Linear Programming
(1) As we slide the profit line away from the origin, we reach the optimum point indicated
in the graph above (at the intersection of the Material and Machinery constraints). The
optimal values of the decision variables are A = 24, B = 20, and the optimal objective
function value = Z = 204. The work for these solutions is shown below:
Simultaneous solution:
B = 20
Step 2:
Substitute B = 20 in either constraint:
20A + 6B = 600
Step 3:
Substitute the values of A and B in the objective function:
Z = 6A + 3B
Z = 6(24) + 3(20) = 204
(2) All constraints have ≤ in them. The Material and Machinery constraints are binding
and have zero slack. The Labor constraint has slack of 120 (1,200 – 1,080) as shown
below:
20A + 30B ≤ 1,200
Chapter 19 – Linear Programming
19–13
2. a. Graph the constraints and the objective function:
Potassium constraint:
5S + 8T ≥ 200
Replace the inequality sign with an equal sign:
5S + 8T = 200
Set S = 0 and solve for T:
5(0) + 8T = 200
8T = 200
Carbohydrate constraint:
15S + 6T ≥ 240
Replace the inequality sign with an equal sign:
15S + 6T = 240
Set S = 0 and solve for T:
15(0) + 6T = 240
Chapter 19 – Linear Programming
19–14
Protein constraint:
4S + 12T ≥ 180
Replace the inequality sign with an equal sign:
4S + 12T = 180
Set S = 0 and solve for T:
T constraint:
T ≥ 10
Replace the inequality sign with an equal sign:
T = 10
Objective function:
Let 1.80S + 2.20T = 99.
Set S = 0 and solve for T:
1.80(0) + 2.20T = 99
2.20T = 99
T = 45
The graph and the feasible solution space (shaded with lines) are shown below:
Chapter 19 – Linear Programming
19–15
0
5
10
15
20
25
30
35
40
45
50
0 5 10 15 20 25 30 35 40 45 50
T
S
Opt.
Chapter 19 – Linear Programming
19–16
(1) As we slide the cost line toward the origin, we reach the optimum point indicated in
the graph above (at the intersection of the Potassium and Carbohydrate constraints).
The optimal values of the decision variables are S = 8, T = 20, and the optimal
Step 1:
Multiply the Potassium constraint by 3 and subtract the Carbohydrate constraint from
the result:
15S + 24T = 600
5S + 8T = 200
5S + 8(20) = 200
5S + 160 = 200
5S = 40
S = 8
(3) The Protein and T constraints have surplus.
Protein constraint has surplus of 92 (272 – 180) as shown below:
4S + 12T ≥ 180
Plug in the values of S & T:
4(8) + 12(20) ≥ 180
(4) The Protein constraint is redundant.
Chapter 19 – Linear Programming
19–17
b. Graph the constraints and the objective function:
D constraint:
4(0) + 2x2 = 20
2x2 = 20
x2 = 10
One point on the line is (0, 10).
E constraint:
2x1 + 6x2 ≥ 18
Replace the inequality sign with an equal sign:
2x1 + 6x2 = 18
Set x1 = 0 and solve for x2:
2x1 = 18
x1 = 9
A second point on the line is (9, 0).
Chapter 19 – Linear Programming
19–18
F constraint:
1x1 + 2x2 ≤ 12
Replace the inequality sign with an equal sign:
1x1 + 2x2 = 12
Set x1 = 0 and solve for x2:
1(0) + 2x2 = 12
2x2 = 12
x2 = 6
Objective function:
Let 2x1 + 3x2 = 24.
Set x1 = 0 and solve for x2:
2(0) + 3x2 = 24
3x2 = 24
x1 = 12
A second point on the line is (12, 0).
The graph and the feasible solution space (shaded) are shown below:
Chapter 19 – Linear Programming
E
F
D
Optimum
x1
0 1 2 3 4 5 6 7 8 9 10 11 12
12
11
10
9
8
7
6
5
4
3
2
1
0
x2
Cost
Chapter 19 – Linear Programming
(1) As we slide the cost line toward the origin, we reach the optimum point indicated in
E: 2x1 + 6x2 = 18
Step 1:
Multiply the D constraint by 3 and subtract the E constraint from the result:
12x1 + 6x2 = 60
–(2x1 + 6x2 = 18)
4(4.2) + 2x2 = 20
16.8 + 2x2 = 20
2x2 = 3.2
x2 = 1.6
7.4 ≤ 12
(3) No, there is no surplus. The D & E constraints have ≥ in them, but both are binding.