经济学第五章整数规划课件

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

2、ming)全部决策变量都必须取整数值。混合整数线性规划(mixed integer linear programming) 决策变量中一部分必须取整数值， 另一部分可以不取整数值。0-1型整数线性规划(zero-one integer linear programming) 例1、 某公司准备投资 50 万元为其产品做广告，广告代理商给公司的有关广告方式的费用和其效果情况如下表，公司面临的管理决策问题是广告总费用不超过 50 万元的基础上选择哪些广告方式，使得潜在顾客数尽可能地多。 广告方式电视台报纸杂志电台 广告费（万元）40152010潜在顾客数（万人）40202510整数规划问题实例 x

3、i = 1 选择第i 种广告方式0 不选择第i种广告方式Max Z = 40 x1 + 20 x2 + 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 点，设备投资估计为

4、 bi 元，每年可获利润估计为 ci 元，但投资总额不能超过 B 元。问公司选择哪几个点可使年总利润最大？ 例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混合泳接力队，怎样选派运动员，

5、方使接力队的游泳成绩最好？运动员仰泳蛙泳蝶泳自由泳甲75.586.866.658.4乙65.866.257.052.8丙67.684.377.859.1丁74.069.460.857.0 设：工序 B 有两种方式完成方式（1）的工时约束: 0.3x1 + 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

6、 若工序 B 采用方式（2）完成1 若工序 B 不采用方式（2）完成于是前面两个互斥的约束条件可以统一为如下三个约束条件： 0.3x1 + 0.5x2 150 + M1y1 0.2x1 + 0.4x2 120 + M2y2 y1 + y2 = 1 其中 M1 ，M2 都是足够大的正数。 有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。 资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012 例5固定费用问题 解：设xj为第j种产品的生产数量，j

7、=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 + 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 三

8、种轴件，其规格与数量如下表，各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床，最少要用多少根圆钢？轴类规格：长度（米）每台机床所需轴件数A3.11B2.12C1.24 例6、模型 分析该问题后，发现较合理的下料方案有：轴类方案1方案2方案3方案4方案5A（3.1）11000B（2.1）10012C（1.2）02421用料长5.25.54.84.55.4余料0.300.710.1 例6、模型 设：xi 采用方案i下料所用的原料根数。Min Z = x1 + x2 + x3 + x4 + x5 x1 + x2 = 100 x1 + x4 + 2x5 = 200 2x2 + 4x3 +

9、 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建厂

10、 模型：（三）整数规划与线性规划的关系 从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。举例说明。例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用图解法求出最优解x13/2, x2 = 10/3且有Z = 29/6x1x233(3/2,10/3) 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)、 (2，3)、(1，4)、(2，4)。 按整数规划约束条件，其可行

11、解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。 显然，它们都不可能是整数规划的最优解。 因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。 如上例：其中（2，2）（3，1）点为最大值，Z=4。 目前，常用的求解整数规划的方法有： 分支定界法和割平面法；对于特别的01规划问题采用隐枚举法 和匈牙利法。（一）基本思路 考虑纯整数问题：整数问题的松弛问题：二、分枝定界法 maxZ=CXAX=bX0(A)IPmaxZ=CXAX=bX0X为整数 (B)LP(B)为(A)的松弛问题。 分枝定界法一般步骤：(1) 先解(A)的松弛问题

12、(B) (2) (B)无可行解(A)无可行解。 (B)最优解符合(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) 剪枝条件: (C)，(D)无可行解 (C)（(D)）对应的目标值Sc (Sd) S0 （极大化） (C)（(D)）对应的目标值Sc (Sd) S0 （极小化） 且解为整数解，令Sc (Sd) S0 且解为非整

13、数解，令(C)，(D)取代 (B) 返回(4)例1：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）例题用图解法求（LP）的最优解，如图所示。x1x233(18/11,40/11)对于x118/111.64， 取值x1 1， 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）的最优解即可。x1x233(

14、18/11,40/11) 先求（LP1）,如图所示。此时在B 点取得最优解。 x11, x2 =3, Z(1)16找到整数解，问题已探明，此枝停止计算。11同理求（LP2） ,如图所示。在C 点取得最优解。即x12, x2 =10/3, Z(2) 56/318.7BAC(2) Z()16 原问题有比（16）更小的最优解，但 x2 不是整数，故利用 3 10/34 加入条件。加入条件： x23, x24 有下式：只要求出（LP3）和（LP4）的最优解即可。x1x233(18/11,40/11)11BAC先求（LP3）,如图所示。此时在D 点取得最优解。即 x112/52.4, x2 =3, Z(

15、3)-87/5 -17.4 Z(5) F 如对 Z(6) 继续分解，其最小值也不会低于15.5 ，问题探明,剪枝。 至此，原问题（IP）的最优解为： x1=2， x2 =3, Z* = Z(5) 17以上的求解过程可以用一个树形图表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4无可行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23x24x12x13例2:用分枝定界法求解整

16、数规划问题LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP5x1=1, x2=2Z(5) 3LP6无可行解x22x23LP3x1=33/14, x2=2Z(3) 61/14LP4无可行解x22x23LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x12x13LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9LP3x1=33/14, x2=2Z(3) 6

17、1/14LP4无可行解LP7x1=2, x2=2Z(7) 4LP8x1=3, x2=1Z(8) 4x11x12x22x23x12x133200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例3、用分枝定界法求解整数规划问题（单纯形法） x1=13/4 x2=5/2 Z(0) =59/414.75 选 x2 进行分枝，即增加两个约束，2 x2

18、 3 有下式： 分别在(LP1)和(LP2)中引入松弛变量x5和x6 ，将新加约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(

19、1) =29/2=14.5继续分枝，加入约束 3 x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝接(LP1)继续分

20、枝，加入约束 4 x1 3，有下式：分别引入松弛变量x7 和 x8 ，然后进行计算。CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整数解，问题已探明

21、，停止计算。LP3CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整数解，问题已探明，停止计算。LP4树形图如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14练习：用分枝定界法求解整数规划问题 （单纯形法）cj-1-5000cBxBbx1x2x3x4x50 x32-111000 x4 30560100 x5410001-Z-1-5000cj-1-5000cBxBbx1