Metodi e modelli per il supporto alle decisioni
3. Geometria della
Programmazione Lineare
Problemi di programmazione convessa
x
y X
w f(w)
x y
2
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.3
Problemi di programmazione lineare (PL)
Caso particolare della programmazione convessa
Sempre possibile scriverli in forma standard min z = c 1 x 1 + c 2 x 2 + …+c j x j +…+ c n x n
subject to
a 11 x 1 + a 12 x 2 + …+a 1j x j +…+ a 1n x n = b 1 a 21 x 1 + a 22 x 2 + …+a 2j x j +…+ a 2n x n = b 2
…
a m1 x 1 + a m2 x 2 + …+a mj x j +…+ a mn x n = b m x j ≥ 0
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.4
Geometria della regione ammissibile
semispazio (affine) iperpiano
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.5
La regione ammissibile di un La regione ammissibile di un problema di PL
problema di PL è è un poliedro. un poliedro.
POLITOPO (poliedro limitato)
TRONCONE (poliedro illimitato)
0
Vertici di poliedri e PL
4
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.7
Esempio
min z = – x 1 – x 2 s.t.
6 x 1 + 4 x 2 ≤ 24 3 x 1 – 2 x 2 ≤ 6 x 1 , x 2 ≥ 0
A B
C D
x
1x
2Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.8
Generalizziamo…
Scrivere in modo conveniente un problema di PL
Richiamare concetti di Algebra Lineare PL in forma STANDARD
min z = c 1 x 1 + c 2 x 2 + …+c j x j +…+ c n x n
s.t. a 11 x 1 + a 12 x 2 + …+a 1j x j +…+ a 1n x n = b 1 a 21 x 1 + a 22 x 2 + …+a 2j x j +…+ a 2n x n = b 2
…
a m1 x 1 + a m2 x 2 + …+a mj x j +…+ a mn x n = b m
x j ≥ 0, j = 1…n
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.9
Notazione
Problema PL: forme compatte
6
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.11
Richiami di algebra lineare (I)
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.12
Richiami di algebra lineare (II)
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.13
Soluzioni di base
Caratterizzazione algebrica dei vertici e
teorema fondamentale della PL
8
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.15
Ipotesi di algoritmo risolutivo per problemi di PL
Algoritmo enumerativo:
1. Genero tutte le soluzioni di base (ponendo a 0 n-m variabili e risolvendo un sistema di equazioni lineari)
2. Scelgo la migliore soluzione ammissibile di base
MA… numero “elevato” di possibili soluzioni di base (al più tutte le possibili combinazioni di m tra n colonne)
Suggerimento:
non genero tutte le soluzioni di base
a partire da una soluzione ammissibile di base, cerco di migliorarla “localmente” finché non sono più possibili miglioramenti ⇒ ottimo locale ⇒ ottimo globale
…ALGORTIMO del SIMPLESSO…
Luigi De Giovanni - MMSD - 3. Geometria della Programmazione Lineare 3.16
