chapter02线性基本概念

运筹学

OperationsResearch杨雯博士深圳大学管理学院

OperationsResearchChapter2.LinearProgramming:BasicConceptsChapter2.

LinearProgramming:

BasicConcepts第二章.线性规划:基本概念OperationsResearchChapter2.LinearProgramming:BasicConceptsThreeClassicApplicationsofLP(Section2.1)(线性规划的三个经典应用[第2.1节])TheWyndorGlassCompanyProductMixProblem(Section2.2)(伟恩德玻璃制品公司产品组合问题[第2.2节])FormulatingtheWyndorProblemonaSpreadsheet(Section2.3)(在电子表格上建立韦恩德公司问题的模型[第2.3节])TheAlgebraicModelforWyndor(Section2.4)(韦恩德公司问题的数学模型[第2.4节])TableofContentsChapter2.LinearProgramming:BasicConceptsTheGraphicalMethodAppliedtotheWyndorProblem(Section2.5)(韦恩德公司问题的图形方法[第2.5节])UsingtheExcelSolverwiththeWyndorProblem(Section2.6)(使用ExcelSolver解决韦恩德公司问题[第2.6节])AMinimizationExample—TheProfit&GambitCo.(Section2.7)(一个最小化的例子——利博公司广告组合问题[第2.7节])TableofContentsChapter2.LinearProgramming:BasicConceptsProductMixatPonderosaIndustrial(潘得罗索工业公司的产品组合问题)市场的变动导致不同时期生产不同类型的胶合板所带来的利润也不同生产资源的有限性Consideredlimitedresources,anddeterminedoptimalmixofplywoodproducts.(考虑了有限资源，并确定了胶合板产品的最优组合)Increasedoverallprofitabilityofcompanyby20%.(公司的总利润增加了20%)ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsPersonnelSchedulingatUnitedAirlines(联合航空公司的员工排程)Designedworkschedulesforallemployeesatalocationtomeetservicerequirementsmostefficiently.(在每个地点为所有员工设计工作排程以最有效地满足服务需求)Saved$6millionannually.(每年可节约600万美元)线性规划太有用了！ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsPlanningSupply,Distribution,andMarketingatCitgoPetroleumCorporation(Citgo石油公司的供应、配送和营销计划)TheSDMsystemusesLPtocoordinatethesupply,distribution,andmarketingofeachofCitgo’smajorproductsthroughouttheUnitedStates.(SDM系统使用LP来协调全美Citgo石油公司主要产品的供应、配送和营销)Theresultingreductionininventoryadded$14millionannuallytoCitgo’sprofits.(库存成本的下降每年为公司增加1400万美元的收入)ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsWyndorhasdevelopedthefollowingnewproducts(韦恩德公司开发了下列新产品):An8-footglassdoorwithaluminumframing.(8英尺的铝框玻璃门)A4-footby6-footdouble-hung,wood-framedwindow.(4英尺*6英尺的双把木框门)Thecompanyhasthreeplants(公司有三个工厂)Plant1producesaluminumframesandhardware.(工厂1生产铝框和五金件)Plant2produceswoodframes.(工厂2生产木框)Plant3producesglassandassemblesthewindowsanddoors.(工厂3生产玻璃并组装窗和门)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDataofWyndorGlassCo.ProductMixProblem(韦恩德玻璃制品公司产品组合问题的有关数据)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsShouldtheygoaheadwithlaunchingthesetwonewproducts?Ifso,whatshouldbetheproductmix?公司是否应该生产这两个新产品？如果生产，两个新产品的生产组合如何？WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsAlgebraicModelforWyndorGlassCo.(韦恩德公司问题的数学模型)Let D=thenumberofdoorstoproduce

(门的生产量)

W=thenumberofwindowstoproduce

(窗的生产量)MaximizeP=$300D+$500Wsubjectto(约束)

D≤4

2W≤12

3D+2W≤

18and D≥

0,W≥

0.运筹学线性规划WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts产品组合图形WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非负约束WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非负约束D≤4WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非负约束2W≤12WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsBoundaryLineforConstraint3D+2W≤

18(约束条件边界线)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts只改变约束条件右侧得到平行的约束边界线WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts3D+2W≤

