《第3章-物流线性规划课件.ppt》由会员分享，可在线阅读，更多相关《第3章-物流线性规划课件.ppt（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3 章 物流线性规划 3.1 线性规划及单纯形法 3.2 线性规划问题的解 3.3 运输问题 3.4 整数规划 3.5 指派问题 第3 章 物流线性规划 本章重点：线 性 规 划 是 运 筹 学 的 一 个 最 基 本 的 分 支，是 科 学、工 程、管理 领 域 广 泛 应 用 的 数 学 模 型。本 章 了 解 线 性 规 划 问 题 的 基 本概 念；掌 握 线 性 规 划 模 型 的 建 立 方 法；掌 握 图 解 法 求 解 线 性规 划 模 型 的 基 本 方 法；掌 握 单 纯 形 表 法 求 解 线 性 规 划 模 型；掌 握 线 性 规 划 模 型 的 物 流 应 用；了
2、解 整 数 规 划 问 题 的 基 本 概念 及 其 数 学 模 型；理 解 分 支 定 界 法 求 解 整 数 规 划 的 基 本 原 理；掌 握0-1 规 划 问 题 的 建 模 方 法；掌 握 限 枚 举 法 求 解0-1 规 划；掌握指派问题的数学模型及其解法。下一页 返回第3 章 物流线性规划 在 物 流 活 动 中，如 何 有 效 地 利 用 有 限 的 人 力 和 物 力 取 得 最 优的 经 济 效 果，或 在 预 定 的 目 标 条 件 下，如 何 花 费 最 少 的 人 力和 物 力 去 实 现 目 标，这 类 问 题 统 称 为 规 划 问 题。规 划 问 题 用数 学
3、语 言 描 述 为：根 据 研 究 问 题 的 目 标 选 取 适 当 的 一 组 变 量，问 题 的 目 标 用 变 量 的 函 数 形 式 表 示，该 函 数 称 为 目 标 函 数，问 题 的 约 束 条 件 用 一 组 由 选 定 变 量 组 成 的 等 式 或 不 等 式 表 达，这 些 等 式 或 不 等 式 称 为 约 束 方 程。即 规 划 问 题 由 一 个 或 几 个目标函数和一组约束方程构成。返回 上一页3.1 线性规划及单纯形法 3.1.1 线性规划的定义 线 性 规 划（Linear Programming，简 记 为LP）是 运 筹学 的 一 个 重 要 分 支。1
4、960 年，前 苏 联 学 者 康 托 洛 维 奇 以 最 佳 资 源 利 用 的 经 济 计 算 一 文 获 诺 贝 尔 奖。从 此 线 性 规划 方 法 用 来 解 决 企 业 的 生 产 经 营 活 动 问 题 并 取 得 了 良 好 的 效果。目 前，大 多 数 计 算 中 心 都 有 线 性 规 划 的 商 用 计 算 机 程 序可 供 使 用。线 性 规 划 已 发 展 成 为 物 流 系 统 现 代 化 管 理 的 有 力工具之一。线 性 规 划 只 有 一 个 目 标 函 数，且 目 标 函 数 和 约 束 方 程 都 是 线性 函 数。用 线 性 规 划 求 解 的 典 型
5、问 题 有 生 产 计 划 问 题、混 合配料问题、下料问题、运输问题等。下一页 返回3.1 线性规划及单纯形法 3.1.2 线性规划的数学模型 通 常 称 现 实 世 界 中 人 们 关 心、研 究 的 实 际 对 象 为 原 型。模 型是 指 将 某 一 部 分 信 息 简 缩、提 炼 而 构 造 的 原 型 替 代 物。数 学模 型 则 是 对 现 实 世 界 的 一 个 特 定 对 象，为 达 到 一 定 目 的，根据 内 在 规 律 做 出 必 要 的 简 化 假 设，并 运 用 适 当 数 学 工 具 得 到的一个数学结构。一般线性规划模型可以表示如下：（3-1）下一页 返回 上一
6、页3.1 线性规划及单纯形法 建立线性规划问题的数学模型一般要经过以下三个步骤。1.根据目标确定决策变量 对 于 一 个 决 策 问 题，首 先 要 明 确 的 是：有 哪 些 可 供 选 择 的 方案。一 般 情 况 下，一 个 决 策 问 题 总 应 有 一 个 以 上 可 供 选 择 的方 案。因 此 可 以 将 其 设 为 变 量，并 以 变 量 的 不 同 取 值 来 表 示可供选择的各个不同方案，这些假设的变量就是决策变量。下一页 返回 上一页3.1 线性规划及单纯形法 一 个 决 策 问 题 到 底 要 设 多 少 个 决 策 变 量，取 决 于 决 策 问 题 本身，但 所 有
7、 假 设 的 决 策 变 量 及 其 取 不 同 的 值，应 反 映 并 包 含该 决 策 问 题 中 所 有 可 供 选 择 的 方 案，以 免 在 建 模 计 算 分 析 中，遗 漏 最 优 的 决 策 方 案。少 设 一 个 决 策 变 量，实 际 上 就 意 味 着这 个 变 量 取 值 为 零；而 多 设 一 个 决 策 变 量，则 其 取 值 可 以 是零，也 可 以 不 为 零，这 大 大 增 加 了 可 供 选 择 的 决 策 方 案，给了 决 策 问 题 更 多 的 机 会 与 选 择。不 过，过 多 的 决 策 变 量，会使 数 学 模 型 复 杂，计 算 困 难。所 以
8、必 须 在 两 者 之 间 作 出 合 理恰当的选择。下一页 返回 上一页3.1 线性规划及单纯形法 2.建立目标函数 作 为 一 个 决 策 问 题，在 决 策 者 的 心 目 中，必 然 会 有 各 种 决 策的 目 标，如 希 望 产 品 产 量 最 大、利 润 最 大、成 本 最 低 等。而这 些 目 标 实 现 的 好 坏，取 决 于 采 用 的 决 策 方 案。因 此，决 策目 标 是 决 策 方 案 的 函 数，也 就 是 决 策 变 量 的 函 数，即 目 标 函数。建 立 数 学 模 型 的 第 二 步，就 是 要 对 每 个 决 策 目 标，建 立 目 标函 数，找 到 目
9、 标 值 与 决 策 变 量 的 数 量 关 系。在 本 章 线 性 规 划中，讨 论 的 数 学 模 型 只 含 一 个 目 标 函 数，且 函 数 关 系 是 线 性的。下一页 返回 上一页3.1 线性规划及单纯形法 3.确定约束条件 一 个 决 策 问 题 的 决 策 目 标 一 般 不 可 能 无 限 制 地 被 优 化。在 其实 现 优 化 的 过 程 中，必 然 会 受 到 有 关 外 界 条 件 的 制 约。这 些限 制 用 数 学 语 言 表 述 出 来 往 往 是 决 策 方 案（即 决 策 变 量）的等 式 或 不 等 式，即 约 束 条 件。在 一 个 决 策 问 题 中
10、，增 加 一 个约 束 条 件，往 往 会 给 决 策 目 标 带 来 不 利 影 响，当 然 也 可 能 没有 影 响，此 时，这 个 约 束 条 件 就 成 为 多 余 的 了。相 反，如 果遗 漏 了 一 个 或 几 个 约 束 条 件，则 可 能 使 计 算 出 的 最 优 目 标 最终 无 法 得 以 实 现，因 为 它 不 能 满 足 那 些 遗 漏 的 约 束 条 件。因此，在 建 立 决 策 问 题 的 数 学 模 型 时，必 须 要 全 面 地 考 虑 所 有与决策目标有关的约束条件，建立一个完整的数学模型。下一页 返回 上一页3.1 线性规划及单纯形法 例3-1 设 某 工
11、 厂 生 产A、B 两 种 产 品，已 知 生 产A、B 产 品 时的 资 源 消 耗 最、单 位 产 品 利 润 及 资 源 限 制 量 如 表3-1 所 示。问A、B 各生产多少公斤，方能使总的利润最大？首 先，设 生 产A、B 两 种 产 品 各 为 x1，x2公 斤，根 据 已 知 条件、要求，问题可归结为如下数学表达式：求一组变量 满足下列条件：使得总利润 取得最大值。下一页 返回 上一页3.1 线性规划及单纯形法 建 立 一 个 实 用 的 线 性 规 划 模 型 必 须 明 确 以 下 四 个 组 成 部 分 的含义：第 一，决 策 变 量。指 决 策 者 为 实 现 规 划 目
12、 标 采 取 的 方 案、措施，是问题中要确定的未知量如式（3-2）中的。第 二，目 标 函 数。线 性 规 划 模 型 的 目 标 是 求 系 统 目 标 的 极 值，可 以 是 求 极 大 值，如 企 业 的 利 润 和 效 率 等，也 可 以 是 求 极 小值，如 成 本 和 费 用 等。式（3-1）即 为 最 优 化 目 标 函 数，简称 目 标 函 数。式 中 即optimize（最 优 化）的 缩 写，根 据 问题要求不同，可以表示为max（最大化）或min（最小化）。下一页 返回 上一页3.1 线性规划及单纯形法 第 三，约 束 条 件。约 束 条 件 是 指 实 现 系 统 目
13、 标 的 限 制 性 因 素，通 常 表 现 为 生 产 力 约 束、原 材 料 约 束、能 源 约 束、库 存 约 束等 资 源 性 约 束，也 有 可 能 表 现 为 指 标 约 束 和 需 求 约 束。式3-2 中 的 s.t.是 英 文Subject to 的 缩 写，是 约 束 条 件 的 意 思，式（3-2）中的个式子就是具体的约束条件。第 四，非 负 限 制。由 于 在 生 产 实 际 问 题 中，资 源 总 是 代 表 一些可以计量的实物或人力，因而一般不能是负数。下一页 返回 上一页3.1 线性规划及单纯形法 3.1.3 线性规划的标准形式 1.线性规划的标准形式 线 性 规
14、 划 问 题 的 标 准 形 要 求 所 有 约 束 必 须 为 等 式 约 束，变 量为非负变量，目标函数求最大值。（3-3）（3-4）下一页 返回 上一页3.1 线性规划及单纯形法 可将式（3-3）简写成（3-3a）（3-4a）2.非标准化线性规划的标准化 对于不符合标准形式（或称非标准形式）的线性规划问题，可分别通过下列方法化为标准形式。（1）目标函数求极小值，即为：（3-5）下一页 返回 上一页3.1 线性规划及单纯形法 因为求 等价于求，令，即化为：（3-5a）（2）约 束 条 件 为 不 等 式。当 约 束 条 件 为“”时，在 不 等式 的 左 端 加 上 一 个 非 负 的“松
15、 弛 变 量”，可 将 不 等 式 化 为 等式；当 约 束 条 件 为“”，在 不 等 式 的 左 端 减 去 一 个 非 负 的“剩 余 变 量”，可 将 不 等 式 化 为 等 式。松 弛 变 量 或 剩 余 变 量在 实 际 问 题 中 分 别 表 示 未 被 充 分 利 用 的 资 源 和 超 用 的 资 源 数，均 未 转 化 为 价 值 和 利 润，所 以 引 进 模 型 后 它 们 在 目 标 函 数 中的系数均为零。下一页 返回 上一页3.1 线性规划及单纯形法（3）决策变量无约束。增加两个新的非负决策变量，令。例3-2 将下列非标准型线性规划问题化为标准型。下一页 返回 上
16、一页3.1 线性规划及单纯形法 解：将 令 将 第 一 个 约 束 方 程 的 左 边 减 去 一 个 非 负 的 松 弛 变 量 x4，将第2、第3 个 约 束 方 程 的 左 边 分 别 加 上 一 个 非 负 的 松 弛 变 量 x5和x6。这样，可以将原来的线性规划问题标准化为：返回 上一页3.2 线性规划问题的解 3.2.1 线性规划问题解的基本概念 对于标准形线性规划问题：（3-6）（3-7）1.可行解。满足约束条件（3-7）的解，称为线性规划问题的可行解。全部可行解的集合称为可行域。下一页 返回3.2 线性规划问题的解 2.最 优 解。使 目 标 函 数（3-6）达 到 最 大
17、值 的 可 行 解 称 为 最优解。3.基、基 变 量、非 基 变 量。A 为 约 束 方 程 组 的 m n 维 系 数矩 阵，秩 为 m，B 是 矩 阵 A 中 阶 的 满 秩 矩 阵，称B 是 线 性 规 划问题的一个基。B 中的每一个列向量 为基向量，与基向量 对应的变量xj称为基变量，其余变量就称为非基变量。下一页 返回 上一页3.2 线性规划问题的解 4.基 解。对 于 基 B，令 非 基 变 量 为 零，求 得 满 足 约 束 条 件 的解，称为基B 对应的基解。5.基可行解。满足变量xj非负条件的基解称为基可行解。3.2.2 线性规划问题的图解法 线 性 规 划 问 题 的 图
18、 解 法 是 建 立 坐 标 系，将 约 束 条 件 在 图 上 表示；确 立 满 足 约 束 条 件 的 解 的 范 围；绘 制 出 目 标 函 数 的 图 形；确 定 最 优 解。图 解 法 主 要 用 于 两 个 变 量 的 线 性 规 划 问 题。这种 方 法 的 优 点 是 直 观 性 强，计 算 方 便，但 缺 点 是 只 适 用 于 问题中有两个变量的情况。下一页 返回 上一页3.2 线性规划问题的解 例3-3 用图解法求解下列线性规划模型的解。解：具体步骤如下（图3-1）：下一页 返回 上一页3.2 线性规划问题的解（1）由全部约束条件构造可行域图形。以x1为横轴，x2为纵轴建
19、立平面直角坐标系，变量的非负条件将图形限制在第一象限。每个约束条件代表一个半平面，如：代表 边界线的下半平面。全部约束条件即各半平面的交集，成为该线性问题的可行域。显然，可行域内各点都满足约束条件，都可作为解，称之为可行解。下一页 返回 上一页3.2 线性规划问题的解（2）做出目标函数的等值线。目标函数代表以Z 为参数，斜率为 的一簇平行线，位于同一条直线上的点具有相同的目标函数值，因而称它为等值线。（3）寻找最优解。沿垂直于等值线的方向（即等值线的法线方向）移动目标函数代表的平行线，当移动到点（）时，目标函数达到最大。从而确定（）为最优点，即，为最优解，Z 的最大值等于。下一页 返回 上一页
20、3.2 线性规划问题的解 3.2.3 线性规划问题的单纯形法 1947 年，美 国 数 学 家 丹 齐 格（George Bernard Dantzig）在 研 究 美 国 空 军 资 源 配 置 问 题 时，提 出 了 求 解 线性 规 划 问 题 的 一 般 解 法 单 纯 形 法（Simplex Method），从 而 为 线 性 规 划 这 门 学 科 奠 定 了 基 础，使 求 解大 规 模 决 策 问 题 成 为 可 能。20 世 纪50 年 代 初，应 用 电 子 计算机求解线性规划问题又获得了成功。1.单纯形法的原理 预备知识：凸集和顶点下一页 返回 上一页3.2 线性规划问题
21、的解 如 果 集 合 中 任 意 两 个 点 X1、X2，其 连 线 上 的 所 有 点 也 都 是 集合C 中的点，称C 为凸集。顶点：凸集C 中满足下述条件的点x 称为顶点。定理1 若线性规划问题存在可行解，则问题的可行域是凸集。引理 线性规划问题的可行解 为可行解的充要条件是X 的正分量所对应的系数列向量是线性独立的。定 理2 线 性 规 划 问 题 的 基 本 可 行 解 x 对 应 线 性 规 划 问 题 可 行域（凸集）的顶点。定 理3 若 线 性 规 划 问 题 有 最 优 解，一 定 存 在 一 个 基 可 行 解 是最优解。下一页 返回 上一页3.2 线性规划问题的解 2.单
22、纯形法的计算步骤 两 个 变 量 的 线 性 规 划 问 题 可 以 用 图 解 法 进 行 求 解，而 当 变 量是 三 个 或 三 个 以 上 且 约 束 条 件 又 多 时，可 行 域 所 在 的 凸 集 表现 为 一 个 凸 多 边 形，在 空 间 上 必 将 是 一 个 凸 几 何 体；因 此 无法 通 过 作 图 来 找 可 行 域，更 无 法 找 到 最 优 解，此 时 图 解 法 就显得无能为力，但这些问题可以利用单纯形法进行求解。本 书 只 介 绍 求 解 约 束 条 件 呈“”的 线 性 规 划 问 题 的 单 纯 形法。下一页 返回 上一页3.2 线性规划问题的解 用例3
23、-1 来阐述单纯形法的具体步骤。解：（1）将线性规划问题化为标准形。引入松弛变量 后将其化为标准形：下一页 返回 上一页3.2 线性规划问题的解（2）寻找初始可行解。约束方程的系数矩阵 易见 的系数列向量 可作为初始可行基下一页 返回 上一页3.2 线性规划问题的解 对应的变量 为基变量，为非基变量。由约束条件得到：令非基变量，得到一个基本可行解，于是目标函数值下一页 返回 上一页3.2 线性规划问题的解（3）最优性检验。当 时，显见目标函数未达到最大值，此时说明两种产品的产出均为零，即工厂处于停工状态，利润为零。若从数学角度观察，Z 是关于 的一个二元函数，可见，只要将其中任何一个变量值增加
24、，即由非基变量变为基变量，都可使目标函数值增加。所以，只要在目标函数表达式中还存在正系数的非基变量，目标函数值就有增加的可能性。因而此时的解不是最优解。下一页 返回 上一页3.2 线性规划问题的解（4）换基。在目前情况下，将非基变量与基变量对换，都会使目标函数值增加，一般选取正系数比较大的那个非基变量 入基，以便使目标函数值较快的增加，同时需要选择一个基变量出来成为非基变量。由变量的非负条件，有：换基后，成为基变量，而 仍为非基变量，不变。上式为：下一页 返回 上一页3.2 线性规划问题的解 若使上式均成立，取，此时，由此确定 为换出基变量。目前，为非基变量，为基变量，新的约束方程变为：下一页
25、 返回 上一页3.2 线性规划问题的解 此时目标函数，得到一个基本可行解，对应的目标函数值。而从目标函数表达式中可以看到，非基变量 的系数仍为正数，说明函数值还有增加的可能，不一定是最优解，继续使用上述方法对入基、出基变量进行迭代。下一页 返回 上一页3.2 线性规划问题的解（5）继续换基。在这个过程中，作为入基变量，仍为非基变量，取零值。由变量的非负条件，有：同理，只有取 才能使不等式均成立，此时，选取 出基作为非基变量。目前，为非基变量，为基变量，新一轮的约束方程变为：下一页 返回 上一页3.2 线性规划问题的解 此时目标函数，得到下一个基本可行解，对应的目标函数值。非基变量的系数为负，说
26、明 的值再增加的话只能减少Z 的值，所以，此时的解已是最优解，最优值。下一页 返回 上一页3.2 线性规划问题的解 3.单纯形表 上 面 介 绍 的 方 法 中 计 算 与 迭 代 的 过 程 都 比 较 麻 烦，而 且 稍 有不 慎 便 会 出 错。所 以 一 般 采 取 一 种 更 简 洁、更 紧 凑 的 方 法 描述单纯形法，即单纯形表。仍以例3-1 来说明单纯形表的使用方法。（1）将 线 性 规 划 问 题 化 为 标 准 形。引 入 松 弛 变 量 后 将 其 划 为标准形：下一页 返回 上一页3.2 线性规划问题的解 在该标准形中，约束方程的系数矩阵 而 的系数列向量 构成一个三阶
27、单位矩阵，可作为初始可行基，对应的变量 为基变量，为非基变量。令非基变量，得到一个基本可行解。下一页 返回 上一页3.2 线性规划问题的解（2）列出初始单纯形表（表3-2）符号与数字说明：行填入目标函数的系数。列填入基变量，列填入基变量在目标函数中的系数，b 列填入约束方程等号右端的常数。下对应约束方程当前的系数。的计算方法，与 相交处填入目标函数Z的当前值。下一页 返回 上一页3.2 线性规划问题的解 行为检验数行，对应各变量 的检验数，所有 表示解达到最优（若要求实现目标函数的最小化，则所有 表示解达到最优），否则继续进行迭代换基。确定入基变量。此时，确定 入基。列用来确定出基变量，找到入
28、基变量 后，确定出基变量，此时，从而确定 为出基变量。下一页 返回 上一页3.2 线性规划问题的解 所在列与 所在行交汇处的元素称为主元或枢轴元，以 表示，进行矩阵的初等行变换，将 变为1 使之所在列变为单位列向量。于是有表3-3。此时得到的基本可行解，目标函数值。（3）继续迭代。从表中可以看出，于是 换入，换出，得到表3-4。此时表3-4 中的所有的，得到最优解，最优值。返回 上一页3.3 运输问题 运 输 问 题 是 一 类 特 殊 的 线 性 规 划 问 题，它 最 早 是 从 物 资 调 运中 提 出 来 的。但 以 后 有 些 其 他 问 题 的 模 型 也 归 结 为 运 输 问
29、题。虽 然 运 输 问 题 也 是 线 性 规 划 问 题，可 以 用 单 纯 形 法 解 决，但考 虑 到 运 输 问 题 数 学 模 型 的 特 点，人 们 提 出 了 更 简 单 的 求 解方法：表上作业法。3.3.1 运输问题的数学模型 物流中的运输问题可以用以下数学语言描述：下一页 返回3.3 运输问题 设有某种物资需要从m 个 产地运到 n 个销地，其中每个产地 的产量为，每个销地 的销量为。设从产地 到销地 的单位运价为，问该怎样进行物资调运才能使总费用最少?这就是由多个产地供应多个销地的品种物资调运问题。如果该问题的总产量等于总销量，即有，则称该问题为产销平衡的运输问题；否则，
30、称为产销不平衡的运输问题。下一页 返回 上一页3.3 运输问题 3.3.2 产销平衡问题运输 根据上述参量的意义列出产销运价表3-5。表中：的单位为吨、公斤、件等；的单位为吨、公斤、件等；的单位为元/吨等。的单位应一致。表的右下角 表示各产地产量的总和，即总产量或总发量；表示各销地销量的总和。令 表示某物资从发点 到收点 的调拨量（运输量），可以列出产销平衡表3-6。下一页 返回 上一页3.3 运输问题 将表3-3 和表3-4 合在一起，得到一个新表，被称为运输表（或称为产销矩阵表），如表3-7 所示。根据表3-7 求解运输问题的数学模型为：下一页 返回 上一页3.3 运输问题 从上面的运输问
31、题的数学模型中可以看到，它包含 个变量，有n 个约束条件。如果用单纯形法求解，应先在每个约束方程中引进一个人工变量。这样一来，即使是，这样简单的运输问题，变量数就有12 个，显然计算起来非常繁杂；而用表上作业法来求解运输问题则比较简便。下一页 返回 上一页3.3 运输问题 用 表 上 作 业 法 求 解 运 输 问 题 时，同 单 纯 形 法 类 似，首 先 要 求出 一 个 初 始 方 案（即 线 性 规 划 问 题 的 初 始 基 本 可 行 解）。一般 来 讲 这 个 方 案 不 一 定 是 最 优 的，因 此 需 要 给 出 一 个 判 别 准则，并 对 初 始 方 案 进 行 调 整
32、、改 进。每 进 行 一 次 调 整，就 得到 一 个 新 的 方 案（基 本 可 行 解），而 这 个 新 方 案 一 般 比 前 一个 方 案 要 合 理 些，也 就 是 对 应 的 目 标 函 数 Z 值 比 前 一 个 方 案 要小 些。经 过 若 干 次 调 整，我 们 就 得 到 一 个 使 目 标 函 数 达 到 最小 值 的 方 案最 优 方 案（最 优 解），而 这 些 过 程 都 可 在 产销矩阵表（运输表）上进行，故称为表上作业法。下一页 返回 上一页3.3 运输问题 下面以某产品的调运问题为例介绍表上作业法的计算过程。例3-4 某 公 司 有 三 个 加 工 厂 A1，
33、A2，A3生 产 某 产 品，每 日的 产 量 分 别 为7 t，4 t，9 t，该 公 司 把 这 些 产 品 分 别 运 往 四 个销 售 点 B1，B2，B3，B4，各 销 售 点 每 日 销 量 分 别 为3 t，6 t，5 t，6 t。从 各 工 厂 到 各 销 售 点 的 单 位 运 价 如 表3-8 所 示。问 该 公 司 应 如 何 调 运 产 品，在 满 足 各 销 售 点 需 要 量 的 前 提 下，使总运费最少？1.初始基可行解的确定 确 定 初 始 基 可 行 解 的 方 法 很 多，下 面 介 绍 两 种 方 法：最 小 元素法和伏格尔法。下一页 返回 上一页3.3
34、运输问题（1）最小元素法 这 个 方 法 的 基 本 思 想 是 就 近 供 应，即 按 运 费 小 的 尽 可 能 优 先分配的一种确定调运的方法。解：由 于 总 产 量 等 于 总 销 量，所 以 该 问 题 是 一 个 产 销 平 衡 的运 输 问 题。用 表 示 从 到 的 运 量。该 问 题 的 运 输 表 如 表3-9 所示，其数学模型为：下一页 返回 上一页3.3 运输问题 第一步：在表3-9 中找一个运价最小的数，不难看出 为最小，先给 分配并尽可能满足，即将A2生产的产品优先供应B1。由于A2每天生产4 吨，B1每天只需要3 吨，因此可令，在表上 处填上3，并画上圈（表3-1
35、0）。由于B1的需求已满足，不需要继续调运，故、必为零，因此可在、处打上“”。这时A2还剩下4-3=1 吨。下一页 返回 上一页3.3 运输问题 第二步：在没有填数和打“”的地方，再以 的最小值处填 的值，这时可发现 运价最小。让A2尽量供给B3，但A2只能供应1 吨，则可令，在表中 填上1 并画上圈，这时A2生产的产品已经分配完了，所以 必须是0，在 处打“”，且B3还需要 5-4=1 吨。下一页 返回 上一页3.3 运输问题 第三步：在没有填数和打“”的地方找出 的最小值。令，在表中 处填上4 并画上圈，在 处打“”，这时A1还剩下7-4=3。用同样的方法继续可求得，然后在这些地方相应地填
36、上数并画上圈，在没有分配运量的格中都打“”，这样在产销矩阵表上就得到了初始运调方案，如表3-10 所示。该运输问题的初始基本可行解为：下一页 返回 上一页3.3 运输问题 它所对应的目标函数值为：（2）伏格尔法。用 最 小 元 素 法 给 定 初 始 方 案 只 从 局 部 观 点 考 虑 就 近 供 应，有时会造成总体的不合理。下一页 返回 上一页3.3 运输问题 伏 格 尔 法 的 步 骤 是 从 运 价 表 上 分 别 找 出 每 行 与 每 列 的 最 小 的两 个 元 素 之 差，再 从 差 值 最 大 的 行 或 列 中 找 出 最 小 运 价 确 定供 需 关 系 和 供 应 数
37、 量。当 产 地 或 销 地 中 有 一 方 数 量 上 供 应 完毕 或 得 到 满 足 时，划 去 运 价 表 中 对 应 的 行 或 列，再 重 复 上 述步骤。下面通过例3-4 说明伏格尔法。首 先 算 出 每 行 每 列 中 次 小 元 素 与 最 小 元 素 的 差 额，分 别 列 于表 的 右 端 与 下 端，见 表3-10 中 两 最 小 元 素 之 差 中 标 志 的 行和 列。从 表 中 看 到 B2列 的 差 值 最 大，从 该 列 找 出 最 小 元 素 为4，即 A3生 产 的 产 品 首 先 满 足 B2的 需 要，在 表3-11 的（A3，B2）交 叉 格 中 填
38、 上6。在 B2列 与 A1行 和 A2行 交 叉 格 中 画“”。依次类推。下一页 返回 上一页3.3 运输问题 此例的解所对应的（3）最优性检验与方案的调整 最 小 元 素 法 或 伏 格 尔 法 给 出 的 是 一 个 运 输 问 题 的 基 可 行 解，需 通 过 最 优 性 检 验 判 别 该 解 的 目 标 函 数 值 是 否 最 优，当 为 否时，应 该 进 行 调 整 得 到 优 化。最 优 解 的 判 别 是 计 算 空 格（非基 变 量）处 的 检 验 数。运 输 问 题 的 目 标 函 数 是 要 求 实 现 最 小化，故 当 所 有 检 验 数 都 大 于 或 等 于
39、零 时 为 最 优 解。下 面 介 绍闭回路法最优解的检验方法。下一页 返回 上一页3.3 运输问题 运 输 问 题 中 的 闭 回 路 是 指 调 运 方 案 中 由 一 个 空 格 和 若 干 个 有数字格的水平和垂直连线包围成的封闭回路。该 回 路 的 确 定 方 法 是：从 空 格 出 发，沿 水 平 或 铅 直 的 方 向 前进，碰 到 一 个 适 当 的 数 字 格 后 转 弯，再 继 续 前 进 和 转 向，直到 回 到 起 始 空 格 为 止。此 处 所 谓“适 当”的 意 思 是 指 要 使 所走 路 线 能 形 成 一 条 闭 回 路，即 能 回 到 出 发 点。闭 回 路
40、 可 以 是一 个 简 单 矩 形，也 可 以 是 由 水 平 或 铅 直 的 线 组 成 的 复 杂 的 封闭 多 边 形。找 出 闭 回 路 以 后，根 据 闭 回 路 计 算 空 格 的 检 验 数。下面结合表3-12 来说明闭回路法。下一页 返回 上一页3.3 运输问题 首先，在 处为空格，故从 出发，沿水平方向划线，遇到数字格 后转弯，沿铅直方向继续划线，遇到数字格 后再转弯，沿水平方向划线，此时碰到数字格，再转弯，沿铅直方向前进，回到初始空格。于是得到一闭回路，如表3-12 所示，表中左下角数字表示单位运价。找到闭回路后，按下述方针计算任一空格处的检验数，如 处，若从A1处调运1t
41、 货物给B1，为了保持产销平衡，就要依次调整，在 处减少1t，在 处增加1t，在 处减少1t。调整引起的总费用变化是：下一页 返回 上一页3.3 运输问题 由检验数定义知，它正是非基变量 的检验数。按同样的方法，可找出所有空格（非基变量）的检验数，如表3-13 所示.由于其中有检验数，故表3-13 中的解不是最优解。（4）解的改进闭回路调整法 当 表3-13 中 出 现 负 的 检 验 数 时，表 明 不 是 最 优 解，需 要 改 进。若 有 两 个 或 两 个 以 上 的 负 检 验 数 时，一 般 选 其 中 最 小 的 负 检验 数，以 对 应 它 的 空 格 为 调 入 格，即 以
42、它 对 应 的 非 基 变 量 为换 入 变 量。由 表3-14 可 知，外 空 格 应 为 调 入 格。以 此 处 为 出发 点，作 一 闭 回 路，并 在 闭 回 路 上 依 次 标 上+，-，+，-，正 负 号 相 间，如 表3-14 所 示。处 空 格 的 调 入 量 是 选 择闭回路上具有（-）的数字格中最小者，即下一页 返回 上一页3.3 运输问题 按 闭 回 路 上 的 正 负 号，加 上 或 减 去 此 值，得 到 调 整 后 的 方 案，如表3-15 所示。对 表3-15 给 出 的 解，再 用 闭 回 路 法 求 各 空 格 处 的 检 验 数，如表3-15 所 示，表 中
43、 的 所 有 检 验 数，故 表3-15 中 的 解为最优解，且总运费最小为85 元。下一页 返回 上一页3.3 运输问题 3.3.3 产销不平衡问题运输 对于产销不平衡的运输问题，可分为总供给量（总产量）总需求量（总销量）（即）或总需求量（总销量）超过总供给量（总产量）（即）两种情形，关键是按具体情况虚设收点或虚设发点，其收量或发量是两类总量的差数，并按实际意义决定各新增格子上的单位运价，虚设收点或虚设发点的运价为0，这样就把它们转化为产销平衡的运输问题。下一页 返回 上一页3.3 运输问题 例3-5 设 有 某 公 司 有 三 个 加 工 厂 A1、A2、A3生 产 某 产 品，每 日 的
44、 产 量 分 别 为7t、5t、7t，该 公 司 把 这 些 产 品 分 别 运 往四 个 销 售 点 B1、B2、B3、B4，各 销 售 点 每 日 销 量 分 别 为2t、3t、4t、6t。从 各 工 厂 到 各 销 售 点 的 单 位 运 价 如 表3-16 所示。问 该 公 司 应 如 何 调 运 产 品，在 满 足 各 销 售 点 需 要 量 的 前提下，使总运费最少？解：产 地 总 产 量 为19t，销 地 总 销 量 为15t，所 以 这 是 一 个 产大 于 销 的 运 输 问 题。按 上 述 方 法 转 化 为 产 销 平 衡 的 运 输 问 题，其 产 销 平 衡 表 和
45、单 位 运 价 表 分 别 如 表3-17 和 表3-18 所 示。对 表3-17 和 表3-18 可 以 用 表 上 作 业 法 计 算 求 出 最 优 方 案，如表3-19 所示。返回 上一页3.4 整数规划 3.4.1 整数规划简介 用 单 纯 形 法 求 解 线 性 规 划 的 结 果 往 往 得 到 分 数 或 小 数 解。但在 很 多 实 际 问 题 中，全 部 或 部 分 变 量 的 取 值 必 须 是 整 数，如人 或 机 器 设 备 等 不 可 分 割。此 外 还 有 一 些 问 题，如 要 不 要 在某 地 建 设 工 厂，可 选 用 一 个 逻 辑 变 量，令 表 示 在
46、 该 地建 厂，表 示 不 在 该 地 建 厂，逻 辑 变 量 也 是 只 允 许 取 整 数值 的 一 类 变 量。在 一 个 线 性 规 划 中 要 求 全 部 变 量 取 整 数 值 的，称 纯 整 数 线 性 规 划 或 简 称 整 数 规 划；只 要 求 一 部 分 变 量 取 整数值的，称为混合整数（线性）规划。下一页 返回3.4 整数规划 有 人 认 为，对 整 数 规 划 的 求 解 可 以 先 不 考 虑 对 变 量 的 整 数 约束，作 为 一 般 线 性 规 划 问 题 来 求 解，当 解 为 非 整 数 时 可 用 四舍 五 入 或 凑 整 方 法 寻 找 最 优 解。
47、当 然 在 变 量 取 值 很 大 时，用上 述 方 法 得 到 的 解 与 最 优 解 差 别 不 大。但 当 变 量 取 值 较 小 时，得 到 的 解 就 可 能 与 实 际 整 数 最 优 解 差 别 很 大。再 者 当 问 题 规划 较 大 时，用 凑 整 办 法 来 算 工 作 量 很 大。如 某 线 性 规 划 问 题最优是为（4.6，5.5），用凑整办法时需比较与 的 上 述 数 值 最 接 近 的 四 种 组 合，即（4，5）、（4，6）、（5，5）、（5，6）。如 果 问 题 中 有10 个 整 数 变 量，就 得比 较 个 整 数 解 组 合，而 且 最 优 解 还 不
48、一 定 在 这 些 组合中。下一页 返回 上一页3.4 整数规划 整 数 规 划 的 模 型 对 研 究 管 理 问 题 有 重 要 意 义。很 多 管 理 问 题无 法 归 结 为 线 性 规 划 的 数 学 模 型，但 却 可 以 通 过 设 置 逻 辑 变量建立起整数规划的数学模型。3.4.2 整数规划问题的解法 1.分枝定界法 根 据 某 种 策 略 将 原 问 题 之 松 弛 问 题 的 可 行 域 分 解 为 越 来 越 小的 子 域，并 检 查 每 个 子 域 内 整 数 解 的 情 况，直 到 找 到 最 优 的整 数 解 或 证 明 整 数 解 不 存 在。这 一 思 路 主
49、 要 由 以 下 三 方 面 的事实建立起来。下一页 返回 上一页3.4 整数规划（1）如 果 求 解 一 个 整 数 规 划 的 松 弛 问 题 时 得 到 的 是 一 个 整 数解，则 这 个 解 也 一 定 就 是 整 数 规 划 的 最 优 解。然 而 在 求 解 实际问题时的这种巧合的概率很小。（2）如 果 解 松 弛 问 题 时 得 到 的 不 是 一 个 整 数 解，则 最 优 整 数解 一 定 不 会 更 优 于 所 得 到 的 松 弛 问 题 的 目 标 函 数 值。因 此，线 性 规 划 松 弛 问 题 的 解 值 必 是 整 数 规 划 目 标 函 数 的 一 个 下 界
50、。它对于最大化问题为上界，对于最小化问题为下界。（3）如 果 在 求 解 的 过 程 中 已 经 得 到 了 一 个 整 数 解，则 最 优 整数 解 一 定 不 会 劣 于 该 整 数 解。因 此，该 整 数 解 可 构 成 最 优 解的 另 一 个 界，对 于 最 大 化 问 题 为 下 界，对 于 最 小 化 问 题 为 上界。下一页 返回 上一页3.4 整数规划 如果用 表示松弛问题的解值，用 表示目前已经找到的整数解，表示最优整数解，表示下界，表示上界，则最优整数解一定满足以下关系：对于最大化问题：，对于最小化问题：，显 然，如 果 能 找 到 一 种 方 法，或 者 降 低 上 界