数据、模型与决策（第12版）课件 第4章线性规划建模实例

LinearProgramming:ModelingExamplesChapter4Copyright©2016PearsonEducation,Inc.ChapterTopicsAProductMixExampleADietExampleAnInvestmentExampleAMarketingExampleATransportationExampleABlendExampleAMultiperiodSchedulingExampleADataEnvelopmentAnalysisExampleCopyright©2016PearsonEducation,Inc.AProductMixExampleProblemDefinition(1of8)Four-productT-shirt/sweatshirtmanufacturingcompany.Mustcompleteproductionwithin72hoursTruckcapacity=1,200standardsizedboxes.Standardsizeboxholds12T-shirts.One-dozensweatshirtsboxisthreetimessizeofstandardbox.$25,000availableforaproductionrun.500dozenblankT-shirtsandsweatshirtsinstock.Howmanydozens(boxes)ofeachtypeofshirttoproduce?Copyright©2016PearsonEducation,Inc.AProductMixExample(2of8)Figure4.1Quick-ScreenShirtsCopyright©2016PearsonEducation,Inc.AProductMixExampleData(3of8)Resourcerequirementsfortheproductmixexample.Copyright©2016PearsonEducation,Inc.DecisionVariables: x1=sweatshirts,frontprinting x2=sweatshirts,backandfrontprinting x3=T-shirts,frontprinting x4=T-shirts,backandfrontprintingObjectiveFunction:

MaximizeZ=$90x1+$125x2+$45x3+$65x4ModelConstraints:

0.10x1+0.25x2+0.08x3+0.21x4

72hr 3x1+3x2+x3+x4

1,200boxes $36x1+$48x2+$25x3+$35x4

$25,000 x1+x2

500dozensweatshirts x3+x4

500dozenT-shirts

AProductMixExampleModelConstruction(4of8)Copyright©2016PearsonEducation,Inc.AProductMixExampleComputerSolutionwithExcel(5of8)Exhibit4.1ObjectivefunctionClickon“Data”tabtoaccessSolver=D7*B14+E7*B15+F7*B16+G7*B17=J7-H7Thesecellshavenoeffect;addedfor“cosmetic”purposes.ModelformulationincludedonallExcelfilesonCompanionWebsite=F11*B16+G11*B17Copyright©2016PearsonEducation,Inc.Exhibit4.2AProductMixExampleSolutionwithExcelSolverWindow(6of8)Includesallfiveconstraints.Copyright©2016PearsonEducation,Inc.Exhibit4.3AProductMixExampleSolutionwithQMforWindows(7of8)Modelsolutionis:x1=175.56boxesoffront-onlysweatshirtsx2=57.78boxesoffrontandbacksweatshirtsx3=500boxesoffront-onlyt-shirtsZ=$45,522.22profitCopyright©2016PearsonEducation,Inc.Exhibit4.4AProductMixExampleSolutionwithQMforWindows(8of8)Copyright©2016PearsonEducation,Inc.Breakfasttoincludeatleast420calories,5milligramsofiron,400milligramsofcalcium,20gramsofprotein,12gramsoffiber,andmusthavenomorethan20gramsoffatand30milligramsofcholesterol.ADietExampleDataandProblemDefinition(1of5)Copyright©2016PearsonEducation,Inc.

x1=cupsofbrancerealx2=cupsofdrycerealx3=cupsofoatmealx4=cupsofoatbranx5=eggsx6=slicesofbaconx7=orangesx8=cupsofmilkx9=cupsoforangejuicex10=slicesofwheattoastADietExampleModelConstruction–DecisionVariables(2of5)Copyright©2016PearsonEducation,Inc.Minimize Z=0.18x1+0.22x2+0.10x3+0.12x4+0.10x5+0.09x6 +0.40x7+0.16x8+0.50x9+0.07x10subjectto: 90x1+110x2+100x3+90x4+75x5+35x6+65x7

+100x8+120x9+65x10

420calories 2x2+2x3+2x4+5x5+3x6+4x8+x10

20gfat 270x5+8x6+12x8

30mgcholesterol 6x1+4x2+2x3+3x4+x5+x7+x10

5mgiron 20x1+48x2+12x3+8x4+30x5+52x7+250x8

+3x9+26x10

400mgofcalcium 3x1+4x2+5x3+6x4+7x5+2x6+x7 +9x8+x9+3x10

20gprotein 5x1+2x2+3x3+4x4+x7+3x10

