szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 21 cze 2016, o 14:52 
Użytkownik

Posty: 39
Lokalizacja: dom
Poniższa macierz dotyczy czasu wykonywania zadań przez pracowników (wartość z komórki (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ń?

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

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

\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 5 \times 5, więc się zgadza).

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

i tym miejscom odpowiada czas w macierzy z treści zadania? czyli czas to:
3+3+3+4+5=18. czy to jest rozwiązanie jednoznaczne?
Góra
Mężczyzna Offline
PostNapisane: 21 cze 2016, o 15:09 
Użytkownik
Avatar użytkownika

Posty: 3403
Lokalizacja: Krk
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?
Góra
Kobieta Offline
PostNapisane: 21 cze 2016, o 15:16 
Użytkownik

Posty: 39
Lokalizacja: dom
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)
Góra
Mężczyzna Offline
PostNapisane: 21 cze 2016, o 15:18 
Użytkownik
Avatar użytkownika

Posty: 3403
Lokalizacja: Krk
Hm, w twoim rozwiązaniu masz dwa razy 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ę.
Góra
Kobieta Offline
PostNapisane: 21 cze 2016, o 15:27 
Użytkownik

Posty: 39
Lokalizacja: dom
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?
Góra
Mężczyzna Offline
PostNapisane: 21 cze 2016, o 15:28 
Użytkownik
Avatar użytkownika

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

Tak.
Góra
Kobieta Offline
PostNapisane: 21 cze 2016, o 15:35 
Użytkownik

Posty: 39
Lokalizacja: dom
dzięki :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiązanie sumy metodą rachunku różnicowego.  Stevie666  4
 Metoda czynnika sumacyjnego - zadanie 3  matiifcb  2
 Metoda podstawiania i zależnosci  mctl  7
 Równanie rekurencyjne - metoda podstawiania - zadanie 2  bartex9  4
 rozwiaz rekurencje metoda funkcji tworzacych  marcyk00  14
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl