Chiziqli dasturlash masalalarini yechish usullari Bajardi: Sanoat farmatsiya fakulteti

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 a_i1x₁+a_i2x₂₌b_i to‘g‘ri chiziq bilan, yechimlarning manfiy bo‘lmaslik shartlari x_j0 j=1;2 esa x_j=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 c₁x₁+c₂x₂=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 X₁OX₂ tekislikda parallel to‘g‘ri chiziqlarni beradi. Chiziqli funksiyani ixtiyoriy o‘zgarmas c₀ songa teng deb olaylik. Unda c₁x₁+c₂x₂=const= c₀ to‘g‘ri chiziq hosil bo‘ladi. Unga perpendikulyar bo‘lgan N(c₁,c₂) 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. c₁x₁+c₂x₂=const to‘g‘ri chiziq N(c₁,c₂) 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. c₁x₁+c₂x₂=const to‘g‘ri chiziq N(c₁,c₂) 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=(c₁,c₂) 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 X₁OX₂ 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 x₁=3, x₂=0 masalaning yechimi bo‘ladi. Grafikdan ko‘rinib turibdiki Z funksiyaga minumum qiymat beruvchi nuqta esa (0,3).