Metode slučajnog pretraživanja. Metode neograničene optimizacije

5. Višedimenzionalna optimizacija

Linearno programiranje

Optimizacija je svrsishodna aktivnost koja ima za cilj postizanje najboljih rezultata u odgovarajućim uslovima.

Kvantitativna procjena kvaliteta koji se optimizira naziva se kriterijum optimalnosti ili ciljna funkcija .Može se napisati u obliku:

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

Postoje dvije vrste problema optimizacije – bezuslovni i uslovni.

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

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

Predmet je rješavanja optimizacijskih problema u kojima je kriterij optimalnosti linearna funkcija nezavisnih varijabli (odnosno, sadrži ove varijable do prvog stepena) sa linearnim ograničenjima na njih. linearno programiranje.

Riječ "programiranje" ovdje odražava krajnji cilj studije - utvrđivanje optimalnog plana ili optimalnog programa prema kojem, između mnogih moguće opcije od procesa koji se proučava, najbolja, optimalna opcija se bira na osnovu nekog kriterijuma.

Primjer takav zadatak je problem optimalne distribucije sirovina između različitih industrija uz maksimalnu cijenu proizvodnje.

Neka se od dvije vrste sirovina prave dvije vrste proizvoda.

Označimo: x 1 , x 2 – broj jedinica proizvoda prve i druge vrste; c 1 , c 2 – jedinična cijena proizvoda prve i druge vrste, respektivno. Tada će ukupna cijena svih proizvoda biti:

Kao rezultat proizvodnje, poželjno je da ukupni troškovi proizvodnje budu maksimizirani.R (x 1, x 2 ) je ciljna funkcija u ovom problemu.

b 1, b 2 – količina raspoloživih sirovina prve i druge vrste;a ij– broj jedinica i -th vrsta sirovine potrebne za proizvodnju jedinicej-ti tip proizvoda.

S obzirom da potrošnja datog resursa ne može premašiti njegovu ukupnu količinu, zapisujemo restriktivne uslove za resurse:

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

Među mnogim rješenjima sistema nejednačina (5.3) i (5.4) potrebno je pronaći takvo rješenje ( x 1 , x 2 ), za koje je funkcijaRdostiže svoju najveću vrijednost.

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

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

Neka se traži da se pronađe x 1 i x 2 , zadovoljavajući sistem nejednakosti:

i uslove nenegativnost:

Za čija funkcija

dostiže svoj maksimum.

Rješenje.

Konstruirajmo u sistemu pravougaonih koordinata x 1 x 2 područje izvodljivih 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:

(i = 1, 2, … , r)

Rice. jedanaest

Ova prava linija dijeli cijelu ravan na dvije poluravnine. Za koordinate x 1 , x 2 bilo koje tačke A jednoj poluravni vrijedi sljedeća nejednakost:

i za koordinate bilo koje tačke IN druga poluravnina – suprotna nejednakost:

Koordinate bilo koje tačke na graničnoj liniji zadovoljavaju jednačinu:

Da bi se utvrdilo na kojoj strani granične linije se nalazi poluravnina koja odgovara datoj nejednakosti, dovoljno je "testirati" jednu tačku (najlakši način je tačka O(0;0)). Ako, prilikom zamjene njegovih koordinata u lijeva strana Ako je nejednakost zadovoljena, tada se poluravnina okreće prema tački koja se testira, ako nejednakost nije zadovoljena, tada se odgovarajuća poluravnina okreće u suprotnom smjeru. Smjer poluravnine prikazan je na crtežu šrafiranjem. nejednakosti:

odgovaraju poluravni koje se nalaze desno od ordinatne ose i iznad ose apscise.

Na slici konstruišemo granične prave i poluravnine koje odgovaraju svim nejednačinama.

Zajednički dio (presjek) svih ovih poluravni predstavljaće područje izvodljivih rješenja ovog problema.

Prilikom konstruisanja regiona izvodljivih rešenja, u zavisnosti od specifičnog tipa sistema ograničenja (nejednakosti) na varijable, može se pojaviti jedan od sledeća četiri slučaja:

Rice. 12. Područje izvodljivih rješenja je prazno, što odgovara nekonzistentnosti sistema nejednačina; nema rješenja

Rice. 13. Područje izvodljivih rješenja predstavljeno je jednom tačkom A, koja odgovara jedinom rješenju sistema

Rice. 14. Područje izvodljivih rješenja je ograničeno i prikazano je kao konveksan poligon. Postoji beskonačan broj izvodljivih rješenja

Rice. 15. Područje izvodljivih rješenja je neograničeno, u obliku konveksnog poligonalnog područja. Postoji beskonačan broj izvodljivih rješenja

Grafički prikaz funkcije cilja

po fiksnoj vrijednostiRdefiniše pravu liniju, a kada se mijenjaR- familija paralelnih linija sa parametromR. Za sve tačke koje leže na jednoj od pravih, funkcija R uzima jednu određenu vrijednost, pa se označene prave linije pozivaju linije nivoa za funkciju R.

Vektor gradijenta:

okomitodo linija nivoa, pokazuje smjer porastaR.

Problem nalaženja optimalnog rješenja sistema nejednačina (5.5) za koji je ciljna funkcijaR(5.7) dostiže maksimum, geometrijski se svodi na određivanje u području dopuštenih rješenja tačke kroz koju će proći linija nivoa koja odgovara najvećoj vrijednosti parametraR

Rice. 16

Ako je područje izvodljivih rješenja konveksan poligon, onda je ekstremum funkcijeR je postignut barem na jednom od vrhova ovog poligona.

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

U slučaju neograničenog područja, ekstremum funkcijeRili ne postoji, ili se postiže na jednom od vrhova regiona, ili ima alternativni optimum.

Primjer.

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

i uslove nenegativnost:

Za čija je funkcija:

dostiže svoj maksimum.

Rješenje.

