Lineair programmeren

Voorbeeld met twee variabelen, dat zijn er in de praktijk meer. De voorwaarden bepalen het convexe toegestane gebied. De doelfunctie wordt pas hierna ingevoerd.

In de wiskunde, meer speciaal in het operationeel onderzoek, of Engels: OR voor Operations Research, is lineair programmeren of lineaire programmering een methode voor het oplossen van zogenaamde lineaire programmeringsproblemen, kortweg LP-problemen. Dat zijn optimaliseringsproblemen waarin de doelfunctie en de randvoorwaarden alle lineair zijn.

Programmering moet daarbij niet in de zin van een computerprogramma worden opgevat, maar in de betekenis van planning. De naam werd in het midden van de jaren 40 ingevoerd door een van de grondleggers van de lineaire programmering, George Dantzig, lang voor de computer voor de berekeningen bij lineair programmeren werd ingezet.

Lineaire programmering is om verscheidene redenen een belangrijke discipline in de optimalisering. Veel praktische problemen in wetenschappelijk onderzoek kunnen als lineaire programmeringsproblemen worden uitgedrukt. Bepaalde speciale gevallen van lineaire programmering, zoals de problemen van stromen in een netwerk, worden genoeg van belang geacht om onderzoek naar gespecialiseerde algoritmen voor hun oplossing te doen. De werking van een aantal algoritmen voor andere soorten optimaliseringsproblemen berust erop deelproblemen als LP-problemen op te lossen. De ideeën over lineaire programmering hebben in de loop van de tijd veel aan de optimaliseringstheorie voortgebracht, zoals de begrippen dualiteit, decompositie en convex.