200 201

200 Metody wielokryterialne

Twierdzenie 4.3

Jeżeli optymalna wartość funkcji celu zadania testującego jest równa zeru, wówczas testowane rozwiązanie bazowe jest sprawne. Jeżeli funkcja celu zadania testującego jest ograniczona, rozwiązanie optymalne zadania testującego generuje rozwiązanie sprawne zadania testowanego.

Rozwiązując to zadanie¹ otrzymujemy następujące rozwiązanie: x, = 0, x₂ = 0, x₃ = 8, x₄ = 16, r, = 0, s₂ = 0.

Optymalna wartość funkcji celu wynosi 0, czyli testowane rozwiązanie jest sprawne.

4.3.3. Sąsiednie bazowe rozwiązanie sprawne

Dwa rozwiązania bazowe nazywamy sąsiednimi rozwiązaniami bazowymi, jeżeli zmienne bazowe określające bazę pierwszego i drugiego rozwiązania są takie same z wyjątkiem dokładnie jednej zmiennej. W rozpatrywanym przez nas przykładzie mamy cztery bazowe rozwiązania dopuszczalne, którym odpowiadają na rys. 4.1 wierzchołki O. A, B i C. Oznaczymy zbiory zmiennych bazowych dla tych rozwiązań jako 93,„ ^cfó_A, 93„ i 93,. Łatwo sprawdzić, że:

93o = {*3, x₄),    93„ = \x₂, x₄\,

93„ = {r„-tj),    93, = (x„ X,}.

Widać stąd, że rozwiązania bazowe odpowiadające wierzchołkom O oraz A czy też O oraz C są sąsiednimi rozwiązaniami bazowymi, natomiast rozwiązania bazowe odpowiadające wierzchołkom O oraz B nie mają tej własności.

Dwa rozwiązania bazowe, odpowiadające wierzchołkom P i Q nazywamy sąsiednimi bazowymi rozwiązaniami sprawnymi, jeżeli obydwa są rozwiązaniami sprawnymi, są one sąsiednimi rozwiązaniami bazowymi oraz wszystkie punkty leżące na odcinku PQ są rozwiązaniami sprawnymi.

Oznaczymy przez D„ podmacierz macierzy D, w skład której wchodzą kolumny niebazowe, a przez A zbiór wszystkich ^-elementowych wektorów o dodatnich składowych, sumujących się do jedności, czyli:

k

A = {), = [>„„ ..., X_t]: 5A=1, h>0 dla i = l, .... k),

I-I

gdzie k oznacza liczbę rozpatrywanych kryteriów (w rozpatrywanym przykładzie k = 2).

Zmienną niebazową x_t w ustalonej bazie 93,. odpowiadającej wierzchołkowi p nazywamy niebazową zmienną sprawną, jeżeli istnieje wektor Xe A taki, że:

U, = 0.

gdzie dj oznacza kolumnę macierzy D_w związana ze zmienną x_r

Związek pomiędzy niebazową zmienna sprawną a sąsiednia bazą sprawną określa poniższe twierdzenie.

Przypuśćmy, że mamy rozwiązanie bazowe, odpowiadające wierzchołkowi P, _Xj jest niebazową zmienna sprawną oraz mamy drugie sąsiednie rozwiązanie bazowe, odpowiadające wierzchołkowi Q, które otrzymujemy, stosując przekształcenia elementarne, przy czym zmienną wchodzącą do bazy jest x_Jy a zmienną opuszczającą bazę wyznaczamy przy pomocy kryterium wyjścia prymalnej metody simpleks.

Twierdzenie 4.4

Wygenerowane w opisany powyżej sposób (za pomocą niebazowej zmiennej sprawnej Xj) rozwiązanie bazowe, odpowiadające wierzchołkowi Q, jest sąsiedni” bazowym rozwiązaniem sprawnym.

Powyższe twierdzenie wykorzystamy do wygenerowania dalszych bazowych rozwiązań sprawnych. W rozwiązaniu bazowym, przedstawionym w tablicy 4.1 zmiennymi niebazowymi są x, i x₂. Sprawdzimy kolejno, czy są to nicbazowe zmienne sprawne.

Dla zmiennej jc, mamy:

2	3		2
		, d, =
-2	-2		-2

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

2X, -    = 0,

3k, -2^0,

kj + \₂ = 1, k, > 0, kj 0,

który nie ma rozwiązania. Wynika stąd, że zmienna nie jest w rozpatrywanej bazie niebazową zmienną sprawną.

Dla zmiennej x₂ mamy:

		3		3
			. d,=
	-2	l K> 1_		-2

1

Możemy wykorzystać program S1MP.BXE.