运筹学第七讲运输问题

教案要点复习可行解、基可行解，基及非基变量。本节重点：运输问题表上作业法步骤：⑴平衡产销；⑵找出初始基可行解[西北角法、最小元素法]；⑶判别基可行解是否最优[闭回路法、位势法]；⑷非最优的基可行解的迭代[闭回路调整法].

难点：计算步骤，基与非基，位势计算。注意：细心，步骤，好的初始解通常能减少迭代次数。带《数学模型》，《线性规划理论及其应用》两书。第一页，共二十页。8/11/2023运筹学第七讲运输问题绍兴文理学院工学院计算机系运筹学第二页，共二十页。8/11/2023运筹学第七讲运输问题第七章运输问题一类特殊类型的LP问题——运输问题；模型、表上作业法应用、用Excel求解讨论第三页，共二十页。8/11/2023运筹学第七讲运输问题运输问题某种产品从若干个产地(产量已知)运往若干个销地(销量已知)，已知各地间运输单价，求总运费最小的运输方案。此问题是我国科学家(王元,越民义等)在1959年前率先研究讨论的，并获得了：表上作业法和图上作业法等重要结果。第四页，共二十页。8/11/2023运筹学第七讲运输问题运输问题产地数m=2,销地数n=3,产销平衡，决策变量个数m*n,等式约束数m+n，不等式约束数0,目标函数是总运价,要求最小。第五页，共二十页。8/11/2023运筹学第七讲运输问题运输问题目标函数：s.t.第六页，共二十页。8/11/2023运筹学第七讲运输问题运输问题它是典型的LP问题，但若用单纯形法，[等式约束数m+n(但当产销平衡的时候其中有一个是多余的，),不等式约束数0]初始基可行解就显得很难求，决策变量个数也较大，我国科学家在上世纪五十年代提出了解运输问题的图上作业法和表上作业法。第七页，共二十页。8/11/2023运筹学第七讲运输问题表上作业法运输问题的表上作业法：平衡产销；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最优的判别(闭回路法、位势法*)；非最优的基可行解的改进(闭回路调整法).

第八页，共二十页。8/11/2023运筹学第七讲运输问题平衡产销运输问题中产销不平衡时：产>销：增加一个假想的仓库，运费为0，当新销地。产<销：增加一个假想的产地，运费为0。总可以调整为产销平衡。

第九页，共二十页。8/11/2023运筹学第七讲运输问题找出初始基可行解运输问题的独立的等式约束数=系数矩阵的秩=基变量个数=m+n-1，非基变量个数=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格尔(Vogel)法*等.

第十页，共二十页。8/11/2023运筹学第七讲运输问题西北角法最后得的初始基可行解。34422223366第十一页，共二十页。8/11/2023运筹学第七讲运输问题找初始基可行解的西北角法尽量用下标小的（左上角——西北角优先安排）：x11=min(s1,d1)=d1=3,划去第一列（B1已满足）,s1←s1-x11；x12=min(s1-x11,d2)=4,划去第一行（A1已满足）；……划去m+n-1行(列)大功告成。第十二页，共二十页。8/11/2023运筹学第七讲运输问题最小元素法最后得的初始基可行解(不同于西北角法)。31144363333第十三页，共二十页。8/11/2023运筹学第七讲运输问题找初始基可行解的最小元素法尽量先用运价小的（就近优先安排，可能“因小失大”）：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行(列)大功告成。第十四页，共二十页。8/11/2023运筹学第七讲运输问题基可行解是否最优的判别基可行解是否最优的判别(闭回路法、位势法*)；闭回路法求检验数,因为非最优的基可行解改进时用闭回路调整,所以优先介绍“闭回路法”位势法求检验数*.

第十五页，共二十页。8/11/2023运筹学第七讲运输问题闭回路法对每个非基变量(如x11)求它的闭回路;121求它的检验数：3-1+2-3=1>0。检验数无负是最优解，否则可调整。314633-11012第十六页，共二十页。8/11/2023运筹学第七讲运输问题闭回路法调优非基变量如x24检验数负,不是最优解;利用它的闭回路调整:min(1,3)=1;调整:奇加偶减，新方案再检验……。314633121-110121052第十七页，共二十页。8/11/2023运筹学第七讲运输问题位势法判优新方案再检验,逐个非基变量求检验数太繁，可用位势法求检验数；检验数全部非负,找到最优解(不唯一)。3132560310-23-590221912第十八页，共二十页。8/11/2023运筹学第七讲运输问题用Excel求解可以利用电子表格“Excel”中的“规划求解”来解运输问题：先产销平衡；找一个预解，求出行、列和；求出目标函数的值；用“工具”下的“规划求解”……。作业P.150№1a;P.152№6ab第十九页，共二十页。8/11/2023运筹学第七讲运输问题内容总结教案要点。复习可行解、基可行解，基及非基变量。本节重点：运输问题表上作业法步骤：⑴平衡产销。⑵找出初始基可行解[西北角法、最小元素法]。⑶判别基可行解是否最优[闭回路法、位势法]。⑷非最优的基可行解的迭代[闭回路调整法].。注意：细心，步骤，。8/9/2023。运筹学第七讲运输问题。一类特殊类型的LP问题——运输问题。某种产品从若干个产地(产量已知)运往若干个销地(销量