Algoritmi i metode neograničene optimizacije. Klasične metode optimizacije bez ograničenja. Klasifikacija metoda koje se razmatraju

Optimalnom se smatra najprihvatljivija opcija odluke koja se donosi na razini menadžera o bilo kojem pitanju, a proces njenog traženja optimizacijom.

Međuovisnost i složenost organizacijskih, socioekonomskih, tehničkih i drugih aspekata upravljanja proizvodnjom trenutno se svodi na donošenje upravljačke odluke koja utječe na veliki broj različitih čimbenika koji su međusobno usko isprepleteni, što onemogućuje njihovu analizu pojedinačno. koristeći tradicionalne analitičke metode.

Većina čimbenika odlučujuća je u procesu donošenja odluka i oni se (inherentno) ne mogu kvantificirati. Ima i onih koji su praktički nepromijenjeni. U tom smislu ukazala se potreba za razvojem posebnih metoda koje bi mogle osigurati odabir važnih upravljačkih odluka u okviru složenih organizacijskih, ekonomskih, tehničkih problema (ekspertne procjene, metode operacijskog istraživanja i optimizacije itd.).

Metode operacijskog istraživanja koriste se za pronalaženje optimalnih rješenja u područjima upravljanja kao što su organizacija proizvodnih i transportnih procesa, planiranje velike proizvodnje, materijalno-tehnička opskrba.

Metode optimizacije rješenja uključuju istraživanje usporedbom numeričkih procjena brojnih čimbenika, čija se analiza ne može provesti tradicionalnim metodama. Optimalno rješenje je najbolje među mogućim opcijama u pogledu gospodarskog sustava, a najprihvatljivije u odnosu na pojedine elemente sustava je suboptimalno.

Bit metoda operacijskog istraživanja

Kao što je ranije spomenuto, oni tvore metode za optimizaciju upravljačkih odluka. Njihova osnova su matematički (deterministički), probabilistički modeli koji predstavljaju proces, vrstu aktivnosti ili sustav koji se proučava. Ova vrsta modela predstavlja kvantitativnu karakteristiku odgovarajućeg problema. Oni služe kao osnova za donošenje važnih upravljačkih odluka u procesu traženja optimalne opcije.

Popis pitanja koja igraju značajnu ulogu za izravne voditelje proizvodnje i koja se rješavaju tijekom korištenja metoda koje se razmatraju:

stupanj valjanosti odabranih opcija odluke;
koliko su bolji od alternativa;
stupanj uvažavanja odlučujućih faktora;
koji je kriterij optimalnosti odabranih rješenja.

Ove metode optimizacije odlučivanja (menadžerske) usmjerene su na pronalaženje optimalnih rješenja za što veći broj tvrtki, tvrtki ili njihovih odjela. Temelje se na postojećim dostignućima u statističkim, matematičkim i ekonomskim disciplinama (teorija igara, čekanje u redu, grafika, optimalno programiranje, matematička statistika).

Metode ekspertne procjene

Ove metode za optimizaciju upravljačkih odluka koriste se kada problem djelomično ili u potpunosti nije podložan formalizaciji, a njegovo rješenje se ne može pronaći matematičkim metodama.

Ekspertiza je proučavanje složenih posebnih pitanja u fazi izrade određene upravljačke odluke od strane relevantnih osoba koje imaju posebnu bazu znanja i impresivno iskustvo u svrhu dobivanja zaključaka, preporuka, mišljenja i ocjena. U procesu stručnog istraživanja koriste se najnovija dostignuća znanosti i tehnologije u okviru specijalizacije stručnjaka.

Razmotrene metode optimizacije niza upravljačkih odluka (stručnih procjena) učinkovite su u rješavanju sljedećih zadataka upravljanja u području proizvodnje:

Proučavanje složenih procesa, pojava, situacija, sustava koje karakteriziraju neformalna, kvalitativna obilježja.
Rangiranje i određivanje, prema zadanom kriteriju, značajnih čimbenika koji su odlučujući za funkcioniranje i razvoj proizvodnog sustava.
Razmatrane metode optimizacije posebno su učinkovite u predviđanju trendova u razvoju proizvodnog sustava, kao i njegove interakcije s vanjskim okruženjem.
Povećanje pouzdanosti stručne procjene uglavnom ciljnih funkcija koje su kvantitativne i kvalitativne prirode, usrednjavanjem mišljenja kvalificiranih stručnjaka.

A ovo su samo neke metode za optimizaciju niza upravljačkih odluka (stručna procjena).

Klasifikacija metoda koje se razmatraju

Metode rješavanja optimizacijskih problema, prema broju parametara, mogu se podijeliti na:

Jednodimenzionalne optimizacijske metode.
Metode višedimenzionalne optimizacije.

Također se nazivaju "numeričke metode optimizacije". Točnije, ovo su algoritmi za njegovo pretraživanje.

Kao dio korištenja derivata, metode su:

metode izravne optimizacije (nulti red);
metode gradijenta (1. red);
metode 2. reda itd.

Većina metoda višedimenzionalne optimizacije bliska je problemu druge skupine metoda (jednodimenzionalna optimizacija).

Jednodimenzionalne optimizacijske metode

Sve metode numeričke optimizacije temelje se na približnom ili točnom izračunu takvih karakteristika kao što su vrijednosti funkcije cilja i funkcije koje definiraju dopušteni skup i njihove derivacije. Dakle, za svaki pojedini zadatak pitanje izbora karakteristika za proračun može se riješiti ovisno o postojećim svojstvima funkcije koja se razmatra, raspoloživim mogućnostima i ograničenjima u pohranjivanju i obradi informacija.

Postoje sljedeće metode za rješavanje problema optimizacije (jednodimenzionalne):

Fibonaccijeva metoda;
dihotomije;
Zlatni omjer;
udvostručivši korak.

Fibonaccijeva metoda

Prvo morate postaviti koordinate točke x na intervalu kao broj jednak omjeru razlike (x - a) i razlike (b - a). Prema tome, a ima koordinatu 0 u odnosu na interval, a b ima koordinatu 1, a središte je ½.

Ako pretpostavimo da su F0 i F1 međusobno jednaki i uzmemo vrijednost 1, F2 će biti jednak 2, F3 - 3, ..., tada je Fn = Fn-1 + Fn-2. Dakle, Fn su Fibonaccijevi brojevi, a Fibonaccijevo pretraživanje je optimalna strategija za takozvano sekvencijalno traženje maksimuma zbog činjenice da je vrlo blisko povezano s njima.

Kao dio optimalne strategije, uobičajeno je odabrati xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. Za bilo koji od dva intervala (ili), od kojih svaki može djelovati kao suženi interval nesigurnosti, točka (naslijeđena) u odnosu na novi interval imat će ili koordinate , ili . Zatim se kao xn - 2 uzima točka koja ima jednu od prikazanih koordinata u odnosu na novi interval. Ako koristite F(xn - 2), vrijednost funkcije koja je naslijeđena iz prethodnog intervala, postaje moguće smanjiti interval nesigurnosti i naslijediti jednu vrijednost funkcije.

U završnom koraku bit će moguće prijeći na interval nesigurnosti kao što je , dok je središnja točka naslijeđena iz prethodnog koraka. Kao x1, postavljena je točka koja ima relativnu koordinatu ½+ε, a konačni interval nesigurnosti će biti ili [½, 1] u odnosu na .

