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

《运筹学课件第五章 整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、1第五章整数规划Integerlinearprogramming第一节整数规划的数学模型一、整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题二、整数线性规划问题的模型j=1,2,…,ni=1,2,…,mxj中取部分或全部为整数三、整数规划问题的类型：3.混合整数规划：部分决策变量取整数值的线性规划1.纯整数规划：全部决策变量都取整数值的线性规划2.0-1型整数规划：决策变量只取0或1的线性规划例1:某服务部门各时段（每2h为一时

2、段）需要的服务员人数见下表。按规定服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？时段12345678服务员最少数目10891113853举例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这是一个纯整数规划例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外

3、，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？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例3工厂A1和A2生产某种物资，由于该种物资供不应求，还需要再建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。各工厂年生产能力、各地年需求量、各厂至各需求地的单

4、位物资运费见下表。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量3504003001501若建工厂A30若建工厂A4再设xij为由Ai送往Bj的物资数量(i,j=1,...,4)则总费用为解:令y=x11+x21+x31+x41=350x12+x22+x32+x42=400x13+x23+x33+x43=300x14+x24+x34+x44=150x11+x12+x13+x14=

5、400x21+x22+x23+x24=600x31+x32+x33+x34=200yx41+x42+x43+x44=200(1-y)xij≥0,y=0或1混合整数规划引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413两种货物各托运多少箱使利润最大？四、解的特点MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0，且为整数MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0，x2x1松弛问题：MaxZ=20x1+10x25

6、x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96(4.8,0)AZ=96MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1x1,x2为整数MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x1,x2为整数x2x1(4.8,0)AZ=96MaxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1,x2≥0x2x1(4.8,0)AZ=96x1,x2为整

7、数(4,0)Z=80(5,0)不在可行域(4,1)maxZ=90（5）ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。注释：（4）整数规划问题的可行域是它的松弛问题可行域的子集，所以松弛问题得最优解优于整数规划问题的最优解。（1）最优解不一定在顶点上达到（2）最优解不一定是放松问题最优解的邻近整数解（3）枚举法不可取第二节解纯整数规划的割平面法考虑纯整数规划问题：其中aij和bi皆为整数。(ILP)一、割平面法（Gomory法）基本思想利用单纯形法求得其松弛问题的最优解，若不满足整数条件，则将松

8、弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问