第1章 线性规划及单纯形法精选文档.ppt

《第1章 线性规划及单纯形法精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 线性规划及单纯形法精选文档.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 线性规划及单纯形法本讲稿第一页，共三十六页（1）可行解：满足上述约束条件(1.7),(1.8)的解X=(x1,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。（2）最优解：使目标函数(1.6)达到最大值的可行解称为最优解。（3）基：设A为约束方程组(1.7)的mn阶系数矩阵，（设nm），其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设本讲稿第二页，共三十六页B中的每一个列向量Pj(j=1,m)称为基向量，与基向理Pj对应的变量xj称为基变量。线性规划中除基变量以外的变量称为非基变量。本讲稿第三页，共三十六页（4）基解：在约束方程

2、组(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，故基解的总数不超过Cnm个。（5）基可行解：满足变量非负约束条件(1.8)的基解称为基可行解。（6）可行基：对应基可行解的基称为可行基。本讲稿第四页，共三十六页可行解基解基可行解（二）可行解、基解与基可行解的关系本讲稿第五页，共三十六页线性规划的基矩阵、基变量、非基变量=目标函数约束条件行列式

3、0基矩阵右边常数（三）线性规划的基本概念的直观描述本讲稿第六页，共三十六页（四）求出下列线性规划问题的所有基解、基可行解该线性规划问题的标准型为：本讲稿第七页，共三十六页基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基可行解，表示可行域的一个极点。目标函数值为：z=20本讲稿第八页，共三十六页基变量x1、x2、x4，非基变量x3、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基可行解，表示可行域的一个极点。目标函数值为：z=18本讲稿第九页，共三十六页基变量x1、x

4、2、x5，非基变量x3、x4、x6基解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基解，但不是可行解，不是一个极点。本讲稿第十页，共三十六页基变量x1、x2、x6，非基变量x3、x4、x5基解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基可行解，表示可行域的一个极点。目标函数值为：z=18本讲稿第十一页，共三十六页基变量x2、x3、x4，非基变量x1、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基解，但不是可行解。本讲稿第十二页，共三十六页基变量x1、x2、x3，非基变量x4、x5、x

5、6基解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基可行解，表示可行域的一个极点。目标函数值为：z=15本讲稿第十三页，共三十六页基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基解但不是可行解。本讲稿第十四页，共三十六页例：设有一标准的线性规划问题的约束条件如下：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(4)(2.5,2,1,0)T,(

6、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（

7、0 1），则称X是凸集C的顶点。本讲稿第十八页，共三十六页三、几个定理的证明定理定理1 若线性规划问题存在可行解，则问题的可行域是凸集。证：设C为满足约束条件的集合，X1=（x11,x12,x1n)T,X2=(x21,x22,x2n)T为C内任意两点，即X1C，x2C，将X1，X2代约束条件有：X1，X2连线上任意一点可以表示为：本讲稿第十九页，共三十六页将（1.9）代入（1.10）得：即：本讲稿第二十页，共三十六页引理引理 线性规划问题的可行解X=（x1,x2,xn)为基可行解的充要条件是X的正分量所对应的系数列向量线性独立的。证：（1）必要性（结论条件）由基可行解的定义显然成立。（2）充分

8、性。（条件结论）若向量P1,P2,Pk线性独立，则必有km.当k=m时，它们恰好构成一个基，从而X=(x1,x2,xm,0,0,.,0)为相应的基可行解。当Km时，则一定可以从其余列向量中找出(m-k)个与P1,P2,Pk构成一个基，其对应的解恰为X，所以根据定义它是基可行解。本讲稿第二十一页，共三十六页定理定理2 线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。证：即要证明X是可行域顶点X是基可行解反证法，即X不是可行域顶点X不是基可行解（1）X不是基可行解 X不是可行域顶点不失一般性，设X的前m个分量为正，即：由引理知P1,P2,Pm线性相关，即存在一组不全为零的数i(i=1

9、,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)P1+(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)/

10、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因有本讲稿第二十四页，共三十六页故有式(1.14)-式(1.15)得因(yj-zj)不全为零,故p1,pr线性相关,即X不是基可行解本讲稿第二十五页，共三十六页定理定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解。证 设X(0)=(x10,x20,xn0)是线性规划的一个最优解,是目标函数的最大值

11、.若X(0)不是基可行解,由定理2知X(0)不是顶点,一定能在可行域内找到通过X(0)的直线上的另外两个顶点(X(0)+)0和(X(0)-)0.将这两个点代入目标函数有本讲稿第二十六页，共三十六页因CX(0)为目标函数的最大值,故有由此C=0,即有X(x(0)+)=CX(0)=X(X(0)-)。如果(x(0)+)或(x(0)-)仍不是基可行解,按上面的方法继续做下去,最后一定可以找到一个基可行解,其目标函数值等于CX(0),问题得证。本讲稿第二十七页，共三十六页四、单纯形法迭代原理1 确定初始基可行解在约束条件(1.16)式的变量的系数矩阵中总会存在一个单位矩阵基可行解：X=(x1,xm,xm

12、+1,xn)T=(b1,bm,0,.,0)T本讲稿第二十八页，共三十六页2 从一个基可行解转换为相邻的基可行解。定义：两个基可行解称为相邻的，如果它们 之间变换且仅变换一个基变量。设初始基可行解中的前m个为基变量，即 X(0)=(x10,x20,xm0,0,0)T代入约束条件(1.16)有写出式(1.19)系数的增广矩阵本讲稿第二十九页，共三十六页因P1,Pm一个基，其他向量Pj可用这个基的线性组合来表示，有将(1.20)式乘上一个正的数0得本讲稿第三十页，共三十六页（1.19)式+(1.21)式并经过整理后有要使X(1)是一个基可行解，因规定0，故应对所有i=1,m，存在本讲稿第三十一页，共

13、三十六页令这m个不等式至少有一个等号成立。因为aij0时，(1.23)式显然成立，故可令故X(1)是一个可行解。又因与变量x11,x1l,x1l-1,x1l+1,xm,xj对应的向量，经重新排列后加上b列有如下形式的增广矩阵。本讲稿第三十二页，共三十六页因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)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。3.最优性检验和解的判别将基可行解X(0)和X(1)分别代入目标函数得本讲稿第三十四页，共三十六页3 最优性检验和解的判别（1）当所有的j0时，该顶点是最优解。（2）当所有的j0，又对某个非基变量xj有cj-zj=0，有无穷多解。（3）如果存在某个j 0，又Pj0，有无界解。本讲稿第三十五页，共三十六页作业：P45（1）1.9（2）1.10本讲稿第三十六页，共三十六页