chiziqli programmalash masalasini simpleks usulida yechish

DOCX 25 sahifa 621,8 KB Bepul yuklash

25 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 621,8 KB

Fayl turi DOCX

Sahifalar 25

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 25

3-mavzu chiziqli programmalash masalasini simpleks usulida yechish reja 1. vektorlarning bazis vektorlar bo‘yicha yoyilmasi. bir bazisdan ikkinchisiga o‘tish. 2. chiziqli tenglamalar sistemasining nomanfiy yechimlari orasidan berilgan chiziqli funksiyaga ekstremal qiymat beruvchi yechimni aniqlash. 3. simpleks usul. tayanch iboralar: tayanch plan, optimal plan, simpleks usul, bazis vektor, sun’iy bazis o‘zgaruvchi yuqorida ko‘rganimizdek, chiziqli programmalash masalasining optimal planini uning barcha planlaridan tashkil topgan qavariq to‘plamning chetki nuqtalari orasidan qidirish kerak. bunday nuqtalar soni yoki boshqkacha aytganda masaladagi tayanch planlar soni dan tadan tuzilgan gruppalash orqali aniqlanadi. masaladagi noma’lumlar soni va tenglamalar soni katta bo‘lganda barcha tayanch planlarning optimalligini tekshirib chiqish ancha qiyin bo‘ladi. shuning uchun tayanch planlarni tartib bilan tekshirib chikib, ular ichidan optimal planni aniqlab beruvchi yechish sxemasini berilishi talab qilinadi. chiziqli programmalash masalasini yechishning bunday sxemalaridan biri simpleks usuldir. bu usul boshlang‘ich tayanch plandan chekli sondagi iteratsiyadan keyin optimal planni hosil kilish yo‘lini ko‘rsatadi va har bir navbatdagi iteratsiya oldingisiga …

2 / 25

uvchilar, o‘zgaruvchilarni esa bazis bo‘lmagan o‘zgaruvchilar deb qabul qilib, bazis bo‘lmagan o‘zgaruvchilarni nolga tenglaymiz. natijada: (5) boshlang‘ich planni hosil qilamiz . (5) planga quyidagi (6) yoyilma mos keladi. bu yoyilmadagi vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi sababli, topilgan boshlang‘ich (5) plan tayanch plan bo‘ladi. endi boshlang‘ich plandan foydalanib, yangi tayanch planni topish mumkinligini ko‘rsatamiz. vektorlar o‘lchovli vektor fazoning bazisini tashkil qilgani uchun vektorlarning ixtiyoriysini bazis vektorlar orqali faqat bir xil yoyilmasini topish mumkin, ya’ni (7) faraz qilaylik, birorta vektor, masalan ning yoyilmasidagi koeffitsiyentlardan kamida bittasi (masalan, ) noldan farqli bo‘lsin: (8) ixtiyoriy ( - hozircha noma’lum son)ni olib, (8) tenglikning ikki tomonini unga ko‘paytirib, hosil bo‘lgan natijani (6) dan ayiramiz. natijada quyidagi tenglikka ega bo‘lamiz: (9) agar bo‘lsa, vektor plan bo‘ladi. bo‘lganligi sababli, planning komponentlari manfiy bo‘lmaydi, shuning uchun bo‘lgan komponentalarni ko‘ramiz. demak, shunday topishimiz kerakki bo‘lganda bo‘lsin. bundan plan ixtiyoriy tengsizlikni qanoatlantiruvchi uchun plan bo‘ladi. lekin tayanch plan …

3 / 25

torni tanlash kriteriysi simpleks usulning asosiy elementlaridan biri hisoblanadi. agar bazisga kiritilayotgan vektorning yoyilmasida barcha bo‘lsa, (9) yoyilmadagi birorta vektorni bazisdan chiqaruvchi ni topib bo‘lmaydi. bu holda plan musbat komponentlarni o‘z ichiga oladi. vektorlar sistemasi esa o‘zaro chiziqli bog‘liq bo‘lib qavariq ko‘pburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. bu nuqtada esa chiziqli funksiya o‘zining minimum qiymatiga erisholmaydi. bu holda chiziqli funksiya quyidan chegaralanmagan bo‘ladi. m i s o l . berilgan masalaning tayanch planini tuzing va yangi tayanch planga o‘ting: sistemani vektor formada yozamiz: bu yerda - bazis vektorlar, bazis o‘zgaruvchilar, - bazis bo‘lmagan o‘zgaruvchilar. bazis bo‘lmagan o‘zgaruvchilarga nol qiymat berib boshlang‘ich planni topamiz. bu planga (11) yoyilma mos keladi. yangi planga o‘tish uchun ixtiyoriy, kamida bita musbat komponentalik bazis bo‘lmagan vektorni (masalan, ni) olamiz va uning bazis vektorlar orqali (12) yoyilmasini yozamiz. bu ifodaning ikki tomonini songa ko‘paytirib, natijani (11) dan ayiramiz va quyidagiga ega bo‘lamiz: . (13) …

