Chiziqli dasturlash masalasini analitik yechish usuli - simpleks usul

chiziqli programmalash masalasini analitik yechish usuli-simpleks usul Reja: Berilgan chiziqli programmalashtirish masalasini normal formaga keltirish. Simpleks jadval tuzish. Masalaning tayanch planlarini aniqlash. Masalaning yechimini yuklik shartlarini tekshirish. Optimallik kriteriyasi. Simpleks usul algoritmi. chiziqli programmalash masalasining optimal yechimini yuklik shartlari. Dastlab berilgan chiziqli programmalash masalasining chegaraviy shartlarida m ta o'zaro chiziqli bog'liq bo'lmagan birlik vektorlar mavjud deb faraz kilamiz. Umumiylikni buzmagan holda bu vektorlar birinchi m ta P1, P2, ,Pm vektordan iborat deylik. U holda masala quyidagi ko'rinishda bo'ladi: x1+a1,m+1 xm+1++a1nxn=b1 x2+a2,m+1 xm+1++a2nxn=b2 (1) xm+amm+1 xm+1++amnxn=bm x10, x20,, xm0, xm+10,, xn0 (2) ymin=c1x1+ c2x2+ +cnxn (3) sistemani vektor formada yozamiz: P1x1+ P2x2++ Pmxm+ Pm+1xm+1++ Pnxn= P0 (4) P1,P2,,Pm vektorlar n o'lchovli vektor fazodagi o'zaro chiziqli bog'liq bo'lmagan birlik vektorlardan iborat bo'lib, bu fazoning bazisini tashkil qiladi. (1) da x1,x2,,xm o'zgaruvchilarni bazis o'zgaruvchilar, xm+1,xm+2,,xm o'zgaruvchilarni esa bazis bo'lmagan (ozod) o'zgaruvchilar deb kabul qilib, bazis bo'lmagan o'zgaruvchilarni nolga tenglaymiz. Natijada: X0=(x1=b1, x2=b2,; xm=bm, xm+1=0,, xn=0) (5) boshlang'ich planni hosil kilamiz. (5) planga quyidagi x1P1+x2P2++xmPm=P0 (6) yoyilma mos keladi. Bu yoyilmadagi P1, P2,, Pm vektorlar o'zaro chiziqli bog'liq bo'lmagan vektorlar bo'lganligi sababli, topilgan boshlang'ich (5) plan tayanch plan bo'ladi. Endi boshlang'ich plandan foydalanib, yangi tayanch planni topish mumkinligini kursatamiz. P1, P2,, Pm vektorlar n o'lchovli vektor fazoning bazisini tashkil kilgani uchun P1, P2,, Pn vektorlarning ixtiyoriysini (Pj ) bazis vektorlar orqali fakat bir xil yoyilmasini topish mumkin, yani Pj =x1jP1+ x2jP2 ++ xmjPm, (7) Faraz kilaylik, birorta vektor, masalan Pm+1 ning yoyilmasidagi koeffitsiyentlardan kamida bittasi (masalan, x1,m+1) noldan farqli bulsin: Pm+1=P1 x1 m+1 +P 2 x 2 m+1 +…+P m x m m+1 (8) Ixtiyoriy 0 ( - hozircha nomalum son)ni olib, (8) tenglikning ikki tomonini unga kupaytirib, hosil bo'lgan natijani (6) dan ayiramiz. Natijada quyidagi tenglikka ega bulamiz: P1(x1- x1,m+1)+ P2(x2- x2,m+1)++ +Pm(xm- xm,m+1)+ Pm+1)=P0 (9) Agar x1- x1,m+10, x2- x2,m+10, , xm- xm,m+1 0 bulsa, X1=( x1- x1,m+1, x2- x2,m+1, , xm- xm,m+1, 0,0,,0) vektor plan bo'ladi. 0 bo'lganligi sababli, X1 planning komponentalari manfiy bulmaydi, shuning uchun x2,m+10 bo'lgan komponentalarni kuramiz. Demak, shunday 0 topishimiz kerakki, xamma i lar uchun xi ,m+10 bo'lganda xi- xi ,m+1 0 bulsin. Bundan 0 X1 plan ixtiyoriy tengsizlikni kanoatlantiruvchi uchun plan bo'ladi. Lekin tayanch plan o'z ichiga m+1 ta komponentani olmaydi, shuning uchun X1 plandagi kamida bitta komponentani nolga aylantirish kerak. Faraz kilaylik, =0== bulsin. Bu holda X1 planning k komponentasi xk- xk,m+1=0 bo'ladi. ning qiymatini (9) ga kuyib quyidagi yoyilmani hosil kilamiz: bu yoyilmaga ...