Dancigova metoda. Problem tipa transporta je poseban slučaj problema linearnog programiranja

1. Koje su tvrdnje netačne? Danzig metoda

Odgovor: može se pripisati grupi gradijenta

2. Koje od sljedećih izjava su tačne:

Odgovor: LP problem sa nekonzistentnim sistemom ograničenja naziva se otvorenim problemom.

3. Koje od sljedećih metoda nisu aktivne

Odgovor: zlatni rez

4. Koje su od sljedećih izjava tačne:

Odgovor: zadatak tipa transporta je poseban slučaj zadatka linearno programiranje

5. Koje od sljedećih tvrdnji su istinite: Metoda najmanjih kvadrata

Odgovor: svodi se na rješavanje sistema br linearne jednačine pri aproksimaciji rezultata polinomima n-tog reda

6. Koje od sljedećih metoda nisu gradijentne

Odgovor: simpleks metoda (Nelder-Mead metoda)

7. Koja od navedenih metoda omogućava pronalaženje globalnog ekstremuma polimodalne funkcije

Odgovor: skeniranje

8. Koje metode od navedenih su metode koordinatnog traženja

Odgovor: tangenta

9. Provjerite tačne izjave

Odgovor: jednostavna metoda nabrajanja ne može se koristiti za pronalaženje ekstrema prema Gauss-Seidelovom postupku.

10. Istaknite istinitu tvrdnju

Odgovor: Plan je bilo koji prihvatljivo rešenje zadataka

11. Ukažite na pogrešnu tvrdnju

Odgovor: ravan koja sadrži najmanje jednu kutnu tačku konveksni poliedar naziva se referentna ravan ovog poliedra

12. Navedite brojeve tačnih tvrdnji

Odgovor: problemi transportnog tipa ne mogu se riješiti Danzigovom metodom, jer se odnose na probleme diskretnog programiranja (1). originalni plan u simpleks metodi dobijamo jednaku nuli svih osnovnih varijabli (3)

13. Navedite tačnu tvrdnju?

Odgovor: osnovno rješenje LP problema je degenerirano ako je barem jedna od slobodnih varijabli jednaka nuli

14. Šta od sljedećeg nije tačno:

Odgovor: bilo koja tačka na pravoj je konveksna linearna kombinacija dvije tačke kroz koje je povučena ova prava.

15. Koja je od navedenih izjava tačna?

Odgovor: Problem trgovačkog putnika pripada području diskretnog programiranja.

16. Šta je od sljedećeg tačno:

Odgovor: jedan od glavnih problema optimizacije je “dimenzionalni problem”

17. Šta nije u redu u gornjim izjavama?

Odgovor: ako funkcija cilja LP problema dostigne ekstrem u nekoliko tačaka, tada dostiže istu vrijednost u bilo kojoj tački koja je konveksna linearna kombinacija ovih tačaka.

18. Koja od sljedećih izjava je netačna?

Odgovor: LP problem se može riješiti postupkom uređenog prijelaza s jednog plana na drugi.

19. Što je od sljedećeg tačno

Odgovor: Unutar domena dopuštenih rješenja LP problema ne može postojati ekstremum

20. Šta je od sljedećeg netačno?

Odgovor: Da pronađemo ekstremum linearne ciljna funkcija korištenjem simpleks metode potrebno je izvršiti n-m iteracija, n je broj nepoznanica problema, m je broj općih ograničenja

gradijent metode traženje optimalne funkcije cilja zasnivaju se na korištenju dvije osnovna svojstva gradijent funkcije.

1. Gradijent funkcije je vektor, koji u svakoj tački domene definicije funkcije
je usmjeren duž normale na ravnu površinu koja prolazi kroz ovu tačku.

Gradijentne projekcije
na koordinatnoj osi jednaki su parcijalnim derivacijama funkcije
za odgovarajuće varijable, tj.

. (2.4)

Gradijentne metode uključuju: metodu opuštanja, gradijent, najstrmiji spust i niz drugih.

Razmotrite neke od metoda gradijenta.

metod gradijenta

Kod ove metode spuštanje se vrši u smjeru najbrže promjene ciljne funkcije, što prirodno ubrzava potragu za optimumom.

Potraga za optimumom se odvija u dvije faze. U prvoj fazi pronalaze se vrijednosti parcijalnih izvoda u odnosu na sve nezavisne varijable koje određuju smjer gradijenta u razmatranoj tački. U drugoj fazi se pravi korak u smjeru suprotnom od smjera gradijenta (prilikom traženja minimuma ciljne funkcije).

Kada se izvrši korak, vrijednosti svih nezavisnih varijabli se mijenjaju istovremeno. Svaki od njih dobija povećanje proporcionalno odgovarajućoj komponenti gradijenta duž date ose.

Formula algoritma može izgledati ovako:

,
. (2.5)

U ovom slučaju, veličina koraka
pri konstantnoj vrijednosti parametra, h se automatski mijenja s promjenom vrijednosti gradijenta i smanjuje se kako se približava optimalu.

Drugi formulaični zapis algoritma je:

,
. (2.6)

Ovaj algoritam koristi normalizirani vektor gradijenta koji ukazuje samo na smjer najbrže promjene ciljne funkcije, ali ne pokazuje stopu promjene u ovom smjeru.

U strategiji promjene terena
u ovom slučaju se koristi da gradijenti
i
razlikuju se u pravcu. Korak pretraživanja se mijenja u skladu sa pravilom:

(2.7)

gdje
je ugao rotacije gradijenta na k-tom koraku, određen izrazom

,

,
su dozvoljene granice ugla rotacije gradijenta.

Priroda potrage za optimumom u metodi gradijenta prikazana je na sl. 2.1.

Trenutak kada se pretraga završava može se pronaći provjerom na svakom koraku relacije

,

gdje je data proračunska greška.

Rice. 2.1. Priroda kretanja prema optimumu u metodi gradijenta sa velikom veličinom koraka

Nedostatak metode gradijenta je u tome što se pri njenoj upotrebi može pronaći samo lokalni minimum ciljne funkcije. Da bi se pronašli drugi lokalni minimumi funkcije, potrebno je tražiti iz drugih početnih tačaka.

Još jedan nedostatak ove metode je značajna količina proračuna, jer u svakom koraku se određuju vrijednosti svih parcijalnih izvoda funkcije koja se optimizira u odnosu na sve nezavisne varijable.

Metoda najstrmijeg spuštanja

Prilikom primjene metode gradijenta, u svakom koraku potrebno je odrediti vrijednosti parcijalnih izvoda funkcije koja se optimizira u odnosu na sve nezavisne varijable. Ako je broj nezavisnih varijabli značajan, tada se količina proračuna značajno povećava i vrijeme traženja optimalnog se povećava.

Smanjenje količine proračuna može se postići korištenjem metode najstrmijeg spuštanja.

Suština metode je sljedeća. Nakon što se u početnoj tački pronađe gradijent funkcije koju treba optimizirati i na taj način odredi smjer njenog najbržeg opadanja u navedenoj tački, pravi se silazni korak u tom smjeru (slika 2.2).

Ako se vrijednost funkcije smanjila kao rezultat ovog koraka, sljedeći korak se poduzima u istom smjeru, i tako sve dok se ne pronađe minimum u ovom smjeru, nakon čega se računa gradijent i novi smjer najbržeg utvrđeno je smanjenje ciljne funkcije.

Rice. 2.2. Priroda kretanja prema optimumu u metodi najstrmijeg spuštanja (–) i metodi gradijenta (∙∙∙∙)

U poređenju sa metodom gradijenta, metoda najstrmijeg spuštanja je povoljnija zbog smanjenja količine proračuna.

Važna karakteristika metode najstrmijeg spuštanja je da kada se primjenjuje, svaki novi smjer kretanja do optimalnog je ortogonan prema prethodnom. To je zbog činjenice da se kretanje u jednom smjeru izvodi sve dok smjer kretanja nije tangentan na bilo koju liniju konstantnog nivoa.

Kao kriterijum za prekid pretrage može se koristiti isti uslov kao u prethodnoj metodi.

Osim toga, može se prihvatiti i uslov za prekid pretrage u obliku relacije

,

gdje
i
su koordinate početne i krajnje tačke posljednjeg segmenta spuštanja. Isti kriterij se može koristiti u kombinaciji s kontrolom vrijednosti funkcije cilja u tačkama
i

.

Zajednička primjena uslova za prekid pretrage opravdana je u slučajevima kada funkcija koja se optimizira ima izražen minimum.

Rice. 2.3. Do definicije kraja potrage u metodi najstrmijeg spuštanja

Kao strategiju za promjenu koraka spuštanja, možete koristiti metode opisane gore (2.7).

Razmotrimo problem bezuslovne minimizacije diferencijabilne funkcije nekoliko varijabli.Neka se vrijednost gradijenta u tački približi minimumu. U metodi gradijenta koji se razmatra u nastavku, pravac spuštanja od tačke se direktno bira. Dakle, prema metodi gradijenta

Postoji razne načine odabir koraka, od kojih svaki postavlja odredjenu varijantu metod gradijenta.

1. Metoda najstrmijeg spuštanja.

Razmotrite funkciju jedne skalarne varijable i odaberite kao vrijednost za koju je jednakost

Ova metoda, koju je 1845. godine predložio O. Cauchy, danas se naziva metodom najstrmijeg spuštanja.

Na sl. 10.5 prikazuje geometrijsku ilustraciju ove metode za minimiziranje funkcije dvije varijable. Od početne tačke, okomito na liniju nivoa u pravcu, spuštanje se nastavlja sve dok se ne postigne minimalna vrednost funkcije duž zraka. U pronađenoj tački ova zraka dodiruje liniju nivoa. Zatim se od tačke spušta u smjeru okomitom na liniju nivoa sve dok odgovarajući snop ne dodirne liniju nivoa koja prolazi kroz ovu tačku u tački itd.

Napominjemo da pri svakoj iteraciji izbor koraka podrazumijeva rješenje jednodimenzionalnog problema minimizacije (10.23). Ponekad se ova operacija može izvesti analitički, na primjer, za kvadratna funkcija.

Primjenjujemo metodu najstrmijeg spuštanja kako bismo minimizirali kvadratnu funkciju

sa simetričnom pozitivno određenom matricom A.

Prema formuli (10.8), u ovom slučaju, dakle, formula (10.22) izgleda ovako:

primetite, to

Ova funkcija je kvadratna funkcija parametra a i dostiže minimum pri takvoj vrijednosti za koju

Dakle, primijenjeno na minimizaciju kvadrata

funkcija (10.24), metoda najstrmijeg spuštanja je ekvivalentna proračunu po formuli (10.25), gdje je

Napomena 1. Pošto se minimalna tačka funkcije (10.24) poklapa sa rešenjem sistema, metoda najstrmijeg spuštanja (10.25), (10.26) se takođe može koristiti kao iterativni metod rješenja linearnih sistema algebarske jednačine sa simetričnim pozitivnim određenim matricama.

Napomena 2. Imajte na umu da je gdje je Rayleighova relacija (vidi § 8.1).

Primjer 10.1. Primjenjujemo metodu najstrmijeg spuštanja kako bismo minimizirali kvadratnu funkciju

Imajte na umu da nam je, dakle, tačna vrijednost minimalne točke unaprijed poznata. Hajde da zapišemo ovu funkciju u obliku (10.24), gdje su matrica i vektor Kao što je lako vidjeti,

Uzimamo početnu aproksimaciju i proračune ćemo izvršiti pomoću formula (10.25), (10.26).

I iteracija.

II iteracija.

Može se pokazati da će se za sve na iteraciji dobiti vrijednosti

Imajte na umu da sa Dakle,

sekvenca dobijena metodom najstrmijeg spuštanja konvergira velikom brzinom geometrijska progresija, čiji imenilac

Na sl. 10.5 prikazuje tačno putanju spuštanja koja je dobijena u ovom primjeru.

Za slučaj minimiziranja kvadratne funkcije vrijedi sljedeće ukupni rezultat.