Zamijenimo svaku od nejednakosti jednakošću i konstruirajmo granične linije:

Rice. 17

Odredimo poluravnine koje odgovaraju ovim nejednačinama “testiranjem” tačke (0;0). Uzimajući u obzir nenegativnost x 1 i x 2 dobijamo oblast izvodljivih rešenja ovog problema u obliku konveksnog poligona OAVDE.

U području izvodljivih rješenja pronalazimo optimalno rješenje konstruiranjem vektora gradijenta

pokazujućismjeru povećanjaR.

Optimalno rješenje odgovara tački IN, čije se koordinate mogu odrediti grafički ili rješavanjem sistema od dvije jednadžbe koje odgovaraju graničnim pravim linijama AB i VD:

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

Zadaci. Odrediti položaj tačke ekstrema i ekstremnu vrijednost funkcije cilja

pod datim ograničenjima.

Optimalnom se smatra najprihvatljivija opcija odluke koja se donosi na menadžerskom nivou u vezi sa bilo kojim pitanjem, a proces traženja za njom optimizacijom.

Međuzavisnost i složenost organizacionih, socio-ekonomskih, tehničkih i drugih aspekata upravljanja proizvodnjom trenutno se svodi na donošenje upravljačke odluke koja utiče na veliki broj različitih faktora koji su međusobno usko isprepleteni, što onemogućava analizu svakog pojedinačno. koristeći tradicionalne analitičke metode.

Većina faktora je odlučujuća u procesu donošenja odluka i oni se (inherentno) ne mogu kvantificirati. Ima i onih koji su praktično nepromijenjeni. S tim u vezi, pojavila se potreba za razvojem posebnih metoda koje bi mogle osigurati odabir važnih upravljačkih odluka u okviru složenih organizacionih, ekonomskih, tehničkih problema (stručne procjene, operativno istraživanje i metode optimizacije itd.).

Za pretragu se koriste metode usmjerene na istraživanje operacija optimalna rješenja u oblastima menadžmenta kao što su organizovanje proizvodnih i transportnih procesa, planiranje proizvodnje velikih razmera, materijalno-tehničko snabdevanje.

Metode za optimizaciju rješenja uključuju istraživanje upoređivanjem numeričkih procjena niza faktora, čija analiza tradicionalne metode nemoguće implementirati. Optimalno rješenje je najbolje među mogućim opcijama u pogledu ekonomskog sistema, a najprihvatljivije u odnosu na pojedine elemente sistema je suboptimalno.

Suština metoda istraživanja operacija

Kao što je ranije spomenuto, oni formiraju metode za optimizaciju upravljačkih odluka. Njihova osnova su matematički (deterministički), probabilistički modeli koji predstavljaju proces, vrstu aktivnosti ili sistem koji se proučava. Ovaj tip 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.

Spisak pitanja koja igraju značajnu ulogu za direktne rukovodioce proizvodnje i koja se rešavaju tokom upotrebe razmatranih metoda:

• stepen valjanosti izabranih opcija odluke;
• koliko su one bolje od alternativa;
• stepen uvažavanja odlučujućih faktora;
• koji je kriterij optimalnosti odabranih rješenja.

Ove metode optimizacije odlučivanja (menadžerske) imaju za cilj pronalaženje optimalnih rješenja za što više više firme, kompanije ili njihove divizije. Zasnovani su na postojećim dostignućima u statističkim, matematičkim i ekonomskim disciplinama (teorija igara, red čekanja, grafika, optimalno programiranje, matematička statistika).

Metode stručne procjene

Ove metode za optimizaciju upravljačkih odluka koriste se kada problem djelomično ili u potpunosti nije podvrgnut 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 konkretne upravljačke odluke od strane relevantnih osoba koje imaju posebnu bazu znanja i impresivno iskustvo u cilju dobijanja zaključaka, preporuka, mišljenja i procjena. U procesu stručnog istraživanja koriste se najnovija dostignuća i nauke i tehnologije u okviru stručne specijalizacije.

Razmatrane metode za optimizaciju niza upravljačkih odluka (stručne procjene) efikasne su u rješavanju sljedećih upravljačkih zadataka u oblasti proizvodnje:

1. Proučavanje složenih procesa, pojava, situacija, sistema koje karakterišu neformalne, kvalitativne karakteristike.
2. Rangiranje i određivanje, prema datom kriterijumu, značajnih faktora koji su odlučujući za funkcionisanje i razvoj proizvodnog sistema.
3. Metode optimizacije koje se razmatraju posebno su efikasne u predviđanju trendova u razvoju proizvodnog sistema, kao i njegove interakcije sa spoljnim okruženjem.
4. Povećanje pouzdanosti stručne procene uglavnom ciljnih funkcija koje su kvantitativne i kvalitativne prirode, usrednjavanjem mišljenja kvalifikovanih stručnjaka.

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

Klasifikacija metoda koje se razmatraju

Metode za rješavanje problema optimizacije, na osnovu broja parametara, mogu se podijeliti na:

• Jednodimenzionalne metode optimizacije.
• Metode višedimenzionalne optimizacije.

Nazivaju se i "numeričke metode optimizacije". Da budemo precizni, ovo su algoritmi za pretragu.

U okviru upotrebe derivata, metode su:

• direktne metode optimizacije (nulti red);
• metode gradijenta (1. red);
• Metode drugog reda, itd.

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

Jednodimenzionalne metode optimizacije

Bilo koja metoda numeričke optimizacije temelji se na približnom ili točnom proračunu takvih karakteristika kao što su vrijednosti ciljne funkcije i funkcije koje definiraju dopušteni skup i njihove derivate. Tako se za svaki pojedinačni zadatak može riješiti pitanje izbora karakteristika za proračun u zavisnosti od postojećih svojstava funkcije koja se razmatra, raspoloživih mogućnosti i ograničenja u pohranjivanju i obradi informacija.

