Reja Chiziqli dasturlash masalalarini simpleks usuda ifodalanishi
Download 6.63 Kb.
|
9-ma’ruza
- Bu sahifa navigatsiya:
- Misol .
9-ma’ruza
Reja
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).
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 .
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. Download 6.63 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling