运输问题表上作业法

运输问题的解法

运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许多其它问题也归结到这一类问题中。正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。

§1 运输问题的数学模型及其特性

1.1 运输问题的数学模型

设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销地或收地） ，各个发点需要调出的物资量分别为 个单位，各个收点需要调进的物资量分别为 个单位。已知每个发点 到每个收点 的物资每单位运价为 ，现问如何调运，才能使总的运费最小。我们把它列在一张表上（称为运价表）。设 表示从产地 运往 销地的运价（ =1，2，…， ； =1，2，…，

）。

表3-1

如果（总发量） （总收量），我们有如下线性规划问题： mmAAA,,,21nnBBB,,,21maaa,,,21nbbb,,,21iAjBijcijxiAjBimjn

（3.1）

（3.1）式称为产销平衡运输问题的数学模型。当（总发量） （总收量）时。即当产大于销（ ）时，其数学模型为

（3.2）

当销大于产（）时，其数学模型为

（3.3）

因为产销不平衡的运输问题可以转化为产销平衡的运输问题。所以我们先讨论产销平衡的运输问题的求解。

运输问题有个未知量,个约束方程。例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。我们必须寻找特殊解法。

minjijijxcz11min),,2,1;,2,1(0),,2,1(),,2,1(11njmixnjbxmIaxijjmiijinjijnjjmiiba11njjmiiba11minjijijxcz11min),,2,1;,2,1(0),,2,1(),,2,1(11njmixnjbxmIaxijjmiijinjijnjjmiiba11minjijijxcz11min),,2,1;,2,1(0),,2,1(),,2,1(11njmixnjbxmIaxijjmiijinjijmnnmmn 1.2 运输问题的特性

运筹学课程设计报告书

专业

班级

学号

姓名 LMZZ

日期 2011.09.01 设计题目：运输问题的表上作业法

设计方案：运输问题是一种应用广泛的网络最优化模型，该问题的主要目的是为物资调运、车辆高度选择最经济的运输路线。有些问题，如m台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最佳方案。

运输问题的一般提法：

某种物资有m个产地Ai，产量是ai（i＝1，2,…,m），有m个销售地Bi，销量(需求量)是bj(j=1,2,…,m)。若从Ai运到Bi单位运价为dij(i=1,2,…,m;j=1,2,…,m),又假设产销平衡，即

minjjiba11

问如何安排运输可使总运费最小？

若用xij(i=1,2,…,m;j=1,2,…,n)表示由Ai运到Bj的运输量，则平衡运输问题可写出以下线性规划模型： minjijijxdZ11min

约束条件

),...,2,1;...,2,1(0)...,2,1()...,2,1(11njmixnjbxmiaxijmijijnjiij

表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。这些步骤在表上进行十分方便。

第三章 运输问题

主要内容 运输问题的模型、算法

讲授重点 运输问题的模型、算法

讲授方式 讲授式、启发式

第一节 运输问题及其数学模型

一、运输问题的数学模型

设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有n个销地Bl,B2,…,Bn,各销地的销量分别为bl,b2,…,bn。假定从产地Ai(i＝1,2,…,m)向销地Bj(j＝1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?

这是由多个产地供应多个销地的单品种物品运输问题。为直观清楚起见，可列出该出该问题的运输表，如表3-1所示。

表3-1

Bl B2 … Bn 产量

A1 c11 c12 … c1n a1

A2 c21 c22 … c2n a2

… … … … … …

Am cm1 cm2 … cmn am

销量 bl bl … bn

设ijx表示从Ai运往Bj的物品数量，ijc表示从Ai运往Bj的单位物品的运价。则对于平衡运输问题（njjmiiba11），其数学模型的一般形式可表示为：

njmiijijxcs11min

njmixnjbxmiaxijjmiijinjij,2,1;,2,10,,2,1,,2,111 (3.1)

二、运输问题数学模型的特点

对于平衡运输问题(njjmiiba11)，可以证明其有如下两个特点：

(1)矩阵A的秩R(A)＝m+n-1。

(2)问题必有最优解，而且当jiba,皆为整数时，其最优解必为整数最优解。

第二节 表上作业法求解运输问题

一、给出运输问题的初始可行解（初始调运方案）

1、最小元素法

解题步骤：

⑴在运价表中找到最小运价c1k；

⑵将的AL产品给B k； ①若aL>b k，则将aL改写为aL-bk，划掉bk，同时将运价表中K列的运价划掉；

谢荣华、林建、岳钱华、叶俊君

【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个目标。在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法，利用伏格尔法求初始方案，位势法求检验数，闭合回路发对可行解进行调整和改进，直至求出最优解。

【关键词】运筹学、运输问题、改善优化、表上作业法

一、理论依据

运输问题的表上作业法步骤

1、制作初始平衡表

用“西北最大运量，然后，每增加角方法”：即在左上角先给予最大运量，然后，每增加一个运量都使一个发量或手里饱。如果所有运量的数字少于（m+n-1），则补0使之正好（m+n-1）个。

（注:补零时不能使这些书构成圈。）

2、判断初始方案是否最优

（1）求位势表：对运价表加一行一列，圈出运价表中相应于有运量的项，在增加的行列上分别添上数，使这些元素之和等于圈内的元素。这些元素称为位势数。

（2）求检验数，从而得到检验数表。

结论：若对任意检验数小于等于0，则该方案最优，否则进入3进行调整.

3、调整

（1）找回路：在检验数大于0对应的应量表上对应元素为起点，沿横向或纵向前进，如遇到有运量的点即转向，直至起点，可得到一个回路。

（2）找调整量：沿上述找到的回路，从起点开始，在该回路上奇数步数字的最小者作为调整量ε。

（3）调整方式：在该回路上奇数步-ε，偶数步+ε，得到新回路。

重复上述步骤，使所有检验数小于0，即得到最优方案。

二、背景

鉴于市场竞争日益激烈，消费者需求渐趋多样，工厂作为市场消费品的产出源头，唯有对这种趋势深刻理解、深入分析，同事具体的应用于实际中，才能使自身手艺，断发展壮大，不被新新行业所淘汰。对于今天的重点研究对象食品工厂而言，由于在不同产品在原料使用、物料损耗、市场价格等方面均存在各种差异，如何确定各产品的生产配比，以及在最优的生产配比方案之下工厂能够达到最大的产值，都是值得进行探讨研究的现实问题。