资源描述
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 也 许 有 人 会 想 , 从 有 限 种 可 能 方 案 中 挑 选 一 种 , 这 总 是 比 较 容 易 的 。如 果 一 一 比 较 下 去 , 最 后 总 可 以 得 出 满 意 的 结 果 。 然 而 , 事 实 并 非 如此 简 单 , 关 键 在 于 问 题 的 规 模 和 求 解
展开阅读全文