1636661690

20

2. METODA SYMPLEKSOWA

ctiCLi = 0, mamy

aiCLi + aj Vi^ai ⁼    + ctji/i)ai,

i—1    i=1

gdzie a*₀ = 0. Wtedy + ajifa = 0 oraz ajUi₀ = 0. Zatem aj = 0, a stąd

ai = 0.

Niech B' = [ai, a2,..., <Xj₀_i, Oś₀+i, ..., a_m, a,] oraz A = [B'N^r]. Wówczas

oraz

Ax = b, stąd b — B'xb + N'xn = B'xq, czyli Xb = B' ¹b tzn. B'~¹b > 0. Ponadto

B'~^lb

0

2.3. Metoda sympleksowa

Przypomnijmy, że chcemy zminimalizować c^Tx przy warunkach Ax — 6, x > 0.

Algorytm sympleks

Krok 1. Wziąć dowolny punkt ekstremalny x zbioru X o zmiennych bazowych Xb-

Krok 2. Wyliczyć a = ĆqB~¹N — cj^. Jeżeli a < 0, to zakończyć algorytm (punkt x jest szukanym punktem). W przeciwnym wypadku przejść do kroku 3.

Krok 3. Wybrać maksymalną dodatnią współrzędną a. Niech tą współrzędną będzie aj, zatem aj — c^B~^ldj — cj. Jeśli yj = B~^ldj < 0, to zakończyć algorytm (brak rozwiązania). W przeciwnym wypadku przejść do