Chiziqli programmalashtirishning masalalari. Optimatlashtirishning chiziqli programmalashtirish

Chiziqli programmalashtirishning masalalari.
Optimatlashtirishning chiziqli programmalashtirish
usuli
Ko’p qollarda maqsadli funktsiya quyidagi tipdagi o’z parametrlariga nisbatan chiziqli funktsiyalarda ifodalanadi
I = CxXx + C = X2 +... + CnXn ^ min (max)
Agar bunday hollar uchun mavjud oblastli va chegaraviy funktsiyalar ham:
X >a;X >a;...X >a
1 ’ 2 ’ n
a i X + a 9 X9 +... + a X < b
11 1 12 2 n n 1
am1X1 + a
9 +... + a 9 X ^ b ;
m2 2 m2 n m ?
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:
J = 3xx _5x2 (maqsadli funktsiya)
2x + 4x2 < 8 (chegaraviy funktsiya)
xx, x2 > 0 (cheklanishlar)
X 0x2 koordinatalar tekisligida avvalo chegaraviy funktsiya grafigini
yasaymiz (15-rasm):
15-rasm. Chiziqli programmalashtirish usuliga doir.
Ko’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. Ko’rilayotgan misol uchun:
O nuqtada Jo 3 * 0 + 5 * 0 = 0
A nuqtada JA = 3 * 4 + 5 * 0 = 12
V nuqtada JB = 3 * 0 + 5 * 2 = 10
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 Jmax uchburchakni A nuqtada tark etadi, ya’ni echim shu nuqtada bo’ladi
2110
= 4,X 2110 = 0) •
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 EXM da echish maqsadga muvofiqdir.
Yuqorida ko’rilgan masalalarning barchasida maqsadli va chegaraviy munosabatlar aniqlanishi kerak bo’lgan parametrga nisbatan funktsiyalar sifatida berilgan edi.
TS ni loyihalashda, ba’zi hollarda maqsadli munosabatlar va chegaraviy munosabatlar funktsiyalar emas funktsionallar sifatida ifodalanadi. Bunday masalalarning optimal echimlarini aniqlash uchun variatsion hisoblash usulidan foydalangan maqsadga muvofiq.
Aytaylik, x, u dy/dx o’zgaruvchilarga ega bo’lgan ikki marta differentsiallanuvchi F funktsiya va uning x1 x2 orasidagi aniq integrali
berilgan bo’lsin va shu integralni optimallashtiruvchi y=u(x) funktsiyani topish kerak bo’lsin.