|
Oliy ta’lim,fan va innovatsiyalar vazirligi toshkеnt axborot tеxnologiyalari univеrsitеti “Algoritmlarni loyihalash
|
| bet | 4/7 | | Sana | 22.01.2024 | | Hajmi | 149,09 Kb. | | #142747 |
Bog'liq Mustaqil ish Mavzu Chiziqli dasturlash masalalarini yechishda s (1)am1x1 + am2x2 + ...+ amnxn + ym = bm .
Demak, CHDMda berilgan noma’lumlar asosiy noma’lumlar, tengsizliklar sistemasini tenglamalar sistemasiga aylantirish uchun qo’shiladigan noma’lumlar qo’shimcha noma’lumlar deb ataladi. Qo’shimcha noma’lumlar «» ko’rinishdagi tengsizliklarga musbat, «» ko’rinishdagi tengsizliklarga esa manfiy ishora bilan qo’shiladi.
Chiziqli dasturlash masalasidagi tengsizliklar sistemasini tenglamalar sistemasi ko’rinishiga keltirish uchun qo’shiladigan qo’shimcha noma’lumlar maqsad funksiyasiga nol koeffistient bilan qo’shiladi, ya’ni:
Zmax = c1x1+c2x2+...+ cnxn+cn+1y1+cn+2y2+...+ cm ym =
=c1x1+c2x2+...+ cnxn+0y1+0y2+...+0ym . (2.1.18)
Standart formadagi x1, x2 , ... , xn o’zgaruvchilar bazis noma’lumlar, qo’shimcha kiritilgan y1, y2, ... , ym 0 o’zgaruvchilar bazis bo’lmagan noma’lumlar deyiladi.
Bu yerda masalani echishda qulay bo’lsin uchun bazis no’malumlar sifatida x1, x2 , ... , xn,, basis bo’lmagan no’malumlar sifatida y1, y2, ... , ym tanlangan.
CHDMda boshlang’ich tayanch rejani topish uchun, masaladagi (2.1.15) tengsizliklar sistemasi qo’shimcha noma’lumlarni qo’shish natijasida tenglamalar sistemasi (2.1.17) ga aylantirilgach, bu sistema qo’shimcha noma’lumlarga nisbatan yechib olinadi, ya’ni:
y1 = b1 – (a11x1 + a12x2 + ... + a1nxn),
y2 = b2 – (a21x1 + a22x2 + ... + a2nxn),
y3=b – (a31x1 + a32x2 + ... + a3nxn), (2.1.19)
... ... ... ... ... …
ym = bm – (am1x1 + am2x2+ ... + amnxn).
Maqsad funksiyasini quyidagicha ifodalab olamiz:
Zmax =0-(- c1x1-c2x2-...- cnxn) +0y1+0y2+0y3+...+0ym . (2.1.20)
Topilgan (2.1.19) sistemadan qoidaga ko’ra asosiy noma’lumlar nolga tenglashtirib olinadi, ya’ni:
x1= x2 = ... = xn= 0.
Natijada quyidagi boshlang’ich tayanch rejaga ega bo’lamiz (bu yerda masalaning berilishidagi ozod hadlar musbat deb qaralmoqda):
y1 = b1, y2 = b2 , y3 = b3 , ... ,ym = bm , Zmax =0. (2.1.21)
CHDMda (2.1.21) ni (boshlang’ich tayanch rejani) umumiy holda quyidagicha yozish qabul qilingan:
X*= (x1,x2, ..., xn, y1, y2 ,… , ym) = (0, 0, .. ., 0 , b1, b2, ... , bm).
Topilgan tayanch rejaning yechimlari (qiymatlari) musbat bo’lsa berilgan CHDMni simpleks usul bilan yechish mumkin bo’ladi.
Quyidagilarga e’tibor berishimiz lozim:
Agar chegaraviy shartlardagi bi ozod xadlar manfiy ishorali bo’lsa, u holda ularni har doim (-1) ga ko’paytirib, musbat holatga keltirish kerak.
Endi (2.1.19) va (2.1.20) da berilganlarni quyidagi ko’rinishdagi jadvalga joylashtiramiz va uni boshlang’ich simpleks jadval deb nomlaymiz.
Boshlang’ich tayanch reja chekli sondagi etap (simpleks)dan keyin optimal rejani hosil qilish yo’lini ko’rsatadi va har bir navbatdagi simpleks oldingisiga nisbatan optimal rejaga yaqinroq rejani beradi. Masalani yechish jarayoni optimal yechim topilguncha yoki masalaning maqsad funksiyasi chekli maksimum (minimum)ga ega emasligi aniqlanguncha davom ettiriladi.
2.1.2-jadval
|
| |
