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

SP máselesiniń optimal jobasın anıqlaw. Optimallıq shártleri.

Meyli (1),( 5),( 6) SP máselesi jobaǵa iye bolıp hám onıń hár bir tayanısh jobası aynımaǵan bolsın. Bul jaǵdayda (8) tayanısh jobası ushın

0

m
x₁ A₁  x₂ A₂  ...  x_m A_m  A₀
(15)

1

1

2

2
x C  x C
 ...  x C
 ZX 
, (16)

m
iye bolamız, bunda barlıq sızıqlı funkciyanıń mánisi.

10. 
     0 ^{, al}
    

^Z  ^{X 0} 
– bul (8) jobaǵa sáykes keliwshi

Qálegen
A_j vektorınıń
A₁ , A₂ ,..., A_m
bazis vektorları boyınsha tek ǵana bir usıl

menen jiklenedi:


x_{1 j} A₁  x_{2 j} A₂ ...  x_mj A_m  A_j ,


j 1,n _{, (17)}

Sonlıqtan baziste
A_j vektorınıń jikleniwine sızıqlı funkciyanıń tek bir

x_{1 j}C₁  x_{2 j}C₂ ...  x_mjC_m  Z _j ,

j 1,n
, (18)

^{mánisi sáykes keledi, bunda} Z _j
– sızıqlı funkciyanıń belgisizleriniń ornına mánisi

^j -vektorınıń jikleniwindegi sáykes koefficientlerin aparıp qoyǵandaǵı onıń mánisi.

A_j vektorına sáykes keliwshi sızıqlı funkciyanıń koefficientleri С _j
dep

belgileymiz. Sonda tómendegi teorema durıs boladı. Bul teoremalardı dálillewsiz

keltiremiz.

1. 
   teorema (minimum máselesi ushın). Egerde bazi bir A_j
   

vektorı ushın

Z _j  C_j  0
shárti orınlansa, onda
X ₀ ^{- optimal joba emes hám
Z}  ^X  ^{ Z}  ^{X 0} 

^{orınlanatuǵın} X ^{jobasın dúziwge boladı.}
Juwmaq. Egerde (1),( 5),( 6) máselesiniń bazı bir


X ₀ ^{sheshimi ushın barlıq}

A_j ,


j 1,n
vektorlarınıń berilgen bazis boyınsha jikleniwleri

Z _j  C _j  0
(19)

shártin qanaatlandırsa, onda
X ₀ ^{vektorı bul máseleniń optimal sheshimi boladı.}

Bunda
Z _j  C_j mánisleri jobanıń bahaları dep ataladı. Demek, sızıqlı

funkciyanıń minimum mánisi izlenip atırǵan máseleniń tayanısh sheshimi, onıń optimal sheshimi bolıwı ushın, bul sheshimniń bahaları oń emes bolıwı zárúr hám jetkilikli.

Maqset funkciyanıń maksimum(eń úlken) mánisi izlenip atırǵan (1), (5), (6) sızıqlı programmalastırıw máselesi ushın tómendegi teorema durıs boladı.

2. 
   teorema. Egerde bazı bir
   

A_j vektorı ushın
Z _j  C _j  0
shárti orınlansa,

onda
X ₀ ^{sheshimi, onıń optimal sheshimi emes hám}
ZX   ZX 
shárti

0
^{orınlanatuǵın} X ^{sheshimin jasawǵa boladı.}

^{Juwmaq: Egerde bazı bir} X ₀
berilgen bazis boyınsha jikleniwleri
sheshimi ushın
A_j ,


j  1,n
vektorlarınıń

Z _j  C _j  0
(20)

teńsizligin qanaatlandırsa, onda máseleniń sheshimi boladı.
X ₀ ^{tayanısh sheshimi onıń optimal}

Solay etip, maqset funkciyasınıń minimum mánisi izlenip atırǵan (1), (5), (6)
máselesiniń tayanısh jobası, onıń optimal sheshimi bolıwı ushın (19) teńsizliginiń orınlanıwı, al maqset funkciyasınıń maksimum mánisi izleniwshi (1),(5),(6) máselesiniń (20) teńsizliginiń orınlanıwı zárúrli hám jetkilikli shártleri boladı.
4.Jasalma Bazis Usil
Joqarıda kórgen edik, sızıqlı programmalastırıwdıń tiykarǵı máselesinde P_i vektorlar ishinde m dana birlik vektor bar bolsa, onda tayansh sheshimdi tabıw múmkin. Lekin sızıqlı programmalastırıwdıń kóp máseleleri sızıqlı programmalastırıwdıń tiykarǵı máselesi kórinisinde berilgen bolıp, tayansh sheshimi bar bolsada, P_i vektorlar ishinde hámme waqıt m dana birlik vektorlar bolmaydı. Bunday jaǵdaylarda tómendegi máseleni jasalma bazis usılınan paydalanıp sheshemiz:

