Reja Chiziqli dasturlash masalalarini simpleks usuda ifodalanishi

9-ma’ruza

Simpleks usulida topilgan yechimning iqtisodiy tahlili. Xulosa va takliflar. Qavariq korpuslarni qurish usullari.

Reja

• Chiziqli dasturlash masalalarini simpleks usuda ifodalanishi.
• Masalalarini yechishda simpleks usul algoritmi va uning tahlili

Simplus usuli - bu bitta tayanch punktdan (asosiy echim) boshqasiga o'tishda ketma-ket yaxshilanadigan echimlar printsipiga asoslangan hisoblash jarayoni. Bunday holda, ob'ektiv funktsiyaning qiymati yaxshilanadi.

Simplus usuli - bu bitta tayanch punktdan (asosiy echim) boshqasiga o'tishda ketma-ket yaxshilanadigan echimlar printsipiga asoslangan hisoblash jarayoni. Bunday holda, ob'ektiv funktsiyaning qiymati yaxshilanadi.

Asosiy yechim qabul qilinadigan qiymatlar mintaqasining uchida joylashgan yo'l qo'yiladigan yechimlardan biridir. Simpeks cho'qqisi orqasidagi eng maqbulligini tekshirib, biz kerakli yechimga erishamiz. Simplus usuli ushbu printsipga asoslanadi.

Asosiy yechim qabul qilinadigan qiymatlar mintaqasining uchida joylashgan yo'l qo'yiladigan yechimlardan biridir. Simpeks cho'qqisi orqasidagi eng maqbulligini tekshirib, biz kerakli yechimga erishamiz. Simplus usuli ushbu printsipga asoslanadi.

Simpleks n-o'lchovli bo'shliqda n + 1 uchlari bilan bir xil giperpadonda yotmaydigan konveks ko'pburchakdir (giperplet bo'shliqni ikki yarim bo'shliqqa ajratadi).

• Simpleks n-o'lchovli bo'shliqda n + 1 uchlari bilan bir xil giperpadonda yotmaydigan konveks ko'pburchakdir (giperplet bo'shliqni ikki yarim bo'shliqqa ajratadi).
• Masalan, byudjet cheklovlari qatori imtiyozlarni arzon va mavjud bo'lmaganlarga ajratadi.
• Agar maqbul echim mavjud bo'lsa, u "loop" holatlaridan tashqari, cheklangan iteratsiyalar (qadamlar) da aniqlanishi isbotlangan.

Simplex usuli algoritmi bir necha bosqichlardan iborat. Birinchi bosqich. Dastlabki optimallashtirish modeli qurilmoqda. Bundan tashqari, shartlarning boshlang'ich matritsasi qisqartirilgan kanonik shaklga aylantiriladi, bu boshqa barcha kanonik shakllar orasida quyidagicha ajralib turadi: a) shartlarning o'ng tomonlari: manfiy bo'lmagan miqdorlardir; b) shartlarning o'zi tenglikdir; c) shartli matritsada to'liq birlik submatrix mavjud.

Agar erkin atamalar manfiy bo'lsa, tengsizlikning ikkala tomoni -1 ga ko'paytiriladi va tengsizlik belgisi teskari bo'ladi. Tengsizliklarni tenglikka aylantirish uchun, odatda foydalanilmaydigan manbalar miqdorini ko'rsatadigan qo'shimcha o'zgaruvchilar kiritiladi. Bu ularning iqtisodiy ma'nosi.

Agar erkin atamalar manfiy bo'lsa, tengsizlikning ikkala tomoni -1 ga ko'paytiriladi va tengsizlik belgisi teskari bo'ladi. Tengsizliklarni tenglikka aylantirish uchun, odatda foydalanilmaydigan manbalar miqdorini ko'rsatadigan qo'shimcha o'zgaruvchilar kiritiladi. Bu ularning iqtisodiy ma'nosi.

Va nihoyat, agar qo'shimcha parametrlarni qo'shgandan so'ng, shartli matritsada to'liq birlik submatrix bo'lmasa, unda iqtisodiy ma'noga ega bo'lmagan sun'iy o'zgaruvchilar kiritiladi. Ular faqat bitta submatrixni olish va soddalashtirish usulidan foydalanib muammoni hal qilish jarayonini boshlash uchun kiritilgan.

Va nihoyat, agar qo'shimcha parametrlarni qo'shgandan so'ng, shartli matritsada to'liq birlik submatrix bo'lmasa, unda iqtisodiy ma'noga ega bo'lmagan sun'iy o'zgaruvchilar kiritiladi. Ular faqat bitta submatrixni olish va soddalashtirish usulidan foydalanib muammoni hal qilish jarayonini boshlash uchun kiritilgan.

Misol .

• Misol .
• Z = 2x + 3y maqsad funksiyasining maksimum qiymatini toping.
• Chegaraviy shartlar quyidagicha berilgan:
• x + y 30, y 3, 0 y 12, x - y 0, va 0 x 20.
•  
• Yechish
• Birinchi navbatda koordinatalar sistemasida x0, y 0 ekanligini belgilab olamiz.
• Koordinatalar sistemasida x + y 30, y 3, y 12, x y va x 20, chegaralarni belgilab, ABCDE shaklni aniqlaymiz.
• Shakl uchlaridagi nuqtalar A(3, 3), B (20, 3), C(20, 10), D(18, 12) va E(12, 12) bo’ladi.
• Shakl uchlaridagi Z ning qiymatlari Z(A) = 15, Z(B) = 49, Z(C)= 70, Z(D)=72, va Z(E) = 60
• D nuqtada Z maksimum qiymatga erishadi. Z(D)=72. Bu nuqtada x va y ning qiymatlari x = 18, y = 12 ga teng.

•  

Asosiy adabiyotlar
1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы построение и анализ. Москва-Санкт-Петербург- Киев. Изд. дом “Вильямс”, 2005. 1293 стр.
2. Levetan Anany. Introduction to The Design & Analisis of Algorithms. 3rd ed. Villanova university.New Jersiy. 2012. 693 page.
3. Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2014. 384 стр.
4. Стивен Скиены. Алгоритмы. Руководство по разработке. Питер 2011. 715 стр.
Qo’shimcha adabiyotlar
1. Computer Algorithms by Horowits E., Sahni., Rajasekaran S., Galgotia Publications, 2001.