Metoda przypisania w problemie przypisania: analiza i rozwiązanie przy użyciu algorytmu prób i błędów

Dodano: 16.01.2024 18:17:36

Rozwiązanie

Aby rozwiązać to zadanie, posłużymy się metodą przypisania w problemie przypisania, która polega na znalezieniu takiego przypisania kandydatów do stanowisk, aby całkowity koszt był minimalny.

Do rozwiązania tego typu problemów można wykorzystać algorytm węgierski, który jest skuteczny w rozwiązywaniu problemów przypisania w czasie wielomianowym. Jednak w tym przypadku, ze względu na niewielkie rozmiary problemu, możemy spróbować znaleźć rozwiązanie metodą prób i błędów.

Zaczynamy od znalezienia najniższego kosztu dla każdego stanowiska i przypisujemy kandydata z najniższym kosztem do danego stanowiska, upewniając się, że każdy kandydat jest przypisany tylko do jednego stanowiska, a każde stanowisko ma tylko jednego kandydata.

a) Najpierw znajdujemy najniższy koszt dla każdego stanowiska:

  • Dla S1S_1: najniższy koszt to 22 (kandydat K2K_2)
  • Dla S2S_2: najniższy koszt to 22 (kandydat K1K_1)
  • Dla S3S_3: najniższy koszt to 22 (kandydaci K3K_3 i K7K_7)
  • Dla S4S_4: najniższy koszt to 22 (kandydat K5K_5)
  • Dla S5S_5: najniższy koszt to 22 (kandydat K7K_7)

Widzimy, że mamy konflikt na stanowisku S3S_3 i S5S_5 - kandydat K7K_7 jest najtańszy dla obu stanowisk. Musimy więc zrobić wybór, który zminimalizuje koszt.

Wybieramy przypisanie, które nie koliduje z pozostałymi już przypisanymi kandydatami:

  • Przypisujemy K7K_7 do S5S_5, ponieważ to jedyne stanowisko, na które pasuje bez konfliktu.
  • Teraz musimy znaleźć kolejnego najtańszego kandydata dla S3S_3. Jest nim K3K_3, który ma koszt 22.

Mamy więc następujące przypisanie:

  • S1S_1 - K2K_2
  • S2S_2 - K1K_1
  • S3S_3 - K3K_3
  • S4S_4 - K5K_5
  • S5S_5 - K7K_7

Koszt tego przypisania to: 2+2+2+2+2=102 + 2 + 2 + 2 + 2 = 10.

Kandydaci, którzy nie zostaną zatrudnieni to: K4K_4, K6K_6, K8K_8 oraz K9K_9.

To nie jest jedyne rozwiązanie, ponieważ mieliśmy kilka kandydatów z tymi samymi kosztami na różnych stanowiskach, więc mogą istnieć inne kombinacje przypisań o tym samym minimalnym koszcie.

b) Jeśli tabela przedstawiałaby potencjalne zyski z zatrudnienia danego kandydata na danym stanowisku, wówczas chcielibyśmy maksymalizować całkowity zysk. W takim przypadku szukalibyśmy największej wartości dla każdego stanowiska i przypisywali kandydatów analogicznie do metody minimalizacji kosztów, ale tym razem zwracając uwagę na maksymalizację zysku. Zmieniłoby to podejście do wyboru kandydatów oraz mogłoby zmienić końcowe przypisanie.

c) Aby wskazać kandydatów, którzy zawsze będą/nie będą brani pod uwagę, musielibyśmy analizować inne możliwe kombinacje przypisań i zobaczyć, czy niektórzy kandydaci są wybierani we wszystkich minimalnych rozwiązaniach kosztów lub są pomijani we wszystkich rozwiązaniach. Jeśli taka sytuacja ma miejsce, to możemy stwierdzić, że dani kandydaci zawsze będą/nie będą brani pod uwagę.

W tym konkretnym przypadku, bez przeprowadzenia pełnej analizy wszystkich możliwych przypisań, trudno jest jednoznacznie wskazać takich kandydatów. Wymagałoby to dokładniejszego zbadania problemu, co mogłoby być czasochłonne bez użycia odpowiedniego algorytmu, jak algorytm węgierski.

Pomagamy rozwiązywać zadania w 30 sekund

Zarejestruj się i zobacz jak to działa.

Zarejestruj się