运筹与决策之2线性规划.ppt

《运筹与决策之2线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹与决策之2线性规划.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、授课内容授课内容 Question线性规划的概念和建模线性规划的概念和建模线性规划的图解法线性规划的图解法单纯形法基本步骤单纯形法基本步骤计算机软件求解计算机软件求解LP问题（下料优化）问题（下料优化）Case 2:哈特风险哈特风险基金（教材基金（教材P51）灵敏度分析灵敏度分析(Case:生产优化问题生产优化问题)1绪论绪论Introduction2线性规划线性规划LinearProgramming3运输问题运输问题 TransportationModels4整数规划整数规划IntegerProgramming5网络模型网络模型NetworkModels6项目计划项目计划PERT&CPM7排

2、队论排队论QueueingModels8模拟模拟Simulation9决策分析决策分析DecisionTheory10多目标决策多目标决策Multi-objectiveDecision运筹与决策运筹与决策 目录目录2.1 线性规划的概念和模型线性规划的概念和模型l线性规划问题的导出线性规划问题的导出lOR在企业管理的具体应用在企业管理的具体应用例例1、家具厂生产计划问题、家具厂生产计划问题例例3、合理下料问题、合理下料问题l线性规划概念和模型线性规划概念和模型线性规划问题的导出线性规划问题的导出产品产品AB可用资源可用资源木工木工1230油漆工油漆工3260搬运工搬运工0224利润利润(￥)4

3、050例例1、家具厂生产计划问题、家具厂生产计划问题A,B各生产多少各生产多少,可获最大利润可获最大利润?如何建模？如何建模？Transforming Model Inputs into OutputUncontrollable InputsUncontrollable Inputs(Environmental Factors)(Environmental Factors)产品消耗系数、利润、可用资源产品消耗系数、利润、可用资源ControllableControllableInputsInputs(Decision(DecisionVariables)Variables)A,B各生产多少各生

4、产多少OutputOutput(Projected(Projected Results)Results)最大利润最大利润MathematicalMathematicalModelModel（见下页）（见下页）（见下页）（见下页）x1+2x2 30 3x1+2x2 602x2 24x1，x2 0maxZ=40 x1+50 x2解解:设产品设产品A,B产量分别为变量产量分别为变量x1，x2例例2 2 营养配餐营养配餐求：最低成本的原料混合方案求：最低成本的原料混合方案原料原料iAB每单位成本每单位成本1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8每单位添每单位添加剂

5、中维生加剂中维生12 14 8素最低含量素最低含量如何建模？如何建模？解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i=1,2,3,4)MinZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 142x2+x3+3x4 8xi 0(i=1,4)线性规划概念线性规划概念定义：定义：对于求取一组变量对于求取一组变量xj(j=1,2,.,n)，使之既，使之既满足线性约束条件，又使具有线性的目满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为标函数取得极值的一类最优化问题称为线性规划问题。线性规划问题。l要解决

6、的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映l对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择l有影响决策的若干约束条件有影响决策的若干约束条件线性规划模型的要求线性规划模型的要求WhyUseLinearProgramming?为什么要使用线性规划为什么要使用线性规划l线性规划很容易而有效率地被求解线性规划很容易而有效率地被求解l如果存在最优解，则必能够找到如果存在最优解，则必能够找到l功能强大的敏感性分析（功能强大的敏感性分析（sensitivityanalysis）l许多实际问题本质上是线性的许多实际问题本质上是线性的线性规划模型的特点线性规划模型的特

7、点l决策变量决策变量：向量：向量(x1xn)T决策人要决策人要考虑和控制的因素非负考虑和控制的因素非负l约束条件约束条件：线性等式或不等式：线性等式或不等式l目标函数目标函数：Z=(x1xn)线性式，求线性式，求Z极大或极小极大或极小一般式一般式max(min)Z=C1X1+C2X2+CnXna11X1+a12X2+a1nXn (=,(=,)b)b1 1a21X1+a22X2+a2nXn(=,(=,)b)b2 2am1X1+am2X2+amnXn(=,(=,)b)bm mXj j 0(0(j=1,n)隐含的假设隐含的假设l比例性比例性：决策变量变化引起目标的改变：决策变量变化引起目标的改变量与

8、决策变量改变量成正比量与决策变量改变量成正比l可加性可加性：每个决策变量对目标和约束的：每个决策变量对目标和约束的影响独立于其它变量影响独立于其它变量l连续性连续性：每个决策变量取连续值：每个决策变量取连续值l确定性确定性：线性规划中的参数：线性规划中的参数aij,bi,ci为确为确定值定值某钢筋架需要某钢筋架需要长度长度1.5m、2.1m和和2.9m各各100段段，每根标准钢筋长度为，每根标准钢筋长度为7.4m，问如何，问如何合理下料所需标准钢筋数目最少？合理下料所需标准钢筋数目最少？2.9m 1 2 0 1 0 2.9m 1 2 0 1 0 2.1m 0 0 2 2 1 2.1m 0 0

9、2 2 1 1.5m 3 1 2 0 3 1.5m 3 1 2 0 3 合计合计 7.4 7.3 7.2 7.1 6.67.4 7.3 7.2 7.1 6.6 料头料头 0 0.1 0.2 0.3 0.80 0.1 0.2 0.3 0.8例例3 3、合理下料问题、合理下料问题解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根minZ=0.1x2+0.2x3+0.3x4+0.8x5 x1+2x2+x4 =100 2x3+2x4+x5=1003x1+x2+2x3 +3x5=100 xi 0(i=1,5)如何正确建模？如何正确建模？该线性规划模型错误该线性规划模型错误l决策变量缺

10、少整数变量约束决策变量缺少整数变量约束l约束条件为等式约束条件为等式l用余料作为目标函数用余料作为目标函数l下料方式不全（少下料方式不全（少3种下料方式）种下料方式）解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根minZ=x1+x2+x3+x4+x5+x6+x7+x8 2x1+x2+x3+x4 100 2x2+x3+3x5+2x6+x7 100 x1+x3+3x4 +2x6+3x7 +4x8 100 xi 0(i=1,8)，且为整数且为整数如何建模？如何建模？例例4 4、运输问题、运输问题某公司有三个分厂分别供应三个市场，某公司有三个分厂分别供应三个市场，具体生产能力和

11、需求量如下表：具体生产能力和需求量如下表：如何建模？如何建模？市场市场1市场市场2市场市场3产量产量工厂工厂121350工厂工厂222430工厂工厂334210需求需求401535设设xij为为i工厂运到工厂运到j市场的产品数量市场的产品数量(i1，2，3，j 1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31 +4x32+2x33x11+x12+x13 50 x21+x22+x23 30 x31+x32+x33 10 x11+x21+x31=40 x12+x22+x32=15x13+x23+x33=35 xij 0例例5 5、连续投资、连续投资1010万

12、元万元lA：从第：从第1年年到第到第4年每年初要投资，次年末回年每年初要投资，次年末回收本利收本利1.15lB：第第3年初投资，到第年初投资，到第5年末回收年末回收1.25，最大，最大投资投资4万元万元lC：第第2年初投资，到第年初投资，到第5年末回收年末回收1.40，最大，最大投资投资3万元万元lD：每年初投资，每年末回收每年初投资，每年末回收1.11。求：求：5 5年末总资本最大年末总资本最大如何建模？如何建模？分析分析 12345Ax1A x2A x3A x4A Bx3BCx2CDx1D x2D x3D x4D x5D Xik(i=1,2,5;k=A,B,C,D)第第i年初投年初投k项目

13、的资金数项目的资金数maxZ=1.15x4A+1.40 x2C+1.25x3B+1.11x5Dx1A+x1D 10 x2A+x2C+x2D=1.11 x1Dx2C 3x3A+x3B+x3D=1.15 x1A+1.11 x2Dx3B 4x4A+x4D=1.15 x2A+1.11 x3Dx5D=1.15 x3A+1.11 x4D xik 02.2 图解法图解法AX=b(1)X 0 (2)maxZ=CX(3)定义定义1 1:满足约束满足约束(1)、(2)的的X=(X1 Xn)T称为称为LP问题的问题的可行解可行解，全部可行解集合称为，全部可行解集合称为可行域。可行域。定义定义2 2:满足满足(3)的

14、可行解称为的可行解称为LP问题的问题的最优解。最优解。图解法举例图解法举例产品产品AB备用资源备用资源木工木工1230油漆工油漆工3260搬运工搬运工0224利润利润4050例例1、家具厂生产计划问题、家具厂生产计划问题A,B各生产多少各生产多少,可获最大利润可获最大利润?建立模型建立模型maxZ=40X1+50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 ,X2 0 0建模后如何计算？建模后如何计算？解：解：(1)、确定可行域、确定可行域X1 0 0 X1=0=0(横轴横轴)X2 0 0 X2=0=0(纵轴纵轴)X1+2X2 30X1+2X2=30两点两点(0,15)、(

15、30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)2X2=24X1(2)、求最优解、求最优解解：解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2 (0,0)，(10,-8)0203010102030X1X2DABCDABCC点：点：X1+2X2=303X1+2X2=60几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集：约束半平面的交集：凸多边形凸多边形满足一组不等式约束的解满足一组不等式约束的解约

16、束直线的交点约束直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线：目标函数等值线：一组平行线一组平行线目标函数值等于一个常目标函数值等于一个常数的解数的解如何对应？如何对应？图解法计算步骤图解法计算步骤（1）用字母表示可行域；）用字母表示可行域；（2）画出目标函数的平行线；）画出目标函数的平行线；（3）注意目标函数的斜率；注意目标函数的斜率；（4）适适当当的的说说明明语语句句（包包括括可可行行域域、最最优优解、目标函数值等）解、目标函数值等）例例2、图解法、图解法max Z=40X1+80X2 X1+2X2 30 3X1+2X2 60 2X2 24 X1,X2

17、0 00Z=40 X1+80X2=0 X1+2X2=30DABCX2X1X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)求解求解最优解：最优解：BCBC线段线段B B点点C C点点无穷多解无穷多解X1=6+(1-)15X2=12+(1-)7.5X1=15-9 X2=7.5+4.5 (0 1)X=+(1-)max Z=1200 X1 6 15 X2 12 7.5无界无界无有限最优解无有限最优解例例3、max Z=2X1+4X2 2X1+X2 8 8-2X1+X2 2X1,X2 0 0Z=0-2X1+X2=28246X22X1+X2=840X1例例4、max

18、Z=3X1+2X2-X1-X2 1 1X1,X2 0 0无解无解无可行解无可行解-1X2-1X10图解法总结图解法总结唯一解唯一解无穷多解无穷多解无有限最优解无有限最优解无可行解无可行解有解有解无解无解AX=b(1)X 0 (2)maxZ=CX(3)概念：概念：1 1 可行解可行解?2 2 可行域可行域?3 3 最优解最优解?2.3 线性规划的基本理论线性规划的基本理论2.3 求解求解 LP问题的常见应用软件问题的常见应用软件1.LINDO2.GAMS3.Excel规划求解规划求解的举例的举例4.TheManagementScientistSoftware（MS6.0）LINDO（Linear

19、 Interactive and Discrete OptimizerLinear Interactive and Discrete Optimizer）美国美国Lindo System Inc.LINDOLINDO是是是是一一一一种种种种专专专专门门门门用用用用于于于于求求求求解解解解数数数数学学学学规规规规划划划划问问问问题题题题的的的的软软软软件件件件包包包包。由由由由于于于于LINDOLINDO执执执执行行行行速速速速度度度度快快快快，易易易易于于于于方方方方便便便便地地地地输输输输入入入入、求求求求解解解解和和和和分分分分析析析析数数数数学学学学规规规规划划划划问问问问题题题题，因因

20、因因此此此此在在在在教教教教学学学学、科研和工业界得到广泛应用。科研和工业界得到广泛应用。科研和工业界得到广泛应用。科研和工业界得到广泛应用。LINDOLINDO主主主主要要要要用用用用于于于于求求求求解解解解线线线线性性性性规规规规划划划划、非非非非线线线线性性性性规规规规划划划划、二二二二次次次次规规规规划划划划和和和和整整整整数数数数规规规规划划划划等等等等问问问问题题题题。一一一一般般般般用用用用于于于于求求求求解解解解线线线线性性性性规规规规划，整数划，整数划，整数划，整数规规规规划划划划问题问题问题问题。LINDOLINDO6 6.1.1学学学学生生生生版版版版可可可可求求求求解解

21、解解多多多多达达达达300300个个个个变变变变量量量量和和和和150150个个个个约约约约束束束束的的的的规规规规划划划划问问问问题题题题。其其其其正正正正式式式式版版版版（标标标标准准准准版版版版）则则则则可可可可求解的变量和约束在求解的变量和约束在求解的变量和约束在求解的变量和约束在104104量级以上。量级以上。量级以上。量级以上。LINDO的运行界面的运行界面GAMS（GeneralAlgebraicModelingSystem）使用简介）使用简介GAMSGAMS（一一一一般般般般性性性性代代代代数数数数仿仿仿仿真真真真系系系系统统统统）的的的的缩缩缩缩写写写写，最最最最早早早早是是

22、是是由由由由美美美美国国国国的的的的世世世世界界界界银银银银行行行行(World(WorldBank)Bank)的的的的MeerausMeeraus和和和和BrookeBrooke所所所所发发发发展展展展。GAMSGAMS是是是是以以以以简简简简单单单单清清清清楚楚楚楚的的的的使使使使用用用用者者者者接接接接口口口口和和和和强强强强健健健健稳定的数值分析能力见长。稳定的数值分析能力见长。稳定的数值分析能力见长。稳定的数值分析能力见长。对对对对线线线线性性性性与与与与非非非非线线线线性性性性规规规规划划划划问问问问题题题题，GAMSGAMS使使使使用用用用MINOSMINOS算算算算法法法法，综

23、综综综合合合合了了了了缩缩缩缩减减减减梯梯梯梯度度度度法法法法和和和和准准准准牛牛牛牛顿顿顿顿法法法法，是是是是专专专专门门门门为为为为大大大大型型型型、复复复复杂杂杂杂的的的的线线线线性性性性与与与与非非非非线线线线性性性性问问问问题题题题设设设设计计计计的的的的算算算算法法法法。对对对对混混混混合合合合整整整整数数数数 规规规规 划划划划 问问问问 题题题题，采采采采 用用用用 ZOOMZOOM(Zero(Zero/OneOneOptimizationMethod)OptimizationMethod)算法。算法。算法。算法。GAMSGAMS的的的的操操操操作作作作可可可可分分分分为为为为

24、三三三三个个个个步步步步骤骤骤骤：建建建建立立立立GAMSGAMS输输输输入入入入文文文文件，执行件，执行件，执行件，执行GAMSGAMS程序，程序，程序，程序，GAMSGAMS输出文件。输出文件。输出文件。输出文件。使用电子表格使用电子表格Excel求解线性求解线性规划规划vEXCEL规划求解规划求解solver的功能：可以解决的功能：可以解决线性规划、线性规划、01规划以及整数线性规划等规划以及整数线性规划等问题。问题。vEXCEL中安装好中安装好“规划求解规划求解”？v（菜单（菜单工具工具加载宏）加载宏）v线性问题、非线性问题，变量限制线性问题、非线性问题，变量限制200个，个，约束条件

25、最多可达约束条件最多可达100个。个。应用计算机求解应用计算机求解 LP问题问题Excel规划求解的举例规划求解的举例*例：家具厂生产计划问题例：家具厂生产计划问题计算机求解计算机求解 LP问题的使用说明问题的使用说明1在约束中使用的在约束中使用的运算符运算符有下列有下列5个：个：=大于等于大于等于;int整数整数;bin二进制（二进制（0或或1）2求解中用到下列概念：求解中用到下列概念：目标单元格最大值（最小值）：指满足可变单元格约目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。束条件后，单元格可取的最大值（最小值）。3可变单元格可变单元格（目标函数、变

26、量和约束条件）（目标函数、变量和约束条件）例如，问题中例如，问题中B1、D6、D7格由公式构成，分别对应格由公式构成，分别对应模型中的目标函数（如：模型中的目标函数（如：B1=B3*B5+C3*C5）和约束）和约束条件；条件；B5、C5为为“可变单元格可变单元格”，分别对应模型中，分别对应模型中的变量。的变量。4求解过程（见求解过程（见Excel）Quantitative Methods in Practicen nLinear ProgrammingLinear Programmingn nInteger Linear Integer Linear ProgrammingProgrammin

27、gn nPERT/CPMPERT/CPMn nInventory modelsInventory modelsn nWaiting Line ModelsWaiting Line Modelsn nSimulationSimulationn nDecision AnalysisDecision Analysisn nGoal ProgrammingGoal Programmingn nAnalytic Hierarchy Analytic Hierarchy ProcessProcessn nForecastingForecastingn nMarkov-Process ModelsMarko

28、v-Process ModelsThe Management Scientist SoftwareModulesModules软件求解下料优化问题软件求解下料优化问题Case课堂练习：课堂练习：Hart Venture Capital哈特风险基金（教材哈特风险基金（教材P51）1 1）两种投资各占多少比例？）两种投资各占多少比例？）两种投资各占多少比例？）两种投资各占多少比例？NPV?NPV?2 2）接接接接下下下下来来来来3 3年年年年为为为为两两两两个个个个公公公公司司司司的的的的资资资资金金金金分分分分配配配配计计计计划划划划？HVCHVC每年投资的总额是多少？每年投资的总额是多少？每年

29、投资的总额是多少？每年投资的总额是多少？3 3）如如如如果果果果HVCHVC公公公公司司司司愿愿愿愿意意意意在在在在第第第第1 1年年年年追追追追加加加加100,000100,000美美美美元投资，对投资计划有何影响？元投资，对投资计划有何影响？元投资，对投资计划有何影响？元投资，对投资计划有何影响？4 4）追加）追加）追加）追加100,000100,000美元投资后的投资分配计划？美元投资后的投资分配计划？美元投资后的投资分配计划？美元投资后的投资分配计划？5 5）你你你你是是是是否否否否建建建建议议议议公公公公司司司司在在在在第第第第1 1年年年年取取取取消消消消追追追追加加加加100,0

30、00100,000美元？美元？美元？美元？Case:Hart Venture CapitallLet S=fraction of the Security Systems project funded by HVClM=fraction of the Market Analysis project funded by HVC Case:Hart Venture Capital1 1）两两两两种种种种投投投投资资资资各各各各占占占占多多多多少比例？少比例？少比例？少比例？NPV?NPV?ObjectiveObjectiveFunctionFunctionValue=2486956.522Valu

31、e=2486956.522 thetheoptimaloptimalsolutionsolutionisisS S=0.6090.609andandMM=0.870.0.870.2 2）接接接接下下下下来来来来3 3年年年年为为为为两两两两个个个个公公公公司司司司的的的的资资资资金金金金分分分分配配配配计计计计划划划划？HVCHVC每每每每年年年年投投投投资的总额是多少？资的总额是多少？资的总额是多少？资的总额是多少？Case 3:Hart Venture Capital哈特风险基金哈特风险基金P513 3）如如如如果果果果HVCHVC公公公公司司司司愿愿愿愿意意意意在在在在第第第第1 1年年

32、年年追追追追加加加加100,000100,000美美美美元投资，对投资计划有何影响？元投资，对投资计划有何影响？元投资，对投资计划有何影响？元投资，对投资计划有何影响？ObjectiveFunctionValue=2550819.672ObjectiveFunctionValue=2550819.672 4 4）追加）追加）追加）追加100,000100,000美元投资后的投资分配计划？美元投资后的投资分配计划？美元投资后的投资分配计划？美元投资后的投资分配计划？Case:Hart Venture Capital5）你你是是否否建建议议公公司司在在第第1年年取取消消追追加加100,000美元？

33、美元？建议公司在第建议公司在第1年取消追加年取消追加77049.180美元美元第三章第三章 LP灵敏度分析与最优解灵敏度分析与最优解l图解法灵敏度分析图解法灵敏度分析l灵敏度分析：计算机求解灵敏度分析：计算机求解l多于两个变量的情况多于两个变量的情况为什么要做灵敏度分析？为什么要做灵敏度分析？what-if（Sensitivity Analysis）l如果在计划实施前或实施中有些因素已发如果在计划实施前或实施中有些因素已发生了改变，则决策者所关心的是目前所执生了改变，则决策者所关心的是目前所执行的计划还行的计划还是不是最优是不是最优？企业应当作出什？企业应当作出什么样的反应，运用灵敏度分析而么

34、样的反应，运用灵敏度分析而不需建立不需建立新的模型。新的模型。l模型中模型中目标函数系数目标函数系数哪个更能影响最优解哪个更能影响最优解。l约束条件的约束条件的右端值变化右端值变化对最优解的影响。对最优解的影响。灵敏度分析对管理者的重要性灵敏度分析对管理者的重要性l模型参数是粗略的模型参数是粗略的估计值估计值 l获取所需数据必须付出许多的获取所需数据必须付出许多的时间与精力时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat-if分析表明改变这些决策对结果的影分析表明改变这些决策对结果的影响，从而有效指导管理者作出响，从而有效指导管理者作

35、出最终决策最终决策A（原材料消耗）（原材料消耗）代表企业的技术状况；代表企业的技术状况；b（资源供应量）（资源供应量）代表企业的资源状况；代表企业的资源状况；C（价值系数）（价值系数）代表企业产品的市场状况；代表企业产品的市场状况；在这些因素（原材料消耗系数、资源供应量、在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业的最优生产计价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值划和最大利润由线性规划的最优解和最优值决定。决定。在生产计划问题的一般形式在生产计划问题的一般形式中，中，A，b，C各代表什么各代表什么？标准型标准型 max Z=CX AX

36、=b X 0如何回答？如何回答？The Importance of What-If Analysis to Managers 灵敏度分析对管理者的重要性灵敏度分析对管理者的重要性l模型参数是粗略的估计值模型参数是粗略的估计值 l获取所需数据必须付出许多的时间与精力获取所需数据必须付出许多的时间与精力l有些因素只有在研究完成后才能精确测量有些因素只有在研究完成后才能精确测量lwhat-ifwhat-if分析表明改变这些决策对结果的影分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策响，从而有效指导管理者作出最终决策灵敏度分析（灵敏度分析（4个方面）个方面）1.C(价格系数价格系数)

37、变化的分析变化的分析:最优条件最优条件CBB-1AC0.2.增加一个新变量增加一个新变量(例如新产品投产例如新产品投产)的分析的分析:如果最优条件如果最优条件CBB-1Pj-Cj0满足，不生产满足，不生产;如果满足如果满足CBB-1Pj-Cj0，新产品生产，新产品生产.3.b(资源量资源量)变化的分析变化的分析:最优条件最优条件B-1b0.4.增加一个新的约束条件的分析：增加一个新的约束条件的分析：最优解满足约束条件，则不变；最优解满足约束条件，则不变；最优解不满足约束条件，则用对偶单纯形法，最优解不满足约束条件，则用对偶单纯形法，目标值变差。目标值变差。标准型标准型 max Z=CX AX=

38、b X 0(1)、参数、参数A，b，C在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个)变动，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？递减成本（递减成本（Reduced Costs）的）的经济意义经济意义l递减成本（递减成本（CBB-1Pj-Cj）表示使目标函数中表示使目标函数中变量的值为正数时相应目标函数系数的改变变量的值为正数时相应目标函数系数的改变量（最大化问题是增加；最小化问题是减小）量（最大化问题是增加；最小化问题是

39、减小）l当某个变量对应的当某个变量对应的递减成本递减成本0，表示含义？，表示含义？l见见P70例中图例中图3-6的的D产品的递减成本为产品的递减成本为1.15003，表明，表明D的利润应增加的利润应增加1.15003元，元，D才能变为正值。才能变为正值。经济解释：经济解释：W=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ymbi：第第 i 种资源的数量种资源的数量yi：对偶价格：对偶价格bi增加增加 bi,其它资源数量不变时其它资源数量不变时,目标函数目标函数的增量的增量 Z=bi yiyi：反映：反映bi 的边际效益的边际效益(边际成本边际成本)l假设目标为假设目标为maxl

40、对偶价格对偶价格y（dualprice）：）：b的单位改变量的单位改变量所引起的目标函数改变量。所引起的目标函数改变量。l如果如果y的大小与系统内资源对目标的贡献有的大小与系统内资源对目标的贡献有关，是资源的一种估价，关，是资源的一种估价，又称为影子价格又称为影子价格。对偶价格（影子价格）经济意义对偶价格（影子价格）经济意义对偶价格的准确经济意义与建模有关。对偶价格的准确经济意义与建模有关。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示利润时，表示利润时，yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单单位时，企业目标增加的净利润。位时，企

41、业目标增加的净利润。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时，yi 是真正的影子价格。是真正的影子价格。对偶价格（影子价格）经济意义对偶价格（影子价格）经济意义例例 家具厂生产计划问题家具厂生产计划问题胜胜利利家家具具厂厂生生产产桌桌子子和和椅椅子子两两种种家家具具。桌桌子子售售价价50元元个个，椅椅子子售售价价30元元个个，生生产产桌桌子子和和椅椅子子需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4小小时时，油油漆漆工工2小小时时。生生产产一一个个椅椅子子需需要要木木工工3小小时时，油油漆漆工工1小小时时。该该

