线性规划及其应用线性规划求解方法精品文稿.ppt

《线性规划及其应用线性规划求解方法精品文稿.ppt》由会员分享，可在线阅读，更多相关《线性规划及其应用线性规划求解方法精品文稿.ppt（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、大，在AX=b,X0AX=b,X0条件下；条件下；（2 2）理论：线性规划基本理论）理论：线性规划基本理论 （3 3）结论：）结论：第2页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法3重庆大学经济与工商管理学院 肖智 （3.3-1)(3.3-2)(3.3-3)第3页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法4重庆大学经济与工商管理学院 肖智 要使要使Z=CXZ=CX达到最大，由达到最大，由(3.3-3)(3.3-3)知只需去寻找一恰当知只需去寻找一恰当的基的基B B使得使得 (称称 为检验数向量为检验数向量)3 3）基本思路：）基本思路：基于线性规

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

4、j j个分量）个分量）,则则X X0 0是线性规划问题的最优解，停止计算；否则转是线性规划问题的最优解，停止计算；否则转(4)(4)第4页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法5重庆大学经济与工商管理学院 肖智（4 4）若若存存在在 t t0 0所所对对应应的的系系数数列列向向量量p pt tOO，则则线线性性规规划问题无最优解，停止计算；否则转（划问题无最优解，停止计算；否则转（5 5）。）。（5 5）按最大检验数规则：）按最大检验数规则：确定进基变量确定进基变量x xk k和主列和主列p pk k；再按最小比值规则：；再按最小比值规则：确定出基变量确定出基变量x

5、 xl l和主元和主元a alklk。（6 6）以以主主元元a alklk进进行行换换基基迭迭代代得得一一新新的的基基可可行行解解x x1 1,将将x x1 1 记记为为x x0 0返回到（返回到（3 3）。）。5 5）基本工具：计算机或单纯形表。）基本工具：计算机或单纯形表。第5页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法6重庆大学经济与工商管理学院 肖智2 2、单纯形法应用举例：、单纯形法应用举例：(3.3-4)(3.3-4)第6页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法7重庆大学经济与工商管理学院 肖智第一步第一步 标准化标准化 (3.3

6、-5)(3.3-5)第二步第二步 建立初始单纯形表建立初始单纯形表 第7页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法8重庆大学经济与工商管理学院 肖智 目标函数系数2510000资源拥有量 决策变量x1x2x3x4x50(x3 的目标系数）x30.60.5100120000(x4 的目标系数）x40.40.101040000(x5 的目标系数）x50.00.40016000最优性检验数25100000表3.3-1第8页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法9重庆大学经济与工商管理学院 肖智此表对应一个可行方案和该方案最优检验结果。此表对应一个

7、可行方案和该方案最优检验结果。可行方案：可行方案：x x1 1=x=x2 2=0,x=0,x3 3=12000,x=12000,x4 4=4000,x=4000,x5 5=6000.=6000.最优性检验结果：检验值全部非负（若全部非正，则可行最优性检验结果：检验值全部非负（若全部非正，则可行方案是最优方案）方案是最优方案）第9页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法10重庆大学经济与工商管理学院 肖智 目标函数系数2510000可行方案 决策变量x1x2x3x4x5 0 x300.351-1.506000 25x110.2502.5010000 0 x500.40

8、016000 最优性检验数03.750-62.50250000第三步：改进当前可行方案，计算下一张单纯形表。表3.3-2第10页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法11重庆大学经济与工商管理学院 肖智 目标函数系数2510000可行方案 决策变量x1x2x3x4x5 0 x3001-1.5-0.875750 25x11002.5-0.6256250 10 x201002.515000最优性检验数000-62.5-9.375306250第四步：改进当前可行方案，计算下一张单纯形表。表3.3-3第11页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法

9、12重庆大学经济与工商管理学院 肖智最优性检验结果：检验值全部为非正最优性检验结果：检验值全部为非正最优方案最优方案:x x1 1=6250(=6250(件件),x),x2 2=15000(=15000(件件),),x x3 3=x=x4 4=x=x5 5=0(=0(件件).).最大效益为最大效益为:306250(:306250(美元美元)第12页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法13重庆大学经济与工商管理学院 肖智3 3、初始基可行解的求法：、初始基可行解的求法：在前边的讨论中我们在前边的讨论中我们总假定当问题化为标准型后，系数矩总假定当问题化为标准型后，系数

10、矩阵中有一个全部由松弛变量列向量构成的单位矩阵，如果右阵中有一个全部由松弛变量列向量构成的单位矩阵，如果右边项边项系数全都大于或等于零，只要取该单位矩阵为初始基就可以得到系数全都大于或等于零，只要取该单位矩阵为初始基就可以得到一个初始基本可行解。但在一般情况下，化为标准型的矩阵中不一定一个初始基本可行解。但在一般情况下，化为标准型的矩阵中不一定含有单位短阵。例如，当线性规划问题有等式约束时就无法引入松弛含有单位短阵。例如，当线性规划问题有等式约束时就无法引入松弛变量；如果约束的右边项系数出现负值时也无法直接得到一个初始可变量；如果约束的右边项系数出现负值时也无法直接得到一个初始可行解。在这种情

11、况下，可引入人工变量来构造一个初始基。行解。在这种情况下，可引入人工变量来构造一个初始基。具体做法是：具体做法是：1)1)将所有约束的右边项值调整为大于或等于零：对右边项将所有约束的右边项值调整为大于或等于零：对右边项第13页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法14重庆大学经济与工商管理学院 肖智为负的约束，约束两边同乘一为负的约束，约束两边同乘一l l。2)2)对小于等于型约束对小于等于型约束()()，仍引入一个松弛变量。，仍引入一个松弛变量。3)3)对大于等于型约束对大于等于型约束()()，引入一个剩余变量和一个人工变，引入一个剩余变量和一个人工变 量。量。4

