kommivoyajer masalasi - ryukzak haqidagi masala

DOCX 10 sahifa 172,1 KB Bepul yuklash

10 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 172,1 KB

Fayl turi DOCX

Sahifalar 10

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 10

13-ma’ruza. kommivoyajer masalasi. ryukzak haqidagi masala reja 1. kommivoyajyor haqidagi masala. 2. keltirilgan matrisa va keltirish jarayoni. 3. ryukzak haqidagi masala. tayanch so’z va iboralar: masofalar matrisasi, marshrut, yopiq marshrut, marshrut uzunligi, butun qiymatli o’zgaruvchilar, graf, gamilton konturi (gamilton sikli), tarmoqlar va chegaralar usuli, keltirilgan matrisa, ryukzak (bombardimonchi samolyot) haqidagi masala, resurslar, yuk, yuklarni tashish (reys). 1. kommivoyajyor haqidagi masala. ta shahar bor. har bir shahar qolganlari bilan transport yo’li bilan bog’langan. shaharlar orasidagi masofalar matrisasi berilgan ( deb hisoblaymiz). kommivoyajyor qandaydir shahardan chiqib har bir shaharda faqat bir martadan bo’lib dastlabki shaharga qaytish kerak. shaharlarga borish marshrutini shunday tanlash kerakki marshrut uzunligi minimal bo’lsin. bu masalaning matematik modelini tuzish uchun (1) kabi belgilaymiz, bu yerda . masala quyidagicha yoziladi: (1) formula bo’yicha aniqlangan o’zgaruvchilarning shunday qiymatlarini topish kerakki, , (2) , (3) , (4) shartlar bajarilsin va bunda (5) funksiya minimumga erishsin. (4) shartda o’zgaruvchilar istalgan qiymatlarini qabul qilishlari …

2 / 10

iqatan ham, agar bo’lsa (ya’ni shahardan shahargacha borilmasa) (4) shart ko’rinishni oladi, bu esa larning ixtiyoriyligi sababli bajariladi. agar biror –chi qadamda shahardan shaharga borilsa, ya’ni bo’lsa, larning ixtiyoriyligi sababli, deb olamiz. u vaqtda , ya’ni (4) shart tenglik bo’lib bajariladi. qo’yilgan masala sodda matematik modelga ega bo’lsada uni hal qilish bir qator qiyinchiliklarga ega. albatta, bu masalani yechish uchun mavjud bo’lgan barcha marshrutlar topilib, ularning uzunliklari aniqlansa yetarli. lekin shaharlar soni o’sishi bilan marshrutlar soni ham tez o’sadi. hozirgi davrda kommivoyajyor haqidagi masalani hal qilishning ko’p usullari mavjud. bu usullar ichida tarmoqlar va chegaralar usuli o’zining samaradorligi bilan ajralib turadi. quyida shu usulni bayon etamiz. shaharlarni sonlar bilan nomerlab, ularni graf uchlari deb, yo’llarni esa graf yoylari deb qaraymiz. grafning barcha uchlaridan faqat bir martadan konturga gamilton konturi yoki sikli deb ataladi. demak, qaralayotgan masala grafda minimal uzunlikga ega gamilton konturini topishdan iboratdir. agar yoy (yo’l) uzunligini ifodalasa sikl …

3 / 10

ijada matrisadan keltirilgan matrisani hosil qilamiz. bunda keltiruvchi o’zgarmaslar (10) yig’indidan iborat bo’ladi. agar matrisani matrisa bilan almashtirsak (7) o’xshash formula bo’yicha yig’indini hosil qilamiz. natijada (11) formulani olamiz, bu yerda (10) bo’yicha aniqlanadi. bo’lgani uchun (11) dan ni hosil qilamiz, ya’ni marshrut (sikl) uzunligining quyi chegarasi bo’la oladi. tarmoqlar va chegaralar usulining asosiy g’oyasini keltiramiz. dastlab barcha gamilton konturlari to’plami uchun kommivoyajyor marshruti uzunligi quyi chegarasi aniqlanadi. bu quyi chegara (10) formula bo’yicha hisoblanadi. so’ngra to’plam ikkita to’plamga ajratiladi. birinchi to’plam shunday gamilton konturlaridan iboratki, ular qandaydir yoyni o’z ichiga oladi. bu to’plamni deb belgilaymiz. ikkinchi to’plam yoyni o’z ichiga olmagan gamilton konturlari to’plami bo’ladi. uni deb belgilaymiz. har bir va to’plamlar uchun gamilton konturlari uzunliklari quyi chegaralari va aniqlanadi. har bir yangi quyi chegara dan kichik emas. ya’ni va to’plamlaridan kichik quyi chegarali to’plam tanlanadi va bu to’plam yana ikkita to’plamga ajratiladi va jarayon qaytariladi. keyingi hosil bo’lgan …

4 / 10

