Programimi linear

Një paraqitje piktoriale e një programi të thjeshtë linear me dy ndryshore dhe gjashtë mosbarazime. Grupi i zgjidhjeve të realizueshme tregohet me të verdhë dhe formon një poligon, një politop 2-dimensional. Optimumi i funksionit të kostos lineare është vendi ku vija e kuqe kryqëzon shumëkëndëshin. Vija e kuqe është një bashkësi niveli i funksionit të kostos dhe shigjeta tregon drejtimin në të cilin po optimizojmë.

Një rajon i mbyllur i realizueshëm i një problemi me tre ndryshore është një shumëfaqësh konveks. Sipërfaqet që japin një vlerë fikse të funksionit objektiv janë rrafshe (nuk tregohen). Problemi i programimit linear është gjetja e një pike në poliedrin që është në rrafshin me vlerën më të lartë të mundshme.

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

${\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 $\mathbf {x}$ janë ndryshoret që do të përcaktohen, $\mathbf {c}$ dhe $\mathbf {b}$ janë dhënë vektorë, dhe $A$ është një matricë e dhënë. Funksioni vlera e të cilit duhet të maksimizohet ( $\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$ në këtë rast) quhet funksion objektiv . Kufizimet $A\mathbf {x} \leq \mathbf {b}$ dhe $\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.