单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2.4,线性整数规划,整数线性规划与线性规划有着密不可分的关系，整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下某个线性函数的最优问题，是应用非常广泛的运筹学的重要分支。,2.4.1 线性整数规划模型及其分类,线性规划问题中有一局部问题要求有整数可行解和整数最优解，例如完成任务的人数，生产机器的台数，生产任务的分配，场址的选定等。都必须局部或者全部满足整数要求，这样的问题称为整数线性规划问题，简称为整数规划问题。,整数规划的引入,【,例2.28,】,某商场决定:营业员每周连续工作5天后连续休息2天,轮流休息。根据统计,商场每天需要的营业员如下表所示。,星期,一,二,三,四,五,六,日,需求人数,300,300,350,400,480,600,550,问商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。,11/16/2024,1,2.4,线性整数规划,解：设xjj=1,2,7)为休息2天后星期一到星期日开始上班的营业员，,星期,一,二,三,四,五,六,日,可以上班的人员,x,1,x,4,x,7,x,1,x,2,x,5,x,7,x,1,x,3,x,6,x,7,x,1,x,4,x,7,x,1,x,5,x,2,x,6,x,3,x,7,所以这个问题的线性规划模型为：,由于所有变量都要求取整数，称它为,纯整数规划问题,。,11/16/2024,2,2.4,线性整数规划,【,例2.29,】,有时企业要作投资决策，就是对几个潜在的投资方案作出选择，例如投资决策可以是在可行的几个厂址中作出选择；或设备构置的选择；或对一组研究和发展项目作出决定。在这类决策问题中，问题是在“要”或者“不要”之间进行选择，如果我们令决策变量,x,j,是整数，且只取0或1，分别表示不投资或者投资第,j,个方案，这种取值的变量为0-1变量。假定,c,j,代表第,j,项投资得到的收益，,a,ij,是用于第,j,个方案的消耗第,i,项资源的数量，,b,i,为第,i,种资源的限制，则上述问题所耗费资源约束为 ，企业投资是为了追求利润最大化，其目标函数为 ，这样该问题的规划模型为下式：,由于所有的变量都只能取0或1，这样的整数规划问题称为,0-1规划,。,11/16/2024,3,2.4,线性整数规划,【例2.30】拟在某区域内建立某个商品的配送中心，如以下图所示。有三个可供选择的配送点Aii=1,2,3)，容量为ai，不考虑固定资产投资；该区域的有4个需求点Bjj=1,2,3,4),各需求点的需求量为dj，Ai配送点到Bj需求点的运费为cij，问：如何选择2个配送点，在满足需求的条件下，总费用最小。,B,1,B,2,B,3,B,4,解,：令,y,ij,表示从,A,i,配送点到,B,j,需求点的运量。,所建立模型如下:,：,11/16/2024,4,2.4,线性整数规划,B,1,B,2,B,3,B,4,y,11,y,12,y,14,y,24,y,21,y,22,y,23,y,32,y,33,y,34,在这个问题中，变量xii=1,2,3)只能取0或1，变量yij为不小于零的实数，这样的整数规划问题称为混合整数规划。,11/16/2024,5,2.4,线性整数规划,整数规划的分类,一般整数规划分为二种类型，如果所有的变量都限制为非负整数，就称这类整数规划为纯整数规划，或纯整数规划，如例2.28、例2.29是纯整数规划纯整数规划的一个特殊情况是变量取值仅限于0或1，这一类问题称为0-1整数规划问题，也称为0-1规划，例2.29就是0-1规划。在整数规划中，如果一局部变量要求取整数而另一局部不一定要求取整数，称这一类问题为混合整数规划问题,例2.30就是混合整数规划。,常用求解整数规划的方法有,分枝定界法,和,割平面法,，这两种方法本书不作介绍。对于特别的0-1规划问题的求解，可以采用,匈牙利法,，将在下一章中讨论。如果在应用过程中遇到整数规划的问题，在要求不太严格的情况下，可以求出其相应线性规划解来近似，也可通过专用数学软件来求解。,11/16/2024,6,2.4,线性整数规划,2.4.2 线性整数规划的应用,这里介绍一些整数规划的实际应用，并建立其数学模型。,固定费用问题Fixed Cost Problem,在讨论线性规划时，有些问题是要求使本钱为最小，那时总设固定本钱为常数，并在线性规划的模型中不必明显列出。但有些固定费用固定本钱的问题不能用一般线性规划来描述，但可转换为混合整数规划来解决。,某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高选购自动化程度高的设备，由于产量大，因而分配到每件产品的变动本钱就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动本钱可能增加，所以必须全面考虑。,假设有三种方式可供选择，令xi表示采用第i种方式时的产量；ci表示采用第i种方式时每件产品的变动本钱；ki表示采用第i种方式时的固定本钱。,11/16/2024,7,2.4,线性整数规划,1为了说明本钱的特点，暂不考虑其它约束条件。采用各种生产方式的总本钱分别为,2在构建目标函数时，为了统一在一个问题中讨论，要引入0-1变量，令,于是本钱的目标函数为,3统一xi,yi的关系,当,x,i,0时,y,i,必须为1；当,x,i,=0时,y,i,必须为零,为了统一这两种情况或状态,需引入一个充分大的数,M,表示为,x,i,y,i,M,i,=1,2,3,.,其中,M,是,x,i,取值的上界，可从题中条件得出。,11/16/2024,8,2.4,线性整数规划,【例2.31】某农场有100公顷土地可用于开展生产，农场劳动力供给为4000人日。该农场种植三种作物：大豆、玉米和小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛投资400元，每只鸡投资3元，农场建立鸡舍需花费1000元，牛栏需要花费5000元。养奶牛时每头需拨出1.5公顷土地种饲草，并占用人工70人日，年净收入1000元/每头奶牛；养鸡时不占土地，需人工为每只鸡0.5人日，年净收入为10元/每只鸡；三种作物每年需要的人工及收入情况如下表所示：,大豆,玉米,麦子,需人日数年净收入(元/公顷),50175,75300,40120,试确定该农场的经营方案，使年净收入为最大。,11/16/2024,9,2.4,线性整数规划,解,：如果设,x,1,x,2,x,3,分别表示种植大豆、玉米、小麦的面积，,x,4,x,5,表示饲养奶牛、鸡的数量。考虑到饲养动物需要固定投资，,该问题的线性整数规划模型可表示为：,11/16/2024,10,2.4,线性整数规划,多种类、多方案投资,问题,【例2.32】某校基金会有一笔数额为5000万元的基金,打算将其存入银行。当前银行存款的利率期限结构见下表。取款政策与银行的现行政策相同,定期存款不提前取,活期存款可任意支取。校基金会方案在5年内每年用局部本息奖励优秀师生，要求每年的奖金额大致相同，且在5年末仍保存原基金数额。校基金会希望获得最正确的基金使用方案，以提高每年的奖金额。请你帮助校基金会设计一个基金最正确使用方案，试建立其模型。,存款期限,活期,半年,一年,二年,三年,五年,银行存款税后年利率(%),0.792,1.664,1.800,1.944,2.160,2.304,分析：参照存款年利率数据表可知,定期存款年限越长,存款年利率越大。因此，在不影响奖金发放的情况下,应尽可能存年限较长的定期存款,这样才能获得较高的利息。所以此基金的最正确使用方案是:拿出一局部基金存入一年定期,一年后的本息全部用于发放第一年的奖金,再拿出一局部基金存入二年定期，二年后的本息全部用于发放第二年的奖金,依此类推,且每年发放奖金数额相同,最后一年得到的存入银行款项在发完奖金后仍然为基金总额。,11/16/2024,11,2.4,线性整数规划,假设每年发放奖学金一次，且均在年末发放；利率计算方式为单利；不考虑利息税。,解,：设每年发放的奖金额为,y,，存期为年的基金为,x,i,(,i,=1,2,3,4,5),因为没有4年期的利息，这时存款方案有：先存1年再存3年、存两次2年、先存3年再存1年、先存2个1年再存2年、存4次一年等，通过各种方案的比较,可知存款方案为先存3年与再存1年的组合效益最高。,，该问题的数学模型：,11/16/2024,12,2.4,线性整数规划,运发动选拔问题,【,例2.33,】,篮球队需要选择5名队员组成出场阵容参加比赛。可候选的8名队员的身高和擅长位置见右表。出场阵容应满足以下条件：,队员,身高(米),擅长位置,1,1.92,中锋,2,1.90,中锋,3,1.88,前锋,4,1.86,前锋,5,1.85,前锋,6,1.83,后卫,7,1.80,后卫,8,1.78,后卫,1中锋只能有一个上场；2至少有一名后卫；3如1号和4号上场，那么6号不出场；42号和6号至少保存一个不出场。,问应中选择哪5名队员上场，才能使出场队员平均身高最高？,解,：令,那么建立规划模型如下：,11/16/2024,13,2.4,线性整数规划,11/16/2024,14,2.4,线性整数规划,背包问题,二维背包问题一个旅行者要在背包里装一些最有用的旅行物品。背包容积为a,携带物品总重量最多为b。现在有物品n种，第i种物品的体积为ai，重量为bi(i=1,2,n)。为了比较物品的有用程度，假设第i件物品的有用程度为ci。假设每件物品的只能整件携带，每件物品都能放进背包中，并且不考虑物品放入背包后相互的间隙。问旅行者应携带哪几件物品才能使携带物品的总价值最大？,解：令xi为第i 种物品的装入件数，那么问题的数学模型是,11/16/2024,15,2.4,线性整数规划,【,例2.34,】,有一艘货轮，它的容积为3000吨(,t,)，其最大允许载重量5400立方米(,m,3,)，现有三种大批量的货物待运，已知有关数据如右表所示：,商品,每件体积,(,m,3,/件),每件重量,(,t,/件),每件运价,(元/件),1,10,8,1000,2,5,6,700,3,7,5,600,问该货轮应装载1、2、3各多少件，其运费收入为最大？,解：令xi为第i 种物品的装入件数(i=1,2,3)，那么问题的数学模型是,11/16/2024,16,