Algorytm redystrybucji

Question

Mam tysiąc wiader o różnych rozmiarach. Każde wiadro składa się z czerwonych i niebieskich kulek o różnych masach. Wiem, że 60 procent całkowitej wagi piłki pochodzi z czerwonych kulek, a 40 procent z niebieskich kulek. Każde wiadro ma losową liczbę piłek, losowe rozmieszczenie kulek czerwonych i niebieskich oraz losowy rozkład ciężarów kul.

Muszę wykonać redystrybucję piłek, aby każda łyżka składała się z 59-61 procent masy kulki z czerwonych kulek i 39-41 procent masy kulki z niebieskich kulek. Każdy kubełek powinien mieć dokładnie taką samą wagę, jak przed redystrybucją, ale liczba kulek w każdym wiadrze nie musi pasować do wcześniejszego numeru. Można podzielić piłki, ale każdy podział ma koszt.

Czy ktoś może wskazać mi kierunek algorytmu?

Dzięki.

Answer 1

Jednym z możliwych sposobów jest sformułowanie problemu programowania mieszanego w następujący sposób. Nie jestem pewien, mogą istnieć inne, znacznie wydajniejsze rozwiązania.

Powiedzmy, że w sumie jest R czerwonych kulek i B niebieskich kulek, każda o wadze odpowiednio r1, r2, ..rR i b1, b2, ...bB.

Powiedz, że Rij jest ułamkiem czerwonej kuli i przypisanej do wiadra j. RBINij jest liczbą binarną, która wynosi 1, jeśli Rij> 0 i 0 w przeciwnym razie. Chcemy zrobić jak najwięcej Rij's 0 (i RBINij's 0) jak to tylko możliwe z minimalną liczbą cięć.

Podobnie Bij jest ułamkiem niebieskiej kuli i przypisanej do kubełka j. BBINij jest liczbą binarną, która wynosi 1, jeśli Bij> 0 i 0 w przeciwnym razie. Chcemy zrobić jak najwięcej Bij 0 (i BBINij 0), jak to możliwe, przy minimalnej liczbie cięć.

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))