DSC03232

18 I.l. Pro|r»mj»i>im‘t liniowe

prey ciym

„T _ /    &    Wi-1 1    1/1+1    v~\

V Pt    Vi Vi Vi    Vi J

Możemy t<*ru albo uaktualnić elementy B bezpośrednio, albo użyć postaci iloczynowej mmcterry odwrotnej (w skrócie PFI, od angielskiej nazwy product form of the tnver§c). TirfirM) »po*ób ma sens praktyczny, dopóki macierz B“^l, składająca się z m² elementów, mose być pamiętana w pamięci głównej komputera. Dla zagadnień o wielkich rozmiarach, które wy magają juz pamięci pomocniczych, takich jak dyski lub taśmy magnetyczne, metoda PFI jest znacznie korzystniejsza. W metodzie tej obliczamy ciąg macierzy E i przetUtawiamy /?“¹ po y-tej iteracji jako iloczyn

(1 11)    B-' = E_p...E₃E₂E_x.

Nałożyliśmy w (111), śe macierz jednostkowa I była bazą początkową. Taka postać odwrotnej macierzy bazowej jest bardzo wygodna do implementacji z użyciem sekwencyjnych pamięci pomocniczych. Wektor X^T oblicza się ze wzoru

A* = ((<$!?„)£„_,) • • • E_x,

i j zgodnie ze wzorem

_v=E_p...(E₂{E₁ o*)).

Każda iteracja metody sympleks daje dodatkowo jeden wektor rj. W praktyce, pamięta się jedynie nieserowe elementy Ej i na ogół dzięki temu używa się mniejszej pamięci niż dla całej macierzy B. Metoda PFI została wykorzystana z powodzeniem do rozwiązania wielkich zagadnień z macierzami rzadkimi.

W kolejnych iteracjach zymplekaowych metoda PFI wymaga pamiętania coraz to nowych macierzy elementarnych. Aby ograniczyć zapotrzebowanie na pamięć i zapewnić dokładność numeryczną, trzeba od czasu do czasu zatrzymać proces iteracyjny i odwrócić macierz B, używając kolumn macierzy A. Taki krok reinwersji musi być uzupełniony ponownym obliczeniem m_B z równania x_B = B~^lb\ potem następuje ciąg iteracji, aż do ponownej reinwersji.

Przykład 1.1. Aby zilustrować metodę sympleksową, wykonamy jedną iterację zrewidowanego algorytmu sympleks na następującym przykładzie:

snaleść minimum    z = —0.5x_t — G.4x₂

pr*y warunkach    *, + 2x_a + *₃    = 24,

1.5*, + *₂    + x₄ — 18,

|l    +Xj = ll,

®1,    • • • i ^5 ^ 0.

Mamy tutąj następujące wektory i macierze:

	ri	2	1	0	0‘		24"
A =	1.5 1		0	1	0	, b =	18
	1	0	0	0	1.		11.

111-0.5, i 0.4, 0, 0, H