《运筹学》运输问题-特殊的线性规划培训课件

第三章运输问题

—特殊的线性规划&模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广产销不平衡的运输问题转运问题

一、运输问题的数学模型1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？3.1运输问题的典例和数学模型例1：产量：A1-7t，A2-4t，A3-9t

销量：B1-3t，B2-6t，B3-5t，B4-6tBjAiB1B2B3B4产量A13113107A219284A3741059需量365620单位根据具体问题选择确定。

产销平衡、单位运价表（表3-1）单位运价销或运距地产地

B1B2…Bn

产量

A1A2┆Am

c11c12…c1nc21c22…c2n………cm1cm2…cmn

a1a2┆am

销量

b1b2…bn

2、运输问题的数学模型

设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：

同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：

总运费为：

运输问题的数学模型二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行矩阵的元素均为1或0；

每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。

将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。例1的数学模型三、运输问题的求解方法1、单纯形法（为什么？）2、表上作业法

由于问题的特殊形式而采用的更简洁、更方便的方法3.2运输问题的表上作业法

一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。

确定初始方案(初始基本可行解)

改进调整（换基迭代）否

判定是否最优？是结束最优方案图3-1运输问题求解思路图

二、初始方案的确定

1、作业表（产销平衡表）

初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。

表3-2是两个产地、三个销地的运输问题作业表。调销地运量产地

B1B2B3

产量A1c11

X11c12

X12

c13

X13a1

A2c21

X21c22

X22c23

X23a2

销量

b1b2b3表3-2运输问题作业表（产销平衡表）

其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个产地到第j个销地的单位运价或运距。2、确定初始方案的步骤：（1）选择一个xij，令xij=min{ai，bj}=将具体数值填入xij在表中的位置；（2）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij=0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。

按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。

对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。

3、举例

例1：产量：A1-7t，A2-4t，A3-9t

销量：B1-3t，B2-6t，B3-5t，B4-6t

；求使总运输量最少的调运方案。BjAiB1B2B3B4产量A13113107A219284A3741059需量3656201、最小元素法:

求出初始方案。&最小元素法的基本思想是“就近供应”BjAiB1B2B3B4产量A13113107A219284A3741059需量365620用最小元素法确定例1初始调运方案

3114436333最小元素法实施步骤口诀《运价表》上找最小，《平衡表》上定产销；满足销量划去“列”，修改“行产”要记牢；（满足产量划去“行”，修改“列销”要记牢）划去列(行)对《运价》，修改“行产(列销)”在《产销》；余表再来找最小，方案很快就找到。2、Vogel法(元素差额法):求出初始方案。第一步：在表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。

用Vogel法确定初始调运方案

BjAiB1B2B3B4产量行差额A13113107A219284A3741059需量365620列差额

Bj

AiB1B2B3B4产量A1××527A23××14A3×6×39需量365620

三、最优性检验

检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。1、闭回路法

以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。

该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。闭回路法计算非基变量xij检验数的公式：=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）当检验数还存在负数时，说明原方案还不是最优解。闭回路法—最小元素法初始方案

B1B2B3B4产量A13113107A219284A3741059需量365620

B1B2B3B4产量A1××437A23×1×4A3×（10）6×39需量365620检验数

B1B2B3B4产量A1×（1）×（2）437A23×（1）1×（－1）4A3×（10）6×（12）39需量3656202、位势法

以例1初始调运方案为例，设置位势变量和，在初始调运方案表的基础上增加一行和一列。

BjAiB1B2B3B4ujA1311310u1A21928u2A374105u3viv1v2v3v4检验数各空格的检验数，令代表空格（Ai,Bj）的检验数。①当检验数还存在负检验数时，说明未得到最优解，还可以改进。②如果表中出现有负的检验数时，对方案进行改进和调整的访求同前面闭回路法调整一样。方案调整—闭回路法

B1B2B3B4产量A1×（1）×（2）437A23×（1）1×（－1）4A3×（10）6×（12）39需量365620调整结果

B1B2B3B4产量A1×（0）×（2）527A23×（2）×（1）14A3×（9）6×（12）39需量365620位势法计算非基变量xij检验数的公式=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）闭回路法计算非基变量xij检验数的公式：复习比较检验数计算的两种方法

四、方案调整

当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。若检验数小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量ε：ijε=min{该闭回路中奇数次顶点调运量xij}3.3运输问题的推广一、产销不平衡的运输问题供大于求供不应求增加虚拟销地

增加虚拟产地

产销平衡的运输问题对应的运距（或运价）

？转化二、转运问题特点是所调运的物资不是由产地直接运送到销地，而是经过