西北农林科技大学运筹学课件第五章整数规划.ppt

第五章整数规划
一、整数规划数学模型及解的特点
二、解纯整数规划的割平面法
三、分支定界法
四、0-1型整数规划
五、指派问题
例1、集装箱运货
货物体积(米3/箱) 重量(百公斤/箱) 利润(千元/箱)
甲 5 2 20
乙 4 5 10
装运限制 24 13
一、数学模型及解的特点
解:设x1 , x2 为甲、乙两货物各托运箱数
5x1+4x2  24
2x1+5x2  13
x1 , x2 0
x1 , x2为整数
maxZ = 20 x1 + 10 x2
纯整数线性规划
一、数学模型及解的特点
例2、背包问题
背包可再装入8单位重量,10单位体积物品
物品名称重量体积价值
1 书 5 2 20
2 摄像机 3 1 30
3 枕头 1 4 10
4 休闲食品 2 3 18
5 衣服 4 5 15
一、数学模型及解的特点
解:xi为是否带第 i 种物品
maxZ=20x1 + 30x2 +10x3+18x4 +15x5
5x1+3x2 +x3 +2x4 +4x5  8
2x1+x2 +4x3 +3x4 +5xX5  10
xi为0, 1
0-1型整数线性规划
一、数学模型及解的特点
例3、选址问题
A1
A3
B2
B4
B3
B1
A2
Ai: 可建仓库地点,容量ai ,投资费用bi ,建2个
Bj: 商店,需求dj ( j=1…4 )
Cij: 仓库 i 到商店 j 的单位运费
问:选择适当地点建仓库,在满足商店需求条件下,总费用最小。
一、数学模型及解的特点
解:设xi ( i=1,2,3)为是否在 Ai 建仓库
yij ( i=1,2,3, j=1…4)由 i仓库向 j商店运货量
混合整数规划
y11 + y21 = d1
y12 + y22 + y32 = d2
y23+ y33 = d3
y14 + y24 + y34 = d4
x1 + x2 + x3= 2
y11 + y12 + y14 a1x1
y21 + y22 + y23 + y24a2x2
y32 + y33 + y34 a3x3
xi 为0-1, yij 0
.
一、数学模型及解的特点
整数规线性划数学模型的一般形式:
,部分或全部为整数
一、数学模型及解的特点
一、数学模型及解的特点
几个概念:
1、整数规划(IP)---要求一部分或全部决策变量必须取整数值的规划问题。
2、松弛问题---不考虑整数条件,由余下的目标函数和约束条件构成的规划问题,称为该整数规划问题的松弛问题。
3、整数线性规划—若松弛问题是一个线性规划,则称该整数规划为整数线性规划。
常用问题:


整数规划的常用解法:


分类 0 – 1 规划
纯整数规划
整数规划…….
混合整数规划
一、数学模型及解的特点