|
Nókis filialí «Kompyuter injiniring» qánigeligi
|
| bet | 1/5 | | Sana | 26.05.2022 | | Hajmi | 190.25 Kb. | | #22045 |
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
ÓZBEKSTAN RESPUBLIKASÍ
INFORMACIYALÍQ TEXNOLOGIYALARÍ HÁM KOMMUNIKACIYALARÍN RAWAJLANDÍRÍW MINISTRLIGI
MUHAMMED AL-XOREZMIY ATINDAǴÍ
TASHKENT INFORMACIYALÍQ TEXNOLOGIYALARÍ UNIVERSITETI
NÓKIS FILIALÍ
«Kompyuter injiniring » qánigeligi
2-kurs 301-20 topar studenti Keńesbaeva Dilyafruzdıń
« Algoritimlerdi proektlestiriw » páninen
Óz betinshe jumısı
Tema: Sızıqlı programmalastırıw máseleleriniń kanonik kórinisi.
Simpleks usıl.
Tayarlaǵan:_________________D. Keńesbaeva.
Qabıllaǵan:_________________ Sh. Abdiganiev.
Nókis – 2022
Joba:
I. Kirisiw.
1.1. Sızıqlı programmalastırıw máselesi ushın sheshim.
II. Tiykarǵı bólim.
2.1. Simpleks usılı haqqında túsinik.
2.2. Sızıqlı programmalastırıw máselelerin sheshiwde simpleks usıl algoritmı hám programması.
2.3. Ekki basqıshlı simpleks usil.
III. Juwmaqlawshı bo’lim .
IV. Paydalanılg’an a’debiyatlar.
I. Kirisiw.
Sızıqlı programmalastırıw máselesi ushın sheshim.
Sızıqlı programmalastırıw máselesi dep sızıqlı funksiyanıń sızıqlı teńlik hám teńsizlikler kórinisindegi shártlerde minimumı yamasa maksimumini tabıw máselesine aytıladı. Sızıqlı programmalastırıw máselesin ulıwma halda tómendegishe jazıw múmkin:
Bul máselede berilgen barlıq sızıqlı shártlerdi qánaatlantıratuǵın barlıq x1,x2,….xn ózgeriwshilerden dúzilgen hár bir n- ólshemli X=( x1,x2,….xn) vektorǵa sızıqlı programmalastırıw máselesiniń jobası dep ataladı. Sızıqlı programmalastırıw máselesiniń barlıq jobalar kompleksin X dep belgileymiz.
Eger qandayda bir x0=( x10,x20,….xn0) X hám barlıq x=( x1,x2,….xn) X ushın (uyqas túrde, )munasábet atqarılsa x0=(x10,x20,….xn0) X rejege minimum (uyqas túrde, maksimum) ushın qoyılǵan sızıqlı programmalastırıw máselesiniń optimal jobası dep ataladı.
Sızıqlı programmalastırıw máselesiniń sheshimi degende onıń optimal rejesin túsinemiz. Sızıqlı programmalastırıw máselesiniń barlıq optimal jobaları kompleksin x0 dep belgileymiz:
Eger x0=( x10,x20,….xn0) X - optimal joba bolsa, maqset funksiyasınıń optimal ma`nisi zmin(zmax)= boladı.
Sızıqlı programmalastırıw máselesinde ózgeriwshileri sanı úshten aspaǵan jaǵdaylarda máseleniń mumkin bolǵan jobalar kompleksin hám maqset funksiyası bahaların geometriyalıq súwretlewge tiykarlanǵan geometriyalıq sheshiw usılınan paydalanıw múmkin. Ásirese bul usıl eki ózgeriwshili sızıqlı programmalastırıw máselesin sheshiwdiń qolay hám ápiwayı usılı esaplanadı. Ózgeriwshiler sanı ekiden kóp bolǵan bir qatar máselelerdi de eki ózgeriwshili máselege keltiriw járdeminde geometriyalıq usıldı qollaw múmkin.
Eki ózgeriwshili sızıqlı programmalastırıw maslasini qaraymız :
Tegislikte Ox1x2 dekart koordinatalar sistemasın qaraymız. Ol waqıtta (2. 1)- (2. 2) máseleniń jobaları tegislikte (x1,x2) koordinatalı noqat sıyaqlı suwretleniwi múmkin. Qaralıp atırǵan máseleniń hár bir sheklewin qánaatlantıratuǵın (x1,x2) noqatlar kompleksi tegislikte shegarası tuwrı sızıqtan ibarat yarım tegislikti ańlatadı. Berilgen teńsizlikke qaysı yarım tegislik sáykes keliwin shegaralıq tuwrı sızıqta jatpaǵan qálegen noqattıń koordinatalarınıń teńsizlikke qoyıp tekseriw menen anıqlaw múmkin: eger teńsizlik qánaatlantirilsa, berilgen teńsizlikke sol noqat jaylasqan yarım tegislik sáykes keledi, keri jaǵdayda, sol noqat jatpaytuǵın ekinshi yarım tegislik sáykes keledi.
Berilgen shártlerinin geometriyalıq suwreti bolǵan barlıq yarım tegisliklerdiń kesilispesi retinde anıqlanıwshı jobalar kompleksi yamasa bos jıynaq, yamasa bos bolmaǵan qabarıq kópmuyishli jabıq jıynaqtan ibarat boladı. Bul kóp múyeshtegi jıynaq shegaralanǵan yamasa shegaralanbaǵan bolıwı múmkin.
Qaralıpatırǵan máseledegi z=c1x1+ c2x2 maqset funksiyası c1x1+ c2x2= tuwrı sızıqtıń barlıq noqatlarında áyne birdey mánis qabıl etedi, bul jerde - qandayda bir haqıyqıy san. Eger ni parametr retinde qabıl qilsak, c1x1+ c2x2= tuwrı sızıqlar shańaraǵına iye bolamız. Bul tuwrı sızıqlarǵa z=c1x1+ c2x2 maqset funksiyasınıń turaqlı mánisler sızıqları yamasa úst sızıqları dep ataladı.
Sızıqlı programmalastırıw máselesiniń qoyılıwına kóre bizni parametrdiń múmkin bolǵan eń úlken ma`nisine uyqas keliwshi maqset funksiyası úst sızıqlarına tiyisli bolǵan mumkin jobalar kompleksiniń noqatları qızıqtiradi. Matematikalıq analiz nátiyjelerine kóre c=(c1,c2) vektor baǵdarı z=c1x1+ c2x2 sızıqlı funksiyanıń ósiw baǵdarı, -c=(-c1,-c2) vektor baǵdarı bolsa z=c1x1+ c2x2 funksiyanıń kemiyiw baǵdarı boladı.
Sol sebepli, eger c1x1+ c2x2= úst sızıǵın onıń normalı bolǵan c=(c1,c2) vektor baǵdarında parallel kóshirilse, parametr hám z=c1x1+ c2x2 funksiyanıń ma`nisi asıp baradı ; eger c1x1+ c2x2= úst sızıǵın onıń normalına teris -c=(-c1,-c2) vektor baǵdarı boyınsha parallel kóshirilse, maqset funksiyası azayıp baradı. Usılarǵa tiykarlanǵan halda, sızıqlı programmalastırıw máselesiniń optimal jobaların anıqlaw ushın tómendegishe geometriyalıq usıldı usınıs etiw múmkin:
1) Daslep dekart koordinatalar tegisliginde máseleniń jobalar kompleksin quramız. Eger jobalar kompleksi bos bolsa, máseleni tarqatıp alıw tawsıladı : optimal joba joq ; keri jaǵdayda maksimum máselesi ushın 2-bandge ótip, minimum máselesi ushın bolsa 3-bandge ótip tarqatıp alıw procesin dawam ettiremiz.
2) Jobalar kompleksi menen kesilisetuǵın c1x1+ c2x2= qandayda bir úst sızıǵın quramız jáne onı normal c=(c1,c2) baǵdarında parallel kóshirip, optimal rejani izleymiz. Bunda, eger jobalar kompleksi menen eń aqırı kesisetuǵın(urınatuǵın) c1x1+ c2x2= úst sızıǵı tapılsa, jobalar kompleksiniń sol sızıqta jatıwshı shegaralıq x0=( x10,x20) noqatları maksimum máselesinde optimal jobalardı anıqlaydı hám maqset funksiyasınıń optimal zmax= c1x10+ c2x20= ma`nisi boladı. Eger úst sızıǵın onıń normalı baǵdarında hár qansha jıljıtganda da olar jobalar kompleksi menen kesesiwi ayan bolsa, maqset funksiyası joqarıdan shegaralanbaǵan hám sonday eken, másele sheshimge iye emes. Bunday jaǵday tek jobalar kompleksi shegaralanbaǵan haldaǵana payda bolıwı múmkin.
3) Jobalar kompleksi menen kesiwetuǵın c1x1+ c2x2= úst sızıǵın qurib jáne onı c=(c1,c2) normalǵa teris -c=(-c1,-c2) vektor baǵdarında parallel kóshirip, optimal rejani izleymiz. Bunda, eger jobalar kompleksi menen eń aqırı kesiwetuǵın(urınatuǵın) c1x1+ c2x2= úst sızıǵı tapılsa, jobalar kompleksiniń sol sızıqta jatıwshı shegaralıq noqatları minimum máselesinde optimal jobalardı anıqlaydı hám maqset funksiyasınıń optimal ma`nisi boladı. Eger úst sızıǵın onıń normalına keri baǵıtda hár qansha jıljıtganda da olar jobalar kompleksi menen kesesiwi ayan bolsa, maqset funksiyası tómenden shegaralanbaǵan hám sonday eken, másele sheshimge iye emes. Bunday jaǵday tek jobalar kompleksi shegaralanbaǵan haldaǵana júz beriwi múmkin.
Geometriyalıq usıldan sonday juwmaqqa keliw múmkin. Jobalar kompleksi shegaralanǵan qabarıq ko'pmuyishlik formasında bolǵanda, maqset funksiyasınıń minimum hám maksimumlari ámeldegi boladı hám optimal jobalar ko'pmuyishliktin qandayda bir ushında yamasa qandayda bir tárepinde tolıq jaylasadı. Sonday eken, geometriyalıq usılǵa kóre sızıqlı programmalastırıw máselesiniń sheshimi (eger ol ámeldegi bolsa ) qabarıq ko'pmuyishlikten ibarat jobalar kompleksiniń qandayda bir ushında anıqlanıwı zárúrli fakt dep esaplanıwı múmkin. Bul nátiyje qálegen ólshemli sızıqlı programmalastırıw máselelerin tarqatıp alıwda óz tastıyıǵın taǵı bir bar tabadı hám ulıwma tarqatıp alıw usılı - simpleks usılǵa ideologik tiykar bolıp xızmet etedi.
|
| |
