[经济学]运筹学 第二章 线性规划ppt课件

1、1线性规划线性规划 Linear Programming（LP） 单单 纯纯 形形 方方 法法2线性规划线性规划 Linear Programming（LP） 单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发明的。近年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。原理及算法。3线性规划线性规划 Linear Programming（LP）给定线性规划问题（标准形式）给定线性规划问题

2、（标准形式）max z = c c1 1x x1 1 + c+ c2 2x x2 2 + + c+ + cn nx xn n a a1111x x1 1 + a+ a1212x x2 2 + a+ a1n1nx xn n = = b b1 1 a a2121x x1 1 + a+ a2222x x2 2 + a+ a2n2nx xn n = = b b2 2s.t. s.t. a am1m1x x1 1 + a+ am2m2x x2 2 + a+ amnmnx xn n = = b bm m x xj j 0 0 （j=1j=1，2 n2 n）4线性规划线性规划 Linear Programm

3、ing（LP）一、线性规划问题的解的概念一、线性规划问题的解的概念 可行解可行解 最优解最优解 基基 基解（基本解）基解（基本解） 基可行解基可行解 可行基可行基5线性规划线性规划 Linear Programming（LP） Max Z =3X1+5X2 X1 + X3 = 4s.t. 2X2 +X4 = 12 3X1 + 2X2 +X5 = 18 Xi0 6线性规划线性规划 Linear Programming（LP）X1X2X3X4X5Z004121800640630094-60454001261260-2120184600-64243060272620036*7线性规划线性规划 Lin

4、ear Programming（LP）123456788线性规划线性规划 Linear Programming（LP）二、凸集及其顶点二、凸集及其顶点 凸集凸集 顶点（极点）顶点（极点）凸集凸集凹集凹集9线性规划线性规划 Linear Programming（LP）三、线性规划基本定理三、线性规划基本定理基本定理基本定理 1 线性规划所有可行解组成的集合线性规划所有可行解组成的集合S= X | AX = b，X 0 是是凸集。凸集。基本定理基本定理 2 X是线性规划问题的是线性规划问题的基本可行解的充要条件为是基本可行解的充要条件为是 X 是凸集是凸集S= X | AX = b，X 0 的极点

5、。的极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题， A是秩为是秩为 m 的的 mn 矩阵，矩阵， （i） 若线性规划问题存在若线性规划问题存在可行解，则必存在基可行可行解，则必存在基可行解解 （ii）若线性规划问题存在有界最优解若线性规划问题存在有界最优解，则必存在有，则必存在有界最优基可行解。界最优基可行解。10线性规划线性规划 Linear Programming（LP）单纯形法迭代原理及其思路单纯形法迭代原理及其思路单纯形法的初步讨论单纯形法的初步讨论 Max Z = 50X1+30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0Max Z =

6、 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 X1，X2，X3，X4 0化为化为标准型标准型11线性规划线性规划 Linear Programming（LP）此线性规划问题此线性规划问题转化为了一个含有四个变量的标准形线性转化为了一个含有四个变量的标准形线性规划问题，规划问题，X3，X4为松弛变量。为求解上面的为松弛变量。为求解上面的LP问题，问题，我们要考虑满足约束条件我们要考虑满足约束条件s.t.并使并使 Z 取得取得Max的的X1，X2，X3，X4的值，由此分析如下的值，由此分析如下-12线性规划线性规划 Linear Progra

7、mming（LP）确定初始基可行解：确定初始基可行解： 通过观察可以发现，松弛变量通过观察可以发现，松弛变量X3和和X4对应的等式对应的等式约束条约束条件中的系数矩阵为单位矩阵可以作为初始件中的系数矩阵为单位矩阵可以作为初始可行基可行基矩阵。因此矩阵。因此取：取：X3，X4为基变量；为基变量；X1，X2为非基变量。则可变为为非基变量。则可变为 Max Z =50X1+30X2 s.t. X3 = 120 - - 4X1 - - 3X2 X4= 50 - - 2X1 - - X2 X1，X2，X3，X40 13线性规划线性规划 Linear Programming（LP）典式典式 关于基的关于基

8、的典式典式 1、等式等式约束条件中显含约束条件中显含基可行解基可行解 2、目标函数中不、目标函数中不含含基基变量变量Max Z = 50X1+30X2s.t. 4X1+3X2 +X3 = 120 2X1+ X2 + X4 = 50 X1，X2，X3，X4 0Max Z =50X1+30X2s.t. X3 = 120 - - 4X1 - - 3X2 X4= 50 - - 2X1 - - X2 X1，X2，X3，X4014线性规划线性规划 Linear Programming（LP）在典式中令：在典式中令： X1=X2 =0 0，我们得到一个我们得到一个基本可行解基本可行解 X1 = =（ X1，

9、X2，X3，X4 ）T=（0，0，120，50）T ，其对应的目标函数值其对应的目标函数值 Z1 = 50X1 + 30X2 = 0Max Z =50X1+30X2s.t. X3 = 120 - - 4X1 - - 3X2 X4= 50 - - 2X1 - - X2 X1，X2，X3，X4015线性规划线性规划 Linear Programming（LP）最优性检验：最优性检验： 基本可行解基本可行解 X1是最优解吗？是最优解吗？ 显然不是。应寻找更好的解。显然不是。应寻找更好的解。 从问题的数学角度分析，在典式的目标函数中，从问题的数学角度分析，在典式的目标函数中，非基非基变量变量X1，X2

10、前的系数都为正，表明前的系数都为正，表明目标函数值有增加的可目标函数值有增加的可能。只要将目标函数中能。只要将目标函数中系数为正的某系数为正的某非基变量非基变量与某一基变与某一基变量地位对换。量地位对换。16线性规划线性规划 Linear Programming（LP）换基迭代：换基迭代： 进行进行换基就是要从非基变量中选一个变量换基就是要从非基变量中选一个变量入基入基，再从，再从基变量中选一个变量基变量中选一个变量出基出基。并且换基后仍需满足：。并且换基后仍需满足：1 1、新的解仍是基本可行解；新的解仍是基本可行解；2 2、目标函数值将得到改善。目标函数值将得到改善。17线性规划线性规划 L

11、inear Programming（LP）选择入基变量：选择入基变量： 由于在目标函数由于在目标函数Z1=50X1+30X2 中中X1，X2的系数都为正，哪一个入的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的们希望目标值增加得越快越好，因此系数最大的X1入基。入基。选择出基变量：选择出基变量： X1入基后，其值从零增加并由于入基后，其值从零增加并由于约束条件的原因会引起其他变量的约束条件的原因会引起其他变量的变化。由变化。由典式典式以及变量必须取正值的条件，我们

12、可以得到下列不等以及变量必须取正值的条件，我们可以得到下列不等式关系：式关系： X3 = 120 - 4X1- 3X2 0 X4= 50 - 2X1- X2 018线性规划线性规划 Linear Programming（LP）因为迭代后因为迭代后X2仍为仍为非基变量非基变量（仍会令其取值为零仍会令其取值为零），则上式可简化为：，则上式可简化为： 120 - 4X1 0 50 - 2X1 0 由此可以看出，虽然我们希望由此可以看出，虽然我们希望X1入基后取正值，且取值越大目标值增加入基后取正值，且取值越大目标值增加越大，但是，越大，但是，X1又得受到又得受到约束。约束。显然，只有显然，只有取取X

13、1 =min（120/4，50/2）=25时，才能使上述不等式成立时，才能使上述不等式成立并且恰使并且恰使基变量基变量X4变为零，这正好满足非基变量必须取变为零，这正好满足非基变量必须取值值零的条件，所零的条件，所以可以可令令X4 出基，出基，方程变为：方程变为： 4X1+ X3 =120 - 3X2 2X1 = 50 - X2 - X4化简后得化简后得新的新的典式典式方程方程 ： X3 = 20 - X2 + 2X4 X1 = 25 -0.5X2 -0.5X419线性规划线性规划 Linear Programming（LP）代入目标函数可得：代入目标函数可得： Z2 =1250+5X2-25

14、X4 令令非基变量非基变量X2 =X4 = 0，即可得一个新的，即可得一个新的基本可行解基本可行解 X2 =（ 25，0，20，0）T ，其对应的目标函数值，其对应的目标函数值Z2 =1250，并完成了第一次并完成了第一次迭代。迭代。由于由于目标函数目标函数 Z2 =1250+5X2-25X4中中X2的系数仍为正，该的系数仍为正，该解解X2仍不是最优解。重复上述仍不是最优解。重复上述迭代过程得到：迭代过程得到：X2入基，入基，X3出基，则新的出基，则新的典式典式方程变为：方程变为： X1 = 15 +0.5X3 - 1.5X4 X2 =20 - X3 + 2X4 Z3 =1350 -5X3 -

15、 15X420线性规划线性规划 Linear Programming（LP）第三个第三个基本可行解基本可行解 X3 =（ 15，20，0，0）T，其对应，其对应的目标函数值的目标函数值Z3=1350 。此时松弛变量都是此时松弛变量都是非基变量非基变量（取值为零取值为零），这表明资，这表明资源已用源已用 尽；并且目标函数值尽；并且目标函数值Z3 =1350 -5X3 - 15X4中中非非基变量基变量X3，X4的系数全为负值，说明目标函数已无法的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。进一步改善，因此该解已是最优解。21线性规划线性规划 Linear Programming

16、（LP）单纯形法小结：单纯形法小结： 单纯形法是这样一种单纯形法是这样一种迭代算法迭代算法如下图如下图X1Z1保持保持单调增单调增保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持单调增单调增保持保持单调增单调增保持保持单调增单调增X2X3.X XkZ2Z3.Zk当当Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行解基本可行解Xk 即是线性规划问题的最优解，即是线性规划问题的最优解，迭代结束。迭代结束。22线性规划线性规划 Linear Programming（LP）单纯形表单纯形表对于给定的线性规划问题：对于

17、给定的线性规划问题：max Z = c c1 1x x1 1 + c+ c2 2x x2 2 + + c+ + cn nx xn n a a1111x x1 1 + a+ a1212x x2 2 + + a+ + a1n1nx xn n b b1 1 a a2121x x1 1 + a+ a2222x x2 2 + + a+ + a2n2nx xn n b b2 2s.t. s.t. a am1m1x x1 1 + a+ am2m2x x2 2 + + a+ + amnmnx xn n b bm m x xj j 0 0 （j=1j=1，2 n2 n）对此问题添加对此问题添加m个松弛变量后，可

18、得下面线性规划问题并且是个松弛变量后，可得下面线性规划问题并且是典式的形式。典式的形式。23线性规划线性规划 Linear Programming（LP）线性规划的典式线性规划的典式max Z = c c1 1x x1 1 + c+ c2 2x x2 2 + + c+ + cn nx xn n a a1111x x1 1 + a+ a1212x x2 2 + a+ a1n1nx xn n + x+ xn+1 n+1 = b= b1 1 a a2121x x1 1 + a+ a2222x x2 2 + a+ a2n2nx xn n + + x xn+2 n+2 = b= b2 2s.t. s.t

19、. a am1m1x x1 1 + a+ am2m2x x2 2 + a+ amnmnx xn n + + x xn+m n+m = b= bm m x xj j 0 0 （j=1j=1，2 n2 n，n+1n+1，n+2n+2，n+mn+m）24线性规划线性规划 Linear Programming（LP）将上面将上面典式中各变量及系数填写在一张表格中就形成下面的典式中各变量及系数填写在一张表格中就形成下面的单纯形表单纯形表cj c1 c2 cn cn+1 cn+mCB基解 x1 x2 xn xn+1 xn+10000 xn+1xn+2xn+m b1 b2 bm a11 a12 a1n 1

