Њзбекистон республикаси олий ва њрта махсус

m n
_ A_i  _B_j , (3.10)
i1 j1


m n
_ A_i  _B_j . (3.11)
i1 j1

(3.10) uchun, bunday holda masalaning matematik modeli quyidagi ko„rinishida bo„ladi:

m n
F  _C_ij X _ij  min (3.12)
i1 j1

Masalaning chegaraviy shartlari esa quyidagicha bo„ladi:

 ^X ij ^{ A}i
j1
(i  1,2,..., m)
(3.13)

_ X _ij  B_j ,
i1
( j  1,2,..., n)
(3.14)

X _ij  0, (i  1,2,..., m;
(3.11) uchun masalaning maqsad funksiyasi
j  1,2,..., n)
(3.15)

m n
F  _C_ij X _ij  min

Masalaning chiziqli sharti

i1 j1

_ X _ij  A_i ,
j1
(i  1,2,..., m)
(3.16)

_ X _ij  B_j ,
i1
( j  1,2,..., n)
(3.17)

X _ij  0, (i  1,2,..., m;
j  1,2,..., n)
(3.18)

(3.10) va (3.11) masalalar transport masalasining ochiq modellari deb ataladi. Bularni (3.6) va (3.9) holatiga keltirish uchun quyidagi (3.10) holatida «n+1» tartib raqamli iste‟molchi kiritiladi B_n+1 talabi kiritiladi, bunda

13. 
    n
    

^Bn1 ^{  A}i ^{ B}j
(3.19)

i1 j1

^Сi,n1 ^{ 0}
(3.20)

(3.11) holatida «m+1» tartib raqamli A_m+1 zapasli ta‟minotchi kiritiladi, bunda

13. 
    m
    

^Аn1 ^{ B}j ^{  A}i
(3.21)

j1 i1

^Сj,m1 ^{ 0}
(3.22)

(3.19), (3.20) yoki (3.21), (3.22) shartlar har qanday transport masalasini yopiq holatga keltiradi. Bu shuning uchunki, C_i,n+1 =0 va C_j,m+1 =0, bunda B_n+1 iste‟molchi yoki A_m+1 ta‟minotchining kiritilishi masalaning maqsad funksiyasiga hech qanday ta‟sir ko„rsatmaydi.

(3.10) uchun matritsaviy model

	B1	B2	B3	B4	...	Bj	...	Bn	^Bn+1
A1	^C11 ^X11	^C12 ^X12	^C13 ^X13	^C14 ^X14	...	^C1j ^X1j	...	^C1n ^X1n	^C1n+1 ^X1n+1
A2	^C21 ^X21	^C22 ^X22	^C23 ^X23	^C24 ^X24	...	^C2j ^X2 j	...	^C2n ^X2 n	^C2n+1 ^X2n+1
...	...	...	...	...	...	...	...	...	...
Ai	^Ci1 ^Xi1	^Ci2 ^Xi2	^Ci3 ^Xi3	^Ci4 ^Xi4	...	^Cij ^Xij	...	^Cin ^Xin	^Cin+1 ^Xin+1
...	...	...	...	...	...	...	...	...	...
Am	^Cm1 ^Xm1	^Cm2 ^Xm2	^Cm3 ^Xm3	^Cm4 ^Xm4	...	^Cmi ^Xmi	...	^Cmn ^Xmn	^Cmn+1 ^Xmn+1

(3.11) uchun matritsaviy model

	B1	B2	...	Bj	...	Bn
A1	^C11 ^X11	^C12 ^X12	...	^C1j ^X1j	...	^C1n ^X1n
A2	^C21 ^X21	^C22 ^X22	...	^C2j ^X2 j	...	^C2n ^X2 n
...	...	...	...	...	...	...
Ai	^Ci1 ^Xi1	^Ci2 ^Xi2	...	Cij ^Xij	...	Cin ^Xin
...	...	...	...	...	...	...
Am	^Cm1 ^Xm1	^Cm2 ^Xm2	...	^Cmi ^Xmi	...	^Cmn+1 ^Xmn+1
^Am+1	^Cm+1,1 ^Xm+1,1	^Cm+1,2 ^Xm+1,2	...	^Cm+1i ^Xm+1i	...	^Cm+1,n ^Xm+1,n

1. 
   teorema. (3.6)-(3.9) masala uchun [X_ij*] aniq yagona optimal reja bo„lsa, u holda (3.6)-(3.9) masalalar uchun ham optimal reja bo„ladi.
   

Isbot: 1) [X_ij*] rejaning (3.6)-(3.9) va (3.12)-(3.15) masalalari uchun optimal ekanini isbotlaymiz.
Тeoremaning shartiga asosan (3.6)-(3.9) masalasi uchun [X_ij*] optimal bo„lgan reja, u (3.12)-(3.15) masalasiga qoniqarli bo„ladi. Bundan ko„rinadiki, masalaning optimallik shartiga asosan X_ij* ning barcha qiymatlari (3.7)-(3.9) shartlarini qanoatlantiradi, demak [X_ij*] optimal rejadir, u (3.6)-(3.9) masala uchun ham qoniqarli reja bo„ladi.
(3.12)-(3.15) masalasiga qo„shimcha iste‟molchi kiritamiz (n+1) tartib raqamli, u holda (3.6)-(3.9) shartlarni quyidagicha yozamiz:

^{ X}ij ^{ X}in1 ^{ A}i
j1
(i  1,2,..., m)

 ^Xij ^{ B}j i1
( j  1,2,..., n 1)

X_ij  0
(i  1,2,..., m, j  1,2,..., n, n 1)

m

(3.9) ga asoslanib, (3.7) ni quyidagicha yozamiz

 ^X ij ^{ A}i ^{ X} in1 ^.

i1

Shunday qilib, reja ochiq transport masalasi uchun qoniqarli ekanligi isbotlandi.

2) [X_ij*] ning (3.12)-(3.15) masalasi uchun optimalligini isbotlaymiz, buning uchun (2‟) funksionalini quyidagi ko„rinishda yozamiz:

ij

ij
m n m n

^{F } ^Cij
X ^*  _C
^X ij
 min ,

i1 j 1
i1 j 1

chunki transport masalasining yopiq modeli uchun optimaldir, bundan kelib chiqadiki, [X_ij*] ochiq model uchun ham optimaldir.

(3.12)-(3.15) masalasi uchun teorema ham yuqoridagiga o„xshash isbotlanadi.

2. 
   teorema. Bir yoki bir necha iste‟molchilarning transport xarajatlarining o„zgarishi yechimning optimalligiga ta‟sir ko„rsata olmaydi.
   

Isbot. Iste‟molchilardagi transport xarajatlari quyidagi ko„rinishda o„zgarsin, deb faraz qilaylik:

ij

ij
С¹  C
  _j ,
 _j  0,
( j  1,2,..., n)
(3.23)

Faraz qilaylik [S_ij] transport xarajatlariga ega bo„lgan masala uchun [X_ij*] optimal bo„lsin va xuddi shu masala uchun X_ij qandaydir qoniqarli reja bo„lsin. Bundan quyidagi kelib chiqadi:

m n m n

_C¹ X ^*  _C¹ X
(3.24)

ij ij ij ij
i1 j 1 i1 j 1

(3.23) ga asosan (3.24) ni quyidagicha yozish mumkin:

ij

ij
m n m n

^(Cij
  _j
)X ^*  _(C
  _j
) X _ij

i1 j 1
i1 j 1

Agar qavsni ochsak, quyidagiga ega bo„lamiz:

m n m n m n m n

^C
X ^*  _ X ^*  _C X
 _ X
(3.25)

i1
ij ij
j 1


i1
i ij
j 1


i1
ij ij
j 1


i1
i ij
j 1

Bundan kelib chiqadiki, X_ij* va X_ij ning qiymatlari masalaning shartlarini qanoatlantiradi, demak,

 ^X ij j 1
 A_i



^va  ^X ij i1
 B_j
bo„ladi.

n
Shunday qilib,

_
j 1



j  ^X ij i1

 _ _j j 1

m

_ X  0
*
ij
i1

bo„ladi, unda (3.25) quyidagi ko„rinishda yoziladi:

ij

ij
m n m n

^Cij
X ^* _C
^X ij
. (3.26)

i1 j 1
i1 j 1

Demak, [X_ij*] optimal reja, chunki u masalaning shartlarini qanoatlantirdi [X_ij] reja shartiga asosan qoniqarlidir.

3. 
   teorema. Bir yoki bir necha ta‟minotchilardagi transport xarajatlarining o„zgarishi yechimning optimalligiga ta‟sir ko„rsatmaydi.
   

Isbot. Тa‟minotchilardagi transport xarajatlari quyidagi shaklda o„zgarsin, deb
faraz qilaylik:

ij

ij
C¹  C
 _i ,
_i  0,
 j  1,2,..., n

Faraz qilaylik, [X_ij*] optimal reja, u holda [X_ij] qoniqarli bo„lgan rejadir (transport xarajatlariga ega bo„lgan transport masalasining yopiq modeli uchun), unda maqsad funksiyasi quyidagicha bo„ladi:

m n m n

_C¹ X ^* _C¹ X
(3.27)

ij ij ij ij
i1 j 1 i1 j 1

(3.26) ga asosan (3.27) ni quyidagicha yozamiz:

m n m n

_(C   ) X ^* _(C
  ) X ,

qavslarni ochamiz:

i1
ij
j 1

9. 
   ij
   

i1
ij
j 1

9. 
   ij
   

ij

ij

j

ij
m n m n m n m n

^Cij
X ^*  _
X ^* _C
^X ij
^ ^i ^X ij ^.

i1 j 1
i1 j 1
i1 j 1
i1 j 1

Masalaning shartlariga asosan:

ij

ij

ij
m n m n m n n

^Cij
X ^* _C
^X ij
^ ^i ⁽ ^X ij
_ X ^* )
(3.28)

i1
j 1
i1
j 1
i1
j 1
j 1

Shunday qilib, ko„rib chiqilayotgan transport masalasining yopiq modeli shartlariga asosan:

m
_ X ^*  A

(i  1, m) ,

ij i
i1
m

Bundan kelib chiqadi:

 ^X ij ^{ A}i
i1
(i  1,2,..., m) .

m _ n _* n _
^i ^ ^X ij ^  ^X ij ^{  0 .}

i1
_ j 1
j 1 _

Bundan (3.28) o„rniga qo„ysak,



ij

ij
m n m n

^Cij
X ^* _C
^X ij

i1 j 1
i1 j 1

bo„ladi. Shunday qilib [X_ij*] reja [S_ij] transport xarajatlariga ega bo„lgan masala uchun optimal ekani isbotlandi.

Sanoat korxonalarida bir xildagi yuklarni transportda tashish masalasini ko„rib chiqamiz
Masala. Berilgan m punktda bir xildagi mahsulotlar miqdori A₁, A₂ va A_m bo„lsin. U holda n ta punktda B₁, B₂,..., B_n mahsulotlar miqdori talab qilinsin. Ular orasidagi transport xarajatlarini C_mn bilan belgilaymiz. Masalaning berilishi va uning matritsaviy modelini quyidagicha yozamiz:

	B1	B2	...	Bj	...	Bn
A1	^C11 ^X11	^C12 ^X12	...	^C1j ^X1j	...	^C1n ^X1n
A2	^C21 ^X21	^C22 ^X22	...	^C2j ^X2 j	...	^C2n ^X2 n
...	...	...	...	...	...	...
Ai	^Ci1 ^Xi1	^Ci2 ^Xi2	...	^Cij ^Xij	...	^Cin ^Xin
...	...	...	...	...	...	...
Am	^Cm1 ^Xm1	^Cm2 ^Xm2	...	^Cmi ^Xmi	...	^Cmn ^Xmn

Bunda:
A_i - i-tartib raqamli ta‟minotchidagi yukning miqdori (i=1, 2,..., m); B_j - j-tartib raqamli iste‟molchining talabi, (j=1, 2, ..., n);

C_ij - i-tartib raqamli ta‟minotchidan j-tartib raqamli iste‟molchiga yuk olib borishga sarflangan transport xarajatlari;
X_ij - i-tartib raqamli ta‟minotchidan j-tartib raqamli iste‟molchiga olib boriladigan yukning hajmi.
Masalaning matematik modeli quyidagicha bo„ladi:


m n
F  _C_ij X _ij  min (3.29)
i1 j 1

Masalaning chiziqli sharti

 ^X ij ^{ A}i
j 1
(i  1,2,..., m) , (3.30)

 ^{X ij  Bj} i1


^{( j  1,2,..., n)} , (3.31)

Agar
X _ij  0
(i  1,2,..., m;
j  1,2,..., n) . (3.32)

m n
 ^Ai ^  ^Bj
i1 j 1

bo„lsa, unda (3.30) tengsizlik qat‟iy tenglikka aylanadi:

bunda



_ X _ij  A_i ,
j 1
i  1,2,..., m

m n

^{F } ^Cij ^X ij
 С₁₁ X₁₁  C ₁₂ X₁₂  ...  C_1n X_1n  ...  C_mn X _mn  min

i1 j 1

Bu masalani yechish uchun transport masalalarini yechish usullarining biridan foydalanish mumkin. Olingan yechimni tahlil qilish yoki olingan rejaning haqiqiyligini hal qilish shart. Agar yuk tashish rejasi haqiqiy bo„lib chiqsa, bu reja boshlang„ich ma‟lumotlar to„g„ri yig„ilganligini isbotlaydi. Agar yuk tashish rejasi real bo„lmasa, boshlang„ich ma‟lumotlarni yig„ishda xatoga yo„l qo„yilgan bo„ladi, u holda boshlang„ich ma‟lumotlarni o„zgartirish kerak bo„ladi.