线性规划问题的对偶与灵敏度分析

《线性规划问题的对偶与灵敏度分析》由会员分享，可在线阅读，更多相关《线性规划问题的对偶与灵敏度分析（52页珍藏版）》请在装配图网上搜索。

1、第 二 章 线 性 规 划 问 题 的 对 偶 与灵 敏 度 分 析w线 性 规 划 的 对 偶 问 题 概 念 、理 论 及 经 济 意 义w线 性 规 划 的 对 偶 单 纯 形 法w线 性 规 划 的 灵 敏 度 分 析本 章 内 容 重 点 1.线 性 规 划 对 偶 问 题 对 偶 原 理 对 偶 问 题 定 义 线 性 规 划问 题 写 出 其 对 偶 问 题 ， 要 掌 握 在对 称 形 式 和 非 对 称 情 况 下 由 原 问题 写 出 对 偶 问 题 的 方 法 。 对 偶 定 理 只 需 了 解 原 问题 与 对 偶 问 题 解 的 关 系 ， 证 明 从略 。 1.对

2、偶 问 题 ： 若 第 二 章 例 2.1问 题 的 设 备 都 用 于外 协 加 工 ， 工 厂 收 取 加 工 费 。 试 问 ： 设备 A、 B、 C 每 工 时 各 如 何 收 费 才 最 有竞 争 力 ？ 设 y1 ， y2 ， y3 分 别 为 每 工 时 设 备 A、 B、 C 的 收 取 费 用 。1.线 性 规 划 对 偶 问 题 线 性 规 划 原 问 题 例 2.1:某 工 厂 拥 有 A、 B、 C三 种 类 型 的设 备 ， 生 产 甲 、 乙 两 种 产 品 。 每 件 产 品 在生 产 中 需 要 占 用 的 设 备 机 时 数 ， 每 件 产 品可 以 获 得

3、的 利 润 以 及 三 种 设 备 可 利 用 的 时数 如 下 表 所 示 。 求 获 最 大 利 润 的 方 案 。 产 品 甲 产 品 乙 设 备 能 力（ h）设 备 A 3 2 65设 备 B 2 1 40设 备 C 0 3 75利 润 （ 元 /件 ） 1500 2500 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原 问 题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （ 不 少 于 甲 产 品 的 利 润 ） 2y1+y2+3y3 25

4、00 对 偶 问 题 （ 不 少 于 乙 产 品 的 利 润 ） y 1, y2 , y3 0 1.线 性 规 划 对 偶 问 题 2、 对 偶 定 义 对 称 形 式 ： 互 为 对 偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”1.线 性 规 划 对 偶 问 题 一 对 对 称 形 式 的 对 偶 规 划 之 间 具 有下 面 的 对 应 关 系 。 (1)若 一 个 模 型 为 目 标 求 “ 极 大 ” ，约 束 为 “ 小 于 等 于 ” 的 不 等 式 ， 则

5、它 的对 偶 模 型 为 目 标 求 “ 极 小 ” ， 约 束 是“ 大 于 等 于 ” 的 不 等 式 。 即 “ max， ”和 “ min， ” 相 对 应 。1.线 性 规 划 对 偶 问 题 (2)从 约 束 系 数 矩 阵 看 ： 一 个 模 型 中为 ， 则 另 一 个 模 型 中 为 AT。 一 个 模 型是 m个 约 束 ， n个 变 量 ， 则 它 的 对 偶 模 型为 n个 约 束 ， m个 变 量 。 (3)从 数 据 b、 C的 位 置 看 ： 在 两 个 规划 模 型 中 ， b和 C的 位 置 对 换 。 (4)两 个 规 划 模 型 中 的 变 量 皆 非 负

6、 。1.线 性 规 划 对 偶 问 题 非 对 称 形 式 的 对 偶 规 划 一 般 称 不 具 有 对 称 形 式 的 一 对 线 性 规 划 为非 对 称 形 式 的 对 偶 规 划 。 对 于 非 对 称 形 式 的 规 划 ， 可 以 按 照 下 面 的 对 应 关 系 直 接 给 出 其 对 偶 规 划 。 （ 1） 将 模 型 统 一 为 “ max， ” 或 “ min， ” 的 形 式 ， 对 于 其 中 的 等 式 约 束 按 下 面（ 2） 、 （ 3） 中 的 方 法 处 理 ； （ 2） 若 原 规 划 的 某 个 约 束 条 件 为 等 式 约 束 ，则 在 对 偶

