5.4 0-1 整数规划

上传人:gmk****56 文档编号:251171862 上传时间:2024-11-06 格式:PPT 页数:32 大小:598.50KB
返回 下载 相关 举报
5.4 0-1 整数规划_第1页
第1页 / 共32页
5.4 0-1 整数规划_第2页
第2页 / 共32页
5.4 0-1 整数规划_第3页
第3页 / 共32页
点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四节 0-1型整数规划,本节内容的安排,引入0-1变量的实际问题,0-1型整数规划的解法,如果线性规划中的所有决策变量的取值只能取,0,、,1,,,则这类线性规划问题是一种特殊的整数规划问题,称之为,0-1,规划,,把只能取,0,或,1,值的变量称为,0-1,变量,。,0-1,变量是一种逻辑变量。,在某些特殊的实际问题中,我们只需做是非选择,,如:是否采纳某方案,某任务是否可交给某人承担,,集装箱是否装入某货物等,,对于这类问题的变量可设置简化为,0,或,1,,,x,=,1,是,0,否,决策变量只取,0,和,1,的线性规划问题,其,数学模型,如下:,其中,x,j,为,0-1,变量,也称二进制变量,逻辑变量。,x,j,仅取值,0,或,1,这个条件可由下述约束条件所代替。,x,j,1,x,j,0,,整数,它和一般整数线性规划的约束条件形式是一致的。,作用:,在实际问题中,如果引入,0-1,变量,,就可以把有各种情况需要分别讨论的,线性规划问题统一在一个问题中讨论了。,在本节我们先介绍引入,0-1,变量的,实际问题,:,投资场所(项目)的选定,相互排斥的约束条件,关于固定费用的问题,然后,再研究,0-1,规划问题的一般解法,-,隐枚举法,。,一,.,引入,0-1,变量的实际问题,1.,投资场所的选定,相互排斥的计划,例,4:,某公司拟在市东、西、南三区建立门市部。,拟议中有,7,个位置,(,点,)A,i,(i=1,,,2,,,,,7),可供选择。,规定:,在东区,由,A,1,,,A,2,,,A,3,三个点中至多选两个;,在西区,由,A,4,,,A,5,两个点中至少选一个;,在南区,由,A,6,,,A,7,两个点中至少选一个。,如选用,A,i,点,设备投资估计为,b,i,元,,每年可获利润估计,为,c,i,元,,但投资总额不能超过,B,元。,问应选择哪几个点可使年利润为最大,?,解题时先引入,0-1,变量,x,i,(=1,2,,,,,7),于是问题可列成:,在东区,由,A,1,,,A,2,,,A,3,三个点中至多选两个;,在西区,由,A,4,,,A,5,两个点中至少选一个;,在南区,由,A,6,,,A,7,两个点中至少选一个。,2.,相互排斥的约束条件,在本章开始的例,1(P114),中,关于运货的,体积限制,为,5x,1,+4x,2,24,(5-9),今设运货有车运和船运两种方式,,上面的条件系用,车运时,的限制条件,,如用,船运,时关于体积的限制条件为,7x,1,+3x,2,45,(5-10),这两条件是互相排斥的。,为了统一在一个问题中,引入,0-1,变量,y,,令,(,1,)两个约束条件中只有一个起作用,车运,船运,于是,(5-9),式和,(5-10),式可由下述的条件,(5-11),式和,(5-12),式 来代替:,5x,1,+4x,2,24+yM (5-11)7x,1,+3x,2,45+(1-y)M (5-12),其中,M,是充分大的数,y,是,0-1,变量。,可以验证,当,y=0,时,,(5-11),式就是,(5-9),式,,而,(5-12),式自然成立,因而是多余的。,当,y=1,时,(5-12),式就是,(5-10),式,,而,(5-11),式是多余的。,引入的变量,y,不必出现在目标函数内,,即认为在目标函数式内,y,的系数为,0,。,5x,1,+4x,2,24,(5-9 ),车运,7x,1,+3x,2,45,(5-10),船运,为了保证这,m,个约束条件只有一个起作用,,引入,m,个,0-1,变量,y,i,(i,=1,2,,,m),和一个充分大的常数,M,。,(,2,)在,m,个互相排斥的约束条件,(,型,),:,i1,x,1,+,i2,x,2,+,+,in,x,n,b,i,,,i=1,,,2,,,m,中只有一个起作用,定义逻辑变量,y,i,:,M,为任意大 的正数,则有下式成立:,i1,x,+,i2,x,2,+,in,x,n,b,i,+y,i,M,,,i=1,2,,,m (5-13),y,1,+y,2,+,y,m,=m-1 (5-14),这是因为,由于,(5-14),式,,m,个,y,i,中只有一个能取,0,值,,设,y,i,*=0,,代入,(5-13),式,,就只有,i=i*,的约束条件起作用,,而别的式子都是多余的。,i1,x,+,i2,x,2,+,in,x,n,b,i,+y,i,M,,,i=1,2,,,m (5-13),y,1,+y,2,+,y,m,=m-1 (5-14),例:,利用,0 1,变量对下列各题分别表示成,一般线性约束条件,(,a,),x,1,+x,2,2,或,2,x,1,+3x,2,5;,解:,(,b,)变量,x,只能取值,0,、,3,、,5,或,7,中的一个,;,(,c,)变量,x,或等于,0,,或,50;,(,d,)若,x,1,2,,则,x,2,1,,否则,x,2,4;,(,e,)以下四个约束条件中至少满足两个,x,1,+x,2,5,,,x,1,2,,,x,3,2,,,x,3,+x,4,6 .,3.,关于固定费用的问题,在讨论线性规划时,,有些问题是要求使成本为最小。,这时总假定固定成本为常数,,并在线性规划的模型中不必明显列出。,但有些固定费用,(,固定成本,),的问题,不能用一般线性规划来描述,,但可改变为混合整数线性规划来解决,见下例。,例,5:,某工厂为了生产某种产品,,有几种不同的生产 方式可供选择,,如选定投资高的生产方式,(,选购自动化程度高的设备,),,,由于产量大,因而分配到每件产品的变动成本就降低;,反之,如选定投资低的生产方式,,将来分配到每件产品的变动成本可能增加,,所以必须全面考虑。,今设有三种方式可供选择,令,x,j,表示采用第,j,种方式时的产量;,c,j,表示采用第,j,种方式时每件产品的变动成本;,k,j,表示采用第,j,种方式时的固定成本。,为了说明成本的特点,暂不考虑其他约束条件。,问题的目标是使所有产品的总生产费用为最小,.,解:,采用各种生产方式的总成本分别为:,在构成目标函数时,为了统一在一个问题中讨论,,现引入,0-1,变量,y,j,,令,于是目标函数,min z=(k,1,y,1,+c,1,x,1,)+(k,2,y,2,+c,2,x,2,)+(k,3,y,3,+c,3,x,3,),(5-15),式这个规定可由以下,3,个线性约束条件表示:,x,j,y,j,M,,,j=1,2,3 (5-16),其中,M,是个充分大的常数。,(5-16),式说明,当,x,j,0,时,y,j,必须为,1,;,当,x,j,=0,时只有,y,j,为,0,时才有意义,,所以,(5-16),式完全可以代替,(5-15),式,二,0-1,型整数规划的一般解法,-,隐枚举法,解,0-1,型整数规划最容易想到的方法,,和一般整数线性规划的情形一样,就是穷举法,,即检查变量取值为,0,或,1,的每一种组合,,比较目标函数值以求得最优解,,这就需要检查变量取值的,2,n,个组合。,对于变量个数,n,较大,(,例如,n,10),,,这几乎是不可能的。,而隐枚举法就是在此基础上改进的,,通过加入一定的条件,就能较快的求得最优解。,只检查变量取值的组合的一部分,,就能求到问题的最优解,,这样的方法称为,隐枚举法,(implicit enumeration),,,分枝定界法也是一种隐枚举法。,其,解题,关键是寻找可行解,产生过滤条件,。,过滤条件:,是满足目标函数值优于计算过的可行解目标函数值的约束条件。,当然,对有些问题隐枚举法并不适用,,所以有时穷举法还是必要的。,下面举例说明求解,0-1,型整数规划的隐枚举法,例,6:,目标函数,max z=3x,1,-2x,2,+5x,3,约束条件:,x,1,+2x,2,-x,3,2 ,x,1,+4x,2,+x,3,4 (5-17),x,1,+x,2,3 ,4x,2,+x,3,6 ,x,1,,,x,2,,,x,3,=0,或,1,解题时先通过试探的方法找一个可行解,容易看出,(x,1,,,x,2,,,x,3,)=(1,,,0,,,0),就是合于条件的,,算出相应的目标函数值,z=3,。,我们在求最优解时,,对于极大化问题,当然希望,z3,,,于是增加一个约束条件:,3x,1,-2x,2,+5x,3,3,后加的条件称为,过滤的条件,(filtering constraint),。,这样,原问题的线性约束条件就变成,5,个。,用全部枚举的方法,,3,个变量共有,2,3,=8,个解,,原来,4,个约束条件,共需,32,次运算。,现在增加了过滤条件,,如按下述方法进行,就可减少运算次数。,将,5,个约束条件按顺序排好,(,表,5-5),,,对每个解,依次代入约束条件左侧,求出数值,,看是否适合不等式条件,,如某一条件不适合,同行以下各条件就不必再检查,,因而就减少了运算次数。,所以改进过滤条件,用,3x,1,-2x,2,+5x,3,5 ,代替,,继续进行。,在计算过程中,若遇到,z,值已超过条件右边的值,应改变条件,使右边值为迄今为止最大者,然后继续作。,例如,当检查点,(0,,,0,,,1),时,因,z=5(,3),,,这种对过滤条件的改进,更可以减少计算量。,再改进过滤条件,用,3x,1,-2x,2,+5x,3,8 ,代替,,,再继续进行。,至此,,z,值已不能改进,即得到最优解,解答如前,但计算已简化。,本例计算过程实际只作,16,次运算。,即求得最优解,(x,1,,,x,2,,,x,3,)=(1,,,0,,,1),max z=8,注意:,一般常重新排列,x,i,的顺序使目标函数中,x,i,的系数 是递增,(,不减,),的,在上例中,,改写,z=3x,1,-2x,2,+5x,3,=-2x,2,+3x,1,+5x,3,因为,-2,,,3,,,5,是递增的,变量,(x,2,,,x,1,,,x,3,),也按下述顺序取值:,(0,,,0,,,0),,,(0,,,0,,,1),,,(0,,,1,,,0),,,(0,,,1,,,1),,,,,这样,最优解容易比较早的发现。,再结合过滤条件的改进,更可使计算简化,步骤,:,(1),、用试探法,求出一个可行解,以它的目标值作为当前最好值,Z,0,(2),、,增加过滤条件,Z,Z,0,(3),、将,x,i,按,c,i,由小,大排列。最小化问题反之。,max,Z,=3x,1,-2x,2,+5x,3,x,1,+2x,2,-,x,3,2,x,1,+4x,2,+x,3,4,x,1,+x,2,3,4x,2,+x,3,6,x,1,x,2,x,3,为,0,或,1,解:,1.,观察得解,(x,1,x,2,x,3,)=(1,0,0),,,Z,0,=3,2.,过滤条件,:,3x,1,-2x,2,+5x,3,3,3.,将,(x,1,x,2,x,3,),(x,2,x,1,x,3,),点,(,x,2,x,1,x,3,),目标值,Z,0,当前最好值,(0,0,0,)0 5,(0,1,0)3 8,(1,0,0,)-2 ,(1,0,1)3 ,(1,1,0)1 ,(1,1,1,)6 ,最优解,x=(1,0,1),T,Z=8,max,Z,=-2x,2,+3x,1,+5x,3,x,1,+2x,2,-,x,3,2,x,1,+4x,2,+x,3,4,x,1,+x,2,3,4x,2,+x,3,6,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 建筑环境 > 建筑资料


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!