电子课件第三章

电子课件第三章第一页，共一百七十三页，2022年，8月28日3.1运输问题模型

第2章中讨论了有关物资调运的问题，即运输问题。有时候为了书写简便，运输问题也被写做TP（TransportationProblem）。第二页，共一百七十三页，2022年，8月28日3.1运输问题模型

对某种物资，设有m个产地A1,A2,…,Am，称它们为发点，其对应产量为a1,a2,…,am，称它们为产量；另有n个销地B1,B2,…,Bn，称它们为收点，其对应销量为b1,b2,…,bn，称它们为销量。又知，从产地（发点）Ai运至销地（收点）Bj，该种物资每单位的运价为cij（cij≥0）。试问：应如何安排调运方案，在满足一定要求的前提下，使总运费最低？第三页，共一百七十三页，2022年，8月28日3.1运输问题模型根据上述参量的意义列出产销运价，如表3.1所示。

表3.1产销运价表

销地产地B1

B2

…Bn

产量A1

c11

c12

c1n

a1

A2

c21

c22

c2n

a2

…Am

cm1

cm2

cmn

am

销量b1

b2

bn

ai

bj

第四页，共一百七十三页，2022年，8月28日3.1运输问题模型

表中：ai的单位为吨、公斤、件等；bj的单位为吨、公斤、件等；cij的单位为元/吨等。ai,bj,cij的单位应该一致（i1,2,…,m；j1,2,…,n）。

第五页，共一百七十三页，2022年，8月28日3.1运输问题模型

表的右下角ai表示各产地产量的总和，即总产量或总发量；bj表示各销地销量的总和，即总销量或总收量。这里有两种可能：（1）aibj（总产量总销量），即产销平衡问题。（2）ai≠bj（总产量≠总销量），即产销不平衡问题。它又可分为两种情况：产大于销，即ai＞bj；销大于产，即ai＜bj。下面先讨论产销平衡问题，再讨论产销不平衡问题。第六页，共一百七十三页，2022年，8月28日3.1运输问题模型令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表如表3.2所示。

表3.2产销平衡表

销地产地

B1

B2

…Bn

产量A1

x11

x12

x1n

a1

A2

x21

x22

x2n

a2

…Am

xm1

xm2

xmn

am

销量b1

b2

…bn

aibj

第七页，共一百七十三页，2022年，8月28日3.1运输问题模型将表3.1和表3.2两个表合在一起，得到的一个新表，被称为运输表（或称为产销矩阵表），如表3.3所示。表3.3

运输表（产销矩阵表）

销地产地B1

B2

…Bn

产量A1

X11c11

x12

c12

x1n

c1n

a1

A2

x21

c21

x22c22

x2n

c2n

a2

…Am

xm1cm1

xm2cm2

xmn

cmn

am

销量b1

b2

…bn

ai

bj

第八页，共一百七十三页，2022年，8月28日3.1运输问题模型根据产销矩阵表，求上述问题的解等于求下面数学模型的解，即求：xij（i1,2,…,m；j1,2,…,n）（3-1）

第九页，共一百七十三页，2022年，8月28日3.1运输问题模型（3-2）第十页，共一百七十三页，2022年，8月28日3.1运输问题模型

从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。（1）该问题的基变量有mn1个。（2）该问题一定有最优解。（3）如果ai，bj全是整数，则该问题一定有整数最优解。

由于对这类问题的研究最早从运输问题开始，故这类问题统称为运输问题。

第十一页，共一百七十三页，2022年，8月28日3.2运输问题的表上作业法

3.2.1产销平衡运输问题的表上作业法

从上面的运输问题的数学模型中可以看到，它包含mn个变量，mn个约束条件。如果用单纯形法求解，应先在每个约束方程中引进一个人工变量。这样一来，即使是m3，n4这样简单的运输问题，变量数就有12个，显然计算起来非常繁杂；而用表上作业法来求解运输问题则比较简便。第十二页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

用表上作业法求解运输问题时，同单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。

第十三页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案——最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。

第十四页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

下面以煤的调运问题为例介绍表上作业法的计算过程。例3.1设有三个产煤基地A1、A2、A3，四个销煤基地B1、B2、B3、B4，产地的产量，销地的销量和从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。第十五页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

表3.4产销运价表

万吨，万元

销地产地B1

B2

B3

B4

产量A1

3113107A2

19284A3

741059销量3656

2020第十六页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法（1）列出运输问题的产销矩阵表。根据表3.4，可列出产销矩阵表（也称为运输表），如表3.5所示。第十七页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法表3.5产销矩阵表万吨，万元销地产地B1

B2

B3

B4

产量A1x113x1211x133x14107A2x211x229x232x2484A3x317x324x3310x3459销量3656

