Punto 2
Costo
di una soluzione di base
e condizioni di ottimalita’
Condizione di ottimalita’ di una
soluzione di base ammissibile
Il sistema Ax=b, x0, ARmxn (m<n) ha n-m gradi di liberta’ 
Posso fissare arbitrariamente il valore di n-m componenti
xN  xN
e determinare l’unico valore delle restanti xB che sia ammissibile
per il valore assegnato alle xN, risolvendo il sistema:
Se la soluzione x=[xB,xN] 0, allora e’ ammissbile.
Analizziamone il costo, cx, avendo espresso x in forma
parametrica rispetto alle componenti xN:
x B  A-1B (b - A N x N )
cx  c Bx B  c N x N  c BA B1 (b  A N x N )  c N x N
 c BA B1b  c BA B1A N x N  c N x N
 c BA B1b  (c N  c BA B1A N )x N
Nelle soluzioni di base si ha xN=0 quindi il costo cx si riduce a cB AB-1b. Tale
soluzione e’ ottima nel problema di minimo se per tutti gli indici j  N vale la
condizione cj = cj - cB AB-1Aj 0, per cui incrementare da 0 a 1 il valore di una
generica componente j fuori base modifica il costo di un valore d positivo.
Questa e’ la spiegazione algebrica, possiamo darne un’interpretazione geometrica?
Interpretazione geometrica del costo ridotto
_
di una variabile fuori base cj = cj - cBAB-1Aj
Ridefinisco il vettore colonna Aj secondo la base corrente B:
le coordinate di Aj secondo B sono la soluzione del sistema ABw=Aj che ha come
unica soluzione w=AB-1Aj. La componente i-esima di w esprime il contributo del iesimo vettore di base, Ai nel generare Aj.
min{cx: Ax=b, x0}  determinare la combinazione conica di costo minimo dei vettori
colonna della matrice A per esprimere b.
La soluzione di base B equivale a generare b coi soli vettori colonne di AB, usando
come moltiplicatori della combinazione conica l’unica possibile soluzione AB-1b.
E’ ottima se l’utilizzo di nessuna altra colonna (fra quelle fuori base) risulta piu’
conveniente.
Dato cB (vettore dei costi delle variabili in base) l’espressione cBAB-1Aj quantifica il
costo di utilizzo di un vettore pari a Aj attraverso le colonne di B, mentre cj esprime il
costo dell’utilizzo diretto del vettore Aj.
_ Aj, jN risulta + conveniente 
La base corrente e’ ottima  nessun altro vettore
-1
cj>cBAB Aj  cj>0
CONDIZIONI DI OTTIMO (min) =
_
NON-NEGATIVITA’ del VETTORE dei COSTI RIDOTTI c
esempio
• Prendiamo la base B={1,2,4} che
corrisponde al vertice c del politopo, di
coordinate x=[4,3,0,6,0] e costo cx=-27
• E’ ottima? Calcoliamo il vettore dei costi
ridotti: c - cBAB-1A
• Calcolo della matrice inversa AB-1
Un metodo per il calcolo di AB-1
A1A2A4
I3
Operazione
elementare
100 100 a3=a3-3a1 100 100 a2=½a2 100 100
021 010 
021 010 
01½ 0½0
320 001
020 -301
020 -301
a3=a3-2a2 100 1 0 0 a3= -a3 100 1 00 a2=a2-½a3

01½ 0½ 0
 01½ 0½0
00-1 -3-11
001 311
100 1 0 0
010 -3/2 0 ½
001 3 1 -1
I
AB-1
ex. verifica ABAB-1 = I
cBAB-1 = [-3 -5 0]
1 0 0 = [9/2 0 -5/2]
-3/2 0 ½
3 1 -1
Calcolo c3 - cBAB-1A3 = 0 - [9/2 0 -5/2] [100]T = -9/2<0
Calcolo c5 - cBAB-1A5 = 0 - [9/2 0 -5/2] [001]T = 5/2>0
Il valore della soluzione migliorerebbe aumentando il valore della
variabile x3, da 0 a un valore positivo
Verifica: il vettore A3 si puo’ generare come combinazione lineare
dei vettori della base B={1,2,4} come A1-3/2A2+3A4
(ha coordinate 1,-3/2,3=AB-1A3 secondo la base B)
con costo cB[1,-3/2,3]T= -3+15/2 > c3=0 (0 e’ il costo di A3)
Ex. Verifica che le variabili in base hanno costo ridotto nullo.
Perche’?
Incrementando x3 mi muovo lungo d
sullo spigolo di x5=0,
Aumentando x3 decrescono x4 e x1.
x1=0
10
8
a1: x1  4 (x3=0)
6
a2: x2  6 (x4=0)
c
4
d
a3: 3x1+2 x2  18 (x5=0)
2
x2=0
0
1
2
4
5
6
8
esercizio
Considera il sistema
6x1 +4x2 +x3 = 24
3x1 -2x2
+x4= 6
xi0  i
Disegna la regione ammissibile P nello spazio di x1 e x2,
enumera le basi ammissibili e calcola le coordinate dei
vertici di P associati.
Testa l’ottimalita’ della base B={1,2} per il problema min 2x1+x2-x4: x  P calcolando il vettore dei costi ridotti
Punto 2
Punto 4
Test di ottimalita’ della soluzione di base corrente
e calcolo del passo lungo la direzione di miglioramento
TEST: c - cBAB-1A 0?
 NO
 jN: cj- cBAB-1Aj<0

SI
STOP (ottimo)
facendo crescere xj da 0 a un valore positivo e,
le variabili in base
variano rispettivamente di - e AB-1Aj. (infatti se
xBAB=b, e Aj=
Punto 4
calcolo del passo lungo la direzione di miglioramento
Di quanto mi sposto? Fintanto che si rimane nell’ammissibilita’!!
Se il valore di xB viene opportunamente rimodulato per garantire il rispetto dei vincoli
del sistema Ax=b, occorre solo verificare il rispetto dei vincoli di segno (xB  0)
Come cambia xB?
facendo crescere la componente xj da 0 a un valore positivo eR,
le variabili in base variano rispettivamente di - e AB-1Aj
Infatti, ricordando che xB=AB-1b, e Aj=ABAB-1Aj, si ha:
ABxB + eAj - eAj=b  ABxB + eAj - eABAB-1Aj=b  AB (xB - eAB-1Aj) + eAj = b
La soluzione resta ammissibile fintanto che
xB - eAB-1Aj  0, i.e. AB-1b - eAB-1Aj  0
Solo le componenti iB per cui AB-1Aj ei  0 sono critiche
(ei indica il versore di proiezione sulle i-esima componente)
perche’ diminuiscono al crescere di xj (lungo la direzione di spostamento ci stiamo avvicinando
al rispettivo vincolo su cui le xi si annullano)
Il massimo valore di e e’ dato da
Max e: e  (AB-1b ei )/(AB-1Ajei) per le sole i tali che AB-1Aj ei  0
Criterio del minimo rapporto
per determinare l’indice
della variabile uscente dalla base
La prima componente che si annulla (indice i*)
esce di base al posto di xj.
i* = argmin {(AB-1bei /AB-1Ajei) t.c. AB-1Ajei>0}
La nuova base e’ data da B’= B\{i*}{j}
Esempio
sia B={1,2,4} la base corrente corrispondente al vertice in
figura d di coordinate x= [4,3,0,6,0],
entra in base x3 (j=3) per il test sui costi ridotti: chi esce?
Calcolo AB-1Aj=[1,-3/2,3]
all’aumentare di x3 diminuiscono le variabili in base che
hanno componente >0 nel generare A3.
Se  x3 allora  x1 e  x4, mentre  x2 .
Restano immutate le altre variabili fuori base (x5=0) perche’
la direzione di spostamento e’ aderente agli altri n-m-1
vincoli attivi nella soluzione di base corrente, mentre ci si
allontana dal vincolo su cui x3=0
1 0 0
ricordo AB-1 =
-3/2 0 ½
3 1 -1
4
b=
12
18
• A3 e’ il vettore [1,0,0]T.
• AB-1 A3 = [ 1, -3/2, 3 ]T
x=
4
3
0
6
0
• x1 ha valore 4 (x1 = AB-1be1 = 4)
Rapporto 4 / 1 = 4
• x4 ha valore 6 ( x2 = AB-1be3 = 6)
Rapporto 6 / 3 = 2
Il minimo si verifica per x4 che sara’ la prima componente
ad annullarsi procedendo lungo la direzione d, dopo un
passo di lunghezza 2
Punto 3
spostamento = miglioramento?
Vado da x=[xB=AB-1b,xN=0]T al punto
x’ = x + e[-AB-1Aj,0..1..0]T quindi mi sposto
da x di un passo e lungo la direzione
d= [-AB-1Aj,0..1..0]
Th: d e’ una direzione di miglioramento per un
problema di minimo (cd<0)
Dim. cd = cB [-AB-1Aj] + cNej = cj - cB AB-1Aj <0
per hp la variabile uscente xj ha costo ridotto <0
Passaggio al vertice adiacente
La nuova soluzione di base avra’ B={1,2,3}
Le coordinate del nuove vertice sono calcolabili
come x’ = x + e d, con d=[-AB-1Aj,0..1..0]
4
2
3
x
0
+
e . d
-1
2
3/2
6
1
=
2
6
-3
0
0
0
0
Casi speciali (1): Ottimo non limitato
• Non c’e’ limite allo spostamento che si puo’ effettuare lungo la
direzione di miglioramento d: spostandosi lungo d non ci si avvicina
ad alcun altro vincolo
• Tutti gli elementi di AB-1Aj sono 0  step e = + in quanto minorante di
un insieme vuoto
• P e’ un poliedro non limitato, combinazione convessa dei suoi vertici
V + combinazione conica dei suoi raggi estremi R.
• La funzione obiettivo c ha prodotto scalare <0 con almeno uno dei
raggi estremi r (per un problema di minimo). Scegliendo d=r si ha
una direzione di miglioramento (cd<0) illimitata (r∈R)
L’algoritmo riconosce la condizione AB-1Aj 0
(spostandosi lungo la direzione prescelta le variabili in base crescono)
e termina con label “OTTIMO ILLIMITATO”
La regione ammissibile
e’ un poliedro
a7
v1
illimitato
x2
r2
In evidenza in giallo la
combinazione convessa
dei vertici v1..v5
a2
10
C1 = Cono delle direzioni
di miglioramento d (tali che cd<0)
C2 = Cono delle
direzioni
c
di spostamento
illimitato
generato da r1 e r2
8
v2
a3
6
v3
4
In evidenza in rosso
i raggi estremi
che concorronno
alla definizione
del poliedro P
a1
d
v4
a8
r1
v5
2
0
1
2
4
5
6
8
x1
a6
C1  C2 
Casi speciali (2): degenerazione
• Si ha quando ci sono variabili in base a valore 0
• Geometricamente significa che sul vertice corrente sono attivi
piu’ degli n-m vincoli necessari a definirlo univocamente. Allo
stesso punto sono associate piu’ basi ammissibili.
• L’algoritmo puo’ ciclare selezionando sottoinsiemi diversi di
colonne corrispondenti alle diverse basi associate al punto.
• Se una variabile in base ha valore 0 nel punto corrente si
candida ad essere selezionata secondo il criterio del minimo
rapporto come variabile uscente, ma il passo associato alla
direzione di spostamento e’ 0.
Giunti in v da w, sono evidenziate possibili direzioni
lungo cui si compie un passo nullo, prima di
poter procedere lungo d
x2
10
Per evitare di ciclare
“regola anticiclo di Bland”
Tra le variabili entranti
con costo ridotto <0
scegli quella a indice minore
8
a1
6
a2
a7
a8
La degenerazione resta un fattore
negativo di una istanza, che inficia
la performance dell’algoritmo.
Spesso si verifica nel punto di
ottimo: lo raggiungo facilmente
ma non riesco a certificarlo
Ci aiutera’ la DUALITA’
a6
4
d
v
2
a3
0
1
w
2
4
5
6
8
x1
Punto 1
Determinazione
di una soluzione di base
ammissibile inizale (HL pg.107)
• Problema ausiliario P (metodo delle 2 fasi):
Moltiplico opportunamente i vincoli affinche’ sia b0
Introduco m variabili artificiali y1,..,ym
e una nuova funzione costo con vettore dei coefficienti c:
cx=0 x, cy=M y.
definisco il problema P
min cT [x,y] : Ax + I y = b, x,y 0
di cui y^i =bi i=1..m, e x^=0 e’ una soluzione di base
ammissibile. Risolvo P con il simplesso, a partire da [y^,x^]
Se l’ottimo [y*,x*] di P ha valore 0 (y*=0) il sottovettore x*(P)
e’ una soluzione di base ammissibile per P.
Altrimenti il problema NON ha soluzione
Porta P in forma standard e Risolvi il problema ausiliario P
If feasible (P) then k:=0, xk:=x(P), x*:=xk. Bk:=B(xk), Nk:={1..n}\Bk
else break
Inizializzazione
Repeat:
Calcola
ABk-1
x_k=[xBk,xN]=[ABk-1b,0]
_ ck = [c – cBkABk-1A]
If (ck 0) then x*:=xk, return (x*)
_ break
jIN := ArgMin jNk {cki}
_
inversa della matrice di base
soluzione di base
vettore dei costi ridotti
test di ottimalita’
 ! un indice jN con ckj <0
prendo l’indice del minimo ckj
coordinate del vettore Aj secondo Bk
-1 A
Calcola
A
Bk
jIN =[aijIN]
_
if (aijIN 0  i) then return (problema-illimitato),
break _
test di illimitatezza
_
iOUT:= ArgMin iBk {ABk-1bi/ aijIN | aijIN >0}
criterio del minimo rapporto,
variabile uscente
e := (ABk-1biOUT
/ aiOUT,jIN )
passo lungo la direzione
_
x := x + e [- aijIN,ejIN]
ejIN e’ il versore della coordinata jin
Bk+1:=Bk{jIN}\{iOUT}, Nk+1:={1..n}\Bk+1 aggiorna la base coi nuovi indici
_