16
Lekcja 3-4. Metoda simpleks w programowaniu liniowym
Lekcja 3-4. Metoda simpleks w planowaniu liniowym.
3.1. Założenia metody simpleks.
3.2. Bazowy plan zadania w metodzie simpleks.
3.3. Tablica simpleks. Przekształcenia tablicy simpleks.
4.1. Kryterium optymalności planu.
4.2. 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.
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.
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 ³ 0 (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 3.1. 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 3.2. 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.
3.3. 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*b1 + c2*b2+ ... + cm*bm) – ((c1*a1,m+1 ...
flipsik