《运筹学基础及应用》PPT课件

《《运筹学基础及应用》PPT课件》由会员分享，可在线阅读，更多相关《《运筹学基础及应用》PPT课件（106页珍藏版）》请在装配图网上搜索。

1、1 运 筹 学 2 第 一 章 线 性 规 划 及 单 纯 形 法 (Linear Programming, LP)n 线 性 规 划 模 型n 图 解 法n 单 纯 形 法 原 理n 单 纯 形 法 计 算 步 骤n 单 纯 形 法 的 进 一 步 讨 论n 数 据 包 络 分 析 3 1 一 般 线 性 规 划 问 题 的 数 学 模 型1.1 引 例 例 1、 生 产 计 划 问 题 能 力 设 备 A 2 2 12 设 备 B 4 0 16 设 备 C 0 5 15 利 润 2 3 ， 各 生 产 多 少 , 可 获 最 大 利 润 ? 2021-4-28 4 2x1+2x2 12 4

2、x1 16 5x2 15 x1， x2 0注 意 模 型 特 点 max Z= 2x1 +3x2解 :设 产 品 , 产 量 分 别 为 变 量 x1 ， x2 2021-4-28 5 线 性 规 划 模 型 特 点n 决 策 变 量 ： 向 量 X=(x1 xn)T 决 策 人 要 考 虑和 控 制 的 因 素 ， 非 负n 约 束 条 件 ： 关 于 X的 线 性 等 式 或 不 等 式n 目 标 函 数 ： Z=(x1 xn) 为 关 于 X 的 线 性 函 数 ，求 Z极 大 或 极 小 2021-4-28 6 1.2 线 性 规 划 问 题 的 数 学 模 型三 个 组 成 要 素

3、：1.决 策 变 量 :是 决 策 者 为 实 现 规 划 目 标 采 取 的方 案 、 措 施 ， 是 问 题 中 要 确 定 的 未 知 量 。2.目 标 函 数 :指 问 题 要 达 到 的 目 的 要 求 ， 表示 为 决 策 变 量 的 函 数 。3.约 束 条 件 :指 决 策 变 量 取 值 时 受 到 的 各 种 可用 资 源 的 限 制 ， 表 示 为 含 决 策 变 量 的 等 式 或不 等 式 。 2021-4-28 7 一 般 线 性 规 划 问 题 的 数 学 模 型 ： 0 x,x,x b,xaxaxa b,xaxaxa b,xaxaxa n21 mnmn22m11

4、m 2nn2222121 1nn1212111 ）（ 或 ）（ 或 ）（ 或 目 标 函 数 ：约 束 条 件 ： nn2211 xcxcxczminmax ）（ 或 2021-4-28 8 简 写 形 式 ： ），（ ），（），（ 或）（ 或 n1j0 x m1ibxa xczminmaxj in1j jij n1j jj 2021-4-28 9 矩 阵 形 式 表 示 为 ： 0 minmaxX bAX CXz），（ 或 ）（ 或其 中 ： mnmm nnaaa aaa aaaA 21 22221 11211 ncccC , 21 TnxxxX , 21 Tmbbbb , 21 2021-

5、4-28 10 1.3 线 性 规 划 问 题 的 标 准 形 式标 准 形 式 ： ），（ ），（ n1j0 x m1ibxa xczmax j in1j jij n1j jj 标 准 形 式 特 点 ：4. 决 策 变 量 取 值 非 负 。1. 目 标 函 数 为 求 极 大 值 ；2. 约 束 条 件 全 为 等 式 ；3. 约 束 条 件 右 端 常 数 项 全 为 非 负 ； 2021-4-28 11 一 般 线 性 规 划 问 题 如 何 化 为 标 准 型 ：1. 目 标 函 数 求 极 小 值 ： nj jjxcz 1min令 ： ， 即 化 为 ：zz nj jjnj jj

6、 xcxc zzz 11 min)max(max 2021-4-28 12 2. 约 束 条 件 为 不 等 式 ：（ 1） 当 约 束 条 件 为 “ ” 时如 ： 1222 21 xx可 令 ： ， 显 然1222 321 xxx 03 x（ 2） 当 约 束 条 件 为 “ ” 时如 ： 181210 21 xx可 令 ： ， 显 然 04 x181210 421 xxx 称 为 松 弛 变 量 。3x 称 为 剩 余 变 量 。4x 2021-4-28 13松 弛 变 量 和 剩 余 变 量 统 称 为 松 弛 变 量 （ 3） 目 标 函 数 中 松 弛 变 量 的 系 数 由 于

7、松 弛 变 量 和 剩 余 变 量 分 别 表 示 未 被 充 分 利用 的 资 源 以 及 超 用 的 资 源 ， 都 没 有 转 化 为 价 值 和 利润 ， 因 此 在 目 标 函 数 中 系 数 为 零 。 2021-4-28 14 3. 取 值 无 约 束 的 变 量 如 果 变 量 x 代 表 某 产 品 当 年 计 划 数 与 上一 年 计 划 数 之 差 ， 显 然 x 的 取 值 可 能 是 正 也可 能 是 负 ， 这 时 可 令 ： xxx 其 中 ： 00 xx ，令4. 变 量 xj0 jj xx ， 显 然 0jx 2021-4-28 15 例 . 将 下 述 线

8、性 规 划 模 型 化 为 标 准 型 取 值 无 约 束 321 321 321 321 321 ,0,0 6323 423 92 32min xxx xxx xxx xxx xxxz 2021-4-28 16 解 ： 令 ， 11 xxzz 00 33333 xxxxx ，得 标 准 形 式 为 ： 0 6 3323 4 22 3 9 2 00332max 543321 3321 53321 43321 543321 xxxxxx xxxx xxxxx xxxxx xxxxxxz ， 2021-4-28 17 求 解 线 性 规 划 问 题 ：就 是 从 满 足 约 束 方 程 组 和 约

9、 束 不 等 式 的 决 策 变 量 取值 中 ， 找 出 使 得 目 标 函 数 达 到 最 大 的 值 。 ），（ ），（ njx mibxa xcz j inj jij nj jj 1 0 1 max1 11.4 线 性 规 划 问 题 的 解 的 概 念 2021-4-28 18 可 行 解 ： 满 足 约 束 条 件 的 解 称 为 可 行 解 ， 可 行 解 的 集合 称 为 可 行 域 。最 优 解 ： 使 目 标 函 数 达 到 最 大 值 的 可 行 解 。 基 ： 约 束 方 程 组 的 一 个 满 秩 子 矩 阵 称 为 规 划 问 题 的 一个 基 ， 基 中 的 每

10、一 个 列 向 量 称 为 基 向 量 ， 与 基 向 量 对 应的 变 量 称 为 基 变 量 ， 其 他 变 量 称 为 非 基 变 量 。 基 解 ： 在 约 束 方 程 组 中 ， 令 所 有 非 基 变 量 为 0， 可 以解 出 基 变 量 的 唯 一 解 ， 这 组 解 与 非 基 变 量 的 0共 同 构 成基 解 。基 可 行 解 ： 满 足 变 量 非 负 的 基 解 称 为 基 可 行 解可 行 基 ： 对 应 于 基 可 行 解 的 基 称 为 可 行 基 2021-4-28 19 例 ： 考 察 下 述 线 性 规 划 问 题 ： 5,.2,1,0 155 164 1

11、222. 00032max 52 41 321 54321ix xx xx xxxts xxxxxzi 2021-4-28 20 （ 1） 可 行 解 ， 如 )15,16,12,0,0( )0,4,0,3,3(或满 足 约 束 条 件 ， 所 以 是 可 行 解 。（ 2） 基系 数 矩 阵 A： 10050 01004 00122A 54321 PPPPP其 中 100 010 001),( 5431 PPPB 或 150 004 022),( 5212 PPPB都 构 成 基 。 而 )( 431 PPP 不 构 成 基 。 2021-4-28 21 （ 3） 基 向 量 、 基 变 量

12、521 , PPP 是 对 应 于 基 的 三 个 基 向 量 ， 而2B521 , xxx 是 对 应 于 这 三 个 基 向 量 的 基 变 量 。（ 4） 基 解 、 基 可 行 解 、 可 行 基)1516,12,0,0( 是 对 应 于 基 1B 的 一 个 基 解 、 基 可 行 解 。)5,0,0,2,4( 是 对 应 于 基 2B的 一 个 基 解 、 基 可 行 解 。21,BB 均 是 可 行 基 。练 习 ： P14， 例 4 2021-4-28 22 为 了 便 于 建 立 n 维 空 间 中 线 性 规 划 问 题 的 概 念 及便 于 理 解 求 解 一 般 线 性

13、 规 划 问 题 的 单 纯 形 法 的 思 路 ，先 介 绍 图 解 法 。求 解 下 述 线 性 规 划 问 题 ： 0, 15164 1222 21 21 21xx xx xx 5 21 32max xxz 2 线 性 规 划 问 题 的 图 解 法 2021-4-28 23 画 出 线 性 规 划 问 题 的 可 行 域 ：1222 21 xx 164 1 x 155 2 x2x 1xO 1Q2Q3Q4Q3 4 21 32 xxZ 目 标 函 数 等 值 线 332 12 zxx 2021-4-28 24 1、 可 行 域 ： 约 束 条 件 所 围 成 的 区 域 。2、 基 可 行

14、 解 ： 对 应 可 行 域 的 顶 点 。3、 目 标 函 数 等 值 线 ： 33232 1221 zxxxxZ 4、 目 标 函 数 最 优 值 : 最 大 截 距 所 对 应 的 。 目 标 函 数 等 值 线 有 无 数 条 ， 且 平 行 。 （ 观 察 规 律 )Z 2021-4-28 25 解 的 几 种 情 况 ：(2) 无 穷 多 最 优 解(1) 唯 一 最 优 解 21 22max xxz 若 目 标 函 数 改 为 ： 约 束 条 件 不 变 ， 则 :1222 21 xx 164 1 x 155 2 x2x 1xO 1Q2Q3Q4Q3 4 21 22 xxZ 目 标

15、 函 数 等 值 线此 时 ， 线 段 32QQ上 所 有 点 都 是 最 优值 点 。 2021-4-28 26 解 的 几 种 情 况 ：(4) 无 界 解(3) 无 可 行 解 ： 当 可 行 域 为 空 集 时 ， 无 可 行 解 。若 目 标 函 数 不 变 ， 将 约 束 条 件 1和 3去 掉 ， 则 可 行 域 及 解 的情 况 见 下 图 。 164 1 x2x 1xO 1Q2Q3Q4Q3 4 21 22 xxZ 目 标 函 数 等 值 线此 时 ， 目 标 函 数 等值 线 可 以 向 上 无 穷远 处 平 移 ， Z值 无界 。 2021-4-28 27 几 点 说 明

16、：1、 图 解 法 只 能 用 来 求 解 含 有 两 个 决 策 变 量 的 线 性 规 划 问 题 。2、 若 最 优 解 存 在 ， 则 必 在 可 行 域 的 某 个 顶 点 处 取 得 。3、 线 性 规 划 问 题 的 解 可 能 是 ： 唯 一 最 优 解 、 无 穷 多 最 优解 、 无 最 优 解 、 无 界 解 。 2021-4-28 28 3 单 纯 形 法 原 理凸 集 ： 如 果 集 合 C 中 任 意 两 个 点 ， 其 连 线 上 的 所 有 点也 都 是 集 合 C 中 的 点 。 21,XX上 图 中 （ 1） （ 2） 是 凸 集 ， （ 3） （ 4） 不

17、 是 凸 集顶 点 ： 如 果 对 于 凸 集 C 中 的 点 X ， 不 存 在 C 中 的 任 意 其 它 两个 不 同 的 点 ， 使 得 X 在 它 们 的 连 线 上 ， 这 时 称 X 为 凸集 的 顶 点 。 21 XX、 3.1 预 备 知 识 2021-4-28 29 3.2 线 性 规 划 问 题 基 本 定 理定 理 1:若 线 性 规 划 问 题 存 在 可 行 解 ， 则 问 题 的 可 行 域 是 凸 集 。证 明 :设 是 线 性 规 划 的 任 意 两 个 可 行 解 ， 则21,XX 0, ,0, 22 11 XbAX XbAX于 是 对 于 任 意 的 ，

18、设 ， 则 )10(, 0)1( 21 XXX bbb AXAX XXAAX )1( )1( )1( 21 21 所 以 也 是 问 题 的 可 行 解 ， 即 可 行 域 是 凸 集 。 21 )1( XXX 2021-4-28 30 引 理 : 线 性 规 划 问 题 的 可 行 解 X为 基 可 行 解 的 充 要 条 件 是 X的正 分 量 所 对 应 的 系 数 列 向 量 线 性 无 关 。证 明 :设 （ 1） 必 要 性 显 然 。 （ 2） 设 A 的 秩 为 m。 可 行 解 X 的 前 k 个 分 量 为 正 ， 且 它 们 对 应的 系 数 列 向 量 线 性 无 关

19、， 则 。 当 时 ， 恰 好 构 成 一 组 基 ， 而 就 是 这 组 基 对 应 的 基 可 行 解 。TnxxxX ),.,( 21) ) kPPP ,., 21 mkmk mPPP ,., 21 TmxxxX )0,.0,.,( 21 当 时 ， 在 基 础 上 从 其 余 列 向 量 中 可 以 找 出个 线 性 无 关 的 向 量 ， 恰 好 构 成 一 组 基 ， 而 X 就 是 这 组 基 对 应 的 基 可 行 解 。 mk kPPP ,., 21 km 2021-4-28 31 定 理 2: 线 性 规 划 问 题 的 基 可 行 解 X 对 应 线 性 规 划 问 题

20、可 行 域 （ 凸 集 ） 的 顶 点 。 i 证 明 :问 题 即 是 要 证 明 : X是 基 可 行 解 X是 可 行 域 顶 点 ， 也 即 要 证 明其 逆 否 命 题 ： X不 是 基 可 行 解 X不 是 可 行 域 顶 点 。（ 1） X不 是 基 可 行 解 X不 是 可 行 域 顶 点 。假 设 X是 可 行 解 ， 但 不 是 基 可 行 解 ， X 的 前 k 个 分 量 为 正 ,其 余 分 量 为 0，则 有又 X不 是 基 可 行 解 ， 所 以 由 引 理 知 ， 正 分 量 对 应 的 列 向 量线 性 相 关 。 即 存 在 一 组 不 全 为 零 的 数

21、， 使 得)1(1 ki ii bxP kPPP ,., 21)2(01 ki iiP 2021-4-28 32 用 非 零 常 数 乘 以 上 式 得 ：（ 1） +（ 3） 得 ：（ 1） -（ 3） 得 ：令 选 择 合 适 的 ， 使 得 所 有 的于 是 均 是 可 行 解 ， 并 且 ， 所 以 X 不 是 可 行域 顶 点 。 )3(01 ki iiP )4()(.)()(1 111 ki kkkiii bPxPxPx )5()(.)()( 1 111 ki kkkiii bPxPxPx 0,.,0),(),.,( 112 kkxxX 0,.,0),(),.,( 111 kkxx

22、X ),.,2,1(,0 kix ii 21,XX 21 2121 XXX 2021-4-28 33 （ 2） X不 是 可 行 域 顶 点 X不 是 基 可 行 解 。设 不 是 可 行 域 的 顶 点 ， 因 而 可 以 找 到 可 行 域 内另 两 个 不 同 的 点 ， 使 得 ， 用 分 量 表 示 即 为 ： TkxxxX )0,.0,.,( 21 0),.,( 21 TnyyyY 0),.,( 21 TnzzzZ0)1( ZYX ),.,2,1,10(,0)1( njzyx jjj 易 知 ， 当 时 ， 必 有 所 以 0 jx ,0jy ),.,1(,0 nkjzj ,)0,

