5.运筹学之运输问题(胡运权版)

第六章 运输问题

运输问题依然属于线性规划问题的范畴，但是由于其约束方程组的系数矩阵具有特殊的结构，因而可以找到一种比单纯形表更简便的求解方法，正是基于此，运输问题从线性规划中单列出来进行讨论。本章分为两大部分，前三节介绍求运输问题单纯形方法——表上作业法，第四节重点介绍运用EXCEL电子表格模型解决运输问题。

§1 运输问题的模型与性质

1.1运输问题模型

运输问题的一般提法是这样的：某种物资有若干个产地和销地，若已知各个产地的产量、各个销地的销量以及各产地到各销地的单位运价（或运输距离）。问应如何组织调运，才能使总运费（或总的运输量）最省？

将此问题更具体化，假定有m个产地，n个销地，

ai——第i产地的供应量，i=1，2，„，m。

bj——第j销地的需求量，j=1，2，„，n。

i=1， cij——从产地i到销地j的单位运费，2，„，2，„，m，j=1，

n。

xij——产地i到销地j的调运数量。

则该问题为求解最佳调运方案，即求解所有xij的值，使总的运输

费用

cx

i1j1

mn

ijij

达到最少。决策变量为xij。

该问题的数学模型形式为： minz s..t

cx

i1j1

mn

ijij

x

i1

m

ij

bj， j=1，2，„，n。

xij ai ， i=1，2，„，m。

j1

n

xij0 ，对所有的i，j。

根据该问题中总需求量ai与总供应量bj的关系，可将运输问

i1

mn

j1

题分为两类： 1、当ai =

i1mm

b

j1n

n

j

时，为平衡型运输问题；

2、当ai ≠ bj 时，为不平衡型运输问题。

i1

j1

实际上不平衡型运输问题可以转换为平衡型运输问题，我们首

先讨论平衡型运输问题，在§3中介绍不平衡型向平衡型的转换。

平衡型运输问题的数学模型形式可表示为： minz s..t

cx

i1j1

mn

ijij

x

i1

m

ij

= bj， j=1，2，„，n。

xij = ai， i=1，2，„，m。

j1

n

xij0 ，对所有的i，j

该模型包含有mn个变量，mn个约束方程，其系数矩阵A如

下：

x11x12x1n x21x22xn 2„ „ xm1xm2xmn

111 

1

11    11 A  1 1 1 1 1 1

  

 1 1 A中对应于变量xij的系数向量Piij，其分量除第个和第mj个为

1

外，其余部分全为0，表示为：

T

Pij0110eiemj

例1 A1、A2两煤矿产的煤运往B1、B2、B3三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表。试列出其数学规划模型。

表6-1 单位运价表 解 设xij为第i煤矿向第j城市的煤的供应量，cij表示第i煤矿向第j城市供应煤的单位运费。i=1，2；j=1，2，3。

此题供应总量与需求总量相等，为平衡型的运输问题。列出模型如下：

minz90x1170x1295x1380x2165x2275x23

x11x12x13200x21x22x23230

s..t x11x21100

x12x22150x13x23180

xij0, i1,2;j1,2,3.

1.2 运输问题的基本概念与性质

本小节介绍运输问题的主要性质和概念，这些性质将有助于§2中运输问题的求解。

显然，当供应总量等于需求总量时，运输问题有可行解，且有最优解。并且，当供应量和需求量均为整数时，必存在决策变量均为整数的最优解。

运输问题的方程总数为mn个，对于平衡型的运输问题，当确定其中的mn1个方程后，剩下的一个方程也就确定了，因而，平衡型运输问题的基变量共有m+n-1个。如在例1中，基变量的个数为2+3-1=4。

一个变量组若能连成如下的形式，我们就称该变量组构成闭回路。

其实闭回路就是一条封闭折线，每个顶点都是转角点。 设m4,n4,将变量组{x21,x11,x12,x42,x44,x14,x13,x23}表示如下：

显然，该变量组形成一闭回路。易得知形成闭回路的变量组对应的列向量是线性相关的。例如，如果变量组包含四个变量

