运筹学整数规划

第1页整数线性规划IntegerLinearProgramming问题与模型整数规划算法：分枝定界法、隐枚举法、匈牙利算法Excel求解2在上一章讨论的LP问题中，对决策变量只限于不能取负值的连续型数值，即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(IntegerProgramming)(简记为IP)。又称约束条件和目标函数均为线性的IP为整数线性规划(IntegerLinearProgramming)(简记为ILP)。§7.1整数线性规划的数学模型（二）、整数规划的数学模型一般形式且部分或全部为整数或n)1.2(j0)2.1()min(max11jnjijijnjjjxmibxaxcZZ依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0－1整数规划：所有决策变量只能取0或1两个整数。为整数xxbAxtsxc,0..min一般整数规划模型pixxbAxtsxci,...,2,1,0..min为整数混合整数规划模型nixbAxtsxci,...,2,1;1,0..min0-1整数规划模型例1、合理下料问题设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？零件方个数式零件零件毛坯数nBB1mAA1mbb1mnmnaaaa1111一、整数规划的模型设：xj表示用Bj(j=1.2…n)种方式下料根数模型：且为整数n)1.2(j0)2.1(min11jnjijijnjjxmibxaxZ例2、某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi(i=1.2…m),又有n个地点B1,B2,…Bn需要销售这种产品，其销量分别为b1.b2…bn。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？单销地厂址价生产能力建设费用销量nmmmnmmmnnbbbfacccAfacccAfacccABnBB2121222222121111211121设：xij表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设Yi＝（i=1.2…m）0不在Ai建厂模型：n)1.2jm1.2(i10,0n)1.2(j)2.1(min111、或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ序号1234567物品食品氧气冰镐绳索帐篷相机设备重量55261224重要系数201518148410例3：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7背包问题(KnapsackProblem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划:MaxZ=Σcjxjs.t.Σajxjbxj=0或117例题4某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E59解：决策变量：设)5,4,3,2,1j(j1j0xj被选中表示项目不被选中表示项目目标函数：期望收益最大xxxxx54321967810zmax约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：10111554246967810zmaxxxxxxxxxxxxxxxxxxxj43423215432154321或例5某服务部门各时段（每2小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作8小时（即四个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。时段12345678服务员最少数目10891113853解：设在第j时段开始时上班的服务员人数为xj，由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班，故决策变量只需考虑x1,x2,x3,x4,x5，此问题的数学模型为：且为整数0,,,,35813119810min543215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZ20例题6（固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。产品单件耗量资源123资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助0-1变量解决这个困难设xj是第j种产品的产量，j=1,2,3,再设)0(0)0(1xjxjyjjj种产品若不生产第种产品若生产第则问题的整数规划模型为：10,010032300432500842200150100654max332211321321321321321或且为整数yxyMxyMxyMxxxxxxxxxxyyyxxxZjjM为很大的正数案例7（工件排序问题）用4台机床加工3件产品。各产品的机床加工顺序，以及产品i在机床j上的加工工时aij如下表。由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1a11a13a14机床1机床3机床4产品2a21a22a24机床1机床2机床4产品3a32a33机床2机床3解：设xij表示产品i在机床j上开始加工的时间(i=1,2,3;j=1,2,3,4)下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故应有：产品1：及xax141313xax131111产品2：及xax242222xax222121产品3：xax3332322、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床1，有两种加工顺序。或先加工产品1，后加工产品2；或反之。对于其它3台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入0-1变量)4,3,2,1(10jyj先加工另一件产品先加工某件产品各yj的意义是明显的。如当yj=0时，表示机床1先加工产品1，后加工产品2，当yj=1时，表示机床1先加工产品2，后加工产品1。机床1：及)1(1112121yMxaxyMxax1211111机床2：及)1(2223232yMxaxyMxax2322222机床3：及)1(3133333yMxaxyMxax3331313机床4：及)1(4142424yMxaxyMxax4241414那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证3、产品2的加工时间约束产品2的开始加工时间是x21，结束加工时间是x24+a24，故应有：dxax212424254、目标函数的建立设全部产品加工完毕的结束时间为W，由于三件产品的加工结束时间分别为x14+a14，x24+a24，x33+a33，故全部产品的实际加工结束时间为：),,max(333324241414axaxaxW转化为线性表达式：axWaxWaxWWZ333324241414min26由此，ILP问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使n1jjjXCMaxZ数且皆为整数或部分为整,0Xj)m,,2,1i(bXat.sn1jiijij上述例子还表明，利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量X1,X2,…,Xn，使njjjXCZ1max),,2,1(10),,2,1(1njXmibXajnjijij或（3.1）（3.2）（3.3）271.对可供项目的选择（1）如果在可供选择的前k(kn)个项目中，必须且只能选择一项，则在(3.2)中加入新的约束条件：kjjX11（2）如果可供选择的k(kn)个项目是相互排斥的，则在(3.2)中加入新的约束条件：kjjX11同时它还表示在第k个项目中至多只能选择一项投资。（3）如果在可供选择的k(kn)个项目中，至少应选择一项投资，则在(3.2)中加入新的约束条件：kjjX1128（4）如果项目j的投资必须以项目i的投资为前提，则可在(3.2)中加入新的约束条件：XjXi（5）如果项目i与项目j要么同时被选中，要么同时不被选中，则在(3.2)中加入新的约束条件：Xj=Xi(ij)2.对可供资源的选择（1）如果对第r种资源br与第t种资源bt的投资是相互排斥的，即只允许对资源br与bt中的一种进行投资，则可将(3.2)的第r个和第t个约束条件改写为：29①②njrjrjyMbXa1njtjtjMybXa1)1(其中y为新引进的0-1变量，M为充分大正数。易见，当y=0时，①式就是原来的第r个约束条件，具有约束作用。此时对②式而言，无论Xj为何值都成立，毫无约束作用，这就使问题仅允许第r种资源进行投资。当y=1时，②式对Xj起了约束作用，而①式成了多余的条件。到底是满足①还是②，