198 199

198 Metod/ wielokryterialne

4.3.1. Rozszerzona tablica simpleksowa

Zajmiemy się ponownie zadaniem, przedstawionym w przykładzie 4.2. Wprowadzając zmienne bilansujące^{1 2 3} x₂ oraz x₄, zadanie możemy przedstawić w postaci:

f (jci, .v₂, a,, a₄) = 2a, + 3a₂ —» max,

/₂(x„ a₂, a_3> a₄)=-2a, +a₂ —> max, a, + 2a₂ + Aj =8,

4ai    + a₄=16,

A|, A₂, Aj, a₄ > 0.

Współczynniki funkcji celu tworzą macierz współczynników funkcji celu C, współczynniki warunków ograniczających wchodzą w skład macierzy współczynników A, prawe strony warunków ograniczających przedstawiamy w postaci wektora warunków ograniczających b, natomiast zmienne występujące w zadaniu jako wektor zmiennych x. Rozpatrywane zadanie dwu kryteria Inego programowania liniowego możemy zapisać jako zadanie w postaci macierzowej:

Cx —> „max”,

Ax = b, x > 0,

gdzie symbol „max” oznacza, że poszukujemy rozwiązań sprawnych. W rozpatrywanym przez nas zadaniu występują 2 funkcje celu, 4 zmienne i 2 warunki ograniczające. stąd składowe wektorów i elementy macierzy są następujące:

A|

	-3	3	0	0		12 11		8
c=					, A =		, b=
	-2	-3	0	0		4 0 0 1		16

A₄

W dalszych rozważaniach wykorzystamy rozszerzoną tablicę simpleksowa, będącą pewną modyfikacją postaci macierzowej. Różni się ona od rozpatrywanej uprzednio tablicy simpleksowej tym, że zamiast wektorowej funkcji celu mamy macierz współczynników funkcji celu C, podobnie zamiast wektora wskaźników optymalności mamy macierz wskaźników optymalności D. Pierwszy wiersz tej macierzy to wektor wskaźników optymalności dla funkcji/,, natomiast drugi wiersz to wektor wskaźników optymalności dla funkcji/,. Elementy macierzy D oznaczymy jako (l,_r W rozpatrywanym przez nas problemie układ równań, odpowiadający

warunkom ograniczającym, jest w postaci bazowej i zmiennymi bazowymi są x₂ oraz Xą- Dopuszczczalne rozwiązanie bazowe, odpowiadające tej bazie ma postać:

X, = 0, x₂ = 0, x₃ = 8, x₄ = i 6.

Na rys. 4.1 rozwiązaniu temu odpowiada punkt O.

Zapiszemy rozszerzoną tablicę simpleksową, odpowiadającą temu rozwiązaniu (tablica 4.1).

Tablica 4.1

Cx -»	„max"		2	3	0	0
			-2		0	0	b
Baza	c„		X,	*2		*4
	0	0	1	2	l	0	8
*4	0	0	4	0	0	1	16
<i,j = <			2	3	0	0	0
	•} ~~ ^‘j		-2	_2	0	0	0

4.3.2. Zadanie testujące

Procedura wyznaczania wszystkich bazowych rozwiązań sprawnych rozpoczyna się od sprawdzenia, czy pierwsze rozwiązanie dopuszczalne jest rozwiązaniem sprawnym. Konstruujemy w tym celu jednokryterialne zadanie testujące, w którym oprócz zmiennych rozpatrywanego zadania jest tyle dodatkowych zmiennych, ile funkcji celu. Maksymalizowaną funkcją celu zadania testującego jest suma wartości dodatkowo wprowadzonych zmiennych. Do ograniczeń zadania wyjściowego dodajemy dodatkowe ograniczenia, z których każde odpowiada jednej z tych zmiennych i definiuje dodatkowo wprowadzoną zmienną jako różnicę między wartością danego kryterium dla dowolnego rozwiązania dopuszczalnego zadania wyjściowego a wartością w rozwiązaniu testowanym. Przyjmujemy, że wszystkie dodatkowo wprowadzone zmienne są nieujemne.

Zapiszemy zadanie testujące dla rozpatrywanego rozwiązania bazowego. Po uporządkowaniu ograniczeń, polegającym na umieszczeniu po lewej stronie każdego równania zmiennych, a po prawej — warunków ograniczających otrzymujemy zadanie:

s, + ,v₂ —> max,

2x_{ + 3x₂    —s,    - 0,

-2*1 + 2jc₃    ~s₂ = 0,

*i    + X)    = 8,

4x,    +x₄    = 16,

X|, .r₂,    ^4, .?|, .v₂ ^ 0.

1

Zauważmy, żc interpretacja zmiennych bilansujących a, i t₄ jest podobna do interpretacji

2

zmiennych bilansujących, omówionych uprzednio w podrozdziale 1.3.1, ale nie identyczna. Obecnie x,

3

interpretujemy jako niewykorzystaną ilość środka S₂. a x_Ą — jako niewykorzystaną ilość środka Sy