运筹学运输问题(补充)

1、运 筹 学 Operations Research1 运输问题及其数学模型运输问题（TP，Transportation Problem）： 其中2022/8/11运 筹 学 Operations Research供需-运费表： 问：应如何组织运输，才能既满足供需关系，又使得运费最省？2022/8/12运 筹 学 Operations Research2022/8/13运 筹 学 Operations Research令2022/8/14运 筹 学 Operations Research则2022/8/15运 筹 学 Operations Research基：基的构造：结论：运输问题总有最优解.

2、2022/8/16运 筹 学 Operations Research在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运输表来实现. 2022/8/17运 筹 学 Operations Research格子格子表（集）： 对应关系：规定：2022/8/18运 筹 学 Operations Research令即得基解2022/8/19运 筹 学 Operations Research2 初始基可行解 运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于运输表来实现；但其算法在理论基础、基本思想、算法步骤等各方面都和单纯形法是一致的. 供需平衡型运输问

3、题：2022/8/110运 筹 学 Operations Research一.西北角法基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运输业务.使用条件：已知2022/8/111运 筹 学 Operations Research2022/8/112运 筹 学 Operations Research解：基本格子集为2022/8/113运 筹 学 Operations Research相应的基本可行解为二 最小元素法基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小单位运费不唯一时，可任选其一）.使用条件：已知2022/8/114

4、运 筹 学 Operations Research2022/8/115运 筹 学 Operations Research例2 求（TP）的一个基本可行解，其中 解：基本格子集为2022/8/116运 筹 学 Operations Research相应的基可行解为Ex: 求平衡型运输问题：的基初始可行解（用两种方法）.2022/8/117运 筹 学 Operations Research三 沃格尔（Vogel）法基本思想：若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。使用条件：步骤2

5、022/8/118运 筹 学 Operations Research分别计算运输表中运价的行罚数和列罚数，并分别填入运输表右边和下边的罚数栏里；2. 从所有罚数中找出最大者，选中罚数所在行（或列）中运价最小对应的格，填入尽可能大的运输量；3. 当供应量已用完（或需求量已满足），划去相应行（或列）；4. 重复上述步骤，直到所有行和列都被划掉.2022/8/119运 筹 学 Operations Research3 最优性的检验对运输问题2022/8/120运 筹 学 Operations Research2022/8/121运 筹 学 Operations Research2022/8/122运

6、 筹 学 Operations Research定义2022/8/123运 筹 学 Operations Research于是，检验数为2022/8/124运 筹 学 Operations Research小结先求位势：再求检验数：2022/8/125运 筹 学 Operations Research例1 求（TP）的一个基本可行解，其中 解：基本格子集为2022/8/126运 筹 学 Operations Research相应的基可行解为求位势：求检验数： 2022/8/127运 筹 学 Operations Research 同单纯形法一样，若所有检验数均非负，则当前的基可行解即为最优解；

7、否则，应改进之（转轴），以使之更优.闭回路的特点：任意两个相邻的格子的行指标相同时，其列指标必不相同；列指标相同时，其行指标必不相同.即任意两个相邻格子的行（列）指标不能同时相同，也不能同时不同. 2022/8/128运 筹 学 Operations Research如2022/8/129运 筹 学 Operations Research例1（续）取取2022/8/130运 筹 学 Operations Research令2022/8/131运 筹 学 Operations Research例1（续）取划分:2022/8/132运 筹 学 Operations Research修正：2022/8/133运 筹 学 Operations Research4 算法步骤max2022/8/134运 筹 学 Operations Research例 求解运输问题：解：作运输表，并利用最小元素法解之.2022/8/135运 筹 学 Operations Res