《管理运筹学》02-7运输问题.ppt
《《管理运筹学》02-7运输问题.ppt》由会员分享,可在线阅读,更多相关《《管理运筹学》02-7运输问题.ppt(73页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第四节第四节 运输问题运输问题Transportation Model一、运输问题及其数学模型一、运输问题及其数学模型二、表上作业法求解运输问题二、表上作业法求解运输问题三、产销不平衡的运输问题及应用三、产销不平衡的运输问题及应用3问题的提出问题的提出 运输问题:产地、销地、产量、销量运输问题:产地、销地、产量、销量 例例1 有有A1,A2,A3三座铁矿,每天要把生产三座铁矿,每天要把生产的铁矿石运往的铁矿石运往B1,B2,B3,B4四个炼铁厂。各矿的四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少?问
2、应如何组织调运才能使运费最少?运输问题及其数学模型运输问题及其数学模型4B1 B2 B3 B4产量产量A1A2A36 3 2 57 5 8 43 2 9 7523销量销量2 3 1 4(百元百元/百吨百吨)xij Ai运给运给Bj的铁矿石数量(百吨)的铁矿石数量(百吨)z 总运费(百元)总运费(百元)运输问题及其数学模型运输问题及其数学模型5B1B2B3B4产量产量A163255A275842A332973销量销量2314(百元百元/百吨百吨)x11x12x13x14x21x22x23x24x31x32x33x34运输问题及其数学模型运输问题及其数学模型6 数学模型为数学模型为:min z=6
3、x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24 +3x31+2x32+9x33+7x34 x11+x12+x13+x14 =5 x21+x22+x23+x24 =2 x31+x32+x33+x34=3 x11 +x21 +x31 =2 x12 +x22 +x32 =3 x13 +x23 +x33 =1 x14 +x24 +x34=4 xij0 (i=1,2,3;j=1,2,3,4)s.t.运输问题及其数学模型运输问题及其数学模型7 运输模型的特点:运输模型的特点:(1)它有它有mn个变量,个变量,m+n个约束方程个约束方程 (2)其系数阵具有特殊的结构其系数阵具有
4、特殊的结构 m=3行行n=4行行A=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8表式表式模型模型 产销平衡产销平衡的运输问题的运输问题:aai i=bbj j 产大于销产大于销的运输问题的运输问题:aai ibbj j 产小于销产小于销的运输问题的运输问题:aai ibbj jB1B2Bn 产量产量 A1c11 x11c12 x12c1n x1n a1A2c21 x21c22 x22c2n x2na2Amcm1 xm1 cm2 xm2 cmn xmnam销量销量b1b2bn aib bj运输问题及其数学模型运输问题及其数学模型运输问题及其数
5、学模型运输问题及其数学模型1 1、运输问题的网络图、线性规划模型及运输表、运输问题的网络图、线性规划模型及运输表设有同一种货物从设有同一种货物从m m个供应地个供应地1 1,2 2,m m运往运往n n个需个需求地求地1 1,2 2,n n。第。第i i个供应地的供应量个供应地的供应量(SupplySupply)为)为 ,第,第j j个需求地的需求量个需求地的需求量(DemandDemand)为)为 。每单位货物从供应地。每单位货物从供应地i i运运到需求地到需求地j j的运价为的运价为 。求一个使总运费最小的运。求一个使总运费最小的运输方案。如果从任一供应地到任一需求地都有道路输方案。如果从
6、任一供应地到任一需求地都有道路通行,这样的运输问题称为完全的运输问题;如果通行,这样的运输问题称为完全的运输问题;如果总供应量等于总需求量,这样的运输问题称为供求总供应量等于总需求量,这样的运输问题称为供求平衡的运输问题。我们先考虑完全的、供求平衡的平衡的运输问题。我们先考虑完全的、供求平衡的运输问题。运输问题。运输问题及其数学模型运输问题及其数学模型1inj1m右图是运输问题的网络表示形式。运输问题及其数学模型运输问题及其数学模型运输问题也可以用线性规划表示。设 为从供应地i运往需求地j的运量,则总运费最小的线性规划问题如下式所示。运输问题及其数学模型运输问题及其数学模型运输问题线性规划变量
7、个数为nm个,每个变量与运输网络的一条边对应,所有的变量都是非负的。约束个数为m+n个,全部为等式约束。前m个约束是供应地的供应量约束,后n个约束是需求地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1,而且每一列中恰有两个系数是1,其他都是0。运输问题及其数学模型运输问题及其数学模型在运输问题线性规划模型中,令 A=则运输问题的线性规划可以写成:运输问题及其数学模型运输问题及其数学模型完全的运输问题系数矩阵A中,列向量 中只有两个元素是1,其他元素都是0。第一个1位于矩阵的第i行,第二个1位于矩阵的第m+j行。这个列向量可以表示为两个单位向量之和,即运输问题及其数学模型运输问题
8、及其数学模型 运输问题除了用网络表示及线性规划表示外,还可以用运输表表示,见右表。运输表是一个m行n列的表格,每一行对应于一个供应地,每一列对应于一个需求地。运输表共有mn个格子,每个格子对应于从一个供应地出发到一个需求地的运输路线。12n12 m运输问题及其数学模型运输问题及其数学模型上页表中,每一格的左上角小方格内的数字表明从相应的供应地i到需求地j的运价 ,每一格右下角表明从相应的供应地i到需求地j的运量 。表右方表明各供应地的供应量 ,表下方表明各需求地的需求量 。每一行运量之和表示从该供应地运往各需求地的运量之和,它应该等于该供应地的供应量;同样,每一列运量之和表示从各供应地运往该需
9、求地的运量之和,它应该等于该需求地的需求量。运输问题及其数学模型运输问题及其数学模型运输问题约束矩阵的性质运输问题约束矩阵的性质A=分别将A的前m行和后n行相加,得到两个相同的mn维向量,其中的元素都是1。即A矩阵的m+n个行向量是线性相关的,因此A矩阵的秩m+n。运输问题分别从供应地1、2、m到需求地n的m条边以及从供应地1分别到需求地1、2、n-1的n-1条边,一共有m+n-1条边。这m+n-1条边组成运输问题约束矩阵A中的m+n-1个列向量,这些列向量在A矩阵中的子矩阵是一个m+n行,m+n-1列的矩阵 B=删除矩阵B的最后一行,得到 B=可以看出,这是一个上三角矩阵,显然,秩Bm+n-
10、1。由m+n-1=秩B秩A0。由于单纯形叠代在每一步都满足互补松弛条件,因此对于基变量xij0,相应的对偶约束条件ui+vj cij的松弛变量一定等于0,即 ui+vj=cij 由于基变量一共有m+n-1个,因此对偶问题一共有m+n-1个等式约束,只要先确定一个对偶变量的值,就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。不妨设vn=0,逐个递推求得ui和vj。求出ui、vj的值以后,就可以进一步计算各非基变量的检验数zij-cij=ui+vj-cij。3.解的改进(1)确定进基变量由单纯形法原理可以知道,凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数中最小的对
11、应变量进基。(2)确定离基变量为保证改进后的解仍为基本可行解,需要保证所有变量的非负性。因此,改进的方法就是从检验数为负数的空格出发,作一条除该空格外其余顶点均为有数字格组成的闭合回路。在这条闭回路上,按对运量作最大可能的调整。表上作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题12341101191530151142131216945453118710501931414131213252515203184例 改进表中用最小元素法得到的初始基本可行解。由表可知,x34的检验数是-2,因此可以作为进基变量。选取变量x34作为进基变量,以其所在的空格为出发点作闭
12、合回路。选取变量x34作为进基变量相应的闭合回路 表上作业法求解运输问题表上作业法求解运输问题12341101191530151521312169454531187105053114414131213252515203184将其改进为新的基本可行解。则x34增加的同时,x14减少,x12增加,x32增加。为保证变量的非负性,能够减少的最大数量为14。此时,x14减少到0,是出基变量。得到新的基本可行解见下表 改进后的基本可行解-1210574422表上作业法求解运输问题表上作业法求解运输问题1234110119153015152131216945453118710502016144141312
13、13252515203184上表给出的调运方案是否为最优呢?还需要对这个方案的空格处(非基变量)求出检验数。由于表中x13的检验数为-1,因此对上表进行改进。得到下表。计算表中的检验数。最优基本可行解 由于检验数表2-38中的所有检验数大于等于0。因此上表是最优方案。1310563322最优解的目标函数值为z=1015+915+945+820+716+1014+1325=1427。需要指出的是,有时在闭合回路调整中,在需要减小运量的地方有两个以上相等的最小数,这样调整时原先空格处填上了这个最小数,而有两个以上最小数的地方成了空格。为了保证基变量的个数是m+n-1个,就要把最小数的空格之一变为空
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理运筹学 管理 运筹学 02 运输 问题
限制150内