Chapter Four: Linear Programming: Modeling Examples

1 40 PROBLEM SUMMARY1. Product mix example2. Diet example3. Investment example4. Marketing example5. Transportation example6. Blend mix (maximization) analysis (4 7) (minimization) mix (minimization) mix (maximization) mix (maximization) mix (maximization) mix (minimization) (maximization) mix (maximization) mix (minimization) distribution (maximization) allocation (maximization) (minimization), sensitivity (maximization) (minimization) scheduling (minimization) busing (minimization) analysis (4 24) mixture (minimization) scheduling (maximization) mixture (maximization) poly mix (maximization) mix (maximization) mix (minimization), sensitivity analysisChapter Four: Linear Programming: Modeling (maximization) borrowing (minimization) production scheduling(minimization) (maximization), sensitivity (minimization), sensitivity (minimization) (minimization) line scheduling (maximization) flow (minimization) admissions (maximization) (maximization) loss (minimization) investment (maximization) sales and inventory (maximization) production and inventory(minimization) assignment (maximization) envelopment envelopment flow (maximization) workforce planning (minimization) solution (4 43) scheduling (maximization), storage (maximization) scheduling (maximization) mix (maximization) mix/advertising (maximization) (minimization) purchasing/leasing (minimization) workforce planning (minimization)

2 Workforce (4 50) envelopment crew scheduling (maximization) project assignment (minimization) admissions (maximization) flow/scheduling (minimization)PROBLEM the profit values would change, the shadow prices would no longer be , the sensitivity analysis provided in thecomputer output does not provide ranges forconstraint parameter changes. Thus, the modelwould have to be reformulated model would have unit costs increased by 10 percent. This same amountwould be subtracted from unit profits. Theindividual processing times would be reducedby 10 percent. This would result in a new,lower solution of $43,310. Thus, the suggestedalternative should not be not. The t-shirts are a variable cost and any additional t-shirts purchased by Quik-Screen would likely reduce unit profit, whichwould change the current shadow price forblank t-shirts.

3 The shadow price is effectiveonly if the profit is based on costs that would beincurred without regard to the acquisition ofadditional new requirement is that,x1= x2= x3= x4 This can be achieved within the model by creating three additional constraints,x1= x2x1= x3x1= x4If x1equals x2,x3and x4then x2,x3and x4must also equal each other. These constraints arechanged to,x1 x2= 0x1 x3= 0x1 x4= 0 The new solution is x1= x2= x3=x4= a minimum of 500 calories, the three food items remain the same, however the amount ofeach and the total cost increases:x3= of oatmeal,x8= cups of milk,x10= slices of toast, and Z= $ a minimum of 600 calories, the fooditems change to x3= cups of oatmeal cups of milk and Z= $ A change ofvariables would be expected given that 600calories is greater than the upper limit of thesensitivity range for different combinations of maximum servings of each of the 10 food items could beused.

4 As an example limiting the four hot andcold cereals,x1,x2,x3and x4to four cups, eggsto three, bacon to three slices, oranges to two,milk to two cups, orange juice to four cups andwheat toast to four slices results in thefollowing solution:x3= 2 cups of oatmealx4= cups of oat branx5= .065 eggsx8= cups of milkx10= 4 slices of wheat toastZ= $ limiting the servings of the four hot and cold cereals to two cups,x1+ x2+ x3+ x4 2,results in the following solution:x3= 2 cups of oatmealx6= .750 slices of baconx8= 2 cups of milkx9= .115 cups of orange juicex10= 4 slices of wheat toastZ= $ would have no effect; the entire $70,000 would be invested the upper limit of the sensitivity range forthe investment amount is unlimited, anincrease of $10,000 will not affect the shadowprice, which is $ Thus, the total increasein return will be $740 ( , $10,000.)

5 074 =$740).No, the entire amount will not be invested in one alternative. The new solution is x1= $22, ,x3= $43, , and x4= $14, shadow price is , thus for every $1 increase in budget, up to the sensitivity rangeupper limit of $14,000, audience exposure willincrease by The total audience increasefor a $20,000 budget increase is 20, new requirement results in two new model constraints,20,000x1= 12,000x220,000x1= 9,000x3or,20,000 12,000x2= 020,000x1 9,000x3= 0 The new solution is x1= ,x2= ,x3= and Z= 184,090. This results inapproximately 61,362 exposures per type ofadvertising (with some slight differences due tocomputer rounding). slack variables for the three warehouse constraints would be added to the constraints asfollows,x1A+ x1B+ x1C+ s1= 300x2A+ x2B+ x2C+ s2= 200x3A+ x3B+ x3C+ s3= 200 These three slacks would then be added to the objective function with the storage costcoefficients of $9 for s1, $6 for s2and $7 for change would not result in a new model must be reformulated with three new variables reflecting the shipments from thenew warehouse at Memphis (4) to the threestores,x4A,x4B, and x4C.

