当前位置：文档之家 › 整数规划分支定界习题

整数规划分支定界习题

  • 格式：pptx
  • 大小：293.08 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

第4章 整数规划

第4章 整数规划

第4章 整数规划判断:用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响； 匈牙利法只能用于平衡分配问题；对于极大化问题，匈牙利法不能直接求解。

整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。

用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。

用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。

分配问题的每个元素都加上同一个常数k ，并不会影响最优分配方案。

分配问题的每个元素都乘上同一个常数k ，并不会影响最优分配方案。

分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。

隐枚举法也可以用来求解分配问题简答试述分枝定界法求解问题的主要思想。

试述隐枚举法的步骤。

试讲述割平面方法的基本原理. 试例举三种应该剪枝的情况。

计算题分枝定界法用分枝定界法求解下列整数规划问题12max Z x x =+1212129511414123,x x x x x x +≤-+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 32Z x x =+121212231429,x x x x x x +≤+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 2010Z x x =+1232312312324434323,,x x x x x x x x x x x ++≤≤+≤≥－--0且为整数用分枝定界法求解下列整数规划问题12max 79Z x x =+121212136735,x x x x x x x +≤+≤≥－0，且为整数用分枝定界法求解下列整数规划问题123max 33Z x x x =++123231231231324432323,,,x x x x x x x x x x x x x ++≤≤+≤≥－--0，且为整数用分枝定界法解下列整数规划问题：1212121212232478188..3219,0MaxZ x x x x x x s t x x x x =+-+≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题1212121212250..6221,0MaxZ x x x x x x s t x x x x =++≤⎧⎪-+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题12312121225231050..7228,0,MaxZ x x x x x s t x x x x x =-+-+≤⎧⎪-≤⎨⎪≥⎩为整数用分枝定界法解下列整数规划问题12312341234345272222..0,1,2,3,4,5,j MaxZ x x x x x x x x x x x s t x j x x =-+-⎧-+-+=⎪⎪⎪-++=⎨⎪≥=⎪⎪⎩为整数用分枝定界法求解下列整数规划模型12max 23z x x =+121257354936x x x x +≤+≤12,0x x ≥且为整数有如下整数规划问题12max z x x =+12129511414123x x x x +≤-+≤12,0x x ≥且为整数试用分枝定界法求其最优解。

分支定界

分支定界

所谓“分支”就是在处理整数规划问题时，逐步加入 对各变量的整数要求限制。先求解整数规划相应的松弛问 题(记为 P0)，若(P0)的最优解不符合整数条件，假设 xi b i 不符合整数条件，于是增加新的约束条件： xi bi 和
xi bi 1， 分别将其加入到松弛问题(P0)中， 从而形成两
5 x1 7 x2 35 s.t . 4 x1 9 x2 36 x , x 0, 全部为整数 1 2
解 :step1
确定与整数规划问题（记为问题 A）对应的松
弛线性规划问题 (记为问题 B)：
max z 2 x1 3 x2
5 x1 7 x2 35 s.t . 4 x1 9 x2 36 x , x 0 1 2
个分支，称为两个后继子问题。后继子问题的可行域包含 整数规划所有的可行解。根据需要，后继子问题可以产生 类似的分支，从而把原整数规划问题通过分支迭代求出最 优解。
所谓“定界”就是在分支过程中，若某个后继子问题最优 解恰好是整数规划的可行解，则该后继子问题最优目标函 数值成为整数规划的目标函数值的一个“界限” ，从而对 那些最优目标函数值比上述“界限”还差的后继子问题可 以剔除不加考虑。 同时在分支过程中出现更好的 “界限” ， 则用它来取代原来的界限，以提高定界的效率。
则总生产成本的目标函数为：
min z C ( x j ) c j x j k j y j
j 1 j 1
n
n
这里 M 是一个充分大的正数。 所以该产品计划问题可以表 述成如下规划问题：
min z c j x j k j y j
j 1
n
0 x j My j , j 1,2,, n s.t. y j 0 or 1, j 1,2,, n

整数规划问题

整数规划问题

整数规划问题的求解方法
分枝定界法branch and bound method 分枝定界法是一种隐枚举方法（implicit enumeration）或部分 枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用 此算法。其关键是分支和定界。 例——
Max
s.t.
Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ， X2 ≥ 0 X1 ， X2 取整数
fi - ∑ fik xk ≤ 0 ……………………（4 式）
此即为所需切割方程。
16
整数规划 Integer Programming（IP）
割平面法cutting plane approach 构造切割方程的步骤： （1）切割方程 fi - ∑ fik xk ≤ 0 真正进行了切割，至少把非整数最优 解这一点切割掉了。 证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由 fi - ∑ fik x*k ≤ 0， 又因为 x*k = 0，（因 x*k 为非基变量） 有 fi ≤ 0 ，这与 fi ＞ 0 矛盾。 （2）不会切割掉任何整数解，因为切割方程是由变量为整的条件 提出的。
18
求解步骤：
1、求解 LP 得到非整数最优解： X =（3/4，7/4，0，0），Max Z = 5/2 Cj CB I表 XB B –1 b 1 X1 1 X2 0 X3 0 X4
0
0 j 1
X3
X4 X1 X2
1
4 0 3/4 7/4
-1
3 1 1 0
1
1 1 0 1
1
0 0 -1/4 3/4
14
整数规划 Integer Programming（IP）

第4章 整数规划

第4章 整数规划

第4章 整数规划 判断:

04100011 用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界； 04100021 指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解； 04100031效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响； 04100041匈牙利法只能用于平衡分配问题； 04100051对于极大化问题，匈牙利法不能直接求解。 04100061整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。 04100071用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。 04100081用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。 04100091分配问题的每个元素都加上同一个常数k，并不会影响最优分配方案。 04100101分配问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。 04100111分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。 04100121隐枚举法也可以用来求解分配问题

简答 04200011 试述分枝定界法求解问题的主要思想。 04200021 试述隐枚举法的步骤。 04200031 试讲述割平面方法的基本原理. 04200041试例举三种应该剪枝的情况。 计算题

分枝定界法 04301012用分枝定界法求解下列整数规划问题

12maxZxx

121212

9511414123,xxxxxx

0且为整数

04301022用分枝定界法求解下列整数规划问题 12max32Zxx 121212

231429,xxxxxx0且为整数

04301032用分枝定界法求解下列整数规划问题 12max2010Zxx 12323123123

第二章 整数规划+答案

第二章 整数规划+答案

故最优解为：X
0010
1 0
0 1
0 0
0 0
，最优值为 14。
0001
6103 0211 1030 5300
5、在今后三年内有五项工程考虑施工，每项工程的期望收入和年度费用（千元）如表所示。假定 每一项已批准的工程要在三年内完成，目标是要选出使总收入达到最大的那些工程。
工程
第1年
费用（千元） 第2年
2 3 14 s. t. 4 2 18
, 0 且为整数
B：X=（3.25,2.5）z=14.75
x2<=3
x2>=4
B1：X=（3,2.67）z=14.33
B2：X=（4,1）z=14
x2<=2
x2>=3
B11：X=（3,2）z=13
B12：X=（2.5,3）z=13.5
所以，最优解为：X=（4,1），最优值为 14。
人
A
B
C
D
E
甲
25
29
31
42
37
乙
39
38
26
20
33
丙
34
27
28
40
32
丁
24
42
36
23
45
解：（1）由于任务数多于人数，所以需要一名假想的人，设为戊。因为工作 E 必须完成，故设戊完
成 E 的时间为 M，其余的假象为 0，建立如下的效率矩阵。
任务
人
A
B
C
D
E
甲
25
29
31
42
37
乙
39
38
解：变换目标函数 max Z=16‐（2 3 5 6 ）

整数规划 割平面法 分枝定界法

整数规划 割平面法 分枝定界法
-x1+x2≤1 3x1+x2≤4 x1,x2≥0
用图解法求得可行域D及最优解点A，见下图：
x2
A（3/4，7/4） 由标准化的约束方程组可得
-x1+x2=1
1
D B（1，1）
x3 =1+x1-x2 x4=4 -3x1-x2 代入切割方程 得
-1 0
3x1+x2=4
3（1+x1-x2）+（4-3x1-x2）≥3
下面以实例来说明算法的步骤。
例2 求解下面整数规划
x2
maxZ=40x1+90x2
⑴8
9x1+ 7x2≤56 7x1+20x2≤70 xx11,,xx22≥0整数
⑵
⑶ ⑷
4
⑸
解：先不考虑条件⑸，求解相 0
应的线性规划问题L，得最优解
x1=4.81，x2=1.82，Z0=356（见图） 该解不是整数解。选择其中一个
整个分枝定界过程如下图所示：
问题L
Z0=356 x1=4.81x2=1.82
Z 0,Z 356
x1≤4
问题L1 Z1=349 x1=4.00，x2=2.10
x2≤2 问题L3 Z3=340 x1=4.00 x2=2.00
Z※=340
x2≥3
问题L4 Z4=327 x1=1.42 x2=3.00
×
x1≥5
运筹学
整数线性规划
§1 整数规划问题
在前面的线性规划问题中，它的解都假设为可以取连续数值。 但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如 变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮 数等等。为了满足整数解的要求，比较自然的简便方法似乎就是把 用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾 取整”处理。当然，这样做有时确实也是有效的，可以取得与整数 最优解相近的可行整数解，因此它是实际工作中经常采用的方法。 但是实际问题中并不都是如此，有时这样处理得到的解可能不是原 问题的可行解，有的虽是原问题的可行解，但却不是整数最优解。 （详见后面例1）。因而有必要专门研究只取整数解的线性规划的 解法问题。

分枝定界法

第8页/共34页
束——缩小可行域;将原整数规划问题分枝——分为两个子 规划,再解子规划的伴随规划……通过求解一系列子规划的 伴随规划及不断地定界 .最后得到原整数规划问题的整数最 优解 . 下面结合一个极大化例题来介绍分枝定界法的主要思路 .
例2 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 ×103m2, 乙种每幢地0.4×103m2.该公司拥有土地3×103m2. 计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每 幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应
x2 3 x1, x2 0
问题 B4
max f 20 x1 10 x2
5x1 8x2 60
x1 8
s.t
x2 4 x1 6
x2 4 x1, x2 0
它们的可行域分别为 K3, K4 ( ). 见图3。
第21页/共34页
x2
因为 K4 ，问题 B4
4
无可行解，此问题已
3
作出问题 A1, 的A2伴随规划 B则1, 问B2题, 的可B1行, B2, 域为 K1, K见2图, 2(b). 以下我们将由同一问题分解出的两
个分枝问题称为"一对分枝".
第15页/共34页
x2
4
x2
3
2 1
O
246
8 x1
O
12 4
6
8
x1
(a)
(b)
图2 ( a )
4. 分别求解一对分枝
在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现 以下几种可能:
x1, x2 0, 整数
（1）
第3页/共34页
若暂且不考虑 x1, x取2 整数这一条件.则(1)就变为下列 线性规划 :

精选整数规划试题

整数规划试题
精选整数规划试题
一、选择题（在下列各题中，从备选答案中选出1个或多个正确答案）1. maxZ?3x1?2x2,2x1?3x2?14,x1?0.5x2?4.5,x1,x2?0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是( )
A.(4，1)
B.(4，3)
C.(3，2)
D.(2，4)
2. 下列说法正确的是 ( )
A.整数规划问题最优值优于其相应的线性规划问题的最优值
B.用分枝定界法求解一个极大化的'整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝
C.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解。

D.以上说法都不对
3. 分枝定界法中( )
A. 最大值问题的目标值是各分枝的下界
B. 最大值问题的目标值是各分枝的上界
C. 最小值问题的目标值是各分枝的上界
D. 以上结论都不对
二、填空题
1．求解纯整数规划的两种方法是（）
2. 已知基变量x1=
3.25，x1要求取整数，则添加分枝约束（）和（）。

三、判断题
1. 整数规划的最优解是先求相应的线性规划的最优解然后取整得到；
2. 部分变量要求是整数的规划问题称为纯整数规划；
3. 求最大值问题的目标函数值是各分枝函数值的上界；
4. 求最小值问题的目标函数值是各分枝函数值的下界；
5. 变量取0或1的规划是整数规划；
6. 整数规划的可行解集合是离散型集合；。

第四章整数规划与分配问题习题


1
0
X1 32/7 1 0 0 1/7 -1/7 0
X3 11/7 0 0 1 1/7 -22/7 0
S1 -4/7 0 0 0 [-1/7] -6/7 1
Cj—Zj
0 0 0 -1
-8
0
X2 3
0
00
1
0
X1 4 1 0 0 0
-1 1
X3 1 0 0 1 0
-4 1
X4 4 Cj—Zj
0001 0000
解：
（1）
LP（1）
1 x1 = 39
7 x2 = 29
5 Z1 = 329
z = 32 5 9
z = 28
x1≤3 LP（4） x1 = 3 x2 = 2 z4 = 28
剪去
x2≤2
x2≥3
LP（2） 1
x1 = 32 x2 = 2
z2 = 31
LP（3） 2
x1 = 25
x2 = 3 4
z3= 315
x3* = (1,2)T , z * = 3 由于表 3(b)中一非基变量x5的检验数为 0，故让x5进量，用单纯形法迭代一次，得另一最优解
（见表 4）：
x3* = (2,1)T , z * = 3
8、 用完全枚举法求解 0—1 规划问题.
max z = 3x1 − 2x2 + 5x3 s.t. x1 + 2x2 − x3 ≤ 2
变换效益矩阵：
⎛0 1 2 3⎞⎛0 ⎞ ⎛0 1 2 3⎞ ⎛ⓞ Ø 2 3 ⎞
Ci'j
=
⎜ ⎜ ⎜
7 8
6 9
5 9
4 8
⎟ ⎟ ⎟
⎜ ⎜ ⎜
−4 −8

混合整数线性规划


