074 075 2

Programowanie liniowe

Kryterium wejścia

Obliczamy ilorazy wartości wskaźników optymcilności przez odpowiadające im elementy wiersza dla zmiennej opuszczającej bazą [((ej— zj): «/,)' dla tych elementów rozpatrywanego wiersza, które są ujemne. Do bazy wchodzi ta zmienna, dla której wartość bezwzględna odpowiactdjąĆegO~jej ilorazu jest najmniejsza. Jeżeli jest więcej niż jedna najmniejsza wartość tego ilorazu, to wybieramy zmienną o najniższym numerze.

Przykład 1.17

Przedstawimy kolejne kroki dualnej metody simpleks, rozwiązując zadanie otrzymane w przykładzie 1.12.

Iteracja 1

Sprawdzamy, czy spełnione jest kryterium dopuszczalności. Ponieważ rozpatrywane rozwiązanie nic jest dopuszczalne (tablica 1.23), więc zgodnie z kryterium wyjścia wybieramy zmienną ys jako zmienną opuszczającą bazę. Tworzymy ilorazy wykorzystywane w kryterium wejścia, otrzymując następujące wartości:

dla zmiennej yi |l4:(-2)|=7, dla zmiennej j>2 I B: (— 2)1 =4,

i wybieramy mniejszą z nich, czyli wartość 4. Zmienną wchodzącą do bazy jest y2. Po wykonaniu odpowiednich przekształceń elementarnych otrzymujemy tablicę 1.24.

Iteracja 2

Tablica 1.24

CX —j	min	14	8	16	0	0	1)
Baza				y^	>4	y>
,V4	0	-1	0	-4	1	-0,5	-0,5
,v2	8	1	i	0	0	-0,5	1.5
<■7-		6	0	16	0	4	12

Sprawdzamy, czy spełnione jest kryterium dopuszczalności. Rozwiązanie _r bazowe z tablicy 1.24 wciąż nie jest dopuszczalne. Jedyną zmienną, która może opuścić bazę, jest zgodnie z kryterium wyjścia zmienna y₄. Tworzymy ilorazy wykorzystywane w kryterium wejścia, otrzymując:

j

dla zmiennej y, I 6: (- 1) | =6, dla zmiennej y₃ |l6:(-4)|=4, dla zmiennej y₅ 14: (-0,5) | = 8,

i wybieramy najmniejszą z nich, czyli wartość 4. Zmienną wchodzącą do bazy jest y₃. Po wykonaniu odpowiednich przekształceń elementarnych otrzymujemy tablicę 1.25.

Iteracja 3

Tablica 1.25

CX —i	min	14	8	16	0	0
Baza	Cl$	>’l	y2	y>	y*	*
*	16	0	0	i	-0,25	0,125	0.125
yi	8	1	1	0	0	-0,5	1.5
cr	"Zr	2	0	0	4	2	14

Sprawdzamy, czy spełnione jest kryterium dopuszczalności. Rozwiązanie przedstawione w tablicy 1.25 jest poszukiwanym rozwiązaniem optymalnym i dopuszczalnym:

yi =0, y₂= 1,5, y, = 0,125, y_A = 0, y_s = 0.

Dysponując bazowym rozwiązaniem dopuszczalnym i optymalnym oraz odpowiadającymi mu wskaźnikami optymalności jednego z problemów, prymal-nego lub dualnego, można wyznaczyć bazowe rozwiązanie optymalne i wskaźniki optymalności drugiego z nich. Możliwość tę omówimy, korzystając z zadań rozważanych w przykładzie 1.12. Z twierdzenia o komplementarności wiemy, że zmienna x, jest komplementarna do pierwszego warunku ograniczającego w zadaniu dualnym, który z kolei określa zmienną bilansującą y₄ w tym zadaniu. Możemy więc uznać, że zmienne jc, i y₄ są komplementarne. Rozpatrując dalsze zależności tego typu, stwierdzamy, że zmiennymi komplementarnymi są:

*i i y*, *2 i y_s.

y\,

yi,

*s i y₃.

Przyjrzyjmy się ponownie tablicy 1.25. W rozwiązaniu optymalnym zadania dualnego, otrzymanego dualną metodą simpleks, wskaźniki optymalności dla zmiennych niebazowych y,, y₄ i y₅ wynoszą, odpowiednio, 2, 4 i 2, są więc równe wartościom optymalnym zmiennych komplementarnych x₃, x, i x₂ zadania prymai-

Wyszukiwarka

Podobne podstrony:
036 037 2 I I 36 Programowanie liniowe ? Kryterium optymalności dla zadania maksymalizacji Jeżeli wa
074 075 74 ^ ‘a przschodniości relacji niesprzeczności. Proces ten przedstawiony Jest na rys. 3>6
092 093 2 92 Programowanie liniowe Chcąc ustalić, dla jakich wartości / otrzymana baza, w skład któr
Zagadnienie programowania liniowego □    Dla rozwiązań optymalnych wartości funkcji
Jedna z klasycznych zasad programowania mówi, że używanie obliczeń za pomocą wskaźników jest szybsze
DSC77 Kryterium wyjścia Obliczamy ilorazy kolejnych wyrazów wolnych przez odpowiadające im elementy
DSC79 Kryterium wyjścia Obliczamy ilorazy kolejnych wyrazów walnych przez odpowiadające im elementy
Ekologia (1) Obliczyć i porównać wartości wskaźników wzrostu pasożyta Trichomonas vaginatis, w warun
Splot kołowy W trakcie obliczania splotu liniowego sygnał wejściowy x (n) traktowany byt jako sygnał
image 086 86 Szyki antenowe liniowe i planarne Z (5.36) obliczamy kierunkowość szyku o zadanej szero
Slajd13 (37) Model programowania w PVM (2/2) T2-2 - Modele obliczeń rozproszonych Marek Nowak 13
Slajd7 (10) Model programowania w PVM (2/2) 72 2- Modele obliczeń rozproszonych Marek Nowak 7
Zdjęcie0576 AU. 74. . Programy komputerowe podlegają ochronie Jak utwory literackie. o Re przepity m
DOOATEK A ZASADA DUALNOŚCI Wełny pod uwagę zodonle programowanie liniowego (pi t r-w o t n o); Należ
Strona11 5.2. Obliczanie współczynnika przenikania ciepła przegród bez mostków liniowych Zasada met

więcej podobnych podstron