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

整数规划-分支定界习题

  • 格式：ppt
  • 大小：318.00 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

运筹学：整数规划习题与答案

运筹学：整数规划习题与答案

一、单选题1、下列说法正确的是（）。

A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.整数规划问题最优值优于其相应的线性规划问题的最优值正确答案：A2、整数规划的最优解中，决策变量满足（）。

A.决策变量不是整数B.没有要求C.决策变量至少有一个是整数D.决策变量必须都是整数正确答案：D3、下列（）可以求解指派问题。

A.梯度法B.牛顿法C.单纯形法D.匈牙利法4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（）。

A.隐枚举法B.0-1规划法C.分支定界法D.割平面法正确答案：D5、标准指派问题（m人，m件事）的规划模型中，有（）个决策变量。

A.都不对B. m*mC. mD.2m正确答案：B二、判断题1、匈牙利法可以直接求解极大化的指派问题。

（）正确答案：×2、整数规划的可行解集合是离散型集合。

（）正确答案：√3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。

（）4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。

（）正确答案：×5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。

（）正确答案：√。

第8章_整数规划(带答案)

第8章_整数规划(带答案)

1 2 3 4 5 6
1 2 3 0 10 16 10 0 24 16 24 0 28 32 12 27 17 27 20 10 21
4 28 32 12 0 15 25
5 27 17 27 15 0 14
6 20 10 21 25 14 0
18
二、背包问题（补充）
背包可装入 8 单位重量， 10 单位体积物品。若 背包中每件物品至多只能装一个，怎样才能使背包 装的物品价值最高。 物品 名称 重量 体积 价值
4
§1 整数规划的图解法
例1. 某公司拟用集装箱托运甲、乙两种货物， 这两种货物每件的体积、重量、可获利润以及 托运所受限制如表所示。
货物
甲 乙 托运限制
每件体积 (立方米) 195 273 1365
每件重量 (百千克) 4 40 140
每件利润 （百元） 2 3
甲种货物至多托运 4 件，问两种货物各托运多 少件，可使获得的利润最大。
例6．有四个工人，要分别指派他们完成四项 不同的工作，每人做各项工作所消耗的时间 如下表所示，问应如何指派工作，才能使总 的消耗时间为最少。
工作 工人 甲 乙 丙 丁 A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17
1 2 3 4 5 6
1 2 3 0 10 16 10 0 24 16 24 0 28 32 12 27 17 27 20 10 21
4 28 32 12 0 15 25
5 27 17 27 15 0 14
6 20 10 21 25 14 0
第2个地区建一个（地区1、2、6都解决了）
第4个地区建一个（地区3、4、5都解决了）

第二章 整数规划+答案

第二章 整数规划+答案

故最优解为：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 ）

运筹学课件第三节分支定界法

运筹学课件第三节分支定界法

约束条件组
n aij xj b i My i j1 st. p (i 1 ,2,...,p) yi pq i1
在约束条件中保证了在P个0-1 变量中有p-q个1,q个0;凡取值 =0的yi对应的约束条件为原约束 条件,凡取值=1的yi对应的约束 条件将自然满足,因而为多余.
,先加工某种产品 0 yj （ j 1 ,2 ,3 ,4 ） 1 ，先加工另外产品 机床1:x11+a11≤x21+My1 ; x21+a21≤x11+M(1-y1) 机床2:x22+a22≤x32+My2 ; x32+a32≤x22+M(1-y2) 机床3:x13+a13≤x33 +My3 ; x33+a33≤x13+M(1-y3) 机床4:x14+a14≤x24 +My4 ; x24+a24≤x14+M(1-y4) 当y1=0,表示机床1先加工产品1,后加工产品2;当y1=1,表示机床1先 加工产品2,后加工产品1.
不同的搜索策略会导致不同的搜索树，一般 情况下，同一层的两个子问题，先搜索目标 函数比较大的较有利（如果是极小问题，则 应先搜索目标函数值小的较为有利）。这样 可能得到数值比较大的下界，下界越大被剪 去的分支越多。 分支定界算法对于混合整数规划特别有效， 对没有整数要求的变量就不必分支，这将大 大减少分支的数量。
Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥2 X2 ≤ 2 X1 ， X2 ≥ 0 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 X1 ≥3 X2 ≤ 2 X1 ， X2 ≥ 0 Max Z = X1 + X2 14X1 + 9X2 ≤ 51 - 6X1 + 3X2 ≤ 1 2≤ X1 ≤2 X2 ≤ 2 X1 ， X2 ≥ 0

整数规划习题

整数规划习题
x1、x 2 均是整数
（2）max z 3x2 3x1 2x2 7 x x 1－ 2 －2 x1 0,x2 0
x1、x 2 均是整数
3. 用隐枚举法求解下列 0-1规划问题:
（1）max z 2x1－x2＋5x3 3x4 4x5 3x1 2x2 7x3 5x4 4x5 6 x1 x2 2x3 4x4 2x5 0 xj 0 或（1 j 1,2,3,4,5)
（2）min z 2x1 5x2＋3x3 4x4 4x1 x2 x3 x4 0 2x1 4x2 2x3 4x4 4 x1 x2 x3 x4 1 xj 0 或（1 j 1,2,3,4)
4. 有四个工人，要分别指派他们完成四项 不同的工作，每人做各项工作所消耗的 时间如表题2.4。问应该如何指派，才 能使总的消耗时间为最少？
• 什么是隐枚举法,为什么说分支定界法也是一种隐枚举 法。
判断题
• 整数规划解的目标函数值一般优于其相应的线性规划 问题的解的目标函数值;
• 用分枝定界法求解一个极大化的整数规划问题时,任何 一个可行解的目标函数值是该问题目标函数值的下界;
• 用分支定界法求解一个极大化的整数规划问题,当得到 多于一个可行解时,通常任取其中一个作为下界值,再 进行比较剪枝;
x1 0,x2 0
x1、x 2 均是整数
（2）max z 5x1 8x2 x1 x2 6 5x1 9x2 45 x1 0,x2 0
x1、x 2 均是整数
2．分别用穷举法和割平面法求解下列整数规划 问题:
（1）max z x1 x2 2x1 x2 6 4x1 5x2 20 x1 0,x2 0

整数规划

整数规划

i=1 j=1
整数规划的特点及应用
例1 现有资金总额为B。可供选择的投资项目有n个，项目 j所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此 外由于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定
7
项目3和4中至少选择一个；
项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。
14
x2
3
⑴
⑵
(3/2,10/3)
标函数值最大，即为Z=4。
3
x1
整数规划的特点及应用
整数规划问题的求解方法： 分支定界法
15
割平面法
匈牙利法（指派问题）
分支定界法
分支定界法的解题步骤：
1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题，称为分枝。 新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当 原问题是求最小值时，目标值是分枝问题的下界。 3) 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于 （max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数 解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优 解。
整数规划的特点及应用
min z =
6
邋
4
4
c ij x ij + [1200y 1 + 1500y 2 ]
ì x 11 + x 21 + x 31 + x 41 = 350 ï ï ï ï x 12 + x 22 + x 32 + x 42 = 400 ï ï ï ï x 13 + x 23 + x 33 + x 43 = 300 ï ï ï x 14 + x 24 + x 34 + x 44 = 150 ï ï ï ï ï x 11 + x 12 + x 13 + x 14 = 400 s .t . í ï x 21 + x 22 + x 23 + x 24 = 600 ï ï ï x 31 + x 32 + x 33 + x 34 = 200y 1 ï ï ï ï x 41 + x 42 + x 43 + x 44 = 200y 2 ï ï ï x ij ? 0 (i , j 1, 2, 3, 4) ï ï ï ï y = 0,1 (i = 1, 2) ï ï î i

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

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

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

运筹学习题库

运筹学习题库

运筹学习题库一、线性规划1．某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。

工厂每天可利用的工时为12个，可供应的原材料为15公斤。

1）试确定使总利润为最大的日生产计划和最大利润。

2）若由于原材料涨价，使得产品丙的单位利润比原来减少了2元，问原来的最优生产计划变否？若不变，说明为什么；若变，请求出新的最优生产计划和最优利润。

