Transport masalasi va uning matematik modelini tuzish Reja

Transport masalasining umumiy qo‘yilishi (minimal qiymat mezoni bo‘yicha) quyidagicha: A₁, A₂, .... A_n punktlarda (ta’minotchilarda) mos ravishda a₁, a₂, ..., a_n miqdorda bir xil yuklar bor. Bu yuklarga bo‘lgan extiyoji mos ravishda b₁, b₂, ...b_m bo‘lgan V₁, V₂, .... V_m punktlarga (iste’molchilarga) yuklarni shunday tashish talab etiladki: natijada tashish uchun ketgan umumiy harajat minimal bo‘lishi kerak.
A_i dan V_j ga bir birlik yukni tashish harajati S_ij ni tashkil etadi. Shu bilan birga yuklarni teskari tashish man etiladi, ta’minotchilarning yuklarni tula tashib ketilishi va iste’molchilarning talabi to‘la qanoatlantirilishi talab qilinadi.
Yuk tashishda qilinadigan xarajatlarni minimallashtirish optimallik mezonini ifodalaydi.
2. Masalani yopiq modeli haqida tushuncha. Masalani ochiq modeli va uni yopiq modelga keltirish yo‘llari.
O‘zgaruvchilarni quyidagicha belgilaymiz. x₁₁-bilan, A₁ ta’minotchidan V₁ iste’molchiga; x₁₂ - bilan, A₁ ta’minotchidan V₁ iste’molchiga; x₁₃ - bilan, A₁ ta’minotchidan V₃ iste’molchiga ,..., x_1n- bilan, A₁ ta’minotchidan V_m iste’molchiga junatiladigan yuklar miqdori; x₂₁ - bilan, A₁ ta’minotchidan V₁ iste’molchiga; x₂₂ - bilan, A₂ ta’minotchidan V₂ iste’molchiga; x₂₃ - bilan, A₂ ta’minotchidan V₃ iste’molchiga ,..., x_2n - bilan, A₂ ta’minotchidan V_m iste’molchiga junatiladigan yuklar miqdori; x_m1 - bilan, A_n ta’minotchidan V₁ iste’molchiga; x_m2 - bilan, A_n ta’minotchidan V₂ iste’molchiga; x_m3 - bilan, A_n ta’minotchidan V₃ iste’molchiga ,..., x_1n - bilan, A_n ta’minotchidan V_m iste’molchiga junatiladigan yuklar miqdori;
Bu masalaning matematik modelini tuzish uchun o‘zgaruvchilarni, ya’ni i - ta’minotchidan j - iste’molchiga tashilishi kerak bo‘lgan yuk miqdorini x_ij deb belgilab olsak, u holda quyidagicha ifodalanadi: x_ij larning shunday qiymatlari topilsinki, natijada maqsad funksiya - tashish uchun ketgan umumiy harajat,
Z_min=s₁₁x₁₁+s₁₂x₁₂+....+s_1mx_1m+s₂₁x₂₁+s₂₂x₂₂+...+s_2mx_2m+....+s_n1x_n1+s_n2x_n2+s_n3x_n3+....+s_nmx_nm .
yoki Z= s_ij s_{ij min} (1)
bo‘lsin va yuklarning to‘la tashilib ketilish shartini:
x₁₁ + x₁₂ + ... + x_1m= a₁
x₂₁ + x₂₂ + ... + x_1m= a₂ (2)
. . . . . . . . . . .
x_n1 + x_n2 + ... + x_nm =a_n .
iste’molchilar talablarining to‘la qanoatlantirilishi shartini:
x₁₁ + x₂₁ + ... + x_n1 = b₁ ,
x₁₂ + x₂₂ +…+ x_n2 = b₂ (3)
. . . . . . . . . . . .
x_1m + x_2m + ...+ x_nm =b_n .
x _ij ≥ 0 i=1,n ; j= 1,m . (4)
o‘zgaruvchilarning nomanfiylik sharti (yoki yuklarning teskari tashilmaslik sharti) ni qanoatlantirsin.
Agar a₁, a₂, ..., a_n yuklarning yig‘indisi, bu yuklarga bo‘lgan ehtiyojlari b₁, b₂, ...,b_m ning umumiy yig‘indisiga teng bo‘lsa,
a₁+ a₂+ ...+ a_n =b₁+ b₂ +...+b_m
yoki a_i = b_j (5)
bo‘lsa transport masalasi yopiq, aks holda ochiq deyiladi.
Ochiq tipdagi masalalar yopiq tipdagi masalaga soxta punkt kiritish yo‘li bilan amalga oshiriladi.
Agar a₁, a₂, ..., a_n yuklarning yig‘indisi, bu yuklarga bo‘lgan ehtiyojlari b₁, b₂, ...,b_m ning umumiy yig‘indisidan katta bo‘lsa, ya’ni:
a₁+ a₂+ ...+ a_n >b₁+ b₂ +...+b_m
yoki a_i > b_j (6)
bo‘lsa modelga V_m+1 soxta qabul punkti kiritiladi, uning yuklarga bo‘lgan extiyoji:
b_m+1= a_i - b_j (7)
va tashish harajati s_im+1=0 (i=1, n), bo‘ladi.
Agar a₁, a₂, ..., a_n yuklarning yig‘indisi, bu yuklarga bo‘lgan ehtiyojlari b₁, b₂, ...,b_m ning umumiy yig‘indisidan kichik bo‘lsa,
a₁+ a₂+ ...+ a_n < b₁+ b₂ +...+b_m
yoki a_i < b_j (8)
bo‘lsa A_n+1 soxta jo‘natish punkti kiritilib undagi yuk miqdori,
a_m+1= b_j - a_i (9)
tashish qiymati S_n+1j = 0 (j = i, m) bo‘ladi.
Shunday qilib transport masalasi chiziqli dasturlash masalasining xususiy holi bo‘lib, u ko‘yidagi xususiyatlarga ega :
∙ chegara shartlari tenglamalar bilan ifodalaniladi;
∙ o‘zgaruvchilar oldidagi koeffisiyentlar 0 yoki 1 ga teng;
∙ har bir o‘zgaruvchi faqat ikkita tenglamada uchraydi.
3. Masalani matritsaviy modelini tuzish.
Transport masalasining matritsaviy modeli quyidagi ko‘rinishda bo‘ladi:

j i	B1	B2	...	Bj	...	Bn
A1	t 11 X11	t 12 X12	...	t 1j X1j	...	t 1n X1n
A2	t 21 X21	t 22 X22	...	t 2j X2j	...	t 2n X2n
...	...	...	...	...	...	...
Ai	t i1 Xi1	t i2 Xi2	...	t ij Xij	...	t in Xin
...	...	...	...	...	...	...
Am	tm1 Xm1	tm2 Xm2	...	tmj Xmj	...	t mn Xmn

Transport masalasini yechishda potensiallar usuli va uning iqtisodiy ma’nosi.
Biror usul bilan topilgan boshlang‘ich reja umuman olganda optimal reja bo‘lavermaydi, biroq usulning samarasiga qarab, optimal rejaga yaqinroq bo‘lishi mumkin. Har qanday yopiq modelli transport masalasi optimal rejaga ega ekanligini inobatga olib, optimal rejani topish usullaridan biri bo‘lgan potensiallar usulini bayon qilamiz. Bu usulda, dastlabki reja topilgandan so‘ng, har bir ta’minotchi va iste’molchiga, potensial deb ataluvchi va sonlarni mos qo‘yamiz. Bu sonlarni aniqlash uchun, jadvaldagi barcha band (yuk taqsimlangan) kataklar uchun potensiallarni aniqlovchi tenglamalar tuzamiz. Deylik, (i, j)- katak band bo‘lsin. U holda u_i va v_j larni shunday tanlaymizki, ularning yig‘indisi mos tarifga teng bo‘lsin:
.
Barcha u_i va v_j miqdorlar soni n+m ta, band kataklar soni esa n+m-1 ta bo‘lgani sababli, n+m ta noma’lumni topish uchun n+m-1 ta tenglamaga ega bo‘lamiz. Bu tenglamalardan noma’lumlarni bir qiymatli topib bo‘lmasligi tufayli, noma’lumlardan birini ixtiyoriy tanlaymiz (masalan, u₁=0 deb tanlaymiz), qolgan o‘zgaruvchilar bir qiymatli aniqlanadi.
Optimallik shartini tekshirish maqsadida barcha bo‘sh (yuk taqsimlanmagan) kattaklar uchun qalbaki tarif kiritamiz:
.
So‘ngra har bir bo‘sh katak uchun shu katakka mos tarif va qalbaki tariflar farqini hisoblaymiz:
.
Qaralayotgan masala uchun o‘rinli bo‘lgan ushbu teoremani keltiraylik:
Teorema. Transport masalasida qaralayotgan reja optimal bo‘lishi uchun, barcha band kataklar uchun

bo‘lishi va barcha bo‘sh kataklar uchun

bo‘lishi zarur va etarlidir.
Bu teorema isboti ikkilanmalik nazariyasi natijalaridan kelib chiqadi.
Optimal rejani topish algoritmini davom ettiraylik. Agar optimallik sharti bajarilsa, qaralayotgan reja optimal bo‘ladi. Deylik, optimallik sharti bajarilmasin, ya’ni sonlar ichida manfiylari bor bo‘lsin. Bunday sonlarning borligi planni yanada «yaxshilash» imkoniyatini beradi. Shu maqsadda, manfiy lar ichidan eng kichigini tanlaymiz (agar yagona bo‘lsa o‘zini, eng kichigi bir nechta bo‘lsa, ulardan ixtiyoriy bittasini tanlaymiz). Tanlangan katakni qutb deb ataymiz va unga ishorasini qo‘yib, uni band kataklar safiga qo‘shamiz. Natijada, jadvaldagi band kataklar soni n+m taga yetadi va bir uchi qutbda qolgan uchlari band kataklardan iborat yagona sikl qurish mumkin bo‘ladi. So‘ngra, sikl bo‘ylab, qutbdan boshlab, qutbning barcha uchlariga soat strelkasi yo‘nalishi bo‘ylab navbat bilan va - ishorasini qo‘yib chiqamiz. Barcha - ishoraga mos keluvchi yuklarni taqqoslab, eng kichik yukni o‘lchov miqdori sifatida qabul qilib, - ishorali kataklardagi yuk miqdoridan o‘lchov miqdorini ayirib, ustun bo‘yicha, ishorali kataklardagi yukka qo‘shamiz. Natijada yangi reja hosil bo‘ladi. Yangi reja uchun yana potensiallarni aniqlab, optimallik sharti bajarilmasa, yuqoridagi tadbirlarni optimal rejani topguncha davom ettiramiz va chekli qadamdan so‘ng optimal reja topiladi.