当前位置：文档之家 › 管理运筹学案例演示混合整数规划

管理运筹学案例演示混合整数规划

  • 格式：ppt
  • 大小：1.54 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

混合整数规划及其应用

混合整数规划及其应用

混合整数规划及其应用混合整数规划（Mixed Integer Programming，MIP）是运筹学中一个重要的分支，它可以用于解决包括生产计划、物流运输、资源调度等实际问题。

本文将探讨混合整数规划的基本概念、典型模型以及应用范例。

一、基本概念1.定义混合整数规划是指在线性规划基础上加入了整数变量的限制条件，有时还将变量限制为 0/1 取值，即 0 表示不选取某个变量，1 表示选取某个变量。

2.数学模型混合整数规划的一般数学模型如下：$max\ Z=c^{T}x+d^{T}y$$s.t.$$A x+B y \leq b$$x\in R^{n}, y \in Z^{m}$其中，$x$ 是连续变量向量，$y$ 是整数变量向量，目标函数$Z$ 为一线性函数，$A$, $B$ 为系数矩阵，$b$ 为约束条件的取值。

本模型中整数变量 $y$ 的限制条件可以是 $y \in\{0,1\}^{m}$ 也可以是 $y \in Z^{m}(m>0)$。

3.求解方法求解混合整数规划可以采用分枝界限法、Gomory 切割法、随机搜索等方法。

其中，分枝界限法是运筹学中最基本的解法，其最优性原理为“不断将问题分解成子问题，逐步地去掉某些变量，直到问题变为纯整数规划问题为止，然后通过确定某些变量取值来求解”。

随机搜索法则是通过不断随机生成可行解并比较其目标值的大小进行求解。

二、典型模型1.背包问题背包问题中，有 $n$ 种不同体积和不同价值的物品，需要将它们装入一个容量为 $V$ 的背包。

每种物品只有选择或不选择两种情况。

设$w_{i}$ 为第 $i$ 种物品的价值，$v_{i}$ 为第 $i$ 种物品的体积，则该问题的混合整数规划模型为：$max\ \sum_{i=1}^{n} w_{i} x_{i}$$s.t.$$\sum_{i=1}^{n} v_{i} x_{i} \leq V$$x_{i} \in\{0,1\}$2.生产调度问题生产调度问题中，对于 $n$ 种产品需要进行加工，但是加工需要设备并且不同设备的加工能力存在差异。

运筹学第五章整数规划

运筹学第五章整数规划

分解 ai0 , j和 bi0 成最大整数与正分数之和：
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:21
xi0 ai0 , j x j bi0 xi0 ( Ni0 , j f i0 , j )x j Ni0 f i0 xi0 Ni0 , j x j Ni0 f i0 f i0 , j x j
S1
x2 2
B: x1=2,x2=23/9 Z=41/9
x2 3
D: S12 x1=33/14,x2=2 Z=61/14
S11
无可行解
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:15
对S12分枝：
构造约束：
x1 3
X
2 5
4
和
x1 2
3
3 10 A( , ) 2 3
形成分枝问题S121 和S122，得解E和F
形成松弛问题2
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:24
CB XB 3 x1 -1 0 0 x2 x4 x6
3 -1 0 0 x1 x2 x3 x4 1 0 1/7 0 0 0 0 0 1 -2/7 0
0 x5 2/7 3/7
0 x6 0 0 0 1 0
b 13/7 9/7 31/7 -6/7
首先不考虑变量的整数约束，求解相应的线性规划问题：
z0
Max z = CX AX = b X0
D
C
下界
O Ir
Max z = CX AX = b xr Ir X0 Max z = CX AX = b xr Ir+1 X0

管理运筹学-整数规划

管理运筹学-整数规划

§3整数规划的应用(5)
五、投资问题 例8．某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额 为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5 万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6 万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额 为最大? 解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是0—1变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（ i = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定：2年投资C项目8万元时，取值为4； 2年投资C项目6万元时，取值为3； 2年投资C项目4万元时，取值为2； 2年投资C项目2万元时，取值为1； 2年不投资C项目时， 取值为0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年
解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 xj 为0--1变量，i = 1,2,3,……,10

混合整数线性规划教育课件

混合整数线性规划教育课件
⑴.若( LP )没有可行解，则( IP )也没有可行解，停止 计算。
⑵.若( LP )有最优解，并符合( IP )的整数条件，则 ( LP )的最优解即为( IP )的最优解，停止计算。
⑶.若( LP )有最优解，但不符合( IP )的整数条件，转 入下一步。为讨论方便，设( LP )的最优解为：
0 不在Ai建厂
模型： min Z
m
cij xij fi yi
i 1
n
xij ai yi
(i 1.2 m)
j 1
m
xij b j
i1
(j 1.2 n)xij0,源自yi0 或 1 (i
1.2
m、 j 1.2 n)
（二）、整数规划的数学模型
一般形式
n
maxZ(或min Z) cj xj j1
x1 . x2. x3
(0)
( 0. 0. 0 ) 0 ( 0. 0. 1 ) 5 ( 0. 1. 0 ) -2 ( 0. 1. 1 ) 3 ( 1. 0. 0 ) 3 ( 1. 0. 1 ) 8 ( 1. 1. 0 ) 1 ( 1. 1. 1 ) 4
B B 零件 方
个数 式
零件
1
零件
n 毛坯数
A1
b a11 a1 n 1
b A m
a m 1 a mn m
设：xj
表示用Bj
(j=1.2…n)
n
种方式下料根数
模型： min Z x j
j 1
n
aij x j bi
(i 1.2 m)
j 1
x
j
0
(j 1.2 n)且为整数
例二、某公司计划在m个地点建厂，可供选择的地点有 A1,A2…Am ，他们的生产能力分别是a1,a2,…am（假设生

《管理运筹学》03- 整数规划

《管理运筹学》03- 整数规划

ppt课件整数规划整数规划
3
3.1 整数规划问题及其建模
例3-1背包问题
max z= 17x1 +72x +35x
s.t.
10x1 2 +42x 3 +20x ≤50
x1, 2 x2,
3 x3
≥0
x1,
x2,
x3为整数
线性规划最优解为: x1=0，x2=0，x3=2.5
而整数规划的最优解是 x1=1，x2=0，x3=2
T
5
ppt课件整数规划整数规划
22
-2x2+3x1+5x3≥5 ◎
点
条件
◎
①
②
③
④
满足条件？ 是（T）否（F）
Z
（0 1 0） 3
F
（0 1 1） 8
0
2
1
5
T
8
-2x2+3x1+5x3≥8 ◎
点
条件
◎
①
②
③
④
满足条件？ 是（T）否（F）
Z
（1 0 0） -2
F
（1 0 1） 3
F
（1 1 0） 1
工件
A
B
C
D
工人
效
甲
14
9
4
15
率
乙
11
7
9
10
矩
丙
13
2
10
5
阵
丁
17
9
15
13
ppt课件整数规划整数规划
24
设xij=1表示第 i人送j货，否则xij=0
上述问题的模型为：
44

《管理运筹学》演示(整数规划)

