第2章 单纯形法(2013使用版)

1、1第第2章章单纯形法单纯形法杨晓艺 数学建模（公修）2主要内容主要内容单纯形法的引入单纯形法的引入2.1单纯形法的计算步骤单纯形法的计算步骤2.2单纯形法的进一步讨论单纯形法的进一步讨论2.3杨晓艺 数学建模（公修）3 先找到一个基可行解（先找到一个基可行解（），），其是否为其是否为最优解，否则，再找到一个使目标函数所改进的基可行解，最优解，否则，再找到一个使目标函数所改进的基可行解，再进行检验，反复再进行检验，反复，直至找到最优解或判定问题无界。，直至找到最优解或判定问题无界。杨晓艺 数学建模（公修）4 某厂生产两种产品，下表给某厂生产两种产品，下表给出了单位产品所需资源及单位产品出了单位产

2、品所需资源及单位产品利润利润 问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使 总利润最大？总利润最大？ max z = 2 x1 + 3 x2x1 + 2x2 8 4x1 16 4x2 12 x1， x20例例 2.1 单纯形法的引入单纯形法的引入杨晓艺 数学建模（公修）5杨晓艺 数学建模（公修）6杨晓艺 数学建模（公修）7杨晓艺 数学建模（公修）8杨晓艺 数学建模（公修）9令非基变量令非基变量 （ x1 , x2）T=（0，0） T 得基可行解：得基可行解： X(0)=(0,0,8,16,12) T , z0=0经济含义：经济含义：不生产产品甲乙，利润为零不生产产品甲乙，利润为

3、零。分析：分析：z = 0+ 2x1 + 3x2 （分别增加单位产品甲、乙，目标函数分别增加（分别增加单位产品甲、乙，目标函数分别增加2、3，即利润分别增加，即利润分别增加2元、元、 3元。）元。） 增加单位产品对目标函数的贡献，这就是增加单位产品对目标函数的贡献，这就是检验检验数数的概念。的概念。杨晓艺 数学建模（公修）10 增加单位产品乙（增加单位产品乙（x2）比甲对目标函数的贡献大（检）比甲对目标函数的贡献大（检验数最大），把非基变量验数最大），把非基变量x2换成基变量，称换成基变量，称x2为为换入变换入变量量，而把基变量，而把基变量x5换成非基变量，称换成非基变量，称x5为为换出变量换

4、出变量。（在选择出基变量时，一定保证所有的变量取值仍非（在选择出基变量时，一定保证所有的变量取值仍非负）（负）（最小比值原则最小比值原则） 事实上，当事实上，当x1 =0，有，有 x3 = 8- 2x20 x4 = 160 （） x5 = 12 - 4 x2 0 min(8/2,-,12/4)=3, 当当x2=3时，时，x5=0。x5为换出基变量。为换出基变量。杨晓艺 数学建模（公修）11确定了确定了换入变量换入变量x2 ，换出变量换出变量x5 以后，得到新的消以后，得到新的消去系统（用非基变量表示基变量）：去系统（用非基变量表示基变量）： x3+2 x2 = 8- x1 （1） x3 = 2

5、- x1+（1/2） x5 x4 = 16-4x1 （2） x4 = 16-4 x1 4x2 = 12- x5 （3） x2 = 3 - （1/4）x5z= 92 x1 -（3/4）x5 令新的非基变量（令新的非基变量（ x1，x5 ）=（0，0）T,得到新的基得到新的基可行解：可行解：X(1)=(0,3,2, 16 , 0) T z1= 9 经济含义：生产乙产品经济含义：生产乙产品3个，获得利润个，获得利润9元。元。(1)-(1/2)(3)杨晓艺 数学建模（公修）12目标函数值还能否增大？目标函数值还能否增大？所有所有非基变量的非基变量的系数均是负数系数均是负数，目标函数值不能目标函数值不能

6、继续增大了。继续增大了。 故故X(3)是最优解，是最优解，最优值是最优值是14。杨晓艺 数学建模（公修）13 x2310 x1Q1Q2 X（3） X（1） Q4X（0） OX（2） Q3X（0） （0，0）X（1） （0，3）X（2） （2，3） X（3） （4，2）迭代过程与图解法对比迭代过程与图解法对比杨晓艺 数学建模（公修）14 2.2 单纯形法的计算步骤单纯形法的计算步骤确定初始基础可行解确定初始基础可行解求最优解的目标函数值求最优解的目标函数值确定改善方向确定改善方向求新的基础可行解求新的基础可行解检查是否为检查是否为最优解？最优解？是是否否杨晓艺 数学建模（公修）15l (1) (

7、1) 按数学模型确定初始可行基和初始基可行解按数学模型确定初始可行基和初始基可行解 l (2) (2) 计算各非基变量计算各非基变量xj的检验数，的检验数， 检查检验数，若所有检验数检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。则已得到最优解，可停止计算。否则转入下一步。 miijijjacc1,njj, 2 , 1, 02.2.1 单纯形法的计算步骤单纯形法的计算步骤杨晓艺 数学建模（公修）16l (3) 在在j0, j=m+1,n中，若有某个中，若有某个k对应对应xk的系数列向量的系数列向量Pk0，则此问题是无界，停止计，则此问题是无界，停止计算。算。l 否则，转入

