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

II. Tiykarǵı bólim.
2.1. Simpleks usılı haqqında túsinik.

Simpleks usılı - bul kóp ólshewli keńislik qabarıq ko'pmuyishliklerdiń úshlerin sanap ótiw arqalı sızıqlı programmalastırıwdı optimallastırıw máselesin sheshiw algoritmı bolıp tabıladı.

Usıldıń mánisi: jergilikli optimallıqtıń zárúr shártleri qanatlandırılġanġa shekem, sızıqlı funktsional monoton túrde azayıp baratuǵın tiykarǵı sheshimlerdi qurıw.
Tariyxan, sızıqlı programmalastırıwdıń ulıwma mashqalası birinshi ret 1947 jılda Jorj Bernard Dantsig, Marshall vud hám olardıń AQSh Áskeriy-hawa kúshleri departamentindegi sherikleri tárepinen qoyılǵan. Sol waqıtta bul gruppa áskeriy hám joybarlaw máseleleri ushın matematikalıq hám tiyisli usıllardan paydalanıw múmkinshiligin úyrengen. Keyinirek, bul ideyalardı islep shıǵıw ushın Áskeriy hawa kúshlerinde Project SCOOP dep atalǵan izertlew toparı dúzildi. SEAC kompyuterinde sızıqlı programmalastırıw máselesin birinshi tabıslı sheshiw 1952 jıl yanvarda ámelge asırıldı.
Sızıqlı programmalastırıw mashqalası sonda, berilgen sızıqlı sheklewler astında kóp ólshewli keńislik birpara sızıqlı funktsionallardı maksimal yamasa minimallastırıw kerek.
Itibar beriń, ózgeriwshiler degi sızıqlı teńsizliklerdiń hár biri tiyisli sızıqlı keńislik yarım boslıqtı shegaralaydı. Nátiyjede, barlıq teńsizlikler birpara qabarıq ko'pburchakni (itimal sheksiz) chekleydi, onı ko'pburchak kompleksi dep da ataladı. W (x) = c teńlemesi, bul jerde W (x) maksimallastırılatuǵın (yamasa minimallastırılatuǵın ) sızıqlı funksional L (c) giper tegisligin payda etedi. c ga baylanıslılıq parallel giperplanlar shańaraǵın payda etedi. Keyin ekstremal másele tómendegi formulaǵa iye boladı : eń úlken c ni tabıw kerek, sonda L (c) giper tegislik ko'pburchakni keminde bir noqatda kesip ótedi. Itibar beriń, optimal gipertekislik hám ko'pmuyishlik kesilispesi keminde bir shıńnı óz ishine aladı hám eger kesilisiw shet yamasa k ólshewli yuzni óz ishine alsa, bir neshe boladı. Sol sebepli funktsional maksimaldı ko'pmuyishliktiń shıńlarında izlew múmkin. Simpleks usılınıń principi sonnan ibarat, ko'pmuyishliktiń shıńlarınan biri saylanadı, sonnan keyin onıń qırları boylap shıńdan shıńǵa shekem bolǵan háreket funktsional ma`nisin asırıw baǵdarı boyınsha baslanadı. Ámeldegi shıńdan funksional ma`nisi joqarı bolǵan basqa shıńǵa shet boylap ótiw múmkin bolmaǵanda, c dıń optimal ma`nisi tabılǵan dep esaplanadı.
Simpleks usılı boyınsha esap -kitaplar izbe-izligin eki tiykarǵı basqıshqa bolıw múmkin:
múmkin bolǵan sheshimler kompleksiniń baslanǵısh shıńın tabıw,
maqset funktsiyası ma`nisin optimallastırıwǵa alıp keletuǵın bir shıńdan ekinshisine izbe-iz ótiw.
Bunnan tısqarı, birpara jaǵdaylarda, dáslepki sheshim anıq yamasa onıń tariypi quramalı esap -kitaplardı talap etpeydi, mısalı, barlıq sheklewler " kem yamasa teń" kórinisindegi teńsizlikler menen kórsetilgende (keyin nol vektor, álbette, múmkin bolǵan sheshim bolıp tabıladı., eger, itimal, ol eń maqul túsetuǵınnan uzoq bolıp tabıladı). Bunday máselelerde simpleks usılınıń birinshi basqıshın pútkilley shıǵarıp taslaw múmkin. Simpleks usılı, óz gezeginde, bir fazalı hám eki fazalı bolıp bólinedi.