3）在保持现行最优基不变的情况下，若要增加一种资源量，应首先考虑增加哪种资源？为什么？单位资源增量所支付的费用是多少才合算？为什么？2．给出一线性规划问题如下：max z = 3x1 + x2x1 + x2≤4－x1 + x2≤26x1 + 2x2≤18x１，x2≥0试用对偶理论判断该问题是否存在以x１、x2和x3为基变量的最优解？3．用单纯形法求解某个目标函数为max，约束为≤形式，x4、x5为松弛变量的线性规划问题的最终表如下：试用改进单纯形法原理求该问题的数学模型。

4．给出一个线性规划问题如下：max z = x1 +2 x2 +3 x3x1 + 2x2 + 3x3≤84x1+ 5x3≤12x1，x2 ，x3 ≥0已知其对偶问题的最优解为Y* = (1，0 )，试用对偶理论求上述问题的最优解和最优值。

5．试用大M法求下述线性规划问题的最优解和最优值（不能用图解法）：max z = 3x 1 – 3 x 2x1 + x2 ≥1 2x 1 + 3x 2 ≤6x 1，x 2 ≥06．已知一线性规划问题如下：max z = 5x 1 + 2 x 2 + 4 x 3 3 x 1 + x 2 + 2 x 3 ≤ 46 x 1 + 3 x 2 + 5 x 3 ≤ 10 x 1，x 2，x 3 ≥ 0试用松紧定理判断X = ( 0，0，2 )T 是否是该问题的最优解，若不是，说明为什么；若是， 请求出相应的目标函数值。

整数规划分支定界习题

