《线性规划》092第二章26几何意义25初始基第九次课解析ppt课件.ppt

《《线性规划》092第二章26几何意义25初始基第九次课解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《《线性规划》092第二章26几何意义25初始基第九次课解析ppt课件.ppt（19页珍藏版）》请在三一办公上搜索。

1、2.6 单纯形法的几何意义,一、基本概念,1、凸集和凸组合,从直观上讲，凸集无凹陷部分，其内部没有洞。,(2)、凸集 (P62定义1):,2.6 单纯形法的几何意义,一、基本概念,1、凸集和凸组合,(3)、凸组合(P63):,2.6 单纯形法的几何意义,一、基本概念,2、极点(P63),凸集C的极点属于此集合C，但是,（顶点）,不能表示为C中任意两点的凸组合，只能表示为极点 自身的凸组合,即是说：,极点不能用不同的两点的连线表示。,x(0)(1-)x(0)+x(0),它不能成为C中任何两个不同点的连线的内点,内点,2.6 单纯形法的几何意义,一、基本概念,3、超平面和闭半空间,(1)、超平面：

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

3、多面凸集：,(2)、凸多面体:,(3)、相邻极点(P64):,换言之，多面凸集K的两个极点是x(1) , x(2)是相邻极点,定义3：设K是Rn中的多面凸集， x(1) , x(2)为K的两个极点，如果线段 上的任意一点都不可能是K中其他任何线段的内点，则称x(1)与x(2)是K的相邻极点。,端点,内点,只能是其他线段的端点,极点x4 、x5相邻，极点x1、x4不相邻,2.6 单纯形法的几何意义,一、基本概念,4、多面凸集和凸多面体,例如，在空间R3中，设超平面如下：,2、以下交集表示怎样的多面凸集？,问：1、以下闭半空间表示什么？,3、多面凸集K、L、M是否有界？是否有极点？极点有 哪些？相

4、邻极点是哪些？,2.6 单纯形法的几何意义,一、基本概念,一些关于凸集的结论：,结论2：任意多个凸集的交还是凸集。(P69第3题),结论3：凸集C中任意有限个点的凸组合仍属于C。(P69第5题),结论4：闭半空间是闭凸集(P69第2题)。,结论5：闭半空间的交集是闭凸集。,结论1：超平面是闭凸集。,二、单纯形法的几何意义,2.6 单纯形法的几何意义,可行域是凸的、闭的，且是由若干超平面和闭半空间所围成的凸集。,定理2.9(P64) 任意一个线性规划问题的可行解集是一个闭凸集，并且是多面凸集。,可行域是凸集，即是说线性规划问题的任意两个可行解所连成的线段上的点仍然是可行解。,若LP有最优解，则最

5、优解必定能够在可行域的顶点达到。,二、单纯形法的几何意义,2.6 单纯形法的几何意义,定理2.9(P64) 任意一个线性规划问题的可行解集是一个闭凸集，并且是多面凸集。,定理2.10 (P64) 设K为标准线性规划问题LP的可行解集，则 x(0)为K的极点 x(0)为LP的基可行解。,基可行解可行域的顶点,定理2.2(P23) 若LP有可行解，则必有基可行解。,定理2.3(P24) 若LP有最优解，则必存在一个基可行解为最优解。,当LP的可行解集K非空时，此可行解集K必有极点。,二、单纯形法的几何意义,2.6 单纯形法的几何意义,定理2.9(P64) 任意一个线性规划问题的可行解集是一个闭凸集

6、，并且是多面凸集。,定理2.10 (P64) 设K为标准线性规划问题LP的可行解集，则 x(0)为K的极点 x(0)为LP的基可行解。,基可行解可行域的顶点,定理2.10 (P65) 设对LP施行一次单纯形迭代时，从基可行解x(1)转换到x(2)，且已知x(1)是非退化的，则x(1)与x(2)是LP的可行解集K的相邻极点。,每次单纯形迭代中基的转换：都是相邻极点的转换，不是跳跃的。,若LP有最优解，则必能在K的极点中找到最优解。,二、单纯形法的几何意义,2.6 单纯形法的几何意义,若K非空，则必有极点，且极点的个数有限。,几何意义：,线性规划问题LP的可行解集K是Rn中的多面凸集。,单纯形法的

