Tema : Sızıqlı programmalastırıw máselesin jasalma bazis usılı menen sheshiw. Mısal sheshiw

_{Tema :} Sızıqlı programmalastırıw máselesin jasalma bazis usılı menen sheshiw. Mısal sheshiw
Joba:

1. 
   Sızıqlı programmalastırıw(SP) máselesiniń qoyılıwı
   
2. 
   SP máselesiniń tayanısh jobasın jasaw.
   
3. 
   SP máselesiniń optimal jobasın anıqlaw. Optimallıq shártleri.
   
4. 
   SP máselesin sheshiwdiń jasalma bazis usılı
   

1. 
   Sızıqlı programmalastırıw – bul sızıqlı funkciyanıń eń úlken hám eń kishi mánislerin tabıw hám izertlew haqqındaǵı ilim bolıp, bunda sızıqlı funkciyanıń belgisizlerine sızıqlı shegaralawshi shártleri qoyıladı. Demek, SP máselesi funkciyanıń shártli ekstremum máselesine tiyisli boladı.
   

Meyli tómendegi (1)sızıqlı funkciyası berilgen bolıp

Z  С₁x₁  С₂ x₂ ...  С_nx_n  min
hám bul funkciyasına tómendegi sheklewleri qoyılǵan bolsın
_a₁₁x₁  a₁₂ x₂  ...  a_{1 j} x _j  ...  a_1n x_n  b₁ ,
(1)

^a x  a x  ...  a x  ...  a x  b ,

_ 21 1 22 2 2 j j
2n n 2

 ^,
a x  a x  ...  a x  ...  a x  b ,

_ i1 1
i 2 2
ij j in n j

 _,

(2)

_a_m1x₁  a_m2 x₂  ...  a_mj x _j  ...  a_mn x_n  b_m ,


x_j  0 (i 1,n)


(3)

bunda
a_ij , b_i
hám C _j - berilgen turaqlı shamalar.

1. 
   sızıqlı funkciyasına eń kishi(minimum) mánisin jetkeretuǵın hám (2)
   

sheklewler sistemasın qanaatlandıratuǵın talap etiledi.
x₁, x₂ ,..., x_n
teris emes mánislerin tabıw

2. 
   sheklewler sistemasında barlıq b _j , boladı.
   

j  1, m
teris emes dep esaplawǵa

Bul másele bir neshe jazıw formasına iye.
1.Vektor formasında jazılıwı. Tómende berilgen sheklewler sistemasında

A₁x₁  A₂ x₂  ... A_n x_n  A₀ ,
Z C X
X 0,
(4)
⁽ 1^{ )}

sızıqlı funkciyanıń eń kishi(minimum) mánisin tabıw, bunda
C (c₁,c₂ ,...,c_n ) ^,

X (x₁, x₂ ,..., x_n ) ^{. C  X}
- eki vektordıń skalyar kóbeymesi,

 ^a₁₁ 
 ^a₁₂ 
 ^a_1n 
 ^b₁ 

 _a 
 _a 
 _a 
 _b 

A  ^
1 _.
21 _{ ,}

_{A  } 22
2 _.
^ , . . . ,

A  ^
n _.
2n _{ ,}

_{A }  ² 
⁰ _. 

 _a 
 _a 
 _a 
 _b 

 m1 
 m 2 
 mn 
 m 

vektorları sáykes ózgeriwshilerindegi hám saltan aǵzalarındaǵı koefficientleri.

Matrica formasında jazılıwı.

AX  A₀ ,
X 0, ^{sheklewler sistemasın}

qanaatlandıratuǵın Z C X
funkciyanıń minimum mánisin tabıw, bunda

 ^x₁ 

 _x 

C (c ,c ,...,c ) ^{- qatar- matricası, A(a}
) - sistemanıń matricası,
X  ^{ 2  -}

1 2 n ^ij
_. 
 _x 

 ^b₁ 

 _b 
 m 

baǵana-matricası,
A  ^
0 _.
^{2 } - baǵana-matricası.


 _b 
 m 
Qósındı belgisi járdeminde jazılıwı. Máselede qoyılǵan sheklewler sistemasın

_a_ij x_j b_i ,

n
j1

i 1,m,

10. 
    _j 0,
    

j 1, n _.

qanaatlandıratuǵın
Z _C_j x_j j1
sızıqlı funkciyanıń minimum mánisin tabıw.

1. 
   anıqlama. (2) hám (3) shártlerin qanaatlandıratuǵın
   

X (x₁, x₂,..., x_n )

vektorın sızıqlı programmalastırıw máselesiniń jobası yamasa sheshimi dep ataydı.

2. 
   ^{anıqlama. Egerde (4) jikleniwindegi oń anıqlanǵan} x_i
   

koefficientleri

menen qatnasqan


A_i , i  1,m
vektorları sızıqlı baylanıssız bolsa, onda

X (x₁, x₂ ,..., x_n ) ^{jobası tayanısh sheshimi(jobası) dep ataladı.}
A_i ^{vektorları m -ólshemli bolǵanı sebepli, onda tayanısh jobaǵa berilgen}
anıqlamadan, onıń oń anıqlanǵan komponentleri sanı m nen kóp bolmaydı.

3. 
   anıqlama. Egerde máseleniń tayanısh jobası m ge teń bolgan oń komponentlerıne iye bolsa, onda tayanısh joba aynımaǵan , al keri jaǵdayda tayanısh joba aynıǵan dep ataladı.
   
4. 
   anıqlama. Sızıqlı funkciyasına eń kishi(eń úlken) mánisin jetkeretuǵın jobanı sızıqlı programmalastırıw máselesiniń optimal jobası yamasa optimal sheshimi dep ataydı.
   

2. SP máselesiniń tayanısh jobasın jasaw.

Meyli bizge bizge (1)-( 3) sızıqlı programmalastırıw máselesi qoyılǵan bolsın. Bunda, dáslep máseleniń sheklewler sisteması m birlik vektorlarına iye dep hám olar dáslepki m vektorları boladı dep boljaymiz. Onda (1) sızıqlı funkciyasınıń tómendegi sheklewler sistemasında

^x1 ^{ a}1,m1 ^xm1
...  a_1n x_n  b₁ ,

x

 a

^ 2 2,m1

^xm1

• 
  ...  a_{2 n} x_n  b₂ ,
  

(5)

_... ... ... ...
... ...
...
... ... ...

_{ xm}

• 
  ^am,m1
  

^xm1

• 
  ...  a_mn x_n
  

 b_m

x _j  0
^{j  1, n}_. (6)

eń kishi(minimum) mánisin tabıw zárúr boladı.
(5) sistemasın vektorlıq formasında jazamız:
x₁ A₁  x₂ A₂  ...  x_m A_m  x_m1 A_m1  ...  x_n A_n  A₀ ^{, (7)}

bunda


A₁


 1,0,...,0^ ,



2
A  0,1,...,0^ ,…,



m
A  0,0,...,1^ ,

A  a , a


,...,a
^, …, A
 a , a


,...,a
^ ,
A  b ,b ,...,b ^

m1
1,m1
2,m1
m,m1
n 1n 2n mn
0 1 2 m

A₁, A₂,..., A_m ^{vektorları m -ólshemli keńisliktiń sızıqlı baylanıssız birlik vektorları}
boladı hám olar bul keńisliktiń bazisın payda etedi. Sonlıqtan (7) jiklewindegi

x₁, x₂ ,..., x_m
belgisizlerin bazislıq dep, al
x_m1, x_m2 ,..., x_n
belgisizlerin erkli(bazislıq

emes) belgisizler dep olardı nolge teńep, hám


b_i  0, i 1,m
esapqa alıp, al

A₁, A₂ ,..., A_m
vektorları birlik vektorları bolǵanı ushın, qoyılǵan máseleniń dáslepki

jobasına iye bolamız
^{X 0 }  ^{x1  b1, x2  b2,..., xm  bm , xm1  0,..., xn  0}
(8) jobasına tómendegi jikleniw sáykes keledi
x₁A₁  x₂ A₂ ...  x_m A_m  A₀
(8)
(9)

bunda
A₁, A₂ ,..., A_m
vektorları sızıqlı baylanıssız boladı, sonlıqtan dúzilgen

baslanǵısh jobası tayanısh bolıp esaplanadı..
Endi (8) baslanǵısh jobasınan paydalanıp, máseleniń ekinshi tayanısh jobasın

dúziw múmkinshiligin qaraymız.
A₁, A₂ ,..., A_m
vektorları m ólshemli keńisliktiń

bazisın payda etedi, sonlıqtan (7) teńliktegi n vektorlardıń hár birin bazis vektorları boyınsha tek ǵana bir usıl menen jayıp(jiklew) jazıwga boladı:

A_j  _x_ij A_i ,
i1


j  1, n .

Meyli , baziske kirmeytuǵın bazı bir vektorı ushın, mısalı
^Am1
vektordıń

^xi, m1
jikleniwindegi koefficientleriniń eń keminde biri oń bolsın dep boljaymız.
^x1,m1 ^A1 ^{ x}2,m1 ^A2 ^{ ...  x}m,m1 ^Am ^{ A}m1 _{. (10)}

Qálegen bir   0 (házirshe belgisiz) shamasın saylap alıp, oǵan (10) teńliktiń eki jaǵın kóbeytemiz hám kelip shıqqan nátiyjeni (9) teńlikten aǵzama-aǵza ayιrιp alamız. Nátiyjede:
 ^x₁ ^{  x}_1m1  ^A₁ ^  ^x₂ ^{  x}_2m1  ^A₂ ^{ ... }  ^x_m ^{  x}_mm1  ^A_m ^{  A}_m1 ^{ A}₀ ^{. (11)}
iye bolamız.
Solay etip, egerde (11)dıń komponentlerı teris emes bolsa, onda
X₁  _x₁  x_{1, m1}, x₂  x_{2, m1}, . . . , x_m  x_{m, m1}, , 0,...,0_
vektorı máseleniń jobasι boladı.

Uyǵarıwmız boyınsha   0
bolǵanlıqtan, onda teris emes
^xi, m1
^kiriwshi X₁

vektordıń barlıq komponentları teris emes boladı. Sonlıqtan bul vektordıń tek ǵana oń mánisli koefficientleri bar komponentlerin tekseriw kerek, yaǵnıy barlıq

^xi, m1 ^{ 0}
ushın


x_i   x_{i, m1}  0.


(12)

teńsizligi orınlanatuǵınday etip
  0 shamasın saylap alıw kerek boladı.

(12) teńsizliginen

  ^{xi x}i, m1


iye bolamız. Demek,

0    min
i
x_i ^xi, m1
, (13)

^{shártin qanaatlandıratuǵın qálegen  ushın} X₁ ^{- máseleniń jobası boladı, bunda}

minimum mánisi
^xi, m1 ^{ 0
ushın} i ^{boyınsha alınadı}_.

Biraq tayanısh jobası
m 1
oń mánistegi komponentlerıne iye bolıwı

múmkin emes, sonlıqtan
X₁ ^{jobasında eń keminde bir komponentasın nolge}

aylandırıw zárúr boladı. Sonlıqtan (13) teńsizliginde

  ₀
 min ^xi
i _x
, (14)

i, m1

dep esaplap, onda minimal mánisine jetisetuǵın

X₁ ^{komponentası nolge aylanadı.}

Meyli bul komponentası birinshi qatarda tursın, yaǵnıy

