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

本文格式为Word版，下载可任意编辑——《运筹学》第四章习题及答案《运筹学》第四章习题

一、思考题

1．运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最

多等于m?n?1？

2．用左上角法确定运输问题的初始基本可行解的基本步骤是什么？

3．最小元素法的基本思想是什么？为什么在一般状况下不可能用它直接得到运输问题的最优方案？

4．沃格尔法（Vogel法）的基本思想是什么？它和最小元素法相比给出的运输问题的

初始基本可行解哪一个更接近于最优解？为什么？

5．试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什

么？

6．用闭回路法检验给定的调运方案时，如何从任意空格出发去寻觅一条闭回路？这闭

回路是否是唯一的？

7．试述用位势法求检验数的原理、步骤和方法。8．试给出运输问题的对偶问题（对产销平衡问题）。

9．如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输

问题。

10．一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？11．试述在表上作业法中出现退化解的涵义及处理退化解的方法。二、判断以下说法是否正确

1．运输问题模型是一种特别的线性规划模型，所以运输问题也可以用单纯形方法求解。2．由于运输问题是一种特别的线性规划模型，因而求其解也可能出现以下四种状况：有唯一最优解；有无穷多个最优解；无界解；无可行解。

3．在运输问题中，只要给出一组（m?n?1）个非零的

?xij?，且满足

j?1，i?1，就可以作为一个基本可行解。4．表上作业法实质上就是求解运输问题的单纯形法。

5．按最小元素法或元素差额法给出的初始基本可行解，从每一空格出发都可以找到一闭回路，且此闭回路是唯一的。

6．假使运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。

7．假使运输问题单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化。

8．用位势法计算检验数时，先从某一行（或列）开始，给出第一个位势的值，这个先给出的位势值必需是正的。

9．用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验数是唯一的。

10．当所有产地的产量和销地的销量都是整数时，运输问题的最优解也是整数。三、求解以下产销平衡的运输问题，下表中列出的为产地到销地之间的运价。

（1）用左上角法、最小元素法、沃格尔法求初始基本可行解；

（2）由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要

的迭代次数。销地B1B2B3B4产量产地123317119432101285749?xij?ai?xij?bjnm销量365620四、用表上作业法求以下产销平衡的运输问题的最优解：（表上数字为产地到销地的运价，M为任意大的正数，表示不可能有运输通道）（1）销地甲乙丙丁产量产地123销量108915523206743076835252550100（2）销地甲产地123销量（3）销地产地1234销量（4）产地销地1234产量（5）产地销地12373410乙95315丙581020丁26410产量17152345甲232510乙541415丙419325丁578620戊357830产量30202030100甲745810乙267815丙17M612丁6M3210戊767618销量2020101565甲1065乙12109丙11912丁121112戊71011销量101110产量(6)产地销地1235657831甲8610乙6M3丙3819丁746戊578销量304030252520102031产量五、用表上作业法求以下产销不平衡的运输问题的最优解：（表上数字为产地到销地的里程，M为任意大的正数，表示不可能有运输通道）。（1）产地甲乙丙丁戊销量销地12345产量（2）产地销地123产量（3）产地销地123产量（4）产地销地1231013092410016M311281202318192336100171416830602216M193480100120140806031甲107850乙4M540丙1041230丁74660戊57820销量804060甲M3990乙2161170丙1411M80丁1131850戊28121970己13M2460销量100120160甲746乙328丙9512丁462戊11105销量3024361218211415产量六、某农民承包了5块土地共206亩，计划小麦、玉米和蔬菜三种农作物，各种农作物的计

划播种面积（亩）以及每块土地种植各种不同的农作物的亩产数量（公斤）见下表，试问怎样安排种植计划可使总产量达到最高？

土地块别作物种类123土地亩数

甲500850100036乙60080095048丙65070085044丁戊计划播种面积86705010508009009505507003246《运筹学》第四章习题解答

二、（1）√（2）X（3）X（4）√(5)√（6）√（７）X（8）X（9）X（10）√

三、解：（1）西北角法：运费为Z=135。

销地B1B2B3B4产量产地123342235667492036销量（2）最小元素法：运费为Z=92

销地B1B2产地123366B3415B4336产量749203销量（3）沃格尔法：运费Z=85

销地B1产地12321B26B35B4336产量74920365销量（4）最优调运方案：最少运费Z=85销地B1B2B3产地1232165B4336产量74920365销量四、各题的最优调运方案如下：（1）最少运费为：535。销地甲乙产地丙丁产量123销量1515155203030251035252550100（2）最少运费为：226销地甲产地123销量（3）最少运费为：295销地甲产地1234551010乙1515丙15520丁2810产量17152345乙15丙151025丁2020戊30030产量302020301001015销量（4）最少运费为：248产地甲乙销地1234108715丙1212丁1010戊103518销量2020101510产量（5）最少运费为：260产地甲销地1235乙156丙55丁257戊88销量101110315产量(6)最少运费为：450产地甲销地123250乙25丙2020丁1010戊105520销量304030312525产量五、解：各题的最优调运方案如下：（1）最短运程为：5240

产地销地12345甲6040乙10020丙404020100丁6060戊80己4080销量100120140806031100120产量（2）最短运程为：980产地甲乙销地1234302040丙3030丁20103060戊2020销量8040605040产量（3）最短运程为：3870产地甲乙销地1234907070丙404080丁5050戊304070己6060销量10012016090产量（4）最短运程为：330产地甲销