第三章 对偶理论

1第三章对偶理论2对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？且看下面详解……线性规划的对偶理论3引例——俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏讪。王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好惨了，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...王老板李老板线性规划的对偶理论4王老板的家具生产模型：x1、x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2≤120（木工）2x1+x2≤50（油漆工）x1，x2≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2≥503y1+y2≥30y1，y2≥0对偶线性规划问题，记为（D）线性规划的对偶理论5王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————线性规划的对偶理论6例1线性规划问题为原始问题，记为P对应第一个约束条件对应第二个约束条件（P）maxZ=2X1+X25X2≤15对应第一个对偶变量y16X1+2X2≤24对应第二个对偶变量y2X1+X2≤5对应第三个对偶变量y3X1，X2≥0线性规划的对偶理论7下面我们从另一角度提出一个新的问题。这个问题我们将其称为原始问题的对偶问题，记为D（D）minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1，y2，y3≥0线性规划的对偶理论8对称形式下对偶问题的一般形式项目原问题对偶问题AbC目标函数约束条件决策变量约束系数矩阵约束条件的右端项向量目标函数中的价格系数向量maxZ=CXAX≤bX≥0其约束系数矩阵的转置目标函数中的价格系数向量约束条件的右端项向量minW=Y′bA′Y≥C′Y≥0线性规划的对偶理论9非对称形式下对偶问题的一般形式—原始（对偶）对偶（原始）关系表项目原问题（对偶问题）对偶问题（原问题）目标函数类型maxmin目标函数系数与右边项的对应关系目标函数各变量系数对应约束条件右边项的系数右边项的系数对应目标函数系数变量个数与约束条件个数的对应关系变量个数n约束条件个数m约束条件个数n变量个数m原问题变量类型与对偶问题约束条件类型的对应关系≥0变量类型≤0自由≥约束条件类型≤=原问题约束条件类型与对偶问题变量类型的对应关系≥约束条件类型≤=≤0变量类型≥0自由线性规划的对偶理论10例：maxz=5x1+12x2+4x3x1+2x2+x3≤42x1-x2+3x3=2x1+x2+x3≥6x1≥0，x2≤0，x3自由线性规划的对偶理论minw=4y1+2y2+6y3y1+2y2+y3≥52y1-y2+y3≤12y1+3y2+y3=4y1≥0，y2自由，y3≤011例：maxz=5x1+6x2+8x3x1+9x2+7x3≤602x1+3x2–2x3≥455x1-2x2+6x3≥20x2-x3=30x1≥0，x2≤0，x3自由线性规划的对偶理论minw=60y1+45y2+20y3+30y4y1+2y2+5y3≥59y1+3y2-2y3+y4≤67y1–2y2+6y3-y4=8y1≥0，y2，y3≤0，y4自由12对偶问题的基本性质1.对称性——原始问题与对偶问题是两个互为对偶的问题。2.弱对偶性——两个问题的可行解对应的目标函数值互为上下界。3.最优性——两个问题最优解的目标函数值必相等。4.强对偶性——两个问题都有可行解时则两个问题必都有最优解。5.互补松弛性——两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束；反之，如果约束条件为松约束，则其对应的对偶变量一定取值为零。因此，该定理又称为松紧定理。线性规划的对偶理论13原问题与对偶问题解的对应关系表问题与解的状态对偶问题有最优解无界解无可行解原问题有最优解一定不可能不可能无界解不可能不可能可能无可行解不可能可能可能线性规划的对偶理论14例：已知线性规划问题线性规划的对偶理论0,,122max32132132121xxxxxxxxxxxz用对偶理论证明上述线性规划问题无最优解。15解：原问题存在可行解，例如X=（0，0，0）对偶问题为：线性规划的对偶理论0,0112min2121212121yyyyyyyyyyw由第一个约束条件可知对偶问题无可行解，又因为原问题有可行解，所以原问题无最优解。16例：已知线性规划问题0,,,,33243232532min54321543215432154321xxxxxxxxxxxxxxxxxxxxw线性规划的对偶理论已知其对偶问题的最优解为：试用对偶理论找出原问题的最优解。5,5/3,5/4*2*1zyy17解：对偶问题为：0,33253232234max21212121212121yyyyyyyyyyyyyyz线性规划的对偶理论将Y*代入约束条件，约束条件2、3、4为严格不等式，由互补松弛性得：0*4*3*2xxx18又因为0,21yy线性规划的对偶理论所以原问题两个约束条件取等式，即3243*5*1*5*1xxxx求解可得：1,1*5*1xx原问题最优解为：5,)1,0,0,0,1(**wXT19对偶问题解的经济解释——影子价格我们已经明白原始线性规划与对偶线性规划之间形式上的对偶以及他们的解之间的关系，那么对偶问题的解除了前面引例中提到的租金这种经济含义外其深刻的经济含义是什么呢？线性规划的对偶理论20对偶问题解的经济含义分析：从单纯形法的矩阵描述中，目标函数取值Z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1。设B是{maxZ=CX|AX≤b，X≥0}的最优基矩阵，由强对偶定理知Z*=CX*=CBB-1b=Y*b=W*由此Z*bZ*bi（Y*b）bi=CBB-1=Y*或==yi*线性规划的对偶理论21对偶问题解的经济含义：由上面分析——对偶问题解中变量yi*的经济含义是在其他条件不变的情况下，单位第i种“资源”变化所引起的目标函数最优值的变化。所以，yi*描述了原始线性规划问题达到最优时（各种“资源”都处于最优的配置时），第i种“资源”的某种“价值”，故称其为第i种“资源”的影子价格。这正是经济学中机会价值的含义。下面图解阐述影子价格的直观含义：线性规划的对偶理论22影子价格我们首先采用单纯形法求解得王老板的家具生产模型（P）的最优解、最优基矩阵如下（P）的最优解为X*=（15，20，0，0）T（D）的最优解为Y*=CBB-1=（5，15）B=（p2，p1）=3412CB=（C2，C1）=（30，50）B-1=1-2-1/23/2线性规划的对偶理论23影子价格王老板的家具生产模型的图解：x1x2D可行域1350=50x1+30x2（15，20）（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥02x1+x2=504x1+3x2=120L0：50x1+30x2线性规划的对偶理论24影子价格的直观含义：x1x24x1+3x2=1202x1+x2=50L0：50x1+30x2D可行域（P）maxZ=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1，x2≥02x1+x2=514x1+3x2=1211365=50x1+30x21355=50x1+30x2线性规划的对偶理论1350=50x1+30x225影子价格的特点：影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源在当前的最优利用配置下的一种客观估价，又表明它是一种虚拟的价格（或价值的影象）而不是真实的价格。特点1、影子价格是对系统资源的一种内部最优估价，只有当系统达到最优状态时才可能赋予资源这种价值。特点2、系统资源的一种动态价格体系，影子价格的大小与系统的价值取向有关，并受系统状态变化的影响。系统环境的任何变化都可能会引起影子价格的变化。线性规划的对偶理论26特点3、影子价格的大小客观地反映资源在系统内的稀缺程度。如果某种资源在系统内供大于求，尽管它有实实在在的市场价格，但它在系统内的影子价格却为零，而影子价格越高，资源在系统内越稀缺。特点4、影子价格是一种边际价值，其与经济学中的边际成本的概念相同。因而，在经济管理中十分重要的应用价值。企业管理者可以根据资源在企业内部的影子价格的大小决定企业的经营策略。特点5、对偶解准确的经济意义与线性规划模型的构造方法有关，模型构造方法的不同有时会导致对偶解的不同经济解释。线性规划的对偶理论27对偶单纯形法思路maxZ=2x1+x2s.t.x1+x2+x3=52x2+x3≤54x2+6x3≥9x1，x2，x3≥0maxZ=2x1+x2s.t.x1+x2+x3=52x2+x3+x4=54x2+6x3-x5=9x1，x2，x3，x4，x5≥0准典式：maxZ=-1x2-2x3s.t.x1+x2+x3=52x2+x3+x4=5-4x2-6x3+x5=-9x1，x2，x3，x4，x5≥0标准化化典式准典式——1、显含基可行解2、目标函数中不含基变量，且Max化目标函数中非基变量的系数均非正线性规划的对偶理论28对偶单纯形法基本思路：如果线性规划原问题标准化之后不能简单得出一个初始基可行解（典式），但却能容易得到该问题的对偶问题的一个初始基可行解（准典式），此时我们就可以通过保持对偶基可行解的可行性的方法进行迭代，逐步消除原问题基本解的不可行性，最终，当对偶基可行解迭代到对偶最优解的同时原问题也得到了最优的基可行解。线性规划的对偶理论29对偶单纯形法的计算方法基解X1X2X3X4X5X1X4X555-911100021100-4-601检验数0-1-200比值--1/41/3----基解X1X2X3X4X5X1X4X211/41/29/410-1/201/400-211/2013/20-1/4检验数00-1/20-1/4比值迭代准典式：maxZ=-1x2-2x3s.t.x1+x2+x3=52x2+x3+x4=5-4x2-6x3+x5=-9x1，x2，x3，x4，x5≥0准典式特点：1、目标函数不含基变量2、最大化目标函数中非基变量的系数均非正3、约束方程中显含基本解线性规划的对偶理论30minW=120y1+50y2s.t.4y1+2y2≥503y1+y2≥30y1，y2≥0maxW’=–120y1–50y2s.t.4y1+2y2–y3=503y1+y2–y4=30y1，y2，y3，y4≥0maxW’=–120y1–50y2s.t.–4y1–2y2+y3=–50–3y1–y2+y4=–30y1，y2，y3，y4≥0线性规划的对偶理论例：31maxW’=–120y1–50y2s.t.–4y1–2y2+y3=–50–3y1–y2+y4=–30y1，y2，y3，y4≥0基解y1y2y3y4y3-50-4-210y4-30-3-101检验数j-120-5000-120/-4-50/-2------线性规划的对偶理论32基解y1y2y3y4y3-50-4-210y4-30-3-101检验数j-120-5000y2