0
^{  min xi  x1} .
^{i x}i,m1 ^x1,m1

₀
bolamız:
dıń mánisin (11)-ge aparıp qoyyamız hám tómendegi nátiyjege iye

^ x  ^x x
 
A  x
_ x _x

A  ... 

1
_ 1 1, m1 _ 1 _ 2
1
2, m1 _ 2

_ ^x1, m1
_{ } ^x1, m1
^ _x x

^ x

bunnan
 _{ m} 

1
^x1, m1
^xm, m1 _ ^Am ^

1
^x1, m1
A_m1  A₀ ,

x^ A  x^ A
 ...  x^ A  x^ A  A

2 2 3 3
m m m1
m1 0

jikleniwine iye bolıp hám oǵan tomendegi jańadan dúzilgen tayanısh jobası sáykes keledi:
X₁  (0, x^₂ , x₃^,...x^_m , x^_m1,0,...,0)

bunda
^xi^{  x}i ^{ }0 ^xi, m1^,
i  2,3,..., m ,
^xm1 ^{ }0
belgilewleri kiritilgen.

Bazisten bir vektordı shıǵarıw hám onıń ornına ₀
járdeminde ekinshi bir

vektorın kiritiw ámeli Jordan-Gauss usılı menen bir bazisten ekinshi bir baziske

ótiwge sáykes keledi. Sonlıqtan
A₂ , A₃ ,..., A_m , A_m1
vektorlar sisteması sızıqlı

baylanıssız boladı hám jańa bazis bolıp esaplanadı. Kelesi tayanısh jobasın anıqlaw ushın


A₂ , A₃ ,..., A_m , A_m1
bazisine

kirmeytuǵın qálegen bir vektordı usı bazistıń vektorları boyınsha jiklep, onnan soń

bul bazistıń vektorlarınıń biri bazisten shıqqanday etip zárúr boladı.
₀  0
shamasın anıqlaw

Demek, qoyılǵan máseleniń jańa tayanısh jobalarına ótiw processi baziske
kiritilgen hám bazisten shıǵarılatuǵın vektorlardı anıqlawdan ibarat boladı. Baziske kiritiletuǵın vektordı anıqlaw ushın paydalanatuǵın kriteriyası, simpleks usılınıń eń tiykarǵı elementleriniń biri boladı.

Egerde
^Am1
vektorın baziske kiritiw kerek bolsa, al onıń jiklewindegi barlıq

^xi,m1 ^{ 0}
bolsa, onda (10) jikleniwindegi vektorlardıń biri bazisten

shıǵarılatuǵınday etip
  0
^{saylap alıw múmkin emes boladı. Bul jaǵdayda} X₁

jobası
m 1 oń komponentlerine iye bolıp, al
A₁, A₂ ,..., A_m , A_m1
vektorlar sisteması

sızıqlı baylanıslı boladı hám sheshimler kópjaqlısınıń múyesh noqatında emes, al sızıqlı funkciyası minimum mániske jetisiwı múmkin emes bolǵan ishki noqatın anıqlaydı. Bul sızıqlı funkciyaǵa sáykes keletuǵın gipertegisligi N vektorınıń baǵıtında qanshelli uzaq jılıstırsaq ta, ol sheshimler kópjaqlısına tayanısh gipertegislik bola almaydı, yaǵnıy sızıqlı funkciyası sheshimler kópjaqlısında shegaralanbaǵan boladı.
Solay etip, egerde SP máselesiniń sheklewler sisteması, saltan aǵzalardıń teris emes mánislerinde birlik bazisine iye bolsa, onda qósımsha esaplawlardı

orınlamay, máseleniń dáslepki tayanısh jobasına iye bolıwmız múmkin, sonıń menen birge sáykes vektorlardıń bazis vektorları boyınsha jikleniwiniń koefficientlerin anıqlawǵa boladı.

3.