《经济学第五章整数规划课件.ppt》由会员分享,可在线阅读,更多相关《经济学第五章整数规划课件.ppt(55页珍藏版)》请在三一办公上搜索。
1、整 数 规 划(Integer Programming),整数规划的模型,分支定界法,01 整数规划,在很多场合,我们建立最优化模型时,实际问题要求决策变量只能取整数值而非连续取值。此时,这类最优化模型就称为整数规划(离散最优化)模型。,整数规划的求解往往比线性规划求解困难得多,而且,一般来说不能简单地将相应的线性规划的解取整来获得。,整数线性规划数学模型的一般形式,整数规划(IP)松弛问题整数线性规划(ILP)的数学模型:,一、整数规划的数学模型及解的特点,决策变量只能取值0 或 1。,整数规划问题的类型,纯整数线性规划(pure integer linear programming),全部
2、决策变量都必须取整数值。,混合整数线性规划(mixed integer linear programming),决策变量中一部分必须取整数值, 另一部分可以不取整数值。,0-1型整数线性规划(zero-one integer linear programming),例1、 某公司准备投资 50 万元为其产品做广告,广告代理商给公司的有关广告方式的费用和其效果情况如下表,公司面临的管理决策问题是广告总费用不超过 50 万元的基础上选择哪些广告方式,使得潜在顾客数尽可能地多。,整数规划问题实例,xi =,1 选择第i 种广告方式0 不选择第i种广告方式,Max Z = 40 x1 + 20 x2
3、+ 25x3 + 10 x4 40 x1 + 15x2 + 20 x3 + 10 x4 50 x1 ,x2 ,x3 ,x4 = 0 或 1,例1、 模型设:xi(i = 1,2,3,4) 表示4 种广告方式。,例2、某公司在城市的东、西、南三区建立门市部。拟议中有7个位置(地点)Ai(i=1,2,7)可供选择。公司规定: 在东区,由 A1,A2,A3 三个点中至多选两个; 在南区,由 A4,A5 两个点中至少选一个; 在西区,由 A6,A7 两个点中至少选一个。 如果选用 Ai 点,设备投资估计为 bi 元,每年可获利润估计为 ci 元,但投资总额不能超过 B 元。问公司选择哪几个点可使年总利
4、润最大?,例2、模型 设:,Ai =,1 选择 Ai 建立门市0 不选择 Ai 建立门市,Max Z = ci Ai bi Ai B A1 + A2 + A3 2 A4 + A5 1 A6 + A7 1 Ai = 0 或 1 ,(i = 1,2,3,4,5,6,7),例3:运动员选拔问题4*100m混合泳接力是观众最感兴趣的游泳项目之一。现在从实例出发,研究混合泳运动员的选拔问题:甲、乙、丙、丁是4名游泳运动员,他们各种姿势的100m游泳成绩见下表,为组成一个4*100m混合泳接力队,怎样选派运动员,方使接力队的游泳成绩最好?,设:工序 B 有两种方式完成方式(1)的工时约束: 0.3x1 +
5、 0.5x2 150方式(2)的工时约束: 0.2x1 + 0.4x2 120 问题是完成工序 B 只能从两种方式中任选一种,如何将这两个互斥的约束条件统一在一个线性规划模型中呢?,例4、应用 0-1 变量解决含互斥约束条件问题,例4、模型 引入 0-1 变量,y1 =,0 若工序 B 采用方式(1)完成1 若工序 B 不采用方式(1)完成,y2 =,0 若工序 B 采用方式(2)完成1 若工序 B 不采用方式(2)完成,于是前面两个互斥的约束条件可以统一为如下三个约束条件: 0.3x1 + 0.5x2 150 + M1y1 0.2x1 + 0.4x2 120 + M2y2 y1 + y2 =
6、 1 其中 M1 ,M2 都是足够大的正数。,有三种资源被用于生产三种产品,资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划,使总收益最大。,例5固定费用问题,解:设xj为第j种产品的生产数量,j=1,2,3;,yj =,1 当生产第j种产品, 即 xj 0 时,0 当不生产第j种产品即 xj = 0 时,引入约束 xi M yi ,i =1,2,3,M充分大,以保证当 yi = 0 时,xi = 0 。,可建立如下的数学模型:,Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 +
7、 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ,i =1,2,3,M充分大 xj 0 yj 为0-1变量,i = 1,2,3,例6、合理下料 造某种机床,需要 A ,B ,C 三种轴件,其规格与数量如下表,各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床,最少要用多少根圆钢?,例6、模型 分析该问题后,发现较合理的下料方案有:,例6、模型 设:xi 采用方案i下料所用的原料根数。,Min Z = x1 + x2 + x3 + x4 + x5 x1 + x2 = 100 x1 + x4 + 2x5 = 2
8、00 2x2 + 4x3 + 2x4 + x5 = 400 x1 ,x2 ,x3 ,x4 ,x5 0 ,且为整数,例7、某公司计划在m个地点建厂,可供选择的地点有A1,A2Am ,他们的生产能力分别是a1,a2,am(假设生产同一产品)。第i个工厂的建设费用为fi (i=1.2m),又有n个地点B1,B2, Bn 需要销售这种产品,其销量分别为b1.b2bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂,既满足各地需要,又使总建设费用和总运输费用最省?,设 xij :从工厂运往销地的运量(i=1,2m、j=1,2n), 1 在Ai建厂 yi (i=1.2m) 0 不在Ai建厂,模
9、型:,(三)整数规划与线性规划的关系,从数学模型上看整数规划似乎是线性规划的一种特殊形式,求解只需在线性规划的基础上,通过舍入取整,寻求满足整数要求的解即可。但实际上两者却有很大的不同,通过舍入得到的解(整数)也不一定就是最优解,有时甚至不能保证所得到的解是整数可行解。举例说明。,例:设整数规划问题如下,首先不考虑整数约束,得到线性规划问题(一般称为松弛问题)。,用图解法求出最优解x13/2, x2 = 10/3且有Z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3)、 (2,3)、(1,4)、(2,4)。,按整数规划约束
10、条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如图所示。,显然,它们都不可能是整数规划的最优解。,因此,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法。 如上例:其中(2,2)(3,1)点为最大值,Z=4。,目前,常用的求解整数规划的方法有: 分支定界法和割平面法;对于特别的01规划问题采用隐枚举法 和匈牙利法。,(一)基本思路,考虑纯整数问题:,整数问题的松弛问题:,二、分枝定界法,(B)为(A)的松弛问题。,分枝定界法一般步骤:,(1) 先解(A)的松弛问题(B),(2) (B)无可行解(A)无可行解。 (B)最优解符
11、合(A)要求,停。 (B)最优解不符合(A)要求,转(3)。,(3) 估整数解S0 ,定界(上界、下界),(4) 选(B)解中不符合整数条件的分量Xj (Xj = bj )分枝,作(B)的后续问题(C)、(D)。 (C):(B) 加约束Xj bj+1 (D):(B) 加约束Xj bj,(6) 全部枝剪完,停,(5) 解(C)、(D),例1:用分枝定界法求解整数规划问题(用图解法计算),记为(IP),解:首先去掉整数约束,变成一般线性规划问题,记为(LP),例题,用图解法求(LP)的最优解,如图所示。,x1,x2,3,3,(18/11,40/11),对于x118/111.64, 取值x1 1,
12、x1 2对于x2 =40/11 3.64,取值x2 3 ,x2 4先将(LP)划分为(LP1)和(LP2),取x1 1, x1 2,x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是(IP)最小值的下限。,有下式:,现在只要求出(LP1)和(LP2)的最优解即可。,x1,x2,3,3,(18/11,40/11),先求(LP1),如图所示。此时在B 点取得最优解。 x11, x2 =3, Z(1)16找到整数解,问题已探明,此枝停止计算。,1,1,同理求(LP2) ,如图所示。在C 点取得最优解。即x12, x2 =10/3, Z(2) 56/318.7,B,
13、A,C,(2) Z()16 原问题有比(16)更小的最优解,但 x2 不是整数,故利用 3 10/34 加入条件。,加入条件: x23, x24 有下式:,只要求出(LP3)和(LP4)的最优解即可。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,先求(LP3),如图所示。此时在D 点取得最优解。即 x112/52.4, x2 =3, Z(3)-87/5 -17.4 Z(1)-16但x112/5不是整数,可继续分枝。即 3x12。,D,求(LP4),如图所示。无可行解,不再分枝。,在(LP3)的基础上继续分枝。加入条件3x12有下式:,只要求出(LP5)和(LP6)的最优
14、解即可。,x1,x2,3,3,(18/11,40/11),1,1,B,A,C,D,先求(LP5),如图所示。此时在E 点取得最优解。即 x12, x2 =3, Z(5)17找到整数解,问题已探明,此枝停止计算。,E,求(LP6),如图所示。此时在F点取得最优解。x13, x2 =2.5, Z(6)31/215.5 Z(5),F,如对 Z(6) 继续分解,其最小值也不会低于15.5 ,问题探明,剪枝。,至此,原问题(IP)的最优解为: x1=2, x2 =3, Z* = Z(5) 17以上的求解过程可以用一个树形图表示如右:,LP1x1=1, x2=3Z(1) 16,LPx1=18/11, x2
15、=40/11Z(0) 19.8,LP2x1=2, x2=10/3Z(2) 18.5,LP3x1=12/5, x2=3Z(3) 17.4,LP4无可行解,LP5x1=2, x2=3Z(5) 17,LP6x1=3, x2=5/2Z(6) 15.5,x11,x12,x23,x24,x12,x13,例2:用分枝定界法求解整数规划问题,x11,x12,x22,x23,x22,x23,x12,x13,LP1x1=1, x2=7/3Z(1) 10/3,LPx1=3/2, x2=10/3Z(0) 29/6,LP2x1=2, x2=23/9Z(2) 41/9,LP3x1=33/14, x2=2Z(3) 61/1
16、4,LP4无可行解,LP7x1=2, x2=2Z(7) 4,LP8x1=3, x2=1Z(8) 4,x11,x12,x22,x23,x12,x13,解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。,初始表,最终表,例3、用分枝定界法求解整数规划问题(单纯形法),x1=13/4 x2=5/2 Z(0) =59/414.75 选 x2 进行分枝,即增加两个约束,2 x2 3 有下式:,分别在(LP1)和(LP2)中引入松弛变量x5和x6 ,将新加约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表:,x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝,加
17、入约束 3 x1 4,LP1,LP2,x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝,接(LP1)继续分枝,加入约束 4 x1 3,有下式:,分别引入松弛变量x7 和 x8 ,然后进行计算。,x1=3, x2=2 Z(3) =13找到整数解,问题已探明,停止计算。,LP3,x1=4, x2=1 Z(4) =14找到整数解,问题已探明,停止计算。,LP4,树形图如下:,LP1x1=7/2, x2=2Z(1)29/2=14.5,LPx1=13/4, x2=5/2Z(0) 59/4=14.75,LP2x1=5/2, x2=3Z(2)27/2=13.5,LP
18、3x1=3, x2=2Z(3) 13,LP4x1=4, x2=1Z(4) 14,x22,x23,x13,x14,练习:用分枝定界法求解整数规划问题 (单纯形法),LP1x1=1, x2=3Z(1) 16,LPx1=18/11, x2=40/11Z(0) 19.8,LP2x1=2, x2=10/3Z(2) 18.5,LP3x1=12/5, x2=3Z(3) 17.4,LP4无可行解,LP5x1=2, x2=3Z(5) 17,LP6x1=3, x2=5/2Z(6) 15.5,x11,x12,x23,x24,x12,x13,隐枚举法(max),原则:1、用试探法,求出一个可行解,以它的目标值 作为当
19、前最好值Z02、增加过滤条件Z Z03、将xi 按ci由小大排列,三、01 整数规划,01 整数规划是一种特殊形式的整数规划,这时的决策变量xi 只取两个值0或1,一般的解法为隐枚举法。,例1:maxZ = 3x1 -2x2+5x3,x1 +2x2 - x3 2 x1 +4x2 +x3 4 x1 + x2 3 4x2+x3 6 x1 , x2 , x3为0或1,解: 观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3,过滤条件:3x1 - 2x2+5x3 3,将(x1 , x2 ,x3 ) (x2 ,x1 ,x3 ),解(x2 x1 x3 ) 目标值 Z0 当前最好值 (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,(0 . 1 . 1 . 0 . 0),练习:用隐枚举法求解01规划问题,