CCF03252008007

gdzie:

I = B~’B,

W = ir ^lN, b* = B~'b.

Jeżeli macierz współczynników A zawiera macierz jednostkową, to taką postać zadania PL nazywamy postacią bazową. Z postaci bazowej (2.48) łatwo można odczytać rozwiązanie bazowe:

x_H = b*, x_N = 0.

Jeżeli dla danej bazy B:

x„ = B 'b 0,

to rozwiązanie bazowe jest rozwiązaniem dopuszczalnym.

Dwie bazy B i B' nazywamy sąsiednimi, jeżeli się różnią tylko jedną kolumną macierzy A. Podobnie, dwa rozwiązania bazowe będziemy nazywali rozwiązaniami sąsiednimi, jeżeli różnią się tylko jedną zmienną bazową.

Przechodzenie w metodzie simpleks od jednego rozwiązania bazowego do drugiego, sąsiedniego; w sensie rachunkowym polega na przekształceniu układu równań (2.46) z jednej postaci bazowej w drugą. Oczywiście najlepiej, gdy wyjściowa postać kanoniczna jest także postacią bazową.

Mając aktualne dopuszczalne rozwiązanie bazowe, związane z określoną bazą, musimy wiedzieć, czy jest ono optymalne, czy też nie.

Oznaczmy przez x₀ wartość funkcji celu. Wektor c dla danej bazy B można przedstawić jako c = (c_B, c_N). Wówczas:

*0 ^{= C}B^XB + ^CN^XN ^{= c}n0’ ~ W_Xn) rf- C_NX_N = C,,b* + (C_N — C„W)x_N.

Łatwo sprawdzić, że jeżeli:

c_N - c_BW ^ 0,    (2.49)

to każdy przyrost wartości zmiennej niebazowej nie zwiększy wartości funkcji celu, czyli rozwiązanie jest optymalne. Warunek (2.49) nazywamy kryterium optymalności rozwiązania bazowego.

2.6.4

Tablica simpleksowa

Zadanie PL, wraz z wszystkimi elementami niezbędnymi do oceny, czy rozwiązanie bazowe jest optymalne, czy też nie, można zapisać w postaci tzw. tablicy simpleksowej T = [/,]. Elementy /-tej kolumny tablicy simpleksowej oraz kolumny wartości zmiennych bazowych definiujemy w następujący sposób:

h.J					ti.o
^(2,j		B~	'A,-		^l2. 0		B ^1 b
^[rn, j	‘				tm, 0
- to, i .		-^cj-			_ to, 0 _		.cDB-‘b_

gdzie A_;- — j-ta kolumna macierzy współczynników A.

Przyjmując wprowadzone oznaczenia, układ równań oraz równanie funkcji celu zapiszemy:

X(0 = ho - E hj*j (' =

i^eZN

^X0 ~ ^00 + E tOj^Xj ■

J^eZN

Wskaźnik kryterium optymalności stojący przy J-tej zmiennej obliczamy: toj = Cj - c_BB"^łAj = _Cj - £ ety = Cj - Zj.

^ieZB

Tablica simpleksowa dla postaci bazowej, w której m pierwszych zmiennych jest zmiennymi bazowymi, ma następującą postać:

Tablica 2.4

^ci		c„.	• > ^Cm >	c»łi. •••.«.
	zmienna				l>*
^Ci	bazowa	^xl»-	M J A n| J	^A*mrl . •••»*„
Cl		1,"	,0,		*1.0
^C2	X2	0,-	,0,	b.m+l .-Tj,.	*2.o
^Cm	xm	0,-	,1,		tmn
^zi		*i,	" ,zm		X0[
^l0j ~	Cj - Zj	*01 »	-,'o.....	*0, m + 1» ’'" > *0, ii	*0.0

Element t_:j > 0 określa, o ile zmniejszy się wartość zmiennej bazowej x_(;), jeżeli zmienna niebazowa x_s przyjmie wartość jeden. Podobnie, element t_tj < 0 określa, o ile zwiększy się wartość zmiennej x_m, gdy zmienna niebazowa x-przyjmie wartość jeden.