2020第十八页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

其中：xij为产地Ai到销地Bj的运量（i1,2,3；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法——最小元素法。第十九页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法在应用最小元素法确定初始方案时，必须注意以下两点。（1）当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt（即asbt），这时，可在产销矩阵表上xst处填上一个数as，并画上圈。为了保证调运方案中画圈的数字为mn1个，只能在s行的其他格上都打上“×”（或在t列的其他格上都打上“×”），不可以同时把s行和t列的其他格子都打上“×”。第二十页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法（2）当最后只剩下一行（或一列）还存在没有填数和打“×”的格子时，规定只允许填数，不允许打“×”，其目的也是为保证画圈数字的个数恰为mn第二十一页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

所谓闭回路，就是从调运方案的某一个打“×”处（xij）处作为一个起点出发，在表格里向纵的或横的方向一直走，碰到有圈数字的格才可以拐弯，这样拐了几个弯以后，再回到起点处，就画出一条封闭的折线（由水平和铅直的直线所组成）第二十二页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

它所有的转角处（通常称为闭回路的顶点或转角点）除该打“×”处以外，其余的都必须是画圈的数字，这样的一条封闭折线成为过xij处的闭回路（简称回路）。例如，表3.9中的直线表示的闭折线分别是过x11处和过x24处的闭回路。

第二十三页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

可以证明，过xij处的闭回路一定存在，而且是唯一的（证明略）。下面我们简单说明用闭回路法来检验调运方案的原理。表3.9中x11的打“×”处表示A1生产的煤不调运给B1。第二十四页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

我们假定把调运方案改变一下，让A1生产的煤调运1（万吨）给B1，观察过x11处的回路，为了保持新的平衡，就要依次在x13处减少1（万吨），x23处增加2（万吨），x21处减少1（万吨），即总运费增加33211（万元）。

第二十五页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

这说明把A1生产的煤调运给B11（万吨），总运费比原方案增加1万元，是不合算的。我们把通过x11处的回路改变的运费数1（万元）称为x11处的检验数，记为111。如果所有的打“×”处检验数都大于或等于0，表明对调运方案作任何改变都将导致总的运费增加，没有比已给定方案更好的方案了，即给定的方案就是最优方案。第二十六页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法否则，如某一打“×”处的检验数为负，则表明对调运方案做出调整后，运费就会减少，即给定方案不是最优方案。因此，利用闭回路求得检验数的正或负可以判别调运方案是否最优。第二十七页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

这样，用闭回路法检验某调运方案是否最优，可按下面两步进行。①求检验数。从某xij的打“×”处出发，沿着它的闭回路前进（顺时针或逆时针都可以）。将这个打“×”处对应的单位运价加上正号，而下面首先遇到的一个顶点作为第一个顶点的对应的单位运价加上负号，再将第二个遇到的顶点处对应的单位运价加上正号，正负交错，依次类推。第二十八页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

最后将这些带有正负号的运费相加而得到的总和称为xij处的检验数ij。例如，表3.9中x24处的检验数24沿它的闭回路（按顺时针）计算如下：24

c24c23c13c14823101

因为过xij的回路是唯一的，所以它的检验数ij也是唯一的。第二十九页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法②根据检验数进行判别。判别准则是：若所有的检验数都是非负的，即ij≥0，则所检查的调运方案为最优方案；否则，若存在负的检验数．则所检查的调运方案不是最优的。

第三十页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法下面给出对表3.9调运方案检验的全过程。解①求检验数。11c11c13c23c213321112c12c14c34c32111054222c22c23c13c14c34c329231054124c24c23c13c1482310131c31c21c23c13c14c3471231051033c33c13c14c3410310512将所有打“×”处的检验数填入表中，得到检验数表，如表3.12所示。

第三十一页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法②根据检验数进行判别。因为241＜0，所以调运方案Ⅰ不是最优的。表3.12检验数表销地产地B1B2B2B2A11B3B3B3A2

B4B4B4A310222第三十二页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法（4）调运方案的调整——闭回路法。如果所得到的调运方案不是最优的，就必须调整。根据前面讲过的闭回路的原理，表3.6调运方案Ⅰ中241＜0，因此设法使x24不为零，就能使总运费减少，所以应对它作最大可能的调整。第三十三页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

观察过x24的闭回路如表3.9所示，为了把A2生产的煤调运给B4，就要相应减少A2调运给B3的煤运量和A1调运给B4的煤运量，只有这样才能得到新的平衡，这两个格内较小的运量是1，即min（1，3）1，因此A2最多只能将1（万吨）煤调运给B4，经这样调整后可得到一个新的调运方案Ⅱ，如表3.13所示。第三十四页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

方案Ⅱ的总运费z85万元，显然85＜86（万元）。对方案Ⅱ进行检验，经计算所有打“×”处的检验数都是非负数（请同学自己作为练习），所以它是最优方案。可见，用闭回路法来调整调运方案是行之有效的。

第三十五页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法表3.13调运方案Ⅱ万吨，万元

销地产地B1

B2

B3

B4

产量A1

3×

11×

3⑤

10②7A2

1③

9×

2×

8①4A3

7×

4⑥

10×

5③9销量3656

2020第三十六页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法一般地，调运方案的调整可分三步进行。①在检验数表中确定一个绝对值最大的负检验数st，作出过xst处的闭回路。②从xst所在的格出发，沿着它的闭回路前进，在各奇数次顶点（画圈的数字）中选出最小的一个数（运量）记为d。③将d填在xst处，并画上圈，同时将闭回路上其他奇数次顶点的运量都减去d，在偶数次顶点的运量都加上d，这样就得到一个新的调运方案。

第三十七页，共一百七十三页，2022年，8月28日产销平衡运输问题的表上作业法

一般说来，经过一次调整后，对新方案进行检验，可能还会出现负的检验数，那就需要再进行调整，直至所有检验数st≥0为止。这里还需指出，有时在闭回路的调整过程中，奇数次顶点的画圈数字中有两个或两个以上相等的最小运量，这样在调整时，为了产销矩阵表上画圈数字的个数仍然保持mn1个，以便用表上作业法继续进行计算，规定在奇数次顶点最小运量处只打上一个“×”，其余的地方都填上“0”，并画上圈。画圈的0仍当做有圈的数字看待。第三十八页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤

第一步，求初始调运方案（用最小元素法）。它保证有调运量的格子个数（基变量个数）等于mn1。

第三十九页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤最小元素法的步骤如下。（1）从没有“×”的运价格子中，找出最小运价（若同时有若干个相同最小运价则可任选一个），在它的左下角填入最大可能调运量（能够供应的数量和尚需数量的最小值），转步（2）。

第四十页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤（2）若无“×”的格子只剩一行或一列，转（1）；否则，“×”去调运量已满足的行或列中其运价处没有填数和没有划“×”的格中的左下角填“×”，（只能在一行或一列中填“×”），转步骤（1）。

第四十一页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤第二步，求检验数。若所有ij≥0，则最优解已求得，计算终止。填有调运量的格子为最优调运方案（未填调运量的格子，调运量为0），计算各调运量与对应格子运价之积，再求它们的和就是最低总运费。若至少有某个ij＜0，转第三步。

第四十二页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤第三步，调整。（1）从最小负检验数的对应格子出发画直线，碰到有调运量的适当格子转角，做出惟一的一条闭回路（理论证明的结果）。（2）在这个闭回路上，令画“×”处格子为偶数转角点，依次（无论沿顺时针方向还是沿逆时针方向）排出各转角点的奇偶性，再求调整量min（各奇数转角点调运量）。

第四十三页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤（3）按“偶点处加调整量，奇点处减调整量”的方法，重新安排回路上转角点处的调运量，将奇数转角点处调运量变为0的一个（仅能一个）格子右上角打“×”，回到第二步。

第四十四页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤

注意：①如遇到发量已发完，且收量已满足的格子还需要填入调运量时，就填入数字0；②在最优解中若非基变量（画“×”处）的检验数为0，仍可从该格子处出发作唯一的闭回路，再按第三步调整可得另一最优解，此时目标函数最小值不改变。第四十五页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤

例3.2

工地有3个高地A1、A2、A3和4个洼地B1、B2、B3、B4，我们想把高地土方有计划地去填洼地。设各个高地的出土量和各个洼地的填土量如表3.14所示，各个高地与各个洼地之间的距离如表3.15所示。试用表上作业法制定最合理的调运方案。

第四十六页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤解（1）将运量表与距离表合并为产销矩阵表，如表3.16所示。（2）用最小元素法求出初始调运方案Ⅰ，如表3.17所示。（3）利用闭回路法求得检验数表Ⅰ，如表3.18所示。因为检验数表中的检验数有负数，必须进行调整。

第四十七页，共一百七十三页，2022年，8月28日洼地高地B1B2B3B4出土A1

70A2

20A3

10填土50251015

100

100

表3.14运量表10土方

第四十八页，共一百七十三页，2022年，8月28日表3.15距离表100米洼地高地B1B2B3B4A110523A24312A35634第四十九页，共一百七十三页，2022年，8月28日表3.16产销矩阵表10土方，100米

洼地高地B1B2B3B4出土A11052370A2431220A3563410填土50251015

