运筹学 单纯形法

《运筹学 单纯形法》由会员分享，可在线阅读，更多相关《运筹学 单纯形法（39页珍藏版）》请在装配图网上搜索。

1、2022-10-61Step 1 化为标准型，找出初始可行基，并列出初始单纯形表化为标准型，找出初始可行基，并列出初始单纯形表 上述初始单纯形表中，最后一行称为检验数j第1页/共39页2022-10-62基基向量 x1x2x3x4x5Z可行解 图中点B1P3P4P50081612 0OB2P2P4P504016-412 AB3P2P3P500无解B4P2P3P40321609Q4B5P1P4P5800-16 12 16 CB6P1P3P5404012 8Q1B7P1P3P400无解B8P1P2P54200414 Q2B9P1P2P42308013 Q3B10P1P2P343-20017 B5,

2、1 ,012 4 16 48 2x 32 max524132121jxxxxxxxxxzjx2x1O11223344Q1Q2Q3Q4ABC第2页/共39页2022-10-63 Step2：检查非基变量所对应的检验数j，若所有的j0，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。否则，转入下一步。Step3：若存在一个k0，k所对应的变量xk的系数列向量Pk0(即Pk中每一个分量aik0)，则该LP无有限最优解，停止计算。否则，转入下一步。Step4：进行可行基的迭代。重复以上步骤第3页/共39页2022-10-64 例7 用单纯形法求解例6。max z=2x1+3x2s.t

3、.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 xj0，j=1,2,5第4页/共39页2022-10-65练习：分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。Max Z=10 x1+5x2 3x1+4x29 5x1+2x2 8 x1，x20第5页/共39页2022-10-66cj10500CBXBbix1x2x3x40 x3934100 x485201j10500 38/5 0X310 x18/512/501/521/5014/51-3/5x1入,x4出j010-2 x2入,x3出3/245X210 x1j110-1/7

4、2/73/2015/14-3/1400-5/14-25/14 0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2对应0对应A对应B第6页/共39页2022-10-67回顾：单纯形法求解步骤：第7页/共39页2022-10-68第5节 单纯形法的进一步讨论第8页/共39页2022-10-69第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论一、人工变量法（大M法）约束条件：“”加一个松弛变量“”减一个剩余变量后，再加一个人工变量“”加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。第9页/共39页2022-10-610Ma

5、xZ=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3增加人工变量后，线性规划问题中就存在一个B 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标准化及变形第10页/共39页2022-10-611练习：列出初始单纯形表，并求解第2小题的最优解1.P55，2.2（1）2.第11页/共39页2022-10-612cj-30100-M-MCBXBbix1x2x3x4x5x6x

6、70 x441111000-Mx61-21-10-110-Mx790310001j-3-2M4M100 3x2入，x6出-M0410 x40 x2-Mx7330211-10j6M-304M+10-4M -x1入，x7出3M01-21-10-1101660403-3110 x40 x2-3x100001-1/21/2-1/2j0030-M-3/2 9x3入，x1出3/2-M+1/23011/30001/33/21102/301/2-1/21/6-0 x40 x21x300001-1/21/2-1/2j-9/2000-M+3/4-3/4-M-1/45/2-1/2100-1/41/41/43/23/

7、20103/4-3/41/4第12页/共39页2022-10-613二、两阶段法 第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，即人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。第13页/共39页2022-10-614求解辅助问题，得到辅助问题的最优解引进人

8、工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化Max W=0?原问题没有可行解。把辅助问题的最优解作为原问题的初始基础可行解用单纯形法求解原问题，得到原问题的最优解否是两阶段法的算法流程图MaxZ=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3Max W=-x6-x7 x1+x2+x3+x4 =4-2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7第14页/共39页2022-10-615cj00000-1-1CBXBbix1x2x3x4x5x6x70 x441111000-

9、1x61-21-10-110-1x790310001j-24000 3x2入，x6出-10410 x40 x2-1x7330211-10j6040-4 x1入，x7出301-21-10-1101660403-3110 x40 x20 x100001-1/21/2-1/2j0000-10-13011/30001/31102/301/2-1/21/6第15页/共39页2022-10-616cj-30100CBXBbix1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2j00303/2 -93/2 0X40X21x35/2-1/2100-1/400001

10、-1/23/23/20103/4x3入，x1出j-9/2000-3/4第16页/共39页2022-10-617单纯形法小结 给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：取取 值值右端项右端项等式或不等式等式或不等式极大或极小极大或极小新加变量系数新加变量系数xj无约束无约束xj 0bi 0=minZxs xa令令xj=xj-xj xj 0 xj 0令令 xj=-xj约束条约束条件两端件两端同乘以同乘以-1加松加松弛变弛变量量xs加入加入人工人工变量变量xa减去减去剩余剩余变量变量xs加入加入人工人工变量变

11、量xa令令z=-ZminZ=-max z0-M第17页/共39页2022-10-618第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论人工变量法（大M法）和两阶段法约束条件：“”加一个松弛变量“”减一个剩余变量后，再加一个人工变量“”加一个人工变量若线性规划问题有最优解则人工变量必为0。第18页/共39页2022-10-619 目标函数极小化时解的最优性判别；无可行解的判别；无界的判别；无穷多最优解的判别；唯一最优解的判别.三、单纯形法计算中的几个问题第19页/共39页2022-10-620cj40452500CBXBbix1x2x3x4x50 x4100231100 x512033201

