Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili

Masalaning optimal yechimni topish. Agar 1-bosqichdan olingan tayanch yechimning simpleks jadvaldagi -satr elementlari (ozod hadi dan tashqari) hammasi musbat bo‘lsa, bu olingan boshlang‘ich tayanch yechim yagona va u masalaning optimal yechimi (yechimi) bo‘ladi. Agar satrdagi hamma musbat elementlaridan kamida bittasi nolga teng bo‘lsa, u holda masalaning cheksiz ko‘p optimal yechimi mavjud bo‘ladi.
Agar satrdagi elementlardan hech bo‘lmaganda bittasi manfiy bo‘lsa, optimal yechim quyidagi algoritim bo‘yicha topiladi:
1. Hal qiluvchi elementni topish.
1.1. Hal qiluvchi ustun topiladi. -qatordagi manfiy elementlarning modul bo‘yicha eng kattasi (bitta bo‘lsa o‘zi) tanlanadi. Shu element turgan ustun hal qiluvchi ustun bo‘ladi.
1.2. Hal qiluvchi satr topiladi. Ozod hadlar elementlari hal qiluvchi ustun elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi olinadi, ya’ni birinchi bosqichning 1.2-punktidagi kabi. Bu songa mos keluvchi ustundagi element hal qiluvchi element va shu element turgan satr esa hal qiluvchi satr bo‘ladi.
2. Hal qiluvchi satr va ustun o‘zgaruvchilari o‘z joylarini almashtiradi (agarda hali ular almashtirilmagan bo‘lsa).
3. Jadvalda simpleks almashtirish bajariladi. Simpleks almashtirish 1- bosqichdagi 3.1, 3.2, 3.3, 3.4 punktlar kabi bajariladi.
4. Yangi topilgan jadvalning satri qaraladi. Agar qatordagi hamma elementlar musbat bo‘lsa, olingan oxirgi yechim masalaning optimal yechimi bo‘ladi. Aks holda yuqoridagi 1,2,3-punktlar yana takrorlanadi, toki optimal yechim topilguncha.
Eslatma: Chiziqli dasturlash masalasida, agar maqsad funktsiyasining minumimi izlansa yuqoridagi 1-chi bosqich to‘lig‘icha o‘rinli bo‘lib, 2-bosqichda esa faqat qator elementlari manfiy holatga keltirilishi kerak, ya’ni teskari holat bo‘ladi

1-misol: chiziqli funktsiyaga maksimum qiymat beruvchi





chegaraviy sistemasining mumkin bo‘lgan yechimlari sohasida noma’lumlar topilsin.