100100第五十页，共一百七十三页，2022年，8月28日表3.17调运方案Ⅰ10土方，100米

洼地高地

B1B2B3B4出土A1105×2⑤370A2×4×3⑩1⑩220A3⑩5×6×3×410填土50251015

100100

第五十一页，共一百七十三页，2022年，8月28日表3.18检验数表Ⅰ

洼地高地B1B2B3B4A1

0

A251

A3

666第五十二页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤（4）在检验数表Ⅰ中，较大，所以过调运方案Ⅰ（表3.17）中x21处做出它的闭回路，进行调整得到调运方案Ⅱ，如表3.19所示。（5）求调运方案Ⅱ的检验数表，如表3.20所示。因为调运方案Ⅱ检验数表中的检验数有负数，必须进行调整。第五十三页，共一百七十三页，2022年，8月28日产销平衡运输问题表上作业法步骤（6）因为135＜0，所以过调运方案（Ⅱ）（表3.19）中x13处做出它的闭回路，进行调整得到调运方案Ⅲ，如表3.21所示。（7）再求出方案（Ⅲ）的检验数表Ⅲ，如表3.22所示。由于检验数全部为正数，所以调运方案Ⅲ为最优方案。（8）目标函数值为：minz2010255102153204105520（土方公里）

第五十四页，共一百七十三页，2022年，8月28日表3.19调运方案Ⅱ10土方，100米

洼地高地B1B2B3B4出土A1105×2370A24×31×220A35×6×3×410填土50251015

100100第五十五页，共一百七十三页，2022年，8月28日表3.20检验数表Ⅱ

洼地高地B1

B2B3B4A1

5

A24

5A3616第五十六页，共一百七十三页，2022年，8月28日表3.21调运方案Ⅲ10土方，100米

洼地高地B1B2B3B4出土A11052370A24×3×1×220A35×6×3×410填土50251015

100100第五十七页，共一百七十三页，2022年，8月28日表3.22检验数表Ⅲ

洼地高地B1

B2B3B4A1

A2455A3666第五十八页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

上面看到，要判别一个方案是否最优，需要过每一个打“×”处做出它的闭回路，再根据回路求出所有的检验数。当一个运输问题的产地和销地个数很多时，用这个方法计算检验数的工作量十分繁重。下面介绍一种更为简便的求检验数的方法——位势法。我们仍用煤的调运问题作为例子来介绍这种方法。第五十九页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

表3.23给出了这个例子用最小元素法确定的初始调运方案。我们用位势法求检验数时，第一步先在表3.23中添加新的一列ui列（i的个数等于产地的个数）和新的一行vj行（j的个数等于销地的个数），如表3.24所示。第六十页，共一百七十三页，2022年，8月28日表3.23初始调运方案

万吨，万元

销地产地B1B2B3B4产量A1×3×11④3③1073A2③1×9①2×

841A3×7⑥4×10③593销量3656

2020第六十一页，共一百七十三页，2022年，8月28日表3.24初始调运方案（第一步）万吨，万元

销地产地

B1B2B3B4产量uiA1×3×11④3③107u1A2③1×

9①2×84u2A3×7⑥4×10③59u3销量365620

vjv1v2v3v4

第六十二页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

这里的ui和vj分别称为第i行和第j列的位势（i1,2,…,m；j列的位势（i1,2,…,m；j1,2,…,n），并规定它们与表中画圈数字所在的格对应的单位运价有如下关系：（3-3）第六十三页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

第二步是确定ui和vj的数值，由于这些ui和vj的数值相互是有关联的，所以只要任意给定其中的一个；根据关系式（3-3），很容易将其他所有的位势的数值求出。例如，在表3.24中，先令v11，则可由第六十四页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数u2v11 u20u2v32 v32u1v33 u11u1v410 v49u9v45 u34u3v24 v28

把这些数分别填入表3.24的ui列和vj行，得到表3.25。第六十五页，共一百七十三页，2022年，8月28日表3.25初始调运方案（第二步）万吨，万元

销地产地B1B2B3B4产量uiA1×3×11④

3③

1071A2③

1×

9①

2×840A3×

7⑥

4×

10③

594销量365620

vj1829

第六十六页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

第三步，求出位势后可以根据下面的原理求“×”处格子的检验数（即非基变量的检验数）。令ij表示xij处的检验数。例如，31可由闭回路法计算得到：31c31c34c14c13c23c21c31（u3v4）（u1v4）（u1v3）（u2v3）（u2v1）c31（u3v1）

第六十七页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

其中c31是x31处对应的单位运价，（u3v1）恰好就是该打“×”处所在行和列的位势之和。类似地，可以得出任一打“×”处（xij处）的检验数，即ij

