下载文档原格式
第2 章线性规划的对偶理论Duality 对偶Dual Problem 对偶问题Dual Linear Programming对偶线性规划Dual Theory 对偶理论2.1 问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。
问:如何安排产品的生产计划,才能使企业获利最大?1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则max z= 2 X1 +3 X2s.t 2 X1 +2 X2 12X1 +2 X2 84 X1 164 X2 12X1 0 , X2 02.资源最低售价模型(原问题) <========> ( 对偶问题)设第i种资源价格为yi,（i=1, 2, 3, 4,）则有min w= 12y1 + 8y2 + 16y3 +12 y4s.t 2y1 + y2 + 4y3 +0 y4 22y1 +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 b1a21 X1 + a22 X2 + ┈+ a2n Xn b2·······················am1 X1 + am2 X2 + ┈+ amn Xn bmxj 0，j=1,2,┈,n对偶问题：min w = b1 y1 + b2 y2 + ┈+ bm yms.t a11 y1 + a21 y2 + ┈+ am1 ym c1a12 y1 + a22 y2 + ┈+ am2 ym c2·························a1n y1 + a2n y2 + ┈+ amn ym cnyi 0，(i=1,2,···,m )典式模型对应对偶结构矩阵表示（1）max z = C Xs.t AX bX 0min w = Y bs.t YA CY 0对偶问题原问题对偶模型其他结构关系（2）若模型为max z = C Xs.t AX b X 0max z = C Xs.t - AX -bX 0变形min w = Y bs.t YA CY 0Min w=Y ´(-b)st. Y ´(-A) C Y ´ 0令Y=- Y ´对偶问题对偶变量Y（3）max z = C Xs.t AX b X 0变形设X= -X´max = -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 = 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 Y A CX 0 Y例2-3 写出下面线性规划的对偶问题：课堂练习：写出下面线性规划的对偶规划：下面的答案哪一个是正确的？为什麽？（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）例题2minZ=3x1+2x2-6x3+x52x1+x2-4x3+x4+3x5 ≥7x1+ 2x3 -x4 ≤4-x1+3x2 -x4+ x5 =-2x1，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 Min w = Y bs t . AX b s t . YA CX 0Y 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* ，Y0 = Y*即X0——原问题最优解，Y0——对偶问题最优解证毕。
第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；防止使用人工变量(人工变量带来很多麻烦，两阶段法那么增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。
加工木门收入为56元/扇，加工木窗收入为30元/扇。
生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？(2)假假设有一个个体经营者，手中有一批木器家具生产订单。
他想利用该木器车间的木工与油漆工来加工完成他的订单。
他就要考虑付给该车间每个工时的价格。
他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，那么数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
