第6章 整数规划 RUC, School of Information ,Ye Xiang 实用运筹学 运用Excel建模和求解 第6章 整数规划 第6章 整数规划 RUC, School of Information ,Ye Xiang 本章内容要点 整数规划的基本概念 整数规划问题的建模与应用 第6章 整数规划 RUC, School of Information ,Ye Xiang 本章节内容 6.1 整数规划基本概念、分类与解的特点 6.2 整数规划电子表格模型 6.3 0-1整数规划 6.4 整数规划应用举例 第6章 整数规划 RUC, School of Information ,Ye Xiang 本章主要内容框架图 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.1 整数规划基本概念、分类与解的特点 u 在许多实际问题中，决策变量必须为整数。例如 当决策变量是分配的人数、购买的设备数、投入 的车辆数、是否投资等时，它们一般必须为非负 整数才有意义。在这种情况下，常需要应用整数 规划进行优化。 u 整数规划（Integer Programming，简称IP），是 要求全部或部分决策变量为整数的规划。整数规 划分为线性整数规划和非线性整数规划。本章只 介绍线性整数规划，简称为整数规划。 u 整数规划分为两大类：一般整数规划与0-1整数规 划（Binary Integer Programming，简称BIP）。 u 整数规划与一般规划相比，其可行解不是连续的 ，而是离散的。 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.1 整数规划基本概念、分类与解的特点 例6.1 某航空公司是一家使用小飞机经营短途航线的小型区域 性企业。该公司已经经营得不错，其管理层决定拓展其经营领 域。 管理层面临的基本问题是：是采购更多的小型飞机来开辟一 些新的短途航线，还是开始通过为一些跨地区航线购买大型的 飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获 得最高收益？ 表6-1提供了购买每一种飞机的年净利润期望（包括资本回 收成本）；给出了每架飞机的采购成本，以及可用于飞机采购 的总可用资金1亿元；并表明了管理层希望小飞机的采购不超过 两架。 需要的决策是：小型飞机和大型飞机各需要采购多少才能 够获得最大的年总净利润？ 小型飞机大型飞机可获得的总资金 每架飞机年利润100万元500万元1亿元 每架飞机采购成本500万元5000万元 最多购买数量2没有限制 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.1 整数规划基本概念、分类与解的特点 解： (1)决策变量 设小型飞机与大型飞机的购买 数量分别为x1、x2(架)。 (2)目标函数 目标是年总净利润最大。 (3) 约束条件 资金限制 小型飞机数量限制（最多 购买2架） 非负且均为整数 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.1 整数规划基本概念、分类与解的特点 求解： u (1)先去掉整数约束，作为一般线性规划问 题，用图解法求出的最优解x12，x21.8 。 如何进行“取、舍”？ u (2)由于离散问题比连续问题更难以处理， 整数规划要比一般线性规划难解得多，而且 至今尚无一种像求解线性规划那样较成熟的 算法。目前常用的基本算法有分支定界法、 割平面法等。 u Excel“规划求解”工具求解整数规划问题 采用分支定界法。 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.2 整数规划电子表格模型 用Excel求解整数规划的基本步骤与求解一般线 性规划问题相同，只是在约束条件中添加一 个“整数”约束。在Excel规划求解的“添 加约束”对话框中，用“int”表示整数。 因此，只要在该对话框中添加一个约束条件 ，在左边输入要求取整的决策变量的单元格 地址，然后选择“int”。 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.2 整数规划电子表格模型 例 6 . 1 的 电 子 表 格 模 型 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 u 0-1整数规划（BIP）是整数规划的特殊情况，也 是应用最广泛的一类整数规划。在0-1整数规划中 ，其整数变量只能取0或1，通常用这些01变量 表示某种逻辑关系。例如用“1”表示“是”，用 “0”表示“非”。 u 0-1整数规划模型的建立和求解方法与一般线性规 划模型相同，只是增加了一个“决策变量必须为0 或1”的约束条件。为反映这一约束条件，在求解 时应在Excel规划求解的“添加约束”对话框中添 加关于决策变量取值为1或0的约束条件。“添加 约束”对话框中，用“bin”（Binary）表示0和1 两者取一。因此，只要在约束条件左边输入要求 取0或1的决策变量的单元格地址，然后选择 “bin”即可。 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 例6.2 分公司选址问题。某销售公司打算通过在武 汉或长春设立分公司（也可以在两个城市都设分公 司）以增加市场份额，管理层同时也在考虑建立一 个配送中心（也可以不建配送中心），但配送中心 地点限制在新设分公司的城市。 经过计算，每种选择使公司收益的净现值和所 需费用如表6-2所示。总的预算费用不得超过1000 万元。目标是在满足以上约束的条件下使总的净现 值最大。 净现值（万元）所需资金（万元） 在长春设立分公司800600 在武汉设立分公司500300 在长春建配送中心600500 在武汉建配送中心400200 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 解： （1）决策变量 本题的决策变量是是非决策的0-1决策变量，每一个决策 只有两种选择，是或者否，1表示对于这个决策选择“是 ”，0表示对于这个决策选择“否” 。 是非决策问题决策变量可能取值 在长春设立分公司？x10或1 在武汉设立分公司？x20或1 在长春建配送中心？x30或1 在武汉建配送中心？x40或1 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 (2)目标函数 总的净现值最大 。 (3) 约束条件 总预算支出 公司最多只建 一个新配送中心（ 互斥） 公司只在新设 分公司的城市建配 送中心（相依） 01变量 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 例6.2的电子表格模型 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3 0-1整数规划 由于可用资金没有使用完（只使用了可用资金1000万 元中的900万元），并且没有建配送中心，所以可以对 可用资金进行敏感性分析。 可用资金 （万元） 实际使用 （万元） 建配送中心?设立分公司? 总的净现值 （万元） 长春武汉长春武汉 7005000101900 8005000101900 90090000111300 100090000111300 1100110001111700 1200110001111700 1300110001111700 1400140010111900 1500140010111900 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 u在例6.2中，每个0-1变量表示一个是非决策 ，这些变量也称为0-1决策变量。除了这些0-1 决策变量，有时还引入其他一些0-1变量以帮 助建立模型。辅助0-1变量，是引入模型的附 加0-1变量，不代表一个是非决策，仅仅是为 了方便建立纯的或混合的0-1整数规划模型。 u下面介绍辅助0-1变量的4种使用方法，在这 些方法中，辅助0-1变量在使问题标准化以便 于求解方面发挥了重要作用。 固定成本问题、产品互斥问题、两个约束 中选一个约束的问题、N个约束中选K个约束的 问题 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 固定成本问题 u在一般情况下，产品的成本是由固定成本和可变 成本两部分组成。固定成本是指在固定投入要素上 的支出，它不受产量影响，例如厂房和设备的租金 、贷款利息、管理费用等；可变成本是指在可变投 入要素上的支出，它是随着产量变化而变化的成本 ，例如原材料费用、生产工人的工资、销售佣金等 。 u通常，变动成本和产量成正比，所以可以用下面 的表达式来代表某一产品的总成本 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 固定成本问题 u对于有n种产品生产问题的一般模型可以表示如 下： u引入yi：是否生产第i种产品 u转化为： 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 例6.3 含有启动成本（固定成本）的 例1.1。假设将例1.1的问题作如下变 形： 变化一：生产新产品（门和窗）各 需要一笔启动成本，分别为700元和 1300元，门和窗的单位利润还是原来 的300元和500元。 变化二：一个生产批次在一个星期 后即终止，因此门和窗的产量需要取 整。 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 解：(1) 决策变量 由于涉及启动成本（固定成本），本问题的决策 变量有两类，第一类是所需要生产的门和窗的数量 ；第二类是决定是否生产门和窗，这种逻辑关系可 用辅助0-1变量来表示。 整数决策变量：设x1、x2分别为门和窗的每 周产量。 辅助0-1变量：设y1、y2分别表示是否生产门 和窗，取0值时表示不生产，取1值时表示生产。 (2) 目标函数 本问题的目标是公司的总利润最大： 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 (3) 约束条件 原有的三个 车间每周可用工 时限制 变化一，新 产品需要启动成 本，即产量xi与是 否生产yi之间的关 系 产量xi非负 且为整数（变化 二）、是否生产yi 为0-1变量 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 例6.3的电子表格模型。在Excel中，相对极大值M需要数值 化，从车间1和车间2的约束中可以看出，x1的最大取值为4，x2的最大 取值为6，因此，M的取值只需不小于6即可，这里取99（需要说明的 是：为了区别其他数据，相对极大值M一般取9，99，999，） 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 产品互斥问题 u在实际生产过程中，为了防止产品的多元化，有 时需要限制产品生产的种类，这就是产品互斥问题 。 u处理产品互斥问题时，采用处理固定成本问题的 方法，引入辅助0-1变量：第i种产品是否生产yi。 u因此，在n种产品中，最多只能生产k种的约束为 ： u还有，产量xi与是否生产yi之间的关系： 第6章 整数规划 RUC, School of Information ,Ye Xiang 6.3.2 辅助0-1变量 例6.4 包含互斥产品的例