Mövzu 14: Qapalı nəqliyyat məsələsinin potensiallar üsulu ilə həlli

Məhsulları istehlakçılara daşımaq üçün elə bir plan tapmaq lazımdır ki, bu plana
görə bütün məntəqələrdə olan məhsullar tam daşınsın, istehlakçıların tələbləri tam ödənsin
və daşınmalara sərf ediləcək məcmu nəqliyyat xərcləri minimum olsun.
Həlli:
=
= 1000
( ) = 3
+ 7
+ 2
+ 6
+ 4
+ 5
+ 3
+ 8
+ 3
+ 9
+ 6
+ 5
+ 9
+ 2
+ 7
→
+
+
+
+
= 200
+
+
+
+
= 500
+
+
+
+
= 300
⎩
⎪
⎨
⎪
⎧
+
+
= 150
+
+
= 170
+
+
= 240
+
+
= 280
+
+
= 160
≥ 0, … … ,
≥ 0
Hazırlıq mərhələsi ən kiçik element üsulu ilə aparılmış və
=
0
0
200 0 0
150 170 40 0 140
0
0
0 280 20
( ) = 3940 pul vahidi.
– da
= + − 1 = 3 + 5 − 1 = 7 sayda sıfırdan böyük element olmalıdır.
Bu şərt ödənilir və
matrisi cırlaşmış daşınmalar planıdır. Odur ki, məsələnin həllini
davam etdirək.
=
− ( − )
,
matrisin tərtib edək.
Bu məqsədlə
daşınmalar matrisinin sətir və sütun potensiallarının qiymətlərini
hesablamaq lazımdır. Bunun üçün
– da
> 0 elementləri üçün
−
=
tənlikləri tərtib ediir və onların bazasında aşağıdakı tənliklər sistemi qurulur.
⎩
⎪
⎪
⎨
⎪
⎪
⎧
−
= 2
−
= 5
−
= 3
−
= 8
−
= 9
−
= 2
−
= 7
– da r = 7 olduğu üçün burada 7 xətti tənlik və 8 məchul vardır. Odur ki, bu
sistemi həll etmək üçün məchullardan hər hansı birinə ixtiyari qiymət vermək lazımdır.
Tutaq ki,
= 0 . Onda alarıq:
downloaded from KitabYurdu.org

 matrisini quraq:
Göründüyü kimi, matrisinin bir elementi mənfidir. Deməli, daşınmalar matrisi
baxılan nəqliyyat məsələsinin optimal planı qurmaq lazımdır.
1 – ci yaxınlaşma: 1 – ci mərhələ. Bu mərhələyə ehtiyac yoxdur, çünki,
daşınmalar matrisin məsələsinin optimal olmadığı artıqməlumdur.
2 – ci mərhələ: daşınmalar matrisində daşınmalar matrisinə keçək:
daşınmalar matrisi üçün:
2 – ci yaxınlaşma: 1- ci mərhələ daşınmalar matrisinin optimal olub – olmadığını
müəyyən etmək üçün matrisindən matrisinə keçək.
– nin heç bir elementi mənfi deyil. Deməli – optimalplandır və bu plana görə
– dür
Beləliklə, 1 – ci məntəqə bütün məhsulunu 3 – cü istehsalçıya göndərilməlidir. 2 –
ci məntəqə 1 – ci istehlakçıya 150t, 2 – ciyə 170t, 3 – üncüyə 40t və 4 – cüyə 140t məhsul
göndərməlidir. 3 – cü məntəqə isə 4 – cü istehlakçıya 140t və 5 – ci istehlakçıya 160t
məhsul göndərməlidir.
downloaded from KitabYurdu.org

200 500 300
150 170 240 280 160
: =
0
0
200 0 0
150 170
40 140 0
0
0
0 140 160
Olduqda
min (
∗
) = 3800
.
downloaded from KitabYurdu.org

