第一章线性规划与单纯形法 §3线性规划问题的几何意义 定义（凸集）设K是n维欧氏空间的一个点集，若 任意两点x(1)∈K,X(2)∈K的连线上的一切点 aX1)+(1-a)x(2)=X∈K (0≤a≤1) 则称K为凸集。 凸集的特征是：连接集合中任意两点的线段整个地 都在集合之中。实心的凸多边形、凸多面体都是凸集。 定义（凸组合）设x1),x(2),,xk)是n维欧氏 空间的k个点，若存在满足0≤μ：≤1,1=1,2.k, 则称 X=μ1X1D+μ2X(2)+..+μkX(k) 含41 为x1),X(2),,Xk)的凸组合
第一章 线性规划与单纯形法 §3 线性规划问题的几何意义 定义（凸集） 设K是n维欧氏空间的一个点集，若 任意两点x（1）∈K ， x（2）∈K的连线上的一切点 αx（1）+（1-α）x（2）=x∈K (0≤α≤1) 则称K为凸集。 凸集的特征是：连接集合中任意两点的线段整个地 都在集合之中。实心的凸多边形、凸多面体都是凸集。 定义（凸组合）设x（1） , x（2） ,…,x（k）是n维欧氏 空间的k个点，若存在满足0≤μi≤1, i=1,2…k, 则称 x=μ1x（1）+μ2x（2）+…+μkx（k） 为x（1）,x（2） ,…,x（k）的凸组合. 1, 1 = = k i i
定义（顶点）设K是凸集，X∈K,若X不能表示成任何 (1) ∈K,x(2)∈K两点连线的内点，则称X为K的一个顶 点（或极点）。 关于线性规划问题解的性质，介绍以下几个定理： 定理3.1线性规划的可行域D={xAx=b,x≥0} 是一个凸集。 证明：设x(1)∈D,X(2)∈D,且x(1)≠x(2) 则 Ax1)=b,X1)≥0；Ax(2)=b,X(2)≥0 令 x=aX1)+(1-a)X(2) 则 Ax=aAx1)+(1-a)Ax(2)=b,且x≥0 '.X∈D 因此，根据凸集的定义，知D是凸集
定义（顶点）设K是凸集,X∈K，若X不能表示成任何 x（1）∈K， x（2）∈K两点连线的内点，则称X为K的一个顶 点（或极点）。 关于线性规划问题解的性质，介绍以下几个定理： 定理3.1 线性规划的可行域 D=｛x︱Ax=b,x≥0｝ 是一个凸集。 证明：设x（1）∈D，x（2） ∈D，且x（1）≠x（2） 则 Ax（1）=b, x（1）≥0；Ax（2）=b, x（2）≥0 令 x＝αx（1）+（1-α）x（2） 则 Ax＝αAx（1）+（1-α）Ax（2）=b,且x≥0 ∴x∈D 因此，根据凸集的定义，知D是凸集
引理1线性规划的可行解X=(x1,X2…x)是基可行解 的充要条件是：X的正分量对应的系数列向量是线性无关 的。 定理3.2X是可行域D={x|Ax=b,x≥0}的顶点的充 要条件是：X是该线性规划问题的基可行解。 证明：必要性→设X是D的顶点。若X不是基可行解， 不妨设x1>0,X2>0,,X>0,Xk+1-xn-0.由写引理1知 P1,P2,,P必线性相关，于是存在不全为0的一组数a1, ak满足 含男0令的 显然0>0。 取x1=(X1+0a1,X2+0a2,,Xk+0ak,0,,0)7 X(2)=(X1-0a1,X2-0a2,,Xk-0ak,0,,0)7
引理1 线性规划的可行解X=(x1 ,x2…xn ) T是基可行解 的充要条件是： X的正分量对应的系数列向量是线性无关 的。 定理3.2 X是可行域D=｛x︱Ax=b,x≥0｝的顶点的充 要条件是：X是该线性规划问题的基可行解。 证明：必要性→设X是D的顶点。若X不是基可行解， 不妨设x1＞0,x2＞0,…,xk＞0, xk+1 =…=xn =0.由引理1知 P1,P2,…,Pk必线性相关,于是存在不全为0的一组数α1, α2,…,αk满足 0 1 = = k j j j αp , = , 1,2, ,k α x α 0 ,令θ min j j j j 显然θ>0。 取x（1）=(x1 +θα1,x2 +θα2,…,xk+θαk,0,…,0)T x（2）=(x1 -θα1,x2 -θα2,…,xk-θαk,0,…,0)T
易于验证x1)∈D,x(2)∈D,x1)≠x(2)且 X=X+闷，此与X是D的顶点矛盾，因而x是基可行解。 充分性：一设X是问题的基可行解，不妨设x1>0,X2> 0,,X>0,Xk1-X-0(k≤m),于是P1,P2,,Pk必线 性无关。若X不是D的顶点，则存在x1)∈D,x(2)∈D, x1)≠x(2)及a∈(0,1)，有 X=aX1)+(1-a)x(2) 于是，对jk+1,k+2,,n,有0=X=ax+1-ax 因此，对于jk+1,k+2,,n,应有x9=x号=0 并且会p-=0，由丁P,PP线性无关， 故x9=x8,j1,2,,k.这就得到了x1)=x2)之矛盾。 因此，X必为顶点
易于验证x（1）∈D，x（2） ∈D，x（1）≠x（2）且 ，此与X是D的顶点矛盾，因而X是基可行解。 = + 1 2 X 2 X 1 2 X 1 充分性：←设X是问题的基可行解，不妨设x1＞0,x2＞ 0,…,xk＞0, xk+1 =…=xn =0（k≤m），于是P1,P2,…,Pk必线 性无关。若X不是D的顶点，则存在x（1）∈D，x（2） ∈D， x（1）≠x（2）及α∈（０，１），有 x＝αx（1）+（1-α）x（2） 于是，对j=k+1,k+2,…,n，有 因此，对于j=k+1,k+2,…,n，应有 并且 ，由于P1,P2,…,Pk线性无关， 故 ,j=1,2,…,k.这就得到了x（1）=x（2）之矛盾。 因此，Ｘ必为顶点。 = = + − 2 j 1 j j 0 x αx 1 αx x x 0 2 j 1 j = = x x 0 k p 2 j 1 j j 1 j − = = = 2 j 1 j x x
引理2若K是有界凸集，则任何一点X∈K都可表 示为K的顶点的凸组合。 定理3.3若可行域非空有界， 则线性规划问题一定 可以在可行域的某个顶点上找到最优解。 证明：不妨设可行域的顶点为x(1),x(2),.,x(k) 再设x(0)是可行域D的任意一点。由引理2，有 x0-ax0,0≤a1≤1，a=l 1 因e9全-含e设删-c 则有 cxO)= 由X(0)的任意性，知线性规划在顶点X(m)处达到最优
引理２ 若Ｋ是有界凸集，则任何一点x∈Ｋ都可表 示为Ｋ的顶点的凸组合。 定理３.３ 若可行域非空有界，则线性规划问题一定 可以在可行域的某个顶点上找到最优解。 证明：不妨设可行域的顶点为x（１） ，x（2） ，…，x（k） 再设x（0）是可行域Ｄ的任意一点。由引理２，有 ， 0≤αi≤１,Σαi=1 因此， 则有 由X（0）的任意性,知线性规划在顶点X（m）处达到最优。 = = k x αx i 1 i i 0 = = = = k αcx k cx c αx i 1 i i i 1 i i 0 (m) i i 1 k ,设max cx =cx = → ( ) (m) i 1 m i i 1 i i 0 cx k αcx k cx = αcx = = =
重要结论 根据以上讨论，可以得到以下结论： 线性规划问题的可行域是凸集（定理3.1）；凸集的 每个顶点对应一个基可行解（定理3.2），基可行解个数 是有限的，当然凸集的顶点也是有限的；若线性规划有最 优解，必在可行域某顶点上达到（定理3.3），亦即在有 限个基可行解中间存在最优解。因此，我们可以在有限个 基可行解中去找最优解。这就是下节将介绍的单纯形法的 理论依据，该方法就是一种在基可行解中搜索最优解的算 法
根据以上讨论，可以得到以下结论： 线性规划问题的可行域是凸集（定理3.1）；凸集的 每个顶点对应一个基可行解（定理3.2），基可行解个数 是有限的，当然凸集的顶点也是有限的；若线性规划有最 优解，必在可行域某顶点上达到（定理3.3），亦即在有 限个基可行解中间存在最优解。因此，我们可以在有限个 基可行解中去找最优解。这就是下节将介绍的单纯形法的 理论依据，该方法就是一种在基可行解中搜索最优解的算 法。 重要结论