B1 B 2 c11 c12 c 21 c 22
cm1 cm 2 b1 b 2
生产 建设
Bn 能力 费用 c1n a1 f1 c2n a2 f2
c mn a m f m bn
设： xij 表示从工厂运往销地的运量(i=1.2…m、
j=1.2…n), 1 在Ai建厂
又设 Yi＝
（i=1.2…m）
⑵ ⑴
A
(18/11,40/11)
BCD
E
F
⑶
求（LP6），如图所示。 1
此时 F在点取得最优解。
x1＝3, x2 =2.5,
1
3
x1
Z(6)＝－31/2≈－15.5 > Z(5)
如对 Z(6) 继续分解，其最小值也不会低于－15.5 ，问 题探明,剪枝。
至此，原问题 （IP）的最优解 为：
x1=2， x2 =3, Z* = Z(5)
x1≥3
LP4 无可 行解
＃
LP5 x1=2, x2=3 Z(5) ＝－17
＃
LP6 x1=3, x2=5/2 Z(6) ＝－15.5
＃
三、0－1 整数规划
0－1 整数规划是一种特殊形式的整数规划，这时的 决策变量xi 只取两个值0或1，一般的解法为隐枚举法。
例一、求解下列0－1 规划问题
max Z 3 x 1 2 x 2 5 x 3
4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为新 的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最 大者作为新的下界。
5、比较与剪枝 ：
各分枝的目标函数值中，若有小于Z 者，则剪掉此 枝，表明此子问题已经探清，不必再分枝了;否则继续 分枝。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(2)求解R0，得R0的最优解x(0)和最优值z0。若x(0)符合R的整 数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个 分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。
(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选 一不符合整数条件的变量xj，其值为bj，构造两个约束条件 xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个 后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题， 以每个后继问题为一分枝标明求解的结果。
9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x1,x2≥0
问题R2为: Max z=40x1+90x2
9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x1,x2 ≥ 0
R1:z1=349 x1=4.00 x2=2.10
R2:z2=341 x1=5.00 x2=1.57
▪ 问题7相应的线性规划的最优解：无最优解
• 第八步，定界过程
▪ LP7的无最优解，不必再分枝，下界仍为29； ▪ 现有上界为未分枝子问题中目标函数最大值，即为209/7。 ▪ LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于
现有下界29，则应继续分枝。
• 第九步，分枝过程
将不满足整数约束的变量x2进行分枝，构造两个新的约束条件 ：
• 第四步，定界过程
▪ LP3的解满足整数约束，不必再分枝，它的目标函数值是29， 大于原有下界0，则新的下界为29；
▪ 现有上界为未分枝子问题中目标函数最大值，即为226/7。 ▪ LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于
现有下界，则应继续分枝。
• 第五步，分枝过程
将不满足整数约束的变量x2进行分枝，构造两个新的约束条件 ：
x2≤ 3， x2≥ 4
• 求解相应的线性规划的最优解 ▪ 问题8相应的线性规划的最优解： x1=2，x2 =3，Z8=27 ▪ 问题9相应的线性规划的最优解：x1=7/5，x2 =4，Z9=142/5
• 第十步，定界过程
▪ LP8的最优解，满足整数约束，不必再分枝，下界仍为29； ▪ 现有上界为未分枝子问题中目标函数最大值，即为29。 ▪ 虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5
R11: z1z12=327 x1=1.42 x2=3.00
R21: z21=308 x1=5.44 x2=1.00
R22: 无可 行解
• 求解相应的线性规划的最优解 ▪ 问题2相应的线性规划的最优解：x1=3，x2 =20/7，Z2=226/7 ▪ 问题3相应的线性规划的最优解：x1=4，x2 =1，Z3=29
x2≤ [20/7]=2， x2 ≥ [20/7] +1=3
• 求解相应的线性规划的最优解 ▪ 问题4相应的线性规划的最优解： x1=3，x2 =2，Z4=28 ▪ 问题5相应的线性规划的最优解：x1=14/5，x2 =3，Z5=159/5
• 第六步，定界过程
▪ LP4的解满足整数约束，不必再分枝，它的目标函数值是28， 小于原有下界29，则下界仍为29；
x2 ≤2
x2≥3 x1 ≤1
x1≥2
问题R11为: Max z=40x1+90x2
9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x2 ≤2 x1,x2≥0
问题R12为: Max z=40x1+90x2
9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x2 ≥3 x1,x2 ≥ 0
(4)定界。在各分枝中找出目标函数值最大者作为新的上界z ；从已符合整数要求的各分枝中，找出目标函数值最大者作为新 的下界z。
(5)比较与剪枝。各分枝的最优目标函数值中如果有小于z 者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没 有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。
例 求解问题
分枝定界法
分枝定界法是20世纪60年代由 Land-Doig和Dakin等人提出的。这 种方法既可用于纯整数规划问题， 也可用于混合整数规划问题，而且 便于用计算机求解，所以很快成为 解整数规划的最主要的方法。
设有最大化的整数规划问题R， 与它相应的线性规划问题为R0，分枝 定界法的做法是：
(1)用观察法求R的一个可行解，其目标值便是R的最优目标 值z*的一个下界z。
小于现有下界29，则不再继续分枝。
• 上界=下界，得整数规划问题的最优解： x1=4，x2 =1，Z=29
• 分枝定界过程
x2≤2 x2≤3
x1≤3 x2 ≥3
x1≤2 x2 ≥4
x1 ≥4 x1 ≥3
▪ 现有上界为未分枝子问题中目标函数最大值，即为159/5。 ▪ LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于
现有下界29，则应继续分枝。
• 第七步，分枝过程
将不满足整数约束的变量x1进行分枝，构造两个新的约束条件 ：
x1≤ [14/5]=2，x1≥ [14/5] +1=3
• 求解相应的线性规划的最优解： ▪ 问题6相应的线性规划的最优解： x1=2，x2 =25/7，Z6=209/7
Max z=40x1+90x2 9x1+7x2 ≤ 56 7x1+20x2≤70 x1,x2≥0, 整数
问题R0为: Max z=40x1+90x2
9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0
R0: z0=356 x1=4.81 x2=1.82
x1 ≤4
x1≥5
问题R1为: Max z=40x1+90x2