运筹学课件整形规划问题.ppt

指派问题是0—1规划的特例。 库恩（ww.kuhn）于1955年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用这名称。 指派问题是0—1规划的特例。 库恩（ww.kuhn）于1955年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用这名称。 甲、乙、丙、丁四个人加工A、B、C、D四种工件所需时间（单位：min）如表所示。应指派何人加工何种工件，能使总的加工时间最少？ 工件 人员 A B C D 甲 14 9 4 15 乙 11 7 9 10 丙 13 2 10 5 丁 17 9 15 13 例二、 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 例二、 求解过程如下： 第一步，变换系数矩阵： －5 第二步，试指派： 找到 3 个独立零元素 但 m = 3 n = 4 ◎ ◎ ◎ ? ? 第三步，作最少的直线覆盖所有0元素： ◎ ◎ ◎ ? ? √ √ √ 独立零元素的个数m等于最少直线数l，即l＝m=3n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派： 第三步：作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号； (2)对已打√号的行中所有含?元素的列打√号； (3)再对打有√号的列中含◎ 元素的行打√号； (4)重复(2)，(3)直到得不出新的打√号的行、列为止； (5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。 0 0 0 0 0 0 得到4个独立零元素， 所以最优解矩阵为： ◎ ◎ ◎ ? ? √ √ √ ◎ ◎ ◎ ? ? 15 ◎ ◎ ◎ ? ? ◎ 第四步，变换矩阵(bij)以增加0元素： 没有被直线覆盖的所有元素中的最小元素为1， 然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派： 已知下列五名运动员各种姿势的游泳成绩（各为50米），如表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。单位：秒 任务 人员 A B C D 甲 37.7 43.4 33.3 29.2 乙 32.9 24.7 38.9 26.4 丙 33.8 42.2 28.5 29.6 丁 37.0 33.1 30.4 28.5 例三、 31.1 33.6 41.8 35.4 戊 第一步：增加一种泳姿，各位运动员的成绩均为零，得方阵： 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间为最少的指派方案。 任务 人员 A B C D 甲 25 29 31 43 乙 38 37 25 20 丙 37 27 28 40 丁 44 41 35 23 例二、 23 32 32 37 E 任务 人员 A B C D 甲 25 29 31 43 乙 38 37 25 20 丙 37 27 28 40 丁 44 41 35 23 23 32 32 37 E ◎ ? ◎ ? ? ◎ ? ◎ ? ◎ 从甲、乙、丙、丁、戊五人中挑选四人去完成四项任务。每人完成各项任务时间如表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作所花费时间为最少。 任务 人员 A B C D 甲 10 5 15 20 乙 2 10 5 15 丙 2 15 14 13 丁 15 2 7 6 例三、 8 15 4 9 戊 -2 -5 先增加一种假想工作5，再据题中给的条件列出矩阵： -8 任务 人员 A B C D 甲 20 19 20 28 乙 18 24 27 20 丙 26 16 15 18 丁 17 2