《0-1型整数规划课件.ppt》由会员分享，可在线阅读，更多相关《0-1型整数规划课件.ppt（48页珍藏版）》请在三一办公上搜索。
1、第四节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元
2、。问应选择哪个点可使年利润最大？,0-1规划的实际问题：,建模如下：,st.,2相互排斥的约束条件,如果有m个互相排斥的约束条件（=型）：,为了保证这个约束条件只有一个起作用，我们引入m个01变量 和一个充分大的常数M，而下面这一组m+1个约束条件,符合要求,第四节0-1整数规划,2、相互排斥的约束条件例：本章例1中，关于货运的体积限制为5x1+4x224(车)。今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为7x1+3x245(船)。（这两条件是互相排斥的）,例1.某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如右表所
3、示。问两种货物各托运多少箱，可使获得利润为最大？,解：设甲、乙两种货物的托运箱数分别为x1,x2。,设变量y表示运货的方式，当y为1时，用车运，y为0时，用船运。,+(1-y)M,+yM,互相排斥的约束条件：用车运的体积约束用船运的体积约束,第五章：0-1整数规划,例：某公司有5个项目列入投资计划，各项目的投资额和期望的投资收益见下表：,该公司只有600万元可用于投资，由于技术上的原因，投资受到以下约束：1.在项目1、2和3中必须只有一项被选中；2.在项目3和4中只能选中一项；3.项目5选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，是投资收益最大？,只有600万元可用于
4、投资,在项目1、2和3中必须只有一项被选中,在项目3和4中只能选中一项,项目5选中的前提是项目1必须被选中,3 固定费用问题,例 有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用如表。要求制定一个生产计划，使总收益最大,解：设xj是第j种产品的产量，j=1，2，3；再设,若生产第j种产品（即xj0）,若不生产第j种产品（即xj=0）,j=1，2，3,则问题的模型为,且为整数，j=1，2，3,j=1，2，3,应用举例,例A 东方大学计算机实验室聘用4名大学生（代号1、2、3、4）和2名研究生（代号5、6）值班答疑。已知每人从周一至周五每天最多可
5、安排的值班时间及每人每h值班的报酬如下表,该实验室开放时间是上午8点至晚上10点，开放时间内须有且仅需一名学生值班，规定大学生每周值班不少于8h，研究生每周不少于7h，每名学生每周值班不超过3次，每次值班不少于2h，每天安排值班的学生不超过3人且其中必须有一名研究生，试为该实验室安排一张人员的值班表，使总支付的报酬最少,解：设xij为学生i在周j的值班时间，,安排学生i在周j值班,否则,用aij代表学生i在周j最多可安排的值班时间，ci为学生i的每h的报酬，则其数学模型为,不超过可安排时间,大学生每周值班不少于8h,研究生每周值班不少于7h,实验室每天开放14h,每名学生一周值班不超过3次,每
6、天值班不超过3人,每天有一名研究生值班,最优结果为总支付报酬每周727.5元值班方案为：,例B 清远市下设八个区，下表给出救护车从一个区至另一个区的车程时间（min）该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内，是为该市提供决策建议：至少建多少个救护中心，建于何处？,解：先根据表整理出若救护中心建于该区时，救护车程8min内所能覆盖的区，见于下表,设,该区设救护中心,否则,列出数学模型如下,求解的结果为x1=1，x6=1，即至少在1、6两个区各设一救护中心,第四节0-1整数规划,二、0-1整数规划的解法,隐枚举法：只检查变量取值的组合的一部分的方法。,(0,0,0),0,Z
7、0,(0,0,1),5,Z5,(0,1,0),-2,(0,1,1),3,(1,0,0),3,Z8,(1,0,1),(1,1,0),8,1,(1,1,1),6,按目标函数中各变量系数的大小重新排列各变量最大化问题：由小到大最小化问题：由大到小,解法二：重新排列xj的顺序(系数递减),0-1型整数规划计算表,目标函数z 3x12x25x3 5x33x12x2 最大值的上限是8，第二大的值是55x33x12x28,隐枚举法：共计算5次(均满足约束条件)。（最优解为1，0，1，最优值8）,可根据计算逐渐改变过滤条件(该例因最大值的点满足其他四个约束，即找到最大化问题的最好的整数解。就不需验证计算第二大
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,最小值0对应的点不满足 约束，改变过滤条件，再验证计算次小值2对应的点满足 约束，即找到最小化问题的最好的整数解。,逐渐改变过滤条件,第五节指派问题,一、什么是指派问题,某单位需完成任务n项任务，恰好有n个人可承担这些任务，由于每人的专长不同，各人完成不同任务效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。这类
9、问题称为指派问题(分派问题、分配问题),人,任务,cij表示第i个人完成第j项任务的效率。,第五节指派问题,二、指派问题的数学模型,=(Cij),人,任务,解：设,例：某单位现在、四项工作需完成，现在甲、乙、丙、丁四个人均可完成这四项任务。每人完成各项任务所用的时间如右表所示，问应指派何人去完成何项任务，使所需时间最少？,A,B,C,D,任务,人员,满足所有约束条件的可行解xij也可写成表格或矩阵形式，称为解矩阵,(xij)=,就是上例的一个可行解矩阵,第五节指派问题,(cij)=,第五节指派问题,指派问题数学模型的性质：,若从指派问题的系数的系数矩阵（cij）的一行（列）各元素中分别减去该行
10、（列）的最小元素，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。,独立的0元素：位于不同行不同列的0元素称为独立的0元素。,结论：若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。将其代入目标函数中得到zk=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了问题的最优解。,第五节指派问题,三、指派问题的解法（匈牙利法）,第一步:使指派问题的系数矩阵经变换，在各行各列都出现元素。,（）从系数矩阵的每行元素减去该行的最小元素；（）再从所得系数矩阵的每列元素中
11、减去该列的最小元素。,min,min,经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，若能找出，就以这些独立的0元素对应解矩阵中的元素为1，其作为0，这就得到最优解。找独立0元素的步骤如下：,第二步：进行试指派，以寻求最优解。,第五节指派问题,（3）反复(1),(2)两步，直到所有0元素都被圈出和划掉为止。,（4）若各行各列均有多于2个的0元素未被圈出或划掉，中任选其中任意一个0元素加圈。,（5）若元素的数目m等于矩阵的阶数n，那么指派问题的最优解已得到，若mn，则转入下一步。,min,第五节指派问题,第五节指派问题,第三步：作最少的直线覆盖所有0元素，以确定该系数
12、矩阵中能找到最多的独立0元素数。,（5）对没有打号的行画一横线，有打号的列画一纵线，这就得到覆盖所有0元素的最少直线。,（1）对没有的行打号；,（2）对已打号的行中所有含划0元素的列打号；,（3）再对打有号的列中含元素的行打号；,（4）重复(2)、(3)直到得不出新的打号的行、列为止；,第五节指派问题,第四步：对第三步所得矩阵进行变换，目的是增加0元素。,在没有被直线覆盖的部分中找出最小元素。然后在打行各元素中都减去该最小元素，而在打列的各元素都加上该最小元素（以保证原来的0元素不变）。这样得到新系数矩阵。重复第二步。,独立0元素的个数等于效率矩阵的阶数得到了最优解,最优解矩阵为：,第五节指派
13、问题,练习：有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：,工作,工人,解：用匈牙利法求解过程如下：,min,min,1,第五节指派问题,第五节指派问题,四、非标准形式的指派问题,1、最大化指派问题2、人数和事数不等的指派问题3、一个人可做几件事的指派问题4、某事一定不能由某人做的指派问题,第五节指派问题,1、求最大化的指派问题,令bij=M-cij其中：M是足够大的常数（cij中最大元素）用匈牙利法求解（bij）即可。所得最小解就是原问题的最大解。,第五节指派问题,2、人数和任务数不等的指派问题,若人少任务多，则添上一些虚拟的“人”。这些虚拟的“人”完成各任务的费
14、用系数可取0，理解为这些费用实际上不会发生。若人多任务少，则添上一些虚拟的“任务”，这些虚拟的“任务”由各人完成的费用系数同样也取0。,第五节指派问题,3、一个人可以完成几项任务的指派问题,若某个人可完成几项任务，则可将人化作相同的几个“人”，来接受指派，这几个“人”完成同一项任务的费用系数都一样。,4、某项任务一定不能由某人完成的指派问题,若某项任务一定不能由某个人完成，则可将相应的费用系数取作足够大的数M。,例：分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方
15、案。,第五节指派问题,第六节应用举例,1、m约束条件中只有k个起作用,设m个约束条件可表示为：,定义,又M为任意大的正数，得,第六节应用举例,定义,第六节应用举例,3、两组条件中满足其中一组,若x14，则x21；否则（即x14）,x23,又M为任意大正数，则问题可表达为：,第六节应用举例,4、用以表示固定费用的函数,生产费用函数：,引入变量yj,复习题,一、判断下列说法是否正确,1、整数规划的目标函数值一般优于其相应的线性规划问题（松弛问题）的解的目标函数值。2、用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。3、用分枝定界法求解一个极大化的整数
16、规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较、剪枝。4、用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。,复习题,一、判断下列说法是否正确,5、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。6、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。7、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。8、求解0-1规划的隐枚举法是分枝定界法的特例。9、分枝定界法在需要分枝时必须满足：一是分枝后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。,复习题,2、用匈牙利法求解最小化的指派问题，效率矩阵如下：,min,复习题,3、应用建模：教材128页4.16,
