运筹学（第2版）课件 第二章 运输问题

南京航空航天大学经济与管理学院运筹学第二章运输问题

前面讨论了一般线性规划问题的数学模型的建立和求解方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束条件系数矩阵具有特殊结构，这就使我们有可能找到比单纯形法更为简单的求解方法，从而节约大量的计算时间和费用。本章所讨论的运输问题就是属于这样一类特殊的线性规划问题。

在日常生产和经营管理过程中，常常遇到这样一类问题：公司有若干个生产单位与销售单位，根据各生产单位的产量及销售单位的销售量，并且知道各生产单位到各销售单位之间的运输单价，该公司应如何将产品运到各销售单位而使总的运输费用最小？运输问题是特殊的线性规划问题，它是早期的线性网络最优化的一个例子。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。运输问题是极具实际意义的研究。运输问题中最有名的一个实例是罗马尼亚薪柴配送问题。当时的研究条件相当艰苦，整个罗马尼亚只有一台计算机和两位程序员。在没有计算机的帮助下，巴拉斯硬是和八名学生一起通过手算的方式，利用线性规划技术成功解决了当时罗马尼亚交通领域的大难题——薪柴配送问题，为整个罗马尼亚节约了8%的运输成本，这在当时引起了极大轰动。小有成就后，巴拉斯进入了木材工业设计院工作，领导院里的线性规划小组。发展简史

发展简史

2.1运输问题的数学模型例2.1某公司有3个生产同类产品的生产地点（以后称为产地），运往4个销售地（以后称为销地）销售，各产地的生产量、各销地的销售量以及各产地到各销地的单位产品运价如表2.1所示。问该公司应如何调运产品，在满足各销地的需要量的前提下，使总的运费为最小。假设xij

表示从Ai到Bj

的运量,Z表示的运输费用，从而得到其数学模型:

在该模型中，目标函数要求其极小化；前4个约束条件的意义是由各产地运往某一销地的物品数量之和等于该销地的销量；第(5),(6),(7)这3个约束条件表示由某一产地运往各销地的物品数量之和等于该产地的产量;最后一个约束条件表示决策变量的非负条件。

可见运输问题是一种线性规划问题。对于一般情况，假设有m个生产地点，可以供应某种物资(以后称为产地)，用Ai表示，i=1,2,…,m；有n个销售地(以后称为销地)，用Bj表示，j=1,2,…,n；产地的产量和销地的销售量分别为ai,i=1,2,…,m和bj，j=1,2,…,n，从Ai到Bj运输单位物资的运价为cij，这些数据可汇总于如表2.2。如果运输问题的总产量等于其总销量，即则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。下面建立在产销平衡情况下的运输问题的数学模型。假设xij表示从Ai到Bj的运量,则所求的数学模型为:下面建立在产销不平衡情况下的运输问题的数学模型。当产大于销时，即时，运输问题的数学模型可以写成：当销大于产时即时，运输问题的数学模型可以写成：2.2运输问题的基本可行解

针对运输问题的数学模型结构的特殊性，它的约束方程组的系数矩阵具有如下特点：（1）在该矩阵中，它的元素均等于0或1；（2）每列只有两个元素为1，其余元素都是0；（3）对应于每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。（2.1）

根据运输问题的数学模型求出的运输问题的解，它代表着一个运输方案，其中每一个变量xij的值表示由Ai调运到Bj的物品数量。由于运输问题也是一个线性规划问题，因此在求解时，我们与使用单纯形方法类似，首先应当确定该问题的基变量个数；其次，要知道这样一组基变量应当是由哪些变量来组成（也就是要求出初始基本可行解）。运输问题的解X必须要满足模型中的所有约束条件；基变量对应的约束方程组的系数列向量必须是线性无关的；可以证明系数矩阵（2.1）的秩是m+n-1。一方面矩阵的前m行相加之和减去后n行之和结果是0向量，因此该矩阵的秩小于m+n；另一方面有矩阵（2.1）的第2行至第m+n行和前n列及

对应的列交叉处的元素构成m+n-1阶方阵D，D的行列式。

因此矩阵A的秩恰好等于m+n-1，可以证明m+n个方程中的任意m+n-1个方程的系数向量都是线性无关的。

因此在运输问题中解的基变量个数应由m+n-1个变量组成(即基变量的个数=产地个数+销售地个数–1)。进一步我们想知道，怎样的m+n-1个变量会构成一组基变量？为此我们需要引入一些基本概念，通过对这些基本概念的分析和讨论，结合单纯形算法的基本结果，便可得出我们所需要的结论。定义2.1凡是能排成：或互不相同，且互不相同，且形成的变量的集合称之为一个闭回路。而把出现在闭回路中的变量称为这个闭回路的顶点。例2.2设m=3，n=4，决策变量表示由产地Ai调运到销地Bj的数量，如表2.3中，x11、x12、x32、x34、x24、x21构成一个闭回路。这里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4。

销地产地B1B2B3B4A1x11x12

A2x21

x24A3

x32

x34若把闭回路的顶点都在表中画出，并且把相邻的顶点都用一条直线连接起来，就可以得到一条封闭的折线，并且折线的每一条边或者是水平的，或者是垂直的。另外表中每一行和每一列由折线相连的闭回路的顶点只有两个。如表2.4，即顶点为{x12、x32、x34、x14}和表2.5，即顶点为{x11、x12、x22、x24、x34、x31}也分别构成两个闭回路。

表2.4

表2.5定理2.1

m+n-1个变量

构成基变量的充分必要条件是它不包含有任何闭回路。

该定理给出了运输问题基的一个重要特征，这个结论是非常重要的，因为利用它可以判断m+n-1个变量是否构成基变量，它比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。

如果定理2.1中的m+n-1个基变量全部大于等于0，这时是基本可行解。开始结束按某种规则找出一个初始解（初始调运方案）在运输表上对其进行调整，得出一个新解现行解为最优性YesNo2.3运输问题表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形算法。只是具体计算和术语有所不同，可归纳为：（1）找出初始基可行解，即在(mn)产销平衡表上给出m+n-1个有数字的格，这些有数字的格不能构成闭回路，且行和等于产量，列和等于销售量；（2）求各非基变量的检验数，即在表上求出空格的检验数，判断是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求得最优解为止。以下具体给出求解运输问题表上作业法的计算步骤。2.3.1确定初始基可行解确定初始基可行解即首先给出初始的调运方案，方法很多，我们只介绍其中的两种方法：（1）最小元素法最小元素法的基本思想就是就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。下面通过例2.3来说明最小元素法确定初始基可行解的具体步骤。例2.3用最小元素法求例2.1的初始运输方案。解：第一步：从单位运价表2.1中找出最小的单位运价为1，这表示先将A2的产品供应给B1。由于A2每天生产4吨，B1每天只需要3吨，即A2除每日能满足B1的需要外还剩余1吨。因此在产销平衡表(A2,B1)交叉处填上3(即x21=3=min(a2,b1)=min(4,3))，表示A2调运3吨给B1，再在单位运价表中将B1这一列单位运价划去，表示B1的需求已满足，不需要继续调运。第二步:从上述未划去的单位运价表的元素中再找出最小的单位运价2，即A2把剩余的产品供应给B3；B3每天需要5吨，A2只剩余1吨，因此在上述产销平衡表的(A2,B3)交叉处填上1，划去上述单位运价表中A2这一行单位运价，表示A2的产品已分配完毕，如表2.6所示。

销地产地B1B2B3B4产量A13113107A21③92①84A3741059销量3656

表2.6第三步:在表2.6中，未划去的元素中找出最小单位运价为3。这表示将A1的产品供应B3，A1每天生产7吨，B3尚缺4吨，因此在产销平衡表的(A1,B3)交叉处填上4，由于B3的需求已满足，将单位运价表中的B3这一列单位运价划去。如此，一步步进行下去，直到单位运价表中所有元素都划去为止，最终在产销平衡表上就可以得到一个初始调运方案。这个方案的总运费为86元，如表2.7所示。

销地产地B1B2B3B4产量A1

437A23

1

4A3

6

39销量3656

表2.7检查全表，产销已平衡，得到初始调运方案为：,

其余。

有数字的格的总数应为6个（m+n–1=6），而这6个变量包含有任何回路，满足定理2.1，所以是一个基本解。又满足模型的所有约束条件，所以是可行解。该方案对应的解是一个基本可行解。该调运方案的运费为86。

销地产地B1B2B3B4产量A1

437A23

1

4A3

6

39销量3656

表2.7

应当注意的是，在用最小元素法确定初始基可行解的时候，有可能出现以下的两种特殊情况：

一是当在中间步骤的未划去的单位运价表中寻找最小元素时，有多个元素同时达到最小，这时从这些最小元素中任意选择一个作为基变量；

二是当在中间步骤的未划去的单位运价表中寻找最小元素时，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位置填上该剩余产量数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n–1）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。最小元素法代码展示（2）伏格尔法

最小元素法的缺点是，为了节省一处的费用，有时造成在其它地方要花多几倍的运费。伏格尔法考虑到，一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最小运费调运。例2.4用最伏格尔法求例2.1的初始运输方案。步骤如下：第一步：在单位运价表中增加一行和一列，列的格位置相应填入该行的次小运费与最小运费之差，我们称之为行差额。行的格位置相应填入该列的次小运费与最小运费之差，我们称之为列差额。如此可得表2.8：

销地产地B1B2B3B4行差额A13113100A219281A3741051列差额2513

表2.8第二步：从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素。比较该元素所在的行和列的产量与销量，取它们最小者填入产销平衡表相应的位置。同时在单位运价表中划去一行或一列。由于B2

的列差额最大。B2

列中最小元素为4（即A3

行），可确定A3

产品优先供应B2

。比较它们的产量和销量，可知产地A3的产量为9，销地B2的销量为6，因此在产销平衡表的(A3,B2)空格处填入6，由于销地B2已经满足，因此在单位运价表中划去B2

列。第三步：对上述未划去的元素中计算出各行、各列的差额。重复第一、二步的工作，直到给出初始解为止。本问题利用伏格尔方法给出的初始调运方案如表2.9所示。由以上可见：伏格尔方法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同，因而给出的初始调运方案也是基可行解。一般来说，用伏格尔方法所求出的初始解比用最小元素法求出的初始解更接近于最优解。本例用伏格尔方法给出的初始解的总运费为85元。表2.9

销地产地B1B2B3B4产量A1

527A23

14A3

6

39销量3656

伏格尔法代码展示2.3.2最优解的判别

得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于0时为最优解。下面介绍两种求空格检验数的方法。

（1）闭回路法

在给出调运方案的计算表上，如表2.7，从每一空格出发，找一条闭回路。它是以空格为起点，用水平线或垂直线向前划，每碰到一数字格就转90度后继续前进。直到回到起始空格处为止。该闭回路除了起始顶点是非基变量外，其它顶点均为基变量（对应着数字格）。可以证明，如果对闭回路的方向不加区别，对于任一非基变量而言，以每个空格为起点的闭回路都存在且唯一。如(A1,B1)空格与(A1,B3)、(A2,B3)和(A2,B1)三个有数字的格构成一闭回路，如此等等。

闭回路计算检验数的经济解释为：在已给出初始解的表2.7中，可以从任一空格出发，如从(A1,B1)出发，若让A1

的产品调1吨给B1，为了保持产销平衡，就要依次作调整：在(A1,B3)处减少1吨，(A2,B3)处增加1吨，(A2,B1)处减少1吨，即构成了以(A1,B1)空格为起点，其它为有数字的格的闭回路。如表2.10中的直线所示。各顶点所在格的右上角的数字是单位运价。表2.10

销地产地B1B2B3B4产量A13（＋1）

34（－1）

37A213（－1）

21（＋1）

4A3

6

39销量3656

可见这一调整方案使运费增加了：(+1)

3+(-1)

3+(+1)

2+(-1)

1=1(元)这表明若这样调整运输方式将增加运费。将“1”这个数填入(A1,B1)格，这就是该空格的检验数。按以上所述，就可以找出所有空格的检验数，见如下表2.11表2.11空格闭

回

路检验数(A1,B1)(1,1)→(1,3)→(2,3)→(2,1)→(1,1)1(A1,B2)(1,2)→(1,4)→(3,4)→(3,2)→(1,2)2(A2,B2)(2,2)→(2,3)→(1,3)→(1,4)→(3,4)→(3,2)→(2,2)1(A2,B4)(2,4)→(2,3)→(1,3)→(1,4)→(2,4)-1(A3,B1)(3,1)→(3,4)→(1,4)→(1,3)→(2,3)→(2,1)→(3,1)10(A3,B3)(3,3)→(3,4)→(1,4)→(1,3)→(3,3)12这时检验数还存在负数，因为(A2,B4)空格的检验数为–1，这说明表2.7给出的调运方案还不是最优解，还需要进一步改进，改进方法见本节后面的基可行解的改进方法。（2）位势法

用闭回路法求检验数时，需要给每一空格找一条闭回路。当产销点很多时，空格的数量很大，计算检验数将十分费时。下面介绍一种较为简便的方法——位势法。

是一组基可行解，现在引进m+n

个未知量u1,···,um,v1,···,vn，由上述基本可行解可构造如下一个方程组：其中

为变量对应的单位运价。方程组（2.1）共有m+n个未知数和m+n-1个方程。(2.1)的解存在且恰有一个自由变量。称u1,···,um

，v1,···,vn为列位势。定理2.2

设已给了一组基本可行解，则对每一个非基变量xij

来说，它所对应的检验数为：

ij=cij–(ui+vj

)(2.2)

下面,我们就以例子来说明这种方法的具体实施过程。

仍以例2.3所给出的初始基可行解表2.7为例：第一步：在对应表2.7的数字格处填入单位运价如表2.12所示：销地产地B1B2B3B4A1

331010A211

22

A3

44

55表2.12第二步：在表2.12上增加一行和一列，列中填入行位势ui

，行中填入列位势vj

得表2.13。表2.13销地产地B1B2B3B4行位势uiA1

3310100A211

22

－1A3

44

55－5列位势vj29310

先令u1=0（一般令行和列中数字格（基变量）多的行位势或列位势令为0），然后按ui+vj=cij

(i,j)

基变量指标集

，相继确定ui、vj

。由表3—15可见，当u1=0时，由u1+v3=c13=3可得v3

=3，由u1+v4=c14=10，可得v4

=10；在v4

=10时，由u3+v4=c34=5可得u3=-5。以此类推可确定所有的ui、vj的值。第三步：按

ij=cij–(ui+vj

),(i,j)

非基变量指标集，计算所有的空格检验数。如：

11

=c11–(u1+v1

)=3–(0+2)=1

12

=c12–(u1+v2

)=11-(0+9)=2这些计算可直接在表2.13上进行。为了方便，特设计计算表，如表2.14。右上角框内的数为单位运价。在表2.14中检验数还有小于0的，说明还未达到最优解，还得进一步进行改进。表2.14销地产地B1B2B3B4行位势uiA131112301000A21091208-1－1A371040101250－5列位势vj29310

2.3.3基可行解改进的方法——闭回路调整法

当计算完所有的空格检验数时，如果检验数还有小于0的，这表明还未达到最优解。若有两个或两个以上的检验数小于0时，一般选择其中最小的小于0的检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表2.14可知(A2,B4)为调入格（即以它对应的变量x24

为换入变量）。以x24为出发点，作一闭回路为x24→x14→x13→x23，如表2.15所示。

销地产地B1B2B3B4产量A1

4(+1)3(-1)7A23

1(-1)(+1)4A3

6

39销量3656

表2.15

在闭回路上作运量调整，称空格点x24为第1顶点，x14，x13，x23，分别称为第2，3，4顶点，(A2,B4)格的调入量

是选择闭回路上偶数格中运量的最小者，即

=min{1,3}=1(其原理与单纯形法中按

规则来确定的换出变量是相同)，然后在闭回路上的奇顶点加入该调整量，偶顶点减入该调整量，，得到调整方案如表2.16所示。对表2.16给出的解，再用闭回路法或位势法求各空格的检验数，这时表中的所有检验数全都大于等于0，所以表2.16所给出的解为最优解。这时得到的总运费的最小值是85元。表2.16

销地产地B1B2B3B4产量A1

527A23

14A3

6

39销量3656

2.4运输问题的Excel求解方法2.4.1产销平衡运输问题例2.5使用Excel规划求解工具求解例2.1。方法如下：Step(1)根据题目条件，建立电子表格如图2.1，其中第2-5行是运费表，第7-15行是规划求解需要的表格。其中的C8:F10是规划求解的可变单元格区域，用于存放从3个产地发往4个销地的产品数量，为便于识别进行了颜色填充。图2.1电子表格Step(2)对电子表格的单元格编辑公式。

第11行用于对3个产地的供货数量进行求和，以便于与存量目标进行对比。单击C11单元格后如图2.2输入公式C11=SUM(C8:C10)点击对号符号“√”，则完成对C11单元格的公式输入。并向右复制填充至F11单元格。图2.2单元格公式输入G列用于对4个销地的实际到货数量进行求和，以便于与产地的产量进行对比。在G8单元格内输入公式G8=SUM(C8:F8)并向下复制填充至G10单元格。

第13行用于计算实际到货量与需求量之间的差额，即缺货量。在C13单元格内输入公式C13=C12-C11并向右复制填充至F13单元格。I列用于计算3个产地的产量与实际供货量之间的差额，在I8单元格内输入公式I8=H8-G8并向下复制填充至I10单元格。C15是目标单元格用于计算实际产生的运输费用：C15=SUMPRODUCT(C3:F5,C8:F10)所有公式输入结束之后，当点击公式下的显示公式，会看到编辑的所有公式见图2.4。Step(3)选中C15单元格，打开“规划求解参数”对话框，在“设置目标单元格”文本框中选择C15单元格，选中“最小值”按钮，在“可变单元格”文本框中选择C8:F10单元格区域。图2.4Step(4)单击“添加”按钮，打开“添加约束”对话框进行约束条件的添加，本例所包含的约束条件如下：

条件1：C11:F11=C12:F12

条件2：G8:G10=H8:H10添加完成，单击“添加约束”对话框中的“确定”按钮，返回“规划求解参数”对话框，结果如图2.5所示。图2.5设置规划求解参数因为是供需平衡，所以条件1表示需求全部满足，有实际到货总量=需求量；条件2表示产量全部用完，即有实际供货量=产量。Step(5)因为所有变量的运算均是线性运算并且要求变量是正数，所以选择“使无约束变量为非负数”选项。为了提高规划求解的运算效率，可以单击“单纯线性规划”复选框旁的“选项”按钮，打开“所有方法”对话框，如图2.6所示。图2.6采用线性模型和假定非负Step(6)单击“确定”按钮返回“规划求解参数”对话框，然后单击“求解”按钮开始求解运算过程，显示找到一个结果。单击“规划求解结果”对话框中的“确定”按钮保存此结果，如图2.7所示。可知，结果显示总运费为85。图2.7运输问题求解结果2.4.2产销不平衡运输问题（1）当产量大于销量例2.6

若例2.1中A2产量增加到6,该运输问题如何用Excel求解呢?

解：此时，总产量>总销量。使用Excel规划工具求解时按照例2.5的步骤操作，注意以下几个步骤：Step(1)图2.3中H9数据单元格的值由4改为6。Step(4)添加2个约束如下：条件1：C11:F11=C12:F12条件2：G8:G10<=H8:H10。因为是产量大于销量，条件1：实际到货总量=需求量，表示需求全部满足；条件2：实际供货总量<=产量，表示产量有剩余。最后求解的结果如图2.8所示。图2.8生产量大于销售量的求解结果（2）当产量小于销量例2.7

若将例2.1中B3的需求调整为7,该运输问题如何用Excel求解呢?解：此时，总产量<总销量。使用Excel规划工具求解时按照例2.5的步骤操作，注意以下几个步骤：Step(1)将图2.3中B3的需求对应的数据单元格E12由5改为7。Step(4)如果仍用例2.6的2个约束Step(6)求解结果显示无解，如图2.9所示。图2.9生产量小于销售量的求解结果可以判断是供不应求，而事实确实如此。那么该怎么做呢？Step(4)选中要修改的约束单击【更改】按钮，改变一下条件1和条件2。条件1：C11:F11<=C12:F12条件2：G8:G10=H8:H10Step(6)最后求解的结果如图2.10所示。图2.10改变条件后生产量小于销售量的求解结果

