文档介绍：该【指派问题的匈牙利法公开课获奖课件赛课一等奖课件 】是由【读书之乐】上传分享，文档一共【43】页，该文档可以免费在线阅读，需要了解更多关于【指派问题的匈牙利法公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。指派问题
指派问题是一种特殊的整数规划问题
一、问题的提出
设有m个工人，能做n件事，但效率不一样，并规定每个工人做且只能做一件事，每件事有且只能有一种工人做，问应当怎样安排他们的工作，使花费的总时间（成本）至少或效率最高？
二、指派问题的数学模型
设第i个工人做第j件事的时间是 ，决策变量是
则数学模型如下
举例阐明 1）表上作业法 2）匈牙利法
例 有四个工人和四台不一样的机床，，问安排哪位工人操作哪一台机床可使总工时至少？
任务1
任务2
任务3
任务4
工人1
工人2
工人3
工人4
2
15
13
4
10
4
14
7
3
14
16
13
7
8
11
9
获得初始解：圈零/划零操作
将时间矩阵C的每一行都减去对应行的最小元素和每一列都减去对应列的最小元素，使每一行和每一列都具有零；
从至少零数的行或列开始，将“零”圈起来，并划去它所在行和所在列的其他零；
反复做2），直到所有零被圈起或被划掉为止。得到初始解。
判断与否为最优解：圈起的零的个数与否等于n。
确定调整行和列
在没有圈起的零所在行上打“√”；
在打“√”行中所有零所在的列打“√”；
在打“√”列中具有圈起零的行上打“√”，
反复执行2）和3）两步，直到不能打“√”为止；
用直线划去打“√”的列和不打“√”的行，没有划去的行构成调整的行，划去的列构成调整列。
调整可行解的措施
在调整行中寻找最小的元素，将它作为调整量；
将调整行各元素减去调整量，对调整列中各元素加上调整量。
再次执行“圈零”和“划零”的操作，并循环以上的环节，直到圈起的零数等于n为止。
时间矩阵
各行各列减去最小元素后得
圈零划零
得最优解
将圈起的零改为1，其他元素改为0，即得最优解如下
最小总时间为22。