Mövzu : n məchullu xp məsələsinin həndəsi izahı Sərbəst iş No: 1

Ekonometrika Simran Kürdədehli

Mövzu : n məchullu XP məsələsinin

həndəsi izahı

Sərbəst iş No: 1

Qrafik üsul xətti proqramlaşdırma məsələsinin həndəsi izahına əsaslanır və adətən ikiölçülü, üçölçülü məsələlərin həlli məqsədi ilə tətbiq edilir. Belə ki, ölçüsü üçdən çox olan məsələni həndəsi olaraq təsvir etmək ümumiyyətlə mümkün deyil.

Qeyd 1. Xüsusi halda əgər məhdudiyyət şərtləri sistemi n məchullu xətti asılı olmayan m tənliklər sistemindən iba- rətdirsə və n – m  2 olarsa, onda müvafiq xətti proqram- laşdırma məsələsini də qrafik üsulla həll etmək mümkündür.

İkiölçülü halda, daha doğrusu iki dəyişən (x₁ və x₂) daxil olduqda xətti proqramlaşdırma məsələsinə baxaq:

Məqsəd funksiyası


Z (x)  p₁ x₁  p₂ x₂  max (min);

məhdudiyyət şərtləri

^a₁₁ ^x₁ ^{ a}₁₂ ^x₂ ^{ a}₁ ^,

a₂₁ x₁  a₂₂ x₂  a₂ ,

………………

^am1 ^x1 ^{ a}m 2 ^x2 ^{ a}m

(1)

(2)


x₁  0,

x₂  0

(3)

(1) – (3) XP məsələsinin qrafik üsulla həlli prosesi aşağıdakı mərhələlərdən ibarətdir:

1. 
   Məsələnin həllər çoxluğunun (oblastının) təyini. O aşağıdakı altmərhələlərdə yerinə yetirilir:
   

1. 
   (2) və (3) şərtlərində bərabərsizlik işarələri bərabərlik işarələri ilə əvəz edilir. X₁OX₂ düzbucaqlı koordinat sistemində alınmış tənliklərə uyğun düz xəttlər qurulur. Daha doğrusu tənliklərin həllər çoxluqları təyin edilir:
   

 _i1 x₁   _i2 x₂  a_i ,

(i  1, m);

x₁  0 və

^x₂ ^{ 0} ( 4)

Х ₂

S

В

D

A

E

P₂

N

r

О

P₁

X

1

məsələnin ayrı-ayrı məhdudiyyət şərtlərinin həllər çoxluğu tapılır. Bunlara (4) sərhəd düz xətləri ilə məhdudlaşan yarımmüstəvilər uyğundur ki, onlar da düz xəttlər üzərindəki oxlarla göstərilmişdir (şək. 1.).

c) alınmış yarımmüstəvilərin ortaq kəsişməsi təyin edilir. Əgər (2) və (3) sistemləri uyuşandırsa (birgədirsə), onda o qabarıq çoxbucaqlıdan (ABSDE) ibarət olur ki, bu da məsələnin həllər çoxluğunu (oblastını) təşkil edir.

Beləliklə, yarımmüstəvilərin ortaq kəsişməsi XP məsələsinin həllər çoxbucaqlısı adlanır. O nöqtə, parça, çoxbucaqlı, qeyri-məhdud çoxbucaqlı oblast və s. ola bilər.

Şəkil 1.
Tutaq ki, məsələnin həllər çoxbucaqlısı məhduddur.

2. 
   N  ( p₁ , p₂ ) vektoru qurulur.
   

OX₁ və OX₂ oxları üzərində məqsəd funksiyasının p₁ və


p₂ əmsalları müvafiq olaraq götürülməklə,

N  ( p₁ , p₂ )


radius-vektoru qurulur. Bu zaman

Z (x) 

p₁ x₁ 

p₂ x₂

məqsəd funksiyasının qiymətləri N vektoru istiqamətində artır və ona əks olan istiqamətdə isə azalırlar.

3. 
   Z (x)  0 N
   

düz xətti qurulur.


Z (x)  0 yaxud

p₁ x₁ 

p₂ x₂  0

(5)

düz xətti O (0;0) koordinat başlanğıcından keçir, belə ki, O nöqtəsinin koordinatları (5) tənliyini ödəyirlər.

4. 
   Ekstremum (dayaq) nöqtənin tapılması.
   

Ekstremum nöqtə aşağıdakı iki üsulla təyin edilir:

1. 
   - ci üsul : həllər çoxbucaqlısının (ABSDE) kənar nöqtələrindən (5) düz xəttinə endirilmiş perpendikulyarların uzunluqları müqayisə edilir. Z(x) məqsəd funksiyasının maksimum (minimum) qiyməti (5) düz xəttindən ən uzaqda (ən yaxında) yerləşən kənar nöqtədə alınır:
   

Z _max  Z (S )

^(Z min

 Z ( A))

2- ci üsul : (5) düz xətti özü-özünə paralel qalmaqla

13. 
    vektoru istiqamətində (yaxud əks istiqamətdə) o vaxta qədər hərəkət etdirilir ki, o həllər çoxbucaqlısına dayaq olsun.
    

5. 
   Məsələnin optimal həllinin təyini.
   

Ekstremum nöqtə həllər çoxbucaqlısının kənar nöqtələ- rindən biri ilə üst-üstə düşür. Şəkil 1-dən göründüyü kimi həmin nöqtə müəyyən düz xəttlərin kəsişməsində yerləşir. Deməli, ekstremum nöqtənin koordinatlarını tapmaq üçün müvafiq düz xətt tənliklərini sistem şəklində həll etmək kifayətdir. Alınmış qiymətlər məcmusu məsələnin optimal həllini təyin edir.

6. 
   Məqsəd funksiyasının ekstremum qiymətinin hesablanması.
   

S(A) ekstremum nöqtəsinin koordinatlarını (1) ifadəsində yerinə yazır və məqsəd funksiyasının maksimum (minimum) qiymətini hesablayırıq:
Z _max  Z (S )

^(Z min

 Z ( A)) .

(1) – (3) ikiölçülü XP məsələsinin həndəsi izahına baxdıqdan sonra belə nəticəyə gəlmək olar ki, əgər (1) məqsəd funksiyası üçün maksimum qiymət axtarılırsa, onda məsələnin həlli prosesində şəkil 1 – 5 - də təsvir edilmiş müxtəlif hallara rast gəlmək mümkündür. Məsələn, yuxarıda göstərildiyi kimi, şəkil 1 – də məqsəd funksiyası öz maksimum qiymətini həllər çoxbucaqlısının yeganə S kənar

nöqtəsində alır, daha doğrusu Z_max = Z(S) olur.