第二章最优化线性规划详解演示文稿

第二章最优化线性规划详解演示文稿当前1页，总共165页。优选第二章最优化线性规划当前2页，总共165页。凸集设集合D

Rn,若对于任意点x,y∈

D,及实数a,0≤a≤1,都有ax+(1-a)y∈

D,则称集合D为凸集.常见的凸集:单点集{x},空集,整个欧式空间Rn,超平面H={x∈

Rn|a1x1+a2x2+…anxn=b}，半空间H+={x∈Rn|a1x1+a2x2+…anxn≥b}，实心圆，实心球，实心长方体等都是凸集。3当前3页，总共165页。凸集从直观上看，没有凹入部分，或没有空洞的是凸集。几何解释为：集合D中任两点连线上的每一点仍在D中，则D为凸集。4当前4页，总共165页。凸集的例超球||x||≤r为凸集证明设x,y为超球中任意两点,0≤a≤1,则有||ax+(1-a)y||≤a||x||+(1-a)||y||≤a

r+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.5当前5页，总共165页。凸集的性质(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j∈

J)是凸集,则它们的交集D={x|x∈

Dj,j∈J}是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD={y|y=bx,x∈

D}.6当前6页，总共165页。凸集的性质(iii)设D1,D2是凸集,则D1与D2的和集D1+D2={y|y=x+z,x∈

D1,z∈D2}是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1={(x,0)T|x∈

R}表示x轴上的点,D2={(0,y)T|y∈R},表示y轴上的点.则D1∪D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集7当前7页，总共165页。推论凸集的线性组合是凸集.定义2.1.2设xi∈

Rn,i=1,…,k,实数li≥0,则称为x1,x2,…,xk的凸组合.容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.两点的凸组合三点的凸组合多点的凸组合8当前8页，总共165页。极点设D为凸集,x∈D.若D中不存在两个相异的点y,z及某一实数a∈(0,1)使得

x=ay+(1-a)z

则称x为D的极点.凸集极点凸集极点9当前9页，总共165页。极点例D={x∈Rn|||x||≤a}(a>0),则||x||=a上的点均为极点证明:设||x||=a,若存在y,z∈D及a∈(0,1),使得x=ay+(1-a)z.则a2=||x||2≤a2||y||2+(1-a)2||z||2+2a(1-a)||y||||z||≤a2不等式取等号,必须||y||=||z||=a,容易证明y=z=x,根据定义可知,x为极点.10当前10页，总共165页。凸函数设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,及任意的a∈

[0,1]都有

f(ax+(1-a)y)≤af(x)+(1-a)f(y)

则称函数f(x)为凸集D上的凸函数.11当前11页，总共165页。凸函数设函数f(x)定义在凸集DRn上,若对任意的x,y∈D,x≠y,及任意的a∈(0,1)都有

f(ax+(1-a)y)<af(x)+(1-a)f(y)

则称函数f(x)为凸集D上的严格凸函数.将上述定义中的不等式反向,可以得到凹函数和严格凹函数的定义.12当前12页，总共165页。凸函数的例设f(x)=(x–1)2,试证明f(x)在(–∞,+∞)上是严格凸函数.证明:设x,y∈R,且x≠y,a∈(0,1)都有f(ax+(1-a)y)-(af(x)+(1-a)f(y))

=(ax+(1-a)y-1)2-a(x-1)2-(1-a)(y-1)2=–a(1-a)(x-y)2<0因此f(x)在(–∞,+∞)上是严格凸函数.13当前13页，总共165页。凸函数的几何性质对一元函数f(x),在几何上af(x1)+(1-a)f(x2)

(0≤a≤1)表示连接(x1,f(x1)),(x2,f(x2))的线段,f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.14当前14页，总共165页。凸函数的性质(i)设f(x)是凸集DRn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数.(ii)设f1(x),f2(x)是凸集DRn上的凸函数,实数l,m≥0,则lf1(x)+mf2(x)也是D上的凸函数.(iii)设f(x)是凸集DRn上的凸函数,b为实数,则水平集S(f,b)={x|x∈D,f(x)≤b}是凸集.下面的图形给出了凸函数f(x,y)=x4+3x2+y4+y2+xy的等值线(f(x,y)=2,4,6,8,10,12)的图形.可以看出水平集为凸集.15当前15页，总共165页。凸函数的性质16当前16页，总共165页。凸函数的判断设f(x)定义在凸集DRn上,x,y∈D.令F(t)=f(tx+(1-t)y),t∈[0,1],则该定理的几何意义是:凸函数上任意两点之间的部分是一段向下凸的弧线.(i)f(x)是凸集D上的凸函数的充要条件是对任意的x,y∈D,一元函数F(t)为[0,1]上的凸函数.(ii)f(x)是凸集D上的严格凸函数的充要条件是对任意的x,y∈D(x≠y),一元函数F(t)为[0,1]上的严格凸函数.17当前17页，总共165页。凸函数的判断18当前18页，总共165页。一阶条件

(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y∈D,都有f(y)≥f(x)+f(x)T(y-x)定理2.1.3(一阶条件)设在凸集DRn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y∈D,x≠y,都有f(y)>f(x)+f(x)T(y-x)19当前19页，总共165页。二阶条件设在开凸集DRn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.20当前20页，总共165页。凸规划设DRn为凸集,则f(x)为D上的凸函数,则称规划问题

minf(x)

s.t.x∈D

为凸规划问题.(i)凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是DRn上的严格凸函数,且凸规划问题minf(x)s.t.x∈D的整体极小点存在,则整体极小点唯一.21当前21页，总共165页。§2.2线性规划的标准型

与基本概念22当前22页，总共165页。线性规划的一般形式min(max)c1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn≥(或≤,=)b1a21x1+a22x2+···+a2nxn(或≤,=)b2······am1x1+am2x2+···+amnxn(或≤,=)bmx1,x2,···,xn≥023当前23页，总共165页。线性规划的标准型minc1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2······am1x1+am2x2+···+amnxn=bmx1,x2,···,xn≥0其中bi≥0.在标准形式中目标函数一律改为最大化或最小化，此处我们统一为最小化，约束条件（非负约束条件除外）一律化成等式，且要求其右端项大于等于零。24当前24页，总共165页。矩阵-向量形式的标准型mincTx(LP)s.t.Ax=bx≥0其中c=(c1,c2,···,cn)T,x=(x1,x2,···,xn)T,b=(b1,b2,···,bm)Tc:价格向量A:约束矩阵b:右端向量25当前25页，总共165页。矩阵-向量形式的标准型记A=(p1,p2,···,pn),其中pj=(a1j,a2j,···,amj)T,线性规划(LP)又可以表示为26当前26页，总共165页。线性规划解的情况满足约束条件的向量x是可行解,全体可行解构成可行域D.D≠F

时但目标函数无下界时,称线性规划(LP)无界或无最优解;D=F

时,称线性规划无可行解;D≠F

时若目标函数有下界,可以证明线性规划(LP)必有最优解.27当前27页，总共165页。可行域为凸集线性规划问题mincTx(LP)s.t.Ax=bx≥0的可行域D为凸集.证明任取x,y∈D,则有Ax=b,x≥0,Ay=b,y≥0对任意的a∈[0,1],设z=ax+(1-a)y,则z≥0,且Az=A(ax+(1-a)y)=aAx+(1-a)Ay=ab+(1-a)b=b因此z∈DD为凸集.28当前28页，总共165页。一般形式转化为标准型(i)极大极小

maxf(x)min–f(x)(ii)若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量——称为松弛变量，将不等式改为等式。如(iii)若约束条件是大于等于型，则在该约束条件不等式左边减去一个新变量——称为剩余变量，将不等式改为等式。如29当前29页，总共165页。一般形式转化为标准型(iv)若某个约束方程右端项，则在约束方程两端乘以（-1），不等号改变方向，然后再将不等式化为等式。(v)若变量xj无非负约束，则引入非负变量xj’≥0,xj’’≥0,令xj=xj’-xj”.30当前30页，总共165页。例将线性规划miny=2x1-x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1-x2+2x3=5x1,x2≥0,x3是自由变量化为标准型解:令x3=x3’-x3’’,得到标准型miny=2x1-x2-3x3’+3x3’’s.t.x1+x2+x3’-x3’’+x4=7x1-x2+x3’-x3’’-x5=2-3x1-x2+2x3’-2x3’’=5x1,x2,x3’,x3’’,x4,x5≥031当前31页，总共165页。例将线性规划maxy=250x1+350x2s.t.5x1+6x2≥2508x1+6x2≤

30010x1+20x2=-700x1≥0,x2≤

0化为标准型解:令x2’=-x2,得到标准型min-y=-250x1+350x2’s.t.5x1-6x2’

-x3=2508x1-6x2’+x4=

300-10x1+20x2’=700x1≥0,x2’≥0,x3≥0,

x4≥032当前32页，总共165页。基本概念设约束矩阵A的秩为m(行满秩),且m≤n,则A中必存在m阶非奇异子阵B,不妨设B=(p1,p2,···,pm)称B为线性规划问题(LP)的一个基矩阵,或称为基,基矩阵中的列向量称为基向量,对应的决策变量称为基变量,其余变量称为非基变量.33当前33页，总共165页。基本概念在约束方程组取定基矩阵B=(p1,p2,···,pm)之后,令非基变量均为0,得到的方程组p1x1+p2x2+···+pmxm=b有唯一解,这样得到约束方程组的一个解向量x=(x1,x2,···xm)T通过这种方法得到的满足约束方程组的解称为基矩阵B对应的基解.34当前34页，总共165页。基本概念如果基解又满足非负条件,则称之为基可行解.此时的基B称为可行基.基可行解中非零分量的个数不会超过m,若基可行解中非零分量的个数恰为m,称此基可行解为非退化的基可行解,否则称为退化的基可行解.若一个线性规划的所有基可行解都是非退化的,称此线性规划是非退化的.线性规划(LP)的基解个数不会超过35当前35页，总共165页。例考虑线性规划min2x1-x2

s.t.x1+x2+x3=5

-x1-x2+x4=0

2x1+2x2+x5=22

x1,x2,x3,x4,x5≥0该线性规划有5个变量,3个约束,最多个基解.事实上,该线性规划只有7个基解(p1,p2线性相关)下面列出7个基解及对应的基(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p3,p4,p5),(0,0,5,0,22)T退化36当前36页，总共165页。§2.3线性规划的

基本定理37当前37页，总共165页。本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了,这样将选择的范围控制在有限个.设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x的正分量对应的系数列向量线性无关.38当前38页，总共165页。设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x为可行域D的极点.证明:

必要性不妨设x=(x1,x2,···,xm,0,···,0)T是(LP)的基可行解,且x1,x2,···,xm是基变量,假设有u,v∈D,0<a<1,使得x=au+(1-a)v当m+1≤j≤n时,0=xj=auj+(1-a)vj,因此uj=vj=0.所以p1u1+p2u2+···+pmum=p1v1+p2v2+···+pmvm=b从而p1(u1-v1)+p2(u2-v2)+···+pm(um-vm)=0由于x是基可行解,所以p1,p2,···,pm线性无关,uj=vj(i=1,2,···,m).从而u=v.这说明x为极点.39当前39页，总共165页。充分性设x=(x1,x2,···,xk,0,···,0)T是可行域的极点,其中x1,x2,···,xk>0.假设x不是基可行解,于是p1,p2,···,pk线性相关,即有一组不全为0的数a1,a2,···,ak,使得a1p1+a2p2+···+akpk=0 (2.4)又x∈D,所以x1p1+x2p2+···+xkpk=b(2.5)用e>0乘(2.4)再与(2.5)相加减得(x1+ea1)p1+(x2+ea2)p2+···+(xk+eak)pk=b(x1–ea1)p1+(x2–ea2)p2+···+(xk–eak)pk=b40当前40页，总共165页。令u=(x1+ea1,x2+ea2,···,xk+eak,0,···,0)Tv=(x1–ea1,x2–ea2,···,xk–eak,0,···,0)T则有Au=b,Av=b,当e充分小时,可使u≥0,v≥0.因此,当e充分小时,u,v都是(LP)的可行解,且u≠v,x=1/2u+1/2v,这与x是D的极点相矛盾.因此x是基可行解.推论:线性规划(LP)的可行域D={x|Ax=b,x≥0}最多具有有限个极点41当前41页，总共165页。(p1,p3,p4),(11,0,-6,11,0)T不可行(p1,p3,p5),(0,0,5,0,22)T退化(p1,p4,p5),(5,0,0,5,12)T非退化(p2,p3,p4),(0,11,-6,11,0)T不可行(p2,p3,p5),(0,0,5,0,22)T退化(p2,p4,p5),(0,5,0,5,12)T非退化(p3,p4,p5),(0,0,5,0,22)T退化前例中三个退化的基可行解对应着同一个极点(基可行解与极点不是一一对应)42当前42页，总共165页。有可行解有基可行解若线性规划(LP)存在可行解,则它一定存在基可行解.43当前43页，总共165页。有最优解有最优的基可行解若线性规划(LP)存在最优解,则必存在基可行解是最优解.44当前44页，总共165页。单纯形方法的思路找出一基可行解(极点)若其不是最优,找到一个相邻极点新的目标函数值不大于原目标函数值经过有限次迭代给出最优解或判断无最优解45当前45页，总共165页。单纯形方法的思路(几何)线性规划min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0的等价形式为min-72x1-64x2

s.t.x1+x2≤50

12x1+8x2≤490

3x1≤100

x1,x2≥046当前46页，总共165页。OABCD梯度方向x2=0x1=0x5=0x3=0x4=0等值线基可行解O47当前47页，总共165页。OABCDx2=0x1=0x5=0x3=0x4=0基可行解A48当前48页，总共165页。OABCDx2=0x1=0x5=0x3=0x4=0基可行解B49当前49页，总共165页。OABCDx2=0x1=0x5=0x3=0x4=0基可行解C是最优解50当前50页，总共165页。单纯形方法的思路(代数)例考察线性规划min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0以x3,x4,x5为基变量,容易得到基可行解(0,0,50,490,100)T.由于x1的价格系数为负数,增加x1的取值可以使得目标函数值减少.类似的,我们也可以增加x2的取值,使得目标函数值减少.由于-72负得多一些,我们先增加x1.51当前51页，总共165页。单纯形方法的思路(代数)min-72x1-64x2

s.t.x1+x2+x3=50

12x1+8x2+x4=490

3x1

+x5=100

x1,x2,x3,x4,x5≥0x1可以增加多少?x1≤50x1≤490/12x1≤100/3因此x1的最大取值为min(50,490/12,100/3)=100/3此时x5的取值为0,x5“出基”.52当前52页，总共165页。单纯形方法的思路(代数)根据3x1+x5=100,我们将原来的线性规划改写如下min-64x2+24x5-2400s.t.x2+x3-x5/3=50/3

8x2+x4-4x5=90

x1

+x5/3=100/3

x1,x2,x3,x4,x5≥0此时,基变量为x1,x3,x4,基可行解为(100/3,0,50/3,90,0)T.若x2(其系数为负)的取值增加,可以使得目标函数值减少x2≤50/3x2≤90/8因此x2的最大取值为min(50/3,90/8)=90/8x4“出基”.53当前53页，总共165页。单纯形方法的思路(代数)此时,x4,x5是非基变量,将原规划化为min8x4-8x5-3120s.t.x3-x4/8+x5/6=65/12

x2+x4/8-x5/2

=45/4

x1

+x5/3=100/3

x1,x2,x3,x4,x5≥0解为(100/3,45/4,65/12,0,0)T.x5最大可以取为65/2.对应的,线性规划可以转化为下页的形式54当前54页，总共165页。单纯形方法的思路(代数)min48x3+2x4-3380s.t.6x3-3x4/4+x5=65/2

x2+3x3-x4/4

=55/2

x1-2x3+x4/4=45/2

x1,x2,x3,x4,x5≥0对应的解为(45/2,55/2,0,0,65/2)T.此时,目标函数中非基变量的系数为正,因此目标函数的取值不能再减少.最优值为

-3380.55当前55页，总共165页。单纯形方法的思路(代数)单纯形方法求解线性规划,首先找出一个基可行解.将目标函数写成非基变量的线性组合(再加上一个常数)的形式.如果组合的系数全部非负,则已经找到最优解.如果组合的系数中有负数,从中选取一个变量(“进基”)来增加取值,可以使得函数值减少.根据约束条件,可以控制增加的范围.在进基变量取最大值时,有一个变量出基,从而得到另一个基可行解.重复上面的过程,可以求得最优解.56当前56页，总共165页。§2.4单纯形方法57当前57页，总共165页。设线性规划R(A)=m，x1,x2,…,xm是基变量，而xm+1,…,xn是非基变量，并记基矩阵B=(p1,p2,…,pm),N=(pm+1,…,pn),A=(B,N),则上述线性规划问题化为58当前58页，总共165页。进一步可以将线性规划问题转化为以下形式59当前59页，总共165页。规范式线性规划与基变量x1,···,xm对应的规范式线性规划与基变量xj1,···,xjm对应的规范式S={j1,···,jm},

T={1,2,···,n}\S60当前60页，总共165页。2.4.1基可行解是最优解的判断准则在规范式中,令非基变量xj=0,j∈T,得到一个基解x0=(x1,···,xn)T,其中如果b’j≥0(j∈S),则x0是基可行解.61当前61页，总共165页。最优性条件目标函数中各个变量的系数就是判别数.在规范式中,设x0是线性规划(LP)对应于基B=(pj1,···,pjm)的基可行解.与基变量xj1,···,xjm对应的规范式中,若x0的全体判别数非负,则x0是(LP)的最优解.62当前62页，总共165页。判断无最优解设x0是线性规划(LP)对应于基B=(p1,···,pm)的基可行解.与基变量x1,···,xm对应的规范式中,若存在sk<0,且对所有的i=1,2,···,m有aik’≤0,则线性规划(LP)无最优解.63当前63页，总共165页。基可行解的转换从上面定理可以看出,如果某个判别数为负时,可以构造新的可行解,使得目标函数值减少.1.确定进基变量负的判别数对应的变量都可以作为进基变量.一般的,若sk=min{sj|sj<0}则以xk为进基变量.64当前64页，总共165页。基可行解的转换2.确定离基变量(采用最小比值准则)设已确定xk为进基变量,根据min{qi=b’i/a’ik|a’ik>0}=b’l/a’lk=ql,则称第l行为主行，与主行所对应的基变量xl为离基变量.65当前65页，总共165页。单纯形方法如果线性规划是非退化的,则按照上面的方法(进基,离基)迭代一次后,目标函数值有所下降.经过有限次迭代之后,一定可以得到一个基可行解,使得其所有判别数非负(得到最优解),或者其有一个判别数是负的,但对应列向量的所有分量非正(线性规划无最优解).这种求解线性规划的方法称为单纯形方法.66当前66页，总共165页。§2.5单纯形表67当前67页，总共165页。建立实用单纯形表以下是初始单纯形表：

68当前68页，总共165页。用单纯形法解线性规划minf=–2x1–3x2s.t.x1+x2≤6x1+2x2≤8x1≤4x2≤3x1,x2≥0解引入松弛变量将原问题化为标准型minf=–2x1–3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥069当前69页，总共165页。显然p3,p4,p5,p6是一组基,标准型线性规划中的系数以及这一组基可用表格的形式给出minf=-2x1-3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x6≥0目标函数中的系数基向量基变量的价格系数右端系数约束等式的系数cj-2-30000

p1

p2

p3

p4

p5

p6Bp3p4p5p6cB0000b684311100012010010001001000170当前70页，总共165页。第一步的判别数:由于在此例中基变量的价格系数均为0,所以判别数就是价格系数.cj-2-30000cBBbp1p2p3p4p5p60000p3p4p5p66843111000120100100010010001sj

-2-30000进基变量:s2=-3=min{sj|sj<0},所以x2为进基变量离基变量的判别标准:qi=bi/ai2(ai2>0)qi64/3离基变量:q6

=minqi,所以x6为离基变量()-33标出主元71当前71页，总共165页。第二步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p2写出基向量(p6换成p2)归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变)3010001写出价格系数000-3消去:用初等行变换将主元所在列其它元素消为0p5所在行不变4100010p2所在行乘以-1加到p3所在行310100-1p2所在行乘以-2加到p4所在行210010-2p2所在行乘以3加到判别数所在行

sj-20000372当前72页，总共165页。第二步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60000p3p4p5p668431110001201001000100(1)000164/3sj-2-30000p3p4p5p23010001000-34100010310100-1210010-2

sj-20000373当前73页，总共165页。cj-2-30000cBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-110010-2100010010001sj

-200003进基变量:s1=-2=min{sj|sj<0},所以x1为进基变量离基变量的判别标准:qi=bi/ai1(ai1>0)qi324/离基变量:q4=2=minqi,x4为离基变量()-22标出主元74当前74页，总共165页。第三步迭代过程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p2写出基向量(p4换成p1)归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变)3010001写出价格系数0-20-3消去:用初等行变换将主元所在列其它元素消为0p2所在行不变2000-112p1所在行乘以-1加到p3所在行1001-101p1所在行乘以-1加到p5所在行210010-2p1所在行乘以2加到判别数所在行

sj00020-175当前75页，总共165页。第三步迭代过程cj-2-30000qicBBbp1p2p3p4p5p6000-3p3p4p5p2324310100-1(1)0010-2100010010001324/sj-200003p3p1p5p230100010-20-32000-1121001-101210010-2

sj00020-176当前76页，总共165页。cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-112010001sj

00020-1进基变量:s6=–1=min{sj|sj<0},所以x6为进基变量离基变量的判别标准:qi=bi/ai6(ai6>0)qi1/13离基变量:q5=1=minqi,x5为离基变量(此处可选x3)()-11标出主元77当前77页，总共165页。第四步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p2写出基向量(p5换成p6)归一化:若主元不等于1,则进行行变换,将主元变为1(此处除以2)2010½-½0写出价格系数0-20-3消去:用初等行变换将主元所在列其它元素消为01000-½½1p6所在行乘以-1加到p3所在行0001-½-½0p6所在行乘以2加到p1所在行4100010p6所在行乘以1加到判别数所在行

sj0003/2½0p6所在行乘以-1加到p2所在行78当前78页，总共165页。第四步迭代过程cj-2-30000qicBBbp1p2p3p4p5p60-20-3p3p1p5p21223001-10110010-2000-11(2)0100011/13sj00020-1p3p1p6p22010½-½00-20-31000-½½10001-½-½04100010

sj0003/2½079当前79页，总共165页。cj-2-30000cBBbp1p2p3p4p5p60-20-3p3p1p6p20412001-1/2-1/20100010000-1/21/210101/2-1/20sj

0003/21/20此时所有的判别数都非负,迭代终止.最优解为x*=(4,2,0,0,0,1)T,原问题的最优解为x*=(4,2)T,最优值为f*=(-2)·4+(-3)·2=-14.80当前80页，总共165页。§2.6初始基可行解的求法81当前81页，总共165页。对于线性规划问题mincTxs.t.Ax≤b(b≥0)x≥0引入松弛变量化为标准型mincTxs.t.Ax+IxS=bx,xS≥0其中I是单位矩阵,xS=(xn+1,···,xn+m)T.则可以将xS作为基变量,以(0,···,0,b1,···,bm)T为初始基可行解进行单纯形迭代.对于一般的线性规划问题,无法简单给出初始基可行解.82当前82页，总共165页。为了使初始可行基成为一个单位矩阵，在有些约束条件中需要加入人工变量，但加入人工变量后的数学模型与未加入人工变量的数学模型一般是不等价的。在这一点上，人工变量与松弛变量或剩余变量是不同的，松弛变量或剩余变量只是将不等式改写为等式，而改写前后，两个约束是等价的。83当前83页，总共165页。2.6.1大M单纯形法对于线性规划问题引入人工变量xn+1,···,xn+m,构造辅助线性规划问题84当前84页，总共165页。M是相当大的正数(可以理解为正无穷),对人工变量起到惩罚的作用,逼迫辅助线性规划的最优解中人工变量均为0.

上述辅助线性规划模型与原规划模型一般是不等价的，只有当最优解中，人工变量都取零值时，才可认为两个问题的最优解是相当的。关于这一点有以下的结论：（1）辅助线性规划问题的最优解中，人工变量都处在非基变量位置（即取零值），则原问题有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。85当前85页，总共165页。（2）若辅助线性规划问题的最优解中包含非零的人工变量，则原问题无可行解。（3）若辅助线性规划问题的最优解的基变量中包含人工变量，但该人工变量取值为0，这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解。

86当前86页，总共165页。大M方法算例例2.6.1用大M单纯形法求解线性规划minf(x)=-3x1+x2+x3s.t.x1-2x2+x3≤11-4x1+x2+2x3-x4=3-2x1+x3=1x1,x2,x3,x4≥0引入松弛变量x5,人工变量x6,x7,构造辅助线性规划min–3x1+x2+x3+Mx6+Mx7s.t.x1-2x2+x3+x5=11–4x1+x2+2x3-x4+x6=3–2x1+x3+x7=1x1,···,x7≥0注:根据线性规划问题本身的形式,可以少引进一些人工变量.87当前87页，总共165页。单纯形方法求解第一步的判别数:s1=-3-1·0-(-4)M-(-2)M=6M-3类似地可以给出其它各个判别数.cj-31100M

McBBbp1p2p3p4p5p6p70MMp5p6p711311-210100-412-1010-20

10001sj

6M-3-M+1-3M+1

M000qi113/2

1x3进基,x7离基,标出主元.()注:人工变量一旦离基,则在迭代时不再参与计算.88当前88页，总共165页。续表cj-31100M

McBBbp1p2p3p4p5p6p70MMp5p6p711311-210100-412-1010-20(1)0001sj6M-3-M+1-3M+1M0000M1p5p6p310113-20010010-101-20

1000sj-1-M+10M0089当前89页，总共165页。0M1p5p6p310113-200100(1)0-101-20

1000/1/sj-1-M+10M00011p5p2p31211(3)00-21010-10-20

1004//sj-10010-311p1p2p3419100-2/31/3010-1000

1-4/32/3sj0001/31/390当前90页，总共165页。求得辅助规划问题的最优解为(4,1,9,0,0,0,0)T,原线性规划的最优解为(4,1,9,0)T,最优值为

-3·4+1·3+1·9=-2.注:根据各个判别数,可以发现M应满足–3M+1<–M+1,–3M+1<6M–3,–M+1<–1即M>2.在实际问题中可以取M为适当大的一个数,比如比问题中的系数大一个数量级.91当前91页，总共165页。2.6.2两阶段单纯形法对于线性规划问题引入人工变量xn+1,···,xn+m,构造辅助线性规划问题92当前92页，总共165页。将上述辅助线性规划问题拆成两个线性规划，即为两阶段法。第1阶段求解第1个线性规划，第1个线性规划的目标函数是对所有人工变量之和求最小。（1）若求得的最优解中，所有人工变量都处在非基变量的位置，即，则从第1阶段的最优解中去掉人工变量后，即为原问题的一个基本可行解，作为原问题的一个初始基本可行解，再求解原问题，从而进入第2阶段。93当前93页，总共165页。（2）假若求得第1阶段的最优解中，至少有一个人工变量不为零值，则说明添加人工变量之前的原问题无可行解，不再需要进入第2阶段。因此两阶段法的第1阶段求解，有两个目的：一为判断原问题有无可行解；二，若有，则可求得原问题的一个初始基本可行解，再对原问题进行第2阶段的计算。94当前94页，总共165页。两阶段法算例用两阶段法求解线性规划

min4x1+x2+x3

s.t.2x1+x2+2x3=4

3x1+3x2+x3=3

x1,x2,x3≥0解,引入人工变量,构造辅助线性规划:

minx4+x5

s.t.2x1+x2+2x3+x4=4

3x1+3x2+x3+x5=3

x1,x2,x3,x4,x5≥095当前95页，总共165页。单纯形表cj00011qicBBbp1p2p3p4p511p4p54321210(3)310121sj-5-4-30010p4p1210-1(4/3)1111/303/23sj01-4/3000p3p13/21/20-3/4115/40sj00096当前96页，总共165页。单纯形表cj00011qicBBbp1p2p3p4p511p4p54321210(3)310021sj-5-4-30010p4p1210-1(4/3)1111/303/23sj01-4/3000p3p13/21/20-3/4115/40sj000最优解(1/2,0,3/20,0)T,最优值w*=0,由此得到原线性规划的一个基可行解x0=(1/2,0,3/2)T.将上表的最后部分转到新的单纯形表中(求解原线性规划),不过判别数要重新计算.97当前97页，总共165页。求解原线性规划的单纯形表得到原线性规划的最优解x*=

(0,2/5,9/5)T,最优值f*=11/5.cj411qicBBbp1p2p314p3p13/21/20-3/411(5/4)0/2/5sj0-13/4011p3p29/52/53/5014/510sj13/50098当前98页，总共165页。§2.7线性规划的

对偶理论99当前99页，总共165页。假设某工厂有m种设备:B1,B2,···,Bm.一年内各设备的生产能力(有效台时数)为b1,b2,···,bm.利用这些设备可以加工n种产品:A1,A2,···,An,单位产品的利润分别为c1,c2,···,cn.第j种产品需要在第i种设备上加工的台时数为aij.问在设备能力允许的条件下怎样安排生产计划,使全年总收入最多?设x1,x2,···,xn为各产品的计划年产量,s为全年总收入,易建立该问题的数学模型.100当前100页，总共165页。假设某工厂有m种设备:B1,B2,···,Bm.一年内各设备的生产能力(有效台时数)为b1,b2,···,bm.利用这些设备可以加工n种产品:A1,A2,···,An,单位产品的利润分别为c1,c2,···,cn.第j种产品需要在第i种设备上加工的台时数为aij.问在设备能力允许的条件下怎样安排生产计划,使全年总收入最多?设x1,x2,···,xn为各产品的计划年产量,s为全年总收入,易建立该问题的数学模型.101当前101页，总共165页。对偶问题假设工厂将所有的设备用于出租,需要给各种设备制定出租价格.定价原则有两条:一是出租后得到的单位利润不得少于直接生产时的收入,二是出租价格尽量的低,以利于市场竞争.设第i种设备Bi的单位台时的出租价格为yi,全年总收入为w,则该问题的数学模型为102当前102页，总共165页。对偶问题假设工厂将所有的设备用于出租,需要给各种设备制定出租价格.定价原则有两条:一是出租后得到的单位利润不得少于直接生产时的收入,二是出租价格尽量的低,以利于市场竞争.设第i种设备Bi的单位台时的出租价格为yi,全年总收入为w,则该问题的数学模型为103当前103页，总共165页。可以看出,原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述.原始线性规划对偶线性规划104当前104页，总共165页。对称形势下对偶问题的一般形式定义2.7.1满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取“≤”号，当目标函数求极小时均取“≥”号。105当前105页，总共165页。对称形势下对偶问题的一般形式原始线性规划mincTx(LP)