运筹学PPT 第四章 线性整数规划

1 7 1 7
1 选中A 即x 0 不选A
则A 的利润为c x , 需投资为b x
东区在A1，A2， A3中至多选2个
怎样表示？
1 选中A 解：设x 0 不选A 则模型为 Maxz c x

x x x 2
b x B x x x 2 x x 1 x x 1 x ,, x 是0 1变量
1 1 1 1 2 2 2 2 3 3 3 3
x 0 x M y y 0或1
[例]
人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所需司机和乘 务人员数如下： 班次 1 2 3 4 5 时间 6：00 —— 10：00 10：00 —— 14：00 14：00 —— 18：00 18：00 —— 22：00 22：00 —— 2：00 所需人数 60 70 60 50 20
xi=0或 1，i=1, … ,4
课堂练习: 某市为方便学生上学，拟在新建的居民小区增设 若干所小学。已知备选校址代号及其能覆盖的居民 小区编号如表所示，问为覆盖所有小区至少应建多 少所小学？
备选校址代号
A B C D E F
覆盖的居民小区编号
1、5、7 1、2、5 1、3、5 2、4、5 3、6 4、6
例13 投资场所选址问题
计划在东、西、南三个区开设若干商业网点，拟在 A1，…，A7 7个地点中选择。规定：东区在A1，A2，A3中
至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中
至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资 金为B。问应如何布局可使总利润最大？ 分析：
决策变量x , , x 分别表示地址A , , A 的选择变量,
课堂练习2: 某篮球队有8名队员，其身高和专长如下表，现要选 拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？
队员 身高 专长 1 1.92 中锋 2 1.90 中锋 3 1.88 前锋 4 1.86 前锋 5 1.85 前锋 6 1.83 后卫 7 1.80 后卫 8 1.78 后卫
E 2 10 9 7 J 15 4 14 8 G 13 14 16 11 R 4 15 13 9
甲 乙 丙 丁
解：令
xij= min

1， 指派第i人去完成第j项任务
0， 不指派第i人去完成第j项任务 z=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24
第四章 线性整数规划
整数规划——变量只能取整数的规划问题。 当变量只能取0或1两个值， 称0-1规划。
整数规划的分类：
纯整数规划：所有变量都限制为整数