整数规划分支定界习题
(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大于

整数规划-割平面法-分枝定界法18页PPT

整数规划-割平面法-分枝定界法18页PPT

在求解实际问题中，割平面法经常会遇到收敛很慢的情
况，但若和其它方法，如分枝定界法，联合使用，一般能收 到比较好的效果。
§3 分枝定界法
分枝定界法是求解整数规划的常用算法，既可用来解全部变量 取值都要求为整数的纯整数规划，又可用以求解混合整数规划。
该算法的基本思路是：先不考虑整数限制，求出相应的线性规 划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分 可行域，将可行域D分成D1、D2两部分（分枝） ，然后分别求解这 两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继 续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两 部分，再求解D3与D4对应的线性规划，……，在计算中若已得到一 个整数可行解X0，则以该解的目标函数值Z0作为分枝的界限，如果 某一线性规划的目标值Z≤ Z0 ，就没有必要继续分枝，因为分枝（ 增加约束）的结果所得的最优解只能比Z0 更差。反之若Z＞ Z0 ，则 该线性规划分枝后，有可能产生比Z0 更好的整数解，一旦真的产生 了一个更好的整数解，则以这个更好的整数解目标值作为新的界限 ，继续进行分枝，直至产生不出更好的整数解为止。
所以有
x1-x3=3/4-3/4x3-1/4x4
因而有切割方程： 3/4x3+1/4x4 ≥ 3/4
即
3x3+x4 ≥3
引入松弛变量x5，得方程 -3x3-x4+x5=-3
将新约束方程加到原最优表下面（切割），求得新的最优解如下 ：
由于x1，x2的值已是整数，所以该题经一次切割已得最优解： x1=1，x2=1，最优值：Z※=2
46
10
x1
x1=4.81，x2=1.82，Z0=356（见图） 该解不是整数解。选择其中一个

分支定界问题1

分支定界问题1

分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。

但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是： 1 ．产生当前扩展结点的所有孩子结点；2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；3 ．将其余的孩子结点加入活结点表；4 ．从活结点表中选择下一个活结点作为新的扩展结点。

如此循环，直到找到问题的可行解（最优解）或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式： 1 ．FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。

如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。

又称分支定界搜索法。

过程系统综合的一类方法。

该法是将原始问题分解，产生一组子问题。

分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。

如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。

分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。

用该法寻求整数最优解的效率很高。

将该法原理用于过程系统综合可大大减少需要计算的方案数日。

分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。

在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。

运筹学教材编写组《运筹学》笔记和课后习题(含考研真题)详解(整数规划)【圣才出品】

运筹学教材编写组《运筹学》笔记和课后习题(含考研真题)详解(整数规划)【圣才出品】
若有 n 个决策变量，则可以产生 2n 个可能的变量组合，故完全枚举是不可能的，因此
常设计一些方法，只检查变量取值的组合的一部分，这样的方法称为隐枚举法。
隐枚举法的基本思想是：在 2n 个可能的变量组合中，往往只有一部分是可行解。只要
发现某个变量组合不满足其中的某一约束条件，就不必要再去检验其他的约束条件是否可行。 若已发现一个可行解，则根据它的目标函数值可以产生一个过滤条件，对于目标函数值比它 差的变量组合就不必再去检验它的可行性（类似分支定界法中的定界。实际上，隐枚举法是 一种特殊的分支定界法）。在以后的求解过程中，每当发现比原来更好的可行解，则依次替 代原来的过滤条件（可减少运算次数，较快地发现最优解）。
3．割平面法 基本思想：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束 条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标 顶点的可行域，而该顶点恰好是原整数规划问题的最优解。割平面法的关键是切割方程的求 解。 切割方程的基本步骤：
（1）令 xi 是相应线性规划问题最优解中为分数值的一个基变量，由最终单纯形表得到
2．分支定界法 分支定界法的依据：整数规划的最优解不会优于相应的线性规划问题的最优解。 分支定界法步骤： （1）求解相应的线性规划问题的最优解和最优值。 ①若没有可行解，计算停止； ②若有满足整数条件的最优解，则已得到整数规划问题的最优解，计算停止；
③若有最优解，但不满足整数条件，记此最优值为原整数规划问题 Z* 的上界，然后，
圣才电子书 十万种考研考证电子书、题库视频学习平台

第 6 章 整数规划
6.1 复习笔记
1．整数规划的分类 （1）纯整数规划：要求所有的变量均为（非负）整数； （2）混合整数规划：只有部分变量限制为整数； （3）0-1 规划：变量的取值仅限于 0 或 1。 注意：由于整数规划对变量的整数限制，一般情况下，整数规划的最优解不会优于相应 线性规划的最优解。

第五章整数规划练习题

第五章整数规划练习题

第五章整数规划练习题
一. 判断下列说法是否正确
1.用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是该问题目标函数值的下界。

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

( )
3.用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。

( )
4.指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。

( )
二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问
应如何分配这五项工作，并求得最大产值。

三. 对整数规划
12
121212MaxZ 8x 5x 2x 3x 12
x x 6
x ,x 0,=++≤⎧⎪-≤⎨⎪≥⎩整数
解得其松弛问题最优表如下：。

整数规划及分支定界法

整数规划及分支定界法
4x1+2x2 9 x1,x2 0 且为整数
用单纯形法可解得相应的松驰问题的最 优解（6/5，21/10），Z=111/10为各 分枝的上界。
分枝：X1 1,x1 2
x2 4 3 2
P1
1 0
1
P2 2
3
4
x1
两个子问题：
（P1）Max Z=4x1+3x2
s.t. 3x1+4x2 12 4x1+2x2 9 x1,x2 0 ， x/4） Z=10(3/4)
（P2）Max Z=4x1+3x2
s.t. 3x1+4x2 12
4x1+2x2 9
x1,x2 0 ， x1 2 ，整数
用单纯形法可解得相应的（P2）的 最优解（2，1/2） Z=9(1/2)
再对（P1）分枝：X1 1
x2 4 P4 3 2 1 0
（P3） x2 2
（P4） x2 3
s.t. 3x1+4x2 12
4x1+2x2 9 x1,x2 0 ,x1 1, x2 3整数
用单纯形法可解得相应的（P4）的最优 解（0，3） Z=9
X1
2
P2:(2,1/2) Z=9(1/2)
P:(6/5,21/10) Z=111/10 X1 1 P1:(1,9/4) Z=10(3/4)
最通常的松驰问题是放弃变量 的整数性要求后，（P）为线性规 划问题。
分枝定界法步骤
一般求解对应的松驰问题，可能 会出现下面几种情况： 若所得的最优解的各分量恰好是 整数，则这个解也是原整数规划 的最优解，计算结束。
若松驰问题无可行解，则原整数 规划问题也无可行解，计算结束。

整数规划问题(割平面-分枝定界算例)

整数规划问题(割平面-分枝定界算例)

x1 3.25;
x2 2.5
分枝定界法思路
第二步：分枝与定界 在x1=3.25；x2=2.5 中，任选一变量的解X2=2.5 ， 可将其分为 x2≤2；x2≥3（去掉小数部分），则有：
max Z 3x1 2 x2 2 x1 3x2 14 x 0.5 x 4.5 1 2 s.t. x2 2 x1 , x2 0
(3.5, 2); z 14.5
X1可分为x1≤3；x1≥4，则有：
max Z 3x1 2 x2 2 x1 3x2 14 x 0.5 x 4.5 1 2 s.t. x2 2 x 3 1 x1 , x2 0 (3, 2); z 13
逻辑变量在建立数学模型中的作用
y1 y2 ... ym
中m-k不起作用
（2）割平面法思路
max Z 3 x1 2 x2 2 x1 3 x2 14 s.t. x1 0.5 x2 4.5 x , x 0 且取整数 1 2
第一步：将约束条件决策变量的系数化为整数，用单纯形法求 解出最终单纯形表 找一个分数部
（3）分支定界法
max Z 3 x1 2 x2 2 x1 3 x2 14 s.t. x1 0.5 x2 4.5 x , x 0束，求解。
max Z 3x1 2 x2 2 x1 3x2 14 s.t. x1 0.5 x2 4.5 x , x 0 1 2
max Z 3x1 2 x2 2 x1 3x2 14 x 0.5 x 4.5 1 2 s.t. x2 2 x 4 1 x1 , x2 0
(4, 1);

运筹学：目标规划、整数规划习题与答案

运筹学：目标规划、整数规划习题与答案

一、判断题1、正偏差变量大于等于零，负偏差变量小于等于零。

（）正确答案：×2、系统约束中最多含有一个正或负的偏差变量。

（）正确答案：×3、目标约束一定是等式约束。

（）正确答案：√4、一对正负偏差变量至少一个大于零。

（）正确答案：×5、一对正负偏差变量至少一个等于零。

（）正确答案：√6、要求不超过目标值的目标函数是minZ= d+。

（）正确答案：√7、超出目标的差值称为正偏差。

（）正确答案：√8、未到达目标的差值称为负偏差。

（）正确答案：√二、填空题1. 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。

正确答案：下界2.在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。

正确答案：X1<=1，X1>=23. 已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P0（）。

正确答案：无可行解4.在0 - 1整数规划中变量的取值可能是（）。

正确答案：0或15. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。

正确答案：n三、选择题1. 整数规划问题中，变量的取值可能是（）。

A.整数B.0或1C.大于零的非整数D.以上三种都可能正确答案：D2.在下列整数规划问题中，分枝定界法和割平面法都可以采用的是（）。

A.纯整数规划B.混合整数规划C.0—1规划D.线性规划正确答案：A3.下列方法中用于求解分配问题的是（）。

A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法正确答案：D。

整数规划分支定界习题

整数规划分支定界习题

整数规划分支定界习题什么是整数规划？整数规划是一种最优化问题，其目标函数和约束条件都是整数。

整数规划问题可以被转化为一个线性规划问题，但因变量必须是整数，所以求解整数规划问题比线性规划问题更为复杂和困难。

分支定界法是什么？分支定界法是解决整数规划问题的一种常见方法。

该方法通过不断将问题分解为子问题，再通过限制变量的取值范围来减少问题的搜索空间，最终得到整数规划问题的最优解。

该方法的核心思想是将问题分解为一个树状结构，每个节点表示一个子问题。

分支定界法的步骤分支定界法的具体步骤如下：1.初始化：将整个问题作为根节点加入树中。

2.分支：从当前未解决子问题中选择一个变量，将其限制为两个子区间后，将两个子问题加入树中。

3.约束：对每个子问题添加限制条件，以去除已知不可行或不需要考虑的解。

4.解决：对每个子问题使用线性规划算法解决最优化问题。

5.界定：对每个子问题得到的可行解进行界定，以确定可能的最优解区间。

6.剪枝：将树中的某些分支剪去，以消除已知不可能或不需要考虑的解。

7.重复：重复步骤2-6，直到找到最优解或确定没有可行解。

分支定界法示例下面给出一个简单的例子，以说明分支定界法的具体过程。

假设有一个整数规划问题：Maximize 5x1 + 3x2s.t. 2x1 + x2 ≤ 10x1 + 3x2 ≤ 15x1, x2 ≥ 0x1, x2 为整数我们可以将其转化为一个线性规划问题：Maximize 5x1 + 3x2s.t. 2x1 + x2 ≤ 10x1 + 3x2 ≤ 15x1, x2 ≥ 0为了应用分支定界法，我们需要将每个问题分解为子问题，并对每个子问题添加限制条件。

假设我们从 x1 开始分支：子问题 1：Maximize 5x1 + 3x2s.t. x1 = 0x2 ≤ 5x2 ≥ 0子问题 2：Maximize 5x1 + 3x2s.t. x1 = 1x2 ≤ 4x2 ≥ 0我们使用线性规划算法解决每个子问题，得到以下最优解：子问题 1：x1 = 0, x2 = 5, obj = 15子问题 2：x1 = 1, x2 = 4, obj = 8然后，我们根据子问题的最优解，界定问题的最优解区间。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 第四步，定界过程
LP3的解满足整数约束，不必再分枝，它的目标函数值是29， 大于原有下界0，则新的下界为29； 现有上界为未分枝子问题中目标函数最大值，即为226/7。 LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于 现有下界，则应继续分枝。
• 第五步，分枝过程
将不满足整数约束的变量x2 进行分枝，构造两个新的约束条件： x2≤ [20/7]=2， x2 ≥ [20/7] +1=3
5 4 3
x1=3 x1=4
• • • •
1
• • •
2
2
1
• •
3
•
4
5x1 +7 x2 =35
2x1 + x2 =9
x1
• 求解相应的线性规划的最优解
问题2相应的线性规划的最优解：x1=3，x2 =20/7，Z2=226/7 问题3相应的线性规划的最优解：x1=4，x2 =1，Z3=29
问题4：maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1≤3 x2≤2 x1, x2 ≥0 x1, x2取整数
x2
5
问题5： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1 ≤ 3 x2 ≥3 x1, x2 ≥0 x1, x2取整数 x1=3 x1=4
R12: z12=327 x1=1.42 x2=3.00
R21: z21=308 x1=5.44 x2=1.00
R22: 无可 行解
例 maxZ= 6x1 +5 x2
2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2取整数
• 第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解：
分枝定界法
分 枝 定 界 法 是 20 世 纪 60 年 代 由 Land-Doig和Dakin 等人提出的 。这 种方法既可用于纯整数规划问题， 也可用于混合整数规划问题，而且 便于用计算机求解，所以很快成为 解整数规划的最主要的方法。 设有最大化的整数规划问题R， 与它相应的线性规划问题为R0，分枝 定界法的做法是：
问题8：maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1≤3 x2 ≥3 x1≤2 x2≤3 x1, x2 ≥0 x1, x2取整数 x2
5 4 3
问题9： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1 ≤3 x2 ≥3 x1≤2 x2 ≥4 x1, x2 ≥0 x1, x2取整数 x1=2 x1=3 x1=4
(1)用观察法求R的一个可行解，其目标值便是R的最优目标 值z*的一个下界z。 (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。不考虑整数条件求解这两个后继问题， 以每个后继问题为一分枝标明求解的结果。 (4)定界。在各分枝中找出目标函数值最大者作为新的上界 z；从已符合整数要求的各分枝中，找出目标函数值最大者作为 新的下界z。 (5)比较与剪枝。各分枝的最优目标函数值中如果有小于z 者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没 有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。
问题6：maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1≤3 x2 ≥3 x1≤2 x1, x2 ≥0 x1, x2取整数
x2 x1=2ຫໍສະໝຸດ 问题7： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1 ≤3 x2 ≥3 x1 ≥ 3 x1, x2 ≥0 x1, x2取整数
x2≤2
问题4： x1 3, x2 2, Z 28
x2 ≥3
问题5： x1 2 4 4 , x2 3, Z 31 5 5
上界： 31 下界： 29 4 5
x1≤2
问题6： x1 2, x2 3 4 6 , Z 29 7 7
x1 ≥3
问题7： 无可行解
上界： 29 下界： 29 6 7
• 第八步，定界过程
LP7的无最优解，不必再分枝，下界仍为29； 现有上界为未分枝子问题中目标函数最大值，即为209/7。 LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于 现有下界29，则应继续分枝。
• 第九步，分枝过程
将不满足整数约束的变量x2 进行分枝，构造两个新的约束条件： x 2≤ 3 ， x2≥ 4
问题R11为: 问题R12为: Max z=40x1+90x2 Max z=40x1+90x2 9x1+7x2≤56 9x1+7x2≤56 7x1+20x2 ≤ 70 7x1+20x2 ≤ 70 x1 ≤4 x1 ≤4 x2 ≤2 x2 ≥3 x1,x2≥0 x1,x2 ≥ 0
R11: z11=340 x1=4.00 x2=2.00
x1=28/9，x2 =25/9，Z1=293/9
• 第二步,定界过程
这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界； 因为x1=x2=0是整数规划问题的可行解，所以下界为0。
• 第三步,分枝过程
将不满足整数约束的变量x1 进行分枝，x1 称为分枝变量，构造两个新 的约束条件： x1≤ [28/9]=3， x1 ≥ [28/9] +1=4
4
3 2 1
•
• • •
1
• • •
2
x2=3
• •
3
•
4
5x1 +7 x2 =35 2x1 + x2 =9
x2 =2
x1
• 求解相应的线性规划的最优解
问题4相应的线性规划的最优解： x1=3，x2 =2，Z4=28 问题5相应的线性规划的最优解：x1=14/5，x2 =3，Z5=159/5
5 4 3
x1=3 x1=4
• • • •
1
• • •
2
x2=3
2
1
• •
3
•
4
5x1 +7 x2 =35
2x1 + x2 =9
x2 =2
x1
• 求解相应的线性规划的最优解：
问题6相应的线性规划的最优解： x1=2，x2 =25/7，Z6=209/7 问题7相应的线性规划的最优解：无最优解
问题R2为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x1,x2 ≥ 0
R0: z0=356 x1=4.81 x2=1.82
x1 ≤4 R1:z1=349 x1=4.00 x2=2.10 x2 ≤2 x2≥3
x1≥5
R2:z2=341 x1=5.00 x2=1.57 x1 ≤1 x1≥2
例 求解问题 Max z=40x1+90x2 9x1+7x2 ≤ 56 7x1+20x2≤70 x1,x2≥0, 整数
问题R1为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≤4 x1,x2≥0
问题R0为: Max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0
• 分枝定界过程
问题1 ： 1 7 5 x1 3 , x2 2 , Z 32 9 9 9
上界： 32 下界： 0
5 9
x1≤3
问题2 ： 6 2 x1 3, x2 2 , Z 32 7 7
x1 ≥4
问题3 ： x1 4, x2 1, Z 29
上界： 32 下界： 29 2 7
• 第六步，定界过程
LP4的解满足整数约束，不必再分枝，它的目标函数值是28， 小于原有下界29，则下界仍为29； 现有上界为未分枝子问题中目标函数最大值，即为159/5。 LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于 现有下界29，则应继续分枝。
• 第七步，分枝过程
将不满足整数约束的变量x1 进行分枝，构造两个新的约束条件： x1≤ [14/5]=2，x1≥ [14/5] +1=3
• • • •
1
x2 =4
• • •
2
x2=3
2
1
• •
3
•
4
5x1 +7 x2 =35
2x1 + x2 =9
x2 =2
x1
• 求解相应的线性规划的最优解
问题8相应的线性规划的最优解： x1=2，x2 =3，Z8=27 问题9相应的线性规划的最优解：x1=7/5，x2 =4，Z9=142/5
x2≤3
问题8： x1 2, x2 3, Z 27
x2 ≥4
问题9： x1 1 2 2 , x2 4, Z 28 5 5
上界： 29 下界： 29
问题2：maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1≤3 x1, x2 ≥0 x1, x2取整数