O poveste cu o demonstrație a posibilităților metodei gradientului de a găsi soluția optimă.
Sarcinile de optimizare (găsirea celei mai bune soluții) nu sunt cele mai populare în mediul 1C. Într-adevăr, este un lucru de luat în considerare pentru punerea în aplicare a oricăror decizii, și este chiar o altă problemă de a adopta aceste decizii. Recent, totuși, mi se pare că 1C s-a grăbit să ajungă din urmă cu concurenții în această problemă. Este cu adevărat interesant să combinați sub un singur acoperiș tot ce ar putea fi nevoie de un manager modern, capturarea SAP în această chestiune și înlocuirea MS Project și a altor sisteme de planificare.
Deci, prima temă este metoda de coborâre a gradientului.
Domeniul de aplicare al metodei este orice sarcină de a găsi o matrice de variabile n care să ofere valoarea minimă (maximă) a funcției obiectiv. Funcția obiectiv în acest caz - funcția de cele mai multe dintre aceste variabile n de formă arbitrară - singura condiție impusă metoda funcției obiectiv - continuitatea acestuia, cel puțin pe segmentul la pentru a găsi o soluție. Continuitatea în practică înseamnă că pentru orice combinație de valori ale variabilelor se poate găsi valoarea reală a funcției obiective.
Să prezentăm notația:
- Setul de variabile X pe care depinde valoarea funcției obiective
Și funcția țintă Z în sine, calculată în modul cel mai arbitrar din setul X
Acum, să explicăm ce este un gradient. Un gradient este un vector al unui spațiu multidimensional, indicând direcția celei mai mari creșteri a unei anumite funcții. Componentele gradientului sunt diferențialele tuturor variabilelor funcției Z.
Aceasta este principala limitare a aplicabilității metodei de coborâre a gradientului - diferențiabilitatea (continuitatea) unei funcții în întregul domeniu al căutării soluției. Dacă această condiție este îndeplinită, atunci căutarea unei soluții optime este pur tehnică.
Metoda de coborâre gradientului Classic este implementat pentru a minimiza funcția obiectiv prin antigradient (adică opusă vectorului gradient) care se obține din gradientul în cel mai simplu mod - multiplicarea prin -1 a componentelor de gradient. Sau în notație:
Acum, cea mai importantă întrebare: cum găsim aceste dZ și dX1 foarte. dX2, etc. Este foarte simplu! dXn este o creștere infinitezimală a variabilei Xn. spune 0.0001 din valoarea sa actuală. Sau 0.0000000001 - principalul lucru este că (increment) este foarte mic :)
Și cum se calculează dZ. Prea elementară! Calculăm Z pentru setul de variabile X. și apoi modificăm variabila Xn în acest set de dXn. Din nou, vom calcula valoarea funcției obiectiv Z pentru acest set ușor modificată (Zn), și pentru a găsi diferența - aceasta va dZ = Zn - Z. Și acum știm DXN miza și pentru a găsi dZ dZ / DXN o bucată de tort.
După ce am găsit succesiv toate componentele gradientului și antigradientului, obținem direcția de variație a variabilelor, ceea ce ne va permite să atingem cât mai curând posibil minimul funcției.
În (+ 1 k) etapa următoare, este necesar să se calculeze noile valori ale X. variabile matrice Evident, pentru a ajunge mai aproape de minimul funcției obiectiv Z, trebuie să se adapteze valorile X anterioare (k-lea) pas în antigradient direcția cu această formulă:
Rămâne să înțelegem foarte bine această alfa în formulă. De ce este nevoie și de unde provine.
α este coeficientul prin care se multiplică antigraful pentru a se asigura că minimul posibil al funcției este atins într-o anumită direcție. În sine, un gradient sau o antigrădare nu este o măsură a deplasării unei variabile, dar indică numai direcția mișcării. Sensul geometric al gradientului - este panta tangentei la funcția în punctul Z Xn (raportul piciorului opus unui dZ DXN adiacent), dar se deplasează pe o tangentă, vom se abate în mod inevitabil de la linia de funcție pentru a atinge valoarea minimă. Semnificația tangentei este aceea că dă o cartografiere sub forma unei linii drepte a unei funcții arbitrare, curviinare, într-un cartier foarte restrâns, al punctului Xn.
Căutarea valorii parametrului α se realizează prin una dintre metodele de optimizare unidimensională. Valorile variabilelor ne sunt cunoscute, iar gradienți lor sunt cunoscute - este de a minimiza funcția obiectiv în vecinătatea soluției curente pe un singur parametru: α.
Oprește pe o optimizare unidimensională, eu sunt aici - metodele sunt destul de simplu de înțeles și de a pune în aplicare, cu excepția să spun că am folosit „secțiunea de aur“, metoda în decizia sa. ODZ pentru α este în intervalul de la 0 la 1.
Astfel, rezumând ceea ce am scris, formulam o secvență de pași pentru găsirea unei soluții prin metoda de coborâre a gradientului:
- Formăm soluția inițială de susținere, atribuind variabilele aleatoare variabilelor necesare de la DGD.
- gradienti de descoperire Antigradient pentru fiecare câștig variabilă ca raportul dintre funcția obiectiv cu o creștere relativ mică a valorii variabilei la valoarea sporului variabilei în sine.
- Gasim coeficientul α. Asupra cărora este necesar să multiplicăm antigradienții înainte de a adăuga la valorile inițiale ale soluției suport prin metoda de optimizare unidimensională. Criteriul de optimizare este cea mai mică valoare posibilă a funcției obiective pentru valorile corectate în acest fel.
- Recalculăm în funcție de valorile antigradientului și de coeficientul de schimb α.
- Verificăm dacă precizia necesară (ε) este calculată pentru calcularea minimului funcției obiectiv:
6. În cazul în care este îndeplinită condiția și de la o etapă la valoarea funcției obiectiv a schimbat mai puțin decât ne-am stabilit criteriul, ceea ce înseamnă că se atinge precizia necesară, iar setul curent este o soluție, în caz contrar - treceți la pasul 2.
Acum, hai să trecem la sarcina practică care este rezolvată în procesul de procesare.
În funcție de condiția sarcinii, este necesar să se stabilească prețul pentru o anumită marfă în așa fel încât profitul din vânzarea sa în perioada planificată să fie maxim. Trebuie avut în vedere faptul că volumul vânzărilor depinde de prețul instalat de noi, și prețul de achiziție al bunurilor (care afectează profitul brut) este, de asemenea, depinde de valoarea de cumpărare a bunurilor: furnizorul este dispus să ofere reduceri mai mult, cu atât mai mult va fi suma cumpărăturilor noastre. Asta este, avem nevoie atât de stabilire a prețurilor înțeleagă cât produsul vom fi în măsură să pună în aplicare și la ce preț, și, prin urmare, cât de multe bunuri de care avem nevoie pentru această achiziție, iar atunci vom ști ce va fi prețul de achiziție. În general, o astfel de mică logică recursivă pentru găsirea de soluții :)
Cel mai important lucru pe care o avem - este o variabilă continuă (prețul și volumul de achiziții / vânzări) și funcția obiectiv (profitul este întotdeauna acolo și poate avea orice valoare, chiar dacă este minus, aceasta se numește o pierdere), și, astfel, gradientul metoda de coborâre - pentru este.
Pentru a rezolva problema, această metodă este utilizată de două ori: în prima etapă găsim parametrii ecuației cererii pentru produse în funcție de datele de vânzări din perioadele anterioare. Adică, presupunând un fel de dependență a cererii de preț, se calculează valorile parametrilor care minimizează suma pătratului abaterilor între datele estimate și cele reale de vânzări. În a doua etapă, folosind dependențele constatate între volumul vânzărilor și prețul de vânzare, optimizăm profitul și folosim și metoda de coborâre a gradientului, cel puțin aplicată unei singure variabile. Deoarece metoda de coborâre gradientului pentru a minimiza funcția obiectiv, și profit ca are nevoie de nimic altceva pentru a maximiza, nu folosim tvialnuyu funcție obiectiv numit „MinusPribyl“, care este doar ceea ce face calculează că profitul obținut prețurile de valoare, și înainte de a reveni multiplică-l pe -1 :) Și funcționează! Acum, cu cât devine mai puțin "Minus Profibel", cu atât este mai mult faptul că nici nu este profitul real din vânzări.
Un exemplu de soluție în procesare, cum ar fi funcția de căutare universală a soluției prin metoda coborârii gradientului. Esența universalității este că variabilele îi sunt transmise ca o matrice, iar funcția obiectivă este trecută ca parametru de un șir. Funcția țintă, care ia o serie de variabile și returnează o valoare, scrie orice tip doriți - principalul lucru este că returnează un număr. Și un astfel de număr, cu cât este mai mic, cu cât este mai apropiată matricea de argumente date la soluția optimă.
De ce nu am dat procedura aici și am stabilit tratamentul? În primul rând, procedura este deja prea lungă și, în al doilea rând, nu funcționează fără funcții direcționate, deci este necesar să trageți totul, chiar și în interconectare. Sper că teoria menționată în articol este suficientă pentru a vă putea realiza soluția, poate chiar mai bine decât mine. Ei bine, dacă nu funcționează deloc - descărcați procesarea finală și utilizați-o :)
Descărcați fișiere
Trimiteți-le prietenilor: