线性规划讲义课件.ppt

《线性规划讲义课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.3单纯形法1、线性规划的标准型．目标函数max．变量非负．约束条件等式．约束常数非负(1)、简缩形式a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmxj0(j=1,2,…,n)其中bi0(i=1,…,m)maxS=c1x1+c2x2+…+Cnxn可有如下三种形式:(2)、矩阵形式x1X=x2xn…b1b=b2bm…C=(C1C2…Cn)a11a12………a1n其中A=a21a22………a2n…………………

2、am1am2………amnm×nP1P2………PnmaxS=CXAX=bX0x1AX=(P1P2…Pn)x2=bxn…P1x1+P2x2+…+Pnxn=b(3)、向量形式(1)minS=CXL.P问题数学模型的标准化令Sˊ=-S得到：maxSˊ=-CX(2)约束条件例minS=40x1+50x2x1+2x2303x1+2x2602x224x1,x2,x30令Sˊ=-S得maxSˊ=-40x1–50x2+0x3+0x4+0x5松弛变量剩余变量x1+2x2+x3=303x1+2x2+x4=602x2+

3、－x5=24x1,…,x50(3)变量3x1'–3x1"+2x28x1'-x1"–4x214x1',x1",x20例3x1+2x28x1–4x214x20令x1=x1'-x1"若xj0,令xj=-xjˊ,其中:xjˊ0若xj是无限制变量.令xj=xjˊ-xj〞,其中:xjˊ、xj〞0解：①令x3=x4-x5②添加松弛变量x6③添加剩余变量x7④令S'=-SmaxS'=x1–2x2+3x4–3x5x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,…,x7

4、0将minS=-x1+2x2–3x3x1+x2+x37x1-x2+x32x1，x20，x3无限制化为标准型例8例9对例1的L.P问题进行标准化maxS=40x1+50x2x1+2x2≤303x1+2x2≤602x2≤24x1，x20maxS=40x1+50x2x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1，…，x50(m

5、基阵—A中一个子矩阵B是可逆矩阵，则方阵B称为LP问题的一个基。a11…a1ma1m+1…a1na21…a2ma2m+1…a2n………………………am1…ammamm+1…amnPm+1…PnP1…PmBNA=[BN]A=(P1…PmPm+1…Pn)=(BN)…X=x1…xmxm+1…xn定义：基向量非基向量=(XBXN)T有：AX=P1x1+P2x2+…+Pnxn=b定义：基变量非基变量BXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXNS=CBB-1b+(CN-CBB-1N)XNAX=b求

6、解A=(BN)X=(XBXN)TXBXN(BN)=bTTAX=b的求解若令非基变量xm+1=···=xn=0,用高斯消元法可求出LP标准型的一个解X=(x1x2···xm0···0)T称X为基本解.这个解的非0分量的数目不大于方程个数m.P1x1+…+Pmxm+Pm+1xm+1+…+Pnxn=bAX=b的求解BXB=b-NXN三种形式XB=B-1b定义2基本解：对应于基B，X=为AX=b的一个解。B-1b0定义3基本可行解——基B，基本解X=若B-1b0可行基:对应于基本可行解的基B。B-1b0※基本解

7、中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!可行解基本解定义4最优基本可行解最优基x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50maxS=40x1+50x2(1)写出它的矩阵形式；(2)判断(P3P4P5)是否为基阵,若是基阵,写出该基阵对应的基变量；(3)根据（2）中的基阵，用非基变量表示基变量；(4)根据（2）中的基阵，求出该问题的一个基本解，并判断是否为基可行解，同时求出对应的目标函数值；(5)将(3)中的基变量代入目标方程，并判断目

8、标函数有没有达到最优.例10–对例9的线性规划问题标准形式判断∵40>0∴X不是X=(0126360)TS=600B=(P3P4P2)行列式＝２x3=6-x1+x5x4=36-3x1+x5x2=12-1/2x5(6,12)A0(0,0)x2x1DCB(0,12)(15,7.5)S=600+40x1–25x5S=40x1+50x23、单纯形算法单纯形算法的基本思路:根据LP问题的标准型某个基可行解(顶点)开始,转换到另一个基可行