|
- qism. Ruxsat etilayotgan elementni topish
|
| bet | 2/8 | | Sana | 23.05.2024 | | Hajmi | 5,58 Mb. | | #251216 |
Bog'liq Samatova Zarnigor Nematovna1.1- qism. Ruxsat etilayotgan elementni topish.
C qatordagi manfiy ishorali sonlar turgan kataklar tahlil qilinib, ularning eng kichik qiymatga ega boʻlgan element turgan katak yoki manfiy ishorali elementlarga absalyut qiymat berilib, ushbu elementlarning eng kattasi turgan katakni ruxsat etilayotgan ustun deb ataladi va S harfi bilan belgilanadi.
1.2- qism. Ruxsat etilyotgan qatorni topish.
Ruxsat etilayotgan ustunning C qator elementidan tashqari musbat ishorali elementlari tanlab olinadi va ozod sonlar turgan ustun elementlarining mos ravishda ruxsat etilayotgan ustun elementlariga boʻlib chiqiladi, hosil boʻlgan sonlarning eng kichigi turgan katak ruxsat etilayotgan qatorni koʻrsatadi va r harfi bilan belgilanadi. Ruxsat etilayotgan qator bilan, ruxsat etilayotgan ustun kesishayotgan katakda ruxsat etilayotgan element (ar,s) yotadi.
II - qism. Jordon Madifikatsiya usuli.
2.1 Yangi jadvaldagi ruxsat etilayotgan element oʻrnida turgan elementni topish.
ars - avvalgi jadvaldagi ruxsat etilayotgan element.
2.2 Yangi jadvalning ruxsat etilayotgan qatoriga mos boʻlgan qator kataklarining qolgan elementlarini topish.
arj - avvalgi jadvaldagi ruxsat etilayotgan qator elementlari.
2.3 Yangi jadvaldan ruxsat etilgan ustunning qolgan elementlarini topish.
ais - avvalgi jadvaldagi yangi jadvalda qidirilayotgan katak elementlariga mos element.
2.4 Yangi jadvalning qolgan kataklari elementlarini topish.
2.5 Optimallik sharti.
Simpleks jadvalining optimallik shartini ya’ni masala eng yuqori daromad shartida C qatoridagi manfiy elementlarning yoʻqligi yaxshi natijaga erishganligidir.
Chiziqli dasturlash masalasida, agar maqsad funksiyasining minimumi izlansa yuqoridagi F qator elementlari manfiy holatga keltirilishi kerak, ya’ni teskari holat bo‘ladi.
Biz bilamizki, chiziqli dasturlash masalasi bu chiziqli funksionalni ko‘p o‘lchovli fazoda chiziqli cheklovlarni qanoatlantirgan holda minimum yoki maksimum qiymatini topishdan iborat. Bu masaladagi har bir chiziqli cheklovlar n- o‘lchovli fazoni (n-1)- o‘lchovli yarim fazosi bo‘ladi, demak bundan chiqadiki, barcha chiziqli cheklovlarni umumiy yechimi (mumkin bo‘lgan rejalar to‘plami) n- o‘lchovli fazoda qavariq ko‘pyoq bo‘ladi.
Simpleks algoritmi (yoki Simpleks usuli) chiziqli dasturlash (LP) optimallashtirish muammolarini hal qilish uchun keng qo'llaniladigan algoritmdir. Simpleks algoritmini tengsizlik muammosini hal qilishning elementar bosqichlaridan biri sifatida ko'rish mumkin, chunki ularning ko'pchiligi LP ga aylantiriladi va Simpleks algoritmi orqali yechiladi.[1] Simpleks algoritmi Jorj Dantsig tomonidan taklif qilingan bo'lib, uni qavariq ko'pburchakning cho'qqilaridan biriga bosqichma-bosqich pasaytirish g'oyasidan kelib chiqqan.[2] "Simpleks" ni oddiy konusning yuqori cho'qqisi deb atash mumkin, bu LP muammolaridagi cheklovlarning geometrik tasviri.
Algoritmik muhokama
LPda ikkita teorema mavjud:
1. LP muammosi uchun mumkin bo'lgan mintaqa qavariq to'plamdir (har bir chiziqli tenglamaning ikkinchi hosilasi 0 ga teng, bu tendentsiyaning monotonligini bildiradi). Shuning uchun, agar LP optimal echimga ega bo'lsa, amalga oshirish mumkin bo'lgan mintaqaning eng maqbul nuqtasi bo'lishi kerak.
2. LP optimallashtirish muammosi uchun har bir asosiy amalga oshirish mumkin bo'lgan yechimga nisbatan LPning mumkin bo'lgan hududining faqat bitta ekstremal nuqtasi mavjud. Bundan tashqari, mumkin bo'lgan mintaqadagi har bir ekstremal nuqtaga mos keladigan kamida bitta asosiy mumkin bo'lgan yechim bo'ladi.
Yuqoridagi ikkita teoremaga asoslanib, LP muammosining geometrik tasvirini tasvirlash mumkin. Ushbu ko'pburchakning har bir chizig'i LP cheklovlarining chegarasi bo'ladi, bunda har bir tepa teorema bo'yicha ekstremal nuqtalar bo'ladi.
Simpleks usuli - bu asosiy bo'lmagan o'zgaruvchilarni optimal echim topilgunga qadar turli cho'qqilarga o'tish uchun sozlash usuli.
Umumiy chiziqli dasturlash muammosining standart shakli sifatida quyidagi ifodani ko'rib chiqing:
maks∑�=1�����
LP muammosining geometrik tasviri
Quyidagi cheklovlar bilan:
Simpleks usulining birinchi bosqichi maqsad funktsiyalarni ifodalovchi bo'sh o'zgaruvchilar va belgilarni qo'shishdir:
Yangi kiritilgan bo'sh o'zgaruvchilar asl qiymatlar bilan chalkashishi mumkin. Shuning uchun, bu bo'sh o'zgaruvchilarni qo'shish qulay bo'ladi. zi�� quyidagi ifoda bilan x o'zgaruvchilar ro'yxatining oxirigacha:
Simpleks usulining rivojlanishi bilan boshlang'ich lug'at (yuqoridagi tenglamalar) optimal qiymatlarni izlashda lug'atlar o'rtasida almashinadi. Har bir lug'atda amalga oshirilishi mumkin bo'lgan sohani tashkil etuvchi m ta asosiy o'zgaruvchilar, shuningdek, maqsad funktsiyasini tashkil etuvchi n ta asosiy bo'lmagan o'zgaruvchilar bo'ladi. Shundan so'ng, lug'at funktsiyasi quyidagi shaklda yoziladi:
Barli o'zgaruvchilar mos keladigan qiymatlar simpleks usulining rivojlanishi bilan mos ravishda o'zgarishini ko'rsatadi. Kuzatish mumkinki, bitta o'zgaruvchi asosiy bo'lmagandan asosiyga o'tadi va boshqasi teskari harakat qiladi. Bunday o'zgaruvchiga kirish o'zgaruvchisi deyiladi. Ko'paytirish maqsadi ostida� ϕ, kiritilayotgan oʻzgaruvchilar {1,2,...,n} toʻplamidan tanlanadi. Takroriy kiritiladigan o'zgaruvchilarni tanlash mumkin bo'lmaguncha, optimal qiymatlar topiladi. Qaysi o'zgaruvchini birinchi navbatda tanlash kerakligi to'g'risida qaror odatda bir nechta cheklovlar mavjudligini hisobga olgan holda qabul qilinishi kerak (n>1). Simpleks algoritmi uchun eng kichik qiymatga ega bo'lgan koeffitsientga afzallik beriladi, chunki asosiy maqsad maksimallashtirishdir.
|
| |
