数据、模型与决策-线性规划与电子表格.ppt

《数据、模型与决策-线性规划与电子表格.ppt》由会员分享，可在线阅读，更多相关《数据、模型与决策-线性规划与电子表格.ppt（63页珍藏版）》请在三一办公上搜索。

1、Data,Model and Decisions数据、模型与决策,Session 3 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 Categori

2、es of LP Problems 线性规划问题的主要类型Three Classic Applications of LP三个经典的线性规划应用,数 据 模 型 决 策,线性最优化我们讨论的很多问题是在经济管理领域中对数据的收集、整理、分析，在此基础之上进行决策的理论和方法。这些方法都是建立在概率统计理论之上的。但是，这些方法不能完全解决经济管理领域中的众多最优化问题，特别是几乎无法处理经济管理中的系统最优化问题。我们必须寻求另外的方法和模型，而运筹学自二战后发展起来的一门科学，为我们提供了解决这一类问题的大量独特的方法和模型。,数 据 模 型 决 策,二战中成功的运筹学案例：1、英国防空部门

3、如何布置防空雷达，建立最有效的防空警报系统。英，美空军如何提高对地面目标轰炸的命中率。2、如何安排反潜飞机的巡逻飞行线路。3、深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。4、商船如何编队，遭潜艇攻击时如何减少损失。使船只受敌机攻击时，中弹数由47%降到29%。这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！,数 据 模 型 决 策,战争结束了！整个世界投入到了战后的重建国家的经济之中。运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。线性规划，非线性规划，整数规划，目标规划，动态规

4、划，图与网络分析，统筹方法，排队论，存储论，对策论，决策论，多目标决策。,数 据 模 型 决 策,运筹学的主要应用 二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述。1、市场销售-广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。（美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。2、生产计划-从总体确定生产、存储和劳动力的配合等计划适应波动的需求计划。巴基斯坦一重型制造厂用线性规划安排生产计划，节省10%的生产费用。3、运输问题-涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，

5、出租车的调度等。,数 据 模 型 决 策,4、人事管理-需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。5、设备维修，更新和可靠性等。6、计算机和信息系统-内存分配研究，网络设计分析等。7、城市管理-紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路线等。8、对策研究-价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。,数 据 模 型 决 策,线性最优化建模的若干例子 运筹学中线性最优化理论和模型是我们在经济管理中首先遇到，又是最简单的，也恰恰是目前最广泛应用

6、的工具，运筹学中又常常称为线性规划（LP-Linear Programming）。如何解决有限资源在有竞争的使用方向中如何进行最佳分配。自1947年旦茨基（G.B.Dantzig）提出了一般线性规划问题求解的方法单纯形法（simplex method）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界500家最大的企业中，有 85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。,数 据 模 型 决 策,线性最优化建模的若干例子 下面，我们将首先关心如何将一些管理决策问题转化为一个线性规划模型，这一点将是最关

7、键的一点。线性规划问题究竟是一类什么样的问题呢？请看案例,数 据 模 型 决 策,线性最优化建模的若干例子例 1 投资组合问题例 2 生产调配问题 一家刀剪厂主要生产两种产品，菜刀和剪子。它们都需要铁做原料，并经过“浇铸”与“装配”两道工序完成。经过搜集、分析后，我们获得如下各种数据：,数 据 模 型 决 策,线性最优化建模的若干例子 现在，管理者面临的决策是：利用现有的设备与可获得的原料，每月工厂生产多少刀及多少剪可以获得最大总利润，且这个最大利润是多少？如果再进一步，管理人员还希望知道这个能够使工厂获得最大利润的生产计划在哪些设备或原料方面已经充分利用，哪些还有空闲的余地。下面，我们首先飞

8、行此问题需要一种什么样的决策模型加以解决，为此，引入：,数 据 模 型 决 策,线性最优化建模的若干例子决策变量：（产品产量）D=每月生产的刀数（单位：万把）J=每月生产的剪数（单位：万把）目标函数：（总利润）Z=5300 D+8200 J约束条件：原料约束：0.5 D+0.2 J 6 制模约束：0.5 D+0.7 J 16 装配约束：0.1 D+0.2 J 4 需求约束：D 7，J 16 产量非负约束：D 0，J 0,数 据 模 型 决 策,线性最优化建模的若干例子生产调配问题数学模型,数 据 模 型 决 策,Max z=0.53D+0.82J 0.5D+0.2J 6 s.t.0.5D+0.

