Kombinatorial optimallaşdırma

**Kombinatorial optimallaşdırma** — riyaziyyatın və əməliyyatlar tədqiqinin bir sahəsi olub, diskret obyektlər üzərində optimal həllərin tapılması ilə məşğul olur. Bu sahədə əsas məqsəd sonlu və ya sayılabilən çoxluq daxilində mümkün variantlardan ən yaxşısını (maksimum və ya minimum dəyərlini) seçməkdir.

Kombinatorial optimallaşdırma həm nəzəri, həm də praktik baxımdan mühüm əhəmiyyətə malikdir. O, müxtəlif sahələrdə — kompüter elmləri, nəqliyyat, telekommunikasiya, robot texnikası, sənaye mühəndisliyi və bioinformatika kimi istiqamətlərdə tətbiq olunur.

Kombinatorial optimallaşdırmada aşağıdakı əsas anlayışlar istifadə olunur:
* **Axtarış sahəsi** — mümkün həllərin təşkil etdiyi çoxluq.
* **Məqsəd funksiyası** — hər bir mümkün həllə uyğun qiymət verən funksiya; bu funksiya maksimumlaşdırılır və ya minimumlaşdırılır.
* **Məhdudiyyətlər** — həll variantlarının müəyyən şərtlərə cavab verməsini təmin edən qaydalar.

## Tarixi
Kombinatorial optimallaşdırma anlayışı riyaziyyatın və əməliyyatlar tədqiqinin inkişafı ilə paralel olaraq XX əsrin birinci yarısında formalaşmağa başlamışdır. Onun elmi əsasları Leonhard Eulerin 1736-cı ildə Königsberq körpüləri problemi ilə başlatdığı qraf nəzəriyyəsində qoyulmuşdur. Bu problem müasir qraf nəzəriyyəsinin və dolayısı ilə kombinatorial optimallaşdırmanın ilkin nümunəsi hesab olunur.

XX əsrin əvvəllərində Corc Dantziq tərəfindən 1947-ci ildə təklif olunmuş simpleks metodu və xətti proqramlaşdırma sahəsində aparılan tədqiqatlar kombinatorial məsələlərin dəqiq və səmərəli həlli yollarını açdı. 1950-ci illərdə Harold Kuhn tərəfindən hazırlanmış Macar alqoritmi və Karoy Eqervarinin nəzəri nəticələri *assignment problem* kimi konkret məsələlərin optimal həllində dönüş nöqtəsi oldu.

1960–1970-ci illərdə Edmonds alqoritmi, Dinamik proqramlaşdırma (R. Bellman tərəfindən), Axtarış ağacları və müxtəlif təxmini alqoritmlər təklif edildi. Bu dövr həm də NP-tamlıq və hesablama mürəkkəbliyi nəzəriyyəsi kimi anlayışların riyaziyyat və kompüter elmlərinə daxil olması ilə əlamətdardır. Kombinatorial optimallaşdırma məsələlərinin çoxunun NP-çətin olduğu sübut ediləndən sonra daha səmərəli və praktik həll yollarının axtarışına başlanıldı.

1980-ci illərdən etibarən metaalqoritmlərə maraq artmağa başladı. Genetik alqoritmlər, simulated annealing, tabu search və digər metodlar real vaxt və böyük həcmli məsələlərin yaxın optimallaşdırılmış həllini tapmaq üçün istifadə olunmağa başlandı.

XXI əsrdə kombinatorial optimallaşdırma süni intellekt, maşın öyrənməsi, nəqliyyat sistemləri, şəbəkə dizaynı, robot texnikası və bioinformatika sahələrində mühüm alətə çevrilmişdir. Bu sahə həm nəzəri tədqiqatların, həm də praktiki tətbiqlərin mərkəzində dayanaraq daim inkişaf edir.

## Nümunələr
Kombinatorial optimallaşdırmanın ən məşhur məsələləri aşağıdakılardır:
* Tapşırıqların təyini problemi ()
* Səyahət edən satıcı problemi ()
* Qrafda maksimum uyğunluq
* Minimum örtük problemi
* Rəngləmə problemi
* Çoxbucaqlının örtülməsi problemi

## Alqoritmlər
Kombinatorial optimallaşdırma məsələlərinin həlli üçün müxtəlif alqoritmlər mövcuddur:
* Macar alqoritmi
* Tamahkar alqoritmləri (*Greedy algorithms*)
* Dinamik proqramlaşdırma
* Quruluşlanmış axtarış
* Metaalqoritm alqoritmlər:
** Genetik alqoritm
** Simulated annealing
** Tabu search

## Həmçinin bax
* Əməliyyatlar tədqiqi
* Qraf nəzəriyyəsi
* Riyazi optimallaşdırma

## İstinadlar

## Ədəbiyyat
*

*

*

*

## Xarici keçidlər

*Journal of Combinatorial Optimization
*The Aussois Combinatorial Optimization Workshop
*Java Combinatorial Optimization Platform (open source code)
*Why is scheduling people hard?
*Complexity classes for optimization problems / Stefan Kugele