Simlpex.doc

Praca pochodzi z serwisu www.e-sciagi.pl

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 = pX + pX + ... +pX (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:

aX + aX + ... + aX b

aX + aX + ... + aX b

............................................................

aX + aX + ... + aX=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:

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

(wiersz 0)

(wiersz 1)

(wiersz 2)

(wiersz 3)

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:

(wiersz 0)

(wiersz 1)

(wiersz 2)

(wiersz 3)

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: