To tylko jedna z 11 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Problem transportowy Metoda najmniejszego elementu. Pełna nazwa to metoda najmniejszego elementu w macierzy kosztów. Metodą tą uzyskamy rozwiązanie dopuszczalne zadania transportowego. Bierze ona pod uwagę macierz kosztów dzięki czemu daje w wyniku niski koszt rozwiązania.
Jesteśmy firmą przewozową (np. oranżady). Czterech producentów oranżady (P1, P2, P3, P4) z różnych miast dysponuje odpowiednio 20, 30, 10 i 40 skrzynkami napoju. Natomiast 5 sklepów (S1, S2, S3, S4, S5) z innych miast chętnie kupią odpowiednio 10, 15, 30, 10 i 35 skrzynek. Mamy jak najmniejszym kosztem porozwozić wszystkie skrzynki, znając koszty drogi od danego producenta (dostawcy) do każdego sklepu (odbiorcy). Koszty te zostały zestawione w tabeli poniżej (Tabelka.1.). Tabelka.1. Zestawienie danych z zadania w postaci tabelki
Rozwiązanie problemu metodą najmniejszego elementu macierzy kosztów:
Na początek musimy przygotować sobie dwie tabelki o wymiarze m-wierszy na n-kolumn,
gdzie: m - liczba odbiorców,
n - liczba dostawców.
Dodajemy wiersz u góry z liczbą towaru do dostarczenia (podaż) i kolumnę na końcu z liczbą towaru do odebrania (popyt). Przy czym pierwsza tabelka jest czysta (na wyniki) druga natomiast wypełniona kosztami (Tabelka.2.).
Tabelka.2. Tabelka na wyniki (a) oraz tabelka kosztów (b)
W pierwszym kroku kładziemy przed sobą tabelkę kosztów. Zaczynając od góry szukamy pierwszej komórki o najmniejszym koszcie, odznaczamy ją. Komórce tej odpowiada jedna wartość podaży oraz popytu. Wybieramy spośród nich wartość mniejszą i odejmujemy ją zarówno od danej komórki popytu jak i komórki podaży.
Pierwszym minimalnym kosztem jest 1, o podaży = 10 jak i popycie = 10. Wartości podaży i popytu są równe, więc wartością minimalną będzie 10. Odejmujemy ją od popytu (10-10=0) jak i od podaży (10-10=0) (Tabelka. 3.). Tabelka.3. Krok.1.Min. koszt = 1. Min(10,10) = 10
Teraz sięgamy po czystą tabelkę. Wpisujemy naszą wartość minimalną min(popyt, podaż) w komórkę, która odpowiada komórce z minimalnym kosztem w tabeli kosztów. Następnie sprawdzamy, która wartość (popytu czy podaży) wyzerowała się. Jeżeli wyzerowała się podaż to wstawiamy zera w resztę komórek w tej kolumnie, jeżeli popyt to wstawiamy zera w resztę komórek danego wiersza. W tym przypadku wyzerowała się zarówna podaż jak i popyt - wypełniamy więc zerami zarówno wiersz jak i kolumnę (Tabelka. 4.). Tabelka.4. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (1,3). Popyt=0 i podaż=0, zerujemy komórki w kolumnie jak i w wierszu.
Krok drugi - bierzemy tabelkę kosztów i zakreślamy na niej komórki, które wypełniliśmy zerami w tabelce wyników. Następnie szukamy w niej następnego minimalnego kosztu (pomijając zakreślone komórki). Jest to
... zobacz całą notatkę
Komentarze użytkowników (0)