Programowanie
całkowitoliczbowe
Wykład nr 5
RozwiÄ…zanie PCL za pomocÄ… LP
Zadanie programowania liniowego, w którym
zmienne decyzyjne muszą przyjmować wartości
całkowite nazywamy zadaniem programowania
liniowego całkowitoliczbowego (krótko PCL)
Jeśli n1 = n, zagadnienie nazywamy czystym zagadnieniem programowania liniowego
(PCL) natomiast, gdy n1 < n zagadnienie nazywamy mieszanym lub (MCL, ang. MILP)
Przykład. Zagadnienie plecakowe
W magazynie znajduje się 7 paczek, z których każda
paczka ma określoną wagę i wartość:
Samochód ma ładowność 15 (czyli może zabrać ładunek
o łącznej wadze nie większej niż 15). Które paczki ma
zabrać aby zmaksymalizować wartość ładunku?
Zapis modelu
Aby znalez
ć rozwiązanie przy pomocy przeglądu zupełnego przestrzeni
rozwiązań dopuszczalnych należy wygenerować i sprawdzić 2n rozwiązań.
Zakładając, że jedno rozwiązanie wymaga 10-6 s, czas obliczeń dla n = 7
wyniesie ok. 0,0001 s, dla n = 50 ok. 35 lat, a dla n = 60 ok. 36 558 lat!
Dla ogólnego zadania PCL nie jest znany efektywny algorytm (wszystkie
algorytmy mogą działać bardzo długo dla pewnych niedużych problemów)
Dodatkowe warunki logiczne
spotykane w modelowaniu PCL
Należy zabrać paczkę 2 lub 5, czyli: x2 = 1 v x5 = 1
Nie wolno przewozić razem paczek 1 i 6, czyli:
~ (x1 = 1 ^ x6 = 1) <=> (x1 = 0 v x6 = 0)
Jeżeli zabieramy paczkę 3 to musimy zabrać
również paczkę 4, czyli: x3 = 1 => x4 = 1
W urzÄ…dzeniach energetycznych
Minimum techniczne: P >= Pmin·x
Maksimum techniczne: P <= Pmax·x
Koszt poczÄ…tkowy: K = K0·x + K1·P
Relaksacja zagadnienia PCL
Zadanie PL otrzymane z PLC przez usunięcie warunków
całkowitoliczbowości nazywamy relaksacją PCL:
Zachodzi zawsze warunek z*R >= z*, czyli relaksacja PCL
określa górne ograniczenie na wartość funkcji celu PCL.
Relaksację można efektywnie rozwiązać np. algorytmem
sympleks. Na relaksacji opiera się algorytm podziału i
ograniczeń (ang. Branch&Bound)
Metody programowania całkowitoliczboweg
Wyróżnia się trzy podejścia do rozwiązywania zagadnień
programowania całkowitoliczbowego
metody podziału i ograniczeń,
metody płaszczyzn odcinających,
metody oparte na teorii grup.
Programowanie całkowitoliczbowe PLC  p. 1/17
RozwiÄ…zanie PCL za pomocÄ… LP
Przykład 1
z"= max z = 5x1 + 8x2
x1 + x2 d" 6
5x1 + 9x2 d" 45
x1, x2 e" 0 i całkowite
Programowanie całkowitoliczbowe PLC  p. 2/17
RozwiÄ…zanie PCL za pomocÄ… LP
x2
x1 + x2 = 6
6
5
Optymalne rozwiązanie ciągłe
4
z = 5x1 + 8x2 = 41.25
3
L0
5x1 + 9x2 = 45
2
1
x1
1 2 3 4 5 6 7 8 9
Programowanie całkowitoliczbowe PLC  p. 3/17
RozwiÄ…zanie PCL za pomocÄ… LP
RozwiÄ…zanie RozwiÄ…zanie RozwiÄ…zanie RozwiÄ…zanie
optymalne zaokrąglone najbliższe optymalne
ciągłe całkowite całkowite
9
x1 = 2.25 2 2 0
4
15
x2 = 3.75 4 3 5
4
z 41.25 niedopuszcz. 34 40
Programowanie całkowitoliczbowe PLC  p. 4/17
Metoda podziału i ograniczeń dla PCL
Kluczowe fakty
PCL= LP + ogranicznia całkowitoliczbowości
Fakt 1. Wartość optymalna funkcji celu LP jest górnym ograniczeniem
(maksymalizacja funkcji celu) optymalnej wartości funkcji celu PCL.
Fakt 2. Wartość funkcji celu PCL dla dowolnego rozwiązania
całkowitoliczbowego jest dolnym ograniczeniem (maksymalizacja funkcji
celu) optymalnej wartości funkcji celu PCL.
Programowanie całkowitoliczbowe PLC  p. 5/17
RozwiÄ…zanie PCL za pomocÄ… LP
Pomijamy warunki całkowitoliczbowości i rozwiązujemy
następujące zagadnienie LP
z"= max z = 5x1 + 8x2
Å„Å‚
ôÅ‚
x1 + x2 d" 6
òÅ‚
L0 =
5x1 + 9x2 d" 45
ôÅ‚
ół
x1, x2 e" 0
Otrzymujemy: x1 = 21, x2 = 33, z0 = 411 oraz górne
4 4 4
ograniczenie
1
z"d" 41 .
4
Ponieważ współczynniki funkcji celu są całkowitoliczbowe,
możemy poprawić górne ograniczenie
z"d" 41.
Programowanie całkowitoliczbowe PLC  p. 6/17
Metoda podziału i ograniczeń dla PCL
Wybieramy zmienną decyzyjną o wartości ułamkowej np. x2
 wybór jest heurystyczny (możemy wybrać również x1).
