线性规划与计算复杂性简介

1 线 性 规 划 与 计 算 复 杂 性 简 介浙江大学数学建模实践基地 上 一 页 下 一 页 2 8.1 线 性 规 划 问 题一 、 线 性 规 划 的 实 例 与 定 义二 、 线 性 规 划 的 标 准 形 式三 、 线 性 规 划 的 图 解 法四 、 基 本 可 行 解 与 极 点 的 等 价 定 理五 、 求 解 线 性 规 划 的 单 纯 形 法六 、 初 始 可 行 解 的 求 法 两 段 单 纯 形 法 8.2 运 输 问 题一 、 运 输 问 题 的 数 学 模 型三 、 最 优 性 判 别二 、 初 始 可 行 解 的 选 取 8.3 指 派 问 题 一 、 指 派 问 题 的 数 学 模 型二 、 求 解 指 派 问 题 的 匈 牙 利 算 法 8.4 计 算 复 杂 性 问 题 的 提 出一 、 P类 与 NP类 ， NP完 全 性二 、 有 关 离 散 问 题 模 型 及 其 算 法 的 几 点 附 加 说 明 上 一 页 下 一 页 3 8.1 线 性 规 划 问 题在 人 们 的 生 产 实 践 中 ， 经 常 会 遇 到 如 何 利 用 现 有 资 源来 安 排 生 产 以 取 得 最 大 经 济 效 益 的 问 题 ， 此 类 问 题 构成 了 运 筹 学 的 一 个 重 要 分 支 数 学 规 划 ， 而 线 性 规划 （ Linear Programming, 简 记 LP） 则 是 数 学 规 划 的一 个 重 要 部 分 。 自 从 1947年 GBDantzig提 出 求 解 线 性规 划 的 单 纯 形 方 法 以 来 ， 线 性 规 划 在 理 论 上 日 趋 成熟 ， 在 应 用 上 日 趋 广 泛 ， 已 成 为 现 代 管 理 中 经 常 采用 的 基 本 方 法 之 一 。 上 一 页 下 一 页 4 一 .线 性 规 划 的 实 例 与 定 义例 8.1 某 机 床 厂 生 产 甲 、 乙 两 种 机 床 ， 每 台 销 售 后 的 利润 分 别 为 4000元 与 3000元 。 生 产 甲 机 床 需 用 A、 B机 器 加 工 ，加 工 时 间 分 别 为 每 台 2小 时 和 1小 时 ； 生 产 乙 机 床 需 用 A、B、 C三 种 机 器 加 工 ， 加 工 时 间 为 每 台 各 一 小 时 。 若 每 天 可用 于 加 工 的 机 器 时 数 分 别 为 A机 器 10小 时 、 B机 器 8小 时 和 C机 器 7小 时 ， 问 该 厂 应 生 产 甲 、 乙 机 床 各 多 少 台 ， 才 能 使总 利 润 最 大 ？ 上 一 页 下 一 页 5 例 1的 数 学 模 型 ： 设 该 厂 生 产 x1台 甲 机 床 和 x2台 乙 机 床 时 总利 润 最 大 ， 则 x1 、 x2应 满 足 max 4x1 + 3x2 s.t 2x1 + x2 10 x1 + x2 8 (8.1) x2 7 x1 , x2 0（ 8.1） 式 中 4x1 + 3x2表 示 生 产 x1台 甲 机 床 和 x2台 乙 机 床 的总 利 润 ， 被 称 为 问 题 的 目 标 函 数 ， 当 希 望 使 目 标 函 数 最 大 时 ，记 为 max； 反 之 ， 当 希 望 使 目 标 函 数 最 小 时 ， 记 为 min。 （ 8.1）中 的 几 个 不 等 式 是 问 题 的 约 束 条 件 ， 记 为 S.t（ 即 Subject to） 。 由 于 （ 8.1） 式 中 的 目 标 函 数 及 约 束 条 件 均 为线 性 函 数 ， 故 被 称 为 线 性 规 划 问 题 。 总 之 ， 线 性 规 划问 题 是 在 一 组 线 性 约 束 条 件 的 限 止 下 ， 求 一 线 性 目 标函 数 最 大 或 最 小 的 问 题 。 上 一 页 下 一 页 6 二 、 线 性 规 划 的 标 准 形 式例 8.2 min S.t i=1, ,m x j 0,j=1, ,n jnj jxc 1 inj jij bxa 1线 性 规 划 的 目 标 函 数 可 以 是 求 最 大 值 ， 也 可 以 是 求 最 小 值 ， 约 束 条 件可 以 是 不 等 式 也 可 以 是 等 式 ， 变 量 可 以 有 非 负 要 求 也 可 以 没 有 非 负 要求 （ 称 这 样 的 变 量 为 自 由 变 量 ） 。 为 了 避 免 这 种 由 于 形 式 多 样 性 而 带来 的 不 便 ， 规 定 线 性 规 划 的 标 准 形 式 为利 用 矩 阵 与 向 量 记 为min z = CT x S.t Ax = bx 0 （ 8.3）其 中 C 和 x 为 n 维 列 向 量 ， b为 m 维 列向 量 ， b 0， A为 m n矩 阵 ,mn且rank(A)=m。或 更 简 洁 地 上 一 页 下 一 页 7 如 果 根 据 实 际 问 题 建 立 起 来 的 线 性 规 划 问 题 并 非 标 准 形式 ， 可 以 将 它 如 下 化 为 标 准 形 式 ：（ 1） 若 目 标 函 数 为 max z =CT x， 可 将 它 化 为 min z = CT x（ 2） 若 第 i个 约 束 为 ai1x1+ +ainxn bi， 可 增 加 一 个 松 驰 变量 yi， 将 不 等 式 化 为 ai1x1+ +ainxn+yi = bi， 且 yi 0。若 第 i个 约 束 为 ai1x1+ +ainxn bi， 可 引 入 剩 余 量 yi， 将不 等 式 化 为 ai1x1+ +ainxn yi = bi， 且 yi 0。（ 3） 若 xi为 自 变 量 ， 则 可 令 ,其 中 、 0 iii xxx ix ix例 如 例 18.1并 非 标 准 形 式 ， 其 标 准 形 式 为min 4x1 3x2s.t 2x1 + x2 + x3 = 10 x1 + x2 + x4 = 8x2 + x5 = 7x1 , x2 , x3 , x4, x5 0 上 一 页 下 一 页 8图 8.1 对 于 例 8.1， 显 然 等 位 线 越 趋于 右 上 方 ， 其 上 的 点 具 有 越大 的 目 标 函 数 值 。 不 难 看 出 ，本 例 的 最 优 解 为 x*=(2,6)T ，最 优 目 标 值 z*=26 。 三 、 线 性 规 划 的 图 解 法为 了 了 解 线 性 规 划 问 题 的 特 征 并 导 出 求 解 它 的 单 纯 形 法 ， 我们 先 应 用 图 解 法 来 求 解 例 8.1。 满 足 线 性 规 划 所 有 约 束 条 件的 点 称 为 问 题 的 可 行 点 （ 或 可 行 解 ） ， 所 有 可 行 点 构 成 的 集合 称 为 问 题 的 可 行 域 ， 记 为 R。 对 于 每 一 固 定 的 值 z， 使 目 标函 数 值 等 于 z的 点 构 成 的 直 线 称 为 目 标 函 数 等 位 线 ， 当 z变 动时 ， 我 们 得 到 一 族 平 行 直 线 （ 图 8.1） 。 上 一 页 下 一 页 9上 述 论 断 可 以 推 广 到 一 般 的 线 性 规 划 问 题 ， 区 别 只 在 于 空 间的 维 数 。 在 一 般 的 n维 空 间 中 ， 满 足 一 线 性 等 式 aix=bi的 点 集被 称 为 一 个 超 平 面 ， 而 满 足 一 线 性 不 等 式 aix bi （ 或aix bi ） 的 点 集 被 称 为 一 个 半 空 间 （ 其 中 ai为 一 n维 行 向 量 ，bi为 一 实 数 ） 。 若 干 个 半 空 间 的 交 集 被 称 为 多 胞 形 ， 有 界 的多 胞 形 又 被 称 为 多 面 体 。 易 见 ， 线 性 规 划 的 可 行 域 R必 为 多 胞形 （ 为 统 一 起 见 ， 空 集 也 被 视 为 多 胞 形 ） 。 （ 1） 可 行 域 R可 能 会 出 现 多 种 情 况 。 R可 能 是 空 集 也 可 能 是 非空 集 合 ， 当 R非 空 时 ， 它 必 定 是 若 干 个 半 平 面 的 交 集 （ 除 非遇 到 空 间 维 数 的 退 化 ） 。 R既 可 能 是 有 界 区 域 ， 也 可 能 是 无 界区 域 。 （ 2） 在 R非 空 时 ， 线 性 规 划 既 可 以 存 在 有 限 最 优 解 ，也 可 以 不 存 在 有 限 最 优 解 （ 其 目 标 函 数 值 无 界 ） 。 （ 3） 若 线性 规 划 存 在 有 限 最 优 解 ， 则 必 可 找 到 具 有 最 优 目 标 函 数 值 的可 行 域 R的 “ 顶 点 ” 。从 上 面 的 图 解 过 程 可 以 看 出 并 不 难 证 明 以 下 断 言 ： 上 一 页 下 一 页 10 在 一 般 n维 空 间 中 ， 要 直 接 得 出 多 胞 形 “ 顶 点 ” 概 念 还 有 一 些困 难 。 在 图 8.1中 顶 点 可 以 看 成 为 边 界 直 线 的 交 点 ， 但 这 一几 何 概 念 的 推 广 在 一 般 n维 空 间 中 的 几 何 意 义 并 不 十 分 直 观 。定 义 8.1 称 n 维 空 间 中 的 区 域 R为 一 凸 集 ， 若 x1 , x2 R及 (0, 1)， 有 x1 +（ 1 ） x2 R。定 义 8.2 设 R为 n维 空 间 中 的 一 个 凸 集 ， R中 的 点 x被 称 为 R的一 个 极 点 ， 若 不 存 在 x1 、 x2 R及 (0, 1)， 使 得x = x1 +（ 1 ） x2 。定 义 8.1说 明 凸 集 中 任 意 两 点 的 连 线 必 在 此 凸 集 中 ； 而 定 义8.2说 明 ， 若 x是 凸 集 R的 一 个 极 点 ， 则 x不 能 位 于 R中 任 意 两点 的 连 线 上 。 不 难 证 明 ， 多 胞 形 必 为 凸 集 。 同 样 也 不 难 证明 ， 图 8.1中 R的 顶 点 均 为 R的 极 点 （ R 也 没 有 其 他 的 极 点 ）为 此 ， 我 们 将 采用 另 一 途 径 来 定义 它 。 上 一 页 下 一 页 11 三 、 基 本 解 与 基 本 可 行 解给 定 一 个 标 准 形 式 的 线 性 规 划 问 题 （ 8.3） ， 其 中 A=(aij)mxn ，m 0 ， 则 称 x=（ B-1b ， 0） 为 （ 8.3） 的 一 个 非 退 化 的 基本 可 行 解 ， 并 称 B为 非 退 化 的 可 行 基 。 由 于 基 矩 阵 最 多 只 有 种 不 同 的 取 法 ， 即 使 A的 任 意 m解 均 线 性 无 关 ， 且 对 应 的 基 本 解均 可 行 ， （ 8.3） 最 多 也 只 能 有 个 不 同 的 基 本 可 行 解 。mnC 上 一 页 下 一 页 12 四 、 基 本 可 行 解 与 极 点 的 等 价 定 理在 线 性 规 划 的 求 解 中 ， 下 列 定 理 起 了 关 键 性 的 作 用 。 在 这 里 ，我 们 不 加 证 明 地 引 入 这 些 定 理 。 。 0 x bAx定 理 8.1 （ 基 本 可 行 解 与 极 点 的 等 价 定 理 ）设 A为 一 个 秩 为 m的 m n矩 阵 （ nm） b为 m维 列 向 量 ，记 R为 （ 8.3） 的 可 行 域 。 则 x为 R的 极 点 的 充 分 必 要 条 件 为 x 是 的 基 本 可 行 解 。定 理 8.1既 提 供 了 求 可 行 域 R的 极 点 的 代 数 方 法 ， 又 指明 了 线 性 规 划 可 行 域 R的 极 点 至 多 只 有 有 限 个 .对 定 理 证 明 有 兴 趣 的读 者 可 以 参 阅 D.G.鲁 恩 伯 杰 著 的 “ 线 性与 非 线 性 规 划 引 论 ”一 书 第 二 章 上 一 页 下 一 页 13 （ 线 性 规 划 基 本 定 理 ） 线 性 规 划 （ 8.3） 具 有 以 下 性 质 ：（ 1） 若 可 行 域 R ， 则 必 存 在 一 个 基 本 可 行 解 。（ 2） 若 问 题 存 在 一 个 最 优 解 ， 则 必 存 在 一 个 最 优 的 基 本可 行 解 。定 理 8.2并 非 说 最 优 解 只 能 在 基 本 可 行 解 （ 极 点 ） 上 达 到 ，而 是 说 只 要 （ 8.3） 有 有 限 最 优 解 ， 就 必 定 可 在 基 本 可 行解 （ 极 点 ） 中 找 到 。 定 理 8.2从 模 型 本 身 讲 ， 线 性 规 划 显 然 应 属 连 续 模 型 。 但 定 理 2表 明 ，如 果 线 性 规 划 有 有 限 最 优 解 ， 我 们 只 需 比 较 各 基 本 可 行 解 上的 目 标 函 数 值 即 可 找 到 一 个 最 优 解 ， 而 问 题 的 基 本 可 行 解 至多 只 有 有 限 个 ， 从 而 问 题 化 为 一 个 从 有 限 多 个 点 选 取 一 个 最优 点 的 问 题 。 正 是 基 于 这 样 一 种 思 路 ， Dantzig提 出 了 求 解线 性 规 划 的 单 纯 形 法 。 也 正 因 为 如 此 ， 我 们 把 线 性 规 划 列 入了 离 散 模 型 ， 因 为 求 解 它 的 单 纯 形 法 更 具 有 离 散 模 型 问 题 的算 法 特 征 。 上 一 页 下 一 页 14 五 、 求 解 线 性 规 划 的 单 纯 形 法（ 步 1） 取 一 初 始 可 行 基 B（ 一 般 取 法 见 后 面 的 两 段 单 纯 形法 ） ， 再 用 高 斯 约 当 消 去 法 求 出 初 始 基 本 可 行 解 x0， 编制 成 所 谓 的 初 始 单 纯 形 表 ；（ 步 2） 判 断 x0是 否 最 优 解 ， 如 果 x0是 最 优 解 ， 输 出 x0， 停 ，否 则 到 步 3；（ 步 3） 按 一 改 进 准 则 ， 将 一 个 非 基 变 量 转 变 为 基 变 量 ，而 将 一 个 基 变 量 转 变 为 非 基 变 量 。 这 相 当 于 交 换 B与 N的 一个 列 ， 同 样 可 用 高 斯 约 当 消 去 法 ， 运 算 可 以 通 过 单 纯 形表 上 的 “ 转 轴 运 算 ” 实 现 。Dantzig单 纯 形 法 的 基 本 步 骤 如 下 ： 上 一 页 下 一 页 15 设 B为 一 非 退 化 的 可 行 基 ， x=（ B-1b， 0） 为 其 对 应 的 基本 可 行 解 。 现 在 ， 我 们 先 来 讨 论 如 何 判 别 x0是 否 为 最 优解 。 为 此 ， 考 察 任 一 可 行 解 。 由 Ax=b可 得 （ 8.5）代 入 目 标 函 数 ， 得 到 NBxxxNB NxBbBx 11 NTBTNTBNTNBTB xNBCCbBCxCxCZ )( 11 NTBTNT xNBCCxC )( 10 NBCCr TBTNN 1NjjN rr )( Nj定理8.3 （最优性判别定理） 令 。（1）若rN0，则x0必为（8.3）的一个最优解。（2）记 。若 ，rj0 ， 根 据 （ 7.15） 式 知 ， 当 且 充 分 小 时 ， 仍 有 xB0 。 此 时 对 应 的 x仍 为 可 行 解 ， 但 由 （ 8.6） ， 其 目 标 函 数 值 ：故 x 0必 非 最 优 解 。Njrj ,00 Rx0 xCxCz TT 011 00 xCbBCxrbBCxCz TTBjjTBT 定 理 8.3不 仅 给 出 了 判 别 一 个 基 本 可 行 解 是 否 为 最 优 解 的 准 则 ， 而 且 在 x0非 最 优 解 时 还 指 出 了 一 条 改 进 它 的 途 径 。 由 于 rN在 判 别 现 行 基 本 可 行 解 是否 为 最 优 解 时 起 了 重 要 作 用 ， 所 以 rN被 称 为 x0处 的 检 验 向 量 ， 而 rj (j N)被 称 为 非 基 变 量 xj的 检 验 数 。 上 一 页 下 一 页 17 有 趣 的 是 上 述 过 程 完 全 可 以 在 以 下 的 单 纯 形 表 上 进 行 。 先 将CT、 A、 b及 数 0写 在 一 个 矩 阵 中 ， 在 表 上 用 高 斯 约 当 消 去 法解 方 程 组 Ax=b 高 斯 -约 当 消 去 法 （ 第 一 行 不 变 ） bACT 0 bBNBI CC TNTB 11 0利 用 单 位 矩 阵 I消 第 一 行 的为 零 向 量 ， 则 被 消 成 ， 而 0则 被 消成 。 将 消 去 后的 行 向 量 写 到 最 后 一 行 ， 删 去原 来 的 第 一 行 ， 得 到 一 张 被 称为 单 纯 表 的 表 格 ： TBCTNCNTBTN rNBCC 1 01 ZbBCTB xB xNI B 1N B 1b0 rN Z0(8.7)表 格 （ 8.7） 以 极 为 简 洁 明 了 的 方 式 表 达 了 我 们 需 要 的 全部 信 息 。 从 其 前 m行 可 看 出 哪 些 变 量 是 基 变 量 并 可 直 接 读出 对 应 的 基 本 可 行 解 x0=（ B 1b， 0） 。 其 最 后 一 行 又 给 出了 非 基 变 量 的 检 验 数 及 x0处 目 标 函 数 值 的 相 反 数 。 上 一 页 下 一 页 18 例 8.1的 标 准 形 式 为 （ 8.4） ， 容 易 看 出 它 的 一 个 初 始 基B=I（ 以 x3、 x4、 x5为 基 变 量 ） ， 且 CB已 经 为 零 ， 故 我 们 已有 了 一 张 初 始 的 单 纯 形 表 表 8.1： 表 8.1 x1 x2 x3 x4 x5基变量 x3 1 1 0 0 10 x4 1 1 0 1 0 8x 5 0 1 0 0 1 7rj 4 3 0 0 0 0 x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=( 4， 3)现 在 ， 我 们 以 例 8.1为 例 ， 来 看 一 下 单纯 形 法 是 如 何 工 作的 。 上 一 页 下 一 页 19 由 于 存 在 着 负 的 检 验 数 且 x0非 退 化 ， x0非 最 优 解 。 r1， r2均 为 负 ， x1， x2增 大 （ 进 基 ） 均 能 改 进 目 标 函 数 值 。 例 如 ， 取 x1进 基 仍 令 x2=0（ x2仍 为 非 基 变 量 ） ， 此 时 由 （ 8.5） 式 及（ 8.6） 式 有 且 z = CTx = 4x1x1增 加 得 越 多 ， 目 标 函 数 值 下 降 得 越 多 ， 但 当 x1 =5时 x3=0， x1再 增 大 则x3将 变 负 。 为 保 证 可 行 性 ， x1最 多 只 能 增 加 到 5， 此 时 x3成 为 非 基 变 量（ 退 基 ） 。 78 2105 14 13x xx xx不 难 看 出 ， 上 述 改 进 可 以 在 单 纯 形 表 上 进 行 。 对 于 一 般 形 式 的 单 纯 形 表 ，记 最 后 一 列 的 前 m个 分 量 为 （ y i0） ， i=1,m。 若 取 进 基 ， 记 j0列 前 m个 分 量 为 （ ） ， i=1,m。 易 见 ， 阻 碍 增 大 的 只 可 能 在 0的 那 些 约 束 中 。 若 0对 一 切 i=1,m成 立 （ j0列 前 m个 分 量中 不 存 在 正 值 ） ， 则 可 任 意 增 大 ， 得 到 的 均 为 可 行 解 ， 但 其 目 标 值随 之 可 任 意 减 小 ， 故 问 题 无 有 限 最 优 解 。 0jx0ijy 0jx0ijy 0ijy0jx 上 一 页 下 一 页 20 否 则 ， 令则 随 着 的 增 大 ， 将 最 先 降 为 零 （ 退 出 基 变 量 ） ， 故 只 需 以 为 主元 作 一 次 消 去 法 运 算 （ 称 此 运 算 为 一 次 转 轴 运 算 ） ， 即 可 得 到 改 进 后 的 基本 可 行 解 处 的 单 纯 形 表 。 在 本 例 中 ， 因 取 x1进 基 （ j=1） 而 ， 以 y11为 主 元 作 第 一 次 转 轴 ， 得 到 000000 0min0 ijiijjii yyyyy0jx 0ix 00 jiy51110 yy82120 yyx 1=(5,0,0,3,7)T z1= 20 rN=(r2,r3)=( 1， 2)20002 10rj 710010 x5 301 -0 x4 5001x3基变量 x5x4x3x2x1 212121 21表 8.2 上 一 页 下 一 页 21 表 8.2中 r20） 最 小 选 定 以 下 y22 = 为 主 元 转 轴 ， 得 到 下 一 基 本 可 行 解 x2处 的 单 纯 形 表 表 8.3。21表 8.3 x1 x2 x3 x4 x5基变量 x3 1 0 1 0 2x4 0 1 0 6x5 0 0 1 1r j 0 0 0 26x2=(2,6,0,0,1)Tz2= 26rN=(r3,r4)=(1， 2)对 于 x2， rN= (1， 2)为 非 负 向 量 ， 故 x2为 最 优 解 ， 最 优 目 标 值 为 26。于 是 ， 原 问 题 例 1的 最 优 解 x*=(2,6)T， 最 优 目 标 值 为 26。 上 一 页 下 一 页 22 六 、 初 始 可 行 解 的 求 法 两 段 单 纯 形 法 阶 段 2 若 辅 助 规 划 的 最 优 目 标 值 不 等 于 零 ， 原 规 划 无 可 行解 。 否 则 我 们 已 求 得 原 问 题 的 一 个 基 本 可 行 解 x0。 删 去 阶 段 1最 终 单 纯 表 中 最 后 一 行 及 对 应 人 工 变 量 的 列 ， 作 出 原 规 划 对 应x0的 初 始 单 纯 形 表 。 此 时 又 可 利 用 上 述 单 纯 形 法 求 解 原 规 划 了 。阶 段 1 对 第 i个 约 束 引 入 人 工 变 量 yi， yi 0， 将 其 改 写 为ai1x1+ ainxn+yi=bi， i=1,m。 作 辅 助 线 性 规 划 LP（ 1） ，其 目 标 函 数 为 。容 易 看 出 ， 原 规 划 有 可 行 解 （ 从 而 有 基 本 可 行 解 ） 的 充 分 必 要条 件 为 辅 助 规 划 的 最 优 目 标 值 为 零 。 由 于 辅 助 规 划 具 有 明 显 的初 始 可 行 基 （ 人 工 变 量 对 应 的 列 构 成 单 位 矩 阵 I） ， 可 利 用 上述 单 纯 形 法 逐 次 改 进 而 求 出 辅 助 规 划 最 优 解 。mi iy1 上 一 页 下 一 页 23 例 8.2 min 4x1+ x2+ x3 S.t 2x1+ x2+2x3 = 4 3x1+ 3x2+x3 = 3 x1、 x2、 x30?解 ： 因 为 初 始 可 行 基 不 能 直 接 看 出 ， 我 们 采 用 两 段 单 纯 形 法求 解 。阶 段 1 先 求 解 辅 助 规 划 ：min x 4+ x5S.t 2x1+ x2+2x3 + x4= 4 3x1+ 3x2+x3+ x5 = 3 x1， ， x30 上 一 页 下 一 页 24 表 8.4 x1 x2 x3 x4 x5基变量 x4 2 1 2 1 0 4x5 3 1 0 1 3rj 5 4 3 0 0 7选 取 x1进 基 ， 以 y21=3为 主 元 转 轴 （ x5出 基 ） ， 得 表 8.5。表 8.5 x 1 x2 x3 x4 x5基变量 x4 0 1 4/3 1 2/3 2x1 1 1 1/3 0 1/3 1rj 0 1 4/3 0 5/3 2 上 一 页 下 一 页 25 因 r3 0 。 当 B 1b也 存 在 零 分 量 时 ，我 们 遇 到 了 一 个 退 化 的 基 本 可 行 解 。 此 时 rN存 在 负 分 量 不 一 定 说 明 现 行 基本 可 行 解 不 是 最 优 解 ， 单 纯 形 法 也 可 能 会 遇 到 循 环 迭 代 。 存 在 着 几 种 避 免循 环 的 技 巧 ， 例 如 ， 只 要 每 次 在 rj0的 非 基 变 量 中 选 取 具 有 最 小 足 标 者 进基 即 可 。 在 求 解 线 性 规 划 时 ， 首 先 应 将 问 题 化 为 标 准 形 式 。 若 从 标 准 形 式 已 可 看 出一 个 初 始 基 ， 则 可 直 接 用 单 纯 法 求 解 ： （ 1） 写 出 初 始 单 纯 形 表 ； （ 2） 若检 验 向 量 rN 0， 则 已 得 以 最 优 解 ； （ 3） 任 选 一 负 分 量 rj。 以 进 基 ，考 察 所 在 列 。 若 对 i=1,m均 有 0， 则 问 题 无 有 限 最 优 解 ， 停 ；否 则 令 ，以 为 主 元 转 轴 ， 返 回 （ 2） ， 直 至 rN 0求 出 最 优 解 。 若 从 标 准 形 式 无法 看 出 初 始 可 行 基 ， 则 需 采 用 两 段 单 纯 形 法 求 解 。 0jx0jx 0ijy 000000 0min0 ijiijjii yyyyy00 jiy 变 量 同 时 具 有 上 、 下 界 限 止 的 线 性 规 划 问 题也 可 化 为 标 准 形 式 求 解 ， 有 兴 趣 的 读 者 可 以参 阅 D.G.鲁 恩 伯 杰 的 “ 线 性 与 非 线 性 规 划 引论 ” 一 书 的 第 三 章 。 上 一 页 下 一 页 28 8.2 运 输 问 题一 .运 输 问 题 的 数 学 模 型 例 8.3 某 商 品 有 m个 产 地 、 n个 销 地 ， 各 产 地 的 产 量 分 别 为a1,am各 销 地 的 需 求 量 分 别 为 b1,bn。 若 该 商 品 由 i产 地运 到 j销 地 的 单 位 运 价 为 Cij， 问 应 该 如 何 调 运 才 能 使 总 运 费最 省 ? 解 ： 引 入 变 量 xij， 其 取 值 为 由 i产 地 运 往 j销 地 的 该 商 品 数 量 。 例 8.3的数 学 模 型 为min S.t ， i=1,m (8.9) ， j=1,n xij 0 nj ijijmi xC11inj ij ax 1 jmi ij bx 1（ 8.9） 显 然 是 一 个 线 性 规 划 问 题 ， 当 然 可 以 用 单 纯 形 方 法 求 解 ， 但 由 于其 约 束 条 件 的 系 数 矩 阵 相 当 特 殊 ， 求 解 它 可 以 采 用 其 他 简 便 办 法 。 本 节将 介 绍 由 康 脱 洛 维 奇 和 希 奇 柯 克 两 人 独 立 地 提 出 的 表 上 作 业 法 （ 简 称康 希 表 上 作 业 法 ） ， 其 实 质 仍 然 是 先 作 出 一 个 初 始 基 本 可 行 解 ， 然 后用 最 优 性 准 则 检 验 是 否 为 最 优 并 逐 次 改 进 直 至 最 优 性 准 则 成 立 。 上 一 页 下 一 页 29 二 、 初 始 可 行 解 的 选 取不 难 发 现 ， （ 8.9） 的 约 束 条 件 中 存 在 着 多 余 方 程 。 容 易 证明 ， 只 要 从 中 除 去 一 个 约 束 ， 例 如 最 后 一 个 方 程 ， 约 束 条件 就 彼 此 独 立 了 。 因 而 ， （ 8.9） 是 一 个 具 有 m n个 变 量 的线 性 规 划 ， 其 每 一 基 本 可 行 解 应 含 有 m+n 1个 基 变 量 。记 （ 8.9） 约 束 条 件 中 前 m+n 1个 方 程 的 系 数 矩 阵 为 A， A为（ m+n 1） mn矩 阵 ， 它 的 每 一 列 最 多 只 有 两 个 非 零 元 素且 非 零 元 素 均 为 1。 利 用 线 性 代 数 知 识 能 够 判 定 A中 怎 样 的m+n 1个 列 可 以 取 为 基 （ 即 怎 样 的 m+n 1个 变 量 可 以 取 为基 变 量 ） ， 为 了 判 明 哪 些 变 量 对 应 的 列 是 线 性 无 关 的 ， 先引 入 下 面 的 定 义 ： 上 一 页 下 一 页 30 定 义 8.3 （ 闭 回 路 ） xij （ i=1,m; j=1,n） 的 一 个 子 集 被 称 为一 个 闭 回 路 ， 若 它 可 以 被 排 成其 中 互 异 ， 也 互 异 。 211132222111 , jijijijijiji xxxxxx tii ,.,1 tjj ,.,1用 下 面 的 方 法 可 以 较 方 便 直 观 地 看 出 xij 的 一 个 子 集 是 否 为 一 闭 回 路 ：作 一 个 m行 n列 的 表 格 ， 令 格 （ i,j） 对 应 xij 。 将 子 集 中 的 变 量 填 于 相 应格 中 ， 并 将 相 邻 变 量 （ 或 同 行 或 同 列 ） 用 边 相 连 ， 则 此 子 集 为 闭 回 路 当且 仅 当 其 点 按 上 述 连 法 作 出 的 折 线 可 构 成 一 个 闭 回 路 。例 如 ， 当 m=3,n=4时 ， X1=x12,x13,x23,x24,x34,x32和X 2=x12,x14,x24,x21,x31,x32 均 为 闭 回 路 ， 见 表 8.9和 表 8.10。表 (8.9) 表 (8.10) 上 一 页 下 一 页 31 定 理 8.4 X为 xij （ i=1,， m； j=1， ， n） 的 一 个 子 集 ， X中 的 变量 对 应 的 A中 的 列 向 量 集 线 性 无 关 的 充 要 条 件 为 X中 不 包 含 闭 回 路 。定 量 8.4不 难 用 线 性 代 数 知 识 证 明 ， 详 细 证 明 从 略 。 根 据 定 理 8.4， 要 选取 （ 8.9） 的 一 组 基 变 量 并 进 而 得 到 一 个 基 本 可 行 解 ， 只 需 选 取 xij的一 个 子 集 X， X =m+n-1且 X中 不 含 闭 回 路 ， 其 中 X 表 示 X中 的 变 量 个数 。 我 们 从 下 面 的 例 子 来 说 明 如 何 选 取 一 个 基 本 可 行 解 。 例 8.3 给 定 运 输 问 题 如 表 8.11所 示 ， 表 中 左 上 角 的 数 字 为 单 位 运 价Cij 。 易 见 ， 本 例 是 产 销 平 衡 的 即 。 ji ba表 8.11 6432销 量 72 31 48 7 3 59 25 3 310 2 34 13 11 2 21 产 量4321 ji ba销 地产 地 上 一 页 下 一 页 32 现 采 用 “ 最 小 元 素 法 ” 求 一 基 本 可 行 解 。 单 位 运 价 最 小 的 为 C33=1， 令x33=mina3,b3=4,并 令 x13= x23=0（ 销 地 3已 满 足 ） ， 相 应 格 打 “ ”。 产地 3已 运 出 4单 位 ， 将 产 量 改 为 剩 余 产 量 3。 剩 余 表 中 单 位 运 价 最 小 的 为C11=2（ 或 C34=2） ， 令 x11= min a1,b1=2,并 令 x21= x31=0， 相 应 格 打“ ”， a1改 为 剩 余 产 量 1， ， 直 至 全 部 产 品 分 配 完 毕 。 注 意 到 除 最 后一 次 分 配 外 每 次 只 能 对 一 行 或 一 列 找 “ ”， 表 示 某 销 地 已 满 足 或 某 产 地产 品 已 分 配 完 （ 当 两 者 同 时 成 立 时 只 能 打 “ ”行 或 列 之 一 ， 将 剩 余 需 求量 或 产 量 记 为 0， 此 时 基 本 可 行 基 是 退 化 的 ） 。 容 易 证 明 ： 这 样 分 配 共 选出 了 m+n-1个 变 量 ， 且 这 些 变 量 的 集 合 不 含 闭 回 路 ， 从 而 构 成 一 个 基 本 可行 解 。 当 每 一 基 变 量 xij选 取 时 i产 地 的 剩 余 商 品 量 与 j销 地 的 剩 余 需 求 量总 不 相 等 ， 选 出 的 基 本 可 行 解 是 非 退 化 的 。初 始 基 本 可 行 解 也 可 按 其 他 方式 选 取 ， 如 “ 左 上 角 法 ” 等 ，其 方 法 与 原 理 是 类 似 的 ， 左 上角 法 每 次 选 取 剩 余 表 格 中 位 于 最 左 上 角 的 变 量 ， 其 余 均 相 同 。 上 一 页 下 一 页 33 三 、 最 优 性 判 别类 似 单 纯 形 法 ， 可 计 算 非 基 变 量 的 检 验 数 ， 存 在 多 种 求 检 验 数 的 方 法（ 求 得 的 结 果 是 相 同 的 ） ， 下 面 介 绍 计 算 简 便 且 计 算 量 也 较 小 的 “ 位 势法 ” 。 引 入 m+n个 量 （ 被 称 为 位 势 ） u1， ， um； u1， ， un。 对 每 一 变量 xij， 引 入 rij,令 xij= ij- ui-vj(事 实 上 ， 这 一 公 式 与 单 纯 形 法 求 检 验数 的 公 式 是 相 同 的 )。 对 基 变 量 xij， 令 rij=0， 得 到Cij ui vj=0 (xij为 基 变 量 ) （ 8.10) 齐 次 线 性 方 程 组 （ 8.10） 共 有 m+n 个 独 立 方 程 ， 但 含 有 m+n个 变 量 。任 取 一 变 量 ， 例 如 u 1作 为 自 由 变 量 ， 便 可 解 出 方 程 组 。 容 易 看 出 ， u1的取 值 不 同 虽 会 改 变 位 势 的 取 值 但 不 会 改 变 非 基 变 量 的 检 验 数 。 为 方 便 起见 ， 只 要 令 u1 即 可 。 事 实 上 ， 我 们 甚 至 不 必 去 解 方 程 组 （ 8.10） ， 而只 需 令 u1 ， 对 所 有 基 变 量 令 ui vj cij， 即 = ij- ui-vj ， 在 表 上逐 次 求 出 所 有 位 势 ， 进 而 再 对 非 基 变 量 xij计 算 其 检 验 数rij= ij- ui-vj 上 一 页 下 一 页 34 例 如 ， 对 表 8.11中 取 定 的 基 ， 我 们 求 出 位 势 及 非 基 变 量 的 检 验数 ， 列 于 表 8.12中 ， 表 中 不 带 圈 的 数 为 基 变 量 取 值 ， 带 圈 的 数为 非 基 变 量 检 验 数 ， 右 上 角 的 数 为 单 位 运 价 ij。u1=0 2 2 11 13 3 0 4 1u1=5 10 3 3 5 3 9 2u3=-2 10 8 12 1 4 2 3 1 = 2 = 2 3 = 3 4 = 4利 用 线 性 代 数 知 识 可 以 证 明 下 列 各 定 理 (证 明 从 略 )：定 理 8.5 任 取 一 非 基 变 量 ， 将 其 加 入 基 变 量 集 合 中 ， 则 在 所 得变 量 集 合 中 存 在 唯 一 的 闭 回 路 。易 见 闭 回 路 中 含 有 偶 数 个 变 量 ， 若 令 进 基 ， 令 = ， 为 保 持 平衡 条 件 ， 位 于 偶 数 位 置 的 变 量 必 须 减 少 ， 而 位 于奇 数 位 置 的 变 量 则 必 须 增 加 （ 注 ： ） 。1 1i jx 1 1 1 2 1, , , ,t t ti j i j i j i jx x x x1 1i jx 1 1i jx 1( 1, , )k ki jx k t ( 1, , )k ki jx k t 1 1tj j 表 8.12 上 一 页 下 一 页 35 定 理 8.6 设 是 非 基 变 量 与 基 变 量 集 合 的并 集 中 唯 一 的 闭 回 路 ， 若 令 = 并 在 闭 回 路 上 调 整 基 变 量 取 值 使之 平 衡 ， 得 一 可 行 解 x， 则 x处 的 目 标 值 与 原 基 本 可 行 解 上 的 目 标 值 之差 为 。 1 1 1 2 1, , , ,t t ti j i j i j i jx x x x 1 1i jx1 1i jx1 1i jr 根 据 定 理 8.6， 若 存 在 检 验 数 的 非 基 变 量 ， 取 进 基 （ 取正 值 ） 并 令 （ 8.12）则 原 取 值 为 的 位 于 偶 数 位 置 的 基 变 量 退 基 ， 得 到 一 新 的 基 本 可 行 解 ，其 目 标 值 减 少 。 1 1 0i jr 1 1i jx 1 1 11min k ki j i jk tx x 1 1i jr 1 1i jx定 理 8.7 设 为 （ 8.9） 的 一 个 基 本 可 行 解 ， 若 x0所 有 非 基 变量 的 检 验 数 均 非 负 ， 则 x0必 为 （ 8.9） 的 一 个 最 优 解 。 当 x0非 退 化 时 ，此 条 件 还 是 必 要 的 。0 0 ijx x证 明 由 定 理 8.6知 ， 当 x0所 有 非 基 变 量 的 检 验 数 均 非 负 时 ， 任 一 非 基 变量 进 基 均 不 会 使 目 标 值 减 小 ， 由 于 （ 8.9） 是 一 线 性 规 划 ， 此 性 质 表 明 x0已 为 最 优 基 本 可 行 解 。 反 之 ， 则 只 要 令 具 有 负 检 验 数 的 非 基 变 量 进 基 即 可 。 上 一 页 下 一 页 36 综 上 所 述 ， 康 希 表 上 作 业 法 可 如 下 操 作 ：（ 步 1） 按 最 小 元 素 法 （ 或 右 上 角 法 等 ） 求 一 初 始 基 本 可 行 解 。（ 步 2） 按 （ 8.10） 求 出 位 势 ui, j（ i=1,m; j=1,n） 。 进而 按 （ 8.11） 求 出 非 变 量 的 检 验 数 rij。 若 一 切 rij 0， 则 已 求 得 一最 优 解 。（ 步 3） 任 取 一 0， 找 出 进 基 后 形 成 的 唯 一 闭 回 路 。 在 找 出 的 闭 回路 上 调 整 ， 按 （ 8.12） 取 ， 得 出 新 的 基 本 可 行 解 ， 返 回 步 2。 直 至找 到 最 优 解 。 上 一 页 下 一 页 37 对 于 例 8.3， 表 8.12已 给 出 非 基 变 量 的 检 验 数 。 因 r230， 令 x23进 基 ， 得闭 回 路x23, x24, x34, x33取 =min x24, x33 =2， 调 整 后 得 一 新 的 基 本 可 行 解 。 求 出 新 的 基 本可 行 解 、 对 应 的 位 势 及 非 基 变 量 检 验 数 ， 列 成 表 8.13。表 8.13u1=0 2 2 11 11 3 4 1u1=3 10 3 3 5 2 9 u3= 1 7 8 1 2 3 5 1 = 2 = 0 3 = 3 4 = 4现 在 ， 非 基 变 量 检 验 数 均 已 非 负 ， 故 已 求 得 最 优 解 ： x11=2， x14=1，x22=3， x23=2， x33=2， x34=5， 其 余 =0（ 非 基 变 量 ） 。若 运 输 问 题 是 产 销 不 平 衡 的 ， 则 应 先 将 其 转 化 为 产 销 平 衡 的 ， 然 后 再求 解 。 例 如 ， 若 产 大 于 销 ， 可 虚 设 一 销 地 （ 剩 余 产 量 存 贮 ） ， 将 单 位运 价 取 为 零 即 可 。 ijx 上 一 页 下 一 页 38 一 、 指 派 问 题 的 数 学 模 型 8.3 指 派 问 题 例 8.4 拟 分 配 n人 去 干 n项 工 作 ， 每 人 干 且 仅 干 一 项 工 作 ， 若 分 配 第 i人去 干 第 j项 工 作 ， 需 化 费 Cij单 位 时 间 ， 问 应 如 何 分 配 工 作 才 能 使 工 人 化费 的 总 时 间 最 少 ？容 易 看 出 ， 要 给 出 一 个 指 派 问 题 的 实 例 ， 只 需 给 出 矩 阵 C=（ Cij） ,C被 称为 指 派 问 题 的 系 数 矩 阵 。引 入 变 量 xij， 若 分 配 i干 j工 作 ， 则 取 xij =1， 否 则 则 取 xij =0。 上 述 指 派问 题 的 数 学 模 型 为 S.t （ 8.13） x ij=0或 1 1 1min n n ij iji j C x 1 1n ijj x 1 1n iji x 上 一 页 下 一 页 39 （ 8.13） 的 可 行 解 既 可 以 用 一 个 矩 阵 表 示 ， 其 每 行 每 列 均 有 且 只 有 一个 元 素 为 1， 其 余 元 素 均 为 0， 也 可 以 用 1,n中 的 一 个 置 换 表 示 。 （ 8.13） 的 变 量 只 能 取 0或 1， 从 而 是 一 个 01规 划 问 题 。 下 一 章 将指 出 ， 一 般 的 01规 划 问 题 的 求 解 极 为 困 难 。 但 指 派 问 题 （ 8.13 ）并 不 难 解 ， 其 约 束 方 程 组 的 系 数 矩 阵 十 分 特 殊 （ 被 称 为 全 单 位 模 矩阵 或 全 幺 模 矩 阵 ， 其 各 阶 非 零 子 式 均 为 1） ， 其 非 负 可 行 解 的 分 量只 能 取 0或 1， 故 约 束 “ xij=0或 1”可 改 写 为 xij 0而 不 改 变 其 解 。 此 时 ，（ 8.13） 被 转 化 为 一 个 特 殊 的 运 输 问 题 ， 其 中 m=n, ai=bi=1。 上 一 页 下 一 页 40 二 、 求 解 指 派 问 题 的 匈 牙 利 算 法由 于 指 派 问 题 的 特 殊 性 ， 又 存 在 着 由 匈 牙 利 数 学 家 Konig提 出 的 更 为 简便 的 解 法 匈 牙 利 算 法 。 算 法 主 要 依 据 以 下 事 实 ： 如 果 将 系 数 矩 阵C=（ Cij） 中 一 行 （ 或 一 列 ） 的 每 一 元 素 都 加 上 或 减 去 同 一 个 数 ， 得 到一 个 新 矩 阵 B=（ bij） ， 则 以 C和 B为 系 数 矩 阵 的 指 派 问 题 具 有 相 同 的 最优 指 派 。 例 8.5 求 解 指 派 问 题 ， 其 系 数 矩 阵 为 16 15 19 2217 21 19 1824 22 18 17 17 19 22 16C 上 一 页 下 一 页 41 解 将 第 一 行 元 素 减 去 此 行 中 的 最 小 元 素 15， 同 样 ， 第 二 行 元 素 减去 17， 第 三 行 元 素 减 去 17， 最 后 一 行 的 元 素 减 去 16， 得1 1 0 4 70 4 2 17 5 1 01 3 6 0B *2 * *1 0 3 70 4 1 17 5 0 01 3 5 0B 再 将 第 3列 元 素 各 减 去 1， 得以 B2为 系 数 矩 阵 的 指 派 问 题 有 最 优 指 派由 等 价 性 ， 它 也 是 例 2的 最 优 指 派 。有 时 问 题 会 稍 复 杂 一 些 ， 见 下 面 的 例 8.61 2 3 42 1 3 4 上 一 页 下 一 页 42 例 8.6 求 解 下 面 的 系 数 矩 阵 为 C的 指 派 问 题12 7 9 7 98 9 6 6 67 17 12 14 1215 14 6 6 104 10 7 10 6C 解 ： 先 作 等 价 变 换 如 下 * * *7 12 7 9 7 9 5 0 2 0 26 8 9 6 6 6 2 3 0 0 07 7 17 12 14 12 0 10 5 7 56 15 14 6 6 10 9 8 0 0 44 4 10 7 10 6 0 6 3 6 2 容 易 看 出 ， 从 变 换 后 的 矩 阵 中 只 能 选 出 四 个 位 于 不 同 行 不 同 列 的 零 元 素 ，但 n=5， 最 优 指 派 还 无 法 看 出 。 此 时 等 价 变 换 还 可 进 行 下 去 。 上 一 页 下 一 页 43 步 骤 如 下 ： （ 1） 对 未 选 出 0元 素 的 行 打 ；（ 2） 对 行 中 0元 素 所 在 列 打 ；（ 3） 对 列 中 选 中 的 0元 素 所 在 行 打 ；重 复 （ 2） 、 （ 3） 直 到 无 法 再 打 为 止 。可 以 证 明 ， 若 用 直 线 划 没 有 打 的 行 与 打 的 列 ， 就 得 到 了 能 够 复 盖 住矩 阵 中 所 有 零 元 素 的 最 少 条 数 的 直 线 集 合 。 找 出 未 复 盖 的 元 素 中 的 最 小者 ， 令 行 元 素 减 去 此 数 ， 列 元 素 加 上 此 数 ， 则 原 先 选 中 的 0元 素 不变 ， 而 未 复 盖 元 素 中 至 少 有 一 个 已 转 变 为 0， 且 新 矩 阵 的 指 派 问 题 与 原问 题 也 等 价 。 上 述 过 程 可 反 复 采 用 ， 直 到 能 选 出 足 够 的 0元 素 为 至 。 例如 ， 对 例 8.6变 换 后 的 矩 阵 再 变 换 ， 第 三 行 、 第 五 行 元 素 减 去 2， 第 一列 元 素 加 上 2， 得7 0 2 0 2 4 3 0 0 00 8 3 5 311 8 0 0 40 4 1 4 0 现 在 已 可 看 出 ， 最 优 指 派 为1 2 3 4 52 4 1 3 5 （ 注 ： 相 应 定 理 从 略 ） 上 一 页 下 一 页 44 8.4 计 算 复 杂 性 问 题 的 提 出离 散 模 型 的 实 质 是 从 有 限 多 个 候 选 值 中 选 取 一 个 最 佳 取 值 。 例 如 8.1中的 线 性 规 划 ， 虽 然 可 行 解 一 般 有 无 穷 多 个 ， 但 线 性 规 划 基 本 定 理 指 出 ，只 要 存 在 有 限 最 优 解 ， 就 必 可 在 基 本 可 行 解 中 找 到 ， 而 基 本 可 行 解 总 共只 有 有 限 多 个 。 Dantzig的 单 纯 形 法 正 是 利 用 了 这 一 性 质 ， 在 基 本 可 行 解中 选 取 最 优 解 。在 有 限 多 个 候 选 者 中 选 择 其 中 之 一 ， 通 常 不 存 在 连 续 模 型 中 备 受 关 注 的解 的 存 在 性 问 题 ， 因 为 有 限 个 值 中 选 取 最 佳 取 值 ， 解 的 存 在 性 不 成 问 题 。解 的 唯 一 性 问 题 也 不 再 被 人 们 重 视 。 例 如 ， 在 用 单 纯 形 法 求 得 一 最 优 基本 可 行 解 后 ， 我 们 认 为 问 题 已 被 解 出 ， 它 是 否 还 有 其 他 的 最 优 解 ， 我 们一 般 不 再 感 兴 趣 。 上 一 页 下 一 页 45 也 许 有 人 会 想 ， 从 有 限 种 可 能 方 案 中 挑 选 一 种 ， 这 总 是 比 较 容 易 的 。如 果 一 一 比 较 下 去 ， 最 后 总 可 以 得 出 满 意 的 结 果 。 然 而 ， 事 实 并 非 如此 简 单 ， 关 键 在 于 问 题 的 规 模 和 求 解