Chiziqli dasturlash masalalari. Simpleks masalasi va trasport masalalarining qo'yilishi

Chiziqli programmalashtirish masalalari. Simpleks masalasi va trasport masalalarining qo'yilishi Reja: 1. Chiziqli programmalash masalasining umumiy qo'yilishi. 2. Chiziqli programmalash masalasining turli formada ifodalanishi. 3. Teng kuchli almashtirishlar. 4. Chiziqli programmalash masalasining mumkin bo'lgan yechimlari. Tayanch yechim. 5. Mumkin bo'lgan yechimlar to'plamining qavariqligi. 6. Chiziqli programmalash 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 programmalash 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 programmalash masalasining kanonik ko'rinishi deb ataladi. (4)-(6) masala 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'liq bo'lmasa, u holda 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 holda 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 programmalash masalasi ustida quyidagi teng kuchli almashtirishlarni bajarish mumkin. 1)Ymax ni ...