Algorytm do wyliczenia pokrycia zapotrzebowania materiałów

0

Witam
Dane jest 8 rodzajów materiałów wejściowych ponumerowanych 1-8, oraz 5 rodzajów materiałów wyjściowych A-E takich że :
1 = {3A} ,cena to 3
2 = {2A, 2B} , cena to 6
3 = {4B, 1C} , cena to 11
4 = {1A, 3B, 3C} cena to 16 itd....
screenshot-20181212182523.png

Moje zapotrzebowanie to : 1000A , 500B , 250C , 100C , 50D
Napisać algorytm który wyliczy ile i których materiałów wejściowych potrzebuję aby pokryć zapotrzebowanie przy jak najniższej cenie sumarycznej, biorąc pod uwagę, że dopuszczalna jest różnica 10% przy końcowej ilości materiałów wyjściowych względem zapotrzebowania.

Czy ktoś mógłby napisać słowo na temat powyższego zagadnienia? Jak zabrać się za stworzenie algorytmu? A może taki już istnieje? Jakiej wiedzy potrzebuję żeby móc popracować nad tym?
Nie jestem studentem informatyki, informatykiem, projekt czysto prywatny.

Dzięki i pozdrawiam

1

Wygląda na typowe zadanie optymalizacyjne, jakiś SAT/SMT/ILP powinien sobie poradzić.

1

Do dyspozycji masz:

  • brute force, tj. przeszukanie wszystkich możliwych rozwiązań (spisują się OK dla malutkich problemów)
  • algorytmy dokładne, np. te wspomniane przez Afish, co do których nie zastosowano heurystyki (spisują się OK dla dużych problemów, ale nie radzą sobie z "nieskończonymi" problemami)
  • algorytmy heurystyczne - np. algorytm genetyczny (bardzo szybko znajdują zadowalające rozwiązanie, ale nie zawsze jest ono mocno zbliżone do optymalnego)
1

@Tig: Rozwiązanie zaproponowane przeze mnie może też dawać przybliżone wyniki, to już kwestia konfiguracji.

1
kremo napisał(a):

Witam
Dane jest 8 rodzajów materiałów wejściowych ponumerowanych 1-8, oraz 5 rodzajów materiałów wyjściowych A-E takich że :
1 = {3A} ,cena to 3
2 = {2A, 2B} , cena to 6
3 = {4B, 1C} , cena to 11
4 = {1A, 3B, 3C} cena to 16 itd....

screenshot-20181212182523.png

Moje zapotrzebowanie to : 1000A , 500B , 250C , 100C , 50D
Napisać algorytm który wyliczy ile i których materiałów wejściowych potrzebuję aby pokryć zapotrzebowanie przy jak najniższej cenie sumarycznej, biorąc pod uwagę, że dopuszczalna jest różnica 10% przy końcowej ilości materiałów wyjściowych względem zapotrzebowania.

Może być np. metoda simpleks Danziga, rozwiążesz to na spokojnie liniowym solwerem z MS Excela :)
Jeśli z 1 jedn. materiału 2 uzyskujesz po 2 jedn. materiału A i B i nie potrzebujesz dodatkowych składników np. 3 do produkcji B (a tak rozumiem ten zapis z klamrami, jeżeli jest inaczej to sprecyzuj proszę), to masz daną taką funkcję celu do zminimalizowania:

\sum\limits_{i = 1}^{8}{x_i \cdot{} c_i }  \rightarrow{} min

Plus dla każdego k-tego materiału wyjściowego masz dwa ograniczenia, od góry i od dołu (nie sprecyzowałeś w którą stronę jest dopuszczalna różnica, więc założyłem, że w obie:

\sum\limits_{i = 1}^{8}{x_i \cdot{} n_{k,i}  \geq{} 0.9 \cdot{} N_k

\sum\limits_{i = 1}^{8}{x_i \cdot{} n_{k,i}  \leq{} 1.1 \cdot{} N_k

ci to cena i-tego materiału wejściowego, xi to ilość i-tego materiału wejściowego, nk,i to ilość k-tego materiału wyjściowego pozyskiwana z 1 jedn. i-tego materiału wejściowego, a Nk to docelowa ilość k-tego materiału wyjściowego.

1 użytkowników online, w tym zalogowanych: 0, gości: 1