运筹学——.整数规划与分配问题

,第四章 整数规划与分配问题,对于线性规划问题，最优解可能是分数或小数。但是对于某些问题，会要求解答必须是整数（称为,整数解,）。,对于所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等；,对于一些决策变量必须取,Boolean,值时，如要不要在某地建工厂，可选用一个逻辑变量,x,，令,x=0,表示不在该地建厂，,x=1,表示在该地建厂。,这时，分数或小数的解就不合要求，我们称这样的问题为,整数规划。,例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：,货物,体积,米,3,/,箱,重量,百斤,/,箱,利润,百元,/,箱,甲,乙,5,4,2,5,20,10,托运限制,24,13,问两种货物各托运多少箱，可使获得的利润为最大？,能否先不考虑对变量的整数约束，作为一般线性规划来求解，当解为非整数的时候可以用,“,四舍五入,”,或,“,凑整,”,方法寻找最优解？,对于变量取值很大时，用上述方法得到的解与最优解差别不大；但当变量取值较小时，得到的解就可能与实际整数最优解差别很大。,当问题规模较大（决策变量较多）时，用,“,凑整,”,方法来算工作量很大。,例：某线性规划问题最优解为,(,x,1,x,2,)=(4.6,5.5),，用凑整法需要比较与上述数据最接近的几种组合：,(4,5),(4,6),(5,5),(5,6),，共四种组合。若问题中有,10,个整数变量，则解组合达到,2,10,=1024,个整数组合。,且最优解未必在这些组合中。,例：求整数规划问题的最优解,解：,用图解法得最优解为（,3.25,2.5,）,如果不考虑整数约束（称为整数规划问题的,松弛问题,）,最优解为（,4,1,），,z,*,=14,。,凑整法求解：比较四个点（,4,3,）,（,4,2,）,（,3,3,）,（,3,2,），前三个都不是可行解，第四个虽然是可行解，但,z=13,不是最优解。,(4,1),主要内容,一、整数规划的特点及作用,二、分配问题与匈牙利法,三、分枝定界法,四、应用举例,第一节 整数规划的特点及作用,第四章 整数规划及分配问题,一、整数规划的特点及作用,1.1,整数规划的概念,整数规划,(,Integer Programming,),：决策变量要求取整数的线性规划。,如果所有的决策变量、技术系数和右端项都是非负整数，就称为,纯整数规划。,如果所有的决策变量都是非负整数，技术系数和右端项为有理数，称为,全整数规划。,如果仅一部分决策变量为整数，则称为,混合整数规划。,如果变量取值仅限于,0,或,1,，称为,0-1,整数规划,。,一、整数规划的特点及作用,1.2,0-1,整数规划,某公司拟在市东、西、南三区建立门市部。拟议中有,7,个位置（点）,A,i,供选择。规定,在东区，由,A,1,，,A,2,，,A,3,三个点中至多选两个；,在西区，由,A,4,，,A,5,两个点中至少选一个；,在南区，由,A,6,，,A,7,两个点中至少选一个。,如选用,A,i,点，设备投资估计为,b,i,元，每年可获利润估计为,c,i,元，但投资总额不能超过,B,元。,问：应如何,选址,，可使年利润为最大？,一、整数规划的特点及作用,1.2,0-1,整数规划,0-1,整数规划的一般形式,:,0-1,整数规划一般都是纯整数规划。,一、整数规划的特点及作用,1.3,整数规划的作用,0-1,整数规划在管理领域具有重要作用,m,个约束条件中只有,k,个起作用；,约束条件的右端项可能是,r,个值,(,b,1,b,2,b,r,),中的某一个；,两组条件中满足一组；,用以表示含固定费用的函数。,第二节 分配问题与匈牙利法,第四章 整数规划及分配问题,二、分配问题与匈牙利法,2.1,分配问题,(1),指派,n,个人去完成,n,项任务，使完成,n,项任务的总效率最高,(,或所需总时间最少,),，这类问题称为,指派问题或分配问题,。,安排工作（,派工,）：有,n,项加工任务，怎样指派到,n,台机床上完成；,有,n,条航线，怎样指定,n,艘船去航行的；,二、分配问题与匈牙利法,2.1,分配问题,(2),如果完成任务的效率表现为,资源消耗,，考虑的是如何分配任务使得目标函数,极小化,；,如果完成任务的效率表现为,生产效率的高低,，则考虑的是如何分配使得目标函数,最大化,。,在分配问题中，利用不同资源完成不同计划活动的效率，通常用表格形式表示为,效率表,，表格中数字组成,效率矩阵,。,二、分配问题与匈牙利法,2.2,分配问题实例,(1),例：有一份中文说明书，需要译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下，问应指派何人去完成工作，使所需总时间最少,?,人员,任务,甲,乙,丙,丁,译成英文,译成日文,译成德文,译成俄文,2,15,13,4,10,4,14,15,9,14,16,13,7,8,11,9,二、分配问题与匈牙利法,2.2,分配问题实例,(2),效率矩阵,用,a,ij,表示。,a,ij,0(,i,j,=1,2,n),表示指派第,j,人去完成第,i,项任务时的效率,(,时间,、,成本等,),。,人员,任务,甲,乙,丙,丁,译成英文,译成日文,译成德文,译成俄文,2,15,13,4,10,4,14,15,9,14,16,13,7,8,11,9,二、分配问题与匈牙利法,2.2,分配问题实例,(3),某项任务只能由,1,人完成；,某人只能完成,1,项任务。,建立整数规划模型,分配问题是,0-1,整数规划的特例，也是运输问题的特例；,n=m,a,j,=,b,j,=1,。,二、分配问题与匈牙利法,2.3,匈牙利法,分配问题可以用单纯形法或运输表求解。,库恩,(,W.W.Kuhn,),于,1955,年提出了指派问题的解法，他引用了匈牙利数学家康尼格,(,D.Knig,),一个关于矩阵中零元素的定理：,系数矩阵中独立,0,元素的最多个数等于能覆盖所有,0,元素的最少直线数,。,这个解法称为,匈牙利法,。,二、分配问题与匈牙利法,2.3,匈牙利法的基本思想,如果效率矩阵的所有元素,a,ij,0,而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的,x,ij,=1,，其余的,x,ij,=0,，则所得到的可行解就是问题的最优解。,显然令,x,11,=1,x,23,=1,x,32,=1,x,44,=1,，即将第一项工作分配给甲，第二项给丙，第三项给乙，第四项给丁。这时完成总工作的时间为最少。,如何寻找这组位于不同行不同列的零元素？,二、分配问题与匈牙利法,2.3,匈牙利法的基本定理,定理,1,如果从分配问题效率矩阵,a,ij,的每一行元素中分别减去,(,或加上,),一个常数,u,i,(,被称为该,行的位势,),，从每一列分别减去,(,或加上,),一个常数,v,j,(,被称为该,列的位势,),，得到一个新的效率矩阵,b,ij,，若其中,b,ij,=,a,ij,u,i,v,j,，,则,b,ij,的最优解等价于,a,ij,的最优解。,定理,2,若矩阵,A,的元素可分为,“,0,”,和非,“,0,”,两部分，则覆盖,“,0,”,元素的最少直线数等于位于不同行不同列的,“,0,”,元素的最大个数。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(1),人员,任务,甲,乙,丙,丁,译成英文,译成日文,译成德文,译成俄文,2,15,13,4,10,4,14,15,9,14,16,13,7,8,11,9,第一步：,找出每行的最小元素，每行对应减去这个元素。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(2),第二步：,找出矩阵每列的最小元素，再分别从各列中减去。,必定满足：,b,ij,=,a,ij,u,i,v,j,二、分配问题与匈牙利法,2.4,匈牙利法实例,(3),第三步：,从第一行开始，若该行只有一个零元素，对零元素打上,(),括号，表示行所代表的任务已指派。用直线划去其所在列；若该行没有零元素或有两个以上零元素,(,已划去的不计在内,),，则转下一行，依次进行到最后一行为止。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(4),第三步：,从第一列开始，若该列只有一个零元素，对零元素打上,(),括号,(,同样不考虑已划去的零元素,),，再用直线划去其所在行；若该列没有零元素或有两个零元素，则转下一列，依次进行到最后一列为止。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(5),效率矩阵,每行都有一个打,(),的零元素,，这些零元素都位于不同行不同列，令对应打,(),零元素的,x,ij,=1,就得到最优解；,矩阵中所有零元素或被划去，或被打上,(),，但打,(),的零元素,少于,m,个,，这时,转第四步,。,打,(),的零元素小于,m,，但未被划去的零元素之间存在,闭回路,。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(6),顺着闭回路的走向，对每个间隔的零元素打,(),，然后对所有打,(),的零元素或所在行或所在列画一条直线，同样得到最优解。,二、分配问题与匈牙利法,2.4,匈牙利法实例,(7),第四步：,继续按照定理,1,，对矩阵进行变换。,从矩阵未被直线覆盖的数字中找出一个最小的数,k,；对矩阵的每行，当该行有直线覆盖时，令,u,i,=0,，无直线覆盖的，令,u,i,=,k,；对矩阵中有直线覆盖的列，令,v,j,=,-k,，对无直线覆盖的列，令,v,j,=0,。,只有一条直线覆盖的元素保持不变,二、分配问题与匈牙利法,2.4,匈牙利法实例,(8),第五步：,回到第三步，迭代运算，直到矩阵的每一行都有一个打,(),的零元素为止。,最优分配方案为：甲译俄文，乙译日文，丙译英文，丁译德文。所需时间为：,4,+,4,+,9,+,11=28h,二、分配问题与匈牙利法,2.5,人数和任务数不相等的分配问题,有四项工作分配给六个人去完成，每个人分别完成各项工作的时间如下，依然规定每个人完成一项工作。每项工作只交给一个人去完成。即六个人中挑选哪四个人去完成，花费时间最少。,工作,人,I,II,III,IV,1,2,3,4,5,6,3,7,3,6,5,5,6,1,6,4,2,7,2,4,5,3,4,6,6,4,8,7,3,2,工作,人,I,II,III,IV,V,VI,1,2,3,4,5,6,3,7,3,6,5,5,6,1,6,4,2,7,2,4,5,3,4,6,6,4,8,7,3,2,0,0,0,0,0,0,0,0,0,0,0,0,二、分配问题与匈牙利法,2.6,目标函数最大化的分配问题,令,b,ij,=,M,-,a,ij,标准化,M,为充分大的常数，可以得到,b,ij,0,。根据定理,1,，这种转换是等价的。,b,ij,=,a,ij,u,i,v,j,=,a,ij,+,M,若,a,ij,0,，转换后的效率矩阵不符合匈牙利法的条件。,第四章 整数规划及分配问题,作 业 一,求下面指派问题的最优解,第三节 分枝定界法,第四章 整数规划及分配问题,三、分枝定界法,3.1,分枝定界法的基本思想,分枝定界法,可用于,全部类型,的整数规划问题。,设有最大化的整数规划问题,A,，对应的,线性规划为问题,B,，从解问题,B,开始，若其最优解不符合,A,的整数条件，那么,B,的最优目标函数必是,A,的最优目标函数,z,*,的,上界,，记作 ；而,A,的任意可行解的目标函数值将是,z,*,的,下界,。分支定界法就是将,B,的可行域分成子区域,(,称为,分枝,),的方法，逐步减小和增大上、下界，最终得到整数规划问题,A,的,z,*,。,三、分枝定界法,3.2,分枝定界法实例,(1),求解,B,：,其最优解为,x,1,=3.25,，,x,2,=2.5,，最优目标函数值为,z,*,=14.75,松弛问题,定界：,令,x,1,=0,，,x,2,=0,作为初始整数解，其,z,=0,，因此 。,分枝：,在,B,的最优解中，任取一个非整数变量，如,x,2,=2.5,；因,x,2,的最近邻整数解为,x,2,=2,或,x,2,=