Danzigova metoda. Problem transportnog tipa poseban je slučaj problema linearnog programiranja

1. Koje su tvrdnje netočne? Danzigova metoda

Odgovor: može se klasificirati kao gradijent

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

Odgovor: LP problem s nekonzistentnim sustavom ograničenja naziva se otvorenim

3. Koje od navedenih metoda nisu aktivne

Odgovor: zlatni rez

4. Koje su od sljedećih tvrdnji točne:

Odgovor: problem tipa transporta poseban je slučaj problema linearno programiranje

5. Koje su od sljedećih tvrdnji točne: Metoda najmanjih kvadrata

Odgovor: u konačnici se svodi na rješavanje sustava n linearne jednadžbe pri aproksimaciji rezultata polinomima n-tog reda

6. Koje od sljedećih metoda nisu gradijentne

Odgovor: simpleks metoda (Nelder-Mead metoda)

7. Koja od ovih metoda omogućuje pronalaženje globalnog ekstrema multimodalne funkcije

Odgovor: skenira

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

Odgovor: tangenta

9. Provjerite točne tvrdnje

Odgovor: metoda grube sile ne može se koristiti za pronalaženje ekstrema prema Gauss-Seidelovom postupku

10. Navedite točnu tvrdnju

Odgovor: bilo koji plan se zove valjano rješenje zadaci

11. Navedite netočnu tvrdnju

Odgovor: ravnina koja sadrži barem jednu kutnu točku konveksni poliedar naziva se referentna ravnina tog poliedra

12. Označite brojevima točne tvrdnje

Odgovor: problemi transportnog tipa ne mogu se rješavati Danzigovom metodom jer spadaju u probleme diskretnog programiranja (1). Izvorni plan u simpleks metodi dobivamo da su sve osnovne varijable jednake nuli (3)

13. Odredi točnu tvrdnju?

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

14. Što je od sljedećeg netočno:

Odgovor: bilo koja točka na liniji je konveksna linearna kombinacija dviju točaka kroz koje je ta linija povučena

15. Koja je od dolje navedenih tvrdnji točna?

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

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

Odgovor: jedan od glavnih problema optimizacije je "problem dimenzionalnosti"

17. Što je netočno u gornjim tvrdnjama?

Odgovor: Ako funkcija cilja LP problema dosegne ekstrem u nekoliko točaka, tada ona doseže istu vrijednost u bilo kojoj točki koja je konveksna linearna kombinacija tih točaka.

18. Koja je od sljedećih tvrdnji netočna?

Odgovor: Problem LP može se riješiti postupkom za uredan prijelaz s jednog plana na drugi.

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

Odgovor: ne može postojati ekstrem u području mogućih rješenja problema LP

20. Što je od sljedećeg netočno?

Odgovor: Za pronalaženje ekstrema linearne ciljna funkcija koristeći simplex metodu, potrebno je izvršiti n-m iteracija, n je broj nepoznanica problema, m je broj općih ograničenja

Gradijentne metode traženje optimuma funkcije cilja temelje se na uporabi dvaju osnovna svojstva funkcija gradijenta.

1. Gradijent funkcije je vektor koji u svakoj točki domene definiranosti funkcije
usmjerena normalno na ravnu površinu povučena kroz ovu točku.

Gradijentne projekcije
na koordinatnoj osi jednaki su parcijalnim izvodnicama funkcije
prema odgovarajućim varijablama, tj.

. (2.4)

Gradijentne metode uključuju: relaksacijsku metodu, gradijentnu metodu, metodu najvećeg spuštanja i niz drugih.

Pogledajmo neke od metoda gradijenta.

Metoda gradijenta

Kod ove metode spuštanje se provodi u smjeru najbrže promjene funkcije cilja, što prirodno ubrzava proces pronalaženja optimuma.

Potraga za optimumom provodi se u dvije faze. U prvoj fazi pronalaze se vrijednosti parcijalnih derivacija u odnosu na sve nezavisne varijable koje određuju smjer gradijenta u predmetnoj točki. U drugom stupnju radi se korak u smjeru suprotnom od smjera gradijenta (pri traženju minimuma funkcije cilja).

Kada se korak izvrši, vrijednosti svih nezavisnih varijabli se mijenjaju istovremeno. Svaki od njih dobiva inkrement proporcionalan odgovarajućoj komponenti gradijenta duž zadane osi.

Formulacijski zapis algoritma može izgledati ovako:

,
. (2.5)

U ovom slučaju, veličina koraka
pri konstantnoj vrijednosti parametra h automatski se mijenja s promjenama vrijednosti gradijenta i smanjuje se približavanjem optimumu.

Druga formula za algoritam je:

,
. (2.6)

Ovaj algoritam koristi normalizirani vektor gradijenta koji pokazuje samo smjer najbrže promjene funkcije cilja, ali ne pokazuje brzinu promjene u tom smjeru.

U strategiji koraka promjene
u ovom slučaju koristi se da gradijenti
I
razlikuju po smjeru. Korak pretraživanja mijenja se u skladu s pravilom:

(2.7)

Gdje
– kut rotacije gradijenta na k-tom koraku, određen izrazom

,

,
– dopuštene granice kuta zakretanja gradijenta.

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

Trenutak završetka pretrage može se pronaći provjerom na svakom koraku relacije

,

Gdje – navedena pogreška izračuna.

Riža. 2.1. Priroda kretanja prema optimumu u gradijentnoj metodi s velikim korakom

Nedostatak metode gradijenta je što se pri njenoj uporabi može detektirati samo lokalni minimum funkcije cilja. Da bi se pronašli drugi lokalni minimumi za funkciju, potrebno je tražiti iz drugih polazišta.

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

Metoda najstrmijeg spusta

Kod primjene metode gradijenta u svakom koraku potrebno je odrediti vrijednosti parcijalnih derivacija funkcije koja se optimizira u odnosu na sve nezavisne varijable. Ako je broj nezavisnih varijabli značajan, tada se volumen izračuna značajno povećava i vrijeme potrebno za pronalaženje optimuma se povećava.

Smanjenje količine izračuna može se postići metodom najvećeg spuštanja.

Suština metode je sljedeća. Nakon što je pronađen gradijent optimizirane funkcije u početnoj točki i određen smjer njegovog najbržeg pada u navedenoj točki, u tom se smjeru radi korak spuštanja (slika 2.2).

Ako vrijednost funkcije opadne kao rezultat ovog koraka, poduzima se još jedan korak u istom smjeru, i tako dalje dok se ne nađe minimum u tom smjeru, nakon čega se izračunava gradijent i novi smjer najbržeg pada određena je funkcija cilja.

Riža. 2.2. Priroda kretanja prema optimumu u metodi najvećeg spuštanja (–) i metodi gradijenta (∙∙∙∙)

U usporedbi s metodom gradijenta, metoda najvećeg spuštanja ima prednost zbog smanjenja količine izračuna.

Bitna značajka metode najstrmijeg spuštanja je da je pri njenoj primjeni svaki novi smjer kretanja prema optimumu okomit na prethodni. To se objašnjava činjenicom da se kretanje u jednom smjeru provodi sve dok smjer kretanja nije tangentan na bilo koju liniju konstantne razine.

Isti uvjet kao u gore navedenoj metodi može se koristiti kao kriterij za završetak pretrage.

Osim toga, možete također uzeti uvjet završetka pretraživanja u obliku relacije

,

Gdje
I
– koordinate početne i završne točke posljednjeg segmenta spuštanja. Isti kriterij može se koristiti u kombinaciji s praćenjem vrijednosti funkcije cilja u točkama
I

.

Zajednička primjena uvjeta završetka pretraživanja opravdana je u slučajevima kada funkcija koja se optimizira ima jasno definiran minimum.

Riža. 2.3. Za određivanje kraja potrage u metodi najvećeg spuštanja

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

Razmotrimo problem bezuvjetne minimizacije diferencijabilne funkcije mnogih varijabli. Neka se vrijednost gradijenta u točki približi minimalnoj točki funkcija je dana antigradijentom Ovo svojstvo se značajno koristi u brojnim metodama minimizacije. U metodi gradijenta koja se razmatra u nastavku, smjer spuštanja od točke se bira izravno prema metodi gradijenta

postojati razne načine odabir koraka, od kojih svaki specificira specifična opcija metoda gradijenta.

1. Metoda najstrmijeg spusta.

Promotrimo funkciju jedne skalarne varijable i izaberimo kao vrijednost za koju jednakost vrijedi

Ovu metodu, koju je 1845. predložio O. Cauchy, danas se obično naziva metoda najstrmijeg spuštanja.

Na sl. Slika 10.5 prikazuje geometrijsku ilustraciju ove metode za minimiziranje funkcije dviju varijabli. Od početne točke okomite na niveletu u smjeru spuštanja nastavlja se spuštanje dok se ne postigne minimalna vrijednost funkcije duž zrake. U pronađenoj točki ta zraka dotakne niveletu, zatim se od točke izvodi spuštanje u smjeru okomitom na niveletu sve dok odgovarajuća zraka ne dotakne niveletu koja prolazi kroz tu točku, itd.

Imajte na umu da u svakoj iteraciji izbor koraka uključuje rješavanje jednodimenzionalnog problema minimizacije (10.23). Ponekad se ova operacija može izvesti analitički, na primjer za kvadratna funkcija.

Upotrijebimo metodu najvećeg spuštanja da minimiziramo kvadratnu funkciju

sa simetričnom pozitivno određenom matricom A.

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

primijeti da

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

Dakle, u odnosu na minimiziranje kvadratnog

funkcija (10.24), metoda najvećeg spuštanja ekvivalentna je izračunu pomoću formule (10.25), gdje

Napomena 1. Budući da se minimalna točka funkcije (10.24) podudara s rješenjem sustava, metoda najvećeg spuštanja (10.25), (10.26) također se može koristiti kao iterativna metoda rješenja linearnih sustava algebarske jednadžbe sa simetričnim pozitivno određenim matricama.

Opaska 2. Primijetite gdje je Rayleighov omjer (vidi § 8.1).

Primjer 10.1. Upotrijebimo metodu najvećeg spuštanja da minimiziramo kvadratnu funkciju

Imajte na umu da, dakle, unaprijed znamo točnu vrijednost minimalne točke. Zapišimo to ovu funkciju u obliku (10.24), gdje je matrica i vektor As lako vidjeti,

Uzmimo početnu aproksimaciju i izvršimo izračune pomoću formula (10.25), (10.26).

I iteracija.

II ponavljanje.

Može se pokazati da će se za sve iteracije dobiti vrijednosti

Imajte na umu da za Dakle,

niz dobiven metodom najstrmijeg spuštanja konvergira s brzinom geometrijska progresija, čiji je nazivnik

Na sl. Slika 10.5 prikazuje točno putanju spuštanja koja je dobivena u ovom primjeru.

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

Teorem 10.1. Neka je A simetrična pozitivno određena matrica i neka je kvadratna funkcija (10.24) minimizirana. Zatim, za bilo koji izbor početne aproksimacije, metoda najvećeg spuštanja (10.25), (10.26) konvergira i sljedeća procjena pogreške je točna:

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

Imajte na umu da ova metoda konvergira brzinom geometrijske progresije, čiji je nazivnik, ako su blizu, mali i metoda konvergira prilično brzo. Na primjer, u primjeru 10.1 imamo i stoga Ako je Aschakh, onda 1 i trebali bismo očekivati ​​sporu konvergenciju metode najvećeg spuštanja.

Primjer 10.2. Primjena metode najvećeg spuštanja za minimiziranje kvadratne funkcije tijekom početne aproksimacije daje niz aproksimacija gdje je putanja spuštanja prikazana na sl. 10.6.

Niz ovdje konvergira brzinom geometrijske progresije, čiji je nazivnik jednak, tj. znatno sporiji,

Isprobat ću ga više nego u prethodnom. Budući da je ovdje dobiveni rezultat sasvim u skladu s procjenom (10.27).

Napomena 1. Formulirali smo teorem o konvergenciji metode najstrmijeg spuštanja u slučaju kada je funkcija cilja kvadratna. U opći slučaj, ako je funkcija koju treba minimizirati strogo konveksna i ima minimalnu točku x, tada također, bez obzira na izbor početne aproksimacije, niz dobiven ovom metodom konvergira k x na . U ovom slučaju, nakon ulaska u dovoljno malu okolinu minimalne točke, konvergencija postaje linearna i nazivnik odgovarajuće geometrijske progresije procjenjuje se odozgo vrijednošću i gdje su i minimum i maksimum svojstvene vrijednosti Hessianove matrice

Napomena 2. Za kvadratnu funkciju cilja (10.24), rješenje jednodimenzionalnog problema minimizacije (10.23) može se pronaći u obliku jednostavne eksplicitne formule (10.26). Međutim, za većinu drugih nelinearne funkcije To se ne može učiniti i za izračunavanje najstrmijeg spusta morate koristiti metodu numeričke metode jednodimenzionalna minimizacija tipa o kojem se raspravljalo u prethodnom poglavlju.

2. Problem "jaruga".

Iz gornje rasprave slijedi da metoda gradijenta konvergira prilično brzo ako su, za funkciju koja se minimizira, površine ravni blizu sfera (ako su linije razine blizu krugova). Za takve funkcije i 1. Teorem 10.1, primjedba 1, kao i rezultat primjera 10.2 pokazuju da stopa konvergencije naglo opada kako se vrijednost povećava. Doista, poznato je da metoda gradijenta konvergira vrlo sporo ako površine razine funkcija koja se minimizira jako je izdužena u nekim smjerovima. U dvodimenzionalnom slučaju, reljef odgovarajuće površine nalikuje terenu s klancem (slika 10.7). Stoga se takve funkcije obično nazivaju gully funkcije. Duž smjerova koji karakteriziraju "dno jaruge", funkcija jaruge se neznatno mijenja, ali u drugim smjerovima koji karakteriziraju "padinu jaruge", dolazi do oštre promjene funkcije.

Ako početna točka pada na "padinu klanca", tada se ispostavlja da je smjer gradijentnog spuštanja gotovo okomit na "dno klanca", a sljedeći pristup pada na suprotnu "padinu klanca". Sljedeći korak prema “dnu jaruge” vraća pristup izvornoj “padini jaruge”. Kao rezultat toga, umjesto da se kreće duž "dna klanca" prema minimalnoj točki, putanja spuštanja čini cik-cak skokove preko "jaruge", gotovo nikada ne približavajući se cilju (Sl. 10.7).

Kako bi se ubrzala konvergencija gradijentne metode uz minimiziranje gully funkcija, razvijen je niz posebnih "gully" metoda. Dajmo ideju jedne od najjednostavnijih tehnika. S dviju bliskih polaznih točaka spuštaju se strmoglavo do “dna klanca”. Kroz pronađene točke povlači se ravna crta duž koje se pravi veliki "jarak" (Sl. 10.8). Od tako pronađene točke, jedan korak gradijenta se ponovno poduzima do točke, a zatim se poduzima drugi korak "jarak" duž ravne linije koja prolazi kroz točke. Kao rezultat toga, kretanje duž "dna klanca" do minimalne točke značajno se ubrzava.

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

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

Kao što je lako razumjeti, pri svakoj iteraciji bilo bi poželjno odabrati smjer spuštanja blizak smjeru po kojem kretanje vodi od točke do točke x. Nažalost, antigradijent (je u pravilu neuspješan smjer spuštanja. To je posebno izraženo kod vododerinskih funkcija. Stoga se postavlja sumnja u svrhovitost temeljitog traženja rješenja problema jednodimenzionalne minimizacije (10.23) i postoji želja da se učini samo takav korak u smjeru koji bi osigurao "značajno smanjenje" funkcije Štoviše, u praksi se ponekad zadovoljava definiranjem vrijednosti koja jednostavno osigurava smanjenje vrijednosti funkcije cilja.

Gauss-Seidel metoda

Metoda se sastoji u naizmjeničnom pronalaženju parcijalnih ekstrema funkcije cilja za svaki faktor. U isto vrijeme, u svakoj fazi (k-1) faktori se stabiliziraju i samo jedan i-ti faktor se mijenja

Postupak izračuna: u lokalnom području faktorskog prostora, na temelju preliminarnih eksperimenata, odaberite točku koja odgovara najbolji rezultat procesa, a odatle se počinju kretati prema optimumu. Korak kretanja za svaki faktor postavlja istraživač. Prvo, svi faktori su fiksirani na istoj razini i jedan faktor se mijenja dok ne dođe do porasta (smanjenja) u funkciji odgovora (Y), zatim se drugi faktor mijenja kada se ostali stabiliziraju, itd. dok se ne dobiju željeni rezultat(Y). Glavna stvar je odabrati pravi korak kretanja za svaki faktor.

Ova metoda je najjednostavnija i najočitija, ali kretanje prema optimumu traje dugo i metoda rijetko dovodi do optimalne točke. Trenutno se ponekad koristi u strojnim eksperimentima.

Ove metode osiguravaju kretanje prema optimumu po ravnoj liniji okomitoj na linije jednakog odziva, odnosno u smjeru gradijenta funkcije odziva.

Gradijentne metode imaju nekoliko varijanti, koje se razlikuju u pravilima za odabir stupnjeva varijacije i radnih koraka u svakoj fazi kretanja prema ekstremumu.

Bit svih metoda je sljedeća: u početku, na temelju preliminarnih eksperimenata, oni odabiru osnovna točka. Zatim se u svakoj fazi organiziraju probni eksperimenti oko sljedeće bazne točke, na temelju čijih se rezultata procjenjuje novi smjer gradijenta, nakon čega se poduzima jedan radni korak u tom smjeru.

Metoda gradijenta (uobičajena) provodi se prema sljedećoj shemi:

a) odaberite baznu točku;

