线性规划的对偶问题

教案五线性规划的对偶问题教学内容第四节线性规划的对偶问题1．线性规划的对偶问题2．对偶单纯形法3．线性规划的灵敏度分析4．线性规划在卫生管理中的应用教学学时7学时教学目标1．理解对偶问题的基本概念2．掌握对偶单纯形法3．掌握线性规划的灵敏度分析4．掌握线性规划在卫生管理中的应用重点难点重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析教学手段教师与学生互动使用多媒体课件教学过程一、复习巩固1．单纯形法的基本原理（见课件）2．单纯形解法（见课件）3．大M法（见课件）二、讲授新课1．线性规划的对偶问题（1）对偶问题的基本概念（见课件）对偶现象每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶．其中一个问题称为原问题，另一个问题称为其对偶问题．两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解．下面通过一个实例来解释对偶线性规划的概念．例2-12以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法．现在假定该制药厂决定在计划期内不生产药品I、II,而将生产设备的有效台时全部租给某公司，那么该公司应对设备A、B、C、D每小时付多少租金，才能使成本最小,而又能为制药厂所接受？从租用设备的公司的角度考虑,一是所付的租金越低越好；二是所付的租金总额能使制药厂接受,即租金应不低于制药厂自己生产该两种药品所得利润,否则,制药厂宁可自己生产,而不租给公司．设公司租用该制药厂A、B、C、D四种设备的租金（元/小时）分别为y］、y、y和y.在考虑租用设备的定价时，能使该制药厂接受的条件是：234公司租用该制药厂用以生产每千克药品I所需A、B、C、D四种设备的台时的租金不应少于200元,即y+y+4y+0y>2001 2 3 4同样，公司租用该制药厂用以生产每千克药品II所需A、B、C、D四种设备的台时的租金不应少于300元,即2y+2y+0y+4y>3001234公司在考虑自身利益时，其目标是使付出的租金总额为最小，即MinW=12y+8y+16y+12yTOC\o"1-5"\h\z1 2 3 4于是,上面的问题可以用下列线性规划的数学模型表示MinW=12y+8y+16y+12y1 2 3 4广2y+y+4y+0y>20012 3 4s.t.丿2y+2y+0y+4s.t.2 3 4y1,y2,y3,y4>0若把制药厂利润最大的线性规划问题称为原问题,则想租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dualproblem）;反之，若把租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题．影子价格一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解y称为第i种资源的影子价格.它并不是某种资源在市场上i的价格，而是代表单位资源在最优利用的条件下所产生的经济效果.为了和市场价格相区别，我们才称它为影子价格.它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小.另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准.（2）对称的对偶线性规划（见课件）如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（＜）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（n）的符号.对称形式的原问题和对偶问题叫做对称的对偶线性规划.原问题和对偶问题在形式上的对比如果我们把线性规划MaxZ=ex+exH Fex1122nnIax+axF Fax<bTOC\o"1-5"\h\z111 122 1nn 1ax+axF Fax<b211 222 2nn 2 ax+axF Fax<bm11 m22 mnn mx,x，•…,x>01 2 n称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：MinW=by+byF Fby1 1 2 2 mm'ay+ayF Fay>e1 21 2 m1m 1ay+ayF Fay>e1 222 m2m 2s.t.ay+ayF Fay>e1n1 2n2 mnm ny,y,…,y>01 2 m而且 MinW=MaxZ用简缩形式表示：

原问题为MaxZ=工exi=1,2,…i=1,2,…，mj=1,2,…,n工ax<bijjiS.t. V j=1「x.>0对偶问题为MinW=]Ebyiii=1｛迟ay>e j=1,2,…,nijij°=1y>0 ； i=1,2,…,m矩阵形式表示：原问题为MaxZ=CXAX<bs.t.X>0对偶问题为MinW=Yb其中，s.t.s.t.YA其中，s.t.s.t.YA>CY>0C=(e1,C2,…,：)1na2nTOC\o"1-5"\h\z'a a1na2n1112a aA= 21 22X=rx)1x2b=rb)1b2<x.<b丿Ia am1 m2amnnmY=5y2,…,j原问题与对偶问题之间的关系1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值

2）原问题约束条件的右端项变成对偶问题目标函数的系数．原问题目标函数中的系数变成对偶问题约束条件的右端项．3）原问题约束条件是”，对偶问题的约束条件则是“>”.4） 原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目．5） 原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目．6） 对偶问题的对偶规划正是原问题．MiWnMiWn=2x+5x12>4x1x>3

2x+2x>812x,x>012试写出它的对偶问题．MaxZ=4y+3y+8yTOC\o"1-5"\h\z1 2 3{y+y<21 3y+2y<53y,y,y>01 2 33）非对称的对偶线性规划（见课件）对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题．实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划（dualofanonnormalLP）时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题．表2-13原问题与对偶问题间的转换原问题（或对偶问题）对偶问题（或原问题）原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MaxZ目标函数MinW约束条件数：m约束条件数：m个对偶变量数：m个第：个约束条件为“<” 对偶变量y>0i第i第i个约束条件为“>第i个约束条件为“=”变量x的数目：n个j变量x>0j变量x<0j变量x无非负条件j限定向量b成本或利润向量C系数矩阵A对偶变量y<0i对偶变量y无非负条件i约束条件数：n个第j个约束条件为“>”第j个约束条件为“<”第j个约束条件为成本或利润向量C限定向量b系数矩阵AT例2-14原问题为：MaZ-4x+5x12{3x+2x<20124x-3x>1012x+x-512x>0,x符号不限可按表2-13的原则，将原问题直接转化成对偶问题:MinW-20y+10y+5yTOC\o"1-5"\h\z1 2 3(3y+4y+y>41 2 3s.t.丿2y-3y+y-51 2 3y^>0,y?<0,y符号不限（4）对偶问题的基本性质（见课件）1） 对偶问题的对偶是原问题（对称性质）．2） 若X和Y分别是原问题和对偶问题的可行解，则CX<Yb（弱对偶性质）．3） 设X和Y分别是原问题和对偶问题的可行解，当两者目标函数值相等，即CX=Yb时，X，Y分别是原问题和对偶问题的最优解（可行解是最优解的性质）4）若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等（对偶性质）．5） 若x和Y分别是原问题和对偶问题的可行解，则X和Y为原问题及对偶问题最优解的充分条件为：vX=0和Yu=0其中，u=（u,u，…,u）T,u,u，…,u是原问题的松弛变量，v=12m12m（v,v,…,v）,v,v,…,v是对偶问题的剩余变量（松弛互补性质）.12n12n此性质在线性规划中有广泛应用．如从已知的原问题最优解（或对偶问题最优解）求取对偶问题最优解（或原问题最优解）；验证原问题的可行解是否最优解等等．6） 原问题的检验数对应于对偶问题的一个基本解．由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得的检验数与对偶问题的基本解仅仅相差一个符号，于是原问题获得最优解时对应的单纯形表中检验数的相反数，即为对偶问题的最优解．例2-15设原问题为：MaxZ=x+2x+3x+4x1234{x+2x+2x+3x<20TOC\o"1-5"\h\z12 3 42x+x+3x+2x<2012 3 4x,x,x,x>012 3 4已知其对偶问题的最优解为y*=1.2,y*=0.2,相应的目标函数最小值W*12=28,试利用对偶性质求该问题的最优解．解原问题的对偶问题为：MinW=20y+20yIJ+2y>1122y1+y2>22y+3y>3y+2y>412y,y>012由松弛互补性质可知，在最优条件下，vX=0和Yu=0,即卩u*y*=0,u*y*=0,v*x*=0,v*x*=0,v*x*=0,v*x*=0；这112211223344里u*（i=1,2），v*（j=1,2,3,4）分别为原问题的松弛变量及对偶问题的剩余ij变量．由y*=1.2>0，可以推出u*=0；由y*=0.2>0，可推出u*=0．1122由对偶约束y*+2y*=1.6>1,知v*>0,于是x*=0；同理，由2y*+y*=2.6>2,121112知v*>0,于是x*=0.22根据上述结果，原约束可以转化成二元一次线性方程组：{2x*+3x*=2043x*+2x*=203 4解方程得x*=x*=434综上所得，原问题的最优解为X*=（0044》，相应的目标函数最优值为Z*=28.由对偶性质还可以推论：1）若原问题可行，但有无界解（或称无有限最优解），则对偶问题不可行；若对偶问题可行，但有无界解（或称无有限最优解），则原问题不可行；2）若原问题可行，而对偶问题不可行，则原问题有无界解（或称无有限最优解）；若对偶问题可行，而原问题不可行，则对偶问题有无界解（或称无有限最优解）.2.对偶单纯形法前面已叙述原问题与对偶问题的解之间的对应关系.在用单纯形法进行迭代时，在b列中得到的是原问题的基本可行解，而在检验数（c-Z）行得到的jj是对偶问题基本解的相反数.通过逐步迭代，当在检验数行得到的对偶问题的解也是可行解时，原问题和对偶问题都达到了最优解.所以，单纯形法的特点是保持原问题解的可行性，通过逐步迭代，使对偶问题的解由基本解变成基本可行解，这时原问题和对偶问题都达到了最优解.

那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解是可行解（即c-Z<0）,而原问题则从非可行解开始，通过迭代，逐步达到jj基本可行解．这样，也使原问题和对偶问题都达到了最优解．事实上，对偶单纯形法（dualsimplexmethod）并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法．（1）对偶单纯形法的要点（见课件）例2-16用对偶单纯形法求解下列线性规划问题MinW=1600x+2500x+400x123{2x+5x+x>4TOC\o"1-5"\h\z1 2 32x+2.5x >31 2x,x,x>01 2 3解此问题可用大M法去解，但用大M法求解很麻烦，现在用对偶单纯形法求解．先将原问题化为标准形式，为此引入剩余变量x，x，令Z=-W，得45MaxZ=-1600x一2500x一400xTOC\o"1-5"\h\z1 2 3厂2x+5x+x一x=41 2 3 4s.t.2x+2.5x 一s.t.1 2 5<x,x,x,x,x>01 2 3 4 5然后将约束条件等式的两边都乘以（-1），得到MaxZ=-1600x一2500x一400x1 2 3尸—2x—5x—x+x=—4s.s.t. y—2x—2.5x +x——31 2 5x,x,x,x,x>012345建立这个问题的初始单纯形表，见表2-14建立这个问题的初始单纯形表，见表2-14：0x4-2-5-110-40x5-2-52001-3Cj-1600-2500-40000Z=0在这个初始单纯形表中，x、x是基本变量，初始单纯形表所对应的基本45解为X=（000-4-3》，它是一个不可行解.而全部检验数C-Z<0,jj即所对应的对偶问题的一个基本解也是一个可行解,y>0,i=1,2,…,5.下面i的迭代是在保持检验数小于等于零的条件下，逐步使x>0,j=1,2,—,5.为了j满足上面要求，迭代的要点是：1） 首先确定换出变量：选择具有负数的基本变量中绝对值最大的基本变量为换出变量.2） 确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解.3） 把换出变量的那一行除以枢元位置的系数，使枢元位置变为1.4） 进行行变换，使除枢元外的其他枢列位置变为0.5） 进行最优解检查.如果所得的基本解都是非负的，则此解即为最优解.如果基本解中还有负的数值，则重复第1步继续迭代，直到所有基本变量为非负的数值为止.（2）表解形式的对偶单纯形法（见课件）按上述迭代的要点，对表2-14继续运算，见表2-15.

0x4-2-5[-1]10-40x5-22001-3Cj-1600 -2500 -40000Z=09800500400-400x3251-1040x5-2__5__2_001-3C-800-500 0-4000Z=-16009400200-400x3[-2]01-12-2-2500x24100_26Cj-40000-400-200Z=-22009200400-1600x1102t-11-2500x2012222Cj00-200-200-600Z=-2600表2-15中b列数字全为非负，检验数全为非正，故问题的最优解为X*=G0.4000）T，最优值w*=2600.若对应两个约束条件的对偶变量分别为y和y，则对偶问题的最优解为12Y*=（20060000200）,最优值=2600.（3）对偶单纯形法的优点及用途（见课件）1）初始解可以是非可行解,当检验数都是小于等于零时,就可以进行基变换,这样就避免了增加人工变量,使运算简化.2）对变量较少,而约束条件很多的线性规划问题,可先将其变为对偶问题,再用对偶单纯形法求解,简化计算.3）用于灵敏度分析．3．线性规划的灵敏度分析在上述讨论线性规划问题时，假定a，b，c都是精确的数据，然而在大ijij多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化．因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简单的方法找到新的最优解？这就是线性规划灵敏度分析（sensitivityanalysisofLP）的任务.（1）单纯形法的矩阵表达式（见课件）设有一线性规划问题，用矩阵表示为MaxZ=CXAX<bs.t.]X>0式中，A为mxn矩阵，C为lxn行向量，X为nx1列向量，b为mx1列向量，0为nx1列向量.现引入松弛变量n+1xn+2=x,x，…,xn+2n+1 n+2 n+mIx+n+m化为标准型MaxZ=CX+0X>0，SAX+IX>0，SAX+IX=bSX>0，X>0SI是mxm阶单位矩阵,约束条件也可写成0有m+n个元素.如果我们把系数矩阵A分为两块，A=（B,N）,B也称基矩阵（即原始系数矩阵中对应于基本变量的列所组成的矩阵)，对应于B的变量x,x，…,x是基B1B2Bm本变量，用向量X二(x,x，…,x)T表示，其他的变量则为非基本变量，于是B B1B2 Bm将X也分为两块：(XBIX'N向量C也可分为两块C二(C,C)，其中C是目标函数中基本变量向量XBN B B的系数行向量，C是目标函数中非基本变量向量X的系数行向量.所以NN=(C,=(C,C,0〕XBNNIX丿' 5zBXNIX丿' 5z于是线性规划问题可以写成=(B,N,I=BX+NX+IXB N SMaxZ二CX+CX+0XBBNN S{BX+NX+IX二bBNSX,X,X>0BNS在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵.用2-9)2-10)矩阵方法，则将上述约束方程的两边乘以基矩阵B的逆矩阵B-2-9)2-10)B-1BX+B-1NX+B-1IX二B-ibTOC\o"1-5"\h\zB N S即： IX+B-1NX+B-1X二B-ibB N S所以 X二B-1b-B-1NX-B-1X (2—11)B N S将式(2—11)代入目标函数可得Z二CB-1b-CB-1NX-CB-1X+CXB B NBSNNZ二CB-1b+(C-CB-1N)X-CB-1X (2—12)B NB NBS或者 Z+(CB-1N-C)X+CB-1X二CB-1b (2—13)B NNBSB

从式（2-9）可知，在单纯形表每次迭代后,每个变量的系数列向量是B的逆阵B-i乘以该变量的原始列向量而得到的，右端常数的列向量是B的逆阵B-1乘以右端常数的原始列向量而得到的．从式（2-10）可见，其松弛变量的系数矩阵正好是基矩阵的逆阵B-1.更一般地理解，在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵．例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是x,x，x和316x．对应于表2-7的基矩阵2r102r1021002、2B二0400<0014丿000-214141210010所以对应于表2-7的x列向量是1-41-41-21-87oJ-41-41-21-87oJ1一21000B-ixP=1式中P为原始单纯形表中对应于x的列向量.11对应于表2-7的x列向量是410r0)(-1]_411040丿丿X0=—21121丿<0丿<2丿10丿一8丿1—1B-1xP=0 00-212式中P为原始单纯形表中对应于x的列向量.44对应于表2-7的b列向量是1-11-100-410-24112102-8丿1B-ixb=000<12]'0、8<4X =<<16<<4<12V12丿V2丿式中b为原始单纯形表中右端列向量.对应于表2-7的非基本变量的检验数是C-CB-1N，松弛变量的检验数NB是-CB-1．B（2）系数变化的灵敏度分析（见课件）系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系数的变化对最优解的影响．它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变（但数值有所改变）；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解．目标函数中c变化范围的确定假设其他参数不变，仅目标函数中x的系jj数c变成c+Ac，现求不改变最优解的Ac的大小.这分两种情况：jjjj1）c是非基本变量x的成本或利润系数jj因为C=c-Z （j=1,2,,n）jjjZ=£caa=CP'j iij Bji=1（式中c是基本变量的成本或利润系数）i所以改变非基本变量的成本或利润系数，Z.不变，但C=c-Z变为TOC\o"1-5"\h\zj jj j新的检验数C:C=c+Ac-Z二C+Acj jj j j j j要想保持极大化问题最优解不变，即C=C+Ac<0，则:Ac<-C.j j j j j2）c是基本变量x的成本或利润系数jj因为C-(c+Ac)-Z'—(c+Ac)-迟(c+Ac)a'jjjjjjiiiji—1—c-ca'+Ac- Aca'jiijjiiji—1 i—1—C+Ac- Aca'—C+Ac-ACP‘jjiijjjBji—1要保持极大化问题最优解不变，则C—C+Ac-ACpy0.jjjBj对于基本变量检验数总为零，而对于非基本变量x，因Ac二0，所以要求jj检验数小于等于0变为：C-ACPr<0jBj例2-17以例2-8的最终计算表（表2-7）为例•设基本变量x在目标函2数中的系数c变化了Ac;这时表2-7的最终计算表便成为表2-16所示.22表2-16基本变量利润系数变化的灵敏度分析CBc200300+Ac?0000b\\xxxxxx0x001-110034200x1000104140x000-211462300+Acx01011022228C-000-150--Ac-25+1Ac0Z=1400j22282+2Ac2这时要保持最优解不变，则必须满足下列不等式：-150-(0-150-(0oAc丿2=-150-2Ac2'0=-25+1AC2<0-300<Ac<100'2即c可在［0,400］间变动，不影响原来的生产计划安排，但制药厂收益变化2了．在约束条件中b变化范围的确定初始单纯形表中b的变化，除了影响最ii优解的数值之外，不影响最终单纯形表中的其他系数．所以只要保证最后的解仍是可行解，那么它仍然是最优解．即b=B-1(b+Ab)=B-1b+B-1Ab=b'+B-1Ab>0式中，b为右端常数变化后，最终单纯形表右端常数向量；b'为右端常数未变化时，最终单纯形表右端常数向量例2-18在例2-8中，如果第三个约束条件b发生变化，变化量为Ab，33为了使最后的解仍为可行解，Ab应满足下列不等式：3/0、4b'+B-/0、4b'+B-1Ab=42丿-10-21214

丄41218Ab30丿'0、44<2丿'-1Ab4 31Ab

4 3Ab3

—1AbI8 343+1Ab434+1Ab232-1Ab83IA^<0A^>-16Ab>-8A^<16-8<Ab<03所以Ab在［-8,0］之间变动时（即b的变化范围在［8,16］时），原来最优解33的基本变量不变，但最优解的值发生变化.例如，Ab为-2时（即b=14）,贝U33br=br+B-ibr=br+B-iAb'0、4＋4-01000、丿00101^41-41-21-8Ab34 34+1Ab4 34+1Ab2 32 Abk8 3丿、丿1-27-239-4厂J(7 9(7 9 1 、最优解x-上42003丿最优值Z*=1375，见表2-17.表2-17右端常数变化后的最优解qc2003000000b9xxxxxx0x001-1101342200x1000107142

0x000-213300x0101092284C000-150250Z=1375j2如果Ab的变化超出了[-8,0]的范围，这时最优解的基本变量就发生变3化．在这种情况下要用对偶单纯形法继续求出新的最优解．例如Ab为2时（即b=18）,33b'=bf+Bb'=bf+B-iAb=-21441218'0'ri \--Abr1]043219=4+Ab=Ab4323I0丿4+-Ab2 32-1Ab57(4丿丿I83丿0010则最终单纯形表变为表2-18表2-18右端常数变化后的对偶单纯形法求解cbc.2003000000bxxxxxx0x001-1r丄]013I4丿2200x10001091420x000-211562300x01011072284C000-150250Z=1425j29150500x00-441025200X101-10040兀6002-4014300X01-21002Cj00-50-10000Z=1400新的最优解X*=（420024》，最优值Z*=1400.矩阵A中的系数改变对最优解的影响当对应于P的变量x为非基本变量jj的系数时，它的变化不会改变基矩阵B和它的逆阵B-1，所以只需修改单纯形表中所对应x的列就可以了.jP'二B-1PjjC=C-CB-1Pj jB j若极大化问题C<0,则得到的还是新问题的最优单纯形表，最优解和最优j值不变，否则可用单纯形法求解.当对应于P的变量X为基本变量的系数时，它的变化会改变基矩阵B和它jj的逆阵B-1，所以会影响到最终单纯形表的右端向量和非基本变量对应的列.下面就举例讨论此种基本变量的系数变化情况.例2-19以例2-1为例，若计划生产的药品I的工艺结构有了改进，相应地生产单位药品I所需设备A、B、C、D的台时改为（3,2,5,2）,它的利润也提高到每千克400元.试分析已求得的最优计划有何变化？解当x的系数列向量变化后，原最终单纯形表（表2-7）中x的系数列向11量变成:

P'二P'二B一iP=11原最终单纯形表变成表表2-19决策变量系数改变对最优解的影响（1）CBc4003000000bxxxxxx0x101-1'10034I4」400x50001041440x100-2114622300x31011022828Cj由x的系数列向量可知