《第二章最优化-线性规划》由会员分享，可在线阅读，更多相关《第二章最优化-线性规划（170页珍藏版）》请在金锄头文库上搜索。
1、第二章线性规划2.1 凸集与凸函数凸集与凸函数2 2凸凸 集集定义定义2.1.1 设集合设集合D Rn,若对于任意点若对于任意点x,y D,及实数及实数a a,0a a1,都有都有a ax+(1-a a)y D,则称集合则称集合D为为凸集凸集.常见的凸集常见的凸集:单点集单点集x, 空集空集, 整个整个欧式空间欧式空间Rn,超平面超平面 H=x Rn|a1x1+a2x2+anxn= =b，半空间半空间 H+=xRn|a1x1+a2x2+anxnb，实，实心圆，实心球，实心长方体等都是凸集。心圆，实心球，实心长方体等都是凸集。3 3凸凸 集集 从直观上看，没有凹入部分，或没有空洞从直观上看，没有
2、凹入部分，或没有空洞的是凸集。的是凸集。 几何解释为：集合几何解释为：集合D中任两点连线上的每中任两点连线上的每一点仍在一点仍在D中，则中，则D为凸集。为凸集。4 4凸集的例凸集的例例例2.1.2 超球超球|x|r为凸集为凸集证明证明 设设x,y为超球中任意两点为超球中任意两点, 0 0a a1,则有则有|a ax+(1-a a)y|a a| |x|+(1-a a)|y|a a r+(1-a a) r = r,即点即点a ax+(1-a a)y属于超球属于超球,所以超球为凸集所以超球为凸集.5 5凸集的性质凸集的性质(i)有限个有限个(可以改成无限可以改成无限)凸集的交集为凸集凸集的交集为凸集
3、.即即:若若Dj(j J)是凸集是凸集,则它们的交集则它们的交集D=x|x Dj,j J 是凸集是凸集.(ii)设设D是凸集是凸集,b b是一实数是一实数,则下面集合是凸则下面集合是凸集集b b D=y | y =b b x, x D.6 6凸集的性质凸集的性质(iii)设设D1,D2是凸集是凸集,则则D1与与D2的和集的和集D1+D2=y|y=x+z,x D1,z D2是凸集是凸集.注注:和集与并集有很大的区别和集与并集有很大的区别,凸集的并集未凸集的并集未必是凸集必是凸集, 而凸集的和集是凸集而凸集的和集是凸集.例例:D1=(x,0)T|x R表示表示 x 轴上的点轴上的点, D2=(0,
4、y)T|y R,表示表示 y 轴上的点轴上的点.则则D1D2表示两个轴的所有点表示两个轴的所有点,它不是凸集它不是凸集;D1+D2=R2是凸集是凸集7 7推论推论 凸集的线性组合是凸集凸集的线性组合是凸集.定义定义2.1.2 设设xi Rn,i=1,k,实数实数l li 0,则则 称为称为x1,x2, ,xk的的凸组合凸组合.容易证明容易证明:凸集中任意有限个点的凸组合仍然凸集中任意有限个点的凸组合仍然在该凸集中在该凸集中.两点的凸组合两点的凸组合三点的凸组合三点的凸组合 多点的凸组合多点的凸组合8 8极极 点点定义定义2.1.3 设设D为凸集为凸集, xD.若若D中不存在两中不存在两个相异的
5、点个相异的点y,z及某一实数及某一实数a a(0,1)使得使得x=a ay+(1-a a)z则称则称x为为D的极点的极点.凸凸集集极点极点凸凸集集极点极点9 9极极 点点例例 D=x Rn| |x|a(a0),则则|x|=a上的点上的点均为极点均为极点证明证明:设设|x|=a,若存在若存在y,z D及及a a(0,1),使得使得x=a ay+(1-a a)z.则则a2=|x|2a a2|y|2+(1-a a)2|z|2+2a a (1-a a)|y|z|a2不等式取等号不等式取等号,必须必须|y|=|z|=a, 容易证明容易证明y=z=x,根根据定义可知据定义可知,x为极点为极点.1010凸凸
6、 函函 数数定义定义2.1.4 设函数设函数f (x)定义在凸集定义在凸集D Rn上上,若若对任意的对任意的x,y D,及任意的及任意的a a 0,1都有都有f (a a x+(1-a a)y) a a f(x)+(1-a a) f (y)则称函数则称函数f (x)为凸集为凸集D上的上的凸函数凸函数.1111凸凸 函函 数数定义定义2.1.5 设函数设函数f (x)定义在凸集定义在凸集D Rn上上,若若对任意的对任意的x,yD,xy,及任意的及任意的a a (0,1)都有都有f (a a x+(1-a a)y) a a f(x)+(1-a a) f (y)则称函数则称函数f (x)为凸集为凸集
7、D上的上的严格凸函数严格凸函数.将上述定义中的不等式反向将上述定义中的不等式反向,可以得到可以得到凹函数凹函数和和严格凹函数严格凹函数的定义的定义.1212凸函数的例凸函数的例例例2.1.3 设设f (x)=(x1)2,试证明试证明f(x)在在(,+)上是严格凸函数上是严格凸函数.证明证明:设设x,y R,且且xy, a a (0,1)都有都有 f (a ax+(1-a a)y)-(a a f (x) +(1-a a)f (y)=(a ax+(1-a a)y-1)2-a a (x-1)2-(1-a a) (y-1)2= a a (1-a a)(x-y)2f(x)+ f(x)T(y-x)1919
8、二阶条件二阶条件设在开凸集设在开凸集D Rn上上f(x)可微可微,则则(i) f(x)是是D内的凸函数的充要条件为内的凸函数的充要条件为,在在D内内任一点任一点x处处, f(x)的的Hesse矩阵矩阵G(x)半正定半正定,其中其中(ii) 若在若在D内内G(x)正定正定,则则f(x)在在D内是严格凸函内是严格凸函数数.2020凸规划凸规划定义定义2.1.6 设设D Rn为凸集为凸集,则则f(x)为为D上的凸函数上的凸函数,则称则称规划问题规划问题min f(x)s.t. x D为凸规划问题为凸规划问题.定理定理2.1.5 (i)凸规划的任凸规划的任一局部极小点一局部极小点x是整体极小是整体极小
9、点点,全体极小点组成凸集全体极小点组成凸集.(ii)若若f(x)是是D Rn上的严上的严格凸函数格凸函数,且凸规划问题且凸规划问题min f(x)s.t. x D的整体极小点存在的整体极小点存在,则整体则整体极小点唯一极小点唯一.21212.2 线性规划的标准型线性规划的标准型与基本概念与基本概念2222线性规划的一般形式线性规划的一般形式min(max) c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn(或或,=)b1 a21x1+a22x2+a2nxn(或或,=)b2 am1x1+am2x2+amnxn(或或,=)bm x1,x2,xn02323线性规划的标准型线性
10、规划的标准型min c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2,xn0其中其中bi 0.在标准形式中目在标准形式中目标函数一律改为标函数一律改为最大化或最小化，最大化或最小化，此处我们统一为此处我们统一为最小化，约束条最小化，约束条件（非负约束条件（非负约束条件除外）一律化件除外）一律化成等式，且要求成等式，且要求其右端项大于等其右端项大于等于零。于零。2424矩阵矩阵-向量形式的标准型向量形式的标准型min cTx(LP) s.t. Ax=b x0其中其中c=(
11、c1,c2,cn)T,x=(x1,x2,xn)T,b=(b1,b2,bm)Tc:价格向量价格向量A:约束矩阵约束矩阵b:右端向量右端向量2525矩阵矩阵-向量形式的标准型向量形式的标准型记记A=(p1,p2, ,pn),其中其中pj=(a1j,a2j,amj)T,线性规划线性规划(LP)又又可以表示为可以表示为2626线性规划解的情况线性规划解的情况满足约束条件的向量满足约束条件的向量x是可行解是可行解,全体可行解全体可行解构成可行域构成可行域D. D F F 时时但目标函数无下界时但目标函数无下界时,称线性规划称线性规划(LP)无界或无最优解无界或无最优解;D= F F 时时,称线性规划无可
12、行解称线性规划无可行解; D F F 时若时若目标函数有下界目标函数有下界,可以证明线性规可以证明线性规划划(LP)必有最优解必有最优解.2727可行域为凸集可行域为凸集定理定理2.2.1线性规划问题线性规划问题 min cTx(LP) s.t. Ax=b x0的可行域的可行域D为凸集为凸集. 证明证明 任取任取x,y D,则有则有Ax=b,x0, Ay=b,y0对任意的对任意的a a 0,1,设设z=a ax+(1-a a)y,则则z0,且且Az=A(a ax+(1-a a)y)=a aAx+(1-a a)Ay=a ab+(1-a a)b=b因此因此z DD为凸集为凸集.2828一般形式转化
13、为标准型一般形式转化为标准型(i)(i)极大极大极大极大极小极小极小极小max max f f( (x x) ) min min f f( (x x) )(ii)若约束条件是小于等于型，则在该约束若约束条件是小于等于型，则在该约束条件不等式左边加上一个新变量条件不等式左边加上一个新变量称为松称为松弛变量，将不等式改为等式。弛变量，将不等式改为等式。 如如(iii)若约束条件是大于等于型，则在该约束若约束条件是大于等于型，则在该约束条件不等式左边减去一个新变量条件不等式左边减去一个新变量称为剩称为剩余变量，将不等式改为等式。余变量，将不等式改为等式。 如如2929一般形式转化为标准型一般形式转化
14、为标准型(iv)若某个约束方程右端项若某个约束方程右端项 ，则在约，则在约束方程两端乘以（束方程两端乘以（-1），不等号改变方向，），不等号改变方向，然后再将不等式化为等式。然后再将不等式化为等式。(v) 若变量若变量xj无非负约束，则引入非负变量无非负约束，则引入非负变量xj0, xj0, 令令xj=xj-xj”.3030例例将线性规划将线性规划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+3
15、x3s.t. x1+x2+x3-x3+x4=7 x1-x2+x3-x3-x5=2 -3x1-x2+2x3-2x3=5 x1,x2,x3,x3,x4,x503131例例将线性规划将线性规划max y=250x1+350x2s.t. 5x1+6x2 2508x1+6x2 30010x1+20x2=-700x10, x2 0化为标准型化为标准型解解:令令x2= -x2,得到标得到标准型准型min -y=-250x1+350x2s.t. 5x1-6 x2 -x3 =2508x1-6x2 +x4 = 300-10x1+20x2=700x1 0, x2 0, x3 0, x4 03232基本概念基本概念设
16、约束矩阵设约束矩阵A的秩为的秩为m (行满秩行满秩),且且mn,则则A中中必存在必存在m阶非奇异子阵阶非奇异子阵B,不妨设不妨设B=(p1,p2,pm)称称B为线性规划问题为线性规划问题(LP)的一个的一个基矩阵基矩阵,或称为或称为基基,基矩阵中的列向量称为基矩阵中的列向量称为基向量基向量,对应的决策变量称为对应的决策变量称为基变量基变量,其余变量称为其余变量称为非基变量非基变量.3333基本概念基本概念在约束方程组取定基矩阵在约束方程组取定基矩阵B=(p1,p2,pm)之后之后,令非基变量均为令非基变量均为0,得到的方程组得到的方程组p1x1+p2x2+pmxm=b有唯一解有唯一解,这样得到
17、约束方程组的一个解向量这样得到约束方程组的一个解向量x=(x1,x2, xm)T通过这种方法得到的满足约束方程组的解称为通过这种方法得到的满足约束方程组的解称为基矩阵基矩阵B对应的对应的基解基解.3434基本概念基本概念如果基解又满足非负条件如果基解又满足非负条件,则称之为则称之为基可行解基可行解.此时的基此时的基B称为可行基称为可行基.基可行解中非零分量的个数不会超过基可行解中非零分量的个数不会超过m,若基若基可行解中非零分量的个数恰为可行解中非零分量的个数恰为m,称此基可行称此基可行解为解为非退化的基可行解非退化的基可行解,否则称为否则称为退化的基可退化的基可行解行解.若一个线性规划的所有
18、基可行解都是非退化的若一个线性规划的所有基可行解都是非退化的,称此线性规划是非退化的称此线性规划是非退化的.线性规划线性规划(LP)的基解个数不会超过的基解个数不会超过3535例例例例 考虑线性规划考虑线性规划考虑线性规划考虑线性规划min 2min 2x x1 1- -x x2 2s.ts.t. . x x1 1+ +x x2 2+ +x x3 3 =5=5 - -x x1 1- -x x2 2 + +x x4 4 =0=0 2 2x x1 1+2+2x x2 2 + +x x5 5=22=22 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 500该线性规
19、划有该线性规划有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,
20、5,0,22)T退退化化36362.3 线性规划的线性规划的基本定理基本定理3737本节的基本定理要说明要找线性规划的最优本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了解只需在基可行解中选择就可以了,这样将选这样将选择的范围控制在有限个择的范围控制在有限个.定理定理2.3.1 设设x是标准型线性规划是标准型线性规划(LP)的可行解的可行解,x为为(LP)的基可行解的充要条件是的基可行解的充要条件是,x的正分的正分量对应的系数列向量线性无关量对应的系数列向量线性无关.3838定理定理2.3.2 设设x是标准型线性规划是标准型线性规划(LP)的可行解的可行解,x为为(LP)的
21、基可行解的充要条件是的基可行解的充要条件是,x为可行域为可行域D的的极点极点.证明证明: 必要性必要性 不妨设不妨设x=(x1,x2,xm,0,0)T是是(LP)的基的基可行解可行解,且且x1,x2,xm是基变量是基变量,假设有假设有u,vD,0a a 0.假设假设x不是基可行解不是基可行解,于是于是p1,p2, ,pk线线性相关性相关,即有一组不全为即有一组不全为0的数的数a a1,a a2, ,a ak,使得使得a a1p1+a a2p2+ +a akpk=0 (2.4) 又又xD,所以所以 x1p1+x2p2+ +xkpk=b (2.5)用用e e 0乘乘(2.4)再与再与(2.5)相加
22、减得相加减得(x1+eaea1)p1+(x2+eaea2)p2+ +(xk+eaeak)pk=b(x1eaea1)p1+(x2eaea2)p2+ +(xkeaeak)pk=b4040令令u=(x1+eaea1,x2+eaea2, ,xk+eaeak,0, ,0)Tv=(x1eaea1,x2eaea2, ,xkeaeak,0, ,0)T则有则有Au=b,Av=b,当当e e充分小时充分小时,可使可使u0,v0.因此因此,当当e e充分小时充分小时,u,v都是都是(LP)的可行解的可行解,且且uv, x=1/2 u+1/2 v,这与这与x是是D的极点相矛盾的极点相矛盾.因此因此x是基可行解是基可行
23、解.推论推论:线性规划线性规划(LP)的可行域的可行域D=x|Ax=b,x0最多具有有限个极点最多具有有限个极点4141(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退退化化前例中三个退化的基可行解对前例中三个退化的基可行解对应着同一个极
24、点应着同一个极点(基可行解与基可行解与极点不是一一对应极点不是一一对应)4242有可行解有可行解有基可行解有基可行解定理定理2.3.3 若线性规划若线性规划(LP)存在可行解存在可行解,则它一则它一定存在基可行解定存在基可行解.4343有最优解有最优解有最优的基可行解有最优的基可行解 定理定理2.3.4 若线性规划若线性规划(LP)存在最优解存在最优解,则必存在则必存在 基可行解是最优解基可行解是最优解.4444单纯形方法的思路单纯形方法的思路找出一基可行解找出一基可行解(极点极点)若其不是最优若其不是最优,找到一个相邻极点找到一个相邻极点新的目标函数值不大于原目标函数值新的目标函数值不大于原
25、目标函数值经过有限次迭代给出最优解或判断无最优解经过有限次迭代给出最优解或判断无最优解4545单纯形方法的思路单纯形方法的思路(几何几何)线性规划线性规划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,x204646OABCD梯度方向梯度方向x2=0x1=0x5=0x3=0x4=0等等值值线线基可行解基可行解O4747OABCDx2=0x1=0x5=0x3=0
26、x4=0基可行解基可行解A4848OABCDx2=0x1=0x5=0x3=0x4=0基可行解基可行解B4949OABCDx2=0x1=0x5=0x3=0x4=0基可行解基可行解C是最优解是最优解5050单纯形方法的思路单纯形方法的思路(代数代数)例例 考察线性规划考察线性规划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的取
27、值的取值可以使得目标函数可以使得目标函数值减少值减少.类似的类似的,我们也可以我们也可以增加增加x2的取值的取值,使得使得目标函数值减少目标函数值减少.由于由于-72负得多一些负得多一些,我们先增加我们先增加x1.5151单纯形方法的思路单纯形方法的思路(代数代数)min -72x1-64x2s.t. x1 +x2+x3 =50 12x1+8x2 +x4 =490 3x1 +x5=100 x1,x2,x3,x4,x50x1可以增加多少可以增加多少?x150x1490/12x1100/3因此因此x1的最大取值为的最大取值为min(50,490/12,100/3)=100/3此时此时x5的取值为的
28、取值为0, x5“出基出基”.5252单纯形方法的思路单纯形方法的思路(代数代数)根据根据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/3x290/8因此因此x2的最大取值为的最
29、大取值为min(50/3,90/8)=90/8x4“出基出基”.5353单纯形方法的思路单纯形方法的思路(代数代数)此时此时,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.对应的对应的,线性规划线性规划可以转化为下页可以转化为下页的形式的形式5454单纯形方法的思路单纯形方法的思路(代数代数)min 48x3
30、+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.5555单纯形方法的思路单纯形方法的思路(代数代数)单纯形方法求解线性规划单纯形方法求解线性规划,首先找出一个基可首先找出一个基可行解行解.将目标函数写成非基变量的线性组合将目标函数写成非基变量的线性组合(再
31、加上一个常数再加上一个常数)的形式的形式.如果组合的系数全部非负如果组合的系数全部非负,则已经找到最优解则已经找到最优解.如果组合的系数中有负数如果组合的系数中有负数,从中选取一个变量从中选取一个变量(“进基进基”)来增加取值来增加取值,可以使得函数值减少可以使得函数值减少.根据约束条件根据约束条件,可以控制增加的范围可以控制增加的范围.在进基变量取最大值时在进基变量取最大值时,有一个变量出基有一个变量出基,从从而得到另一个基可行解而得到另一个基可行解.重复上面的过程重复上面的过程,可以求得最优解可以求得最优解.56562.4 单纯形方法单纯形方法5757设线性规划设线性规划R(A)=m，x1
32、,x2, ,xm是基变量，而是基变量，而xm+1, ,xn是是非基变量，并记基矩阵非基变量，并记基矩阵B=(p1,p2, ,pm),N= (pm+1, ,pn),A=(B,N), 则上述线性规划问题化为则上述线性规划问题化为5858进一步可以将线性规划问题转化为以下形式进一步可以将线性规划问题转化为以下形式5959规范式规范式线性规划与基变量线性规划与基变量x1,xm对应的对应的规范规范式式线性规划与基变量线性规划与基变量xj1,xjm对应的对应的规范规范式式S=j1,jm,T=1,2,nS60602.4.1 基可行解是最优解的判断准则基可行解是最优解的判断准则在规范式在规范式中中,令非基变量
33、令非基变量xj=0,jT,得到一个基解得到一个基解x0=(x1,xn)T,其中其中如果如果bj0(jS),则则x0是基可行解是基可行解.6161最优性条件最优性条件目标函数中各个变量的系数就是判别数目标函数中各个变量的系数就是判别数.在规范式在规范式 中中,定理定理2.4.1 设设x0是线性规划是线性规划(LP)对应于基对应于基B=(pj1,pjm)的基可行解的基可行解.与基变量与基变量xj1,xjm对应的规范式中对应的规范式中,若若x0的全体判别数的全体判别数非负非负,则则x0是是(LP)的最优解的最优解.6262判断无最优解判断无最优解定理定理2.4.2设设x0是线性规划是线性规划(LP)
34、对应于基对应于基B=(p1,pm)的基可行解的基可行解.与基变量与基变量x1,xm对应的规范式中对应的规范式中,若存在若存在s sk0,且对所有的且对所有的i=1,2,m有有aik0,则则线性规划线性规划(LP)无最优解无最优解.6363基可行解的转换基可行解的转换从上面定理可以看出从上面定理可以看出,如果某个判别数为负时如果某个判别数为负时,可以构造新的可行解可以构造新的可行解,使得目标函数值减少使得目标函数值减少.1. 确定进基变量确定进基变量负的判别数对应的变量都可以作为进基变量负的判别数对应的变量都可以作为进基变量.一般的一般的,若若s sk=mins sj|s sj0=bl/alk=
35、q ql,则称第则称第l 行为主行，与主行所对应的基变量行为主行，与主行所对应的基变量xl为离基变量为离基变量.6565单纯形方法单纯形方法如果线性规划是非退化的如果线性规划是非退化的,则按照上面的方法则按照上面的方法(进基进基,离基离基)迭代一次后迭代一次后,目标函数值有所下目标函数值有所下降降.经过有限次迭代之后经过有限次迭代之后,一定可以得到一个一定可以得到一个基可行解基可行解,使得其所有判别数非负使得其所有判别数非负(得到最优得到最优解解),或者其有一个判别数是负的或者其有一个判别数是负的,但对应列向但对应列向量的所有分量非正量的所有分量非正(线性规划无最优解线性规划无最优解).这种求
36、解线性规划的方法称为单纯形方法这种求解线性规划的方法称为单纯形方法.66662.5 单纯形表单纯形表6767建立实用单纯形表以下是初始单纯形表：以下是初始单纯形表：以下是初始单纯形表：以下是初始单纯形表： 6868例例2.5.1 用单纯形法用单纯形法解线性规划解线性规划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,x606
37、969显然显然p3,p4,p5,p6是一是一组基组基, 标准型线性规标准型线性规划中的系数以及这一划中的系数以及这一组基可用表格的形式组基可用表格的形式给出给出min min f f = -2= -2x x1 1-3-3x x2 2s s. .t t. . x x1 1+ +x x2 2+ +x x3 3 =6=6 x x1 1+2+2x x2 2 + +x x4 4 =8=8 x x1 1 + +x x5 5 =4=4 x x2 2 + +x x6 6=3=3 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 600目标函数中的系数基向量基变
38、量的价格系数右端系数约束等式的系数cj -2 -3 0 0 0 0 p1 p2 p3 p4 p5 p6 Bp3p4p5p6cB0000b6843 1 1 1 0 0 01 2 0 1 0 01 0 0 0 1 00 1 0 0 0 17070第一步的判别数第一步的判别数:由于在此例中基变量的价格由于在此例中基变量的价格系数均为系数均为0,所以判别数就是价格系数所以判别数就是价格系数.cj-2 -3 0 0 0 0cBBbp1 p2 p3 p4 p5 p60000p3p4p5p668431 1 1 0 0 01 2 0 1 0 01 0 0 0 1 00 1 0 0 0 1s sj -2 -3
39、0 0 0 0进基变量进基变量:s s2=-3=mins sj|s sj0)q qi64/3离基变量离基变量: q q6 =minq qi ,所以所以x6为离基变量为离基变量( )-33标出主元标出主元7171第二步迭代过程第二步迭代过程cj-2 -3 0 0 0 0q qi icBBbp1 p2 p3 p4 p5 p60000p3p4p5p668431 1 1 0 0 01 2 0 1 0 01 0 0 0 1 00 (1) 0 0 0 164/3sj-2 -3 0 0 0 0p3p4p5p2 写出基向量(p6换成p2)归一化:若主元不等于1,则进行行变换,将主元变为1(此处不变)3 0 1
40、 0 0 0 1写出价格系数000-3消去:用初等行变换将主元所在列其它元素消为0p5所在行不变4 1 0 0 0 1 0p2所在行乘以-1加到p3所在行3 1 0 1 0 0 -1p2所在行乘以-2加到p4所在行2 1 0 0 1 0 -2p2所在行乘以3加到判别数所在行 s sj -2 0 0 0 0 37272第二步迭代过程第二步迭代过程cj-2 -3 0 0 0 0q q q qi icBBbp1 p2 p3 p4 p5 p60000p3p4p5p668431 1 1 0 0 01 2 0 1 0 01 0 0 0 1 00 (1) 0 0 0 16 64 4/ /3s sj-2 -3
41、 0 0 0 0p3p4p5p2 3 0 1 0 0 0 1000-34 1 0 0 0 1 03 1 0 1 0 0 -12 1 0 0 1 0 -2 s sj -2 0 0 0 0 37373cj-2 -3 0 0 0 0cBBbp1 p2 p3 p4 p5 p6000-3p3p4p5p232431 0 1 0 0 -11 0 0 1 0 -21 0 0 0 1 00 1 0 0 0 1s sj -2 0 0 0 0 3进基变量进基变量:s s1=-2=mins sj|s sj0)q qi324/离基变量离基变量: q q4=2=minq qi , x4为离基变量为离基变量( )-22标出
42、主元标出主元7474第三步迭代过程第三步迭代过程cj-2 -3 0 0 0 0q q q qi icBBbp1 p2 p3 p4 p5 p6000-3p3p4p5p232431 0 1 0 0 -1(1) 0 0 1 0 -21 0 0 0 1 00 1 0 0 0 13 32 24 4/s sj-2 0 0 0 0 3p3p1p5p2 写出基向量写出基向量(p4换成换成p1)归一化归一化:若主元不等于若主元不等于1,则进行则进行行变换行变换,将主元变为将主元变为1(此处不变此处不变)3 0 1 0 0 0 1写出价格系数写出价格系数0-20-3消去消去:用初等行变换将主元所在列其它元素消为用
43、初等行变换将主元所在列其它元素消为0p2所在行不变所在行不变2 0 0 0 -1 1 2p1所在行乘以所在行乘以-1加到加到p3所在行所在行1 0 0 1 -1 0 1p1所在行乘以所在行乘以-1加到加到p5所在行所在行2 1 0 0 1 0 -2p1所在行乘以所在行乘以2加到判别数所在行加到判别数所在行 s sj 0 0 0 2 0 -17575第三步迭代过程第三步迭代过程cj-2 -3 0 0 0 0q q q qi icBBbp1 p2 p3 p4 p5 p6000-3p3p4p5p232431 0 1 0 0 -1(1) 0 0 1 0 -21 0 0 0 1 00 1 0 0 0 1
44、3 32 24 4/s sj-2 0 0 0 0 3p3p1p5p2 3 0 1 0 0 0 10-20-32 0 0 0 -1 1 21 0 0 1 -1 0 12 1 0 0 1 0 -2 s sj 0 0 0 2 0 -17676cj-2 -3 0 0 0 0cBBbp1 p2 p3 p4 p5 p60-20-3p3p1p5p212230 0 1 -1 0 11 0 0 1 0 -20 0 0 -1 1 20 1 0 0 0 1s sj 0 0 0 2 0 -1进基变量进基变量:s s6= 1=mins sj|s sj0)q qi1/13离基变量离基变量: q q5=1=minq qi
45、, x5为离基变量为离基变量(此处可选此处可选x3)( )-11标出主元标出主元7777第四步迭代过程第四步迭代过程cj-2 -3 0 0 0 0q qi icBBbp1 p2 p3 p4 p5 p60-20-3p3p1p5p212230 0 1 -1 0 11 0 0 1 0 -20 0 0 -1 1 (2)0 1 0 0 0 11/13sj0 0 0 2 0 -1p3p1p6p2 写出基向量(p5换成p6)归一化:若主元不等于1,则进行行变换,将主元变为1(此处除以2)2 0 1 0 - 0写出价格系数0-20-3消去:用初等行变换将主元所在列其它元素消为01 0 0 0 - 1p6所在行
46、乘以-1加到p3所在行0 0 0 1 - - 0p6所在行乘以2加到p1所在行4 1 0 0 0 1 0p6所在行乘以1加到判别数所在行 s sj 0 0 0 3/2 0p6所在行乘以-1加到p2所在行7878第四步迭代过程第四步迭代过程cj-2 -3 0 0 0 0q q q qi icBBbp1 p2 p3 p4 p5 p60-20-3p3p1p5p212230 0 1 -1 0 11 0 0 1 0 -20 0 0 -1 1 (2)0 1 0 0 0 11 1/ /1 13s sj0 0 0 2 0 -1p3p1p6p2 2 0 1 0 - 00-20-31 0 0 0 - 10 0 0
47、 1 - - 04 1 0 0 0 1 0 s sj 0 0 0 3/2 07979cj-2 -3 0 0 0 0cBBbp1 p2 p3 p4 p5 p60-20-3p3p1p6p204120 0 1 -1/2 -1/2 01 0 0 0 1 00 0 0 -1/2 1/2 10 1 0 1/2 -1/2 0s 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.80802.6 初始
48、基可行解的求法初始基可行解的求法8181对于线性规划问题对于线性规划问题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为初始基可行解进为初始基可行解进行单纯形迭代行单纯形迭代.对于一般的线性规划问题对于一般的线性规划问题,无法简单给出初始无法简单给出初始基可行解基可行解.8282 为了使初始可行基成为一个单位矩阵，为了使初始可行基成为一个单位矩阵，在有些约束条件中需要加
49、入人工变量，但加在有些约束条件中需要加入人工变量，但加入人工变量后的数学模型与未加入人工变量入人工变量后的数学模型与未加入人工变量的数学模型一般是不等价的。在这一点上，的数学模型一般是不等价的。在这一点上，人工变量与松弛变量或剩余变量是不同的，人工变量与松弛变量或剩余变量是不同的，松弛变量或剩余变量只是将不等式改写为等松弛变量或剩余变量只是将不等式改写为等式，而改写前后，两个约束是等价的。式，而改写前后，两个约束是等价的。83832.6.1 大大M单纯形法单纯形法对于线性规划问题对于线性规划问题引入人工变量引入人工变量xn+1,xn+m,构造辅助线性规构造辅助线性规划问题划问题8484 M是相
50、当大的正数是相当大的正数(可以理解为正无穷可以理解为正无穷),对对人工变量起到惩罚的作用人工变量起到惩罚的作用,逼迫辅助线性规划的逼迫辅助线性规划的最优解中人工变量均为最优解中人工变量均为0. 上述辅助线性规划模型与原规划模型一般上述辅助线性规划模型与原规划模型一般是不等价的，只有当最优解中，人工变量都取是不等价的，只有当最优解中，人工变量都取零值时，才可认为两个问题的最优解是相当的。零值时，才可认为两个问题的最优解是相当的。关于这一点有以下的结论：关于这一点有以下的结论： （1）辅助线性规划问题的最优解中，人工变）辅助线性规划问题的最优解中，人工变量都处在非基变量位置（即取零值），则原问量都
51、处在非基变量位置（即取零值），则原问题有最优解，且将前者最优解中去掉人工变量题有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。部分即为后者最优解。8585（2）若辅助线性规划问题的最优解中包含非零）若辅助线性规划问题的最优解中包含非零的人工变量，则原问题无可行解。的人工变量，则原问题无可行解。（3）若辅助线性规划问题的最优解的基变量中）若辅助线性规划问题的最优解的基变量中包含人工变量，但该人工变量取值为包含人工变量，但该人工变量取值为0，这时可，这时可将某个非基变量引入基变量中来替换该人工变将某个非基变量引入基变量中来替换该人工变量，从而得到原问题的最优解。量，从而得到原问题的最优解
52、。 8686大大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注注:根据线性规划问题本身的形式根据线性规划问题本身的形式,可以少引可以少引进进
53、一些人工变量一些人工变量.8787单纯形方法求解单纯形方法求解第一步的判别数第一步的判别数:s s1=-3-10-(-4)M-(-2)M=6M-3类似地可以给出其它各个判别数类似地可以给出其它各个判别数.cj-3 1 1 0 0 M McBBb p1 p2 p3 p4 p5 p6 p7 0MMp5p6p711311 -2 1 0 1 0 0-4 1 2 -1 0 1 0-2 0 1 0 0 0 1s sj 6M-3 -M+1 -3M+1 M 0 0 0q qi113/2 1x3进基进基, x7离基离基,标出主元标出主元.( )注注:人工变量一旦离基人工变量一旦离基,则在迭代时不再参与计算则在迭
54、代时不再参与计算.8888续表续表cj-3 1 1 0 0 M McBBb p1 p2 p3 p4 p5 p6 p7 0MMp5p6p711311 -2 1 0 1 0 0-4 1 2 -1 0 1 0-2 0 (1) 0 0 0 1s s j6M-3 -M+1 -3M+1 M 0 0 0 0M1p5p6p310113 -2 0 0 1 0 0 1 0 -1 0 1 -2 0 1 0 0 0 s s j-1 -M+1 0 M 0 0 89890M1p5p6p310113 -2 0 0 1 0 0 (1) 0 -1 0 1 -2 0 1 0 0 0 /1/s s j-1 -M+1 0 M 0 0
55、 011p5p2p31211(3) 0 0 -2 1 0 1 0 -1 0 -2 0 1 0 0 4/s s j-1 0 0 1 0 -311p1p2p34191 0 0 -2/3 1/3 0 1 0 -1 0 0 0 1 -4/3 2/3 s s j0 0 0 1/3 1/3 9090求得辅助规划问题的最优解为求得辅助规划问题的最优解为 (4,1,9,0,0,0,0)T ,原线性规划的最优解为原线性规划的最优解为(4,1,9,0)T,最优值为最优值为-34+13+19=-2.注注:根据各个判别数根据各个判别数,可以发现可以发现M应满足应满足3M+1M+1,3M+16M3,M+12.在实际问题
56、中可以取在实际问题中可以取M为适当大的一个数为适当大的一个数,比比如比问题中的系数大一个数量级如比问题中的系数大一个数量级.91912.6.2 两阶段单纯形法两阶段单纯形法对于线性规划问题对于线性规划问题引入人工变量引入人工变量xn+1,xn+m,构造辅助线性规构造辅助线性规划问题划问题9292 将上述辅助线性规划问题拆成两个线性将上述辅助线性规划问题拆成两个线性规划，即为两阶段法。第规划，即为两阶段法。第1阶段求解第阶段求解第1个线个线性规划，第性规划，第1个线性规划的目标函数是对所个线性规划的目标函数是对所有人工变量之和求最小。有人工变量之和求最小。（1）若求得的最优解中，所有人工变量都）
57、若求得的最优解中，所有人工变量都处在非基变量的位置，即，则从第处在非基变量的位置，即，则从第1阶段的阶段的最优解中去掉人工变量后，即为原问题的一最优解中去掉人工变量后，即为原问题的一个基本可行解，作为原问题的一个初始基本个基本可行解，作为原问题的一个初始基本可行解，再求解原问题，从而进入第可行解，再求解原问题，从而进入第2阶段。阶段。9393（2）假若求得第）假若求得第1阶段的最优解中，至少有阶段的最优解中，至少有一个人工变量不为零值，则说明添加人工变一个人工变量不为零值，则说明添加人工变量之前的原问题无可行解，不再需要进入第量之前的原问题无可行解，不再需要进入第2阶段。阶段。 因此两阶段法的
58、第因此两阶段法的第1阶段求解，有两个阶段求解，有两个目的：一为判断原问题有无可行解；二，若目的：一为判断原问题有无可行解；二，若有，则可求得原问题的一个初始基本可行解，有，则可求得原问题的一个初始基本可行解，再对原问题进行第再对原问题进行第2阶段的计算。阶段的计算。9494两阶段法算例两阶段法算例例例2.6.2 用两阶段用两阶段法求解线性规划法求解线性规划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+3
59、x2+x3 +x5=3x1,x2,x3,x4,x509595单纯形表单纯形表cj 0 0 0 1 1q q q qi icBBb p1 p2 p3 p4 p5 11p4p543 2 1 2 1 0(3) 3 1 0 121s s j-5 -4 -3 0 010p4p121 0 -1 (4/3) 1 1 1 1/3 0 3/23s s j 0 1 -4/3 000p3p13/21/2 0 -3/4 1 1 5/4 0 s s j 0 0 09696单纯形表单纯形表cj 0 0 0 1 1q q q qi icBBb p1 p2 p3 p4 p5 11p4p543 2 1 2 1 0(3) 3 1
60、 0 021s s j-5 -4 -3 0 010p4p121 0 -1 (4/3) 1 1 1 1/3 0 3/23s s j 0 1 -4/3 000p3p13/21/2 0 -3/4 1 1 5/4 0 s s j 0 0 0最最优解解(1/2,0,3/2 0,0)T,最最优值w*=0,由此得到原由此得到原线性性规划的一个基可行解划的一个基可行解x0=(1/2,0,3/2)T.将上表的最后部分将上表的最后部分转到新的到新的单纯形表中形表中(求解原求解原线性性规划划),不不过判判别数要重新数要重新计算算.9797求解原线性规划的单纯形表求解原线性规划的单纯形表得到原线得到原线性规划的性规划
61、的最优解最优解x*=(0,2/5,9/5)T,最优值最优值f*=11/5.cj 4 1 1q q q qi icBBb p1 p2 p314p3p13/21/2 0 -3/4 1 1 (5/4) 0 /2/5s s j 0 -13/4 011p3p29/52/5 3/5 0 1 4/5 1 0 s s j13/5 0 098982.7 线性规划的线性规划的对偶理论对偶理论9999假设某工厂有假设某工厂有m种设备种设备:B1,B2, ,Bm.一一年内各设备的生产能力年内各设备的生产能力(有效台时数有效台时数)为为b1,b2, ,bm.利用这些设备可以加工利用这些设备可以加工n种种产品产品:A1,
62、A2, ,An,单位产品的利润分别单位产品的利润分别为为c1,c2, ,cn.第第j种产品需要在第种产品需要在第i种设种设备上加工的台时数为备上加工的台时数为aij.问在设备能力允许的问在设备能力允许的条件下怎样安排生产计划条件下怎样安排生产计划,使全年总收入最多使全年总收入最多?设设x1,x2, ,xn为各产品的计划年产量为各产品的计划年产量,s为全年总收入为全年总收入,易建立该问题的数学模型易建立该问题的数学模型.100100假设某工厂有假设某工厂有m种设备种设备:B1,B2, ,Bm.一一年内各设备的生产能力年内各设备的生产能力(有效台时数有效台时数)为为b1,b2, ,bm.利用这些设
63、备可以加工利用这些设备可以加工n种种产品产品:A1,A2, ,An,单位产品的利润分别单位产品的利润分别为为c1,c2, ,cn.第第j种产品需要在第种产品需要在第i种设种设备上加工的台时数为备上加工的台时数为aij.问在设备能力允许的问在设备能力允许的条件下怎样安排生产计划条件下怎样安排生产计划,使全年总收入最多使全年总收入最多?设设x1,x2, ,xn为各产品的计划年产量为各产品的计划年产量,s为全年总收入为全年总收入,易建立该问题的数学模型易建立该问题的数学模型.101101对偶问题对偶问题假设工厂将所有的设备用于出租假设工厂将所有的设备用于出租,需要给各种需要给各种设备制定出租价格设备
64、制定出租价格.定价原则有两条定价原则有两条:一是出一是出租后得到的单位利润不得少于直接生产时的租后得到的单位利润不得少于直接生产时的收入收入,二是出租价格尽量的低二是出租价格尽量的低,以利于市场竞以利于市场竞争争.设第设第i种设备种设备Bi的单位台时的出租价格为的单位台时的出租价格为yi,全全年总收入为年总收入为w,则该问题的数学模型为则该问题的数学模型为102102对偶问题对偶问题假设工厂将所有的设备用于出租假设工厂将所有的设备用于出租,需要给各种需要给各种设备制定出租价格设备制定出租价格.定价原则有两条定价原则有两条:一是出一是出租后得到的单位利润不得少于直接生产时的租后得到的单位利润不得
65、少于直接生产时的收入收入,二是出租价格尽量的低二是出租价格尽量的低,以利于市场竞以利于市场竞争争.设第设第i种设备种设备Bi的单位台时的出租价格为的单位台时的出租价格为yi,全全年总收入为年总收入为w,则该问题的数学模型为则该问题的数学模型为103103可以看出可以看出,原始规原始规划与对偶规划是划与对偶规划是同一组数据参数同一组数据参数,只是位置有所不只是位置有所不同同,所描述的问题所描述的问题实际上是同一个实际上是同一个问题从另一种角问题从另一种角度去描述度去描述.原始线性规划原始线性规划对偶线性规划对偶线性规划104104对称形势下对偶问题的一般形式对称形势下对偶问题的一般形式定义定义2
66、.7.1 满足下列条件的线性规划问题称为具有对称形 式：其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取“”号。105105对称形势下对偶问题的一般形式对称形势下对偶问题的一般形式原始线性规划原始线性规划 min cTx(LP) s.t.Axb x 0对偶线性规划对偶线性规划 max bTy(DP) s.t. ATyc y 0cATbTmaxmnminbAcTmn106106对合性对合性定理定理2.7.1 对偶线性规划的对偶问题是原始线对偶线性规划的对偶问题是原始线性规划问题性规划问题max -cTxs.t. Axbx0min bTys.t. ATy cy0m
67、ax bTys.t. ATycy 0min cTxs.t. Axb x0对偶对偶定义定义对偶对偶定义定义107107例例例例 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型108108解：按照对称形式的对偶关系，其对偶模型为109109非对称形式下对偶线性规划非对称形式下对偶线性规划 并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对偶问题。 原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系： 目标函数类型之间的对应关系 目标函数系数与右边项的对应关系 约束系数矩阵之间的对应关系
68、约束类型与变量类型之间的对应关系110110 由于前面三个对应关系与标准形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:111111例 写出下列线性规划问题的对偶问题（1 1）112112 答案：113113（2 2）114114 答案：115115116116117117对偶规划的性质对偶规划的性质考虑如下的线性规划考虑如下的线性规划 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
69、 0 y y1 1， y y2 2 无约束无约束118118对偶规划的性质对偶规划的性质(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)在在可行解上的取值可行解上的取值;若两者取值相等若两者取值相等,则对应的解都是最优解则对应的解都是最优解.11911
70、9弱对偶性定理弱对偶性定理标准型线性规划标准型线性规划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定理定理2.7.4 极小化线性规划问题的目标函数值极小化线性规划问题的目标函数值不小于其对偶规划的目标函数值不小于其对偶规划的目标函数值.120120定理定理定理定理2.7.5 (2.7.5 (最优性最优性最优性最优性) )若若若若x x0 0是原始线
71、性规划的可行解是原始线性规划的可行解是原始线性规划的可行解是原始线性规划的可行解, ,y y0 0是对偶线性规划的可行解是对偶线性规划的可行解是对偶线性规划的可行解是对偶线性规划的可行解, ,且且且且c cT Tx x0 0= =b bT Ty y0 0, ,则则则则x x0 0与与与与y y0 0分别是原始线性规划问题与对偶线性规划问题分别是原始线性规划问题与对偶线性规划问题分别是原始线性规划问题与对偶线性规划问题分别是原始线性规划问题与对偶线性规划问题的最优解的最优解的最优解的最优解. .证明：证明：证明：证明：121121定理定理2.7.6 若原始线性规划问题与对偶线性规若原始线性规划问
72、题与对偶线性规划问题之一具有无界的目标函数值划问题之一具有无界的目标函数值,则另一个则另一个无可行解无可行解.即即：若原问题有可行解而其对偶问题无可：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。对偶问题的目标函数值无界。122122对偶的线性规划问题的解对偶的线性规划问题的解两个互为对偶的线性规划的解的情况两个互为对偶的线性规划的解的情况(1) 两个都有可行解两个都有可行解(2)两个都无可行解两个都无可行解两个都有最优解两个都有最优解,最
73、优值相最优值相等等一个有最优解一个有最优解(3)一个有可行解一个有可行解,无最优解无最优解(目标函数无界目标函数无界),则另一个无可行解则另一个无可行解123123互补松弛性互补松弛性(ATy-c)Tx=0bTy=cTxAx=b 定理定理2.7.8 x,y分别是原始线性规划问题与对偶线分别是原始线性规划问题与对偶线性规划的可行解性规划的可行解,则则x,y分别是最优解的充要条件分别是最优解的充要条件为为(ATy-c)Tx=0.124124互补松弛性互补松弛性原始线性规划原始线性规划原始线性规划原始线性规划min min f f = -2= -2x x1 1-3-3x x2 2s.ts.t. .
74、x x1 1+ +x x2 2+ +x x3 3 =6=6 x x1 1+2+2x x2 2 + +x x4 4 =8=8 x x1 1 + +x x5 5 =4=4 x x2 2 + +x x6 6=3=3 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 600对偶线性规划对偶线性规划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,
75、-1/2,0)T.对偶规划对偶规划y*的松弛量的松弛量q=c-ATy=(0,0,0,3/2,1/2,0)T互补松弛性互补松弛性:qTx=01251252.8 对偶单纯形法对偶单纯形法1261261. 最优解的判别最优解的判别已知线性规划问题的基矩阵已知线性规划问题的基矩阵B及它对应的基解及它对应的基解,并且此基解的所有判别数非负并且此基解的所有判别数非负.若若xB=B-1b0则所得的基解为最优解则所得的基解为最优解1271272. 确定离基变量确定离基变量令令min(B-1b)i|(B-1b)i0=(B-1b)l ,则以则以xl为离基变量为离基变量若若xl所在行的所有系数所在行的所有系数alj
76、0(j=1,2,n),则线性则线性规划问题无可行解规划问题无可行解.1281283.确定进基变量确定进基变量设目标函数的形式为设目标函数的形式为已确定离基变量为已确定离基变量为xl,设进基变量为设进基变量为xk.在目标在目标函数中函数中,用用xk替换替换xl,令令则则xk为进基变量为进基变量129129算例算例例例2.8.1 用对偶单纯形法解线性规划用对偶单纯形法解线性规划min z= 12x1+8x2+16x3+12x4s.t. 2x1+x2+4x3 2 2x1+2x2 +4x4 3 x1,x2,x3,x40min z= 12x1+8x2+16x3+12x4 s.t. 2x1-x2-4x3
77、+x5 = 2 2x1-2x2 -4x4 +x6= 3 x1,x2,x3,x4,x5,x60引入松弛变引入松弛变量得到标准量得到标准型线性规划型线性规划130130构造对偶单纯形表构造对偶单纯形表min z= 12x1+8x2+16x3+12x4 s.t. -2x1-x2-4x3 +x5 =-2 -2x1-2x2 -4x4 +x6=-3 x1,x2,x3,x4,x5,x60cj 12 8 16 12 0 0cBBbp1 p2 p3 p4 p5 p600p5p6-2-3 -2 -1 4 0 1 0 -2 -2 0 -4 0 1s sj 12 8 16 12 0 0s sj/alj(alj0) -
78、6 -4 -3 选取离基变量选取离基变量b6=-3=minbj|bj0-3选取进基变量选取进基变量s s4/a64=maxs sj/a6j|a6j0-3主元主元( )131131cj 12 8 16 12 0 0cBBbp1 p2 p3 p4 p5 p600p5p6-2-3 -2 -1 4 0 1 0 -2 -2 0 -4 0 1s sj 12 8 16 12 0 0s sj/alj(alj0) -6 -4 -3 012p5p4 s sj s sj/alj(alj0) 3/4 1/2 1/2 0 1 0 -1/4 6 2 16 0 0 3-2 -2 -1 -4 0 1 0-2-3 -2 -4-
79、2( )132132012p5p4-23/4-2 (-1) -4 0 1 0 1/2 1/2 0 1 0 -1/4s sj6 2 16 0 0 3s sj/alj(alj0)-3 -2 -4 812p2p42- 2 1 4 0 -1 0 - 0 -2 1 - s sj2 0 8 0 2 3s sj/alj(alj0)-4 -4 -12-4( )816p2p33/21/8 1 1 0 2 0 -1/2 0 1 - - 1/8 s sj0 0 0 4 4 2基解已基解已可行可行,最优最优解为解为x*=(0,3/2,1/8,0)T最优值最优值为为z*=141331332.9 灵敏度分析灵敏度分析13
80、4134灵敏度分析灵敏度分析在线性规划中在线性规划中,已经求得了最优解已经求得了最优解.若系数若系数cj,bi,aij等发生变化的时候等发生变化的时候,最优解是否最优解是否发生变化发生变化?怎样变化怎样变化?这一类问题称为灵敏度分析这一类问题称为灵敏度分析.通常通常,我们进行灵敏度分析时我们进行灵敏度分析时,都假设只有一都假设只有一个系数发生变化个系数发生变化.135135灵敏度分析灵敏度分析设已经用单纯形法求得线性规划设已经用单纯形法求得线性规划 min cTx(LP) s.t. Ax=b x0的最优解的最优解xB=B1b,基矩阵基矩阵B=(p1,p2,pm)(称为最优基称为最优基),最优值
81、最优值z*=cBTxB=cBTB1b.136136非基变量价格系数的变化非基变量价格系数的变化若若xr是非基变量是非基变量,其价格系数其价格系数cr的变化不影响的变化不影响解的可行性解的可行性.由于由于s sk=ck-cBTB-1pk,cr的变化只影响的变化只影响xr的判别的判别数数,不影响其它变量的判别数不影响其它变量的判别数.设设cr的变化量为的变化量为D Dcr ,s sr=cr+ D Dcr -cBTB-1pr= s sr + D Dcr因此因此,若若s sr + D Dcr 0,即即 D Dcr s sr 最优解最优解,最优值都不变最优值都不变.137137基变量价格系数的变化基变量
82、价格系数的变化若若xr是基变量是基变量,其价格系数其价格系数cr的变化不影响解的变化不影响解的可行性的可行性.由于由于s sk=ck-cBTB-1pk,cr变化时变化时,cB发生变化发生变化,所所有的非基变量的判别数都发生变化有的非基变量的判别数都发生变化.设设cr的变化量为的变化量为D Dcr ,cB=cB+D DcB其中其中D DcB=(0,0,D Dcr,0,0)Ts sj=cj cBTB-1pj= cj cBTB-1pjD D cBTB-1pj = s sjD Dcrarj138138基变量价格系数的变化基变量价格系数的变化s sj= s sjD Dcrarj在所有的判别数仍然非负时在
83、所有的判别数仍然非负时,最优解不变最优解不变,根根据上面的式子据上面的式子,可以得到可以得到maxs sj/arj | arj0在满足上述条件的情况下在满足上述条件的情况下,最优值由原来的最优值由原来的z*变为变为 z*+D Dcr xr实际讨论时实际讨论时,只要写出新的判别数只要写出新的判别数,然后解不然后解不等式即可求得价格系数的变化范围等式即可求得价格系数的变化范围.139139右端项的变化右端项的变化右端项变化右端项变化,原来的最优解不再可行原来的最优解不再可行.原原始始线线性性规规划划对对偶偶线线性性规规划划判别数不变判别数不变对偶解的可行性不变对偶解的可行性不变右端项的变化右端项的
84、变化价格系数的变化价格系数的变化最优基最优基B不变不变对偶解对偶解y=(cBTB-1)T的最优性不变的最优性不变按照基重新写出的按照基重新写出的基解的可行性不变基解的可行性不变判别数的非判别数的非负性不变负性不变什么条件下成立什么条件下成立?140140B仍然是最优基仍然是最优基?xB=B1(b+D Db)=B1b+B1D Db=xB+B1D Db,B1=(bij)mm,D Db=(0,0,D Dbr,0,0)TxB=xB+D Dbr(b1r,b2r,bmr)T,(xB)i=(xB)i+D Dbr bir,(i=1,2,m).当当xB0,即即(xB)i+D Dbr bir0时时,最优基最优基B
85、不变不变.即即max-(xB)i /bir | bir0D Dbrmin-(xB)i /bir | bir0141141影子价格影子价格(对偶最优解的经济解释对偶最优解的经济解释) 当线性规划原问题求得最优解当线性规划原问题求得最优解xj*(j=1,2n)时，其对偶问题也得到最优解时，其对偶问题也得到最优解yi*(i=1,.,m),代入各自的目标函数后有：代入各自的目标函数后有：其中，bi代表第i种资源的拥有量，对偶变量yi*的意义代表在资源最优利用条件下对单位资源i的估价。这种估计不是资源的市场价格，而是根据在生产中做出的贡献而作的估价，为区别一般意义的价格，我们将其（yi*）称为影子价格（
86、shadow price）142142影子价格的几点说明影子价格的几点说明1. 资源的市场价格是已知数，相对比较稳定，资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。况发生变化，资源的影子价格也随之改变。2. 影子价格是一种边际价格，在上式中对影子价格是一种边际价格，在上式中对Z求求bi的偏导数得的偏导数得这说明这说明yi*的值相当于在资源得到最优利用的值相当于在资源得到最优利用的生产条件下，的生产条件下，bi每增加
87、一个单位时目标函每增加一个单位时目标函数数Z的增量。的增量。143143影子价格的几点说明影子价格的几点说明3. 资源的影子价格实际上又是一种机会成本。资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当某一资源的市场价格在纯市场经济条件下，当某一资源的市场价格低于该影子价格时，可以买进这种资源；相反，低于该影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保随之发生变化，一直到影子价格与市场价格保持同等
88、水平时，才处于平衡状态。持同等水平时，才处于平衡状态。144144影子价格的几点说明影子价格的几点说明4.根据互补松弛定理，生产过程中如果某资根据互补松弛定理，生产过程中如果某资源源bi未得到充分利用，则该种资源的影子价未得到充分利用，则该种资源的影子价格为零；又当某资源的影子价格不为零时，格为零；又当某资源的影子价格不为零时，表明该种资源已消耗完毕。表明该种资源已消耗完毕。145145影子价格的几点说明影子价格的几点说明5. 5. 一般说来，对线性规划问题的求解是确定资源的一般说来，对线性规划问题的求解是确定资源的一般说来，对线性规划问题的求解是确定资源的一般说来，对线性规划问题的求解是确定
89、资源的最优分配方案，而对于对偶问题的求解则是确定对最优分配方案，而对于对偶问题的求解则是确定对最优分配方案，而对于对偶问题的求解则是确定对最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估计直接涉及资源的最有效资源的恰当估价，这种估计直接涉及资源的最有效资源的恰当估价，这种估计直接涉及资源的最有效资源的恰当估价，这种估计直接涉及资源的最有效利用。利用。利用。利用。 例如，在一个大公司内部，可借助资源的影子例如，在一个大公司内部，可借助资源的影子例如，在一个大公司内部，可借助资源的影子例如，在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的价格确定一些
90、内部结算价格，以便控制有限资源的价格确定一些内部结算价格，以便控制有限资源的价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。使用和考核下属企业经营的好坏。使用和考核下属企业经营的好坏。使用和考核下属企业经营的好坏。 又如，在社会上可对一些最紧缺的资源，借助又如，在社会上可对一些最紧缺的资源，借助又如，在社会上可对一些最紧缺的资源，借助又如，在社会上可对一些最紧缺的资源，借助影子价格规定使用这种单位资源时必须上交的利润影子价格规定使用这种单位资源时必须上交的利润影子价格规定使用这种单位资源时必须上交的利润影子价格规定使用这种单位资源时必须上交的利润额，以控制一些经济效益
91、低的企业自觉地节约使用额，以控制一些经济效益低的企业自觉地节约使用额，以控制一些经济效益低的企业自觉地节约使用额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。紧缺资源，使有限资源发挥更大的经济效益。紧缺资源，使有限资源发挥更大的经济效益。紧缺资源，使有限资源发挥更大的经济效益。1461462.10 整数线性规划整数线性规划147147整数线性规划整数线性规划如果线性规划的全部或部分变量要求取为整如果线性规划的全部或部分变量要求取为整数数,就称为整数线性规划就称为整数线性规划,有时简称为整数规有时简称为整数规划划.所有的变量都要求是整数时所有的变量都要求是整数
92、时,称为纯整数线性称为纯整数线性规划规划;部分变量要求取整数时部分变量要求取整数时,称为混合型整称为混合型整数线性规划数线性规划.求解的简单思路求解的简单思路:先不考虑整数要求先不考虑整数要求,求解一求解一般的线性规划般的线性规划.若求得的最优解不满足整数要若求得的最优解不满足整数要求时求时,用用”舍入取整舍入取整”的方法处理的方法处理.该方法有时会带来很大的误差该方法有时会带来很大的误差,甚至得到的解甚至得到的解不可行不可行.1481482.10.1 割平面法割平面法考虑整数规划考虑整数规划min x1x2s.t. 2x1+x264x1+5x220x1,x20且为整数且为整数如果不考虑整数约
93、束如果不考虑整数约束,其可行域见下图其可行域见下图.最优解为最优解为(5/3,8/3)T.149149(5/3,8/3)150150割平面法割平面法如果考虑整数约束如果考虑整数约束,那么可行域是那么可行域是(LP)可行域可行域内的内的13个整点个整点.我们考虑的方法之一是首先将我们考虑的方法之一是首先将(LP)的最优点的最优点附近的一块区域附近的一块区域“ “挖掉挖掉”再求解再求解,挖掉的区域挖掉的区域内不含任何整点内不含任何整点.151151(5/3,8/3)152152解解(LP)最终单最终单纯形表为纯形表为cj-1 -1 0 0 cBBbp1 p2 p3 p4 -1-1p1p25/38/
94、31 0 5/6 -1/60 1 -2/3 1/3s s j0 0 1/6 1/6考虑考虑x2对应的方程对应的方程由单纯形表得到由单纯形表得到由于由于x2x32为整数为整数,可得可得化为等式约束化为等式约束x3x4+x5= -2153153割平面法割平面法考虑到考虑到x3=6-(2x1+x2),x4=20-(4x1+5x2),根据根据2/3-x3/3-x4/3 0可以得到可以得到x1+x2 4可以看出可以看出,(LP)中的可行域确实去掉了一块不中的可行域确实去掉了一块不含整点的部分含整点的部分.154154(5/3,8/3)155155割平面法割平面法设纯整数线性规划为设纯整数线性规划为 mi
95、n cTx(ILP) s.t. Ax=b x0 xj为整数为整数,j=1,2,n其中其中A,c,b中的元素为整数中的元素为整数.去掉其中去掉其中xj为整数的要求为整数的要求,得到的线性规划得到的线性规划(LP)称为与称为与(ILP)相对应的线性规划相对应的线性规划.156156割平面方程割平面方程设对应的线性规划设对应的线性规划(LP)的最优解为的最优解为 ,再设其再设其中的中的xr为非整数的基变量为非整数的基变量.由最终的单纯形表由最终的单纯形表可写出约束方程可写出约束方程其中其中T表示非基变量的下标集表示非基变量的下标集.把把 与与a arj分解为整数部分与非负真分数分解为整数部分与非负真
96、分数(纯纯小数小数),即即代入到约束方程中得到代入到约束方程中得到157157割平面方程割平面方程所有的变量都取非负整数时所有的变量都取非负整数时,上式的左端是整上式的左端是整数数,因此右端也是整数因此右端也是整数.而右端是小于而右端是小于1的的,从而小于等于从而小于等于0.这是所有变量取非负整数时必须满足的条件这是所有变量取非负整数时必须满足的条件.称之为割平面方程称之为割平面方程.158158增加割平面方程的规划增加割平面方程的规划将割平面方程添加到纯整数规划的约束条件将割平面方程添加到纯整数规划的约束条件中中,得到新的规划问题得到新的规划问题 min cTx(ILP) s.t. Ax=b
97、 x0 xj为整数为整数,j=1,2,n该整数规划对应的线性规划可以用对偶单纯该整数规划对应的线性规划可以用对偶单纯形方法求解形方法求解.159159割平面法示例割平面法示例例例2.10.1 求解整数规划求解整数规划min x1x2s.t. 2x1+x264x1+5x220x1,x20且为整数且为整数解解:此规划的标准形式为此规划的标准形式为min x1x2s.t. 2x1+x2+x3 =6 4x1+5x2 +x4=20x1,x2,x3,x40且为整数且为整数160160解与之对应的线性规划解与之对应的线性规划,得到得到最优解最优解(5/3,8/3,0,0)T.相应的最终单纯形表为相应的最终单
98、纯形表为cj-1 -1 0 0 cBBbp1 p2 p3 p4 -1-1p1p25/38/31 0 5/6 -1/60 1 -2/3 1/3s s j0 0 1/6 1/6x1与与x2都不是都不是整数整数.我们不我们不妨先考虑妨先考虑x2.由单纯形表得到由单纯形表得到由于由于x2x32为整数为整数,可得割平面方程可得割平面方程化为等式约束化为等式约束x3x4+x5=-2161161解与之对应的线性规划解与之对应的线性规划,得到得到最优解最优解(5/3,8/3,0,0)T.相应的最终单纯形表为相应的最终单纯形表为cj-1 -1 0 0 cBBbp1 p2 p3 p4 -1-1p1p25/38/3
99、1 0 5/6 -1/60 1 -2/3 1/3s s j0 0 1/6 1/6x1与与x2都不是都不是整数整数.我们不我们不妨先考虑妨先考虑x2.162162将约束将约束x3x4+x5= 2添加到原问题中添加到原问题中,再求再求解对应的线性规划解对应的线性规划.将新增加的约束置于单纯将新增加的约束置于单纯形表的最后一行形表的最后一行.-1-10p1p2p55/38/3-21 0 5/6 -1/6 00 1 -2/3 1/3 00 0 -1 -1 1sj0 0 1/6 1/6 0cj-1 -1 0 0 0cBBbp1 p2 p3 p4 p5 该解已经是该解已经是整数解整数解.从而从而原规划的最
100、原规划的最优解为优解为x*=(0,4)T,最优值为最优值为-4.用对偶单纯形方法求解此问题用对偶单纯形方法求解此问题,得得x=(0,4,2,0,0)T163163分枝定界法分枝定界法对于整数规划对于整数规划(ILP),求解与之对应的线性规划求解与之对应的线性规划(LP),如果如果(LP)的最优解满足整数要求的最优解满足整数要求,那么就那么就是是(ILP)的最优解的最优解.否则否则,设设(LP)的最优解的分量的最优解的分量xr不是整数不是整数,设设xr=Nr+fr,0fr1,Nr为整数为整数,(ILP)的整数可行解必满足下面两个条件之一的整数可行解必满足下面两个条件之一xrNr或或xrNr+11
101、64164分枝定界法分枝定界法根据上面的两个条件将原规划划分为两个子根据上面的两个条件将原规划划分为两个子问题问题.对这两个子问题对这两个子问题,依然不考虑整数要求依然不考虑整数要求,求解对应的线性规划的最优解求解对应的线性规划的最优解,即求解下面两即求解下面两个线性规划问题个线性规划问题. min z=cTx(P1) s.t. Ax=b xrNr x0 min z=cTx(P2) s.t. Ax=b xrNr+1 x0165165分枝定界法分枝定界法设设(P1),(P2)的最优解分别为的最优解分别为x1,x2最优值为最优值为z1,z2.考虑考虑z1z2的情况的情况.若若x1为整数解为整数解,
102、则则x1为原来的问题为原来的问题(ILP)的解的解;若若x1不是整数解不是整数解,再将再将(P1)划分为两个线性规划分为两个线性规划子问题划子问题.在求出这两个子问题的解之后再考在求出这两个子问题的解之后再考虑是否需要划分虑是否需要划分(P2).166166算例算例例例2.10.1用分枝定界方用分枝定界方法求解整数规划法求解整数规划 min z=5x1+3x2(P0) s.t. 3x1+4x212 5x1+2x210 x1,x20且为整数且为整数解解:解与解与(P0)对应的线对应的线性规划性规划,得到最优解与得到最优解与最优值分别为最优值分别为x=(8/7,15/7)Tz=85/712.141
103、67167算例算例x1,x2都不是整数都不是整数,不妨先根据不妨先根据x1进行分枝进行分枝.x1=1+1/7,构造以下两个线性规划子问题构造以下两个线性规划子问题. min z=5x1+3x2 s.t. 3x1+4x212(P1) 5x1+2x210 x11 x1,x20 min z=5x1+3x2 s.t. 3x1+4x212(P2) 5x1+2x210 x12 x1,x20168168算例算例分别解上面两个线性规划分别解上面两个线性规划,(P1)的最优解的最优解(1,2.5)T,最优值为最优值为12.5,(P2)的最优解的最优解(2,1.5)T,最优值为最优值为14.5.(P1)的最优值较
104、小的最优值较小,在将在将(P1)分划为两个子问分划为两个子问题题. min z=5x1+3x2 s.t. 3x1+4x212(P3) 5x1+2x210 x11 x22 x1,x20 min z=5x1+3x2 s.t. 3x1+4x212(P4) 5x1+2x210 x11 x23 x1,x20无可无可行解行解169169算例算例(P4)的最优解为的最优解为(1,3)T(已是整数解已是整数解), 最优值最优值为为14.由于由于(P2)的最优值比的最优值比(P4)的最优值大的最优值大.所以所以(P2)不再分划不再分划.原问题的最优解为原问题的最优解为(1,3)T, 最优值为最优值为14.170170
