5-ma’ruza. Transport masalasining qo’yilishi. Balans modeli va uni transport masalasi yordamida yechish

5-ma’ruza. Transport masalasining qo’yilishi. Balans modeli va uni transport masalasi yordamida yechish

5-ma’ruza. Transport masalasining qo’yilishi. Balans modeli va uni transport masalasi yordamida yechish
REJA:
1. Transport masalasi va uning xususiyatlari
2. Transport masalasining boshlang‘ich tayanch planini topish usullari


TAYANCH IBORALAR: boshlang‘ich tayanch plan, yopiq model, ochiq model, shimoliy – g‘arb burchak usuli, minimal harajatlar usuli


Transport masalasi
Trasport masalasi chiziqli programmalash masalalari ichida nazariy va amaliy nuqtai nazardan eng yaxshi o‘zlashtirilgan masalalardan biri bo‘lib, undan sanoat va qishloq xo‘jalik mahsulotlarini tashishni optimal planlashtirish ishlarida muvaffaqiyatli ravishda foydalanilmoqda.

Trasport masalasi maxsus chiziqli programmalash masalalari sinfiga tegishli bo‘lib, uning chegeralovchi shartlaridagi koeffitsiyetlardan tuzilgan matritsaning elementlari 0 va 1 raqamlaridan iborat bo‘ladi va har bir ustunda faqat ikkita element noldan farqli, qolganlari esa nolga teng bo‘ladi. Transport masalasini yechish uchun uning maxsus xususiyatlarini nazarga oluvchi usullar yaratilgan bo‘lib, quyida biz ular bilan tanishamiz.

1. Transport masalasining xususiyatlari

Bizga ma’lumki, trasport masalasining matematik modelini quyidagi ko‘rinishda yozish mumkin.

(1)
(2)
(3)
(4)
Bu yerdagi (1) shart harbir ishlab chiqaruvchi punktlardagi mahsulot to‘la taqsimlansin, (2) esa har bir iste’mol qiluvchi punktning talabi to‘la qanoatlantirilsin degan ma’nolarni bildiradi. Mahsulotni tashish uchun sarf qilinadigan umumiy transport harajatlari (4) chiziqli funksiya orqali ifodalanadi.
Masaladagi har bir , va manfiy bo‘lmagan sonlar, ya’ni
, , .
Agar (1) – (4) masalada
(5)
tenglik o‘rinli bo‘lsa, ya’ni ishlab chiqarilgan mahsulotlar yig‘indisi unga bo‘lgan talablar yig‘indisiga teng bo‘lsa, u holda bu masalani yopiq modelli transport masalasi deb aytamiz.
1 -teorema. Har qanday yopiq modelli transport masalasi yechimga ega.
I s b o t. Shartga ko‘ra
.
U holda

berilgan transport masalasining plani bo‘ladi. Haqiqatan ham,

chunki , , .

Demak, transport masalasining hamma shartlarini qanoatlantiradi. Shuning uchun bu miqdor masalaning plani bo‘ladi.

2 – teorema. Transport masalasining shartlaridan tuzilgan matritsaning rangi ga teng.
Isbot. Haqiqatdan ham bu matritsa kengaytirilgan holda quyidagi ko‘rinishga ega bo‘ladi.

Bu matritsaning ixtiyoriy qatori (masalan 1-qatori) qolgan qatorlarning chiziqli kombinatsiyasidan iborat ekanligini ko‘rsatish mumkin. qatorlarni o‘zaro qo‘shib, natijasidan 2, 3, …, qatorlarni ayirsak 1-qatorni hosil qilamiz. Demak matritsaning rangi . Endi 2, 3, …, - qatorlar o‘zaro chiziqli bog‘liq bo‘lmagan sistemani tashkil qilishini ko‘rsatamiz. Buning uchun ixtiyoriy sonlar olib ularga mos ravishda 2, 3, …, qatorlarni ko‘paytirib o‘zaro qo‘shamiz va natijasini ga tenglaymiz. Natijada quyidagilarga ega bo‘lamiz:

(6)
va
(7)
(6) sistemadan (8)
ekani va (7) sistemadan
(9)
kelib chiqadi. Bundan (8) ga asosan bo‘ladi. Demak matritsaning ta qatori o‘zaro chiziqli bo‘lmagan sistemani tashkil qiladi va demak, bo‘ladi.
3 -teorema. Agar masaladagi barcha va lar butun sonlardan iborat bo‘lsa, transport masalasinig yechimi butun sonli bo‘ladi
Teoremaning isbotini transport masalasining boshlang‘ich tayanch planlarini topish usullarida ko‘rish mumkin.
4 -teorema. Ixtiyoriy transport masalasining optimal plani mavjuddir.
Isbot. 1-teoremaga asosan masalaning kamida bitta plani mavjuddir. (1), (2) shartlardagi koeffitsiyentlar va barcha va lar musbat butun son bo‘lganligi sababli ham yuqoridan chegaralangan bo‘ladi va uning qiymati mos va larning qiymati oshmaydi.
Shunday qilib transport masalasi planlaridan tashkil topgan to‘plam bo‘sh to‘plam bo‘lmaydi. U chegaralangan to‘plam bo‘ladi. Demak transport masalasi optimal planga ega.