《管理运筹学》演示(整数规划)
分枝定界法的求解步骤: 分枝定界法的求解步骤: 1. 先不考虑整数约束条件，求解相 应的线性规划，有以下几种情况： 如果线性规划没有可行解，则整 数规划也没有可行解，停止计算； 如果线性规划有最优解，且为整 数最优解，则这个解为整数规划的 整数最优解； 如果线性规划有最优解，但为非 整数最优解，则转入下一步；
解：先不考虑整数约束，求相应的线性规划的最优解，用单纯 形法求解，标准型和初始单纯形表如下： 1 1 0 0
C XB B
0 0
b
1 4
x 1
-1 3 1
x2
1 1 1
x3
1 0 0
x4
0 1 0
σj
x3 x4
⋮
经过若干步迭代后，得到如下最优表及最优解：
cj
1
1
0
0
C XB B
1 1
b
3/4 7/4 -5/2
x4
1/3 0 -1 -1/3
x5
1/12 0 -1/3 -1/6
x 1 x2
σj
x3
整数最优解： x1=1 , x2=1 , x3=1 , x4= x5=0 , max
z =2
例：用隐枚举法求0 例：用隐枚举法求0－1规划
3 x1 − 2 x2 + 5 x3 ≥ 3 (0) x + 2x − x ≤ 2 x1 + 2 x2 − x3 ≤ 2 () 1 2 3 1 x + 4x + x ≤ 4 (2) 2 3 x1 + 4 x2 + x3 ≤ 4 1 ⇒ (3 ) x1 + x2 ≤ 3 x1 + x2 ≤ 3 4 x + x ≤ 6 (4) 3 4 x2 + x3 ≤ 6 2 x1 , x2 , x3 = 0, 或1 x1 , x2 , x3 = 0, 或1 解：先找出一个可行解，显然， x1 = 1, x2 = 0, x3 = 0 满足约束

第六章 运筹学 整数规划案例

第六章 运筹学 整数规划案例

第六章整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。

1、 max z=3x1+2x2S.T. 2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、 min f=10x1+9x2S.T. 5x1+3x2≥45x1≥8x2≤10x1、x2≥06.2 求解下列整数规划问题1、 min f=4x1+3x2+2x3S.T. 2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3S.T. -4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。

3、max Z=2x1+3x2+5x3+6x4S.T. 5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19约束条件x1 + x2+x3≤30x4+ x5＋x6-10 x16≤0x7+ x8＋x9-20 x17≤0x10+ x11＋x12-30 x18≤0x13+ x14＋x15-40 x19≤0x1 + x4+ x7+x10+ x13＝30x2 + x5+ x8+x11+ x14＝20x3 + x6+ x9+x12+ x15＝20x i为非负数（i=1,2…..8）x i为非负整数（i=9,10…..15）x i为为0－1变量（i=16,17…..19）解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：8606.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。

运筹学01整数规划

运筹学01整数规划
货物体积每箱m3重量每箱吨利润每箱百元托运限制20分别表示甲乙两种货物的托运箱数则其整数规划数学模型为当采用船运方式当采用车运方式其中一般情况下m个约束条件中选择q个约束条件则可变成为
第四节 0-1整数规划
• 问题的提出：
0-1整数规划是线性规划及整数规划的一种特殊形式。 模型结构和形式是线性规划，只是决策变量取0或1。 例1：投资场所的选定——相互排斥的计划 某公司拟在城市的东、西、南三区建立分公司，拟议中有七 个位置Ai（i=1, 2,…,7), 规定在东区A1,A2,A3个点中至多选二个; 在 西区A4,A5两点中至少选一个; 在南区A6,A7中至少选一个, 如选用Ai 点,设备投资估计为bi元, 每年可获利润估计为ci元, 但投资总额不能 超过B元, 问应选择哪几个点可年利润最大?
解：求解过程见下表
(x1,x2,x3) （0,0,0）
(0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)
Z值 0 5 -2 3 3 8 1 6
约束条件

过滤条件 Z0 Z5

Z8
所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8.
令
xi

1

0
当Ai点被选用 当Ai点未被选用
i=1, …,7
7
max Z c i x i
i1

7

bixi
B
i1
x1 x 2 x 3 2
s .t

x
4

x5
1

x
0 or 1
例2: 相互排斥的约束条件

管理运筹学案例演示混合整数规划

管理运筹学案例演示混合整数规划

yi
当 选 择 Ai 地 建 厂 时; 当 不 选 择 Ai 地 建 厂 时 。
约束条件: A1产量限制条件;及A2、 A3、 A4、 A5准备建设的新厂, 其产量约束条件；
满足销量的约束条件；
目标函数: 总的固定成本和总的运费之和最小。
（2）在上述模型的基础上加上一个约束条件，即：
y2 ? y3 ? 1
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。
该广告计划模型为：
max z ? 40x1 ? 90x2 ? 50x3 ? 2x4
D Goal Programmingmic Programming
E Transportation Programming
1 2 3 4 5 6 7 N Simulation
F Assignment
123456
8 9 10 11 12 O Forecasting
G Break-Even Analysis
x1 ? y1M x2 ? y2 M x3 ? y3 M
目标函数： 为扣除固定费用的利润最大化，即：
4x1 ? 5x2 ? 6x3 ? 100y1 ? 150y2 ? 200y3
该生产计划整数规划模型为：
max z ? 4x1 ? 5x2 ? 6x3 ? 100 y1 ? 150 y2 ? 200 y3

运筹学课件--第四章 整数规划

运筹学课件--第四章 整数规划
上述分枝过程可用下图表示
LP0:X=(3.57,7.14),Z0=35.7
x1≤3 x1≥4
LP1:X=(3,7.6) Z1=34.8
x2≤6
LP2:X=(4,6.5) Z2=35.5
x2≥7 无可行解 x1≥5 LP5:X=(5,5) Z5=35
OR:SM OR:SM
LP3:X=(4.33,6) Z3=35.33
10
OR:SM OR:SM
第二节 整数规划求解
【例3.5 】用分枝定界法求解例3.1
max Z 4 x 1 3 x 2 1 . 2 x 1 0 . 8 x 2 10 2 x 1 2 . 5 x 2 25 x 1 , x 2 0 , 且均取整数
【解】先求对应的松弛问题（记为LP0）：
7
OR:SM OR:SM
第二节 整数规划求解
一、舍入化整法
为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到 与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出 了可行域，成为非可行解；或者虽是可行解，却不是最优解。

不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型，不考虑整数约束的最优解：
6
LP1 LP3
LP3:X=(4.33,6),Z3=35.33
C o
14
3
4
10
x1
OR:SM OR:SM
x2 ① ②
10 A
由于 Z 3 Z 1，选择 LP 3 进行分枝，增加约束 x 1 4 及 x 1 5，到线性规划 LP 4 及 LP 5：
max Z 4x1 3x2 LP1:X=(3,7.6),Z1=34.8 1.2x1 0.8x2 10 2x1 2.5x2 25 LP4 : LP4:X=(4,6),Z4=34 x1 4，x2 6，x1 4 x1 , x2 0 即x1 4, 可行域是一条线段 max Z 4x1 3x2

2.运筹学_整数规划案例

2.运筹学_整数规划案例
1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可 供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行 投资？ 1…对项目j投资 先引入0－1变量xj，令 xj＝ 0…否则 n
设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－ 1变量yi= 1表示在Ai设立仓库，否则不设。 设每个月的总花费为z，则上述问题的数学模型为 Min z＝200x11+400x12+500x13+300x21+250x22+450x23 +600x31+400x32+250x33+300x41+150x42+350x43+45000y1+5000 0y2+70000y3+40000y4 s.t. x11+x12+x13≤1000y1 x21+x22+x23≤1000y2 x31+x32+x33≤1000y3 x41+x42+x43≤1000y4 x11+x21+x31+x41≥600 x12+x22+x32+x42≥700 x13+x23+x33+x43≥800 y2-y4≤0 y1+y2+y3+y4≤3
y3+y4 ≤ 1
工厂选址运输问题
设有n个需求点，有m个可供选择的厂址， 每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。

运筹学第10讲：整数规划(一)

运筹学第10讲：整数规划(一)

x14-80y4<=0
x14-0.01y4>=0
x24-x14<=15
x34-x24<=15
x44-x34<=15 x54-x44<=15
取L=0.01，M=10000
x16-60y16>=0 x26-60y26>=0
最优值: Z*=1752.19
x36-60y36>=0 x46-60y46>=0
最优解：

x34+320y5+x36+x37-120y1-28y2-0.25x24-1.2x26-1.15x27=150
x44+x46+x47-140y1-28y2-65y3-0.25x34-1.2x36-1.15x37=0
x54+x56+x57-140y1-28y2-65y3-0.25x44-180y5-1.2x46-1.15x47=0
x6 + x7 + x8 ≥ 1 x1 + x4 + x6 ≤ 2 x2 + x8 ≤ 1 ∑xi = 5 xi=0或1, i =1,2,…,8
最优值: 9.32 最优解：
x2 = x3= x4=
x5= x6=1
其余xi = 0.
例2
混合整数规划问题
工厂A1 和 A2生产某种物资。由于该物资供不应求，故需再建一家工厂。
工厂A3 或 A4开工后，每年的生产费用估计分别为1200万元或1500万元。 现要决定应该建设工厂A3 还是 A4，才能使今后每年的总费用（即全部物 资运费和新工厂生产费用之和）最少。
运筹学
二、Ip问题的求解
第10讲：整数规划(一)
例：max

管理运筹学第四章整数规划与指派问题

管理运筹学第四章整数规划与指派问题

货物运输路线选择案例
案例描述
某物流公司需要为其客户提供从起点到终点的货物运 输服务。在运输过程中，有多种可能的路线可以选择 ，每条路线都有不同的运输成本和时间。此外，客户 对货物的运输时间和成本也有一定的要求。
整数规划应用
该案例可以通过整数规划来解决。首先，将每条路线的 选择定义为整数决策变量，1表示选择该路线，0表示 不选择。然后，根据每条路线的运输成本和时间，构建 目标函数，即最小化总运输成本和时间。接下来，根据 客户的要求和路线的特点，构建约束条件，如运输时间 限制、成本限制和路线连通性等。最后，使用整数规划 求解算法，找到满足所有约束条件的最优路线组合，即 最小化总运输成本和时间的路线选择方案。
展望
未来，整数规划与指派问题将在更多领域得到应用和推广 ，为实际问题的解决提供更加有效的方法和工具。同时， 随着相关技术的不断发展，整数规划与指派问题的求解方 法将更加高效和精确，为相关领域的发展提供更加有力的 支持。
THANKS
感谢观看
要点一
Xpress
Xpress是一款功能强大的数学优化求 解器，适用于线性规划、整数规划等 多种问题。它提供了丰富的算法和工 具，支持大规模问题的求解和分析。
要点二
LINGO
LINGO是一款易于使用的数学优化建 模工具，具有直观的语法和丰富的函 数库。它可以帮助用户快速构建和求 解线性规划、整数规划等问题，并提 供详细的解决方案和报告。
原理
通过添加割平面约束条件，逐 步缩小问题的可行域，从而找 到整数最优解。
添加割平面
根据松弛问题的最优解，构造 一个割平面约束条件，添加到 原问题中。
迭代
重复添加割平面和求解新问题 的步骤，直到找到整数最优解 或确定无整数最优解为止。

管理运筹学-03- 整数规划

管理运筹学-03- 整数规划
Integer Programming
第3章 整数规划
IP
第3章 整数规划
3.1 整数规划问题及其建模 3.2 分支定界法 3.3 割平面法 3.4 0-1型整数线性规划的解法 3.5 指派问题 .6 整数规划应用
第3章 整数规划
2
基本概念
整数规划：变量取整数的线性规划； 纯整数规划：所有变量都取整数的线性规划； 混合整数规划：部分变量取整数的线性规划； 0-1规划：所有变量都取0、1两个值的规划； 0-1混合规划：部分变量取0、1两个值的规划。
x3 6 ④
x 1 , x 2 , x 3 0 或 1
可行解：X=(1，0，0)，Z=3
增加过滤条件（filtering constraint）
3x12x25x33◎
第3章 整数规划
20
3.4 0-1型整数规划的解法
第3章 整数规划
21
改进算法（更早发现最优解）
按价值系数从小到大排列
max z=-2x2+3x1+5x3
当xj 0 当xj 0
设第j种设备运行每小时可以生产第i种产品a ij 件，而第i种产品 定货为 b i 件。要满足定货同时使设备运行的总成本最小的问题
为： n min z (d j y j c j x j )
j1
n
s.t.
aij x j bi
i 1,2, , m
j1
x j Myj
j 1,2, , n
x1≥6
x1 x2
6 5 7
z 14 13 7
z 13 1 2
图3-3. 探索过程示意图
x2≤0
√ Sub-9
x1 7 x2 0 z 14 z z 14

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第6章 整数规划

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第6章 整数规划

解为：
表 6-1 问题 B1 z1 = 349 x1 = 4.00 x2 = 2.10
问题 B2 z2 = 341 x1 = 5.00 x2 = 1.57
显然没有得到全部变量是整数的解。现存在两个打开节点 B1 和 B2，因 z1 > z2 ，故将 z 改 为 349，那么必存在最优整数解，得到 z* ，并且
3．定界与剪枝：通过不断的分枝和求解各个子问题，分枝定界法不断修正其上下界的 过程称为定界。上界通常由各打开节点中最大的目标函数值确定，下界则由已经找到的最好 的整数解来确定。求解任何一个子问题都有以下三种可能的结果。
(1)子问题无可行解。此时无需继续向下分枝，该节点因不可行而被关闭。因为与父节 点相比，子节点是一个约束得更紧得的问题（比父节点多一个约束）。如果父节点不可行，
z3 = z = z* = 340 问题 B3 得解 x1 = 4.00 ， x2 = 2.00 为最优整数解。
问题 B
x1=4.81 x2=1.82 z0=356
z=0, z=356
x1 4
问题 B1
明显减少搜索的计算量。所有节点的被关闭表明搜索已经完成。如果此时没有找到任何整数
解，则该问题没有整数解；否则搜索过程中得到的最好的整数解就是该问题的最优解。
6.2.2 分枝定界算法
下面结合一具体例子来说明分枝定界法是如何工作的。
例 2 求解 A
max z = 40x1 + 90x2
①
⎧⎪⎪⎨⎪79xx11x++1,27x02xx2≥2≤0≤5760
0 ≤ z* ≤ 349 继续对问题 B1 和 B2 进行分解，因 z1 > z2 ，故先分解 B1 为两支。增加条件 x2 ≤ 2 者，称为问 题 B3 ；增加条件 x2 ≥ 3 者称为问题 B4 。在图 1-4 中再舍去 x2 > 2 与 x3 < 3 之间的可行域，再 进行第二次迭代。解题过程的结果都列在图 1-5 中。可见问题 B3 的解已都是整数，它的目 标函数值 z3 = 340 ，可取为 z ，而它大于 z4 = 327 。所以再分解 B4 已无必要。而问题 B2 的 z2 = 341，所以 z* 可能在 340 ≤ z* ≤ 341 之间有整数解。于是对 B2 分解，得问题 B5 ，既非整 数解，且 z5 = 308 < z3 ，问题 B6 为无可行解。于是可以断定

管理运筹学 第五章 整数规划

管理运筹学 第五章 整数规划
整数规划问题的松弛问题
j 1
整数规划的类型

纯整数规划：变量全部是整数 混合整数规划：变量部分整数，部分非整数 0-1型整数规划：变量= 0或1
x2
3 2
2x1+3x2 =14.66
1
x1
2x1+3x2 =14
1
2
3 2x1+3x2 =6
4
整数规划对应松弛问题最优解为：
x1=2.44, x2=3.26,目标函数值为14.66。
如果A2和A3两地必 须有且只有一个建 厂，怎么办？
1、整数规划数学模型的一般形式
n
max(min) z c jx j n a ijx j ( , )b i (i 1,2, , m ) j 1 st. x j 0( j 1,2, , n ) xj部分或全部取整数


负数所在列加上一个常数，继续循环。

直到系数矩阵中没有负数，而且整个消耗系数矩阵的所有元素总和已经变小；此 时调整结束，重新回到step2。
步骤1：行减、列减
15 19 C 26 19
21 24 23 22 18 17 16 19 21 23 17 17

例5.6 有三种资源被用于生产三种产品，资源量、产品单件可变费用 及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制 定一个生产计划，使总收益最大。
5.3.2 0-1ILP的隐枚举法
解 为提高搜索效率，减少运算量，先按照目标函数中各变量系数的大小顺 序重新排列各变量。 对于求极大值问题，按照从小到大排为x3,x2,x1。（注意： 对于求极小值问题，应从大到小排序）

《管理运筹学》演示(图论)

《管理运筹学》演示(图论)

v3 (v2 ,1)
检查 vs 相邻点 v1 和 v2 。 v2点，fs2 = cs2 =3，不满足标号条件；v1点，fs1 < cs1 , v1点标号为（ vs , l(v1) ）, l(v1) =min[ l(vs) ,( cs1 - fs1 )]= min[+ , 5-1] = 4； 检查 v1 相邻点 v3 和 v2 。 v3点，f13 = c13 =2，不满足标号条件； v2点，f21=1> 0 , v2点标号为（ -v1 , l(v2) ）, l(v2) =min[ l(v1) , f21]= min[4 , 1] = 1； 检查 v2 相邻点 v3 和 v4 。v3点，f32=1> 0 , v3点标号为（ -v2 , l(v3) ）, l(v3) =min[ l(v2) , f32]= min[1 , 1]=1 ； v4点，f24 < c24 =1，v4点标号为（ v2 , 1 ） ；
,
最大流量 v(f ) = 5
最小费用最大流问题
例：求下列网络最小费用最大流。弧旁数字为( bij , cij ) 步骤：
v1
(1,7)
vt
取 f ( 0 ) ＝0为初始可行流； 构造赋权有向图w( f ( 0 ))，
vs
解：
v1
0 0
v2
0
0
v3
vt
0
bij wij bij wij
v8
步 骤：
给 vs点以 P 标号，P(vs) = 0，其余各点给 T 标号，
T(vs) = ＋ ；
若 vs点为刚得到 P 标号的点，考虑这样的点 vj：
( vi , vj )属于A(或[vi , vj ] 属于E )，且vj 为 T 标号。对 vj 的T 标号进行如下的更改：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

