Chiziqli programmalashtirishning masalalari. Optimatlashtirishning chiziqli programmalashtirish usuli

Chiziqli programmalashtirishning masalalari.
Optimatlashtirishning chiziqli programmalashtirish usuli
Кo’p qollarda maқsadli funktsiya quyidagi tipdagi o’z parametrlariga nisbatan chiziqli funktsiyalarda ifodalanadi

Agar bunday hollar uchun mavjud oblastli va chegaraviy funktsiyalar ham:

chiziqli funktsiyalar bo’ladigan bo’lsa, bunday masalalar matematikada chiziqli programmalashtirish masalalari deb ataladi.

Maqsadli funktsiyadagi parametrlar soni ikkita yoki uchta bo’lsa masalani eng oson grafik usulda echish mumkin.
Misol sifatida quyidagini ko’raylik:
(maqsadli funktsiya)
(chegaraviy funktsiya)
(cheklanishlar)
koordinatalar tekisligida avvalo chegaraviy funktsiya grafigini yasaymiz (15-rasm):


15-rasm. Chiziqli programmalashtirish usuliga doir.

Кo’rinib turibdiki, chegaraviy funktsiya va cheklanishlar shartlaridan OAV burchagi kelib chiqadi, ruxsat etilgan echimlar oblasti esa shu uchburchak bilan chegaralangan bo’ladi (shtrixlangan oblast). Shu joyda aytib o’tish kerakki, umuman olganda, ruxsat etilgan echimlar oblasti parametrlarda ifodalangan chegaraviy funktsiyalar soniga ega bo’lib, ko’pburchaklarda tasvirlanadi va optimal echim shu ko’pburchaklarning biror uchida joylashgan bo’ladi. Кo’rilayotgan misol uchun:

O nuqtada
A nuqtada
V nuqtada
Demak, maqsadli funktsiyani maksimallashtiruvchi optimal echim A nuqtada bo’lar ekan. Masalani grafik usulda echganda, berilgan koordinatalar tekisligida maqsadli funktsiyaning grafigi chiziladi va o’ziga parallel holatda maksimallashtirish masalasida o’sish tomonga, minimallashtirish masalasida esa kamayish tomonga siljitib boriladi.
Bu siljitishlardagi maqsadli funktsiya chizig’ining ruxsat etilgan oblast ko’pburchagining eng so’ngida tark etgan uchi optimal echim koordinatasi bo’ladi. Misolda J_max uchburchakni A nuqtada tark etadi, ya’ni echim shu nuqtada bo’ladi .
Agar parametrlar soni uchta bo’lsa masalani fazodagi grafik tasvirlarda echishga to’g’ri keladi va optimallashtirishning bu usulini qo’llanish qiyinchiliklarga olib keladi. Amalda ko’p parametrli masalalarni chiziqli programmalashtirish usulida echishda iteratsion-hisoblash usullari qo’llaniladi. Bunday usullardan biri bo’lgan simpleks usuli [3] da tavsiflangan.
Chiziqli programmalashtirish masalalarini echishning ham maxsus amaliy dasturlar to’plami mavjud. Dasturlar to’plami yordamida bunday masalalarni EҲM da echish maqsadga muvofiqdir.