Qrup: 202 Müəllim

x_{i 1}+x_i2+. . . .+x_{i n}=a_i i=1,m

qədər yük daşınacaq və j-ci məntəqəyə

x_1j+x_2j+. . . .+x_mj=b_j j=1,n

miqdarda yük gətiriləcək.Bundan başqa

x_{i j} ≥0 , i=1,m , j=1,n

şərtləri ödənməlidir.Beləliklə nəqliyyat məsələsi yuxarıda göstərilən funksiyanın verilən şərtləri ödənildikdə minimallaşdırılması məsələsinə gətirilir . Göründüyü kimi bu məsələ kanonik xətti proqramlaşdırma məsələsidir:

x_ij≥0 , i=1,2,....m, j=1,2,....m

Göründüyü kimi biz nəqliyyat məsələsinin riyazi modelini qurmuş olduq.Nəqliyyat məsələsini qrafik olaraq aşağıdakı kimi təsvir edə bilərik :

İstehsal məntəqələri İstehlak məntəqələri


1

1

1
c₁₁:x₁₁

a₁ b₁

2

2

a₂ b₂

. .

. .

. .

m

n

a_m c_mn:x_mn b_n

İndi isə bu modelin həll prosesinə baxaq.Əvvəlcə bəzi anlayışları verək.

Əgər

şərti ödənərsə belə nəqliyyat məsələsi qapalı nəqliyyat məsələsi adlanır.Verilmiş şərt isə ümumi balans şərti adlanır.Əks halda nəqliyyat məsələsi açıq nəqliyyat məsələsi adlanır.Qeyd edək ki , hər bir açıq nəqliyyat məsələsi qapalı nəqliyyat məsələinə gətirilir.

Tərif

Yuxarıdakı məsələnin məhdudiyyət şərtləridəki xətti tənliklər sisteminin mənfi olmayan hər bir

x={x_ij , i=1..m, j=1..n}
həllinə nəqliyyat məsələsinin planı deyilir.

Nəqliyyat məsələsinin planlar çoxluğunda məqsəd funksiyasına ən kicik qiymət verən

x^*={x_ij^* , i=1..m, j=1..n}

planına isə bu məsələnin optimal planı deyilir.

Əvvəldə qeyd etdiyimiz kimi nəqliyyat məsələsi xətti proqramlaşdırma məsələsidir və bu məsələni də xətti proqramlaşdima məsələsinin həlli üçün universal üsul olan simpleks üsulla həll oluna bilər.Ancaq nəqliyyat məsələsi özünəməxsus xətti proqramlaşdırma məsələsidir.Məsələnin qoyuluşundan göründüyü kimi məhdudiyət şərtlərinin sol tərəfindəki əmsalladan düzəldilmiş matris 0 və 1 lərdən ibarətdir . Nəqliyyat məsələsinin yeni həll üsuluna baxaq. Nəqliyyat məsələsinin həllinin varlığı haqqında aşağıdakı teoremi qeyd edək :

Teorem

Qapalı nəqliyyat məsələsinin həli vardır.

Nəqliyyat məsələsinin həll üsulunun mahiyyəti ondan ibarətdir ki , baxılan nəqliyyat məsələsi cədvəl formasında yazılır:

İstelak məntəqələri İstehsal Nəntəqələri	B1	B2	B3	...............	Bn	Ehtiyyat
A1	c11 x11	c12 x12	c13 x13	...............	c1n x1n	a1
A2	c21 x21	c22 x22	c23 x23	...............	c2n x2n	a2
............... ...............	................ ................	............... ...............	............... ...............	................ ................	................ ................	............... ...............
Am	cm1 xm1	cm2 xm2	cm3 xm3	...............	cmn xmn	aj
Tələb	b1	b2	b3	...............	bn

Sonra qurulmuş cədvələ əsasən ilkin bazis həll yəni ilkin bazis planı tapılır.Bazis plan anlayışına və bir sıra köməkçi anlayışlara tərif verək:

Tərif

Nəqliyyat cədvəlində aşağıdakı xassəni ödəyən xanalar ardıcıllığına dövr deyilir : Bu ardıcıllığa aid olan xanalardan yalnız və yalnız ikisi bir sətirdə və ya bir sütunda ardıcıllığın axırıncı xanası isə onun birinci xanası ilə bir sətirdə və ya bir sütunda yerləşir.

Tərif:

Əgər

