运筹学第四章整数规划与分配问题.ppt

设原整数规划问题为IP，其松弛问题为L0。 用单纯形法求L0，若L0无可行解，则IP也无可 行解，计算停止。若求得L0为整数解，则得IP 的最优解，停止。否则，转下一步； 第二步 分枝与定界
在L0的解中，任选一个不满足整数条件的 变量xi，设xi = bi ，则做两个子问题
整数线性规划的一般形式: n max(或min)z cj xj j 1
n
aij xj ( 或 ）bi (i 1,2,...m)
j 1
xj 0( j 1,2,...n),且部分或全部取整数
例1.求下述整数规划问题的最优解
max z 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5 x1, x2 0,且均取整数值
先不考虑整数解的限制，用单纯形法求 解其松弛问题，如果求得的解恰好是整数解， 则得整数规划最优解，停止计算。否则，将 松弛问题分解为两个子问题（也称后继问 题），每个子问题都是在原松弛问题的基础 上增加一个变量取整数的约束条件，这样就 缩小了原来的可行域，然后用单纯形法求解， 直至得到最终结果。
二、分枝定界法的步骤（最大值问题） 第一步 寻找替代问题并求解
则分配问题的数学模型为
mm
min z
a ij x ij
i1 j1
m
x ij 1 ( i 1 , 2 ,...,
m)
j1
m
x ij 1 ( j 1 , 2 ,...,
m)
i1
x
ij
0或
1，( i ,
j
1 , 2 ,...,
m)
2-2 匈牙利法 定理1.如果从分配问题效率矩阵(aij)的每一 行元素中分别减去（或加上）一个常数ui （称为该行的位势）；从每一列中分别减去 （或加上）一个常数 vj （称为该列的位 势）；得到一个新的效率矩阵bij，其中bij= aij - ui - vj ，则aij的最优解等价于bij的 最优解。
不考虑整数要求时， 最优解为： X=(3.25 ,2.5)T Z=13 （见下页图解法） 考虑整数要求时，最优解为： X=(4 ,1)T Z=14 凑整 （3，2）可行，非最优，Z=13。
（4，3），（4，2），（3，3） 不可行
二、整数规划的分类 1. 全整数线性规划
决策变量全部取整数，约束系数和约束常数项 也取整数的整数线性规划。 2. 纯整数线性规划
设每个人完成不同任务的耗费见下面的 效率矩阵，通常要求aij≥0。
a11 a12 ... a1m
A
aij
mm
a21 ...
a22 ...
...
a2m
... ...
am1 am2 ... amm
又 x ij 设 1 0 ,， 分 不i人 配 分 i人 去 第 配 去 j项 j项 完 第 完 任 任 ( 成 i,j成 务 1 ,2 务 第 ,.第 m .； ).。 ,
决策变量全部取整数，约束系数和约束常数项 可取非整数的整数线性规划。
纯整数线性规划可化为全整数线性规划。 3. 混合整数线性规划
决策变量中有一部分取整数值，另一部分可取 非整数值的整数线性规划。 4. 0-1整数线性规划
决策变量只能取0或1的整数线性规划。
三、0-1变量（或称逻辑变量）在模型中 的应用
3. 重复1.、2.两个步骤，可能出现三种情况： （1）若能找到m个位于不同行不同列的0元素（即 带（ ）的0元素），则令（0）处的xij=1,求解结 束； （2）若有形成闭回路的0元素，则任选一个打 （ ），然后对每个间隔的0元素打（ ），同时 对打（ ）的0元素所在行（或列）画一条直线。 （3）若位于不同行不同列的0元素[即带（ ）的0 元素]少于m，转第四步。
作业：P126 4.1 4.2 4.3(a) 4.4
第四章 整数规划与分配问题
第一节 整数规划的特点及应用
一、整数规划的一般形式 定义：一部分或全部决策变量必须取整数 值的规划问题称为整数规划。不考虑整数 条件，由余下的目标函数和约束条件构成 的规划问题称为该整数规划的松弛问题。 若松弛问题是线性规划，则该整数规划称 为整数线性规划。
3. 对求最大值问题的处理
设目标函数为
mm
maxHale Waihona Puke Baidu
aijxij
可将其变换为
i1 j1 mm
minz'
(aij)xij
i1 j1
此时，效率矩阵的元素全成为负值，不符合要
求，根据定理1，令 Mma aijx
变换后的效率矩阵每行都加M即可。
作业：P127 4.8(a) 第三节 分枝定界法 一、分枝定界法的基本思想
整数规划模型对研究管理问题有重
要意义。很多不能归结为线性规划数学 模型的管理问题，却可以通过设置逻辑 变量建立起整数规划数学模型。
第二节 分配问题(指派问题）与匈牙利法 2-1 问题的提出及数学模型
假设有m项任务分配给m个人去完成，并 指定每个人完成其中一项，每项任务也只由 一个人完成，问应如何分配任务，才能使总 效率最高？（或总费用最少，花费的总时间 最少等等。）
第四步 为产生m个位于不同行不同列的0元素， 用定理一对效率矩阵进行调整，使之生成新的0 元素。方法： 1. 在效率矩阵未被直线覆盖的元素中找出最小 元素k； 2. 效率矩阵未被直线覆盖的行都减k; 3. 效率矩阵被直线覆盖的列都加k; 4. 转回第三步。
2-3 特殊情况的处理 1. 人数多于任务数，加虚拟任务。 设有n人，m项任务，n＞m,则增加n-m项任务。 2. 人数少于任务数，加虚拟人员。 设有n人，m项任务，n＜m,则增加m-n项任务。
定理2. 若效率矩阵A的元素可分成0与非0两 部分，则覆盖所有0元素的最少直线数等于位 于不同行不同列的0元素的最大个数。
匈牙利法的步骤： 第一步 效率矩阵每行都减去该行的最小元素； 第二步 效率矩阵每列都减去该列的最小元素；
此时，效率矩阵的每行每列都有0元素。
第三步 寻找位于不同行不同列的0元素，也就是 寻找能覆盖所有0元素的最少直线数。 方法： 1. 从只有一个0元素的行开始，对0元素打上（ ） 号，然后对打（ ）的0元素所在列画一条直线， 依次进行到最后一行； 2. 从只有一个0元素的列开始，对0元素打上（ ） 号， 然后对打（ ）的0元素所在行画一条直线， 依次进行到最后一列；