高速公路运输问题.ppt_第1页
高速公路运输问题.ppt_第2页
高速公路运输问题.ppt_第3页
高速公路运输问题.ppt_第4页
高速公路运输问题.ppt_第5页
已阅读5页，还剩43页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1.9 运输问题,1.9.1 数学模型,数学模型：,设xij为从i 地到 j 地的物资运量,r(a)=m+n-1,1) r(a)m+n,1.9.2 表上作业法,(1)、初始基本可行解, 最小元素法, 西北角法, vogol法,z=210, 最小元素法步骤：,定义：互不相同的2k个变量x11 , x21 , x22 , , xkk , x1k组成一个闭回路。,定理1：最小元素法方案中，数字格不含闭回路。,定理2：xij 是可行解，则它是基本可行解 xij 的正分量不含闭回路。, 西北角法：, vogol法：,1) 计算各行各列中最小与次小cij的差。,2) 选差最大的行(列)按cij最小填写。,(2) 检验是否最优？, 闭回路法, 位势法, 闭回路法,定理3：每个空格有唯一一条闭回路(其余拐点为数字格),定理4：调整后方案仍为基本可行解,定理5：全部 ij 0时，xij 为最优解。,(3)、方案调整,1) 求出 xpq闭回路， xpq换入。,2) 调整量 =min 奇拐点处运量 ， xst xst换出。,3) 奇拐点运量 ，偶拐点运量 。,得新基本可行解转(2)。, 23= -10 z=200,(2), 位势法,定理6： xij 为()的可行解，(ui , vj )为(d)的可行解，若满足xij (cij - ui - vj )=0, 则xij 为()的最优解，(ui , vj )为(d)的最优解。,2) 位势法基本思想：,u1 + v2 = c12 =5 u1 + v3 = c13 =5 u2 + v1 = c21 =1 u3 + v1 = c31 =2 u3 + v2 = c32 =3,1.9.3 产销不平衡的运输问题,(1)、产大于销,增加松弛变量xi n+1 ( i =1 m ) , ai 的库存量，销地 bn+1 。,例：,解：,minz =35,(2)、销大于产,例：,解：,例1：货船调度问题,1.9.4 应用举例,解：,例3：作物布局问题,例4：转口运输问题,解：,最优解：,例5：多维运输问题,m个工厂 个批发站 n个商店 求最优分配方案，使总运费最小,pi :工厂i 生产能力 ( i =1 m ) j :批发站 j最大容量 ( j =1 ) dk :商店k需求量 ( k =1 n ) sij :工厂i 到批发站 j的单位商品运费 tjk : 批发站 j到商店k的单位商品运费 cijk = sij+tjk,设xijk为工厂i 经批发站 j到商店k的商品数量,解xijk,实例：,伐木厂i ( i =1 m ) 加工厂j ( j =1 n) 运输方式k (
人人文库> 全部分类> 专业文献 > 工程机械

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论