《线性规划》第二章2.4退化问题 2.6单纯形法的几何意义=第八次课

1、 第四步第四步，若检验数中有些为正数，且它们所对应的系数，若检验数中有些为正数，且它们所对应的系数bir中有正数，则需要换基、进行迭代运算。中有正数，则需要换基、进行迭代运算。 在所有大于零的检验数中选取最大的一个，设对应的在所有大于零的检验数中选取最大的一个，设对应的非基变量为非基变量为xr， 则取则取xr为进基变量，并求最小比值：为进基变量，并求最小比值：由此确定由此确定xj s为离基变量为离基变量( (若上述最小值同时在几个比值上若上述最小值同时在几个比值上达到，则选取其中下标最小的变量为离基变量达到，则选取其中下标最小的变量为离基变量) )。然后用然后用pr代代换换pjs，得到新基，得

2、到新基 ，再接下一步。，再接下一步。00m in0,1, 2,iriirrrsbbbimbb B 第五步第五步，求出新基，求出新基 对应的典式以及基可行解对应的典式以及基可行解x (1)，然后，然后以以 取代取代B，x (1)取代取代x (0)，返回第二步。返回第二步。 BB从第二步到第五步的每一次循环，称为一次从第二步到第五步的每一次循环，称为一次单纯形迭代。单纯形迭代。复习复习2.4 2.4 退化情形的处理退化情形的处理最大检验数规则最大检验数规则最小下标规则最小下标规则2.4 2.4 退化情形的处理退化情形的处理 2、由于退化问题的目标函数值在迭代过程中可能并不改、由于退化问题的目标函数

3、值在迭代过程中可能并不改进，一旦前面出现的基在迭代过程中又重新出现进，一旦前面出现的基在迭代过程中又重新出现，则后面的则后面的迭代过程可能会在几个基上面兜圈子，此现象成为迭代过程可能会在几个基上面兜圈子，此现象成为“基的循基的循环环”。对退化的线性规划问题，使用单纯形法时：对退化的线性规划问题，使用单纯形法时： 对非退化的线性规划问题使用单纯形法时，对非退化的线性规划问题使用单纯形法时，由于每次迭代都使目标函数值有所改进，从而经过有限次迭由于每次迭代都使目标函数值有所改进，从而经过有限次迭代，必能求得最优解或判断问题无最优解。代，必能求得最优解或判断问题无最优解。非退化情形：非退化情形：退化情

4、形：退化情形： 3、若问题还未达到最优就出现了、若问题还未达到最优就出现了“基的循环基的循环”，再按照通，再按照通常的单纯形法继续迭代下去，必然导致常的单纯形法继续迭代下去，必然导致“死循环死循环”，以致最终，以致最终不能得到最优解。不能得到最优解。(如如P48的的Beale例子例子) 1、如果迭代过程中基不出现重复，则经过有限次迭代也、如果迭代过程中基不出现重复，则经过有限次迭代也能得到最优解或判断问题无最优解。能得到最优解或判断问题无最优解。(如如2.3节的例节的例4)2.4 2.4 退化情形的处理退化情形的处理方法：摄动法、字典序法、布兰德规则方法：摄动法、字典序法、布兰德规则定理定理2

5、.7(P50) 对任一线性规划问题对任一线性规划问题LP用单纯形法求解时，按用单纯形法求解时，按Bland规则确定进基变量和离基变量，便不会出现基的循环。规则确定进基变量和离基变量，便不会出现基的循环。可确保不出现可确保不出现基的循环基的循环规则规则1、当有多个检验数是正数时，选对应变量中下标最小者当有多个检验数是正数时，选对应变量中下标最小者 为进基变量。为进基变量。与普通单纯形法：有区别与普通单纯形法：有区别布兰德布兰德(Bland)规则规则规则规则2、当最小比值当最小比值同时在多行达到时，选取对应基变量中同时在多行达到时，选取对应基变量中 下标最小者为离基变量。下标最小者为离基变量。即由

