Mavzu: chiziqsiz programmalashtirish. Reja
Yüklə 87,86 Kb.
|
| 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 koeffitsientlaridan 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 koeffitsientli 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 Ymin ga aylantirish. Har qanday chiziqli programmalash masalasini (4)–(6) ko‘rinishga keltirish uchun (1) tengsizliklar sistemasini tenglamalar sistemasiga va Ymax ni Ymin ga aylantirish kerak. Ymax ni Ymin ga keltirish uchun Ymax ni teskari ishora bilan olish, ya'ni - Ymax = Ymin yoki Ymax = - Ymin ko‘rinishda olish yetarlidir. Haqiqatdan ham, har qanday f(x1, x2, …, xn) funksiyaning minimumi teskari ishora bilan olingan shu funksiya maksimumining qiymatiga teng, ya'ni minf(x1, x2, …, xn) va – max[f(x1, x2, …, xn)],maxf(x1, x2, …, xn) va – min[f(x1, x2, …, xn)]ifodalar noma'lumlarning bir xil qiymatlaridagina o‘zaro teng bo‘lishini ko‘rsatish mumkin2)Tengsizliklarni tenglamaga aylantirish. n noma'lumli a1x1 + a2x2+ … + anxn ЈЈ b (16) chiziqli tengsizlikni qaraymiz. Bu tengsizlikni tenglamaga aylantirish uchun uning kichik tomoniga nomanfiy noma'lum sonni, ya'ni xn+1 іі 0 ni qushamiz.Natijada n+1 noma'lumli chiziqli tenglamaga ega bo‘lamiz:a1x1 + a2x2+ … + anxn +xn+1 = b (17) (16) tengsizlikni tenglamaga aylantirish uchun qo‘shilgan xn+1 o‘zgaruvchi qo‘shimcha o‘zgaruvchi deb ataladi.(16) tengsizlik va (17) tenglamaning yechimlari bir xil ekanligi quyidagi teoremada ko‘rsatilgan. 1-teorema Berilgan (16) tengsizlikning har bir X=(aa1, aa2, …, aan) yechimiga (17) tenglamaning faqat bittaY0 = (aa1, aa2, …, aan, aan+1)yechimi mos keladi va, aksincha, (17) tenglamaning har bir Y0 yechimiga (16) tengsizlikning faqat bitta X0 yechimi mos keladi. Teorema isboti. Faraz qilaylik, X0 (16) tengsizlikning yechimi bo‘lsin. U holda a1aa1 + a2aa2+ … + anaan ЈЈ b munosabat o‘rinli bo‘ladi. Tengsizlikning chap tomonini o‘ng tomonga o‘tkazib hosil bo‘lgan ifodani aan+1 bilan belgilaymiz 0 ЈЈ b – (a1aa1 + a2aa2+ … + anaan) = aan+1. Endi Y0 =(aa1, aa2, …, aan, aan+1) vektorni (17) tenglamaning yechimi ekanligini ko‘rsatamiz. a1aa1+a2aa2+…+anaan +aan+1=a1aa1+a2aa2+…+anaan+(b-a1aa1-a2aa2 - …-anaan )=b Endi agar Y0 (17) tenglamani qanoatlantirsa, u holda u (16) tengsizlikni ham qanoatlantirishini ko‘rsatamiz. Shartga ko‘ra: a1aa1+a2aa2+…+anaan +aan+1=b, aan+1 іі 0 Bu tenglamadan aan+1іі 0 sonni tashlab yuborish natijasida a1aa1 + a2aa2+ … + anaan ЈЈ b tengsizlikni hosil qilamiz. Bundan ko‘rinadiki, X0=(aa1, aa2, …, aan) (16) tengsizlikning yechimi ekan. Shunday yo‘l bilan chiziqli programmalash masalasining chegaralovchi shartlaridagi 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 programmalash masalasi quyidagi x1 іі 0, x2 іі 0, …, xn іі 0, (19) Ymax = c0 + c1x1 + c2x2+ … + cnxn (20) 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 Ymin ga 0 koeffitsient bilan kiritiladi. Natijada berilgan (18)–(20) masala quyidagi ko‘rinishga keladi. x1 іі 0, x2 іі 0, …, xn іі 0, xn іі 0, xn+1 іі 0, …, xn+m іі 0, (22) Ymax = c0 + c1x1 + c2x2+ … + cnxn+O(xn+1 +… + xn+m) (23) Xuddi shuningdek, x1 іі 0, x2 іі 0, …, xn іі 0 (25) Ymin = c1x1 + c2x2+ … + cnxn (26) ko‘rinishda berilgan chiziqli programmalash 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: x1 іі 0, x2 іі 0, …, xn іі 0, xn іі 0, xn+1 іі 0, …, xn+m іі 0, (28) Ymin = c0 + c1x1 + c2x2+ … + cnxn+O(xn+1 +… + xn+m) (29) Endi chiziqli programmalash masalasi yechimlarining xossalari bilan tanishamiz. Buning uchun eng avval qavariq kombinatsiya va qavariq to‘plam tushunchasini eslatib o‘tamiz. 5-ta'rif. A1,A2,…,An vektorlarning qavariq kombinatsiyasi deb shartlarni qanoatlantiruvchi A = aa1A1 + aa2A2+ … + aanAn vektorga aytiladi. n-o‘lchovli fazodagi har bir A=(a1, a2, …, an) vektorga koordinatalari (a1, a2, …, an) bo‘lgan nuqta mos keladi. Shuning uchun bundan keyin A=(a1, a2, …, an) vektorni n-o‘lchovli fazodagi nuqta deb qaraymiz. 6-ta'rif. Agar n-o‘lchovli vektor fazodagi C to‘plam o‘zining ixtiyoriy A1 va A2 nuqtalari bilan bir qatorda bu nuqtalarning qavariq kombinatsiyasidan iborat bo‘lgan A = aa1A1 + aa2A2 ( aa1>0, aa2 >0 , aa1 + aa2 = 1) nuqtani ham o‘z ichiga olsa, ya'ni A1 , A2 OOC YuYu AOOC bo‘lsa, bu to‘plam qavariq to‘plam deb ataladi. 2-teorema. Chiziqli programmalash masalasining yechimlaridan tashkil topgan to‘plam qavariq to‘plam bo‘ladi. Isboti. Chiziqli programmalash masalasining ixtiyoriy ikkita yechimining qavariq kombinatsiyasi ham yechim ekanligini ko‘rsatamiz. Faraz qilaylik, x1 va x2 berilgan chiziqli programmalash masalasining yechimlari bo‘lsin. U holda Yüklə 87,86 Kb. Dostları ilə paylaş:
|