最優指派問題與R

04-29

1.最優指派問題

最優指派問題也稱為最優匹配問題，它是運輸問題的特殊情況。問題描述如下：

設有 $n$ 個人，計劃做 $n$ 項工作，其中 $c_{ij}$ 表示第 $i$ 個人做第j項工作的收益，現求一種指派方式，使得每個人完成一項工作，總收益最大。

2.數學模型

設決策變數為 $x_{ij}，$ 當第i個人做第j項工作時，決策變數 $x_{ij}=1$ ;否則，決策變數 $x_{ij}=0$ ，因此最優指派問題可以寫成0-1規劃模型：

$max z =sum^n_{i=1}sum^n_{j=1}c_{ij}x_{ij}$

s.t.

$sum^n_{j=1}x_{ij}=1,i=1,2,3,cdots,n\ sum^n_{i=1}x_{ij}=1,j=1,2,cdots,n\ x_{ij}=1quad orquad 0,i=1,2,cdots,n;j=1,2,cdots,n$

如果c_{ij}表示第i個人做第j項工作所用的花費，則目標函數為求最小。

3.案例

設收益矩陣下表所示，表中「-」表示某人無法完成該項工作。

6人做6項工作的收益情況

解：這裡提供的是收益矩陣，所以目標函數為求最大值。當某人無法完成某項共工作時，其收益值為負無窮大（計算的時候取較大的數）。這樣收益矩陣為

$c=egin{equation} left( egin{array}{ccc} 20 & 15 & 16 & 5& 4 & 7 \ 17 &15 &33& 12 &8& 6 \ 9 &12 & 18 &16 &30& 13\ 12 & 8 & 11& 27 &19 &14\ -99 & 7& 10& 21 &10& 32\ -99& -99& -99 & 6 &11& 13\ end{array} ight) end{equation}$

R 語言實現

z<-c( 20, 15 , 16 , 5, 4, 7, 17, 15, 33, 12 , 8 , 6, 9, 12, 18, 16, 30, 13, 12, 8, 11, 27, 19, 14 ,-99, 7, 10, 21, 10, 32, -99, -99, -99, 6, 11, 13)cost<-matrix(z,nrow=6,byrow=T)assign.sol<-lp.assign(cost.mat=cost,direction="max")

> assign.sol

Success: the objective function is 135

> assign.sol$solution

[,1] [,2] [,3] [,4] [,5] [,6]

[1,] 1 0 0 0 0 0

[2,] 0 0 1 0 0 0

[3,] 0 1 0 0 0 0

[4,] 0 0 0 1 0 0

[5,] 0 0 0 0 0 1

[6,] 0 0 0 0 1 0

結果分析：

第1個人做第1項工作；

第2個人做第3項工作；

第3個人做第2項工作；

第4個人做第4項工作；

第5個人做第6項工作；

第6個人做第5項工作。

4.最優指派問題的應用

游泳隊員的選拔問題

某高校準備從5名游泳隊員中選擇4人組成接力隊，參加市裡的4*100米混合泳接力比賽。5名隊員4種泳姿的百米平均成績如下表所示，應該如何選拔隊員組成接力隊？

5名隊員4種泳姿的百米平均成績

解：由於工作數少於人數，需要添加一個虛擬泳姿，而且沒問隊員在虛擬泳姿上的游泳時間為0。這樣矩陣c為

R程序為

R實現過程

-----------------------------

> z<-scan("clipboard")

Read 25 items

> z

[1] 66.8 75.6 87.0 58.6 0.0 57.2 66.0 66.4 53.0 0.0 78.0 67.8 84.6 59.4 0.0 70.0 74.2 69.6 75.2 0.0 67.4 71.0 83.8 62.4 0.0

> c<-matrix(z,nrow=5,byrow=T)

> c

[,1] [,2] [,3] [,4] [,5]

[1,] 66.8 75.6 87.0 58.6 0

[2,] 57.2 66.0 66.4 53.0 0

[3,] 78.0 67.8 84.6 59.4 0

[4,] 70.0 74.2 69.6 75.2 0

[5,] 67.4 71.0 83.8 62.4 0

> assign.sol<-lp.assign(cost.mat=c,direction="min")

> assign.sol

Success: the objective function is 253.2

> assign.sol$solution

[,1] [,2] [,3] [,4] [,5]

[1,] 0 0 0 1 0

[2,] 1 0 0 0 0

[3,] 0 1 0 0 0

[4,] 0 0 1 0 0

[5,] 0 0 0 0 1

----------------------------

結果分析：

甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳，戊沒有被選拔上，成績為253.2秒。

5.參考文獻

［1］數學建模---基於R. 薛毅編著機械工業出版社