Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Programowanie liniowe całkowitoliczbowe
PCL
Metodologia podziału i oszacowań – Branch and Bound Technique
(B&B)
Z
x
∈
≥
=
=
x
0,
x
b,
x
A
x,
c
T
max
0
• Podstawą metodologii B&B jest przegląd drzewa rozwiązań.
• Wykorzystuje się fakt skończoności zbioru moŜliwych wartości
zmiennych całkowitoliczbowych w przypadku ograniczonych
zadań PCL.
• Etapy metody: -podział
-gałęzienie
-obliczanie górnych i dolnych oszacowań
funkcji celu.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Metodologia podziału i oszacowań – B&B
iczbowy},
calkowitol
i
0
,
{
≥
=
=
x
b
x
A
x
S
j
j
j
}
0
,
{
T
j
≥
=
=
x
b
x
A
x
j
j
Osłabienie, które prowadzi do zadania PL:
j
j
S
T ⊇
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Metodologia podziału i oszacowań – B&B
Podział.
Przyjmijmy, Ŝe zadanie PL zostało rozwiązane dla
wierzchołka v
j ,
przy czym x (j) ma nie wszystkie składowe
całkowitoliczbowe. Przykładowo niech pewna zmienna
Podział S
j
, który jest przy tym rozbiciem zbioru, jest następujący:
Gdzie <a> jest najmniejszą liczbą całkowitą większą lub równą a, [a]
zaś oznacza największą liczbę całkowitą mniejszą lub równą a.
}},
{
},
]
[
{
{
.
1
0
,
]
[
0
0
*
0
0
0
>
≥<
∩
≤
∩
=
<
<
+
=
i
Bi
j
i
Bi
j
j
i
i
i
Bi
y
x
x
S
y
x
x
S
S
f
f
y
x
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Metodologia podziału i oszacowań – B&B
Skończoność. ZałóŜmy, Ŝe kaŜda ze zmiennych x
j
jest
ograniczona i jej granica górna wynosi u
j
. Niech
Zadanie PL jest poŜądanym osłabieniem zadania PCL, gdyŜ
dołączone ograniczenia dają górną i dolną granicę dla
poszczególnych zmiennych.
Zagadnienia PL przy załoŜeniu ograniczoności zmiennych
rozwiązuje się algorytmem dualnym sympleks.
}.
,...,
1
,
0
{
},
,...,
1
,
0
,
{
n
j
x
u
x
x
H
n
j
u
x
b
Ax
x
S
j
j
k
j
j
k
j
k
j
k
j
j
k
j
k
=
≤
≤
≤
≤
=
=
≤
≤
≤
≤
=
=
β
α
β
α
całkowite
całkowite
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Drzewo rozwiązań
0
0
1
1
2
2
3
3
4
4
5
5
6
6
17
15
−
=
−
=
z
z
4
2
≥
x
3
2
≤
x
0
1
≤
x
0
1
≤
x
1
1
≥
x
1
1
≥
x
15
−
=
z
15
−
=
z
17
−
=
z
18
−
=
z
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przykład zadania PCL
0
,
,
5
3
8
3
2
3
2
1
5
3
2
1
4
3
2
1
≥
=
−
+
+
=
−
+
+
x
x
x
x
x
x
x
x
x
x
x
3
2
1
0
4
3
7
max
x
x
x
x
−
−
−
=
2
1
5
2
1
1
3
5
3
1
2
15
4
2
0
5
3
1
−
−
−
−
−
−
−
x
x
x
x
x
x
2
.
0
2
.
0
4
.
0
4
.
0
6
.
0
6
.
1
2
.
0
8
.
3
4
.
0
6
.
0
2
.
2
2
.
14
1
2
0
5
3
1
−
−
−
−
−
−
−
x
x
x
x
x
x
Rozwiązanie PL
Rozwiązanie PCL
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przegląd pośredni
metodologia podziału i oszacowań dla wektora binarnego
śą
śą
danie binarno
danie binarno
ś
ś
ci wektora x nie jest ograniczeniem
ci wektora x nie jest ograniczeniem
zadania gdy jest znana sko
zadania gdy jest znana sko
ń
ń
czona g
czona g
ó
ó
rna granica
rna granica
u
u
j
j
dla
dla
sk
sk
ł
ł
adowej
adowej
x
x
j
j
{
}
pj
j
j
j
j
j
j
s
s
S
x
u
x
i
Z
x
dla
,...,
0
1
=
∈
≤
≤
∈
Jest ono równowaŜne układowi ograniczeń:
j
o
kaŜ
dla
p
k
j
o
kaŜ
dla
s
x
kj
p
k
kj
p
k
kj
kj
j
deg
,...,
2
,
1
,
1
lub
0
deg
1
1
1
=
=
=
=
∑
∑
=
=
δ
δ
δ
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przegląd pośredni
metodologia podziału i oszacowań dla wektora binarnego
Etapy metody:
podział – wybór pewnej zmiennej x
j
i przyjęcie
{
}
{
}
{
}
1
,
,
0
,
*
=
∩
=
∩
=
j
k
j
k
k
x
S
x
S
S
x
x
oraz
{
}
{
}
{
}
k
k
j
k
k
j
k
k
W
j
j
F
x
i
W
j
j
S
x
i
W
j
j
S
∉
=
=
∈
=
=
∈
=
−
+
,
0
,
1
,
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Podział pośredni
oszacowania – wierzchołkowi v
k
przyporządkowany jest problem:
,
max
∑
∑
∈
∈
+
+
=
k
k
F
j
S
j
j
j
j
k
c
x
c
z
,
,...,
1
,
m
i
s
a
b
x
a
k
k
F
j
S
j
i
ij
i
j
ij
=
=
−
≤
∑
∑
∈
∈
+
.
,
1
lub
0
k
j
F
j
x
∈
=
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Programowanie liniowe całkowitoliczbowe
metodologia odcięć
ZałóŜmy, Ŝe istnieją
oraz
takie, Ŝe:
Z}.
x
i
0
,
{
,
max x
0
∈
≥
=
=
∈
=
x
b
Ax
x
S
x
x
c
T
b
A
}
0
,
,
{
≥
=
=
=
x
b
x
A
b
Ax
x
T
oraz zadanie osłabione w stosunku do zadania (1):
ma całkowitoliczbowe rozwiązanie optymalne x
opt
.
Wówczas
x
opt
jest rozwiązaniem optymalnym zadania (1).
T
S ⊆
T
x
x
c
T
∈
=
,
max x
0
(1)
(1)
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Metoda odcięć
ZałóŜmy, Ŝe mamy reprezentację problemu (2) w postaci
}.
0
,
{
,
max x
0
≥
=
=
∈
=
x
b
Ax
x
Q
x
x
c
T
∑
∈
=
−
=
R
j
j
ij
i
B
m
i
x
y
y
x
i
,
,...,
1
,
0
,
0
∑
∈
−
≥
−
R
j
i
i
j
ij
ij
hy
y
h
x
hy
y
h
]
[
]
[
])
[
]
([
0
0
Podstawowe odci
Podstawowe odci
ę
ę
cie
cie
(2)
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Odcięcia w metodzie form całkowitych
]
[
]
[
a
),
]
[
]
([
)
(
.
0
,
,
]
[
.
]
[
])
[
(
0
0
0
0
0
0
0
∑
∑
∑
∑
∑
∑
∈
∈
∈
∈
∈
∈
−
−
+
+
−
−
=
≥
+
−
=
≥
+
=
−
≥
−
R
j
j
ij
i
R
j
R
j
j
ij
i
j
ij
i
Bi
R
j
j
ij
i
R
j
i
j
ij
ij
ij
ij
R
j
i
i
j
ij
ij
x
y
y
x
y
y
x
f
f
x
s
x
f
f
s
f
x
f
f
y
y
y
y
x
y
y
s musi być liczbą całkowitą:
jest ca
jest ca
ł
ł
kowite.
kowite.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Heurystyczne reguły wyboru wiersza źródłowego
NaleŜy zbudować odcięcie usuwające największy moŜliwy
obszar nie zawierający punktów całkowitoliczbowych.
↑
↓
0
i
ij
f
a
f
PoŜądane jest aby f
i0
było moŜliwie duŜe a
f
ij
było moŜliwie małe dla j
∈
∈
∈
∈R
Odcięcie staje się „głębsze”, jeśli
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Reguły wyboru wiersza w metodzie form całkowitych
0
0
max
i
i
r
f
f
=
∑
∑
∈
∈
=
R
j
ij
i
i
R
j
rj
r
f
f
f
f
0
0
max
ik
i
i
rk
r
f
f
f
f
0
0
max
=
Dla określonego
R
k ∈
( I )
( II )
( III )
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Badanie całkowitoliczbowości rozwiązania PCL
W obliczeniach komputerowych liczba rzeczywista r jest
traktowana jako liczba całkowita, jeśli
ε
≤
−
}
,
1
{
min
r
r
f
f
I na odwrót – błędne stwierdzenie całkowitoliczbowości moŜe
spowodować niepoprawne zakończenie obliczeń.
Nierozpoznanie całkowitoliczbowości moŜe powodować:
wykonanie niepotrzebnych iteracji,
dołączenie niepoprawnych odcięć
utratę rozwiązania optymalnego.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Optymalne rozwiązanie zadania PCL
Rozwiązanie dopuszczalne x zadania PCL jest jego
rozwiązaniem optymalnym, gdy są spełnione trzy
warunki:
(i) prymarna dopuszczalność,
(ii) całkowitoliczbowość,
całkowite,
(iii) dualna dopuszczalność,
dla wszystkich
;
,...,
1
,
0
0
m
i
y
i
=
≥
m;
1,...,
i
0
=
i
y
R
j
y
j
∈
≥
0
0
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przegląd algorytmów metodologii odcięć
1.
Metoda form całkowitych- nie spełniony warunek
całkowitoliczbowości y
i0
dla i=1,...,m
m
i
dla
y
i
,...,
1
0
0
=
≥
3.
3. Całkowitoliczbowy algorytm prymalny – nie spełniony
warunek dualnej dopuszczalności:
R
∈
∀
≥
j
dla
y
j
0
0
2. Całkowitoliczbowy algorytm dualny – nie spełniony
warunek prymalnej dopuszczalności:
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Algorytm odcięć dla zadania PCL
Krok 1
Znajdź rozwiązanie spełniające dwa spośród trzech
wymienionych warunków. Idź do Kroku 2.
Krok 2
- Test na optymalność
Jeśli trzeci warunek jest spełniony – Stop. W
przeciwnym wypadku idź do Kroku 3.
Krok 3
- Odcinanie i eliminacja
Dodaj odcięcie z odpowiednio dobraną wartością h.
Dokonaj eliminacji – aby zachować dwa wybrane warunki.
MoŜe zaistnieć konieczność wykonania większej liczby
kroków eliminacji. Wróć do Kroku 2.