12 xi

0,foralljADietExampleModelSummary(3of5)Copyright©2016PearsonEducation,Inc.Exhibit4.5ADietExampleComputerSolutionwithExcel(4of5)Decisionvariable,C5:C14=SUMPRODUCT(C5:C14,F5:F14)or=C5*F5+C6*F6+C7*F7+C8*F8+C9*F9+C10*F10+C11*F11+C12*F12+C13*F13+C14*F14Constraintvalue,420,typedincellF17=SUMPRODUCT(C5:C14,E5:E14)or=C5*E5+C6*E6+C7*E7+C8*E8+C9*E9+C10*E10+C11*E11+C12*E12+C13*E13+C14*E14Copyright©2016PearsonEducation,Inc.Exhibit4.6ADietExampleSolutionwithExcelSolverWindow(5of5)Decisionvariables;“servings”incolumnCConstraintfor“calories”incolumnF;SUMPRODUCT(C5:C14,F5:F14)<420Copyright©2016PearsonEducation,Inc.Aninvestorhas$70,000todivideamongseveralinstruments.Municipalbondshavean8.5%return,CD’sa5%return,t-billsa6.5%return,andgrowthstock13%.Thefollowingguidelineshavebeenestablished:Nomorethan20%inmunicipalbondsInvestmentinCDsshouldnotexceedtheotherthreealternativesAtleast30%investedintreasurybillsandCDsMoreshouldbeinvestedinCDsandtreasurybillsthaninmunicipalbondsandgrowthstocksbyaratioof1.2to1All$70,000shouldbeinvested.AnInvestmentExampleModelSummary(1of5)Copyright©2016PearsonEducation,Inc.MaximizeZ=$0.085x1+0.05x2+0.065x3+0.130x4subjectto: x1

$14,000x2-x1-x3-x4

0x2+x3

$21,000-1.2x1+x2+x3-1.2x4

0x1+x2+x3+x4=$70,000x1,x2,x3,x4

0wherex1=amount($)investedinmunicipalbondsx2=amount($)investedincertificatesofdepositx3=amount($)investedintreasurybillsx4=amount($)investedingrowthstockfundAnInvestmentExampleModelSummary(2of5)Copyright©2016PearsonEducation,Inc.AnInvestmentExampleComputerSolutionwithExcel(3of5)Exhibit4.7Totalinvestmentrequirement,=D10*B13+E10*B14+F10*B15+G10*B16Firstguideline,=D6*B13Objectivefunction,Z,fortotalreturnCopyright©2016PearsonEducation,Inc.Exhibit4.8AnInvestmentExampleSolutionwithExcelSolverWindow(3of4)GuidelineconstraintsCopyright©2016PearsonEducation,Inc.AnInvestmentExampleSensitivityReport(4of4)Exhibit4.9ShadowpricefortheamountavailabletoinvestCopyright©2016PearsonEducation,Inc.

Budgetlimit$100,000TelevisiontimeforfourcommercialsRadiotimefor10commercialsNewspaperspacefor7adsResourcesfornomorethan15commercialsand/oradsAMarketingExampleDataandProblemDefinition(1of7)Copyright©2016PearsonEducation,Inc.MaximizeZ=20,000x1+12,000x2+9,000x3subjectto: 15,000x1+6,000x2+4,000x3

100,000 x1

4x2

10x3

7x1+x2+x3

15x1,x2,x3

0wherex1=numberoftelevisioncommercialsx2=numberofradiocommercialsx3=numberofnewspaperadsAMarketingExampleModelSummary(2of7)Copyright©2016PearsonEducation,Inc.Exhibit4.10AMarketingExampleSolutionwithExcel(3of7)Objectivefunction=F6*D6+F7*D7+F8*D8or=SUMPRODUCT(D6:D8,F6:F8)Copyright©2016PearsonEducation,Inc.Exhibit4.11AMarketingExampleSolutionwithExcelSolverWindow(4of7)IncludesallfiveconstraintsCopyright©2016PearsonEducation,Inc.AMarketingExampleIntegerSolutionwithExcel(5of7)Exhibit4.12DecisionvariablesClickon“int”forinteger.Copyright©2016PearsonEducation,Inc.Exhibit4.13AMarketingExampleIntegerSolutionwithExcel(6of7)IntegerrestrictionCopyright©2016PearsonEducation,Inc.Exhibit4.14AMarketingExampleInteger

SolutionwithExcel(7of7)IntegersolutionBettersolution—17,000moretotalexposures—thanrounded-downsolutionCopyright©2016PearsonEducation,Inc.Warehousesupplyof RetailstoredemandTelevisionSets: fortelevisionsets:

1-Cincinnati300 A-NewYork 1502-Atlanta200 B-Dallas 2503-Pittsburgh200

C-Detroit 200Total700 Total 600ATransportationExampleProblemDefinitionandData(1of3)Copyright©2016PearsonEducation,Inc.MinimizeZ=$16x1A+18x1B+11x1C+14x2A+12x2B+13x2C+ 13x3A+15x3B+17x3C

subjectto:

x1A+x1B+x1C

300 x2A+x2B+x2C

200 x3A+x3B+x3C

200 x1A+x2A+x3A=150 x1B+x2B+x3B=250 x1C+x2C+x3C

=200Allxij

0ATransportationExampleModelSummary(2of4)Copyright©2016PearsonEducation,Inc.Exhibit4.15ATransportationExampleSolutionwithExcel(3of4)=C5+C6+C7=C5+D5+E5Copyright©2016PearsonEducation,Inc.Exhibit4.16ATransportationExampleSolutionwithSolverWindow(4of4)DecisionvariablesSupplyconstraintsDemandconstraintsCopyright©2016PearsonEducation,Inc.ABlendExampleProblemDefinitionandData(1of7)Copyright©2016PearsonEducation,Inc.Determinetheoptimalmixofthethreecomponentsineachgradeofmotoroilthatwillmaximizeprofit.Companywantstoproduceatleast3,000barrelsofeachgradeofmotoroil.Decisionvariables:Thequantityofeachofthethreecomponentsusedineachgradeofgasoline(9decisionvariables);xij=barrelsofcomponentiusedinmotoroilgradejperday,wherei=1,2,3andj=s(super),p(premium),ande(extra).ABlendExampleProblemStatementandVariables(2of7)Blendspecificationconstraintforsuper,whichmustcontain50%ofcomponent1.Copyright©2016PearsonEducation,Inc.ABlendExampleProblemStatementandVariables(3of7)Converttostandardform,alinearfunctionontheleftsideandnumericvalueontheright.MultiplybothsidesbythedenominatorandcollecttermsCopyright©2016PearsonEducation,Inc.MaximizeZ=11x1s+13x2s+9x3s+8x1p+10x2p+6x3p+6x1e +8x2e+4x3esubjectto:x1s+x1p+x1e

4,500bbl.x2s+x2p+x2e

2,700bbl.x3s+x3p+x3e

3,500bbl.0.50x1s-0.50x2s-0.50x3s

00.70x2s-0.30x1s-0.30x3s

00.60x1p-0.40x2p-0.40x3p

00.75x3p-0.25x1p-0.25x2p

00.40x1e-0.60x2e--0.60x3e

00.90x2e-0.10x1e-0.10x3e

0x1s+x2s+x3s

3,000bbl.x1p+x2p+x3p

3,000bbl.x1e+x2e+x3e

3,000bbl.ABlendExampleModelSummary(4of7)allxij

0Copyright©2016PearsonEducation,Inc.Exhibit4.17ABlendExampleSolutionwithExcel(5of7)=B7+B10+B13Decisionvariables-B7:B15=B7+B8+B9=0.5*B7-0.5*B8-0.5*B9Copyright©2016PearsonEducation,Inc.Exhibit4.18ABlendExampleSolutionwithSolverWindow(6of7)Copyright©2016PearsonEducation,Inc.ABlendExampleSensitivityReport(7of7)Exhibit4.19Theshadowpriceforcomponent1is$20.Theupperlimitforthesensitivityrangeforcomponent1is4500+1700=6200.Copyright©2016PearsonEducation,Inc.ProductionCapacity:160computersperweek 50morecomputerswithovertimeAssemblyCosts:$190percomputerregulartime; $260percomputerovertimeInventoryHoldingCost:$10/computerperweekOrderschedule:AMultiperiodSchedulingExampleProblemDefinitionandData(1of5)Copyright©2016PearsonEducation,Inc.DecisionVariables: rj=regularproductionofcomputersinweekj (j=1,2,…,6) oj=overtimeproductionofcomputersinweekj (j=1,2,…,6) ij=extracomputerscarriedoverasinventoryinweekj (j=1,2,…,5)AMulti-PeriodSchedulingExampleDecisionVariables(2of5)Copyright©2016PearsonEducation,Inc.Modelsummary:

