nechodím na prednáškyCelociselne programovanie
prednaska 2
Stiahnuť PDF · 59 kBPreber si túto poznámku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto poznámky.
Náhľad poznámky
CELOČÍSELNÉ PROGRAMOVANIE (CP)
Sú tri možnosti CP, pod
ľ
a toho, akú doménu (defini
č
ný obor) majú premenné v danej úlohe:
n – po
č
et všetkých premenných
n' – po et celo
č
íselných premenných
1. Ak n' < n , potom ide o tzv. zmiešané úlohy („mixed integer programming“)
2. Ak n' = n , potom ide o
č
isté celo
č
íselné programovanie,
3. Ak n' = n ٨ xi∈{0, 1} (i = 1, ... , n), potom ide o tzv. bivalentné programovanie
METÓDY RIEŠENIA ÚLOH CP:
A) Úplné (napr. metóda vetvenia a medzí alebo metóda se
č
ných nadrovín) – zaru
č
ujú nájdenie
optimálneho riešenia, ale v nepolynomiálnom
č
ase v závislosti od ve
ľ
kosti úlohy (tj. po
č
tu
premenných n).
B) Približné (napr. simulované žíhanie, genetické algoritmy) – tieto metódy nikdy nezaru ia
nájdenie optimálneho riešenia, ale v rozumnom
č
ase poskytnú celkom dobré („suboptimálne“)
riešenie.
METÓDA VETVENIA A MEDZÍ
1. Princíp vetvenia – množinu prípustných riešení (MPR) rozkladá na radu spravidla disjunktívnych
podmnožín.
2. Princíp odhadu medzí – ide o odhady hodnoty kriteriálnej funkcie na MPR, resp. na niektorej jej
podmnožine (tzv. horná medza a dolná medza).
POSTUP (pre prípad maximalizácie kriteriálnej funkcie):
1) Uvažujeme celú MPR ako jediného kandidáta vetvenia a stanovíme dolnú (spodnú) medzu
kriteriálnej funkcie fS = -∞ (ide o najlepšie doteraz nájdené riešenie, platí globálne) a hornú
medzu kriteriálnej funkcie fH (platí len pre danú (pod)množinu riešení) odhadneme v závislosti
od charakteru úlohy (najväčšia teoreticky možná hodnota kriteriálnej funkcie pre riešenie z
MPR).
2) Vetvenie – podľa vybraného pravidla vetvenia (napr. najvyššia hodnota fH), vyberieme
z kandidátov vetvenia jednu množinu a rozložíme ju na jednu alebo viac podmnožín prípustných
riešení.
-
Ak je súbor kandidátov prázdny, tak algoritmus končí. Pritom riešenie zodpovedajúce
aktuálnej spodnej medzi fS je optimálne. T.j.
( )x
f
f
S =
=> x je optimálne riešenie.
-
Ak fS = -∞ , potom riešenie neexistuje (MPR je prázdna).
3) Stanovenie hornej medze fH – pre každú novú podmnožinu stanovíme hornú medzu kriteriálnej
funkcie na tejto podmnožine (najlepšia teoreticky možná hodnota kriteriálnej funkcie pre
riešenia z danej podmnožiny).
4) Orezávanie – z ďalšieho skúmania vylúčime tie podmnožiny, pre ktoré fH < fS , alebo ktoré sú
prázdne.
5) Stanovenie spodnej medze fS – určíme najlepšie prípustné riešenie x pre každú novú
podmnožinu:
- Ak ( )
S
f
x
f
≥
=>
upravíme aktuálnu dolnú medzu
( )x
f
f
S =
, x je najlepšie doteraz
nájdené riešenie a opätovne sa vykoná orezávanie, pričom sa zistí či nemožno vylúčiť ďalšie
podmnožiny na základe podmienky z kroku 4).
6) Návrat do bodu 2)
Príklad: Výber zákaziek
V skúmanom období môže podnik prevziať 6 rôznych zákaziek, ktoré sa líšia spotrebou času
a materiálu. Kapacity výrobného zariadenia a zásob materiálu sú obmedzené. Úlohou je rozhodnúť,
ktoré zákazky má podnik prevziať.
( )
100
2
3
5
10
70
15
15
5
7
8
4
5
9
63
11
6
5
4
3
2
1
6
5
4
3
2
1
!
6
5
4
3
2
1
≤
+
+
+
+
+
≤
+
+
+
+
+
=
+
+
+
+
+
=
x
x
x
x
x
x
x
x
x
x
x
x
MAX
x
x
x
x
x
x
x
f
OBRÁZOK:
VÝPOČET:
1. Vetvenie
(
) 0
0
,
0
,
0
,
0
,
0
,
1
100
=
=
=
f
f
f
S
H
95
95
1
1
0
100
0
0
1
100
2
3
5
10
70
14
5
7
8
4
5
9
63
11
6
5
4
3
2
6
5
4
3
2
!
6
5
4
3
2
≤
+
+
+
+
≤
+
+
+
+
=
+
+
+
+
+
x
x
x
x
x
x
x
x
x
x
MAX
x
x
x
x
x
0
11
12
1
2
3
5
7
9
4
6
10
8
13
14
15
16
1
0
1
1
0
0
1
0
1
0
1
0
x1
x2
x3
x4
x5
x6
x5
x6
fH =100
100
100
100
89
37
91
96
88
91
95
87
(
) 0
0
,
0
,
0
,
0
,
0
,
0
89
=
=
=
f
f
f
S
H
2. Vetvenie (Rozhodli sme sa pre lebo dáva nádej na väčší zisk.)
- Vychádzajú z
(
) 74
0
,
0
,
0
,
0
,
1
,
1
100
=
=
=
f
f
f
S
H
(
) 11
0
,
0
,
0
,
0
,
0
,
1
37
=
=
=
f
f
f
S
H
3. Vetvenie
- Vychádzajú z
(
) 83
0
,
0
,
0
,
1
,
1
,
1
100
=
=
=
f
f
f
S
H
(
) 74
0
,
0
,
0
,
0
,
1
,
1
91
=
=
=
f
f
f
S
H
4. Vetvenie
- Vychádzajú z
(
) 88
0
,
0
,
1
,
1
,
1
,
1
100
=
=
=
f
f
f
S
H
(
) 83
0
,
0
,
0
,
1
,
1
,
1
95
=
=
=
f
f
f
S
H
1
3
5
1
2
100
2
3
5
10
70
15
5
7
8
4
5
9
63
6
5
4
3
2
6
5
4
3
2
!
6
5
4
3
2
≤
+
+
+
+
≤
+
+
+
+
=
+
+
+
+
x
x
x
x
x
x
x
x
x
x
MAX
x
x
x
x
x
3
4
15
2
3
5
10
7
5
8
4
5
9
74
6
5
4
3
6
5
4
3
!
6
5
4
3
≤
+
+
+
≤
+
+
+
=
+
+
+
+
x
x
x
x
x
x
x
x
MAX
x
x
x
x
85
2
3
5
10
14
5
8
4
5
9
11
6
5
4
3
6
5
4
3
!
6
5
4
3
≤
+
+
+
≤
+
+
+
=
+
+
+
+
x
x
x
x
x
x
x
x
MAX
x
x
x
x
5
6
100
2
3
5
15
5
8
4
5
83
6
5
4
6
5
4
!
6
5
4
≤
+
+
≤
+
+
=
+
+
+
x
x
x
x
x
x
MAX
x
x
x
15
2
3
5
7
5
8
4
5
74
6
5
4
6
5
4
!
6
5
4
≤
+
+
≤
+
+
=
+
+
+
x
x
x
x
x
x
MAX
x
x
x
7
8
0
2
3
5
5
8
4
88
6
5
6
5
!
6
5
≤
+
≤
+
=
+
+
x
x
x
x
MAX
x
x
5
2
3
6
5
8
4
83
6
5
6
5
!
6
5
≤
+
≤
+
=
+
+
x
x
x
x
MAX
x
x
5. Vetvenie
- Vychádzajú zo
(
) 92
0
,
1
,
1
,
1
,
1
,
1
100
=
=
=
f
f
f
S
H
(
) 88
0
,
0
,
1
,
1
,
1
,
1
96
=
=
=
f
f
f
S
H
6. Vetvenie
- Vychádzajú z
=> nespĺňa
(
) 88
0
,
0
,
1
,
1
,
1
,
1
88
=
=
=
f
f
f
S
H
7. Vetvenie
- Vychádzajú z
(
) 87
0
,
1
,
0
,
1
,
1
,
1
95
=
=
=
f
f
f
S
H
(
) 83
0
,
0
,
0
,
1
,
1
,
1
1
9
=
=
=
f
f
f
S
H
8. Vetvenie
- Vychádzajú z
(
) 95
1
,
1
,
0
,
1
,
1
,
1
=
= f
f
S
(
) 87
0
,
1
,
0
,
1
,
1
,
1
=
= f
f
S
7
10
8
13
9
10
3
2
4
5
8
92
6
6
!
6
−
≤
≤
=
+
x
x
MAX
x
0
2
5
5
8
88
6
6
!
6
≤
≤
=
+
x
x
MAX
x
11
12
( )
0
2
5
5
96
≤
≤
=
x
f
( )
0
0
5
0
88
≤
≤
=
x
f
13
14
2
2
5
5
8
87
6
6
!
6
≤
≤
=
+
x
x
MAX
x
5
2
6
5
8
83
6
6
!
6
≤
≤
=
+
x
x
MAX
x
15
16
( )
0
0
0
0
95
≤
≤
=
x
f
( )
2
0
5
0
87
≤
≤
=
x
f
Automaticky vygenerovaný textový náhľad. Pre plné formátovanie si stiahnite súbor.