excel建模整数规划 实用运筹学－运用Excel建模和求解.pptVIP

实用运筹学－运用Excel建模和求解 第6章 整数规划 本章内容要点 整数规划的基本概念 整数规划问题的建模与应用 本章节内容 6.1 整数规划基本概念、分类与解的特点 6.2 整数规划电子表格模型 6.3 0-1整数规划 6.4 整数规划应用举例 本章主要内容框架图 6.1 整数规划基本概念、分类与解的特点 在许多实际问题中，决策变量必须为整数。例如当决策变量是分配的人数、购买的设备数、投入的车辆数、是否投资等时，它们一般必须为非负整数才有意义。在这种情况下，常需要应用整数规划进行优化。 整数规划（Integer Programming，简称IP），是要求全部或部分决策变量为整数的规划。整数规划分为线性整数规划和非线性整数规划。本章只介绍线性整数规划，简称为整数规划。 整数规划分为两大类：一般整数规划与0-1整数规划（Binary Integer Programming，简称BIP）。 整数规划与一般规划相比，其可行解不是连续的，而是离散的。 6.1 整数规划基本概念、分类与解的特点 例6.1 某航空公司是一家使用小飞机经营短途航线的小型区域性企业。该公司已经经营得不错，其管理层决定拓展其经营领域。 管理层面临的基本问题是：是采购更多的小型飞机来开辟一些新的短途航线，还是开始通过为一些跨地区航线购买大型的飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获得最高收益？ 表6-1提供了购买每一种飞机的年净利润期望（包括资本回收成本）；给出了每架飞机的采购成本，以及可用于飞机采购的总可用资金1亿元；并表明了管理层希望小飞机的采购不超过两架。 需要的决策是：小型飞机和大型飞机各需要采购多少才能够获得最大的年总净利润？ 6.1 整数规划基本概念、分类与解的特点 解： (1)决策变量 设小型飞机与大型飞机的购买数量分别为x1、x2(架)。 (2)目标函数 目标是年总净利润最大。 (3) 约束条件 ① 资金限制 ② 小型飞机数量限制（最多购买2架） ③ 非负且均为整数 6.1 整数规划基本概念、分类与解的特点 求解： (1)先去掉整数约束，作为一般线性规划问题，用图解法求出的最优解x1＝2，x2＝1.8。 如何进行“取、舍”？ (2)由于离散问题比连续问题更难以处理，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的基本算法有分支定界法、割平面法等。 Excel“规划求解”工具求解整数规划问题采用分支定界法。 6.2 整数规划电子表格模型 用Excel求解整数规划的基本步骤与求解一般线性规划问题相同，只是在约束条件中添加一个“整数”约束。在Excel规划求解的“添加约束”对话框中，用“int”表示整数。因此，只要在该对话框中添加一个约束条件，在左边输入要求取整的决策变量的单元格地址，然后选择“int”。 6.2 整数规划电子表格模型 例6.1的电子表格模型 6.3 0-1整数规划 0-1整数规划（BIP）是整数规划的特殊情况，也是应用最广泛的一类整数规划。在0-1整数规划中，其整数变量只能取0或1，通常用这些0－1变量表示某种逻辑关系。例如用“1”表示“是”，用“0”表示“非”。 0-1整数规划模型的建立和求解方法与一般线性规划模型相同，只是增加了一个“决策变量必须为0或1”的约束条件。为反映这一约束条件，在求解时应在Excel规划求解的“添加约束”对话框中添加关于决策变量取值为1或0的约束条件。“添加约束”对话框中，用“bin”（Binary）表示0和1两者取一。因此，只要在约束条件左边输入要求取0或1的决策变量的单元格地址，然后选择“bin”即可。 6.3 0-1整数规划 例6.2 分公司选址问题。某销售公司打算通过在武汉或长春设立分公司（也可以在两个城市都设分公司）以增加市场份额，管理层同时也在考虑建立一个配送中心（也可以不建配送中心），但配送中心地点限制在新设分公司的城市。 经过计算，每种选择使公司收益的净现值和所需费用如表6-2所示。总的预算费用不得超过1000万元。目标是在满足以上约束的条件下使总的净现值最大。 6.3 0-1整数规划 解： （1）决策变量 本题的决策变量是是非决策的0-1决策变量，每一个决策只有两种选择，是或者否，1表示对于这个决策选择“是”，0表示对于这个决策选择“否” 。 6.3 0-1整数规划 (2)目标函数 总的净现值最大。 (3) 约束条件 ① 总预算支出 ② 公司最多只建一个新配送中心（互斥） ③ 公司只在新设分公司的城市建配送中心（相依） ④ 0－1变量 6.3 0-1整数规划 例6.2的电子表格模型 6.3 0-1整数规划 由于可用资金没有使用完（只使用了可用资金1000万元中的900万元）