7、迭代过程，是K的一个极点到另一个相邻极点的相继转换过程，使目标函数值逐步改进，直至得出最优解或判定问题无最优解。,下面举例说明单纯形法的几何意义(以2.3节的例4*作图解释),以B1=( p3 , p4 , p5 )为初始可行基，以x(1) = (0 , 0 , 4 , 3 , 8)T为初始基可行解开始；,2.6 单纯形法的几何意义,例4 * 求解问题,非退化,单纯形法求解结果如下：,例4 (P45)求解问题,另一最优基可行解x(4) = (4 , 2 , 0 , 1 , 0)T。,最优基可行解x(3) = (2 , 3 , 2 , 0 , 0)T；,基可行解x(2) = (0 , 3 , 4

8、 , 0 , 2)T；,= (0 , 0)T,二、单纯形法的几何意义,2.6 单纯形法的几何意义,只需证明为多面凸集，即可知为闭凸集(P69第2题)。,定理2.9 线性规划问题的可行解集是闭凸集，并且是多面凸集。,设线性规划问题的一般形式(P7)的约束条件为：,证明：,于是以上约束条件可改写为：,将每个式子改写成 向量形式,设,是第 l 个分量为1的单位行向量。,多面凸集有限个闭半空间的交集,二、单纯形法的几何意义,2.6 单纯形法的几何意义,定理2.9 线性规划问题的可行解集是闭凸集，并且是多面凸集。,于是线性规划问题的可行解集为以下n+m个集合的交集：,证明：,于是线性规划问题的可行解集为

9、上述有限个闭半空间的交集，故为多面凸集，从而为闭凸集。,以上集合，除 外均为闭半空间。,而,多面凸集有限个闭半空间的交集,为闭半空间的交集，,2.5 初始基可行解的求法,第二章单纯形方法,第二章 单纯形方法,一、初始基可行解的选择方法,2.5 初始基可行解的求法,一般的线性规划问题，当约束条件都是“”时，加入松弛变量标准化之后，我们可得到一个显然的基可行解(如松弛变量作为基变量的一个初始基可行解)。,然而，并非所有问题标准化之后都可得到一个显然的初始基可行解，比如含有 “”或“”型约束的线性规划，就没有现成的单位矩阵。,所以，直接确定线性规划问题的一个初始基可行解是比较困难的。这时就需要我们寻

10、找确定初始基可行解的方法。,一、初始基可行解的选择方法,2.5 初始基可行解的求法,通常采用的是人工变量法来确定初始基可行解。,将原问题的约束条件标准化，再引入非负的人工变量，建立辅助问题。辅助问题以人工变量作为初始基变量，其对应的系数列向量便构成单位阵，称为“人造基”。求解辅助问题后便可以得到原问题的一个初始基可行解。,一般有两种方法： 1、大M法(罚因子法)：规定人工变量在目标函数中的系数为M (M为任意大的数) 2、两阶段法,用计算机处理数据时，只能用很大的数代替M，可能造成计算机上的错误，故多采用两阶段法。,人工变量法：,二、两阶段法,两阶段法,第一阶段：通过辅助问题判断原问题是否有基

11、可行解。若有 解则进入第二阶段。,定义(P56) 对于不具有明显可行基的线性规划问题LP，可先解它的辅助问题(LP)1 , 解的结果或者说明原问题LP无可行解，或者找到LP的一个基可行解；然后再从这个基可行解开始求解原问题LP。这种求解LP的方法称为两阶段法 (或人造基方法)，辅助问题(LP)1又称为第一阶段问题。,第二阶段：从第一阶段求得的基可行解出发，对原问题继续 迭代，求最优解。,2.5 初始基可行解的求法,如果某一个右端元素bi0，该方程两边乘于1，则可以使右端数变成正数。,二、两阶段法,1、第一阶段：求解辅助问题(LP)1，获得LP的初始基可行解,设标准线性规划LP，且不妨设 , 系数矩阵A未必行满秩。,原问题LP,2.5 初始基可行解的求法,目标函数仅含人工变量，为全体人工变量之和。,人工变量对应单位矩阵Im，便为可行基，称为人造基。,辅助问题(LP)1,