whut运筹学-3_单纯形法

1、1 线性规划的单纯形法线性规划的单纯形法 (Simplex Algorithm for LP)1 单纯形法的基本思路单纯形法的基本思路基本思想：基本思想：从某一初始基可行解出发，判别它是否为最优从某一初始基可行解出发，判别它是否为最优 解，如果不是，寻找一个更好的基可行解，再解，如果不是，寻找一个更好的基可行解，再 进行判别。以此类推，直到找到最优解，或者进行判别。以此类推，直到找到最优解，或者 判定该问题无界。判定该问题无界。 2 线性规划的单纯形法线性规划的单纯形法例例 1 求下列线性规划问题的解求下列线性规划问题的解 0,5 8 5.05.1220 5.12 448 6 8s.t.203

2、060max765432172632153214321321xxxxxxxxxxxxxxxxxxxxxxxxz3线性规划的单纯形法线性规划的单纯形法寻找一个初始基可行解寻找一个初始基可行解 解：解：约束方程的系数矩阵为约束方程的系数矩阵为由于由于P4 , P5 ，P6，P7 线性无关线性无关, 则则 B=(P4 , P5 ，P6，P7 ) 是该问题的一个基。是该问题的一个基。相应的基变量为相应的基变量为 x4 , x5 ，x6，x7，得到初始基可行解为，得到初始基可行解为X (0) =(0, 0, 0, 48, 20, 8, 5)T基变量集基变量集=x4 , x5 ，x6，x7 1000010

3、01005 . 05 . 1200105 . 1240001168) , , , , , ,(7654321PPPPPPPA4线性规划的单纯形法线性规划的单纯形法321203060 xxxz x1 或或 x2 或或 x3 z 当前基可行解不是最优解当前基可行解不是最优解n确定入基变量确定入基变量x1 增加一个单位，增加一个单位， z 将增加将增加 60个单位个单位x2 增加一个单位，增加一个单位， z 将增加将增加 30个单位个单位x3 增加一个单位，增加一个单位， z 将增加将增加 20个单位个单位x1 为入为入基变量基变量如果当前目标函数中含有正系如果当前目标函数中含有正系数的非基变量，则

4、当前基可行数的非基变量，则当前基可行解不是最优的解不是最优的 选取当前目标选取当前目标函数中正系数函数中正系数最大的非基变最大的非基变量为入基变量量为入基变量n当前基可行解是最优解？当前基可行解是最优解？5线性规划的单纯形法线性规划的单纯形法x6为离基变量为离基变量 含有正系数入基变量的含有正系数入基变量的 约束约束条件条件的右端项的右端项 入基变量的正系数入基变量的正系数n确定离基变量确定离基变量x1 =min6,5,4 =4 x6 =0选取与最小选取与最小 比值比值 相应的相应的基变量为离基变量基变量为离基变量基变量集基变量集=x4 , x5 ，x1，x7 0 5 4 28 0 2 8 5

5、420 0 420 6848 08 48 7116115114 xxxxxxxxxx6线性规划的单纯形法线性规划的单纯形法X (1) =(4, 0, 0, 16, 4, 0, 5)Tn寻找新的基可行解寻找新的基可行解 5 8 5 . 05 . 1220 5 . 12 448 6 8 20306072632153214321321xxxxxxxxxxxxxxzxxx 5 4 5 . 0 25. 075. 0 4 2 5 . 0 16 4 30 5 15 2407263216532643632xxxxxxxxxxxxxzxxx单纯形法单纯形法 标准型标准型主元素主元素7线性规划的单纯形法线性规划的

6、单纯形法x3 为入基变量为入基变量n确定入基变量确定入基变量n确定离基变量确定离基变量825. 04,5 . 04min3 xx5为离基变量为离基变量基变量集基变量集=x4 , x3 ，x1，x7n当前基可行解是最优解？当前基可行解是最优解？当前基可行解不是最优解当前基可行解不是最优解8线性规划的单纯形法线性规划的单纯形法X (2) =(2, 0, 8, 24, 0, 0, 5)Tn寻找新的基可行解寻找新的基可行解 5 4 5 . 0 25. 075. 0 4 2 5 . 0 16 4 30 5 15 2407263216532643632xxxxxxxxxxxxxzxxx 5 2 5 . 1

7、 5 . 0 25. 1 8 4 2 2 24 8 2 2 10 10 5 28072652165326542652xxxxxxxxxxxxxxzxxx基变量集基变量集=x4 , x5 ，x1，x7基变量集基变量集=x4 , x3 ，x1，x79线性规划的单纯形法线性规划的单纯形法n当前基可行解是最优解？当前基可行解是最优解？当前基可行解是最优解当前基可行解是最优解最优解：最优解：X * =(2, 0, 8, 24, 0, 0, 5)T最优值：最优值：z*=28010人造基法人造基法线性规划的单纯形法线性规划的单纯形法(1) (1) 直接从直接从 A A 中观察到一个初始可行基中观察到一个初始

8、可行基( (单位阵单位阵) )； 1.1 确定初始基可行解确定初始基可行解( (2) 2) 若在化标准型前，约束条件都是若在化标准型前，约束条件都是 “” 的形式。利用化标准型的的形式。利用化标准型的方法，将每一个约束条件左边都加上一个松弛变量，这方法，将每一个约束条件左边都加上一个松弛变量，这 m m 个松弛变量就成个松弛变量就成为基变量，而对应的系数列向量组成的为基变量，而对应的系数列向量组成的 m m 阶单位矩阵就是一个初始可行基。阶单位矩阵就是一个初始可行基。(3) (3) 若在化标准若在化标准型型前，约束前，约束条件都是条件都是 “” 的的形式形式和等式的情况。对不等和等式的情况。对

9、不等式约束，其左端减去一个非负的剩余变量后，再加上一个非负的式约束，其左端减去一个非负的剩余变量后，再加上一个非负的人工变量人工变量，对于等式约束，直接在其左端加上对于等式约束，直接在其左端加上人工变量人工变量。则这些人工变量就成为基变。则这些人工变量就成为基变量，对应的列向量组成的单位矩阵就是一个初始可行基。量，对应的列向量组成的单位矩阵就是一个初始可行基。 11线性规划的单纯形法线性规划的单纯形法例例 2 设某线性规划问题的约束条件为：设某线性规划问题的约束条件为： 0,20 303 250423321321321321 xxxxxxxxxxxx).7 , 2 , 1(020 30 3 2

10、50 4237321653214321 jxxxxxxxxxxxxxxj12线性规划的单纯形法线性规划的单纯形法 ), 2 , 1( 0 s.t.11221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmm,mmnnm,mnnm,mnjjjxcz1 max经过整理后，不妨设线性规划模型为：经过整理后，不妨设线性规划模型为： 初始基可行解为：初始基可行解为： X(0)=(b1, b2, . . . , bm, 0, 0, , 0)T基变量集：基变量集： x1, x2, . . . , xm13线性规划的单纯形法线性规划的单纯形法1.2 最优性检验最优性检验 设经过若干次迭

11、代后，得设经过若干次迭代后，得),2, 1(1mixabxjnmjijii 则目标函数变为则目标函数变为jminmjmiijijiixaccbcZ 111)( 则则z z0 0j jnmjjxzz 10 检验数检验数14线性规划的单纯形法线性规划的单纯形法若关于非基变量的所有检验数若关于非基变量的所有检验数 则基可行解则基可行解 为最优解为最优解; ;特别地，若存在某个非基变量的检验数为特别地，若存在某个非基变量的检验数为0 0，则有无穷多最优，则有无穷多最优解。解。), 1( 0nmjj Tmbbbx)0 , 0 ,(21)0( 15线性规划的单纯形法线性规划的单纯形法1.3 基变换基变换(

12、1) (1) 入基（换入）变量的确定入基（换入）变量的确定记记 . 0 max jjjtm xm+t 为入基变量为入基变量 否则，进行单纯形法的下一步否则，进行单纯形法的下一步-基变换基变换16线性规划的单纯形法线性规划的单纯形法(2) (2) 离基（换出）变量的确定离基（换出）变量的确定（最小比值规则）（最小比值规则）), 2 , 1(1mixabxjnmjijii xm+1=.=xm+t-1=xm+t+1=xn=0),2, 1( 0 ,mixabxtmtmiii 0min. ,tmitmiiitmlltmaababx xl 为为离基变量离基变量 17线性规划的单纯形法线性规划的单纯形法1.

13、4 寻找新的基可行解寻找新的基可行解( (迭代迭代/ /旋转运算旋转运算) ), 2 , 1(1mixabxjnmjijii ,1,1,1, 1, 11, 111111 mnmtmmmmlnltmlmlntmmntmmm lbaaabaaabaaabxxxxxx初等初等变换变换 18线性规划的单纯形法线性规划的单纯形法 ,1,1,1, 1,1, 1, 1, 1,1,1, 1, 1 11011101 tmmtmllmtmmtmlnlnmtmmtmlmlmmtmltmmtmlltmlnltmlmltmltmtmlltmtmlnlntmtmlmlmtmltmntmmmlaabbaaaaaaaaaaa

14、baaaaaaabbaaaaaaaaaabxxxxxx19线性规划的单纯形法线性规划的单纯形法新的基可行解为：新的基可行解为：TtmlltmmtmllmtmltmllltmltmllltmtmllabaabbaabbaabbaabbX 0 , 0, 0, 0, , , 0, 1,1, 1,1, 1,1)1(第第 l 个分量个分量第第 m+t 个分量个分量20线性规划的单纯形法线性规划的单纯形法2 单纯形表单纯形表 (Simplex Tableau) XB x1 x2 xm xm+1 xn b x1 1 0 0 a1, m+1 a1, n b1 x2 0 1 0 a2, m+1 a2, n b2

15、 . xm 0 0 1 am, m+1 an, n bm -z 0 0 0 mimiimacc11,1 miniinacc1, miiibc1 检验数行检验数行基变量集：基变量集： x1, x2, . . . , xmC CB Bc c1 1c c2 2c cm mR Rr r1 1r r2 2r rm mc c1 1 c c2 2 c cm m c cm+1m+1 c cn n右端项右端项基变量基变量基变量的价值系数基变量的价值系数变量的价值系数变量的价值系数比值比值21线性规划的单纯形法线性规划的单纯形法例例 2 用单纯形法求解例用单纯形法求解例1问题。问题。 XB x1 x2 x3 x4

16、 x5 x6 x7 b x4 8 6 1 1 0 0 0 48 x5 4 2 1.5 0 1 0 0 20 x6 2 1.5 0.5 0 0 1 0 8 x7 0 1 0 0 0 0 1 5 -z 60 30 20 0 0 0 0 0 0,5 8 5.05.1220 5.12 448 6 8s.t.203060max765432172632153214321321xxxxxxxxxxxxxxxxxxxxxxxxz解：解：首先建立初首先建立初始单纯形法表，始单纯形法表，求解过程如下。求解过程如下。主主元元素素 R 6 5 4 -C CB B0 00 000 022线性规划的单纯形法线性规划的单纯

17、形法x*=(2, 0, 8，24，0，0，5)T z*=280 XB x1 x2 x3 x4 x5 x6 x7 b R x4 0 -2 0 1 2 -8 0 24 x3 0 -2 1 0 2 -4 0 8 x1 1 1.25 0 0 -0.5 1.5 0 2 x7 0 1 0 0 0 0 1 5 -z 0 -5 0 0 -10 -10 0 -280 XB x1 x2 x3 x4 x5 x6 x7 b x4 0 0 -1 1 0 -4 0 16 x5 0 -1 0.5 0 1 -2 0 4 x1 1 0.75 0.25 0 0 0.5 0 4 x7 0 1 0 0 0 0 1 5 -z 0 -1

18、5 5 0 0 - 30 0 - 240 R - 8 16 -C CB B0 00 0600 0C CB B0 02020600 023线性规划的单纯形法线性规划的单纯形法例例 3 用单纯形法求解下面的线性规划问题。用单纯形法求解下面的线性规划问题。 0,12 4 16 482 s.t.32max21212121xxxxxxxxz解解: 把原问题化为标准型：把原问题化为标准型： 0,12 4 16 48 2 s.t.32max54321524132121xxxxxxxxxxxxxxz24线性规划的单纯形法线性规划的单纯形法用单纯形法求解如下用单纯形法求解如下: XB x1 x2 x3 x4 x

19、5 b x3 1 2 1 0 0 8 x4 4 0 0 1 0 16 x5 0 4 0 0 1 12 -z 2 3 0 0 0 0 XB x1 x2 x3 x4 x5 b x3 1 0 1 0 -0.5 2 x4 4 0 0 1 0 16 x2 0 1 0 0 1/4 3 -z 2 0 0 0 -3/4 -9 R 4 - 3 R 2 4 - C CB B0 00 00C CB B0 00 03C 2 3 C 2 3 0 0 0C 2 3 C 2 3 0 0 025线性规划的单纯形线性规划的单纯形 XB x1 x2 x3 x4 x5 b x1 1 0 1 0 -0.5 2 x4 0 0 -4 1

20、 2 8 x2 0 1 0 0 1/4 3 -z 0 0 -2 0 1/4 -13 XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4 x5 0 0 -2 0.5 1 4 x2 0 1 0.5 -1/8 0 2 -z 0 0 -3/2 -1/8 0 -14最优解：最优解： x*=(4, 2)T,最优值：最优值： z*=14 R - 4 12 C CB B2 20 03 3C CB B2 20 03 3C 2 3 C 2 3 0 0 0C 2 3 C 2 3 0 0 026线性规划的单纯形线性规划的单纯形基可行解基可行解与可行域与可行域顶点的对顶点的对应关系应关系 O

21、(0, 0) A (0, 3) B (2, 3) C (4, 2)(0, 0) Ox1 x2 D (4, 0)(0, 3) AB (2,3) C (4, 2) x1+2x2=84x2=124x1=162x1+3x2=1427线性规划的单纯形法线性规划的单纯形法 3. 3. 用单纯形法判别线性规划的解的情形用单纯形法判别线性规划的解的情形 唯一最优解唯一最优解如果单纯形表中所有非基变量的检验数均为负数，则线性规划有如果单纯形表中所有非基变量的检验数均为负数，则线性规划有唯一最优解唯一最优解. 无穷多最优解无穷多最优解如果单纯形表中所有非基变量的检验数均为非正数，且存在一个如果单纯形表中所有非基变

22、量的检验数均为非正数，且存在一个非基变量的检验数为零，则线性规划有无穷多最优解非基变量的检验数为零，则线性规划有无穷多最优解. 无界解无界解如果单纯形表中存在一个非基变量的检验数为正数，但在其他行如果单纯形表中存在一个非基变量的检验数为正数，但在其他行中该非基变量的系数均为非正数，则线性规划有无界解中该非基变量的系数均为非正数，则线性规划有无界解.28线性规划的单纯形法线性规划的单纯形法例例4: 用单纯形法求解下面的问题。用单纯形法求解下面的问题。解解: 把原问题化为标准型：把原问题化为标准型： 0,12 4 16 482 s.t.2max21212121xxxxxxxxz 0,12 4 16

23、 48 2 s.t.2max54321524132121xxxxxxxxxxxxxxz29线性规划的单纯形法线性规划的单纯形法用单纯形法求解如下用单纯形法求解如下: XB x1 x2 x3 x4 x5 b x3 1 2 1 0 0 8 x4 4 0 0 1 0 16 x5 0 4 0 0 1 12 -z 1 2 0 0 0 0 XB x1 x2 x3 x4 x5 b x3 1 0 1 0 -0.5 2 x4 4 0 0 1 0 16 x2 0 1 0 0 1/4 3 -z 1 0 0 0 -1/2 -6 R 4 - 3 R 2 4 - C CB B0 00 00 0C CB B0 00 02 230线性规划的单纯形线性规划的单纯形 XB x1 x2 x3 x4 x5 b x1 1 0 1 0 -0.5 2 x4 0 0 -4 1 2 8 x2 0 1 0 0 1/4 3 -z 0 0 -1 0 0 -8 XB x1 x2 x3 x4 x5 b R x1 1 0 0 1/4 0 4 x5 0 0 -2 0.5 1 4 x2 0 1 0.5 -1/8 0 2 -z 0 0 -1 0 0 -8该问题有该问题有 无穷多无穷多最优解最优解最优解：最优解： x*=(2, 3)T,最优值：最