结果显示，产地的生产量没有剩余的同时B4销地还缺货2吨，总运费为71元。2.5案例分析案例分析1（生产玩具销售）某玩具公司分别生产三种新型玩具，每月可供应量分别为1000件、2000件、2000件，它们分被送到甲、乙、丙三个百货商店销售。已知每月各百货商店各类玩具总和的预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同（见表2.18）。又知道丙百货商店要求至少供应C玩具1000件，而拒绝A玩具。求满足上述条件下使总盈利额为最大的供销分配方案。

甲乙丙可供应量A54—1000B16892000C1210112000表2.18三种新型玩具有关数据解：由于总供应量为1000+2000+2000=5000,总需求量（预期销售量）为1500+1500+1500=4500，总供应大于总需求，因此是产大于销的运输问题。用Excel求解时其电子表格模型见图2.11。图2.11生产玩具销售案例数学模型单元格公式参照图2.12进行编辑。图2.12生产玩具销售案例数学模型的公式编辑模型的“规划求解参数”对话框如图2.13所示。在“设置目标”文本框中选择B13单元格，选中“最大值”按钮，在“通过更改可变单元格”文本框中选择B6:D8单元格区域。添加4个约束：

条件1：B9:D9=B10:D10

条件2：D6=0

条件3：D8>=1000

条件4：E6:E8<=F6:F8图2.13生产玩具销售案例“规划求解参数”设置

各条件的含义如下：条件1：到货总量=需求量，表示需求全部满足；条件2：表示丙拒绝A玩具，所以A运到丙的玩具数量是0；条件3：表示丙百货商店要求至少供应C玩具1000件条件4：供货总量<=产量，表示产量有剩余；

最后求解结果见图2.14。图2.14生产玩具销售案例求解结果案例分析2（化肥调拨问题）

设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的运价表如表2.19所示。试求出总的运费最省的化肥调拨方案。表2.19单位运价：万元/万吨）

需求产地B1B2B3B4产量(万吨)A11613221750A21413191560A3192023—50最低需求3070010

最高需求507030不限解:显然这是一个产销不平衡问题。总产量为160万吨，按照题意分析最多运往B4地区60万吨。所以设定B4地区的最高需求是60万吨。用Excel求解时其电子表格模型见图2.15。图2.15解:显然这是一个产销不平衡问题。总产量为160万吨，按照题意分析最多运往B4地区60万吨。所以设定B4地区的最高需求是60万吨。图2.16所示对单元格进行公式编辑。图2.16选中B16单元格，打开“规划求解参数”对话框，在“设置目标”文本框中选择B12单元格，选中“最小值”按钮，在“通过更改可变单元格”文本框中选择B6:E8单元格区域，如图2.17所示。图2.17添加4个约束：条件1：B10:E10<=B11:E11条件2：B10:E10>=B9:E9条件3：E8=0条件4：F6:F8=G6:G8图2.18含义如下：条件1：实际收到<=最高需求；条件2：实际收到>=最低需求条件3：表示A3不能运送化肥到B4地区，所以该单元格运量是0；条件4：因为最高需求量总和大于产量，所以有实际运送=产量。

结果显示B1、B2地区的最高需求得到满足，B3地区的到货量是0，B4地区的到货量是40万吨，均满足了最低需求。案例分析3（生产安排问题）

某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表2.20所示。又如果生产出来的柴油机当季不交货，每台每季度需存储费、维护费等共0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护等）费用最小的决策。表2.20季

度生产能力(台)单位成本(万元)I2510.8II3511.1III3011.0IV1011.3人们常常尽可能把某些线性规划问题化为运输问题的数学模型。下面介绍如何把线性规划问题转化为运输问题。解：4个季度作为4个产地，每季度的生产能力为对应的产量；4个季度作为4个销地，按合同规定须于每个季度末分别提供同一规格的柴油机的数量作为对应的需求量。第i季度生产的用于第j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。得到一个运输问题,数据见表2.21。表2.21产销表与单位运价表

销售生产I销地II销地III销地IV销地产量I产地10.810.9511.1011.2525II产地

11.1011.2511.4035II产地

11.0011.1530IV产地

11.3010销量10152520

由于每个季度生产出来的柴油机不一定当季交货，所以设xij

表示为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足：

x11=10

x12+x22=15

x13+x23+x33=25

x14+x24+x34+x44=20又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：

x11+x12+x13+x14

25x22+x23+x24

35x33+x34

30x44

10第i

季度生产的用于第j

季度交货的每台柴油机的实际成本cij

应该是该季度单位成本加上储存、维护等费用。

cij

的具体数值见表2.22。

设用ai

表示该厂第i季度生产能力，bj表示第j季度的合同供应量，则问题可写成：表2.22显然这是一个产大于销的运输问题模型。用Excel求解时建立的规划求解的电子模型如图2.19。图2.19单元格公式按照图2.20进行编辑。图2.20求解时添加的约束条件有：条件1：B8=0条件2：B9:C9=0条件3：B10:D10=0条件4：B11:E11=B12:E12条件5：F7:F10<=G7:G10

条件1表示产地II不能向销地I供货,条件2表示产地III不能向销地I,销地II供货条件3表示产地V不能向销地I,销地II和销地III供货最后求解的结果如图2.21所示。

结果显示，第Ⅰ季度生产25台，其中10台当季交货，10台第Ⅱ季度交货；第Ⅱ季度生产5台用于第Ⅱ季度交货；第Ⅲ季度生产30台，其中25台当季交货，5台用于第Ⅳ季度交货；第Ⅳ季度生产10台用于当季度交货。按此方案安排生产，可使该厂总的生产(包括储存费、维护费等)费用最省，即为773万元。案例分析4（生产成本问题）某造船厂根据合同要求从当年起连续三年末各提供三条规格型号相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如表2.23所示。表2.23造船厂三年内生产大型客货轮的有关数据

已知加班生产时，每艘客货轮成本比正常生产时高出70万元。又知造出来的客货轮如当年不交货，每艘每积压一年造成的积压损失为40万元。在签订合同时，该厂已储存了两艘客货轮，而该厂希望在第三年末完成合同后还能储存一艘备用。问该厂该如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用加积压损失为最少。解：这是一个生产与储存问题，可以转化为运输问题来做。根据已知条件可以列出生产能力（正常生产能力和加班生产能力）和合同要求以及费用表2.24。表2.24费用表年度1至年度3，总的生产能力(包括上年年末储存)为17艘，合同要求总量为10艘(包括第三年年末储存)，为生产量大于销售量。上年年末库存2艘客货轮，只考虑每艘积压一年造成的积压损失40万元。当年生产当年交货，则只计算生产成本；如果当年生产出来的客货轮当年不交货，则将生产成本以及每艘每积压一年40万元所造成的积压损失一起计算。4.对于第三年年末的留出库存考虑生产成本以及每年的积压损失。

生产分成正常生产和加班生产。运用Excel求解时建立的电子表格模型如图2.22所示。图2.22单元格公式见图2.23。图2.23求解时添加的约束有：

条件1：B14:B17=0条件2：C16:C17=0条件3：B18:E18=B20:E20条件4：F11:F17<=H11:H17最后结果见图2.24。下面讨论运输问题中的转运问题。所谓的转运问题是运输问题的一个扩充，即在原来运输问题中的产地与销地之间再增加中转点。在运输问题中只允许物品从产地运往销地，而在转运问题中还允许把物品从一个产地运往另一个产地(中转点或销地)，允许把物品从一个中转点运往另一个中转点(产地或销地)，也允许把物品从一个销地运往另一个中转点或产地。每个产地的生产量都有限制，而每个销地的需求量也都有一个限制，在任意两点间单位物品运价已知的情况下，如何使总的运输费最小图2.24案例分析5（物质调运问题）宏达电子仪器公司，其生产线分别在大连、广州，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。在任意分厂的生产线生产的产品可能被运往公司设在长沙或天津的地区仓库中的任意一个。从这些仓库，公司向南京、西安、济南和上海的零售商发货。这些城市间的每台仪器的运费我们标在两个城市间上的弧上，单位为万元；工厂和零售商的供给与需求在图的左侧和右侧标明如图2.25所示。问应该如何调运仪器，使总的运费最低？图2.25宏达电子仪器公司转运网络图解：该转运问题可以转化为两个运输问题。可做如下处理：(1)由于问题中的所有产地、中转点都可以看成产地，而中转点与销地都可以看成销地，因此整个问题可以看成是一个由四个产地和六个销地组成的运输问题；(2)对于扩大的运输问题建立运价表，表中的不可能运输方案的运价用M代替；(3)所有中转点的生产量等于销售量，即流入量等于流出量。由于运费最小时不可能出现物资来回倒运的现象，因此每个中转点的运量不会超过1000台，所以可以规定中转点的生产量和销售量均为1000台，这样就可以得到扩大的产销平衡运输问题及其运价表，如表2.25所示。表2.25

