Session2线性规划与电子表格.ppt

Data,ModelandDecisions数据、模型与决策,Session2LinearProgrammingWithSpreadsheet线性规划与电子表格,SessionTopics,AnClassWorkingExample一个课堂操作举例BasicConceptsofLinearProgramming线性规划的基本概念TheGraphicalMethodforSolvingLP线性规划的图解法UsingExcelSolvertoSolving用微软ExcelSolver求解KeyCategoriesofLPProblems线性规划问题的主要类型ThreeClassicApplicationsofLP三个经典的线性规划应用,每个小组都有一组拼装玩具(8个小块和6大块)，这些是你们的原材料（rawmaterials），你们要用这些原材料去生产桌和椅（tablesandchairs）这两种产品（products），具体拼装图如下一个幻灯片。,TheLegoProductionProblem拼装玩具生产,自己动手,你怎么去分析呢？,自己动手,为了最小化成本或最大化利润的目的需要对一些稀缺资源进行配置,自己动手,你的答案是什么？,ComponentsoftheModel模型的组成部分,Decisionvariables决策变量Objectivefunction目标函数Constraints约束,AssumptionsofLinearProgramming线性规划的假设,Linearity线性Divisibility可分性Certainty确定性Nonnegativity非负性,WhyUseLinearProgramming?为什么要使用线性规划,线性规划很容易而有效率地被求解如果存在最优解，则肯定能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的,MathematicalStatementofLPProblem线性规划的数学描述,线性规划要确定决策变量x1,x2,xn使得,已知参数c1,cn;a11,amn;b1,bm.,StepsinFormulatingLPProblem线性规划问题建模步骤,需要做哪些决策？决策变量是什么问题的目标是什么？写出目标函数资源和需求之间的情况如何？确定约束条件,TheGraphicalMethodforSolvingLP线性规划的图解法,TheSimpleMethodforSolvingLP线性规划的单纯形法,UsingExcelSolvertoSolving用微软ExcelSolver求解,SolvingLegoProblem求解玩具拼装问题,用易理解方式输入数据和构筑数据之间的联系定义目标单元格（目标函数）确定可变单元（决策变量）添加约束变量（AddingConstraints）,TheSolution求解结果,KeyCategoriesofLPProblems线性规划问题主要类型,资源分配问题（resource-allocation）成本收益平衡问题（cost-benefit-trade-off）网络配送问题（distribution-network）混合问题（mixedProblem）,Resource-allocationProblem资源分配问题,问题类型,资源分配（resource-allocation）问题是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为资源限制(resourceconstraint),并且每一种有限资源都可以表现为如下的形式：使用的资源数量可用的资源数量,DatumGathering收集数据,问题所有活动可获得使用的每种资源的有限数量每一种活动所需要的各种资源的数量,每一种资源与活动的组合,单位活动消耗资源量必须首先估计每一种活动对总的绩效测度的单位贡献,SuperGrainCorp.超级谷物公司,实际举例,Think-BigDevelopmentCo.梦大发展公司,实际举例,Cost-benefit-trade-offProblem成本收益平衡问题,问题类型,成本收益平衡问题（Cost-benefit-trade-offProblem）是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益的水平。这类问题的共性是，所有的函数约束均为收益约束，并具有如下的形式：完成的水平最低可接受的水平,Cost-benefit-trade-offExamples成本收益平衡问题举例,PersonnelScheduling工作人员排程ControllingAirPollution控制空气污染,UnionAirwaysCorp.邦联航空公司,实际举例,Distribution-networkProblem网络配送问题,问题类型,网络配送问题（distributionnetwork）能以最小的成本完成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：提供的数量需要的数量,DistributionUnlimitedCo.无限配送公司,实际举例,MixedProblem混合问题,问题类型,资源分配问题，成本收益平衡问题以及网络配送问题，都以一类约束条件为特色的。实际上，纯资源分配问题的共性是它所有的函数约束均为资源约束，而成本收益平衡问题的共性是它所有的函数约束均为收益约束，网络配送问题中，主要的函数约束为一特定类型的确定需求的约束。,混合问题是第四类线性规划问题，这一类型包括了三类约束函数,Save-ItCompany塞维特公司,实际举例,Save-ItCompany塞维特公司,实际举例,SummaryofLPTypes线性规划问题总结,类型总结,ModelingfromManagerialPerspective管理视角的建模,总绩效测度必须是管理层想获得的现实目标准确细致地描述资源约束管理科学小组与管理层的有效沟通模型往往要不断地修改和扩展要进行what-if分析,ClassicalApplicationsofLP线性规划经典应用回顾,应用回顾,为潘德罗索工业公司选择产品组合联合航空公司工作人员排程Citgo石油集团供应、配送与营销的规划,PonderosaIndustrial潘德罗索工业公司,公司经验,潘德罗索应用成功的因素：以自然语言为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。最优化系统是互动的（interactive），管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的what-if问题，并能立即得到回应。,PersonnelSchedulingatUA.联合航空公司人员排程,公司经验,联合航空公司利用线性规划，来为其在主要的机场和定票点的上万个工作人员安排每周的工作时间表。目标是为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括20，000个决策变量。应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。,CitgoPetroleumCorporationCitgo石油集团,公司经验,Citgo石油集团运用管理科学的技术，特别是线性规划，建立供应、配送与营销的建模系统将公司主要产品的供应、配送与营销通过公司庞大的销售与配送网络得到很好的协调。在90年代中期创造了大量的财富。公司每种主要产品的模型都含有大约1，500个决策量以及3，000个确定需求的约束最重要的成功因素是高层管理者所给予的无限制的支持，并且设立运作协调副总裁，来负责评价与协调这一跨组织边界的模型所提供的建议,SessionSummary本讲小结,小结,以符号表示的函数约束称为资源约束，这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。以符号表示的函数约束为收益约束，形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束，这一问题为成本收益平衡问题。,SessionSummary本讲小结,小结,以符号表示的函数约束称为确定需求的约束，它们表示了一定数量的确定的需求，提供的数量等于要求的数量。网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束。不能归于这三类的任何线性规划的问题称为混合问题。在实际的应用当中，管理科学小组经常建立和分析大型的线性规划模型以指导管理