|
Dasturiy injiniringi
|
| bet | 3/8 | | Sana | 23.05.2024 | | Hajmi | 5,58 Mb. | | #251216 |
Bog'liq Samatova Zarnigor NematovnaChiqib ketuvchi o'zgaruvchilar asosiydan asosiy bo'lmaganga o'tuvchi sifatida aniqlanadi. Ularning mavjudligining sababi bu asosiy o'zgaruvchilarning manfiy emasligini ta'minlashdir. Kiruvchi o'zgaruvchilar aniqlangandan so'ng, tegishli chiquvchi o'zgaruvchilar quyidagi tenglamadan mos ravishda o'zgaradi:
Kiritilgan o'zgaruvchilarning manfiy emasligi ta'minlanishi kerakligi sababli, quyidagi tengsizlikni olish mumkin:
Qayerda�� xk o'zgarmasdir. Minimal�� xi minimal qiymatni olish uchun nolga teng bo'lishi kerak, chunki bu salbiy bo'lishi mumkin emas. Shunday qilib, quyidagi tenglamani olish kerak:
Barcha o'zgaruvchilarning manfiy emasligi tufayli ning qiymati xk ��yuqoridagi tenglamadan hisoblangan barcha qiymatlarning eng kattasiga ko'tarilishi kerak. Shunday qilib, quyidagi tenglamani olish mumkin:
Chiqish-asosiy va kiruvchi-asosiy bo'lmagan o'zgaruvchilar tanlangandan so'ng, joriy lug'atdan yangi lug'atga o'tish uchun oqilona qator operatsiyasini bajarish kerak, chunki bu bosqich pivot deb ataladi.
Pivot jarayonida bo'lgani kabi, tanlangan burilish elementi uchun koeffitsient bitta bo'lishi kerak, ya'ni bu koeffitsientning o'zaro nisbati ushbu qatordagi har bir elementga ko'paytirilishi kerak. Keyinchalik, ushbu maxsus qatorni mos keladigan koeffitsientlar bilan ko'paytirib, uni turli qatorlarga qo'shib, ushbu pivot element ustunidagi barcha boshqa yozuvlar uchun 0 qiymatini olish kerak.
Agar aylanish jarayonidan keyin salbiy o'zgaruvchilar mavjud bo'lsa, yuqoridagi jarayonni takrorlash orqali pivot elementini topishni davom ettirish kerak. Bir vaqtning o'zida asosiy va asosiy bo'lmagan o'zgaruvchilar uchun boshqa salbiy qiymatlar yo'q. Optimal yechim topildi.
Raqamli misol
Yaxshiroq tushunish uchun quyidagi raqamli misolni ko'rib chiqing:
quyidagi cheklovlar bilan:
Bo'sh o'zgaruvchilarni qo'shish bilan quyidagi tenglamalarni olish uchun:
Simpleks jadvali quyidagicha olinishi mumkin:
Oxirgi qatorda eng kichik qiymatga ega ustunni tanlash kerak. Ikkita eng kichik qiymat mavjud bo'lsa-da, qaysi biri birinchi bo'lib tanlanganidan qat'iy nazar, natija bir xil bo'ladi. Ushbu yechim uchun birinchi ustun tanlangan. Eng kam koeffitsient topilgandan so'ng, aylanish jarayoni koeffitsientni qidirish orqali amalga oshiriladi���1 . Birinchi qatordagi koeffitsient 1 va ikkinchi qator uchun 4 bo'lganligi sababli, birinchi qatorni burish kerak. Va quyidagi jadval tuzilishi mumkin:
Qator operatsiyasini bajarish orqali 1-ustundagi barcha boshqa satrlar (birinchi qatordan tashqari) nolga teng:
�1�2�3�1�2�3��10,50,50,500011230100422100108−4−1−400010
Oxirgi qatorda bitta salbiy qiymat borligi sababli, xuddi shu jarayonlar yana bajarilishi kerak. Oxirgi qatordagi eng kichik qiymat uchinchi ustunda. Va uchinchi ustunda, ikkinchi qatorda eng kichik koeffitsientlar mavjud
���3bu 1.2. Shunday qilib, ikkinchi qator aylanish uchun tanlanadi. Simpleks jadvali quyidagicha:
Boshqa ustunlarni 0 ga aylantirish uchun satr operatsiyasini bajarish orqali quyidagilar olinishi mumkin:
Qo'shimcha hisob-kitoblarni amalga oshirishning hojati yo'q, chunki oxirgi qatordagi barcha qiymatlar manfiy emas. Yuqoridagi jadvaldan,x1�1, x2 �3va z �Ular asosiy o'zgaruvchilardir, chunki ularning ustunlaridagi barcha satrlar 0 dan iborat bo'lib, bitta satr 1 dan tashqari. Shuning uchun optimal yechim bo'ladi. x1=0.4�1=0.4, x2=0�2=0, x3=1.2�3=1.2, maksimal qiymatga erishish:�=6.4 z=6.4
Simpleks usuli ko'plab dasturlash muammolarida qo'llanilishi mumkin, chunki ular LP (chiziqli dasturlash) ga aylantiriladi va simpleks usuli bilan hal qilinadi. Matematik dasturdan tashqari, boshqa ko'plab sanoat rejalashtirish ushbu usuldan foydani ko'paytirish yoki zarur resurslarni minimallashtirish uchun foydalanadi.
Simpleks usuli har qanday chiziqli programmalashtirish masalasining optimal echimini topishga xizmat qiluvchi eng universal usullardan biridir.
Qishloq va suv xo‘jaligi iqtisodi va uni rejalashtirish, iqtisodiyotning boshqa ko‘p masalalarining optimal echimini topishda bu usuldan foydalanish mumkin.
Ulardan eng asosiylari – qishloq va suv xo‘jaligi korxonalarining optimal ixtisoslashuvini, chorva mollarini oziqlantirish uchun optimal ratsionini hisoblash, ishlab chiqarish korxonalarini joylashtirishning optimal rejasini tuzish.
Qishloq xo’jalik ekinlarini almashlab ekish dalalari bo’yicha optimal joylashtirish, fermer xo’jaligi yer maydonlarining optimal o’lchamini aniqlash va boshqa shunga o’xshash masalarning optimal yechimini topish.
|
| |
