运筹学运输与指派问题-ppt课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学运输与指派问题-ppt课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运输 指派 问题 ppt 课件
- 资源描述:
-
1、2021/3/301第4章 运输问题和指派问题 运输问题和指派问题是实际中碰到的比较常见的一类线性规划问题,它们在变量的取值、约束条件的系数矩阵等具有一定的特殊性,所以可以找到比单纯形法更为简便的求解方法。22021/3/304.1 运输问题模型及表上作业法求解111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjiijxaims txbjnxim jnB1B2BnA1A2A3c11c21cm1c12c22cm2c1nc2ncmn单位运价表单位运价表(cij) B1B2 Bn产量产量A1A2Amx11X21xm1x12X22xm2x1nX2nxmna1a2am销量销量
2、b1b2bn产销平衡表(决策变量产销平衡表(决策变量xij=0或或1)11minmnijijijzc x产销平衡的运输问题产销平衡的运输问题:精品资料42021/3/30 你怎么称呼老师? 如果老师最后没有总结一节课的重点的难点,你是否会认为老师的教学方法需要改进? 你所经历的课堂,是讲座式还是讨论式? 教师的教鞭 “不怕太阳晒,也不怕那风雨狂,只怕先生骂我笨,没有学问无颜见爹娘 ” “太阳当空照,花儿对我笑,小鸟说早早早”52021/3/30运输问题的表上作业法n表上作业法是一种简便而有效的方法表上作业法是一种简便而有效的方法,实质是单纯实质是单纯形法形法.n例例4.1某公司下属有三个加工厂
3、某公司下属有三个加工厂A1,A2,A3生产化肥生产化肥,负责供负责供应应B1,B2,B3,B4四个地区所需化肥,各厂化肥产量及各地区四个地区所需化肥,各厂化肥产量及各地区所需化肥、各化肥厂到各地区所的运输距离见下表:所需化肥、各化肥厂到各地区所的运输距离见下表:单位单位 销地销地运价运价 产地产地B1B2B3B4产量产量(吨吨)A13113107A219284A2741059销量销量(吨吨)3656单位运价表单位运价表(元元) 产销平衡表产销平衡表 B1B2B3B4产量产量(吨吨)A1x11x12x13x147A2x11x12x13x144A2x11x12x13x149销量销量(吨吨)3656
4、销地销地运量运量产地产地62021/3/30给出初始解给出初始解n给出初始解有西北给出初始解有西北角法、最小元素法角法、最小元素法和和Vogel法法,我们只我们只介绍比较简单的介绍比较简单的最最小元素法小元素法.n步骤步骤:在产销平衡的在产销平衡的前提下前提下,运价低的优运价低的优先安排调运先安排调运.B1B2B3B4产量产量A1(3)(11)(3)(10)7A2(1)(9)(2)(8)4A3(7)(4)(10)(5)9销量销量3656314633最小元素法初始方案最小元素法初始方案产产 销销B1B2B3B4产量产量A1A2A3317119432101085749销量销量365620 20单位
5、运价表单位运价表72021/3/30解的最优性检验解的最优性检验n解的最优性检验主要有闭回路解的最优性检验主要有闭回路法和位势法法和位势法,我们只介绍我们只介绍位势法位势法.n位势法位势法:n(1)把产销平衡表中初始方案中把产销平衡表中初始方案中有数字格对应的运价写到检验有数字格对应的运价写到检验数表中数表中;n(2)对运输表上的每一行对运输表上的每一行(列列)赋赋予一个数值予一个数值ui(vj),称为位势称为位势.各格各格子的位势等于行位势与列位势子的位势等于行位势与列位势之和之和.n(3)求出检验数求出检验数:ij=cij-(ui+vj)B1B2B3B4(ui)A1(3)0(10)0A2(
6、1)0(2)0A3(4)0(5)0(vj)2-13010-59B1B2B3B4A1311310A21928A374105单位运价表单位运价表位势法检验数计算表位势法检验数计算表(3)1(11)2(9)1(8)-1(7)10(10)1282021/3/30运输方案的改进运输方案的改进n当所有当所有ij0,即为即优即为即优.当当ijbj时时, 用产销平衡的数学模型用产销平衡的数学模型,其约束其约束会产生矛盾会产生矛盾.此时模型应改为此时模型应改为:111,2,.,. .1,2,.,01,2,.,;1,2,.,nijijmijjixaimstxbjnxijim jn11minmnijijijzc x
7、若用表上作业法求之若用表上作业法求之,可设一个假想销地可设一个假想销地, 使其销使其销量为量为bn+1=ai-bj,ci,n+1=0.1111,2,.,. .1,2,.,101,2,.,;1,2,.,1nijijmijjixaimstxbjnxijim jn11minmnijijijzc x122021/3/301234生产能力生产能力110.810.9511.1011.2525211.1011.2511.4035311.011.530411.310需量需量10152520例例4.2 按合同供货的生产计划问题(按合同供货的生产计划问题(P109)季度季度生产的能力(台)生产的能力(台)生产成本
8、费(万元)生产成本费(万元)1 1252510.810.82 23511.111.13 33011.04 41011.311.3生产能力与生产成本生产能力与生产成本某厂按合同规定于当年每季度未分别提供10、15、25、20台同一规格柴油机。已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货,则需储存、维护等费用1500元。要求在完成合同的情况下,做出全年生产费用最小的决策。分析:由题设我们可得第i季度生产,第j季度交货的成本如下表,因此可看成是供大于求的运输问题。交货季度交货季度j生产季度生产季度i交货的成本交货的成本132021/3/301234生产生产能力能力1x11x12x13
展开阅读全文