18的非负可行域WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsGraphofFeasibleRegion(可行域图像)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsObjectiveFunction(P=1,500)(目标函数)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsFindingtheOptimalSolution(寻找最优解)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDrawtheconstraintboundarylineforeachconstraint.Usetheorigin(oranypointnotontheline)todeterminewhichsideofthelineispermittedbytheconstraint.(画出每个函数约束的约束边界线，用原点或其它不在约束边界线上的点来确定直线的哪一边是约束条件所允许的)Findthefeasibleregionbydeterminingwhereallconstraintsaresatisfiedsimultaneously.(找出由所有约束条件都同时满足所决定的可行域)Determinetheslopeofoneobjectivefunctionline.Allotherobjectivefunctionlineswillhavethesameslope.(确定一条目标函数线的斜率，所有其它目标函数线具有与之相同的斜率)SummaryoftheGraphicalMethodWyndorGlassCo.ProductMixProblemMoveastraightedgewiththisslopethroughthefeasibleregioninthedirectionofimprovingvaluesoftheobjectivefunction.Stopatthelastinstantthatthestraightedgestillpassesthroughapointinthefeasibleregion.Thislinegivenbythestraightedgeistheoptimalobjectivefunctionline.(在可行域范围内朝着目标函数改进的方向移动目标函数线，在它还穿过可行域的一个点时停止移动，这时得到的就是最优目标函数线)Afeasiblepointontheoptimalobjectivefunctionlineisanoptimalsolution.(最优目标函数线上的可行点是一个最优解)SummaryoftheGraphicalMethodWyndorGlassCo.ProductMixProblemDevelopingaSpreadsheetModel(建立电子表格模型)Step#1:DataCells(第一步:数据单元格)Enterallofthedatafortheproblemonthespreadsheet.(在电子表格中输入问题的所有数据)Makeconsistentuseofrowsandcolumns.(有效利用行和列)Itisagoodideatocolorcodethese“datacells”(e.g.,lightblue).(为这些数据单元格标上颜色便于区分和建模)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel(建立电子表格模型)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsStep#2:ChangingCells(第二步:可变单元格)Addacellinthespreadsheetforeverydecisionthatneedstobemade.(在电子表格中为每一决策添加一个单元格)Ifyoudon’thaveanyparticularinitialvalues,justenter0ineach.(如果没有任何初始值，输入0即可)Itisagoodideatocolorcodethese“changingcells”(e.g.,yellowwithborder).(为这些可变单元格标上颜色便于区分和建模)DevelopingaSpreadsheetModel(建立电子表格模型)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel(建立电子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立电子表格模型)Step#3:TargetCell(第三步:目标单元格)Developanequationthatdefinestheobjectiveofthemodel.(建立定义模型目标的方程式)Typicallythisequationinvolvesthedatacellsandthechangingcellsinordertodetermineaquantityofinterest(e.g.,totalprofitortotalcost).(典型地，这个方程式包含了数据单元格和可变单元格的数据，以确定有关的数量值，如总利润和总成本)Itisagoodideatocolorcodethiscell(e.g.,orangewithheavyborder).(给目标单元格标记颜色)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立电子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立电子表格模型)Step#4:Constraints(约束)Foranyresourcethatisrestricted,calculatetheamountofthatresourceusedinacellonthespreadsheet(anoutputcell).(对所有有限资源，在电子表格的输出单元格中计算出资源的使用量)Definetheconstraintinthreeconsecutivecells.Forexample,ifQuantityA≤QuantityB,putthesethreeitems(QuantityA,≤,QuantityB)inconsecutivecells.(在三个连续的单元格中定义约束)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立电子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsATrialSolution(试验解)ThespreadsheetfortheWyndorproblemwithatrialsolution(4doorsand3windows)enteredintothechangingcells.(含试验解的韦恩德公司问题的电子表格模型，在可变单元格中输入了4扇门和3扇窗)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsChoosethe“Solver”fromtheToolsmenu.(从工具菜单中选择“Solver”)Selectthecellyouwishtooptimizeinthe“SetTargetCell”window.(在“SetTargetCell”中选择要优化的单元格)Choose“Max”or“Min”dependingonwhetheryouwanttomaximizeorminimizethetargetcell.(根据需要选择“Max”或者“Min”选项)Enterallthechangingcellsinthe“ByChangingCells”window.(在“ByChangingCells”窗体中输入所有可变单元格)IdentifyingtheTargetCellandChangingCells

(确定目标单元格和可变单元格)Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConcepts41218Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsAddingConstraints(添加约束)Tobeginenteringconstraints,clickthe“Add”buttontotherightoftheconstraintswindow.(在约束窗体的右侧点击“Add”按钮添加约束)FillintheentriesintheresultingAddConstraintdialoguebox.(在添加约束对话框中填入相应内容)Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConcepts41218Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsTheCompleteSolverDialogueBox(设置完成的Solver对话框)Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsSomeImportantOptions(一些重要选项)Clickonthe“Options”button,andclickinboththe“AssumeLinearModel”andthe“AssumeNon-Negative”box.(单击“Options”按钮，并且选中“AssumeLinearModel”和“AssumeNon-Negative”选项)“AssumeLinearModel”tellstheSolverthatthisisalinearprogrammingmodel.(“AssumeLinearModel”选项使Solver确定该模型为线性规划模型)“AssumeNon-Negative”addsnonnegativityconstraintstoallthechangingcells.(“AssumeNon-Negative”选项给所有可变单元格添加非负约束条件)Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsSolver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsTheOptimalSolution(最优解)41218Solver求解韦恩德公司的产品组合问题Chapter2.LinearProgramming:BasicConceptsManagementhasdecidedtoundertakeamajoradvertisingcampaignthatwillfocusonthefollowingthreekeyproducts:(管理层决定集中在下列三个主要产品上实行大规模广告活动)Asprayprewashstainremover.(一种喷雾去污剂)Aliquidlaundrydetergent.(一种液体洗涤剂)Apowderlaundrydetergent.(一种洗衣粉)Thecampaignwillusebothtelevisionandprintmedia(这一广告活动将采用电视和印刷媒体)Thegeneralgoalistoincreasesalesoftheseproducts.(总目标是要增加所有这些产品的销售量)TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConceptsManagementhassetthefollowinggoalsforthecampaign:(管理层设定了如下广告目标)Salesofthestainremovershouldincreasebyatleast3%.(喷雾去污剂至少增加3%的市场份额)Salesoftheliquiddetergentshouldincreasebyatleast18%.(液体洗涤剂至少增加18%的市场份额)Salesofthepowderdetergentshouldincreasebyatleast4%.(洗衣粉至少增加4%的市场份额)TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConceptsDataofProfit&GambitCo.Problem(利博公司问题的有关数据)TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConcepts