运筹与决策之线性规划演示文稿

运筹与决策之线性规划演示文稿1第一页，共八十七页。1绪论—Introduction2线性规划—LinearProgramming3运输问题

—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8

模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《运筹与决策》目录2第二页，共八十七页。§2.1线性规划的概念和模型线性规划问题的导出OR在企业管理的具体应用例1、家具厂生产计划问题例3、合理下料问题线性规划概念和模型3第三页，共八十七页。线性规划问题的导出

产品AB 可用资源木工1230

油漆工3260

搬运工0224

利润(￥)

4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?如何建模？4第四页，共八十七页。TransformingModelInputsintoOutputUncontrollableInputs(EnvironmentalFactors)产品消耗系数、利润、可用资源ControllableInputs(DecisionVariables)A,B各生产多少Output(ProjectedResults)最大利润MathematicalModel（见下页）5第五页，共八十七页。x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0maxZ=40x1+50x2解:设产品A,B产量分别为变量x1

，x26第六页，共八十七页。例2营养配餐求：最低成本的原料混合方案

原料iABＣ每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量如何建模？7第七页，共八十七页。解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)MinZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)8第八页，共八十七页。线性规划概念定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。9第九页，共八十七页。要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划模型的要求10第十页，共八十七页。WhyUseLinearProgramming?为什么要使用线性规划线性规划很容易而有效率地被求解如果存在最优解，则必能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的11第十一页，共八十七页。线性规划模型的特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小12第十二页，共八十七页。一般式max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)13第十三页，共八十七页。14第十四页，共八十七页。隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值15第十五页，共八十七页。某钢筋架需要长度1.5m、2.1m和2.9m各100段，每根标准钢筋长度为7.4m，问如何合理下料所需标准钢筋数目最少？

ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203

合计

7.47.37.27.16.6

料头00.10.20.30.8例3、合理下料问题16第十六页，共八十七页。解：设按第i种方案下料的原材料为xi根minZ=0.1x2

+0.2x3+0.3x4+0.8x5x1+2x2+x4=1002x3+2x4+x5=100

3x1+x2+2x3+3x5=100

xi

0(i=1,…,5)如何正确建模？17第十七页，共八十七页。该线性规划模型错误决策变量缺少整数变量约束约束条件为等式用余料作为目标函数下料方式不全（少3种下料方式）18第十八页，共八十七页。解：设按第i种方案下料的原材料为xi根minZ=x1+

x2

+x3+x4+x5+x6+x7+x82x1+x2+x3+x41002x2

+x3+3x5+2x6+x7100x1+x3+3x4+2x6+3x7

+4x8100

xi

0(i=1,…,8)，且为整数如何建模？19第十九页，共八十七页。例4、运输问题某公司有三个分厂分别供应三个市场，具体生产能力和需求量如下表：如何建模？

市场1市场2市场3产量工厂121350工厂222430工厂334210

需求40153520第二十页，共八十七页。设xij为i

工厂运到j市场的产品数量(i

＝1，2，3，j＝1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

021第二十一页，共八十七页。例5、连续投资10万元A：从第1年到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大如何建模？22第二十二页，共八十七页。[分析]

12345Ax1A

x2A

x3A

x4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D23第二十三页，共八十七页。Xik(i=1,2,…,5;k=A,B,C,D)第i年初投k项目的资金数maxZ=1.15x4A+1.40x2C+1.25x3B+1.11x5Dx1A+x1D10x2A+x2C+x2D=1.11x1Dx2C

3x3A+x3B+x3D=1.15x1A+

1.11x2Dx3B4x4A+x4D=1.15x2A+

1.11x3Dx5D=1.15x3A+

1.11x4Dxik

0第二十四页，共八十七页。§2.2图解法AX=b(1)X

0(2)maxZ=CX(3)定义1:满足约束(1)、(2)的X=(X1…Xn)T称为LP问题的可行解，全部可行解集合称为可行域。定义2:满足(3)的可行解称为LP问题的最优解。25第二十五页，共八十七页。图解法举例

产品AB备用资源木工1230

油漆工3260

搬运工0224

利润4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?26第二十六页，共八十七页。建立模型maxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20建模后如何计算？27第二十七页，共八十七页。解：(1)、确定可行域

X10X1=0(横轴)X20X2=0(纵轴)X1+2X230X1+2X2=30两点(0,15)、(30,0)2030100102030X2DABC3X1+2X2=60(0,30)(20,0)

2X2=24X128第二十八页，共八十七页。(2)、求最优解解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)0203010102030X1X2DABCDABCC点：X1+2X2=30

3X1+2X2=6029第二十九页，共八十七页。几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基本解可行域的极点基本可行解目标函数等值线：一组平行线目标函数值等于一个常数的解如何对应？30第三十页，共八十七页。图解法计算步骤（1）用字母表示可行域；（2）画出目标函数的平行线；（3）

注意目标函数的斜率；（4）适当的说明语句（包括可行域、最优解、目标函数值等）31第三十一页，共八十七页。例2、图解法

maxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X2032第三十二页，共八十七页。0Z=40X1+80X2=0

X1+2X2=30DABCX2X1X(1)=(6,12)X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)求解最优解：BC线段B点——C点无穷多解33第三十三页，共八十七页。X1=6++(1-)·15X2=12++(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.534第三十四页，共八十七页。无界无有限最优解例3、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=0-2X1+X2=28246X22X1+X2=840X135第三十五页，共八十七页。例4、maxZ=3X1+2X2-X1-X21X1,X20无解无可行解-1X2-1X1036第三十六页，共八十七页。图解法总结

唯一解无穷多解无有限最优解无可行解有解无解37第三十七页，共八十七页。AX=b(1)X

0(2)maxZ=CX(3)概念：1可行解?2可行域?3最优解?2.3线性规划的基本理论38第三十八页，共八十七页。2.3求解LP问题的常见应用软件LINDOGAMSExcel规划求解的举例TheManagementScientistSoftware（MS6.0）39第三十九页，共八十七页。LINDO（LinearInteractiveandDiscreteOptimizer）

－美国LindoSystemInc.

LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度快，易于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界得到广泛应用。LINDO主要用于求解线性规划、非线性规划、二次规划和整数规划等问题。一般用于求解线性规划，整数规划问题。LINDO6.1学生版可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在10^4量级以上。40第四十页，共八十七页。LINDO的运行界面41第四十一页，共八十七页。GAMS（GeneralAlgebraicModelingSystem）使用简介GAMS（一般性代数仿真系统）的缩写，最早是由美国的世界银行(WorldBank)的Meeraus和Brooke所发展。GAMS是以简单清楚的使用者接口和强健稳定的数值分析能力见长。

对线性与非线性规划问题，GAMS使用MINOS算法，综合了缩减梯度法和准牛顿法，是专门为大型、复杂的线性与非线性问题设计的算法。对混合整数规划问题，采用ZOOM(Zero/OneOptimizationMethod)算法。

GAMS的操作可分为三个步骤：建立GAMS输入文件，执行GAMS程序，GAMS输出文件。42第四十二页，共八十七页。使用电子表格Excel求解线性规划EXCEL规划求解solver的功能：可以解决线性规划、0－1规划以及整数线性规划等问题。EXCEL中安装好“规划求解”？（菜单——工具——加载宏）线性问题、非线性问题，变量限制200个，约束条件最多可达100个。43第四十三页，共八十七页。应用计算机求解LP问题Excel规划求解的举例*例：家具厂生产计划问题44第四十四页，共八十七页。计算机求解LP问题的使用说明1在约束中使用的运算符有下列5个：

<=小于等于;=等于;>=大于等于;int整数;bin二进制（0或1）2求解中用到下列概念：目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。3可变单元格（目标函数、变量和约束条件）例如，问题中B1、D6、D7格由公式构成，分别对应模型中的目标函数（如：B1=B3*B5+C3*C5）和约束条件；B5、C5为“可变单元格”，分别对应模型中的变量。4求解过程（见Excel）45第四十五页，共八十七页。QuantitativeMethodsinPracticeLinearProgrammingIntegerLinearProgrammingPERT/CPMInventorymodelsWaitingLineModelsSimulationDecisionAnalysisGoalProgrammingAnalyticHierarchyProcessForecastingMarkov-ProcessModels46第四十六页，共八十七页。TheManagementScientistSoftwareModules软件求解下料优化问题47第四十七页，共八十七页。Case课堂练习：HartVentureCapital

哈特风险基金（教材P51）1）两种投资各占多少比例？NPV?2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少？3）如果HVC公司愿意在第1年追加100,000美元投资，对投资计划有何影响？4）追加100,000美元投资后的投资分配计划？5）你是否建议公司在第1年取消追加100,000美元？48第四十八页，共八十七页。Case:HartVentureCapitalLet S=fractionoftheSecuritySystemsprojectfundedbyHVCM=fractionoftheMarketAnalysisprojectfundedbyHVC49第四十九页，共八十七页。Case:HartVentureCapital1）两种投资各占多少比例？NPV?ObjectiveFunctionValue=2486956.522

theoptimalsolutionisS=0.609andM=0.870.

2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少？50第五十页，共八十七页。Case3:HartVentureCapital

哈特风险基金P513）如果HVC公司愿意在第1年追加100,000美元投资，对投资计划有何影响？ObjectiveFunctionValue=2550819.672

4）追加100,000美元投资后的投资分配计划？51第五十一页，共八十七页。Case:HartVentureCapital5）你是否建议公司在第1年取消追加100,000美元？建议公司在第1年取消追加77049.180美元52第五十二页，共八十七页。第三章LP灵敏度分析与最优解图解法灵敏度分析灵敏度分析：计算机求解多于两个变量的情况53第五十三页，共八十七页。为什么要做灵敏度分析？

what-if（SensitivityAnalysis）如果在计划实施前或实施中有些因素已发生了改变，则决策者所关心的是目前所执行的计划还是不是最优？企业应当作出什么样的反应，运用灵敏度分析而不需建立新的模型。模型中目标函数系数哪个更能影响最优解。约束条件的右端值变化对最优解的影响。54第五十四页，共八十七页。灵敏度分析对管理者的重要性模型参数是粗略的估计值获取所需数据必须付出许多的时间与精力有些因素只有在研究完成后才能精确测量what-if分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策55第五十五页，共八十七页。A（原材料消耗）代表企业的技术状况；b（资源供应量）代表企业的资源状况；C（价值系数）代表企业产品的市场状况；在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在生产计划问题的一般形式中，A，b，C各代表什么？标准型maxZ=CX

AX

=bX0如何回答？56第五十六页，共八十七页。TheImportanceofWhat-IfAnalysistoManagers

灵敏度分析对管理者的重要性模型参数是粗略的估计值获取所需数据必须付出许多的时间与精力有些因素只有在研究完成后才能精确测量what-if分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策57第五十七页，共八十七页。灵敏度分析（4个方面）1.C(价格系数)变化的分析:

最优条件λ

＝CBB-1A–C≤0.2.增加一个新变量(例如新产品投产)的分析:如果最优条件CBB-1Pj-Cj≤0满足，不生产;如果满足CBB-1Pj-Cj≥0，新产品生产.3.b(资源量)变化的分析:最优条件B-1b≥0.4.增加一个新的约束条件的分析：最优解满足约束条件，则不变；最优解不满足约束条件，则用对偶单纯形法，目标值变差。58第五十八页，共八十七页。标准型maxZ=CX

AX

=bX0(1)、参数A，b，C在什么范围内变动，对当前方案无影响？(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？(3)、如果最优方案改变，如何用简便方法求新方案？59第五十九页，共八十七页。递减成本（ReducedCosts）的经济意义递减成本（CBB-1Pj-Cj）表示使目标函数中变量的值为正数时相应目标函数系数的改变量（最大化问题是增加；最小化问题是减小）当某个变量对应的递减成本>0，表示含义？见P70例中图3-6的D产品的递减成本为1.15003，表明D的利润应增加1.15003元，D才能变为正值。60第六十页，共八十七页。经济解释：W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

第i种资源的数量yi：对偶价格bi增加bi,其它资源数量不变时,目标函数的增量Z=biyiyi：反映bi的边际效益(边际成本)61第六十一页，共八十七页。假设目标为max对偶价格y（dualprice）：b的单位改变量所引起的目标函数改变量。如果y的大小与系统内资源对目标的贡献有关，是资源的一种估价，又称为影子价格。对偶价格（影子价格）经济意义62第六十二页，共八十七页。对偶价格的准确经济意义与建模有关。情况①模型中，目标函数系数Ci表示利润时，

yi不是真正的影子价格，只表示资源bi增加1单位时，企业目标增加的净利润。情况②模型中，目标函数系数Ci表示成本时，

yi是真正的影子价格。对偶价格（影子价格）经济意义63第六十三页，共八十七页。例家具厂生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？

资源单耗产品桌子椅子资源限量

木工

43120小时

油漆工

21

50小时售价(元／个)5030

64第六十四页，共八十七页。例家具厂生产问题的灵敏度分析模型1：产品A(桌子)，B(椅子)销售价格发生变化，最优解是否改变？模型3：如果家具厂木工资源可能发生变化，要使生产计划不变，问木工工时b1变化范围如何?模型2：设计一种新产品柜子,售价100元,单耗木工9工时、油漆工3工时问是否投产?模型4：若增加约束:每月可用木材量是10立方米,桌子单耗0.4立方米,椅子单耗0.3立方米。如何安排生产?模型5：如果桌子价格降价10％，而椅子价格上涨10％，该问题的最优解是否发生变化？65第六十五页，共八十七页。100％法则（目标函数系数）P66对所有变化的目标函数系数，允许的增量和允许的减量百分比之和未达到100%，最优解就不会改变。模型5：如果桌子价格降价10％，而椅子价格上涨10％，如何？目标式系数允许的增量允许的减量501010307.5566第六十六页，共八十七页。灵敏度分析的方法图解法灵敏度分析（参见教材P57）应用Excel的灵敏度分析应用MS6.0的灵敏度分析67第六十七页，共八十七页。图解法灵敏度分析68第六十八页，共八十七页。判断新产品是否投产？

方法：利用对偶价格（影子价格）概念分析：找出原问题的对偶解，利用机会成本CBB

–1Pj。从最优表中可知：Y=CBB

–1=(5,15)。∵销售价格85元≤机会成本,∴新产品不应生产!机会成本CBB

–1Pj=5×9＋15×3＝90若柜子售价为100元，情况是否有变化?69第六十九页，共八十七页。Case课堂练习：TruckLeasingStrategy

3-3卡车租赁策略（教材P92）Xij表示第i月租赁卡车j月的数量，Yi表示第i月获得长期租赁卡车的数量70第七十页，共八十七页。Case3-3:TruckLeasingStrategy

MIN6000X11+11400X12+15675X13+20160X14+6000X21+11400X22+15675X23+6000X31+

11400X32+6000X41+

2000Y1+

2000Y2+

2000Y3+2000Y4S.T.1)1X11+1X12+1X13+1X14+1Y1=102)1X12+1X13+1X14+1X21+1X22+1X23+1Y2=123)1X13+1X14+1X22+1X23+1X31+1X32+1Y3=144)1X14+1X23+1X32+1X41+1Y4=85)1Y1<16)1Y2<27)1Y3<38)1Y4<171第七十一页，共八十七页。1.租赁的最优方案

TheManagementScientistSoftwareObjectiveFunctionValue=203660.000VariableValueReducedCosts-----------------------------------------------X110.0001515.000X120.0001725.000X133.0000.000X146.0000.000X210.000810.000X220.000210.000X231.0000.000X311.0000.000X320.000915.000X410.0001515.000Y11.0000.000Y22.0000.000Y33.0000.000Y41.0000.00072第七十二页，共八十七页。2.最优方案的租赁成本（考虑裁员）

Anadditionalcostforlayoffpolicy73第七十三页，共八十七页。3.最优方案的租赁成本（不考虑裁员）

Anadditionalcostfornolayoffpolicy74第七十四页，共八十七页。第四章线性规划模型的应用4.1市场营销问题石油公司的营销计划模型P96媒体选择问题市场调查问题4.2财务管理问题投资组合优化问题财务计划问题4.3营运管理问题生产决策问题(make-or-buy)生产计划问题（家乐士的最优化生产、库存以及分销）劳动力分配问题4.4产品配方(blending)问题75第七十五页，共八十七页。第5章高级线性规划应用5.1数据包络分析（DataEnvelopmentAnalysis）：用来衡量相同运营分公司的相对效率（例如快餐店、医院等）。5.2收入管理（RevenueManagement）：适用于管理易逝品的短期需求，从而使组织有获得最大收入的潜力（例如酒店房间、机票预订、汽车出租等）。76第七十六页，共八十七页。原书第五章LP单纯形法单纯型法的基本思路单纯形法基本步骤单纯形表77第七十七页，共八十七页。单纯型法的基本思路78第七十八页，共八十七页。例2.1生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？

资源单耗产品桌子椅子资源限量

木工

43120小时

油漆工

21

50小时售价(元／个)5030

79第七十九页，共八十七页。问题求什么?决策变量是什么?→问该厂如何组织生产?→生产桌子和椅子两种家具各多少?→X1=生产桌子数量;X2=生产椅子数量.目的是什么?目标函数是什么?→使每月的销售收入最大？Z=每月的销售收入,则MaxZ=50X1+30X23.满足什么?约束条件是什么?

木工工时为120小时:4X1+3X2≤120

油漆工工时为50小时:2X1+1X2≤50

生产数量:X1≥0;X2≥0模型为:求X1,X2maxZ=50X1+30X2s.t:4X1