《4.1-3整数规划》由会员分享，可在线阅读，更多相关《4.1-3整数规划（44页珍藏版）》请在金锄头文库上搜索。
1、Chapter4 Chapter4 整数规划整数规划( Integer Programming )( Integer Programming )整数规划的特点及分类分支定界法0-1规划指派问题本章主要内容：本章主要内容：Page 2整数规划的特点及分类整数规划的特点及分类第一节整数规划的特点及分类Page 3整数规划的特点及分类整数规划的特点及分类整数规划（简称：整数规划（简称：ILPILP）要求一部分或全部决策变量取整数值的线性规划问题称 为整数线性规划。整数线性规划数学模型的一般形式：Page 4整数规划的特点及分类整数规划的特点及分类整数线性规划问题的种类：整数线性规划问题的种类：纯整数
2、线性规划：指全部决策变量都必须取整数值的整数 线性规划。混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。Page 5整数规划的特点及分类整数规划的特点及分类例4.1 设整数规划问题如下首先不考虑整数约束，得到对应的线性规划问题Page 6整数规划的特点及分类整数规划的特点及分类用图解法求出最优解为：x13/2, x2 = 10/3，且有Z = 29/6现求整数解(最优解):如用舍 入取整法可得到4个点即(1， 3),(2，3),(1，4),(2，4)。显然， 它们都不可能是整数规划的最优 解
3、。x1x233(3/2,10/3)按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(2,2),(3,1)点的目 标函数值最大，即为Z=4。 枚举法Page 7整数规划的特点及分类整数规划的特点及分类整数规划问题的求解方法：分支定界法和割平面法匈牙利法（指派问题）Page 8第二节分支定界法Page 9分支定界法分支定界法例4.4 用分支定界法求解整数规划问题解：首先去掉整数约束，变成一般线性规划问题LPILPPage 10分支定界法分支定界法用图解法求对应LP问题的最优解，如图所示。x1x23(18/11,40/
4、11)21123x118/11, x2 =40/11Z=218/11(19.8)对于x118/111.64，取值x1 1， x1 2（或对于x2 =40/11 3.64，取值x2 3 ，x2 4）先将（LP）划分为（LP1） 和（LP2）,取x1 1, x1 2挖掉Page 11分支定界法分支定界法分支：分别求出（LP1）和（LP2）的最优解。Page 12分支定界法分支定界法先求LP1,如图所示。此时在B 点取得最优解。x11, x2 =3, Z(1)16找到整数解，问题已探明，此 枝停止计算。x1x233(18/11,40/11)11BA C同理求LP2,如图所示。在C 点 取得最优解。即
5、:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原问题有比16更好的最优解 ，但 x2 不是整数，故继续分 支。Page 13分支定界法分支定界法在IP2中分别再加入条件： x23, x24 得下式两支：分别求出LP21和LP22的最优解Page 14分支定界法分支定界法x1x233(18/11,40/11)11BACD先求LP21,如图所示。此时D 在点取得最优解。即 x112/52.4, x2 =3, Z(21)87/517.4 Z(1)=16但x112/5不是整数，可继续 分枝。即 x12, x13 。求LP22，如图所示。无可行解 ，故不再分枝。Pag
6、e 15分支定界法分支定界法在（LP21）的基础上继续分枝。加入条件 x12, x13有下式 ：分别求出（LP211）和（LP212）的最优解Page 16分支定界法分支定界法x1x233(18/11,40/11)11BACDEF先求（LP211）,如图所示。此时 在E点取得最优解。即 x12, x2 =3, Z(211)17找到整数解，问题已探明，此枝 停止计算。求（LP212），如图所示。此时 F在点取得最优解。即x13, x2 =2.5, Z(212)31/215.5 Z(211) 如对LP212继续分解，其最大值 也不会大于15.5 ，问题探明,剪 枝。Page 17分支定界法分支定界
7、法原整数规划问题的最 优解为: x1=2, x2 =3, Z* =17以上的求解过程可以 用一个树形图表示如 右：LP1 x1=1, x2=3 Z(1) 16LP x1=18/11, x2=40/11 Z(0) 19.8LP2 x1=2, x2=10/3 Z(2) 18.5LP21 x1=12/5, x2=3 Z(21) 17.4LP22 无可 行解LP211 x1=2, x2=3 Z(211) 17LP212 x1=3, x2=5/2 Z(212) 15.5x11x12x23x24x12x13Page 18分支定界法分支定界法1）求整数规划的对应问题最优解；若对应问题的最优解满足整数要求，得
8、到整数规划的最优解,否则转下 一步； 2）分支与定界： 任意选一个非整数解的变量xi，在对应问题中加上约束： xixi 和 xixi+1组成两个新问题，称为分支。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数 值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若 还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝， 再检查，直到得到最优解。分支定界法的解题步骤：分支定界法的解题步骤：Page 19求解分支时可能遇到的几种情况：分支定界法分支定界法1. 无可行解-直接减枝2. 得到整数最优解- 不再分支，进行比较2. 得到非整数最优解若对应函数值 -
9、若对应函数值 -直接减枝继续分支Page 20在不断地分支，定界中得到整数规划的最优解如何定界：分支定界法分支定界法取已知的整数可行解的最优目标函数值取当前层中所有分支的最优目标函数值指整数规划的最优目标函数值Page 21分支定界法分支定界法例4.5 用分枝定界法求解解: 先求对应的线性规划（记为LP0）用图解法得到最优解X(3.57,7.14),Z0=35.7,如下图所示。Page 22分支定界法分支定界法1010松弛问题LP0的最优解 X=(3.57,7.14),Z0=35.7x1x2oABCPage 23分支定界法分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z
10、1=34.8LP2:X=(4,6.5),Z2=35.5Page 24分支定界法分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336Page 25分支定界法分支定界法10x1x2oACLP1346LP211:X=(4,6), Z211=34LP212:X=(5,5) ,Z212=355LP212Page 26分支定界法分支定界法上述分枝过程可用下图表示：上述分枝过程可用下图表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x13x14LP21:X=(4.33,6)
11、Z21=35.33x26LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x14x15LP22 无可行解x27Page 27小结小结学习要点： 掌握一般整数规划问题概念及模型结构 掌握分支定界法原理 能够用分支定界法求解一般整数规划问题在不断地分支与定界 中寻找最优整数解。Page 28第三节0-1整数规划Page 290-1型整数线性规划（决策变量只能取值0或1的整数线性规划）背包问题运动员选拔问题选址问题固定费用问题整数规划的应用整数规划的应用（0-10-1规划）规划）Page 30例1. （背包问题）一个徒步旅行者要在背包中选择一些最有价值的物品 携带。他最
12、多能携带 115 kg的物品。现有5件物品，分别 重54，35，57，46，19 (kg)，其价值依次为7，5，9 ，6 ，3。问该旅行者携带哪些物品，使总价值最大？解：设则有：整数规划的应用整数规划的应用（0-10-1规划）规划）Page 31例2 （运动员选拔问题）某篮球队拟从编号为1,2，,6的6名预备运动员中挑选出3 名正式队员，要求他们的平均身高尽量高。此外，入选 运动员还需符合以下条件：（1）至少一名后卫（2）2号与5号至多只能入选1名（3）最多入选一名中锋（4）若2号或4号入选，则6号不能入选整数规划的应用整数规划的应用（0-10-1规划）规划）编号位置身高1中锋1.932中锋1
13、.913前锋1.874前锋1.865后卫1.806后卫1.85Page 32（1）至少一名后卫（2）2号与5号至多只能入选1名（3）最多入选一名中锋（4）若2号或4号入选，则6号不 能入选整数规划的应用整数规划的应用（0-10-1规划）规划）Page 33例3. 现有资金总额为B。可供选择的投资项目有n个，项目j 所需投资额和预期收益分别为aj和cj（j1,2,.,n），此外由 于种种原因，有三个附加条件：若选择项目1，就必须同时选择项目2。反之不一定项目3和4中至少选择一个；项目5,6,7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。整数规划的应用整数规划的应用（0-10-1规
14、划）规划）Page 34解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为：投资问题可以表示为：整数规划的应用整数规划的应用（0-10-1规划）规划）Page 35例4 （选址问题）现有如图所示的 A,B,C,D,E共5个新开发的小区，其 间都有主要干道相连接。现为救火的需要，需建立一个 消防系统，要求在15分钟内能及时到达任一小区。问如 何设置消防站，既能满足消防要求，又使设置的消防站 数量最少？整数规划的应用整数规划的应用（0-10-1规划）规划）ACDEB101515202515Page 36ABCDEA010153030B100
15、253520C152501530D303515015E302030150整数规划的应用整数规划的应用（0-10-1规划）规划）Page 37整数规划的应用整数规划的应用（0-10-1规划）规划）例5. 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再 建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需 求地的单位物资运费cij，见下表：B1B2B3B4年生产能力 A12934400 A28357600 A37612200 A44525200 年需求量350400300150工厂A3或A4开工后，每年的
16、生产费用估计分别为1200万或1500万 元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用 最少。Page 38解：这是一个物资运输问题，特点是事先不能确定应该建A3 还是A4中哪一个，因而不知道新厂投产后的实际生产物资。 为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。则该规划问题的数学模型可以表示为：整数规划的应用整数规划的应用（0-10-1规划）规划）Page 39混合整数规划问题整数规划的应用整数规划的应用（0-10-1规划）规划）Page 40整数规划的应用整数规划的应用（0-10-1规划）规划）例6. 某地区有甲乙两座城镇
