Müasir cəmiyyətdə informasiyanın həcmi planetin 20 IL əvvəl mövcud olan bütün informasiya həcmini üstələyir. Bütün daxil olan məlumatların emalı çox vaxt aparır

1.2. “Dinamik proqramlaşdırma” üsulu ilə həll edilən
klassik məsələlərin növləri

Dinamik proqramlaşdırma nəzəriyyəsində 1940-cı ildən başlayaraq həm riyaziyyatın, həm də proqramlaşdırmanın müxtəlif sahələrinə təsir edən müəyyən şərtləri olan bir çox problemlərə, konkret nümunələrə baxılır. R. Bellman bəzi problemləri nəzərdən keçirərək, Bellman tənliyinin optimal həllini və tətbiqini göstərən bir neçə problemi ətraflı təsvir edərək bu problemlərin həllinə öz töhfəsini verdi. Dinamik proqramlaşdırma metodu digər alimlər tərəfindən genişləndirilmiş, praktik məsələlərin həllinə doğru istiqamətlənmiş, yeni sinif məsələlər yaratmaq üçün inkişaf etdirilmiş və klassik problemlər toplusunu tamamlanması üçün işlənmişdir. Dinamik proqramlaşdırma metodu ilə həll olunan məsələlərin növlərinə şərtlərə görə Bellman tənliyi ilə eyni olan oxşar rekursiv münasibətlər aiddir. Dinamik proqramlaşdırmanın xüsusi bilik tələb edən ayrıca metod kimi yaradıldığı vaxtdan xeyli vaxt keçib, eynilə riyaziyyatda olduğu kimi, orada da klassik məsələlər qrupu formalaşıb. Əlbəttə ki, proqramçının praktik fəaliyyətində başqa vəzifələr də var, lakin bu təsnifat mütəxəssisin metodun başa düşməsi üçün bilməli olduğu əsas növləri əks etdirir.

1950-ci illərdə R.Vellman və onun tələbələri tərəfindən böyük ölçüdə yaradılmış dinamik proqramlaşdırma çoxmərhələli optimal həllərin öyrənilməsi üçün riyazi alətdir. Çoxmərhələli proseslər elm və texnologiyanın müxtəlif sahələrində optimallaşdırma problemlərinin həlli yollarını əldə etməyə imkan verir.
R.Vellman metodun adını belə izah edir [6]: “Ad aşağıdakı mülahizələr əsasında qəbul edilmişdir. İndi məşhur olan terminologiyadan istifadə edərək deyə bilərik ki, nəzərdən keçirdiyimiz problemlər proqramlaşdırma problemləridir (yəni qərar vermə problemləri). Eyni zamanda, "dinamik" sözü zamanın əhəmiyyətli rol oynadığı proseslərlə maraqlandığımızı göstərir və burada əməliyyatların ardıcıllığının rolu həlledici ola bilər.
R.Vellmanın təbirincə optimallıq prinsipi belədir: “Optimal davranış elə bir xüsusiyyətə malikdir ki, ilkin vəziyyət və qərar (nəzarət) nə olursa olsun, ilkin anda sonrakı qərarlar (nəzarətlər) ilkin qərar nəticəsində yaranan vəziyyətə nisbətən optimal davranışı təşkil etməlidir”. Başqa sözlə desək, indiki məqamda belə bir qərarın (idarəetmənin) qəbulu zəruridir ki, qalan vaxt ərzində ən yaxşı nəticələr əldə olunsun.
Dinamik proqramlaşdırmanın əsas əhəmiyyəti ondan ibarətdir ki, dinamik proqramlaşdırma optimallaşdırma məsələlərinin həlli üçün bir sıra ədədi alqoritmlərin əsasında dayanır.
Dinamik proqramlaşdırma çoxmərhələli proseslərə xüsusi uyğunlaşdırılmış optimal idarəetmənin tapılması üçün riyazi üsuldur. Belə bir prosesin bir nümunəsini nəzərdən keçirin. Bir qrup müəssisələrin fəaliyyəti N il müddətinə planlaşdırılsın. Burada addım bir ildir. 1-ci ilin əvvəlində müəssisələrin inkişafı üçün vəsait ayrılır ki, bu da bir növ bu müəssisələr arasında bölüşdürülməlidir. Onların fəaliyyət göstərməsi prosesində ayrılan vəsaitlər qismən xərclənir. Hər bir müəssisə il ərzində qoyulan vəsaitdən asılı olaraq müəyyən gəlir gətirir. İlin əvvəlində mövcud vəsaitlər müəssisələr arasında yenidən bölüşdürülə bilər: onların hər birinə vəsaitin müəyyən hissəsi ayrılır. Sual yaranır: hər ilin əvvəlində mövcud vəsaiti müəssisələr arasında necə bölüşdürmək lazımdır ki, bütün müəssisələrdən N il ərzində ümumi gəlir maksimum olsun? Qarşımızda idarə olunan proses - bir qrup müəssisənin fəaliyyətini nəzərdə tutan tipik dinamik proqramlaşdırma problemi dayanır. Proseslərin idarə edilməsi vəsaitlərin bölüşdürülməsindən (və ya yenidən bölüşdürülməsindən) ibarətdir.
Dinamik proqramlaşdırma ən güclü optimallaşdırma üsullarından biridir. Müxtəlif profilli mütəxəssislər rasional qərarlar qəbul etmək, ən yaxşı variantları seçmək və optimal nəzarət vəzifələri ilə məşğul olurlar. Optimallaşdırma üsulları arasında dinamik proqramlaşdırma xüsusi yer tutur. Bu üsul onun əsas prinsipinin - optimallıq prinsipinin sadəliyi və aydınlığı səbəbindən son dərəcə cəlbedicidir. Optimallıq prinsipinin tətbiq dairəsi son dərəcə genişdir, onun tətbiq oluna biləcəyi problemlərin dairəsi hələ tam şəkildə göstərilməyib. Dinamik proqramlaşdırma əvvəldən optimallaşdırma məsələlərinin praktiki həlli vasitəsi kimi çıxış edir.
Bu metodun yaranması 1950-ci illərin əvvəllərində bir sıra konkret problemlərə sonralar optimallıq prinsipi adlanan texnikanı tətbiq edən amerikalı alim R.Bellmanın adı ilə bağlıdır. Sonuncunun əsas tətbiq sahəsi çox mərhələli proseslərdir, yəni yeni optimallaşdırma metodunu dinamik adlandırmağa əsas verən zamanla inkişaf edən proseslərdir. Dinamizmə işarə edərək, bu üsul əsas problemlərinin ilkin tərtibi statik xarakter daşıyan xətti və riyazi proqramlaşdırmadan fərqlənirdi.
Dinamik proqramlaşdırmanın dəqiq tərifini vermək çətindir. Onun yalnız üç xarakterik xüsusiyyətini qeyd edək. Dinamik proqramlaşdırma aparatında əsas tədqiqat metodu olan optimallıq prinsipinə əlavə olaraq, oxşar problemlər ailəsində müəyyən bir optimallaşdırma probleminin batırılması ideyası mühüm rol oynayır. Onu digər optimallaşdırma üsullarından fərqləndirən üçüncü xüsusiyyəti yekun nəticənin formasıdır. Çoxmərhələli, diskret proseslərdə optimallıq prinsipinin və immersion prinsipinin tətbiqi keyfiyyət meyarının optimal qiymətinə münasibətdə rekursiv-funksional tənliklərə gətirib çıxarır. Alınan tənliklər ilkin problem üçün optimal idarəetmə vasitələrini ardıcıl olaraq yazmağa imkan verir. Burada üstünlük ondan ibarətdir ki, bütün proses üçün nəzarətin hesablanması vəzifəsi prosesin ayrı-ayrı mərhələləri üçün nəzarətin hesablanmasının bir sıra sadə tapşırıqlarına bölünür.
Metodun əsas çatışmazlığı, Bellmanın təbirincə desək, “ölçülülüyün lənətidir” – problemin ölçüsünün artması ilə onun mürəkkəbliyi fəlakətli şəkildə artır.
Dinamik proqramlaşdırma idarə olunan proseslərin optimal planlaşdırılmasına imkan verən riyazi aparatdır. “İdarə olunan” dedikdə müəyyən dərəcədə təsir edə biləcəyimiz prosesləri nəzərdə tuturuq. Bu işin məqsədi stoxastik dinamik proqramlaşdırmanın üsullarını öyrənmək və praktiki məsələlərin həllində tətbiq etməkdir.
Dinamik proqramlaşdırma həlləri alt problemlərlə birləşdirərək problemləri həll edir. O, böl və fəth et metoduna bənzər ola bilər, burada problem üst-üstə düşməyən alt problemlərə bölünür, alt problemlər rekursiv şəkildə həll edilir və sonra orijinal problemin həllini tapmaq üçün birləşdirilir. Bunun əksinə olaraq, dinamik proqramlaşdırma alt tapşırıqlar üst-üstə düşdükdə, yəni alt tapşırıqların ümumi alt tapşırıqları olduqda tətbiq edilir. Bu kontekstdə böl və fəth alqoritmi lazım olduğundan daha çox işləyir, təkrar-təkrar ümumi alt problemləri həll edir. Dinamik proqramlaşdırma alqoritmi hər bir alt problemi yalnız bir dəfə həll edir və sonra onun cavabını cədvəldə saxlayır, beləliklə, hər bir alt problemi həll etdikdə cavabı yenidən hesablamaq işindən qaçır [36].
Optimallıq prinsipinə əsaslanan təxmini alqoritmlərin ümumi ideyası ondan ibarətdir ki, prosesin optimallaşdırılması lazım olan bütün interval o qədər kiçik intervallara bölünür ki, bu kiçik intervalda optimallaşdırma probleminin həlli artıq çətin olmayacaq. Bundan sonra problemin həlli “sondan” başlayır. Optimallıq prinsipinə görə, son mərhələdə optimal idarəetmə əvvəlki addımlarda nəzarətin necə olmasından asılı deyil. Son mərhələdə nəzarət, birincisi, bu (və yalnız bu) addımın şərtləri üçün optimal olmalı və ikincisi, verilmiş son nöqtəyə aparmalıdır [37].
Bununla belə, son mərhələdə nəzarəti seçmək üçün sondan əvvəlki addımın necə bitdiyini bilməlisiniz. Bu, son addım üçün ilkin şərti verir. Bunu bilmədiyimiz üçün sondan əvvəlki addımın nəticəsi ilə bağlı müxtəlif fərziyyələr irəli sürəcəyik və bu fərziyyələrin hər biri üçün son mərhələdə optimal nəzarəti və funksionalın qiymətini hesablayacağıq. Bundan sonra biz sondan əvvəlki mərhələdə idarəetmə seçiminə keçirik və onu elə seçirik ki, artıq sonuncu mərhələdə seçilmiş idarəetmə ilə birlikdə son iki addımda funksionalın ekstremumunu təmin etsin. Beləliklə, dinamik proqramlaşdırma prosesi zamanla əks istiqamətdə - sondan əvvələ - verilmiş başlanğıc nöqtəsinə çatana qədər inkişaf edir.
Kəsilməz optimal idarəetmə məsələləri kifayət qədər kiçik kvantlaşdırma addımını seçməklə diskret seçimlərə gətirilə bilər. Lakin addım azaldıqca hesablamaların həcmi sürətlə artır və dinamik proqramlaşdırmanın ədədi alqoritmləri onların həyata keçirilməsi üçün çox yüksək sürətli kompüterlər tələb edir.
Dinamik proqramlaşdırma həllin tapılması üçün addım-addım əməliyyatlara uyğunlaşdırılmış optimallaşdırma texnikasıdır. Tapşırıq bir sıra ardıcıl addımlara və ya mərhələlərə bölünür.
Metodun tətbiq oluna bilməsinin şərti məqsəd funksiyasının additivliyi, yəni hər biri yalnız bir dəyişəndən asılı olan n dəyişənli funksiyanın funksiyanın cəmi kimi təqdim edilməsinin mümkünlüyüdür.
Dinamik proqramlaşdırmanın vəzifələri arasında aşağıdakı məsələlər var: avadanlıqların dəyişdirilməsi və yüklənməsi; planlaşdırma mərhələləri üzrə resursların optimal bölgüsü; optimal inventar idarə edilməsi; kapital qoyuluşlarının optimal bölgüsü və bir çox başqaları [37-38].
Dinamik proqramlaşdırma metodunun klassik problemləri aşağıdakılardır:
1. Fibonaççi ədədlərinin hesablanması məsələsi;
2. Ən böyük ümumi alt ardıcıllıq məsələsi;
3. Ən böyük artan alt ardıcıllığın tapılması məsələsi;
4. Redaksiya məsafəsi problemi (Levenşteyn məsafəsi);
5. Matrislərin vurulması qaydası məsələsi;
6. Trayektoriyanın seçilməsi problemi;
7. Davamlı qərar qəbul etmə vəzifəsi;
8. Əməyin istifadəsi problemi;
9. İnventarların idarə edilməsinin vəzifəsi;
10. Çanta məsələsi;
11. Floyd-Warshall alqoritmi: qrafın bütün təpələri arasında ən qısa məsafənin tapılması;
12. Bellman-Ford alqoritmi: verilmiş iki təpə arasında qrafda ən qısa yolun tapılması.