江西财经大学:《运筹学》课程教学资源(PPT课件)第三章 运输问题——数学模型及其解法

CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第三章运输问题 数学模型及其解法 顺风而呼,声非加疾也,而闻者彰。 假舆马者,非利足也,而致干里;假舟 楫者,非能水也,而绝江河。君子生非 异也,善假于物也。 荀子《劝学》
第三章 运输问题 — 数学模型及其解法 顺风而呼,声非加疾也,而闻者彰。 假舆马者,非利足也,而致千里;假舟 楫者,非能水也,而绝江河。君子生非 异也,善假于物也。 荀子《劝学》 ©管理与人文学院 忻展红 1999,4

3运输问题的一般数学模型 有m个产地生产某种物资,有n个地区需要该类物资 令a1,a2,…,an表示各产地产量,b1,b2…,b表示各销 地的销量,Σ∑b称为产销平衡 设x;表示产地i运往销地j的物资量,w/表示对应的单 位运费,则我们有运输问题的数学模型如下: minf(x)=∑∑w 运输问题有mn个 决策变量,m+n个 约束条件。由于产 a1i=1.2,…,m产地约束销平衡条件,只有 m+n-1个相互独立 12…,n销量约束因此,运输问题的 基变量只有m+n1 ≥0 个
2 3.1 运输问题的一般数学模型 • 有m个产地生产某种物资,有n个地区需要该类物资 • 令a1 , a2 , …, am表示各产地产量, b1 , b2 , …, bn表示各销 地的销量,ai=bj 称为产销平衡 • 设xij表示产地 i 运往销地 j 的物资量,wij表示对应的单 位运费,则我们有运输问题的数学模型如下: = = = = = = = = = 0 1,2, , 1,2, , min ( ) 1 1 1 1 i j j m i i j n j i j i m i n j i j i j x x b j n x a i m f x w x 销量约束 产地约束 运输问题有mn个 决策变量,m+n 个 约束条件。由于产 销平衡条件,只有 m+n–1个相互独立, 因此,运输问题的 基变量只有m+n–1 个

32运输问题的求解方法 约束条件非常有规律,技术系数非0即1 基变量的个数远小于决策变量的个数 采用表上作业法,称为位势法和踏石法 运算中涉及两个表:运费表和产销平衡表(分配表) 镅销地 销地 产量 费 2 n运量 n 产地 产地 W1 w12 n in W2122 w2n wml m2 , m1-m2 销量bb1b2
3 3.2 运输问题的求解方法 • 约束条件非常有规律,技术系数非 0 即 1 • 基变量的个数远小于决策变量的个数 • 采用表上作业法,称为位势法和踏石法 • 运算中涉及两个表:运费表和产销平衡表(分配表) 销 地 运 费 1 2 n 产 地 1 w11 w1 2 w1n 2 w2 1 w2 2 w2n m wm1 wm2 wm n

321寻找初始可行解的方法 1、西北角法 从x1开始分配,从西北向东南方向逐个分配 x的分配公式 (a1-行已分配的总量)=i行尚余物资量 x,=m(b-列已分配的总量)=/列待分物资量 例321 销地 产量 费地 12011365 5910210 31874115 销量b33122
4 3.2.1 寻找初始可行解的方法 1、西北角法 – 从 x11开始分配,从西北向东南方向逐个分配 – xij 的分配公式 − = − = = 列已分配的总量 列待分物资量 行已分配的总量 行尚余物资量 ( ) ( ) min b j j a i i x j i i j 例3.2.1 销 地 产 量 运 费 1 2 3 4 ai 产 地 1 2 0 11 3 6 5 2 5 9 1 0 2 1 0 3 1 8 7 4 1 1 5 销 量 bj 3 3 1 2 1 2

