Egamberdiyev Ollobergan 22-55 guruh talabasi

Optimallik shartini tekshirish maqsadida barcha bo‘sh (yuk taqsimlanmagan) kattaklar uchun qalbaki tarif kiritamiz:

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.
1-teorema. Har qanday yopiq modelli transport masalasi yechimga ega.
2-teorema. Transport masalasining shartlaridan tuzilgan matritsaning
rangi ga teng.
3-teorema. Agar masaladagi barcha
lar butun sonlardan iborat bo‘lsa, transport masalasining yechimi butun sonli bo‘ladi.
4-teorema. Ixtiyoriy transport masalasining optimal rejasi mavjuddir.