Simplex Metoda programowania liniowego

Simplex Metoda programowania liniowego!

Każdy problem programowania liniowego z udziałem dwóch zmiennych można łatwo rozwiązać za pomocą metody graficznej, ponieważ łatwiej jest radzić sobie z dwuwymiarowym wykresem. Wszystkie możliwe rozwiązania w formie graficznej znajdują się w możliwym do wykonania obszarze na wykresie i wykorzystaliśmy do przetestowania punktów narożnych możliwego obszaru pod kątem optymalnego rozwiązania, tj. Jednym z punktów narożnych możliwej powierzchni był optymalne rozwiązanie. Sprawdzaliśmy wszystkie punkty narożne, umieszczając te wartości w funkcji celu.

Ale jeśli liczba zmiennych wzrasta z dwóch, bardzo trudno jest rozwiązać problem, rysując jego wykres, ponieważ problem staje się zbyt złożony. Metoda Simplex została opracowana przez GB Dantzig, amerykańskiego matematyka.

Ta metoda jest matematycznym traktowaniem metody graficznej. Tutaj również różne punkty narożne możliwego obszaru są testowane pod kątem optymalności. Ale nie jest możliwe przetestowanie wszystkich punktów narożnych, ponieważ liczba punktów narożnych zwiększa liczbę kolektorów, gdy liczba równań i zmiennych wzrasta. Maksymalna liczba tych punktów do przetestowania może być

m + n m = m + 1! / m! n!

gdzie m to liczba a, n to liczba zmiennych.

W metodzie simpleks liczba punktów narożnych do testowania jest znacznie zredukowana dzięki zastosowaniu bardzo skutecznego algorytmu, który prowadzi nas do optymalnego punktu narożnego rozwiązania w zaledwie kilku iteracjach. Weźmy jeden przykład i przejdźmy krok po kroku.

Celem funkcji jest maksymalizacja Z = 12x 1 + 15x 2 + 14x 3

Z zastrzeżeniem warunków

Krok 1:

(a) Prawa strona wszystkich ograniczeń musi wynosić zero lub + ve. Jeśli są one -ve, to muszą zostać uczynione + ve przez pomnożenie obu stron przez (-1), a znak nierówności zostanie odwrócony. W tym przykładzie RHS jest już + ve lub zero.

(b) Wszystkie nierówności są przekształcane na równości przez dodawanie lub odejmowanie zmiennych zwłoki lub nadwyżki. Te zmienne luźne lub nadmiarowe zostały wprowadzone, ponieważ łatwiej jest radzić sobie z równościami niż nierówności w traktowaniu matematycznym.

Jeśli ograniczenie jest typu ≤, zmienne luzu są dodawane, jeśli ograniczenie jest typu ≥, wówczas odejmuje się zmienną dodatkową. Tutaj luźne zmienne s, s 2 i s 3 dodaje się w trzech w równościach (i), (ii) i (iii), otrzymujemy.

I funkcja celu staje się

Maksymalizuj Z = 12x 1 + 15x 2 + 14x 3 + os 1 + os 2 + os 3

Krok 2:

Znajdź początkowe podstawowe możliwe rozwiązanie:

Rozpoczynamy od wykonalnego rozwiązania, a następnie przechodzimy do optymalnego rozwiązania w kolejnych iteracjach. Początkowe wykonalne rozwiązanie jest korzystnie wybrane jako źródło, tj. Gdzie zwykłe zmienne, np. W tym przypadku xv2, x3 przyjmują wartości zerowe. tj. x 1 x 2, x 3 = 0

a otrzymamy s 1 = 0, s 2 = 0 i s 3 = 100 z nierówności (i), (ii) i (iii)

Zmienne podstawowe to zmienne znajdujące się obecnie w rozwiązaniu, np. S v S 2 i S 3 to podstawowe zmienne w początkowym rozwiązaniu.

Zmienne nieoznaczone to zmienne, które są ustawione na zero i nie znajdują się w bieżącym rozwiązaniu, np. X 1, a x 2 i x 3 są zmiennymi innymi niż podstawowe w rozwiązaniu początkowym.