b) odabrati korake kretanja za svaki faktor;

c) odrediti koordinate ispitnih točaka;

d) izvoditi pokuse na pokusnim točkama. Kao rezultat, dobivene su vrijednosti parametra optimizacije (Y) u svakoj točki.

e) na temelju rezultata eksperimenata izračunavaju se procjene komponenata vektorskog gradijenta u t za svaki i-ti faktor:

gdje je H i korak kretanja duž X i.

X i – koordinate prethodne radne točke.

g) koordinate ove radne točke uzimaju se kao nova osnovna točka, oko koje se izvode pokusi na probnim točkama. Izračunajte gradijent itd. dok se ne postigne željeni parametar optimizacije (Y). Nakon svakog koraka korigira se smjer kretanja.

Prednosti metode: jednostavnost, veća brzina kretanja prema optimumu.

Nedostaci: visoka osjetljivost na smetnje. Ako krivulja ima složenog oblika, metoda možda neće dovesti do optimuma. Ako je krivulja odgovora ravna, metoda je neučinkovita. Metoda ne daje informacije o međudjelovanju čimbenika.

a) Metoda strmog uspona (Box - Wilson).

b) Donošenje odluka nakon strmog uspona.

c) Jednostavna optimizacijska metoda.

d) Prednosti i nedostaci metoda.

5.7.3 Metoda strmog uspona (Box-Wilson)

Ova metoda je sinteza Najbolje značajke gradijentne metode, Gauss-Seidelova metoda te PFE i DFE metode - kao način dobivanja matematičkog modela procesa. Optimizacijski problem se ovom metodom rješava tako da se postupno kretanje odvija u smjeru najbržeg porasta (smanjenja) optimizacijskog parametra. Smjer kretanja se prilagođava (za razliku od gradijentnih metoda) ne nakon svakog koraka, već nakon postizanja određenog ekstrema ciljne funkcije. Zatim se u točkama određenog ekstrema provodi novi faktorski pokus, novi matematički model a strmi uspon se opet ponavlja dok se ne postigne globalni optimum. Kretanje duž gradijenta počinje od nulte točke (središte plana).

Metoda strmog uspona uključuje kretanje prema optimalnom usponu.

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

Postupak izračuna.

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

Izračuni se provode sljedećim redoslijedom:

a) bolje je regresijsku jednadžbu prevesti u prirodni oblik pomoću varijabilnih formula za kodiranje:

Gdje x i -kodirana vrijednost varijable x i ;

X i - prirodna vrijednost varijable x i;

X i C je središnja razina faktora u njegovom prirodnom obliku;

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

b) izračunajte korake kretanja prema optimumu za svaki faktor.

Da biste to učinili, izračunajte umnoške koeficijenata regresijske jednadžbe u prirodnom obliku i odgovarajućih intervala varijacije

B i *.l I ,

Zatim se iz dobivenih proizvoda odabire maksimalni modul, a faktor koji odgovara tom produktu uzima se kao osnovni faktor (B a l a). Za osnovni faktor treba postaviti korak kretanja, koji je preporučljivo postaviti manji odn jednaka intervalu varijacija osnovnog faktora

Predznak koraka gibanja l a ’ mora se podudarati s predznakom koeficijenta regresijske jednadžbe koji odgovara baznom faktoru (B a). Veličina koraka za ostale faktore izračunava se proporcionalno osnovnom prema formuli:

Predznaci koraka kretanja također se moraju podudarati s predznacima odgovarajućih koeficijenata regresijske jednadžbe.

c) izračunajte funkciju odziva u središtu plana, tj. za vrijednosti faktora jednake središnjoj razini faktora, budući da kretanje prema optimumu počinje od središta plana.

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

Postupak se ponavlja, uzastopno povećavajući broj koraka dok se ne postigne željena vrijednost optimizacijskog parametra (Y). Svaki od čimbenika nakon g bitni su koraci:

Ako je Y® max X i =X i c +gl i ` ’

ako je Y® min . X i =X i c -gl i ` .(5.36)

Metoda gradijenta i njezine varijacije su među najčešćim metodama traženja ekstrema funkcija više varijabli. Ideja gradijentne metode je da se svaki put kreće u smjeru najvećeg porasta funkcije cilja u procesu traženja ekstrema (kako bi se odredio maksimum).

Metoda gradijenta uključuje izračunavanje prvih izvoda funkcije cilja iz njezinih argumenata. Ona se, kao i prethodne, odnosi na približne metode i omogućuje, u pravilu, da se ne postigne optimalna točka, već samo da joj se približi dalje konačni broj korake.

Riža. 4.11.

Riža. 4.12.

(dvodimenzionalni slučaj)

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

pomicati samo lijevo ili desno (vidi sl. 4.9), tada je u višedimenzionalnom slučaju broj mogućih smjerova kretanja beskonačno velik. Na sl. 4.11, koja ilustrira slučaj dviju varijabli, sa strelicama koje izlaze iz početne točke A, prikazujući razne mogući pravci. Štoviše, kretanje duž nekih od njih daje povećanje vrijednosti funkcije cilja u odnosu na točku A(na primjer, upute 1-3), a u drugim smjerovima dovodi do njegovog smanjenja (smjerovi 5-8). S obzirom da je pozicija optimalne točke nepoznata, najboljim se smatra smjer u kojem funkcija cilja najbrže raste. Ovaj smjer se zove gradijent funkcije. Imajte na umu da u svakoj točki koordinatna ravnina smjer gradijenta je okomit na tangentu na liniju razine povučenu kroz istu točku.

U matematička analiza dokazano je da komponente vektora gradijenta funkcije na =/(*, x 2, ..., x p) su njegove parcijalne derivacije u odnosu na argumente, tj.

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

Dakle, kod traženja maksimuma metodom gradijenta, u prvoj iteraciji se komponente gradijenta izračunavaju pomoću formula (4.20) za početnu točku i radi se radni korak u pronađenom smjeru, tj. prijelaz na nova točka -0)

Y" s koordinatama:

1§gas1/(x (0)),

ili u vektorskom obliku

Gdje X- trajno ili promjenjivi parametar, koji određuje duljinu radnog koraka, ?i>0. U drugoj iteraciji ponovno izračunavaju

vektor gradijenta je već za novu točku.U, nakon čega, po analogiji,

prema formuli idu u točku x^ > itd. (Slika 4.12). Besplatno Do- iteracija koju imamo

Ako se ne traži maksimum, nego minimum funkcije cilja, tada se u svakoj iteraciji poduzima korak u smjeru suprotnom od smjera gradijenta. To se naziva smjerom antigradijenta. Umjesto formule (4.22) u ovom slučaju bit će

Postoji mnogo varijanti metode gradijenta, koje se razlikuju po izboru radnog koraka. Možete, na primjer, prijeći na svaku sljedeću točku kada konstantna vrijednost X, i onda

duljina radnog koraka - udaljenost između susjednih točaka x^

njihov 1 " - bit će proporcionalan veličini vektora gradijenta. Možete, naprotiv, pri svakoj iteraciji odabrati x tako da duljina radnog koraka ostaje konstantna.

Primjer. Moramo pronaći maksimum funkcije

y = 110-2(l, -4) 2 -3(* 2 -5) 2.

Naravno, koristeći nužan uvjet ekstremu, odmah dobivamo željeno rješenje: X ] - 4; x 2= 5. Međutim, na ovom jednostavan primjer Prikladno je demonstrirati algoritam metode gradijenta. Izračunajmo gradijent funkcije cilja:

dipl y = (du/dh-,du/dh 2) =(4(4 - *,); 6(5 - x 2)) i odaberite početnu točku

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

Vrijednost funkcije cilja za ovu točku, kako se lako može izračunati, jednaka je y[x^ j = 3. Pretpostavimo x= konst = 0,1. Vrijednost gradijenta u točki

Zc (0) je jednako gradu y|x^j = (16; 30). Zatim u prvoj iteraciji dobijemo, prema formulama (4.21), koordinate toč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, znatno je veća od prethodne vrijednosti. U drugoj iteraciji iz formula (4.22) imamo:

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