当前位置：文档之家 › 第五章整数规划

第五章整数规划

  • 格式：ppt
  • 大小：427.50 KB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

整数规划.

整数规划.

5.2 整数规划的解题思路
1. 当人们开始接触整数规划问题时，常常会 有如下两种初始想法： 想法一：因为可行方案的数目常常是有限 的，因此，从理论上讲，经过一一比较后， 总能求得最好方案。例如背包问题充其量有 2n-1种方式。但是这种穷尽法是行不通的。假 设一台计算机每秒比较一百万个方式，那么 要比较20！种方式，大约需要800年，要比较 260种方式，需要360多个世纪。
可行域=空集
max f = x1 + 4 x2 s.t. - 2 x1 + 3x2 ≤3 x1 + 2 x2 ≤8 x2 ≤2 x1 , x2 ≥0 解得 x1 = 4, x2 = 2
2. 分枝定界法的最优解步骤：
第一步：首先将整数规划问题当作一般的线性规划问 题处理，如果得到的解是整数解，则停止，否则转入第 二步； 第二步：增加整数约束，分枝，对分枝用线性规划求 解。如果得到的最优整数解的目标函数比其他分枝的最 优整数解的目标函数值都要好，则停止，否则转第三步； 第三步：（Ⅰ）若未获整数解的目标函数值比同层的 分枝要差，则暂停分枝。 （Ⅱ）如果其他枝的整数解目标函数值比这样要好，此 枝再也不用再分枝。 （Ⅲ）如果其他分枝的整数解目标函数比这枝要差，回 过头来继续对此枝分枝，希望找到一个使目标函数值有 所改善的整数解，转回第二步。
原始结点
图示：
上述说法可用图表示
max f = x1 + 4 x2 - 2 x1 + 3x2 ≤3
s.t.
x1 + 2 x2 ≤8
x1 , x2 ≥0 解 x1 = 2.5, x2 = 2.7
分枝 1 分枝 2
x2 ≥3
结点 1
x2 ≤2
原始结点
max f = x1 + 4 x2 s.t. x + 2 x ≤8 1 2 - 2 x1 + 3x2 ≤3 x2 ≥3 x1 , x2 ≥0

第五章整数规划

第五章整数规划

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96m ax ,0,8.421===z x x 。

用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z ；而A 的任意可行解的目标函数值是*z的一个下界z ，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82,①② ③ ④ ⑤=0z 356（见下图）。

第五章____整数规划

第五章____整数规划

例5.2
选址问题
现准备在几个地点建厂，可供选择的地点有 A1, A2, …, Am，它们的 生产能力分别是 a1, a2, …, am（假设生产同一种产品）.第 i 个工厂 的建设费用为 fi ( i = 1, 2, …, m)，并有 n 个地点 B1, B2, …, Bn， 需要销售这种产品，其销量分别为 b1, b2, …, bn，从工厂 Ai 运往销 地 Bj 的单位运费为 cij（如表所示）.试决定在哪里地方建厂，既能满 足各地的要求，又能使总建设费和总运输费用最省？
min z
i 1
m
c
j 1
n
ij
xij f i yi
i 1
m
s.t.
x
j 1
n
ij
ai yi
i 1, 2,, m (5.2)
xij 0, yi 0或1
i 1, 2, , m; j 1, 2, , n
在本例中，xij可以取非负实数，而yi只能取0或1，这类问题称为 混合整数规划问题.
二、割平面法
整数规划的割平面法是一个有效的求解整数规划的方法，因系 R.E Gomory提出，故称Gomory割平面法（Gomory Cutting Plane Algorithm）.
该方法的基本思想是首先求解整数规划（IP）对应的松弛问题 （LP），如果（LP）的最优解不是整数解，则逐次增加一个新约 束（即割平面），它能割去松弛问题可行域中不含整数解的区域. 逐次切割，直到得到一个整数最优极点（即整数解）为止.
如果其最优解不符合整数条件，则求出整数规划的上下界用增加约 束条件的方法，并把相应的线性规划的可行域分成子区域（称为分 枝），再求解这些子区域上的线性规划问题.

第5章 整数规划

第5章 整数规划

第五章 整数规划整数规划（integer programming ）亦称整数线性规划，它实质上是在线性规划的基础上，给一些或全部决策变量附加取整约束得到的。

在许多情况下，我们都可以把规划问题的决策变量看成是连续的变量；但在某些情况下，规划问题的决策变量 却被要求一定是整数。

例如，完成某项工作所需要的人数或设备台数，进入市场销售的商品件数，以及某一机械设备维修的次数等。

为了满足整数解的要求，最容易想到的办法就是把求得的非整数解进行四舍五入处理来得到整数解，但这往往是行不通的。

