9《线性规划》092第二章2.6几何意-义-2.5初始基=第九次课解析

2.6单纯形法的几何意义一、基本概念1、凸集和凸组合01(1)、直线段：并称x(1)，x(2)为线段的端点;称集合为Rn中的直线段，称线段上其余的点为线段的内点。(1)(2)(1)(2)(1),01xxxxxx凸集的几何意义：是集合中任意两点的连线仍在该集合中。即集中任意两点间的直线段上的所有点都属于该集合。从直观上讲，凸集无凹陷部分，其内部没有洞。(2)、凸集(P62定义1):(1)(2)(1)(2)[0,1](1)CxxCxxC，，凸集任意的任意的有为凸组合1x2x4x3x3x2x1x4x凸集非凸集凸组合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①直线段中任意一点皆为两端点的凸组合。注:②凸集——集合中任意两点的凸组合仍然属于此集合。推广：凸集C中任意有限个点的凸组合仍属于C。(P69第5题)2.6单纯形法的几何意义一、基本概念2、极点(P63)凸集C的极点属于此集合C，但是（顶点）定义2：设C为Rn中的凸集，设x(0)∈C，称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中任何两个不同点的连线的内点内点凸集5x2x1x4x只能为端点3x7x6x2.6单纯形法的几何意义一、基本概念3、超平面和闭半空间(1)、超平面：(2)、闭半空间:集合H称为Rn中的超平面，其中{,}nHxaxxR{,}nHxaxxR{,}nHxaxxR集合H＋和H－称为Rn中的闭半空间，其中即，H＋和H－是由超平面H所划分的两个闭半空间。注:①超平面H恰为两个闭半空间的交集，即H=H＋∩H－。平面中，超平面实为平面中的直线，而由此超平面所划分的两个闭半空间实为两个半平面。三维空间中，超平面就是通常所说的平面。②闭半空间是闭凸集(P69第2题)。③闭半空间的交集是闭凸集。闭集∩闭集→闭集凸集∩凸集→凸集Rn中有限个闭半空间的交集称为多面凸集，多面凸集的极点又称为顶点。显然，多面凸集是闭凸集，但多面凸集不一定有界。有界的多面凸集称为凸多面体。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),01，则必有。(0)(1)(2)xxx(3)(4)(1)(2),xxxx2x3x端点内点只能是其他线段的端点极点x4、x5相邻，极点x1、x4不相邻4x6x7x5x1x2.6单纯形法的几何意义一、基本概念4、多面凸集和凸多面体例如，在空间R3中，设超平面如下：2、以下交集表示怎样的多面凸集？问：1、以下闭半空间表示什么？{,}nHxaxxR{,}nHxaxxR{,}nHxaxxR3、多面凸集K、L、M是否有界？是否有极点？极点有哪些？相邻极点是哪些？T3(0,0,1){(,,)(,,)0}HxyzxyzT1(1,0,0){(,,)(,,)0}HxyzxyzT2(0,1,0){(,,)(,,)0}HxyzxyzT4(1,1,1){(,,)(,,)1}Hxyzxyz1234,,,,HHHH1234,,,HHHH1Hxyzo4H2H3H123KHHH1234MHHHH1234LHHHH√√2.6单纯形法的几何意义一、基本概念一些关于凸集的结论：结论2：任意多个凸集的交还是凸集。(P69第3题)结论3：凸集C中任意有限个点的凸组合仍属于C。(P69第5题)结论4：闭半空间是闭凸集(P69第2题)。结论5：闭半空间的交集是闭凸集。结论1：超平面是闭凸集。二、单纯形法的几何意义2.6单纯形法的几何意义可行域是凸的、闭的，且是由若干超平面和闭半空间所围成的凸集。定理2.9(P64)任意一个线性规划问题的可行解集是一个闭凸集，并且是多面凸集。可行域是凸集，即是说线性规划问题的任意两个可行解所连成的线段上的点仍然是可行解。若LP有最优解，则最优解必定能够在可行域的顶点达到。二、单纯形法的几何意义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.2+2.10几何解释定理2.3+2.10并非“只能”二、单纯形法的几何意义2.6单纯形法的几何意义定理2.9(P64)任意一个线性规划问题的可行解集是一个闭凸集，并且是多面凸集。定理2.10(P64)设K为标准线性规划问题LP的可行解集，则x(0)为K的极点x(0)为LP的基可行解。基可行解↔可行域的顶点定理2.6(P31)若基可行解x(0)对应的典式中，有某个检验数0r，而T12(,,,)mrrrbbb中至少有一个大于零，并且00ib，(1,2,,)im，则必存在另一基可行解，其对应的目标函数值比(0)()fx小。几何解释定理2.6+2.10定理2.10(P65)设对LP施行一次单纯形迭代时，从基可行解x(1)转换到x(2)，且已知x(1)是非退化的，则x(1)与x(2)是LP的可行解集K的相邻极点。每次单纯形迭代中基的转换：都是相邻极点的转换，不是跳跃的。若LP有最优解，则必能在K的极点中找到最优解。二、单纯形法的几何意义2.6单纯形法的几何意义若K非空，则必有极点，且极点的个数有限。几何意义：线性规划问题LP的可行解集K是Rn中的多面凸集。单纯形法的迭代过程，是K的一个极点到另一个相邻极点的相继转换过程，使目标函数值逐步改进，直至得出最优解或判定问题无最优解。下面举例说明单纯形法的几何意义(以2.3节的例4*作图解释)以B1=(p3,p4,p5)为初始可行基，以x(1)=(0,0,4,3,8)T为初始基可行解开始；2.6单纯形法的几何意义例4*求解问题s.t.12121212max24328,0fxxxxxxxx化为标准型后用单纯形法求解迭代一次再迭代一次非退化单纯形法求解结果如下：例4(P45)求解问题s.t.121214523243280(1,n2,5)m,iixxxfxxxxxxxi继续迭代另一最优基可行解x(4)=(4,2,0,1,0)T。求解结果如下：最优基可行解x(3)=(2,3,2,0,0)T；基可行解x(2)=(0,3,4,0,2)T；=(0,0)T(1)ˆx=(0,3)T(2)ˆx=(2,3)T(3)ˆx=(4,2)T(4)ˆx最优基可行解二、单纯形法的几何意义2.6单纯形法的几何意义只需证明为多面凸集，即可知为闭凸集(P69第2题)。定理2.9线性规划问题的可行解集是闭凸集，并且是多面凸集。设线性规划问题的一般形式(P7)的约束条件为：证明：于是以上约束条件可改写为：112211122211223123,(1,2,),(1,2,),(1,2,)0(1,2),iiinnijjjnnjkkknnklaxaxaxbimaxaxaxbjmaxaxaxbkmxlnmmmm，，，其中→将每个式子改写成向量形式设T1212(,,,)(1,2),(,,,),llllnnaaaalnxxxx(0,,0,1,0,,0)le是第l个分量为1的单位行向量。123,(1,2,),(1,2,),(1,2,)0(1,2)iijjkklaxbimaxbjmaxbkmexln，，，多面凸集——有限个闭半空间的交集二、单纯形法的几何意义2.6单纯形法的几何意义定理2.9线性规划问题的可行解集是闭凸集，并且是多面凸集。于是线性规划问题的可行解集为以下n+m个集合的交集：证明：于是线性规划问题的可行解集为上述有限个闭半空间的交集，故为多面凸集，从而为闭凸集。1(1,2,)iixaxbim，2(1,2,)jjxaxbjm，3(1,2,)kkxaxbkm，0(1,2)lxexln以上集合，除外均为闭半空间。3(1,2,)kkxaxbkm，kkkkkkxaxbxaxbxaxb而多面凸集——有限个闭半空间的交集3(1,2,)km，为闭半空间的交集，2.5初始基可行解的求法第二章单纯形方法第二章单纯形方法一、初始基可行解的选择方法2.5初始基可行解的求法一般的线性规划问题，当约束条件都是“≤”时，加入松弛变量标准化之后，我们可得到一个显然的基可行解(如松弛变量作为基变量的一个初始基可行解)。然而，并非所有问题标准化之后都可得到一个显然的初始基可行解，比如含有“≥”或“＝”型约束的线性规划，就没有现成的单位矩阵。所以，直接确定线性规划问题的一个初始基可行解是比较困难的。这时就需要我们寻找确定初始基可行解的方法。一、初始基可行解的选择方法2.5初始基可行解的求法通常采用的是人工变量法来确定初始基可行解。将原问题的约束条件标准化，再引入非负的人工变量，建立辅助问题。辅助问题以人工变量作为初始基变量，其对应的系数列向量便构成单位阵，称为“人造基”。求解辅助问题后便可以得到原问题的一个初始基可行解。一般有两种方法：1、大M法(罚因子法)：规定人工变量在目标函数中的系数为－M(M为任意大的数)2、两阶段法用计算机处理数据时，只能用很大的数代替M，可能造成计算机上的错误，故多采用两阶段法。人工变量法：二、两阶段法两阶段法第一阶段：通过辅助问题判断原问题是否有基可行解。若有解则进入第二阶段。定义(P56)对于不具有明显可行基的线性规划问题LP，可先解它的辅助问题(LP)1,解的结果或者说明原问题LP无可行解，或者找到LP的一个基可行解；然后再从这个基可行解开始求解原问题LP。这种求解LP的方法称为两阶段法(或人造基方法)，辅助问题(LP)1又称为第一阶段问题。第二阶段：从第一阶段求得的基可行解出发，对原问题继续迭代，求最优解。2.5初始基可行解的求法如果某一个右端元素bi0，该方程两边乘于－1，则可以使右端数变成正数。二、两阶段法1、第一阶段：求解辅助问题(LP)1，获得LP的初始基可行解设标准线性规划LP，且不妨设,系数矩阵A未必行满秩。0b11111221121122222112212mins.t.,,,0njjjnnnnmmmnnmnfcxaxaxaxbaxaxaxbaxaxaxbxxx原问题LP加入非负人工变量2.5初始基可行解的求法目标函数仅含人工变量，为全体人工变量之和。121211112211211222221122121,mins.t.,,...,......,0,nn