Algorytm do wyliczenia pokrycia zapotrzebowania materiałów

Odpowiedz Nowy wątek
2018-12-12 18:35
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

Pozostało 580 znaków

2018-12-13 16:28
1

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

Pozostało 580 znaków

2018-12-13 18:08
Tig
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)
edytowany 1x, ostatnio: Tig, 2018-12-13 18:32

Pozostało 580 znaków

2018-12-13 18:10
1

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

Dziękuję za sprostowanie. Wyedytowałem nieco swój post. - Tig 2018-12-13 18:40

Pozostało 580 znaków

2018-12-13 19:37
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.


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)
edytowany 1x, ostatnio: superdurszlak, 2018-12-13 19:38
Zadziała spoko, o ile zmienne są ciągłe, w przeciwnym wypadku sympleks nie wystarczy i trzeba bawić się w ILP czy coś. - Afish 2018-12-13 19:46

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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