《运筹学-整数规划二名校讲义.ppt》由会员分享，可在线阅读，更多相关《运筹学-整数规划二名校讲义.ppt（22页珍藏版）》请在金锄头文库上搜索。
1、第十六讲第十六讲 整数规划（二）整数规划（二） 1匈牙利法2蒙特卡洛法（随机取样法）1 匈牙利法 （1） 匈牙利法主要解决指派问题，指派问题是一种特殊的“01”规划。例如指派授课问题，现有A、B、C、D四门课程，需由甲、乙、丙、丁四人讲授，并且规定：每人只讲且必须讲门课。每门课必须且只需人讲。四人分别讲每门课的费用示于表2-3中：1 匈牙利法 （2） 表2-3 授课费用表 课费用人 A B C D甲乙丙丁2109715414813141611415139求何人讲何门课才能使总费用最低？ 1 匈牙利法 （3） 该例便是指派问题的典型实例，该类问题的典型数学模型为：=1i=1,m=1j=1,m x
2、ij=min z = 1 匈牙利法 （4） 其中，cij为效能矩阵（或费用矩阵）元素，表示第i人去完成第j任务时的费用。共有m个人去完成m件工作。求解该问题可采用匈牙利法，其主要思路和步骤如下：在费用矩阵中，任一行（列）减去或加上个常数，其最优基础解集不变，只改变费用函数值。从费用矩阵中的i行每个元素减去ai(i=1,m)，从j列中每个元素减去bj（j=1,m），则新目标函数改变为：minz =1 匈牙利法 （5） =显而易见，变化后的目标函数表达式只相差一个常数，则规划的最优解集不可能改变。2用上述方法变换，使费用矩阵每行每列都至少出现1个零，且能达到全分配时，即可令零元素所对应的变量xij
3、=1（当然分配时，必须使每行每列有且仅有1个xij为1）。于是可获得费用函数值z=0，这必是此次的最优分配，否则，只会使z0。例如，由表1所示的授课例子中，经过变换可得最后结果为：1 匈牙利法 （6） 当达到右边费用矩阵时，就已达到全分配，用表示之，即，最优解集为：x13=1(甲讲C门课)x22=1（乙讲B门课）x34=1（丙讲D门课） x41=1（丁讲A门课）1 匈牙利法 （7） 此时对应的最后规划模型目标函数必为零，但原始规划目标函数最优值为变换中历次从行（列）中减去（或加上的）常数之代数和。该题变换中共减去28，故本例最优费用值为28。3从前所述，指派问题的关键是如何将原规划的费用矩阵变
4、换成全分配矩阵，现不加证明的阐述其变换步骤（仍结合前例说明）。1)修改费用矩阵，使矩阵的每一行和第一列至少出现1个零元素，处理方法即为每行（每列）都减去该行（列）的最小元素。1 匈牙利法 （8） 5 匈牙利法 （9） 2) 试图制订一个完全分配方案，该方案只与表中零元素相对应。从第行开始，依次检查各行，直到找出只有一个未标记的零元素的一行为止。如果在零元素上有一个符号或，则称零元素已标记。符号表示分配所在行的那一位教师担任所在列的那一门课程。对未做标记的零元素标后，应对同一列其它的零元素画。1 匈牙利法 （10） 现在依次检查每列中只含一个未标记的零元素，并给未标记的零元素标。对同一行其它的零
5、元素画（如果有的话）。如果有多行多列同时有2个或以上的未标记零元素，则可将其中的任意行或列中一个未标零元素标，并将同行和同列的其他零元素画。1 匈牙利法 （11） 因为本例此时不可能制定出只包含零元素的完全分配方案，于是画出最少数目的水平线和垂直线，使它们穿过每行每列的零元素至少一次。其画线步骤如下：检查所有尚未分配（即未标记）的行，并记上。1 匈牙利法 （12） 检查那些尚未检查过的，而在已检查过的行中有零元素的列，并记上。检查那些尚未检查过的，而在已检查过的列中有标记的行，并记上。1 匈牙利法 （13） 重复步骤和，直到不能进一步检查为止。本例中，第轮检查以后即停止。在所有未检查的行和已检
6、查的列画直线，这些线可覆盖所有的零。1 匈牙利法 （14） 在上述最后的缩减矩阵中，检查那些没有线通过的元素。设k为其中最小元素。找出含有未画线元素的各行，将这些行的每个元素减去k。本例中，k=2，因而由第1行、第4行减去2，可得1 匈牙利法 （15） 第步的减法使第步中画垂直线的各列中某些元素变为负，因此对第步画垂直线的每一列中的所有元素加k。本例第1列的每个元素加2可得1 匈牙利法 （16） 为了确定完全分配分案，对上述第步得到的新的费用矩阵，重复制定分配方案。具体说：于是一个完全的最优分配方案制定出来了。即分配如下：甲完成C 乙完成B 丙完成D 丁完成A总费用为9+4+11+4=28（这
7、亦可从变换中从每行（列）减去或加上的数值之代数和求得）。2 蒙特卡洛法（随机取样法）（1） 由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。例2-9已知非线性纯整数规划为：maxP =0xi99(i=1,5)2 蒙特卡洛法（随机取样法）（2） x1+x2+x3+x4+x5400x1+2x2+2x3+x4+6x58002x1+x2+6x3200x3+x4+5x5200对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算(1
8、00)5=1010个点，其计算量非常之大。然而应用蒙特卡洛法去随机计算106个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？2 蒙特卡洛法（随机取样法）（3） 下面就分析随机取样采集106个点计算时，应用概率理论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点，且其目标函数概率分布可示如图2-8与图2-9。高值区0.00001低值区Pab c z图2-9高值区0.01低值区Pab c z图2-82 蒙特卡洛法（随机取样法）（4） 图2-8和图2-9分别表示某规划不同标本集刻画的目标函数分布概率，其中，a b为低值区，b c为高值区，图2-8的高值区b c概率为0.01，图2-9高值区概率为0.00001。现计算，当计算106个点后，有任一个点能落到高值区的概率Ph是多少？对于图2-8：Ph=10.991000000=0.9999（100多位）对于图2-9：Ph=10.9999910000000.999954602可见，即使对于图2-9所示的高区只占0.00001的标本群，蒙特卡洛法的计算可信度也是相当高的。2 蒙特卡洛法（随机取样法）（5） 当然，用计算机来计算106个标本点需花很长时间，然而，在微机日益普及的今天，这种矛盾日趋缓和。从国外一些国家的应用看，该法愈来愈显出其优越性，有广泛的发展前途。