Mövzu 15: Açıq nəqliyyat məsələsinin həll alqoritmi
Fərz edək ki,
, , ə müəssisələrində
= 200 ,
= 300 ,
=
500 ,
= 300 eyniadlı məhsul vardır. Bu məhsulları
, , istehlak
məntəqələrinə daşımaq lazımdır. Istehlakçıların tələbləri uyğun olaraq
= 260 ,
=
370 ,
= 390 – dur. Məhsul vahidlərinin müxtəlif kommunikasiyalar üzrə daşınma
xərcləri aşağıdakı nəqliyyat xərcləri matrisi ilə verilmişdir.
=
3 7 2
4
7
4
9
3
4
5
9
8
Məhsulların istehlakçılardan istehsalçılara daşımaq üçün elə bir plan tapmaq
lazımdır ki, bu plana görə nəqliyyat xərclərinin cəmi minimum olsun.
Həlli: Məsələ
= 1300 ,
= 1020 olduğu üçün açıq nəqliyyat məsələsidir − dir.
( ) = 3
+ 7
+ 2
+ 4
+ 9
+ 5
+ 7
+ 3
+ 9
+ 4
+ 4
+ 8
+
+
≤ 200
+
+
≤ 300
+
+
≤ 500
+
+
≤ 300
+
+
+
= 260
+
+
+
= 370
+
+
+
= 390
≥ 0,
≥ 0, … ,
≥ 0
>
olduğu üçün bu məsələni qapalı şəkilə gətirmək üçün
şərti
istehsalçı qəbul edilir və onun məhsula olan tələbi
=
−
= 1300 − 1020 = 280
Bu halda həm C nəqliyyat xərcləri matrisinə, həm də X daşınmalar matrisinə 4 – cü
sütun əlavə ediləcəkdir.
=
3 7 2 0
4 9 5 0
7
4
3
4
9 0
8 0
; =
Onda açıq nəqliyyat məsələsi aşağıdakı klassik qapalı nəqliyyat məsələsinə
gələcəkdir.
downloaded from KitabYurdu.org

+
+
+
= 200
+
+
+
= 300
+
+
+
= 500
+
+
+
= 300
+
+
+
= 260
+
+
+
= 370
+
+
+
= 390
+
+
+
= 280
≥ 0;
≥ 0; … ;
≥ 0
Bu məsələni potensiallar üsulu ilə həll edən ən kiçik element üsulu ilə daşınmalar
matrisini tərtib edək:
( )
=
0
0
200 0
260
0
40 0
0
0
370
0
130 0
20 280
( )
= 4080
Bu matrisdə
=
+ − 1 = 4 + 4 − 1 = 7 olduğundan məsələnin həllini
davam etdiririk.
=
− ( − )
,
⎩
⎪
⎪
⎨
⎪
⎪
⎧
−
= 2
−
= 4
−
= 5
−
= 3
−
= 9
−
= 8
−
= 0
= 0
= −3
= −7
= −6
= 1
= −4
= 2
= −6
=
2
11
0 6
0
10 0 3
−1
−3
0
2
0
0
−1
0
∆
Göründüyü kimi
– də mənfi elementlər var. Deməli
( )
– optimal plan deyil və
1- ci yaxınlaşmaya keçib yeni daşınmalar planı qurmaq lazımdır.
1 – ci yaxınlaşma: 1 – ci mərhələ: Bu mərhələyə ehtiyac yoxdur, çünki
( )
daşınmalar matrisinin məsələsinin optimal planı olmadığı artıq məlumdur.
2 – ci mərhələ:
( )
daşınmalar matrisindən
( )
matrisinə keçək:
( )
=
0
0
200 0
260
( )
0
40
( )
0
0
0
( )
370
0
130 0
20
( )
280
( )
=
0
0
200 0
240
0
60 0
0
20
370
0
130 0
0 280
( )
= 4020
downloaded from KitabYurdu.org

2 – ci yaxınlaşma: 1 – ci mərhələ:
( )
daşınmalar matrisinin optimal olub –
olmadığını yoxlayaq:
=
2
11
0 6
0
10 0 3
−1
−3
0
2
0
0
−1
0
=
2
11
0 3
0
10 0 0
−1
0
0
5
0
3
−4
0
∆
Göründüyü kimi
( )
daşınmalar matrisi də optimal plan deyil.
2 – ci mərhələ:
( )
– dən
( )
- ə keçək:
( )
=
⎝
⎛
0
0
200 0
240
( )
0
60 0
0
20
( )
370
0
130 0
( )
0 280
( )
⎠
⎞
( )
=
0
0
200 0
110
0
190 0
0
150
370
0
0 130
0 150
( )
= 3500
3 – cü yaxınlaşma: 1 – ci mərhələ:
( )
– in optimal olub – olmadığını yoxlayaq:
=
2
11
0 3
0
10 0 0
−1
0
0
5
0
3
−4
0
+4
=
2 7 0 3
0 6 0 0
3
0
0
1
4
3
0
0
– ün heç bir elementi mənfi deyil. Deməli
( )
– optimal plandır.
( )
=
0
0
200 0
110
0
190 0
0
150
370
0
0 130
0 150
downloaded from KitabYurdu.org

( )
= 3500
Indi isə qapalı nəqliyyat məsələsinin optimal həllindən açıq nəqliyyat məsələsinin
optimal həllini tapaq:
Bu məqsədlə
( )
daşınmalar matrisində 4 – cü sütunu silmək kifayətdir.
( )
=
0
0
200
110
0
190
0
150
370
0
0
0
min (
) = 3500
downloaded from KitabYurdu.org

Mövzu 16: Tam ədədli XP məsələsi
Tamədədli XP məsələsinin və onun həllər çoxluğunun tapılmasının həndəsi
izahı xüsusi maraq kəsb edir. Məlum olur ki, XP məsələsinin həllər çoxluğu
tamədədli kənar nöqtələrə malik olan çoxbucaqlıdan və ya çoxüzlüdən ibarətdir ki,
o da qabarıq çoxluq olmaya da bilər.
Bilməliyik ki, Qomori üsuluyaxud kəsmə üsulu TXP məsələsinin həlli
məqsədilə işlənilmiş əsas alqoritmlərdən biridir və o, mahiyyatə müvafiq XP
məsələsinin həlli üçün tətbiq edilən Simpleks üsulu ilə bilavasitə əlaqədardır.
Məchulları üçün yalnız tam ədədli qiymətlər axtarılan riyazi
proqramlaşdırma məsələsinə tam ədədli proqramlaşdırma məsələsi deyilir.
Tam ədədli proqramlaşdırma məsələsinin riyazi qoyuluşunda həm məqsəd
funksiyası, həm də məhdudiyyət şərtləri xətti, qeyri - xətti və qarışıq şəkildə verilə
bilər. Əgər tam ədədli proqramlaşdırma məsələsində məqsəd funksiyası və
məhdudiyyət şərtləri xətti olarsa, ona tam ədədli xətti proqramlaşdırma məsələsi
deyilir. Əks halda, yəni asılılıqlardan heç olmazsa biri qeyri – xətti olarsa, ona tam
ədədli qeyri – xətti proqramlaşdırma məsələsi deyilir. Xətti proqramlaşdırma
məsələsindən fərqli olaraq, tam ədədli xətti proqramlaşdırma məsələsinə əlavə
şərtlər daxi edilir ki, onlar da optimal həlldə məhculların qiymətlərinin mənfi
olmayan tam ədədlərdən ibarət olmasını tələb edirlər.
Tərif 1: Aşağıdakı şəkildə verilmiş xətti proqramlaşdırma məsələsinə:
Məqsəd funksiyası
( ) =
→ max(
) (1)
Məhdudiyyət şərtləri
= = 1, (2)
≤ = + 1,
(3)
≥ 0 ( = 1, ) (4)
, ( = 1, , ≤ ) (5)
Tam ədədli xətti proqramlaşdırmanın ümumi məsələsi deyilir.
Tərif 2: Əgər
= olarsa, onda (1) – (5) – məsələsi bütövlükdə tam ədədli
xətti proqramlaşdırma məsələsi adlanır.
Əgər müvafiq xətti proqramlaşdırma məsələsi üçün tapılmış həllin
komponentləri tam ədədli deyildirsə, bu zaman onları yaxın tam ədədlərə qədər
downloaded from KitabYurdu.org

yuvarlaqlaşdırmaq olar. Bu üsullardan o vaxt istifadə edilir ki, məcmunun ayrıca
vahidi bütün məcmu həcminin bir hissəsini təşkil edir.
Doğrudan da, ekstremum məsələnin məhdudiyyətlər sistemində məchulların
tam ədədli olması şərtlərindən irəli gələn prinsipial çətinlik ondan ibarətdir ki,
əksər hallarda tam ədədli xətti proqramlaşdırma məsələsini onun kəsilməz analoqu
ilə əvəz etmək və müvafiq həlli tapdıqdan sonra onun komponentlərini yaxın tam
ədədlərə qədər yuvarlaqlaşdırma mümkün olmur.
Misal üçün fərz edək ki, ikiölçülü xətti proqramlaşdırma məsələsinin qrafik
üsulla həlli nəticəsində onun tam ədədli olmayan
∗
= (
∗
;
∗
)..... optimal həlli
tapılmışdır. Şəkil 1 – dən görünür ki,
∗
optimal həllini yaxın tam ədədlərə qədər
yuvarlaqlaşdırdıqda
([
∗
]; [
∗
]) nöqtəsi alınır ki, bu da xətti proqramlaşdırma
məsələsinin G mümkün həllər çoxluğuna daxil deyildir.
......
.....
Qeyd edək ki, kəsilməz xətti proqramlaşdırma məsələsinin optimal həllinin
komponentlərini tam ədədlərə qədər yuvarlaqlaşdırdıqda o, mümkün həll də ola
bilər. Lakin bu zaman tam ədədli xətti proqramlaşdırma məsələsinin məqsəd
funksiyasının optimal həlldəki ekstremum qiyməti ilə müqayisə onun tapılmış
mümkün həlldəki qiyməti kifayət qədər pis ola bilər.
Yuxarıda göstərilmiş problemlər, qrafik üsulla yanaşı tam ədədli xətti
proqramlaşdırma məsələsinin həlli üçün xüsusi üsullarında işlənib hazırlanması
zəruriyyətini yaradırlar.
Tam ədədli xətti proqramlaşdırma məsələsinin həndəsi izahı, bir sıra
fərqləndirici xüsusiyyətlər nəzərə almaqla, müvafiq ölçüyə malik xətti
proramlaşdırma məsələsində olduğu kimi verilir. Onun həlli qrafik üsulun tətbiqi
adətən məsələyə iki, yaxud üç məchul daxil olduqda yerinə yetirilir.
Fərz edək ki, “max” tam ədədli xətti proqramlaşdırma məsələsi verilmişdir
və burada məchulların sayı 2 – yə bərabərdir. Onda məsələni qrafik üsulla həll
etmək olar və bu məqsədlə onun həndəsi izahını nəzərdən keçirək. Burada ilkin
olaraq məchulların tam ədəli olması şərtləri nəzərə alınmadan müvafiq “max” xətti
proqramlaşdırma məsələsi qrafik üsulla həll edilir. Tutaq ki, onun mümkün həllər
çoxbucaqlısı tapılmışdır. (şəkil 2)
...............
...............
Şəkil 2. – dən göründüyü kimi xətti proqramlaşdırma məsələsinin məqsəd
funksiyası öz ektremum qiyməti tam ədədli olmayan B kənar nöqtəsində alır. Yəni
= ( )
.
Bununla bərabər, əgər məchulların qiymətləri üzərində qoyulmuş tam ədəli
şərtlərini nəzərə alsaq, onda tam ədədli xətti proqramlaşdırma məsələsinin
downloaded from KitabYurdu.org

mümkün həllər çoxluğu yalnız tam ədəli koordinatlara malik 17 dənə təcrid edilmiş
nöqtələr məcmusundan ibarət olur və bu çoxluq qabarıq deyilir. Ona görə də
verilmiş tam ədədli xətti proqramlaşdırma məsələsinin optimal həllini təyin edən
ekstremum nöqtəni tapmaq üçün
çoxbucaqlısı bütün tam ədəli nöqtələrin
daxil olduğu yeni
çoxbucaqlısı ilə əvəz olur. Nəticədə alınmış
çoxbucaqlısının kənar nöqtələrindən hər birinin koordinatları da tam ədədlərdən
ibarət olacaqdır.
≤
oxşar qayda ilə
≥
downloaded from KitabYurdu.org

Mövzu 17: Qomori metodu
Bu üsul tam ədədli xətti proramlaşdırma məsələsinin həlli üçün tətbiq edilən ən
əlverişli üsuldur və onun əsasını simpleks üsulu təşkil edir. Qomori üsulunu həmçinin
kəsmə üsulu da adlandırırlar. Onun mahiyyəti bundan ibarətdir ki, əvvəlcə ilkin tam
ədədli xətti proramlaşdırma məsələsində məchulların tam ədədli olması şərtləri nəzərə
alınmır və onun analoqu olan xətti proramlaşdırma məsələsinin optimal həlli tamədədli
olarsa, onda bu həm də ilkin tam ədədli xətti proramlaşdırma məsələsi üçün optimal həll
qəbul edilir. Əgər həll tamədədli deyildirsə, onda xətti proramlaşdırma məsələsinin
məhdudiyyət şərti (kəsmə şərti) daxil edilir.
Tərif: Aşağıdakı xassələrə malik olan əlavə məhdudiyyət şərtinə düzgün kəsik
deyilir.
– O xətti olmalıdır;
– O tapılmış tamədədli olmayan optimal həlli kəsməlidir;
– O heç bir tamədədli həlli kəsməməlidir.
Daha sonra əlvə məhdudiyyət şərti daxil olan yeni genişləndirilmiş xətti
proramlaşdırma məsələsi həll edilir. Əgər onun optimal həlli tamədədli olarsa, o həm də
verilmiş tam ədədli xətti proramlaşdırma məsələsinin opimal həlli olur. Əgər bundan
sonra da optimal həllin bütün məchulları üçün tamədədlilik şərti ödənilmirsə, onda yeni
kəsmə şərti daxil edilir və s.
Qeyd edək ki, əgər tam ədədli xətti proramlaşdırma məsələsinin həlli vardırsa,
onda kəsmə şərtləri elə seçilməlidir ki, sonlu sayda addımlardan sonra tamədədli optimal
həll alınmış olsun. Bu kimi kəsmə şərtlərinin qurulması alqoritmi Qomori tərəfindən
təklif edilmişdir. Bu alqoritmin mahiyyətini nəzərdən keçirək.
Tutaq ki, tam ədədli xətti proramlaşdırma məsələsi aşağıdakı şəkildə verilmişdir.
Məqsəd funksiyası
( ) =
→ max (1)
Məhdudiyyət şərtləri
≤ , ( = 1, ) (2)
≥ 0,
( = 1, ) (3)
− tam ədədlərdir.
, , … ,
əlavə mənfi olmayan məchullarını daxil etməklə
(1) − (3)
məsələsini kanonik şəkilə gətirək:
Məqsəd funksiyası
downloaded from KitabYurdu.org

( ) =
→ max (4)
Məhdudiyyət şərtləri
+
≤ , ( = 1, ) (5)
≥ 0,
( = 1, ) (6)
≥ 0,
( = 1, ) (7)
ə − tam ədədlərdir. (8)
Beləliklə,
(1) − (3) ilkin tam ədədli xətti proramlaşdırma məsələsinə asılı
məchullar daxil edilir ki, onlar da
= −
+
≥ 0 , ( = 1, ) (9)
şərtlərini ödəyirlər
Aydındır ki,
(1) − (3) və (4) − (8) məsələləri ekvivalentdirlər. Alınmış (4) − (8)
kanonik tam ədədli xətti proramlaşdırma məsələsinin Qomoriu üsulu ilə həlli alqorimi iki
əsas mərhələdən ibarətdir. İlkin addım və ümumi (təkrarlanan) addım.
İlkin addım. Burada
(4) − (7) məsələsi Simpleks üsulu ilə həll edilir, yəni
məchulların
(8) tamədədli olmaı şərtləri nəzərə alınmır.
Məsələyə baxaq:
Məqsəd funksiyası
( ) = 4 + 5 → max (1`)
Məhdudiyyət şərtləri
3 + 2 ≤ 10 ( )
+ 4 ≤ 11 ( )
3 + 3 ≤ 13 ( )
≥ 0 ,
≥ 0 (3
`
)
,
− tam ədədlərdir.
Alınmış
1
`
− (3
`
) tam ədədli xətti proramlaşdırma məsələsinin həllinə
keçməmişdən əvvəl, onu kanonik şəkilə gətirək:
Məqsəd funksiyası
( ) = 4 + 5 → max (1``)
Məhdudiyyət şərtləri
3 + 2 +
≤ 10
+ 4 +
≤ 11
3 + 3 +
≤ 13
(2``)
≥ 0 ( = 1,2) (3``)
downloaded from KitabYurdu.org

≥ 0 ( = 1,2,3)
( = 1,2) ə ( = 1,2,3) − tam ədədlərdir.
= 3 + 2 + 10 ≥ 0
=
+ 4 + 11 ≥ 0
= 3 + 3 + 13 ≥ 0
(4``)
1
"
− (3
"
) tam ədədli xətti proramlaşdırma məsələsini Qomori üsulu ilə həll edək.
İklin addım:
4
"
− nəzərə almaqla 1
"
− 3
"
"max" xətti proramlaşdırma
məsələsini Simpleks cədvəli şəklində göstərək:
− − ↓
J
=
3
2
10
→
=
1
4
11
=
3
3
13
=
-4
-5
0
İki addım tətbiq etməklə bu cədvəldən ardıcıl olaraq aşağıdakı cədvəlləri alarıq.
vdvsd
Buradan
"max" xətti proramlaşdırma məsələsinin optimal həllini tapırıq, yəni
∗
=
∗
=
18
10 ;
∗
=
23
10
ə
( ) = (
∗
) =
187
10
.
Bu tapılan həll tamədədli olmadığı üçün ümumi addıma keçmək lazımdır.
− ↓ −
J
→
= 10/4 −2/4
=
1/4
1
=
9/4 −3/4
=
−
− ↓
−
J
→
=
10/4
−2
/10
=
−1/10 3/10
=
−9/10 −3
/10
=
downloaded from KitabYurdu.org

Mövzu 18: Parametrik xətti proqramlaşdırma məsələsi
Məlumdur ki, xətti proqramlaşdırmanın ümumi məsələsinə sabit kəmiyyətlər
daxildir. Bunlar
,
ə səbəst hədlərdir. Bir tərəfdən bu kəmiyyətlərin təyinində
praktikada rast gəlirik ki, onlar sabit deyillər. Onların qiymətləri hər hansı intervalda
dəyişirlər. Digər tərəfdən optimal planın tapılmasında (bir sıra iqtisadi məsələlərdə) qeyd
olunmuş
, , qiymətlərində (təcrübədən alınmış) bilmək zəruridir ki, bunları hanı
mümkün olan intervalda dəyişmək olar ki, plan optimal olsun.
Buna görədə belə bir zərurət yanarır ki, xətti proramlaşdırma məsələsinin optimal
həllinin tədqiqində onun amsallarının dəyişməsi və sərbəst hədlərin dəyişməsi
araşdırılmalıdır. Oxşar tipli tədqiqat parametrik xətti proramlaşdırma məsələsinin

Download 0.55 Mb.