Narzucamy warunki, x2 d" 3 lub x2 e" 4, wykluczajÄ…ce
przedział (3, 4).
x2
6
5
Optymalne rozwiązanie ciągłe
L1
4
3
2
L2
1
x1
1 2 3 4 5 6 7 8 9
Programowanie całkowitoliczbowe PLC  p. 7/17
Metoda podziału i ograniczeń dla PCL
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L1 L2
max z = 5x1 + 8x2 max z = 5x1 + 8x2
Å„Å‚ Å„Å‚
x1 + x2 d" 6 x1 + x2 d" 6
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
òÅ‚ òÅ‚
5x1 + 9x2 d" 45 5x1 + 9x2 d" 45
L1 = L2 =
ôÅ‚ ôÅ‚
x2 e" 4 x2 d" 3
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ół ół
x1, x2 e" 0 x1, x2 e" 0
Wybór węzła L1 czy L2 jest heurystyczny. Rozpatrzmy L1.
Otrzymujemy: x1 = 1.8, x2 = 4, z = 41.
Programowanie całkowitoliczbowe PLC  p. 8/17
Metoda podziału i ograniczeń dla PCL
Wybieramy zmienną decyzyjną o wartości ułamkowej x1
Narzucamy warunki, x1 d" 1 lub x1 e" 2, wykluczajÄ…ce
przedział (1, 2).
x2
6
5
Optymalne rozwiązanie ciągłe
L4
4
3
2
L2
1
x1
1 2 3 4 5 6 7 8 9
Programowanie całkowitoliczbowe PLC  p. 9/17
Metoda podziału i ograniczeń dla PCL
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L1 L2
x1 = 1.8 x2 = 4 z = 41
x1 d" 1
x1 e" 2
L3 L4
Zadanie sprzeczne
max z = 5x1 + 8x2 max z = 5x1 + 8x2
Å„Å‚ Å„Å‚
ôÅ‚ x1 + x2 d" 6 ôÅ‚ x1 + x2 d" 6
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
5x1 + 9x2 d" 45 5x1 + 9x2 d" 45
ôÅ‚ ôÅ‚
òÅ‚ òÅ‚
L3 = L4 =
x2 e" 4 x2 e" 4
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
x1 e" 2 x1 d" 1
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ół ół
x1, x2 e" 0 x1, x2 e" 0
4 5
sprzeczne x1 = 1, x2 = 4 , z = 40
9 9
Programowanie całkowitoliczbowe PLC  p. 10/17
Metoda podziału i ograniczeń dla PCL
Wybieramy zmienną decyzyjną o wartości ułamkowej x2
Narzucamy warunki, x2 d" 4 lub x2 e" 5, wykluczajÄ…ce
przedział (4, 5).
x2
6
L6
5
Optymalne rozwiązanie ciągłe
L4
4
L5
3
2
L2
1
x1
1 2 3 4 5 6 7 8 9
Rozpatrujemy L5.
Programowanie całkowitoliczbowe PLC  p. 11/17
Metoda podziału i ograniczeń dla PCL
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L1 L2
x1 = 1.8 x2 = 4 z = 41
x1 d" 1
x1 e" 2
L3 L4
Zadanie sprzeczne x1 = 1 x2 = 44 z = 405
9 9
x2 d" 4 x2 e" 5
co najwyzej 10% od optimum!
Dolne ograniczenie
L5 L6
z"e" 37
x1 = 1 x2 = 4 z = 37
Programowanie całkowitoliczbowe PLC  p. 12/17
Metoda podziału i ograniczeń dla PCL
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L1 L2
x1 = 1.8 x2 = 4 z = 41
x1 d" 1
x1 e" 2
L3 L4
Zadanie sprzeczne x1 = 1 x2 = 44 z = 405
9 9
x2 d" 4 x2 e" 5
co najwyzej 2.5% od optimum!
dolne ograniczenie
L5 L6
z"e" 37 z"e" 40
x1 = 1 x2 = 4 z = 37 x1 = 0 x2 = 5 z = 40
Programowanie całkowitoliczbowe PLC  p. 13/17
Metoda podziału i ograniczeń dla PCL
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L2
L1
x1 = 3 x2 = 3 z = 39
x1 = 1.8 x2 = 4 z = 41
x1=<1
x1>=2
L3 L4
Zadanie sprzeczne x1 = 1 x2=4 4/9 z=40 5/9
x2 d" 4 x2 e" 5
optimum!
L5 L6
z>=37 z>=40
x1 = 1 x2 = 4 z = 37 x1 = 0 x2 = 5 z = 40
Programowanie całkowitoliczbowe PLC  p. 14/17
Metoda podziału i ograniczeń dla PCL
x2
6
Optymalne rozwiązanie całkowitoliczbowe
L6
5
Optymalne rozwiązanie ciągłe
L4
4
L5
3
2
L2
1
x1
1 2 3 4 5 6 7 8 9
Programowanie całkowitoliczbowe PLC  p. 15/17
Czy można poprawić górne ograniczenie?
L0
z"d" 41
x1 = 2.25 x2 = 3.75 z = 41.25
x2 e" 4 x2 d" 3
L2
L1
x1 = 3 x2 = 3 z = 39
x1 = 1.8 x2 = 4 z = 41
x1 d" 1
x1 e" 2
L3 L4
Zadanie sprzeczne x1 = 1 x2 = 44 z = 405
9 9
Załóżmy, że w naszym przykładzie rozpatrujemy węzeł L2 przed L5 lub L6. Optymalne
5
rozwiązanie leży w L2 lub L4. Stąd z"jest ograniczone przez 40 . Ponieważ współczynniki
9
funkcji celu są całkowitoliczbowe, możemy poprawić górne ograniczenie na 40.
Programowanie całkowitoliczbowe PLC  p. 16/17
Podsumowanie
Załóżmy rozpatrzyliśmy węzeł Lj. Nie ma sensu dzielić Lj
(rozgałęziać) jeśli:
LP w Lj jest sprzeczne,
optymalne rozwiązanie LP jest całkowitoliczbowe,
wartość funkcji celu LP w Lj jest nie większa niż
aktualne dolne ograniczenie.
Uwagi
Relaksacje LP rozwiÄ…zuje siÄ™ efektywnie,
Nie ma ogólnej metody wyboru zmiennej decyzyjne.
Nie ma ogólnej metody wyboru węzła po rozgałęzieniu.
Programowanie całkowitoliczbowe PLC  p. 17/17
Ćwiczenie
Rozwiązać podany przykład przy pomocy
algorytmu podziału i ograniczeń, rozpoczynając
drzewo binarne od zmiennej decyzyjnej x2