Slajd41 3

Metoda simpleks

Najpierw zajmiemy się wyznaczeniem wyjściowego bazowego rozwiązania dopuszczalnego programu i przedstawimy go w pierwszej tablicy simpleksowej.

Wyjściowe równania ograniczeń A#k_b +    = b postaci kanonicznej

zadania programowania liniowego obejmują wśród wszystkich n+m zmiennych m zmiennych x_Ml, x_m2, x_Włn, z których każda występuje tylko w jednym równaniu ze współczynnikiem 1. Współczynniki te tworzą więc macierz jednostkową o wymiarach [n x m]. Taka sytuacja występuje wówczas, gdy ograniczenia mają postać nierówności typu „mniejsze lub równe" i przekształcamy je w równania przez wprowadzenie zmiennych swobodnych. Powyższa własność pozwala przyjąć za wyjściowe bazowe rozwiązanie dopuszczalne wartości zmiennych:

⁼ 0, x₂ ⁼ 0,x_n ⁼ 0,

^n+i^— hj, ^,^2 — ^ >«., x_rHHłł — b_m.

Zmienne x_lf x_z, x_n są więc zmiennymi niebazowymi, natomiast zmienne x_łrt._1/ x_n¥V x_Irtłn tworzą zmienne bazowe.