重新分配算法

我有一千個不同大小的桶。每個桶由不同重量的紅色和藍色球組成。我知道60％的球重量來自紅球，40％來自藍球。每個桶中有隨機數量的球，紅色和藍色球的隨機分佈以及球重量的隨機分佈。重新分配算法

我需要做一個球的重新分配，所以每個球桶由紅球的球重量爲59-61％，藍球的球重量爲39-41％。每個桶應該具有與重新分配前相同的權重，但每個桶中的球數不一定與先前的數量相匹配。分球是可能的，但每個分組都有成本。

任何人都可以指向算法的方向嗎？

謝謝。

來源

2013-10-01 Anders Lund Fredriksen

一種可能的方法是按照以下方式制定混合整數編程問題。我不確定，可能還有其他更有效的解決方案。假設共有R個紅球和B個藍球，每個球的重量分別爲r1，r2，... rR和b1，b2，... bB。

說Rij是分配給桶j的紅球i的分數。 RBINij是一個二進制數，如果Rij> 0，則爲1，否則爲0。我們希望儘可能多的Rij的0（和RBINij的0）用於最小切割次數。

類似地，Bij是分配給桶j的藍色球i的分數。 BBINij是一個二進制數，如果Bij> 0，則爲1，否則爲0。我們希望儘可能多的Bij的0（和BBINij的0）用於最小切割次數。

Constraints: 
summation over i(wi*Rij) <= 1.564*summation over i(wi*Bij) (61-39 ratio) { for all j buckets } 
summation over i(wi*Rij) >= 1.439*summation over i(wi*Bij) (59-41 ratio) { for all j buckets } 
RBINij >= Rij 
BBINij >= Bij 
+ maybe more constraints like the total weight etc. 

Objective Function: 
Minimize(Ci*summation over i(RBINij + BBINij))

來源

2013-10-01 13:53:55

重新分配算法

回答

相關問題