Metoda podziału i ogranicze ´n

Literatura

[1] E. M. Reingold, J. Nievergelt, N. Deo Algorytmy

kombinatoryczne PWN, 1985.

[2] R.S. Garfinkel, G.L. Nemhauser Programowanie

całkowitoliczbowe PWN, 1978.

[3] M.M. Sysło, M. Deo, J.S. Kowalik Algorytmy

optymalizacji dyskretnej z programami w j ˛ezyku
PASCAL PWN, 1993.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 1/7

Metoda podziału i ogranicze ´n

Zagadnienie plecakowe ZP

Sformułomanie zagadnienie w postaci

PLC

c

1

x

1

+ · · · + c

n

x

n

→ max

przy ograniczeniach:

a

1

x

1

+ · · · + a

n

x

n

≤ b,

x

i

∈ {0, 1}

dla

i

= 1, . . . , n.

Rozwi ˛

azanie nast ˛epuj ˛

acego problemu

LP

dostarcza nam

górnego ograniczenia

warto´sci funkcji celu w

ZP

.

c

1

x

1

+ · · · + c

n

x

n

→ max

przy ograniczeniach:

a

1

x

1

+ · · · + a

n

x

n

≤ b,

0 ≤ x

i

≤ 1

dla

i

= 1, . . . , n.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 2/7

Metoda podziału i ogranicze ´n

Jak efektywnie rozwi ˛

aza ´

n problem LP?

Uporz ˛

adkuj przedmioty w

nierosn ˛

acym

porz ˛

adku

wzgl ˛edem stosunków

c

i

a

i

,

c

1

a

1

≥ · · · ≥

c

n

a

n

.

Włó˙z do plecaka przedmiot o najwi ˛ekszym stosunku.
(najbardziej atrakcyjny).
Powtarzaj proces dopóki plecak nie jest pełny.

Otrzymujemy rozwi ˛

azanie

x

1

= · · · = x

r

= 1, x

r+1

= · · · = x

n

= 0,

dla którego

a

1

x

1

+ · · · + a

r

x

r

≤ b

i

a

1

x

1

+ · · · + a

r+1

x

r+1

> b.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 3/7

Metoda podziału i ogranicze ´n

x

∗

1

= · · · = x

∗

r

= 1, x

∗

r+1

=

1

a

r+1

(b−a

1

−· · ·−a

r

), x

∗

r+2

= · · · = x

∗

n

= 0,

jest rozwi ˛

azanie optymalnym problem

LP

c

1

x

1

+ · · · + c

n

x

n

→ max

a

1

x

1

+ · · · + a

n

x

n

≤ b,

0 ≤ x

i

≤ 1

dla

i

= 1, . . . , n.

Jest oczywiste, ˙ze

x

x

x

∗

jest rozwi ˛

azaniem dopuszczalnym.

Aby pokaza´c

x

x

x

∗

jest rozwi ˛

azaniem optymalnym, wystarczy

wyznaczy´c rozwi ˛

azanie dualne

y

y

y

∗

, dla którego

c

1

x

∗

1

+ · · · + c

n

x

∗

n

= b

1

y

∗

1

+ y

∗

2

+ · · · + y

∗

n+1

.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 4/7

Metoda podziału i ogranicze ´n

Model dualny jest postaci

b

1

y

1

+ y

2

+ · · · + y

n+1

→ min

a

1

y

1

+ y

2

≥ c

1

..

.

a

n

y

1

+ y

n+1

≥ c

n

y

1

, . . . , y

n+1

≥ 0.

Rozwi ˛

azanie

y

∗

1

=

c

r

+1

a

r

+1

, y

∗

k

= c

k−1

− a

k−1

c

r

+1

a

r

+1

k

= 2, . . . , r + 1,

y

∗

k

= 0 k = r + 2, . . . , n + 1

jest dopuszczalne przy zało˙zeniu

c

1

a

1

≥ · · · ≥

c

n

a

n

i spełnia

c

1

x

∗

1

+ · · · + c

n

x

∗

n

= b

1

y

∗

1

+ y

∗

2

+ · · · + y

∗

n+1

.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 5/7

Metoda podziału i ogranicze ´n

Przykład 2

5x

1

+ 3x

2

+ 6x

3

+ 6x

4

+ 2x

5

→ max

przy ograniczeniach:

5x

1

+ 2x

2

+ 7x

3

+ 6x

4

+ 2x

5

≤ 15,

x

i

∈ {0, 1}

dla

i

= 1, . . . , 5.

ranking

przedmiot

c

i

/a

i

(1=najlepszy, 5=najgorszy)

1

1

1

2

0.75

5

3

0.86

4

4

1

1

5

1

1

Wkładamy do plecaka przedmioty

1, 4, 5

. Je˙zeli doło˙zymy

3

,

to nast ˛

api przepełnienie. Zatem

x

1

= 1

, x

2

= 0,

x

3

=

2
7

,

x

4

= 1

,

x

5

= 1

,

z

= 14

5
7

.

Metoda oszacowa ´n i podziału dla zagadnienia plecakowego – p. 6/7

M

et

o

d

a

p

o

d

zi

a

łu

i

o

g

ra

n

ic

ze

´n

sprzeczne

x

3

=

x

4

=

1

x

1

=

2

5

z

=

1

4

z

=

1

4

z

=

1

4

z

=

1

4

x

1

=

x

4

=

x

2

=

1

z

=

1

3

x

3

=

x

4

=

x

5

=

1

x

1

=

x

3

=

1

x

4

=

1

2

x

1

=

x

3

=

x

5

=

1

x

2

=

1

4

z

=

1

3

3

4

x

1

=

1

x

1

=

0

x

2

=

1

x

2

=

0

x

3

=

1

x

3

=

0

x

4

=

1

x

4

=

0

o

p

ti

m

u

m

o

p

ti

m

u

m

x

1

=

x

4

=

x

5

=

1

x

1

=

x

4

=

x

5

=

1

x

1

=

x

4

=

x

5

=

1

x

3

=

2

7

z

=

1

4

5

7

x

2

=

1

2

z

=

1

4

1

2

M

e

to

d

a

o

s

z

a

c

o

w

a

´n

i

p

o

d

z

ia

łu

d

la

z

a

g

a

d

n

ie

n

ia

p

le

c

a

k

o

w

e

g

o

–

p

.

7

/7