线性规划及其应用3线性规划求解方法课件.ppt

1、 3.3 线性规划求解方法线性规划求解方法1重庆大学经济与工商管理学院 肖智4 4、作用：线性规划理论的几何意义，并说明线性规划解、作用：线性规划理论的几何意义，并说明线性规划解 的四种情况（唯一最优解、无穷最优解、有可的四种情况（唯一最优解、无穷最优解、有可 行解而无最优解、无可行解）。行解而无最优解、无可行解）。5 5、举例说明。、举例说明。三、单纯形三、单纯形法法 1 1、单纯形法的概述、单纯形法的概述 1 1）适用范围：线性规划标准形问题。适用范围：线性规划标准形问题。 2 2）基本原理：）基本原理： （1 1）目标：使）目标：使Z=CXZ=CX最大，在最大，在AX=b,X0AX=b,

2、X0条件下；条件下； （2 2）理论：线性规划基本理论）理论：线性规划基本理论 （3 3）结论：）结论： 3.3 线性规划求解方法线性规划求解方法2重庆大学经济与工商管理学院 肖智OXOXNXBbBXXNBCCbBCZOXOXbNXBXXCXCZOXbAXCXZNBNBNBNBNBNBNNBB,)(max,maxmax1111 （3.3-1)3.3-1) (3.3-2)(3.3-2) (3.3-3)(3.3-3) 3.3 线性规划求解方法线性规划求解方法3重庆大学经济与工商管理学院 肖智 要使要使Z=CXZ=CX达到最大，由达到最大，由(3.3-3)(3.3-3)知只需去寻找一恰当知只需去寻找

3、一恰当的基的基B B使得使得 ( (称称 为检验数向量为检验数向量) )3 3）基本思路：）基本思路： 基于线性规划问题的标准形，先确定一初始基可行解基于线性规划问题的标准形，先确定一初始基可行解X X0 0，并由此开始在保证目标函数值不下降的情况下逐次施，并由此开始在保证目标函数值不下降的情况下逐次施行从一个基可行解到另一个基可行解的转换。如此进行下行从一个基可行解到另一个基可行解的转换。如此进行下去，直到取得最优解或判明问题无最优解为止。去，直到取得最优解或判明问题无最优解为止。4 4）基本步骤：）基本步骤：（1 1）对一般线性规划问题标准化；）对一般线性规划问题标准化；（2 2）确定一初

4、始基可行解）确定一初始基可行解X X0 0；（3 3）若所有检验数）若所有检验数 j j00（ j j为为 的第的第j j个分量）个分量）, , 则则X X0 0是线性规划问题的最优解，停止计算；否则转是线性规划问题的最优解，停止计算；否则转(4)(4) ONBCCBN1ONBCCBN1NBCCBN1 3.3 线性规划求解方法线性规划求解方法4重庆大学经济与工商管理学院 肖智（4 4）若存在）若存在 t t0 0所对应的系数列向量所对应的系数列向量p pt tOO，则线性规，则线性规划问题无最优解，停止计算；否则转（划问题无最优解，停止计算；否则转（5 5）。）。（5 5）按最大检验数规则：）

5、按最大检验数规则： 确定进基变量确定进基变量x xk k和主列和主列p pk k；再按最小比值规则：；再按最小比值规则： 确定出基变量确定出基变量x xl l和主元和主元a alklk。（6 6）以主元）以主元a alklk进行换基迭代得一新的基可行解进行换基迭代得一新的基可行解x x1 1, ,将将x x1 1 记记为为x x0 0返回到（返回到（3 3）。）。5 5）基本工具：计算机或单纯形表。）基本工具：计算机或单纯形表。kjjj0|maxlklikikiiabaab0|min 3.3 线性规划求解方法线性规划求解方法5重庆大学经济与工商管理学院 肖智2 2、单纯形法应用举例：、单纯形法

6、应用举例： (3.3-4)(3.3-4)0,060004.040001.04.0120005.06.01025max212212121xxxxxxxxxZ 3.3 线性规划求解方法线性规划求解方法6重庆大学经济与工商管理学院 肖智第一步第一步 标准化标准化 (3.3-5)(3.3-5)第二步第二步 建立初始单纯形表建立初始单纯形表 5,4,3,2,1,060004.040001.04.0120005.06.01025max5242132121jxxxxxxxxxxxZj 3.3 线性规划求解方法线性规划求解方法7重庆大学经济与工商管理学院 肖智 目标函数系数2510000资源拥有量 决策变量x

