413 2

413

10.2. Metoda sympleks

__e j_ui dla niezbyt dużych m i n. Można natomiast użyć tzw. metody sympleks. Jest * metoda iteracyjna, prowadząca od jednego bazowego wektora dopuszczalnego do innego rektora tego rodzaju w taki sposób, że/ przy tym wzrasta. Metoda sympleks daje dokładny

^rynik po pewnej liczbie kroków, zwykle znacznie mniejszej od    Doświadczenia

numeryc2ne wydają się świadczyć o tym, że liczba niezbędnych kroków jest funkcją liniową liczby ograniczeń, słabo zależy od liczby zmiennych i wynosi mniej więcej od 2m do 3m.

Zilustrujemy teraz użycie metody sympleks na poprzednim przykładzie. Następnie rozważymy pewne komplikacje, jakie mogą wystąpić w obliczeniach.

I. Szukamy najpierw bazowego wektora dopuszczalnego, od którego można zacząć proces iteracyjny, tzn. dzielimy zmienne na dwie klasy: zmienne prawostronne {n—m zmiennych, które powinny mieć wartości zerowe w bazowym wektorze dopuszczalnym) i zmienne lewostronne (m pozostałych zmiennych). Rozwiązując układ równań (10.1.2) (m równań, m niewiadomych), wyrażamy zmienne lewostronne i/jako funkcje zmiennych prawostronnych.

W przypadku (10.1.4), uznając x_l i x₂ za zmienne prawostronne, mamy wzory x₃ = 60-5x₁-x₂,

(10.2.1)

*4=60—3x_ł—4x₂, x₃=60—4x₁-3x₂,

/« 30x_l+20x₂.

W korzystnym przypadku współrzędne bazowego wektora dopuszczalnego otrzymuje się, podstawiając zera pod zmienne prawostronne. Jeśli jednak pewne zmienne lewostronne mają wartości ujemne, to powstały wektor nie jest bazowym wektorem dopuszczalnym. W takim przypadku trzeba wypróbować inny układ zmiennych prawostronnych.

W rozważanym przykładzie dla x₁=x₂ = 0 otrzymujemy x₃ = X4.=x₅==60. Znaleźliśmy więc bazowy wektor dopuszczalny (punkt O na rys. 10.1.1).

Bazowy wektor dopuszczalny można często znaleźć bezpośrednio (jak w tym przykładzie) lub zaledwie po kilku próbach. Systematy czna metoda, której można używać w trud-niejszych przypadkach, będzie podana w przykładzie 10.2.2. W zasadzie nic jest istotne, od którego bazowego wektora dopuszczalnego zaczyna się obliczenia. Często jednak natrafienie na punkt leżący blisko optymalnego rozwiązania dopuszczalnego (np. dzięki uwzględnie-^niu sensu zadania) pozwala zmniejszyć liczbę iteracji. W przykładach tego rozdziału nie idziemy wybierać wektorów początkowych w taki specjalny sposób.

1L Sprawdzamy, czy jest spełnione kryterium maksimum (kryterium oplymalności). ^ tym celu badamy współczynniki w wyrażeniu /przez aktualne zmienne prawostronne.

^CSi żaden ze współczynników przy' tych zmiennych w /nie jest dodatni, to znaleziono już ^ł1tttwiązanie optymalne: /nie może zwiększyć się, gdyby niektórym zmiennym prawostronnym nadano wartości dodatnie, a ujemne są wykluczone. Można wykazać, że sformuło-warunek jest konieczny dla optymainości rozwiązania.

^Jn. Załóżmy, że kryterium maksimum nie jest spełnione. Badamy wtedy, jak bardzo hienia się wartość/, gdy przechodzi się od aktualnego bazowego wektora dopuszczalnego