《数学软件MATLAB课件第五章整数规划.ppt》由会员分享，可在线阅读，更多相关《数学软件MATLAB课件第五章整数规划.ppt（83页珍藏版）》请在三一办公上搜索。
1、1,第五章 整数规划Integer linear programming,第一节 整数规划的数学模型,一、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题,二、整数线性规划问题的模型,j=1,2,n,三、整数规划问题的类型：,3.混合整数规划：部分决策变量取整数 值的线性规划,1.纯整数规划：全部决策变量都取整数 值的线性规划,2.0-1型整数规划：决策变量只取0 或1的线性规划,例1:某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作
2、8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？,举例,minZ=x1+x2+x3+x4+x5,x1 10 x1+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个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选
3、择两个。应当怎样选择投资项目，才能使总预期收益最大？,解：令,这是一个 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 x
4、12+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=200yx41+x42+x43+x44=200(1-y)xij0,y=0或1,混合整数规划,引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量、可获利润及托运限制如下：,两种货物各托运多少箱使利润最大？,四、解的特点,Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20，且为整数,Max Z=20 x1+10 x25x1+4x2242
5、x1+5x213x1,x20，,x2,x1,松弛问题：,Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20,x2,x1,Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20,x2,x1,(4.8,0)AZ=96,(4.8,0)AZ=96,Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20,x2,x1,x1,x2 为整数,Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20,x1,x2 为整数,x2,x1,(4.8,0)AZ=96,Max Z=20 x1+10 x25x1+
6、4x2242x1+5x213x1,x20,x2,x1,(4.8,0)AZ=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),一、割平
7、面法（Gomory法）基本思想,利用单纯形法求得其松弛问题的最优解，若不满足整数条件，则将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。即增加线性约束条件于原松弛问题中，形成一个新的线性规划，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解为止。,x0,x1,x*,约束条件构造的条件,（1）已获得的不符合整数要求的线性规划最优解不满足该线性约束条件,从而不可能在以后的解中出现;,（2）凡是整数可行解均满足该线性约束条件,因而整数最优解始终保留在每次形成的线性规划中.,二、割平面约束的构造,在松弛问题的最优单纯性表中，记s为基变量的下标集，
8、为非基变量的下标集。,m个约束方程可表示为:,将系数和常数分解为整数N和正真分数f之和，即：,割平面约束,上式左端是整数，右端1，因此,割平面约束条件的性质,(2)有上面的推导知，凡是满足ILP约束条件的整数可行解均满足该约束条件。,因此约束条件满足两个基本性质，把它加入到松弛问题中得一新的线性规划。,(1)由于非基变量xj取值为0，所以,三、割平面法求解举例,-x1+x2+x3=13x1+x2+x4=4x1,x2,x3,x40,松弛规划,例1,松弛问题的最优单纯形表为：,将-3x3-x4+x5=-3（割平面方程）代入最优表,例2 用割平面法求解纯整数规划,松弛规划,最终单纯形表如下：,x1+
9、1/7x3+2/7x5=13/7 x1+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,-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
10、/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）定界：分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如
11、果目标函数值劣于或等于这个“界”，就停止继续分支。,一、基本思想,原问题A,松弛问题B,例2,分支定界法如下,问题B x1=4.81,x2=1.82 Z=356,Z=356Z=0,问题C1 x1=4,x2=2.1 Z=349,问题C2x1=5,x2=1.57 Z=341,Z=349Z=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变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时
12、是否取某个特定方案。,现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,二、0-1变量的实际应用,1.制定相互排斥的计划,例1：投资场所的选定,解：令,j=1,.,n,2.相互排斥的约束条件问题,例：集装箱运货（用车运或用船运）,两种货物各托运多少箱可以使利润最大？,Max Z=20 x1+10 x25x1+4x224+yM7x1+3x245+(1-y)M2x1+5x2
13、13x1,x20，y=0或1x1,x2为整数,解：,x1，x2 分别为甲乙两种货物托运的箱数,3.固定费用问题,例：有三种资源被用于生产三种产品，资源量、产品单件可变费用、售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。,解：设xj 为生产第 j 种产品的数量(件),2x1+4x2+8x35002x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1 x2 M2y2 x3 M3y3xj 0且为整数，j=1,2,3yj=0或1，j=1,2,3,max Z=4x1+5x2+6x3-100y1-150y2-200y3,4.工件排序问题,例：4台
14、机床加工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
15、),机床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),x1
16、4+a14x24+My4,x24+a24x14+M(1-y4),x24+a24-x21 d,三、0-1型整数规划的解法 隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。过滤条件：目标函数值优于计算过的可行解目标函数值。,例1,例2,目标函数有大到小排列,第五节 指派问题,一、典型的指派问题 某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做
17、E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？,例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？,指派问题的标准形式 n个人，n件事，第i个人做第j件事的费用为cij,确定人和事之间一一对应的指派方案，使完成n件事的总费用最小。,效率矩阵或系数矩阵,C=(cij)nn=,2151341041415914161378119,二、标准指派问题的数学模型,解
18、矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。例：,三、匈牙利解法（1）关键性质：若从指派问题的系数矩阵(cij)nn的某行或某列各元素中分别减一个常数k,得到的新矩阵与原矩阵有相同的最优解。,C=(cij)nn=,01370606905320100,匈牙利法的步骤1.变换系数矩阵,C=(cij)nn=,01370606905320100,匈牙利法的步骤2.寻找独立“0”元素,C=(cij)nn=,137669 532 1,匈牙利法的步骤2.寻找独立“0”元素,C=(cij)nn=,2151341041415914161378119,Min Z=c31+c22+c43+c1
19、4=4+4+9+11=28,匈牙利法的步骤2.寻找独立“0”元素,130页例13,C=(cij)nn=,4 8 7 15 127 9 17 14 106 9 12 8 76 7 14 6 106 9 12 10 6,匈牙利法的步骤2.寻找独立“0”元素,130页例13,C=(cij)nn=,0 4 3 11 80 2 10 7 30 3 6 2 10 1 8 0 40 3 6 4 0,匈牙利法的步骤2.寻找独立“0”元素,130页例13,C=(cij)nn=,0 3 0 11 80 1 7 7 30 2 3 2 10 0 5 0 40 2 3 4 0,匈牙利法的步骤4.继续变换系数矩阵,1 3
20、 11 80 0 6 6 20 1 2 1 01 5 41 2 3 4,（1）未被覆盖的元素中减去最小元素，出现新的0元素（2）打列中各元素都加上最小元素。,匈牙利法的步骤4.继续变换系数矩阵,1 3 11 80 0 6 6 20 1 2 1 01 5 41 2 3 4,（1）未被覆盖的元素中减去最小元素，出现新的0元素（2）打列中各元素都加上最小元素。,匈牙利法的步骤4.继续变换系数矩阵,1 3 0 11 80 0 6 6 20 1 2 1 01 0 5 0 41 2 3 4 0,（1）未被覆盖的元素中减去最小元素，出现新的0元素（2）打列中各元素都加上最小元素。,匈牙利法的步骤5.重新寻找独立0元素,1 3 0 11 80 0 6 6 20 1 2 1 01 0 5 0 41 2 3 4 0,匈牙利法的步骤5.重新寻找独立0元素,1 3 11 8 6 6 2 1 2 1 1 5 41 2 3 4,X=(xij)nn=,0 0 1 0 00 1 0 0 01 0 0 0 00 0 0 1 00 0 0 0 1,四、一般的指派问题1.最大化指派问题（用最大元素-所有元素化成最小化问题）2.人数和事数不等3.一个人可做几件事的指派问题4.某件事一定不能由某人做,
