Programmazione lineare: differenze tra le versioni

Versione delle 21:19, 20 ago 2018

Versione attuale delle 22:39, 4 feb 2024

(25 versioni intermedie di 14 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:

::<math>\begin{matrix}

\text{massimizza } & 2x_1 + x_2 + 3x_3\\

\text{soggetto ai vincoli: } & x_1 + x_2 + x_3 \leq 1\\

&x_1 \geq 0\\

&x_2 \geq 0\\

&x_3 \geq 0

\end{matrix}</math>

==Dualità dei problemi lineari continui==

Ad ogni problema di massimizzazione lineare corrisponde un problema di minimizzazione lineare con le seguenti proprietà:

* Se il primo problema ha una solutionesoluzione finita, allora anche il secondo problema ha una soluzione finita e i valori delle funzioni obbiettivo per le due soluzioni coincidono,

* Se il primo problema non ha alcuna soluzione, il secondo problema ha una soluzione infinita,

* 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 <math>} &c^Tx</math>\\

\text{soggetto ai vincoli: } &Ax \geq b\\

<math>&x \geq 0 </math>

\end{matrix}</math>

dove <math>A</math> è una matrice <math>m \times n</math> con righevettori riga: <math>a_1, ... , a_m</math> e <math>b</math> è un vettore in <math>\R^m</math>.

minimizza <math>c^Tx</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):

soggetto ai vincoli:

<math>Axc^Tx \geq b(A^Ty)^Tx = y^TAx \geq y^T(Ax)\geq y^Tb</math>

<math>x \geq 0 </math>

dove <math>A</math> è una matrice <math>m \times n</math> con righe: <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):

::<math>\begin{matrix}

\text{massimizza } &b^Ty\\

\text{soggetto ai vincoli: } &A^Ty \leq c\\

<math>&y \geq 0 </math>

\end{matrix}</math>

ha un valore di funzione obiettivo minore di qualsiasi soluzione <math>x \in \R^n</math>. È infatti possibile dimostrare che se l'insieme delle soluzioni di (P1) non è vuoto e (P1) ha una soluzione finita, allora esistono un <math>x</math> e <math>y</math> tali per cui <math>c^Tx = b^Ty</math> che quindi sono ottimali.

massimizza <math>b^Tx</math>

soggetto ai vincoli:

<math>A^Ty \leq c</math>

<math>y \geq 0 </math>

ha un valore di funzione obiettivo minore di qualsiasi soluzione <math>x \in \R^n</math>. È infatti possibile dimostrare che se l'insieme delle soluzioni di (P1) non è vuoto e (P1) ha una soluzione finita, allora esistono un x e y tali per cui c^Tx = b^Ty che quindi sono ottimali.

==Problemi lineari interi==

Riga 67 ⟶ 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 79 ⟶ 88:

== Altri progetti ==

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

== Collegamenti esterni ==

* {{ThesaurusCollegamenti BNCFesterni}}

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

{{Controllo di autorità}}

{{Portale|matematica}}