6、即由 确定进基变量为确定进基变量为xr 。 min|0(2.39)jjr 000minmin(2.40)lsiribrirllbbjjbb 即由即由确定离基变量为确定离基变量为xjs 。进基、离基均采用最小下标规则进基、离基均采用最小下标规则与普通单纯形法：没有区别与普通单纯形法：没有区别s.t. 123412345123463731min150645011609042511903025010 (1,2,7)ifxxxxxxxxxxxxxxxxxi 2.4 2.4 退化情形的处理退化情形的处理P48 Beale例子例子用用Bland法则求解法则求解解：解：取初始基为取初始基为B0=( p5，p

7、6，p7 )且原问题即为基且原问题即为基B0对应的典式。对应的典式。且此问题为退化的线性规划问题。且此问题为退化的线性规划问题。基基B0对应的单纯形表见表对应的单纯形表见表2-15 。 在第在第1、2行取得，行取得，故故x5为离基变量。为离基变量。2.4 2.4 退化情形的处理退化情形的处理由表由表2-15可知，可知， x1 、x3的的检验数均为正数，由检验数均为正数，由Bland规则，取规则，取x1为进基变量。为进基变量。因为最小比值因为最小比值解：解： 基基 B0=( p5，p6，p7 )对应的单纯形表见表对应的单纯形表见表2-15 。于是，于是，b11为表为表2-15的枢元，新基为的枢元

8、，新基为B1=( p1，p6，p7 )。 并将并将x5换为换为x1，得新基，得新基B1对应的单纯对应的单纯形表，见表形表，见表2-16：对表对表2-15作初等行变换，作初等行变换，x1为新的基变量，则对应单位列向量为新的基变量，则对应单位列向量进基的选择也进基的选择也符合：最大检符合：最大检验数规则验数规则*最小下标规则最小下标规则离基离基进基进基P48 Beale例子例子用用Bland法则求解法则求解2.4 2.4 退化情形的处理退化情形的处理由表由表2-16可知，可知， x2 、x3的的检验数均为正数，由检验数均为正数，由Bland规则，取规则，取x2为进基变量。为进基变量。解：解： 基基

9、 B1=( p1，p6，p7 )对应的单纯形表见表对应的单纯形表见表2-16。进基的选择也符合：最进基的选择也符合：最大检验数规则。大检验数规则。进基进基类似地，得到基类似地，得到基 B2=( p1，p2，p7 )。P48 Beale例子例子用用Bland法则求解法则求解2.4 2.4 退化情形的处理退化情形的处理由表由表2-17可知，可知， 只有只有x3的的检验数均为正数，取检验数均为正数，取x3为为进基变量。进基变量。解：解： 基基 B2=( p1，p2，p7 )对应的单纯形表见表对应的单纯形表见表2-17 。进基进基类似地，得到基类似地，得到基 B3=( p3，p2，p7 )。P48 B

10、eale例子例子用用Bland法则求解法则求解进基的选择：既符合最进基的选择：既符合最大检验数规则，又符合大检验数规则，又符合Bland规则。规则。2.4 2.4 退化情形的处理退化情形的处理由表由表2-18可知，可知， x4 、x5的的检验数均为正数，由检验数均为正数，由Bland规则，取规则，取x4为进基变量。为进基变量。解：解： 基基 B3=( p3，p2，p7 )对应的单纯形表见表对应的单纯形表见表2-18 。进基进基进基的选择也符合：最进基的选择也符合：最大检验数规则。大检验数规则。类似地，得到基类似地，得到基 B4=( p3，p4，p7 )。前前4次迭代：用最大检验数规则和次迭代：

