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)!