|
Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili
|
| bet | 1/4 | | Sana | 19.05.2024 | | Hajmi | 32,71 Kb. | | #243681 |
Bog'liq 7-ma\'ruza (9)
Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili
CH.D.M. grafik usulda mumkin bo‘lgan yechimlarni qirralar va ularni tutashtiruvchi chiziqlardan tashkil topgan qavariq sohadan olinadi. Optimal yechimga esa ushbu qavariq sohaning ba’zi qirralarida erishamiz. Agar optimal yechim unikal bo‘lmasa, optimal nuqtalar uning chegaralarida joylashadi. Bunday kuzatishlar umumiy CH.D.M.siga ham tegishli. Aslida muammo optimal yechimga mos keladigan uchni (qavariq sohaning tomonini) topishdan iborat. Optimal yechimni (optimal uchni) joylashishini aniqlashning eng ko‘p qo‘llaniladigan usuli bu simpleks usul hisoblanadi.
Yuqorida aytganimizdek, chiziqli dasturlash masalasining optimal yechimini uning barcha yechimlaridan tashkil topgan qavariq to‘plamning chetki nuqtalari orasidan qidirish kerak. Bunday nuqtalar soni yoki boshqacha aytganda tayanch yechimlar soni dan tadan tuzilgan gruppalash orqali aniqlanadi. Masaladagi noma’lumlar soni dan tenglamalar soni katta bo‘lganda barcha (mumkin bo‘lgan) tayanch yechimlarning optimalligini tekshirib chiqish ancha qiyin bo‘ladi. Shuning uchun tayanch yechimlarni tartib bilan tekshirib chiqib, ular ichidan optimal yechimni aniqlab beruvchi yechish sxemasining berilishi talab qilinadi.
Chiziqli dasturlash masalasini yechishning bunday sxemalaridan biri bu Simpleks usulidir. Bu usul boshlang‘ich tayanch yechimdan chekli sondagi iteratsiyadan keyin optimal yechimni hosil qilish yo‘lini ko‘rsatadi va har bir navbatdagi iteratsiya oldingisiga nisbatan optimal yechimga yaqinroq yechimni beradi. Yechish jarayoni optimal yechim topilguncha yoki masalaning chiziqli funktsiyasi chekli ekstremum qiymatga ega emasligi aniqlanguncha davom ettiriladi. Bu usul hozirgi kunda keng miqiyosda ishlatilib kompyuterlar uchun uning amaliy paket dasturlari ishlab chiqilgan.
Simpleks jadval tuzish. Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo‘lib, ketma ket yaqinlashish usuli yordamida o‘zgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funktsiyasigi maksimal (yoki minimal) qiymat beradi.
Quyidagi funktsionalga maksimum qiymat beruvchi chiziqli dasturlash masalasi berilgan bo‘lsin.
Masalani yechish uchun simpleks jadval quramiz va simpleks usuli g‘oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.
Bu yerda - bazis o‘zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o‘zgaruvchilardan farqlash uchun mos ravishda deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz Bu belgilashlar asosida simpleks jadval tuzamiz.
Bazis o‘zgaruvchilar
|
1
|
|
|
...
|
|
...
|
|
|
|
|
|
...
|
|
...
|
|
|
|
|
|
...
|
|
...
|
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
|
|
|
|
...
|
|
...
|
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
|
|
|
|
...
|
|
...
|
|
|
|
|
|
...
|
|
...
|
|
Chiziqli dasturlash masalasini simpleks usul yordamida yechish ikki bosqichdan iborat:
1-bosqich. Boshlang‘ich tayanch yechimni topish.
2-bosqich. Tayanch yechimlar ichidan masalaning optimal yechimini topish.
|
| |