例321西北角法 销地 里 量地 234 32 93 10 1215 销量b331212 m+n=7有6个基变量(x)=∑∑nx=205
5 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 5 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 例3.2.1 西北角法 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 x1 2 5 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 x2 2 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 x2 3 1 0 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 x3 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 3 x3 3 1 5 销 量 bj 3 3 1 2 1 2 销 地 产 量 运 量 1 2 3 4 ai 产 地 1 3 2 5 2 1 9 1 0 3 3 1 2 1 5 销 量 bj 3 3 1 2 1 2 = = + = = = 3 1 4 1 7 6 ( ) 205 i j i j i j m n 有 个基变量 f x w x

2、最低费用法 采用最小费用优先分配的原则,看一步 编号 运费表{wn} 分配表{x} 2011(3)6 59102 10 18741 1215 331212 「编号运费表{wn} 分配表{x} 201136 5 5 59102 10 187(4) 31215 331212 编号 运费表{wn 分配表{x} 201136 5 5|c)=121,比 Ⅲ159(10)2334 10 西北角法低 18741 31215 84 331212
6 2、最低费用法 • 采用最小费用优先分配的原则,看一步 编 号 运费表{wi j} 分配表{xi j} 2 0 11 (3) 6 x1 3 5 I 5 9 1 0 2 1 0 1 8 7 4 1 1 2 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 5 5 I I 5 9 1 0 2 1 0 1 8 7 (4) 1 x33 1 2 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 5 5 III 5 9 (10) 2 3 3 4 1 0 1 8 7 4 1 3 1 2 1 5 3 3 1 2 1 2 f(x)=121,比 西北角法低 84

3、运费差额法 釆用最大差额费用即利用每行或列中最小费用与次最小之L 间的差额中选最大优先分配的原则,看两步 编号 运费表{wn} 分配表{xn} 201136 59102 187 333 505 132 331212 编号 运费表{wn} 分配表{x 2011363 5910273 710 187413 132 331212 编号 运费表{wn} 分配表{x} 201136 59102 373 3 18741 134 331212 fx)=98,比 编号 运费表{w;} 分配表{x} 最低费用法 201136 5又低了23 I 10 3 710 1874 873 37515 13 5 331212
7 3、运费差额法 • 采用最大差额费用(即利用每行或列中最小费用与次最小之 间的差额中选最大)优先分配的原则,看两步 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 I 5 9 1 0 2 3 3 1 0 1 8 7 4 1 3 1 5 1 3 2 1 1 3 3 1 2 1 2 f(x)=98,比 最低费用法 又低了23 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 I I 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 1 5 1 3 2 1 1 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 3 5 III 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 5 1 5 1 3 4 1 5 3 3 1 2 1 2 编 号 运费表{wi j} 分配表{xi j} 2 0 11 3 6 8 5 5 I V 5 9 1 0 2 7 3 7 1 0 1 8 7 4 1 3 3 7 5 1 5 1 3 - - 5 3 3 1 2 1 2

3.22利用位势法检验分配方案是否最优 不采用单纯型法,如何获得x:的检验数 找到原问题的基础可行解,保持互补松弛条件,求出 对应对偶问题的解,若该对偶问题的解非可行,则原 问题的解不是最优解;否则,达到最优解 mf(x)=∑∑1 xy max g(nv)=>a4+>b ∑xn=41i=1,2,…,m L.+v:≤ l,v±不限 ∑xn=b;j=1 1,2,…,m2j=1,2,…,n ≥0
8 3.2.2 利用位势法检验分配方案是否最优 • 不采用单纯型法,如何获得xij的检验数 • 找到原问题的基础可行解,保持互补松弛条件,求出 对应对偶问题的解,若该对偶问题的解非可行,则原 问题的解不是最优解;否则,达到最优解 = = = = = = = = = 0 1,2, , 1,2, , min ( ) 1 1 1 1 i j j m i i j n j i j i m i n j i j i j x x b j n x a i m f x w x = = + = + = = i m j n u v u v w g u v a u b v i j i j i j n j j j m i i i 1,2, , , 1, 2, , , max ( , ) 1 1 不限

