《数学规划模型》PPT课件

《《数学规划模型》PPT课件》由会员分享，可在线阅读，更多相关《《数学规划模型》PPT课件（27页珍藏版）》请在装配图网上搜索。

1、第 6章 数 学 规 划 模 型 在 一 系 列 客 观 或 主 观 限 制 条 件 下 ， 寻 求 使 关 注 的 某 个 或 多 个 指 标达 到 最 大 （ 或 最 小 ） 的 决 策 。 例 如 ： 运 输 方 案 要 在 满 足 物 资 需 求 和 装 载 条 件 下 安 排 从 各 供 应 点到 各 需 求 点 的 运 量 和 路 线 ， 使 运 输 总 费 用 最 低 ； 生 产 计 划 要 按 照 产品 工 艺 流 程 和 顾 客 需 求 ， 制 定 原 料 、 零 件 、 部 件 等 订 购 、 投 产 的 日程 和 数 量 ， 尽 量 降 低 成 本 使 利 润 最 高 。

2、上 述 这 些 决 策 问 题 通 常 称 为 优 化 问 题 。 虽 然 最 优 化 可 以 追 溯 到 十 分 古 老 的 极 值 问 题 ， 然 而 ， 它 成 为 一门 独 立 的 学 科 是 在 上 世 纪 40年 代 末 ， 是 在 1947年 Dantzing提 出 求 解一 般 线 性 规 划 问 题 的 单 纯 型 法 之 后 。 问 题 驱 动 ： 高 等 教 育 收 费 学 费 问 题 涉 及 到 每 一 个 大 学 生 及 其 家 庭 ， 是 一 个 敏 感 而 又 复 杂的 问 题 ： 过 高 的 学 费 会 使 很 多 学 生 无 力 支 付 ， 过 低 的 学 费

3、 又 使 学校 财 力 不 足 而 无 法 保 证 质 量 。 高 等 教 育 属 于 非 义 务 教 育 ， 其 经 费在 世 界 各 国 都 由 政 府 财 政 拨 款 、 学 校 自 筹 、 社 会 捐 赠 和 学 费 收 入等 几 部 分 组 成 。 对 适 合 接 受 高 等 教 育 的 经 济 困 难 的 学 生 ， 一 般 可通 过 贷 款 和 学 费 减 、 免 、 补 等 方 式 获 得 资 助 ， 品 学 兼 优 者 还 能 享受 政 府 、 学 校 、 企 业 等 给 予 的 奖 学 金 。 学 费 问 题 近 来 在 各 种 媒 体 上 引 起 了 热 烈 的 讨 论

4、。 据 中 国 国 情 ，利 用 数 学 建 模 的 方 法 ， 收 集 诸 如 国 家 生 均 拨 款 、 培 养 费 用 、 家 庭收 入 等 相 关 数 据 ， 就 几 类 学 校 或 专 业 的 学 费 标 准 进 行 定 量 分 析 ， 得 出 明 确 、 有 说 服 力 的 结 论 。 问 题 背 景 分 析n 要 确 保 有 良 好 的 高 等 教 育 质 量 ， 必 须 有 相 应 的 经 费 保 障 。 高 等 教育 的 学 费 问 题 涉 及 到 每 一 个 大 学 生 及 其 家 庭 。 根 据 相 关 规 定 ， 高等 教 育 属 于 非 义 务 教 育 ， 其 成 本

5、 主 要 是 根 据 高 等 教 育 收 益 分 享 情况 进 行 分 摊 ， 即 遵 循 “ 谁 收 益 、 谁 负 担 ” 的 原 则 。 基 于 此 理 论 ，我 国 于 1993年 试 行 并 轨 招 生 ， 缴 费 上 学 制 度 开 始 在 部 分 高 校 试 行 。到 1997年 ， 全 国 高 校 全 部 并 轨 收 费 。 然 而 ， 自 高 等 教 育 实 行 收 费政 策 以 来 ， 收 费 标 准 出 现 了 逐 步 攀 升 的 情 况 ， 以 至 于 学 费 水 平 在一 定 程 度 上 成 了 人 们 关 注 的 社 会 问 题 ， 也 成 为 人 们 争 议 的

6、社 会 焦点 。 n 高 等 教 育 的 经 费 主 要 由 政 府 拨 款 、 学 校 自筹 、 社 会 捐 赠 和 学 费 收 入 等 几 部 分 组 成 ，其 中 由 受 教 育 者 及 其 家 庭 所 承 担 的 学 费 是本 文 主 要 的 讨 论 对 象 。 目 前 学 费 收 入 已 成为 高 等 学 校 办 学 经 费 的 主 要 来 源 之 一 ， 也已 成 为 维 系 学 生 与 学 校 经 济 关 系 的 主 要 纽带 。 目 标 分 析n 高 等 教 育 收 费 要 满 足 如 下 几 个 需 求 因 素 ：n 目 标 1： 培 养 质 量 指 标 （ 师 资 力 量

7、、 教 育 设 备 、 教 学 氛 围 ） ；n 目 标 2： 学 生 就 读 指 标 ；n 目 标 3： 办 学 收 益 指 标 （ 办 学 获 利 ） ；n 目 标 4： 学 生 收 益 指 标 。n 这 是 一 个 多 因 素 的 问 题 ， 多 因 素 分 析 的 方 法 有 很 多 ， 解 决 高 等教 育 收 费 问 题 的 方 法 也 有 很 多 ， 但 是 结 合 实 际 ， 主 要 考 虑 制 定最 合 理 的 学 费 价 格 和 生 均 奖 贷 助 学 金 。 n 而 “ 最 ” 在 数 学 上 通 常 就 是 我 们 所 说 的 优 化 问 题 。 6.1规 划 模 型

8、简 介n 模 型 分 类n 在 很 多 实 际 问 题 中 ， 所 能 够 提 供 的 决 策 变 量 取 值 受 到 很 多因 素 的 制 约 ， 这 样 就 产 生 了 一 般 的 优 化 模 型 ， 统 称 为 数 学规 划 模 型 。 按 照 数 学 规 划 模 型 的 具 体 特 征 可 以 将 数 学 规 划分 为 ： 线 性 规 划 ， 非 线 性 规 划 ， 整 数 规 划 ， 多 目 标 规 划 ，目 标 规 划 等 。 规 划 问 题 结 构 （ 三 要 素 ）1、 决 策 变 量 ， 通 常 是 该 问 题 要 求 解 的 那 些 未 知 量 ；2、 目 标 函 数 ，

