线性规划及单纯形法

《线性规划及单纯形法》由会员分享，可在线阅读，更多相关《线性规划及单纯形法（137页珍藏版）》请在装配图网上搜索。

1、运 筹 学 在 军 事 上 ， 史 记 ： 决 胜 千 里 之 外 , 运 筹 帷 幄 之 中 .田 忌 赛 马 。运 筹 学 ： operational research在 工 程 上 ， 丁 渭 修 皇 宫 。 运 筹 学 的 主 要 内 容线 性 规 划数学规划 非 线 性 规 划整 数 规 划动 态 规 划学科内容 多 目 标 规 划双 层 规 划组合优化 最 优 计 数 问 题网 络 优 化排 序 问 题统 筹 图 随机优化 对 策 论排 队 论库 存 论决 策 分 析可 靠 性 分 析 线 性 规 划 及 单 纯 形 法v线 性 规 划 问 题 及 其 数 学 模 型v图 解 法v

2、单 纯 形 法 原 理v数 学 试 验 第 一 节 线 性 规 划 问 题 及 其 数 学 模 型一 。 问 题 的 提 出线 性 规 划 主 要 解 决 ： 如 何 利 用 现 有 的 资 源 ， 使 得 预 期 目 标 达到 最 优 。例 1 美 佳 公 司 计 划 制 造 、 两 种 家 电 产 品 。 已 知 各 制 造 一件 时 分 别 占 用 的 设 备 A、 B的 台 时 、 调 试 工 序 及 每 天 可 用 于这 两 种 家 电 的 能 力 、 各 售 出 一 件 时 的 获 利 情 况 ， 如 表 1-1所示 。 问 该 公 司 应 制 造 两 种 家 电 各 多 少 件

3、， 使 获 取 的 利 润 最 大 ？ 项 目 每 天 可 用 能 力设 备 A (h)设 备 B (h)调 试 工 序 (h) 061 521 15245利 润 （ 元 ） 2 1表 1-1解 ： 设 公 司 制 造 、 两 种 家 电 分 别 为 件 。 , 1x 2x问 题 ： x1=? x2=? 利 润 Z 最 大 ？设 备 A工 时 限 制 ： 155 2 x设 备 B工 时 限 制 ： 2426 21 xx 解 ： 公 司 制 造 、 两 种 家 电 分 别 为 件 。 ,1x 2x调 试 工 序 时 间 限 制 ： 521 xx利 润 ： 212 xxZ 即 要 求 ： 212m

4、ax xxZ 项 目 每 天 可 用 能 力设 备 A (h)设 备 B (h)调 试 工 序 (h) 061 521 15245利 润 （ 元 ） 2 1表 1-1 212max xxZ 目 标 函 数约 束 条 件 资 源 约 束非 负 约 束其 中 ,约 束 条 件 可 记 s. t. (subject to), 意 思 为 “ 以 为 条件 ” “ 假 定 ” 、 “ 满 足 ” 之 意 。 0, 52426 15521 21 21 2xx xx xx x 212max xxZ 21 21 21 25 156 2 24. 5, 0 xx xst x xx x 例 2： 捷 运 公 司

5、在 下 一 年 度 的 1 4月 份 的 4个 月 内 拟 租 用 仓 库堆 放 物 资 。 已 知 各 月 份 所 需 仓 库 面 积 列 于 下 表 1-2。 仓 库 租借 费 用 随 合 同 期 而 定 ， 期 限 越 长 ， 折 扣 越 大 ， 具 体 数 字 见 表1-3。 租 借 仓 库 的 合 同 每 月 初 都 可 办 理 ， 每 份 合 同 具 体 规 定租 用 面 积 和 期 限 。 因 此 该 厂 可 根 据 需 要 ， 在 任 何 一 个 月 初 办理 租 借 合 同 。 每 次 办 理 时 可 签 一 份 合 同 ， 也 可 签 若 干 份 租 用面 积 和 租 用

6、期 限 不 同 的 合 同 。 试 确 定 该 公 司 签 订 租 借 合 同 的最 优 决 策 ， 目 的 是 使 所 租 借 费 用 最 少 。 月 份 1 2 3 4所 需 仓 库 面 积 15 10 20 12表 1-2表 1-3合 同 租 借 期 限 1个 月 2个 月 3个 月 4个 月合 同 期 内 的 租 费 2800 4500 6000 7300单 位 ： 100m2单 位 ； 元 /100m2解 ： 设 表 示 捷 运 公 司 在 第 i (i=1,2,3,4)月 初 签 订 的 租 期 为 j (j=1,2,3,4)个 月 的 仓 库 面 积 的 合 同 （ 单 位 为

7、100m 2)。 ijx 月 份 1 2 3 4所 需 仓 库 面 积 15 10 20 12表 1-2表 1-3合 同 租 借 期 限 1个 月 2个 月 3个 月 4个 月合 同 期 内 的 租 费 2800 4500 6000 7300单 位 ： 100m2单 位 ； 元 /100m2 11x12x 11x12x13x14x 21x22x23x 31x32x 41x 15 10 20 1215 14131211 xxxx 10232221141312 xxxxxx 1241322314 xxxx 20323123221413 xxxxxx2800Z )( 41312111 xxxx 45

8、00 )( 322212 xxx 6000 )( 2313 xx 147300 x 经 过 上 面 的 讨 论 ， 得 到 下 面 的 LP模 型 ： )4,1;4,1(0 12 201015. 41322314 323123221413 232221141312 14131211 jix xxxx xxxxxx xxxxxx xxxxst ij )(4500)(2800min 32221241312111 xxxxxxxZ 142313 7300)(6000 xxx 目 标 函 数约 束 条 件 每 一 个 问 题 都 有 一 组 变 量 称 为 决 策 变 量 ， 一 般 记 为下 面 从

9、 数 学 的 角 度 来 归 纳 上 述 两 个 例 子 的 共 同 点 。 每 个 问 题 中 都 有 决 策 变 量 需 满 足 的 一 组 约 束 条 件 线 性的 等 式 或 不 等 式 。 ., 21 nxxx 对 决 策 变 量 每 一 组 值 ： Tnxxx ),( )0()0(2)0(1 代 表 了一 种 决 策 方 案 。 通 常 要 求 决 策 变 量 取 值 非 负 ， 即).,2,1(,0 nixi 二 。 线 性 规 划 问 题 的 数 学 模 型 都 有 一 个 关 于 决 策 变 量 的 线 性 函 数 称 为 目 标 函 数 。 要求 这 个 目 标 函 数 在

10、 满 足 约 束 条 件 下 实 现 最 大 化 或 最 小 化 。将 约 束 条 件 及 目 标 函 数 都 是 决 策 变 量 的 线 性 函 数 的 规 划 问 题称 为 线 性 规 划 。 有 时 也 将 线 性 规 划 问 题 简 记 为 LP（ linear programming)其 数 学 模 型 为 ： nnxcxcxcZ 2211max(min)11 1 12 2 1 121 1 22 2 2 21 1 2 2 ( , )( , ). ( , )0,( 1,2, , )n nn nm m mn n m ja x a x a x ba x a x a x bst a x a

11、x a x bx j n 上 述 模 型 的 简 写 形 式 为 ： nj jjxcZ 1max(min) ),2,1(0 ),2,1(),(. 1 njx mibxats jnj ijij 若 令 );,( 21 ncccC ;21 nxxxX ;21 mbbbb ),( 2121 22221 11211 nmnmm nn PPPaaa aaa aaaA 线 性 规 划 问 题 可 记 为 矩 阵 和 向 量 的 形 式 ：CXZ max(min) 0 ),(. X bAXts CXZ max(min) 0 ),(. 1 X bxPts nj jj用 向 量 表 示 时 ， 上 述 模 型

12、可 写 为 ： 三 。 线 性 规 划 问 题 的 标 准 形 式 ：LP问 题 的 数 学 模 型 的 标 准 形 式 为 ： nnxcxcxcZ 2211max ),2,1(,0. 2211 22222121 11212111 njx bxaxaxa bxaxaxa bxaxaxats j mnmnmm nn nn其 中 常 数 项 ,0ib ),2,1( mi LP问 题 标 准 形 式 的 特 征 是 ： 求 目 标 函 数 的 最 大 值 ； 约 束 条 件 为 变 量 满 足 线 性 方 程 组 与 非 负 性 两 部 分 ； 方 程 组 中 常 数 项 皆 非 负 。 下 面 分

13、 析 如 何 将 LP问 题 标 准 化 ： 若 目 标 函 数 为 nnxcxcxcZ 2211min引 进 新 的 目 标 函 数 ,ZZ 则 Z的 最 小 值 即 为Z 的 最 大 值ZZ maxmin从 而 目 标 函 数 变 换 为 ： nnxcxcxcZ 2211max即 ： 例 1 将 LP问 题 3212min xxxZ )2,1(0 222. 31 321 ix xx xxxts i化 为 标 准 形 。解 ： 引 进 新 的 目 标 函 数 ,ZZ 于 是 原 LP问 题 化 为 标 准 形 式 ： )2,1(0 222. 31 321 ix xx xxxts i 3212

14、max xxxZ 当 约 束 条 件 中 含 有 不 等 式 时 ， 如 ：例 2 将 LP问 题 1 2max 3 3Z x x )2,1(0 142 102. 21 21 ix xx xxts i化 为 标 准 形 。此 时 ， 对 102 21 xx 引 入 变 量 ,03 x 使 得 式 变 为 ：102 321 xxx 同 理 对 式 142 21 xx 引 入 变 量 ,04 x 使 得 式 变 为 ：142 421 xxx 于 是 原 LP问 题 化 为 标 准 形 式 ： 1 2max 3 3Z x x )4,3,2,1(0 142 102. 421 321 ix xxx xx

15、xts i引 进 变 量 x3,x4称 为 松 弛 变 量 。 例 3 将 LP问 题 1 2 3max 2Z x x x )3,2,1(0 62 142. 21 321 ix xx xxxts i化 为 标 准 形 。 对 式 引 进 变 量同 理 对 式 62 21 xx 引 入 变 量 ,05 x 使 得 式 变 为 ：62 521 xxx ,04 x 使 得 式 变 为 ：142 4321 xxxx引 进 变 量 x4,x5称 为 剩 余 变 量 。 1 2 3 4 5max 2 0 0Z x x x x x 1 2 3 41 2 52 14. 2 60 ( 1,2, ,5)ix x

16、x xst x x xx i 于 是 原 LP问 题 化 为 标 准 形 式 ： 若 约 束 条 件 中 线 性 方 程 式 的 常 数 项 为 负 数 ， 则 将 该 线 性方 程 式 两 端 乘 以 -1。 如 ：例 4 将 LP问 题 1 2 3 4max 3Z x x x x )4,3,2,1(0 21. 421 321 ix xxx xxxts i化 为 标 准 形 。 例 4 将 LP问 题 1 2 3 4max 3Z x x x x )4,3,2,1(0 21. 421 321 ix xxx xxxts i化 为 标 准 形 。 解 ： 将 式 两 边 乘 以 -1得 此 LP问

17、 题 的 标 准 形 式 ： 1 2 3 4max 3Z x x x x )4,3,2,1(0 21. 421 321 ix xxx xxxts i 若 变 量 lx 无 约 束 ， 则 引 进 两 个 非 负 变 量 ,0lx 0lx将 lx 表 示 为 ： lll xxx 例 5 将 LP问 题 1 2max 2Z x x )4,3,2(0 62 2. 421 321 ix xxx xxxts i化 为 标 准 形 。 例 5 将 LP问 题 1 2max 2Z x x )4,3,2(0 62 2. 421 321 ix xxx xxxts i化 为 标 准 形 。解 ： 111 xxx

18、将 上 式 代 入 目 标 函 数 及 约 束 条 件 中 ， 得 到 其 标 准 形 式 ：1 1 2max 2 2Z x x x )4,3,2(0,0,0 62 2. 11 4211 3211 ixxx xxxx xxxxts i 例 6 将 LP问 题 1 2max 3Z x x )2,1(0 16. 21 21 ix xx xxts i化 为 标 准 形 。解 ： 由 于 （ 2） 式 常 数 项 为 负 ， 不 等 式 两 边 乘 以 -1得 )2,1(0 16. 21 21 ix xx xxts i 1 2max 3Z x x )2,1(0 16. 21 21 ix xx xxts

19、 i 1 2max 3Z x x 解 ：引 进 松 弛 变 量 ： ,03 x 04 x 此 LP问 题 的 标 准 形 为 ：1 2max 3Z x x )4,3,2,1(0 16. 421 321 ix xxx xxxts i 第 二 节 图 解 法一 。 预 备 知 识 ：1。 平 面 上 一 条 直 线 可 把 平 面 分 成 三 部 分 ： 平 面 上 的 点 ，直 线 一 侧 的 点 ， 直 线 另 一 侧 的 点 。 y x0 5 5例 ： 5: 21 xxl用 集 合 表 示 ： ,5|),( 212121 Rxxxxxxl 521 xx2。 二 元 一 次 不 等 式 的 解

20、 集 代 表 一 个 平 面 域 。例 ： 521 xx 代 表 ： 5521 21 xx xx 3。 梯 度 ：定 义 ： 设 二 元 函 数 若 在 点 的 偏 导 数存 在 ， 则 称 向 量 ：),( 21 xxfz ,)( 10 xXf 20)(xXf )(,)( 2010 xXfxXf 为 ),( 21 xxfz 在 点 处 的 梯 度 。 记 ),( )0(2)0(10 xxX ),( )0( 2)0(10 xxX )(,)()( 20100 xXfxXfXf 其 几 何 意 义 是 ： 二 元 函 数 ),( 21 xxfz 在 某 点 ),( )0(2)0(10 xxX 沿

21、梯 度 正 向 为 增 加 最 快 的 方 向 。 例 ： 函 数 yxz 32 在 原 点 （ 0， 0） 处 的 梯 度 为,202 xz 330 yz 0 xy 23 )3,2(二 。 两 个 变 量 LP问 题 的 图 解 法图 解 法 步 骤 ： 根 据 约 束 条 件 画 出 可 行 域 。 根 据 目 标 函 数 Z的 表 达 式 画 出 目 标 直 线 Z=0,并 表 明 目 标函 数 增 加 的 方 向 。 在 可 行 域 中 ， 找 符 合 要 求 的 距 离 目 标 直 线 Z=0的 最 远 或最 近 点 ， 并 求 出 该 点 坐 标 。 例 1 解 LP问 题 ： 1

22、 2max 3Z x x 2,106 82. 1 21 ixx xxts i 画 出 可 行 域 。 82 21 xx 61 x 1x2x4 860 令 Z=0,有 2130 xx 在 原 点 的 梯 度 ：1 23Z x x 1 3,xZ 2 1xZ 所 以 (3,1)Z )3,1( 12 3xx )3,1( 12 3xx 画 出 直 线 解 ： 例 1 解 LP问 题 ： 1 2max 3Z x x 2,106 82. 1 21 ixx xxts i在 原 点 的 梯 度 ： 1 23Z x x 1 3,xZ 2 1xZ 所 以 (3,1)Z 解 ： 82 21 xx 61 x 1x2x4

23、 860 3)3,1( )3,1( 112 3xx 例 1 解 LP问 题 ： 1 2max 3Z x x 2,106 82. 1 21 ixx xxts i解 ： 82 21 xx 61 x 1x2x4 860 31)3,1( )3,1( 随 着 直 线 112 3xx 12 3xx 沿 梯 度 方 向 去 扫 可 行 域 ，1 23Z x x 目 标 函 数中 的 Z在 增 加 。 如 ：经 过 点 )1,1( 时 ， 4.Z 例 1 解 LP问 题 ： 1 2max 3Z x x 2,106 82. 1 21 ixx xxts i解 ： 82 21 xx 61 x 1x2x4 860 3

24、1)3,1( )3,1( 112 3xx 随 着 直 线 12 3xx 沿 梯 度 方 向 去 扫 可 行 域 ，1 23Z x x 目 标 函 数中 的 Z在 增 加 。 如 ：经 过 点 )1,1( 时 ， 4.Z 例 1 解 LP问 题 ： 1 2max 3Z x x 2,106 82. 1 21 ixx xxts i解 ： 82 21 xx 61 x 1x4 860 31)3,1( )3,1( 1 )1,6(由 此 可 见 ， 当 目 标 函 数 沿梯 度 的 方 向 去 扫 可 行 域 时 ，在 顶 点 )1,6( 处 取 得 最 大 值 。从 而 得 最 优 解 ： 1621xx目

25、 标 函 数 的 最 优 值 为 ： max 3 6 1 19.Z 例 2 解 LP问 题 ： 1 2minZ x x )2,1(0 1. 21 ix xxts i解 ： 画 出 可 行 域 。 令 Z=0,有 210 xx 画 出 直 线 12 xx 在 原 点 的 梯 度 ：1 2Z x x 1 1,xZ 2 1xZ 所 以 (1, 1)Z 1x2x0 121 xx1 12 xx )1,1( 1 例 2 解 LP问 题 ： 1 2minZ x x )2,1(0 1. 21 ix xxts i解 ： 1x2x0 121 xx11 12 xx )1,1( 随 着 直 线 12 xx 沿 梯 度

26、 反 方 向 去 扫 可 行 域 ，1 2Z x x 目 标 函 数中 的 Z在 减 小 。 且 在 点 )1,0()1,0(处 取 得 最 小 值 。 从 而 得 最 优 解 ： 1021xx 目 标 函 数 的 最 优 值 为 ： max 0 2 1 2.Z 例 3 解 LP问 题 ： 1 2maxZ x x )2,1(0 42. 21 ix xxts i解 ： 1x2x0 画 出 可 行 域 。 令 Z=0,有 210 xx 画 出 直 线 12 xx 在 原 点 的 梯 度 ：1 2Z x x 1 1,xZ 2 1xZ 所 以 ( 1,1)Z 12 xx 42 21 xx)2,8(4

27、8)1,1( 例 3 解 LP问 题 ： 1 2maxZ x x )2,1(0 42. 21 ix xxts i解 ： 1x0 12 xx 42 21 xx)2,8(4 82x)1,1( 12 3xx 沿 梯 度 方 向 去 扫 可 行 域 ，1 23Z x x 目 标 函 数在 点 先 把 目 标 直 线 Z=0平 行地 拉 到 可 行 域 内 ， 再 让 直 线)0,4( 处 取 得 最 大 值 。从 而 得 最 优 解 ： 0421xx 目 标 函 数 的 最 优 值 为 ： max 4 0 4.Z 例 4 解 LP问 题 ： 1 2min 2 4Z x x 解 ： 2,10 20. 2

28、1 21 ix xx xxts i 画 出 可 行 域 。 令 Z=0,有 21 420 xx 画 出 直 线 122 xx 在 原 点 的 梯 度 ：1 22 4Z x x 1 2,xZ 2 4xZ 所 以 ( 2,4)Z 1x2x0 12 xx 221 xx2 2 122 xx )4,2( B A仅 为 AB线 段 。 1x2x0 12 xx 221 xx2 2 122 xx )4,2( B A 例 4 解 LP问 题 ： 1 2min 2 4Z x x 解 ： 2,10 20. 21 21 ix xx xxts i 由 于 目 标 函 数 是 减 小 ， 故 应 沿 梯 度 反 方 向

29、去 扫 可行 域 ， 先 把 目 标 直 线 拉 到 上 面 。 例 4 解 LP问 题 ： 1 2min 2 4Z x x 解 ： 2,10 20. 21 21 ix xx xxts i 1x2x0 12 xx 221 xx2 2 122 xx )4,2( B A 随 着 直 线 122 xx 1 22 4Z x x 目 标 函 数中 的 Z在 减 小 。 且 在 点处 取 得 最 小 值 。 从 而 得 最 优 解 ： 1121xx沿 梯 度 反 方 向 去 扫 可 行 域 ，A目 标 函 数 的 最 优 值 为 ： min 2 1 4 1 2.Z 例 5 解 LP问 题 ：1 2max

30、2Z x x 解 ： )2,1(024 62. 21 21 ixxx xxts i 画 出 可 行 域 。 令 Z=0,有 ,20 21 xx 画 出 直 线在 原 点 的 梯 度 ：1 22Z x x 1 1,xZ 2 2.xZ 所 以(1,2)Z 1x2x0 62 21 xx 41 x 22 x21 20 xx 21 20 xx )2,1( s 1x2x0 62 21 xx 41 x 22 x 21 20 xx )2,1( s例 5 解 LP问 题 ：1 2max 2Z x x 解 ： )2,1(024 62. 21 21 ixxx xxts i 随 着 直 线 沿 梯 度 方 向 去 扫

31、 可 行 域 ， 1 22Z x x 目 标 函 数中 的 Z在 增 加 。 直 到 与 直 线 21 20 xx 62 21 xx 重 合 。D C此 时 ， 线 段 CD上 的 所 有 点 均 是 最 优 解 。其 中 ， 点 C的 坐 标 为 ： ),1,4( 点 D的 坐 标 为 ： ).2,2( 1x2x0 62 21 xx 41 x 22 x 21 20 xx )2,1( s D C例 5 解 LP问 题 ：1 2max 2Z x x 解 ： )2,1(024 62. 21 21 ixxx xxts i回 忆 过 两 点 ),(),( dcBbaA的 直 线 方 程 式 ： ac

32、axbd bx 12从 而 ， 过 )2,2(),1,4( DC 的 直 线 方 程 为 ：42 412 1 12 xx 例 5 解 LP问 题 ：21 2max xxs 解 ： )2,1(024 62. 21 21 ixxx xxts i 1x2x0 62 21 xx 41 x 22 x 21 20 xx )2,1( s D C从 而 ， 过 )2,2(),1,4( DC 的 直 线 方 程 为 ：42 412 1 12 xx整 理 得 ： 321 12 xx )42( 1 x即 ： cxx cx 121 21 其 中 )42( c 例 6 解 LP问 题 ：1 2maxZ x x )2,1

33、(0 632. 21 ix xxts i解 ： 画 出 可 行 域 。 1x2x0 632 21 xx 令 Z=0,有 ,0 21 xx 画 出 直 线 12 xx 在 原 点 的 梯 度 ：1 2Z x x 1 1,xZ 2 1.xZ 所 以(1, 1)Z )1,1( s 随 着 直 线 沿 梯 度 方 向 去 扫 可 行 域 ， 1 2Z x x 目 标 函 数中 的 Z一 直 在 增 加 。 所 以 ， 此 LP问 题 无 最 优 解 。 12 xx 12 xx 为 无 界 域 。 例 7 解 LP问 题 ：1 2min 3Z x x 2,10 11. 21 21 ixxx xxts i

34、 0 1x2x 121 xx 121 xx111解 ： 画 出 可 行 域 。由 于 可 行 域 为 空 集 ， 所 以 此 LP问 题 无 可 行 解 ， 当 然 无 最 优 解 。 通 过 以 上 的 讨 论 ， LP问 题 的 解 有 下 面 四 种 类 型 ： 有 最 优 解 且 有 唯 一 的 最 优 解 。 有 可 行 解 且 有 无 穷 多 最 优 解 。 有 可 行 解 但 无 最 优 解 。(4) 无 可 行 解 补 充 知 识 ： 凸 集凸 集 ： 在 点 集 中 任 取 两 点 ， 则 其 连 线 仍 在 其 中 。即 没 有 凹 入 的 部 分 ； 没 有 空 洞 。

35、在 凸 集 中 ， 点 A， B， C， D称 为 极 点 （ 或 顶 点 ） 。A BCD 从 图 解 法 中 我 们 了 解 到 以 下 事 实 ： 若 LP问 题 的 可 行 域 存 在 ， 则 可 行 域 一 定 是 凸 集 。 若 LP问 题 的 最 优 解 存 在 ， 则 最 优 解 或 最 优 解 之 一 （ 如 果 有无 穷 多 最 优 解 的 话 ） 一 定 是 可 行 域 凸 集 的 某 个 极 点 （ 顶点 ） 。思 路 ： 最 优 解 先 在 可 行 域 中 找 。 （ 可 行 域 为 空 集 ， 则 无 可行 解 ， 故 无 最 优 解 。 ） 最 优 解 在 可 行

36、 域 的 极 点 中 找 。 极 点 是 有 限 个 ， 若 两 个 极 点 都 是 最 优 解 ， 则 两 个 极 点 所 连 线 段 上 的 所 有 点 均 是 最 优 解 ）定 义 ： LP问 题 的 可 行 域 的 极 点 （ 顶 点 ） 称 为 基 本 可 行 解 。 1.3 单 纯 形 法 原 理 1。 复 习 ： 非 齐 次 线 性 方 程 组 解例 ： 解 非 齐 次 线 性 方 程 组 52426 155 521 421 32 xxx xxx xx增 广 矩 阵 （ 1） 510011 2401026 1500150A 1x 2x 3x 4x 5x b 若 线 性 方 程 组

37、 没 有 现 成 的 基 ， 可 利 用 增 广 矩 阵 的 行 初 等 变 换法 找 到 一 组 基 。 为 基 变 量 。称 ,3x ,4x 5x其 变 量 个 数 = 3)()( ArAr此 方 程 组 的 解 为 215 214 23 5 2624 515 xxx xxx xx 其 中 ,1x 2x 为 任 意 实 数 。为 非 基 变 量 ， 或 自 由 变 量 。2x,1x称称 非 基 变 量 ,1x 2x 为 0的 解 （ 15， 24， 5， 0， 0） 叫 基 解 。TX )5,24,15,0,0( 0 若 对 （ 1） 式 中 的 变 量 再 加 上 非 负 限 制 215

38、 214 23 5 2624 515 xxx xxx xx 5,10 52426 155 521 421 32 ix xxx xxx xxi其 解 为 5,10 5 2624 515 215 214 23 ix xxx xxx xx i由 的 非 负 性 知 ：,3x ,4x 5x （ 2） 0 4 53 1x2x 5,10 05 02624 0515 215 214 23 ix xxx xxx xxi 0515 2 x5 05 21 xx 02624 21 xx从 而 ,1x 2x 解 域 为注 意 ： 此 时 的 ,1x 2x已 经 不 是 任 意 实 数 。不 是 自 由 变 量 了 。

39、 而 对 于 带 有 非 负 约 束 的 方 程 组 解 的 每 个 分 量 都 是 非 负 数 ， 就 叫 做 可 行 解 。如 果 基 解 是 可 行 的 ， 就 叫 基 可 行 解 。基 可 行 解 所 对 应 的 基 称 为 可 行 基 。 非 基可行 最 优 基基 非 可 行 基四 种 形 式 的基 之 间 的 关系 为 ： 基 与 解 的 对 应 关 系 ： 非 可 行 解可行 基 本解 可 行 解 基 本 解解 与 解 之 间的 关 系 为 ： 基 解基可 行 基 基 可 行 解最 优 基 基 最 优 解 5,10 05 02624 0515 215 214 23 ix xxx

40、xxx xxi,11 x 22 x 所 对 应 的 解例 如 T)2,14,10,2,1( 是 可 行 解 。,01 x 02 x 所 对 应 的 解 T)5,24,15,0,0( 是 基 解 。也 是 可 行 解 ， 故 而 是 基 本 可 行 解 。 （ 1） 式 中 为 一 组 可 行 基 。,3x ,4x 5x但 并 不 是 所 有 基 都 有 资 格 充 当 可 行 基 。 例 如 （ 1） 中 510011 2401026 1500150A （ -6） 510011 661040 1500150 510011 661040 1500150 524 23 521 646 5155 x

41、xx xx xxx所 对 应 的 方 程 组 为 ：令 非 基 变 量 ,2x 5x 为 0， 得 到 基 解 ： T)0,6,15,0,5( 非 可 行 解 。 即 , 431 xxx 非 可 行 基 。 基 可 行 解 很 重 要 ， 可 以 证 明 以 下 定 理 ：定 理 1 若 线 性 规 划 问 题 存 在 最 优 解 ， 则 问 题 的 可 行 域 是 凸 集 。定 理 2 线 性 规 划 问 题 的 基 可 行 解 对 应 线 性 规 划 问 题 可 行 域（ 凸 集 ） 的 顶 点 。定 理 3 若 线 性 规 划 问 题 最 优 解 存 在 ， 则 最 优 解 一 定 在

42、可 行 域 顶点 处 取 得 。由 此 可 看 出 ， 最 优 解 要 在 基 可 行 解 （ 可 行 域 顶 点 ） 中 找 。 通 过 以 上 分 析 ， 可 得 到 以 下 几 个 结 论 ：（ 1） 线 性 规 划 问 题 的 可 行 域 是 一 个 凸 集 ， 可 行 域 可 能 有界 ， 也 可 能 无 界 ， 但 其 顶 点 数 是 有 限 个 。 （ ？ ）（ 2） 线 性 规 划 问 题 每 个 基 本 可 行 解 对 应 于 可 行 域 的 一 个 顶点 。（ 3） 若 线 性 规 划 问 题 有 最 优 解 ， 则 必 可 在 其 可 行 域 的 某 个（ 或 多 个 ）

43、 顶 点 上 达 到 最 优 值 。 如 何 从 一 个 可 行 基 找 另 一 个 可 行 基 ？ 称 基 变 换 。定 义 ： 两 个 基 可 行 解 称 为 相 邻 的 ， 如 果 它 们 之 间 仅 变 换一 个 基 变 量 。 对 应 的 基 称 为 相 邻 可 行 基 。例 LP问 题 5,10 52426 155 521 421 32 ix xxx xxx xxi 54321 0002max xxxxxZ 当 前 可 行 基 所 对 应 的 基 本 可 行 解,3x ,4x 5xTX )5,24,15,0,0(0 相 应 地 ， 将 代 入 目 标 函 数 得 0)( 0 XZ显

44、 然 不 是 最 优 。 因 为 从 经 济 意 义 上 讲 ， ,01 x 02 x意 味 着 该 厂 不 安 排 生 产 ， 因 此 没 有 利 润 。0X从 数 学 角 度 看 ， 若 让 非 基 变 量 取 值 从 零 增 加 ，,1x 2x 54321 0002max xxxxxZ (对 应 可 行 域 的 )0,0(o 相 应 的 目 标 函 数 值 Z也 将 随 之 增 加 。 因 此 有 可 能 找 到 一 个新 的 基 本 可 行 解 ， 使 其 目 标 函 数 值 有 所 改 善 。 即 进 行 基 变换 ， 换 一 个 与 它 相 邻 的 基 。 再 注 意 到 前 的

45、系 数 5比 前 的 系 数 2大 ， 即 每 增 加 一 个 单 位 对 Z的 贡 献 比 大 。2x1x 2x1x故 应 让 从 非 基 变 量 转 为 基 变 量 ， 称 为 进 基 。 又 因 为 基 1x变 量 只 能 有 三 个 ， 因 此 必 须 从 原 有 的 基 变 量 ,3x ,4x 5x中 选 一 个 离 开 基 转 为 非 基 变 量 ， 称 为 出 基 。 谁 出 基 ？ 又 因 为 仍 留 作 非 基 变 量 ， 故 仍 有2x 02 x（ 2） 式 变 为 05 0624 015 15 143 xx xxx再 让 从 零 增 加 ， 能 取 得 的 最 大 值 为

46、 1x 6241 x 51 x .45,624min1 x此 时 ， 已 经 从 24降 到 了 0， 达 到 了 非 基 的 取 值 ， 变成 非 基 变 量 。 从 而 得 到 新 的 可 行 基 。4x , 531 xxx由 此 得 到 一 个 新 的 基 本 可 行 解 ： TX )1,0,15,0,4(1 目 标 函 数 值 ： .0)(842)( 01 XZXZ 从 目 标 函 数 值 明 显 看 出 ， 比 明 显 地 得 到 了 改 善 。0X1X )0,4(1Q此 基 本 可 行 解 对 应 可 行 域 的将 （ 2） 式 5,10 5 2624 515 215 214 23

47、 ix xxx xxx xxi （ 2）可 行 基 , 531 xxx 留 在 左 边 ， 非 基 变 量 ,2x 4x 移 到 右 边 5,10 5 2246 515 251 421 23 ix xxx xxx xxi （ 3）用 代 入 法 的 ： 5,10 61321 61314 515 425 421 23 ix xxx xxx xxi （ 4）用 代 入 法 的 ： （ ） 代 入 目 标 函 数 得 ： 42 31318 xxZ 这 一 过 程 用 增 广 矩 阵 的 行 初 等 变 换 表 示 为 ： 000012 510011 2401026 1500150A 2x 4x3x

48、5x1x b 1/6 000012 510011 406/103/11 1500150 （ -1） （ -2）按 最 小 比 值 规 则 ： 415,624,min 54321 0002 xxxxxZ 主 元 素 803/103/10 116/103/20 406/103/11 1500150 2x 4x3x 5x1x b 目 标 函 数 系 数 行 42 31318 xxZ 按 最 小 比 值 规 则 ： 233/21,3/14,515min 803/103/10 116/103/20 406/103/11 1500150 2x 4x3x 5x1x b 3/2 803/103/10 2/32

49、/34/1010 406/103/11 1500150 （ -5） （ -1/3） （ -1/3） 2/172/14/1000 2/32/34/1010 2/72/14/1001 2/152/154/5100所 对 应 的 LP问 题 5,10 232341 272141 21521554 542 541 543ix xxx xxx xxxi 54 2141217max xxZ 5,10 232341 272141 21521554 542 541 543ix xxx xxx xxxi 54 2141217max xxZ 可 行 基 , 321 xxx 令 非 基 变 量 为 0， 得 到 最

50、 优 解2 7 3 15( , , ,0,0)2 2 2 TX ,4x 5x最 优 值 217max Z 总 结 ： 在 迭 代 过 程 中 要 保 持 常 数 列 向 量 非 负 ， 这 能 保 证 基可 行 解 的 非 负 性 。 最 小 比 值 能 做 到 这 一 点 。 主 元 素 不 能 为 0。 因 为 行 的 初 等 变 换 不 能 把 0变 成 1。 主 元 素 不 能 为 负 数 。 因 为 用 行 的 初 等 变 换 把 负 数 变 成 1会把 常 数 列 中 对 应 的 常 数 变 成 负 数 。此 基 本 可 行 解 对 应 可 行 域 的 )2/3,2/7(B其 结

51、果 与 图 解 法 一 致 。 2 1 0 0 0 基0 150 240 5 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 2 1 0 0 0表 1-7 P/29jcBC b 1x 2x3x4x5x 3x 4x 5xjj zc 2 1 0 0 0 基0 152 40 1 0 5 1 0 0 1 2/6 0 1/6 0 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0表 1-8 P/30jcBC b 1x 2x3x5x 3x 4x 5xjj zc 1x 2 1 0 0 0 基0 15/22 7/21 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0

52、 1 0 -1/4 3/2 0 0 0 -1/3 -1/2表 1-9 P/30jcBC b 1x 2x3x2x 3x 4x 5xjj zc 1x 54321 002max xxxxxZ )5,4,3,2,1(0 6122. 5321 4321 ix xxxx xxxxts i例 2 解 LP问 题 ：对 单 纯 形 矩 阵 作 初 等 行 变 换 ， 有 ： 000121 610111 101221T 按 最 小 比 值 原 则 ：116,11min 确 定 主 元 素 。 （ -1） （ -1） 3。 无 穷 多 个 解 情 况 ： 101100 511330 101221 至 此 ， 检

53、验 行 已 没 有 正 数 ，当 前 解 即 为 最 优 解 。此 时 对 应 的 LP问 题 为 ：1 2 3 4 5max 0 0 0 1Z x x x x x )5,4,3,2,1(0 5330 122. 54321 4321 ix xxxxx xxxxts i 0 101100 511330 101221此 时 对 应 的 LP问 题 为 ： 1000max 54321 xxxxxS )5,4,3,2,1(0 5330 122. 54321 4321 ix xxxxx xxxxts i 0 TX )5,0,0,0,1(1 1Z 101100 511330 101221此 时 对 应 的

54、 LP问 题 为 ： 1000max 54321 xxxxxS )5,4,3,2,1(0 5330 122. 54321 4321 ix xxxxx xxxxts i 01 TX )2,0,0,1,3(2 1Z 当 0043xx 时 ， 不 管 取 何 值 ， 均 有 目 标 函 数取 得 最 大 值 1。 此 时 约 束 方 程 为 ： 53 12 52 21 xx xx其 中 为 基 变 量 。,1x 5x 25 21 35 21 xx xx 用 非 基 变 量 表 示 出 基 变 量 ：其 中 ， 为 自 由 变 量 。 设 为 有 :2x ,2 cx cx cx 35 2151 其 中

55、 c是 满 足 非 负 性 的 任 意常 数 。 2x 再 由 ,1x 5x 的 非 负 性 ， 知 ： 035 0021521 cx cx cx解 出 350 c （ 其 中 ）350 c Tccc )35,0,0,12( 最 优 解 为 ：最 优 值 为 ： .1max Z 另 解 ： 101100 511330 101221A 2x 4x3x 5x1x b当 前 最 优 基 变 量 对 应 最 优 解 为 ： , 1x 5x TX )5,0,0,0,1(1 再 强 行 让 检 验 数 为 0的 进 基 ， 再 找 一 个 最 优 解 ：2x 101100 3/53/13/1110 101

56、221 101100 3/53/13/1110 3/133/23/1001 101100 511330 101221A 2x 4x3x 5x1x b 3535,min 确 定 主 元 素 。 1/3按 最 小 比 值 原 则 ： 2 TX )0,0,0,3/5,3/13(2 以 与 的 连 线 段 ：1X 2X 21)1( XX 10 即 TX )55,0,0,35,3101( 10 为 全 部 解 的 一 般 形 式 。若 令 ： c35 有 TcccX )35,0,0,12( 350 c TX )5,0,0,0,1(1 2X LP当 前 解 已 是 最 优 的 四 大 特 征 ： 存 在

57、一 组 (初 始 )可 行 基 （ 其 系 数 矩 阵 为 单 位 阵 ） 。 检 验 行 的 基 变 量 系 数 =0。 检 验 行 的 非 基 变 量 系 数 0。 全 部 0 唯 一 解 。存 在 =0 无 穷 多 个 解 。 常 数 列 向 量 0。下 面 的 问 题 是 ： 所 给 LP的 标 准 型 中 约 束 矩 阵 中 没 有 现 成 的可 行 基 怎 么 办 ？ 人 工 变 量 法 （ 也 称 大 M法 ）针 对 标 准 形 约 束 条 件 的 系 数 矩 阵 中 不 含 单 位 矩 阵 的 处 理方 法 。例 6 用 单 纯 形 法 求 解 LP问 题 313max xxZ

58、 0, 93 12 4321 32 321 321 xxx xx xxx xxx 第 五 节 单 纯 形 的 进 一 步 讨 论 解 ： 先 将 其 化 为 标 准 形 式 54321 0003max xxxxxZ 0 93 12 4 51 32 5321 4321x xx xxxx xxxx再 强 行 加 上 人 工 变 量 ， 使 其 出 现 单 位 矩 阵 ： 0 93 12 4 51 732 65321 4321x xxx xxxxx xxxx 但 这 样 处 理 后 ： 不 易 接 受 。 因 为 是 强 行 引 进 ， 称 为 76,xx人 工 变 量 。 它 们 与 不 一 样

59、。 称 为 松 弛 变 量 和 剩54,xx 54,xx余 变 量 ， 是 为 了 将 不 等 式 改 写 为 等 式 而 引 进 的 ， 而 改 写 前 后两 个 约 束 是 等 价 的 。 人 工 变 量 的 引 入 一 般 来 说 是 前 后 不 等价 的 。 只 有 当 最 优 解 中 ， 人 工 变 量 都 取 值 零 时 （ 此 时 人 工变 量 实 质 上 就 不 存 在 了 ） 才 可 认 为 它 们 是 等 价 的 。处 理 办 法 ： 把 人 工 变 量 从 基 变 量 中 赶 出 来 使 其 变 为 非 基 变量 。 为 此 ， 发 明 者 建 议 把 目 标 函 数 作

60、 如 下 处 理 ： 7654321 0003max MxMxxxxxxZ 0 93 12 451 732 65321 4321x xxx xxxxx xxxx其 中 M为 任 意 大 的 实 数 ， “ -M”称 为 “ 罚 因 子 ” 。 用 意 ： 只要 人工 变 量 取 值 大 于 零 ， 目 标 函 数 就 不 可 能 实 现 最 优 。对 此 单 纯 形 矩 阵 作 初 等 行 变 换 ， 有 ： 000103 91000130 10110112 40001111 MMT 1 1 1 1 0 0 0 42 1 1 0 1 1 0 10 3 1 0 0 0 1 92 3 4 1 0

61、0 0 10M M M M M M （ -1） （ -3） （ -4M）3 0 2 1 1 1 0 32 1 1 0 1 1 0 16 0 4 0 3 3 1 66 3 0 4 1 0 3 4 0 6M M M M M 1/6 3 0 2 1 1 1 0 32 1 1 0 1 1 0 11 0 2/3 0 1/2 1/2 1/6 16 3 0 4 1 0 3 4 0 6M M M M M （ -6M-3） 2 （ -3） 34/32/32/30300 16/12/12/103/201 33/10003/110 02/12/12/11000 MM 3/2 34/32/32/30300 14/14

62、/34/30102/3 33/10003/110 02/12/12/11000 MM （ -1/3） （ -3） 2/34/14/34/30002/9 2/34/14/34/30102/3 2/54/14/14/10012/1 02/12/12/11000 MM 至 此 ， 检 验 行 已 没 有 正 数 ， 当 前 解 即 为 最 优 解 。TX )0,0,23,25,0(0 最 优 值 为 ： .23max Z例 7/P34 求 解 LP问 题 212max xxZ 0, 622 221 21 21xx xx xx 去 掉 人 工 变 量 ， 即 得 原 LP问 题 的 最 优 解 ：76

63、,xx 解 ： 从 上 面 已 看 出 ， 此 LP问 题 无 解 。 下 面 用 大 M法 求 解 看 一下 会 出 现 什 么 情 况 。 引 进 人 工 变 量 ， 上 述 问 题 化 为 ：54321 002max MxxxxxZ 0 622 2 41 5421 321x xxxx xxx对 单 纯 形 矩 阵 作 初 等 行 变 换 ， 有 ： 00012 611022 200111 MT M MMMM 6002122 611022 200111 （ -2） （ -2-2M） MMM 2402210 211200 200111 2x 4x3x 5x1x至 此 ， 检 验 行 已 没

64、有 正 数 ， 当 前 解 即 为 最 优 解 。但 此 时 基 变 量 为 ： 2251xx 含 非 零 的 人 工 变 量 5 2x 矛 盾 。 说 明 原 问 题 无 可 行 解 。使 用 大 M法 小 结 ：对 LP问 题 nj jjxcZ 1max ),2,1(0. 1 njx bxPts jnj jj 式 中 .),(,0 21 Tmjjjj aaaPb 则 在 每 个 约 束 方 程 左 边 加 上 一 个 人 工 变 量 ).,2,1( mix in （ 1.1） 0,0 11 2211 222222121 111212111 mnmn mmnnmnmm nnn nnnxxx

65、bxxaxaxa bxxaxaxa bxxaxaxa （ 1.2 ）式 （ 1.2） 中 含 有 一 个 m阶 单 位 阵 。 以 mnnn xxx , 21 为 基 变 量 。 得 到 一 个 初 始 基 本 可 行 解 ：TmbbX ),0,0( 10 我 们 可 以 从 出 发 进 行 迭 代 。 0X （ 1.3) 当 以 式 （ 1.2） 为 约 束 的 线 性 规 划 问 题 的 最 优 解 中 ， 人工 变 量 都 处 在 非 基 变 量 位 置 （ 即 取 零 值 ） ， 则 原 问 题 有 最 优解 ， 且 将 前 者 最 优 解 中 去 掉 人 工 变 量 部 分 即 为

66、后 者 最 优 解 。 当 （ 1.2） 问 题 的 最 优 解 中 包 含 非 零 的 人 工 变 量 时 ， 则原 问 题 无 可 行 解 。 当 （ 1.2） 问 题 最 优 解 的 基 变 量 中 包 含 人 工 变 量 ， 但 该 人工 变 量 取 值 为 零 ， 这 时 可 将 某 个 非 基 变 量 引 入 基 变 量 中 ，来 替 换 该 人 工 变 量 。 从 而 得 到 原 问 题 的 最 优 解 。 从 式 （ 1.3） 的 做 初 始 基 本 可 行 基 解 进 行 迭 代 时 ， 目 标 是 尽快 把 人 工 变 量 从 基 变 量 中 全 部 “ 赶 ” 出 去 （ 如 果 能 全 部 “ 赶 ”出 去的 话 ） 。 所 用 方 法 除 了 大 M法 外 ， 还 有 下 面 的 两 阶 段 法 。0X3。 两 阶 段 法用 大 M法 处 理 人 工 变 量 时 ， 若 用 计 算 机 处 理 ， 必 须 对 M给 出一 个 较 大 的 具 体 数 据 ， 并 视 具 体 情 况 对 M值 作 适 当 的 调 整 。为 了 克 服 这 一 麻 烦 ， 下 面