运筹学整数规划(二)(名校讲义).ppt
第十六讲 整数规划（二）,1 匈牙利法2 蒙特卡洛法（随机取样法）,1 匈牙利法（1）,匈牙利法主要解决指派问题，指派问题是一种特殊的“0 1”规划。例如指派授课问题，现有A、B、C、D四门课程，需由甲、乙、丙、丁四人讲授，并且规定：每人只讲且必须讲门课。每门课必须且只需人讲。四人分别讲每门课的费用示于表2-3中：,1 匈牙利法（2）,表2-3 授课费用表,求何人讲何门课才能使总费用最低？,1 匈牙利法（3）,该例便是指派问题的典型实例，该类问题的典型数学模型为：=1 i=1,m=1 j=1,m xij=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=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从前所述，指派问题的关键是如何将原规划的费用矩阵变换成全分配矩阵，现不加证明的阐述其变换步骤（仍结合前例说明）。1)修改费用矩阵，使矩阵的每一行和第一列至少出现1个零元素，处理方法即为每行（每列）都减去该行（列）的最小元素。,1 匈牙利法（8）,5 匈牙利法（9）,2)试图制订一个完全分配方案，该方案只与表中零元素相对应。从第行开始，依次检查各行，直到找出只有一个未标记的零元素的一行为止。如果在零元素上有一个符号或，则称零元素已标记。符号表示分配所在行的那一位教师担任所在列的那一门课程。对未做标记的零元素标后，应对同一列其它的零元素画。,1 匈牙利法（10）,现在依次检查每列中只含一个未标记的零元素，并给未标记的零元素标。对同一行其它的零元素画（如果有的话）。如果有多行多列同时有2个或以上的未标记零元素，则可将其中的任意行或列中一个未标零元素标，并将同行和同列的其他零元素画。,1 匈牙利法（11）,因为本例此时不可能制定出只包含零元素的完全分配方案，于是画出最少数目的水平线和垂直线，使它们穿过每行每列的零元素至少一次。其画线步骤如下：检查所有尚未分配（即未标记）的行，并记上。,1 匈牙利法（12）,检查那些尚未检查过的，而在已检查过的行中有零元素的列，并记上。检查那些尚未检查过的，而在已检查过的列中有标记的行，并记上。,1 匈牙利法（13）,重复步骤和，直到不能进一步检查为止。本例中，第轮检查以后即停止。在所有未检查的行和已检查的列画直线，这些线可覆盖所有的零。,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（这亦可从变换中从每行（列）减去或加上的数值之代数和求得）。,2 蒙特卡洛法（随机取样法）（1）,由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。例2-9已知非线性纯整数规划为：max P=0 xi99(i=1,5),2 蒙特卡洛法（随机取样法）（2）,x1+x2+x3+x4+x5400 x1+2x2+2x3+x4+6x58002x1+x2+6x3200 x3+x4+5x5200对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算(100)5=1010个点，其计算量非常之大。然而应用蒙特卡洛法去随机计算106个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？,2 蒙特卡洛法（随机取样法）（3）,下面就分析随机取样采集106个点计算时，应用概率理论来估计一下可信度。不失一般性，假定一个整数规划的最优点不是孤立的奇点，且其目标函数概率分布可示如图2-8与图2-9。,2 蒙特卡洛法（随机取样法）（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个标本点需花很长时间，然而，在微机日益普及的今天，这种矛盾日趋缓和。从国外一些国家的应用看，该法愈来愈显出其优越性，有广泛的发展前途。,
