运筹学运输问题课件.ppt

《运筹学运输问题课件.ppt》由会员分享，可在线阅读，更多相关《运筹学运输问题课件.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 运输与指派问题运输问题的表示运输问题模型、运价表运输问题的求解 表上作业法 指派问题 1-运 输、指 派 和 转 运 问 题，实 际 上 都 可 以 用 L.P.模 型 加 以 描 述，所 以 可 以 认 为 它 们 是 L.P.的特例单 列 一 章 的 原 因 在 于：应 用 面 极 广，实 践 性很 强，而 特 有 的 数 学 结 构 使 得 人 们 设 计 出 了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法求解运输简述2-提出问题 有A1，A2，A3 三个砖瓦厂月产量分别为14，27，19万块，供应B1，B2，B3，B4 四个工地，月需要量分别为22，13，12，

2、13万块，每万块运费如下表，求总运费最少的方案。A1 14A2 27A3 1922 13 12 13B1 B2 B3 B46(千元）7 5 38 4 2 75 9 10 6运输问题3-运输问题线性规划模型供应地约束需求地约束4-3.1 运输问题模型与性质一、运输问题的数学模型 1、运 输 问 题 的 一 般 提 法：某 种 物 资 有 若 干产 地 和 销 地，现 在 需 要 把 这 种 物 资 从 各 个 产地 运 到 各 个 销 地，产 量 总 数 等 于 销 量 总 数。已 知 各 产 地 的 产 量 和 各 销 地 的 销 量 以 及 各 产地 到 各 销 地 的 单 位 运 价（或

3、运 距），问 应 如何 组 织 调 运，才 能 使 总 运 费（或 总 运 输 量）最省？5-运输问题的一般数学模型 有m 个产地生产某种物资，有n 个地区需要该类物资 令a1,a2,am表示各产地产量，b1,b2,bn表示各销地的销量，ai=bj 称为产销平衡 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下：运输问题6-二、运输问题的特点与性质1约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m 行n 行7-矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,，0，1，0，,0,1

4、,0,0)T，其中两个元素1分别处于第i 行和第m+j 行。8-三、运输问题的求解方法 1、单纯形法（为什麽？）2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法9-3.2 运输问题的表上作业法 一、表 上 作 业 法 的 基 本 思 想 是:先 设 法 给 出一 个 初 始 方 案,然 后 根 据 确 定 的 判 别 准 则 对 初始 方 案 进 行 检 查、调 整、改 进，直 至 求 出 最优方案，如图3-1 所示。表 上 作 业 法 和 单 纯 形 法 的 求 解 思 想 完 全 一 致，但是具体作法更加简捷。10-确定初始方案(初 始 基本可行解)改进调整（换基迭代）否 判

5、定是否 最 优？是结 束最优方案图3-1 运输问题求解思路图11-二、初始方案的确定 1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。表3-3 是两个产地、三个销地的运输问题作业表。12-调 销地 运 量产地 B1 B2 B3 产 量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销 量 b1 b2 b3表3-3 运输问题作业表（运价表）13-3、举例 例3-2 甲、乙 两 个 煤 矿 供 应A、B、C三 个 城 市 用 煤，各 煤 矿 产

6、 量 及 各 城市 需 煤 量、各 煤 矿 到 各 城 市 的 运 输距 离 见 表3-4，求 使 总 运 输 量 最 少 的调运方案。14-表3-4 例3-2 有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量（供应量）C B A运距 城市煤矿15-例3-2 的数学模型16-初始解的确定 一、最小元素法&最小元素法的基本思想是最小元素法的基本思想是“就近供应就近供应”；二、西北角法&西北角法则不考虑运距（或运价），每次都选剩余表 西北角法则不考虑运距（或运价），每次都选剩余表格的左上角（即西北角）元素作为基变量，其

7、它过程 格的左上角（即西北角）元素作为基变量，其它过程与最小元素法相同 与最小元素法相同；三、沃格尔法（VOGLE）17-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用最小元素法确定例3-2 初始调运方案 150 100100 10010010010018-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150

8、 200 450 用西北角法确定例3-2 初始调运方案 100 100100 50 50200 20019-得到初始调运方案为：x11=100，x12=100，x22=50，x23=200 20-元 素 差 额 法（Vogel 近 似 法）最 小 元 素 法 只 考 虑 了 局 部 运 输 费 用最 小。有 时 为 了 节 省 某 一 处 的 运 费，而 在 其 它 处 可 能 运 费 很 大。元 素 差 额 法 对 最 小 元 素 法 进 行 了 改 进，考 虑 到 产 地 到 销 地 的 最 小运 价 和 次 小 运 价 之 间 的 差 额，如 果 差 额 很 大，就 选 最 小 运 价