cij(uivj)（3-4）

第六十八页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数

根据式（3-4），很容易求出表3.25中所有打“×”处的检验数，即113–1111211182229081248091317(4)1103310(4)212第六十九页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数显然，求得的6个检验数与用闭回路求得的检验数（见表3.12）完全一致。如果检验数中出现了负数，对方案进行调整的方法同前面闭回路法一样。最后再指出一点，有无可能在计算位势时出现中断或某一行或某一列可能得出两个不同的位势值的情况。答案是否定的，对给定的初始方案，只要首先给出一个位势，则其他行与其他列的位势存在且惟一。第七十页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数例3.3

对表3.19调运方案Ⅱ，用位势法求检验数。解

（1）在表3.19中添加新的ui列和vj行得表3.26。（2）令u15，用各有圈数字所在格的单位运价，按关系式cij(uivj)依次求出各位势值填入表3.26。第七十一页，共一百七十三页，2022年，8月28日表3.26调运方案Ⅱ10土方，100米

洼地高地

B1B2B3B4出土uiA1105×23705A24×31×2201A35×6×3×4100填土50251015

vj5022

第七十二页，共一百七十三页，2022年，8月28日3.2.3用位势法求检验数（3）利用打“×”处的单位运价，按式（3-4），即可间接求得相应的检验数表Ⅱ，如表3.27所示。

第七十三页，共一百七十三页，2022年，8月28日表3.27检验数表Ⅱ

洼地高地B1B2B3B4A1

5

A2

4

5A3

616第七十四页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

对于运输问题的初始方案的确定，除了可用最小元素法之外，还可以用其他的方法。例如，西北角法和沃格尔法（Vogel法，也称为元素差额法）等，下面介绍这两种方法。第七十五页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法1．西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足产销矩阵表中西北角（即左上角）上空格的供销需求，优先满足供应。下面讨论表3.28所表示的例子。

第七十六页，共一百七十三页，2022年，8月28日表3.28西北角法例子数据

万吨，万元

销地产地

B1B2B3B4产量A1⑧4⑧12×4×11168A2×2⑥

10④3×9104A3×8×5⑧1162214销量814612148

4848第七十七页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

由表3.28可知，该表左上角的空格是（A1，B1），在使用西北角法时先在（A1，B1）格中填入数字xijmin（a1，b1）min（16，8）8。因为B1的销量已经满足，所以B1所在列的格内x21、x31处打“×”，A1的可供量变为1688。在产销矩阵表尚未填数和打“×”的部分中，左上角格子变为（A1，B2）。由于min（a1–8，6）min（8，14）8，故在（A1，B2）格子中填入8。第七十八页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

因为A1的可供量已经用完，所以A1所在行的格内x13、x14处打“×”，B2的需求量由b214变为1486。这时（A2，B2）是产销矩阵表剩下部分的左上角格子。因min（a2，b8）6，在（A2，B2）中填入数字6，并在B2所在列的格内x32处打“×”，A2的可供量变为1064。如此继续下去，在（A2，B3）格中填入4，在（A3，B3）格中填入8，最后在（A3，B4）格中填入14，同时在A3行和B4列中的其他格中填“×”。寻求初始调运方案的过程示于表3.28中。第七十九页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法至此得到初始方案解为x118，x128，x226，x234，x338，x3414其他变量均等于0。它所对应的目标函数z值为：z8481261043811146372第八十页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法2．沃格尔法

沃格尔法（Vogel法）也称为元素差额法。

初看起来，最小元素法十分合理；但是，有时按某一最小单位运价优先安排物品调运时．却可能导致不得不采用运费很高的其他供销点对，从而使整个运输费用增加。对每一个供应地（或销售地），均可由它到各销售地（或各供应地）的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地（或销售地）的罚数（也称为差额）。第八十一页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。

第八十二页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

下面结合表3.28所表示的例子说明这种方法。

首先计算产销矩阵表中每一行和每一列的次小单位运价和最小单位运价之间的差值，并分别称之为行罚数和列罚数。将算出的行罚数填入位于表右侧行罚数栏的左边第一列的相应格子中，列罚数填入位于表下边列罚数栏的第一行的相应格子中，如表3.29所示。

第八十三页，共一百七十三页，2022年，8月28日表3.29沃格尔法例子数据

销地产地B1

B2

B3

B4

产量

行罚数12345A1×4

×12

4④1116000⑦

A2⑧2

×10×3②91011160A3×8

5×11⑧62212销量8141214列罚数12⑤13221③3②124125②第八十四页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

例如，A1行中的次小和最小单位运价均为4，故其行罚数等于0；A2行中的次小和最小单位运价分别为3和2，其行罚数等于321；B1列中的次小单位运价和最小单位运价分别为4和2，其列罚数等于2。如此进行，计算出本A1、A2和A3行的行罚数分别为0、1和1、B1、B2、B3和B4列的列罚数分别为2、5、1和3。第八十五页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

在这些罚数中，最大者为5（在表3.29中用小圆圈示出），它位于B2列。由于B2列中的最小单位运价是位于（A3，B2）格中的5，故在（A3，B2）格中填入尽可能大的运量14，此时B2的需要量得到满足，在B2列的其他格中填“×”。第八十六页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

在尚未填数和填入“×”的各行和各列中，按上述方法重新计算各行罚数和列罚数，并分别填入行罚数栏的第2列和列罚数栏的第2行。例如，在A3行中剩下的次小单位运价和最小单位运价分别为8和6，故其罚数等于2。由表3.29中填入这一轮计算出的各罚数可知，最大者等于3位于B4列，由于B4列中的最小单位运价为6，故在其相应的格中填入这时可能的最大调运量8，在A3行的其他格中填“×”。第八十七页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

用上述方法继续做下去，依次算出每次迭代的行罚数和列罚数，根据其最大罚数值的位置在表中的适当格中填入一个尽可能大的运输量，并在对应的一行或一列的其他格中填“×”。在本例中，依次在表中填入运输量x3214，x348，x218，x1312，x242，并相应地依次在B2列、A3行、B1列、B3列、A2行中填“×”。最后未画“×”的格仅为（A1，B4），在这个格中填入数字4，并同时在A1行和B4列中填“×”。第八十八页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法用这种方法得到的初始方案的解为x1312，x144，x218，x242，x3214，x348其他变量的值等于零。这个解的目标函数值为z124411822914586244第八十九页，共一百七十三页，2022年，8月28日3.2.4确定初始方案的其他方法

比较上述最小元素法、西北角法和沃格尔法三种方法给出的初始方案的解，以沃格尔法给出的解的目标函数值最小，最小元素法次之，西北角法解的目标函数值最大。一般说来，沃格尔法得出的初始解的质量较好，常用来作为运输问题最优解的近似解。

第九十页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

对于产销不平衡的运输问题，可分为总供给量（总产量）＞总需求量（总销量）（即ai＞bj）或总需求量（总销量）超过总供给量（总产量）（即ai＜bj）两种情形，关键是按具体情况虚设收点或虚设发点，其收量或发量是两类总量的差数，并按实际意义决定各新增格子上的单位运价，这样就把它们转化为产销平衡的运输问题。

第九十一页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题下面举例说明上述方法。例3.4

求下面运输问题的最优调拨方案，其产销运价表如表3.30所示。

第九十二页，共一百七十三页，2022年，8月28日表3.30例3.4产销运价表

销地产地

B1B2B3B4产量A1211347A2103595A378127

销量23461915

第九十三页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

解通过对右下角总供给、总需求的计算，发现ai＞bj，产量有剩余，应虚设一收点，叫做库存。任何发点到库存的单位运价设为0，收点“库存”的收量等于：总发量总收量19154，这就建立了一个平衡的运输问题，如表3.31所示。第九十四页，共一百七十三页，2022年，8月28日表3.31例3.4产销运价表（平衡方案）

销地产地

B1B2B3B4B0产量A12②11×3×4③0②7A210×3③5×9×0②5A37×8×1④2③0×7销量234641919

第九十五页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

但是，在用最小元素法寻找初始调运方案时，每次不要考虑（新增）库存这一列的单位运价，否则一开始就去满足库存而不是实际的需要，会使初始方案离最优方案距离更远，会增加以后调整的工作量。按最小元素法做出的初始调运方案（请读者重新做一遍并与此题结果核对）如上表所示。经检验，它就是最优调拨方案。由于130，还可有另外的最优调拨方案但总运费不会再下降。第九十六页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题例3.5

设有3个化肥厂供应4个地区的化肥，并设等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地年需求量，以及化肥的单位运价如表3.32所示，其中（3，4）处的M表示运价非常高。试求使总运费最低的调拨方案。

第九十七页，共一百七十三页，2022年，8月28日表3.32例3.5产销运价表

销地产地

ⅠⅡⅢⅣ产量/万吨A1613221750B1413191560C192023M50最低需求/万吨3070010160110

最高需求/万吨507030不限160M

第九十八页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题解从满足各地最低需求角度，这是一个总产量大于总销量的运输问题，但从市场或支农角度，应尽量满足各地对化肥的最高需求，所以这又是一个总销量大于总产量的运输问题。

第九十九页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

