Linjär programmering är en gren av matematik och statistik som gör det möjligt för forskare att bestämma lösningar på optimeringsproblem. Linjära programmeringsproblem är distinkta genom att de definieras tydligt i termer av en objektiv funktion, begränsningar och linjäritet. Karaktäristiken för linjär programmering gör det till ett extremt användbart fält som har använts inom tillämpade områden, allt från logistik till industriell planering.
Alla problem med linjär programmering är optimeringsproblem. Det betyder att det verkliga syftet bakom att lösa ett linjärt programmeringsproblem är att antingen maximera eller minimera något värde. Linjära programmeringsproblem finns således ofta inom ekonomi, affärer, reklam och många andra områden som värdesätter effektivitet och resursbevarande. Exempel på objekt som kan optimeras är vinst, resursförvärv, fritid och nytta.
Som namnet antyder har linjära programmeringsproblem alla egenskaper att vara linjära. Detta linjäritetsdrag kan dock vara vilseledande, eftersom linjäritet endast hänvisar till variabler som är till den första kraften (och därmed exklusive kraftfunktioner, kvadratrötter och andra icke-linjära funktioner). Linjäritet betyder emellertid inte att funktionerna för ett linjärt programmeringsproblem endast har en variabel. Kort sagt, linjäritet i linjära programmeringsproblem gör det möjligt för variablerna att relatera till varandra som koordinater på en linje, exklusive andra former och kurvor.
Alla problem med linjär programmering har en funktion som kallas ”objektivfunktionen”. Objektivfunktionen är skriven i termer av de variabler som kan ändras efter behag (t.ex. tid på ett jobb, producerade enheter och så vidare på). Objektfunktionen är den som lösaren för ett linjärt programmeringsproblem vill maximera eller minimera. Resultatet av ett linjärt programmeringsproblem kommer att ges i termer av objektivfunktionen. Objektivfunktionen skrivs med stora bokstäver "Z" i de flesta linjära programmeringsproblem.
Alla linjära programmeringsproblem har begränsningar för variablerna i objektivfunktionen. Dessa begränsningar har formen av ojämlikheter (t.ex. ”b <3” där b kan representera enheter av böcker skrivna av en författare per månad). Dessa ojämlikheter definierar hur objektivfunktionen kan maximeras eller minimeras, eftersom de tillsammans bestämmer "domänen" där en organisation kan fatta beslut om resurser.