运筹学课件第五章 整数规划

第1页1第五章整数规划Integerlinearprogramming第2页第一节整数规划的数学模型一、整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题第3页二、整数线性规划问题的模型j=1,2,…,njnjjxcZ1max(min)0),(1jinjjijxbxai=1,2,…,mxj中取部分或全部为整数第4页三、整数规划问题的类型：3.混合整数规划：部分决策变量取整数值的线性规划1.纯整数规划：全部决策变量都取整数值的线性规划2.0-1型整数规划：决策变量只取0或1的线性规划第5页例1:某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？时段12345678服务员最少数目10891113853举例第6页minZ=x1+x2+x3+x4+x5x110x1+x28x1+x2+x39x1+x2+x3+x411x2+x3+x4+x513x3+x4+x58x4+x55x53xj0(j=1,…,5)且为整数解：设在第j时段开始时上班的服务员人数为xj这是一个纯整数规划第7页例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？第8页1对项目j投资0对项目j不投资xj=MaxZ=∑cjxj∑ajxj≤Bx2≥x1x3+x4≥1x5+x6+x7=2xj=0或1（j=1,2,…n）解：令这是一个0-1规划j=1,...,n第9页例3工厂A1和A2生产某种物资，由于该种物资供不应求，还需要再建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费见下表。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。第10页B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量350400300150第11页1若建工厂A30若建工厂A4再设xij为由Ai送往Bj的物资数量(i,j=1,...,4)则总费用为解:令y=)]-1500(1[1200Zmin4141yyxciijjij第12页x11+x21+x31+x41=350x12+x22+x32+x42=400x13+x23+x33+x43=300x14+x24+x34+x44=150x11+x12+x13+x14=400x21+x22+x23+x24=600x31+x32+x33+x34=200yx41+x42+x43+x44=200(1-y)xij≥0,y=0或1混合整数规划第13页引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？四、解的特点第14页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0，且为整数第15页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0，x2x1松弛问题：第16页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1第17页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96第18页(4.8,0)AZ=96MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1x1,x2为整数第19页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x1,x2为整数x2x1(4.8,0)AZ=96第20页MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96x1,x2为整数(4,0)Z=80(5,0)不在可行域(4,1)maxZ=90第21页（5）ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。注释：（4）整数规划问题的可行域是它的松弛问题可行域的子集，所以松弛问题得最优解优于整数规划问题的最优解。（1）最优解不一定在顶点上达到（2）最优解不一定是放松问题最优解的邻近整数解（3）枚举法不可取第22页第二节解纯整数规划的割平面法考虑纯整数规划问题：),...,1(0),...,1(..max11njxmibxatsxcZjinjjijnjjj且为整数其中aij和bi皆为整数。(ILP)第23页一、割平面法（Gomory法）基本思想利用单纯形法求得其松弛问题的最优解，若不满足整数条件，则将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。即增加线性约束条件于原松弛问题中，形成一个新的线性规划，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解为止。第24页x0x1x*第26页sibxaxisjjiji二、割平面约束的构造在松弛问题的最优单纯性表中，记s为基变量的下标集，为非基变量的下标集。m个约束方程可表示为:ssjsjbxxxXjjTn,0,),...,(***1*其中其最优解为第27页isjjijibxaxiisjjijijifNxfNx)(将系数和常数分解为整数N和正真分数f之和，即：设其对应的方程为不是整数若,)(sibi0sjjijixff割平面约束10,10,iijiijffNN均为整数，其中sjjijiisjjijixffNxNx移项得上式左端是整数，右端1，因此isjjijfxf)(第28页割平面约束条件的性质(2)有上面的推导知，凡是满足ILP约束条件的整数可行解均满足该约束条件。得）（代入约束将isjjijfxfX*不满足约束条件。所以*X因此约束条件满足两个基本性质，把它加入到松弛问题中得一新的线性规划。矛盾,0if(1)由于非基变量xj取值为0，所以第29页),...,1(0),...,1(..max11njxmibxatsxczjinjjijnjjj),...,1(0)(),...,1(..max11njxfxfmibxatsxczjisjjijinjjijnjjj第30页三、割平面法求解举例MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0且为整数MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0-x1+x2+x3=13x1+x2+x4=4x1,x2,x3,x4≥0松弛规划例1第31页松弛问题的最优单纯形表为：CBXBb1100x1x2x3x40x31-11100x443101σj1100…………………1x13/410-1/41/41x27/4013/41/4σj00-1/2-1/2474143432xxx第32页474143432xxx43414343xx3343xx33543xxx474143432xxx第33页将-3x3-x4+x5=-3（割平面方程）代入最优表CBXBb11000x1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5-300-3-11σj00-1/2-1/201x111001/31/121x2101001/40x310011-1/3σj000-1/3-1/3，满足整数要求。最优解为TTxxx)0,0,1,1,1(),,,(521第34页MaxZ=3x1-x23x1-2x2≤35x1+4x2≥102x1+x2≤5x1,x2≥0且为整数MaxZ=3x1-x23x1-2x2≤35x1+4x2≥102x1+x2≤5x1,x2≥0例2用割平面法求解纯整数规划松弛规划最终单纯形表如下：第35页CBXBb3-1000x1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70x431/700-3/7122/7Z=30/7σj00-5/70-3/7x1+1/7x3+2/7x5=13/7x1+1/7x3+2/7x5=1+6/7x1-1=6/7-（1/7x3+2/7x5）6/7-（1/7x3+2/7x5）≤0-1/7x3-2/7x5≤-6/7第36页-1/7x3-2/7x5≤-6/7-1/7x3-2/7x5+x6=-6/7CBXBb3-10000x1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700x431/700-3/7122/700x6-6/700-1/70-2/71σj00-5/70-3/70第37页CBXBb3-10000x1x2x3x4x5x63x11100001-1x25/4010-1/40-5/40x35/2001-1/20-11/20x57/40001/41-3/4Z=7/4σ00000-17/4-1/4x4-1/4x6≤-3/4-1/4x4-1/4x6+x7=-3/4第38页CBXBb3-100000x1x2x3x4x5x6x73x111000010-1x2201000-1-10x3400100-5-20x5100001-110x43000101-4Z=-1σj00000-4-1-1/4x4-1/4x6+x7=-3/4，满足整数要求。最优解为TTxxx)0,0,1,3,4,2,1(),,,(721第39页第三节分支定界法整数0,21260522121212121xxxxxxxxxxMaxZ例10,21260522121212121xxxxxxxxxxMaxZ松弛问题第40页(11/4,9/4)Z=31/4(3,3/2)Z=15/2(2,2)Z=6无解无解(11/4,9/4)x1≤2x1≥3(2,2)(3,3/2)x2≤1x2≥2(19/6,1)Z=22/3(3,1)Z=7(19/6,1)x1≤3x1≥41234321最优值为Z=7，最优解为(3,1)第41页一、基本思想（1）分支：如果松弛线性规划的最优解不符合整数要求，即至少有一个分量不是整数，假设则构造两个约束条件分别加入松弛问题中，把线性规划的可行域切割成两部分，形成两个分支，分别求解这两个线性规划，如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。如此继续下去，直到获得整数规划的最优解。1][][iiiibxbx和iibx不是整数，第42页（2）定界：分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。一、基本思想第43页原问题AMaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0x1,x2都为整数MaxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0松弛问题B例2分支定界法如下第44页问题Bx1=4.81,x2=1.82Z=356Z=356Z=0问题C1x1=4,x2=2.1Z=349问题C2x1=5,x2=1.57Z=341x1≤4x1≥5Z=349Z=0x2≤2x2≥3问题D1x1=4,x2=2Z