Chapter 2. Linear Programming: Basic Concepts第二章第二章. . 线性规划线性规划: : 基本概念基本概念运筹学运筹学Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学2ThreeClassicApplicationsofLP(Section2.1)(线性规划的三个经典应用线性规划的三个经典应用第第2.1节节)TheWyndorGlassCompanyProductMixProblem(Section2.2)(伟恩德玻璃制品公司产品伟恩德玻璃制品公司产品组合问题组合问题第第2.2节节)FormulatingtheWyndorProblemonaSpreadsheet(Section2.3)(在电子表格上建立韦在电子表格上建立韦恩德公司问题的模型恩德公司问题的模型第第2.3节节)TheAlgebraicModelforWyndor(Section2.4)(韦恩德公司问题的数学模型韦恩德公司问题的数学模型第第2.4节节)Table of Contents (主要内容主要内容)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学3TheGraphicalMethodAppliedtotheWyndorProblem(Section2.5)(韦恩德公司问题的图形方韦恩德公司问题的图形方法法第第2.5节节)UsingtheExcelSolverwiththeWyndorProblem(Section2.6)(使用使用ExcelSolver解决韦恩德公司解决韦恩德公司问题问题第第2.6节节)AMinimizationExampleTheProfit&GambitCo.(Section2.7)(一个最小化的例子一个最小化的例子利博公利博公司广告组合问题司广告组合问题第第2.7节节)Table of Contents (主要内容主要内容)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学4Three Classic Applications of LPProductMixatPonderosaIndustrial(潘得潘得罗索工业公司的产品组合问题罗索工业公司的产品组合问题)lConsideredlimitedresources,anddeterminedoptimalmixofplywoodproducts.(考虑了有限资源，并确定了胶合考虑了有限资源，并确定了胶合板产品的最优组合板产品的最优组合)lIncreasedoverallprofitabilityofcompanyby20%.(公司的总利润增加了公司的总利润增加了20%)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学5Three Classic Applications of LPPersonnelSchedulingatUnitedAirlines(联合航空公司的员工排程联合航空公司的员工排程)lDesignedworkschedulesforallemployeesatalocationtomeetservicerequirementsmostefficiently.(在每个地点为所有员工设在每个地点为所有员工设计工作排程以最有效地满足服务需求计工作排程以最有效地满足服务需求)lSaved$6millionannually.(每年可节约每年可节约600万美元万美元)线性规划线性规划太有用了！太有用了！Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学6PlanningSupply,Distribution,andMarketingatCitgoPetroleumCorporation(Citgo石油公石油公司的供应、配送和营销计划司的供应、配送和营销计划)lTheSDMsystemusesLPtocoordinatethesupply,distribution,andmarketingofeachofCitgosmajorproductsthroughouttheUnitedStates.(SDM系统使用系统使用LP来协调全美来协调全美Citgo石油石油公司主要产品的供应、配送和营销公司主要产品的供应、配送和营销)lTheresultingreductionininventoryadded$14millionannuallytoCitgosprofits.(库存成本的库存成本的下降每年为公司增加下降每年为公司增加1400万美元的收入万美元的收入)Three Classic Applications of LPCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学7Wyndorhasdevelopedthefollowingnewproducts(韦恩德公司开发了下列新产品韦恩德公司开发了下列新产品):lAn8-footglassdoorwithaluminumframing.(8英尺的英尺的铝框玻璃门铝框玻璃门)lA4-footby6-footdouble-hung,wood-framedwindow.(4英尺英尺*6英尺的双把木框门英尺的双把木框门)Thecompanyhasthreeplants(公司有三个工厂公司有三个工厂)lPlant1producesaluminumframesandhardware.(工厂工厂1生产铝框和五金件生产铝框和五金件)lPlant2produceswoodframes.(工厂工厂2生产木框生产木框)lPlant3producesglassandassemblesthewindowsanddoors.(工厂工厂3生产玻璃并组装窗和门生产玻璃并组装窗和门)Wyndor Glass Co. Product Mix ProblemCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学8Wyndor Glass Co. Product Mix ProblemShouldtheygoaheadwithlaunchingthesetwonewproducts?Ifso,whatshouldbetheproduct mix?公司是否应该生产这公司是否应该生产这两个新产品？如果生两个新产品？如果生产，两个新产品的生产，两个新产品的生产组合如何？产组合如何？Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学9DevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Step#1:DataCells(第一步第一步:数据单元格数据单元格)lEnterallofthedatafortheproblemonthespreadsheet.(在电子表格中输入问题的所有在电子表格中输入问题的所有数据数据)lMakeconsistentuseofrowsandcolumns.(有有效利用行和列效利用行和列)lItisagoodideatocolorcodethese“datacells”(e.g.,lightblue).(为这些数据单元格标为这些数据单元格标上颜色便于区分和建模上颜色便于区分和建模)Wyndor Glass Co. Product Mix ProblemCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学10Wyndor Glass Co. Product Mix ProblemDevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学11Step#2:ChangingCells(第二步第二步:可变单元格可变单元格)lAddacellinthespreadsheetforeverydecisionthatneedstobemade.(在电子表格中为每一决策添加一在电子表格中为每一决策添加一个单元格个单元格)lIfyoudonthaveanyparticularinitialvalues,justenter0ineach.(如果没有任何初始值，输入如果没有任何初始值，输入0即可即可)lItisagoodideatocolorcodethese“changingcells”(e.g.,yellowwithborder).(为这些可变单元格标上颜为这些可变单元格标上颜色便于区分和建模色便于区分和建模)DevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Wyndor Glass Co. Product Mix ProblemCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学12DevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Wyndor Glass Co. Product Mix Problem41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学13DevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Wyndor Glass Co. Product Mix ProblemStep#3:TargetCell(第三步第三步:目标单元格目标单元格)lDevelopanequationthatdefinestheobjectiveofthemodel.(建立定义模型目标的方程式建立定义模型目标的方程式)lTypicallythisequationinvolvesthedatacellsandthechangingcellsinordertodetermineaquantityofinterest(e.g.,totalprofitortotalcost).(典型地，这典型地，这个方程式包含了数据单元格和可变单元格的数据，个方程式包含了数据单元格和可变单元格的数据，以确定有关的数量值，如总利润和总成本以确定有关的数量值，如总利润和总成本)lItisagoodideatocolorcodethiscell(e.g.,orangewithheavyborder).(给目标单元格标记颜色给目标单元格标记颜色)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学14Wyndor Glass Co. Product Mix ProblemDevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学15DevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)Step#4:Constraints(约束约束)lForanyresourcethatisrestricted,calculatetheamountofthatresourceusedinacellonthespreadsheet(anoutputcell).(对所有有限资源，在电对所有有限资源，在电子表格的输出单元格中计算出资源的使用量子表格的输出单元格中计算出资源的使用量)lDefinetheconstraintinthreeconsecutivecells.Forexample,ifQuantityAQuantityB,putthesethreeitems(QuantityA,QuantityB)inconsecutivecells.(在三个连续的单元格中定义约束在三个连续的单元格中定义约束)Wyndor Glass Co. Product Mix ProblemCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学16Wyndor Glass Co. Product Mix ProblemDevelopingaSpreadsheetModel(建立电子表格模型建立电子表格模型)41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学17Wyndor Glass Co. Product Mix ProblemATrialSolution(试验解试验解)ThespreadsheetfortheWyndorproblemwithatrialsolution(4doorsand3windows)enteredintothechangingcells.(含试含试验解的韦恩德公司问题的电子表格模型，在可变单元格中输入验解的韦恩德公司问题的电子表格模型，在可变单元格中输入了了4扇门和扇门和3扇窗扇窗)41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学18Wyndor Glass Co. Product Mix ProblemAlgebraicModelforWyndorGlassCo.(韦恩德公司问题的数学模型韦恩德公司问题的数学模型)LetD=thenumberofdoorstoproduce(门的生产量门的生产量)W=thenumberofwindowstoproduce(窗的生产量窗的生产量)MaximizeP=$300D+$500Wsubjectto(约束约束)D42W123D+2W18andD0,W0.运筹学运筹学Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学19Wyndor Glass Co. Product Mix Problem产产品品组组合合图图形形Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学20Wyndor Glass Co. Product Mix Problem非非负负约约束束Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学21Wyndor Glass Co. Product Mix Problem非非负负约约束束D4Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学22Wyndor Glass Co. Product Mix Problem非非负负约约束束2W12Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学23Wyndor Glass Co. Product Mix ProblemBoundaryLineforConstraint3D+2W18(约束条件边界线约束条件边界线)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学24Wyndor Glass Co. Product Mix Problem只改变约束条件右侧得到平行的约束边界线只改变约束条件右侧得到平行的约束边界线Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学25Wyndor Glass Co. Product Mix Problem3D+2W18的非负可行域的非负可行域Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学26Wyndor Glass Co. Product Mix ProblemGraphofFeasibleRegion(可行域图像可行域图像)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学27Wyndor Glass Co. Product Mix ProblemObjectiveFunction(P=1,500)(目标函数目标函数)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学28Wyndor Glass Co. Product Mix ProblemFindingtheOptimalSolution(寻找最优解寻找最优解)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学29Summary of the Graphical MethodDrawtheconstraintboundarylineforeachconstraint.Usetheorigin(oranypointnotontheline)todeterminewhichsideofthelineispermittedbytheconstraint.(画出每个函数约束的约束边界线，画出每个函数约束的约束边界线，用原点或其它不在约束边界线上的点来确定直线的哪用原点或其它不在约束边界线上的点来确定直线的哪一边是约束条件所允许的一边是约束条件所允许的)Findthefeasibleregionbydeterminingwhereallconstraintsaresatisfiedsimultaneously.(找出由所有找出由所有约束条件都同时满足所决定的可行域约束条件都同时满足所决定的可行域)Determinetheslopeofoneobjectivefunctionline.Allotherobjectivefunctionlineswillhavethesameslope.(确定一条目标函数线的斜率，所有其它目标函数线确定一条目标函数线的斜率，所有其它目标函数线具有与之相同的斜率具有与之相同的斜率)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学30Summary of the Graphical MethodMoveastraightedgewiththisslopethroughthefeasibleregioninthedirectionofimprovingvaluesoftheobjectivefunction.Stopatthelastinstantthatthestraightedgestillpassesthroughapointinthefeasibleregion.Thislinegivenbythestraightedgeistheoptimalobjectivefunctionline.(在可行域范围内在可行域范围内朝着目标函数改进的方向移动目标函数线，在它还穿朝着目标函数改进的方向移动目标函数线，在它还穿过可行域的一个点时停止移动，这时得到的就是最优过可行域的一个点时停止移动，这时得到的就是最优目标函数线目标函数线)Afeasiblepointontheoptimalobjectivefunctionlineisanoptimalsolution.(最优目标函数线上的可行点是最优目标函数线上的可行点是一个最优解一个最优解)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学31Wyndor Glass Co. Product Mix ProblemChoosethe“Solver”fromtheToolsmenu.(从工具菜单从工具菜单中选择中选择“Solver”)Selectthecellyouwishtooptimizeinthe“SetTargetCell”window.(在在“SetTargetCell”中选择要优化的单中选择要优化的单元格元格)Choose“Max”or“Min”dependingonwhetheryouwanttomaximizeorminimizethetargetcell.(根据需根据需要选择要选择“Max”或者或者“Min”选项选项)Enterallthechangingcellsinthe“ByChangingCells”window.(在在“ByChangingCells”窗体中输入所有可变窗体中输入所有可变单元格单元格)IdentifyingtheTargetCellandChangingCells(确定目标单元格和可变单元格确定目标单元格和可变单元格)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学32Wyndor Glass Co. Product Mix Problem41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学33Wyndor Glass Co. Product Mix ProblemAddingConstraints(添加约束添加约束)Tobeginenteringconstraints,clickthe“Add”buttontotherightoftheconstraintswindow.(在约束窗体的右侧点击在约束窗体的右侧点击“Add”按钮添加约按钮添加约束束)FillintheentriesintheresultingAddConstraintdialoguebox.(在添加约束对话框在添加约束对话框中填入相应内容中填入相应内容)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学34Wyndor Glass Co. Product Mix Problem41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学35Wyndor Glass Co. Product Mix ProblemTheCompleteSolverDialogueBox(设置完成的设置完成的Solver对话框对话框)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学36Wyndor Glass Co. Product Mix ProblemSomeImportantOptions(一些重要选项一些重要选项)Clickonthe“Options”button,andclickinboththe“AssumeLinearModel”andthe“AssumeNon-Negative”box.(单击单击“Options”按钮，并按钮，并且选中且选中“AssumeLinearModel”和和“AssumeNon-Negative”选项选项)l“AssumeLinearModel”tellstheSolverthatthisisalinearprogrammingmodel.(“AssumeLinearModel”选项使选项使Solver确定该模型为线性规划模型确定该模型为线性规划模型)l“AssumeNon-Negative”addsnonnegativityconstraintstoallthechangingcells.(“AssumeNon-Negative”选项给所有可变单元格添加非负约束条件选项给所有可变单元格添加非负约束条件)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学37Wyndor Glass Co. Product Mix ProblemCopyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学38Wyndor Glass Co. Product Mix ProblemTheOptimalSolution(最优解最优解)41218Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学39The Profit & Gambit Co.Managementhasdecidedtoundertakeamajoradvertisingcampaignthatwillfocusonthefollowingthreekeyproducts:(管理层决定集中在下管理层决定集中在下列三个主要产品上实行大规模广告活动列三个主要产品上实行大规模广告活动)lAsprayprewashstainremover.(一种喷雾去污剂一种喷雾去污剂)lAliquidlaundrydetergent.(一种液体洗涤剂一种液体洗涤剂)lApowderlaundrydetergent.(一种洗衣粉一种洗衣粉)Thecampaignwillusebothtelevisionandprintmedia(这一广告活动将采用电视和印刷媒体这一广告活动将采用电视和印刷媒体)Thegeneralgoalistoincreasesalesoftheseproducts.(总目标是要增加所有这些产品的销售量总目标是要增加所有这些产品的销售量)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学40Managementhassetthefollowinggoalsforthecampaign:(管理层设定了如下广告目标管理层设定了如下广告目标)lSalesofthestainremovershouldincreasebyatleast3%.(喷雾去污剂至少增加喷雾去污剂至少增加3%的市场份额的市场份额)lSalesoftheliquiddetergentshouldincreasebyatleast18%.(液体洗涤剂至少增加液体洗涤剂至少增加18%的市场份额的市场份额)lSalesofthepowderdetergentshouldincreasebyatleast4%.(洗衣粉至少增加洗衣粉至少增加4%的市场份额的市场份额)The Profit & Gambit Co.Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学41Howmuchshouldtheyadvertiseineachmediumtomeetthesalesgoalsataminimumtotalcost?The Profit & Gambit Co. 要以最低的总成本要以最低的总成本满足销售目标，公司满足销售目标，公司应该在每种媒体上做应该在每种媒体上做多少钱的广告？多少钱的广告？Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学42The Profit & Gambit Co.Profit&GambitCo.SpreadsheetModel(电子表格模型电子表格模型)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学43AlgebraicModelforProfit&Gambit(数学模型数学模型)Let:TV=thenumberofunitsofadvertisingontelevision(电视广告的单位数量电视广告的单位数量)PM=thenumberofunitsofadvertisingintheprintmedia(印刷媒体的广告数量印刷媒体的广告数量)MinimizeCost=TV+2PM(inmillionsofdollars)The Profit & Gambit Co.Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学44AlgebraicModelforProfit&Gambit(数学模型数学模型)subjectto:Stainremoverincreasedsales:PM3(喷雾去污剂的销售增量喷雾去污剂的销售增量)Liquiddetergentincreasedsales: 3TV+2PM18(喷雾去污剂的销售增量喷雾去污剂的销售增量)Powderdetergentincreasedsales:TV+4PM4(喷雾去污剂的销售增量喷雾去污剂的销售增量)AndTV0,PM0.The Profit & Gambit Co.Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学45The Profit & Gambit Co.ApplyingtheGraphicalMethod(应用图形方法应用图形方法)Copyright2007深圳大学管理学院深圳大学管理学院运筹学运筹学46TheOptimalSolution(最优解最优解)The Profit & Gambit Co.Theendofchapter2