Lineaire programmering is een tak van wiskunde en statistiek waarmee onderzoekers oplossingen voor optimalisatieproblemen kunnen bepalen. Lineaire programmeerproblemen zijn onderscheidend omdat ze duidelijk zijn gedefinieerd in termen van een objectieve functie, beperkingen en lineariteit. De kenmerken van lineaire programmering maken het een uiterst nuttig veld dat gebruik heeft gevonden in toegepaste velden, variërend van logistiek tot industriële planning.

Optimalisatie

Alle lineaire programmeerproblemen zijn optimalisatieproblemen. Dit betekent dat het echte doel achter het oplossen van een lineair programmeringsprobleem het maximaliseren of minimaliseren van een bepaalde waarde is. Lineaire programmeringsproblemen zijn dus vaak te vinden in de economie, het bedrijfsleven, de reclame en vele andere gebieden die waarde hechten aan efficiëntie en het behoud van hulpbronnen. Voorbeelden van items die kunnen worden geoptimaliseerd zijn winst, resource-acquisitie, vrije tijd en nut.

Linearity

Zoals de naam aangeeft, hebben lineaire programmeerproblemen allemaal het kenmerk lineair te zijn. Deze eigenschap van lineariteit kan echter misleidend zijn, omdat lineariteit alleen betrekking heeft op variabelen die betrekking hebben op de eerste macht (en dus exclusief krachtfuncties, vierkantswortels en andere niet-lineaire functies). Lineariteit betekent echter niet dat de functies van een lineair programmeringsprobleem slechts één variabele zijn. Kortom, lineariteit in lineaire programmeringsproblemen maakt het mogelijk dat de variabelen zich tot elkaar verhouden als coördinaten op een lijn, met uitzondering van andere vormen en krommen.

Objectieve functie

Alle lineaire programmeerproblemen hebben een functie genaamd de "objectieve functie". De doelfunctie is geschreven in termen van de variabelen die naar believen kunnen worden gewijzigd (bijvoorbeeld tijd besteed aan een baan, geproduceerde eenheden enzovoort). De objectieve functie is degene die de oplosser van een lineair programmeringsprobleem wil maximaliseren of minimaliseren. Het resultaat van een lineair programmeringsprobleem zal worden gegeven in termen van de doelfunctie. De objectieve functie is geschreven met de hoofdletter "Z" in de meeste lineaire programmeerproblemen.

Beperkingen

Alle lineaire programmeerproblemen hebben beperkingen voor de variabelen binnen de objectieffunctie. Deze beperkingen nemen de vorm aan van ongelijkheden (bijv. "B & l; 3" waarbij b de eenheden van boeken kan voorstellen die door een auteur per maand zijn geschreven). Deze ongelijkheden bepalen hoe de doelfunctie kan worden gemaximaliseerd of geminimaliseerd, omdat ze samen het 'domein' bepalen waarin een organisatie beslissingen over hulpbronnen kan nemen.