运筹学-整数规划(二)(名校讲义).ppt
《运筹学-整数规划(二)(名校讲义).ppt》由会员分享,可在线阅读,更多相关《运筹学-整数规划(二)(名校讲义).ppt(22页珍藏版)》请在三一文库上搜索。
1、第十六讲 整数规划(二),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为效能矩阵(或费用
2、矩阵)元素,表示第i人 去完成第j任务时的费用。共有m个人去完成m件工作。 求解该问题可采用匈牙利法,其主要思路和步骤如下: 在费用矩阵中,任一行(列)减去或加上个常数,其最优基础解集不变,只改变费用函数值。 从费用矩阵中的i行每个元素减去ai(i=1,m),从j列中每个元素减去bj(j=1,m),则新目标函数改变为: min z = ,1 匈牙利法 (5),= 显而易见,变化后的目标函数表达式只相差一个常数,则规划的最优解集不可能改变。 2用上述方法变换,使费用矩阵每行每列都至少出现1个零,且能达到全分配时,即可令零元素所对应的变量xij=1(当然分配时,必须使每行每列有且仅有1个xij为1
3、)。于是可获得费用函数值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),现在依次检查每列中只含一个未标记的零元素,并给未标记的零元素标。对同一行其它的零元素画(如果有的话)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 整数 规划 名校 讲义
链接地址:https://www.31doc.com/p-2123970.html