U 1. koraku duljina ovog intervala smanjena je na Fn-1: Fn (od jedan). U završnim koracima smanjenje duljina odgovarajućih intervala predstavlja se brojevima Fn-2: Fn-1, Fn-3: Fn-2, ..., F2: F3, F1: F2 (1 + 2ε ). Dakle, duljina takvog intervala kao konačne verzije poprimit će vrijednost (1 + 2ε) : Fn.

Ako zanemarimo ε, tada će asimptotski 1: Fn biti jednako rn, s n→∞, i r = (√5 - 1) : 2, što je približno jednako 0,6180.

Vrijedno je napomenuti da asimptotski za značajan n, svaki sljedeći korak Fibonaccijeve pretrage značajno sužava razmatrani interval za gornji koeficijent. Taj se rezultat mora usporediti s 0,5 (koeficijent sužavanja intervala nesigurnosti unutar metode bisekcije za određivanje nule funkcije).

Metoda dihotomije

Ako zamislite određenu ciljnu funkciju, tada prvo trebate pronaći njezin ekstrem na intervalu (a; b). Da biste to učinili, os apscisa je podijeljena na četiri ekvivalentna dijela, tada je potrebno odrediti vrijednost dotične funkcije u 5 točaka. Zatim se odabire najmanji među njima. Ekstrem funkcije mora ležati unutar intervala (a"; b"), koji je susjedan točki minimuma. Granice pretraživanja sužene su 2 puta. A ako se minimum nalazi u točki a ili b, onda se sužava za sva četiri puta. Novi interval također je podijeljen na četiri jednaka segmenta. Zbog činjenice da su vrijednosti ove funkcije u tri točke određene u prethodnoj fazi, tada je potrebno izračunati funkciju cilja u dvije točke.

Metoda zlatnog reza

Za značajne vrijednosti n, koordinate točaka kao što su xn i xn-1 su blizu 1 - r, jednako 0,3820, i r ≈ 0,6180. Potisak od ovih vrijednosti vrlo je blizu željene optimalne strategije.

Ako pretpostavimo da je F(0,3820) > F(0,6180), tada je interval ocrtan. Međutim, zbog činjenice da je 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, tada je F već poznat u ovom trenutku. Posljedično, u svakoj fazi, počevši od 2., potreban je samo jedan izračun funkcije cilja, a svaki korak smanjuje duljinu razmatranog intervala za faktor 0,6180.

Za razliku od Fibonaccijeve pretrage, ova metoda ne zahtijeva fiksiranje broja n prije početka pretrage.

“Zlatni presjek” presjeka (a; b) je presjek kod kojeg je omjer njegove duljine r prema većem dijelu (a; c) identičan omjeru većeg dijela r prema manjem, tj. , (a; c) do (c; b). Nije teško pogoditi da je r određen gornjom formulom. Posljedično, za značajno n, Fibonaccijeva metoda ulazi u ovu.

Metoda udvostručavanja koraka

Suština je traženje smjera smanjenja ciljne funkcije, kretanje u tom smjeru u slučaju uspješnog traženja s postupnim povećanjem koraka.

Prvo odredimo početnu koordinatu M0 funkcije F(M), najmanju vrijednost koraka h0 i smjer traženja. Zatim definiramo funkciju u točki M0. Zatim ćemo napraviti korak i pronaći vrijednost ove funkcije u ovoj točki.

Ako je funkcija manja od vrijednosti koja je bila u prethodnom koraku, sljedeći korak treba poduzeti u istom smjeru, nakon što je prvo povećan za 2 puta. Ako je njegova vrijednost veća od prethodne, morat ćete promijeniti smjer traženja i zatim se početi kretati u odabranom smjeru s koracima h0. Prikazani algoritam se može modificirati.

Metode višedimenzionalne optimizacije

Gore spomenuta metoda nultog reda ne uzima u obzir derivacije minimizirane funkcije, zbog čega njihova uporaba može biti učinkovita ako se jave bilo kakve poteškoće pri izračunavanju derivacija.

Skupina metoda 1. reda naziva se i gradijentnim metodama, jer se za određivanje smjera pretraživanja koristi gradijent zadane funkcije - vektor čije su komponente parcijalne derivacije minimizirane funkcije u odnosu na odgovarajuće optimizirane parametre. .

U skupini metoda 2. reda koriste se 2 derivacije (njihova upotreba je prilično ograničena zbog poteškoća u njihovom izračunavanju).

Popis metoda neograničene optimizacije

Kada koristite višedimenzionalno pretraživanje bez korištenja izvedenica, metode neograničene optimizacije su sljedeće:

Hook i Jeeves (provođenje 2 vrste pretraživanja - temeljeno na obrascima i istraživačko);
minimizacija ispravnim simpleksom (traženje minimalne točke odgovarajuće funkcije usporedbom njezinih vrijednosti na vrhovima simpleksa pri svakoj pojedinačnoj iteraciji);
cikličko spuštanje koordinata (koristeći koordinatne vektore kao referentne točke);
Rosenbrock (temeljen na korištenju jednodimenzionalne minimizacije);
minimizacija korištenjem deformiranog simpleksa (modifikacija metode minimizacije korištenjem regularnog simpleksa: dodavanje postupka kompresije i istezanja).

U situaciji korištenja derivacija u procesu višedimenzionalne pretrage izdvaja se metoda najstrmijeg spuštanja (najtemeljniji postupak za minimiziranje diferencijabilne funkcije s više varijabli).

Postoje i druge metode koje koriste konjugirane smjerove (Davidon-Fletcher-Powell metoda). Njegova bit je prikaz pravaca pretraživanja kao Dj*grad(f(y)).

Klasifikacija matematičkih optimizacijskih metoda

Konvencionalno, na temelju dimenzije funkcija (cilj), to su:

s 1 varijablom;
višedimenzionalni.

Ovisno o funkciji (linearna ili nelinearna), postoji veliki broj matematičkih metoda usmjerenih na pronalaženje ekstrema za rješavanje problema.

Na temelju kriterija korištenja izvedenica metode matematičke optimizacije dijele se na:

metode za izračunavanje 1 izvoda funkcije cilja;
višedimenzionalni (1. derivacija-vektorska količina-gradijent).

Na temelju učinkovitosti izračuna postoje:

metode za brzo izračunavanje ekstrema;
pojednostavljeni izračun.

Ovo je uvjetna klasifikacija metoda koje se razmatraju.

Optimizacija poslovnih procesa

Ovdje se mogu koristiti različite metode, ovisno o problemima koji se rješavaju. Uobičajeno je razlikovati sljedeće metode optimizacije poslovnih procesa:

iznimke (smanjenje razina postojećeg procesa, otklanjanje uzroka smetnji i dolazne kontrole, smanjenje transportnih ruta);
pojednostavljenje (olakšana obrada narudžbi, smanjena složenost strukture proizvoda, raspodjela posla);
standardizacija (korištenje posebnih programa, metoda, tehnologija itd.);
ubrzanje (paralelni inženjering, stimulacija, operativni dizajn prototipova, automatizacija);
promjena (promjene u sirovinama, tehnologiji, metodama rada, osoblju, sustavima rada, obujmu narudžbi, postupcima obrade);
osiguranje interakcije (u odnosu na organizacijske jedinice, osoblje, sustav rada);
odabir i uključivanje (u odnosu na potrebne procese, komponente).

Porezna optimizacija: metode

Rusko zakonodavstvo pruža poreznom obvezniku vrlo bogate mogućnosti za smanjenje poreza, zbog čega je uobičajeno razlikovati takve metode usmjerene na njihovo minimiziranje kao opće (klasične) i posebne.

Opće metode porezne optimizacije su sljedeće:

razrada računovodstvene politike tvrtke uz maksimalno moguće korištenje mogućnosti koje pruža rusko zakonodavstvo (postupak otpisa malih poduzeća, izbor metode izračuna prihoda od prodaje robe itd.);
optimizacija putem ugovora (sklapanje povlaštenih transakcija, jasna i kompetentna uporaba teksta itd.);
primjena raznih vrsta olakšica i poreznih oslobođenja.

Drugu skupinu metoda također mogu koristiti sve tvrtke, ali one još uvijek imaju prilično uzak opseg primjene. Posebne metode porezne optimizacije su sljedeće:

zamjena odnosa (operacija koja uključuje opterećujuće oporezivanje zamjenjuje se drugom, čime se postiže sličan cilj, ali se istovremeno koristi povlašteni porezni tretman).
podjela odnosa (zamjena samo dijela poslovne transakcije);
odgoda plaćanja poreza (odgoda trenutka pojave oporezivog predmeta na drugo kalendarsko razdoblje);
izravno smanjenje predmeta oporezivanja (oslobađanje od mnogih oporezivih transakcija ili imovine bez negativnog utjecaja na glavne gospodarske aktivnosti poduzeća).

5. Višedimenzionalna optimizacija

Linearno programiranje

Optimizacija je svrhovita aktivnost usmjerena na postizanje najboljih rezultata u odgovarajućim uvjetima.

Kvantitativna procjena kvalitete koja se optimizira naziva se kriterij optimalnosti ili ciljna funkcija .Može se napisati u obliku:

(5.1)

gdje je x 1, x 2, …, x n– neki parametri objekta optimizacije.

Postoje dvije vrste optimizacijskih problema – bezuvjetni i uvjetni.

Bezuvjetni zadatak optimizacija se sastoji u pronalaženju maksimuma ili minimuma realne funkcije (5.1).nrealne varijable i određivanje odgovarajućih vrijednosti argumenata.

Problemi uvjetne optimizacije , ili problemi s ograničenjima, su oni u čijoj se formulaciji ograničenja u obliku jednakosti ili nejednakosti nameću vrijednostima argumenata.

Rješavanje optimizacijskih problema u kojima je kriterij optimalnosti linearna funkcija neovisnih varijabli (odnosno sadrži te varijable do prvog stupnja) s linearnim ograničenjima na njih je predmet linearno programiranje.

Riječ "programiranje" ovdje odražava krajnji cilj studije - određivanje optimalnog plana ili optimalnog programa, prema kojem se od mnogih mogućih opcija za proces koji se proučava odabire najbolja, optimalna opcija na temelju nekog kriterija.

Primjer takav zadatak je problem optimalne raspodjele sirovina između različitih industrija uz maksimalne troškove proizvodnje.

Neka se iz dvije vrste sirovina naprave dvije vrste proizvoda.

Označimo: x 1 , x 2 – broj jedinica proizvoda prve, odnosno druge vrste; c 1 , c 2 – jedinična cijena proizvoda prve, odnosno druge vrste. Tada će ukupni trošak svih proizvoda biti:

(5.2)

Kao rezultat proizvodnje, poželjno je da ukupni trošak proizvodnje bude maksimiziran.R (x 1, x 2 ) je funkcija cilja u ovom problemu.

b 1, b 2 – količinu raspoloživih sirovina prve i druge vrste;a ij– broj jedinica ja -ta vrsta sirovine potrebna za proizvodnju jedinicej-tu vrstu proizvoda.

S obzirom da potrošnja pojedinog resursa ne može prijeći njegovu ukupnu količinu, zapisujemo restriktivne uvjete za resurse:

(5.3)

Što se tiče varijabli x 1, x 2 također možemo reći da su nenegativni i beskonačni:

(5.4)

Između mnogih rješenja sustava nejednadžbi (5.3) i (5.4) potrebno je pronaći takvo rješenje ( x 1, x 2 ), za koju je funkcijaRdostiže svoju najveću vrijednost.

U sličnom obliku formulirani su i tzv. transportni problemi (zadaci optimalne organizacije dopreme robe, sirovina ili proizvoda iz različitih skladišta na više odredišta uz minimalne troškove prijevoza) i niz drugih.

Grafička metoda za rješavanje problema linearnog programiranja.

Neka se traži pronaći x 1 i x 2 , zadovoljavajući sustav nejednakosti:

(5.5)

i uvjetima nenegativnost:

(5.6)

Za čija funkcija

(5. 7 )

doseže svoj maksimum.

Riješenje.

Konstruirajmo u sustavu pravokutnih koordinata x 1 x 2 područje mogućih rješenja problema (slika 11). Da bismo to učinili, zamjenjujući svaku od nejednakosti (5.5) jednakošću, konstruiramo relevantan njegova granična linija:

(ja = 1, 2, … , r)

Riža. jedanaest

Ova pravac dijeli cijelu ravninu na dvije poluravnine. Za koordinate x 1, x 2 bilo koja točka A jedne poluravnine vrijedi nejednakost:

a za koordinate bilo koje točke U druga poluravnina – suprotna nejednakost:

Koordinate bilo koje točke na graničnoj liniji zadovoljavaju jednadžbu:

Da bismo odredili s koje strane rubne crte se nalazi poluravnina koja odgovara zadanoj nejednadžbi, dovoljno je “testirati” jednu točku (najlakši način je točka OKO(0;0)). Ako je pri zamjeni svojih koordinata u lijevu stranu nejednadžbe ona zadovoljena, tada se poluravnina okreće prema točki koja se ispituje; ako nejednadžba nije zadovoljena, tada se odgovarajuća poluravnina okreće u suprotnom smjeru . Smjer poluravnine prikazan je na crtežu šrafiranom. nejednakosti:

odgovaraju poluravninama koje se nalaze desno od osi ordinata i iznad osi apscise.

Na slici konstruiramo rubne pravce i poluravnine koje odgovaraju svim nejednadžbama.

Zajednički dio (presjek) svih ovih poluravnina predstavljat će područje mogućih rješenja ovog problema.

Prilikom konstruiranja regije izvedivih rješenja, ovisno o specifičnoj vrsti sustava ograničenja (nejednakosti) na varijable, može se pojaviti jedan od sljedeća četiri slučaja:

Riža. 12. Područje izvodljivih rješenja je prazno, što odgovara nekonzistentnosti sustava nejednadžbi; nema rješenja

Riža. 13. Područje izvodljivih rješenja prikazano je jednom točkom A koja odgovara jedinom rješenju sustava

Riža. 14. Područje izvedivih rješenja je ograničeno i prikazano je kao konveksni poligon. Postoji beskonačan broj izvedivih rješenja

Riža. 15. Područje izvodljivih rješenja je neograničeno, u obliku konveksne poligonalne regije. Postoji beskonačan broj izvedivih rješenja

Grafički prikaz funkcije cilja

na fiksnu vrijednostRdefinira ravnu liniju, a pri promjeniR- obitelj paralelnih pravaca s parametromR. Za sve točke koje leže na jednom od pravaca, funkcija R uzima jednu određenu vrijednost, pa se nazivaju označene ravne linije linije razine za funkciju R.

Vektor gradijenta:

okomitolinijama razine, pokazuje smjer povećanjaR.

Problem nalaženja optimalnog rješenja sustava nejednadžbi (5.5), kojemu je funkcija ciljaR(5.7) dostiže maksimum, geometrijski se svodi na određivanje u području dopuštenih rješenja točke kroz koju će proći linija razine koja odgovara najvećoj vrijednosti parametraR

Riža. 16

Ako je područje mogućih rješenja konveksni mnogokut, tada je ekstrem funkcijeR se postiže barem u jednom od vrhova ovog poligona.

Ako je ekstremna vrijednostRse postiže na dva vrha, tada se ista ekstremna vrijednost postiže na bilo kojoj točki na segmentu koji povezuje ta dva vrha. U ovom slučaju se kaže da zadatak ima alternativni optimum .

U slučaju neograničene regije, ekstrem funkcijeRili ne postoji, ili se postiže na jednom od vrhova regije, ili ima alternativni optimum.

Primjer.

Pretpostavimo da trebamo pronaći vrijednosti x 1 i x 2 , zadovoljavajući sustav nejednakosti:

i uvjetima nenegativnost:

Za čija je funkcija:

doseže svoj maksimum.

Riješenje.

Zamijenimo svaku od nejednakosti jednakošću i konstruirajmo rubne crte:

Riža. 17

Odredimo poluravnine koje odgovaraju ovim nejednakostima "testiranjem" točke (0;0). Uzeti u obzir nenegativnost x 1 i x 2 dobivamo područje mogućih rješenja ovog problema u obliku konveksnog poligona OAVDE.

U području izvedivih rješenja optimalno rješenje nalazimo konstrukcijom vektora gradijenta

pokazivanjesmjer povećanjaR.

Optimalno rješenje odgovara točki U, čije se koordinate mogu odrediti ili grafički ili rješavanjem sustava dviju jednadžbi koje odgovaraju graničnim ravnim linijama AB i VD:

Odgovor: x 1 = 2; x 2 = 6; Rmax = 22.

Zadaci. Odredite položaj točke ekstrema i ekstremnu vrijednost funkcije cilja

pod zadanim ograničenjima.

Tablica 9
Opcija br.	Ekstremno	Ograničenja
	M sjekira	; ; ; ;
	Maks	; ; ; ;
		; ;
		; ; ; ;
		; ; ; ;
		; ;

Klasične metode optimizacije bez ograničenja

Uvod

Kao što je poznato, klasični problem neograničene optimizacije ima oblik:

Za rješavanje ovih problema postoje analitičke i numeričke metode.

Prije svega, podsjetimo se analitičkih metoda za rješavanje problema neograničene optimizacije.

Metode neograničene optimizacije zauzimaju značajno mjesto u tečajevima ML-a. To je zbog njihove izravne upotrebe u rješavanju niza optimizacijskih problema, kao iu implementaciji metoda za rješavanje značajnog dijela problema uvjetne optimizacije (MP problema).

1. Nužni uvjeti za lokalni minimalni (maksimalni) bod

Neka m daje minimalne vrijednosti funkcije. Poznato je da je u ovom trenutku prirast funkcije nenegativan, tj.

Pronađimo ga pomoću proširenja funkcije u Taylorov red u blizini m.

gdje je zbroj članova niza čiji je redoslijed relativan prema priraštajima (dva) i više.

Iz (4) jasno proizlazi da

Pretpostavimo onda

Uzimajući u obzir (6) imamo: . (7)

Pretpostavimo da je pozitivan, tj. . Izaberimo onda proizvod koji je u suprotnosti s (1).

Dakle, stvarno je očito.

Slično razmišljajući za druge varijable, dobivamo nužan uvjet za lokalne minimalne točke funkcije mnogih varijabli

Lako je dokazati da će za lokalnu točku maksimuma potrebni uvjeti biti potpuno isti kao i za lokalnu točku minimuma, tj. uvjeti (8).

Jasno je da će rezultat dokaza biti nejednakost oblika: - uvjet nepozitivnog prirasta funkcije u blizini lokalnog maksimuma.

Dobiveni potrebni uvjeti ne daju odgovor na pitanje je li stacionarna točka točka minimuma ili točka maksimuma.

Odgovor na ovo pitanje može se dobiti proučavanjem dovoljnih uvjeta. Ovi uvjeti podrazumijevaju proučavanje matrice drugih izvoda funkcije cilja.

2. Dovoljni uvjeti za lokalnu minimalnu (maksimalnu) točku

Predstavimo proširenje funkcije u okolini točke u Taylorovom nizu do kvadratnih članova.

Dekompozicija (1) može se ukratko prikazati pomoću pojmova: “skalarni umnožak vektora” i “vektorsko-matrični umnožak”.

Matrica dviju derivacija funkcije cilja prema odgovarajućim varijablama.

Povećanje funkcije na temelju (1") može se napisati kao:

Uzimajući u obzir potrebne uvjete:

Zamijenimo (3) u obliku:

Kvadratni oblik naziva se diferencijalni kvadratni oblik (DQF).

Ako je DCF pozitivno određen, tada je stacionarna točka također lokalna minimalna točka.

Ako su DCF i matrica koja ga predstavlja negativno određene, tada je stacionarna točka također točka lokalnog maksimuma.

Dakle, nužan i dovoljan uvjet za lokalnu minimalnu točku ima oblik

(ovi potrebni uvjeti mogu se napisati na sljedeći način:

Dovoljno stanje.

Prema tome, nužan i dovoljan uvjet za lokalni maksimum ima oblik:

Prisjetimo se kriterija koji nam omogućuje da odredimo jesu li kvadratna forma i matrica koja je predstavlja pozitivno određene ili negativno određene.

3. Sylvesterov kriterij

Omogućuje vam da odgovorite na pitanje: jesu li kvadratni oblik i matrica koja ga predstavlja pozitivno određeni ili negativno određeni.

Zove se Hessian matrica.

Glavna determinanta Hessianove matrice

a DCF koji predstavlja bit će pozitivno određen ako su sve glavne determinante Hessianove matrice () pozitivne (tj. vrijedi sljedeća shema znakova:

Ako postoji drugačija shema predznaka za glavne determinante Hessianove matrice, na primjer, tada su matrica i DCF negativno definirani.

4. Eulerova metoda - klasična metoda za rješavanje problema neograničene optimizacije

Ova se metoda temelji na nužnim i dovoljnim uvjetima proučavanim u 1.1 - 1.3; primjenjivo na pronalaženje lokalnih ekstrema samo kontinuiranih diferencijabilnih funkcija.

Algoritam za ovu metodu je prilično jednostavan:

1) pomoću potrebnih uvjeta formiramo sustav nelinearnih jednadžbi u općem slučaju. Napominjemo da je ovaj sustav nemoguće analitički riješiti u općem slučaju; potrebno je primijeniti numeričke metode za rješavanje sustava nelinearnih jednadžbi (NL) (vidi "FM"). Zbog toga će Eulerova metoda biti analitičko-numerička metoda. Rješavanjem navedenog sustava jednadžbi nalazimo koordinate stacionarne točke.;

2) proučavamo DCF i Hessianovu matricu koja ga predstavlja. Koristeći Sylvesterov kriterij, određujemo je li stacionarna točka točka minimuma ili točka maksimuma;

3) izračunati vrijednost funkcije cilja u ekstremnoj točki

Pomoću Eulerove metode riješite sljedeći problem neograničene optimizacije: pronađite 4 stacionarne točke funkcije oblika:

Saznajte prirodu ovih točaka, jesu li minimalne točke ili sedlaste točke (vidi). Konstruirati grafički prikaz ove funkcije u prostoru i ravnini (niveletama).

5. Klasični problem ograničene optimizacije i metode za njegovo rješavanje: Metoda eliminacije i Lagrangeova metoda množitelja (LML)

Kao što je poznato, klasični problem ograničene optimizacije ima oblik:

Graf koji objašnjava formulaciju problema (1), (2) u prostoru.

Jednadžbe linija razine

Dakle, ODR u problemu koji se razmatra je određena krivulja predstavljena jednadžbom (2").

Kao što se može vidjeti sa slike, točka je točka bezuvjetnog globalnog maksimuma; točka - točka uvjetnog (relativnog) lokalnog minimuma; točka - točka uvjetnog (relativnog) lokalnog maksimuma.

Problem (1"), (2") može se riješiti metodom eliminacije (supstitucije) rješavanjem jednadžbe (2") s obzirom na varijablu i zamjenom pronađenog rješenja (1").

Izvorni problem (1"), (2") se tako transformira u problem bezuvjetne optimizacije funkcije, koji se lako može riješiti Eulerovom metodom.

Metoda eliminacije (supstitucije).

Neka funkcija cilja ovisi o varijablama:

nazivaju se zavisne varijable (ili varijable stanja); prema tome, možete unijeti vektor

Preostale varijable nazivaju se varijablama neovisne odluke.

Prema tome, možemo govoriti o vektoru stupca:

i vektor.

U klasičnom problemu ograničene optimizacije:

Sustav (2), u skladu s metodom eliminacije (supstitucije), mora biti riješen s obzirom na ovisne varijable (varijable stanja), tj. Trebalo bi dobiti sljedeće izraze za zavisne varijable:

Je li sustav jednadžbi (2) uvijek rješiv u odnosu na ovisne varijable - nije uvijek moguće samo u slučaju kada je determinanta, koja se naziva jakobijan, čiji elementi imaju oblik:

nije jednako nuli (vidi odgovarajući teorem u MA tečaju)

Kao što se može vidjeti, funkcije moraju biti kontinuirane diferencijabilne funkcije; drugo, elementi determinante moraju se izračunati u stacionarnoj točki funkcije cilja.

Zamjenom iz (3) u funkciju cilja (1) imamo:

Proučavana funkcija može se dovesti do ekstrema Eulerovom metodom - metodom bezuvjetne optimizacije kontinuirano diferencijabilne funkcije.

Dakle, metoda eliminacije (supstitucije) omogućuje vam korištenje klasičnog uvjetnog optimizacijskog problema za njegovu transformaciju u bezuvjetni optimizacijski problem funkcije - funkcije varijabli pod uvjetom (4), što vam omogućuje da dobijete sustav izraza (3 ).

Nedostatak metode isključenja: teškoće, a ponekad i nemogućnost dobivanja sustava izraza (3). Bez ovog nedostatka, ali zahtijeva ispunjenje uvjeta (4) je MML.

5.2. Lagrangeova metoda multiplikatora. Nužni uvjeti u klasičnom problemu ograničene optimizacije. Lagrangeova funkcija

MML dopušta izvorni problem klasične ograničene optimizacije:

Pretvorite u problem neograničene optimizacije posebno konstruirane funkcije - Lagrangeove funkcije:

gdje su Lagrangeovi multiplikatori;

Kao što vidite, to je zbroj koji se sastoji od izvorne ciljne funkcije i "ponderiranog" zbroja funkcija - funkcija koje predstavljaju njihova ograničenja (2) izvornog problema.

Neka je točka bezuvjetna točka ekstrema funkcije, tada, kao što je poznato, ili (ukupni diferencijal funkcije u točki).

Korištenje pojma zavisne i nezavisne varijable - zavisne varijable; - nezavisne varijable, tada prikazujemo (5) u proširenom obliku:

Iz (2) očito slijedi sustav jednadžbi oblika:

Rezultat izračuna ukupnog diferencijala za svaku od funkcija

Predstavimo (6) u “proširenom” obliku koristeći koncept zavisnih i nezavisnih varijabli:

Imajte na umu da je (6"), za razliku od (5"), sustav koji se sastoji od jednadžbi.

Pomnožimo svaku jednadžbu sustava (6") s odgovarajućim Lagrangeovim množiteljem. Zbrojimo ih zajedno i s jednadžbom (5") i dobijemo izraz:

Posložimo Lagrangeove multiplikatore tako da izraz u uglatim zagradama ispod predznaka prvog zbroja (drugim riječima, koeficijenata diferencijala nezavisnih varijabli) bude jednak nuli.

Izraz "odlaganje" Lagrangeovih multiplikatora na gornji način znači da je potrebno riješiti neki sustav jednadžbi za.

Struktura takvog sustava jednadžbi može se lako dobiti izjednačavanjem izraza u uglatim zagradama ispod prvog znaka zbroja s nulom:

Prepišimo (8) u obliku

Sustav (8") je sustav linearnih jednadžbi u odnosu na poznato: . Sustav je rješiv ako (zato, kao i kod metode eliminacije u ovom slučaju, uvjet mora biti zadovoljen). (9)

Kako je u ključnom izrazu (7) prvi zbroj jednak nuli, lako je razumjeti da će i drugi zbroj biti jednak nuli, tj. ima mjesto sljedeći sustav jednadžbi:

Sustav jednadžbi (8) sastoji se od jednadžbi, a sustav jednadžbi (10) sastoji se od jednadžbi; ukupne jednadžbe u dva sustava i nepoznanice

Jednadžbe koje nedostaju dane su sustavom jednadžbi ograničenja (2):

Dakle, postoji sustav jednadžbi za pronalaženje nepoznanica:

Dobiveni rezultat - sustav jednadžbi (11) - čini glavni sadržaj MML-a.

Lako je razumjeti da se sustav jednadžbi (11) može vrlo jednostavno dobiti uvođenjem u razmatranje posebno konstruirane Lagrangeove funkcije (3).

Stvarno

Dakle, sustav jednadžbi (11) može se prikazati kao (koristeći (12), (13)):

Sustav jednadžbi (14) predstavlja nužan uvjet u klasičnom problemu ograničene optimizacije.

Vektorska vrijednost pronađena kao rezultat rješavanja ovog sustava naziva se uvjetno stacionarna točka.

Da bismo saznali prirodu uvjetno stacionarne točke, potrebno je koristiti dovoljno uvjeta.

5.3 Dovoljni uvjeti u klasičnom problemu ograničene optimizacije. MML algoritam

Ovi uvjeti omogućuju da se utvrdi je li uvjetno stacionarna točka točka lokalnog uvjetnog minimuma ili točka lokalnog uvjetnog maksimuma.

Relativno jednostavno, slično kao što su dovoljni uvjeti dobiveni u problemu bezuvjetnog ekstremuma. Također je moguće dobiti dovoljne uvjete u klasičnom problemu ograničene optimizacije.

Rezultat ove studije:

gdje je točka lokalnog uvjetnog minimuma.

gdje je točka lokalnog uvjetnog maksimuma, je Hessova matrica s elementima

Hessian matrica ima dimenziju.

Dimenzija Hessove matrice može se reducirati korištenjem uvjeta da Jacobian nije nula: . Pod ovim uvjetom, ovisne varijable mogu se izraziti kroz nezavisne varijable, tada će Hessova matrica imati dimenziju, tj. moramo govoriti o matrici s elementima

tada će dovoljni uvjeti izgledati ovako:

Lokalna uvjetna minimalna točka.

Lokalna uvjetna maksimalna točka.

Dokaz: MML Algoritam:

1) sastaviti Lagrangeovu funkciju: ;

2) koristeći potrebne uvjete, formiramo sustav jednadžbi:

3) iz rješenja ovog sustava nalazimo točku;

4) pomoću dovoljnih uvjeta utvrđujemo je li točka točka lokalnog uvjetnog minimuma ili maksimuma, zatim nalazimo

1.5.4. Grafičko-analitička metoda za rješavanje klasičnog problema ograničene optimizacije u prostoru i njezina modifikacija pri rješavanju najjednostavnijih IP i AP problema

Ova metoda koristi geometrijsku interpretaciju problema klasične ograničene optimizacije i temelji se na nizu važnih činjenica svojstvenih ovom problemu.

B je zajednička tangenta za funkciju i funkciju koja predstavlja ODR.

Kao što se može vidjeti sa slike, točka je točka bezuvjetnog minimuma, točka je točka uvjetnog lokalnog minimuma, točka je točka uvjetnog lokalnog maksimuma.

Dokažimo da u točkama uvjetnih lokalnih ekstrema krivulja i odgovarajuće linije razine

Iz MA kolegija je poznato da je na mjestu kontakta uvjet zadovoljen

gdje je kutni koeficijent tangente povučene odgovarajućom nivelacijom; - kutni koeficijent tangente povučene na funkciju

Poznat je izraz (MA) za ove koeficijente:

Dokažimo da su ti koeficijenti jednaki.

jer o tome “govore” potrebni uvjeti

Gore navedeno nam omogućuje da formuliramo GFA algoritam za rješavanje problema klasične ograničene optimizacije:

1) izgradite obitelj linija razine funkcije cilja:

2) konstruirajte ODD koristeći jednadžbu ograničenja

3) da bismo ispravili povećanje funkcije, nalazimo i razjašnjavamo prirodu ekstremnih točaka;

4) proučavamo interakciju linija razine i funkcija, dok iz sustava jednadžbi pronalazimo koordinate uvjetno stacionarnih točaka - lokalnih uvjetnih minimuma i lokalnih uvjetnih maksimuma.

5) izračunati

Posebno treba napomenuti da se glavne faze GFA metode za rješavanje problema klasične uvjetne optimizacije poklapaju s glavnim fazama GFA metode za rješavanje LP i LP problema, jedina razlika je u ODR-u, kao iu pronalaženju položaj ekstremnih točaka u ODD (na primjer, u LP problemima te točke nužno se nalaze na vrhovima konveksnog poligona koji predstavlja ODR).

5.5. O praktičnom značenju MML-a

Zamislimo klasični problem ograničene optimizacije kao:

gdje su varijabilne količine koje predstavljaju varijabilne resurse u primijenjenim tehničkim i ekonomskim problemima.

U prostoru problem (1), (2) ima oblik:

