2999072767

są ze współczynników odpowiadających zmiennym bilansującym x₃, x₄, x₅. Tworzą one macierz B. Jest to macierz kwadratowa (w naszym przypadku macierz 3. stopnia), składająca się z liniowo niezależnych kolumn macierzy A. Macierz B nazywać będziemy bazą, jej kolumny kolumnami bazowymi, a pozostałe kolumny macierzy A - kolumnami niebazowymi. Zmienne związane z kolumnami bazowymi nazywać będziemy zmiennymi bazowymi, a pozostałe zmienne zmiennymi niebazowymi.

Z każdą bazą B układu Ax = b związane jest rozwiązanie bazowe. Jeżeli układ Ax = b jest niesprzeczny oraz n>m, to układ ten ma nieskończenie wiele rozwiązań, ale skończoną liczbę rozwiązań bazowych.

Oznacza to, że w naszym zadaniu układ równań [2.25]-[2.27], z którego powstała macierz A, jest w postaci bazowej oraz że zmienne (jtj, x₄, x₅) tworzą bazę, czyli, że są zmiennymi bazowymi, natomiast zmienne decyzyjne X/ i x₂ zmiennymi niebazowymi, a rozpatrywane zadanie programowania liniowego jest zadaniem w postaci bazowej. Jeśli przyjmiemy, że w równaniach [2.29]-[2.31] zmienne decyzyjne Xj i x₂ przyjmują wartości równe zeru, to wartości zmiennych bazowych x₃, x₄ i x₅ są dodatnie (nieujemne). Ponieważ wszystkie wartości zmiennych bazowych są nieujemne, to takie rozwiązanie jest bazowym rozwiązaniem dopuszczalnym. Na rys. 2.1 odpowiada to punktowi A (0,0), który jest jednym z wierzchołków czworokąta A, B, C, D, wyznaczającego zbiór rozwiązań dopuszczalnych. Takiemu rozwiązaniu bazowemu odpowiadają wartości zmiennych:

X/ = 0, x₂ = 0, x₃ = 14, x₄ = 8, x₃ = 16

W rozwiązaniu tym wartość funkcji celu jest równa zeru, gdyż nie uruchamiamy produkcji (zmienne decyzyjne x₃ i x₂ są równe zeru), natomiast zmienne bilansujące x₃, x₄, i x₅, określające niewykorzystane zasoby surowców Sj, S₂ i S₃, są równe dysponowanym wielkościom tych zasobów.

Każdej bazie B odpowiada określony podział zmiennych na zmienne bazowe i niebazowe oraz związane z nią rozwiązanie bazowe. Przy danej bazie B wektor zmiennych x oraz macierz A można przedstawić jako: x = (x_B,x_N), A = (B, N)

Wówczas układ równań [2.12] zapiszemy w postaci:

Bx_b + Nx_n = b    [2.33]

Mnożąc lewostronnie układ [2.32] przez B'¹, otrzymujemy postać bazową:

IxB + WxN = b*	[2.34]
1 = 8*8	[2.35]
w = b'n	[2.36]
b* = B 'b	[2.37]

Z postaci bazowej [2.34] łatwo można odczytać rozwiązanie bazowe: x_B = b*. x_N = 0

Jeżeli dla danej bazy B: x_B = B''b > 0, to rozwiązanie bazowe jest rozwiązaniem dopuszczalnym.

17