Tutorial "scilab"

Curs 5. Probleme de optimizare

Aceasta este cea mai comună clasă de sarcini în practica de inginerie. Într-adevăr, atunci când proiectăm o instalație, o tehnologie sau un proces, ne propunem să minimizăm unele costuri sau sarcini, să maximizăm efectul pozitiv, să scurtăm ciclul de producție sau, dimpotrivă, să-l mărim pentru a obține cei mai buni indicatori de calitate ai produsului.

Observați ce adjective sunt folosite: cea mai mare, maximă, minimă, cea mai bună. Toate acestea caracterizează problemele de optimizare. Calculele economice sunt în general o soluție la astfel de probleme, dintre care unele au devenit deja clasice. De exemplu, problema alocării resurselor, problema vânzătorului călător.

Cred că este evident că sarcinile acestei clase sunt foarte diverse și, prin urmare, necesită abordări fundamental diferite. Pentru creditul Scilab, trebuie remarcat că are un arsenal suficient de instrumente pentru rezolvarea problemelor de optimizare, la care ne cunoaștem.

Minimul local al funcțiilor unei variabile

Ca cea mai simplă problemă de optimizare, considerăm căutarea unui minim local al unei funcții de o variabilă. Sarcina este de a găsi coordonatele punctului minim local al unei funcții date.

Ca și în cazul găsirii rădăcinilor unei ecuații neliniare, soluția este realizată în două etape. În primul rând, trebuie să construim un grafic pentru a verifica existența unui minim și a alege aproximarea inițială pentru abscisa punctului dorit. Apoi se găsește valoarea exactă a coordonatelor punctului minim.

Să luăm în considerare un exemplu concret.

Găsiți funcția minimă

f (x) = x4 + 3 x 3 -13 x 2 -6x + 26

Planificăm funcția pe un interval arbitrar. care pot fi apoi ajustate dacă este necesar.

Se poate observa că funcția are două minime locale, dar pentru o reprezentare mai vizuală este logic să se ia în considerare comportamentul funcției pe un interval mai mic. deoarece "coada" graficului din dreapta nu este foarte informativă.

Punctele minime sunt acum vizibile clar. Primul este în vecinătatea lui -4, al doilea este de aproximativ 2. Pentru a găsi valoarea mai precisă a minimului funcției în Scilab, folosiți comanda

Aici x0 este aproximația inițială. Comanda optimă returnează abscisa punctului minim xmin și valoarea funcției în acest punct fmin. Caracteristica principală a comenzii optim este structura argumentului său principal, funcția distractivă.

Să presupunem că funcția f (x). minimul pe care îl căutăm este dat de comanda deff sau constructul de funcții (așa cum este, pe măsură ce construim graficul). Apoi distracția este definită după cum urmează:

funcție [Fmain, Fdif, ind] = distracție (x, ind)

Fun funcie. Astfel, returnează funcția Fmain și derivatul său Fdif. Nu atingem parametrul ind: este un parametru intern și are nevoie de SciLab pentru a comunica distractiv cu comanda optimă.

Aplicăm acum această informație problemei noastre.

Acum găsim valorile punctelor minime, folosind aproximația inițială explicată anterior.

Astfel, punctele minime din cazul nostru sunt:

(-3,8487884, -95,889413) și (1,8068586, 1,0725284).

Subliniem că principala problemă este alegerea corectă a aproximării inițiale. Dar aceasta nu este o problemă SciLab, ci una matematică.

Rețineți că atunci când stabiliți distracție, funcțiile Fmain și Fdif ar putea fi specificate în mod explicit, dar va trebui să calculați singur derivatul, ceea ce nu este dificil în acest caz.

Rezultatul, desigur, va fi același:

Minimul funcției Rosenbrock

Să trecem la o problemă mai complicată - căutarea unui minim de funcții a mai multor variabile. Pentru claritate, vom vorbi despre o funcție a două variabile.

Formal, abordarea soluției diferă puțin de cea prezentată în secțiunea anterioară. Trebuie luată în considerare doar faptul că argumentul nu este o variabilă, ci un vector x, compus din două elemente x (1) și x (2).

De exemplu, luați în considerare căutarea unui minim de funcție Rosenbrock

Aceasta este o funcție bine-cunoscută datorită specificității sale fiind folosită ca o funcție de testare pentru algoritmi de minimizare.

Începem soluția, firește, cu construirea graficului.

Construirea de grafice tridimensionale

Graficul grafic al funcției a două variabile, definite în cazul nostru, într-o formă explicită, este construit cel mai ușor folosind comanda surf.

Codul este destul de simplu. Mai întâi, setați domeniul de aplicare al modificării argumentelor cu ajutorul comenzii meshgrig. așa-numita rețea. Apoi, valorile funcției se calculează la nodurile acestei grile și, dacă se face corect, comanda de surf furnizează rezultatul dorit.

Vă atragem atenția, deoarece x și y sunt coloane, operațiile element-cu-element ar trebui să fie folosite atunci când scrieți o funcție. În cazul nostru, aceasta este exponentiația: ".

Graficul arată astfel:

Aceasta nu este o funcție a unui argument și este mult mai dificil să se găsească grafic un minim, totuși, în colorare, este clar că în zona aleasă are sens să se caute un minim. Prin urmare, permiteți stabilirea aproximării inițiale (0, 0), deoarece în vecinătatea acestui punct există cea mai neagră culoare.

Găsirea minimului

Se alege aproximarea inițială, se trece la determinarea directă a punctului minim. Pentru comoditatea programării, rescriim funcția Rosenbrock "în termeni de" Scilab.

Deoarece funcția nu este dintr-o variabilă, ci dintr-un vector, este mai ușor să o specificați prin intermediul funcției:

Deoarece numerele sunt deja utilizate aici, mai degrabă decât coloanele valorice, puteți utiliza operatorul obișnuit de exponentiere.

Definim funcția fn exact așa cum am făcut pentru cazul unei funcții a unei variabile.

Dăm aproximația inițială și găsim punctul minim:

Astfel, funcția Rosenbrock are un minim la punctul (1; 1) egal cu 0. Rezultatul corespunde celui teoretic. SciLab sa confruntat cu un caz de testare complex!

Problema dietei

O altă problemă de optimizare întâlnită frecvent în practică este problema programării liniare. Această clasă include sarcinile planului, sarcina de transport, sarcina dietei și altele. Ca un exemplu, ia în considerare acesta din urmă.

Pentru a crea o astfel de dietă pentru a oferi condițiile specificate la un cost minim.

Formularea problemei

Să presupunem că x1. x2. x3. x4 este numărul dorit de produse P1. P2. P3. P4 respectiv. Apoi, costul total al rației

Sarcina noastră este să alegem xi astfel încât această funcție să fie minimă. Următoarele limitări sunt impuse celor necunoscute xi:

restricționarea semnului (într-adevăr, cantitățile căutate trebuie să fie pozitive)

Astfel, formularea matematică a problemei constă în găsirea valorilor variabilelor x1. x2. x3. x4. satisfacerea sistemului de constrângeri (2) - (5) pentru care funcția liniară (1) ar fi minimă. Funcția L se numește funcția obiectivă.

Pentru a rezolva problema de programare liniară în SciLab, se folosește funcția linpro. care are sintaxa:

c - vector-coloană a coeficienților pentru xi în funcția obiectivă; desigur, lungimea unui vector este egală cu numărul de necunoscute.

A este matricea coeficienților pentru necunoscuți în sistemul de constrângeri; numărul de rânduri ale matricei este egal cu numărul constrângerilor, iar numărul de coloane coincide cu numărul de necunoscute. Toate condițiile limită trebuie să aibă semnul "≤". Dacă în formula originală (ca în cazul nostru) există un semn "≥", inegalitatea este înmulțită cu -1.

b - vector-coloană a membrilor liberi ai sistemului de constrângeri.

ci este un vector de coloană care conține limita inferioară pentru variabilele necunoscute; în absența lui [].

cs este un vector de coloană care conține limita superioară pentru variabilele cerute; în absența lui [].

k este o variabilă întreg, egală cu numărul de egalități din constrângere. În acest caz, formarea matricei A ia în considerare în primul rând egalitățile și apoi inegalitățile.

x0 este o coloană vectorală a aproximațiilor inițiale pentru valorile necunoscute.

Funcția linpro returnează o matrice de x necunoscută, valoarea minimă a funcției f și matricea multiplicatorilor Lagrange kl.

Pentru ca comanda linpro să funcționeze, instrumentul quapro trebuie să fie conectat. Dacă nu este instalat, descărcați acest modul de la scilab.org, instalați și executați încărcător de fișiere (File - Run) din directorul quapro.