- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2018/10/27 7
表3-2 销地 产地 A1 A2
B1 3
B2 4
B3 2 6 x13 3
产量
10-6=4 10 4-3=1 1-1=0
x 311
x21 0 3
x12 1
x22 4 5
x0 23
4-4=0 4
4-4=0 3-3=0 5-1=4 6-6=0 3 5 6 销量 min z 3x11 4 x12 2 x13 3x21 5 x22 3x23
第三章
运输问题
讲四节： 第一节 第二节 运输问题及其数学模型 用表上作业法求解运输问题
第三节
第四节
2018/10/27
运输问题的进一步讨论
应用问题举例
1
§3-1 运输问题及其数学模型
一、运输问题的数学模型
设某物品有m个产地A1, A2 ,…, Am；各产地的产量
分别是a1,a2,…,am；有n个销地B1, B2,…, Bn。各销地 的销量分别是 b1,b2,…,bn ；假如从产地 Ai(i=1,2,…,m) 向销地Bj( j= 1,2,…,n)运输单位物品的运价是cij；问怎 样调运这些物品才能使总运费最小？
解题思路： （1）假设变量 （2）分析约束 （3）明确目标 （4）建立模型 （5）求解变量 （6）x12 x13 10 x x x 4 23 21 22 x11 x21 3 x12 x22 5 x13 x23 6 2018/10/27 x11 , x12 , x13 , x21 , x22 , x23 0
2018/10/27 4
二、运输问题的数学模型的特点
1.运输问题有有限最优解 对运输问题的数学模型，若令变量 ai b j xij , i 1,2,, m; j 1,2,, n Q 其中： Q ai b j
i 1 j 1 m n
是运输问题的 一个可行解
另外，在运输问题的数学模型中,目标函数是取最小值,它 的值不会趋于无穷大, 在实际问题中也不可能出现这种情况 , 因此,运输问题有有限最优解。 对运输问题数学模型的约束条件进行整理,得其系数矩阵 的结构形式为：
2018/10/27 5
2.运输问题约束条件的系数矩阵
x11 1 x12 x1n 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x21 x22 x2 n xm1 xm 2 xmn
m行
n行
系数列向量的结构：
第i个
第(m+j)个
T
Aij 0,,0,1,0,,0,1,0,,0
由某一产地运往各 个销地的物品数量 之和等于该产地的 产量
由各个产地运往某 一销地的物品数量 之和等一该销地的 销量 非负条件
非负约束
这是一个线性规划问题，可以用单纯形法求解。 但是，由于它所含变量多，求解极不方便。即使求解一个 m＝3，n＝4的简单运输问题，变量数目也将达到19个之多。 因此，必须寻找更简便的求解方法。
2018/10/27
称 为 产 销 平 衡 运 输 问 题
A2
┇
Am
┇
xm 1
┇
xm 2
┅
┅
┇
am
xmn
销量
b1
b2
┅
bn
2018/10/27
变量 xij( i = 1,2,..,m;j = 1,2,…,n )为由产地 Ai 运往销地 Bj 的物品数量。 m n m n ai b j ai b j
即除第i个和第( m + j )个分量为1外，其它分量全等于0。
2018/10/27 6
运输问题的特点:
(1) 约束条件系数矩阵的元素等于0或1； (2) 约束条件系数矩阵的每一列有两个非零元素，对应于 每一个变量在前 m 个约束方程中出现一次,在后 n 个约束方 程中也出现一次。 如果是产销平衡运输问题,还有以下特点： （3）所有结构约束条件都是等式约束； （4）各产地产量之和等于各销地销量之和。 例1 某种物品先存放在两个仓库A1和A2中，再运往三个 使用地B1，B2，B3，其间的运距（或单位运价）如表3-2小方 格中的数据所示，试建立使总运输量（或总运费）最小的运 输问题数学模型。
i 1 j 1
称 为 产 销 不 平 衡 运 输 问 题
i 1
j 1
3
产销平衡运输问题的数学模型 极小化
min z cij xij
i 1 j 1 m n
总运输费用 产量约束 销量约束
n xij ai ; i 1,2,...,m 1 jm xij b j ; j 1,2,...,n i 1 xij 0 ; i 1,2,...,m; j 1,2,...,n
显然 x11=3,x12=1,x13=6,x22=4, x21=0,x23=0 是 该 运 输 问 题的一个可行解。 目标函数值z = 45
8
§3-2 用表上作业法求解运输问题
它是求解运输问题的一种简便而有效的方法,其求解过程 在运输表上进行,它是一种迭代法,其步骤为： 1. 先按某种规划找出一个初始解(初始调运方案）； 2. 对现行解作最优性判别； 3. 若不是最优解 ,就在表上对它进行调整改进 ,得出一个 新解； 4. 再判别,再改进,直到得到运输问题的最优解为止； ※在迭代过程中,得出的所有解都要求是运输问题的基可 行解。 例2 某部门有3个生产同类产品的工厂（产地），生产 的产品由4 个销售地出售，各工厂的生产量，各销售地的销 售量（假定单位均为吨）以及各工厂到各销售地的单位运价 （元/吨）示于表3-4中，要求研究产品如何调运才能使总运 费最小？
这个问题是一个多产地多销地的单品种物品运输
问题。把这个问题整理成为一个表,称之为运价表。 （见下页）
2018/10/27
返回第三章目录
2
表3-1 运价表
销地 产地 A1 x11 x21 B1 c11 c21 … cm1 x12 x22 B2 c12 c22 … cm2 ┅ ┅ ┅ … … … … x1n x2n Bm c1 n c2 n … cmn 产量 a1 a2
