Chiziqli dasturlash masalalarining simpleks usulda yechilishi

Chiziqli dasturlash masalalarining simpleks usulda yechilishi

Masalaning qo’yilishi ayrim injeneriya masalalarini echish, shu jumladan qishloq va suv xo`jaligida energiya ta’minoti, texnologik jarayonlarni avtomatlashtirish va boshqarish, mehnat muhofazasi va texnika xavfsizlik masalalari chiziqli dasturlash masalalarini echishga keltiriladi. Chiziqli dasturlash masalasi umumiy holda quyidagi ko’rinishda bo’ladi:

bu erda (5.6.1) maqsad funksiyasi, (5.6.2) cheklanishlar sistemasi, (5.6.3) nomanfiylik sharti deyiladi. Masalada o’zgaruvchilarning shunday qiymatlarini topish kerakki, ular (5.6.2) va(5.6.3) shartlarni qanoatlantirsin hamda (5.6.1) funksiya maksimal (minimal) qiymatni qabul qilsin. Ushbu masalani umumiy holda simpleks usulda, o’zgaruvchilar soni ikkita bo’lgan holda esa, grafik usulda echish mumkin.

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 - satrdagi ozod sonni tanlab olaylik.

4) - 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, - ustundagi sonni tanlab olaylik. - ustun hal qiluvchi ustun deyiladi. 5) Ozod sonlar va -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 -ustundagi element bosh element deyiladi. Agar bosh element - satrga mos kelsa - bosh element bo’ladi, - satr hal qiluvchi satr deyiladi. Jadval quyidagi ko’rinishga keladi:

7) elementga nisbatan simpleks almashtirishlarini bajarib navbatdagi jadvalni to’ldiramiz:

7) 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: .

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) satrdagi manfiy sonlar qaraladi. Agar manfiy sonlar bo’lmasa, optimal echim topilgan hisoblanadi va 1 - ustundagi o’zgaruvchilar va ularga mos ozod sonlarga, 1- satrdagi o’zgaruvchilar esa nolga tenglashtiriladi. Agar satrda bir nechta manfiy sonlar bo’lsa, ulardan eng kichigi tanlanadi. Masalan eng kichik manfiy koifisient 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:.

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 k- tanlab olingan juftliklar soni.

3) Eng kichik nisbatga mos element bosh element hisoblanadi va unga nisbatan simpleks almashtirishlari bajariladi.

4) 1)-3) punktlar 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. Natijada bo’ladi.