nn xcxcxcz2211m a x
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
线性规划模型：
实际问题要求 xi为整数！
如机器的台数，人数等
整数规划线性整数规划非线性整数规划简称整数规划一、实例例 2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价 50元 /
个，椅子售价 30元 /个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工 4个小时，油漆工 2小时。生产一个椅子需要木工 3个小时，油漆工 1小时。该厂每月可用木工工时为 120小时，油漆工工时为 50小时。问该厂如何组织生产才能使每月的销售收入最大？
每月的销售收入生产椅子的数量生产桌子的数量解：设
Z
xx 21,
21 3050m ax xxZ求
12034
.
21 xx
ts 502 21 xx
0,21?xx
为整数21,xx
纯整数规划例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带 b公斤的东西，
而每件物品都只能整件携带，于是他给每件物品规定了一个
“价值”，以表示其有用程度。如果共有 m件物品，第 i件件物品的重量为 bi,价值为 ci,问题就变成：在携带的物品总重量不超过 b公斤的条件下，携带哪些物品可使总价值最大解：
件物品不带第件物品带第设
i
ix
i 0
1
Z表示所带物品的总价值
件带第 i
icZ?
m
i
ii xc
1
携带物品的总重量
m
i
ii xb
1
数学模型：
m
i
ii xcZ
1
m a x
bxbts
m
i
ii
1
.
mi
x i
,2,1
1,0
,
0-1规划解,的运量运往商店表示工厂设
jiij BAx
则总运费为
个地点建厂不在第个地点建厂在第设
i
iy
i 0
1
则总建厂费为最省？使总建设费和总运输费的需求，又建厂，使得既满足各地。试决定应在哪些地方费为的单位运运往销地。从工厂，，，其销售量分别为品需要销售这种产，，，个地点。又有，，，分别是建设费，，，生产能力分别是它们生产同一种产品，
，，，地点有地点建厂，可供选择的例：某公司计划在几个
ij
jin
nm
mm
c
BAbbb
BBBnfff
aaaA
AA
21
2121
21
21
,
,,
n
j 1
m
i1
ijijxc
m
i
ii yf
1
njbx j
m
i
ij,2,1
1
m
i
i
n
j
ijij
m
i
fxcZ
111
m in
miax
ts
i
n
j
ij,2,1
,1
0?ijx 1,0?iy
数学模型：
混合型整数规划
整数规划纯整数规划
0— 1规划混合型整数规划纯整数规划的数学模型,
nn xcxcxcz2211m a x
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
取整数nxxx,,21?
0--1规划的数学模型,
nn xcxcxcz2211m a x
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
1,0,,21?nxxx?
例
为整数
21
21
21
21
21
,
0,0
92
1432
.
2030m a x
xx
xx
xx
xx
ts
xxz
0,0
92
1432
.
2030m a x
21
21
21
21
xx
xx
xx
ts
xxz对
5.225.3 21 xx,最优解为
33 21 xx,取×
23 21 xx,取
√
√
√
√ Z=130
时，但当 14 21 xx
√
√
√
√
，可行且 Z=140
不可行可行二、整数规划解的理论
为整数对整数规划问题：
j
x
X
bAX
ts
CXz
0.
m a x
0
.
m a x
X
bAX
ts
CXz
（ IP）
（ IP）问题的松弛问题
为整数
）问题：对（
jx
X
bAX
ts
CXz
IP
0.
m a x
0
.
m a x
X
bAX
ts
CXz
其松弛问题为：
的可行解域）（ IP1 松弛问题的可行解域的最优值）（ IP2 ≤
松弛问题的最优值是原整数规划的目标函数值的上界若松弛问题无可行解，
，个整数解若松弛问题可以找到一 X)3(
为整数解）若松弛问题的最优解（ *4 X
的最优解也是则 IPX *
最优值的下界的目标函数值是则 IPX
无可行解则 IP
松弛问题的最优值
