线性规划求解演示文稿

线性规划求解演示文稿99/081*当前1页，总共46页。（优选）线性规划求解99/082*当前2页，总共46页。（4）基：设A为线性规划模型约束条件系数矩阵（mn，m<n），而B为其mm子矩阵，若|B|≠0，则称B为该线性规划模型的一个基。（5）基变量：基中每个向量所对应的变量称为基变量。（6）非基变量：模型中基变量之外的变量称为非基变量。（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n

aijxj=bi(i=1,2,……,m)得到的一组解。

j=1（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。（9）可行基：对应于基可行解的基称为可行基。99/083*当前3页，总共46页。Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0

Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。设B=

1001，令，则|B|=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基变量令B=1110

x1x3

，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化99/084*当前4页，总共46页。复习思考题：

1.可行解和可行域有怎样的关系？

2.一个标准化LP模型，最多可有多少个基？

3.基解是如何定义的？怎样才能得到基解？

4.可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？

5.什么是可行基？99/085*当前5页，总共46页。1.2

线性规划问题的图解方法*利用作图方法求解。例：maxz=2x1+3x2 s.t2x1+2x212----------①

x1+2x28----------② 4x116----------③ 4x212----------④ x10,x20

99/086*当前6页，总共46页。x1x222468460①②④③Z=6Z=0(4,2)Zmax99/087*当前7页，总共46页。AAB唯一解无穷多解无界解无可行解99/088*当前8页，总共46页。步骤：（1）作平面直角坐标系，标上刻度； （2）做出约束方程所在直线，确定可行域； （3）做出一条目标函数等值线，判定优化方向； （4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。讨论一：模型求解时，可得到如下几种解的状况： （1）唯一最优解：只有一点为最优解点，简称唯一解； （2）无穷多最优解：有许多点为最优解点，简称无穷多解； （3）无界最优解：最优解取值无界，简称无界解 ； （4）无可行解：无可行域，模型约束条件矛盾。讨论二：LP模型求解思路： （1）若LP模型可行域存在，则为一凸形集合； （2）若LP模型最优解存在，则其应在其可行域顶点上找到； （3）顶点与基本解、基本可行解的关系：99/089*当前9页，总共46页。复习思考题：1.LP模型的可行域是否一定存在?2.图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3.LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？为什么？99/0810*当前10页，总共46页。1.3

单纯形法的基本原理（SimplexMethod）

两个概念： （1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称C为凸集。

或者，任给X1C，X2C，X=X1+(1-)X2

C(0<<1)，则C为凸集。凸集非凸集99/0811*当前11页，总共46页。（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。或者，

设C为凸集，对于XC，不存在任何X1C，X2C，且X1≠X2，使得X=X1+(1-)X2C，(0<<1)，则X为凸集顶点。XXXXX99/0812*当前12页，总共46页。定理1：若线性LP模型存在可行解，则可行域为凸集。证明：设maxz=CX st. AX=b X0并设其可行域为C，若X1、X2为其可行解，且X1≠X2，则X1C，X2C，即AX1=b，AX2=b，X10，X20，又X为X1、X2连线上一点，即X=X1+(1-)X2C，(0<<1)，∴AX=AX1+(1-)AX2=b+(1-)b=b,(0<<1)，且X0，

∴XC，

∴C为凸集。

三个基本定理：99/0813*当前13页，总共46页。引理：线性规划问题的可行解X=(x1,x2,······,xn)T为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。证：（1）必要性：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为基本可行解。当k<m时，则必定可再找出m-k个列向量与P1,P2,······,Pk一起构成基，∴X为基本可行解。99/0814*当前14页，总共46页。证：用反证法X非基本可行解X非凸集顶点（1）必要性：X非基本可行解X非凸集顶点不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解，∵X为可行解，∴pjxj=b，j=1n即

pjxj=b······(1)j=1m又

X是非基本可行解，∴P1,P2,······,Pm线性相关，即有1P1+2P2+······+mPm=0，其中1，2，······，m不全为0，两端同乘≠0，得1P1+2P2+······+mPm=0，······（2）定理2：线性规划模型的基本可行解对应其可行域的顶点。99/0815*当前15页，总共46页。由(1)+(2)得(x1+1)P1+(x2+2)P2+······+(xm+m)Pm=b由(1)-(2)得(x1-1)P1+(x2-

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非凸集顶点。99/0816*当前16页，总共46页。（2）充分性：X非凸集顶点X非基本可行解设X=(x1,x2,······,xr,0,0,······,0)T为非凸集顶点，则必存在Y、Z两点，使得X=Y+(1-)Z，(0<<1)，且Y、Z为可行解或者xj=yj+(1-)zj(0<<1)，（j=1,2,······,n)，yj0，zj0∵>0,1->0，当xj=0，必有yj=zj=0∴

pjyj=j=1n

pjyj=b······(1)j=1r

pjzj=j=1n

pjzj=b······(2)j=1r

(yj-zj)pj=0j=1r,(1)-(2),得即(y1-z1)P1+(y2-z2)P2+······+(yr

-zr)Pr=099/0817*当前17页，总共46页。∵Y、Z为不同两点，∴yj-zj不全为0，∴

P1,P2,······,Pr线性相关，∴X非基本可行解。99/0818*当前18页，总共46页。34O(3,3)C(4,2)662X1+2X2+X3=124X2+X5=124X1+X4=16XA=(0,3,6,16,0)TXO=(0,0,12,16,12)TXB=(3,3,0,4,0)TXC=(4,2,0,0,4)TXD=(4,0,4,0,12)TADBX1X299/0819*当前19页，总共46页。z1=CX1=CX0-C=zmax-C

，z2=CX2=CX0+C=zmax+C∵z0=zmaxz1

，z0=zmaxz2

，∴z1=z2=z0

，即X1

、X2也为最优解，若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。从而，必然会找到一个基本可行解为最优解。定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。证：设X0=(x10,x20,······,xn0)T是线性规划模型的一个最优解，

z0=zmax=CX0 若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1=X0-0

，X2=X0

+0

，即X1

、X2为可行解，99/0820*当前20页，总共46页。单纯形法的计算步骤：初始基本可行解新的基本可行解最优否？STOPYN99/0821*当前21页，总共46页。1．初始基本可行解的确定：设模型nmaxz=cjxj

j=1ns.t.aijxjbi

（i=1,2,……,m)

j=1xj0（j=1,2,……,n)

n mmaxz=cjxj+0·xsi

j=1 I=1ns.t.aijxj+xsi=bi

（i=1,2,……,m)

j=1xj0，xsi0

（j=1,2,……,n;i=1,2,……,m)化标准形∴初始基本可行解X=(0,0,······,0,b1,b2,······,bm)T，n个099/0822*当前22页，总共46页。2．从一个基本可行解向另一个基本可行解转换不失一般性，设基本可行解X0=(x10,x20,······,xm0,0,······,0)T，前m个分量为正值，秩为m，其系数矩阵为P1P2……PmPm+1……Pj……Pnb10……0 a1,m+1·····a1j

·····a1n

b1

0

1……0 a2,m+1·····a2j

·····a2n b200……1 am,m+1·····amj

·····amn

bm…………………………………………………………∴

pjxj0=j=1n

pixi0=b······(1)i=1m99/0823*当前23页，总共46页。又P1P2……Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即

Pj

=a1jP1+a2jP2+······+amj

Pm ，即

Pj

=

aij

pi

，

移项，两端同乘>0，有(Pj-

aij

pi

)=0·········(2)i=1mi=1m(1)+(2)：(xi0-

aij)Pi+

Pj=b，取充分小，使所有xi0-

aij

0，从而i=1mX1=(x10-

a1j

,x20-

a2j,······,xm0-

amj,0,······,,······,0)T也是可行解。当取

=min—aij

>0=—，则X1的前m个分量至少有一个xL1为0。xi0aijaljxL0i∴P1

,P2,······,PL-1,PL+1,······Pm,Pj线性无关。99/0824*当前24页，总共46页。∴X1

也为基本可行解。3.最优解的判别依题义z0=cjxj0

=cixi0

i=1mj=1nz0=cjxj1

=ci(xi0-

aij)

+

cj

i=1mj=1n

=ci(xi0-

aij)

+(cj

-

ciaij)=z0+

ji=1mi=1m99/0825*当前25页，总共46页。因>0，所以有如下结论：(1)对所有j，当j0

，有z1z0，即z0为最优值，X0为最优解；(2)对所有j，当j0

，但存在某个非基变量k=0，则对此Pk作为新基向量得出的解X1

，应有z1=

z0，故z1

也为最优值，从而X1为最优解，且为基本可行解，∴X0、X1连线上所有的点均为最优解，因此该线性规划模型

具有无穷多解；(3)若存在某个j

0，但对应aij0，则因当时，有z1，∴该线性规划模型具有无界解。99/0826*当前26页，总共46页。1.4 单纯形法的计算及示例1.4.1单纯形法几何解释---顶点寻优例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23标准化s.tx1+x2+x3=3 x1+2x24 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）是否为最优解的判定:-----计算检验数 若

x1↑1,则

x3↓1,x4↓1,

σ1=2-（01+01）=2 σj=△z=cj-zj=cj-ciaij，称σj为检验数。x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T99/0827*当前27页，总共46页。若

x2↑1,则

x3↓1,x4↓2,

σ2=3-(01+02)=3 ****当所有检验数均有σj

0时，则为最优解。****（3）找新的顶点（基本可行解）： 直观看，x2↑1,则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，则新的基本可行解为X=(0，2，1，0)T重复上述过程，直至所有检验数

σj

0。99/0828*当前28页，总共46页。继续迭代：找新的顶点（基本可行解）： 若x1↑1,则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若

x1↑1,则

x3↓1/2,x2↓1/2,

σ1=2-（01/2+31/2）=1/2若

x4↑1,则

x3↓-1/2,x2↓1/2,

σ4=0-（0(-1/2)+31/2）=-3/2σ3=-1, σ4=-1, zmax=799/0829*当前29页，总共46页。①②O

C

A

BX1X2(0,2)(3,0)(2,1)3499/0830*当前30页，总共46页。Cj→x1x2x3x4XBbCB1 1 1 01 2 012 3 0 034x3x400cj-zj23003/1=34/2=21/2 0 1 -1/21/2 1 01/2x3x212cj-zj1/2 00-3/203241 0 2 -10 1 -11x1x221cj-zj0 0 -1 -1231.4.2单纯形法计算：θi99/0831*当前31页，总共46页。单纯形法计算过程总结：（1）化标准形，列初始单纯形表；（2）计算检验数：σj=△z=cj-zj=cj-ciaij（3）最优性判断：当所有检验数均有σj

0时，则为最优解。否则 迭代求新的基本可行解。（4）迭代： 入基变量：取max{σj0}=

σk→xk 出基变量：取min{θi=bi/aikaik>0}=θl

→x(l)

主元素：[alk] 新单纯表：pk=单位向量注：当所有检验数σj

0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。i=1m99/0832*当前32页，总共46页。例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23标准化s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)

maxz=-2x1-3x2+0x3-Mx4-Mx5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) 引进人工变量，及M——非常大正系数，模型转变为这种处理方法称为大M法，以下则可完全按单纯形法求解。1．大M法1.5单纯形法进一步讨论99/0833*当前33页，总共46页。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

-2 -3 0 -M-M

34x4x5-M-Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj-1/2+M/2

0-M

0

3/2-M/2-M-3241 0 -2 2-10 1 1-11x1x221cj-zj0 0 -1 1-M1-M-2-3θix5099/0834*当前34页，总共46页。说明：

当所有j0

，但存在人工变量x人=0，则可以判定该模型有无可行解。采用大M法求解线性规划模型时，如果模型中各个系数与M的值非常接近时，若手工计算时，不会出现任何问题。如果利用计算机程序求解，则大M表现为一个较大的数字，由于综合计算的影响，导致检验数出现符号误差，引起判断错误，从而使大M方法失效。在这种情况下，可采用下面的两阶段法进行计算。99/0835*当前35页，总共46页。2．两阶段法：

例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23标准化s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)

obj:maxz=-x4-x5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) (1)

第一阶段，构造判断是否存在可行解的模型：

用单纯形法求解，若zmax=0，表明该模型有可行解，则可进入第二阶段，求原模型最优解。99/0836*当前36页，总共46页。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

0 0 0 -1-1

34x4x5-1-1cj-zj2

3-103/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj

1/20-101-10241 0 -2 2-10 1 1-11x1x221cj-zj0 0 0 -1-100θix5099/0837*当前37页，总共46页。

(2)第二阶段，将原目标函数引入最终单纯形表，继续迭代：

maxz=-2x1-3x2+0x3Cj→x1x2x3XBbCB11 0 0 0 -1

-2 -3 0 21x1x2-2-3cj-zj0

0-199/0838*当前38页，总共46页。1.4.3程序求解（1）用LINDO软件求解（2）用EXCEL工具求解使用EXCEL中数据处理工具———规划求解。99/0839*当前39页，总共46页。1.6改进单纯形法单纯形法迭代过程可用矩阵变换描述如下：设

maxz=CXst AXb X0分解

maxz=CBXB+CNXN+0XSst BXB+NXN+IXS=b XB,XN,,XS0约束方程两端同乘B-1，则可得如下表达式：式中，B——最终表中基对应的矩阵，

N——初始表与最终表中均为非基对应的矩阵，

I——单位矩阵A=[BN]

maxz=CBXB+CNXN+0XSst B-1BXB+B-1NXN+B-1XS=B-1

b XB,XN,,XS0——对应最终单纯形表的模型99/0840*当前40页，总共46页。用单纯形表表示如下：XS=bB N IXB=b´I N´

B-1初始表

XB

XN

XS

cj-zj0,······,0

N

S最终表

XB

XN

XS

cj-zj

B

N 0,······,0表中，b´=B-1bN´=B-1N

或者Pj´=B-1PjN´=CN-CBB-1

N或者j´=Cj-CBB-1

PjS´=-CBB-1········99/0841*当前41页，总共46页。⑴化标准形：B-1

new

=I，XB=b，⑵求检验数：N

=CN-CBB-1

new

N，S

=-CBB-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为换出变量，⑸令改进单纯形法计算步骤：99/0842*当前42页，总共46页。D=1·······-a1k/aLk······00·······1/aLk······00·······-amk