运筹学对偶问题

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

1、2021/6/16 1 第 四 章 对 偶 问 题l 对 偶 问 题 的 一 般 形 式l 对 偶 问 题 的 经 济 意 义l 对 偶 性 质l 对 偶 单 纯 形 法l 对 偶 单 纯 形 法 的 解 题 原 理 2021/6/16 2 一 、 对 偶 问 题 的 一 般 形 式 l 若 设 一 线 性 规 划 问 题 如 下 ：（ A） 0,0,0.max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nnxxx bxaxaxa bxaxaxa bxaxaxats xcxcxcF 2021/6/16 3 则 以 下 线 性 规 划 问 题 ：

2、（ B） 称 为 原 问 题 （ A） 的 对 偶 线 性 规 划 问 题 ， 或 称 A、 B互 为 对 偶 问 题 。 0,0,0.min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mmyyy cyayaya cyayaya cyayayats ybybybW 2021/6/16 4 如 果 采 用 向 量 、 矩 阵 来 表 示 0.max X BAXts CXF 0.min Y CYAts YBW T ncccC 21 myyyY 21 mbbbB 21 nxxxX 21 mnmn nnaaa aaa aaaA 21 22221 112

3、11（ A） （ B）其 中 ： 2021/6/16 5 可 以 将 以 上 关 系 列 成 以 下 对 偶 表 ： maxmin x1 x2 xn by1 a11 a12 a1n b1y2 a21 a22 b2 ym am1 am2 amn bm c c 1 c2 cn 2021/6/16 6 例l 写 出 下 列 线 性 规 划 问 题 的 对 偶 问 题0,0,0 6042 4824. 13146max 321 321 321 321 xxx xxx xxxts xxxF 2021/6/16 7 解 ：l 可 以 将 原 问 题 的 有 关 参 数 列 成 下 表 maxmin x1 x

4、2 x3 by1 1 4 2 48y2 1 2 4 60 c 6 14 13 2021/6/16 8 对 偶 规 划 问 题 为 0,0 1342 1424 6. 6048min 21 21 21 21 21 yy yy yy yyts yyW 2021/6/16 9 比 较l 以 上 我 们 介 绍 的 对 偶 问 题 是 严 格 定 义 的 对 偶 问 题 ， 也成 为 对 称 对 偶 问 题 。 l 它 满 足 两 个 条 件 ： 0,0,0 6042 4824. 13146max 321 321 321 321 xxx xxx xxxts xxxF 0,0 1342 1424 6. 6

5、048min 21 21 21 21 21 yy yy yy yyts yyW 2021/6/16 10 两 个 条 件 ： 1、 所 有 变 量 非 负 ： 即 X0， Y02、 约 束 条 件 均 为 同 向 不 等 式 。 若 原 问 题 约 束 条 件 均为 “ ” ， 则 它 的 对 偶 问 题 的 约 束 条 件 都 是 “ ” 。l当 原 问 题 的 约 束 条 件 的 符 号 不 完 全 相 同 时 ， 也 存 在对 偶 问 题 ， 这 种 对 偶 问 题 称 为 非 对 称 对 偶 问 题 。 2021/6/16 11 例l 分 析 ： l 为 求 对 偶 问 题 ， 可 先

6、 做 过 渡 ， 将 问 题 对 称 化 ：为 自 由 变 量21 21 21 21 21,0 5 1034 2023 . 54max xx xx xx xxts xxZ 2021/6/16 12 对 称 化为 自 由 变 量 21 21 21 21 21,0 5 1034 2023 . 54max xx xx xx xxts xxZ 0 x,0 x,xxx 55 1034 43432 21 21 21 设 xx xx xx 521 xx 2021/6/16 13 则 ， 原 问 题 变 为 0,0,0 5 5 10334 20223 . 554max 431 431 431 431 431

7、431 xxx xxx xxx xxx xxxts xxxZ为 自 由 变 量 21 21 21 21 21,0 5 1034 2023 . 54max xx xx xx xxts xxZ （ A） （ A） 2021/6/16 14 则 （ A） 的 对 偶 问 题 如 下 ： 0,0,0,0 532 532 443 . 551020min 4321 4321 4321 4321 4321 yyyy yyyy yyyy yyyyts yyyyW （ B）0,0,0 5 5 10334 20223 . 554max 431 431 431 431 431 431 xxx xxx xxx xxx

8、 xxxts xxxZ （ A） 2021/6/16 15 对 比 结 果l 以 上 对 偶 问 题 （ B） 并 非 原 问 题 （ A） 的 对 偶 问 题 ，它 是 线 性 规 划 问 题 （ A） 的 对 偶 问 题 。 0,0,0,0 532 532 443 . 551020min 4321 4321 4321 4321 4321 yyyy yyyy yyyy yyyyts yyyyW为 自 由 变 量21 21 21 21 21,0 5 1034 2023 . 54max xx xx xx xxts xxZ （ A） （ B） 2021/6/16 16 调 整l 对 照 问 题 B

9、目 标 函 数 系 数 的 符 号 与 原 问 题 A中约 束 条 件 右 端 常 数 项 的 符 号 ， 可 做 以 下 调 整 ：l 令 y1=y1， y2=-y2， y3=y4-y3 2021/6/16 17 令 y1=y1， y2=-y2， y3=y4-y3则 得 到 以 下 对 偶 问 题 为 自 由 变 量321 321 321 321 321,0,0 532 532 443 . 51020min yyy yyy yyy yyyts yyyW 0,0,0,0 532 532 443 . 551020min 4321 4321 4321 4321 4321 yyyy yyyy yyy

10、y yyyyts yyyyW （ B） （ B） 2021/6/16 18 合 并 为 自 由 变 量 321 321 321 321 321,0,0 532 532 443 . 51020min yyy yyy yyy yyyts yyyW 为 自 由 变 量321 321 321 321,0,0 532 443 . 51020min yyy yyy yyyts yyyW （ B） 2021/6/16 19 比 较 l 对 于 任 何 一 个 线 性 规 划 问 题 ， 我 们 都 可 以 求 出它 的 对 偶 问 题 。为 自 由 变 量21 21 21 21 21,0 5 1034 20

11、23 . 54max xx xx xx xxts xxZ （ A） （ B）为 自 由 变 量321 321 321 321,0,0 532 443 . 51020min yyy yyy yyyts yyyW 2021/6/16 20 原 问 题 与 对 偶 问 题 的 相 应 关 系 原 问 题 A（ 对 偶 问 题 B） 对 偶 问 题 B（ 原 问 题 A）最 大 化 max 最 小 化 minA系 数 矩 阵 ATB右 端 常 数 （ 列 向 量 ） 目 标 函 数 系 数 (行 向 量 )C目 标 函 数 系 数 右 端 常 数 （ 列 向 量 ）第 i个 约 束 条 件 为 等 式

12、 “ =” yi为 自 由 变 量第 i个 约 束 条 件 为 不 等 式 “ ” y i 0第 i个 约 束 条 件 为 不 等 式 “ ” yi 0 xj为 自 由 变 量 第 j个 约 束 条 件 为 等 式 “ =”xj 0 第 j个 约 束 条 件 为 不 等 式 “ ”xj 0 第 j个 约 束 条 件 为 不 等 式 “ ” 2021/6/16 21 例 ： 写 出 下 列 问 题 的 对 偶 形 式 ： 为 自 由 变 量 321 321 321 321 321 ,0,0 4 163 2532 . 34max xxx xxx xxx xxxts xxxZ 2021/6/16 2

13、2 解 ： 为 自 由 变 量 321 321 321 321 321 ,0,0 365 43 132 . 42min yyy yyy yyy yyyts yyyW 为 自 由 变 量321 321 321 321 321 ,0,0 4 163 2532 . 34max xxx xxx xxx xxxts xxxZ 2021/6/16 23 例 ： 写 出 下 列 问 题 的 对 偶 问 题 ,0,0 24732 543 3432. 4323min 43,21 4321 432 4321 4321 xxxx xxxx xxx xxxxts xxxxZ 为 自 由 变 量 2021/6/16 2

14、4 解 ： 为 自 由 变 量 321 321 321 321 31 321,0,0 4444 3733 232 32. 253max yyy yyy yyy yyy yyts yyyW ,0,0 24732 543 3432. 4323min 43,21 4321 432 4321 4321 xxxx xxxx xxx xxxxts xxxxZ 为 自 由 变 量 2021/6/16 25 二 、 对 偶 问 题 的 经 济 意 义 ：l 若 原 规 划 问 题 是 “ 在 一 定 条 件 下 ， 使 工 作 或 成果 （ 产 品 产 量 、 利 润 等 ） 尽 可 能 的 大 ” ，l 那

15、 么 它 的 对 偶 问 题 就 是 “ 在 另 外 一 些 条 件 下 ，使 工 作 的 消 耗 （ 浪 费 、 成 本 等 ） 尽 可 能 的 小 ” 。l 实 际 上 是 一 个 问 题 的 两 个 方 面 。 2021/6/16 26 例 ： 某 产 品 计 划 问 题 的线 性 规 划 数 学 模 型 为 0, 1025 1553 . 2max 21 21 21 21 xx xx xxts xxF （ 设 备 的 约 束 ）（ 原 料 的 约 束 ） l 假 设 生 产 部 门 根 据 市 场 变 化 ，决 定 停 止 生 产 甲 、 乙 产 品 ，而 将 原 有 的 原 料 、 设

16、 备 专 用于 接 受 外 来 订 货 以 生 产 市 场急 需 的 紧 俏 商 品 ， 则 需 要 考虑 决 策 的 问 题 就 是 “ 在 什 么样 的 价 格 条 件 下 ， 才 能 接 受外 来 订 货 ？ ” 。 问 题 的 实 质就 是 如 何 确 定 原 料 、 设 备 的收 费 标 准 ？ 2021/6/16 27 分 析l 若 设 y1为 单 位 原 材 料 的 价 格 ， y2为 设 备 单 位 台 时 价 格 ， 由于 用 了 3个 单 位 原 料 和 5个 单 位 设 备 台 时 就 可 以 生 产 一 个 单位 甲 产 品 而 获 利 2个 单 位 ， 现 在 不 生

17、 产 甲 产 品 ， 转 而 接 受外 来 订 货 加 工 ， 则 收 取 的 费 用 不 能 低 于 2个 单 位 ， 否 则 自己 生 产 甲 产 品 更 有 利 。 因 此 ， 可 以 得 到 下 面 的 条 件 ：253 21 yy 2021/6/16 28 分 析l 同 理 ， 将 生 产 乙 产 品 的 原 料 和 设 备 工 时 用 于 接受 外 来 加 工 订 货 ， 收 取 的 费 用 不 能 低 于 乙 产 品的 单 位 利 润 1个 单 位 ： 125 21 yy 2021/6/16 29 分 析l 另 外 ， 为 了 争 取 外 来 加 工 订 货 ， 在 满 足 上

18、述 要求 的 基 础 上 ， 收 费 标 准 应 尽 可 能 低 从 而 具 有 竞争 力 ， 因 此 总 的 收 费 w=15y1+10y2 应 极 小 化 。这 样 ， 就 得 到 一 个 目 标 函 数 ： 21 1015min yyW 2021/6/16 30 这 样 ， 就 得 到 另 一 个 线 性 规 划 模 型 ： 0,0 125 253 . 1015min 21 21 21 21 yy yy yyts yyW 2021/6/16 31 比 较 0,0 125 253 . 1015min 21 21 21 21 yy yy yyts yyW0, 1025 1553 . 2max

19、21 21 21 21 xx xx xxts xxF 生 产 问 题（ 要 利 用 资 源 ） 资 源 利 用 问 题（ 会 影 响 生 产 ） 2021/6/16 32 第 二 节 对 偶 理 论 2021/6/16 33 定 理 1（ 对 称 性 定 理 ）l 对 偶 问 题 （ B） 的 对 偶 规 划 为 线 性 规 划 （ A）l 对 称 性 定 理 是 很 重 要 的 。 它 表 明 原 规 划 问 题 （ A） 和 对 偶规 划 问 题 （ B） 是 互 为 对 偶 的 。 也 就 是 说 ， 如 果 （ B） 是（ A） 的 对 偶 ， 那 么 （ A） 也 是 （ B） 的

