文档介绍：第四章整数规划
整数规划的难度远大于一般线性规划
©管理与人文学院忻展红
1999,4
1
整数规划简介
要求所有 xj 的解为整数,称为纯整数规划
要求部分 xj 的解为整数,称为混合整数规划
对应没有整数解要求的线性规划称之为松弛问题
整数规划的解是可数个的,最优解不一定发生在极点
整数规划的最优解不会优于其松弛问题的最优解
2
整数规划的分枝定界法
思路与解题步骤
只解松弛问题
1、在全部可行性域上解松弛问题
若松弛问题最优解为整数解,则其也是整数规划的最优解
2、分枝过程
若松弛问题最优解中某个 xk=bk 不是整数,令 bk 为 bk 的整数部分
构造两个新的约束条件 xk bk 和 xk bk +1,分别加于原松弛问题,形成两个新的整数规划
3、求解分枝的松弛问题—定界过程
设两个分枝的松弛问题分别为问题 1 和问题 2 ,它们的最优解有如下情况
3
分枝问题解可能出现的情况
情况 2, 4, 5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为界被保留,用于以后与问题 2 的后续分枝所得到的解进行比较,结论如情况 4 或 5
4
分枝定界法举例
解:松弛问题的最优解为 x1=, x2=2, OBJ=23
由 x1= 得到两个分枝如下:
5
分枝问题的松弛解
问题II的解即原整数问题的最优解
可能存在两个分枝都是非整数解的情况,则需要两边同时继续分枝,直到有整数解出现,就可以进行定界过程
当存在很多变量有整数约束时,分枝即广又深,在最坏情况下相当于组合所有可能的整数解
一般整数规划问题属于一类未解决的难题,plete,只有少数特殊问题有好的算法,如任务分配问题、匹配问题
6
任务分配问题
有四个熟练工人,他们都是多面手,有四项任务要他们完成。若规定每人必须完成且只完成一项任务,,问如何分配任务使完成四项任务的总工时耗费最少?
7
任务分配问题的数学模型
模型中:xij 为第 i 个工人分配去做第 j 项任务;
aij 为第 i 个工人为完成第 j 项任务时的工时消耗;
{aij}mm 称为效率矩阵
运输问题是任务分配问题的松弛问题
任务分配问题不但是整数规划,而且是01规划
任务分配问题有2m个约束条件,但有且只有m个非零解,是自然高度退化的
任务分配是两部图的匹配问题,有著名的匈牙利算法
下面介绍一种适合手算的算法(出自清华教科书)
8
清华算法
定理 1 如果从效率矩阵{aij}mm中每行元素分别减去一个常数 ui,从每列元素分别减去一个常数 vj ,所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。
证明:略
定理 2 若方阵中一部分元素为零,一部分元素非零,则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。
证明:略
清华算法的基本思路:
根据定理 1 变换效率矩阵,使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零,就找到了最优解
若覆盖变换后的效率矩阵零元素的直线少于m 条,就尚未找到最优解,设法进一步变换矩阵,增加新的零
9
清华算法的步骤:
第一步:变换效率矩阵,使每行每列至少有一个零
行变换:找出每行最小元素,从该行各元素中减去之
列变换:找出每列最小元素,从该列各元素中减去之
第二步:检查覆盖所有零元素的直线是否为m条
划线规则
1、逐行检查,若该行只有一个未标记的零,对其加( )标记,将( )标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零,暂不标记,转下一行检查,直到所有行检查完;
10