第二章最优化-线性规划

第二章线性规划,.,2,2.1凸集与凸函数,.,3,凸集,定义2.1.1设集合DRn,若对于任意点x,yD,及实数a,0a1,都有ax+(1-a)yD,则称集合D为凸集.,常见的凸集:单点集x,空集,整个欧式空间Rn,超平面H=xRn|a1x1+a2x2+anxn=b，半空间H+=xRn|a1x1+a2x2+anxnb，实心圆，实心球，实心长方体等都是凸集。,.,4,凸集,从直观上看，没有凹入部分，或没有空洞的是凸集。几何解释为：集合D中任两点连线上的每一点仍在D中，则D为凸集。,.,5,凸集的例,例2.1.2超球|x|r为凸集证明设x,y为超球中任意两点,0a1,则有|ax+(1-a)y|a|x|+(1-a)|y|ar+(1-a)r=r,即点ax+(1-a)y属于超球,所以超球为凸集.,.,6,凸集的性质,(i)有限个(可以改成无限)凸集的交集为凸集.即:若Dj(jJ)是凸集,则它们的交集D=x|xDj,jJ是凸集.(ii)设D是凸集,b是一实数,则下面集合是凸集bD=y|y=bx,xD.,.,7,凸集的性质,(iii)设D1,D2是凸集,则D1与D2的和集D1+D2=y|y=x+z,xD1,zD2是凸集.注:和集与并集有很大的区别,凸集的并集未必是凸集,而凸集的和集是凸集.例:D1=(x,0)T|xR表示x轴上的点,D2=(0,y)T|yR,表示y轴上的点.则D1D2表示两个轴的所有点,它不是凸集;D1+D2=R2是凸集,.,8,推论凸集的线性组合是凸集.,定义2.1.2设xiRn,i=1,k,实数li0,则称为x1,x2,xk的凸组合.,容易证明:凸集中任意有限个点的凸组合仍然在该凸集中.,两点的凸组合,三点的凸组合,多点的凸组合,.,9,极点,定义2.1.3设D为凸集,xD.若D中不存在两个相异的点y,z及某一实数a(0,1)使得x=ay+(1-a)z则称x为D的极点.,凸集,极点,凸集,极点,.,10,极点,例D=xRn|x|a(a0),则|x|=a上的点均为极点,证明:设|x|=a,若存在y,zD及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,凸函数,定义2.1.4设函数f(x)定义在凸集DRn上,若对任意的x,yD,及任意的a0,1都有f(ax+(1-a)y)af(x)+(1-a)f(y)则称函数f(x)为凸集D上的凸函数.,.,12,凸函数,定义2.1.5设函数f(x)定义在凸集DRn上,若对任意的x,yD,xy,及任意的a(0,1)都有f(ax+(1-a)y)af(x)+(1-a)f(y)则称函数f(x)为凸集D上的严格凸函数.,将上述定义中的不等式反向,可以得到凹函数和严格凹函数的定义.,.,13,凸函数的例,例2.1.3设f(x)=(x1)2,试证明f(x)在(,+)上是严格凸函数.,证明:设x,yR,且xy,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)2f(x)+f(x)T(y-x),.,20,二阶条件,设在开凸集DRn上f(x)可微,则(i)f(x)是D内的凸函数的充要条件为,在D内任一点x处,f(x)的Hesse矩阵G(x)半正定,其中,(ii)若在D内G(x)正定,则f(x)在D内是严格凸函数.,.,21,凸规划,定义2.1.6设DRn为凸集,则f(x)为D上的凸函数,则称规划问题minf(x)s.t.xD为凸规划问题.,定理2.1.5(i)凸规划的任一局部极小点x是整体极小点,全体极小点组成凸集.(ii)若f(x)是DRn上的严格凸函数,且凸规划问题minf(x)s.t.xD的整体极小点存在,则整体极小点唯一.,.,22,2.2线性规划的标准型与基本概念,.,23,线性规划的一般形式,min(max)c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(或,=)b1a21x1+a22x2+a2nxn(或,=)b2am1x1+am2x2+amnxn(或,=)bmx1,x2,xn0,.,24,线性规划的标准型,minc1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1,x2,xn0其中bi0.,在标准形式中目标函数一律改为最大化或最小化，此处我们统一为最小化，约束条件（非负约束条件除外）一律化成等式，且要求其右端项大于等于零。,.,25,矩阵-向量形式的标准型,mincTx(LP)s.t.Ax=bx0,其中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.,DF时但目标函数无下界时,称线性规划(LP)无界或无最优解;,D=F时,称线性规划无可行解;,DF时若目标函数有下界,可以证明线性规划(LP)必有最优解.,.,28,可行域为凸集,定理2.2.1线性规划问题mincTx(LP)s.t.Ax=bx0的可行域D为凸集.,证明任取x,yD,则有Ax=b,x0,Ay=b,y0,对任意的a0,1,设z=ax+(1-a)y,则z0,且Az=A(ax+(1-a)y)=aAx+(1-a)Ay=ab+(1-a)b=b因此zDD为凸集.,.,29,一般形式转化为标准型,(i)极大极小maxf(x)minf(x),(ii)若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量称为松弛变量，将不等式改为等式。如,(iii)若约束条件是大于等于型，则在该约束条件不等式左边减去一个新变量称为剩余变量，将不等式改为等式。如,.,30,一般形式转化为标准型,(iv)若某个约束方程右端项，则在约束方程两端乘以（-1），不等号改变方向，然后再将不等式化为等式。,(v)若变量xj无非负约束，则引入非负变量xj0,xj0,令xj=xj-xj”.,.,31,例将线性规划miny=2x1-x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1-x2+2x3=5x1,x20,x3是自由变量化为标准型,解:令x3=x3-x3,得到标准型miny=2x1-x2-3x3+3x3s.t.x1+x2+x3-x3+x4=7x1-x2+x3-x3-x5=2-3x1-x2+2x3-2x3=5x1,x2,x3,x3,x4,x50,.,32,例将线性规划maxy=250 x1+350 x2s.t.5x1+6x22508x1+6x230010 x1+20 x2=-700 x10,x20化为标准型,解:令x2=-x2,得到标准型min-y=-250 x1+350 x2s.t.5x1-6x2-x3=2508x1-6x2+x4=300-10 x1+20 x2=700 x10,x20,x30,x40,.,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,例考虑线性规划min2x1-x2s.t.x1+x2+x3=5-x1-x2+x4=02x1+2x2+x5=22x1,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,本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了,这样将选择的范围控制在有限个.,定理2.3.1设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x的正分量对应的系数列向量线性无关.,.,39,定理2.3.2设x是标准型线性规划(LP)的可行解,x为(LP)的基可行解的充要条件是,x为可行域D的极点.,证明:必要性不妨设x=(x1,x2,xm,0,0)T是(LP)的基可行解,且x1,x2,xm是基变量,假设有u,vD,00乘(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/2u+1/2v,这与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,有可行解有基可行解,定理2.3.3若线性规划(LP)存在可行解,则它一定存在基可行解.,.,44,有最优解有最优的基可行解,定理2.3.4若线性规划(LP)存在最优解,则必存在基可行解是最优解.,.,45,单纯形方法的思路,找出一基可行解(极点)若其不是最优,找到一个相邻极点新的目标函数值不大于原目标函数值经过有限次迭代给出最优解或判断无最优解,.,46,单纯形方法的思路(几何),线性规划min-72x1-64x2s.t.x1+x2+x3=5012x1+8x2+x4=4903x1+x5=100 x1,x2,x3,x4,x50的等价形式为,min-72x1-64x2s.t.x1+x25012x1+8x24903x1100 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=5012x1+8x2+x4=4903x1+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=5012x1+8x2+x4=4903x1+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/38x2+x4-4x5=90 x1+x5/3=100/3x1,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是非基变量,将原规划化为min8x4-8x5-3120s.t.x3-x4/8+x5/6=65/12x2+x4/8-x5/2=45/4x1+x5/3=100/3x1,x2,x3,x4,x50解为(100/3,45/4,65/12,0,0)T.,x5最大可以取为65/2.对应的,线性规划可以转化为下页的形式,.,55,单纯形方法的思路(代数),min48x3+2x4-3380s.t.6x3-3x4/4+x5=65/2x2+3x3-x4/4=55/2x1-2x3+x4/4=45/2x1,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,最优性条件,定理2.4.1设x0是线性规划(LP)对应于基B=(pj1,pjm)的基可行解.与基变量xj1,xjm对应的规范式中,若x0的全体判别数非负,则x0是(LP)的最优解.,.,63,判断无最优解,定理2.4.2设x0是线性规划(LP)对应于基B=(p1,pm)的基可行解.与基变量x1,xm对应的规范式中,若存在sk0,且对所有的i=1,2,m有aik0,则线性规划(LP)无最优解.,.,64,基可行解的转换,从上面定理可以看出,如果某个判别数为负时,可以构造新的可行解,使得目标函数值减少.,1.确定进基变量负的判别数对应的变量都可以作为进基变量.一般的,若sk=minsj|sj0=bl/alk=ql,则称第l行为主行，与主行所对应的基变量xl为离基变量.,.,66,单纯形方法,如果线性规划是非退化的,则按照上面的方法(进基,离基)迭代一次后,目标函数值有所下降.经过有限次迭代之后,一定可以得到一个基可行解,使得其所有判别数非负(得到最优解),或者其有一个判别数是负的,但对应列向量的所有分量非正(线性规划无最优解).这种求解线性规划的方法称为单纯形方法.,.,67,2.5单纯形表,.,68,建立实用单纯形表,以下是初始单纯形表：,.,69,例2.5.1用单纯形法解线性规划minf=2x13x2s.t.x1+x26x1+2x28x14x23x1,x20,解引入松弛变量将原问题化为标准型minf=2x13x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x60,.,70,显然p3,p4,p5,p6是一组基,标准型线性规划中的系数以及这一组基可用表格的形式给出,minf=-2x1-3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x60,目标函数中的系数,基向量,基变量的价格系数,右端系数,约束等式的系数,cj-2-30000p1p2p3p4p5p6,Bp3p4p5p6,cB0000,b6843,111000120100100010010001,.,71,第一步的判别数:由于在此例中基变量的价格系数均为0,所以判别数就是价格系数.,sj-2-30000,进基变量:s2=-3=minsj|sj0),qi64/3,离基变量:q6=minqi,所以x6为离基变量,(),-3,3,标出主元,.,72,第二步迭代过程,p3p4p5p2,写出基向量(p6换成p2),归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变),3010001,写出价格系数,000-3,消去:用初等行变换将主元所在列其它元素消为0,p5所在行不变,4100010,p2所在行乘以-1加到p3所在行,310100-1,p2所在行乘以-2加到p4所在行,210010-2,p2所在行乘以3加到判别数所在行,sj-200003,.,73,第二步迭代过程,p3p4p5p2,3010001,000-3,4100010,310100-1,210010-2,sj-200003,.,74,sj-200003,进基变量:s1=-2=minsj|sj0),qi324/,离基变量:q4=2=minqi,x4为离基变量,(),-2,2,标出主元,.,75,第三步迭代过程,p3p1p5p2,写出基向量(p4换成p1),归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变),3010001,写出价格系数,0-20-3,消去:用初等行变换将主元所在列其它元素消为0,p2所在行不变,2000-112,p1所在行乘以-1加到p3所在行,1001-101,p1所在行乘以-1加到p5所在行,210010-2,p1所在行乘以2加到判别数所在行,sj00020-1,.,76,第三步迭代过程,p3p1p5p2,3010001,0-20-3,2000-112,1001-101,210010-2,sj00020-1,.,77,sj00020-1,进基变量:s6=1=minsj|sj0),qi1/13,离基变量:q5=1=minqi,x5为离基变量(此处可选x3),(),-1,1,标出主元,.,78,第四步迭代过程,p3p1p6p2,写出基向量(p5换成p6),归一化:若主元不等于1,则进行行变换,将主元变为1(此处除以2),2010-0,写出价格系数,0-20-3,消去:用初等行变换将主元所在列其它元素消为0,1000-1,p6所在行乘以-1加到p3所在行,0001-0,p6所在行乘以2加到p1所在行,4100010,p6所在行乘以1加到判别数所在行,sj0003/20,p6所在行乘以-1加到p2所在行,.,79,第四步迭代过程,p3p1p6p2,2010-0,0-20-3,1000-1,0001-0,4100010,sj0003/20,.,80,sj0003/21/20,此时所有的判别数都非负,迭代终止.最优解为x*=(4,2,0,0,0,1)T,原问题的最优解为x*=(4,2)T,最优值为f*=(-2)4+(-3)2=-14.,.,81,2.6初始基可行解的求法,.,82,对于线性规划问题mincTxs.t.Axb(b0)x0,引入松弛变量化为标准型mincTxs.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单纯形法求解线性规划minf(x)=-3x1+x2+x3s.t.x1-2x2+x311-4x1+x2+2x3-x4=3-2x1+x3=1x1,x2,x3,x40,引入松弛变量x5,人工变量x6,x7,构造辅助线性规划min3x1+x2+x3+Mx6+Mx7s.t.x1-2x2+x3+x5=114x1+x2+2x3-x4+x6=32x1+x3+x7=1x1,x70,注:根据线性规划问题本身的形式,可以少引进一些人工变量.,.,88,单纯形方法求解,第一步的判别数:s1=-3-10-(-4)M-(-2)M=6M-3类似地可以给出其它各个判别数.,sj6M-3-M+1-3M+1M000,qi113/21,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,两阶段法算例,例2.6.2用两阶段法求解线性规划min4x1+x2+x3s.t.2x1+x2+2x3=43x1+3x2+x3=3x1,x2,x30,解,引入人工变量,构造辅助线性规划:minx4+x5s.t.2x1+x2+2x3+x4=43x1+3x2+x3+x5=3x1,x2,x3,x4,x50,.,96,单纯形表,.,97,单纯形表,最优解(1/2,0,3/20,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,对称形势下对偶问题的一般形式,原始线性规划mincTx(LP)s.t.Axbx0,对偶线性规划maxbTy(DP)s.t.ATycy0,.,107,对合性,定理2.7.1对偶线性规划的对偶问题是原始线性规划问题,.,108,例写出下面线性规划的对偶规划模型,.,109,解：按照对称形式的对偶关系，其对偶模型为,.,110,非对称形式下对偶线性规划,并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系：目标函数类型之间的对应关系目标函数系数与右边项的对应关系约束系数矩阵之间的对应关系约束类型与变量类型之间的对应关系,.,111,由于前面三个对应关系与标准形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:,.,112,例写出下列线性规划问题的对偶问题（1）,.,113,答案：,.,114,（2）,.,115,答案：,.,116,.,117,.,118,对偶规划的性质,考虑如下的线性规划min5x1+3x2(LP)s.t.x1+2x2-x3=24x1+x2-x4=3x1,x2,x3,x40,其对偶规划为max2y1+3y2(DP)s.t.y1+4y252y1+y23-y10-y20y1，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,弱对偶性定理,标准型线性规划mincTx(LP)s.t.Ax=bx0,对偶线性规划maxbTy(DP)s.t.ATyc,若x0,y0分别是(LP)与(DP)的可行解,则Ax0=b,x00,ATy0c,于是y0Tb=y0T(Ax0)=(y0TA)x0=(ATy0)Tx0cTx0,定理2.7.4极小化线性规划问题的目标函数值不小于其对偶规划的目标函数值.,.,121,定理2.7.5(最优性)若x0是原始线性规划的可行解,y0是对偶线性规划的可行解,且cTx0=bTy0,则x0与y0分别是原始线性规划问题与对偶线性规划问题的最优解.证明：,.,122,定理2.7.6若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值,则另一个无可行解.,即：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,.,123,对偶的线性规划问题的解,两个互为对偶的线性规划的解的情况,(1)两个都有可行解,(2)两个都无可行解,两个都有最优解,最优值相等,一个有最优解,(3)一个有可行解,无最优解(目标函数无界),则另一个无可行解,.,124,互补松弛性,(ATy-c)Tx=0,bTy=cTx,Ax=b,定理2.7.8x,y分别是原始线性规划问题与对偶线性规划的可行解,则x,y分别是最优解的充要条件为(ATy-c)Tx=0.,.,125,互补松弛性,原始线性规划minf=-2x1-3x2s.t.x1+x2+x3=6x1+2x2+x4=8x1+x5=4x2+x6=3x1,x2,x3,x4,x5,x60,对偶线性规划maxf=6y1+8y2+4y3+3y4s.t.y1+y2+y3-2y1+2y2+y4-3y10y20y30y40,原始规划最优解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用对偶单纯形法解线性规划minz=12x1+8x2+16x3+12x4s.t.2x1+x2+4x322x1+2x2+4x43x1,x2,x3,x40,minz=12x1+8x2+16x3+12x4s.t.2x1-x2-4x3+x5=22x1-2x2-4x4+x6=3x1,x2,x3,x4,x5,x60,引入松弛变量得到标准型线性规划,.,131,构造对偶单纯形表,minz=12x1+8x2+16x3+12x4s.t.-2x1-x2-4x3+x5=-2-2x1-2x2-4x4+x6=-3x1,x2,x3,x4,x5,x60,sj128161200,选取离基变量b6=-3=minbj|bj0,-3,选取进基变量,s4/a64=maxsj/a6j|a6j0Dbrmin-(xB)i/bir|bir0,.,142,影子价格(对偶最优解的经济解释),当线性规划原问题求得最优解xj*(j=1,2n)时，其对偶问题也得到最优解yi*(i=1,.,m),代入各自的目标函数后有：,其中，bi代表第i种资源的拥有量，对偶变量yi*的意义代表在资源最优利用条件下对单位资源i的估价。这种估计不是资源的市场价格，而是根据在生产中做出的贡献而作的估价，为区别一般意义的价格，我们将其（yi*）称为影子价格（shadowprice）,.,143,影子价格的几点说明,1.资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。,2.影子价格是一种边际价格，在上式中对Z求bi的偏导数得,这说明yi*的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数Z的增量。,.,144,影子价格的几点说明,3.资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当某一资源的市场价格低于该影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。,.,145,影子价格的几点说明,4.根据互补松弛定理，生产过程中如果某资源bi未得到充分利用，则该种资源的影子价格为零；又当某资源的影子价格不为零时，表明该种资源已消耗完毕。,.,146,影子价格的几点说明,5.一般说来，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估计直接涉及资源的最有效利用。例如，在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如，在社会上可对一些最紧缺的资源，借助影子价格规定使用这种单位资源时必须上交的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。,.,147,2.10整数线性规划,.,148,整数线性规划,如果线性规划的全部或部分变量要求取为整数,就称为整数线性规划,有时简称为整数规划.所有的变量都要求是整数时,称为纯整数线性规划;部分变量要求取整数时,称为混合型整数线性规划.求解的简单思路:先不考虑整数要求,求解一般的线性规划.若求得的最优解不满足整数要求时,用”舍入取整”的方法处理.该方法有时会带来很大的误差,甚至得到的解不可行.,.,149,2.10.1割平面法,考虑整数规划minx1x2s.t.2x1+x264x1+5x220 x1,x20且为整数如果不考虑整数约束,其可行域见下图.最优解为(5/3,8/3)T.,.,150,(5/3,8/3),.,151,割平面法,如果考虑整数约束,那么可行域是(LP)可行域内的13个整点.我们考虑的方法之一是首先将(LP)的最优点附近的一块区域“挖掉”再求解,挖掉的区域内不含任何整点.,.,152,(5/3,8/3),.,153,解(LP)最终单纯形表为,考虑x2对应的方程,由单纯形表得到,由于x2x32为整数,可得,化为等式约束x3x4+x5=-2,.,154,割平面法,考虑到x3=6-(2x1+x2),x4=20-(4x1+5x2),根据2/3-x3/3-x4/30可以得到x1+x24可以看出,(LP)中的可行域确实去掉了一块不含整点的部分.,.,155,(5/3,8/3),.,156,割平面法,设纯整数线性规划为mincTx(ILP)s.t.Ax=bx0 xj为整数,j=1,2,n其中A,c,b中的元素为整数.去掉其中xj为整数的要求,得到的线性规划(LP)称为与(ILP)相对应的线性规划.,.,157,割平面方程,设对应的线性规划(LP)的最优解为,再设其中的xr为非整数的基变量.由最终的单纯形表可写出约束方程,其中