20、对 偶 。 这 就 为 以后 的 讨 论 带 来 方 便 。 不 难 理 解 ， 如 果 当 A具 有 某 种 性 质 时可 以 推 出 B的 某 些 性 质 ， 于 是 可 以 无 需 另 加 证 明 地 得 到 ：当 B具 有 某 种 性 质 时 ， 问 题 A也 具 有 那 些 性 质 。 2021/6/16 34 定 理 2（ 弱 对 偶 定 理 ）l 当 原 问 题 A是 求 最 大 值 max， 而 对 偶 问 题 是 求最 小 值 时 ， 如 果 X0是 原 问 题 的 任 意 可 行 解 ， Y0是 对 偶 问 题 的 任 意 可 行 解 ， 则 有 以 下 关 系 式 成立

21、： BYCX 00 2021/6/16 35 定 理 3（ 最 优 性 定 理 ）l 设 和 分 别 是 问 题 A和 B的 可 行 解 ，若 相 应 于 和 ， A和 B的 目 标 函 数 值相 等 ， 即 ， 则 和 分 别 是 A和 B的 最 优 解 。 x y x ybyxc y x 2021/6/16 36 定 理 4（ 无 界 性 定 理 ）l 如 果 原 问 题 A的 目 标 函 数 值 无 界 ， 则 对 偶 问 题B无 可 行 解 ； 如 果 对 偶 问 题 B的 目 标 函 数 值 无界 ， 则 原 问 题 A无 可 行 解 。 2021/6/16 37 以 上 三 个 定

22、 理 可 以 这 样 记 忆l 原 问 题 A和 对 偶 问 题 B如 果 有 可 行 解 ， 则 它 们 的 可 行 解 区 域 只可 能 相 接 ， 不 可 能 相 交 。 两 个 区 域 的 交 界 线 即 是 它 们 的 最 优 解 ，如 果 原 问 题 A的 目 标 函 数 无 界 ， 意 味 着 可 行 解 区 域 无 界 ， 向 外扩 张 ， 挤 占 了 对 偶 问 题 B的 可 行 解 区 域 ， 则 对 偶 问 题 无 可 行 解 ，反 之 同 理 可 说 明 。对 偶 问 题 (B) minW 原 问 题 (A) maxZ y0bcx0 byxc 2021/6/16 38

23、定 理 5（ 强 对 偶 定 理 ）l 若 线 性 规 划 A存 在 最 优 解 ， 则 对 偶 规 划 B也 存在 最 优 解 ， 并 且 它 们 的 最 优 值 相 等 ； 相 反 地 ，若 规 划 B存 在 最 优 解 ， 则 规 划 A也 存 在 最 优 解 ，并 且 它 们 的 最 优 值 相 等 。 2021/6/16 39 定 理 6（ 存 在 性 定 理 ）l 若 线 性 规 划 A和 B都 存 在 可 行 解 ， 则 A和 B都 存在 最 优 解 。 2021/6/16 40 第 三 节 对 偶 单 纯 形 法l 条 件 ：l b列 中 至 少 有 一 个 bi0；l 原 问

24、 题 A的 检 验 数 满 足 符 号 条 件 。 2021/6/16 41 例 )4,3,2,1(0 242 32. 34min 4321 4321 421 jx xxxx xxxxts xxxZ j 2021/6/16 42 解 ： min maxl 解 ： 引 入 松 弛 变 量 ， 化 为 标 准 形 式 ： )6,2,1(0 242 32. 34max 64321 54321 421 jx xxxxx xxxxxts xxxZ j 2021/6/16 43 观 察 A矩 阵 101412 011121A 2021/6/16 44 解l 以 上 标 准 形 式 中 没 有 完 全 单

25、位 向 量 组 ， 我 们 将约 束 条 件 进 行 变 换 ， 两 边 同 乘 （ -1） 。l A矩 阵 中 存 在 完 全 单 位 向 量 组 ， 但 bi0时 ， 得 到 最 优 解 。l 否 则 ， 进 行 换 基 迭 代 段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x 5 -3 -1 -2 1 -1 1 00 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0 j 2021/6/16 47 步 骤 3： 换 基 迭 代l （ 1） ： 找 到 b列 中 绝 对 值 最 大 者 所 在 行 为主 元 行 ， 记

26、为 Pi*， 主 元 行 对 应 的 变 量 Xi*为 调 出 变 量 。 段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x 5 -3 -1 -2 1 -1 1 00 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0 j 2021/6/16 48 （ 2）l 找 出 主 元 行 Pj*中 所 有 负 分 量 ， 计 算l 注 ： 若 主 元 行 中 没 有 负 分 量 ， 则 问 题 无 解 。 ji jjj p zc *段 Cj 基 0b -1P 1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 -1

27、 -2 1 -1 1 00 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - - 2021/6/16 49 （ 3）l j中 绝 对 值 最 小 者 所 在 的 列 为 主 元 列 ， 记 为 Pj*，主 元 列 所 对 应 的 变 量 xj*为 调 入 变 量 。段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x 5 -3 -1 -2 1 -1 1 00 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - - 2021/6/16 50 （

28、4）l 主 元 行 与 主 元 列 相 交 处 的 元 素 即 主 元 素 ， 记 为 Pi*j*。 段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x 5 -3 (-1) -2 1 -1 1 00 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - - 2021/6/16 51 （ 5） 迭 代l 用 高 斯 消 去 法 ， 使 原 主 元 列 中 除 了 原 主 元 素 为 1外 ，其 余 元 素 均 为 0。 段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x

29、 5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - -2 -1 x1 10 x6 0Cj-Zj j 2021/6/16 52 计 算 结 果段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - -2 -1 x 1 3 1 2 -1 1 -1 00 x6 -8 0 -3 -2 -3 2 1Cj-Zj j

30、 2021/6/16 53 找 主 元 行 、 确 定 调 出 变 量 、计 算 zj-cj段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - 1 4 0 3 0 0j - -1 -2 - -3 - - 2 -1 x1 3 1 2 -1 1 -1 00 x6 -8 0 -3 -2 -3 2 1Cj-Zj - - -2 -1 -2 - -j 2021/6/16 54 计 算 j、 确 定 调 入 变 量段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0

31、P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - -2 -1 x 1 3 1 2 -1 1 -1 00 x6 -8 0 -3 -2 -3 2 1Cj-Zj - 0 -2 -1 -2 1 0j - 2/3 1/2 2/3 - - 2021/6/16 55 继 续 换 基 迭 代 ：段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj -

32、 -1 -4 0 -3 0 0j - 1 2 - 3 - -2 -1 x1 3 1 2 -1 1 -1 00 x 6 -8 0 -3 (-2) -3 2 1 Cj-Zj - 0 -2 -1 -2 -1 0j - - 2/3 1/2 2/3 - -3 -1 x1 00 x3 1Cj-Zj j 2021/6/16 56 继 续 换 基 迭 代 ：段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - -2 -1

33、x1 3 1 2 -1 1 -1 00 x 6 -8 0 -3 (-2) -3 2 1 Cj-Zj - 0 -2 -1 -2 -1 0j - - 2/3 1/2 2/3 - -3 -1 x1 7 1 7/2 0 5/2 -2 -1/20 x3 4 0 3/2 1 3/2 -1 -1/2Cj-Zj j 2021/6/16 57 继 续 换 基 迭 代 ：段 Cj 基 0b -1P1 -4P2 0P3 -3P4 0P5 0P6 注1 0 x5 -3 (-1) -2 1 -1 1 0 0 x6 -2 2 1 -4 -1 0 1Cj-Zj - -1 -4 0 -3 0 0j - 1 2 - 3 - -

34、2 -1 x1 3 1 2 -1 1 -1 00 x 6 -8 0 -3 (-2) -3 2 1 Cj-Zj - 0 -2 -1 -2 1 0j - - 2/3 1/2 2/3 - -3 -1 x1 7 1 7/2 0 5/2 -2 -1/20 x3 4 0 3/2 1 3/2 -1 -1/2Cj-Zj 7 0 -1/2 0 -1/2 -2 -1/2j 2021/6/16 58 得 到 最 优 解 ：l 计 算 到 第 三 段 时 ， b0且 Cj-Zj0， 得 到 原 问 题的 最 优 解 ： 7maxmin 0,4,0,7 654321 ZZ xxxxxx 2021/6/16 59 五 、

35、 对 偶 单 纯 形 法 的 求 解 思 路 ：l 一 般 单 纯 形 法 的 思 路 ：l 在 使 用 表 格 单 纯 形 法 求 解 线 性 规 划 标 准 型 的 最 优 解 时 ， 是 从 一 个初 始 基 本 可 行 解 （ 可 行 域 的 一 个 顶 点 ） 开 始 ， 按 照 一 定 的 规 则 进行 迭 代 ， 求 出 第 二 个 基 本 可 行 解 （ 另 一 个 可 行 域 的 顶 点 ） ， 同 时 ，逐 步 使 检 验 数 都 变 成 正 值 ， 目 标 函 数 的 当 前 值 则 逐 步 变 优 ， 直 至所 有 检 验 数 全 部 变 成 非 负 值 ， 对 应 的

36、 基 本 可 行 解 就 成 为 最 优 解 。 l 由 于 迭 代 过 程 中 出 现 的 基 本 可 行 解 既 是 满 足 约 束 条 件 的 基 本 解 ，又 是 保 持 取 非 负 值 的 可 行 解 ， 即 使 解 答 列 中 基 变 量 的 取 值 （ b列 ）始 终 保 持 非 负 ， 通 过 迭 代 逐 步 消 除 检 验 数 行 中 的 不 满 足 符 号 条 件的 检 验 数 。 2021/6/16 60 l 检 验 数 也 可 以 用 向 量 形 式 写 出 ： （ 这 里 只 写 出 非 基 变 量 的 检 验 数 向 量 ）l 从 可 以 很 容 易 得 推 出 ，

37、这 说 明 原 问 题 的 最 优 基 正 是 对 偶 问 题 的 可 行 基 。 换 言之 ， 当 原 问 题 的 基 B即 是 原 问 题 的 可 行 基 又 是 对 偶 问题 的 可 行 基 时 ， B就 是 最 优 基 。 因 此 ， 单 纯 性 法 求 解过 程 正 是 在 保 持 原 始 可 行 （ 解 答 列 基 变 量 取 值 均 非 负 ）的 条 件 下 ， 通 过 迭 代 逐 步 实 现 对 偶 可 行 性 。jjj zcZ NBNN PBCCZ 1 01 NBNN PBCCZ CABCB 1 2021/6/16 61 l 在 对 偶 关 系 中 ， 由 于 价 值 系 数

38、 C和 约 束 条 件 右端 常 数 系 数 b互 换 位 置 ， 因 此 可 以 设 想 ， 能 否在 保 持 检 验 数 Cj-Zj非 正 的 条 件 下 ， 逐 步 消 除基 本 解 中 的 负 分 量 ， 使 之 成 为 可 行 解 。 这 样 ，该 基 本 解 就 是 基 本 最 优 解 。l 对 偶 单 纯 形 法 正 是 基 于 这 种 思 想 而 产 生 的 ，其 基 本 思 想 就 是 在 保 持 对 偶 可 行 性 的 条 件 下 ，通 过 逐 步 迭 代 实 现 原 始 可 行 性 。 2021/6/16 62 l 所 以 ， 对 偶 单 纯 形 法 的 使 用 条 件 是 ：l b列 中 至 少 有 一 个 bi0；l 原 问 题 A的 检 验 数 Cj-Zj0； 若 有 不 当 之 处 ， 请 指 正 ， 谢 谢 ！