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 koszt = 1 o wartości podaży 30 i popycie 15. Wartością mniejszą jest 15. Odejmujemy ją od podaży (30-15=15) jak i od popytu (15-15=0) (Tabelka. 5.).
Tabelka.5. Krok.2.Min. koszt = 1. Min(30,15) = 15
Sięgamy po tabelkę wyników. Wpisujemy 15 w miejsce odpowiadające minimalnej wartości kosztów w tabelce kosztów. Wyzerował się popyt, więc wypełniamy resztę komórek w wierszu zerami (Tabelka. 6.).
Tabelka.6. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (2,2). Popyt=0, zerujemy komórki w wierszu.
Krok kolejny - 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 koszt = 1 o wartości podaży 20 i popycie 30. Wartością mniejszą jest 20. Odejmujemy ją od podaży (20-20=0) jak i od popytu (30-20=10) (Tabelka. 7.).
Tabelka.7. Krok.3.Min. koszt = 1. Min(20,30) = 20
Sięgamy po tabelkę wyników. Wpisujemy 20 w miejsce odpowiadające minimalnej wartości kosztów w tabelce kosztów. Wyzerowała się podaż, więc wypełniamy resztę komórek w kolumnie zerami (Tabelka. 8.).
Tabelka.8. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (3,1). Podaż=0, zerujemy komórki w kolumnie.
Krok kolejny - 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 koszt = 1 o wartości podaży 15 i popycie 10. Wartością mniejszą jest 10. Odejmujemy ją od podaży (15-10=5) jak i od popytu (10-10=0) (Tabelka. 9.).
Tabelka.9. Krok.4.Min. koszt = 1. Min(15,10) = 10
Sięgamy po tabelkę wyników. Wpisujemy 10 w miejsce odpowiadające minimalnej wartości kosztów w tabelce kosztów. Wyzerował się popyt, więc wypełniamy resztę komórek w wierszu zerami (Tabelka. 10.).
Tabelka.10. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (3,2). Popyt=0, zerujemy komórki w wierszu.
Krok kolejny - 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 koszt = 1 o wartości podaży 5 i popycie 10. Wartością mniejszą jest 5. Odejmujemy ją od podaży (5-5=0) jak i od popytu (10-5=5) (Tabelka. 11.).
Tabelka.11. Krok.5.Min. koszt = 1. Min(5,10) = 5
Sięgamy po tabelkę wyników. Wpisujemy 5 w miejsce odpowiadające minimalnej wartości kosztów w tabelce kosztów. Wyzerowała się podaż, więc wypełniamy resztę komórek w kolumnie zerami (Tabelka. 12.).
Tabelka.12. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (4,2). Podaż=0, zerujemy komórki w kolumnie.
Krok kolejny - 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 koszt = 1 o wartości podaży 40 i popycie 5. Wartością mniejszą jest 5. Odejmujemy ją od podaży (40-5=35) jak i od popytu (5-5=0) (Tabelka. 13.).
Tabelka.13. Krok.6.Min. koszt = 1. Min(40,5) = 5
Sięgamy po tabelkę wyników. Wpisujemy 5 w miejsce odpowiadające minimalnej wartości kosztów w tabelce kosztów. Wyzerował się popyt jednak nie ma w wierszu już więcej komórek do wyzerowania (Tabelka. 14.).
Tabelka.14. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (4,4). Popyt=0, nie ma co zerować.
Krok ostatni - bierzemy tabelkę kosztów i zakreślamy na niej komórki, które wypełniliśmy zerami w tabelce wyników. Została ostatnia nie zakreślona komórka w tabelce kosztów. Jest to koszt = 6 o wartości podaży 35 i popycie 35. Dla ostatniego elementu (w ostatnim kroku) popyt i podaż zawsze muszą być sobie równe. Odejmujemy 35 od podaży (35-35=0) jak i od popytu (35-35=0 (Tabelka. 15.).
Tabelka.15. Krok.7.Min. koszt = 6. Min(35,35) = 35
Sięgamy po tabelkę wyników. Wpisujemy 35 w ostatnią komórkę tabelki. Wyzerowały się zarówno popyt jak i podaż (Tabelka. 16.).
Tabelka.16. Miejsce odpowiadające minimalnemu kosztowi w tabeli kosztów - (5,4). Popyt=0, nie ma co zerować.
Tabelka po tym kroku powinna mieć wszystkie wartości popytu i podaży równe zero.
W ten sposób uzyskaliśmy rozwiązanie dopuszczalne(Tabelka. 19.). Wszystkie zerowe elementy rozwiązania nazywamy elementami niebazowymi. Natomiast elementami bazowymi nazywamy wszystkie elementy niezerowe. Przy czym el. bazowych powinno być m+n-1 (5+4-1=8), wówczas rozwiązanie nazywamy zdegenerowanym. W innym przypadku rozwiązanie będzie niezdegenerowane a my nie będziemy w stanie sprawdzić jego optymalności metodą potencjałów.
Tabelka.19. Rozw. dopuszczalne -> niezdegenerowane (7 el. bazowych).
Na koniec należałoby policzyć koszt jaki uzyskaliśmy tą metodą. Koszt wyliczamy przemnażając dany element tablicy kosztów z danym elementem naszego rozwiązania poczym wartości te sumujemy (Tabelka. 20.).
Tabelka.20. Koszt rozwiązania dopuszczalnego
Uzyskaliśmy wynik 275. Porównując go z kosztem uzyskanym innymi metodami (pn.-zach. kąta lub VAM) zauważymy, że wynik nie jest najgorszy (ani najlepszy). W odróżnieniu od metody pn. - zach. kąta w metodzie najmniejszego elementu bierzemy pod uwagę macierz kosztów.
Szymuszka