1
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs
Programowanie
całkowitoliczbowe
Piotr Sawicki / Programowanie całkowitoliczbowe
2
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
2
Piotr Sawicki / Programowanie całkowitoliczbowe
3
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 / Programowanie całkowitoliczbowe
4
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
3
Piotr Sawicki / Programowanie całkowitoliczbowe
5
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 / Programowanie całkowitoliczbowe
6
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
4
Piotr Sawicki / Programowanie całkowitoliczbowe
7
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 / Programowanie całkowitoliczbowe
8
Programowanie całkowitoliczbowe
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
Przebieg procesu
•
identyfikacja problemu decyzyjnego
•
konstrukcja modelu matematycznego
•
rozwiązanie problemu
•
interpretacja rozwiązania
Analiza procesu rozwiązywania problemu
sformułowanego w postaci zadania programowania
całkowitoliczbowego Æ analiza przypadku FLS
•
identyfikacja problemu i konstrukcja modelu
matematycznego nie ulega zmianie
•
rozwiązanie problemu decyzyjnego
– metoda płaszczyzn odcinających (metoda Gomory’ego)
– metoda rozgałęzień i ograniczeń (ang. branch-and-bound)
•
interpretacja rozwiązania
5
Piotr Sawicki / Programowanie całkowitoliczbowe
9
Programowanie całkowitoliczbowe
Metoda płaszczyzn odcinających –
metoda Gomory’ego
Programowanie całkowitoliczbowe
Metoda płaszczyzn odcinających –
metoda Gomory’ego
Piotr Sawicki / Programowanie całkowitoliczbowe
10
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Założenia metody Gomory’ego
•
metoda bazuje na redukcji Gaussa-Jordana, stosowanej w metodzie SIMPLEX
•
metoda rozpoczyna się od rozwiązywania problemu z pominięciem ograniczenia o
całkowitoliczbowym charakterze zmiennych decyzyjnych
problem decyzyjny
rozwiązanie optymalne
(metoda SIMPLEX)
czy rozwiązanie jest
całkowitoliczbowe?
problem rozwiązany
Tak
dodatkowe ograniczenia
„płaszczyzn odcinających”
Nie
6
Piotr Sawicki / Programowanie całkowitoliczbowe
11
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Procedura obliczeniowa
•
rozwiązanie optymalne uzyskane za pomocą metody SIMPLEX
– ostateczny układ równań w III-ciej iteracji
(A) Z +190
N
1
+760
N
5
= 448.400
(B)
1
/
33
N
1
+
19
/
33
N
5
+
N
6
=
2.045
/
33
(C)
–
4
/
33
N
1
+
N
2
+
122
/
33
N
5
=
6.340
/
33
(D)
+
N
3
+
N
5
= 90
(E)
–
1
/
33
N
1
+
N
4
–
19
/
33
N
5
=
265
/
33
(F)
S
–
N
5
= 10
(G)
H
+
1
/
33
N
1
+
19
/
33
N
5
=
2.210
/
33
– rozwiązanie optymalne Æ zmienna decyzyjna H nie jest liczbą całkowitą
(Z, S,
H
, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
) = (448.400; 10;
66,96
; 0; 192,12; 90; 8,03; 0; 61,96)
•
poszukiwana jest największa wartość ułamkowa spośród wartości RHS, wśród
wszystkich równań, za wyjątkiem (A) Æ
warto
warto
ść
ść
najbli
najbli
ż
ż
sza liczbie ca
sza liczbie ca
ł
ł
kowitej
kowitej
– arbitralny wybór równania (B)
RHS
61
32
/
33
192
4
/
33
90
8
1
/
33
10
66
32
/
33
Å
Å
max
max
Å
Å
max
max
Piotr Sawicki / Programowanie całkowitoliczbowe
12
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
przekształcenie równania niecałkowitoliczbowego
(B)
1
/
33
N
1
+
19
/
33
N
5
+
N
6
= 61
32
/
33
do postaci semi-całkowitoliczbowej
Æ
wartości liczbowe wyrażane są jako suma części
całkowitej i nieujemnej części ułamkowej
(B
1
) (0+
1
/
33
)
N
1
+ (0+
19
/
33
)
N
5
+(1+0)
N
6
= 61+
32
/
33
•
przeniesienie wartości całkowitych z lewej na prawą stronę równania (RHS)
(B
1
)
1
/
33
N
1
+
19
/
33
N
5
+0
N
6
=
32
/
33
+ (61 – 0
N
1
– 0
N
5
– 1
N
6
)
dzięki czemu można zapisać
1
/
33
N
1
+
19
/
33
N
5
+0
N
6
≥
32
/
33
•
przekształcenie nierówności do postaci równania Æ wprowadzenie dodatkowej zmiennej
1
/
33
N
1
+
19
/
33
N
5
+0
N
6
–
N
7
=
32
/
33
•
do układu równań wprowadzane jest dodatkowe równanie Æ H
1
(nowa płaszczyzna)
może być ujemne
lub dodatnie
na pewno jest dodatnie
musi być dodatnie
7
Piotr Sawicki / Programowanie całkowitoliczbowe
13
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
nowy układ równań
(A
1
) Z +190
N
1
+760
N
5
= 448.400
(B
1
)
1
/
33
N
1
+
19
/
33
N
5
+
N
6
=
2045
/
33
(C
1
)
–
4
/
33
N
1
+
N
2
+
122
/
33
N
5
=
6.340
/
33
(D
1
)
+
N
3
+
N
5
= 90
(E
1
)
–
1
/
33
N
1
+
N
4
–
19
/
33
N
5
=
265
/
33
(F
1
)
S
–
N
5
= 10
(G
1
)
H
+
1
/
33
N
1
+
19
/
33
N
5
=
2.210
/
33
(H
1
)
1
/
33
N
1
+
19
/
33
N
5
–
N
7
=
32
/
33
•
mechanizm redukcji zmiennej
– poszukiwanie najmniejszego (dodatniego) współczynnika przy zmiennej w równaniu funkcji
celu Æ najmniejsze obniżenie wartości FC
– redukcja zmiennej N
1
ze wszystkich równań za wyjątkiem (H
1
)
33(H
1
)
N
1
+19
N
5
–33
N
7
= 32
– przykładowa redukcja zmiennej N
1
z równania C
1
4
/
33
(33H
1
)
4
/
33
N
1
+
76
/
33
N
5
–4
N
7
=
128
/
33
(C
1
)
–
4
/
33
N
1
+
N
2
+
122
/
33
N
5
=
6.340
/
33
(C
1
)+
4
/
33
(33H
1
)
N
2
+6
N
5
–4
N
7
= 196
Å
Å
r
r
ó
ó
wnanie g
wnanie g
ł
ł
ó
ó
wne
wne
Piotr Sawicki / Programowanie całkowitoliczbowe
14
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
ostateczny układ równań po I-szej iteracji
(A
2
) Z –2.850
N
5
+6.270
N
7
= 442.320
(B
2
)
N
6
–
N
7
= 61
(C
2
)
+
N
2
+
N
5
–4
N
7
= 196
(D
2
)
+
N
3
+
N
5
= 90
(E
2
)
+
N
4
–
N
7
= 9
(F
2
)
S
–
N
5
= 10
(G
2
)
H
+
N
7
= 66
(H
2
)
N
1
+19
N
5
–33
N
7
= 32
– nowe dopuszczalne rozwiązanie bazowe
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
, N
7
) = (442.320, 10, 66, 32, 196, 90, 0, 61, 0)
•
poszukiwanie kolejnej zmiennej niebazowej wchodzącej do bazy
– zmienna N
5
(najbardziej ujemny współczynnik w równaniu funkcji celu)
– poszukiwanie nowego równania głównego Æ równanie H
2
•
redukcja G-J zmiennej N
5
z równań, za wyjątkiem równania H
2
Æ
np. red N
5
z równ.C
2
1
/
19
(H
2
)
1
/
19
N
1
+
N
5
–
33
/
19
N
7
=
32
/
19
(C
2
)
+
N
2
+
N
5
–4
N
7
= 196
(C
2
)–
1
/
19
(H
2
)
–
1
/
19
N
1
+
N
2
–
43
/
19
N
7
=
3692
/
19
RHS/Współcz.N
5
0
196
90
0
-10
0
32
/
19
= 1,7 min
8
Piotr Sawicki / Programowanie całkowitoliczbowe
15
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
ostateczny układ równań po II-giej iteracji
(
A
3
) Z +150
N
1
+1.320
N
7
= 447.120
(B
3
)
N
6
–
N
7
= 61
(C
3
)
–
1
/
19
N
1
+
N
2
–
43
/
19
N
7
=
3692
/
19
(D
3
)
–
1
/
19
N
1
+
N
3
+
33
/
19
N
7
=
1678
/
19
(E
3
)
+
N
4
–
N
7
= 9
(F
3
)
S
+
1
/
19
N
1
–
33
/
19
N
7
=
222
/
19
(G
3
)
H
+
N
7
= 66
(H
3
)
1
/
19
N
1
+
N
5
–
33
/
19
N
7
=
32
/
19
•
analiza rozwiązania
– nowe dopuszczalne rozwiązanie bazowe
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
, N
7
) = (447.120, 11
13
/
19
, 66, 0, 194
6
/
19
, 88
6
/
19
, 9, 1
13
/
19
, 61, 0)
– zmienna decyzyjna S nie jest liczbą całkowitą
– poszukiwana jest największa wartość ułamkowa spośród wartości RHS, wśród wszystkich
równań, za wyjątkiem FC (A
3
) Æ
warto
warto
ść
ść
najbli
najbli
ż
ż
sza liczbie ca
sza liczbie ca
ł
ł
kowitej
kowitej
– arbitralny wybór równania (H
3
)
RHS
61
194
6
/
19
88
6
/
19
9
11
13
/
19
66
1
13
/
19
Å
Å
max
max
Å
Å
max
max
Piotr Sawicki / Programowanie całkowitoliczbowe
16
•
przekształcenie równania niecałkowitoliczbowego
(H
3
)
1
/
19
N
1
+
N
5
–
33
/
19
N
7
=
32
/
19
do postaci semi-całkowitoliczbowej
Æ
wartości liczbowe wyrażane są jako suma części całkowitej i nieujemnej części ułamkowej
(H
3
) (0+
1
/
19
)
N
1
+ (1+0)
N
5
+ (-2+
5
/
19
)
N
7
= (1+
13
/
19
)
•
przeniesienie wartości całkowitych na prawą stronę równań (RHS)
(H
3
)
1
/
19
N
1
+ 0
N
5
+
5
/
19
N
7
=
13
/
19
+ (1 – 0
N
1
– 1
N
5
+ 2
N
7
)
dzięki czemu można zapisać
1
/
19
N
1
+ 0
N
5
+
5
/
19
N
7
≥
13
/
19
•
przekształcenie nierówności do postaci równania Æ wprowadzenie dodatkowej zmiennej
1
/
19
N
1
+ 0
N
5
+
5
/
19
N
7
–
N
8
=
13
/
19
•
wprowadzane jest dodatkowe równanie Æ I
3
(nowa płaszczyzna)
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
może być ujemne
lub dodatnie
na pewno jest dodatnie
musi być dodatnie
9
Piotr Sawicki / Programowanie całkowitoliczbowe
17
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
nowy układ równań Æ w III-ciej iteracji
(
A
3
) Z +150
N
1
+1.320
N
7
= 447.120
(B
3
)
N
6
–
N
7
= 61
(C
3
)
–
1
/
19
N
1
+
N
2
–
43
/
19
N
7
=
3692
/
19
(D
3
)
–
1
/
19
N
1
+
N
3
+
33
/
19
N
7
=
1678
/
19
(E
3
)
+
N
4
–
N
7
= 9
(F
3
)
S
+
1
/
19
N
1
–
33
/
19
N
7
=
222
/
19
(G
3
)
H
+
N
7
= 66
(H
3
)
1
/
19
N
1
+
N
5
–
33
/
19
N
7
=
32
/
19
(I
3
)
1
/
19
N
1
+
5
/
19
N
7
–
N
8
=
13
/
19
•
mechanizm redukcji zmiennej
– poszukiwanie najmniejszego (dodatniego) współczynnika przy zmiennej w równaniu FC
– redukcja zmiennej N
1
ze wszystkich równań za wyjątkiem (I
3
)
19(I
3
)
N
1
+5
N
7
– 19
N
8
= 13
– redukcja G-J zmiennej N
1
Æ
dla przykładu redukcja G-J zmiennej N
1
z równania FC (A
3
)
150(19I
3
)
150
N
1
+750
N
7
–2.850
N
8
= 1.950
(
A
3
) Z +150
N
1
+1.320
N
7
= 447.120
A
3
–150(19I
3
) Z
+570
N
7
+2.850
N
8
= 445.170
Å
równanie główne
Piotr Sawicki / Programowanie całkowitoliczbowe
18
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
•
układ równań po redukcji G-J Æ po III-ciej iteracji
(A
4
) Z +570
N
7
+ 2.850
N
8
= 445.170
(B
4
)
+
N
6
–
N
7
= 61
(C
4
)
+
N
2
+2
N
7
–
N
8
= 195
(D
4
)
+
N
3
+ 2
N
7
–
N
8
= 89
(E
4
)
+
N
4
–
N
7
= 9
(F
4
)
S
+2
N
7
–
N
8
= 11
(G
4
)
H
+
N
7
= 66
(H
4
)
N
5
–2
N
7
+
N
8
= 1
(I
4
)
N
1
+5
N
7
–
19
N
8
= 13
•
analiza rozwiązania
– nowe dopuszczalne rozwiązanie bazowe
(Z, S, H, N
1
, N
2
, N
3
, N
4
, N
5
, N
6
, N
7
, N
8
) = (445.170, 11, 66, 13, 195, 89, 9, 1, 61, 0, 0)
– zmienne decyzyjne S i H są liczbami całkowitymi
{
S = 11
{
H = 66
10
Piotr Sawicki / Programowanie całkowitoliczbowe
19
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Analiza rozwiązania zadania
Max Z(S, H) = 2.850
S
+ 6.270
H
S
= 11
i H
= 66
Z = 445.170 Æ Z
max
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
i
(10,66); Z = 442.320
(10; 66,96); Z = 448.400
(11,66); Z = 445.170
Piotr Sawicki / Programowanie całkowitoliczbowe
20
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Porównanie rezultatu uzyskanego metodą SIMPLEX i Gomory’ego
0
--
N
8
(warunek płaszczyzny odcinającej)
0
--
N
7
(warunek płaszczyzny odcinającej)
61
61,96
N
6
(liczba wózków 45H powyżej min.)
1
0
N
5
(liczba wózków 20S powyżej min.)
9
8,04
N
4
(dostępność wózków 45H)
89
90
N
3
(dostępność wózków 20S)
195
192,12
N
2
(fundusz czasu)
13
≈0
N
1
(zasoby finansowe)
66
66,96
H
11
10
S
448.400
Metoda SIMPLEX
445.170 (–3.230)
Z
Metoda Gomory’ego
Parametr
11
Piotr Sawicki / Programowanie całkowitoliczbowe
21
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Algorytm metody Gomory’ego
•
uzyskaj wstępne rozwiązanie
– wyznacz rozwiązanie optymalne z pominięciem warunku o całkowitoliczbowym
charakterze zmiennych decyzyjnych
{
jeżeli uzyskasz rozwiązanie o charakterze całkowitoliczbowym problem został
rozwiązany
{
jeżeli przynajmniej jedna ze zmiennych, która powinna mieć charakter
całkowitoliczbowy, nie jest całkowitoliczbowa należy przeprowadzić procedurę
tworzenia płaszczyzn odcinających
•
tworzenie płaszczyzn odcinających
(1) w układzie równań wyróżnij równanie dla którego RHS charakteryzuje się największą
częścią ułamkową
(2) przekształć wyróżnione w kroku (2) równanie niecałkowitoliczbowe do postaci
nierówności semi-całkowitoliczbowej
(3) przekształć nierówność do postaci równania dodając dodatkową zmienną
(4) wprowadź nowe równanie, jako równanie dodatkowe
(5) przeprowadź redukcję G-J na nowym układzie równań
Piotr Sawicki / Programowanie całkowitoliczbowe
22
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda Gomory’ego
Algorytm metody Gomory’ego …cd
•
poszukaj rozwiązanie optymalne
(7) jeżeli w nowym układzie równań w wierszu FC pojawią się ujemne współczynniki przy
zmiennych decyzyjnych przeprowadź kolejną redukcję G-J aż do uzyskania
rozwiązania optymalnego w sensie metody SIMPLEX
(8) powtarzaj kroki (1) – (6) do chwili, w której wszystkie oczekiwane zmienne decyzyjne
będą miały charakter całkowitoliczbowe
12
Piotr Sawicki / Programowanie całkowitoliczbowe
23
Programowanie całkowitoliczbowe
Metoda rozgałęzień i ograniczeń
ang. branch-and-bound
Programowanie całkowitoliczbowe
Metoda rozgałęzień i ograniczeń
ang. branch-and-bound
Piotr Sawicki / Programowanie całkowitoliczbowe
24
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
13
Piotr Sawicki / Programowanie całkowitoliczbowe
25
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
Piotr Sawicki / Programowanie całkowitoliczbowe
26
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
14
Piotr Sawicki / Programowanie całkowitoliczbowe
27
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
Piotr Sawicki / Programowanie całkowitoliczbowe
28
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)
15
Piotr Sawicki / Programowanie całkowitoliczbowe
29
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
Piotr Sawicki / Programowanie całkowitoliczbowe
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)
16
Piotr Sawicki / Programowanie całkowitoliczbowe
31
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
Piotr Sawicki / Programowanie całkowitoliczbowe
32
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 = 66
– 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
(12; 65)
R
3
R
4
S ≤11
S ≥12
(13,42; 65)
H ≤ 65
R
5
{
R
6
17
Piotr Sawicki / Programowanie całkowitoliczbowe
33
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
(12; 65)
R
3
R
4
S ≤11
S ≥12
(13,42; 65)
H ≤ 65
R
5
R
6
S ≥14
S ≤ 13
Piotr Sawicki / Programowanie całkowitoliczbowe
34
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)
18
Piotr Sawicki / Programowanie całkowitoliczbowe
35
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
Piotr Sawicki / Programowanie całkowitoliczbowe
36
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
19
Piotr Sawicki / Programowanie całkowitoliczbowe
37
Programowanie całkowitoliczbowe
Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń
Zadanie do rozwiązania
•
sformułowanie problemu
– funkcja celu
Max Z (x
1
,x
2
) = 3x
1
+ 4x
2
– ograniczenia
5x
1
+ 3x
2
≤ 15
3x
1
+ 5x
2
≤ 15
x
1
≥ 0
x
2
≥ 0
x
1
, x
2
∈ C
•
znajdź optymalne rozwiązanie problemu z wykorzystaniem metody RiO
Piotr Sawicki / Programowanie całkowitoliczbowe
38
Programowanie całkowitoliczbowe
Podsumowanie
Porównanie metody Gomory’ego i RiO
zastosowanie w algorytmie
obliczeniowy w Solverze
MS Excel
--
praktyczne zastosowanie
duża
duża
pracochłonność
wzrasta wraz ze wzrostem
liczby płaszczyzn odcinających
metoda
Gomory’ego
nie ulega zmianie
liczba zmiennych
decyzyjnych
metoda rozgałęzień i
ograniczeń (RiO)
parametr
porównania
20
Piotr Sawicki / Programowanie całkowitoliczbowe
39
Programowanie całkowitoliczbowe
Podsumowanie
Pojęcia do zapamiętania
•
zmienna bazowa vs. niebazowa
•
redukcja G-J
•
ograniczenie płaszczyzn
odcinających
•
największa wartość ułamkowa
•
semi-całkowitoliczbowa postać
równania
•
procedura rozgałęzień i ograniczeń
Wyszukiwarka
Podobne podstrony:
Jadczak R - Badania operacyjne Wykład 3, programowanie całkowitoliczbowe
programowanie calkowitoliczbowe
Jadczak R Badania operacyjne, Wykład 3 programowanie całkowitoliczbowe
Programowanie całkowitoliczbowe metoda podziału i ograniczeń
programowanie calkowitoliczbowe
Jane Scrivner Program całkowitego oczyszczania organizmu (2004) (OCR, mało literówek)
21-25, tablice, Potrafisz już przechowywać w programie liczby całkowite, rzeczywiste, znaki i napisy
program leszka do calkowania
mazurkiewicz,badania operacyjne,Lista zadań z programowania liniowego i całkowitego
Nowy Prezentacja programu Microsoft PowerPoint 5
Charakterystyka programu
1 treści programoweid 8801 ppt
Programowanie rehabilitacji 2
więcej podobnych podstron