Domande orale Ricerca operativa

Direzione di recessione?

(, )

∈ ℝ = ⊆ ℝ ∀ ∈

Un vettore si dice direzione di recessione (o raggio) di un poliedro se

∀ ≥ 0 + .

e la semiretta è completamente contenuta in

{

= ∈ : ≤ }

[Teorema] Le direzioni di recessione di un poliedro sono tutte e sole le

≤ 0.

soluzioni del sistema omogeneo di disequazioni

Resolution Theorem?

[Resolution Theorem (Teorema di Weyl)] Sia P un poliedro non vuoto e con almeno un vertice. Ogni

( ))

∈ = + , ∈ (

punto può essere espresso come con e d direzione di

.

recessione di

⊂ ℝ

Quando è un politopo (è un poliedro limitato. Un insieme si dice limitato se esiste una

costante M tale che ogni componente di ogni elemento di è limitato, in valore assoluto, da M),

l’unica direzione di recessione è il vettore 0 e il teorema è proprio il Resolution Theorem enunciato

per il caso limitato.

[Resolution Theorem (caso limitato)] Un poliedro non vuoto e limitato (politopo) coincide con

(( ))

=

l’involucro convesso dei suoi punti estremi: ( ))

∈ ( ∈

È immediato verificare che se allora dato che è un insieme convesso.

Invece non è evidente che ogni punto di un politopo sia esprimibile come una combinazione

convessa dei suoi punti estremi.

⊆ ∀, ∈ ≠

Un punto di un insieme convesso (un insieme è convesso se con ogni

(1 ) [0,1])

, = + − ∈ ∈

loro combinazione convessa appartiene a cioè per ogni si dice

, ∈

estremo se non esiste alcuna coppia di punti tale che sia combinazione convessa (il

, … , ∈ ℝ

vettore è combinazione convessa di m vettori se e solo se è contemporaneamente

1

∑ ∑

= = 1, , … , ≥ 0) .

affine e conica, ovvero con non banale di e

1

=1 =1

{ }

= , … , ⊆ ℝ () ⊆ ℝ

L’involucro convesso di è l’insieme di tutte le combinazioni

1

.

convesse di vettori in

Minimo locale implica minimo globale?

Consideriamo un problema di ottimizzazione convessa, cioè un problema in cui la funzione

[0,1]

: → ℝ : ℝ → ℝ ∀, ∈ ℝ ∈ =

obiettivo è convessa (Una funzione è convessa se , e

(1 ) () () (1 )()

+ − ≤ + −

si ha ) e la regione ammissibile è un insieme convesso

⊆ ℝ ∀, ∈ ≠

(Un insieme è convesso se con ogni loro combinazione convessa

(1 ) [0,1]):

= + − ∈ ∈

appartiene a Q, cioè: per ogni

(())

= ∈

′

[Proposizione] Ogni ottimo locale di è anche un ottimo globale

[Dim] (1 )

= ′ + − ∈ (0,1) ′

Sia con una combinazione convessa di e contenuta nell’intorno di

′

( ) ()

′. ∈ ≤ ′

ottimalità di perché è un insieme convesso; dato che è un minimo

′

() ( (1 )) (′) (1 )()

= + − ≤ + −

locale; dato che è convessa. Cioè

(1 )(′) (1 )() (1 )

− ≤ − −

dividendo per si ottiene la tesi.

[Corollario] L’insieme dei punti di minimo di è un insieme convesso.

Teorema fondamentale della PL? }

= { : ≤ , ∈ ℝ

[Teorema fondamentale della PL] Sia un problema di PL in forma

generale e il poliedro associato, che supponiamo non vuoto e con almeno un vertice. Allora:

> 0

1. Se esiste una direzione di recessione di tale che allora il problema di PL è

illimitato;

≤ 0

2. Se per ogni direzione di recessione di si ha allora il problema di PL ammette

.

ottimo finito. Inoltre, esiste una soluzione ottima che è un punto estremo di

[Dim] ∗ ∗

1. Si supponga per assurdo che il problema ammetta un ottimo finito , cioè un tale che

∗ ∗

( )

≠ +∞ − ≥ 0 ∈ .

e per ogni Per ipotesi d è una direzione di recessione di

∀ > 0 ∀ ∈ + ∈ .

cioè e si ha

∗ ∗ ∗

( ) ( )

− − ≥ 0 − − ≥ 0 − ≥

Quindi cioè da cui ma

∗

( )

−

questa relazione è in generale falsa. Infatti, è una quantità finita mentre

> 0 > 0.

può crescere senza limite dato che e per ipotesi

Geometricamente:

||||

, . > 0

è il prodotto scalare tra i vettori e anche definito come Se

> 0)

