Risposte domande Metodi di ottimizzazione

PRO : Il metodo grafico si può applicare facilmente quando il problema ha due

 variabili.

CONTRO:

Se il problema avesse tre variabili decisionali la regione ammissibile

 diventerebbe una figura solida (un poliedro in particolare) mentre la funzione

obiettivo sarebbe un fascio di piani paralleli. È chiaro come la rappresentazione

grafica di tali enti geometrici diventi molto più complessa, seppur non

impossibile da studiare.

Perché se esiste ed è unica la soluzione di un problema di programmazione

lineare essa è uno tra i vertici del poliedro che delimita la regione di

ammissibilità?

La ragione per cui, se esiste ed è unica, la soluzione di un problema di

programmazione lineare è uno tra i vertici del poliedro che delimita la regione di

ammissibilità è spiegata dai teoremi di ottimizzazione e proprietà geometriche dei

politopi. In particolare:

Il teorema di Weyl-Minkowski afferma che ogni punto interno al politopo può essere

espresso come combinazione convessa dei suoi vertici.

Un altro teorema importante dimostra che, se la regione ammissibile è un politopo, il

massimo della funzione obiettivo non può essere un punto interno. Questo perché il

valore della funzione obiettivo cresce sempre spostandosi verso i vertici adiacenti

finché non si raggiunge una soluzione ottima, il che implica che il massimo si trova

sempre su un vertice.

In sintesi, queste proprietà assicurano che, in un problema di programmazione lineare,

una soluzione ottima è localizzata su uno dei vertici della regione ammissibile

rappresentata da un politopo.

Illustra il metodo del simplesso a due fasi

Il metodo del simplesso a due fasi è una variante del metodo del simplesso utilizzata

per risolvere problemi di programmazione lineare in cui non è immediato trovare una

soluzione di base ammissibile. Si articola in due fasi principali:

Fase 1: Trovare una soluzione di base ammissibile

Introduzione delle variabili artificiali o variabili slack per soddisfare il problema.

Definizione di una nuova funzione obiettivo che minimizza la somma delle variabili

artificiali:

∑

=−

Z variabili artificiali .

Applicazione del metodo del simplesso per minimizzare Z. Se Z=0 alla fine di questa

fase, esiste una soluzione di base ammissibile per il problema originale.

Fase 2: Risolvere il problema originale

Rimozione delle variabili artificiali dalla funzione obiettivo originale.

Applicazione del metodo del simplesso standard, utilizzando la soluzione ottenuta

nella Fase 1 come punto di partenza per trovare la soluzione ottimale del problema

originale.

Se Z>0 alla fine della Fase 1, il problema non ha soluzioni ammissibili, poiché non è

possibile soddisfare tutti i vincoli contemporaneamente.

Spiegare nel dettaglio la procedura risolutiva da utilizzare nel caso in cui x1

sia una variabile binaria.

La procedura per trattare una variabile binaria x1 in un problema di programmazione

lineare tramite il metodo del simplesso a due fasi si può descrivere come segue:

Procedura Risolutiva

1. Vincolo binario: Poiché x1∈{0,1}, il vincolo si traduce in: 0≤x1≤1.

2. Rilassamento lineare: Si sostituisce temporaneamente il vincolo binario con:

0≤x1≤1.

trattando x1 come una variabile continua per applicare il metodo del simplesso.

3. Risoluzione con il simplesso a due fasi:

Prima fase: Si introduce una funzione obiettivo ausiliaria per eliminare

 eventuali variabili artificiali e trovare una soluzione di base ammissibile.

Seconda fase: Si risolve il problema con la funzione obiettivo originale

 partendo dalla base ottenuta.

4. Branch-and-Bound: Se il rilassamento produce una soluzione non intera per x1,

si applica il metodo di Branch-and-Bound, suddividendo il problema in due

sottoproblemi:

In un ramo si fissa x1=0.

 Nell'altro ramo si fissa x1=1.



5. Ripetizione: Si continua a esplorare i rami fino a trovare la soluzione ottimale

binaria.

Illustra l’algoritmo di Kruskal per la ricerca del minimo albero ricoprente

L'algoritmo di Kruskal per trovare il minimo albero ricoprente (Minimum Spanning Tree)

è una tecnica che si basa sull'ordinamento dei lati del grafo e sull'aggiunta progressiva

di quelli con peso minimo, evitando la formazione di cicli.

Procedura

1. Si selezione il lato di lunghezza minima ( se più lati verificano

contemporaneamente la condizione, si sceglie in modo arbitrario);

2. Ad ogni iterazione si selezionano i lati che hanno la stessa lunghezza e si sceglie

quello che, aggiunti all’insieme di lati già scelti, non forma alcun ciclo;

3. All’aumentare delle iterazioni sono scelti i lati di lunghezza via via crescente.