运筹学课件第5章整数规划.pptVIP

*;第一节 整数规划的数学模型;二、整数线性规划问题的模型;三、整数规划问题的类型：;例1: 某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？;minZ= x1 + x2 +x3+x4+x5;例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj , 此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？;1 对项目 j 投资 0 对项目 j 不投资 ; 例3 工厂A1和A2生产某种物资，由于该种物资供不应求，还需要再建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。各工厂年生产能力、各地年需求量、各厂???各需求地的单位物资运费见下表。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。;;;x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200y x41+ x42+ x43+ x44=200(1-y) xij≥0, y=0或1;引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量 、可获利润及托运限制如下：;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0，且为整数 ;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0，;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0;(4.8, 0 ) A Z=96;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0;Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0; （5）ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。;第二节 解纯整数规划的割平面法;一、 割平面法（Gomory法）基本思想;x0;约束条件构造的条件;二、割平面约束的构造;将系数和常数分解为整数N和正真分数f之和，即：;割平面约束条件的性质;三、割平面法求解举例;松弛问题的最优单纯形表为：;将 -3x3-x4+x5= -3（割平面方程）代入最优表;MaxZ=3x1-x2 3x1-2x2≤3 5x1+4x2≥10 2x1+x2≤5 x1,x2≥0 且为整数;CB;-1/7x3 - 2/7x5≤- 6/7 -1/7x3 - 2/7x5+x6=- 6/7;CB;CB;第三节 分支定界法;(11/4,9/4) Z=31/4;一、基本思想;（2）定界：分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。;原问题A ; 问题B x1=4.81 ,x2=1.82 Z=356;第四节 0-1型整数规划;现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj , 此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？;1 对项目 j 投资 0 对项目 j 不投资 ;2. 相互排斥的约束条件问题;Max Z=20x1+10x2 5x1+4x2≤24+yM 7x1+3x2≤45 +(1-y)M 2x1+5x2≤13 x1, x2≥0 ，y=0或1 x1, x2为整数; 产品 资源;解：设xj 为生产第 j 种产品的数量(件);4. 工件排序问题;解：设xi表示产品i在机床j上开始加工时间;（2）每台机床对不同产品加工顺序约束;（3）产品2加工总时间约束;（4）目标函数的建立;模型为：;三、0-1型整数规划的解法