第1章 线性规划及单纯形法(2)

1、第三节 单纯形法原理 一、线性规划规划问题的解的概念 （一）线性规划问题标准型 )8 . 1 (),.,1(0 )7 . 1 (),.,1( . . )6 . 1 (max 1 1 njx mibxa ts xcz j i n j jij n j jj （1）可行解：满足上述约束条件(1.7),(1.8) 的解X=(x1,xn)T，称为线性规划问题的可行 解。全部可行解的集合称为可行域。 （2）最优解：使目标函数(1.6)达到最大值 的可行解称为最优解。 （3）基：设A为约束方程组(1.7)的mn阶 系数矩阵，（设nm），其秩为m，B是矩阵A 中的一个mm阶的满秩子矩阵，称B是线性 规划问题的

2、一个基。不失一般性，设 B中的每一个列向量Pj(j=1,m)称为基向量， 与基向理Pj对应的变量xj称为基变量。线性规 划中除基变量以外的变量称为非基变量。 ),.,( . . . 1 1 111 m mmm m PP aa aa B （4）基解：在约束方程组(1.7)中，令所有 非基变量为xm+1=xm+2=xn=0零，以因为有 |B|0，根据克莱姆法则，由m个约束方程可解 出m个基变量的唯一解XB=(x1,xm)T。将这个 解加上非基解中变量取0的值有X= （x1,x2,xm,0,0,0）T，称X为线性规划问 题的基解。显然在基解中变量取非零值的个数 不大于方程数m，故基解的总数不超过Cn

3、m个。 （5）基可行解：满足变量非负约束条件(1.8) 的基解称为基可行解。 （6）可行基：对应基可行解的基称为可行基。 可行解 基解 基可行解 （二）可行解、基解与基可行解的关系 线性规划的基矩阵、基变量、非基变量 = = 目标函数 约束条件 行列式0 基矩阵 右边常数 （三）线性规划的基本概念的直观描述 （四）求出下列线性规划问题的所有基解、基可行解 该线性规划问题的标准型为： x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 基变量x1、x2、x3，非基变量x4、x5、x6 基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，

4、0） 是基可行解，表示可行域的一个极点。 目标函数值为：z=20 x1+3x2+x3=15 2x1+3x2-x3=18 x1-x2+x3=3 x1+3x2+x4=15 2x1+3x2=18 x1-x2=3 基变量x1、x2、x4，非基变量x3、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基可行解，表示可行域的一个极点。 目标函数值为：z=18 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 x1+3x2=15 2x1+3x2+x5=18 x1-x2=3 x1+3x2+x3+x4=15 2

5、x1+3x2-x3+x5=18 x1-x2+x3+x6=3 基变量x1、x2、x5，非基变量x3、x4、x6 基解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基解，但不是可行解，不是一个极点。 x1+3x2=15 2x1+3x2=18 x1-x2+x6=3 基变量x1、x2、x6，非基变量x3、x4、x5 基解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基可行解，表示可行域的一个极点。 目标函数值为：z=18 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 3x2+x3+x4=15 3x2-

6、x3=18 -x2+x3=3 基变量x2、x3、x4，非基变量x1、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0， 0） 是基解，但不是可行解。 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 3x2+x3=15 3x2-x3+x5=18 -x2+x3=3 基变量x1、x2、x3，非基变量x4、x5、x6 基解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0， 15，0） 是基可行解，表示可行域的一个极点。 目标函数值为：z=15 x1+3x2+x3+x4=15 2x1+3x2-x3+x

7、5=18 x1-x2+x3+x6=3 3x2+x3=15 3x2-x3=18 -x2+x3+x6=3 基变量x1、x2、x3，非基变量x4、x5、x6 基解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0， 0，10） 是基解但不是可行解。 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 例：设有一标准的线性规划问题的约束条件 如下： 2x1+x2+ x4=7 x2+x3 =3 x1,x2,x3,x40 已知下列各点均满足以上的两个方程： (1)(0,7,-4,0)T,(2)(2,3,0,0)T,(3)(1,0,3,5)T

8、(4)(2.5,2,1,0)T,(5)(0,3,0,4)T 二、凸集及其顶点 1凸集 设C是n维空间中的一个点集。若对任 意n维向量X1C，X2C，且X1X2，以及 任意实数（0 1），有 X= X1+(1- )X2C 则称C为n维空间中的一个凸集。点X称 为点X1和X2的凸组合。 以上定义有明显的几何意义，它表示凸 集C中的任意两个不相同的点连线上的点 （包括这两个端点），都位于凸集C之中。 2 顶点 凸集C中满足下述条件的点X称为顶点： 如果C中不存在任何两个不同的点X1，X2，使 X成为这两个点连线上的一个点。或者这样叙 述：对任何X1C，X2C ，不存在X= X1+(1- )X2C （

9、0 1）， 则称X是凸集 C的顶点。 三、几个定理的证明 定理定理1 若线性规划问题存在可行解，则问题的 可行域是凸集。 证：设C为满足约束条件的集合， X1=（x11,x12,x1n)T,X2=(x21,x22,x2n)T为C内任意两 点，即X1C，x2C，将X1，X2代约束条件有： )9.1(; 1 2 1 1 bxPbxP n j jj n j jj X1，X2连线上任意一点可以表示为： )10.1()10()1( 21 XXX 将（1.9）代入（1.10）得： )1( 2 1 1 1 j n j jj n j jj xxPxP bbbb xPxPxP n j jj n j jj n j

10、 jj 1 2 1 2 1 1 即：CXXX 21 )1( 0)1( 21 XXX又 引理引理 线性规划问题的可行解X=（x1,x2,xn) 为基可行解的充要条件是X的正分量所对应 的系数列向量线性独立的。 证：（1）必要性（结论条件） 由基可行解的定义显然成立。 （2）充分性。 （条件结论）若向量 P1,P2,Pk线性独立，则必有km. 当k=m时，它们恰好构成一个基，从而 X=(x1,x2,xm,0,0,.,0)为相应的基可行解。 当Km时，则一定可以从其余列向量中找 出(m-k)个与P1,P2,Pk构成一个基，其对 应的解恰为X，所以根据定义它是基可行解。 定理定理2 线性规划问题的基可

11、行解X对应线性规 划问题可行域（凸集）的顶点。 证：即要证明X是可行域顶点X是基可行解 反证法，即X不是可行域顶点X不是基可行解 （1）X不是基可行解 X不是可行域顶点 不失一般性，设X的前m个分量为正，即： )11.1( 1 bxP m j jj 由引理知P1,P2,Pm线性相关，即存在一组不全为 零的数i(i=1,m)使得有： 1P1+ 2P2+ mPm=0 (1.12) (1.12)式乘上一个不为零的数得： 1P1+2P2+mPm=0 (1.13) 式(1.11)+(1.13)得： (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 式(1.11)-(1.13)得： (x1-1)P

12、1+(x2-2)P2+(xm-m)Pm=b 令：X(1)=(x1+1),(x2+2),(xm+m),0,0 X(2)=(x1-1),(x2-2),(xm-m),0,0 又可以这样来选取，使得对所有i=1,2,m有 x11 0 由引X(1)C,X(2) C,又X=X(1)/2+X(2)/2 即X不是可行域的顶点。 （2）X不是可行域顶点 X不是基可行解 不失一般性，设X=(x1,x2,xr,0,0)不是可 行域的顶点，因而可以找到可行域内另外两 个不同点Y和Z， 有 X=Y+(1-)Z (01)，或可写成 xj= yj+(1- )zj (0 0,1- 0,故当xj=0时,必有yj=zj=0 因有

13、 bxPxP r j jj n j jj 11 故有 )15.1 ( )14.1 ( 11 11 bzPzP byPyP r j jj n j jj r j jj n j jj 式(1.14)-式(1.15)得0)( 1 j r j jj Pzy 因(yj-zj)不全为零,故p1,pr线性相关,即X不是基可行解 定理定理3 若线性规划问题有最优解，一定存在 一个基可行解是最优解。 证 设X(0)=(x10,x20,xn0)是线性规划的一个 最优解, n j jj xcCXZ 1 0)0( 是目标函数的最大值.若X(0)不是基可行解,由定理2 知X(0)不是顶点,一定能在可行域内找到通过X(0)

14、的直 线上的另外两个顶点(X(0)+)0和(X(0) -)0.将 这两个点代入目标函数有 CCXXC CCXXC )0()0( )0()0( )( )( 因CX(0)为目标函数的最大值,故有 CCXCX CCXCX )0()0( )0()0( 由此C=0,即有C(x(0)+)=CX(0)=C(X(0)- )。如果 (x(0)+)或(x(0)-)仍不是基可行 解,按上面的方法继续做下去,最后一定可以 找到一个基可行解,其目标函数值等于CX(0), 问题得证。 四、单纯形法迭代原理 1 确定初始基可行解 )17.1(),.,1(0 )16.1( . max 1 1 njx bxP ts xcz j

15、 n j jj n j jj )18.1( 100 010 001 ),( 21 m PPP 在约束条件(1.16)式的变量的系数矩阵中总会 存在一个单位矩阵 基可行解：X=(x1,xm,xm+1,xn)T=(b1,bm,0,.,0)T 2 从一个基可行解转换为相邻的基可行解。 定义：两个基可行解称为相邻的，如果它们 之间变换且仅变换一个基变量。 设初始基可行解中的前m个为基变量，即 X(0)=(x10,x20,xm0,0,0)T 代入约束条件(1.16)有 )19.1( 1 0 bxP m i ii 写出式(1.19)系数的增广矩阵 因P1,Pm一个基，其他向量Pj可用这个基的 线性组合来表

16、示，有 mmnmjmm njm njm njmm baaa baaa baaa bPPPPPP 1, 2221,2 1111,1 121 100 010 001 )20.1(0 1 1 m i iijj m i iijj PaP PaP 或 将(1.20)式乘上一个正的数0得 （1.19)式+(1.21)式并经过整理后有 )21.1(0)( 1 m i iijj PaP T mjmj n j jj j m i iij o i axaxX XbxP bPPax )0,0,( )22.1( )22.1()( 0 1 0 1 )1( )1( 1 1 的另一个点 式找到满足约束方程组由 要使X(1)是

17、一个基可行解，因规定0，故应对所有 i=1,m，存在 令这m个不等式至少有一个等号成立。因为 aij0时，(1.23)式显然成立，故可令 )23.1(0 0 iji ax )(0 )(0 )24.1( )24.1(0|min 0 00 li li ax a x a a x iji lj l ij ij i i 由式 故X(1)是一个可行解。 又因与变量x11,x1l-1,x1l, x1l+1,xm,xj对应的向量， 经重新排列后加上b列有如下形式的增广矩阵。 bPPPPPP mljl 1121 mmj ljl llj ljl j j ba ba ba ba ba ba 10000 01000 00000 00100 00010 00001 11 11 22 11 因alj0，故由上述矩阵元素组成的行列式不为零， P1,P2,Pl-1,Pj,Pl+1,Pm是一个基。在上述增广矩阵 中进行行的初等变换，将第l行乘上(1/alj)，再分别乘以 (-aij)(i=1,k,l-1,l+1,m)加到各行上去，则增广矩阵 左半部变成为单位矩阵，又因bl/alj=，故 X(1)=(b1-a1j,bl-1- al-1,j,bl+1- al+1,j,bm- amj)T 由此X(1)是同X(0)相邻的基可行解，且由基向量组成的矩