运筹学课件--整数规划

1、第四章第四章 整数规划与分配问题整数规划与分配问题 第一节第一节 整数线性规划问题整数线性规划问题 第二节第二节 分枝定界法分枝定界法 第三节第三节 01 规划规划 第四节第四节 分配问题分配问题 第一节第一节 整数线性规划问题整数线性规划问题一一 、整数线性规划问题、整数线性规划问题二、二、 整数规划的分类整数规划的分类l纯整数规划纯整数规划 所有变量都取非负整数的线性规划所有变量都取非负整数的线性规划 特：特：0 01 1规划规划 变量的值只限制取变量的值只限制取0 0或或1 1的线性规划的线性规划l混合整数规划混合整数规划 部分变量取非负整数的线性规划部分变量取非负整数的线性规划第三节第

2、三节 01规划规划 第三节第三节 01规划规划 第四节第四节 分配问题分配问题 一、一、分配问题分配问题 二、匈牙利方法二、匈牙利方法一、分配问题一、分配问题 分配问题分配问题 分配问题分配问题 基基 本本 概概 念念l解矩阵解矩阵l系数矩阵系数矩阵l匹配匹配l独立独立0元素元素系数矩阵的定义与性质系数矩阵的定义与性质匹匹 配配甲甲蝶泳蝶泳乙乙蛙泳蛙泳 丙丙自由泳自由泳丁丁仰泳仰泳甲甲蛙泳蛙泳乙乙自由泳自由泳 丙丙蝶泳蝶泳丁丁仰泳仰泳分配问题的匈牙利解法分配问题的匈牙利解法 第一步：给系数矩阵第一步：给系数矩阵“制造制造”0元素：元素： 1.从系数矩阵的每行元素减去该行的最小元素；从系数矩阵的

3、每行元素减去该行的最小元素； 2. 从系数矩阵的每列元素减去该列的最小元素。从系数矩阵的每列元素减去该列的最小元素。第二步：找第二步：找 n 个独立的个独立的“0”元素元素 ： 如果个数达到如果个数达到n个，则结束，已得最优解；个，则结束，已得最优解； 否则，转第三步。否则，转第三步。第三步第三步 增加系数矩阵中的增加系数矩阵中的0元素：元素：1. 找最少直线覆盖效率矩阵中的所有找最少直线覆盖效率矩阵中的所有0元素元素（1）对没有）对没有0*行的行打行的行打 ，（2）对打）对打 的行上所有有的行上所有有0元素的列打元素的列打 ，（3）对打）对打 的列上所有有的列上所有有0*元素的行打元素的行打

4、 ，（4）重复（）重复（2）（）（3）步，到过程结束）步，到过程结束（5）对没有打）对没有打 的行画横线，所有打的行画横线，所有打 的列画垂线，的列画垂线，找到了覆盖所有找到了覆盖所有0元素的最少直线。元素的最少直线。 分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法2. 增加增加0元素元素（1）在系数矩阵中没有被覆盖的元素中找最小）在系数矩阵中没有被覆盖的元素中找最小元素元素 ；（2）对没有被直线覆盖的行，减去最小元素）对没有被直线覆盖的行，减去最小元素 ，对被直线覆盖的列，加上最小元素对被直线覆盖的列，加上最小元素 ； 转第二步。转第二步。 分配问题的匈牙利

5、解法分配问题的匈牙利解法 9118713161491514410413152分配问题的匈牙利解法分配问题的匈牙利解法 794291187131614915144104131522424104750111006211130001023509606017130 0010235096*06017130001235*096*0601713*01235*096*0601713*01235*096*06*01713 分配问题的匈牙利解法分配问题的匈牙利解法 541100032450115280分配问题的匈牙利解法分配问题的匈牙利解法 最大值问题最大值问题 匈牙利法实质上一种求最小值的方法，匈牙利法实质上一

6、种求最小值的方法，如果给我们的是系数矩阵，如果给我们的是系数矩阵，a ij表示表示的是第的是第 i 个个人员完成第人员完成第 j 项任务的收益，则要求我们如何项任务的收益，则要求我们如何分配某人完成某项任务，使总收益最大。这种分配某人完成某项任务，使总收益最大。这种求最大值的分配问题如何求解呢。求最大值的分配问题如何求解呢。分配问题的匈牙利解法分配问题的匈牙利解法系数矩阵不是方阵系数矩阵不是方阵 在实际问题中，往往遇到有些任务没有人去在实际问题中，往往遇到有些任务没有人去做，或某些人没有分配到任务的情况。对系数做，或某些人没有分配到任务的情况。对系数矩阵来说，表现为系数矩阵不是方阵，而用匈矩阵

7、来说，表现为系数矩阵不是方阵，而用匈牙利法求解时，系数矩阵为方阵是必要条件。牙利法求解时，系数矩阵为方阵是必要条件。 分配问题的匈牙利解法分配问题的匈牙利解法 某工厂订购了三台机器（某工厂订购了三台机器（A,B,C），有四），有四各位置可供机器安装（位置一，二，三，四），各位置可供机器安装（位置一，二，三，四），但但B机器不能安装在第二号位置。由于这四个机器不能安装在第二号位置。由于这四个安装位置离工厂中心的远近不同，所需要的原安装位置离工厂中心的远近不同，所需要的原料运送费用也就不同，想要求总的原料运送费料运送费用也就不同，想要求总的原料运送费用达到最小，问这些机器安装在哪几个位置最用达到最小，问这些机器安装在哪几个位置最适合？适合？ 分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法分配问题的匈牙利解法00006107520131511121013M分配问题的匈牙利解法分配问题的匈牙利解法 某单位有四项