




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1,第五章 整数规划,2,整数规划是一类要求变量取整数值的数学规划,可分成线性和非线性两类(本章讨论线性)。 根据变量的取值性质,又可以分为纯整数规划,混合整数规划,0-1整数规划等。,3,整数规划是数学规划中一个较弱的分支,目前只能解中等规模的线性整数规划问题,而非线性整数规划问题,还没有好的办法。,4,例:一登山队员做登山准备,他需要携带的物品有:食品,氧气,冰镐,绳索,帐篷,照相机和通讯设备,每种物品的重要性系数和重量如下,假定登山队员可携带最大重量为25公斤。问:如何装备?,5,6,解:如果令xi=1表示登山队员携带物品i,xi=0表示登山队员不携带物品i,则问题表示成0-1规划: M
2、ax Z= 20 x1+15x2 +18x3 +14x4 +8x5 +4x6 +10 x7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1或xi=0 i=1,2,.7,7,例 背包问题( Knapsack Problem) 一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?,8,解:如
3、果令xj=1表示携带物品j,xj=0表示不携带物品j,则问题表示成0-1规划: Max Z = cjxj s.t. ajxj b xj=0 或1,9,例 用集装箱托运货物 问:甲乙货物托运多少 箱,使总利润最大?,10,图解法:, x1* = 4 x2* = 1 zI* = 90,max z = 20 x1 + 10 x2 5x1 + 4x2 24 2x1 + 5x2 13 x1,x2 0 x1,x2取整数,11,一般,整数规划的最优解不会优于相应 线性规划的最优解。,对于max问题, zI* zl* 对于min问题, zI* zl*,12,数学模型 整数规划(IP)的一般数学模型: Max
4、Z = cjxj s.t. aijxj bi(i=1,2,m) xj 0 且部分或全部是整数,13,特殊约束的处理(IP的应用) 互斥约束 矛盾约束 在建立数学模型时,有时会遇到相互矛盾的约束,模型只要求其中的一个约束起作用。,14,例:下面两个约束相互矛盾 f(x)-5 0 (1) f(x) 0 (2) 引入一个整数变量来处理 -f(x)+5 M(1-y) (3) f(x) My (4) M是足够大的整数,y 是0-1变量,15,当y=1时,(1)(3)无差别,(4)式显然成立; 当y=0时,(2)(4)无差别,(3)式显然成立。 以上方法可以处理绝对值形式的约束 f(x) a (a0) 此
5、时 f(x) a (5) f(x) -a (6) 是矛盾约束。,f(x)-5 0 (1) -f(x)+5 M(1-y) (3) f(x) 0 (2) f(x) My (4),16,引入一个整数变量来处理 -f(x)+a M(1-y) f(x)+a My M是足够大整数,y 是0-1变量 注意:对 |f(x)| a (a0) 不必引入0-1变量,因为f(x) a和f(x) -a并不矛盾。,f(x) a (5) f(x) -a (6),17,例:两个约束条件 2x1+3x2 8 x1+ x2 2 只能有一个成立,试用0-1变量来表示这个要求。 解:引入0-1变量y和足够大的正数M, 则,18,8-
6、2x1-3x2 M(1-y) x1+ x2 - 2 My 当y=0, x1+ x2 2 成立, 而 2x1+3x2 8-M 自然成立,从而是多余的; 当y=1, 2x1+3x2 8 成立, 而 x1+ x2 2+M 自然成立,从而是多余的。,2x1+3x2 8 x1+ x2 2,19,多中选一的约束 例如:模型希望在下列n个约束中,只能有一个约束有效, fi(x) 0 i=1,2,.n. 引入 n个0-1变量yi , i=1,2,n,则上式可改写为: fi(x) M(1-yi) y1+ y2 + + yn=1,20,如果希望有k个约束有效,则: fi(x) M(1-yi), y1+ y2 +
7、+ yn= k 如果希望至多有k个约束成立,则: 如果希望至少有k个约束成立,则:,fi(x) M(1-yi), y1+ y2 + + yn k,fi(x) M(1-yi), y1+ y2 + + yn k,21,逻辑关系约束 比较典型的逻辑关系是 if-then关系,也称if-then约束,这类逻辑关系一般涉及两个约束,如果第一个约束成立,则第二个约束也必须成立,否则,如果第一个约束不成立,则第二个约束也可以不成立。可以描述如下:,22,如果f (x)0成立,则g (x) 0必须成立; 如果f (x)0不成立,则对g (x)无限制。 引入0-1变量: f (x) -M(1-y) (*) g
8、(x) My,23,如果f (x)0成立,则y不能为1,否则与(*)矛盾; 所以 y=0, g (x) 0 成立。 如果 f (x) 0(即f (x)0不成立) 则y的取值已无关紧要,因为y取任何值(*)总成立,所以y的取值不由(*)控制,因此g (x) 的取值不受任何限制。,f (x) -M(1-y) (*) g (x) My,24,解法概述 当人们开始接触整数规划问题时,常会有如下两种初始想法: 因为可行方案数目有限,因此经过穷举法一一比较后,总能求出最好方案,例如,背包问题充其量有2n种方式,实际上这种方法是不可行。,设想计算机每秒能比较1000000个方式,那么比较完260种方式,大约
9、需要360世纪。,25,先放弃变量的整数性要求,解一个线性规划问题,然后用“四舍五入”法取整数解,这种方法,只有在变量的取值很大时,才有成功的可能性,而当变量的取值较小时,特别是0-1规划时,往往不能成功。,26,例 求下列问题: Max Z=3x1+13x2 s.t. 2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,27,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,放弃整数要求后,最优解B(9.2,2.4) Z0=58.8,而原整数规划最优解I(2,4) Z0=58,实际上B附近四个整点(
10、9,2)(10,2)(9,3)(10,3)都不是原规划最优解。,Max Z=3x1+13x2 s.t. 2x1+9x2 40 11x1-8x2 82 x1,x2 0,且取整数值,28,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A,D,假如能求出可行域的“整点凸包”(包含所有整点的最小多边形OEFGHIJ),则可在此凸包上求线性规划的解,即为原问题的解。但求“整点凸包”十分困难。,E,F,G,H,I,J,29,O 1 2 3 4 5 6 7 8 9 10,5 4 3 2 1,x1,x2,I(2,4),B(9.2,2.4),A
11、,D,假如把可行域分解成五个互不相交的子问题P1 P2 P3 P4 P5之和, P3 P5的定义域都是空集,而放弃整数要求后P1最优解I(2,4),Z1=58 P2最优解(6,3),Z2=57 P4最优解(98/11,2),Z4=52(8/11),P1,P2,P4,P3,P5,30,X1 2,X1 6,X2 3,X2 2,X1 3,X1 7,X2 4,X2 3,P1,P5,P4,P2,P3,P,31,假如放弃整数要求后,用单纯形法求得最优解,恰好满足整数性要求,则此解也是原整数规划的最优解。,以上内容中描述了目前解整数规划问 题的两种基本途径。,32,5.1 分枝定界法 (Branch and
12、 Bound Method) 原问题的松驰问题: 任何整数规划(IP),凡放弃某些约束条件(如整数要求)后,所得到的问题(P) 都称为(IP)的松驰问题。,最通常的松驰问题是放弃变量的整数性要求后,(P)为线性规划问题。,33,去掉整数约束,用单纯形法,34,分枝定界法步骤 一般求解对应的松驰问题,可能会出现下面几种情况: 若所得的最优解的各分量恰好是整数,则这个解也是原整数规划的最优解,计算结束。,35,分枝定界法步骤 一般求解对应的松驰问题,可能会出现下面几种情况: 若所得的最优解的各分量恰好是整数,则这个解也是原整数规划的最优解,计算结束。 若松驰问题无可行解,则原整数规划问题也无可行解
13、,计算结束。,36,若松驰问题有最优解,但其各分量不全是整数,则这个解不是原整数规划的最优解,转下一步。,37,若松驰问题有最优解,但其各分量不全是整数,则这个解不是原整数规划的最优解,转下一步。 从不满足整数条件的基变量中任选 一个xl进行分枝,它必须满足xl xl 或 xl xl +1中的一个,把这两个约束条件加进原问题中,形成两个互不相容的子问题(两分法)。,38,定界:把满足整数条件各分枝的最优目标函数值作为上(下)界,用它来判断分枝是保留还是剪枝。,39,定界:把满足整数条件各分枝的最优目标函数值作为上(下)界,用它来判断分枝是保留还是剪枝。 剪枝:把那些子问题的最优值与界值比较,凡
14、不优或不能更优的分枝全剪掉,直到每个分枝都查清为止。,40,例: 用分枝定界法求解: Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解(6/5,21/10)Z=111/10为各分枝的上界。,41,0 1 2 3 4,4 3 2 1,x1,x2,分枝:x1 1,x1 2,P1,P2,(6/5,21/10),42,两个子问题: (P1)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 1 ,整数 用单纯形法可解得相应的(P1)的最优解(1,9/4) Z
15、=10(3/4),43,(P2)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 , x1 2 ,整数 用单纯形法可解得相应的(P2)的最优解(2,1/2) Z=9(1/2),44,0 1 2 3 4,4 3 2 1,x1,x2,再对(P1) x1 1 (1,9/4)分枝: (P3) x2 2 (P4) x2 3,P1,P2,P3,P4,45,(P1)两个子问题: (P3)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 2整数 用单纯形法可解得相应的(P3)的最优解(1,2) Z=
16、10 为上界,46,(P1)两个子问题: (P4)Max Z=4x1+3x2 s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ,x1 1, x2 3整数 用单纯形法可解得相应的(P4)的最优解(0,3) Z=9,47,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4) Z=10(3/4),P4: (0,3) Z=9,P2:(2,1/2) Z=9(1/2),P3: (1,2) Z=10,P:(6/5,21/10) Z=111/10,原问题的最优解(1,2) Z=10,48,例 用分枝定界法求解: Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2
17、 6 x1,x2 0 整数 用单纯形法可解得相应的松驰问题的最优解(10/3,4/3)Z=26/3为各分枝的下界。,49,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,50,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,(10/3,4/3)选 x1进行分枝: (P1) x1 3 (P2) x1 4 为空集,P1,51,(P1) Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 ,x1 3 整数 用单纯形法可解得(P1)的最优解(3,3/2)Z=9,52,(P2) Min Z= x1+4x2 s
18、.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0 x1 4 整数 无可行解。,53,0 1 2 3 4 5 6,8 7 6 5 4 3 2 1,x1,x2,p,对(P1) x1 3 选 x2进行分枝: (P3) x2 1无可行解 (P4) x2 2,P4,54,(P3) Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0, x1 3 ,x2 1整数 无可行解。,55,(P4) Min Z= x1+4x2 s.t. 2x1+ x2 8 x1+2x2 6 x1,x2 0, x1 3 ,x2 2整数 用单纯形法可解得(P4)的最优解(2,2)Z=1
19、0,56,X1 4,X2 1,X1 3,X2 2,P1:(3,3/2) Z=9,P4:(2,2) Z=10,P2:无可行解,P3:无可行解,P:(10/3,4/3) Z=26/3,原问题的最优解(2,2) Z=10,57,作业: P103 2.1(1)分枝定界法,58,5.2 割平面法,割平面法的基本思想:先不考虑整数约束,按一般线性规划问题求其最优解,线性规划问题的最优基本可行解是解集的一个顶点,这个顶点的坐标未必都是整数,若不是整数解,可增加一条约束,相当于增加一个平面将这个顶点割掉,称这种方法为割平面法。 重点:新约束的求法。,59,算 法 思 想,由松弛问题的可行域向整数规划的可行域逼
20、近 方法利用超平面切除 要求 整数解保留 松驰问题最优值增加,60,设放弃整数要求的线性规划最优单纯表为:,设基变量xr的值br不是整数, 则将第r个约束 改写为整数和小数分离的形式。,61,记,改写为,即,62,对于任何可行解,有,对于整数可行解,此约束式可写成更严格的不等式:,新约束条件 切割方程:,非整数解不满足这个约束。,63,例 求解整数线性规划问题,64,解 这是纯整数规划问题 引入松驰变量将其化为标准形式 不考虑整数约束,利用单纯形法求其最优解。 最优单纯形表如下,65,从最优单纯形表中看出约束条件变成,变形得,上式分别记为,都应为小于等于0的整数。引进松弛变量,0,0,66,用
21、对偶单纯形法求解,取i=3为主元行,k=3为主元列,进行换基迭代。再取i=4为主元行,k=4为主元列,进行换基迭代得表。,67,最优基本可行解为:,68,用割平面法求解完全整数规划问题的步骤:,不考虑整数约束,利用单纯表法求出一般线性规划问题的最优解。,若该最优基本可行解中基变量之值全为非负整数,停止计算。否则,增加新约束,继续求解。,利用对偶单纯形法求解扩充后的新问题,求出最优解后,转,69,例 用割平面法求解下面整数线性规划问题,解 该问题的松弛问题的标准形为,70,利用单纯形法求出松弛问题的最优解如表所示,表4-7,可以看出,约束条件变为,71,按割平面要求变形为,考虑到整数约束,从而需
22、新加入约束条件,引入松弛变量 ,得,72, ,40,73,得到最优解为 ,满足整数约束条件,该解即为原整数规划问题的最优解。,作业: P103 2.2(1)割平面法,74,5.3 求解0-1规划的隐枚举法,例 求解0-1线性规划问题,75,解 从目标函数可以看出:若所有变量全取0可使目标函数达到下界值。因此应尽量让变量取0,除非不得已,再使某些变量取1去试试。这就是隐枚举法的基本思想。,76,隐枚举法的标准形式,其中, 任意。,对目标函数求极大值时,将目标函数中的系数加上负号,改为求极小值。 约束不等式为 时,两边乘以-1改为 。 约束为等式时,改为 和 两个不等式,再在 式两边乘以-1使之变
23、为 。 若某个 。,77,隐枚举法的步骤:,1.化为标准形式, 2.判断节点1(0,0,0)T是否可行,若可行,即为最优解, 3.如不可行,判断分枝能否得到可行解,方法? 4.如继续分枝,选择一个自由变量作固定变量,选择原则? 5.进行分枝,计算分枝节点的可行解, 6.判断各不可行节点是否继续分枝。如继续转4。 判断准则:能否得到更好的可行解。,令正系数变量均为1,看不满足的约束能否变满足,使所有约束离可行性的总距离最小,1.不满足的某个约束中有一个正的系数 2.目标函数中的系数小于,z:迄今最好的目标值,S:非自由变量下标,78,0-1规划的另一种隐枚举法 例 选择投资场所 Ai投资Bi元,
24、总投资B, 收益Ci元. 问:如何选择Ai,使收益最大?,79,例 求解如下0-1规划 max z = 3x1 - 2x2 + 5x3 x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或1,解:(1)观察一个可行解x1 = 1 x2 = x3 = 0 此时,z = 3,(2)增加一个过滤条件 3x1-2x2+5x33 *,80,(3)求解新问题(含过滤条件)。列表计算, 最优解:x1* = 1 x2* = 0 x3* = 1 此时,z* = 8,x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1
25、 + x2 3 4x2 + x3 6 ,3x1-2x2+5x33 *,3x1-2x2+5x35 *,3x1-2x2+5x38 *,81,5.4 求解指派问题的匈牙利法,一、指派问题及其标准形式,一般称矩阵,为指派问题的系数矩阵(coefficient matrix)。,82,为了建立标准指派问题的数学模型,引入 个0-1变量,问题的数学模型可写成,83,例 某商业公司设计开办五家新闻商店 。为了尽早建成营业,商业公司通知了 五个建筑公司,以便让每家新商店由一个建筑公司承建。建筑公司 对新商店 的建造费用的投标为 均见下表。商业公司应当对五家建筑公司怎样分配建造任务,才能使总建造费用最少?,表4
26、-9,84,这是一个标准的指派问题。若设0-1变量 则问题的数学模型为,85,二、匈牙利解法,常用来求解指派问题的方法是匈牙利数学家考尼格的方法,习惯上称之为匈牙利解法。,对于标准的指派问题,匈牙利解法的一般步骤为: 步骤一:变换系数矩阵,使各行和各列皆出现零元素。 如各行及各列分别减去本行及本列最小元素,这样可保证每行及每列中都有零元素,同时,也避免了出现负元素。,甲 乙 丙 丁 戊,A B C D E,86,步骤二:试指派,以寻求最优解。此时,若独立零元素等于 , 则已可得出最优解。否则2种情况:,存在未标记0,且其所在行和列中至少有2个未标记0。,独立零元素小于n。,将任一0记 ,其余同
27、行同列的未标记0记。,转步骤三。,87,步骤三:做能覆盖所有零元素的最少数目的直线集合。,重复步,直到不能继续做标记,,88,步骤四:变换系数矩阵,使未被直线覆盖的元素中出现零元素。回到步骤二。,在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行(或列)中各元素都减去这一最小元素, 为了消除负元素,只要对它们所在的列(或行)中各元素都加上这一最小元素(可以看作减去这一最小元素的相反数)即可。,甲B,乙C,丙E,丁D,戊A,或 甲B,乙D,丙E,丁C,戊A,89,现在,我们来解例。指派问题的系数矩阵为,90,对各行元素分别减去本行的最小元素,对各列也如此,得,试指派后,独立零元素不够。可用四条直线覆盖所有零元素,这是最少数直线集合,即由于C的阶数 =5,故需对系数矩阵C继续变换。,91,为了使未被直线覆盖的元素中出现零元素,将第二行和第三行中各元素减去未被直线覆盖元素中的最小元素1。但这样一来,第一列中出现了负元素,因而再对第一列各元素分别加上1,即,此时,试指派后,可得独立零元素5个,故已可得最优指派方案。,92,所以,本题最优解为,这样,总的建设费用最少,为34万元。,也就是说,最优指派方案为:让 承建 承建 承建 承建 承建 。,93,三、 一般的指派问题,1、最大化指派问题,设最大化指派问题系数矩阵 ,其中最大元素 为 。
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 公司产品标准管理办法
- 企业数据开发管理办法
- 代谢药品注册管理办法
- 企业外部审计管理办法
- 企业办公区域管理办法
- 乡镇违反建设管理办法
- 乡镇法庭人员管理办法
- 乡镇集体资产管理办法
- 会计档案管理办法讲解
- 乡镇城区公厕管理办法
- 2025至2030中国细胞健康筛查和和健康测试行业市场深度研究及发展前景投资可行性分析报告
- 2025发展对象考试题库带有答案
- 肝癌介入术护理课件
- 企业安全生产内部举报奖励制度
- 胸痛的诊断与处理
- 户外反洗钱宣传活动方案
- 声带小结护理查房
- 2025届山西中考语文真题试卷【含答案】
- 闵行区2024-2025学年下学期七年级数学期末考试试卷及答案(上海新教材沪教版)
- 2024年湖南人文科技学院招聘笔试真题
- 实验室人员授权管理制度
评论
0/150
提交评论