Postoji sledećim metodama rješavanje problema optimizacije (jednodimenzionalno):

• Fibonačijeva metoda;
• dihotomije;
• zlatni omjer;
• udvostručavanje koraka.

Fibonačijeva metoda

Prvo, trebate postaviti koordinate tačke x na intervalu kao broj jednak omjeru razlike (x - a) i razlike (b - a). Dakle, a ima koordinatu 0 u odnosu na interval, a b ima koordinatu 1, a sredina je ½.

Ako pretpostavimo da su F0 i F1 jednaki jedan drugom i uzmemo vrijednost 1, F2 će biti jednak 2, F3 - 3, ..., tada je Fn = Fn-1 + Fn-2. Dakle, Fn su Fibonačijevi brojevi, a Fibonačijeva pretraga je optimalna strategija za takozvanu sekvencijalnu pretragu maksimuma zbog činjenice da je prilično blisko povezana sa njima.

Unutar optimalna strategija Uobičajeno je izabrati 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, tačka (naslijeđena) u odnosu na novi interval će imati ili koordinate , ili . Zatim se kao xn - 2 uzima tač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 biće moguće preći na interval nesigurnosti kao što je , dok je srednja tačka naslijeđena iz prethodnog koraka. Kao x1, postavljena je tačka koja ima relativnu koordinatu ½+ε, a konačni interval nesigurnosti će biti ili [½, 1] u odnosu na .

U 1. koraku, dužina ovog intervala je smanjena na Fn-1: Fn (sa jedan). U završnim koracima, smanjenje dužina odgovarajućih intervala predstavljeno je brojevima Fn-2: Fn-1, Fn-3: Fn-2, ..., F2: F3, F1: F2 (1 + 2ε ). Dakle, dužina takvog intervala kao konačna verzija će imati vrijednost (1 + 2ε): Fn.

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

Vrijedi napomenuti da asimptotski za značajno n, svaki sljedeći korak Fibonačijeve pretrage značajno sužava razmatrani interval za gornji koeficijent. Ovaj rezultat se mora uporediti sa 0,5 (koeficijent sužavanja intervala nesigurnosti unutar metode bisekcije za pronalaženje nule funkcije).

Metoda dihotomije

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

Metoda zlatnog omjera

Za značajne vrijednosti n, koordinate tačaka kao što su xn i xn-1 su blizu 1 - r, jednako 0,3820, a r ≈ 0,6180. Guranje od ovih vrijednosti je vrlo blizu željenoj optimalnoj strategiji.

Ako pretpostavimo da je F(0,3820) > F(0,6180), onda 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. Shodno tome, u svakoj fazi, počevši od 2., potrebno je samo jedno izračunavanje funkcije cilja, a svaki korak smanjuje dužinu razmatranog intervala za faktor 0,6180.

Za razliku od Fibonačijeve pretrage, u ovu metodu nema potrebe popravljati broj n prije početka pretraživanja.

„Zlatni presjek” presjeka (a; b) je presjek kod kojeg je omjer njegove dužine 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 pretpostaviti da je r određeno gornjom formulom. Shodno tome, za značajno n, Fibonačijeva metoda ide u ovu.

Metoda udvostručavanja koraka

Suština je traženje smjera opadanja ciljne funkcije, kretanje u tom smjeru u slučaju uspješnog traženja uz postupno povećanje koraka.

Prvo određujemo početnu koordinatu M0 funkcije F(M), minimalnu vrijednost koraka h0 i smjer traženja. Tada definiramo funkciju u tački M0. Zatim ćemo napraviti korak i pronaći vrijednost ove funkcije u ovom trenutku.

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ćate za 2 puta. Ako je njegova vrijednost veća od prethodne, morat ćete promijeniti smjer pretraživanja, a zatim krenuti u odabranom smjeru sa koracima h0. Prikazani algoritam se može modifikovati.

Metode višedimenzionalne optimizacije

Navedena metoda nultog reda ne uzima u obzir izvode minimizirane funkcije, zbog čega njihova upotreba može biti efikasna ako se pojave poteškoće u izračunavanju izvoda.

Grupa metoda 1. reda naziva se i gradijentna metoda, jer se za uspostavljanje smjera pretraživanja koristi gradijent date funkcije - vektor čije su komponente djelomične izvode minimizirane funkcije u odnosu na odgovarajuće optimizirane parametre. .

U grupi metoda 2. reda koriste se 2 derivata (njihova upotreba je prilično ograničena zbog poteškoća u njihovom proračunu).

Lista metoda neograničene optimizacije

Kada se koristi višedimenzionalno pretraživanje bez upotrebe derivata, metode neograničene optimizacije su sljedeće:

• Hook i Jeeves (sprovođenje 2 vrste pretraživanja - bazirano na uzorcima i istraživačko);
• minimizacija ispravnim simpleksom (traženje minimalne točke odgovarajuće funkcije poređenjem njenih vrijednosti na vrhovima simpleksa na svakoj pojedinačnoj iteraciji);
• ciklično koordinatno spuštanje (koristeći koordinatne vektore kao referentne tačke);
• Rosenbrock (zasnovan na upotrebi jednodimenzionalne minimizacije);
• minimizacija pomoću deformisanog simpleksa (modifikacija metode minimizacije pomoću običnog simpleksa: dodavanje postupka kompresije i rastezanja).

U situaciji korištenja derivacija u procesu višedimenzionalnog pretraživanja, izdvaja se metoda najstrmijeg spuštanja (najosnovniji postupak za minimiziranje diferencijabilne funkcije s više varijabli).

Postoje i druge metode koje koriste konjugirane smjerove (Davidon-Fletcher-Powell metoda). Njegova suština je predstavljanje pravaca traženja kao Dj*grad(f(y)).

Klasifikacija metoda matematičke optimizacije

Konvencionalno, na osnovu dimenzije funkcija (cilja), oni su:

• sa 1 varijablom;
• multidimenzionalni.

U zavisnosti od funkcije (linearne ili nelinearne), postoji veliki broj matematičkih metoda koje imaju za cilj pronalaženje ekstrema za rešavanje problema.

Na osnovu kriterijuma za korišćenje derivata, metode matematičke optimizacije se dele na:

• metode za izračunavanje 1 derivacije ciljne funkcije;
• višedimenzionalni (1. derivacija-vektor količina-gradijent).

Na osnovu efikasnosti proračuna razlikuju se:

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

Ovo je uslovna 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 za optimizaciju poslovnih procesa:

• izuzeci (smanjenje nivoa postojećeg procesa, eliminisanje uzroka smetnji i dolazne kontrole, smanjenje transportnih ruta);
• pojednostavljenje (olakšana obrada narudžbi, smanjena složenost strukture proizvoda, distribucija posla);
• standardizacija (upotreba posebnih programa, metoda, tehnologija itd.);
• ubrzanje (paralelni inženjering, stimulacija, operativni dizajn prototipova, automatizacija);
• promjena (promjene sirovina, tehnologije, metoda rada, osoblja, sistema rada, obima narudžbi, postupaka obrade);
• obezbjeđivanje interakcije (u odnosu na organizacione jedinice, kadrove, sistem rada);
• odabir i uključivanje (u odnosu na potrebne procese, komponente).

Optimizacija poreza: 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šte metode optimizacije poreza su sljedeće:

• razvoj računovodstvenih politika preduzeća maksimalno moguća primena mogućnosti koje pruža rusko zakonodavstvo (postupak otpisa IBP-a, izbor metode za obračun prihoda od prodaje robe, itd.);
• optimizacija putem ugovora (zaključivanje preferencijalnih transakcija, jasna i kompetentna upotreba formulacije, itd.);
• primjena raznih vrsta beneficija i poreskih olakšica.

Drugu grupu metoda također mogu koristiti sve kompanije, ali one i dalje imaju prilično uzak opseg primjene. Posebne metode optimizacije poreza su sljedeće:

• zamjenski odnos (operacija koja uključuje opterećujuće oporezivanje zamjenjuje se drugom koja vam omogućava postizanje sličnog cilja, ali istovremeno korištenje preferencijalni tretman oporezivanje).
• podjela odnosa (zamjena samo dijela poslovne transakcije);
• odlaganje plaćanja poreza (odgađanje trenutka pojavljivanja predmeta oporezivanja za drugi kalendarski period);
• direktno smanjenje predmeta oporezivanja (oslobađanje od mnogih oporezivih transakcija ili imovine bez obezbjeđenja negativan uticaj za glavne poslovne aktivnosti kompanije).

Među metodama optimizacije nultog reda u CAD-u, koriste se Rosenbrockove metode, konfiguracije, deformabilni poliedar i slučajna pretraga. Metode koje koriste derivate uključuju najstrmiji pad, konjugirani gradijent i varijabilne metričke metode.

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

Metoda koordinatnog spuštanja karakteriše izbor pravaca traženja naizmjenično duž svih koordinatnih osa, korak se izračunava na osnovu jednodimenzionalne optimizacije, kriterij za završetak pretrage je , gdje je navedena tačnost određivanja lokalnog ekstremuma, je dimenzija prostor kontrolisanih parametara. Koordinatna putanja spuštanja za primjer dvodimenzionalnog prostora kontroliranih parametara prikazana je na Sl. 1, gdje su tačke na putanji pretraživanja i kontrolirani parametri. Funkcija cilja je predstavljena svojim linijama jednakih nivoa, a odgovarajuća vrijednost je upisana pored svake linije. Očigledno postoji minimalna tačka.

Rice. 1. Trajektorija koordinatnog spuštanja

Kada se koristi metoda koordinatnog spuštanja, postoji velika vjerovatnoća da se pretraga zaglavi na dnu jaruge daleko od tačke ekstrema. Na sl. 2 pokazuje da su nakon udarca u tačku koja se nalazi na dnu jaruge daljnji koraci mogući samo u smjerovima ili , ali oni dovode do pogoršanja funkcije cilja. Stoga se pretraga zaustavlja na tački .

Napomena 1

Jaruga je dio prostora kontroliranih parametara u kojem se u pojedinim smjerovima uočavaju slabe promjene derivacija funkcije cilja, a u drugim značajne promjene sa promjenom predznaka. Predznak derivacije se mijenja na tačkama koje pripadaju dnu jaruge.

Rice. 3. Trajektorija koordinatnog spuštanja uz povoljnu orijentaciju koordinatnih osa

Rosenbrock metoda sastoji se u rotaciji koordinatnih osa tako da jedna od njih ispadne kvaziparalelna s dnom jaruge. Ova rotacija se izvodi na osnovu podataka dobijenih nakon niza koraka koordinatnog spuštanja. Položaj novih osa može se dobiti linearnom transformacijom prethodnih osa: os se poklapa u pravcu sa vektorom; preostale ose se biraju iz uslova ortogonalnosti na i jedna na drugu.

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

Rice. 4. Ilustracija metode konfiguracije

Potražite ekstrem metoda deformabilnog poliedra(Nelder-Mead) se zasniva na konstrukciji poliedra sa vrhovima u svakom koraku pretraživanja, gdje je dimenzija prostora kontroliranih parametara. Na početku pretrage, ovi vrhovi se biraju nasumično u narednim koracima, izbor je podložan pravilima metode;