(cioè se vuol dire che esiste una direzione di recessione concorde con il gradiente

della funzione obiettivo. = { , … , }

2. Ordiniamo i punti estremi d i per valori non crescenti della funzione

1

≥ ≥ ⋯ ≥

obiettivo (cioè tali che ).

1 2 (( ))

∈ = + , ∈

Teorema di Weyl: ogni si può esprimere come con e d

direzione di recessione.

= + ∈ , + ≤ ≤ 0.

Quindi per ogni dato che per ipotesi

, = ( + ⋯ +

Siccome è una combinazione convessa di punti estremi di si ha 1 1

) + ⋯ + = 1, , … , ≥ 0 ( = + ⋯ + )

con e sfruttando

1 1 1 1

≥ ( = 2, … , ),

l’ipotesi dell’ordinamento, cioè che posso sostituire ogni

1

≤ ( + ⋯ + ) + ⋯ + = 1 ≤

con e scrivere ma quindi .

1 1 1 1 1

( )

≤ ≤ ∈ , ∈

Ricapitolando per ogni quindi è una soluzione ottima

1 1

.

per

Caso 1. Regione ammissibile non vuota e limitata:

• Esiste una soluzione ottima. Inoltre, esiste una soluzione ottima che è un punto estremo

(cioè un vertice).

Caso 2. Regione ammissibile non vuota e non limitata:

• Esiste una soluzione ottima che è un punto estremo (cioè un vertice);

• Esiste una soluzione ottima ma nessuna soluzione ottima è un punto estremo (e questo può

accadere solo se la regione ammissibile non ha punti estremi);

• +∞).

Il problema è illimitato (il valore della f.o. è

Il teorema fondamentale della PL ci dice come risolvere un problema di PL non vuoto, ma per

poterlo utilizzare è necessario conoscere la rappresentazione interna del poliedro (L’insieme dei

( )

vertici di un poliedro coincide con l’insieme dei suoi punti estremi).

In generale però nessun problema di PL è descritto da un numero finito di equazioni/disequazioni

lineari (rappresentazione esterna).

Per problemi con al più 3 variabili si può utilizzare la soluzione geometrica, ma per risolvere problemi

con più di 3 variabili è necessaria una descrizione analitica dei vertici.

},

= { : = , ≥ , ∈ ℝ

Se il problema è posto in forma standard una qualsiasi

=

soluzione ammissibile di è anche una soluzione del sistema di equazioni lineari (ma non

vale il viceversa).

Operazioni elementari su matrici?

Calcolo della matrice inversa: (ⅈ) )

( ()

= -esima

[Regola di Cramer] dove : matrice ottenuta sostituendo la colonna di con

()

.

il vettore :

Operazioni elementari su una matrice

• Moltiplicare una riga per una costante non nulla

• Sommare ad una riga una combinazione lineare delle altre

• Cambiare l’ordine delle righe [|]

[Teorema] Le operazioni elementari sulla matrice estesa di un sistema di equazioni lineari

′ ′

|

[ ]

= conducono a una matrice estesa di un sistema di equazioni equivalente.

Il metodo di Gauss-Jordan è una procedura iterativa che trasforma, tramite una serie di operazioni di

−1

= = .

pivot, il sistema nel sistema

Legame SBA-vertici? Teorema di caratterizzazione analitica dei

vertici? −1

[

= , 0]

La particolare soluzione del sistema che si ottiene annullando le componenti fuori

−1 −1

[

. ≥ 0 = , 0]

base, è detta soluzione di base associata alla matrice di base Se allora è

anche una soluzione del problema e per questo è detta soluzione di base ammissibile, in breve

.

SBA, di

La soluzione ottima è un vertice del poliedro (Un poliedro è l’intersezione di un numero finito m di

{

ℝ = ∈ : ≤ } ⊆ ℝ

semispazi affini di . L’insieme si dice semispazio affine) ma è anche

una Soluzione di Base Ammissibile del problema posto in forma standard.

[Algoritmo]

• Poni il problema di PL in forma standard

• Enumera tutte le basi e valuta tutte le SBA

• Seleziona la SBA con il miglior valore della funzione obiettivo

Il teorema fondamentale della PL afferma che se esiste una soluzione ottim