BO wyklad2

Badania operacyjne
Wykład 2
Wykład 2
Programowanie liniowe
Plan wykładu
l� Programowanie liniowe
l� Metoda graficzna rozwiązywania zadań programowania
liniowego
2012-10-19 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-19 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-19 4
Programowanie liniowe
l� Zadanie programowania liniowego można sformułować
następująco:
l� gdzie:
5
2012-10-19 5
Programowanie liniowe
l� Alternatywnie zadanie programowania liniowego
w zapisie macierzowym można sformułować następująco:
l� gdzie:
2012-10-19 6
Przykład
2012-10-19 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-19 8
Zastosowanie modelu
programowania liniowego
l� Problem alokacji środków produkcji, zwany również
problemem optymalnego rozdziału środków produkcji, jest
j d kl h d i ń b d ń j h
jednym z klasycznych zagadnień badań operacyjnych.
l� W ogólnym ujęciu polega on na takim rozdziale
l� W ogólnym ujęciu polega on na takim rozdziale
posiadanych przez przedsiębiorstwo środków produkcji
(surowców, materiałów, robocizny, maszyn) pomiędzy
poszczególne asortymenty produkcji, aby łączny zysk
produkcji wszystkich wyrobów by możliwie jak największy.
2012-10-19 9
Zastosowanie modelu
programowania liniowego
l� Do rozwiązania problemu stosuje się model
programowania liniowego, uwzględniający posiadane
il ś iól h ś dkó d k ji
ilości poszczególnych środków produkcji oraz
zapotrzebowanie na te środki produkcji przy produkcji
poszczególnych wyrobów
poszczególnych wyrobów.
l� Rozwiązaniem problemu jest optymalny plan
asortymentowy produkcji, określający ile którego wyrobu
należy produkować dla osiągnięcia maksymalnego zysku.
2012-10-19 10
Przykład (1 / 3)
l� Przedsiębiorstwo produkuje cztery wyroby W1, W2, W3
oraz W4. Dwa spośród wielu środków wykorzystywanych
w procesie produkcji są limitowane. Limity te wynoszą
id k ji li it Li it t
90000 jednostek na środek pierwszy oraz 120000
jednostek na środek drugi Nakłady limitowanych środków
jednostek na środek drugi. Nakłady limitowanych środków
na jednostkę produkcji podano w tabeli:
2012-10-19 11
Przykład (2 / 3)
l� Zysk osiągany na jednostce produkcji kształtuje się
odpowiednio: 4, 6, 3 oraz 12 zł.
l� Polecenie: Zbuduj model matematyczny (określ zmienne
decyzyjne, funkcję celu i ograniczenia).
2012-10-19 12
Przykład (3 / 3)
l� Tworząc model przyjmujemy następującą listę zmiennych
decyzyjnych:
l� - liczba produkowanych wyrobów W1 (szt.)
l� - liczba produkowanych wyrobów W2 (szt.)
l� liczba produkowanych wyrobów W3 (szt )
l� - liczba produkowanych wyrobów W3 (szt.)
l� - liczba produkowanych wyrobów W4 (szt.)
l� Ustalenie optymalnego rozmiaru produkcji poszczególnych
l� Ustalenie optymalnego rozmiaru produkcji poszczególnych
wyrobów sprowadza się do znalezienia takich wartości
zmiennych aby:
2012-10-19 13
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-19 14
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-19 15
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-19 16
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.
17
2012-10-19 17

Wyszukiwarka

Podobne podstrony:
BO wyklad prezentacja
BO Wyklad Przyklad Rozwiazania Testu
BO Wyklad Przyklad Rozwiazania Testu
BO wyklad3
BO II stacjonarne wykład nr 10
BO ZP Wyklad Zarzadzanie Czasem
BO II stacjonarne wykład nr 01
BO II stacjonarne wykład nr 02
BO II stacjonarne wykład nr 11
BO II stacjonarne wykład nr 09
BO II stacjonarne wykład nr 04
BO OL Wyklad Modele optymalizacji liniowej
Pytania sprawdzian z wykładów BO II stacjonarne
BO II stacjonarne wykład nr 07
BO ZP Wyklad Wstep do Zarzadzania Projektami

więcej podobnych podstron