运筹学2线性-3

1、 2022-6-412022-6-422022-6-43 1. 1. 单纯形方法的推导单纯形方法的推导2. 2. 单纯形计算表单纯形计算表3. 3. 单纯形方法的基本定理单纯形方法的基本定理4. 4. 如何寻找初始可行解如何寻找初始可行解2022-6-442022-6-452.4.1. 2.4.1. 单纯形方法推导单纯形方法推导单纯形方法的基本思单纯形方法的基本思想想 从可行域的一个基本可从可行域的一个基本可行解行解( (极点极点) )出发，判别它是出发，判别它是否已是最优解，如果不是，否已是最优解，如果不是，寻找下一个基本可行解，并寻找下一个基本可行解，并使目标函数得到改进，如此使目标函数得

2、到改进，如此迭代下去，直到找到最优解迭代下去，直到找到最优解或判定问题无界为止。或判定问题无界为止。2022-6-46 求解线性规划：求解线性规划：max z = 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1, x2 02022-6-47 max z = 50 x1+ 30 x2 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 0 选选 x3 , x4 为基变量为基变量转换为典则形式转换为典则形式 ： max z = 50 x1 + 30 x2 s.t.x3 = 12

3、0 - 4x1 - 3x2 x4 = 50 - 2x1 - x2 x1 , x2 , x3 , x4 0将原问题转化为将原问题转化为标准型模型标准型模型：2022-6-48（用非基变量表示（用非基变量表示基变量和目标函数基变量和目标函数的形式称为关于基的形式称为关于基的典则形式）的典则形式）寻找初始可行解：寻找初始可行解：令非基变量为零，令非基变量为零， 得到：得到： x(1) = (0, 0, 120, 50) ， z(1) = 0最优性检验最优性检验 :该解是最优解吗？该解是最优解吗？第一次换基迭代第一次换基迭代 选选x1入基（系数为正有利于入基（系数为正有利于z增加、最大增加增加、最大增

4、加原则）。得到下列不等式关系原则）。得到下列不等式关系:2022-6-49 x3 = 120 - 4x1 - 3x2 0 x4 = 50 - 2x1 - x2 0 简化为：简化为：120 - 4x1 0 50 - 2x1 0 选选 x1= min(120/4, 50/2) = 25（最小比值原则或（最小比值原则或原则）原则）, 才使上述不等式成立，并迫使才使上述不等式成立，并迫使 x4 为零；为零；因此需令因此需令 x4 出基。出基。2022-6-410新的典则方程变为新的典则方程变为:4x1 + x3 = 120 - 3x22x1 = 50 - x2 - x4化简后：化简后： z(2) =

5、1250 + 5x2 - 25x4 x1 = 25 - 0.5x2 - 0.5x4 x3 = 20 - x2 + 2x4第二个基本可行解第二个基本可行解 (25, 0, 20, 0) , z(2)=12502022-6-411第二次换基迭代第二次换基迭代 选选 x2入基。得到下列不等式关系入基。得到下列不等式关系:x1 = 25 - 0.5x2 - 0.5x4 0 x3 = 20 - x2 + 2x4 0 简化为：简化为：25 - 0.5x2 0 20 - x2 0 选选 x2 = min(25/0.5, 20/1) = 20 时才能使不等时才能使不等式成立，并使式成立，并使 x3为零，令为零

6、，令 x3 出基。出基。2022-6-412换基后的典则形式变为：换基后的典则形式变为：z(3) = 1350 - 5x3 - 15x4x1 = 15 + 0.5x3 - 1.5x4x2 = 20 - x3 + 2x4 第三个解为第三个解为(15, 20, 0, 0) ，z(3) = 1350； 此时，此时，目标函数表达式中非基变量的目标函数表达式中非基变量的系数系数都为负都为负，目标函数无法继续改进，为，目标函数无法继续改进，为最优解最优解。2022-6-413考虑标准形式的线性规划问题：考虑标准形式的线性规划问题：Max z = c1x1 + c2x2 + + cnxn s.t. a11

7、x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 02022-6-4 x1 c1 b1 a11 a12.a1n x2 c2 b2 a21 a22.a2nx = . C= . b= . A= . . . . . . . . . xn cn bm am1 am2.amn 14 这里，矩阵这里，矩阵A表示为：表示为： A = ( p1 ，p2 ，pn ) ， 其中其中 pj = ( a1j ，a2j ，amj )T Rm。若。

