第五节 线性整数规划整数规划 —— 变量只能取整数的规划问题。
当变量只能取 0或 1两个值，
称 0-1规划。
整数规划分类：
纯整数规划 —— 全部变量为整数。
混合整数规划 —— 部分变量为整数。
本节主要介绍 0-1规划的模型建立。
例 13 投资场所选址问题计划在东、西、南三个区开设若干商业网点，拟在
A1,…,A7 7个地点中选择。规定：东区在 A1,A2,A3中至多选 2个，西区在 A4,A5中至少选 1个，南区在 A6,A7中至少选 1个。已知在 Ai建点需投资 bi，可获利 ci，现共有资金为 B。问应如何布局可使总利润最大？
分析：
xbxcA
A
A
x
AAxx
需投资为的利润为则不选选中即的选择变量分别表示地址决策变量
,
0
1
,,,,,
7171




变量是则模型为不选选中解：设
10,,
1
1
2
xx
xx
xx
xxx
Bxb
xcM a xz
A
A
x
0
1
东区在 A1,A2，
A3中至多选 2个怎样表示？
2 xxx
例 14 固定费用问题某工厂为生产某种产品，有 3种不同的生产方式可供选择。设第 j种生产方式的固定成本为 kj，
可变成本为 cj 。若不考虑其他约束，请建立使总成本最小的规划模型。

0 0
0
,
x
xxck
j
xj
种方式时的成本为则使用第种生产方式时的产量为设采用第分析：

0,0
0,,1
种生产方式时即不采用第，
种生产方式时即采用第若设
jx
j xy
)()()( xcykxcykxcykz则总费用

10
0
或初步建立模型为
y
x
xcykxcykxcykM i n z )()()(
333322221111
怎样解决？时必有问题：不能保证当 1,0 yx
的上界。则最后模型为为—加约束— xMyMx,?

10
0
)()()(
333322221111
或y
yMx
x
xcykxcykxcykM i n z