Programmazione lineare
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
La programmazione lineare (PL) è quella branca della ricerca operativa che si occupa di studiare algoritmi di risoluzione per problemi di ottimizzazione lineari[1].
Un problema è detto lineare se sia la funzione obiettivo sia i vincoli sono funzioni lineari.
Questo significa che la funzione obiettivo può essere scritta come: avendo indicato con
- NV il numero delle variabili che descrivono il problema;
- il vettore colonna dei coefficienti della funzione obiettivo;
- il vettore colonna delle variabili .
- la T ad esponente è l'operatore di trasposizione.
Esistono tre grandi classi di problemi lineari:
1) Problemi lineari continui (Linear Programming =>LP)
2) Problemi lineari interi (Integer Linear Programming =>ILP)
3) Problemi lineari misto-interi (Mixed Integer Linear Programming => MILP)
Problemi lineari continui
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 algoritmo del simplesso. Questo algoritmo deve la sua importanza al fatto che è un metodo di risoluzione esatto: permette cioè 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:
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 soluzione 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.
Dato il seguente problema di minimizzazione lineare (P1):
dove è una matrice con vettori riga: e è un vettore in .
è possibile considerare una combinazione lineare delle righe di per ottenere che per ogni vettore che soddisfi: e , ed ogni vettore che soddisfi i vincoli di (P1):
in particolare, questo dimostra che ogni soluzione al problema lineare (P2):
ha un valore di funzione obiettivo minore di qualsiasi soluzione . È infatti possibile dimostrare che se l'insieme delle soluzioni di (P1) non è vuoto e (P1) ha una soluzione finita, allora esistono un e tali per cui che quindi sono ottimali.
Problemi lineari interi
Sono tutti quei problemi lineari che presentano al loro interno solo variabili intere, cioè variabili che possono assumere solo i valori interi contenuti all'interno del loro dominio di esistenza.
Per questa classe di problemi esiste un algoritmo di risoluzione molto importante, chiamato Branch and bound. 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.
Problemi lineari misto-interi
Sono tutti quei problemi lineari che presentano al loro interno sia variabili intere sia variabili continue.
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
- ^ Reminiscences about the origin of linear programming
Voci correlate
- Programmazione non lineare
- Programmazione quadratica
- Programmazione stocastica
- Elenco di algoritmi di ottimizzazione
- Ricerca operativa
- Algoritmo del simplesso
- Branch and bound
- Branch and cut
Altri progetti
Altri progetti
- Wikizionario
- Wikimedia Commons
Wikizionario contiene il lemma di dizionario «programmazione lineare»
Wikimedia Commons contiene immagini o altri file sulla programmazione lineare
Collegamenti esterni
- Robert Dorfman, Programmazione lineare, in Enciclopedia delle scienze sociali, Istituto dell'Enciclopedia Italiana, 1991-2001.
- (EN) linear programming / linear programming (altra versione), su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Programmazione lineare, su MathWorld, Wolfram Research.
- (EN) Programmazione lineare, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
- (EN) Denis Howe, linear programming, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
Controllo di autorità | Thesaurus BNCF 21955 · LCCN (EN) sh85082127 · GND (DE) 4035816-1 · BNF (FR) cb119415380 (data) · J9U (EN, HE) 987007555765405171 · NDL (EN, JA) 00570683 |
---|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)