混合整数规划：仅部分变量限制为整数
0-1整数规划：变量的取值仅限于0或1
整数规划的解法：分枝定界法或割平面法
基本思想是把一个整数规划问题化为一 系列的线性规划问题来求解
1. 投资场所的选址问题
某城市拟在东、西、南三区设立商业网点，备选位置有 A1~A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要 求总投资不超过B元，规定 东区：A1、A2、A3中至多选2个 西区：A4、A5中至少选一个 南区：A6、A7中至少选一个 问如何设点使总利润最大？
max z= ci xi
x2 + x 3
x3 + x 4 x4 + x 5
≥ 60
≥ 50 ≥ 20
x5 + x 6
≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0且为整数
最优解：X* =(60 ，10，50 ，0 ，30 ，0）， Z*=150
二、

0-1整数规划
投资场所的选址问题 指派问题 背包问题 消防队问题
s.t.
x
i 1
8
i
5
x1 x2 1
x6 x7 x8 1
x6 x2
xi 0 或 1，i=1, … ,8
2. 指派问题 问题描述：n项任务可由n个人完成，由于专长不同，各人 完成各任务的时间也不同，求最优安排。 要求：每人只能完成一项任务，每项任务只能由一人完成。 例： 有一份中文说明书，需译成英、日、德、俄四种文字， 分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们 将中文说明书翻译成不同语种说明书所需的时间如下表所示， 问应指派何人去完成何项任务，使所需总时间最少？
解：模型为：
Max Z 7 x1 5 x2 9 x3 6 x4 3 x5
54x1 35x2 57x3 46x4 19x5 115 s.t. x 0 或 1 (i 1,,5) i
4. 消防队问题 某城市的消防总部将全市划分为11个防火区，设有4个 消防救火站。下图①~④表示消防站，1~11表示防火区域， 图中连线表示各地区由哪个消防站负责。问题：可否减少消 防站的数目，仍能同样负责各地区的防火任务？如果可以， 应关闭哪个消防站？ 2
运动员 甲 乙
丙 丁
仰泳 75.5 65.8
67.6 74.0
蛙泳 86.8 66.2
84.3 69.4
蝶泳 66.6 57.0
77.8 60.8
自由泳 58.4 52.8
59.1 57.0
3. 背包问题 问题描述 已知：一个背包最大容量为b公斤；有m件物品供选择，每 件物品重ai公斤，价值为ci（i=1,…,m）。 问题：携带哪些物品可使总价值最大？ 一般模型 xi=

1， 物品i被选中 0，物品i没被选中
m
Max z ci xi
ai xi b s.t. i 1 xi 0 或 1

m
i 1
例：一个徒步旅行者要在背包中选择一些最有价值的物品携 带。他最多能带115kg的物品，现有5件物品，分别重54、35、 57、46、19kg，其价值依次为7、5、9、6、3。问携带哪些 物品可使总价值最大？
1, x 0,即采用第j 种生产方式时 0， x 0,即不采用第j 种生产方式时
则总费用z ( k y c x ) ( k y c x ) ( k y c x )
初步建立模型为 Minz ( k y c x ) ( k y c x ) ( k y c x )
解：令 x i=

1， Si被选中
min z=
10
c x
i 1
10
i i
0， Si没被选中
s.t.
x x 1 xx xx 11 x x 1 x x x x 2 x 0
i 1 i
x
1 7
5
8
8
3
5
4
5
5
6
7
8
i
或 1，i=1, … ,10
（2）选择了S3或S4就不能选择S5，反 过来也一样;
（3）在S5，S6 ，S7，S8中最多只能选 两个。 问如何选择井位使总费用最小？
课堂练习1: 某钻井队要从S1~S10共10个井位中确定五个钻井探油，
如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 （2）选择了S3或S4就不能选择S5，反过来也一样 （3）在S5，S6 ，S7，S8中最多只能选两个 问如何选择井位使总费用最小？
解：令 x i=

7
1， Ai被选中
i 1Biblioteka 0， Ai没被选中 ∑ bixi≤B i=1 x1+x2+x3≤2 s.t. x4+x5≥1 x6+x7≥1 x =0或 1，i=1, … ,7
i
7
课堂练习1:
某钻井队要从S1~S10共10个井位中确定五个钻 井探油，如果选Si，估计钻探费用为ci元，并且 井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 ;
1 8 2 9
1
3 6 5
7
4
10
4
3
11
解：令 x i=

1， 保留第i个消防队 0， 撤消第i个消防队
则模型为
min z= x1+x2+x3+x4

x1+x2 ≥1 x1+x2 ≥1 x1 ≥1 x1 +x3 ≥1 x3 ≥1 x1 +x3+x4≥1 x1 +x4≥1 x1+x2 +x4≥1 x1 +x4≥1 x4≥1 x3+x4≥1
x14+ x24+ x34+ x44= 1 ( R任务只能一人干)
xij = 0 或 1，i,j = 1,2,3,4
课堂练习:P57例2.23
例：甲、乙、丙、丁是四名游泳运动员，他们各种 姿势的100m游泳成绩如表。为组成一个4×100m 混合泳接力队，怎样选派运动员，方使接力队的游 泳成绩最好？
某篮球队有8名队员，其身高和专长如下表，现要选 拔5名球员上场参赛，要求： （1）中锋只有1人上场 （2）后卫至少有一人上场 （3）只有2号上场，6号才上场 要求平均身高最高，应如何选拔队员？
解：令 x i=

1， 队员i被选中 0，队员i没被选中
1 8 max z= ci xi 5 i 1
1 1 1 1 2 2 2 2 3 3 3 3
x 0 y 0或1
问题：不能保证当 0时必有y 1,怎样解决？ x
— —加约束 x M y , M 为x 的上界。则最后模型为