IDEA METODY SIMPLEKS DLA ROZWIĄZYWANIA ZADAŃ

PROGRAMOWANIA LINIOWEGO

METODA SIMPLEKS

• Metoda: Podstawy teoretyczne,

• Algorytm: Niesprzeczny, skończony ciąg obliczeń kończący się spodziewanym wynikiem,

• Program: Implementacja komputerowa (kod, standard danych WE/WY, stabilność numeryczna).

UWAGI WSTĘPNE

• Zamknięty zbiór rozwiązań dopuszczalnych utworzony przez ograniczenia:

• Jedyne skończone rozwiązanie optymalne,

• Wiele skończonych rozwiązań optymalnych (np. odcinek).

• Otwarty zbiór rozwiązań dopuszczalnych:

• Jedyne skończone rozwiązanie optymalne,

• Wiele skończonych rozwiązań optymalnych - promień,

• Nieograniczone wartość funkcji celu.

WIELOŚCIAN WYPUKŁY

a

b

• 
  Punkty ekstremalne wielościanu

WIELOŚCIENNY ZBIÓR WYPUKŁY (zbiór wypukły otwarty)

• Jeżeli istnieje skończone rozwiązanie optymalne, to istnieje optymalny punkt ekstremalny.

• Algebraicznym odpowiednikiem punktu ekstremalnego jest baza (wartości współrzędnych punktu) - rozwiązanie bazowe.

PUNKTY EKSTREMALNE - BAZA, ROZWIĄZANIA BAZOWE

Niech zadanie PL będzie w postaci bazowej:

c^Tx*maks,

Ax =b,

x * 0,

gdzie:

A - macierz współczynników o wymiarach m x n,

x - n-wymiarowy wektor zmiennych decyzyjnych,

b - n-wymiarowy wektor prawych stron,

c - n-wymiarowy wektor współczynników funkcji celu.