Ova pravila su objašnjena na sl. 5 koristeći primjer dvodimenzionalnog problema optimizacije. Odabrani su vrhovi originalnog trokuta: , , . Novi vrh se nalazi na zraku povučenom iz najgoreg vrha (iz vrha sa najvećom vrijednošću funkcije cilja) kroz težište poliedra, a preporučuje se odabir na udaljenosti od , jednakom . Novi vrh zamjenjuje najgori vrh. Ako se pokaže da ima najbolju vrijednost ciljne funkcije među vrhovima poliedra, tada se udaljenost povećava. Na slici je upravo takva situacija i povećanje daje poentu. U novom poliedru sa vrhovima , , najgori je vrh , na sličan način se dobija vrh , zatim vrh, itd. Ako se novi vrh pokaže lošijim, onda se najbolji vrh mora sačuvati u poliedru, a dužine svih ivica se moraju smanjiti, na primjer, za polovicu (sažimanje poliedra do najboljeg vrha). Pretraga se zaustavlja kada se ispuni uslov smanjenja veličine poliedra na određenu granicu.

optimalni korak se bira pomoću jednodimenzionalne optimizacije.

Kada se koristi metoda najstrmijeg spuštanja, kao i većina drugih metoda, efikasnost pretraživanja je značajno smanjena u situacijama jaruga. Traktorija traženja poprima cik-cak oblik uz sporo kretanje po dnu jaruge prema ekstremumu. Da bi se povećala efikasnost gradijentnih metoda, koristi se nekoliko tehnika.

Jedna od tehnika koje se koriste u metoda konjugovanog gradijenta(takođe nazvana Fletcher-Reeves metoda), zasniva se na konceptu konjugacije vektora. Vektori i nazivaju se -konjugirani ako , gdje je pozitivno određena kvadratna matrica istog reda kao i veličina vektora i (poseban slučaj konjugacije je ortogonalnost vektora, kada je matrica identiteta reda ), je red vektor, je vektor stupac.

Posebnost konjugiranih pravaca za , gdje je Hessian matrica, u problemima s kvadratnom ciljnom funkcijom je sljedeća: jednodimenzionalna minimizacija sekvencijalno duž konjugiranih pravaca omogućava pronalaženje ekstremne točke u najviše koraka.

Napomena 2

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

Razlog za korištenje -konjugirane pretrage je taj za funkcije () opšti pogled Može se primijeniti kvadratna aproksimacija, što u praksi rezultira izvođenjem pretraživanja u više od koraka.

Potraga za ekstremom se vrši u skladu sa formulom

gdje je koeficijent. Uz to se uzima u obzir i uslov konjugacije

Budući da je korak izračunat na osnovu jednodimenzionalnog uvjeta optimizacije, tada je, prvo, tačan sljedeća relacija:

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

Da biste odredili koeficijent, riješite sistem jednadžbi (2)-(7) zamjenom u (4) vrijednosti iz (3) i iz (2):

ili

gdje

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

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

Zbog toga

Može se pokazati da teži , - do kada , gdje je dimenzija prostora kontroliranih parametara. Nakon koraka, morate ponovo početi od .

Optimizacija je proces pronalaženja ekstrema (globalnog maksimuma ili minimuma) određene funkcije ili odabira najbolje (optimalne) opcije iz skupa mogućih. Najpouzdaniji način da se pronađe najbolja opcija je komparativna 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 metode se mogu primijeniti ako postoji striktna formulacija problema: specificiran je skup varijabli, utvrđeno područje njihove moguće promjene (ograničenja su specificirana) i tip funkcije cilja (funkcija čiji je ekstremum treba pronaći) iz ovih varijabli se određuje. Ovo drugo je kvantitativna mjera (kriterijum) za procjenu stepena ostvarenosti cilja.

Problem neograničene optimizacije je pronaći minimum ili maksimum funkcije u odsustvu bilo kakvih ograničenja. Iako većina praktičnih problema optimizacije sadrži ograničenja, učenje metoda neograničene optimizacije je važno sa nekoliko gledišta. Mnogi algoritmi za rješavanje ograničenog problema uključuju njegovo svođenje na niz neograničenih optimizacijskih problema. Druga klasa metoda zasniva se na pronalaženju odgovarajućeg smjera i zatim minimiziranju duž ovog smjera. Opravdanje neograničenih metoda optimizacije može se prirodno proširiti na opravdanje procedura 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 ciljne funkcije za određivanje priraštaja x1, ..., xn na svakoj iteraciji. Postoje i približne metode za rješavanje nelinearnih problema. Ovo su metode zasnovane na metodi linearne aproksimacije po komadima. Točnost nalaženja rješenja ovisi o broju intervala u kojima nalazimo rješenje linearnog problema koje je što bliže nelinearnom. Ova metoda omogućava izvođenje proračuna korištenjem simpleks metode. Tipično, u linearnim modelima, koeficijenti ciljne funkcije su konstantni i ne ovise o vrijednostima varijabli. Međutim, postoji niz problema u kojima troškovi nelinearno zavise od obima.

Algoritam rješenja:

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

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

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

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

C1 - cijena metala, rub/kg;

X2 - masa potrebnih elektroda, kg;

C2 - cijena 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 lifta, h;

C5 - naknada za lift, rub/sat.

1. Pronađite optimalnu površinu posude:

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

gdje je V=2750 litara.

x1=16,331; x2=10,99

Minimum funkcije dobijen je u procesu optimizacije po Box metodi - 1196.065 dm2

U skladu sa GOST 19903 - 74, prihvatamo:

h=16,50 dm, b=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 peska.

Opterećenje na zidu kontejnera najveće površine:

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

Odredimo debljinu zida na osnovu uslova:

gdje je: l dužina lista (po mogućnosti najduža da bi se ostavila dodatna sigurnosna granica);

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

Debljina lima, m

Maksimalno dozvoljeno naprezanje metala, N/mm2.

Izrazimo debljinu zida iz (2):

S obzirom da je 320 MPa = 3263 kg/cm2,

Metalna masa

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

Debljina metalnog zida, m;

Gustoća metala, kg/m3.

Cijena St2sp čelika je oko 38 rubalja/kg.

2. Dužina zavarivanja:

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

