Z.T. Problem transportowy - metoda e-perturbacji.doc

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.