Rossi Marco & Carisi Matteo
classe 5 ISA
26/03/13
Programmazione lineare
Istituto C.Zuccante
A.S. 2012/2013
1/10
Campi di applicazione
La programmazione lineare serve per determinare l’allocazione ottimale di risorse
disponibili in quantità limitata, per ottimizzare il raggiungimento di un obiettivo
prestabilito, in condizioni di certezza.
• Problema
• Modello matematico lineare
• Algoritmi matematici standard
• Metodo del simplesso
2/10
Formulazione di un modello di
programmazione lineare: CONDIZIONI
Variabili di
decisione non
negative
Criterio selezione
variabili: funzione
obiettivo
Insieme equazioni
o disequazioni
lineari: insieme
dei vincoli
3/10
Formulazione di un modello di programmazione
lineare: MODO STANDARD
Date le variabili di decisione
x1,x2,…,xn (positive)
determinare il massimo della funzione
Z= c1x1 + c2x2 +….+ cnxn
soggetta a particolari vincoli
Ak1xk1 + ak2xk2 +….+ aknxn <= bk
4/10
Metodo grafico
Per risolvere un problema di programmazione lineare con due
sole variabili di decisione si può usare il metodo grafico.
 si definisce l’area da prendere in considerazione in base ai
vincoli di non negatività
 si impongono i limiti ⇒ si definisce l’insieme delle soluzioni
accettabili
 si disegnano le rette parallele associate alla funzione
obiettivo
 si calcola il valore che assume la funzione obiettivo nei
vertici (soluzioni accettabili di base)
 il valore più grande (o più piccolo) è associato alla soluzione
ottimale
5/10
Esempio metodo grafico
6/10
Proprietà dell’insieme delle soluzioni
ammissibili
l’insieme delle soluzioni accettabili costituisce
un insieme convesso
se esiste una soluzione accettabile, esiste una
soluzione accettabile di base
le soluzioni accettabili di base sono in numero
finito
se la soluzione obiettivo ha un massimo finito,
allora almeno una soluzione ottimale é
accettabile di base
7/10
Metodo del simplesso
Nel caso in cui il nostro problema abbia molte variabili si utilizza
l’algoritmo del metodo del simplesso, sviluppato dal matematico
americano Dantzing nel 1947.
Con questo metodo si cerca la soluzione ottimale spostandosi sui
vertici dell’insieme delle soluzioni accettabili; supponiamo il problema
sia nella sua forma standard :
 si introducono m variabili di scarto trasformando le disuguaglianze
in uguaglianze nei vincoli
 tutte le variabili di scarto si scelgono come variabili in base e si
pongono uguali a bi ≥ 0; le altre variabili si impongono uguali a zero
 una soluzione accettabile di base ha n + m variabili di cui almeno n
sono nulle; se le altre m sono positive la soluzione é non degenere
 se non consideriamo le variabili di scarto, l’origine é la prima
soluzione accettabile di base
8/10
Fasi del metodo del simplesso
Si convertono tutte le
disuguaglianze in equazioni
aggiungendo le variabili di scarto e
si scrive la matrice dei coefficienti
aij e bi
Calcolo nuova matrice dei
coefficienti con opportune
operazioni su righe e colonne
Si effettua nuovamente la prova di
ottimalità come nella fase 2
Si prende una soluzione
ammissibile di base e la si
inserisce in una riga sotto la
matrice; si aggiungono due
colonne, una per la variabile e
l’altra cb per indicare i coefficienti
cj
Individuata la variabile entrante, si
deve individuare quella uscente
Il processo si conclude quando si
trova la soluzione ottimale ossia
quando si giunge alla soluzione di
base: deltaj ≤ 0
La soluzione ammissibile di base
individuata deve essere
sottoposta alla prova di ottimalità
Si determina la variabile entrante
xj con condizioni: deltaj > 0 e
almeno uno dei coefficienti aij
maggiore di 0
9/10
Il duale
Per ogni problema di programmazione lineare è possibile
definire un problema duale. Ad esempio dato un
problema di massimizzazione, il duale corrispondente si
otterrà:
 Minimizzando invece di massimizzare;
 Trasponendo le righe e le colonne dei coefficienti dei
vincoli;
 Trasponendo i coefficienti della funzione obiettivo e i
termini noti dei vincoli;
 Invertendo le disuguaglianze.
10/10