Chiziqli dasturlash masalasini yechishning Simpleks usuli
Ma’lumki, chiziqli dasturlash masalasi umumiy holda simpleks usulda echiladi. CHiziqli dasturlash masalasini simpleks usulda echish ikki bosqichdan iborat bo’lib, birinchi bosqichda masalaning tayanch echimi, ikkinchi bosqichda esa optimal echim topiladi.
Tayanch echimni topish qoidasi quyidagicha:
1) (5.4.1)-(5.4.3) masalani quyidagi
ko’rinishga keltiramiz.
2) Yuqoridagi munosabatlardan quyidagi simpleks jadvalini tuzamiz:
3) Ozod sonlar ustunidagi manfiy sonlarni qaraymiz. Agar ushbu sonlarning hammasi musbat bo’lsa, u holda masalaning tayanch echimi topilgan hisoblanadi. Agar ozod sonlar orasida bir nechta manfiy sonlar mavjud bo’lsa, ulardan birini tanlaymiz. Faraz qilaylik
l- satrdagi al 0 ozod sonni tanlab olaylik.
4) l- satrdagi manfiy sonlarni qaraymiz. Agar ushbu satrda manfiy sonlar bo’lmasa, masala echimga ega bo’lmaydi, agar manfiy sonlar bir nechta bo’lsa, ulardan birini tanlaymiz Masalan,k- ustundagi alk 0 sonni tanlab olaylik .k- ustun hal qiluvchi ustun deyiladi.
5) Ozod sonlar va k -ustundagi mos koifisientlar juftliklarini qaraymiz. Agar ularning ishoralari bir хil bo’lsa, ozod sonlarni mos koifisientlarga bo’lamiz.
6) Hosil bo’lgan nisbatlarning eng kichigini tanlab olamiz:
Bu erda - tanlab olingan juftliklar soni. ga mos keluvchi k ustundagi element bosh element deyiladi. Agar bosh element j - satrga mos kelsa aka - bosh element bo’ladi, j - satr hal qiluvchi satr deyiladi. Jadval quyidagi ko’rinishga keladi:
7) a k a elementga nisbatan simpleks almashtirishlarini bajarib navbatdagi jadvalni to’ldiramiz:
7.1) Hal qiluvchi satr va ustundagi o’zgaruvchilar o’rni almashtiriladi;
7.2) Bosh element o’rniga unga teskari sonni yozamiz;
7.3) Hal qiluvchi satr elementlarini bosh elementga bo’lib, mos kataklarga yozamiz;
7.4) Hal qiluvchi ustun elementlarini bosh elementga bo’lib, ishorasini qaramaqarshisiga o’zgartiramiz va mos kataklarga yozamiz;
7.5) Qolgan kataklar to’rtburchak qoidasi bo’yicha to’ldiriladi. Masalan, (2.2) katakni to’ldirish uchun quyidagi hisoblash bajariladi:
Natijada jadval quyidagi ko’rinishga keladi:
8) So’ngra 3)-6) punktlar barcha ozod sonlar musbat bo’lguncha yoki masalaning echimi mavjud emasligi aniqlangunga qadar takrorlanadi. Tayanch echim topilgach optimal echimni topishga o’tish mumkin. Buning uchun quyidagi amallar bajariladi:
1) z satrdagi manfiy sonlar qaraladi. Agar manfiy sonlar bo’lmasa, optimal echim topilgan hisoblanadi va 1 - ustundagi x o’zgaruvchilar va z ularga mos ozod sonlarga, 1- satrdagi x o’zgaruvchilar esa nolga tenglashtiriladi. Agar z satrda bir nechta manfiy sonlar bo’lsa, ulardan eng kichigi tanlanadi. Masalan eng kichik manfiy koifisient c2 bo’lsin.
2) 2- ustundagi musbat sonlarni tanlaymiz. Agar ushbu ustunda musbat sonlar bo’lmasa, masalaning optimal echimi cheksizlikka intiladi. Agar ustunda musbat sonlar bo’lsa, ularga mos ozod sonlarni bo’lib, eng kichik nisbatni tanlab olamiz:
Bu erda - tanlab olingan juftliklar soni.
3) Eng kichik nisbatga mos element bosh element hisoblanadi va unga nisbatan simpleks almashtirishlari bajariladi.
4) 1)-3) punktlar z qatordagi barcha sonlar musbat bo’lguncha yoki masalaning echimi yuqoridan chegaralamaganligi aniqlanguncha davom ettiriladi.
Agar maqsad funksiyasida
bo’lsa, u holda masala koifisientlar ishoralari o’zgartirilib, maksimumga keltiriladi:
va masala yuqoridagi usul bilan echiladi.
|
