Chiziqli dasturlash masalasining umumiy qo'yilishi va uning turli formada ifodalanishi

Chiziqli dasturlash masalasining umumiy qo'yilishi va uning turli formada ifodalanishi Reja: Chiziqli dasturlash masalasining umumiy qo'yilishi. Chiziqli dasturlash masalasining turli formada ifodalanishi. Chiziqli dasturlash masalasining mumkin bo'lgan yechimlari. Tayanch yechim. Teng kuchli almashtirishlar. Mumkin bo'lgan yechimlar to'plamining qavariqligi. Chiziqli dasturlash masalasi umumiy holda quyidagicha ifodalanadi: x1 0, x2 0, …, xn 0, (2) Ymin(max) = c0 + c1x1 + c2x2+ … + cnxn (3) (1) va (2) shartlarni qanoatlantiruvchi nomalumlarning shunday qiymatlarini topish kerakki, ular (3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (1) va (2) shartlari uning chegaraviy shartlari deb, (3) chiziqli funksiya esa masalaning maqsadi yoki maqsad funksiyasi deb ataladi. Masaladagi barcha chegaralovchi shartlar va maqsad funksiya chiziqli ekanligi ko'rinib turibdi. Shuning uchun ham (1)-(3) masala chiziqli dasturlash masalasi deb ataladi. Konkret masalalarda (1) shart tenglamalar sistemasidan, «» yoki «» ko'rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo'lishi mumkin. Lekin ko'rsatish mumkinki, (1)-(3) ko'rinishdagi masalani osonlik bilan quyidagi ko'rinishga keltirish mumkin. x1 0, x2 0, …, xn 0, (5) Ymin = c0 + c1x1 + c2x2+ … + cnxn (6) (4)-(6) ko'rinish chiziqli dasturlash masalasining kanonik ko'rinishi deb ataladi. (4)-(6) masalani vektorlar yordamida quyidagicha ifodalash mumkin: P1x1 + P2x2+ … + Pnxn = P0 (7) X 0 (8) Ymin = CX (9) bu yerda S = (C1, C2, …, Cn) - vektor-qator. X = (X1, X2, …, Xn) - vektor-ustun. (4)-(6) masalaning matritsa ko'rinishdagi ifodasi quyidagicha yoziladi: AX = P0, (10) X 0, (11) Ymin = CX, (12) bu yerda S = (C1, C2, …, Cn) - qator vektor, A = (aij) - (4) sistema koeffitsiyentlaridan tashkil topgan matritsa; X = (X1, X2, …, Xn) va P0 = (b1, b2, …, bn) - ustun vektorlar. (4)-(6) masalani yig'indilar yordamida ham ifodalash mumkin: 1-ta'rif. Berilgan (4)-(6) masalaning mumkin bo'lgan yechimi yoki rejasi deb, uning (4) va (5) shartlarni qanoatlantiruvchi X = (x1, x2, …, xn) vektorga aytiladi. 2-ta'rif. Agar (7) yoyilmadagi musbat xi koeffitsiyentli Pi (i=1,…,m) vektorlar o'zaro chiziqli bog'iq bo'lmasa, u olda X=(x1, x2, …, xn) reja tayanch reja deb ataladi. 3-ta'rif. Agar X=(x1, x2, …, xn) tayanch rejadagi musbat komponentalar soni m ga teng bo'lsa, u hoda bu reja aynimagan tayanch reja, aks holda aynigan tayanch reja deyiladi. 4-ta'rif. Chiziqli funksiya (6) ga eng kichik qiymat beruvchi X=(x1, x2, …, xn) tayanch reja masalaning optimal rejasi yoki optimal yechimi deyiladi. Chiziqli dasturlash masalasi ustida quyidagi teng kuchli almashtirishlarni bajarish mumkin. 1)Ymax ni Ymin ga aylantirish. Har qanday ...