BO wyklad3

Badania operacyjne
Wykład 3
Wykład 3
Programowanie liniowe dualizm
Plan wykładu
l� Dualizm zadania liniowego
2012-10-21 2
Programowanie liniowe
l� Jednym z najczęściej wykorzystywanych modeli
decyzyjnych jest model programowania liniowego.
l� Składa się on z trzech podstawowych części:
l� funkcji celu odzwierciedlającej kryterium decyzyjne
l� funkcji celu, odzwierciedlającej kryterium decyzyjne,
l� warunków ograniczających, opisujących warunki podejmowania
decyzji,
l� warunku nieujemności zmiennych decyzyjnych (musi to być
zastrzeżone w modelu, gdyż moglibyśmy otrzymać w rozwiązaniu
liczby ujemne, które zwykle nie mają żadnego sensu
y j , y ją g
praktycznego).
2012-10-21 3
Programowanie liniowe
l� Zagadnienia programowania liniowego, które posiadają
tylko dwie zmienne decyzyjne, można rozwiązać metodą
graficzną.
fi
l� Gdy problem jest bardziej złożony i występuje większa
l� Gdy problem jest bardziej złożony i występuje większa
liczna zmiennych decyzyjnych, to takie zagadnienie
rozwiązujemy algorytmem simpleks lub korzystając
z profesjonalnych pakietów komputerowych.
l� Jeżeli w zadaniu decyzyjnym wszystkie relacje są liniowe
l� Jeżeli w zadaniu decyzyjnym wszystkie relacje są liniowe
oraz wszystkie zmienne są ciągłe, to takie zadanie
nazywamy zadaniem programowania liniowego (PL).
y y p g g ( )
2012-10-21 4
Programowanie liniowe
l� Zadanie programowania liniowego można sformułować
następująco:
l� gdzie:
5
2012-10-21 5
Programowanie liniowe
l� Alternatywnie zadanie programowania liniowego
w zapisie macierzowym można sformułować następująco:
l� gdzie:
2012-10-21 6
Przykład
2012-10-21 7
Programowanie liniowe
l� Każdy wektor zmiennych decyzyjnych
nazywamy rozwiązaniem dopuszczalnym zadania PL.
l� Rozwiązanie dopuszczalne, dla którego funkcja celu
osiąga maksimum (minimum) nazywamy rozwiązaniem
osiąga maksimum (minimum), nazywamy rozwiązaniem
optymalnym.
2012-10-21 8
Budowa modelu matematycznego
l� Aby zbudować model matematyczny należy podać:
l� jakie wielkości mają być wyznaczone (podanie zmiennych
d j h)
decyzyjnych),
l� jakie wielkości są dane (określenie parametrów),
l� jakie warunki ograniczające musi spełnić decyzja dopuszczalna
l� jakie warunki ograniczające musi spełnić decyzja dopuszczalna
(zapisanie warunków ograniczających),
l� cel jaki chcemy osiągnąć (określenie funkcji celu).
l� Decyzje zgodne z warunkami ograniczającymi to decyzje
dopuszczalne
dopuszczalne.
l� Decyzja najlepsze z punktu widzenia przyjętych celów to
decyzja optymalna.
2012-10-21 9
Budowa modelu matematycznego
l� Zadanie PL może mieć rozwiązanie dopuszczalne lub być
zadaniem sprzecznym, nie mającym rozwiązania
dl
dopuszczalnego.
l� Jeżeli zadanie PL na rozwiązanie dopuszczalne to
l� Jeżeli zadanie PL na rozwiązanie dopuszczalne, to
zachodzi jedna z trzech możliwości:
l� istnieje jedno rozwiązanie optymalne,
l� istnieje wiele rozwiązań optymalnych,
l� brak rozwiązania optymalnego.
l� W przypadku dwóch zmiennych bardzo łatwo jest znalezć
rozwiązanie optymalne lub pokazać, że go nie ma.
ą py p , g
Stosujemy wówczas metodę graficzną.
2012-10-21 10
Metoda graficzna
l� Problem znajdowania rozwiązania zadania PL metodą
graficzną sprowadza się do:
l� wyznaczenia półpłaszczyzn odpowiadających poszczególnym
nierównościom,
l� znalezienia części wspólnej dla wszystkich półpłaszczyzn ZRD
l� znalezienia części wspólnej dla wszystkich półpłaszczyzn ZRD
(zbiór rozwiązań dopuszczalnych),
l� wyszukania w ZRD rozwiązania najlepszego dla przyjętej funkcji
celu (rozwiązania optymalnego).
l ( i i t l )
l� Jeżeli ZRD jest zbiorem pustym lub zbiorem
jp y
nieograniczonym w kierunku wzrostu wartości funkcji celu
dla zadania na maksimum bądz spadku dla zadania na
minimum, to zadanie nie ma rozwiązania optymalnego.
i i t d i i i i t l
2012-10-21 11
Dualizm zadania liniowego
l� Każde zagadnienie minimalizacji ma odpowiednik
w postaci zagadnienia maksymalizacji. Podobnie dla
k żdd i i li jii t i j
każdego zagadnienia maksymalizacji zawsze istnieje
k
odpowiadające mu zagadnienie minimalizacji.
l� Jedno z tych zagadnień liniowych zazwyczaj jest
nazywane zagadnieniem pierwotnym/prymalnym, a jego
odpowiednik zagadnieniem podwójnym/dualnym.
2012-10-21 12
Dualizm zadania liniowego
l� Zagadnienie maksymalizacji i minimalizacji nie są więc
tak rozłączne, jak mogłoby się wydawać. Ponieważ
wartości optymalne funkcji celu w zagadnieniach
t ś i t l f k ji l d i i h
prymalnym i dualnym są zawsze identyczne, możemy
więc rozwiązać to z nich które jest łatwiejsze
więc rozwiązać to z nich, które jest łatwiejsze.
2012-10-21 13
Dualizm zadania liniowego
l� Program dualny względem programu prymarnego
tworzymy wykorzystując następujące reguły:
l� W programie dualnym jest tyle zmiennych decyzyjnych ile warunków
ograniczających w programie pierwotnym (i odwrotnie).
l� Jeżeli w programie pierwotnym funkcja celu jest maksymalizowana
l� Jeżeli w programie pierwotnym funkcja celu jest maksymalizowana,
to w programie dualnym jest minimalizowana (i odwrotnie).
l� Współczynniki układu nierówności w programie dualnym są
tj ół ikó i ó ś i l
transpozycją współczynników nierówności programu prymalnego.
l� Współczynniki funkcji celu programu pierwotnego są wyrazami
wolnymi układu nierówności programu dualnego (i odwrotnie).
y p g g ( )
l� Konstruując program dualny należy zmienić kierunki nierówności na
przeciwne względem programu pierwotnego.
2012-10-21 14
Dualizm zadania liniowego
l� Program dualny względem programu prymarnego
tworzymy wykorzystując następujące reguły (c.d.):
l� Programem dualnym względem programu dualnego jest program
pierwotny.
l� Rozwiązanie programu pierwotnego gdy dysponujemy
l� Rozwiązanie programu pierwotnego, gdy dysponujemy
rozwiązaniem programu dualnego, obliczamy z zastosowaniem
poniższych reguł:
l� Wartości funkcji celów w rozwiązaniach obu programów są takie same.
Wartości funkcji celów w rozwiązaniach obu programów są takie same
l� Jeżeli warunek ograniczający programu dualnego jest w rozwiązaniu
optymalnym niewiążący, to odpowiadająca mu zmienna decyzyjna programu
prymarnego przyjmuje wartość 0
prymarnego przyjmuje wartość 0.
2012-10-21 15
Dualizm zadania liniowego
l� Program prymarny: l� Program dualny:
2012-10-21 16
Przykład
l� Program prymarny: l� Program dualny:
2012-10-21 17
Dualizm zadania liniowego
l� Twierdzenie Dantzinga Ordena:
l� Jeżeli dla rozwiązań optymalnych zadania pierwotnego i dualnego
j ti i d i d l j t ł i j k
j-te ograniczenie zadania dualnego jest spełnione jako
nierówność, to j-ta zmienna w zadaniu pierwotnym jest równa 0.
l� Jeżeli i-ta zmienna dualna jest dodatnia to i-te ograniczenie
j g
w zadaniu pierwotnym jest równością.
2012-10-21 18
Literatura
l� Ignasiak E. (red.), Badania operacyjne. Polskie
Wydawnictwo Ekonomiczne, Warszawa 1996.
l� Mitchell G.H. (red.), Badania operacyjne. Metody
i przykłady. Wydawnictwo Naukowo-Techniczne,
Warszawa 1977
Warszawa 1977.
l� Aucki Z. (red.), Matematyczne techniki zarządzania.
Przykłady i zadania Wydawnictwa AGH Kraków 1998
Przykłady i zadania. Wydawnictwa AGH, Kraków 1998.
l� Sawik T., Badania operacyjne dla inżynierów
zarządzania Wydawnictwa AGH Kraków 1998
zarządzania. Wydawnictwa AGH, Kraków 1998.
l� Wagner H.M., Badania operacyjne: zastosowania
w zarządzaniu. Państwowe Wydawnictwo Ekonomiczne,
ą y,
Warszawa 1980.
2012-10-21 19

Wyszukiwarka