Ўзбeкистон республикаси олий ва ўрта махсус таълим вазирлиги
Chiziqli programmalashtirish masalasini analitik yechish usuli (simpleks usul)
Download 90.49 Kb.
|
Al mustaqil ish 15-variant
- Bu sahifa navigatsiya:
- Optimallik kriteriysi. Optimal yechimni topish
1.Chiziqli programmalashtirish masalasini analitik yechish usuli (simpleks usul)Dastlab berilgan chiziqli programmalashtirish masalasining chegaraviy shartlarida m ta o`zaro chiziqli bog`liq bo`lmagan birlik vektorlar mavjud deb faraz qilamiz. Umumiylikni buzmagan holda bu vektorlar birinchi m ta P1 , P2 ,..., Pm vektorlardan iborat deylik. U holda masala quyidagi ko`rinishda bo`ladi: x1 a1,m1 xm1 ... a1n xn b1 , x2 a2,m1 xm1 ... a2 n xn b2 , (2.5.1) ............................................. xm am,m1 xm1 ... amn xn bm , x j 0 , j 1, n , (2.5.2) ymin c1 x2 c2 x2 ... cn xn . (2.5.3) (2.5.1) sistemani vektor ko’rinishda yozamiz: P1x1 P2 x2 ... Pm xm Pm1xm1 ... Pn xn P0 (2.5.4)
bog`liq bo`lmagan birlik vektorlardan iborat bo`lib, bu fazoning bazisini tashkil qiladi. (2.5.1) da x1 , x2 ,..., xm o`zgaruvchilarni bazis o`zgaruvchilar, xm1 , xm2 ,..., xn o`zgaruvchilarni esa bazis bo`lmagan (ozod) o`zgaruvchilar deb qabul qilib, bazis bo`lmagan o`zgaruvchilarni nolga tenglaymiz. Natijada: X0 (x1 b1 , x2 b2 ,..., xm bm , xm1 0,..., xn 0) boshlang`ich yechimni hosil kilamiz. (5) yechimga quyidagi P1x1 P2 x2 ... Pn xn P0 (2.5.5) (2.5.6)
yoyilma mos keladi. Bu yoyilmadagi P1 , P2 ,..., Pm vektorlar o`zaro chiziqli bog`liq bo`lmagan vektorlar bo`lganligi sababli, topilgan boshlang`ich (2.5.5) yechim tayanch yechim bo`ladi. Endi boshlang`ich yechimdan foydalanib, yangi tayanch yechimni topish mumkinligini ko`rsatamiz. P1 , P2 , ... , Pm vektorlar n o`lchovli vektor fazoning bazisini tashkil qilgani uchun P1 , P2 ,..., Pm vektorlarning ixtiyoriysini Pj bazis vektorlar orqali faqat bir xil yoyilmasini topish mumkin, ya’ni: j 1, n uchun Pj P1x1 j P2 x2 j ... Pm xmj (2.5.7) yoyilmasidagi koeffitsientlardan kamida bittasi (masalan, x1,m1 ) noldan farqli bo`lsin: Pm1 P1 x1,m1 P2 x2,m1 ... Pm xm,m1 (2.5.8) Ixtiyoriy >0 ( - hozircha noma’lum son) ni olib, (2.5.8) tenglikning ikki tomonini unga ko`paytirib, hosil bo`lgan natijani (2.5.6) dan ayiramiz. Natijada quyidagi tenglikka ega bulamiz: P1(x1 x1,m1) P2 (x2 x2,m1) ... Pm (xm xm,m1) Pm1 P0 (2.5.9) Agar x1 x1,m1, x2 x2,m1 ,..., xm xm,m1 , sonlarning har biri nomanfiy bo`lsa, X (x1 x1,m1, x2 x2,m1 ,..., xm xm,m1 , , 0, 0, ..., 0) vektor yechim bo`ladi. X dan farq qiluvchi X yechim qidirilayotgani uchun ning faqat musbat qiymatlari qaraladi. Shuning uchun xi,m1 >0 bo`lgan komponentalarni ko`ramiz. Demak, shunday >0 topishimiz kerakki, hamma i lar uchun bajarilsin. xi,m1 >0 , bo`lganda xi xi,m1 0 tengsizlik Bunlardan, 0< tengsizlik hosil bo` ladi. xi xi,i1 X yechim xi,m1 >0 tengsizlik qanoatlantiriladigan ( 0< min xi ) x i,i1 uchun yechimdir. Lekin tayanch yechim o`z ichiga m+1 ta komponentlarni olmaydi, shuning uchun X yechimdagi kamida bitta komponentani nolga aylantirish kerak. Faraz qilaylik, min xi xk bajarilsin. 0 i x x i,m1 k ,m1 Bu holda X yechimning k komponentasi xk xk ,m1 =0 bo`ladi. ning qiymatini (1.5.9) ga qo`yib quyidagi yoyilmani hosil qilamiz: P1 (x1 0 x1,m1 ) P2 (x2 0 x2, m1 ) ... Pk 1 (xk 1 0 xk 1,m1 ) Pk 1 (xk 1 0 xk 1,m1 ) ... Pm (xm 0 xm,m1 ) P0 . Bu yoyilmaga X (x1 0 x1,m1, x2 0 x2,m1 ,..., xk 1 0 xk 1,m1 , xk 1 0 xk 1,m1 ,..., xm 0 xm,m1 ,0 , 0, 0, ..., 0) yechim mos keladi. Demak, yangi yechimning komponentalari quyidagicha aniqlanar ekan: xi xi 0 xi,m1 , xk 0, xm 2 ... xn 0 xm 1 0 (2.5.10) kirmagan ixtiyoriy vektorning P1 , P2 ,..., Pm bazis vektorlar orqali yoyilmasini aniqlash hamda shunday sonni topish kerakki, uning yordamida yangi vektor bazisga kirsin va eski bazis vektorlardan birortasi bazisdan chiqsin. Shunday qilib, yangi tayanch yechimlarni hosil qilish jarayoni bazisga kiritiladigan va bazisdan chiqariladigan vektorni tanlashdan iboratdir. Bazisga kiritiladigan vektorni tanlash kriteriysi simpleks usulning asosiy elementlaridan biri hisoblanadi. Agar bazisga kiritilayotgan Pm1 birorta vektorni bazisdan chikaruvchi 0 ni topib bo’lmaydi. Bu holda X yechim m+1 musbat komponentalarni o`z ichiga oladi. P1 , P2 ,..., Pm , Pm1 vektorlar sistemasi esa o`zaro chiziqli bog`liq bo`lib, qavariq ko`pburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. Bu nuqtada esa chiziqli funksiya o`zining minimum qiymatiga erisholmaydi. Bu holda chiziqli funksiya quyidan chegaralanmagan bo`ladi. Optimallik kriteriysi. Optimal yechimni topishQuyidagi ko`rinishda berilgan chiziqli programmalashtirish masalasining x1 a1,m1 xm1 ... a1n xn b1 , x2 a2,m1 xm1 ... a2n xn b2 , ............................................. xm am,m1 xm1 ... amn xn bm , (2.5.11) x j 0 , j 1, n , ymin c1 x2 c2 x2 ... cn xn yechimlari mavjud va ular xosmas deb faraz qilamiz, ya’ni barcha bi>0, i 1, m . Masalaning X (x1 , x2 ,..., xm ) (2.5.12) tayanch yechimi va unga mos keluvchi o`zaro chiziqli bog`liq bo`lmagan P1 , P2 ,..., Pm vektorlar sistemasi ma’lum bo`lsin. U holda P1x1 P2 x2 ... Pn xn P0 (2.5.13)
va y0 c1x1 c2 x2 ... cn xn . (2.5.14)
Bu yerda y0 - chiziqli funksiyaning X tayanch yechimdagi qiymati, xi 0 va cj j 1, n chiziqli funksiyaning koeffisientlari. P1 , P2 ,..., Pm vektorlar o`zaro chiziqli bog`liq bo`lmagan vektorlar bo`lganligi sababli ixtiyoriy bazis bo`lmagan orqali faqat bitta yoyilmasini topish mumkin: Pj vektorning bu vektorlar x1 j P1 x2 j P2 ... xmj Pm Pj , Bu vektorga chiziqli funksiyaning c1x1 j c2 x2 j ... cmxmj yj , j 1, n (2.5.16) qiymati mos keladi. Pj vektorga mos keluvchi chiziqli funksiyaning koeffitsientini c j bilan belgilaymiz. j 1, n. (2.5.15) ChPM yechimlarining shunday to`plamini tuzish mumkinki, ularning har biri uchun tengsizlik o`rinlidir. y y0 (y – ChPM maqsad funksiyasining qiymati) hol. y-sonlarining quyi chegarasi cheklangan bo`lsa, shunday yangi yechim topish mumkinki, u o`zidan oldingisiga qaraganda kichik qiymatga ega bo`ladi. hol. y - sonlarining quyi chegarasi cheksiz bo`lsa, shunday yangi yechim topilishi mumkinki, uning koordinatalari m+1 ta musbat sonlardan tashkil topib, qiymati har qancha kichik bo`lishi mumkin. Yuqorida keltirilganlarni isbotsiz qabul qilamiz. Berilgan boshlang`ich yechimdan boshlab tayanch yechimlar ketma- ketligini hosil qilib, jarayonni optimal yechim topilguncha davom ettirish mumkin. Bu jarayon simpleks usuldan iborat. Endi simpleks usulning algoritmi bilan tanishaylik. Faraz qilaylik: 1) m ta chiziqli bog`liqsiz vektorlar tanlanganki, ular biror tayanch yechimning bazislari bo`lsin; 2) masalaning chegaraviy shartlari m - nchi tartibli birlik matritsaga ega bo`lsin. Birinchi hol uchun m ta chiziqli bog`liqsiz vektorlar - P1 , P2 ,..., Pm va masalaning boshlang`ich tayanch yechimi - X (x1 , x2 ,..., xm ) bo`lsin. Bu vektorlardan tashkil topgan ( P1 , P2 ,..., Pm ) matritsani B bilan belgilaymiz. U holda BX P0 . Bundan: X=B-1P0 va j j X B 1P , x 0 i kelib chiqadi. Bu yerda X (x1 , x2 ,..., xm ) , ( xi 0 ) va X j (x1 j , x2 j ,..., xmj ) - vektor ustunlar. Simpleks jarayonni boshlashdan avval masalaning vektorlarini quyidagidek guruhlaymiz: (R0| P1, P2,...,Pm | Pm+1,...,Pn) Download 90.49 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling