第三章运输问题习题

题

一、疑问：

运输问题中，若出现退化情形，应该在什么地方补0？ 答：为了使产销平衡表上有(m + n - 1)个数字格，这时需要添加“0”，它的位置可以对应同时划去的那行或那列的任一空格处。（这时填数字格不构成闭回路） 二、判断下列说法是否正确 ：

(a) 运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列情况之一：有唯一最优解、有无穷多最优解、无界解和无可行解；

(b) 在运输问题中，只要给出一组含（m + n –1）个非负

的{xij}，且满足

xj1nijai，xmi1ijbj，就可以作为

一个初始基可行解；

(c) 表上作业法实质上就是求解运输问题的单纯形法； (d) 按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路； (e) 如果运输问题的单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化； (f) 如果运输问题的单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化； 三、选择：

1．在产销平衡运输问题中，设产地为m个，销地为n个，

那么解中非零变量的个数（ ）。 A．不能大于(m+n-1)；B．不能小于(m+n-1)；C．等于(m+n-1)；D．不确定。

2．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ ）。

A．无最优解；B．有无穷多个最优解；C．有唯一最优解；D．出现退化解。 四、判断表(a),(b),(c)中给出的调运方案能否作为作业法求解时的初始解，为什么？ 表 (a)

销地 产地 1 A1 A2 A3 A4 销量

B B2 B3 B4 B5 B6 产量 20 10 30 20 10 10 50 5 20 30 50 75 20 20 40 30 10 50 25 表 (b) 销地 产地 1 BB2 B3 4 B B5 B6 产量 A1 A2 A3 A4 销量 0 表(c) 销地 产地 A1 5 A2 A3 15 A4 销量 解：

20 B1 0 2 30 10 30 10 30 20 25 30 50 75 20 240 30 10 50 25 B2 B3 B4 B5 产量

20 18 12 5 20 20 20 25 30 40 20 38 17 20 (a) 可以作为初始方案。

(b) 中非零元素小于9（产地+销地-1），不能作为初始方案。 (c) 中存在以非零元素为顶点的闭回路，不能作为初始方案。

五、已知某运输问题的产销平衡表，单位运价表及给出的一个调运方案分别见下表。判断所给出的调运方案是否为最优？如是，说明理由，如否，也说明理由。

产销平衡表及某一调运方案

销地 产地 B B2 B3 B4 B5 B6 产量 1 A1 A2 A3 A4 销量 5 225 20 5 5 240 10 20 24 16 10 5 15 11 50 40 60 31 20 20 71

单位运价表

销地 产地 B1 B2 B3 B4 B5 B6

解：题目中

A1 2 1 3 3 2 5 给出的调运A2 3 2 2 4 3 4 方案有11个A3 3 5 4 2 4 1 非零元素，不A4 4 2 2 1 2 2 是基可行解，应先调整得到基可行解，然后求检验数，判别是否最优。

六、已知某运输公司问题的产销平衡表与单位运价表如下所示

销地 产地 I II III 销量 25 A B 10 20 15 40 C 20 D 20 E 40 30 150 30 70 产量 50 100 150

15 30 40 25 30 35 115 60 （a）求最优调拨方案； 解：（a）最优调拨方案如下表：

销地 产地 I II III A B 15 10 80 35 60 C 30 D 70 销量 25 115 60 30 70 E 产量 50 100 150

（b）如产地III的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案。

(b)根据题设条件重新列出这个问题的产销平衡表与单位运价表

销地 产地 I II III Ⅳ（假想） 销量 A B 10 20 15 40 C 20 D 20 E 40 30 25 0 70 产量 50 100 130 20 15 30 40 0 55 0 30 30 35 0 25 M 115 60

重新求出最优调拨方案如下表：

销地 产地 I II III Ⅳ（假想） 销量 25 115 60 30 70 A B 25 65 50 60 C 15 15 D E 65 5 产量 50 100 130 20 七、表1和表2分别是一个具有无穷多最优解的运输问题的产销平衡表、单位运价表。表1给出了一个最优解，要求再找出两个不同的最优解。

表1

销地 产地 BB2 1 B3 B4 产量 表2

A1 A2 A3 A4 销量 4 2 14 24 4 7 5 30 18 24 6 12 6 14 35 销地 产地 B B2 B3 B4

1 A1 A2 A3 A4 9 10 8 10 8 10 9 7 13 12 14 14 11 13 11 12 解：因（A4，B2）格检验

数为0，从该空格寻找闭回路调整可以得到最优解，将两个不同最优解对应数字相加除以2，变得到第三个最优解。 八、如表所示的问题中，若产地i有一个单位物资未运出，则将发生储存费用。假定1，2，3产地单位物资储存费用分别为5，4，3。又假定产地2的物资至少运出38个单位，产地3的物资至少运出27个单位，试求解此运输问题的最优解。

销地 产地 1 2 3 销量 A 1 1 2 30 B 2 4 3 20 C 2 5 3 20 产量 20 40 30 70 90

解：增加假想销

地D，销量为20，将产地分为1，2，2’,3,3’,其中2’于3’的物资必须全部运出，不准分给D，由此可以得到小表，再用表上作业最优方案。

销地 产地 1 2 2/ 3 3/ 销量 A 1 1 1 2 2 30 B 2 4 4 3 3 20 C 2 5 5 3 3 20 D 5 4 M 3 M 20 产量 20 2 38 3 27 90

九、甲、乙、丙三各城市，每年分别需要煤炭320，250，350（万t），由A，B两个煤矿负责供应。已知煤矿煤产量A为400万t，B为450万t，从两煤矿至各城市煤炭运价如表3－23所示。由于需求大于产量，经协商平衡，甲城市必

要时可少供0－30万t，乙城市需求量需全部满足，丙城市需求量不少于270万t。试求将甲、乙两煤矿全部分配出去，满足上述条件又使总运费为最低的调运方案。

A B

甲 15 21 乙 18 25 丙 22 16 十、某化学公司有甲，乙，丙，丁四个化工厂生产某种产品，产量分别为200，300，400，100（t），供应I,II,III,IV,V,VI六个地区的需要，需要量分别为200，150，400，100，150，150（t）。由于工艺，技术等条件的差别，各厂每kg的产品成本分别为1.2,1.4,1.1,1.5(元)，又由于行情的不同，各地区的销售价分别为每kg2.0,1.8,2.2,1.6,2.0(元)。已知从各厂运往各销售地区每kg产品价格如下表所示。

销地 产地 甲 乙 丙 丁 IV 0.5 0.3 0.7 0.4 0.3 0.8 0.9 0.4 0.5 0.3 0.1 0.6 0.2 0.4 0.5 0.4 0.8 V VI I II III 0.7 0.3 0.7 0.6 0.4 0.2 0.6 如果第III个地区至少供应100t，第IV个地区的需要必须全部满足，试确定使该公司获利最大的产品调运方案。 解：先列出这个问题的产销平衡表和单位运价表，再用表上

作业法可以求得最优解： 销 地 I II III III’ IV 产地 甲-0.3 -0.8 0.3 -0.3 -0.6 乙-0.3 -0.2 0.5 0. 5 -0.3 丙-0.2 -0.6 0.4 –0.4 -0.4 丁0. 1 -0.5 0. 1 –0.1 -0.1 戊0 0 0 M M 销200 150 300 100 100 量

产V VI 量 -0.1 -0.7 0. 4 -0.4 -0.1 -0.5 0. 4 0. 3 0 0 150 150 200 300 400 100 150 销 地 I 产地 甲 乙 200 丙 丁 戊 销200 量 II III III’ IV 产V VI 量 50 100 300 100 100 0 0 150 300 100 100 150 0 150 150 150 200 300 400 100 150 十一、某糖厂每月最多生产糖270吨，先运至A1,A2,A3三个仓库，然后再分别供应B1,B2,B3,B4,B5五个地区需要。已知各仓库容量分别为50,100,150（吨），各地区的需要量分别为25,105,60,30,70（吨）。已知从糖厂经由各仓库然后供应各地区的运费和储存费如表所示。 B1 B2 B3 B4 B5 A1 10 15 20 20 40 A2 20 40 15 30 30 A3 30 35 40 55 25 解：仓库容量300吨，各地区需要量总计290吨。仓库有30吨装不满，各地区有20吨需要不能满足。可虚设一库容20吨的仓库A4来满足需要，相应虚设一地区B6来虚构仓库中未装进的30万吨糖。由此列出运输表如下 B1 B2 B3 B4 B5 B6 供应 A1 10 15 20 20 40 0 50 A2 20 40 15 30 30 0 100 A3 30 35 40 55 25 0 150 A4 0 0 0 0 0 M 20

需求

25 105 60 30 70 30 320