Cijena 88,66 rub/kg;

gdje je: Sweld - površina poprečnog presjeka šava, m2;

l je dužina zavara, m;

Gustina nanesenog metala, kg/m3.

3. Vrijeme zavarivanja:

gdje je l dužina šava, 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 mesta u proseku su 40 - 60%. Koristimo prosječnu vrijednost od 50%.

Ukupno vrijeme:

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

Plus tarifni koeficijent od 17% za rad u skučenom, slabo provetrenom prostoru:

Plaćanje asistenta iznosi 60% od plaće zavarivača:

8055 0,6 = 4833 rub.

Ukupno: 8055+4833 = 12888 rubalja.

5. Dizalica je potrebna za držanje limova tokom zavarivanja, utovara i istovara metalnih limova i samog gotovog kontejnera.

Da bi "zahvatio" cijelu strukturu, zavarivač treba nanijeti oko 30% šavova.

Plaćanje za dizalicu je 1000 rubalja/sat.

Ukupna cijena kontejnera.

Klasične metode neograničene optimizacije

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 kursevima ML. To je zbog njihove direktne upotrebe u rješavanju niza optimizacijskih problema, kao i u implementaciji metoda za rješavanje značajnog dijela uvjetnih optimizacijskih problema (MP problema).

1. Neophodni uslovi za lokalnu minimalnu (maksimalnu) tačku

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

Pronađimo ga koristeći proširenje funkcije u Taylorov red u okolini m.

gdje je zbir članova niza čiji je redoslijed u odnosu na priraštaje (dva) i više.

Iz (4) jasno proizilazi da

Pretpostavimo onda

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

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

Tako da je to zaista očigledno.

Slično argumentirajući za druge varijable, dobijamo neophodno stanje za tačke lokalnog minimuma funkcije više varijabli

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

Jasno je da će rezultat dokaza biti nejednakost oblika: - uslov za nepozitivan prirast funkcije u blizini lokalnog maksimuma.

Dobijeni neophodni uslovi ne daju odgovor na pitanje: da li je stacionarna tačka minimalna ili maksimalna tačka.

Odgovor na ovo pitanje može se dobiti proučavanjem dovoljne uslove. Ovi uvjeti podrazumijevaju proučavanje matrice drugih izvoda ciljne funkcije.

2. Dovoljni uslovi za lokalnu minimalnu (maksimalnu) tačku

Predstavimo proširenje funkcije u susjedstvu tačke u Taylorovom redu do kvadratnih članova.

Dekompoziciju (1) možemo ukratko predstaviti koristeći koncepte: „skalarni proizvod vektora” i „vektorsko-matrični proizvod”.

Matrica dva izvoda ciljne funkcije u odnosu na odgovarajuće varijable.

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

Uzimajući u obzir neophodne uslove:

Zamenimo (3) u obliku:

Kvadratna forma se naziva diferencijalna kvadratna forma (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đeni, tada je stacionarna tačka također tačka lokalnog maksimuma.

Dakle, neophodan i dovoljan uslov za lokalnu minimalnu tačku ima oblik

(ovi neophodni uslovi se mogu napisati na sledeći način:

Dovoljno stanje.

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

Prisjetimo se kriterija koji nam omogućava da odredimo jesu li kvadratni oblik i matrica koja ga predstavlja pozitivno ili negativno definitivna.

3. Silvesterov kriterijum

Omogućava vam da odgovorite na pitanje: je li kvadratni oblik i matrica koja ga predstavlja pozitivno ili negativno definitivna.

Zove se Hessian matrica.

Glavna determinanta Hesove matrice

a DCF koji on predstavlja bit će pozitivno definitivan ako su sve glavne determinante Hessove matrice () pozitivne (tj. vrijedi sljedeća shema predznaka:

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

4. Ojlerova metoda - klasična metoda za rješavanje neograničenih optimizacijskih problema

Ova metoda se zasniva na neophodnim i dovoljnim uslovima proučavanim u 1.1 - 1.3; primjenjivo za pronalaženje lokalnih ekstrema samo kontinuiranih diferencijabilnih funkcija.

Algoritam za ovu metodu je prilično jednostavan:

1) koristeći potrebne uslove, formiramo sistem nelinearnih jednačina u opštem slučaju. Imajte na umu da je nemoguće analitički riješiti ovaj sistem u opštem slučaju; potrebno je primijeniti numeričke metode za rješavanje sistema nelinearnih jednačina (NL) (vidi "FM"). Iz tog razloga, Eulerova metoda će biti analitičko-numerička metoda. Rješavanjem navedenog sistema jednadžbi nalazimo koordinate stacionarne tačke.;

2) proučavamo DCF i Hessian matricu koja ga predstavlja. Koristeći Sylvesterov kriterij, utvrđujemo da li je stacionarna tačka minimalna ili maksimalna tačka;

3) izračunati vrijednost ciljne funkcije u ekstremnoj tački

Koristeći Eulerovu metodu, riješite sljedeći problem neograničene optimizacije: pronađite 4 stacionarne točke funkcije oblika:

Saznajte prirodu ovih tačaka, bilo da su to minimalne tačke ili sedla (vidi). Konstruisati grafički prikaz ove funkcije u prostoru i na ravni (pomoću linija nivoa).

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

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

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

Jednadžbe linija nivoa

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

Kao što se vidi sa slike, tačka je tačka bezuslovnog globalnog maksimuma; tačka - tačka uslovnog (relativnog) lokalnog minimuma; tačka - tačka uslovnog (relativnog) lokalnog maksimuma.

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

Originalni problem (1"), (2") se tako transformiše u problem bezuslovne optimizacije funkcije, koji se lako može rešiti Ojlerovom metodom.

Metoda eliminacije (supstitucije).

Neka funkcija cilja zavisi od varijabli:

nazivaju se zavisne varijable (ili varijable stanja); u skladu s tim, možete unijeti vektor

