5.4 解 线 性 方 程 组 与 线 性 规 划 教 学 要 求 要 求 掌 握 用 Mathematica 解 线 性 方 程 组 的 方 法, 了 解 齐 次 线 性 方 程 组 的 基 础 解 系 的 概 念. 理 解 线 性 规 划 问 题 的 提 法, 并 掌 握 用 Mathematica 处 理 线 性 规 划 问 题 的 办 法. 知 识 点. 齐 次 线 性 方 程 组 的 基 础 解 系. 非 齐 次 线 性 方 程 组 的 通 解 3. 线 性 规 划 问 题 的 提 法 4. 线 性 规 划 问 题 的 解 与 求 解 5.4.. 齐 次 线 性 方 程 组 的 基 础 解 系 我 们 知 道 一 般 的 元 线 性 方 程 组 a + a a + a am + a m L + L + a + L + a L L + L + a m + = b + = b + = b m (5.4.) 可 写 成 矩 阵 形 式 AX=B, 若 B=0, 则 (5.4.) 称 为 齐 次 线 性 方 程 组, 当 齐 次 线 性 方 程 组 系 数 矩 阵 A 的 秩 r(a)= 时, 它 有 唯 一 的 零 解, 当 r(a)< 时, 有 无 穷 多 个 非 零 解, 且 通 解 含 - r(a) 个 任 意 常 数. 例 5.4. 齐 次 线 性 方 程 组 + 34 5 + 3 4 4 + 63 + 34 45 + 4 3 + 44 75 的 系 数 矩 阵 的 秩 是 3, 有 通 解 : 5 = c + c, = c, 3 = c c, 4 = c, 5 = c 6 3 其 中 包 含 5-3= 个 任 意 常 数 c 与 c. 我 们 知 道, 通 解 的 表 达 式 不 是 唯 一 的. 以 后 我 们 把 齐 次 线 性 方 程 组 通 解 的 一 组 值 称 为 该 方 程 组 的 一 个 解 向 量. 比 如 令 c =, c =0, 我 们 就 得 到 一 个 解 向 量 : =-, =, 3 =, 4 =0, 5 =0, 我 们 用 矩 阵 的 形 式 把 它 表 示 为 (-,,, 0, 0), 即 X = (-,,, 0, 0). 如 果 令 c =0, c =, 我 们 将 得 到 另 一 个 解 向 量 : 5 X = 0. 于 是 通 解 可 以 写 成 X = c X + c X, 或 6 3 X = c 0 0 + c 0 5 6 3., 76
其 中 c 与 c 是 任 意 常 数. 向 量 X 与 X 在 通 解 的 表 示 式 中 起 了 基 本 的 作 用, 因 此 把 它 们 组 成 的 集 合 { X, X } 称 为 方 程 组 的 一 个 基 础 解 系. 值 得 注 意 的 是 齐 次 线 性 方 程 组 的 基 础 解 系 不 是 唯 一 的. 下 面 介 绍 有 关 的 Mathematica 语 句 RowReduce 与 NullSpace: RowReduce[A] 用 来 把 矩 阵 A 化 简 为 阶 梯 形, 并 可 求 出 矩 阵 A 的 秩. 例 5.4. 通 过 初 等 行 变 换 将 矩 阵 0 A = 3 3 3 3 化 为 阶 梯 形, 并 求 A 的 秩. 解. I[]:=A={{,,,},{,0,-,},{3,,-,3},{3,,,3}} Out[]={{,,,},{,0,-,},{3,,-,3},{3,,,3}} I[]:= RowReduce[A] Out[]={{,0,-,},{0,,,0},{0,0,0,0},{0,0,0,0}} 由 此 可 见, 矩 阵 A 有 阶 梯 形 0 0 0 (5.4.) 0 0 0 0 0 0 0 0 而 且 显 然 A 的 秩 是. NullSpace[A] 用 来 求 系 数 矩 阵 A 的 齐 次 线 性 方 程 组 的 一 个 基 础 解 系. 例 5.4.3 求 齐 次 线 性 方 程 组 AX 的 一 个 基 础 解 系, 并 写 出 它 的 通 解, 其 中 A 为 (5.4.). 解. I[3]:= NullSpace[A] Out[3]={{-,0,0,},{,-,,0}} 于 是 给 定 方 程 组 的 通 解 是 X = c 0 + c, 其 中 c 0 与 c 是 任 意 常 数. 0 5.4.. 非 齐 次 线 性 方 程 组 的 通 解 设 AX=B 是 一 般 的 元 线 性 方 程 组 (5.4.), 其 中 Bπ0, 则 对 应 的 齐 次 线 性 方 程 组 AX 称 为 AX=B 的 导 出 组, AX=B 的 通 解 与 导 出 组 的 通 解 有 着 密 切 的 关 系, 即 有 下 面 的 定 理 5.4.. 设 X 0 是 元 线 性 方 程 组 (5.4.) AX=B 的 一 个 特 解, {X, X,, X k } 是 导 出 组 AX 的 一 个 基 础 解 系, 则 AX=B 的 通 解 是 X = X 0 + c X + c X + + c k X k, 其 中 c, c,, c k 是 任 意 常 数. 因 此, 对 于 一 般 的 元 线 性 方 程 组 (5.4.), 只 要 求 出 它 的 任 何 一 个 解, 再 求 出 其 导 出 组 的 一 个 基 础 解 系, 就 可 按 照 定 理 5.4., 写 出 它 的 通 解 了. 用 Mathematica 求 解 一 般 的 元 线 性 方 程 组 的 有 关 语 句 主 要 是 : Det, LiearSolve, 77
Iverse, Solve. Det[A] 是 求 方 阵 A 的 行 列 式. a 例 5.4.4 求 方 阵 M = c 解. I[4]:=M={{a,b},{c,d}} Out[4]={{a,b},{c,d}} I[5]:= Det[M] Out[5]= -(bc)+ad 因 此 M = ad -bc. b 的 行 列 式. d 语 句 LiearSolve[A, B] 是 求 线 性 方 程 组 AX=B 的 一 个 解, 其 中 A 是 方 阵 ; 而 语 句 Iverse[A] 是 求 方 阵 A 的 逆. + 5y = a 例 5.4.5 求 线 性 方 程 组 的 解. + y = b 解 一. I[6]:=P={{,5},{,}} Out[6]= {{,5},{,}} I[7]:= P.{,y} == {a,b} Out[7]={+5y,+y} == {a,b} I[8]:=Solve[%,{,y}] a 5b a b Out[8]={{-> +, y-> }} 9 9 9 9 解 二. I[9]:=LiearSolve[P,{a,b}] a 5b a b Out[9]={-( ),-( + )} 9 9 9 9 解 三. I[0]:=Iverse[P].{a,b} a 5b a b Out[0]={ +, } 9 9 9 9 a 5b = + 于 是 得 方 程 组 的 唯 一 解 9 9. a b y = 9 9 注. 当 方 程 组 的 系 数 行 列 式 为 0 时, 上 面 的 求 解 过 程 就 失 效 了, 此 时 应 按 定 理 5.4. 来 解. 也 可 直 接 用 语 句 Solve 求 出 所 有 解. + + 3 + 4 5 = + 3 + 4 + 5 + 6 = 例 5.4.6 求 线 性 方 程 组 + + 4 + 6 = + 3 + 4 6 的 全 部 解. 显 然 此 方 程 组 的 未 知 数 个 数 多 于 方 程 的 个 数, 因 此 有 无 穷 多 个 解, 我 们 可 用 语 句 Solve 来 求 解. 解. I[]:= A={{,,,,-,0},{0,,,,,},{,,0,,0,},{0,,,,0,-}} Out[]= {{,,,,-,0},{0,,,,,},{,,0,,0,},{0,,,,0,-}} 78
I[]:= A.{,,3,4,5,6} =={,,,0} Out[]={ ++3+4-5, +3+4+5+6, ++4+6, +3+4-6} == {,,,0} I[3]:= Solve[%,{,,3,4,5,6}] Out[3]={{ ->+ 3+5-6, ->-- 3+5+6, 4->-5-36}} 因 此 给 定 方 程 组 的 通 解 是 0 0 0 X = + c + c +c 3, 0 3 0 0 0 0 0 0 其 中 c, c 与 c 3 是 任 意 常 数. 实 验 5.4.7 某 地 区 有 三 个 产 业 : 煤 矿 发 电 厂 和 地 方 铁 路. 开 采 一 元 钱 的 煤, 煤 矿 要 支 付 0.5 元 的 电 费 及 0.5 元 的 运 输 费. 生 产 一 元 钱 的 电 力, 发 电 厂 要 支 付 0.65 元 的 煤 费,0.05 元 的 电 费 及 0.05 元 的 运 输 费. 创 收 一 元 钱 的 运 输 费, 铁 路 要 支 付 0.55 元 的 煤 费 及 0.0 元 的 电 费. 在 某 一 周 内, 煤 矿 接 到 外 地 金 额 为 50000 元 的 定 货, 发 电 厂 接 到 外 地 金 额 为 5000 元 的 定 货, 外 界 对 地 方 铁 路 没 有 需 求. 请 你 编 制 投 入 产 出 表, 并 求 三 个 企 业 在 这 一 周 内 总 产 值 多 少 才 能 满 足 自 身 及 外 界 的 需 求?( 关 于 投 入 产 出 可 参 看.4.3 线 性 方 程 组 在 经 济 中 的 应 用 ) 实 验 5.4.7 假 定 我 国 兵 器 工 业 主 要 由 五 个 行 业 组 成, 某 年 度 兵 器 工 业 主 要 行 业 简 化 的 投 入 产 出 平 衡 表 如 下 ( 产 值 单 位 是 亿 元 ): 3 4 5 A 行 业 B 行 业 C 行 业 D 行 业 E 行 业 合 计 最 终 产 品 总 产 值 A 行 业 0 0 30 40 50 50 350 500 B 行 业 40 30 0 50 60 00 00 400 3 C 行 业 50 30 60 0 0 80 0 400 4 D 行 业 30 30 0 0 40 30 70 400 5 E 行 业 40 30 0 0 30 40 360 500 6 物 资 30 60 50 60 80 7 能 源 0 50 40 30 40 8 工 资 利 税 90 50 60 70 80 总 投 入 500 400 400 400 500 如 果 要 求 把 最 终 产 品 均 提 高 8%, 那 么 各 行 业 应 如 何 修 改 生 产 计 划? 5.4.3. 线 性 规 划 问 题 的 提 法 例 5.4.8 某 工 厂 有 甲 乙 丙 丁 四 个 车 间, 生 产 A B C D E F 六 种 产 品. 根 据 车 间 生 产 条 件 与 原 有 生 产 情 况, 得 知 生 产 各 种 产 品 每 单 位 所 需 工 作 小 时 数, 各 车 间 每 月 工 作 小 时 的 上 限, 以 及 产 品 的 价 格 如 下 表 所 示 : A B C D E F 每 月 工 作 小 时 上 限 甲 0. 0. 0. 0.3 0.3 0.3 850 乙 0. 0.5 700 丙 0. 0.5 00 79
丁 0.3 0.8 900 单 价 4.0.8 3. 7. 6.4 6.0 各 种 产 品 每 月 应 该 生 产 多 少, 才 能 使 该 厂 每 月 的 生 产 总 值 最 大? 我 们 用,,, 6 分 别 表 示 每 月 生 产 A B C D E F 六 种 产 品 的 单 位 数, 于 是 它 们 应 满 足 下 列 约 束 条 件 : 0. + 0. + 0. 3 + 0.3 4 + 0.3 5 + 0.3 6 850 0. + 0.5 4 700 0. + 0.5 5 00 0.3 3 + 0.8 6 900 其 中 0, =,,,6. 于 是 问 题 成 为 求 生 产 总 值 函 数 f = 4.0 +.8 + 3. 3 + 7. 4 + 6.4 5 + 6.0 6 在 上 述 约 束 条 件 下 达 到 最 大. 这 个 f 称 为 目 标 函 数, 称 为 决 策 变 量, 它 们 应 满 足 的 不 等 式 组 称 为 约 束 条 件, 其 中 0 称 为 非 负 约 束. 在 这 里, 目 标 函 数 与 约 束 条 件 不 等 式 的 左 端 均 为 决 策 变 量 的 线 性 函 数, 因 此 把 这 个 问 题 称 为 线 性 规 划. 一 般 情 况, 约 束 条 件 可 以 是 包 含 的 不 等 式, 也 可 以 是 包 含 的 不 等 式 或 等 式, 同 样, 目 标 函 数 可 以 是 求 最 大 值, 也 可 以 是 求 最 小 值. 但 我 们 总 可 以 把 给 定 线 性 规 划 问 题 化 为 等 价 的 标 准 形 式 : (LP) s.t. = mi a i f 0, = b = i c =, L,, i =, L, m 其 中 目 标 函 数 f 是 求 最 小 值, 约 束 条 件 是 包 含 的 不 等 式. 也 可 以 写 成 矩 阵 形 式 : mi f = c s.t. A b, 0 5.4.4. 线 性 规 划 问 题 的 解 与 求 解 满 足 约 束 条 件 A b, 0 的 向 量 称 为 线 性 规 划 问 题 (LP) 的 一 个 可 行 解, 全 体 可 行 解 的 集 合 称 为 (LP) 的 可 行 域, 使 目 标 函 数 f 达 到 最 小 值 的 可 行 解 称 为 (LP) 的 最 优 解, 其 对 应 的 目 标 函 数 的 值 称 为 最 优 值. 我 们 先 用 作 图 的 方 法 解 一 个 简 单 线 性 规 划 问 题, 从 直 观 上 理 解 线 性 规 划 问 题 的 解 例 5.4.9 求 解 两 个 变 量 的 线 性 规 划 问 题 mi f = - + y s.t. - y - y + y 5, y 0. 解. 我 们 知 道, 二 元 一 次 方 程 a + b y + c 表 示 直 角 坐 标 平 面 上 的 一 条 直 线, 该 直 线 又 把 整 个 平 面 分 成 两 个 半 平 面, 分 别 可 以 用 二 元 一 次 不 等 式 a + b y + c > 0 与 a + b y + c < 0 表 示 ( 如 果 带 边 界, 只 要 将 > 与 < 分 别 改 成 与 即 可 ). 现 在, 问 题 中 的 五 个 不 等 式 分 别 表 示 五 个 半 平 面, 于 是 问 题 成 为 在 这 五 个 半 平 面 的 交 集 上 求 函 数 f = - + y 的 最 小 值. 我 们 作 图 如 下 : 图 5. 80
图 中 的 四 边 形 ADEC( 包 括 边 界 ) 是 问 题 的 可 行 域, 其 中 顶 点 的 坐 标 分 别 是 : A(7/3,8/3), D(,0), E(,0), C(4,). 另 一 方 面, 二 元 线 性 函 数 f = - + y 显 然 连 续, 而 且 其 线 性 性 质 使 它 只 能 在 可 行 域 四 边 形 ADEC 的 边 界 上 取 得 最 小 值. 进 一 步, 它 又 在 边 界 的 四 条 线 段 AD, DE, EC, CA 的 各 自 端 点 处 取 得 该 线 段 上 函 数 的 最 小 值. 因 此, 我 们 只 要 计 算 出 四 个 顶 点 A,D,E,C 处 的 函 数 值 : f(a) = /3, f(d) = -, f(e) = -, f(c) = -3, 其 中 的 最 小 者 f(c) = -3 就 是 问 题 的 解. 在 Mathematica 中 解 线 性 规 划 问 题 可 用 下 面 的 三 种 语 句. 在 约 束 条 件 下 求 目 标 函 数 f 的 最 大 值, 用 语 句 : CostraiedMa[f, {iequalities},{, y, }] 在 约 束 条 件 下 求 目 标 函 数 f 的 最 小 值, 用 语 句 : CostraiedMi[f, {iequalities},{, y, }] 以 上 两 种 语 句 不 必 将 问 题 标 准 化. 如 果 解 矩 阵 形 式 的 线 性 规 划 问 题, 则 应 先 将 问 题 化 为 等 价 的 标 准 形 式 (LP), 然 后 用 语 句 : LiearProgrammig[c, A, b] 例 5.4.0 Ma f = 5 + 7y s.t. + 5 y 50 3 + y 4, y 0. 解. I[4]:= CostraiedMa[5 + 7y,{ + 5y<=50, 3 + y<=4},{, y}] Out[4]={9,{ ->0, y->6}} 于 是 得 f(0,6) = 9 是 问 题 的 解. 例 5.4. Mi f = 5 + 7y s.t. + 5 y 0 3 + y 4, y 0. 解. I[5]:= CostraiedMi[5 + 7y,{ + 5y<=0, 3 + y>=4},{, y}] 运 行 后, 屏 幕 出 现 下 述 内 容 : CostraiedMi :: sat : Specified costraits caot be satisfied. Out[5]= CostraiedMi[5 + 7y,{ + 5y<=0, 3 + y>=4},{, y}] 这 表 明 问 题 无 可 行 解. 例 5.4. Ma f = 5 + 7y s.t. + 5 y 0 3 + y 4, y 0. 解. I[6]:= CostraiedMa[5 + 7y,{ + 5y>=0, 3 + y>=4},{, y}] 运 行 后, 屏 幕 出 现 下 述 内 容 : CostraiedMa :: bdd : Specified domai appears uboued. Out[6]={Ifiity, {->Idetermiate}} 这 表 明 问 题 有 可 行 解, 但 无 最 优 解. 例 5.4.3 现 在 用 语 句 LiearProgrammig 来 解 例 5.4.8 中 的 问 题. 首 先 将 问 题 标 准 化, 即 求 求 目 标 函 数 的 最 小 值, 并 用 不 等 式 的 约 束 条 件. I[7]:=c={-4.0,-.8,-3.,-7.,-6.4,-6.0}; A={{-0.,-0.,-0.,-0.3,-0.3,-0.3},{-0., 0,0,-0.5,0,0},{0, -0.,0,0,-0.5,0}, {0,0, -0.3,0,0,-0.8}}; b={-850,-700,-00,-900}; LiearProgrammig[c,A,b] Out[7]={3500.,500.,3000.,0,0,0} 注. 只 给 出 最 优 解, 但 不 给 出 最 优 值. 实 验 5.4.4 某 煤 矿 公 司 拥 有 两 个 分 矿, 甲 矿 每 班 能 生 产 0t 优 质 煤,30t 中 等 煤,50t 次 煤 ; 乙 矿 每 班 能 生 产 三 种 煤 各 0t. 该 公 司 生 产 的 煤 能 全 部 卖 掉, 但 两 个 矿 的 运 作 费 用 不 同, 因 此 为 公 司 挣 得 的 利 润 不 同. 甲 矿 每 班 能 挣 得 利 润 000 元, 乙 矿 是 00 元. 而 公 司 的 最 大 开 采 量 是 8800t 优 质 煤,6000t 中 等 煤,0000t 次 煤. 公 司 可 任 意 安 排 班 次. 问 如 何 计 划 生 产, 才 能 获 得 最 大 利 润, 最 大 利 润 又 是 多 少? 8
实 验 5.4.5 某 人 需 补 充 维 生 素. 现 有 两 种 维 生 素 胶 囊, 都 含 维 生 素 A,C,D,E 及 Z. 甲 种 胶 囊 每 粒 含 g 维 生 素 A, g C, 4g D, 4g E, 5g Z, 乙 种 胶 囊 每 粒 含 3g 维 生 素 A, g C, g D, 3g E, g Z. 根 据 医 生 嘱 咐, 他 每 天 需 摄 入 至 多 8g A, 3g C, 4g D 与 至 少 g E, 而 维 生 素 Z 的 摄 取 量 没 有 限 制. 问 : 他 每 天 应 服 两 种 胶 囊 各 多 少 粒 才 能 满 足 维 生 素 的 需 要, 而 且 能 摄 取 最 大 量 的 维 生 素 Z. 又 若 甲 种 胶 囊 每 粒.5 元, 乙 种 每 粒 元. 那 么 怎 样 才 能 花 费 最 少 又 能 满 足 每 天 维 生 素 的 需 要 量? 此 时 能 摄 入 多 少 维 生 素 Z? 8