Programmazione lineare

Da Wikipedia, l'enciclopedia libera.

Questa voce di matematica è solo un abbozzo: contribuisci a migliorarla secondo le convenzioni di Wikipedia.

La programmazione lineare (PL oppure LP)è quella branca della ricerca operativa che si occupa di studiare algoritmi di risoluzione per problemi lineari.

Un problema è detto lineare se sia all'interno della funzione obiettivo sia all'interno dei vincoli le variabili non sono mai nè moltiplicate nè divise le une con le altre.

Questo signica che la funzione obiettivo può essere scritta come: $F.O.=\sum_{i=1}^{NV}c_i\cdot x_i=\underline{c}^T\underline{x}$ avendo indicato con

NV il numero delle variabili che descrivono il problema;
$\underline{c}$ il vettore dei coefficienti della funzione obiettivo;
$\underline{x}$ il vettore delle variabili.

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)

[modifica] 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. Questo significa che permette 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 ammette alcuna soluzione ammissibile, è possibile saperlo con certezza.

[modifica] Problemi lineari interi

Sono tutti quei problemi lineari che presentano al loro interno solo variabili intere, cioè variabili che possono assumere solo i valori 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.

[modifica] 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.