运筹学第七讲运输问题

2019/8/14运筹学第七讲运输问题绍兴文理学院工学院计算机系运筹学2019/8/14运筹学第七讲运输问题第七章运输问题一类特殊类型的LP问题——运输问题；模型、表上作业法应用、用Excel求解讨论2019/8/14运筹学第七讲运输问题运输问题某种产品从若干个产地(产量已知)运往若干个销地(销量已知)，已知各地间运输单价，求总运费最小的运输方案。此问题是我国科学家(王元,越民义等)在1959年前率先研究讨论的，并获得了：表上作业法和图上作业法等重要结果。2019/8/14运筹学第七讲运输问题运输问题产地数m=2,销地数n=3,产销平衡，决策变量个数m*n,等式约束数m+n，不等式约束数0,目标函数是总运价,要求最小。销地运价产地B1B2B3产量A1646200A2655300销量150150200500销地运量产地B1B2B3产量A1x11x12x13200A2x21x22x23300销量1501502005002019/8/14运筹学第七讲运输问题运输问题,xcfminm1in1jijij目标函数：m..1isxin1jijn..1jdxjm1iijn..1j,m..1i,0xijs.t.2019/8/14运筹学第七讲运输问题运输问题它是典型的LP问题，但若用单纯形法，[等式约束数m+n(但当产销平衡的时候其中有一个是多余的，),不等式约束数0]初始基可行解就显得很难求，决策变量个数也较大，我国科学家在上世纪五十年代提出了解运输问题的图上作业法和表上作业法。n1jm1iijm1in1jijxx2019/8/14运筹学第七讲运输问题表上作业法运输问题的表上作业法：平衡产销；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最优的判别(闭回路法、位势法*)；非最优的基可行解的改进(闭回路调整法).2019/8/14运筹学第七讲运输问题平衡产销运输问题中产销不平衡时：产销：增加一个假想的仓库，运费为0，当新销地。产销：增加一个假想的产地，运费为0。总可以调整为产销平衡。2019/8/14运筹学第七讲运输问题找出初始基可行解运输问题的独立的等式约束数=系数矩阵的秩=基变量个数=m+n-1，非基变量个数=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格尔(Vogel)法*等.2019/8/14运筹学第七讲运输问题西北角法最后得的初始基可行解。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量365620344222233662019/8/14运筹学第七讲运输问题找初始基可行解的西北角法尽量用下标小的（左上角——西北角优先安排）：x11=min(s1,d1)=d1=3,划去第一列（B1已满足）,s1←s1-x11；x12=min(s1-x11,d2)=4,划去第一行（A1已满足）；……划去m+n-1行(列)大功告成。2019/8/14运筹学第七讲运输问题最小元素法最后得的初始基可行解(不同于西北角法)。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量365620311443633332019/8/14运筹学第七讲运输问题找初始基可行解的最小元素法尽量先用运价小的（就近优先安排，可能“因小失大”）：c21=min(cij)=1,x21=min(s2,d1)=3划去第一列（B1已满足）s2←s2-x21；c23=min,x23=min(s2-x21,d3)=1划去第二行（A2已满足）d3←d3-x23；……划去m+n-1行(列)大功告成。2019/8/14运筹学第七讲运输问题基可行解是否最优的判别基可行解是否最优的判别(闭回路法、位势法*)；闭回路法求检验数,因为非最优的基可行解改进时用闭回路调整,所以优先介绍“闭回路法”位势法求检验数*.2019/8/14运筹学第七讲运输问题闭回路法对每个非基变量(如x11)求它的闭回路;121求它的检验数：3-1+2-3=10。检验数无负是最优解，否则可调整。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量365620314633-110122019/8/14运筹学第七讲运输问题闭回路法调优非基变量如x24检验数负,不是最优解;利用它的闭回路调整:min(1,3)=1;调整:奇加偶减，新方案再检验……。销地运价产地B1B2B3B4产量A13113107A219284A3741059销量365620314633121-1101210522019/8/14运筹学第七讲运输问题位势法判优新方案再检验,逐个非基变量求检验数太繁，可用位势法求检验数；检验数全部非负,找到最优解(不唯一)。销地运价产地B1B2B3B4uiA1311310A21928A374105vj3132560310-23-5902219122019/8/14运筹学第七讲运输问题用Excel求解可以利用电子表格“Excel”中的“规划求解”来解运输问题：先产销平衡；找一个预解，求出行、列和；求出目标函数的值；用“工具”下的“规划求解”……。作业P.150№1a;P.152№6ab