非线性规划

非线性规划百科名片非线性非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非线性规划是 20 世纪 50 年代才开始形成的一门新兴学科。70 年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。目录概述 简史 实例 常见问题 数学模型 一维最优化方法 无约束最优化方法 约束最优化方法 概述简史实例常见问题数学模型一维最优化方法无约束最优化方法约束最优化方法 凸规划 二次规划 几何规划 应用问题 参考书目展开编 辑 本 段 概 述非 线 性 规 划 nonlinear programming 具 有 非 线 性 约 束 条 件 或 目 标 函 数 的 数 学 规 划 ， 是 运 筹 学 的 一 个 重 要 分支 。 非 线 性 规 划 研 究 一 个 n 元 实 函 数 在 一 组 等 式 或 不 等 式 的 约 束 条 件 下 的极 值 问 题 ， 且 目 标 函 数 和 约 束 条 件 至 少 有 一 个 是 未 知 量 的 非 线 性 函 数 。 目 标函 数 和 约 束 条 件 都 是 线 性 函 数 的 情 形 则 属 于 线 性 规 划 。 编 辑 本 段 简 史非 线 性 规 划 是 20 世 纪 50 年 代 才 开 始 形 成 的 一 门 新 兴 学 科 。 1951 年H.W.库 恩 和 A.W.塔 克 发 表 的 关 于 最 优 性 条 件 (后 来 称 为 库 恩 塔 克 条 件 )的论 文 是 非 线 性 规 划 正 式 诞 生 的 一 个 重 要 标 志 。 在 50 年 代 还 得 出 了 可 分 离 规划 和 二 次 规 划 的 n 种 解 法 ,它 们 大 都 是 以 G.B.丹 齐 克 提 出 的 解 线 性 规 划 的 单纯 形 法 为 基 础 的 。 50 年 代 末 到 60 年 代 末 出 现 了 许 多 解 非 线 性 规 划 问 题 的 有效 的 算 法 ， 70 年 代 又 得 到 进 一 步 的 发 展 。 非 线 性 规 划 在 工 程 、 管 理 、 经 济 、科 研 、 军 事 等 方 面 都 有 广 泛 的 应 用 ， 为 最 优 设 计 提 供 了 有 力 的 工 具 。 编 辑 本 段 实 例下 面 通 过 实 例 归 纳 出 非 线 性 规 划 数 学 模 型 的 一 般 形 式 ， 介 绍 有 关 非 线 性规 划 的 基 本 概 念 。 例 1 （ 投 资 决 策 问 题 ） 某 企 业 有 n 个 项 目 可 供 选 择 投 资 ， 并 且 至 少 要对 其 中 一 个 项 目 投 资 。 已 知 该 企 业 拥 有 总 资 金 A 元 ， 投 资 于 第 i 个 项 目 需花 资 金 ai 元 ， 并 预 计 可 收 益 bi 元 。 试 选 择 最 佳 投 资 方 案 。 解 设 投 资 决 策 变 量 为 则 投 资 总 额 为 aixi， 投 资 总 收 益 为 bixi。 因 为 该 公 司 至 少 要 对 一个 项 目 投 资 ， 并 且 总 的 投 资 金 额 不 能 超 过 总 资 金 ， 故 有 限 制 条 件 另 外 ， 由 于 xi 只 取 值 0 或 1， 所 以 还 有 最 佳 投 资 方 案 应 是 投 资 额 最 小 而 总 收 益 最 大 的 方 案 ， 所 以 这 个 最 佳 投 资决 策 问 题 归 结 为 总 资 金 以 及 决 策 变 量 （ 取 0 或 1） 的 限 制 条 件 下 ， 极 大 化 总收 益 和 总 投 资 之 比 。 因 此 ， 其 数 学 模 型 为 ： 上 面 例 题 是 在 一 组 等 式 或 不 等 式 的 约 束 下 ， 求 一 个 函 数 的 最 大 值 （ 或 最小 值 ） 问 题 ， 其 中 目 标 函 数 或 约 束 条 件 中 至 少 有 一 个 非 线 性 函 数 ， 这 类 问 题称 之 为 非 线 性 规 划 问 题 ， 简 记 为 （ NP） 。 可 概 括 为 一 般 形 式 (NP) 其 中 x=x1 . xn称 为 模 型 （ NP） 的 决 策 变 量 ， f 称 为 目 标 函 数 ，gi 和 hj 称 为 约 束 函 数 。 另 外 ， gi(x)=0 称 为 等 式 约 束 ,hj(x)=0 称 为 不 等式 约 束 。 编 辑 本 段 常 见 问 题对 于 一 个 实 际 问 题 ， 在 把 它 归 结 成 非 线 性 规 划 问 题 时 ， 一 般 要 注 意 如 下几 点 ： （ i） 确 定 供 选 方 案 ： 首 先 要 收 集 同 问 题 有 关 的 资 料 和 数 据 ， 在 全 面 熟悉 问 题 的 基 础 上 ， 确 认 什 么 是 问 题 的 可 供 选 择 的 方 案 ， 并 用 一 组 变 量 来 表 示它 们 。 （ ii） 提 出 追 求 目 标 ： 经 过 资 料 分 析 ， 根 据 实 际 需 要 和 可 能 ， 提 出 要 追求 极 小 化 或 极 大 化 的 目 标 。 并 且 ， 运 用 各 种 科 学 和 技 术 原 理 ， 把 它 表 示 成 数学 关 系 式 。 （ iii） 给 出 价 值 标 准 ： 在 提 出 要 追 求 的 目 标 之 后 ， 要 确 立 所 考 虑 目 标的 “好 ”或 “坏 ”的 价 值 标 准 ， 并 用 某 种 数 量 形 式 来 描 述 它 。 （ iv） 寻 求 限 制 条 件 ： 由 于 所 追 求 的 目 标 一 般 都 要 在 一 定 的 条 件 下 取 得极 小 化 或 极 大 化 效 果 ， 因 此 还 需 要 寻 找 出 问 题 的 所 有 限 制 条 件 ， 这 些 条 件 通常 用 变 量 之 间 的 一 些 不 等 式 或 等 式 来 表 示 。 编 辑 本 段 数 学 模 型对 实 际 规 划 问 题 作 定 量 分 析 ， 必 须 建 立 数 学 模 型 。 建 立 数 学 模 型 首 先 要选 定 适 当 的 目 标 变 量 和 决 策 变 量 ， 并 建 立 起 目 标 变 量 与 决 策 变 量 之 间 的 函 数关 系 ,称 之 为 目 标 函 数 。 然 后 将 各 种 限 制 条 件 加 以 抽 象 ,得 出 决 策 变 量 应 满足 的 一 些 等 式 或 不 等 式 ， 称 之 为 约 束 条 件 。 非 线 性 规 划 问 题 的 一 般 数 学 模 型可 表 述 为 求 未 知 量 x1， x2， ， xn， 使 满 足 约 束 条 件 ： gi(x1， ， xn) 0 i 1,m hj(x1， ， xn) 0 j 1,p 并 使 目 标 函 数 f(x1， ,xn)达 到 最 小 值 (或 最 大 值 )。 其 中 f， 诸 gi 和诸 hj 都 是 定 义 在 n 维 向 量 空 间 Rn 的 某 子 集 D(定 义 域 )上 的 实 值 函 数 ,且 至少 有 一 个 是 非 线 性 函 数 。 上 述 模 型 可 简 记 为 ： min f(x) s.t. gi(x) 0 i 1,m hj(x) 0 j 1,p 其 中 x (x1， ,xn)属 于 定 义 域 D， 符 号 min 表 示 “求 最 小 值 ”， 符号 s.t.表 示 “受 约 束 于 ”。 定 义 域 D 中 满 足 约 束 条 件 的 点 称 为 问 题 的 可 行 解 。 全 体 可 行 解 所 成 的 集合 称 为 问 题 的 可 行 集 。 对 于 一 个 可 行 解 x*,如 果 存 在 x*的 一 个 邻 域 ， 使 目标 函 数 在 x*处 的 值 f(x*)优 于 (指 不 大 于 或 不 小 于 )该 邻 域 中 任 何 其 他 可 行解 处 的 函 数 值 ， 则 称 x*为 问 题 的 局 部 最 优 解 （ 简 称 局 部 解 ） 。 如 果 f(x*)优 于 一 切 可 行 解 处 的 目 标 函 数 值 ,则 称 x*为 问 题 的 整 体 最 优 解 （ 简 称 整 体 解 ）。 实 用 非 线 性 规 划 问 题 要 求 整 体 解 ， 而 现 有 解 法 大 多 只 是 求 出 局 部 解 。 编 辑 本 段 一 维 最 优 化 方 法指 寻 求 一 元 函 数 在 某 区 间 上 的 最 优 值 点 的 方 法 。 这 类 方 法 不 仅 有 实 用 价值 ， 而 且 大 量 多 维 最 优 化 方 法 都 依 赖 于 一 系 列 的 一 维 最 优 化 。 常 用 的 一 维 最优 化 方 法 有 黄 金 分 割 法 、 切 线 法 和 插 值 法 。 黄 金 分 割 法 又 称 0.618 法 。 它 适 用 于 单 峰 函 数 。 其 基 本 思 想 是 ：在 初 始 寻 查 区 间 中 设 计 一 列 点 ， 通 过 逐 次 比 较 其 函 数 值 ， 逐 步 缩 小 寻 查 区 间 ，以 得 出 近 似 最 优 值 点 。 切 线 法 又 称 牛 顿 法 。 它 也 是 针 对 单 峰 函 数 的 。 其 基 本 思 想 是 ： 在一 个 猜 测 点 附 近 将 目 标 函 数 的 导 函 数 线 性 化 ， 用 此 线 性 函 数 的 零 点 作 为 新 的猜 测 点 ， 逐 步 迭 代 去 逼 近 最 优 点 。 插 值 法 又 称 多 项 式 逼 近 法 。 其 基 本 思 想 是 用 多 项 式 （ 通 常 用 二 次或 三 次 多 项 式 ） 去 拟 合 目 标 函 数 。 此 外 ， 还 有 斐 波 那 契 法 、 割 线 法 、 有 理 插 值 法 、 分 批 搜 索 法 等 。 编 辑 本 段 无 约 束 最 优 化 方 法指 寻 求 n 元 实 函 数 f 在 整 个 n 维 向 量 空 间 Rn 上 的 最 优 值 点 的 方 法 。 这类 方 法 的 意 义 在 于 ： 虽 然 实 用 规 划 问 题 大 多 是 有 约 束 的 ， 但 许 多 约 束 最 优 化方 法 可 将 有 约 束 问 题 转 化 为 若 干 无 约 束 问 题 来 求 解 。 无 约 束 最 优 化 方 法 大 多 是 逐 次 一 维 搜 索 的 迭 代 算 法 。 这 类 迭 代 算 法 可 分为 两 类 。 一 类 需 要 用 目 标 函 数 的 导 函 数 ,称 为 解 析 法 。 另 一 类 不 涉 及 导 数 ，只 用 到 函 数 值 ,称 为 直 接 法 。 这 些 迭 代 算 法 的 基 本 思 想 是 ： 在 一 个 近 似 点 处选 定 一 个 有 利 搜 索 方 向 ,沿 这 个 方 向 进 行 一 维 寻 查 ,得 出 新 的 近 似 点 。 然 后对 新 点 施 行 同 样 手 续 ， 如 此 反 复 迭 代 ， 直 到 满 足 预 定 的 精 度 要 求 为 止 。 根 据搜 索 方 向 的 取 法 不 同 ， 可 以 有 各 种 算 法 。 属 于 解 析 型 的 算 法 有 ： 梯 度 法 ：又 称 最 速 下 降 法 。 这 是 早 期 的 解 析 法 ， 收 敛 速 度 较 慢 。 牛 顿 法 ： 收 敛 速度 快 ， 但 不 稳 定 ， 计 算 也 较 困 难 。 共 轭 梯 度 法 ： 收 敛 较 快 ， 效 果 较 好 。 变 尺 度 法 ： 这 是 一 类 效 率 较 高 的 方 法 。 其 中 达 维 登 -弗 莱 彻 -鲍 威 尔 变 尺度 法 ， 简 称 DFP 法 ， 是 最 常 用 的 方 法 。 属 于 直 接 型 的 算 法 有 交 替 方 向 法（ 又 称 坐 标 轮 换 法 ） 、 模 式 搜 索 法 、 旋 转 方 向 法 、 鲍 威 尔 共 轭 方 向 法 和 单 纯形 加 速 法 等 。 编 辑 本 段 约 束 最 优 化 方 法指 前 述 一 般 非 线 性 规 划 模 型 的 求 解 方 法 。 常 用 的 约 束 最 优 化 方 法 有 4种 。 拉 格 朗 日 乘 子 法 ： 它 是 将 原 问 题 转 化 为 求 拉 格 朗 日 函 数 的 驻 点 。 制 约 函 数 法 ： 又 称 系 列 无 约 束 最 小 化 方 法 ， 简 称 SUMT 法 。 它 又 分 两 类 ， 一类 叫 惩 罚 函 数 法 ， 或 称 外 点 法 ； 另 一 类 叫 障 碍 函 数 法 ， 或 称 内 点 法 。 它 们 都是 将 原 问 题 转 化 为 一 系 列 无 约 束 问 题 来 求 解 。 可 行 方 向 法 ： 这 是 一 类 通过 逐 次 选 取 可 行 下 降 方 向 去 逼 近 最 优 点 的 迭 代 算 法 。 如 佐 坦 迪 克 法 、 弗 兰 克 沃 尔 夫 法 、 投 影 梯 度 法 和 简 约 梯 度 法 都 属 于 此 类 算 法 。 近 似 型 算 法 ：这 类 算 法 包 括 序 贯 线 性 规 划 法 和 序 贯 二 次 规 划 法 。 前 者 将 原 问 题 化 为 一 系 列线 性 规 划 问 题 求 解 ， 后 者 将 原 问 题 化 为 一 系 列 二 次 规 划 问 题 求 解 。 编 辑 本 段 凸 规 划这 是 一 类 特 殊 的 非 线 性 规 划 。 在 前 述 非 线 性 规 划 数 学 模 型 中 ， 若 f 是凸 函 数 ， 诸 gi 都 是 凹 函 数 ,诸 hj 都 是 一 次 函 数 ， 则 称 之 为 凸 规 划 。 所 谓f 是 凸 函 数 ,是 指 f 有 如 下 性 质 ： 它 的 定 义 域 是 凸 集 ,且 对 于 定 义 域 中 任 意 两点 x 和 y 及 任 一 小 于 1 的 正 数 ， 下 式 都 成 立 ： f(1- )x + y) (1- )f(x)+ f(y) 将 上 述 不 等 式 中 的 不 等 号 反 向 即 得 凹 函 数 的 定 义 。 所 谓 凸 集 ， 是 指 具 有如 下 性 质 的 集 合 ： 连 结 集 合 中 任 意 两 点 的 直 线 段 上 的 点 全 部 属 于 该 集 合 。 对 于 一 般 的 非 线 性 规 划 问 题 ， 局 部 解 不 一 定 是 整 体 解 。 但 凸 规 划 的 局 部解 必 为 整 体 解 ， 而 且 凸 规 划 的 可 行 集 和 最 优 解 集 都 是 凸 集 。 编 辑 本 段 二 次 规 划一 类 特 殊 的 非 线 性 规 划 。 它 的 目 标 函 数 是 二 次 函 数 ， 约 束 条 件 是 线 性 的 。求 解 二 次 规 划 的 方 法 很 多 。 较 简 便 易 行 的 是 沃 尔 夫 法 。 它 是 依 据 库 恩 塔 克条 件 ， 在 线 性 规 划 单 纯 形 法 的 基 础 上 加 以 修 正 而 成 的 。 此 外 还 有 莱 姆 基 法 、毕 尔 法 、 凯 勒 法 等 。 编 辑 本 段 几 何 规 划几 何 规 划 一 类 特 殊 的 非 线 性 规 划 。 它 的 目 标 函 数 和 约 束 函 数 都 是 正 定多 项 式 （ 或 称 正 项 式 ） 。 几 何 规 划 本 身 一 般 不 是 凸 规 划 ， 但 经 适 当 变 量 替 换 ，即 可 变 为 凸 规 划 。 几 何 规 划 的 局 部 最 优 解 必 为 整 体 最 优 解 。 求 解 几 何 规 划 的方 法 有 两 类 。 一 类 是 通 过 对 偶 规 划 去 求 解 ； 另 一 类 是 直 接 求 解 原 规 划 ， 这 类算 法 大 多 建 立 在 根 据 几 何 不 等 式 将 多 项 式 转 化 为 单 项 式 的 思 想 上 。 编 辑 本 段 应 用 问 题在 经 营 管 理 、 工 程 设 计 、 科 学 研 究 、 军 事 指 挥 等 方 面 普 遍 地 存 在 着 最 优化 问 题 。 例 如 ： 如 何 在 现 有 人 力 、 物 力 、 财 力 条 件 下 合 理 安 排 产 品 生 产 ， 以取 得 最 高 的 利 润 ； 如 何 设 计 某 种 产 品 ， 在 满 足 规 格 、 性 能 要 求 的 前 提 下 ， 达到 最 低 的 成 本 ； 如 何 确 定 一 个 自 动 控 制 系 统 的 某 些 参 数 ， 使 系 统 的 工 作 状 态最 佳 ； 如 何 分 配 一