第一章 线性规划求解(4).ppt

1、2006/08,-第 1 章 线性规划-,-1-,线性规划的求解Linear Programming,二维线性规划的图解法,2. 线性规划的单纯形法,2006/08,-第 1 章 线性规划-,-2-,1.1.4线性规划问题解的有关概念,设模型 n max z=cjxj j=1 n s.t. aijxj=bi （i=1,2,m) j=1 xj0 （j=1,2,n),（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的取值。,（2）可行域：全部可行解的集合称为可行域。,（3）最优解：使目标函数达到最优值的可行解。,2006/08,-第 1 章 线性规划-,-3-,（4）基：设A为线性规划模

2、型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。,（5）基变量：基中每个向量所对应的变量称为基变量。,（6）非基变量：模型中基变量之外的变量称为非基变量。,（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n aijxj =bi (i=1,2,m)得到的一组解。 j=1,（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。,（9）可行基：对应于基可行解的基称为可行基。,2006/08,-第 1 章 线性规划-,-4-,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Ma

3、x z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,设,B=,1 0 0 1,，令,，则,| B |=10,令 x1=x2 =0，则 x3 =3, x4=4，X=(0,0,3,4)T,例：,x3 x4,基变量,令,B=,1 1 1 0,x1 x3,，则,令 x2=x4 =0，则 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基本可行解,基本可行解

4、,标准化,2006/08,-第 1 章 线性规划-,-5-,复习思考题： 1. 可行解和可行域有怎样的关系？ 2. 一个标准化LP模型，最多可有多少个基？ 3. 基解是如何定义的？怎样才能得到基解？ 4. 可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？ 5. 什么是可行基？,2006/08,-第 1 章 线性规划-,-6-,1.2线性规划问题的图解方法,* 利用作图方法求解。 例：max z=2x1+3x2 s.t 2x1+2x212 - x1+2x2 8 - 4x116 - 4x2 12 - x10, x20,2006/08,-第 1 章 线性规划-,-7-,x1,x2

5、,2,2,4,6,8,4,6,0,Z=6,Z=0,(4,2),Zmax,2006/08,-第 1 章 线性规划-,-8-,A,A,B,唯一解,无穷多解,无界解,无可行解,2006/08,-第 1 章 线性规划-,-9-,步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。,讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3）无界最优解：最优解取值无界，

6、简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。,讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：,2006/08,-第 1 章 线性规划-,-10-,复习思考题： 1. LP模型的可行域是否一定存在? 2. 图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？ 3. LP模型的可行域的顶点与什么解具有对应关系？ 4. 你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？,2006/08,-第 1 章 线性规划-,-11-

7、,1.3单纯形法的基本原理（Simplex Method）,1.3.1 两个概念： （1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称 C为凸集。,或者，任给X1C，X2 C，X=X1+ (1-)X2 C (01)，则C为凸集。,凸集,非凸集,2006/08,-第 1 章 线性规划-,-12-,（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。,或者， 设C为凸集，对于XC，不存在任何X1C，X2 C， 且X1X2，使得X=X1+(1-)X2C， (01)，则X为凸集顶点。,X,X,X,X,X,2006/08,-第 1 章 线性规划-,-13-,定理1：若线性LP模型存在可行

8、解，则可行域为凸集。,证明：设 max z=CX st.AX=b X0,并设其可行域为C，若X1、X2为其可行解，且X1X2 ， 则 X1C，X2 C， 即AX1=b，AX2=b，X10，X20，,又 X为X1、X2连线上一点，即 X=X1+(1-)X2C， (01)， AX=AX1+ (1-)AX2 = b+ (1-)b =b , (01)，且 X 0， X C， C为凸集。,1.3.2 三个基本定理：,2006/08,-第 1 章 线性规划-,-14-,引理：线性规划问题的可行解X=(x1, x2,xn)T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。,证： （1）必要性

9、：X基本可行解X的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由基本可行解定义可知x1, x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。,（2）充分性： X的正分量所对应的系数列向量线性独立 X为基本可行解 若A的秩为m，则X的正分量的个数km； 当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基， X为基本可行解。 当km时，则必定可再找出m-k个列向量与P1,P2,Pk一起构成基， X为基本可行解。,2006/08,-第 1 章 线性规划-,-15-,证：用反证法 X非基本可行解X非凸集顶点 （1）必要

10、性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解， X为可行解，, pjxj=b，,j=1,n,即 pjxj=b (1),j=1,m,又 X是非基本可行解， P1,P2,Pm线性相关，即有 1P1+2P2+mPm=0， 其中1，2，m不全为0，两端同乘0，得 1P1+2P2+mPm=0，（2）,定理2：线性规划模型的基本可行解对应其可行域的顶点。,2006/08,-第 1 章 线性规划-,-16-,由 (1)+(2)得 (x1+ 1)P1+ (x2+ 2)P2+ (xm+ m)Pm=b 由 (1)-(2)得 (x1 -1)P1+ (x2 -

11、 2)P2+ (xm -m)Pm=b,令X1=(x1+ 1，x2+ 2，xm+ m，0， ，0)T X2=(x1- 1，x2- 2，xm- m ，0，0)T 取充分小,使得 xj j0， 则 X1、X2均为可行解， 但 X=0.5X1+(1-0.5)X2， X是X1、X2连线上的点， X非凸集顶点。,2006/08,-第 1 章 线性规划-,-17-,（2）充分性： X非凸集顶点 X非基本可行解,设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使得,X=Y+(1-)Z，(01)，且Y、Z为可行解 或者 xj=yj+(1-)zj (01)，（j=1,2,n)， yj0，

12、zj0, 0, 1-0 ，当xj=0， 必有yj=zj=0, pjyj =,j=1,n, pjyj=b (1),j=1,r, pjzj =,j=1,n, pjzj=b (2),j=1,r, (yj-zj)pj=0,j=1,r,(1)-(2),得,即,(y1 - z1)P1+ (y2 - z2)P2+ (yr -zr)Pr=0,2006/08,-第 1 章 线性规划-,-18-, Y、Z为不同两点， yj-zj不全为0， P1,P2,Pr线性相关， X非基本可行解。,2006/08,-第 1 章 线性规划-,-19-,3,4,O,(3,3),C (4,2),6,6,2X1+2X2+X3=12,4

13、X2+X5=12,4X1+X4=16,XA=(0,3,6,16,0)T,XO=(0,0,12,16,12)T,XB=(3,3,0,4,0)T,XC=(4,2,0,0,4)T,XD=(4,0,4,0,12)T,A,D,B,X1,X2,2006/08,-第 1 章 线性规划-,-20-,z1=CX1=CX0-C=zmax-C ，z2=CX2=CX0+C =zmax+C z0 = zmax z1 ， z0 = zmax z2 ， z1 = z2 = z0 ，即 X1 、 X2也为最优解， 若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。 从而，必然会找到一个基本可行解为最优解。,定理3

14、：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,证：设 X0=(x10, x20,xn0)T 是线性规划模型的一个最优解， z0=zmax=CX0 若X0非基本可行解，即非顶点，只要取充分小， 则必能找出X1= X0-0 ，X2 = X0 +0 ，即X1 、 X2为可行解，,2006/08,-第 1 章 线性规划-,-21-,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,2006/08,-第 1 章 线性规划-,-22-,1初始基本可行解的确定：,设模型 n max z=cjxj j=1 n s.t. aijxjbi （i=1,2,m) j=1

15、 xj0 （j=1,2,n),n m max z=cjxj + 0 xsi j=1 I=1 n s.t. aijxj+xsi=bi （i=1,2,m) j=1 xj0， xsi0 （j=1,2,n; i=1,2, ,m),化标准形,初始基本可行解 X=(0,0,0, b1,b2,bm)T，,n个0,2006/08,-第 1 章 线性规划-,-23-,2从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解X0=(x10, x20,xm0,0,0)T ， 前m个分量为正值，秩为m，其系数矩阵为,P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1

16、 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm, pjxj0 =,j=1,n, pixi0=b (1),i=1,m,2006/08,-第 1 章 线性规划-,-24-,又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即 Pj = a1j P1 + a2j P2 + amj Pm ，即 Pj = aij pi ， 移项，两端同乘0 ，有 (Pj- aij pi )=0 (2),i=1,m,i=1,m,(1)+(2)： (xi 0- aij)Pi + Pj =b， 取充分小，使所有xi 0 - aij 0，从而,i=

17、1,m,X1 = (x1 0- a1j ,x2 0- a2j ,xm 0- amj ,0,0)T,也是可行解。,当取 = min aij 0 = ，则X1的前m个分量至少有一个xL1为0。,xi 0,aij,alj,xL 0,i, P1 , P2,PL-1, PL+1, Pm, Pj 线性无关。,2006/08,-第 1 章 线性规划-,-25-, X1 也为基本可行解。,3.最优解的判别,依题义,z0 = cjxj0 =ci xi0,i=1,m,j=1,n,z0 = cjxj1 =ci(xi 0- aij) + cj ,i=1,m,j=1,n,=ci(xi 0- aij) + (cj - c

18、iaij)= z0 + j,i=1,m,i=1,m,2006/08,-第 1 章 线性规划-,-26-,因0，所以有如下结论：,(1) 对所有j，当 j0 ，有z1 z0 ，即z0为最优值，X0为最优解； (2) 对所有j，当j0 ，但存在某个非基变量k=0，则对此Pk作 为新基向量得出的解X1 ，应有z1 = z0 ，故z1 也为最优值， 从而 X1为最优解，且为基本可行解， X0、X1 连线上所有的点均为最优解，因此该线性规划模型 具有无穷多解； (3) 若存在某个j 0，但对应aij0，则因当 时，有z1 ， 该线性规划模型具有无界解。,2006/08,-第 1 章 线性规划-,-27-

19、,1.4单纯形法的计算及示例,1.4.1 单纯形法几何解释-顶点寻优 例： max z=2x1+3x2 max z=2x1+3x2+0 x3 +0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10, x20 xj0, (j=1,2,3,4),（1）初始基本可行解的选择：-坐标原点处,令 x1 =x2 =0,由 x1+x2+x3=3 x1+2x2+x4=4,（2）是否为最优解的判定:-计算检验数,若 x11, 则 x31, x41, 1= 2-（01+01）=2 j =z=cj-zj = cj-ciaij ，称 j为检验数。,x3

20、=3 -(x1+x2) x4=4 -(x1+2x2),解得 X=( 0,0,3,4 )T,2006/08,-第 1 章 线性规划-,-28-,若 x21, 则 x31, x42, 2=3-(01+02)=3,* 当所有检验数均有j 0时，则为最优解。*,（3）找新的顶点（基本可行解）：直观看，x21, 则 z 3， 应找A点，即增加x2。,x2 可增加多少？需要保证 x3=3 -(x1+x2)0 x4=4 -(x1+2x2)0 ，, x2 = min（3/1，4/2），从而 x3=1 -(x1 / 2 - x4 /2） x2=2 -(x1 / 2 + x4 / 2),令 x1 = x4 =0，

21、则新的基本可行解为 X=( 0，2，1，0)T 重复上述过程，直至所有检验数 j 0。,2006/08,-第 1 章 线性规划-,-29-,继续迭代：,找新的顶点（基本可行解）：若x11, 则 z 1/2， 应找B点，即增加x1。 x1 可增加多少？需要保证 x3=1 -(x1/2 - x4 /2)0 x2=2 -(x1/2+x4/2)0， x1 = min（2，4），从而 x1=2 -(2x3-x4) x2=1 -(-x3+x4) , 则新的基本可行解为 X=( 2，1，0，0)T,若 x11, 则 x31/2, x21/2, 1= 2-（01/2+31/2）=1/2,若 x41, 则 x3

22、-1/2, x21/2, 4= 0-（0(-1/2)+31/2）=-3/2,3 = -1, 4 = -1, zmax=7,2006/08,-第 1 章 线性规划-,-30-,O,C,A,B,X1,X2,(0,2),(3,0),(2,1),3,4,2006/08,-第 1 章 线性规划-,-31-,Cj ,x1,x2,x3,x4,XB,b,CB,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj - zj,2,3,0,0,3/1=3,4/2= 2,1/2 0 1 -1/2 1/2 1 0 1/2,x3 x2,12,cj - zj,1/2 0 0 -3/2,03,24,1

23、 0 2 -1 0 1 -1 1,x1 x2,21,cj - zj,0 0 -1 -1,23,1.4.2 单纯形法计算：,i,2006/08,-第 1 章 线性规划-,-32-,单纯形法计算过程总结：,（1）化标准形，列初始单纯形表；,（2）计算检验数： j =z=cj-zj = cj- ciaij,（3）最优性判断：当所有检验数均有j 0时，则为最优解。否则迭代求新的基本可行解。,（4）迭代：入基变量：取maxj 0 = kxk出基变量：取min i=bi/aik aik0= l x(l)主元素： alk新单纯表：pk=单位向量,注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷

24、多解，否则只有唯一最优解。,i=1,m,2006/08,-第 1 章 线性规划-,-33-,例： min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2 -x3=3 x1+2x2 = 4 x1+2x2=4 x10, x20 xj0, (j=1,2,3,4),max z=-2x1-3x2+0 x3 -M x4-M x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5),引进人工变量，及M非常大正系数，模型转变为,这种处理方法称为大M法，以下则可完全按单纯形法求解。,1大M法,

25、1.5 单纯形法进一步讨论,2006/08,-第 1 章 线性规划-,-34-,Cj ,x1,x2,x3,x4,XB,b,CB,1 1 -1 1 0 1 2 0 0 1,-2 -3 0 -M -M,34,x4 x5,-M -M,cj - zj,-2+2M,-3+3M,-M,0,3/1=3,4/2= 2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x4 x2,12,cj - zj,-1/2+M/2 0 -M 0 3/2-M/2,-M -3,24,1 0 -2 2 -1 0 1 1 -1 1,x1 x2,21,cj - zj,0 0 -1 1-M 1-M,-2 -3,i,x5,0,

26、2006/08,-第 1 章 线性规划-,-35-,说明： 当所有j0 ，但存在人工变量x人=0，则可以判定该模型有无可行解。,采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近时，若手工计算时，不会出现任何问题。如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，可采用下面的两阶段法进行计算。,2006/08,-第 1 章 线性规划-,-36-,2两阶段法：,例： min z=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s.t x1+x2 -x

27、3=3 x1+2x2 = 4 x1+2x2=4 x10, x20 xj0, (j=1,2,3,4),obj: max z=-x4-x5 s.t x1+x2 -x3+ x4 =3 x1+2x2 +x5 =4 xj0, (j=1,2,3,4,5),(1) 第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解，若zmax=0 ，表明该模型有可行解，则可进入第二阶段，求原模型最优解。,2006/08,-第 1 章 线性规划-,-37-,Cj ,x1,x2,x3,x4,XB,b,CB,1 1 -1 1 0 1 2 0 0 1,0 0 0 -1 -1,34,x4 x5,-1 -1,cj - zj,2,

28、3,-1,0,3/1=3,4/2= 2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x4 x2,12,cj - zj,1/2 0 -1 0 1,-1 0,24,1 0 -2 2 -1 0 1 1 -1 1,x1 x2,21,cj - zj,0 0 0 -1 -1,0 0,i,x5,0,2006/08,-第 1 章 线性规划-,-38-,(2) 第二阶段，将原目标函数引入最终单纯形表，继续迭代： max z=-2x1-3x2+0 x3,Cj ,x1,x2,x3,XB,b,CB,1 1 0 0 0 -1,-2 -3 0,21,x1 x2,-2 -3,cj - zj,0,0,-1,2

29、006/08,-第 1 章 线性规划-,-39-,1.4.3 程序求解,（1）用LINDO软件求解,（2）用EXCEL工具求解,使用EXCEL中数据处理工具规划求解。,2006/08,-第 1 章 线性规划-,-40-,1.6 改进单纯形法,单纯形法迭代过程可用矩阵变换描述如下： 设,max z=CX stAXbX0,分解,max z=CBXB+ CNXN+0XS stBXB+ NXN+IXS=bXB , XN, , XS0,约束方程两端同乘B-1，则可得如下表达式：,式中， B最终表中基对应的矩阵， N初始表与最终表中均为非基对应的矩阵， I 单位矩阵,A= B N ,max z=CBXB+

30、 CNXN+0XS st B-1 BXB+ B-1 NXN+ B-1 XS= B-1 b XB , XN, , XS0,对应最终单纯形表的模型,2006/08,-第 1 章 线性规划-,-41-,用单纯形表表示如下：,XS = b,B N I,XB = b I N B-1,初始表 XB XN XS,cj - zj 0,0 N S,最终表 XB XN XS,cj - zj B N 0,0,表中， b =B-1b N =B-1N 或者 Pj =B-1Pj N = CN-CB B-1 N 或者j=Cj-CBB-1 Pj S = -CB B-1,2006/08,-第 1 章 线性规划-,-42-, 化

31、标准形： B-1 new =I， XB =b， 求检验数：N = CN-CB B-1 new N， S = -CB B-1 new 最优性判别： 所有 0，X人0，无可行解； 所有 0，X人=0，存在 N =0，无穷多解； 所有 0，X人=0，不存在N =0，唯一解； 否则(存在 0)，转 ， 取max xk ，为换入变量， 计算Pk = B-1 new Pk，若 Pk 0 无界解, 否则，计算i = bi /aik |aik 0 ，取min xL为换出变量， 令,改进单纯形法计算步骤：,2006/08,-第 1 章 线性规划-,-43-,D=,1 - a1k / aLk 0 0 1/ aLk

32、 0 0 - amk / aLk 1, , , ,xL,计算 B-1 new =D B-1old ， b = B-1 newb,转。,注：D矩阵为单位矩阵中出基变量所在单位向量以上述列向量代换。,实例演算如下：,2006/08,-第 1 章 线性规划-,-44-,例： max z=2x1+3x2 max z=2x1+3x2+0 x3 +0 x4 s.t x1+x23 标准化 s.t x1+x2+x3=3 x1+2x2 4 x1+2x2+x4=4 x10, x20 xj0, (j=1,2,3,4),x1x2x3 x4 b 111 0 3 120 1 4, 初始解： B-1 new=I， XB=(x3 ,，x4)T=(3，4)T, N=(1，2)=(2，3)， 计算 P2 = B-1 new P2