苏大 张芳华 运筹学课件第二章 对偶理论

1、第二章第二章 对偶线性规划对偶线性规划第二章第二章 对偶线性规划对偶线性规划对偶的定义对偶问题的性质对偶单纯形法对偶的经济解释灵敏度分析第二章第二章 对偶线性规划对偶线性规划原始问题min z=CTXs.t.AXbX 0对偶问题Max w =bT ys.t. AT y C y 0minbACTCATbTmaxmnmn一、对偶的定义一、对偶的定义第二章第二章 对偶线性规划对偶线性规划对偶的定义对偶的定义 当原问题为求极小值时，对偶问题为求极大值。 原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。 原始问题约束条件系数矩阵的转置对应对偶问

2、题中约束条件的系数矩阵。 原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。 原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。第二章第二章 对偶线性规划对偶线性规划原始问题（prime)与对偶问题之间的关系 极小化问题 （min) 极大化问题 （max) 变量 Xj 0 约束 aijwj bi Xj :unr aijwj =bi Xj 0 aijwj bi 约束 aijxj bi 变量 wj 0 aijxj = bi wj: unr aijxj bi wj 0 第二章第二章 对偶线性规划对偶

3、线性规划q对偶问题的形成min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unrq原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原

4、始问题约束条件的性质影响对偶问题变量的性质，用 表示第二章第二章 对偶线性规划对偶线性规划对偶问题的解p84 当原始问题有最优解时，对偶问题也有最优解，而且两者相等； 原问题的最优解和对偶问题的最优解构成互补松弛关系； 原问题最优表中松弛变量的检验数的反号就是对偶问题的最优解；对偶问题最优表中松弛变量的检验数的反号就是原问题的最优解。第二章第二章 对偶线性规划对偶线性规划1、对偶的对偶就是原始问题max z=-CTXs.t. -AX-bX 0Minw=-bTys.t. -ATy-Cy 0max w=bT ys.t. AT y C y 0min z=CTXs.t. AXb X 0对偶的定义对偶的

5、定义二、对偶问题的性质二、对偶问题的性质第二章第二章 对偶线性规划对偶线性规划2、可行解的目标函数值之间的关系 设XF、 y F分别是原始问题和对偶问题的可行解z=CTXF y TAXF y Tb=w3、最优解的目标函数值之间的关系 设Xo、yo分别是原始问题和对偶问题的最优解 z=CTXo= y oTAXo= y oTb=w第二章第二章 对偶线性规划对偶线性规划4、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t. AX-u=b X, u0max w=bTys.t. ATy+v=C y, v0min z=CTXs.t. AXb X 0max w=bTys.t. ATyC y

6、0对偶引进松弛变量引进松弛变量XTv=0 yTu=0互补松弛关系互补松弛关系X，uy，v第二章第二章 对偶线性规划对偶线性规划min z=CTXs.t.AX-u=bX, u 0max w=bTys.t. ATy+v=Cy, v 0XTv=0yTu=0mn=yvATICn=Au-IbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数第二章第二章 对偶线性规划对偶线性规划y1 yi ym vm+1 vm+j vn+m x1 xj xn un+1 un+i un+m 对偶问题的变量 对偶问题的松弛变量 原始问题的变量 原始问题的松弛变量xjvm+j=0yiun+i=

7、0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0第二章第二章 对偶线性规划对偶线性规划1、单纯形表最优基必须同时满足两个条件右端列中的所有i0 可行性条件全部检验数j0 最优性条件（1）（2）三、对偶单纯形法三、对偶单纯形法第二章第二章 对偶线性规划对偶线性规划单纯形法的迭代过程单纯形法的迭代过程 i 0 j0 i0 j 0 i0 j0 对偶单纯形法的迭代过程对偶单纯形法的迭代过程 i0 j0 第二章第二章 对偶线性规划对偶线性规划2 2、对偶单纯形法、对偶单纯形法 例题例题1 1min=15y1+5y2+11y3s.t. 3y1+2y2+2y355y1+y

8、2+2y34y1，y2，y30解:将每个不等式两边乘以-1,再引入松驰变量S1和S2, 则上述问题化为:直接写成标准式时有-S1和-S2,则无法有初始基,因此乘个-1min=15y1+5y2+11y3 s.t. -3y1-2y2-2y3+ S1 = -5 -5y1-y2-2y3+ S2 = -4 y1，y2，y3, S1,S2,0第二章第二章 对偶线性规划对偶线性规划 对偶单纯形法对偶单纯形法2 建立该问题的初始单纯形表 y1y2y3s1s2右端-15-5-11 0 0 0s1-3-2-210 -5s2-5-1-2 01-4 由表知1的两个基变量均取负值,故它不是可行基,从而不能从1出发应用单

9、纯形法。但由于表(I)中所有j0,我们目的是要保证全部检验数始终为非正的前提下,逐步使全部基变量取的值0,为此要按以下方法换基. (I)第二章第二章 对偶线性规划对偶线性规划 对偶单纯形法对偶单纯形法3出基变量确定出基变量确定：可选任何一个取负值的基变量（通常选：可选任何一个取负值的基变量（通常选 取值最小的一个）为出基变量取值最小的一个）为出基变量入基变量的确定入基变量的确定：考虑出基变量行中那些取负值的：考虑出基变量行中那些取负值的ijij, , 对每个这样的对每个这样的ijij, ,作比式作比式j j/ /a aijij令：令：=min=minj j/ /a aijija aijij0=

10、 0= s s/ /a aisis则取则取x xs s为入基变量。为入基变量。 (I) y1y2y3s1s2右端-15-5-11 0 0 0s1-3-2-210 -5s2-5-1-2 01-4第二章第二章 对偶线性规划对偶线性规划然后进行单纯形迭代,得表（II） (III) -15/20-6-5/2 025/2y23/211-1/2 05/2s2-7/2 0-1-1/21-3/2 (II) 0 0-27/7-10/7-15/7110/7y2014/7-5/73/713/7y1102/71/7-2/73/7 得最优解：y1=3/7,y2=13/7,y3=s1=s2=0 第二章第二章 对偶线性规划

11、对偶线性规划q对偶单纯形法对偶单纯形法对偶单纯形法用来求解最优性条件满足，可行性条件不满足的问题。对偶单纯形法的步骤Step 0：从一个最优性条件满足，可行性条件不满足的解出发，确定基变量、非基变量，列出单纯形表，转Step 1。Step 1：如果右边常数全为非负，得到最优解，算法终止。否则，选择右边常数为负数，绝对值最大的基变量离基，转Step 2。Step 2：在离基变量行中，选择系数为负数并且和目标函数行的比值最小的元素作为主元，确定进基变量。Step 3：对单纯形表进行行变换，使主元为1，主元所在列的其他元素为0，转Step 1。第二章第二章 对偶线性规划对偶线性规划1、原始问题是利润

12、最大化的生产计划问题0. .max2121221122222212111121211122211mnnnnmmnnmnmmnnnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxat sxcxcxcz单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）四、对偶的经济解释四、对偶的经济解释第二章第二章 对偶线性规划对偶线性规划2、对偶问题0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayay

13、atsybybybw资源限量（吨）资源价格（元/吨）总租金（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min w第二章第二章 对偶线性规划对偶线性规划3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzyiooimmiiybybybybwz2211mmiiiybybbybybzz)(2211iiybz第二章第二章

14、对偶线性规划对偶线性规划4、互补松弛关系的经济解释wixn+i=0如果wi0，则xn+i=0如果xn+i0，则wi=0边际利润大于0的资源，在最优生产计划条件下没有剩余wm+jxj=0如果wm+j0，则xj=0如果xj0，则wm+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）第二章第二章 对偶线性规划对偶线性规划max z=4x1+3x2+5x3s.t. 2x1+x2+3x3200 x1+2x2+2x3350 3x1+4x2 +x3220 2x1+3x2+2x3400 x1，x2，x3

15、0产品1产品2产品3资源限量资源12.01.03.0200资源21.02.02.0350资源33.04.01.0220资源42.03.02.0400利润4.03.05.0第二章第二章 对偶线性规划对偶线性规划引进松弛变量x4,x5,x6，x70,得到： max z=4x1+3x2+5x3 s.t. 2x1+x2+3x3+x4 =200 x1+2x2+2x3 +x5 =350 3x1+4x2 +x3 +x6 =220 2x1+3x2+2x3 +x7 =400 xi0第二章第二章 对偶线性规划对偶线性规划得到最优解：X1=0,x2=460/11=41.82,x3=580/11(件），最大利润z=3

16、89.09(万元），可以得到资源的剩余量：X4=200-(2x1+x2+3x3)=0(t)X5=350-(x1+2x2+2x3 )=1770/11=160.9(t)X6=220-(3x1+4x2 +x3 )=0X7=400-(2x1+3x2+2x3 )=1860/11=169.9第二章第二章 对偶线性规划对偶线性规划 这个问题的对偶问题是： Min y=200w1+350w2+220w3+400w4 S.t 2w1+w2+3w3+2w4-w5 =4 w1+2w2+4w3+3w4 w6 =3 3w1+2w2+w3+2w4 -w7 =5 wi0 第二章第二章 对偶线性规划对偶线性规划 利用互补松弛关系，得到： W1=17/11,w2=0,w3=4/11,w4=0,w5=2/11 即四种资源的影子价格为： W1=17/11,w2=0,w3=4/11,w4=0 由此可以计算出三种产品的机会成本： 产品1：2w1+w2+3w3+2w4 =4.18（万元/件） 产品2：w1+2w2+4w3+3w4 =