Nókis filialí «Kompyuter injiniring» qánigeligi

2.3. Ekki basqıshlı simpleks usil.


Simpleks-usıldıń birinshi basqıshı.
Joqarıda simpleks-usıl algoritmı tómendegi boljawlarda bayanlaindi:
1) kanonik másele jobalarǵa iye;
2) tiykarǵı sheklewler matritsasi A nıń qatar-vektorları sızıqlı baylanıspaǵan
( rankA= m);
3) qandayda-bir bazis joba málim. Bul barlıq boljawlardan waz keshken halda da kanonik máselege simpleks-usıldı qollap onı sheshiw múmkin. Bul bolsa simpleks-usıldıń eki basqıshında atqarıladı.
Birinshi basqıshda tómendegi járdemshi másele qaraladı :

Bul jerde e = (1,.. ., 1) - m-vektor, x_e={x_n+1….x_n+m} - jasalma ózgeriwshiler vektorı.
Bul máselede jobalar kompleksi bántli ( ={x=0, x_c=b } b - bazis joba ) hám maqset funksiyası joqarıdan shegaralanǵan : -e^’x_c 0. Demek , (5. 1) birinshi basqısh máselesi hámme waqıt sheshimge iye. Birinshi basqısh máselesiniń áhmiyeti tómendegi teoremada kórsetilgen.
5. 1-teorema. Kanonik máseleniń jobalar kompleksi bos bolmawi ushın oǵan járdemshi (5. 1) máseleniń {x’ , x’_c} sheshiminde x’_c=0 bolıwı zárúr hám jetkilikli bolıp tabıladı.
Dàlilleniwi. Zárúrliligi. Eger x’ - kanonik máseleniń jobası bolsa, {x’ , x’_c=0} - (5. 1) máseleniń sheshimi boladı : sebebi (5. 1) máseleniń jobası bolǵan bul vektorda e^’x_c 0
; (5. 1) máseleniń basqa qálegen {x, x_c } rejesinde bolsa -e^’x_c 0 teńsizlik atqarıladı.
Jetkilikliligi. Eger {x’ , x’_c=0} - (5. 1) máseleniń sheshimi bolsa, x^’ kanonik máseleniń jobası bolıwı ayqın bolıp tabıladı. Teorema tastıyıq boldı.
Birinshi basqısh máselesin sheshiw járdeminde berilgen kanonik
másele jobalarǵa iyema yamasa joqpa degen sorawǵa juwap beriw hám ol
jobalarǵa iye bolsa, baslanǵısh bazis rejani anıqlaw múmkin.


Simpleks-usıldıń ekinshi basqıshı.
Birinshi basqısh máselesine simpleks-algoritmdı qollaymiz. Onıń tiykarǵı shekleniwler matritsasi {A , E_m } kóriniste bolǵanı ushın {x = 0, x_c=b} - baslanǵısh bazis joba boladı. Eger simpleks-algoritm menen sheshilgen (5. 1) máseleniń
{x’ , x’_c} optimal bazis rejesinde x’_c 0 yaǵnıy noldan ayrıqsha jasalma ózgeriwshi ámeldegi bolsa, berilgen kanonik másele rejege iye emes. Sonday eken, bul halda máseleni sheshiw procesi tawsıladı. Eger x’_c 0 bolsa, bul halda simplek-usılda ekinshi basqıshqa ótiw arqalı berilgen máseleni sheshiw procesi dawam ettiriledi.
Shama menen oylayıq, (5. 1) máseleniń {x’ , x’_c} optimal bazis jobası ushın J’_B
- bazis indeksleri kompleksi, - uyqas bazis matritsa bolsın.
Eger x’_c=0 yaǵnıy barlıq jasalma
ózgeriwshiler nolǵa teń hám bazis ózgeriwshiler arasında jasalma
ózgeriwshiler joq bolsa, bul halda, x’ - berilgen kanonik máseleniń
baslanǵısh bazis jobası boladı. Oǵan simpleks-algoritmdı qollaymiz,
yaǵnıy simpleks-usıl ekinshi basqıshına ótemiz.
Endi yaǵnıy barlıq jasalma ózgeriwshiler nolge teń bolsada, bazis ózgeriwshiler arasında jasalma ózgeriwshiler de bar bolǵan haldı qaraymız. Bul halda (5. 1) másele {x’ , x’_c} sheshiminiń x’_I jasalma bazis ózgeriwshisine uyqas túrde hár bir j J ushın vektordıń x_i,j komponentasini esaplaymiz. Eger qandayda bir j, J ushın bolsa, taǵı bir simpleks-iteratsiya atqarıp, x’_I ózgeriwshini (5. 1) máseleden shıǵaramız hám J’_E de I ornına j ni kiritemiz. Eger barlıq
ushın x_i,j=0 bolsa, A matritsaning ústinleri e_i,-n birlik vektorǵa ortogonal boladı.
Nátiyjede (5. 1) máseleniń ólshemi birge azayadı. Sol tárzde barlıq nolǵa teń jasalma ózgeriwshilerdi joǵatıp hám kanonik máseleniń tiykarǵı shártlerinen sızıqlı baylanısqan teńliklerdi shıǵarıp tastap onıń baslanǵısh bazis rejesine iye bolamız. Sol baslanǵısh bazis rejeden simplek-usıldıń ekinshi basqıshı baslanadı.

III. Juwmaqlawshı bo’lim .

Juwmaqlap aytqanda Simpleks usılı sızıqlı programmalastırıw máselesin sheshiwdiń tiykarǵı usıllarınan biri bolıp, usıl óz atınıń " simpleks" sózinen kelip shıqqan halda, eń ápiwayı konveks kópmuyishlikti ańlatadı, onıń úshları sanı mudamı boslıq ólsheminen birge kóp. Simpleks usılı AQSHda 1940 -jıllardıń aqırında matematikalıq J. Dansig tárepinen islep shıǵılǵan.

Simpleks-usıl sızıqlı programmalastırıwdıń kanonik forma daǵı máselesi ushın qo'laniladi. Biraq bul fakt simpleks-usıldıń ulıwmalıǵın shekley almaydı, sebebi joqarıda kórgenimizdey, sızıqlı programmalastırıwdıń qálegen máselesin oǵan ekvivalent kanonik formadaǵı máselege keltiriw múmkin.
Simpleks-usıldıń mánisin túsinip alıw ushın ólshemleri kishi bolǵan sızıqlı programmalastırıw máselelerinde simpleks-algoritm boyınsha esaplawlardı ratsional shólkemlestiriwdiń áhmiyeti úlken bolıp tabıladı. Simpleks-algoritm boyınsha esaplawlar orınlanǵanda odaǵı formulalardan tikkeley paydalanıw talay quramalı processti óz ishine aladı. Bunda algoritmdı simpleks-kesteler járdeminde ámelge asırıw bolsa esaplawlardı ańsatlastıradı hám másele sheshimin tabıw procesin
ayqınlaw oyda sawlelendiriwge múmkinshilik beredi. Atap aytqanda, optimallıq kriteryanı hám sheshim ámeldegi bolmaw shártlerin tekseriw, simpleks-iteratsiyanı
atqarıp jańa bazis rejege ótiw sıyaqlı operatsiyalardı qolay tárzde orınlaw múmkin boladı.