7、1x2x3x4x50( x3 的目标系数）x30.60.5100120000 ( x4 的目标系数）x40.40.101040000 ( x5 的目标系数）x50.00.40016000最优性检验数25100000表表3.3-13.3-1 3.3 线性规划求解方法线性规划求解方法8重庆大学经济与工商管理学院 肖智此表对应一个可行方案和该方案最优检验结果。此表对应一个可行方案和该方案最优检验结果。可行方案：可行方案： x x1 1=x=x2 2=0, x=0, x3 3=12000, x=12000, x4 4=4000, x=4000, x5 5=6000.=6000.最优性检验结果：检验值全

8、部非负（若全部非正，则可行最优性检验结果：检验值全部非负（若全部非正，则可行方案是最优方案）方案是最优方案） 3.3 线性规划求解方法线性规划求解方法9重庆大学经济与工商管理学院 肖智 目标函数系数2510000可行方案 决策变量x1x2x3x4x5 0 x300.351-1.506000 25x110.2502.5010000 0 x500.40016000 最优性检验数03.750-62.50250000第三步：改进当前可行方案，计算下一张单纯形表。第三步：改进当前可行方案，计算下一张单纯形表。表表3.3-23.3-2 3.3 线性规划求解方法线性规划求解方法10重庆大学经济与工商管理学院

9、 肖智 目标函数系数2510000可行方案 决策变量x1x2x3x4x5 0 x3001-1.5-0.875750 25x11002.5-0.6256250 10 x201002.515000最优性检验数000- 62.5-9.375306250第四步：改进当前可行方案，计算下一张单纯形表。第四步：改进当前可行方案，计算下一张单纯形表。 表表3.3-33.3-3 3.3 线性规划求解方法线性规划求解方法11重庆大学经济与工商管理学院 肖智最优性检验结果：检验值全部为非正最优性检验结果：检验值全部为非正最优方案最优方案: : x x1 1=6250 ( =6250 ( 件件), x), x2 2

10、=15000( =15000( 件件), ), x x3 3= x= x4 4=x=x5 5=0( =0( 件件). ).最大效益为最大效益为: 306250( : 306250( 美元美元) ) 3.3 线性规划求解方法线性规划求解方法12重庆大学经济与工商管理学院 肖智3 3、初始基可行解的求法：、初始基可行解的求法： 在前边的讨论中我们在前边的讨论中我们总假定当问题化为标准型后，系总假定当问题化为标准型后，系数矩阵中有一个全部由松弛变量列向量构成的单位矩阵，数矩阵中有一个全部由松弛变量列向量构成的单位矩阵，如果右边项如果右边项系数全都大于或等于零，只要取该单位矩阵为系数全都大于或等于零，

11、只要取该单位矩阵为初始基就可以得到一个初始基本可行解。但在一般情况下，初始基就可以得到一个初始基本可行解。但在一般情况下，化为标准型的矩阵中不一定含有单位短阵。例如，当线性化为标准型的矩阵中不一定含有单位短阵。例如，当线性规划问题有等式约束时就无法引入松弛变量；如果约束的规划问题有等式约束时就无法引入松弛变量；如果约束的右边项系数出现负值时也无法直接得到一个初始可行解。右边项系数出现负值时也无法直接得到一个初始可行解。在这种情况下，可引入人工变量来构造一个初始基。在这种情况下，可引入人工变量来构造一个初始基。具体做法是：具体做法是： 1)1)将所有约束的右边项值调整为大于或等于零：对右边项将所

12、有约束的右边项值调整为大于或等于零：对右边项 3.3 线性规划求解方法线性规划求解方法13重庆大学经济与工商管理学院 肖智为负的约束，约束两边同乘一为负的约束，约束两边同乘一l l。 2)2)对小于等于型约束对小于等于型约束()()，仍引入一个松弛变量。，仍引入一个松弛变量。 3)3)对大于等于型约束对大于等于型约束()()，引入一个剩余变量和一个人工，引入一个剩余变量和一个人工变变 量。量。 4)4)对等于型约束对等于型约束( () )，引入一个人工变量。，引入一个人工变量。 通过以上调整后，每一个约束或者有一个松弛变量，或通过以上调整后，每一个约束或者有一个松弛变量，或者有一个人工变量，它

13、们构成的单位矩阵可以作为一个初者有一个人工变量，它们构成的单位矩阵可以作为一个初始基，可见，调整后的问题一定有可行解。然而，对原问始基，可见，调整后的问题一定有可行解。然而，对原问题来说，新引入的人工变量是多余的，如果人工变量在最题来说，新引入的人工变量是多余的，如果人工变量在最后的结果中取正值，则表明该解不满足原问题约束条件。后的结果中取正值，则表明该解不满足原问题约束条件。因此，尽管引入人工变量后我们可以很容易找到一个初始因此，尽管引入人工变量后我们可以很容易找到一个初始 3.3 线性规划求解方法线性规划求解方法14重庆大学经济与工商管理学院 肖智基，然而该基不一定是原问题的可行基，只有当

