predmetrini təşkil edir. Parametrik proqramlaşdırma məsələsi istehsalın
proqramlaşdırması məsələsinin öyrənilməsi ilə əlaqədar meydana gəlmişdir. Bu müxtəlif
iqtisadi proseslərin riyazi modelinin qurulması ilə onu optimal planlaşdırmağa imkan
verir.
Indi isə məqsəd funksiyası parametrik olan məsələyə baxaq.
Tutaq ki,
=
Məqsəd funksiyasının
əmsalları hər hansı
−
`
; +
`
aralığında dəyişir.
Onda uyğunluq üçün məqsəd funksiyasının əmsalını
( ) =
`
+
"
ilə əvəz edib tədqiq
etmək məqsədə uyğundur. Harda ki,
`
,
"
hər hansı aralıqda dəyişən sabitlər,
− isə
parametrdir. Bu halda riyai məsələ aşağıdakı şəkilə düşər.
=
(
`
+
"
)
məqsəd funksiyası verilmişdir.
Məhdudiyyət şərtləri
= = 1, (2)
≥ 0 = 1, (3)
Hər bir
− nın qiyməti üçün ≤ ≤ intervalında (harda ki, ə ixtiyari
həqiqi ədədlərdir) elə mənfi olmayan
= ( , , … , ) vektorunu tapmalı ki, (2)
sistemini ödəsin və
(1) funksiyasına minimum qiymət versin.
Qoyulmuş məsələni
parametrininin dəyişməsindən asılı olaraq araşdıraq.
Nəticədə iki haldan birinə gələrik:
–
= üçün optimal plan mövcuddur ( halı);
downloaded from KitabYurdu.org
–
= üçün məqsəd funksiyası məhdud deyil ( halı);
Bu halların hər birinə nəzər yetirək:
A – halı:
Tutaq ki,
= üçün optimal plan alınmışdır. Hansı ki, hər hansı bazisə uyğun
gəlir.
, , … , sistemindən ibarət olan m vektordan təşkil olunmuşdur. Planın
optimallıq şərtinə görə onun qiymətləndirilməsi
− ≤ 0 şərtini ödəməlidir. Belə ki,
=
`
+
"
. Onda optimallıq şərti belə şəkil alır.
−
=∝ +
≤ 0 = 1, (4)
Harda ki,
ə − hər hansı həqiqi ədədlərdir. Burada daxil edilir ki,
+
≤ 0, = 1, bərabərsizliklər sisemi birgədir və aşağıdakı həlli var:
≥ − ∝ ⁄ ü ü < 0 −
üçü
≤ − ∝ ⁄ ü ü > 0 −
üçü
Tutaq ki,
=
max(− ∝ ⁄ )
−∞ ə ə ≥ 0
̅ =
min(− ∝ ⁄ )
+∞ ə ə ≤ 0
Onda
= üçün məsələnin optimal həlli bu məsələnin optimal planı ilə üst – üstə
düşür, bütün
üçün,
≤ ≤ şərtini ödəyən. Bu halda [ ; ] intervalının sol ucu
örtülmüşdür, yəni
≤ , onda məsələnin həlli üçün sağ ucu da örtmək zəruridir və yaxud
≥ məsələnin həlli olmadığını göstərmək lazımdır.
Beləliklə, əgər sonludursa və
≥ , və yaxud = +∞, onda həll prosesi sona
çatır.
Bu prosesi davam etdirsək aşağıdakı teoremi isbat etmiş olarıq.
Teorem:
parametrinin heç olmazsa bir qiyməti üçün yeni bazis optimal plana
uyğundur.
B – halı:
1.
Tutaq ki, aparılmış iberasiya nəticəsində hər bir
vektoru üçün
+
>
0 qiymətləndirilməsi alınmışdır,
≤ 0. Onda əgər
≥ 0 olarsa ixtiyari üçün xətti
funksiya aşağıdan məhdud deyil.
2.
Əgər
< 0 olarsa. Onda
+
> 0 bərabərsizliyi bütün
<
`
=
−
. Buradan ixtiyari
≤ <
`
üçün optimal plana malik deyil.
Bu qayda ilə sərbəst hədlərdə parametr olan və məhdudiyyət sistemində parametr
olan parametrik məsələlərə də baxılır.
Məqsəd funksiyası
=
Məhdudiyyət şərtləri
downloaded from KitabYurdu.org
= ` +
= 1,
≥ 0 = 1,
Hər bir
≤ ≤ üçün harda ki, ə ixtiyari həqiqi ədədlərdir. Elə bir mənfi
olmayan
= ( , , … , ) vektoru tapmalı ki, məhdudiyyət sistemini ödəsin və məqsəd
funksiyasına minimum qiymət versin.
downloaded from KitabYurdu.org
Mövzu 19: Kəsr – xəti proqramlaşdırma məsələsi
Əgər qeyri xətti proqramlaşdırma məsələsində məhdudiyyət xətti ancaq məqsəd
funksiyası kəsr – xətti olarsa, onda belə məsələni kəsr – xətt proqramlaşdırma məsələsi
adlanır. Kəsr – xətti proqramlaşdırma məsələsinin ümumi şəkli:
( ) =
+
+ … +
+
+ … +
=
∑
∑
(1)
Funksiyasını
Şərtləri daxilində maksimallaşdırmalı (minimallaşdırmalı)
Simpleks metodu
Bir sıra iqtisadi məsələlərdə məzmunu tələb edir ki;
Məqsəd funksiyası
.........................
şərtini ödəsin.
Bu şərt daxilində kəsr – xətti proqramlaşdırma məsələsinin simpleks metodla həll
etmək olar.
Yeni dəyişənlər daxil edək.
.........................
.........................
Onda
(1) − (3) məsələsi aşağıdakı şəkil alar.
..................................
..................................
..................................
.................................
Şərtləri daxilində
downloaded from KitabYurdu.org
Nəticədə xətti proqramlaşdırma məsələsi alınır. Onu Simpleks metodla həll
etdikdən sonra (
(4) −ü nəzərə almaqla) (1) − (2) məsələsinin optimal həllini taparıq.
Dediklərimizi misal üzəridə aydınlaşdıraq.
Misal 1:
...............................
...............................
...............................
Həlli: Şərtə görə bütün dəyişənlər mənfi deyil. Onda
(3) şərti 2 + 3 + 1 > 0
və, uyğun olaraq, əlavə məhdudiyyətlər
...............................
..........................
Məsələ aşağıdakı şəkili alar:
...............................
...............................
...............................
...............................
İkinci, üçüncü və dördüncü məhdudiyyətləri
> 0 − a vurub yeni dəyişənlər
daxil edək:
= ;
=
Nəticədə xətti proqramlaşdırma məsələsi alarıq:
...........................
...........................
...........................
Bu məsələni Simpleks üsulla həll etsək, alarıq:
...........................
Əvəzləməni nəzərə alsaq:
=
= 20 ; =
= 12
downloaded from KitabYurdu.org
Beləliklə,
..............................
Kəsr – xətti proqramlaşdırma məsələlərində məqsəd funksiyası ii xətti funksiya
nisbəti şəklində verilməklə, məchulların mümkün dəyişmə oblastını müəyyən edən şərtlər
həmçinin xətli olurlar.
downloaded from KitabYurdu.org
Mövzu 20: Dinamik proqramlaşdırma məsələsi
Dinamik proqramlaşdırma optimal həllin tapılması bir neçə etapın yolu ilə
tapılmasına əsaslanır. Bu mövqe müxtəlif prinsiplərlə həyata keçirilir. Bir sıra məsələlərdə
zaman periodu ilə, digərlərində isə idarəetmə obyektinə görə. Çox vaxt bölgü süni olaraq
yerinə yetirilir. Dinamik proqramlaşdırmanın fundamental prinsipi onun mövqeyinin və
məsələnin etaplara bölünməsi optimaldır.
Belə yanaşma böyük həcmli məsələləri kiçik məsələlərə bölməkdən ibarətdir. Bu
isə hesablamanın həcmini kifayət qədər ixtisar edir və idarə edici həllin tapılmasını
sürətləndirir. Dinamik proqramlaşdırmada hesablama rekurrent aparılır, belə ki, hər hansı
alt məsələnin optimal həlli növbəti məsələnin ilkin verilənləri kimi qəbul edilir.
Misala baxaq. 1 – ci məntəqədən 10 – cu məntəqəyə verilmiş hərəkət marşrutuna
görə optimal marşrutu tapmalı.
..........................................
..........................................
..........................................
..........................................
Şək.1
Sxemdə göstərilmiş hər bir kvadrat məntəqələri göstərir. Özləridə nömrələnib. Bir
məntəqədən digər məntəqəyə gediş haqqı, məsələn i məntəqəsindən İ məntəqəsinə gediş
haqqı
ilə işarə edək (Bu qiymətlər sxemdə göstərilmişdir).
Tələb olunur ki, 1 – ci məntəqədən 10 – cu məntəqəyə elə marşrutla getmək
lazımdır ki, xərc mimimum olsun.
Həlli: Belmanın rekurrent münasibətlər düsturuna görə
..............................
Harda ki, N – həlldəki etapların sayıdır.
( ) − i məntəqəsindən olan yol üçn minimal xərcin strategiyasına cavab verən
dəyərdir. Harda ki, əgər sonuncu məntəqəyə n addım qalıb.
( ) − ( ) tapmaq üçün həlldi.
Sonuncu məntəqədən optimal marşrutun tapılması ilə başlayaq.
.....................................
......................................
.......................
.............................
.............................
..............................
.............................
.............................
.............................
Beləliklə, optimal yol təyin olundu.
downloaded from KitabYurdu.org
Mövzu 21: Qeyri – xətti proqramlaşdırma məsələsinin
ümumi qoyuluşu
Əgər
( , , … , ) =
,
= 1, (1)
Və
= ( , , … , ) =
(2)
,
harda ki,
ə − məlum sabitlərdir. Onda həllin mənfi olmaması şərti ilə xətti
proqramlaşdırma məsələsi alırıq. Riyazi proqramlaşdırmanın
(1) − (2) şərtlərini
ödəməyən istənilən məsələsinə qeyri – xətti proqramlaşdırma məsələsi deyilir.
Qeyri – xətti proqramlaşdırma məsələsi sinfi xətti proqramlaşdırma məsələsi
sinfindən genişdir. Qeyri – xətti proqramlaşdırmada əsas nəticələr elə məsələlərə baxarkən
alınır ki, hansı ki, mədudiyyət sistemi xəttidir, ancaq məqsə funksiyası qeyri – xəttidir.
Hətta belə məsələəlrin optimal həlli yalnız bir sinif məqsəd funksiyalar üçün tapıla bilər.
Xüsusi bir sinif məqsəd funksiyalar üçün tapıla bilər. Xüsusi hallara baxaq. Əgər məqsəd
funksiyası separabellidirsə (
− funksiyasının cəmidir) və ya kvadratikdir.
Xətti proqramlaşdırma məsələsində ekstremum nöqtələri həllər çoxbucaqlısının
təpə nöqtələrində olurdusa, biz elə misallara baxacayıq ki, qeyri – xətti proqramlaşdırma
məsələsində qeyri – xətti məqsəd funksiyası oblastın daxilində ola bilər4 üzün tilində və
ya çoxbucaqlının təpəsində ola bilər.
Beləliklə, xətti proqramlaşdırma metodunun köməyi ilə, bir təpədən digərinə
keçidihəyata keçirən, optimal həlli almaq olar, o şərt daxilində ki, məqsəd funksiyası əlavə
məhdudiyyətləri ödəyir.
Daha çox çətinlik qeyri – xətti məhdudiyyət olduqda meydana çıxır.
Qeyri – xətti proqramlaşdırma məsələsinə baxılması klassik optimallaşdırma
məsələsi ilə başlayır. Bu zaman
(1) − də tənliklər olur, mənfi olmamaq şərti iştirak etmir
və dəyişənlərin tam ədədli olması
( , , … , ) ə ( , , … , ) funksiyaları ikinci
tərtibdən az olmayan xüsusi törəməyə malikdirlər və kəsilməzdirlər.
İki dəyişənli qeyri – xətti proqramlaşdırma məsələsinin həllinə nəzər yetirək. Necə
ki, xətti proqramlaşdırmada onlar ola bilsin ki, qrafik üsulla həll edilsin.
Misal 1:
= ( − 4) + ( − 6) separabelli funksiyasının
+
≥ 1
2 + 3 ≥ 12
≥ 0,
≥ 0
Məhdudiyyət şərtləri daxilində maksimal və minimal qiymətini tapın.
downloaded from KitabYurdu.org
Həlli: n Təyin oblastı
çoxbucaqlısıdır (şək.1). yəni mümkün olan həllər
oblastı
− dir.
...........(şək. 1)...............
Əgər
= ( > 0) götürsək, Onda ( − 4) + ( − 6) = çevrə tənliyini
alarıq.
Q (radiusun kvadratını) – nü azaltmaqla (artırmaqla) Z – in qiyməti uyğun olaraq
azalır (artır).
M – nöqtəsindən, çevrənin mərkəzi kimi müxtəlif radiuslu çevrələr çəksək alarıq:
funksiyanın minimal qiyməti
( ) = 196/13 . (24/3 ; 36/15) nöqtəsində alır, hansı
ki, çevrə həllər oblastına kəsir. D nöqtəsi künc deyil, onun koordinatları MD və CE düz
xətlərinin tənlikləri sistemindən tapılır.
Z funksiyasının iki lokal maksimumu var:
( ; 0) təpəsində
( ) = 45, (6; 0) − təpəsində ( ) = 40. Belə ki, ( ) > ( ) onda
− təpəsi
qlobal maksimum olar.
Misal 2. Tutaq ki, fərz edilən həllər çoxluğu əvvəlki misaldakı kimidir.
= ( − 4) + ( − 1)
Bu funksiyanın minimum və maksimum qiymətini tapın.
Həlli: Funksiya minimal qiymətini
(4; 1) nöqtəsində alır. (şək.2)
( ) = 0
Z funksiyasının iki lokal maksimumu var:
Təpələrdə isə
(6; 0) − ( ) = 5
(0; 4) − ə ( ) = 25
Buna görə qlobal maksimumu C təpəsində alır.
Misal 3.
=
+ funksiyasının
+
≤ 4
+
≥ 5
≤ 7
≤ 6
≥ 0, ≥ 0
məhdudiyyət şərtlərini ödəyən maksimum və minimum qiymətlərini tapın.
Həlli:
Bu halda mümkün olan həllər çoxluğu iki ayrı – ayrı hissədən ibarətdir.
Z funksiyası Z=17
(1; 4) ə (4; 1) – də alır.
Z funksiyası iki lokal maksimuma malikdir.
( ; 6) nöqtəsində ( ) =
– i
(7; ) – də ( ) = 2417 49
M nöqtəsi qlobal maksimum nöqtəsidir.
Xətti proqramlaşdırma məsələsinin həlli üçün Laqranj vuruqları üsuluna baxaq.
Qeyri - xətti proqramlaşdırma nəzəriyyəsinin praktiki tətbiqi zamanı çox vaxt elə hallara
downloaded from KitabYurdu.org
təsadüf edilir ki, məsələnin riyazi qoyuluşunda məhdudiyyət şərtləri bərabərliklərdən
ibarət olur, məhculların işarələri üzərinə isə heç bir məhdudiyyət qoyulmur. Bununla
bərabər
öz törəmələri ilə birlikdə keçilməz funksiyalar olurlar, yəni alırıq:
Məqsəd fuksiyası
Məhdudiyyət şərtləri
– yə şərti ekstremum məsələsi yaxud klassik optimallaşdırma məsələsi
deyilir.
Bu məsələnin Laqranj vuruqları üsulu ilə həlli aşağıdakı etaplardan ibarətdir.
I.
– Laqranj funksiyasının tərtib edilməsi.
Bu məqsədlə Laqranj vuruqları adlanan
dəyişənləri daxil edilməklə
Laqranj fuksiyası tərtib edilir.
II.
– nın
dəyişənlərinə nəzərən xüsusi törəmələrinin tapılması
III. Tənliklər sisteminin həlli
IV. Optimal həllin təyini
Ekstremumun kafilik əlamətinin vasitəsi ilə şübhəli nöqtələr içərisində elə nöqtə
tapılır ki, burada Z(x) məqsəd funksiyası maksimum (minimum) qiymət alır. Bu isə (1),
(2) məsələsinin optimal həlli olur.
V. Z(x) – in ekstremum qiymətinin hesablanması
Optimal həlli (1) ifadəsində nəzərə alınmaqla
hesablanır.
Misal.
I.
II.
downloaded from KitabYurdu.org
III.
IV. Ikinci tərtib xüsusi törəmələrdən istifadə etməklə asanlıqla göstərmək olar ki,
alınan həlldə Z(x) minimum qiymət alır. Deməli, optimal həlldir.
V.
)
.
downloaded from KitabYurdu.org
Mövzu 22: Qradiyent metodu və onun alqoritmi
Qeyri – xətti proqramlaşdırma məsələsinin qradiyent metodu ilə həlli elə istənilən
metod başa düşülür ki, məqsəd funksiyasının optimal nöqtəyə hərəkətinin istiqaməti bu
funksiyanın qradiyentinin metodu lokal eksremum nöqtəsini məqsəd funksiyasının həllər
oblastının qabarıqlığı (çöküklüyü) şərti ilə tapılmasını göstərir.
Tutaq ki,
məsqəd funksiyası verilmişdir.
funksiyasının hər hansı
nöqtəsində qradiyenti.
vektorudur. vektoru
səthinin normalı istiqamətindədir.
funksiyasının şərtsiz ekstremum tapılması
üçün qradiyent metodunun tətbiqinə baxaq. Yəni məhdudiyyət iştirak etmir. Həll prosesi
iterasiyalıdır.
başlanğıc nöqtəsi götürülür və yerdəyişmə addımı ( vuruğu ilə
xarakterizə olunan) götürülür, belə ki,
funksiyasına ən böyük dəyişmə təmin etsin.
harda ki, yeni nöqtə
vuruğu
in ektrmumu şərtinin zəruriliyinə görə olan
Çətindən tapılır. – dən
nı tapıb
müəyyən edirik. Əgər yeni nöqtədə
olarsa həll sona çatır. Belə halda qradiyent üzrə həll mümkün olunur. Əgər
olarsa
nöqtəsi başlanğıc nöqtə qəbul edilir və proses o vaxta kimi davam
etdirilir ki, hələlik sıfır qradiyent alınmışdır. Çox vaxt həllin nəticəsi başlanğıc nöqtənin
seçilməsindən asılı olur, hansı ki, optimal həllə yaxınlaşma başlayır.
Tutaq ki, bizə qabarıq proqramlaşdır məsələsi verilmişdir.
Qradiyent metodunun alqoritmi.
1.
Funksiyanın
qradiyentini tapmalı və
tənliyini həll etməli.
şərtlərini (sistemini) stasionar nöqtələri təyin etməli və bu nöqtələrdə
funksiyasını
hesablamalı.
2.
funksiyasının qradiyentinin tapmalı və stasionar nöqtələrini təyin
etməli onları ki, oblastın uyğun
– sərhədində yerləşsin. bunun üçün aşağıdakı sistemi
həll etməli.
sisteminin həllindən eləsi götürürük ki,
ü və
şərtini ödəsin.
Məqsəd funksiyasının bu nöqtələrdə qiymətini hesablayırıq.
downloaded from KitabYurdu.org
3.
Bütün sərhəd hiper müstəvilərin kəsişməsini tapırıq. Bunun üçün aşağıdakı
sistemi həll edirik.
Harda ki,
və
həllərindən götürürük və bu həllərdə
in qiymətini
hesablayırıq.
Bu halda, əgər
olarsa, həllər çoxbucaqlısının bucaq nöqtələrini tapmaq
kafidir və bu nöqtələrdə məqsəd funksiyasının qiymətini hesablayırıq.
4.
Məqsəd funksiyasının qiymətlərinin bütün nöqtələrdə müqayisə edirik və
və
götürürük.
| 