线性规划与单纯形法

线 性 规 划 与 单 纯 形 法 线 性 规 划 （ LP： Linear Programming） 规 划 论 中 的 静 态 规 划 解 决 有 限 资 源 的 最 佳 分 配 问 题 求 解 方 法 ： 图 解 法 单 纯 形 解 法 线性规划简介 1939年 苏 联 的 康 托 洛 维 奇 （ H.B.Kahtopob ） 和 美 国 的 希 奇柯 克 （ F.L.Hitchcock） 等 人 就 在 生 产 组 织 管 理 和 制 定 交 通运 输 方 案 方 面 首 先 研 究 和 应 用 一 线 性 规 划 方 法 。 1947年 旦 茨 格 等 人 提 出 了 求 解 线 性 规 划 问 题 的 单 纯 形 法 ，为 线 性 规 划 的 理 论 与 计 算 奠 定 了 基 础 。 随 着 电 子 计 算 机 的 出 现 和 日 益 完 善 ， 规 划 论 得 到 迅 速 的 发展 ， 可 用 电 子 计 算 机 来 处 理 成 千 上 万 个 约 束 条 件 和 变 量 的大 规 模 线 性 规 划 问 题 ， 从 解 决 技 术 问 题 的 最 优 化 ， 到 工 业 、农 业 、 商 业 、 交 通 运 输 业 以 及 决 策 分 析 部 门 都 可 以 发 挥 作用 。 线性规划问题的三个要素 决 策 变 量 决 策 问 题 待 定 的 量 值 称 为 决 策 变 量 。 决 策 变 量 的 取 值 要 求 非 负 。 约 束 条 件 任 何 问 题 都 是 限 定 在 一 定 的 条 件 下 求 解 ， 把 各 种 限 制 条件 表 示 为 一 组 等 式 或 不 等 式 ， 称 之 为 约 束 条 件 。 约 束 条 件 是 决 策 方 案 可 行 的 保 障 。 LP的 约 束 条 件 ， 都 是 决 策 变 量 的 线 性 函 数 。 目 标 函 数 衡 量 决 策 方 案 优 劣 的 准 则 ， 如 时 间 最 省 、 利 润 最 大 、 成本 最 低 。 目 标 函 数 是 决 策 变 量 的 线 性 函 数 。 有 的 目 标 要 实 现 极 大 ， 有 的 则 要 求 极 小 。 1线性规划问题及其数学模型 设 备原 料 A原 料 B 1 4 0 2 0 4 8台 时 16kg 12kg例 某 工 厂 在 计 划 期 内 要 安 排 生 产 、 两 种 产 品 ，已 知 生 产 单 位 产 品 所 需 的 设 备 台 时 和 原 料 A、 B的 消耗 量 如 下 表 。 该 工 厂 每 生 产 一 件 产 品 可 获 利 2元 ，每 生 产 一 件 产 品 可 获 利 3元 ， 问 应 如 何 安 排 生 产 计划 能 使 该 厂 获 利 最 多 ？ 这 个 问 题 可 以 用 下 面 的 数 学 模 型来 描 述 ， 设 计 划 期 内 产 品 、 的 产 量 分 别 为 x1， x2， 可 获 利 润用 z表 示 ， 则 有 ： Max Z=2x1+3x2x1+2x284x1 16 4x212x1, x20 1.1问 题 的 提 出 又 例 靠 近 某 河 流 有 两 个 化 工 厂 ， 流 经第 一 化 工 厂 的 河 流 流 量 为 每 天 500万 m3，两 工 厂 之 间 有 一 条 流 量 为 每 天 200万 m3的支 流 （ 见 图 ） 。 第 一 化 工 厂 每 天 排 放 污 水 2万 m3， 第 二化 工 厂 每 天 排 放 污 水 1.4万 m3。 污 水 从工 厂 1流 到 工 厂 2前 会 有 20%自 然 净 化 。根 据 环 保 要 求 ， 河 水 中 污 水 的 含 量 应 不大 于 0.2%。 而 工 厂 1和 工 厂 2处 理 污 水 的成 本 分 别 为 1000元 /万 m 3和 800元 /万 m3。问 两 工 厂 各 应 处 理 多 少 污 水 才 能 使 处 理污 水 的 总 费 用 最 低 ？ 设 工 厂 1和 工 厂 2每 天 分 别 处 理 污 水 x1和 x2万 m3， 则 有 ：Min z=1000 x1+800 x2 (2-x1)/500 0.0020.8(2-x1)+1.4-x2/700 0.002 x12, x21.4 x1, x20 以 上 两 例 都 有 一 些 共 同 的 特 征 ： 用 一 组 变 量 表 示 某 个 方 案 ， 一般 这 些 变 量 取 值 是 非 负 的 。 存 在 一 定 的 约 束 条 件 ， 可 以 用线 性 等 式 或 线 性 不 等 式 来 表 示 。 都 有 一 个 要 达 到 的 目 标 ， 可 以用 决 策 变 量 的 线 性 函 数 来 表 示 。 满 足 以 上 条 件 的 数 学 模 型 称 为线 性 规 划 模 型 。 线 性 规 划 模 型的 一 般 形 式 如 下 ：0, ),( ),( ),(max(min) 21 2211 22222121 11212111 2211 n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxa xcxcxcz 其 中 ：cj为 价 值 系 数 ； aij为 技 术 系 数 ；bi为 限 额 系 数 ； xj为 非 负 变 量 图 解 法 即 是 用 图 示 的 方 法 来 求 解 线 性 规 划 问题 。 一 个 二 维 的 线 性 规 划 问 题 ， 可 以 在 平 面 图 上求 解 ， 三 维 的 线 性 规 划 则 要 在 立 体 图 上 求 解 ，这 就 比 较 麻 烦 ， 而 维 数 再 高 以 后 就 不 能 图 示了 。1.2线性规划的图解法 可行域的确定 例 :数 学 模 型 为 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x 1 +4 x2 36 x1 0, x2 0S.t. x1 =8 2x2 =123x1 +4 x2 =36x1x2 4 8 12369 五 边 形 OABCD内 (含 边 界 )的 任 意 一 点 (x1， x2) 都 是 满 足 所 有约 束 条 件 的 一 个 解 ， 称 之 可 行 解 。 满 足 所 有 约 束 条 件 的 解 的 集 合 ， 称 之 为 可 行 域 。 即 所 有 约 束条 件 共 同 围 城 的 区 域 。 最优解的确定Z=30 Z=42Z=15 目 标 函 数 Z= 3x1 +5 x2 代 表 以 Z为 参 数 的 一 族 平 行 线 。x1 =8 2x2 =12 3x1 +4 x2 =36x1x2 4 8 12369 等 值 线 ： 位 于 同 一 直 线 上 的 点 的 目 标 函 数 值 相 同 。 最 优 解 ： 可 行 解 中 使 目 标 函 数 最 优 (极 大 或 极 小 )的 解 由 线 性 不 等 式 组 成 的 可 行 域 是 凸 集 (凸 集 的 定义 是 ： 集 合 内 部 任 意 两 点 连 线 上 的 点 都 属 于 这个 集 合 )。 可 行 域 有 有 限 个 顶 点 。 设 规 划 问 题 有 n个 变 量 ，m个 约 束 ， 则 顶 点 的 个 数 不 多 于 Cnm个 。 目 标 函 数 最 优 值 一 定 在 可 行 域 的 边 界 达 到 ， 而不 可 能 在 其 内 部 。几点说明 解的可能性x 1 =8 2x2 =123x1 +4 x2 =36x1x2 4 8 12369上 例 的 数 学 模 型 变 为 maxZ= 3x1 +4 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t. Z=24 Z=36Z=12 唯 一 最 优 解 ： 只 有 一 个 最 优 点 。 多 重 最 优 解 ： 无 穷 多 个 最 优 解 。 若 在 两 个 顶 点 同 时得 到 最 优 解 ， 则 它 们 连 线 上 的 每 一 点 都 是 最 优 解 。 无 界 解 ： 线 性 规 划 问 题 的 可 行 域 无 界 ， 使 目 标 函数 无 限 增 大 而 无 界 。 （ 缺 乏 必 要 的 约 束 条 件 ）例 如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x 1 -3 x2 3 x1 0, x2 0 -2x1 + x2 =2 x1 -3 x2 =3x2123-1 x11 2 3-1 Z=6 Z=12S.t. 无 可 行 解 ： 若 约 束 条 件 相 互 矛 盾 ， 则 可 行 域 为 空 集例 如 maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x 1 0, x2 0 -2x1 + x2 =2 x1 -3 x2 =3x2123-1 x11 2 3-1S.t. 唯 一 最 优 解 无 穷 多 最 优 解x1x2 x1x2无 界 解 无 可 行 解当 线 性 规 划 的 可 行 域 非 空 它 是 有界 或 无 界 凸 多 边 形 ， 若 存 在 最 优解 ， 则 最 优 解 一 定 在 可 行 域 的 的某 个 顶 点 或 顶 点 的 连 线 取 得 ， 也即 有 唯 一 最 优 解 或 无 穷 多 最 优 解图 解 法 虽 然 简 单 直 观 ， 但 是 只 能解 决 两 个 变 量 练 习 :用 图 解 法 求 解 以 下 LP模 型 无 符 号 限 制 21 21 21 21, 232 22 65maxxx xx xx xxz Answer x1x2 -2x1+3x2=2x1-2x2=20Ax 1= -10,x2= -6,z= -86 1.3 线 性 规 划 的 标 准 型 线 性 规 划 问 题 的 数 学 模 型 有 各 种 不 同 的 形 式 ， 如 目 标 函 数 有 极 大 化 和 极 小 化 ； 约 束 条 件 有 “ ”、 “ ”和 “ ” 三 种 情 况 ； 决 策 变 量 一 般 有 非 负 性 要 求 ， 有 的 则 没 有 。 为 了 求 解 方 便 ， 特 规 定 一 种 线 性 规 划 的 标 准 形 式 ，非 标 准 型 可 以 转 化 为 标 准 型 。 标 准 形 式 为 ： 目 标 函 数 极 大 化 约 束 条 件 为 等 式 右 端 常 数 项 b i0 决 策 变 量 非 负 。 一 、标准型 1. 代 数 式二、标准型的表达方式 有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1,x2,xn 0 maxZ= cjxj aijxj bi ( i=1,2,m) xj0 ( j=1,2,n)nj 1nj 1简 记 2. 矩阵式 0.maxX bAXts XCZ ),( 21 ncccC 价 值 向 量 mnmm nnaaa aaa aaaA 21 22221 11211技 术 矩 阵 mbbbb 21资 源 向 量 nxxxX 21决 策 向 量 目 标 函 数 为 min z=c1x1+c2x2+cnxn 令 z=-z ,变 为 max z= -c1x1- c2x2- -cnxn 两 端 同 乘 以 -1 当 约 束 方 程 为 “ ”时 ， 左 端 加 入 一 个 非 负 的 松 弛 变 量 ， 就 把 不 等式 变 成 了 等 式 ； 当 约 束 条 件 为 “ ”时 ， 不 等 式 左 端 减 去 一 个 非 负 的 剩 余 变 量 (也可 称 松 弛 变 量 )即 可 。 令 x k=xk-x k ， 其 中 xk， x k 0 ， 用 xk、 x k 取 代 模 型 中 xk 三、非标准型向标准型转化 标 准 型 例 1 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t. x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30 例 2 minZ= x1 +2 x2 -3 x3 x1 +2 x2 - x3 5 2x1 +3 x2 - x3 6 -x1 - x2 + x3 -2 x1 0, x3 0 标 准 化 1S.t. 标 准 化 2 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 - x1 - (x2-x 2 ) - x3 -2 x1, x2,x 2 , x3 0 标 准 化 3 minZ= x1 +2 (x2-x 2 ) +3 x3 x 1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2 , x3 0 标 准 化 4 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x3+ x4 =5 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2 , x3, x4 0 标 准 化 5 minZ= x1 +2 (x2-x 2 ) +3 x3 x 1 +2 (x2-x 2 ) + x3+ x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2 , x3, x4 , x5 0 标 准 化 6 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x3+ x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2 , x3, x4 , x5 , x6 0 标 准 化 7 maxZ= -x1 -2 (x2-x 2 ) - 3x3+0 x4+0 x5+0 x6 x 1 +2 (x2-x 2 ) + x3+ x4 =5 2x1 +3 (x2-x 2 ) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2 , x3, x4 , x5 , x6 0 可 行 解 ： 满 足 约 束 条 件 AX=b, X0的 解 。 最 优 解 ： 使 目 标 函 数 达 到 最 大 的 可 行 解 ， 称 为 最 优 解 。 基 设 A是 约 束 方 程 组 的 m n维 系 数 矩 阵 ， 其 秩 为 m， B是 矩 阵 A中 的 m m阶 非 奇 异 子 矩 阵 ， 则 称 B是 线 性 规划 问 题 的 一 个 基 。 m n， 且 m个 方 程 线 性 无 关 ， 即 矩 阵 A的 秩 为 m； 根据 线 性 代 数 定 理 可 知 ， n m， 则 方 程 组 有 多 个 解 ，这 也 正 是 线 性 规 划 寻 求 最 优 解 的 余 地 所 在 。 一、线性规划解的概念 1.4 线 性 规 划 问 题 的 解 的 概 念 线 性 方 程 组 的 增 广 矩 阵 例 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 3610 1201 800043 020 101A x1 x2 x3 x4 x5 基 矩 阵 ： 系 数 矩 阵 A中 任 意 m列 所 组 成 的 m阶 非 奇 异 子 矩 阵 ，称 为 该 线 性 规 划 问 题 的 一 个 基 矩 阵 。 或 称 为 一 个 基 ， 用 B表 示 。 称 基 矩 阵 的 列 为 基 向 量 ， 用 Pj表 示 (j=1,2,m) 。 10 01 00043 020 101 A 的 基 矩 阵 B最 多 C53=10， 如 下 ： 100 010 001x3 x4 x5 103 010 001x1 x4 x5 104 012 000 x2 x4 x5 130 000 011x3 x1 x5 140 020 001x3 x2 x5 300 010 101x3 x4 x1 400 210 001x 3 x4 x2 043 020 101x1 x2 x5 x1 x2 x4 043 120 001 x1 x2 x5 143 020 001 基 变 量 ： 与 基 向 量 Pj相 对 应 的 m个 变 量 xj称 为 基 变 量 ， 其 余 的 m-n个 变 量 为 非 基 变 量 。 基 解 ： 令 所 有 非 基 变 量 等 于 零 ， 对 m个 基 变 量 所 求 的 解 对 应 一 个 特 定 的 基 矩 阵 能 求 得 一 组 唯 一 解 ， 这 个 对 应 于 基的 解 称 为 基 解 。 结 合 图 解 来 看 ， 基 解 是 各 约 束 方 程 及 坐 标 轴 之 间 交 点 的 坐标 。 100 010 001B x3 x4 x5 基 变 量 是 x3, x4, x5 非 基 变 量 是 x1, x2 令 非 基 变 量 x1=x2=0， 得 到 一 个 基 解 x3=8， x4=12， x5=36 基 可 行 解 ： 满 足 非 负 性 约 束 的 基 解 称 为 基 可 行 解 。 可 行 基 ： 对 应 于 基 可 行 解 的 基 ， 称 为 可 行 基 。 最 优 基 ： 最 优 解 对 应 的 基 矩 阵 ， 称 为 最 优 基 。 非可行解可行解基解基可行解 .若 线 性 规 划 问 题 存 在 可 行 域 ， 则 其 可行 域 一 定 是 凸 集 。.线 性 规 划 问 题 的 基 可 行 解 对 应 可 行 域的 顶 点 。.若 可 行 域 有 界 ， 线 性 规 划 的 目 标 函 数一 定 可 以 在 可 行 域 的 顶 点 上 达 到 最 优 。 二、线性规划的基本定理 线 性 规 划 问 题 可 以 有 无 数 个 可 行 解 ， 最 优 解 只 可 能 在顶 点 上 达 到 ， 而 有 限 个 顶 点 对 应 的 是 基 可 行 解 ， 故 只要 在 有 限 个 基 可 行 解 中 寻 求 最 优 解 即 可 。 从 一 个 顶 点 出 发 找 到 一 个 可 行 基 ， 得 到 一 组 基 可 行 解 ，拿 目 标 函 数 做 尺 度 衡 量 一 下 看 是 否 最 优 。 如 若 不 是 ， 则 向 邻 近 的 顶 点 转 移 ， 换 一 个 基 再 行 求 解 、检 验 ， 如 此 迭 代 循 环 目 标 值 逐 步 改 善 ， 直 至 求 得 最 优解 。 三、线性规划的解题思路 例 maxz=2x1+3x2St:X1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 Xi=0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1令 非 基 变 量 X4=X5=0， 则 可 解 出X1=4, X2=3, X3=-2所 以 得 出 基 解 X 1=（ 4， 2， -2， 0， 0） ， 但 由 于X30,所 以 X2是 可 行 解 ， 相 应 的 B2为 可 行 基若 用 以 上 方 法 可 枚 举 出 此 线 性 规 划 问 题 的 基 可 行 解 分 别 为 X3(4,0,4,0,12)， X4(0,3,2,16,0)， X5（ 2， 3， 0， 8， 0） 和 X6（ 4， 2， 0， 0， 4） ， 将 这 些 解 代 入目 标 函 数 ， 可 知 X 6可 使 得 Z最 大 ， 所 以 X6为 最 优 解 2 单 纯 形 法 单 纯 形 法 的 思 路 ： 先 找 到 一 个 初 始 可 行 基 ， 求 出这 个 基 可 行 解 ， 然 后 判 断 该 基 可 行 解 是 否 为 最 优解 ， 若 是 最 优 解 ， 则 求 解 结 束 ， 若 不 是 ， 则 进 行基 变 换 ， 得 到 一 个 新 的 可 行 基 ， 再 进 行 判 断 该 基可 行 解 是 否 为 最 优 解 。 每 次 基 变 换 后 的 目 标 函 数不 断 增 大 ， 一 直 到 找 到 最 优 解 为 止 。 单 纯 形 法 基 本 思 路是 否 最 优 解 求 最 优 目 标 函 数 值是基 变 换 ,迭 代否确 定 初 始 可 行 解 2.1单 纯 形 法 的 原 理例 ： maxz=2X1+3X2+0X3+0X4+0X5 st X1+2X2+X3=8 4X1+X4=16 4X2+X5=12 Xj 0 系 数 子 矩 阵 1 2 1 0 0A=（ P1 P2 P3 P4 P5） = 4 0 01 0 0 4 0 0 1初 始 可 行 基 1 0 0 B1= 0 1 0 0 0 1（ 1）所 以 ： X 3=8-X1-2X2 X4=16-4X1 X5=12-4X2 将 此 代 入 目 标 函 数 Z=2X1+3X2， 令 非 基 变 量 等 于 0，则 得 到 一 个 基 可 行 解 X0=（ 0 0 8 16 12） ， 目 标 函 数值 等 于 0。 但 是 从 目 标 函 数 可 知 ， 因 X1， X2的 价 值 系数 均 大 于 0， 当 X1或 X2由 非 基 变 量 变 成 基 变 量 时 ， 目标 函 数 就 会 增 加 ， 所 以 此 解 并 非 最 优 解 。 将 x2换 入 ， x2换 入 后 ， 需 从 X3,X4,X5中 换 出 一 个 变 量 ， 并 保 证 所 有 变 量 非 负X3=8-2X2 X4=16X5=12-4X2 当 X2增 大 时 ， 要 满 足 X3， X4， X5 0， 所 以 x2的 最 大 只 能 取 3， 且此 时 x5为 换 出 变 量（ 2） 基 变 换 新 基 变 量 为 （ X3， X4， X2） ， 得X3=2-X1+0.5X5X 4=16-4X1X2=3-0.25X5 代 入 目 标 函 数 得 Z=9+2X1-0.75X5因 为 x1的 系 数 为 正 ， 依 然 不 是 最 优 解 ， 换 入 x1， 再 经 过 迭 代最 后 的 最 优 解 （ 4 2 0 0 4） 2.2单 纯 形 法 求 解（ 1） 初 始 基 可 行 解 的 确 定a 直 接 观 察 法b 构 造 法 形 式 ， 加 松 弛 变 量 形 式 ,减 松 弛 变 量 后 加 人 工 变 量 （ 具 体 求 解 要 用 大 法 或 二 阶 段 法 ） 目 的 :使 初 始 可 行 基 为 单 位 阵 ,令 非 基 变 量 等 于 零 ,因 为b 0,即 可 以 得 到 初 始 基 可 行 解 . （ 2） 最 优 性 检 验 与 解 的 判别四 种 情 况 : 唯 一 最 优 解 无 穷 多 最 优 解 无 界 解 无 可 行 解 一 般 情 况 下 ,经 过 迭 代 后 jnmj mi ijijimi i jnmj ijii xaccbcz mi xabx )(),2,1( 1 1 1 1 z0 j 对 于 a.最 优 解 的 判 别 定 理 :若 为 对 应 于 基 B的 一 个 基 可 行 解 ,且 对 于 一 切j=m+1,n有 j 0,则 为 最 优 解 .称 j为 检 验 数 . 21)0( )0,0,( mbbbX )0(X nmj jjxzz 10 证 明 :因 对 一 切 非 基 变 量 的 角 下 标 j，均 有 0， 显 然 ， 对 于 任 一 可 行 解 均 有 z z0,但 基 本 可 行 解 能 使等 式 成 立 ， 故 为 最 优 解 )0(X)0(Xj b.无 穷 多 最 优 解 的 判 别 定 理 :若 为 一 个 基 可 行 解 ,且 对 于 一 切 j=m+1,n有 j 0,又 存 在 某 个 非 基 变 量 的 检 验 数 m+k=0,则 线 性 规 划 问 题 有 无 穷 多 最 优 解 21)0( )0,0,( mbbbX c.无 界 解 （ 无 有 限 最 优 解 ） 判 别 定 理若为 一 基 可 行 解 ， 有 一 个 m+k ， 并 且 对 i=1,2, ,m有 ai,m+k 0,那 么 该 线 性 规 划 问 题 具 有 无 界 解 （ 无 最优 解 ） 21)0( )0,0,( mbbbX d.无 可 行 解 约 束 条 件 相 互 矛 盾 ， 可 行 域 为 空 集 最 终 计 算 表 中 人 工 变 量 仍 然 为 基 变 量 （ 3） 基 变 换 当 初 始 基 可 行 解 不 是 最 优 解 及 不 能 判 别 无 界 时 ,需 要 找一 个 新 的 基 可 行 解 ,具 体 是 从 原 可 行 解 基 中 换 一 个 列 向量 ,得 到 一 个 新 的 可 行 基 ,称 为 基 变 换 . 基 变 换 的 关 键 是 如 何 选 择 换 入 变 量 和 换 出 变 量 这 两 个问 题 .(原 则 和 原 则 )a.换 入 变 量 ： 当 j0时 取 j中 最 大 的 所 对 应 的 非 基 变 量xk 。b.换 出 变 量 ： =b i/aik(aik0)中 最 小 的 所 对 应 的 xl为换 出 变 量 。 经 过 基 变 换 得 到 的 解 是 基 可 行 解 ,目 标 函 数 值 增 加 （ 4） 迭 代 运 算 将 xk和 xl进 行 对 换 ， 即 把 Pk变 为 单 位 列 向 量 取 代 Pl,可通 过 系 数 矩 阵 的 增 广 矩 阵 的 初 等 变 换 来 实 现 将 增 广 矩 阵 的 第 l行 除 以 alk 将 k列 除 alk变 换 为 1以 外 ， 其 他 都 变 成 0。 alk称 之 为 主 元 素 ， k列 成 为 主 元 列 ， l行 称 为 主 远 行 。 2.3 单 纯 形 表 单 纯 形 表 ， 是 对 上 节 讨 论 的 方 法 步 骤 进 行 具 体 化 、规 范 化 、 表 格 化 的 结 果 。 Cj C1 C2 Cj Cn 比值CB XB b x1 x2 xj xnCB1 xB1 b1 a11 a12 a1j a1n 1CB2 xB2 b2 a21 a22 a2j a2n 2 C Bn xBn bm am1 am2 amj amn m检 验 数 j -Z 1 2 j n 将 线 性 规 划 问 题 化 成 标 准 型 。 找 出 或 构 造 一 个 m阶 单 位 矩 阵 作 为 初 始 可 行 基 ， 建 立 初 始 单 纯形 表 。 计 算 各 非 基 变 量 xj的 检 验 数 j=Cj-CBPj ， 若 所 有 j0， 则 问 题已 得 到 最 优 解 ， 停 止 计 算 ， 否 则 转 入 下 步 。 在 大 于 0的 检 验 数 中 ， 若 某 个 k所 对 应 的 系 数 列 向 量 Pk0， 则此 问 题 是 无 界 解 ， 停 止 计 算 ， 否 则 转 入 下 步 。 根 据 maxj j 0=k原 则 ， 确 定 xk为 换 入 变 量 (进 基 变 量 )，再 按 规 则 计 算 ： =minbi/aik| aik 0=bl/ aik 确 定 xBl为 换 出 变量 。 建 立 新 的 单 纯 形 表 ， 此 时 基 变 量 中 x k取 代 了 xBl的 位 置 。 以 aik为 主 元 素 进 行 迭 代 ， 把 xk所 对 应 的 列 向 量 变 为 单 位 列 向 量 ，即 aik变 为 1， 同 列 中 其 它 元 素 为 0， 转 第 步 。 单纯形法的计算步骤 maxZ=3x1 +5 x2 +0 x3 +0 x4+0 x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36 单纯形法计算举例Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 5 0 0 08 1 0 1 0 012 0 2 0 1 036 3 4 0 0 1x3x4x5000 0 3 5 0 0 0 -12/2=636/4=9 mi ijBjj aCC i1 检 验 数 j 8 1 0 1 0 06 0 1 0 1/2 012 3 0 0 -2 1x3x2x5050 -30 3 0 0 -5/2 0 8-4Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 5 0 0 08 1 0 1 0 012 0 2 0 1 036 3 4 0 0 1x3x4x5000 0 3 5 0 0 0 -12/2=636/4=9 Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 5 0 0 08 1 0 1 0 06 0 1 0 1/2 012 3 0 0 -2 1x3x2x5050 -30 3 0 0 -5/2 0 8-4检 验 数 j 4 0 0 1 2/3 -1/36 0 1 0 1/2 04 1 0 0 -2/3 1/3x3x2x1053 -42 0 0 0 -1/2 -1最 优 解 :X*=(4,6,4,0,0)T， Z*=42 最 优 基 Cj 3 5 0 0 0 比值CB XB b x1 x2 x3 x4 x50 x3 4 0 0 1 2/3 -1/35 x2 6 0 1 0 1/2 03 x1 4 1 0 0 -2/3 1/3检 验 数 j -42 0 0 0 -1/2 -1 340 020 101*B x3 x2 x1 31320 0210 313211*B 最 优 基 的 逆 最 优 基 和 最 优 基 的 逆 又 例Max z=2x1+3x2 x 1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1, x2, x3 ,x4,x50 此 问 题 的 最 优 解 为 :x1*=4, x2*=2, x5*=4, x3*= x4*= x1*=0, z*=24+32=14例 Max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1, x2 0 例如maxZ= 3x1 +2 x2 -2x1 + x2 2 x1 -3 x2 3 x1 , x2 0S.t.标准化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x 1 , x2 , x3, x4 0 Cj 比值CB XB b检 验 数 j x1 x2 x3 x43 2 0 02 -2 1 1 03 1 -3 0 1x3x400 0 3 2 0 0 -3检 验 数 j 8 0 -5 1 2x3x103 -3 1 -3 0 1-9 0 11 0 -3 此 时 ， 检 验 数 2=11 0， 还 没 有 得 到 最 优 解 。 确 定 x2进 基 ， 但 x2所 在 列 的 系 数 向 量 元 素 非 正 ， 无 界 值 不 存 在 ， 有 进 基 变 量 但 无 离 基 变 量 。 用 单 纯 形 法 解 题 时 ， 需 要 有 一 个 单 位 矩 阵 作 为 初 始 基 。 当 约 束 条 件 都 是 “ ”时 ， 加 入 松 弛 变 量 就 形 成 了 初 始 基 。 但 实 际 存 在 “ ”或 “ ” 型 的 约 束 ， 没 有 现 成 的 单 位 矩 阵 。采用人造基的办法： 在 没 有 单 位 列 向 量 的 等 式 约 束 中 加 入 人 工 变 量 ， 构 成 原 线 性规 划 问 题 的 伴 随 问 题 ， 从 而 得 到 一 个 初 始 基 。 人 工 变 量 是 在 等 式 中 人 为 加 进 的 ， 只 有 它 等 于 0时 ， 约 束 条 件才 是 它 本 来 的 意 义 。处理方法有两种： 大 M 法 两 阶 段 法3.单 纯 形 法 的 进 一 步 讨 论 没 有 单 位 矩 阵 ， 不 符 合 构 造 初 始 基 的 条 件 ， 需 加 入 人工 变 量 。 人 工 变 量 最 终 必 须 等 于 0才 能 保 持 原 问 题 性 质 不 变 。 为 保 证 人 工 变 量 为 0， 在 目 标 函 数 中 令 其 系 数 为 -M。 M为 无 限 大 的 正 数 ， 这 是 一 个 惩 罚 项 ， 倘 若 人 工 变 量不 为 零 ， 则 目 标 函 数 就 永 远 达 不 到 最 优 ， 所 以 必 须 将人 工 变 量 逐 步 从 基 变 量 中 替 换 出 去 。 如 若 到 最 终 表 中 人 工 变 量 仍 没 有 置 换 出 去 ， 那 么 这 个问 题 就 没 有 可 行 解 ， 当 然 亦 无 最 优 解 。 大M法 例 如 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t. 按 大 M法 构 造 人 造 基 ， 引 入 人 工 变 量 x4 , x5 的 辅 助 问 题 如 下 ： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 -1 -2 -M -M6 3 2 -3 1 04 1 -2 1 0 100-2-2M-13+4M-10Mx4x5-M-M 24 mi ijBjj aCC i1 Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 -1 -2 -M -M6 3 2 -3 1 04 1 -2 1 0 13+4M -1 -2-2M 0 0 x4x5-M-M 24检 验 数 j 2 1 2/3 -1 1/3 02 0 -8/3 2 -1/3 10-1-4M/31+2M-3-8M/30 x1x53-M -1检 验 数 j 3 1 -2/3 0 1/6 1/21 0 -4/3 1 -1/6 1/20 -5/3 0 -M-5/6 -M-1/2x1x33-2 用 计 算 机 处 理 数 据 时 ， 只 能 用 很 大 的 数 代 替 M,可 能造 成 计 算 机 上 的 错 误 ， 故 多 采 用 两 阶 段 法 。 第 一 阶 段 ： 在 原 线 性 规 划 问 题 中 加 入 人 工 变 量 ， 构 造 如 下 模 型 ： 0 00min1 11 111111 11mn mmnnmnm nnn nmnnxx bxxaxa bxxaxa xxxxW 两 阶 段 法 对 上 述 模 型 求 解 （ 单 纯 形 法 ） ， 若W=0,说 明 问 题 存 在 基 本 可 行 解 ， 可 以 进 行第 二 个 阶 段 ； 否 则 ， 原 问 题 无 可 行 解 ， 停止 运 算 。 第 二 阶 段 ： 在 第 一 阶 段 的 最 终 表 中 ，去 掉 人 工 变 量 ， 将 目 标 函 数 的 系 数 换 成 原问 题 的 目 标 函 数 系 数 ， 作 为 第 二 阶 段 计 算的 初 始 表 （ 用 单 纯 形 法 计 算 ） 。 单 纯 形 法 补 遗 进 基 变 量 相 持 ： 单 纯 形 法 运 算 过 程 中 ， 同 时 出 现 多 个 相 同 的 j最 大 。 在 符 合 要 求 的 j(目 标 为 max： j 0， min： j 0)中 ， 选 取 下 标 最小 的 非 基 变 量 为 换 入 变 量 ； 离 基 变 量 相 持 ： 单 纯 形 法 运 算 过 程 中 ， 同 时 出 现 多 个 相 同 的 最 小 值 。 继 续 迭 代 ， 便 有 基 变 量 为 0， 称 这 种 情 况 为 。 选 取 其 中 下 标 最 大 的 基 变 量 做 为 换 出 变 量 。 多 重 最 优 解 ： 最 优 单 纯 形 表 中 ， 存 在 非 基 变 量 的 检 验 数 j=0。 让 这 个 非 基 变 量 进 基 ， 继 续 迭 代 ， 得 另 一 个 最 优 解 。 无 界 解 ： 大 于 0的 检 验 数 中 ， 若 某 个 k所 对 应 的 系 数 列 向 量 Pk0， 则 解 无 界 。 无 可 行 解 ： 最 终 表 中 存 在 人 工 变 量 是 基 变 量 。 4.线 性 规 划 的 运 用解 先 看 有 多 少 种 裁 料 方 案 ， 再 进 行 组 合 和 选 择 。 方 案 ：套 裁 下 料 现 要 做 一 百 套 钢 管 , 每 套 要 长 为 2.9m、 2.1m和 1.5m的 钢 管 各一 根 。 已 知 原 料 长 7.4m， 问 应 如 何 下 料 ， 使 用 的 原 料 最 省 。 设 用 方 案 , , , 分别 裁 原 料 钢 管 x1,x2,.x5根 , 则 ： Min z= 0 x1+0.1 x2+0.2 x3+0.3x4+ 0.8x5x1+ 2x2 + x4 =100 2x3+2x4+x5 =100 3x1+x2 +2x3 +x5 =100 x1, x2, x3, x4, x5 0 例 某 工 厂 要 用 三 种 原 材 料 C,P,H混 合 调 配 出 三 种 不 同 规 格 的 产品 A,B,D。 已 知 产 品 的 规 格 要 求 、 单 价 和 原 料 的 供 应 量 、 单 价 如下 表 。 该 厂 应 如 何 安 排 生 产 ， 能 使 利 润 最 大 ？产 品 名 规 格 要 求 单 价A 原 料 C 不 少 于 50% 原 料 P 不 超 过 25% 50 元 /KGB 原 料 C 不 少 于 25%原 料 P 不 超 过 50% 35 元 /KGD 不 限 25 元 /KG 配 料 问 题 根 据 产 品 要 求 有 ： AC0.5A, AP0.25A BC0.25B, BP0.5B AC+AP+AH =A BC+BP+BH =B根 据 原 料 供 应 量 有 ： AC+BC+DC100 AP+BP+DP100 AH +BH +DH 60 设 AC,AP,DH 分 别 为 x1,x2,x9， 有Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x10.5(x1+ x2+ x3) x2 0.25(x1+ x2+ x3) x4 0.25(x4+ x5+ x6) x5 0.5(x4+ x5+ x6) x1+ x4+ x7100 x 2+ x5+ x8100 x3+ x6+ x960 xj0, j=1,2,3,4,5,6,7,8,9 解 ： 记 产 品 A、 B、 D中 C、 P、 H的 含 量 分 别 为 ： AC、AP、 AH 、 BC、 BP、 BH 、 DC、 DP、 DH 。 例 某 单 位 有 资 金 10万 元 ， 在 今 后 5年 内 可 考 虑 下 列 投 资 项 目 ，已 知 ： 项 目 A： 从 第 1到 第 4年 每 年 初 可 投 资 ， 并 于 次 年 末 回 收 本 利115%； 项 目 B： 第 3年 初 需 要 投 资 ， 到 第 5年 末 回 收 本 利 125%， 但 最大 投 资 额 不 超 过 4万 元 ； 项 目 C： 第 2年 初 需 要 投 资 ， 到 第 5年 末 能 回 收 本 利 140%， 但最 大 投 资 额 不 超 过 3万 元 ； 项 目 D： 5年 内 每 年 初 可 购 买 公 債 ， 当 年 末 回 收 本 利 106%。 问 它 应 该 如 何 安 排 每 年 的 投 资 ， 使 到 5年 末 拥 有 的 资 金 最 多 ？投 资 计 划 x2A+x2C+x2D=1.06x1D解 ： 每 年 的 投 资 额 应 不 超 过 手 中 的 资 金 。 由 于 项 目 D每年 都 可 投 资 ， 且 当 年 末 就 可 收 回 。 所 以 该 单 位 每 年 必然 把 资 金 全 部 投 出 去 ， 即 投 资 额 等 于 手 中 的 资 金 数 。设 第 i年 投 资 各 项 目 的 资 金 为 xiA、 xib、 xiC、 xiD ， 数 学模 型 为 ： Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2Dx4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4DxiA,xib,xiC,xiD0 例 某 昼 夜 服 务 的 公 交 线 路 每 天 各 时 间 段 内 所 需 司 机 和 乘 务 人员 数 如 下 ： 设 司 机 和 乘 务 人 员 分 别 在 各 时 间 段 一 开 始 时 上 班 ， 并 连 续工 作 八 小 时 ， 问 该 公 交 线 路 怎 样 安 排 司 机 和 乘 务 人 员 ， 既 能满 足 工 作 需 要 ， 又 配 备 最 少 司 机 和 乘 务 人 员 ?人力资源分配的问题 解 ： 设 xi 表 示 第 i班 次 时 开 始 上 班 的 司 机 和 乘 务 人员 数 ,这 样 我 们 建 立 如 下 的 数 学 模 型 。目 标 函 数 ： Min x1 + x2 + x3 + x4 + x5 + x6 约 束 条 件 ： s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x 1,x2,x3,x4,x5,x6 0 例 ： 明 兴 公 司 生 产 甲 、 乙 、 丙 三 种 产 品 ， 都 需 要 经 过 铸 造 、机 加 工 和 装 配 三 个 车 间 。 甲 、 乙 两 种 产 品 的 铸 件 可 以 外 包 协 作 ，亦 可 以 自 行 生 产 ， 但 产 品 丙 必 须 本 厂 铸 造 才 能 保 证 质 量 。 数 据如 下 表 。 问 ： 公 司 为 了 获 得 最 大 利 润 ， 甲 、 乙 、 丙 三 种 产 品 各生 产 多 少 件 ？ 甲 、 乙 两 种 产 品 的 铸 造 中 ， 由 本 公 司 铸 造 和 由 外包 协 作 各 应 多 少 件 ？生产计划 解 ： 设 x1,x2,x3 分 别 为 三 道 工 序 都 由 本 公 司 加 工 的 甲 、 乙 、 丙三 种 产 品 的 件 数 ， x4,x5 分 别 为 由 外 协 铸 造 再 由 本 公 司 机 加工 和 装 配 的 甲 、 乙 两 种 产 品 的 件 数 。 求 xi 的 利 润 ： 利 润 = 售 价 - 各 成 本 之 和可 得 到 xi（ i=1,2,3,4,5） 的 利 润 分 别 为 15、 10、 7、 13、 9元 。这 样 我 们 建 立 如 下 的 数 学 模 型 。目 标 函 数 ： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 约 束 条 件 ： s.t. 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x 1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0 练 习 ： 某 厂 生 产 、 、 三 种 产 品 ， 均 要 经 过 A、 B 两 道 工 序加 工 。 假 设 有 两 种 规 格 的 设 备 A1、 A2能 完 成 A 工 序 ； 有 三 种规 格 的 设 备 B1、 B2、 B3能 完 成 B 工 序 。 可 在 A、 B的 任 何 规格 的 设 备 上 加 工 ； 可 在 任 意 规 格 的 A设 备 上 加 工 ， 但 对 B工序 ， 只 能 在 B1设 备 上 加 工 ； 只 能 在 A2与 B2设 备 上 加 工 ； 数 据如 下 表 。 问 ： 为 使 该 厂 获 得 最 大 利 润 ， 应 如 何 制 定 产 品 加 工方 案 ？ 解 ： 设 xijk 表 示 第 i 种 产 品 ， 在 第 j 种 工 序 上 的 第 k 种 设 备 上 加 工 的数 量 。 利 润 = （ 销 售 单 价 - 原 料 单 价 ） * 产 品 件 数 之 和 - （ 每 台 时 的 设备 费 用 *设 备 实 际 使 用 的 总 台 时 数 ） 之 和 。 这 样 我 们 建 立 如 下 的 数 学 模 型 : Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t. 5x111 + 10 x211 6000 （ 设 备 A1 ） 7x112 + 9x212 + 12x312 10000 （ 设 备 A2 ） 6x 121 + 8x221 4000 （ 设 备 B1 ） 4x122 + 11x322 7000 （ 设 备 B2 ） 7x123 4000 （ 设 备 B3 ） x111+ x112- x121- x122- x123 = 0 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） x211+ x212- x221 = 0 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） x312 - x322 = 0 （ 产 品 在 A、 B工 序 加 工 的 数 量 相 等 ） xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,3 某 名 牌 饮 料 在 国 内 有 三 个 生 产 厂 ， 分 布 在 城 市 A1、 A2、 A3,其 一 级 承 销 商 有 4个 ， 分 布 在 城 市 B1、 B2、 B3、 B4， 已 知各 厂 的 产 量 、 各 承 销 商 的 销 售 量 及 从 Ai到 Bj的 每 吨 饮 料 运费 为 Cij， 为 发 挥 集 团 优 势 ， 公 司 要 统 一 筹 划 运 销 问 题 ， 求运 费 最 小 的 调 运 方 案 。 销 地产 地 B1 B2 B3 B4 产 量A1A 2A3 6 3 2 5 7 5 8 4 3 2 9 7 523销 量 2 3 1 4 解 ： 设 从 Ai到 Bj的 运 输 量 为 xij，minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 ： 产 量 之 和 等 于 销 量 之 和 ,故 要 满 足 ： 供 应 平 衡 条 件 x11+x12+x13+x14=5x21+x22+x23+x24=2x 31+x32+x33+x34 =3 销 售 平 衡 条 件 x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4 xij0 (i=1,2,3； j=1,2,3,4)