14、人工变量基，然而该基不一定是原问题的可行基，只有当人工变量都变为非基变量或都为零时，引入人工变量的问题才与原都变为非基变量或都为零时，引入人工变量的问题才与原问题等价。因此，应通过某种方法把所有的人工变量从基问题等价。因此，应通过某种方法把所有的人工变量从基中赶出去才能得到原问题的一个可行基。常用的方法有以中赶出去才能得到原问题的一个可行基。常用的方法有以下两种：下两种： （1 1）大）大MM法法 大大MM法实质上是一种罚函数法，它在目标函数中赋予人法实质上是一种罚函数法，它在目标函数中赋予人工变量一个很大的负系数工变量一个很大的负系数( (一一M)M)。由于人工变量对目标函数。由于人工变量对

15、目标函数有很大的负影响，单纯形方法的寻优机制会自动将人工变有很大的负影响，单纯形方法的寻优机制会自动将人工变量赶到基外，从而找到一个原问题的可行基。量赶到基外，从而找到一个原问题的可行基。 用单纯形表计算时，可直接在目标函数中使用用单纯形表计算时，可直接在目标函数中使用MM参数，参数， 3.3 线性规划求解方法线性规划求解方法15重庆大学经济与工商管理学院 肖智通过人的计算和判断进行单纯形迭代。用计算机计算时，由通过人的计算和判断进行单纯形迭代。用计算机计算时，由于计算机无法直接使用参数计算，于计算机无法直接使用参数计算，MM必须赋予一个较大的值，必须赋予一个较大的值，并视求解的情况对并视求解

16、的情况对MM值进行调整。如果给定值进行调整。如果给定MM后，计算所得后，计算所得的最优基已不含人工变量，该解即为最优可行解。当给定的的最优基已不含人工变量，该解即为最优可行解。当给定的MM足够大时，最优解中仍含有人工变量，则可判断原问题无足够大时，最优解中仍含有人工变量，则可判断原问题无可行解。下面举例说明如何使用大可行解。下面举例说明如何使用大MM法。法。 例：用大例：用大MM法求解下列线性规划问题：法求解下列线性规划问题： (3.3-6)(3.3-6)0, 01020316232max2121212121xxxxxxxxxxZ6 , 5 , 4 , 3 , 2 , 1, 010000200

17、031600020032max654321654321654321654321jxxxxxxxxxxxxxxxxxxxMxMxxxxxZj 3.3 线性规划求解方法线性规划求解方法16重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-43.3-4 cj2 300-M-MbxB CBx1x2x3x4x5x6x302 21 11 10 00 00 01616x5-M1 13 30 0-1-11 10 02020 x6-M1 11 10 00 00 01 11010 j2+2M2+2M3+4M3+4M0 0-M-M0 00 0-30M-30Mx305/35/30 01 11

18、/31/3-1/3-1/30 028/328/3x231/31/31 10 0-1/3-1/31/31/30 020/320/3x6-M2/32/30 00 01/31/3-1/3-1/31 110/310/3j1+2M/31+2M/30 00 01+M/31+M/3-1-4M/3-1-4M/30 020-20-10M/310M/3 3.3 线性规划求解方法线性规划求解方法17重庆大学经济与工商管理学院 肖智表表3.3-43.3-4续续 cj2 300-M-MbxB CBx1x2x3x4x5x6x300 00 01 1-1/2-1/21/21/2-5/2-5/21 1x230 01 10 0-

19、1/2-1/21/21/2-1/2-1/25 5x121 10 00 01/21/2-1/2-1/23/23/25 5 j0 00 00 01/21/2-1/2-M-1/2-M-3/2-M-3/2-M2525x301 10 01 10 00 0-1-16 6x231 11 10 00 00 01 11010 x402 20 00 01 1-1-13 31010j-1-10 00 00 0-M-M-3-M-3-M3030 3.3 线性规划求解方法线性规划求解方法18重庆大学经济与工商管理学院 肖智该问题的最优解为：该问题的最优解为：X X* *=(0=(0，10)10)T T； 最优值为最优值为

20、: Z: Z* *=30=30与与计算机计算计算机计算结果相同。结果相同。 大大MM法的优点是方法比较直观，易于理解和手工计算，法的优点是方法比较直观，易于理解和手工计算，缺点是当使用计算机计算时，由于缺点是当使用计算机计算时，由于MM值较大容易引起数值较大容易引起数值计算上的困难，所以几乎所有商业线性规划软件都不值计算上的困难，所以几乎所有商业线性规划软件都不使用大使用大MM法而使用另外一种方法法而使用另外一种方法两阶段法。两阶段法。（2 2）两阶段法）两阶段法 顾名思义，两阶段法是将线性规划求解过程分为两个顾名思义，两阶段法是将线性规划求解过程分为两个阶段。第一阶段只是寻找一个初始可行基，

21、第二阶段再阶段。第一阶段只是寻找一个初始可行基，第二阶段再按正常方法寻找最优解。按正常方法寻找最优解。 3.3 线性规划求解方法线性规划求解方法19重庆大学经济与工商管理学院 肖智第一阶段：在原问题中引入人工变量并找到一个初始基。另第一阶段：在原问题中引入人工变量并找到一个初始基。另构造一个新的求极小值的目标函数，该目标函数除人工变量构造一个新的求极小值的目标函数，该目标函数除人工变量的系数为的系数为1 1以外，其余变量的目标函数系数都为零。求解该以外，其余变量的目标函数系数都为零。求解该线性规划问题，在不退化的前提下，如果得到的最优解值为线性规划问题，在不退化的前提下，如果得到的最优解值为零

22、，表明所有的人工变量已经不在基中。第一阶段的最优解零，表明所有的人工变量已经不在基中。第一阶段的最优解即是原问题的一个基可行解。即是原问题的一个基可行解。 第二阶段：将原目标函数换回，以第一阶段得到的可行基第二阶段：将原目标函数换回，以第一阶段得到的可行基为初始基进行迭代，直到找到最优基为止。在第二阶段的迭为初始基进行迭代，直到找到最优基为止。在第二阶段的迭代中可以删去所有人工变量，保留它们只会增加不必要的计代中可以删去所有人工变量，保留它们只会增加不必要的计算。下面举例说明两阶段法求解过程。算。下面举例说明两阶段法求解过程。 3.3 线性规划求解方法线性规划求解方法20重庆大学经济与工商管理

23、学院 肖智例：用两阶段法求解下列线性规划问题：例：用两阶段法求解下列线性规划问题： (3.3-7) (3.3-7) 第一阶段模型：第一阶段模型： (3.3-8)(3.3-8)6 , 5 , 4 , 3 , 2 , 1, 01000020003160002)max(65432165432165432165jxxxxxxxxxxxxxxxxxxxxxwj0,01020316232max2121212121xxxxxxxxxxZ 3.3 线性规划求解方法线性规划求解方法21重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-53.3-5 cj0 000-1-1bxB CBx1

24、x2x3x4x5x6x302 21 11 10 00 00 01616x5-11 13 30 0-1-11 10 02020 x6-11 11 10 00 00 01 11010 j2 24 40 0-1-10 00 0-30-30 x305/35/30 01 11/31/3-1/3-1/30 028/328/3x201/31/31 10 0-1/3-1/31/31/30 020/320/3x6-12/32/30 00 01/31/3-1/3-1/31 110/310/3j2/32/30 00 01/31/3-4/3-4/30 0-10/3-10/3 3.3 线性规划求解方法线性规划求解方法2

25、2重庆大学经济与工商管理学院 肖智表表3.3-53.3-5续续第二阶段模型：第二阶段模型： (3.3-9) (3.3-9) cj0 000-1-1bxB CBx1x2x3x4x5x6x300 00 01 1-1/2-1/21/21/2-5/2-5/21 1x200 01 10 0-1/2-1/21/21/2-1/2-1/25 5x101 10 00 01/21/2-1/2-1/23/23/25 5 j0 00 00 00 0-1-1-1-10 04 , 3 , 2 , 1, 055 . 00055 . 00015 . 00032max43214321432121jxxxxxxxxxxxxxxx

26、Zj 3.3 线性规划求解方法线性规划求解方法23重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-63.3-6 cj2 300bxB CBx1x2x3x4x300 00 01 1-1/2-1/21 1X230 01 10 0-1/2-1/25 5X121 10 00 01/21/25 5 j0 00 00 01/21/22525x301 10 01 10 06 6x231 11 10 00 01010 x402 20 00 01 11010j-1-10 00 00 03030 3.3 线性规划求解方法线性规划求解方法24重庆大学经济与工商管理学院 肖智0,01020316232max2121212121xxxxxxxxxxZ通过上述讨论，对于线性规划模型：通过上述讨论，对于线性规划模型：应用计算机方法、图解法、单纯形法、大应用计算机方法、图解法、单纯形法、大MM法、两阶段法、两阶段法均可求得相同的最优解法均可求得相同的最优解:X:X* *=(0=(0，10)10)T T和和 最优值最优值:Z:Z* *=30=30 3.3 线性规划求解方法线性规划求解方法25重庆大学经济与工商管理学院 肖智 THE END