《整数规划(IP)问题.ppt》由会员分享，可在线阅读，更多相关《整数规划(IP)问题.ppt（49页珍藏版）》请在三一办公上搜索。
1、整数规划(IP)问题,一、定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。二、整数规划(IP)分类 变量全限制为整数的，称纯（完全）整数规划。变量部分限制为整数的，称混合整数规划。要求决策变量仅取0或1,称为0-1规划问题.,整数规划问题的提出,例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：,问两种货物各托运多少箱，可使获得的利润为最大？,解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：,(ILP),称为(ILP)的伴随规划,2、整数规划一般形式,（1）求解方法方面,3、与L
2、P问题的区别,在例1中，,此IP问题的最优解(值)为：,求ILP问题的伴随规划的最优解(值)为：,例2 做图分析例1的最优解(直观),x1,x2,4,8,4,0,Z=96,1,2,3,5,6,7,3,1,2,5x1+4x2=24,2x1+5x2=13,C(4.8,0),Z=90(最优解),B(4,1),Z=80,整数规划特点 伴随规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况；原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。整数规划无可行解。有可行解（当然就存在最优解），但最优解值变差。,例 原线性规划为：min x1+x2 s.t.2x1+4x2=5，x1 0
3、x2 0 其最优实数解为：x1=0，x2=5/4，最优值=5/4。若限制整数则可行域为空集.例 原线性规划为：min x1+x2 s.t.2x1+4x2=6 x1 0 x2 0 其最优实数解为：x1=0，x2=3/2，最优值=3/2。若限制整数则得：x1=1，x2=1，最优值=2。,四、求解方法分类：1 割平面法主要求解纯整数线性规划 2 分枝定界法可求纯或混合整数线性规划 3 隐枚举法求解“01”整数规划：过滤隐枚举法；分枝隐枚举法 4 匈牙利法解决指派问题（“01”规划特殊情形）。5蒙特卡洛法求解各种类型规划。,第二节 分枝定界法,一、几何解释,适用范围：纯整数规划问题 0-1规划问题混合
4、整数规划问题,解：图解法。,x1,x2,0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9x1+7x2=56,7x1+20 x2=70,B,C,问题B1Z1=349x1=4.00 x2=2.10,问题B2Z2=341x1=5.00 x2=1.57,x1x(0),x1x(0)+1,Z=40 x1+90 x2,例:求解下列整数规划问题,(A0)的伴随规划为:,1.计算原问题(A0)的目标函数值的初始上界,注1:若(B0)无可行解,则(A0)也无可行解,停止计算.注2:若(B0)的最优解满足整数条件,则该最优解也 是(B0)的最优解,停止计算.注3:若(B0)无界,则(
5、A0)也无界,停止计算.,3.增加约束条件将原问题分枝,作出问题A1,A2的伴随规划B1,B2并将同一问题分解出的两个分枝问题称为”一对分枝”.,4.分别求解一对分枝（伴随规划）,（）无可行解：说明该枝情况已查明，不需要再继续分枝，称该分枝为“树叶”,（）得到整数最优解：说明该枝情况也已查明，不需要再继续分枝，称该分枝为“树叶”,（）得到非整数解：,树叶,树叶,6.结束准则,例:求解下列整数规划问题,(A0)的伴随规划为:,问题B0 x1=5.6 x2=4 f0=136,问题B1x1=5 x2=4 f1=130,问题B2x1=6 x2=3.75 f2=135,问题B3x1=7.2 x2=3 f
6、0=132,问题B4不可行,问题B5x1=7 x2=3 f0=130,问题B6x1=8 x2=2.5 f0=130,例:求解下列整数规划问题,(A0)的伴随规划为:,问题B0 x1=8.12 x2=3.13 f0=17.51,问题B1x1=8 x2=3.21 f1=17.62,问题B2x1=9 x2=3.13 f2=18.39,问题B3可行域空,问题B4x1=6.77 x2=4 f4=18.77,问题B5可行域空,问题B6x1=9 x2=4 f6=21,问题B8x1=7 x2=4 f8=19,问题B7x1=6 x2=4.5 f7=19.5,三、运算步骤,解伴随规划问题,满足要求?,结束,分枝,
7、Y,N,一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题,第三节 割平面法,一、一个符号的说明,适用范围：全整数规划问题,min z=cxS.t.Ax=b(1)x 0(2)xi为整数(3)不考虑xi为整数的条件，解(LP)问题，得最优单纯性表 x1 x2 xm xm+1 xn x1 1 0 0 y1m+1 y1n b1x2 0 1 0 y2m+1 y2n b2 xr 0 0 0 yrm+1 yrn brxm 0 0 1 ymm+1 ymn bm 0 CBB-1N-CN CBB-1b,1.若bi为整数，则x0=(b1,b2,bm,
8、0,0)T即为原整数规划问题的最优解.2.若存在br不是整数，考虑第r个方程:xr+j=m+1nyrjxj=br 写成xr+j=m+1nyrjxj+j=m+1nfrjxj=br+fr(4)其中 frj=yrj-yrj fr=br-br(4)写成j=m+1nfrjxj=fr+(br-xr-j=m+1nyrjxj)若br-xr-j=m+1nyrjxj-1 则j=m+1nfrjxj fr-10，矛盾。所以br-xr-j=m+1nyrjxj 0即-j=m+1nfrjxj-fr所以-j=m+1nfrjxj+yr=-fr yr 0为整数。,割平面方程(Gomory约束).,定理：整数规划 min z=cx
9、 S.t.Ax=b x 0 xi为整数 与 min z=cx S.t.Ax=b yr-j=m+1nfrjxj=-fr x，yr0 xi，yr为整数 等价。,例：用割平面法解下列整数规划问题,解：引入松弛变量，求解如下模型得最优表如下：x1 x2 x3 x4 x5x1 1 0 0 1/3 2/3 8/3x2 0 1 0-1/3 1/3 1/3x3 0 0 1-1/3 4/3 7/3 0 0 0 4/3 5/3 23/3,x1 x2 x3 x4 x5x1 1 0 0 1/3 2/3 8/3x2 0 1 0-1/3 1/3 1/3x3 0 0 1-1/3 4/3 7/3 0 0 0 4/3 5/3
10、23/3x1=8/3不是整数，取相应的方程x1+1/3 x4+2/3 x5=8/3=(2+2/3)得割平面方程y1-1/3 x4-2/3 x5=-2/3将割平面方程添入原最优表：,x1 x2 x3 x4 x5 y1x1 1 0 0 1/3 2/3 0 8/3x2 0 1 0-1/3 1/3 0 1/3x3 0 0 1-1/3 4/3 0 7/3y1 0 0 0-1/3-2/3 1-2/3 0 0 0 4/3 5/3 0 23/3x1 1 0 0 0 0 1 2x2 0 1 0-1/2 0 1/2 0 x3 0 0 1-1 0 2 1x5 0 0 0 1/2 1-3/2 1 0 0 0 1/2
11、0 5/2 6,-2/3,x1-2x2=2,x1+x2=3,x1+2x2=1,x1=2,注1：通常取fr=maxfi|1 i m，以 yr-j=m+1nfrjxj=-fr作为割平面方程。注2：每增加一个割平面方程，就增加一个松弛变量yr，此松弛变量是唯一可被选作离基变量的基变量，若在求解过程中yr再次成为基变量，则可从表中删除它相应的行和列。,0-1型整数规划,-变量xi仅可取值0或1.应用：1特殊约束的处理。2多中选一的约束。,隐枚举法(Implicit Enumeration),例：max z=3x1-2 x2+5 x3 s.t x1+2 x2-x3 2(1)x1+4 x2+x3 4(2)
12、x1+x2 3(3)4x2+x3 6(4)xi=0 or 1解：(1)先用试探法求出一个可行解，如x0=(1,0,0)T,其目标函数值为z0=3.(2)以zz0作为过滤条件增加到原有约束集中,得,max z=3x1-2 x2+5 x3 s.t x1+2 x2-x3 2(1)x1+4 x2+x3 4(2)x1+x2 3(3)4x2+x3 6(4)3x1-2 x2+5 x3 3(5)xi=0 or 1(3)求解新的规划模型。按照枚举法的思路，依次检查各种变量的组合，每找到一个可行解，求出它的目标函数值z1，若z1z0，则将过滤条件换成zz1。,点 过滤条件 约束 z值 3x1-2 x2+5 x3
13、3(5)(1)(2)(3)(4)(0,0,0)T(0,0,1)T 5 3x1-2 x2+5 x3 5(0,1,0)T(0,1,1)T(1,0,0)T(1,0,1)T 8 3x1-2 x2+5 x3 8(1,1,0)T(1,1,1)T 最优解为：(1,0,1)T,0-1型整数规划的典型应用问题,1.背包问题例：一登山运动员，他需要携带的物品如下，设他可携带的最大量为25kg,试选择该队员所应携带的物品。物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信器材重量/kg 5 5 2 6 12 2 4重要性 20 15 18 14 8 4 10解：设xi=0 不应携带物品i xi=1 应携带物品IMa
14、x 20 x1+15x2+18x3+14x4+8x5+4x6+10 x7S.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7 25 xi=0 or 1,背包问题的一般形式,2.布点问题,例：某城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站越少越好，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场，据实地测定，各区之间消防车行驶的时间见下表，试制定一个布点最少的计划。地区1 地区2 地区3 地区4 地区5 地区6地区1 0 10 16 28 27 20地区2 10 0 24 32 17 10地区3 16 24 0 12 27 21 地区4 28 32 12 0 15 25 地区5 27 17 27 15 0 14地区6 20 10 21 25 14 0,3.旅行商问题,一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路，使得商人每个城市走过一遍后回到起点且所走路径最短。解：设xij=1若商人行走的路线中包含从城市i到j的路径，否则xij=0。,
