11.4. METODA PODWÓJNA PROSTOTA
Z wyników poprzednich podrozdziałów wynika, że w celu uzyskania rozwiązania pierwotnego problemu, możemy przejść do rozwiązania dualnego i korzystając z oszacowań jego optymalnego projektu, wyznaczyć optymalne rozwiązanie pierwotnego problemu.
Przejście do problemu dualnego nie jest konieczne, ponieważ jeśli weźmiemy pod uwagę pierwszą tablicę simpleksową z jednostkową dodatkową podstawą, to łatwo zauważyć, że kolumny zawierają oryginalny problem, a problem dualny jest zapisany w wierszach.
Jak pokazano, przy rozwiązywaniu bezpośredniego problemu w dowolnej iteracji różnica, tj. ogrom -współczynnik ze zmienną, jest równa różnicy między prawą i lewą stroną odpowiedniego ograniczenia problemu podwójnego. Jeżeli przy rozwiązywaniu problemu bezpośredniego z maksymalizowaną funkcją celu iteracja nie prowadzi do rozwiązania optymalnego, to przynajmniej dla jednej zmiennej i tylko w optymalnym dla wszystkich różnica .
Biorąc pod uwagę ten warunek z uwzględnieniem dwoistości, możemy napisać
.
Tak więc, jeśli, następnie . Oznacza to, że gdy rozwiązanie pierwotnego problemu nie jest optymalne, rozwiązanie podwójnego problemu jest nieważne. Z drugiej strony 
w . Oznacza to, że optymalne rozwiązanie problemu pierwotnego odpowiada dopuszczalnemu rozwiązaniu problemu dualnego.
Umożliwiło to opracowanie nowej metody rozwiązywania problemów programowania liniowego, przy użyciu której najpierw uzyskuje się rozwiązanie nieakceptowalne, ale „lepsze niż optymalne” (w zwykłej metodzie simplex najpierw dopuszczalny, ale nieoptymalny rozwiązanie). Nowa metoda o nazwie metoda dual simplex, zapewnia spełnienie warunku optymalności rozwiązania i jego systematyczne „zbliżanie” do obszaru rozwiązań dopuszczalnych. Gdy otrzymane rozwiązanie okaże się dopuszczalne, iteracyjny proces obliczeń kończy się, gdyż i to rozwiązanie jest optymalne.
Metoda dual simplex umożliwia rozwiązywanie problemów programowania liniowego, których układy ograniczeń o podstawie dodatniej zawierają wyrazy dowolne o dowolnym znaku. Metoda ta umożliwia zmniejszenie liczby przekształceń systemu więzów oraz rozmiaru tablicy simpleksowej. Rozważ zastosowanie metody dual simplex na przykładzie.
Przykład. Znajdź minimum funkcji 
pod ograniczeniami
.
Przejdźmy do formy kanonicznej:
pod ograniczeniami
Początkowa tablica simpleksowa ma postać
|
Podstawowy zmienne |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Rozwiązanie |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Wstępne rozwiązanie podstawoweoptymalny, ale nie do zaakceptowania.
Podobnie jak zwykła metoda simpleks, rozważana metoda rozwiązania opiera się na wykorzystaniu warunków dopuszczalności i optymalności.
Warunek dopuszczalności. Największa ujemna zmienna podstawowa w wartości bezwzględnej jest wybierana jako zmienna wykluczona (jeśli istnieją alternatywy, wybór jest dokonywany arbitralnie). Jeżeli wszystkie podstawowe zmienne są nieujemne, proces obliczeniowy kończy się, ponieważ wynikowe rozwiązanie jest wykonalne i optymalne.
Stan optymalność. Zmienna uwzględniona w podstawie jest wybierana spośród zmiennych niepodstawowych w następujący sposób. Obliczane są stosunki współczynników lewej strony-równania do odpowiednich współczynników równania związanego z wykluczoną zmienną. Relacje z dodatnimi lub zerowymi mianownikami nie są brane pod uwagę. W zagadnieniu minimalizacji zmiennej wejściowej musi odpowiadać najmniejszy ze wskazanych stosunków, a w zagadnieniu maksymalizacji stosunek o najmniejszej wartości bezwzględnej (jeżeli są alternatywy, wybór dokonywany jest arbitralnie). Jeśli mianowniki wszystkich stosunków są zerowe lub dodatnie, problem nie ma wykonalnych rozwiązań.
Po wybraniu zmiennych, które mają być uwzględnione w bazie i wykluczone, wykonuje się zwykłą operację przekształcenia wierszy tablicy simpleksowej w celu uzyskania kolejnego rozwiązania.
W tym przykładzie wykluczoną zmienną jest. Wskaźniki obliczone w celu wyznaczenia nowej zmiennej bazowej przedstawiono w poniższej tabeli:
|
Zmienne |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Równanie x 4 - równanie |
–2 –4 |
–1 –3 |
|||
|
Nastawienie |
Zmienna, którą należy uwzględnić, to x 2. Kolejna konwersja ciągów daje w wyniku nową tabelę simpleks:
|
Podstawowy zmienne |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Rozwiązanie |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
Nowe rozwiązanie również optymalny, ale wciąż nieważny. Jako nową wykluczoną zmienną wybieramy (arbitralnie) x 3 . Zdefiniujmy zawartą zmienną.
|
Zmienne |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Równanie x 4 - równanie |
|||||
|
nastawienie |
Metoda simpleks - jest to metoda sukcesywnego przejścia od jednego rozwiązania podstawowego (wierzchołek wielościanu rozwiązania) układu ograniczeń zadania programowania liniowego do innego rozwiązania podstawowego, aż funkcja celu przyjmie wartość optymalną (maksimum lub minimum).
Metoda simpleks to uniwersalna metoda, która może rozwiązać każdy problem programowania liniowego, podczas gdy metoda graficzna jest odpowiednia tylko dla systemu więzów z dwiema zmiennymi.
Metodę simpleks zaproponował amerykański matematyk R. Danzig w 1947 roku, od tego czasu na potrzeby przemysłu metoda ta często rozwiązuje problemy programowania liniowego z tysiącami zmiennych i ograniczeń.
Zanim przejdziemy do algorytmu metody simplex, kilka definicji.
Każde nieujemne rozwiązanie systemu ograniczeń nazywa się akceptowalne rozwiązanie .
Niech będzie system m ograniczenia od n zmienne ( m n).
Dopuszczalne rozwiązanie podstawowe jest roztworem zawierającym m nieujemny poważny (podstawowy ) zmienne i n - m niezwiązany z rdzeniem . (niepodstawowe lub darmowy ) zmienne. Zmienne niepodstawowe w rozwiązaniu podstawowym są równe zeru, natomiast zmienne główne z reguły są niezerowe, czyli są liczbami dodatnimi.
Każdy m zmienne systemowe m równania liniowe z n zmienne nazywają się Główny , jeśli wyznacznik współczynników na nich jest różny od zera. Potem reszta n - m zmienne nazywają się niezwiązany z rdzeniem (lub darmowy ).
Algorytm metody simpleks
- Krok 1. Sprowadź problem programowania liniowego do postaci kanonicznej. Aby to zrobić, przenieś wyrazy wolne na prawą stronę (jeśli wśród tych wyrazów wolnych są ujemne, pomnóż odpowiednie równanie lub nierówność przez -1) i wprowadź dodatkowe zmienne do każdego ograniczenia (ze znakiem plus, jeśli w pierwotna nierówność znak jest mniejszy lub równy ", a ze znakiem minus, jeśli "większy lub równy").
- Krok 2. Jeśli w powstałym systemie m równania, to m weź zmienne jako główne, wyraź zmienne główne jako zmienne niepodstawowe i znajdź odpowiednie rozwiązanie podstawowe. Jeśli znalezione rozwiązanie podstawowe okaże się dopuszczalne, przejdź do dopuszczalnego rozwiązania podstawowego.
- Krok 3. Wyraź funkcję celu w postaci zmiennych drugorzędnych dopuszczalnego rozwiązania podstawowego. Jeżeli zostanie znalezione maksimum (minimum) postaci liniowej i nie ma w jej wyrażeniu zmiennych niepodstawowych o ujemnych (dodatnich) współczynnikach, to kryterium optymalności jest spełnione i otrzymane rozwiązanie podstawowe jest optymalne – rozwiązanie jest zakończone. Jeżeli przy znajdowaniu maksimum (minimum) formy liniowej jej wyrażenie zawiera jedną lub więcej zmiennych niepodstawowych o ujemnych (dodatnich) współczynnikach, przejdź do nowego rozwiązania podstawowego.
- Krok 4. Z niepodstawowych zmiennych zawartych w postaci liniowej o ujemnych (dodatnich) współczynnikach wybierz tę, która odpowiada największemu współczynnikowi (modulo) i przenieś ją na główne. Przejdź do kroku 2.
Ważne warunki
Niektóre szczególne przypadki zostały omówione w osobnych artykułach: kiedy maksymalna funkcja celu - nieskończoność, gdy system nie ma rozwiązania, i kiedy optymalne rozwiązanie nie jest jedynym .
Następnie przeanalizujemy typowy przykład, kiedy układ więzów jest spójny i istnieje skończone optimum i tylko jedno. Odmianą metody simplex jest sposób dystrybucji rozwiązania problemu transportowego .
Metoda simpleksowa z tabelami simpleksowymi
Konstruując tabele simpleksowe, znacznie łatwiej jest rozwiązać problem programowania liniowego niż za pomocą przekształceń algebraicznych, co pokazano w następnym akapicie. Tabele simpleksowe są bardzo wizualne. Istnieje kilka rodzajów reguł pracy z tabelami simpleks. Przeanalizujemy regułę, która jest najczęściej nazywana regułą wiodącej kolumny i wiodącego wiersza.
Przydałoby się otworzyć manual Actions with ułamki w nowym oknie: jest ich wystarczająco dużo, ułamki w problemach na metodzie simplex, delikatnie mówiąc.
Przykład.
Wprowadzamy dodatkowe zmienne nieujemne i redukujemy ten układ nierówności do równoważnego układu równań
.
Dokonano tego zgodnie z następującą zasadą: jeśli znak w pierwotnym ograniczeniu jest „mniejszy lub równy”, to zmienna dodatkowa musi być dodana, a jeśli „większy lub równy”, to zmienna dodatkowa musi być odejmowane.
Wprowadzone dodatkowe zmienne są traktowane jako główne (podstawowe). Wtedy i są niepodstawowymi (wolnymi) zmiennymi.
Wyrażając główne (podstawowe) zmienne w kategoriach niepodstawowych (wolnych), otrzymujemy
Wyrażamy również funkcję celu w postaci zmiennych niepodstawowych (wolnych):
Ze współczynników zmiennych (niewiadomych) konstruujemy pierwszą tablicę simpleksową.
| Tabela 1 | ||||
| Podstawowe niewiadome | Bezpłatni członkowie | Luźne niewiadome | Współczynniki pomocnicze | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Ostatni wiersz tabeli, który zawiera funkcję celu i zawarte w niej współczynniki zmiennych wolnych, będzie nazywany wierszem indeksu.
Otrzymane rozwiązanie nie jest optymalne, ponieważ współczynniki wolnych zmiennych w wierszu indeksu są ujemne. Oznacza to, że optymalnym rozwiązaniem będzie takie, w którym współczynniki wolnych zmiennych w wierszu indeksu będą większe lub równe zero.
Aby przejść do następnej tabeli, znajdź największą (modulo) z liczb i . Ta liczba to 2. Dlatego wiodącą kolumną jest kolumna, w której jest napisana
Aby określić wiersz wiodący, znajdujemy minimum stosunków wolnych członków do elementów kolumny wiodącej, a jeśli licznik ma liczbę dodatnią, a mianownik jest ujemny, uważa się, że stosunek jest równy nieskończoności.
.
Dlatego wiodącą linią jest ta, w której jest napisana
Wiodącym elementem jest zatem -2.
Tworzymy drugą tablicę simpleksową.
W pierwszym wierszu wpisujemy nowy element podstawowy i wpisujemy kolumnę w której się znajdował, wpisujemy nową zmienną wolną
Wypełnij pierwszy wiersz. Aby to zrobić, dzielimy wszystkie liczby w wiodącym rzędzie tabeli 1 przez wiodący element i zapisujemy go w odpowiedniej kolumnie pierwszego rzędu tabeli 2, z wyjątkiem liczby w wiodącej kolumnie, gdzie odwrotność wiodącego jest zapisywany element (czyli jeden podzielony przez element wiodący).
Wypełnij kolumnę współczynników pomocniczych. Dla tego numeru kolumny wiodącej tabeli 1 oprócz elementu wiodącego wpisujemy przeciwstawnymi znakami w kolumnie współczynników pomocniczych tabeli 2.
| Tabela 2 | ||||
| Podstawowe niewiadome | Bezpłatni członkowie | Luźne niewiadome | Współczynniki pomocnicze | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Kto jeszcze nie otworzył w nowym oknie instrukcji Akcje z ułamkami, może to zrobić teraz, bo już czas.
Aby otrzymać pozostałe wiersze tabeli 2, liczby już w pierwszym wierszu tej tabeli mnoży się przez współczynnik pomocniczy w wierszu wypełnianym, a do wyniku dodajemy liczbę z tabeli 1, która znajduje się w tym samym wierszu z odpowiednią zmienną.
Na przykład, aby uzyskać wolny członek drugiego rzędu, mnożymy liczbę 1 przez 1 i dodajemy liczbę -4 z tabeli 1. Otrzymujemy -3. Współczynnik dla w drugim wierszu znajdujemy w ten sam sposób: 
. Ponieważ w poprzedniej tabeli nie ma kolumny z nową zmienną wolną, współczynnik drugiego wiersza w kolumnie nowej zmiennej wolnej będzie wynosił 
(czyli z tabeli 1 dodajemy 0, ponieważ w tabeli 1 nie ma kolumny c).
Linia indeksu jest wypełniana w ten sam sposób:
Uzyskane w ten sposób rozwiązanie ponownie nie jest optymalne, ponieważ współczynniki wolnych zmiennych w wierszu indeksu są ponownie ujemne.
Aby przejść do następnej tabeli simpleksowej, znajdźmy największą (modulo) z liczb i , czyli moduły współczynników w linii indeksu. Ta liczba to 2. Dlatego wiodącą kolumną jest kolumna zawierająca .
Aby wyszukać wiersz wiodący, znajdźmy minimalny stosunek wolnych członków do elementów wiersza wiodącego. Otrzymujemy:
.
Dlatego linia wiodąca to ta, w której jest zapisana, a elementem wiodącym jest -3/2.
Kompilacja trzeciej tablicy simpleksowej
W pierwszym wierszu piszemy nową zmienną podstawową. W kolumnie, w której się znajdowała, wpisujemy nową wolną zmienną .
Pierwsza linia:
Współczynniki pomocnicze:
| Tabela 3 | ||||
| Podstawowe niewiadome | Bezpłatni członkowie | Luźne niewiadome | Współczynniki pomocnicze | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
Otrzymane rozwiązanie ponownie nie jest optymalne, ponieważ współczynniki wolnych niewiadomych w wierszu indeksów są ponownie ujemne.
Aby przejść do czwartej tablicy simpleksowej, znajdźmy największą z liczb oraz . To jest liczba.
Dlatego wiodącą kolumną jest ta z .
Minimalny moduł relacji prętów swobodnych do elementów kolumny wiodącej:
.
Dlatego linia wiodąca to ta, w której jest napisana, a elementem wiodącym jest 1/3.
W czwartej tablicy simpleksowej w pierwszym wierszu wpisujemy nową zmienną podstawową. W kolumnie, w której to było, piszemy nową wolną zmienną .
Pierwsza linia:
Współczynniki pomocnicze:
| Tabela 4 | ||||
| Podstawowe niewiadome | Bezpłatni członkowie | Luźne niewiadome | Współczynniki pomocnicze | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Obliczenie pozostałych wierszy na przykładzie drugiego wiersza:
Otrzymane rozwiązanie również nie jest optymalne, ale już jest lepsze od poprzednich, ponieważ jeden ze współczynników dla zmiennych wolnych w wierszu indeksu jest nieujemny.
Aby ulepszyć plan, przejdźmy do następnej tabeli simpleksowej.
Znajdź największą z liczb 4 i . Ta liczba to 4. Dlatego wiodąca kolumna to .
Aby znaleźć pierwszy wiersz, znajdź
.
Dlatego linia wiodąca to ta, która zawiera . Ale byli już razem wśród wolnych zmiennych. Dlatego, aby przenieść kolejną zmienną z wolnej na podstawową, wybieramy kolejną kolumnę wiodącą - tę, w której jest napisana.
Aby znaleźć pierwszy wiersz, znajdź
.
Dlatego kluczową linią jest ta, w której jest napisana, a wiodącym elementem jest 1.
W piątej tablicy simpleksowej w pierwszym wierszu jest zapisana nowa zmienna podstawowa. W kolumnie, w której to było, piszemy nową wolną zmienną .
Pierwsza linia:
Współczynniki pomocnicze:
| Tabela 5 | ||||
| Podstawowe niewiadome | Bezpłatni członkowie | Luźne niewiadome | Współczynniki pomocnicze | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Spróbujmy od razu dowiedzieć się, czy rozwiązanie nie jest optymalne. Dlatego dla pozostałych wierszy obliczamy tylko wolne terminy (aby znaleźć wartości zmiennych podstawowych, gdy wolne zmienne są równe zero) oraz współczynniki dla wolnych zmiennych w wierszu indeksu.
Bezpłatni członkowie:
W drugim wierszu ;
W trzecim wierszu;
W czwartej linii.
Linia indeksu:
Patrzymy na tabelę simpleks 5. Widzimy, że uzyskano optymalne rozwiązanie, ponieważ współczynniki dla wolnych niewiadomych w wierszu indeksów są nieujemne.
Metoda sympleksowa z przekształceniami algebraicznymi
Rozwiążmy przez przekształcenia algebraiczne ten sam przykład, co w poprzednim akapicie. Należy zauważyć, że przy rozwiązywaniu tego typu metody simpleks lepiej nie zapisywać funkcji celu w postaci , ponieważ łatwo się pomylić w znakach. Jednak w tym przypadku punkt algorytmu określający kryterium optymalności zostanie zmodyfikowany w następujący sposób.
Jeżeli zostanie znalezione maksimum (minimum) postaci liniowej i nie ma w jej wyrażeniu zmiennych niepodstawowych o współczynnikach dodatnich (ujemnych), to kryterium optymalności jest spełnione i otrzymane rozwiązanie podstawowe jest optymalne – rozwiązanie jest zakończone. Jeżeli przy znajdowaniu maksimum (minimum) formy liniowej jej wyrażenie zawiera jedną lub więcej zmiennych niepodstawowych o dodatnich (ujemnych) współczynnikach, przejdź do nowego rozwiązania podstawowego.
Przykład. Znajdź maksimum funkcji z ograniczeniami
Krok I. Wprowadzamy dodatkowe zmienne nieujemne i redukujemy ten układ nierówności do równoważnego układu równań
.
Wprowadzone dodatkowe zmienne są traktowane jako główne, ponieważ w tym przypadku łatwo jest znaleźć podstawowe rozwiązanie systemu. Wtedy i są pomniejszymi zmiennymi.
Wyrażając główne zmienne w kategoriach niepodstawowych otrzymujemy
W konsekwencji ten podział zmiennych na podstawowe i niepodstawowe odpowiada rozwiązaniu podstawowemu 
, który jest nieprawidłowy (dwie zmienne są ujemne), a zatem nie jest optymalny. Przejdźmy od tego podstawowego rozwiązania do ulepszonego.
Aby zdecydować, która zmienna powinna zostać przeniesiona ze zmiennej niepodstawowej do głównej, rozważ jedno z dwóch dostępnych równań ostatniego układu z ujemnymi wyrażeniami wolnymi, na przykład drugie. Pokazuje to i można to przełożyć na zmienne główne, ponieważ w tym równaniu mają one współczynniki dodatnie (a zatem, gdy wzrosną, a stanie się tak, jeśli przełożymy którąkolwiek z nich na zmienne główne, zmienna wzrośnie).
Spróbujmy przetłumaczyć na zmienną główną . Aby określić, która zmienna powinna zostać przeniesiona z głównej na niepodstawową, znajdujemy wartość bezwzględną najmniejszego stosunku wolnych elementów układu do współczynników przy . Mamy . Wynika to z trzeciego równania, z którego wynika, że zmienna musi zostać przekonwertowana na niepodstawowe, co w pierwotnym rozwiązaniu podstawowym jest dodatnie. W konsekwencji otrzymane rozwiązanie podstawowe, podobnie jak oryginalne, zawiera dwa składowe ujemne, tzn. nie będzie poprawy w przejściu na takie rozwiązanie podstawowe.
Metoda simpleks− jest to sposób uporządkowanego wyliczania planów referencyjnych (uporządkowanie zapewnia jednostajna zmiana wartości funkcji celu podczas przejścia do kolejnego planu). W tym przypadku należy przestrzegać zasady: każdy kolejny krok powinien poprawiać lub w skrajnych przypadkach nie pogarszać wartości funkcji celu.
Aby rozwiązać LLP metoda simpleks sprowadza się do formy kanonicznej, tj. z ograniczeń - nierówności trzeba czynić ograniczenia - równości. W tym celu każde ograniczenie jest uzupełniane dodatkowym nieujemnym zmienna bilansowa ze znakiem „+”, jeśli znakiem nierówności jest „£”, a ze znakiem „–”, jeśli znakiem nierówności jest „³”.
W funkcji celu te dodatkowe zmienne wchodzą z zerowymi współczynnikami, tj. wpis funkcji docelowej nie zmieni się. Każdą zmienną, która nie podlega warunku nieujemności, można przedstawić jako różnicę dwóch zmiennych nieujemnych: .
Jeżeli ograniczenia zadania odzwierciedlają obecność i zużycie zasobów, to wartość liczbowa dodatkowej zmiennej w planie zadania, zapisana w formie kanonicznej, jest równa ilości niewykorzystanego zasobu.
Aby rozwiązać problem metodą simpleks, użyjemy skrócone tablice simpleksowe układu równań liniowych i zmodyfikowana metoda eliminacji Jordana.
1. Opracowujemy pierwszy plan podstawowy
Zadanie pozostaje takie samo. Sprowadźmy standardową postać układu nierówności (1) do postaci kanonicznej układu równań, wprowadzając dodatkowe zmienne bilansowe x 3 , x 4 , x 5 ,x 6 .
W sensie ekonomicznym wartości dodatkowych zmiennych x 3 , x 4 , x 5 określić bilans surowców po sprzedaży produktów.
Macierz wynikowego układu równań ma postać:
Widać, że w matrycy A podstawą drugorzędną czwartego rzędu jest determinanta, złożona ze współczynników jednostkowych dla dodatkowych zmiennych x 3 , x 4 , x 5 ,x 6 , ponieważ jest niezerowe i równe 1. Oznacza to, że wektory kolumnowe dla tych zmiennych są liniowo niezależne, tj. Formularz podstawa i odpowiednie zmienne x 3 , x 4 , x 5 ,x 6 are podstawowy(podstawowy). Zmienne x 1 , x 2 zostanie nazwany darmowy(drobny).
Jeśli wolne zmienne x 1 i x 2 ustalając różne wartości, to rozwiązując układ ze względu na podstawowe zmienne, otrzymujemy nieskończony zbiór poszczególnych rozwiązań. Jeżeli dla zmiennych wolnych ustawione są tylko wartości zerowe, to z nieskończonego zbioru poszczególnych rozwiązań, podstawowe rozwiązania- podstawowe plany.
Aby dowiedzieć się, czy zmienne mogą być podstawowe, konieczne jest obliczenie wyznacznika składającego się ze współczynników tych zmiennych. Jeśli ten wyznacznik nie jest równy zero, to te zmienne mogą być podstawowe.
Liczba rozwiązań podstawowych i odpowiadająca im liczba grup zmiennych podstawowych nie może być większa niż , gdzie n to całkowita liczba zmiennych, r to liczba podstawowych zmiennych, r≤ m≤ n.
Za nasze zadanie r = 4; n= 6. Wtedy , tj. Możliwych jest 15 grup po 4 podstawowe zmienne (lub 15 podstawowych rozwiązań).
Rozwiążmy układ równań ze względu na podstawowe zmienne x 3 , x 4 , x 5 ,x 6:
Zakładając, że wolne zmienne x 1 = 0, x 2 = 0, otrzymujemy wartości podstawowych zmiennych: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, tj. podstawowym rozwiązaniem będzie = (0; 0; 312; 15; 24; -10).
To podstawowe rozwiązanie to gorszący, dlatego x 6 = -10 ≤ 0 oraz przez warunek ograniczający x 6 ≥ 0. Dlatego zamiast zmiennej x 6 jako podstawę należy wziąć inną zmienną spośród wolnych x 1 lub x 2 .
Dalsze rozwiązanie przeprowadzimy za pomocą skróconych tabel simpleksowych, wypełniając wiersze pierwszej tabeli współczynnikami układu w następujący sposób (Tabela 1):
Tabela 1
F- ciąg nazywa się indeks. Jest wypełniony współczynnikami funkcji celu wziętymi z przeciwstawnymi znakami, ponieważ równanie funkcji można przedstawić jako F = 0 – (– 4x 1 – 3x 2).
W kolumnie wolnych członków b ja jest element negatywny b 4 = -10, tj. rozwiązanie systemu jest nieprawidłowe. Aby uzyskać prawidłowe rozwiązanie (plan bazowy), element b 4 musi być nieujemny.
Wybierać x 6 - linia z ujemnym wolnym członkiem. Ten wiersz zawiera elementy negatywne. Wybierz dowolny z nich, na przykład "-1" w x 1 -kolumna, i x 1 - kolumna zaakceptuj jako kolumna uprawnień(określi to, że zmienna x 1 zmieni się z bezpłatnego na podstawowy).
Dzielimy się darmowymi członkami b ja na odpowiednich elementach jest kolumna rozstrzygająca, otrzymujemy relacje wartościoweΘ i==(24, 15, 12, 10). Spośród nich wybieramy najmniejszy pozytyw (minΘ i=10), co odpowiada linia pozwolenia. Ciąg uprawnień definiuje zmienną x j, który w kolejnym kroku wystaje z podstawy i staje się wolny. Dlatego x 6 -line to linia zezwalająca, a element "-1" to włączenie elementu. Okrążamy to. Zmienne x 1 i x 6 są zamienione.
Szacunkowe wskaźniki Θ i w każdej linii określają zasady:
1) i= jeśli b ja oraz jest mieć różne znaki;
2) i= ∞ jeśli b ja= 0 i jest < 0;
3) i= ∞ jeśli jest = 0;
4) i= 0 jeśli b ja= 0 i jest > 0;
5) i= jeśli b ja oraz jest mają te same znaki.
Przechodzimy do etapu zmodyfikowanej eliminacji jordańskiej (MJJI) z elementem permisywnym i zestawiamy nową tabelę (Tabela 2) zgodnie z następującą zasadą:
1) w miejsce rozstrzygającego elementu (RE) ustawiana jest wartość, jej odwrotność, tj. ;
2) elementy linii permisywnej dzielą się na RE;
3) elementy kolumny rozstrzygającej dzielą się na RE i zmienia się znak;
4) pozostałe elementy znajdują się zgodnie z zasadą prostokąta:
Z tabeli. 2 pokazuje, że wolni członkowie w b ja-kolumny są nieujemne, w związku z czym uzyskuje się wstępne dopuszczalne rozwiązanie - pierwszy plan podstawowy= (10; 0; 182; 5; 4; 0). W tym przypadku wartość funkcji F() = 40. Geometrycznie odpowiada to górze F(10; 0) rozwiązanie wielokąta (rys. 1).
Tabela 2
2. Sprawdzamy plan pod kątem optymalności. Plan bazowy nie jest optymalny, ponieważ w F-line ma ujemny współczynnik „-4”. Ulepszamy plan.
3. Znalezienie nowej linii bazowej
Element dopuszczający wybieramy zgodnie z zasadą:
Wybieramy najmniejszy ujemny współczynnik w F-line "-4", który określa kolumnę włączającą - x 6; zmienny x 6 przełożyć na podstawowe;
Znajdujemy proporcje Θ i, spośród nich wybieramy najmniejszy dodatni, który odpowiada łańcuchowi permisywnemu:
min Θ i = min(14, 5, 2, ∞) = 2, stąd x 5 - linia - permisywna, zmienna x 5 tłumaczymy na darmowe (zmienne x 5 i x 6 są zamienione).
Na przecięciu permisywnego rzędu i kolumny znajduje się permisywny element „2”;
Wykonujemy krok SHMZhI, budujemy stół. 3 zgodnie z powyższą regułą i uzyskaj nowy plan odniesienia = (12; 0; 156; 3; 0; 2).
Tabela 3
4. Sprawdzenie nowego planu podstawowego pod kątem optymalności
Plan bazowy również nie jest optymalny, ponieważ w F-line ma ujemny współczynnik „-1”. Wartość funkcji F() = 48, co geometrycznie odpowiada wierzchołkowi mi(12; 0) wielokąt rozwiązania (ryc. 1). Ulepszamy plan.
5. Znalezienie nowej linii bazowej
x 2 kolumny są dozwolone, ponieważ in F-line najmniejszy ujemny współczynnik "-1" jest w x 2 kolumny (Δ 2 = -1). Znalezienie najmniejszego Θ i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, stąd x Czwarta linia - permisywna. Dozwolony element „1/2”. Zamiana zmiennych x 2 i x cztery . Wykonujemy krok SHMZhI, budujemy stół. 4, otrzymujemy nowy plan odniesienia = (9; 6; 51; 0; 0; 5).
6. Sprawdzenie podstawowego planu pod kątem optymalności
W F-line, wszystkie współczynniki są nieujemne, dlatego plan odniesienia jest optymalny. Geometrycznie odpowiada punktowi D(9;6) (patrz rys. 1). Plan optymalny daje maksymalną wartość funkcji celu c.u.
Główny idea metody simplex do rozwiązywania LLP polega na konsekwentnym doskonaleniu rozwiązań wspierających LLP.
Istnieje kilka sposobów na napisanie metody simplex.
- Podstawowa forma metody simplex;
- Metoda simpleksowa w formie tablicy simpleksowej;
- Zmodyfikowana metoda simpleks;
- Metoda simpleksowa w formie kolumnowej;
- Metoda simpleksowa w formie wierszowej.
Zdefiniujmy maksymalną wartość funkcji celu F(X) = 3x 1 +5x 2 +4x 3 w następujących warunkach ograniczających.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000
Aby skonstruować pierwszy plan odniesienia, sprowadzamy układ nierówności do układu równań, wprowadzając dodatkowe zmienne (przejście do postaci kanonicznej).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Podstawowy zapis metody simpleks
| Rozwiązanie jest realizowane poprzez wyrażenie podstawowych zmiennych za pomocą niepodstawowych: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Metoda simpleksowa w formie tablicy simpleksowej
Rozwiązanie realizowane jest w formie tabeli simpleksowej. Formularz przeznaczony jest do obliczeń na komputerze. Podczas korzystania ze sztucznej podstawy używana jest specjalna liczba M (zwykle 10000).| Plan | Podstawa | W | x 1 | x2 | x 3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Linia indeksu | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Linia indeksu | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Linia indeksu | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Zmodyfikowana metoda simpleks
| Macierz współczynników A = a ij Macierz b. |
Metoda simpleksowa w formie kolumnowej
| Przechodzimy do formy kolumnowej metody simplex. Każdą zmienną wyrażamy w kategoriach niepodstawowych. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Ten system odpowiada tabeli T 0 .
|
Metoda simpleksowa w formie ciągu
Jako początkową dopuszczalną podstawę możemy przyjąć B 0 =<4, 5, 6>. Będzie to odpowiadało poniższej tabeli.
|
Macierz Q, złożona ze współczynników układu, nazywa się stół simpleksowy odpowiadające podstawie B. Nazywamy tablicę simpleks dopuszczalny, lub bezpośrednio dopuszczalne, jeśli q i0 ≥ 0. Elementy q i0 ostatniego wiersza tabeli simpleksowej Q są nazywane względne szacunki.
Formy rozwiązania metodą sztucznej bazy
Za wykorzystanie zmiennych sztucznych wprowadzanych do funkcji celu nakładana jest tzw. kara M, bardzo duża liczba dodatnia, która zwykle nie jest określona.Powstała baza nazywana jest sztuczną, a metoda rozwiązania nazywana jest metodą sztucznej bazy.
Co więcej, zmienne sztuczne nie są związane z treścią zadania, ale pozwalają zbudować punkt wyjścia, a proces optymalizacji wymusza na tych zmiennych przyjęcie wartości zerowych i zapewnia dopuszczalność optymalnego rozwiązania.
Formy rozwiązania metodą sztucznej bazy:
- Metoda M (tabela simpleks);
- dwuetapowa lub dwufazowa metoda simpleks (Zapis podstawowy, Zmodyfikowana metoda simpleks, Metoda Simplex w formie kolumnowej, Metoda Simplex w formie liniowej).
Jeżeli istnieją ograniczenia ze znakiem ≥ w warunkach problemu, to można je sprowadzić do postaci ∑a ji b j mnożąc obie części nierówności przez -1. Wprowadzamy m dodatkowych zmiennych x n+j ≥0(j =1,m ) i przekształcamy ograniczenia do postaci równości
(2)
Załóżmy, że wszystkie początkowe zmienne zadania x 1 , x 2 ,..., x n są niepodstawowe. Wówczas zmienne dodatkowe będą podstawowe, a konkretne rozwiązanie układu ograniczeń ma postać
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Ponieważ w tym przypadku wartość funkcji celu F 0 = 0 , możemy przedstawić F(x) w następujący sposób:
F(x)=∑c i x i + F 0 =0 (4)
Wstępna tabela simpleks (tablica simpleks 1) jest kompilowana na podstawie równań (2) i (4). Jeżeli dodatkowe zmienne x n+j są poprzedzone znakiem „+”, jak w (2), to wszystkie współczynniki przed zmiennymi x i oraz wyrazem swobodnym b j są wpisywane do tablicy simpleksowej bez zmian. Współczynniki funkcji celu podczas jej maksymalizacji wpisuje się w dolnym wierszu tabeli simpleksowej z przeciwstawnymi znakami. Wolne elementy w tablicy simpleksowej określają rozwiązanie problemu.
Algorytm rozwiązania problemu wygląda następująco:
Pierwszy krok. Wyszukiwane są elementy kolumny wolnych członków. Jeżeli wszystkie są pozytywne, to znaleziono akceptowalne rozwiązanie podstawowe i należy przejść do kroku 5 algorytmu, który odpowiada znalezieniu rozwiązania optymalnego. Jeśli w początkowej tablicy simpleksowej znajdują się ujemne terminy wolne, rozwiązanie nie jest prawidłowe i należy przejść do kroku 2.
Drugi krok. Aby znaleźć realne rozwiązanie, należy podjąć decyzję, którą ze zmiennych niepodstawowych uwzględnić w bazie, a którą z niej wycofać.
Tabela 1.
| zmienne bazowe | Bezpłatni członkowie w ograniczeniach | Zmienne niepodstawowe | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b 1 | 11 | 12 | ... | 1l | ... | 1 n |
| xn+2 | b 2 | 21 | 22 | ... | 2l | ... | 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | r1 | r2 | ... | RL | ... | rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | bm | m1 | m2 | ... | ml | ... | amni |
| F(x)maks. | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Aby to zrobić, wybierz dowolny z ujemnych elementów kolumny wolnych członków (niech będzie to b 2 wiodące lub zezwalające. Jeśli w wierszu z ujemnym wolnym członkiem nie ma żadnych ujemnych elementów, system ograniczeń jest niespójny i problem nie ma rozwiązania.
Jednocześnie zmienna, która jako pierwsza zmienia znak wraz ze wzrostem wybranego NP x l, jest wyłączona z BP. Będzie to x n+r , którego indeks r jest wyznaczany z warunku
tych. zmienna odpowiadająca najmniejszemu stosunkowi wyrazu wolnego do elementu wybranej kolumny wiodącej. Ten związek nazywa się relacja simpleks. Należy brać pod uwagę tylko dodatnie relacje simpleksowe.
Ciąg odpowiadający zmiennej x n+r nazywa się prowadzenie lub przyzwolenie. Element tablicy simpleksowej a rl , który znajduje się na przecięciu wiodącego wiersza i wiodącej kolumny, nazywany jest elementem wiodącym lub rozstrzygającym. Znalezienie wiodącego elementu kończy pracę z każdym kolejnym tableau simplex.
Trzeci krok. Obliczana jest nowa tablica simpleks, której elementy są przeliczane z elementów tablicy simpleks z poprzedniego kroku i oznaczone liczbą pierwszą, tj. b" j , a" ji , c" i , F" 0 . Elementy są przeliczane według następujących wzorów:
Najpierw wiersz i kolumna, które prowadziły w poprzedniej tabeli simpleksowej, zostaną wypełnione w nowej tabeli simpleksowej. Wyrażenie (5) oznacza, że element a „rl w miejsce elementu wiodącego jest równy odwrotności elementu poprzedniej tablicy simpleksowej. Elementy wiersza a ri są dzielone przez element wiodący, a elementy tablicy kolumna a jl są również dzielone przez element wiodący, ale są brane z przeciwnym znakiem, elementy b" r i c" l są obliczane zgodnie z tą samą zasadą.
Pozostałe wzory można łatwo napisać za pomocą .
Prostokąt jest zbudowany według starej tablicy simpleksowej w taki sposób, że jedną z jego przekątnych tworzą elementy przeliczone (a ji) i wiodące (a rl) (rys. 1). Druga przekątna jest jednoznacznie określona. Aby znaleźć nowy element a „ji, iloczyn elementów o przeciwnej przekątnej, podzielony przez element wiodący, jest odejmowany od elementu a ji (wskazuje na to znak” - „w komórce). Podobnie elementy b” j, (j≠r) i c” i są przeliczane (i≠l).
Czwarty krok. Analiza nowej tablicy simpleksowej rozpoczyna się od pierwszego kroku algorytmu. Akcja trwa do momentu znalezienia możliwego do zrealizowania rozwiązania podstawowego, tj. wszystkie elementy kolumny wolnych członków muszą być dodatnie.
Piąty krok. Uważamy, że znaleziono akceptowalne rozwiązanie podstawowe. Przyglądamy się współczynnikom prostej funkcji celu F(x) . Oznaką optymalności tablicy simpleksowej jest nieujemność współczynników dla zmiennych niepodstawowych w rzędzie F.
Ryż. 1. Reguła prostokąta
Jeśli wśród współczynników rzędu F są ujemne (z wyjątkiem okresu wolnego), musisz przejść do innego podstawowego rozwiązania. Przy maksymalizacji funkcji celu, podstawą są zmienne niepodstawowe (np. x l), których kolumna odpowiada maksymalnej wartości bezwzględnej ujemnego współczynnika cl w dolnym wierszu tabeli simpleks. Pozwala to wybrać zmienną, której wzrost prowadzi do poprawy funkcji celu. Kolumna odpowiadająca zmiennej x l nazywana jest kolumną wiodącą. Jednocześnie ta zmienna x n+r jest wyłączona z bazy, której indeks r określa minimalny stosunek simpleks:
Wiersz odpowiadający x n+r nazywany jest wierszem wiodącym, a element tabeli simpleks a rl , który znajduje się na przecięciu wiersza wiodącego i kolumny wiodącej, jest nazywany wiodący element.
Szósty krok. zgodnie z zasadami określonymi w 3 kroku. Procedura trwa do momentu znalezienia optymalnego rozwiązania lub stwierdzenia, że ono nie istnieje.
Jeżeli w procesie optymalizacji rozwiązania w kolumnie wiodącej wszystkie elementy są niedodatnie, to nie można wybrać wiersza wiodącego. W tym przypadku funkcja w dziedzinie dopuszczalnych rozwiązań problemu nie jest ograniczona od góry i F max ->&∞.
Jeżeli w kolejnym kroku poszukiwania ekstremum jedna z podstawowych zmiennych staje się równa zeru, to odpowiednie rozwiązanie podstawowe nazywamy degeneracją. W tym przypadku występuje tzw. zapętlenie, które charakteryzuje się tym, że ta sama kombinacja BP zaczyna się powtarzać z określoną częstotliwością (w tym przypadku zachowana jest wartość funkcji F) i nie można przełączyć na nowe akceptowalne rozwiązanie podstawowe. Pętla jest jedną z głównych wad metody simplex, ale jest stosunkowo rzadka. W praktyce w takich przypadkach zwykle odmawia się wpisania do bazy zmiennej, której kolumna odpowiada maksymalnej wartości bezwzględnej ujemnego współczynnika w funkcji celu i dokonuje się losowego wyboru nowego rozwiązania podstawowego.
Przykład 1. Rozwiąż problem
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Metoda Simplex i dać geometryczną interpretację procesu rozwiązania.
Graficzną interpretację rozwiązania problemu przedstawiono na ryc. 2. Maksymalna wartość funkcji celu osiągana jest w górnej części ODZP ze współrzędnymi . Rozwiążmy problem za pomocą tablic simpleksowych. Mnożymy drugie ograniczenie przez (-1) i wprowadzamy dodatkowe zmienne, aby sprowadzić nierówności do postaci równości, a następnie
Początkowe zmienne x 1 i x 2 są traktowane jako niepodstawowe, a dodatkowe x 3 , x 4 i x 5 są uważane za podstawowe i kompilujemy tablicę simpleksową (tablica simpleks 2). Rozwiązanie odpowiadające tablicy simpleksowej. 2, jest nieważny; element wiodący jest zarysowany i wybrany zgodnie z krokiem 2 powyższego algorytmu. Następna zakładka simpleks. 3 określa dopuszczalne rozwiązanie podstawowe; 2 Element wiodący jest zarysowany i wybrany zgodnie z 5 krokiem algorytmu rozwiązania problemu. Patka. 4 odpowiada optymalnemu rozwiązaniu problemu, a więc: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; Fmaks = 20.
Ryż. 2. Graficzne rozwiązanie problemu