11、用最大检验数规则和Bland规则的结论一样，规则的结论一样，具体结果都是表具体结果都是表2-15与与2-19。P48 Beale例子例子用用Bland法则求解法则求解 在第在第3行取行取得，得， 故故x7为离基变量。为离基变量。2.4 2.4 退化情形的处理退化情形的处理由表由表2-19可知，可知， x1 、x5的的检验数均为正数，由检验数均为正数，由Bland规则取规则取x1为进基变量。为进基变量。因为最小比值因为最小比值解：解： 基基 B4=( p3，p4，p7 )对应的单纯形表见表对应的单纯形表见表2-19 。于是，于是，b31为表为表2-19的枢元，新基为的枢元，新基为B5=( p3，

12、p4，p1 )。 并将并将x7换为换为x1，得新基，得新基B5对应的单纯对应的单纯形表，见表形表，见表2-22：对表对表2-19作初等行变换，作初等行变换，x1为新的基变量，则对应单位列向量为新的基变量，则对应单位列向量进基的选择：进基的选择：不符合不符合最大检最大检验数规则，否验数规则，否则则x5才是进基才是进基变量。变量。*离基离基进基进基P48 Beale例子例子用用Bland法则求解法则求解 在第在第2行行取得，取得， 故故x4为离基变量。为离基变量。2.4 2.4 退化情形的处理退化情形的处理由表由表2-22可知，只有可知，只有 x5的的检验数为正数，故取检验数为正数，故取x5为为进

13、基变量。进基变量。因为最小比值因为最小比值解：解： 基基 B5=( p3，p4，p1 )对应的单纯形表见表对应的单纯形表见表2-22 。于是，于是，b25为表为表2-22的枢元，新基为的枢元，新基为B6=( p3，p5，p1)。 并将并将x4换为换为x5，得新基，得新基B6对应的单纯对应的单纯形表，见表形表，见表2-23：对表对表2-22作初等行变换，作初等行变换，x3为新的基变量，则对应单位列向量为新的基变量，则对应单位列向量进基的选择也进基的选择也符合：最大检符合：最大检验数规则验数规则*离基离基进基进基P48 Beale例子例子用用Bland法则求解法则求解2.4 2.4 退化情形的处理

14、退化情形的处理解：解： 基基 B6=( p3，p5，p1)对应的单纯形表见表对应的单纯形表见表2-23 。，最优值为，最优值为f*=f(x*)由表由表2-23可知，检验数全部非正，故表可知，检验数全部非正，故表2-23为最优解表。为最优解表。检验数全部非正，检验数全部非正，满足定理满足定理2.4对应最优解为对应最优解为x*最优解表最优解表T13(,0,1,0,0,0)25100 为该基解的基分量的值为该基解的基分量的值为该基解对应的目标函数值为该基解对应的目标函数值120 。P48 Beale例子例子用用Bland法则求解法则求解解：解： 基基 B4=( p3，p4，p7 )对应的单纯形表见表

15、对应的单纯形表见表2-19 。2.4 2.4 退化情形的处理退化情形的处理由由Bland规则，规则，x1为进基变量；为进基变量；*离基离基进基进基对比对比由最大检验数规则，由最大检验数规则，x5为进基变量；为进基变量；进基进基*离基离基x3为离基变量。为离基变量。x7为离基变量。为离基变量。采用采用Bland规则后，目标函数值得到了改善，规则后，目标函数值得到了改善，也不在再现基的循环了，详见表也不在再现基的循环了，详见表2-20与与2-22.2.4 2.4 退化情形的处理退化情形的处理对比对比退退化化的的非非退退化化的的采用采用Bland规规则后，目标则后，目标函数值得到函数值得到了改善；也

16、了改善；也不再现基的不再现基的循环了。循环了。2.4 2.4 退化情形的处理退化情形的处理 虽然虽然Bland法则可避免循环，但一般说来求解法则可避免循环，但一般说来求解LP的的 迭代效率较低迭代效率较低 (长期的实际表明，退化经常有，而循环极为罕见长期的实际表明，退化经常有，而循环极为罕见) 。 一般方法：一般方法： 用单纯形法求解用单纯形法求解LP问题时，问题时，一般按照一般按照2.3节节(P3738)的的 步骤与规则步骤与规则(最大检验数规则最大检验数规则)来进行单纯形迭代，对于来进行单纯形迭代，对于 退化退化问题万一问题万一遇到循环现象，再改用遇到循环现象，再改用Bland规则。规则。

17、说明说明2.4 2.4 退化情形的处理退化情形的处理 问题无可行解问题无可行解 (当然就没有最优解当然就没有最优解) 。 有可行解，但是目标函数在可行域上无下界有可行解，但是目标函数在可行域上无下界(此时也此时也 无最优解无最优解)综合定理综合定理2.2至至2.7，可得到如下结论：，可得到如下结论：线性规划问题线性规划问题LP(不管是否退化不管是否退化)有且仅有如下三种可能情形：有且仅有如下三种可能情形： 有最优解，且必能在基可行解中找到最优解。有最优解，且必能在基可行解中找到最优解。可行域为空集可行域为空集定理定理2.8若线性规划问题若线性规划问题LP的可行域非空，且目标函数在可行域上的可行

