第七章 运输问题(1表上作业).ppt
《第七章 运输问题(1表上作业).ppt》由会员分享,可在线阅读,更多相关《第七章 运输问题(1表上作业).ppt(87页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第七章第七章 运输问题运输问题TransportationProblem2021/9/241第七章第七章 运输问题运输问题l运输问题在工商管理中有着广泛的应用,运输问题在工商管理中有着广泛的应用,是一类重要的和特殊的是一类重要的和特殊的线性规划问题线性规划问题。l由于这类线性规划问题在结构上有特殊性,由于这类线性规划问题在结构上有特殊性,所以有专门的解法所以有专门的解法表上作业法表上作业法等,用等,用以简便求解这类问题。以简便求解这类问题。l管理运筹学软件中也为求解这类问题编制管理运筹学软件中也为求解这类问题编制了专门的程序供我们使用。了专门的程序供我们使用。2021/9/242第七章第七章
2、运输问题运输问题u7.1运输问题的模型运输问题的模型2021/9/2437.1 运输问题的模型运输问题的模型例例1.某公司从两个产地某公司从两个产地A1、A2 将物品运往三个销地将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问应如何调运运往各销地每件物品的运费如下表所示,问应如何调运可使总运输费用最小?可使总运输费用最小?运费单价运费单价销销地地产地产地B1B2B3产产量量(件件)A1646200A2655300销销量量(件件)1501502002021/9/2447.1 运输问题的模型运输问题的模型
3、解:这是一个解:这是一个产销平衡问题产销平衡问题:总产量总产量=总销量总销量=500。设设xij 为从产地为从产地Ai 运往销地运往销地Bj 的运输量,如:的运输量,如:x12表示从产地表示从产地A1 运往销地运往销地B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格:运费单价运费单价销销地地产地产地B1B2B3产产量量(件件)A1646200A2655300销销量量(件件)1501502002021/9/2457.1 运输问题的模型运输问题的模型解:这是一个解:这是一个产销平衡问题产销平衡问题:总产量总产量=总销量总销量=500。设设xij 为从产地为从产地Ai
4、运往销地运往销地Bj 的运输量,如:的运输量,如:x12表示从产地表示从产地A1 运往销地运往销地B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格:运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)1501502005005002021/9/246运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =
5、6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2;j=1,2,3)。解得:解得:min f =2500,x11=50,x12=150,x13=0,x21=100,x22=0,x23=200。2021/9/2477.1 运输问题的模型运输问题的模型1.1.一般运输问题的线性规划模型一般运输问题的线性规划模型 假设假设 A A1 1,A A2 2,A Am m 表示某物资的表示某物资的 m m 个产地;个产地;B B1
6、1,B B2 2,B Bn n 表示某物资的表示某物资的 n n 个销地;个销地;s si i 表示产地表示产地 A Ai i 的产量;的产量;d dj j 表示销地表示销地 B Bj j 的销量;的销量;c cijij 表示把物资从产地表示把物资从产地 A Ai i 运往销地运往销地 B Bj j 的单位运价。的单位运价。如果如果 s s1 1+s s2 2+s sm m =d d1 1+d d2 2+d dn n,称该运输问题是称该运输问题是产销平衡的产销平衡的;否则,称它是;否则,称它是产销不平衡的产销不平衡的。2021/9/2487.1 运输问题的模型运输问题的模型销地销地产地产地B1
7、B2Bn产量产量A1c11x11c12x12c1nx1ns1A2c21x21c22x22c2nx2ns2 Amcm1xm1cm2xm2cmn xmnsm销量销量d1d2dn2021/9/2497.1 运输问题的模型运输问题的模型 设设 x xijij 为为从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的运运输输量量,则则对对于产销平衡问题,可得到下列运输问题的模型:于产销平衡问题,可得到下列运输问题的模型:m nminf=c cij ij x xij ij i=1j=1 ns.t.x xij ij =s si i i i=1,2,=1,2,m m j=1m x xij ij =
8、d dj j j j=1,2,=1,2,n n i=1x xij ij 0 0(i=1,2,m;j=1,2,n)。2021/9/2410运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2;j=1,2,3)。2021
9、/9/24117.1 运输问题的模型运输问题的模型 设设 x xijij 为为从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的运运输输量量,则则对对于产销平衡问题,可得到下列运输问题的模型:于产销平衡问题,可得到下列运输问题的模型:m nminf=c cij ij x xij ij i=1j=1 ns.t.x xij ij =s si i i i=1,2,=1,2,m m j=1m x xij ij =d dj j j j=1,2,=1,2,n n i=1x xij ij 0 0(i=1,2,m;j=1,2,n)。2021/9/24127.1 运输问题的模型运输问题的模型2.2
10、.一般模型的系数矩阵特征一般模型的系数矩阵特征1.共有共有 m+n 行,分别表示各产地和销地;行,分别表示各产地和销地;mn 列,列,分别表示各变量;分别表示各变量;2.每列只有两个每列只有两个 1 1,其余为,其余为 0 0,分别表示只有一个产地,分别表示只有一个产地和一个销地被使用。和一个销地被使用。2021/9/2413运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.
11、t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2;j=1,2,3)。2021/9/24147.1 运输问题的模型运输问题的模型2.2.一般模型的系数矩阵特征一般模型的系数矩阵特征1.共有共有 m+n 行,分别表示各产地和销地;行,分别表示各产地和销地;mn 列,列,分别表示各变量;分别表示各变量;2.每列只有两个每列只有两个 1 1,其余为,其余为 0 0,分别表示只有一个产地,分别表示只有一个产地和一个销地被使用。和一个销地被使用。2021/9/24157.1 运输问题的模型运
12、输问题的模型3.一般模型有时会发生一些如下变化:一般模型有时会发生一些如下变化:1)有时求目标函数最大值。如求利润最大或营业额)有时求目标函数最大值。如求利润最大或营业额最大等;最大等;2)当某些运输线路上的能力有限制时,模型中可直)当某些运输线路上的能力有限制时,模型中可直接加入(接加入(等式或不等式等式或不等式)约束;)约束;3)产销不平衡时,可加入虚设的产地(销大于产时)产销不平衡时,可加入虚设的产地(销大于产时)或销地(或销地(产大于销时产大于销时)。)。2021/9/2416第七章第七章 运输问题运输问题u7.1运输问题的模型运输问题的模型l7.2运输问题的表上作业法运输问题的表上作
13、业法2021/9/2417 7.2 运输问题的表上作业法运输问题的表上作业法l表上作业法是一种求解运输问题的特殊方表上作业法是一种求解运输问题的特殊方法,其实质是单纯形法。法,其实质是单纯形法。l运输问题都存在最优解。运输问题都存在最优解。2021/9/2418 7.2 运输问题的表上作业法运输问题的表上作业法计算过程(假设产销平衡):计算过程(假设产销平衡):l1.找出初始基本可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题,则有个销地的产销平衡问题,则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。2021/9/241
14、9运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2;j=1,2,3)。2021/9/2420 7.2 运输问题的表上作业法运输问题的表上作业法计算过程(假设产销平衡):计算过程(假设产销平衡):l1.找出初始基本
15、可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题,则有个销地的产销平衡问题,则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。由于产销平衡,其模型最多只有由于产销平衡,其模型最多只有m+n-1个独立个独立的约束方程,即运输问题有的约束方程,即运输问题有m+n-1个基变量。个基变量。2021/9/2421运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x1
16、2+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2;j=1,2,3)。2021/9/2422 7.2 运输问题的表上作业法运输问题的表上作业法计算过程(假设产销平衡):计算过程(假设产销平衡):l1.找出初始基可行解找出初始基可行解。对于有对于有m个产地个产地n个销地的产销平衡问题,则有个销地的产销平衡问题,则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。由于产销平衡,其模型最多只有由于
17、产销平衡,其模型最多只有m+n-1个独立个独立的约束方程,即运输问题有的约束方程,即运输问题有m+n-1个基变量。个基变量。2021/9/2423 7.2 运输问题的表上作业法运输问题的表上作业法计算过程(假设产销平衡):计算过程(假设产销平衡):l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。即检验除了上述即检验除了上述m+n-1个基变量以外的空格的检验个基变量以外的空格的检验数判别是否达到最优解,如果已是最优,停止计数判别是否达到最优解,如果已是最优,停止计算,否则转到下一步。算,否则转到下一步。2021/9/2424 7.2 运输问题的表上作业
18、法运输问题的表上作业法计算过程(假设产销平衡):计算过程(假设产销平衡):l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量,找出新的基可行解。确定入基变量和出基变量,找出新的基可行解。l4.重复重复2、3直到得到最优解。直到得到最优解。2021/9/2425 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。2021/9/2426 7.2 运输问题的表上作业法运输问题的表上作业法例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1,A2,A3,有四个销售公司有四个
19、销售公司B1,B2,B3,B4,其各分厂每日的产,其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示,在表中产量与销量的单位为吨,运单位运价如表所示,在表中产量与销量的单位为吨,运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少?销点的需求量的前提下总运费最少?销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365620202021/9/2427 7.2 运输问题的表上作业法运输问题的表上作
20、业法1.找出初始基可行解。找出初始基可行解。最小元素法最小元素法我们很容易的直观想到我们很容易的直观想到,为了减少运费为了减少运费,应应优先考虑单位运输价格最小优先考虑单位运输价格最小(或运输距离最或运输距离最短短)的供销业务的供销业务,最大限度的满足其供销量。最大限度的满足其供销量。2021/9/2428 7.2 运输问题的表上作业法运输问题的表上作业法例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1,A2,A3,有四个销售公司有四个销售公司B1,B2,B3,B4,其各分厂每日的产,其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的
21、销量以及各分厂到各销售公司的单位运价如表所示,在表中产量与销量的单位为吨,运单位运价如表所示,在表中产量与销量的单位为吨,运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少?销点的需求量的前提下总运费最少?销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365620202021/9/2429销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9
22、/2430销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2431销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2432销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2433销地销地产地产地B1
23、B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2434销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2435销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2436销地销地产地产地B1B2B3B4产量产量A1311
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七章 运输问题1表上作业 第七 运输 问题 作业
限制150内