De grands problèmes résolus
Certains grands problèmes d'optimisation possèdent une solution algorithmique efficace. C'est le cas quand il s'agit de trouver le plus court chemin parmi un nombre immense de possibilités, de faire transiter un flot (d'électricité, d'eau, d'information…) dans un réseau ou de résoudre un programme « linéaire », ne nécessitant pas d'énumérer toutes les solutions potentielles. Ces questions ont le bon goût d'appartenir à la classe P des problèmes qui peuvent être résolus en temps « raisonnable » (parfois polynomial). Les algorithmes associés, dont certains, comme le simplexe, sont classés parmi les dix plus importants du xxe siècle, ont gravé le nom de leur découvreur dans l'histoire de l'informatique : Dijkstra, Ford et Fulkerson, Bellman…
Tutti gli articoli di questo dossier
Comprendere il caso
I problemi di ottimizzazione stocastica sono caratterizzati da un’incertezza sui dati. Il modellatore conosce solo parzialmente i dati relativi al sistema considerato o alla sua evoluzione. Tuttavia, i loro valori possono essere descritti mediante distribuzioni di probabilità.
L’ottimizzazione equa
Le decisioni prese all’interno delle organizzazioni hanno spesso conseguenze per più persone, che occorre considerare in modo equo. L’ottimizzazione equa permette di trovare soluzioni efficienti controllando al contempo l’equilibrio delle soddisfazioni.
Schedulazione: pianificazione matematica | Tangente
Quando occorre decidere quando svolgere le attività necessarie a raggiungere un obiettivo, a volte servono immaginazione o capacità di astrazione. Tutte queste situazioni possono però avvalersi della teoria della schedulazione, un settore della ricerca operativa molto attivo da oltre un secolo.
Trasporti, flussi e tagli nelle reti | Tangente
Molti problemi di trasporto possono essere modellizzati mediante i «flussi». È il caso del trasporto dell’elettricità presentato in questo articolo. Altre applicazioni classiche riguardano il trasporto di fluidi (gas, acqua, petrolio...) e quello di persone o merci (camion, treno, nave...).