204 205

204 Metody wielokryterialne

na przejście do wierzchołka A. co nie jest dla nas interesujące. Sprawdzimy teraz, czy zmienna x₃ jest niebazową zmienną sprawną. Dla rozpatrywanej bazy mamy:

0,5 —0,125^_

D„ =

0    0,5

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

0,5*., = 0,

—1,125?., + 0,5*^ <0,

/l, + *2 = 1,

x,^o,x₂^o,

który jest sprzeczny. Oznacza to, że zmienna x₃ nie jest niebazową zmienna sprawną. Jednocześnie wyczerpaliśmy w ten sposób wszystkie możliwości generowania dalszych wierzchołków sprawnych, wynikające z analizy wierzchołka B oraz nie ma już żadnych innych wierzchołków, które moglibyśmy analizować. Wynika stąd, że proces generowania wierzchołków sprawnych został zakończony.

Przykład 4.3^S

Rozwiązać zadanie:

—jc | —> max, x₂ —» max,

-x, + 2-x₂ < 4,

—x, + 2— x₂ < 6, x,, x₂ >4.

Zbiór rozwiązań dopuszczalnych rozpatrywanego zadania w przestrzeni decyzyjnej przedstawiono na rysunku 4.6.

Rozwiązanie bazowe po dołączeniu zmiennych bazowych ma postać:

X| = 0, x₂ = 0, x₃ = 4, x₄ = 6.

Sprawdzimy, czy jest to bazowe rozwiązanie sprawne. Zadanie testujące jest następujące:

.s, + s₂ —> max,

-x,    —S| = 0,

x₂    —s₂ = 0,

-x, + 2x₂ + x₃ =4,

—x, + x₂ + x₄ = 6, x,, x₂, x₃, x₄, s,, s₂ > 0.

' Przykład ten zaczerpnięty został z. ptyly CD-rom dołączonej do książki pod red. T. Tr/.askalika, Metody wielokryterialne na italskim rynku finansowym, PWE, Warszawa 2006.

Rysunek 4.6

Otrzymujemy rozwiązanie: a'i = 0, x₂ = 2, x_y = 0, x_Ą = 4, a₅ = 0, x₍, = 2

oraz optymalną (skończoną) wartość rozwiązania optymalnego równą 2. Na podstawie twierdzenia 4.3 stwierdzamy, że składowe rozwiązania:

a, = 0, x₂ - 2, a, = 0, x₄ = 4

wyznaczają rozwiązanie sprawne zadania wyjściowego (odpowiadające wierzchołkowi A), od którego możemy rozpocząć omówiony dalej proces generowania wszystkich bazowych rozwiązań sprawnych.

Rozszerzona tablica simpleksowa dla rozwiązania bazowego odpowiadającego wierzchołkowi A ma postać tablicy 4.4.

Tablica 4.4

Cx -»	„max”	-1 0	0 1	0 0	0 0	b
Baza	c„	*i	^X7		^XA
*2	3 -2	0,5	l	0,5 •	0	2
x,	2 -2	i	0	-0.5	1	4
		0	0	0	0	0
=	ij-Zij	0	0	0	0	2

Zapisując odpowiednie układy warunków, stwierdzamy, ze zmienna a, jest niebazową zmienną sprawną, natomiast a_;( nie ma tej własności. Ponieważ wszystkie elementy kolumny odpowiadającej zmiennej x, są w tablicy 4.4 ujemne, oznacza to, że nie ma możliwości zastosowania kryterium wyjścia prymalnej metody simpleks. Oznacza to, że punkt A jest początkiem nieograniczonej krawędzi sprawnej.