9、通 常 是 该 问 题 要 优 化 （ 最 小 或 最 大 ）的 那 个 目 标 的 数 学 表 达 式 ；3、 约 束 条 件 ， 由 该 问 题 对 决 策 变 量 的 限 制 条 件 给 出 ，即 允 许 取 值 的 范 围 ， 称 为 可 行 域 ， 常 用 一 组 关 于 的不 等 式 （ 也 可 以 有 等 式 ） 来 界 定 。 规 划 模 型 的 一 般 形 式 migts xfxf xi ,210. )(min()(max )( ，）（ 或 或 规 划 模 型 的 分 类 1、 在 模 型 中 若 目 标 函 数 和 约 束 条 件 中 的 函 数 均 为 线 性 函 数 ，

10、 则称 为 线 性 规 划 （ 简 记 为 LP） ， 否 则 就 称 为 非 线 性 规 划 （ 简 记 为NLP） 。 2、 规 划 中 的 变 量 （ 部 分 或 全 部 ） 限 制 为 整 数 时 ， 称 为 整 数 规 划（ 简 记 为 IP） 。 3、 若 整 数 规 划 模 型 中 的 决 策 变 量 只 能 取 0或 1， 则 称 模 型 为 0-1规划 。 如 不 加 特 殊 说 明 ， 整 数 规 划 一 般 指 整 数 线 性 规 划 例 1s.t. 21 30004000max xxz 0, 7 8 102 212 21 21 xxx xx xx 例 2 s.t. 1

11、2max 40 90z x x Zxx xx xx 21 21 21, 70207 5679 6 2数 学 规 划 模 型 实 例 及 求 解 1、 线 性 规 划 问 题 数 学 模 型 例 2.1 加 工 奶 制 品 的 生 产 计 划 一 奶 制 品 加 工 厂 用 牛 奶 生 产 A1、 A2两 种 奶 制 品 ， 1桶 牛 奶 可 以在 设 备 甲 上 用 12小 时 加 工 成 3公 斤 A1 ， 或 者 在 设 备 乙 上 用 8小 时 加 工 成 4公 斤 A2 。 根 据 市 场 需 求 ， 生 产 的 A1、 A2能 全 部售 出 ， 且 每 公 斤 A1获 利 24元 ，

12、 每 公 斤 A2获 利 16元 。 现 在 加 工厂 每 天 能 得 到 50桶 牛 奶 的 供 应 ， 每 天 正 式 工 人 总 的 劳 动 时 间为 480小 时 ， 并 且 设 备 甲 每 天 至 多 能 加 工 100公 斤 ， 设 备 乙的 加 工 能 力 没 有 限 制 。 试 为 该 厂 制 定 一 个 生 产 计 划 ， 使 每 天获 利 最 大 。 n 决 策 变 量 设 每 天 用 x1桶 牛 奶 生 产 A1， 用 x2桶 牛奶 生 产 A2 n 目 标 函 数 设 每 天 获 利 为 Z元 。 x1桶 牛 奶 可 生 产3x1公 斤 A1 ， 获 利 24*3x1

13、， x2桶 牛 奶 可 生 产 4 x2公 斤 A2 ， 获 利 16* 4 x2 ， 故 Z= 24*3x1+ 16* 4 x2 n 约 束 条 件 原 料 供 应 劳 动 时 间 非 负 约 束 、 均 不 能 为 负 值 1 21 21 21 1 2 max 72 64. . 5012 8 4803 1000, 0z x xs t x xx xxx x 在 LINGO模 型 窗 口 输 入 如 下 ：Max =72*x1+64*x2; X1+x2=50;12*x1+8*x2=480;3*x1=100; 用 鼠 标 单 击 菜 单 中 的 求 解 命 令 （ SOLVE） 就 可 以 得

14、到 解 答 ，结 果 窗 口 显 示 如 下 ：Global optimal solution found at iteration: 2 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000 ,04.014,03.013,02.012,

15、01.011 44332211 xpxpxpxp 假 定 A,B,C,D四 种 产 品 价 格 随 产 量 的 扩 大 而 递 减 ， 其 需 求 函 数 分 别 为试 确 定 四 种 产 品 的 产 量 ， 以 便 使 总 收 益 最 大 。 产 品消 耗 定 额 资 源 A B C D 资 源 可 供 应 量甲 1 2 3 2 200乙 7 9 8 1 300丙 3 0 1 7 400例 设 用 甲 、 乙 、 丙 三 种 有 效 资 源 生 产 A,B,C,D四 种 产 品 ，产 品 的 资 源 消 耗 定 额 及 资 源 的 有 效 供 应 量 如 表 所 示 443322114321

16、 ),( xpxpxpxpxxxxz )03.013()02.012()01.011( 332211 xxxxxx )04.014( 44 xx )14131211( 4321 xxxx )04.003.002.001.0( 24233221 xxxx 解 设 A,B,C,D四 种 产 品 的 产 量 分 别 为 x1,x2,x3和 x4，则 问 题 的 目 标 函 数 （ 总 收 益 函 数 ） 为 ： 注 意 到 资 源 约 束 ， 上 述 问 题 可 表 为 )14131211(max 4321 xxxxz )04.003.002.001.0( 24232221 xxxx 200232.

17、 4321 xxxxts 300897 4321 xxxx 40073 431 xxx 4,3,2,1,0 jxj 下 面 用 Lingo软 件 来 求 解 上 述 的 例 子 ，打 开 Lingo执 行 文 件 ， 编 程 如 下 ： Model: max=11*x1+12*x2+13*x3+14*x4-x5; x5=0.01*(x1*x1+2*x2*x2+3*x3*x3+4*x4*x4); x1+2*x2+3*x3+2*x4200; 7*x1+9*x2+8*x3+x4300; 3*x1+x3+7*x4400; end为 了 编 制 程 序 的 方 便 ， 我 们 引 入 了 中 间 变 量

18、 选 择 菜 单 “ Solve”进 行 求 解 ， 得 到 输 出 Objective value: 1003.010 Variable Value Reduced Cost X1 0.000000 1.713858 X2 6.900608 0.4349500E-07 X3 23.00476 0.000000 X4 53.85646 0.000000 X5 132.8497 0.0000005x 。 某 航 空 公 司 为 满 足 客 运 量 日 益 增 长 的 需 要 ，欲 购 置 一 批 新 的 远 程 、 中 程 及 短 程 客 机 。每 架 远 程 客 机 价 格 6700万 元 ，

19、 中 程 客 机 5000万 元 ，短 程 客 机 3500万 元 。 该 公 司 现 有 资 金 7.5亿 元 可 用 于 购 买 飞 机 。估 计 年 净 利 润 每 架 远 程 客 机 为 420万 元 ，中 程 客 机 300万 元 ， 短 程 客 机 230万 元 。该 公 司 现 有 熟 练 驾 驶 员 可 用 来 配 备 30架 新 飞 机 。维 修 设 备 足 以 维 修 新 增 加 40架 新 的 短 程 客 机 ，每 架 中 程 客 机 的 维 修 量 相 当 于 4/3短 程 客 机 ，而 每 架 远 程 客 机 的 维 修 量 相 当 于 5/3架 短 程 客 机 。

20、为 获 取 最 大 利 润 ， 该 公 司 应 购 买 各 类 客 机 多 少 架 ？ 设 购 买 远 程 、 中 程 、 短 程 客 机 的 数 量 分 别 为 x1,x2,x3架 ,问 题 的 数 学模 型 为 321 230300420max xxxz ， （ 目 标 函 数 ）1 2 3. 6700 5000 3500 75000st x x x ， 30 321 xxx ， 403435 321 xxx ， （ 约 束 条 件 ）0, 321 xxx ， 均 为 整 数 321 , xxx。 将 上 述 模 型 输 入 Lingo如 下 ： max= 420*x1+300*x2+23

21、0*x3; 6700*x1+5000*x2+3500*x375000; x1+x2+x330;5*x1+4*x2+3*x3120;gin(x1);gin(x2);gin(x3);得 到 最 优 解 为 1 2 30, 1, 20 x x x 最 优 解 为 4900z 元 6.4多 目 标 规 划 在 许 多 实 际 问 题 中 ， 衡 量 一 个 方 案 的 好 坏 标 准 往 往 不 止 一个 ， 例 如 设 计 一 个 导 弹 ， 既 要 射 程 最 远 ， 又 要 燃 料 最 省 ， 还 要精 度 最 高 . 这 一 类 问 题 统 称 为 多 目 标 最 优 化 问 题 或 多 目

22、标 规 划问 题 . 设 在 一 段 时 间 （ 比 如 两 年 ） 内 ， 某 市 有 b亿 元 资 金 可 用 于投 资 ， 有 m个 项 目 ， A1， A2,Am 可 供 选 择 。 若 对 第 i个 项 目 投资 ， 需 要 资 金 bi亿 元 ， 可 安 排 劳 动 力 ai人 就 业 ， 消 耗 能 源 ei(t)标准 煤 ， 可 获 利 税 收 入 c i亿 元 ， 若 该 市 在 这 段 时 间 内 的 能 耗 限 额为 e(t)标 准 煤 ， 有 a个 人 急 需 安 置 就 业 ， 欲 确 定 一 个 最 佳 的 投 资方 案 ， 使 该 市 所 获 得 的 利 税 总

23、收 入 最 多 、 安 置 的 劳 动 力 最 多 ，而 能 耗 最 少 ？ 1, 1,2,0 ix ii 若 对 A 投 资 ， 否 则 ， ,mz1为 所 获 得 的 利 税 总 收 入 ，z2为 安 置 的 劳 动 力 的 总 数 ，z3为 总 能 耗 1 12 13 111 1 m ax ,m ax ,m in ,. . , 0 1, 1, 2, , . m i ii m i iim i iim i iim i iim i ii i z c xz a xz e xs t b x ba x ae x e x i m 或 1 2 311 1 min ( ) ( ( ), ( ), ( )

24、,. ,0 1, 1,2, , . Tm i iim i iim i ii i v F x f x f x f xst b x ba x ae x ex i m 或改 写 为 如 下 形 式 ： 1 1( ) m i iif x c x ， 2 1( ) m i iif x a x， mi ii xexf 13 )( 多 目 标 规 划 问 题 的 求 解多 目 标 规 划 问 题 的 解 法 大 致 可 分 为 两 类 ：直 接 解 法 和 间 接 解 法 。到 目 前 为 止 ， 关 于 直 接 解 法 的 成 果 还 不 多 ，常 用 的 多 为 间 接 解 法 。 所 谓 间 接 解

25、法 是 指 ：根 据 问 题 的 实 际 背 景 和 特 征 ，设 法 将 多 目 标 的 优 化 问 题 转 化 为 单 目 标 优 化 问 题 ，从 而 获 得 满 意 解 的 方 法 。下 面 我 们 来 介 绍 线 性 加 权 求 和 法 。 1min ( ) ( ) ,. . . p i iih x w f xs t x R 对 模 型 （ 6.4.1） 的 p个 目 标 函 数 1( ), , ( )pf x f x按 其 重 要 程 度 给 以 适 当 的 权 系 数0, 1,2,iw i p 1 1p ii w 1( ) ( )p i iih x w f x作 为 新 的 目 标 函 数 ，称 为 评 价 （ 目 标 ） 函 数 ，再 求 解 问 题