О‘zbekiston respublikasi oliy va о‘rta maxsus ta’lim vazirligi navoiy davlat konchilik instituti

Optimatlashtirishning chiziqli programmalashtirish usuli

Ko’p hollarda maqsadli funksiya quyidagi turdagi o’z parametrlariga nisbatan chiziqli funksiyalarda ifodalanadi

Agar bunday hollar uchun mavjud oblastli va chegaraviy funksiyalar ham:

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

Maqsadli funksiyadagi parametrlar soni ikkita yoki uchta bo’lsa masalani eng oson grafik usulda echish mumkin.
Misol sifatida quyidagini ko’raylik:
(maqsadli funksiya)
(chegaraviy funksiya)
(cheklanishlar)
koordinatalar tekisligida avvalo chegaraviy funksiya grafigini yasaymiz (15-rasm):
Ko’rinib turibdiki, chegaraviy funksiya va cheklanishlar shartlaridan OAB 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 funksiyalar soniga ega bo’lib, ko’pburchaklarda tasvirlanadi va optimal echim shu ko’pburchaklarning biror uchida joylashgan bo’ladi. Ko’rilayotgan misol uchun:

15-rasm. Chiziqli programmalashtirish usuliga doir

O nuqtada

A nuqtada
B nuqtada
Demak, maqsadli funksiyani maksimallashtiruvchi optimal echim A nuqtada bo’lar ekan. Masalani grafik usulda echganda, berilgan koordinatalar tekisligida maqsadli funksiyaning grafigi chiziladi va o’ziga parallel holatda maksimallashtirish masalasida o’sish tomonga, minimallashtirish masalasida esa kamayish tomonga siljitib boriladi.
Bu siljitishlardagi maqsadli funksiya 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 kompyuterda echish maqsadga muvofiqdir.