Przedmiot: Ekonometria

Ekonometria - metoda simplex (14 stron)

Pobierz ten dokument Wróć do kategorii

schematy i tabele w pliku do pobrania.

Metoda simpleks w planowaniu liniowym.
Założenia metody simpleks.
Bazowy plan zadania w metodzie simpleks.
Tablica simpleks. Przekształcenia tablicy simpleks.
Kryterium optymalności planu.
Przykład rozwiązania zadania planowania liniowego metodą simpleks.
Ćwiczenie 3. Rozwiązanie metodą simpleks zadania planowania liniowego.
Zadania.
Ćwiczenie 4. Rozwiązanie metodą simpleks zadania planowania liniowego w Excel’u.
Zadania.

Założenia metody simpleks.

W związku z głównym twierdzeniem planowania liniowego naturalnie powstaje pomysł o następującej możliwości rozwiązywania ZPL z dowolną ilością zmiennych: obliczyć wszystkie wierzchołkowe punkty wielościanu planów (będzie ich nie więcej niż , gdzie n – ilość zmiennych xi, r jest rangą macierzy układu ograniczeń) i zatem należy porównać wartości celowej funkcji w tych wierzchołkowych punktach. Takie dojście do rozwiązania nawet ze stosunkowo niedużą ilością zmiennych i ograniczeń jest praktycznie niemożliwe, tak jak proces obliczenia wierzchołkowych punktów może być porównany według ciężkości z rozwiązaniem całego zadania. Do tego trzeba dodać, że ilość wierzchołkowych punktów planów może okazać się bardzo duża. W związku z tymi problemami powstaje zadanie racjonalnego sprawdzenia wierzchołkowych punktów. Jego istota jest następująca. Jeżeli jest znany jakikolwiek wierzchołkowych punkt i wartość w tym punkcie celowej funkcji, wtedy wszystkie wierzchołkowe punkty, w których celowa funkcja przyjmuje gorsze wartości nie są potrzebne. Stąd rzeczywiście potrzebujemy znaleźć sposób przejścia od danego wierzchołkowego punktu do punktu znajdującego się na jednej krawędzi z danym punktem, ale w którym celowa funkcja osiąga lepsze wartości, a zatem przejścia do jeszcze lepszego punktu itd. Więc potrzebujemy warunku, że niektóry wierzchołkowy punkt jest najlepszy z wszystkich wierzchołkowych punktów pod względem odpowiednich wartości celowej funkcji. Na tym bazuje się ogólna idea najbardziej rozpowszechnionej w teraźniejszym czasie simpleks metody (metoda kolejnego ulepszenia planu) dla rozwiązania ZPL.
I tak, w algebraicznych terminach simpleksowa metoda zawiera:
1) umiejętności znalezienia początkowego dopuszczalnego planu;
2) obecność warunku optymalności dopuszczalnego planu;
3) umiejętności przechodzenia do nie gorszego (pod względem wartości celowej funkcji) dopuszczalnego planu.

Bazowy plan zadania w metodzie simpleks.

Niech ZPL jest przedstawione jako układ ograniczeń w kanonicznej postaci:
ai1*x1+ai2*x2+ ... + ain*xn = bi, lub , (i=1, 2,...m) (3.1)
xj ł 0, j=1,2, ... n (3.2)

Definicja. Mówią, że ograniczenie ZPL ma najodpowiedniejszą postać, jeżeli dla nieujemnej prawej strony (bi ł 0) lewa strona ograniczenia zawiera zmienną, która ma współczynnik równy jedynce, a w pozostałych ograniczeniach - równościach zmienna ma współczynnik równy zeru.
Na przykład, w układzie ograniczeń

pierwsze i trzecie ograniczenia mają najodpowiedniejszą postać, drugie i czwarte nie mają.
Jeżeli każde ograniczenie ZPL w kanonicznej postaci ma najodpowiedniejszą postać, wówczas mówią, że układ ograniczeń ma najodpowiedniejszą postać. W tym przypadku łatwo znaleźć jego bazowy plan: wszystkie swobodne zmienne można porównać do zera, wówczas bazowe zmienne będą równe wolnym wyrazom.
Przyrównanie najodpowiedniejszych zmiennych do prawych stron daje bazowe rozwiązanie, tj. wierzchołek wielościanu rozwiązań. Dlatego najodpowiedniejsze zmienne są bazowymi. Zmienne porównane do zera są wolnymi.
Niech układ ograniczeń ma postać
ai1*x1+ai2*x2+ ... + ain*xn Ł bi, lub , (i=1, 2,...m), bi ł 0 (3.3)
(Takie ograniczenia mają ZPL o najlepszym wykorzystaniu zasobów, technologii itd.). Przekształćmy zadanie do kanonicznej postaci. Dlatego dodamy do lewych stron nierówności dodatkowe zmiennie xn+i ł 0 (i=1, 2, ... m). Otrzymamy jak było pokazane wyżej, ekwiwalentny układ:
, (i=1, 2,...m) (3.4)
który ma najkorzystniejszą postać. I więc początkowy bazowy plan przyjmie postać

Do celowej funkcji dodatkowe zmienne wprowadzajmy ze współrzędnymi równymi zeru:
сn+i = 0 (i = 1, 2, ... m).

Niech teraz układ ograniczeń ma postać
ai1*x1+ai2*x2+ ... + ain*xn ł bi, lub , (i=1, 2,...m), bi ł 0 (3.5)
Sprowadzimy jego do ekwiwalentnego układu odejmując dodatkowe zmienne xn+i ł 0 (i=1, 2, ... m) z lewych stron nierówności ograniczeń. Otrzymamy układ
, (i=1, 2,...m). (3.6)
Teraz układ ograniczeń nie ma najkorzystniejszej postaci, bo dodatkowe zmienne xn+i wchodzą w lewą stronę (dla bi ł 0) ze współczynnikami równymi -1. Dlatego, ogólnie mówiąc, bazowy plan

nie jest dopuszczalny. Więc wprowadzamy sztuczną bazę, to znaczy do już wprowadzonych m zmiennych dodatkowych jeszcze kilka zmiennych. Do lewych stron ograniczeń równości, nie mających najkorzystniejszej postaci, dodajemy sztuczne zmienne wi. Do celowej funkcji zmienne wi wchodzą ze współczynnikami równymi М w przypadku rozwiązania zadania, w którym obliczamy minimum i ze współczynnikami -М w przypadku rozwiązania zadania, w którym obliczamy maksimum, gdzie М jest dużą dodatnią liczbą (na przykład w 20 razy większa niż największa wartość bezwzględna danych zadania). Otrzymane zadanie nazywa się М-zadaniem, odpowiednim wejściowemu. Ono zawsze ma najodpowiedniejszą postać.
Niech wejściowe ZPL ma postać

max (min) Z = c1*x1+c2*x2+ ... + cn*xn , lub (3.7)
ai1*x1+ai2*x2+ ... + ain+m*xn+m = bi, lub , bi ł 0 (i=1, 2,...m) (3.8)
xj ł 0, j=1,2, ... n (3.9)
zakładamy również, że żadne z ograniczeń nie ma najodpowiedniejszej zmiennej. Wtedy M - zadanie możemy zapisać w postaci:
(3.10)
, bi ł  (i=1, 2,...m) (3.11)
xj ł 0, j=1,2, ... n; wi ł 0, i=1,2, ... m, (3.12)
gdzie znak «-» w funkcji (3.10) zapisujemy w przypadku obliczenia maksimum, znak «+» w funkcji (3.10) zapisujemy w przypadku obliczenia minimum. Zadanie (3.10) — (3.12) ma najodpowiedniejszą postać. Jego początkowy bazowy plan jest
.
Jeżeli niektóre z równań (3.8) mają najodpowiedniejszą postać, to dla nich nie potrzeba wprowadzić sztucznych zmiennych.
Twierdzenie Jeżeli w optymalnym planie

М-zadania (3.10) — (3.12) wszystkie sztuczne zmienne wi = 0 (i = 1, 2, ... m), wtedy plan

jest optymalnym planem wejściowego zadania (3.7) — (3.9).

Żeby rozwiązać zadanie z ograniczeniami, które nie mają najodpowiedniejszej postaci, wprowadzamy sztuczną bazę i rozwiązujemy rozszerzone М - zadanie, mające początkowy bazowy plan

Rozwiązanie wejściowego zadania simpleks metodą z wykorzystaniem sztucznych zmiennych wi nazywa się simpleks metodą ze sztuczną bazą.
Jeżeli w wyniku zastosowania simpleks metody do rozszerzonego zadania otrzymujemy optymalny plan, w którym wszystkie sztuczne zmienne w* = 0, to jego pierwsze n komponenty dają optymalny plan wejściowego zadania.
Twierdzenie Jeżeli w optymalnym planie М - zadania co najmniej jedna sztuczna zmienna nie jest równa zeru, to wejściowe zadanie nie ma dopuszczalnych rozwiązań, tj. jego układ ograniczeń jest sprzeczny.

