最优化-线性规划.ppt

第二章线性规划,2,2.1 凸集与凸函数,3,凸 集,定义 设集合D Rn,若对于任意点x,y D,及实数a,0a1,都有ax+(1-a)y D,则称集合D为凸集.,常见的凸集:单点集x,空集,整个欧式空间Rn,超平面 H=x Rn|a1x1+a2x2+anxn=b，半空间 H+=xRn|a1x1+a2x2+anxnb，实心圆，实心球，实心长方体等都是凸集。,4,凸 集,从直观上看，没有凹入部分，或没有空洞的是凸集。几何解释为：集合D中任两点连线上的每一点仍在D中，则D为凸集。,5,凸集的例,例 超球|x|r为凸集证明 设x,y为超球中任意两点,0a1,则有|ax+(1-a)y|a|x|+(1-a)|y|a r+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.,6,凸集的性质,(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(j J)是凸集,则它们的交集D=x|x Dj,j J 是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集b D=y|y=b x,x D.,7,凸集的性质,(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 轴上的点.则D1D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集,8,推论 凸集的线性组合是凸集.,定义2.1.2 设xi Rn,i=1,k,实数li0,则 称为x1,x2,xk的凸组合.,容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.,两点的凸组合,三点的凸组合,多点的凸组合,9,极 点,定义 设D为凸集,xD.若D中不存在两个相异的点y,z及某一实数a(0,1)使得x=ay+(1-a)z则称x为D的极点.,凸集,极点,凸集,极点,10,极 点,例 D=x Rn|x|a(a0),则|x|=a上的点均为极点,证明:设|x|=a,若存在y,z D及a(0,1),使得x=ay+(1-a)z.则a2=|x|2a2|y|2+(1-a)2|z|2+2a(1-a)|y|z|a2,不等式取等号,必须|y|=|z|=a,容易证明y=z=x,根据定义可知,x为极点.,11,凸 函 数,定义 设函数f(x)定义在凸集D Rn上,若对任意的x,y D,及任意的a 0,1都有f(a x+(1-a)y)a f(x)+(1-a)f(y)则称函数f(x)为凸集D上的凸函数.,12,凸 函 数,定义 设函数f(x)定义在凸集D Rn上,若对任意的x,yD,xy,及任意的a(0,1)都有f(a x+(1-a)y)a f(x)+(1-a)f(y)则称函数f(x)为凸集D上的严格凸函数.,将上述定义中的不等式反向,可以得到凹函数和严格凹函数的定义.,13,凸函数的例,例 设f(x)=(x1)2,试证明f(x)在(,+)上是严格凸函数.,证明:设x,y R,且xy,a(0,1)都有 f(ax+(1-a)y)-(a f(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)20,因此f(x)在(,+)上是严格凸函数.,14,凸函数的几何性质,对一元函数f(x),在几何上a f(x1)+(1-a)f(x2)(0a1)表示连接(x1,f(x1),(x2,f(x2)的线段,f(ax1+(1-a)x2)表示在点ax1+(1-a)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.,对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.,15,凸函数的性质,(i)设f(x)是凸集D Rn上的凸函数,实数k0,则kf(x)也是D上的凸函数.,(ii)设f1(x),f2(x)是凸集D Rn上的凸函数,实数l,m0,则lf1(x)+m f2(x)也是D上的凸函数.,(iii)设f(x)是凸集D Rn上的凸函数,b为实数,则水平集S(f,b)=x|xD,f(x)b 是凸集.,下面的图形给出了凸函数f(x,y)=x4+3x2+y4+y2+xy的等值线(f(x,y)=2,4,6,8,10,12)的图形.可以看出水平集为凸集.,16,凸函数的性质,17,凸函数的判断,定理 设f(x)定义在凸集D Rn上,x,yD.令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(xy),一元函数F(t)为0,1上的严格凸函数.,18,凸函数的判断,19,一阶条件,定理(一阶条件)设在凸集D Rn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y D,都有f(y)f(x)+f(x)T(y-x),定理2.1.3(一阶条件)设在凸集D Rn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y D,xy,都有f(y)f(x)+f(x)T(y-x),20,二阶条件,设在开凸集D Rn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中,(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.,21,凸规划,定义 设D Rn为凸集,则f(x)为D上的凸函数,则称规划问题min f(x)s.t.x D为凸规划问题.,定理(i)凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是D Rn上的严格凸函数,且凸规划问题min f(x)s.t.x D的整体极小点存在,则整体极小点唯一.,22,2.2 线性规划的标准型与基本概念,23,线性规划的一般形式,min(max)c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(或,=)b1 a21x1+a22x2+a2nxn(或,=)b2 am1x1+am2x2+amnxn(或,=)bm x1,x2,xn0,24,线性规划的标准型,min c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0其中bi 0.,在标准形式中目标函数一律改为最大化或最小化，此处我们统一为最小化，约束条件（非负约束条件除外）一律化成等式，且要求其右端项大于等于零。,25,矩阵-向量形式的标准型,min cTx(LP)s.t.Ax=b x0,其中c=(c1,c2,cn)T,x=(x1,x2,xn)T,b=(b1,b2,bm)T,c:价格向量A:约束矩阵b:右端向量,26,矩阵-向量形式的标准型,记A=(p1,p2,pn),其中pj=(a1j,a2j,amj)T,线性规划(LP)又可以表示为,27,线性规划解的情况,满足约束条件的向量x是可行解,全体可行解构成可行域D.,D F 时但目标函数无下界时,称线性规划(LP)无界或无最优解;,D=F 时,称线性规划无可行解;,D F 时若目标函数有下界,可以证明线性规划(LP)必有最优解.,28,可行域为凸集,定理线性规划问题 min cTx(LP)s.t.Ax=b x0的可行域D为凸集.,证明 任取x,y D,则有Ax=b,x0,Ay=b,y0,对任意的a 0,1,设z=ax+(1-a)y,则z0,且Az=A(ax+(1-a)y)=aAx+(1-a)Ay=ab+(1-a)b=b因此z DD为凸集.,29,一般形式转化为标准型,(i)极大极小max f(x)min f(x),(ii)若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量称为松弛变量，将不等式改为等式。如,(iii)若约束条件是大于等于型，则在该约束条件不等式左边减去一个新变量称为剩余变量，将不等式改为等式。如,30,一般形式转化为标准型,(iv)若某个约束方程右端项，则在约束方程两端乘以（-1），不等号改变方向，然后再将不等式化为等式。,(v)若变量xj无非负约束，则引入非负变量xj0,xj0,令xj=xj-xj”.,31,例将线性规划min y=2x1-x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1-x2+2x3=5x1,x20,x3是自由变量化为标准型,解:令x3=x3-x3,得到标准型min y=2x1-x2-3x3+3x3s.t.x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2-3x1-x2+2x3-2x3=5 x1,x2,x3,x3,x4,x50,32,例将线性规划max y=250 x1+350 x2s.t.5x1+6x2 2508x1+6x2 30010 x1+20 x2=-700 x10,x2 0化为标准型,解:令x2=-x2,得到标准型min-y=-250 x1+350 x2s.t.5x1-6 x2-x3=2508x1-6x2+x4=300-10 x1+20 x2=700 x1 0,x2 0,x3 0,x4 0,33,基本概念,设约束矩阵A的秩为m(行满秩),且mn,则A中必存在m阶非奇异子阵B,不妨设B=(p1,p2,pm)称B为线性规划问题(LP)的一个基矩阵,或称为基,基矩阵中的列向量称为基向量,对应的决策变量称为基变量,其余变量称为非基变量.,34,基本概念,在约束方程组取定基矩阵B=(p1,p2,pm)之后,令非基变量均为0,得到的方程组p1x1+p2x2+pmxm=b有唯一解,这样得到约束方程组的一个解向量x=(x1,x2,xm)T通过这种方法得到的满足约束方程组的解称为基矩阵B对应的基解.,35,基本概念,如果基解又满足非负条件,则称之为基可行解.此时的基B称为可行基.基可行解中非零分量的个数不会超过m,若基可行解中非零分量的个数恰为m,称此基可行解为非退化的基可行解,否则称为退化的基可行解.若一个线性规划的所有基可行解都是非退化的,称此线性规划是非退化的.,线性规划(LP)的基解个数不会超过,36,例 考虑线性规划min 2x1-x2s.t.x1+x2+x3=5-x1-x2+x4=0 2x1+2x2+x5=22 x1,x2,x3,x4,x50,该线性规划有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退化,37,2.3 线性规划的基本定理,38,本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了,这样将选择的范围控制在有限个.,定理 设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x的正分量对应的系数列向量线性无关.,39,定理 设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x为可行域D的极点.,证明:必要性 不妨设x=(x1,x2,xm,0,0)T是(LP)的基可行解,且x1,x2,xm是基变量,假设有u,vD,0a 1,使得 x=a u+(1-a)v当m+1jn时,0=xj=a uj+(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为极点.,40,充分性 设x=(x1,x2,xk,0,0)T是可行域的极点,其中x1,x2,xk0.假设x不是基可行解,于是p1,p2,pk线性相关,即有一组不全为0的数a1,a2,ak,使得a1p1+a2p2+akpk=0(2.4)又xD,所以 x1p1+x2p2+xkpk=b(2.5)用e 0乘(2.4)再与(2.5)相加减得(x1+ea1)p1+(x2+ea2)p2+(xk+eak)pk=b(x1ea1)p1+(x2ea2)p2+(xkeak)pk=b,41,令u=(x1+ea1,x2+ea2,xk+eak,0,0)Tv=(x1ea1,x2ea2,xkeak,0,0)T则有Au=b,Av=b,当e充分小时,可使u0,v0.因此,当e充分小时,u,v都是(LP)的可行解,且uv,x=1/2 u+1/2 v,这与x是D的极点相矛盾.因此x是基可行解.,推论:线性规划(LP)的可行域D=x|Ax=b,x0最多具有有限个极点,42,(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退化,前例中三个退化的基可行解对应着同一个极点(基可行解与极点不是一一对应),43,有可行解有基可行解,定理 若线性规划(LP)存在可行解,则它一定存在基可行解.,44,有最优解有最优的基可行解,定理 若线性规划(LP)存在最优解,则必存在 基可行解是最优解.,45,单纯形方法的思路,找出一基可行解(极点)若其不是最优,找到一个相邻极点新的目标函数值不大于原目标函数值经过有限次迭代给出最优解或判断无最优解,46,单纯形方法的思路(几何),线性规划min-72x1-64x2s.t.x1+x2+x3=50 12x1+8x2+x4=490 3x1+x5=100 x1,x2,x3,x4,x50的等价形式为,min-72x1-64x2s.t.x1+x2 50 12x1+8x2 490 3x1 100 x1,x20,47,O,A,B,C,D,梯度方向,x2=0,x1=0,x5=0,x3=0,x4=0,等值线,基可行解O,48,O,A,B,C,D,x2=0,x1=0,x5=0,x3=0,x4=0,基可行解A,49,O,A,B,C,D,x2=0,x1=0,x5=0,x3=0,x4=0,基可行解B,50,O,A,B,C,D,x2=0,x1=0,x5=0,x3=0,x4=0,基可行解C,是最优解,51,单纯形方法的思路(代数),例 考察线性规划min-72x1-64x2s.t.x1+x2+x3=50 12x1+8x2+x4=490 3x1+x5=100 x1,x2,x3,x4,x50以x3,x4,x5为基变量,容易得到基可行解(0,0,50,490,100)T.,由于x1的价格系数为负数,增加x1的取值可以使得目标函数值减少.类似的,我们也可以增加x2的取值,使得目标函数值减少.由于-72负得多一些,我们先增加x1.,52,单纯形方法的思路(代数),min-72x1-64x2s.t.x1+x2+x3=50 12x1+8x2+x4=490 3x1+x5=100 x1,x2,x3,x4,x50 x1可以增加多少?,x150,x1490/12,x1100/3,因此x1的最大取值为min(50,490/12,100/3)=100/3,此时x5的取值为0,x5“出基”.,53,单纯形方法的思路(代数),根据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,x50此时,基变量为x1,x3,x4,基可行解为(100/3,0,50/3,90,0)T.,若x2(其系数为负)的取值增加,可以使得目标函数值减少,x250/3,x290/8,因此x2的最大取值为min(50/3,90/8)=90/8,x4“出基”.,54,单纯形方法的思路(代数),此时,x4,x5是非基变量,将原规划化为min 8x4-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,x50解为(100/3,45/4,65/12,0,0)T.,x5最大可以取为65/2.对应的,线性规划可以转化为下页的形式,55,单纯形方法的思路(代数),min 48x3+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,x50对应的解为(45/2,55/2,0,0,65/2)T.,此时,目标函数中非基变量的系数为正,因此目标函数的取值不能再减少.最优值为-3380.,56,单纯形方法的思路(代数),单纯形方法求解线性规划,首先找出一个基可行解.将目标函数写成非基变量的线性组合(再加上一个常数)的形式.如果组合的系数全部非负,则已经找到最优解.如果组合的系数中有负数,从中选取一个变量(“进基”)来增加取值,可以使得函数值减少.根据约束条件,可以控制增加的范围.在进基变量取最大值时,有一个变量出基,从而得到另一个基可行解.重复上面的过程,可以求得最优解.,57,2.4 单纯形方法,58,设线性规划R(A)=m，x1,x2,xm是基变量，而xm+1,xn是非基变量，并记基矩阵B=(p1,p2,pm),N=(pm+1,pn),A=(B,N),则上述线性规划问题化为,59,进一步可以将线性规划问题转化为以下形式,60,规范式,线性规划与基变量x1,xm对应的规范式,线性规划与基变量xj1,xjm对应的规范式,S=j1,jm,T=1,2,nS,61,2.4.1 基可行解是最优解的判断准则,在规范式,中,令非基变量xj=0,jT,得到一个基解x0=(x1,xn)T,其中,如果bj0(jS),则x0是基可行解.,62,最优性条件,定理 设x0是线性规划(LP)对应于基B=(pj1,pjm)的基可行解.与基变量xj1,xjm对应的规范式中,若x0的全体判别数非负,则x0是(LP)的最优解.,63,判断无最优解,定理设x0是线性规划(LP)对应于基B=(p1,pm)的基可行解.与基变量x1,xm对应的规范式中,若存在sk0,且对所有的i=1,2,m有aik0,则线性规划(LP)无最优解.,64,基可行解的转换,从上面定理可以看出,如果某个判别数为负时,可以构造新的可行解,使得目标函数值减少.,1.确定进基变量负的判别数对应的变量都可以作为进基变量.一般的,若sk=minsj|sj0则以xk为进基变量.,65,基可行解的转换,2.确定离基变量(采用最小比值准则)设已确定xk为进基变量,根据,minqi=bi/aik|aik0=bl/alk=ql,则称第l 行为主行，与主行所对应的基变量xl为离基变量.,66,单纯形方法,如果线性规划是非退化的,则按照上面的方法(进基,离基)迭代一次后,目标函数值有所下降.经过有限次迭代之后,一定可以得到一个基可行解,使得其所有判别数非负(得到最优解),或者其有一个判别数是负的,但对应列向量的所有分量非正(线性规划无最优解).这种求解线性规划的方法称为单纯形方法.,67,2.5 单纯形表,68,建立实用单纯形表,以下是初始单纯形表：,69,例 用单纯形法解线性规划min f=2x13x2s.t.x1+x26 x1+2x28 x1 4 x23 x1,x20,解 引入松弛变量将原问题化为标准型min f=2x13x2s.t.x1+x2+x3=6 x1+2x2+x4=8 x1+x5=4 x2+x6=3 x1,x2,x3,x4,x5,x60,70,显然p3,p4,p5,p6是一组基,标准型线性规划中的系数以及这一组基可用表格的形式给出,min f=-2x1-3x2s.t.x1+x2+x3=6 x1+2x2+x4=8 x1+x5=4 x2+x6=3 x1,x2,x3,x4,x5,x60,目标函数中的系数,基向量,基变量的价格系数,右端系数,约束等式的系数,cj-2-3 0 0 0 0 p1 p2 p3 p4 p5 p6,Bp3p4p5p6,cB0000,b6843,1 1 1 0 0 01 2 0 1 0 01 0 0 0 1 00 1 0 0 0 1,71,第一步的判别数:由于在此例中基变量的价格系数均为0,所以判别数就是价格系数.,sj-2-3 0 0 0 0,进基变量:s2=-3=minsj|sj0,所以x2为进基变量,离基变量的判别标准:qi=bi/ai2(ai20),qi64/3,离基变量:q6=minqi,所以x6为离基变量,(),-3,3,标出主元,72,第二步迭代过程,p3p4p5p2,写出基向量(p6换成p2),归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变),3 0 1 0 0 0 1,写出价格系数,000-3,消去:用初等行变换将主元所在列其它元素消为0,p5所在行不变,4 1 0 0 0 1 0,p2所在行乘以-1加到p3所在行,3 1 0 1 0 0-1,p2所在行乘以-2加到p4所在行,2 1 0 0 1 0-2,p2所在行乘以3加到判别数所在行,sj-2 0 0 0 0 3,73,第二步迭代过程,p3p4p5p2,3 0 1 0 0 0 1,000-3,4 1 0 0 0 1 0,3 1 0 1 0 0-1,2 1 0 0 1 0-2,sj-2 0 0 0 0 3,74,sj-2 0 0 0 0 3,进基变量:s1=-2=minsj|sj0,所以x1为进基变量,离基变量的判别标准:qi=bi/ai1(ai10),qi324/,离基变量:q4=2=minqi,x4为离基变量,(),-2,2,标出主元,75,第三步迭代过程,p3p1p5p2,写出基向量(p4换成p1),归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变),3 0 1 0 0 0 1,写出价格系数,0-20-3,消去:用初等行变换将主元所在列其它元素消为0,p2所在行不变,2 0 0 0-1 1 2,p1所在行乘以-1加到p3所在行,1 0 0 1-1 0 1,p1所在行乘以-1加到p5所在行,2 1 0 0 1 0-2,p1所在行乘以2加到判别数所在行,sj 0 0 0 2 0-1,76,第三步迭代过程,p3p1p5p2,3 0 1 0 0 0 1,0-20-3,2 0 0 0-1 1 2,1 0 0 1-1 0 1,2 1 0 0 1 0-2,sj 0 0 0 2 0-1,77,sj 0 0 0 2 0-1,进基变量:s6=1=minsj|sj0,所以x6为进基变量,离基变量的判别标准:qi=bi/ai6(ai60),qi1/13,离基变量:q5=1=minqi,x5为离基变量(此处可选x3),(),-1,1,标出主元,78,第四步迭代过程,p3p1p6p2,写出基向量(p5换成p6),归一化:若主元不等于1,则进行行变换,将主元变为1(此处除以2),2 0 1 0-0,写出价格系数,0-20-3,消去:用初等行变换将主元所在列其它元素消为0,1 0 0 0-1,p6所在行乘以-1加到p3所在行,0 0 0 1-0,p6所在行乘以2加到p1所在行,4 1 0 0 0 1 0,p6所在行乘以1加到判别数所在行,sj 0 0 0 3/2 0,p6所在行乘以-1加到p2所在行,79,第四步迭代过程,p3p1p6p2,2 0 1 0-0,0-20-3,1 0 0 0-1,0 0 0 1-0,4 1 0 0 0 1 0,sj 0 0 0 3/2 0,80,sj 0 0 0 3/2 1/2 0,此时所有的判别数都非负,迭代终止.最优解为x*=(4,2,0,0,0,1)T,原问题的最优解为x*=(4,2)T,最优值为f*=(-2)4+(-3)2=-14.,81,2.6 初始基可行解的求法,82,对于线性规划问题min cTxs.t.Axb(b0)x0,引入松弛变量化为标准型min cTxs.t.Ax+IxS=bx,xS0,其中I是单位矩阵,xS=(xn+1,xn+m)T.则可以将xS作为基变量,以(0,0,b1,bm)T为初始基可行解进行单纯形迭代.对于一般的线性规划问题,无法简单给出初始基可行解.,83,为了使初始可行基成为一个单位矩阵，在有些约束条件中需要加入人工变量，但加入人工变量后的数学模型与未加入人工变量的数学模型一般是不等价的。在这一点上，人工变量与松弛变量或剩余变量是不同的，松弛变量或剩余变量只是将不等式改写为等式，而改写前后，两个约束是等价的。,84,2.6.1 大M单纯形法,对于线性规划问题,引入人工变量xn+1,xn+m,构造辅助线性规划问题,85,M是相当大的正数(可以理解为正无穷),对人工变量起到惩罚的作用,逼迫辅助线性规划的最优解中人工变量均为0.,上述辅助线性规划模型与原规划模型一般是不等价的，只有当最优解中，人工变量都取零值时，才可认为两个问题的最优解是相当的。关于这一点有以下的结论：（1）辅助线性规划问题的最优解中，人工变量都处在非基变量位置（即取零值），则原问题有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。,86,（2）若辅助线性规划问题的最优解中包含非零的人工变量，则原问题无可行解。（3）若辅助线性规划问题的最优解的基变量中包含人工变量，但该人工变量取值为0，这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解。,87,大M方法算例,例2.6.1 用大M单纯形法求解线性规划min f(x)=-3x1+x2+x3s.t.x1-2x2+x3 11-4x1+x2+2x3-x4=3-2x1+x3=1x1,x2,x3,x40,引入松弛变量x5,人工变量x6,x7,构造辅助线性规划min 3x1+x2+x3+Mx6+Mx7s.t.x1-2x2+x3+x5=11 4x1+x2+2x3-x4+x6=3 2x1+x3+x7=1 x1,x70,注:根据线性规划问题本身的形式,可以少引进一些人工变量.,88,单纯形方法求解,第一步的判别数:s1=-3-10-(-4)M-(-2)M=6M-3类似地可以给出其它各个判别数.,sj 6M-3-M+1-3M+1 M 0 0 0,qi113/2 1,x3进基,x7离基,标出主元.,(),注:人工变量一旦离基,则在迭代时不再参与计算.,89,续表,90,91,求得辅助规划问题的最优解为(4,1,9,0,0,0,0)T,原线性规划的最优解为(4,1,9,0)T,最优值为-34+13+19=-2.,注:根据各个判别数,可以发现M应满足3M+12.,在实际问题中可以取M为适当大的一个数,比如比问题中的系数大一个数量级.,92,2.6.2 两阶段单纯形法,对于线性规划问题,引入人工变量xn+1,xn+m,构造辅助线性规划问题,93,将上述辅助线性规划问题拆成两个线性规划，即为两阶段法。第1阶段求解第1个线性规划，第1个线性规划的目标函数是对所有人工变量之和求最小。（1）若求得的最优解中，所有人工变量都处在非基变量的位置，即，则从第1阶段的最优解中去掉人工变量后，即为原问题的一个基本可行解，作为原问题的一个初始基本可行解，再求解原问题，从而进入第2阶段。,94,（2）假若求得第1阶段的最优解中，至少有一个人工变量不为零值，则说明添加人工变量之前的原问题无可行解，不再需要进入第2阶段。因此两阶段法的第1阶段求解，有两个目的：一为判断原问题有无可行解；二，若有，则可求得原问题的一个初始基本可行解，再对原问题进行第2阶段的计算。,95,两阶段法算例,例 用两阶段法求解线性规划min 4x1+x2+x3s.t.2x1+x2+2x3=4 3x1+3x2+x3=3x1,x2,x30,解,引入人工变量,构造辅助线性规划:min x4+x5s.t.2x1+x2+2x3+x4=4 3x1+3x2+x3+x5=3x1,x2,x3,x4,x50,96,单纯形表,97,单纯形表,最优解(1/2,0,3/2 0,0)T,最优值w*=0,由此得到原线性规划的一个基可行解x0=(1/2,0,3/2)T.,将上表的最后部分转到新的单纯形表中(求解原线性规划),不过判别数要重新计算.,98,求解原线性规划的单纯形表,得到原线性规划的最优解x*=(0,2/5,9/5)T,最优值f*=11/5.,99,2.7 线性规划的对偶理论,100,假设某工厂有m种设备:B1,B2,Bm.一年内各设备的生产能力(有效台时数)为b1,b2,bm.利用这些设备可以加工n种产品:A1,A2,An,单位产品的利润分别为c1,c2,cn.第j种产品需要在第i种设备上加工的台时数为aij.问在设备能力允许的条件下怎样安排生产计划,使全年总收入最多?,设x1,x2,xn为各产品的计划年产量,s为全年总收入,易建立该问题的数学模型.,101,假设某工厂有m种设备:B1,B2,Bm.一年内各设备的生产能力(有效台时数)为b1,b2,bm.利用这些设备可以加工n种产品:A1,A2,An,单位产品的利润分别为c1,c2,cn.第j种产品需要在第i种设备上加工的台时数为aij.问在设备能力允许的条件下怎样安排生产计划,使全年总收入最多?,设x1,x2,xn为各产品的计划年产量,s为全年总收入,易建立该问题的数学模型.,102,对偶问题,假设工厂将所有的设备用于出租,需要给各种设备制定出租价格.定价原则有两条:一是出租后得到的单位利润不得少于直接生产时的收入,二是出租价格尽量的低,以利于市场竞争.,设第i种设备Bi的单位台时的出租价格为yi,全年总收入为w,则该问题的数学模型为,103,对偶问题,假设工厂将所有的设备用于出租,需要给各种设备制定出租价格.定价原则有两条:一是出租后得到的单位利润不得少于直接生产时的收入,二是出租价格尽量的低,以利于市场竞争.,设第i种设备Bi的单位台时的出租价格为yi,全年总收入为w,则该问题的数学模型为,104,可以看出,原始规划与对偶规划是同一组数据参数,只是位置有所不同,所描述的问题实际上是同一个问题从另一种角度去描述.,原始线性规划,对偶线性规划,105,对称形势下对偶问题的一般形式,定义2.7.1 满足下列条件的线性规划问题称为具有对称形 式：其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取“”号。,106,对称形势下对偶问题的一般形式,原始线性规划 min cTx(LP)s.t.Axb x 0,对偶线性规划 max bTy(DP)s.t.ATyc y 0,107,对合性,定理 对偶线性规划的对偶问题是原始线性规划问题,108,例 写出下面线性规划的对偶规划模型,109,解：按照对称形式的对偶关系，其对偶模型为,110,非对称形式下对偶线性规划,并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系：目标函数类型之间的对应关系 目标函数系数与右边项的对应关系 约束系数矩阵之间的对应关系 约束类型与变量类型之间的对应关系,111,由于前面三个对应关系与标准形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:,112,例 写出下列线性规划问题的对偶问题（1）,113,答案：,114,（2）,115,答案：,116,117,118,对偶规划的性质,考虑如下的线性规划 min 5x1+3x2(LP)s.t.x1+2x2-x3=2 4x1+x2-x4=3 x1,x2,x3,x40,其对偶规划为 max 2y1+3y2(DP)s.t.y1+4y25 2y1+y2 3-y1 0-y2 0 y1，y2 无约束,119,对偶规划的性质,(LP)的三个基可行解(只写出x1,x2)及对应的目标函数值为(2,0)10(0,3)9(4/7,5/7)5,(DP)的四个基可行解(只写出y1,y2)及对应的目标函数值为(0,0)0(3/2,0)3(0,5/4)15/4(1,1)5,可见:(LP)在可行解上的取值不小于(DP)在可行解上的取值;若两者取值相等,则对应的解都是最优解.,120,弱对偶性定理,标准型线性规划min cTx(LP)s.t.Ax=bx0,对偶线性规划max bTy(DP)s.t.ATyc,若x0,y0分别是(LP)与(DP)的可行解,则Ax0=b,x00,ATy0c,于是y0Tb=y0T(Ax0)=(y0TA)x0=(ATy0)Tx0cTx0,定理 极小化线性规划问题的目标函数值不小于其对偶规划的目标函数值.,121,定理2.7.5(最优性)若x0是原始线性规划的可行解,y0是对偶线性规划的可行解,且cTx0=bTy0,则x0与y0分别是原始线性规划问题与对偶线性规划问题的最优解.证明：,122,定理 若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值,则另一个无可行解.,即：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,123,对偶的线性规划问题的解,两个互为对偶的线性规划的解的情况,(1)两个都有可行解,(2)两个都无可行解,两个都有最优解,最优值相等,一个有最优解,(3)一个有可行解,无最优解(目标函数无界),则另一个无可行解,124,互补松弛性,(ATy-c)Tx=0,bTy=cTx,Ax=b,定理 x,y分别是原始线性规划问题与对偶线性规划的可行解,则x,y分别是最优解的充要条件为(ATy-c)Tx=0.,125,互补松弛性,原始线性规划min f=-2x1-3x2s.t.x1+x2+x3=6 x1+2x2+x4=8 x1+x5=4 x2+x6=3 x1,x2,x3,x4,x5,x60,对偶线性规划max f=6y1+8y2+4y3+3y4s.t.y1+y2+y3-2 y1+2y2+y4-3 y1 0 y2 0 y3 0 y4 0,原始规划最优解x*=(4,2,0,0,0,1)T,对偶规划最优解y*=(0,-3/2,-1/2,0)T.,对偶规划y*的松弛量q=c-ATy=(0,0,0,3/2,1/2,0)T,互补松弛性:qTx=0,126,2.8 对偶单纯形法,127,1.最优解的判别,已知线性规划问题的基矩阵B及它对应的基解,并且此基解的所有判别数非负.若xB=B-1b0则所得的基解为最优解,128,2.确定离基变量,令min(B-1b)i|(B-1b)i0=(B-1b)l,则以xl为离基变量,若xl所在行的所有系数alj0(j=1,2,n),则线性规划问题无可行解.,129,3.确定进基变量,设目标函数的形式为,已确定离基变量为xl,设进基变量为xk.在目标函数中,用xk替换xl,令,则xk为进基变量,130,算例,例2.8.1 用对偶单纯形法解线性规划min z=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3 2 2x1+2x2+4x4 3 x1,x2,x3,x40,min z=12x1+8x2+16x3+12x4 s.t.2x1-x2-4x3+x5=2 2x1-2x2-4x4+x6=3 x1,x2,x3,x4,x5,x60,引入松弛变量得到标准型线性规划,131,构造对偶单纯形表,min z=12x1+8x2+16x3+12x4 s.t.-2x1-x2-4x3+x5=-2-2x1-2x2-4x4+x6=-3 x1,x2,x3,x4,x5,x60,s