Teorema 10.1. Neka je A simetrična pozitivno određena matrica i neka je kvadratna funkcija (10.24) minimizirana. Tada, za bilo koji izbor početne aproksimacije, metoda najstrmijeg spuštanja (10.25), (10.26) konvergira i sljedeća procjena greške je tačna:

Ovdje i Lado su minimalne i maksimalne vlastite vrijednosti matrice A.

Imajte na umu da ova metoda konvergira brzinom geometrijske progresije, čiji nazivnik, osim toga, ako su blizu, onda je mali i metoda konvergira prilično brzo. Na primjer, u primjeru 10.1 imamo i, prema tome, If Asch, onda 1, i treba očekivati ​​da metoda najstrmijeg spuštanja polako konvergira.

Primjer 10.2. Primjena metode najstrmijeg spuštanja za minimiziranje kvadratne funkcije u početnoj aproksimaciji daje niz aproksimacija gdje je putanja spuštanja prikazana na Sl. 10.6.

Niz ovdje konvergira brzinom geometrijske progresije, čiji je imenilac, tj., mnogo sporiji,

nego u prethodnom primjeru. Pošto se ovdje dobijeni rezultat u potpunosti slaže sa procjenom (10.27).

Napomena 1. Formulisali smo teoremu o konvergenciji metode najstrmijeg spuštanja u slučaju kada je ciljna funkcija kvadratna. AT opšti slučaj, ako je funkcija koja se minimizira strogo konveksna i ima minimalnu tačku x, tada također, bez obzira na izbor početne aproksimacije, niz dobiven ovom metodom konvergira na x na . U ovom slučaju, nakon pada u dovoljno malu okolinu minimalne tačke, konvergencija postaje linearna i nazivnik odgovarajuće geometrijske progresije se procjenjuje odozgo po vrijednosti i gdje su i minimum i maksimum sopstvene vrijednosti Hesove matrice

Napomena 2. Za kvadratnu ciljnu funkciju (10.24) rješenje jednodimenzionalnog problema minimizacije (10.23) može se naći u obliku jednostavne eksplicitne formule (10.26). Međutim, za većinu drugih nelinearne funkcije to se ne može učiniti, a za proračun metodom najstrmijeg spuštanja treba se prijaviti numeričke metode jednodimenzionalne minimizacije tipa opisanog u prethodnom poglavlju.

2. Problem "jaruga".

Iz gornje rasprave slijedi da metoda gradijenta konvergira prilično brzo ako su površine nivoa za minimiziranu funkciju blizu sfera (kada su linije nivoa blizu krugova). Za takve funkcije i 1. Teorema 10.1, primjedba 1 i rezultat primjera 10.2 pokazuju da stopa konvergencije naglo opada kao vrijednost . U dvodimenzionalnom slučaju, reljef odgovarajuće površine podsjeća na teren sa jarugom (sl. 10.7). Stoga se takve funkcije obično nazivaju jarugama. Duž pravaca koji karakteriziraju "dno jaruge" funkcija jaruge se neznatno mijenja, dok se u ostalim pravcima koji karakteriziraju "padinu jaruge" dolazi do oštre promjene funkcije.

Ako početna tačka padne na "padinu jaruge", tada se ispostavlja da je smjer gradijenta gotovo okomit na "dno jaruge", a sljedeća aproksimacija pada na suprotnu "padinu jaruge". Sljedeći korak prema "dnu jaruge" vraća prilaz prvobitnoj "padini jaruge". Kao rezultat toga, umjesto da se kreće duž „dna jaruge“ prema minimalnoj tački, putanja spuštanja čini cik-cak skokove preko „jaruge“, gotovo da se ne približava cilju (slika 10.7).

Da bi se ubrzala konvergencija metode gradijenta uz minimiziranje funkcija jaruga, razvijen je niz posebnih metoda "jaruga". Hajde da damo ideju o jednoj od najjednostavnijih metoda. Sa dvije bliske početne tačke, pravi se nagibni spust do "dna jaruge". Kroz pronađene tačke povučena je ravna linija duž koje se pravi veliki korak "jaruga" (slika 10.8). Od ovako pronađene tačke ponovo se pravi jedan korak gradijentnog spuštanja do tačke, a zatim se pravi drugi "jaruški" korak duž prave linije koja prolazi kroz tačke . Kao rezultat toga, kretanje duž "dna jaruge" do minimalne točke značajno je ubrzano.

