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.

Wyszukiwarka

Podobne podstrony:
skanuj0010 Slajd 4 Slajd 5 Slajd 6 Całka szczególna Jeżeli jako wymuszenie przyjmujemy skok jednostk
MOŻLIWOŚĆ WJAZDU NA WZNIESIENIE Jeżeli pojazd porusza się mchem jednostajnym to siła napędowa może
Zadanie 15. Jeżeli macierz M = magic(7), to czym jest M(l,l), M(l,:), M(:,l), M(:,2:) oraz M(end,2:2
154C B~I> gdzie J to macierz jednostkowa rozmiaru JJ
Obraz
5 (61) jlj, uiucils Caspcyrcsa: a. może być mniejszy od jedności; •b. nie może być mniejszy od
DSC02362 b«<3wUji« KONSERWACJA_222Ł..Metody głębokie Sa to tpondof pcpzez które mcmmy (zyskać we*
68987 Obraz
5 (61) jlj, uiucils Caspcyrcsa: a. może być mniejszy od jedności; •b. nie może być mniej
Obraz
5 (61) jlj, uiucils Caspcyrcsa: a. może być mniejszy od jedności; •b. nie może być mniejszy od
page0360 350 S. DlCKSTEIN. Jeżeli <1* = F(z), f (z) = £, gdzie Fi f są funkcyami analitycznemi zm
0 ikona MB?lit lii tśf
II prawo Lallcmanda t = a + bln(w+c) gdzie: a. b. c - stale t - temperatura w - wysokość od Zie
Zbiornik ciśnieniowy spawany4 26 gdzie: Jeżeli w dnach wykonane są otwory (rys. 2.5), to ich rozmie
Gdzie jest centrum interesów życiowych człowieka? Jeżeli te przesłanki są niejednoznaczne to decyduj
garfield (53) JEŻELI RZUCISZ WE MNIE TĄ ŚNIEŻKĄ, TO MOZESZ POCAŁOWAĆ im

więcej podobnych podstron