20、a21 a22 a2n am1 am2 amn 112mj = cj zj c1 c2 cn 0 0j = cj zj 1 2 n n+1 n+m 25线性规划线性规划 Linear Programming（LP）上面上面的的单纯形表还可以表示成矩阵的形式单纯形表还可以表示成矩阵的形式基基解解 X XS XSb A I j C 0基基解解 XB XN XS XSb B N I j CB CN 026线性规划线性规划 Linear Programming（LP）由单纯形表进行由单纯形表进行迭代步骤：迭代步骤：1. 选择选择 Xj 入基：当入基：当 j 行中行中 c cj j= max c= ma

21、x ci icci i 00 2. 选择选择 Xi 出基：当出基：当 i i = min(b= min(bi i/a/aijij)a)aij ij 003.3. 换基换基迭代：当确定了迭代：当确定了入基变量入基变量 Xj 、出基变量、出基变量 Xi 后，以后，以 aij 作为主元对作为主元对单纯形表进行初等行变换（取单纯形表进行初等行变换（取主主运算），运算），即将即将 aij 所在列除采用初等行变换所在列除采用初等行变换将将 aii 变换为变换为1外的其外的其余元素都余元素都变换为变换为 0 0。注意这种。注意这种变换只能采用初等行变换变换只能采用初等行变换!27线性规划线性规划 Linea

22、r Programming（LP）最优解检验：最优解检验： 1、 当迭代进行至某一步时，当迭代进行至某一步时， j 行中所有行中所有检验数均小于等于检验数均小于等于零，则零，则迭代结束。迭代结束。表中当前表中当前所指所指基本可行解即为基本可行解即为最优解。最优解。 2、 当迭代进行至某一步时，当迭代进行至某一步时， j 行中所有行中所有检验数均小于等于检验数均小于等于零，且此时至少有一个零，且此时至少有一个非基变量所对应的检验数非基变量所对应的检验数rk等于零，则原线性等于零，则原线性规划问题有无穷多个规划问题有无穷多个最优解。最优解。 3、 当迭代进行至某一步时，当迭代进行至某一步时， j

23、行中至少有一个行中至少有一个检验数检验数 rk 大于零，且该检验数对应的大于零，且该检验数对应的列中列中a1k ，a2k ， amk ，均均小于等于小于等于零，零，则原线性规划问题则原线性规划问题最优解无界（最优解无界（ max Z +）。）。28线性规划线性规划 Linear Programming（LP）其中其中 b 0 ，I 是是 mm 单位单位矩阵。矩阵。对上面对上面（I 式式）经过迭代，经过迭代，并设最终的最优基矩阵为并设最终的最优基矩阵为B,不妨设不妨设B 为为A 的首的首m 列，则将（列，则将（I 式式）改写后有）改写后有单纯形方法的矩阵描述：单纯形方法的矩阵描述：设线性规划问题

24、设线性规划问题 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式式） X 0 X ，XS 029线性规划线性规划 Linear Programming（LP）max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0 max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0 B 式中式中最优最优目标函数值目标函数值Z*= CB B

25、-1 ，检验数，检验数 CN - CB B -1 0 ， - CB B -1 0单纯形方法迭代单纯形方法迭代（I 式）式）（B 式式）30线性规划线性规划 Linear Programming（LP）单纯形方法的矩阵描述：单纯形方法的矩阵描述：基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1对应对应I 式式的的单纯形表单纯形表 I 表表对应对应B 式式的的单纯形表单纯形表 B 表表迭代31线性规划线性规划 Linear Programming（LP）单纯形

26、表计算步骤举例单纯形表计算步骤举例给定线性规划问题给定线性规划问题max z = 50X1 + 30X2s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 032线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4 X31204310X4502101检验数检验数 j 5030002120/450/2X111/201/2250201- 2050- 2520/125211X2150-

