运筹学课件------3-第三章 运输问题.ppt

第三章运输问题 —数学模型及其解法
顺风而呼,声非加疾也,而闻者彰。假舆马者,非利足也,而致千里;假舟楫者,非能水也,而绝江河。君子生非异也,善假于物也。荀子《劝学》
©管理与人文学院忻展红
1999,4
1
运输问题的一般数学模型
有m个产地生产某种物资,有n个地区需要该类物资
令a1, a2, …, am表示各产地产量, b1, b2, …, bn表示各销地的销量,ai=bj 称为产销平衡
设xij表示产地 i 运往销地 j 的物资量,wij表示对应的单位运费,则我们有运输问题的数学模型如下:
运输问题有mn个决策变量,m+n 个约束条件。由于产销平衡条件,只有m+n–1个相互独立,因此,运输问题的基变量只有m+n–1 个
2
运输问题的求解方法
约束条件非常有规律,技术系数非 0 即 1
基变量的个数远小于决策变量的个数
采用表上作业法,称为位势法和踏石法
运算中涉及两个表:运费表和产销平衡表(分配表)
3
寻找初始可行解的方法
1、西北角法
从 x11开始分配,从西北向东南方向逐个分配
xij 的分配公式

4
西北角法
5
2、最低费用法
采用最小费用优先分配的原则,看一步
f(x)=121,比
西北角法低
84
6
3、运费差额法
采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则,看两步
f(x)=98,比
最低费用法
又低了23
7
利用位势法检验分配方案是否最优
不采用单纯型法,如何获得xij的检验数
找到原问题的基础可行解,保持互补松弛条件,求出对应对偶问题的解,若该对偶问题的解非可行,则原问题的解不是最优解;否则,达到最优解
8
9
位势法的原理
为满足互补松弛条件,原问题中xij被选为基变量,即xij0,则要求对偶问题中ui+vj=wij,即该行的松弛变量为0
共有m+n1个基变量xij ,因此可得m+n1个等式 ui+vj=wij
m+n1个等式只能解出 m+n1个 ui 和 vj ,而一共有m+n个 ui 和 vj ,但可令任一个ui 或 vj =0,从而解出其它 m+n1个的值;这就是位势法
令 zij= ui + vj ,其相当原问题xij的机会费用
若对所有非基变量有 zij  wij  0,即 ui + vj  wij,表明当前ui 和 vj 是对偶问题的可行解,由互补松弛定理可知当前m+n1个基变量xij 是最优解,否则
从 zij  wij > 0 中找最大者,对应 xij 就是入变量
10