没有合适的资源?快使用搜索试试~ 我知道了~
数学建模_优化问题_整数规划
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 8 浏览量
2022-06-04
23:49:04
上传
评论
收藏 193KB PDF 举报
温馨提示
试读
16页
数学建模_优化问题_整数规划
资源推荐
资源详情
资源评论
-16-
第二章 整数规划
§1 概论
1.1 定义
规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,
变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
1
o
变量全限制为整数时,称纯(完全)整数规划。
2
o
变量部分限制为整数的,称混合整数规划。
1.2 整数规划特点
(i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
21
min xxz +=
0,0,542
2121
≥≥=+ xxxx
其最优实数解为:
4
5
min,
4
5
,0
21
=== zxx 。
③有可行解(当然就存在最优解),但最优解值变差。
例 2 原线性规划为
21
min xxz +=
0,0,642
2121
≥≥=+ xxxx
其最优实数解为:
2
3
min,
2
3
,0
21
=== zxx 。
若限制整数得:
2min,1,1
21
=
== zxx 。
(ii) 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类:
(i)分枝定界法—可求纯或混合整数线性规划。
(ii)割平面法—可求纯或混合整数线性规划。
(iii)隐枚举法—求解“0-1”整数规划:
①过滤隐枚举法;
②分枝隐枚举法。
(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。
(v)蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系
统搜索,这就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小的子
集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称
为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,
-17-
这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land
Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解,所以现在它已是解
整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂
选址问题、背包问题及分配问题等。
设有最大化的整数规划问题
A,与它相应的线性规划为问题
B
,从解问题
B
开始,
若其最优解不符合
A
的整数条件,那么
B
的最优目标函数必是
A
的最优目标函数
*
z 的
上界,记作
z ;而 A 的任意可行解的目标函数值将是
*
z 的一个下界 z 。分枝定界法就
是将
B
的可行域分成子区域的方法。逐步减小 z 和增大 z ,最终求到
*
z 。现用下例来
说明:
例 3 求解下述整数规划
21
9040Max xxz +=
⎪
⎩
⎪
⎨
⎧
≥
≤+
≤+
且为整数0,
70207
5679
21
21
21
xx
xx
xx
解 (i)先不考虑整数限制,即解相应的线性规划
B
,得最优解为:
355.8779,8168.1,8092.4
21
=
=
= zxx
可见它不符合整数条件。这时
z
是问题
A
的最优目标函数值
*
z 的上界,记作 z 。而
0,0
21
== xx 显然是问题 A 的一个整数可行解,这时 0
=
z ,是
*
z 的一个下界,记作 z ,
即
3560
*
≤≤ z 。
(ii)因 为
21
,xx 当前均为非整数,故不满足整数要求,任选一个进行分枝。设选
1
x
进行分枝,把可行集分成 2 个子集:
44.8092][
1
=≤x
,
514.8092][
1
=
+
≥x
因为 4 与 5 之间无整数,故这两个子集的整数解必与原可行集合整数解一致。这
一步称为分枝。这两个子集的规划及求解如下:
问题
1
B :
21
9040Max xxz
+
=
⎪
⎩
⎪
⎨
⎧
≥≤≤
≤+
≤+
0,40
70207
5679
21
21
21
xx
xx
xx
最优解为:
349,1.2,0.4
121
=
== zxx 。
问题
2
B :
21
9040Max xxz
+
=
⎪
⎩
⎪
⎨
⎧
≥≥
≤+
≤+
0,5
70207
5679
21
21
21
xx
xx
xx
最优解为:
4.341,57.1,0.5
121
=
== zxx 。
再定界:
3490
*
≤≤ z 。
(iii)对问题
1
B 再进行分枝得问题
11
B 和
12
B ,它们的最优解为
-18-
340,2,4:
112111
=
=
=
zxxB
327.14,00.3x1.43,:
122112
=
=
=
zxB
再定界: 341340
*
≤≤ z ,并将
12
B
剪枝。
(iv)对问题
2
B 再进行分枝得问题
21
B 和
22
B ,它们的最优解为
083,00.1x5.44,:
222121
=
=
=
zxB
22
B 无可行解。
将
2221
,BB 剪枝。
于是可以断定原问题的最优解为:
340,2,4
*
21
=== zxx
从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为:
开始,将要求解的整数规划问题称为问题
A
,将与它相应的线性规划问题称为问
题
B
。
(i)解问题
B
可能得到以下情况之一:
(a)
B
没有可行解,这时 A 也没有可行解,则停止.
(b)
B
有最优解,并符合问题 A 的整数条件,
B
的最优解即为 A 的最优解,则
停止。
(c)
B
有最优解,但不符合问题 A 的整数条件,记它的目标函数值为 z 。
(ii)用观察法找问题 A 的一个整数可行解,一般可取 njx
j
,,1,0 L
=
=
,试探,
求得其目标函数值,并记作
z 。以
*
z 表示问题 A 的最优目标函数值;这时有
zzz ≤≤
*
进行迭代。
第一步:分枝,在
B
的最优解中任选一个不符合整数条件的变量
j
x ,其值为
j
b ,
以
][
j
b 表示小于
j
b 的最大整数。构造两个约束条件
][
jj
bx ≤
和
1][ +≥
jj
bx
将这两个约束条件,分别加入问题
B
,求两个后继规划问题
1
B 和
2
B 。不考虑整数条件
求解这两个后继问题。
定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出
最优目标函数值最大者作为新的上界
z 。从已符合整数条件的各分支中,找出目标函数
值为最大者作为新的下界 z ,若无作用 z 不变。
第二步:比较与剪枝,各分枝的最优目标函数中若有小于
z 者,则剪掉这枝,即
以后不再考虑了。若大于
z
,且不符合整数条件,则重复第一步骤。一直到最后得到
zz =
*
为止。得最优整数解 njx
j
,,1,
*
L= 。
§3
10 − 型整数规划
10 − 型整数规划是整数规划中的特殊情形,它的变量
j
x 仅取值 0 或 1。这 时
j
x 称
为
10 − 变量,或称二进制变量。
j
x
仅取值 0 或 1 这个条件可由下述约束条件:
10
≤
≤
j
x ,整数
-19-
所代替,是和一般整数规划的约束条件形式一致的。在实际问题中,如果引入
10 −
变
量,就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们
先介绍引入
10 −
变量的实际问题,再研究解法。
3.1 引入
10
−
变量的实际问题
3.1.1 投资场所的选定——相互排斥的计划
例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置(点)
)7,,2,1( L=iA
i
可供选择。规定
在东区。由
321
,, AAA 三个点中至多选两个;
在西区。由
54
, AA 两个点中至少选一个;
在南区,由
76
, AA 两个点中至少选一个。
如选用
i
A 点,设备投资估计为
i
b 元,每年可获利润估计为
i
c 元,但投资总额不能
超过
B
元。问应选择哪几个点可使年利润为最大?
解题时先引入 10 − 变量 )7,,2,1( L
=
ix
i
令
⎩
⎨
⎧
=
.0
,1
点没被选中当
点被选中当
,
,
i
A
i
A
i
x 7,,2,1 L
=
i .
于是问题可列写成:
i
i
i
xcz
∑
=
=
7
1
Max
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
=≥+
≥+
≤++
≤
∑
=
10,1
1
2
76
54
321
7
1
或
i
i
ii
xxx
xx
xxx
Bxb
3.1.2 相互排斥的约束条件
有两个相互排斥的约束条件
2445
21
≤
+ xx 或 4537
21
≤
+
xx 。
为了统一在一个问题中,引入
10
−
变量
y
,则上述约束条件可改写为:
⎪
⎩
⎪
⎨
⎧
=
−+≤+
+≤+
10
)1(4537
2445
21
21
或y
Myxx
yMxx
其中
M
是充分大的数。
约束条件
0
1
=x
或
800500
1
≤
≤
x
可改写为
⎩
⎨
⎧
=
≤≤
10
800500
1
或y
yxy
剩余15页未读,继续阅读
资源评论
Sherry_shiry
- 粉丝: 2
- 资源: 1097
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功