xi1j1,xi1j2,xi2j2,xi2j1形成图6-1中（1）的闭回路，相应的列向量满足：

pi1j1pi1j2pi2j2pi2j10

即pij,pij,pij,pij线性相关。事实上，我们有：

11

12

22

21

运输问题m+n-1个变量构成基变量的充要条件是不含闭回路。相应的，从一个非基变量出发，存在且唯一存在一条闭回路。

§2 表上作业法求解运输问题

表上作业法是求解运输问题的主要方法，它的实质是单纯形法在

求解运输问题时的一种简化方法，归根结底，表上作业法还是属于单纯形法，也称为是运输单纯形法，因而它具有与单纯形法相同的求解思想。如下图：

根据这个思路，首先讨论初始基可行解的确定问题，然后再讨论解的改进问题。

2.1 初始基可行解的确定

求解运输问题的初始基可行解的基本步骤如下：

1、在产销平衡表中选一个单元xij，令xijminai,bj，即Ai尽量满足Bj的需求，使一个约束方程得到满足，将xij的值填入表中相应位置；

2、从ai和bj中分别减去xij的值，即Ai在尽可能满足Bj的需求后，调整Ai供给量和Bj需求量；

3、若ai0，则划去对应行（Ai产品全部供给完），若bj0，则划去对应列（Bj需求全部满足），注意每次只能划去一行或是一列（即只去掉一个约束）。

4、若产销平衡表中所有的行或列均被划去，则结束。否则，在剩下的产销平衡表中选下一个变量，转2的步骤继续进行。

最终产生的一组变量将满足下面的条件： a、所有的变量xij非负，且变量总数为mn1； b、所有的约束均得到满足； c、所有的变量xij不构成闭回路。

这里介绍两种常见的确定基可行解的方法：西北角法和最小元素法。其实它们的区别就是在于xij的选取方法上。

一、西北角法

也称为左上角法，每次选取的xij，都是左上角第一个元素，也就是说，优先安排运价表上编号最小的产地和销地之间的运输业务。该方法的特点是xij选取方便，因而算法简单易实现。

例2 用西北角法求解例1的初始调运方案。

解 第一步，从表6-2中选取西北角的元素x11，取x11mina1,b1100，意即A1煤矿尽可能满足B1城市的需求量100，此时B1达到全部需求后，需求量修改为b11001000，A1的供给量第一次修改为

a1200100100。划去第1列；

第二步，重复第一步，选取剩下的表中西北角的元素x12，取

意即A1煤矿尽可能满足B2城市的需求量，此时A1x12mina1,b2100，

已供给完所有的煤，供给量第二次修改为a11001000，B2未满足全部需求，需求量修改为b215010050。划去第1行；

第三步，重复前面的步骤，选取剩下表中西北角的元素x22，取意即A2煤矿尽可能满足B2城市的需求量，此时B2x22mina2,b250，

获得全部需求，需求量第二次修改为b250500，A2供给量第一次修改为a223050180。划去第2列；

第四步，重复前面的步骤，选取剩下表中西北角的元素x23，取

x23mina2,b3180，该问题是平衡型运输问题，所以最后A2煤矿的







供给量刚好达到B3城市的需求量，a2和b3均修改为0。此时划去第2行或划去第3列均可。

表6-2 产销平衡表

第二步

第四步

第一步 第三步

至此产销平衡表中所有的行或列均被划去。由表6-2可得，初始基可行解为：x11100,x12100,x2250,x23180,x13x210.

二、最小元素法

西北角法唯一的优点就是简单易实现，但是从例2可看出，在用西北角法求解初始基可行解时，完全没有考虑运费的因素，也许优先满足需求的西北角上的元素运费是最大的。最小元素法正是从运费上

考虑，希望能优先安排单位运价最小的产地与销地之间的运输业务，从而实现“就近供应”。

例3 用最小元素法求解例1的初始调运方案。 解 见表6-3和表6-4

表6-3 单位运价表

表6-4 产销平衡表

第四步

