运筹学指派问题.pdf

该【运筹学指派问题 】是由【雪雁】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【运筹学指派问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学-指派问题(AssignmentProblem)

指派问题的标准形式是:有n个人和n件事,已知第i个人做第j件
事的费用为cij(i,j=1,2,…,n),要求确定人和事之间的一一对
应的指派方案,使完成这n件事的总费用最小。
2
设n个0-1变量若指派第i个人做第j件事
(i,j=1,2,…,n)
若不指派第i个人做第j件事
数学模型为:
其中矩阵C称为是效率矩阵或系数矩阵。
其解的形式可用0-1矩阵的形式来描述,即(xij)nn。
标准的指派问题是一类特殊的整数规划问题,又是特殊的0-1
规划问题和特殊的运输问题。
,提出了解指派问题的一
种算法,习惯上称之为匈牙利解法。

匈牙利解法的关键是指派问题最优解的以下性质:若从指派
问题的系数矩阵C=(cij)的某行(或某列)各元素分别减去一个
’
常数k,得到一个新的矩阵C’=(cij),则以C和C’为系数矩阵的两
个指派问题有相同的最优解。(这种变化不影响约束方程组,而
只是使目标函数值减少了常数k,所以,最优解并不改变。)
作变换,其不变性是最优解
对于指派问题,由于系数矩阵均非负,故若能在在系数矩阵
中找到n个位于不同行和不同列的零元素(独立的0元素),则对
应的指派方案总费用为零,从而一定是最优的。
匈牙利法的步骤如下:
步1:变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最
小元素;再对系数矩阵中的每列元素分别减去该列中的最小元素。若
某行或某列已有0元素,就不必再减了(不能出现负元素)。
步2:在变换后的系数矩阵中确定独立0元素(试指派)。若独立0元
素已有n个,则已得出最优解;若独立0元素的个数少于n个,转步3。
确定独立0元素的方法:当n较小时,可用观察法、或试探法;当n较
大时,可按下列顺序进行
•从只有一个0元素的行(列)开始,给这个0元素加圈,记作,然后划
去所在的列(行)的其它0元素,记作。
•给只有一个0元素的列(行)的0加圈,记作,然后划去所在行的0元
素,记作。
•反复进行,直到系数矩阵中的所有0元素都被圈去或划去为止。
•如遇到行或列中0元素都不只一个(存在0元素的闭回路),可任选其中
一个0元素加圈,同时划去同行和同列中的其它0元素。被划圈的0元素即
是独立的0元素。
•步3:作最少数目的直线,覆盖所有0元素(目的是确定系数矩阵的下
一个变换),可按下述方法进行
1)对没有的行打“”号;
2)在已打“”号的行中,对所在列打“”
3)在已打“”号的列中,对所在的行打“”号;
4)重复2)3),直到再也找不到可以打“”号的行或列为止;
5)对没有打“”的行划一横线,对打“”的列划一纵线,这样就得到
覆盖所有0元素的最少直线数。
步4:继续变换系数矩阵,目的是增加独立0元素的个数。方法是在
未被直线覆盖的元素中找出一个最小元素,然后在打“”行各元素中都
减去这一元素,而在打“”列的各元素都加上这一最小元素,以保持原
来0元素不变(为了消除负元素)。得到新的系数矩阵,返回步2。
以例说明匈牙利法的应用。
例1:求解效率矩阵为如下的指派问题的最优指派方案。
解:第一步:系数矩阵的变换(目的是得到某行或列均有0元素)
第二步:确定独立0元素
元素的个数m=4,而n=5,进
行第三步。
第三步:作最少的直线覆盖所有的0元素,目的是确定系数矩阵
的下一个变换。



第四步:对上述矩阵进行变换,目的是增加独立0元素的个数。方法是
在未被直线覆盖的元素中找出一个最小元素,然后在打“”行各元素
中都减去这一元素,而在打“”列的各元素都加上这一最小元素,以
保持原来0元素不变(消除负元素)。得到新的系数矩阵。(它的最优
解和原问题相同,为什么?)
由解矩阵可得指派方案和最优值为32。
例2某大型工程有五个工程项目,决定向社会公开招标,有五家
建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai(I=1
,2,3,4,5)的报价cij(百万元)见表,问该部门应该怎样分配建
造任务,才能使总的建造费用最小?