《运筹学》胡运权 第4版 第三章 运输问题.ppt
《《运筹学》胡运权 第4版 第三章 运输问题.ppt》由会员分享,可在线阅读,更多相关《《运筹学》胡运权 第4版 第三章 运输问题.ppt(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学胡运权第4版第三章运输问题本章本章内容内容|运输问题及其数学模型|用表上作业法求解运输问题|运输问题的进一步讨论|应用问题举例如果运输问题的总产量等于其总销量,即有 则称该运输问题为产销平衡运输问题;反之,称产销不平衡运输问题。产销平衡运输问题的数学模型可表示如下:1运输问题及其数学模型二、运输问题数学模型的特点:二、运输问题数学模型的特点:1.运输问题一定有最优解;基变量的个数=m+n-12.运输问题约束条件的系数矩阵:x1mx2mxm1xmmx11x12x21x22xm2m行n行1运输问题及其数学模型|运输问题具有下述特点:(1)约束条件系数矩阵的元素等于0或1;(2)约束条件系数矩
2、阵的每一列有两个非零元素,这对应于每一个变量在前m个约束方程中出现一次,在后n个约束方程中也出现一次。1运输问题及其数学模型|对产销平衡运输问题,除上述两个特点外,还有以下特点:(1)所有结构约束条件都是等式约束;(2)各产地产量之和等于各销地销量之和。1运输问题及其数学模型例1 某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点(销地)出售,各工厂的生产量、各销售点的销售量(假定单位均为t)以及各工厂到各销售点的单位运价(元t)示于表3-2中,要求研究产品如何调运才能使总运费最小?表3-2 销地产地B1B2B3B4产量A116A210A322销量81412144842812541
3、011396111运输问题及其数学模型该问题的数学模型:1运输问题及其数学模型12本章本章内容内容|运输问题及其数学模型|用表上作业法求解运输问题|运输问题的进一步讨论|应用问题举例一、表上作业法的基本思想和步骤:一、表上作业法的基本思想和步骤:1.1.基本思想:同基本思想:同单纯形法单纯形法的基本思的基本思想想基本可行解是否为最优解换基结束YN2 用用表表上上作作业业法法求求解解运运输输问问题题二、表上作业法的步骤(1)寻找初始基可行解;最小元素法、西北角法、沃格尔法(2)求出非基变量检验数(空格检验数),判断是否为最优解;闭回路法、位势法(3)换基改进,找到新的基可行解闭回路调整法(4)重
4、复(2)(3)2 用用表表上上作作业业法法求求解解运运输输问问题题1.1.最小元素法最小元素法 从运价最小的格开始,在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。寻寻找找初初始始基基可可行行解解 销地产地B1B2B3B4产量A1 16A2 10A3 22销量 814 12 14484285101112346911 821014 861.1.最小元素法最小元素法总费用 z=104+611+82+23+145+86=246寻寻找找初初始始基基可可行行解解2.2.西北角法西北角法 从
5、西北角(左上角)格开始,在格内的右下角标上允许取得的最大数。然后按行(列)标下一格的数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。寻寻找找初初始始基基可可行行解解 销地产地B1B2B3B4产量A1 16A2 10A3 22销量 8 14 12 14484285101112346911 846 14882.2.西北角法西北角法总费用 z=84+812+610+43+811+146=372寻寻找找初初始始基基可可行行解解3.沃格尔法|罚数=次小费用-最小费用|找出最大的罚数行或列所对应的最小费用优先安排。|重复计算步骤1和2寻寻找找初初始始
6、基基可可行行解解3.沃格尔法沃格尔法 销地产地B1B2B3B4产量行罚数12345A116A210A322销量 814121448列罚数123454101211346911285201513221011321148810217062201242总费用 z=244寻寻找找初初始始基基可可行行解解 最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同,即计算检验数。由于目标要求极小,因此,当所有的检验数都大于或等于零时该调运方案就是最优方案;否则就不是最优,需要进行调整。下面介绍两种求检验数的方法:闭回路法和对偶变量法。解解的的最最优优性性检检验验1.闭回路法|闭回路:
7、从空格出发,遇到数字格可以旋转90度,最后回到空格所构成的回路;|原理:利用检验数的经济含义;|检验数:非基变量增加一个单位引起的成本变化量。|当所有非基变量的检验数均大于或等于零时,现行的调运方案就是最优方案,因为此时对现行方案作任何调整都将导致总的运输费用增加。|闭回路法的主要缺点是:当变量个数较多时,寻找闭回路以及计算两方面都会产生困难。解解的的最最优优性性检检验验 销地产地B1B2B3B4产量A116A210A322销量8141214481.1.闭回路法闭回路法(结合最小元素法的初始解)4281254101139611解解的的最最优优性性检检验验81410268检验数11=c11-c2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运筹学胡运权 第4版 第三章 运输问题 胡运权 第三 运输 问题
限制150内