23、.0,.,( 21 TkyyyY TkzzzZ )0,.0,.,( 21所 以 )1(1 kj jj byP )2(1 kj jj bzP于 是 （ 1） -（ 2） 得 kj jjj Pzy1 0)(而 不 全 为 零 ， 于 是 知 线 性 相 关 ， X不 是 基 可 行 解 。 jj zy kPPP ,., 21 2021-4-28 34 定 理 3: 若 线 性 规 划 问 题 有 最 优 解 ， 一 定 存 在 一 个 基 可 行 解 是 最 优 解 。引 理 ： 有 界 凸 集 中 的 任 何 一 点 均 可 表 示 成 顶 点 的 凸 组 合 。证 明 :假 设 是 可 行 域

24、 顶 点 ， 不 是 可 行 域 顶 点 ， 且 目 标函 数 在 处 达 到 最 优 ， 即 。kXXX ,., 21 0X0X 0CXz 由 引 理 知 ： 可 表 示 为 的 凸 组 合 ， 即0X kXXX ,., 21 ki iikkXXXX 122110 1,0,. 因 此 ki ki iiii CXXCCX 1 10 假 设 是 所 有 中 最 大 者 ， 则mCX iCX ki mmiki ii CXCXCXCX 110 2021-4-28 35 而 是 目 标 函 数 的 最 大 值 ， 所 以 也 是 最 大 值 ，也 即 ， 目 标 函 数 在 可 行 域 的 某 个 顶

25、 点 达 到 了 最 优 。0CX 0CXCXm 从 上 述 三 个 定 理 可 以 看 出 ， 要 求 线 性 规 划 问 题 的 最优 解 ， 只 要 比 较 可 行 域 （ 凸 集 ） 各 个 顶 点 对 应 的 目标 函 数 值 即 可 ， 最 大 的 就 是 我 们 所 要 求 的 最 优 解 。 单 纯 形 方 法 的 基 本 思 路自 从 1947年 丹 齐 格 （ G.B Dantzig） 提 出 单 纯 形 方 法 以 来 ， 迄今 为 止 仍 是 求 解 线 性 规 划 问 题 的 最 有 效 的 方 法 。 在 介 绍 这 种 方法 之 前 ， 先 通 过 一 个 例 子

26、 介 绍 单 纯 形 方 法 的 基 本 思 想 。例 用 消 元 法 解 线 性 规 划 问 题 . 124 164 82 52 41 321 xx xx xxx (1.3.1) 1 21 2 1 3 4 52 32 3 0(1.3.1) (1.3.1) , ,S x xS x x B p p p 的 非 负 解 ， 且 使 目 标 函 数 取 到 最 大 值 。 将 (1.2.4)中 的 目 标 函 数 改 为 ： 并 代 入 式 。 注 意 到 式 中 ， 是 只 选 定 基 ，解 求 解 线 性 规 划 问 题 （ 1.2.4） ， 实 际 上 是 求 线 性 方 程 组 3 1 24

27、 18 21x x xx 每 一 个 基 变 量 只 出 现 在 一 个 方 程 中 且 系 数 等 于 ， 每 个 方 程 中 只 含有 一 个 基 变 量 ， 并 且 目 标 函 数 所 在 的 方 程 中 基 变 量 的 系 数 等 于 0。以 后 每 一 步 初 等 变 换 都 要 按 照 这 个 要 求 去 做 。 为 了 求 (1.3.1)的 非 负 解 ， 我 们 在 解 方 程 组 时 ， 要 求 右 端 常 数项 非 负 ， 当 自 由 未 知 量 （ 非 基 变 量 ） 取 0时 ， 基 变 量 的 取 值 就 是 其表 达 式 右 端 的 常 数 项 的 值 ， 这 样

28、就 可 以 得 到 基 可 行 解 。 (1.3.1)等价 于 1 1 25 2 (1)1 2 11 1 2 1 22 3 4 5 56 4 2 312 40 (0,0,8,16,12)0 2 3 , 0, , 0 Tx S x xx xx x B xS S x x x xx x x x x ， 令 ， 得 对 应 于 可 行 基 的 基 可 行 解 ，对 应 的 目 标 函 数 值 。 从 目 标 函 数 的 表 达 式 可 以 看 出 ， 若 不 取 值 ， 则可 使 目 标 函 数 值 增 大 。 增 大 的 值 ， 使 得 的 值 不 小 于 ， 首 2 5 2 3 4 21 3 51

29、 42 5 1 53 1 5 14 1 1 5 1 542 5 1 12143412 341 4 0 , ,(1.3.1) 24 1632 9(1.3.2) 216 4 2 3(3 ) 9 2 3 x x B p p px x xx xx xS x xx x xx x S x x x x x xx 先 变 为 ， 成 为 基 变 量 ， 退 出 基 变 量 。 得 对 应 基 ，由 式 施 行 初 等 变 换 得 ： 式 等 价 于 ， 令 (2)5 220 (0,3,2,16,0)9 Tx BS ， 得 对 应 于 可 行 基 的 基 可 行 解 ，对 应 的 目 标 函 数 值 。 x (

30、1.3.2) 安 徽 省 十 一 五 规 划 教 材 1 5 11 3 4 23 1 33 1 4 2 1 3 53 4 52 53 5 34121414 9 2 , , , (1.3.2) 24 2 832 13(1.3.3) S x x xx x x xx x xx x xx x xx xS x xx 从 目 标 函 数 的 表 达 式 可 以 看 出 ， 若 不 取 0值 ， 则 可 使 目 标 函 数 增 大 。 增 大 的 值 ， 使 得 的 值 不 小于 零 ， 首 先 变 为 零 ， 成 为 基 变 量 ， 退 出 基 变 量 。 得 对 应 基， 由 式 施 行 初 等 行 变

31、 换 得 ：式 等 价 于B p p p11 3 52 14 3 5 3 5412 5428 4 2 13 23 x xx x x S x xx x ， (1.3.3) 安 徽 省 十 一 五 规 划 教 材 3 5 3(3) 3 13 545 5 1 4 2 4 54 4 1 5 20 (2,3,0,8,0) 1313 20, , , , (1.3.3)Tx x BSS x xx xx x x x xx 令 ， 得 对 应 于 可 行 基 的 基 可 行 解， 。 从 目 标 函 数 的 表 达 式 可 以 看 出 ， 若不 取 值 ， 则 可 使 目 标 函 数 值 增 大 。 增 大 的

32、 值 ， 使 得的 值 不 小 于 零 ， 首 先 变 为 零 ， 成 为 基 变 量 ，退 出 基 变 量 。 得 对 应 基 ， 由 式 施行 初 等 变 换 得 ： x B p p p11 4413 4 521 12 3 42 8 13 48 42 422 14(1.3.4) x xx x xx x xS x x 等 价 于 (1.3.4) 安 徽 省 十 一 五 规 划 教 材 11 44 31 15 3 4 3 42 2 81 12 3 52 8 (4)3 4 444 2 14 142 0 (4,2,0,0,4) 14Tx xx x x S x xx x xx x S ，令 ， 得

33、基 可 行 解 ， 即 为 最优 解 。 x (1) (2) (3)(4)(0,0) (0,3) (2,3) (4,2)o D C B与 图 解 法 相 对 照 ， 、 、和 对 应 的 分 别 为 图 1.2.1中 的、 、 和 ，目 标 函 数 不 断 增 大 ， 最 后 取 得 最优 解 。 如 果 把 (1.3.1)-(1.3.4)用 表格 的 形 式 表 现 出 来 ， 每 一 个 表 都是 单 纯 形 表 (表 1.3.1-表 1.3.4)，单 纯 形 表 的 迭 代 过 程 就 是 单 纯 形方 法 。 x x xx 2 4 6 8 x1246O ABCD 2x1+3x2=6 x

34、2 x1=4 x2=3 x 1+2x2=8图 1.2.1 2021-4-28 43 3.3 确 定 初 始 基 可 行 解寻 求 最 优 解 的 思 路 ： 线 性 规 划 问 题 的 最 优 解 一 定 会 在基 可 行 解 中 取 得 ， 我 们 先 找 到 一 个 初 始 基 可 行 解 。 然后 设 法 转 换 到 另 一 个 基 可 行 解 ， 并 使 得 目 标 函 数 值 不断 增 大 ， 直 到 找 到 最 优 解 为 止 。设 给 定 线 性 规 划 问 题 ： ），（ ），（ njx mibxa xczj inj jij nj jj 10 1max1 1 2021-4-28

35、 44 因 此 约 束 方 程 组 的 系 数 矩 阵 为 ： 100 010 00121 22221 11211 mnmm nnaaa aaa aaa添 加 松 弛 变 量 得 其 标 准 形 为 ： ），（ ），（ njx mibxxa xxczj isinj jij mi sinj jj 1 0 1 0max1 11 2021-4-28 45 由 于 该 矩 阵 含 有 一 个 单 位 子 矩 阵 ， 因 此 ， 这 个 单 位 阵 就 是 一 组基 ， 就 可 以 求 出 一 个 基 可 行 解 ： TmbbX ,0,0 1 说 明 ： 如 果 约 束 条 件 不 全 是 形 式 ，

36、如 含 所 有 形 式 ，则 无 法 找 到 一 个 单 位 阵 做 为 一 组 基 ， 这 时 需 要 添 加 人 工 变 量 。后 面 的 内 容 介 绍 。 ,称 其 为 初 始 基 可 行 解 。 2021-4-28 46 3.4 从 初 始 基 可 行 解 转 换 为 另 一 个 基 可 行 解 思 路 ： 对 初 始 基 可 行 解 的 系 数 矩 阵 进 行 初 等 行 变 换 ， 构 造出 一 个 新 的 单 位 矩 阵 ， 其 各 列 所 对 应 的 变 量 即 为 一 组 新 的基 变 量 ， 求 出 其 数 值 ， 就 是 一 个 新 的 基 可 行 解 。 设 有 初

37、始 基 可 行 解 ， 并 可 设 前 m 个 分 量 非 零 ， 即 ， 于 是),.,( )0()0(2)0(1)0( nxxxX )0,.,0,x,.,x,x(X )0(m)0(2)0(1)0( )1(1 )0( mi ii bxP 2021-4-28 47 由 构 造 初 始 可 行 基 的 方 法 知 前 m 个 基 向 量 恰 好 是 一 个 单 位阵 ， 所 以 约 束 方 程 组 的 增 广 矩 阵 为 mnmnnjmmm jm jm bbbaaaaa aa aa . . . .1.00 . 0.10 0.01 21,2,1,1, ,21,2 ,11,1 bPPPPPP njm

38、m . 121 由 于 任 意 系 数 列 向 量 均 可 由 基 向 量 组 线 性 表 示 ， 则 非 基 向量 中 的 用 基 向 量 组 线 性 表 示 为 ：jP )n,.,1mj(,0PaPPaP m1i iijjm1i iijj 2021-4-28 48 )2(0)( 1 mi iijj PaP设 有 ， 则0（ 1） +（ 2） 得 ： )3()()( 1 )0(11 )0( bPPaxPaPxP jimi ijimi iijjmi ii 由 此 式 可 知 ， 我 们 找 到 了 满 足 约 束 方 程 组 的 另 一 个 解 ，)1(X )0,.,0,.,( )0(2)0(

39、21)0(1)1( mjmjj axaxaxX 要 使 其 成 为 可 行 解 ， 只 要 对 所 有 i=1,2,m ， 下 式 成 立0)0( iji ax 要 使 其 成 为 基 可 行 解 ， 上 面 m个 式 中 至 少 有 一 个 取 零 。（ 基 可 行 解 中 非 零 分 量 的 个 数 不 超 过 m 个 。 ）（ 与 比 较 ）)0,.,0,x,.,x,x(X )0(m)0(2)0(1)0( 2021-4-28 49 只 要 取 ljlijiji axaax )0()0( 0min 于 是 前 m个 分 量 中 的 第 l个 变 为 零 ， 其 余 非 负 ， 第 j个 分

40、 量 为正 ， 于 是 非 零 分 量 的 个 数 ， 并 可 证 得线 性 无 关 ， 所 以 是 新 的 基 可 行 解 。 jmll PPPPPP ,. 1121 )1(X m 2021-4-28 50 3.4 最 优 性 检 验 和 解 的 判 别设 有 基 可 行 解 TnxxxX 00201)0( , )0,.,0,.,( )0(2)0(21)0(1)1( mjmjj axaxaxX 比 较 两 者 对 应 的 目 标 函 数 值 ， 哪 一 个 更 优 ？ mi iixcz 1 0)0( mi ijijjijmi ii acczcaxcz 1)0(1 0)1( )()( 2021

41、-4-28 51 2） 若 对 所 有 的 ， 则 ， 就 是 最 优 解 。 0)( 1 mi ijijj acc )0()1( zz )0(z mi ijijj acc 1 是 判 断 是 否 达 到 最 优 解 的 标 准 ，称 为 检 验 数 。1） 当 时 ， ， 目 标 函 数 值 得 到了 改 进 ， 不 是 最 优 解 ， 需 要 继 续 迭 代 。0)( 1 mi ijijj acc )0()1( zz )0(z易 知 2021-4-28 52 1. 当 所 有 时 ， 现 有 顶 点 对 应 的 基 可 行 解 即 为 最 优解 。2. 当 所 有 时 ， 又 对 某 个

42、非 基 变 量 有 则 该 线 性 规 划 问 题 有 无 穷 多 最 优 解 。3. 如 果 存 在 某 个 ， 又 向 量 的 所 有 分 量 ，对 任 意 ， 恒 有 ， 则 存 在 无 界解 。 kx0j 0j 0k0 j jP 0ija0 00 iji ax 结 论 2021-4-28 53 4 单 纯 形 法 的 计 算 步 骤 Max(min)Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn =b1a21x1+ a22x2+ a2nxn=b2 a m1x1+ am2x2+ amnxn =bmxj 0(j=1,n)设 有 线 性 规 划 问 题 ： 2021

43、-4-28 54 (1)找 到 初 始 可 行 基 ， 建 立 初 始 单 纯 形 表 .(4) 重 复 二 、 三 两 步 ， 直 至 找 到 最 优 解 。 4 单 纯 形 法 的 计 算 步 骤 (2)进 行 最 优 性 检 验 。计 算 检 验 数 ， 若 所 有 0 则 得 最 优 解 ， 结 束 .否 则 转 下 步 .若 某 0 而 0 ， 则 最 优 解 无 界 ， 结 束 .否 则 转 下 步 .k kP j(3)从 一 个 可 行 解 转 换 到 另 一 个 目 标 函 数 值 更 大 的基 可 行 解 。由 最 大 增 加 原 则 确 定 进 基 变 量 ； 由 最 小

44、比 值 原 则 选 择 出 基 变量 ； 以 为 主 元 素 进 行 换 基 迭 代 。 lka 2021-4-28 550 01 (1)找 到 初 始 可 行 基 ， 建 立 初 始 单 纯 形 表 .0CBC BX bZ bCBmccc21 mxxx21 mbbb21 mcc .1 mxx .1 nm xx j1 x. m21 mi ijij acc 1100 nm cc j1 c. mjjjaaa211, 1,2 1,1 mmmmaaa mnnnaaa21 mi inin acc 1 mi miim acc 1 1,10 ml PPPP .21 是 初 始 基 。 2021-4-28 5

45、6 (2)进 行 最 优 性 检 验计 算 检 验 数 ， 若 所 有 0 则 得 最 优 解 ， 结 束 .否 则 转 下 步 .若 某 0 而 0 ， 则 最 优 解 无 界 ， 结 束 .否 则 转 下 步 .k kP j mi ijijj acc 1检 验 数 的 计 算 方 法 ：基 变 量 的 检 验 数 一 定 为 0。 判 断 是 否 达 到 最 优 时 ， 只 要 考 虑非 基 变 量 检 验 数 。 2021-4-28 57 (3)从 一 个 可 行 解 转 换 到 另 一 个 目 标 函 数 值 更 大 的基 可 行 解 。由 最 小 比 值 原 则 选 择 出 基 变

46、量 ； lklikikii abaab /0/min kjjjk x 0max 进 基 变 量 由 最 大 增 加 原 则 确 定 进 基 变 量 ： 当 某 些 非 基 变 量 的 检 验 数 时 ， 为 使 目 标 函 数 值增 加 地 更 快 ， 一 般 选 择 正 检 验 数 中 最 大 者 对 应 的 非 基 变量 进 基 ， 成 为 新 的 基 变 量 。 0j为 确 保 新 的 基 可 行 解 的 非 零 分 量 非 负 ， 按 下 述 规 则 求 得 最 小比 值 ， 其 所 对 应 的 原 基 变 量 中 的 出 基 。 lx于 是 ， 新 的 一 组 基 是 ： kmll

47、PPPPPP ,. 1121 2021-4-28 58 以 为 主 元 素 进 行 换 基 迭 代 ：即 利 用 初 等 行 变 换 将 进 基 变 量 所 在 的 系 数 列 变 为 单 位列 向 量 ， 而 变 为 1。 这 样 原 来 基 矩 阵 中 的 就 不 再是 单 位 向 量 ， 取 而 代 之 的 是 ， 这 样 就 找 到 了 一 组 新 的基 。 lka kxlka lPkP(4) 重 复 二 、 三 两 步 ， 直 至 找 到 最 优 解 。说 明 ： 若 目 标 函 数 是 求 最 小 ， 可 以 不 必 将 其 转 变 为 求 最 大 ， 但 在 使 用 单 纯 形

48、法 求 解 时 ， 确 定 进 基 变 量 ， 应 找 负 检 验 数 中 最 小 者 ， 并 应 以 检 验 数 全 部 为 正 作 为 判 别 最 优 的 条 件 。 2021-4-28 59 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 解 将 模 型 标 准 化例 maxZ=3x1 +5x2 x1 8 2x2 12 3x1+4x2 36 x1 ， x2 0 2021-4-28 60 Cj 比值CB XB b检 验 数 j x1 x2

49、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 ijijj acc 1 lklikikii abaab /0/min 2021-4-28 61检 验 数 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-4 Cj 比值CB XB b检 验 数 j x1 x2 x3 x4 x53 5 0 0 08 1 0

50、 1 0 012 0 2 0 1 036 3 4 0 0 1x3x4x5000 0 3 5 0 0 0 -12/2=636/4=9 2021-4-28 62 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 202

51、1-4-28 63 n 特 殊 情 况 ：（ 1） 出 现 两 个 或 两 个 以 上 相 同 的 最 大 ， 此时 可 任 选 一 个 所 对 应 的 变 量 作 为 进 基 变 量 。 （ 2） 利 用 规 则 决 定 出 基 变 量 时 ， 出 现 两 个 或两 个 以 上 的 最 小 比 值 ， 则 迭 代 后 ， 会 出 现 一个 或 几 个 基 变 量 等 于 零 的 情 况 ， 我 们 称 此 为 退 化现 象 。 进 而 可 能 会 出 现 迭 代 过 程 的 循 环 ， 致 使 永远 达 不 到 最 优 解 。出 现 退 化 现 象 时 ， 可 考 虑 采 用 “ 勃 兰 特

52、 ” 规 则 决定 进 基 变 量 和 出 基 变 量 的 选 择 。 jj 单 纯 形 法 计 算 中 用 规 划 确 定 换 出 变 量 时 ， 有 时 存 在 两 个以 上 相 同 的 最 小 比 值 ， 这 样 在 下 一 次 迭 代 中 就 有 一 个 或几 个 基 变 量 等 于 零 ， 这 就 出 现 了 退 化 解 ， 当 出 现 退 化 时 ，进 行 多 次 迭 代 ， 而 基 又 返 回 到 最 初 的 情 形 ， 即 出 现 计 算过 程 的 循 环 ， 使 永 远 达 不 到 最 优 解 。 为 解 决 这 个 问 题 我们 介 绍 勃 兰 特 规 则 ： （ 1） 当

53、 存 在 两 个 或 两 个 以 上 最 大 检 验 数 时 ， 选 取 中 下标 最 小 的 非 基 变 量 为 换 入 变 量 ； （ 2） 当 按 规 则 计 算 时 ， 存 在 两 个 或 两 个 以 上 最 小 比 值时 ， 选 取 下 标 最 小 的 基 变 量 为 换 出 变 量 。 2021-4-28 65 5.1 人 工 变 量 n 用 单 纯 形 法 解 题 时 ， 需 要 有 一 个 单 位 阵 作 为 初始 基 。n 当 约 束 条 件 都 是 “ ” 时 ， 加 入 松 弛 变 量 就 形 成了 初 始 基 。n 但 实 际 存 在 “ ” 或 “ ” 型 的 约 束

54、 ， 没 有 现 成的 单 位 矩 阵 。n 采 用 人 造 基 的 办 法 ： 添 加 5 单 纯 形 法 的 进 一 步 讨 论 2021-4-28 66 人 工 单 位 矩 阵 的 构 造 方 法 在 “ ” 的 不 等 式 约 束 中 减 去 一 个 剩 余 变 量 后 可 变 为等 式 约 束 ， 但 此 剩 余 变 量 的 系 数 是 （ -1） ， 所 以 再 加 入一 个 人 工 变 量 ， 其 系 数 是 （ +1） ， 因 而 在 系 数 矩 阵 中 可得 到 一 个 相 应 的 单 位 向 量 ， 以 便 构 成 初 始 单 位 阵 ， 即 初始 基 矩 阵 。 在 原

55、本 就 是 “ = ”的 约 束 中 可 直 接 添 加 一 个 人 工 变 量 ，以 便 得 到 初 始 基 矩 阵 。注 意 ： 人 工 变 量 是 在 等 式 中 人 为 加 进 的 ， 只 有 它 等 于 0时 ，约 束 条 件 才 是 它 本 来 的 意 义 。 求 解 带 人 工 变 量 的 线 性 规 划 有 两 种 方 法 ： 大 M法 两 阶 段 法 2021-4-28 67 5.2 大 M法 没 有 单 位 矩 阵 ， 不 符 合 构 造 初 始 基 的 条 件 ， 需 加 入 人 工 变量 。 人 工 变 量 最 终 必 须 等 于 0才 能 保 持 原 问 题 性 质

56、不 变 。 为 保 证人 工 变 量 为 0， 在 目 标 函 数 中 令 其 系 数 为 （ -M） 。（ 求 最 小 值 问 题 中 ， 人 工 变 量 系 数 取 M） M为 无 限 大 的 正 数 ， 这 是 一 个 惩 罚 项 ， 倘 若 人 工 变 量 不 为 零 ，则 目 标 函 数 就 永 远 达 不 到 最 优 ， 所 以 必 须 将 人 工 变 量 逐 步 从基 变 量 中 替 换 出 去 。 如 若 到 最 终 表 中 人 工 变 量 仍 没 有 置 换 出 去 ， 那 么 这 个 问 题就 没 有 可 行 解 ， 当 然 亦 无 最 优 解 。 2021-4-28 68

57、 例 解 线 性 规 划 0, 93 12 4. 3max 321 32 321 321 31xxx xx xxx xxxts xxZ解 化 为 标 准 型 0, 93 12 4. 3max 54321 32 5321 4321 31 xxxxx xx xxxx xxxxts xxZ此 时 无 单 位 矩 阵 作 为 初 始 基 。 2021-4-28 69 添 加 人 工 变 量 ， 构 造 初 始 基 ： 0,., 93 12 4. 3max 71 732 65321 4321 7631xx xxx xxxxx xxxxts MxMxxxZ（ 求 最 小 值 问 题 中 ， 人 工 变 量

58、 系 数 取 M） 2021-4-28 70 -3 0 1 0 0 -M -Mx1 x2 x3 x4 x5 x6 x71 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3 1 0 0 0 1初 始 单 纯 形 表 ：j CCB XB b0 x4 4-M x6 1-M x7 9 -3-2M 4M 1 0 -M 0 0 4133 0 2 1 1 -1 0-2 1 -1 0 -1 1 06 0 4 0 3 -3 1 1-10 x4 30 x2 1-M x 7 6 -3+6M 0 1+4M 0 3M -3M 0 2021-4-28 71 -3 0 1 0 0 -M -Mx1 x2 x3 x

59、4 x5 x6 x7j CCB XB b 0 0 3 0 3/2 -M-3/2 -M+1/2 -33/20 0 0 1 -1/2 1/2 -1/20 1 1/3 0 0 0 1/31 0 2/3 0 1/2 -1/2 1/60 x4 00 x2 3-3 x1 1 -3/2 0 0 0 -3/4 -M+3/4 -M-1/40 x4 00 x2 5/21 x3 3/2 0 0 0 1 -1/2 1/2 -1/2-1/2 1 0 0 -1/4 1/4 1/43/2 0 1 0 3/4 -3/4 1/4 2021-4-28 72 此 时 人 工 变 量 全 部 出 基 ， 并 已 达 最 优 条 件

60、。最 优 解 为 )25,25,0(X ， 最 优 值 为 25Z注 意 ： 计 算 机 上 使 用 大 M法 时 ， 需 要 用 机 器 最 大 字 长 的 数 字代 替 M， 但 当 某 些 系 数 与 之 较 接 近 时 ， 还 是 可 能 会 出 错 。另 外 一 种 求 解 带 人 工 变 量 的 线 性 规 划 问 题 的 方 法 不 会 出 现 这 种问 题 -两 阶 段 法 。 2021-4-28 73 maxZ= 3x1 - x2 -2 x3 3x1 + 2 x2 -3 x3 =6 x1 - 2 x2 + x3 =4 x1 , x2 , x3 0S.t.例 解 线 性 规 划

61、 maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x 1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0解 按 大 M法 构 造 人 造 基 ， 引 入 人 工 变 量 x4 , x5 的 辅 助 问 题 如 下 ： 2021-4-28 74 作 出 单 纯 形 表 ， 进 行 迭 代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检

62、验 数 j 2 1 2/3 -1 1/3 02 0 -8/3 2 -1/3 10 -3-8M/3 1+2M -1-4M/3 0 x1x53-M 2021-4-28 75 检 验 数 j 2 1 2/3 -1 1/3 02 0 -8/3 2 -1/3 10 -3-8M/3 1+2M -1-4M/3 0 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最 优 解 :X*=(3,0,1)T， Z*=7 2021-4-28 76 5.3 两 阶 段 法 第 一 阶 段 ： 构 造 目

63、 标 函 数 只 含 人 工 变 量 的 线 性 规 划 问 题 ， 求 解 后 判 断 原 线 性 规 划 问 题 是 否 有 基 本 可 行 解 ， 若 有 ， 则 进 行 第 二 阶 段 ；第 二 阶 段 ： 将 第 一 阶 段 的 最 终 单 纯 形 表 所 对 应 的 解 ， 去 掉 人 工 变 量 ， 作 为 第 二 阶 段 的 初 始 单 纯 形 表 的 初 始 基 可 行 解 ， 进 行 单 纯 形 法 的 迭 代 。 2021-4-28 77 解 （ 1） 化 标 准 型 、 并 添 加 人 工 变 量 得 ： Min f = 2x1 + 3 x2 （ 此 处 未 将 目 标

64、 变 为 MAX） s.t. x1 + x2 x3 +x6 = 350 x1 - x4 +x7 =125 2 x1 + x2 +x5 =600 x1 , x2 , x3, x4, x5 ,x6,x7 0 例 ： 目 标 函 数 ： Min f = 2x1 + 3 x2 约 束 条 件 ：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 2021-4-28 78 （ 2） 构 造 第 一 阶 段 问 题 ： Min z = x6 +x7 (Max z = -x6 -x7) s.t. x1 + x2 x3 +x6 = 350 x1 - x4 +x7 =

65、125 2 x1 + x2 +x5 =600 x1 , x2 , x3, x4, x5 ,x6,x7 0 说 明 ： 原 问 题 目 标 函 数 无 论 是 求 MAX还 是 求 MIN， 构 造 的 第 一 阶 段 问 题 目 标 函 数 都 是 求 最 小 MIN。 2021-4-28 79 求 解 第 一 阶 段 问 题 ： 2021-4-28 80此 时 所 得 可 行 解 目 标 函 数 值 为 0， 故 原 规 划 问 题 有 基 可 行解 。 转 入 第 二 步 。 2021-4-28 81 （ 3） 去 掉 人 工 变 量 ， 得 到 第 二 阶 段 的 单 纯 形 表 ， 在

66、 此 基 础 上 继 续 求 解 。最 优 解 为 ： 125,100,250 421 xxx 2021-4-28 82 5.4 关 于 解 的 不 同 情 况 的 判 别 1、 无 穷 多 最 优 解例 ： 0, 15 5 16 4 1222 21 21 21xx xx xx 21 33max xxz 解 ： 将 问 题 化 为 标 准 型 ： 0., 15x 5 16x 4 1222 51 52 41 321 xx xx xxx 21 33max xxz 2021-4-28 83 2021-4-28 84 从 上 表 中 可 知 ， 已 达 最 优 解 ， 为 ，而 ， 若 将 选 为 进 基 变 量 迭 代 后 ， 可 得 另 一 最 优解 。 )5,0,0,2,4(1 Z04 4x)0,4,0,3,3(2 Z上 述 两 最 优 解 分 别 对 应 两 个 顶 点 ， 而 两 点 连 线 上 的 点 均是 最 优 解 ， 故 有 无 穷 多 最 优 解 。 判 别 无 穷 多 最 优 解 的 方 法 ： 单 纯 形 表 的 检 验 数 行 已 达 最有 性 条 件 （ 全 部 小