Programimi linear ( LP ), i quajtur gjithashtu optimizim linear, është një metodë për të arritur rezultatin më të mirë (siç është fitimi maksimal ose kostoja më e ulët) në një model matematik, kërkesat dhe objektivi i të cilit përfaqësohen nga marrëdhënie lineare. Programimi linear është një rast i veçantë i programimit matematik (i njohur edhe si optimizim matematikor ).

Më formalisht, programimi linear është një teknikë për optimizimin e një funksioni objektiv linear, që i nënshtrohet kufizimeve të barazimeve lineare dhe mosbarazimeve lineare . Rajoni i realizueshëm i tij është një politop konveks, i cili është një bashkësi e përcaktuar si prerja e gjysmë hapësirave të fundme, secila prej të cilave përcaktohet nga një mosbarazim linear. Funksioni i tij objektiv është një funksion afin (linear) me vlerë reale i përcaktuar në këtë politop. Një algoritëm programimi linear gjen një pikë në politop ku ky funksion ka vlerën më të madhe (ose më të vogël) nëse ekziston një pikë e tillë.

Programet lineare janë probleme që mund të shprehen në formë standarde si

${\displaystyle {\begin{aligned}&{\text{Gjej një vektor}}&&\mathbf {x} \\&{\text{që maksimizon}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subjekt i}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{dhe}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}$

Këtu përbërësit e ${\displaystyle \mathbf {x} }$ janë ndryshoret që do të përcaktohen, ${\displaystyle \mathbf {c} }$ dhe ${\displaystyle \mathbf {b} }$ janë dhënë vektorë, dhe ${\displaystyle A}$ është një matricë e dhënë. Funksioni vlera e të cilit duhet të maksimizohet ( ${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x} }$ në këtë rast) quhet funksion objektiv . Kufizimet ${\displaystyle A\mathbf {x} \leq \mathbf {b} }$ dhe ${\displaystyle \mathbf {x} \geq \mathbf {0} }$ specifikoni një politop konveks mbi të cilin funksioni objektiv duhet të optimizohet.

Programimi linear mund të aplikohet në fusha të ndryshme studimi. Përdoret gjerësisht në matematikë dhe, në një masë më të vogël, në biznes, ekonomi dhe disa probleme inxhinierike. Industritë që përdorin modele të programimit linear përfshijnë transportin, energjinë, telekomunikacionin dhe prodhimin. Është dëshmuar i dobishëm në modelimin e llojeve të ndryshme të problemeve në planifikim, rrugëzim, planifikim, caktim dhe dizajn.