运筹学期中测试参考答案

(0)1线性规划问题maxz?CX,AX?b,X?0,设X为问题的最

优解。若目标函数中用C*代替C后，问题的最优解变为X*，证明：

(0)(C*?C)(X*?X)?0

证明：因为X(0)为问题maxz?CX,AX?b,X?0的最优解，

同时X*为问题maxz?CX,AX?b,X?0的可行解。

(0)所以有： CX?CX*?0 （1）

同理可得：C*X(0)?C*X*?0 （2）

由不等式（1），（2）可知：

(C*?C)(X*?X(0))?0

2、已知线性规划：

maxz?3x1?2x2??x1?2x2?4?3x?2x?12?12? x?x?312??xj?0(j?1,2)?要求：（1）用单纯形法求解该线性规划问题的最优解和最优值；

（2）写出线性规划的对偶问题；

（3）根据对偶问题的性质求解对偶问题的最优解和最优值； 解：（1）化标准型：

maxZ?3x1?2x2??x1?2x2?x3?4?3x?2x?x?12?124? ?x1?x2?x5?3??xi?0,i?1,...,5根据标准型列单纯形表

Cj CB 0 0 0 -Z 0 0 3 -Z 0 2 3 -Z X3 X2 X1 X3 X4 X1 B X3 X4 X5 b 4 12 3 0 7 3 3 -9 32/5 3/5 18/5 -12 3 X1 -1 3 1 3 0 0 1 0 0 0 1 0 2 X2 2 2 -1 2 1 5 -1 5 0 1 0 0 0 X3 1 0 0 0 1 0 0 0 1 0 0 0 0 X4 0 1 0 0 0 1 0 0 -1/5 1/5 1/5 -1 0 X5 0 0 1 0 1 -3 1 -3 8/5 -3/5 2/5 0 所以，此线性规划有无穷多最优解 最优解之一 （18/5，3/5，32/5，0，0）

最优值 Zmax=12

（2）线性规划的对偶问题为：

minW?4y1?12y2?3y3??y1?3y2?y3?3??2y1?2y2?y3?2?y?0,i?1,...,3?i

（3）由原问题的最优单纯形表可知： 对偶问题的最优解为：（0，1，0） 最优值为：Wmin=12

3 下表给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解：

销地 产地 B1 2 10 7 4 B2 2 8 6 3 B3 2 5 6 4 B4 1 4 8 4 产量 3 6 6 A1 A2 A3 销量 解：利用Vogel法求解第一个运输方案： 3 2 10 1 7 4 5 2 8 3 6 3 4 2 2 5 2 6 4 3 1 4 4 8 4 3 3 6 6 1 1 0 3 0 3 2 1 4 利用对偶变量法求解检验数： 2 4 10 7 4 7 1 2 3 8 6 3 6 1 2 5 6 4 6 1 1 4 3 8 4 5 3 6 6 -5 -1 0 所有非基变量的检验数全部大于零，所以此运输方案是最优的运输方案。

最优值为：3*2+1*7+3*6+2*6+2*5+4*4=69

4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为

s1,s2,s3?s10，相应的钻井费用为c1,c2,?,c10，并且井

位选择上要满足下列限制条件：

①选择s1和s7就不能选择钻探s8；反过来也一样； ②选择了s3或s4就不能选s5，反过来也一样；

s,s,s,s5678中最多只能选两个； ③在

试建立这个问题的整数规划模型。（不求解） 解：设用xi表示第i个井位是否钻井探油，即

?1钻井xi??

0不钻井?