Ulohy s ohraniceniami

1

Úlohy s ohrani

lohy s ohra

eniami

enia

OBSAH PREDNÁŠKY

Hlavné aplika né oblasti

Základné definície

Metódy riešenia

Logické programovanie ohrani ení

Jazyk ECLiPSe

Hlavn

Hla

é aplika

apl

né oblasti

obla

Rozvrhovanie

–

asové

výrobné,

zá až procesorov,

rozvrh hodín a pod.

–

priestorové (rozmiest ovanie skladov, pobo iek, strojov ...)

Plánovanie

Rôzne optimaliza né úlohy

–

investi ný,

–

distribu ný,

–

dopravný a pod.

Konfigura ný návrh

2

Rozvrhovanie a logistika (Úlohy s ohrani eniami)

Ján Parali (www.tuke.sk/paralicj)

Základn

kla

é defin

de

ície

Úloha s ohrani eniami (CSP) je vo všeobecnosti
definovaná pomocou 3 množín:

–

Množina premenných V = {V

1, V2, …, Vn}

–

Množina domén D = {D

1, D2, …, Dn}

–

Množina ohrani ení C = {C1, …, Cn, C1,2, …, Cn-1,n , …, C1,2,…,n}

Domény môžu by :

–

Kone né (boolovské, ohrani

ené celo íselné, vymenované)

–

Nekone né (neohrani

ené celo íselné, racionálne, reálne)

Ohrani

enia môžu by :

–

Unárne (Ci), binárne (Ci,j), …, n-árne (C1,2,…,n)

–

Pozitívne alebo negatívne definované

3

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Ohrani

enia definované vymenovaním

povolených (zakázaných) kombinácií
hodnôt, napr. C1,2 = {(sym0,sym2),
(sym0,sym3), (sym1,sym0), …}

Ohrani

enia definované predpisom

–

Napr. nerovnos

pre celo íselné

premenné C1,2: V

2 > 0.5V1 + 0.75

Defin

De

ície ohrani

cie ohra

ení

–

alebo rovnos

pre reálne

premenné C1,2: V

2 = 0.25V1 + 1

4

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Grafick

Graf

á reprezent

repreze ácia

c

úloh s ohrani

loh s ohra

eniami

enia

Sie

ohrani ení

a)

Neorientovaný graf s dvoma typmi
uzlov (pre premenné a pre
ohrani enia), hrany sú možné len
medzi uzlami rôznych typov

c)

Jednoduchšie znázornenie pre
binárne CSP

b)

Hypergraf s jedným typom uzlov
(premenné) a hyperhranami
(ohrani enia)

5

Rozvrhovanie a logistika (Úlohy s ohrani eniami)

Ján Parali (www.tuke.sk/paralicj)

o znamen

o znam

á rieši úlohu

loh

s ohrani

s ohra

eniami

enia

?

Priestor preh

adávania P je definovaný ako kartézsky

sú in domén všetkých premenných, t.j. D

1 x D2 x … x Dn

Rieši

úlohu s ohrani eniami znamená jednu

z nasledujúcich úloh:

–

Dokáza existenciu alebo neexistenciu riešenia

–

Zisti po et riešení

–

Nájs jedno riešenie

–

Nájs všetky riešenia

Ak je definovaná funkcia nákladov f

c(P)->

nad P,

potom je možné rieši

aj optimaliza nú verziu CSP, t.j.

–

Nájs

optimálne riešenie (ktoré minimalizuje f

c)

6

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

2

Príklad

kla 1. (dopl

do

ova

o

ka)

Nasledovné slová sú k dispozícii pre
vloženie do danej dopl

ova ky:

–

6 písmen: žirafa, európa

–

5 písmen: puška, kurín

–

4 písmen: auto, íver

–

3 písmen: pór, eso

Transformácia na úlohu s ohrani

eniami:

–

V = {V

1, V2, V3, V4}

–

D

i = {žirafa, európa, puška, kurín, auto, íver, pór, eso}

i = 1 ..

4

–

C = {C1, C2, C3, C4, C1,2, C1,4, C2,3, C3,4}

–

Napr. C1 = {(žirafa), (európa)}, C1,2 = {(žirafa,žirafa), …, (eso,
eso), …, (európa, puška), …}

7

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Sie

ohrani

ohra

ení pre pr

pre

íklad

kla 1.

(redukovan

redukov

á verzia

ver

)

8

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Príklad

kla 2. (numerick

numer

á dopl

do

ova

o

ka)

Dopl

te 4 kladnéreálne ísla do voných

polí

ok tak, aby

–

Sú

et

ísiel v každom riadku a st

pci bol 20

–

ísla sa zvyšujú v smere z

ava doprava

–

ísla sa zvyšujú v smere zhora nadol

Transformácia na úlohu s ohrani

eniami:

–

V = {V

12, V14, V32, V34}

–

D

i =

i

–

C = {C12, C14, C32, C34, C12,14, C12,32, C32,34, C14,34}

–

Napr. C12: {V12 > 1.7, V12 < 2.4},

C12,14 : {V12 < V14 0.8 + V12 + 2.4 + 2.6 + V14 + 8.8 = 20}, etc.

9

Rozvrhovanie a logistika (Úlohy s ohrani eniami)

Ján Parali (www.tuke.sk/paralicj)

Prístupy k rie

stupy k

šeniu

en

úloh s ohrani

loh s ohra

eniami

eniam

nad

na kone

ko

nými

ný

dom

d

énami

na

1. Reduk né algoritmy (sa snažia zredukova

P,t.j.

domény premenných a/alebo ohrani

enia tak aby

nájdenie riešenia bolo

o najjednoduchšie)

–

Zabezpe

enie silnej k-konzistencie je výpo

tovo náro

né, ale

následné nájdenie riešenia je ve

mi jednoduché

2. Preh adávacie algoritmy (preh

adávajúP za ú elom

nájdenia riešení)

–

Jednoduché algoritmy, ale

asto musia preh

adáva

obrovské

asti P

3. Kombinované algoritmy (kombinujú prístupy 1 a 2 v

snahe využi

výhody oboch prístupov)

–

Pred každým krokom preh

adávania sa aplikuje

(jednoduchší) reduk

ný algoritmus

10

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

né algoritmy

algoritm 1.

k-konzistencia (k

<1,n>) siete ohrani enívlastne

znamená konzistenciu všetkých podmnožín množiny
premenných V s kardinalitou k

Formálna definícia k-konzistencie:

Nech

ubovo

ným k-1 premenným sú priradené také

hodnoty z ich domén, aby všetky ohrani

enia definované

nad touto (k-1)-ticou premenných boli splnené. Pre

ubovo

nú

alšiu k-tu premennú je možné vybra

takú

hodnotu z jej domény, že všetky ohrani

enia definované

nad vzniknutou k-ticou premenných sú splnené.

Silná k-konzistencia znamená, že sie

ohrani eníje

j-konzistentná pre všetky j z intervalu <1,k>

11

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

1-konzistenciu (uzlovú konzistenciu, NC) je ve

!mi

jednoduché zabezpe

i , sta íporovna každúdoménu D

i

s unárnym ohrani

ením Ci aodstráni všetky

nekonzistentné hodnoty z D

i

2-konzistencia (hranová konzistencia, AC) znamená, že
hodnoty v

!ubovo!nej doméne D

i sa porovnávajú s

hodnotami inej premennej D

j a ak pre

!ubovo!núhodnotu

v

m

i z D

i neexistuje konzistentná hodnota z Dj (s oh

!adom

na Ci,j), táto hodnota v

m

i sa odstráni z doményD

j

Existujú rôzne verzie algoritmu AC s rôznou

asovou a

priestorovou zložitos

ou (AC2 .. AC7)

Zložitos

algoritmov pre zabezpe enie k-konzistencie

k>2 je exponenciálna, preto sa používajú iba v

!mi

zriedkavo (niekedy sa používa 3-konzistencia nazývaná
tiež konzistencia po ceste, PC)

Reduk

Red

" né algoritmy 2.

algoritmy

12

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

3

Reduk

Red

" né algoritmy 3.

algoritmy

Aplikujme teraz algoritmus AC na úlohu z príkladu 1 pri danom
poradí premenných: V

1, V2, V4, a V3

Za neme teda premennou V