长沙/万元天津/万元南京/万元西安/万元济南/万元上海/万元生产量/台广州23MMMM600大连31MMMM400长沙0M26361000天津M044651000销售量/台10001000200150350300

运用Excel求解：建立的电子表格模型见图2.26，在模型中运价是M处均用10000替换（这个值要远远大于其它的单位运价，当求运费最小时，此处运量就是0）。这样，求解时约束条件如同例2.5只有2个，即供货总量=产量；到货总量=需求量。图2.26单元格公式见图2.27。图2.27最后结果如图2.28。图2.28如图2.28所示最优运输方案为从广州运往长沙550台，从长沙再运往南京200台、济南350台；从广州运往天津50台、从大连运往天津400台，从天津再运往西安150台；直接从天津运往上海300台。总运费为5200万元。如果公司认为从大连到上海的距离较近，可以直接从大连分厂向上海供货，且每台运费为5万元，如图2.29所示，这时的运输问题及其运价表，如表2.26所示当采用excel求解时只需将电子模型（图2.26）的单元格G4的值改为5，参照上一问的步骤，最后求解结果见图2.30。图2.29宏达电子仪器公司转运网络图图2.30这时的最优运输方案为从广州运往长沙550台，从长沙再运往南京200台、济南350台；从广州运往天津50台、从大连运往天津100台，从天津再运往西安150台；直接从大连运往上海300台。总运费为4900万元。如果公司认为从大连到上海的距离较近，可以直接从大连分厂向上海供货，每台运费为4万元，也可以从济南向上海供货，每台运费为1万元，如图2.31所示。这时要把问题中的产地、销地、中转点都看成产地，中转点与销地看成销地，因此整个问题可以看成是一个由五个产地和六个销地组成的运输问题图2.31宏达电子仪器公司转运网络图

这时的运输问题及其运价表，如表2.27所示。此时济南作为产地承担了中转的作用，最多运出1000，所以规定产量是1000；而济南作为销地需求是1000+350=1350。此时excel求解建立的电子模型和求解结果见图2.32。表2.27

这时的最优运输方案为：从广州运往长沙600台，从长沙再运往南京200台、济南400台，从济南运50台到上海；从大连运往天津150台，运往上海250台，再从天津运往西安150台。总运费为4850万元。图2.32案例分析6（蔬菜供应问题）某市是一个人口不到15万人的小城市，根据该市的蔬菜种植情况，分别在A、B和C设立三个收购点，再由收购点分别送到全市的8个菜市场。按照往年情况，A、B、C三个收购点每天的收购量分别是200、170和160（单位：kg）,各菜市场每天的需求量及发生供应短缺时带来的损失见表2.28。各收购点至各菜市场的距离见表2.29。各收购点至各菜市场的单位运价为1元/100kg.100m。表2.28表2.29各收购点至菜场的距离为该市设计一个从各收购点至菜市场的定点供应方案，使总费用(包括蔬菜运费、缺货损失)最小。若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案。为满足城市居民的蔬菜供应，该市规划增加蔬菜的种植面积，试问增产的蔬菜每天应分别向A、B、C三个收购点各供应多少最为经济合理。解：（1）三个收购点每天总收购量为200+170+160=530，而菜市场每天总需求量为75+60+80+70+100+55+90+80=610，这是一个“销大于产”的运输问题①设假设xij

表示从收购点i（i=A,B,C）向菜市场j(j=1,2,…,8)调运的蔬菜量（单位：100kg）,yj表示菜场j(j=1,2,…,8)的供应短缺量