8344

6.3 Macierz i zmienne bazowe

Załóżmy, że kolumny macierzy A zostały uporządkowane w taki sposób, że m pierwszych kolumn jest liniowo niezależnych.

Niech:

A = (B.N) x = (x_B,x_N)

gdzie

B macierz bazowa, baza zadania PL.

B jest macierzą nieosobliwą o wymiarach m x m. tzn. |B ^ 0 oraz istnieje B ', xb zmienne bazowe, odpowiadające kolumnom w B.

Xn zmienne niebazowe. odpowiadające kolumnom w N.

Liczba baz jest skończona ) = —-— -—

^J    \m/ m!(n - m)!

6.4 Rozwiązania bazowe

Warunek Ax = b można teraz zapisać Bx_b + Nxn = b stąd

x_b = B ^lb-B 'Nx_n    (6.2)

jest to równanie wypukłego stożka, gdzie:

B 'b wierzchołek stożka,

kolumny B ¹N wektory kierunkowe tworzących stożka.

Jednym z jego rozwiązań jest tzw. rozwiązanie bazowe:

x_B = B ^]b, Xn = 0    (6.3)

Jeżeli x_B > 0. to jest to tzw. rozwiązanie bazowe dopuszczalne punkt ekstremalny (-wierzchołek) wielościanu ograniczeń.

Punkt x jest punktem ekstremalnym zbioru F jeżeli nic istnieją x',x" 6 F i a € (0,1), takie, że x = ax' + (1 — a)x"

17