运筹学 运输问题 (2)优秀课件.ppt
《运筹学 运输问题 (2)优秀课件.ppt》由会员分享,可在线阅读,更多相关《运筹学 运输问题 (2)优秀课件.ppt(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学 运输问题第1页,本讲稿共44页 运输问题 运运输问题(Transportation Problem,简记为TP)是一是一类常常见而且极其特殊的而且极其特殊的线性性规划划问题.它最早是从它最早是从物物资调运工作中提出来的,是物流运工作中提出来的,是物流优化管理的重要的化管理的重要的内容之一内容之一 。从理从理论上上讲,运,运输问题也可用也可用单纯形法来求解,形法来求解,但是由于运但是由于运输问题数学模型具有特殊的数学模型具有特殊的结构,存在一构,存在一种比种比单纯形法更形法更简便的便的计算方法算方法 表上作业法表上作业法,用表上作用表上作业法来求解运法来求解运输问题比用比用单纯形法可形法
2、可节约计算算时间与与计算算费用用.但表上作但表上作业法的法的实质仍是仍是单纯形法形法 第2页,本讲稿共44页1 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物某种物资共有共有 m 个个产地地 A1,A2,Am,各各产地的地的产量分量分别是是a1,a2,am;有有n 个个销地地 B1,B2,Bn,各各销地的地的销量分量分别为b1,b2,bn.假定从假定从产地地Ai(i=1,2,m)向向销地地Bj(j=1,2,n)运运输单位物位物资的运价是的运价是cij,问怎怎样调运才能运才能使使总运运费最小?最小?一、运输问题的数学模型一、运输问题的数学模型 加速物加速物资流流转
3、 降低流通降低流通费用用 第3页,本讲稿共44页 运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1n a1 A2c21c22 c2n a2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运运输表表1 1、产销平衡平衡问题即即 设 xij 表示表示产地地 Ai 运往运往销地地 Bj(i=1,2,m;j=1,2,n)的运量的运量.销地销地产地产地 B1 B2 Bn产量产量 A1 x11c11 x12c21 x1n c1n a1 A2 x21c21 x22c22 x2nc2n a2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bn
4、Note:cij 在左下角在左下角 xij 在右上角在右上角 第4页,本讲稿共44页1 运输问题及其数学模型2 2、产销不平衡不平衡问题当当当当第5页,本讲稿共44页 运输问题二、运输问题数学模型的特点二、运输问题数学模型的特点讨论产销平衡平衡问题定理定理 1 平衡运平衡运输问题必有可行解,也必有最优解问题必有可行解,也必有最优解.证明明定理定理 2 平衡运平衡运输问题的的约束方程系数矩束方程系数矩阵 A 和增广矩和增广矩阵 的秩相等,且等于的秩相等,且等于 m+n-1.即即 定理定理2 说明:明:基可行解包含基可行解包含m+n-1个基个基变量量.定理定理 3 平衡运输问题的约束方程系数矩阵平
5、衡运输问题的约束方程系数矩阵 A 的所有的所有各各阶子式只取子式只取 0,1 或或-1 三个三个值.定理定理 4 如果平衡运输问题中的所有产量如果平衡运输问题中的所有产量 ai 和销量和销量 bj都是整数,那么,它的任一基可行解都是整数解都是整数,那么,它的任一基可行解都是整数解.证明明note第6页,本讲稿共44页定理定理 1 1 的证明的证明Proof:则取取显然有然有 ,又又所以所以 ,是,是问题的一个可行解的一个可行解.又因又因为 ,对于任一可行于任一可行解有目解有目标函数函数值 ,对于求极小化于求极小化问题,目,目标函数函数值有下界,有下界,则必有最必有最优解解.第7页,本讲稿共44
6、页1 运输问题及其数学模型Note:平衡运输问题有平衡运输问题有 个变量,个变量,个约束个约束条件,规模很大。条件,规模很大。Go back第8页,本讲稿共44页定理定理 4 的证明的证明Proof:设 x 是是 Ax=b 的任一基可行解,的任一基可行解,B 为对应的基矩的基矩阵,则 其中其中 Bt 是用是用 b 中中对应的的 m+n-1元素替元素替换 B 的第的第t 列列元素得到的矩元素得到的矩阵.显然然,由定理,由定理 3 知,知,det Bt 是个整数,是个整数,det B=,因此,因此,都是整数都是整数.其基其基变量量为第9页,本讲稿共44页 运输问题定义定义 1 1(其中(其中 互不
7、相同,互不相同,互不相同)互不相同)形式的形式的变量集合,称量集合,称为一个一个闭回路,其中回路,其中诸变量称量称为这个个闭回路的回路的顶点点.B1 B2 B3 B4 B5 A1 x11 x12 x13 x14 x15 A2 x21 x22 x23 x24 x25 A3 x31 x32 x33 x34 x35 A4 x41 x42 x43 x44 x45如:如:变量集合量集合变量集合量集合2、每一行(或列)若有每一行(或列)若有闭回路的回路的顶点,点,则有两个有两个顶点;点;3、每两个每两个顶点格子的点格子的连线都是水平的或垂直的;都是水平的或垂直的;4、闭回路中回路中顶点的个数必点的个数必为
8、偶数偶数.闭回路的几何特征:回路的几何特征:1、每一个每一个顶点格子都是点格子都是 90转角点;角点;凡是能排列成凡是能排列成凡是能排列成凡是能排列成第10页,本讲稿共44页1 运输问题及其数学模型闭回路的代数性回路的代数性质:性性质 1 构成构成闭回路的回路的变量量组对应的列向量的列向量组必必线性相关性相关.证明明性性质 2 分组分组构成构成闭回路,回路,则该变量量组对应的列向量的列向量组是是线性相关的性相关的.推推论 1 若若变量量组对应的列向量的列向量组线性无关,性无关,则该变量量组一定不包含一定不包含闭回路回路.若若变量量组 中有一个部中有一个部Go on第11页,本讲稿共44页性质性
9、质 1 的证明的证明Proof:由直接由直接计算可知算可知故故该向量向量组线性相关性相关.第12页,本讲稿共44页 运输问题在在变量量组 中,若有某中,若有某一个一个变量量 xij 是它所在的行(第是它所在的行(第 i 行)或列(第行)或列(第 j 列)列)中出中出现于于(*)中的唯一中的唯一变量,量,则称称该变量量 xij 是是该变量量组的一个孤立点的一个孤立点.定定义 2闭回路的特征回路的特征性性质 3 没有孤立点没有孤立点 若一若一变量量组中不包含任何中不包含任何闭回路,回路,则该变量量组必有孤立点必有孤立点.反反证孤立点不会是孤立点不会是闭回路上的点回路上的点定理定理 5 变量量组 对
10、应的列向量的列向量组线性无关的充性无关的充要要条件是条件是该变量量组中不包含任何中不包含任何闭回路回路.证明明第13页,本讲稿共44页定理定理 5 的的证明明Proof:用反用反证法法设变量量组(*)对应的列向量的列向量组线性无关,但性无关,但该变量量组包含一个以其中某些包含一个以其中某些变量量为顶点的点的闭回路,回路,则由性由性质 2 知,知,这些些变量量对应的列向量必的列向量必线性相关,与假性相关,与假设矛盾矛盾.定理定理 5 变量量组 对应的列向量的列向量组线性无关的充性无关的充要要条件是条件是该变量量组中不包含任何中不包含任何闭回路回路.设有一有一组数数 使得使得 由于由于变量量组(*
11、)中不包含任何中不包含任何闭回路,由性回路,由性质 3 可知其中必有孤立点,可知其中必有孤立点,不妨设不妨设 为孤立点,为孤立点,又不妨设又不妨设 是(是(*)在第)在第i1 1行上唯一的变量,这时由行上唯一的变量,这时由p pijij的特征,(的特征,(1 1)的左端第)的左端第i1个分量和个分量和为k1,而右端,而右端为0,在第在第 j1列上的唯一列上的唯一变量如何?量如何?但但 仍不包含仍不包含闭回路,其中回路,其中还有孤立点有孤立点,与前面与前面类似分析可似分析可证 k2=0.同理得同理得 k3=k4=kr=0这就就证明了向量明了向量组(*)线性无关性无关.第14页,本讲稿共44页1
12、运输问题及其数学模型推论推论 2 2 平衡运平衡运输问题中的一中的一组 m+n-1 个个变量量能构成基能构成基变量的充要条件是它不包含任何量的充要条件是它不包含任何闭回路回路.该推推论给出了运出了运输问题的基可行解中基的基可行解中基变量的一量的一个基本特征:基个基本特征:基变量量组不含不含闭回路回路.这就是基可行解就是基可行解在表上的一个表在表上的一个表现,利用它来判断,利用它来判断 m+n 1 个个变量量是否构成基是否构成基变量量组,就看它是否包含,就看它是否包含闭回路回路.这种方法种方法简便易行,它比直接判断便易行,它比直接判断这些些变量量对应的列向量是否的列向量是否线性无关要性无关要简便
13、得多便得多.利用基利用基变量的量的这个特征,将可以个特征,将可以导出求平衡运出求平衡运输问题的初始基可行解的一些的初始基可行解的一些简便方法便方法.第15页,本讲稿共44页2 运输问题的表上作业法2 2 运输问题的表上作业法运输问题的表上作业法 表上作表上作业法(又称运法(又称运输单纯形法)是根据形法)是根据单纯形形法的原理和运法的原理和运输问题的特点,的特点,设计的一种在表上运算的一种在表上运算的求解运的求解运输问题的的简便而有效的方法便而有效的方法.主要步主要步骤:1、求一个初始求一个初始调运方案(初始基可行解);运方案(初始基可行解);2、判判别当前方案是否当前方案是否为最最优,若是,若
14、是则迭代停止,否迭代停止,否则 转下一步;下一步;3、改改进当前方案,得到新的方案(新的基可行解),当前方案,得到新的方案(新的基可行解),再返回再返回 2。第16页,本讲稿共44页 运输问题一、初始方案的确定一、初始方案的确定1、西北角法西北角法 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex.1 50 已知某商品有三个已知某商品有三个产地地A1、A2、A3和四个和四个销地地B1、B2、B3、B4 ,产量、量、销量及量及单位运价如表位运价如表.问应如何如何调运,在运,在满足各足各销地
15、需要的情况下,使地需要的情况下,使总的运的运费支出支出为最少?最少?解:解:5101020235规则:从运从运输表的西表的西北角开始北角开始,优先安排先安排编号小的号小的产地和地和销地地的运的运输任任务.填了几个数字?填了几个数字?Note:在填入一个数在填入一个数时,如果行和列同,如果行和列同时饱和,和,规定只划去一行或一列定只划去一行或一列 BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15500第17页,本讲稿共44页2 运输问题的表上作业法2、最小元素法最小元素法 BjAi B1 B2
16、 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15规则:优先安排先安排单位运价最小的位运价最小的产地与地与销地之地之间的运的运输 任任务.40102551010Note:在某行(或列)填入最后一个数在某行(或列)填入最后一个数时,如果行和,如果行和列同列同时饱和,和,规定只划去定只划去该行(或列)行(或列)BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字?填了几个数字?第18页,
17、本讲稿共44页 运输问题定理定理 6 用西北角法或最小元素法得到的初始解是用西北角法或最小元素法得到的初始解是平衡平衡运运输问题的基可行解,的基可行解,m+n-1 个个填入数字的格子填入数字的格子对应的的是基是基变量量.Proof:首先,得到的初始解首先,得到的初始解 为可行解是显然的为可行解是显然的.其次,由于行列数共有其次,由于行列数共有 m+n,而按填数字的方法,而按填数字的方法,除填最后一个数除填最后一个数时,划去一行一列外,每填一个数划去,划去一行一列外,每填一个数划去一行或一列一行或一列.因此因此,共填共填 m+n-1 个数个数.最后,最后,证明所填明所填 m+n-1 个数个数对应
18、的的变量量组不含不含闭回路回路.用反用反证法法若含有若含有闭回路回路 不妨不妨设此此闭回路如右回路如右(其他情形同理可(其他情形同理可证)不妨不妨设填填 后划去行,故后划去行,故 必必须较 先填,先填,且填后划去的是列,从而且填后划去的是列,从而 必必须较 先填,且填后划先填,且填后划去的是行,而去的是行,而这又又说明明 必必须较 先填,且填后划先填,且填后划去的是列,去的是列,这又得到又得到 必必须较 先填,且填后划去的先填,且填后划去的是行,是行,这样就得到了矛盾,所以,填数的就得到了矛盾,所以,填数的 m+nm+n-1-1 个格个格子子对应的的变量量组不含不含闭回路,从而,回路,从而,证
19、得了本定理得了本定理.第19页,本讲稿共44页2 运输问题的表上作业法关关键1、填一个数字划去一行或一列填一个数字划去一行或一列 不产生闭回路;不产生闭回路;2、填一个数字填一个数字只只划去一行或一列划去一行或一列 填满填满m+n-1-1个数个数.BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315 BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 按最小元素法按最小元素法3423、Vogel 法法 (元素差元素差额法法)规则:计算各行各列的最小元素与次小元素的差算各行各列的最小元素与次小元素的差额,
20、优先安排差先安排差额最大的所最大的所在行或列的在行或列的单位运价最位运价最小的小的产地与地与销地之地之间的的运运输任任务第20页,本讲稿共44页 运输问题二、最二、最优性性检验 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010定理定理 7 设 是平衡运是平衡运输问题的的一一组基基变量,量,是非基是非基变量,量,则在在变量量组 中存在唯一的中存在唯一的闭回路回路.1、闭回路法回路法+1-1+1-1 BjAi B1 B2 B3 B4 A1 A2 A3检验数表数表-5-10
21、6 6 6第21页,本讲稿共44页2 运输问题的表上作业法2、位位势法(法(对偶偶变量法)量法)求求检验数的数的方法方法约束方程的系数矩束方程的系数矩阵的秩的秩为m+n-1x0必必为基基变量量,x0=0约束方程的系数矩束方程的系数矩阵的秩的秩为m+n对任意的任意的 a0,与原与原问题等价等价由于由于xj 的的检验数数 设:为基基变量,由于基量,由于基变量量的的检验数等于零数等于零有解,不唯一有解,不唯一ui 称称为行位行位势,vj 称称为行位行位势第22页,本讲稿共44页 运输问题 BjAi B1 B2 B3 B4 ui A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2
22、A3 10 5 6 3 4 vj BjAi B1 B2 B3 B4 A1 A2 A3检验数表数表-5-10 6 6 6-2-120273见 Ex.1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解10053-12-5 若若 ,则此时的运输方案为最优的,则此时的运输方案为最优的第23页,本讲稿共44页2 运输问题的表上作业法三、基可行解的改三、基可行解的改进 BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010 BjAi B1 B2 B3 B4 A1 A2 A3检验
23、数表数表-5-10 6 6 6选择进基基变量量则取非基取非基变量量 xst 为进基基变量量确定出基确定出基变量量调整量整量则基基变量量 xkl 出基(运量擦去)出基(运量擦去)调整方法:在整方法:在该闭回路上,奇点运量加回路上,奇点运量加 ,偶点减去,偶点减去 能能转运多少?运多少?153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因为因为 ,所以此运输方案为最优,所以此运输方案为最优方案方案Note:若在若在闭回路上有几个偶点回路上有几个偶点处的运量等于的运量等于 ,则可任取其中一个作可任取其中一个作为出基出基变量(运量擦去),其余几量(运量擦去),其余几个点的个点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运输问题 2优秀课件 运输 问题 优秀 课件
限制150内