6运筹学——运输问题.ppt

《6运筹学——运输问题.ppt》由会员分享，可在线阅读，更多相关《6运筹学——运输问题.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学第六讲运筹学第六讲2007.10.18线性规划中的线性规划中的运输问题及其解法运输问题及其解法 线性规划单纯形线性规划单纯形原问题是什么：_基是什么？基变量几个：_非基变量几个：_系数矩阵秩是：_1/21/2023运筹学第六讲运输问题第七章运输问题第七章运输问题特殊特殊LPLP问题问题:运输问题运输问题;模型、表上作业法模型、表上作业法位势法判优位势法判优;用用VogelVogel法求初始解法求初始解;讨论讨论1/21/2023运筹学第六讲运输问题运输问题运输问题某种产品从若干个产地某种产品从若干个产地(产量产量已知已知)运往若干个销地运往若干个销地(销量已销量已知知)，已知各地间运输单

2、价，求，已知各地间运输单价，求总运费最小的运输方案。总运费最小的运输方案。此问题是我国科学家此问题是我国科学家(王元王元,越越民义等民义等)在在19591959年前率先研究讨年前率先研究讨论的，并获得了：表上作业法论的，并获得了：表上作业法和图上作业法等重要结果。和图上作业法等重要结果。1/21/2023运筹学第六讲运输问题运输问题运输问题产地数产地数m=2,m=2,销地数销地数n=3,n=3,产销平衡，产销平衡，决策变量个决策变量个数数m*n,m*n,等式等式约束数约束数m+nm+n，不等式约束不等式约束数数0,0,目标函目标函数是总运价数是总运价,要求最小。要求最小。1/21/2023运筹

3、学第六讲运输问题运输问题运输问题目标函数：目标函数：1/21/2023运筹学第六讲运输问题运输问题运输问题 它是典型的它是典型的LPLP问题，但若用单纯问题，但若用单纯形法，形法，等式约束数等式约束数m+n(m+n(但但当产销平衡当产销平衡的时候其中有一个是的时候其中有一个是多余多余的，的，),),不等式约束不等式约束数数00初始基可行解初始基可行解就显得很难求，决策就显得很难求，决策变量个数也较大，我国科学家在上世纪变量个数也较大，我国科学家在上世纪五十年代提出了解运输问题的图上作业五十年代提出了解运输问题的图上作业法和表上作业法。法和表上作业法。1/21/2023运筹学第六讲运输问题运输问

4、题运输问题产地数产地数m=2,m=2,销地数销地数n=2,n=2,产销平衡产销平衡,决策变量个数决策变量个数m*n,m*n,等式约束数等式约束数m+nm+n,不等式约束数不等式约束数0,0,目标函数是总运目标函数是总运价价,要求最小。要求最小。Min Min z=xz=x1111+2x+2x1212+7x+7x2121+100 x+100 x2222x x1111+x+x12 12 =50=50 x x2121+x+x2222=70=70s.ts.t.x.x11 11 +x+x21 21 =40=40 x x12 12 +x+x2222=80=80 x x1111,x,x1212,x,x212

5、1,x,x222200要特别提请注意的是：四个等式约束要特别提请注意的是：四个等式约束不独立不独立！(1)+(2)(1)+(2)就是就是(3)+(4)(3)+(4)，或，或 (1)+(2)-(3)=(4)(1)+(2)-(3)=(4)，不能直接就这样用单纯形法。不能直接就这样用单纯形法。A A1 1A A2 2B B1 1B B2 21/21/2023运筹学第六讲运输问题运输问题运输问题A1A1B1B1最近，优先考虑，最近，优先考虑，最多可运：最多可运：min40,50=40,min40,50=40,于是于是x11=40 x11=40其运价其运价:z=xz=x1111+2x+2x1212+7x

6、+7x2121+100 x+100 x2222=7060=7060同理应优先考虑同理应优先考虑x x1212，而且它可以取，而且它可以取min10,80=10min10,80=10最后最后x x2222=70,=70,而而x x2121=0=0。我们得到一个运输方案。我们得到一个运输方案。请注意要一个运输方案并不难，如可按比例分：请注意要一个运输方案并不难，如可按比例分：至此至此B1B1满足了，可以划去第一列；满足了，可以划去第一列；A1A1的产量可以认为只有的产量可以认为只有50-40=1050-40=10；10408010700一个运输方案是一个可行解一个运输方案是一个可行解,并非必是基可

7、行解：并非必是基可行解：系数矩阵应看成系数矩阵应看成3 3行，基变量行，基变量3 3个，非基变量个，非基变量4-3=14-3=1个，非基变量要取个，非基变量要取0 0，所以此运输问题的非零变量，所以此运输问题的非零变量至多至多3 3个。个。问题问题:一个运输方案是否是最优的？一个运输方案是否是最优的？1/21/2023运筹学第六讲运输问题运输问题运输问题 求初始运输方案常用的方法有三种：西北角法、求初始运输方案常用的方法有三种：西北角法、最小元素法和沃格尔最小元素法和沃格尔(Vogel)(Vogel)法；法；我们得到的运输方案应该是一个基可行解，即我们得到的运输方案应该是一个基可行解，即非零的

8、变量至多非零的变量至多m+n-1m+n-1个。个。请注意要一个运输方案并不难，如可按比例分：请注意要一个运输方案并不难，如可按比例分：7001 1、西北角法：优先考虑下标、西北角法：优先考虑下标ijij小的小的x xijij,也就是表也就是表上的上的 左上角左上角 西北角的格中填入尽量大的值，然后西北角的格中填入尽量大的值，然后把已满足的行或列划去，产销量相应加以调整，把已满足的行或列划去，产销量相应加以调整，直到一个完整的运输方案诞生。，直到一个完整的运输方案诞生。4010问题问题:如何找第一个运输方案如何找第一个运输方案?一个运输方案是否是最优的一个运输方案是否是最优的?非最优的方案如何改

9、进非最优的方案如何改进?1/21/2023运筹学第六讲运输问题表上作业法表上作业法运输问题的表上作业法：运输问题的表上作业法：平衡产销；平衡产销；找出初始基可行解找出初始基可行解(西北角法、西北角法、最小元素法、最小元素法、VogelVogel法法)；基可行解是否最优的判别基可行解是否最优的判别(闭闭回路法、位势法回路法、位势法*)；非最优的基可行解的改进非最优的基可行解的改进(闭闭回路调整法回路调整法).).1/21/2023运筹学第六讲运输问题平衡产销平衡产销:运输问题中产销不平衡时：运输问题中产销不平衡时：:产产 销：增加一个相应运价销：增加一个相应运价为为 0 0 的：的：。:产产 销