Više detaljne informacije o problemu metoda "jaruga" i "jaruga" mogu se naći, na primjer, u , .

3. Drugi pristupi određivanju koraka spuštanja.

Kao što je lako razumjeti, pri svakoj iteraciji bilo bi poželjno odabrati smjer spuštanja blizak smjeru kojim kretanje vodi od tačke do tačke x. Nažalost, antigradijent (po pravilu je nesrećan pravac spuštanja. Ovo je posebno izraženo za funkcije jaruge. Stoga se sumnja u uputnost temeljnog traženja rješenja za jednodimenzionalni problem minimizacije (10.23) a postoji želja da se napravi samo takav korak u pravcu koji bi obezbedio "značajno smanjenje" funkcije. Štaviše, u praksi se ponekad zadovoljava definisanjem vrednosti koja jednostavno obezbeđuje smanjenje vrednosti cilja. funkcija.

Gauss-Seidelova metoda

Metoda se sastoji u naizmjeničnom pronalaženju parcijalnih ekstrema ciljne funkcije za svaki faktor. Istovremeno, u svakoj fazi, (k-1) faktori se stabilizuju i samo jedan i-ti faktor varira

Procedura proračuna: u lokalnom području faktorskog prostora, na osnovu preliminarnih eksperimenata, odabire se tačka koja odgovara najbolji rezultat proces, a odatle počinju da se kreću ka optimumu. Korak kretanja za svaki faktor postavlja istraživač. Prvo se svi faktori fiksiraju na istom nivou i jedan faktor se mijenja sve dok ne dođe do povećanja (smanjenja) funkcije odziva (Y), zatim se mijenja drugi faktor dok se ostali stabiliziraju itd. željeni rezultat(Y). Glavna stvar je odabrati pravi korak za svaki faktor.

Ova metoda je najjednostavnija, najilustrativnija, ali je kretanje do optimuma dugo i metoda rijetko vodi do optimalne točke. Trenutno se ponekad koristi u mašinskom eksperimentu.

Ove metode omogućavaju kretanje do optimuma duž prave linije okomito na linije jednakog odziva, odnosno u smjeru gradijenta funkcije odziva.

Gradijentne metode imaju nekoliko varijanti koje se razlikuju po pravilima za izbor koraka varijacije i radnih koraka u svakoj fazi kretanja do ekstrema.

Suština svih metoda je sljedeća: u početku, na osnovu preliminarnih eksperimenata, bazna tačka. Zatim se u svakoj fazi organiziraju probni eksperimenti oko sljedeće bazne tačke, čiji rezultati procjenjuju novi smjer gradijenta, nakon čega se radi jedan radni korak u tom smjeru.

Metoda gradijenta (normalna) provodi se prema sljedećoj shemi:

a) izabrati baznu tačku;

b) odabrati korake kretanja za svaki faktor;

c) odrediti koordinate ispitnih tačaka;

d) sprovesti eksperimente na ispitnim tačkama. Kao rezultat, vrijednosti parametra optimizacije (Y) se dobijaju u svakoj tački.

e) na osnovu rezultata eksperimenata izračunavaju se procjene komponenti vektora gradijenta u tački M za svaki i-ti faktor:

gdje je H i korak kretanja duž X i .

X i – koordinate prethodne radne tačke.

g) koordinate ove radne tačke se uzimaju kao nova bazna tačka, oko koje se izvode eksperimenti na ispitnim tačkama. Gradijent se izračunava, i tako dalje, sve dok se ne postigne željeni parametar optimizacije (Y). Korekcija smjera kretanja vrši se nakon svakog koraka.

Prednosti metode: jednostavnost, veća brzina kretanja do optimuma.

Nedostaci: visoka osjetljivost na smetnje. Ako kriva ima složenog oblika, metoda možda neće dovesti do optimalnog. Ako je kriva odgovora ravna, metoda je neefikasna. Metoda ne daje informacije o interakciji faktora.

a) Metoda strmog uspona (Box-Wilson).

b) Donošenje odluka nakon strmog uspona.

c) Metoda Simpleksne optimizacije.

d) Prednosti i nedostaci metoda.

5.7.3 Metoda strmog uspona (Box-Wilson)

Ova metoda je sinteza najbolje karakteristike Gradijentne metode, Gauss-Seidelova metoda i PFE i DFE metode - kao sredstvo za dobijanje matematičkog modela procesa. Rješenje optimizacijskog problema ovom metodom izvodi se na način da se koračno kretanje odvija u smjeru najbržeg povećanja (smanjenja) parametra optimizacije. Korekcija smjera kretanja (za razliku od gradijentnih metoda) se ne vrši nakon svakog koraka, već nakon postizanja određenog ekstremuma ciljne funkcije. Dalje, na tačkama parcijalnog ekstremuma postavlja se novi faktorski eksperiment, novi matematički model i opet se strmi uspon ponavlja sve dok se ne postigne globalni optimum. Kretanje duž gradijenta počinje od nulte tačke (centra plana).

Metoda strmog uspona uključuje kretanje prema optimumu duž gradijenta.

Gdje i,j,k-jedinični vektori u smjeru odgovarajućih koordinatnih osa.

Procedura izračunavanja.

Početni podaci su matematički model procesa dobiven bilo kojom metodom (PFE, DFE, itd.).

Proračuni se vrše sljedećim redoslijedom:

a) bolje je prevesti jednadžbu regresije u prirodni oblik koristeći formule kodiranja varijabli:

gdje x i -kodirana vrijednost varijable x i ;

X i - prirodna vrijednost varijable x i ;

X i C - centralni nivo faktora u njegovom prirodnom obliku;

l i - interval varijacije faktora x i u prirodnom obliku.

b) izračunajte korake kretanja do optimuma za svaki faktor.

Da biste to učinili, izračunajte proizvode koeficijenata regresijske jednadžbe u prirodnom obliku prema odgovarajućim intervalima varijacije

B i *.l I ,

Zatim se od rezultirajućih proizvoda bira maksimalni modul, a faktor koji odgovara ovom proizvodu uzima se kao osnovni faktor (B a l a). Za osnovni faktor treba podesiti korak kretanja, za koji se preporučuje da bude manji ili jednak intervalu varijacija osnovnog faktora

Predznak koraka kretanja l a ’ mora odgovarati predznaku koeficijenta regresijske jednadžbe koji odgovara osnovnom faktoru (B a). Vrijednost koraka za ostale faktore izračunava se proporcionalno osnovnoj prema formuli:

Znakovi koraka kretanja također moraju odgovarati predznacima odgovarajućih koeficijenata regresijske jednačine.

c) funkcija odziva se izračunava u centru plana, odnosno sa vrijednostima faktora jednakim centralnom nivou faktora, budući da kretanje prema optimumu počinje od centra plana.

Zatim se izračunava parametar optimizacije, povećavajući vrijednosti faktora za vrijednost odgovarajućeg koraka kretanja, ako želite da dobijete Y max. Inače, ako je potrebno dobiti Y min, vrijednosti faktora se smanjuju za vrijednost koraka kretanja.

Postupak se ponavlja, sukcesivno povećavajući broj koraka dok se ne postigne željena vrijednost parametra optimizacije (Y). Svaki od faktora nakon g bit će bitni koraci:

Ako Y® max X i \u003d X i c + gl i ` '

ako Y® min . X i \u003d X i c -gl i `.(5.36)

Metoda gradijenta i njene varijante su među najčešćim metodama za pronalaženje ekstrema funkcija nekoliko varijabli. Ideja metode gradijenta je da se svaki put kreće u pravcu najvećeg povećanja ciljne funkcije u procesu traženja ekstrema (za definiciju maksimuma).

Metoda gradijenta uključuje izračunavanje prvih izvoda ciljne funkcije u odnosu na njene argumente. On se, kao i prethodni, odnosi na približne metode i omogućava, po pravilu, da se ne postigne optimalna tačka, već samo da joj se približi za konačan broj stepenice.

Rice. 4.11.

Rice. 4.12.

(dvodimenzionalno kućište)