6 These variables mustbe included in the objective function with thecost coefficients of $18, 9 and 12 new supply constraint must be added,x4A+ x4B+ x4C 200 The solution to this reformulated model is,x1C= 200x2B= 50x3A= 150x4B= 200Z= 6,550 Yes, the warehouse should be shadow price for the Atlanta warehouse shows the greatest decrease in cost, $6 forevery additional set supplied from this , the upper limit of the sensitivityrange is 200, the same as the current supplyvalue. Thus, if the supply is increased atAtlanta by even one television set the shadowprice will change would not affect the solution at all since there is no surplus with any of the 1 has the greatest dual price of $20. For each barrel of component 1 the companycan acquire, profit will increase by $20, up tothe limit of the sensitivity range which is anincrease of 1,700 bbls.

7 Or 6,200 total bbls. ofcomponent 1. For example an increase of onebbl. of component 1 from 4,500 to 4,501 resultsin a increase in total cost to $76, (a)maximize Z= $190x1+ 170x2+ 155x3subject + + + + 24040x1+ 55x2+ 20x3 6,500x1,x2,x3 0(b)x1= ,x2= 0,x3= ,Z= $27, s2= 0,s3= 2, (a)It would not affect the model. The slack apples are multiplied by the revenue per apple of $.08to determine the extra total revenue, ,(2, )($.08) = $ (b)This change requires a new variable,x4, and that the constraint for apples be changed from to =. No, the Friendly s should not producecider. The new solution would be x1= 135,x2= 0,x3= 0,x4= and Z= $26, reduction in profit occurs because therequirement that all 6,500 apples be usedforces resources to be used for cider that wouldbe more profitable to be used to produce theother products.

8 If the final model constraint forapples is, rather than =, the previous solutionin 1(b) (a)x1= no. of eggsx2= no. of bacon stripsx3= no. of cups of cerealminimize Z= 4x1+ 3x2+ 2x3subject to2x1+ 4x2+ x3 163x1+ 2x2+ x3 12x1,x2,x3 0(b)x1= 2x2= 3Z= $ (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,00043or,10,500x1+ 9,500x2+ 12,300x3= 2,800,000minimize Z= 12,500x1+ 8,500x2+ 13,700x3subject to10,500x1+ 9,500x2+ 12,300x3= 2,800,000x1 70x2 50x3 50x1 120x2 120x3 120x1,x2,x3 0(b)x1= $2,925, (a) x1= no. of clocksx2= no. of radiosx3= no. of toastersmaximize Z= 8x1+ 10x2+ 7x3subject to7x1+ 10x2+ 5x3 2,0002x1+ 3x2+ 2x3 660x1 200x2 300x3 150x1,x2,x3 0(b)x1= $2, (a) x1= no.

9 Of gallons of Yodelx2= no. of gallons of Shotzx3= no. of gallons of Rainwatermaximize Z= + + tox1+ x2+ x3= 1, + .90x2+ .50x3 2,000x1 400x2 500x3 300x1,x2,x3 0(b)x1= 400x2= 500x3= 100Z= $1, (a) x1= no. of lb of Super Two at Fresnox2= no. of lb of Super Two at Dearbornx3= no. of lb of Green Grow at Fresnox4= no. of lb of Green Grow at Dearbornmaximize Z= 7x1+ 5x2+ 5x3+ 4x4subject to2x1+ 4x2+ 2x3+ 3x4 45,000x1+ x2 6,000x3+ x4 7,000x1+ x3 5,000x2+ x4 6,000x1,x2,x3,x4 0(b)x1= 5,000x2= 1,000x4= 5,000Z= $60,00014. (a) xi= ore i(i= 1,2,3,4,5,6)minimize Z= 27x1+ 25x2+ 32x3+ 22x4+ 20x5+ 24x6subject + .43x2+ .17x3+ .20x4+.12x6 . + .10x2+ .12x4+ .24x5+ .18x6 . + .25x2+ .10x5+ .16x6 . + .07x2+ .53x3+ .18x4+ + .25x6 . + .07x2+ .53x3+ .18x4+ .31x5+ .25x6 . +.

10 85x2+ .70x3+ .50x4+ .65x5+ .71x6= (b)x2= .1153 ton ore 2x3= .8487 ton ore 3x4= .0806 ton ore 4x5= .4116 ton ore 5Z= $ (a) xij= number of trucks assigned to route from warehouse ito terminal j, where i= 1(Charlotte), 2 (Memphis), 3 (Louisville) and j = a (St. Louis), b (Atlanta), c (New York)maximize Z= + 2,100x1b+ 1,600x1c+ 1,000x2a+ 700x2b+ 900x2c+ 1,400x3a+ 800x3b+ 2,200x3csubject tox1a+ x1b+ x1c= 30x2a+ x2b+ x2c= 30x3a+ x3b+ x3c= 30x1a+ x2a+ x3a 40x1b+ x2b+ x3b 60x1c+ x2c+ x3c 50xij 044(b)x1b= 30x2a= 30x3c= 30Z= $159,00016. (a)x1= no. of sofasx2= no. of tablesx3= no. of chairsmaximize Z= 400x1+ 275x2+ 190x3subject to7x1+ 5x2+ 4x3 2,25012x1+ 7x3 1,0006x1+ 9x2+ 5x3 240x1+ x2+ x3 650x1,x2,x3 0(b)x1= 40Z= $16,00017. (a)xij= lbs. of seed iused in mix j, where i= t (tall fescue), m (mustang fescue), b (bluegrass)and j= 1,2, Z= (xt1+ xt2+ xt3) + (xm1+ xm2+ xm3) + (xb1+ xb2+ xb3)subject.