Ўзбeкистон республикаси олий ва ўрта махсус таълим вазирлиги


Chiziqli programmalashtirish masalasini analitik yechish usuli (simpleks usul)



Yüklə 90,49 Kb.
səhifə2/4
tarix20.08.2023
ölçüsü90,49 Kb.
#139978
1   2   3   4
Al mustaqil ish 15-variant

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)


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. (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)

Faraz qilaylik, bazisga kirmagan birorta vektor, masalan
Pm1
ning

yoyilmasidagi koeffitsientlardan kamida bittasi (masalan,
x1,m1
) noldan

farqli bo`lsin:
Pm1 P1 x1,m1 P2 x2,m1 ... Pm xm,m1
(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,i1

X yechim
xi,m1
>0 tengsizlik qanoatlantiriladigan  ( 0<  min xi )
x

i,i1
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,m1 k ,m1
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,m1 ) P2 (x2 0 x2, m1 ) ... Pk 1 (xk 1 0 xk 1,m1 ) Pk 1 (xk 1 0 xk 1,m1 )
...  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,m1 ,

xk  0, xm 2  ...  xn  0
xm 1 0
(2.5.10)

Bundan keyingi tayanch yechimni hosil qilish uchun bazisga

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
Pm1

vektorning yoyilmasida barcha
xi,m1 0 bo`lsa, (2.5.9) yoyilmadagi

birorta vektorni bazisdan chikaruvchi  0 ni topib bo’lmaydi. Bu holda X

yechim m+1 musbat komponentalarni o`z ichiga oladi.
P1 , P2 ,..., Pm ,
Pm1

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 topish


Quyidagi 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)

  1. hol. y-sonlarining quyi chegarasi cheklangan bo`lsa, shunday yangi

yechim topish mumkinki, u o`zidan oldingisiga qaraganda kichik qiymatga ega bo`ladi.

  1. 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)



Yüklə 90,49 Kb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin