metoda węgierska

[aga285]

Poniższa macierz dotyczy czasu wykonywania zadań przez pracowników (wartość z komórki \(\displaystyle{ (i; j)}\) to czas wykonania zadania i przez pracownika j). Zadania można realizować równolegle, a jedno zadanie przypada na jednego pracownika. Ile co najmniej czasu zajmie wykonanie tych zadań?

\(\displaystyle{ \left[\begin{array}{ccccc}5&5&3&6&5\\3&5&5&6&4\\3&4&5&3&5\\5&6&3&5&4\\4&5&4&6&5\end{array}\right]}\)

prosiłabym o sprawdzenie czy dobrze robię to zadanie metodą węgierską.

1. znajduję najmniejsze elementy w każdym wierszu i odejmuję je odpowiednio od każdego wiersza
(czyli w pierwszym wierszu 3, w drugim 3, w trzecim 3, w czwartym 3, w piątym 4)

\(\displaystyle{ \left[\begin{array}{ccccc}2&2&0&3&2\\0&2&2&3&1\\0&1&2&0&2\\2&3&0&2&1\\0&1&0&2&1\end{array}\right]}\)

2. znajduję najmniejsze elementy w każdej kolumnie i odejmuję je odpowiednio od każdej kolumny
(czyli w pierwszej kolumnie 0, w drugiej 1, w trzeciej 0, w czwartej 0, w piątej 1)

\(\displaystyle{ \left[\begin{array}{ccccc}2&1&0&3&1\\0&1&2&3&0\\0&0&2&0&1\\2&2&0&2&0\\0&0&0&2&0\end{array}\right]}\)

3. szukam jak pokryć wszystkie zera minimalną liczbą linii. wyszło mi, że jest ich 5 (macierz jest \(\displaystyle{ 5 \times 5}\), więc się zgadza).

4. szukam rozproszonych zer, to będą wyrazy: \(\displaystyle{ a_{13}}\), \(\displaystyle{ a_{21}}\), \(\displaystyle{ a_{34}}\), \(\displaystyle{ a_{45}}\), \(\displaystyle{ a_{52}}\)

i tym miejscom odpowiada czas w macierzy z treści zadania? czyli czas to:
\(\displaystyle{ 3+3+3+4+5=18}\). czy to jest rozwiązanie jednoznaczne?

[mortan517]

A nie było jeszcze kroku gdzie odejmowało/dodawało się jeden w zależności od tego ile linii przecina się w danej komórce?

[aga285]

z tego, co czytałam to nie. był jeszcze wariant, gdzie liczba linii jest mniejsza niż n, ale też nic o jedynkach nie było. (korzystałam z opracowania na jednej z angielskich stron i z wikipedii)

[mortan517]

Hm, w twoim rozwiązaniu masz dwa razy \(\displaystyle{ a_{21}}\), więc chyba coś jest nie tak.

Możliwe, że jest to dobrze. Ja znam troszeczkę inną metodę. Do tej ostatniej macierzy robi się wszystko tak samo, pokrywa się zera liniami, ale następnie w komórkach których linie nie przecinają odejmuje się jedynkę, tam gdzie przecinają raz nic się nie robi, a tam gdzie przecinają dwukrotnie dodajemy jedynkę.

[aga285]

faktycznie pomyliłam się w tym ostatnim wyrazie, już poprawiłam.

okej, sprawdzę też tak, ale jakby ktoś wiedział czy tamten sposób jest dobry, to fajnie by było, gdyby napisał

a jak już pododaję te jedynki, to wtedy wybieram te zera i odpowiadający im czas?

[mortan517]

Nie znam twojej metody, ale wyniki wychodzą identyczne jak w tej którą używam, więc twoja też musi być dobra

Tak.

[aga285]

dzięki