[工学]第6章运输问题课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《[工学]第6章运输问题课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 运输 问题 课件
- 资源描述:
-
1、2022-8-9运输问题6-16 运输问题运输问题u 运输问题的数学模型运输问题的数学模型u 运输问题及其基的特征运输问题及其基的特征u 表上作业法表上作业法u 产销不平衡的运输问题产销不平衡的运输问题u 转转运问题运问题u 运输问题的应用运输问题的应用x2x1zo2022-8-9运输问题6-26.1 运输问题的数学模型运输问题的数学模型2022-8-9运输问题6-3考察问题考察问题 某公司经营一种产品,它下设三个加某公司经营一种产品,它下设三个加工厂和四个销售点。三个加工厂工厂和四个销售点。三个加工厂 A1,A2,A3 的产的产量分别为量分别为 7 吨,吨,5 吨,吨,9 吨;四个销售点吨;
2、四个销售点 B1,B2,B3,B4 的销量分别为的销量分别为 3 吨,吨,6 吨,吨,6 吨,吨,6 吨。从吨。从各加工厂到各销售点的每吨产品的运费如表各加工厂到各销售点的每吨产品的运费如表6.1所所示。问该公司应如何调运产品,使总运费最小。示。问该公司应如何调运产品,使总运费最小。设设 xij 为从加工厂为从加工厂 Ai 到销售点到销售点 Bj 的产品运输的产品运输量量(i=1,2,3;j=1,2,3,4),将产销量和所有可能,将产销量和所有可能安排的运输量列于表安排的运输量列于表6.2,则上述问题可形成一个,则上述问题可形成一个数学问题。数学问题。2022-8-9运输问题6-4问题的数学形
3、式问题的数学形式min z =5x11+11x12+3x13+9x13 +x21+10 x22+2x23+6x24 +8x31+4x32+7x33+5x34s.t.x11+x12+x13+x14=7 x21+x22+x23+x24=5 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=6 x14+x24+x33=6 xij 0,i,j表表6.1 单位运价表单位运价表表表6.2 产销平衡表产销平衡表2022-8-9运输问题6-5运输问题的一般描述运输问题的一般描述 某种物资有某种物资有 m 个产地个产地(也称为也称为“发点发点”或
4、或“源源”)和和 n 个销地个销地(也称为也称为“收点收点”或或“汇汇”),第第 i 个产地个产地 Ai 的产量为的产量为 ai,i=1,2,m,第,第 j 个销地个销地 Bj 的销量为的销量为 bj,j=1,2,n,从,从 Ai 到到 Bj 的单位物资运价为的单位物资运价为 cij。问在产销平衡的条件下,。问在产销平衡的条件下,如何确定总运费最小的物资调运方案。如何确定总运费最小的物资调运方案。设设 xij 为从产地为从产地 Ai 到销地到销地 Bj 的物资运输量,的物资运输量,则上述问题可归结为一个线性规划问题。则上述问题可归结为一个线性规划问题。2022-8-9运输问题6-6表表6.3
5、单位运价表单位运价表 销销 地地产产 地地B1B2BnA1c11c12c1nA2c21c22c2nAmcm1cm2cmn2022-8-9运输问题6-7表表6.4 产销平衡表产销平衡表 销销 地地产产 地地B1B2BnaiA1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnambjb1b2bn2022-8-9运输问题6-8运输问题的模型运输问题的模型s.t.x11+x12+x1n=a1 x21+x22+x2n=a2 xm1+xm2+xmn=am x11+x21+xm1=b1 x12+x22+xm2=b2 x1n+x2n+xmn=bn xij 0,i,j 销销地地产产地地B1
6、B2BnaiA1x11x12 x1na1A2x21x22 x2na2Amxm1xm2 xmnambjb1b2bn 销销地地产产地地B1B2 BnA1c11c12 c1nA2c21c22 c2nAmcm1cm2 cmnijijxcmin z=nj 1=mi 1=2022-8-9运输问题6-9数学模型的两种形式数学模型的两种形式s.t.x11+x12+x1n=a1 x21+x22+x2n=a2 xm1+xm2+xmn=am x11+x21+xm1=b1 x12+x22+xm2=b2 x1n+x2n+xmn=bn xij 0,i,jijijxcmin z=nj 1=mi 1=ijijxcmin z=
7、nj 1=mi 1=xij 0,i,jaxiij=nj 1=mi1=s.t.,nj1=bxjij=mi 1=,=njjb1=miia1ijxnj 1=mi 1=2022-8-9运输问题6-10表表6.5 运输表运输表 销销 地地产产 地地B1B2BnaiA1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnambjb1b2bn2022-8-9运输问题6-11表表6.6 运输表运输表(综合表综合表)2022-8-9运输问题6-12表表6.7 例例6.1的运输表的运输表cijB1B2B3B4aiA1511397A2110265A384759bj3666212022-8-9运输问
8、题6-13表表6.8 例例6.1的综合运输表的综合运输表cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj3666212022-8-9运输问题6-146.2 运输问题及其基的特征运输问题及其基的特征2022-8-9运输问题6-156.2.1 运输问题的解运输问题的解 与一般线性规划问题不同,产销平衡的运输问题一定与一般线性规划问题不同,产销平衡的运输问题一定存在可行解。因有存在可行解。因有 则存在可行解则存在可行解 xij 0=ai bj/
9、Q,i,j 又因又因 0 xij min ai,bj 所以运输问题必存在最优解。所以运输问题必存在最优解。=njjb1=miia1=Q2022-8-9运输问题6-16运输问题解的特性运输问题解的特性 运输问题还有一个重要的性质,若产销量运输问题还有一个重要的性质,若产销量 ai 和和 bj都是整数,则必存在整数最优解。因此,将都是整数,则必存在整数最优解。因此,将某些整数规划问题化为运输问题来求解,即便不某些整数规划问题化为运输问题来求解,即便不用整数限制条件,结果可自然满足整数要求。在用整数限制条件,结果可自然满足整数要求。在“整数规划整数规划”一章中,将会看到求解整数规划问一章中,将会看到
10、求解整数规划问题相当费事,而运输问题解的特性给求解某些整题相当费事,而运输问题解的特性给求解某些整数规划问题带来了很大方便。数规划问题带来了很大方便。2022-8-9运输问题6-176.2.2 运输问题的形式特征运输问题的形式特征 运输问题的数学模型具有下列特征:运输问题的数学模型具有下列特征:n方程组中所有变量的系数皆为方程组中所有变量的系数皆为 1和和 0;n任何一个变量任何一个变量 xij 在前在前 m 个方程中以系数个方程中以系数 1 出出现一次,在后现一次,在后 n 个方程也以系数个方程也以系数 1 出现一次;出现一次;n由于要求由于要求 ai=bj,这,这(m+n)个方程是线性个方
11、程是线性相关的。如果从中去掉一个方程相关的。如果从中去掉一个方程,剩下的剩下的(m+n-1)个方程线性无关。个方程线性无关。2022-8-9运输问题6-18运输问题的系数矩阵运输问题的系数矩阵(单模单模)或幺模或幺模x11x12 x1nx21x22 x2n xm1xm2 xmn1 1 11 1 111 1111111111m行行n行行2022-8-9运输问题6-19系数矩阵的秩系数矩阵的秩u假设假设 m,n 2,则有,则有 m+n m n,于是矩阵,于是矩阵 A 的的秩小于或等于秩小于或等于m+n。但是。但是A的秩不等于的秩不等于m+n,这,这是因为是因为 A 的前的前 m 行之和恰好等于后行
12、之和恰好等于后 n 行之和,行之和,所以所以 A 的的 m+n 行是线性相关的。因此,行是线性相关的。因此,A 的秩的秩小于或等于小于或等于 m+n-1u对于运输问题的约束方程的增广矩阵对于运输问题的约束方程的增广矩阵A(就是由(就是由矩阵矩阵A再增添一列约束方程组的右端项所组成的再增添一列约束方程组的右端项所组成的(m+n)(m+n-1)阶矩阵),也有阶矩阵),也有A的秩的秩=m+n-1.2022-8-9运输问题6-20001001000010000000000100第第 i 行行第第 m+j 行行系数矩阵列向量的结构系数矩阵列向量的结构 系数矩阵每一列的元素只有两个系数矩阵每一列的元素只有
13、两个1,其余都为,其余都为0。Pij =ei +em+j2022-8-9运输问题6-216.2.3 运输问题的基运输问题的基 同一般的线性规划问题一样,运输问同一般的线性规划问题一样,运输问题的最优解一定可以在基可行解中找到。题的最优解一定可以在基可行解中找到。因此,继考察了约束方程组的系数矩阵之因此,继考察了约束方程组的系数矩阵之后,还要进一步研究运输问题的基及其基后,还要进一步研究运输问题的基及其基变量所具有的特征。变量所具有的特征。2022-8-9运输问题6-22 由上面的讨论可知,运输问题基变量的数目由上面的讨论可知,运输问题基变量的数目应该是应该是 m+n-1 个,接下来研究怎样的个
14、,接下来研究怎样的 m+n-1 个个变量变量 可以组成基变量。或者说,怎样的可以组成基变量。或者说,怎样的 m+n-1 个变个变量量 (s=m+n-1)对应的系数列向对应的系数列向量量 (s=m+n-1)是线性无关的。是线性无关的。下面引入有关闭回路的概念,它有助于分析下面引入有关闭回路的概念,它有助于分析和解决上述问题。和解决上述问题。基变量与基向量基变量与基向量sssjijijijijijixxxxxx122111211,(s=m+n-1)ssjijijiPPP2211,ssjijijixxx2211,2022-8-9运输问题6-23闭回路及其形式闭回路及其形式cij(xij)B1B2B3
15、B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj366621x1 1,x1 3,x3 3,x3 12022-8-9运输问题6-24闭回路的定义闭回路的定义 凡是能排成凡是能排成(i1,i2,is 互不相同互不相同,j1,j2,js 互不相同互不相同)形式的变量的集合称为一个形式的变量的集合称为一个闭回路闭回路,而把出现在,而把出现在(1)中的变量称为这个闭回路的中的变量称为这个闭回路的顶点顶点(或或拐角点拐角点),相邻两顶点的连线称为闭回路的相邻两顶点的连线称为闭回
16、路的边边。(1)132222111,jijijijijijisssxxxxxx2022-8-9运输问题6-25闭回路的形式之二闭回路的形式之二 cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)58475A3(x31)(x32)(x33)(x34)9bj366621x1 1,x1 2,x3 2,x3 4,x2 4,x2 1 2022-8-9运输问题6-26cij(xij)B1B2B3B4ai51139A1(x11)(x12)(x13)(x14)711026A2(x21)(x22)(x23)(x24)
17、58475A3(x31)(x32)(x33)(x34)9bj366621闭回路的形式之三闭回路的形式之三2022-8-9运输问题6-27闭回路的特点闭回路的特点 从上面几个闭回路的例子中不难看出,如果从上面几个闭回路的例子中不难看出,如果把一个闭回路的所有顶点都在表上画出,并且把把一个闭回路的所有顶点都在表上画出,并且把相邻的顶点用一条直线连接起来,就可以得到一相邻的顶点用一条直线连接起来,就可以得到一条封闭的折线,折线的每一条边或者是水平的,条封闭的折线,折线的每一条边或者是水平的,或者是垂直的,即折线是由交替的水平和垂直或者是垂直的,即折线是由交替的水平和垂直(联接的)线段组成。另外,在表
18、中的每一行和(联接的)线段组成。另外,在表中的每一行和每一列中,至多只有闭回路的两个顶点;对一条每一列中,至多只有闭回路的两个顶点;对一条闭回路是按顺时针方向还是逆时针方向是无关紧闭回路是按顺时针方向还是逆时针方向是无关紧要的。要的。2022-8-9运输问题6-28 若有一闭回路若有一闭回路 则则 根据列向量的特征根据列向量的特征 Pij=ei+em+j 可得可得闭回路闭回路及其性质及其性质132222111-+-+-jijijijijijisssPPPPPP=0132222111-+-+-jijijijijijisssPPPPPP()+jmiee32-()+jmiee22-=()+jmiee
19、11+()+jmiee21-()+jmieess+=0()+jmiee1s1ssjijijijijijixxxxxxs32222111,2022-8-9运输问题6-29srrjijijijijijixxxxxx122111211,(6.2)122112111-,+-jijijijijijisrrPPPPPP=0闭回路与闭回路与列向量列向量 若变量组若变量组 中有一部分组成闭回路,则中有一部分组成闭回路,则(6.2)对应的列向量对应的列向量 是线性相关的。是线性相关的。性质性质6.1表明构成闭回路的变量组对应的列向量表明构成闭回路的变量组对应的列向量组是线性相关的,组是线性相关的,而向量组中有一
20、部分线性相关,则全而向量组中有一部分线性相关,则全体也体也线性相关线性相关。性质性质6.2说明:若变量组说明:若变量组(6.2)对应的列向量线性无关,对应的列向量线性无关,则该变量组一定不包含有闭回路。则该变量组一定不包含有闭回路。2022-8-9运输问题6-30 变量组变量组 对应的系数列向量组线性无关的充要条件是:变对应的系数列向量组线性无关的充要条件是:变量组量组(6.2)不包含有闭回路。不包含有闭回路。m+n-1 个变量个变量 (s=m+n-1)构成基变量的充要条件是不含闭回路。构成基变量的充要条件是不含闭回路。运输问题的基及其构成条件运输问题的基及其构成条件ssjijijixxx22
21、11,rrjijijixxx2211,(6.2)2022-8-9运输问题6-316.3 表上作业法表上作业法n表上作业法是运用单纯形法求解运输问表上作业法是运用单纯形法求解运输问题的一种形式;题的一种形式;n表上作业法的计算步骤和计算内容与单表上作业法的计算步骤和计算内容与单纯形法完全相同,只是在计算方法上有纯形法完全相同,只是在计算方法上有较大的简化,其实质仍是单纯形法;较大的简化,其实质仍是单纯形法;n表上作业法的所有计算可以在运输表上表上作业法的所有计算可以在运输表上操作,故得此名。操作,故得此名。2022-8-9运输问题6-326.3.1 初始解的求解方法初始解的求解方法2022-8-
22、9运输问题6-331.最小元素法最小元素法u最小元素法的基本思想是就近供应,这是因为运最小元素法的基本思想是就近供应,这是因为运输问题是要确定总运费最小的运输方案;输问题是要确定总运费最小的运输方案;u最小元素法的宗旨是从运价表中依次选择当前最最小元素法的宗旨是从运价表中依次选择当前最小运价的格子分配相应的运输量,由此确定初始小运价的格子分配相应的运输量,由此确定初始运输方案;运输方案;u最小元素法求得的初始解一般很接近最优解。最小元素法求得的初始解一般很接近最优解。2022-8-9运输问题6-34最小元素法算例最小元素法算例cijB1B2B3B4A151139A211026A38475 最小
23、元素法计算程序:最小元素法计算程序:(4)若若 xlk(0)=q1,则则 It+1=It-l,Jt+1=Jt(1)t=0,It=1,m,Jt=1,n 若若 xlk(0)=q2,则则 It+1=It,Jt+1=Jt-k (2)clk(t)=min cij|i It,j Jt (5)t=t+1,返回返回 (2)。(xij)B1B2B3B4aiA17A25A39bj3666(3)(2)(4)(6)(3)(3)1234566z0=85al-,bk-ljxnj 1=(0)ikxmi 1=(0)(3)xlk(0)=min =minq1,q22022-8-9运输问题6-35关于最小元素法的定理关于最小元素法
24、的定理用最小元素法得到的变量用最小元素法得到的变量 xij 的值构成一个基可行解,括号中的数则是的值构成一个基可行解,括号中的数则是基变量的值。基变量的值。u有有m+n-1个基变量;个基变量;u基变量不包含闭回路。基变量不包含闭回路。x1x2x3x42022-8-9运输问题6-362.左上角法左上角法(西北角法西北角法)u左上角法的特点是不考虑运输方案的运费,只要左上角法的特点是不考虑运输方案的运费,只要求运输量满足产销平衡便可。因此该法不依赖运求运输量满足产销平衡便可。因此该法不依赖运价表,可直接在产销平衡表上操作。价表,可直接在产销平衡表上操作。u左上角法的要点是按产地和销地的排序从前到后
25、左上角法的要点是按产地和销地的排序从前到后依次确定供销关系,即每次都是在运价表中选择依次确定供销关系,即每次都是在运价表中选择当前处在左上角的格子分配运输量,由此确定初当前处在左上角的格子分配运输量,由此确定初始运输方案;始运输方案;u左上角法的计算量较小,但求得的初始解远不如左上角法的计算量较小,但求得的初始解远不如最小元素法的好,通常与最优解相去甚远。最小元素法的好,通常与最优解相去甚远。2022-8-9运输问题6-372.左上角法左上角法(西北角法西北角法)算例算例(xij)B1B2B3B4aiA17A25A39bj3666(3)(4)(2)(3)(3)(6)z0=1352022-8-9
展开阅读全文