运筹学习题集04

销地 1 2 3 行差额 产地 1 5 1 8 4 2 2 4 1 1 3 3 6 7 3 列差额 1 3 6 从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表： 销地 1 2 3 产量 产地 1 12 11 2 14 3 4 销量 9 10 11 同时将运价表第三列数字划去，得 销地 1 2 产量 产地 1 5 1 12 2 2 4 14 3 3 6 4 销量 9 10 对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是： 销地 1 2 3 产量 产地 1 2 10 12 2 3 11 14 3 4 4 销量 9 10 11 （2）3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同3-3相同）

最终得出原问题的初始解：

销地 产地 1 2 3 4 销量 1 2 3 4 5 产量 25 20 30 20 30 20 20 30 10 25 3.3用表上作业法求给出运输问题的最优解（M是任意大正数） （1） 销地 甲 乙 丙 丁 产量 产地 1 3 7 6 4 5 2 2 4 3 2 2 3 4 3 8 5 3 销量 3 3 2 2 解：

1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最（1）○右列和最下列。

2从行差额或者列差额中找出最大的， ○选择它所在的行或者列中的最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，

而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到： 销地 甲 乙 丙 丁 产量 产地 1 3 7 4 5 2 2 3 4 3 5 3 销量 3 3 2 3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，○

1○2，直到求出初始解为止。得到下表：填入该标的最右列和最下行，重复步骤○

销地 甲 乙 丙 丁 产量 产地 1 2 3 销量 3 0 3 3 3 使用位势法进行检验： 2 2 2 0 2 5 2 3 1上表中，数字格处填入单位运价并增加一行一列，在列中填入ui（i=1，○

2，3），在行中填入vj（j=1，2，3，4），先令同）来确定销地 产地 1 2 3 uivi+

=cij（i，j?B，B为基，下

ui和

vi，得到下表：

乙 丙 丁 甲 ui0 -2 1 vi3 4 3 3 2 -（

3 5 4 2 4 2由?ij=○

cijuivi+

）（i，j为非基，下同）计算所有空格的检验数，并

在每个格的右上角填入单位运价，得到下表 销地 甲 乙 丙 丁 ui 产地 1 3 7 6 4 0 0 5 1 0 2 2 4 3 2 -2 1 4 0 0 3 4 3 8 5 1 0 0 2 0 3 2 5 4 vi 由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。 又因为?34=0，此问题有无穷多最优解。 总运费min z=3*3+3*3+2*3+2*4=32

（2）

销地 产地 1 2 3 销量 甲 乙 丙 丁 产量 10 16 5 5 6 10 4 2 7 5 10 4 12 9 10 6 4 9 4 1计算出各行和各列的次最小运费和最小运费的差额，填入该表解：（2）○的最右列和最下列。

2从行差额或者列差额中找出最大的， ○选择它所在的行或者列中的最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲

的需求，同时将运价表中产地3所在行的数字划去。

3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额， ○

1○2，直到求出初始解为止。得到下表：填入该标的最右列和最下行，重复步骤○ 销地 甲 乙 产地 1 1 2 2 3 4 销量 5 2 使用位势法进行检验： 丙 丁 产量 1 3 4 6 6 4 9 4 1上表中，○数字格处填入单位运价，并增加一行一列，在列中填入ui（i=1，2，3），在行中填入vj（j=1，2，3，4），先令u1=0，由 为基，下同）来确定

2由?ij=○

uivi+

=cij（i，j?B，B

ui和+

vi.

cij-（

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

丙 丁 右上角填入单位运价，得到下表 销地 甲 乙 产地 1 10 0 2 16 8 6 3 5 ui12 0 6 10 0 4 7 1 5 0 10 9 -2 10 -5