《对偶问题一般题答案》由会员分享，可在线阅读，更多相关《对偶问题一般题答案（8页珍藏版）》请在金锄头文库上搜索。
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 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 / n)n11 _ j _ n内容2:根据对偶问题，判定原问题有最优解
2、、无解、有无穷大解2.1 应用对偶理论，证明线性规划问题有最优解。max z = 3 x12 x2-x1 +2x2 43x1 +2x2 4s.t. x1 - x2 x3 - 1 4xj 之 0 j =1, 2,3提示：说明对偶问题无解，再根据原问题有可行解，就说明原问题为无穷解，所以没有最优解。2.3应用对偶理论，证明线性规划问题无解。max z = x1 +5 x2x1 -2 x2 4 12x1 +x2 1s.t.2 x1 -3x2 a 2143和23由于1a12 ) f 1 / 2 )B =0 j =1, 2,3, 4,5m ax z = 3x1 3x22x1 +2 x2 1 24x1 1
3、6引入松弛变量后为S.t. 5x2 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, 0),试完成原规划的最优单纯形表(不用单纯形求解，并写出具体思路)。第一步：先给出原问题的初始单纯形表表1初始单纯型表Cj33000CB基bx1x2x3x4x50X312221000X416400100X51505001ci -zi33000第二步：根据对偶问题的最优解(3/2, 0, 0),得到下图表2最优单纯形表33000cB基bxix 2x3x4
4、*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基bx1x2x3x4x501/400X553 235/411/23 340c z jj00-3/200第四步：预指定xi为第一行的基变量，那么 x2为第三行的基变量，有下表表4最优单纯形表33000cB基bx1x2x3x4x53X141001/400X55003 235/413X22011/23 340cj 00-3/200检3/x1是否为第一行的基变量。根据
5、表 3的第一行和4xi+x4 =16 ,立即可验证x1确实 是第一行的基变量。第五步：在表4中，对于x4有0=0-( 3*1/4+0*5/4+ 3* 334),因而可得表5最优单纯形表33000cB基bx1x 2x3x4*53X141001/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:
6、计算影子价格和隐含成本4.1 课本(2.12)。(略)内容5:会使用对偶单纯形法5.1 用对偶单纯形法解下列问题m in z =6x17x2 3x3 5 x45x1 +6x2 -3x3 +4x4 1 2(a.)x2 +5x3 -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
7、, 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, 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. 2 x1 x2 -2 x3 - 6(略)2x1 +4x3 75x1 + x2 +7x2 5(略)(d)3x1 +4x2 +8x3 =4s.t.2x1 +6x2 +8x3 之 6xj 至0 j =1,2,3内容6:能进行敏感性分析6.1 课本2.9题（略）内容7:会解参数规划7.1 课本2.10题中和（d）（略）
