整数规划.ppt

《整数规划.ppt》由会员分享，可在线阅读，更多相关《整数规划.ppt（134页珍藏版）》请在三一办公上搜索。

1、第八章 整 数 规 划,整数规划,整数规划问题的定义整数规划问题与模型整数规划算法计算软件应用案例,整数规划,整数规划的基本含义:,在线性规划问题中,求得的最优解有时可能是整数,也有可能不是整数,对于某些实际问题,要求必须是整数,象这种要求结果是整数解的,称为整数规划问题.若结果要求是0-1整数结果,则称为0-1规划问题.,整数规划问题,实例特点模型分类,整数规划,应用案例,投资组合问题旅游售货员问题背包问题,整数规划,投资组合问题,背 景实 例模 型,整数规划,背景,证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资：财团或银行把资金投入到若干项目中以获得中长期的

2、收益最大。,整数规划,案例,某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 万元，问应如何选择项目使得5年后总收益最大？,整数规划,模型,变量每个项目是否投资约束总金额不超过限制目标总收益最大,整数规划,整数规划,旅游售货员问题,背景案例模型,整数规划,背景,旅游线路安排 预定景点走且只走一次 路上时间最短配送线路货郎担问题 送货地到达一次 总路程最短,案例,有一旅行团从 出发要遍游城市，已知从 到 的旅费为，问应如何安排行程使总费用最小？,整数规划,模型,变量是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开

3、一次,整数规划,目标总费用最小,整数规划,整数规划,背包问题,背景案例模型,整数规划,背景,邮递包裹 把形状可变的包裹用尽量少的车辆运走旅行背包 容量一定的背包里装尽可能的多的物品,整数规划,实例,某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放

4、在三个旅行包里。,整数规划,整数规划,问题分析,变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中,整数规划,约束 包裹容量限制 必带物品限制 选带物品限制,整数规划,目标函数未带物品购买费用最小,整数规划,费用：,模型,整数规划,特征变量整数性要求来源 问题本身的要求 引入的逻辑变量的需要性质可行域是离散集合,整数规划,整数规划,线性整数规划模型,一般整数规划模型0-1整数

5、规划模型混合整数规划模型,一般整数规划模型,返回,0-1整数规划模型,返回,混合整数规划模型,返回,算 法,与线性规划的关系分支定界算法割平面算法近似算法,返回,与线性规划的关系,整数规划,放松的线性规划,可行解是放松问题的可行解,最优值大于等于放松问题的最优值,注释,最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取,1 整数规划的图解法,例1 某公司拟用集装箱托运甲乙两种货物，货物体积、重量，获利及若干限制事下表，且甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？,解：设甲乙托运数为x1,x2件，则 max z=2x1+3x

6、2 s.t.195x1+273x2=0,且x1,x2为整数。,3,2,3,2x1+3x2=14.66,2x1+3x2=14,2x1+3x2=0,性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值，任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标数值。,2 整数规划的计算机求解,解：设甲乙托运数为x1,x2件，则 模型：max z=2x1+3x2 s.t.195x1+273x2=0,且x1,x2为整数。,2 整数规划的计算机求解,整数变量定义 LinDoGIN 一般整数变量:GIN 0-1

7、整数变量:INT LinGo 一般整数变量:GIN(variable_name);0-1整数变量：BIN(variable_name);,Integer variable General variable,2 整数规划的计算机求解,源程序：max 2x1+3x2 s.t.195x1+273x2=1365 4x1+40 x2=140 x1=4end Gin 2,2 整数规划的计算机求解,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE VALUE=14.6511631 NEW INTEGER SOLUTION OF 14.0000000 AT BRANCH 0 PIVOT

8、 6 BOUND ON OPTIMUM:14.00000 ENUMERATION COMPLETE.BRANCHES=0 PIVOTS=6 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)14.00000 VARIABLE VALUE REDUCED COST X1 4.000000-2.000000 X2 2.000000-3.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)39.000000 0.000000 3)

9、44.000000 0.000000 4)0.000000 0.000000 NO.ITERATIONS=6 BRANCHES=0 DETERM.=1.000E 0,整数规划,例3 求解下面的混合整数规划问题：Max z=3x1+x2+3x3S.t.-x1+2x2+x3=0,x1,x3为整数,整数规划,整数规划,例3 求解下面的混合整数规划问题：源程序代码：Max 3x1+x2+3x3S.t.-x1+2x2+x3=4 4x2-3x3=2 X1-3x2+2x3=3 X3=1endGin x1int x3,整数规划,整数规划,OBJECTIVE FUNCTION VALUE 1)16.25000

