第三章 运输规划--表上作业法

表上作业法什么是表上作业法表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。

是线性规划一种求解方法。

当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭合回路法、位势法等方法进行调整，直至得到满意的结果。

这种列表求解方法就是表上作业法。

表上作业法的步骤1、找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；（1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。

然后按行（列）标下一格的数。

若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。

如此进行下去，直至得到一个基本可行解。

（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。

然后按运价从小到大顺序填数。

若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。

如此进行下去，直至得到一个基本可行解。

注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。

当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。

2、求出各非基变量的检验数，判别是否达到最优解。

如果是停止计算，否则转入下一步，用位势法计算；运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。

其对偶问题也应有m+n个变量，据此：σij = c ij− (u i + v j) ,其中前m个计为,前n个计为由单纯形法可知，基变量的σij = 0c ij− (u i + v j) = 0因此u i,v j可以求出。

3、改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。

基变量的检验数σij = 0，非基变量的检验数。

运输问题的求解方法(过程)——表上作业法的解题思路和原理、具体步骤。

运输问题是指在给定的供应地和需求地之间，选择最佳的运输方案，使总运输成本最低的问题。

表上作业法是一种常用的解决运输问题的方法，它基于线性规划的思想，通过逐步逼近最优解的方式来求解运输问题。

表上作业法的原理是将运输问题转化为一个线性规划问题，通过构建一个供需平衡表来描述运输问题。

在该表中，将供应地和需求地分别作为行和列，并在表中填入运输量的变量。

同时，引入一个辅助表来记录每个供应地和需求地的运输量。

具体的求解步骤如下：1. 构建供需平衡表：将给定的供应地和需求地以及对应的运输量填入表格中，并计算每个供应地和需求地的供应总量和需求总量。

2. 确定初始基本可行解：根据运输量的限制条件，确定一个初始的基本可行解。

可以选择将某些运输量设置为0，使得每个供应地和需求地都满足其供应总量和需求总量。

3. 计算单位运输成本：根据给定的运输成本，计算每个供应地和需求地之间的单位运输成本，填入表格中。

4. 判断最优解条件：检查当前的基本可行解是否满足最优解的条件。

如果每个供应地和需求地都满足其供应总量和需求总量，并且没有其他更低成本的运输方案，则当前解为最优解。

5. 迭代改进解：如果当前解不满足最优解的条件，则需要进行迭代改进。

在每一次迭代中，选择一个非基本变量（即非0运输量）进行改变，并计算改变后的基本可行解。

6. 更新供需平衡表和辅助表：根据改变后的基本可行解，更新供需平衡表和辅助表的运输量，并重新计算单位运输成本。

7. 重复步骤4-6，直到找到最优解为止。

通过以上的步骤，表上作业法能够有效地求解运输问题，并得到最优的运输方案。

它在实践中广泛应用于物流管理、供应链优化等领域，为运输问题的决策提供了科学的依据。

第三章 运输问题的解法运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许多其它问题也归结到这一类问题中。

正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。

§1 运输问题的数学模型及其特性1.1 运输问题的数学模型设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销地或收地），各个发点需要调出的物资量分别为个单位，各个收点需要调进的物资量分别为 个单位。

已知每个发点到每个收点的物资每单位运价为 ，现问如何调运，才能使总的运费最小。

我们把它列在一张表上（称为运价表）。

设 表示从产地运往销地的运价（ =1，2，…， ； =1，2，…， ）。

表3-1如果（总发量）（总收量），我们有如下线性规划问题：m mA A A ,,,21 n nB B B ,,,21 ma a a ,,,21 nb b b ,,,21 iA jB ijc ijx iA jB i m jn（3.1）（3.1）式称为产销平衡运输问题的数学模型。

当（总发量）（总收量）时。

即当产大于销（）时，其数学模型为（3.2）当销大于产（）时，其数学模型为（3.3）因为产销不平衡的运输问题可以转化为产销平衡的运输问题。

所以我们先讨论产销平衡的运输问题的求解。

运输问题有个未知量,个约束方程。

例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。

我们必须寻找特殊解法。

1.2 运输问题的特性∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==≠nj jm i i ba 11∑∑==>nj jm i i ba 11∑∑===mi nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij ∑∑==<nj jm i i ba 11∑∑===m i nj ijij x c z 11min ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=≤==∑∑==),,2,1;,2,1(0),,2,1(),,2,1(11n j m i x n j b x m I a x ij j mi ij i nj ij mn n m +m n由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一定可以在基可行解中找到。

第三章运输问题第三章运输问题本章内容重点：●运输问题与有关概念●运输问题的求解—表上作业法●运输问题应⽤—建模第⼀节运输问题模型及有关概念问题的提出：⼀般的运输问题就是要解决把某种产品从若⼲个产地调运到若⼲个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定⼀个使得总的运输费⽤最⼩的⽅案。

例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所⽰，问：应如何调运可使总运输费⽤最⼩？解：产销平衡问题：总产量 = 总销量设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：Min f = 6x11+4x12+6x13+6x21+5x22+5x23s.t. x11+ x12 + x13 = 200x21 + x22+ x23 = 300x11 + x21 = 150x12 + x22 = 150x13 + x23 = 200xij≥0(i=1,2；j=1,2,3）系数矩阵1 1 1 0 0 00 0 0 1 1 11 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1模型系数矩阵特征1.共有m+n⾏，分别表⽰各产地和销地；m n列，分别表⽰各决策变量；2.每列只有两个 1，其余为 0，分别表⽰只有⼀个产地和⼀个销地被使⽤。

⼀般运输问题的线性规划模型及求解思路：⼀般运输问题的提法：假设 A1, A2,…,Am表⽰某物资的m个产地；B1,B2,…,Bn表⽰某物资的n个销地；si 表⽰产地 Ai的产量；dj表⽰销地 Bj的销量；cij表⽰把物资从产地 Ai运往销地 Bj的单位运价（表4-3）。

如果s1 + s2+ … + sm= d1+ d2+ … + dn则称该运输问题为产销平衡问题；否则，称产销不平衡。

⾸先讨论产销平衡问题。

表4-3 运输问题数据表设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建⽴运输变量表（表4-4）。