12、j4045025100/340 3 45X225x380/31/3102/3-1/320101-11x2入，x4出j000-5例1:012023310032254540321321321321xxxxxxxxxtsxxxZ,.max0-10思考：无穷多最优解的一般形式？第20页/共39页2022-10-6210 x,x50 xx100 x2xs.t.xxmaxZ21212121cj1100CBXBbix1x2x3x40 x3100-21100 x4501-101j1100-50 0X31x12000-112501-101x1入，x4出j020-1例2:第21页/共39页2022-10-622例

13、3:下表为一极大化问题对应的单纯形表讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为：唯一最优解；无穷多最优解；无界；无可行解；非最优，继续换基：X3换入，x2换出x1x2x3x4x5bix110a10a2a6x20110-22x400-21a33j00a40a5a40,a50,a20,a30a40,a50,x4或x2为人工变量，a60；x1为人工变量，a60a40,a4a5;a6/a12a10 a60 a1 0第22页/共39页2022-10-623复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中aL的值及各变量下标mt的值；45,x

14、x第23页/共39页2022-10-624第6节 应用举例 一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。.要求解问题的目标函数能用数值指标来反映，且为线性函数；.存在着多种方案；.要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。第24页/共39页2022-10-625 第25页/共39页2022-10-626一般的产品计划问题举例 例1：某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二

15、道工序为24小时。余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。试列出线性规划模型，决定A、B两种产品的产量，使工厂总的利润最大。第26页/共39页2022-10-627Y数学模型：设：x1产品A的产量，x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得第27页/共39页2022-10-628例2 合理下料问题。现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。根数根数方案方案需要需要根数根数长度长度III III IVVVI VII VIII2.9120101001

16、002.1002211301001.531203104100合计合计 7.4 7.3 7.2 7.1 6.6 6.5 6.36料头料头00.1 0.2 0.3 0.8 0.9 1.11.4 解：依题意，在排除明显不合理的方案后。可以列出8种套裁方案，前5种更合理。第28页/共39页2022-10-629例3第29页/共39页2022-10-630练习1：练习2：P57，T2.9第30页/共39页2022-10-631第31页/共39页2022-10-632 例4.连续投资问题。P53,2-13项目项目 第第1年年第第2年年第第3年年第第4年年第第5年年投资回报率投资回报率投资额限制投资额限制A

17、x1Ax2Ax3Ax4A115%Bx3B125%4万元万元Cx2C140%3万元万元Dx1Dx2Dx3Dx4Dx5D公债利息公债利息6%投资总额：投资总额：10万元万元第32页/共39页2022-10-633练习：设某投资者有30 000元可供为期四年的投资，现有五个投资机会可供选择：A:可在每年年初投资，每年每元投资可获0.2元。B:第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。C:第一年初投资，三年后每元投资获利0.8元。这项投资最多不超过20 000元。D:第二年年初投资，两年后每元投资可获利0.6元。这项投资最多不超过15 000元。E:第一年年初投资，四年后

18、每元获利1.7元，这项投资最多不超过20 000元。投资者应如何投资，使他在四年后所拥有资金总额最大？第33页/共39页2022-10-634第一章 总结 基本概念：可行解，基，基解，基可行解，可行基，凸集，顶点 基本定理：可行域为凸集；基可行解 顶点；最优解一定在顶点上取得。第34页/共39页2022-10-635基本问题：1.什么是线性规划问题的数学模型结构？2.如何用图解法及单纯形法判断解的情况？3.什么是线性规划问题的标准型，如何化标准型？4.如何求线性规划的基解，基可行解及最优解？5.单纯形法的计算步骤？6.什么情况要加入人工变量？7.两阶段法的基本步骤？第35页/共39页2022-

19、10-636单纯形法小结 给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：取取 值值右端项右端项等式或不等式等式或不等式极大或极小极大或极小新加变量系数新加变量系数xj无约束无约束xj 0bi 0=minZxs xa令令xj=xj-xj xj 0 xj 0令令 xj=-xj约束条约束条件两端件两端同乘以同乘以-1加松加松弛变弛变量量xs加入加入人工人工变量变量xa减去减去剩余剩余变量变量xs加入加入人工人工变量变量xa令令z=-ZminZ=-max z0-M第36页/共39页2022-10-637添加松弛变量

20、、人工变量列出初始单纯形表添加松弛变量、人工变量列出初始单纯形表所有所有 基变量中有基变量中有非零人工变量非零人工变量某非基变量某非基变量检验数为零检验数为零唯一最优解唯一最优解无穷多最优解无穷多最优解无可行解无可行解对任一对任一 有有 换基继续换基继续YYYYNNN无界解无界解Njjika000jjika000jjika000计算非基变量各列的计算非基变量各列的检验数检验数j第37页/共39页2022-10-638对任一 有 jjika000jjika000N换基继续换基继续令maxkj0minikiiiklillkabaxa对所有计算令为换出变量为主元素(1)(2)();(3)(1;0(4);lljklljllklklkljlijikljiikilklkxxlabbaaaaabaaababaa迭代运算用非基变量替换基变量在主元素行 第 行令在主元素列 第k列)令其它元素表中其它行列元素令计算所有非基变量的检验数计算所有非基变量的检验数第38页/共39页2022-10-639感谢您的观看！第39页/共39页