第四章-整数规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 整数规划,数据、模型与决策,(,第二版,),*,第四章 整数规划,第四章 整数规划,数据、模型与决策,(,第二版,),学习目的,整数规划是最近二十年多来发展起来的规划论中的一个分支。,本章的学习应着重于整数线性规划的概念、整数线性规划模型分类、如何建立整数规划模型、整数规划的求解,图解法、分枝定界法，以及,0-1,整数规划的求解方法。,第四章 整数规划,数据、模型与决策,(,第二版,),第四章 整数规划,4.1,整数规划概述,4.2,整数规划的图解法,4.3,分枝定界法,4.4,0-1,整数规划,第四章 整数规划,数据、模型与决策,(,第二版,),4.1,整数规划概述,4.1.1,整数线形规划的概念,4.1.2,整数线形规划模型分类,4.1.3,建立整数规划模型,第四章 整数规划,数据、模型与决策,(,第二版,),4.1.1,整数线形规划的概念,整数规划：是一类要求设计变量取整数值的数学规划。,整数线性规划的可行解集是相应的线性规划的可行解集的一个子集。,第四章 整数规划,数据、模型与决策,(,第二版,),实例分析：,航空公司是一家地区性公司，从事小型飞机的短途运输。公司运营状况良好，目前正考虑扩展业务。,公司管理层面临的主要问题是要在两种决策中作出选择：是购买小型飞机增加短途航班，在原有市场中进一步发展；还是购买一个大型机提供跨省市航班，从而将市场扩大到整个国家；或者是采取两种措施。许多因素都影响着管理层的最终决策，但其中最重要的一点是其中哪种措施会带来最大的利润。,表的第一行表示的是各种型号飞机估计的年利润（包括资金回收成本）。第二行表示的是各种飞机的单位购买成本以及可用于购买飞机的总资金亿美元。第三行表明管理层购买小型飞机不会多于两架，因为他们认为可获利的短途航线是有限的，不需要在短途航线上增加更多的飞机，而大型飞机的购买量还没有确定。,公司要作出决策，为了获取最大的利润，公司应该购买多少架飞机？而各种型号飞机的用油该如何组合呢？,第四章 整数规划,数据、模型与决策,(,第二版,),项目,小型飞机,大型飞机,可得资金总额,每架飞机年利润（万美元）,100,500,1,亿美元,飞机的单位购价（万美元）,500,5000,最多购买数量,2,-,第四章 整数规划,数据、模型与决策,(,第二版,),4.1.2,整数线形规划模型分类,纯整数线性规划,所有决策变量必须取整数值的整数线性规划，也称为全整数线性规划。,混合整数线性规划,决策变量中的一部分必须取整数值，而其他的可以不取整数值的整数线性规划。,型整数线性规划,决策变量只能取或的整数线性规划。,第四章 整数规划,数据、模型与决策,(,第二版,),4.1.3,建立整数规划模型,实例分析：,一家电子厂生产两种产品和，需经过三道工序加工：，。单件加工利润以及各工时每周限额如表所示。应该如何安排生产才能取得最大利润？,第四章 整数规划,数据、模型与决策,(,第二版,),项目,工序,B1,工序,B2,工序,B3,利润（元,/,件）,产品 （件）,0.4,0.4,0.3,30,产品 （件）,0.5,0.3,0.2,28,工时限额（小时,/,周）,200,180,120,-,解题过程：,因为待生产的产品数量是整数，所以这是一个整数线性规划问题。,设每周生产 产品 件，产品 件。,目标函数：,max z,30,28,约束条件：,0.4,0.5,200,0.4,0.3,180,0.3,0.2,200,，且必须为整数,第四章 整数规划,数据、模型与决策,(,第二版,),某宾馆服务部门各时段（每小时为一时段）需要的服务人员人数如表所示。按照规定，服务员连续工作个小时也就是三个时段为一班，现在要根据此表安排服务员工作时间，使该部门的服务员数量最少。,时段,1,2,3,4,5,6,7,8,服务员最少数量（人）,9,8,10,12,7,5,6,3,第四章 整数规划,数据、模型与决策,(,第二版,),这是一个纯整数线性规划问题。假设在第时段上班的服务员人数为，由于第时段开始上班的服务员人数将在第（）时段结束时下班，所以不需要设置个决策变量将各个时段的服务员人数全部表示出来，只需要个决策变量：，和，建立该问题的整数线性规划模型如下。,目标函数：,min z,约束条件：,非负整数约束,，且均为整数。,第四章 整数规划,数据、模型与决策,(,第二版,),某公司准备有总额为的投资资金，可供选择的投资项目有个，项目所需投资额和预期收益分别为和（，,，），此外，由于种种原因，投资项目有三个附加条件：若是选择项目，就必须同时选择项目。项目和项目至少选择一个。项目，中必须选择两个。现在应该如何选择投资项目？,第四章 整数规划,数据、模型与决策,(,第二版,),解题过程为：由于每一个项目都有被选择和不被选择两种可能性，因此这个问题可以看成一个规划问题，决策变量设为 ，如果对项目投资，那么 ，否则为。,第四章 整数规划,数据、模型与决策,(,第二版,),第四章 整数规划,4.1,整数规划概述,4.2,整数规划的图解法,4.3,分枝定界法,4.4,0-1,整数规划,第四章 整数规划,数据、模型与决策,(,第二版,),4.2,整数规划的图解法,当整数规划问题中只含有两个决策变量时，可以先做出松弛问题的可行域，确定目标函数的斜率，然后以该斜率在可行域内平移直线，增大目标函数值。,但是与线性规划不同的一点是，直线平移到可行域内的最后一个整数解即停下来，而不是平移到可行域的边缘。最后平移到的整数解即为最优整数解。,第四章 整数规划,数据、模型与决策,(,第二版,),第四章 整数规划,4.1,整数规划概述,4.2,整数规划的图解法,4.3,分枝定界法,4.4,0-1,整数规划,第四章 整数规划,数据、模型与决策,(,第二版,),4.3,分枝定界法,4.3.1,分枝定界法简介,4.3.2,分枝定界法的解题过程,第四章 整数规划,数据、模型与决策,(,第二版,),4.3.1,分枝定界法简介,分枝定界法可以用于解决整数规划问题。,在世纪年代初，这种方法由,Land,和,Doig,提出，后经过,Dakin,修正而成。,由于这种方法灵活且便于计算机求解，所以现在它已成为求解整数规划的重要方法。,这种方法将问题的所有解分类归入不同的解集，然后逐一考察每一个解集，判断它是否包含最优解在内，或者它是否可以被忽略。,第四章 整数规划,数据、模型与决策,(,第二版,),4.3.2,分枝定界法的解题过程,分枝定界法的具体做法是：首先不考虑变量的整数要求，求解相应的线性规划问题；考察所求得的最优解，如果不符合整数要求，则把原问题分为两部分，每一部分增加新的约束条件，以减小原线性规划问题的最优解，直到最后求得整数最优解。,在这个过程中，包括分枝和定界两个关键步骤。,第四章 整数规划,数据、模型与决策,(,第二版,),实例分析：,问题一：通达公司是一家设备生产公司，今年主要生产两种设备：和。由于这两种设备的材料相同，技术上也相似，对材料和技术人员的需求如表所示。因此要对其生产作出一个计划，以便使利润值达到最大。,项目,材料（单位）,技术人员（人）,利润（元）,设备,A,1,2,3,设备,B,0.5,3,2,总量限制,4.5,14,-,第四章 整数规划,数据、模型与决策,(,第二版,),建立该问题的整数规划模型,目标函数：,max,（）,约束条件：,0.5,4.5,14,，（且为整数）,首先忽略整数约束，将上述问题作为一个一般线性规划问题对待，得到最优解为：,A,3.25,（件），,B,2.5,（件），目标函数是,14.75,元。,第四章 整数规划,数据、模型与决策,(,第二版,),问题二,:,将约束,B,加到模型中去，得到新问题。,目标函数：,maxz,（,A,B,）,约束条件：,A,0.5B,4.5,A,B14,B,AB,用单纯形法求解该模型，得到：最优解为,A,3.5,件，,B,件，目标函数为,14.5,元。,第四章 整数规划,数据、模型与决策,(,第二版,),问题三：将约束条件,B,加到原模型中去。,目标函数：,maxz,（,A,B,）,约束条件：,A,0.5B,4.5,A,B,B,A,，,B,求得这一问题的解为：,A,2.5,件，,B,件，目标函数为,13.5,元。,第四章 整数规划,数据、模型与决策,(,第二版,),问题四：将约束,A,加到问题二中。,目标函数：,maxz,（,A,B,）,约束条件：,A,0.5B,4.5,A,B,B,A,A,，,B,求解这一模型，得到最优解：,A,件，,B,件目标函数为元。,第四章 整数规划,数据、模型与决策,(,第二版,),问题五：将约束,A,，加到问题二中去。,目标函数：,maxz,（,A,B,）,约束条件：,A,0.5B,4.5,A,B,B,A,A,，,B,求解这一模型，得到最优解：,A,件，,B,件，目标函数为元。,第四章 整数规划,数据、模型与决策,(,第二版,),最后求得最优解为,A,，,B,，目标函数为。,松弛问题上界,14.75,下界,13,问题二上界,14.5,下界,13,问题三上界,13.5,下界,13,问题四,A=3B=2Z=13,问题五,A=4B=1Z=14,第四章 整数规划,数据、模型与决策,(,第二版,),利用分枝定界法求解整数规划问题的步骤,:,第一步：求解相应的线性规划问题，并确定目标函数值的上下界。,第二步：分枝和求解。,第三步：修改上下界。,第四步：剪枝与比较。,第四章 整数规划,数据、模型与决策,(,第二版,),第四章 整数规划,4.1,整数规划概述,4.2,整数规划的图解法,4.3,分枝定界法,4.4,0-1,整数规划,第四章 整数规划,数据、模型与决策,(,第二版,),4.4 0-1,整数规划,4.4.1 0-1,整数规划的主要概念,4.4.2,0-1,规划的解题过程,第四章 整数规划,数据、模型与决策,(,第二版,),4.4.1 0-1,整数规划的主要概念,当整数规划的变量皆为,-,变量时，该问题称之为,-,整数规划问题（,Binary,Integer,Programming,，,BIP,）。,所有的决策变量均为变量的整数规划问题，称为纯问题（,Pure,）。,变量的混合也是很普遍的，既有变量，又有如线性规划中的连续变量的问题称为混合问题（）,第四章 整数规划,数据、模型与决策,(,第二版,),4.4.2,0-1,规划的解题过程,实例分析：,公司准备开发几种新产品，该公司的四个项目小组分别都提出了各自的方案，但是由于公司的投资金额有限，不能对所有项目进行投资，必须在其中作出选择。表列出了各个项目对于资金、工作人员以及将会产生的净现值的情况。总的投资额为万元，可以调用的工作人员一共有人。关于投资的项目，还有一个附加条件，即项目和项目由于某些原因不得同时投资。应该如何挑选投资项目？,第四章 整数规划,数据、模型与决策,(,第二版,),项目,需要投资额（万元）,需要工作人员（人）,净现值（万元）,1,650,16,900,2,500,8,700,3,550,7,650,4,400,5,600,第四章 整数规划,数据、模型与决策,(,第二版,),满足约束条件,过滤条件,最优,z,值（万元）,(0,0,0,0),(1),、,(2),、,(3),无,0,(1,0,0,0),(1),、,(2),、,(3),无,900,(1,0,0,1),(1),、,(2),（,3,）,-,(1,0,1,0),(1),、,(3),(2),-,(1,1,0,0),(1),、,(3),(2),-,(0,1,0,1),(1),、,(2),、,(3),无,1300,(0,1,1,0),(1),、,(2),、,(3),无,1300,(0,0,1,1),(1),、,(2),、,(3),无,-,(0,1,1,1),(2),、,(3),(1),-,第四章 整数规划,数据、模型与决策,(,第二版,),