《运筹学（第3版）》 课件 第5章 整数规划

实用运筹学

－－运用Excel建模和求解（第3版）第5章整数规划IntegerProgramming本章内容要点整数规划的基本概念一般整数规划的建模与应用背包问题排班问题0-1规划的建模与应用本章主要内容框架图5.1整数规划的基本概念在许多实际问题中，决策变量必须为整数。例如，当决策变量是指派的人数、购买的设备数、投入的车辆数、是否投资等的时候，它们一般必须为非负整数才有意义。在这种情况下，常常需要应用整数规划进行优化。整数规划是要求全部或部分决策变量为整数的规划。整数规划分为线性整数规划和非线性整数规划。本章只介绍线性整数规划，简称为整数规划。整数规划分为两大类：一般整数规划与0-1整数规划。整数规划与一般规划相比，其可行解不再是连续的，而是离散的。5.2一般整数规划例5-1

某航空公司是一家使用小型飞机经营短途航线的小型区域性企业。该航空公司已经经营得不错，管理层决定拓展其经营领域。管理层面临的基本问题是：是采购更多小型飞机来开辟一些新的短途航线，还是开始通过为一些跨地区航线购买大型飞机来进军全国市场（或双管齐下）？哪种战略最有可能获得最大收益？表5-1提供了购买两种飞机的年利润估计值；给出了每架飞机的采购成本，以及可用于飞机采购的总可用资金；并表明了管理层希望小型飞机的采购量不超过2架。需要做的决策是：小型飞机和大型飞机各采购多少架，才能获得最大利润？小型飞机大型飞机每架飞机的年利润（百万元）15每架飞机的采购成本（百万元）550最多购买数量（架）2没有限制总可用资金（百万元）1005.2一般整数规划【解】（1）决策变量设小型飞机与大型飞机的购买数量分别为x1(架)和x2

(架)。（2）目标函数总利润最大。（3）约束条件①资金限制②小型飞机数量限制（最多购买2架）③变量非负，且均为整数5.2一般整数规划（1）为了进行比较，暂不考虑“整数”约束，看作一般的线性规划问题，用图解法求出的最优解x1＝2，x2＝1.8

如何进行“取、舍”？（2）由于离散问题比连续问题更难处理，因此，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的基本算法有分支定界法、割平面法等。Excel”规划求解”功能采用分支定界法来求解整数规划问题。5.2一般整数规划用Excel求解整数规划问题的基本步骤与求解一般线性规划问题相同，只是在约束条件中多添加一个“整数”约束。在Excel规划求解的“添加约束”对话框中，用“int”表示整数。因此，只要在该对话框中添加一个约束条件，在左边输入要求取整的决策变量的单元格（或区域），然后选择“int”。5.2一般整数规划例5-1的电子表格模型5.3背包问题背包问题可以抽象为这样一类问题：设有n种物品，已知每种物品的重量及价值；同时有一个背包，最大承重为C，现从n种物品中选取若干件（同一种物品可以选多件），使其总重量不超过C，而且总价值最大。背包问题等同于车、船、人造卫星等工具的最优装载问题，有广泛的实际意义。5.3.1一维背包问题例5-2

某货运公司使用一种最大承载能力为10吨的卡车来装载三种货物，每种货物的单位重量和单位价值如表5-2所示。应当如何装载货物才能使总价值最大？货物编号123单位重量（吨）345单位价值（万元）4565.3.1一维背包问题【解】本问题是典型的一维背包问题。（1）决策变量设卡车装载的编号为i的货物有xi件（i=1,2,3）。（2）目标函数总价值最大。（3）约束条件①卡车最大承载能力限制②变量非负，且均为整数5.3.1一维背包问题例5-2的电子表格模型5.3.2多维背包问题当约束条件不仅有货物的重量，还有体积等限制时，构成了多维背包问题。例5-3

现有一辆载重为5吨、装载体积为8立方米的卡车，可装载三种货物，已知每种货物各有8件，其他有关信息如表5-3所示，求携带货物价值最大的装载方案。货物品种单位重量（吨）单位体积（立方米）单位价值（万元）10.20.3320.40.57.530.30.465.3.2多维背包问题【解】本问题是典型的多维背包问题。（1）决策变量设卡车装载的第i种货物的数量为xi件（i=1,2,3）。（2）目标函数总价值最大。（3）约束条件①卡车载重限制②卡车装载体积限制③每种货物最多8件④变量非负，且均为整数5.3.2多维背包问题例5-3的电子表格模型5.4排班问题例5-4

