第9 章 指派问题和旅行商问题 9.1 指派问题 9 .2 指派问题的句牙利算法 9 .3 旅行商问题的句牙利算法 9 .4 哥尼斯堡七桥问题与欧拉回路9. 1 指派问题 指派问题是指在满足特定指派要求条件下，使指派方案总体效果最佳。在生活中经常碰到有若干项工作需要分配给若干个人( 或部门) 来完成，怎么样才会效率最高呢? 这就是指派问题，一也可以说是分配问题。 此类问题可以归纳为同一种情况: 有个人A1,A2,An有n 项任务 B1,B2,B3,Bn, 指派第i 个人去完成第j 项任务，可以得到一个，nXn矩阵 其中 , 表示第i 个人去完成第j 项任务的效率，这个矩阵称为效益矩阵或价值矩阵。返回9. 2 指派问题的匈牙利算法 指派问题求解归结起来有三种解法:1. 一一列举法，即从概率学出发，1 个人，1 项工作，有1 种指派;2 个人，2 项工作，有2 种指派;3 个人，3项工作，有6 种指派;n 个人，n 项工作，一共有，i! 种指派方法，然后一一列出来，并逐个计算其效益，找出效益最大的那个指派，当然仅限于，i 的个数少的现象;2. 表上作业法，即将指派问题当做物资调运问题来求解
