《运筹学》第二章 对偶问题

1、1第 2 章 线性规划的对偶理论 2.1 对偶问题的提出 2.2 原问题与对偶问题的关系 2.3 对偶问题的性质 2.4 影子价格 2.5 对偶单纯形法 2.6 灵敏度分析 2.7 参数线性规划2对偶：Duality 对偶问题： Dual Problem 对偶线性规划： Dual Linear Programming 对偶理论： Dual Theory 32.1 对偶问题的提出例：某企业计划生产甲、乙两种产品，该两种产品均需要A、B、C、D 四种不同的材料，按工艺资料规定，生产一单位甲乙产品需要各种材料数量及单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大? 4解：设企业

2、生产甲产品为X1件， 乙产品为X2件，则 max z= 2 X1 +3 X2 s.t . 2 X1 +2 X2 12 X1 +2 X2 8 4 X1 16 4 X2 12 X1 0 , X2 05如果另外一企业想将上述企业拥有的资源收买过来，至少应付出多少代价，才能使第一个企业愿意放弃生产活动，出售资源？我出让资源的代价不应低于我自己组织生产时的产值!我要用最小的代价购买资源!注: 关键是确定转让价格6设第i种资源单位增值价单位增值价（售价成本增值），为yi,（ i=1, 2, 3, 4）, 则有min w= 12y1 + 8y2 + 16y3 +12 y4s.t. 2y1 + y2 + 4y

3、3 +0 y4 2 2y1 +2y2 + 0y3 +4 y4 3yi 0, (i=1, 2, 3, 4 )71.最大生产利润模型设 企业生产甲产品为X1件,乙产品为X2件，则 max z= 2 X1 +3 X2 s.t 2 X1 +2 X2 12 X1 +2 X2 8 4 X1 16 4 X2 12 X1 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=

4、1, 2, 3, 4 )y1y2y3y4注：考虑角度不同，模型中的系数有对应关系。8对偶问题： min w = b1 y1 + b2 y2 + + bm ym 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 )2.2 原问题与对偶问题的关系原问题： max z = c1 x1 + c2 x2 + + cn xn a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a2n xn b2 am1

5、x1 + am2 x2 + + amn xn bm xj 0，j=1,2,n 一般形式：目标函数系数: C=c1 c2 cn 系数矩阵: A=aijmn 约束右端项: b=b1b2:bm目标函数系数: b 系数矩阵: A 约束右端项: C9（1） max z = C X s.t AX b X 0典式模型的对偶结构的矩阵表示min w = Y b s.t YA C Y 0 对偶问题原问题Y=(y1,ym)10(2) max z = C X s.t AX b X 0max z = CX s.t - AX -b X 0变形min w = Y b s.t YA C Y 0 min w=Y (-b) s

6、t. Y (-A) C Y 0令 Y=- Y 对偶问题对偶变量Y其它模型的对偶结构的矩阵表示11（3）max z = C X s.t. AX b X 0变形设X= -Xmax z= (-C)X s.t. (-A)X b X 0min w = Y b s.t. YA C Y 0min w = Y b s.t. Y(-A) - C Y 0对偶变量Y12原问题与对偶问题的对应关系用矩阵形式表示： （1） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （2） max z = C X min w = Y b s.t AX b s.t YA C X 0

7、 Y 0 （3）max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 013 原问题原问题(对偶问题对偶问题) 对偶问题对偶问题(原问题原问题) 目标函数系数目标函数系数 约束右端项约束右端项 约束右端项约束右端项 目标函数系数目标函数系数 约束条件系数列向量约束条件系数列向量 A约束条件系数行向量约束条件系数行向量 A 变量个数变量个数 约束条件个数约束条件个数max min 变量变量 x j : 第第j个约束方程个约束方程 : x j 0 x j 无约束无约束 = x j 0 第第i各约束方程各约束方程: 变量变量 y i : y i 0 = y

8、i 无约束无约束 y i 0 原问题与对偶问题的对应关系表14 无约束无约束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyW 例 写出下列线性规划问题的对偶问题.解：原问题的对偶问题为对偶问题的对偶还是原问题1512312312123123123max4324 3532 42 346310,0,无约束Zxxxxxxxxxxxxxxxxx 练习 写出下列线性规划问题的对

9、偶问题.162.3 对偶问题的基本性质 原问题 对偶问题 Max z = CXMin w = Y b s. t . AX b s. t . YA C X 0 Y 0(1) 弱对偶性(2) 最优性(3) 强对偶性(或称对偶定理)(4) 互补松弛性(5) 单纯形表上的对应关系 17(1)弱对偶性： 若X0是原问题可行解，Y0是对偶问题可行解，则CX0 Y0 b证明： Y0 0， AX0 b， Y0 AX0 Y0 b， 而 Y0 A C ， CX0 Y0AX0 ， CX0 Y0 AX0 Y0 b 由弱对偶性，可得以下结论：(1) 原问题(对偶问题)任一可行解的目标函数值是其对偶问题(原问题)目标函数

10、值的下(上)界；(2) 若原问题(或对偶问题)具有无界解，则对偶问题(或原问题)无可行解。其逆定理不成立，即如果原问题（对偶问题）无可行解，那么对偶问题（或原问题）无可行解，或者有可行解（此时有无界解）。 证明：由性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b 。(3) 若原问题(对偶问题)有可行解而其对偶问题(原问题)无可行解，则原问题(对偶问题)具有无界解。19(2) 最优性：若X0是原问题可行解，Y0是对偶问题可行解，且CX0 = Y0b，则X0是原问题最优解，Y0是对偶问题最优解。 证明：设X* 是原问题最优解，Y* 是对偶问题最优解， 则 CX

11、0 CX* Y* b Y0 b 但CX0 = Y0 b， CX0 = CX* = Y* b = Y0 b 即 X0是原问题最优解， Y0是对偶问题最优解。 20(3) 强对偶性（对偶定理）：若原(对偶)问题有最优解,则对偶(原)问题一定有最优解，且有z max = w min.证： 由 = C- CB B-1 A 0， s = 0- CB B-1 I 0，令 CBB-1 = Y* ，得 Y* A C，-Y * = -CBB-1 0， Y* 0， 因此， Y*是对偶问题的可行解， 又 CX* = CB (B-1 b) = CB B-1b = Y* b， 由性质2，Y*是对偶问题的最优解。21一组

12、互为对偶的线性规划问题的解之间只有下列三种情况:(1) 两个规划问题都有可行解(此时,两个规划问题都有最优解,且最优值相等);(2) 两个规划问题都不可行;(3) 一个规划问题不可行,另一个规划问题有可行解,且具有无界解。22（4）互补松弛性： 在线性规划问题的最优解中， n 若 y i * 0, 则 aij xj * = bi ； j=1 n 若 a ij xj * 0, 则 aij yi * = cj ； i=1 m 若 a ij yi* cj , 则 xj* = 0 i=123 n n m m 证： cj x j* = ( a ij y i* ) xj* = bi y i* j=1 j=

13、1 i =1 i =1 n m m ( a ij y i* ) xj* - bi y I* =0 j=1 i =1 i =1 m n ( a ij xj* - bi ）y i* =0 i =1 j=1 当 y i*0时, a ij xj* - bi =0, 即 a ij xj* = bi 当 a ij xj* - bi 0, y i*=0j=1j=1j=1 n n n24性质(4)的应用: 已知原问题(对偶问题)的最优解,求对偶问题(原问题)的最优解.25例 已知线性规划的最优解是X=(6,2,0),求其对偶问题的最优解Y. 3 , 2 , 1, 0162210243max321321321j

14、xxxxxxxxxxzj26解：写出原问题的对偶问题，即 0,1422321610min2121212121yyyyyyyyyyw因为X=(6,2,0), 所以y1+2y2=32y1+2y2=4解得y1=1,y2=1。所以对偶问题的最优解为Y*=(1,1), 最优值为w=26.27例 已知线性规划max z=2x1+x2+5x3+6x4 2x1+x3+x48 2x1+2x2+x3+2x412 xj0,j=1,2,3,4,其对偶问题的最优解是y1*=4,y2*=1，求原问题的最优解X.28解：写出原问题的对偶问题，即因为y1*=4,y2*=1，所以2x1+x3+x4=82x1+2x2+x3+2x

15、4=12又因为 2y1*+2y2*2 2y2*1所以x1*=0,x2*=0。求得原问题的最优解为X*=(0,0,4,4), 最优值为z=44.min w=8y1+12y2 2y1+2y22 2y21 y1+y25 y1+2y26 y1,y20, j=1,2,3,4,29（5）单纯形表中的对应关系 原问题 对偶问题 max z= 2 x1 +3 x2 min w= 12y1 + 8y2 + 16y3 +12 y4 s.t 2 x1 +2 x2 12 s.t 2y1 + y2 + 4y3 +0 y4 2 x1 +2 x2 8 2y1 +2y2 + 0y3 +4 y4 3 4 x1 16 yi 0,

16、 i=1, 2, 3, 4 4 x2 12 x1 0 , x2 0cj2 3 0 0 0 0CB XB b x1 x2 x3 x4 x5 x60 x3 02 x1 40 x6 43 x2 20 0 1 - 1 - 0.25 01 0 0 0 0.25 00 0 0 - 2 0.5 10 1 0 0.5 - 0.125 0cj-zj0 0 0 - 1.5 - 0.125 0 -y1 - y2 - y3 - y4 -y5 -y6用单纯形法对原问题求解30 原问题 对偶问题 max z= 2 x1 +3 x2 min w= 12y1 + 8y2 + 16y3 +12 y4 s.t 2 x1 +2 x

17、2 12 s.t 2y1 + y2 + 4y3 +0 y4 2 x1 +2 x2 8 2y1 +2y2 + 0y3 +4 y4 3 4 x1 16 yi 0, i=1, 2, 3, 4 4 x2 12 x1 0 , x2 0-y1 - y2 - y3 - y4Cj x1x2x3x4XBbCB2 3 0 0 0 02283x3 x1x5x20203cj - zj x5x6010000011000-21-4000100.5-0.520.25 0 0 0 -2 0 0.25 -y5 -y6用单纯形法对原问题求解312.4 影子价格(Shadow price)约束条件右侧（即资源）改变1个单位时，目标

18、函数（即利润）的变化量，它度量了约束条件对应的那种资源的价值，经济学上称为影子价格影子价格。z=c1x1*+cnxn*=b1y1*+bmym*注：(y1*, , ym*)=CBB-1，其中B是原问题的最优解的基变量在初始 表里对应的矩阵。*32市场价格影子价格商品的价值的货币表现资源最优利用时的边际价值随着市场的供求情况和有关方针，政策的变化而变化。随着经济结构的变化而变化，同一资源在不同的经济结构中影子价格不同。它的制定含定价者的主观因素它的形成完全由经济结构的客观条件确定。它的制定是个比较复杂的过程，不存在统一的计算公式。它的计算是比较容易的。用单纯形法求得任何一种商品的市场价格都不可能为

19、0影子价格可以为0，当资源过剩时，其影子价格为0市场价格为已知数，相对比较稳定。影子价格则有赖于资源利用情况，是未知数。因企业生产任务，产品的结构等情况发生变化，资源的影子价格也随之改变。影子价格与市场价格的比较33(1) 决定买进或卖出某种资源的参考依据(2) 对资源使用状况的估算（互补松弛性）(3) 机会成本： j = cj- CB B-1pj = cj- Ypj= cj- aijyi，其中 aijyi 为隐含成本。(4) 制定内部结算价格的参考。影子价格的作用影子价格的作用注:(1)影子价格在一定范围内有效的;(2)最优状态;(3)一个变。34产品原材料A B C甲乙丙单位利润（元）2

20、1 31 2 32 2 14 1 3原材料总量（kg）200500600例 某工厂利用原材料生产A，B，C三种产品，有关资料如上表示。(1) 怎么安排生产使利润最大？(2) 如果增加1kg的原材料甲，总利润增加多少？(3) 设原材料乙的市场价格为1.2元/kg，若要转让乙，工厂至少要叫价多少？为什么？(4) 单位产品利润分别在什么范围内变化时，原生产计划不变？(5) 原材料分别单独在什么范围波动时，仍只生产A和C两种产品？(6) 由于市场的变化，产品B和C的利润分别变为3元和2元时，应如何调整生产计划？(7) 工厂计划生产新产品D，每件产品D消耗原材料甲乙丙分别为2kg，2kg，1kg，每件产

21、品D应获利多少才有利于生产？362.5 对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。 单纯形法的基本思想：保持原问题为可行解(这时对偶问题一般不可行)的基础上，通过迭代，使目标函数向最优方向靠近，当对偶问题也达到可行解时，即得到了目标函数的最优值。 对偶单纯形法的基本思想：保持对偶问题为可行解(这时原问题一般不可行)的基础上，通过迭代，使目标函数向最优方向靠近，当原问题也达到可行解时，即得到了目标函数的最优值。37Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0 x3 x40

22、0cj - zj 保证此行为负保证此列非负Cj x1x2x3x4XBbCB-1 -1 1 0-1 -2 0 1-2 -3 0 0 x3 x400cj - zj 单纯形法对偶单纯形法38对偶单纯形法步骤：1.将min化成max形式，约束条件中出现单位矩阵；2.列初始单纯形表，使得所有检验数j 0 ；3.出基变量：取min bi0 = bl x(l)；4.入基变量：min |alk0 选择y作入基变量，继续迭代。 cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y0 x3 0 2 x1 4 0 x6 4 3 x2 20 0 1 -1 -0.25 0 -0.5

23、1 0 0 0 0.25 0 1.5 0 0 0 -2 0.5 1 2 0 1 0 0.5 -0.125 0 0.25cjzj0 0 0 -1.5 -0.125 0 1.250 x3 1 2 x1 1 5 y 2 3 x2 1.50 0 1 -1.5 -0.125 0.25 0 1 0 0 1.5 -0.125 -0.75 0 0 0 0 -1 0.25 0.5 1 0 1 0 0.75 -0.1875 -0.125 0cjzj0 0 0 -0.25 -0.4375 -0.625 061(4.1)aij工艺条件的变化Cj x1x2x3x4XBbCB2 3 0 0 x3 x203cj - zj

24、iP1P2P3P4如果xj在最后一张表里为非基变量，则B-1不变。步骤：(1)将Pi的变化反映到最终单纯形表上，即重新计算Pj=B-1(Pj + Pj)和检验数j;(2)如果所有检验数0，则已是最优；否则，按单纯形法确定换入换出变量，继续运算。62(4.2)aij工艺条件的变化Cj x1x2x3x4XBbCB2 3 0 0 x3 x203cj - zj iP1P2P3P4如果xj为基变量，则B-1变，此时，原问题与对偶问题都可能不可行，需要引进人工变量，将原问题转化为可行解，再用单纯形法求解。63(5)增加一个约束条件Cj x1x2x3x4XBbCB2 3 0 0 x3 x203cj - zj

25、 iP1P2P3P4步骤：(1)先判断最优解是否满足新的约束条件，如果是，仍然最优，否则，转第(2)步；(2)直接把新约束反映在在最后一张表的最后一行；(3)进行行初等变换，仍使基变量的系数列向量为单位向量；(4)如果b0,已最优，否则按照对偶单纯形法继续计算。64 max z= 2 x1 +3 x2 s.t 2 x1 +2 x2 12 x1 +2 x2 8 4 x1 16 4 x2 12 x1 0 , x2 0例：已知某线性规划模型及最终的单纯形表如下：例：已知某线性规划模型及最终的单纯形表如下：（1）若）若c2增加增加2个单位，最优解如何改变？个单位，最优解如何改变？（2）若）若b2增加增

26、加8个单位，最优解如何变化？个单位，最优解如何变化？（3）若引进一个新变量（产品）若引进一个新变量（产品）y，其目标函，其目标函 数系数数系数为为 cy=5，系数列向量为，系数列向量为py=3 2 6 3，问最优解是否，问最优解是否会改变？会改变？ cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 0 2 x1 4 0 x6 4 3 x2 20 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 065解： （1）当cj变化时，=CCB

27、B-1 A，列出单纯形表，重新求出检验数，如表中所示。 cj 2 5 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 0 2 x1 4 0 x6 4 5 x2 20 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 -2.5 0.125 00 x3 2 2 x1 2 0 x5 8 5 x2 30 0 1 -2 0 0.5 1 0 0 1 0 -0.5 0 0 0 -4 1 2 0 1 0 0 0 0.25cjzj0 0 0 -2 0 -0.2566（2）（b+b）=B-1

28、 b+ B-1 b = b+B-1 b =0 4 4 2T + -8 0 -16 4 T = -8 4 -12 6 TB-1 b =1 -1 -0.25 0 0 0 0.25 0 0 -2 0.5 1 0 0.5 -0.125 00 8 0 0=-8 0 -16 4 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 0 利用对偶单纯形

29、法继续 求最优解。0 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 067 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 6cjzj0 0 0 -1.5 -0.125 00 x3 -2 2 x1 4 0 x4 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 0 0 0 0.25cjzj0 0 0 0 -0.5 -0.750 x5 4 2 x1 3

30、0 x4 7 3 x2 30 0 -2 0 1 1 1 0 0.5 0 0 -0.25 0 0 -0.5 1 0 -0.25 0 1 0 0 0 0.25cjzj0 0 -1 0 0 -0.25返回右端项变化分析单纯形表：68（3）增加y时， py= B-1 py= =-0.5 1.5 2 0.25T y= cy- CB B-1 py=5- (0 1.5 0.125 0) 3 2 6 3T =1.250 选择y作入基变量，继续迭代。 cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y0 x3 0 2 x1 4 0 x6 4 3 x2 20 0 1 -1 -

31、0.25 0 -0.5 1 0 0 0 0.25 0 1.5 0 0 0 -2 0.5 1 2 0 1 0 0.5 -0.125 0 0.25cjzj0 0 0 -1.5 -0.125 0 1.250 x3 1 2 x1 1 5 y 2 3 x2 1.50 0 1 -1.5 -0.125 0.25 0 1 0 0 1.5 -0.125 -0.75 0 0 0 0 -1 0.25 0.5 1 0 1 0 0.75 -0.1875 -0.125 0cjzj0 0 0 -0.25 -0.4375 -0.625 0(4) c2变为8,p2变为3，2，0，6 cj 2 3 0 0 0 0 CB XB b

32、 x1 x2 x3 x4 x5 x60 x3 0 2 x1 4 0 x6 4 3 x2 20 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 0 x2102185 cj 2 8 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 -2 2 x1 4 0 x6 0 8 x2 20 0 1 -1.5 -0.125 0 1 0 0 0 0.25 0 0 0 0 -3 0.75 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -4 0.5 0 c

33、j 2 8 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 -2 2 x1 4 0 x6 0 8 x2 20 0 1 -1.5 -0.125 0 1 0 0 0 0.25 0 0 0 0 -3 0.75 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -4 0.5 0-2=x3-1.5x4-0.125x52=-x3+1.5x4+0.125x5+x7 cj 2 8 0 0 0 0 -M CB XB b x1 x2 x3 x4 x5 x6 x7-M x7 2 2 x1 4 0 x6 0 8 x2 20 0 -1 1.5 0.125 0 1 0 0 0 0.2

34、5 0 0 0 0 -3 0.75 1 0 1 0 0.5 -0.125 0cjzj1000712.7 参数线性规划 1. 概念：研究目标函数值随某一参数变化的规律及最优解相应的变化。2. 算法：先令变化量=0，再考察随着的增加引起解的变化情况。3. 最后，画出目标值随的变化所形成的曲线。72例：有如下线性规划模型： max z=2x1+3x2 s.t x1+x23 x1+2x2 4 + x10, x20（ 0 ）max z=2x1+3x2+0 x3 +0 x4 s.t x1+x2+x3=3 x1+2x2+x4=4 xj 0, (j=1,2,3,4) （1）当 =0 时的最优解；（2）当0时，

35、z 值的变化规律。解：先令 =0，有下述模型的标准形利用单纯形法求解：73Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj - zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj - zj 1/2 0 0 -3/2031 0 2 -1 0 1 -1 1x1 x221cj - zj 0 0 -1 -123（ =0）74Cj x1x2x3x4XBbCB2 3 0 02- 1+ x1 x223cj - zj -1 0 -2 1 1 1 1 0 x4 x2cj - zj -1 0 -3 0030 0 -1 -11 0 2

36、-1 0 1 -1 1（0 2）当0时， b= B-1b= B-1b (0 )T = (- )T，继续迭代如下：（对偶单纯形法） -2 3 （2）其变化曲线如下：75Z ( )027976例： 某大学教授利用部分业余时间从事咨询工作。现有三个A、B、C企业欲聘请，各自每小时的咨询费用分别为10，12，16元。教授每月可用于外出咨询的时间为40小时，但对每个企业而言，用于准备的时间与咨询所花的时间的比例分别为0.1，0.5，0.8，教授每月可用于准备的时间应不超过24小时。若假定三个企业每月要求的咨询时间可分别达到80，60，20小时。现问：教授应作何种决策，才能使收益最大？ 从目前看，教授有许

37、多咨询机会，但可用的外出咨询时间及准备的时间有限，所以可考虑雇用助手（用于帮助准备），但要支付每小时4元的费用，现帮助教授分析一下，它是否该雇用助手，若需雇用，每月应雇用多少时间？77设 用于三个企业咨询的时间分别为Ax1， Bx2， Cx3，Max z=10 x1+12x2+16x3s.t. x1+x2+x340 0.1x1+0.5x2+0.8x324 x180 x2 60 x3 20 x10, x20, x30+- 4第2章 对偶理论学习要求1、能够由原问题写出其对偶问题；2、了解对偶问题的基本性质：弱对偶性、无界性、最优性、对偶定理、互补松弛性、原问题与对偶问题的解的对应关系（会利用这些

38、性质解题） ；3、了解影子价格的含义；4、了解对偶单纯形法的求解思路；5、掌握bi和cj变化时的灵敏度分析。练习题 1 已知线性规划 min z=x1+2x3s.t. x1+x2+x36 2x1-x2+3x35 x1,x2,x3 0（1）写出该LP的对偶规划LD； (2) 求LP和LD的最优解和最优目标值； （3）将目标变成z=x1+x3,约束条件不变，何为其解？79计算机与信息工程学院 2 设有线性规划如下：max z=c1x1+c2x2s.t. a11x1+a12x2b1 a21x1+a22x2 b2 x1,x20, b1, b20在第一，二约束中加入松弛变量x3,x4( 0)后，引入人工

39、变量x5 ( 0),并用大M法求解，得到最优单纯形表如下：要求：写出原LP和对偶的LD，并用对偶性质求LD的最优解。Cj x1x2x3x4XBbCB1 0 1/3 2/3 -2/3 0 1 1/3 -1/3 1/312x1 x2cj - zj 00-4/3 -5/3ix55/3-M3 已知线性规划 max z=x1+2x2+3x3+4x4s.t. x1+2x2+2x3+3x4a 2x1+x2+3x3+2x420 x1,x2,x3 ,x40已知其最优解是X*=(b,c,4,4),且b 0,c 0.假设以上对偶问题的最优解为Y*=(d,1/5),请确定a,b,c,d的值。81a=20,b=c=0,

40、d=1.22022年2月22日星期二4 考虑下列线性规划32142maxxxxZ0,) 3 (4) 2(315423321321321321xxxxxxxxxxxx）（求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。（1）改变右端常数为:2410b2022年2月22日星期二 （2）改变目标函数x3的系数为c3=1;（4）改变x2的系数为21222323312caaa（5）改变约束（1）为123245;xxx（6）增加新约束565321xxx2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis2022年2月22日星期二【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如210所示。表210Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/70 最优解X=（1，0，2，0，0，1）T ，最优值Z=102022年2月22日星期二1100747107371,1110110341BB最优基矩阵及其逆（1）基变量的解为276722241011007471073711bBXB基本解不可行，将求得的XB代替表210中的常数项，用对偶单纯形法求解，其结果见表211所示。2.