CCF03252008005

2.6

Metoda simpleks

Metoda simpleks jest podstawową metodą znajdowania optymalnych rozwiązań zadań programowania liniowego. Jest to metoda ogólna, pozwalająca rozwiązać każde zadanie PL. Polega ona na sekwencyjnym, ściśle określonym przeglądzie rozwiązań bazowych.

2.6.1

Rozwiązanie bazowe zadania PL

Rozwiązanie bazowe związane jest z postacią kanoniczną. Załóżmy więc, że dane jest zadanie PL o postaci kanonicznej:

(2.43)

gdzie:

A — macierz współczynników o wymiarach (m x n), x — 11-wymiarowy wektor zmiennych, b — m-wymiarowy wektor wyrazów wolnych, c — n-wymiarowy wektor wag funkcji celu.

Niech B oznacza macierz kwadratową m-tego stopnia, składającą się z m liniowo niezależnych kolumn macierzy A. Wyznacznik tej macierzy jest oczywiście różny od zera:

det (B) + 0. '

Macierz B nazywać będziemy bazą, jej kolumny — kolumnami bazowymi, a pozostałe kolumny macierzy A — kolumnami niebazowymi. Zmienne związane z kolumnami bazowymi nazywamy 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. Układ m

m! (ii — m)!

n!

rozwiązań ba-

rownan z n zmiennymi ma co najwyżej

zowych.

Rozwiązania bazowe układu Ax = b można uzyskać np. w następujący sposób:

1)    wybieramy m liniowo niezależnych kolumn macierzy A, czyli bazę B,

2)    zmienne niebazowe przyjmują wartości zerowe (x_N = 0),

.„i m r-^i    hjf.T^ffi^T^rTYŚ ^T.^r:7^r.tT^YV;«M - .‘.WiiW

• ł .

P.44)

•3x₁ + x₂ + 0x₃ + 0x₄ -+ max, 2xj + 3x₂ -f x₃ + 0x₄ = 12,

2x, + 0x₂ + 0x₃ + x₄ = 6,

Xi, x₂, x_3> x₄ ^ 0.

Zadanie (2.44) ma co najwyżej

= 6 rozwiązań bazo-

3) wartości zmiennych bazowych ustalamy rozwiązując układ m równań z m niewiadomymi: Bx„ = b.

Jeżeli każda zmienna bazowa jest różna od zera, to takie rozwiązanie bazowe jest niezdegenerowane. Jeżeli natomiast chociaż jedna zmienna bazowa jest zerowa, to takie rozwiązanie bazowe jest zdegenerowane. Dla zadań PL prawdziwe jest następujące twierdzenie.

TWIERDZENIE &

Jeżeli zadanie PL ma rozwiązanie optymalne, to ma także rozwiązanie optymalne bazowe.

WNIOSEK fi

Rozwiązania optymalnego wystarczy szukać wśród rozwiązań bazowych, których liczba jest skończona.

WNIOSEK 2

Można znaleźć rozwiązanie optymalne dokonując przeglądu zupełnego zbioru wszystkich rozwiązań bazowych.

PRZYKŁAD 2.10

Mamy zadanie PL o postaci standardowej:

r

3Xj + x₂ -> max,

< 2x, + 3x₂ < 12, J.

2x, ^ 6, x_lt x₂ ^ 0.

Wprowadzając zmienne swobodne uzyskujemy równoważną postać kanoniczną:

2.45)

4!

2! (4-2)1

wych. Możemy je wyznaczyć przyjmując jako zmienne niebazowe kolejno: x_lt x₂; x_v x₃; x_v x₄; x₂, x₃; x₂, x₄; x₃,x₄. Ponieważ dla trzeciego wariantu zmiennych niebazowych wektory:

A² =

oraz A³

są liniowo zależne (nie mogą tworzyć bazy), stąd

ostatecznie mamy 5 następujących rozwiązań bazowych:

35