运输问题与指派问题

第六章 运输问题与指派问题,运输问题(Transportation Problem)和指派问题(Assignment Problem)属于线性规划问题，是线性规划的两类常见问题，并且这两类问题具有特殊的数学性质，使得管理科学家能够开发出多种高效独特的求解算法，所以我们专门用一章来研究。,本章内容,6.1 案例研究：L食品公司的运输问题 6.2 运输问题的模型与性质 6.3 应用EXCEL和LINGO求解运输问题 6.4 运输问题变形的一些应用 6.5 指派问题,6.1 L食品公司的运输问题,例1 湖南L食品公司是生产食品罐头的企业，有桔子、竹笋、野山菌三个罐头厂，三个工厂的厂址分别在A、B、C三个靠近不同原料产地的城镇，每个工厂都能生产不同品种的罐头，但每个工厂生产不同品种罐头的产能不同，各工厂生产与厂名相同的罐头的设计产能要大一些。 2009年6月份来自深圳、武汉、成都和西安的四个配送中心的野山菌罐头订单和各工厂的野山菌罐头的计划产量如表6-1所示。 2009年6月每箱野山菌罐头从各个工厂到各个配送中心的具体运价如表6-2所示。,表6-1 罐头的产能和配送中心需求 （单位：箱）,表6-2 各工厂到配送中心的野山菌罐头运价 （单位：元/箱）,表6-1 、表6-2 可以用下图表示：,小张的运输方案 （单位：箱）,小张的运输方案需要运费成本是：,小刘的运输方案 （单位：箱）,小刘的运输方案需要运费成本是：,杨经理的思考,小刘的运输方案比小张的节约了140元，于是，杨经理决定用小刘的方案。但是，会不会还有更节约的运输方案呢？ 杨经理开始琢磨这个问题，或许以后能找到更好的方案吧，不管怎么样，以后要在运输方案安排上多用点心思了，因为每隔几天运输部都要为公司不同的产品订单集中安排一次运输，如果每次都能用最好的方案，一年下来也是一笔可观的费用呢。,6.2 运输问题的模型与性质,1 运输问题的模型 例1中提到的湖南某食品公司的问题就是一个典型的运输问题。在运输问题中，寻求从产地到销地的最小的运输成本。运输问题的一般提法是这样的： 某种物资有若干个产地和销地，若已知各个产地的产量、各个销地的销量以及各产地到各销地的单位运价（或运输距离）。问应如何组织运输，才能使总运费（或总的运输量）最省？ 假定有 m个产地， n个销地，我们定义如下变量：,第 产地 的供应量， i =1，2，m ； 第 销地 的需求量，j =1，2，n ； 从产地 到销地 的单位运费，i =1，2，m ， j =1，2，n ； 产地 到销地 的运输数量， i =1，2，m ， j =1，2，n 。 则该问题为求解最佳运输方案，即求解所有 的值，使总的运输费用 达到最少。决策变量为,该问题的数学模型形式为：,把例1的问题用数学模型表达出来就是：,2 运输问题的性质 运输问题中每一个产地都有一定的供应量（supply）配送到销地，每一个销地都有一定的需求量（demand），接收从产地发出的产品，基本的运输问题有如下性质： 1）需求假设（The Requirements Assumption） 每一个产地都有一个固定的供应量，所有的供应量都必须配送到销地。与之相类似，每一个销地都有一个固定的需求量，整个需求量都必须由产地满足。,2）可行解特性（The Feasible Solutions Property） 当且仅当供应量的总和等于需求量的总和，也就是产销平衡时，运输问题才有可行解。 3）成本假设（The Cost Assumption）： 从任何一个产地到任何一个销地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以配送的数量。 4）整数解性质（Integer Solutions Property） 只要运输问题的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件，这使得求解运输问题避免了整数约束所导致的计算复杂性大幅度增加的麻烦,6.3 应用EXCEL和LINGO求解运输问题,1 应用EXCEL求解运输问题 由于运输问题是线性规划问题，我们可以很方便地在电子表格中建模求解。见图6.2。 应用“规划求解”后，我们得到一个最优解，由图6.2中表格的阴影部分的数据可知，A厂运50箱到武汉、运30箱到西安；B厂运100箱到西安；C厂运85箱到深圳、60箱到武汉、75箱到成都，此时总运费最低，最优值是31530元。 采用这个方案，食品公司6月份这批野山菌罐头订单的运输费用比小张的方案（32390元）节约了860元，比小刘的方案（32250元）节约了720元。,2 LINGO使用简介,LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 因为篇幅所限，本小节只对LINGO最基本的应用和功能结构进行介绍，每个功能详细的应用技巧请见本书相关的例子和LINGO的帮助文件。,1) LINGO快速入门 当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：,线性规划模型在电子表格中布局的好坏关系到问题可读性和求解方便性的高低。 本节以第一章中的例1（资源分配问题）为例来说明一下如何在电子表格中描述线性规划模型，让我们回顾一下第一章中例1的数学模型： Max s.t. 在模型窗口中输入如下代码：,max=4*x1+3*x2; x1=6; 2*x2=8; 2*x1+3*x2=18; 然后点击工具条上的按钮 即可。,2) LINGO中的集 对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等。LINGO允许把这些相联系的对象聚合成集（sets）。一旦把对象聚合成集，就可以利用集来最大限度的发挥LINGO建模语言的优势。 现在我们将深入介绍如何创建集，并用数据初始化集的属性。学完本节后，你对基于建模技术的集如何引入模型会有一个基本的理解。,（1）为什么使用集,集是LINGO建模语言的基础，是程序设计最强有力的基本构件。借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型。,（2）什么是集,集是一群相联系的对象，这些对象也称为集的成员.一个集可能是一系列产品、卡车或雇员。 每个集成员可能有一个或多个与之有关联的特征，我们把这些特征称为属性。属性值可以预先给定，也可以是未知的，有待于LINGO求解。 例如: 产品集中的每个产品可以有一个价格属性； 卡车集中的每辆卡车可以有一个牵引力属性； 雇员集中的每位雇员可以有一个薪水属性，也可以有一个生日属性等等。,LINGO有两种类型的集：原始集(primitive set)和派生集(derived set)。 一个原始集是由一些最基本的对象组成的。 一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。,（3）模型的集部分,集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。 集部分以关键字“sets:”开始，以“endsets”结束。 一个模型可以没有集部分，或有一个简单的集部分，或有多个集部分。 一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须定义了它们。,1） 定义原始集 为了定义一个原始集，必须详细声明： 集的名字 可选，集的成员 可选，集成员的属性 定义一个原始集，用下面的语法： setname/member_list/:attribute_list; 注意：用“”表示该部分内容可选。下同，不再赘述。 Setname是你选择的来标记集的名字，最好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线（_）为首字符，其后由拉丁字母（AZ）、下划线、阿拉伯数字（0，1，9）组成的总长度不超过32个字符的字符串，且不区分大小写。 注意：该命名规则同样适用于集成员名和属性名等的命名,Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们 当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。 例如，可以定义一个名为students的原始集，它具有成员John、Jill、Rose和Mike，属性有sex和age： sets: students/John Jill, Rose Mike/: sex, age; endsets 当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法： setname/member1memberN/: attribute_list;,这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名，用于创建一些特殊的集。列表如下：, 集成员不放在集定义中，而在随后的数据部分来定义 !集部分; sets: students:sex,age; endsets !数据部分; data: students,sex,age= John 1 16 Jill 0 14 Rose 0 17 Mike 1 13; enddata 注意：开头用感叹号（!），末尾用分号（;）表示注释，可跨多行。,在集部分只定义了一个集students，并未指定成员。在数据部分罗列了集成员John、Jill、Rose和Mike，并对属性sex和age分别给出了值。 集成员无论用何种字符标记，它的索引都是从1开始连续计数。在attribute_ list可以指定一个或多个集成员的属性，属性之间必须用逗号隔开。 2） 定义派生集 为了定义一个派生集，必须详细声明： 集的名字 父集的名字 可选，集成员 可选，集成员的属性,可用下面的语法定义一个派生集： setname(parent_set_list)/member_list/:attribute_list; setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。举例如下： sets: product/A B/; machine/M N/; week/12/; allowed(product,machine,week):x; endsets,LINGO生成了三个父集的所有组合共八组作为allowed集的成员。列表如下： 编号 成员 1 (A,M,1) 2 (A,M,2) 3 (A,N,1) 4 (A,N,2) 5 (B,M,1) 6 (B,M,2) 7 (B,N,1) 8 (B,N,2),成员列表被忽略时，派生集成员由父集成员所有的组合构成，这样的派生集成为稠密集。如果限制派生集的成员，使它成为父集成员所有组合构成的集合的一个子集，这样的派生集成为稀疏集。 同原始集一样，派生集成员的声明也可以放在数据部分。一个派生集的成员列表有两种方式生成： 显式罗列； 设置成员资格过滤器。 当采用方式时，必须显式罗列出所有要包含在派生集中的成员，并且罗列的每个成员必须属于稠密集。使用前面的例子，显式罗列派生集的成员： allowed(product,machine,week)/A M 1,A N 2,B N 1/;,如果需要生成一个大的、稀疏的集，那么显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。我们可以把这些逻辑条件看作过滤器，在LINGO生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。详细内容请参见LINGO帮助文件。 3) 模型的数据部分 数据部分提供了模型相对静止部分和数据分离的可能性。显然，这对模型的维护和维数的缩放非常便利。 数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。其语法如下： object_list = value_list;,对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。一个对象列中至多有一个集名，而属性名可以有任意多。如果对象列中有多个属性名，那么它们的类型必须一致。如果对象列中有一个集名，那么对象列中所有的属性的类型就是这个集。 数值列（value_list）包含要分配给对象列中的对象的值，用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。 看下面的例子(a)和(b)：,(a) sets: set1/A,B,C/: X,Y; endsets data: X=1,2,3; Y=4,5,6; enddata 在集set1中定义了两个属性X和Y。X的三个值是1、2和3，Y的三个值是4、5和6。也可采用如下例子中的复合数据声明（data statement）实现同样的功能。,(b) sets: set1/A,B,C/: X,Y; endsets data: X,Y=1 4 2 5 3 6; enddata 看到这个例子，可能会认为X被指定了1、4和2三个值，因为它们是数值列中前三个，而正确的答案是1、2和3。假设对象列有n个对象，LINGO在为对象指定值时，首先在n个对象的第1个索引处依次分配数值列中的前n个对象，然后在n个对象的第2个索引处依次分配数值列中紧接着的n个对象，以此类推。,4) LINGO函数 LINGO有9种类型的函数： (1）基本运算符：包括算术运算符、逻辑运算符和关系运算符 (2）数学函数：三角函数和常规的数学函数 (3）金融函数：LINGO提供的两种金融函数 (4）概率函数：LINGO提供了大量概率相关的函数 (5）变量界定函数：这类函数用来定义变量的取值范围 (6）集操作函数：这类函数为对集的操作提供帮助 (7）集循环函数：遍历集的元素，执行一定的操作的函数 (8）数据输入输出函数：这类函数允许模型和外部数据源相联系，进行数据的输入输出 (9）辅助函数：各种杂类函数,一 基本运算符,1） 算术运算符 算术运算符是针对数值进行操作的。LINGO提供了5种二元运算符： 乘方 乘 除 加 减 LINGO唯一的一元算术运算符是取反函数“”,一 基本运算符（续）,这些运算符的优先级由高到底为： 高 （取反） 低 运算符的运算次序为从左到右按优先级高低来执行。运算的次序可以用圆括号“（）”来改变。,二 逻辑运算符,LINGO具有种逻辑运算符： #not# 否定该操作数的逻辑值，not是一个一元运算符 #eq# 若两个运算数相等，则为true；否则为flase #ne# 若两个运算符不相等，则为true；否则为flase #gt# 若左边的运算符严格大于右边的运算符，则为true；否则为flase #ge# 若左边的运算符大于或等于右边的运算符，则为true；否则为flase #lt# 若左边的运算符严格小于右边的运算符，则为true；否则为flase,二 逻辑运算符（续）,#le# 若左边的运算符小于或等于右边的运算符，则为true；否则为flase #and# 仅当两个参数都为true时，结果为true；否则为flase #or# 仅当两个参数都为false时，结果为false；否则为true 这些运算符的优先级由高到低为： 高 #not# #eq# #ne# #gt# #ge# #lt# #le# 低 #and# #or#,三 关系运算符,关系运算符与逻辑运算符#eq#、#le#、#ge#截然不同，前者是模型中该关系运算符所指定关系的为真描述，而后者仅仅判断一个该关系是否被满足：满足为真，不满足为假。 LINGO有三种关系运算符：“=”、“=”。 LINGO中还能用“”表示大于等于关系。,三 关系运算符（续）,LINGO并不支持严格小于和严格大于关系运算符。然而，如果需要严格小于和严格大于关系，比如让A严格小于B：AB， 那么可以把它变成如下的小于等于表达式：A+=B， 这里是一个小的正数，它的值依赖于模型中A小于B多少才算不等。,三类操作符的优先级,高 #not# （取反） #eq# #ne# #gt# #ge# #lt# #le# #and# #or# 低 =,（2） 数学函数,abs(x) 返回x的绝对值 sin(x) 返回x的正弦值，x采用弧度制 cos(x) 返回x的余弦值 tan(x) 返回x的正切值 exp(x) 返回常数e的x次方 log(x) 返回x的自然对数 lgm(x) 返回x的gamma函数的自然对数 sign(x) 如果x=0时，返回不超过x的最大整数；当x0时，返回不低于x的最大整数。 smax(x1,x2,xn) 返回x1，x2，xn中的最大值 smin(x1,x2,xn) 返回x1，x2，xn中的最小值,（3）金融函数,目前LINGO提供了两个金融函数。 fpa(I,n) 返回如下情形的净现值：单位时段利率为I，连续n个时段支付，每个时段支付单位费用。 fpl(I,n) 返回如下情形的净现值：单位时段利率为I，第n个时段支付单位费用。,（4） 概率函数,1）pbn(p,n,x) 二项分布的累积分布函数。当n和（或）x不是整数时，用线性插值法进行计算。 2）pcx(n,x) 自由度为n的2分布的累积分布函数。 3）peb(a,x) 当到达负荷为a，服务系统有x个服务器且允许无穷排队时的Erlang繁忙概率。 4）pel(a,x) 当到达负荷为a，服务系统有x个服务器且不允许排队时的Erlang繁忙概率。 其他概率函数参考LIGNO帮助,(5) 变量界定函数,变量界定函数实现对变量取值范围的附加限制，共4种： bin(x) 限制x为0或1 bnd(L,x,U) 限制LxU free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数 gin(x) 限制x为整数 在默认情况下，LINGO规定变量是非负的，也就是说下界为0，上界为+。free取消了默认的下界为0的限制，使变量也可以取负值。bnd用于设定一个变量的上下界，它也可以取消默认下界为0的约束。,（6）集操作函数,1）in(set_name,primitive_index_1 ,primitive_index_2,) 如果元素在指定集中，返回1；否则返回0。 2）index(set_name, primitive_set_element) 该函数返回在集set_name中原始集成员primitive_set_element的索引。如果set_name被忽略，那么LINGO将返回与primitive_set_element匹配的第一个原始集成员的索引。如果找不到，则产生一个错误。,（6）集操作函数（续）,3）wrap(index,limit) 该函数返回j=index-k*limit，其中k是一个整数，取适当值保证j落在区间1，limit内。该函数相当于index模limit再加1。该函数在循环、多阶段计划编制中特别有用。 4）size(set_name) 该函数返回集set_name的成员个数。在模型中明确给出集大小时最好使用该函数。它的使用使模型更加数据中立，集大小改变时也更易维护。,（7）集循环函数,集循环函数遍历整个集进行操作。其语法为 function(setname(set_index_list)|conditional_qualifier: expression_list); function相应于下面四个集循环函数之一： 1）for 该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。 2）sum 该函数返回遍历指定的集成员的一个表达式的和。 3）min和max 返回指定的集成员的一个表达式的最小值或最大值。,其他函数及菜单,略，请参见教材的相关部分及LINGO帮助文档,3 应用LINGO求解运输问题,定义工厂Plants、配送中心DCs两个原始集和派生集Links 原始集Plants有一个产量属性product，DCs有一个需要量属性demand 因为两个原始集的成员很少，所以采用显示罗列的方法以加强模型的可读性。 派生集有成本cost和运量volume两个属性，product、demand、cost、volume四个属性中前三个是已知的，作为输入参数在数据部分给出具体数值，volume是待求解的未知决策变量。 例1的程序代码及计算见LINGO文件,6.4 运输问题变形的一些应用,1 不平衡运输问题 一、不平衡运输问题的模型 在例1的食品公司运输问题当中，三个工厂的总产能（供应量）是400箱，四个配送中心的总需求量也是400箱，这类总供应量正好与总需求量相等的问题叫做平衡运输问题 运输问题的可行解特性、整数解性质等也是以产销平衡，即 为前提的 然而，在实际的生产生活中，总供应量超过总需求量或小于总需求量的不平衡运输问题，即 更有可能发生 不平衡型运输问题有以下两种情况,1)当总供应量大于总需求量时，,2)当总供应量小于总需求量时，,二、不平衡运输问题举例,例2 若第一节中L食品公司的A工厂2009年6月份的野山菌罐头产量增加到120箱，配送中心的订单不变，总的产量就增加到了120箱，而配送中心的需求量没有变化，使得总供应量比总需求量多了40箱，于是可以假设有一个虚拟配送中心，需求量刚好是40箱，从各罐头厂到虚拟配送中心的运价都是0元/箱。 这个不平衡运输问题在Excel电子表格中的布局、公式编辑、求解选项设置及求解结果见图6.3,2 转运问题,前述运输问题产地与销地的界线非常分明，产地只供给（输出）货物，销地只需求（输入）货物，而实际上，绝对的输出与输入几乎是不存在的，有时一地仅作为其他两地之间输入输出的中转站，更多的是有些产地的货物可以或必需直达运输，而另外有些必需或可以经过中转站转运，我们称这些类型的运输问题为转运问题。 这里我们只讨论产销平衡的转运问题，不平衡的转运问题可以按上节讲到的办法转化成平衡的问题再行研究。,一、转运问题模型,假定有 个产地， 个销地， 个中转站，我们定义如下变量： 第 i 产地 Ai 的供应量，i =1，2，m ； 第 j销地Bj 的需求量， j=1，2，, n； 产地 i到销地 j的单位运费， i=1，2，m ， j=1，2，n ； 产地 i到中转站 k的单位运费， i=1，2， ,m， k=1，2，,p ； 中转站 k到销地 j的单位运费，k =1，2，p ， j=1，2，n ； 产地 i到销地 j的运输数量， i=1，2，m ， j=1，2，n ； 产地i 到中转站 k的运输数量， i=1，2， ,m， k=1，2，,p ； 中转站 k到销地j 的运输数量， k =1，2，p ， j=1，2，n ； 则该问题模型为：,如果所有产地的物资都要经过中转站运到销地，只需要把 的内容去掉就可以，具体如下：,二、L食品公司的转运问题在EXCEL电子表格中的建模与求解,例3 湖南L食品公司的运输部杨经理在寻找最节省的运费过程中发现了位于长沙市和郑州市的两个物流中心，由于这两个物流中心具有专业的农产品运输设施、更为完善的运输网络和先进的管理水平，能以较低的运价为杨经理提供从工厂到配送中心的运输服务。经过洽谈，这两个物流中心为杨经理的运费报价如表6-5、6-6所示。由于杨经理出色的公关技能，他仍然可以利用其他运输公司以前为他提供的运价表（表6-2）上规定的直达运价从工厂到配送中心进行直达运输。为了使运费尽可能的节约，杨经理希望在利用物流中心中转的同时也并不排除从工厂到配送中心的直达运输方式。 杨经理应该如何决策呢？,三、L食品公司的转运问题在LINGO中的建模与求解,定义工厂Plants、物流中心TCs和配送中心DCs三个原始集 原始集Plants有一个产量属性product，DCs有一个需求量属性demand，TCs不需要定义属性。因为三个原始集的成员很少，所以都采用显示罗列的方法以加强模型的可读性。 然后定义工厂直达配送中心的派生集PDlinks、工厂运到物流中心的派生集PTlinks和物流中心转运到配送中心的派生集TDlinks。 派生集PDlinks有成本PDcost和运量PDvolume两个属性； 派生集PTlinks有成本PTcost和运量PTvolume两个属性； 派生集TDlinks有成本TDcost和运量TDvolume两个属性。 模型在lingo程序中例3运输问题的代码和求解结果见lingo文件或教材。,四、一般的转运问题,前文讲到的中转运输问题考虑到了以下两种情况： 产地与销地之间没有直达路线，货物同产地到销地必须通过某中间站转运； 产地与销地之间有直达路线，但也可以通过中转站转运； 更一般的运输问题还会考虑到下面的第三种情况： 某些产地既输出物资，也吸收一部分物资，也就是说相同的物资可以在一些产地之间相互调配；某销地既需要物资，又可以输出部分物资，销地之间也可以相互调配运输。即产地或销地本身也可以起中转站的作用；,四、一般的转运问题,这种转运问题的特点是产地、销地都可能成为中转站，容易造成产量和需求量的混淆，所以解题思路是先将其转化为平衡型运输问题，这一点和不平衡型运输问题是一样的。 首先来看一下转运问题在这个转化中一些假定： 求最大可能中转量 Q（ Q 为大于总产量 的一个数） 纯中转站视为输入量和输出量均为Q 的一个产地和销地 兼中转站 的产地 视为输入量为 Q的销地和输出量为 的产地 兼中转站 的销地 视为输出量为 Q的产地和输入量为 的销地 在此假设的基础上，列出各产地的供应量、各销地的需求量及各产销地之间的运价表，然后运用前文讲到的线性规划法求解即可。,例4 已知某物资的有三个产地A1、A2、A3，四个销地B1、B2、B3、B4，该物资各产地、销地的产量、需求量及运价如下表所示。,表6-7 某物资的产量、需求量,表6-8 某物资的运价表,表6-9 产地间互相调运的运价表,表6-10 销地间互相调运的运价表,另外，还假设这些物资在三个产地之间可以互相调运，在四个销地之间也可以互相调运，其运价表如表6-9、表6-10所示。,表6-11 中转站到产地、销地及中转站之间互相调运的运价表,然后，再假设还有两个纯中转站T1、T2，它们到各产地、各销地及中转站之间的运价表如表6-11所示。,在考虑从产地到销地之间的直接运输、经纯中转站或产销地之间非直接转运等各种可能方案的情况下，如何将三个产地所生产的物资运往四个销地，使总的运费最省。,解：从表6-8可知，从A1 到B3的运费是8，A3 到B3的运费是3，表6-9中A1 到A3的运费是2，这样，从从A1 到B3的运输如果经过A3中转运费是2+3=5，可见这个问题中，从每个产地到各销地之间的运输方案是很多的。为了把这个问题仍当作一般的运输问题处理，可以按下面的方法做： 1）由于问题中的3个产地、2中转站、4个销地都可以既看作产地，又可以看作销地，因此可以把整个问题当作有3+3+4=9个产地和9个销地的扩大运输问题。 2）对扩大的运输问题，建立扩大的单位运价表，如表6-12所示。,表6-12 扩大的单位运价表,3）所有中转站的产量等于销量。由于运费最少时不可能出现一批物资重复在相同的运输路线上来回倒运的现象，所以每个纯中转站的转运数量不会超过总产量19。因此，可以规定两个纯中转站T1、T2的产量和销量均为19。由于实际的转运量,所以，可以在每个约束条件中增加一个松驰变量,，,相当于一个虚拟的转运站，意义就是自己运给自己，,就是每个纯中转站的实际转运量，,对应的运价,4）扩大的运输问题中，原来的产地与销地也有转运站的作用，所以同样在原来产量与销量的数字上加上总产量19，即三个产地A1、A2、A3的产量分别改成27，23，26，销量均为19；四个销地B1、B2、B3、B4的销量分别改成24，22，26，23，产量均为19。同时引入松驰变量,按照上述方法可以重新构成产销平衡的单位运价表，（见表6-12）。由于表6-12是一个产销平衡的运输问题，可以用单纯形法求解，这里略过求解过程，也不再举例，具体可参考本章的例1、例3。,3 运输问题的一些应用,运输问题并非仅仅用来解决实际的运输问题，现实生产和生活中，许多决策问题具有运输问题的特点和性质，或者可以转化成为运输问题。 因为运输问题的算法在求解某些问题时具有较好的效果