074 075 2

74

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.

*3

x₄

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-