10、VARIABLE VALUE REDUCED COST X1 4.000000-3.000000 X3 1.000000-3.750000 X2 1.250000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)4.500000 0.000000 3)0.000000 0.250000 4)0.750000 0.000000 5)0.000000 0.000000 NO.ITERATIONS=6 BRANCHES=1 DETERM.=1.000E 0,整数规划,第3节 整数规划的应用,整数规划模型:目标:max(min)c1x1+c2x2+cnxn约束:

11、a11x1+a12x2+a1nxn()b1 a21x1+a21x2+a2nxn()b2 a31x1+a32x2+a3nxn()b3 an1x1+an2x2+annxn()bn x1,x2 x3 x4 x5 xn 0，且xi为整数,第3节 整数规划的应用,Lindo 程序：max(min)c1x1+c2x2+cnxnS.t.a11x1+a12x2+a1nxn()b1 a21x1+a21x2+a2nxn()b2 a31x1+a32x2+a3nxn()b3 an1x1+an2x2+annxn()bn endGin n(普通整数变量）Int n(0-1整数变量）Int x1Int x2。Int Xn,

12、Integer variableGeneral variable,Integer variable General variable,第3节 整数规划的应用,一.投资场所的选择：P163 例4 京成畜产品公司计划在市区的东西南北四区建立销售门市部，拟议中10个位置可供选择，其中有若干约束：东区：A1,A2,A3至多选择2个；南区：A4，A5至少选一个；西区：A6，A7至少选一个；北区：A8，A9，A10至少选二个,第3节 整数规划的应用,要求投资总额不能超720万元，问应选择哪几个销售点，可使年利润最大？,解：设变量xi，取值1或0，代表Ai选用或不选用；,总利润：Z=36x1+40 x2+5

13、0 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10,约束：(1)总投资=1(4)南区选点=1(5)北区选点=2,100X1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10=720,X1+x2+x3=2,X4+x5=1,X6+x7=1,X8+x9+x10=2,Xi=0,且xi为0-1变量,模型：Max Z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10 s.t.100X1+120 x2+150 x3+80 x4+70 x5+90

14、x6+80 x7+140 x8+160 x9+180 x10=1 X6+x7=1 X8+x9+x10=2 x1.x10=0,且 xi 为0-1变量,模型的Lindo软件 源程序代码：Max 36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10 s.t.100X1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10=1 X6+x7=1 X8+x9+x10=2 end int 10,LP OPTIMUM FOUND AT STEP 12 OBJECTIVE VALUE=246

15、.222229 NEW INTEGER SOLUTION OF 245.000000 AT BRANCH 0 PIVOT 12 RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)245.0000 VARIABLE VALUE REDUCED COST X1 1.000000-36.000000 X2 1.000000-40.000000 X3 0.000000-50.000000 X4 0.000000-22.000000 X5 1.000000-20.000000 X6 1.000000-30.000000 X7 0.000000-

16、25.000000 X8 0.000000-48.000000 X9 1.000000-58.000000 X10 1.000000-61.000000,LP OPTIMUM FOUND AT STEP 12 OBJECTIVE VALUE=246.222229 NEW INTEGER SOLUTION OF 245.000000 AT BRANCH 0 PIVOT 12 RE-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)245.0000 NO.ITERATIONS=12 BRANCHES=0 DETERM.=1.000E 0 X10

17、 ENTERS AT VALUE 0.88889 IN ROW 2 OBJ.VALUE=245.00 X5 ENTERS AT VALUE 1.0000 IN ROW 4 OBJ.VALUE=246.22,二、固定成本问题,例5 高压容器公司制造大中小尺寸的容器，所用资源有金属板、劳动力和机械设备三类，所需数量如下：,二、固定成本问题,例5 不考虑固定费用，每种容器售出一只所得利润分别为4万元，5万元，6万元，可使用的金属板有500吨，劳动力有300人月，机器100台月，每种容器的固定成本小号是100万元，中号为150万元，大号为200万元，现要制定一个生产计划，使获得的利润为最大。,解：设x

18、1,x2,x3为小，中，大容器的生产数量，yj代表J种容器的生产事实，取值为1或0，则生产利润为：Max 4x1+5x2+6x3-100y1-150y2-200y3约束：2x1+4x2+8x3=5002x1+3x2+4x3=300 x1+2x2+3x3=100费用与投产：因为每种容器生产都需固定费用Xi=Myi:x1=200y1X2=200y2;X3=200y3;,Max 4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3=500 2x1+3x2+4x3=300 x1+2x2+3x3=100 x1-200y1=0 X2-200y2=0 X3-200y3=0

19、endgin x1 gin x2gin x3Int y1 int y2int y3,LP OPTIMUM FOUND AT STEP 6 OBJECTIVE VALUE=350.000000 FIX ALL VARS.(1)WITH RC 0.000000E+00 NEW INTEGER SOLUTION OF 300.000000 AT BRANCH 0 PIVOT 13 BOUND ON OPTIMUM:300.0000 ENUMERATION COMPLETE.BRANCHES=0 PIVOTS=13 LAST INTEGER SOLUTION IS THE BEST FOUND RE-

20、INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)300.0000 VARIABLE VALUE REDUCED COST X1 100.000000-4.000000 X2 0.000000-5.000000 X3 0.000000-6.000000 Y1 1.000000 100.000000 Y2 0.000000 150.000000 Y3 0.000000 200.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)300.000000 0.000000 3)100.000000 0.000000

21、4)0.000000 0.000000 5)100.000000 0.000000 6)0.000000 0.000000 7)0.000000 0.000000 NO.ITERATIONS=13 BRANCHES=0 DETERM.=1.000E 0,三、指派问题根据个人特长，把N个任务分给N个人，人尽其才，总体消耗最小。,问：需要如何分派任务才能使总的耗时最少？,例6 现有四个工人，及四项任务，每人特长如下：,解：引入0-1变量 xij=,1 指派了i去完成任务j,0 没指派i去完成任务j,目标：min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23

22、+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44,约束：（1）每人只能做一项工作：(横向)x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1（2）每项工作只能由一人做:(纵向)x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x44=1 x14+x24+x34+x44=1（3）0-1整数值,min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+2

23、6x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x44=1 x14+x24+x34+x44=1 xij=0,且xij为0-1变量,Lindo 的源程序代码 min 15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+

24、19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x44=1 x14+x24+x34+x44=1 end int 16,Result:LP OPTIMUM FOUND AT STEP 9 OBJECTIVE VALUE=70.0000000 NEW INTEGER SOLUTION OF 70.0000000 AT BRANCH 0 PIVOT 9 RE

25、-INSTALLING BEST SOLUTION.OBJECTIVE FUNCTION VALUE 1)70.00000 VARIABLE VALUE REDUCED COST X11 1.000000 15.000000 X12 0.000000 18.000000 X13 0.000000 21.000000 X14 0.000000 24.000000 X21 0.000000 19.000000 X22 0.000000 23.000000 X23 0.000000 22.000000 X24 1.000000 18.000000 X31 0.000000 26.000000 X32

26、 0.000000 17.000000 X33 1.000000 16.000000 X34 0.000000 19.000000 X41 0.000000 19.000000 X42 1.000000 21.000000 X43 0.000000 23.000000 X44 0.000000 17.000000,四、建厂选址：分布系统设计,例7：某企业在A1已有一工厂，其产品生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择地方建厂。已知在A2-A5各地建厂固定成本分别为175千元，300，375，500千元，其它资源如下表：,解：设xij为Ai运往Bj的运输量 Yi=

27、,1 当Ai厂址被选中,0 当Ai厂址没被选中,则此问题的固定成本及总运输费用最小目标为：Min z=175y2+300y3+375y4+500y5+8x11+4x12+x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53,约束条件：(1)生产能力 x11+x12+x13=30 x21+x22+x23=10y2 x31+x32+x33=20y3 x41+x42+x43=30y4 x51+x52+x53=40y5（2）销售量：x11+x21+x31+x41+x51=30 x12+x22+x22+x42+x52=20 x

28、13+x23+x33+x43+x53=20,模型：目标：min z=175y2+300y3+375y4+500y5+8x11+4x12+x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53 s.t.x11+x12+x13=0,yi为0-1变量,Lindo 源程序：Min 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53+175y2+300y3+375y4+500y5 s.t.x11+x12+x13=30 x21+x

29、22+x23=10y2 x31+x32+x33=20y3 x41+x42+x43=30y4 x51+x52+x53=40y5 x11+x21+x31+x41+x51=30 x12+x22+x32+x42+x52=20 x13+x23+x33+x43+x53=20 end gin 15Int y2；Int y3Int y4；int y5,五、投资问题略。,4 分支定界算法,算法思想算法步骤算例注释,分支定界算法,例9。用分支定法求解整数规划：max 2x1+3x2S.t.195x1+273x2=0,且x1,x2 整数。,第一步：先按普通LP求解：max 2x1+3x2S.t.195x1+273x

30、2=0,（且x1,x2 整数去掉）,第一步：先按普通LP求解：求得结果：LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)14.65116 VARIABLE VALUE REDUCED COST X1 2.441860 0.000000 X2 3.255814 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.010137 3)0.000000 0.005814 4)1.558140 0.000000,这说明最优值Z不超过14.65,同时令x1=2,x2=3,得Z=13,故13

31、=Z=14.65即Z在(13,14.65),第二步:确定Z的上下界:这说明最优值Z不超过14.65,同时令x1=2,x2=3,得Z=13,故13=3,使得原问题变为两个线性规划问题进行求解.,分支一:LP2max 2x1+3x2S.t.195x1+273x2=0,分支二:LP3max 2x1+3x2S.t.195x1+273x2=3 X1,x2=0,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)13.90000 VARIABLE VALUE REDUCED COST X1 2.000000 0.000000 X2 3.300000

32、0.000000,LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1)14.57143 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.857143 0.000000,第四步,修改上下界:上界为14.57,下界为13.9,其中,LP3取得最大上界,故选取X2分界.X2=2.85,令X2=3,分支一:LP31max 2x1+3x2S.t.195x1+273x2=3 x2=0,分支二:LP32max 2x1+3x2S.t.195x1+273x2=3 x2=3 X1,x2=0,LP O

33、PTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)14.00000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 2.000000 0.000000,无可行解,显然,LP的最优值上界为14.00同时,x1=4,x2=2,满足IP条件,则LP的下界为14.00,算法思想,隐枚举法 分支 求解放松问题 舍弃 变界 分支,最优值比界坏,最优解为整数最优值比界好,最优解为非整数最优值比界好,分支的方法,定界,当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最

34、好解的值则替代原有最好解整数解且目标值大于原有最好解的值则 删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解,选一分支写出并求解放松问题，同时从分支集中删除该分支,判定是否为整数解,初始分支为可行解集，初始界为无穷大,判定是否分支集空,是停止,当前最好解为最优解,是,否,判定最优值是否小于当前界,判定最优值是否小于当前界,是,否,按非整数变量分支并加入分支集,否,是,以最优解替代当前最好解最优值替代当前界,算例,注释,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。,对0-1整数规划分支时,算法思想算法

35、步骤算例,割平面算法,算法思想,由放松问题的可行域向整数规划的可行域逼近方法利用超平面切除要求 整数解保留 放松问题最优值增加,返回,割平面生成方法,条件-保留整数解删除最优解,整数可行解,最优基可行解,正则解,算法步骤,求放松问题的最优基可行解,判断是否为整数解,是停止,得到最优解,否,在单纯性表中加入一列利用对偶单纯性算法求最优解,算 例,(1,1.5),计算软件,整数变量定义 LinDo 一般整数变量:GIN 0-1整数变量:INT LinGo 一般整数变量:GIN(variable_name);0-1整数变量：BIN(variable_name);算例,算 例,max 3 x1+5 x

36、2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2+5 x3=2000endgin x1gin x3,model:max=3*x1+5*x2+4*x3;2*x1+3*x2=1500;2*x2+4*x3=800;3*x1+2*x2+5*x3=2000;gin(x1);gin(x3);end,Global optimal solution found at iteration:3 Objective value:2675.000Variable Value Reduced CostX1 375.0000 0.3333333 X2 250

37、.0000 0.000000 X3 75.00000-4.000000,应用案例分析,人力资源分配问题应急设施选址问题,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,返回,模型假设,每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量,问题分析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案：确定每天工作的人数，由于连续休息2

38、天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数 约束条件：1.每人休息时间2天，自然满足。,3.变量非负约束：,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,模型,计算,model:min=200*x1+200*x2+200*x3+200*x4+200*x5+200*x6+200*x7;x2+x3+x4+x5+x6=12;x3+x4+x5+x6+x7=15;x1+x4+x5+x6+x7=12;x1+x2+x5+x6+x7=14;x1

39、+x2+x3+x6+x7=16;x1+x2+x3+x4+x7=18;x1+x2+x3+x4+x5=19;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);End,返回,Global optimal solution found at iteration:9 Objective value:4400.000 Variable Value Reduced Cost X1 5.000000 0.000000 X2 2.000000 0.000000 X3 8.000000 0.000000 X4 0.000000 0.000000 X5

40、4.000000 0.000000 X6 0.000000 66.66667 X7 3.000000 0.000000,注解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。定义整数变量用函数gin(x1)gin(x7);0-1整数变量为bin(x1),应急选址问题,某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。,问题分析,该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设,问题分析,为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离 约束条件 小区服务约束,问题分析,最远距离约束 中心个数约束目标函数：最远距离 最小,模 型,