r

U = O,

hj' = t,j - t_ik t_rj' (i * r, j = 0,1.....n).

(2.53)

Przekształcając elementy tablicy T według podanych wzorów, otrzymujemy w nowej tablicy T wektory jednostkowe dla nowego zestawu zmiennych bazowych.

Degeneracja rozwiązania bazowego. Możemy się zetknąć z tym problemem, gdy chociaż jedna zmienna bazowa jest zerowa. Wówczas mogą wystąpić tzw. martwe kroki, to znaczy przechodzimy od jednego rozwiązania bazowego do drugiego, związanego z tym samym punktem. Wartości zmiennych nie ulegają w tym przypadku zmianie, podobnie jak wartość funkcji celu. Teoretycznie możliwe jest powstanie cyklu, czyli ciągu rozwiązań, który będzie się stale powtarzał. Na szczęście w praktyce degeneracja rozwiązania bazowego albo znika, albo kolejne rozwiązanie zdegenerowane okazuje się rozwiązaniem optymalnym.

PRZYKŁAD 2.10

Rozwiążmy zadanie PL analizowane już wcześniej:

r

3*! + x₂ -> max,

_< 2x_t + 3x, ^ 12,

(2.54)

Wprowadzając zmienne swobodne x₃ i x₄, sprowadzamy zadanie (2.54) do równoważnej postaci kanonicznej:

r

3xj + x₂ + 0x₃ + 0x₄ -» max, 2x₍ + 3x₂ + x₃ + 0x₄ = 12, 2.Xj -(- 0x₂ + 0x₃ + x₄ — 6,

Xj, x₂, x₃, X₄ 5: 0.

(2.55)

Postać kanoniczna (2.55) jest zarazem postacią bazową, generującą początkowe, dopuszczalne rozwiązanie bazowe. Jeżeli zmiennymi bazowymi będą zmienne swobodne x₃ i x₄ z wektorami jednostkowymi: