运输问题及解法

运输问题及解法运输问题的一般提法是：

1.产销平衡问题

第2页,共42页，2024年2月25日，星期天2.产销不平衡问题此时分为两种情形来考虑：供不应求：即产量小于销量时有

供过于求：即产量大于销量时有第3页,共42页，2024年2月25日，星期天二.运输问题的模型产销平衡问题模型第4页,共42页，2024年2月25日，星期天将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。第5页,共42页，2024年2月25日，星期天第6页,共42页，2024年2月25日，星期天第7页,共42页，2024年2月25日，星期天2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。第8页,共42页，2024年2月25日，星期天三.运输问题的解法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：

1.运输问题所涉及的变量多，造成单纯形表太大；

2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。第9页,共42页，2024年2月25日，星期天表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始可行调运方案。可以通过最小元素法、Vogel法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。第10页,共42页，2024年2月25日，星期天（Ⅰ）运输问题的常用解法：最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整）以下面例题说明这种方法的具体步骤：例12：某食品公司下设3个加工厂A1，

A2，A3，和4个门市部B1，

B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？第11页,共42页，2024年2月25日，星期天运输问题一般用表上作业法求解，需建立表格模型：单位运价表产销平衡表用线性规划法处理此问题。设由产地i到销地j的运量为xij，模型为：minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)第12页,共42页，2024年2月25日，星期天给出初始调运方案最常用的方法——最小元素法314633初始方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)第13页,共42页，2024年2月25日，星期天表上作业法要求，调运方案的数字格必须为m+n-1个，且所有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。闭回路:从方案中某一始格出发，沿同行或同列前进，当遇到一个数字格时可以可转90度或继续前进，按此方法进行，直到回到始点的一个封闭曲线。同行或同列最多有两个点。第14页,共42页，2024年2月25日，星期天最小元素法中的退化情况360542出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。第15页,共42页，2024年2月25日，星期天

①找出任意空格的闭回路—除此空格外，其余顶点均为有数格。如可找（A1

B1

）→（A1

B3

）→（A2

B3）→（A2

B1

）；

2.检验（闭回路法:计算空格的检验数）②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。如σ11＝c11

-c13+c23-c21=1

314633第16页,共42页，2024年2月25日，星期天③计算出此空格的检验数σij,若σij≥０，则该方案为最优方案，否则转３；

注：检验数的经济意义，以σ11为例，空格表示原方案中X11=0,即A1→B1

的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是σ11，可见检验数σij的意义是：

Ai

→

Bj增运１单位所引起的总费用的增量。

σij>０，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在

Ai

→

Bj上增运。第17页,共42页，2024年2月25日，星期天3.调整:从σij为最大正值的空格出发.对其闭回路上的奇数顶点运量增加θ,偶数顶点的运量减少θ(这才能保证新的平衡)，其中θ为该空格闭回路中偶数顶点的最小值。∵σ24=-1<0，∴从（A2

B4）出发其闭回路上θ=1，调整后得到一个新方案（如下表），运量为θ=1的（A2

B3）变空格，得到新方案后再转

2。σ11=1，σ12=2σ22=1，σ24=-1σ31=10，σ33=12314633第18页,共42页，2024年2月25日，星期天经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为θ，则调整后其中一个变空格，其余填0。（保证基变量个数不变）

3

6

1

3

2

5第19页,共42页，2024年2月25日，星期天2.确定初始方案的方法之二—伏格尔法（Vogel法）⑴求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；

⑵如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，即得最优方案。第20页,共42页，2024年2月25日，星期天3635122762第21页,共42页，2024年2月25日，星期天3.求空格检验数的方法之二—位势法原理：设有运输问题的对偶问题为第22页,共42页，2024年2月25日，星期天

3146333101245仍以例一为例：对偶变量表面上是7个，实际上只有6个。∴有一个是自由变量。第23页,共42页，2024年2月25日，星期天当找出σij<0的格后，调整方法仍用闭回路法。位势法步骤：

①由有数格cij=ui+vj求得ui和vj（先令u1=0），原有数格（基变量）的检验数σij=0；

②空格σij=cij—

(ui+vj)；

③由此可得检验数表。第24页,共42页，2024年2月25日，星期天（Ⅲ）产销不平衡的运输问题1.产大于销的情况：添加松弛变量xi,n+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地—Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即Ai的剩余量。第25页,共42页，2024年2月25日，星期天A1AmB1……BnBn+1C1100C1nCm1Cmn产大于销的单位运价表产大于销的产销量表A1Ama1amB1……BnBn+1b1……bn第26页,共42页，2024年2月25日，星期天2.销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。第27页,共42页，2024年2月25日，星期天销大于产的产销量表A1Ama1amB1……Bnb1……bnAm+1A1AmB1……BnC1100C1nCm1Cmn销大于产的单位运价表Am+1……第28页,共42页，2024年2月25日，星期天四应用举例由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。第29页,共42页，2024年2月25日，星期天例3某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-29所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策。第30页,共42页，2024年2月25日，星期天解由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足第31页,共42页，2024年2月25日，星期天又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：第32页,共42页，2024年2月25日，星期天第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见表3-30。第33页,共42页，2024年2月25日，星期天设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：

第34页,共42页，2024年2月25日，星期天显然，这是一个产大于销的运输问题模型。注意到这个问题中当i＞j时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见表3-31)。

第35页,共42页，2024年2月25日，星期天经用表上作业法求解，可得多个最优方案，表3-32中列出最优方案之一。即第Ⅰ季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台，用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货。Ⅳ季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。第36页,共42页，2024年2月25日，星期天例4某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数

见表3-33。第37页,共42页，2024年2月25日，星期天假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-34。第38页,共42页，2024年2月25日，星期天又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足