资源描述
运 筹 学 教 程第 二 章 线 性 规 划 的 对 偶 理 论 与 灵 敏 度 分 析 运 筹 学 教 程 运 筹 学 教 程 3 对 偶 理 论 是 线 性 规 划 中 最 重 要 的 理 论 之 一 ， 是 深 入 了解 线 性 规 划 问 题 结 构 的 重 要 理 论 基 础 。 同 时 ， 由 于 问题 提 出 本 身 所 具 有 的 经 济 意 义 ， 使 得 它 成 为 对 线 性 规划 问 题 系 统 进 行 经 济 分 析 和 敏 感 性 分 析 的 重 要 工 具 。那 么 ， 对 偶 问 题 是 怎 样 提 出 的 ， 为 什 么 会 产 生 这 样 一种 问 题 呢 ？ 运 筹 学 教 程线 性 规 划 的 对 偶 理 论引 例 俩 家 具 制 造 商 间 的 对 话 ：唉 !我 想 租 您 的 木 工 和 油 漆 工 一用 。 咋 样 ？ 价 格 嘛 好 说 ，肯 定 不 会 让 您 兄 弟 吃 亏 讪 。 王 老 板 做 家 具 赚 了 大 钱 ， 可 惜 我 老 李 有 高 科 技 产 品 ， 却 苦 于 没 有足 够 的 木 工 和 油 漆 工 咋 办 ？ 只 有 租 咯 。 H i： 王 老 板 ， 听 说近 来 家 具 生 意 很 好 ，也 帮 帮 兄 弟 我 哦 ! 家 具 生 意 还 真 赚 钱 ， 但 是 现 在 的 手 机 生 意 这 么 好 ， 不 如 干 脆 把 我 的 木 工 和 油 漆工 租 给 他 ， 又 能收 租 金 又 可 做 生 意 。 价 格 嘛 好 商 量 ， 好 商 量 。 只 是 . 家 具 -王 总 李 总 桌 子 椅 子 能 力木 工 4 3 120漆 工 2 1 50价 格 50 30 运 筹 学 教 程线 性 规 划 的 对 偶 理 论王 老 板 的 家 具 生 产 模 型 ：x1 、 x2是 桌 、 椅 生 产 量 。Z是 家 具 销 售 总 收 入 （ 总 利 润 ） 。max Z = 50 x 1 + 30 x2s.t. 4x1+3x2 120（ 木 工 ） 2x1+ x2 50 （ 油 漆 工 ） x1， x2 0原 始 线 性 规 划 问 题 ， 记 为 （ P） 王 老 板 的 资 源 出 租 模 型 ：y1、 y2单 位 木 、 漆 工 出 租 价 格 。W是 资 源 出 租 租 金 总 收 入 。min W =120y1 + 50y2s.t. 4y1+2y2 50 3y1+ y2 30 y1， y2 0对 偶 线 性 规 划 问 题 ， 记 为 （ D） 桌 子 椅 子 能 力木 工 4 3 120漆 工 2 1 50价 格 50 30 运 筹 学 教 程线 性 规 划 的 对 偶 理 论 王 老 板 按 （ D） 的 解 y1 、 y2出 租 其 拥 有 的 木 、 漆 工 资 源 ， 既 保 证 了 自己 不 吃 亏 （ 出 租 资 源 的 租 金 收 入 并 不 低 于 自 己 生 产 时 的 销 售 收 入 ） ， 又 使得 出 租 价 格 对 李 老 板 有 极 大 的 吸 引 力 （ 李 老 板 所 付 出 的 总 租 金 W最 少 ） 。 运 筹 学 教 程对 偶 问 题Min w=YbT=YTbs.t.ATY CTY 0原 始 问 题max z=CXs.t. AX bX 0 max bAC C TATbT min mnm n 运 筹 学 教 程 例 要 求 制 定 一 个 生 产 计 划 方 案 ， 在 设 备A,B和 调 试 三 种 资 源 限 制 下 ， 使 得 产 品 的 总利 润 最 大 。 maxZ=2x 1+x2 5x215 6x1+2x224 x1+x25 x1,x20st. 运 筹 学 教 程转 换 思 路 :投 资 人 :如 果 某 投 资 公 司 准 备 购 买 该 工 厂 ， 它 至 少 应 付 出 多 大的 代 价 ， 才 能 使 工 厂 自 己 放 弃 生 产 产 品 、 ， 而 将 可 利 用的 资 源 都 出 让 。被 兼 并 人 :该 工 厂 的 底 线 ： 最 低 可 接 受 价 格 ， 指 按 这 种 价 格 转让 资 源 比 自 己 生 产 产 品 、 合 算 的 价 格 。设 y 1,y2， y3为 代 表 单 位 时 间 这 三 种 资 源 的 出 让 价 格 ， 为 了使 工 厂 出 让 资 源 合 算 ， 显 然 应 该 使 出 让 原 来 生 产 一 件 产 品 的 资 源 所 得 收 入 不 低 于 自 己 生 产 产 品 的 利 润 ， 即 0y1+6y2+1y3 2 对 于 产 品 ， 同 样 可 以 建 立 类 似 的 约 束 条 件 5y1+2y2+1y31项 目 产 品 产 品 每 天 可 用能 力设 备 A(h)设 备 B(h)调 试 工 序 (h) 061 521 15245利 润 (元 ) 2 1 y1y2y3 运 筹 学 教 程 当 原 问 题 和 对 偶 问 题 都 取 得 最 优 解 时 ， 这 一 对 线性 规 划 对 应 的 目 标 函 数 值 是 相 等 的 ： Z max=Wmin显 然 在 满 足 这 两 个 约 束 的 前 提 下 ， 价 格 越 高 ， 该工 厂 越 合 算 ， 但 价 格 太 高 ， 投 资 人 方 面 又 不 会 愿意 购 买 。 因 此 ， 我 们 需 要 确 定 的 价 格 是 使 工 厂 合 算 的 最 低 价 格 ， 故 应 建 立 目 标 函 数 ： min w=15y1+24y2+5y3 项 目 产 品 产 品 每 天 可 用能 力设 备 A(h)设 备 B(h)调 试 工 序 (h) 061 521 15245利 润 (元 ) 2 1 运 筹 学 教 程 考 察 原 问 题 和 对 偶 问 题 的 解 ， 给 作 决策 的 管 理 者 另 一 个 自 由 度 ； 对 应 第 一 个 约 束 条 件 对 应 第 二 个 约 束 条 件（ P）max Z = 2X1 + X2 5X2 15 对 应 第 一 个 对 偶 变 量 y1 6X1 + 2X2 24 对 应 第 二 个 对 偶 变 量 y2 X1 + X2 5 对 应 第 三 个 对 偶 变 量 y3 X 1 ， X2 0 （ D）min w = 15y1 + 24y2 + 5y3 6y2 + y3 2 5y1 + 2y2 + y3 1 y1， y2， y3 0 运 筹 学 教 程（ 1） 定 义 ： 若 原 问 题 是 0,. 21 2211 22222112 11212111 2211 n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxats xcxcxcMaxZ 运 筹 学 教 程 0,. 21 2211 22222112 11221111 2211 m nnmnnn nm mm mmyyy cyayaya cyayaya cyayayats ybybybMinW 这 两 个 式 子 之 间 的 变 换 关 系 称 为“ ” 。 运 筹 学 教 程 0,. 21 2211 22222112 11221111 2211 m nnmnnn nm mm mmyyy cyayaya cyayaya cyayayats ybybybMinW 0,. 21 2211 22222112 11212111 2211 n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxats xcxcxcMaxZ 运 筹 学 教 程（ 2） 对 称 形 式 的 对 偶 关 系 的 矩 阵 描 述 0. Y CYAts YbbYMinW TT TT（ D） 0. X bAXts CXMaxZ（ L） （ 3） 从 原 问 题 写 出 其 对 偶 问 题按 照 定 义 ； 记 忆 法 则 ： “ 上 、 下 ” 交 换 ， 换 后 矩 阵 转 置 。 不 等 式 变 号 ， “ 极 大 ” 变 “ 极 小 ” 运 筹 学 教 程例 写 出 下 面 线 性 规 划 的 对 偶 问 题 ： 0, 1025 1543. 2 21 21 21 21xx xx xxts xxMaxZ 0, 124 253. 101521 21 21 21yy yy yyts yyMinW 运 筹 学 教 程 333221 33333232131 22323222121 22323222121 11313212111 33332211 321 3333232131 2323222121 1313212111 332211 ,0,0 )( )(.max ,0,0.max xxxxxx ybxaxaxa ybxaxaxa ybxaxaxa ybxaxaxast xcxcxcxcZ xxx bxaxaxa bxaxaxa bxaxaxast xcxcxcZ 自 由 ,0,0.min 0,0,0,0 .min 321 3333223113 2332222112 1331221111 332211 3221 3333223223113 3333223223113 2332222222112 1331221221111 33222211 yyy cyayaya cyayaya cyayayast ybybybW yyyy cyayayaya cyayayaya cyayayaya cyayayayast ybybybybW 自 由y2=y2-y2y3=-y3 运 筹 学 教 程（ 2） 怎 样 写 出 非 对 称 形 式 的 对 偶 问 题 ？（ 3） 原 -对 偶 表 运 筹 学 教 程项 目 原 问 题 （ 对 偶 问 题 ） 对 偶 问 题 （ 原 问 题 ）目 标 函 数 类 型 max min目 标 函 数 系 数 与 右 边 项的 对 应 关 系 目 标 函 数 各 变 量 系 数 对 应约 束 条 件 右 边 项 的 系 数 右 边 项 的 系 数 对 应 目 标 函 数系 数变 量 个 数 与 约 束 条 件 个数 的 对 应 关 系 变 量 个 数 n约 束 条 件 个 数 m 约 束 条 件 个 数 n变 量 个 数 m原 问 题 变 量 类 型 与 对 偶问 题 约 束 条 件 类 型 的 对应 关 系 0 (对 称 )变 量 类 型 0 (非 对 称 ) 自 由 (对 称 )约 束 条 件 类 型 (非 对 称 ) = 原 问 题 约 束 条 件 类 型 与对 偶 问 题 变 量 类 型 的 对应 关 系 (非 对 称 )约 束 条 件 类 型 (对 称 ) = (非 对 称 )变 量 类 型 (对 称 ) 自 由 运 筹 学 教 程例 题 ： 写 出 下 面 线 性 规 划 的 对 偶 规 划 ： 0,0 141312 111098 7654. 324 321 21 321 321 321 xxx xx xxx xxxts xxxMinZ 符 号 不 限 运 筹 学 教 程 0,0, 3106 21395 41284. 14117 321 21 321 321 321 yyy yy yyy yyyts yyyMaxW符 号 不 限 0,0, 3106 21395 41284. 14117 321 21 321 321 321 yyy yy yyy yyyts yyyMaxW符 号 不 限（ 原 问 题 是 极 小 化 问 题 ， 因 此 应 从 原 -对 偶 表的 右 边 往 左 边 查 ！ ） 0,0 141312 111098 7654. 324 321 21 321 321 321 xxx xx xxx xxxts xxxMinZ 符 号 不 限 项 目 原 问 题 （ 对 偶 问 题 ） 对 偶 问 题 （ 原 问 题 ）目 标 函 数 类 型 max min原 问 题 变 量 类 型与 对 偶 问 题 约 束条 件 类 型 的 对 应关 系 0 (对 称 )变 量 类 型 0 (非对 称 ) 自 由 (对 称 )约 束 条 件 类 型 (非对 称 ) =原 问 题 约 束 条 件类 型 与 对 偶 问 题变 量 类 型 的 对 应关 系 (非 对 称 )约 束 条 件 类 型 (对 称 ) = (非 对 称 )变 量 类 型 (对 称 ) 自 由 运 筹 学 教 程原 问 题 对 偶 问 题 为 对 称 形 式 的 线 性 规 划 问 题 njx mibxats xcMaxZjnj ijijnj jj ,2,10 ,2,1. 1 1 miy njcyats ybMinWimi jiij mi ii ,2,10 ,2,1. 1 1 ， 运 筹 学 教 程 运 筹 学 教 程 0,0. 0 SS SXX bIXAXts XCXMaxZ)( NB CCC )( NB XXX )(),.,(, 21 INBPPPPIA mnn 运 筹 学 教 程（ 1） 由 约 束 条 件 bIXNXBXIXXXNBIXAX SNBSNBS )( 可 得 SN SNB XBNXBbB IXNXbBX 111 1 )( 运 筹 学 教 程项 目 非 基 变 量 基 变 量XB XN XS0 XS b B N ICj-Zj CB CN 0项 目 基 变 量 非 基 变 量X B XN XSCB XB B-1 b I B-1 N B-1 Cj-Zj 0 CN -CB B-1 N -CB B-1 迭 代 后 的 单 纯 形 表初 始 单 纯 形 表 对 应 初 始 单 纯 形 表中 的 单 位 阵 I， 迭代 后 为 B-1基 变 量 的 变 换 ： 初 始 XS=b； 迭代 后 XB= B-1b约 束 系 数 矩 阵 的 变 化 ： A,I=B,N,I；B-1 A, B-1 I=B-1 B, B-1 N, B-1 I=I, B-1 N, B-1.约 束 系 数 矩 阵 的 向 量 变 化 ： PjT = B-1 PjCB CN 0 运 筹 学 教 程检 验 数 ： CN-CB B-1 N0 (1); -CB B-1 0; 令 :CB-CBI=0 (2)(1)+(2)得 到 CN-CB B-1 N +CB-CBI= CN-CB B-1 N +CB-CBB-1B=CB+CN-CBB-1(B+N)=C-CBB-1A 0 -C B B-1 0;令 YT= CB B-1 单 纯 形 乘 子 ATY CT; Y 0 Wmin= YTb= CBB-1b=ZmaxC-YTA 0C YTA C T (YTA)T检 验 数 的 相 反 数 为 其对 偶 问 题 的 一 个 可 行解 运 筹 学 教 程 05 2426 155. 0002max 3521 2421 132 54321 jx yxxx yxxx yxxst xxxxxZ 0 125 26. 0052415min 25321 1431 54321 iy xyyyy xyyyst yyyyyW 例 原 问 题 、 对 偶 问 题 之 间 的 关 系 项 目 原 问 题 变 量 原 问 题 松 弛 变 量 x1 x2 x3 x4 x5X3 15/2X1 7/2X2 3/2 0 0 1 0 0 1 1 5/4 -15/20 -1/20 -1/4 3/2 -Cj+zj 0 0 0 1/2DUAL 剩 余 变 量 DUAL 变 量 y4 y5 y1 y2 y3项 目 dual变 量 dual剩 余 变 量 y1 y2 y3 y4 y5y2 1/4 y3 1/2 -5/4 1 015/2 0 1 -1 /4 -3/2Cj-zj 15/2 0 0 7/2 3/2原 问 题 松 弛 变 量 原 问 题 变 量 x3 x4 x5 x1 x2 运 筹 学 教 程y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对 偶 问 题 的 变 量 对 偶 问 题 的 松 弛 变 量 原 始 问 题 的 变 量 原 始 问 题 的 松 弛 变 量x jym+j=0 yixn+i=0 (i=1,2,m; j=1,2,n)在 一 对 变 量 中 ， 其 中 一 个 大 于 0， 另 一 个 一 定 等 于 0 运 筹 学 教 程。 0. X bAXts CXMaxZ（ L） 0. Y CYAts bYMinW和 （ D） 均 有 可 行 解 ， 分 别 为 和 ， 则 C b。X XY Y证明思路： 由 （ L） bXA 左 乘 ， 得 bYXAY Y由 （ D） CAY 右 乘 ， 得 X XCXAY bYXC 运 筹 学 教 程。 推 论 :极 小 化 问 题 有 下 界 原 问 题 ( ) 运 筹 学 教 程极 大 化 问 题 有 上 界 对 偶 问 题 ( ) 运 筹 学 教 程 运 筹 学 教 程XXX YYY 运 筹 学 教 程CX =Y bCX* Y*b弱 对 偶定 理 已 知 结 论Y*b Y b因 为XY可 行解 CX CX*设 X*,Y*分 别 为 原 问 题 和 对 偶 问 题 的 最 优 解 ; X,Y分 别 为 原 问题 和 对 偶 问 题 的 可 行 解CX CX* Y*bY b=CXCX =CX* = Y*b=Y b 运 筹 学 教 程都 有 可 行 解 各 自 有 上 下 界都 有 最 优 解 目 标 函 数 值 相 等证 明 要 点 ： 1* *Bz C B b Y b 运 筹 学 教 程互 补 松 弛 性 在 线 性 规 划 问 题 的 最 优 解中 ， 如 果 对 应 某 一 约 束 条 件 的 对 偶 变 量 值 为 非 零 ，则 该 约 束 条 件 取 严 格 等 式 ； 反 之 ， 如 果 约 束 条 件取 严 格 不 等 式 ， 则 其 对 应 的 对 偶 变 量 一 定 为 零 。 0,01 1 inj jij inj jiji ybixa bxay 有若 有若 0,0 0,0 0,.,2,1 20,0 0 )2(0 )1()( 1 111 1 11 1 111 1 1 11 iinj jji inj jjii iinj jji i nj jjii iimi nj jjimi nj mi iiijji mi iinj jj mi nj mi iijijinj jj ybxa bxay ybxami bxay ybxa ybyxa ybxc ybxyaxc 必 有当 所 以因 此 当 有 ） 成 立 必 须 对 所 有 的， 所 以 （因 证 明 弱 对 偶 性最 优 性此 定 理 适 用 于非 对 称 形 式(1)式 应 取 = 运 筹 学 教 程 0 1622 102. 43 31 321 321 321x xxx xxxst xxxnaxZ例 :已 知 线 性 规 划其 最 优 解 为 x=(6,2,0)T,求 对 偶问 题 的 最 优 解 2 6+2 2+0=16;y206+2 2+0=10;y10 01 422 32. 1610min 21 21 21 21 21yyy yy yyst yyW 运 筹 学 教 程 01 422 32. 1610min 21 21 21 21 21yyy yy yyst yyW x1=60;约 束 条 件 为 =x2=20;约 束 条 件 为 =x3=0;约 束 条 件 为 01 422 3221 21 21 21yyy yy yy 求 解 结 果 为 Y=(1,1)TMin W=26 运 筹 学 教 程n 思 考 题n 如 何 理 解 对 偶 问 题 的 基 本 性 质 ？n 讨 论 题n 用 例 子 说 明 互 补 松 弛 性 的 实 际 应 用 。 运 筹 学 教 程n 小 结n 对 偶 问 题 的 基 本 性 质 。n 对 偶 定 理 。n 作 业 :n 2.1(1),2.3,2.7
展开阅读全文