een systeem van methoden en technieken, geschikt om de optimale oplossing, en in het algemeen de toegelaten oplossingen te bepalen van planningsproblemen waarbij men te maken heeft met randvoorwaarden, zoals goederenschaarste, beperktheid van het budget e. d. In wiskundig opzicht is LP een onderdeel van de mathematische programmering.
Zij komt neer op het bepalen van een uiterste waarde van een lineaire functie, waarvan de variabelen tegelijk moeten voldoen aan een aantal lineaire ongelijkheden. Derhalve dient een dergelijk probleem allereerst wiskundig te worden geformuleerd. Stel b.v. dat pb ..., pnde opbrengsten per eenheid zijn van de artikelen x1, ..., xn, waarvan men de onbekende hoeveelheden xb ..., xn zou willen produceren. De totale opbrengst wordt gegeven door de functie: n P1x1+ ••• + Pnxn = Σ P1X1 j = 1 terwijl de hoeveelheden van de artikelen beperkt zijn door de voorwaarde a1x1 + ... + anxn ≦ b waarin de coëfficiënten a1, ..., an b.v. de produktiekosten per eenheid zijn en b de bovengrens van het budget is. Omdat het aantallen artikelen betreft, mogen de onbekenden x1, ..., xn geen negatieve waarden aannemen.In een LP-probleem heeft men vaak te maken met een (groot) aantal m van deze beperkingen, terwijl het aantal onbekenden n ook groot kan zijn. Men kan het probleem, bestaande in het vinden van de optimale oplossing, algemeen formuleren als: n maximaliseer Σ PjXj onder de voorwaarden j = 1 n Σ aijXj≦bv i = 1,...m j = 1 xj≧0, j=1, ...n De te optimaliseren functie wordt ook doelfunctie genoemd. Elk maximalisatieprobleem kan tevens als minimalisatieprobleem worden geformuleerd. Dit verdient soms de voorkeur met het oog op vereenvoudiging van de uit te voeren berekeningen. Het verband tussen het oorspronkelijke probleem en zijn tegenhanger, het duale probleem, wordt bestudeerd in de dualiteitstheorie.De oplossing van LP-problemen geschiedt gewoonlijk met een iteratieve algebraïsche procedure, de simplexmethode, in 1947 ontwikkeld door de Amerikaan G.B.Dantzig. In LP-problemen met slechts twee of drie onbekenden kan behalve een numerieke oplossing ook een grafische oplossing worden gegeven. In het eerste geval door een planimetrische figuur, in het tweede geval door een stereometrische figuur.
De LP is een van de belangrijkste technieken in de operationele research. Hierbij moet programmering opgevat worden in de economische betekenis van het maken van een produktieprogramma en heeft niets te maken met het programmeren van een computer, hoewel deze voor het uitvoeren van de berekeningen wel nodig is. De in praktijk voorkomende lineaire programmeringsproblemen zijn dikwijls zeer uitgebreid: honderden ongelijkheden en variabelen zijn mogelijk. Daarom zijn de numerieke aspecten van de simplexmethode uitvoerig bestudeerd, en zijn er uiterst efficiënte computerprogrammas ontwikkeld.
LITT. G.B.Dantzig, Linear programming and extensions (1948); R.Dorfman.P.Samuelson en R. Solow, Linear programming and economie analysis (1958); R.E.D.Henderiks, Lineaire programmering (1972); H.M.Salkin en J.Saha, Studies in linear programming (1975).
