FANDOM


Si descriva brevemente il metodo del simplesso per la programmazione lineare.


In uno spazio N-dimensionale il simplesso è un politopo di N+1 vertici. In parole povere in uno spazio monodimensionale un simplesso è un segmento, in uno spazio 2-D è un triangolo, in uno spazio 3-D una piramide a base triangolare, ecc... quindi il simplesso è il politopo con il minor numero di vertici che può essere usato per circondare un punto nello spazio in questione. Il metodo del simplesso è usato in programmazione lineare per risolvere problemi di minimizzazione (o massimizzazione se si inverte la funzione costo) a N parametri. Nello spazio N-dimensionale dei parametri viene costrutito un simplesso sulla base di un initial guess fornito dall'utente o da qualche forma di euristica e la funzione costo da minimizzare viene valutata in tutti i vertici del simplesso. Poi iterativamente la funzione viene calcolata in punti prossimi al simplesso: quando si trova un punto in cui la funzione costo risulta minore rispetto ai vertici del simplesso allora un vertice del simplesso viene sostituito dal nuovo punto. In questo modo il simplesso si modifica e man mano si restringe attorno ad un minimo locale della funzione costo, nella fattispecie si tratta del minimo locale nel cui bacino di attrazione si trovava il simplesso di partenza. Questo metodo è infatti un algortimo di discesa del gradiente ed in quanto tale la bontà della soluzione finale è fortemente influenzata dalla scelta dell'initial guess.




Si descriva il metodo delle due fasi per la programmazione lineare.




Il candidato descriva brevemente il concetto di grafo ed il suo utilizzo nei problemi di ottimizzazione.

Un grafo è un'astrazione matematica utile per formalizzare molti tipi di problemi in ricerca operativa. Un grafo consiste di due liste: una di nodi e una di archi (coppie di nodi) che definisce la topologia del grafo. Gli archi possono essere orientati (per indicare un collegamento di andata e ritorno tra due nodi servono due archi, uno in una direzione e l'altro nella direzione opposta), pesati (al passaggio tra due nodi connessi è associato un peso, ad esempio la distanza tra due città) o nessuno dei due (gli archi indicano connessioni bidirezionali tutte uguali tra di loro). In pratica molti problemi di natura anche molto diversa sono formalizzabili in ricerche su grafo ad esempio:

  • Colorare una mappa politica in modo che ogni stato abbia colori diversi dagli stati confinanti. I nodi sono gli stati, gli archi indicano i confini;
  • Risolvere il cubo di Rubik. I nodi sono le configurazioni diverse del cubo, gli archi indicano le mosse possibili;
  • Trovare il percorso ottimo per attraversare un certo numero di città. I nodi sono le città, gli archi indicano i collegamenti tra le città e i pesi dei collegamenti indicano la distanza tra le città collegate.

Questi pochi esempi danno un'idea della potenza di astrazione dei grafi. Una cosa che hanno in comune questo tipo di problemi è il fatto che se affrontati in modo naive, provando tutte le possibili combinazioni, le risorse richieste dalla ricerca (tempo e memoria) crescono esponenzialmente con le dimensioni dell'istanza del problema (basti pensare che per ogni nodo si possono fare tante decisioni quanti sono gli archi che ne escono). Perciò nel corso degli anni sono stati sviluppati molti algoritmi di ricerca su grafo che mirano a ridurre al minimo la porzione delle possibilità esplorate, ad esempio eliminando a priori intere famiglie di percorsi che non possono dare soluzioni ottime (branch and bound). In molti casi questi algoritmi hanno raggiunto livelli di performance tali da rendere preferibile la formalizzazione del problema in ricerca su grafo e la risoluzione di quest'ultima rispetto alla risoluzione diretta del problema stesso.



Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale