Chiziqli dasturlash asoslari. Chiziqli dasturlashning chegaralanish shartlari. Chiziqli dasturlashning maqsad funksiyasi
Chiziqli dasturlash masalasining umumiy qoʻyilishi va uning
Yüklə 19,73 Kb.
|
1 2
2-Ma\'ruza- Bu səhifədəki naviqasiya:
- Chiziqli dasturlash
|
Chiziqli dasturlash masalasining umumiy qoʻyilishi va uning
turli formada ifodalanishi Chiziqli dasturlash masalasi umumiy holda quyidagicha ifodalanadi: a11x1 + a12x2 + ... + a1nxn ≥ (≤) b1 a21x1 + a22x2 + ... + a2nxn ≥ (≤) b2 , (2.1) ...................................................... ...................................................... am1x1 + am2x2 + ... +amnxn ≥ (≤) bm , x1 ≥ 0, x2 ≥ 0, ... , xn ≥ 0, (2.2) Y =c1x1 +c2x2 + ... + cnxn→ min(max). (2.3) (2.1) va (2.2) shartlarni qanoatlantiruvchi noma’lumlarning shunday qiymatlarini topish kerakki, ular (2.3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (2.1) va (2.2) cheklamalari uning chegaraviy shartlari deb, (2.3) chiziqli funksiya esa masalaning maqsadi yoki maqsad funksiyasi deb ataladi. Masaladagi barcha cheklamalar shartlar va maqsad funksiya chiziqli ekanligi koʻrinib turibdi. Shuning uchun ham (2.1) - (2.3) masala chiziqli dasturlash masalasi deb ataladi. Aniq masalalarda (2.1) shart tenglamalar sistemasidan, «≥» yoki «≤» koʻrinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat boʻlishi mumkin. Shunday yoʻl bilan chiziqli dasturlash masalasining cheklamalaridagi tengsizliklarni tenglamalarga aylantirish mumkin. Bunda shunga e’tibor berish kerakki, sistemadagi turli tengsizliklarni tenglamalarga aylantirish uchun ularga bir-birlaridan farq qiluvchi nomanfiy oʻzgaruvchilarni qoʻshish kerak. Masalan, agar chiziqli dasturlash masalasi quyidagi a11x1 + a12x2 + ... + a1nxn ≤ b1 , a21x1 + a22x2 + ... + a2nxn ≤ b2 , (2.4) ...................................................... ...................................................... am1x1 + am2x2 + ... +amnxn ≤ bm , x1 ≥ 0, x2 ≥ 0, ... , xn ≥ 0, (2.5) Y= c1x1 +c2x2 + ... + cnxn→ max (2.6) koʻrinishda boʻlsa, bu masaladagi tengsizliklarning kichik tomoniga xn+1 ≥ 0, xn+2 ≥ 0, ..., xn+m ≥ 0 qoʻshimcha oʻzgaruvchilar qoʻshish yordamida tenglamalarga aylantirish mumkin. Bu oʻzgaruvchilar Y=CʻX ga 0 koeffitsient bilan kiritiladi. Natijada berilgan (2.4)-(2.6) masala quyidagi koʻrinishga keladi. a11x1 + a12x2 + ... + a1nxn + xn+1 = b1 , a21x1 + a22x2 + ... + a2nxn + xn+2 = b2 , (2.7) ...................................................... ...................................................... am1x1 + am2x2 + ... +amnxn + xn+m = bm , x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0, xn+1 ≥ 0,..., xn+m ≥ 0, (2.8) Y = c1x1+c2x2 +...+cnxn+O(xn+1+...+xn+m) → max (2.9) Xuddi shuningdek, a11x1 + a12x2 + ... + a1nxn ≥ b1 , a21x1 + a22x2 + ... + a2nxm ≥ b2 , (2.10) ...................................................... ...................................................... am1x1 + am2x2 + ... +amnxn ≥ bm , x1 ≥ 0, x2 ≥ 0, ... , xn ≥ 0, (2.11) Y = c1x1 +c2x2 + ... + cnxn → min. (2.12) koʻrinishda berilgan chiziqli dasturlash masalasini kanonik koʻrinishga keltirish mumkin. Buning uchun qoʻshimcha xn+1 ≥ 0, xn+2 ≥ 0, ..., xn+m ≥ 0 oʻzgaruvchilar tengsizliklarning katta tomonidan ayriladi. Natijada quyidagi masala hosil boʻladi: a11x1 + a12x2 + ... + a1nxn - xn+1 = b1 , a21x1 + a22x2 + ... + a2nxn - xn+2 = b2 , (2.14) ...................................................... ...................................................... am1x1 + am2x2 + ... +amnxn - xn+m = bm , x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0, xn+1 ≥ 0,..., xn+m ≥ 0, (2.15) Y = c1x1+c2x2 +...+cnxn+O(xn+1+...+xn+m) → min. (2.16) Chiziqli dasturlash - to‘plamlarda ekstremal masalalarni yechish nazariyasi va usullariga bag‘ishlangan matematik intizom hisoblanadi. Nazorat savollari: Сhiziqli dasturlash masalasining mohiyati. Chegaraviy shartlari tushunchasi. 3. Masalaning maqsad funksiyasi. Yüklə 19,73 Kb. Dostları ilə paylaş:
|
1 2