Tabela simpleks.

Dowolne ZPL postaci (3.7)-(3.9), jak było pokazano wyżej, po niektórych przekształceniach można zapisać w ekwiwalentnej najkorzystniejszej postaci:
(3.13)
, (3.14)
xj ł 0, j=1,2, ... n; (3.15)
Zapiszemy bazowe zmienne x1, x2, ..., xm z równości (3.14) przez swobodne xm+1, xm+2, ... , xm+n i podstawimy je do celowej funkcji. Po zgrupowaniu podobnych członków otrzymamy
Z=(c1*1 + c2*2+ ... + cm*m) – ((c1*1,m+1 + c2*2,m+1 + ... + cm*m,m+1 - cm+1)*xm+1 +(c1*1,m+2 + c2*2,m+2 + ... + cm*m,m+2 – cm+2)*xm+2 + ... + (c1*1,n + c2*2,n + ... + cm*m,n – cn)*xn) (3.16)
Wprowadzimy oznaczenia:
0 = c1*1 + c2*2 + ... + cm*m =cB*Ao (3.17)
j = c1*1j + c2*2j + ... + cm*mj - cj =cB*Aj - cj , j=m+1, m+2, ..., n , (3.18)
gdzie cB = (c1 ; c2 ; ... cm) jest wektorem współczynników celowej funkcji dla bazowych zmiennych; Ao = (1 ; 2 ; ... m ) jest wektorem – kolumną wolnych wyrazów; Aj = (1j ; 2j ... mj ) jest wektorem – kolumną współczynników zmiennych хj. Biorąc pod uwagę równości (3.16) — (3.18), zadanie (3.13) — (3.15) przyjmie postać:
max (min) Z = 0 - (3.19)
xi+ , i ł 0 (i=1, 2,...m), (3.20)
xj ł 0, j=1,2, ... n; (3.21)
gdzie 0 = cB*Ao , j =cB*Aj - cj , j=m+1, m+2, ..., n.
Zadanie (3.19) — (3.21) zapisujemy w tabelę, która nazywa się tabela simpleks (tab. 3.1). Ostatni, (m+1)-szy, wiersz nazywa się indeksowym wierszem (wierszem celowej funkcji), liczba 0 = cB*Ao jest wartością celowej funkcji dla początkowego bazowego planu xо, tj. Ao = z(xo) = cB*Ao. Liczby j =cB*Aj - cj , () nazywają się ocenami swobodnych zmiennych.
Twierdzenie Niech w wejściowym zadaniu obliczamy maksimum. Jeżeli dla niektórego bazowego planu wszystkie oceny j, są nieujemne, to taki plan jest optymalny.
Dowód. Mamy Z = 0 - i to, że j ł 0 (j=m+1, m+2, ..., n), więc Z osiągnie maksymalną wartość dla =0. To będzie możliwe tylko dla xm+1=0, xm+2=0, ... , xn=0, tj. bazowy plan jest optymalny.
Twierdzenie Niech w wejściowym zadaniu obliczamy minimum i dla bazowego planu wszystkie oceny j, (j=m+1, m+2, ..., n) są nie dodatne, to taki plan jest optymalny.
Dowód jest analogiczny do poprzedniego twierdzenia.

Tabela 3.1.
Bazowe zmienne cB A0 x1 x2 ... xi ... xm xm+1 ... xj ... xn
c1 c2 ... ci ... cm cm+1 ... cj ... cn
x1 c1 1 1 0 ... 0 ... 0 1,m+1 ... 1,j ... 1,n
x2 c2 2 0 1 ... 0 ... 0 2,m+1 ... 2,j ... 2,n
... ... ... ... ... ... ... ... ... ... ... ... ... ...
xi ci i 0 0 ... 1 ... 0 i,m+1 ... i,j ... i,n
... ... ... ... ... ... ... ... ... ... ... ... ... ...
xm cm m 0 0 ... 0 ... 1 m,m+1 ... m,j ... m,n
zi - ci  0 0 ... 0 ... 0 m ... j ... n

Prze adania otrzymujemy optymalny plan, w którym wszystkie sztuczne zmienne w* = 0, to jego pierwsze n komponenty dają optymalny plan wejściowego zadania.
Twierdzenie Jeżeli w optymalnym planie М - zadania co najmniej jedna sztuczna zmienna nie jest równa zeru, to wejściowe zadanie nie ma dopuszczalnych rozwiązań, tj. jego układ ograniczeń jest sprzeczny.

Tabela simpleks.

Dowolne ZPL postaci (3.7)-(3.9), jak było pokazano wyżej, po niektórych przekształceniach można zapisać w ekwiwalentnej najkorzystniejszej postaci:
(3.13)
, (3.14)
xj ł 0, j=1,2, ... n; (3.15)
Zapiszemy bazowe zmienne x1, x2, ..., xm z równości (3.14) przez swobodne xm+1, xm+2, ... , xm+n i podstawimy je do celowej funkcji. Po zgrupowaniu podobnych członków otrzymamy
Z=(c1*1 + c2*2+ ... + cm*m) – ((c1*1,m+1 + c2*2,m+1 + ... + cm*m,m+1 - cm+1)*xm+1 +(c1*1,m+2 + c2*2,m+2 + ... + cm*m,m+2 – cm+2)*xm+2 + ... + (c1*1,n + c2*2,n + ... + cm*m,n – cn)*xn) (3.16)
Wprowadzimy oznaczenia:
0 = c1*1 + c2*2 + ... + cm*m =cB*Ao (3.17)
j = c1*1j + c2*2j + ... + cm*mj - cj =cB*Aj - cj , j=m+1, m+2, ..., n , (3.18)
gdzie cB = (c1 ; c2 ; ... cm) jest wektorem współczynników celowej funkcji dla bazowych zmiennych; Ao = (1 ; 2 ; ... m ) jest wektorem – kolumną wolnych wyrazów; Aj = (1j ; 2j ... mj ) jest wektorem – kolumną współczynników zmiennych хj. Biorąc pod uwagę równości (3.16) — (3.18), zadanie (3.13) — (3.15) przyjmie postać:
max (min) Z = 0 - (3.19)
xi+ , i ł 0 (i=1, 2,...m), (3.20)
xj ł 0, j=1,2, ... n; (3.21)
gdzie 0 = cB*Ao , j =cB*Aj - cj , j=m+1, m+2, ..., n.
Zadanie (3.19) — (3.21) zapisujemy w tabelę, która nazywa się tabela simpleks (tab. 3.1). Ostatni, (m+1)-szy, wiersz nazywa się indeksowym wierszem (wierszem celowej funkcji), liczba 0 = cB*Ao jest wartością celowej funkcji dla początkowego bazowego planu xо, tj. Ao = z(xo) = cB*Ao. Liczby j =cB*Aj - cj , () nazywają się ocenami swobodnych zmiennych.
Twierdzenie Niech w wejściowym zadaniu obliczamy maksimum. Jeżeli dla niektórego bazowego planu wszystkie oceny j, są nieujemne, to taki plan jest optymalny.
Dowód. Mamy Z = 0 - i to, że j ł 0 (j=m+1, m+2, ..., n), więc Z osiągnie maksymalną wartość dla =0. To będzie możliwe tylko dla xm+1=0, xm+2=0, ... , xn=0, tj. bazowy plan jest optymalny.
Twierdzenie Niech w wejściowym zadaniu obliczamy minimum i dla bazowego planu wszystkie oceny j, (j=m+1, m+2, ..., n) są nie dodatne, to taki plan jest optymalny.
Dowód jest analogiczny do poprzedniego twierdzenia.

Tabela 3.1.
Bazowe zmienne cB A0 x1 x2 ... xi ... xm xm+1 ... xj ... xn
c1 c2 ... ci ... cm cm+1 ... cj ... cn
x1 c1 1 1 0 ... 0 ... 0 1,m+1 ... 1,j ... 1,n
x2 c2 2 0 1 ... 0 ... 0 2,m+1 ... 2,j ... 2,n
... ... ... ... ... ... ... ... ... ... ... ... ... ...
xi ci i 0 0 ... 1 ... 0 i,m+1 ... i,j ... i,n
... ... ... ... ... ... ... ... ... ... ... ... ... ...
xm cm m 0 0 ... 0 ... 1 m,m+1 ... m,j ... m,n
zi - ci  0 0 ... 0 ... 0 m ... j ... n

Przekształcenia tabeli simpleks. Kryterium optymalności planu.

Powstaje pytanie, jak przejść do nie gorszego planu?
Rozpatrzymy zadanie na maksimum. Jeżeli wszystkie j ł 0 (j=1,2, ... n), to bazowy plan xо jest optymalny. Niech istnieje jо, dla którego j0 0) obliczymy stosunki i/ijo (i odpowiada dodatnim współczynnikom ijo);
2) wybierzemy i/ijo najmniejsze dla i = io i oznaczymy . Ono nazywa się najmniejszym simpleksowym: min(i/ijo) = io/iojo.
Jeżeli ten warunek jest spełniony dla kilka i, to za io możemy wybrać dowolne. Wiersz io nazywa się rozwiązujący, element iojo — rozwiązujący (lub źródłowy). Bazowa zmienna хio, jest nie perspektywiczną, musimy ją wyeliminować ze zmiennych bazowych.
Praktyka pokazuje, że w przypadku rozwiązania zadania na maksimum ilość kroków często zmniejsza się, jeżeli rozwiązującą kolumnę wybierać według reguły max(|j|) (j0 0).
3) Przekształcenie ZPL do nowej bazy nazywa się simpleks przekształceniem. Istnieją następujące reguły przejścia do kolejnej simpleks tabeli (jordan’ego przekształcenia).
а). Elementy io – go wiersza kolejnej tabeli są równe odpowiednim elementom rozwiązującego wiersza poprzedniej tabeli, podzielone przez rozwiązujący element:

b). Elementy rozwiązującej kolumny jo kolejnej tabeli są równe zeru, za wyjątkiem ’iojo=1:
.
c). Żeby obliczyć dowolny inny element kolejnej simpleks tabeli, musimy wykorzystać regułę prostokąta:

Рис. 4.1.
(4.1)
Dlatego w wejściowej tabeli wydzielamy prostokąt wierzchołkami, którego są niezbędne do obliczeń elementy. Przekątna, zawierająca rozwiązujący i poszukiwany element kolejnej tabeli, nazywa się główną, a druga — poboczną. Żeby obliczyć element kolejnej simpleks tabeli, musimy z iloczynu rogowych elementów głównej przekątnej odjąć iloczyn rogowych elementów pobocznej przekątnej i otrzymaną liczbę podzielić przez rozwiązujący element (rys. 4.1).
d). Według takich samych reguł mogą być obliczone wszystkie pozostałe elementy indeksowego wiersza 'j (j=1,2, ... n) i nowa wartość celowej funkcji о:
(4.2)
Krok simpleks metody, dający możliwość przejść od jednego bazowego planu do drugiego, nie gorszego nazywa się iteracją. Takim czynem, simpleks metoda jest iteracyjną metodą kolejnego polepszenia planu.
Można pokazać, że ocena (k)j0 swobodnej zmiennej xj0 charakteryzuje zmianę celowej funkcji Z na k – ej iteracji, odpowiadającej jednostkowej zmianie wartości zmiennej xj0. Stąd pochodzi termin «ocena».

