0-1整数规划模型ppt课件

Z≥0
√√ √ √
Z≥5
枚举法：
（1 0 1） 1
检验可行解： 32次运算
（1 1 0） 8 （0 1 1） 3 （1 1 1） 6
× √√ √ √
计算目标 函数值：8次
最优解：x1 1，x2 1，x3 1
最优值Z 6
3
二、指派问题
例 有一份说明书，需译成
英、日、德、俄四种文字。
任务
现有甲、乙、丙、丁四个人， 人员
i=1,2, …,6
Z表示全区消防站总数
s.t
x1 x2 1 x1 x2 x6 1
x3 x4 1
x3 x4 x5 1 x2 x5 x6 1 2
xi 0,1 i 1,2, ,6
二、过滤隐枚举法 （适合于变量个数较少的0-1规划）
例：求max Z 3x1 5x2 2x3
一、决策问题与0-1变量
决策变量xi 是否做第i件事 i 1,2, , n
1 做第i件事
xi
0 不做第i件事 n件事中必须做k件并只做k件事 x1 x2 xn k n件事中最多做k件事 x1 x2 xn k
n件事中至少做k件事 x1 x2 xn k 做第i件事的充要条件是做第j件事 xi x j 做第i件事的充要条件是不做第j件事 xi 1 x j 只在做了第i件事前提下才考虑是否做第j件事 x j xi1
钟内赶到x现2=场1,。x4据=1实地测定，
各区之间消防车行驶的时间见
5 6
27 17 27 15 0 14 20 10 21 25 14 0
右表。 请为该市制定一个 布点问题模型：
最节省的最计优划值
min Z x1 x2 x3 x4 x5 x6
解：xi
1Z=2在第i个地区建站
0
不在第i个地区建站
“0”画○，划去与◎同列的其它“0”； (2)给只有一个0元素（不含划去的0）的列中的
“0”画○，划去与◎同行的其它“0”； (3)重复(1)、(2)，直到无新的◎画出。若系数
矩阵中已无未画○也未划去的“0”，则已得到最多 的◎，转(5)；否则，便出现了0元素的闭回路，转 (4)。
(4)从0元素的闭回路上任选一个“0”画○，划去 其同行同列的其它“0”，转(1)。
xij＝ 0 不指派第i人去完成第j项任务
来自百度文库
4
数学模型为 Min z＝∑∑cijxij
n
∑i=1xij＝1 j=1,2,…,n
n
∑xij＝1 i=1,2,…,n
j=1
xij＝0或1
可见指派问题是0-1 型整数规划的特例。不 难发现，指派问题也是 运输问题的特例，其产 地和销地数都为n，各 产地的产量和各销地的 销量都为1。
他们将说明书译成不同文字
甲
所需的时间如下表。问应指
乙
派哪个人完成哪项工作，使
丙
所需的总时间最少？
丁
EJGR
2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9
一般地，有n项任务、n个完成人，第i人完成第j
项任务的代价为cij（i,j＝1,2,…,n）。为了求得总
代价最小的指派方案，引入0-1型变量xij，并令 1 指派第i人去完成第j项任务
i1
x
i
j
取0或1(i
,
j
1.2.
.n)
9
❖克尼格定理 : ❖ 如果从分配问题效率矩阵[aij]的每一行元 素中分别减去(或加上)一个常数ui，从每一列 中分别减去(或加上)一个常数vj，得到一个新 的效率矩阵[bij]，则以[bij]为效率矩阵的分配 问题与以[aij]为效率矩阵的分配问题具有相同 的最优解。
例1（布点问题）某城市共有6个 地 1 2 3 4 5 6
区，每个区都可以建消防站。 区
市政府希望设置的消防站最少，1 0 10 16 28 27 20
2 10 0 24 32 17 10
但必须满足在城市任何地区发
生火火警时最，优消解防车要在15分
3 4
16 24 0 12 27 21 28 32 12 0 15 25
第四步：变换系数矩阵，增加0元素。在未被画线 覆盖的其它元素中找出最小元素，各打“√”行减 去最小元素，各打“√”列加上最小元素，转第二 步。
8
❖ 指派问题的数学模型为：
nn
minZ
c x ij ij
i 1 j1
n
xij 1
(i 1.2. .n)
j1
n
xij 1
( j 1.2. .n)
10
❖ 指派问题的求解步骤：
1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列 中都出现0元素，即
从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。
2) 进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元
例如： （cij）=
0420
2078 3150 0603
匈牙利法求解指派问题的步骤如下：
6
第一步：变换系数矩阵，使每行每列都出现0元素。 (1)系数矩阵的各行分别减去各行中的最小元素；(2) 所得系数矩阵的各列再分别减去各列中的最小元素。
第二步：试求最优解。 (1)给只有一个0元素（不含划去的0）的行中的
x1 2x2 x3 2
s.t
x1 4x2 x1 x2
x3
42 3
（x1 x2 x3) Z值
（0 0 0） 0
4x2 x3 6
x1, x2, x3 0或1
（0 0 1） -2 （0 1 0） 5
（1 0 0） 3
运算次数： 21
约束条件
过滤条件
（1）（2）（3）（4）
√√ √ √
(5)显然，按上述步骤得到的◎是位于不同行不 7 同列的。若◎已达n个，则指派问题的最优解已得到，
第三步：用最少的直线覆盖所有0元素。 (1)给无◎的行打“√”； (2)给打√行中含有0元素的列打“√”； (3)给打√列中含有◎元素的行打“√”； (4)重复(2)、(3)，直到无新的“√”打出。 (5)给没有打√的行画横线，给打√的列画纵线。
指派问题的求解，最简便易行的方法是匈牙利法。
匈牙利法基于下面的效率矩阵：
（cij）=
c11 c12 … c1n c21 c22 … c2n
………………. 5 cn1 cn2 … cnn
匈牙利法基于这样一个明显的事实：如果系 数矩阵的所有元素满足cij≥0，而其中有n个位 于不同行不同列的一组0元素，则只要令对应 于这些0元素位置的xij＝1，其余的xij＝0，就 得到最优解。