202 203

202 Metody wielokryterialne

stąd otrzymujemy następujący układ warunków:

2A, - 2Ar 0,

3A., - 2X2 = 0,

X | + At — 1 ,

a, >0, a^o,

którego rozwiązaniem jest A, =%, X? =%. Oznacza to, że zmienna x₂ jest w rozpatrywanej bazie niebazową zmienną sprawną.

Stosując kryterium wyjścia prymalnej metody simpleks do zadania zapisanego w tablicy 4.1, stwierdzamy, że zmienną usuwaną z bazy jest x₃. Po wykonaniu odpowiedniego przekształcenia elementarnego otrzymujemy tablicę 4.2.

Tablica 4.2

Cx -»	„max”	2 -2	3 -2	0 0	0 0	b
Baza	C»		^x2	Xy	X4
	3 -2	0,5	1	0,5	0	4
*4	0 0	4	0	0	1	16
		0.5	0	-1,5	0	0
tl„=(	•j ~ Ztj	-1	0	1	0	0

Tak więc wykorzystując niebazową zmienną sprawną x₂. możemy przejść od sprawnego rozwiązania wierzchołkowego, odpowiadającego wierzchołkowi O do sąsiedniego sprawnego rozwiązania bazowego, odpowiadającego wierzchołkowi A.

Liczba bazowych rozwiązań sprawnych jest oczywiście skończona. O możliwości ich wygenerowania przesądza twierdzenie sformułowane poniżej.

Twierdzenie 4.5

Każde dwa bazowe rozwiązania .sprawne można połączyć ciągiem sąsiednich baz sprawnych.

Wykorzystamy powyższe twierdzenie do wygenerowania pozostałych wierzchołków sprawnych. Punktem wyjścia był wierzchołek O. Okazało się, że zmienna x, nie jest niebazową zmienną sprawną, nie będzie więc dalej brana pod uwagę, natomiast wykorzystując niebazową zmienną sprawną x₂ uzyskaliśmy sprawny wierzchołek A. W ten sposób wyczerpaliśmy wszystkie możliwości generowania dalszych wierzchołków sprawnych, wynikających z analizy wierzchołka O, przechodzimy więc do rozpatrywania możliwości generowania dalszych wierzchołków sprawnych, związanych z wierzchołkiem A.

Z tablicy 4.2 odczytujemy otrzymane rozwiązanie bazowe:

a*j = 0, x₂ = 4, x₃ = 0, a'₄ = 16.

Zmiennymi nicbazowymi są x, oraz x,. Z wcześniejszych rozważań wiemy, że zmienna x, jest niebazową zmienną sprawną i pozwala na przejście do wierzchołka Os co nie jest już dla nas interesujące, gdyż stwierdziliśmy, że wszystkie możliwości generowania wierzchołków sprawnych dla wierzchołka O zostały wyczerpane. Sprawdzimy teraz, czy zmienna a, jest niebazową zmienną sprawną. Dla rozpatrywanej bazy mamy:

0,5 -1,5		0,5
	, d,=
-1 1		-1

stąd otrzymujemy następujący układ warunków:

0,5X., - X₂ = 0,

-1,5X, + ^,<0,

X| + ^2 ⁼ 1 >

x,>0, ^>0,

którego rozwiązaniem jest X, =³/„    = V_y Oznacza to, że zmienna x₂ jest w roz

patrywanej bazie niebazową zmienną sprawną.

Stosując kryterium wyjścia prymalnej metody simpleks do zadania zapisanego w tablicy 4.2, stwierdzamy, że zmienną usuwaną z bazy jest x₄. Po wykonaniu odpowiednich przekształceń elementarnych otrzymujemy tablicę 4.3.

Tablica 4.3

Cx -»	„max”	2 -2	3 -2	0 0	0 0	b
Baza	c„		Al	X\	•*4
jca	3 -2	0,5	1	0,5	0	2
	2 -2	1	0	0	0,5	4
(i,, =	ij ~ Zij	0 0	0 0	-1.5 1	-0,125 0,5	0 0

Tak więc wykorzystując niebazową zmienną sprawną a,, można przejść od sprawnego rozwiązania bazowego odpowiadającego wierzchołkowi A do sąsiedniego rozwiązania bazowego sprawnego, odpowiadającego wierzchołkowi B. Jednocześnie stwierdzamy, że wyczerpaliśmy w ten sposób wszystkie możliwości generowania dalszych wierzchołków sprawnych, wynikające z analizy wierzchołka A.

7. tablicy 4.3 odczytujemy otrzymane rozwiązanie bazowe. Mamy: ^xi = 4, a₂ = 2, a₃ = 0, x₄ = 0.

Zmiennymi nicbazowymi w otrzymanym rozwiązaniu są a, oraz a₄. Stwierdziliśmy już wcześniej, że zmienna a₄ jest niebazową zmienną sprawną i pozwala