DSC03229

1.1.1. Wyprowadzenie zrewidowanej metody sympleks 15

Jeśli program liniowy jest podany w postaci standardowej, ale zmienne, jedna lub więcej, są swobodne (nie muszą być nieujemne), to problem można sprowadzić do postaci standardowej, zastępując swobodne zmienne zmiennymi x_t = x_i — s*, gdzie zarówno jak i x* są nieujemne. Jeśli funkcję celu trzeba maksymalizować, pomnożenie jej przez —1 zmienia maksymalizację na minimalizację.

1.1.1. Wyprowadzenie zrewidowanej metody sympleks

Rozważmy zagadnienie LP w standardowej postaci (1.1) - (1.3) i załóżmy, że macierz A jest rzędu m. Jeśli B jest dowolną nieosobliwą pod macierzą stopnia m macierzy A, a N jest pozostałą podmacierzą A, to (1.2) możemy zapisać w postaci

(1.4)

[B,N] *^B =i,

^XN

gdzie x_B i x_N mają, odpowiednio, rain-m składowych. Wygodnie jest założyć, że B składa się z pierwszych m kolumn macierzy A.

Jeśli x_N = 0, to rozwiązanie (1.4) nazywa się rozwiązaniem bazowym x_B = B~¹b, a nieosobliwą macierz B nazywa się bazą. Jeśli ponadto x > 0, to mówimy, że x jest bazowym rozwiązaniem dopuszczalnym.

Następujące twierdzenie określa ważną rolę bazowych rozwiązań dopuszczalnych:

Twierdzenie 1.1. Jeśli istnieje rozwiązanie dopuszczalne (spełniające (1.2) -(1.3)), to istnieje bazowe rozwiązanie dopuszczalne. Co więcej, jeśli istnieje rozwiązanie optymalne minimalizujące z, to istnieje optymalne rozwiązanie bazowe.

Dowód znajdzie czytelnik u Luenbergera [1973]. To podstawowe twierdzenie stanowi klucz do algorytmu sympleks, najpotężniejszej metody rozwiązywania programów liniowych. Istnieje kilka różnych wersji tej metody i wiele implementacji numerycznych. Opiszemy prymalną metodę sympleks w wersji zrewidowanej, która jest najpopularniejszą metodą rozwiązywania LP.

Zauważmy najpierw, że dzieląc wektor kosztów c na dwa zbiory elementów związanych z x_B i x_N, możemy wyrazić funkcję celu z następująco:

Z — CgXg + cJ,X_N.

x_B =B~¹h-B~¹Nx„

z = ^B-H+ (e& - c^tbB~¹N)x_n = z₀ + p^Tx„,

Po podstawieniu (1.5)

otrzymamy

(1.6)

gdzie

(1.7)

(1.8)