1. fejezet - Bevezetés

Az élet igen sok területéről származó feladatoknál előfordul, hogy egy adott függvénynek keressük a globális minimumát vagy éppen globális maximumát. Ez már egy egyváltozós függvénynél sem egyszerű feladat. Az analízisből megismert módszerek eszközt adnak arra, hogy megtaláljuk a függvény lokális szélsőértékhelyeit, ám ezekből ki kell választani a legjobbat. Noha ez így első olvasásra egyszerűnek tűnik, hiszen egy véges halmazból kell kiválasztani egy elemet, az adott halmaz igen nagy is lehet, melyet a szokott módszerekkel nem tudunk elfogadható időn belül megvizsgálni. Hasonló a helyzet diszkrét feladatoknál is, ahol az értelmezési tartomány elemeit kellene sorra vizsgálni.

Lássunk pár jellemző optimalizálási feladatot:

Ha arra gondolunk, hogy adott 100 000 pont az utazó ügynök problémájához, vagy 10 000 különböző logikai változót tartalmazó formula, akkor nyilvánvalóvá válik, hogy esély sincs az összes lehetséges megoldás átvizsgálására. Így az optimális megoldás helyett megelégszünk egy közel optimális megoldással is. A közel optimális megoldáshoz tartozó függvényérték reményeink szerint igen közel van az optimális megoldáshoz tartozó függvényértékhez.

Az általunk a későbbiekben vizsgálni kívánt feladatok mindegyike diszkrét feladat, és a célfüggvényt minimalizálni kívánjuk. A megoldási módszerek egy része változtatás nélkül alkalmazható folytonos esetben is. Míg más módszerek csak apróbb változtatással alkalmazhatóak folytonos függvénnyel leírható problémákra. Ezekben az esetekben felvázoljuk az eltéréseket. Végül vannak olyan módszerek is, melyek csak diszkrét feladatokra alkalmazhatóak.