TATU URGANCH FILIALI
921 21 GURUH TALABASI NURMETOV XURSANDNING
ALGORITMLARNI LOYIHALASH
FANIDAN MUSTAQIL ISHI
Chiziqli dasturlash masalalari kanonik ko’rinishi. Simpleks usuli.
Simpleks usuli, optimallashtirish muammosini hal qilish uchun chiziqli dasturlashda standart texnika , odatda bitta funktsiya va tengsizlik sifatida ifodalangan bir nechta cheklovlarni o'z ichiga oladi. Tengsizliklar ko'pburchak mintaqani belgilaydi va yechim odatda cho'qqilardan birida bo'ladi. Simpleks usuli - bu cho'qqilarni mumkin bo'lgan yechimlar sifatida sinash uchun tizimli protsedura.
Ba'zi oddiy optimallashtirish muammolarini grafikda cheklovlarni chizish orqali hal qilish mumkin. Biroq, bu usul faqat ikkita o'zgaruvchini o'z ichiga olgan tengsizliklar tizimlari uchun foydalidir. Amalda, muammolar ko'pincha minglab o'zgaruvchilarga ega bo'lgan yuzlab tenglamalarni o'z ichiga oladi, bu esa astronomik ekstremal nuqtalarga olib kelishi mumkin. 1947 yilda AQSh Harbiy-havo kuchlarining matematik maslahatchisi Jorj Dantsig tekshirilishi kerak bo'lgan ekstremal nuqtalar sonini cheklash uchun simpleks usulini ishlab chiqdi. Simpleks usuli hozirgacha ixtiro qilingan eng foydali va samarali algoritmlardan biri bo'lib , u hali ham kompyuterlarda optimallashtirish masalalarini hal qilishda qo'llaniladigan standart usul hisoblanadi.
Birinchidan, usul ekstremal nuqta ma'lum deb taxmin qiladi. (Hech qanday ekstremal nuqta berilmagan bo'lsa, I bosqich deb ataladigan simpleks usuli bir variantni topish yoki amalga oshirish mumkin bo'lgan echimlar yo'qligini aniqlash uchun ishlatiladi.) Keyinchalik, masalaning algebraik spetsifikatsiyasidan foydalanib, test bu yoki yo'qligini aniqlaydi. ekstremal nuqta optimal hisoblanadi. Agar optimallik testidan o'tmagan bo'lsa, maqsad funktsiyasining qiymati eng tez sur'atlarda o'sadigan yo'nalishdagi chekka bo'ylab qo'shni ekstremal nuqta qidiriladi. Ba'zan chekka bo'ylab harakatlanishi va maqsad funktsiyasi qiymatini chegaralanmagan holda oshirishi mumkin. Agar bu sodir bo'lsa, protsedura ob'ektiv ijobiy cheksizlikka o'tadigan chekkaning retsepti bilan tugaydi. Agar yo'q bo'lsa, hech bo'lmaganda oldingisi kabi yuqori maqsad funktsiyasi qiymatiga ega bo'lgan yangi ekstremal nuqtaga erishiladi. Keyin tasvirlangan ketma-ketlik takrorlanadi. Tugatish optimal ekstremal nuqta topilganda yoki chegaralanmagan holat yuzaga kelganda sodir bo'ladi. Garchi printsipial jihatdan zaruriy qadamlar ekstremal nuqtalar soni bilan eksponent ravishda o'sishi mumkin bo'lsa-da, amalda usul odatda ekstremal nuqtalar sonining kichik ko'paytmasi bo'lgan bir qator bosqichlarda optimal echimga yaqinlashadi .
Chiziqli dasturlash usulini qo'llash birinchi marta 1930-yillarning oxirida sovet matematigi Leonid Kantorovich va amerikalik iqtisodchi Vasiliy Leontef tomonidan ishlab chiqarish jadvallari va iqtisod sohalarida jiddiy urinishgan , ammo ularning ishlari o'nlab yillar davomida e'tiborga olinmagan. Ikkinchi Jahon urushi paytida chiziqli dasturlash xarajatlar va mavjudlik kabi ma'lum cheklovlarga bog'liq bo'lgan resurslarni tashish, rejalashtirish va taqsimlash bilan shug'ullanish uchun keng qo'llanilgan . Ushbu ilovalar 1947 yilda amerikalik matematik Jorj Dantsigning kiritilishi bilan yanada kuchagan ushbu usulning maqbulligini aniqlash uchun juda ko'p yordam berdi. Simpleks usuli , bu chiziqli dasturlash masalalarini hal qilishni ancha soddalashtirdi.
Misol sifatida ushbu berilgan masalani ko’rib chiqsak:
Korxona 4 xil maxsulot ishlab chiqaradi. Maxsulotlarni bir birligini baxosi mos ravishda 2, 1, 3 va 5 birlik. Ishlab chiqarish uchun uchta resurs ishlatiladi energiya, xom ashyo va mexnat rusurslari. Maxsulotni bir birligini ishlab chiqarish uchun resurslar normasi quyidagi jadvalda keltirilgan:
Optimallik kriteriyasi — korxonani maxsulotlarini realizasiya qilishni masimallashtirish. Masalani yechish uchun iqtisodiy matematik modelni tuzamiz. Belgilashlar kiritamiz:
– 1-maxsulotni ishlab chiqarish miqdori, dona;
-2-maxsulotni ishlab chiqarish miqdori, dona;
-3-maxsulotni ishlab chiqarish miqdori, dona;
-4-maxsulotni ishlab chiqarish miqdori, dona.
Masalaning shartini cheklanishlar sistemasi kurinishida yozamiz:
Energiyadan foydalanish:
2) Xom ashyodan foydalanish
3) Ishchi kuchidan foydalanish:
Maqsad funksiyasi – maxsulotni sotishni maksimallashtirish:
Modelni chiziqli programmalash masalasining kanonik kurinishiga keltiramiz:
Bu yerda qo’shimcha kiritilgan x o'zgaruvchilar iqtisodiy jixatdan tejaladigan resurslarni anglatadi mos ravishda energiya, xom ashyo va mexnat. Masala uchun bazis plan quyidagidan iborat bo'ladi X (0,0,0,0,30,40,25)
Demak (1.1) – (1.5) masalani simpleks usulida yechish mumkin. Simpleks jadvalni to'ldiramiz.
Yangi 3-jadvalda bazisga kirgan o'zgaruvchini satrini elementlarini quyidagicha aniqlaymiz, ya’ni 2- jadvaldagi x5 satr elementlari qoralangan katakdagi songa (2 ga) bo'lib chiqiladi va 3- jadvaldagi x4 satrga yoziladi. 3-jadvalning qolgan elementlari to'rtburchak usulida xisoblanadi:
Optimal plan x (0,0,4,13,0,10,0) , maqsad funksiyasini optimal qiymati
Modelni taxlil qilish:
Ko’rinib turibdiki barcha resurslar to’liq ishlatilgan!
|
