Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularning aniqlash usullari

Masala. Quyidagi chiziqli dasturlash masalasini grafik usulda yeching:


Yechish. Berilgan (L1 ),( L2 ) tengsizliklarga mos tenglamalarni yozamiz:

Berilgan tenglamalarga mos to‘g‘ri chiziqlarni va tengsizliklarga mos yarim tekisliklarni X 1OX 2 koordinatalar tekisligida ifodalab, yarim tekisliklar kesishmasini topamiz (8-rasm)

Bu yerda AC to‘g‘ri chiziqbilan chegaralangan yuqori yarim tekislik L1 tengsizlikni, BC to‘g‘ri chiziq bilan chegaralangan quyi yarim tekislik esa L 2 tengsizlikni ifodalaydi. Bo‘yalgan sohadagi nuqtalarning koordinatalari berilgan masaladagi barcha tengsizliklarni qanoatlantiradi. z maqsad funksiyasi maksimal

qiymatga ABC uchburchakning chegaraviy nuqtalarida erishganligi sababli, optimal yechimni topish uchun A, B, C nuqtalarning koordinatalarini topib, z funksiyasiga qo‘yamiz va ularning ichidan z funksiyaga eng katta qiymat beruvchi nuqtani tanlab olamiz.

8-rasm
S nuqta ( L1 ) va ( L2 ) to‘g‘ri chiziqlarning kesishish nuqtasi bo‘lganligi uchun ushbu tenglamalarni birgalikda yechamiz.

Tenglamalar sistemasidan x1 = 2, x2 = 1 ekanligi kelib chiqadi. U holda A, B ,C nuqtalarning koordinatalari quyidagicha bo‘ladi: A( 0 ,2 ), B( 0 ,3 ), C( 2 ,1 ) .

Ushbu nuqtalarning koordinatalarini maqsad funksiyasiga qo‘yib, quyidagilarni hosil qilamiz:

Yuqoridagilardan ko‘rinib turibdiki z funksiya maksimal qiymatga V nuqtada

erishadi:

Chiziqli dasturlash masalasini amaliy dasturlar yordamida yechish

Chiziqli dasturlash masalasini amaliy dasturlar, masalan PER, Excel, Mathcad dasturlari yordamida ham yechish mumkin. Yuqoridagi masalani Excel elektron jadvali yordamida yechamiz. Buning uchun elektron jadvalda masala koeiffisientlar va ozod hadlarni ikkinchi tengsizliklaridagi va uchinchi satrlarga, z funksiya koifisientlarini to’rtinchi satrga, x1 va x 2 o‘zgaruvchilarning
boshlang‘ich qiymatlarini 0 ga tenglab beshinchi qatorga yozamiz. Natijada jadval quyidagi ko‘rinishga keladi:


Kursorni C2 yacheykaga o‘rnatib f x tugmasini bosamiz. Natijada quyidagi muloqot oynasi hosil bo’ladi:
Hosil bo‘lgan muloqot oynasida «Категория» bo‘limida «Математическое» punktini tanlaymiz, so‘ng «Выберите функцию» bo‘limida «СУМПРОИЗВ» funksiyasini tanlaymiz.


So‘ngra «OK» tugmasini bosamiz. Natijada quyidagi muloqot oynasi hosil bo‘ladi:
Hosil bo‘lgan navbatdagi muloqot oynasida «Массив 1» darchasidagi
tugmachani bosib, A2 : B2 diapazonidagi ma’lumotlarni, «Массив 2» darchasidagi tugmachani bosib, A5 : B5 diapazonidagi ma’lumotlarni kiritamiz, «Массив 2» darchasidagi diapazonni fiksirlash uchun F4 tugmasini bosamiz:

So‘ngra «OK» tugmasini bosamiz va C2 katakda hosil bo‘lgan ma’lumotni

C3 : C4 diapazoniga nusхa qilamiz. Natijada jadval quyidagi ko‘rinishga keladi:

Kursorni maqsad funksiyasi koefitsientlari joylashgan C4 katakka o‘rnatib,

«Сервис - Поиск решения» buyrug’ini beramiz.

Natijada quyidagi «Поиск решения» muloqot oynasi hosil bo‘ladi.

Hosil bo‘lgan muloqot oynasida «Установить целевую ячейку» darchasiga C4 katagini, «Изменяя ячейки» darchasiga A5 : B5 diapazonini kiritamiz.

«Ограничения» darchasiga o‘tib, «Добавить» tugmasini bosamiz va quyidagi oynani hosil bo’ladi:
Hosil bo‘lgan muloqot oynasida «Ссылка на ячейку» darchasiga C2 ni kiritamiz, tengsizlikni aniqlaymiz, «Ограничения» darchasiga E2 ni kiritib,
«Добавить» tugmasini bosamiz.

C5 : E5 diapazondagi munosabatni ham shu tariqa kiritib, «OK» tugmasini bosamiz. Natijada «Поиск решения» muloqot oynasiga qaytamiz:

«Параметры» tugmasini bosamiz. Natijada quyidagi muloqot oynasi hosil bo‘ladi:

Oynadagi «Неотрицательное значение» parametrini belgilaymiz.

«OK» tugmasini bosib, «Поиск решения» muloqot oynasiga qaytamiz va

«Выполнить» tugmasini bosamiz. Natijada quyidagi oynaga o‘tamiz:

«OK» tugmasini bosamiz. Natijada yechim quyidagi ko‘rinishda ifodalanadi:

Ushbu rasmdan ko‘rinib turibdiki, barcha cheklanishlar bajariladi va yechim quyidagi ko‘rinishda bo‘ladi: x1 = 0, x2 = 3, z max = 12.

MathCadda chiziqli dasturlash masalasini yechishda maxsimize va minimize funksiyalaridan foydalaniladi. Bu funksiyalar umumiy ko‘rinishda quyidagicha Yoziladi: MAX() MIN().
MathCadda chiziqli dsturlash masalasini yechish quyidagi amallar
ketma-ketligidan iborat bo‘ladi: MathCad dasturi ishga tushiriladi. Birinchi qatorga maqsad funksiyasi quyidagicha yoziladi: L(х1,х2):=2*х1+4*х2. Navbatdagi qatorga “Given” so‘zi yozilgach, keyingi qatordan quyidagi tengsizliklar sistemasi yoziladi: х1+2*х2≥4 х1+х2≤3 х1≥0 х2≥0 х3≥0. Navbatdagi qatorda o‘zgaruvchilarning boshlang‘ich qiymatlari yoziladi: х1:=0 х2:=3 So‘ng quyidagi operator kiritiladi: p:=Maxsimize(L,х1,х2). Optimal yechimni beruvchi o‘zgaruvchilarning qiymatlari r= operatori yordamida, maqsad funksiyasining optimal qiymati esa L(p0,p1)= operatori yordamida hosil qilinadi. MathCadda masalaning dasturi quyidagicha bo’ladi:
Natija quyidagicha bo‘ladi: x 1 = 0, x 2 = 3, z max = 12.