9、7J 16 0.1D+0.2J 4 D 7 J 16 D，J 0,线性最优化建模的若干例子建立线性最优化模型的基本步骤：1.确定决策变量：决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。2.确定目标函数：目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（max）或最小化（min）。3.确定约束方程：一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。4.变量取值限制：一般情况下，决策变量取正值（

10、非负值）。因此，模型中应有变量的非负约束即Xj0，但也存在例外。,数 据 模 型 决 策,Assumptions of Linear Programming线性规划的假设,Linearity 线性Divisibility 可分性Certainty 确定性Nonnegativity 非负性,数 据 模 型 决 策,Why Use Linear Programming?为什么要使用线性规划,线性规划很容易而有效率地被求解如果存在最优解，则肯定能够找到功能强大的敏感性分析（sensitivity analysis）许多实际问题本质上是线性的,数 据 模 型 决 策,Mathematical Stat

11、ement of LP Problem线性规划的数学描述,线性规划要确定决策变量 x1,x2,xn 使得,已知参数 c1,cn;a11,amn;b1,bm.,数 据 模 型 决 策,Steps in Formulating LP Problem线性规划问题建模步骤,需要做哪些决策？决策变量是什么 问题的目标是什么？写出目标函数 资源和需求之间的情况如何？确定约束条件,数 据 模 型 决 策,13.2 线性最优化模型的解 对于建立的线性最优化模型，重要的问题是寻求它的解。那么，如何求解一般的线性规划呢？下面我们分析一下简单的情况 只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解

12、法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。稍后我们在介绍如何利用 Microsoft Excel 所提供的一种宏“规划求解”来完成此任务，并且进行非常有益的一些相关分析。,数 据 模 型 决 策,13.2 线性最优化建模的解图解法：例：有如下线性规划问题,数 据 模 型 决 策,max z=2x1+x2 5x1 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0,13.2 线性最优化建模的解,数 据 模 型 决 策,max z=2x1+x2 5x1 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0,x1,x2,可行解域,最优解（3，2）,1

13、3.2 线性最优化建模的解,数 据 模 型 决 策,J,D,Max z=0.53D+0.82J 0.5D+0.2J 6 s.t.0.5D+0.7J 16 0.1D+0.2J 4 D 7 J 16 D，J 0,可行解域,0.5D+0.2J=6,0.5D+0.7J=16,0.1D+0.2J=4,D=7,J=16,16.088=0.53D+0.82J,（D，J）=（5.6，16）,The Simple Method for Solving LP线性规划的单纯形法,13.3 线性最优化模型的 Microsoft Excel 操作 利用 Microsoft Excel 求解线性最优化模型的基本内容：1、

14、收集整理数据，建立原始数据表；2、设计决策变量，有必要时引入关系变量；3、分析问题的约束条件，并将其反映在表格上；4、建立问题的目标函数，确定优化方向；5、利用加载宏 Solver（规划求解）进行求解；6、生成计算结果及分析报告。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本 运算结果报告：到达限制值 未到限制值 型数值离到达限制值的剩余值,数 据 模 型 决 策,敏感性分析、影子价格及递减成本 线性最优化模型的应用一个重要的环节是敏感性分析。敏感性分析又称为灵敏度分析，敏感性分析的重要性在于向决策者提供线性规划问题的最优解所能适应的环境条件变化的范围，环境条件变化时可能对经营状况带

15、来何种影响，产生影响后的解决途径。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本目标函数（目标式系数）中各变量系数的敏感性分析：从敏感性报告中，可以知道目标式中各变量的系数的当前值及允许的增加量和减少量，此即是这些系数的允许变化范围，在此范围内变化时，最优解组不变（最优解也不变）。当然，最优目标值会发生变化！约束条件右端常数（约束限制值）的敏感性分析：从敏感性报告中，还可以知道各约束条件右端常数的当前值及允许的增加量和减少量，此即是这些系数的允许变化范围，在此范围内变化时，最优解组不变（但最优解可能变化）。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本影子价格：影子价格是线

16、性最优化模型的分析中最重要的概念之一，它有其经济学上的重要意义。在线性最优化模型中，我们常常将约束条件右端的常数解释为“资源”。而影子价格提供了该资源在系统中的经济学意义上的“边际价值”。影子价格 在其它条件和目标函数等一切不变的情况下，约束条件右端的常数（资源）每增加 1 个单位时，最优目标函数值的增加值。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本敏感性报告：约束表格：终值表示最优解情况下最终的用量 阴影价格影子价格 约束限制值约束条件的右端值,数 据 模 型 决 策,敏感性分析、影子价格及递减成本敏感性报告：约束表格：阴影价格影子价格 允许增量/允许减量影子价格的有效范围 阴

