Chapter02-线性规划：基本概念

Chapter2.LinearProgramming:BasicConcepts第二章.线性规划:基本概念运筹学Copyright2013©北京工商大学商学院管理决策模型与方法2线性规划的基本概念伟恩德玻璃制品公司产品组合问题在电子表格上建立韦恩德公司问题的模型韦恩德公司问题的数学模型韦恩德公司问题的图形方法使用ExcelSolver解决韦恩德公司问题主要内容Copyright2013©北京工商大学商学院管理决策模型与方法3每个小组都有一组拼装玩具(8个小块和6大块)，这些是你们的原材料（rawmaterials），你们要用这些原材料去生产桌和椅（tablesandchairs）这两种产品（products），具体拼装图如下一个幻灯片。TheLegoProductionProblem拼装玩具生产自己动手你怎么去分析呢？想想看！Copyright2013©北京工商大学商学院管理决策模型与方法4原材料6大块8小块产品桌2L2S椅1L2SProfit=$20/TableProfit=$15/Chair自己动手Copyright2013©北京工商大学商学院管理决策模型与方法5Maximize($15)Chairs+($20)TablessubjecttoLargeBricks:Chairs+2Tables£6SmallBricks:2Chairs+2Tables£8andChairs³0,Tables³0.为了最小化成本或最大化利润的目的需要对一些稀缺资源进行配置自己动手你的答案是什么？Copyright2013©北京工商大学商学院管理决策模型与方法6ComponentsoftheModel模型的组成部分Decisionvariables决策变量Objectivefunction目标函数Constraints约束Copyright2013©北京工商大学商学院管理决策模型与方法7AssumptionsofLinearProgramming线性规划的假设Linearity线性Divisibility可分性Certainty确定性Nonnegativity非负性Copyright2013©北京工商大学商学院管理决策模型与方法8WhyUseLinearProgramming?为什么要使用线性规划线性规划很容易而有效率地被求解如果存在最优解，则肯定能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的Copyright2013©北京工商大学商学院管理决策模型与方法9MathematicalStatementofLPProblem线性规划的数学描述线性规划要确定决策变量x1,x2,…,xn使得MaximizeZ=c1x1+¼+cnxn¬ObjectiveFunctionsubjecttoa11x1+¼+a1nxn£b1a21x1+¼+a2nxn£b2am1x1+¼+amnxn£bmüýïïþïï¬FunctionalConstraintsandx1³0,¼,xn³0¬NonnegativityConstraints已知参数c1,…,cn;a11,…,amn;b1,…,bm.Copyright2013©北京工商大学商学院管理决策模型与方法10StepsinFormulatingLPProblem线性规划问题建模步骤需要做哪些决策？决策变量是什么问题的目标是什么？写出目标函数资源和需求之间的情况如何？确定约束条件Copyright2013©北京工商大学商学院管理决策模型与方法11韦恩德公司开发了下列新产品:8英尺的铝框玻璃门4英尺*6英尺的双把木框窗公司有三个工厂工厂1生产铝框和五金件工厂2生产木框工厂3生产玻璃并组装窗和门韦恩德公司产品组合问题Copyright2013©北京工商大学商学院管理决策模型与方法12韦恩德玻璃制品公司产品组合问题的数据韦恩德公司产品组合问题工厂单位产品的生产时间每周可得时间门窗11小时04小时202小时12小时33小时2小时18小时单位利润300500Copyright2013©北京工商大学商学院管理决策模型与方法13公司是否应该生产这两个新产品？如果生产，两个新产品的生产组合如何？韦恩德公司产品组合问题Copyright2013©北京工商大学商学院管理决策模型与方法14韦恩德公司产品组合问题韦恩德公司问题的数学模型LetD=门的生产量W=窗的生产量MaximizeP=$300D+$500Wsubjectto(约束)D≤42W≤123D+2W≤18andD≥0,W≥0.运筹学Copyright2013©北京工商大学商学院管理决策模型与方法15韦恩德公司产品组合问题产品组合图形Productionrate(unitsperweek)forwindowsAproductmixofAproductmixof123456780-1-1-212345678-2Productionrate(unitsperweek)forwindowsProductionrate(unitsperweek)fordoors(4,6)(2,3)D=4andW=6D=2andW=3OriginDWCopyright2013©北京工商大学商学院管理决策模型与方法16韦恩德公司产品组合问题非负约束Productionrateforwindows864224680ProductionratefordoorsProductionrateforwindowsDWCopyright2013©北京工商大学商学院管理决策模型与方法17韦恩德公司产品组合问题非负约束D≤4ProductionrateforwindowsDW864224680ProductionratefordoorsProductionrateforwindowsD=4Copyright2013©北京工商大学商学院管理决策模型与方法18韦恩德公司产品组合问题非负约束2W≤12Productionratefordoors8642246802W=12DWProductionrateforwindowsCopyright2013©北京工商大学商学院管理决策模型与方法19韦恩德公司产品组合问题BoundaryLineforConstraint3D+2W≤18(约束条件边界线)Productionratefordoors86422468010(0,9)(2,6)(4,3)21_(1,7)21_(3,4)21_(5,1)(6,0)3D+2W=18DWProductionrateforwindowsCopyright2013©北京工商大学商学院管理决策模型与方法20韦恩德公司产品组合问题只改变约束条件右侧得到平行的约束边界线121086420246810ProductionratefordoorsDW3D+2W=243D+2W=183D+2W=12ProductionrateforwindowsCopyright2013©北京工商大学商学院管理决策模型与方法21韦恩德公司产品组合问题3D+2W≤18的非负可行域86402468102ProductionratefordoorsDW3D+2W=18ProductionrateforwindowsCopyright2013©北京工商大学商学院管理决策模型与方法22韦恩德公司产品组合问题GraphofFeasibleRegion(可行域图像)02468864102FeasibleregionProductionratefordoorsDW2W=12D=43D+2W=18ProductionrateforwindowsCopyright2013©北京工商大学商学院管理决策模型与方法23韦恩德公司产品组合问题ObjectiveFunction(P=1,500)(目标函数)024688642ProductionrateforwindowsProductionratefordoorsFeasibleregionP=1500=300D+500WDWCopyright2013©北京工商大学商学院管理决策模型与方法24韦恩德公司产品组合问题FindingtheOptimalSolution(寻找最优解)024688642ProductionrateforwindowsProductionratefordoorsFeasibleregion(2,6)Optimalsolution10WDP=3600=300D+500WP=3000=300D+500WP=1500=300D+500WCopyright2013©北京工商大学商学院管理决策模型与方法25图解法总结画出每个函数约束的约束边界线，用原点或其它不在约束边界线上的点来确定直线的哪一边是约束条件所允许的找出由所有约束条件都同时满足所决定的可行域确定一条目标函数线的斜率，所有其它目标函数线具有与之相同的斜率在可行域范围内朝着目标函数改进的方向移动目标函数线，在它还穿过可行域的一个点时停止移动，这时得到的就是最优目标函数线最优目标函数线上的可行点是一个最优解Copyright2013©北京工商大学商学院管理决策模型与方法26建立电子表格模型第一步:数据单元格在电子表格中输入问题的所有数据有效利用行和列为这些数据单元格标上颜色便于区分和建模韦恩德公司产品组合问题Copyright2013©北京工商大学商学院管理决策模型与方法27韦恩德公司产品组合问题建立电子表格模型Copyright2013©北京工商大学商学院管理决策模型与方法28第二步:可变单元格在电子表格中为每一决策添加一个单元格如果没有任何初始值，输入0即可为这些可变单元格标上颜色便于区分和建模建立电子表格模型韦恩德公司产品组合问题Copyright2013©北京工商大学商学院管理决策模型与方法29建立电子表格模型韦恩德公司产品组合问题41218Copyright2013©北京工商大学商学院管理决策模型与方法30建立电子表格模型韦恩德公司产品组合问题第三步:目标单元格建立定义模型目标的方程式典型地，这个方程式包含了数据单元格和可变单元格的数据，以确定有关的数量值，如总利润和总成本给目标单元格标记颜色Copyright2013©北京工商大学商学院管理决策模型与方法31韦恩德公司产品组合问题建立电子表格模型TotalProfit=C4*C12+D4*D1241218Copyright2013©北京工商大学商学院管理决策模型与方法32建立电子表格模型第四步:约束对所有有限资源，在电子表格的输出单元格中计算出资源的使用量在三个连续的单元格中定义约束韦恩德公司产品组合问题Copyright2013©北京工商大学商学院管理决策模型与方法33韦恩德公司产品组合问题建立电子表格模型HoursUsed=C7*C12+D7*D12=C8*C12+D8*D12=C9*C12+D9*D1241218Copyright2013©北京工商大学商学院管理决策模型与方法34韦恩德公司产品组合问题决策变量的非负限制规划求解允许通过直接引用代表决策变量的单元格对决策变量制定简单上限和下限。因此，没必要在电子表格中采取特别的工作来建立这些界限。建立电子表格模型Copyright2013©北京工商大学商学院管理决策模型与方法35韦恩德公司产品组合问题ATrialSolution(试验解)含试验解的韦恩德公司问题的电子表格模型，在可变单元格中输入了4扇门和3扇窗41218Copyright2013©北京工商大学商学院管理决策模型与方法36韦恩德公司产品组合问题从工具菜单中选择“Solver”在“SetTargetCell”中选择要优化的单元格根据需要选择“Max”或者“Min”选项在“ByChangingCells”窗体中输入所有可变单元格确定目标单元格和可变单元格Copyright2013©北京工商大学商学院管理决策模型与方法37韦恩德公司产品组合问题41218Copyright2013©北京工商大学商学