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. (Information on the largest TSP instances solved to date.) 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 (This is a continuously updated catalog of approximability results for NP optimization problems.):
 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

Kateqoriya:Optimallaşdırma
Kateqoriya:Kombinatorika
Kateqoriya:Riyazi proqramlaşdırma