E 3 M ic r o s o f t E x c e l > Ч с и зД М 1
Ф ай л
(Правка
Вид
В ставка
Ф орм ат
С ервис
Д а н н ы е
Окно
С п р а вка
I
Л
[ З Ы
Л
_jp
■
Л
- У
J-гД, I
л
-'-Э
.%
-
j
' I ^ ^ -
j A rialC y 0ткр ы ть |
- 1°
-
Ж
л г
Ч
т
ш т М
-
% ООО 7
о
8 -£о !
F 1 4
-
А ___ 1
В____ !
С
D
Е
[ : :
ғ
1
G
1
х1
х 2
хЗ
1
2
1
1
1
1 .3 3 3 3 3 3 < =
2
3
4
2
1
3 < =
3
4
1
-1
2
-1 < =
-1
6
-3
2
-2
1 .8 3 3 3 3 3 < =
5
6
17
1
3
4
7
0 ,1 6 6 6 6 7
1 .1 6 6 6 6 7
0
8
9
■
10
11
1 2
13
1 4
I
1
15
т
16
Rasmdan ko'rinib turibdiki, barcha cheklanishlar bajariladi va yechim
quyidagi ko'rinishda bo'ladi:
7.3. T ransport masalasi. Potensiailar usuli.
Yuk zaxiralari
av a2,
am
bo'lgan
m
ta jo'natish punkti, yukka bo'lgan ta
lab
b,, b2,
bn
bo'lgan
n
ta qabul punktlari berilgan bo'lib, jo'natish punktlari-
dan
qabul
punktlariga
birlik
yukni
tashish
harajatlari
cv, i = \,...,m; j =\,...,n
bo'lsin. Bu yerda /-jo 'n a tis h punkti nomeri,
j
- qabul
punkti nomerini bildiradi. Umumiy yuk tashish harajatlari
г = 1 Е сл
f=l 7=1
formula orqali beriladi. Bu yerda
xf - i
nomerli jo'natish punktidan
j
nomerli
qabul punktiga tashiladigan yuk hajmi. Yuk tashish harajatlarini iioji boricha ka-
maytirish uchun
z
funksiyani minimumga intiltiramiz:
= У У
с x —> min
i—i L
_
i j
ij
i
=1 /=1
(7.7)
Yuk tashishning shunday tashkil etish kerakki, jo'natish punktlaridagi barcha
yuk olib chiqib ketilishi va qabul punktlaridagi yukka bo'lgan talab to'liq
qondirilishi kerak:
(7.8)
+ JCp + ..
= o,
x2 + X12
+
■
+ х2я = a2
xn
+
xm2
+
„
=
an
X
+ X2I +.
= b,
X
+ Jt,, + .
:+Xm2=b2
X
+ x,„ +
„
=
b„
Agar
(7.9)
(7.10)
munosabat bajarilsa, transport masalasi yopiq masala deyiladi va masalani
yechishga kirishish mumkin. Agar (7.10) shart bajarilmasa, masala ochiq deyiladi.
Ochiq masalani yechish uchun u yopiq masalagi keltiriladi. Masalan,
>
YJbl
/=1
7=1
bo'lsin. Ushbu masalani yopiq masalagi keltirish uchun yukka bo'lgan talabi
b
„.I = X ° .
bo'lgan qo'shimcha qabul punkti tuziladi. Ushbu punkt uchun
i=l
M
birlik
yukni
tashish
harajatlarini
0
ga
teng
deb
olamiz:
1 1 2
с,„+1 = с2„+| = ... = c„wl = 0 . Natijada quyidagi yopiq masalani hosil qilamiz.
Agar
X я.
bo'lsa,
yuk
zaxiralari
amA
= X ^ \ “
bo'lgan
»=l
У=1
/=1
i = l
qo'shimcha jo'natish punkti tuziladi va yuqoridagi kabi yopiq masalagi keltiriladi.
Transport masalasini yechish ikki bosqichda olib boriladi:
1)
Birinchi bosqichda (7.8)-(7.9) shartlarni qanoatlantiruvchi bosh-
lang'ich * / = 1,2.....
m; j
= 1,2...... /7 yechim topiladi. Boshlang'ich re-
jani topishning bir necha usullari bo'lib, ularga shimoli-sharq usuli,
minimal element usuli va boshqalar kiradi. Shimoli- sharq usulida
(1,1) katak tanlab olinib,
x u = min(arb j
deb
olinadi. Agar
min(al,bl) = a,
bo'lsa, bu l-jo'natish punktidagi barcha yuk 1 -qabul
punktiga yuborilishini, l-jo'natish punktidan qolgan qabul punktlariga
yuk yuborilmasligini bildiradi. Shuning uchun a, joylashgan satrdagi
boshqa kataklarga minus qo'yiladi. 1- qabul punktidagi yukka bo'lgan
talab
b] = b ,-a ,
bo'lib qoladi. Agar
min(arb[) = bl
bo'lsa, 1 - qabul
punktidagi yukka bo'lgan talab to'liq qondirilganligini, 1-jo‘natish
punktida esa a, = a, - 6 , miqdor yuk qolganligini bildiradi. 1- qabul
punktiga boshqa jo'natish punktlaridan yuk keltirilmaydi.
113
1-jadval
Qabul
punktlari
Jo 'n a tish ^ v
1
2
n
Yuk
zaxiralari
punktlari
1
c„
C,2
C,„
0
2
c 2,
c,2
C2„
a
,
m
c m 2
c_
am
Yukka bo'lgan talab
b,
b.
b,
bl
Hisoblashlarni 1-jadval bo'yicha davom ettirib, (2,1) katakka o'tamiz.
л-,, =min(a,,6,')=*,' bo‘lsin. Jadvalni yuqoridagi usul bilan to‘ldirib, quyidagini ho
sil qilamiz:
114
jadvadagi barcha
xlJt i =
= 1..... л lami aniqlaymiz. Bunda
(7.8)-(7.9)
shartlar bajarilishi kerak.
Masalaning ikkinchi bosqichida boshlang‘ich reja asosida (7.7) shartni
qanoatlantiruvchi optimal yechim topiladi. Optimal yechimni topishning potent-
siallar, taqsimot kabi bir necha usullari mavjud bo'lib, biz potentsiallar usulini
qarab chiqamiz. Ushbu usulni qarashdan oldin hisoblash jarayonida ishlatiladigan
ayrim tushunchalar bilan tanishamiz. Jadvaldagi ixtiyoriy nuqtalar to‘plami nabor
deyiladi.
Naborni tashkil qiluvchi nuqtalar har bir qatorda ikkitadan oshib ketmasa,
bunday nabor zanjir deyiladi.
_____ _____ ____________
Agar zanjir yopiq bo'lsa, u sikl deyiladi.
115
|