x={x_ij , i=1..m, j=1..n}
planı üçün elə U­_B tam xanalar çoxluğu olarsa ki
x_ij=0 , (i , j) € U_H , U_H=U \ U_B
şərti ödənilsin , onda x-ə bazis plan deyilir.Bu halda x_ij=0 , (i , j) € U_B kəmiyyətinə bazis daşınmalar , x_ij=0 , (i , j) € U_H kəmiyyətinə isə bazis olmayan daşınmalar U_B –yə x bazis planına uyğun bazis xanalar çoxluğu və U_H isə x-ə uyğun bazis olmayan xanalar çoxluğu adlanır.
Tərif :

Əgər

x={x_ij , i=1..m, j=1..n}

bazis planı üçün x_ij>0 , (i , j) € U_B , olarsa ona cırlaşmayan bazis plan deyilir.Əgər heç olmasa bir (i₀ , j₀) € U_B xanası üçün x_i0­j0=0 olarsa , onda x-ə cırlaşan bazis deyilir.

Qeyd edək ki , əgər U­_B çoxluğu (m+n-1) sayda xanadan ibarətdirsə və onun elementlərindən heç bir dövr təşkil etmək mümkün deyilsə onda U­_B tam xanalar çoxluğu adlanır.Bazis plana adətən dayaq həll deyilir.

İlkin dayaq həlli tapmaq üçün müxtəlif üsullar mövcuddur.Bu üsullardan bir neçəsini qeyd edək :

1. 
   Şimal qərb üsulu
   

Bu üsula əsasən nəqliyyat cədvəlinin şimal qərb bucağında yerləşən (1,1) xanası üçün x₁₁=min{a₁,b₁} götürülür.Əgər x₁₁=a₁ olarsa , onda birinci sətri aradan çıxarırıq və b₁ ədədini b₁-x₁₁ ilə əvəz edirik.Əks halda əgər x₁₁=b₁ onda birinci sütunu aradan çıxarırıq və a₁ ədədini a₁-x₁₁ ilə əvəz edirik.Nəticədə yeni cədvəl almış oluruq.Yeni alınmış nəqliyyat cədvəlində şimal qərb hissədə yerləşən bucağı seçirik və yuxarıda izah olunan prosesi davam etdiririk.Nəticədə m+n-1 addımdan sonra nəliyyat məsələsinin müəyyən bazis planını almış olacağıq.

2. 
   Minimal element üsulu
   

Bu üsula əsasən ən kiçik tarif dəyərə malk olan xanalar doldurulur.Bunun üçün c_ij dəyəri müqaisə olunur minimal c_i1,j1 elementi tapılır və

x_i1,j1=min{a_i1 , b_j1 }

götürülür.Əgər x_i1,j1=a_i1 olarsa , onda i₁ sətrini aradan çıxarırıq və b_j1 ədədini b_j1- x_i1,j1 ilə əvəz edirik .Əks halda əgər x_i1,j1=b_j1 olarsa , onda j₁ sütunu aradan çıxarırıq və a_i1 ədədini a_i1- x_i1,j1 ilə əvəz edirik . Nəticədə yeni cədvəl almış oluruq .Yeni alınmış nəqliyyat cədvəlində yenidən yerinə yetirdiyimiz əməliyyatları təkrarlayırıq.Nəticədə (m+n-1) sayda addımdan sonra nəqliyyat məsələsinin müəyyən bazis planı tapılır.

3. 
   Foqel üsulu
   

Əvvəlcə qeyd edək ki , Foqel üsulu şimal-qərb və minimal element üsulları ilə müqaisədə daha yaxşı başlanğıc bazis planı tapmağa imkan verir.Foqel üsulunun alqaritmi aşağıdakı addımlardan ibarətdir :

Addım 1:

Hər bir sətir üçün həmin sətirdə ən kiçik iki dəyər tapılır.Bu dəyərlərdən böyüyündən kiçiyi çıxılmaqla cərimələr hesablanır.Analoji olaraq hər bir sütunda ən kiçik dəyərlərdən böyükdən kiçiyi çıxılmaqla cərimələr hesablanır.

Addım 2

Hesablanmış cərimələrdən ən böyük cəriməyə uyğun sətir və ya sütun seçilir. Əgər sətir və ya sütun bir neçə dənədirsə onda seçim ixtiyaridir . Seçilmiş sətir və ya sütunda ən kiçik dəyərə uyğun dəyişən seçilir , tutaq ki , bu dəişən x_i1,j1-dir və həmin dəyişənə məhdudiyyət şərtlərinin ödənildiyi ən böyük qiymət mənimsədilir,yəni x_i1,j1=min{a_i1 , b_j1} götürülür . Əgər x_i1,j1= a_i1 olarsa onda i₁ sətrini cədvəldən çıxarırıq , b_j1 ədədini b_j1-x_i1,j1 ədədi ilə əvəz edirik . Əks halda əgər x_i1,j1= b_j1 olarsa onda j₁ sütununu cədvəldən çıxarırıq , a_i1 ədədini a_i1-x_i1,j1 ədədi ilə əvəz edirik . Cədvəldə saxlanılan sətir və sütuna uyğun olaraq ehtiyyac və ehtiyyata 0 qiyməti mənimsədirik.

Addım3

1. 
   Əgər cədvəldə yalnız 1 ədəd 0 qiymətli ehtiyyaca və ya ehtiyyata uğun sətir və ya sütun qalıbsa onda hesablama başa çatmış hesab olunur.
   
2. 
   Əgər cədvəldə müsbət qiymətli ehtiyyaca və ya ehtiyyata uyğun sətir və ya sütun qalıbsa onda , bu sətirdə və ya sütunda bir qədər əvvəl izah etdiyimiz minilal dəyər üsulu ilə bazis dəyişən tapılır və hesablama başa çatmış hesab olunur.
   
3. 
   Əgər cədvəldən çıxarılmamış bütün sətir və sütunlara sıfır qiymətli ehtiyyat və ehtiyyac uyğundursa onda yenə də minimal dəyər üsulunun köməyi ilə bazis dəişəni hesablanır və proses başa çatmış hesab olunur .
   
4. 
   Qalan bütün hallarda Addım1-ə qayitmaq lazımdır.
   

Görundüyü kimi Foqel üsulu bir qədər çox hesablama tələb edir. Amma Foqel üsulu digər üsullarla müqaisədə daha dəqiq başlanğıc həlli verir.Foqel üsulunun tətbiqi ilə aşağıdakı misala baxaq :

Misal1 :

Tutaq ki , müəyyən avtomobil firmasını 3 mütəlif şəhərdə avtomobil zavodları var(bu şəhərləri şərti olaraq A₁ , A₂ , A₃ ilə işarə edək) . Bu avtomobillərin 4 müxtəlif yerlərdə satış mərkəzləri var(bu satış mərkəzlərini də şərti olaraq B₁ , B₂ , B₃ , B₄ ilə işarə edək). A₁ , A₂ , A₃ zavodlarında uyğun olaraq 15,25,10 atomobil var və B₁ , B₂ , B₃ , B₄ satış məntəqələri uyğun olaraq 5,15,15,15 avtomobil satmaq imkanı var.Bir avtomobilin A₁-dən B₁-ə daşınma xərci 10 manat , A₁-dən B₂-yə 2 manat , A₁-dən B₃-ə 20 manat , A₁-dən B₄-ə 11 manat , A₂-dən B₁-ə 12 manat , A₂-dən B₂-yə 7 manat , A₂-dən B₃-ə 9 manat , A₃-dən B₁-ə 4 manat , A₃-dən B₂-yə 14 manat , A₃-dən B₃-ə 16 manat , A₃-dən B₄-ə 18 manatdır.Avtomolillərin zavodlardan satış məntəqələrinə daşınma planını elə tərtib etməli ki , daşınma xərci minimum olsun.

Göründüyü kimi bu məsələ qapalı nəqliyyat məsələsidir :15+25+10=5+15+15+15

A_i -dən(i=1,2,3) B_j-yə (j=1,2,3,4) daşınmalı olan avtomobillərin sayını x_ij ilə işarə etsək məsələnin riyazi modeli aşağıdakı kimi olar :

Z=10x₁₁+2x₁₂+20x₁₃+11x₁₄+12x₂₁+7x₂₂+9x₂₃+20x₂₄+4x₃₁+14x₃₂+16x₃₃+18x₃₄→min

x₁₁+ x₁₂+ x₁₃+ x₁₄=15

x₂₁+ x₂₂+ x₂₃+ x₂₄=25

x₃₁+ x₃₂+ x₃₃+ x₃₄=10
x₁₁+ x₂₁+ x₃₁=5

x₁₂+ x₂₂+ x₃₂=15

x₁₃+ x₂₃+ x₃₃=15

x₁₄+ x₂₄+ x₃₄=15

Məsələnin nəqliyyat cədvəlini isə aşağıdakı kimi göstərə bilərik :

	Satış mətəqələri