运筹学 17-20-1二章五节线性 整数规划.ppt

文档介绍：第五节线性整数规划
整数规划——变量只能取整数的规划问题。
当变量只能取0或1两个值,
称0-1规划。
整数规划分类:
纯整数规划——全部变量为整数。
混合整数规划——部分变量为整数。
本节主要介绍0-1规划的模型建立。
例13 投资场所选址问题
计划在东、西、南三个区开设若干商业网点,拟在
A1,…,A7 7个地点中选择。规定:东区在A1,A2,A3中
至多选2个,西区在A4,A5中至少选1个,南区在A6,A7中
至少选1个。已知在Ai建点需投资bi,可获利ci,现共有资
金为B。问应如何布局可使总利润最大?
分析:
东区在A1,A2,A3中至多选2个
怎样表示?
课堂练习1:
某钻井队要从S1~S10共10个井位中确定五个钻井探油,如果选Si,估计钻探费用为ci元,并且井位选择上要满足下列条件:
(1)或选择S1和S7,或选择S8 ;
(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中最多只能选两个
问如何选择井位使总费用最小?
1, Si被选中

0, Si没被选中
解:令
xi=
min z=
.
或 1,i=1, …,10
某篮球队有8名队员,其身高和专长如下表,现要选拔5名球员上场参赛,要求:
(1)中锋只有1人上场
(2)后卫至少有一人上场
(3)只有2号上场,6号才上场
要求平均身高最高,应如何选拔队员?
课堂练习2:
1, 队员i被选中

0,队员i没被选中
解:令
xi=
max z=
或 1,i=1, …,8
.
某篮球队有8名队员,其身高和专长如下表,现要选拔5名球员上场参赛,要求:
(1)中锋只有1人上场
(2)后卫至少有一人上场
(3)只有2号上场,6号才上场
要求平均身高最高,应如何选拔队员?
例14. 固定费用问题
最基本的带有固定费用的费用函数一般表示为:
若引入0-1变量
则带有固定费用的费用函数可表示为:
固体废物处理规划例()示意图: