第五章整数规划PPT课件
- 格式：pptx
- 大小：442.62 KB
- 文档页数：40
下载文档原格式
合集下载
运筹学 第05章 整数规划与分配问题
1
整数规划问题的提出
0 xj 1 表示项目j不被选中 表示项目j被选中 ( j 1,2,3,4,5)
解：决策变量：设
目标函数：期望收益最大
max z 10 x1 8 x 2 7 x3 6 x 4 9 x5
约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515 项目A、C、E之间必须且只需选择一项：x1+x3+x5=1 项目B、D之间必须且只需选择一项：x2+x4=1 项目C的实施要以项目D的实施为前提条件： x3 x4 归纳起来，其数学模型为：
n
(i 1,2, , m) ( j 1,2, , n)
2
整数规划问题的分类
根据变量取整数的情况，将整数规划分为：
（1）纯整数规划，所有变量都取整数.
（2）混合整数规划，一部分变量取整数,一部分变量取实数 （3）0-1整数规划 ,所有变量均取0或1
2
整数规划问题的求解思考
1
整数规划问题与其松弛问题
2
匈牙利法
例：用匈牙利法求解下列指派问题，已知效率矩阵分别如下：
任务 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 9
人员
甲 乙 丙 丁
2
匈牙利法
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
例：其中（2，2）（3，1）点为最大值，Z=4。常用的求解整数规划的方法有： 割平面法和
分支定界法，对于0－1规划问题采用隐枚举法和匈牙利法。
3
分派问题与匈牙利法
1
整数规划
第五章
整数规划
1．整数规划的基本概念 ． 2．分枝定界法解整数规划 ． 3．０－１规划 ． 4. 指派问题的解法
第一节
概
述
人们探讨某些线性规划问题， 人们探讨某些线性规划问题 ， 有时必须把 全部或部分决策变量限制为整数。 全部或部分决策变量限制为整数。这样的线性 整数规划。 规划问题，通常称为整数规划 规划问题，通常称为整数规划。作为线性规划 的特殊情况， 的特殊情况，整数规划也有最小化和最大化之 此外，整数规划还可以分成纯整数规划 纯整数规划和 别。此外，整数规划还可以分成纯整数规划和 混整数规划。二者的区别在于： 混整数规划。二者的区别在于：前者的决策变 量必定全部取整数 而后者的决策变量只是部 全部取整数。 量必定全部取整数。而后者的决策变量只是部 分取整数。 分取整数。
销售店 B1 B2 B3
表 2－1 － 需求量（ 周 需求量（箱/周） 50 60 30
表 2－2 －
产量 制药厂 (箱/周) 箱周 A1 A2 A3 A4 50 70 20 20
运资(元 箱 运资 元/箱) B1 3 10 1 4 B2 2 5 3 5模型
设 ： 制 药厂 i 每周运到销售店 j 的药品为 ij 药厂A 每周运到销售店B 的药品为x 箱（i = 1 , 2 ，3 ，4 ； j = 1 ，2 ，3 ）；
其中： 称为整数条件。 其中：“ xk´为整数 ” ,称为整数条件。
整数规划问题及其数学模型一律简称为整数 规划；整数规划删去整数条件之前和之后， 规划；整数规划删去整数条件之前和之后，分别 称为原整数规划 相应线性规划。 原整数规划和 称为原整数规划和相应线性规划。 按照四舍五入的规则， 按照四舍五入的规则，使相应线性规划的最 优解整数化，在通常情况下， 优解整数化，在通常情况下，不能作为原整数规 划的最优解。这可以从两个方面来说明： 划的最优解。这可以从两个方面来说明： 其一、相应线性规划的最优解化整后，已经 其一、相应线性规划的最优解化整后， 不是原整数规划的可行解， 不是原整数规划的可行解，当然也就不可能是它 的最优解。 的最优解。 其二、相应线性规划的最优解化整后，虽然 其二、相应线性规划的最优解化整后， 是原整数规划的可行解， 是原整数规划的可行解，但是有可能不是它的最 优解。 优解。
整数规划
1．整数规划的基本概念 ． 2．分枝定界法解整数规划 ． 3．０－１规划 ． 4. 指派问题的解法
第一节
概
述
人们探讨某些线性规划问题， 人们探讨某些线性规划问题 ， 有时必须把 全部或部分决策变量限制为整数。 全部或部分决策变量限制为整数。这样的线性 整数规划。 规划问题，通常称为整数规划 规划问题，通常称为整数规划。作为线性规划 的特殊情况， 的特殊情况，整数规划也有最小化和最大化之 此外，整数规划还可以分成纯整数规划 纯整数规划和 别。此外，整数规划还可以分成纯整数规划和 混整数规划。二者的区别在于： 混整数规划。二者的区别在于：前者的决策变 量必定全部取整数 而后者的决策变量只是部 全部取整数。 量必定全部取整数。而后者的决策变量只是部 分取整数。 分取整数。
销售店 B1 B2 B3
表 2－1 － 需求量（ 周 需求量（箱/周） 50 60 30
表 2－2 －
产量 制药厂 (箱/周) 箱周 A1 A2 A3 A4 50 70 20 20
运资(元 箱 运资 元/箱) B1 3 10 1 4 B2 2 5 3 5模型
设 ： 制 药厂 i 每周运到销售店 j 的药品为 ij 药厂A 每周运到销售店B 的药品为x 箱（i = 1 , 2 ，3 ，4 ； j = 1 ，2 ，3 ）；
其中： 称为整数条件。 其中：“ xk´为整数 ” ,称为整数条件。
整数规划问题及其数学模型一律简称为整数 规划；整数规划删去整数条件之前和之后， 规划；整数规划删去整数条件之前和之后，分别 称为原整数规划 相应线性规划。 原整数规划和 称为原整数规划和相应线性规划。 按照四舍五入的规则， 按照四舍五入的规则，使相应线性规划的最 优解整数化，在通常情况下， 优解整数化，在通常情况下，不能作为原整数规 划的最优解。这可以从两个方面来说明： 划的最优解。这可以从两个方面来说明： 其一、相应线性规划的最优解化整后，已经 其一、相应线性规划的最优解化整后， 不是原整数规划的可行解， 不是原整数规划的可行解，当然也就不可能是它 的最优解。 的最优解。 其二、相应线性规划的最优解化整后，虽然 其二、相应线性规划的最优解化整后， 是原整数规划的可行解， 是原整数规划的可行解，但是有可能不是它的最 优解。 优解。
运筹学第五章 整数规划ppt课件
，求解过程停止。 3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。
第二步：确定A的最优目标函数值z*的上下界，其上界即为 z ,再用观察法
找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。
第三步：判断 z 是否等于z 。若相等，则整数规划最优解即为其目标函
数值等于z的A的那个整数可行解；否则进行第四步。
2020/3/2
11
•割平面法，即通过添加约束条件，逐步切割可行区域的 边角余料，让其整数解逐步的露到边界或顶点上来，只要 整数解能曝露到顶点上来，则就可以利用单纯形法求出来。
•关键是通过添加什么样的约束条件，既能让整数解往边 界露，同时又不要切去整数解，这个条件就是Gomory约束 条件。 •Gomory约束只是割去线性规划可行域的一部分，保留了 全部整数解。
2020/3/2
7
7
第二节 割平面法
2x1 2x2 11
13/4,5/2
松弛问题 x1+x2≤5 第二次切割
2020/3/2
第一次切割 4,1
8
设纯整数规划
n
m a x Z c j x j j 1
s
.t
.
n j 1
aij x j
bi
x
j
0且
为
整
数
，
j
1,L
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证yi=0 xi=0 这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500
第二步：确定A的最优目标函数值z*的上下界，其上界即为 z ,再用观察法
找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。
第三步：判断 z 是否等于z 。若相等，则整数规划最优解即为其目标函
数值等于z的A的那个整数可行解；否则进行第四步。
2020/3/2
11
•割平面法，即通过添加约束条件，逐步切割可行区域的 边角余料，让其整数解逐步的露到边界或顶点上来，只要 整数解能曝露到顶点上来，则就可以利用单纯形法求出来。
•关键是通过添加什么样的约束条件，既能让整数解往边 界露，同时又不要切去整数解，这个条件就是Gomory约束 条件。 •Gomory约束只是割去线性规划可行域的一部分，保留了 全部整数解。
2020/3/2
7
7
第二节 割平面法
2x1 2x2 11
13/4,5/2
松弛问题 x1+x2≤5 第二次切割
2020/3/2
第一次切割 4,1
8
设纯整数规划
n
m a x Z c j x j j 1
s
.t
.
n j 1
aij x j
bi
x
j
0且
为
整
数
，
j
1,L
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证yi=0 xi=0 这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500
运筹学 第四版 第五章 整数规划
货物/箱 甲 乙
托运限制/集 装箱
体积/米3 5 4
24
重量/百斤 2 5
13
利润/百元 20 10
表 3.1
货物/箱 甲 乙
托运限制/集 装箱
体积/米3 5 4
24
重量/百斤 2 5
13
利润/百元 20 10
解 设 x1,分x2 别为甲、乙两种货物的托运箱数.则这是一个
纯整数规划问题 .其数学模型为:
(pzreorgor-aomnme iinngte)ger linear
若不考虑整数条件，由余下的目标函数和约束条件构成
的规划问题称为该整数规划问题的松弛问题（slack
problem）
n
max Z (或 min Z ) c j x j j 1
整数线性规划数学
n
st. j1 aij x j
max Z 20 x1 10 x2
5x1 4x2 24 s.t 2x1 5x2 13
x1, x2 0, 整数
（1）
若暂且不考虑 x1, x取2 整数这一条件.则(1)就变为下列 线性规划 :
max Z 20 x1 10 x2
s.t
52xx11
4x2 5x2
24 13
x1, x2 0
目前，常用的求解整数规划的方法有： 分支定界法和割平面法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。
§2 解纯整数规划的割平面法
考虑纯整数规划问题
n
max Z cjxj j 1
n
aijxj bis.tj 1xj0
xj取整数
i 1, 2....m
j 1, 2...n j 1, 2,..n
n
max Z (或 min Z ) c j x j j 1
《整数线性规划》PPT课件_OK
19
物品 1 2 3 4 5 6 7 8 9 10
体积 200 350 500 430 320 120 700 420 250 100
价格 15 45 100 70 50 75 200 90 20 30
20
问题分析
• 变量—对每个物品要确定是否带同时要确定放在哪个 包裹里，如果增加一个虚拟的包裹把不带的物品 放在里面，则问题就转化为确定每个物品放在哪 个包裹里。如果直接设变量为每个物品放在包裹 的编号，则每个包裹所含物品的总容量就很难写 成变量的函数。为此我们设变量为第i个物品是否 放在第j个包裹中
0 0 0 0 m1 0 n 0 0
1 1 1
a1m1 a1n 0
arm 1
arn 0
0
1 amm 1 amn 0
1 arm1 arm1 arn arn
cB B 1b b1
br
bm
br br61
x1 x2 xr
0 0 0
1 1 1
0
xm xm1 xn s r
0 m1 0 n 0 0 cB B 1b
）万元，问应如何选择项
目使得5年后总收益最大？
c j j 1,2...,n bj
7
模型
• 变量—每个项目是否投资
x 1,0 • 约束—总金额不超过限制 j
j 1,2...,n
• 目标—总收益最大
n
bjxj B
j 1
n
max c j x j
8
j 1
n
m ax c j x j j 1
n
对问题 2 继续分枝
情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的解进行比较，结论如情况 4 或 5
物品 1 2 3 4 5 6 7 8 9 10
体积 200 350 500 430 320 120 700 420 250 100
价格 15 45 100 70 50 75 200 90 20 30
20
问题分析
• 变量—对每个物品要确定是否带同时要确定放在哪个 包裹里，如果增加一个虚拟的包裹把不带的物品 放在里面，则问题就转化为确定每个物品放在哪 个包裹里。如果直接设变量为每个物品放在包裹 的编号，则每个包裹所含物品的总容量就很难写 成变量的函数。为此我们设变量为第i个物品是否 放在第j个包裹中
0 0 0 0 m1 0 n 0 0
1 1 1
a1m1 a1n 0
arm 1
arn 0
0
1 amm 1 amn 0
1 arm1 arm1 arn arn
cB B 1b b1
br
bm
br br61
x1 x2 xr
0 0 0
1 1 1
0
xm xm1 xn s r
0 m1 0 n 0 0 cB B 1b
）万元，问应如何选择项
目使得5年后总收益最大？
c j j 1,2...,n bj
7
模型
• 变量—每个项目是否投资
x 1,0 • 约束—总金额不超过限制 j
j 1,2...,n
• 目标—总收益最大
n
bjxj B
j 1
n
max c j x j
8
j 1
n
m ax c j x j j 1
n
对问题 2 继续分枝
情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后 续分枝所得到的解进行比较，结论如情况 4 或 5
运筹学 第五章 整数规划PPT课件
x 32
x 42
400
x 13
x 23
x 33
x 43
300
x 14 x 24 x 34 x 44 1 5 0
s
.t
x 11 x 21
x 12 x 22
x 13 x 23
x 14 x 24
400 600
x
31
x 32
x 33
x 34
200 y3
x 41 x 42 x 43 x 44 2 0 0 y 4
max Z 85x11 92x12 73x13 90x14 95x21 87 x22 78x23 95x24 82x31 83x32 79x33 90x34 86x41 90x42 80x43 88x44
要求每人做一项工作，约束条件为：
x11 x12 x13 x14 1
例5.3 设整数规划问题如下
max Z x1 x2
14 x1 9 x2 51
6 x1
3x2
1
x
1
,
x2
0且 为 整 数
首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）
max Z x 1 x 2
14
x1 6x
1
9x2 3x
2
51 1
ቤተ መጻሕፍቲ ባይዱ
x
1
,
x2
0
用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6
在很多场合，我们建立最优化模型时，实际问题要求决 策变量只能取整数值而非连续取值。此时，这类最优化 模型就称为整数规划（离散最优化）模型。
整数规划的求解往往比线性规划求解困难得多，而且， 一般来说不能简单地将相应的线性规划的解取整来获得。
整数规划
6
单 销地 厂址 价
B1 c11 M cm1 b1
B2 c12
L L L
Bn c1n c2n M cmn bn
生产 能力
建设 费用
A1 A2 M Am
销量
a1 a2
f1 f2
c 21 c 22
M cm 2 L b2 L
M M am fm
7
表示从工厂运往销地的运量(i=1.2…m、j=1.2…n), 解：设xij表示从工厂运往销地的运量 1 在Ai建厂 又设 Yi＝ （i=1.2…m） ） 0 不在 i建厂 不在A 模型： 模型： min Z = ∑∑ cij xij + ∑ fi yi
10
整数线性规划的分类
整数线性规划：所有变量均为整数（这时引进的松 弛变量和剩余变量可以不要求取整数）。 混合整数线性规划：只有一些而不是全部变量为整 数。 0-1整数线性规划：所有决策变量只能取0和1两个整 数。
11
整数规划与线性规划的关系
从数学模型上看整数规划似乎是线性规划的一种特 殊形式，求解只需在线性规划的基础上，通过舍入 取整，寻求满足整数要求的解即可。但实际上两者 却有很大的不同，通过舍入得到的解（整数）也不 一定就是最优解，有时甚至不能保证所得倒的解是 整数可行解。
s.t. 2 x1 + 3x2 ≤ 14 x1 + 0.5 x2 ≤ 4.5 x1、x2 ≥ 0 x1、x2为整数
(1) (2) (3) (4)
15
整数规划问题及其数学模型
例1
首先，不考虑整数约束条件（4），用单纯形法对相 应线性规划求解，其最优解为： x1=3.25,x2=2.5,max z=14.75 因为最优解都不是整数，所以用四舍五入凑整的方法 看能否得到最优解？ 最后，用图解方法来看寻找整数最优解的过程。
整数规划及分支定界法42页PPT
谢谢！
36、自己的鞋子，自己知道紧在哪里。——西班牙
37、我们唯一不会改正的缺点是软弱。——拉罗什福科
xiexie! 38、我这个人走得很慢，但是我从不后退。——亚伯拉罕·林肯
39、勿问成功的秘诀为何，且尽全力做你应该做的事吧。——美华纳
1、不要轻言放弃，否则对不起自己。
2、要冒一次险!整个生命就是一场冒险。走得最远的人，常是愿意 去做，并愿意去冒险的人。“稳妥”之船，从未能从岸边走远。-戴尔．卡耐基。
梦 境
3、人生就像一杯没有加糖的咖啡，喝起来是苦涩的，回味起来却有 久久不会退去的余香。
整数规划及分支定界法 4、守业的最好办法就是不断的发展。 5、当爱不能完美，我宁愿选择无悔，不管来生多么美丽，我不愿失 去今生对你的记忆，我不求天长地久的美景，我只要生生世世的轮 孔子
运筹学--整数规划 ppt课件
三、投资问题
某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末
回收本利115%，但要求第一年投资最低金额为4万元，第 二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％， 但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%， 但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利 息6%，此项投资金额不限。
= 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D =
1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D =
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以 保证当 yi = 0 时，xi = 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 -
200y3
s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3
一、投资场所的选择
京成畜产品公司计划在市区的东、西、南、北四区建立销售
门市部，拟议中有10个位置 Aj ( j＝1，2，3，…，10)可供 选择，考虑到各地区居民的消费水平及居民居住密集度，规
整数规划ppt课件
可行解的凸组合不一定满足整数要求，因而不一定
仍为可行解）。
2021精选ppt
第13页
产生问题：利用对松弛问题的最优解中不符合整
数要求的分量简单地取整，是否能得出整数规划
问题的最优解呢？
2021精选ppt
第14页
3. 对松弛问题的最优解中不符合整数要求的分量简 单地取整，所得到的问题解：
不一定是整数线性规划问题的最优解。
θi
CB XB
b
x1 x2
x3
x4
x5
x6
6 x2 88/23 0 1 4/23 -3/23 0 0
5 x1 72/23 1 0 -3/23 8/23 0 0
-M x6 4 1 0 0 0 -1 1
c j– z j
2021精选ppt
第43页
将 x1 的系数列向量变为单位向量，并计算检验数
cj
5
CB XB
第8页
整数线性规划
松弛问题
n
max( 或 min) z c j x j j1
n
a ij x j ( 或 ， )b i , i 1 ,..., m
j1 x j 0 , j 1 ,..., n
x
1
,...,
x n中部分或全部取整数
n
max( 或 min) z c j x j j1
甚至也不一定是整数线性规划问题的可行解。
2021精选ppt
第15页
例：
mz a 2 xx 0 1 1x 0 2
5 x 1 4 x 2 24
2 x
x
1
1
,
x2
5x
2
0
13
x 1 , x 2 整 数
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
10
xi 5
i 1
x1 x8 1
x7 x8 1 x3 x5 1
x4
x5
1
x5 x6 x7 x8 2
i 1,…,10
2021/2/12
10
例3、应用 0-1 变量解决含互斥约束条件问题
设：工序 B 有两种方式完成
方式（1）的工时约束: 0.3X1 + 0.5X2 ≤ 150 方式（2）的工时约束: 0.2X1 + 0.4X2 ≤ 120
①或选择S1和S7，或选择S8； ②选择了S3或S4就不能选S5，反之，选了S5， 则不能选S3或S4； ③在S5~S8中最多选两个。 建立这个问题的0-1型整数规划模型
2021/2/12
9
解：令
xi
1 0
不选选择择钻钻探探SiS井i井位位（i＝1，…，10）
10
max z ci xi
i 1
0-1型整数线性规划(zero-one integer linear
programming)
——决策变量只能取值0 或 1。
2021/2/12
4
整数规划问题实例
例1、 某公司准备投资 50 万元为其产品做广告， 广告代理商给公司的有关广告方式的费用和其 效果情况如下表，公司面临的管理决策问题是 广告总费用不超过 50 万元的基础上选择哪些 广告方式，使得潜在顾客数尽可能地多。
2021/2/12
xj ≥ 0 yj 为0--1变量，i = 1,2,3 14
例5、人员时间安排
某航空公司希望更有效地安排售票员的工作 时间，以减少工资支出。每个售票员上班后将连 续工作8个小时，但并非每时每刻都有一样多的 顾客，因此，适当地将一天分成8个时段，每个 时段2小时（假定每天的8：00 至24：00 为售票 工作时间）。应该如何计划每个时段初的上班售 票员人数，才能使一天雇佣的售票员总人数最少？
2021/2/12
7
例2、模型 设：
Ai =
1 选择 Ai 建立门市 0 不选择 Ai 建立门市
Max
Z = ∑ ci Ai
∑ bi Ai
≤B
A1 + A2 + A3
≤2
A4 + A5
≥1
A6 + A7 ≥ 1
Ai = 0 或 1 ，（i = 1，2，3，4，5，6，7）
2021/2/12
8
例 某钻井队要从以下10个可供选择的井位中 确定5个钻井探油，使总的钻探费用为最小。 若10个井位的代号为S1…S10，相应的钻探费用 为c1…c10，并且井位选择上要满足下列限制条 件：
2021/2/12
6
例2、某公司在城市的东、西、南三区建立门市部。 拟议中有7个位置（地点）Ai（i=1，2，…，7） 可供选择。公司规定：
在东区，由 A1，A2，A3 三个点中至多选两个； 在南区，由 A4，A5 两个点中至少选一个； 在西区，由 A6，A7 两个点中至少选一个。 如果选用 Ai 点，设备投资估计为 bi 元，每年 可获利润估计为 ci 元，但投资总额不能超过 B 元。 问公司选择哪几个点可使年总利润最大？
2021/2/12
2
一、整数规划的数学模型及解的特点
整数线性规划数学模型的一般形式
整数规划（IP）
松弛问题
整数线性规划（ILP）的数学模型：
∑n
max（或min）z = c j x j
5.1a
∑n
j =1
aij x j ≤（或 = ，≥）bi i 1，2，，m 5.1b
st.
j =1
xj 0
j 1，2，，n
5.1c
x1, x2 ,, xn中部分或全部取整数 5.1d
2021/2/12
3
整数规划问题的类型
纯整数线性规划(pure integer linear programming) ——全部决策变量都必须取整数值。
混合整数线性规划(mixed integer linear programming) ——决策变量中一部分必须取整数值， 另一部分可以不取整数值。
于是前面两个互斥的约束条件可以统一为如下三个约束条件： 0.3X1 + 0.5X2 ≤ 150 + M1y1 0.2X1 + 0.4X2 ≤ 120 + M2y2 y1 + y2 = 1
其中 M1 ，M2 都是足够大的正数。
2021/2/12
12
例4．固定费用问题
有三种资源被用于生产三种产品，资源量、产 品单件可变费用及售价、资源单耗量及组织三种产 品生产的固定费用见下表。要求制定一个生产计划， 使总收益最大。
问题是完成工序 B 只能从两种方式中任选一种， 如何将这两个互斥的约束条件统一在一个线性规划 模型中呢？
2021/2/12
11
例3、模型
引入 0-1 变量
0 若工序 B 采用方式（1）完成 y1 = 1 若工序 B 不采用方式（1）完成 y2 = 0 若工序 B 采用方式（2）完成
1 若工序 B 不采用方式（2）完成
整 数 规划
(Integer Programming)
整数规划的模型
分支定界法
0－1 整数规划
指派问题
2021/2/12
1
在很多场合，我们建立最优化模型时，实际问 题要求决策变量只能取整数值而非连续取值。 此时，这类最优化模型就称为整数规划（离散 最优化）模型。
整数规划的求解往往比线性规划求解困难得多， 而且，一般来说不能简单地将相应的线性规划的 解取整来获得。
Ⅰ Ⅱ Ⅲ 资源量
A
2
4
8
500
B
2
3
4
300
C
1
2
3
单件可变费用 4
5
6
固定费用 100 150 200
单件售价 2021/2/12
8
10 12
100
13
解：设xj为第j种产品的生产数量，j=1,2,3；
1 当生产第 j种产品, 即 xj＞ 0 时 yj = 0 当不生产第 j种产品即 xj = 0 时 引入约束 xi ≤ M yi ，i =1，2，3，M充分大，
广告方式
电视台
广告费（万元）
40
ห้องสมุดไป่ตู้
潜在顾客数（万人） 40
报纸 15 20
杂志 20 25
电台 10 10
2021/2/12
5
例1、 模型 设：xi（i = 1,2,3,4）—— 表示 4 种广告方式。
xi =
1 选择第 i 种广告方式 0 不选择第 i 种广告方式
Max Z = 40x1 + 20x2 + 25x3 + 10x4 40x1 + 15x2 + 20x3 + 10x4 ≤ 50 x1 ，x2 ，x3 ，x4 = 0 或 1
以保证当 yi = 0 时，xi = 0 。 可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3
s.t. 2x1 + 4x2 + 8x3 ≤ 500
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi ，i =1，2，3，M充分大