CCF03252008006

Tablica 2.3

	X'	X2	X3	X4	X5
*1	0	0	6	3	3
x2	0	4	0	0	2
X3	12	0	0	6	0
x4	6	6	-6	0	0
X0	0	8	niedop.	9	131.

Rozwiązanie bazowe X³ jest niedopuszczalne. Rozwiązaniem optymalnym jest X⁵:xj = 3, x₂ — 2, x₃ = 0, x₄ = 0 z wartością funkcji celu x₀ — 13.

Rozwiązaniom bazowym dopuszczalnym odpowiadają wierzchołki zbioru rozwiązań dopuszczalnych. Pokazano to doskonale na rys. 2.2, na którym przedstawiono rozwiązanie analizowanego zadania (2.44) metodą geometryczną. W przestrzeni R² każdy punkt przecięcia się co najmniej dwóch prostych jest rozwiązaniem bazowym. Jeżeli dany punkt jest punktem przecięcia się dwóch prostych, to rozwiązanie bazowe jest niezdegenerowane. Jeżeli natomiast ten punkt jest punktem przecięcia trzech lub więcej prostych, to z tym punktem jest związanych więcej rozwiązań bazowych, ale każde z nich jest zdegenerowane.

2.6.2

Idea metody simpleks

Zastosowany pełny przegląd zbioru rozwiązań bazowych jest w ogólnym przypadku nieefektywny, ze względu na liczbę tych rozwiązań oraz rozmiary

każdego układu równań, jaki należy rozwiązać. Jeżeli n = 20, a m = 10, to

Ć2(P

układy 10 równań z 10 zmiennymi.

W metodzie simpleks stosujemy przegląd ukierunkowany zbioru rozwiązań bazowych. Przechodzimy od jednego dopuszczalnego rozwiązania bazowego do drugiego, o którym wiemy, że jest nie gorsze od poprzedniego. Pomijamy więc rozwiązania bazowe niedopuszczalne oraz te, które są gorsze od aktualnie rozpatrywanego.

Przegląd ukierunkowany zbioru rozwiązań bazowych zadania PL w metodzie simpleks sprowadza się do realizacji następujących kroków (o ile zadanie ma rozwiązanie optymalne):

KROK A

Wyznaczamy rozwiązanie wyjściowe, dopuszczalne i bazowe.

KROK B

Sprawdzamy, czy aktualne rozwiązanie bazowe jest optymalne. Jeżeli tak, następuje koniec obliczeń. Jeżeli nie, to przechodzimy do kroku C.

KROK C

Bierzemy pod uwagę sąsiednie rozwiązanie bazowe, o którym wiemy, że jest nie gorsze od poprzedniego i wracamy do kroku B.

2.6.3

Postać bazowa zadania PL

Każdej bazie B odpowiada określony podział zmiennych na zmienne bazo-

we i niebazowe oraz związane z nią rozwiązanie bazowe. Przy danej bazie B wektor zmiennych X oraz macierz współczynników A można przedstawić:
x = (xB, xN), A = (B, N).
Wówczas układ równań Ax = b zapiszemy w	postaci:
Bx„ + Nxn = I).	(2.46)
Mnożąc lewostronnie układ (2.46) przez B-1,	otrzymujemy:
B-'Bxb + B~'Nxn = ir‘b.	(2.47)
Układ (2.47) możemy zapisać następująco:
lx„ + WxN = b*,	(2.48)

37

Wyszukiwarka

Podobne podstrony:
CCF03252008009 rU = O, hj = t,j - tik trj (i * r, j = 0,1.....n). (2.53) Przekształcając elementy
skanuj0010 (223) Tablica 1.24 cd Wyróżnik oznaczenia L Wymiary Otwory Poke przekroju Masa Obwód na
skanuj0012 (309) PN-77/M-32425 Tablica. I d

więcej podobnych podstron