1. V jej doméne pre hodnotu žirafa

neexistuje hodnota v doméne premennej V

2, ani V4, ktorá by bola

konzistentná s príslušným binárnym ohrani ením C12, resp. C14 . Túto
hodnotu môžeme preto vyradi

13

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 4.

algoritmy

Pokra ujeme teraz premennou V

2, v doméne ktorej zase hodnota

puška nemá kompatibilnú hodnotu v doméne V

3, ktorá by sp

ala

ohrani enie C23

Hodnotu puška teda môžeme z domény D

2 odstráni

. V dôsledku

toho sa nám zjednoduší aj ohrani enie C23 , v ktorom vypadne
prípustná dvojica hodnôt (európa,puška).

14

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 5.

algoritmy

alšou premennou v poradí je V

4. V jej doméne existuje hodnota

eso, pre ktorú nemáme kompatibilnú hodnotu premennej V

3

vzh

adom na ohrani enie C34 .

Hodnotu eso môžeme preto z domény D

4 odstráni

. V dôsledku toho

sa upraví aj ohrani enie C34, z ktorého vypadne povolená dvojica
(eso,auto).

15

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 6.

algoritmy

A nakoniec ostala premenná V

3. V jej doméne môžeme

analogicky odstráni

hodnotu auto vzh!adom na

ohrani

enie C34 .

16

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 7.

algoritmy

Výsledkom aplikácie reduk

ného algoritmu AC bola

redukcia P na jediný bod, ktorý zárove

predstavuje

jediné riešenie danej úlohy s ohrani

eniami

(dopl

ova

ka).

17

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 8.

algoritmy

Aplikujme teraz algoritmus AC na úlohu z príkladu 1
modifikovanú takým spôsobom, že pridáme 2 nové možné
slová, a síce medve

a dekan

Poradie premenný sa nezmení: V

1, V2, V4, a V3

18

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

4

Reduk

Red

" né algoritmy 9.

algoritmy

V doméne premennej V

1, môžeme z rovnakých dôvodov

ako predtým (nekompatibilita s V

2 a V4, vh

!adom na

ohrani

enia C12

, resp.

C14) odstráni

hodnotu žirafa.

19

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Reduk

Red

" né algoritmy 10.

algoritmy 1

Podobne v doméne premennej V

2, hodnota puška opä

nemá

kompatibilnú hodnotu v doméne premennej V

3, ktorá by sp

ala

ohrani enie C23 . Môžeme ju teda odstráni

a upravi pod a toho aj

ohrani enie C12 vypustením povolenej kombinácie (európa,puška).

Žiadna alšia redukcia použitím algoritmu AC nie je možná
Pre CSP s n premennými vo všeobecnosti iba prísna n-konzistencia
zabezpe í že následné preh

adávanie nemôže skon i v slepej uli ke!

20

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Preh

P

adávacie

vac

algoritmy

algoritm 1.

Základným je algoritmus spätného navracania (BT),
ktorý vlastne realizuje slepé preh

!adávanie P do hbky

–

Premenným sa prira ujú hodnoty sekven ne

–

Každé ohrani enie sa testuje hne ako je to možné (t.j. ke
akonáhle sú priradené hodnoty všetkým premenným, nad
ktorými je ohrani enie definované)

–

Ak je ohrani enie porušené, BT sa vráti k premennej, ktorej bola
priradená hodnota naposledy a pokúsi sa jej priradi

novú

hodnotu z jej domény

–

Zvykne dochádza

k „trashing“-u (opakovanie tej istej prí iny

neúspechu v rôznych astiach priestoru preh

adávania)

Lepšie (ale výpo

tovo náro nejšie) preh!adávacie

algoritmy sú spätné navracanie riadené závislos

ami,

algoritmus spätného skoku a mnohé

alšie

21

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Strom preh

adávania

generovaný
algoritmom BT pre
dané poradie
premenných (V

2, V4,

V

1, V3) a

usporiadanie hodnôt
(vi redukovaná sie

ohrani ení dole)

Trashing možno
pozorova

v uzloch

6 a 15: tá istá
prí ina neúspechu –
C3,4 nekompatibilita
slov pór a auto

22

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Preh

P

adávacie

va