18、域非空，且目标函数在可行域上有下界有下界，则，则LP必有最优解。必有最优解。可行域可行域非空非空检验数全部检验数全部00时时为最优解为最优解全部全部0 唯一解。唯一解。存在存在=0 无穷多个解。无穷多个解。非基变量非基变量检验数检验数第二章第二章 单纯形方法单纯形方法在在1.31.3节节“图解法图解法”已经得到如下结论：已经得到如下结论：2.6 2.6 单纯形法的几何意义单纯形法的几何意义1、线性规划的可行域是一个什么形状？、线性规划的可行域是一个什么形状？多边形，而且是多边形，而且是“凸凸”的多边形。的多边形。2、最优解在什么位置获得？、最优解在什么位置获得？在边界，而且是在某个顶点获得。在

19、边界，而且是在某个顶点获得。这些结论具有这些结论具有普遍意义，对普遍意义，对于两个以上变于两个以上变量的线性规划量的线性规划问题也成立。问题也成立。凸集凸集顶点顶点基可行解基可行解x(1)2.6 2.6 单纯形法的几何意义单纯形法的几何意义1、凸集和凸组合、凸集和凸组合(1)、直线段：、直线段：并称并称x(1)，x(2)为线段的端点为线段的端点(他们分别对应他们分别对应=0与与=1)；x(2)(1)(2)xx设设 ，称集合称集合为为Rn中的直线段，中的直线段， (1)(2)(1),01xxxx (1)(2),Rnxx 记为记为(1)(2).xx称线段上其余的点为线段的内点。称线段上其余的点为线

20、段的内点。端点端点端点端点内点内点01 2.6 2.6 单纯形法的几何意义单纯形法的几何意义1、凸集和凸组合、凸集和凸组合(2)、凸集凸集 (P62定义定义1):定义定义1 设设C是是Rn中的中的点集，若点集，若对对任意任意的的x(1)，x(2)C和和任意任意 实数实数 (0，1)，有有 x(1)+(1- )x(2) C则称则称C是是Rn中的中的凸集，否则为非凸集。凸集，否则为非凸集。代数定义代数定义凸集的几何意义：是集合中任意两点的连线仍在该集合中。凸集的几何意义：是集合中任意两点的连线仍在该集合中。即集中任意两点间的直线段上的所有点都属于该集合。即集中任意两点间的直线段上的所有点都属于该集

21、合。从直观上讲，凸集从直观上讲，凸集无无凹陷凹陷部分，其内部分，其内部没有洞。部没有洞。凸集凸集1x2x非凸集非凸集4x3x3x2x1x (1)(2)(1)(2)(1),01xxxxxx 线段上的点线段上的点4x例如：例如：凸集凸集非凸集非凸集2.6 2.6 单纯形法的几何意义单纯形法的几何意义1、凸集和凸组合、凸集和凸组合(2)、凸集凸集 :凸集的特殊情况：一条线、一个点、空集。凸集的特殊情况：一条线、一个点、空集。 两点连线的中的任一点能够表示，如何表示三角形中的两点连线的中的任一点能够表示，如何表示三角形中的任一点呢？如何表示多维空间中的任一点呢？任一点呢？如何表示多维空间中的任一点呢？

22、 集合中任意两点的连线仍在该集合中。集合中任意两点的连线仍在该集合中。凸组合凸组合2.6 2.6 单纯形法的几何意义单纯形法的几何意义1、凸集和凸组合、凸集和凸组合(3)、凸组合凸组合(P63):直线段中任意一点皆为两端点的凸组合。直线段中任意一点皆为两端点的凸组合。两个点的凸组合：当两个点的凸组合：当 时，称向量时，称向量 为为x(1)与与x(2)的凸组合。的凸组合。(1)(2)(1)xx 01 k个点的个点的凸组合凸组合: 设设 ，0 i 1 且且 则称则称 是是x(1)， x(2)， ，x(k)的凸组合。的凸组合。 ( )R (1,2, )inxik 11kii ( )1kiiix 注注

23、:凸集凸集集合中任意两点的凸组合仍然属于此集合。集合中任意两点的凸组合仍然属于此集合。推广：凸集推广：凸集C中任意中任意有限个点有限个点的凸组合仍属于的凸组合仍属于C。(P69第第5题题) (1)(2)(1)(2)(1),01x xx xxx 段段线线(1)( 2 )(1)( 2 )0,1(1)CxxCxxC ，凸凸 集集任任 意意 的的任任 意意 的的有有为为凸组合凸组合凸组合凸组合2.6 2.6 单纯形法的几何意义单纯形法的几何意义2、极点极点(P63)凸集凸集C的极点属于此集合的极点属于此集合C，但是，但是（顶点）（顶点）定义定义2：设：设C为为Rn中的中的凸集凸集，设，设 x(0)C，

24、 称称x(0)为为C的极点的极点 如果存在如果存在x(1) , x(2)C，使，使x(0)(1- )x(1)+ x(2)， 0 1，则必有，则必有x(1)=x(2)= x(0)。不存在不存在x(1)， x(2)C，x(1)x(2)，以及，以及 (0 1)，使得使得 x(0)(1- )x(1)+ x(2) 。不能表示为不能表示为C中任意两点的凸组合，只能表示为极点中任意两点的凸组合，只能表示为极点 自身的凸组合自身的凸组合即是说：即是说： 极点不能用不同的两点的连线表示。极点不能用不同的两点的连线表示。x(0)(1- )x(0)+ x(0)它不能成为它不能成为C中任何两个不同点的连线的内点中任何

25、两个不同点的连线的内点内点内点凸集凸集5x2x1x4x 只能为端点只能为端点3x7x6x二维平面中的凸集与极点举例二维平面中的凸集与极点举例有无数个极点有无数个极点椭圆周上的点都是极点椭圆周上的点都是极点1、多边形、多边形2.6 2.6 单纯形法的几何意义单纯形法的几何意义2、极点极点(P63)仅有有限个极点仅有有限个极点2、闭椭圆域、闭椭圆域3、开圆域、开圆域4、第一象限、第一象限oxy只有一个极点，即坐标原点只有一个极点，即坐标原点2.6 2.6 单纯形法的几何意义单纯形法的几何意义3、超平面和闭半空间、超平面和闭半空间(1)、超平面：超平面：(2)、闭半空间闭半空间:集合集合H称为称为R

26、n中的超平面，其中中的超平面，其中,nHx axxR ,nHx axxR ,nHx axxR 集合集合H和和H称为称为Rn中的闭半空间，其中中的闭半空间，其中即，即，H和和H是由超平面是由超平面H所划分的两个闭半空间。所划分的两个闭半空间。注注: 超平面超平面H 恰为两个闭半空间的交集，即恰为两个闭半空间的交集，即H=HH。 平面中，超平面实为平面中的直线，而由此超平面所划平面中，超平面实为平面中的直线，而由此超平面所划分的分的两个闭半空间实为两个半平面。两个闭半空间实为两个半平面。 三维空间中，超平面就是通常所说的平面。三维空间中，超平面就是通常所说的平面。闭半空间是闭凸集闭半空间是闭凸集(P69第第2题题)。闭半空间的交集是闭凸集闭半空间的交集是闭凸集。闭集闭集闭集闭集闭集闭集凸集凸集凸集凸集凸集凸集Rn中中有限个有限个闭半空间的交集称为多面凸集，闭半空间的交集称为多面凸集，多面凸集的极点又称为顶点。多面凸集的极点又称为顶点。显然，多面凸集是闭凸集，显然，多面凸集是闭凸集，但多面凸集不一定有界。但多面凸集不一定有界。有界的多面凸集称为凸多面体。有界的多面凸集称为凸多面体。2.6 2.6 单纯形法的几何意义单纯形法的几何意义4、多面凸集和相邻极点、多面凸集和相邻极点(1)、多面凸