资源分配问题

1、1 有有n n项任务，分配给项任务，分配给n n个人去完成，要求每个个人去完成，要求每个人完成其中一项任务，每项任务只交给其中一人完成其中一项任务，每项任务只交给其中一个人完成，已知每个人完成各项任务的成本个人完成，已知每个人完成各项任务的成本（或效率），求使总成本最少的分配方案。（或效率），求使总成本最少的分配方案。 任务分配问题；指派问题任务分配问题；指派问题（Assignment Problem, AP）2有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表，问如何分配任务使完成四项任务的总工时耗费最少？任务任务 工时

2、工时ABCD人员人员人员人员甲甲109781乙乙58771丙丙54651丁丁23451任务任务11113xij 为第 i 个工人分配去做第 j 项任务；aij 为第 i 个工人为完成第 j 项任务时的工时消耗；aijmm 称为效率矩阵mjijijixij, 2 , 1,01项任务项任务个工人未分配去做第个工人未分配去做第当第当第项任务项任务个工人分配去做第个工人分配去做第当第当第1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx4 目的地目的地车辆编号车辆编号D D1 1D D2 2D D3 3D D4 4D D5 5D D6 61

3、 14646666655555959202028282 22424818125256262252591913 32828222239395050272786864 44646313145454747545458585 56565444464644343313160606 6323224243434242433336464设某运输队有6辆卡车，需分派驶往6个不同的目的地，由于各辆卡车的性能、消耗和效率不同，因而驶往各目的地的运输成本也不同，如下表所示。试求能使总成本最低的车辆分派方案。 效率矩阵5否则目的地号车辆驶往第若分派第 , 1 , 0jixij6 , 2 , 1,ji6665646362

4、61565554535251464544434241363534333231262524232221161514131211643324342432 603143644465 585447453146 8627503962228 912562258124 282059556646min xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz6 , 2 , 1, 1, 06 , 2 , 1 , 16 , 2 , 1 , 1 s.t.6161jixjxixijiijjij或6运输问题是运输问题是AP的松弛问题；的松弛问题；AP不但是整数规划，而且是不但是整数规划，而且是0 1规

