最优化理论运输问题

1、关于最优化理论运输问题现在学习的是第一页，共84页2第四章 运输问题4.1 运输问题的数学模型运输问题的数学模型 4.2 表上作业法表上作业法4.3 产销不平衡的运输问题产销不平衡的运输问题 4.4 运输问题应用举例运输问题应用举例现在学习的是第二页，共84页3n在经济建设中，经常遇到大宗物资的调运问题，如煤、在经济建设中，经常遇到大宗物资的调运问题，如煤、钢材、粮食等钢材、粮食等. 如果在我们考虑范围之内有若干个生产如果在我们考虑范围之内有若干个生产基地和若干消费地点，根据已有的交通网络，如何制定基地和若干消费地点，根据已有的交通网络，如何制定调运方案，使总的运费达到最小，这就是运输问题调运

2、方案，使总的运费达到最小，这就是运输问题.n运输问题是特殊的线性规划问题，故可以用单纯形法来运输问题是特殊的线性规划问题，故可以用单纯形法来求解，又因为它具有特殊性，因而它还具有比单纯形法求解，又因为它具有特殊性，因而它还具有比单纯形法更为简便的解法，这就是我们专门研究运输问题的目的更为简便的解法，这就是我们专门研究运输问题的目的.4.1 运输问题的数学模型运输问题的数学模型本节我们先引入运输问题的数学模型，然后讨论运输问题数学模型的本节我们先引入运输问题的数学模型，然后讨论运输问题数学模型的特点特点. 现在学习的是第三页，共84页4例例1 假设有三家工厂，都将产品运往三个不同的商店(如图)，

3、每家工厂每周的生产能力和每个商店每周的需求量如表4-1和表4-2所示. 工厂1工厂3工厂2商店1商店3商店2表4-1表4-2 工厂工厂1 2 3供应量（吨供应量（吨/周）周）50 70 20商店商店1 2 3需求需求量（吨量（吨/周）周）50 60 304.1.1 运输问题的数学模型运输问题的数学模型 先通过一个简单的例子来说明运输问题及其数学模型.现在学习的是第四页，共84页5显然，每周的供应总量与需求总量是相等的，即产销平衡，这可以用表4-3来表示，称为产销平衡表. 由于运货距离和运货公路的路况不同，各个工厂运往各商店物资的单位运输费用是不同的，单位费用如表4-4所示，称为单位运价表. 表

4、4-3 产销平衡表 单位：吨商店工厂123供应量150270320需求量506030现在学习的是第五页，共84页6商店工厂123供应量13235021058703131020需求量506030商店工厂12313232105831310表4-4 单位运价表 单位：元/吨当然，我们也可以将产销平衡表和单位运价表放在一个表中，如下表4-5所示.问如何确定调运方案，使总费用达到最小？现在学习的是第六页，共84页7解解 模型建立模型建立 决策变量决策变量 用双下标决策变量用双下标决策变量X Xijij表示从第表示从第i i （i=1i=1，2 2，3 3）家工厂运送到第）家工厂运送到第j j（j=1j=

5、1，2 2，3 3）家商店产品的数量。）家商店产品的数量。 目标函数目标函数 利用单位运价表和产销平衡表中的数据，我们希望总的运费利用单位运价表和产销平衡表中的数据，我们希望总的运费达到最小，即达到最小，即Min Z = Min Z = 由工厂由工厂1 1运出产品的总费用运出产品的总费用( 3X( 3X1111+ 2X+ 2X1212+ 3X+ 3X1313) ) + +由工厂由工厂2 2运出产品的总费用运出产品的总费用(10X(10X2121+ 5X+ 5X2222+ 8X+ 8X2323) ) + +由工厂由工厂3 3运出产品的总费用运出产品的总费用( X( X3131+ 3X+ 3X32

6、32+10X+10X3333) )写成表达式就是：写成表达式就是： 现在学习的是第七页，共84页8 对工厂对工厂1 1必须有必须有 X X1111+X+X1212+X+X1313 = 50 = 50 对工厂对工厂2 2必须有必须有 X X2121+X+X2222+X+X2323 = 70 = 70 对工厂对工厂3 3必须有必须有 X X3131+X+X3232+X+X3333 = 20 = 20 对商店对商店1 1必须有必须有 X X1111+X+X2121+X+X3131 = 50 = 50 对商店对商店2 2必须有必须有 X X1212+X+X2222+X+X3232 = 60 = 60

7、对商店对商店3 3必须有必须有 X X1313+X+X2323+X+X3333 = 30 = 30约束条件约束条件主要是对工厂的产量约束和商店的销量约束，由于主要是对工厂的产量约束和商店的销量约束，由于产量与销量相同，因而有：产量与销量相同，因而有：现在学习的是第八页，共84页9 于是，解此问题的线性最优化模型为：于是，解此问题的线性最优化模型为：Min Z = 3XMin Z = 3X1111+ 2X+ 2X1212+ 3X+ 3X13 13 + 10X+ 10X2121+ 5X+ 5X2222+ 8X+ 8X2323+X+X3131+3X+3X3232+10X+10X3333 X X111

8、1+X+X1212+X+X13 13 = 50 = 50 X X2121+X+X2222+X+X23 23 = 70 = 70 X X3131+X+X3232+X+X33 33 = 20 = 20 X X1111+ X+ X2121+ X+ X3131 = 50 = 50 X X1212+ X+ X2222+ X+ X3232 = 60 = 60 X X1313+ X+ X2323+ X+ X33 33 = 30 = 30 X Xijij0 i=10 i=1，2 2，3 j=13 j=1，2 2，3 3 s. t.上述模型显然是线性规划模型，我们可以使用线性规划的单纯形法对它进行求解. 但是，

9、当用单纯形法求解运输问题时，先得给每个约束条件中引入一个人工变量，这样模型的变量个数就会达到15个，求解是比较繁琐的，因而有必要寻求更简便的解法.现在学习的是第九页，共84页10运输问题的一般形式为： 已知有m个生产地点Ai， i=1，2，m，可供应某种物资，其供应量是ai， i=1，2，m. 有n个销地Bj，需求量是bj，j=1，2，n. 从Ai到Bj运送单位物资的运价为cij，i=1，2，m；j=1，2，n，问如何安排运输可使总运费最小？ 这是多个产地供应多个销地的单一物品运输问题，我们用Xij表示从产地Ai到销地Bj的运量，为直观起见，可以单独将Xij列出得该问题的运输表. 但我们也可以

10、将运输表和单位运价表、产销量放在一起，如下表4-6所示.为了说明适于求解运输问题的更好的解法，先看一下运输问题的一般描述及模型的一般形式. 现在学习的是第十页，共84页11 销地 产地B1 B2 Bn产量A1X11c11X12c12X1nc1na1A2X21c21X22c22X2nc2na2AmXm1cm1Xm2cm2Xmncmnam销量b1b2bn表中每格元素Xij代表运量，右上角元素 cij代表单位运价.现在学习的是第十一页，共84页12如果 ，就称此运输问题为非平衡运输问题，包含产大于销和销大于产两种情况，这我们将在第3节介绍。 下面我们只考虑产销平衡问题，产销平衡运输问题的一般模型为：

11、 ), 2 , 1;, 2 , 1(0), 2 , 1(), 2 , 1(.Min1111njmiXnjbXmiaXtsXcZijmijijnjiijminjijij在产销平衡条件下，可知njjmiiba11（4.2） njjmiiba11其中约束条件右端常数ai 和bj满足（4.2），在运输问题（4.3）中，目标函数要求运输总费用最小；前m个约束条件的意义是：由某一产地运往各个销地的物资数量之和等于该产地的产量；中间n个约束条件的意义是：由各产地运往某一销地的物资数量之和等于该销地的销量；后mn个约束条件是变量的非负条件. （4.3） 现在学习的是第十二页，共84页134.1.2 运输问题数

12、学模型的特点运输问题数学模型的特点 对于产销平衡运输问题（4.3），将其约束条件加以整理，可知其系数矩阵具有下述形式： 行行nmxxxxxxxxxmnmmnn111111111111111111212222111211（4.4） 由此可知，产销平衡运输问题数学模型有下述特点：现在学习的是第十三页，共84页14（1）约束条件中决策变量的系数等于0或1.（2）所有约束条件都是等式.（3）约束条件的系数矩阵中每一列有两个非零元素，对应于变量Xij的系数列向量Pij，其分量除第i个和第m+j个等于1以外，其余的均为零，即Pij=ei+em+j. 这对应于每一个变量在前m个约束方程中出现一次，在后n个约

13、束方程中也出现一次. （4）由于（4.2）成立，因而约束条件中m个约束方程并不是独立的，实际上只有个m+n-1方程是独立的，因而约束方程系数矩阵的秩为m+n-1.（5）运输问题（4.3）总存在基可行解，下节我们将给出找基可行解的方法. （6）运输问题存在有限最优解这是由于对运输问题（4.3），若令其变量则Xij就是该运输问题的一个可行解，其中 是总产量；另一方面，（4.3）的目标函数有下界，即目标函数不会趋向于负无穷，从而运输问题必存在有限最优解. njmiQbaXjiji, 2 , 1;, 2 , 1,/Q现在学习的是第十四页，共84页15例例2 某种物品先存放在两个仓库A1和A2中，再运往

14、三个使用地B1， B2和 B3，产销平衡表和单位运价表如下表4-7所示，试建立使总运费最小的运输问题数学模型. 使用地 仓库B1 B2 B3产量A134210A23534销量356解：设 表示从Ai运到Bj的物品数量，则由表中数据可知该问题的数学模型为： )3 , 2 , 1; 2 , 1(jixji3 , 2 , 1; 2 , 1, 0653410.353243min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZji现在学习的是第十五页，共84页16前面已经指出，运输问题是特殊的线性规划问题，可设想用单纯形法进行求解，

15、而单纯形法的基本思路是：先找出某个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，得到新的更好的解，然后继续验证和调整改进，直至得到最优解为止.为了按照上述思想求解运输问题，要求每步得到的解都必须是基可行解，因而解必须满足模型中所有约束条件，而且由运输问题的特点（4）知基变量的个数在迭代过程中始终保持为m+n-1个，同时基变量对应的约束方程组的系数列向量是线性无关的.在运输问题的数学模型中，每个解就代表一个运输方案，运输问题解的每一个分量，都唯一对应其运输表中的一个格. 若X是运输问题的一个基可行解，则将其基变量的值填入到运输表相应的格处（含填数字0的格），非基变量对应的格不填

16、数字. 现在学习的是第十六页，共84页17例如下表4-8表示例2的一个基可行解. 使用地 仓库B1 B2 B3供应量A133146210A234534需求量356表4-8有4个填有数字的格，它们对应4个基变量，两个空格对应2个非基变量. 可以验证，基可行解对应的约束方程组的系数列向量线性无关. 现在学习的是第十七页，共84页184.2 表上作业法表上作业法 由于运输问题具有特殊形式，因而我们可以在运输表中直接对问题求解，称为表上作业法. 表上作业法是单纯形法求解运输问题时的简化方法，其实质是单纯形法，它的步骤可归纳为：(1) 找出初始基可行解，即在m行n列产销平衡表上给出m+n-1个数字格.(

17、2) 求各非基变量的检验数，即在表上计算空格的检验数，并判别是否达到最优解，如果是最优解，停止；否则转下一步.(3) 确定换入变量和换出变量，找出新的基可行解，在表上进行调整.(4) 重复(2)(3)，直至得到最优解.表上作业法的步骤中，确定初始基可行解、判断是否达到最优解和确定换入换出变量并在表上进行调整是其中几个关键点. 下面我们依次来看. 现在学习的是第十八页，共84页194.2.1 确定初始基可行解确定初始基可行解 我们以一个例子来说明找初始基可行解的方法. 下表4-9表示某个运输问题的产销平衡表和单位运价表(二表合一).一般来说，找运输问题的初始基可行解主要有三种方法，即西北角法、最

18、小元素法和差值法（也叫伏格尔法），下面我们用上表4-9依次来说明. 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656现在学习的是第十九页，共84页201. 西北角法(1) 从图的西北角（即左上方）开始，在(A1,B1)格填入a1和b1中的较小值，这里填入较小值b1=3，即从A1运送3个单位物资到B1，此时的B1物资已经全部满足，划去B1列，如下表4-10所示. 销地产地B1B2B3B4产量A133113107A219284A3741059销量3656现在学习的是第二十页，共84页21（2）向a1,b1中较大数方向移动一格（或向右，或向下），这里是向右移动

19、一格，移动到(A1,B2)位置. B2需要6个单位物资，而A1只剩有4个单位，故在(A1,B2)处填4，A1的物资已经全部发完，划去A1行，如下表4-11所示. 销地产地B1B2B3B4产量A1334113107A219284A3741059销量3656现在学习的是第二十一页，共84页22（3）继续按照上述步骤进行，可知A2向B2运送2个单位物资，此时B2的物资已经满足，划去B2列. 销地产地B1B2B3B4产量A1334113107A2129284A3741059销量3656现在学习的是第二十二页，共84页23（4）继续按照上述步骤进行. 销地产地B1B2B3B4产量A1334113107A

20、21292284A3741059销量3656现在学习的是第二十三页，共84页24（5）继续进行. 销地产地B1B2B3B4产量A1334113107A21292284A37431059销量3656现在学习的是第二十四页，共84页25（6）继续进行. 最后在(A3,B4)处填入6，此时A3和B4的物资已经全部发送和接收完毕，因而同时划去A3行和B4列，如下表4-13所示. 销地产地B1B2B3B4产量A1334113107A21292284A374310659销量3656现在学习的是第二十五页，共84页26（7）得到初始方案，如下表4-14所示. 销地产地B1B2B3B4产量A133411310

21、7A21292284A374310659销量3656总运费 13565310222941133Z现在学习的是第二十六页，共84页272. 最小元素法用西北角法很容易得到初始基可行解，但得到的解往往离最优解相差甚远. 为了得到较好的初始基可行解，我们通常希望就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止，这种方法称为最小元素法. 我们仍以表4-9所示的运输问题来说明最小元素法. 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656现在学习的是第二十七页，共84页28（1）从表中最小单位运价开始确定运输方案，这里(A2

22、,B1)位置的1最小，因而A2优先供应物资到B1，根据的A2产量和B1的销量知，A2只能供应3个单位物资到B1，B1已经满足，划去B1列，如下表4-15所示. 销地产地B1B2B3B4产量A13113107A2319284A3741059销量3656现在学习的是第二十八页，共84页29（2）再从未划去的元素中找最小元素，并从该元素开始确定运输关系，这里(A2,B3)处2最小，故从此元素开始，即A2优先供应B3物资，A2只剩1个单位物资，从而A2只能供应1个单位物资到B3，A2物资已经发完，划去A2行，如下表4-16所示. 销地产地B1B2B3B4产量A13113107A23191284A374

23、1059销量3656现在学习的是第二十九页，共84页30（3）再从未划去的元素中找最小元素，并从该元素开始确定运输关系，这里(A1,B3)处3最小，故从此元素开始，即A1优先供应B3物资，根据A1的产量和B3的销量知A1供应4个单位物资到B3，B3物资已经满足，划去B3列，如下表所示. 销地产地B1B2B3B4产量A131143107A23191284A3741059销量3656现在学习的是第三十页，共84页31（4）再从未划去的元素中找最小元素，并从该元素开始确定运输关系，这里(A3,B2)处4最小，故从此元素开始，即A3优先供应B2物资6个单位，B2物资已经满足，划去B2列，如下表所示.

24、销地产地B1B2B3B4产量A131143107A23191284A37641059销量3656现在学习的是第三十一页，共84页32（5）再从未划去的元素中找最小元素，并从该元素开始确定运输关系，这里(A3,B4)处5最小，故从此元素开始，即A3优先供应B4物资3个单位，A3物资已经发完，划去A3行，如下表4-17所示. 销地产地B1B2B3B4产量A131143107A23191284A376410359销量3656现在学习的是第三十二页，共84页33（6）最后在(A1,B4)处填3，即A1供应B4物资3个单位，A1物资已经发完，划去A3行， B4物资全部满足，划去B4列，如下表所示. 销地

25、产地B1B2B3B4产量A1311433107A23191284A376410359销量3656现在学习的是第三十三页，共84页34（7）得到初始方案，如下表4-18所示. 销地产地B1B2B3B4产量A1311433107A23191284A376410359销量3656总运费 863564123131043Z现在学习的是第三十四页，共84页353. 差值法（伏格尔法）初看起来，最小元素法十分合理. 事实上，最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费，这是因为有时按某一最小单位运价优先安排物资运输时，却可能导致不得不采用运费很高的其它点对，从而使整个运输费用增加.

26、 伏格尔法考虑到，一个产地的产品假如不能按最小费用就近供应，就考虑次小费用，这样最小费用和次小费用就有一个差额，差额越大，说明不按最小费用调运时，运费增加越多，因而对差额最大处，就应当采用最小调运方案.基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的单位运价来确定运输关系，直到求出初始方案.现在学习的是第三十五页，共84页36 销地产地B1B2B3B4产量行差额A131131070A2192841A37410591销量3656列差额2513我们仍然考虑表4-9所示的运输问题，伏格尔法确定初始基可行解的步骤如下： （1

27、）先分别计算出各行和各列最小费用与次小费用的差额，称为行差额和列差额，并将行差额和列差额填入该表的最右列和最下行，如下表4-19所示.现在学习的是第三十六页，共84页37 销地产地B1B2B3B4产量行差额A131131070A2192841A376410591销量3656列差额2513（2）从行差额和列差额中选出最大者，选择它所在的行或列中的最小费用所在的格作为优先的运输关系.在这里行差额与列差额最大值为5，故选择5所在的列最小单位运价4为优先运输关系，即让A3优先供应物资到B2，根据产、销量知A3供应6个单位物资到B2，此时B2列已满足，划去B2列，得下表4-20. 现在学习的是第三十七页

28、，共84页38 销地产地B1B2B3B4产量行差额A131131070A2192841A3764103592销量3656列差额2513（3）计算剩余元素的行差额和列差额，选出最大者，选择它所在的行或列中的最小费用所在的格作为优先的运输关系. 在这里行差额与列差额最大值为B4列的3，故选择3所在的列最小单位运价5为优先运输关系，即让A3供应物资到B4，由剩余的产、销量知A3只能供应3个单位物资到B4，这时A3已经发货完毕，划去A3行，如表4-21所示. 现在学习的是第三十八页，共84页39（4）继续计算剩余元素的行差额和列差额，并按照上述步骤确定运输关系，经过若干步以后，最后填2到(A1,B4)

29、格，A1和B4的供应量和需求量都得到满足，此时同时划去A1行和B4列，可得初始方案 ，其余变量为0，如下表4-22所示. 销地产地B1B2B3B4产量A1311532107A23192184A376410359销量36563, 6, 1, 3, 2, 5343224211413xxxxxx总运费为 853564183121053Z现在学习的是第三十九页，共84页40从上述计算步骤可见，三种方法除了在确定供求关系的原则不同外，其余步骤是相同的. 表4-9所示的运输问题用三种方法得到的初始方案和总运费分别是：西北角法得到的初始方案是总运费为135；最小元素法得到初始方案为总运费是86；差值法的初始

30、方案是总运费85. 比较三种方法给出的初始基可行解，伏格尔法给出的解的目标函数值最小，最小元素法次之，西北角法给出的解的目标函数值最大. 一般来说，伏格尔法确定的初始基可行解更接近最优解，常用来作为运输问题的初始基可行解进行迭代 6, 6, 2, 2, 4, 3343323221211xxxxxx3, 6, 1, 3, 3, 4343223211413xxxxxx3, 6, 1, 3, 2, 5343224211413xxxxxx现在学习的是第四十页，共84页41需要注意的是三种方法给出的初始方案都是运输问题的基可行解，这是因为：（1）在产销平衡表上，选择表中某一元素以后，要比较产量和销量，当

31、产大于销，划去该元素所在列；当产小于销，划去该元素所在行，然后在未划去的元素中继续选另一元素.表中共有m行n列，总共可划条m+n直线，但当表中只剩一个元素时，同时划去一行和一列. 因而表中共填了m+n-1个数字，即给出了m+n-1个基变量的值. 注：选择表中某一个元素后，有可能同时划去一行和一列，这就出现退化，退化的处理我们在后文中讲述.（2）这m+n-1个基变量对应的系数列向量是线性独立的. 这是因为若表中确定了某一个基变量 以后，它对应的系数列向量 ，给定 的值以后，将划去第i行或第j列，即其后的系数列向量中不再出现 或 ，因而 不可能用其它向量的线性组合表示. 所以这m+n-1个基变量对

32、应的系数列向量是线性独立的. jixjmijieePiejmejiPjix现在学习的是第四十一页，共84页424.2.2解的最优性检验及改进解的最优性检验及改进 前面三种方法可以很容易找出运输问题的初始基可行解，但初始基可行解未必是最优解.按照表上作业法的步骤，给出初始基可行解后，还要计算各非基变量的检验数，即在表上计算各空格的检验数，以判别基可行解是否达到最优. 由于运输问题的目标函数是要求实现最小化，因而所有的检验数大于等于零时基可行解为最优解. 判别初始基可行解是否为最优解一般有两种常用方法：闭回路法和位势法，下面我们依次来介绍. 1. 闭回路法闭回路方法是在初始调运方案表中，从任意空格

33、出发，沿着纵向或横向行进，遇到适当填有数据的方格后90度转弯，继续行进，总能回到原来空格，这个封闭的曲线称为闭回路. 可以证明每个空格都对应着唯一的闭回路. 现在学习的是第四十二页，共84页43 销地产地B1B2B3B4产量A1311433107A23191284A376410359销量3656现在学习的是第四十三页，共84页44 销地产地B1B2B3B4产量A1311433107A23191284A376410359销量3656现在学习的是第四十四页，共84页45 销地产地B1B2B3B4产量A1311433107A23191284A376410359销量3656现在学习的是第四十五页，共8

34、4页46下面我们看用闭回路法计算非基变量（空格点）检验数的计算方法. 首先考虑表4-23的空格点(A1,B1), 假设产地A1运送1个单位的物资到销地B1，为使运入销地B1物资的数量等于它的销量，就应当将原来A2运送到的B1物资数量减去1个单位，即将(A2,B1)格的3变为2；另一方面，为使运出产地A2物资的数量等于它的产量，就应当将原来(A2,B3)格的数1加上1，再考虑B3知应将(A1,B3)格的4变为3，从而得到一个新的运输方法. 显然这样的调整将影响到空格(A1,B1)闭回路上的各个数据. 按照上述假设，如果由产地A1运送1个单位的物资到销地B1，由此引起的总费用变化是 ，即总费用增加

35、1. 按照检验数的定义知它正是非基变量 （即空格(A1,B1)）的检验数. 同理按空格(A1,B2)的闭回路知它的检验数为 ，空格(A3,B1)的检验数为10. 1123321231311cccc11x245101132341412cccc现在学习的是第四十六页，共84页47 销地产地B1B2B3B4产量A131143310712A231912841-1A3764103591012销量3656 现在学习的是第四十七页，共84页48由于运输问题的目标函数是要求实现最小化，因而对该问题的某个基可行解，如果所有空格的检验数中没有负值，则该基可行解就是最优解；如果某个空格处出现负检验数，表明调运方案不

36、是最优解，这时就要进行调解. 和单纯形法类似，当有两个和两个以上空格的检验数为负时，一般选其中最小的负检验数，以它对应的空格作为调入格，即该空格对应的变量为进基变量. 在进基变量的回路中，比较奇数拐角点的运量，为了使新得到的解仍为基可行解，应当选择一个具有最小运量的基变量作为出基变量，并使调整的运量为各个奇数拐角点运量的最小值. 在表4-26中，只有空格(A2,B4)处的检验数为负，因而它对应的变量 为进基变量，它的闭回路如表4-27所示.24x现在学习的是第四十八页，共84页49 销地产地B1B2B3B4产量A1311433107A23191284A376410359销量3656奇数拐点处运

37、量的最小值为1, 因而为了保持平衡，将奇数拐点处的运量减去1，偶数拐点处的运量加1，调整后的运输方案如下表4-28所示. 现在学习的是第四十九页，共84页50 销地产地B1B2B3B4产量A1311532107A23192184A376410359销量3656调整以后，再计算各个空格的检验数，如果所有的检验数均大于等于零，则这个运输方案就是最优解；如果还有某个空格的检验数为负数，则再以这个空格为调入格，作相应的基变换，直到所有的检验数为非负. 上述表中得到的所有的检验数为非负，因而此运输方案是最优方案. 现在学习的是第五十页，共84页512. 位势法位势法 在闭回路法中，为了计算一个空格点处的

38、检验数，就要画出该空格的闭回路，当空格点较多时，计算很繁. 位势法是另一种计算每个空格检验数的方法，这个方法比闭回路法更加简洁.现在学习的是第五十一页，共84页52位势法的基本思想是： 设一组新的变量ui和vj(i=1,2,m;j=1,2,n)是对应运输问题的m+n个约束条件的对偶变量，B是原问题的初始基矩阵，则由单纯形法知而每个决策变量 的系数向量 ，所以有 ，于是检验数 由于基变量的检验数始终为0，因而对于基变量，始终有 ，所以我们可以根据基变量对应的单位运输费用算出所有ui与vj的值，再根据ui与vj的值算出非基变量的检验数。),(21211nmBvvvuuuBCjmiijeePjiij

39、BvuPBC1)(1jiijijBijijvucPBCcBjivucjiij,0)(jix现在学习的是第五十二页，共84页53例如在表4-9所表示的运输问题中，用最小元素法得到的初始调运方案如下表所示. 销地产地B1B2B3B4uiA131143310u1A2319128u2A37641035u3vjv1v2v3v4在此调运方案中，我们可以根据基变量对应的单位运输费用cij算出ui和vj .计算方程组是： . 5; 4; 2; 1;10; 3432332124131vuvuvuvuvuvu现在学习的是第五十三页，共84页54 销地产地B1B2B3B4uiA1311433100A2319128-

40、1A37641035-5vj29310该方程组含6个方程和7个未知数，因而有一个未知数是自由变量，通常我们令u1=0，此时可得到所有ui(i=1,2,m)和vj(j=1,2,n)的值，如下表4-29所示. 现在学习的是第五十四页，共84页55根据ui和vj的值算出所有空格处（即非基变量）的检验数，计算公式为cij-(ui+vj)，计算结果如下表4-30方括号数字所示，这和用闭回路法得到的检验数结果一致. 销地产地B1B2B3B4uiA131143310012A2319128-11-1A37641035-51012vj29310因为检验数 ，故这个解不是最优解，因此我们再根据闭回路法进行调整，直

41、至得出最优解. 0124现在学习的是第五十五页，共84页56表上作业法在计算中可能还会出现一些问题，这里我们需要说明.1. 当迭代到运输问题的最优解时，如果有某个非基变量的检验数等于零，则说明该运输问题有无穷多最优解.2. 退化 (1) 当确定供需关系时，如果某个产地的剩余产量等于某个销地的需量，这时就要划去一行和一列，此时需要添加一个0，它的位置可在对应划去的那行或那列的任意处. (2) 在用闭回路法调整时，如果闭回路奇数拐弯处具有两个或两个以上相等的最小值，此时经调整后，得到退化解，这时有一个数字格必须填0，以表示它是基变量. 现在学习的是第五十六页，共84页574.3产销不平衡的运输问题

42、产销不平衡的运输问题 上一节讲到运输问题的表上作业法，是以总产量等于总销量（即产销平衡）为前提的. 实际上，在很多运输问题中，总产量并不等于总销量. 为了使用表上作业法求解，我们可以将产销不平衡的运输问题转化为产销平衡运输问题.如果总产量大于总销量，即njjmiiba11这时运输问题的数学模型为： ), 2 , 1;, 2 , 1(. 0), 2 , 1(,), 2 , 1(,.min1111njmixnjbxmiaxtsxcZjimijjinjijiminjjiji（4.5） 现在学习的是第五十七页，共84页58由于总产量大于总销量，因而要考虑多余物资就地贮存的问题. 为借助产销平衡运输问题

43、的表上作业法，可增加一个假想的销地Bn+1，由各产地Ai(i=1,2,m)运送到这个销地Bn+1物资的数量设为 ，实际上就是产地Ai就地贮存物资的数量，显然单位运价 . 因此假想后原问题的最优总费用与假想之前的最优总费用是一致的. 由于总产量剩余为使产销平衡，可假设销地Bn+1的销量此时模型（4.5）可以变为： 1, nixmicni, 2 , 1, 01, njjmiiba11njjmiinbab111) 1, 2 , 1;, 2 , 1(. 0) 1, 2 , 1(,), 2 , 1(,.min111111njmixnjbxmiaxtsxcZjimijjinjijiminjjiji（4.6

44、） 现在学习的是第五十八页，共84页59 销地 产地B1 B2 BnBn+1产量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2AmXm1cm1Xm2cm2XmncmnXm，n+10am销量b1b2bn可以看出，模型（4.6）是有m个产地，n+1个销地的产销平衡运输问题，因而通过假想销地，可将产大于销的运输问题转化为产销平衡运输问题. 和模型（4.6）对应的运输表如下表所示. njjmiiba11现在学习的是第五十九页，共84页60如果总销量大于总产量，即可仿照产大于销的操作过程，增加一个假想的产地Am+1，它的产量为由于这个

45、假想的产地并不存在，求出的由它发往各个销地的物资数量 实际上是各销地所需物资的欠缺额，这部分物资的运输并未发生，因而单位运价 . 这样也可以将原问题化为产销平衡运输问题.miinjjab11miinjjmaba111), 2 , 1(, 1njxjm), 2 , 1(0, 1njcjm现在学习的是第六十页，共84页61例例3 某市有三个造纸厂A1，A2，A3和四个批发用户B1，B2，B3，B4，各造纸厂纸的产量、各批发用户的需求量及各造纸厂到各批发用户的单位运价如下表4-32所示，试确定运输总费用最小的调运方案. 批发用户造纸厂B1B2B3B4产量A1312348A2112595A367159

46、需求量4356现在学习的是第六十一页，共84页62解解 由于该问题中总产量为22，总销量为18，因而该问题是总产量大于总销量的产销不平衡运输问题. 按照模型（4.5）的分析知，增加一个假想销地B5，其需求量为22-18=4，可将该问题表示的运输问题转化为下表4-33所示的产销平衡运输问题. 用户造纸厂B1B2B3B4B5产量A13123408A21125905A3671509需求量435622-18=4根据表上作业法，可得该问题的最优运输方案如下表4-34所示 现在学习的是第六十二页，共84页63用户造纸厂B1B2B3B4B5产量A1431234408A2113259205A367512520

47、9销量435622-18=4在以上讨论中，我们都假定物资由产地直接运送到销售目的地，不经过中间转运. 在实际问题中，还会遇到将物资运到某个中间转运站（包括产地、销地或中间转运仓库），然后再运往销售目的地的情况. 有时经转运比直接运往目的地更为经济，在决定运输方案时有必要将转运也考虑进去. 当然考虑转运将使问题变得复杂，有兴趣的读者可以参阅相关文献. 现在学习的是第六十三页，共84页64 下面我们通过几个例子介绍运输问题的一些实际应用.例例4 设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区试用效果相同. 各化肥厂年产量、各地区年需求量（单位：万吨）及从各化肥厂到各地区运送单位化肥

48、的单位运价（单位：万元/万吨）如表4-35所示，试给出总运费最小的化肥调拨方案. 4.4运输问题应用举例运输问题应用举例 现在学习的是第六十四页，共84页65 需求地区化肥厂产量1161322175021413191560319202350最低需求最高需求3050707003010不限解解 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求不限，但根据现有产量，第个地区每年最多能分配到60万吨，因而最高需求为210万吨，大于总产量. 为了求得平衡，在产销表中增加一个假想的化肥厂4，其年产量为50万吨. 现在学习的是第六十五页，共84页66各地区的需求量包

49、含最低需求和额外需求两部分. 如地区，其中30万吨是最低需求，故不能由假想化肥厂供给，因而令假想化肥厂4到地区的单位运价为M（M为任意大的数），而额外需求20万吨对地区来说可以满足，也可以不满足，因此额外需求可以由假想化肥厂4供给，而且相应的运价为0. 事实上，对凡是需求分两种情况的地区，我们按照两个地区看待，这样可将原问题转化为产销平衡运输问题，其产销平衡表与单位运价表如下表4-36所示. 现在学习的是第六十六页，共84页67需求地区化肥厂产量116161322171750214141319151560319192023MM504M0M0M050需求量302070301050根据表上作业法进

50、行计算，可以求得最优方案如下表4-37所示. 现在学习的是第六十七页，共84页68需求地区化肥厂产量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050从表4-37可以看出，地区满足最高需求量50万吨，地区没有接收到任何物资，只满足最低需求0，而地区满足了40万吨现在学习的是第六十八页，共84页69 使用者产地产量124321563324使用量1046例例5 设有三个产地生产同一种产品并供应给三个使用者，各产地到各使用者的单位运价及使用者的需求量如下表4-38所示. 由于销售需要

51、及客观条件的限制，产地1至少要发出6个单位的产品，它最多只能生产11个单位的产品；产地2的产量为7个单位；产地3至少要发出4个单位的产品，试根据上述条件用表上作业法求该运输问题的最优调运方案. 43a72a现在学习的是第六十九页，共84页70使用者产地产量1243M61243052156M73324M4332403使用量10465解解 由表4-38可知，若产地1、2的产量按最小值计算，在产销平衡条件下，产地3的产量最多等于7. 用类似于例4的方法，可将原问题表示成下表4-39所示的产销平衡运输问题.由表4-39求解该产销平衡运输问题解的过程及结果请读者自己完成. 现在学习的是第七十页，共84页

52、71 销地产地产量112220214540323330销量302020例例6 三个产地欲将同一种物资运送到三个销地，各产地产量、各销地销量以及各产地运送物资到各销地的单位运价如下表4-40所示. 若各产地有物资没有运出，就发生存储费用，假设三个产地单位物资存储费分别为4,4,3；产地2的物资最多运出35个单位，产地3的物资至少运出28个单位，试给出使总运输费用最小的运输方案.现在学习的是第七十一页，共84页72解解 这是一个有存储形式的产销不平衡运输问题.为使问题化为无存储费用的产销平衡运输问题，可将产地1,2,3设想为三个销地,，考虑到物资存储的费用，可将单位存储费按单位运价来表示. 如产地

53、1到销地（即产地1）的单位运输费用为4，产地1不能运送物资到产地2（即销地），因而产地1到销地的单位运输费用为M（M任意大）. 又由于产地2的物资最多运出35个单位，因而产地2至少存储5个单位物资，即销地的需求量至少为5个单位，同理销地需求量至多为2个单位，为保持运输平衡，销地的需求量是015之间使产销平衡的值，因而原问题转化为下表4-41所示的产销平衡运输问题.现在学习的是第七十二页，共84页73销地产地产量11224MM202145M4M403233MM330销量30202001552表4-41现在学习的是第七十三页，共84页74销地产地产量181212204MM20222145M184M

54、403220383MM2330销量30202001552通过表上作业法可得该问题的最优方案如下表4-42所示，总费用为216. 现在学习的是第七十四页，共84页75例例7 某工厂根据合同，要在下一年每个季度末向销售公司提供某种产品，该工厂的生产能力、生产成本以及销售公司的需求量如下4-43表所示季度生产能力 （吨）生产成本 （万元/吨）需求量（吨）123430402010151415.314.820203010jajjd若当季生产的产品过多，就要进行储存，已知每季度储存每吨产品需0.2万元，试给出该厂在完成合同的情况下的最佳生产方案，使全年的生产费用最低.我们已经知道，运输问题是线性规划问题的特殊形式，由于在变量个数相等的情况下，运输问题表上作业法的计算远比单纯形法简单得多，所以在解决实际问题时，人们常常尽可能将某些线性规划问题转化为运输问题的数学模型. 下面我们看一个具体例子. 现在学习的是第七十五页，共84页76解解 这个问题在第二章例15解法2中已给出了线性规划模型，设第i季度生产而用于第j季度交货的产品数量为 吨，则原问题的数学模型为：ijx在这里，我们可以将其化为产销平衡运输问题，从而简化