第五章运输问题和指派问题.ppt
《第五章运输问题和指派问题.ppt》由会员分享,可在线阅读,更多相关《第五章运输问题和指派问题.ppt(27页珍藏版)》请在三一文库上搜索。
1、第五章 运输问题和指派问题,第一节 运输问题的数学模型,运输问题的一般描述:某种物质(粮食、棉花、煤等)有若干个产地和销地,现在需要把物质从各个产地运往各个销地,产量总数等于销量总数,调运方案很多。若已知各产地的产量、各销地的销量以及各产地到销地的单位运价(或运输距离)。又假定运费和运输量成正比,问如何调运,才能使总运费最省?,第一节 运输问题的数学模型,设Xij为第i个产地运往第j个销地的数量 这是mn个变量,约束条件为m+n个的线性规划问题。,Min Z= CijXij xij =ai (i=1,2,m) xij =bj (j=1,2,n) xij0 (i=1,2,m;j=1,2,n),第
2、一节 运输问题的数学模型,一、运输问题约束条件系数矩阵,A =,1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1,(m+n)(mn),第一节 运输问题的数学模型,二、运输问题的基变量共有m+n-1个 三、 m+n-1个变量构成基变量的充要条件是它们不构成闭合回路,第二节 表上作业法,表上作业法求解运输问题的思路和单纯形法完全类似。 建立作业表 确定初始调运方案 现行方案的最优性检验 现行方案的调整,第二节 表上作业法,一、初始方案的确定: 1.西北角法(左上角法) 从表的左上角开始,保证产销平衡,每填上一个数划去一行或一列,直到有m+n-1行或列划去即可。填上数字为基
3、变量,从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定: 2.最小元素法 采用“就近供应”的思想。 从运输表的运费最小的元素开始,保证产销平衡,每填上一个数划去一行或一列,直到有m+n-1行或列划去即可。填上数字为基变量,从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,一、初始方案的确定: 3. 元素差额法(Vogel近似法) 是在最小元素法基础上的改进。 求每行和每列的行罚数和列罚数 从行罚数和列罚数最大的行或列的运费最小的元素开始,保证产销平衡,每填上一个数划去一行或一列。 重复和直到有m+n-1行或列划去即可。 填上数字为基变量,
4、从而保证其个数为m+n-1个又不构成闭合回路。,第二节 表上作业法,二、最优性检验 1.闭合回路法: 2. 位势法: 三、调整,表上作业法的几点说明:,1.若运输问题的某一基可行解有多个非基变量的检验数为负时,在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善,但通常取最小者对应的非基变量进基。 2.当迭代到最优解时,有某非基变量的检验数为 0 时,则问题有无穷多最优解。 3.当在表上作业时,同时划去了一行和一列运输价格时,就出现了退化,此时必须在当前划去的运价中某一空格填入一个 0 ,表示该格中的变量是取值为 0 的基变量。,第三节 产销不平衡的运输问题,一、产大于销的运输问题 虚设
5、销地,其需要量为ai-bj,相应的运费为0,化成产销平衡的运输问题。,Min Z= CijXij xij ai (i=1,2,m) xij =bj (j=1,2,n) xij0 (i=1,2,m;j=1,2,n),第三节 产销不平衡的运输问题,一、销大于产的运输问题 虚设产地,其产量为bj-ai,相应的运费为0,化成产销平衡的运输问题。,Min Z= CijXij xij = ai (i=1,2,m) xij bj (j=1,2,n) xij0 (i=1,2,m;j=1,2,n),14,第四节 指派问题,指派问题的标准形式(以人和事为例)是: 有 n 个人和 n 件事,已知第 i 人做第 j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 运输 问题 指派
链接地址:https://www.31doc.com/p-3505890.html