Mustaqil ishi Bajarildi: 2-kurs talabasi cal008-L1 guruh Begmatov J. Tekshirildi: Aliqulov Y. Q. Toshkent – 2022 Mavzu


Download 91.89 Kb.
bet1/4
Sana18.06.2022
Hajmi91.89 Kb.
#764916
  1   2   3   4
Bog'liq
Algoritm mustaqil ish
1 a, Kadirberdiyev1917 Var 14, theme 1, Mamatqobilov AL MI

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI

ALGORITMLASH VA MATEMATIK MODELLASHTIRISH KAFEDRASI


ALGORITMLARNI LOYIYALASH FANI BO’YICHA
Mustaqil ishi

Bajarildi:
2-kurs talabasi
CAL008-L1 - guruh
Begmatov J.

Tekshirildi:
Aliqulov Y.Q.


Toshkent – 2022
Mavzu: Chiziqli dasturlash masalasi. Masala matematik modeli, iqtisodiy tahlili.
REJA:
1.Chiziqli dasturlash masalasi.
2.Matematik modeli.
3.Iqtisodiy tahlili.

Chiziqli dasturlash masalasi.


Chiziqli dasturlash- bu matematik dasturlashning eng rivojlangan bo'limi bo'lib, uning yordamida chiziqli ulanishlar va cheklovlar bilan ekstremal masalalarni tahlil qilish va yechish amalga oshiriladi.
Chiziqli dasturlash bir qator evristik (taxminan) yechim usullarini o'z ichiga oladi, ular berilgan sharoitlarda ishlab chiqarish muammolarining barcha mumkin bo'lgan echimlaridan eng yaxshisini, optimalini tanlashga imkon beradi. Bu usullarga quyidagilar kiradi - grafik, simpleks, potentsial usul (modifikatsiyalangan taqsimlash usuli - MODI), Xichkova, Kreko, Vogelga yaqinlashish usuli va boshqalar.
Ushbu usullarning ba'zilari umumiy nom - tarqatish yoki tashish usuli bilan birlashtirilgan.
Chiziqli dasturlashning vatani Rossiyadir. Chiziqli dasturlash bo'yicha birinchi ishlar bo'lajak akademik L.V. Kantorovich 1939 yilda nashr etilgan. 1975 yilda u chiziqli dasturlash usullarini ishlab chiqqani uchun iqtisod bo'yicha Nobel mukofotiga sazovor bo'lgan. Akademik L.Vning aksariyat asarlaridan beri. Kantorovich transport muammolarini hal qilishga bag'ishlangan, shuni aytish mumkinki, ko'rsatilgan Nobel mukofoti ham Rossiya transport fanining xizmatlarini tan oladi.
Avtomobil transportida 1960-yillardan boshlab ko'plab eng muhim ishlab chiqarish muammolarini hal qilish uchun chiziqli dasturlash usullari qo'llanila boshlandi, xususan: yuklarni tashish masofasini qisqartirish; optimal tashish sxemasini tuzish; eng qisqa harakat yo'nalishlarini tanlash; har xil, lekin bir-birini almashtiradigan tovarlarni tashish vazifalari; smenali kunlik rejalashtirish; kichik partiyadagi yuklarni tashishni rejalashtirish; avtobuslarni marshrutlarga taqsimlash va boshqalar.
Chiziqli dasturlash modelining xususiyatlari quyidagilardan iborat:
Maqsad funktsiyasi va cheklovlar chiziqli bog'liqliklar (tenglik yoki tengsizlik) bilan ifodalanadi;
Bog'liqlar soni har doim noma'lumlar sonidan kamroq (noaniqlik sharti);
Kerakli o'zgaruvchilarning manfiy emasligi. Chiziqli dasturlash modelini qisqartirilgan shaklda yozishning umumiy shakli quyidagicha:
Toping NS ij ≥ 0 (j = 1, 2 ... n) quyidagi turdagi cheklovlar ostida:
Ushbu cheklovlar maqsad funktsiyasini minimallashtiradi (yoki maksimal darajaga keltiradi).
Chiziqli dasturlash modelini yozishning standart shakli chiziqli tenglamalar tizimida yozilgan kanonik shaklda, ya'ni chiziqli tenglik shaklida, manfiy bo'lmagan sonlarda:
a 11 x 1 + a 12 x 2 + ... + a 1 n x n = b 1;
a 21 x 1 + a 22 x 2 + ... + a 2 n x n = b 2 ; (3.1)
……………………………..
a m x 1 + a m 2 x 2 +… + a mn x n = b m ..
Agar model manfiy bo'lmagan sonlarda tengsizliklar ko'rinishida yozilsa, ya'ni u shaklga ega.
a 11 x 1 + a 12 x 2 + ... + a 1 n x n ≤ b 1;
a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)
……………………………..
a m x 1 + a m 2 x 2 +… + a mn x n ≤ b m, ..
keyin bu rekord kamayadi kanonik qo'shimcha o'zgaruvchilarni kiritish orqali (3.1) shakl x n +1> 0 (i=1,2…m) tengsizlikning chap tomoniga (yoki tengsizlik belgisi boshqa tomonga yo'naltirilgan bo'lsa, o'zgaruvchilar sonini bekor qilish). Qo'shimcha o'zgaruvchilar asosni tashkil qiladi.
Chiziqli dasturlash masalasini echishning standart shakli maqsad funktsiyasini minimallashtiradigan manfiy bo'lmagan sonlardagi chiziqli tenglamalar tizimining echimlarini topishdir. Bunday holda, maqsad funktsiyasi shaklga ega
L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3,3)
qayerda s 1, s 2 ... s n- maqsad funksiya koeffitsientlari L o'zgaruvchilar bilan NS j.
Qo'shimcha o'zgaruvchilar maqsad funktsiyasiga nol koeffitsientlar bilan kiradi.
Maqsad funksiyasini maksimallashtirish holatida L maqsad funktsiyasining o'zgaruvchilari belgilari teskari bo'lishi kerak va biz yana minimallashtirish muammosiga kelamiz, ya'ni. almashtirish orqali bir vazifa boshqasiga qisqartiriladi LL yoki maks L= min (- L).
Chiziqli tenglamalar tizimining asosiy yechimi (3.1) asosiy bo'lmagan o'zgaruvchilarga nol qiymatlar berilgan yechimdir.
Bazisga kiritilgan o'zgaruvchilar manfiy bo'lmagan asosiy yechim ruxsat etilgan deb ataladi.
Optimal yechim - bu maqsad funktsiyasini (3.3) maksimallashtirish (yoki minimallashtirish) mumkin bo'lgan echimdir.
Har bir chiziqli dasturlash masalasi boshqasiga mos keladi, bu ikki chiziqli dasturlash muammosi deb ataladi. Dualga nisbatan asl muammo to'g'ridan-to'g'ri deyiladi. To'g'ridan-to'g'ri va ikkilamchi masalalar juftlikni hosil qiladi, ular chiziqli dasturlashda qo'sh juftlik deb ataladi. To'g'ridan-to'g'ri va qo'sh juftlik to'g'ridan-to'g'ri masala kanonik shaklda yozilsa, assimetrik juftlikni, masalaning shartlari tengsizliklar bilan yozilsa, simmetrik juftlikni hosil qiladi.
Ikkilamchi masalaning matematik modelini tuzish qoidalari matritsalarni hisoblash qoidalariga asoslanadi.
Ikkilik tushunchasi chiziqli dasturlash masalalarini tahlil qilishda keng qo'llaniladi. Ikkilik xususiyati har bir alohida holatda batafsil ko'rib chiqiladi.
Grafik-analitik usul
Grafoanalitik usul chiziqli dasturlashning eng oddiy usullaridan biridir. U chiziqli dasturlashning mohiyatini, uning geometrik talqinini aniq ochib beradi. Uning kamchiligi shundaki, u 2 yoki 3 ta noma'lumli masalalarni yechishga imkon beradi, ya'ni tor doiradagi masalalar uchun qo'llaniladi. Usul analitik geometriya qoidalariga asoslanadi.
Ikki o‘zgaruvchili masalani yechish x 1 va x 2, bu masala ma'nosida manfiy bo'lmasligi kerak, Dekart koordinata tizimida bajariladi. Tenglamalar x 1= 0 va x 2= 0 - birinchi kvadrant koordinata tizimining o'qlari
Keling, muayyan misol yordamida hal qilish usulini ko'rib chiqaylik.

Download 91.89 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling