数学软件MATLAB课件第五章整数规划.ppt

1,第五章 整数规划 Integer linear programming,第一节 整数规划的数学模型,一、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。 重点研究：整数线性规划问题,二、整数线性规划问题的模型,j=1,2,n,三、整数规划问题的类型：,3. 混合整数规划：部分决策变量取整数 值的线性规划,1.纯整数规划：全部决策变量都取整数 值的线性规划,2. 0-1型整数规划：决策变量只取0 或1的线性规划,例1: 某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？,举例,minZ= x1 + x2 +x3+x4+x5,x1 10 x1 + x2 8 x1 + x2+ x3 9 x1+x2+ x3 + x4 11 x2+ x3 + x4 + x5 13 x3+ x4 + x5 8 x4 + x5 5 x5 3 xj 0 (j =1,5)且为整数,解：设在第j时段开始时上班的服务员人数为xj,这是一个纯整数规划,例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj , 此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,解：令,这是一个 0-1规划,j=1,.,n,例3 工厂A1和A2生产某种物资，由于该种物资供不应求，还需要再建一家工厂。由两个待选方案A3和A4。物资需求地为Bj(j=1,2,3,4)。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费见下表。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。,1 若建工厂A3 0 若建工厂A4,再设xij为由Ai送往Bj 的物资数量(i,j=1,.,4) 则总费用为,解: 令 y=,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) xij0, y=0或1,混合整数规划,引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量 、可获利润及托运限制如下：,两种货物各托运多少箱使利润最大？,四、解的特点,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20，且为整数,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20，,x2,x1,松弛问题：,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,(4.8, 0 ) A Z=96,(4.8, 0 ) A Z=96,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,x1 , x2 为整数,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x1 , x2 为整数,x2,x1,(4.8, 0 ) A Z=96,Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20,x2,x1,(4.8, 0 ) A Z=96,x1 , x2 为整数,(4,0) Z=80 (5,0) 不在可行域 (4,1) max Z=90,（5）ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。,注释：,（4）整数规划问题的可行域是它的松弛问题可行域的子集，所以松弛问题得最优解优于整数规划问题的最优解。,（1）最优解不一定在顶点上达到,（2）最优解不一定是放松问题最优解的邻近整数解,（3）枚举法不可取,第二节 解纯整数规划的割平面法,考虑纯整数规划问题：,其中ai j和bi 皆为整数。,(ILP),一、 割平面法（Gomory法）基本思想,利用单纯形法求得其松弛问题的最优解，若不满足整数条件，则将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。即增加线性约束条件于原松弛问题中，形成一个新的线性规划，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解为止。,x0,x1,x*,约束条件构造的条件,（1）已获得的不符合整数要求的线性规划最优解不满足该线性约束条件,从而不可能在以后的解中出现;,（2）凡是整数可行解均满足该线性约束条件,因而整数最优解始终保留在每次形成的线性规划中.,二、割平面约束的构造,在松弛问题的最优单纯性表中，记s为基变量的下标集， 为非基变量的下标集。,m个约束方程可表示为:,将系数和常数分解为整数N和正真分数f之和，即：,割平面约束,上式左端是整数，右端1，因此,割平面约束条件的性质,(2)有上面的推导知，凡是满足ILP约束条件的整数可行解均满足该约束条件。,因此约束条件满足两个基本性质，把它加入到松弛问题中得一新的线性规划。,(1)由于非基变量xj取值为0，所以,三、割平面法求解举例,-x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x2 ,x3 ,x40,松弛规划,例1,松弛问题的最优单纯形表为：,将 -3x3-x4+x5= -3（割平面方程）代入最优表,例2 用割平面法求解纯整数规划,松弛规划,最终单纯形表如下：,x1+1/7x3 + 2/7x5=13/7 x1+1/7x3 + 2/7x5=1+6/7 x1- 1 = 6/7 -（1/7x3 + 2/7x5） 6/7 -（1/7x3 + 2/7x5）0 -1/7x3 - 2/7x5- 6/7,-1/7x3 - 2/7x5- 6/7 -1/7x3 - 2/7x5+x6=- 6/7,-1/4x4 -1/4x6-3/4,-1/4x4 -1/4x6+x7=-3/4,-1/4x4 -1/4x6+x7=-3/4,第三节 分支定界法,例1,松弛问题,(11/4,9/4) Z=31/4,(3,3/2) Z=15/2,(2,2) Z=6,无 解,无 解,(11/4,9/4),x12,x13,(2,2),(3,3/2),x21,x22,(19/6,1) Z=22/3,(3,1) Z=7,(19/6,1),x13,x14,1 2 3 4,3 2 1,最优值为Z=7，最优解为(3,1),一、基本思想,（1）分支：如果松弛线性规划的最优解不符合整数要求，即至少有一个分量不是整数，,假设,则构造两个约束条件,分别加入松弛问题中，把线性规划的可行域切割成两部分，形成两个分支，分别求解这两个线性规划，如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。如此继续下去，直到获得整数规划的最优解。,不是整数，,（2）定界：分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。,一、基本思想,原问题A,松弛问题B,例2,分支定界法如下,问题B x1=4.81 ,x2=1.82 Z=356,Z=356 Z=0,问题C1 x1=4,x2=2.1 Z=349,问题C2 x1=5 ,x2=1.57 Z=341,Z=349 Z=0,问题D1 x1=4, x2=2 Z=340,问题D2 x1=1.42 x2=3 Z=327,Z=349 Z=340,问题D3 x1=5.44 x2=1 Z=308,Z*=340,问题D4 无可行解,第四节 0-1型整数规划,一、0-1变量的概念 0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。,现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj , 此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,二、0-1变量的实际应用,1. 制定相互排斥的计划,例1：投资场所的选定,解：令,j=1,.,n,2. 相互排斥的约束条件问题,例：集装箱运货（用车运或用船运）,两种货物各托运多少箱可以使利润最大？,Max Z=20x1+10x2 5x1+4x224+yM 7x1+3x245 +(1-y)M 2x1+5x213 x1, x20 ，y=0或1 x1, x2为整数,解：,x1 ，x2 分别为甲乙两种货物托运的箱数,3. 固定费用问题,例：有三种资源被用于生产三种产品，资源量、产品单件可变费用、售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。,解：设xj 为生产第 j 种产品的数量(件),2x1+4x2+8x3500 2x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1 x2 M2y2 x3 M3y3 xj 0且为整数，j=1,2,3 yj=0或1，j=1,2,3,max Z=4x1+5x2+6x3-100y1-150y2-200y3,4. 工件排序问题,例：4台机床加工3件产品，产品i在机床j上的加工工时为aij,制定加工方案，使最短的时间内加工完全部产品,解：设xi表示产品i在机床j上开始加工时间,（1）同一产品在不同机床上的加工顺序约束,产品1：x11+a11x13,及 x13+a13x14,产品2：x21+a21x22,及 x22+a22x24,产品3：x32+a32x33,（2）每台机床对不同产品加工顺序约束,机床1：x11+a11x21+My1,及:x21+a21x11+M(1-y1),机床2：x22+a22x32+My2,及:x32+a32x22+M(1-y2),机床3：x13+a13x33+My3,及:x33+a33x13+M(1-y3),机床4：x14+a14x24+My4,及:x24+a24x14+M(1-y4),（3）产品2加工总时间约束,x24+a24 - x21 d,（4）目标函数的建立,W=max( x14+a14 ,x24+a24 , x33+a33),设全部产品加工完毕的结束时间为W,目标函数Z为,模型为：,x11+a11x13,x13+a13x14,x21+a21x22,x22+a22x24,x32+a32x33,x11+a11x21+My1,x21+a21x11+M(1-y1),x22+a22x32+My2,x32+a32x22+M(1-y2),x13+a13x33+My3,x33+a33x13+M(1-y3),x14+a14x24+My4,x24+a24x14+M(1-y4),x24+a24 - x21 d,三、0-1型整数规划的解法 隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。 过滤条件：目标函数值优于计算过的可行解目标函数值。,例1,例2,目标函数有大到小排列,第五节 指派问题,一、典型的指派问题 某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？,指派问题的标准形式 n个人，n件事，第i个人做第j件事的费用为cij,确定人和事之间一一对应的指派方案，使完成n件事的总费用最小。,效率矩阵 或 系数矩阵,C=(cij )nn=,2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9,二、标准指派问题的数学模型,解矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。 例：,三、匈牙利解法 （1）关键性质： 若从指派问题的系数矩阵(cij)nn的某行或某列各元素中分别减一个常数k, 得到的新矩阵与原矩阵有相同的最优解。,C=(cij )nn=,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,匈牙利法的步骤 1.变换系数矩阵,C=(cij )nn=,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,匈牙利法的步骤 2.寻找独立“0”元素,C=(cij )nn=, 13 7 6 6 9 5 3 2 1 ,匈牙利法的步骤 2.寻找独立“0”元素,C=(cij )nn=,2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9,Min Z=c31+c22+c43+c14=4+4+9+11=28,匈牙利法的步骤 2.寻找独立“0”元素,130页例13,C=(cij )nn=,4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6,匈牙利法的步骤 2.寻找独立“0”元素,130页例13,C=(cij )nn=,0 4 3 11 8 0 2 10 7 3 0 3 6 2 1 0 1 8 0 4 0 3 6 4 0,匈牙利法的步骤 2.寻找独立“0”元素,130页例13,C