8、若找到一个可行基，不妨设找到一个可行基，不妨设 B = ( p1 ，p2 ，pm ) ， 则则m个基变量为个基变量为 x1 , x2 , , xm，n-m个非个非基变量为基变量为 xm+1 ，xm+2 ，xn 。通过运算，。通过运算，所有的基变量都可以用非基变量来表示所有的基变量都可以用非基变量来表示：2022-6-415 x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn） (1 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它们代入目标函数，得把它们代入目标函数，得 z

9、 = z+ m+1xm+1+ m+2xm+2+ nxn (2 ) 其中其中 j=cj-（c1a1j + c2a2j + + cm amj） 我们把由非基变量表示的目标函数形式称为我们把由非基变量表示的目标函数形式称为基基B相应的目标函数典式相应的目标函数典式。2022-6-416单纯形法的基本步骤可描述如下：单纯形法的基本步骤可描述如下： （1）寻找一个初始的可行基和相应基本寻找一个初始的可行基和相应基本可行解（极点）。确定基变量、非基变量可行解（极点）。确定基变量、非基变量以及基变量、非基变量（全部等于以及基变量、非基变量（全部等于0 0）和目）和目标函数的值，并标函数的值，并将目标函数和基

10、变量分别将目标函数和基变量分别用非基变量表示用非基变量表示；2022-6-417 max z = 50 x1+ 30 x2 s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 0 选选 x3 , x4 为基变量为基变量转换为典则形式转换为典则形式 ： max z = 50 x1 + 30 x2 s.t.x3 = 120 - 4x1 - 3x2 x4 = 50 - 2x1 - x2 x1 , x2 , x3 , x4 0将原问题转化为将原问题转化为标准型模型标准型模型：2022-6-418（用非基变量表示（用非基变量表示基

11、变量和目标函数基变量和目标函数的形式称为关于基的形式称为关于基的典则形式）的典则形式）例例 （2）在用非基变量表示的目标函数表达式（在用非基变量表示的目标函数表达式（2）中，我们称中，我们称非基变量非基变量xj的系数为检验数记为的系数为检验数记为 j 。若。若 j 0，那么相应的非基变量，那么相应的非基变量xj，它的值从当前值，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的开始增加时，目标函数值随之增加。这个选定的非基变量非基变量xj称为称为“进基变量进基变量”，转（，转（3）。如果任）。如果任何一个非基变量的值增加都不能使目标函数值增何一个非基变量的值增加都不能使目标函数值增加，

12、即加，即所有所有 j 非正，则当前的基本可行解就是最非正，则当前的基本可行解就是最优解优解，计算结束；，计算结束；2022-6-419寻找初始可行解：寻找初始可行解：令非基变量为零，令非基变量为零， 得到：得到： x(1) = (0, 0, 120, 50) ， z(1) = 0最优性检验最优性检验 :该解是最优解吗？该解是最优解吗？第一次换基迭代第一次换基迭代选选 x1入基（系数大有利于入基（系数大有利于z增加）。增加）。2022-6-420例例2022-6-421问题：问题：选择非基变量进基的原则？选择非基变量进基的原则？1.任意一个任意一个2.任意一个正检验数对应的非基变量任意一个正检验

13、数对应的非基变量3.最大正检验数对应的非基变量最大正检验数对应的非基变量4.排在最前面的正检验数对应的非基变量排在最前面的正检验数对应的非基变量X （3）在用非基变量表示的基变量的表达式（在用非基变量表示的基变量的表达式（1）中，观察进基变量增加时各基变量变化情况，确中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到定基变量的值在进基变量增加过程中首先减少到0的变量的变量xr ，满足，满足， =min bi /aij aij 0 = br /arj这个基变量这个基变量xr称为称为“出基变量出基变量”。当进基变量的值。当进基变量的值增加到增加到 时，出基变量时，

14、出基变量xr的值降为的值降为0时，可行解就时，可行解就移动到了相邻的基本可行解（极点），转（移动到了相邻的基本可行解（极点），转（4）。）。2022-6-422 x3 = 120 - 4x1 - 3x2 0 x4 = 50 - 2x1 - x2 0 简化为：简化为：120 - 4x1 0 50 - 2x1 0 选选 x1= min(120/4, 50/2) = 25（最小比值原则或（最小比值原则或原则）原则）, 才使上述不等式成立，并迫使才使上述不等式成立，并迫使 x4 为零；为零；因此需令因此需令 x4 出基。出基。2022-6-423例例如果进基变量的值增加时，所有基变量的值都不减如果进基

15、变量的值增加时，所有基变量的值都不减少，即少，即所有所有aij 非正非正，则表示可行域是不封闭的，且，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解不存在有限最优解，计算结束；，计算结束； （4）将进基变量作为新的基变量，出基变量作将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础新的目标函数值。在新的基变量、非基变量的基础上上重复重复（1）。）。2022-6-424新的典则方程变为新的典则

16、方程变为:4x1 + x3 = 120 - 3x22x1 = 50 - x2 - x4化简后：化简后： z(2) = 1250 + 5x2 - 25x4 x1 = 25 - 0.5x2 - 0.5x4 x3 = 20 - x2 + 2x4第二个基本可行解第二个基本可行解 (25, 0, 20, 0) , z(2)=12502022-6-425例例第二次换基迭代第二次换基迭代选选 x2入基。得到下列不等式关系入基。得到下列不等式关系:x1 = 25 - 0.5x2 - 0.5x4 0 x3 = 20 - x2 + 2x4 0 简化为：简化为：25 - 0.5x2 0 20 - x2 0 选选 x

17、2 = min(25/0.5, 20/1) = 20 时才能使不等式成立，并使时才能使不等式成立，并使 x3为零，令为零，令 x3 出基。出基。换基后的典则形式变为：换基后的典则形式变为：z(3) = 1350 - 5x3 - 15x4x1 = 15 + 0.5x3 - 1.5x4x2 = 20 - x3 + 2x4第三个解为第三个解为(15, 20, 0, 0) ，z(3) = 1350；此时，此时，目标函数表达式中非基变量的系数目标函数表达式中非基变量的系数都为负都为负，目标函，目标函数无法继续改进数无法继续改进。2022-6-426例例2022-6-427n 确定初始的基本可行解确定初始

18、的基本可行解 n 判断现行的基本可行解是否最优判断现行的基本可行解是否最优 n 基本可行解的改进基本可行解的改进 l 换入变量的确定换入变量的确定最大增加原则最大增加原则 l 换出变量的确定换出变量的确定最小比值原则最小比值原则n 用初等变换求改进了的基本可行解用初等变换求改进了的基本可行解 n 确定初始的基本可行解确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定。解也就唯一确定。 为了讨论方便，不妨假设在标准型线性规划中，为了

19、讨论方便，不妨假设在标准型线性规划中，系数矩阵中前系数矩阵中前m m个系数列向量恰好构成一个可行基，个系数列向量恰好构成一个可行基，即即 = =（，），其中（，），其中B=B=（1 1，2 2，m m）为基）为基变量变量x x1 1，x x2 2，x xm m的系数列向量构成的可行基，的系数列向量构成的可行基，=(=(m+1m+1，P Pm+2m+2, ,P,Pn n) )为非基变量为非基变量x xm+1 m+1 ,x,xm+2,m+2,x,xn n的系数列向的系数列向量构成的矩阵。量构成的矩阵。 2022-6-428 用可行基的逆阵用可行基的逆阵-1-1左乘等式两端，再通过移项可推得：左乘等

20、式两端，再通过移项可推得： 若令所有非基变量若令所有非基变量, , 则基变量则基变量 由此可得初始的基本可行解由此可得初始的基本可行解所以约束方程所以约束方程 就可以表示为就可以表示为BBNNXAX=(BN)=BX+NX=bX1B bX=0AX=b-1-1BNX =B b-B NX-1BX =B bNX =02022-6-429l 问题：问题： 要判断要判断m m个系数列向量是否恰好构成一个基并不是一件容易的事。个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵中基由系数矩阵中m m个线性无关的系数列向量构成。个线性无关的系数列向量构成。但是要判断但是要判断m m个系数列向量是否线

21、性无关并非易事。个系数列向量是否线性无关并非易事。 即使系数矩阵中找到了一个基即使系数矩阵中找到了一个基B B，也不能保证该基恰好是可行基。，也不能保证该基恰好是可行基。因为不能保证基变量因为不能保证基变量B B= =-1-1b0b0。 为了求得基本可行解为了求得基本可行解 ，必须求基的逆阵，必须求基的逆阵-1-1。但是求逆阵但是求逆阵-1-1也是一件麻烦的事。也是一件麻烦的事。l 结论：在线性规划标准化过程中应设法得到一个结论：在线性规划标准化过程中应设法得到一个m m阶单位矩阵阶单位矩阵I I作为初作为初始可行基始可行基，1B bX=0-1-1-1BNBNNBAX=bBX +NX =bX

22、=B b-B NXX =0,X =B b2022-6-430 若在化标准形式前，约束方程中有若在化标准形式前，约束方程中有“”不等式，不等式，那么在化标准型时除了在方程式左端减去剩余变量使不等式变那么在化标准型时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为成等式以外，还必须在左端再加上一个非负新变量，称为人工变量人工变量 若在化标准形式前，约束方程中有等式方程，那么可以直接在若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。等式左端添加人工变量。为了设法得到一个为了设法得到一个m m阶单位矩阵阶单位矩阵I I作为初始可行基作

23、为初始可行基，可在线性规，可在线性规划标准化过程中作如下处理：划标准化过程中作如下处理： 若在化标准型前，若在化标准型前，m m个约束方程都是个约束方程都是“”的形式，的形式，那么在化标准型时只需在一个约束不等式左端都加上一个松弛变那么在化标准型时只需在一个约束不等式左端都加上一个松弛变量量x xn+in+i (i=1,2, (i=1,2,m),m)。2022-6-431n 判断现行的基本可行解是否最优判断现行的基本可行解是否最优 假如已求得一个基本可行解假如已求得一个基本可行解 将这一基本可行解代入目标函数，可求得相应的目标函将这一基本可行解代入目标函数，可求得相应的目标函数值数值 其中其中

24、 分别表示基变分别表示基变量和非基变量所对应的价值系数子向量。量和非基变量所对应的价值系数子向量。1B bX=01-1BNBB bZ=CX=(C C )=C B b0B12mNm+1m+2nC =(c ,c ,c ), C =(c,c,c )2022-6-432 要判定要判定 是否已经达到最大值，只需将是否已经达到最大值，只需将 代入目标函数，使目标函数用非代入目标函数，使目标函数用非基变量基变量表表示，示， 即：即： m+1m+2-1-1BNNBm+1,m+1,nnxxC B b+ XC B b+( )x 其中其中 称为称为非基变量非基变量N N的检验向量，它的各个分量称为检验数。若的检验向

25、量，它的各个分量称为检验数。若N N的每一个检的每一个检验数均小于等于验数均小于等于0 0，即，即N N00，那么现在的基本可行解就是最优解。，那么现在的基本可行解就是最优解。-1-1BNX=B b-B NX-1BZ=C B b-1NNBm+1m+1n=C -C B N=(,)BBNN-1-1BBNNBNNN-1-1BNBNXZ=CX=(C C )X=C X +C X =C (B b-B NX )+C X=C B b+(C -C B N)X2022-6-433定理定理1 1 最优解判别定理最优解判别定理 对于线性规划问题对于线性规划问题若某个基本可行解所对应的检验向量，若某个基本可行解所对应的

26、检验向量， 则这个基本可行解就是最优解。则这个基本可行解就是最优解。nmaxZ=CX, D= XR /AX=b,X0-1NNB=C -C B N0定理定理2 2 无穷多最优解判别定理无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量若是一个基本可行解，所对应的检验向量，其中存在一个检验数，其中存在一个检验数m+km+k=0=0，则线性规划问题有无穷多最优解。则线性规划问题有无穷多最优解。1B bX=0-1NNB=C -C B N0m +1m +2-1Bm +1,m +1,nnxxZCBb+()x2022-6-434p24n 基本可行解的改进基本可行解的改进 如果现行的基本可行解不是最优

27、解，即在检验向量如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：具体做法是： 先从检验数为正的非基变量中确定一个换入变量，使它从非基先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量，使它从基变量变成非再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）

28、。基变量（将它的值从正值减至零）。 由此可得一个新的基本可行解，由由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所增加。可知，这样的变换一定能使目标函数值有所增加。-1NNB=C -C B Nm+1m+2-1Bm+1,m+1,nnxxZC B b+( )x2022-6-435 假设检验向量假设检验向量 ， 若其中有两个以上的检验数为正，那么为了使目标函数值增加若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用得快些，通常要用“最大增加原则最大增加原则”，即选取最大正检验数所对应的，即选取最大正检验数所对应的非基变量为换入变量，即若非基变量为换入变量，即

29、若 则选取对应的则选取对应的 为换入变量，为换入变量， 由于由于 且为最大，且为最大， 因此当由零增至正值，因此当由零增至正值， 可使目标函数值可使目标函数值 最大限度的增加。最大限度的增加。 换入变量和换出变量的确定换入变量和换出变量的确定：l换入变量的确定换入变量的确定最大增加原则最大增加原则 -1NNBm+1m+2n=C -C B N=(,)jjm+kmax / 0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )x2022-6-436l 换出变量的确定换出变量的确定最小比值原则最小比值原则 如果确定如果确定 为换入变量，方程为换入变量，方程其中其中 为中与对应的系数列向量。为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。 当当 由零慢慢增加到某个值时，由零慢慢增加到某个值时， 的非负性可能被打破。的非负性可能被打破。 为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小比值原则确定换出变量： B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B