《线性规划对偶资料》由会员分享，可在线阅读，更多相关《线性规划对偶资料（22页珍藏版）》请在金锄头文库上搜索。
1、线性规划的对偶理论线性规划的对偶理论 Dual Theory 2.1 对偶问题的提出对偶问题的提出 例例常山机器厂生产常山机器厂生产 I I、 IIII 两种产品。这两种产品两种产品。这两种产品 都分别要在都分别要在ABCABC三种不同设三种不同设 备上加工。按工艺规定，生备上加工。按工艺规定，生 产每件产品的单位利润、消产每件产品的单位利润、消 耗三种设备的工时以及各种耗三种设备的工时以及各种 设备工时的限额如表设备工时的限额如表： 如何安排生产才能使如何安排生产才能使 总的利润最大？总的利润最大？ 消耗设备消耗设备 工时工时 I IIIII设备工时设备工时 限量限量 设备设备A A 设备设
2、备B B 设备设备C C 2 4 0 2 0 5 12 16 15 利润（元）利润（元） 23 解：max z=2 x1+3 x2 2 x1+2 x2 12 4x1 16 5x2 15 x10，x2 0 s.t. LP1 假设另有四海机器厂想租借常山机器厂的全部可用资源进假设另有四海机器厂想租借常山机器厂的全部可用资源进 行生产。问：如何定位各设备的出租价格，才能使得常山机行生产。问：如何定位各设备的出租价格，才能使得常山机 器厂愿意出租设备，且四海机器厂所付租金最少。器厂愿意出租设备，且四海机器厂所付租金最少。 解：设解：设A、B、C设备每小时出租的价格分别为设备每小时出租的价格分别为y1、
3、y2、y3元元， 则新的线性规划数学模型为：则新的线性规划数学模型为： 123 12 13 123 min121615 24 2 s. . 2 53 ,0 wyyy yy tyy y yy LP2 消耗设备消耗设备 工时工时 I IIIII设备工时设备工时 限量限量 设备设备A A 设备设备B B 设备设备C C 2 4 0 2 0 5 12 16 15 利润（元）利润（元） 23 对偶性是线性规划问题的最重要的内容之一。对偶性是线性规划问题的最重要的内容之一。 每一个线性规划（每一个线性规划（LPLP1 1）必然有与之相伴而生的另）必然有与之相伴而生的另 一个线性规划问题（一个线性规划问题（
4、LPLP2 2），即任何一个求），即任何一个求maxmax z z 的的LPLP1 1都有一个求都有一个求minmin w w的的LPLP2 2。 将将LPLP1 1称为“原问题”，记为称为“原问题”，记为P P ； 将将LPLP2 2称为“对偶问题”，记为称为“对偶问题”，记为D D 。 1 1、基本概念、基本概念 12 12 1 2 12 max 23 2212 4 16 s.t. 5 15 , 0 zxx xx x x xx 123 12 13 123 min121615 24 2 s.t. 2 53 ,0 wyyy yy yy y yy 原问题（原问题（P P）：）： 对偶问题（对偶问
5、题（D D）：）： 原问题P对偶问题 D 原变量x1,x2对偶变量y1,y2,y3 原目标z对偶目标 w 原约束对偶约束 12 13 123 24 2 2 53 ,0 yy yy y yy 12 1 2 12 2212 4 16 5 15 , 0 xx x x xx 变量变量约束约束 2、基本形式对偶 原问题原问题P max z = c1 x1+ c2 x2 + +cn xn s.t.a11 x1+ a12 x2 + +a1n xnb1 a21 x1+ a22 x2 + +a2n xnb2 am1 x1+ am2 x2 + +amn xnbm xj 0，（j=1,2, ,n） 对偶问题对偶问题
6、D min w = b1y1+ b2 y2+ + bm ym s.t.a11 y1+ a21y2+ + am1 ymc1 a12 y1+ a22y2+ + am2 ymc2 a1n y1+ a2ny2+ + amn ymcn yi0，(i=1,2, ,m ) 12 ( ,) n Cc cc 1 2 n x x X x 其中 11121 21222 1 2 n n mmmn aaa aaa A aaa 1 2 m b b b b 1 2 m y y Y y ,为的转置 TTT bACb A C (P)max z=CX s.t. AXb x0 (D)min w=b s.t. A Y0 T TT Y
7、 YC 矩阵形式矩阵形式 例：写出下列例：写出下列LPLP问题的对偶问题问题的对偶问题 123 12 13 123 min81612 45 246 ,0 wyyy yy styy yyy 解：对偶问题为：解：对偶问题为： 12 12 1 2 12 max56 28 416 412 ,0 zxx xx x st x xx 2.2 原问题与对偶问题 1 1、基本形式的联系与区别、基本形式的联系与区别 （1 1）原目标求极大，对偶目标求极小；）原目标求极大，对偶目标求极小； （2 2）原约束个数）原约束个数= =对偶变量个数对偶变量个数原变量个数原变量个数= =对偶约束个数对偶约束个数 原约束决定对
8、偶变量原约束决定对偶变量 原变量决定对偶约束原变量决定对偶约束； （3 3）原约束）原约束方向，对偶约束方向，对偶约束方向；方向； （4）原目标的系数对应对偶约束的右端常数）原目标的系数对应对偶约束的右端常数 原约束的右端常数对应对偶目标的系数；原约束的右端常数对应对偶目标的系数； （5）原系数矩阵与对偶系数矩阵互为转置；）原系数矩阵与对偶系数矩阵互为转置； （6）原变量与对偶变量都是非负取值。）原变量与对偶变量都是非负取值。 例例 将下列问题作为原问题，写出其对偶问题将下列问题作为原问题，写出其对偶问题。 123 12 13 123 min121615 24 2 s.t. 2 53 ,0 w
9、yyy yy yy y yy 123 12 13 123 max121615 24 2 s.t.2 53 ,0 wyyy yy yy y yy 解：先改写为原问题的基本形式：解：先改写为原问题的基本形式： 2 2、互为对偶关系、互为对偶关系 12 12 1 2 12 min 23 2212 4 16 s.t. 5 15 , 0 zxx xx x x xx 再对偶化：再对偶化： 12 12 1 2 12 max 23 2212 4 16 s.t. 5 15 , 0 zxx xx x x xx 最后简化得到已知问最后简化得到已知问 题的对偶问题：题的对偶问题： 123 12 13 123 max1
10、21615 24 2 s.t.2 53 ,0 wyyy yy yy y yy 若若LP2是是LP1的对偶问题，则的对偶问题，则LP1是是LP2的对偶问题。的对偶问题。 min Z= - CX s.t. -AX- b X 0 min W= b TY s.t. ATYCT Y 0 max Z=C X s.t. AXb X 0 对偶的定义对偶的定义 对偶的定义对偶的定义 max W= -bTY s.t. -ATY-CT Y 0 改写改写 改写改写 2.3 对偶问题的基本性质 ( ) max s.t. 0 PzCX AXb X ( ) min s.t. 0 T TT Dwb Y A YC Y 在本节中
11、设原问题和对偶问题如下：在本节中设原问题和对偶问题如下： 设设和和分别是问题分别是问题P P和和D D的可行解，则必有的可行解，则必有 _ X _ Y _ T C Xb Y TT TTT TTT AXbY AXY b A YCCY A CXY AXY bb Y 证明：证明： 1 1、弱对偶性（弱对偶原理）、弱对偶性（弱对偶原理） ( ) max s.t. 0 PzCX AXb X ( ) min s.t. 0 T TT Dwb Y A YC Y 若若 X X* * 和和 Y Y* * 分别是分别是 P P 和和 D D 的可行解且的可行解且 CXCX* * = = B BT TY Y* * ，
12、 则则X X* *，Y Y* *分别是问题分别是问题 P P和和D D 的最优解。的最优解。 2 2、最优性：、最优性： 若原问题有无界解，则对偶问题无可行解。若原问题有无界解，则对偶问题无可行解。 若对偶问题有无界解，则原问题无可行解。若对偶问题有无界解，则原问题无可行解。 3 3、无界性、无界性 注：逆定理不成立。注：逆定理不成立。 即“如果原问题无可行解，那么对偶问题有无界解”不成立即“如果原问题无可行解，那么对偶问题有无界解”不成立 。此时，对偶问题可能有无界解，也可能无可行解。此时，对偶问题可能有无界解，也可能无可行解。 4、强对偶性（对偶定理） 若原问题有最优解，则对偶问题一定有最
13、优解，且 ZMAX=WMIN . 证证： 设设X*是原问题的是原问题的最优解，则所有检验数都非正。最优解，则所有检验数都非正。 即即 = C- -CB B- -1 A 0 CBB-1A C 令令 CBB- -1=Y* T，有，有 Y*TA C, 转置得转置得A TY* CT - 又因为又因为 S = - -CBB- -1= -Y * T 0，所以，所以Y* = -（ S） ）T 0- 由由知知Y*是对偶问题的可行解，是对偶问题的可行解， 且满足且满足 CX*= CBb =CB (B- -1 b) = CB B- -1b = Y*Tb= b TY* 由最优性，由最优性， Y*是对偶问题的是对偶问题的最优解。最优解。 注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解 是第三列，而对偶问题的最优解是松弛变量检验数的相反数。是第三列，而对偶问题的最优解是松弛变量检验数的相反数。 345 例 下面是某问题的最优单纯形表， 其中,为松弛变量， 请直接写出该问题及对偶问题的最优解。 LP xxx *T 31 其对偶问题的最优解为Y(,0) 28 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 4 4 2 2 X1 0 X5 3 X2 x1 x2 x3 x4 x5 CB XB
