利用excel软件求解线性规划问题

1数学规划模型实验指导手册（一）怎样用Excel的规划求解加载宏求解数学规划问题李锋编著2008年3月3日2一 、 什 么 是 规 划 求 解 加 载 宏 ？规 划 求 解 加 载 宏 （ 简 称 规 划 求 解 ） 是 Excel 的 一 个 加 载 项 1， 可以用来解决线性规划与非线性规划优化问题。规划求解可以用来解决最多有 200个变量，100 个外在约束和 400个简单约束（决策变量整数约束的上下边界）的问题。可以设置决策变量为整型变量。规 划 求 解 加 载 宏 的 开 发 商 是 Fronline System 公 司 。 用 户 通 过 自 定 义 安 装 MS-Office 所 使 用 的 是 标 准 版 本 规 划 求 解 加 载 宏 ， Fronline System 公 司 同 时 提 供 增 强 的Premium Solver 工 具 。规 划 求 解 工 具 在 Office 典 型 安 装 状 态 下 不 会 安 装 ， 可 以 通 过 自 定 义 安 装 选 择 该 项或 通 过 添 加 /删 除 程 序 增 加 规 划 求 解 加 载 宏 。二 、 怎 样 加 载 规 划 求 解 加 载 宏 ？加 载 规 划 求 解 加 载 宏 的 方 法 如 下 ：（ 1） 打 开 “工 具 ”下 拉 列 菜 单 ， 然 后 单 击 “加 载 宏 ”， 打 开 “加 载 宏 ”对 话 框 。（ 2） 在 “可 用 加 载 宏 ”框 中 ， 选 中 “规 划 求 解 ”旁 边 的 复 选 框 2， 然 后 单 击“确 定 ”按 钮 。1加 载 项 的 功 能 是 为 Microsoft Office 提 供 自 定 义 命 令 或 自 定 义 功 能 的 补 充 程 序3（ 3） 如 果 出 现 一 条 消 息 ， 指 出 您 的 计 算 机 上 当 前 没 有 安 装 规 划 求 解 ， 请 单 击“是 ”用 原 Office 安 装 盘 进 行 安 装 。 （ 4） 单 击 菜 单 栏 上 的 “工 具 ”。 加 载 规 划 求 解 后 ， “规 划 求 解 ”命 令 会 添 加 到“工 具 ”菜 单 中 。 三、怎样使用规 划 求 解 加 载 宏 求 解 数 学 规 划 ？规 划 求 解 加 载 宏 是 一 组 命 令 构 成 的 一 个 子 程 序 ， 这 些 命 令 有 时 也 称 作 假 设 分 析 3工具 ， 其 功 能 是 可 以 求 出 线 性 和 非 线 性 数 学 规 划 问 题 的 最 优 解 和 最 优 值 。使 用 规 划 求 解 加 载 宏 求 解 数 学 规 划 的 步 骤首 先 ， 在 Excel 工 作 表 中 输 入 目 标 函 数 的 系 数 向 量 、 约 束 条 件 的 系 数 矩 阵 和 右 端 常数 项 （ 每 一 个 单 元 格 输 入 一 个 数 据 ） ；其 次 ， 选 定 一 个 单 元 格 存 储 目 标 函 数 （ 称 为 目 标 单 元 格 ） ， 用 定 义 公 式 的 方 式 在 这 个目 标 单 元 格 内 定 义 目 标 函 数 ；再 次 ， 选 定 与 决 策 变 量 个 数 相 同 的 单 元 格 （ 称 为 可 变 单 元 格 ） ， 用 以 存 储 决 策 变 量 ；再 选 择 与 约 束 条 件 个 数 相 同 的 单 元 格 ， 用 定 义 公 式 的 方 式 在 每 一 个 单 元 格 内 定 义 一 个 约束 函 数 （ 称 为 约 束 函 数 单 元 格 ） ；最 后 ， 点 击 下 拉 列 菜 单 中 的 规 划 求 解 按 钮 ， 打 开 规 划 求 解 参 数 设 定 对 话 框 （ 如 图4 所 示 ） ， 完 成 规 划 模 型 的 设 定模 型 设 定 方 法 如 下 ：（ 1） 设 定 目 标 函 数 和 优 化 方 向 ： 光 标 指 向 规 划 求 解 参 数 设 定 对 话 框 中 的 “设 置 目 标单 元 格 ”提 示 后 的 域 ， 点 击 鼠 标 左 键 ， 然 后 选 中 Excel 工 作 表 中 的 目 标 单 元 格 。 然 后2如 果 “规 划 求 解 ”未 列 出 ， 请 单 击 “浏 览 ”进 行 查 找 。3该 过 程 通 过 更 改 单 元 格 中 的 值 来 查 看 这 些 更 改 对 工 作 表 中 公 式 结 果 的 影 响 。 例 如 ， 更 改 分 期 支 付 表 中的 利 率 可 以 调 整 支 付 金 额 。4根 据 模 型 中 目 标 函 数 的 优 化 方 向 ， 在 规 划 求 解 参 数 设 定 对 话 框 中 的 “等 于 ”一 行 中 选择 “最 大 值 ”或 “最 小 值 ”；（ 2） 设 定 （ 表 示 决 策 变 量 的 ） 可 变 单 元 ： 光 标 指 向 规 划 求 解 参 数 设 定 对 话 框 中 的“可 变 单 元 格 ”提 示 后 的 域 ， 点 击 鼠 标 左 键 ， 然 后 选 中 Excel 工 作 表 中 的 可 变 单 元 组 。可 以 点 击 “推 测 ”按 钮 ， 初 步 确 定 可 变 单 元 格 的 范 围 ， 然 后 在 此 基 础 上 进 一 步 确 定 ；（ 3） 设 定 约 束 条 件 ： 直 接 点 击 规 划 求 解 参 数 设 定 对 话 框 中 的 添 加 按 钮 ， 出 现 如 下 添 加约 束 对 话 框 ：先 用 鼠 标 左 键 点 击 “单 元 格 引 用 位 置 ”标 题 下 的 域 ， 然 后 在 工 作 表 中 选 择 一 个 约 束函 数 单 元 格 ， 再 点 击 添 加 约 束 对 话 框 中 向 下 的 箭 头 ， 出 现 =， int 和 bin 五 个选 项 ， 根 据 该 约 束 函 数 所 在 约 束 方 程 的 情 况 选 择 ， 其 中 int 和 bin 分 别 用 于 说 明 整 型变 量 和 0 1 型 变 量 。 选 择 完 成 后 ， 如 果 还 有 约 束 条 件 未 设 定 ， 就 点 击 “添 加 ”按 钮 ，重 复 以 上 步 骤 设 定 约 束 条 件 ， 设 定 完 所 有 约 束 条 件 后 ， 点 击 确 定 完 成 约 束 条 件 设 定 ， 回到 规 划 求 解 参 数 设 定 对 话 框 。（ 4） 设 定 算 法 细 节 ： 点 击 规 划 求 解 参 数 设 定 对 话 框 中 的 “选 项 ”按 钮 ， 出 现 如 下 规划 求 解 选 项 对 话 框 。该 对 话 框 为 使 用 者 提 供 了 在 一 些 可 供 选 择 的 常 用 算 法 。 主 要 是 供 高 级 用 户 使 用 ， 初学 者 不 必 考 虑 这 些 选 择 。5选 择 完 成 后 点 击 确 定 按 钮 回 到 规 划 求 解 参 数 设 定 对 话 框（ 5） 求 解 模 型 ： 完 成 以 上 设 定 后 ， 点 击 规 划 求 解 参 数 设 定 对 话 框 中 的 “求 解 ”按 钮 ，将 出 现 如 下 求 解 结 果 对 话 框 。根 据 需 要 选 择 右 边 列 出 的 三 个 报 告 中 的 一 部 分 或 全 部 ， 然 后 点 击 确 定 按 钮 就 可 以 在Excel 内 看 到 求 解 报 告 。四、用规划求解加载宏求解数学规划举例下 面 我 们 通 过 一 个 例 子 来 解 释 怎 样 用 “规 划 求 解 ”来 求 解 数 学 规 划 问 题 。例 1 公 司 通 常 需 要 确 定 每 月 （ 或 每 周 ） 生 产 计 划 ， 列 出 每 种 产 品 必 须 生 产 的 数 量 。具 体 来 说 就 是 ， 产 品 组 合 问 题 就 是 要 确 定 公 司 每 月 应 该 生 产 的 每 种 产 品 的 数 量 以 使 利润 最 大 化 。 产 品 组 合 通 常 必 须 满 足 以 下 约 束 ： 产 品 组 合 使 用 的 资 源 不 能 超 标 。 对 每 种 产 品 的 需 求 都 是 有 限 的 。 我 们 每 月 生 产 的 产 品 不 能 超 过 需 求 的 数 量 ， 因 为 生 产过 剩 就 是 浪 费 （ 例 如 ， 易 变 质 的 药 品 ） 。 下 面 ， 我 们 来 考 虑 让 某 医 药 公 司 的 最 优 产 品 组 合 问 题 。 该 公 司 有 六 种 可 以 生 产 的 药品 ， 相 关 数 据 如 下 表 所 示 。表 1消耗系数产品1产品2产品3产品4产品5产品6 现有劳动力（小时）6 5 4 3 2.5 1.5 4500原料（磅） 3.2 2.6 1.5 0.8 0.7 0.3 1600单位利润（元）6 5.3 5.4 4.2 3.8 1.8 需求量（磅） 960 928 1041 977 1084 1055 设 该 公 司 生 产 药 品 1 6 的 产 量 分 别 为 （ 磅 ） ， 则 最 优 产 品 组 合 的 线 性126,x规 划 模 型 为6123456123456123456max6581.03.07.3968. 710,jzxxxxst xj下 面 用 规划求解加载宏来求解这个问题：首先，如下如所示，在 Excel工作表内输入目标函数的系数、约束方程的系数、右端常数项；其次，选定目标函数单元、可变单元、约束函数单元，定义目标函数、约束函数系数矩阵 目标函数的系数系数矩阵右端常数可变单元约束函数单元目标函数单元7其中，劳动力约束函数的定义公式是“=MMULT(B3:G3, J5:J10)” ，原料约束函数的定义公式是“MMULT(B4:G4,J5:J10)” ，目标函数的定义公式是“MMULT(B5:G5, J5:J10)” 。注：函数 MMULT(B3:G3, J5:J10)的意义是：单元区 B3:G3表示的行向量与单元区 J5:J10表示的列向量的内积。这一要特别注意的是，第一格单元区必须是行，第二格单元区必须是列，并且两个单元区所含的单元格个数必须相等。最 后 ， 打 开 规 划 求 解 参 数 设 定 对 话 框 设 定 模 型（ 1） （ 2） 目 标 函 数 和 可 边 单 元 的 设 定 很 简 单 ， 在 此 就 不 再 赘 述（ 3） 约 束 条 件 的 设 定(3.1) 约 束 条 件 的 设 定 ：123456652.1.403.0873xxx（ 3.2） 约 束 条 件 的 设 定1234569608710xx8（ 3.3） 约 束 条 件 的 设 定1260,0xx这 里 值 得 注 意 的 是 ： 我 们 采 用 向 量 的 形 式 设 定 同 向 不 等 式 ， 并 且 不 等 式 两 边 可 以 一 个 时 行 向 量 ， 另一 个 是 列 向 量 ； 对 所 有 分 量 都 是 0 的 向 量 ， 我 们 可 以 用 一 个 0 来 代 替 。（ 4） 求 解 ： 我 们 选 择 保 存 三 个 报 告得 到 的 三 张 份 告 如 下910补 充 说 明 ：a) 如 果 数 学 规 划 模 型 中 包 含 整 型 变 量 或 0 1 型 变 量 ， 只 需 要 在 设 定 约 束 条 件 一步 中 设 定 相 应 的 变 量 是 整 型 变 量 或 0 1 型 变 量 即 可 。 例 如 ， 假 定 在 上 例 中 变量 是 整 型 变 量 ， 只 需 要 增 加 如 下 图 所 示 的 整 型 约 束 设 定 即 可 。 不 过 要 注 意12,x的 是 ， 含 整 型 变 量 或 0 1 型 变 量 的 问 题 是 不 能 进 行 敏 感 性 分 析 的 。b) 求 解 报 告 中 把 输 出 目 标 函 数 单 元 、 约 束 函 数 单 元 、 和 可 边 单 元 上 方 第 一 个 输 有 文字 单 元 及 左 边 第 一 个 输 有 文 字 单 元 内 全 部 文 字 都 作 为 对 解 释 目 标 函 数 单 元 、 约 束函 数 单 元 、 和 可 边 单 元 的 解 释 ， 例 如 ， 把 Excel 表 改 为11则 求 解 报 告 输 出 变 为c) 另 外 ， 非 线 性 规 划 模 型 的 求 解 方 法 类 似 ， 在 此 不 再 赘 述 。五、 “规划求解”疑难解答1、尚未找到满足要求的结果，“规划求解”即停止了运行由于下列任意一个原因，“规划求解”在找到答案前，可能停止运行： 中断了求解过程。 在单击“求解”之前，选中了“规划求解选项”对话框中的“显示迭代结果”选项。 在单步迭代过程中，或达到最长运算时间或最大迭代次数时，单击了“停止”按钮。 选中了“规划求解选项”对话框中的“采用线性模型”复选框，但问题是非线性的。 在“规划求解参数”对话框的“设置目标单元格”框中指定的数值不收敛地增加或减少。 需要让“规划求解”运行更长的时间以求得结果。请调整“规划求解选项”对话框中的“最长运算时间”或“迭代次数”的设置。 对于具有整数约束条件的问题，应该减小“规划求解选项”对话框中的“允许误差”的设置，使“规划求解”找到更好的整数解。 对于非线性问题，应该减小“规划求解选项”对话框中的“收敛度”的设置，使目标单元格数值变化缓慢时，“规划求解”仍可以运行，最终找到较好的结果。 12 应该选中“规划求解选项”对话框中的“自动按比例缩放”复选框，可能一些输入数值相差几个数量级，或输入和输出数值相差几个数量级。 当“规划求解”停止运行时，在“规划求解结果”对话框中显示出完成信息。单击“保存规划求解结果”或“恢复为原值”，进行所需的更改，然后再运行一次。2、可变单元格与约束条件或目标单元格中的数值差别很大当可变单元格的典型数值与约束单元格或目标单元格中的数值相差几个数量级时，请选中“规划求解选项”对话框中的“自动按比例缩放”复选框。对于非线性问题，在单击“规划求解参数”对话框中的“求解”之前，请确认可变单元格的初始数值与期望的最终数值的数量级相同。3、未得到预期的结果对于非线性问题，在可变单元格中尝试不同的初始值可能会有帮助，特别是在“规划求解”结果与期望的数值差别很大时。预先将可变单元格的数值设置为预期的最优值，可以减少求解时间。对于线性模型（也就是当“规划求解选项”对话框的“采用线性模型”复选框被选中时），改变可变单元格的初始值不会影响最终数值或求解时间。4、“规划求解”得到的结果与以前的结果不同“规划求解”显示如下消息：“规划求解已收敛到当前结果。满足所有约束条件”。这表明目标单元格中的数值在最近五次求解过程中的变化量小于“规划求解选项”对话框中“收敛度”设置的值。“收敛度”中设置的值越小，“规划求解”在计算时就会越精细，但求解过程将花费更多的时间。5、“规划求解”不能达到最优解下面列出“规划求解”显示的完整消息。 “规划求解”不能改进当前解。所有约束条件都得到了满足这表明仅得到近似值，迭代过程无法得到比显示结果更精确的数值；或是无法进一步提高精度，或是精度值设置得太小，请在“规划求解选项”对话框中试着设置较大的精度值，然后再运行一次。 求解达到最长运算时间后停止这表明在达到最长运算时间限制时，没有得到满意的结果。若要保存当前结果并节省下次计算的时间，请单击“保存规划求解”或“保存方案”选项。 求解达到最大迭代次数后停止13这表明在达到最大迭代次数时，没有得到满意的结果。增加迭代次数也许有用，但是应该先检查结果数值来确定问题的原因。若要保存当前值并节省下次计算的时间，请单击“保存规划求解”或“保存方案”选项。 目标单元格中的数值不收敛这表明即使满足全部约束条件，目标单元格数值也只是有增或有减但不收敛。这可能是在设置问题时忽