[摘要]對(duì)圖論中二元匹配問(wèn)題及其不同要求下的最優(yōu)匹配問(wèn)題，在線性規(guī)劃的理論基礎(chǔ)上，基于Matlab軟件，給出最大效益或最小成本的求解程序及運(yùn)行命令。具有較廣泛和很方便的實(shí)際應(yīng)用價(jià)值。

[關(guān)鍵詞]二元匹配 鄰接矩陣 最大效益分派 最小成本分派 Matlab程序命令

在現(xiàn)實(shí)中有多種多樣的分派(匹配)問(wèn)題，他們的共同特征是:在滿足一定的分派條件的前提下，通過(guò)制定分派方案以達(dá)到總體效益最佳的目的。本文就解決m個(gè)人、n項(xiàng)工作的最優(yōu)分派方案為目的，基于Matlab軟件給出的計(jì)算程序具有運(yùn)行速度快、命令簡(jiǎn)潔，并且對(duì)較多類型的分派問(wèn)題均可求解，在實(shí)際應(yīng)用中具有可操作性。

設(shè)二元匹配的鄰接矩陣為W，其中:cij表示xi人做yj項(xiàng)工作的效益(或表示yj項(xiàng)由xi人完成所付的成本);再設(shè)決策變量xij=1:第i個(gè)人做第j項(xiàng)工作(任務(wù));或xij=0:第i個(gè)人不做第j項(xiàng)工作(任務(wù))。根據(jù)線性規(guī)劃可建立如下所示的數(shù)學(xué)模型，其中:k為每個(gè)人所承擔(dān)的任務(wù)項(xiàng)數(shù)，t為執(zhí)行每項(xiàng)任務(wù)所需要的人數(shù)。

一、一人一項(xiàng)任務(wù)的分派問(wèn)題

這種分派(匹配)問(wèn)題，是指每個(gè)人最多只能承擔(dān)一項(xiàng)任務(wù)，并且每項(xiàng)任務(wù)最多只能由一個(gè)人承擔(dān);建立該類問(wèn)題的數(shù)學(xué)模型時(shí)，只需在上面數(shù)學(xué)模型中(1)和(2)取等式，且k=t=1即可。為應(yīng)用方便，先建立三個(gè)m—文件(源碼、程序及命令在Matlab 6.5.1檢驗(yàn)通過(guò))，再分別討論這類問(wèn)題。

第一個(gè)M—文件matrixGenerator.m如下:

function array = matrixGenerator(len)

array = zeros(2 * len， len ^ 2);for row = 1 : len;for ind = 1 : len;

array(row， ind + (row - 1) * len) = 1; end， end，for row = len + 1 : len * 2;

for ind = 1 : len;array(row， (row - len) + (ind - 1) * len) = 1; end， end

第二個(gè)M—文件ipslvWraper.m為:

function [x， how] = ipslvWraper(W)

W=W'; a=W(:);a=a';valueMat=-a;len = length(valueMat);base = sqrt(len);

if floor(base) ~= base;sprintf('價(jià)值系數(shù)的個(gè)數(shù)不能開平方而得到整數(shù)，參數(shù)錯(cuò)誤!\');

how = 0; x = []; return; end，A = matrixGenerator(base);intlist = ones(1，len);

B = ones(2*base， 1);ctype = zeros(2*base， 1);xm = zeros(len，1);xM = ones(len，1);

[x，how] = ipslv_mex(valueMat，A，B，intlist，xM，xm，ctype);how，z = valueMat*x，x = x';

result = zeros(base， base);for i = 1 : len;result(i) = x(i);end，result'

第三個(gè)M—文件ipslv_mex.m在免費(fèi)工具箱lpsolve文件夾中，可以由MathWorks公司網(wǎng)站下載lpsolve文件夾。

1. 人數(shù)與任務(wù)的項(xiàng)數(shù)相等(m=n)

此時(shí)每人必須承擔(dān)一項(xiàng)任務(wù)，且每項(xiàng)任務(wù)由且僅由一人承擔(dān)。

在Matlab運(yùn)行窗口中輸入以下運(yùn)行命令:

clear， W=[2 3 5 1 7;2 5 4 6 3;4 2 6 3 8;3 4 2 1 5;6 8 9 4 7]; [x， how] = ipslvWraper(W);

(若由鄰接矩陣求成本最小的匹配，W = -W即可。)返回的結(jié)果為:

how = 0z = -30(最優(yōu)值為-z = 30，若求成本最小的匹配，返回中最優(yōu)值為z。)

2. 人數(shù)多于任務(wù)的項(xiàng)數(shù)(m > n)

此時(shí)每人最多承擔(dān)一項(xiàng)任務(wù)，且每項(xiàng)任務(wù)由且僅由一人承擔(dān)。人數(shù)m多于任務(wù)數(shù)n，增添m-n列，其元素均為0，構(gòu)成方陣(a);即虛構(gòu)m-n項(xiàng)任務(wù)。執(zhí)行這些虛構(gòu)的任務(wù)的效率為0，在求出效益最大匹配的輸出結(jié)果中，劃去虛構(gòu)的這些列，即可得最佳匹配方案。

3. 人數(shù)少于任務(wù)的項(xiàng)數(shù)(m < n)

此時(shí)每人必須承擔(dān)一項(xiàng)任務(wù)，且每項(xiàng)任務(wù)最多有一人承擔(dān)。人數(shù)m少于任務(wù)數(shù)n，增添n-m行，其元素均為0，構(gòu)成方陣(b);即虛構(gòu)n-m個(gè)人。設(shè)這些虛構(gòu)人執(zhí)行各項(xiàng)任務(wù)的效率為0，在求出效益最大匹配的輸出結(jié)果中，劃去虛構(gòu)的這些行，即可得最佳匹配方案。

二、一人多項(xiàng)任務(wù)的分派問(wèn)題

所謂一人多項(xiàng)任務(wù)的分派(匹配)，是指每個(gè)人可以承擔(dān)多項(xiàng)任務(wù)，并且每項(xiàng)任務(wù)最多只能由一個(gè)人執(zhí)行;假設(shè)共有m個(gè)人和n項(xiàng)任務(wù)，也分以下幾種不同的形式討論。

1. 每個(gè)人必須承擔(dān)k項(xiàng)任務(wù)

由于每個(gè)人必須承擔(dān)k項(xiàng)任務(wù)，且每項(xiàng)任務(wù)最多只能由一個(gè)人執(zhí)行，所以有m×k≤n;建立的模型為:在前面給出的數(shù)學(xué)模型中(1)取“=k”，(2)取“≤1”即可。

在Matlab運(yùn)行窗口中輸入以下運(yùn)行命令:

W=[6 9 5 6 5 7;8 8 6 7 4 5;7 8 6 6 5 7]; W=W'; c=-W(:); c=c'; ze=zeros(1，5);zr=zeros(1，6);

A=[ones(1，6)，zeros(1，12);zr，ones(1，6)，zr;zeros(1，12)，ones(1，6);1，ze，1，ze，1，ze;0 1，ze，1，ze，...

1 0 0 0 0;0 0 1，ze，1，ze，1，0 0 0;0 0 0 1，ze，1，ze，1 0 0;0 0 0 0 1，ze，1，ze，1 0;ze，1，ze，1，ze，1];

intlist=ones(1，18);B=[2;2;2;ones(6，1)];ctype=-[ones(9，1)];xm=zeros(18，1);xM=ones(18，1);

[x，how]=ipslv_mex(c，A，B，intlist，xM，xm，ctype);how，z=-c*x， x=x'

返回的結(jié)果為:how = 0，z = 42，最優(yōu)的匹配方案為:x1—y2、y5;x2—y1、y4;x3—y3、y6。

2. 每個(gè)人最多可承擔(dān)k項(xiàng)任務(wù)

每個(gè)人最多承擔(dān)k項(xiàng)，且每項(xiàng)最多由一個(gè)人承擔(dān);模型為:在前面的數(shù)學(xué)模型中(1)取“≤k”，(2)取“≤1”。比如把例2改為:有三個(gè)人，六項(xiàng)任務(wù)，要求每人最多完成三項(xiàng)任務(wù)，其他條件和要求不變;只需在運(yùn)行命令中修改以下兩項(xiàng):B=[3;3;3;1;1;1;1;1;1]; ctype=[-1;-1;-1;-1;-1;-1;-1;-1;-1]。運(yùn)行后得最優(yōu)匹配為:x1—y2、y5、y6;x2—y1、y3、y4 。

3. 每個(gè)人最少執(zhí)行k項(xiàng)任務(wù)

每個(gè)人最少承擔(dān)k項(xiàng)，且每項(xiàng)必須由一個(gè)人承擔(dān);模型為:在前面的數(shù)學(xué)模型中(1)取“≥k”，(2)取“=1”即可。比如把例2改為:有三個(gè)人，六項(xiàng)任務(wù)，要求每人最少完成兩項(xiàng)任務(wù)，其他條件和要求不變;只需在運(yùn)行命令中修改一項(xiàng):ctype=[1;1;1;0;0;0;0;0;0]; 運(yùn)行后得最優(yōu)匹配為:x1—y2、y6;x2—y1、y4;x3—y3、y5。

4. 第i人承擔(dān)k i項(xiàng)任務(wù)

這種情況更具有一般性，比如把例2改為:第一個(gè)人必須完成兩項(xiàng)，第二個(gè)人最多完成四項(xiàng)，第三個(gè)人最少完成一項(xiàng)，其他條件不變。也只需在運(yùn)行命令中修改兩項(xiàng):B=[2;4;1;1;1;1;1;1;1]; ctype=[0;-1;1;0;0;0;0;0;0] .運(yùn)行后得最優(yōu)匹配為:x1—y2、y6;x2—y1、y3、y4;x3—y5。

三、多人合作完成任務(wù)的分派問(wèn)題

所謂多人合作完成任務(wù)的分派，是指有些任務(wù)可以由一個(gè)人單獨(dú)完成，而有些任務(wù)必須由若干個(gè)人共同合作才能完成;假設(shè)共有m個(gè)人和n項(xiàng)任務(wù)，分以下幾種不同的形式討論。

1. 所有任務(wù)必須由h個(gè)人共同合作才能完成

由于每個(gè)人可承擔(dān)多項(xiàng)任務(wù)，且每項(xiàng)任務(wù)必須由h個(gè)人共同合作才能完成;所建立的模型為:在前面給出的數(shù)學(xué)模型中(1)取“≤n”，(2)取“=h”。

在Matlab運(yùn)行窗口中輸入以下運(yùn)行命令:

W=[6 9 6 6 4;8 7 6 7 5;7 8 5 6 6];W=W';c=-W(:);c=c'; ze=zeros(1，4);

A=[1 1 1 1 1， zeros(1，10); zeros(1，5)，1 1 1 1 1， zeros(1，5); zeros(1，10)，1 1 1 1 1;

1，ze，1，ze，1，ze;0 1，ze，1，ze，1 0 0 0;0 0 1，ze，1，ze，1 0 0;0 0 0 1，ze，1，ze，1 0;ze，1，ze，1，ze，1];

intlist=ones(1，15);B=[5;5;5;2;2;2;2;2];ctype=[-1;-1;-1;0;0;0;0;0];xm=zeros(15，1); xM=ones(15，1);[x，how]=ipslv_mex(c，A，B，intlist，xM，xm，ctype);how，z=-c*x，x=x'

由返回的結(jié)果可得: how = 0 ，z = 68，所得最優(yōu)匹配為:y1—x2、x3;y2—x1、x3;y3—x1、x2;y4—x1、x2;y5—x2、x3。即:x1—y2、y3、y4;x2—y1、y3、y4、y5;x3—y1、y2、y5。

2. 所有任務(wù)最多由h個(gè)人共同合作才能完成

每個(gè)人可承擔(dān)多項(xiàng)任務(wù)，且每項(xiàng)任務(wù)最多由h個(gè)人共同合作完成;模型為:在前面數(shù)學(xué)模型中(1)取“≤n”，(2)取“≤h”。在運(yùn)行命令中修改B:前m行的元素為n，后n行的元素為h;修改ctype:共有m+n行，所有元素都取-1。

3. 所有任務(wù)最少由h個(gè)人共同合作才能完成

每個(gè)人可承擔(dān)多項(xiàng)任務(wù)，且每項(xiàng)任務(wù)最少由h個(gè)人共同合作完成;建立的模型為:在前面給出的數(shù)學(xué)模型中(1)取“≤n”，(2)取“≥h”。在運(yùn)行命令中修改B:前m行的元素為n，后n行的元素為h;修改ctype:前m行元素取-1，后n行元素取1。

4. 第i項(xiàng)任務(wù)必須由h i個(gè)人合作才能完成

由于每個(gè)人可承擔(dān)多項(xiàng)任務(wù)，且第i項(xiàng)任務(wù)必須由hi個(gè)人共同合作完成;建立的模型為:在前面給出的數(shù)學(xué)模型中(1)取“≤n”，(2)取“=hi”。

比如將例3改為:有三個(gè)人，五項(xiàng)任務(wù)，第一項(xiàng)、第三項(xiàng)任務(wù)必須由一人單獨(dú)完成;第二項(xiàng)、第四項(xiàng)、第五項(xiàng)任務(wù)必須由兩人合作完成;效益矩陣W如例3所給;求總效益最大的匹配方案。只需在例3的運(yùn)行命令中修改一項(xiàng):B=[3;3;3;1;2;1;2;2]; 運(yùn)行后得最優(yōu)匹配為:y1—x2;y2—x1、x3;y3—x1;y4—x1、x2;y5—x2、x3。

小結(jié):在線性規(guī)劃數(shù)學(xué)模型的理論基礎(chǔ)上，基于Matlab軟件。對(duì)諸類不同的分派問(wèn)題，模型的修改和命令的變化并不大，這就使模型和程序在實(shí)際中的應(yīng)用較為方便。程序運(yùn)行的不足之處是僅給出一個(gè)最優(yōu)方案;如果問(wèn)題存在多種最優(yōu)方案、如果需要得到，可以在鄰接矩陣中交換某些行，即可解決該問(wèn)題。比如對(duì)例3中的W=[6 9 6 6 4;8 7 6 7 5;7 8 5 6 6];變換為w=[7 8 5 6 6;8 7 6 7 5;6 9 6 6 4]; 可得到不同的最優(yōu)方案。

參考文獻(xiàn):

[1] 薛定宇等著:高等應(yīng)用數(shù)學(xué)問(wèn)題的MATLAB求解(第2版)[M].北京:清華大學(xué)出版社.2008.10

[2] 趙靜等編:數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)(第2版)[M].北京:高等教育出版社，2003.6

[3] 樓順天等著: MATLAB 7.X程序設(shè)計(jì)語(yǔ)言[M].西安:西安電子科技大學(xué)出版社，2007.8