MinimizeZ=$190(r1+r2+r3+r4+r5+r6)+$260(o1+o2 +o3+o4+o5+o6)+10(i1+i2+i3+i4+i5) subjectto: rj

160computersinweekj(j=1,2,3,4,5,6) oj

150computersinweekj(j=1,2,3,4,5,6) r1+o1-i1

=105 week1 r2+o2+i1-i2

=170 week2 r3+o3+i2-i3

=230 week3 r4+o4+i3-i4

=180 week4 r5+o5+i4-i5

=150 week5 r6+o6+i5

=250 week6 rj,oj,ij

0AMulti-PeriodSchedulingExampleModelSummary(3of5)Copyright©2016PearsonEducation,Inc.AMulti-PeriodSchedulingExampleSolutionwithExcel(4of5)Exhibit4.20Decisionvariablesforregularproduction–B6:B11Decisionvariablesforovertimeproduction–D6:D11B7+D7+I6;regularproduction+overtimeproduction+inventoryfrompreviousweekG7-H7Copyright©2016PearsonEducation,Inc.Exhibit4.21AMulti-PeriodSchedulingExampleSolutionwithSolverWindow(5of5)Copyright©2016PearsonEducation,Inc.DEAcomparesanumberofserviceunitsofthesametypebasedontheirinputs(resources)andoutputs.Theresultindicatesifaparticularunitislessproductive,orefficient,thanotherunits.Elementaryschoolcomparison: Input1=teachertostudentratio Input2=supplementaryfunds/student Input3=averageeducationallevelofparents Output1=averagereadingSOLscore Output2=averagemathSOLscore Output3=averagehistorySOLscoreADataEnvelopmentAnalysis(DEA)ExampleProblemDefinition(1of5)Copyright©2016PearsonEducation,Inc.ADataEnvelopmentAnalysis(DEA)ExampleProblemDataSummary(2of5)Copyright©2016PearsonEducation,Inc.DecisionVariables: xi=apriceperunitofeachoutputwherei=1,2,3 yi=apriceperunitofeachinputwherei=1,2,3ModelSummary: MaximizeZ=81x1+73x2+69x3 subjectto: .06y1+460y2+13.1y3=1 86x1+75x2+71x3

.06y1+260y2+11.3y3

82x1+72x2+67x3

.05y1+320y2+10.5y3

81x1+79x2+80x3

.08y1+340y2+12.0y3

81x1+73x2+69x3

.06y1+460y2+13.1y3xi,yi

0ADataEnvelopmentAnalysis(DEA)ExampleDecisionVariablesandModelSummary(3of5)Copyright©2016PearsonEducation,Inc.Exhibit4.22ADataEnvelopmentAnalysis(DEA)ExampleSolutionwithExcel(4of5)Valueofoutputs,alsoincellH8=B5*B12+C5*B13+D5*B14=E8*D12+F8*D13+G8*D14Copyright©2016PearsonEducation,Inc.Exhibit4.23ADataEnvelopmentAnalysis(DEA)ExampleSolutionwithSolverWindow(5of5)ScalingconstraintConstraintforoutputs<inputsCopyright©2016PearsonEducation,Inc.ExampleProblemSolutionProblemStatementandData(1of5)Cannedcatfood,MeowChow;dogfood,BowChow.Ingredients/week:600lb.horsemeat;800lb.fish;1000lb.cereal.Reciperequirement:MeowChowatleasthalffish BowChowatleasthalfhorsemeat.2,250sixteen-ouncecansavailableeachweek.Profit/can:MeowChow$0.80 BowChow$0.96.

HowmanycansofBowChowandMeowChowshouldbeproducedeachweekinordertomaximizeprofit?Copyright©2016PearsonEducation,Inc.Step1:DefinetheDecisionVariablesxij=ouncesofingredientiinpetfoodjperweek, wherei=h(horsemeat),f(fish)andc(cereal), andj=m(Meowchow)andb(BowChow).Step2:FormulatetheObjectiveFunctionMaximizeZ=$0.05(xhm+xfm+xcm)+0.06(xhb+xfb+xcb)ExampleProblemSolutionModelFormulation(2of5)Copyright©2016PearsonEducation,Inc.Step3:FormulatetheModelConstraintsAmountofeachingredientavailableeachweek: xhm+xhb

9,600ounc