Prvo odaberite početnu točku Ako je u jednodimenzionalnom slučaju (vidi pododjeljak 4.2.6) iz nje bilo moguće

kretati se samo lijevo ili desno (vidi sliku 4.9), tada je u višedimenzionalnom slučaju broj mogućih smjerova kretanja beskonačno velik. Na sl. 4.11, ilustrujući slučaj dve varijable, strelice koje izlaze iz početne tačke ALI, prikazivanje raznih mogućim pravcima. Istovremeno, kretanje duž nekih od njih daje povećanje vrijednosti funkcije cilja u odnosu na tačku ALI(na primjer upute 1-3), a u drugim smjerovima dovodi do njegovog smanjenja (smjerovi 5-8). S obzirom da je pozicija optimalne tačke nepoznata, najboljim se smatra smjer u kojem se ciljna funkcija najbrže povećava. Ovaj pravac se zove gradijent funkcije. Imajte na umu da u svakoj tački koordinatna ravan smjer gradijenta je okomit na tangentu na liniju nivoa povučenu kroz istu tačku.

AT matematička analiza dokazano je da su komponente vektora gradijenta funkcije at =/(*, x 2, ..., x n) su njegovi parcijalni derivati ​​u odnosu na argumente, tj.

&ad/(x 1 ,x 2 ,.= (du / dhu, dy / dx 2 , ..., dy / dx p ). (4.20)

Dakle, pri traženju maksimuma metodom gradijenta, na prvoj iteraciji, komponente gradijenta se računaju prema formulama (4.20) za početnu tačku i radi se radni korak u pronađenom pravcu, tj. tranzicija je napravljena na nova tačka -0)

Y" sa koordinatama:

1§gas1/(x (0)),

ili u vektorskom obliku

gdje X- trajno ili varijabilni parametar, koji određuje dužinu radnog koraka, ?i>0. U drugoj iteraciji, ponovo izračunajte

vektor gradijenta je već za novu tačku Y, nakon čega, analogno

formula ide do tačke x^ > itd. (Sl. 4.12). Za proizvoljno do- iteraciju imamo

Ako se ne traži maksimum, već minimum ciljne funkcije, tada se pri svakoj iteraciji pravi korak u smjeru suprotnom od smjera gradijenta. Zove se pravac protiv gradijenta. Umjesto formule (4.22), u ovom slučaju će biti

Postoji mnogo varijanti metode gradijenta, koje se razlikuju po izboru radnog koraka. Moguće je, na primjer, otići do svake sljedeće tačke na konstantna vrijednost x, i onda

dužina radnog koraka je rastojanje između susednih tačaka x^

njihov 1 "- će biti proporcionalan modulu vektora gradijenta. Možete, naprotiv, na svakoj iteraciji izabrati X tako da dužina radnog koraka ostane konstantna.

Primjer. Potrebno je pronaći maksimum funkcije

y \u003d 110-2 (lg, -4) 2 -3 (* 2 -5) 2.

Naravno, korišćenjem neophodno stanje ekstremu, odmah dobijamo željeno rešenje: X ] - 4; x 2= 5. Međutim, o ovome jednostavan primjer zgodno je demonstrirati algoritam metode gradijenta. Izračunajmo gradijent funkcije cilja:

grad y \u003d (du / dx-, dy / dx 2) \u003d(4(4 - *,); 6(5 - x 2)) i odaberite početnu tačku

A*» = (x)°> = 0; 4°> = O).

Vrijednost funkcije cilja za ovu tačku, kako je lako izračunati, jednaka je y[x^ j = 3. Neka X= const = 0,1. Vrijednost gradijenta u tački

3c (0) je jednako gradu y|x^j = (16; 30). Tada na prvoj iteraciji, prema formulama (4.21), dobijamo koordinate tačke

x 1)= 0 + 0,1 16 = 1,6; x^ = 0 + 0,1 30 = 3.

y (x (1)) = 110 - 2 (1,6 - 4) 2 - 3 (3 - 5) 2 = 86,48.

Kao što vidite, značajno je veća od prethodne vrijednosti. U drugoj iteraciji imamo po formulama (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;