Niech B oznacza macierz kwadratową m-tego stopnia, składającą się z m liniowo niezależnych kolumn macierzy A. Wyznacznik tej macierzy jest, rzecz jasna różny od zera (detB # 0). Dla macierzy B istnieje zatem macierz odwrotna B^-1 = C.

gdzie, I jest macierzą identycznościową (1 na głównej przekątnej i 0 poza nią).

,

gdzie, D = [A_ij]^T, przy czym A_ij jest kofaktorem elementu a_ij.

Macierz B nazywa się bazą, jej kolumny - kolumnami bazowymi, a pozostałe kolumny macierzy A - kolumnami niebazowymi. Zmienne związane z kolumnami macierzy B nazywamy - zmiennymi bazowymi (oznaczenie x_B), a pozostałe zmienne - zmiennymi niebazowymi (oznaczenie x_A). Z każdą baza B układu Ax =b, jest związane rozwiazanie bazowe. Jeśli układ Ax =b, jest niesprzeczny i n > m, to układ ten ma nieskończenie wiele rozwiązań, ale skończoną liczbę rozwiązań bazowych. Układ m równań z n niewiadomymi ma co najwyżej
rozwiązań bazowych.

OZNACZENIA

A = (B, N), x = (x_B, x_N), c = (c_B, c_N).

Układ Ax =b można zapisać: Bx_B +Nx_N = b. Pomnóżmy ostatnią równość lewostronnie przez B^-1, otrzymamy:

B^-1Bx_B +B^-1Nx_N = B^-1b

lub, podstawiając: I = B^-1B, W = B^-1N i b^* = B^-1b,

Ix_B +Wx_N = b^*.

Jeżeli przyjmiemy x_N = 0, to mamy początkowe bazowe rozwiązanie układu równań:

x_B = b^*.

Jeżeli, x_B = b^* = B^-1b > 0, to rozwiązanie bazowe jest rozwiązaniem dopuszczalnym zadania PL.

IDEA METODY SIMPLEKS

• Znaleźć dowolne rozwiązanie bazowe.

• Przejść do innego rozwiązania bazowego, które poprawia wartość funkcji celu.

• Przechodzenie powtarzać do osiągnięcia ekstremum funkcji celu.

WAŻNE

• Kryterium optymalności - kryterium stopu.

• Kryterium według którego wyprowadzamy zmienną z bazy i kryterium wprowadzania na jej miejsce innej zmiennej niebazowej.

PRZYKŁAD

POSTAĆ BAZOWA:

Otrzymujemy ją dodając do lewej strony każdego ograniczenia zmienną bilansującą.

W obliczeniach posługujemy się tablicą simpleksową

Tablica początkowa:

c^Tx→maks		x1	x2	x3	x4	x5	b
BAZA	cB	2	3	0	0	0
x3	0	2	2	1	0	0	14
x4	0	1	2	0	1	0	8
x5	0	4	0	0	0	1	16
cj - zj		2	3	0	0	0

Zmienne x₃, x₄, x₅ - zmienne bilansujące - muszą spełniać warunek nieujemności Ich współczynniki w funkcji celu mają wartość zero: c₃ = c₄ = c₅ = 0.

Pierwsze rozwiązanie bazowe otrzymujemy natychmiast:

x₁ = 0, x₂ = 0, x₃ = 14, x₄ = 8, x₅ = 16.

Bazę tworzą zmienne x₃, x₄, x₅. Zmienne x₁, x₂ są zmiennymi niebazowymi.

Różnicę c_j - z_j nazywamy wskaźnikiem optymalności. Wiersz z tymi współczynnikami nazywany jest także wierszem zerowym i objaśniamy go następująco:

c_j - jest to współczynnik funkcji celu dla zmiennej o indeksie j,

z_j - jest liczbą pokazującą o ile zmniejszy się wartość funkcji celu jeżeli wprowadzimy do bazy zmienną x_j = 1.

c_j - z_j = c_Ba_j, gdzie a_j jest j-tą kolumną macierzy A w aktualnej tablicy simpleksowej

Weźmy zmienną x₁ z naszego przykładu.

Jeżeli x₁ = 1, to nowe wartości dla zmiennych x₃, x₄ , x₅ wynoszą: x₃ = 14 -2 = 12, x₄ = 8 - 1 = 7, x₅ = 16 - 4 =12.

Ponieważ współczynniki funkcji celu dla tych zmiennych maja wartość zero, to z_j = 0 dla wszystkich indeksów j i c_j - z_j = c_j.

KRYTERIUM OPTYMALNOŚCI

Jeżeli wartości wszystkich wskaźników optymalności są ujemne lub równe zero, to rozpatrywane rozwiązanie bazowe jest rozwiązaniem optymalnym. Wartość funkcji celu można zwiększyć kiedy choć jeden współczynnik optymalności ma wartość dodatnią.

KRYTERIUM WEJŚCIA

Do bazy wprowadzamy tę zmienną niebazową, dla której wartość współczynnika optymalności jest największa.

KRYTERIUM WYJŚCIA

Obliczamy ilorazy kolejnych wyrazów wolnych przez odpowiadające im elementy kolumny wchodzącej do bazy (b_i / a_ij ), dla a_ij > 0. Bazę opuszcza ta zmienna, dla której odpowiadający jej iloraz jest najmniejszy.

Przejście od starej bazy do nowej jest nazywane iteracją i jest ono dokonywane na drodze normalnych przekształceń algebraicznych polegających na zamianie zmiennych w układzie równań liniowych.

Tablica po 1-szej iteracji (zmieniamy bazę początkową na bazę sąsiednią):

c^Tx→maks		x1	x2	x3	x4	x5	b
BAZA	cB	2	3	0	0	0
x3	0	2	0	1	-1	0	6
x2	3	1/2	1	0	1/2	0	4
x5	0	4	0	0	0	1	16
cj - zj		1/2	0	0	-3/2	0

Dodatnia wartość c₁ - z₁ wskazuje, że zwiększenie wartości funkcji celu jest możliwe - stąd nazwa wskaźnik optymalności dla c_j - z_j.

Dalsze iteracje są niezbędne.

Ogólna postać tablicy simpleksowej w zapisie macierzowym, dla dowolnej iteracji.

BAZA		c	b
xB	cB	B^-1A B^-1
cj - zj

B^-1 jest odwrotnością macierzy współczynników ograniczeń, które stoją przy aktualnych, dla danej iteracji, zmiennych bazowych. W początkowej macierzy simpleksowej tą macierzą jest macierz jednostkowa I.

ZMIENNE SZTUCZNE

Zmodyfikujmy nasz przykład następująco:

Ponieważ w nowym zadaniu pojawiła się nierówność x₁ + x₂ * 3, to od jej lewej strony odejmujemy nieujemną zmienną x₆ i dla utrzymania początkowego rozwiązania bazowego, dodajemy nieujemną zmienną x₇. Zmienną x₇ nazywa się zmienną sztuczną i wprowadzamy ją do funkcji celu (maksymalizowanej) ze współczynnikiem liczbowym -M, przy czym M jest b. dużą liczbą dodatnią (np. M = ∞).

Mamy zatem postać bazową nowego zadania:

Tablica wyjściowa nowego zadania (M = 100):

c^Tx→maks		x1	x2	x3	x4	x5	x6	x7	b
BAZA	cB	2	3	0	0	0	0	100
x3	0	2	2	1	0	0	0	0	14
x4	0	1	2	0	1	0	0	0	8
x5	0	4	0	0	0	1	0	0	16
x7	-100	1	1	0	0	0	-1	1	3
cj - zj		102	103	0	0	0	-100	0

Dalsze postępowanie jest standardowe.

SPRZECZNOŚĆ

Jeżeli zbiór rozwiązań dopuszczalnych zadania PL jest zbiorem pustym, to o zadaniu mówimy, że jest zadaniem sprzecznym. W tablicy simpleksowej sprzeczność zadania uwidacznia się tym, że gdy wszystkie współczynniki optymalności są niedodatnie (co wskazuje, że znaleziono maksimum funkcji), to współczynnik w macierzy ograniczeń przy zmiennej sztucznej pozostaje dodatni, co wskazuje na niemożliwość znalezienia rozwiązania dopuszczalnego (zmienna sztuczna musi mieć wartość 0).

Wróćmy do początkowego przykładu:

i zmodyfikujmy go następująco:

Łatwo sprawdzić metodą geometryczną lub algebraiczną (tradycyjną), że zadanie jest sprzeczne.

Końcowa tablica simpleksowa (proszę sprawdzić) przyjmie postać:

c^Tx→maks		x1	x2	x3	x4	x5	x6	x7	b
BAZA	cB	2	3	0	0	0	0	100
x3	0	0	0	1	-1	-1/4	0	0	2
x2	3	0	1	0	1/2	-1/8	0	0	2
x1	2	1	0	0	0	1/4	0	0	4
x7	-100	0	0	0	-1/8	0	-1	1	2
cj - zj		0	0	0	-51/2	-60/8	-100	0

NIEOGRANICZONOŚĆ

Rozważmy zadanie:

Bez trudu sprawdzimy sprzeczność tego zadania.

Zmienne bilansujące i zmienna sztuczna (dla 2-go ograniczenia) zmieniają zadanie do postaci bazowej:

Początkowa tablica simpleksowa:

c^Tx→maks		x1	x2	x3	x4	x5	b
BAZA	cB	2	3	0	0	-100
x3	0	4	0	1	0	0	16
x5	-100	1	1	0	-1	1	3
cj - zj		102	103	0	-100	0

Po jednej iteracji mamy:

c^Tx→maks		x1	x2	x3	x4	x5	b
BAZA	cB	2	3	0	0	-100
x3	0	4	0	1	0	0	16
x2	3	1	1	0	-1	1	3
cj - zj		-1	0	0	3	-103

Kandydatem do bazy jest x₄, ale współczynniki przy zmiennych x₃ i x₂ są niedodatnie, zatem można dowolnie zwiększać wartość funkcji celu przez zwiększanie wartości x₂ bez naruszenia ograniczeń.

10

---