Condizioni geometriche di ottimalità e illimitatezza

Teoria della programmazione lineare
Corso di Ricerca Operativa
A.A. 2015-2016
Argomenti

Concetti preliminari

Condizioni geometriche di ottimalità e
illimitatezza

Condizioni algebriche di ottimalità
Concetti preliminari

Esercizio

Esercizio
Esercizio

Concetti preliminari

Esercizio

Esercizio
Concetti preliminari

Esercizio

Esercizio
Esercizio

Concetti preliminari
Un problema di PL è in «forma
standard» se:
1. la funzione obiettivo è di minimo;
2. il poliedro P è in forma standard.
Si possono utilizzare diverse notazioni
per rappresentare un problema di PL in
forma standard, tutte equivalenti e
intercambiabili.
Concetti preliminari

Concetti preliminari

Concetti preliminari

Concetti preliminari

Concetti preliminari

Argomenti

Concetti preliminari

Condizioni geometriche di ottimalità e
illimitatezza

Condizioni algebriche di ottimalità
Condizioni geometriche di ottimalità e illimitatezza

Esercizio

Esercizio

Esercizio

Condizioni geometriche di ottimalità e illimitatezza

Condizioni geometriche di ottimalità e illimitatezza

Condizioni geometriche di ottimalità e illimitatezza

Condizioni geometriche di ottimalità e illimitatezza

Condizioni geometriche di ottimalità e illimitatezza

k
h
   j ( c x )   i ( c t ) 








j 1
i 1
T
( j)
T (i )
0
 cT x*
k
   jc x  c x
T
j 1
*
T
*
Condizioni geometriche di ottimalità e illimitatezza
Ricordando il Teorema 5.5, dal Teorema 6.1 si
deduce immediatamente che se un
problema di PL è espresso in forma standard,
l’esistenza di una soluzione ottima implica
l’esistenza di un vertice ottimo.
Inoltre, il Teorema 3.6 fornisce uno strumento
operativo per identificare i vertici di un
poliedro.
Si può quindi concludere introducendo il
seguente corollario (6.1).
Condizioni geometriche di ottimalità e illimitatezza

Argomenti

Concetti preliminari

Condizioni geometriche di ottimalità e
illimitatezza

Condizioni algebriche di ottimalità
Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Esercizio

Esercizio

Esercizio

Esercizio

0 0 1 4   7 9 1 0 0 
1 0  9 4  2 3 0 1 0  



0 1  3 4   1 4 0 0  1
 1 2 0 0 0 1 2
Esercizio

0 0 1 4  35
T 1




z  cB AB b  [2 0 0] 1 0  9 4 6  2

 
0 0  3 4   4 
Esercizio

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Esercizio

Esercizio

Esercizio

Esercizio

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Esercizio

Esercizio
Esercizio

Esercizio

Esercizio

Esercizio

Esercizio
Esercizio

Esercizio

Condizioni algebriche di ottimalità

Condizioni algebriche di ottimalità

Esercizio

Esercizio

 1 
 0 
 
 0 
d  
 2 
2 3
 
3 2 
Esercizio

Condizioni algebriche di ottimalità
I risultati teorici fin qui conseguiti consentono
di definire una possibile strategia per risolvere
un problema di PL: si può costruire la forma
canonica del problema rispetto a tutte le basi
ammissibili
e
verificare
l’eventuale
soddisfacimento della condizione di ottimalità
espressa dal Teorema 6.2 o quella di
illimitatezza espressa dal Teorema 6.3. Se
esiste almeno una base ammissibile, è
evidente che, al termine della procedura,
essendo il numero delle basi ammissibili finito,
si giungerà a una delle due condizioni su
indicate.
Condizioni algebriche di ottimalità
