Mapa Serwisu
|
| . WSTęP |
|
Admin1 dnia marzec 15 2007 17:16:13
|
1. WSTęP
Podejmowanie decyzji jest nieodłączną częścią prowadzenia działalności gospodarczej. Z tego względu, istotne jest by były to decyzje jak najbardziej optymalne z punktu widzenia celów przedsiębiorstwa. Wiąże się to z koniecznością przyjęcia określonego kryterium, według którego dokonujemy wartościowania.
W poniższym opracowaniu starałyśmy się ukazać w sposób jasny i zrozumiały metody rozwiązywania zadań programowania liniowego z wykorzystaniem algorytmu simpleksowego. Dla szerszego zrozumienia istoty algorytmu przedstawiłyśmy w pracy trzy sposoby rozwiązywania problemów tą uniwersalną metodą. Są to:
1) metoda klasyczna,
2) metoda macierzowa,
3) program dualny.
Algorytm Simpleks można stosować do każdego modelu liniowego, mającego rozwiązanie. Wadą tego modelu jest jego pracochłonność, wymaga bowiem sporej liczby obliczeń. W pewnych przypadkach można to postępowanie nieco uprościć, co pokazałyśmy na przykładach.
2. ISTOTA METODY SIMPLEKS
Metoda simpleks jest podstawową metodą znajdowania optymalnych rozwiązań zadań programowania liniowego. Polega ona sekwencyjnym, ściśle określonym przeglądzie rozwiązań bazowych.
W metodzie simpleks stosujemy ukierunkowany przegląd zbioru rozwiązań bazowych, gdyż pełny przegląd jest w ogólnym przypadku nieefektywny, ze względu na liczbę rozwiązań oraz rozmiary każdego układu równań. W metodzie tej przechodzimy od jednego dopuszczalnego rozwiązania bazowego do drugiego, o którym wiemy, że jest nie gorsze od poprzedniego. Pomijamy więc rozwiązania bazowe niedopuszczalne oraz te, które są gorsze od aktualnie rozpatrywanego.
Chcąc uogólnić można założyć, że w tych przypadkach, w których model zawiera m równań w celu skonstruowania rozwiązania dopuszczalnego wykorzystuje się m zmiennych, którym nadaje się odpowiednie wartości dodatnie, natomiast pozostałym zmiennym nadaje się wartość zero. Procedurę obliczeniową możemy wówczas scharakteryzować następująco:
Krok 1. Wybieramy zbiór m zmiennych, które określają wstępne rozwiązania dopuszczalne. Eliminujemy wybrane m zmiennych z funkcji celu.
Krok 2. Sprawdzamy, czy w funkcji celu występuje zmienna, która we wstępnym rozwiązaniu dopuszczalnym jest równa zeru, lecz która mogłaby poprawić wartość funkcji celu, gdybyśmy nadali jej wartość dodatnią. Jeżeli taka zmienna istnieje, przechodzimy do kroku 3. W przeciwnym przypadku kończymy postępowanie.
Krok 3. Badamy jak dużą wartość dodatnią możemy nadać zmiennej określonej w kroku 2, tak, aby jedna ze zmiennych występująca w rozwiązaniu dopuszczalnym przyjęła wartość zero. Eliminujemy tę ostatnią zmienną z rozwiązania i wprowadzamy do niego nową zmienną, którą określiliśmy w kroku 2 i której nadaliśmy maksymalną z możliwych wartość dodatnią.
Krok 4. Rozwiązujemy układ warunków ograniczających względem nowego zbioru m zmiennych, przyjmując, że pozostałe zmienne w kolejnym rozwiązaniu są równe zeru. Eliminujemy zmienne o wartościach dodatnich z funkcji celu. Powracamy do kroku 2.
Zauważmy, że otrzymany w ten sposób algorytm pozwala na wyznaczenie rozwiązania optymalnego modelu programowania liniowego w skończonej liczbie iteracji (przekształceń), jeżeli tylko takie istnieje. Często metoda ta nazywana jest algorytmem simpleksowym Dantziga od nazwiska matematyka, który go zaproponował.
Rysunek 1. Schemat postępowania w algorytmie simpleks - ilustracja graficzna
Ogólna postać modelu liniowego z n zmiennymi decyzyjnymi to:
K = p X + p X + ... +p X (maksimum lub minimum),
gdzie:
K – funkcja celu czyli funkcja zmiennych decyzyjnych mierząca cel, który chce
osiągnąć decydent,
X , X ,..., X - zmienne decyzyjne,
p , p ,..., p - parametry.
Wartość tej funkcji odgrywa tu rolę kryterium to znaczy, że spośród zbioru wartości zmiennych decyzyjnych X , X ,..., X spełniających grupę warunków:
a X + a X + ... + a X b
a X + a X + ... + a X b
............................................................
a X + a X + ... + a X =b
jako rozwiązanie należy przyjąć te wartości poszczególnych zmiennych dla których funkcja K przyjmuje wartości minimum lub maksimum, co zależy od charakteru zadania.
W przypadku nierówności typu „ ” do ich lewych stron dodajemy tzw. zmienne swobodne, które stanowią początkowe rozwiązanie bazowe. W przypadku nierówności typu „ ” od lewych stron odejmujemy zmienne swobodne i dodajemy zmienne sztuczne. W tym przypadku zmienne sztuczne wchodzą do pierwszej bazy.
Do funkcji celu zmienne swobodne wchodzą ze współczynnikami równymi zero, a zmienne sztuczne z tzw. współczynnikami M, gdzie M jest liczbą bardzo dużą (M ). O ile zmienne swobodne mogą znale¼ć się w końcowym rozwiązaniu PL, o tyle zmienne sztuczne nie, dlatego w funkcji celu, która jest maksymalizowana, zmienne sztuczne występują ze współczynnikami –M, natomiast w funkcji celu, która jest minimalizowana, zmienne sztuczne występują ze współczynnikami +M.
3. WYKORZYSTANIE METODY SIMPLEKS W ZADANIACH
3.1. Przykład 1:
Określ ilość węgla, który w danej sytuacji ma zostać poddany płukaniu. W zależności od tego, czy węgiel jest płukany, czy nie, otrzymuje się różne ilości poszczególnych wymiarów:
Węgiel płukany Węgiel niepłukany
Bryły 0,1 0,3
Sortowany 0,5 -
Drobny niepłukany 0,4 0,7
Zysk na tonę w funtach 1,07 1,09
Zdolność wytwórcza kopalni wynosi 400 t/h, zdolność przerobowa płuczni 250 t/h. Chłonność rynku, jeśli chodzi o drobny węgiel niepłukany, wynosi tylko 200 t/h. Ile węgla powinno się produkować i jaką jego część poddać płukaniu, by otrzymany zysk był maksymalny?
x1 –liczba ton węgla płukanego
x2 – liczba ton węgla niepłukanego
Na podstawie danych z zadania budujemy model matematyczny (model 0):
Przekształcamy model do postaci kanonicznej, bowiem rozwiązanie bazowe wykorzystywane w metodzie simpleks wymaga zastosowania postaci kanonicznej modelu. W tym celu wprowadzamy do modelu zmienne dodatkowe x3, x4, x5 nieujemne. Przez x0 oznaczamy wartość funkcji celu. Otrzymujemy model 1:
Stosujemy krok 1. procedury obliczeniowej metody simpleks: znajdujemy wstępne rozwiązanie dopuszczalne modelu.
Najwygodniej jest wybrać rozwiązanie ze zmiennymi dodatkowymi – wstępne rozwiązanie bazowe. Zmiennymi bazowymi będą tu: x0, x3,x4, x5, gdzie:
x0 = 0,
x3 = 250,
x4 = 400,
x5 = 200.
Oczywiście zmienne x1 i x2 jako zmienne niebazowe przyjmują wartość 0.
Krok 2. procedury obliczeniowej metody simpleks:
Sprawdzamy, czy w funkcji celu występuje zmienna, która we wstępnym rozwiązaniu dopuszczalnym jest równa zeru, lecz która mogłaby poprawić wartość funkcji celu, gdybyśmy nadali jej wartość dodatnią.
W tym celu wykorzystujemy kryterium simpleksowe I:
Jeżeli w wierszu 0 występują zmienne niebazowe o współczynnikach ujemnych, to spośród nich do następnej bazy należy wybrać zmienną, przy której ujemny współczynnik ma największą wartość bezwzględną, tzn. zmienną, która zapewnia największy jednostkowy przyrost wartości funkcji celu. Jeżeli wszystkie zmienne niebazowe występujące w wierszu 0 mają współczynniki dodatnie lub =0, to rozpatrywane rozwiązanie jest rozwiązaniem optymalnym.
W naszym przypadku zmienne niebazowe x1 i x2 mają współczynniki ujemne, tak więc rozwiązanie nie jest jeszcze optymalne. Zgodnie z kryterium simpleksowym I do następnej bazy wybieramy więc zmienną x2, bowiem każdy jednostkowy przyrost zmiennej x2 wywoła przyrost wartości x0 o 1,09, czyli jest to przyrost większy niż analogiczny wywołany przez x1.
Wprowadzając do bazy nową zmienną (w naszym przypadku x2), musimy z tej bazy usunąć jedną ze zmiennych dotychczasowych. Wybór tej zmiennej jest trzecim krokiem procedury obliczeniowej metody simpleks :
Krok 3.
Badamy, jak dużą wartość dodatnią możemy nadać zmiennej określonej w kroku 2., tak, aby jedna ze zmiennych występujących w rozwiązaniu dopuszczalnym przyjęła wartość 0. Eliminujemy tę ostatnią zmienną z rozwiązania i wprowadzamy do niego nową zmienną określoną uprzednio w kroku 2.
Wybór zmiennej usuwanej z bazy następuje w oparciu o kryterium simpleksowe II:
Obliczamy ilorazy wyrazów wolnych stojących po prawej stronie równań oraz współczynników przy zmiennej wprowadzanej do bazy (pomijamy ilorazy, których mianownik jest liczbą ujemną lub zerem!). Wybieramy iloraz minimalny, a odpowiadająca mu dotychczasowa zmienna bazowa zostaje z tej bazy usunięta i w kolejnym rozwiązaniu bazowym jest równa 0.
Kryterium simpleksowe II wygodnie jest przedstawić w postaci tabeli:
Kryterium II dla zmiennej x2 wprowadzanej do bazy:
Zmienne bazowe Rozwiąz. bieżące Współcz. przy zmiennej x2 Ilorazy Min Następne rozwiąz.
x0 0 -1,09 -
x3 250 0 -
x4 400 1 400
x5 200 0,7 285,71 285,71 x2=285,71
x5=0
Tak więc do bazy wprowadzamy zmienną x2, a usuwamy z niej zmienną x5.
Krok 4.
Rozwiązujemy układ warunków ograniczających względem nowego zbioru m zmiennych, przyjmując, że pozostałe zmienne w nowym rozwiązaniu są równe 0. Eliminujemy zmienne o wartościach dodatnich z funkcji celu i powracamy do kroku 2.
Innymi słowy:
Przepisujemy nasz otrzymany uprzednio model w postaci kanonicznej (model 1) tak, by zmienna wprowadzana do bazy (w naszym przypadku x2) miała takie współczynniki w odpowiednich wierszach, jakie w tych samych wierszach miała zmienna usuwana obecnie z bazy (x5). Czyli zmienna x2 w wierszu trzecim ma mieć współczynnik 1, a w pozostałych wierszach – współczynnik 0. Przekształcenie modelu następuje za pomocą operacji elementarnych.
Otrzymujemy model 2:
Model otrzymano za pomocą operacji elementarnych:
Wiersz 0: wiersz 3 z modelu 2 pomnożono przez 1,09 i dodano do wiersza 0
Wiersz 1: bez zmian
Wiersz 2: wiersz 3 z modelu 2 pomnożono przez (-1) i dodano do wiersza 2
Wiersz 3: wiersz 3 z modelu 1 podzielono przez 0,7
Obecne dopuszczalne rozwiązanie bazowe tworzą zmienne:
x0 = 311,429
x3 = 250
x4 = 114,286
x2 = 285,714
Nadal możemy zwiększyć x0 (nasz zysk, który ma być maksymalnie duży), zwiększając x1, bowiem jest to ostatnia już zmienna niebazowa ze współczynnikiem ujemnym w wierszu 0. Wybieramy więc zmienną x1 do nowej bazy (na podstawie kryterium simpleksowego I).
Szukając zmiennej, którą należy usunąć z bazy, posługujemy się kryterium simpleksowym II:
Kryterium II dla zmiennej x1 wprowadzanej do bazy:
Zmienne bazowe Rozwiąz. bieżące Współcz. przy zmiennej x1 Ilorazy Min Następne rozwiąz.
x0 311,429 -0,447 -
x3 250 1 250 250 x1 = 250
x3 = 0
x4 114,286 0,428 266,67
x2 285,714 0,571 500
Tak więc do bazy wprowadzamy zmienną x1, a usuwamy z niej zmienną x3.
Realizując krok 4 przekształcamy uprzednio uzyskany model (model 2) za pomocą operacji elementarnych tak, by w nowym modelu zmienna x1 miała takie współczynniki, jakie miała zmienna x3 w poszczególnych wierszach modelu 2.
Otrzymujemy model 3 :
Model otrzymano za pomocą operacji elementarnych:
Wiersz 0: wiersz 1 pomnożono przez 0,47 i dodano do wiersza 0 (modelu 2)
Wiersz 1: bez zmian
Wiersz 2: wiersz 1 pomnożono przez (-0,428) i dodano do wiersza 2 (modelu 2)
Wiersz 3: wiersz 1 pomnożono przez (-0,571) i dodano do wiersza 3 (modelu 2)
Wszystkie współczynniki otrzymane w wierszu 0 są nieujemne, co zgodnie z kryterium I świadczy o tym, że otrzymane rozwiązanie jest optymalne.
Wartości:
x0 = 423,2
x1 = 250
x2 = 142,964
x4 = 7,286
spełniają układ równań modelu 1.
Odpowied¼: Zysk maksymalny jest realizowany, gdy produkuje się 393,2 tony węgla na godzinę, z czego płukaniu poddaje się 250 ton węgla na godzinę.
Ponieważ nasze zadanie jest zadaniem dwuwymiarowym, polegającym na znalezieniu takich nieujemnych wartości dowolnej pary x1 i x2, które maksymalizują zysk (nasze x0) i dla których równania modelu 1 są spełnione przy nieujemnych x3, x4 i x5, możemy przedstawić rozwiązanie także graficznie:
Legenda:
Prosta 1: 1,07x1 + 1,09x2 = 0
Prosta 2: x1+x2 = 400
Prosta 3: 0,4x1 + 0,7 x2 = 200
Prosta 4: x1 = 250
Wykres potwierdza, że rozwiązaniem optymalnym jest punkt B o współrzędnych: x1 = 250, x2 = 142,964
Metoda graficzna uwidacznia, że rozwiązanie optymalne leży na wierzchołku, co oznacza, że jest dopuszczalnym rozwiązaniem bazowym.
Istnieje także możliwość przedstawienia algorytmu simpleksowego w ujęciu tabelarycznym:
Iteracja Baza Wart. zmiennych bazowych X1 X2 X3 X4 X5 Wiersz
1 X0 0 -1,07 -1,09 0 0 0 0
X3 250 1 0 1 0 0 1
X4 400 1 1 0 1 0 2
X5 200 0,4 0,7 0 0 1 3
2 X0 311,42 -0,447 0 0 0 1,557 0
X3 250 1 0 1 0 0 1
X4 114,29 0,43 0 0 1 -1,43 2
X2 285,71 0,57 1 0 0 1,43 3
3 X0 423,2 0 0 0,45 0 1,56 0
X1 250 1 0 1 0 0 1
X2 142,964 0 1 -0,57 0 1,43 3
X4 7,286 0 0 -0,43 1 -1,43 2
¬ródło: opracowanie własne
3.2. Przykład 2:
Przedsiębiorstwo ,,Vena’’ produkuje dwa wyroby: W1-torbę skórzaną dużą i W2-torbę małą. Do produkcji tych wyrobów zużywa się m.in. dwa limitowane surowce: skórę-S1 oraz metalu-S2. Zużycie tych surowców na jednostkę każdego z wyrobów, dopuszczalne limity zużycia surowców oraz zyski jednostkowe ze sprzedaży wyrobów podano w tabeli.
Wyroby
Zużycie na jednostkę wyrobu surowca Zysk jednostkowy
S1 S2
W1
W2 12
4 8
8 50
10
Limit zużycia surowca 480 640
Ile należy produkować wyrobu W1 a ile W2, aby nie przekraczając limitów zużycia surowców zmaksymalizować zysk ze sprzedaży wyrobów? Zbudować model matematyczny.
Rozwiązanie:
W modelu matematycznym opisującym przedstawioną sytuację decyzyjną występują dwie zmienne decyzyjne:
x1 -oznacza wielkość produkcji wyrobu W1
x2- oznacza wielkość produkcji wyrobu W2
Model ten ma postać:
50x1 + 10x2 max
12x1 + 4x2 480
8x1 + 8x2 640
x1, x2 0
Model zostanie rozwiązany za pomocą algorytmu simplex. Sprowadzamy go do postaci kanonicznej, dodając do lewych stron nierówności (które są mniejsze) zmienne swobodne: x3, x4. A zatem:
50x1 + 10x2 + 0x3 + 0x4 max
12x1 + 4x2 + 1x3 + 0x4 =480
8x1 + 8x2 + 0x3 + 1x4 = 640
Zmienną swobodną x3 możemy traktować jako niewykorzystany zasób surowca S1, natomiast
zmienną swobodną x4 możemy traktować jako niewykorzystany zasób surowca S2.
Tablica simpleksowa dla początkowego rozwiązania bazowego ma postać tablicy:
Tablica simpleksowa I:
cb cj
50 10 0 0 Rozwiązanie
Zmienne bazowe x1 x2 x3 x4
0
0 x3
x4 12
8 4
8 1
0 0
1 480
640
zj
0 0 0 0 0
cj-zj
50 10 0 0
Wartość zj dla poszczególnych zmiennych (kolumn) I tablicy można obliczyć jako sumę iloczynów współczynników odpowiadających poszczególnym zmiennym przez współczynnik funkcji celu dla zmiennych bazowych (kolumna cb), czyli zj= .
Następnie sprawdzamy czy dane dopuszczalne rozwiązanie bazowe jest optymalne-jest ono optymalne, gdy wska¼niki kryterium simpleks dla zmiennych niebazowych są niedodatnie (w zadaniu na maksimum) czyli cj - zj 0.
Poszczególne elementy zapisu macierzowego zadania są następujące:
A = I = b = c = xb = cb =
W przypadku maksymalizacji funkcji celu do kolejnego rozwiązania bazowego wchodzi zmienna o największej wartości kryterium simpleks (czyli o największej wartości w tzw. wierszu zerowym cj - zj = max ).
Tak więc w drugiej iteracji do bazy wchodzi zmienna x1 [max (cj -zj ) = 50]. Aby ustalić w miejsce której z dotychczasowych zmiennych bazowych ją wprowadzić, należy podzielić wartości zmiennych bazowych ( bi ) przez współczynniki stojące przy wprowadzanej zmiennej w aktualnej tablicy simpleksowej i wybrać zmienną, dla której ten iloraz jest najmniejszy. W tym przypadku spośród dwóch ilorazów: 480: 12 = 40, 640: 8 = 80 najmniejszy odpowiada zmiennej x3. A zatem w drugiej iteracji x1 wchodzi do bazy w miejsce x3, a w tablicy simpleksowej zmiennymi bazowymi są: x1, x4. Dla takiej bazy
macierz B (macierz współczynników stojących przy aktualnych w danej iteracji zmiennych bazowych w I tablicy simpleksowej) ma postać:
B = det B = =12
B-1 = = = - elementy x3, x4 w II tablicy simpleksowej
B-1 A = = - elementy x1, x2 w II tablicy simpleksowej
B-1 b = = - wektor wartości zmiennych bazowych
Tablica simpleksowa II:
cb cj
50 10 0 0 Rozwiązanie
Zmienne bazowe x1 x2 x3 x4
50
0 x1
x4 1
0
0
1 40
320
zj
50
0 2000
cj-zj
0 -
-
0
cbT B-1 = = -elementy wiersza zj w kolumnie x3, x4
cbT B-1 A = = -elementy wiersza zj w kolumnie x1, x2
cbT B-1b = = 2000 – wartość funkcji celu
Optymalne rozwiązanie zadania to:
xb = =
czyli x1= 40, x4= 320, F(x1,x2)=2000
Odpowied¼: Aby zmaksymalizować zysk ze sprzedaży należy wyprodukować 40 sztuk dużych toreb oraz 0 sztuk małych. Wartość zmiennej x4 oznacza, że przy takim rozwiązaniu zostaje niewykorzystany zasób surowca S2, czyli metalu.
3.3. Przykład 3:
Przedsiębiorstwo kosmetyczne ,,NIVEA” produkuje 2 wyroby: krem przeciwzmarszczkowy-W1 i krem nawilżający na dzień-W2. Ograniczeniem w procesie produkcji są zapasy trzech surowców: wody-S1, gliceryny-S2 i koenzymu Q10-S3. W tablicy podano jednostkowe nakłady surowców na produkcję wyrobów, zapasów oraz ceny wyrobów. Ustalić rozmiary produkcji kremów, które gwarantują maksymalny przychód ze sprzedaży przy istniejących zapasach surowców.
Surowce Zużycie surowca na 1 szt. wyrobu
Zapas surowca
W1 W2
S1
S2
S3 2
3
1,5 1
3
- 1000
2400
600
Cena 30 20
Na podstawie tego przykładu przedstawimy program dualny, który ma postać:
1000y1 + 2400y2 + 600y3 → min
2y1 + 3y2 + 1,5y3 ≥ 30
y1 + 3y2 ≥ 20
y1, y2, y3 ≥ 0
Aby rozwiązać zadanie metodą simpleks, należy je sprowadzić do postaci bazowej z nieujemnym wektorem wyrazów wolnych b, przyjmując wówczas, że zmiennymi bazowymi są zmienne związane z wektorami jednostkowymi, uzyskujemy początkowe rozwiązanie bazowe:
xB = b, xN = 0
W przypadku gdy i-ty wyraz wolny jest ujemny, mnożymy odpowiadające mu i-te
równanie obustronnie przez (-1). W przypadku, gdy macierz współczynników postaci kanonicznej nie zawiera macierzy jednostkowej można wówczas sztucznie utworzyć taką macierz, uzupełniając macierz współczynników A o odpowiednią liczbę brakujących wektorów jednostkowych. Jest to metoda sztucznej bazy. W ślad za wprowadzonymi wektorami jednostkowymi rozszerzamy listę zmiennych o tzw. zmienne sztuczne.
Waga przy zmiennej sztucznej jest taka, że nieopłacalne jest pozostawienie tej zmiennej w rozwiązaniu optymalnym. Jest to bardzo duża liczba dodatnia dla zadania na minimum oraz liczba ujemna, duża co do modułu, w zadaniu na maksimum.
Stosowanie zmiennych sztucznych jest metodą rachunkową mającą na celu szybkie uzyskanie początkowego rozwiązania bazowego. Wprowadzając je, uzyskujemy nowe, równoważne, pomocnicze zadanie PL. Optymalne rozwiązanie zadania pomocniczego wyznacza optymalne rozwiązanie zadania wyjściowego, o ile wszystkie zmienne sztuczne w rozwiązaniu optymalnym są zerowe. Jeżeli natomiast chociaż jedna zmienna jest dodatnia, to wyjściowe zadanie jest sprzeczne.
Ponieważ w układzie warunków ograniczających występują nierówności "≥", aby je sprowadzić do postaci liniowej, należy od lewych stron nierówności odjąć zmienne swobodne y4 i y5 i dodać zmienne sztuczne (odpowiednio s1 i s2). Jeżeli w modelu występują warunki równościowe, do nich również wprowadzamy zmienną sztuczną, która wchodzi do pierwszej bazy, ale jak wiadomo, nie może znale¼ć się w rozwiązaniu optymalnym. Zauważmy jeszcze, że s1 = -y4, a s2 = -y5.
Postać kanoniczna programu dualnego jest następująca:
1000y1 + 2400y2 + 600y3 + 0y4 + 0y5 + Ms1 + Ms2 → min
2y1 + 3y2 + 1,5y3 - y4 + s1 = 30
y1 + 3y2 - y5 + s2 = 20
Korzystając z zapisu macierzowego otrzymujemy:
, , , , .
Pierwsza tablica simpleksowa ma więc postać:
Tablica simpleksowa I:
cb cj 1000 2400 600 0 0 M M Rozwiązanie
Zmienne bazowe y1 y2 y3 y4 y5 s1 s2
M s1 2 3 1,5 -1 0 1 0 30
M s2 1 3 0 0 -1 0 1 20
zj 3M 6M 1,5M -M -M M M 50M
cj-zj 1000-3M 2400-6M 600-1,5M M M 0 0
Jak widać, największym ujemnym kryterium simpleks charakteryzuje się zmienna y2, ona zatem wejdzie do bazy w kolejnej iteracji, w miejsce zmiennej s2:
(min{30:3; 20:3} = 20/3, co odpowiada zmiennej s2).
Dokonując obliczeń na macierzach uzyskamy elementy II tablicy simpleksowej:
, ,
to elementy kolumn zmiennych sztucznych s1 i s2
to elementy kolumn zmiennych decyzyjnych
to wartości zmiennych bazowych
, to elementy wiersza zj dla kolumn s1 i s2.
to elementy wiersza zj dla kolumn y1, y2, y3.
to wartość funkcji celu.
W rezultacie tablica simpleks dla II iteracji przybierze postać:
Tablica simpleksowa II:
cb cj 1000 2400 600 0 0 M M Rozwiązanie
zmienne bazowe y1 y2 y3 y4 y5 s1 s2
M s1 1 0 1,5 -1 1 1 -1 10
2400 y2 1/3 1 0 0 -1/3 0 1/3 20/3
zj 800+M 2400 1,5M -M M-800 M 800-M 16000M+10M
cj-zj 200-M 0 600-1,5M M 800-M 0 -800+M
Obecnie największy spadek wartości funkcji celu można uzyskać wprowadzając do kolejnej bazy zmienną y3 w miejsce s1:
(10/1,5 = 20/3; 20/3:0 → ∞)
Posługując się rachunkiem macierzowym obliczamy elementy III tablicy simpleksowej:
, , , ,
to elementy kolumn zmiennych sztucznych s1 i s2
to elementy kolumn zmiennych decyzyjnych
wartości zmiennych bazowych
elementy wiersza zj dla kolumn s1, s2
elementy wiersza zj dla kolumn y1, y2, y3
wartość funkcji celu
Tablica simpleks dla trzeciej iteracji ma postać:
Tablica simpleksowa III:
cb cj 1000 2400 600 0 0 M M Rozwiązanie
zmienne bazowe y1 y2 y3 y4 y5 s1 s2
600 y3 2/3 0 1 -2/3 2/3 2/3 -2/3 20/3
2400 y2 1/3 1 0 0 -1/3 0 1/3 20/3
zj 1200 2400 600 -400 -400 400 400 20000
cj-zj -200 0 0 400 400 M-400 M-400
Rozwiązanie nadal nie jest optymalne, ponieważ w wierszu zerowym występuje jeszcze element ujemny, co oznacza, że wartość funkcji celu można zmniejszyć wprowadzając do kolejnej bazy zmienną y1. Zauważmy, że M → ∞, zatem M - 400 ≈ ∞ i zmienne sztuczne nie mogą wejść do kolejnych rozwiązań bazowych. Ponieważ:
min{20/3 : 2/3; 20/3 : 1/3} = 10, co odpowiada wierszowi y3.
Zatem w kolejnej tablicy zmiennymi bazowymi są y1 i y2.
Posługując się rachunkiem macierzowym obliczono poszczególne elementy tablicy simpleksowej IV:
to elementy kolumn zmiennych sztucznych s1 i s2.
to elementy kolumn zmiennych decyzyjnych y1, y2, y3.
to wartości zmiennych bazowych (rozwiązanie)
więc to elementy wiersza zj dla kolumn s1 i s2.
to elementy wiersza zj dla kolumn y1, y2, y3.
to wartość funkcji celu.
Optymalne rozwiązanie programu dualnego jest zatem następujące:
y1*=10, y2*=10/3, F(y1*, y2*) = 18000
Zauważmy jeszcze, że z ostatniej tablicy simpleksowej można odczytać także rozwiązanie optymalne programu dualnego. Mianowicie, optymalne wartości zmiennych decyzyjnych programu dualnego są równe wartościom bezwzględnym liczb występujących w wierszu zerowym (cj - zj) ostatniej tablicy simpleksowej, odpowiadających zmiennym swobodnym programu pierwotnego:
y1* =│-10│= 10
y2* =│-10/3│= 10/3
y3* = 0
Analogicznie, wartości zmiennych decyzyjnych programu pierwotnego są równe wartościom bezwzględnym liczb występujących w wierszu zerowym ostatniej tablicy simpleksowej programu dualnego, odpowiadających zmiennym swobodnym tego programu:
x1* =│200│= 200
x2* =│600│= 600
Tablica simpleksowa IV
cb cj 1000 2400 600 0 0 M M Rozwiązanie
zmienne bazowe y1 y2 y3 y4 y5 s1 s2
1000 y1 1 0 1,5 -1 1 1 -1 10
2400 y2 0 1 -0,5 1/3 -2/3 -1/3 2/3 10/3
zj 1000 2400 300 -200 -600 200 600 18000
cj-zj 0 0 300 200 600 -200+M -600+M
Obecnie wszystkie zmienne niebazowe mają dodatnie kryterium simpleks, a więc wartości funkcji celu nie da się już zmniejszyć
4. ZUPE£NOŁć ALGORYTMU
Niekiedy zastosowanie kryteriów I (dotyczącego wyboru zmiennej wprowadzanej do bazy) i II (odnoszącego się do wyboru zmiennej usuwanej z bazy) algorytmu simpleksowego może przysporzyć trudności w podjęciu decyzji, którą ze zmiennych należy wprowadzić lub usunąć z bazy.
Gdy w kryterium I, wartości dwóch lub więcej zmiennych mają jednakowe wartości współczynników w wierszu zero, można np. wybrać zmienną o mniejszym numerze lub zmienną, która wydaje nam się, iż ma większe predyspozycje do wystąpienia w optymalnej bazie.
Gdy w kryterium II, dwie lub więcej zmiennych z aktualnej bazy przyjmują wartości zerowe po wprowadzeniu nowej zmiennej, to należy tylko jedną z nich usunąć z bazy. Pozostałe zostawiamy, mimo iż są zerowe. Bazę, którą otrzymamy, nazywamy bazą zerową. Teoretycznie możliwe jest powstanie cyklu, czyli ciągu rozwiązań, który będzie się stale powtarzał. W praktyce jednak degeneracja rozwiązania bazowego albo zanika, albo kolejne rozwiązanie zdegenerowane okazuje się rozwiązaniem optymalnym.
Gdy stosując kryterium II, w pewnej iteracji nie będzie ani jednego dodatniego współczynnika w każdym wierszu przy zmiennej wprowadzanej do bazy, to nie istnieje skończone rozwiązanie optymalne i funkcja celu jest nieograniczona. Wtedy też zmienna wprowadzana do bazy może przyjąć dowolnie duże wartości, co powoduje, że wartość x wzrasta nieograniczenie, a aktualne zmienne bazowe pozostają nieujemne. To właśnie pozwala na odrzucenie założenia, że optymalna wartość funkcji celu jest skończona. Algorytm simpleks zawiera więc kryterium oceny sygnalizujące, w którym przypadku wartość funkcji celu jest nieograniczona.
5. ZAKRES STOSOWALNOŁCI ALGORYTMU
W wielu modelach programowania liniowego funkcja celu jest minimalizowana. Zagadnienia z minimalizacją funkcji celu mogą być rozwiązywane metodą zmiany znaków współczynników w funkcji celu. Wówczas kryterium I (maksymalizacji) może być stosowane do przeformułowanej postaci funkcji celu.
W zadaniu programowania liniowego, gdzie funkcja celu jest minimalizowana, możemy też po prostu skorzystać z kryterium minimalizacji. Wówczas, gdy wśród zmiennych niebazowych występują zmienne ze współczynnikami ujemnymi w wierszu zero, to do bazy wprowadzamy tę z nich, która ma największy współczynnik ujemny. Jeżeli wszystkie zmienne niebazowe w wierszu zero mają współczynniki dodatnie lub równe zeru, to wyznaczone rozwiązanie jest rozwiązaniem optymalnym.
6. ZAKOńCZENIE
Algorytm simpleks jest procedurą etapową, a wyniki poszczególnych etapów zestawia się w kolejnych tablicach simpleksowych. Rozwiązanie wyznaczone w końcowej iteracji jest rozwiązaniem dokładnym. Postępowanie kończy się w momencie stwierdzenia, że aktualne rozwiązanie bazowe jest optymalne.
Zawarte przykłady w sposób jednoznaczny pokazują, że najmniej pracochłonnym sposobem wykorzystania algorytmu simpleks jest rozwiązywanie zadań PL za pomocą metody eliminacji Gaussa. Metoda macierzowa, choć bardzo uciążliwa rachunkowo, jest szeroko wykorzystywana w praktyce z uwagi na jej zastosowanie przy użyciu oprogramowania komputerowego. Pozwala ona na rozwiązywanie trudnych i złożonych problemów w badaniach operacyjnych.
Prostota oraz powtarzalność algorytmu simpleks powoduje, że może on mieć zastosowanie do rozwiązania każdego zadania optymalizacji liniowej, co czyni zeń metodę uniwersalną.
BIBLIOGRAFIA:
Ignasiak E. (red.), Badania operacyjne,
Kukuła K. (red.), Badania operacyjne w przykładach i zadaniach,
Mitchell G.H., Badania operacyjne. Metody i przykłady,
Sadowski A, Teoria podejmowania decyzji,
Wagner H.M., Badania operacyjne.
|
|
|
Zaloguj się, żeby móc dodawać komentarze.
|
|
|
Dodawanie ocen dostępne tylko dla zalogowanych Użytkowników.
Proszę się zalogować lub zarejestrować, żeby móc dodawać oceny.
Brak ocen.
|
|
|
|
