第二章对偶问题一般题答案

对偶问题一般习题答案●一般题目内容1：根据原规划，写出对偶规划1.1写出下面线性规划问题的对偶问题(a.)2341234123412341234max2343567358..12999200,0,0,zxxxxxxxxxxxxstxxxxxxxx无约束(b.)111111111max(1,)(1)..0(1,)1njjjnijjijnijjijjjzcxaxbimmmaxbmimstxjnnnxnjn无约束,当内容2：根据对偶问题，判定原问题有最优解、无解、有无穷大解2.1应用对偶理论,证明线性规划问题有最优解。12121212max32243214..301,2jzxxxxxxstxxxj提示：找到原问题和对偶问题的一个可行解，那么就能说明原问题有最优解。2.2应用对偶理论,证明线性规划问题是可行的，但无最优解。12313123max4..1401,2,3jzxxxxxstxxxxj提示：说明对偶问题无解，再根据原问题有可行解，就说明原问题为无穷解，所以没有最优解。2.3应用对偶理论,证明线性规划问题无解。12121212max5241..23101,2jzxxxxxxstxxxj提示：说明对偶问题有无穷解，就说明原问题无解。内容3：由原问题的最优解得到对偶问题的最优解3.1课本2.11题。（a）写出最优单纯形表c1c2c3c4c5Bc基b1x2x3x4x5xc33x01/211/20c11x1-1/20-1/61/3jjcz0-40-4-2写出初始单纯形表c1c2c3c4c5Bc基b1x2x3x4x5xc33x11a12a13a10c11x21a22a23a01jjczc1c2c300由最优单纯形表对于2x有2311/2*(1/2)*4ccc对于2x有43141/2*(1/6)*4(0)cccc对于5x有53150*(1/3)*2(0)cccc可得1c、2c和3c的值由于11/201/61/3B13112321aaBaa且1*BBI那么可求得11a、21a、13a和23a由于121221/2*1/2aBa那么可求得12a和22a3.2原规划为121212max332212416..51501,2jzxxxxxstxxj引入松弛变量后为121231425max332212416..51501,2,3,4,5jzxxxxxxxstxxxj对偶规划为1231213min121615243..25301,2,3jwyyyyystyyyj已知对偶规划的最优解为(3/2,0,0),试完成原规划的最优单纯形表(不用单纯形求解，并写出具体思路)。第一步：先给出原问题的初始单纯形表表1初始单纯型表jc33000Bc基b1x2x3x4x5x0X312221000X416400100X51505001jjcz33000第二步：根据对偶问题的最优解(3/2,0,0)，得到下图表2最优单纯形表33000Bc基b1x2x3x4x5x01/4023a5/411/234a0jjcz-3/200第三步：由于只能是5x、1x和2x为基变量，那么3x40x，立即可得14x，22x，55x，且可得下表表3最优单纯形表33000Bc基b1x2x3x4x5x01/400X5523a5/411/234a0jjcz00-3/200第四步：预指定1x为第一行的基变量，那么2x为第三行的基变量，有下表表4最优单纯形表33000Bc基b1x2x3x4x5x3X141001/400X550023a5/413X22011/234a0jjcz00-3/200检验1x是否为第一行的基变量。根据表3的第一行和14416xx，立即可验证1x确实是第一行的基变量。第五步：在表4中，对于4x有0=0-(3*1/4+0*5/4+3*34a)，因而可得表5最优单纯形表33000Bc基b1x2x3x4x5x3X141001/400X550023a5/413X22011/2-1/40jjcz00-3/200第六步：根据1*BBI，可得12301/405/411/21/40Ba202400015B表6最优单纯形表Bc基b1x2x3x4x5x3X141001/400X5500-5/25/413X22011/2-1/40jjcz00-3/200内容4：计算影子价格和隐含成本4.1课本(2.12)。（略）内容5：会使用对偶单纯形法5.1用对偶单纯形法解下列问题（a.）123412342341234min67355634125610..25801,2,3,4jzxxxxxxxxxxxstxxxxxj引入松弛变量转化为下式123412345234612347max67355634125610..25801,2,3,4,5,6,7jzxxxxxxxxxxxxxstxxxxxxj（b）123123123123min2242352373..46501,2,3jzxxxxxxxxxstxxxxj引入松弛变量转化为下式123123412351236max2242352373..46501,2,3jzxxxxxxxxxxxstxxxxxj令1236546xxxx代入上式得23623236234236235max2(546)242(546)352..3(546)7302,3,4,5,6jzxxxxxxxxxxxstxxxxxxxj即23623642365max585728..111131202,3,4,5,6jzxxxxxxxstxxxxxj（c）1231231312313min2332384..22624701,2,3jzxxxxxxxxstxxxxxxj（略）（d）122122123123min9745753484..268601,2,3jzxxxxxxxxxstxxxxj（略）内容6：能进行敏感性分析6.1课本2.9题（略）内容7：会解参数规划7.1课本2.10题中(a)和(d)（略）