dynamisk programmering

Dynamisk programmering er en matematisk metode til optimering af en flertrinsbeslutningsproces, foreslået af den amerikanske matematiker Richard Bellmann (1920-1984) i bogen Dynamic Programming (1957). Processen beskrives af en række tilstande, hvoraf den første er givet, mens de følgende bestemmes af den foregående samt en beslutningsvariabel for hver tilstand. Et optimum forstås som maksimum af en objektfunktion.

Bellmans idé er, at er man kommet til en tilstand, så er man tvunget til at træffe den næste beslutning, så den maksimerer objektfunktionen med den fundne tilstand som givet. Det betyder, at betragtes den næstsidste tilstand som en variabel, kan den sidste beslutning bestemmes som en funktion af denne tilstand, nemlig som den beslutning, der maksimerer objektfunktionen. Sådan bliver den sidste beslutning en konsekvens af den næstsidste tilstand og er dermed elimineret. Processen kan derfor gentages, indtil den første beslutning nås og dermed løser problemet.