Чизиқли дастурлаш масаласи

_{ЧИЗИҚЛИ} ДАСТУРЛАШ МАСАЛАСИ

5.6.1. Masalaning qo’yilishi

Ayrim injeneriya masalalarini echish, shu jumladan qishloq va suv xo`jaligida energiya ta’minoti, texnologik jarayonlarni avtomatlashtirish va boshqarish, mehnat muhofazasi va texnika xavfsizlik masalalari chiziqli dasturlash masalalarini echishga keltiriladi. Chiziqli dasturlash masalasi umumiy holda quyidagi ko’rinishda bo’ladi:

z  с₁ x₁  с₂ x₂ ...  с_n x_n
 max(min)
(5.6.1)


^{a11x1  a12 x2 ...  a1n xn  a1}

a
^ 21 ^x1

 a₂₂
x₂ ...  a x

(5.6.2)

_...................
^_a x

x₁  0,
x₂  0,..., x_n  0
(5.6.3)

bu erda (5.6.1) maqsad funksiyasi, (5.6.2) cheklanishlar sistemasi, (5.6.3) nomanfiylik sharti deyiladi.

Masalada
x₁ , x₂ ,, x_n
o’zgaruvchilarning shunday qiymatlarini topish kerakki,

ular (5.6.2) va(5.6.3) shartlarni qanoatlantirsin hamda (5.6.1) funksiya maksimal (minimal) qiymatni qabul qilsin.

Ushbu masalani umumiy holda simpleks usulda, o’zgaruvchilar soni ikkita bo’lgan holda esa, grafik usulda echish mumkin.

6.6.2. Grafik usul

Agar (5.6.1)-(5.6.3) masalada o’zgaruvchilar soni ikkita bo’lsa, bu masala quyidagi ko’rinishga keladi:

^{z  с}₁ ^x₁ ^{ с}₂ ^x₂ ^{ max(min)}(5.6.4)


_a₁₁ x₁  a₁₂ x₂  a₁

a
^ 21 ^x1

 a₂₂ x₂
 a₂

(5.6.5)

_..........................
^^am1 ^x1 ^{ a}m 2 ^x2 ^{ a}n

x₁  0,
x₂  0
(5.6.6)

(5.6.4) –(5.6.6) masalani grafik usulda echishni ko’rib chikamiz. (5.6.5) va (5.2.3) shartlarni qanoatlantiruvchi echimlar echimlar ko’pburchagi deyiladi.
Teorema. Maqsad funksiyasi o’zining optimal qiymatiga echimlar qo’pburchagining chegara nuqtalarida erishadi.
Chiziqli dasturlash masalasini grafik usulda echish quyidagi tartibda bajariladi:

1) Berilgan masaladagi tengsizliklarga mos tenglamalarni tuzamiz va ularni mos ravishda

a₁₁ x₁  a₁₂ x₂  a₁ a₂₁ x₁  a₂₂ x₂  a₂
.........................
a_m1 x₁  a_{m 2} x₂  a_n x₁  0
x₂  0
(L₁ )
(L₂ )


(L_m )
(L_m1 )
(L_m2 )

bilan belgilaymiz.

2) ^(L₁ ^{), (L}₂ ^{), , (L}_m2 ⁾

tenglamalar bilan berilgan chiziqlarni
X ₁OX ₂

koordinatalar tekisligida ifodalaymiz (6.5-rasm).

5.5-rasm

3. 
   (5.6.2) da berilgan tengsizliklarga mos yarim tekisliklarni aniqlaymiz (5.6- rasm).
   

5.6-rasm

Rasmdagi har bir to’g’ri chiziq grafigiga qo’yilgan strelkalar (5.6.2)-(5.6.3) tengsizliklarga mos yarim tekisliklarni aniqlaydi.

3. 
   Yarim tekisliklarning kesishmasini qaraymiz. Agar kesishma ko’pburchakdan iborat bo’lsa, masalaning echimi chekli qiymatga ega bo’ladi. Ushbu ko’pburchak echimlar ko’pburchagi bo’lib, uning iхtiyoriy nuqtasi berilgan (5.6.2)-(5.6.3) tengsizliklar sistemasini qanoatlantiradi (5.7-rasm).
   

5.7-rasm

Agar kesishma bo’sh to’plam bo’lsa, masala echimga ega bo’lmaydi (5.8-rasm).

5.8-rasm

Kesishma bo’sh to’plam bo’lmagan holda masalaning optimal echimini topish uchun o’zgaruvchilarning shunday qiymatlarini topish kerakki, ushbu qiymatlarda z maqsad funksiyasi eng katta (eng kichik) qiymatga erishsin. Bunday qiymatlar echimlar ko’pburchagining chegaraviy nuqtalarida bo’ladi. Agar optimal echim ko’pburchakning bitta uchida bo’lsa, echim yagona bo’ladi, aks holda masala cheksiz ko’p echimga ega bo’lib, ular ko’pburchakning optimal echim qabul qiladigan uchlarining chiziqli kombinaцiyalaridan iborat bo’ladi.
Agar yarim tekisliklar kesishmasi cheksiz soha bo’lsa, masala echimining qiymati yuqoridan chegaralanmagan bo’lishi mumkin (5.9-rasm).

5.9-rasm

Agar kesishma bo’sh to’plam bo’lmasa, optimal echim ikki хil usulda aniqlanadi.

Birinchi usul:

1. 
   Echimlar ko’pburchagi uchlarining koordinatalari aniqlanadi.
   
2. 
   Aniqlangan koordinatalar z funksiyasiga qo’yiladi.
   
3. 
   Hosil bo’lgan qiymatlarning eng katta yoki eng kichigi topiladi. Ikkinchi usul:
   

1. 
   
   1
   
   2
   n^c ,c ^ normal vektor chiziladi.
   

2. 
   Normal vektorga perpendikulyar bo’lgan
   

z  0
to’g’ri chiziq chiziladi

(5.10-rasm).

3) ^{z  0}
5.10-rasm

to’g’ri chiziq normalь bo’ylab o’ziga nisbatan parallel holda suriladi.

4) Parallel surish jarayonida
z  0
to’g’ri chiziq echimlar ko’pburchagiga

urinadigan birinchi kiruvchi nuqtada masala minimal echimga ega bo’ladi, oхirgi chiquvchi nuqtada maksimal echimga ega bo’ladi.

Masalan, quyidagi 5.11-rasmda erishadi.
z funksiya
A( x,
nuqtada maksimal qiymatga

5.11-rasm

Masala. Quyidagi chiziqli dasturlash masalasini grafik usulda eching:

z  2x₁  4x₂
 max

_x₁  2x₂  4 L₁
^x  x  3 L
^ 1 2 2
^x  0, x  0
 1 2

Echish. Berilgan (L₁ ),( L₂ )
tengsizliklarga mos tenglamalarni yozamiz:

_x₁  2x₂  4 (L₁ )

^x  x  3
(L )

 1 2 2

Berilgan tenglamalarga mos to’g’ri chiziqlarni va tengsizliklarga mos yarim

tekisliklarni
X ₁OX ₂
koordinatalar tekisligida ifodalab, yarim tekisliklar kesishmasini

topamiz (5.12-rasm).

Bu erda tengsizlikni,
^AC to’g’ri chiziq bilan chegaralangan yuqori yarim tekislik L₁
^BC to’g’ri chiziq bilan chegaralangan quyi yarim tekislik esa ^L2

tengsizlikni ifodalaydi. Bo’yalgan sohadagi nuqtalarning koordinatalari berilgan
masaladagi barcha tengsizliklarni qanoatlantiradi. z maqsad funksiyasi maksimal

qiymatga
ABC
uchburchakning chegaraviy nuqtalarida erishganligi sababli, optimal

echimni topish uchun
A, B
nuqtalarning koordinatalarini topib,
z funksiyasiga

qo’yamiz va ularning ichidan olamiz.
z funksiyaga eng katta qiymat beruvchi nuqtani tanlab

5.12-rasm

S nuqta
(L₁ )
va ^(L₂ ⁾
to’g’ri chiziqlarning kesishish nuqtasi bo’lganligi uchun

ushbu tenglamalarni birgalikda echamiz.


_x₁  2x₂  4
^x  x  3
 1 2

Tenglamalar sistemasidan
x₁  2, x₂  1
ekanligi kelib chiqadi. U holda
A,B

nuqtalarning koordinatalari quyidagicha bo’ladi:
A( 0,2 ),
B( 0,3 ),
^{C( 2,1 )}. Ushbu

nuqtalarning koordinatalarini maqsad funksiyasiga qo’yib, quyidagilarni hosil qilamiz:

z _A  2  0  4  2  8 z_B  2  0  4  3  12 z_C  2  2  4 1  8



1

2

x

x
Yuqoridagilardan ko’rinib turibdiki z funksiya maksimal qiymatga V nuqtada

erishadi:
^zmax
 12,
^*  0,
^*  3.

5.6.3 Chiziqli dasturlash masalasini amaliy dasturlar yordamida yechish

Chiziqli dasturlash masalasini amaliy dasturlar, masalan PER, Excel, Mathcad dasturlari yordamida ham echish mumkin. Yuqoridagi masalani Excel elektron jadvali yordamida echamiz. Buning uchun elektron jadvalda masala tengsizliklaridagi

koifisientlar va ozod hadlarni ikkinchi va uchinchi satrlarga, z funksiya

koifisientlarini to’rtinchi satrga,
x₁ va
x₂ 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
«Сервис - Поиск решения» buyrug’ini beramiz.
katakka o’rnatib,

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 oynai hosil bo’ladi:

Hosil bo’lgan muloqot oynasida «Ссылка на ячейку» darchasiga ^C2 ni

kiritamiz, tengsizlikni aniqlaymiz, «Ограничения» darchasiga
«Добавить» tugmasini bosamiz.
^E2 ni kiritib,

^{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 echim quyidagi ko’rinishda ifodalanadi:

Ushbu rasmdan ko’rinib turibdiki, barcha cheklanishlar bajariladi va yechim quyidagi

ko’rinishda bo’ladi:
x₁  0,
x₂  3,
z_max  12.

MathCadda chiziqli dasturlash masalasini echishda maxsimize va minimize funksiyalaridan foydalaniladi. Bu funksiyalar umumiy ko’rinishda quyidagicha yoziladi: MAX() MIN(). MathCadda chiziqli dsturlash masalasini echish 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 echimni 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₁  0,
x ₂  3,
^zmax
 12.