Piiramatu optimeerimise klassikalised meetodid

Sissejuhatus

Nagu teate, on piiramatu optimeerimise klassikaline probleem järgmine:

Nende probleemide lahendamiseks on olemas analüütilised ja numbrilised meetodid.

Kõigepealt tuletame meelde analüütilisi meetodeid piiramatu optimeerimisprobleemi lahendamiseks.

Piiramatutel optimeerimismeetoditel on ML -i kursusel märkimisväärne koht. See on tingitud nende otsesest rakendamisest mitmete optimeerimisülesannete lahendamisel, samuti tingimusliku optimeerimise ülesannete (MT -probleemide) olulise osa lahendamise meetodite rakendamisel.

1. Vajalikud tingimused kohaliku miinimumpunkti jaoks (maksimum)

Olgu m funktsiooni minimaalsed väärtused. On teada, et sel hetkel on funktsiooni juurdekasv mittenegatiivne, s.t.

Leiame, kasutades funktsiooni laiendamist Taylori seeria m läheduses.

kus on selle seeria liikmete summa, kelle järjekord on võrdne juurdekasvuga (kaks) ja suurem.

Sellest (4) tuleneb selgelt, et

Oletame siis, et

Võttes arvesse (6), on meil :. (7)

Oletame, et see on positiivne, s.t. ... Valime siis toote, mis on vastuolus (1).

Seetõttu on see tõesti ilmne.

Vaideldes teiste muutujate suhtes sarnaselt, saame mitme muutuja funktsiooni lokaalse miinimumi punktide jaoks vajaliku tingimuse

Lihtne on tõestada, et kohaliku maksimumpunkti jaoks vajalikud tingimused on täpselt samad, mis kohaliku miinimumpunkti puhul, s.t. tingimused (8).

On selge, et tõestuse tulemuseks on vormi ebavõrdsus: - tingimus funktsiooni mittepositiivseks suurendamiseks kohaliku maksimumi naabruses.

Saadud vajalikud tingimused ei vasta küsimusele: kas statsionaarne punkt on miinimum- või maksimumpunkt.

Sellele küsimusele saab vastuse piisavate tingimuste uurimisel. Need tingimused eeldavad objektiivse funktsiooni teise tuletise maatriksi uurimist.

2. Piisavad tingimused kohaliku miinimumpunkti jaoks (maksimum)

Esitame funktsiooni laienemist Taylori seeria punkti naabruses kuni ruudukujuliseks.

Laiendust (1) saab esitada lakoonilisemalt, kasutades mõistet: "vektorite punktprodukt" ja "vektormaatriksprodukt".

Eesmärgifunktsiooni kahe tuletise maatriks vastavate muutujate suhtes.

Funktsiooni juurdekasvu (1 ") põhjal saab kirjutada järgmiselt:

Arvestades vajalikke tingimusi:

Asendaja (3) kujul:

Ruutkuju nimetatakse diferentsiaalruutvormiks (DKF).

Kui DKF on positiivne kindel, on statsionaarne punkt ka kohalik miinimumpunkt.

Kui DKF ja seda esindav maatriks on negatiivselt määratletud, siis on statsionaarne punkt ka kohalik maksimumpunkt.

Seega on kohaliku miinimumpunkti jaoks vajalikud ja piisavad tingimused vormis

(samad vajalikud tingimused saab kirjutada järgmiselt:

Piisav tingimus.

Seega on kohaliku maksimumi jaoks vajalik ja piisav tingimus järgmine:

Meenutagem kriteeriumi, mille järgi määratakse, kas ruutkuju ja seda kujutav maatriks on positiivne kindel või negatiivne.

3. Sylvesteri kriteerium

Võimaldab vastata küsimusele: kas ruutvorm ja seda kujutav maatriks on positiivne kindel või negatiivne.

Seda nimetatakse Hesse maatriksiks.

Hesse maatriksi peamine määraja

ja selle kujutatav DKF on positiivne kindel, kui kõik Hessi maatriksi () peamised määrajad on positiivsed (st toimub järgmine märgiskeem:

Kui näiteks Hessi maatriksi peamiste determinantide jaoks on erinev märgiskeem, siis on maatriks ja DKF negatiivselt määratletud.

4. Euleri meetod on klassikaline meetod piiramatu optimeerimise probleemide lahendamiseks

See meetod põhineb vajalikel ja piisavatel tingimustel, mida on uuritud punktides 1.1–1.3; rakendame ainult pidevate diferentseeruvate funktsioonide kohaliku äärmuse leidmist.

Selle meetodi algoritm on üsna lihtne:

1) kasutades vajalikke tingimusi, moodustame süsteemi üldjuhul mitte lineaarvõrrandid... Pange tähele, et seda süsteemi ei ole üldjuhul võimalik analüütiliselt lahendada; mittelineaarsete võrrandite (NE) süsteemide lahendamiseks on vaja rakendada numbrilisi meetodeid (vt "FM"). Sel põhjusel on Euleri meetod analüütiline-numbriline meetod. Lahendades määratud võrrandisüsteemi, leiame statsionaarse punkti koordinaadid.;

2) uurime DKF -i ja seda esindavat Hessi maatriksit. Kasutades Sylvesteri kriteeriumi, teeme kindlaks, kas statsionaarne punkt on miinimum- või maksimumpunkt;

3) arvutab sihtfunktsiooni väärtuse äärmises punktis

Lahendage Euleri meetodi abil järgmine piiramatu optimeerimisülesanne: leidke vormi funktsiooni 4 statsionaarset punkti:

Uurige nende punktide olemust, olgu need siis miinimum- või sadulapunktid (vt.). Ehitage selle funktsiooni graafiline kuvamine ruumis ja tasapinnal (kasutades nivoojooni).

5. Tingimusliku optimeerimise klassikaline probleem ja selle lahendamise meetodid: kõrvaldamise meetod ja Lagrange'i kordajate meetod (MLM)

Nagu teate, on tingimusliku optimeerimise klassikaline probleem järgmine:

Graafik, mis selgitab probleemi (1), (2) avaldust ruumis.

Tasejoone võrrandid

Niisiis, vaadeldava probleemi ODR on teatud kõver, mida kujutab võrrand (2 ").

Nagu jooniselt näha, on mõte tingimusteta globaalse maksimumi punkt; punkt - tingliku (suhtelise) kohaliku miinimumi punkt; punkt - tingliku (suhtelise) kohaliku maksimumi punkt.

Ülesande (1 "), (2") saab lahendada kõrvaldamise (asendamise) meetodiga, lahendades muutuja suhtes võrrandi (2 ") ja asendades leitud lahendi (1").

Algne probleem (1 "), (2") muudetakse seega funktsiooni piiramatu optimeerimise probleemiks, mida saab hõlpsasti lahendada Euleri meetodiga.

Välistamise (asendamise) meetod.

Olgu eesmärgifunktsioon sõltuv muutujatest:

nimetatakse sõltuvateks muutujateks (või olekumuutujateks); vastavalt saame vektori sisse tuua

Ülejäänud muutujaid nimetatakse sõltumatuteks otsustusmuutujateks.

Sellest tulenevalt võime rääkida veeruvektorist:

ja vektorid.

Klassikalise tingimusliku optimeerimise probleemi puhul:

Süsteem (2) tuleb vastavalt välistamise (asendamise) meetodile lahendada sõltuvate muutujate (olekumuutujate) suhtes, s.t. sõltuvate muutujate jaoks tuleks saada järgmised avaldised:

Kas võrrandisüsteem (2) on alati sõltuvate muutujate suhtes lahendatav - mitte alati, see on võimalik ainult juhul, kui determinant, mida nimetatakse jakoobiks, mille elementide vorm on järgmine:

ei ole võrdne nulliga (vt vastavat teoreemi MA kursusel)

Nagu näete, peavad funktsioonid olema pidevad diferentseeruvad funktsioonid ja teiseks tuleb determinandi elemendid arvutada objektiivfunktsiooni statsionaarses punktis.

Asendades (3) eesmärgi funktsiooniks (1), on meil:

Ekstreemi uuritud funktsiooni saab toota Euleri meetodil - pidevalt diferentseeruva funktsiooni piiramatu optimeerimise meetodil.

Niisiis, kõrvaldamise (asendamise) meetod võimaldab kasutada klassikalise tingimusliku optimeerimise probleemi, et muutuda funktsiooni piiramatu optimeerimise probleemiks - muutujate funktsioon tingimusel (4), mis võimaldab saada avaldiste süsteemi (3) ).