第二步

第三步 第一步

第一步，在表6-3中选取单位运价最小的c22=65，对应的变量为

x22。在表6-4中，取x22mina2,b2150，此时B2需求量修改为

b21501500。A2供给量第修改为a223015080。划去表6-3和

表6-4中第2列；

第二步，在表6-3中选取剩下的单位运价最小的c23=75，对应的变量为x23，在表6-4 中取x23mina2,b380，此时B3需求量修改为



b318080100，A2供给量第二次修改为a20。划去表6-3和表6-4

中第2行；

第三步，在表6-3中选取剩下的单位运价最小的c11=90，对应的变量为x11， 在表6-4 中取x11mina1,b1100，此时B1的需求量修改为b10，A1的供给量第一次修改为a1200100100。划去表6-3和表6-4中第1列；

第四步， 在表6-3中此时只剩c13=95，对应变量为x13，在表6-4中，取

x13mina1,b3100，最终A1的供给量第二次修改值a1和B3的需求量



第二次修改值b1均为0。划去第1行或第3列均可。

由表6-4可得，初始基可行解为：

x11100,x13100,x22150,x2380,x12x210.

三、两种特殊情况

以上两种方法求解初始基可行解时，均会遇到一些特殊情况，一般称为是“退化”。总的来说，退化有以下两种情况：

1、当选定元素xij后发现该元素所在行的产量等于所在列的销量，这样，修改后的产量和销量均为0，此时只能划去一行或是一列，不能同时划去。

2、当选定元素xij后，发现对应供给量ai和需求量bj均为0，那么xij=min{ai，bj}=0，此时仍应把xij作为基变量，把0值填入相应表中（基变量取0值退化）。

2.2 最优性检验

所求得的基可行解均要经过最优性检验，以判定该解是否为最优解（也就是最终选择的方案）。表上作业法的最优性检验是对检验数

cijCBB1P,,m;j1,,n进行判别。运输问题的目标函数要求实ij, i1

现最小化，因而，当所有的cijCBB1Pij0时，所得的解为最优解，否则还要进行解的改进。下面介绍两种常用的最优性判别方法。

一、闭回路法

一般称基变量在产销平衡表中所对应的格为数字格，非基变量值均为0，对应格为空格。

闭回路法是通过在调运方案的计算表上，从每一空格出发，以水平的或是垂直的直线向前划，每碰到数字格就转90度后，继续前进，直到回到起点为止。以§2.1中的表6-2为例，x11,x12,x22,x23为基变量，

x21和x13为非基变量。从空格x21（非基变量）出发，经数字格x11,x12,x22

回到起点，形成回路，如下图：

图6-4

考察这个初始方案，x210表示A2煤矿的煤没有运往B1城市，现若想改变初始方案，把A2的煤运送一单位给B1，那么，为了保持平衡，就必须使x11减少1单位、x12增加一单位以及x22减少一单位。上述调整是为了使总的运输数量达到平衡，但是会造成总的运输费用上的改

变。

总运输费用改变量=8019017016515。

也就是说，当改变运输方案，使A2运一单位的煤到B1时，会使总的运输费用减少5元。此总运输费用改变量5即为检验数。 同法可求得另一非基变量x13的检验数为15，增加x13的值总运输费用改变量增加15元。

因而可通过增加非基变量x21的值寻求更优方案。实际上，x21就是在单纯型表里进行迭 代时的入基变量。

闭回路法的原理就是通过寻找闭回路来计算非基变量的检验数，再对检验数判断是否找到最优解。而从每一空格出发一定存在唯一的闭回路。

二、位势法

当产销点过多时，采用闭回路法就很繁琐，这时一般采用位势法。位势法又称v—V法，它是由解运输问题的对偶问题而来的。平衡运输问题的对偶问题为

maxgaiuibjvj

i1

j1

m

n

tuivjcij s..

i1,,m;j1,n.

这里对偶模型里的变量uii1,,m与m个供应约束相对应，变量

vjj1,,n与n个需求约束相对应。ui和vj称为变量xij的位势。由于

原问题是等式约束，因而对偶变量ui和vj的符号无限制。

根据对偶理论，有CBB1u1,u2,,um,v1,v2,,vn， 而决策变量xij的系数向量Pijeiemj，

所以，CBB1Pijuivj，从而cijCBBPijcijuivj。这是一

种通过位势求检验数的方法。

单纯形法所有基变量的检验数为0，所以对于基变量xij有 cijuivj0，即uivjcij。

平衡型运输问题基变量的个数有mn1个，因而象uivjcij这样的方程有mn1个。这组方程中包含有mn个未知的对偶变量ui和

vj，所以其中必存在一个自由未知量，假定为u1，并取u10（这样做

并不影响结果），从而可以计算出所有其他的对偶变量的值。再根据对偶变量的值计算非基变量的检验数，并进行判断。

综上所述，位势法的判定步骤如下：

1、根据初始基可行解列出关于对偶变量的方程组（共有mn1个方程）

ui1vj1ci1j1

ui2vj2ci2j2



uimn1vjmn1cimn1jmn1

2、令u10，求得所有对偶变量ui和vj的值；

3、将ui和vj的值代入cijuivj，求的所有非基变量的检验数，若存在非基变量的检验数为负，则该非基变量的增大可以使解更优。

下面以西北角法求得的初始基可行解

x11100,x12100,x2250,x23180,x13x210.为例，

根据基变量x11,x12,x22,x23给出对偶变量方程组为：

u1v190u1v270u2v265u2v375

令u10，求得u10,u25,v190,v270,v380。代入cijuivj求得非基变量x13和x21的检验数分别为c13u1v315和c21u2v15，意即非基变量x21的增加能使方案更优，在进行解的改进的时候，选取它为入基变量。可以看到，此法求得的结果与闭回路法一致。

2.3 解的改进

前面一小节介绍了如何判断所求的基可行解是否为最优解，当经过判断所求解非最优解时，尚需对解进行改进，这就涉及到入基和出基的问题，本小节对此进行介绍。

运输问题最常用的解的改进方法为闭回路调整法。其基本思想是，选取检验数为负的所有非基变量中的最小者作为入基变量，以对应空格为出发点画出闭回路，在经过的数字格中选择（-1）的最小者，对应的基变量为出基变量，然后对数据进行调整。

我们依然在前面几小节中计算的数据上进行说明。根据西北角法计算的初始基可行解为x11100,x12100,x2250,x23180,x13x210，求得非基变量x13和x21的检验数分别为15和-5，此时只有x21的检验数不满足非负，取其为入基变量，以对应的空格引出闭回路如下：

表6-5 产销平衡表

选取闭回路上具有（-1）的数字格中最小者，min100,180100（其原理与单纯形法中由确定出基变量相同）。然后在闭回路上按照+、号分别加上和减去值，即x13100,x12100,x22100,x23100，得到如下表

表6-6 产销平衡表

得到新一

1x50,23

轮基可

行解为

x11100x,1310x02,2

x802x,。 1

采用闭回路法或位势法计算该基可行解的非基变量x12和x21的检验数分别为-15和10，从而确定x12为换入变量。

重复上述步骤，直至求得最终数据如下： 表6-7 产销平衡表

在计算过程中需要注意的是，可能会出现非基变量（空格）的检验数为0的情况，这时，该产销平衡的运输问题存在有无穷多最优解。在已求得一个最优解的表格中，以这样的空格出发做闭回路重新进行调整，可以得到另一个最优解。

2.4 其它运输问题的处理

一、 不平衡型运输问题

在§1给出的运输问题的一般模型中，当

a ≠ b

ii1

mn

j

时，该

j1

问题为不平衡型运输问题。不平衡型运输问题有产大于销和销大于产两种情况，下面讨论其中一种情况，另一种情况类似推出。

对于产量大于销量的运输问题，有aibj，模型形式为：

i1

j1

m

n

minzcijxij

i1j1

m



 xijbj, j1,2,n.

1

i n

s..t xijai, i1,2,m.

j1

 x0, 对所有的i，j.

ij



mn

虚拟一个销地Bn1，Bn1的需求量bn1为总产量与总销量之差，即单位运费cin10(i1,,m)，这样原问题转化为有m个bn1aibj，

i1

j1

m

n

产地和n1个销地的平衡型运输问题，剩下的工作就是求解一个平衡型运输问题了。

销量大于产量的情况可以类似的虚拟一个产地。

二、转运问题

前述运输问题产地与销地的界线非常分明，产地只供给（输出）货物，销地只需求（输入）货物，而实际上，绝对的输出与输入几乎是不存在的，最多存在的是产地又是销地的情形，甚至有时一地仅作为其他两地之间输入输出的中转站，象这些类型的运输问题，我们称为转运问题。

转运问题的解题思路是先将其转化为平衡型运输问题，再按表上

作业法求解，这一点和不平衡型运输问题是一样的。我们来看一下转运问题在这个转化中一些假定：

1、求最大可能中转量Q（Q为大于总产量ai的一个数）；

i1m

2、纯中转站视为输入量和输出量均为Q的一个产地和销地； 3、兼中转站的产地Ai视为输入量为Q的销地和输出量为Qai的产地；

4、兼中转站的销地Bj视为输出量为Q的产地和输入量为Qbj的销地。

转化按照上述假设来完成，重新画出单位运价表和产销平衡表，再按表上作业法进行求解。这里不再举例。

对于上述两类运输问题，在EXCEL求解里，并不需要先转化成平衡型运输问题，仅仅在电子表格模型上稍作修改。

§3 应用EXCEL求解运输问题

前面从代数角度给出了运输问题的线性规划模型及求解方法。根据运输问题求解的算法，已经存在许多软件解决求解问题。本节介绍电子表格模型，它和代数模型是等价的。

本节分为两部分，第一部分介绍各种运输问题的模型，第二部分讲述运输问题的应用。

§3.1 典型运输问题的EXCEL求解

例4 EXCEL求解例1中的平衡型运输问题。 解 建立EXCEL电子表格模型如图6-5：

图6-5

图6-5中，单位运价表对应于表6-1，产销平衡表对应于表6-7，可变单元格为(C12:E13)，目标单元格为F14。该电子表格中包含两类约束，即供应约束和需求约束。

对于供应约束，图6-5产销平衡表表格中F列算出了每一个产地的实际供给总量，它是对应行所有决策变量单元格数据的总和，如F12

单元格中的等式是“F12=C12+D12+E12”或

“F12=SUM(C12:E12)”。每一个产地的供应量都包含在F列中，F列中的单元格数据应该等于对应H列单元格中的数据（也就是供应能力）。

对于需求约束，14行列出了所有销地的实际需求总量，它是相应列所有决策变量单元格数据的总和，如“C14=C12+C13”或

“C14=SUM（C12:C13）”。14行中单元格数据应该等于对应16行单元格中的数据（也就是需求能力）。

目标单元格F14计算了总的运输费用，它是单位运价表和产销平衡表主体部分每一对应单元格乘积的和，F14=SUMPRODUCT(C5:E6,C12:E13)。

在规划求解参数对话框里，填入目标单元格、可变单元格以及约束。在约束里，给出了各销地实际需求总量等于需求量（C14:E14=C16:E16）和各产地的实际供应总量等于供应能力（F12:F13=H12:H13）。 在规划求解选项对话框里，由于运输问题仍属于线性规划的范畴，因而选择“采用线性模型”和“假定非负”复选框。

按下规划求解对话框里的求解键，EXCEL规划求解按照单纯型法求得该运输问题解和最优目标值如图6-5的单元格（C12：E13）和单元格F14。

通过例3的求解易知，对于不平衡型运输问题只需在约束里按照总供应量与总需求量的关系将对应的“=”改为“

对于转运问题，在EXCEL求解里并不涉及向平衡型转换的问题，下面给出一例。

例5 假设例1中的煤矿和城市均可作为中转站，新的单位运价表如下。试用EXCEL求解。

表6-8 单位运价表

解 由于每一个产地和销地都可作为中转站，因而产地和销地都有货物的输入与输出。那么一个产地（煤矿）的实际供给量就是其总输出与总输入之差。一个销地的实际需求量是其总输入与总输出之差。模型中单元格（H14:H18）统一为计算各产地或销地总输出与总输入之差。如A1地，总输出为可变单元格中第14行各单元格之和，即SUM

（C14:G14），总输入为可变单元格中C列各单元格之和，即SUM（C14:C18），单元格H14= SUM（C14:G14）-SUM（C14:C18）。该问题依然为平衡型问题，单元格（H14:H18）与J列单元格对应相等。 图6-6给出了该问题的模型和求解结果。

图6-6

在实际应用中，供给量往往是有限的，并不能满足客户的所有需求，产地对于不同的客户会考虑不同的满足程度。正因为此，客户的需求量也并非固定不变的，往往存在着最大需求和最小需求，最大需求一般是销地的需求量，而最小需求是考虑到实际能满足的底线值。

例6 对于例1，将两煤矿的供应量分别减少为180和220，此时三城市的需求不能全被满足。若考虑满足B1城市的所有需求，B2城市至少1/3的需求和B3城市至少2/3的需求。试用EXCEL寻找解决该问题的最佳方案。

解 根据问题在模型中列出最小需求和最大需求。第15行单元格(C15:E15)为各销地的实际需求总量，应“>=”第16行（最小需求）和“=”单元格C16，并且“

图6-7给出了该问题的模型和求解结果。

图6-7

3.2 一些应用

这一小节要给出的是，运输问题并非仅仅用来解决实际的运输问题，许多应用和运输并没有什么直接联系，只要能转化为一个运输问题进行分析，就可以通过它获得解决方案。

例7、某汽车发动机制造厂拟计划生产一批发动机来满足未来四个月汽车安装的需要。为了给出最优的进度安排，使总成本最小，有关人员已收集数据如下表：

表6-9

每个月生产一定数量的发动机，没有安装完的入库保存。加班的单位生产成本高于正常时间生产成本。这样，成本由生产成本和库存成本两部分构成。试为该问题寻找最优进度方案，使总成本最少。 解 见图6-8的模型。

图6-8

该问题产地为每月正常或加班时间生产发动机，供应量为最大产量；销地为每月安装发动机，需求量为计划安装量。单位成本=单位生产成本+单位库存成本*库存的月份数。

决策变量xij，i表示生产的时间，j表示安装的时间。如可变单元格（C16:F23）中，C16表示1（正）生产、1月份安装的发动机台数。

单元格（G16:G23）为各月正常或加班时间的产量，应不超过对应最大产量，它们等于各自供给各月安装量的总和。如单元格G16为1（正）的产量，它为其供应各月安装量的总和，因而为可变单元格第16行各单元格的和，即SUM（C16:F16）。

单元格（C24:F24）为各月安装的发动机台数，应满足（等于）对应计划安装量，它们等于各月正常或加班时间生产的发动机供给该月安装台数的总和。如单元格F24，为各月正常或加班时间生产的发动机供给4月安装的台数的总和，因而为可变单元格F列的和，即SUM（F16:F23）。

每月生产的发动机只能在从本月开始以后的月份（包括本月）安装，因而当生产月份大于安装月份时，xij=0。 图6-8给出了规划求解的结果。 最优进度安排见表6-10 表6-10 最优进度安排表

例8 某市拟开办第三所小学，需要为该市内的所有小学重新划定服务区域。该市大致分6个城区，每一城区内小学生数量以及到各小学的近似距离见表6-11。学校的招生数量视具体情况可在一定范围内变动。服务区域的划分目标是使学生到学校的平均距离最短。试求最优划分方案。 表6-11

解 该问题产地为各城区的学生数，供应量为各城区的学生数量；销地为各学校就读的学生数，需求量在各学校的最大招生数和最小招生数之间。单位成本在这里是距离学校的里程。

决策变量xij，表示i城区到j学校就读的学生数。如可变单元格（C16:E21）中，C16表示第1城区到第1所小学就读的学生数。

单元格（F16:F21）为各城区就读的总学生数，应满足各城区的学生数量，它们各自等于到各所学校读书的学生的总和。如单元格F16为第1城区就读的学生总数，它为到三所学校就读的学生数的总和，因而为可变单元格第16行各单元格的和，即SUM（C16:E16）。

单元格（C22:E22）为到各所学校就读的学生数，界于各所学校的最大招生数和最小招生数之间，应等于各城区分到某学校的学生数的总和。如单元格C22，为到第1所学校就读的学生数，因而为可变单元格C列的和，即SUM（C16:C21）。

学生到学校的平均距离由SUMPRODUCT(C4:E9，C16:E21)实现，目标达到最小。

图6-9给出了规划求解的结果

31

图6-9

习题6

6.1 已知某运输问题的供应量、需求量及单位费用如下：32

a1150,a2100,a365;b195,b250,b3110,b460;

c118,c126,c133,c144,c216,c227,c238,c245,c314,c323,c332,c345.

试建立该问题的数学模型。

6.2 某厂拟定下年度的生产计划，根据预测，单位生产成本四个季度依次为8、9、10、11元。在二、四季度考虑加班，单位生产成本为12、14元。每季能生产10万件产品，加班能增加3万件。根据合同，每季要交货依次为8、9、10、11万件。每季的产品销不出去的库存费用为1元。试建立该厂使总成本最小的生产计划模型。

6.3 判断下列调运方案是否为表上作业法求解时的初始方案。为什么？

表6-1（a）

表6-1（b）

33

表6-1（c）

6.4 已知运输问题的供需关系表与单位运价表如表6-2（表中M表示任意大正数）。试用表上作业法求其最优方案，初始方案用西北角法或最小元素法。

表6-2（a）

34

表6-2（b）

表6-2（c）

表6-2（d）

35

6.5 某一运输问题可以叙述如下：有n个地区需要某种物资，需要量分别不少于bj(j1,,n)。这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别不大于ai(i1,,m)，已知从i地区工厂至地j个需求地区单位物资的运价为cij，又aibj，试写出

i

1

j1

m

n

其对偶问题，并解释对偶变量的经济意义。

6.6 已知某运输问题的产销平衡表和单位运价表，并给出了一个调运方案，见表6-3和6-4，判断给出的方案是否为最优方案，并说明理由。

表6-3

36

表6-4

6.7 表6-5和6-6给出了一个具有无穷多最优解的运输问题的产销平衡表、单位运价表。并在6-5中给出了一个最优解，要求找出两个不同的最优解。

表6-5

37

表6-6

6.8 试用EXCEL方法求解6.2中的生产计划模型。

6.9 某水管站是一个水资源分配机构，它所主管的地域十分干燥，需从外地引水。引水来源主要是三条河流。引入水后该水管站再将水转卖给该地区的客户。其客户是该地区所属四城市的供水部门。该机构的供水成本主要取决于水的来源及供给的城市。以100万立方英尺为单位，给出该水管站的水资源数据如表6-7。该站的目标是选择合适的供水方案，是在满足每个城市用水需求的前提下供水的成本最小。试建立该问题的电子表格模型，并用EXCEL规划求解进行求解。

表6-7

38

6.10 对于6.9中的问题，由于参数表中的数据都是估计出来的，并不准确。管理人员希望进行what-if分析。使用EXCEL规划求解生成一个灵敏度报告，并回答下面的问题：

１、若从河流3配送单位立方英尺的水给城市3的单位成本是200元而不是230元，那么原来求得的最优方案是否依然最优？ 2、若从河流2配送单位立方英尺的水给城市2的单位成本是160元而不是130元，那么原来求得的最优方案是否依然最优？ 3、若前面两问题中的数值分别为215和145，所求得的最优方案是否依然最优？

4、若河流2的供应量和城市4的需求量同时减少50万立方英尺，估计这些变化的影子价格是否仍然有效？

39