• Simpleks-usıldıń ekinshi basqıshı.
    		•

    Ekki basqıshlı simpleks usil




    Download 190.25 Kb.
    bet4/5
    Sana26.05.2022
    Hajmi190.25 Kb.
    #22045
    1   2   3   4   5
    Bog'liq
    Algaritim
    AXMATOVA SARVINOZ ABROR QIZI, Psixoloyiya fani pridmeti va vazifalari, metodlari, Morfemika haqida umumiy malumot f9ac5302f93d409466983def8f28edb0, MUXLISA, Iqtosodiyot nazariya, Р,Диёров, lab11 12, -1-NAZORAT-ISHI, 9999, buklet, Роман Франсуа Рабле, 6 sinf tabiiy fan nazorat ishi kitobchasi, 11-Sinf tarbiyaviy soat, NEWSLAR
    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, xe={xn+1….xn+m} - jasalma ózgeriwshiler vektorı.
    Bul máselede jobalar kompleksi bántli (={x=0, xc=b } b - bazis joba ) hám maqset funksiyası joqarıdan shegaralanǵan : -e’xc0. 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’xc0
    ; (5. 1) máseleniń basqa qálegen {x, xc } rejesinde bolsa -e’xc0 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 , Em } kóriniste bolǵanı ushın {x = 0, xc=b} - baslanǵısh bazis joba boladı. Eger simpleks-algoritm menen sheshilgen (5. 1) máseleniń
    {x’ , x’c} optimal bazis rejesinde x’c0 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’c0 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ıń xi,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 xi,j=0 bolsa, A matritsaning ústinleri ei,-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ı.

    Download 190.25 Kb.
    1   2   3   4   5




    Download 190.25 Kb.