27、 1/23/210- 5- 1533线性规划线性规划 Linear Programming（LP）人工变量法：人工变量法： 当一般线性规划问题标准化之后，我们或可得到一个显当一般线性规划问题标准化之后，我们或可得到一个显然的然的基本可行解（如基本可行解（如松弛变量作为松弛变量作为基变量的一个基变量的一个初始初始基本可基本可行解），这样我们就可以马上进入行解），这样我们就可以马上进入单纯形表的运算步骤。然单纯形表的运算步骤。然而，并非所有而，并非所有问题标准化之后我们都可得到一个显然的问题标准化之后我们都可得到一个显然的初始初始基本可行解，基本可行解，这时就需要我们首先确定出一个这时就需要我们首

28、先确定出一个基本可行解作基本可行解作为为初始初始基本可行解。通常采用的是人工变量法来确定这样的基本可行解。通常采用的是人工变量法来确定这样的初始初始基本可行解。这种情况下一般有两种方法：基本可行解。这种情况下一般有两种方法： 1 1、大、大M M法（罚因子法）法（罚因子法） 2 2、两阶段法、两阶段法34线性规划线性规划 Linear Programming（LP）max z = - 3X1 + X3 x1 + x2 + x3 4 - 2x1 + x2 x3 1 3x2 + x3 = 9 x1 ，x2 ，x3 0LPM max z = - 3x max z = - 3x1 + x3 + 0 x

29、4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 035线性规划线性规划 Linear Programming（LP）大大 M 法求解线性规划问题的具体方法与前面的一法求解线性规划问题的具体方法与前面的一般单纯形法相同，就是将般单纯形法相同，就是将M当作一个充分大的数来处当作一个充分大的数来处理。理。36线性规划线性规划 Linear Programming（LP）1、大、大 M 法法LPM max z = - 3x

30、1 + x3 + 0 x4 + 0 x5 Mx6 Mx7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + + x6 = 1 3x2 + x3 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j37线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-3-2M

31、4M10-M0038线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7 X4411110004X61-21-10-1101X7903100013检验数检验数 j-3-2M4M10-M00基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-10X21-21-10-110X7660403-31检验数检验数 j-3+6M01+4M03M-4M039线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X7660403

32、-311检验数检验数 j-3+6M01+4M03M-4M0基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00301.5-1.5-M0.5-M40线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2-X23011/30001/39X11102/301/2-1/21/63/2检验数检验数 j00301.5-1.5-M0.5-M基基XB解解B-1bX1X2X3X4X5X6X7 X400

33、001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4检验数检验数 j-9/2000-3/43/4-M-1/4-M41线性规划线性规划 Linear Programming（LP）采用大采用大 M 法求解线性规划问题时可能出现的几种情况：法求解线性规划问题时可能出现的几种情况：1、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解时，基变量得到最优解时，基变量不含不含任何任何人工变量，则所得到的最优解就是原问题的最优解；人工变量，则所得到的最优解就是原问题的最优解；2、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解

34、时，基变量至少得到最优解时，基变量至少含有含有一个人工变量且一个人工变量且非零非零，则原问题无可行解；，则原问题无可行解；3、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解时，基变量至少得到最优解时，基变量至少含有含有一个人工变量且人工变量都一个人工变量且人工变量都为零为零，则通过变换得到原问题最优，则通过变换得到原问题最优解；解；42线性规划线性规划 Linear Programming（LP）2、两阶段法、两阶段法I 阶段问题阶段问题 max z = x6 x7 x1 + x2 + x3 + x4 = 4 - 2x1 + x2 x3 - x5 + x6 = 1 3x2 + x3

35、 +x7 = 9 x1 ，x2 ，x3 ， x4 ， x5 ， x6 ， x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j43线性规划线性规划 Linear Programming（LP）第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-2400-10044线性规划线性规划 Linear Programming（LP）第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X4411110004

36、X61-21-10-1101X7903100013检验数检验数 j-2400-100基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-10X21-21-10-110X7660403-31检验数检验数 j60403-4045线性规划线性规划 Linear Programming（LP）第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X7660403-311检验数检验数 j60403-40基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00000-1-146线性规划线性规划 Linear Programming（LP）第第II 阶段阶段基基XB解解B-