舍入处理会出现两方面的问题：一是化整后的解根本不是可行解；二是化整后的解虽是可行解，但并非是最优解。

因此，有必要另行研究整数规划的求解问题。

在线性规划的基础上，要求所有变量都取整的规划问题称为纯整数规划问题（pure integer programming ）；如果仅仅是要求一部分变量取整，则称为混合整数规划问题（mixed integer programming ）。

根据整数规划的定义，可将整数规划的数学模型表示为：0,;{min ≥==X b AX CX w 且（部分）为整数}。

显而易见，整数规划的可行域是其相应线性规划可行域的子集。

§1分枝定界法分枝定界法（branch and bound method ）是求解整数规划常用的一种方法，它具有灵活且便于用计算机求解等优点。

它的一般思想是利用连续的（线性规划）模型来求解非连续的（整数规划）问题。

假定k x 是一个有取整约束的变量，而其最优连续值*k x 是非整数；那么在][*k x （表示*k x 的取整值）和1][*+k x 之间不可能包括任何可行整数解。

因此，k x 的可行整数值必然满足][*k k x x ≤或1][*+≥k k x x 之一。

把这两个条件分别加到原线性规划的解空间上，产生两个互斥的线性规划子问题。

实际上这一过程利用了整数约束条件，在“分割”时删除了不包含可行整数点的部分连续空间（1][][**+<<k k k x x x ）。

运筹学 第五章 整数规划

运筹学 第五章 整数规划

M是足够大的整数，y 是0-1变量
14
f(x)-5 0
f(x) 0
(1)
(2)
-f(x)+5 M（1-y)
f(x) My
(3)
(4)
当y=1时,(1)(3)无差别,(4)式显然成立;
当y=0时,(2)(4)无差别,(3)式显然成立。
以上方法可以处理绝对值形式的约束
f(x) a (a>0)
31
5.1 分枝定界法 （Branch and Bound Method)
原问题的松驰问题： 任何整数规划（IP），凡放弃某些约束 条件（如整数要求）后，所得到的问题 （P） 都称为（IP）的松驰问题。 最通常的松驰问题是放弃变量的整数性 要求后，（P）为线性规划问题。
32
去掉整数约束,用单纯形法 IP LP
23
解法概述
当人们开始接触整数规划问题时，常会有 如下两种初始想法： 因为可行方案数目有限，因此经过穷举 法一一比较后，总能求出最好方案，例如， 背包问题充其量有2n种方式，实际上这种 方法是不可行。
设想计算机每秒能比较1000000个方式，那 么比较完260种方式，大约需要360世纪。
24
先放弃变量的整数性要求，解一个 线性规划问题，然后用“四舍五入” 法取整数解，这种方法，只有在变量 的取值很大时，才有成功的可能性， 而当变量的取值较小时，特别是0-1规 划时，往往不能成功。
Yes xI* = xl*
xl*
判别是否整数解
No 去掉非整数域 多个LP ……
33
分枝定界法步骤
一般求解对应的松驰问题，可能会出现 下面几种情况：
若所得的最优解的各分量恰好是整数， 则这个解也是原整数规划的最优解，计 算结束。

第五章-整数规划

第五章-整数规划

在E点取得最优解。即
x2
x1＝2, x2 =3, Z(211)＝－17
找到整数解，问题已探明，此枝 3
停止计算。
求（LP212），如图所示。此时
F在点取得最优解。即x1＝3, x2
=2.5,
1
Z(212)＝－31/2≈－15.5 > Z(211)
如对LP212继续分解，其最小值
也不会低于－15.5 ，问题探明,
例5.2 现有资金总额为B。可供选择的投资项目有n个，项目j 所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由 于种种原因，有三个附加条件：
若选择项目1，就必须同时选择项目2。反之不一定; 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。
现求整数解(最优解):如用舍
入取整法可得到4个点即(1，3),(2 x2
⑴
⑵
，3),(1，4),(2，4)。显然，它们 都不可能是整数规划的最优解。 3
(3/2,10/3)
按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右
图所示。其中(2,2),(3,1)点的目 标函数值最大，即为Z=4。
考虑纯整数规划问题：
设其中aij和bi皆为整数（若不为整数时，可乘上 一个倍数化为整数）。
割平面法（纯整数）
割平面法是R.E.Gomory于1958年提出的一种方法， 它主要用于求解纯ILP。
割平面法是用增加新的约束来切割可行域，增加的新 约束称为割平面方程或切割方程。其基本思路为：
若其松弛问题的最优解X*不满足整数约束，则从X*的 非整分量中选取一个，用以构造一个线性约束条件，将其加 入原松弛问题中，形成一个新的线性规划，然后求解之。若 新的最优解满足整数要求，则它就是整数规划的最优解；否 则重复上述步骤，直到获得整数最优解为止。

第五章整数规划【模板】

第五章整数规划【模板】

第五章整数规划§1整数规划的数学模型及特点要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。

其模型为：Max(或min)z=s.t若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。

§5 指派问题一．指派问题的标准形式及数学模型在现实生活中，有各种性质的指派问题。

例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。

诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。

由于指派问题的多样性，有必要定义指派问题的标准形式。

指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。

为了建立标准指派问题的数学模型，引入个0-1变量：这样，问题的数学模型可写成（5.1）s.t （5.3）其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。

注：○1指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n的运输问题。

○2有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。

并称矩阵C= =（5.5）为效率矩阵（或价值系数矩阵）。

并称决策变量排成的n×n矩阵X== （5.6）为决策变量矩阵。

(5.6)的特征是它有n个1，其它都是0。

这n个1位于不同行、不同列。

每一种情况为指派问题的一个可行解。

共n!个解。

其总的费用 z =C⊙X这里的⊙表示两矩阵对应元素的积，然后相加。

问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵C=则X（1）=，X（2）=都是指派问题的最优解例12/P-149：某商业公司计划开办五家新商店。

为了尽早建成营业，商业公司决定由5家建筑公司分别承建。

第五章 整数规划

第五章 整数规划
整数规划
1.整数规划的数学模型及解的特点 2.分支定界法、割平面法 3.0-1整数规划 4.指派问题
1.整数规划的数学模型及解的特点

整数规划数学模型的一般形式
一部分或全部决策变量取整数值的规划问题 ——整数规划 整数规划中不考虑整数条件是对应的规划问题 ——该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 ——整数线性规划
(0,1,0,0,0)
Z8=2< Z5 ，不可 行，不可行子域， 停止分支。
Z7=9> Z5 ，停止分支。
(0,1,0,0,0)
4. 指派问题(assignment

problem)
4.1指派问题的标准 形式及其数学模型 4.2匈牙利解法 4.3一般的指派问题


指派问题的标准形式的提出？

在我们现实生活中，常有 各种性质的指派问题。例 如：应如何分配若干项工 作给若干个人（或部门） 来完成，以达到总体的最 佳效果等等。由于指派问 题的多样性，我们有必要 定义指派问题的标准形式 。
x2 2
x2 1.57 z 0 z 2 341 z 349
x2 3
z 340 z 341
B3 : x1 4.00 x2 2.00 z3 340
B4 : x1 1.42 x2 3.00 z 4 327
x2 1
*
x2 2
B5 : x1 5.44 B : 6 z z 340 x2 1.00 z5 308 无可行解

（4） 检验解是否可行。如可行，已得一个可行解，计算并
记下它的z值，并停止分枝，若子域都检验过，转步骤（7） ，否则转步骤（6）。因继续分枝，即使得到可行解，目标 函数值也比记下的z值大，不会是最优解；如不可行，进行 步骤（5）。

第五章整数规划

第五章整数规划

第五章 整数规划
本例问题B 及问题B 本例问题B1及问题B2的模型及求解结果如下 问题B 问题B 问题B1 问题B2
m z = 10x1 + 20x2 ax 5x1 + 8x2 ≤ 60 x ≤ 8 1 s.t .x2 ≤ 4 x ≤ 5 1 x1 , x2 ≥ 0
m z = 10x1 + 20x2 ax 5x1 + 8x2 ≤ 60 x ≤ 8 1 s.t.x2 ≤ 4 x ≥ 6 1 x1 , x2 ≥ 0
m z = 20x1 + 10x2 ax 5x1 + 4x2 ≤ 24 s.t. 2x1 + 5x2 ≤ 13 x , x ≥ 0, x , x 为整数 1 2 1 2 m z = 20x1 + 10x2 ax 5x1 + 4x2 ≤ 24 s.t.2x1 + 5x2 ≤ 13 x , x ≥ 0 1 2
第五章 整数规划
B5解为：X5*=(7,3)T，f5*=130；B6解为：X6*=(8,2.5)T， 解为： =130； 解为： f6*=130。因为此时B5的解为整数解，因此修改下界为130， =130。因为此时B 的解为整数解，因此修改下界为130， 而此时所有未被分支的问题（ 而此时所有未被分支的问题（B4,B5,B6)的目标函数中的最小 值为f =130，故修改上界为Z=130。 值为f5*=f6*=130，故修改上界为Z=130。 6.结束准则 6.结束准则 当所有的分支均已查明（或为无可行解— 树枝” 当所有的分支均已查明（或为无可行解—“树枝”，或为 整数可行解— 树叶” 或其目标函数值不大于下界— 整数可行解—“树叶”，或其目标函数值不大于下界— 枯枝”），且此时 且此时Z=Z，则已求得了原问题的整数最优解， “枯枝”），且此时Z=Z，则已求得了原问题的整数最优解， 即目标函数下界Z的那个整数。 即目标函数下界Z的那个整数。 在本例中，当解完一对分支B5、B6后，得到Z=Z=130，又 在本例中，当解完一对分支B 得到Z=Z=130， B5是“树叶”，B6为“枯枝”，因此所有分支(B1,B4,B5,B6) 树叶” 枯枝” 因此所有分支(B 均已查明，故已求得问题A 的最优解： 均已查明，故已求得问题A0的最优解：

运筹学第五章 整数规划

运筹学第五章 整数规划

2、0-1型变量常用来表示是否处于某个特定状态
例5.6
有三种资源被用于生产三种产品，资源量、产 品单件可变费用及售价、资源单耗量及组织三种产品 生产的固定费用见下表。要求制定一个生产计划，使 总收益最大。
0-1型变量常用来表示两个选项中非此即彼的选择

例5.7 用4台机床加工3件产品。各产品的机床加工顺序，以及产品在机 床上的加工工时见下表，且要求工件二的总工时不超过d。现要求确定 各件产品在机床上的加工方案,使在最短的时间内加工完全部产品.
A 甲 15 B 17 C 21 D 24
乙
丙 丁
19
26 19
23
17 21
22
16 23
18
19 17
解：令 xij=
1 若指派第i 人做第j 事 （i, j=1, …, n） 0 若不指派第i 人做第j 事
每个人只能完 成一项任务
满足约束条件的可行解 也可写成矩阵形式，称 为解矩阵。如例5.9的一 个可行解矩阵是:
每行减该行最小数
0 1 10 2
2 5 1 4
6 4 0 6
9 0 3 0
每列减该列最小数
0 1 10 2
1 4 0 3
6 4 0 6
产品1
产品2
产品3
a11 机床1 a21 机床1
a22 机床2 a32 机床2
a13 机床3
a33 机床3
a14 机床4 a24 机床4
xij表示第i种产品在第j台机床上加工的开始时间。 同一件产品在下一台机床上加工的开始时间不得早 1 同一 于在上一台机床上加工的结束时间 件产品 产品1：x11+a11x13 及 x13+a13x14 在不同 机床上 产品2：x21+a21x22 及 x22+a22x24 的加工 产品3：x32+a32x33 顺序

5_整数规划_0421

5_整数规划_0421
x ij ì 1 包装袋i 在旅行包j中 ï ï =í (i = 1, 2,...,15; j = 1, 2, 3) ï 0 包装袋 i 不在旅行包 j 中 ï ï î
典型的整数规划问题
背包问题
由于每个旅行包的容积确定，故装入第j个旅行包中的所有包装袋的容积的总 和必须小于第j个旅行包的容积，即需要满足约束条件：
*
f = 5x1 + 8x 2
整数规划的求解
求解思路
由上述分析可知，舍入法一般是不可取的，当然如果对应线性规划的最优解恰 好满足整数要求，则该解也是整数规划的最优解，那么何时才能满足此要求呢？ 我们直接给出一个结论： 假设由整数规划问题除去整数要求之后得到的线性规划标准型中，等式约 束个数等于决策变量个数(m=n)，则此时的等式约束构成一个线性方程组 Ax=b，如果det(A) = 1或-1，则解x一定是整数向量，当然这种情况在解决实 际问题的过程中一般还是比较少见的。 对于整数规划问题的解法，一般有利用分解技术的算法和不利用分解技术的算 法
3
我们确定打包方案的原则就是使得 f 取得最小值，故综合以上分析，该背包 15 3 ì æ ö ï 问题的数学模型为： ç ï min f = ÷ p ç1 x ÷
ï ï ï ï ï ï ï ï s.t. ï ï ï ï ï ï í ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï ï î
j =1
典型的整数规划问题
背包问题
我们的目标就是使得在到达A地之后，所买物品的价格最低，即不在旅行包中 的包装袋的总价格最低，如果某包装袋i不在旅行包中，则有：å x ij = 0 故其价格
3 j =1 æ ö ÷ ç 1 - å x ij ÷ 可以用pi ç 来表示，故所有不在旅行包中的包装袋的价值f可表达如下 ÷ ç ÷ ç è ø j =1 15 3 æ ö ÷ ç f = å pi ç 1 x ij ÷ å ÷ ç ÷ ç è ø i =8 j =1

整数规划

整数规划

√
√ × √
×
√ × ×
√
√ √ √
√
√ √ √ √ 8 8
（二）0－1 整数规划——隐枚举法
首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为
一个过滤条件，优于其值的再判断约束条件，直到找到最优解。
满足约束条件（是∨ x1 . x2. x3 ( 0. ( 0. 0. 0. 0 ) 1) √ √ (1) √ √ (2) √ √ (3) √ √ 否×） (4)
目标函数： Max z = 2x1 +3 x2 约束条件： 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1≥3 x2≥3 x1，x2 ≥ 0
无可行解
（四）比较子问题的最优解，判断是否还要继续分枝 因为Z21=14大于Z1=13.90，所以x1=3，x2=2是原 问题的最优整数解
过滤 条件
0 5 -2 3 3
max Z 3 x1 2 x2 5 x3 x1 2 x2 x3 2 (1) x1 4 x2 x3 4 (2) 3 (3) x1 x2 4 x2 x3 6 (4) x1 , x2 , x3 0或1
第五章 整数规划
在整数规划中，如果所有的变量都为非负整数，则 称为纯整数规划问题；如果有一部分变量为负整数，则 称之为混合整数规划问题。在整数规划中，如果变量的 取值只限于0和1，这样的变量我们称之为0-1变量。在 纯整数规划和混合整数规划问题中，如果所有的变量都 为0-1变量，则称之为0-1规划。 求整数解的线性规划问题，不是用四舍五入法或去 尾法对线性规划的非整数解加以处理都能解决的，而要 用整数规划的方法加以解决。

第五章 整数规划

第五章 整数规划

令 x3′=1-x3, x4′=1-x4, x5′=1-x5，得 Max z=2x2+4x3′+5x5′+7x4′+8x1-16 3x2- x3′- 3x5′- 2x4′+3x1≤-2 ① 3x2+2x3′- x5′+ x4′+5x1≤6 ② x2, x3′,x5′,x4′,x1 =0或1
z=8,不可行 x2 =x3′=x5′ = x4
若某行(列)已有0元素，那就不必再减了。例1的计算为：
2 15 10 4 ) 9 14 8 7 4 14 15 16 13 11 9 13
( c ij
-2 -4 -9 -7
0 6 0 0
13 0 0 1
11 10 7 4
2 11 4 2
R0: z0=356 x1=4.81 x2=1.82
x1 ≤4
x1≥5
R2:z2=341 x1=5.00 x2=1.57 x1 ≤1 x1≥2
R1:z1=349 问题R2为: x1=4.00 Max z=40x1+90x2 x2=2.10 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x2 ≤2 x2≥3 x1,x2 ≥ 0
指派问题的数学模型可写成如下页形式：
min z

i1 j1
n
n
c ij x ij
第j项工作由 一个人做 第i人做 一项工作

i1
n
x ij 1 x ij 1
( j 1 , , n)

j1
n
( i 1 , , n ) (i 1, , n; j 1, , n)

第五章 整数规划(运筹学教程)

第五章 整数规划(运筹学教程)

什么叫0-1规划
• 0-1型整数规划是整数规划中的特殊情况， 它的变量xi仅取0或1，这时xi称为0-1变量 或二进制变量（binary), • xi仅取0或1这个条件可由下述约束条件所 取代： xi≤1, xi ≥0， Xi整数。 • 但是，0-1变量还有许多其它作用。 • 下面举例说明。
4.1 引入0-1变量的实际问题
定界
0≤ Z≤349
定界 340≤ Z≤341
Z3=340
Z4=327
B5（x2≤1）最优解 X1=5,x2=1.57 Z2=308 B6（x2≥2） 无可行解
定界 340≤ Z≤340
§3 割平面法
• 1、分枝定界法本质上是一种对线性规划可行域的 分割方法，只是分割方式比较单一和规范。每次从 对应线性规划的最优解出发，选定某个取非整数值 的变量，挖掉其中的小数部分，将原可行域一分为 二。如此反复进行，直到发现最优整数解为止。 • 2、割平面法的思路也是采用求解对应线性规划的 方法去解整数规划的问题。通过增加适当的约束条 件，从原可行域中切割掉不含整数解的部分。但其 切割方式灵活多样，每次切割可以切一刀，也可以 同时切几刀。旨在造成一个具有整数坐标的顶点， 恰好对应着原问题的最优解
B5, B6
图5-4
B1(x1≤4）最优解
X1=4,x2=2.1 Z1=349 B3(x2≤2）最优解 X1=4,x2=2
B最优解
定界 0≤ Z≤356
X1=4.81,x2=1.82
Z0=356
B2（x1≥5）最优解
X1=5,x2=1.57 Z2=341 B4(x2≥3）最优解 X1=1.42,x2=3
最优解 X1=4,x2=2：整数可行解 Z3=340 最优解 X1=1.42,x2=3

运筹学课件 第5章：整数规划

运筹学课件 第5章：整数规划

依照决策变量取整要求的不同，整数规划可分为纯 整数规划/全整数规划、混合整数规划、0－1整数规划
整数规划解的性质
求解整数规划问题
max Z 3 x1 2 x2 2 x1 x2 9 ( IP)2 x1 3 x2 14 x1 , x2 0且为整数
分析：考虑对应的线性规划问题(LP)
b
x1
2
2 3
x2
1
3 2
x3
1
0 0
x4
0
1 0
b
x1
1
0 0
x2
0
1 0
x3
3/4
-1/2
x4
-1/4 1/2
0
0
x3 9 x4 14
9/2
14/2
3
2
x1 13/4 x2 5/2
-5/4
-1/4
初始表
最终表
可见，最优解为x1=3.25 x2=2.5 z(0) =59/4=14.75
选 x2 进行分枝，即增加两个约束x2≤2 和x2 ≥3 ，则
max Z 3 x1 2 x2 2 x1 x2 9 2 x 3 x 14 2 ( IP1) 1 x2 2 x1 , x2 0且为整数
max Z 3 x1 2 x2 2 x1 x2 9 2 x 3 x 14 2 ( IP2) 1 x2 3 x1 , x2 0且为整数
b
7/2 2 1 3 -29/2 7/2 2 1 -1/2 -29/2
x1
1 0 0 1 0 1 0 0 0 0
x2
0 1 0 0 0 0 1 0 0 0
x3
1/2 0 -1 0 -3/2 1/2 0 -1 -1/2 -3/2

运筹学 整数规划

运筹学 整数规划

Company 运 筹 Logo 学
第五章 整数规划

三、0-1规划的解法 规划的解法 穷举法： 穷举法： 隐枚举法： 隐枚举法：
Company 运 筹 Logo 学

四、整数规划的lingo软件求解 、整数规划的 软件求解 @ @ @ @ Free(变量名)：自由变量函数； Gin（变量名）：整数变量函数； Bin（变量名）：二进数变量函数（0-1规划用）； Bnd（下界，变量名，上界）：变量带上下界的函数。
停止 停止
Company 运 筹 Logo 学
L1: X1 ≤4 X*=（4.00，2.10） （ ， ） Z1*=349 L11: X2 ≤2 X*=（4,2 ） （ Z11*=340
L22: X2 ≥2 无可行解
X2 ≥3 X*=（1.42,3） （ ） Z12*=327
第五章 整数规划

Company Logo
Company Logo
第五章 整数规划

例：相互排斥的约束条件
设有两种运输方式：车运、船运。 设有两种运输方式：车运、船运。 采用船运时，载重受限制， 采用船运时，载重受限制，即5x1+4x2≤24 采用车运时，载重受限制， 采用车运时，载重受限制，即2x1+5x2≤13
分枝定界法步骤： 分枝定界法步骤： （1）求整数规划的松驰问题 的最优解 ； ）求整数规划的松驰问题L的最优解 无可行解,则原整数规划无可行解 的最优解满足整数要求， （2）若L无可行解 则原整数规划无可行解；若L的最优解满足整数要求， ） 无可行解 则原整数规划无可行解； 的最优解满足整数要求 则得到整数规划的最优解；否则转下一步； 则得到整数规划的最优解；否则转下一步； （3）分枝：任意选一个不满足整数要求的变量 i，在原问题中分别加 ）分枝：任意选一个不满足整数要求的变量x 上约束x ︱ 组成两个新的线性规划， 上约束 i≤︱xi ︱及 xi≥ ︱ xi ︱ +1组成两个新的线性规划，称 组成两个新的线性规划 为分枝。继续求这两个松驰问题。 为分枝。继续求这两个松驰问题。 新的松驰问题具有的特征：当原问题是求最大值时， 新的松驰问题具有的特征：当原问题是求最大值时，目标值是 分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； 分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界； （4）定界：将当前得到的最好整数解的目标函数值定为上界（max） ）定界：将当前得到的最好整数解的目标函数值定为上界（ ） 检查所有分枝的解及目标函数值， 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值 大于等于其它分枝的目标值，则将其它分枝剪去不再计算， 大于等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在 非整数解并且目标值大于整数解的目标值，需要继续分枝，再检查， 非整数解并且目标值大于整数解的目标值，需要继续分枝，再检查， 直到得到最优解。 直到得到最优解。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x 6 1 x1 , x 2 0, 取整数
x2 4 3 2 1 O 2 4 6 8 x1 K1 K2
第五章 整数规划
4.分别求解一对分支 在一般情况下，对某个分支问题（伴随规划）求解时，可 能出现以下几种可能： （1）无可行解 （2）求得整数最优解。 （3）得到非整数最优解。 若求得某个分支问题得到的是不满足整数条件的最优解， 还要分两种情况：①该最优解的目标函数值Z小于当前的下 界Z，则该分支不可能含有原问题的整数最优解，称为“枯 枝”，需要剪掉。②该最优解的目标函数值Z大于当前的下 界Z，则仍需对该枝继续分支，以查明该分支内是否有目标 函数值比当前的Z更好的整数最优解。
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x1 6 x2 3 x , x 0 1 2 max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x1 6 x2 4 x , x 0 1 2
第五章 整数规划
第5步：修改上、下界。 （1）修改下界 （2）修改上界 在每解完一对分支、修改完上下界后，若上下界相等，此 时所有分支都已查明，即得到了原问题的最优解，求解结 束。若上界大于下界，说明分支仍没查明，需继续分支， 回到第4步。
第五章 整数规划
5.3割平面 5.3.1 基本思路 用割平面法求解整数规划的基本思路，是先不考虑约束条 件，求松弛问题的最优解，如果获得整数最优解，即为所求， 运算停止。如果所求得到最优解不满足整数约束，则在此非 整数解的基础上增加新的约束重新求解。这个新增的约束条 件的作用就是切割去相应松弛问题的可行域，即切割去松弛 问题的非整数解（包括原已得到的非整数最优解）。而把所 有的整数解都保留下来，故称新增的约束条件为割平面。当 经过多次切割后，就会使被切割后保留下来的可行域上有一 个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。 即切割后所对应的松弛问题，与原整数规划问题具有相同的 最优解。
中原工学院机电学院 主讲：丁剑飞 dingjf06@
第五章 整数规划
5.1 整数规划的数学模型 在线性规划问题中，如果决策变量要求全部取整数，就称 为纯整数规划；如果仅部分决策变量要求取整数则称为混 合整数规划，二者统称为整数规划。 例5.1 某工厂拟用火车装运甲、乙两种货物集装箱，每箱 的货物体积、重量、可获利润以及装运所受的限制如下表。 问两种货物各装多少箱，可获得利润最大？
第五章 整数规划
在分支界定法的整个求解过程中，上界的值不断减小。 因为X3*=(7.2,3)T不满足整数条件，故问题B3分别增加约 束条件x1≤7，x1≥8，得问题B5与B6。 问题B5 问题B6
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 x2 4 s .t . x 6 1 x 3 2 x1 7 x1 , x 2 0 max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 x2 4 s .t . x 6 1 x 3 2 x1 8 x1 , x 2 0
第五章 整数规划
解 设计划建甲种宿舍x1幢，乙种宿舍x2幢，则其数学模型 为：max z 10 x1 20 x2
0.25 x1 0.4 x 2 3 x 8 1 s .t . x2 4 x1 , x 2 0, 取整数
原问题称为A0，将上式约束条件系数全化为整数，去掉整 数条件，得到问题A0的伴随问题，称之为B0：
第五章 整数规划
5.3.2 求解步骤与举例 例5.3 求解下列整数规划问题
第五章 整数规划
3.增加约束条件将原问题分支
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x 5 1 x1 , x 2 0, 取整数
x2 4 3 2 1 O 2 4 6 8 x1 K0 (5.6,4) (8,2.5)
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x2 4 x1 , x 2 0
第五章 整数规划
用单纯形法求解问题B0，得到最优解及最优值： x1=5.6，x2=4，X0*=(x1,x2)T，f0*=136 1.计算原问题A0目标函数值的初始上界Z ' 因为X0*不是问题的最优解，且 K 0 K 0 0’为A0的可行域， （K K0为B0的可行域），故问题A0的最优值不会超过B0的最优 值，即 。 Z 136 2.计算原问题A0目标函数的初始下界Z 若能从问题A0的约束条件中观察到一个整数可行解，则 可以作为问题A0目标函数的初始下界，否则可令初始下界 Z 。给定下界的目的，是希望在求解过程中寻找比当前 Z更好的目标函数值。
解为：f1*=130 X1*=(5,4)T f2*=135 X2*=(6,3.75)T 问题B1的解是整数最优解，它也是问题A0的整数可行解， 故A0的整数解Z*≥f1*=130。此时修改Z=130，同时B1成为 “树叶”。
第五章 整数规划
问题B2的解不满足整数条件，故问题A0分别增加约束条 件：x2≤3及x2≥4。分为A3与A4两支，建立相应的伴随规划B3、 B4。 问题B3 问题B4
第五章 整数规划
B5解为：X5*=(7,3)T，f5*=130；B6解为：X6*=(8,2.5)T， f6*=130。因为此时B5的解为整数解，因此修改下界为130， 而此时所有未被分支的问题（B4,B5,B6)的目标函数中的最小 值为f5*=f6*=130，故修改上界为Z=130。 6.结束准则 当所有的分支均已查明（或为无可行解—“树叶”，或为 整数可行解—“树叶”，或其目标函数值不大于下界— “枯枝”），且此时Z=Z，则已求得了原问题的整数最优解， 即目标函数下界Z的那个整数。 在本例中，当解完一对分支B5、B6后，得到Z=Z=130，又 B5是“树叶”，B6为“枯枝”，因此所有分支(B1,B4,B5,B6) 均已查明，故已求得问题A0的最优解：
第五章 整数规划
本例问题B1及问题B2的模型及求解结果如下 问题B1 问题B2
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x 5 1 x1 , x 2 0
max z 10 x1 20 x 2 5 x1 8 x 2 60 x 8 1 s .t . x 2 4 x 6 1 x1 , x 2 0
明显K4=Φ，问题B4无可行解，此问题已是“树叶”。
第五章 整数规划
求解B3，得最优解X3*=(7.2,3)T，f3*=132。 5.修改上下界Z与Z （1）修改下界Z 修改下界的时机是：每求出一个整数可行解时，都要修改 下界。修改下界的原则：在至今所有计算出的整数可行解 中选出目标函数值最大的那个为最新下界。 （2）修改上界Z 修改上界的时机是：每求完一对分支，都要考虑修改上界。 修改上界的原则是：挑选迄今为止所有未被分支的问题的 目标函数之中最大的一个作为新的上界。新的上界应小于 原来的上界。 本例中，因为f3*<f0*，所以新的上界为Z=132。
Z=135 Z=130 x2≥4 B4 无可 行解
Z=132 Z=130 x1≤7 B5 X1=7 X2=3 f5=130
Z=130 Z=130
第五章 整数规划
5.2.2 分支界定法的计算步骤 第1步：原问题去掉整数条件，得到伴随规划B0。 第2步：求解问题B0，有以下几种可能： （1）B0没有可行解，则原规划也没有可行解，停止 计算。 （2）得到B0的最优解，且满足整数条件，则B0的最 优解也是原规划的最优解，停止计算。 （3）B0得不到整数最优解，对其分支转下 B O x1 C
第五章 整数规划
5.2 分支界定法 分支界定法的主要思路是首先求解整数规划的伴随规划， 如果求得的最优解不符合整数条件，则增加新约束——缩 小可行域；将原规划问题分支——分为两个子规划，再解 子规划的伴随规划。通过求解一系列子规划的伴随规划， 不断地界定，最后得到原整数规划问题的整数最优解。 5.2.1 分支界定法的主要思路 例5.2 某公司设计两种类型的宿舍，甲种每幢占地 0.25×100㎡，乙种每幢占地0.40×100㎡。该公司拥有土地 3×100㎡。计划甲种宿舍不超过8幢，乙种宿舍不超过4幢。 甲宿舍每幢利润10万元，乙种宿舍每幢利润20万元。问该 公司应计划甲、乙两种类型的宿舍各建多少幢时，能使公 司获利最大？
第五章 整数规划
以f0*作为上界。观察原规划的一个整数可行解，将其目标 函数值记为下界，若观察不到，记-∞。 第4步 将B0分支。 得两个分支：B1、B2。对每个分支问题求解，得以下几种 可能： （1）分支无可行解—该分支是“树叶”。 （2）该分支有整数最优解。将该最优解的目标函数值作为 新的下界，该分支也是“树叶”。 （3）求得分支的最优解不满足整数条件，其目标函数不大 于当前下界，该分支是“枯枝”，需要剪枝。 （4）求得最优解，不满足整数条件且最优值大于当前的下 界，则该分支需要继续进行分支。
货物集装箱 甲 乙 托运限制 体积（m³ ） 5 4 24 重量（百斤） 2 5 13 利润（百元） 20 10
第五章 整数规划
解 设甲乙两种货物装箱数分别为x1，x2。显然x1，x2是整 数，于是可建立整数规划模型如下：
max z 20 x1 10 x 2 5 x1 4 x 2 24 s .t . 2 x1 5 x 2 13 x , x 0, x , x 为整数 1 2 1 2

相关主题