Metodą selekcji możemy rozwiązać
dowolny problem optymalizacji liniowej
przedstawiony w postaci standardowej:
T
FC: Z = c x → MA (
X MI )
N
O: Ax = b
WB: x ≥ 0
Jeżeli po prawej stronie ograniczenia mamy liczbę ujemną to mnożymy to ograniczenie
przez –1
Do ograniczenia nierównościowego należy
dodać (lub odjąć) nową nieujemną zmienną
zwaną zmienną bilansującą.
Zmienna bilansująca musi być uwzględniona w
funkcji celu ze współczynnikiem zerowym
Jeżeli nie są spełnione warunki brzegowe na nieujemność zmiennych decyzyjnych to
zmienną nie spełniającą tego warunku
zastępujemy różnicą dwóch dodatkowych
zmiennych nieujemnych.
Każde rozwiązanie x spełniające ograniczenia Ax = b
b ≥ 0
oraz warunki brzegowe
x ≥ 0
nazywamy rozwiązaniem dopuszczalnym
(RD)
m liniowo niezależnych wektorów kolumnowych macierzy A nazywamy bazą.
Zmienne odpowiadające tym kolumnom
nazywamy zmiennymi bazowymi, pozostałe to zmienne niebazowe.
Rozwiązaniem bazowym (RB) nazywamy takie rozwiązanie x, dla którego wszystkie
zmienne niebazowe są równe zero.
Rozwiązaniem bazowym dopuszczalnym
(RBD) nazywamy takie rozwiązanie x, dla
którego wszystkie zmienne niebazowe są
zero a zmienne bazowe są większe lub
równe zero.
1. tworzymy bazy
2. w każdej bazie poszukujemy rozwiązania
bazowego
3. jeżeli otrzymane RB jest RBD to
obliczamy wartość funkcji celu
4. spośród wszystkich RBD wybieramy te,
dla których funkcja celu przyjmuje
wartość maksymalną (minimalną), czyli
znajdujemy rozwiązanie optymalne
Jeżeli w postaci standardowej problemu optymalizacji liniowej mamy r zmiennych
to maksymalna liczba baz wynosi
r!
m (
! r − m)!