运筹学 单纯形法课件

1、2020/8/17,运筹学 单纯形法,1,第4节 单纯形法计算步骤,2020/8/17,运筹学 单纯形法,2,Step 1 化为标准型，找出初始可行基，并列出初始单纯形表,上述初始单纯形表中，最后一行称为检验数j,2020/8/17,运筹学 单纯形法,3,2020/8/17,运筹学 单纯形法,4,Step2：检查非基变量所对应的检验数j，若所有的j0，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。 否则，转入下一步。 Step3：若存在一个k0，k所对应的变量xk的系数列向量Pk0(即Pk中每一个分量aik0)，则该LP无有限最优解，停止计算。 否则，转入下一步。 Step

2、4：进行可行基的迭代。 重复以上步骤,2020/8/17,运筹学 单纯形法,5,例7 用单纯形法求解例6。 max z = 2x1 + 3x2,s.t.,x1 + 2x2 +x3 =8 4x1 +x4 =16 4x2 +x5 =12 xj0，j=1,2,5,2020/8/17,运筹学 单纯形法,6,练习：,分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。,Max Z = 10 x1+ 5x2 3x1+ 4x29 5x1+ 2x2 8 x1 ，x20,2020/8/17,运筹学 单纯形法,7,解：,j,10,5,0,0, ,3,8/5, ,x1入,x

3、4出,j,0,1,0,-2, ,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2)T Z*=35/2, ,对应0,对应A,对应B,2020/8/17,运筹学 单纯形法,8,回顾：单纯形法求解步骤：,2020/8/17,运筹学 单纯形法,9,第5节 单纯形法的进一步讨论,2020/8/17,运筹学 单纯形法,10,第5节 单纯形法的进一步讨论,一、人工变量法（大M法） 约束条件： “” 加一个松弛变量 “” 减一个剩余变量后，再加一个人工变量 “” 加一个人工变量 目标函数： 人工变量的系数为“M”，即罚因子 若线性规划问题有最优解则人

4、工变量必为0。,2020/8/17,运筹学 单纯形法,11,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,标准化及变形,2020/8/17,运筹学 单纯形法,12,练习：列出初始单纯形表，并求解第2小题的最优解 P55，2.2（1） 2.,2020/8

5、/17,运筹学 单纯形法,13,单纯形表,j,-3-2M,4M,1,0,0, ,3,x2入，x6出,-M,0,4,1, ,j,6M-3,0,4M+1,0,-4M, ,-,x1入，x7出,3M,0,1,1, ,j,0,0,3,0,-M-3/2, ,9,x3入，x1出,3/2,-M+1/2,3/2,-, ,j,-9/2,0,0,0,-M+3/4,-3/4,-M-1/4,所以：X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020/8/17,运筹学 单纯形法,14,二、两阶段法 第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（

6、求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。 当第一阶段中目标函数的最优值0，即人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。 第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,2020/8/17,运筹学 单纯形法,15,求解辅助问题，得到辅助问题的最优解,引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,Max W = 0 ?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解