gdje je varijabilna veličina. (2")

Neka je uvjetna točka ekstrema:

Prilikom mijenjanja promjena

Vrijednost funkcije cilja će se promijeniti u skladu s tim:

Izračunajmo derivaciju:

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

Zamijenite (5") u (3) i dobijete:

Iz (6) Lagrangeov multiplikator karakterizira vrijednost "reakcije" (ortogonalno na vrijednost funkcije cilja) na promjene parametra.

U općem slučaju (6) ima oblik:

Iz (6), (7), množitelj karakterizira promjenu kada se odgovarajući resurs promijeni za 1.

Ako je maksimalni profit ili minimalni trošak, tada karakterizira promjene ove vrijednosti kada se promijeni za 1.

5.6. Klasični problem ograničene optimizacije, kao problem nalaženja sedla Lagrangeove funkcije:

Par se naziva sedlom točkom ako nejednakost vrijedi.

Očito je da iz (1). (2)

Iz (2), to. (3)

Kao što vidite, sustav (3) sadrži jednadžbe slične onim jednadžbama koje predstavljaju nužan uvjet u klasičnom problemu ograničene optimizacije:

gdje je Lagrangeova funkcija.

U vezi s analogijom sustava jednadžbi (3) i (4), klasični problem ograničene optimizacije može se smatrati problemom pronalaženja sedla Lagrangeove funkcije.

Slični dokumenti

Višedimenzionalni optimizacijski problemi u proučavanju tehnoloških procesa u tekstilnoj industriji, analiza pojavnih poteškoća. Određivanje ekstrema, vrsta ekstrema, vrijednost funkcije cilja neograničene višedimenzionalne optimizacije.

test, dodan 26.11.2011

Obilježja klasičnih metoda neograničene optimizacije. Određivanje potrebnog i dovoljnog uvjeta postojanja ekstrema funkcija jedne i više varijabli. Lagrangeovo pravilo množitelja. Potrebni i dovoljni uvjeti optimalnosti.

kolegij, dodan 13.10.2013

Metodologija i značajke rješavanja optimizacijskih problema, posebice o raspodjeli ulaganja i izboru putanje u prometnoj mreži. Specifičnosti modeliranja metodama Hamminga i Browna. Identifikacija, stimulacija i motivacija kao funkcije upravljanja.

test, dodan 12.12.2009

Prikaz, analiza, grafičko rješavanje problema linearne optimizacije, simpleks metoda, dualnost u linearnoj optimizaciji. Postavka prometnog problema, svojstva i pronalaženje referentnog rješenja. Uvjetna optimizacija pod ograničenjima jednakosti.

priručnik za obuku, dodan 07/11/2010

Kritični put u grafu. Optimalna raspodjela protoka u prometnoj mreži. Problem linearnog programiranja riješen grafički. Problem neuravnoteženog transporta. Numeričke metode za rješavanje jednodimenzionalnih problema statičke optimizacije.

kolegij, dodan 21.06.2014

Grafička metoda rješavanja problema optimizacije proizvodnih procesa. Primjena simpleks algoritma za rješavanje ekonomski optimiziranog problema upravljanja proizvodnjom. Metoda dinamičkog programiranja za odabir optimalnog profila staze.

test, dodan 15.10.2010

Optimizacijske metode za rješavanje ekonomskih problema. Klasična formulacija optimizacijskog problema. Optimizacija funkcija. Optimizacija funkcionalnosti. Višekriterijska optimizacija. Metode redukcije višekriterijskog problema na jednokriterijski. Metoda koncesija.

sažetak, dodan 20.06.2005

Primjena metoda nelinearnog programiranja za rješavanje problema s nelinearnim funkcijama varijabli. Uvjeti optimalnosti (Kuhn-Tuckerov teorem). Metode uvjetne optimizacije (Wolfe metoda); dizajn gradijenta; kaznene i zaprečne funkcije.

sažetak, dodan 25.10.2009

Pojam, definicija, isticanje značajki, mogućnosti i karakteristika postojećih problema višekriterijske optimizacije i načina njihovog rješavanja. Proračun metode jednakih i najmanjih odstupanja višekriterijske optimizacije i njezina primjena u praksi.

kolegij, dodan 21.01.2012

Osnovni pojmovi modeliranja. Opći pojmovi i definicija modela. Postavljanje optimizacijskih problema. Metode linearnog programiranja. Opći i tipični problem linearnog programiranja. Simpleksna metoda za rješavanje problema linearnog programiranja.

Od metoda optimizacije nultog reda u CAD-u koriste se metode Rosenbrocka, konfiguracija, deformabilnog poliedra i slučajnog pretraživanja. Metode koje koriste izvedenice uključuju metode najvećeg spuštanja, konjugiranog gradijenta i varijabilne metričke metode.

Rosenbrockova metoda je poboljšana verzija koordinatnog spuštanja.

Metoda koordinatnog spuštanja karakterizira izbor smjerova pretraživanja naizmjenično duž svih koordinatnih osi, korak se izračunava na temelju jednodimenzionalne optimizacije, kriterij za završetak pretraživanja je , gdje je navedena točnost određivanja lokalnog ekstremuma, je dimenzija prostor kontroliranih parametara. Koordinatna putanja spuštanja za primjer dvodimenzionalnog prostora kontroliranih parametara prikazana je na slici. 1, gdje su točke na trajektoriji pretraživanja i kontrolirani parametri. Funkcija cilja je prikazana svojim linijama jednakih razina, a uz svaku crtu ispisana je odgovarajuća vrijednost. Očito postoji minimalna točka.

Riža. 1. Putanja koordinatnog spuštanja

Kada koristite metodu koordinatnog spuštanja, postoji velika vjerojatnost da će pretraga zapeti na dnu klanca daleko od ekstremne točke. Na sl. 2 pokazuje da su nakon udaranja u točku koja se nalazi na dnu jaruge daljnji koraci mogući samo u smjerovima ili , ali dovode do pogoršanja funkcije cilja. Stoga se pretraga zaustavlja na točki .

Napomena 1

Jaruga je dio prostora kontroliranih parametara u kojem se u nekim smjerovima uočavaju slabe promjene izvodnica funkcije cilja, au nekim drugim značajne promjene s promjenom predznaka. Predznak derivacije mijenja se u točkama koje pripadaju dnu jaruge.

Riža. 3. Trajektorija koordinatnog spuštanja s povoljnom orijentacijom koordinatnih osi

Rosenbrockova metoda sastoji se u rotaciji koordinatnih osi tako da se jedna od njih pokaže kvaziparalelnom s dnom jaruge. Ova rotacija se provodi na temelju podataka dobivenih nakon niza koraka spuštanja koordinata. Položaj novih osi može se dobiti linearnom transformacijom prethodnih osi: os se poklapa u smjeru s vektorom; preostale osi su odabrane iz uvjeta ortogonalnosti jedna prema drugoj.

Još jedna uspješna modifikacija koordinatnog spuštanja je način konfiguracije(Hook-Jeeves). U skladu s ovom metodom, prvo se izvodi uobičajeni niz koraka koordinatnog spuštanja, zatim se radi dodatni korak u smjeru vektora, kao što je prikazano na sl. 4, gdje se izvodi dodatni korak u smjeru vektora, koji vodi do točke .

Riža. 4. Ilustracija metode konfiguracije

Potraga za ekstremom metoda deformabilnog poliedra(Nelder-Mead) temelji se na konstrukciji poliedra s vrhovima na svakom koraku pretraživanja, gdje je dimenzija prostora kontroliranih parametara. Na početku pretraživanja, ovi se vrhovi biraju nasumično; u sljedećim koracima odabir je podložan pravilima metode.

Ova su pravila objašnjena na sl. 5 na primjeru problema dvodimenzionalne optimizacije. Odabrani su vrhovi izvornog trokuta: , , . Novi vrh nalazi se na zraki povučenoj iz najlošijeg vrha (iz vrha s najvećom vrijednošću funkcije cilja) kroz težište poliedra, a preporuča se odabrati udaljenost od , jednaku . Novi vrh zamjenjuje najgori vrh. Ako se pokaže da ima najbolju vrijednost funkcije cilja među vrhovima poliedra, tada se udaljenost povećava. Na slici se događa upravo takva situacija i povećanje daje poantu. U novom poliedru s vrhovima , , najgori je vrh , slično se dobije vrh , pa vrh itd. Ako se novi vrh pokaže lošijim, tada se u poliedru mora sačuvati najbolji vrh, a duljine svih bridova smanjiti, na primjer, za pola (kontrahiranje poliedra na najbolji vrh). Pretraga se zaustavlja kada se ispuni uvjet smanjenja veličine poliedra na određenu granicu.

optimalni korak odabire se pomoću jednodimenzionalne optimizacije.

Pri korištenju metode najstrmijeg spuštanja, kao i kod većine drugih metoda, učinkovitost pretraživanja značajno je smanjena u situacijama s vododerinama. Trajektorija potrage poprima cik-cak oblik s polaganim kretanjem po dnu jaruge prema ekstremumu. Za povećanje učinkovitosti gradijentnih metoda koristi se nekoliko tehnika.

Jedna od tehnika koja se koristi u metoda konjugiranog gradijenta(također nazvana Fletcher-Reevesova metoda), temelji se na konceptu konjugacije vektora. Vektori i nazivaju se -konjugirani ako je , gdje je pozitivno određena kvadratna matrica istog reda kao veličina vektora i (poseban slučaj konjugacije je ortogonalnost vektora, kada je matrica identiteta reda ), redak vektor, je vektor stupac.

Osobitost konjugiranih pravaca za , gdje je Hessova matrica, u problemima s kvadratnom ciljnom funkcijom je sljedeća: jednodimenzionalna minimizacija sekvencijalno duž konjugiranih pravaca omogućuje pronalaženje ekstremne točke u ne više od koraka.

Napomena 2

Hessian matrica je matrica drugih parcijalnih derivacija funkcije cilja u odnosu na kontrolirane parametre.

Razlog korištenja pretraživanja u -konjugiranim smjerovima je taj što se za funkcije () općeg oblika može primijeniti kvadratna aproksimacija, što u praksi rezultira izvođenjem pretraživanja u više od koraka.

Potraga za ekstremom provodi se prema formuli

gdje je koeficijent. Osim toga, u obzir se uzima uvjet konjugacije

Budući da se korak izračunava na temelju uvjeta jednodimenzionalne optimizacije, tada je, prvo, istinita sljedeća relacija:

Algoritam pretraživanja svodi se na primjenu formule (3) dok se ne ispuni uvjet za dovršetak izračuna

Za određivanje koeficijenta riješite sustav jednadžbi (2)-(7) tako da u (4) zamijenite vrijednosti iz (3) i iz (2):

ili

gdje

i uzimajući u obzir (6) i (7)

Izraz (10) je sustav linearnih algebarskih jednadžbi. Njegov korijen je još jedna aproksimacija rješenja

Ako proces konvergira, tada se rješenje postiže u malom broju iteracija, čiji je kraj ispunjenje uvjeta
Gdje

Zato

Može se pokazati da teži , - kada je , gdje je dimenzija prostora kontroliranih parametara. Nakon koraka morate ponovno krenuti od .

Optimizacija je proces pronalaženja ekstremuma (globalnog maksimuma ili minimuma) određene funkcije ili odabira najbolje (optimalne) opcije iz skupa mogućih. Najpouzdaniji način pronalaska najbolje opcije je usporedna procjena svih mogućih opcija (alternativa). Ako je broj alternativa velik, obično se koriste metode matematičkog programiranja kako bi se pronašla najbolja. Ove se metode mogu primijeniti ako postoji striktna formulacija problema: zadan je skup varijabli, utvrđeno je područje njihove moguće promjene (navedena su ograničenja) i tip funkcije cilja (funkcija čiji je ekstremum treba pronaći) iz ovih varijabli se određuje. Potonji je kvantitativno mjerilo (kriterij) za ocjenu stupnja ostvarenja cilja.

Problem neograničene optimizacije je pronaći minimum ili maksimum funkcije u nedostatku bilo kakvih ograničenja. Iako većina praktičnih problema optimizacije sadrži ograničenja, učenje metoda optimizacije bez ograničenja važno je s nekoliko točaka gledišta. Mnogi algoritmi za rješavanje ograničenog problema uključuju njegovo svođenje na niz neograničenih optimizacijskih problema. Druga klasa metoda temelji se na pronalaženju prikladnog smjera i zatim minimiziranju u tom smjeru. Opravdanost metoda optimizacije bez ograničenja može se prirodno proširiti na opravdanost postupaka za rješavanje problema s ograničenjima.

Problem ograničene optimizacije je pronaći minimalnu ili maksimalnu vrijednost skalarne funkcije f(x) n-dimenzionalnih vektorskih argumenata. Rješenje problema temelji se na linearnoj ili kvadratnoj aproksimaciji funkcije cilja za određivanje inkremenata x1, ..., xn u svakoj iteraciji. Postoje i približne metode za rješavanje nelinearnih problema. To su metode koje se temelje na metodi komadno-linearne aproksimacije. Točnost pronalaženja rješenja ovisi o broju intervala na kojima nalazimo rješenje linearnog problema koje je što bliže nelinearnom. Ova metoda omogućuje izračune koristeći simpleks metodu. Tipično, u linearnim modelima, koeficijenti funkcije cilja su konstantni i ne ovise o vrijednostima varijabli. Međutim, postoji niz problema kod kojih troškovi nelinearno ovise o obujmu.

Algoritam rješenja:

1. Rad počinje konstruiranjem regularnog simpleksa u prostoru neovisnih varijabli i procjenom vrijednosti funkcije cilja na svakom od vrhova simpleksa.
2. Određuje se vrh – najveća vrijednost funkcije.
3. Vrh se projicira kroz težište preostalih vrhova u novu točku, koja se koristi kao vrh novog simpleksa.
4. Ako funkcija opada dovoljno glatko, iteracije se nastavljaju sve dok se ne pokrije točka min ili ne započne cikličko kretanje duž 2 ili više simpleksa.
5. Pretraga završava kada dimenzije simpleksa ili razlike između vrijednosti funkcije na vrhovima ostanu dovoljno male.

Zadatak: optimizacija kapaciteta. Ostvarite minimalne troškove za izradu spremnika od 2750 litara za skladištenje pijeska.

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

gdje je: X1 - količina potrebnog metala, kg;

C1 - trošak metala, rub / kg;

X2 - masa potrebnih elektroda, kg;

C2 - trošak elektroda, rub / kg;

X3 - količina potrošene električne energije, kWh;

C3 - trošak električne energije, rub / kWh;

X4 - radno vrijeme zavarivača, h;

C4 - tarifna stopa zavarivača, rub / sat;

X5 - vrijeme rada dizala, h;

C5 - naknada za podizanje, rub./sat.

1. Pronađite optimalnu površinu spremnika:

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

gdje je V=2750 litara.

x1=16,331; x2=10,99

Minimum funkcije dobiven je u procesu optimizacije Box metodom - 1196,065 dm2

U skladu s GOST 19903 - 74, prihvaćamo:

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

Izrazimo a iz (1) i dobijemo:

Izračunajmo optimalnu debljinu metalnog lima

Odaberimo obični ugljični čelik St2sp

Za ovaj čelik 320 MPa, ;

Masa pijeska.

Opterećenje na stjenku posude najveće površine:

Izračunajmo opterećenje po 1 linearnom centimetru lista širine 100 cm:

Odredimo debljinu stijenke na temelju uvjeta:

gdje je: l duljina lista (po mogućnosti najduža kako bi se ostavila dodatna granica sigurnosti);

q - opterećenje po 1 linearnom centimetru, kg / cm;

Debljina metalnog lima, m

Najveće dopušteno naprezanje metala, N/mm2.

Izrazimo debljinu stijenke iz (2):

Uzimajući u obzir da je 320 MPa = 3263 kg/cm2,

Metalna masa

gdje je: F - površina spremnika, m2;

Debljina metalne stijenke, m;

Gustoća metala, kg / m3.

Cijena St2sp čelika je oko 38 rubalja / kg.

2. Duljina zavara:

Koristit ćemo elektrode za nehrđajući čelik “UONI-13/45”

Cijena 88,66 rub / kg;

gdje je: Zavar - površina poprečnog presjeka zavara, m2;

l je duljina zavara, m;

Gustoća nataloženog metala, kg/m3.

3. Vrijeme zavarivanja:

gdje je l duljina zavara, m;

v - brzina zavarivanja, m / h.

Ukupna potrošnja energije:

Rsum = 5 17 = 85 kWh;

Trošak električne energije je 5,7 rubalja/kWh.

4. Za ručno elektrolučno zavarivanje troškovi pomoćnog, pripremnog i završnog vremena i vremena za servisiranje radnog mjesta iznose u prosjeku 40 - 60%. Uzmimo prosječnu vrijednost od 50%.

Ukupno vrijeme:

Plaćanje zavarivača VI kategorije je 270 rubalja / sat.

Plus tarifni koeficijent od 17% za rad u zatvorenom, slabo prozračenom prostoru:

Plaćanje pomoćnika bit će 60% plaćanja zavarivača:

8055 0,6 = 4833 rub.

Ukupno: 8055+4833 = 12888 rubalja.

5. Dizalica je potrebna za držanje limova tijekom zavarivanja, utovara i istovara limova i samog spremnika.

Da bi "zgrabio" cijelu strukturu, zavarivač treba primijeniti oko 30% šavova.

Plaćanje dizalice je 1000 rubalja / sat.

Ukupna cijena kontejnera.