线性规划问题的对偶问题

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

1、2、 线 性 规 划 问 题 的 对 偶 问 题 2.1 对 偶 问 题 设 备 能 力设 备 A 2h 2h 12h设 备 B 4h 0h 16h设 备 C 0h 5h 15h单 位 利 润 （ 元 ） 2 3问 该 企 业 因 安 排 生 产 两 种 产 品 各 多 少 件 ， 使 总 的利 润 收 入 为 最 大 ？ 现 某 机 械 厂 为 扩 大 生 产 租 借 常 山 机 器 厂拥 有 的 设 备 资 源 ， 问 常 山 厂 分 别 以 每 小 时什 么 样 的 价 格 才 愿 意 出 租 自 己 的 设 备 ？ 设 常 山 厂 将 设 备 A、 B、 C每 h的 出 租价 格 为

2、y1,y2,y3; 它 的 对 偶 问 题 为 min w=12y1+16y2+15y3 2y1+4y2 2 2y1 +5y3 3 y1,y2,y3 0 把 例 2.2用 矩 阵 表 示 ： 对 偶 问 题 原 问 题 : Max z=(2,3) 21xx 0 xx 151612xx50 04 22 21 21 321yyy151612min 0yyy 32yyy502 042 321 321 综 上 所 述 其 变 换 形 式 如 下 ：原 问 题 （ 或 对 偶 问 题 ） 对 偶 问 题 （ 或 原 问 题 ）目 标 函 数 max 目 标 函 数 min约束条件 m个 m个 变量 0

3、0= 无 约 束变量 n个 n个 约束条件 0 0 无 约 束 =约 束 条 件 右 端 项 目 标 函 数 变 量 的 系 数 目 标 函 数 变 量 的 系 数 约 束 条 件 右 端 项 例 2-7： 写 出 下 列 线 性 规 划 的 对 偶 问 题 min z=7x1+4x2-3x3s.t. -4x1+2x2-6x3 24 -3x1-6x2-4x3 15 5x2+3x3=30 x1 0,x2取 值 无 约 束 ,x3 0 Max w=24y1+15y2+30y3s.t. -4y1-3y2 7 2y1-6y2+5y3=4 -6y1-4y2+3y3 -3 y1 0,y2 0,y3无 约

4、束 性 质 2.4 如 果 原 问 题 (对 偶 问 题 ） 具 有 无界 解 ， 则 其 对 偶 问 题 （ 原 问 题 ） 无可 行 解 。 但 原 问 题 (对 偶 问 题 )无 可 行 解 时 ，其 对 偶 问 题 （ 原 问 题 ） 或 无 可 行 解或 具 有 无 界 解 。 定 理 2.5（ 互 补 松 弛 性 ） 在 线 性 规 划 问 题 的 最 优 解 中 ， 如果 该 约 束 条 件 取 严 格 等 式 ， 则 对 应某 一 约 束 条 件 的 对 偶 变 量 值 为 非 零 ；反 之 如 果 约 束 条 件 取 严 格 不 等 式 ，则 其 对 应 的 对 偶 变 量

5、一 定 为 零 。 它 的 最 优 解 为 （ 3， 3）而 对 于 第 二 个 约 束 条 件 ， 为 严格 的 不 等 式 ， 所 以 y2=0y1y2y3 性 质 2.6线 性 规 划 的 原 问 题 与 对 偶 问 题 中 ，原 问 题 的 松 弛 变 量 对 应 对 偶 问 题 的 变量 ， 对 偶 问 题 的 剩 余 变 量 对 于 原 问 题的 变 量 。 ） 例 ：C 基 b x x x x x 2 x 3 0 x 4 3 x 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5C j-zj 0 0 -1 0 -1/5原 问 题 变 量 原 问 题 松 弛

6、 变 量对 偶 问 题 变 量对 偶 问 题 的 剩 余 变 量 YYY Y Y 2.3 影 子 价 格在 线 性 规 划 原 问 题 和 对 偶 问 题 中 ： m1i iin1j jj ybxczbi代 表 第 i种 资 源 的 拥 有 量 ， 而 yi代 表 对一 个 单 位 第 i种 资 源 的 估 价 影 子 价 格 不 是 市 场 价 格 ， 随 企 业 的 生 产 任务 和 产 品 结 构 而 发 生 变 化 。 影 子 价 格 是 一 种 边 际 价 格 。 Z= bTy*=b1y1*+b2y2*+bmym* 可 知 Z / bi = yi* 2X+2y=121 2 3 4 5

7、 6654321 X=4 X=3 点 （ 3， 3） 是 最 优 解 ，z*=15当 A的 资 源 变 为 13小时 ， z*=16,说 明 A的 边际 价 格 是 1， 即 影 子 价格 是 1。 在 对 偶 问 题 的 互 补 松 弛 性 质 中 有 0ybxa iijn 1j ij ， 时表 示 某 种 资 源 bi没 有 充 分 利 用 ， 该 种资 源 的 影 子 价 格 为 零 。 如 果 ijn1j iji bxa0y 时 ，表 示 该 种 资 源 已 耗 费 完 毕 。 是 生 产 该 种 产 品 所 消 耗 的 各 项 资 源 的影 子 价 格 总 和 ， 即 产 品 的 隐

8、 含 成 本 。 从 影 子 价 格 的 含 义 上 再 来 考 察 单 纯 形 法 的 计算 ： im 1i ijjjj yaczc im1i ijya当 检 验 数 大 于 零 ， 说 明 生 产 此 种 产 品 有利 ， 可 在 生 产 中 安 排 。 2.4 对 偶 单 纯 形 法例 ： 求 解 如 下 线 性 规 划 问 题 ： min w=12y1+16y2+15y3 s.t. 2y1+4y2 2 2y1+ 5y3 3 y1,y2,y3 0 划 为 标 准 形 ： max w=-12y 1-16y2-15y3 -2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 yi

9、 0（ i=1,5) Cj -12 -16 -15 0 0CB 基 b Y1 y2 y3 y4 y50 y4 -20 y5 -3 -2 -4 0 1 0-2 0 -5 0 1Cj-Zj -12 -16 -15 0 0 如 何 转 换 ? 当 bi 0时 ， 令 min(bi)所 对 应 的 行 中 的Xr为 换 出 基 变 量 。 令 0a|a zcmin rjrj jjj所 对 应 的 列 变 量 为 换 入 基 变 量 Y5为 换 出 基 变 量 515,2-12min故 x3为 换 入 基 变 量 ， -5为 主 元 素Cj -12 -16 -15 0 0CB 基 b Y1 y2 y3

10、y4 y50 y4 -2-15 y 3 3/5 -2 -4 0 1 02/5 0 1 0 -1/5Cj-Zj -6 -16 0 0 -3 Y4为 换 出 基 变 量 416,2- 6min故 Y1为 换 入 基 变 量 ， -2为 主 元 素Cj -12 -16 -15 0 0CB 基 b Y1 y2 y3 y4 y5-12 y1 1-15 y3 1/5 1 2 0 -1/2 0 0 -4/5 1 1/5 -1/5C j-Zj 0 -4 0 -3 -3故 此 问 题 的 最 优 解 为 ： Y1=1， Y2=0，Y3=1/5， W=15 对 偶 单 纯 形 法 的 基 本 思 想 对 偶 单

11、纯 形 法 的 基 本 思 想 是 ： 从 原 规 划 的 一个 基 解 出 发 ， 此 基 解 不 一 定 可 行 ， 但 它 对 应 着 一个 对 偶 可 行 解 （ 检 验 数 非 正 ） ； 从 对 偶 可 行 解 出发 ， 然 后 检 验 原 规 划 的 基 本 解 是 否 可 行 ， 即 是 否有 负 的 分 量 ， 如 果 有 小 于 零 的 分 量 ， 则 进 行 迭 代 ，求 另 一 个 基 解 ， 此 基 解 对 应 着 另 一 个 对 偶 可 行 解（ 检 验 数 非 正 ） 。 如 果 得 到 的 基 解 的 分 量 皆 非 负 则 该 基 解 为 最优 解 。 也 就

12、 是 说 ， 对 偶 单 纯 形 法 在 迭 代 过 程 中 始终 保 持 对 偶 解 的 可 行 性 （ 即 检 验 数 非 正 ） ， 使 原规 划 的 基 解 由 不 可 行 逐 步 变 为 可 行 对 偶 单 纯 形 法 在 什 么 情 况 下 使 用 ： 应 用 前 提 ： 有 一 个 基 ， 其 对 应 的 基 满 足 : 单 纯 形 表 的 检 验 数 行 全 部 非 正 （ 对偶 可 行 ） ； 变 量 取 值 可 有 负 数 （ 非 可 行 解 ） 。 注 ： 通 过 矩 阵 行 变 换 运 算 ， 使 所 有 相 应变 量 取 值 均 为 非 负 数 即 得 到 最 优 单

13、 纯 形 表 。 对 偶 单 纯 形 法 求 解 线 性 规 划 问 题 过 程 ： 1.建 立 初 始 对 偶 单 纯 形 表 ,对 应 一 个基 本 解 ,所 有 检 验 数 均 非 正 ,转 2； 2.若 b 0,则 得 到 最 优 解 ,停 止 ;否则 ,若 有 bk0则 选 k行 的 基 变 量 为 出 基 变 量 ,转 3 3.若 所 有 akj 0( j = 1,2,n )，则 原 问 题 无 可 行 解 ,停 止 ;否 则 ,若 有 akj 0 则 选 =minj / akj akj 0=r /akr那 么 x r为 进 基 变 量 ,转 4； 4.以 akr 为 转 轴 元

14、,作 矩 阵 行 变 换 使其 变 为 1,该 列 其 他 元 变 为 0,转 2。 对 偶 单 纯 形 法 解 的 讨 论 if br0,而 arj0,这 时 原 问 题 解 的 情 况 如何 ？ rnrn1m1m,rr bxaxax 故 不 可 能 存 在 xj0（ j=1,n） 的 解 ，故 原 问 题 无 可 形 解 ， 这 时 对 偶 问 题 的 目标 函 数 值 无 界 。 )3.2.1(0 145 1232 1022 15129min 321 321 321 321jx xxx xxx xxx xxxZj 例 题 :用 对 偶 单 纯 形 法 求 解 解 :将 上 述 模 型 转

15、 化 为 0 145 1232 1022 15129max 61 6321 5321 4321 321x xxxx xxxx xxxx xxxZ Cj -9 -12 -15 0 0 0CB 基 b X1 x2 x3 x4 x5 x6 0 x4 -10 0 x5 -12 0 x6 -14 -2 -2 -1 1 0 0-2 -3 -1 0 1 0-1 -1 -5 0 0 1 Cj-zj -9 -12 -15 0 0 0 =min(-9/-1,-12/-1,-15/-5)=3 Cj -9 -12 -15 0 0 0CB 基 b X1 x2 x3 x4 x5 x6 0 x4 -36/5 0 x5 -4

16、6/5 -15 x3 14/5 -9/5 -9/5 0 1 0 -1/5-9/5 -14/5 0 0 1 -1/51/5 1/5 1 0 0 -1/5 Cj-zj -6 -9 0 0 0 -3 =min(6*5/9,9*5/14,15)=45/14 Cj -9 -12 -15 0 0 0CB 基 b X1 x2 x3 x4 x5 x6 0 x4 -9/7 -12 x2 23/7 -15 x3 15/7 -9/14 0 0 1 -9/14 -1/149/14 1 0 0 -5/14 1/141/14 0 1 0 1/14 -3/14 Cj-zj -3/14 0 0 0 -45/14 -33/14 =min(1/3,5,33)=1/3 Cj -9 -12 -15 0 0 0CB 基 b X1 x2 x3 x4 x5 x6-9 x1 2 -12 x2 2 -15 x3 2 1 0 0 -14/9 1 1/90 1 0 1 -1 00 0 1 1/9 0 -2/9 Cj-zj 0 0 0 -1/3 -3 -7/3 所 以 ， X*=（ 2 . 2 . 2 . 0 . 0 . 0） Z* = 72， 原 问 题 Z* =72 其 对 偶 问 题 的 最 优 解 为 ： Y*= (1/3 . 3 . 7/3)， W*= 72