4 / 25

yechimni topish. quyidagi (15) (16) chiziqli programmalash masalasining plandagi mavjud va ular xosmas deb faraz qilamiz. masalaning tayanch plan va unga mos keluvchi o‘zaro chiziqli bog‘liq bo‘lmagan. vektorlar sistemasi ma’lum bo‘lsin. u holda (17) va (18) bu yerda chiziqli funksiyaning tayanch plandagi qiymati, chiziqli funksiyaning koeffitsiyentlari. vektorlar o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar bo‘lganligi sababli ixtiyoriy bazis bo‘lmagan vektorning bu vektorlar orqali faqat bitta yoyilmasini topish mumkin: (19) bu vektorga chiziqli funksiyaning (20) qiymati mos keladi. vektorga mos keluvchi chiziqli funksiyaning koeffitsentini bilan belgilaymiz. u holda quyidagi teoremalar o‘rinli bo‘ladi. 1- t ye o r ye m a . agar tayanch planda tayinlangan j uchun tengsizlik o‘rinli bo‘lsa, x0 plan optimal plan bo‘lmaydi va shunday x plan topish mumkin bo‘ladiki, uning uchun tengsizlik o‘rinli bo‘ladi. isbot. (19) va (20) ni ga ko‘paytirib, mos ravishda (17) va (18) dan ayiramiz. natijada quyidagilarga ega bo‘lamiz: (21) (22) agar (21) dagi , vektorlar oldidagi …

5 / 25

hun vektorning bu vektorlar orqali faqat bitta yoyilmasini topish mumkin. demak (26) va (27) dagi vektorlar oldidagi koeffitsiyentlar o‘zaro teng bo‘lishi kerak, ya’ni (28) endi (28) dagi larning qiymatlarini (27) ga qo‘yamiz, natijada (29) tengsizlikni hosil qilamiz. bundan (18) ga asosan: teorema isbot bo‘ldi. shart tayanch planining optimal bo‘lish sharti (optimallik kriteriysi) bo‘ladi. 3. simpleks usul algoritmi. yuqoridagi 1- va 2- teoremalarga asosan berilgan boshlang‘ich plandan boshlab tayanch planlar ketma-ketligini hosil qilib borib, jarayonni optimal yechim topulguncha davom ettirish mumkin. faraz qilaylik, masalaning boshlang‘iya tayanch plani, shu planga mos keluvchi o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar sistemasi bo‘lsin. bu vektorlardan tashkil topgan () matritsani v bilan belgilaymiz. u holda bundan va kelib chiqadi. bu yerda vektor ustunlar. simpleks jarayoni boshlashdan avval masalaning vektorlarini quyidagidek gruppalaymiz: yoki (30) elementlari ayrim qismlardan iborat bo‘lgan (30) matritsani ga ko‘paytiramiz va quyidagiga ega bo‘lamiz: yoki so‘ngra har bir uchun ni hisoblaymiz. agar barcha lar uchun …

Ko'proq o'qimoqchimisiz?

Barcha 25 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"chiziqli programmalash masalasini simpleks usulida yechish" haqida

3-mavzu chiziqli programmalash masalasini simpleks usulida yechish reja 1. vektorlarning bazis vektorlar bo‘yicha yoyilmasi. bir bazisdan ikkinchisiga o‘tish. 2. chiziqli tenglamalar sistemasining nomanfiy yechimlari orasidan berilgan chiziqli funksiyaga ekstremal qiymat beruvchi yechimni aniqlash. 3. simpleks usul. tayanch iboralar: tayanch plan, optimal plan, simpleks usul, bazis vektor, sun’iy bazis o‘zgaruvchi yuqorida ko‘rganimizdek, chiziqli programmalash masalasining optimal planini uning barcha planlaridan tashkil topgan qavariq to‘plamning chetki nuqtalari orasidan qidirish kerak. bunday nuqtalar soni yoki boshqkacha aytganda masaladagi tayanch planlar soni dan tadan tuzilgan gruppalash orqali aniqlanadi. masaladagi noma’lumlar soni va tenglamalar soni katta bo‘lganda barcha tayan...

Bu fayl DOCX formatida 25 sahifadan iborat (621,8 KB). "chiziqli programmalash masalasini simpleks usulida yechish"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: chiziqli programmalash masalasi… DOCX 25 sahifa Bepul yuklash Telegram