运筹与决策之2线性规划

1、1,授课内容,Question 线性规划的概念和建模 线性规划的图解法 单纯形法基本步骤 计算机软件求解LP问题（下料优化） Case 2:基金（教材P51） 灵敏度分析(Case: 生产优化问题,2,1绪论 Introduction 2线性规划 Linear Programming 3运输问题 Transportation Models 4整数规划 Integer Programming 5网络模型 Network Models 6项目计划 PERT k =A,B,C,D)第i年初投k项目的资金数,max Z = 1.15x4A +1.40 x2C+1.25x3B+1.11x5D,25,2.

2、2 图解法,定义1:满足约束(1)、(2)的X=(X1 Xn)T称为LP问题的可行解，全部可行解集合称为可行域,定义2:满足(3)的可行解称为LP问题的最优解,26,图解法举例,例1、家具厂生产计划问题,A, B 各生产多少, 可获最大利润,27,建立模型 max Z = 40X1+ 50X2,建模后如何计算,28,解：(1)、确定可行域 X1 0 X1 =0 (横轴) X2 0 X2=0 (纵轴,X1+2X2 30 X1+2X2 =30 两点 (0,15)、 (30,0,3X1+2X2 =60 (0,30) (20,0,2X2 =24,X1,29,2)、求最优解,解：X* = (15,7.5

3、) Zmax =975,Z= 40X1+50X2 0=40X1+50X2 (0,0)， (10,-8,30,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集： 凸多边形,满足一组不等式约束的解,约束直线的交点,基本解,可行域的极点,基本可行解,目标函数等值线： 一组平行线,目标函数值等于一个常数的解,如何对应,31,图解法计算步骤,1）用字母表示可行域； （2）画出目标函数的平行线； （3） 注意目标函数的斜率； （4）适当的说明语句（包括可行域、最优解、目标函数值等,32,例2、图解法 max Z =40X1+ 80X2,33,0,X(

4、1)=(6,12) X(2)=(15,7.5) X= X(1)+(1-) X(2) (0 1,求解,最优解：BC线段 B点C点 无穷多解,34,35,无界 无有限最优解,X1,36,无解 无可行解,0,37,图解法总结,38,概念： 1 可行解? 2 可行域? 3 最优解,2.3 线性规划的基本理论,39,2.3 求解 LP问题的常见应用软件,LINDO GAMS Excel规划求解的举例 The Management Scientist Software （MS 6.0,40,LINDO（Linear Interactive and Discrete Optimizer）美国Lindo Sy

5、stem Inc,LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度快，易于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界得到广泛应用。 LINDO主要用于求解线性规划、非线性规划、二次规划和整数规划等问题。一般用于求解线性规划，整数规划问题。 LINDO 6 .1 学生版可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在104量级以上,41,LINDO的运行界面,42,GAMS（General Algebraic Modeling System）使用简介,GAMS（一般性代数仿真系统）的缩写，最早是由美国的世界银行(W

6、orld Bank)的Meeraus和Brooke所发展。GAMS是以简单清楚的使用者接口和强健稳定的数值分析能力见长。 对线性与非线性规划问题，GAMS使用MINOS算法，综合了缩减梯度法和准牛顿法，是专门为大型、复杂的线性与非线性问题设计的算法。对混合整数规划问题，采用ZOOM (Zero / One Optimization Method)算法。 GAMS的操作可分为三个步骤：建立GAMS输入文件，执行GAMS程序，GAMS输出文件,43,使用电子表格Excel求解线性规划,EXCEL规划求解solver的功能：可以解决线性规划、01规划以及整数线性规划等问题。 EXCEL中安装好“规划

7、求解”？ （菜单工具加载宏） 线性问题、非线性问题，变量限制200个，约束条件最多可达100个,44,应用计算机求解 LP问题,Excel规划求解的举例* 例：家具厂生产计划问题,45,计算机求解 LP问题的使用说明,1 在约束中使用的运算符有下列5个： =大于等于; int 整数; bin 二进制（0或1） 2 求解中用到下列概念： 目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。 3 可变单元格（目标函数、变量和约束条件） 例如，问题中B1、D6、D7格由公式构成，分别对应模型中的目标函数（如：B1=B3*B5+C3*C5）和约束条件；B5、C5为“可

8、变单元格”，分别对应模型中的变量。 4 求解过程（见Excel,46,Quantitative Methods in Practice,Linear Programming Integer Linear Programming PERT/CPM Inventory models Waiting Line Models Simulation,Decision Analysis Goal Programming Analytic Hierarchy Process Forecasting Markov-Process Models,47,The Management Scientist Softw

9、are,Modules,软件求解下料优化问题,48,Case课堂练习： Hart Venture Capital哈特风险基金（教材P51,1）两种投资各占多少比例？NPV? 2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少？ 3）如果HVC公司愿意在第1年追加100,000美元投资，对投资计划有何影响？ 4）追加100,000美元投资后的投资分配计划？ 5）你是否建议公司在第1年取消追加100,000美元,49,Case : Hart Venture Capital,LetS = fraction of the Security Systems project funded

10、by HVC M = fraction of the Market Analysis project funded by HVC,50,Case : Hart Venture Capital,1）两种投资各占多少比例？NPV? Objective Function Value = 2486956.522 the optimal solution is S = 0.609 and M = 0.870. 2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少,51,Case 3: Hart Venture Capital哈特风险基金P51,3）如果HVC公司愿意在第1年追加100,00

11、0美元投资，对投资计划有何影响？ Objective Function Value = 2550819.672 4）追加100,000美元投资后的投资分配计划,52,Case : Hart Venture Capital,5）你是否建议公司在第1年取消追加100,000美元,建议公司在第1年取消追加77049.180美元,53,第三章 LP灵敏度分析与最优解,图解法灵敏度分析 灵敏度分析：计算机求解 多于两个变量的情况,54,为什么要做灵敏度分析？ what-if （Sensitivity Analysis,如果在计划实施前或实施中有些因素已发生了改变，则决策者所关心的是目前所执行的计划还是不

12、是最优？企业应当作出什么样的反应，运用灵敏度分析而不需建立新的模型。 模型中目标函数系数哪个更能影响最优解 。 约束条件的右端值变化对最优解的影响,55,灵敏度分析对管理者的重要性,模型参数是粗略的估计值 获取所需数据必须付出许多的时间与精力 有些因素只有在研究完成后才能精确测量 what-if分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策,56,A（原材料消耗）代表企业的技术状况； b（资源供应量）代表企业的资源状况； C（价值系数）代表企业产品的市场状况； 在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值

13、决定,在生产计划问题的一般形式中，A，b，C各代表什么,如何回答,57,The Importance of What-If Analysis to Managers 灵敏度分析对管理者的重要性,模型参数是粗略的估计值 获取所需数据必须付出许多的时间与精力 有些因素只有在研究完成后才能精确测量 what-if分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策,58,灵敏度分析（4个方面,1. C(价格系数)变化的分析: 最优条件 CBB-1A C 0. 2.增加一个新变量(例如新产品投产)的分析: 如果最优条件CBB-1Pj - Cj 0满足，不生产; 如果满足CBB-1Pj -

14、Cj 0，新产品生产. 3. b(资源量)变化的分析: 最优条件B-1b0. 4. 增加一个新的约束条件的分析： 最优解满足约束条件，则不变； 最优解不满足约束条件，则用对偶单纯形法， 目标值变差,59,1)、参数A，b，C在什么范围内变动，对当前方案无影响,2)、参数A，b，C中的一个(几个)变动，对当前方案影响,3)、如果最优方案改变，如何用简便方法求新方案,60,递减成本（Reduced Costs）的经济意义,递减成本（CBB-1Pj -Cj）表示使目标函数中变量的值为正数时相应目标函数系数的改变量（最大化问题是增加；最小化问题是减小） 当某个变量对应的递减成本0，表示含义？ 见P70

15、 例3.4.1中图3-6的D产品的递减成本为1.15003，表明D的利润应增加1.15003元，D才能变为正值,61,经济解释,62,假设目标为max 对偶价格y （dual price）：b 的单位改变量所引起的目标函数改变量。 如果y的大小与系统内资源对目标的贡献有关，是资源的一种估价，又称为影子价格,对偶价格（影子价格）经济意义,63,对偶价格的准确经济意义与建模有关。 情况 模型中，目标函数系数Ci 表示利润时， yi 不是真正的影子价格，只表示资源bi 增加1单位时，企业目标增加的净利润,情况 模型中，目标函数系数Ci 表示成本时， yi 是真正的影子价格,对偶价格（影子价格）经济意

16、义,64,例 家具厂生产计划问题,胜利家具厂生产桌子和椅子两种家具。桌子售价50元个，椅子售价30元个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大,65,例家具厂生产问题的灵敏度分析,模型1：产品A(桌子)，B(椅子)销售价格发生变化，最优解是否改变？ 模型3：如果家具厂木工资源可能发生变化，要使生产计划不变，问木工工时b1变化范围如何? 模型2：设计一种新产品柜子, 售价100元, 单耗木工9工时、油漆工3工时问是

17、否投产? 模型4：若增加约束: 每月可用木材量是10立方米, 桌子单耗0.4立方米,椅子单耗0.3立方米。如何安排生产? 模型5：如果桌子价格降价10，而椅子价格上涨10，该问题的最优解是否发生变化,66,100法则（目标函数系数）P66,对所有变化的目标函数系数，允许的增量和允许的减量百分比之和未达到100%，最优解就不会改变。 模型5：如果桌子价格降价10，而椅子价格上涨10，如何,67,灵敏度分析的方法,图解法灵敏度分析（参见教材P57） 应用Excel的灵敏度分析 应用MS6.0的灵敏度分析,68,图解法灵敏度分析,69,判断新产品是否投产？方法：利用对偶价格（影子价格）概念,分析：找

18、出原问题的对偶解， 利用机会成本CBB 1Pj 。从最优表中可知：Y=CBB 1=(5,15,销售价格85元机会成本, 新产品不应生产,机会成本CBB 1Pj = 5915390,若柜子售价为100元，情况是否有变化,70,Case课堂练习： Truck Leasing Strategy 3-3 卡车租赁策略（教材P92,Xij表示第i月租赁卡车j月的数量，Yi表示第i月获得长期租赁卡车的数量,71,Case 3-3: Truck Leasing Strategy,MIN 6000X11+11400X12+15675X13+20160X14+6000X21+11400X22+15675X23+

19、6000X31+ 11400X32+6000X41+ 2000Y1+ 2000Y2+ 2000Y3+2000Y4 S.T. 1) 1X11+1X12+1X13+1X14+1Y1=10 2) 1X12+1X13+1X14+1X21+1X22+1X23+1Y2=12 3) 1X13+1X14+1X22+1X23+1X31+1X32+1Y3=14 4) 1X14+1X23+1X32+1X41+1Y4=8 5) 1Y11 6) 1Y22 7) 1Y33 8) 1Y41,72,1.租赁的最优方案The Management Scientist Software,Objective Function Va

20、lue = 203660.000 Variable Value Reduced Costs - - - X11 0.000 1515.000 X12 0.000 1725.000 X13 3.000 0.000 X14 6.000 0.000 X21 0.000 810.000 X22 0.000 210.000 X23 1.000 0.000 X31 1.000 0.000 X32 0.000 915.000 X41 0.000 1515.000 Y1 1.000 0.000 Y2 2.000 0.000 Y3 3.000 0.000 Y4 1.000 0.000,73,2.最优方案的租赁成

21、本（考虑裁员）An additional cost for layoff policy,74,3.最优方案的租赁成本（不考虑裁员） An additional cost for no layoff policy,75,第四章 线性规划模型的应用,4.1市场营销问题 石油公司的营销计划模型P96 媒体选择问题 市场调查问题 4.2财务管理问题 投资组合优化问题 财务计划问题 4.3营运管理问题 生产决策问题(make-or-buy) 生产计划问题（家乐士的最优化生产、库存以及分销） 劳动力分配问题 4.4产品配方(blending)问题,76,第5章 高级线性规划应用,5.1 数据包络分析（ D

22、ata Envelopment Analysis ）：用来衡量相同运营分公司的相对效率（例如快餐店、医院等） 。 5.2收入管理（Revenue Management）：适用于管理易逝品的短期需求，从而使组织有获得最大收入的潜力（例如酒店房间、机票预订、汽车出租等,77,原书第五章 LP单纯形法,单纯型法的基本思路 单纯形法基本步骤 单纯形表,78,单纯型法的基本思路,79,例2.1 生产计划问题,胜利家具厂生产桌子和椅子两种家具。桌子售价50元个，椅子售价30元个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大,80,问题求什么? 决策