5、划；规划；AP有有2m个约束条件，但有且只个约束条件，但有且只有有m个非零解，是自然个非零解，是自然高度退化高度退化的。的。1111min( )1 1,2,1 1,2,0,1mmijijijmijjmijiijf xa xximxjmx7njmixnbxmiaxxcCijjmiijinjijminijij, 2 , 1, 2 , 1, 0, 2 , 1j , 2 , 1 min 1111j ), 2 , 1( 0, 2 , 1 s.t.max 11 且为整数或部分为整数njxmibxaxcZjinjjijnjjj运输问题整数规划资源分配问题8定理定理 1 如果从效率矩阵aijmm中每行元素分别

6、减 去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵bijmm的任务分配问题的最优解等价于原问题的最优解。定理定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 9根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零匈牙利算法匈牙利算法清华算法清华算法10 有有5 5辆公交车可以在辆公交车可以在5 5条公交线路上行驶。不同车条公交线路上行驶。不同车辆在不同

7、的路线上发生的年平均交通事故数如下辆在不同的路线上发生的年平均交通事故数如下表所示。这表所示。这5 5辆公交车如何分配，才能使全年的总辆公交车如何分配，才能使全年的总事故数最少？事故数最少？匈牙利法的解题步骤匈牙利法的解题步骤 线路编号线路编号车辆车辆R1R2R3R4R5D173328D2108697D392706D460835D55342711使费用矩阵出现使费用矩阵出现0元素元素 3 3 2 8 8 6 9 7 2 7 0 6 0 8 3 55 3 4 2 7 1 1 0 6 2 0 3 1 2 7 0 6 0 8 3 53 1 2 0 5初始效率矩阵初始效率矩阵第一步：变换效率矩阵，使每

8、行每列至少有一个零 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4行变换行变换列变换列变换检验是否存在不同行列的检验是否存在不同行列的0元素元素2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4行检验行检验：若某行只有一个零若某行只有一个零元素，则给这零元素加元素，则给这零元素加“”，该零元素为独立零元素。若该零元素为独立零元素。若某行零元素多于一个，则暂某行零元素多于一个，则暂不标号。不标号。 每行、每列只能有一个独

9、立零元素每行、每列只能有一个独立零元素检验是否存在不同行列的检验是否存在不同行列的0元素元素2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4 列检验列检验：若某列只有一个零元素，则给这零元素加若某列只有一个零元素，则给这零元素加“”，该零元素为独立零元素。若某行零元素多于一个，则暂不该零元素为独立零元素。若某行零元素多于一个，则暂不标号。标号。 没有得到位于不同没有得到位于不同行不同列的行不同列的n n个个0 0元元素素方案变换方案变换在所有没有被分配的行打上在所有没有被分配的行打上“ ”号。号。2 1 1 0 51 2 0 3 06 2 7 0 53

10、 0 8 3 40 1 2 0 4 在已打在已打“ ”号的行中找出打号的行中找出打“ ”的列，的列， 并打并打“ ”。在已打在已打“ ”号的列中找出打号的列中找出打“”的行，的行，并打并打“ ”。 重复以上过程，直到无法打重复以上过程，直到无法打“ ”时为止。时为止。方案变换方案变换2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4 对所有打对所有打“ ”号的列和未打号的列和未打“ ”号的行划线。号的行划线。这些线可以将所有的这些线可以将所有的0 0元素至少覆盖一次。元素至少覆盖一次。如果是如果是M M M M矩阵，而又要使最优解分配在矩阵，而又要使最优

11、解分配在0 0元素位置上，划线元素位置上，划线数量应为数量应为M M。本例还没有达到最优解。本例还没有达到最优解。方案变换方案变换在未划线的元素中找出最在未划线的元素中找出最小元素小元素2 1 1 0 51 2 0 3 06 2 7 0 53 0 8 3 40 1 2 0 4 未划线的各行元素减去这个最小元素未划线的各行元素减去这个最小元素已划线的各列元素加上这个最小元素已划线的各列元素加上这个最小元素1 0 0 0 41 2 0 4 05 1 6 0 43 0 8 4 40 1 2 1 41 0 0 0 41 2 0 4 05 1 6 0 43 0 8 4 40 1 2 1 4行检验行检验：

12、若某行只有一个零若某行只有一个零元素，则给这零元素加元素，则给这零元素加“”，该零元素为独立零元素。若该零元素为独立零元素。若某行零元素多于一个，则暂某行零元素多于一个，则暂不标号。不标号。 1 0 0 0 41 2 0 4 05 1 6 0 43 0 8 4 40 1 2 1 4 列检验列检验：若某列只有一个若某列只有一个零元素，则给这零元素加零元素，则给这零元素加“”，该零元素为独立零，该零元素为独立零元素。若某行零元素多于元素。若某行零元素多于一个，则暂不标号。一个，则暂不标号。 1 0 0 0 41 2 0 4 05 1 6 0 43 0 8 4 40 1 2 1 4 1 0 0 0

13、41 2 0 4 05 1 6 0 43 0 8 4 40 1 2 1 4 结果结果第一辆车在第一辆车在3 3号线路号线路 第二辆车在第二辆车在5 5号线路号线路第三辆车在第三辆车在4 4号线路号线路 第四辆车在第四辆车在2 2号线路号线路第五辆车在第五辆车在1 1号线路号线路19 找到原效率矩阵最大元素找到原效率矩阵最大元素m，以，以m减去原效率矩阵减去原效率矩阵各元素值，则新矩阵的最小化各元素值，则新矩阵的最小化AP与原问题有同解与原问题有同解 将相应的费用系数取足够大的数将相应的费用系数取足够大的数M 将此人虚化成多个人，费用系数相同。将此人虚化成多个人，费用系数相同。 类同于不平衡的运

14、输问题。类同于不平衡的运输问题。 已经讨论的问题是费用（成本）最小化的资源分配问已经讨论的问题是费用（成本）最小化的资源分配问题题 工程中经常遇到要求效益最大化的资源分配问题工程中经常遇到要求效益最大化的资源分配问题 解决思路：解决思路：将最大化问题转化为最小化问题将最大化问题转化为最小化问题 在原费用矩阵中减去最大元素，并改变符号，就得到在原费用矩阵中减去最大元素，并改变符号，就得到了新的费用矩阵，并且每个元素均为正了新的费用矩阵，并且每个元素均为正21 某出租汽车公司有5辆出租车在5条线路上服务，不同车辆在不同线路上服务的利润不同。应如何分配这5辆出租车，才能使该公司的收入最大。 线路编号线路编号车辆车辆R1R2R3R4R5T1599104T224635T33105126T4612497T5798105 首先将原问题转化为求极小化问题首先将原问题转化为求极小化问题原费用矩阵中，找出最大元素原费用矩阵中，找出最大元素1212。将矩阵中各元素减将矩阵中各元素减1212，并改变符