Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
Zarzą
dzanie transportem
dzanie transportem
Programowanie całkowitoliczbowe
ca
ł
ł
kowitoliczbowe
kowitoliczbowe
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
Zarządzanie transportem
Zarz
Programowanie
ca
Programowanie
Plan prezentacji
Istota programowania całkowitoliczbowego
•
informacje wprowadzające
•
przykładowe problemy
Ogólne sformułowanie zadania programowania całkowitoliczbowego
Programowanie całkowitoliczbowe na przykładzie
•
identyfikacja problemu
•
konstrukcja modelu matematycznego
•
rozwiązanie problemu
•
interpretacja rozwiązania
Procedura rozwiązywania zadania programowania całkowitoliczbowego
•
metoda płaszczyzn odcinających
•
metoda rozgałęzień i ograniczeń
Podsumowanie
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
Programowanie całkowitoliczbowe
Istota
Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego
H
140
S=10
S=100
Max Z(S, H) = 2.850
S
+ 6.270
H
100
6S + 4H = 520
75
H=75
Z
max
= 448.400
(10; 66,96)
19S +33H = 2 400
Obszar dalszej analizy
20
5
H=5
0
20
100 120
S
Programowanie całkowitoliczbowe
Istota
Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego
H
S=10
75
H=75
74
Max Z(S, H) = 2.850
S
+ 6.270
H
73
72
71
19S +33H = 2 400
„siatka” rozwiązań
całkowitoliczbowych
70
69
(10; 66,96); Z = 448.400
68
(10,67); Z = 448.590
67
(10; 66,96)
66
65
i
(10,66); Z = 442.320
(11,66); Z = 445.170
Obszar rozwiązań dopuszczalnych
0 1 2 3 4 5 6 7 8 9 10 11 12 13
S