7、,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,Max W= -x6 - x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,2020/8/17,运筹学 单纯形法,16,(第一阶段）单纯形表1,j,-2,4,0,0,0, ,3,x2入，x6出,-1,0,4,1, ,j,6,0,4,0,-4, ,x1入，x7出,3,0,1,1, ,j,0,0,0,0,-1,0,-1,所以

8、：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。,2020/8/17,运筹学 单纯形法,17,（第二阶段）单纯形表2,j,0,0,3,0,3/2, ,-,9,3/2, ,x3入，x1出,j,-9/2,0,0,0,-3/4,所以： X*=(x1,x2,x3)T=(0,5/2, 3/2)T Z*=3/2,2020/8/17,运筹学 单纯形法,18,单纯形法小结,给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：,2020/8/17,运筹学 单纯形法,19,第5节 单纯形法的进一步讨论,

9、人工变量法（大M法）和两阶段法 约束条件： “” 加一个松弛变量 “” 减一个剩余变量后，再加一个人工变量 “” 加一个人工变量 若线性规划问题有最优解则人工变量必为0。,2020/8/17,运筹学 单纯形法,20,目标函数极小化时解的最优性判别； 无可行解的判别； 无界的判别； 无穷多最优解的判别； 唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解；,最优解中人工变量为非0的基变量时；,存在某个k0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,2020/8/17,运筹学 单纯形法,21,j,40,45,0,

10、25,100/3,40, 3 ,x2入，x4出,j,0,0,0,-5,因为全j 0,且1=0,则有无穷多最优解。 所以：其中一个最优解为X*=(0,80/3,20,0,0) T,Z*=1700,例1:,0,-10,思考：无穷多最优解的一般形式？,2020/8/17,运筹学 单纯形法,22,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因为2 = 2,且ai2 全0所以：无界,例2:,2020/8/17,运筹学 单纯形法,23,例3:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为： 唯一最优解； 无穷多最优解；

11、无界； 无可行解； 非最优，继续换基： X3换入，x2换出,a40,a20, a30 a40,a50, x4或x2为人工变量，a60 ； x1为人工变量，a60 a40,a4a5;a6/a12a10 a60 a1 0,2020/8/17,运筹学 单纯形法,24,复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表， 为松弛变量，试求表中aL的值及各变量下标mt的值；,2020/8/17,运筹学 单纯形法,25,第6节 应用举例,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。 .要求解问题的目标函数能用数值指标来反映，且为线性函数； .存在着多种方案； .要求

12、达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。,2020/8/17,运筹学 单纯形法,26,建模步骤：, 第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。 第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。 第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。 决策变量的非负要求可以根据问题的实际意义加以确定。,2020/8/17,运筹学 单纯形法,27,一般的产品计划问题举例 例1：,某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第

13、一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。 生产产品B的同时产出副产品C，每生产一吨产品B，可同时得到2吨产品C而毋需外加任何费用；副产品C一部分可以盈利，剩下的只能报废。 出售产品A每吨能盈利400元、产品B每吨能盈利1000元，每销售一吨副产品C能盈利300元，而剩余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。试列出线性规划模型，决定A、B两种产品的产量，使工厂总的利润最大。,2020/8/17,运筹学 单纯形法,28,数学模型：,设：x1产品

14、A的产量， x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得,2020/8/17,运筹学 单纯形法,29,例2 合理下料问题。 现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。,解：依题意，在排除明显不合理的方案后。可以列出8种套裁方案，前5种更合理。,2020/8/17,运筹学 单纯形法,30,例3,2020/8/17,运筹学 单纯形法,31,练习1：,练习2：P57，T2.9,2020/8/17,运筹学 单纯形法,32,2020/8/17,运筹学 单纯形法,33,例4. 连续投资问题。P

15、53, 2-13,2020/8/17,运筹学 单纯形法,34,练习：,设某投资者有30 000元可供为期四年的投资，现有五个投资机会可供选择： A: 可在每年年初投资，每年每元投资可获0.2元。 B: 第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。 C: 第一年初投资，三年后每元投资获利0.8元。这项投资最多不超过20 000元。 D: 第二年年初投资，两年后每元投资可获利0.6元。这项投资最多不超过15 000元。 E: 第一年年初投资，四年后每元获利1.7元，这项投资最多不超过20 000元。 投资者应如何投资，使他在四年后所拥有资金总额最大？,2020/8/17,运筹学 单纯形法,35,第一章 总结,基本概念： 可行解，基，基解，基可行解，可行基，凸集，顶点 基本定理： 可行域为凸集； 基可行解 顶点； 最优解一定在顶点上取得。,2020/8/17,运筹学 单纯形法,36,基本问题：,什么是线性规划问题的数学模型结构？ 如何用图解法及单纯形法判断解的情况？