线性规划退化问题单纯形法的几何意义学习教案

1、会计学1第一页，共27页。2.4 退化情形(qng xing)的处理 2、由于退化问题的目标函数值在迭代过程中可能并不改进，一旦前面出现的基在迭代过程中又重新出现，则后面的迭代过程可能会在几个基上面兜圈子，此现象成为“基的循环”。对退化的线性规划问题，使用单纯形法时： 对非退化的线性规划问题使用单纯形法时，由于每次迭代都使目标函数值有所改进，从而经过有限次迭代，必能求得最优解或判断问题无最优解。非退化情形：退化情形： 3、若问题还未达到最优就出现了“基的循环”，再按照通常的单纯形法继续迭代下去，必然导致“死循环”，以致最终不能得到最优解。(如P48的Beale例子) 1、如果迭代过程中基不出现

2、重复，则经过有限次迭代也能得到最优解或判断问题无最优解。(如2.3节的例4)第1页/共26页第二页，共27页。2.4 退化(tuhu)情形的处理方法：摄动法、字典序法、布兰德规则定理2.7(P50) 对任一线性规划问题LP用单纯形法求解时，按Bland规则确定进基变量和离基变量，便不会出现基的循环。可确保不出现基的循环规则1、当有多个检验数是正数时，选对应变量中下标最小者 为进基变量。与普通单纯形法：有区别布兰德(Bland)规则规则2、当最小比值同时在多行达到时，选取对应基变量中 下标最小者为离基变量。即由 确定进基变量为xr 。 min|0(2.39)jjr 000minmin(2.40)

3、lsiribrirllbbjjbb 即由确定离基变量为xjs 。进基、离基均采用最小下标规则与普通单纯形法：没有区别第2页/共26页第三页，共27页。s.t. 123412345123463731min150645011609042511903025010 (1,2,7)ifxxxxxxxxxxxxxxxxxi 2.4 退化(tuhu)情形的处理P48 Beale例子(l zi)用Bland法则(fz)求解解：取初始基为B0=( p5，p6，p7 )且原问题即为基B0对应的典式。且此问题为退化的线性规划问题。基B0对应的单纯形表见表2-15 。第3页/共26页第四页，共27页。 在第1、2行取

4、得(qd)，故x5为离基变量(binling)。2.4 退化情形(qng xing)的处理由表2-15可知， x1 、x3的检验数均为正数，由Bland规则，取x1为进基变量。因为最小比值解：基 B0=( p5，p6，p7 )对应的单纯形表见表2-15 。于是，b11为表2-15的枢元，新基为B1=( p1，p6，p7 )。 并将x5换为x1，得新基B1对应的单纯形表，见表2-16：对表2-15作初等行变换，x1为新的基变量，则对应单位列向量进基的选择也符合：最大检验数规则*最小下标规则离基进基P48 Beale例子用Bland法则求解第4页/共26页第五页，共27页。2.4 退化(tuhu)

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

6、8 Beale例子用Bland法则求解进基的选择：既符合最大检验数规则，又符合Bland规则。第6页/共26页第七页，共27页。2.4 退化(tuhu)情形的处理由表2-18可知(k zh)， x4 、x5的检验数均为正数，由Bland规则，取x4为进基变量。解：基 B3=( p3，p2，p7 )对应的单纯形表见表2-18 。进基进基的选择(xunz)也符合：最大检验数规则。类似地，得到基 B4=( p3，p4，p7 )。前4次迭代：用最大检验数规则和Bland规则的结论一样，具体结果都是表2-15与2-19。P48 Beale例子用Bland法则求解第7页/共26页第八页，共27页。 在第3

7、行取得，故x7为离基变量(binling)。2.4 退化(tuhu)情形的处理由表2-19可知， x1 、x5的检验数均为正数(zhngsh)，由Bland规则取x1为进基变量。因为最小比值解：基 B4=( p3，p4，p7 )对应的单纯形表见表2-19 。于是，b31为表2-19的枢元，新基为B5=( p3，p4，p1 )。 并将x7换为x1，得新基B5对应的单纯形表，见表2-22：对表2-19作初等行变换，x1为新的基变量，则对应单位列向量进基的选择：不符合最大检验数规则，否则x5才是进基变量。*离基进基P48 Beale例子用Bland法则求解第8页/共26页第九页，共27页。 在第2行