8、下一步。否则，转入下一步。l (4) 根据根据max(j0)=k，确定，确定xk为换入变量为换入变量（进基，所在列称主元列）（进基，所在列称主元列）l （5）按）按规则（最小比值原则）计算，确定规则（最小比值原则）计算，确定xl为换出变量（出基，所在行称主元行）为换出变量（出基，所在行称主元行）lklikikiabaab0min杨晓艺 数学建模（公修）17l (6) 以以alk为主元进行迭代为主元进行迭代(即用高斯消去法或称为旋转运算即用高斯消去法或称为旋转运算)，把把xk所对应的列向量所对应的列向量l 将将XB列中的列中的xl换为换为xk，得到新的基可行解。重复，得到新的基可行解。重复(2)

9、(6)，直到终止。直到终止。行第变换laaaaPmklkkkk010021杨晓艺 数学建模（公修）18 换基迭代过程：换基迭代过程： 现考虑以下形式的约束方程组现考虑以下形式的约束方程组11,1111122,11222,11n,11mmkknnmmkknnll mmlkklnlmm mmmkkmnmxaxa xa xbxaxa xa xbxaxa xa xbxaxaxa xb 杨晓艺 数学建模（公修）19为了使为了使xk与与xl进行对换，须把进行对换，须把Pk变为单位向量变为单位向量，这可，这可以通过上述方程式系数矩阵的增广矩阵进行初等变换以通过上述方程式系数矩阵的增广矩阵进行初等变换来实现。

10、来实现。 111,1111,1ln,1111lmmknmknl mlklm mmkmnmxxxxxxbaabaaaabaaab杨晓艺 数学建模（公修）201111,111,1ln,11001001010lmmknkmnlkl mllkmkm mmnmlkxxxxxxbaaabaaabaaaaba变换后新的增广矩阵为变换后新的增广矩阵为 杨晓艺 数学建模（公修）21由此可得到变换后系数矩阵各元素的变换关系式：由此可得到变换后系数矩阵各元素的变换关系式：;ljikijikillklkijiljllklkaaaailbbilaaababililaa 是变换后的新元素。是变换后的新元素。 ,iijba

11、例例杨晓艺 数学建模（公修）221216810040010040012154321bxxxxx例例 试用上述方法计算例试用上述方法计算例1所示所示LP问题的两问题的两个基变换个基变换,并求解这个问题的最优解。并求解这个问题的最优解。31624/10010010042/1010154321bxxxxx2 3 0 0 00002 3 0 0 043杨晓艺 数学建模（公修）2331624/10010010042/1010154321bxxxxx2 3 0 0 00032 0 0 0 -3/424 -1234510101/ 2 200412801001/ 43xxxxxb杨晓艺 数学建模（公修）242

12、 3 0 0 02030 0 2 0 1/44 121234510101/ 2 200412801001/ 43xxxxxb123451001/ 40 40021/ 21 4011/ 21/80 2xxxxx b杨晓艺 数学建模（公修）252 3 0 0 02030 0 3/2 -1/8 0123451001/ 40 40021/ 21 4011/ 21/80 2xxxxx b杨晓艺 数学建模（公修）26 2.2.2 单纯形表单纯形表 单纯形法的表格形式是把用单纯形法求出基可单纯形法的表格形式是把用单纯形法求出基可行解、检验其最优性、迭代过程都用表格的方式来行解、检验其最优性、迭代过程都用表格

13、的方式来计算求出，以下用单纯形表表示线性规划模型。计算求出，以下用单纯形表表示线性规划模型。杨晓艺 数学建模（公修）27jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Ziibc 0 0 ijijjacc min(0)iikiikbaa单纯形表单纯形表(表表21)价值系数价值系数基变量的基变量的价值系数价值系数基变量基变量方程右端方程右端常数常数检验数检验数目标函数的目标函数的相反数相反数杨晓艺 数学建模（公修）28 1.计算检验数，由它确定为换人变量计算检验数，由它确定为换人变量2.计算计算，由它确定为换出变

14、量，由它确定为换出变量3.确定主元素确定主元素例例 用单纯形法求解例用单纯形法求解例1。基变量基变量目标函数中各变量的价值系数目标函数中各变量的价值系数杨晓艺 数学建模（公修）29 杨晓艺 数学建模（公修）30 杨晓艺 数学建模（公修）31 杨晓艺 数学建模（公修）32练习练习 用单纯形法求解下述线性规划问题用单纯形法求解下述线性规划问题Ex.123123123123max( )40452423100. .332120,0f xxxxxxxstxxxx x x杨晓艺 数学建模（公修）33 2.3 单纯形法的进一步讨论单纯形法的进一步讨论2.3.1 人工变量法人工变量法2.3.2 退化退化杨晓艺

