武汉大学MBA课程《数据模型与决策》课件 29线性规划与电子表格.ppt

1、Data, Model and Decisions 数据、模型与决策,Session 13 Linear Programming With Spreadsheet 线性规划与电子表格,Session Topics,An Class Working Example 一个课堂操作举例 Basic Concepts of Linear Programming 线性规划的基本概念 The Graphical Method for Solving LP 线性规划的图解法 Using Excel Solver to Solving 用微软Excel Solver 求解 Key Categories of

2、LP Problems 线性规划问题的主要类型 Three Classic Applications of LP 三个经典的线性规划应用,每个小组都有一组拼装玩具(8个小块和6 大块) ，这些是你们的原材料（raw materials），你们要用这些原材料去生产桌和椅（ tables and chairs）这两种产品（products），具体拼装图如下一个幻灯片。,The Lego Production Problem 拼装玩具生产,自己动手,你怎么去分析呢？,自己动手,为了最小化成本或最大化利润的目的需要对一些稀缺资源进行配置,自己动手,你的答案是什么？,Components of the

3、Model 模型的组成部分,Decision variables 决策变量 Objective function 目标函数 Constraints 约束,Assumptions of Linear Programming 线性规划的假设,Linearity 线性 Divisibility 可分性 Certainty 确定性 Nonnegativity 非负性,Why Use Linear Programming? 为什么要使用线性规划,线性规划很容易而有效率地被求解 如果存在最优解，则肯定能够找到 功能强大的敏感性分析（sensitivity analysis） 许多实际问题本质上是线性的,M

4、athematical Statement of LP Problem 线性规划的数学描述,线性规划要确定决策变量 x1, x2, , xn 使得,已知参数 c1, , cn ; a11, , amn ; b1, , bm.,Steps in Formulating LP Problem 线性规划问题建模步骤,需要做哪些决策？决策变量是什么 问题的目标是什么？写出目标函数 资源和需求之间的情况如何？ 确定约束条件,The Graphical Method for Solving LP 线性规划的图解法,The Simple Method for Solving LP 线性规划的单纯形法,Usi

5、ng Excel Solver to Solving 用微软Excel Solver 求解,Solving Lego Problem 求解玩具拼装问题,用易理解方式输入数据和构筑数据之间的联系 定义目标单元格（目标函数） 确定可变单元（决策变量） 添加约束变量（Adding Constraints）,The Solution 求解结果,Key Categories of LP Problems 线性规划问题主要类型,资源分配问题（resource-allocation） 成本收益平衡问题 （cost-benefit-trade-off） 网络配送问题（distribution-network）

6、 混合问题（mixed Problem）,Resource-allocation Problem资源分配问题,问题类型,资源分配（resource-allocation）问题是将有限的资源 分配到各种活动中去的线性规划问题。这一类问题的 共性是在线性规划模型中每一个函数限制均为资源限 制(resource constraint) , 并且每一种有限资源都可以表 现为如下的形式： 使用的资源数量 可用的资源数量,Datum Gathering 收集数据,问题所有活动可获得使用的每种资源的有限数量 每一种活动所需要的各种资源的数量, 每一种资源 与活动的组合,单位活动消耗资源量必须首先估计 每一种

7、活动对总的绩效测度的单位贡献,Super Grain Corp. 超级谷物公司,实际举例,Think-Big Development Co. 梦大发展公司,实际举例,Cost-benefit-trade-off Problem 成本收益平衡问题,问题类型,成本收益平衡问题（ Cost-benefit-trade-off Problem ） 是一类线性规划问题，这类问题中，通过选择各种 活动水平的组合，从而以最小的成本来实现最低可 接受的各种收益的水平。这类问题的共性是，所有 的函数约束均为收益约束，并具有如下的形式： 完成的水平 最低可接受的水平,Cost-benefit-trade-off

8、Examples 成本收益平衡问题举例,Personnel Scheduling 工作人员排程 Controlling Air Pollution 控制空气污染,Union Airways Corp. 邦联航空公司,实际举例,Distribution-network Problem 网络配送问题,问题类型,网络配送问题（distribution network）能以最小的成 本完成货物的配送，所以称之为网络配送问题并具有 如下的确定性约束形式： 提供的数量需要的数量,Distribution Unlimited Co. 无限配送公司,实际举例,Mixed Problem 混合问题,问题类型,资

9、源分配问题，成本收益平衡问题以及网络配送问 题，都以一类约束条件为特色的。实际上，纯资源 分配问题的共性是它所有的函数约束均为资源约束， 而成本收益平衡问题的共性是它所有的函数约束均 为收益约束，网络配送问题中，主要的函数约束为 一特定类型的确定需求的约束。,混合问题 是第四类线性规划问题，这一类型包括 了三类约束函数,Save-It Company 塞维特公司,实际举例,Save-It Company 塞维特公司,实际举例,Summary of LP Types 线性规划问题总结,类型总结,Modeling from Managerial Perspective 管理视角的建模,总绩效测度必

10、须是管理层想获得的现实目标 准确细致地描述资源约束 管理科学小组与管理层的有效沟通 模型往往要不断地修改和扩展 要进行what-if分析,Classical Applications of LP 线性规划经典应用回顾,应用回顾,为潘德罗索工业公司选择产品组合 联合航空公司工作人员排程 Citgo石油集团供应、配送 与营销的规划,Ponderosa Industrial 潘德罗索工业公司,公司经验,潘德罗索应用成功的因素： 以自然语言为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。 最优化系统是互动的（i

11、nteractive），管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的what-if问题，并能立即得到回应。,Personnel Scheduling at UA. 联合航空公司人员排程,公司经验,联合航空公司 利用线性规划，来为其在主要的机场和定票点的上万个工作人员安排每周的工作时间表。目标是为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括20，000个决策变量。 应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。,Citgo Petroleum Corporation Citgo石油集团,公司经验

12、,Citgo石油集团 运用管理科学的技术，特别是线性规划，建立供应、配送与营销的建模系统将公司主要产品的供应、配送与营销通过公司庞大的销售与配送网络得到很好的协调。在90年代中期创造了大量的财富。 公司每种主要产品的模型都含有大约1，500个决策量以及3，000个确定需求的约束 最重要的成功因素是高层管理者所给予的无限制的支持，并且设立运作协调副总裁，来负责评价与协调这一跨组织边界的模型所提供的建议,Session Summary 本讲小结,小结,以符号表示的函数约束称为资源约束，这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。 以符号表示的函数约束为收益约束，形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束，这一问题为成本收益平衡问题。,Session Summary 本讲小结,小结,以符号表示的函数约束称为确定需求的约束，它们表示了一定数量的确定的需求，提供的数量等于要求的数量。网络配送问题的共性就是它们的主要函数约束为一种特定形式的确定需求的约束。 不能归于这三类的任何线性规划的问题称为混合问题。 在实际的应用当中，管理科学小组经常建立和分析大型的线性规划模型以指导管理决策，这些工作需要管理层足够强大的管理上的投入与支持，才能达到管