Transport masalasi

Transport masalasi Reja: Transport masalasining kuyilishi. Transport masalasining turlari. Transport masalasining asosiy modeli. Asosiy teoremalar. Transport jadvalini tuzish Transport masalasining boshlang'ich tayanch planini topish usullari. Minimal xarajatlar usulining asosiy g'oyasi. Shimoliy - g'arb usulining asosiy g'oyasi. Transport masalasi chiziqli programmalash masalalari ichida nazariy va amaliy nuqtai nazaridan eng yaxshi uzlashtirilgan masalalardan biri bo'lib, undan sanoat va qishloq xo'jalik mahsulotlarini tashishni optimal planlashtirish ishlarida muvaffakiyatli ravishda foydalanilmokda. Tranport masalasi maxsus chiziqli programmalash masalalari sinfiga tegishli bo'lib, uning chegaralovchi shartlaridagi koeffitsentlaridan tuzilgan () matritsaning elementlari 0 va 1 rakamlardan iborat bo'ladi va xar bir ustunda fakat ikkita element 0 dan farqli, kolganlari esa 0 ga teng bo'ladi. Transport masalasini yechish uchun uning maxsus xususiyatlarini nazarga oluvchi usullar yaratilgan. Transport masalasining matematik modelini quyidagi ko'rinishda yozish mumkinligi bizga malum. Bu yerdagi (1) shart xar bir ishlab chikaruvchi punktlaridagi mahsulot tula taksimlansin, (2) esa xar bir istemol qiluvchi punktning talabi tula kanoatlantirilsin degan manolarni bildiradi. mahsulotni tashish uchun sarf kilinadigan umumiy transport xarajatlari (4) chiziqli funksiya orqali ifodalanadi. Masaladagi xar bir manfiy bo'lmagan sonlar. Agar (1) - (4) masalada tenglik urinli bulsa, yani ishlab chikarilgan mahsulotlar yig'indisi unga bo'lgan talablar yig'indisiga teng bulsa, u holda bu masalani yopiq modelli transport masalasi deb ataymiz. 1 -teorema. Xar qanday yopiq modelli transport masalasi yechimga ega. Isbot. Shartga ko'ra U holda berilgan transport masalasining plani bo'ladi. Xakikatan xam, Demak, transport masalasining xamma shartlarini kanoatlantiradi. Shuning uchun bu miqdor masalaning plani bo'ladi. 2 - teorema. Taransport masalasining shartlaridan tuzilgan matritsaning rangi ga teng. Isbot. Xakikatan xam, bu matritsa kengaytirilgan holda quyidagi ko'rinishga ega bo'ladi: Bu matritsaning ixtiyoriy katori (masalan 1-katori) kolgan katorlarning chiziqli kombinatsiyasidan iborat ekanligini ko'rsatish mumkin. katorlarni o'zaro kushib, natijasidan katorlarni ayirsak 1-katorni hosil kilamiz. Demak, A matritsaning rangi . Endi - katorlar o'zaro chiziqli bog'liq bo'lmagan sistemani tashkil qilishini kursatamiz. Buning uchun ixtiyoriy sonlar olib ularga mos ravishda - katorlarni kupaytirib o'zaro kushamiz va natijasini ga tenglaymiz. Natijada kuyidagilarga ega bulamiz: (6) va (7) (6) sistemadan (8) ekani va (7) sistemadan (9) kelib chikadi. Bundan (8) ga asosan bo'ladi. Demak, A matritsaning ta katori o'zaro chiziqli bog'liq bo'lmagan sistemani tashkil qiladi va demak bo'ladi. 3-teorema. Agar masaladagi barcha ai va bj lar butun sonlardan iborat bulsa, transport masalasining yechimi butun sonli bo'ladi. Teoremaning isbotini transport masalasining boshlang'ich tayanch planlarini topish usullaridan ko'rish mumkin. 4-teorema. Ixtiyorniy transport masalasining optimal plani mavjuddir. Isbot. 1-teoremaga asosan masalaning kamida bitta plani mavjuddir. (8.1.1), (8.1.2) shartlardagi koeffitsiyentlar va barcha ai ...