Simplex usuli algoritmi bir necha bosqichlardan iborat

Chiziqli dasturlash masalalarini yechishning simpleks usuli algoritmi va uni tahlil qilish. Hisoblash geometriyasi.
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.

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.
Ikkinchi bosqich Ushbu iteratsiyada ushbu raqamga ega bo'lgan soddalashtirilgan jadvalning ustuni umumiy ustun deb nomlanadi.
Uchinchi bosqich Umumiy satrni topish uchun barcha bo'sh a'zolar (manbalar) umumiy ustunning tegishli elementlariga bo'linadi (bir birlik uchun resursni sarflash darajasi). Olingan natijalardan eng kichigi tanlanadi. Ushbu iteratsiyada tegishli chiziq umumiy deb nomlanadi. Ushbu berilgan iteratsiyada ishlab chiqarishni cheklaydigan resursga mos keladi.
Tortinchi bosqich Umumiy ustun va satr chorrahasida joylashgan soddalashtirilgan jadvalning elementi umumiy element deyiladi.
Beshinchi bosqich. Olingan asosiy yechim optimalligi tekshiriladi (uchinchi bosqichga qarang). Agar u eng maqbul bo'lsa, hisob-kitoblar to'xtaydi. Aks holda, yangi asosiy yechimni (to'rtinchi bosqich) va boshqalarni topish kerak.
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 x 0, 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.