经济数学方法与模型教学ppt课件-第五章 匈牙利法与最佳指派问题

《经济数学方法与模型教学ppt课件-第五章 匈牙利法与最佳指派问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章匈牙利法与最佳指派问题什么是最佳指派问题？最佳指派（或分配）问题是经济计划工作中经常遇到的一个问题．比如，当某一个部门或某一个企业的生产任务已经确定，如何分配给它们所属的单位，使得完成这些任务所需费用最小（或效益最大）．分配问题是较简单的线性规划问题，也是运输问题的一个特例，当然可以用线性规划的单纯形法加以求解．然而，使用本章介绍的方法——匈牙利法去求解，效果会更好，该方法的得名是因为匈牙利数学家狄·考尼格（D·Konig）为发展这个方法证明了主要定理．本章主要内容第一节最佳指派问题的线性规划模型第二节标准指派问题的匈牙利法第三节非标准指派问题第一节最佳指派问题的LP模型例1有一份资

2、料需从汉语译成英、日、俄三种文字，现有A、B、C三人，每人需完成且只完成其中的一种工作．因各人对不同文字的熟悉程度不一样，所需工作时间（单位：天）也不同（见下表）．问应指派哪一个人去完成哪一项工作才能使花费的总时间最短？解：对于某个人来讲，要么做某项工作，比如“译英”要么不做，二者必居其一，换句话说，每个人与每项工作之间只有两种状态：“做”或“不做”为此我们设变量：此时称为0-1变量．由于每个人只能完成一项工作，因而有：又由于每项工作只能由一个人完成，因而又有：上述6个方程以及为0-1变量就构成了本问题的约束条件，而目标为所消耗的总时间最少，因而目标函数为：这是依本例实际问题而建立的线性规划

3、模型．一般地，当指派n个人去完成n项任务时，其数学模型如下：（5.1.1）其中为第个人完成第项任务所消耗的资源（一般指时间或费用等），称之为价值系数．此模型称为指派问题的标准形式。第二节标准指派问题的匈牙利法匈牙利法的基本原理匈牙利法的求解步骤一、匈牙利法的基本原理1、指派问题最优解的性质假设是指派问题的价值系数矩阵，现将它的某一行（或某一列）的各个元素都减去一个常数（可为正，也可为负），得到矩阵．那么以为价值系数矩阵的新的指派问题的最优解与原指派问题的最优解相同，但其最优值比原来减小．利用上述性质，可使原价值系数矩阵变为含有很多0元素的新系数矩阵，而其最优解保持不变，在系数矩阵中，我们关心

4、位于不同行不同列的0元素，以下简称为独立0元素，若能在系数矩阵中得到n个独立的0元素，则令解矩阵中对应这n个独立0元素的变量取值为1，其它变量取值为0，就可以得到原指派问题的最优解．2、关于矩阵中0元素的定理系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数．二、匈牙利法的求解步骤例1有5个人去完成5项任务．每个人只能完成1项任务，每项任务也只能由1个人完成，价值系数矩阵如下表所示（单位：天）．问如何分配才能使完成任务的总时间最少？第一步：变换价值系数矩阵，使各行各列都出现0元素1、将系数矩阵的每行都减去本行的最小元素；2、将上步所得新的价值系数矩阵的每列都减去本列的最小元素．第

5、二步：进行试指派，以寻求最优解1．进行行检验从第一行开始逐行检查，当遇到只含有一个未标记的0元素的一行时，就在该0元素上标记符号△，这表示分配△所在行的那个人担任△所在列的那个任务．然后在该0元素所在列的其它0元素上标记，以免对此任务再进行分配．重复上述行检验，直到每一行都没有未标记的0元素或至少有两个未标记的0元素时为止．2、进行列检验与行检验类似，从第一列开始逐列检查，当遇到只含有一个未标记的0元素的一列时，就在该0元素上标记△，并在该0元素所在行的其它0元素上标记．重复上述列检验，直到每一列都没有未标记的0元素或至少有两个未标记的0元素时为止．3、反复进行1、2直到下列三种情况之一出现

6、：情况一：每一行均标记有△，令△的个数为m，则有m=n．情况二：存在未标记的0元素，但它们所在行和列中，未标记的0元素均至少有2个．情况三：不存在未标记的0元素，但△的个数m

7、元素的列的下侧打√号3．对已打√号的列中含有△的行的右侧打√号；4、重复上述步骤“第三步2”“第三步3”，直到不能进一步打√为止；5、对没打√号的每一行画一横线，而对于已打√号的每列画一纵线，即得到覆盖当前所有0元素的最少直线。本例题中，给第2步所得矩阵的第5行打√号，再给第1列打√号，然后给第3行打√号．分别对该矩阵的第1、2、4行画一横线，而对第1列画一纵线．即得到覆盖当前所有0元素的最少直线．此矩阵如下