078 079 2
78 Programowanie liniowe
Wykorzystując dualną metodę simpleks, wykonujemy kolejne iteracje simpleksowe. Wykonywane kroki ilustrują tablice 1.28 i 1.29.
Tablica 1.28
|
cx —» |
max |
2 |
3 |
0 |
0 |
0 |
0 |
h |
|
Baza |
Xi |
Xy |
XĄ |
Xs |
Xh | |||
|
X* |
0 |
0 |
0 |
i |
0 |
0 |
-2 |
-3 186 |
|
X, |
2 |
1 |
0 |
0 |
-1 |
0 |
2 |
3 192 |
|
JC5 |
0 |
0 |
0 |
0 |
4 |
1 |
-8 |
-12 752 |
|
x2 |
3 |
0 |
1 |
0 |
1 |
0 |
-1 |
-1 592 |
|
et |
-Z, |
0 |
0 |
0 |
-1 |
0 |
-1 |
1 608 |
Tablica 1.29
|
cx —> |
max |
2 |
3 |
0 |
0 |
0 |
0 |
b |
|
Baza |
CB |
*1 |
*2 |
Xy |
Xą |
x* |
*6 | |
|
x% |
0 |
0 |
0 |
i |
-i |
-0.25 |
0 |
2 |
|
x, |
2 |
1 |
0 |
0 |
0 |
-0,25 |
0 |
4 |
|
X(i |
0 |
0 |
0 |
0 |
-0,5 |
-0,13 |
1 |
1 594 |
|
*2 |
3 |
0 |
1 |
0 |
0,5 |
-0,13 |
0 |
2 |
|
cr |
- 7 ■ |
0 |
0 |
0 |
-1,5 |
-0,13 |
0 |
14 |
Otrzymane na początku trzeciej iteracji rozwiązanie jest dopuszczalne. Widzimy jednocześnie, że zmienna bilansująca sztucznego ograniczenia stała się ponow- j nie zmienną bazową, przy czym jej wartość wynosi:
jc6= 1600-je,-** =1594.
1.7.3. Zadanie sprzeczne
Po zaprezentowaniu w poprzedniej części rozdziału podstawowej wersji prymalnej metody simpleks zajęliśmy się szczególnymi przypadkami, m.in.: zadaniem sprzecznym, alternatywnym rozwiązaniem optymalnym oraz nieograniczoną funkcją celu. Rozpatrując takie same (lub bardzo podobne) przykłady, jak w podrozdziale 1.4, pokażemy, jak przypadki te rozpoznać dla dualnej metody simpleks. Rozpoczniemy od zadania sprzecznego.
Przykład 1.19
Rozwiążemy ponownie zadanie z przykładu 1.3, wykorzystując dualną metodę simpleks. Pierwsza tablica simpleksowa z dołączonym sztucznym ograniczeniem i po wyeliminowaniu z bazy zmiennej x7 ma postać (tablica 1.30):
Tablica 1.30
|
cx -> |
max |
2 |
3 |
0 |
0 |
0 |
0 |
0 |
b |
|
Baza |
Cli |
X, |
x2 |
Xą |
•*7 | ||||
|
Xi |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-2 |
-3 186 |
|
*4 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
-2 |
-3 192 |
|
*5 |
0 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
16 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 592 | |
|
*■> |
3 |
1 |
1 |
0 |
0 |
0 |
0 |
I |
1 600 |
|
Ci- |
-*/ |
-1 |
0 |
0 |
0 |
0 |
0 |
-3 |
4 800 |
Na początku trzeciej iteracji otrzymujemy tablicę (tablica 1.31):
aie. o U V mr
rrv
Tablica 1.31
|
cx -» |
max |
2 |
3 |
0 |
0 |
0 |
0 |
0 | |
|
Baza |
CB |
x, |
X* |
*4 |
x* |
*7 | |||
|
Xi |
0 |
0 |
0 |
i |
-1 |
-0,25 |
0 |
0 |
2 |
|
xt |
2 |
1 |
0 |
0 |
0 |
0.25 |
0 |
0 |
4 |
|
*7 |
0 |
0 |
0 |
0 |
-0.5 |
-0,13 |
0 |
1 '. |
1 594 |
|
Xf> |
0 |
0 |
0 |
0 |
0,5 |
0,13 |
1 |
0 |
-2 |
|
x2 |
3 |
0 |
1 |
0 |
0,5 |
-0,13 |
0 |
0 |
2 |
|
c,- |
-Zj |
0 |
0 |
0 |
-1,5 |
-0,13 |
0 |
0 |
14 |
Otrzymane rozwiązanie nie jest dopuszczalne, jednak ze względu na to, że \viersz odpowiadający zmiennej Xb nie zawiera elementu ujemnego, kryterium wejścia metody simpleks nie daje możliwości dalszej poprawy. Tak więc, jeżeli wszystkie elementy wiersza odpowiadającego zmiennej opuszczającej bazę są nieujemne, to rozpatrywane zadanie jest sprzeczne.
1.7.4. Nieograniczona funkcja celu
Obecnie zilustrujemy sytuację, gdy zbiór rozwiązań dopuszczalnych jest nieograniczony i funkcja celu również nie jest ograniczona.
Wyszukiwarka
Podobne podstrony:
078 079 78 Anna Kamińska. Artur Gas Zadanie 2 Zbadać stabilność układu opisanego równaniem
078 079 78 Zamiana układu Moore a aa układ Mealy ego przebiega następująooi 1) wew
078 079 78 Anna Kamińska. Artur Gas Zadanie 2 Zbadać stabilność układu opisanego równaniem
[BADANIA OPERACYJNE - PROGRAMOWANIE LINIOWE] Koszalin 20062 Metoda simpleks 2.1 Wstęp Metoda ta poma
106 107 2 106 Programowanie liniowe całkowitoliczbowe leks, a także metodę geometryczną, moż.na wyko
072 073 2 72 Programowanie liniowe Maksymalne zwiększenie wykorzystania środka S2 pozwala na uzyskan
DSC00204 7. METODA PROGRAMOWANIA LINIOWEGO ładnym / częściej wykorzystywanych modeli decyzyjnych jc«
■Zagadnienie transportowe - specjalny rodzaj Programowania Liniowego (PL) -wykorzystywane w chwili,
2. Zastosowanie programowania liniowego w praktyce Wiele gałęzi przemysłu wykorzystuje w swojej
2.4.1. Postać bazowa Aby zastosowań metodę simpleks, należy zadanie programowania liniowego zadanego
image 079 Jednorodny szyk liniowy anten 79 sposobu zasilania anteny. Jeśli więc wszystkie anteny są
Slajd3 (10) Modele obliczeń równoległych - perspektywa programisty (2/2) 1. Model
Slajd5 (25) Modele obliczeń równoległych - perspektywa programisty (2/2) 1. Model
DOOATEK A ZASADA DUALNOŚCI Wełny pod uwagę zodonle programowanie liniowego (pi t r-w o t n o); Należ
Tabela 11 przedstawia liczbę komputerowych programów edukacyjnych wykorzystywanych przez szkolę w dy
P1000653 (2) 38. Opisz z wykorzystaniem rysunku metodę wyznaczania OSC człowieka p
więcej podobnych podstron