DSC03235

21

Gdy przyjmiemy teraz podane oznaczenia oraz wartości początkowe • m k_t, , s 1₍ 2, ..., m, wtedy obliczenia w fazach I i II przebiegają następująco.

Faza I

Krok 1. Jeśli *_n+m+2 < 0, to obliczyć

m+2

6j = wiersz _m+7{U) • kolumnami) =    «m+2j>^ap/» i « 1, 2, ..., n,

pal

i przejść do kroku 2. Jeśli x_n. _m, ₂ = 0, przejść do kroku 1 fasy 11.

uwaga. W fazie I *_n+_m+2 jest maksymalizowaną funkcją celu i wszystkie jej współczynniki, poza c_n+m+2 = 1, są równe zeru. Wartości 6j są składowymi wektora względnych kosztów p, określonego równością (1.8).

Krok 2. Jeśli wszystkie m > 0, to zmienna x_n+mĄ,₂ osiągnęła maksymalną wartość i nie istnieje rozwiązanie dopuszczalne zagadnienia LP. Jeśli co najmniej jedno Śj < 0, to wówczas zmienną wprowadzaną do bazy jest takie x_k, że

6_k = min{ój-: 6j <0, 1 < j < »}.

Krok S. Obliczyć

m+2

m + 1

y_f = wiersz_{(U) • kolumna*^) = ^ ti_ipa_pfcs j = 1, 2,

p=i

Krok Ą. Obliczyć

-¹: Vi > 0, 1 < i < ^m

y.

Jeśli y> < 0 dla wszystkich = 1,2, ..., m, to nie ma wtedy rozwiązania dop—n sinego W przeciwnym razie zmienną x_{ należy usunąć s basy.

Krok 5. Obliczyć nowe wartości zmiennych w rozwiązaniu basowym

Xi =    — $y_if i£ k_t    i ss X, 2*    t,

oraz

- % 11 m	^y* yz ’
^u«> ^= u»j ?		«#/, 1 = 1,2.	.... m + 1, j = 1,2* ..	., m
Wrócić do kroku 1.

i;waga. Kolumny m + 1 i m + 2 macierzy V nie zmieniają się Iteracje fazy 1 wykonywane az do momentu, gdy albo    = 0, albo też stwierdzi »ę. sr me istnieje

rozwiązanie dopuszczalne. W pierwszym z tych przypadków prawrbodtuny do (asy H