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

并用位势法进行检验： 销地 甲 乙 丙 丁 戊 己 ui 产地 1 2 3 10 18 2 8 13 M 3 M-16 0 0 6 29 0 21 1 11 3 14 0 M 13 6 16 12 0 -10 22 12 0 0 0 0 第 42 页 共 64 页

0 4 4 5 24 2 10 9 0 11 0 28 0 16 0 23 7 36 3 21 0 18 10 30 5 13 M-6 19 8 34 6 16 22 0 17 0 -12 12 -5 vi由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为?31=0，此问题有无穷多最优解。

总运费min z=5520 3.4 已知运输问题的产销平衡表、单位运价表及最优调运方案如下表所示 表1 销产量 B1 B2 B3 B4 地 产地 5 10 15 A1 A2 A3 0 5 5 10 15 15 15 10 25 5 销量 表2 销地 产地 B1 B21 7 14 c22 B3 B411 20 18 A1 （1）（2）

10 12 2 20 9 16 A2A3A2A2到到

B2B4的单位运价在什么范围变化时，上述最优方案不变？

的单位运价变为何值时，有无穷多最优方案。除表1中方案

外，至少写出其他两个。

解：

1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在列中(1)○

填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由

uivi+=cij第 43 页 共 64 页

（i，j?B）来确定

2由?ij=○

uiv和i.

cij-（

uivi+）（i，j?N）计算所有空格的检验数，并在每个格的右

上角填入单位运价（c22未知）。

最优调运方案不变，则所有非基变量的检验数都是非负。所以：

c22-3?0 c22+10?0

10-c22?0 24-c22?0 18-c22?0 解得: 3?c22?10

单位运价在此区间变化时，最优调运方案不变。

1在对应表的数字格处（c22未知）填入单位运价，并增加一行，在（2）○

列中填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 （i，j?B）来确定2由?ij=○

uivi+=cijuiv和i.

cij-（uivi+）（i，j?N）计算所有空格的检验数，并在每个格的右

上角填入单位运价（c22未知）。

有无穷多最优方案，则至少有一个非基变量的检验数为0.

取c24-17=0，所以单价变为17时，该问题 有无穷多最优调运方案。 另外的两种调运方案： 1 ○销地 产地 A1 A2 B1 B2 B3 B40 10 产量 15 25 0 15 15 第 44 页 共 64 页

A3 5 5 2 ○

15 15 10 5 销量 销地 产地 A1 A2 A3 B1 B2 B3 B4 10 10 产量 15 25 5 0 5 5 15 0 15 15 15 销量 3.5 某百货公司去外地采购ABCD四种规格的服装，数量分别为：A,1500套；B，2000套；C，3000套；D，3500套；有三个城市可以供应上述服装，分别为：I，2500套，II，2500套；III，5000套。已知下表，求预期盈利最大的采购方案。 A B C D I 10 5 6 7 II 8 2 7 6 III 9 3 4 8 解： 因为利润表中的最大利润是10，所以令M=10，用M减去利润表上的数字，此问题变成一个运输问题，见下表： 销地 A B C D 产量 产地 I 0 5 4 3 2500 II 2 8 3 4 2500 III 1 7 6 2 5000 销量 1500 2000 3000 3500 使用伏格尔法计算初始解： ○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下行。

○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，同时划掉所在列或行的元素。

○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。

第 45 页 共 64 页

销地 A 产地 I 1500 II III 销量 1500 使用位势法检验： B C D 产量 500 1500 2000 500 2500 3000 3500 3500 2500 2500 5000 1数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3）○，在行中填入vj（j=1，2，3，4），先令u1=0，由 uiviu+=cij（i，j?B，）来确定iv和i. 2由?ij=○cij-（uivi+）（i，j?N）计算所有空格的检验数，并在每个格的右上角填入单位运价。 如果没有得到最优解，用逼回路法进行改进。 盈利最大方案： 销地 A B C 产地 I 0 5 4 0 0 II 2 8 3 3 4 0 III 1 7 6 0 1 1 0 5 4 vi D ui3 0 2 4 4 2 1 1 -1 此时，总运费为28000元;最大盈利为72000元。 3.6甲乙丙三个城市每年需要煤炭分别为：320万吨、250万吨、350万吨，由A、B两处煤矿供应。煤炭供应量分别为：A,400万吨；B,450万吨；运价如下表，由于需大于供应，经研究平衡决定，甲城市供应量可以减少0~30万吨，乙城市需要完全供应，丙城市供应不少于270万吨。试求将供应量分配完又使总运费最低的调运方案。 甲 乙 丙