8、取得(qd)，故x4为离基变量(binling)。2.4 退化(tuhu)情形的处理由表2-22可知，只有 x5的检验数为正数，故取x5为进基变量。因为最小比值解：基 B5=( p3，p4，p1 )对应的单纯形表见表2-22 。于是，b25为表2-22的枢元，新基为B6=( p3，p5，p1)。 并将x4换为x5，得新基B6对应的单纯形表，见表2-23：对表2-22作初等行变换，x3为新的基变量，则对应单位列向量进基的选择也符合：最大检验数规则*离基进基P48 Beale例子用Bland法则求解第9页/共26页第十页，共27页。2.4 退化情形(qng xing)的处理解：基 B6=( p3，

9、p5，p1)对应的单纯形表见表2-23 。，最优值为f*=f(x*)由表2-23可知，检验数全部(qunb)非正，故表2-23为最优解表。检验数全部非正，满足定理2.4对应(duyng)最优解为x*最优解表T13(,0,1,0,0,0)25100 为该基解的基分量的值为该基解对应的目标函数值120 。P48 Beale例子用Bland法则求解第10页/共26页第十一页，共27页。解：基 B4=( p3，p4，p7 )对应的单纯形表见表2-19 。2.4 退化情形(qng xing)的处理由Bland规则(guz)，x1为进基变量；*离基进基对比(dub)由最大检验数规则，x5为进基变量；进基*

10、离基x3为离基变量。x7为离基变量。采用Bland规则后，目标函数值得到了改善，也不在再现基的循环了，详见表2-20与2-22.第11页/共26页第十二页，共27页。2.4 退化(tuhu)情形的处理对比(dub)退化的非退化的采用Bland规则后，目标函数值得到了改善；也不再现基的循环了。第12页/共26页第十三页，共27页。2.4 退化(tuhu)情形的处理 虽然Bland法则可避免循环，但一般说来求解LP的 迭代(di di)效率较低 (长期的实际表明，退化经常有，而循环极为罕见) 。 一般方法： 用单纯形法求解LP问题时，一般按照2.3节(P3738)的 步骤与规则(最大检验(jiny

11、n)数规则)来进行单纯形迭代，对于 退化问题万一遇到循环现象，再改用Bland规则。说明第13页/共26页第十四页，共27页。2.4 退化情形(qng xing)的处理 问题无可行(kxng)解 (当然就没有最优解) 。 有可行解，但是目标(mbio)函数在可行域上无下界(此时也 无最优解)综合定理2.2至2.7，可得到如下结论：线性规划问题LP(不管是否退化)有且仅有如下三种可能情形： 有最优解，且必能在基可行解中找到最优解。可行域为空集定理2.8若线性规划问题LP的可行域非空，且目标函数在可行域上有下界，则LP必有最优解。可行域非空检验数全部0时为最优解全部0 唯一解。存在=0 无穷多个解

12、。非基变量检验数第14页/共26页第十五页，共27页。第二章 单纯形方法(fngf)第15页/共26页第十六页，共27页。在1.3节“图解法”已经(y jing)得到如下结论：2.6 单纯形法的几何(j h)意义1、线性规划的可行域是一个(y )什么形状？多边形，而且是“凸”的多边形。2、最优解在什么位置获得？在边界，而且是在某个顶点获得。这些结论具有普遍意义，对于两个以上变量的线性规划问题也成立。凸集顶点基可行解第16页/共26页第十七页，共27页。x(1)2.6 单纯形法的几何(j h)意义1、凸集和凸组合(zh)(1)、直线(zhxin)段：并称x(1)，x(2)为线段的端点(他们分别对

13、应=0与=1)；x(2)(1)(2)xx设 ，称集合为Rn中的直线段， (1)(2)(1),01xxxx (1)(2),Rnxx 记为(1)(2).xx称线段上其余的点为线段的内点。端点端点内点01 第17页/共26页第十八页，共27页。2.6 单纯形法的几何(j h)意义1、凸集和凸组合(zh)(2)、凸集 (P62定义(dngy)1):定义1 设C是Rn中的点集，若对任意的x(1)，x(2)C和任意 实数 (0，1)，有 x(1)+(1- )x(2) C则称C是Rn中的凸集，否则为非凸集。代数定义凸集的几何意义：是集合中任意两点的连线仍在该集合中。即集中任意两点间的直线段上的所有点都属于该

14、集合。从直观上讲，凸集无凹陷部分，其内部没有洞。凸集1x2x非凸集4x3x3x2x1x (1)(2)(1)(2)(1),01xxxxxx 线段上的点4x第18页/共26页第十九页，共27页。例如(lr)：凸集非凸集2.6 单纯形法的几何(j h)意义1、凸集和凸组合(2)、凸集 :凸集的特殊(tsh)情况：一条线、一个点、空集。 两点连线的中的任一点能够表示，如何表示三角形中的任一点呢？如何表示多维空间中的任一点呢？ 集合中任意两点的连线仍在该集合中。凸组合第19页/共26页第二十页，共27页。2.6 单纯形法的几何(j h)意义1、凸集和凸组合(zh)(3)、凸组合(zh)(P63):直线段

15、中任意一点皆为两端点的凸组合。两个点的凸组合：当 时，称向量 为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 注:凸集集合中任意两点的凸组合仍然属于此集合。推广：凸集C中任意有限个点的凸组合仍属于C。(P69第5题) (1)(2)(1)(2)(1),01x xx xxx 段段线线(1)(2)(1)(2)0,1(1)CxxCxxC ，凸凸 集集任任 意意 的的任任 意意 的的有有为为凸组合凸组合第20页/共26页第二十一页，

16、共27页。2.6 单纯形法的几何(j h)意义2、极点(jdin)(P63)凸集C的极点属于此集合(jh)C，但是（顶点）定义2：设C为Rn中的凸集，设 x(0)C， 称x(0)为C的极点 如果存在x(1) , x(2)C，使x(0)(1-)x(1)+ x(2)， 01，则必有x(1)=x(2)= x(0)。不存在x(1)， x(2)C，x(1)x(2)，以及 (01)，使得 x(0)(1-)x(1)+x(2) 。不能表示为C中任意两点的凸组合，只能表示为极点 自身的凸组合即是说：极点不能用不同的两点的连线表示。x(0)(1-)x(0)+x(0)它不能成为C中任何两个不同点的连线的内点内点凸集

17、5x2x1x4x 只能为端点3x7x6x第21页/共26页第二十二页，共27页。二维平面中的凸集与极点(jdin)举例有无数个极点(jdin)椭圆(tuyun)周上的点都是极点1、多边形2.6 单纯形法的几何意义2、极点(P63)仅有有限个极点2、闭椭圆域3、开圆域4、第一象限oxy只有一个极点，即坐标原点第22页/共26页第二十三页，共27页。2.6 单纯形法的几何(j h)意义3、超平面和闭半空间(kngjin)(1)、超平面：(2)、闭半空间(kngjin):集合H称为Rn中的超平面，其中,nHxaxxR ,nHx axxR ,nHx axxR 集合H和H称为Rn中的闭半空间，其中即，H

18、和H是由超平面H所划分的两个闭半空间。注:超平面H 恰为两个闭半空间的交集，即H=HH。 平面中，超平面实为平面中的直线，而由此超平面所划分的两个闭半空间实为两个半平面。 三维空间中，超平面就是通常所说的平面。闭半空间是闭凸集(P69第2题)。闭半空间的交集是闭凸集。闭集闭集闭集凸集凸集凸集第23页/共26页第二十四页，共27页。Rn中有限个闭半空间的交集(jioj)称为多面凸集，多面凸集的极点又称为(chn wi)顶点。显然(xinrn)，多面凸集是闭凸集，但多面凸集不一定有界。有界的多面凸集称为凸多面体。2.6 单纯形法的几何意义4、多面凸集和相邻极点(1)、多面凸集：(2)、凸多面体:(3)、相邻极点(P64):换言之，多面凸集K的两个极点是x(1) , x(2)是相邻极点 定义3：设K是Rn中的多面凸集， x(1) , x(2)为K的两个极点，如果线段 上的任意一点都不可能是K中其他任何线段的内点，则称x(1)与x(2)是K的相邻极点。(1)(2)xxx(1)x(2)且任取 ，若存在x(3)，x(4) K，使得 x(0)(1-)x(3)+x(4) , 01，则必有 。(0)(1)(2)xxx (3)(4)(1)(2),xxx x 2x3x端点内点只能是其他线段的端点极点x4 、x5相邻，极点x1、x4不相邻4x6x7x5x1x第24页/共26页第二