9、先 调运，否则会增加总运费。例如下面两种运输方案前一种按最小元素法求得，总运费是Z1=108+52+151=105后 一 种 方 案 考 虑 到C11与C21之 间 的 差 额 是82=6，先 调 运x21，再是x22，其次是x12这时总运费Z2=105+152+51=85Z1。21-基于以上思路，元素差额法求初始基本可行解的步骤是：第 一 步：求 出 每 行 次 小 运 价 与 最 小 运 价 之 差，记 为 ui，i=1,2,m；同 时 求 出 每 列 次 小 运 价 与 最 小 运 价 之 差，记 为vj，j=1，2，n；第 二 步：找 出 所 有 行、列 差 额 的 最 大 值，即L=

10、maxui，vi，差额L 对应行或列的最小运价处优先调运；第 三 步：这 时 必 有 一 列 或 一 行 调 运 完 毕，在 剩 下 的 运 价 中 再 求最 大 差 额，进 行 第 二 次 调 运，依 次 进 行 下 去，直 到 最 后 全 部 调 运完毕，就得到一个初始调运方案。用 元 素 差 额 法 求 得 的 基 本 可 行 解 更 接 近 最 优 解，所 以 也 称 为 近似方案。22-表5-13B1B2B3B4aiA15 8 9 12 15A21 7 2 4 25A36 10 13 8 20bj20 10 5 25 60【例5.5】用元素差额法求表513运输问题的初始基本可行解。【

11、解】求行差额 ui,i=1,2,3 及列差额vj,j=1,2,3,4.计算公式为 ui=i 行次小运价i 行最小运价 vj=j 列次小运价j 例最小运价23-表514 BjAiB1B2B3B4aiuiA15 8 9 1215 3A21 7 2 425 1A36 10 13 820 2bj20 10 5 25 60vj4 1 7 4【】524-表5-15 BjAiB1B2B3B4aiuiA15 8 9 1215 3A21 7 2 425 35A36 10 13 820 2bj20 10 5 25 60vj4 1420 0【】25-表5-16 BjAiB1B2B3B4aiuiA15 8 9 121

12、5 4A21 7 2 4255A36 10 13 820 2bj20 10 5 25 60vj2420 0【】1020526-基本可行解为总运费Z=108+201+52+208=270。27-检 查 当 前 调 运 方 案 是 不 是 最 优 方 案 的 过 程 就 是最 优 性 检 验。检 查 的 方 法：计 算 非 基 变 量（未填 上 数 值 的 格，即 空 格）的 检 验 数（也 称 为 空格 的 检 验 数），若 全 部 大 于 等 于 零，则 该 方 案就是最优调运方案，否则就应进行调整。一、闭回路法二、对偶变量法 三、最优性检验28-1、闭回路法 什么是闭回路？表中的折线构成一条

13、封闭曲线，且所有的边都是水平或垂直的；（a）（b）（c）（d）29-以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。1、闭回路法 30-约 定 作 为 起 始 顶 点 的 非 基 变 量 为 奇 数 点1 其它 顶 点 顺 次 排 列，那 麽，该 非 基 变 量xij的 检验数：现在，在用最小元素法确定例3-2 初始调运方案的基础上，计算非基变量X12的检验数：=（闭回路上奇数次顶点运距或运