12、)4)对等于型约束对等于型约束()，引入一个人工变量。，引入一个人工变量。通过以上调整后，每一个约束或者有一个松弛变量，或者有通过以上调整后，每一个约束或者有一个松弛变量，或者有一个人工变量，它们构成的单位矩阵可以作为一个初始基，可见，一个人工变量，它们构成的单位矩阵可以作为一个初始基，可见，调整后的问题一定有可行解。然而，对原问题来说，新引入的人调整后的问题一定有可行解。然而，对原问题来说，新引入的人工变量是多余的，如果人工变量在最后的结果中取正值，则表明工变量是多余的，如果人工变量在最后的结果中取正值，则表明该解不满足原问题约束条件。因此，尽管引入人工变量后我们可该解不满足原问题约束条件。

13、因此，尽管引入人工变量后我们可以很容易找到一个初始以很容易找到一个初始第14页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法15重庆大学经济与工商管理学院 肖智基，然而该基不一定是原问题的可行基，只有当人工变量都基，然而该基不一定是原问题的可行基，只有当人工变量都变为非基变量或都为零时，引入人工变量的问题才与原问题变为非基变量或都为零时，引入人工变量的问题才与原问题等价。因此，应通过某种方法把所有的人工变量从基中赶出等价。因此，应通过某种方法把所有的人工变量从基中赶出去才能得到原问题的一个可行基。常用的方法有以下两种：去才能得到原问题的一个可行基。常用的方法有以下两种：（1

14、 1）大）大MM法法 大大MM法实质上是一种罚函数法，它在目标函数中赋予人工法实质上是一种罚函数法，它在目标函数中赋予人工变量一个很大的负系数变量一个很大的负系数(一一M)M)。由于人工变量对目标函数。由于人工变量对目标函数有很大的负影响，单纯形方法的寻优机制会自动将人工变量有很大的负影响，单纯形方法的寻优机制会自动将人工变量赶到基外，从而找到一个原问题的可行基。赶到基外，从而找到一个原问题的可行基。用单纯形表计算时，可直接在目标函数中使用用单纯形表计算时，可直接在目标函数中使用MM参数，参数，第15页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法16重庆大学经济与工商管理

15、学院 肖智通过人的计算和判断进行单纯形迭代。用计算机计算时，由于通过人的计算和判断进行单纯形迭代。用计算机计算时，由于计算机无法直接使用参数计算，计算机无法直接使用参数计算，MM必须赋予一个较大的值，并必须赋予一个较大的值，并视求解的情况对视求解的情况对MM值进行调整。如果给定值进行调整。如果给定MM后，计算所得的最后，计算所得的最优基已不含人工变量，该解即为最优可行解。当给定的优基已不含人工变量，该解即为最优可行解。当给定的MM足够足够大时，最优解中仍含有人工变量，则可判断原问题无可行解。大时，最优解中仍含有人工变量，则可判断原问题无可行解。下面举例说明如何使用大下面举例说明如何使用大MM法

16、。法。例：用大例：用大MM法求解下列线性规划问题：法求解下列线性规划问题：(3.3-6)(3.3-6)第16页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法17重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-43.3-4 cj2 300-M-MbxB CBx1x2x3x4x5x6x3021100016x5-M130-11020 x6-M11000110 j2+2M3+4M0-M00-30Mx305/3011/3-1/3028/3x231/310-1/31/3020/3x6-M2/3001/3-1/3110/3j1+2M/3001+M/3-1-4M

17、/3020-10M/3第17页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法18重庆大学经济与工商管理学院 肖智表表3.3-43.3-4续续 cj2 300-M-MbxB CBx1x2x3x4x5x6x30001-1/21/2-5/21x23010-1/21/2-1/25x121001/2-1/23/25 j0001/2-1/2-M-3/2-M25x3010100-16x2311000110 x402001-1310j-1000-M-3-M30第18页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法19重庆大学经济与工商管理学院 肖智该问题的最优解为：该问

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

19、将线性规划求解过程分为两个阶段。第一阶段只是寻找一个初始可行基，第二阶段再按正常段。第一阶段只是寻找一个初始可行基，第二阶段再按正常方法寻找最优解。方法寻找最优解。第19页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法20重庆大学经济与工商管理学院 肖智第一阶段：在原问题中引入人工变量并找到一个初始基。另构第一阶段：在原问题中引入人工变量并找到一个初始基。另构造一个新的求极小值的目标函数，该目标函数除人工变量的系造一个新的求极小值的目标函数，该目标函数除人工变量的系数为数为1 1以外，其余变量的目标函数系数都为零。求解该线性规以外，其余变量的目标函数系数都为零。求解该线性规

20、划问题，在不退化的前提下，如果得到的最优解值为零，表明划问题，在不退化的前提下，如果得到的最优解值为零，表明所有的人工变量已经不在基中。第一阶段的最优解即是原问题所有的人工变量已经不在基中。第一阶段的最优解即是原问题的一个基可行解。的一个基可行解。第二阶段：将原目标函数换回，以第一阶段得到的可行基为第二阶段：将原目标函数换回，以第一阶段得到的可行基为初始基进行迭代，直到找到最优基为止。在第二阶段的迭代中初始基进行迭代，直到找到最优基为止。在第二阶段的迭代中可以删去所有人工变量，保留它们只会增加不必要的计算。下可以删去所有人工变量，保留它们只会增加不必要的计算。下面举例说明两阶段法求解过程。面举

21、例说明两阶段法求解过程。第20页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法21重庆大学经济与工商管理学院 肖智例：用两阶段法求解下列线性规划问题：例：用两阶段法求解下列线性规划问题：(3.3-7)(3.3-7)第一阶段模型：第一阶段模型：(3.3-8)(3.3-8)第21页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法22重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-53.3-5 cj0 000-1-1bxB CBx1x2x3x4x5x6x3021100016x5-1130-11020 x6-111000110 j240

22、-100-30 x305/3011/3-1/3028/3x201/310-1/31/3020/3x6-12/3001/3-1/3110/3j2/3001/3-4/30-10/3第22页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法23重庆大学经济与工商管理学院 肖智表表3.3-53.3-5续续第二阶段模型：第二阶段模型：(3.3-9)(3.3-9)cj0 000-1-1bxB CBx1x2x3x4x5x6x30001-1/21/2-5/21x20010-1/21/2-1/25x101001/2-1/23/25 j0000-1-10第23页，本讲稿共26页 3.3 3.3 线

23、性规划求解方法线性规划求解方法24重庆大学经济与工商管理学院 肖智具体解题步骤见下表具体解题步骤见下表3.3-63.3-6 cj2 300bxB CBx1x2x3x4x30001-1/21X23010-1/25X121001/25 j0001/225x3010106x23110010 x40200110j-100030第24页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法25重庆大学经济与工商管理学院 肖智通过上述讨论，对于线性规划模型：应用计算机方法、图解法、单纯形法、大M法、两阶段法均可求得相同的最优解:X*=(0，10)T和 最优值:Z*=30第25页，本讲稿共26页 3.3 3.3 线性规划求解方法线性规划求解方法26重庆大学经济与工商管理学院 肖智 THE END 第26页，本讲稿共26页