Preostale varijable se nazivaju nezavisne varijable odluke.

U skladu s tim, možemo govoriti o vektoru stupca:

i vektor.

U klasičnom problemu ograničene optimizacije:

Sistem (2), u skladu sa metodom eliminacije (supstitucije), mora biti razriješen u odnosu na zavisne varijable (varijable stanja), tj. Trebalo bi dobiti sljedeće izraze za zavisne varijable:

Da li je sistem jednačina (2) uvijek rješiv u odnosu na zavisne varijable - to nije uvijek moguće u slučaju kada je determinanta, nazvana Jakobijan, čiji elementi imaju oblik:

nije jednako nuli (pogledajte odgovarajuću teoremu u MA kursu)

Kao što se može vidjeti, funkcije moraju biti kontinuirane diferencibilne funkcije, drugo, elementi determinante moraju biti izračunati u stacionarnoj tački ciljne funkcije.

Zamjenom iz (3) u ciljnu funkciju (1), imamo:

Funkcija koja se proučava može se dovesti do ekstrema Ojlerovom metodom - metodom bezuslovne optimizacije kontinuirano diferencibilne funkcije.

Dakle, metoda eliminacije (supstitucije) vam omogućava da koristite klasični problem uslovne optimizacije da ga transformišete u bezuslovni optimizacioni problem funkcije - funkciju varijabli pod uslovom (4), što vam omogućava da dobijete sistem izraza (3 ).

Nedostaci metode isključivanja: poteškoće, a ponekad i nemogućnost dobijanja sistema izraza (3). Bez ovog nedostatka, ali koji zahteva ispunjenje uslova (4) je MML.

5.2. Lagrangeova metoda množenja. Neophodni uslovi u klasičnom problemu ograničene optimizacije. Lagrangeova funkcija

MML dozvoljava originalni problem klasične ograničene optimizacije:

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

gdje su Lagrangeovi množitelji;

Kao što možete vidjeti, to je zbir koji se sastoji od originalne ciljne funkcije i “ponderiranog” zbira funkcija – funkcija koje predstavljaju njihova ograničenja (2) originalnog problema.

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

Korištenje koncepta zavisnih i nezavisnih varijabli - zavisnih varijabli; - nezavisne varijable, tada predstavljamo (5) u proširenom obliku:

Iz (2) očigledno slijedi sistem jednačina oblika:

Rezultat izračunavanja 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"), sistem koji se sastoji od jednačina.

Pomnožimo svaku jednačinu sistema (6") odgovarajućim Lagrangeovim množiteljem. Saberimo ih i sa jednačinom (5") i dobijemo izraz:

Uredimo Lagrangeove množitelje na način da izraz u uglastim zagradama pod predznakom prve sume (drugim riječima, koeficijenti diferencijala nezavisnih varijabli) bude jednak nuli.

Izraz “raspolaganje” Lagrangeovih množitelja na gore navedeni način znači da je potrebno riješiti neki sistem jednačina za.

Struktura takvog sistema jednačina može se lako dobiti izjednačavanjem izraza u uglastim zagradama pod prvim znakom zbira sa nulom:

Prepišimo (8) u obliku

Sistem (8") je sistem linearnih jednačina u odnosu na poznato: . Sistem je rješiv ako (zato, kao u metodi eliminacije u predmetnom slučaju, mora biti zadovoljen uslov). (9)

Kako je u ključnom izrazu (7) prvi zbir jednak nuli, lako je shvatiti da će i drugi zbir biti jednak nuli, tj. odvija se sljedeći sistem jednačina:

Sistem jednačina (8) se sastoji od jednačina, a sistem jednačina (10) se sastoji od jednačina; ukupne jednačine u dva sistema, i nepoznate

Jednačine koje nedostaju date su sistemom jednačina ograničenja (2):

Dakle, postoji sistem jednačina za pronalaženje nepoznanica:

Dobijeni rezultat - sistem jednačina (11) - čini glavni sadržaj MML-a.

Lako je shvatiti da se sistem jednačina (11) može dobiti vrlo jednostavno uvođenjem u razmatranje posebno konstruisane Lagrangeove funkcije (3).

Zaista

Dakle, sistem jednačina (11) se može predstaviti kao (pomoću (12), (13)):

Sistem jednadžbi (14) predstavlja neophodan uslov u klasičnom problemu ograničene optimizacije.

Vrijednost vektora pronađena kao rezultat rješavanja ovog sistema naziva se uslovno stacionarna tačka.

Da bi se saznala priroda uslovno stacionarne tačke, potrebno je koristiti dovoljne uslove.

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

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

Relativno jednostavno, slično kao što su dobijeni dovoljni uslovi u problemu bezuslovnog ekstremuma. Također je moguće dobiti dovoljne uvjete u klasičnom ograničenom optimizacijskom problemu.

Rezultat ove studije:

gdje je tačka lokalnog uslovnog minimuma.

gdje je tačka lokalnog uslovnog maksimuma, je Hesova matrica sa elementima

Hesova matrica ima dimenziju.

Dimenzija Hessian matrice može se smanjiti korištenjem uvjeta da Jacobian nije nula: . Pod ovim uslovom, zavisne varijable se mogu izraziti kroz nezavisne varijable, tada će Hessian matrica imati dimenziju, tj. moramo razgovarati o matrici sa elementima

tada će dovoljni uslovi izgledati ovako:

Lokalna uslovna minimalna tačka.

Lokalna uslovna maksimalna tačka.

Dokaz: MML algoritam:

1) sastaviti Lagrangeovu funkciju: ;

2) koristeći potrebne uslove, formiramo sistem jednačina:

3) iz rješenja ovog sistema nalazimo tačku;

4) koristeći dovoljne uslove, odredimo da li je tačka tačka lokalnog uslovnog 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 njegove modifikacije pri rješavanju najjednostavnijih IP i AP problema

