Probleme de optimizare

În capitolul precedent s-a arătat că problemele nedeterministe pot avea mai multe soluții. În problemele de optimizare se cere să se găsească soluția optimă, adică cea mai bună dintre toate soluțiile posibile. În acest scop este necesar să se definească riguros ce se înțelege prin "cea mai bună soluție".

Vom considera ca soluția optimă s* este cea pentru care o anumită funcție obiectiv f(s*) are valoarea maximă sau valoarea minimă. De exemplu, se cere să se determine soluția pentru care eficiența este maximă, sau pentru care costul este minim.

Problemele de optimizare se împart în două mari categorii:
    a) probleme continue, în care s ia valori într-un domeniu continuu;
    b) probleme de optimizare discretă, în care s aparține unei mulțimi discrete S={s1 , s2 , ...}.

În numeroase situații practice, mulțimea S a soluțiilor posibile este nu numai discretă, dar și finită S={s1 , s2 , ..., sn}. În astfel de situații, în principiu, pentru determinarea soluției optime se poate aplica tehnica "forței brute": se determină mai întâi toate soluțiile, se calculează pentru fiecare valoarea corespunzătoare a funcției obiectiv f și se alege soluția cu valoarea optimă (maximă sau minimă, după caz) a acestei funcții. Totuși, în numeroase cazuri, chiar dacă numărul de soluții posibile este finit, el este foarte mare. În astfel de cazuri, determinarea tuturor soluțiilor ar necesita un timp foarte mare de calcul, astfel încât aplicarea practică a tehnicii "forței brute" nu este rațională sau este chiar imposibilă. Din această cauză, au fost create diverse tehnici de determinare a soluției optime fară a fi necesară parcurgerea tuturor soluțiilor posibile.

În acest capitol se prezintă două dintre metodele de determinare a soluției pentru probleme de optimizare discretă: metoda Greedy și metoda programării dinamice.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați