最优化理论 第3章线性规划

第三章,线性规划,3.1线性规划模型,例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x265；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x240；,3.1线性规划模型,对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x275；另外，产品数不可能为负，即x1,x20。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,3.1线性规划模型,目标函数Maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x20,3.1线性规划模型,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。,3.1线性规划模型,一般形式目标函数：Max(Min)z=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bmx1，x2，xn0,3.1线性规划模型,标准形式目标函数：Maxz=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bmx1，x2，xn0,3.1线性规划模型,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,3.1线性规划模型,1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+cnxn则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf-Maxz,3.1线性规划模型,2、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+ainxnbi可以引进一个新的变量s，使它等于约束右边与左边之差s=bi(ai1x1+ai2x2+ainxn)显然，s也具有非负约束，即s0，这时新的约束条件成为ai1x1+ai2x2+ainxn+s=bi,3.1线性规划模型,当约束条件为ai1x1+ai2x2+ainxnbi时，类似地令s=(ai1x1+ai2x2+ainxn)-bi显然，s也具有非负约束，即s0，这时新的约束条件成为ai1x1+ai2x2+ainxn-s=bi,3.1线性规划模型,为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3.1线性规划模型,例2.2：将以下线性规划问题转化为标准形式Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x315.74.1x1+3.3x38.9x1+x2+x3=38x1,x2,x30,3.1线性规划模型,解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3,其次考虑约束，有2个不等式约束，引进松弛变量x4，x50。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x50,3.1线性规划模型,3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj-xj”其中xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,3.1线性规划模型,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0,且B-1pj0,则(LP)无有界解.,3.2线性规划的单纯形法,表格单纯形法1、原理及算法过程MaxcTx(LP)s.t.Ax=bx0其中,c,xRnbRmAmn矩阵，秩（A）=m,3.2线性规划的单纯形法单纯形法原理及算法过程,算法过程(考虑一般步,k=0,1,2,)设x(k)为极点,对应分解A=B,N，使xT=xBT,xNT,这里xB=B-1b0,xN=0，相应cT=cBT,cNT。那么，1）若cNT-cBTB-1N0,则x(k)opt，停；2）否则，存在cj-cBTB-1pj0,a）若B-1pj0,则(LP)无有界解，停；b）若存在(B-1pj)i0,取=min(B-1b)i/(B-1pj)i|(B-1pj)i0=(B-1b)r/(B-1pj)r0,3.2线性规划的单纯形法单纯形法原理及算法过程,(续)得到x(k+1)=x(k)+d是极点其中,dT=dBT,dNT,这里jdB=-B-1pj,dN=(0,.,1,0)T有,cTx(k+1)=cTx(k)+cTd=cTx(k)+(cj-cBTB-1pj)cTx(k)所以，x(k+1)比x(k)好重复这个过程，直到停机。,3.2线性规划的单纯形法表格单纯形法,2、单纯形表：设x为初始极点,相应分解A=B,N,作变换，使前m+1列对应的m+1阶矩阵变为单位矩阵。相当于该表左乘1cBT-11-cBTB-10B0B-1,=,3.2线性规划的单纯形法表格单纯形法,得到：检验数,为了计算方便，我们对规范形式建立如下单纯形表：（注：引入了m个松弛变量）,3.2线性规划的单纯形法,表格单纯形法考虑：bi0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,3.2线性规划的单纯形法,加入松弛变量：Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0,显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解对应的基是单位矩阵。以下是初始单纯形表：mm其中：f=-+ibij=cj-cn+iaij为检验数cn+i=0i=1,mi=1i=1an+i,i=1,an+i,j=0(ji)i,j=1,m,建立实用单纯形表,利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,3.2线性规划的单纯形法,单纯形法,单纯形法的基本过程,例：用单纯形法的基本思路解前例的线性规划问题Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50,3.2线性规划的单纯形法,3.2线性规划的单纯形法,最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000,注意：单纯形法中，1、每一步运算只能用矩阵初等行变换；2、表中第3列的数总应保持非负（0）；3、当所有检验数均非正（0）时，得到最优单纯形表。,3.2线性规划的单纯形法,一般情况的处理及注意事项的强调：主要是讨论初始基本可行解不明显时，常用的方法。要弄清它的原理，并通过例题掌握这些方法，同时进一步熟悉用单纯形法解题。考虑一般问题：bi0i=1,m,3.2线性规划的单纯形法,Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bmx1，x2，xn0,3.2线性规划的单纯形法,大M法：引入人工变量xn+i0（i=1,m）及充分大正数M。得到：Maxz=c1x1+c2x2+cnxn-Mxn+1-Mxn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0,3.2线性规划的单纯形法,显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足xn+i=0i=1,m则是原问题的最优解；否则，原问题无可行解。,单纯形法,两阶段法：引入人工变量xn+i0，i=1,m；构造:Maxz=-xn+1-xn+2-xn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2.am1x1+am2x2+amnxn+xn+m=bmx1,x2.xn,xn+1,xn+m0,单纯形法,第一阶段求解上述问题：显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解,它对应的基是单位矩阵。,结论：若得到的最优解满足xn+i=0i=1,m则是原问题的基本可行解;否则，原问题无可行解。得到原问题的基本可行解后，第二阶段求解原问题。,单纯形法,例（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,3.2线性规划的单纯形法,Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,大M法问题(LP-M）,3.2线性规划的单纯形法,大M法（LP-M）,得到最优解：(25/3，10/3，0，11)T最优目标值：112/3,3.2线性规划的单纯形法,第一阶段问题（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,两阶段法：,3.2线性规划的单纯形法,第一阶段(LP-1）,得到原问题的基本可行解:(0，15/7，25/7，52/7)T,3.2线性规划的单纯形法,第二阶段把基本可行解填入表中,得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3,3.2线性规划的单纯形法,3.3线性规划的对偶,对偶原理对偶问题定义线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。对偶定理只需了解原问题与对偶问题解的关系，证明从略。,1.对偶问题：若3.1中的例题的设备都用于外协加工，工厂收取加工费。试问：设备A、B、C每工时各如何收费才最有竞争力？设y1，y2，y3分别为每工时设备A、B、C的收取费用。,3.3线性规划的对偶,线性规划原问题,例:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,Maxz=1500 x1+2500 x2s.t.3x1+2x2652x1+x240原问题3x275x1,x20Minf=65y1+40y2+75y3s.t.3y1+2y21500（不少于甲产品的利润）2y1+y2+3y32500对偶问题（不少于乙产品的利润）y1,y2,y30,3.3线性规划的对偶,2、对偶定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Axbs.t.ATycx0y0“Max-”“Min-”,3.3线性规划的对偶,一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,3.3线性规划的对偶,(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。,3.3线性规划的对偶,非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；,3.3线性规划的对偶,（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,3.3线性规划的对偶,3.3线性规划的对偶,例写出下面线性规划的对偶规划模型,解先将约束条件变形为“”形式,3.3线性规划的对偶,再根据非对称形式的对应关系，直接写出对偶规划,3.3线性规划的对偶,对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）,定理3-1(弱对偶定理）若x,y分别为（LP)和（DP）的可行解，那么cTxbTy。,推论若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。,3.3线性规划的对偶,定理3-2(最优性准则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。,定理3-3(主对偶定理)若(LP)和(DP)均可行那么(LP)和(DP)均有最优解,且最优值相等。,以上定理、推论对任意形式的相应性规划的对偶均有效,3.3线性规划的对偶,影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cTx*=bTy*。根据f=bTy*=b1y1*+b2y2*+bmym*可知f/bi=yi*yi*表示bi变化1个单位对目标f产生的影响，称yi*为bi的影子价格。注意：若B是最优基，y*=(BT)-1cB为影子价格向量。,3.3线性规划的对偶,影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,3.3线性规划的对偶,需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。,3.3线性规划的对偶,由最优单纯形表求对偶问题最优解标准形式：Maxz=50 x1+100 x2s.t.x1+x2+x3=3002x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x50,3.3线性规划的对偶,-cBTB-1,I,B=(p1,p4,p2),oT,B-1,最优解x1=50 x2=250 x4=50影子价格y1=50y2=0y3=50,B-1对应的检验数T=cBTB-1。,3.3线性规划的对偶,对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,对偶单纯形法,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,对偶单纯形法,对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转33.若所