Bn x1n x2n … xmn bn
产量 a1 a2 … am
A1 A2
…
Am 销量
产销平衡
m in cij xij
i 1 j 1
m
n
n xij ai j 1 m s.t. xij b j i 1 xij 0i 1,2, , m; j 1,2, , n
3 ）约束条件： x11 x12 x13 x14 5 x 21 x22 x23 x24 2 x31 x32 x33 x34 3 x11 x21 x31 2 s.t . x12 x22 x32 3 x13 x23 x33 1 x14 x24 x34 4 x 0i 1, 2,3; j 1, 2,3, 4 ij
A1，A2，A3；其一级分销商有4个，分布在城市B1，B2，B3 ， B4 。现已知每月各生产工厂的产量、各分销商的需求量；
以及从Ai到Bj的每吨饮料的运费cij（见下表）。
销地 产地
B1
B2
B3
B4
产量
A1
A2 A3 销量
6
7 3
3
5 2
2
8 9
5
4 7
5
2 3
2
3
1
4
为发挥集团优势，公司需要统一筹划运销问题，求使运费最小的 调运方案。
意味着？
• 可以证明：平衡模型的系数阵和增广阵的秩均 为m+n-1，这也意味着平衡模型的基本可行解 所含基变量的个数必为m+n-1个。 • 【结论】
m+n-1
5.2 表上作业法
• 【讨论】上述运输问题所建立的LP模型如果用传统的 单纯形法进行求解会出现什么情况？ • 【友情提示】 1）表上作业法仅仅适用于产销平衡的运输问题
和库普曼（Koopmans，1947）提出。
• 中国 ——“图上作业法”（1958年）
• 1975年康托洛维奇和库普曼因资源配置理论研究获得
诺贝尔经济学奖（丹茨格）（24、12、4）（日内瓦国
际应用系统分析研究所）
• 运输模型是线性规划诸多模型中的特例，其约束方程 组对应的系数矩阵具有特殊的结构，使得有可能找到 比单纯形法更为简便的求解方式。 • 运输问题的专门求解方法不仅适用于运输问题本身，
i 1 j 1
n xij ai j 1 m s.t. xij b j i 1 xij 0i 1,2,, m; j 1,2,, n
【运输模型 系数矩阵】
1 1 1 1 1 1 1 1 1 A 1 1 1 1 1 1 1 1 1
2）表上作业法基于一种作业表 —— “产销平衡及运价表”
特征？
• 用单纯形法求解LP式运输模型，必须删掉一个函数约 束，而且计算量很大，但表上作业法不必如此费力， 而是另辟蹊径。 • 表上作业法是一种专门求解运输问题的特殊方法，其 实质仍是单纯形法，只是具体计算和术语有所区别。 • 与一般的LP问题不同的是，平衡运输问题总是存在最 优解。
运输问题的一般提法：
设某种物资有m个产地 Ai i 1,2, , m ，其产量分别为
a i ；有n个销地 B j j 1,2,, ，其销量分别为 b j ；
从Ai 到 B j 的单位运价为 cij 。
问应该如何组织调运才能使总的运费最少？
设
xij 为把这种物资从Ai运到Bj的数量，简称
产大于销
m n
m in cij xij
i 1 j 1
n xij ai j 1 m s.t. xij b j i 1 xij 0i 1,2,, m; j 1,2,, n
产小于销
m n
m in cij xij
3）“产量”——各产地的可供货量 4）“销量”——各销地的需求数量
• 【运输问题的描述】
• 运输问题就是研究如何组织调运，在满足各销地需
求的前提下，追求总的运费（或里程、时间等）达
到最少？
• 运输问题所建立的模型就称为运输模型。
5.1 运输问题及其数学模型
【例1】 某饮料集团在国内有3个生产工厂，分布在城市
还适用于其他相当多的应用问题（如指派问题），更
使其得到人们的高度重视和深入的系统研究。
在经济建设中经常会碰到大宗物资的调运问题。如 煤、铁、木材、粮食等大宗物资，在全国有若干生产基 地，根据现已有的交通网络，应该如何制定调运方案，
将这些物资运往各消费地点。
1）“产地”——货物发出的地点
2）“销地”——货物接收的地点
解：建立该运输问题的LP模型如下
1 ）决策变量： 设xij为每月从产地 Ai到销地B j的数量（吨） 2）目标函数： m in 6 x11 3x12 2 x13 5 x14 7 x21 5 x22 8 x23 4 x24 3x31 2 x32 9 x33 7 x34
第5章 运输模型
• 5.1 运输问题及其数学模型 • 5.2 表上作业法
• 5.2.1 初始方案的确定 • 5.2.2 最优性检验 • 5.2.3 非最优方案的调整 • 5.2.4 产销不平衡问题的解法
• 5.3 运输模型的应用
• 运输模型是线性规划诸多模型中较早引起人们关注的
一类模型，由美国学者希奇柯克（Hitchcock，1941）
为Ai至Bj的运量；设z为总运费，则一般运输问 题及其数学模型可以简洁地表示为下表这种形 式，称为表格形式的一般运输模型，简称表式
运输模型。
p136
表式运输模型
销地 产地
B1 c11 c21 x11 x21 … cm1 b1 xm1 cm2 c12 c22
B2 x12 x22 … xm2 b2
… … … … … … cmn c1n c2n
m
行
n
行
• 【讨论】运输模型系数矩阵的特征？
• [表面]任意一个运输模型系数矩阵同一个与之规模相当
的普通LP模型的系数矩阵相比都大为简洁，且其中只含
有0和1这两个元素，且0的个数远远多于1的个数，一般
我们把这样的矩阵称为稀疏阵。
• [深层次]对任意产销平衡的运输模型来说，其系数阵的 前m行之和等于后n行之和。