《数学软件MATLAB课件第五章整数规划.ppt》由会员分享，可在线阅读，更多相关《数学软件MATLAB课件第五章整数规划.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1页1第五章 整数规划Integer linear programming第2页第一节 整数规划的数学模型一、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。重点研究：整数线性规划问题第3页二、整数线性规划问题的模型j=1,2,ni=1,2,mxj 中取部分或全部为整数第4页三、整数规划问题的类型：3.混合整数规划：部分决策变量取整数 值的线性规划 1.纯整数规划：全部决策变量都取整数 值的线性规划2.0-1型整数规划：决策变量只取0 或1的线性规划第5页例1:某服务部门各时段（每2h为
2、一时段）需要的服务员人数见下表。按规定服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少？时段1 2 3 4 5 6 7 8服务员最少数目10 8 9 11 13 8 5 3举例第6页minZ=x1+x2+x3+x4+x5x1 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这是一个纯整数规划第7页例2：现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,
3、此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？第8页1 对项目 j 投资0 对项目 j 不投资 xj=Max Z=cjxjajxjBx2 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)。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费见
4、下表。工厂A3和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用（包括物资运费和新工厂的生产费用）最小。第10页B1B2B3B4生产能力A12 9 3 4 400A28 3 5 7 600A37 6 1 2 200A44 5 2 5 200需求量350 400 300 150第11页 1 若建工厂A3 0 若建工厂A4再设xij为由Ai送往Bj 的物资数量(i,j=1,.,4)则总费用为解:令 y=第12页x11+x21+x31+x41=350 x12+x22+x32+x42=400 x13+x23+x33+x43=300 x14+x24+x34+x44=150 x1
5、1+x12+x13+x14=400 x21+x22+x23+x24=600 x31+x32+x33+x34=200yx41+x42+x43+x44=200(1-y)xij0,y=0或1混合整数规划第13页引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量、可获利润及托运限制如下：体积 重量 利润甲5 2 20乙4 5 10托运限制24 13两种货物各托运多少箱使利润最大？四、解的特点第14页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20，且为整数第15页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20，x2x1松弛问题：
6、第16页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1第17页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1(4.8,0)AZ=96第18页(4.8,0)AZ=96Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x2x1x1,x2 为整数第19页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20 x1,x2 为整数x2x1(4.8,0)AZ=96第20页Max Z=20 x1+10 x25x1+4x2242x1+5x213x1,x20
7、x2x1(4.8,0)AZ=96x1,x2 为整数(4,0)Z=80(5,0)不在可行域(4,1)max Z=90第21页（5）ILP是其中LP的一个子问题，所有解也是LP的可行解，所以如果LP的最优解满足ILP的整数条件，则已得最优解。注释：（4）整数规划问题的可行域是它的松弛问题可行域的子集，所以松弛问题得最优解优于整数规划问题的最优解。（1）最优解不一定在顶点上达到（2）最优解不一定是放松问题最优解的邻近整数解（3）枚举法不可取第22页第二节 解纯整数规划的割平面法考虑纯整数规划问题：其中ai j和bi 皆为整数。(ILP)第23页一、割平面法（Gomory法）基本思想 利用单纯形法求得
8、其松弛问题的最优解，若不满足整数条件，则将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。即增加线性约束条件于原松弛问题中，形成一个新的线性规划，逐渐缩小解的范围，又不去掉整数解，直至找到最优解为整数解为止。第24页x0 x1x*第26页二、割平面约束的构造 在松弛问题的最优单纯性表中，记s为基变量的下标集，为非基变量的下标集。m个约束方程可表示为:第27页将系数和常数分解为整数N和正真分数f之和，即：割平面约束上式左端是整数，右端1，因此第28页割平面约束条件的性质(2)有上面的推导知，凡是满足ILP约束条件的整数可行解均满足该约束条件。因此约束
9、条件满足两个基本性质，把它加入到松弛问题中得一新的线性规划。(1)由于非基变量xj取值为0，所以第29页第30页三、割平面法求解举例Max Z=x1+x2-x1+x213x1+x2 4x1,x20且为整数Max Z=x1+x2-x1+x213x1+x2 4x1,x20-x1+x2+x3=13x1+x2+x4=4x1,x2,x3,x40松弛规划例1第31页松弛问题的最优单纯形表为：CBXBb1 1 0 0 x1x2x3x40 x31-1 1 1 00 x44 3 1 0 1j1 1 0 0 1 x13/4 1 0-1/4 1/41 x27/4 0 1 3/4 1/4j0 0-1/2-1/2第32
10、页第33页将-3x3-x4+x5=-3（割平面方程）代入最优表CBXBb1 1 0 0 0 x1x2x3x4x51 x13/4 1 0-1/4 1/4 01 x27/4 0 1 3/4 1/4 00 x5-3 0 0-3-1 1j0 0-1/2-1/2 01 x11 1 0 0 1/3 1/121 x21 0 1 0 0 1/40 x31 0 0 1 1-1/3j0 0 0-1/3-1/3第34页MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20 且为整数MaxZ=3x1-x23x1-2x235x1+4x2102x1+x25x1,x20例2 用割平面法求解纯整数
11、规划松弛规划最终单纯形表如下：第35页CBXBb3-1 0 0 0 x1x2x3x4x53 x113/7 1 0 1/7 0 2/7-1 x29/7 0 1-2/7 0 3/70 x431/7 0 0-3/7 1 22/7Z=30/7 j0 0-5/7 0-3/7x1+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 第36页-1/7x3-2/7x5-6/7-1/7x3-2/7x5+x6=-6/7CBXBb3-1 0 0 0 0 x1x2x3x4x5x63
12、x113/7 1 0 1/7 0 2/7 0-1 x29/7 0 1-2/7 0 3/7 00 x431/7 0 0-3/7 1 22/7 00 x6-6/7 0 0-1/7 0-2/7 1j0 0-5/7 0-3/7 0第37页CBXBb3-1 0 0 0 0 x1x2x3x4x5x63 x11 1 0 0 0 0 1-1 x25/4 0 1 0-1/4 0-5/40 x35/2 0 0 1-1/2 0-11/20 x57/4 0 0 0 1/4 1-3/4Z=7/4 0 0 0 0 0-17/4-1/4x4-1/4x6-3/4-1/4x4-1/4x6+x7=-3/4第38页CBXBb3-1
13、 0 0 0 0 0 x1x2x3x4x5x6x73 x11 1 0 0 0 0 1 0-1 x22 0 1 0 0 0-1-10 x34 0 0 1 0 0-5-20 x51 0 0 0 0 1-1 10 x43 0 0 0 1 0 1-4Z=-1 j0 0 0 0 0-4-1-1/4x4-1/4x6+x7=-3/4第39页第三节 分支定界法例1松弛问题第40页(11/4,9/4)Z=31/4(3,3/2)Z=15/2(2,2)Z=6无 解无 解(1 1/4,9/4)x12x13(2,2)(3,3/2)x21x22(19/6,1)Z=22/3(3,1)Z=7(19/6,1)x13x141 2
14、 3 4 3 2 1最优值为Z=7，最优解为(3,1)第41页一、基本思想（1）分支：如果松弛线性规划的最优解不符合整数要求，即至少有一个分量不是整数，假设 则构造两个约束条件分别加入松弛问题中，把线性规划的可行域切割成两部分，形成两个分支，分别求解这两个线性规划，如果这两个线性规划的最优解还不是整数解，分别把每一个可行域再进行分割。如此继续下去，直到获得整数规划的最优解。不是整数，第42页（2）定界：分支过程得到的整数解中，目标函数值最优的一个叫做整数规划目标函数值的“界”。分支过程中非整数的线性规划的最优解，如果目标函数值劣于或等于这个“界”，就停止继续分支。一、基本思想第43页原问题A
15、MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 x1,x2 都为整数MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 松弛问题B例2分支定界法如下第44页 问题B x1=4.81,x2=1.82 Z=356Z=356Z=0 问题C1 x1=4,x2=2.1 Z=349 问题C2x1=5,x2=1.57 Z=341x14x15Z=349Z=0 x22x23问题D1 x1=4,x2=2 Z=340问题D2 x1=1.42 x2=3 Z=327Z=349 Z=340 x21x22问题D3 x1=5.44 x2=1 Z=
16、308Z*=340问题D4无可行解第45页第四节 0-1型整数规划一、0-1变量的概念 0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。x=1 当决策取方案P时 0 当决策不取方案P时第46页现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj,此外，因种种原因，有3个附加条件：若选择项目1必须同时选择项目2，反之不一定；项目3和项目4中至少选择一个；第三，项目5、6、7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？二、0-1变量的实际应用1.制定相互排斥的计划例1：投资场所的选定第47页1 对项目 j 投
17、资0 对项目 j 不投资 xj=Max Z=cjxjajxjBx2 x1x3+x4 1x5+x6+x7=2xj=0或1（j=1,2,n）解：令j=1,.,n第48页2.相互排斥的约束条件问题例：集装箱运货（用车运或用船运）车运 体积船运 体积单位 重量单位 利润甲5 7 2 20乙4 3 5 10托运限制24 45 13两种货物各托运多少箱可以使利润最大？第49页Max Z=20 x1+10 x25x1+4x224+yM7x1+3x245+(1-y)M2x1+5x213x1,x20，y=0 或1x1,x2为整数y=1 船运 0 车运解：x1，x2 分别为甲乙两种货物托运的箱数第50页 产品资源
18、 资源量A 2 4 8 500B 2 3 4 300C 1 2 3 100单件可变费用4 5 6固定费用100 150 200单价8 10 123.固定费用问题 例：有三种资源被用于生产三种产品，资源量、产品单件可变费用、售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。第51页解：设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-100y
19、1-150y2-200y3第52页4.工件排序问题例：4台机床加工3件产品，产品i在机床j上的加工工时为aij产品1a11 a13 a14机床1 机床3 机床4产品2a21 a22 a24机床1 机床2 机床4产品3a32 a33 机床2 机床3制定加工方案，使最短的时间内加工完全部产品第53页解：设xi表示产品i在机床j上开始加工时间（1）同一产品在不同机床上的加工顺序约束产品1a11 a13 a14机床1 机床3 机床4产品2a21 a22 a24机床1 机床2 机床4产品3a32 a33 机床2 机床3产品1：x11+a11x13及 x13+a13x14产品2：x21+a21x22及 x
20、22+a22x24产品3：x32+a32x33第54页（2）每台机床对不同产品加工顺序约束产品1a11 a13 a14机床1 机床3 机床4产品2a21 a22 a24机床1 机床2 机床4产品3a32 a33 机床2 机床3机床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)第55页（3）产品2加工总时间约束产品1a11 a13 a14机床1
21、机床3 机床4产品2a21 a22 a24机床1 机床2 机床4产品3a32 a33 机床2 机床3x24+a24-x21 d第56页（4）目标函数的建立产品1a11 a13 a14机床1 机床3 机床4产品2a21 a22 a24机床1 机床2 机床4产品3a32 a33 机床2 机床3W=max(x14+a14,x24+a24,x33+a33)设全部产品加工完毕的结束时间为W目标函数Z为第57页模型为：x11+a11x13x13+a13x14x21+a21x22 x22+a22x24x32+a32x33x11+a11x21+My1x21+a21x11+M(1-y1)x22+a22x32+M
22、y2x32+a32x22+M(1-y2)x13+a13x33+My3x33+a33x13+M(1-y3)x14+a14x24+My4x24+a24x14+M(1-y4)x24+a24-x21 d第58页三、0-1型整数规划的解法 隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。过滤条件：目标函数值优于计算过的可行解目标函数值。第59页(x1,x2,x3)Z 值约束条件 过滤条件(0,0,0)0 Z0（0,0,1)5 Z5（0,1,0)-2（0,1,1)3（1,0,0)3（1,0,1)8 Z8（1,1,0)1（1,1,1)6m
23、axZ=3X1-2X2+5X3X1+2X2-X3 2 X1+4X2+X3 4 X1+X2 3 4X2+X3 6 X1,X2,X3=0 或 1 例1第60页X Z 值约束条件 过滤条件(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,0,1,1)(0,1,0,0)(1,1,1,1)例2目标函数有大到小排列第61页第五节 指派问题 一、典型的指派问题 某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。第62页 例：有一份中文说明书，需译成英、日、德、俄四种文字，分
24、别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？第63页 任务人员E J G R甲2 15 13 4乙10 4 14 15丙9 14 16 13丁7 8 11 9 例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？第64页指派问题的标准形式 n个人，n件事，第i个人做第j件事的费用为cij,确定人和事之间一一对应的指派方案，使完成n件事的总费用最小。
25、效率矩阵或系数矩阵C=(cij)nn=c11 c12 c1n c21 c22 c2n cn1 cn1 cnn 第65页C=(cij)nn=2 15 13 410 4 14 159 14 16 137 8 11 9第66页二、标准指派问题的数学模型xij=1 指派第 i 个人做第 j 件事0 不指派第 i 个人做第 j 件事j=1,2,ni=1,2,nxij=1或0第67页 解矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。例：X=(xij)44=0 1 0 00 0 0 11 0 0 00 0 1 0第68页三、匈牙利解法（1）关键性质：若从指派问题的系数矩阵(cij)nn的某行或某列各元素中分别减一个常数k,得到的新矩阵与原矩阵有相同的最优解。C=(cij)nn=2 15 13 410 4 14 159 14 16 137 8 11 9第69页C=(cij)nn=2 15 13 410 4 14 159 14 16 137 8 11 9第70页C=(cij)nn=0 13 7 06 0 6 90 5 3 20 1 0 0匈牙利法的步骤1.变换系数矩阵第71页C=(cij)nn=0 13 7 06 0 6 90 5 3 20 1 0 0匈牙利法的步骤2.寻找独立“0”元素若有n个，计算结束若少于n个，转3