运筹学-单纯形法.ppt

第第4节节 单纯形法计算步骤单纯形法计算步骤11/13/202411/13/20241 1Step 1 化为标准型，找出初始可行基，并列出初始单纯形表化为标准型，找出初始可行基，并列出初始单纯形表上述初始单纯形表中，最后一行称为检验数上述初始单纯形表中，最后一行称为检验数j11/13/202411/13/20242 2基基向量 x1x2x3x4x5Z可行解 图中点B1P3P4P50081612 0OB2P2P4P504016-412 AB3P2P3P500无解B4P2P3P40321609Q4B5P1P4P5800-16 12 16 CB6P1P3P5404012 8Q1B7P1P3P400无解B8P1P2P54200414 Q2B9P1P2P42308013 Q3B10P1P2P343-20017 Bx2x1O11223344Q1Q2Q3Q4ABC11/13/202411/13/20243 3Step2：检查非基变量所对应的检验数检查非基变量所对应的检验数j，若所有的，若所有的j0，则当，则当前的基可行解就是最优解，当前的目标函数值就是最优值，停前的基可行解就是最优解，当前的目标函数值就是最优值，停止计算。止计算。否则，转入下一步。否则，转入下一步。Step3：若存在一个若存在一个k0，k所对应的变量所对应的变量xk的系数列向量的系数列向量Pk0(即即Pk中每一个分量中每一个分量aik0)，则该，则该LP无有限最优解，停止计算。无有限最优解，停止计算。否则，转入下一步。否则，转入下一步。Step4：进行可行基的迭代。进行可行基的迭代。重复以上步骤重复以上步骤11/13/202411/13/20244 4例例7 用单纯形法求解例用单纯形法求解例6。max z=2x1+3x2s.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 xj0，j=1,2,511/13/202411/13/20245 5练习：练习：分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。Max Z=10 x1+5x2 3x1+4x29 5x1+2x2 8 x1，x2011/13/202411/13/20246 6解：解：解：解：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对应B11/13/202411/13/20247 7回顾：单纯形法求解步骤：回顾：单纯形法求解步骤：11/13/202411/13/20248 8第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论11/13/202411/13/20249 9第第5节节 单纯形法的进一步讨论单纯形法的进一步讨论一、人工变量法（大一、人工变量法（大M法）法）约束条件：约束条件：“”加一个松弛变量加一个松弛变量“”减一个剩余变量后，再加一个人工变量减一个剩余变量后，再加一个人工变量“”加一个人工变量加一个人工变量目标函数：目标函数：人工变量的系数为人工变量的系数为“M”，即罚因子，即罚因子若线性规划问题有最优解则人工变量必为若线性规划问题有最优解则人工变量必为0。11/13/202411/13/20241010MaxZ=-3x1+x3 x1+x2+x34 -2x1+x2-x31 3x2+x3=9 xi 0,j=1,2,3增加人工变量后，线性规划问题中就存在一个增加人工变量后，线性规划问题中就存在一个B B为单位矩阵，为单位矩阵，后面可以根据我们前面所讲的单纯形法来进行求解。后面可以根据我们前面所讲的单纯形法来进行求解。MaxZ=-3x1+x3Mx6-Mx7 x1+x2+x3+x4 =4 -2x1+x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7标准化及变形11/13/202411/13/20241111练习：练习：列出初始单纯形表，并求解第2小题的最优解1.P55，2.2（1）2.2.11/13/202411/13/20241212cj-30100-M-MCBXBbix1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001单纯形表单纯形表单纯形表单纯形表j-3-2M 4M100 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/211/13/202411/13/20241313二、两阶段法二、两阶段法第一阶段暂不考虑原问题是否存在基可行解，给原问题加第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为小化），人工变量的价值系数一般为1，约束条件和原问，约束条件和原问题的一样。题的一样。当第一阶段中目标函数的最优值当第一阶段中目标函数的最优值0，即人工变量，即人工变量0，则，则转入第二阶段；若第一阶段中目标函数的最优值不等于转入第二阶段；若第一阶段中目标函数的最优值不等于0，即人工变量不等于，即人工变量不等于0，则判断原问题为无解。，则判断原问题为无解。第二阶段：将第一阶段计算所得的单纯形表划去人工变量第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数作为第二所在的列，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。阶段的初始单纯形表，进行进一步的求解。11/13/202411/13/20241414求解辅助问题，得到辅助问题的最优解引进人工变量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,711/13/202411/13/20241515cj00000-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所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。去掉人工变量，得原问题的一个即可行基。11/13/202411/13/20241616（第二阶段）单纯形表（第二阶段）单纯形表（第二阶段）单纯形表（第二阶段）单纯形表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*=(x X*=(x X*=(x X*=(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/211/13/202411/13/20241717单纯形法小结单纯形法小结给定给定LP问题首先化为标准型，选取或构造一个单位问题首先化为标准型，选取或构造一个单位矩阵作为基，求出初始基可行解，并列出初始单纯矩阵作为基，求出初始基可行解，并列出初始单纯形表。标准化过程按第形表。标准化过程按第1.3节内容分节内容分7种情况：种情况：取取 值值右端项右端项等式或不等式等式或不等式极大或极小极大或极小新加变量系数新加变量系数xj无约束无约束xj 0bi 00，且所有的，且所有的，且所有的，且所有的a aikik00时；时；时；时；得最优解时，有检验数为得最优解时，有检验数为得最优解时，有检验数为得最优解时，有检验数为0 0的非基变量；的非基变量；的非基变量；的非基变量；得最优解时，所有非基变量检验数为负；得最优解时，所有非基变量检验数为负；得最优解时，所有非基变量检验数为负；得最优解时，所有非基变量检验数为负；11/13/202411/13/20242020cj40452500CBXBbix1x2x3x4x50 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思考：无穷多最优解的一般形式？思考：无穷多最优解的一般形式？11/13/202411/13/20242121cj1100CBXBbix1x2x3x40 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:11/13/202411/13/20242222例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 011/13/202411/13/20242323复习题复习题：下表为一求解极大值线性规划问题的初始单纯型表及迭代后的表，为松弛变量，试求表中aL的值及各变量下标mt的值；11/13/202411/13/20242424第第6节节 应用举例应用举例一般而言，一个经济、管理问题凡是满足一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。以下条件时，才能建立线性规划模型。.要求解问题的目标函数能用数值指要求解问题的目标函数能用数值指标来反映，且为线性函数；标来反映，且为线性函数；.存在着多种方案；存在着多种方案；.要求达到的目标是在一定条件下实要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描现的，这些约束可用线性等式或不等式描述。述。11/13/202411/13/20242525建模步骤建模步骤：第第第第一一一一步步步步：设设设设置置置置要要要要求求求求解解解解的的的的决决决决策策策策变变变变量量量量。决决决决策策策策变变变变量量量量选选选选取取取取得得得得当当当当，不不不不仅仅仅仅能能能能顺顺顺顺利利利利地地地地建建建建立立立立模模模模型型型型而而而而且且且且能能能能方方方方便便便便地地地地求求求求解解解解，否否否否则则则则很可能事倍功半。很可能事倍功半。很可能事倍功半。很可能事倍功半。第二步：找出所有的限制第二步：找出所有的限制第二步：找出所有的限制第二步：找出所有的限制，即约束条件，即约束条件，即约束条件，即约束条件，并用决策并用决策并用决策并用决策变量的线性方程或线性不等式来表示变量的线性方程或线性不等式来表示变量的线性方程或线性不等式来表示变量的线性方程或线性不等式来表示。第三步：明确目标要求，并用决策变量的线性函数第三步：明确目标要求，并用决策变量的线性函数第三步：明确目标要求，并用决策变量的线性函数第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。来表示，确定对函数是取极大还是取极小的要求。来表示，确定对函数是取极大还是取极小的要求。来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以决策变量的非负要求可以根据问题的实际意义加以决策变量的非负要求可以根据问题的实际意义加以决策变量的非负要求可以根据问题的实际意义加以确定。确定。确定。确定。11/13/202411/13/20242626一般的产品计划问题举例一般的产品计划问题举例 例例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两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。两种产品的产量，使工厂总的利润最大。11/13/202411/13/20242727Y数学模型：数学模型：设设：x1产产品品A的的产产量量，x2产产品品B的的产产量量，x3产产品品C的的销销售售量量，x4产产品品C的报废量。依题意，可得的报废量。依题意，可得11/13/202411/13/20242828例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种更合理。11/13/202411/13/20242929例例311/13/202411/13/20243030练习练习1：练习练习2：P57，T2.911/13/202411/13/2024313111/13/202411/13/20243232例例4.连续投资问题。连续投资问题。P53,2-13项目项目 第第1年年第第2年年第第3年年第第4年年第第5年年投资回报率投资回报率投资额限制投资额限制Ax1Ax2Ax3Ax4A115%Bx3B125%4万元万元Cx2C140%3万元万元Dx1Dx2Dx3Dx4Dx5D公债利息公债利息6%投资总额：投资总额：10万元万元11/13/202411/13/20243333练习：练习：设某投资者有设某投资者有30 000元可供为期四年的投资，现有五个投资元可供为期四年的投资，现有五个投资机会可供选择：机会可供选择：A:可在每年年初投资，每年每元投资可获可在每年年初投资，每年每元投资可获0.2元。元。B:第一年年初或第三年年初投资，每两年每元投资可获利润第一年年初或第三年年初投资，每两年每元投资可获利润0.5元，两年后获利。元，两年后获利。C:第一年初投资，三年后每元投资获利第一年初投资，三年后每元投资获利0.8元。这项投资最元。这项投资最多不超过多不超过20 000元。元。D:第二年年初投资，两年后每元投资可获利第二年年初投资，两年后每元投资可获利0.6元。这项投元。这项投资最多不超过资最多不超过15 000元。元。E:第一年年初投资，四年后每元获利第一年年初投资，四年后每元获利1.7元，这项投资最多元，这项投资最多不超过不超过20 000元。元。投资者应如何投资，使他在四年后所拥有资金总额最大？投资者应如何投资，使他在四年后所拥有资金总额最大？11/13/202411/13/20243434第一章第一章 总结总结基本概念：基本概念：可行解，基，基解，基可行解，可行基，可行解，基，基解，基可行解，可行基，凸集，顶点凸集，顶点基本定理：基本定理：可行域为凸集；可行域为凸集；基可行解基可行解 顶点；顶点；最优解一定在顶点上取得。最优解一定在顶点上取得。11/13/202411/13/20243535基本问题：基本问题：1.什么是线性规划问题的数学模型结构？什么是线性规划问题的数学模型结构？2.如何用图解法及单纯形法判断解的情况？如何用图解法及单纯形法判断解的情况？3.什么是线性规划问题的标准型，如何化标准型？什么是线性规划问题的标准型，如何化标准型？4.如何求线性规划的基解，基可行解及最优解？如何求线性规划的基解，基可行解及最优解？5.单纯形法的计算步骤？单纯形法的计算步骤？6.什么情况要加入人工变量？什么情况要加入人工变量？7.两阶段法的基本步骤？两阶段法的基本步骤？11/13/202411/13/20243636单纯形法小结单纯形法小结给定给定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-M11/13/202411/13/20243737添加松弛变量、人工变量列出初始单纯形表添加松弛变量、人工变量列出初始单纯形表所有所有 基变量中有基变量中有非零人工变量非零人工变量某非基变量某非基变量检验数为零检验数为零唯一最优解唯一最优解无穷多最优解无穷多最优解无可行解无可行解对任一对任一 有有 换基继续换基继续YYYYNNN无界解无界解N计算非基变量各列的计算非基变量各列的检验数检验数11/13/202411/13/20243838对任一 有 N换基继续换基继续令计算所有非基变量的检验数计算所有非基变量的检验数11/13/202411/13/20243939