最全运筹学习题及答案(8)

第 31 页 共 64 页

x1+4x2 ?420 x1，x2，x3?0

（2）Max z(t)=(7+2t)x1+(12+t) x2+(10-t)x3 (t?0) s.t.

x1+x2+x3 ?20

2x1+2x2+ x3 ?30

x1，x2，x3?0

（3）Max z(t)=2x1+x2 (0 ?t ?25) s.t.

x1 ?10+2t x1 +x2 ?25-t x2 ?10+2t x1，x2?0 （4）Max z(t)=21x1+12x2+18x3+15x4 (0 ?t ?59) s.t.

6x1+3x2+6x3+3x4 ?30+t 6x1-3x2+12x3+6x4 ?78-t 9x1+3x2-6x3+9x4 ?135-2t x1，x2，x3，x4?0

解：

（1）化成标准形式：

Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3+0x4+0x5+0x6 (t?0) s.t.

x1+2x2+x3+x4=430

3x1+2x3+x5=460

第 32 页 共 64 页

x1+4x2+x6=420

x1，x2，x3，x4，x5, x6?0

令t=0，用单纯形表计算， 3-6t 2-2t c j5-5t x3 0 x4 0 x5 0 x6 ?i CB XB x2 x3 x6 B 100 230 20 x1 x2 2-2t 5-5t 0 -z -1/4 3/2 2 1 0 0 0 0 1 0 0 0.5 0 -2 t-1 -1/4 1/2 [1] 2t-2 0 0 1 0 - 460 20 1350t t-4 -1350 t增大，t大于1，首先出现?4，?5大于0，所以当0?t?1时有最优解。 X=（0，100，230，0，0，20)T 目标函数最优值为1350（t-1） （0?t?1）。 t=1是第一临界点。 t大于1时，x6是换出变量。 t大于1，最优解是：X=（0，0， 0，430，460，420)T 目标函数最优值为 Max z(t)=0， （t大于1） （2） 化成标准型，然后令t=0，单纯形法解得： t开始增大时，当t大于8/3时，首先出现优解。

目标函数最优值Max z(t)=220，（0?t?8/3） 所以，t=8/3为第一临界点。 当8/3

?4大于0，所以0?t?8/3，得最?4为换入变量，由?规则，x3为换出变量，使用单纯形法

继续迭代，t继续增大，当t>5，首先?1大于0，8/3

第 33 页 共 64 页

X=（0，15，0，5)T

目标函数最优值为180+15t ，（8/3

当t>5时，x1是换入变量，x2为换出变量，单纯性法计算， 当t继续增大，所有检验数都非正，所以当t>5，最优解： X=（15，0，0，5)T

目标函数最优值为105+30t， t〉0

(3)化成标准型，令t=0,用单纯形法计算得：

当t开始增大，t大于5时，首先出现b2小于0，当0?t?5，最优解为： X=（10+2t，0，10+2t，5-t，0)T 目标函数最优值为6t+30 ，（0?t?5）。 所以t=5是第一临界点。

当t大于5时，x4是换出变量，x5是换入变量。用对偶单纯形法计算， 当t大于5时，最优解为： X=（10+2t，15+t，0，0，t-5)T

目标函数最优值为35+5t。 （4）解： 先化为标准型，令t=0，用单纯形法计算，得：

当t开始增大，当t大于6时，首先出现b2小于0，当0?t?6，有最优解： X=（0，0，0，10+t/3，0，18-3t，45-5t)T 目标函数最优值为150+5t （0?t?6）。

当t大于6时，首先出现b2小于0，x6是换出变量，x2是换入变量，使用单纯形法计算得：t继续增大，当t大于11时，b3首先小于零，x7是换出变量，x3为换入变量，对偶单纯形法迭代得： 当 t≤59，有最优解：

X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0)T

目标函数最优值为5t/2+345/2 ，（11

1. （2006年西北工业大学）已知线性规划：

maxz?3x1?2x2

第 34 页 共 64 页

??x1?2x2?4?3x?2x?12?2 s..t?1?x1?x2?3??x1,x2?0（1） 用单纯形法求解该线性规划问题的最优解和最优值；

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

（3） 求解对偶问题的最优解和最优值。

解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。

?18解题过程：X*???53532?00? 5?Tmaxz?12，有无穷多解。 对偶问题为： minw?4y1?12y2?3y3 ??y1?3y2?y3?3?s..t?2y1?2y2?y3?2 ?y,y,y?0123?Y*??010? w*?z*?12 2. （2005年东南大学）写出如下线性规划问题的对偶问题： maxz?x1?2x2?x3 ?x1?x2?x3?2?x?x?x?1? s..t?1232x?x?x?2?123?x3 无限制?x1?0,x2?0,并利用弱对偶性说明z的最大值不大于1。 解题过程：原问题的对偶问题为： minw?2y1?y2?2y3 ?y1?y2?2y3?1?y?y?y?2?3 s..t?12??y1?y2?y3?1??y1?0,y3?0,y2由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解

X都有 CX?Y b第 35 页 共 64 页

?2???1，所以z的最大值不大于1。 1而Yb??010??????2??

第三章（86页）

3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为什么？

表3—1 销地1 产量 2 3 4 产地 1 2 3 销量 表3—2 销1 地 产地 1 2 3 4 5 销量 0 5 5 2 15 15 3 15 15 4 10 10 5 15 25 5 产量 150 90 240 200 210 410 300 250 550 250 80 330 50 20 70 400 500 300 300 100 解： 表3—1中，有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格，所以表3-1的调运方案不能作为用表上作业法求解时的初始解。 表3-2中，有10个数字格，而作为初始解，应该有m+n-1=9个数字格，所以表3-2的调运方案不能作为表上作业法的初始解。 3.2 表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。

表3-3 销地 1 产量 2 3 产地 1 5 1 8 12 2 2 4 1 14 3 3 6 7 4 销量 9 10 11