R中的賦值語法lp.assign（）

有誰知道R函數來解決組合優化的賦值問題。例如：假設我有N = 3名學生（1,2,3）和S = 4個可能的工作安排（A，B，C，D）。每個N = 3名學生對所有S = 4個工作職位進行排名。 1分配顯然沒有學生（缺少表示爲「。」）。這是事實（因爲N小於S）並沒有問題。有（我認爲）4！可能的分配位置：R中的賦值語法lp.assign（）

A B C D 
1 2 3 . 
1 . 2 3 
1 3 . 2 
1 . 3 2 
1 3 2 . 

And so on for the next 18 possible ways...

所以，如果N和S是小我能考慮學生的所有可能的「現實」被分配的工作。我可以從每個「現實」中總結出隊伍。並選擇最低總和等級的現實（在一個公平的系統中），即大多數學生得到他們想要的東西。

來源

2014-01-15 Chris

你的直覺，這是不是這麼一個合適的問題可能是正確的。您基本上要求提供工具建議和一般意見的組合，這通常不是我們在這裏的目標。我會建議尋求這方面的專家的建議，可能是處理組合優化或組合優化的人。 – joran

舉個例子來說R中假設矩陣m其中每行是學生，每列是工作，1表示學生的首選，2表示第二選擇等。 9意味着學生沒有排名工作。有3個學生和4個任務，所以我們在最後一行中添加了一個虛擬學生U，這樣學生和任務的數量是相同的。我們假設目標是最小化隊伍總和。下面我們看到，最好的任務是將學生1分配到工作C，學生2到工作D，學生3到工作A和未分配的行潦倒起來工作B。

m <- matrix(c(3, 2, 1, 9, 2, 3, 2, 9, 1, 9, 3, 9, 9, 1, 9, 9), 4, 
     dimnames = list(c(1, 2, 3, "U"), c("A", "B", "C", "D"))) 

# A B C D 
# 1 3 2 1 9 
# 2 2 3 9 1 
# 3 1 2 3 9 
# U 9 9 9 9 

library(lpSolve) 
fm <- lp.assign(m)

此時fm$solution包含溶液，相同尺寸的用0和1項的基質如m。

注：如果解決方案是可能除了一些行是全零，那麼這將給予分配置換矩陣：

student <- rownames(m) 
ix <- round(fm$solution %*% seq_len(ncol(m))) 
job <- colnames(m)[ifelse(ix == 0, NA, ix)] 
data.frame(student, job)

最後一行給出在這種情況下，每個學生下面這樣得到了他們的第一選擇：

student job 
1  1 C 
2  2 D 
3  3 A 
4  U B

注意，可能有不止一個最小化的解決方案，例如，如果兩個學生選擇相同的排名。

來源

2014-01-15 22:39:58

Thx爲'lp.assign（）'建議。我真正的問題是188 * 188的成本矩陣。我得到輸出'成功：目標函數是1171'爲我的問題。每個'FM $ solution'表188個rowsums和colsums的是1。當我用'工作< - colnames（M）[應用（FM $溶液== 1，1，它）]'我得到錯誤：'錯誤在colnames（m）[apply（fm $ solution == 1，1，which）]：無效的下標類型'list''。一些元素是'integer（0）'。爲什麼'which（）'沒有正確地將列編號分配給特定作業正在評估的學生的1位置？ – Chris

我認爲在'fm $ solution'中，每行和每列都會有一個1，其他所有內容都是0.看起來情況並非如此。查看'fm $ solution'來確定發生了什麼。 –

我仔細看了一下我的矩陣...... lp.assign（）的輸出看起來像一個置換矩陣（可能是僞裝）。然而，當我邏輯地評估看起來像1的'[i，j]'元素是否爲1時，他們評估爲'FALSE'。因此，當你查找確切的1時，爲什麼'which（）'失敗。我通過將'round（）'應用於'fm $ solution（）'矩陣來解決這個問題。所以我的僞裝1被取整爲1（確切），然後通過'which（）'函數找到。合理？我希望？我認爲這是lp.assign（）和它創建的解決方案矩陣類型的錯誤？ – Chris

你試圖解決的問題是運籌學中一個叫做Assignment Problem的着名問題。

貪婪算法不起作用，因爲它強烈依賴於它分配學生的順序，並且可能做出非常糟糕的決定。

你可以解決它平凡使用itertools庫從Python來遍歷所有排列（如在How to generate all permutations of a list in Python），並選擇最好的一個，但它是真的，真的昂貴這種方式（有階乘#jobs可能的分配）...雖然這是一種調試算法的方法;）。

正如維基百科文章所說，您可以使用匈牙利算法（但我不會嘗試自己實現它，這有點棘手）或使用最小成本流算法解決此問題。

Python中有一個實現已經，自帶的例子：

https://pypi.python.org/pypi/munkres/

要安裝它，你可以簡單地使用PIP：

pip install munkres

來源

2014-01-15 22:15:03

R中的賦值語法lp.assign（）

回答

相關問題