变量取整数的规划称为整数规划.所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划.在线性规划问题中，如果所有的变量都只能取值0或1.这样的线性规划问题称为（纯）0—1整数规划问题.如果一个线性规划问题中，有的变量是连续变量，而另一些变量是0—1变量，这样的问题称为混合0—1规划问题.
1. 背包问题
例4一只背包最大装载重量为50公斤.现有三种物品，每种物品数量无限.每种物品每件的重量、价值如下表所示：
表54
物品1物品2物品3
重量（公斤/件）104120
价值（元/件）177235
要在背包中装入这三种物品各多少件，使背包中的物品价值最高.
设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：
maxz=17x1+72x2+35x3〖1〗
s.t.10x1+41x2+20x3≤50
x1,x2,x3≥0,x1,x2,x3是整数
这个问题的最优解是：x1=1件,x2=0件,x3=2件,最高价值为：z=87元.
例5一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等.每种物品的重量和重要性系数如表所示.设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品.
表55
序号1234567
物品食品氧气冰镐绳索帐篷照相器材通信设备
重量/kg55261224
重要性系数201518148410
解：引入0—1变量xi,xi=1表示应携带物品i，xi=0表示不应携带物品I，i=1,2,…,7
maxz=20x1+15x2+18x3+14x4+8x5+4x6+10x7
5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25
xi=0或1,i=1,2,…,7
比较每种物品的重要性系数和重量的比值，比值大的物品首先选取，直到达到重量限制，上述问题就是一个标准的整数规划问题，由分枝定界法，解得：X=（x1，x2，x3，x4，x5，x6，x7）=（1,1,1,1,0,1,1），Z=81
一般地，有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限.第i种物品每件重量为wi公斤，价值为vi元.每种物品各取多少件装入背包，使其中物品的总价值最高.
设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为
maxz=v1x1+v2x2+…+vkxk〖1〗
s.t.w1x1+w2x2+…+wkxk≤W〖1〗
x1,x2,…xk≥0〖1〗
x1,x2,…xk为整数
例6集合覆盖和布点问题
某市消防队布点问题.该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场.据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划.
表56
地区1地区2地区3地区4地区5地区6
地区1
地区2
地区3
地区4
地区5
地区60
10
16
28
27
2010
0
24
32
17
1016
24
0
12
27
2128
32
12
0
15
2527
17
27
15
0
1420
10
21
25
14
0
解：引入0—1变量xi,xi=1表示在该区设消防站，xi=0表示不设
minz=x1+x2+x3+x4+x5+x6
x1+x2≥1
x1+x2+x6≥1
x3+x4≥1
x3+x4+x5≥1
x4+x5+x6≥1
x2+x5+x6≥1
xi=1或0
解得：X=（x1，x2，x3，x4，x5，x6）=（0,1,0,1,0,0），Z=2
2. 厂址选择问题
在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，…，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨.现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大.
设xi=0表示在i地不建厂
1表示在i地建厂
整数规划模型为
maxz=∑Ni=1Pixi
s.t.∑Ni=1Iixi≤I
∑Ni=1Lixi≤L
∑Ni=1xi≤r
xi=0,1
这是一个0—1规划问题.
3. 考虑固定成本的最小生产费用问题
在最小成本问题中，设第j种设备运行的固定成本为dj，运行的变动成本为cj，则生产成本与设备运行时间的关系为
fj（xj）=0当xj=0
dj+cjxj当xj0
设第j种设备运行每小时可以生产第i种产品aij件，而第i种产品的定货为bi件.要满足定货同时使设备运行的总成本最小的问题为
minz=∑nj=1djyj+cjxj
s.t.∑nj=1aijxj≥bii=1,2,…,m
xj≤Myjj=1,2,…,n
xj≥0,yj=0,1
这里M是一个很大的正数.
当yj=0时，xj=0，即第j种设备不运行，相应的运行成本
djyj+cjxj=0
当yj0时，0≤xj≤M，实际上对xj没有限制，这时相应的运行成本为
dj+cjxj
这是一个混合0—1规划问题
4. 指派问题
例7有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务.由第i个人去做第j项任务的成本（或效益）为cij.求使总成本最小（或效益最大）的分配方案.
设：xij=0第i个人不从事第j项任务
1第i个人被指派完成第j项任务
得到以下的线性规划模型：
min（max）z=∑ni=1∑nj=1cijxij
s.t.∑ni=1xij=1j=1,2,…,n
∑nj=1xij=1i=1,2,…,n
xij=0,1
例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教.根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：
表57
语文数学物理化学
张92688576
王82917763
李83907465
赵93618375
四位教师每人只能教一门课，每一门课只能由一个教师来教.要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高.
设xij（i=1,2,3,4；j=1,2,3,4）为第i个教师是否教第j门课，xij只能取值0或1，其意义如下：
xij=0第i个教师不教第j门课
1第i个教师教第j门课
变量xij与教师i以及课程j的关系如下：
表58
j
i语文数学物理化学
张x11x12x13x14
王x21x22x23x24
李x31x32x33x34
赵x41x42x43x44
这个指派问题的线性规划模型为：
maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24
+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44
s.t.x11+x12+x13+x14=1（1）
x21+x22+x23+x24=1（2）
x31+x32+x33+x34=1（3）
x41+x42+x43+x44=1（4）
x11+x21+x31+x41=1（5）
x12+x22+x32+x42=1（6）
x13+x23+x33+x43=1（7）
x14+x24+x34+x44=1（8）
xij=0,1
这个问题的最优解为x14=1，x23=1，x32=1，x41=1，maxz=336；即张老师教化学，王老师教物理，李老师教数学，赵老师教语文，如果这样分配教学任务，四门课的平均总分可以达到336分.
例8有4种机械要分别装在4个工地，它们在4个工地的工作效率不同，问应如何指派安排，才能使4台机械发挥总的效率最大？效率表如下：
表59
工地
机器甲乙丙丁
Ⅰ
Ⅱ
Ⅲ
Ⅳ30
32
35
2825
35
40
4340
30
34
3232
36
27
38
由表知：maxcij=c42=43
所以bij=43-cij
B=1318311
118137
83916
150115行变换
101508
4160
50613
150115列变换
61508
0160
10613
110115
61508
0160
10613
110115
圈0打勾覆盖增0
61608
0260
00512
100104，得
0
0
0
0，0010
0001
1000
0100
令x13=x24=x31=x42=1，其余取0，得到最佳指派方案.