17、影价格为 0,说明用量未达到限制值，在此情况下允许增量为无穷，表示怎么增加此种资源量也不会增加纯利润，允许减量等于型数值。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本影子价格的特点：特点1、影子价格是对系统资源的一种内部最优估价，只有当系统 达到最优状态时才可能赋予资源这种价值。特点2、系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本影子价格的特点：特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有

18、实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。特点4、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。特点5、影子价格准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致影子价格的不同经济解释。一般的解释有影子利润和影子成本两种。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本敏感性报告：递减成本待减去的值 下面我们引入一个重要概念：基变量 入选最优解组，终值大于0，可变单元格的限制未起作用。非基变量 未入选最优

19、解组，终值取0，或者入选最优解但可变单元的限制起作用，终值达到上限。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本敏感性报告：可变单元格：目标系数在何种范围内可保持原有的最优解不变 终值最优解 目标系数目标函数中相应的系数值 允许增量/允许减量在（目标式系数允许减量，目标式系数允许增量）范围内，相应的决策变量的最优解不发生变化。递减成本待减去的值,数 据 模 型 决 策,敏感性分析、影子价格及递减成本递减成本：某非基变量的递减成本（Reduced Cost）非 0 的含义是指该非基变量在目标函数中的系数如果减去的值超过其递减成本，则该非基变量就会被入选到最优解组当中而成为一个基变量，

20、同时原有的基变量中必然有一个会退出最优解组而变为非基变量。鉴于此，我们也可以将递减成本理解为“可减去的值”。,数 据 模 型 决 策,敏感性分析、影子价格及递减成本极限值报告：最优解下目标函数的取值。,数 据 模 型 决 策,Key Categories of LP Problems 线性规划问题主要类型,资源分配问题（resource-allocation）成本收益平衡问题（cost-benefit-trade-off）网络配送问题（distribution-network）混合问题（mixed Problem）,Resource-allocation Problem资源分配问题（案例p92

21、-100）,问题类型,资源分配（resource-allocation）问题是将有限的资源分配到各种活动中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数限制均为资源限制(resource constraint),并且每一种有限资源都可以表现为如下的形式：使用的资源数量 可用的资源数量,Think-Big Development Co.梦大发展公司（p101-106）资金预算,实际举例,Datum Gathering收集数据,问题所有活动可获得使用的每种资源的有限数量每一种活动所需要的各种资源的数量,每一种资源 与活动的组合,单位活动消耗资源量必须首先估计每一种活动对总的绩效测度

22、的单位贡献,Super Grain Corp.超级食品公司,实际举例,资源分配问题的特点p100,对每一个活动，需要作出活动数量的决策，也就是要确定活动水平三类数据对任何一个资源分配问题都是必须的：每种资源的可供量每一种活动所需要的各种资源的数量（单位活动消耗的资源量）每一种活动对总绩效测度的单位贡献,资源分配问题的建模步骤总结（p106）解决资源分配问题的第一步是明确活动和资源,1、确定问题的活动类型，即决定各种活动的水平2、明确合适的绩效测度以求解问题3、估计每一种活动对于总绩效测度的单位贡献4、明确分配给各种活动的有限资源5、对于每一种资源，明确可获得的数量以及各种活动的单位使用量6、将

23、3和5收集的数据输入数据单元格7、指定可变单元格显示活动水平的决策量8、输入约束条件输出单元格，=或=，sumproduct函数9、指派目标单元格,Cost-benefit-trade-off Problem成本收益平衡问题,问题类型,成本收益平衡问题（Cost-benefit-trade-off Problem）是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益的水平。这类问题的共性是，所有的函数约束均为收益约束，并具有如下的形式：完成的水平 最低可接受的水平,成本收益平衡问题需要的三种数据,每种收益的最低可接受水平（管理决策）每一种活动对

24、每一种收益的贡献（单位活动的贡献）每种活动的单位成本解决任何成本收益问题的第一步是明确活动和收益,Cost-benefit-trade-off Examples成本收益平衡问题举例,利博公司广告组合（p44-49）Personnel Scheduling 工作人员排程（p108-113）Controlling Air Pollution 控制空气污染（p112-113）,Union Airways Corp.邦联航空公司工作人员排程,实际举例,Distribution-network Problem网络配送问题,问题类型,网络配送问题（distribution network）能以最小的成本完

25、成货物的配送，所以称之为网络配送问题并具有如下的确定性约束形式：提供的数量需要的数量 解决任何配送问题的第一步都是明确活动和确定的限制,Distribution Unlimited Co.无限配送公司,实际举例,Mixed Problem混合问题（p121-128）,问题类型,资源分配问题，成本收益平衡问题以及网络配送问题，都以一类约束条件为特色的。实际上，纯资源分配问题的共性是它所有的函数约束均为资源约束，而成本收益平衡问题的共性是它所有的函数约束均为收益约束，网络配送问题中，主要的函数约束为一特定类型的确定需求的约束。,混合问题 是第四类线性规划问题，这一类型包括了三类约束函数,Save-

26、It Company塞维特公司混合问题(p122-127),实际举例,Save-It Company塞维特公司,实际举例,Summary of LP Types线性规划问题总结,类型总结,Modeling from Managerial Perspective管理视角的建模,总绩效测度必须是管理层想获得的现实目标 准确细致地描述资源约束 管理科学小组与管理层的有效沟通 模型往往要不断地修改和扩展要进行what-if分析,Classical Applications of LP线性规划经典应用回顾(p20-21),应用回顾,为潘德罗索工业公司选择产品组合联合航空公司工作人员排程 Citgo石油集

27、团供应、配送 与营销的规划,Ponderosa Industrial潘德罗索工业公司,公司经验,潘德罗索应用成功的因素：以自然语言为用户界面的财务计划系统，使用自然语言而不是数学符号来显示线性规划模型各个组成部分以及输出的结果，使得做决策的管理者能够很容易看懂整个过程。最优化系统是互动的（interactive），管理者在从一个版本的模型中获得一组最优解之后，可以提出一系列的what-if问题，并能立即得到回应。,Personnel Scheduling at UA.联合航空公司人员排程,公司经验,联合航空公司利用线性规划，来为其在主要的机场和定票点的上万个工作人员安排每周的工作时间表。目标是

28、为了能够在满足客户的服务需要的同时，将一周内每天每半个小时的人员成本最小化。联合航空公司一些地点的规划模型却包括20，000个决策变量。应用成功最主要的因素是因为得到了运营经理以及其它员工的大力支持。,Citgo Petroleum CorporationCitgo石油集团,公司经验,Citgo石油集团运用管理科学的技术，特别是线性规划，建立供应、配送与营销的建模系统将公司主要产品的供应、配送与营销通过公司庞大的销售与配送网络得到很好的协调。在90年代中期创造了大量的财富。公司每种主要产品的模型都含有大约1，500个决策量以及3，000个确定需求的约束 最重要的成功因素是高层管理者所给予的无限

29、制的支持，并且设立运作协调副总裁，来负责评价与协调这一跨组织边界的模型所提供的建议,Session Summary本讲小结,小结,以符号表示的函数约束称为资源约束，这些限制要求使用的资源必须小于等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。以符号表示的函数约束为收益约束，形式为收益取得的水平必须大于等于最低可接受水平。收益约束反映了管理层所规定的目标。如果所有约束均为收益约束，这一问题为成本收益平衡问题。,Session Summary本讲小结,小结,以符号表示的函数约束称为确定需求的约束，它们表示了一定数量的确定的需求，提供的数量等于要求的数量。网络配送问题的

30、共性就是它们的主要函数约束为一种特定形式的确定需求的约束。不能归于这三类的任何线性规划的问题称为混合问题。在实际的应用当中，管理科学小组经常建立和分析大型的线性规划模型以指导管理决策，这些工作需要管理层足够强大的管理上的投入与支持，才能达到管理层实际的要求。,结束语 我们应该清楚：“应用线性规划解决经济，管理领域的实际问题时，最重要的一步是建立全面、准确地反映实际问题的线性规划模型”，这是一项技巧性很强的创造性工作，既要求对所研究的问题有深入了解，又要求很好掌握线性规划模型的结构特点，并具有对实际问题进行数学描述的较强能力。因此，在研究建立一些较复杂问题的数学模型时，需要各个方面的专业人员的通力协作配合。一般情况下，一个经济、管理问题要满足下列条件，才能归结为线性规划的模型！,数 据 模 型 决 策,结束语要求解的问题的目标能用某种效益指标度量大小，并能用线性函数描述目标的要求；为了达到这个目标存在多种方案；要达到的目标是在一定约束条件下实现的，这些条件可以用一组线性等式或不等式描述。,数 据 模 型 决 策,The End of Session 2,