isa qandaydir qadamda o’lchovli matrisadan iborat bo’lib qoldi va shaharlarning faqat ikkita mumkin bo’lgan juftini o’zida saqlaydi. bu juftliklar yordamida yopiq marshrut gamilton konturlari hosil qilish mumkin. agar qisqarilgan matrisa matrisa bo’lsa 11-punktga aks holda 10- punktga o’tamiz. agar hosil qilingan matrisa keltirilgan matrisa bo’lsa, to’plamning quyi chegarasi shu to’plam hosil qilingan to’plamning quyi chegarasiga teng, ya’ni . aks holda hosil qilingan matrisadan keltirilgan matrisa hosil qilinadi va hisoblanadi, topiladi, deb 4-punktga o’tiladi. 10. gamilton konturlari olingandan so’ng tarmoqlanish daraxtining uzilgan tarmoqlari qaraladi va ularning quyi chegaralari kontur uzunligi (rekord-) bilan solishtiriladi. agar uzilgan tarmoqlarga mos to’plamlar quyi chegaralari dan kichik bo’lsa, bu tarmoqlar yuqoridagi qoida bo’yicha davom ettiriladi. bu jarayon yangi hosil bo’lgan to’plamlar quyi chegaralari dan kichik bo’lguncha davom ettiriladi. tarmoqlarni davom ettirish vaqtida yangi gamilton konturlari hosil bo’lishi mumkin. bu holda sifatida gamilton konturlari uzunligi eng kichik bo’lgani olinadi. agar uzunlik tarmoqlari quyi chegaralari dan kichik bo’lmasa …

5 / 10

larning foydaliliklari yig’indisini tushunamiz. shunday reysni tashkil etish kerakki, uning foydalilik darajasi maksimal bo’lsin. qo’yilgan masalaning matematik modelini tuzamiz. – tashish uchun ajratilgan j-yuk soni bo’lsin. yukning bo’linmaslik talabi , – butun son, j=1,2,...,n, (12) ko’rinishdagi shartga olib keladi. har bir yukning birlik miqdorini tashish uchun resurs sarfi va resurslarning jami miqdori asosida , (13) shartga ega bo’lamiz. reysning umumiy foydalilik darajasi esa (14) funksiya qiymati bilan aniqladi. shunday qilib, (14) funksiyani (12), (13) shartlarda maksimallashtirish masalasiga ega bo’ldik. bu masalada (12) ko’rinishda butun sonlilik talabi mavjud. qaralayotgan masalada, xususiy holda, nta yukning ixtiyoriy bittasi tashish uchun tanlanadi yoki tanlanmaydi degan shart qo’yilishi mumkin. bu holda har bir o’zgaruvchi faqat ikkita qiymat qabul qiladi: (yuk tanlanadi), (yuk tanlanmaydi). natijada, (14) funksiyaning (13) va (15) shartlardagi minimumni topish masalasiga ega bo’lamiz. ma’lumki, faqat 1 yoki 0 qiymat qabul qiluvchi diskret o’zgaruvchi buliy o’zgaruvchi deyiladi. shuning uchun (15) ko’rinishdagi shartlari bo’lgan butun …

Ko'proq o'qimoqchimisiz?

Barcha 10 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"kommivoyajer masalasi - ryukzak haqidagi masala" haqida

13-ma’ruza. kommivoyajer masalasi. ryukzak haqidagi masala reja 1. kommivoyajyor haqidagi masala. 2. keltirilgan matrisa va keltirish jarayoni. 3. ryukzak haqidagi masala. tayanch so’z va iboralar: masofalar matrisasi, marshrut, yopiq marshrut, marshrut uzunligi, butun qiymatli o’zgaruvchilar, graf, gamilton konturi (gamilton sikli), tarmoqlar va chegaralar usuli, keltirilgan matrisa, ryukzak (bombardimonchi samolyot) haqidagi masala, resurslar, yuk, yuklarni tashish (reys). 1. kommivoyajyor haqidagi masala. ta shahar bor. har bir shahar qolganlari bilan transport yo’li bilan bog’langan. shaharlar orasidagi masofalar matrisasi berilgan ( deb hisoblaymiz). kommivoyajyor qandaydir shahardan chiqib har bir shaharda faqat bir martadan bo’lib dastlabki shaharga qaytish kerak. shaharlarga borish...

Bu fayl DOCX formatida 10 sahifadan iborat (172,1 KB). "kommivoyajer masalasi - ryukzak haqidagi masala"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: kommivoyajer masalasi - ryukzak… DOCX 10 sahifa Bepul yuklash Telegram

kommivoyajer masalasi - ryukzak haqidagi masala

Sahifa ko'rinishi (5 sahifa)

Ko'proq o'qimoqchimisiz?

"kommivoyajer masalasi - ryukzak haqidagi masala" haqida

O'xshash fayllar