Linear Programming Modeling Examples

Linear Programming: Modeling Examples PROBLEM SUMMARY 1. “Product mix” example 32. Blend (maximization) 2. “Diet” example 33. Multiperiod borrowing (minimization) 3. “Investment” example 34. Multiperiod production scheduling (minimization) 4. “Marketing” example 5. “Transportation” example 35. Blend (maximization), sensitivity analysis 6. “Blend” example 36. Assignment (minimization), sensitivity analysis 7. Product mix (maximization) 37. Transportation (minimization) 8. Sensitivity analysis (4–7) 38. Scheduling (minimization) 9. Diet (minimization) 39. Production line scheduling (maximization) 10. Product mix (minimization) 40. Network flow (minimization) 11. Product mix (maximization) 41. College admissions (maximization) 12. Product mix (maximization) 42. Blend (maximization) 13. Product mix (maximization) 43. Trim loss (minimization) 14. Ingredients mix (minimization) 44. Multiperiod investment (maximization) 15. Transportation (maximization) 45. Multiperiod sales and inventory (maximization) 16. Product mix (maximization) 17. Ingredients mix (minimization) 46. Multiperiod production and inventory (minimization) 18. Crop distribution (maximization) 47. Employee assignment (maximization) 19. Monetary allocation (maximization) 48. Data envelopment analysis 20. Diet (minimization), sensitivity analysis 49. Data envelopment analysis 21. Transportation (maximization) 50. Network flow (maximization) 22. Transportation (minimization) 51. Multiperiod workforce planning (minimization) 23. Warehouse scheduling (minimization) 52. Integer solution (4–43) 24. School busing (minimization) 25. Sensitivity analysis (4–24) 53. Machine scheduling (maximization), sensitivity analysis 26. Ingredients mixture (minimization) 54. Cargo storage (maximization) 27. Interview scheduling (maximization) 55. Broadcast scheduling (maximization) 28. Investments mixture (maximization) 56. Product mix (maximization) 29. Insurance poly mix (maximization) 57. Product mix/advertising (maximization) 30. Product mix (maximization) 58. Scheduling (minimization) 31. Advertising mix (minimization), sensitivity analysis 59. Truck purchasing/leasing (minimization) 60. Multiperiod workforce planning (minimization) 2. 61. Multiperiod workforce (4–50) 62. Data envelopment analysis 63. Airline crew scheduling (maximization) With a minimum of 600 calories, the food items change to x3 = 4.622 cups of oatmeal and 1.378 cups of milk and Z = $0.683. A change of variables would be expected given that 600 calories is greater than the upper limit of the sensitivity range for calories. 64. Consultant project assignment (minimization) 65. College admissions (maximization) 66. Product flow/scheduling (minimization) Many different combinations of maximum servings of each of the 10 food items could be used. As an example limiting the four hot and cold cereals, x1, x2, x3 and x4 to four cups, eggs to three, bacon to three slices, oranges to two, milk to two cups, orange juice to four cups and wheat toast to four slices results in the following solution: PROBLEM SOLUTIONS 1. Since the profit values would change, the shadow prices would no longer be effective. Also, the sensitivity analysis provided in the computer output does not provide ranges for constraint parameter changes. Thus, the model would have to be resolved. x3 = 2 cups of oatmeal x4 = 1.464 cups of oat bran x5 = .065 eggs x8 = 1.033 cups of milk x10 = 4 slices of wheat toast Z = $0.828 The reformulated model would have unit costs increased by 10 percent. This same amount would be subtracted from unit profits. The individual processing times would be reduced by 10 percent. This would result in a new, lower solution of $43,310. Thus, the suggested alternative should not be implemented. Further limiting the servings of the four hot and cold cereals to two cups, x1 + x2 + x3 + x4 ≤ 2, results in the following solution: Probably not. The t-shirts are a variable cost and any additional t-shirts purchased by QuikScreen would likely reduce unit profit, which would change the current shadow price for blank t-shirts. The shadow price is effective only if the profit is based on costs that would be incurred without regard to the acquisition of additional resources. The new requirement is that, x3 = 2 cups of oatmeal x6 = .750 slices of bacon x8 = 2 cups of milk x9 = .115 cups of orange juice x10 = 4 slices of wheat toast Z = $0.925 3. x1 = x2 = x3 = x4 x1 = x2 x1 = x3 x1 = x4 No, the entire amount will not be invested in one alternative. The new solution is x1 = $22,363.636, x3 = $43,636.364, and x4 = $14,000. If x1 equals x2, x3 and x4 then x2, x3 and x4 must also equal each other. These constraints are changed to, The new solution is x1 = x2 = x3 =x4 = 112.5. It would have no effect; the entire $70,000 would be invested anyway. Since the upper limit of the sensitivity range for the investment amount is “unlimited,” an increase of $10,000 will not affect the shadow price, which is $0.074. Thus, the total increase in return will be $740 (i.e., $10,000 × .074 = $740). This can be achieved within the model by creating three additional constraints, x1 – x2 = 0 x1 – x3 = 0 x1 – x4 = 0 With a minimum of 500 calories, the three food items remain the same, however the amount of each and the total cost increases: x3 = 2.995 cups of oatmeal, x8 = 1.352 cups of milk, x10 = 1.005 slices of toast, and Z = $0.586. 4. The shadow price is 1.00, thus for every $1 increase in budget, up to the sensitivity range upper limit of $14,000, audience exposure will increase by 1.00. The total audience increase for a $20,000 budget increase is 20,000. This new requirement results in two new model constraints, 20,000x1 = 12,000x2 20,000x1 = 9,000x3 or, 20,000 – 12,000x2 = 0 20,000x1 – 9,000x3 = 0 The new solution is x1 = 3.068, x2 = 5.114, x3 = 6.818 and Z = 184,090. This results in approximately 61,362 exposures per type of advertising (with some slight differences due to computer rounding). 5. The slack variables for the three ≤ warehouse constraints would be added to the constraints as follows, x1A + x1B + x1C + s1 = 300 x2A + x2B + x2C + s2 = 200 x3A + x3B + x3C + s3 = 200 These three slacks would then be added to the objective function with the storage cost coefficients of $9 for s1, $6 for s2 and $7 for s3. This change would not result in a new solution. The model must be reformulated with three new variables reflecting the shipments from the new warehouse at Memphis (4) to the three stores, x4A, x4B, and x4C. These variables must be included in the objective function with the cost coefficients of $18, 9 and 12 respectively. A new supply constraint must be added, x4A + x4B + x4C ≤ 200 The solution to this reformulated model is, x1C = 200 x2B = 50 x3A = 150 x4B = 200 Z = 6,550 Yes, the warehouse should be leased. The shadow price for the Atlanta warehouse shows the greatest decrease in cost, $6 for every additional set supplied from this source. However, the upper limit of the sensitivity range is 200, the same as the current supply value. Thus, if the supply is increased at Atlanta by even one television set the shadow price will change. 6. This change would not affect the solution at all since there is no surplus with any of the three constraints. Component 1 has the greatest dual price of $20. For each barrel of component 1 the company can acquire, profit will increase by $20, up to the limit of the sensitivity range which is an increase of 1,700 bbls. or 6,200 total bbls. of component 1. For example an increase of one bbl. of component 1 from 4,500 to 4,501 results in a increase in total cost to $76,820. 7. (a) maximize Z = $190x1 + 170x2 + 155x3 subject to 3.5x1 + 5.2x2 + 2.8x3 ≤ 500 1.2x1 + 0.8x2 + 1.5x3 ≤ 240 40x1 + 55x2 + 20x3 ≤ 6,500 x1,x2,x3 ≥ 0 (b) x1 = 41.27, x2 = 0, x3 = 126.98, Z = $27,523.81 s1 = s2 = 0, s3 = 2,309.52 8. (a) It would not affect the model. The slack apples are multiplied by the revenue per apple of $.08 to determine the extra total revenue, i.e., (2,309.52)($.08) = $184.76. (b)This change requires a new variable, x4, and that the constraint for apples be changed from ≤ to =. No, the Friendly’s should not produce cider. The new solution would be x1 = 135, x2 = 0, x3 = 0, x4 = 18.33 and Z = $26,475. This reduction in profit occurs because the requirement that all 6,500 apples be used forces resources to be used for cider that would be more profitable to be used to produce the other products. If the final model constraint for apples is, ≤ rather than =, the previous solution in 1(b) results. 9. (a) x1 = no. of eggs x2 = no. of bacon strips x3 = no. of cups of cereal minimize Z = 4x1 + 3x2 + 2x3 subject to 2x1 + 4x2 + x3 ≥ 16 3x1 + 2x2 + x3 ≥ 12 x1, x2, x3 ≥ 0 (b)x1 = 2 x2 = 3 Z = $0.17 10. (a) xi = number of boats of type i, i = 1 (bass boat), 2 (ski boat), 3 (speed boat) In order to break even total revenue must equal total cost: 23,000x1 + 18,000x2 + 26,000x3 = 12,500x1 + 8,500x2 + 13,700x3 + 2,800,000 or, 10,500x1 + 9,500x2 + 12,300x3 = 2,800,000 minimize Z = 12,500x1 + 8,500x2 + 13,700x3 subject to 10,500x1 + 9,500x2 + 12,300x3 = 2,800,000 x1 ≥ 70 x2 ≥ 50 x3 ≥ 50 x1 ≤ 120 x2 ≤ 120 x3 ≤ 120 x1, x2, x3 ≥ 0 (b)x1 = 70.00 x2 = 120.00 x3 = 75.203 Z = $2,925,284.553 11. (a) x1 = no. of clocks x2 = no. of radios x3 = no. of toasters maximize Z = 8x1 + 10x2 + 7x3 subject to 7x1 + 10x2 + 5x3 ≤ 2,000 2x1 + 3x2 + 2x3 ≤ 660 x1 ≤ 200 x2 ≤ 300 x3 ≤ 150 x1, x2, x3 ≥ 0 (b)x1 = 178.571 x3 = 150.00 Z = $2,478.571 12. (a) x1 = no. of gallons of Yodel x2 = no. of gallons of Shotz x3 = no. of gallons of Rainwater maximize Z = 1.50x1 + 1.60x2 + 1.25x3 subject to x1 + x2 + x3 = 1,000 1.50x1 + .90x2 + .50x3 ≤ 2,000 x1 ≤ 400 x2 ≤ 500 x3 ≤ 300 x1, x2, x3 ≥ 0 (b)x1 = 400 x2 = 500 x3 = 100 Z = $1,525.00 13. (a) x1 = no. of lb of Super Two at Fresno x2 = no. of lb of Super Two at Dearborn x3 = no. of lb of Green Grow at Fresno x4 = no. of lb of Green Grow at Dearborn maximize Z = 7x1 + 5x2 + 5x3 + 4x4 subject to 2x1 + 4x2 + 2x3 + 3x4 ≤ 45,000 x1 + x2 ≤ 6,000 x3 + x4 ≤ 7,000 x1 + x3 ≤ 5,000 x2 + x4 ≤ 6,000 x1, x2, x3, x4 ≥ 0 (b)x1 = 5,000 x2 = 1,000 x4 = 5,000 Z = $60,000 14. (a) xi = ore i (i = 1,2,3,4,5,6) minimize Z = 27x1 + 25x2 + 32x3 + 22x4 + 20x5 + 24x6 subject to .19x1 + .43x2 + .17x3 + .20x4 +.12x6 ≥ .21 .15x1 + .10x2 + .12x4 + .24x5 + .18x6 ≤ .12 .12x1 + .25x2 + .10x5 + .16x6 ≤ .07 .14x1 + .07x2 + .53x3 + .18x4 + 0.31x5 + .25x6 ≥ .30 .14x1 + .07x2 + .53x3 + .18x4 + .31x5 + .25x6 ≤ .65 .60x1 + .85x2 + .70x3 + .50x4 + .65x5 + .71x6 = 1.00 (b)x2 = .1153 ton – ore 2 x3 = .8487 ton – ore 3 x4 = .0806 ton – ore 4 x5 = .4116 ton – ore 5 Z = $40.05 15. (a) xij = number of trucks assigned to route from warehouse i to terminal j, where i = 1 (Charlotte), 2 (Memphis), 3 (Louisville) and j = a (St. Louis), b (Atlanta), c (New York) maximize Z = 1.800x1a + 2,100x1b + 1,600x1c + 1,000x2a + 700x2b + 900x2c + 1,400x3a + 800x3b + 2,200x3c subject to x1a + x1b + x1c = 30 x2a + x2b + x2c = 30 x3a + x3b + x3c = 30 x1a + x2a + x3a ≤ 40 x1b + x2b + x3b ≤ 60 x1c + x2c + x3c ≤ 50 x ij ≥ 0 (b)x1b = 30 x2a = 30 x3c = 30 Z = $159,000 16. (a)x1 = no. of sofas x2 = no. of tables x3 = no. of chairs maximize Z = 400x1 + 275x2 + 190x3 subject to 7x1 + 5x2 + 4x3 ≤ 2,250 12x1 + 7x3 ≤ 1,000 6x1 + 9x2 + 5x3 ≤ 240 x1 + x2 + x3 ≤ 650 x1, x2, x3 ≥ 0 (b)x1 = 40 Z = $16,000 17. (a) xij = lbs. of seed i used in mix j, where i = t (tall fescue), m (mustang fescue), b (bluegrass) and j = 1,2,3. minimize Z = 1.70 (xt1 + xt2 + xt3) + 2.80 (xm1 + xm2 + xm3) + 3.25 (xb1 + xb2 + xb3) subject to .50xt1 –- .50xm1 – .50xb1 ≤ 0 –.20xt1 + .80xm1 – .20xb1 ≥ 0 –.30xt2 – .30xm2 + .70xb2 ≥ 0 –.30xt2 + .70xm2 – .30xb2 ≥ 0 .80xt2 – .20xm2 – .20xb2 ≤ 0 .50xt3 – .50xm3 – .50xb3 ≥ 0 .30xt3 – .70xm3 – .70xb3 ≤ 0 –.10xt3 – .10xm3 + .90xb3 ≥ 0 xt1 + xm1 + xb1 ≥ 1,200 xt2 + xm2 + xb2 ≥ 900 xt3 + xm3 + xb3 ≥ 2,400 xij ≥ 0 (b)xt1 = 600 xt2 = 180 xt3 = 1,680 xm1 = 600 xm2 = 450 xm3 = 480 xb1 = 0 xb2 = 270 xb3 = 240 Z = $10,123.50 18. (a) xij = acres of crop i planted on plot j, where i = c (corn), p (peas), s (soybeans) and j = 1,2,3 maximize Z = 600(xc1 + xc2 + xc3) + 450(xp1 + xp2 + xp3) + 300(xs1 + xs2 + xs3) subject to xc1 + xp1 + xs1 ≥ 300 xc1 + xp1 + xs1 ≤ 500 xc2 + xp2 + xs2 ≥480 xc2 + xp2 + xs2 ≤ 800 xc3 + xp3 + xs3 ≥420 xc3 + xp3 + xs3 ≤ 700 xc1 + xc2 + xc3 ≤ 900 xp1 + xp2 + xp3 ≤ 700 xs1 + xs2 + xs3 ≤ 1,000 800(xc1 + xp1 + xs1) – 500(xc2 + xp2 + xs2) = 0 700(xc2 + xp2 + xs2) – 800(xc3 + xp3 + xs3) = 0 700(xc1 + xp1 + xs1) – 500(xc3 + xp3 + xs3) = 0 xij ≥ 0 (b)xc1 = 500 xc2 = 100 xc3 = 300 xp2 = 700 xs3 = 400 Z = $975,000 19. (a) x1 = $ allocated to job training x2 = $ allocated to parks x3 = $ allocated to sanitation x4 = $ allocated to library maximize Z = .02x1 + .09x2 + .06x3 + .04x4 subject to x1 + x2 + x3 + x4 = 4,000,000 x1 ≤ 1,600,000 x2 ≤ 1,600,000 x3 ≤ 1,600,000 x4 ≤ 1,600,000 x2 – x3 – x4 ≤ 0 x1 – x3 ≥ 0 x1, x2, x3, x4 ≥ 0 (b) x1 = 800,000 x2 = 1,600,000 x3 = 800,000 x4 = 800,000 Z = 240,000 20. (a) minimize Z = .80x1 + 3.70x2 + 2.30x3 + .90x4 + .75x5 + .40x6 + .83x7 subject to 520x1 + 500x2 + 860x3 + 600x4 + 50x5 + 460x6 + 240x7 ≥ 1,500 520x1 + 500x2 + 860x3 + 600x4 + 50x5 + 460x6 + 240x7 ≤ 2,000 4.4x1 + 3.3x2 + .3x3 + 3.4x4 + .5x5 + 2.2x6 + .2x7 ≥ 5 30x1 + 5x2 + 75x3 + 3x4 + 10x7 ≥ 20 30x1 + 5x2 + 75x3 + 3x4 + 10x7 ≤ 60 17x1 + 85x2 + 82x3 + 10x4 + 6x5 + 10x6 + 16x7 ≥ 30 30x4 + 70x6 + 22x7 ≥ 40 180x1 + 90x2 + 350x3 + 20x7 ≤ 30 xi ≥ 0 (b)x4 = 1.667 x6 = 0.304 x7 = 1.500 Z = $2.867 (c) The model becomes infeasible and cannot be solved. Limiting each food item to one-half pound is too restrictive. In fact, experimentation with the model will show that one food item in particular, dried beans, is restrictive. All other food items can be limited except dried beans. 21. (a) xij = number of units of products i (i = 1,2,3) produced on machine j (j = 1,2,3,4) maximize Z = $7.8x11 + 7.8x12 + 8.2x13 + 7.9x14 + 6.7x21 + 8.9x22 + 9.2x23 + 6.3x24 + 8.4x31 + 8.1x32 + 9.0x33 + 5.8x34 subject to 35x11 + 40x21 + 38x31 ≤ 9,000 41x12 + 36x22 + 37x32 ≤ 14,400 34x13 + 32x23 + 33x33 ≤ 12,000 39x14 + 43x24 + 40x34 ≤ 15,000 x11 + x12 + x13 + x14 = 400 x21 + x22 + x23 + x24 = 570 x31 + x32 + x33 + x34 = 320 xij ≥ 0 (b)x11 = 15.385 x14 = 384.615 x22 = 400.00 x23 = 170.00 x31 = 121.212 x33 = 198.788 Z = $11,089.73 22. (a) Minimize Z = 69x11 + 71x12 + 72x13 + 74x14 + 76x21 + 74x22 + 75x23 + 79x24 + 86x31 + 89x32 + 80x33 + 82x34 subject to x11 + x12 + x13 + x14 ≤ 220 x21 + x22 + x23 + x24 ≤ 170 x31 + x32 + x33 + x34 ≤ 280 x11 + x21 + x31 = 110 x12 + x22 + x32 = 160 x13 + x23 + x33 = 90 x14 + x24 + x34 = 180 Ash: .03x11 – .01x21 – .02x31 ≤ 0 .04x12 – .0x22 – .01x32 ≤ 0 .04x13 – .0x23 – .01x33 ≤ 0 .03x14 – .01x24 – .02x34 ≤ 0 Sulfur: .01x11 – .01x21 – .02x31 ≤ 0 .01x12 + .01x22 – .02x32 ≤ 0 –.01x13 + .03x23 – .04x33 ≤ 0 .0x14 – .02x24 – .03x34 ≤ 0 xij ≥ 0 (b) x11 = 42 x13 = 18 x14 = 72 x21 = 10 x22 = 160 x31 = 58 x33 = 72 x34 = 108 Z = $41,726 23. (a) xij = space (ft2) rented in month i for j months, where i = 1,2...,6, and j = 1,2,...,6 Minimize Z = 1.70x11 + 1.40x12 + 1.20x13 + 1.10x14 + 1.05x15 + 1.00x16 + 1.70x21 + 1.40x22 + 1.20x23 + 1.10x24 + 1.05x25 + 1.70x31 + 1.40x32 + 1.20x33 + 1.10x34 + 1.70x41 + 1.40x42 + 1.20x43 + 1.70x51 + 1.40x52 + 1.70x61 subject to: x11 + x12 + x13 + x14 + x15 + x16 = 47,000 x12 + x13 + x14 + x15 + x16 + x22 + x23 + x24 + x25 = 35,000 x13 + x14 + x15 + x16 + x22 + x23 + x24 + x25 + x31 + x32 + x33 + x34 = 52,000 x14 + x15 + x16 + x23 + x24 + x25 + x32 + x33 + x34 + x41 + x42 + x43 = 27,000 x15 + x16 + x24 + x25 + x33 + x34 + x42 + x43 + x51 + x52 = 19,000 x16 + x25 + x34 + x43 + x52 + x61 = 15,000 (b)x11 = 12,000 x13 = 25,000 x14 = 8,000 x15 = 2,000 x33 = 2,000 x34 = 15,000 Z = $80,200 (c)x16 = 52,000 Z = $52,000 It is much cheaper to rent all the space for the entire six month period in April and have excess or “surplus” space. 24. (a) xij = no. of students bused from district i to school j, where i = n, s, e, w, c and j = c,w,s minimize Z = 8xnc + 11xnw + 14xns + 12xsc + 9xsw + 0xss + 9xec + 16xew + 10xes + 8xwc + 0xww + 9xws + 0xcc + 8xcw + 12xcs subject to xnc + xnw + xns = 700 xsc + xsw + xss = 300 xec + xew + xes = 900 xwc + xww + xws = 600 xcc + xcw + xsc = 500 xnc + xsc + xec + xwc + xcc ≤ 1,200 xnw + xsw + xew + xww + xcw ≤ 1,200 xns + xss + xes + xws + xcs ≤ 1,200 xij ≥ 0 (b)xnc = 700 xss = 300 xes = 900 xww = 600 xcc = 500 Z = 14, 600 25. (a) Add the following 3 constraints to the original formulation: xss ≤ 150 xww ≤ 300 xcc ≤ 250 xnc = 700 xnw = 0 xsw = 150 xss = 150 xes = 900 xwc = 250 xww = 300 xws = 50 xcc = 250 xcw = 250 Z = 20,400 (b)Change the 3 demand constraints in the (a) formulation from ≤ 1,200 to = 1,000. xnc = 400 xnw = 300 xsw = 150 xss = 150 xec = 50 xes = 850 xwc = 300 xww = 300 xcc = 250 xcw = 250 Z = 21,200 26. (a) x1 = no. of lb of oats x2 = no. of lb of corn x3 = no. of lb of soybean x4 = no. of lb of vitamin supplement minimize Z = .50x1 + 1.20x2 + .60x3 + 2.00x4 subject to x1 ≤ 300 x2 ≤ 400 x3 ≤ 200 x4 ≤ 100 x3/(x1 + x2 + x3 + x4) ≥ .30 x4/(x1 + x2 + x3 + x4) ≥ .20 x2/x1 ≤ 2/1 x1 ≤ x3 x1 + x2 + x3 + x4 ≥ 500 x1, x2, x3, x4 ≥ 0 (b) x1 = 200 x2 = 0 x3 = 200 x4 = 100.00 Z = $420 27. (a) x1 = no. of day contacts by phone x2 = no. of day contacts in person x3 = no. of night contacts by phone x4 = no. of night contacts in person maximize Z = 2x1 + 4x2 + 3x3 + 7x4 subject to x2 + x4 ≤ 300 6x1 + 15x2 ≤ 1,200 5x3 + 12x4 ≤ 2,400 x1, x2, x3, x4 ≥ 0 (b) x1 = 200 x3 = 480 Z = 1,840 28. (a) xij = dollar amount invested in alternative i in year j, where i = p (product research and development), m (manufacturing operations improvements), a (advertising and sales promotion) and j = 1,2,3,4 (denoting year): sj = slack, or uninvested funds in year j maximize Z = s4 + 1.2xa4 + 1.3xm3 + 1.5xp3 subject to xa1 ≥ 30,000 xm1 ≥ 40,000 xp1 ≥ 50,000 xa1 + xm1 + xp1 + s1 = 500,000 xa2 + xm2 + xp2 + s2 = s1 + 1.2xa1 xa3 + xm3 + xs3 = s2 + 1.2xa2 + 1.3xm1 xa4 + xs4 = s3 + 1.2xa3 + 1.3xm2 + 1.5xp1 xij, sj ≥ 0 Note: Since it is assumed that any amount of funds can be invested in each alternative— i.e., there is no minimum investment required—and funds can always be invested in as short a period as one year yielding a positive return, it is apparent that the sj variables for uninvested funds will be driven to zero in every period. Thus, these variables could be omitted from the model formulation for this problem. (b)xa1 = 410,000 xa2 = 492,000 xa3 = 642,400 xa4 = 845,880 xm1 = 40,000 xp1 = 50,000 Z = $1,015,056 29. (a) x1 = no. of homeowner's policies x2 = no. of auto policies x3 = no. of life policies maximize Z = 35x1 + 20x2 + 58x3 subject to 14x1 + 12x2 + 35x3 ≤ 35,000 6x1 + 3x2 + 12x3 ≤ 20,000 x1, x2, x3 ≥ 0 (b)x1 = 2,500 Z = $87,500 30. (a) x1 = no. of issues of Daily Life x2 = no. of issues of Agriculture Today x3 = no. of issues of Surf’s Up maximize Z = 2.25x1 + 4.00x2 + 1.50x3 subject to x1 + x2 + x3 ≥ 5,000 .01x1 + .03x2 + .02x3 ≤ 120 .2x1 + .5x2 + .3x3 ≤ 3,000 x1 ≤ 3,000 x2 ≤ 2,000 x3 ≤ 6,000 x1, x2, x3 ≥ 0 (b)x1 = 3,000 x2 = 2,000 x3 = 1,500 Z = $17,000 31. (a) x1 = no. of television commercials x2 = no. of newspaper ads x3 = no. of radio commercials minimize Z = 15,000x1 + 4,000x2 + 6,000x3 subject to x3/x2 ≥ 2/1 25,000x1 + 10,000x2 + 15,000x3 ≥ 100,000 (15,000x1 + 3,000x2 + 12,000x3)/ (10,000x1 + 7,000x2 + 3,000x3) ≥ 2/1 (15,000x1 + 4,000x2 + 9,000x3)/ (25,000x1 + 10,000x2 + 15,000x3) ≥ .30 x2 ≤ 7 x1, x2, x3 ≥ 0 (b)x2 = 2.5 x3 = 5.0 Z = 40,000 (c) This reformulation of the model would result in a fourth variable x4, with model parameters inserted accordingly. However, it would have no effect on the solution. 32. (a) xij = lbs. of coffee i used in blend j per week, where i = b (Brazilian), o (Mocha), c (Colombian), m (mild) and j = s (special), d (dark), r (regular) maximize Z = 4.5xbs + 3.75xos + 3.60xcs + 4.8xms + 3.25xbd + 2.5xod + 2.35xcd + 3.55xmd + 1.75xbr + 1.00xor + 0.85xcr + 2.05xmr subject to . 6xcs – .4xbs – .4xos – .4xms ≥ 0 –.3xbs + .7xos – .3xcs – .3xms ≥ 0 .4xbd – .6xod – .6xcd – .6xmd ≥ 0 –.1 xbd – .1xod – .1xcd + .9xmd ≤ 0 –.6xbr – .6xor – .6xcr + .4xmr ≤ 0 .7xbr – .3xor – .3xcr – .3xmr ≥ 0 xbs + xbd + xbr ≤ 110 xos + xod + xor ≤ 70 xcs + xcd + xcr ≤ 80 xms + xmd + xmr ≤ 150 xij ≥ 0 (b) xos = 60 Special: xos + xcs + xms = 200lbs. xcs = 80 Dark: xbd + xmd = 72 lbs. xms = 60 Regular: xbr + xor + xmr = 138 lbs. xbd = 64.8 xmd = 7.2 xbr = 45.2 xor = 10 xmr = 82.8 Z = $1,296 33. (a) x1 = $ amount borrowed for six months in July yi = $ amount borrowed in month i (i = 1, 2, ..., 6) for one month ci = $ amount carried over from month i to i + 1 6 minimize Z = .11x1 + .05∑ yi i =1 subject to July: August: September: October: November December: End: (b)x14 = 20 x44 = 40 x35 = 20 x55 = 60 x66 = 90 x17 = 10 x27 = 30 x37 = 0 x77 = 50 x1 + y1 + 20,000 – c1 = 60,000 c1 + y2 + 30,000 – c2 = 60,000 + y1 c2 + y3 + 40,000 – c3 = 80,000 + y2 c3 + y4 + 50,000 – c4 = 30,000 + y3 c4 + y5 + 80,000 – c5 = 30,000 + y4 c5 + y6 + 100,000 – c6 = 20,000 + y5 x1 + y6 ≤ c6 x1, yi, ci ≥ 0 Production for Month j (b) Solution x1 = 70,000 y3 = 40,000 y4 = 20,000 y1 = y2 = y5 = y6 = 0 c1 = 30,000 c5 = 30,000 c6 = 110,000 Z = $10,700 (c) Changing the six-month interest rate to 9% results in the following new solution: x1 = 90,000 y3 = 20,000 c1 = 50,000 c2 = 20,000 c5 = 50,000 c6 = 130,000 Z = $9,100 34. (a) xij = production in month i to meet demand in month j, where i = 1,2,... 7 and j = 4,5,6 and 7 yj = overtime production in month j where j = 4,5,6,7. Minimize Z = 150x14 + 100x24 + 50x34 + 200x15 + 150x25 + 100x35 + 250x16 + 200x26 + 150x36 + 300x17 + 250x27 + 200x37 + 400y4 + 400y5 + 400y6 + 400y7 Subject to x14 + x24 + x34 + x44 + y4 = 60 x15 + x25 + x35 + x55 + y5 = 85 x16 + x26 + x36 + x66 + y6 = 100 x17 + x27 + x37 + x77 + y7 = 120 x14 + x15 + x16 + x17 ≤ 30 x24 + x25 + x26 + x27 ≤ 30 x34 + x35 + x36 + x37 ≤ 30 x44 ≤ 40 x55 ≤ 60 x66 ≤ 90 x77 ≤ 50 y4 ≤ 20 y5 ≤ 20 y6 ≤ 20 y7 ≤ 20 y5 = 5 y6 = 10 y7 = 20 Z = $31,500 Month i Capacity 4 5 6 1 2 3 4 5 6 7 30 30 30 40 60 90 50 20 Overtime — 5 10 20 Demand 60 85 100 120 20 7 Capacity 10 30 10 30 30 30 40 60 90 50 40 60 90 50 (c) x34 = 20 x44 = 40 x25 = 5 x35 = 20 x55 = 60 x26 = 10 x66 = 90 x17 = 40 x27 = 25 x77 = 50 y7 = 5 Z = $26,000 35. (a) xij = amount of ingredient i in wiener type j, where i = c, b, p, a represent chicken, beef, pork, and additives, and j = r,b,m represent regular, beef, and all-meat, respectively maximize Z = .7xcr + .6xbr + .4xpr + .85xar + 1.05 xcb + .95xbb + .75xpb + 1.20xab + 1.55xcm + 1.45xbm + 1.25xpm + 1.70xam subject to xcr + xcb + xcm ≤ 200 xbr + xbb + xbm ≤ 300 xpr + xpb + xpm ≤ 150 xar + xab + xam ≤ 400 .90xbr + .90xpr – .l0xcr – l0xar ≤ 0 .80xcr –.20xbr – .20xpr – .20xar ≥ 0 .25xbb – .75xcb – .75xpb – .75xab ≥ 0 *xam = 0 .5xbm + .5xpm – .5xcm – .5xam ≤ 0 xij ≥ 0 *Also feasible to delete xam from the problem. (b) xcr = 75 xar = 300 xcm = 125 xab = 100 xbb = 300 xpm = 1250 Z = $1,062.50 36. (a) This is an assignment problem. x1 = operator 1 to drill press x2 = operator 1 to lathe x3 = operator 1 to grinder x4 = operator 2 to drill press x5 = operator 2 to lathe x6 = operator 2 to grinder x7 = operator 3 to drill press x8 = operator 3 to lathe x9 = operator 3 to grinder minimize Z = 22x1 + 18x2 + 35x3 + 41x4 + 30x5 + 28x6 + 25x7 + 36x8 + 18x9 subject to x1 + x2 + x3 = 1 x4 + x5 + x6 = 1 x7 + x8 + x9 = 1 x1 + x4 + x7 = 1 x2 + x5 + x8 = 1 x3 + x6 + x9 =1 x1, x2, x3, x4, x5, x6, x7, x8, x9 ≥ 0 (b)x1 = 1 x5 = 1 x9 = 1 Z = 70 (c) This would require the model to be reformulated with three new variables, x10, x11, x12, representing Kelly’s assignment to the press, lathe, and grinder. The model would be reformulated as, Minimize Z = 22x1 + 18x2 + 35x3 +41x4 + 30x5 + 28x6 + 25x7 + 36x8 + 18x9 + 20x10 + 20x11 +20x12 subject to x1 + x2 + x3 ≤ 1 x4 + x5 + x6 ≤ 1 x7 + x8 + x9 ≤ 1 x10 + x11 + x12 ≤ 1 x1 + x4 + x7 + x10 = 1 x2 + x5 + x8 + x11 = 1 x3 + x6 + x9 + x12 = 1 xi ≥ 0 The new solution is x2 = 1, x9 = 1, x10 = 1, Z = 56. Joe should hire Kelly. 37. (a) This is a transportation problem. x1 = no. of tons of carpet shipped from St. Louis to Chicago x2 = no. of tons of carpet shipped from St. Louis to Atlanta x3 = no. of tons of carpet shipped from Richmond to Chicago x4 = no. of tons of carpet shipped from Richmond to Atlanta minimize Z = 40x1 + 65x2 + 70x3 + 30x4 subject to x1 + x2 = 250 x3 + x4 = 400 x1 + x3 = 300 x2 + x4 = 350 x1, x2, x3, x4 ≥ 0 (b)x1 = 250 x3 = 50 x4 = 350 Z = 24,000 38. (a) xi = number of nurses that begin the 8-hour shift in period i, where i = 1,2,...12 and period 1 = 12 AM–2 AM, period 2 = 2AM–4AM, etc. minimize Z = x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 subject to x10 + x11 + x12 + x1 ≥ 30 x11 + x12 + x1 + x2 ≥ 20 x12 + x1 + x2 +x3 ≥ 40 x1 + x2 + x3 + x4 ≥ 50 x2 + x3 + x4 + x5 ≥ 60 x3 + x4 + x5 + x6 ≥ 80 x4 + x5 + x6 + x7 ≥ 80 x5 + x6 + x7 + x8 ≥ 70 x6 + x7 + x8 + x9 ≥70 x7 + x8 + x9 + x10 ≥ 60 x8 + x9 + x10 + x11 ≥ 50 x9 + x10 + x11 + x12 ≥ 50 xij ≥ 0 (b)x1 = 30 x3 = 10 x4 = 10 x5 = 40 x6 = 20 x7 = 10 x9 = 40 x10 = 10 Z = 170 39. (a) x1 = no. of hours molding x2 = no. of hours smoothing x3 = no. of hours painting maximize Z = 175(7x1) = 1,225x1 subject to 8x1 + 5x2 + 6.5x3 ≤ 3,000 x1 + x2 + x3 ≤ 120 90(7x1) ≤ 10,000 7x1 – 12x2 = 10x3 7x1 – 12x2 = 0 (The no. of units going 12x2 – 10x3 = 0 through each process 7x1 – 10x3 = 0 must be equal. More x1, x2, x3 ≥ 0 bathtubs cannot be smoothed than are first molded.) (b)x1 = 15.87 hours x2 = 9.26 hours x3 = 11.11 hours Z = 19,444.44 40. xi = In-state freshman in college i; i = 1,2, .... 6 yi = Out-of-state freshmen in college i; i =1,2,.... 6 Maximize Z = 8600 (∑ xi) + 19,200 (∑ yi) subject to: x1 + y1 ≤ 820 x2 + y2 ≤ 1300 x3 + y3 ≤ 240 x4 + y4 ≤ 820 x5 + y5 ≤ 1060 x6 + y6 ≤ 610 Σ SATIi ( xi ) + Σ SATOi ( yi ) ≥ 1150 Σxi + Σyi Σyi ≤ .47 Σxi + Σyi xi ≥ .30, i = 1, 2, … 6 xi + yi Σ xi + Σ yi ≤ 4, 500 xi , yi ≥ 0 Solution: x1 (in-state Architecture) = 201 x2 (in-state A&S) = 742 x3 (in-state Agriculture) = 103 x4 (in-state Business) = 351 x5 (in-state Engineering) = 454 x6 (in-state Human Resource) = 446 y1 (out-of-state Architecture) = 269 y2 (out-of-state A&S) = 558 y3 (out-of-state Agriculture) = 137 y4 (out-of-state Business) = 469 y5 (out-of-state Engineering) = 606 y6 (out-of-state Human Resources) = 0 Z = $59,905,095 41. (a) x13 = tons shipped from 1 to 3 x14 = tons shipped from 1 to 4 x12 = tons shipped from 1 to 2 x34 = tons shipped from 3 to 4 x45 = tons shipped from 4 to 5 x25 = tons shipped from 2 to 5 minimize Z = 3x13 + 4x14 + 5x12 + 2x34 + 7x45 + 8x25 subject to x13 + x14 + x12 = 5 x45 + x25 = 5 x13 = x34 x14 + x34 = x45 x12 = x25 x13, x14, x12, x34, x45, x25 ≥ 0 (b)x14 = 5 x45 = 5 Z = $55,000 42. (a) xij = barrels of component i used in gasoline grade j per day, where i = 1, 2, 3, 4 and j = R (regular), P (premium), L (low lead) Regular: x1R + x2R + x3R + x4R Premium: x1P + x2P + x3P + x4P Low lead: x1L + x2L + x3L + x4L maximize Z = 3x1R + 5x2R + 0x3R + 6x4R + 9x1P + 11x2P + 6x3P + 12x4P + x1L + 3x2L – 2x3L + 4x4L subject to x1R + x2R + x3R + x4R ≥ 3,000 x1P + x2P + x3P + x4P ≥ 3,000 x1L + x2L + x3L + x4L ≥ 3,000 x1R + x1P + x1L ≤ 5,000 x2R + x2P + x2L ≤ 2,400 x3R + x3P + x3L ≤ 4,000 x4R + x4P + x4L ≤ 1,500 .6x1R – .4x2R – .4x3R – .4x4R ≥ 0 -.2x1R + .8x2R – .2x3R – .2x4R ≤ 0 -.3x1R – . 3x2R + .7x3R – .3x4R ≥ 0 -.4x1P – .4x2P + .6x3P – .4x4P ≥ 0 -.5x1L + .5x2L – .5x3L – .5x4L ≤ 0 .9x1L – .1x2L – .1x3L – .1x4L ≥ 0 all xij ≥ 0 (b)x1R = 2,000 x2R = 100 x3R = 900 x2P = 2,300 x3P = 3,100 x4P = 1,500 x1L = 3,000 Z = $71,400 44. (a) Year 1 S1 Total used (ft) Year 4 S3 Year 5 S4 B4 B2 2 3 4 5 6 3 0 0 2 0 1 2 1 0 1 2 0 0 1 1 0 0 2 21 24 23 25 19 20 xi = no. of standard-length boards to cut using pattern i minimize Z = x1 + x2 + x3 + x4 + x5 + x6 subject to 3x1 + 2x2 + 2x3 + x4 = 700 x3 + 2x4 + x5 = 1,200 x2 + x5 + 2x6 = 300 xi ≥ 0 (b)x2 = 50 x4 = 600 x6 = 125 Z = 775 B3 C2 R5 Si = amount of money invested in stocks at the beginning of year i, i = 1,2,3,4,5 Bi = amount of money invested in bonds at the beginning of the year i, i = 1,2,3,4,5 C2 = amount of money invested in certificates of deposit in year 2 Ri = amount of money invested in real estate at the beginning of year i, i = 5,6 Ii = amount of money held idle and not invested at beginning of year i maximize Z = 1.20S5 + 1.40B4 + 1.10R6 + I6 subject to S2 + B2 + C2 − I1 + I 2 = 0 − 1.20 S1 + S3 + B3 − I2 + I3 = 0 Pattern Length (ft) 1 Trim loss (ft) R6 S1 + B1 + I1 = $1, 000, 000 (c) 7 9 10 Year 6 S5 B1 Pattern Length (ft) 1 Year 3 S2 43. (a)First, all possible patterns that contain the desired lengths must be determined. 7 9 10 Year 2 − 1.20S2 + S4 − 1.40 B1 + 2 3 4 5 6 3 0 0 2 0 1 2 1 0 1 2 0 0 1 1 0 0 2 4 1 2 0 6 5 B4 − I 3 + I4 = 0 −1.20 S3 + S5 − 1.40 B2 + R5 − I 4 + I5 = 0 −1.20 S4 = 1.40 B3 − 1.8 80C2 − 1.10 R5 + R6 − I 5 + I6 = 0 xi = no. of standard-length boards to cut using pattern i; coefficients of objective function = trim loss using pattern i 0.7∑ Si − 0.3∑ Bi − 0.3C2 − minimize Z = 4x1 + x2 + 2x3 + 0x4 + 6x5 + 5x6 subject to 0.3∑ Ri ≤ 0 3x1 + 2x2 + 2x3 + x4 ≥ 700 x3 + 2x4 + x5 ≥ 1,200 x2 + x5 + 2x6 ≥ 300 xi ≥ 0 x2 = 300 x4 = 600 Z = 300 5 4 i =1 i =1 6 i =5 5 4 i =1 i =1 −0.25∑ Si − 0.25∑ Bi + 6 0.75C2 − 0.25∑ Ri ≥ 0 i =5 Si , Bi , Ci , Ri , Ii ≥ 0 (b) I1 = 1,000,000 C2 = 1,000,000 R6 = 1,800,000 Z = $1,980,000 45. (a) xi = amount sold in month i yi = amount purchased in month i si = amount held in storage in month i (until the beginning of the following month) s0 = amount available at the beginning of month 1 4 3 i =1 i =1 maximize Z = ∑ pi xi − ∑ ci yi subject to xi ≤ si-1 (sales ≤ amount held in storage from previous month) si = si-1 – xi + yi (ending storage = beginning storage – sales + purchases) si ≤ 10,000 (amount held in storage ≤ storage capacity) or maximize Z = 4x1 + 8x2 + 6x3 + 7x4 – 5y1 – 6y2 – 7y3 subject to s0 = 2,000 x1 ≤ s0 s1 = s0 – x1 + y1 s1 ≤ 10,000 x2 ≤ s1 s2 = s1 – x2 + y2 s2 ≤ 10,000 x3 ≤ s2 s3 = s2 – x3 + y3 s3 ≤ 10,000 x4 ≤ s3 xi, yi, si ≥ 0 (b) x1 = 0 x2 = 10,000 x4 = 10,000 y1 = 8,000 y2 = 10,000 s0 =2,000 s1 = 10,000 s2 = 10,000 s3 = 10,000 Z = $50,000 46. (a) xi = regular production in month i, where i = 1, 2, 3, 4, 5 yi = overtime production in month i, where i = 1,2,3,4,5 wi = units in inventory at end of month i, where i = 1, 2, 3, 4 minimize Z = $10(x1 + x2 + x3 + x4 + x5) + 15(y1 + y2 + y3 + y4 + y5) + 2(w1 + w2 + w3 + w4) subject to xi ≤ 2,000 (i = 1, 2, 3, 4, 5) yi ≤ 600 (i = 1,2,3,4,5) x1 + y1 – w1 = 1,200 x2 + y2 + w1 – w2 = 2,100 x3 + y3 + w2 – w3 = 2,400 x4 + y4 + w3 – w4 = 3,000 x5 + y5 + w4 = 4,000 xi, yi, wi ≤ 0 (b) x1 = 2,000 x2 = 2,000 x3 = 2,000 x4 = 2,000 x5 = 2,000 y1 = 300 y2 = 600 y3 = 600 y4 = 600 y5 = 600 w1 =1,100 w2 = 1,600 w3 = 1,800 w4 = 1,400 Z = $152,300 47. (a) xij = employee i assigned to department j, where i = 1,2,3,4 and j = a (lamps), b (sporting goods), c (linen) maximize Z = 130x1a + l50x1b + 90x1c + 275x2a + 300x2b + 100x2c + 180x3a + 225x3b + 140x3c + 200x4a + 120x4b + 160x4c subject to x1a + x1b + x1c = 1 x2a + x2b + x2c = 1 x3a + x3b + x3c = 1 x4a + x4b + x4c = 1 1≤ (x1a + x2a + x3a + x4a) ≤ 2 1≤ (x1b + x2b + x3b + x4b) ≤ 2 1 ≤ (x1c + x2c + x3c + x4c) ≤ 2 xij ≥ 0 (b) x1a = 1 x2b = 1 x3b = 1 x4c = 1 Z = 815 (c) xij = employee i assigned to department j, where i = 1,2,3,4, and j = a (lamps), b (sporting goods), c (linen) maximize Z = 130x1a + 150x1b + 90x1c + 275x2a + 300x2b + 100x2c + 180x3a + 225x3b + 140x3c + 200x4a + 120x4b + 160x4c subject to x1a + x1b + x1c ≤ 1 x2a + x2b + x2c ≤ 1 x3a + x3b + x3c ≤ 1 x4a + x4b + x4c ≤ 1 x1a + x2a + x3a +x4a = 1 x1b + x2b + x3b + x4b = 1 x1c + x2c + x3c + x4c = 1 xi ≥ 0 x2a = 1 x3b = 1 x4c = 1 Z = 660 48. Z values: A =1.000, B = 1.000, C = .6700, D = 1.000 Bank C is inefficient 49. Z values: A =1.000, B = 1.000, C = 1.000 all 3 hospitals are relatively inefficient. 150x + y10 = 700 + y11 150x + y11 ≥ 500 (b) Z = x = 4.4545 lawyers y1 = 18.1818 y2 = 236.3636 y3 = 304.5454 y4 = 472.7273 y5 = 440.9091 y6 = 459.09 y7 = 377.2727 y8 = 145.4545 y9 = 13.6364 y10 = 31.8182 y11 = 0 50.(a) xij = amount shipped from city i to city j maximize Z = xAB + xAC or maximize Z = xEF + xCF subject to xAB ≤ 7 xAC ≤ 6 xBE ≤ 2 xBD ≤ 5 xBC ≤ 10 xCD ≤ 3 xCF ≤ 9 xDE ≤ 4 xEF ≤ 3 xAB = xBC + xBD + xBE xAC +xBC = xCD + xCF xBD + xCD = xDE xBE + xDE = xEF xij ≥ 0 (b) xAB = 6 xAC = 6 xBE = 2 xBD = 1 xBC = 3 xCF = 9 xDE = 1 xEF = 3 Z = 12 51.(a) Minimize Z = x subject to 150x = 650 + y1 150x + y1 = 450 + y2 150x + y2 = 600 + y3 150x + y3 = 500 + y4 150x + y4 = 700 + y5 150x + y5 = 650 + y6 150x + y6 = 750 + y7 150x + y7 = 900 + y8 150x + y8 = 800 + y9 150x + y9 = 650 + y10 52. The original optimal solution has x = 4.4545 lawyers being hired. To get an “optimal” integer solution you would have to round either down to x = 4 or up to x = 5. Adding a new constraint, x = 4, to the original model formulation results in an infeasible solution so rounding down is not possible. Adding the constraint, x = 5, instead (i.e., rounding up) results in a feasible solution so (by logical deduction) it must be optimal. The original solution had 168.1818 surplus hours while the new integer solution has 1,150 surplus hours, a large difference in excess capacity. However, increasing the number of lawyers (to 6, for example) only increases the surplus so x = 5 has to be the optimal integer solution. 53. (a) y = quantity of assembled product produced per day x1 = quantity of component 1 produced per day x2 = quantity of component 2 produced per day x3 = quantity of component 3 produced per day maximize Z = y subject to y = x1 y = x2 y = x3 (Component 1) (Component 2) (Component 3) Note: The above constraints reflect the fact that the quantity of completely assembled product cannot exceed the quantities of components 1, 2, and 3 produced per day, i.e., no in-process inventory. The time available on one lathe is: 60 min/hr. × 8 hrs/day = 480 min. In order to reflect the availability of two lathes (with the work load shared evenly between them) the total minutes of lathe time available is: 480 min/day/machine × 2 machines = 960 min. relaxed such that y ≤ x1, y ≤ x2 and y ≤ x3, production output would increase: Thus, the lathe use/availability constraint is: 10x1 + 8x2 + 6x3 ≤ 960 (Lathe Time) x1 = 43.077 x2 = x3 = y = 29.31 By the same rationale, the press use/ availability constraint (for three presses) is: The best alternative is to remove the machine balancing requirement. If both requirements are relaxed the production output is x1 = x2 = x3 = y = 32. 9x1 + 21x2 + 15x3 ≤ 1440 (Press Time) Assuming that the work loads are shared equally among the lathes, and similarly for presses, the individual machine utilizations, are: (10x1 + 8x2 + 6x3)/2 = 5x1 + 4x2 + 3x3 (9x1 + 21x2 + 15x3)/3 = 3x1 + 7x2 + 5x3 54. (a) xij = amount of commodity i put into hold j, where i = b (beef), g (grain) and j = f (fore), a (aft) maximize Z = .35(xbf + xba) + .12(xgf + xga) subject to The balance condition is reflected by specifying that the absolute difference between individual machine time consumed (on lathes versus presses) must be less than or equal to 60 minutes. xbf + xgf ≤ 70,000 xba + xga ≤ 90,000 .2xbf + .4xgf ≤ 30,000 .2xba + .4xga ≤ 40,000 xbf + xba ≤ 85,000 xgf + xga ≤ 100,000 xij ≤ 0 |(5x1 + 4x2 + 3x3) – (3x1 + 7x2 + 5x3)| ≤ 60 or, (b) xba = 85,000 xgf = 70,000 xga = 5,000 Z = 38,750 |2x1 – 3x2 – 2x3| ≤ 60 Absolute value constraint conditions can be reflected by: 2x1 – 3x2 – 2x3 ≤ 60 –2x1 + 3x2 + 2x3 ≤ 60 The model is summarized as follows: maximize Z = y subject to y – x1 = 0 y – x2 = 0 y – x3 = 0 10x1 + 8x2 + 6x3 ≤ 960 9x1 + 21x2 + 15x3 ≤ 1440 2x1 – 3x2 – 2x3 ≤ 60 –2x1 + 3x2 + 2x3 ≤ 60 x1, x2, x3, y ≥ 0 (b) x1 = x2 = x3 = y = 20 (c) If the machine balancing requirement is relaxed such that the constraints 2x1 – 3x2 – 2x3 ≤ 60 and –2x1 + 3x2 + 2x3 ≤ 60 are eliminated, production output would increase: x1 = x2 = x3 = y = 32 Alternatively, if the restriction that there be no excess component parts at the end of the day is 55. xi = no. of commercial minutes during broadcast segment i, where i = l (local news), n (national news), s (sports), w (weather) yi = no. of minutes for broadcast segment i maximize Z = $850xl + 600xn + 750xs + 1000xw subject to xl + xn + xs + xw = 18 xl + xn + xs + xw + yl + yn + ys + yw = 60 400yl + 100yn + 175ys + 90yw ≤ $9,000 10 ≤ yl ≤ 25 5 ≤ yn ≤ 10 5 ≤ ys ≤ 10 5 ≤ yw ≤ 10 xl ≤ 6 xn ≤ 6 xs ≤ 6 xw ≤ 6 xi, yi, ≥ 0 Solution: xl = 6 xn = 0 xs = 6 xw = 6 yl = 14.44 yn = 10 ys = 7.56 yw = 10 Z = $15,600 Multiple optimal solutions exist. 56. (a) xij = amount (oz) of ingredient i in jar of j, where i = cabbage, tomato, onions and j = chow-chow, tomato maximize Z  2.25   1.95  =  ( xcc + xtc + xoc ) +   ( xct + xtt + xot ) 16    16  y2 = 1,747.126 Z = $14,201.64 58. (a) xi = no. of employees assigned to time period i, where i = 1,2,...,6 (time period 1 = 12:00 midnight –4:00 A.M.; period 2 = 4:00–8:00 A.M.; etc.) minimize Z = x1 + x2 + x3 + x4 + x5 + x6 subject to subject to xcc + xtc + xoc + xct + xtt + xot ≤ (700)(16) xcc ≥ .60 xcc + xtc + xoc xoc xtt ≥ .50 , ≥ .05 xcc + xtc + xoc xct + xtt + xot xoc xtc ≤ .10 , ≥ .10 xcc + xtc + xoc xcc + xtc + xoc xot xot ≤ .10 , ≥ .05 xct + xtt + xot xct + xtt + xot xcc + xct ≤ (3000)(16) xtc + xtt ≤ (350)(16) xoc + xot ≤ (30)(16) xcc + xtc + xoc xct ≥ 1.3, ≥ .10 xct + xtt + xot xot + xtt + xct xij ≥ 0 (b) chow-chow relish xcc = 4800 oz xtc = 2,688 oz 384 oz xoc = 7872 oz 480 jars Z = $1,313.66 x6 + x1 ≥ 90 x1 + x2 ≥ 215 x2 + x3 ≥ 250 x3 + x4 ≥ 65 x4 + x5 ≥ 300 x5 + x6 ≥ 125 xi ≥ 0 (b)x1 = 90 x2 = 250 x3 = 0 x4 = 175 x5 = 125 x6 = 0 Z = 640 59. (a) xij = consultant i hours assigned to project j; i = A, ... , F and j = 1, ..., 8 tomato relish xct = 192 oz xtt = 1632 oz 96 oz xot = 1920 oz 120 jars F i = A j=1 Subject to 8 ∑x subject to x1 ≤ 5,000 + 3y1 x2 ≤ 4,000 + 5y2 .60x1 + .85x2 + y1 + y2 ≤ $16,000 x1 ≥ .30(x1 + x2) x1 ≤ .60(x1 + x2) x1, x2, y1, y2 ≥ 0 (b)x1 = 5,458.128 x2 = 12,735.63 y1 = 152.709 ij ≤ available hours, i = A, …, F ij = project hours, j = 1, …, 8 j=1 F ∑x 57. (a) x1 = no. of jars of applesauce x2 = no. of bottles of apple juice y1 = $ amount spent on advertising applesauce y2 = $ amount spent on advertising apple juice maximize Z = .85x1 + .90x2 – y1 – y2 8 Minimize Z = ∑ ∑ (ranking) • x ij i=A F ∑ (hourly rate) • x ij ≤ Budget, j = 1, …, 8 i=A (b) Solution: xA7 = 290 xD8 = 129.7 xA8 = 70.3 xE2 = 240 xB1 = 219.7 xE3 = 400 xC1 = 110 xE6 = 70 xC6 = 390 xF4 = 475 xD1 = 170.3 xF5 = 350 Z = 12,130 (c) xA4 = 257.2 xE1 = 129.7 xA5 = 192.8 xE2 = 240 xB4 = 95 xE3 = 270 xC1 = 333.3 xE8 = 33.3 xC8 = 166.7 xF5 = 110 xD3 = 130 xF6 = 460 xD4 = 112.8 xF7 = 290 xD5 = 47.2 Z = $576,250 60. (a) x = full-time operators yi = part-time operators hired in week i, where i = 1,2,...8 1.1(x1 + x2 + x3) + 2.7y3 ≤ 200 1.1(x1 + x2 + x3 + x4) + 2.7y4 ≤ 200 1.1(x1 + x2 + x3 + x4 + x5) + 2.7y5 ≤ 200 1.1(x1 + x2 + x3 + x4 + x5 + x6) + 2.7y6 ≤ 200 1.1(x1 + x2 + x3 + x4 + x5 + x6 + x7) + 2.7y7 ≤ 200 1.1(x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8) + 2.7y8 ≤ 200 xi, yi ≥ 0 Solution: x1 = 0 x2 = 4 x3 = 18.4 x4 = 6.4 x5 = 24.8 8 Minimize Z = $4, 880 x + $450∑ yi i =1 subject to 360x + 270y1 = 19,500 360x + 270y2 = 21,000 360x + 270y3 = 25,600 360x + 270y4 = 27,200 360x + 270y5 = 33,400 360x + 270y6 = 29,800 360x + 270y7 = 27,000 360x + 270y8 = 31,000 1.1x + 2.7yi ≤ 200, i = 1,2,...,8 x, yi ≥ 0 Note: Objective function coefficient of $4,880 for x is computed as ($610/week)(8 weeks). (b)Solution x = 53.6 full-time operators y1 = 0.76 part-time operators y2 = 6.31 part-time operators y3 = 23.35 part-time operators y4 = 29.27 part-time operators y5 = 52.24 part-time operators y6 = 38.90 part-time operators y7 = 28.53 part-time operators y8 = 43.35 part-time operators Z = $361,788 61. Minimize Z = 4880x1 + 4270x2 + 3660x3 + 3050x4 + 2440x5 + 1830x6 + 1220x7 + 610x8 + 450 g yi subject to 360x1 + 270y1 = 19,500 360(x1 + x2) + 270y2 = 21,000 360(x1 + x2 + x3) + 270y3 = 25,600 360(x1 + x2 + x3 + x4) + 270y4 = 27,200 360(x1 + x2 + x3 + x4 + x5) + 270y5 = 33,400 360(x1 + x2 + x3 + x4 + x5 + x6) + 270y6 = 29,800 360(x1 + x2 + x3 + x4 + x5 + x6 + x7) + 270y7 = 27,000 360(x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8) + 270y8 = 31,000 1.1x1 + 2.7y1 ≤ 200 1.1(x1 + x2) + 2.7y2 ≤ 200 y1 = 72.22 y2 = 72.44 y3 = 64.95 y4 = 62.34 y5 = 52.24 y6 = 38.90 y7 = 28.53 y8 = 43.35 Z = $360,196 62. Z values: A = .9276, B = 1.000, C = 1.000, D = 1.000 Police station A is inefficient. 63. Minimize Z = 1x1D + 3x1E + 5x1F + 6x1G + 9x1H +10x1I + 12x1J + 1x2E + 3x2F + 4x2G + 7x2H + 8x2I + 10x2J + 2x3F + 3x3G + 6x3H + 7x3I + 9x3J + 1x4I + 3x4J + 1x5J + 6xA4 + 8xA5 +10xA6 + 11xA7 + 5xB4 + 7xB5 + 9xB6 + 10xB7 + 4xC4 + 6xC5 + 8xC6 + 9xC7 + 2xD4 + 4xD5 + 6xD6 + 7xD7 + 2xE5 + 4xE6 + 5xE7 + 2xF6 + 3xF7 + 1xG6 + 2xG7 subject to x1D + x1E + x1F + x1G + x1H + x1I + x1J ≤ 2 x2E + x2F + x2G + x2H + x2I + x2J ≤ 2 x3F + x3G + x3H + x3I + x3J ≤ 2 x4I + x4J ≤ 1 x5J ≤ 1 x A 4 + x A 5 + x A6 + x A 7 = 1 x B4 + x B 5 + x B6 + x B 7 = 1 xC 4 + xC 5 + xC 6 + xC 7 = 1 x D 4 + x D5 + x D 6 + x D 7 = 1 xE 5 + x E 6 + xE 7 ≤ 1 xF 6 + xF 7 ≤ 1 xG 6 + xG 7 ≤ 1 x1D + x D 4 + x D5 + xD 6 + x D 7 = 1 x1E + x2E + xE 5 + xE 6 + x E 7 = 1 x1F + x2F + x3F + x F 6 + xF 7 = 1 x1G + x2G + x3G + xG 6 + xG 7 = 1 x A4 + x B 4 + xC 4 + x D 4 + x4I + x4J = 1 x A5 + x B5 + xC 5 + x D5 + xE 5 + x5J = 1 x A6 + xB 6 + xC 6 + x D6 + x E 6 + xF 6 + xG 6 = 1 x A7 + xB 7 + xC 7 + x D 7 + x E 7 + xF 7 + xG 7 = 1 x1H + x2H + x3H = 1 x1I + x2I + x3I + x4I = 1 x1J + x2J + x3J + x4J + x5J = 1 xij ≥ 0 Solution: 1 – D (1 hr) and 1 – I (10 hr) 2 – E (1 hr) and 2 – H (7 hr) 3 – F (2 hr) and 3 – G (3 hr) 5 – J (1 hr) A – 7 (11 hr) B – 6 (9 hr) C – 4 (4 hr) x12 ≤ 60, 000 x13 ≤ 50, 000 x14 ≤ 55, 000 x15 ≤ 60, 000 x26 + x27 + x28 ≤ 50, 000 x36 + x37 + x38 ≤ 40, 000 x46 + x47 + x48 ≤ 46, 000 x56 + x57 + x58 ≤ 50, 000 Z = 49 hours (ground time) 7 crews originate at Pittsburgh; 3 in Orlando An extra crew ferries on flights 1, 2, and 3 from Pittsburgh. 64. xij = flow of product from node i to node j Maximize Z = .17(x26 + x27 + x28) + .20(x36 + x37 + x38) + .18(x46 + x47 + x48) + .16(x56 + x57 + x58) + .26(x69 + x610 + x611) + .29(x79 + x710 + x711) + .27(x89 + x810 + x811) + .12(x912) + .11(x1012) +.14(x1112) subject to x12 x13 x14 x15 = x26 + x27 + x28 = x36 + x37 + x38 = x46 + x47 + x48 = x56 + x57 + x58 .25x26 + .25x36 + .25x46 + .25x56 = x69 + x610 + x611 x26 = x36 x36 = x46 x46 = x56 .25x27 + .25x37 + .25x47 + .25x57 = x79 + x 710 + x711 x27 = x37 x37 = x47 x47 = x57 .25x28 + .25x38 + .25x48 + .25x58 = x89 + x810 + x811 x28 = x38 x38 = x48 x48 = x58 x69 + x79 + x89 = x912 x610 + x710 + x810 = x1012 x611 + x711 + x811 = x1112 x9112 + x1012 + x1112 = 37,000 x69 + x610 + x611 ≤ 12, 000 x79 + x710 + x711 ≤ 14, 000 x89 + x810 + x811 ≤ 19, 000 x912 ≤ 14, 000 x1012 ≤ 16, 000 x1112 ≤ 12, 000 x ij ≥ 0 solution: x12 = x13 = x14 = x15 = 37, 000 x26 = x36 = x46 = x56 = 12, 000 x27 = x37 = x47 = x57 = 6, 000 x28 = x38 = x48 = x58 = 19, 000 x69 = 5, 000 x79 = 6, 000 x89 = 3, 000 x810 = 16, 000 x611 = 7, 000 x912 = 14, 000 x1012 = 16, 000 x1112 = 7, 000 Z = $40, 680 CASE SOLUTION: SUMMER SPORTS CAMP AT STATE UNIVERSITY Model Formulation: wi = new sheets purchased in week i (i = 1,2,...8) xi = sheets cleaned at laundry at end of week i yi = sheets cleaned by Mary’s friends at end of week i minimize Z = 10(w1 + w2 + w3 + w4 + w5 + w6 + w7 + w8) + 4(x1 + x2 + x3 + x4 + x5 + x6) + 2(y1 + y2 + y3 + y4 + y5) subject to w1 = 115 x1 + y1 = 115 .06A1 + .13A2 + .05A3 + .10A4 ≤ 600 hrs. .06y1 + .13y2 + .05y3 + .10y4 ≤ 100 hrs. .05A1 + .21A2 + .02A3 + .10A4 ≤ 550 hrs. .05y1 + .21y2 + .02y3 + .10y4 ≤ 100 hrs. .03A1 + .15A2 + .04A3 + .15A4 ≤ 500 hrs. .03y1 + .15y2 + .04y3 + .15y4 ≤ 100 hrs. R1 + S1 + x1 = A1 + y1 R2 + S2 + x2 = A2+ y2 R3 + S3 + x3 = A3 + y3 R4 + S4 + x4 = A4 + y4 y1 + A1 = 1,800 y2 + A2 = 1,400 y3 + A3 = 1,600 y4 + A4 = 1,800 Ri, Si, xi, Ai, yi ≥ 0 w2 = 210 x2 + y2 = 210 w3 + .8x1 = 250 x3 + y3 = 250 w4 + .8x2 + .8y1 = 230 x4 + y4 = 230 w5 + .8x3 + .8y2 = 260 x5 + y5 = 260 w6 + .8x4 + .8y3 = 300 x6 = 300 w7 + .8x5 + .8y4 = 250 w8 + .8x6 +.8y5 ≥ 190 wi, xi, yi ≥ 0 Model Solution: w1 = 115 w2 = 210 w3 = 250 w4 = 138 w5 = 50 w6 = 0 w7 = 0 w8 = 0 Z = $11,940 x1 = 0 x2 = 0 x3 = 52.5 x4 = 177.5 x5 = 260 x6 = 300 y1 = 115 y2 = 210 y3 = 197.5 y4 = 52.5 y5 = 0 CASE SOLUTION: SPRING GARDEN TOOLS Model Formulation: Let i = 1 (trowel), 2 (hoe), 3 (rake), 4 (shovel) Ri = regular production of product i in stage 1 Si = subcontracted production of product i in stage 1 xi = overtime production of product i in stage 1 Ai = regular production of product i in stage 2 yi = overtime production of product i in stage 2 minimize Z = $6R1 + 10R2 + 8R3 + 10R4 + 7.2S1 + 12S2 + 9.6S3 + 12S4 + 6.2x1 + 10.7x2 +8.5x3 + 10.7x4 + 3A1 + 5A2 + 4A3 + 5A4 + 3.1y1 + 5.4y2 + 4.3y3 + 5.4y4 subject to .04R1 + .17R2 + .06R3 + .12R4 ≤ 500 hrs. .04x1 + .17x2 + .06x3 + .12x4 ≤ 100 hrs. .05R1 + .14R2 + .14R4 ≤ 400 hrs. .05x1 + .14x2 + .14x4 ≤ 100 hrs. 1.2R1 + 1.6R2 + 2.1R3 + 2.4R4 + 1.2x1 + 1.6x2 + 2.1x3 + 2.4x4 ≤ 10,000 ft2 Solution: R1 = 1,691.954 R2 = 1,319.54 R3 = 1,600 R4 = 933.33 A1 = 1,800 A2 = 1,084.849 A3 = 1,600 A4 = 1,461.818 x3 = x4 = 0 s1 = s2 = s3 = 0 s2 = 866.6667 y1 = 0 Z = $85,472.60 y2 = 315.1514 y3 = 0 y4 = 388.1822 x1 = 108.0457 y2 = 80.4599 CASE SOLUTION: SUSAN WONG’S PERSONAL BUDGETING MODEL (b)Let xij = amount invested for i months in month j where i = 1,3 and 7, and j = 1, 2, ..., 12. 12 12 12 j =1 j =1 j =1 Max Z = ∑ 0.005x1 j + ∑ 0.02 x3 j + ∑ 0.07 x7 j subject to Jan: –x11 – x31 – x71 + 2,450 + 3,800 = 2,750 Feb: x11 – x12 – x32 – x72 + 2,450 = 2,860 Mar: x12 – x13 – x33 – x73 + 2,450 = 2,335 Apr: x13 – x14 + x31 – x34 – x74 + 2,450 = 2,120 May: x14 – x15 + x32 – x35 – x75 + 2,450 = 2,205 June: x15 – x16 + x33 – x36 – x76 + 2,450 = 1,600 July: x16 – x17 + x34 – x37 – x77 + 2,450 = 3,050 Aug: x17 – x18 + x35 – x38 + x71 – x78 + 2,450 = 2,300 Sep: x18 – x19 + x36 – x39 + x72 – x79 + 2,450 = 1,975 Oct: x19 – x110 + x37 – x310 + x73 – x710 + 2,450 = 1,670 Nov: x110 – x111 + x38 – x311 + x74 – x711 + 2,450 = 2,710 Dec: x111 – x112 + x39 – x312 + x75 – x712 + 2,450 = 2,980 Investments (i = 1,3,7) Month ( j) 1-month 1. January 2. February 3. March 4. April 5. May 6. June 7. July 8. August 9. September 10. October 11. November 12. December x11 = 3500 3-month 7-month x72 = 3090 x73 = 115 x74 = 330 x75 = 245 x16 = 600 minimize Z = $850xnv + 720xnm + 910xnt + 750xni + 970xpv + 790xpm + 1,050xpt + 880xpi + 900xov + 830xom + 780xot + 820xoi + 2,100yjv + 2,350yjm + 2,200yjt + 1,900yji + 4,100ykv + 4,300ykm + 3,950ykt + 3,900yki + 2,600ylv + 2,300ylm + 2,500ylt + 2,800yli subject to x36 = 250 xnv + xnm + xnt + xni ≤ 1,400 xpv + xpm + xpt + xpi ≤ 1,100 xov + xom + xot + xoi ≤ 1,700 xnv + xpv + xov ≤ 1,200 xnm + xpm + xom ≤ 1,100 xnt + xpt + xot ≤ 1,400 xni + xpi + xoi ≤ 1,400 yjv + yjm + yjt + yji = 1,200 ykv + ykm + ykt + yki = 900 ylv + ylm + ylt + yli = 700 yjv + 2ykv + 1.5ylv = xnv + xpv + xov yjm + 2ykm + 1.5ylm = xnm + xpm + xom yjt + 2ykt + 1.5ylt = xnt + xpt + xot yji + 2yki + 1.5yli = xni + xpi + xoi xij, yij ≥ 0 x38 = 150 x39 = 3815 x110 = 895 x111 = 1115 x712 = 4645 Z = $704.60 earned in interest payments (b)Using sensitivity analysis for the January constraint, the lower range for the right hand side is –410. Thus, Susan needs $710 out of her original $3,800 to make the model feasible (i.e., avoid an infeasible solution). CASE SOLUTION: WALSH’S JUICE COMPANY xij = tons of unprocessed grape juice transported from vineyard i to plant j where i = n (New York), p (Pennsylvania), o (Ohio), and j = v (Virginia), m (Michigan), t (Tennessee), i (Indiana). yij = tons of grape juice processed into product i at plant j where i = j (juice), k (concentrate), l (jelly) Solution: xni = 1400 xpm = 1100 xov = 150 xot = 1400 Z = $10,606,000 yji = 1200 ykv = 75 ykm = 25 ykt = 700 yki = 100 ylm = 700