1. 
   15- másele. Tómendegi
   

shegaralıq shártlerdi qánaatlandırıwshı:

funksiyanıń maksimum ma`nisin tabıń

P_j vektorınıń ishinde m dana birlik vektor joq
1.Anıqlama. Tómendegi

Shegaralıq shártlerde

funksiyanıń maksimum ma`nisin tabıw (1.17)-(1.18) máselege salıstırǵanda keńeytirilgen másele dep ataladı.
B ul jerde M — aldınan berilmegen jetkiliklishe úlken oń san.
Keńeytirilgen másele ko'rinishdagi 
t ayansh sheshimge iye bolıp, birlik vektorlar sisteması arqalı anıqlanadı jáne bul bazis m ólshewli vektor keńisligin quraydı. Payda bolǵan bazis jasalma bazis dep ataladı.
Sonday etip, keńeytirilgen másele tayansh sheshimge iye bolǵanı ushın, bul máseleni simpleks usılı menen sheshiw múmkin boladı.
Bul jerde tómendegi teorema orınlı bolıp tabıladı
1 t e o re m a. Eger keńeytirilgen (1. 17) - (1. 18) máseleniń

o ptimal jobasında bolsa,

onday jaǵdayda joba (1.15-1.16) máseleniń optimal jobası bolıp tabıladı.

Teoremani dáliyllewsiz qabıl etemiz.
Solay etip, keńeytirilgen máseleniń optimal jobasınıń jasalma bazis ózgeriwshileri nolge teń bolǵanınan dáslepki máseleniń optimal jobası kelip shıǵadı.
Máseleniń tayansh sheshimi

b olǵanınan keńeytirilgen másele ushın sızıqlı forma tómendegishe boladı :

niń mánisi ǵa teń boladı.

Sonday eken, F₀ hám z_j-c_j ayırma bir-birine baylanıslı bolmaǵan eki bólimnen ibarat bolıp, birinshisi M ǵa baylanıslı, ekinshisi M ǵa baylanıslı emes.

Usınıń menen bir qatarda, (m+2) qatarǵa M dıń koefficiyentleri kiritiledi, (m+ 1) qatar bolsa M qatnaspaǵan qosılıwshılarǵa tiykarlanıp toltırıladı. Endi (m+2) qatardaǵı eń kishi teris sanǵa uyqas bolǵan vektordı bazisga kiritemiz hám tayansh jobanı jaqsılaymız. Simpleks kestelerdi esaplaw simpleks kestelerdi dúziwdiń ulıwmalıq qaǵıydalarına tiykarlanadı.
Sonı da aytıw kerek, (m+2) qatarǵa tiykarlanǵan iteraciya procesi tómendegishe bolaman degenge shekem dawam ettiriledi:
1) hámme jasalma vektorlar qadaǵan etilmegen jaǵday
2) derlik jasalma vektorlar qadaǵan etilmegen bolıp, (m+2) qatardaǵı P1, P2,…, Pn+m ga uyqas bolǵan baǵanalarda teris sanlar bolmaǵan jaǵday.
Birinshi jaǵdayda bazis dáslepki máseleniń qandayda bir tayansh jobasına juwap beredi hám máseleniń optemal joba tabıw (m+ 1) qatarǵa tıykarlanıp dawam ettiriledi.
Ekinshi jaǵdayda bolsa (m+2) qatardaǵı P vektorǵa uyqas bolǵan san
teris, bul halda másele sheshimge iye emes dep ataladı. Eger P < 0
bolsa, tabılǵan tayansh joba dáslepki máseleniń payda bolǵan jobası boladı, baziste bolsa jasalma vektorlardıń hesh bolmaǵanda qandayda-birı qatnasadı.
Eger dáslepki máselede qandayda bir vektor birlikler qatnassa, ol halda bul vektorlami jasalma bazisga kirgiziw kerek.
Sonday etip, (1. 15) - (1. 16 ) máseleni jasalma bazis usılı menen sheshiw ushın tómendegi qádemlerdi orınlaw kerek:
1) (1. 17) - (1. 18) keńeytirilgen másele dúziledi;
2) keńeytirilgan máseleniń tayansh(optimal) jobası tabıladı ;
3) simpleks usılın qollap, jasalma vektorlar bazisten shiǵarıladı (qadaǵan etiledi). Nátiyjede (1. 15) - (1. 16 ) máseleniń tayansh jobası tabıladı yamasa bolmasa máseleni sheshiw múmkin emesligi kórsetiledi;
4) (1. 15) - (1. 16 ) máseleniń tayansh rejesine tıykarlanıp, dáslepki máseleniń optimal jobası tabıladı yamasa bolmasa máseleni sheshiw múmkin emesligi kórsetiledi.