对偶问题和运输问题

原问题与对偶问题的关系原问题(或对偶问题)对偶问题(或原问题)目标函数maxzn个变=0量=0无约束目标函数minwn个约=束=条=件约m个束=条=约束条件右端项目标函数变量的系数m个=0变=0量目标函数变量的系数约束条件右端项例3写对偶问题Minz=2x1+3x2-5x3+x4x1+x2-3x3+x4=52x1+2x3-x4=4x2+x3+x4=6x1=0,x2,x3=0x4无约束Maxz’=5y1+4y2+6y3y1+2y2=0y1+y3=0-3y1+2y2+y3=-5y1-y2+y3=1y1=0,y2=0,y3无约束3.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）定理3-1(弱对偶定理）若x,y分别为（LP)和（DP）的可行解，那么cTx≤bTy。推论若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。1.线性规划对偶问题定理3-2(最优性准则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。定理3-3(主对偶定理)若(LP)和(DP)均可行那么(LP)和(DP)均有最优解,且最优值相等。以上定理、推论对任意形式的相应性规划的对偶均有效1.线性规划对偶问题4、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0对偶引进松弛变量引进松弛变量XTWS=0WTXS=0互补松弛关系X，XsW，Ws五、对偶的经济解释1、原始问题是利润最大化的生产计划问题0xxxxxxbxxaxaxabxxaxaxabxxaxaxa.t.sxcxcxczmaxmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）2、对偶问题0资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=miny3、资源影子价格的性质■影子价格越大，说明这种资源越是相对紧缺■影子价格越小，说明这种资源相对不紧缺■如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooimmii2211wbwbwbwbyzmmiii2211wbw)bb(wbwbzziiwbz影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。1.线性规划对偶问题需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。1.线性规划对偶问题5.由最优单纯形表求对偶问题最优解标准形式：Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x5≥01.线性规划对偶问题maxz=CTXs.t.AX+XS=bX,XS≥0maxy=bTWs.t.ATW-WS=CW,WS≥0maxz=CTXs.t.AX≤bX≥0miny=bTWs.t.ATW≥CW≥0单纯形表和对偶对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1WSTWTCBTB-1b0B-1AB-1B-1bzXXSRHS1-CT0T00AIbmaxz=CTXs.t.AX+XS=bX,XS≥0miny=bTWs.t.ATW-WS=CW,WS≥0zXXSRHS1CBTB-1A-CTCBTB-1CBTB-1b0B-1AB-1B-1bWT=CBTB-1WST=WTA-CT50100000CBXBx1x2x3x4x5θi0x3300111003000x4400210104000x52500(1)001250-z050100*0000x350(1)010-1500x41502001-175100x225001001-z-2500050*000-10050x1501010-10x45000-211100x225001001-z-2750000-500-50-cBTB-1IB=(p1,p4,p2)oTB-1最优解x1=50x2=250x4=50影子价格y1=50y2=0y3=50,B-1对应的检验数T=cBTB-1。1.线性规划对偶问题例3.2：求解线性规划问题：标准化：Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥02.对偶单纯形法对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。2.对偶单纯形法如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。2.对偶单纯形法对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:①单纯形表的检验数行全部非正（对偶可行）；②变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。2.对偶单纯形法•1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b’≥0,则得到最优解,停止;否则,若有bk0则选k行的满足min{bk0}基变量为出基变量,转33.若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj’0则选=min{j’/akj’┃akj’0}=r’/akr’那么xr为进基变量,转4；4.以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。对偶单纯形法求解线性规划问题过程：2.对偶单纯形法例3.2：求解线性规划问题：标准化：Maxz=-2x1-3x2-4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0Minf=2x1+3x2+4x3S.t.x1+2x2+x3≥32x1-x2+x3≥4x1,x2,x3≥02.对偶单纯形法•表格对偶单纯形法CI-2-3-400CBXBbX1X2X3X4X50X4-3-1-2-1100X5-4[-2]1-301σj-2-3-4000X4-10[-5/2]1/21-1/2-2X121-1/23/20-1/2σj0-4-10-1-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5σj00-9/5-8/5-1/52.对偶单纯形法单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题2.对偶单纯形法在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。2.对偶单纯形法单纯形表的理解（例题）上表中6个常数a1,a2,a3,b,1,2取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由x1取代x6目标函数可改善。CiCBXBb'x1x2x3x4x5x6x3b4a110a20x42-1-501-10x63a3-300-41σ1σ200-30进一步理解最优单纯性表中各元素的含义考虑问题Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥03.灵敏度分析3、灵敏度分析无防设，xj=0j=m+1,…,n;xi=bi’i=1,…,m是基本可行解,对应的目标函数典式为：z=-f+m+1xm+1+…+nxn以下是初始单纯形表：mm其中：f=-∑cibi’j=cj-∑ciaij’为检验数。向量b’=B-1bi=1i=1A=[p1,p2,…,pn],pj’=B-1pj,pj’=(a1j’,a2j’,…,amj’)T，j=m+1,…,nc1…cmcm+1…cnCBXBx1…xmxm+1…xnθic1x1b1'1…0a'1m+1…a'1nθ1c2x2b2'0…0a'2m+1…a'2nθ2┇┇┇┇┇┇┇┇┇┇cmxmbm'0…1a'mm+1…a'mnθm-zf0…0σm+1…σnci,bj发生变化增加一约束或变量及A中元素发生变化—通过例题学会处理对于表格单纯形法，通过计算得到最优单纯形表。应能够找到最优基B的逆矩阵B-1，B-1b以及B-1N，检验数j等。3.灵敏度分析价值系数c发生变化：m考虑检验数j=cj-∑criarijj=1,2,……,ni=11.若ck是非基变量的系数：设ck变化为ck+ckk’=ck+ck-∑criarik=k+ck只要k’≤0,即ck≤-k，则最优解不变；否则，将最优单纯形表中的检验数k用k’取代，继续单纯形法的表格计算。3.灵敏度分析例3.3:Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥03.灵敏度分析例：最优单纯形表CI-2-3-400CBXBbX1X2X3X4X5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5σj00-9/5-8/5-1/5CI-2-3-4+Δc300CBXBbX1X2X3X4X5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5σj00-9/5+Δc3-8/5-1/5从表中看到σ3=c3