对偶问题一般题答案

1、对偶问题一般习题答案 一般题目内容1:根据原规划，写出对偶规划1.1写出下面线性规划问题的对偶问题max z =x +2x2 - 3x3 - 4 x4x1 +x2 x3 3 x4 =5(a.)6x1 +7 x2 +3x3 -5x4 >8s.t.1 2 x1 -9x2 - 9x3 9x4 <201x1 >0,x2 >0, x3 M0,x4无约束(b.)n“ a x _ b. ij jijns.t.«E aj xj = bij三xj之0x j无约束，当xj(1 _ i _ m1, m1 _ m)(m1 - 1 _ i _ m)(1 三 j £5, n /

2、 n)n11 _ j _ n内容2:根据对偶问题，判定原问题有最优解、无解、有无穷大解2.1 应用对偶理论，证明线性规划问题有最优解。max z = 3 x12 x2"-x1 +2x2 < 43x1 +2x2 <14 s.t.| x1- x2 3x j 0 j = 1, 2提示：找到原问题和对偶问题的一个可行解，那么就能说明原问题有最优解。2.2 应用对偶理论，证明线性规划问题是可行的，但无最优解。max z = x1 - x2 x3x1 - x3 > 4s.t. x1 - x2 x3 - 1 4xj 之 0 j =1, 2,3提示：说明对偶问题无解，再根据原问题有

3、可行解，就说明原问题为无穷解，所以没有最优解。2.3应用对偶理论，证明线性规划问题无解。max z = x1 +5 x2x1 -2 x2 > 4 12x1 +x2 <1s.t.2 x1 -3x2 <1xj 之 0j =1, 2提示：说明对偶问题有无穷解，就说明原问题无解。内容3:由原问题的最优解得到对偶问题的最优解3.1 课本2.11题。(a)写出最优单纯形表c1c2c3c4c5cb基bx1x2x3x4x5c3x301/211/20c1x11-1/20-1/61/3c z jj0-40-4-2写出初始单纯形表c1c2c3c4c5cB基bx1x2x3x4x5c3x 3ana12

4、a1310c1x1a 21a22a 2301cj _Zjc1c2c300由最优单纯形表对于 x2 有 c2 - H / 2 * c3 +(-1 / 2) * 5 =-4对于 x2 有 c4 -11 / 2 * c3 - ( -1 / 6) * c1 I - -4(c4 = 0)对于 x5 有 c5 - 10 * c3 - (1 / 3) * c1 I - -2(c5 =0)可得c1、c2和c3的值由于Bal 1a2 1 ;1 1/20B - =1/61 / 3 ,且 B * B 1 = I那么可求得a11 > a 2143和23由于1'a12 ) f 1 / 2 )B =<

5、a22)L/2/那么可求得a.和a?3.2原规划为m ax z = 3x1 ; 3x22 x1 + 2 x2 + x3 =124 x. + x. =16 1 4s.t.5 x2 + x5 =15xj >0 j =1, 2,3, 4,5m ax z = 3x1 3x22x1 +2 x2 <1 24x1 16引入松弛变量后为S.t. «5x2 <1 5xj >0 j =1,2对偶规划为m in w =12yl -16y21 5 y32 y1 +4 y2 之3s.t. 2 y15 y3 _ 3I 、V j -0 j =1,2,3已知对偶规划的最优解为(3/2, 0,

6、 0),试完成原规划的最优单纯形表(不用单纯形求解，并写出具体思路)。第一步：先给出原问题的初始单纯形表表1初始单纯型表Cj33000CB基bx1x2x3x4x50X312221000X416400100X51505001ci -zi33000第二步：根据对偶问题的最优解(3/2, 0, 0),得到下图表2最优单纯形表33000cB基bxix 2x3x4*501/403 235/411/23 340c j Z j-3/200第三步：由于只能是 x5、x1和x2为基变量，那么x3 =x4 =0 ,立即可得x1 =4 , x2 =2 , x5 =5 ,且可得下表表3最优单纯形表33000cB基bx

7、1x2x3x4x501/400X553 235/411/23 340c z jj00-3/200第四步：预指定xi为第一行的基变量，那么 x2为第三行的基变量，有下表表4最优单纯形表33000cB基bx1x2x3x4x53X141001/400X55003 235/413X22011/23 340cj "00-3/200检3/x1是否为第一行的基变量。根据表 3的第一行和4xi+x4 =16 ,立即可验证x1确实 是第一行的基变量。第五步：在表4中，对于x4有0=0-( 3*1/4+0*5/4+ 3* 334),因而可得表5最优单纯形表33000cB基bx1x 2x3x4*53X14

8、1001/400X5500a 235/413X22011/2-1/40c j 一 zj00-3/20001 / 401B 一 二a235 / 41L1 / 2-1 / 40产20B第六步：根据B * B1=1 ,可得cB基bXiX 2X3X4X53X141010X5500*JL3X2201zM_-1/4c j j00-3/200,0151 J表6最优单纯形表内容4:计算影子价格和隐含成本4.1 课本(2.12)。(略)内容5:会使用对偶单纯形法5.1 用对偶单纯形法解下列问题m in z =6x17x2 3x3 5 x45x1 +6x2 -3x3 +4x4 >1 2(a.)x2 +5x3

9、 -6x4 >10s.t2x1 +5x2 +x3 +x4 8 8 xj _0 j =1,2,3, 4引入松弛变量转化为下式m ax z - -6 x1 - 7 x2 - 3 x3 - 5x4”5x1 6 x2 +3x3 4 x4 + x5 =12-x2 - 5x3 76 x4 +x6 - -1 0一2 x1 .5x2 .x3 .x4x7 = -8 xj _0 j =1,2,3, 4,5,6,7m in z = _2 x1 2 x2 .4 x32 x1 + 3 x) + 5 x, > 2 I23(b)3x1 +x2 +7x3 <3S.t .4x1 +4 x? +6 x, <

10、;5123 xj 之0 j =1,2,3引入松弛变量转化为下式m ax z = 2 x12 x24 x3广-2x1 3x2 5x3 +x4 =-23x1 + x2 + 7 x3 + x5 =3 s.tx1 +4x2 +6x3 +x6=5xj 之 0 j =1, 2,3令x1 =5 -4x2 -6x3 一x6代入上式得m ax z = 2 (5 4x, - 6x, - xR ) 2 x, 4 x, 236232(5 _ 4 x2 _ 6 x3 _ x6) 3x? _ 5x3,x4 = - 2s.t. 3(5 - 4 x2 - 6 x3 -x6) »x2，7 x3，x5 =3 xj >0 j =2,3, 4,5, 6即m ax z = -5x2 -8x35x, + 7x, +2x6 + x4 =8 2364s.t .4-1 1 x, -1 1 xq 3 xK + x< =-12 2365xj 之 0 j =2,3,4,5, 6m in z - -2 x1 - 3 x2 x3-3x1 -2x2 3x3 - -8(c)x1 +x3 < 4s.t