03 第三章 运输问题.pptx

第1页：运输问题章节目录

本章共分四节：

• 3.1 运输问题及其数学模型
• 3.2 表上作业法（最小元素法、位势法、闭回路法）
• 3.3 产销不平衡的运输问题
• 3.4 运输问题应用举例

第2页：运输问题实例与单位运价表

例：某公司经销一种产品，下设三个工厂、四个销售部。三个工厂的日产量分别为 A1—7 吨、A2—4 吨、A3—9 吨；各销售部的日销量分别为 B1—3 吨、B2—6 吨、B3—5 吨、B4—6 吨。各厂到各销售部的单位产品运价如下表，问应如何调运产品，才能完成运输任务而使运费最省。

源文件该页表格的行列被打散，表中运价按第3页线性规划模型中的系数还原（A1: 3、11、3、10；A2: 1、9、2、8；A3: 7、4、10、5）。

第3页：运输问题的数学模型

用线性规划法处理此问题。设由产地 i 到销地 j 的运量为 xij，模型为：

min z = 3x11 + 11x12 + 3x13 + 10x14 + x21 + 9x22 + 2x23 + 8x24 + 7x31 + 4x32 + 10x33 + 5x34

满足：x11 + x12 + x13 + x14 = 7；x21 + x22 + x23 + x24 = 4；x31 + x32 + x33 + x34 = 9；x11 + x21 + x31 = 3；x12 + x22 + x32 = 6；x13 + x23 + x33 = 5；x14 + x24 + x34 = 6；xij ≥ 0（i = 1,2,3；j = 1,2,3,4）。

运输问题一般用表上作业法求解，需建立表格模型：单位运价表与产销平衡表。

第4页：运输问题的一般模型

有 m 个生产地点生产或供应某种物资，有 n 个销售地点销售或需求该种物资。若第 i 个产地的产量为 ai，第 j 个销地的销量为 bj，并且有 Σai = Σbj，而第 i 个产地到第 j 个销地的单位运价为 cij，使总运费达到最小的运输问题的数学模型为：

min z = Σmi=1 Σnj=1 cijxij，满足 Σnj=1 xij = ai（i = 1,…,m）、Σmi=1 xij = bj（j = 1,…,n）、xij ≥ 0。

第5页：表上作业法的步骤

表上作业法的步骤类似于单纯形法：

1. 给出初始调运方案
2. 检验方案是否最优，若是最优解则停止计算，否则转下一步
3. 调整调运方案，得到新的方案
4. 重复第 2、3 步，直到求出最优方案

第6页：最小元素法

3.2.1 给出初始调运方案最常用的方法——最小元素法。表上作业法要求：数字格必须为 m + n - 1 个，且有数字格不构成闭回路。

源文件该页含多张被打散的表格，此处按「单位运价 + 产量销量」结构还原，各格的调运量数字建议对照原图核对。

第7页：最小元素法的退化处理

最小元素法中的退化情况：出现退化时，要在同时被划去的行列中任选一个空格填 0，此格作为有数字格。

第8页：伏格尔法

3.2.1 给出初始调运方案的另一种方法——伏格尔法：

1. 从单位运价表中的每行每列中分别找出两个最小元素之差，所有差值中最大的一个所在的行或列中最小的元素所在位置即为进行调动的位置
2. 在产销平衡表上对应的调运位置尽最大可能调运
3. 在单位运价表中划掉已满足的行或列的运价
4. 重复上述步骤，直至所有的运价都被直线覆盖掉，即得到一初始方案

示例：各行两个最小元素之差分别为 0、1（A1）、0（A2）、1（A3）等，按差值最大的行或列优先调动。

源文件该页含两最小元素之差的排行表，数值被打散，建议对照原图核对。

第9页：位势法

3.2.2 最优性检验的方法——位势法：对有数字格令 ui + vj = cij 求出位势，再对空格计算检验数 σij = cij - (ui + vj)。若所有检验数非负，则是最优解。

源文件该页位势表与检验数表数字被打散，括号内为检验数示例值，建议对照原图核对。

第10页：闭回路法

3.2.3 方案调整的方法——闭回路法：

