《对偶问题.ppt.convertor》由会员分享，可在线阅读，更多相关《对偶问题.ppt.convertor（17页珍藏版）》请在金锄头文库上搜索。
1、第 2 章 线性规划的对偶理论Duality 对偶Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划Dual Theory 对偶理论2.1 问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要 A、B、C、D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大? 1.最大生产利润模型设 企业生产甲产品为 X1 件， 乙产品为 X2 件，则 max z= 2 X1 +3 X2 s.t 2 X1 +2 X2 12 X1 +2 X2 8 4 X1 16 4 X
2、2 12X1 0 , X2 02.资源最低售价模型(原问题) ( 对偶问题)设第 i 种资源价格为 yi,（ i=1, 2, 3, 4,） 则有min w= 12y1 + 8y2 + 16y3 +12 y4s.t 2y1 + y2 + 4y3 +0 y4 2 2y1 +2y2 + 0y3 +4 y4 3yi 0, (i=1, 2, 3, 4 )y1y2y3y42.2 原问题与对偶问题的关系一般表示式：原问题： max z = c1 X1 + c2 X2 + + cn Xns.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b
3、2 am1 X1 + am2 X2 + + amn Xn bmxj 0，j=1,2,n 对偶问题： min w = b1 y1 + b2 y2 + + bm ym s.t a11 y1 + a21 y2 + + am1 ym c1 a12 y1 + a22 y2 + + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn yi 0， (i=1,2,m )典式模型对应对偶结构矩阵表示（1） max z = C X s.t AX b X 0min w = Y bs.t YA CY 0 对偶问题原问题对偶模型其他结构关系（2）若模型为 max z = C X s.t AX
4、 b X 0max z = C Xs.t - AX -b X 0变形min w = Y bs.t YA CY 0 Min w=Y (-b)st. Y (-A) C Y 0令 Y=- Y 对偶问题对偶变量 Y（3）max z = C X s.t AX b X 0变形设 X= -Xmax = -CX st. -AX b X 0min w = Y bs.t YA CY 0则有min w = Y bs.t -YA - CY 0对偶问题典式：用矩阵形式表示：（1） max z = C X min w = Y bs.t AX b s.t YA CX 0 Y 0 （2） max z = C X min w
5、= Y bs.t AX b s.t YA CX 0 Y 0 （3）max z = C X min w = Y bs.t AX b s.t YA CX 0 Y 0原问题（或对偶问题） 对偶问题（或原问题） 目标函数 MaxZ目标函数 MinW约束条件数：m个第 i 个约束条件类型为“”第 i 个约束条件对偶变量数：m个第 i 个变量 0第 i 个变量 0第 i 个变量是自类型为“”第 i 个约束条件类型为“=” 由变量 决策变量数：n个第 j 个变量0第 j 个变量0第 j 个变量是自由变量 约束条件数：n第 i 个约束条件类型为“”第 i 个约束条件类型为“”第 i 个约束条件类型为“=” 例
6、 2-3 写出下面线性规划的对偶问题： 课堂练习：写出下面线性规划的对偶规划：下面的答案哪一个是正确的？为什麽？ （原问题是极小化问题，因此应从原始对偶表的右边往左边查！）例题 2minZ=3x1+2x2-6x3+x5 2x1+x2-4x3+x4+3x5 7 x1+ 2x3 -x4 4 -x1+3x2 -x4+ x5 =-2 x1，x2，x3 0; x4 0;x5 无限制 max =7y1+4y2-2y32y1+ y2- y3 3y1 +3y3 2-4y1+ 2y2 -6y1 -y2 -y3 03y1 +y3=1y1 0 y2 0 y3 无约束2.3 对偶问题的基本性质Max z = CX M
7、in w = Y bs t . AX b s t . YA CX 0 Y 0(1) 弱对偶性：若 X0原问题可行解，Y0 对偶问题可行解则 CX0 Y0 b证明： Y0 0， AX0 b， Y0 AX0 Y0 b，而 Y0 A C ， CX0 Y0AX0 ， CX0 Y0 AX0 Y0 b （2）最优性：若 X0原问题可行解， Y0对偶问题可行解，且 CX0 = Y0 b则 X0原问题最优解， Y0对偶问题最优解证明：设 X* 原问题最优解， Y* 对偶问题最优解则 CX0 CX* Y* b Y0 b但 CX0 = Y0 b， CX0 = CX* = Y* b = Y0 b X0 = X* ，
8、 Y0 = Y* 即 X0原问题最优解， Y0对偶问题最优解证毕。 （3）无界性若原问题最优解无界，则对偶问题无可行解证：有性质 1，C X0 Y0 b，当 CX0 时，则不可能存在 Y0，使得 C X0 Y0 b 。注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么对偶问题（或原问题） “解无界”不成立。（4）强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且有 z max = w min证： 由 = C- CB B-1 A 0 令 CBB-1 = Y* ， 得 Y* A C若 -Y * = -CBB-1 0，则 Y* 0因此， Y*是对偶问题的可行解，又 CX* =
9、CB (B-1 b) = CB B-1b = Y* b Y*是对偶问题的最优解。（5）互补松弛性n若 y i * 0, 则 aij xj* = bi j=1 n若 a ij xj* 0, a ij xj* - bi =0, 即 a ij xj* = bi 当 a ij xj* - bi 0 选择 y 作入基变量， py= B-1 py= =-0.5 1.5 2 0.25T 继续迭代：cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 -8 2 x1 4 0 x6 -12 3 x2 60 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -1.5 -0.125 00 x3 -2 2 x1 4 0 x6 6 3 x2 30 0 1 0 -0.5 -0.5 1 0 0 0 0.25 0 0 0 0 1 -0.25 -0.5 0 1
