|
Chiziqli programmalashtirish masalasini grafik usulda yechish algoritmi
|
| bet | 3/5 | | Sana | 14.09.2024 | | Hajmi | 0,59 Mb. | | #271032 |
Bog'liq B.M. 1-маърузаChiziqli programmalashtirish masalasini grafik usulda yechish algoritmi
Masalaning chegaraviy shartlaridan, uning mumkin bo‘lgan yechimlar sohasi aniqlanadi.
vektorni quramiz.
vektorga perpendikulyar bo‘lgan, sath chizig‘i o‘tkaziladi.
Maksimum masalada, sath chizig‘i vektor yo‘nalishi bo‘yicha, minimum masalada esa vektor yo‘nalishiga qarama-qarshi suriladi. Bu surish, sath chizig‘i bilan mumkin bo‘lgan yechimlar sohasining yagona umumiy nuqtasi hosil bo‘lguncha, davom ettiriladi. Bu nuqta, mumkin bo‘lgan yechimlar sohasida, maqsad funksiyaning ekstremum nuqtasi bo‘ladi, ya’ni chiziqli programmalashtirish masalasining optimal yechimidir.
Maqsad funksiyaning qiymatini, ekstremum nuqtalarning koordinatalari orqali aniqlaymiz.
Agar sath chizig‘i, mumkin bo‘lgan yechimlar sohasining biror tomoniga parallel bo‘lsa, u holda chiziqli programmalashtirish masalasi cheksiz yechimlar sohasiga ega.
Agar mumkin bo‘lgan yechimlar sohasi, cheksiz soha bo‘lsa, maqsad funksiya chegaralanmagan bo‘ladi.
Mumkin bo‘lgan yechimlar sohasining chegaraviy shartlari qarama-qarshi bo‘lsa, chiziqli programmalashtirish masalasi yechimga ega emas.
Chiziqli programmalashtirish masalasining optimal yechimini aniqlashda quyidagi vaziyatlar bo‘lishi mumkin:
masala yagona yechimga ega (1.3.2-rasm);
masala cheksiz ko‘p yechimlar to‘plamiga ega (1.3.3-rasm);
F funksiya yuqoridan chegaralangan emas, ya’ni ekstremal qiymatga ega emas (1.3.4-rasm);
masalaning chegaraviy shartlari birgalikda emas, ya’ni mumkin bo‘lgan yechimlar sohasi bo‘sh to‘plamdan iborat (1.3.5-rasm).
0
|
| |