1. 从一个检验数为负数且最小的空格出发，和其它数字格构成闭回路。可证，此闭回路存在且唯一
2. 在闭回路上进行运量调整，使选定空格处的运量尽可能地增加
3. 运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案

源文件该页两张调运表数字被打散，具体运量建议对照原图核对。

第11页：表上作业法举例

3.2.4 表上作业法举例：对当前调运方案求位势表与检验数表，表中出现负检验数（如 -1），故不是最优解，需用闭回路法调整。

源文件该页检验数被打散，括号数值为示例，建议对照原图核对。

第12页：表上作业法举例（续）

表上作业法举例（续）：经闭回路调整后重新求位势与检验数，表中检验数都非负，得最优解。

源文件该页表格数字被打散，检验数与最终调运量建议对照原图核对。

第13页：产销不平衡的运输问题

表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况：

（1）产大于销

即 Σmi=1 ai > Σnj=1 bj。此时增加一个假想的销地 n+1，该销地的销量为 Σai - Σbj，而各产地到假想销地的单位运价定为 0，就转化成产销平衡的运输问题

（2）销大于产

即 Σmi=1 ai < Σnj=1 bj。此时增加一个假想的产地 m+1，该产地的产量为 Σbj - Σai，而假想产地到各销地的单位运价定为 0，就转化成产销平衡的运输问题

第14页：化肥供应调运实例

产销不平衡的运输问题举例：设有三个化肥厂供应四个地区的农用化肥。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送化肥的单位运价如下表。试求出总运费最省的花费调运方案。

源文件该页为表格排版，行列表头被打散，数值按「产量行 + 需求行」结构还原；C 厂到Ⅳ地区的运价源文标记为 M（不允许调运），建议对照原图核对。

第15页：化肥调运问题的求解

解：三个厂的总产量为 160 万吨，四个地区的最低需求为 110 万吨，最高需求为无限。地区Ⅳ每年最多能分配到 60 万吨，这样四个地区最高需求为 210 万吨，销大于产。于是，增加虚产地 D，产量为 50 万吨。还要把地区Ⅰ和Ⅳ的需求分为两部分（Ⅰ′、Ⅰ″ 与 Ⅳ′、Ⅳ″），建立表格模型求解。

源文件该页为双表并列排版，需求拆分后的销量与 M（不允许调运）位置由求解逻辑推定，建议对照原图核对。

第16页：柴油机生产计划实例

例：某厂按合同规定须于当年每个季度末分别提供 10、15、25、20 台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。又知如果生产出来的柴油机当季度不交货，每台每季度的存储维护费为 0.15 万元。试安排全年生产计划，使总费用最低。

第17页：柴油机生产计划的求解

解：各季度都产出产品，都可看作产地；各季度都有定货，都可看作销地。这是一个产大于销的运输问题，需增加虚销地 D。表格模型如下。

各季产量为 25、35、30、10 台，总产量 100 台大于总销量 70 台，虚销地 D 的销量为 30 台；跨季交货的运价 = 本季成本 + 0.15 × 存储季数。

第18页：航运公司配船实例

例：某航运公司承担六个港口城市 A、B、C、D、E、F 间四条航线的货物运输任务。各航线的起点、终点、日航班数如下：航线1（B→C）2 班，航线2（D→E）3 班，航线3（A→F）1 班，航线4（F→A）1 班。假定各航线使用的船只相同，各城市间的航程天数如下（矩阵）。又知每条船每次装卸货时间各需 1 天，问该公司至少应配备多少条船？

源文件该页航程矩阵被打散为逐行数字串，此处按「从/到」对称结构还原，建议对照原图核对。

第19页：配船问题的求解

解：所需船只分成两部分：

（1）载货航行需要的船只数

3 × 19 + 2 × 5 + 9 + 15 = 91 条

（2）各港口间调度需要的船只数

各港口每天船只的余缺数为：A -1、B -1、C 2、D -3、E 3、F 0，通过调度模型求得调度需要的船只数为 2 + 5 + 13 + 17 + 3 = 40 条

故该公司至少应配备 91 + 40 = 131 条船。

源文件该页余缺数与调度运量被打散，加总的两部分数值按原文算式保留，建议对照原图核对。

第20页：