0-1型整数规划课件.ppt

第四节第四节0-1整数规划整数规划决策变量只能取决策变量只能取0或或1的整数规划，叫做的整数规划，叫做0-1整数规整数规划。决策变量称为划。决策变量称为0-1变量变量(二进制变量、逻辑变量二进制变量、逻辑变量)。0-1变量作为逻辑变量，常被用来表示系统是否处于某变量作为逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。个特定状态，或者决策时是否取某个特定方案。一、什么是一、什么是0-1整数规划整数规划第四节第四节0-1整数规划整数规划1、投资场所的选定相互排斥的计划、投资场所的选定相互排斥的计划例：某公司拟在市东、西、南三区建立门市部，拟议中有例：某公司拟在市东、西、南三区建立门市部，拟议中有7个个位置位置Ai(i=1,2,7)可供选择。规定可供选择。规定在东区，由在东区，由A1，A2，A3三个点中至多选两个；三个点中至多选两个；在西区，由在西区，由A4，A5两个点中至少选一个；两个点中至少选一个；在南区，由在南区，由A6，A7两个点中至少选一个。两个点中至少选一个。如选用如选用Ai点，设备投资估计为点，设备投资估计为bi元，每年可获利润估计为元，每年可获利润估计为ci元，元，但投资总额不能超过但投资总额不能超过B元。问应选择哪个点可使年利润最大？元。问应选择哪个点可使年利润最大？0-1规划的实际问题：规划的实际问题：建模如下：建模如下：st.2 2相互排斥的约束条件相互排斥的约束条件 如果有m个互相排斥的约束条件（0）若不生产第j种产品（即xj=0）j=1，2，3则问题的模型为且为整数，j=1，2，3j=1，2，3应用举例例A 东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表学生代号报酬（元/h)每天最多可安排的值班时间周一 周二 周三 周四 周五12345610109.99.810.811.36 0 6 0 770 6 0 6 04 8 3 0 55 5 6 0 43 0 4 8 040 6 0 6 3该实验室开放时间是上午8点至晚上10点，开放时间内须有且仅需一名学生值班，规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人且其中必须有一名研究生，试为该实验室安排一张人员的值班表，使总支付的报酬最少解：设xij为学生i在周j的值班时间，安排学生i在周j值班否则用aij代表学生i在周j最多可安排的值班时间，ci为学生i的每h的报酬，则其数学模型为不超过可安排时间大学生每周值班不少于8h研究生每周值班不少于7h实验室每天开放14h每名学生一周值班不超过3次每天值班不超过3人每天有一名研究生值班学生代号一 二 三 四 五1234566 6 77 4 68 8 55 63 2 24 2 6 3 最优结果为总支付报酬每周727.5元值班方案为：例B 清远市下设八个区，下表给出救护车从一个区至另一个区的车程时间（min）该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内，是为该市提供决策建议：至少建多少个救护中心，建于何处？至从 2 3 4 5 6 7 8 12345678 9 11 13 14 8 159 10 12 13 11 17 1410 7 7 8 12 1011 8 7 10 9 12 8 14 1613 10 714 12 解：先根据表整理出若救护中心建于该区时，救护车程8min内所能覆盖的区，见于下表救护中心设于该区救护车程8min内所能覆盖的区123456781 2 72 23 4 5 643 4 5 653 4 5 663 4 5 6 81 726 8设 该区设救护中心否则列出数学模型如下求解的结果为x1=1，x6=1，即至少在1、6两个区各设一救护中心第四节第四节0-1整数规划整数规划二、二、0-1整数规划的解法整数规划的解法隐枚举法：只检查变量取值的组合的一部分的方法。隐枚举法：只检查变量取值的组合的一部分的方法。(x1,x2,x3)Z值abcd过滤条件过滤条件(0,0,0)0Z0(0,0,1)5Z5(0,1,0)-2(0,1,1)3(1,0,0)3Z8(1,0,1)(1,1,0)81(1,1,1)6按目标函数中各变量系数的大小重新排列各变量按目标函数中各变量系数的大小重新排列各变量最大化问题：由小到大最大化问题：由小到大最小化问题：由大到小最小化问题：由大到小解法二：重新排列xj的顺序(系数递减)0-1型整数规划计算表目标函数z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是55x33x12x28 点(x3,x1,x2)约束条件满足条件?是否z值(1,1,0)8 8隐枚举法：共计算5次(均满足约束条件)。（最优解为1，0，1，最优值8）可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大值的点是否满足约束条件)例：求解下面的0-1型整数规划 解：按递增序列排列 因为xi取0或1，最小下界点为(0,0,0)，z值为0；其次为(0,0,1)点，z值为2；(0,1,0)点，z值为3；0-1型整数规划计算表最优解为：(0,0,1)最优值为：2点(x3,x2,x1)约束条件满足条件?是否z值过滤条件(0,0,0)0(1,0,1)22最小值0对应的点不满足 约束，改变过滤条件，再验证计算次小值2对应的点满足 约束，即找到最小化问题的最好的整数解。逐渐改变过滤条件第五节指派问题第五节指派问题一、什么是指派问题一、什么是指派问题某单位需完成任务某单位需完成任务n项任务，恰好有项任务，恰好有n个人可承担个人可承担这些任务，由于每人的专长不同，各人完成不同任务这些任务，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成使完成n项任务的总效率最高。这类问题称为项任务的总效率最高。这类问题称为指派问题指派问题(分派问题、分配问题分派问题、分配问题)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任务任务cij表示第表示第i个人完成第个人完成第j项项任务的效率。任务的效率。第五节指派问题第五节指派问题二、指派问题的数学模型二、指派问题的数学模型=(Cij)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人人任务任务解：设解：设例：某单位现在、例：某单位现在、四项工作需完成，、四项工作需完成，现在甲、乙、丙、丁四个现在甲、乙、丙、丁四个人均可完成这四项任务。人均可完成这四项任务。每人完成各项任务所用的每人完成各项任务所用的时间如右表所示，问应指时间如右表所示，问应指派何人去完成何项任务，派何人去完成何项任务，使所需时间最少？使所需时间最少？甲甲215134乙乙1041415丙丙9141613丁丁78119ABCD任务任务人员人员满足所有约束条件的可行解满足所有约束条件的可行解xij也可也可写成表格或矩阵形式，称为写成表格或矩阵形式，称为解矩阵解矩阵(xij)=就是上例的就是上例的一个可行解一个可行解矩阵矩阵第五节指派问题第五节指派问题(cij)=第五节指派问题第五节指派问题指派问题数学模型的性质：指派问题数学模型的性质：若从指派问题的系数的系数矩阵（若从指派问题的系数的系数矩阵（cij）的一行（列）各元）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（素中分别减去该行（列）的最小元素，得到新矩阵（bij），那），那么以（么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。优解相同。独立的独立的0元素：元素：位于不同行不同列的位于不同行不同列的0元素称为独立的元素称为独立的0元素。元素。结论：结论：若能在系数矩阵若能在系数矩阵(bij)中找出中找出n个独立的个独立的0元素；则令解矩阵元素；则令解矩阵(xij)中对应这中对应这n个独立的个独立的0元素取值为元素取值为1，其它元素取值为，其它元素取值为0。将。将其代入目标函数中得到其代入目标函数中得到zk=0，它一定是最小。这就是以，它一定是最小。这就是以(bij)为为系数矩阵的指派问题的最优解。也就得到了问题的最优解。系数矩阵的指派问题的最优解。也就得到了问题的最优解。第五节指派问题第五节指派问题三、指派问题的解法（匈牙利法）三、指派问题的解法（匈牙利法）第一步第一步:使指派问题的系数矩阵经变换，在各行各列都出现元素。使指派问题的系数矩阵经变换，在各行各列都出现元素。（）从系数矩阵的每行元素减去该行的最小元素；（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素中减去该列的最小元素。（）再从所得系数矩阵的每列元素中减去该列的最小元素。2497min24min经第一步变换后，系数矩阵中每行每列都已有了经第一步变换后，系数矩阵中每行每列都已有了0元素；元素；只需找出只需找出n个独立的个独立的0元素，若能找出，就以这些独立的元素，若能找出，就以这些独立的0元素元素对应解矩阵中的元素为对应解矩阵中的元素为1，其作为，其作为0，这就得到最优解。找独，这就得到最优解。找独立立0元素的步骤如下：元素的步骤如下：第二步：进行试指派，以寻求最优解。第二步：进行试指派，以寻求最优解。第五节指派问题第五节指派问题0（1）从只有一个从只有一个0元素的行开始，给这个元素的行开始，给这个0元素加圈，记作元素加圈，记作.然然后再划去后再划去所在列的其它所在列的其它0元素，记作元素，记作 。（2）给只有一个给只有一个0元素的列的元素的列的0元素加圈，记作元素加圈，记作；然后划去；然后划去所在行的所在行的0元素，记作元素，记作 。0（3）反复反复(1),(2)两步，直到所有两步，直到所有0元素都被圈出和划掉为止。元素都被圈出和划掉为止。（4）若各行各列均有多于若各行各列均有多于2个的个的0元素未被圈出或划掉，中任选元素未被圈出或划掉，中任选其中任意一个其中任意一个0元素加圈。元素加圈。（5）若若元素的数目元素的数目m等于矩阵的阶数等于矩阵的阶数n，那么指派问题的最优，那么指派问题的最优解已得到，若解已得到，若m4）,x23又又M为任意大为任意大正数，则问题正数，则问题可表达为：可表达为：第六节应用举例第六节应用举例4、用以表示固定费用的函数、用以表示固定费用的函数生产费用函数：生产费用函数：引入变量引入变量yj复习题复习题一、判断下列说法是否正确一、判断下列说法是否正确1、整数规划的目标函数值一般优于其相应的线性规、整数规划的目标函数值一般优于其相应的线性规划问题（松弛问题）的解的目标函数值。划问题（松弛问题）的解的目标函数值。2、用分枝定界法求解一个极大化的整数规划问题时，、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的任何一个可行解的目标函数值是该问题目标函数值的下界。下界。3、用分枝定界法求解一个极大化的整数规划问题，、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较、剪枝。下界值，再进行比较、剪枝。4、用割平面法求解整数规划时，构造的割平面有可、用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。能切去一些不属于最优解的整数解。复习题复习题一、判断下列说法是否正确一、判断下列说法是否正确5、用割平面法求解纯整数规划时，要求包括松弛变、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。量在内的全部变量必须取整数值。6、指派问题效率矩阵的每个元素都乘上同一常数、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。，将不影响最优指派方案。7、指派问题数学模型的形式同运输问题十分相似，、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。故也可以用表上作业法求解。8、求解、求解0-1规划的隐枚举法是分枝定界法的特例。规划的隐枚举法是分枝定界法的特例。9、分枝定界法在需要分枝时必须满足：一是分枝后、分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。必须覆盖原问题的解。复习题复习题2、用匈牙利法求解最小化的指派问题，效率矩阵如下：、用匈牙利法求解最小化的指派问题，效率矩阵如下：min76746复习题复习题3、应用建模：教材、应用建模：教材128页页4.16