Z geometrycznej interpretacji ZPL wynika, że jeżeli rozwiązująca prosta (płaszczyzna, hiperpłaszczyzna) przechodzi przez bok (krawędź, kraniec) wielokąta (wielościanu, wielościennej dziedziny) planów, to ZLP ma nieskończenie wiele optymalnych planów. W tym przypadku mówimy o alternatywnym optimum. Jak sprawdzić, rozwiązując ZPL simpleks metodą czy ma ona jedyny optymalny plan lub nieskończenie wiele? Odpowiedź na to pytanie daje następujące twierdzenie.
Twierdzenie Jeżeli w indeksowym wierszu ostatniej simpleks tabeli, zawierającej optymalny plan mamy co najmniej jedną zerową ocenę, odpowiadającej swobodnej zmiennej, to ZPL ma nieskończenie wiele optymalnych planów.
Dowód. Niech w optymalnym planie jo = 0, gdzie jо przyjmuje wartości indeksów wolnych zmiennych, a minimalny simpleks’owy stosunek odpowiada wierszowi iо. Wtedy, wprowadza się хjо do bazy i otrzymujemy nową wartość celowej funkcji
.
Wartość celowej funkcji przy przychodzeniu do nowego bazowego planu nie zmieniła się.
Jeżeli zerowych nie bazowych ocen w ostatniej simpleks tabeli okaże się kilka, to wprowadzamy każdą z odpowiednich zmiennych do bazy i wtedy znajdziemy optymalne plany х1*, х2*, ..., хk*, dla których wartości celowej funkcji będą równe, tj.
z(х1*)=z(х2*)=...=z(хk*).
Zgodnie z drugą częścią bazowego twierdzenia liniowego programowania, w tym przypadku optymalnym będzie dowolny plan, który jest ich wypukłą liniową kombinacją, tj. ogólne rozwiązanie przyjmie postać
х* = 1*х1* +2*х2* + ... +k*хk*, 1 +2 + ... +k= 1, i ł 0 (i=1,2,...k).
Ten wzór definiuje nieskończenie wiele rozwiązań.
Rezultat. Jeżeli w indeksowym wierszu simpleks tabeli zawierającej optymalny plan, wszystkie oceny wolnych zmiennych są dodatnie, to otrzymany optymalny plan jest jedyny.
Jak wynika z geometrycznej interpretacji ZPL, są możliwe przypadki, gdy celowa funkcja w zadaniu na maksimum nie jest ograniczona z góry, a w przypadku zadania na minimum nie jest ograniczona z dołu. Takie przypadki dla zadań, które rozwiązujemy simpleks metodą łatwo wyjaśnić wykorzystując następujące twierdzenia.
Twierdzenie (Cecha nieograniczoności celowej funkcji.) Jeżeli w indeksowym wierszu simpleks tabeli ZPL na maksimum jest ujemna ocena jo < 0, a w odpowiedniej kolumnie zmiennej xjo nie ma żadnego dodatniego elementu, to celowa funkcja na zbiorze dopuszczalnych rozwiązań nie jest ograniczona z góry.
Twierdzenie Jeżeli w indeksowym wierszu simpleks tabeli ZPL na minimum jest dodatnia ocena jo > 0, a w kolumnie zmiennej xjo nie ma żadnego dodatniego elementu, to na zbiorze dopuszczalnych planów celowa funkcja nie jest ograniczona z dołu.

Z ekonomicznego punktu widzenia nieograniczoność celowej funkcji ZPL świadczy tylko o jednym: rozpracowany model nie jest dokładny. Bez sensu mówić na przykład o nieskończonym zysku. Typowymi błędami doprowadzającymi do zbudowania nieprawidłowych modeli są: 1) nie branie pod uwagę wszystkich ograniczeń, które są istotne w danym zadaniu; 2) złe oceny parametrów w ograniczeniach.

Rzeczywiście, bazowy plan ZPL, zapisanej w najodpowiedniejszej postaci, nie jest zdegenerowany, gdy swobodne zmienne wszystkich równań są dodatnie, i jest zdegradowany, jeżeli niektóre z nich mają zerowe wartości. Kanoniczną postać ZPL nazywamy nie zdegenerowaną, jeżeli wszystkie jego bazowe plany są nie zdegenerowane. Jeżeli pomiędzy bazowymi planami jest co najmniej jeden zdegenerowany, to zadanie nazywa się zdegenerowane.
Niech rozwiązujemy ZPL na maksimum. Na dwóch kolejnych iteracjach k, k+1 wartości celowej funkcji są powiązane stosunkiem:

gdzie io ł 0; io Ł 0; aiojo > 0.
Jeżeli zadanie jest zdegenerowane, to dla dowolnego kroku io > 0, io < 0. Skąd , tj. wartość celowej funkcji będzie nie gorsza od poprzedniej (monotonicznie rośnie). Analogicznie, jeżeli zadanie rozwiązujemy na minimum, wykorzystując nierówność io ł 0, otrzymujemy dla dowolnego kroku, że dla wartości celowej funkcji dwóch kolejnych iteracji zachodzi nierówność , tj. celowa funkcja monotonicznie maleje. Na tym polega monotoniczność simpleksowej metody.
Algorytm simpleks metody jest końcowy, co bezpośrednio wnioskujemy z końcowej ilości bazowych planów ZPL (nie jest ich więcej niż ).
Jeżeli ZPL jest zdegenerowane, to możliwe są przypadki, gdy io = 0. W tej sytuacji wartość celowej funkcji nie polepsza się. Założymy, że ten proces ciągnie się bez przerwy, generując nieskończony ciąg bazowych planów. Biorąc pod uwagę, że ilość różnych planów jest ograniczona w tym ciągu, niektóre plany muszą powtarzać się. Tak jak celowa funkcja dla nich przyjmuje jednakowe wartości, muszą one należeć do jednej hiperpłaszczyzny i być wierzchołkami wypukłego wielościanu. Dlatego musi powstać łańcuch (cykl), w którym początkowe i końcowe plany zgadzają się.
Proces będzie ciągnął się nieograniczenie, i takie zjawisko nazywa się nieskończonym cyklem. Nieskończony cykl możliwy jest tylko dla zdegenerowanych zadań. Teoria i praktyka pokazują, że prawdopodobieństwo takiego zjawiska jest bardzo małe. Dokładny algorytm wyjścia z cyklu jest skomplikowany. W najłatwiejszym przypadku w cyklu potrzebne jest zmienić kolejność obliczeń, wybierając inną rozwiązującą kolumnę. Druga reguła rekomenduje zmienić wybór rozwiązującego wiersza. Jeżeli w procesie simpleksowych przekształceń mamy kilka minimalnych simpleksowych stosunków, to za rozwiązujący wybieramy ten wiersz, dla którego będzie najmniejszy stosunek elementów pierwszej kolumny do rozwiązującego. Jeżeli przy tym okaże się znowu kilka minimalnych stosunków, to obliczajmy stosunki elementów drugiej kolumny do rozwiązującej, i tak dopóki rozwiązujący wiersz nie będzie wyznaczony jednoznacznie.

Przykład rozwiązania zadania programowania liniowego metodą simpleks.

Zadanie . Przedsiębiorstwo ma możliwość produkować cztery rodzaje produkcji. W trakcie ich wytwarzania wykorzystuje trzy różne zasoby: sprzęt, surowce, półwyroby. Przedsiębiorstwo dysponuje pierwszym z zasobów w ilości b1 godzin, drugim – w ilości b2 kg i trzecim – w ilości b3 m. Dla produkcji jednej jednostki przemysłowej produkcji rodzaju j (j=1,2,3,4) potrzeba odpowiednio zasobów w ilości: pierwszego - а1j godzin, drugiego - a2j kg, trzeciego - a3j m (j=1,2,3,4). Planowy zysk przedsiębiorstwa w realizacji jednej jednostki produkcji rodzaju j (j=1,4) wynosi сj pieniężnych jednostek.
Potrzeba: 1) sformułować ekonomiczno – matematyczny model zadania, pozwalający znaleźć zbilansowany według zasobów plan wyprodukowania produktów oraz gwarantujący przedsiębiorstwu maksymalny zysk;
2) simpleks metodą znaleźć optymalny plan procesu produkcji.
b1=21 b2=85 b3=22 a11=0.13 a12=0.21 a13=0.36 a14=0.15 a21=0.31 a22=0.9 a23=1.4 a24=1.26 a3l=0.37 a32=0.21 a33=0.18 a34=0.12 cl=7 c2=9 c3=4 c4=8.
Rozwiązanie.
1) Znajdziemy simpleks metodą plan wyprodukowania produktów według rodzajów i dysponowanych zasobów. Dlatego sformułujemy ekonomiczno – matematyczny model zadania obliczenia optymalnego planu wyprodukowania produktów, gwarantujący przedsiębiorstwu maksymalny zysk oraz minimalne rozchody zasobów.
Oznaczymy przez х1, х2, х3 , х4 – ilość jednostek produktów odpowiedniego rodzaju P1, P2, P3, P4 a przez Z – wartość zysku z realizacji tych produktów. Zapiszemy ogólnie wyliczony zysk (celową funkcję) Z – w następującej postaci:
Z = c1x1 + c2x2 + c3x3 + c4x4 = 7x1 + 9x2 + 4x3+ 8x4
Zmienne х1, х2, х3 , х4 muszą spełniać ograniczenia na dysponujące przez przedsiębiorstwo zasoby. Wykorzystanie zasobu S1 do produkcji planu (х1, х2, х3, х4) wynosi а11х1 + а12х2 + а13х3 + а14х4 = 0.13х1 + 0.21х2 + 0.36х3 + 0.15х4 jednostek. Wiadomo, że suma nie może przewyższać zapasu zasobu S1 w przedsiębiorstwie, który wynosi b1=21 jednostek, tj. 0.13х1 + 0.21х2 + 0.36х3 + 0.15х4 ...

Ciąg dalszy w pliku do pobrania.

wkuwanko.pl