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.