《数据、模型与决策》 课件 5整数规划模型

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

某航空公司是一家使用小型飞机经营短途航线的小型区域性企业。该公司已经经营得不错，其管理层决定拓展其经营领域。管理层面临的基本问题是：是采购更多的小型飞机来开辟一些新的短途航线，还是开始通过为一些跨地区航线购买大型的飞机来进军全国市场（或双管齐下）？哪一种战略最有可能获得最高收益？表6-1提供了购买每一种飞机的年净利润期望（包括资本回收成本）；给出了每架飞机的采购成本，以及可用于飞机采购的总可用资金1亿元；并表明了管理层希望小型飞机的采购不超过两架。需要的决策是：小型飞机和大型飞机各需要采购多少才能够获得最大的年总净利润？小型飞机大型飞机可获得的总资金每架飞机年利润100万元500万元1亿元每架飞机采购成本500万元5000万元最多购买数量2没有限制5.1整数规划基本概念、分类与解的特点解：(1)决策变量设小型飞机与大型飞机的购买数量分别为x1、x2(架)。(2)目标函数目标是年总净利润最大。(3)约束条件①资金限制②小型飞机数量限制（最多购买2架）③非负且均为整数5.1整数规划基本概念、分类与解的特点求解：(1)先去掉整数约束，作为一般线性规划问题，用图解法求出的最优解x1＝2，x2＝1.8。如何进行“取、舍”？(2)由于离散问题比连续问题更难以处理，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的基本算法有分支定界法、割平面法等。Excel“规划求解”工具求解整数规划问题采用分支定界法。5.2整数规划电子表格模型用Excel求解整数规划的基本步骤与求解一般线性规划问题相同，只是在约束条件中添加一个“整数”约束。在Excel规划求解的“添加约束”对话框中，用“int”表示整数。因此，只要在该对话框中添加一个约束条件，在左边输入要求取整的决策变量单元格，然后选择“int”。5.2整数规划电子表格模型例5.1的电子表格模型5.30-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”即可。5.30-1整数规划例5.2分公司选址问题。某销售公司打算通过在武汉或长春设立分公司（也可以在两个城市都设分公司）以增加市场份额，管理层同时也在考虑建立一个配送中心（也可以不建配送中心），但配送中心地点限制在新设分公司的城市。经过计算，每种选择使公司收益的净现值和所需费用如表6-2所示。总的预算费用不得超过1000万元。目标是在满足以上约束的条件下使总的净现值最大。净现值（万元）所需资金（万元）在长春设立分公司800600在武汉设立分公司500300在长春建配送中心600500在武汉建配送中心4002005.30-1整数规划解：（1）决策变量本题的决策变量是是非决策的0-1决策变量，每一个决策只有两种选择，是或者否，1表示对于这个决策选择“是”，0表示对于这个决策选择“否”。是非决策问题决策变量可能取值在长春设立分公司？x10或1在武汉设立分公司？x20或1在长春建配送中心？x30或1在武汉建配送中心？x40或15.30-1整数规划(2)目标函数总的净现值最大。(3)约束条件①总预算支出②公司最多只建一个新配送中心（互斥）③公司只在新设分公司的城市建配送中心（相依）④0－1变量5.30-1整数规划例5.2的电子表格模型5.30-1整数规划由于可用资金没有使用完（只使用了可用资金1000万元中的900万元），并且没有建配送中心，所以可以对可用资金进行敏感性分析。可用资金（万元）实际使用（万元）建配送中心?设立分公司?总的净现值

（万元）长春武汉长春武汉7005000101900800500010190090090000111300100090000111300110011000111170012001100011117001300110001111700140014001011190015001400101119005.3.2辅助0-1变量在例5.2中，每个0-1变量表示一个是非决策，这些变量也称为0-1决策变量。除了这些0-1决策变量，有时还引入其他一些0-1变量以帮助建立模型。辅助0-1变量，是引入模型的附加0-1变量，目的是为了方便建立纯的或混合的0-1整数规划模型。下面介绍辅助0-1变量的4种使用方法，在这些方法中，辅助0-1变量在使问题标准化以便于求解方面发挥了重要作用。固定成本问题产品互斥问题两个约束中选一个约束的问题N个约束中选K个约束的问题5.3.2辅助0-1变量固定成本问题在一般情况下，产品的成本是由固定成本和可变成本两部分组成。固定成本是指在固定投入要素上的支出，它不受产量影响，例如厂房和设备的租金、贷款利息、管理费用等；可变成本是指在可变投入要素上的支出，它是随着产量变化而变化的成本，例如原材料费用、生产工人的工资、销售佣金等。通常，变动成本和产量成正比，所以可以用下面的表达式来代表某一产品的总成本5.3.2辅助0-1变量固定成本问题对于有n种产品生产问题的一般模型可以表示如下：引入yi：是否生产第i种产品

转化为：5.3.2辅助0-1变量例5.3

含有启动成本（固定成本）的例1.1(见下页）假设将例1.1的问题作如下变形：

变化一：生产新产品（门和窗）各需要一笔启动成本，分别为700元和1300元，门和窗的单位利润还是原来的300元和500元。

变化二：一个生产批次在一个星期后即终止，因此门和窗的产量需要取整。例1.1

某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂应如何安排这两种新产品的生产计划，可使总利润最大？例题1.1参考版5.3.2辅助0-1变量解：(1)决策变量由于涉及启动成本（固定成本），本问题的决策变量有两类，第一类是所需要生产的门和窗的数量；第二类是决定是否生产门和窗，这种逻辑关系可用辅助0-1变量来表示。① 整数决策变量：设x1、x2分别为门和窗的每周产量。② 辅助0-1变量：设y1、y2分别表示是否生产门和窗，取0时表示不生产，取1时表示生产。(2)目标函数本问题的目标是公司的总利润最大5.3.2辅助0-1变量(3)约束条件①原有的三个车间每周可用工时限制②变化一，新产品需要启动成本，即产量xi与是否生产yi之间的关系③产量xi非负且为整数（变化二）、是否生产yi为0-1变量5.3.2辅助0-1变量例5.3的电子表格模型。在Excel中，相对极大值M需要数值化，从车间1和车间2的约束中可以看出，x1的最大取值为4，x2的最大取值为6，因此，M的取值只需不小于6即可，这里取99（需要说明的是：为了区别其他数据，相对极大值M一般取9，99，999，…）5.3.2辅助0-1变量产品互斥问题在实际生产过程中，为了防止产品的多元化，有时需要限制产品生产的种类，这就是产品互斥问题。处理产品互斥问题时，采用处理固定成本问题的方法，引入辅助0-1变量：第i种产品是否生产yi。因此，在n种产品中，最多只能生产k种的约束为：还有，产量xi与是否生产yi之间的关系：5.3.2辅助0-1变量例5.4

包含互斥产品的例1.1。假设将例1.1的问题作如下的变形：两种新产品门和窗具有相同的用户，是互相竞争的。因此，管理层决定不同时生产两种产品，而是只能选择其中的一种进行生产。解：(1)决策变量本问题的决策变量仍有两类，第一类是门和窗的每周产量；第二类是门和窗是否生产。①决策变量：设x1、x2分别为门和窗的每周产量。②辅助0-1变量：设y1、y2分别表示是否生产门和窗，取0时表示不生产，取1时表示生产。5.3.2辅助0-1变量(2)目标函数本问题的目标是公司的总利润最大。(3)约束条件①原有的三个车间每周可用工时限制②只能生产一种产品（产品互斥）③产量xi非负、是否生产yi为0-1变量5.3.2辅助0-1变量例5.4的电子表格模型5.3.2辅助0-1变量两个约束中选一个约束的问题管理决策时经常会遇到在两个约束中选一个的问题，举例来说，某个投资方案有两个约束，但只要其中有一个成立就可以了，另外一个约束则不做要求。把这种问题转换为有0-1变量的混合整数规划问题，这样，需要引入一个变量，来决定满足两个约束条件中的哪一个，这样的问题也是一个辅助0-1变量问题，用y表示：5.3.2辅助0-1变量例5.5

加入二选一约束的例1.1。假设将例1.1的问题作如下的变形：公司最近建了一个与车间3类似的新车间（车间4），因此，新车间也可以生产两种新产品。但是，由于管理上的原因，管理层决定只在一个车间内生产新产品，同时要选取能获得产品组合总利润最大的那一个车间。车间单位产品的生产时间（小时）每周可获得的生产时间（小时）门窗1104202123321842428单位利润（元）3005005.3.2辅助0-1变量解：该问题有两种解法。解法1：分别建立模型求解（P215）。解法2：建立一个模型求解，这时需要

引入一个辅助0-1变量。(1)决策变量

本问题的决策变量仍有两类，第一类是门和窗的每周产量；第二类是决定是在车间3还是在车间4生产，这种逻辑关系可用辅助0-1变量来表示，值得注意的是，两个车间不能同时生产。①设x1、x2分别为门和窗的每周产量。②辅助0-1变量：设y=0表示选择车间3，y=1表示选择车间4。5.3.2辅助0-1变量(2)目标函数

本问题的目标是公司的总利润最大。(3)约束条件

①车间1和车间2的约束

②选择车间3还是车间4③产量xi非负、选择变量y为0-1变量5.3.2辅助0-1变量例5.5电子表格模型5.3.2辅助0-1变量N个约束中选K个约束的问题有时会遇到在一个规划问题中有N个约束条件，但只要求其中K个约束条件成立，另外N－K个约束条件则可以不要求成立（K

N）。当K＝1，N＝2时，这个问题便等价于前面所讲述的两个约束条件中选一个约束的问题。5.3.2辅助0-1变量N个约束中选K个约束的问题假设N个可能的约束是：引入N个0-1变量yi：

将问题重新描述为5.4整数规划应用举例例5.6

某公司的新产品选择问题。某公司的研发部最近开发出了三种新产品。但是，为了防止生产线的过度多元化，公司管理层增加了如下的约束：约束1：在三种新产品中，最多只能选择两种进行生产。这些产品都可以在两个工厂中生产，但是，为了管理方便，管理层加入第二个约束：约束2：两个工厂中必须选出一个专门生产新产品。两个工厂中各种产品的单位生产成本是相同的，但是，由于生产设备的不同，每单位产品所需要的生产时间是不同的。5.4整数规划应用举例表6-6给出了这方面的相关数据，包括生产出来的产品每周内估计的可销售量。管理层制定的目标是通过选择产品、工厂以及确定各种产品的每周产量，使得总利润最大化。工厂单位产品的生产时间（小时）每周可获得的生产时间（小时）产品1产品2产品3134230246240单位利润（千元）573每周可销售量7595.4整数规划应用举例解：(1)决策变量

本问题是一个混和0-1整数规划模型，所需的决策变量有三类，第一类是三种新产品的每周产量；第二类是决定是否生产这种新产品；第三类是决定选择哪家工厂生产新产品。①决策变量：设xi为新产品i的每周产量（i=1,2,3）②辅助0-1变量：设yi为是否生产新产品i，yi=1表示生产，yi=0表示不生产（i=1,2,3）。③辅助0-1变量：设y=0表示选择工厂1，y=1表示选择工厂2。5.4整数规划应用举例(2)目标函数

本问题的目标是公司的总利润最大。(3)约束条件

①约束1：在三种新产品中，最多只能选择两种进行生产

②约束2：两个工厂中必须选出一个专门生产新产品

③产品的每周产量受每周可销售量限制

④产量xi非负、yi和y为0-1变量5.4整数规划应用举例例5.6的电子表格模型5.4整数规划应用举例例5.7

不符合比例性要求问题。某公司正在为其下一年的新产品制定营销计划，并准备在全国电视网上购买5个广告片，以促销三种产品。每个广告只针对一种产品，因此，这一问题就是如何将5个广告片分配给三种产品，每种产品最多可以有三个广告，最少可以不作广告。表6-7表示的是在每种产品上分配0、1、2、3个广告所产生的利润。问题的目标是如何将5个广告分配给三种产品，从而能获得最大的总利润。电视广告片数利润（百万元）产品1产品2产品30000110-1232233345.4整数规划应用举例解：(1)决策变量

问题的目标是将5个广告片分配给三种产品，从而能获得最大的总利润。因此，按照以往的经验，一般会假设分配给三种产品的电视广告片数分别为x1、x2、x3，但由于其利润不是电视广告片数的线性函数，所以可以根据利润情况（为的是将非线性转化为线性），将该问题视为纯0-1规划模型，并设决策变量为0-1变量：

设xij为是否将电视广告片数i分配给产品j（0－不分配，1－分配）（i,j=1,2,3）。

这类似指派问题：每种产品最多分配一次电视广告片数（0片～3片）。5.4整数规划应用举例(2)目标函数本问题的目标是将5个广告片分配给三种产品获得的总利润最大(3)约束条件①每种产品最多分配一次电视广告片数（0片～3片）②广告片数限制③0-1变量5.4整数规划应用举例例5.7的电子表格模型5.4整数规划应用举例例5.8

某速递公司的路线选择问题。某速递公司提供快递服务，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该地区的几辆卡车。因为快递行业的竞争加剧，为了减少平均的送货时间，必须将各包裹根据目的地的地理位置加以分类，并分装到不同的卡车上。假设每天有三辆卡车提供快递服务，卡车可行的路线有10条，如表6-8所示（其中各列的数字表示送货的先后次序）。公司有特制软件，该软件第一步就是根据当天要送快递的地点，找出各卡车可能的路线。假设当天有9个快件需要送到9个地点，请根据各种可能的路线以及所需时间的估计值，建立相应的0-1整数规划模型，为每辆卡车选出一条路线，以最短的总时间完成各地的送货工作。5.4整数规划应用举例表6-8某速递公司的路线选择的相关数据快递地点可行的路线12345678910A11