algoritmy

algoritm 3.

Efektívnos

procesu preh!adávania je danánielen

použitým algoritmom preh

!adávania ale aj:

–

Usporiadaním premenných (vi . napr. strom preh

adávania

algoritmu BT pre príklad 1 so zmeneným poradím premenných
na V

2, V4, V1, V3)

–

Poradie priradzovania hodnôt z domény

(napr. ak zmeníme
poradie hodnôt
v D

1 a D3 ušetríme

alšie dva uzly

v strome
preh

adávania,

a síce uzly
s íslami 10 a 13)

23

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Kombinovan

Kombinov

é algoritmy

algorit

1.

CSP

Jednoduchšia

CSP

Reduk ný

krok

navracanie

1 krok

preh

adávania

(priradenie

hodnoty

premennej)

navracanie

24

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

5

Logick

Log

é programovanie ohrani

programovanie ohra

ení (CLP)

(CL

Deklaratívne programovanie
Logické premenné
Unifikácia => syntaktická
manipulácia s
neinterpretovanými štruktúrami
Preh

adávacia stratégia BT =>

„generuj a testuj“

Logick

Log

é programovanie

programova

Sp

anie ohrani

anie ohra

ení

Deklaratívna formulácia úlohy
ako:

Premenné s po

iato

nými

doménami

Ohrani

enia

Reduk né algoritmy (ur itý
stupe

konzistencie)

Deklaratívne programovanie

Premenné s atribútmi => rozšírená unifikácia

Sémantické objekty (kvôli špecifickým typom domén)

Kombinovaná stratégia preh

adávania => „ohrani a

generuj“

Integrované optimaliza né algoritmy

2 rôzne technológie

25

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Logick

Log

é programovanie ohrani

programovanie ohra

ení

Neúplné reduk né algoritmy

Samostatný algoritmus pre
každý typ ohrani ení (lokálna
propagácia)

Optimalizácia metódou
„vetvenia a medzí“

Kone

Ko

nédom

d

ény

Nekone

Neko

nédom

d

ény

Úplné reduk né algoritmy

Jeden algoritmus pre celú
množinu ohrani ení

Optimalizácia použitím
simplexového algoritmu

26

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

Jazyk

Jazy ECLiPSe

ECLiP

ECLiPSe (ECLiPSe Common Logic Programming System) je logický
programovací jazyk (rozšírený Prolog) ktorého cie

om je poskytova

platformu pre integráciu rôznych rozšírení logického programovania,
najmä logické programovanie ohrani ení (CLP)
Je postavený na inkrementálnom kompilátore, ktorý kompiluje
zdrojový kód v ECLiPSe do kódu podobného WAM a emulátore
tohoto abstraktného kódu

alšie informácie: http://www.icparc.ic.ac.uk/eclipse

! " # $!%'&(!)*

eclipse-

users@icparc.ic.ac.uk).

+ ! -,!. !!!/. !0

1#2 . !!,3 4 2 !. !

majordomo@icparc.ic.ac.uk

5 68789 : 2 6;<!. =. !>? @ @!%'&(!)!A

–

TkEclipse

BC!DFE GHI J KMLN!HKPO QPEHRS N!KMTO QPULVFEWBC!I!XRS QPHK!YDEW

O C!Z[!O QPN!LKMEI$EC!\$BL]^PHC!O I$QMVFKP]W\$I$DGDFHWP\@I$_P`aLbPcKPd

–

DosEclipse

BC!DFE GHI J KMHO QPeLfFN g?BO REQPZC SFg?O LQPeC!E

5h! !i2 68. j @kmlh&$n . >-!

5%'&(!) - !. ,4o0p8 >-9 !q <3. i! 68 . !:8,

http://neuron.tuke.sk/~paralic/eclipse5.3

27

:- lib(fd).

doplnovacka(Zoznam) :-

% PREMENNE

Zoznam = [V1,V2,V3,V4],

% DOMAINS

V1 :: [žirafa,európa],

V2 :: [puška,kurín],

V3 :: [auto,íver],

V4 :: [por,eso],

% OHRANICENIA

V1 #= európa #<=> (V2 #= puška #\/ V2 #= kurín), %C12

V2 #= kurín #<=> V3 #= íver,

%C23

V1 #= európa #<=> V4 #= por,

%C14

((V3 #= íver #<=> V4 #= por) #\/

(V3 #= auto #<=> V4 #= eso)) ,

%C34

% PREHLADAVANIE

labeling(Zoznam).

Príklad 1

klad

– riešenie v jazyku

enie v jazyk ECLiPSe

ECLiP

28

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

:- lib(clpr).

numericka_doplnovacka(Zoznam) :-

% PREMENNE

Zoznam = [V12,V14,V23,V34],

% OHRANICENIA

{

1.7 < V12, V12 < 2.4, %

C12

2.6 < V14, V14 < 8.1, %

C14

3.2 < V23, V23 < 3.6, %

C23

8.1 < V34,

%

C34

0.8 + V12 + 2.4 + 2.6 + V14 + 8.8 = 20, %

C12,14

1.7 + V12 + 3.2 + V23 + 9.7 = 20,

%

C12,23

V23 + 3.6 + 4.5 + V34 = 20, %

C23,34

V14 + 8.1 + V34 = 20 %

C14,34

}.

Príklad 2

klad

– riešenie v jazyku

enie v jazyk ECLiPSe

ECLiP

29

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

?- numericka_doplnovacka(Zoznam).

Zoznam = [V12, V14, V23, V34]

Yes (0.00s cpu)

% Linear constraints:

{

V12 < 2.2,

V14 = 5.3999999999999986 - V12,

V23 = 5.4 - V12,

V34 = 6.5 + V12,

V12 > 1.8000000000000003

}

Príklad 2

klad

– výsledky

výsled

To znamená, že existuje nekone

s

ne

ve

t

a riešení, V12 je nezávislá

premenná a musí by

u

z intervalu

(1.8, 2.2). Nech napr. V12 = 2.0

?- numericka_doplnovacka([V12,

V14, V23, V34]), V12 = 2.0.

V14 = 3.3999999999999986

V23 = 3.4000000000000004

V34 = 8.5

V12 = 2.0

Yes (0.00s cpu)

30

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

6

:- lib(clpq).

Numericka_doplnovacka(Zoznam) :-

% PREMENNE

Zoznam = [V12,V14,V23,V34],

% OHRANICENIA

{

4/5 < V12, V12 < 12/5, 17/10 < V12, V12 < 16/5, %

C12

13/5 < V14, V14 < 44/5, V14 < 81/10,

%

C14

V23 > 16/5, V23 < 18/5, V23 < 97/10,

%

C23

V34 > 9/2, V34 > 81/10,

%

C34

4/5 + V12 + 12/5 + 13/5 + V14 + 44/5 = 20,

%

C12,14

17/10 + V12 + 16/5 + V23 + 97/10 = 20,

%

C12,23

V23 + 18/5 + 9/2 + V34 = 20,

%

C23,34

V14 + 81/10 + V34 = 20

%

C14,34

}.

Príklad 2

klad

– riešenie s absol

enie s abs útnou

tno

presnos

presn

ou

31

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

?- numericka_doplnovacka(Zoznam).

Zoznam = [V12, V14, V23, V34]

Yes (0.00s cpu)

% Linear constraints:

{

V12 < 11 / 5,

V14 = 27 / 5 - V12,

V23 = 27 / 5 - V12,

V34 = 13 / 2 + V12,

V12 > 9 / 5

}

Príklad

kla 2 – výsledky pre racion

výsledky pre rac

álne

ln

dom

d

ény

To znamená, že existuje nekone

s

ne

ve

t

a riešení, V12 je nezávislá

premenná a musí by

u

z intervalu

(9/5, 11/5), nech napr. V12 = 2

?- numericka_doplnovacka([2, V14,

V23, V34]).

V14 = 17 / 5

V23 = 17 / 5

V34 = 17 / 2

Yes (0.01s cpu)

32

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

:- lib(clpr).

numericka_doplnovacka(Zoznam, Vazeny_sucet) :-

% PREMENNE

Zoznam = [V12,V14,V23,V34],

% KRITERIALNA FUNKCIA

Vazeny_sucet = 5*V12 + 3*V14 + 2*V2 + V34,

% OHRANICENIA

{

1.7 < V12, V12 < 2.4, %

C12

2.6 < V14, V14 < 8.1, %

C14

3.2 < V23, V23 < 3.6, %

C23

8.1 < V34,

%

C34

0.8 + V12 + 2.4 + 2.6 + V14 + 8.8 = 20, %

C12,14

1.7 + V12 + 3.2 + V23 + 9.7 = 20,

%

C12,23

V23 + 3.6 + 4.5 + V34 = 20, %

C23,34

V14 + 8.1 + V34 = 20 %

C14,34

},

% OPTIMALIZACIA

maximize(Vazeny_sucet).

Príklad 2

klad

– optimaliza

optimal

ná verzia (1)

verzia

33

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

?- numericka_doplnovacka(L,Suma).

No (0.00s cpu)

To znamená, že v tomto prípade

riešenie neexistuje (v dôsledku
ostrých nerovností), ale môžeme
vypo

s

íta

u

supremum kriteriálnej

funkcie

Namiesto volania predikátu:

maximize(Vazeny_sucet)

použijeme volanie:

sup(Vazeny_sucet, Supremum)

a výsledok bude:

?- numericka_doplnovacka(L, Sup).

L = [V12, V14, V23, V34]

Sup = 35.699999999999996

Yes (0.01s cpu)

% Linear constraints:

{

V14 = 5.3999999999999986 - V12,

V23 = 5.4 - V12,

V34 = 6.5 + V12,

V12 =< 2.2,

V12 >= 1.8000000000000003

}

Príklad 2

klad

– optimaliza

optimal

ná verzia (2)

verzia

34

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

Príklad

kla 3 – Investi

Inve

ná úloha

lo

Spolo

nos

by chcela zrealizova

pä

rôznych investi

ných akcií

(1 až 5) s danými nákladmi a o

akávanými ziskami (vi

. tabu

ka) v

priebehu nasledujúceho roka. Ale existuje limit investícií pre
nasledujúci rok vo výške 130 pe

ažných jednotiek. Ktoré

investi

né akcie majú by

vybrané, aby sa maximalizoval ro

ný

zisk?

1

3

2

5

4

O

s

akávaný ro

s

ný zisk

20

50

30

70

40

Náklady

5

4

3

2

1

Investi

s

ná akcia

35

Rozvrhovanie a logistika (Úlohy s ohrani

r

eniami)

Ján Parali

r

(www.tuke.sk/paralicj)

:- lib(fd).

investi

ný(Investície) :-

% PREMENNÉ

Investície = [I1, I2, I3, I4, I5],

% DOMENY

Investície :: [0,1],

% OHRANI

ENIE

40*I1 + 70*I2 + 30*I3 + 50*I4 + 20*I5 #<= 130,

% KRITERIÁLNA FUNKCIA

4*I1 + 5*I2 + 2*I3 + 3*I4 + I5 #= Zisk,

% OPTIMALIZÁCIA

min_max((labeling(Investície),write(Investície),write(' ')),-Zisk).

Program je možné napísa

aj všeobecne tak, aby riešil

ubovo

nú investi

nú

úlohu ve

kosti N.

Príklad

kla 3 – riešenie v jazyku

enie v jazyk ECLiPSe

ECLiP

cie

kriteriálna

funkcia

36

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)

7

?- investicny(Investicie).

Investicie = [1, 1, 0, 0, 1]

Yes (0.02s cpu)

[0, 0, 0, 0, 0] Found a solution with cost 0

[0, 0, 0, 0, 1] Found a solution with cost -1

[0, 0, 0, 1, 0] Found a solution with cost -3

[0, 0, 0, 1, 1] Found a solution with cost -4

[0, 0, 1, 1, 0] Found a solution with cost -5

[0, 0, 1, 1, 1] Found a solution with cost -6

[0, 1, 0, 1, 0] Found a solution with cost -8

[1, 0, 1, 1, 0] Found a solution with cost -9

[1, 1, 0, 0, 1] Found a solution with cost -10

Príklad

kla 3 – výsledky

výsled

37

Rozvrhovanie a logistika (Úlohy s ohrani

eniami)

Ján Parali

(www.tuke.sk/paralicj)