ecel建模整数规划

Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,第,6,章 整数规划,RUC, School of Information ,Ye Xiang,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,ecel建模整数规划,本章内容要点,整数规划的根本概念,整数规划问题的建模与应用,本章节内容,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提供了购置每一种飞机的年净利润期望包括资本回收本钱；给出了每架飞机的采购本钱，以与可用于飞机采购的总可用资金1亿元；并说明了管理层希望小飞机的采购不超过两架。,需要的决策是：小型飞机和大型飞机各需要采购多少才能够获得最大的年总净利润？,小型飞机,大型飞机,可获得的总资金,每架飞机年利润,100,万元,500,万元,1,亿元,每架飞机采购成本,500,万元,5000,万元,最多购买数量,2,没有限制,6.1 整数规划根本概念、分类与解的特点,解：,(1)决策变量,设小型飞机与大型飞机的购置数量分别为x1、x2(架)。,(2)目标函数,目标是年总净利润最大。,(3) 约束条件, 资金限制, 小型飞机数量限制最多购置2架, 非负且均为整数,6.1 整数规划根本概念、分类与解的特点,求解：,(1)先去掉整数约束，作为一般线性规划问题，用图解法求出的最优解x12，x2。,如何进展“取、舍？,(2)由于离散问题比连续问题更难以处理，整数规划要比一般线性规划难解得多，而且至今尚无一种像求解线性规划那样较成熟的算法。目前常用的根本算法有分支定界法、割平面法等。,Excel“规划求解工具求解整数规划问题采用分支定界法。,6.2 整数规划电子表格模型,用Excel求解整数规划的根本步骤与求解一般线性规划问题一样，只是在约束条件中添加一个“整数约束。在Excel规划求解的“添加约束对话框中，用“int表示整数。因此，只要在该对话框中添加一个约束条件，在左边输入要求取整的决策变量的单元格地址，然后选择“int。,6.2 整数规划电子表格模型,例的电子表格模型,6.3 0-1整数规划,0-1整数规划BIP是整数规划的特殊情况，也是应用最广泛的一类整数规划。在0-1整数规划中，其整数变量只能取0或1，通常用这些01变量表示某种逻辑关系。例如用“1表示“是，用“0表示“非。,0-1整数规划模型的建立和求解方法与一般线性规划模型一样，只是增加了一个“决策变量必须为0或1的约束条件。为反映这一约束条件，在求解时应在Excel规划求解的“添加约束对话框中添加关于决策变量取值为1或0的约束条件。“添加约束对话框中，用“binBinary表示0和1两者取一。因此，只要在约束条件左边输入要求取0或1的决策变量的单元格地址，然后选择“bin即可。,6.3 0-1整数规划,例6.2 分公司选址问题。某销售公司打算通过在武汉或长春设立分公司也可以在两个城市都设分公司以增加市场份额，管理层同时也在考虑建立一个配送中心也可以不建配送中心，但配送中心地点限制在新设分公司的城市。,经过计算，每种选择使公司收益的净现值和所需费用如表6-2所示。总的预算费用不得超过1000万元。目标是在满足以上约束的条件下使总的净现值最大。,净现值（万元）,所需资金（万元）,在长春设立分公司,800,600,在武汉设立分公司,500,300,在长春建配送中心,600,500,在武汉建配送中心,400,200,6.3 0-1整数规划,解：,1决策变量,此题的决策变量是是非决策的0-1决策变量，每一个决策只有两种选择，是或者否，1表示对于这个决策选择“是，0表示对于这个决策选择“否 。,是非决策问题,决策变量,可能取值,在长春设立分公司？,x,1,0,或,1,在武汉设立分公司？,x,2,0,或,1,在长春建配送中心？,x,3,0,或,1,在武汉建配送中心？,x,4,0,或,1,6.3 0-1整数规划,(2)目标函数,总的净现值最大。,(3) 约束条件, 总预算支出, 公司最多只建一个新配送中心互斥, 公司只在新设分公司的城市建配送中心相依, 01变量,6.3 0-1整数规划,6.3 0-1整数规划,由于可用资金没有使用完只使用了可用资金1000万元中的900万元，并且没有建配送中心，所以可以对可用资金进展敏感性分析。,可用资金,（万元）,实际使用,（万元）,建配送中心,?,设立分公司,?,总的净现值（万元）,长春,武汉,长春,武汉,700,500,0,1,0,1,900,800,500,0,1,0,1,900,900,900,0,0,1,1,1300,1000,900,0,0,1,1,1300,1100,1100,0,1,1,1,1700,1200,1100,0,1,1,1,1700,1300,1100,0,1,1,1,1700,1400,1400,1,0,1,1,1900,1500,1400,1,0,1,1,1900,6.3.2 辅助0-1变量,在例中，每个0-1变量表示一个是非决策，这些变量也称为0-1决策变量。除了这些0-1决策变量，有时还引入其他一些0-1变量以帮助建立模型。辅助0-1变量，是引入模型的附加0-1变量，不代表一个是非决策，仅仅是为了方便建立纯的或混合的0-1整数规划模型。,下面介绍辅助0-1变量的4种使用方法，在这些方法中，辅助0-1变量在使问题标准化以便于求解方面发挥了重要作用。,固定本钱问题、产品互斥问题、两个约束中选一个约束的问题、N个约束中选K个约束的问题,6.3.2 辅助0-1变量,固定本钱问题,在一般情况下，产品的本钱是由固定本钱和可变本钱两局部组成。固定本钱是指在固定投入要素上的支出，它不受产量影响，例如厂房和设备的租金、贷款利息、管理费用等；可变本钱是指在可变投入要素上的支出，它是随着产量变化而变化的本钱，例如原材料费用、生产工人的工资、销售佣金等。,通常，变动本钱和产量成正比，所以可以用下面的表达式来代表某一产品的总本钱,6.3.2 辅助0-1变量,固定本钱问题,对于有n种产品生产问题的一般模型可以表示如下：,引入yi：是否生产第i种产品,转化为：,6.3.2 辅助0-1变量,例 含有启动本钱固定本钱的例。假设将例的问题作如下变形：,变化一：生产新产品门和窗各需要一笔启动本钱，分别为700元和1300元，门和窗的单位利润还是原来的300元和500元。,变化二：一个生产批次在一个星期后即终止，因此门和窗的产量需要取整。,6.3.2 辅助0-1变量,解：(1) 决策变量,由于涉与启动本钱固定本钱，本问题的决策变量有两类，第一类是所需要生产的门和窗的数量；第二类是决定是否生产门和窗，这种逻辑关系可用辅助0-1变量来表示。,整数决策变量：设x1、x2分别为门和窗的每周产量。,辅助0-1变量：设y1、y2分别表示是否生产门和窗，取0值时表示不生产，取1值时表示生产。,(2) 目标函数,本问题的目标是公司的总利润最大：,6.3.2 辅助0-1变量,(3) 约束条件,原有的三个车间每周可用工时限制, 变化一，新产品需要启动本钱，即产量xi与是否生产yi之间的关系, 产量xi非负且为整数变化二、是否生产yi为0-1变量,6.3.2 辅助0-1变量,例6.3的电子表格模型。在Excel中，相对极大值M需要数值化，从车间1和车间2的约束中可以看出，x1的最大取值为4，x2的最大取值为6，因此，M的取值只需不小于6即可，这里取99需要说明的是：为了区别其他数据，相对极大值M一般取9，99，999，,6.3.2 辅助0-1变量,产品互斥问题,在实际生产过程中，为了防止产品的多元化，有时需要限制产品生产的种类，这就是产品互斥问题。,处理产品互斥问题时，采用处理固定本钱问题的方法，引入辅助0-1变量：第i种产品是否生产yi。,因此，在n种产品中，最多只能生产k种的约束为：,还有，产量xi与是否生产yi之间的关系：,6.3.2 辅助0-1变量,例 包含互斥产品的例。假设将例的问题作如下的变形：两种新产品门和窗具有一样的用户，是互相竞争的。因此，管理层决定不同时生产两种产品，而是只能选择其中的一种进展生产。,解：(1) 决策变量,本问题的决策变量仍有两类，第一类是门和窗的每周产量；第二类是门和窗是否生产。, 决策变量：设x1、x2分别为门和窗的每周产量。, 辅助0-1变量：设y1、y2分别表示是否生产门和窗，取0值时表示不生产，取1值时表示生产。,6.3.2 辅助0-1变量,(2) 目标函数,本问题的目标是公司的总利润最大。,(3) 约束条件,原有的三个车间每周可用工时限制,只能生产一种产品产品互斥,产量xi非负、是否生产yi为0-1变量,6.3.2 辅助0-1变量,6.3.2 辅助0-1变量,两个约束中选一个约束的问题,管理决策时经常会遇到在两个约束中选一个的问题，举例来说，某个投资方案有两个约束，但只要其中有一个成立就可以了，另外一个约束那么不做要求。,把这种问题转换为有0-1变量的混合整数规划问题，这样，需要引入一个变量，来决定满足两个约束条件中的哪一个，这样的问题也是一个辅助0-1变量问题，用y表示：,6.3.2 辅助0-1变量,例 参加二选一约束的例。假设将例的问题作如下的变形：公司最近建了一个与车间3类似的新车间车间4，因此，新车间也可以生产两种新产品。但是，由于管理上的原因，管理层决定只在一个车间内生产新产品，同时要选取能获得产品组合利润最大的那一个车间。,车间,单位产品的生产时间（小时）,每周可获得的生产时间（小时）,门,窗,1,1,0,4,2,0,2,12,3,3,2,18,4,2,4,28,单位利润（元）,300,500,6.3.2 辅助0-1变量,解：,该问题有,两种,解法。,解法1：分别建立模型求解P215。,解法2：,建立一个模型求解，这时需要,引入一个辅助0-1变量,。,(1) 决策变量,本问题的决策变量仍有两类，第一类是门和窗的每周产量；第二类是决定是在车间3还是在车间4生产，这种逻辑关系可用辅助0-1变量来表示，值得注意的是，两个车间不能同时生产。, 设,x,1,、,x,2,分别为门和窗的每周产量。, 辅助0-1变量：设,y,=0,表示选择车间,3,，,y,=1,表示选择车间,4,。,6.3.2 辅助0-1变量,(2) 目标函数,本问题的目标是公司的总利润最大。,(3) 约束条件,车间1和车间2的约束,选择车间3还是车间4,产量,x,i,非负、选择变量,y,为,0-1,变量,6.3.2 辅助0-1变量,6.3.2 辅助0-1变量,N个约束中选K个约束的问题,有时会遇到在一个规划问题中有N个约束条件，但只要求其中K个约束条件成立，另外NK个约束条件那么可以不要求成立KN。当K1，N2时，这个问题便等价于前面所讲述的两个约束条件中选一个约束的问题。,6.3.2 辅助0-1变量,N个约束中选K个约束的问题,假设N个可能的约束是：,引入N个0-1变量,y,i,：,将问题重新描述为,6.4 整数规划应用举例,例 某公司的新产品选择问题。某公司的研发部最近开发出了三种新产品。但是，为了防止生产线的过度多元化，公司管理层增加了如下的约束：,约束1：在三种新产品中，最多只能选择两种进展生产。,这些产品都可以在两个工厂中生产，但是，为了管理方便，管理层参加第二个约束：,约束2：两个工厂中必须选出一个专门生产新产品。,两个工厂中各种产品的单位生产本钱是一样的，但是，由于生产设备的不同，每单位产品所需要的生产时间是不同的。,6.4 整数规划应用举例,表,6-6,给出了这方面的相关数据，包括生产出来的产品每周内估计的可销售量。管理层制定的目标是通过选择产品、工厂以,与,确定各种产品的每周产量，使得总利润最大化。,工厂,单位产品的生产时间（小时）,每周可获得的,生产时间（小时）,产品,1,产品,2,产品,3,1,3,4,2,30,2,4,6,2,40,单位利润（千元）,5,7,3,每周可销售量,7,5,9,6.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。,6.4 整数规划应用举例,(2) 目标函数,本问题的目标是公司的总利润最大。,(3) 约束条件,约束1：在三种新产品中，最多只能选择两种进展生产,约束2：两个工厂中必须选出一个专门生产新产品,产品的每周产量受每周可销售量限制,产量xi非负、yi和y为0-1变量,6.4 整数规划应用举例,6.4 整数规划应用举例,不符合比例性要求问题。某公司正在为其下一年的新产品制定营销方案，并准备在全国电视网上购置5个广告片，以促销三种产品。每个广告只针对一种产品，因此，这一问题就是如何将5个广告片分配给三种产品，每种产品最多可以有三个广告，最少可以不作广告。表6-7表示的是在每种产品上分配0、1、2、3个广告所产生的利润。问题的目标是如何将5个广告分配给三种产品，从而能获得最大的利润。,电视广告片数,利润（百万元）,产品,1,产品,2,产品,3,0,0,0,0,1,1,0,-1,2,3,2,2,3,3,3,4,6.4 整数规划应用举例,解：(1)决策变量,问题的目标是将5个广告分配给三种产品，从而能获得最大的利润。因此，按照以往的经历，一般会假设分配给三种产品的电视广告片数分别为x1、x2、x3，但由于其利润不是电视广告片数的线性函数，所以可以根据利润情况为的是将非线性转化为线性，将该问题视为纯0-1规划模型，并设决策变量为0-1变量：,设xij为是否将电视广告片数i分配给产品j0不分配，1分配i,j=1,2,3。,这类似指派问题：每种产品最多分配一种电视广告片数0片3片。,6.4 整数规划应用举例,(2)目标函数,本问题的目标是将5个广告数分配给三种产品获得的利润最大。,(3) 约束条件,每种产品最多分配一种电视广告片数0片3片,广告片数限制,0-1变量,6.4 整数规划应用举例,6.4 整数规划应用举例,例6.8 某速递公司的路线选择问题。某速递公司提供快递效劳，所有快件两天内都能送到。快件在晚上到达各收集中心，并于第二天早上装上送往该地区的几辆卡车。因为快递行业的竞争加剧，为了减少平均的送货时间，必须将各包裹根据目的地的地理位置加以分类，并分装到不同的卡车上。假设每天有三辆卡车提供快递效劳，卡车可行的路线有10条，如表6-8所示其中各列的数字表示送货的先后次序。公司有特制软件，该软件第一步就是根据当天要送快递的地点，找出各卡车可能的路线。假设当天有9个快件需要送到9个地点，请根据各种可能的路线以与所需时间的估计值，建立相应的0-1整数规划模型，为每辆卡车选出一条路线，以最短的总时间完成各地的送货工作。,6.4 整数规划应用举例,表6-8 某速递公司的路线选择的相关数据,快递地点,可行的路线,1,2,3,4,5,6,7,8,9,10,A,1,1,1,B,2,1,2,2,2,C,3,3,3,3,D,2,1,1,E,2,2,3,F,1,2,G,3,1,2,3,H,1,3,1,I,3,4,2,时间,(,小时,),6,4,7,5,4,6,5,3,7,6,6.4 整数规划应用举例,解：,(1) 决策变量,该问题可视为纯0-1整数规划模型，决策变量为0-1变量。设xi为是否选择路线i0表示不选择，1表示选择,(2) 目标函数,本问题的目标是选择可行的路线使所需要的总时间最短。,(3) 约束条件,到达每个快递地点：每个快递地点至少有1辆卡车经过,只有三辆卡车,0-1变量,6.4 整数规划应用举例,例6.8 的0-1整数规划模型,6.4 整数规划应用举例,补充：,整数规划应用举例,补充1：特塞格公司的选址问题。,补充2：例6.8的应用(覆盖问题)。,建消防站:从多个备选消防站中选取，最多只需建立几个消防站即可。,建连锁店:各小区都有时机建见后面的举例,选修课见后面的举例,开设医疗门诊所见后面的举例,补充,1,：特塞格公司的选址问题,特塞格公司是一家设在美国外乡的大型一体化石油公司。这家公司大局部的石油在公司自己的油田中生产，所需的其他局部从中东地区进口。公司拥有大型配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。,油田：提供原油,(,百万桶,),德克萨斯,80,加利福尼亚,60,阿拉斯加,100,中东地区,120,炼油厂：生产石油产品,新奥尔良,100,查尔斯顿,60,西雅图,80,新的炼油厂,120,配送中心：,匹兹堡,100,亚特兰大,80,堪萨斯城,80,旧金山,100,备选炼油厂地址：,洛杉矶,加尔维斯敦,圣路易斯,补充1： 特塞格公司的选址问题 续,特塞格公司正在持续增加其几种主要产品的市场占有率。因此管理层决定建一个新的炼油厂来增加公司的产量，同时增加从中东地区进口石油的数量。接下来所要作出的决策就是确定在什么地方建立新的炼油厂。,新炼油厂的参加对整个配送系统都将产生巨大的影响，其中包括要确定从每一个出发地运送到炼油厂的原油数量，以与从每一个炼油厂运送石油制品到每一个配送中心的数量。因此，影响管理者选择新炼油厂建立地点的三个关键因素是：,从出发地运送原油到所有炼油厂包括新炼油厂的本钱,从所有炼油厂包括新炼油厂运送石油制品到每一个配送中心的本钱,新炼油厂的运作本钱，包括劳动力本钱、赋税、原料不包括原油本钱、能源本钱、保险本钱等资金本钱并不是一个所要关注的因素，因为任何地点的资金本钱几乎都是一样的。,特塞格选址问题 解决方案,收集估计数据,三个油田的产量，所有炼油厂包括新炼油厂的需求量生产能力，不够的原油从中东进口，四个配送中心的需求量见前面,从四个油田出发地：3个自己中东地区到所有炼油厂包括新炼油厂的单位运输本钱见下面,从所有炼油厂包括新炼油厂到每一个配送中心的单位运输本钱见下面,新炼油厂的运营本钱,地点,每年的运营成本（百万美元）,洛杉矶,620,加尔维斯敦,570,圣路易斯,530,特塞格选址问题 解决方案续,原油的单位运输本钱百万美元/百万桶,油田,炼油厂,新奥尔良,查尔斯顿,西雅图,洛杉矶,加尔维斯敦,圣路易斯,德克萨斯,2,4,5,3,1,1,加利福尼亚,5,5,3,1,3,4,阿拉斯加,5,7,3,4,5,7,中东地区,2,3,5,4,3,4,特塞格选址问题 解决方案续,石油制品的单位运输本钱百万美元/百万桶,炼油厂,配送中心,匹兹堡,亚特兰大,堪萨斯城,旧金山,新奥尔良,6.5,5.5,6,8,查尔斯顿,7,5,4,7,西雅图,7,8,4,3,洛杉矶,8,6,3,2,加尔维斯敦,5,4,3,6,圣路易斯,4,3,1,5,特塞格选址问题 解决方案续,方法1：将备选新炼油厂每次一个增加到整个配送系统，并计算平衡运输问题：,每一个新炼油厂建立地点选择带来的原油总运输本钱,每一个新炼油厂建立地点选择带来的石油制品总运输本钱,方法2：使用0-1变量方法。,地点,运输原油的总成本（百万美元）,运输石油制品,的总成本,（十亿美元）,新炼油厂,的运营成本,(,百万美元,),总变动成本,(,十亿美元,),洛杉机,880,1.57,620,3.07,加尔维斯敦,920,1.63,570,3.12,圣路易斯,960,1.43,530,2.92,特塞格选址问题结论,特塞格炼油厂每一个备选厂址所带来的年变动本钱,最终选择了在,圣路易斯建造新的炼油厂,特塞格选址问题：思考题,如果要求最终选择的圣路易斯新炼油厂的生产能力不是原来方案的每年加工亿桶，而是以后市场需求的每年加工亿桶。此时有三种解决方案：,将亿桶原油从产油地运往炼油厂包括圣路易斯新建的炼油厂，每家炼油厂收到的原油数在不超过其生产能力的根底上，使运输本钱最小化。以此时每家炼油厂收到的原油数为根底，寻找将产成品从炼油厂运往配送中心的最优运输方案；,与1的顺序相反，先求产成品从炼油厂运往配送中心的最优运输方案，然后以此为根底炼油厂的实际供给量，再求将亿桶原油从产油地运往炼油厂包括圣路易斯新建的炼油厂的最优运输方案；,合并运输原油和运输石油制品这两张运输问题表为一张表，同时使两种产品的运输方案到达最优总运输本钱最小化 提示：增加约束各炼油厂收到的原油数量与运送出去的石油制品数量相等。,补充,2,：建连锁店,便民超市准备在城市西北郊新建的居民小区中开设如干个连锁店。为方便购物，规划任一居民小区至其中一个连锁店的距离不超过,800m,。右表给出了新建的居民小区,与,离该居民小区半径,800m,内的各小区，问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内。,答案：建,3,个连锁店，但有多种方案：,GHJ,、,BGJ,、,EHJ,小区,该小区,800m,半径,内各小区,A,ACEGHI,B,BHI,C,ACGHI,D,DJ,E,AEG,F,FJK,G,ACEG,H,ABCHI,I,ABCHI,J,DFJKL,K,FJKL,L,JKL,补充,2,：选修课,某大学运筹学专业硕士生要求课程方案中必须选修两门数学类、两门运筹学类、两门计算机类课程。,课程中有些只归属某一类，如微积分归属数学类，计算机程序归属计算机类；,但有些课程是跨类的，如运筹学归属运筹学类和数学类，数据构造归属计算机类和数学类，管理统计归属数学类和运筹学类，计算机模拟归属计算机类和运筹学类，预测归属运筹学类和数学类，凡归属两类的课程选学后可认为两类中各学了一门。,此外，有些课程要求先学习先修课，如学计算机模拟或数据构造必须先修计算机程序，学管理统计必须先修微积分，学预测必须先修管理统计。,问一个硕士生最少应学几门与哪几门，才能满足上述要求。,提示：对7门可选课设0-1变量。答案：选修4门课。,补充,2,：开设医疗门诊所,以下图给出了7个居民小区，它们的邻接关系与每个小区内的居民人数。限于各方面条件限制，目前暂时只能在其中2个小区开设医疗门诊所，且每个门诊所只效劳相邻的两个小区如在A开设门诊所，可效劳于A和B或A和C。问应在哪两个小区开设门诊所，及分别为哪些小区效劳，使其覆盖的居民人数最多。,答案：在G开设门诊所，并效劳于G和D；在E开设门诊所，并效劳于E和B。总效劳人数为17700人。,A,（,3400,）,C,（,4200,）,B,（,2900,）,D,（,2100,）,G,（,7100,）,F,（,1800,）,E,（,5600,）,提示：列出每种情况在哪个小区开设门诊所，并效劳于相邻的哪个小区，并设0-1变量，约束条件要包括每个小区最多覆盖一次。,上机,实验六 整数规划,实验目的：用Excel软件求解整数规划纯整数、混合整数、0-1规划。,二内容和要求：求解习题、 、 、案例7 选作题：习题6.11 、 。,三操作步骤：,1建立电子表格模型；,2使用Excel规划求解功能求解整数规划、0-1规划问题；,3结果分析；,4在Excel或Word文档中写实验报告，包括整数规划或0-1规划模型手写、电子表格模型和结果分析等。,谢谢大家！,结 语,62,Thank You !,不尽之处，恳请指正！,