Programmazione lineare: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Etichette: Modifica da mobile Modifica da web per mobile
Aggiunto il template "F"
 
(8 versioni intermedie di 4 utenti non mostrate)
Riga 1:
{{F|matematica|febbraio 2024}}
La '''programmazione lineare''' (PL) è quella branca della [[ricerca operativa]] che si occupa di studiare algoritmi di risoluzione per ''problemi di ottimizzazione lineari''<ref>[https://archive.org/details/DTIC_ADA112060/ ''Reminiscences about the origin of linear programming'']</ref>.
 
Un problema è detto ''lineare'' se sia la ''funzione obiettivo'' sia i ''vincoli'' sono [[Funzione lineare|funzioni lineari]].
 
Questo significa che la funzione obiettivo può essere scritta come:
Riga 25 ⟶ 26:
 
==Poliedri e geometria dei punti permessi==
L'insieme dei punti permessi dai vincoli di un problema lineare continuo forma un [[politopo]], un'intersezione di mezzi-spazi. Un esempio di problema lineare continuo è il seguente:
Considera il seguente problema lineare continuo:
 
::<math>\begin{matrix}
Riga 42:
* Se il secondo problema non ha alcuna soluzione, il primo problema ha una soluzione infinita.
 
ConsideraDato il seguente problema di minimizzazione lineare (P1):
::<math>\begin{matrix}
\text{minimizza } &c^Tx\\
Riga 51:
dove <math>A</math> è una matrice <math>m \times n</math> con vettori riga: <math>a_1, ... , a_m</math> e <math>b</math> è un vettore in <math>\R^m</math>.
 
è possibile considerare una [[combinazione lineare]] delle righe di <math>A</math> per ottenere che per ogni vettore <math>y \in \R^m</math> che soddisfi: <math>A^Ty \leq c</math> e <math>y \geq 0</math>, ed ogni vettore <math>x \in \R^n</math> che soddisfi i vincoli di (P1):
 
<math>c^Tx \geq (A^Ty)^Tx = y^TAx \geq y^T(Ax)\geq y^Tb</math>
Riga 88:
 
== Altri progetti ==
{{interprogetto|preposizione=sulla|wikt=programmazione lineare}}
 
== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|linear programming|linear programming}}
 
{{Controllo di autorità}}