运筹学运输问题补充.ppt

《运筹学运输问题补充.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、运筹学OperationsResearch§1运输问题及其数学模型运输问题（TP，TransportationProblem）：其中2021/7/281运筹学OperationsResearch供需-运费表：问：应如何组织运输，才能既满足供需关系，又使得运费最省？2021/7/282运筹学OperationsResearch▍2021/7/283运筹学OperationsResearch令2021/7/284运筹学OperationsResearch则2021/7/285运筹学OperationsR

2、esearch基：基的构造：结论：运输问题总有最优解.2021/7/286运筹学OperationsResearch在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运输表来实现.2021/7/287运筹学OperationsResearch格子格子表（集）：对应关系：规定：2021/7/288运筹学OperationsResearch令即得基解2021/7/289运筹学OperationsResearch§2初始基可行解运输问题的求解过程并不象一般线性规划问题一样借助于

3、单纯形表，而是借助于运输表来实现；但其算法在理论基础、基本思想、算法步骤等各方面都和单纯形法是一致的.供需平衡型运输问题：2021/7/2810运筹学OperationsResearch一.西北角法基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运输业务.使用条件：已知2021/7/2811运筹学OperationsResearch2021/7/2812运筹学OperationsResearch解：基本格子集为2021/7/2813运筹学OperationsRese

4、arch相应的基本可行解为▍二最小元素法基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小单位运费不唯一时，可任选其一）.使用条件：已知2021/7/2814运筹学OperationsResearch2021/7/2815运筹学OperationsResearch例2求（TP）的一个基本可行解，其中解：基本格子集为2021/7/2816运筹学OperationsResearch相应的基可行解为▍Ex:求平衡型运输问题：的基初始可行解（用两种方法）.2021/7/28

5、17运筹学OperationsResearch三沃格尔（Vogel）法基本思想：若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。使用条件：步骤2021/7/2818运筹学OperationsResearch分别计算运输表中运价的行罚数和列罚数，并分别填入运输表右边和下边的罚数栏里；2.从所有罚数中找出最大者，选中罚数所在行（或列）中运价最小对应的格，填入尽可能大的运输量；3.当供应量已用完

6、（或需求量已满足），划去相应行（或列）；4.重复上述步骤，直到所有行和列都被划掉.2021/7/2819运筹学OperationsResearch§3最优性的检验对运输问题2021/7/2820运筹学OperationsResearch2021/7/2821运筹学OperationsResearch2021/7/2822运筹学OperationsResearch定义2021/7/2823运筹学OperationsResearch于是，检验数为2021/7/2824运筹学OperationsResea

7、rch小结先求位势：再求检验数：2021/7/2825运筹学OperationsResearch例1求（TP）的一个基本可行解，其中解：基本格子集为2021/7/2826运筹学OperationsResearch相应的基可行解为求位势：求检验数：▍2021/7/2827运筹学OperationsResearch同单纯形法一样，若所有检验数均非负，则当前的基可行解即为最优解；否则，应改进之（转轴），以使之更优.闭回路的特点：任意两个相邻的格子的行指标相同时，其列指标必不相同；列指标相同时，其行指标必不

8、相同.即任意两个相邻格子的行（列）指标不能同时相同，也不能同时不同.2021/7/2828运筹学OperationsResearch如2021/7/2829运筹学OperationsResearch例1（续）取取▍2021/7/2830运筹学OperationsResearch令▍2021/7/2831运筹学OperationsResearch例1（续）取划分:2021/7/2832运筹学OperationsResearch修正：▍2021/7/2833运筹学Oper