Page 255, Problem 4
Solution by Mr. Eric Malone
The original statement of the problem can be summarized in the following table:
Ring / Rubies / Sapphires / Labor / Sale $ / Min.Type 1 / 2 / 3 / 1 / $400 / 20
Type 2 / 3 / 2 / 2 / $500 / 25
Max. / 100 / 120 / 70 / - / -
Add'l $ / $100 / - / - / - / -
The information given in the table is converted to the following LP formulation:
x1: # Type 1 Rings produced
x2: # Type 2 Rings produced
R: # additional Rubies purchased
Max z = 400x1 + 500x2 – 100R
S.T.
2x1 + 3x2 – R £ 100 (Rubies)
3x1 + 2x2 £ 120 (Sapphires)
x1 + 2x2 £ 70 (Labor)
x1 ³ 20 (Type 1 Min.)
x2 ³ 25 (Type 2 Min.)
x1, x2, R ³ 0 (Sign Restriction)
The solution to this LP problem is presented in the following WinQSB output table:
Combined Report for Page 226, #4 OriginalDecision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 300 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 700
3 / R / 15 / -100 / -1,500.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 19,000.00
Left Hand / Right Hand / Slack / Shadow / Allowable / Allowable
Constraint / Side / Direction / Side / or Surplus / Price / Min. RHS / Max. RHS
1 / Rubies / 100 / <= / 100 / 0 / 100 / -M / 115
2 / Sapphires / 110 / <= / 120 / 10 / 0 / 110 / M
3 / Labor / 70 / <= / 70 / 0 / 200 / 70 / 73.3333
4 / Type 1 min. / 20 / >= / 20 / 0 / 0 / -M / 20
5 / Type 2 min. / 25 / >= / 25 / 0 / -200 / 22.5 / 25
So, from the results, we can see that Zales should produce 20 Type 1 Rings, 25 Type 2 Rings, and purchase 15 additional rubies for a total profit of $19,000.
a) Suppose that each ruby now costs $190. Would Zales still purchase rubies? What would be the new optimal solution to this problem?
From the output table obtained through the use of the WinQSB software, it is clearly evident that the cost of $190 for each additional ruby falls within the range for the objective function coefficients for the rubies. In fact the range includes all costs from $0 to $200. Therefore, although the value of the optimal solution (max. profit) will change, the optimal mix of variables (amounts of Type 1 and 2 rings to produce) will not change. We can then solve for the new optimal solution as follows:
Original optimal z-value: z = 400(20) + 500(25) – 100(15) = $19,000
New optimal z-value: z’ = 400(20) + 500(25) – 190(15) = $17,650 or
z’ = 19,000 + [(-190) – (-100)]15 = $17,650
b) Suppose that Zales were only required to produce a minimum of 23 Type 2 rings. What would be the new optimal solution?
Once again from the output obtained from WinQSB, we can see that the value of 23 required Type 2 rings falls within the RHS range in which the current basis remains optimal. Therefore, we can calculate the new optimal z-value as follows:
New optimal z-value: z’ = z + D(RHS)*(Shadow Price)
z’ = 19,000 + (23-25)(-200) = $19,400
Therefore, we conclude that by the reduction in the requirement of Type 2 ring production, Zales profit has increased by $400.
c) What is the most that Zales would be willing to pay for another hour of jeweler’s labor?
From the WinQSB output, we see that the third constraint, which refers to the maximum availability of jeweler’s labor, has a slack value of zero, meaning that every available hour of labor (i.e. 70 hours) has been utilized by Zales. Therefore, if Zales were to choose to hire the jeweler for an additional hour, this would be the equivalent of increasing the RHS for constraint #3 to 71. As we see from the allowable RHS range, 71 hours falls within this range (70 – 73.33). As in part (b), we can calculate the new optimal z-value based on this change. The amount by which the optimal solution is increased is the maximum amount that Zales should be willing to pay the jeweler for the additional hour. However, the answer to this question can be found much quicker. Because the proposed increase of one hour falls within the allowable RHS range, we can merely look at the value of the shadow price. The meaning of this value is the amount by which the profit would improve if the RHS for that constraint were increased by one unit. In this case, that value is $200. Therefore, we conclude that Zales should be willing to pay, at most, $200 for an additional hour of jeweler’s labor.
d) What is the most that Zales would be willing to pay for another sapphire?
From the WinQSB output, we see that the second constraint, which refers to the maximum availability of sapphires, has a slack value of 10 sapphires, meaning that not every sapphire (i.e. 120) has been utilized by Zales. This makes sense because the optimal solution requires
(20 Type 1)*(3 sapphires/Type 1) + (25 Type 2)*(2 sapphires/Type 2)
= 60 +50 = 110 sapphires
So we see, that not all of the sapphires available to Zales have been used. By definition, we know that a constraint that has a nonnegative slack or excess value automatically has a shadow price of 0. This means that for Zales to purchase another sapphire would mean to reduce profits. Therefore, the most Zales should pay for another sapphire is $0.
e) Draw a graph of the optimal z-value as a function of the cost of extra ruby ($100 now) by solving each problem repeatedly to find each line segment for the plot.
To obtain this graph, we must first solve for the optimal z-value for different costs of extra rubies. The following tables show the resulting objective function values (in blue) for different costs of additional rubies. We will use the following values for the extra ruby cost: $0, $100, $115, $150, and $200.
Combined Report for Page 226, #4 R = 0Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 250 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 800
3 / R / 15 / 0 / 0.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 20,500.00 / (Note: / Alternate / Solution / Exists!!)
Combined Report for Page 226, #4 R=50
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 275 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 750
3 / R / 15 / -50 / -750.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 19,750.00
Combined Report for Page 226, #4 R=100
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 300 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 700
3 / R / 15 / -100 / -1,500.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 19,000.00
Combined Report for Page 226, #4 R=115
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 307.5 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 685
3 / R / 15 / -115 / -1,725.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 18,775.00
Combined Report for Page 226, #4 R=200
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / -M / 400
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 600
3 / R / 15 / -200 / -3,000.00 / 0 / basic / -M / -200
Objective / Function / (Max.) = / 17,500.00 / (Note: / Alternate / Solution / Exists!!)
The above graph plots values of the objective function for various values of the extra cost for rubies according to the tables above. From the graph, it is evident that as the cost of rubies increases gradually from $0 (no cost), the objective function value increases indefinitely.
f) Draw a graph of the optimal z-value as a function of the available hours of labor by solving each problem repeatedly to find each line segment for the plot.
To obtain this graph, we must first solve for the optimal z-value for different levels of available labor hours. The following tables show the resulting objective function values (in blue) for different labor hour levels. We will use the following values for the labor availabilities: 0, 50, 70, 75, 100, 125
Combined Report for Page 226, #4 Labor=70Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / 300 / M
2 / X2 / 25 / 500 / 12,500.00 / 0 / basic / -M / 700
3 / R / 15 / -100 / -1,500.00 / 0 / basic / -200 / 0
Objective / Function / (Max.) = / 19,000.00
Left Hand / Right Hand / Slack / Shadow / Allowable / Allowable
Constraint / Side / Direction / Side / or Surplus / Price / Min. RHS / Max. RHS
1 / C1 / 100 / <= / 100 / 0 / 100 / -M / 115
2 / C2 / 110 / <= / 120 / 10 / 0 / 110 / M
3 / C3 / 70 / <= / 70 / 0 / 200 / 70 / 73.3333
4 / C4 / 20 / >= / 20 / 0 / 0 / -M / 20
5 / C5 / 25 / >= / 25 / 0 / -200 / 22.5 / 25
Combined Report for Page 226, #4 Labor=75
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 22.5 / 400 / 9,000.00 / 0 / basic / 300 / 500
2 / X2 / 26.25 / 500 / 13,125.00 / 0 / basic / 433.3333 / 700
3 / R / 23.75 / -100 / -2,375.00 / 0 / basic / -140 / 0
Objective / Function / (Max.) = / 19,750.00
Left Hand / Right Hand / Slack / Shadow / Allowable / Allowable
Constraint / Side / Direction / Side / or Surplus / Price / Min. RHS / Max. RHS
1 / C1 / 100 / <= / 100 / 0 / 100 / -M / 123.75
2 / C2 / 120 / <= / 120 / 0 / 50 / 115 / 125
3 / C3 / 75 / <= / 75 / 0 / 50 / 73.3333 / 80
4 / C4 / 22.5 / >= / 20 / 2.5 / 0 / -M / 22.5
5 / C5 / 26.25 / >= / 25 / 1.25 / 0 / -M / 26.25
Combined Report for Page 226, #4 Labor=80
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / -M / 500
2 / X2 / 30 / 500 / 15,000.00 / 0 / basic / 433.3333 / M
3 / R / 30 / -100 / -3,000.00 / 0 / basic / -140 / 0
Objective / Function / (Max.) = / 20,000.00
Left Hand / Right Hand / Slack / Shadow / Allowable / Allowable
Constraint / Side / Direction / Side / or Surplus / Price / Min. RHS / Max. RHS
1 / C1 / 100 / <= / 100 / 0 / 100 / -M / 130
2 / C2 / 120 / <= / 120 / 0 / 100 / 110 / 120
3 / C3 / 80 / <= / 80 / 0 / 0 / 80 / M
4 / C4 / 20 / >= / 20 / 0 / -100 / 20 / 23.3333
5 / C5 / 30 / >= / 25 / 5 / 0 / -M / 30
Combined Report for Page 226, #4 Labor=100
Decision / Solution / Unit Cost or / Total / Reduced / Basis / Allowable / Allowable
Variable / Value / Profit c(j) / Contribution / Cost / Status / Min. c(j) / Max. c(j)
1 / X1 / 20 / 400 / 8,000.00 / 0 / basic / -M / 500
2 / X2 / 30 / 500 / 15,000.00 / 0 / basic / 433.3333 / M
3 / R / 30 / -100 / -3,000.00 / 0 / basic / -140 / 0
Objective / Function / (Max.) = / 20,000.00
Left Hand / Right Hand / Slack / Shadow / Allowable / Allowable
Constraint / Side / Direction / Side / or Surplus / Price / Min. RHS / Max. RHS
1 / C1 / 100 / <= / 100 / 0 / 100 / -M / 130
2 / C2 / 120 / <= / 120 / 0 / 100 / 110 / 140
3 / C3 / 80 / <= / 100 / 20 / 0 / 80 / M
4 / C4 / 20 / >= / 20 / 0 / -100 / 10 / 23.3333
5 / C5 / 30 / >= / 25 / 5 / 0 / -M / 30
The above sensitivity graph plots values of the objective function for various values of the available labor according to the tables above. From the graph, it is evident that as the amount of available labor increases gradually from 70 hours, the objective function value increases. However, after the availability reaches 80 hours, the objective function levels at an optimal value of $20,000.
1