某航空公司正准备增加其中心机场的往来航班，因此需要雇用更多的服务人员。不同时段有最少需求人数，有5种排班方式（连续工作8个小时）。时段排班1排班2排班3排班4排班5最少需求人数06:00～08:00√4808:00～10:00√√7910:00～12:00√√6512:00～14:00√√√8714:00～16:00√√6416:00～18:00√√7318:00～20:00√√8220:00～22:00√4322:00～24:00√√5200:00～6:00√15每人每天工资（元）1701601751801955.4排班问题【解】本问题是排班问题。（1）决策变量确定不同排班的上班人数。设：xi为排班i的上班人数(i＝1,2,

,5)（2）目标函数每天的总成本最小。（3）约束条件①每个时段的在岗人数必须不少于最少需求人数②变量非负，且均为整数5.4排班问题例5-4的线性规划模型5.4排班问题例5-4的电子表格模型5.5显性0-1变量的整数规划0-1规划是整数规划的特殊情况，也是应用最广泛的一类整数规划。在0-1规划中，其整数变量只能取0或1，通常用这些0-1变量表示某种逻辑关系。例如：用“1”表示“是”，用“0”表示“非（否）”。0-1规划模型的建立和求解方法与一般线性规划模型相同，只是增加了一个“变量取值必须是0或1”的约束条件。为反映这一约束条件，在求解时应在Excel规划求解的“添加约束”对话框中添加关于变量取值为1或0的约束条件。在“添加约束”对话框中，用“bin”（Binary）表示“0”和“1”两者取一。因此，只需在约束条件左边输入要求取“0”或“1”的变量的单元格（或区域），然后选择“bin”。5.5显性0-1变量的整数规划请体会以下不同情况下决策变量的逻辑关系区别。例如，两个０-1变量x1和x2分别表示两个决策的指令状态，则：（1）x1＋x1＝0，表示两者皆非；（2）x1＋x1＝1，表示两者中有且只有一个许可；（3）x1＋x1＝2，表示两者必须同时许可；（4）x1＋x1≤1，表示两者至多一个许可，但不排除两者皆非的情况；（5）x1＋x1≥1，表示两者至少一个许可，但不排除两者皆可的情况；（6）x1＋x1≤2，表示两者可以以上述任何情况出现，实际上是同时放弃了对这两个逻辑变量的约束。5.5显性0-1变量的整数规划例5-5分公司选址问题。某销售公司打算在长春或武汉设立分公司（也可以在两个城市都设立分公司）以增加市场份额，同时管理层也在考虑建一个配送中心（也可以不建配送中心），但配送中心的地点限制在新设立分公司的城市。经过计算，每种选择可使公司获得的利润和所需资金如表5-6所示。总预算不得超过1000万元。目标是在满足以上约束的条件下使总利润最大。利润所需资金在长春设立分公司800600在武汉设立分公司500300在长春建配送中心600500在武汉建配送中心4002005.5显性0-1变量的整数规划【解】（1）决策变量本问题的决策变量是“是非决策”的（显性）0-1变量，每个决策只有两种选择--“是”或者“否”，“1”表示对于这个决策选择“是”，“0”表示对于这个决策选择“否”。是非决策问题决策变量可能取值在长春设立分公司？x10或1在武汉设立分公司？x20或1在长春建配送中心？x30或1在武汉建配送中心？x40或15.5显性0-1变量的整数规划（2）目标函数总利润最大。（3）约束条件①总预算约束②公司最多只建一个新配送中心（互斥）③公司只在新设立分公司的城市建配送中心（相依）④0－1变量5.5显性0-1变量的整数规划例5-5的电子表格模型5.5显性0-1变量的整数规划由于可用资金没有用完（只用了可用资金1000万元中的900万元），并且没有建配送中心，所以可以对可用资金进行敏感性分析。可用资金（万元）实际使用（万元）是否建配送中心是否设立分公司总利润

（万元）长春武汉长春武汉7005000101900800500010190090090000111300100090000111300110011000111170012001100011117001300110001111700140014001011190015001400101119005.6隐性0-1变量的整数规划在例5-5中，每个0-1变量表示一个“是非决策”，这些变量也称为0-1决策变量或显性0-1变量。除了这些0-1决策变量，有时还引入其他一些0-1变量以帮助建立模型。隐性0-1变量（也称为辅助0-1变量），是引入模型的附加0-1变量，目的是方便建立纯的或混合的0-1规划模型。介绍隐性0-1变量的5种使用方法，在这些方法中，隐性0-1变量在使问题标准化以便于求解方面发挥了重要作用。固定成本问题产品互斥问题最少产量问题两个约束中选一个约束的问题N个约束中选K个约束的问题5.6.1固定成本问题

在一般情况下，产品的成本由固定成本和可变成本两部分组成。固定成本是指在固定投入要素上的支出，它不受产量影响，例如厂房和设备的租金、贷款利息、管理费用等；可变成本是指在可变投入要素上的支出，它是随着产量变化而变化的成本，例如原材料费用、生产工人的工资、销售佣金等。通常，可变成本和产量成正比，所以可以用下面的表达式来表示某一产品的总成本5.6.1固定成本问题对于有n种产品生产问题的一般模型可以表示如下：引入yi：是否生产第i种产品

转化为：5.6.1固定成本问题例5-6

需要启动资金（固定成本）的例1-1。假设将例1-1的问题做如下变形：变化一：生产新产品（门和窗）各需要一笔启动资金，分别为700元和1300元，门和窗的单位利润还是原来的300元和500元。变化二：一个生产批次在一个星期后即终止，因此门和窗的产量需要取整。5.6.1固定成本问题【解】（1）决策变量由于涉及启动资金（固定成本），本问题的决策变量有两类：第一类是所需要生产的门和窗的数量；第二类是决定是否生产门和窗，这种逻辑关系可用隐性0-1变量来表示。①整数决策变量：设x1、x2分别表示门和窗的每周产量。②隐性0-1变量：设y1、y2分别表示是否生产门和窗（1表示生产，0表示不生产）。（2）目标函数两种新产品的总利润最大5.6.1固定成本问题（3）约束条件

①原有的三个车间每周可用工时限制②变化一，新产品需要启动资金，即产量xi与是否生产yi之间的关系③产量xi非负且为整数（变化二）、是否生产yi为0-1变量5.6.1固定成本问题例5-6的电子表格模型在Excel中，相对极大值M需要数值化，从车间1和车间2的约束中可以看出，x1的最大取值为4，x2的最大取值为6，因此，M的取值只需不小于6即可，这里取99（需要说明的是：为了区别其他数据，相对极大值M一般取9，99，999，9999等）5.6.2产品互斥问题

在实际生产过程中，为了防止产品的过度多元化，有时需要限制产品生产的种类，这就是产品互斥问题。求解产品互斥问题时，采用求解固定成本问题的方法，引入隐性0-1变量：第i种产品是否生产yi。因此，在n种产品中，最多只能生产k种的约束为：以及产量xi与是否生产yi之间的关系：5.6.2产品互斥问题例5-7

包含互斥产品的例1-1。假设将例1-1的问题做如下的变形：两种新产品门和窗具有相同的用户，是互相竞争的。因此，管理层决定不同时生产两种产品，而是只选择其中的一种进行生产。【解】（1）决策变量

本问题的决策变量有两类：第一类是门和窗的每周产量；第二类是门和窗是否生产。①决策变量：设x1、x2分别表示门和窗的每周产量。②隐性0-1变量：设y1、y2分别表示是否生产门和窗（1表示生产，0表示不生产）。5.6.2产品互斥问题（2）目标函数

两种新产品的总利润最大（3）约束条件

①原有的三个车间每周可用工时限制②只能生产一种产品（产品互斥）③产量xi非负、是否生产yi为0-1变量5.6.2产品互斥问题例5-7的电子表格模型5.6.3最少产量问题

在实际生产生活中，经常会碰到最少产量、最少订购量问题。求解最少产量问题时，采用求解固定成本问题的方法，引入隐性0-1变量：第i种产品是否生产yi。因此，对于第i种产品，如果生产，最少生产Si的约束为：以及产量xi与是否生产yi之间的关系为：5.6.3最少产量问题例5-8某公司需要购买5000个灯泡。公司已经收到三家供应商的投标，供应商1提供的灯泡每个3元，一次最少订购2000个，最多3000个；供应商2提供的灯泡每个5元，一次最少订购1000个，多购不限；供应商3可供应3000个以内任意数量的灯泡，每个1元，另加固定费用5000元。公司决定从一家或两家购买。该公司正在考虑采取什么样的订购方案，可以使其所花的总费用最少。【解】（1）决策变量本问题的决策变量有两类：第一类是从各供应商购买灯泡的数量；第二类是是否从各供应商购买灯泡。5.6.3最少产量问题例5-8的混合0-1规划模型5.6.3最少产量问题例5-8的电子表格模型5.6.4从两个约束中选一个约束的问题

管理决策时经常会遇到在两个约束中选一个的问题。举例来说，某个投资方案有两个约束，但只要其中有一个约束成立就可以了，另外一个约束则不做要求。可以把这种问题转化为有0-1变量的混合整数规划问题。这样，需要引入一个0-1变量来决定满足两个约束条件中的哪一个，这样的问题也是隐性0-1变量问题，用y表示：5.6.4从两个约束中选一个约束的问题例5-9

加入二选一约束的例1-1。假设将例1-1的问题做如下变形：工厂最近建了一个与车间3类似的新车间（车间4），因此，新车间也可以参与两种新产品的生产。但是，由于管理上的原因，管理层决定只允许车间3和车间4中的一个车间参与新产品的生产，同时要选取能获得产品组合总利润最大的那个车间。每个产品所需时间每周可用工时（小时）门窗车间1104车间20212车间33218车间42428单位利润（元）3005005.6.4从两个约束中选一个约束的问题【解】

该问题有两种求解方法。方法1：分别建立模型求解（P173--174）。方法2：建立一个模型求解，这时就需要

引入一个隐性0-1变量。（1