Connessione tra Ricerca Operativa- Programmazione

[galois23]

Salve a tutti!!!

Qualcuno mi può aiutare a trovare dei possibili collegamenti tra la ricerca operativa e la programmazione, per esempio in C++???

Grazie a tutti in anticipo!

[hamming_burst]

Ciao,
cosa intendi con "collegamenti"?
La ricerca operativa si può vedere a diversi livelli, dalla modellizzazione di problemi di ottimizzazione, alla scrittura di problemi...
Un collegamento banale: hai un problema PL e lo dai in pasto ad un calcolatore che ha in esecuzione l'algoritmo del simplesso (scritto ad esempio in C++)...

[galois23]

Ho seguito un corso di ricerca operativa che in cui si parlava di problemi di ottimizzazione, programmazione lineare e metodo del simplesso.

Mi piacerebbe trovare un argomento che vada al di là di quelli studiati in cui sia possibile implementare qualche algoritmo mediante c++... però ho fatto qualche ricerca su internet e ho trovato qualcosa sui grafi, ma non mi soddisfa... qualcuno che ha qualche conoscenza in più di ricerca operativa, può indicarmi su che strada procedere???

[Deckard]

La ricerca operativa è un campo molto vasto, dovresti dirci quali sono le tue preferenze. Ovviamente qualsiasi algoritmo è implementabile in C++, però, ecco, a meno che non sei proprio un appassionato, eviterei di implementare l'algoritmo del simplesso.
Potresti ad esempio implementare un algoritmo basato sul branch & bound per risolvere un problema di PLI; un esempio può essere lo "0-1 knapsack problem": usi il metodo B&B e ogni sottoproblema lo risolvi con il rilassamento di Dantzig (su wiki ci dovrebbe essere scritto tutto se non hai fatto qualcosa).

[galois23]

ok, grazie mille.... ora mi documento!!!

[hamming_burst]

La ricerca operativa è un campo molto vasto, dovresti dirci quali sono le tue preferenze. Ovviamente qualsiasi algoritmo è implementabile in C++, però, ecco, a meno che non sei proprio un appassionato, eviterei di implementare l'algoritmo del simplesso.
Potresti ad esempio implementare un algoritmo basato sul branch & bound per risolvere un problema di PLI; un esempio può essere lo "0-1 knapsack problem": usi il metodo B&B e ogni sottoproblema lo risolvi con il rilassamento di Dantzig (su wiki ci dovrebbe essere scritto tutto se non hai fatto qualcosa).

concordo se ci dici le tue basi che hai studiato, si possono creare molti algoritmi. Breanch and Bound io non lo consiglierei, ma è sempre implementabile. C'è anche ricerca locale che ha tantissime applicazioni in problemi combinatori di ottimizzazione.
Bho dicci qualcosa e ti si da una mano

[galois23]

Beh, ho dato un'occhiata allo "0-1 knapsack problem" e sembra carino... Il B&B è un argomento che conosco perchè svolto nel corso che ho seguito.

In linea generale si è parlato di programmazione matematica e problemi di ottimo, entrando un po' nello specifico nella programmazione lineare (interpretando un problema geometricamente e graficamente), poi siamo passati alla programmazione lineare intera e quindi B&B e infine il metodo del simplesso... Considerate che molti risultati non mi sono stati dimostrati (per esempio il teorema fondamentale della programmazione lineare).

Ricerca Locale non so cosa sia...

[hamming_burst]

se hai studiato solo questi argomenti, sono gli argomenti principali di un corso di Ricerca Operativa. Se conosci la modelizzazione di programmazione matematica non avrai problemi a produrre algoritmi implementabili in qualunque linguaggio con tecnica (visto che è l'unica oltre PL che hai studiato) B&B, che e io evito per questioni teoriche ma è applicabile a un'immensità di problemi, ma a me non piace molto.

La ricerca locale (Local Search) è una tecnica o modello di pensiero, un modello di implementazione di algoritmi per risolvere problemi intrattabili, combinatori, ottimizzazione...tanti tipi di problemi, è molto potente.