5.4 0-1 整数规划.ppt

第四节 0-1型整数规划
0-1 0-1 整数规划
本节内容的安排
引入0-1变量的实际问题
0-1型整数规划的解法
0-1 0-1 整数规划
如果线性规划中的所有决策变量的取值只能取
0、1,
则这类线性规划问题是一种特殊的整数规划问题
称之为0-1规划,把只能取0或1值的变量称为0-1变量。
0-1变量是一种逻辑变量。
在某些特殊的实际问题中,我们只需做是非选择,
如:是否采纳某方案,某任务是否可交给某人承担,
集装箱是否装入某货物等,
对于这类问题的变量可设置简化为0或1,
x=
1 是
0 否
0-1 0-1 整数规划
决策变量只取0和1的线性规划问题, 其数学模型如下:
其中xj为0-1变量,也称二进制变量,逻辑变量。
xj仅取值0或1这个条件可由下述约束条件所代替。
xj≤1, xj≥0,整数
它和一般整数线性规划的约束条件形式是一致的。
0-1 0-1 整数规划
作用:
在实际问题中,如果引入0-1变量,
就可以把有各种情况需要分别讨论的
线性规划问题统一在一个问题中讨论了。
在本节我们先介绍引入0-1变量的实际问题:
①投资场所(项目)的选定
②相互排斥的约束条件
③关于固定费用的问题
然后,再研究0-1规划问题的一般解法---隐枚举法。
0-1 0-1 整数规划
-1变量的实际问题
1. 投资场所的选定——相互排斥的计划
例4 : 某公司拟在市东、西、南三区建立门市部。
拟议中有7个位置(点)Ai (i=1,2,…,7)可供选择。
规定:
在东区,由A1,A2,A3三个点中至多选两个;
在西区,由A4,A5两个点中至少选一个;
在南区,由A6,A7两个点中至少选一个。
如选用Ai点,设备投资估计为bi元,
每年可获利润估计为ci元,
但投资总额不能超过B元。
问应选择哪几个点可使年利润为最大?
0-1 0-1 整数规划
解题时先引入0-1变量xi (=1,2,…,7)
于是问题可列成:
在东区,由A1,A2,A3三个点中至多选两个;
在西区,由A4,A5两个点中至少选一个;
在南区,由A6,A7两个点中至少选一个。
0-1 0-1 整数规划
2. 相互排斥的约束条件
在本章开始的例1 (P114)中,关于运货的体积限制为
5x1+4x2≤24 (5-9)
今设运货有车运和船运两种方式,
上面的条件系用车运时的限制条件,
如用船运时关于体积的限制条件为
7x1+3x2≤45 (5-10)
这两条件是互相排斥的。
为了统一在一个问题中,引入0-1变量y,令
(1)两个约束条件中只有一个起作用
车运
船运
0-1 0-1 整数规划
于是(5-9)式和(5-10)式可由下述的条件(5-11)式和(5-12)式来代替:5x1+4x2≤24+yM (5-11)7x1+3x2≤45+(1-y)M (5-12)其中M是充分大的数, y是0-1变量。
可以验证,当y=0时,(5-11)式就是(5-9)式,
而(5-12)式自然成立,因而是多余的。
当y=1时,(5-12)式就是(5-10)式,
而(5-11)式是多余的。
引入的变量y不必出现在目标函数内,
即认为在目标函数式内y的系数为0。
5x1+4x2≤24 (5-9 ) 车运
7x1+3x2≤45 (5-10) 船运
0-1 0-1 整数规划
为了保证这m个约束条件只有一个起作用,
引入m个0-1变量yi(i=1,2,…,m)和一个充分大的常数M。
(2)在m个互相排斥的约束条件(≤型):
αi1x1+αi2x2+…+αinxn≤bi,i=1,2,…,m
中只有一个起作用
定义逻辑变量yi :
M为任意大的正数,则有下式成立:
αi1x1+αi