Dwufazowe metody rozwiązywania problemów w programowaniu liniowym: pierwsza i druga faza
W tej metodzie problem rozwiązano w dwóch fazach, jak podano poniżej.
Pierwsza faza:
(a) Wszystkie warunki na RHS powinny być nieujemne. Jeśli niektóre z nich są -ve, to muszą być wykonane, tak jak wyjaśniono wcześniej.
(b) Ograniczenia ekspresowe w standardowej formie.
(c) Dodaj sztuczne zmienne w ograniczeniach równości lub (>) ograniczeniach typu.
(d) Tworzą nową funkcję celu W, która składa się z sumy wszystkich sztucznych zmiennych
W = A 1 + A 2 + ........................ + A m
Funkcja (W) jest znana jako forma niewykonalności.
(e) Funkcja W ma być zminimalizowana, z zastrzeżeniem ograniczeń pierwotnego problemu i otrzymuje się optymalne podstawowe możliwe rozwiązanie.
Mogą wystąpić dowolne z następujących trzech przypadków:
(Jestem w. W> 0 i co najmniej jedna sztuczna zmienna pojawia się w kolumnie "Podstawowe zmienne" na poziomie Pozytyw. W takim przypadku nie istnieje możliwe rozwiązanie pierwotnego LPP i procedura zostaje zatrzymana.
(ii) Min. W = 0 i co najmniej jedna sztuczna zmienna pojawia się w kolumnie "Podstawowe zmienne" na poziomie zerowym. W takim przypadku optymalne, podstawowe, wykonalne rozwiązanie formy nieefektywności może, ale nie musi być podstawowym wykonalnym rozwiązaniem dla danego (oryginalnego) LPP Aby uzyskać podstawowe możliwe rozwiązanie, kontynuujemy fazę I i staramy się wyprzeć wszystkie sztuczne zmienne z podstawę, a następnie przejść do fazy II.
(iii) Min. W = 0 i brak sztucznej zmiennej pojawia się w kolumnie "Podstawowe zmienne" bieżące rozwiązanie ". W takim przypadku znaleziono podstawowe możliwe rozwiązanie pierwotnego LPP. Przejdź do fazy II.
Druga faza:
Użyj optymalnego, podstawowego, wykonalnego rozwiązania fazy I, jako początkowego rozwiązania dla oryginalnego LPP. Używając metody simpleks, wykonuj iteracje, aż uzyskasz optymalne, podstawowe, wykonalne rozwiązanie.
Można zauważyć, że nowa funkcja celu W jest zawsze typu minimalizacji, niezależnie od tego, czy dany (oryginalny) LPP ma typ maksymalizacji czy minimalizacji. Weźmy następujący przykład.
Przykład 1 (dwufazowa metoda simpleksowa):
Użyj dwufazowej metody simpleks do
Minimalizuj Z = -3X - 2Y - 2Z
Z zastrzeżeniem 5X + 7Y + 4Z <7
-4X + 7Y + 5Z> -2
3X + 4 V - 6Z> 29/7
X, Y, Z> 0
Rozwiązanie:
Pierwsza faza
Składa się z następujących kroków.
(a) W drugim ograniczeniu, RHS jest -ve, dlatego jest on wprowadzany + ve przez pomnożenie przez znak minus po obu stronach
4X - 7Y - 5Z <2
(b) Dodawanie zmiennych luzu w ograniczeniach
5X + 7Y + 4Z + S 1 = 7
4X - 7Y - 5Z + S 2 = 2
3X + 4Y - 6Z - S 3 = 29/7
gdzie X, Y, Z, S 1, S 2, S 3 > 0
(c) Put X = Y = Z = 0, otrzymujemy S 1 = 7, S 2 = 2, S 3 = -29/7. jako wstępne rozwiązanie. Ale seria S 3 to -ve, dodamy sztuczną zmienną A, czyli
3X + 4Y- 6Z-S 3 + A 1 = 29/7
(d) Funkcja celu, która jest typem minimalizacji, jest tworzona jako typ maksymalizacji, tj
Maksymalizuj Z = 3X + 2Y + 2Z
(e) Wprowadzamy nową funkcję celu W = A 1 dla pierwszej fazy, która ma być zminimalizowana.
(f) Podstawienie X = Y = Z = S 3 = 0 w ograniczeniach otrzymujemy S 1 = 7, S 2 = 2, / A 1 = 29/7 jako początkowe podstawowe wykonalne rozwiązanie Tabela 1, jeśli jest utworzona.
Preformowany test optymalności
Ponieważ Cj-Ej jest ujemny pod tymi samymi kolumnami (problem minimalizacji), obecne podstawowe możliwe rozwiązanie może zostać poprawione.
Iteracja i optymalne rozwiązanie:
Wykonanie iteracji w celu uzyskania optymalnego rozwiązania.
Zamień S 1 na X 2 . jest to pokazane w tabeli poniżej
W tabeli znajduje się remis dla wiersza klucza X kolumna jest kolumną kluczową, a kolumna y jest pierwszą kolumną tożsamości. Po metodzie rozbijania wiązań stwierdzamy, że kolumna y nie przerywa remisu. Następna kolumna tożsamości, tj. Kolumna S 2, daje A- 1 jako kluczowy wiersz. Tak więc (1/7) kluczowym elementem jest jedność w tabeli
Zastąp symbol A 1 symbolem X, jak pokazano w tabeli poniżej
Tabela 5 przedstawia optymalne rozwiązanie. Również od minimalnego W = 0 i nie ma sztucznej zmiennej w podstawowych zmiennych, tj. W bieżącym rozwiązaniu, tablica 5 daje podstawowe możliwe rozwiązanie dla fazy-ll
Druga faza:
Oryginalną funkcją celu jest
Maksymalizuj Z = 3x + 2y + 2Z + OS, + 0S 2 + 0S 3
Ma być zmaksymalizowany przy użyciu oryginalnych ograniczeń. Wykorzystując rozwiązanie fazy I jako rozwiązanie początkowe dla fazy II i wykonując obliczenia za pomocą algorytmu simpleks, otrzymujemy tabelę 6
Kluczowym elementem jest jedność w tabeli7
Zamień S 2 na X 3 .
