excel建模整数规划.ppt

《excel建模整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用运筹学－运用Excel建模和求解第6章整数规划本章内容要点整数规划的基本概念整数规划问题的建模与应用本章节内容6.1整数规划基本概念、分类与解的特点6.2整数规划电子表格模型6.30-1整数规划6.4整数规划应用举例本章主要内容框架图6.1整数规划基本概念、分类与解的特点在许多实际问题中，决策变量必须为整数。例如当决策变量是分配的人数、购买的设备数、投入的车辆数、是否投资等时，它们一般必须为非负整数才有意义。在这种情况下，常需要应用整数规划进行优化。整数规划（IntegerProgramming，简称IP），是要求全部或部分决策变量为整数的规划。整数规划分为线性整数规划和非线性整

2、数规划。本章只介绍线性整数规划，简称为整数规划。整数规划分为两大类：一般整数规划与0-1整数规划（BinaryIntegerProgramming，简称BIP）。整数规划与一般规划相比，其可行解不是连续的，而是离散的。6.1整数规划基本概念、分类与解的特点例6.1某航空公司是一家使用小飞机经营短途航线的小型区域性企业。该公司已经经营得不错，其管理层决定拓展其经营领域。管理层面临的基本问题是：是采购更多的小型飞机来开辟一些新的短途航线，还是开始通过为一些跨地区航线购买大型的飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获得最高收益？表6-1提供了购买每一种飞机的年净利润期望（包括

3、资本回收成本）；给出了每架飞机的采购成本，以及可用于飞机采购的总可用资金1亿元；并表明了管理层希望小飞机的采购不超过两架。需要的决策是：小型飞机和大型飞机各需要采购多少才能够获得最大的年总净利润？小型飞机大型飞机可获得的总资金每架飞机年利润100万元500万元1亿元每架飞机采购成本500万元5000万元最多购买数量2没有限制6.1整数规划基本概念、分类与解的特点解：(1)决策变量设小型飞机与大型飞机的购买数量分别为x1、x2(架)。(2)目标函数目标是年总净利润最大。(3)约束条件①资金限制②小型飞机数量限制（最多购买2架）③非负且均为整数6.1整数规划基本概念、分类与解的特点求解：

4、(1)先去掉整数约束，作为一般线性规划问题，用图解法求出的最优解x1＝2，x2＝1.8。如何进行“取、舍”？(2)由于离散问题比连续问题更难以处理，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的基本算法有分支定界法、割平面法等。Excel“规划求解”工具求解整数规划问题采用分支定界法。6.2整数规划电子表格模型用Excel求解整数规划的基本步骤与求解一般线性规划问题相同，只是在约束条件中添加一个“整数”约束。在Excel规划求解的“添加约束”对话框中，用“int”表示整数。因此，只要在该对话框中添加一个约束条件，在左边输入要求取整的决策变

5、量的单元格地址，然后选择“int”。6.2整数规划电子表格模型例6.1的电子表格模型6.30-1整数规划0-1整数规划（BIP）是整数规划的特殊情况，也是应用最广泛的一类整数规划。在0-1整数规划中，其整数变量只能取0或1，通常用这些0－1变量表示某种逻辑关系。例如用“1”表示“是”，用“0”表示“非”。0-1整数规划模型的建立和求解方法与一般线性规划模型相同，只是增加了一个“决策变量必须为0或1”的约束条件。为反映这一约束条件，在求解时应在Excel规划求解的“添加约束”对话框中添加关于决策变量取值为1或0的约束条件。“添加约束”对话框中，用“bin”（Binary）表示0和1两者

6、取一。因此，只要在约束条件左边输入要求取0或1的决策变量的单元格地址，然后选择“bin”即可。6.30-1整数规划例6.2分公司选址问题。某销售公司打算通过在武汉或长春设立分公司（也可以在两个城市都设分公司）以增加市场份额，管理层同时也在考虑建立一个配送中心（也可以不建配送中心），但配送中心地点限制在新设分公司的城市。经过计算，每种选择使公司收益的净现值和所需费用如表6-2所示。总的预算费用不得超过1000万元。目标是在满足以上约束的条件下使总的净现值最大。净现值（万元）所需资金（万元）在长春设立分公司800600在武汉设立分公司500300在长春建配送中心600500在武汉建配送中

7、心4002006.30-1整数规划解：（1）决策变量本题的决策变量是是非决策的0-1决策变量，每一个决策只有两种选择，是或者否，1表示对于这个决策选择“是”，0表示对于这个决策选择“否”。是非决策问题决策变量可能取值在长春设立分公司？x10或1在武汉设立分公司？x20或1在长春建配送中心？x30或1在武汉建配送中心？x40或16.30-1整数规划(2)目标函数总的净现值最大。(3)约束条件①总预算支出②公司最多只建一个新配送中心（互斥）③公司只在新设分公司