由于第Ⅳ地最高需求不限，但总产量只有160万吨，故第Ⅳ地的最高需求量是可以计算的，它等于从总产量中扣除其他各地最低需求量后的剩余，即160（30700）60。于是所有各地最高需求量总和为；50703060210（万吨）。它超出总产量21016050（万吨），应虚拟一个产地D，其产（发）量为50。第一百页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

由于各地最低需求量必须满足，故不能用虚拟发点D的发量去满足。为此，必须把最高需求比最低需求量多的收点分成两个。例如，销地II'I"，其中I'表示最低需求，I"表示超过最低需求的部分。由于D不能供给I'，相交处运价填M；由于D可以供给I"，但D是虚拟发点，即使对应格子填有正的调运量也不至于产生运费，因此交点处单位运价填0。其他仿此，我们做出下面平衡的产销矩阵表，如表3.33所示。第一百零一页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

在用最小元素法确定初始运输方案时，首先不考虑虚拟发点D所在行的运价，而应先在运价最小的格子（A1，B3）处填入50，第一行中其他格子打“×”；接着填格子（A2，B3），只能填20，列中其他格子打“×”。这两个格子的调运量填好后，看到Ⅳ'的需求10单位必须由B处剩余产量满足，所以应先填（A2，B5）处的10。尽管其单位运价还不是最低的，否则会造成初始调拨方案与最优调拨方案相距甚远。余下格子填数的方法从略。本例调运量未加“〇”而用“（）”表示。如表3.34所示。第一百零二页，共一百七十三页，2022年，8月28日表3.33例3.5产销矩阵表（一）

销地产地

Ⅰ'Ⅰ"ⅡⅢⅣ'Ⅳ"产量/万吨A16161322171750B14141319151560C19192023MM50DM0M0M050需求量/万吨302070301050160160

第一百零三页，共一百七十三页，2022年，8月28日表3.34例3.5产销矩阵表（二）

销地产地

Ⅰ'Ⅰ"ⅡⅢⅣ'Ⅳ"产量/万吨A161613(50)22171750B14(10)14(20)13(20)1915(10)1560C19(20)192023(30)MM50DM0M0(0)M0(50)50需求量/万吨302070301050160160

第一百零四页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题求出的初始调拨方案如表3.34所示。计算出行位势ui、列位势vj，再计算检验数后发现1617（018）

1＜0，26

3＜0，从（A2，B6）出发作闭回路，其转角点为（A2，B6）偶，（A4，B6）奇，（A4，B4）偶，（A3，B4）奇，（A3，B1）偶，（A2，B1）奇，（A2，B6）偶。调整量min（50，30，10）10，按第三步调整结果如表3.35所示。

第一百零五页，共一百七十三页，2022年，8月28日表3.35例3.5产销矩阵表（三）

销地产地

Ⅰ'Ⅰ"ⅡⅢⅣ'Ⅳ"产量/万吨A161613(50)22171750B1414(20)13(20)1915(10)15(10)60C19(30)192023(20)MM50DM0M0(10)M0(40)50需求量/万吨302070301050160160

第一百零六页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题3219（814）3＜0，它是最小负检验数。从（A3，B2）出发作闭合回路，找出：调整量min（20，40，20）20，并在回路上调整后得表3.36。第一百零七页，共一百七十三页，2022年，8月28日表3.36例3.5产销矩阵表（四）

销地产地

Ⅰ'Ⅰ"ⅡⅢⅣ'Ⅳ"产量/万吨A161613(50)22171750B1414(0)13(20)1915(10)15(30)60C19(30)19(20)2023MM50DM0M0(30)M0(20)50需求量/万吨302070301050160160

第一百零八页，共一百七十三页，2022年，8月28日3.3产销不平衡的运输问题

对于表3.36所示的调运方案，经检验未发现负检验数，故它是最优调运方案。由于2114（013）0，还可能做出另一最优方案，但因从（A2，B1）出发的闭回路上，奇数的角点最小调运量为0，故不能产生实质性的另一最优方案。最低总运费为2460，最优调运方案请读者补出。

第一百零九页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

例3.6

（最大元素法）某公司进口一批商品，共有900万件。计划在A1港卸货100万件，A2港卸货400万件，A3港卸货400万件，然后再运往B1、B2、B3三个城市进行销售。已知三个城市的需要量分别为300万件、200万件、400万件。从港口运往各城市每万件销售利润由表3.37给出，问应如何因地制宜安排调运计划，才使总销售利润最多。

第一百一十页，共一百七十三页，2022年，8月28日表3.37例3.6销售利润表元/万件

城市港口B1B2B3A1700500480A2850700600A3400300500第一百一十一页，共一百七十三页，2022年，8月28日3.4运输问题应用案例解

本问题是求总销售利润最多的解，所以用最大元素法来进行研究。

首先说一下什么叫最大元素法。它与最小元素法的区别主要表现在：确定初始方案时将最小元素中的“小”字改为“大”字；用检验数判别方案时，若所有ij≤0，最优解已获得；若某个检验数ij＞0时，还要进行调整。ij＞0的经济意义是调整1个单位利润收入的增加值。现采用最大元素法进行求解。为此做一个产销矩阵表，如表3.38所示。

第一百一十二页，共一百七十三页，2022年，8月28日表3.38例3.6产销矩阵表（一）元/万件

城市港口

B1B2B3卸货量/万A1700×500(100)480(0)100A2850(300)700(100)600×400A3400×300×500(400)400需要量/万300200400第一百一十三页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

第一个应填“调运量”的格子为（A2，B1），因为它的销售收入850最大。因min（300，400）300，故填入300，此处未用“〇”圈上而用“（）”表示。它的经济意义，是从港口A2运到城市B1后销售收入最高，就尽可能多地优先安排调运。这只是一种局部观点，即还未在全局上进行考察和协调。第一百一十四页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

接着在B1城市其他收入处左下角空格打“×”，因为B1城市的需要已满足。以后的步骤不一一重述，初始方案安排如表3.38所示。第一百一十五页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

现在求检验数，方法同前。因为11c11（u1v1）700（0650）50＞0，其他各格没有正检验数。从（A1，B1）出发作闭回路，其转角点为（A1，B1）偶，（A2，B1）奇，（A2，B2）偶，（A1，B2）奇。奇数转角点的销售收入总和8505001350，而偶数转角点的销售收入总和7007001400。第一百一十六页，共一百七十三页，2022年，8月28日3.4运输问题应用案例因此当每个奇数的转角点上的计划数减少1万件时，总销售收入将减少1350元；而每个偶数转角点上的计划数增加1万件时，总销售收入将增加1400元。如作这种安排，总收入将增加50元，这正是1150的经济意义。于是上述回路上的调整量min（300,100）100，调整结果如表3.39所示。

第一百一十七页，共一百七十三页，2022年，8月28日表3.39例3.6产销矩阵表（二）元/万件

城市港口

B1B2B3卸货量/万A1700(100)500×480(0)100A2850(200)700(200)600×400A3400×300×500(400)400需要量/万300200400

第一百一十八页，共一百七十三页，2022年，8月28日3.4运输问题应用案例通过计算，发现在每个有“×”的格子里，它们的检验数都是负的，所以这是一个最优方案，即100A1→B1（表示由港口A1运到城市B1销售100万件，下同）200 200 400A2→

B1， A2→

B2， A3→

B3这种安排可获得最大的总收入为z（700×100）（850×200）（700×200）（500×400）58000（元）

第一百一十九页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

由于在变量个数相等的情况下，表上作业的计算远比单纯形法简单得多；所以在解决生产管理的实际问题时，人们常常尽可能把某些线性规划问题（表面上看来并不是运输问题）进行适当处理后转化为运输问题的数学模型，再用表上作业法来求解。下面我们举一个例子来说明。第一百二十页，共一百七十三页，2022年，8月28日3.4运输问题应用案例例3.7（生产计划问题）某造船厂按订货合同必须在当年每季度末分别提供15、30、20、25条同一类型的驳船。已知该厂每个季度的生产能力及生产每条驳船的成本如表3.40所示；又若生产出来的驳船当季度不交货，每条驳船积压一个季度需支出存储、维护等费用0.4万元。试问在完成合同的情况下，该厂的生产计划应任何安排，才能使全年的生产费用最少？最少费用为多少？第一百二十一页，共一百七十三页，2022年，8月28日表3.40例3.7数据表

季度一二三四生产能力/条30302518成本/万元2020.620.421第一百二十二页，共一百七十三页，2022年，8月28日3.4运输问题应用案例解

用运输问题的方法求解。把当年中的4个季度当成4个收点，收量就是每季度的需求量；每季度的生产当成一个发点，共有4个发点，发量分别为生产能力。4个季度的生产总能力303025181034个季度需求量总和1530202590第一百二十三页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

这是个供给量大于总需求量的运输问题，应虚设“库存”或“不生产”这个收点B，其收量1039013（条）。它的对应运费（这里应是单条驳船的生产成本）都等于0（它表示有能力生产，但实际上不需要生产的驳船数）。第一百二十四页，共一百七十三页，2022年，8月28日3.4运输问题应用案例

另外，在每个季度，生产供给需求的“单件运费”实际上也是单件的生产成本费。由于每季度的产量不能供应前面季度的需求（例如，第四季度的产量就不能满足第一至第三季