文档介绍：2017/11/11
制作与教学---陈慧青
1
第3章 运输问题
运筹学课件
2
第1节运输问题的数学模型
第2节表上作业法
第3节产销不平衡的运输问题
第4节应用举例
运筹学课件
※结束
♂返回
运输问题
3
第 1 节运输问题的 数学模型
已知有m个生产地点Ai,i=1,2,…,m。可供应某种物资,其供应量(产量)分别为ai,i=1,2,…,m,有n个销地Bj,j=1,2,…,n,其需要量分别为bj,j=1,2,…,n,从Ai到Bj运输单位物资的运价(单价)为cij,这些数据可汇总于产销平衡表和单位运价表中,见表3-1,表3-2。有时可把这两表合二为一。
4
销地
产地
1 2 ┉ n
产量
1
2
┆
m
a1
a2
┆
am
销量
b1 b2 ┈ bn
表3-1
第 1 节运输问题的 数学模型
5
表3-2
第 1 节运输问题的 数学模型
6
运输问题的数学模型 若用xij表示从Ai到Bj的运量,那么在产销平衡的条件下,要求总运费最小的调运方案,数学模型
第 1 节运输问题的 数学模型
7
它包含m×n个变量,(m+n)个约束方程。其系数矩阵的结构比较松散,且特殊。
第 1 节运输问题的 数学模型
8
该系数矩阵中对应于变量xij的系数向量Pij,其分量中除第i个和第m+j个为1以外,其余的都为零。即Pij=(0,…,1,0,…,0,1,0,…,0)T=ei+em+j
对产销平衡的运输问题,由于有以下关系式存在:
第 1 节运输问题的 数学模型
♂返回
9
表上作业法是单纯形法在求解运输问题时的一种简化方法,其实质是单纯形法。但具体计算和术语有所不同。可归纳为:
(1) 找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法,Vogel法给出m+n-1个数字,称为数字格。它们就是初始基变量的取值。
(2) 求各非基变量的检验数,即在表上计算空格的检验数,判别是否达到最优解。如已是最优解,则停止计算,否则转到下一步。方法有闭回路法和位势法。
(3) 确定换入变量和换出变量,找出新的基可行解。在表上用闭回路法调整。
(4) 重复(2),(3)直到得到最优解为止。
第 2 节 表 上 作 业 法
10
例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是:A1为7吨,A2为4吨,A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为:B1为3吨,B2为6吨,B3为5吨,B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品,在满足各销点的需要量的前提下,使总运费为最少。
第 2 节 表 上 作 业 法