Elimineerimismeetodi puuduseks on raskused ja mõnikord võimatu väljendussüsteemi hankida (3). MLM on sellest puudusest vaba, kuid eeldab tingimuse (4) täitmist.

5.2. Lagrange'i kordaja meetod. Vajalikud tingimused tingimusliku optimeerimise klassikalises probleemis. Lagrange'i funktsioon

MLM võimaldab klassikalise tingimusliku optimeerimise algprobleemi:

Muutke spetsiaalselt kavandatud funktsioon - Lagrange'i funktsioon piiramatu optimeerimise probleemiks:

kus, - Lagrange'i kordajad;

Nagu näete, on see summa, mis koosneb esialgsest eesmärgifunktsioonist ja funktsioonide "kaalutud" summast - funktsioonidest, mis esindavad nende esialgse probleemi piiranguid (2).

Olgu punkt funktsiooni tingimusteta ekstreemsuse punkt, siis, nagu teada, või (funktsiooni täielik diferentsiaal punktis).

Sõltuvate ja sõltumatute muutujate mõiste kasutamine - sõltuvad muutujad; on sõltumatud muutujad, siis esitame (5) laiendatud kujul:

Alates (2) on ilmne, et vormis võrrandisüsteem järgneb:

Iga funktsiooni kõigi erinevuste arvutamise tulemus

Esitame (6) laiendatud kujul, kasutades sõltuvate ja sõltumatute muutujate kontseptsiooni:

Pange tähele, et (6 ") on erinevalt (5") süsteem, mis koosneb võrranditest.

Korrutame süsteemi iga 6 -nda võrrandi (6 ") vastava -nda Lagrange'i kordajaga. Liitke need kokku ja võrrandiga (5") ning saate avaldise:

Korraldame Lagrange'i kordajad nii, et avaldis nurksulgudes esimese summa märgi all (teisisõnu koefitsiendid sõltumatute muutujate diferentsiaalide juures) on võrdne nulliga.

Mõiste "käsutada" Lagrange'i kordajaid ülaltoodud viisil tähendab, et on vaja lahendada teatud võrrandisüsteem seoses.

Sellise võrrandisüsteemi struktuuri on lihtne saada, kui võrdsustada avaldis nurksulgudes esimese summa märgi all nulliga:

Kirjutame (8) ümber nii

Süsteem (8 ") on lineaarsete võrrandite süsteem, võrreldes teadaolevatega: )

Kuna võtmeavaldises (7) on esimene summa võrdne nulliga, on lihtne mõista, et ka teine ​​summa võrdub nulliga, s.t. kehtib järgmine võrrandisüsteem:

Võrrandisüsteem (8) koosneb võrranditest ja võrrandisüsteem (10) koosneb võrranditest; kõikidest võrranditest kahes süsteemis ja tundmatutest

Puuduvad võrrandid antakse piirangute võrrandisüsteemi (2) abil:

Niisiis, tundmatute leidmiseks on olemas võrrandisüsteem:

Saadud tulemus on see, et võrrandisüsteem (11) moodustab MLM -i põhisisu.

On lihtne mõista, et võrrandisüsteemi (11) saab väga lihtsalt, kui võtta arvesse spetsiaalselt loodud Lagrange'i funktsiooni (3).

Tõesti

Niisiis, võrrandisüsteemi (11) saab esitada kujul (kasutades (12), (13)):

Võrrandisüsteem (14) kujutab endast tingimust tingimusliku optimeerimise klassikalises ülesandes.

Selle süsteemi saadud lahendit, vektori väärtust nimetatakse tinglikult statsionaarseks punktiks.

Tinglikult seisva punkti olemuse väljaselgitamiseks on vaja kasutada piisavaid tingimusi.

5.3 Piisavad tingimused klassikalises tingimusliku optimeerimise probleemis. MML algoritm

Need tingimused võimaldavad välja selgitada, kas tinglikult statsionaarne punkt on kohaliku tingimusliku miinimumi punkt või kohaliku tingimusliku maksimumi punkt.

Suhteliselt lihtne, nii nagu probleemis saadi piisavad tingimused tingimusteta ekstreemumi jaoks. Piisavaid tingimusi on võimalik saada ka klassikalises tingimusliku optimeerimise ülesandes.

Selle uuringu tulemus:

kus on kohaliku tingimusliku miinimumi punkt.

kus on kohaliku tingimusliku maksimumi punkt, kas elementidega Hessi maatriks

Hesse maatriksil on mõõtmed.

Hessi maatriksi mõõtmeid saab vähendada, kasutades ebavõrdsuse tingimust jakooblaste nullile :. Selle tingimuse korral saab sõltuvaid muutujaid väljendada sõltumatute muutujate kujul, siis saab Hessi maatriks mõõtme, s.t. on vaja rääkida elementidega maatriksist

siis on piisavad tingimused järgmised:

Kohaliku tingimusliku miinimumi punkt.

Kohaliku tingimusliku maksimumi punkt.

Tõestus: MML algoritm:

1) koostada Lagrange'i funktsioon :;

2) kasutades vajalikke tingimusi, moodustame võrrandisüsteemi:

3) leida selle süsteemi lahendusest punkt;

4) kasutades piisavaid tingimusi, teeme kindlaks, kas punkt on kohaliku tingimusliku miinimumi või maksimumi punkt, seejärel leiame

1.5.4. Grapo-analüütiline meetod klassikalise tingimusliku optimeerimise probleemi lahendamiseks ruumis ja selle muudatused IP ja AP lihtsaimate probleemide lahendamisel

See meetod kasutab klassikalise piiratud optimeerimisülesande geomeetrilist tõlgendust ja põhineb sellel probleemil omastel olulistel faktidel.

B on funktsiooni ja ODR -i esindava funktsiooni ühine puutuja.

Nagu jooniselt näha, on punkt tingimusteta miinimumi punkt, punkt tingliku kohaliku miinimumi punkt, punkt tingliku kohaliku maksimumi punkt.

Tõestame, et tingliku kohaliku äärmuse punktides kõver ja vastavad tasandijooned

MA kursuselt on teada, et puutumatuse hetkel on seisund

kus on vastava tasandi joonega tõmmatud puutuja kalle; on funktsiooni puutuja kalle

Nende koefitsientide avaldis (MA) on teada:

Tõestame, et need koefitsiendid on võrdsed.

sest vajalikud tingimused "räägivad" sellest

Ülaltoodu võimaldab meil sõnastada HFA algoritmi klassikalise piiratud optimeerimisprobleemi lahendamise meetodi jaoks:

1) koostame objektiivse funktsioonitaseme ridade perekonna:

2) konstrueerime piiranguvõrrandi abil ODR -i

3) funktsiooni suurenemise korrigeerimiseks leiame ja selgitame äärmuslike punktide olemust;

4) uurime nivoojoonte ja funktsiooni koosmõju, samas leides võrrandisüsteemist tinglikult statsionaarsete punktide koordinaadid - kohalikud tingimuslikud miinimumid ja kohalikud tingimuslikud maksimumid.

5) arvuta

Eriti tuleb märkida, et klassikalise piiratud optimeerimisülesande lahendamise HFA meetodi põhietapid langevad kokku NP ja LP probleemide lahendamise HFA meetodi põhietappidega, ainus erinevus on ODR -is, samuti äärmuslike punktide asukoht ODR -is (näiteks LP -ülesannetes leiduvad need punktid tingimata ODR -i tähistava kumera hulknurga tippudes).

5.5. MML praktilisest tähendusest

Esitame tingimusliku optimeerimise klassikalise probleemi kujul:

kus on muutuvad kogused, mis esindavad tehnilisi ja majanduslikke probleeme käsitlevaid muutuvaid ressursse.

Ruumis on probleem (1), (2) järgmisel kujul:

kus on muutuja. (2 ")

Olgu tingimusliku ekstreemumi punkt:

Kui muudetakse, muutub

Eesmärkfunktsiooni väärtus muutub vastavalt:

Arvutame tuletise:

Alates (3), (4), (5). (6)

Asendage (5 ") punktis 3 ja saate:

Alates (6), et Lagrange'i kordaja iseloomustab "reaktsiooni" väärtust (risti objektiivse funktsiooni väärtusega) kuni parameetri muutumiseni.

Üldiselt (6) on järgmine:

Alates (6), (7), et tegur iseloomustab muutust, kui vastav ressurss muutub 1 võrra.

Kui see on maksimaalne kasum või minimaalsed kulud, siis iseloomustab selle väärtuse muutumist muutmisel 1.

5.6. Tingimusliku optimeerimise klassikaline probleem kui Lagrange'i funktsiooni sadulapunkti leidmise probleem:

Paari nimetatakse sadulapunktiks, kui ebavõrdsus kehtib.

Ilmselgelt alates (1). (2)

Alates (2) sellest. (3)

Nagu näete, sisaldab süsteem (3) võrrandeid, mis on sarnased võrranditega, mis esindavad tingimusliku optimeerimise klassikalises ülesandes vajalikku tingimust:

kus on Lagrange'i funktsioon.

Seoses võrrandisüsteemide (3) ja (4) analoogiaga võib klassikalise piiranguga optimeerimisülesannet pidada Lagrange'i funktsiooni sadulapunkti leidmise probleemiks.

Sarnased dokumendid

Mitmemõõtmelise optimeerimise probleemid tekstiilitööstuse tehnoloogiliste protsesside uurimisel, esilekerkivate raskuste analüüs. Ekstreemumi, näiteks ekstreemumi leidmine, piiramatu mitmemõõtmelise optimeerimise objektiivse funktsiooni väärtus.

test, lisatud 26.11.2011


Piiramatu optimeerimise klassikaliste meetodite omadused. Ühe ja mitme muutuja funktsioonide ekstreemsuse olemasolu vajaliku ja piisava tingimuse kindlaksmääramine. Lagrange'i kordaja reegel. Vajalikud ja piisavad tingimused optimaalsuseks.

kursusetöö lisatud 13.10.2013


Optimeerimisülesannete lahendamise meetodid ja omadused, eelkõige investeeringute jaotamise ja transpordivõrgu tee valiku osas. Hammingi ja Browni meetodite abil modelleerimise eripära. Identifitseerimine, stimuleerimine ja motiveerimine kui juhtimisfunktsioonid.

test, lisatud 12.12.2009


Väide, analüüs, lineaarse optimeerimise ülesannete graafiline lahendus, simpleksmeetod, duaalsus lineaarses optimeerimises. Transpordiprobleemi sõnastamine, omadused ja võrdluslahenduse leidmine. Tingimuslik optimeerimine võrdsuspiirangute all.

kasutusjuhend, lisatud 07.11.2010


Kriitiline tee graafikus. Optimaalne voolu jaotus transpordivõrgus. Lineaarse programmeerimise probleem lahendati graafiliselt. Tasakaalustamata transpordi väljakutse. Numbrilised meetodid staatilise optimeerimise ühemõõtmeliste probleemide lahendamiseks.

kursusetöö, lisatud 21.06.2014


Graafiline meetod tootmisprotsesside optimeerimise probleemi lahendamiseks. Simplex -algoritmi rakendamine majanduslikult optimeeritud tootmiskontrolli probleemi lahendamiseks. Dünaamiline programmeerimismeetod optimaalse rajaprofiili valimiseks.

test, lisatud 15.10.2010


Optimeerimismeetodid majanduslike probleemide lahendamiseks. Optimeerimisülesande klassikaline sõnastus. Funktsioonide optimeerimine. Funktsionaalide optimeerimine. Mitmekriteeriumiline optimeerimine. Meetodid mitme kriteeriumi probleemi vähendamiseks ühe kriteeriumi probleemiks. Soodustuste meetod.

abstraktne, lisatud 20.06.2005


Mittelineaarsete programmeerimismeetodite rakendamine muutujate mittelineaarsete funktsioonidega seotud probleemide lahendamiseks. Optimaalsustingimused (Kuhn-Tuckeri teoreem). Tingimuslikud optimeerimismeetodid (Wolfe'i meetod); gradiendi kujundus; karistus- ja tõkkefunktsioonid.

abstraktne, lisatud 25.10.2009


Mitmekriteeriumilise optimeerimise olemasolevate probleemide mõiste, määratlus, funktsioonide, võimete ja omaduste esiletõstmine ning nende lahendamise viisid. Mitmekriteeriumilise optimeerimise võrdse ja väikseima kõrvalekalde meetodi arvutamine ja selle rakendamine praktikas.

kursusetöö lisatud 21.01.2012


Modelleerimise põhimõisted. Üldised mõisted ja mudeli määratlus. Optimeerimisprobleemide avaldus. Lineaarsed programmeerimismeetodid. Üldine ja tüüpiline ülesanne lineaarses programmeerimises. Simplex meetod lineaarse programmeerimise probleemide lahendamiseks.

Optimeerimine on teatud funktsiooni ekstreemsuse (globaalne maksimum või miinimum) leidmine või võimalike funktsioonide hulgast parima (optimaalse) valimine. Kõige usaldusväärsem viis parima variandi leidmiseks on võrrelda kõiki võimalikke valikuid (alternatiive). Kui alternatiivide arv on suur, kasutatakse tavaliselt parima leidmiseks matemaatilisi programmeerimismeetodeid. Neid meetodeid saab rakendada, kui probleem on rangelt sõnastatud: on seatud muutujate kogum, nende võimalike muutuste ulatus (seatud piirangud) ja eesmärgifunktsiooni tüüp (funktsioon, mille ekstreemsus vajab nende muutujate hulgast. Viimane on kvantitatiivne meede (kriteerium) seatud eesmärgi saavutamise astme hindamiseks.

Piiramatu optimeerimise probleem on leida funktsiooni miinimum või maksimum piirangute puudumisel. Hoolimata asjaolust, et enamik praktilisi optimeerimisprobleeme sisaldab piiranguid, on piiranguteta optimeerimismeetodite uurimine oluline mitmest vaatenurgast. Paljud algoritmid piiratud probleemi lahendamiseks hõlmavad selle vähendamist piiranguteta optimeerimisülesannete jadaks. Teine meetodite klass põhineb sobiva suuna leidmisel ja seejärel selle suuna minimeerimisel. Piiramatu optimeerimise meetodite põhjendamist saab loomulikult laiendada, et õigustada piirangutega probleemide lahendamise menetlusi.

Tingimusliku optimeerimise probleemiks on skalaarfunktsiooni f (x) n-mõõtmeliste vektorargumentide minimaalse või maksimaalse väärtuse leidmine. Lahendus probleemile põhineb objektiivfunktsiooni lineaarsel või ruutmeetrilisel lähendamisel, et määrata igal iteratsioonil juurdekasv x1,…, xn. Mittelineaarsete ülesannete lahendamiseks on olemas ka ligikaudsed meetodid. Need on meetodid, mis põhinevad tükkide kaupa lineaarse lähendamise meetodil. Lahenduste leidmise täpsus sõltub intervallide arvust, mille põhjal leiame lahenduse mittelineaarsele probleemile võimalikult lähedasele lineaarsele probleemile. See meetod võimaldab arvutusi simpleksmeetodi abil. Tavaliselt on lineaarsetes mudelites sihtfunktsiooni koefitsiendid konstantsed ega sõltu muutujate väärtusest. Siiski on mitmeid probleeme, mille puhul kulud sõltuvad mahust mittelineaarsel viisil.

Lahenduse algoritm:

• 1. Töö algab korrapärase simpleksi konstrueerimisega sõltumatute muutujate ruumis ja sihtfunktsiooni väärtuste hindamisega iga üksiku tipu juures.
• 2. Määratakse tipp - funktsiooni suurim väärtus.
• 3. Tipp projitseeritakse läbi ülejäänud tippude raskuskeskme uude punkti, mida kasutatakse uue simpleksi tipuna.
• 4. Kui funktsioon väheneb piisavalt sujuvalt, jätkuvad iteratsioonid seni, kuni minipunkt on kaetud või algab tsükliline liikumine mööda kahte või enamat simpleksit.
• 5. Otsing lõpeb, kui kas simpleksi mõõtmed või funktsiooni väärtuste erinevused tippudes jäävad piisavalt väikeseks.

Väljakutse: paagi optimeerimine. Saavutada minimaalsed kulud liiva säilitamiseks mõeldud 2750 -liitrise mahuti valmistamiseks.

Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min;

kus: X1 on nõutava metalli kogus, kg;

C1 - metalli maksumus, RUB / kg;

X2 on vajalike elektroodide mass, kg;

C2 on elektroodide maksumus, RUB / kg;

X3 on tarbitud elektrienergia kogus, kWh;

C3 on elektri hind, RUB / kWh;

X4 on keevitaja tööaeg, h;

C4 - keevitaja tariifimäär, hõõruda / h;

X5 - tõste tööaeg, h;

C5 - lifti eest tasumine, hõõruda / h.

1. Leidke konteineri optimaalne pindala:

F = 2ab + 2bh + 2ah min (1)

kus V = 2750 liitrit.

x1 = 16,331; x2 = 10,99

Funktsiooni miinimum saadi kasti meetodil optimeerimise käigus - 1196,065 dm2

Vastavalt GOST 19903-74 võtame vastu:

h = 16,50 dm, b = 10,00 dm.

Väljendame a (1) ja saame:

Arvutame metalllehe optimaalse paksuse

Valime süsinikust tavalise terase St2sp

Selle terase jaoks 320 MPa ,;

Liiva mass.

Koormus suurima ala paagi seinale:

Arvutame koormuse 100 cm laiuse lehe 1 lineaarsentimeetrile:

Seina paksuse määramine sõltuvalt olukorrast:

kus: l on lehe pikkus (eelistatavalt suurim, et jätta täiendav ohutusvaru);

q on koormus lineaarse sentimeetri kohta, kg / cm;

Metallpleki paksus, m

Suurim lubatud metallpinge, N / mm2.

Väljendame seina paksust (2):

Arvestades, et 320 MPa = 3263 kg / cm2,

Metallist kaal

kus: F on mahuti pindala, m2;

Metallist seina paksus, m;

Metalli tihedus, kg / m3.

Terase St2sp hind on umbes 38 rubla / kg.

2. Keevisõmbluse pikkus:

Kasutame roostevabast terasest elektroode "UONI-13/45"

Hind 88,66 rubla / kg;

kus: Sseam - keevisõmbluse ristlõikepindala, m2;

l on keevisõmbluse pikkus, m;

Ladestunud metalli tihedus, kg / m3.

3. Keevitusaeg:

kus l on keevisõmbluse pikkus, m;

v - keevituskiirus, m / h.

Kogu energiatarve:

Rsum = 5 17 = 85 kWh;

Elektrienergia maksumus on 5,7 rubla / kWh.

4. Käsitsi kaarkeevitamise korral on abi-, ettevalmistus- ja lõpuaeg ning ajakulu töökoha hooldamiseks keskmiselt 40 - 60%. Kasutame keskmiselt 50%.

Aeg kokku:

Maksmine VI kategooria keevitaja eest - 270 rubla tunnis.

Pluss tariifitegur 17% suletud, halvasti ventileeritavas ruumis töötamise eest:

Assistendi tasu on 60% keevitaja tasust:

8055 0,6 = 4833 rubla.

Kokku: 8055 + 4833 = 12888 rubla.

5. Metalllehtede hoidmiseks keevitamisel, laadimisel ja mahalaadimisel ning otse valmis mahutil on vaja kraanat.

Kogu konstruktsiooni "haaramiseks" peab keevitaja rakendama umbes 30% õmblustest.

Kraana eest tasumine - 1000 rubla tunnis.

Võimsuse kogumaksumus.

Eesmärk 1. Leia

Ülesanne 1 taandub võrrandisüsteemi lahendamisele:

ja teise erinevuse väärtuse uurimine:

võrrandite (8.3) lahenduspunktides.

Kui ruutkuju (8.4) on mingis punktis negatiivselt määratletud, saavutab see oma maksimaalse väärtuse ja kui see on positiivselt määratletud, siis miinimumväärtuse.

Näide:

Võrrandisüsteemil on lahendused:

Punkt (- 1 / 3.0) on maksimaalne punkt ja punkt (1 / 3.2) on miinimumpunkt.

Eesmärk 2. Leia

tingimustel:

Ülesanne 2 lahendatakse Lagrange'i kordaja meetodil. Selleks leitakse süsteemne lahendus (m + n) võrrandid:

Näide. Leidke ringi täisjoonega ristküliku küljed :. Ristküliku ala A võib kirjutada järgmiselt: A = 4hu, siis

Eesmärk 3. Leia:

tingimustel:

See ülesanne hõlmab mitmesuguseid funktsioonidega määratletud ülesandeid f ja  .

Kui need on lineaarsed, on probleem lineaarse programmeerimise probleem.

Ülesanne3 a.

tingimustel

Selle lahendab simpleksmeetod, mis lineaarse algebra aparaadi abil teostab (8.13) määratletud hulktahu tippude sihipärase loendamise.

Simplex meetod (koosneb kahest etapist):

Etapp 1. Tugilahenduse leidmine x (0).

Toetuslahendus on üks polütoobi (8.13) punkte.

Etapp 2. Optimaalse lahenduse leidmine.

Optimaalne lahendus leitakse politopi (8.13) tippude järjestikuse loendamise teel, mille puhul sihtfunktsiooni z väärtus ei vähene igal sammul, see tähendab:

Lineaarse programmeerimise probleemi erijuhtumiks on nn transpordiprobleem.

Transpordi probleem. Olgu punktides laod, milles hoitakse kaupu vastavalt koguses. Punktides on tarbijad, kes peavad neid kaupu vastavalt tarnima. Me tähistame c ij veoseühiku transportimise kulud punktide vahel

Uurime, kuidas tarbijad veavad kaupu tarbijate vajaduste rahuldamiseks piisavas koguses. Tähistagem punktist veetava kauba hulgaga a i osutada b j .

Tarbija vajaduste rahuldamiseks on vaja, et väärtused NS ij vastama tingimustele:

Samal ajal laost; te ei saa tooteid välja võtta suuremas koguses kui praegu. See tähendab, et soovitud väärtused peavad vastama ebavõrdsuste süsteemile:

Tingimuste (8.14), (8.15) täitmiseks, st tarbijate vajadustele vastava transpordiplaani koostamiseks on lugematuid viise. Selleks, et operatsioonide uurija saaks valida konkreetse lahenduse, st määrata teatud NS ij, tuleks sõnastada teatud valikureegel, mis määratakse kindlaks kriteeriumi abil, mis peegeldab meie subjektiivset ettekujutust eesmärgist.

Kriteeriumi probleem lahendatakse sõltumata toimingu uurimisest - kriteeriumi peab täpsustama operatiivpool. Selle probleemi puhul on üheks võimalikuks kriteeriumiks transpordikulud. See on määratletud järgmiselt.

Seejärel sõnastatakse transpordiprobleem lineaarse programmeerimise ülesandena: määrake piirangutele (8.14), (8.15) vastavad kogused ja andke funktsioonile (8.16) miinimumväärtus. Piirang (8.15) on tasakaalu tingimus; tingimust (8.14) võib nimetada toimingu eesmärgiks, sest toimingu mõte on tagada tarbijate vajadused.

Need kaks tingimust moodustavad sisuliselt toimingu mudeli. Operatsiooni elluviimine sõltub kriteeriumist, mille alusel operatsiooni eesmärk saavutatakse. Kriteerium võib esineda erinevates rollides. See võib toimida nii eesmärgi vormistamise viisina kui ka põhimõttena tegevuste valimisel lubatud hulgast, st piirangute rahuldamiseks.

Üks tuntud transpordiprobleemi lahendamise meetodeid on potentsiaalne meetod.

Probleemi lahendamise esimeses etapis koostatakse esialgne transpordiplaan, mis rahuldab

piirangud (8.14), (8.15). Kui (see tähendab, et kogunõuded ei lange kokku ladudes olevate toodete koguvarudega), siis võetakse kasutusele fiktiivne tarbimispunkt või fiktiivne ladu, mille transpordikulud on võrdsed nulliga. Uue ülesande puhul langeb ladudes olevate kaupade koguarv kokku nende kogunõudlusega. Siis on mõni meetod (näiteks väikseim element või loodenurk) esialgne plaan. Saadud plaani menetluse järgmises etapis ehitatakse üles eriomaduste - potentsiaalide süsteem. Optimaalse plaani vajalik ja piisav tingimus on selle potentsiaal. Plaani täpsustamise protseduur viiakse läbi seni, kuni see muutub potentsiaalseks (optimaalseks).

Probleem 3b.Üldiselt nimetatakse probleemi (8.10 - 8.11) mittelineaarseks programmeerimisprobleemiks. Vaatleme seda rohkem aktsepteeritud kujul:

tingimustel

Selle probleemi lahendamiseks kasutatakse nn lõõgastusmeetodeid. Punktide jada koostamise protsessi nimetatakse lõdvestuseks, kui:

Laskumismeetodid (üldine skeem)... Kõik laskumismeetodid piiramatu optimeerimisülesande (8.17) lahendamiseks erinevad kas laskumissuuna valiku või liikumisviisi järgi laskumissuunas. Laskumismeetodid koosnevad järgmisest järjestuse loomise protseduurist { x k }.

Esialgseks lähendamiseks valitakse suvaline punkt x 0 . Järjestikused lähendid koostatakse vastavalt järgmisele skeemile:

Punkt x k laskumissuund on valitud - s k ;

Leidke (k + 1) - lähendus valemiga:

kus väärtuseks valitakse ükskõik milline arv, mis rahuldab ebavõrdsuse

kus number on selline number millal

Enamiku laskumismeetodite puhul valitakse  k väärtus võrdseks ühega. Seega tuleb k määramiseks lahendada ühemõõtmeline minimeerimisülesanne.

Gradiendi laskumise meetod. Kuna antigradient - näitab funktsiooni järsema languse suunda f(x), siis on loomulik liikuda punktist NS k selles suunas. Laskumismeetod, mida nimetatakse gradiendi laskumise meetodiks. Kui, siis nimetatakse lõdvestusprotsessi kõige järsemaks laskumismeetodiks.

Konjugeeritud suundade meetod. Lineaarses algebras on see meetod tuntud kui konjugeeritud gradiendi meetod lineaarsete algebraliste võrrandisüsteemide lahendamiseks AX =b, ja seetõttu ruutfunktsiooni minimeerimise meetodina

Meetodi skeem:

Kui = 0, muutub see skeem järsemaks laskumisskeemiks. Väärtuse sobiv valik t k garanteerib konjugeeritud suuna meetodi lähenemise sama suurusjärguga kui gradiendi laskumismeetoditel ja tagab, et ruutmeetri laskumisel on iteratsioonide arv piiratud (näiteks).

Koordinaatide põlvnemine. Igal kordamisel, kui laskumissuund - s k valitakse suund mööda ühte koordinaattelge. Meetodi minimeerimisprotsessi lähenemise määr on suurusjärgus 0 (1 / m). Pealegi sõltub see sisuliselt ruumi mõõtmetest.

Meetodi skeem:

kus koordinaatide vektor

Kui hetkel x k on teavet funktsiooni gradiendi käitumise kohta f(x), näiteks:

siis laskumissuunaks s k võime võtta koordinaatide vektori e j . Sellisel juhul on meetodi lähenemise kiirus n korda väiksem kui gradiendi laskumisel.

Minimeerimisprotsessi algstaadiumis saate kasutada tsüklilise koordineeritud laskumise meetodit, kui esmalt toimub laskumine suunas e 1 , siis e 2 jne kuni e NS , pärast seda korratakse kogu tsüklit uuesti. Paljutõotavam võrreldes eelmisega on koordinaadist laskumine, kus laskumissuunad valitakse juhuslikult. Selle lähenemisviisiga suuna valimisel on a priori hinnangud, mis tagavad funktsiooni f(x) koos tõenäosus, mis kaldub ühtsusele, protsessi lähenemine kiirusega suurusjärgus 0 (1 / m).

Meetodi skeem:

Protsessi igal etapil, n arvust (1, 2, ..., n), arv j(k) ja nagu s k, ühiku koordinaatide vektor e j ( k ) , pärast mida toimub laskumine:

Juhusliku laskumise meetod.s k jaotatakse selles valdkonnas ühtlaselt ja seejärel vastavalt protsessi k -ndal etapil arvutatud elemendile NS To määrab:

Juhusliku laskumise meetodi lähenemiskiirus on n korda madalam kui gradiendi laskumise meetodil, kuid n korda suurem kui juhusliku koordinaadi laskumise meetodil. Kaalutud laskumismeetodid on rakendatavad ka mitte tingimata kumerate funktsioonide puhul ja tagavad nende lähenemise väga väikeste piirangute korral (näiteks kohalike miinimumide puudumine).

Matemaatilise programmeerimise lõdvestusmeetodid. Tuleme tagasi probleemi 36 juurde ((8.17) - (8.18)):

tingimustel

Piirangutega seotud optimeerimisprobleemide korral on laskumissuuna valik seotud vajadusega pidevalt kontrollida, kas uus väärtus NS k +1 peaks nagu ka eelmine x k piirangute süsteemi rahuldama X.

Tingimuslik gradiendi meetod. Selle meetodi puhul on laskumissuuna valimise idee järgmine: punktis NS To funktsiooni lineariseerida f(x), lineaarse funktsiooni konstrueerimine ja seejärel minimeerimine f(x) võtteplatsil NS, leida punkt y k . Pärast seda eeldatakse ja edasi selles suunas, laskumine viiakse läbi, nii et

Seega tuleks suuna - s k leidmiseks lahendada hulga lineaarfunktsiooni minimeerimise probleem X. Kui X omakorda annavad lineaarsed piirangud, siis saab sellest lineaarse programmeerimise probleem.

Võimalike juhiste meetod. Meetodi idee: kõigi võimalike suundade hulgas NS To valige see, mida mööda funktsioon töötab f(x) väheneb kõige kiiremini ja laskub seejärel mööda seda suunda.

Suund - s punktis NS X nimetatakse võimalikuks, kui on olemas selline arv, mis sobib kõigile. Võimaliku suuna leidmiseks on vaja lahendada lineaarne programmeerimisülesanne või lihtsaim ruutmeetri programmeerimisülesanne:

Tingimustel:

Olgu sellele probleemile lahendus. Tingimus (8.25) garanteerib, et suund on võimalik. Tingimus (8.26) tagab maksimaalse väärtuse (st kõigi võimalike suundade hulgas - s, suund - tagab funktsiooni kiireima lagunemise f(x). Tingimus (8.27) välistab probleemi lahenduse piiramatuse. Võimalike suundade meetod on võimalike arvutusvigade suhtes vastupidav. Selle lähenemise määra on aga üldisel juhul raske hinnata ja see probleem jääb endiselt lahendamata.

Juhuslik otsingu meetod.Üldjuhul on ülaltoodud minimeerimismeetodite rakendamine väga töömahukas, välja arvatud lihtsaimad juhud, kui piirangute kogumil on lihtne geomeetriline struktuur (näiteks on tegemist mitmemõõtmelise rööptahulise). Üldjuhul võib juhuslik otsimismeetod, kui laskumissuund valitakse juhuslikult, olla väga paljutõotav. Sellisel juhul kaotame konvergentsimäära märkimisväärselt, kuid suuna valimise lihtsus võib need kahjud kompenseerida minimeerimisprobleemi lahendamiseks kogutööjõukulude osas.

Meetodi skeem:

N-mõõtmelise ühiku sfääril, mille keskpunkt on lähtepunkt, valitakse juhuslik punkt r k, alludes ühtlasele jaotusele selles sfääris ja siis on laskumissuund s k tingimustest

Valitakse esialgseks lähenduseks. Iga iteratsiooni ajal arvutatud punktis x k ehitamisel ( k+ 1) punkt x k +1 :

Kvaliteedina valitakse suvaline arv =, mis rahuldab ebavõrdsuse:

Selle meetodi lähenemine on tõestatud funktsiooni väga lõdva piiranguga f (kumerus) ja palju piiranguid X (kumerus ja suletus).

kogu valikute hulgast saate koostada histogrammi, hinnata, kui sageli häid valikuid ja lõpuks saate teha otsuse - jätkata otsingut või piirduda leitud lahendusega.

Hoolimata juhusliku uurimisprotseduuri mitmekülgsusest ja lihtsusest, ei saa seda piirata märkimisväärse arvutusliku keerukuse tõttu. Seetõttu on meetodid muutunud laialdasemaks suunatud otsing lahendusi.

4.5.3. Piiramatud optimeerimistehnikad

Kõigi eespool käsitletud vormide äärmuseni jõudmiseks vajalikud tingimused viivad mittelineaarsete võrrandite süsteemi lahendamiseni - see on väga keeruline ja töömahukas probleem (isegi arvutusmatemaatikas vähendatakse mittelineaarsete võrrandite lahendamist sageli teatud optimeerimisülesandeni). . Seetõttu kasutatakse praktikas funktsioone optimeerides ka teisi lähenemisviise, mille kaalumist alustatakse nn otseste meetoditega. Järgnevalt räägime siin minimeerimisest, seega on ekstreemum miinimum.

Praegu on nii tingimusteta kui ka tingimusliku optimeerimise probleemide jaoks välja töötatud palju arvulisi meetodeid. Numbrilise meetodi kvaliteeti iseloomustavad paljud tegurid: lähenemise kiirus, ühe iteratsiooni täitmise aeg, meetodi rakendamiseks vajaliku arvutimälu maht, lahendatavate probleemide klass jne. on ka väga mitmekesised: neil võivad olla kõrged ja madalad mõõtmed, need võivad olla ühemodaalsed ja mitmekstreemsed jne. Sama meetod, mis on tõhus ühe tüüpi probleemide lahendamiseks, võib osutuda täiesti vastuvõetamatuks teist tüüpi probleemide korral.

Allpool on ülevaade mittelineaarsete programmeerimisprobleemide lahendamise peamistest meetoditest. Tuleb meeles pidada, et kogu selliste meetodite loetelu on väga lai ja jääb avatuks. Lisaks on paljude vaadeldavate meetodite puhul teada erinevaid modifikatsioone. Lisateavet saab aadressilt

näide, c.

Alustuseks kaaluge piiramatu optimeerimise otseseid meetodeid, kui piiranguid pole.

Piiramatu optimeerimise otseste meetodite tähendus on punktide X, X, ..., X, näiteks,

et f (X)> f (X)> ……> f (X). Lähtepunktiks X võib valida suvalise punkti, kuid nad kipuvad seda valima miinimumpunktile võimalikult lähedale. Üleminek (iteratsioon) punktist X punkti X, k = 0,1,2, ... koosneb kahest etapist:

– liikumissuuna valik punktist NS;

– sammu määramine selles suunas.

Selliste järjestuste loomise meetodeid nimetatakse sageli laskumismeetoditeks, kuna üleminek funktsiooni suurematelt väärtustelt väiksematele toimub.

Laskumismeetodeid kirjeldab matemaatiliselt seos

X = X + a k p, k = 0,1,2, ...,

kus p on ühikuvektor, mis määrab laskumissuuna;

a k - sammu pikkus.

Erinevad laskumismeetodid erinevad üksteisest selle poolest, kuidas nad valivad p ja a k. Praktikas kasutatakse ainult lähenemise meetodeid. Need võimaldavad miinimumpunkti saamiseks või sellele piisavalt lähedale jõudmiseks piiratud arvu samme. Korduvate iteratiivsete meetodite kvaliteeti hinnatakse lähenemise määra järgi.

Teoreetiliselt lahendavad laskumismeetodid probleemi lõpmatu arvu korduste korral. Praktikas arvutused lõpetatakse, kui on täidetud teatud kriteeriumid (tingimused) iteratiivse protsessi peatamiseks. Näiteks võib see olla selle väiksuse tingimus

f (X [k]) - f (X [k - 1])< γ . Здесь k – номер итерации; ε , γ – задан-

ülesande lahenduse täpsuse väärtused.

Miinimumpunkti leidmise meetodeid nimetatakse deterministlikeks, kui X -lt X -le ülemineku mõlemad parameetrid (liikumissuund ja astme suurus) on ainulaadselt valitud punktis X saadaoleva teabe hulgast. Kui ülemineku ajal kasutatakse mõnda juhuslikku mehhanismi, nimetatakse otsingu algoritmi minimaalseks juhuslikuks otsinguks.

Piiramatu minimeerimise deterministlikud algoritmid on jaotatud klassidesse sõltuvalt kasutatava teabe tüübist. Kui igal iteratsioonil kasutatakse ainult minimeeritud funktsioonide väärtusi, nimetatakse seda meetodit nulljärku meetodiks. Kui lisaks on vaja arvutada minimeeritava funktsiooni esimesed tuletised, siis on olemas esimese järgu meetodid,

kui on vaja täiendavalt arvutada teisi tuletisi - teise järgu meetodeid.

Tuleb märkida, et piiramatu minimeerimise probleemide lahendamisel on esimese ja teise järgu meetoditel reeglina suurem lähenemiskiirus kui nulljärgu meetoditel. Kuid praktikas on suure hulga muutujate funktsiooni esimese ja teise tuletise arvutamine väga töömahukas. Mõnel juhul ei ole neid võimalik saada analüütiliste funktsioonidena. Tuletisinstrumendid määratakse kindlaks erinevate numbriliste meetodite abil, kus on vigu, mis võivad selliste meetodite rakendamist piirata. Lisaks saab optimaalsuse kriteeriumi täpsustada mitte selgesõnaliselt, vaid võrrandisüsteemi abil. Sellisel juhul muutub tuletiste leidmine analüütiliselt või arvuliselt väga keeruliseks ja mõnikord võimatuks. Seetõttu on siin kõige üksikasjalikumad nulljärjestuse meetodid.

Ühemõõtmelised otsingumeetodid. Ühemõõtmelise otsingu meetodite loend - ühe argumendi funktsiooni ekstreemsuse numbriline otsing f (x ) On piisavalt lai ja kirjanduses hästi kaetud. Seetõttu piirdume siin ainult ühe meetodi kaalumisega, mis autorite kogemuste kohaselt on üks tõhusamaid - kuldse lõigu meetod.

Meetodi mõte on vähendada järjestikku määramatuse intervalli - argumendi x väärtuste vahemikku, mis sisaldab nõutavat miinimumpunkti - pikkuseks, mis ei ületa

tulemuse lubatud viga ε. Esialgseks intervalliks on probleemitingimustes määratud argumendi lubatud väärtuste vahemik või juhul, kui viimasel ei ole vasak- ja (või) paremaid piire, mõni piir lubatud piirides, milleni nõutav miinimum on näidatud esialgse analüüsiga, võib kaaluda.

Iga intervall sisaldab kahte punkti x = y 0 ja x = z 0, mis täidavad oma "kuldse suhte" - jagamise kaheks ebavõrdseks osaks nii, et suurema osa ja kogu intervalli pikkuse suhe langeb kokku väiksem osa suuremaks. Ilmselgelt paiknevad need punktid intervalli keskpunkti suhtes sümmeetriliselt (joonis 26). "Kuldse lõigu" punktide koordinaadid leiate vastavatest proportsioonidest:

kust on lihtne saada δ = (1 - δ) / δ ja jõuda võrrandini: δ 2 + δ –1 = 0. Selle tulemusena saame suhtelised osad, mis määravad intervalli "kuldse lõigu": δ = 0,618, 1 - δ = 0,382. “Kuldsel lõigul” on oluline omadus: punkt y 0 on üks intervalli “kuldse lõigu” punktidest, punkt z 0 on üks intervalli “kuldse lõigu” punktidest. See kindlustab

ees ootab lihtne arvutus: 0,382 / 0,618 = 0,618 ja (0,618–0,382) / 0,618 = = 0,382.

Minimaalse leidmise algoritm, mis põhineb kuldse lõigu meetodil, näeb igal iteratsioonil ette kuldse lõigu vasaku või parema punkti vähendatud intervalli ühe piirina, nii et vajalik miinimum jääb selle sisse:

1. Määra k = 0, esialgne määramatuse intervall, tulemi lubatud viga ε.

2. Arvutage kuldse lõigu punktide koordinaadid:

y k = a k +0,382 (b k –a k), z k = a k +0,618 (b k –a k).

3. Arvutage leitud punktides sihtfunktsiooni väärtused

f (y k) ja f (z k).

4. Kui f (yk) ≤f (zk) (joonis 26, a), määrake ak + 1 = ak, bk + 1 = zk, zk + 1 = yk, yk + 1 = ak + zk –yk, k = k +1. Vastasel korral (joonis 26, b) a k + 1 = y k, b k + 1 = b k, y k + 1 = z k, z k + 1 = y k + b k –z k, k = k +1.

5. Kontrollige otsingu lõpuleviimise tingimuse täitmist

b k + 1 - a k + 1 ≤ ε. Kui see on täidetud, valitakse lahendusena punkt x = (y k + 1 + z k + 1) 2. Vastasel korral jätkake 2. sammuga.

"Kuldse sektsiooni" meetodi arvutuslik efektiivsus tuleneb asjaolust, et siin on igal iteratsioonil vaja ainult ühte objektiivse funktsiooni väärtuse arvutamist.

Otsese otsingu meetod (Hook-Jeevesi meetod). Mõned

teine ​​lähtepunkt X. Vektori X komponente vaheldumisi muutes uuritakse selle punkti naabruskonda, mille tulemusel leitakse punkt (uus alus), mis määrab suuna, kuhu minimeeritud funktsioon f (X) väheneb. Laskumine toimub valitud suunas, veendudes, et funktsiooni väärtus väheneb. Protseduuri korratakse tsükliliselt, kuni on võimalik leida laskumissuund, võttes arvesse aktsepteeritud peatumistingimusi.

Otsese otsingu meetodi algoritmi kõige üldisemal kujul saab sõnastada järgmiselt.

1. Määrake koordinaatide x i, i = 1,2, ... n väärtuste järgi, lähtepunkt (k = 0), koordinaatide esialgse juurdekasvu vektor

∆ X = (∆ x 1, ∆ x 2, ..., ∆ xn) naabruskonna uuringu ajal komponentide väikseim lubatud väärtus ε X, kiirendustegur λ ≥ 1, mis määrab laskumiskiiruse, skaala tegur d> 1.

2. Võtke X "vana aluse" jaoks: X b = X. Arvutama

väärtus f (X b).

3. Muutke vaheldumisi iga koordinaati x b i, i = 1,2, ... n,

punktid X b väärtusega ∆ x i, st võtame x i = x b i + ∆ x i, siis

x i = x b i –∆ x i. Arvutage f (X) väärtused saadud proovipunktides ja võrrelge neid f (X b) väärtusega. Kui f (X)< < f (X б ), то соответствующая координата х i приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n -й координаты f (X )

4. Viige laskumine suunas "vanalt" uuele alusele läbi viimase, st arvutage uue punkti koordinaadid

X: x i = x i + λ (x i –x bi), i = 1,2,… n. Arvutage f (X) väärtus. Kui tingimus f (X)

"Uueks" aluseks loetakse "vana" (X b = X, f (X b) = f (X)) ja minnakse sammu 5. Vastasel juhul x i = x i, i = 1,2, ... n ...

5. Nagu lk 3, muutke vaheldumisi punkti iga koordinaati X, võrreldes funktsiooni f (X) vastavaid väärtusi sammuga 4 saadud väärtusega f (X). Pärast viimase koordinaadi muutmist võrrelge vastavat väärtust

funktsiooni f (X) väärtusega f (X b), mis on saadud 4. jaos. Kui f (X)

6. Kui kõigi i ∆ x i puhul<ε , вычисления прекращаются. В противном случае уменьшают значения ∆ х i в d раз и переходят к п. 3.

Algoritmi toimimist on näidatud joonisel fig. 27. Ridade näitamine

minimeeritud funktsiooni tase f (x 1, x 2), st tingimustest f (x 1, x 2) saadud jooned = f 1 = const, f (x 1, x 2) = f 2 = const ja nii edasi. Siin f 1> f 2> f 3. Pidevad jooned on sammude ühe täitmise tulemused. 3 ... 5 (otsige funktsiooni vähendamise suunda ja laskumist), katkendjoon - järgmine laskumine.

Otsese otsingu meetodi eeliseks on selle programmeerimise lihtsus arvutis. See ei nõua eesmärgifunktsiooni selgesõnalist tundmist ning võtab hõlpsalt arvesse ka üksikute muutujate piiranguid ja otsingu ulatuse keerulisi piiranguid.

Otsese otsingu meetodi puuduseks on see, et objektiivse funktsiooni taseme tugevalt pikliku, kumera või terava nurgaga joonte korral ei pruugi see analüüsitud suundade piiratud arvu tõttu tagada edusamme miinimumini.

Deformeeritav polühedronmeetod (Nelder-Meadi meetod) see on funktsiooni minimeerimiseks n muutujat f (X) n-mõõtmelises ruumi, on ehitatud hulktahukas, mis sisaldab n +1 tipp. Ilmselgelt vastab iga tipp mõnele vektorile Xi ... Arvutage eesmärgifunktsiooni väärtused f (Xi), i = 1,2, ..., n +1, määrake polühedrooni igas tipus nende väärtuste maksimum ja vastav tipp Xh ... Joonista selle tipu ja ülejäänud tippude raskuskeskme kaudu väljaulatuv joon, millel punkt asub Xq väiksema objektiivfunktsiooni väärtusega kui tipus Xh (joonis 28, a ). Seejärel välistage ülemine osa Xh ... Ülejäänud tippudest ja punktidest Xq konstrueeritakse uus hulktahukas, millega kirjeldatud protseduuri korratakse. Selliste toimingute tegemise käigus muudab hulktahukas oma suurust, mistõttu nimetati meetodit.

Tutvustame järgmist märget: X on hulktahuka i-nda tipu koordinaatide vektor k-nda otsinguetapi korral, i = 1,2,… n +1, k = 1,2,…; h - tipu number, milles sihtmärgi väärtus

rehvid, välja arvatud X. Arvutuse raskuskeskme koordinaadid

Ligikaudne algoritm deformeeritava polüedrimeetodi jaoks on järgmine:

1. Määravad peegeldusteguridα, pinge γ> 1, kokkusurumine β<1 , допустимой погрешностью определения координат

miinimum ε punktid. Valitud on algse hulktahuka X tippude koordinaadid, i = 1,2, ... n +1, k = 1.

2. Arvutage eesmärgifunktsiooni väärtused kõikidel tippudel f (X), i = 1,2, ... n + 1 ja leidke punktid X, X (joonisel 28, b vastavalt punktid X 2 ja X 1), samuti X.

3. Teostage punktprojektsioon X läbi keskpunkti

leht: X = X + α (X –X).

4. Kui f (X) ≤ X, tehke venitus.

x = X + γ (X – X). Vastasel korral minge punkti 6 juurde.

5. Ehitatakse uus hulktahukas: kui f (X)

asendades X X -ga, vastasel juhul X X -ga. Arvutusi jätkatakse punktist 2 k = k +1 korral.

6. Kui X> f (X)> X kõigi i puhul ei ole h,

tehke tihendusoperatsioon: X = X + β (X - X). Konstrueeritakse uus poltoop, asendades X X -ga ja arvutusi jätkatakse punktist 2 k = k +1 jaoks.

7. Kui f (X)> X, siis tipu X hoides konstrueerige praegusele sarnane uus hulktahukas, vähendades pooleks kõikide servade pikkused: X = X +0,5 (X – X) ja jätkake arvutusi punktist 2 k = k +1 korral.

Lk. 6, 7, tuleb enne punkti 2 juurde liikumist kontrollida, kas miinimumiotsingu lõpuleviimise tingimus on täidetud, näiteks

vaade max n ∑ + 1 (x j [i, k] - x j [n + 2, k]) 2< ε 2 .

i j = 1

KOOS Venitus- ja kokkusurumisoperatsiooni abil kohandatakse deformeeritava polüedri mõõtmed ja kuju vastavalt objektiivse funktsiooni topograafiale. Selle tulemusena venib hulktahukas piki kaldpindu, muudab suunda kõverates orgudes ja kahaneb miinimumi läheduses, mis määrab vaadeldava meetodi tõhususe.

α = 1, 2≤ γ ≤3, 0,4≤β ≤0,6.

Pöörlev koordinaatide meetod (Rosenbrocki meetod). Selle olemus seisneb koordinaatsüsteemi järjestikustes pöörlemistes vastavalt eesmärgifunktsiooni kõige kiirema languse suuna muutumisele (joonis 29). Lähtepunktist X laskuda asja juurde X koordinaattelgedega paralleelsetes suundades. Järgmisel iteratsioonil peab üks telgedest suunda läbima x'1 = X - X, ülejäänud - risti suundades x'1 ... Laskumine mööda neid telgi viib punkti X , mis võimaldab konstrueerida uue vektori x''1 = X - X ja selle alusel uus otsingusuundade süsteem

miinimumpunktid X.

V Erinevalt teistest nulljärjestuse meetoditest keskendub Rosenbrocki meetod optimaalse punkti leidmisele igas suunas, mitte ainult fikseeritud nihe igas suunas. Sammude suurus otsinguprotsessis muutub pidevalt sõltuvalt tasase pinna topograafiast. Koordinaatide pöörlemise ja kõrguse reguleerimise kombinatsioon muudab Rosenbrocki meetodi tõhusaks keerukate optimeerimisülesannete lahendamisel.

V Eelkõige on see meetod erinevalt paljudest teistest efektiivne nn kuristikufunktsioonide minimeerimiseks (tugevalt pikliku tasapinnaga), kuna saadud otsingusuund kipub paiknema piki kuristiku telge.

Paralleelset puutuja meetodit (Powelli meetod). Selle olemus seisneb objektiivse funktsiooni miinimumi ühemõõtmelise otsingu teostamises järjestikku n + 1 suund tuntud ühemõõtmelistest meetoditest. Esimesel iteratsioonil, nagu esimene n juhised on valitud koordinaat, nagu(n + 1) juhiseid, millest esimest kasutatakse (joonis 30). Igal järgneval iteratsioonil algab otsing vastavalt eelmise iteratsiooni teisest suunast, suunanumbrid vähenevad ühe võrra;(n + 1) järgneva iteratsiooni suuna annab vektor X– X [n + 1] - alates eelmise iteratsiooni esimeses etapis leitud miinimumpunktist kuni viimases etapis leitud miinimumpunktini.

5. Mitmemõõtmeline optimeerimine

Lineaarne programmeerimine

Optimeerimine Kas sihipärane tegevus, mille eesmärk on sobivatel tingimustel saavutada parimaid tulemusi.

Optimeeritud kvaliteedi kvantitatiivset hindamist nimetatakse Optimaalsuse kriteerium või sihtfunktsioon Seda saab kirjutada järgmiselt:

kus x 1, x 2, ..., x n- mõned objekti optimeerimise parameetrid.

Optimeerimisprobleeme on kahte tüüpi - tingimusteta ja tingimuslikud.

Tingimusteta ülesanne optimeerimine seisneb tegeliku funktsiooni (5.1) maksimumi või miinimumi leidmisesnkehtivad muutujad ja vastavate argumentide väärtuste määratlemine.

Tingimuslikud optimeerimisprobleemid või probleemid piirangutega on need, mille sõnastamisel seatakse argumentide väärtustele piiranguid võrdsuse või ebavõrdsuse kujul.

Lahendus optimeerimisülesannetele, mille puhul optimaalsuse kriteerium on sõltumatute muutujate lineaarne funktsioon (st sisaldab neid muutujaid esimeses astmes) koos lineaarsete piirangutega, on teema lineaarne programmeerimine.

Sõna "programmeerimine" peegeldab siin uuringu lõppeesmärki - määrata optimaalne plaan või optimaalne programm, mille järgi valitakse uuritava protsessi võimalike variantide hulgast parim, optimaalne variant.

Näide selline ülesanne on toorainete optimaalne jaotus erinevate tööstusharude vahel maksimaalse tootmiskuluga.

Olgu kahte tüüpi tooteid valmistatud kahte tüüpi toorainest.

Tähistame: x 1, 2 - vastavalt esimese ja teise tüübi toodete ühikute arv; c 1, c 2 - vastavalt esimese ja teise tüübi toodete ühikud. Siis on kõigi toodete kogumaksumus:

Tootmise tulemusena on soovitav, et tootmise kogumaksumus oleks maksimaalne.R (x 1, x 2 ) Kas selle probleemi eesmärk on funktsioon.

b 1, b 2 - esimese ja teise liigi tooraine kogus;a ij- ühikute arv i -üksuse tootmiseks vajalik tooraine tüüpj-tootetüüp.

Arvestades, et selle ressursi tarbimine ei tohi ületada selle kogusummat, kirjutame ressursside piiravad tingimused üles:

Muutujad x 1, 2 võime ka öelda, et need ei ole negatiivsed ega ole lõpmatud.:

Ebavõrdsussüsteemi (5.3) ja (5.4) lahenduste hulgast tuleb leida selline lahendus ( x 1, 2 ), mille jaoks funktsioonRsaavutab kõrgeima väärtuse.

Sarnasel kujul sõnastatakse nn transpordiülesanded (kaupade, tooraine või toodete optimaalse korraldamise ülesanded erinevatest ladudest mitme sihtkohaga minimaalsete transpordikuludega) ja hulk muid.

Graafiline meetod lineaarse programmeerimise ülesannete lahendamiseks.

Olgu see nõutud leidmiseks x 1 ja x 2 , rahuldav ebavõrdsuste süsteem:

ja tingimused mitte-negatiivsus:

eest milline funktsioon

jõuab maksimumini.

Lahendus.

Joonistage ristkülikukujuline koordinaatsüsteem x 1 Härg 2 probleemi teostatavate lahenduste valdkond (joonis 11). Selleks konstrueerime kõik ebavõrdsused (5.5) võrdsusega vastav talle piirjoon:

(i = 1, 2, … , r)

Riis. üksteist

See joon jagab kogu tasapinna kaheks tasapinnaks. Koordinaatide jaoks x 1, 2 mis tahes punkt Aühel pooltasapinnal kehtib järgmine ebavõrdsus:

ja mis tahes punkti koordinaatide jaoks V teine ​​pooltasand on vastupidine ebavõrdsus:

Piirijoone mis tahes punkti koordinaadid vastavad võrrandile:

Et teha kindlaks, kummal pool piirjoont asub antud ebavõrdsusele vastav pooltasapind, piisab ühe punkti "testimisest" (lihtsaim punkt on O(0; 0)). Kui selle koordinaadid ebavõrdsuse vasakule küljele asendades see rahuldatakse, siis pööratakse pooltasapind katsepunkti poole, kui ebavõrdsus ei ole täidetud, siis pööratakse vastav pooltasand vastupidises suunas. Pooltasapinna suund on joonisel näidatud koorumisega. Ebavõrdsus:

vastavad pooltasapindadele, mis asuvad ordinaadist paremal ja abstsissist kõrgemal.

Joonisel konstrueerime kõigile ebavõrdsustele vastavad piirjooned ja pooltasandid.

Kõigi nende pooltasapindade ühisosa (ristmik) kujutab endast selle probleemi teostatavate lahenduste piirkonda.

Võimalike lahenduste piirkonna ehitamisel võib sõltuvalt muutujate piirangute (ebavõrdsuste) konkreetsest tüübist esineda üks järgmistest neljast juhtumist:

Riis. 12. teostatavate lahenduste piirkond on tühi, mis vastab ebavõrdsussüsteemi ebajärjekindlusele; pole lahendust

Riis. 13. Võimalike lahenduste piirkonda kujutab üks punkt A, mis vastab süsteemi ainsale lahendusele

Riis. 14. Võimalike lahenduste piirkond on piiratud, kujutatud kumera hulknurgana. Võimalikke lahendusi on lõputult

Riis. 15. Võimalike lahenduste piirkond on piiramatu, kumera hulknurkse piirkonna kujul. Võimalikke lahendusi on lõputult

Eesmärgifunktsiooni graafiline esitus

fikseeritud väärtusegaRmääratleb sirge ja muutmiselR- parameetriga paralleelsete joonte perekondR. Kõigi ühel sirgel asuvate punktide puhul funktsioon R võtab ühe kindla väärtuse, seetõttu nimetatakse neid ridu taseme jooned funktsiooni R jaoks.

Gradiendivektor:

ristitaseme joontele, näitab tõusu suundaR.

Probleem leida optimaalne lahendus ebavõrdsuste süsteemile (5.5), mille jaoks eesmärk toimibR(5.7) jõuab maksimumini, taandab geomeetriliselt lubatavate lahenduste piirkonnas punkti, mille kaudu vastava taseme joon suurim väärtus parameeterR

Riis. 16

Kui teostatavate lahenduste piirkond on kumer hulknurk, siis funktsiooni äärmusR on saavutatud vähemalt selle polügooni ühes tipus.

Kui äärmuslik väärtusRsaavutatakse kahes tipus, siis sama äärmuslik väärtus saavutatakse neid kahte tippu ühendava segmendi mis tahes punktis. Sel juhul öeldakse, et probleem on olemas alternatiivne optimaalne .

Piiramatu domeeni korral funktsiooni äärmusRkas ei eksisteeri või on jõutud piirkonna ühte tippu või on sellel alternatiivne optimum.

Näide.

Olgu nõutud väärtuste leidmine x 1 ja x 2 rahuldada ebavõrdsuste süsteemi:

ja tingimused mitte-negatiivsus:

eest milline funktsioon:

jõuab maksimumini.

Lahendus.

Asendame kõik ebavõrdsused võrdsusega ja konstrueerime piirjooned:

Riis. 17

Määratleme nendele ebavõrdsustele vastavad pooltasandid, "testides" punkti (0; 0). Võttes arvesse mitte-negatiivsus x 1 ja x 2 saame selle probleemi teostatavate lahenduste piirkonna kumera hulknurga kujul OAVDE.

Võimalike lahenduste piirkonnas leiame optimaalse lahenduse gradiendivektori koostamise teel

näidatestõusvas suunasR.

Optimaalne lahendus vastab punktile V mille koordinaate saab määrata kas graafiliselt või lahendades kahe võrrandi süsteemi, mis vastavad piirjoontele AB ja VD:

Vastus: x 1 = 2; x 2 = 6; R max = 22.

Ülesanded. Leidke äärmuspunkti asukoht ja objektiivfunktsiooni äärmuslik väärtus

etteantud piirangute alusel.