1. Chiziqli tenglamalar tizimini yechish Chiziqli dasturlash masalasini yechishning grafik usuli



Yüklə 392,23 Kb.
səhifə3/8
tarix17.10.2023
ölçüsü392,23 Kb.
#156408
1   2   3   4   5   6   7   8
Chiziqli dasturlash masalalarini qo`yilishi

Amaliy mashg‘ulot uchun misollar
Quyidagi tizimlarni teskari matritsani topish va Gauss usullari yordamida yeching.

1. 2.



3. 4.

Quyidagi tizimlarning Jordan-Gauss usuli yordamida ixtiyoriy bazis yechimlarini toping.

1. 2.



3. 4.



2.Chiziqli dasturlash masalasini yechishning grafik usuli
n=2 bo‘lganda tengsizliklar tizimidan quyidagi tizimni hosil qilamiz:

Bu tengsizliklarning har biri ai1x1+ai2x2=bi to‘g‘ri chiziq bilan, yechimlarning manfiy bo‘lmaslik shartlari xj0 j=1;2 esa xj=0 to‘g‘ri chiziq bilan chegaralangan yarim tekisliklar bo‘ladi. Tengsizliklar tizimi birgalikda bo‘lganligi uchun hech bo‘lmaganda bitta yechimga ega bo‘ladi, ya'ni chegaraviy to‘g‘ri chiziqlar bir-biri bilan kesishib, mumkin bo‘lgan (o‘rinli) yechimlar to‘plamini hosil qiladi. Demak, n=2 bo‘lganda mumkin bo‘lgan yechimlar to‘plami ko‘pburchakning nuqtalaridan iborat bo‘ladi.


3.1 rasm 3.2 rasm

3.3 rasm 3.4 rasm
Mumkin bo‘lgan yechimlar sohasi (to‘plami) qavariq ko‘pburchak (3.1rasm), ko‘pburchakli qavariq soha (3.2 rasm), yagona nuqta (3.3 rasm) va bo‘sh to‘plam (3.4 rasm) bo‘lishi mumkin.
Chiziqli dasturlash masalasini ikki o‘zgaruvchi uchun quyidagicha yozamiz.

Tengsizliklarning har biri chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. Chiziqli funksiya ham ma'lum bir o‘zgarmas qiymatda to‘g‘ri chiziqni ifodalaydi c1x1+c2x2=const.
Faraz qilaylik, mumkin bo‘lgan yechimlar qavariq ko‘pburchakdan tashkil topgan bo‘lsin. Yechimlardan tashkil topgan qavariq to‘plamni hosil qilish uchun to‘g‘ri chiziqlar bilan chegaralangan ko‘pburchakni yasaymiz. Bu ko‘pburchak ABCDEF bo‘lsin (3.5 rasm). Maqsad funksiyasi X1OX2 tekislikda parallel to‘g‘ri chiziqlarni beradi. Chiziqli funksiyani ixtiyoriy o‘zgarmas c0 songa teng deb olaylik. Unda c1x1+c2x2=const= c0 to‘g‘ri chiziq hosil bo‘ladi. Unga perpendikulyar bo‘lgan N(c1,c2) vektor Z funksiyaning o‘sish yo‘nalishini belgilaydi (3.5 rasm). Agar yechimlardan tashkil topgan qavariq ko‘pburchak chegaralanmagan bo‘lsa ikki hol bo‘lishi mumkin:
1-hol. c1x1+c2x2=const to‘g‘ri chiziq N(c1,c2) vektor bo‘yicha yoki unga qarama-qarshi yo‘nalishda siljib borib har vaqt qavariq ko‘pburchakni kesib o‘tadi. Ammo minimum yoki maksimum qiymatga erishmaydi. Bu holda chiziqli funksiya quyidan va yuqoridan chegaralanmagan bo‘ladi (3.6 rasm).



3.5 расм 3.6 расм
2-hol. c1x1+c2x2=const to‘g‘ri chiziq N(c1,c2) vektor bo‘yicha siljib borib qavariq ko‘pburchakning birorta chetki nuqtasida minimum yoki maksimum qiymatga erishadi. Bunday holda chiziqli funksiya yuqoridan chegaralangan, quyidan esa chegaralanmagan (3.7 rasm) yoki quyidan chegaralangan yuqoridan esa chegaralanmagan bo‘lishi mumkin (3.8 rasm). Ba'zi chiziqli funksiyalar yuqoridan ham, quyidan ham chegaralangan bo‘lishi mumkin (3.9 rasm).

3.7 rasm 3.8 rasm 3.9 rasm

Chiziqli dasturlash masalasini grafik usulda yechish quyidagi ketma-ketlikda bajariladi:


1.Tenglamalar yoki tengsizliklar tizimining grafiklari quriladi .
2.Har bir tengsizlikning tekislikdagi aniqlanish tomonlari (sohasi) belgilanadi.
3.Mumkin bo‘lgan yechimlar sohasi ajratiladi .
4. N=(c1,c2) vektori quriladi va unga (0,0) nuqtada perpendikulyar o‘tkaziladi.
5.Ko‘pburchakdan perpendikulyarga parallel chiziqni vektor yo‘nalishi bo‘yicha parallel siljitilib ekstremal nuqta topiladi. Agar Z funksiyaning minimal qiymatiga mos nuqtani topish kerak bo‘lsa, u holda bu nuqta p vektorga perpendikulyarning shu vektor yo‘nalishi bo‘yicha siljitganda mumkin bo‘lgan nuqtalar sohasining birinchi nuqtasiga mos keladi. Maksimum qiymat beruvchi nuqta esa eng oxirgi nuqta bo‘ladi. Agar vektor qiymati (manfiy ishora) -N bo‘lsa yuqoridagi holning teskarisi bo‘ladi.
6.Optimal nuqta koordinatasi topiladi va Z funksiya qiymati hisoblanadi.


Misol. Quyidagi chiziqli dasturlash masalasini grafik usulda yeching.

3.10 rasm.
Berilgan tengsizliklarning grafiklarini X1OX2 tekislikda quramiz va mumkin bo‘lgan yechimlar sohasini aniqlaymiz (3.10 rasm). Soha grafigida shtrixlangan joyni aniqlaydi. Chunki bu joy hamma tengsizliklarni qanoatlantiruvchi sohadir. Mumkin bo‘lgan yechimlar sohasidan optimal yechimni aniqlaymiz. Aniqlash uchun (0,0) nuqtadan o‘tuvchi N=(2,-5) vektorini yasaymiz va uning yo‘nalishini aniqlaymiz. (0,0) nuqtada bu vektorga N perpindikulyarini o‘tkazamiz va uni vektor yo‘nalishi bo‘yicha siljitamiz. Soha bilan perpindikulyarning oxirgi kesishish nuqtasi Z funksiyasiga maksimal qiymat beruvchi nuqtadir. Bu nuqta (3,0) bo‘lib uning koordinatasi x1=3, x2=0 masalaning yechimi bo‘ladi. Grafikdan ko‘rinib turibdiki Z funksiyaga minumum qiymat beruvchi nuqta esa (0,3).



Yüklə 392,23 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin