Mavzu: Transport masalasi

1-tеоrеmа. Tаlаblаr hаjmi tаkliflаr hаjmigа tеng bo`lgаn istаlgаn trаnspоrt mаsаlаsining оptimаl yechimi mаvjud bo`lаdi.
Bu teoremani isbotsiz qabul qilamiz.
Transport masalasi matematik modeli tenglamalar sistemasidagi bazis vektorlar sistemasining o`lchovini aniqlaymiz. Buning uchun sistema asosiy matritsasining rangini aniqlash kerak.
Agar o`zgaruvchilarni

ko`rinishda joylashtirsak, u holda transport masalasining cheklamalar matritsasi quyidagi ko`rinishga ega bo`ladi

Bu matritsaning rangi: ekanligini ko`rish qiyin emas. Haqiqatdan ham, matritsada ta satr bo`lib ular chiziqli bo`g`liq. Chunki birinchi ta satrni qo`shib undan oxirgi ta satr yig`indisini ayirsak nol vektorni hosil qilamiz. Bu matritsaning ixtiyoriy satrini olsak chiziqli erkli vektorlar sistemasi hosil bo`ladi.
Demak, masalaning optimal yechimida musbat lar soni ko`pi bilan ta bo`ladi.
Transport masalasi rejalari ko`p takrorlanish xususiyatiga ega. Shu sababli bu aynigansalarning ba`zilari bilan tanishib chiqamiz.
1-ta`rif. nuqtalarning (punktlarning) chekli to`plami va har bir elementi yoy deb ataluvchi tartiblanmagan juftliklarning to`plami berilgan bo`lsin. yoy va nuqtalarni tutashtiradi, bu nuqtalar esa yoyning oxiri deb ataladi. juftlik esa transport tarmog`i deb ataladi.
Masalan,

rasmda elementlari 7 ta nuqtadan iborat to`plam va oltita:

yoylarni o`zichiga oluvchi to`plam tasvirlangan.
2-ta`rif. ( ) ixtiyoriy chekli ketma-ketlik berilgan bo`lsin. Agar har qanday , , juftlik yoy bo`lib ( ), bu juftlik ketma-ketlikda ko`pi bilan bir marta uchrasa, u holda ketma-ketlik marshrut (yo`nalish) deb ataladi.
Yuqoridagi rasmda ikkta marshrut bor: .
3-ta`rif. ko`rinishdagi marshrut sikl deb ataladi.
Demak, marshrytda boshlang`ich holatga qaytilsa u sikl deb ataladi
Rasmdagi marshrutda tsikl yo`q, ammo unga yoy qo`shilsa u holda bu marshrutda ko`rinishdagi tsikl hosil bo`ladi.