运筹学 单纯形法.pptx
2023/2/241Step 1 化为标准型，找出初始可行基，并列出初始单纯形表化为标准型，找出初始可行基，并列出初始单纯形表上述初始单纯形表中，最后一行称为检验数j第1页/共39页2023/2/242基基向量 x1x2x3x4x5Z可行解 图中点B1P3P4P50081612 0OB2P2P4P504016-412 AB3P2P3P500无解B4P2P3P40321609Q4B5P1P4P5800-16 12 16 CB6P1P3P5404012 8Q1B7P1P3P400无解B8P1P2P54200414 Q2B9P1P2P42308013 Q3B10P1P2P343-20017 Bx2x1O11223344Q1Q2Q3Q4ABC第2页/共39页2023/2/243Step2：检查非基变量所对应的检验数j，若所有的j0，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。否则，转入下一步。Step3：若存在一个k0，k所对应的变量xk的系数列向量Pk0(即Pk中每一个分量aik0)，则该LP无有限最优解，停止计算。否则，转入下一步。Step4：进行可行基的迭代。重复以上步骤第3页/共39页2023/2/244例7 用单纯形法求解例6。max z=2x1+3x2s.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 xj0，j=1,2,5第4页/共39页2023/2/245练习：分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。Max Z=10 x1+5x2 3x1+4x29 5x1+2x2 8 x1，x20第5页/共39页2023/2/246解：解：解：解：cj10500CBXBbix1x2x3x40 x3934100 x485201j10500 38/5 0X310 x18/512/501/521/5014/51-3/5x1入,x4出j010-2 x2入,x3出3/245X210 x1j110-1/72/73/2015/14-3/1400-5/14-25/14所以：所以：所以：所以：X*=(xX*=(xX*=(xX*=(x1 1 1 1,x,x,x,x2 2 2 2)T T T T=(1,3/2)=(1,3/2)=(1,3/2)=(1,3/2)T T T T Z*=35/2 Z*=35/2 Z*=35/2 Z*=35/2 0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2对应0对应A对应B第6页/共39页2023/2/247回顾：单纯形法求解步骤：第7页/共39页2023/2/248第5节 单纯形法的进一步讨论第8页/共39页2023/2/249第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论一、人工变量法（大M法）约束条件：“”加一个松弛变量“”减一个剩余变量后，再加一个人工变量“”加一个人工变量目标函数：人工变量的系数为“M”，即罚因子若线性规划问题有最优解则人工变量必为0。第9页/共39页2023/2/2410MaxZ=-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页2023/2/2411练习：列出初始单纯形表，并求解第2小题的最优解1.P55，2.2（1）2.第11页/共39页2023/2/2412cj-30100-M-MCBXBbix1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001单纯形表单纯形表j-3-2M4M100 3x2入，x6出-M041 0 x40 x2-Mx7330211-10j6M-304M+10-4M -x1入，x7出3M01-21-10-1101660403-311 0 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/20103/4-3/41/4所以：所以：所以：所以：X*=(xX*=(xX*=(xX*=(x1 1 1 1,x,x,x,x2 2 2 2,x,x,x,x3 3 3 3)T T T T=(0,5/2,3/2)=(0,5/2,3/2)=(0,5/2,3/2)=(0,5/2,3/2)T T T T Z*=3/2 Z*=3/2 Z*=3/2 Z*=3/2第12页/共39页2023/2/2413二、两阶段法第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。当第一阶段中目标函数的最优值0，即人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于0，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。第13页/共39页2023/2/2414求解辅助问题，得到辅助问题的最优解引进人工变量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页2023/2/2415cj00000-1-1CBXBbix1x2x3x4x5x6x70 x441111000-1x61-21-10-110-1x790310001(第一阶段）单纯形表第一阶段）单纯形表1 1 1 1j-24000 3x2入，x6出-1041 0 x40 x2-1x7330211-10j6040-4 x1入，x7出301-21-10-1101660403-311 0 x40 x20 x100001-1/21/2-1/2j0000-10-13011/30001/31102/301/2-1/21/6所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。第15页/共39页2023/2/2416（第二阶段）单纯形表（第二阶段）单纯形表2 2 2 2cj-30100CBXBbix1x2x3x4x50 x400001-1/20 x23011/300-3x11102/301/2j00303/2 -93/2 0X40X21x35/2-1/2100-1/400001-1/23/23/20103/4x3入，x1出j-9/2000-3/4所以：所以：所以：所以：X*=(xX*=(xX*=(xX*=(x1 1 1 1,x,x,x,x2 2 2 2,x,x,x,x3 3 3 3)T T T T=(0,5/2,3/2)=(0,5/2,3/2)=(0,5/2,3/2)=(0,5/2,3/2)T T T T Z*=3/2 Z*=3/2 Z*=3/2 Z*=3/2第16页/共39页2023/2/2417单纯形法小结给定LP问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第1.3节内容分7种情况：取取 值值右端项右端项等式或不等式等式或不等式极大或极小极大或极小新加变量系数新加变量系数xj无约束无约束xj 0bi 00，且所有的，且所有的a aikik00时；时；得最优解时，有检验数为得最优解时，有检验数为0 0的非基变量；的非基变量；得最优解时，所有非基变量检验数为负；得最优解时，所有非基变量检验数为负；第19页/共39页2023/2/2420cj40452500CBXBbix1x2x3x4x50 x4100231100 x512033201j4045025100/340 3 45X225x380/31/3102/3-1/320101-11x2入，x4出j000-5因为全因为全因为全因为全 j j j j 0,0,0,0,且且且且 1=0,1=0,1=0,1=0,则有无穷多最优解。则有无穷多最优解。则有无穷多最优解。则有无穷多最优解。所以：其中一个最优解为所以：其中一个最优解为所以：其中一个最优解为所以：其中一个最优解为X*=(0,80/3,20,0,0)X*=(0,80/3,20,0,0)X*=(0,80/3,20,0,0)X*=(0,80/3,20,0,0)T T T T,Z*=1700,Z*=1700,Z*=1700,Z*=1700例1:0-10思考：无穷多最优解的一般形式？第20页/共39页2023/2/2421cj1100CBXBbix1x2x3x40 x3100-21100 x4501-101j1100-50 0X31x12000-112501-101x1入，x4出j020-1因为因为因为因为 2 2 2 2=2,=2,=2,=2,且且且且a a a ai2 i2 i2 i2 全全全全 0 0 0 0所以：无界所以：无界所以：无界所以：无界例2:第21页/共39页2023/2/2422例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页2023/2/2423复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中aL的值及各变量下标mt的值；第23页/共39页2023/2/2424第6节 应用举例一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。.要求解问题的目标函数能用数值指标来反映，且为线性函数；.存在着多种方案；.要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。第24页/共39页2023/2/2425建模步骤建模步骤：第第一一步步：设设置置要要求求解解的的决决策策变变量量。决决策策变变量量选选取取得得当当，不不仅仅能能顺顺利利地地建建立立模模型型而而且且能能方方便便地地求求解解，否则很可能事倍功半。否则很可能事倍功半。第二步：找出所有的限制第二步：找出所有的限制，即约束条件，即约束条件，并用决并用决策变量的线性方程或线性不等式来表示策变量的线性方程或线性不等式来表示。第三步：明确目标要求，并用决策变量的线性函第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加决策变量的非负要求可以根据问题的实际意义加以确定。以确定。第25页/共39页2023/2/2426一般的产品计划问题举例 例1：某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。生生产产产产品品B B的的同同时时产产出出副副产产品品C C，每每生生产产一一吨吨产产品品B B，可可同同时时得得到到2 2吨吨产产品品C C而而毋毋需需外外加加任任何何费费用用；副副产品产品C C一部分可以盈利，剩下的只能报废。一部分可以盈利，剩下的只能报废。出出售售产产品品A A每每吨吨能能盈盈利利400400元元、产产品品B B每每吨吨能能盈盈利利10001000元元，每每销销售售一一吨吨副副产产品品C C能能盈盈利利300300元元，而而剩剩余余要要报报废废的的则则每每吨吨损损失失200200元元。经经市市场场预预测测，在在计计划划期期内内产产品品C C最最大大销销量量为为5 5吨吨。试试列列出出线线性性规规划划模模型型，决定决定A A、B B两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。第26页/共39页2023/2/2427Y数学模型：设：x1产品A的产量，x2产品B的产量，x3产品C的销售量，x4产品C的报废量。依题意，可得第27页/共39页2023/2/2428例2 合理下料问题。现要截取2.9米、2.1米和1.5米的圆钢各100根。而现在仅有一批长7.4米的棒料毛坯，问应如何下料，才能使所消耗的原材料最省。根数根数方案方案需要需要根数根数长度长度III III IVVVI VII VIII2.9120101001002.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页2023/2/2429例3第29页/共39页2023/2/2430练习1：练习2：P57，T2.9第30页/共39页2023/2/2431第31页/共39页2023/2/2432例4.连续投资问题。P53,2-13项目项目 第第1年年第第2年年第第3年年第第4年年第第5年年投资回报率投资回报率投资额限制投资额限制Ax1Ax2Ax3Ax4A115%Bx3B125%4万元万元Cx2C140%3万元万元Dx1Dx2Dx3Dx4Dx5D公债利息公债利息6%投资总额：投资总额：10万元万元第32页/共39页2023/2/2433练习：设某投资者有30 000元可供为期四年的投资，现有五个投资机会可供选择：A:可在每年年初投资，每年每元投资可获0.2元。B:第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。C:第一年初投资，三年后每元投资获利0.8元。这项投资最多不超过20 000元。D:第二年年初投资，两年后每元投资可获利0.6元。这项投资最多不超过15 000元。E:第一年年初投资，四年后每元获利1.7元，这项投资最多不超过20 000元。投资者应如何投资，使他在四年后所拥有资金总额最大？第33页/共39页2023/2/2434第一章 总结基本概念：可行解，基，基解，基可行解，可行基，凸集，顶点基本定理：可行域为凸集；基可行解 顶点；最优解一定在顶点上取得。第34页/共39页2023/2/2435基本问题：1.什么是线性规划问题的数学模型结构？2.如何用图解法及单纯形法判断解的情况？3.什么是线性规划问题的标准型，如何化标准型？4.如何求线性规划的基解，基可行解及最优解？5.单纯形法的计算步骤？6.什么情况要加入人工变量？7.两阶段法的基本步骤？第35页/共39页2023/2/2436单纯形法小结给定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页2023/2/2437添加松弛变量、人工变量列出初始单纯形表添加松弛变量、人工变量列出初始单纯形表所有所有 基变量中有基变量中有非零人工变量非零人工变量某非基变量某非基变量检验数为零检验数为零唯一最优解唯一最优解无穷多最优解无穷多最优解无可行解无可行解对任一对任一 有有 换基继续换基继续YYYYNNN无界解无界解N计算非基变量各列的计算非基变量各列的检验数检验数第37页/共39页2023/2/2438对任一 有 N换基继续换基继续令计算所有非基变量的检验数计算所有非基变量的检验数第38页/共39页2023/2/2439感谢您的观看！第39页/共39页