Ova metoda koristi geometrijsku interpretaciju klasičnog problema ograničene optimizacije i zasniva se na brojnim važnim činjenicama svojstvenim ovom problemu.

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

Kao što se vidi sa slike, tačka je tačka bezuslovnog minimuma, tačka je tačka uslovnog lokalnog minimuma, tačka je tačka uslovnog lokalnog maksimuma.

Dokažimo da je u tačkama uslovnih lokalnih ekstrema kriva i odgovarajuće linije nivoa

Iz magistarskog kursa je poznato da je u tački kontakta uslov zadovoljen

gdje je ugaoni koeficijent tangente povučene odgovarajućom linijom nivoa; - ugaoni koeficijent tangente povučene na funkciju

Izraz (MA) za ove koeficijente je poznat:

Dokažimo da su ovi koeficijenti jednaki.

jer o tome „govore“ potrebni uslovi

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

1) izgraditi porodicu linija na nivou funkcije cilja:

2) konstruisati ODD koristeći jednačinu ograničenja

3) da bismo ispravili porast funkcije, pronalazimo i razjašnjavamo prirodu ekstremnih tačaka;

4) proučavamo interakciju linija nivoa i funkcija, pri čemu iz sistema jednačina nalazimo koordinate uslovno stacionarnih tačaka – lokalnih uslovnih minimuma i lokalnih uslovnih maksimuma.

5) izračunati

Posebno treba napomenuti da se glavne faze GFA metode za rješavanje klasičnog problema uslovne optimizacije poklapaju sa glavnim fazama GFA metode za rješavanje LP i LP problema, jedina razlika je u ODR-u, kao i u pronalaženju lokacija ekstremnih tačaka u ODD-u (na primjer, u LP problemima ove tačke se nužno 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 veličine koje predstavljaju promjenjive resurse u primijenjenim tehničkim i ekonomskim problemima.

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

gdje je promjenjiva veličina. (2")

Neka je uslovna tačka ekstrema:

Prilikom promjene promjena

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

Izračunajmo derivaciju:

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

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

Iz (6) Lagrangeov množitelj karakterizira vrijednost “reakcije” (ortogonalnu vrijednosti ciljne funkcije) na promjene parametra.

U opštem 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, onda karakterizira promjene ove vrijednosti pri promjeni za 1.

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

Par se naziva sedlo ako vrijedi nejednakost.

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

Iz (2), to. (3)

Kao što vidite, sistem (3) sadrži jednačine slične onim jednačinama koje predstavljaju neophodan uslov u klasičnom problemu ograničene optimizacije:

gdje je Lagrangeova funkcija.

U vezi sa analogijom sistema jednačina (3) i (4), klasični problem ograničene optimizacije može se posmatrati kao problem nalaženja sedla Lagrangeove funkcije.

Slični dokumenti

Višedimenzionalni problemi optimizacije u proučavanju tehnoloških procesa u tekstilnoj industriji, analiza nastalih poteškoća. Pronalaženje ekstrema, vrste ekstrema, vrijednosti funkcije cilja neograničene višedimenzionalne optimizacije.

test, dodano 26.11.2011


Karakteristično klasične metode bezuslovna optimizacija. Određivanje potrebnog i dovoljnog uslova za postojanje ekstrema funkcija jedne i više varijabli. Lagrangeovo pravilo množitelja. Neophodni i dovoljni uslovi za optimalnost.

rad na kursu, dodato 13.10.2013


Metodologija i karakteristike rješavanja problema optimizacije, posebno o raspodjeli investicija i izboru puta u transportnoj mreži. Specifičnosti modeliranja Hamingovom i Brownovom metodom. Identifikacija, stimulacija i motivacija kao funkcije upravljanja.

test, dodano 12.12.2009


Iskaz, analiza, grafičko rješenje problema linearne optimizacije, simpleks metoda, dualnost u linearnoj optimizaciji. Iskaz transportnog problema, svojstva i pronalaženje referentnog rješenja. Uslovna optimizacija pod ograničenjima jednakosti.

priručnik za obuku, dodan 07.11.2010


Kritična putanja u grafu. Optimalna distribucija protoka u transportnoj mreži. Problem linearnog programiranja riješen grafički. Problem neuravnoteženog transporta. Numeričke metode za rješavanje jednodimenzionalnih problema statičke optimizacije.

kurs, dodato 21.06.2014


Grafička metoda za rješavanje optimizacijskog problema proizvodni procesi. Primjena simpleks algoritma za rješavanje ekonomski optimiziranog problema upravljanja proizvodnjom. Metoda dinamičkog programiranja za odabir optimalnog profila putanje.

test, dodano 15.10.2010


Metode optimizacije za rješavanje ekonomskih problema. Klasična formulacija optimizacijskog problema. Optimizacija funkcije. Optimizacija funkcionalnosti. Višekriterijumska optimizacija. Metode za svođenje višekriterijumskog problema na jednokriterijumski. Metoda koncesija.

sažetak, dodan 20.06.2005


Primjena metoda nelinearnog programiranja za rješavanje problema s nelinearnim funkcijama varijabli. Uvjeti optimalnosti (Kuhn-Tucker teorem). Metode uvjetne optimizacije (Wolfeova metoda); gradijent dizajn; kaznene i barijere funkcije.

sažetak, dodan 25.10.2009


Pojam, definicija, isticanje osobina, mogućnosti i karakteristika postojećih problema višekriterijumske optimizacije i načini njihovog rješavanja. Proračun metode jednakih i najmanjih odstupanja višekriterijumske optimizacije i njena primjena u praksi.

kurs, dodan 21.01.2012


Osnovni koncepti modeliranja. Opšti koncepti i definicija modela. Postavljanje problema optimizacije. Metode linearnog programiranja. Opšti i tipični problem u linearnom programiranju. Simpleksna metoda za rješavanje problema linearnog programiranja.