? ?
1 1
? ?
y4
?
1
??x1, x2, x3, x4 ? 0, yj ? 0 , j ? 1,2,3,4
用QM软件求解结果如下：
最优方案 :装配线A生产100件,装配线 B生产1400件,装配线 C 生产1000件,装配线D生产1500件;
例3.(固定成本问题)高压容器公司制造小、中、大三种尺寸的金属 容器，所用资源为金属板、劳动力和机器设备，制造一个容器所 需所需的各种资源的数量如下表：
?8x1 ? 15x2 ? 6x3 ? 3x4 ? 160 ??30x1 ? 40x2 ? 20x3 ? x4 ? 200
???8x1x1??315x2 ? 100
? ?
x2
?
2
?5 ? ?5
? ?
x3 x4
? 10 ? 10
?? xj ? 0 , j ? 1,2,3,4 , 整数
用QM软件求解结果如下：
使用计算机软件包求解(附件1)
A Linear Programming
1 2 3 4 5 6 7 8 9 10 11 J CPM/PERT
B Integer Programming
1234567
K Inventory Models
C Zero One Programming
1234567
L Queueing Theory
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。
该广告计划模型为：
max z ? 40x1 ? 90x2 ? 50x3 ? 2x4
解：设小号容器、中号容器和大号容器的生产产量分别为x1、x2、 x3；对各种容器的固定费用可引入0－1变量 y1、y2、y3，即：
当生产第 i 种 容 器，
yi
当不生产第 i 种 容 器；
约束条件: ?三种资源金属板、劳动力和机器设备的限制条件；
? 为了避免出现某种容器不投入固定费用就生产这 样一种不合理的情况，必须加上以下约束条件：
x1 ? y1M x2 ? y2 M x3 ? y3 M
目标函数： 为扣除固定费用的利润最大化，即：
4x1 ? 5x2 ? 6x3 ? 100y1 ? 150y2 ? 200y3
该生产计划整数规划模型为：
max z ? 4x1 ? 5x2 ? 6x3 ? 100 y1 ? 150 y2 ? 200 y3
minz ? 100y1 ? 200y2 ? 300y3 ? 200y4 ? 10x1 ? 4x2 ? 2x3 ? 5x4
?x1 ? x2 ? x3 ? x4 ? 4000 ??x1 ? 800y1
???xx32
? ?
1400y2 1000y3
????xy14
? ?
1500y4 1
? ?
y2
? y3
P Markov Analysis
H Decision Theory
Q Game Theory
I Network Models
ESC Exit to Dos
123
总目录
例1.(投资问题 )某厂要制订一个产品宣传计划，可利用的广告渠 道有三种：电视、广播、杂志。市场调研的结果如下表所示。该 厂计划用于广告费用不超过 16万元。此外还要求：（ 1）受到广 告影响的妇女至少要有200千人；（2）电视广告费用不超过10万 元；（3）白昼电视至少要订 3个广告，热门时间至少 2个广告； （4）广播和杂志上的广告数都应在5到10之间。该厂如何制订一 个广告计划使受到影响的总人数最多。
开工费
100 200 300 200
每件产品成本
10 4 2 5
最大生产能力（件）
800 1400 1000 1500
解：有两类决策变量，一类，设 xi 为第 i 条装配线上生产的 产品，i = 1,2,3,4;另一类，引入0－1变量，设 yj =1表示第 j 条装配线启用， yj =0表示第 j 条装配线不启用。
例4.(生产计划问题)某汽车厂生产三种汽车：微型轿车、中级轿车 和高级轿车。每种轿车需要的资源和销售利润如下表：
钢材（吨） 人工（小时） 利润（万元）
微型车 1.5 30 2
中级车 2 40 3
高级车 2.5 50 4
该厂每月可使用的资源为钢材6000吨，人工工时55000小时。为达 到经济规模，每种汽车的月产量必须达到一定的数量时才可以进 行生产。工厂规定的经济规模为：微型车1500辆，中级车1200辆， 高级车1000辆。请构造一个整数规划使该厂的利润最大。
资源 金属板（ 吨）
劳动力（ 人月） 机器设备（ 台月）
小号容器
2 2 1
中号容器
4 3 2
大号容器
8 4 3
不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5
万元、6万元，可使用的金属板有500吨，劳动力有300人月，机器 有100台月，此外，不管每种容器制造的数量是多少，都要支付一
笔固定的费用：小号是100万元，中号为150万元，大号为200万元。 现在要制订一个生产计划，使获得利润为最大？
最优方案:电视白昼时间的广告个数为 3、电视热门时间的广告个 数为 5、广播的广告个数为 10、杂志的广告个数为10。
例2.（生产计划问题）某该厂有4条装配线可以生产同一种 产品，已知每条装配线的开工费，生产1件生产的成本以及 最大生产能力如表所示。该厂已接受订货4000件，应如何 安排生产？
装配线A 装配线B 装配线C 装配线D
?2x1 ? 4x2 ? 8x3 ? 500 ??2x1 ? 3x2 ? 4x3 ? 300
? ? ?
x1 x1
? ?
2x2 ? 3x3 My1 ? 0
?100? ?Fra bibliotekx2?
My2
?
0
?x3 ? My3 ? 0
? ?
x1
,
x2
,
x3
?
0,
y1,
y2 ,
y3
＝0
或
1
用QM软件包求解如下：
最优方案：小号容器生产100台，中号和大号容器不生产，最大利 润为300万元。
D Goal Programming
12345678
M Dynamic Programming
E Transportation Programming
1 2 3 4 5 6 7 N Simulation
F Assignment
123456
8 9 10 11 12 O Forecasting
G Break-Even Analysis

相关主题