《运筹学》 第四章习题及 答案.pdf

《《运筹学》 第四章习题及 答案.pdf》由会员分享，可在线阅读，更多相关《《运筹学》 第四章习题及 答案.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学运筹学 第四章习题及第四章习题及 答案答案一、思考题1运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于 m，n,1？2 用左上角法确定运输问题的初始基本可行解的基本步骤是什么？ 3 最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4 沃格尔法（Vogel 法）的基本思想是什么？它和最小元素法相比给出的运输问题的初始基本可行解哪一个更接近于最优解？为什么？5 试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？6 用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？7 试述

2、用位势法求检验数的原理、步骤和方法。8 试给出运输问题的对偶问题（对产销平衡问题）。9 如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。10一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？11试述在表上作业法中出现退化解的涵义及处理退化解的方法。二、判断下列说法是否正确1运输问题模型是一种特殊的线性规划模型，所以运输问题也可以用单纯形方法求解。 2因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有唯一最优解；有无穷多个最优解；无界解；无可行解。 3在运输问题中，只要给出一组（,xijm，n,1）个非零的，且满足nmx,aiji

3、x,b,ijjj,1 i,1，就可以作为一个基本可行解。 4表上作业法实质上就是求解运输问题的单纯形法。5按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。6如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案将不会发生变化。7如果运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k ，最优调运方案将不会发生变化。8用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必须是正的。9用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。10当所有

4、产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。 三、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。 （1）用左上角法、最小元素法、沃格尔法求初始基本可行解； （2）由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要的迭代次数。销 地产 地 BBBB 产 量 12341 3 11 3 12 72 1 9 2 8 43 7 4 10 5 9销 量 3 6 5 6 20四、用表上作业法求下列产销平衡的运输问题的最优解：（表上数字为产地到销地的运价，M 为任意大的正数，表示不可能有运输通道）（1）销 地 甲 乙 丙 丁 产 量 产 地1 10 5 6

5、 7 252 8 2 7 6 253 9 3 4 8 50销 量 15 20 30 35 100 （2）销 地 甲 乙 丙 丁 产 量 产 地1 7 9 5 2 172 3 5 8 6 153 4 3 10 4 23销 量 10 15 20 10 45 （3）销地 甲 乙 丙 丁 戊 产量 产地1 2 5 4 5 3 302 3 4 1 7 5 203 2 1 9 8 7 204 5 4 3 6 8 30销量 10 15 25 20 30 100 （4）产地 甲 乙 丙 丁 戊 销 量 销地1 7 2 1 6 7 202 4 6 7 M 6 203 5 7 M 3 7 104 8 8 6 2

6、6 15产 量 10 15 12 10 18 65 （5）产地 甲 乙 丙 丁 戊 销 量 销地1 10 12 11 12 7 102 6 10 9 11 10 113 5 9 12 12 11 10产 量 5 6 5 7 8 31 (6)产地 甲 乙 丙 丁 戊 销 量 销地1 8 6 3 7 5 302 6 M 8 4 7 403 10 3 19 6 8 30产 量 25 25 20 10 20 31五、用表上作业法求下列产销不平衡的运输问题的最优解：（表上数字为产地到销地的里程，M 为任意大的正数，表示不可能有运输通道）。（1）产地 甲 乙 丙 丁 戊 销 量 销地1 10 16 23

7、17 22 1002 13 M 18 14 16 1203 0 3 19 16 M 1404 9 11 23 8 19 805 24 28 36 30 34 60产 量 100 120 100 60 80 31 （2）产地 甲 乙 丙 丁 戊 销 量 销地1 10 4 10 7 5 802 7 M 4 4 7 403 8 5 12 6 8 60产 量 50 40 30 60 20 （3）产地 甲 乙 丙 丁 戊 己 销 量 销地1 M 21 14 11 28 13 1002 3 6 11 3 12 M 1203 9 11 M 18 19 24 160产 量 90 70 80 50 70 60

8、（4）产地 甲 乙 丙 丁 戊 销 量 销地1 7 3 9 4 11 302 4 2 5 6 10 243 6 8 12 2 5 36产 量 12 18 21 14 15六、某农民承包了 5 块土地共 206 亩，打算小麦、玉米和蔬菜三种农作物，各种农作物的计划播种面积（亩）以及每块土地种植各种不同的农作物的亩产数量（公斤）见下表，试问怎样安排种植计划可使总产量达到最高？土地块别 计划播甲 乙 丙 丁 戊 作物种类 种面积1 500 600 650 1050 800 862 850 800 700 900 950 703 1000 950 850 550 700 50土地亩数 36 48 44

9、 32 46二、（1）? （2）X （3）X （4）?(5) ?（6）?（）X（8）X（9）X（10）?三、解：（1）西北角法：运费为 Z = 135 。销 地 产 量 BBBB1234 产 地1 3 4 72 2 2 43 3 6 9销 量 3 6 5 6 20 （2）最小元素法：运费为 Z = 92销 地B 产 量 BBB 产 地 12341 4 3 72 3 1 43 6 3 9销 量 3 6 5 6 20 （3）沃格尔法：运费 Z = 85销 地BBBB 产量 产 地 12341 2 5 72 1 3 43 6 3 9销 量 3 6 5 6 20 （4）最优调运方案：最少运费 Z =

10、85销 地BBBB 产 量 产 地 12341 2 5 72 1 3 43 6 3 9销 量 3 6 5 6 20 四、各题的最优调运方案如下：（1） 最少运费为： 535 。销 地 甲 乙 丙 丁 产 量 产 地1 25 252 15 10 253 15 5 30 50销 量 15 20 30 35 100（2）最少运费为：226销 地 甲 乙 丙 丁 产 量 产 地1 15 2 172 10 5 153 15 8 23销 量 10 15 20 10 45 （3）最少运费为：295销地 甲 乙 丙 丁 戊 产量 产地1 30 302 5 15 203 5 15 204 10 20 0 30销

11、量 10 15 25 20 30 100（4）最少运费为：248产地 甲 乙 丙 丁 戊 销 量 销地1 8 12 202 10 10 203 7 3 104 10 5 15产 量 10 15 12 10 18（5）最少运费为：260产地 甲 乙 丙 丁 戊 销 量 销地1 2 8 102 1 5 5 113 5 5 10产 量 5 6 5 7 8 31(6) 最少运费为：450产地 甲 乙 丙 丁 戊 销 量 销地1 20 10 302 25 10 5 403 0 25 5 30产 量 25 25 20 10 20 31五、解：各题的最优调运方案如下：（1）最短运程为：5240产地 甲 乙

12、丙 丁 戊 己 销 量 销地1 60 40 1002 40 80 1203 40 100 1404 20 60 805 20 40 60 产 量 100 120 100 60 80 31（2）最短运程为：980产地 甲 乙 丙 丁 戊 销 量 销地1 40 20 20 802 30 10 403 30 30 604 20 产 量 50 40 30 60 20（3）最短运程为：3870产地 甲 乙 丙 丁 戊 己 销 量 销地1 40 60 1002 40 50 30 1203 90 70 1604 40 产 量 90 70 80 50 70 60（4）最短运程为：330产地 甲 乙 丙 丁 戊 己 销 量 销地1 2 18 10 302 3 21 243 7 14 15 36 产 量 12 18 21 14 15六、解：最优种植计划为：最高总产量为 180900 公斤。土地块别 计划播甲 乙 丙 丁 戊 作物种类 种面积1 44 32 10 862 34 36 703 36 14 50土地亩数 36 48 44 32 46