15、 数学建模（公修）342.4.1 人工变量法人工变量法 设线性规划问题的约束条件设线性规划问题的约束条件 若没有作为若没有作为初始基初始基的的单位矩阵单位矩阵，则分别给每一个约束方程，则分别给每一个约束方程加入人工变量加入人工变量xn+1,xn+m，得到，得到njjjbxP10,; 0,112211222222121111212111mnmnmmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxa杨晓艺 数学建模（公修）35人工变量在目标函数中的系数如何取？人工变量在目标函数中的系数如何取？初始基可行解是什么？初始基可行解是什么？是不是必须加入是不是必须加入m个人工

16、变量？个人工变量？人工变量能否取值非零？人工变量能否取值非零？如何求解带有人工变量的线性规划问题？如何求解带有人工变量的线性规划问题？1、2、3、4、5、杨晓艺 数学建模（公修）362.4.1.1 2.4.1.1 大大M M法法v 在一个线性规划问题的约束条件中加进人工变量后，在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响；为此假定人要求人工变量对目标函数取值不受影响；为此假定人工变量在目标函数中的系数为工变量在目标函数中的系数为(-M)(M(-M)(M为任意大的正数为任意大的正数) )，若为最小化问题，系数取为若为最小化问题，系数取为M M。v 目标函数要实

17、现最大化时，必须把人工变量从基变量目标函数要实现最大化时，必须把人工变量从基变量换出。否则目标函数不可能实现最大化。换出。否则目标函数不可能实现最大化。杨晓艺 数学建模（公修）370,123241123min32131321321321xxxxxxxxxxxxxxz例例 试用大试用大M法求解如下线性规划问题。法求解如下线性规划问题。杨晓艺 数学建模（公修）380,12324112003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz这里这里M是一个任意大的正数是一个任意大的正数。 解解 在上述问题的约束条件中加入松弛变量在上述

18、问题的约束条件中加入松弛变量x4，剩余变，剩余变量量x5，人工变量，人工变量x6,x7，得到，得到杨晓艺 数学建模（公修）39cj -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 M M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj-zj -3+6M 1-M 1-3M 0 M 0 0 杨晓艺 数学建模（公修）40cj -3 1 1 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 M 1 x4 x6 x3 10 1

19、 1 3 0 -2 -2 1 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 1 cj-zj -1 1-M 1-3M 0 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 4 cj-zj -1 0 0 0 1 M-1 M+1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 cj-zj 2 0 0 0 1/3 1/3 M-1/3 M-2/3 杨晓艺

20、 数学建模（公修）41人工变量出基后能否删去该人工变量在系数矩阵人工变量出基后能否删去该人工变量在系数矩阵中所在的列？中所在的列？编程时，编程时，M如何赋值？如何赋值？能否考虑把问题分步解决？能否考虑把问题分步解决？1、2、3、杨晓艺 数学建模（公修）422.4.1.22.4.1.2两阶段法两阶段法第一阶段第一阶段 不考虑原问题是否存在基可行解；给原线不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。量的目标函数和要求实现最小化。目的：目的： 判断原问题是否存在可行解；判断原问题是否存在可行解； 得

21、到一个初始基可行解。得到一个初始基可行解。杨晓艺 数学建模（公修）430,000min1212211222222121111212111211mnnnmmnnmmmnnnnnnnmnnxxxxxbxxaxaxabxxaxaxabxxaxaxaxxxxx约束条件目标函数 用单纯形法求解上述模型，若得到用单纯形法求解上述模型，若得到=0=0，这说明原问题存在基可行解，可以进行第二段这说明原问题存在基可行解，可以进行第二段计算。否则原问题无可行解，应停止计算。计算。否则原问题无可行解，应停止计算。杨晓艺 数学建模（公修）442.4.1.22.4.1.2两阶段法两阶段法第二阶段第二阶段 将第一阶段计算

22、得到的最终表，除去人工将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换原问题的目标变量。将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。各阶函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与单纯形法相同。段的计算方法及步骤与单纯形法相同。杨晓艺 数学建模（公修）45例例 试用两阶段法求解线性规划问题试用两阶段法求解线性规划问题 0,123241123min32131321321321xxxxxxxxxxxxxxz约束条件目标函数杨晓艺 数学建模（公修）460,12324112min765432173165321432176xxxxxxxxxxxx

23、xxxxxxxxx约束条件目标函数杨晓艺 数学建模（公修）47cj 0 0 0 0 0 1 1 CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 1 1 x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj-zj 0 -1 -1 0 1 0 0 0 M 1 x4 x6 x3 10 1 1 3 0 -2 -2 1 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 - 1 - cj-zj 0 -1 0 0 1 0 3 0 1 1 x4 x2 x3 12 1 1 3 0

24、-2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 cj-zj 0 0 0 0 0 1 1 第一阶段第一阶段杨晓艺 数学建模（公修）48第二阶段第二阶段cj -3 1 1 0 0 CB XB b x1 x2 x3 x4 x5 i 0 1 1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 4 - - cj-zj -1 0 0 0 1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 cj-zj 2 0 0 0 1/3 1/3 杨晓艺 数学建模（公修）49练习练习 用大用大M法和两阶段法求解下述线性法和两阶段法求解下述线性规划问题规划问题Ex.123123123123max2357. .2510,0zxxxxxxstxxxx x x杨晓艺 数学建模（公修）502.4.2 退化退化