Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
J.Arabas"Wykładyzalgorytmówewolucyjnych",Warszawa2004,wyd.II,ISBN83-204-2970-6©byWNT
1.2.Rodzajezadań
1.2.1.Właściwościfunkcjicelu
ZadaniawZnbędącedyskretnąwersjązRn.Niektóre
zzadańcałkowitoliczbowychmożnauzyskać,formułujączadanie
ciągłeiprzyjmującdodatkowoograniczenie,żezbiórdopuszczalny
zawierawektory,którychwartościzmiennychniezależnychsąlicz-
bamicałkowitymi.Zadaniatakiemożnapróbowaćrozwiązywać
wsposóbprzybliżony,stosującmetodęrelaksacjiograniczenia
ocałkowitoliczbowości.Wówczas,rozwiązanieodpowiedniego
problemuciągłegomożestanowićoszacowanieproblemudyskret-
negolubprzynajmniej(poprzybliżeniudonajbliższegorozwiąza-
niadyskretnego)służyćjakopunktpoczątkowyposzukiwań*.
Prosteprzeniesieniewłaściwościzadańciągłychnaichwer-
sjedyskretnemożeprowadzićdopochopnychuogólnień.Niespo-
sóbzagwarantować,żenieskomplikowanyproblemciągłyprowa-
dzidorówniełatwegozadaniadyskretnego.Wznacznejmierze
zależytoodsposobudyskretyzacji—imjestona„gęstsza”**,
tymłatwiejmożemyprzenieśćwłaściwościwersjiuciąglonejna
oryginalnąwersjędyskretną.
Liniowość.Funkcjaliniowamapostać
f(x)=aTx+b
(1.2)
gdzieajestn-wymiarowymwektorem,b—stałą.Jeślifunkcja
celujestliniowa,torozwiązaniezadania(1.1)wypadniezawszena
granicyobszarudopuszczalnego(jeślijestdomknięty).Jeślizbiór
dopuszczalnyDjestnieskończonejmiary,toniemożnawykluczyć
sytuacji,żerozwiązanieniebędzieistniało.
Wypukłość.Funkcjawypukła(rys.1.1)spełniawarunek
łf(x1)+(1−ł)f(x2)>f(łx1+(1−ł)x2)
(1.3)
dladowolnychx1∈D,x2∈D,0<ł<1.Zakładamyprzytym,
żeDjestwypukły,czylidladowolnychx1,x2∈Dkażdypunkt
x=łx1+(1−ł)x2
gdzie
0≤ł≤1
31
równieżdoniegonależy.Jeśliwypukłesąfunkcjaceluizbiór
dopuszczalny,toistniejedokładniejednominimum.Właściwość
tabardzoułatwiaprocesoptymalizacji,możnagobowiemograni-
żerozwiązanieproblemu
*Należyjednakpamiętać,
czyćdoprzeszukiwaniasąsiedztwapunkturoboczegoiwybierania
uciąglonegomożepoza-
zeńnowegopunkturoboczego.Dostwierdzeniaznalezieniamini-
okrągleniuznajdowaćsię
dowolniedalekoodposzu-
mumwystarczywówczasupewnićsię,żewsąsiedztwienieistnieje
kiwanegorozwiązaniapro-
punktomniejszejwartościfunkcjicelu.
blemudyskretnego.
**Gęstośćpróbkowaniana-
Różniczkowalność.Kolejnąwłaściwością,któramożebyćwy-
leżyoczywiścieodnieśćdo
szybkościzmiennościfunk-
korzystanawoptymalizacjifunkcji,jestjejróżniczkowalność.Jeśli
cji,np.dostałejLipschitza
(jeśliistniejedlatejfunk-
wkażdympunkcieistniejepochodnafunkcji,topopierwsze—
cji).
