420 2

420

10. Optymalizacja

Uwaga. Nie trzeba szukać wektora x spełniającego nierówności — to robią automa tycznie programy.

3. W pewnym etapie metody sympleks zamienia się zmienną lewostronną x_f i zmień prawostronną Xj (po tej zamianie x, jest więc prawostronna, a Xj — lewostronna). Pr_2e<j zmianą każdej zmiennej lewostronnej .r_t odpowiada związek

Xl°c_ljXj+Y_jc_lRx_ji (również dla x_L=x_l),

gdzie suma po prawej stronie zawiera wszystkie zmienne prawostronne x_R oprócz x_t. p₀ zamianie zachodzą związki

*Ł=cźt*i+5>L**R (takie dla x_L=Xj)_t

gdzie suma zawiera wszystkie zmienne prawostronne x_R oprócz x_t. Wyrazić współczynniki

	^CLK •	^C']t'	^CJR
^cł;-	^CLB-	^cu*	^CIR

(Zauważmy, że pominięcie tu wyrazów wolnych nie ogranicza ogólności. Można przyjąć, że odpowiadają one specjalnej zmiennej prawostronnej x_R równej 1.)

10.3. Dualność

Zadanie programowania liniowego z warunkami (10.1.2) i (10.1.3) wyrazimy w symbolice wektorowo-macierzow-ej.

Znaleźć maksimum wyrażenia

/(*> =

Ax=b.

(10.3.1)

przy ograniczeniach

(10.3.2)

(10.3.3)    x>0

(ta nierówność wektorowa oznacza, że wszystkie składowe x są nieujeirmć). To zadanie nazywamy pierwotnym. Kolumny macierzy A o rozmiarach mxn oznaczmy «j» *3 •    • ^a“'

Zakładamy, że istnieją wektory' dopuszczalne. Na mocy twierdzenia 10.1.1 jednym * °pt> malnych wektorów dopuszczalnych jest punkt x, który ma k (kśm) współrzędni ^ ic,,, x_{3y..., Xf_k dodatnich i dla którego odpowiednie wektory' a_h, a_l2,    ^ ^

zależne liniowo. Czytelnik może łatwo sprawdzić, te jeśli k<m, to ten układ ^wekt0. . można rozszerzyć do układu m wektorów' niezależnych liniowo. Inaczej mówiąc, zbiór S złożony z m takich liczb całkowitych, że kolumny «, (/€ 5) są niezależne 1*^D,C i źc Xj—0, gdy j$ S.

Zadanie dualne do (10.3.1) - (10.3.3) określa się następująco: