Programmazione lineare: differenze tra le versioni

Versione delle 15:07, 5 gen 2019

Versione attuale delle 22:39, 4 feb 2024

(11 versioni intermedie di 7 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 22 ⟶ 23:

Sono tutti quei problemi lineari che presentano al loro interno solo variabili continue, cioè variabili che possono assumere con continuità tutti i valori contenuti all'interno del loro dominio di esistenza.

Per questa classe di problemi esiste un algoritmo di risoluzione molto importante, chiamato ''[[Algoritmoalgoritmo del simplesso]]''. Questo algoritmo deve la sua importanza al fatto che è un metodo di risoluzione ''esatto''.: Questopermette significa che permettecioè di trovare la miglior soluzione ammissibile, qualora questa esista, che risolve il problema studiato. Inoltre, l'algoritmo è strutturato in modo tale che se il problema non ha alcuna soluzione ammissibile, è possibile saperlo con certezza.

==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 \geq= y^TAx \geq y^T(Ax)\geq y^Tb</math>

in particolare, questo dimostra che ogni soluzione al problema lineare (P2):

Riga 73:

Per questa classe di problemi esiste un algoritmo di risoluzione molto importante, chiamato ''[[Branch and cut]]''. Questo algoritmo deve la sua importanza al fatto che è un metodo di risoluzione ''esatto''. Questo significa che permette di trovare la miglior soluzione ammissibile, qualora questa esista, che risolve il problema studiato.

== Note ==

<references/>

== Voci correlate ==

Riga 85 ⟶ 88:

== Altri progetti ==

{{interprogetto|preposizione=sulla|wikt=programmazione lineare}}

== Note ==

<references/>

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{FOLDOC|linear programming|linear programming}}

{{Controllo di autorità}}

{{Portale|matematica}}