运筹与决策之2线性规划-课件

授课内容Question线性规划的概念和建模线性规划的图解法单纯形法基本步骤计算机软件求解LP问题（下料优化）Case2:基金（教材P51）

灵敏度分析(Case:生产优化问题)运筹与决策之2线性规划1授课内容Question运筹与决策之2线性规划11绪论—Introduction2线性规划—LinearProgramming3运输问题

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

模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《运筹与决策》目录运筹与决策之2线性规划21绪论—Introduct§2.1线性规划的概念和模型线性规划问题的导出OR在企业管理的具体应用例1、家具厂生产计划问题例3、合理下料问题线性规划概念和模型运筹与决策之2线性规划3§2.1线性规划的概念和模型线性规划问题的导出运筹与决线性规划问题的导出

产品AB 可用资源木工1230

油漆工3260

搬运工0224

利润(￥)

4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?如何建模？运筹与决策之2线性规划4线性规划问题的导出例1、家具厂生产计划问题A,B各生产多TransformingModelInputsintoOutputUncontrollableInputs(EnvironmentalFactors)产品消耗系数、利润、可用资源ControllableInputs(DecisionVariables)A,B各生产多少Output(ProjectedResults)最大利润MathematicalModel（见下页）运筹与决策之2线性规划5TransformingModelInputsintox1

+2x2

303x1+2x2

60

2x2

24

x1，x2

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

，x2运筹与决策之2线性规划6x1+2x230maxZ=40x1+50x例2营养配餐求：最低成本的原料混合方案

原料iABＣ每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量如何建模？运筹与决策之2线性规划7例2营养配餐求：最低成本的原料混合方案原料i解：设每单位添加剂中原料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)运筹与决策之2线性规划8解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4线性规划概念定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。运筹与决策之2线性规划9线性规划概念定义：运筹与决策之2线性规划9要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划模型的要求运筹与决策之2线性规划10要解决的问题的目标可以用数值指标反映线性规划模型的要求运筹与WhyUseLinearProgramming?为什么要使用线性规划线性规划很容易而有效率地被求解如果存在最优解，则必能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的运筹与决策之2线性规划11WhyUseLinearProgramming?为什线性规划模型的特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小运筹与决策之2线性规划12线性规划模型的特点决策变量：向量(x1…xn)T一般式max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

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

(=,)bmXj0(j=1,…,n)运筹与决策之2线性规划13一般式max(min)Z=C1X1+C2X2+…+CnXn运筹与决策之2线性规划14运筹与决策之2线性规划14隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值运筹与决策之2线性规划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、合理下料问题运筹与决策之2线性规划16某钢筋架需要长度1.5m、2.1m和2.9m各100段解：设按第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)如何正确建模？运筹与决策之2线性规划17解：设按第i种方案下料的原材料为xi根minZ=0.1该线性规划模型错误决策变量缺少整数变量约束约束条件为等式用余料作为目标函数下料方式不全（少3种下料方式）运筹与决策之2线性规划18该线性规划模型错误决策变量缺少整数变量约束运筹与决策之2线性解：设按第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)，且为整数如何建模？运筹与决策之2线性规划19解：设按第i种方案下料的原材料为xi根minZ=x1例4、运输问题某公司有三个分厂分别供应三个市场，具体生产能力和需求量如下表：如何建模？

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

需求401535运筹与决策之2线性规划20例4、运输问题如何建模？ 市场1市场2市场设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

0运筹与决策之2线性规划21设xij为i工厂运到j市场的产品数量(i＝1，2，3，例5、连续投资10万元A：从第1年到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大如何建模？运筹与决策之2线性规划22例5、连续投资10万元A：从第1年到第4年每年初要投资，次[分析]

12345Ax1A

x2A

x3A

x4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D运筹与决策之2线性规划23[分析]12Xik(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线性规划Xik(i=1,2,…,5;k=A,B,C,D)第i24§2.2图解法AX=b(1)X

0(2)maxZ=CX(3)定义1:满足约束(1)、(2)的X=(X1…Xn)T称为LP问题的可行解，全部可行解集合称为可行域。定义2:满足(3)的可行解称为LP问题的最优解。运筹与决策之2线性规划25§2.2图解法AX=b(1)图解法举例

产品AB备用资源木工1230

油漆工3260

搬运工0224

利润4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?运筹与决策之2线性规划26图解法举例例1、家具厂生产计划问题A,B各生产多少,可建立模型maxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20建模后如何计算？运筹与决策之2线性规划27建立模型X1+2X230建模后如何计算？解：(1)、确定可行域

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

2X2=24X1运筹与决策之2线性规划28解：(1)、确定可行域X1+2X23020301(2)、求最优解解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)0203010102030X1X2DABCDABCC点：X1+2X2=30

3X1+2X2=60运筹与决策之2线性规划29(2)、求最优解解：X*=(15,7.5)Z=40X1几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基本解可行域的极点基本可行解目标函数等值线：一组平行线目标函数值等于一个常数的解如何对应？运筹与决策之2线性规划30几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一图解法计算步骤（1）用字母表示可行域；（2）画出目标函数的平行线；（3）

注意目标函数的斜率；（4）适当的说明语句（包括可行域、最优解、目标函数值等）运筹与决策之2线性规划31图解法计算步骤（1）用字母表示可行域；运筹与决策之2线性规划例2、图解法

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

X1,X20运筹与决策之2线性规划32例2、图解法X1+2X230运筹与决策之2线性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点无穷多解运筹与决策之2线性规划330Z=40X1+80X2=0X1+2X2X1=6++(1-)·15X2=12++(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5运筹与决策之2线性规划34X1=6++(1-)·15X1=15-9X=无界无有限最优解例3、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=0-2X1+X2=28246X22X1+X2=840X1运筹与决策之2线性规划35无界例3、maxZ=2X1+4X22X1+X2例4、maxZ=3X1+2X2-X1-X21X1,X20无解无可行解-1X2-1X10运筹与决策之2线性规划36例4、maxZ=3X1+2X2-X1-X21无解-图解法总结

唯一解无穷多解

无有限最优解无可行解有解无解运筹与决策之2线性规划37图解法总结AX=b(1)X

0(2)maxZ=CX(3)概念：1可行解?2可行域?3最优解?2.3线性规划的基本理论运筹与决策之2线性规划38AX=b(1)概念：2.3线性2.3求解LP问题的常见应用软件LINDOGAMSExcel规划求解的举例TheManagementScientistSoftware（MS6.0）运筹与决策之2线性规划392.3求解LP问题的常见应用软件LINDO运筹与决策之2LINDO（LinearInteractiveandDiscreteOptimizer）

－美国LindoSystemInc.

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

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

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

<=小于等于;=等于;>=大于等于;int整数;bin二进制（0或1）2求解中用到下列概念：目标单元格最大值（最小值）：指满足可变单元格约束条件后，单元格可取的最大值（最小值）。3可变单元格（目标函数、变量和约束条件）例如，问题中B1、D6、D7格由公式构成，分别对应模型中的目标函数（如：B1=B3*B5+C3*C5）和约束条件；B5、C5为“可变单元格”，分别对应模型中的变量。4求解过程（见Excel）运筹与决策之2线性规划45计算机求解LP问题的使用说明1在约束中使用的运算符有下列QuantitativeMethodsinPracticeLinearProgrammingIntegerLinearProgrammingPERT/CPMInventorymodelsWaitingLineModelsSimulationDecisionAnalysisGoalProgrammingAnalyticHierarchyProcessForecastingMarkov-ProcessModels运筹与决策之2线性规划46QuantitativeMethodsinPractiTheManagementScientistSoftwareModules软件求解下料优化问题运筹与决策之2线性规划47TheManagementScientistSoftwCase课堂练习：HartVentureCapital

哈特风险基金（教材P51）1）两种投资各占多少比例？NPV?2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少？3）如果HVC公司愿意在第1年追加100,000美元投资，对投资计划有何影响？4）追加100,000美元投资后的投资分配计划？5）你是否建议公司在第1年取消追加100,000美元？运筹与决策之2线性规划48Case课堂练习：HartVentureCapitalCase:HartVentureCapitalLet S=fractionoftheSecuritySystemsprojectfundedbyHVCM=fractionoftheMarketAnalysisprojectfundedbyHVC运筹与决策之2线性规划49Case:HartVentureCapitalLetCase:HartVentureCapital1）两种投资各占多少比例？NPV?ObjectiveFunctionValue=2486956.522

theoptimalsolutionisS=0.609andM=0.870.

2）接下来3年为两个公司的资金分配计划？HVC每年投资的总额是多少？运筹与决策之2线性规划50Case:HartVentureCapital1）两Case3:HartVentureCapital

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

4）追加100,000美元投资后的投资分配计划？运筹与决策之2线性规划51Case3:HartVentureCapital

哈Case:HartVentureCapital5）你是否建议公司在第1年取消追加100,000美元？建议公司在第1年取消追加77049.180美元运筹与决策之2线性规划52Case:HartVentureCapital5）你第三章LP灵敏度分析与最优解图解法灵敏度分析灵敏度分析：计算机求解多于两个变量的情况运筹与决策之2线性规划53第三章LP灵敏度分析与最优解图解法灵敏度分析运筹与决策之2为什么要做灵敏度分析？

what-if（SensitivityAnalysis）如果在计划实施前或实施中有些因素已发生了改变，则决策者所关心的是目前所执行的计划还是不是最优？企业应当作出什么样的反应，运用灵敏度分析而不需建立新的模型。模型中目标函数系数哪个更能影响最优解。约束条件的右端值变化对最优解的影响。运筹与决策之2线性规划54为什么要做灵敏度分析？

what-if（Sensitiv灵敏度分析对管理者的重要性模型参数是粗略的估计值

获取所需数据必须付出许多的时间与精力有些因素只有在研究完成后才能精确测量what-if分析表明改变这些决策对结果的影响，从而有效指导管理者作出最终决策运筹与决策之2线性规划55灵敏度分析对管理者的重要性模型参数是粗略的估计值运筹与决策A（原材料消耗）代表企业的技术状况；b（资源供应量）代表企业的资源状况；C（价值系数）代表企业产品的市场状况；在这些因素（原材料消耗系数、资源供应量、价值系数）不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在生产计划问题的一般形式中，A，b，C各代表什么？标准型maxZ=CX

AX

=bX0如何回答？运筹与决策之2线性规划56A（原材料消耗）代表企业的技术状况；在生产计划问题的一般形式TheImportanceofWhat-IfAnalysistoManagers

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

最优条件λ

＝CBB-1A–C≤0.2.增加一个新变量(例如新产品投产)的分析:如果最优条件CBB-1Pj-Cj≤0满足，不生产;如果满足CBB-1Pj-Cj≥0，新产品生产.3.b(资源量)变化的分析:最优条件B-1b≥0.4.增加一个新的约束条件的分析：最优解满足约束条件，则不变；最优解不满足约束条件，则用对偶单纯形法，目标值变差。运筹与决策之2线性规划58灵敏度分析（4个方面）1.C(价格系数)变化的分析:运筹标准型maxZ=CX

AX

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

第i种资源的数量yi：对偶价格bi增加bi,其它资源数量不变时,目标函数的增量Z=biyiyi：反映bi的边际效益(边际成本)运筹与决策之2线性规划61经济解释：W=yb=(y1…ym)b1…=b1假设目标为max对偶价格y

（dualprice）：b的单位改变量所引起的目标函数改变量。如果y的大小与系统内资源对目标的贡献有关，是资源的一种估价，又称为影子价格。对偶价格（影子价格）经济意义运筹与决策之2线性规划62假设目标为max对偶价格（影子价格）经济意义运筹与决策之2线对偶价格的准确经济意义与建模有关。情况①模型中，目标函数系数Ci表示利润时，

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

yi是真正的影子价格。对偶价格（影子价格）经济意义运筹与决策之2线性规划63对偶价格的准确经济意义与建模有关。情况②模型中，目标函数例家具厂生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？

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

木工

43120小时

油漆工

21

50小时售价(元／个)5030

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

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

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

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

–1Pj=5×9＋15×3＝90若柜子售价为100元，情况是否有变化?运筹与决策之2线性规划69判断新产品是否投产？

方法：利用对偶价格（影子价格）概念分析Case课堂练习：TruckLeasingStrategy

3-3卡车租赁策略（教材P92）Xij表示第i月租赁卡车j月的数量，Yi表示第i月获得长期租赁卡车的数量运筹与决策之2线性规划70Case课堂练习：TruckLeasingStrateCase3-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<1运筹与决策之2线性规划71Case3-3:TruckLeasingStrate1.租赁的最优方案

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.000运筹与决策之2线性规划721.租赁的最优方案

TheManagementScien2.最优方案的租赁成本（考虑裁员）

Anadditionalcostforlayoffpolicy运筹与决策之2线性规划732.最优方案的租赁成本（考虑裁员）

Anadditiona3.最优方案的租赁成本（不考虑裁员）

Anadditionalcostfornolayoffpolicy运筹与决策之2线性规划743.最优方案的租赁成本（不考虑裁员）

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

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

木工

43120小时

油漆工

21

50小时售价(元／个)5030

运筹与决策之2线性规划79例2.1生产计划问题胜利家具厂生产桌子和椅子两种家具。桌问题求什么?决策变量是什么?→问该厂如何组织生产?→生产桌子和椅子两种家具各多少?→X1=生产桌子数量;X2=生产椅子数量.目的是什么?目标函数是什么?→使每月的销售收入最大？Z=每月的销售收入,则MaxZ=50X1+30X23.满足什么?约束条件是什么?

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

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

生产数量:X1≥0;X2≥0模型为:求X1,X2maxZ=50X1+30X2s.t:4X1+3X2≤1202X1+1X2≤50X1≥0;X2≥0图解法求解运筹与决策之2线性规划80问题求什么?决策变量是什么?→问该厂如何组织生产?→生图解法求解运筹与决策之2线性规划81图解法求解运筹与决策之2线性规划81例2.1解maxZ=50X1+30X2s.t:4X1+3X2≤1202X1+X2≤50X1≥0,X2≥0化为标准型:maxZ=50X1+30X2

s.t:4X1+3X2+X3=1202X1+X2+X4=50Xj≥0,j=1,2,3,4运筹与决策之2线性规划82例2.1解maxZ=50X1+30X2化为标准型:运筹与C503000比值CBXBB-1bX1X2X3X400X3

X41205043102101120/4=3050/2=25λj0503000050X3

X12025011-21½01/220/1=2025/1/2=50λj1250050-253050X2

X12015011-210-1/23/2λj135000-5-15∵λj≤0,∴得最优解：X1=15,X2=20.最优值：MaxZ=1350.单纯形表计算运筹与决策之2线性规划83C503000比值C单纯形法基本步骤(1)、定初始基，初始基本可行解(3)、若有k>0，Pk全

0，停，没有有限最优解；否则转(4)(2)、对应于非基变量检验数j全

0。

若是，停，得到最优解；若否，转(3)。运筹与决策之2线性规划84单纯形法基本步骤(1)、定初始基，初始基本可行解(3)、若有θ=minaim+k>0=biaim+kbrarm+k定Xr为换出变量，arm+k为主元。由最小θ比值法求：maxj=m+k→Xm+k换入变量j>0(4)、运筹与决策之2线性规划85θ=minaim+k转(2)m+k0

…………a1m+k0arm+k1amm+k0初等行变换Pm+k=…………(5)、以arm+k为中心，换基迭代运筹与决策之2线性规划86转(2)m+k第一次作业（下周课前交）P15-17图解法1.2管理建模1.15，1.18，灵敏度分析2.11思考题：OR在企业应用的前景运筹与决策之2线性规划87第一次作业（下周课前交）P15-17运筹与决策之2线性规划下次课内容Case：卡车租赁策略（教材P92）3运输问题阅读讲义和教材运筹与决策之2线性规划88下次课内容Case：卡车租赁策略（教材P92）阅读讲义和教授课内容Question线性规划的概念和建模线性规划的图解法单纯形法基本步骤计算机软件求解LP问题（下料优化）Case2:基金（教材P51）

灵敏度分析(Case:生产优化问题)运筹与决策之2线性规划89授课内容Question运筹与决策之2线性规划11绪论—Introduction2线性规划—LinearProgramming3运输问题

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

模拟—Simulation9决策分析—DecisionTheory10多目标决策—Multi-objectiveDecision《运筹与决策》目录运筹与决策之2线性规划901绪论—Introduct§2.1线性规划的概念和模型线性规划问题的导出OR在企业管理的具体应用例1、家具厂生产计划问题例3、合理下料问题线性规划概念和模型运筹与决策之2线性规划91§2.1线性规划的概念和模型线性规划问题的导出运筹与决线性规划问题的导出

产品AB 可用资源木工1230

油漆工3260

搬运工0224

利润(￥)

4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?如何建模？运筹与决策之2线性规划92线性规划问题的导出例1、家具厂生产计划问题A,B各生产多TransformingModelInputsintoOutputUncontrollableInputs(EnvironmentalFactors)产品消耗系数、利润、可用资源ControllableInputs(DecisionVariables)A,B各生产多少Output(ProjectedResults)最大利润MathematicalModel（见下页）运筹与决策之2线性规划93TransformingModelInputsintox1

+2x2

303x1+2x2

60

2x2

24

x1，x2

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

，x2运筹与决策之2线性规划94x1+2x230maxZ=40x1+50x例2营养配餐求：最低成本的原料混合方案

原料iABＣ每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量如何建模？运筹与决策之2线性规划95例2营养配餐求：最低成本的原料混合方案原料i解：设每单位添加剂中原料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)运筹与决策之2线性规划96解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4线性规划概念定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。运筹与决策之2线性规划97线性规划概念定义：运筹与决策之2线性规划9要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划模型的要求运筹与决策之2线性规划98要解决的问题的目标可以用数值指标反映线性规划模型的要求运筹与WhyUseLinearProgramming?为什么要使用线性规划线性规划很容易而有效率地被求解如果存在最优解，则必能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的运筹与决策之2线性规划99WhyUseLinearProgramming?为什线性规划模型的特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小运筹与决策之2线性规划100线性规划模型的特点决策变量：向量(x1…xn)T一般式max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

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

(=,)bmXj0(j=1,…,n)运筹与决策之2线性规划101一般式max(min)Z=C1X1+C2X2+…+CnXn运筹与决策之2线性规划102运筹与决策之2线性规划14隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值运筹与决策之2线性规划103隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变某钢筋架需要长度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、合理下料问题运筹与决策之2线性规划104某钢筋架需要长度1.5m、2.1m和2.9m各100段解：设按第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)如何正确建模？运筹与决策之2线性规划105解：设按第i种方案下料的原材料为xi根minZ=0.1该线性规划模型错误决策变量缺少整数变量约束约束条件为等式用余料作为目标函数下料方式不全（少3种下料方式）运筹与决策之2线性规划106该线性规划模型错误决策变量缺少整数变量约束运筹与决策之2线性解：设按第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)，且为整数如何建模？运筹与决策之2线性规划107解：设按第i种方案下料的原材料为xi根minZ=x1例4、运输问题某公司有三个分厂分别供应三个市场，具体生产能力和需求量如下表：如何建模？

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

需求401535运筹与决策之2线性规划108例4、运输问题如何建模？ 市场1市场2市场设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

0运筹与决策之2线性规划109设xij为i工厂运到j市场的产品数量(i＝1，2，3，例5、连续投资10万元A：从第1年到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大如何建模？运筹与决策之2线性规划110例5、连续投资10万元A：从第1年到第4年每年初要投资，次[分析]

12345Ax1A

x2A

x3A

x4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D运筹与决策之2线性规划111[分析]12Xik(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线性规划Xik(i=1,2,…,5;k=A,B,C,D)第i112§2.2图解法AX=b(1)X

0(2)maxZ=CX(3)定义1:满足约束(1)、(2)的X=(X1…Xn)T称为LP问题的可行解，全部可行解集合称为可行域。定义2:满足(3)的可行解称为LP问题的最优解。运筹与决策之2线性规划113§2.2图解法AX=b