2013-06-26 45 views
1

我正試圖找到一個最優算法,可以找到最大的子集,其中元素的總和最低,同時覆蓋所有元素。需要一個算法來查找元素子集中的最小代價

例如: - 想象一下A B C是零售商,W X Y Z是產品,目標是儘量減少訪問次數,降低價格。

A B C 
W 4 9 2 
X 1 3 4 
Y 9 3 9 
Z 7 1 1 

So it appears my top two choices are 
a) B:{XYZ} - 7 C:{W} - 2 
b) C:{WXZ} - 7 B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9. 

這個問題看起來類似於頂點覆蓋和其他線性規劃算法,但我找不出合適的。

更新:

看來我需要添加一個額外的變量。介紹t。如果訪問最少的零售商和最少的零售商的成本> t,則選擇下一個前者。

Continuing with the example. 

say t = 5, 

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7 C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7 C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7 C:{W} - 2 is picked 

真的,我只是有興趣,如果已經有一個適合這種模式的算法。我不能成爲需要這種優化的第一人。

+0

Hrmm,考慮使用樹,也許深度優先搜索?過了一段時間,因爲我做了這樣的事情,似乎它可以工作。 – Trent

+0

什麼是最小化價格和最小化訪問之間的折中。您是否想以最低的價格找到滿足這些要求的最低訪問次數? – Owen

+0

這個問題看起來像http://en.wikipedia.org/wiki/Transportation_theory_(mathematics) – MBo

回答

1

您有兩個目標的問題 - 1.最大限度地降低產品的總成本,並最小化訪問的商店數量。 (@ btilly的評論正確地顯示了兩種競爭解決方案。)

多種目標在這些類型的Integer編程問題中相當常見。 See MCDM。 要解決這個問題,你需要有類型的成本(您目前只有一個。)

  1. 從零售商[R購買產品p(你已指定)C_rp
  2. 的成本費用參觀零售商:C_r

直覺:如果C_r非常高,那麼我們會從一個零售商購買所有產品。如果C_r很小,那麼我們會去多家零售商,並從最便宜的人那裏購買。

您的問題可以建模爲「Assignment Problem」的變體。另外,如果您需要更多參考資料,請閱讀所謂的fixed-charge transportation problems(FCTP)。 (有一個固定收費來訪問零售商一次。)

所以到整數規劃:

決策變量

Binary 
    X_rp = if product p is purchased from retailer r, 0 otherwise 
    Y_r = 1 if retailer r is visited, 0 otherwise 

目標函數

Min C_rp X_rp + C_r Y_r 

限制條件

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer) 

接下來,我們需要確保Y_r是1,即使其中一個X_rp對於那個零售商來說也是1。通常情況下,我們會採用Big M方法,但在這個問題上更容易。

X_rp <= Y_r for all p, for all r. 

如果任何一個變量x變爲1,迫使Y_r成爲1.該模型將爲此付出代價C_r。

要解決,您可以使用任何LP解算器。好消息是該問題具有完整性屬性,這意味着即使在使用線性編程解決方案技術時,整數解決方案也自然會出現。

希望有所幫助。

+0

非常感謝。它有很多幫助。 –

+0

賦值問題確實有一個完全單模LP,但是帶有新約束的LP不是TU,考慮到從集合掩護存在一個保留客觀的約簡存在,這並不奇怪。 –

+0

我會將這個問題稱爲非度量設施位置。我同意你選擇整數編程作爲解決方法。 –

相關問題