7、 规 划 中 与 此 约 束 对 应 的 那 个 变 量 取 值没 有 非 负 限 制 ；1.线 性 规 划 对 偶 问 题 （ 3） 若 原 规 划 的 某 个 变 量 的 值 没 有 非 负 限 制 ， 则 在 对 偶 问 题 中 与 此 变 量 对 应 的 那 个 约 束 为 等 式 。 下 面 对 关 系 （ 2） 作 一 说 明 。 对 于 关 系 （ 3） 可 以 给 出 类 似 的 解 释 。 设 原 规 划 中 第 一 个 约 束 为 等 式 ： a11x1 + + a1nxn = b1 那 么 ， 这 个 等 式 与 下 面 两 个 不 等 式 等 价1.线 性 规 划 对

8、偶 问 题 1.线 性 规 划 对 偶 问 题11111 11111 . bxaxa bxaxa nn nn 这 样 ， 原 规 划 模 型 可 以 写 成 mjx bxaxa bxaxa bxaxa xcxcZj mnmnm nn nn nn,2,1,0max 11 11111 11111 11 1.线 性 规 划 对 偶 问 题 此 时 已 转 化 为 对 称 形 式 ， 直 接 写 出 对 偶 规 划 没 有 非 负 限 制 1211 1111 22112112 11111111 221111 ,0, min yyyyy cyayaya cyayaya cyayaya ybybybybf

9、 m nmmnnn mm mm mm 这 里 ， 把 y1 看 作 是 y1 = y1 - y1 ，于 是 y1 没 有 非 负 限 制 ， 关 系 （ 2） 的 说 明完 毕 。 1.线 性 规 划 对 偶 问 题 例 3.1 写 出 下 面 线 性 规 划 的 对 偶 规 划模 型解 先 将 约 束 条 件 变 形 为 “ ” 形 式 没 有 非 负 限 制 3214 321 431 4321 4321 ,0,105 30422 60272 2523 75max xxxx xxx xxx xxxx xxxxZ 1.线 性 规 划 对 偶 问 题 没 有 非 负 限 制 4321 44321

10、 431 4321 ,0,0 51030422 60272 2523 xxxx xxxxx xxx xxxx 再 根 据 非 对 称 形 式 的 对 应关 系 ， 直 接 写 出 对 偶 规 划 1.线 性 规 划 对 偶 问 题 0, 72 5472 123 122 510306025min 54321 5421 321 31 321 54321 yyyyy yyyy yyy yy yyy yyyyyf没 有 非 负 限 制 3.对 偶 定 理(原 问 题 与 对 偶 问 题 解 的 关 系 ）考 虑 （ LP） 和 （ DP） 定 理 3-1 (弱 对 偶 定 理 ） 若 x, y 分 别

11、 为 （ LP) 和 （ DP）的 可 行 解 ， 那 么 cTx bTy。 推 论 若 （ LP） 可 行 ， 那 么 （ LP）无 有 限 最 优 解 的 充 分 必 要 条 件 是 （ LD）无 可 行 解 。1.线 性 规 划 对 偶 问 题 定 理 3-2 (最 优 性 准 则 定 理 ) 若 x,y分 别 (LP),(DP)的 可 行 解 ,且cTx=bTy ， 那 么 x,y分 别 为 (LP)和 (DP)的 最 优 解 。 定 理 3-3 (主 对 偶 定 理 ) 若 (LP)和 (DP)均 可 行 那 么 (LP)和(DP)均 有 最 优 解 ,且 最 优 值 相 等 。 以

12、 上 定 理 、 推 论 对 任 意 形 式 的 相应 性 规 划 的 对 偶 均 有 效1.线 性 规 划 对 偶 问 题 4.影 子 价 格 是 一 个 向 量 ， 它的 分 量 表 示 最 优 目 标 值 随 相 应 资 源 数 量变 化 的 变 化 率 。 若 x*,y* 分 别 为 （ LP） 和 （ DP） 的 最 优 解 ， 那 么 ， cT x* = bT y* 。 根 据 f = bTy*=b1y1*+b2y2*+bmym* 可 知 f / bi = yi* yi* 表 示 bi 变 化 1个 单 位 对 目 标 f 产 生的 影 响 ， 称 yi* 为 bi的 影 子 价

13、格 。 注 意 ： 若 B 是 最 优 基 ， y* = (BT)-1 cB 为 影 子 价 格 向 量 。1.线 性 规 划 对 偶 问 题 影 子 价 格 的 经 济 含 义 (1)影 子 价 格 是 对 现 有 资 源 实 现 最大 效 益 时 的 一 种 估 价 企 业 可 以 根 据 现 有 资 源 的 影 子 价格 ， 对 资 源 的 使 用 有 两 种 考 虑 ： 第 一 ，是 否 将 设 备 用 于 外 加 工 或 出 租 ， 若 租费 高 于 某 设 备 的 影 子 价 格 ， 可 考 虑 出租 该 设 备 ， 否 则 不 宜 出 租 。 第 二 ， 是否 将 投 资 用 于

14、 购 买 设 备 ， 以 扩 大 生 产能 力 ， 若 市 价 低 于 某 设 备 的 影 子 价 格 ，可 考 虑 买 进 该 设 备 ， 否 则 不 宜 买 进 。1.线 性 规 划 对 偶 问 题 1.线 性 规 划 对 偶 问 题 （ 2） 影 子 价 格 表 明 资 源 增 加 对 总 效 益产 生 的 影 响 。 根 据 推 论 “ 设 x0和 y0分 别 为 原规 划 （ P） 和 对 偶 规 划 （ D） 的 可 行 解 ， 当cx0=bTy0时 ， x0、 y0分 别 是 两 个 问 题 的 最 优解 ” 可 知 ， 在 最 优 解 的 情 况 下 ， 有 关 系 因 此 ，

15、 可 以 将 z*看 作 是 bi,i=1,2， ,m的函 数 ， 对 bi求 偏 导 数 可 得 到 这 说 明 ， 如 果 右 端 常 数 增 加 一 个 单 位 ， 则 目标 函 数 值 的 增 量 将 是 * 22*11* mmybybybfZ miybZ ii ,2,1,* miy i ,2,1,* 影 子 价 格 反 映 了 不 同 的 局 部 或 个体 的 增 量 可 以 获 得 不 同 的 整 体 经 济 效益 。 如 果 为 了 扩 大 生 产 能 力 ， 考 虑 增加 设 备 ， 就 应 该 从 影 子 价 格 高 的 设 备入 手 。 这 样 可 以 用 较 少 的 局

16、部 努 力 ，获 得 较 大 的 整 体 效 益 。1.线 性 规 划 对 偶 问 题 需 要 指 出 ， 影 子 价 格 不 是 固 定 不 变的 ， 当 约 束 条 件 、 产 品 利 润 等 发 生 变 化时 ， 有 可 能 使 影 子 价 格 发 生 变 化 。 另 外 ，影 子 价 格 的 经 济 含 义 （ 2） ， 是 指 资 源 在一 定 范 围 内 增 加 时 的 情 况 ， 当 某 种 资 源的 增 加 超 过 了 这 个 “ 一 定 的 范 围 ” 时 ，总 利 润 的 增 加 量 则 不 是 按 照 影 子 价 格 给出 的 数 值 线 性 地 增 加 。 这 个 问

17、题 还 将 在灵 敏 度 分 析 一 节 中 讨 论 。1.线 性 规 划 对 偶 问 题 5.由 最 优 单 纯 形 表 求 对 偶 问 题 最优 解 标 准 形 式 ： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.线 性 规 划 对 偶 问 题 50 100 0 0 0CB XB x1 x2 x3 x4 x5 i0 x 3 300 1 1 1 0 0 3000 x4 400 2 1 0 1 0 4000 x 5 250 0 (1)

18、 0 0 1 250-z 0 50 100* 0 0 00 x 3 50 (1) 0 1 0 -1 500 x4 150 2 0 0 1 -1 75100 x 2 250 0 1 0 0 1-z -25000 50* 0 0 0 -10050 x 1 50 1 0 1 0 -10 x4 50 0 0 -2 1 1100 x 2 250 0 1 0 0 1-z -27500 0 0 -50 0 -50 -cBTB-1 IB=(p1, p4,p2 ) oTB-1最 优 解 x 1 = 50 x2 = 250 x4 = 50影 子 价 格 y1 = 50 y2 = 0 y3 = 50 , B-1对

19、应 的 检 验 数 T = cBTB-1 。 1.线 性 规 划 对 偶 问 题 对 偶 单 纯 形 法 的 基 本 思 想 对 偶 单 纯 形 法 的 基 本 思 想 是 ：从 原 规 划 的 一 个 基 本 解 出 发 ， 此 基 本解 不 一 定 可 行 ， 但 它 对 应 着 一 个 对 偶可 行 解 （ 检 验 数 非 正 ） ， 所 以 也 可 以说 是 从 一 个 对 偶 可 行 解 出 发 ； 然 后 检验 原 规 划 的 基 本 解 是 否 可 行 ， 即 是 否有 负 的 分 量 ， 如 果 有 小 于 零 的 分 量 ，则 进 行 迭 代 ， 求 另 一 个 基 本 解

20、， 此 基本 解 对 应 着 另 一 个 对 偶 可 行 解 （ 检 验数 非 正 ） 。2.对 偶 单 纯 形 法 如 果 得 到 的 基 本 解 的 分 量 皆非 负 则 该 基 本 解 为 最 优 解 。 也 就是 说 ， 对 偶 单 纯 形 法 在 迭 代 过 程中 始 终 保 持 对 偶 解 的 可 行 性 （ 即检 验 数 非 正 ） ， 使 原 规 划 的 基 本解 由 不 可 行 逐 步 变 为 可 行 ， 当 同时 得 到 对 偶 规 划 与 原 规 划 的 可 行 解 时 ， 便 得 到 原 规 划 的 最 优 解 。2.对 偶 单 纯 形 法 对 偶 单 纯 形 法 在

21、什 么 情 况 下 使 用 ： 应 用 前 提 ： 有 一 个 基 ， 其 对 应 的 基 满足 : 单 纯 形 表 的 检 验 数 行 全 部 非 正 （ 对偶 可 行 ） ； 变 量 取 值 可 有 负 数 （ 非 可 行 解 ） 。 注 ： 通 过 矩 阵 行 变 换 运 算 ， 使 所 有 相应 变 量 取 值 均 为 非 负 数 即 得 到 最 优 单 纯 形表 。2.对 偶 单 纯 形 法 w 1.建 立 初 始 对 偶 单 纯 形 表 ,对 应 一 个 基 本 解 ,所 有 检 验 数 均 非 正 ,转 2； 2.若 b 0,则 得 到 最 优 解 ,停 止 ;否 则 ,若 有b

22、k0则 选 k行 的 基 变 量 为 出 基 变 量 ,转 3 3.若 所 有 akj 0( j = 1,2, ,n )， 则 原问 题 无 可 行 解 ,停 止 ;否 则 ,若 有 akj 0 则 选 =minj / akj akj 0=r /akr 那 么 xr为 进 基 变 量 ,转 4； 4.以 akr 为 转 轴 元 ,作 矩 阵 行 变 换 使 其 变 为 1,该 列 其 他 元 变 为 0,转 2。 对 偶 单 纯 形 法 求 解 线 性 规 划 问 题过 程 ：2.对 偶 单 纯 形 法 例 3.2： 求 解 线 性 规 划 问 题 ： 标 准 化 ： Max z = - 2x

23、1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x 1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.对 偶 单 纯 形 法 w表 格 对 偶 单 纯 形 法CI -2 -3 -4 0 0C B XB b X1 X2 X3 X4 X50 X4 -3 -1 -2 -1 1 00 X 5 -4 -2 1 -3 0 1 j -2 -3 -4 0 00 X 4 -1 0 -5/2 1/2 1 -1/2-2

24、 X1 2 1 -1/2 3/2 0 -1/2 j 0 -4 -1 0 -1-3 X2 2/5 0 1 -1/5 -2/5 1/5-2 X 1 11/5 1 0 7/5 -1/5 -2/5 j 0 0 -9/5 -8/5 -1/5 2.对 偶 单 纯 形 法 单 纯 形 法 和 对 偶 单 纯 形 法 步 骤是是 是是 否否 否否所 有 所 有得 到最 优 解计 算 计 算典 式 对 应 原 规 划 的基 本 解 是 可 行 的 典 式 对 应 原 规 划 的基 本 解 的 检 验 数所 有 所 有计 算计 算以 为 中 心 元 素 进 行 迭 代 以 为 中 心 元 素 进 行 迭 代停没有

25、最优解 没有最优解 单 纯 形 法 对 偶 单 纯 形 法0j 0ib 0max jjk 0min iie bbb0ika 0ljaekeikiki abaab 0min ekkejeji aaa 0min 0 cs Minj/asjasj0 brMin-bi/airair03.灵 敏 度 分 析 例 3.5: 上 例 最 优 单 纯 形 表 如 下 C i 2 3 0 0 0 CB X B B X 1 X 2 X 3 X 4 X 5 2 X 1 4 1 0 0 1/4 0 0 X 5 4 0 0 -2 1/2 1 3 X 2 2 0 1 1/2 -1/8 0 j 0 0 -1.5 -1/8

26、0 3.灵 敏 度 分 析 0 0.25 0 这 里 B-1 = -2 0.5 1 0.5 -0.125 0 各 列 分 别 对 应 b1、 b2、 b3 的 单 一 变 化因 此 ， 设 b1 增 加 4， 则 x1 ,x5 ,x2分 别 变 为 ：4+0 4=4, 4+(-2) 4=-40, 2+0.5 4=4用 对 偶 单 纯 形 法 进 一 步 求 解 ， 可 得 ：x* = ( 4, 3, 2, 0, 0 )T f* = 173.灵 敏 度 分 析 增 加 一 个 变 量 增 加 变 量 xn+1 则 有 相 应 的pn+1 ,cn+1 。 那 么 计 算 出 B-1pn+1 , n

27、+1=cn+1- cri ari n+1 填 入 最 优 单 纯 形 表 , 若 n+1 0 则 最 优 解 不 变 ； 否 则 ， 进 一 步 用 单 纯 形 法 求 解 。3.灵 敏 度 分 析 例 3.6:例 3.4增 加 x6 , p6=( 2, 6, 3 )T, c6=5 计 算 得 到 Ci 2 3 0 0 0 5CB XB b X1 X2 X3 X4 X5 X62 X 1 4 1 0 0 1/4 0 1.50 X5 4 0 0 -2 1/2 1 23 X 2 2 0 1 1/2 -1/8 0 0.25 j 0 0 -1.5 -1/8 0 1.25用 单 纯 形 法 进 一 步 求

28、 解 ， 可 得 ：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5 3.灵 敏 度 分 析 增 加 一 个 约 束 增 加 约 束 一 个 之 后 ， 应 把 最 优 解 带入 新 的 约 束 ， 若 满 足 则 最 优 解 不 变 ， 否 则填 入 最 优 单 纯 形 表 作 为 新 的 一 行 ， 引 入 一个 新 的 非 负 变 量 （ 原 约 束 若 是 小 于 等 于 形式 可 引 入 非 负 松 弛 变 量 ， 否 则 引 入 非 负 人工 变 量 ） ， 并 通 过 矩 阵 行 变 换 把 对 应 基 变量 的 元 素 变 为 0， 进 一 步 用 单 纯 形

29、 法 或 对偶 单 纯 形 法 求 解 。3.灵 敏 度 分 析 例 3.7:例 3.4增 加 3x1+ 2x2 15， 原 最 优 解 不满 足 这 个 约 束 。 于 是 Ci 2 3 0 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 2 X1 4 1 0 0 1/4 0 0 0 X5 4 0 0 -2 1/2 1 0 3 X2 2 0 1 1/2 -1/8 0 0 0 X6 -1 0 0 -1 -1/2 0 1 j 0 0 -1.5 -1/8 0 0 3.灵 敏 度 分 析经 对 偶 单 纯 形 法 一 步 ， 可 得 最 优 解 为 （ 3.5, 2.25, 0, 0, 3, 2 ) T， 最 优 值 为 13. 75 A中 元 素 发 生 变 化 (只 讨 论 N 中 某 一 列变 化 情 况 ） 与 增 加 变 量 xn+1 的 情 况 类 似 ， 假 设 pj 变 化 。 那 么 ， 重 新 计 算 出 B-1pj j = cj - cri ari j 填 入 最 优 单 纯 形 表 ， 若 j 0 则 最 优 解 不 变 ； 否 则 ， 进 一 步 用 单 纯 形 法 求 解 。（ 例 子 从 略 ）3.灵 敏 度 分 析