To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Problem transportowy Metoda e-perturbacji Metodę tą zastosujemy w momencie kiedy otrzymamy rozwiązanie dopuszczalne niezdegenerowane (dowolną z metod opisanych wcześniej). Nie wpływa ona na koszt rozwiązania dopuszczalnego - powoduje jedynie zwiększenie liczby elementów bazowych
Przyjrzyjmy się rozwiązaniom dopuszczalnym otrzymanym metodami przedstawionymi wcześniej, tj.: metodą pn.-zach. kąta (Tabelka.1a.), najmniejszego elementu w macierzy kosztów (Tabelka.1b.) oraz VAM (Tabelka.1c.). Rozwiązanie otrzymane metodą pierwszą ma 8 elementów bazowych, metodą drugą i trzecią - 7, czyli metoda druga i trzecia dała nam rozwiązanie niezdegenerowane.
Tabelka.1. Rozwiązanie dopuszczalne otrzymane metodą: a)pn.-zach. kąta; b) najmniejszego elementu; c) VAM
Warunkiem rozwiązania zdegenerowanego jest liczba elementów bazowych (baz) równa m+n-1, gdzie:
m - liczba odbiorców,
n - liczba dostawców.
Dla przedstawionego powyżej problemu transportowego baz tych powinno być 5+4-1 = 8. Taką liczbę baz otrzymaliśmy w metodzie pn.-zach. kąta. Dla rozwiązania niezdegenerowanego nie jesteśmy w stanie zastosować metody potencjałów w celu sprawdzenia optymalności rozwiązania (metoda potencjałów zostanie wyjaśniona na następnej stronie.
W celu pozbycia się niezdegenerowania rozwiązania stosujemy metodę e-perturbacji. Wygląda ona następująco (Tabelka.2.):
1. Do każdego odbiorcy dodajemy pomijalnie małą liczbę (nazwijmy ją eta)
2. Do ostatniego dostawcy dodajemy pomijalnie małą liczbę pomnożoną przez liczbę odbiorców (m*eta)
3. Rozwiązujemy zadanie transportowe od nowa wybraną metodą.
Tabelka.2. Metody e-perturbacji.
Poniżej został przedstawiony przykład zastosowania e-perturbacji w przypadku obliczeń metodą najmniejszego elementu macierzy kosztów. Po dodaniu liczby eta do wszystkich odbiorców i liczby m*eta do ostatniego dostawcy postępujemy identycznie jak zostało to opisane w metodzie najmniejszego elementu.
Tabelka.3. Rozwiązanie metodą najmniejszego elementu stosując e-perturbację.
W rezultacie otrzymaliśmy rozwiązanie dopuszczalne, zdegenerowane o liczbie baz = 8.Należy pamiętać, że liczba eta jest wartością pomijalnie małą. Może być - w zależności od danych użytych w zadaniu - liczbą na ósmym, dziesiątym czy setnym miejscu po przecinku (np. eta = 10E-10). Eta nie jest więc brana pod uwagę podczas wyliczania kosztu. Nasze rozwiązanie nadal ma ten sam koszt = 275.
... zobacz całą notatkę
Komentarze użytkowników (0)