x4x1 0 1 0 0 0 1 1 12?321 0 0 -1 1 ?12-2 0 10 15 5 x212
它对应的基本可行解为：x??1550?，目标函数值为z0??35，此时检验数
T向量?为负数，故为最优解。
?minz?x1?x2?x3?x5?x6?s.t.3x?x?x?6356??x2?2x3?x4?10???x1?x6?0（3）、? ?x3?x6?x7?6?xj?0,j?1,?,7??
?0?0解：由此可以得到矩阵A????1??0
则可以得出B??A10310?12?1000?? 000010??010011?T01A2A5A7?是一个单位矩阵，且b??61006?＞0，所
以基B是可行基，x1,x2,x5,x7为基变量，x3,x4,x6为非基变量。基B对应的基本
T可行解为：x??01000606?，其目标函数值z0?0。
由此写出最初的单纯形表：
x x x
-1 1 -1 x 0 0 3 x 0 1 2 x -1 0 0 0 x0 1
123x4
x5
x6
x7
RHS
12570 0 -1 0 0 -1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 6 10 0 6
由题可知，N??A3A4TA6?，cB??1?110?cT10?1? N??T?1T检验数可由?k?cBBN?cN可得：?4?1不是负数，则当前解不是最优解，
故x2为进基变量，x5为出基变量。 进行旋转变换后得下表：
x x
0 3 x 0 4 x 1 -1 x0 2*
1241x3
x4
x5
x6
RHS
6-5 -5 2 -3 T0 1 0 0 -2 -3 1 -1 0 0 0 1 -20 30 10 10 它对应的基本可行解为:x??301010?,其目标函数值为z0??20。但?2?3为正数，仍不是最优解，此时以a32为转轴元，x2为进基变量，x6为出基变量，进行旋转变化得下表：
x x
12x3
12x4
x5
12x6
32RHS
x4x10 0 1 0 0 0 0 1 ?0 1 0 0 ? ?-35 10 15 5 1 123?2-1 1 1?2-2 0 x212
它对应的基本可行解为：x??1550?，目标函数值为z0??35，此时检验数
T向量?为负数，故为最优解。
18、写出下面线性规划的对偶规划
?min?s.t.?????????10x1?10x25x1?2x2?5x1?4x2?3x1?3x2?28x1?2x2?4x1,x2为自变量2?4??， 3??2?
?5?1TT解：由题可得c??1010?，b??5324?，A???1??8有定义可得原问题的线性规划问题的对偶规划为：
??w1?????max?5324??w2??w???3???w??4????s.t.??w1?????5118???w2??10????2432???w????10?? ????3????w???4??按分量形式写出的对偶规划为：
?max??s.t.??????
5w1?3w2?2w3?4w45w1?w2?w3?8w4?102w1?4w2?3w3?2w4?10wj?0,j?1,2,3,4
x3?minx1??s.t.x?2x?512??120、把线性规划问题：?x2?x3?3记为P， ?2??x1,x2,x3?0?（1） 用单纯形算法解P；
（2） 写出P的对偶D；
（3） 写出P的互补松紧条件，并利用他们解对偶D。 解：（1）、由题将P化为标准形式为：
x3?minx1??s.t.x?2x?x4?512?? ?1x2?x3?3?2??x1,x2,x3,x4?0??1201???由此可写出A，即为：A?? 1?10??02??则可以得出B??A1A3?是一个单位矩阵，且b??53?＞0，所以基B是可行基，
TTx1,x3为基变量，x2,x4为非基变量。基B对应的基本可行解为：x??5030?，
其目标函数值z0?0。得到一张单纯形表如下：
x1
x2
x3
x4
RHS
-1 x 1 x 0 130 2 12-1 0 1 x30 1 0 x40 5 3 RHS将第0行化成检验行为： x x
5 0 212
0 0 1 1 1 0 8 5 3 x1 1 x 0 32* 125为正数，仍不是最优解，以x2为进基变量，x1为出基变量，进行2旋转变化得下表：
x x x x RHS
517?? 0 0 444它对应的?2?1234x2
12 1 0 0 1 12 5274 x3 0 1?4
1?它对应的?4??，所以问题P的最优解为x*??04?527?7?，最优值为： 4?4T（2）、由题可得：
x3?minx1??s.t.?x?2x??512?? ?1x?x?323?2??x1,x2,x3?0?所以可得对偶规划：
?max?5w1?3w2?s.t.?w?11??1?2w1?w2?0?2?w2?1??w1?0 ?5?（3）、由题问题P的最优解为x??02?*7??以及互补松紧性定律可得： 4?T1??2w?w2?0?1 2??w2?1?由此解得：
w1?1,w2?1 4T7?1?由此对偶问题的最优解为：w*??1?，最优值为：?5w1?3w2?
4?4?22、用对偶单纯形法求解
?min2x1?3x2?4x3?s.t.x?2x?x?3?123?2x1?x2?3x3?4?x1,x2,x3?0（1）、? ?解：由题将原问题写成标准形式：
?min2x1?3x2?4x3?s.t.x?2x?x?x?3?1234 ?2x1?x2?3x3?x5?4??x1,x2,x3,x4,x5?0?