第四章整数规划讲义.ppt

第四章 整数规划与分配问题 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.1整数规划的特点及应用 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 §4.2分配问题与匈牙利法 本章习题 东 北 林 业 大 学 第二步，按０元素最少的行优先分配。 （因其对应的分配关系 最省；０元素少选择余地小。） 若选中的０元素的个数与矩阵维数相等，则得到最优方案；否则进行下一步。 △号个数为4，与矩阵维数不相等，所以不是最优方案。 东 北 林 业 大 学 第三步，①在无△号的行标√号； ②在标√号行上的０元素所在的列√号； ③再对标√号的列上有△号的行标√号； ④重复②、③直到不能进行下去为止； ⑤在无√号的行和有√号的列画直线，在直线未覆盖的元素中找出最小元素； ⑥从有√号的行中减去该元素，在有√号的列上加上该元素，则得到一个新的矩阵。 √ √ √ +2 -2 -2 东 北 林 业 大 学 第四步，在新矩阵的基础上，重复第二至第三步，即可得到最优解。 因为△的个数与矩阵的维数相等，所以是最优解，即： z=7+6+7+6+6 =32天 13 7 10 7 10 8 10 6 6 6 7 15 10 11 10 14 14 6 6 9 4 9 6 9 6 １ ２ ３ ４ ５ A B C D E 　 任务 工程队 东 北 林 业 大 学 课堂练习题： 东 北 林 业 大 学 -2 -4 -11 -4 z = 5 + 4 + 11 + 4 = 24 -1 √ √ √ +2 -2 -2 东 北 林 业 大 学 三、两点说明 13 7 10 8 10 6 7 15 10 14 14 6 4 9 6 １ ２ ３ ４ ５ A B C 　 任务 工程队 1.人数和任务数不相等时的处理方法。 13 7 10 0 0 8 10 6 0 0 7 15 10 0 0 14 14 6 0 0 4 9 6 0 0 １ ２ ３ ４ ５ A B C D E 　 任务 工程队 东 北 林 业 大 学 2.当目标函数要求实现极大化时的处理方法。 如本节例中的 cij 表示效益，则问题变为如何分配任务，使总效益最大。即目标函数为: 虽然上述目标函数等价于: 但这样一来价值矩阵中的元素都成了负值，不符合匈牙利法的要求。但可用本节定理进行处理，使元素非负。 东 北 林 业 大 学 若目标函数为: 则构造新矩阵B，其元素bij按下式计算： bij = M - cij 其中M是足够大的数，一般取(cij)中最大的元素。则有： 可见，只有当 取得极大值时， 才能有极小 值。故 最小值的解， 就是 最大值的解。 东 北 林 业 大 学 例4.8 问题的提出： 有四项工作，分配给四个人。每个人的能力不同，完成工作的效率也不同(见表)，如何分配总效率最大(求分配问题的最大解)