Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
Zarządzanie transportem
Programowanie liniowe
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
Piotr Sawicki
Plan prezentacji
Istota programowania liniowego
•
informacje wprowadzające
•
przykładowe problemy
Ogólne sformułowanie zadania programowania liniowego
Programowanie liniowe na przykładzie
•
identyfikacja problemu
•
konstrukcja modelu matematycznego
•
rozwiązanie problemu
•
interpretacja rozwiązania i analiza wrażliwości
Procedura rozwiązywania zadania programowania liniowego
•
metoda graficzna
•
metoda algebraiczna - SIMPLEX
•
zastosowanie Solvera MS Excel
Podsumowanie
Programowanie liniowe
Istota
Jedna z najpopularniejszych i najbardziej użytecznych technik
menedżerskich (badań operacyjnych)
Programowanie liniowe znajduje powszechne zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych
zasobów
zasobów
do
operacji
(zadań)
•
wybór portfela oferowanych usług transportowych przy ustalonych kosztach przewozu i
posiadanym taborze
•
określenie rodzaju magazynowanych wyrobów przy uwzględnieniu ich zyskowności
oraz możliwościach magazynowych
Problemy sformułowane w kategoriach programowania liniowego
najczęściej polegają na
•
maksymalizacji zysku
•
minimalizacji kosztów
konkurencyjnych
operacji
Programowanie liniowe
Istota
Problem maksymalizacji zysku
•
osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych
•
każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna
– np.: oferta przewozu pasażerów na odległość do 50km – zmienna x
1
oferta przewozów klasy IC – zmienna x
2
…
oferta przewozów towarowych – zmienna x
n
•
osiągnięcie maksymalnego zysku ograniczają posiadane (limitowane zasoby)
– np.: posiadanie: 15 zestawów kolei podmiejskiej, 20 wagonów klasy IC, 3 lokomotywy
spalinowe do 180 km/h,…. 5 otwartych wagonów towarowych
Problem minimalizacji kosztów
•
osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych
•
każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna
•
osiągnięcie minimalnego kosztu wymaga dostępności zasobów
Programowanie liniowe
Istota
Model matematyczny problemu
sformułowany w postaci zadania
programowania liniowego
•
funkcja celu (kryterium „jakości/
doskonałości” rozwiązania)
– funkcja liniowa
– zmienne decyzyjne w pierwszej
potędze
•
ograniczenia
– funkcja liniowa
– zmienne decyzyjne w pierwszej
potędze
–zależności w postaci >, <, =
Przykłady
•
sformułowanie równań i nierówności
w postaci nieliniowej
Min
Z
(
x
1
,
x
2
)
=
2
x
1
+
3
x
2
2
Min
Z
(
x
,
x
)
=
3
1
2
x
+
x
1
2
2
2
2
x
+
x
3
≤
45
1
•
sformułowanie równań i nierówności
w postaci liniowej
Min
Z
(
x
1
,
x
2
)
=
2
x
1
+
x
2
3
x
1
+
x
4
x
2
+
3
≥
10
•
liniowość w praktyce oznacza, że
zależność funkcyjna pomiędzy
zmiennymi decyzyjnymi posiada
graficzną reprezentację w postaci
linii prostych