10、：增加一个相应运价销：增加一个相应运价为为 0 0 的：的：。新销地新销地(仓库仓库)总可以调整为产销平衡。总可以调整为产销平衡。虚拟产地虚拟产地1/21/2023运筹学第六讲运输问题求初始基可行解求初始基可行解运输问题的独立的等式约束数运输问题的独立的等式约束数=系数矩系数矩阵的秩阵的秩=基变量个数基变量个数=m+n-1=m+n-1，非基变量非基变量个数个数=m*n-m-n+1=m*n-m-n+1。找出初始基可行解找出初始基可行解(m+n-1(m+n-1格格)：西北角西北角(左上角左上角)法法；最小元素最小元素(成本成本)法法;伏格尔伏格尔(Vogel)(Vogel)法法*等等.找初始基可行

11、解的西北角法：尽量填找初始基可行解的西北角法：尽量填西北角的空格。西北角的空格。1/21/2023运筹学第六讲运输问题西北角法西北角法最后得的初始基可行解。最后得的初始基可行解。34422223366总运费总运费135135.1/21/2023运筹学第六讲运输问题找找初初始始基基可可行行解解的的西西北北角角法法尽量用下标小的（左上角尽量用下标小的（左上角西北角优先安排）：西北角优先安排）：x x1111=min(s=min(s1 1,d,d1 1)=d)=d1 1=3,B=3,B1 1已满足已满足,划去第一列划去第一列,s,s1 1ss1 1-x-x1111；x x1212=min(s=min

12、(s1 1-x-x1111,d,d2 2)=4,A)=4,A1 1已满足已满足,划去第一行；划去第一行；划去划去m+n-1m+n-1行行(列列)大功告成。大功告成。1/21/2023运筹学第六讲运输问题最小元素法最小元素法最后得的初始基可行解。最后得的初始基可行解。31144363333总运费总运费8686.1/21/2023运筹学第六讲运输问题找初始基可行解找初始基可行解的最小元素法的最小元素法尽量先用运价小的（就近优先安排，尽量先用运价小的（就近优先安排，可能可能“因小失大因小失大”）：）：c c2121=min(cmin(cijij)=1,x)=1,x2121=min(s=min(s2

13、2,d,d1 1)=3)=3划划去第一列（去第一列（B B1 1已满足）已满足）s s2 2ss2 2-x-x2121；c c2323=min,x=min,x2323=min(s=min(s2 2-x-x2121,d,d3 3)=1)=1划去第划去第二行（二行（A A2 2已满足）已满足）d d3 3dd3 3-x-x2323；划去划去m+n-1m+n-1行行(列列)大功告成。大功告成。1/21/2023运筹学第六讲运输问题第七章运输问题第七章运输问题产地数产地数m,m,销地数销地数n,n,产销平衡产销平衡,决策变决策变量个数量个数m*n,m*n,等式约束数等式约束数m+n,m+n,不等式约不

14、等式约束数束数0,0,总运价是目标函数总运价是目标函数,要求最小。要求最小。独立等式约束数是独立等式约束数是:_基变量个数是基变量个数是:_非基变量个数是非基变量个数是:_基解是否一定可行基解是否一定可行?_可行解是否是基解可行解是否是基解?_最优解的所有检验数要最优解的所有检验数要:_m+n-1m+n-1m*n-m-n+1不一定不一定不一定不一定全部非负全部非负1/21/2023运筹学第六讲运输问题找出初始基找出初始基可行解可行解x xijij=s si i*d dj j/s/si i是可行解吗是可行解吗?非基变量个数非基变量个数=m*n-m-n+1=m*n-m-n+1。初始基可行解初始基可

15、行解(m+n-1(m+n-1格格)：西北角法西北角法；最小元素法最小元素法;伏格尔伏格尔(Vogel)(Vogel)法法*等等.1/21/2023运筹学第六讲运输问题西北角法西北角法最后得的初始基可行解。最后得的初始基可行解。36622331166总运价总运价:1101/21/2023运筹学第六讲运输问题最小元素法最小元素法“一丝不苟、分秒不差、严上加严一丝不苟、分秒不差、严上加严”。32432435455总运价总运价:1001/21/2023运筹学第六讲运输问题找初始基可行解找初始基可行解西北角法西北角法；总运价总运价:110:110 最小元素法最小元素法;总运价：总运价：100100 35

16、34423632161/21/2023运筹学第六讲运输问题Vogel法求初始解法求初始解求每行求每行(列列)次小和最小运价的差：次小和最小运价的差：7-25121123差中最大的先安排：第一行的差中最大的先安排：第一行的x x1111x111/21/2023运筹学第六讲运输问题9573846Vogel法求初始解法求初始解优先安排极差大的行或列中最小运价优先安排极差大的行或列中最小运价3651452252181533151/21/2023运筹学第六讲运输问题Vogel法法VogelVogel法的初始运输方案总运价：法的初始运输方案总运价：95738463453151101101001008888

17、1/21/2023运筹学第六讲运输问题基可行解是否基可行解是否最优的判别最优的判别基可行解是否最优的判别基可行解是否最优的判别(闭回路法、位势法闭回路法、位势法*)；闭回路法闭回路法求检验数求检验数,因为非最因为非最优的基可行解改进时用闭回路优的基可行解改进时用闭回路调整调整,所以优先介绍所以优先介绍“闭回路法闭回路法”位势法位势法求检验数求检验数*.1/21/2023运筹学第六讲运输问题704010闭回路法闭回路法对每个非基变量对每个非基变量(如如x x2121)求它的闭回路求它的闭回路;求它的检验数：求它的检验数：7-100+2-1=-9207-100+2-1=-9203-1+2-3=10

18、。检验数无负是最优解，否则可调整检验数无负是最优解，否则可调整。314633-110121/21/2023运筹学第六讲运输问题闭回路法调优闭回路法调优非基变量如非基变量如x x2424检验数负检验数负,不是最优解不是最优解;利用它的闭回路调整利用它的闭回路调整:min(1,3)=1;:min(1,3)=1;调整调整:奇加偶减，新方案再检验奇加偶减，新方案再检验。314633121-1101210521/21/2023运筹学第六讲运输问题位势法判优位势法判优方案要检验时方案要检验时,逐个非基变量求检验逐个非基变量求检验数太繁，可用位势法求检验数；数太繁，可用位势法求检验数；检验数全部非负检验数全

19、部非负,找到最优解找到最优解(不唯一不唯一)。3132560310-23-590221912任填一任填一1/21/2023运筹学第六讲运输问题34531 5位势法判优位势法判优VogelVogel的方案检验的方案检验,逐个非基变量用闭回逐个非基变量用闭回路法求检验数太繁，用位势法求检验数；路法求检验数太繁，用位势法求检验数；检验数有负检验数有负,不是最优解。不是最优解。077-52-593342-111找闭回路。找闭回路。x22x22进基进基,x12,x12出基出基5061/21/2023运筹学第六讲运输问题34536 0位势法判优位势法判优x x2222进基进基,x,x1212出基后新方案再

20、用位势法求检出基后新方案再用位势法求检验数来判优；验数来判优；检验数无负数检验数无负数,是最优解是最优解,总运费总运费8383。067-52-4814431021/21/2023运筹学第六讲运输问题表上作业法表上作业法求求解解的讨论的讨论最优解非基变量的检验数有等于最优解非基变量的检验数有等于0 0时，会时，会有无穷多最优解，至少两个基最优解。有无穷多最优解，至少两个基最优解。产销不平衡时不能直接用表上作业法；产销不平衡时不能直接用表上作业法；基变量取基变量取0 0的处理的处理:要填数划行要填数划行(或列或列)，否否则则不能判优不能判优,位势不能确定位势不能确定,会使有的非基变会使有的非基变量

21、量(空格空格)的闭回路找不出来。的闭回路找不出来。解的整数性：产销量都是非负整数时，初解的整数性：产销量都是非负整数时，初始基可行解和调整后的基可行解直到最优基始基可行解和调整后的基可行解直到最优基解也是解也是整数解整数解 因为只做过加减运算因为只做过加减运算。1/21/2023运筹学第六讲运输问题一个一个耐人寻味的耐人寻味的例子例子求解运输问题求解运输问题1 1：0.10.91.10.90.90.1 0.9 1.1013-25也可以用闭回路也可以用闭回路法求法求x21x21的检验数：的检验数：检验数检验数0,0,初始初始解最优：运费解最优：运费3.93.91/21/2023运筹学第六讲运输问

22、题一个一个耐人寻味的耐人寻味的例子例子求解运输问题求解运输问题2 2：102001 0 2013-25检验数检验数0,0,初始解初始解最优：运费最优：运费3 3总运量多了运费总运量多了运费反而少了。反而少了。这个这个0 0一定要一定要填，填，x x1212是基变是基变量量,否否则则1/21/2023运筹学第六讲运输问题一个一个耐人寻味的耐人寻味的例子例子求解下面两个运输问题：求解下面两个运输问题：左面问题：最优总运费左面问题：最优总运费3.93.9右面问题：运量多了，但最优总右面问题：运量多了，但最优总运费运费3,3,反而减少了反而减少了。0.1 0.9 1.11 0 2这种节省的途径很难被人

23、发现。这种节省的途径很难被人发现。1/21/2023运筹学第六讲运输问题课堂练习课堂练习求解运输问题：求解运输问题：这几个运输问题的运价完全相同这几个运输问题的运价完全相同;这几个运输问题的产销都平衡。这几个运输问题的产销都平衡。2.3这几个运输问题最优解的总运费这几个运输问题最优解的总运费应该哪个大？应该哪个大？右边的运量大右边的运量大,费用多费用多?=1,91/21/2023运筹学第六讲运输问题作作 业业P.152P.152第七章习题第七章习题1(1)1(1)思考题：思考题：1 1、如何用、如何用ExcelExcel解解运输问题？运输问题？2 2、建议开始关注周围有没、建议开始关注周围有没有运筹学的应用之地？有运筹学的应用之地？1/21/2023运筹学第六讲运输问题补充作业补充作业*求下列产销不平衡的运输问题。求下列产销不平衡的运输问题。1/21/2023运筹学第六讲运输问题