Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
1
Ekotransport i ekologistyka
Ekotransport i ekologistyka
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Programowanie
liniowe
i całkowitoliczbowe
Programowanie
liniowe
i całkowitoliczbowe
Alokacja zasobów
Alokacja zasobów
Piotr Sawicki / Ekotransport i ekologistyka
2
30
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
•
zastosowanie Solvera MS Excel
Istota programowania całkowitoliczbowego
Podsumowanie
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
2
Piotr Sawicki / Ekotransport i ekologistyka
3
30
Programowanie liniowe
Istota
Jedna z najpopularniejszych i najbardziej użytecznych technik
menedżerskich
•
wywodzi się z badań operacyjnych
Programowanie liniowe znajduje powszechne zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych
zasobów
zasobów
do
konkurencyjnych
operacji
operacji
(zadań), np.:
•
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
polegają na
•
maksymalizacji zysku
•
minimalizacji kosztów
•
osiągnięciu zakładanej wartości
Piotr Sawicki / Ekotransport i ekologistyka
4
30
Programowanie liniowe
Istota
Problem maksymalizacji zysku
•
osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych / logistycznych
•
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 dalekobieżnych – zmienna x
2
…
oferta przewozów towarowych do 12 ton – zmienna x
n
•
osiągnięcie maksymalnego zysku ograniczają dostępne (limitowane) zasoby
– np.: posiadanie: 15 zestawów autobusów podmiejskich, 20 autobusów dalekobieżnych,
3 autobusy turystyczne,….3 zestawy drogowe (do 24 ton),…
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
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
3
Piotr Sawicki / Ekotransport i ekologistyka
5
30
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
•
sformułowanie równań i nierówności
w postaci liniowej
•
liniowość w praktyce oznacza, że
zależność funkcyjna pomiędzy
zmiennymi decyzyjnymi posiada
graficzną reprezentację w postaci
linii prostych
2
2
1
2
1
3
2
Min
x
x
x
x
Z
+
=
)
,
(
2
1
2
1
3
Min
x
x
x
x
Z
+
=
)
,
(
45
3
2
2
2
1
≤
+ x
x
2
1
2
1
2
Min
x
x
x
x
Z
+
=
)
,
(
10
4
3
3
2
1
≥
+
+
x
x
x
Piotr Sawicki / Ekotransport i ekologistyka
6
30
Programowanie liniowe
Ogólne sformułowanie
Ogólne sformułowanie zadania programowania liniowego
•
funkcja celu
Max Z = c
1
x
x
1
1
+ c
2
x
x
2
2
+ ... + c
n
x
x
n
n
•
ograniczenia
(ograniczone zasoby)
a
11
x
x
1
1
+ a
12
x
x
2
2
+ ... + a
1n
x
x
n
n
≤
b
1
a
21
x
x
1
1
+ a
22
x
x
2
2
+ ... + a
2n
x
x
n
n
≤
b
2
...
a
m1
x
x
1
1
+ a
m2
x
x
2
2
+ ... + a
mn
x
x
n
n
≤
b
m
x
x
1
1
≥
0,
x
x
2
2
≥
0, ...,
x
x
n
n
≥
0
c
j
– jednostkowy przyrost j – tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)
b
i
– ilość i – tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)
a
ij
– ilość i – tego zasobu konsumowanego przez j – tą czynność
c
j
, b
i
, a
ij
–
parametry;
parametry;
x
1
, x
2
, ..., x
3
–
zmienne decyzyjne
zmienne decyzyjne
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
4
Piotr Sawicki / Ekotransport i ekologistyka
7
30
Programowanie liniowe
Proces rozwiązywania problemu
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Identyfikacja problemu
decyzyjnego
Identyfikacja problemu decyzyjnego
•
zidentyfikuj stan aktualny
– rozpoznaj realizowane działania
– określ trudności w podjęciu decyzji
•
opisz sytuację (zaistniały problem)
Konstrukcja modelu matematycznego
•
zidentyfikuj zmienne decyzyjne
– czego poszukujesz?
– jakie wielkości mają być wyznaczone?
– ile jest niewiadomych?
•
zidentyfikuj parametry zadania
– jakie wielkości są znane (stałe)?
•
zdefiniuj cel swoich poszukiwań Æ skonstruuj funkcję celu
– jaki cel chcesz osiągnąć?
•
określ wszystkie ograniczenia podjęcia decyzji Æ
skonstruuj warunki ograniczające
– co stanowi ograniczenie dla podjęcia Twojej decyzji?
– z jakimi ograniczeniami musisz się liczyć?
Piotr Sawicki / Ekotransport i ekologistyka
8
30
Programowanie liniowe
Proces rozwiązywania problemu
Rozwiązanie problemu (sformułowanego modelu)
•
poszukiwanie rozwiązania
– maksymalizacja funkcji celu
– minimalizacja funkcji celu
•
rozwiązanie problemu za pomocą dostępnych metod
– metoda graficzna (stosowana tylko dla 2 zmiennych
decyzyjnych)
– metoda algebraiczna SIMPLEX (nie ma ograniczenia liczby
zmiennych decyzyjnych)
Interpretacja rozwiązania
•
wartość zmiennych decyzyjnych
•
pozostające zasoby
•
analiza wrażliwości
– zmiana dostępności zasobów
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Identyfikacja problemu
decyzyjnego
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
5
Piotr Sawicki / Ekotransport i ekologistyka
9
30
Programowanie liniowe
Proces rozwiązywania problemu
Tok postępowania przy rozwiązywaniu problemu
sformułowanego w postaci zadania programowania
liniowego Æ analiza przykładu
•
„Firma ForkLift Service (FLS) jest jednym z (…)”
zobacz treść zadania
Model matematyczny
problemu
Dobór metody rozw.
Rozwiązanie problemu
Interpretacja rozw.
Analiza wrażliwości
Identyfikacja problemu
decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Proces rozwiązywania
problemu decyzyjnego
Piotr Sawicki / Ekotransport i ekologistyka
10
30
Programowanie liniowe
Proces rozwiązywania problemu / Model
Konstrukcja modelu matematycznego
•
zmienne decyzyjne w analizowanym problemie
– S
– liczba zakupionych przez FLS wózków widłowych typu 20S
– H
– liczba zakupionych przez FLS wózków widłowych typu 45H
•
funkcja celu Æ cel postawiony przez firmę FLS
– maksymalizacja zysku ze sprzedaży wózków widłowych typu 20S i 45H
– zysk całkowity:
Z = z
s
+z
H
– z
s
- jednostkowy zysk ze sprzedaży wózków typu 20S
z
s
= 15% • 19.000 € •
S
= 2.850
S
– z
H
– jednostkowy zysk ze sprzedaży wózków typu 45H
z
H
= 19% • 33.000 € •
H
= 6.270
H
– ostateczne sformułowanie funkcji celu
Max Z(S, H) = 2.850
S
+ 6.270
H
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
6
Piotr Sawicki / Ekotransport i ekologistyka
11
30
Programowanie liniowe
Proces rozwiązywania problemu / Model
Konstrukcja modelu matematycznego … cd
•
identyfikacja ograniczeń
– zasoby finansowe firmy FLS Æ max. 2.400.000 zł/rok
– dostępny fundusz czasu pracy poświęcany przez pracowników FLS na sprzedaż wózków
20S i 45H Æ max. 520 rbh/rok
– dostępność wózków u producenta
{
max 100 szt./rok 20S
{
max 75 szt./rok 45H
– rynkowy popyt na wózki widłowe
{
min 10 szt. 20S
{
min 5 szt. 45H
•
matematyczny zapis ograniczeń
– zasoby finansowe firmy FLS ograniczają na przestrzeni roku możliwość zakupu wózków
widłowych u producenta
19.000
S
+ 33.000
H
≤ 2.400.000
– czas pracy ludzi zatrudnionych w FLS i zajmujących się sprzedażą wózków 20S i 45H jest
ograniczony
6
S
+ 4
H
≤ 520
Piotr Sawicki / Ekotransport i ekologistyka
12
30
Programowanie liniowe
Proces rozwiązywania problemu / Model
•
matematyczny zapis ograniczeń … cd
– możliwości produkcyjne firmy Clark w zakresie dostarczenia firmie FLS wózków widłowych
typu 20S i 45H
{
dostępność wózków 20S
S
≤ 100
{
dostępność wózków 45H
H
≤ 75
– minimalna liczba wózków w jednorazowym zamówieniu, zapewniająca ciągłość sprzedaży
przy jednoczesnym zachowaniu satysfakcji klientów firmy FLS
{
zapotrzebowanie firmy FLS na wózki typu 20S
S
≥ 10
{
zapotrzebowanie firmy FLS na wózki typu 45H
H
≥ 5
– formalnie Æ poszukiwane rozwiązanie (S, H) nie powinno przyjmować wartości ujemnych
S
≥ 0
H
≥ 0
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
7
Piotr Sawicki / Ekotransport i ekologistyka
13
30
Programowanie liniowe
Proces rozwiązywania problemu / Model
Ostateczna postać modelu matematycznego problemu decyzyjnego
sformułowanego w postaci zadania programowania liniowego
•
funkcja celu
Max Z(S, H) = 2.850
S
+ 6.270
H
•
przy ograniczeniach
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
Piotr Sawicki / Ekotransport i ekologistyka
14
30
Programowanie
liniowe
Graficzna metoda
rozwiązywania
zadania
programowania
liniowego
Programowanie
liniowe
Graficzna metoda
rozwiązywania
zadania
programowania
liniowego
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
8
Piotr Sawicki / Ekotransport i ekologistyka
15
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≥ 10
(5)
10
S ≤ 100
(3)
Obszar rozwiązań dopuszczalnych
dla ograniczeń (3) – (8)
Ograniczenia (7) i (8) są nieaktywne
(4)
H ≤ 75
75
Obszar rozwiązań niedopuszczalnych
Piotr Sawicki / Ekotransport i ekologistyka
16
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
•
ograniczenie (2)
6
S
+ 4
H
= 520
S = 0 Æ H = 130 Æ (0;130)
H = 0 Æ S = 86,7 Æ (86,7;0)
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≥ 10
(5)
10
S ≤ 100
(0;130)
(86,7; 0)
(4)
H ≤ 75
75
(3)
(2)
6S + 4H ≤ 520
Ograniczenia (3) staje się nieaktywne
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
9
Piotr Sawicki / Ekotransport i ekologistyka
17
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19
S
+ 33
H
≤ 2.400
(2) 6
S
+ 4
H
≤ 520
(3)
S
≤ 100
(4)
H
≤ 75
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
•
ograniczenie (1)
19
S
+ 33
H
= 2.400
S = 0 Æ H = 72,7 Æ (0; 72,7)
H = 0 Æ S = 126,3 Æ (126,3; 0)
H
0
20
100
140
S
20
100
120
S ≥ 0
(7)
H ≥ 0
(8)
5
(6)
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
(3)
(2)
6S + 4H ≤ 520
(126,3; 0)
(0; 72,7)
S ≥ 10
(5)
10
19S +33H ≤ 2 400
(1)
(4)
H ≤ 75
75
Piotr Sawicki / Ekotransport i ekologistyka
18
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
określanie kierunku zmiany wartości
funkcji celu (tu kierunek przyrostu)
Max Z(S, H) = 2.850
S
+ 6.270
H
2.850
S
+ 6.270
H
= 0
S = 10 Æ H = - 4,5 Æ (10; - 4,5)
S = 20 Æ H = - 9 Æ (20; - 9)
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S ≥ 10
19S +33H ≤ 2 400
H ≤ 75
75
S
0,45
S
270
6
850
2
H
−
=
−
=
-4,5
-9
Z= 2 850S + 6 270H
40
(40; 20)
Z
1
=239 400
Z
2
=364 800
„
„
Ostatni wierzchołek”
Ostatni wierzchołek”
(40; 40)
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
10
Piotr Sawicki / Ekotransport i ekologistyka
19
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu
programowania liniowego
•
określenie punktu przecięcia
prostych
S = 10
19
S
+ 33
H
= 2.400
H
= - 19/33
S
+ 2.400/33
S = 10 Æ H = 66,96
•
określenie wartości funkcji celu
S=10 i H=66,96
È
Z=448.400
È
Z
max
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S = 10
19S +33H = 2 400
H ≤ 75
75
-4,5
-9
40
(40; 20)
(40; 40)
(10; 66,96)
Piotr Sawicki / Ekotransport i ekologistyka
20
30
Programowanie liniowe
Proces rozwiązywania problemu / Rozwiązywanie
Graficzne rozwiązanie problemu programowania liniowego
(1) narysuj obszar rozwiązań dopuszczalnych i określ jego wierzchołki
– jeżeli obszar rozwiązań jest pusty Æ wszystkie rozwiązania są niedopuszczalne Æ
ponownie rozważ sformułowanie ograniczeń
(2) narysuj 2 różne wykresy funkcji celu (FC) i określ kierunek optymalizacji
(max vs. min)
– jeżeli problem dotyczy maksymalizacji FC równolegle przesuń linię reprezentującą FC w
kierunku przyrostu jej wartości
– jeżeli problem polega na minimalizacji FC przesuń linię w kierunku przeciwnym, tj.
zmniejszania się wartości FC
(3) przesuń funkcję celu znajdując „ostatni wierzchołek”
– w przypadku, gdy FC jest równoległa do jednego z boków obszaru rozwiązań
dopuszczalnych (ORD), wówczas problem posiada szereg rozwiązań alternatywnych
leżących pomiędzy wierzchołkami ORD
(4) równania prostych, które przecinają się w punkcie wierzchołkowym (patrz p.3)
tworzą układ równań określających współrzędne punktu optymalnego
Algorytm metody
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
11
Piotr Sawicki / Ekotransport i ekologistyka
21
30
Programowanie liniowe
Proces rozwiązywania problemu / Interpretacja rozwiązania
Rozwiązanie optymalne
•
optymalna liczba sprzedanych wózków widłowych 20S wynosi S=10 szt.
•
optymalna liczba sprzedanych wózków widłowych 45H wynosi H=66,96 szt.
– w praktyce H=66 lub H=67 (rozwiązanie poza obszarem rozwiązań dopuszczalnych)
•
zysk ze sprzedaży wózków obu typów
Z=2.850 S + 6.270 H
S=10 szt. i H=66,96 szt. Æ Z=448.400 € Æ maksymalny zysk
lub
S=10 i H=66 Æ Z=442.320 €
•
analiza ograniczeń
(1) 19.000
S
+ 33.000
H
≤ 2.400.000 (dostępne zasoby finansowe)
dla S=10 szt. i H=66,96 szt. LHS
1
= 2.400.000 € Æ 0 € rezerwy finansowej
(2) 6
S
+ 4
H
≤ 520 (dostępna liczba roboczogodzin)
dla S=10 szt. i H=66,96 szt. LHS
2
= 327,84 rbh Æ 192,16 rbh rezerwy czasu
LHS
Piotr Sawicki / Ekotransport i ekologistyka
22
30
Programowanie liniowe
Proces rozwiązywania problemu / Interpretacja rozwiązania
•
analiza ograniczeń… cd
(3)
S
≤ 100 (maksymalna dostępność wózków typu 20S)
dla S=10 szt. i H=66,96 szt. LHS
3
= 10 szt. Æ 90 szt. rezerwy
(4)
H
≤ 75
dla S=10 szt. i H=66,96 szt. LHS
4
= 66,96 szt. Æ 8,04 szt. rezerwy
(5)
S
≥ 10
(6)
H
≥ 5
(7)
S
≥ 0
(8)
H
≥ 0
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
12
Piotr Sawicki / Ekotransport i ekologistyka
23
30
Programowanie liniowe
Zastosowanie Solvera Excel / Rozwiązanie problemu
Zapis modelu matematycznego w obszarze roboczym arkusza kalkulacyjnego
Przykład
Przykład
Piotr Sawicki / Ekotransport i ekologistyka
24
30
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport wyników
Maksymalna wartość FC
Wartość zmiennych
decyzyjnych (S, H)
Status ograniczenia
„wiążące” – zasób w pełni wykorzystany
„niewiążący” – pozostają rezerwy
Wartość ograniczenia (LHS) przy
uzyskanych wartościach zmiennych
decyzyjnych
Pozostała do wykorzystania
rezerwa „luz”
analizowanych zasobów
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
13
Piotr Sawicki / Ekotransport i ekologistyka
25
30
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport wrażliwości
Optymalna
wartość
zmiennych
decyzyjnych
Współczynniki
funkcji celu
Przedziały zmienności współczynników FC dla których
wartości zmiennych decyzyjnych nie ulegną zmianie
O ile zmieni się wartość FC jeżeli prawa
strona (RHS) odpowiedniego warunku
ograniczającego ulegnie zmianie o 1
Wartość RHS
warunków
ograniczających
Krańce przedziałów zmienności RHS,
przy których nie nastąpi zmiana zestawu
zmiennych decyzyjnych
Piotr Sawicki / Ekotransport i ekologistyka
26
30
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport granic
Wartość (max)
funkcji celu
Optymalna wartość
zmiennych
decyzyjnych
Obszar rozwiązań dopuszczalnych
S – nie ulega zmianie DG=10, GG=10
H – ulega zmianie: DG=5, GG=66,96
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
14
Piotr Sawicki / Ekotransport i ekologistyka
27
30
Programowanie liniowe
Zastosowanie Solvera Excel / Analiza wrażliwości
Raport granic –
interpretacja dolnej i górnej
granicy
H
0
20
100
140
S
20
100
120
5
H ≥ 5
S ≤ 100
(0;130)
(86,7; 0)
6S + 4H ≤ 520
(126,3; 0)
S ≥ 10
19S +33H ≤ 2 400
H ≤ 75
75
(10; 66,96)
(10; 5)
Z(min)=59.850
Z(max)=448.400
Piotr Sawicki / Ekotransport i ekologistyka
28
30
Programowanie
liniowe
Programowanie
całkowitoliczbowe
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
15
Piotr Sawicki / Ekotransport i ekologistyka
29
30
Programowanie całkowitoliczbowe
Istota
Programowanie całkowitoliczbowe
•
problem z liniową funkcja celu i ograniczeniami
•
niektóre lub wszystkie zmienne decyzyjne muszą być
– nieujemne
i
– całkowite
•
możliwe jest zastosowanie metody SIMPLEX do rozwiązania zadania programowania
całkowitoliczbowego
– jeżeli rozwiązanie optymalne zawiera wartości ułamkowe (rozwiązanie niecałowitoliczbowe)
ułamkowa część rozwiązania jest
{
zaokrąglana do najbliższej liczby całkowitej
{
pomijana
– zaokrąglenie lub pominięcie części ułamkowej powoduje, że rozwiązanie może być
nieoptymalne
programowanie liniowe
Piotr Sawicki / Ekotransport i ekologistyka
30
30
Programowanie całkowitoliczbowe
Istota
Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego
Max Z(S, H) = 2.850
S
+ 6.270
H
H
0
20
100
140
S
20
100
120
5
H = 5
S = 100
6S + 4H = 520
S = 10
19S +33H = 2 400
H = 75
75
Z
max
= 448.400
(10; 66,96)
Obszar dalszej analizy
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
16
Piotr Sawicki / Ekotransport i ekologistyka
31
30
Programowanie całkowitoliczbowe
Istota
Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego
Max Z(S, H) = 2.850
S
+ 6.270
H
S = 10
19S +33H = 2 400
H = 75
S
0 1 2 3 4 5 6 7 8 9 10 11 12 13
H
73
72
71
70
69
68
67
66
65
74
75
(10; 66,96)
Obszar rozwiązań dopuszczalnych
i
„siatka” rozwiązań
całkowitoliczbowych
(10,66); Z = 442.320
(10,67); Z = 448.590
(10; 66,96); Z = 448.400
(11,66); Z = 445.170
Piotr Sawicki / Ekotransport i ekologistyka
32
30
Programowanie całkowitoliczbowe
Istota
Programowanie całkowitoliczbowe znajduje zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych
zasobów
zasobów
do
konkurencyjnych
operacji
operacji
, w przypadku gdy niektóre lub wszystkie zmienne
są liczbami całkowitymi
•
ustalenie liczebności taboru
•
określenie liczby obsług pojazdów w skali roku
•
sprzedaż pojazdów przez przedstawiciela handlowego
Problemy sformułowane w kategoriach programowania całkowitoliczbowego
najczęściej polegają na
•
maksymalizacji
– zysku
– efektywności
– …innych maksymentów
•
minimalizacji
– kosztów
– czasu
– …innych minimentów
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
17
Piotr Sawicki / Ekotransport i ekologistyka
33
30
Programowanie całkowitoliczbowe
Ogólne sformułowanie
Ogólne sformułowanie zadania programowania całkowitoliczbowego
•
funkcja celu
Max Z = c
1
x
x
1
1
+ c
2
x
x
2
2
+ ... + c
n
x
x
n
n
•
ograniczenia
(ograniczone zasoby)
a
11
x
x
1
1
+ a
12
x
x
2
2
+ ... + a
1n
x
x
n
n
≤
b
1
a
21
x
x
1
1
+ a
22
x
x
2
2
+ ... + a
2n
x
x
n
n
≤
b
2
...
a
m1
x
x
1
1
+ a
m2
x
x
2
2
+ ... + a
mn
x
x
n
n
≤
b
m
x
x
1
1
≥
0,
x
x
2
2
≥
0, ...,
x
x
n
n
≥
0
x
x
1
1
,
x
x
2
2
, ...,
x
x
n
n
∈
C
c
j
– jednostkowy przyrost j – tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)
b
i
– ilość i – tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)
a
ij
– ilość i – tego zasobu konsumowanego przez j – tą czynność
c
j
, b
i
, a
ij
–
parametry;
parametry;
x
1
, x
2
, ..., x
3
–
zmienne decyzyjne
zmienne decyzyjne
Piotr Sawicki / Ekotransport i ekologistyka
34
30
Programowanie
całkowitoliczbowe
Metoda rozgałęzień
i ograniczeń
(branch-and-bound)
Programowanie
całkowitoliczbowe
Metoda rozgałęzień
i ograniczeń
(branch-and-bound)
Podsumowanie
Podsumowanie
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
18
Piotr Sawicki / Ekotransport i ekologistyka
35
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Istota metody rozgałęzień i ograniczeń (RiO)
•
dwufazowa metoda rozwiązywania problemów sformułowanych jako zadanie
programowania całkowitoliczbowego
– faza I Æ rozgałęzień
polega na systematycznym podziale pierwotnego obszaru rozwiązań dopuszczalnych (ORD)
na mniejsze obszary (podobszary)
– faza II Æ ograniczeń
polega na przyjęciu zasady, że
{
rozwiązanie uzyskane przy pominięciu warunku całkowitoliczbowości zmiennych
decyzyjnych stanowi górne ograniczenie wartości FC
{
każdy punkt należący do ORD o współrzędnych całkowitoliczbowych wyznacza dolną
granicę wartości FC
Analiza metody rozgałęzień i ograniczeń zostanie przeprowadzona na
przykładzie przypadku FLS
Piotr Sawicki / Ekotransport i ekologistyka
36
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Zakładamy, że rozwiązanie problemu z pominięciem warunku o
całkowitoliczbowym charakterze zmiennych decyzyjnych jest znane
•
funkcja celu
Max Z(S, H) = 2.850
S
+ 6.270
H
•
wartość zmiennych decyzyjnych (wartości optymalne)
S
= 10
H
= 66,96
•
wartość funkcji celu Æ maksymalny zysk ze sprzedaży wózków widłowych 20S i 45H
Max Z = 448.400 €
•
należy przyjąć, że żadne całkowitoliczbowe rozwiązanie problemu FLS nie może
osiągnąć rozwiązania wyższego niż 448.400 Æ wartość ta stanowi górne
ograniczenie wartości FC
Metoda RiO zakłada, że rozwiązanie leży w obszarze wyznaczonym przez
górne i dolne przybliżenia aktualnej wartości niecałkowitoliczbowej zmiennej
decyzyjnej
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
19
Piotr Sawicki / Ekotransport i ekologistyka
37
30
Programowanie całkowitoliczbowe
Istota
Analiza obszaru rozwiązań dopuszczalnych
H
0
20
100
140
S
20
100
120
5
H = 5
S = 100
6S + 4H = 520
S = 10
19S +33H = 2 400
H = 75
75
Z
max
= 448.400
(10; 66,96)
Obszar dalszej analizy
Piotr Sawicki / Ekotransport i ekologistyka
38
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza rozwiązania
•
skoro S = 10 a H = 66,96
to rozwiązania należące do
C poszukać należy w
podobszarach, w którym H
spełnia zależność:
66 ≥ (H=66,96) ≥ 67
•
podział na dwa podobszary
– R
1
: H ≤ 66
– R
2
: H ≥ 67
(10; 66,96); Z = 448.400
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2 400
R
0
H ≥67
H ≤ 66
S = 10
H = 66,96
Z=448.400
R
0
S = ?
H = ?
Z = ?
R
1
S = ?
H = ?
Z = ?
R
2
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
20
Piotr Sawicki / Ekotransport i ekologistyka
39
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
1
i R
2
•
analiza R
1
jeżeli H = 66, to powstają
dwa punkty
– H = 66 i S = 10
Z = 442.320
– oraz
H = 66
19S + 33H = 2.400
S = 11,68
stąd
H = 66 i S = 11,68
Z = 447.108
•
analiza R
2
obszar R
2
stanowi punkt o
współrzędnych S=10 i
H = 67
– punkt ten znajduje się
poza ORD
(10; 67)
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
R
1
H ≥67
H ≤ 66
R
2
(10; 66)
{
(11,68; 66)
Piotr Sawicki / Ekotransport i ekologistyka
40
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
1
i R
2
..cd
•
analiza rozgałęzień
•
jeżeli S = 11,68 to wartość
całkowita S będzie
poszukiwana w przedziale
11 ≥ (S=11,68) ≥ 12
– R
3
: S ≤ 11
– R
4
: S ≥ 12
(10; 67)
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
R
1
H ≥67
H ≤ 66
R
2
(10; 66)
(11,68; 66)
S = 10
H = 66,96
Z=448.400
R
0
S = 11,68
H = 66
Z = 447.108
R
1
poza ORD
R
2
S ≤11
S ≥12
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
21
Piotr Sawicki / Ekotransport i ekologistyka
41
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
3
i R
4
•
analiza obszaru R
3
dwa punkty charakterystyczne
– S = 10 i H = 66
Z = 442.320
– oraz
S = 11 i H = 66
Z = 445.170
•
analiza obszaru R
4
– jeden punkt
S = 12
19S + 33H = 2.400
H = 65,81
S = 12 i H = 65,81
Z = 446.828,7
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
H ≥67
H ≤ 66
(10; 66)
(11, 66)
R
3
R
4
S ≤11
S ≥12
{
(12, 65;81)
Piotr Sawicki / Ekotransport i ekologistyka
42
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
3
i R
4
..cd
•
analiza rozgałęzienia obszaru
R
1
na R
3
i R
4
•
jeżeli H = 65,81, to całkowita
wartość H poszukiwana będzie
w przedziale
65 ≥ (H=65,81) ≥ 66
– R
5
: H ≤ 65
– R
6
: H ≥ 66
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
H ≥66
(10; 66)
(11, 66)
R
3
R
4
S ≤11
S ≥12
(12, 65;81)
S = 11
H = 66
Z = 445.170
R
3
S = 12
H = 65,81
Z = 446.828,7
R
4
S = 11,68
H = 66
Z=447.108
R
1
H ≤ 65
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
22
Piotr Sawicki / Ekotransport i ekologistyka
43
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
5
i R
6
•
analiza obszaru R
5
2 punkty charakterystyczne
– S = 12 i H = 65
Z = 441.750
– oraz
H = 65
19S + 33H = 2400
S = 13,42
jeżeli S = 13,42 i H = 65
to Z = 445.797
•
analiza obszaru R
6
– jeden punkt
S = 12 i H = 65
– punkt znajduje się poza ORD
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
H ≥66
(10; 66)
R
3
R
4
S ≤11
S ≥12
(13,42; 65)
H ≤ 65
R
5
{
R
6
Piotr Sawicki / Ekotransport i ekologistyka
44
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
5
i R
6
…cd
•
analiza rozgałęzień obszaru
R
4
na R
5
i R
6
•
jeżeli S=13,42, to całkowita
wartość S poszukiwana będzie
w przedziale wartości
13 ≥ (S=13,42) ≥ 14
– R
7
: H ≤ 13
– R
8
: H ≥ 14
S = 13,42
H = 65
Z = 445.797
R
5
poza ORD
R
6
S = 12
H = 65,81
Z=447.108
R
4
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
H ≥66
(10; 66)
R
3
R
4
S ≤11
S ≥12
(13,42; 65)
H ≤ 65
R
5
R
6
S ≥14
S ≤ 13
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
23
Piotr Sawicki / Ekotransport i ekologistyka
45
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
7
i R
8
•
analiza obszaru R
7
2 punkty charakterystyczne
– S = 12 i H = 65
Z = 441.750
– oraz
S = 13 i H = 65
Z = 444.600
•
analiza obszaru R
8
– punkt o współrzędnych
S = 14
19S + 33H = 2.400
H = 64,67
jeżeli S = 14 i H = 64,67
to Z = 445.380,9
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
(12; 65)
R
5
R
7
R
8
(13; 65)
{
(14; 64,67)
Piotr Sawicki / Ekotransport i ekologistyka
46
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza obszarów R
7
i R
8
•
analiza rozgałęzień obszaru
R
5
na R
7
i R
8
S
10 11 12 13 14 15 16 17 18 19
H
68
67
66
65
64
63
62
61
60
69
70
S = 10
19S +33H = 2.400
(12; 65)
R
5
R
7
R
8
(13; 65)
(14; 64,67)
S = 13
H = 65
Z = 444.600
R
7
S = 14
H = 64,67
Z = 445.380,9
R
8
S = 13,42
H = 65
Z=445.797
R
5
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
24
Piotr Sawicki / Ekotransport i ekologistyka
47
30
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Analiza wszystkich rozgałęzień
•
poszukiwanie kolejnych rozwiązań
całkowitoliczbowych nie ma
uzasadnienia Æ wartość FC ulega
systematycznemu obniżaniu
•
rozwiązaniem optymalnym jest
S = 11
H = 66
wówczas
Z = 445.170€
S = 10
H = 66,96
Z=448.400
R
0
S = 11,68
H = 66
Z = 447.108
R
1
poza ORD
R
2
S = 11
H = 66
Z = 445.170
R
3
S = 12
H = 65,81
Z = 446.828,7
R
4
S = 13,42
H = 65
Z = 445.797
R
5
poza ORD
R
6
S = 13
H = 65
Z = 444.600
R
7
S = 14
H = 64,67
Z = 445.380,9
R
8
Piotr Sawicki / Ekotransport i ekologistyka
48
30
Programowanie matematyczne
Podsumowanie
Alokacja niepodzielnych
zasobów do konkurencyjnych
prac (zadań)
Alokacja podzielnych
zasobów do konkurencyjnych
prac (zadań)
Zastosowanie
Metoda graficzna,
zmodyfikowana metoda
SIMPLEX, metoda ograniczeń
i rozgałęzień
Solver MS Excel
Metoda graficzna, metoda
SIMPLEX
Solver MS Excel
Metoda rozwiązania
liniowa – addytywna
liniowa - addytywna
Model matematyczny:
Funkcja celu
liniowa - addytywna
liniowa - addytywna
Model matematyczny:
Funkcja celu
liniowa – w pierwszej potędze
programowanie
liniowe
liniowa – w pierwszej potędze
postać zmiennej
decyzyjnej
programowanie
całkowitoliczbowe
parametr
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
25
Piotr Sawicki / Ekotransport i ekologistyka
49
30
Przykłady obszarów rozwiązań
dopuszczalnych
•
funkcja celu może przyjmować
nieograniczone wartości
•
obszar rozwiązań dopuszczalnych jest
pusty
Programowanie matematyczne
Podsumowanie
Podstawowe pojęcia do zapamiętania
•
rozwiązanie dopuszczalne –
rozwiązanie dla którego spełnione są
wszystkie ograniczenia
•
rozwiązania niedopuszczalnych –
rozwiązania znajdujące się poza
obszarem rozwiązań dopuszczalnych
•
rozwiązanie optymalne (optimum) –
rozwiązanie dopuszczalne osiągające
wartość ekstremalną
•
ograniczenie aktywne – ograniczenie
wyznaczające obszar rozwiązań
dopuszczalnych
•
ograniczenie nieaktywne –
ograniczenie nie należące do obszaru
rozwiązań dopuszczalnych
Piotr Sawicki / Ekotransport i ekologistyka
50
30
Programowanie matematyczne
Podsumowanie
Warunki sformułowania problemu w postaci zadania programowania
liniowego i całkowitoliczbowego
•
identyfikacja ograniczonych zasobów (w przeciwnym wypadku nie ma problemu)
– ograniczona liczba pracowników,
– ograniczona dostępność środków transportowych,
– limitowane zasoby finansowe,…
•
określony kierunek zmiany wartości funkcji celu
– maksymalizacja zysku
– minimalizacja kosztów (czasu transportu)
•
liniowość funkcji celu i ograniczeń
– np.: zysk z kursu 2 zestawów drogowych typu A jest dwa razy większy jak zysk z kursu
jednego zestawu drogowego typu A
•
podzielność zasobów dla programowania liniowego
– 0,5 dm
3
oleju napędowego
– 45,3 kWh zużytej energii
•
niepodzielność zasobów dla programowania całkowitoliczbowego
– przejazd 5 zestawów drogowych w relacji: Poznań-Warszawa
Ekotrasport i ekologistyka
Piotr Sawicki / PP/ WMRiT
26
Ekotransport i ekologistyka
Ekotransport i ekologistyka
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Programowanie
liniowe
i całkowitoliczbowe
Programowanie
liniowe
i całkowitoliczbowe
Alokacja zasobów
Alokacja zasobów