Powyższe informacje można wyrazić w tabeli 1

W tabeli pierwszy wiersz reprezentuje współczynniki funkcji celu, drugi wiersz reprezentuje różne zmienne (pierwsze zmienne regularne, a następnie zmienne luzu / nadwyżki). Trzeci czwarty i piąty rząd reprezentuje współczynniki zmiennych we wszystkich ograniczeniach.

Pierwsza kolumna przedstawia współczynniki podstawowych zmiennych (bieżące zmienne rozwiązania) w celu (ei) druga kolumna przedstawia podstawowe zmienne (bieżące zmienne rozwiązania), a ostatnia kolumna przedstawia prawostronne ograniczenia w standardowej postaci. Tj po przeciążeniu wszystkich nierówności w równości, w dowolnej tabeli, bieżące wartości bieżących zmiennych rozwiązania (zmienne podstawowe) podane są przez RHS

W tabeli 1 obecne rozwiązanie to:

S 1 = 0, S 2 = 0, S 3 = 100

Oczywiście nie podstawowe zmienne X v X 2 i X 3 również będą zerowe

Degeneracja, gdy dowolna zmienna podstawowa przyjmuje wartości zerowe, uważa się, że obecne rozwiązanie jest zdegenerowane, ponieważ w obecnym problemie S 1 = 0 i S 2 = 0 problem można dalej rozwiązać, zastępując S 1 = t i S 2 = t, gdzie t jest bardzo mała + ve liczba.

Krok 3:

Test optymalności.

Test optymalności można wykonać, aby sprawdzić, czy obecne rozwiązanie jest optymalne, czy nie. W tym pierwszym wpisz ostatni wiersz w postaci (E j ) gdzie

Ej = Σ ei. A ij.

Gdzie ij reprezentuje współczynniki w macierzy tożsamości ciała dla ith wiersza i kolumny jth, tj. Reprezentuje pierwszą kolumnę tabeli. W ostatnim wierszu wpisz wartość (Cj - Ej) gdzie c ; reprezentuje wartości z pierwszego rzędu, a E j oznacza wartości z ostatniego rzędu. (Cj - Ej) stanowi zaletę polegającą na wprowadzeniu dowolnej zmiennej niearasadowej do bieżącego rozwiązania, tj. Poprzez uczynienie jej podstawową.

W tabeli 2 wartości Cj - Ej wynoszą 12, 15 i 14 dla X v X 2 i X 3 . Jeśli którakolwiek z wartości Cj - Ej jest równa, to oznacza, że ​​większość wartości dodatnich reprezentuje zmienną, która zostanie wprowadzona do bieżącego rozwiązania, w celu maksymalnego zwiększenia funkcji celu. W obecnym przypadku X 2 jest potencjalną zmienną wchodzącą w skład rozwiązania do następnej iteracji. Jeśli wszystkie wartości w wierszu (Cj - Ej) są ujemne, oznacza to, że osiągnięto optymalne rozwiązanie.

Krok 4:

Iteruj w kierunku rozwiązania optymalnego:

Maksymalna wartość Cj - Ej daje Kolor klucza jak zaznaczono w Tabeli

Dlatego X 2 jest zmienną wejściową, tzn. Stałaby się podstawowa i wchodziłaby w rozwiązanie. Z istniejącej nie-podstawowej zmiennej, i trzeba wyjść i stać się nie-podstawowym. Aby dowiedzieć się, która zmienna ma zostać wyrzucona, dzielę współczynniki w kolumnie RHS przez odpowiednie współczynniki w kolumnie klucza, aby uzyskać kolumnę Ratio. Teraz szukaj najmniejszej wartości dodatniej w kolumnie Ratio, która dałaby wiersz klucza. W obecnym problemie mamy trzy wartości, tj. T, μ i 100, a spośród nich t jest najmniej + ve. Dlatego wiersz odpowiadający t w kolumnie Ratio będzie wierszem klucza. A S. byłaby zmienną opuszczającą. Element na przecięciu rzędu klawiszy i klucza jest kluczowym elementem.

Teraz wszystkie elementy w kluczu koloru, oprócz elementu kluczowego, mają być zerem, a kluczowym elementem ma być jedność. Odbywa się to za pomocą operacji na wierszach, ponieważ gotowe są macierze. Tutaj kluczowym elementem jest już jedność, a inny element w kluczowym kolerze jest zerowany przez dodanie -1 razy pierwszego rzędu w trzecim rzędzie i uzyskanie następnej tabeli.

Dlatego powstaje drugie możliwe rozwiązanie

X 1 = 0, X 2 = t i X 3 = 0 tam o z = 15t

W nowej tabeli s 1 został zastąpiony przez X 2 w podstawowych zmiennych i odpowiednio zmieniono także barwę ei.

Krok 5:

Patrząc na wartości Cj-Ej w Tabeli 3, stwierdzamy, że x 1 ma większość wartości + ve równej 27, wskazując tym samym, że rozwiązanie można jeszcze poprawić poprzez wprowadzenie x 1 do rozwiązania, tj. Przez uczynienie go podstawowym. Dlatego x 1 coloumn jest kluczową kolumną, znajdź także wiersz klucza, jak wyjaśniono wcześniej i wypełnij tabelę 5.

Kluczowy element w Tabeli 5 wychodzi na 2 i tworzy jedność, a wszystkie pozostałe elementy w kluczowym kole są zerowane za pomocą operacji na wierszach i wreszcie otrzymujemy tabelę 6. Pierwszym kluczowym elementem jest uczynienie jedności przez podzielenie tego rzędu przez 2. Następnie, dodając odpowiednie wielokrotności tego rzędu w innych wierszach, otrzymamy tabelę 6.

Z tabeli 6 widać, że nadal rozwiązanie nie jest optymalne, ponieważ Cj-Ej nadal ma wartości + ve 1/2 daje to kluczowy kolor i znajduje się odpowiedni wiersz klucza, kluczowy element jest taki jak podano w tabeli 7

Teraz, poprzez odpowiednie operacje na wierszach, pozostałe elementy w kluczowym kolorze wynoszą zero, jak pokazano w Tabeli 8.

Można zauważyć, że ponieważ wszystkie wartości w rzędzie Cj-Ej są albo -ve albo zero, optymalne rozwiązanie zostało osiągnięte.

Ostateczne rozwiązanie to x 1 = 40 ton

x 2 = 40 ton

x 3 = 20 ton

ponieważ t jest bardzo małe, jest zaniedbane.

Przykład 1:

Rozwiąż następujący problem metodą simplex

Maksymalizuj Z = 5x 1 + 4x 2

Z zastrzeżeniem 6x 1 + 4x 2 ≤ 24

x 1 + 2x 2 ≤ 6

-x 1 + x 2 ≤ 1

x 2 ≤ 2

i x 1 x 2 ≥0

Rozwiązanie:

Dodaj zmienne luzu S 1, S 2, S 3, S 4 w czterech wiązaniach, aby usunąć nierówności.

Otrzymujemy 6x 1 + 4x 2 + s 1 = 24

x 1 + 2x 2 + s 2 = 6

-x 1 + x 2 + s 3 = 1

x 2 + s 4 = 2

Z zastrzeżeniem x 1, x 2, s 1, s 2, s 3 i s 4 > 0

Funkcja celu staje się

Maksymalizuj Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4

Powstałą poniżej tabelę 1 podano. Widać, że X 1 jest zmienną wejściową, a S jest zmienną opuszczającą. Kluczowym elementem w tabeli 1 jest jedność, a wszystkie pozostałe elementy w tym kolorze są zerowane.

Z tabeli 2 może wynikać, że X 2 jest zmienną wejściową, a S 2 jest zmienną opuszczającą.

Z tabeli 5 widać, że wszystkie wartości rzędu Cj-Ej wynoszą -ve lub zero. W związku z tym otrzymano optymalne rozwiązanie.

Rozwiązanie to x 1 = 3, x 2 = 3/2

Z max = 5x 3 + 4x = 3/2

= 15 + 6 = 21 Ans.

Duża metoda M

Weźmy następujący problem, aby zilustrować metodę Big M-.

Minimalizuj Z = 2y 1 + 3y 2

podlega ograniczeniom y 1 + y 2 ≥ 5

y 1 + 2y 2 ≥ 6

y 1, y 2 ≥ 0

Konwersja do formularza standardowego:

Maksymalizuj Z = -2y 1 - 3y 2 + Os, + 0s 2

Problem minimalizacji jest konwertowany na problem maksymalizacji poprzez pomnożenie RHS funkcji celu przez -1.

Ograniczenia y 1 + y 2 - s 1 = 6 ... (i)

y, + y 2 - s 2 = 6 ... (ii)

y 1 y 2, s 1 s 2 ≥ 0

Tutaj nadmiarowe zmienne s1, s2 i odejmowane odpowiednio od ograniczeń (i) i (ii).

Teraz y 1, y 2 mogą być przyjmowane jako zmienne inne niż podstawowe i równe zero, aby uzyskać s v s 2 jako zmienne podstawowe, gdzie s 1 = -5, s 2 = -6.

Jest to rozwiązanie nieopłacalne, ponieważ nadmiarowe zmienne s 1 i s 2 mają wartości get -ve. Aby przezwyciężyć ten problem, dodajemy sztuczne zmienne A 1 i A 2 w eqn. (i) i (ii) odpowiednio, aby uzyskać

y 1 + y 2 -s 1 + A 1 = 5 ... (iii)

y 1 + 2y 2 - s 2 + A 2 = 6 ... (iv)

Gdzie y 1 y 2, s 1, s 2, A 1, A 2 ≥ 0

i funkcja celu staje się

Maksymalizuj Z 1 = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2

Można zauważyć, że celowo zastosowaliśmy bardzo surowe kary do sztucznych zmiennych w funkcji celu w postaci -MA1 i MA2, gdzie M jest bardzo dużą liczbą dodatnią. Celem jest, aby sztuczne zmienne pojawiły się początkowo w wyjściowym podstawowym rozwiązaniu.

Ponieważ zmienne sztuczne zmniejszają funkcję celu w bardzo dużym stopniu w przypadku kar, algorytm simpleks wyprowadza sztuczne zmienne z rozwiązania w początkowych iteracjach, a zatem sztuczne zmienne, które wprowadziliśmy, aby rozwiązać problem, nie pojawiają się w ostatecznym rozwiązanie. Sztuczne zmienne są tylko urządzeniem obliczeniowym. Utrzymują równanie wyjściowe w równowadze i dostarczają matematycznej sztuczki do uzyskania początkowego rozwiązania.

Początkowa tabela staje się

Ponieważ Cj-Ej ma wartość + ve w niektórych kolumnach, rozwiązanie podane w Tabeli 1 nie jest optymalne. Można zauważyć, że z -2 + 2M i -3 + 3M, -3 + 3M jest najbardziej + ve, ponieważ M jest bardzo dużą liczbą + ve. Kluczowy element został znaleziony, jak pokazano w tabeli 1 i utworzono jedność, a wszystkie pozostałe elementy w tej kolumnie są zerowane. Otrzymujemy tabelę 2.

Z tabeli 2 można zauważyć, że optymalne rozwiązanie nie zostało jeszcze osiągnięte i istnieje lepsze rozwiązanie. Y 1 jest zmienną wejściową, a A 1 jest zmienną wychodzącą. Otrzymujemy tabelę 3.

Z tabeli 3 można wywnioskować, że optymalne rozwiązanie osiągnęło rozwiązanie

Y 1 = 4, Y 2 = 1

Minimalna wartość Z = 2x 4 + 3x 1 = 11 jednostek Ans.

Nieograniczone rozwiązanie:

Mówi się, że problem programowania liniowego ma nieograniczone rozwiązanie, gdy w kolumnie stosunek dostajemy wszystkie pozycje -ve lub zero i nie ma wpisu + ve. Oznacza to, że wartość zmiennej przychodzącej wybranej z klucza może być tak duża, jak nam się podoba, bez naruszania możliwego warunku i mówi się, że problem ma nieograniczone rozwiązanie.

Nieskończona liczba rozwiązań:

Mówi się, że problem programowania liniowego ma nieskończoną liczbę rozwiązań, jeśli podczas dowolnej iteracji, w wierszu Cj-Ej, mamy wszystkie wartości zerowe lub -ve. Pokazuje, że osiągnęła optymalną wartość. Ponieważ jednak jedna z normalnych zmiennych ma zerową wartość w rzędzie Cj-Ej, można stwierdzić, że istnieje alternatywne, optymalne rozwiązanie.

Przykład tego typu tabeli podano poniżej.

Można zauważyć, że optymalne rozwiązanie zostało osiągnięte, ponieważ wszystkie wartości w wierszu Cj-Ej są zerem lub -ve Ale X 1 jest zmienną nie podstawową i ma zerową wartość w wierszu Cj-Ej, wskazuje, że X, może zostać doprowadzone do rozwiązanie, jednak nie zwiększy to wartości funkcji celu i istnieje alternatywna optymalna.

Case of No. Wykonalne rozwiązanie:

W niektórych LPP można zauważyć, że podczas rozwiązywania problemu ze zmiennymi sztucznymi, rząd Cj-Ej pokazuje, że optymalne rozwiązanie zostało osiągnięte, podczas gdy wciąż mamy zmienną sztuczną w obecnym rozwiązaniu mającą wartość + vp. W takich sytuacjach można stwierdzić, że problem nie ma żadnego możliwego rozwiązania w ogóle.

Przykład 2:

Rozwiązanie:

Aby rozwiązać problem, sztuczne zmienne będą musiały zostać dodane w LHS, aby uzyskać początkowo podstawowe, możliwe do wykonania rozwiązanie. Wprowadźmy zmienne sztuczne A 1, A 2, A 3, powyższe ograniczenia można zapisać jako.

Teraz, jeśli te sztuczne zmienne pojawią się w ostatecznym rozwiązaniu dzięki kilku dodatnim wartościom, wówczas równość równania (i), (ii) lub (iii) zostanie zakłócona. Dlatego chcemy, aby sztuczne zmienne nie pojawiały się w ostatecznym rozwiązaniu, dlatego też stosujemy dużą karę w funkcji celu, którą można zapisać jako.

Maksymalizuj Z = Y, + 2Y 2 + 3Y 3 - Y 4 - MA, - MA 2 - MA 3

Teraz, jeśli bierzemy Y 1 Y 2, y 3 i y 4 jako zmienne inne niż podstawowe i wstawiamy Y 1 = Y 2 = y 4 = 0, otrzymamy rozwiązanie początkowe jako A 1 = 15, A 2 = 20 i A 3 = 10 a A 1, A 2, A 3 i A 4 to podstawowe zmienne (zmienne w bieżącym rozwiązaniu), od których należy zacząć. Powyższe informacje można umieścić w tabeli 1.

AS Cj- Ej jest dodatnie, obecne rozwiązanie nie jest optymalne i dlatego istnieje lepsze rozwiązanie.

Iteruj w kierunku optymalnego rozwiązania

Wykonanie iteracji w celu uzyskania optymalnego rozwiązania, jak pokazano w tabeli poniżej

Ponieważ Cj-Ej ma wartość zerową lub ujemną we wszystkich kolumnach, uzyskano optymalne podstawowe wykonalne rozwiązanie. Optymalne wartości to

Y 1 = 5/2, Y 2 = 5/2, Y 3 = 5/2, Y4 = 0

Również A 1 = A 2 = 0 i Z max = 15 Ans.