第五章整数规划.ppt

《第五章整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、整数规划(IntegerProgramming)整数规划的模型分支定界法0－1整数规划指派问题9/16/20211在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。9/16/20212整数线性规划数学模型的一般形式整数规划（IP）松弛问题整数线性规划（ILP）的数学模型：一、整数规划的数学模型及解的特点5.1c5.1d5.1

2、a5.1b9/16/20213——决策变量只能取值0或1。整数规划问题的类型纯整数线性规划(pureintegerlinearprogramming)——全部决策变量都必须取整数值。混合整数线性规划(mixedintegerlinearprogramming)——决策变量中一部分必须取整数值，另一部分可以不取整数值。0-1型整数线性规划(zero-oneintegerlinearprogramming)9/16/20214例1、某公司准备投资50万元为其产品做广告，广告代理商给公司的有关广告方式的费用和

3、其效果情况如下表，公司面临的管理决策问题是广告总费用不超过50万元的基础上选择哪些广告方式，使得潜在顾客数尽可能地多。广告方式电视台报纸杂志电台广告费（万元）40152010潜在顾客数（万人）40202510整数规划问题实例9/16/20215xi=1选择第i种广告方式0不选择第i种广告方式MaxZ=40x1+20x2+25x3+10x440x1+15x2+20x3+10x4≤50x1，x2，x3，x4=0或1例1、模型设：xi（i=1,2,3,4）——表示4种广告方式。9/16/20216例2、某公司

4、在城市的东、西、南三区建立门市部。拟议中有7个位置（地点）Ai（i=1，2，…，7）可供选择。公司规定：在东区，由A1，A2，A3三个点中至多选两个；在南区，由A4，A5两个点中至少选一个；在西区，由A6，A7两个点中至少选一个。如果选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问公司选择哪几个点可使年总利润最大？9/16/20217例2、模型设：Ai=1选择Ai建立门市0不选择Ai建立门市MaxZ=∑ciAi∑biAi≤BA1+A2+A3≤2A4+A5≥1A6+A

5、7≥1Ai=0或1，（i=1，2，3，4，5，6，7）9/16/20218例某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为S1…S10，相应的钻探费用为c1…c10，并且井位选择上要满足下列限制条件：①或选择S1和S7，或选择S8；②选择了S3或S4就不能选S5，反之，选了S5，则不能选S3或S4；③在S5~S8中最多选两个。建立这个问题的0-1型整数规划模型9/16/20219解：令（i＝1，…，10）9/16/202110设：工序B有两种方式完成方

6、式（1）的工时约束:0.3X1+0.5X2≤150方式（2）的工时约束:0.2X1+0.4X2≤120问题是完成工序B只能从两种方式中任选一种，如何将这两个互斥的约束条件统一在一个线性规划模型中呢？例3、应用0-1变量解决含互斥约束条件问题9/16/202111例3、模型引入0-1变量y1=0若工序B采用方式（1）完成1若工序B不采用方式（1）完成y2=0若工序B采用方式（2）完成1若工序B不采用方式（2）完成于是前面两个互斥的约束条件可以统一为如下三个约束条件：0.3X1+0.5X2≤150+M1y1

7、0.2X1+0.4X2≤120+M2y2y1+y2=1其中M1，M2都是足够大的正数。9/16/202112有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。ⅠⅡⅢ资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012例4．固定费用问题9/16/202113解：设xj为第j种产品的生产数量，j=1,2,3；yj=1当生产第j种产品,即xj＞0时0当不生产第

8、j种产品即xj=0时引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj为0--1变量，i=1,2,39/16/202114例5、人员时间安排某航空公司希望更有效地安排售票员的工作时