42、厂厂每每月月可可用用木木工工工工时时为为120小小时时，油油漆漆工工工工时时为为50小时。问该厂如何组织生产才能使每月的销售收入最大？小时。问该厂如何组织生产才能使每月的销售收入最大？资源资源单耗单耗产品产品桌子桌子椅子椅子资源限量资源限量木工木工43120小时小时油漆工油漆工2150小时小时售价售价(元个元个)5030例家具厂生产问题的灵敏度分析例家具厂生产问题的灵敏度分析l模型模型1 1：产品：产品A(A(桌子桌子)，B(B(椅子椅子)销售价格发生销售价格发生变化，最优解是否改变？变化，最优解是否改变？l模型模型3 3：如果家具厂木工资源可能发生变化，：如果家具厂木工资源可能发生变化，要使

43、生产计划不变，问木工工时要使生产计划不变，问木工工时b1b1变化范围变化范围如何如何?l模型模型2 2：设计一种新产品柜子：设计一种新产品柜子,售价售价100100元元,单耗木工单耗木工9 9工时、油漆工工时、油漆工3 3工时问是否投产工时问是否投产?l模型模型4 4：若增加约束：若增加约束:每月可用木材量是每月可用木材量是1010立立方米方米,桌子单耗桌子单耗0.40.4立方米立方米,椅子单耗椅子单耗0.30.3立方立方米。如何安排生产米。如何安排生产?l模型模型5 5：如果桌子价格降价：如果桌子价格降价1010，而椅子价格，而椅子价格上涨上涨1010，该问题的最优解是否发生变化？，该问题的

44、最优解是否发生变化？100法则（目标函数系数）法则（目标函数系数）P66l对所有变化的目标函数系数，对所有变化的目标函数系数，允许的增允许的增量和允许的减量百分比之和未达到量和允许的减量百分比之和未达到100%100%，最优解就不会改变。，最优解就不会改变。l模型模型5 5：如果桌子价格：如果桌子价格降价降价1010，而椅子而椅子价格价格上涨上涨1010，如何？如何？目标式目标式系数系数允许的允许的增量增量允许的允许的减量减量5010101010307.57.55 5灵敏度分析的方法灵敏度分析的方法l图解法灵敏度分析图解法灵敏度分析（参见教材（参见教材P57P57）l应用应用ExcelExce

45、l的灵敏度分析的灵敏度分析l应用应用MS6.0MS6.0的灵敏度分析的灵敏度分析图解法灵敏度分析图解法灵敏度分析判断新产品是否投产？判断新产品是否投产？方法：利用对偶价格（影子价格）概念方法：利用对偶价格（影子价格）概念分析：找出原问题的对偶解，分析：找出原问题的对偶解，利用机会成本利用机会成本C CB BB B 1 1Pj j。从最优表中可知：。从最优表中可知：Y=CY=CB BB B 1 1=(5,15)(5,15)。销售价格销售价格85元元机会成本机会成本,新产品不应生产新产品不应生产!机会成本机会成本C CB BB B 1 1Pj j=59=591531539090若柜子售价为若柜子售

46、价为100元，情况是否有变化元，情况是否有变化?Case课堂练习：课堂练习：Truck Leasing Strategy 3-3 卡车租赁策略（教材卡车租赁策略（教材P92）XijXij表表表表示示示示第第第第i i月月月月租租租租赁赁赁赁卡卡卡卡车车车车j j月月月月的的的的数数数数量量量量，YiYi表表表表示第示第示第示第i i月获得长期租赁卡车的数量月获得长期租赁卡车的数量月获得长期租赁卡车的数量月获得长期租赁卡车的数量Case 3-3:Truck Leasing Strategy MIN 6000X11+11400X12+15675X13+20160X14+6000X21+11400X

47、22+15675X23+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)1Y4 0 0，Pk全全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全

48、 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。=min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为为主元。主元。由最小由最小比值法求：比值法求：maxmax j=m+kXm+k 换入变量换入变量 j00(4)、转转(2)(2)m+k 0 a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k=(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代第一次作业（下周课前交）第一次作业（下周课前交）lP15-17l图解法图解法1.2l管理建模管理建模1.15，1.18，l灵敏度分析灵敏度分析2.11l思考题：思考题：lOR在企业应用的前景在企业应用的前景下次课内容下次课内容 Case：卡车租赁策略（教材：卡车租赁策略（教材P92）3运输问题运输问题