min Wuru+w12*12+w13-13+w2r-21+W2222+w23-23- x11+2+x13 21+x22+x23=a +x21 13 +X22=b max ayu,+a2u2+bv+b2v2+b3v3 1 12 +1x≤ 13 1 l1,u2,v,v2,3不旅
9 + = + = + = + + = + + = + + + + + 1 3 2 3 3 3 1 2 2 2 2 2 1 1 2 1 1 1 2 1 2 2 2 3 2 2 1 1 1 2 1 3 1 1 1 1 1 1 1 2 1 2 1 3 1 3 2 1 2 1 2 2 2 2 2 3 2 3 x x b v x x b v x x b v x x x a u x x x a u min w x w x w x w x w x w x + + + + + + + + + + u ,u ,v ,v ,v 不 限 u v w u v w u v w u v w u v w u v w max a u a u b v b v b v 1 2 1 2 3 2 3 2 3 2 2 2 2 2 1 2 1 1 3 1 3 1 2 1 2 1 1 1 1 1 1 2 2 1 1 2 2 3 3

位势法的原理 为满足互补松弛条件,原问题中x;被选为基变量,即x1≥0 则要求对偶问题中+y=%,即该行的松弛变量为0 共有m+n-1个基变量x;,因此可得m+n-1个等式ur+v=w m+n-1个等式只能解出m+n-1个u;和v,而一共有m计n个 u;和v;,但可令任一个或v=0,从而解出其它m+n-1个 的值;这就是位势法 令矿l1+,其相当原问题x的机会费用 若对所有非基变量有-wn≤0,即+v≤w7,表明当前m 和v是对偶问题的可行解,由互补松弛定理可知当前 m+n-1个基变量x;是最优解,否则 从动->0中找最大者,对应x;就是入变量
10 位势法的原理 • 为满足互补松弛条件,原问题中xij被选为基变量,即xij0, 则要求对偶问题中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 就是入变量
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.4)随机变量函数的分布.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.3)连续型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.2)离散型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.1)随机变量的定义.ppt
- 《数学史》数学物理.ppt
- 《数学史》世界数学点点.ppt
- 浙江大学:《数学史》廿一世纪的数学展望.ppt
- 香港中文大学:《数学史》几何三十载.ppt
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——目录.pdf
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——正文(共十章).pdf
- 《线性代数智能CAI》电子教案:线性方程组的解.ppt
- 西南交通大学数学系:《数学模型与LINGO软件》.pdf
- 《统计分布》教学资源(书籍文献)目录.doc
- 《统计分布》教学资源(书籍文献)目录.pdf
- 《统计分布》教学资源(书籍文献)正文(共六章).pdf
- 河海大学:《概率论与数理统计》课程教学资源(PPT课件讲稿,共五章,主讲:印凡成).ppt
- 河海大学:《概率论》概率论与数理统计综合练习2004.doc
- 河海大学:《概率论》习题20解答(或答案).doc
- 河海大学:《概率论》习题19解答(或答案).doc
- 河海大学:《概率论》习题十四.doc
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第九章 特殊随机服务系统.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第五章 动态规划 Dynamic programming.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第八章 标准服务系统(M/M/n系统).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(2/2).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(1/2).ppt
- 江西财经大学:《运筹学》课程教学资源_作业题集.doc
- 江西财经大学:《运筹学》课程教学资源_教学大纲.doc
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(2/2)2.4 线性规划的灵敏度分析 2.5 参数线性规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第十章 存储理论 Inventory Theory.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第四章 整数规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(1/2)2.1 线性规划的对偶理论 2.2 线性规划的对偶定理 2.3 对偶单纯型算法.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截 6.5 欧拉回路和中国邮递员问题 6.6 哈密尔顿回路及旅行推销员问题 6.7 选址问题.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第七章 随机服务理论概述.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)绪论(忻展红).ppt
- 江西财经大学:《运筹学》课程教学资源(案例)DEC 的短期制造问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)SYTECH 公司的生产优化问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)里尤尼亚的外购问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)投资基金最佳使用计划.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)项目选择问题.pdf