14、价之和）-（闭回路上偶数次顶点运距或运价之和）（3-6）31-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100100 150例例3-23-2初始调运方案中以初始调运方案中以XX1212(X(X2121)为起点的闭回路为起点的闭回路32-非基变量X12的检验数：非基变量X21的检验数：=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）

15、=15。经 济 含 义：在 保 持 产 销 平 衡 的 条 件 下，该 非基 变 量 增 加 一 个 单 位 运 量 而 成 为 基 变 量 时 目标函数值的变化量。33-以例3-2 初始调运方案为例，设置位势变量 和，在初始调运方案表的基础上增加一行和一列（见下页表格）。2、位势法 34-例3-2 初始调运方案位势变量对应表 调 销地 运 量产地 B1 B2 B3产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450位势变量vj v1 v2 v3100 100100 150位势变量 ui

16、 u1 u235-2、位势法 然后构造下面的方程组：（3-7）36-方程组的特点：方 程 个 数 是m+n-1=2+3-1=4 个，位 势 变 量 共有m+n=2+3=5 个，通 常 称ui为 第i 行 的 位 势，称vj为第j 列的位势；初 始 方 案 的 每 一 个 基 变 量xij对 应 一 个 方 程-所 在 行 和 列 对 应 的 位 势 变 量 之 和 等 于 该 基变量对应的运距（或运价）：ui+vj=cij；方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。37-给 定 自 由 变 量 一 个 值，解 方 程 组 式（3-7），即 可 求 得 位 势 变 量

17、 的 一 组 值，根 据 式（3-6）结合 方 程 组（3-7），推 出 计 算 非 基 变 量xij检 验 数的公式 ij=cij-（ui+vj）（3-8）在 式（3-7）中，令 u1=0，则 可 解 得 v1=90，v3=100，u2=-25，v2=90，于是12=c12-（u1+v2）=70-（0+90）=-2021=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。38-位势法计算非基变量xij检验数的公式 ij=cij-（ui+vj）（3-7）=（闭回路上奇数顶点运距或运价之和）-（闭回路上偶数顶点运距或运价之和）（3-6）闭回路法计算非基变量xij

18、检验数的公式：复习比较检验数计算的两种方法39-四、方案调整 当 至 少 有 一 个 非 基 变 量 的 检 验 数 是 负 值 时，说 明 作 业 表 上 当 前 的 调 运 方 案 不 是 最 优 的，应进行调整。若 检 验 数ij小 于 零，则 首 先 在 作 业 表 上 以xij为起始变量作出闭回路，并求出调整量：ij=min 该闭回路中偶数顶点调运量xij40-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100100 15

19、013 42继续上例，因继续上例，因1212=-20=-20，画出以画出以xx1212为起始变量的闭回为起始变量的闭回路路 41-计算调整量：=Min（100，150）=100。按照下面的方法调整调运量：闭 回 路 上，偶 数 顶 点 的 调 运 量 减 去，奇 数顶 点（包 括 起 始 顶 点）的 调 运 量 加 上；闭 回路之外的变量调运量不变。得到新的调运方案：42-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450100 100200 5

20、0重复上面的步骤，直至求出最优调运方案：43-调 销地 运 量产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450150 50200 5044-结 果 最优调运方案是：x11=50，x12=150，x21=50，x23=200 相应的最小总运输量为：Zmin=9050+70150+8050+75200=34000（吨公里）45-退化问题1、初始解退化。即初始基变量的个数少于m+n 1。必须补足基变量的个数，否则不能正常解出m+n 个ci和 vj2、迭代过程中出现退

21、化 闭合回路中标有“”的基变量同时有多个达到最小 变换后，有多个原基变量变为 0，选运费最大者为出变量，其余保留在新的基础解中 退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。此时，一要耐心，二要正确选择出变量运输问题46-3.3运输问题的推广一、产销不平衡的运输问题供大于求供不应求增加虚拟销地增加虚拟销地 增加虚拟产地增加虚拟产地 产销平衡的运输问题对应的运距（或运价）？转化47-运输问题进一步讨论产销不平衡 产销平衡 供过于求，即 ai bj，增加一个虚收点Dn+1，bn+1=ai-bj,令 wi,n+1=0,i=1,2,m 供小于求，即 ai bj，增加一个虚发点Wm+1，

22、am+1=bj-ai,令 wm+1,j=0,j=1,2,n48-运输问题应用举例如产地3的产量变为130，又B 地区需的115 单位必须满足，试重新确定最优调拨方案49-B1B2B3B4B5aiA1 10 15 20 20 40 50A2 20 40 15 30 30 100A3 30 35 40 55 25 130A4(虚）0 M 0 0 0 20bj25 115 60 30 70 210得到这样的平衡表后50-应用举例1杭州某电视机厂在三个经济区建立分厂，生产产品销往上海，北京，广州。运价表如下，假定产地2的物资至少运出38个单位，产地3的物资至少运出27个电位，试列出新的运价表51-上海

23、 北京 广州虚拟B4aiA1 1 2 2 0 20A2 1 4 5 M 38A21 1 4 5 0 2A3 2 3 3 M 27A31 2 3 3 0 3bj30 20 20 20得到这样的平衡表后52-应用举例2已知某运输问题一个最优调运方案如下表，求K 值范围53-指派问题例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种）语言人员E J G R甲2 15 13 4乙10 4 14 15丙9 14 16 13丁7 8 11 9整数规划54-指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。如指派问题（assignment problem）例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种）语言人员E J G R甲 2 15 13 4乙 10 4 14 15丙 9 14 16 13丁 7 8 11 955