Domande aperte rivisitate e corrette di ricerca operativa 2

Illustrare le principali caratteristiche del metodo dei piani di taglio

Il metodo dei piani di taglio (anche detto metodo di Gomory) individua la soluzione ottima del

problema di PL01 in un numero finito di passi per raffinamenti successivi della formulazione

lineare del problema Le caratteristiche principali sono rappresentate da due concetti chiavi:

1.il rafforzamento di una disequazione valida per un poliedro

2.la sequenza di Gomory

pag. 33 34

Definire i principali passi del metodo dei piani di taglio

pag. 34 35

pag. 35 36

Spiegare il ruolo dell'algoritmo euristico nella soluzione dei problemi di partizione in clique dei

nodi di un grafo

Un metodo euristico molto semplice per la determinazione di una soluzione ammissibile di un

problema di partizione in clique dei nodi di un grafo tiene conto del criterio di ottimalità. e

favorisce le soluzioni in cui la somma della distanza relativa a coppie di nodi dello stesso cluster sia

minima.Tale somma sarà minore delle somme di distanze tra coppie di nodi appartenenti a due

cluster diversi

L’algoritmo euristico, costituisce un metodo semplice , che consente di trovare una soluzione

ammissibile nei problemi di partizione in clique dei nodi di un grafo

La disponibilità della soluzione euristica determinata gioca un ruolo determinante nel metodo

branch and bound rendendolo ancora più efficiente.

pag. 36 37

Illustrare i principali metodi di risoluzione del problema di partizione in clique dei nodi di un

grafo

I principali metodi di risoluzione di un problema di partizione in clique sono formulati con

disequazioni a due partizioni a cui applicare una euristica di separazione.

Applicare il metodo dei piani di taglio e quindi produrre una sequenza di Gomory E infine applicare

l’algoritmo euristico che consente di trovare le soluzioni ammissibili per cui la somma delle

distanze di coppie di nodi appartenenti ad un cluster è sempre minore di coppie non appartenenti

*******************************************

Il problema di partizione in clique dei nodi di un grafo rispetto alle disequazioni a due partizioni,

che comprende l’insieme delle disequazioni triangolo in particolari condizioni, può essere

approcciato con un metodo detto dei metodo dei piani di taglio(anche detto metodo di Gomory).

Tale metodo, si basa sui concetti: di rafforzamento di una disequazione valida per un poliedro e di

sequenza di Gomory. Il metodo dei piani di taglio individua la soluzione ottima del problema di

PL01 in un numero finito di passi per raffinamenti successivi della formulazione lineare del

problema ossia permette di rafforzare successivamente i rilassamenti del problema limitando il

numero di disquequazioni valide da generare grazie a due oracoli di separazione: enumerativo (e

quindi esatto) il primo, euristico il secondo

L’approccio di soluzione proposto permette di risolvere il problema invocando il metodo branch

and bound su un problema descritto da un numero molto limitato di disquazioni.

Quindi si applica un metodo euristico molto semplice per la determinazione di una soluzione

ammissibile di un problema di partizione in clique dei nodi di un grafo tiene conto del criterio di

ottimalità. e favorisce le soluzioni in cui la somma della distanza relativa a coppie di nodi dello

stesso cluster sia minima.Tale somma sarà minore delle somme di distanze tra coppie di nodi

appartenenti a due cluster diversi

Illustrare il metodo euristico per la soluzione dei problemi di partizione in clique dei nodi di un

grafo

pag. 37 38

Dato un grafo orientato G(N,A) dichiarare e definire in AMPL delle adeguate strutture dati per

rappresentare tale dati

E importante ribadire che nel file ` .mod vengono effettuate le dichiarazioni di insiemi e parametri,

mentre nel file .dat vengono effettuate le assegnazioni.

.mod .dat

Set N; Set N:=AB;

set A; set A:=AB;

param M(N,A); param M: AB:=

A -1

B 1;

Dato un insiemi di prezzi definiti sull'insieme di prodotti P = {bottiglie, lattine, cartoni, scatole,

barattoli}, con

Prezzo(bottiglie) = 10

Prezzo(lattine) = 4

Prezzo(cartoni) = 2

Prezzo(scatole) = 3

Prezzo(barattoli) = 5

dichiarare e definire in AMPL delle adeguate strutture dati per rappresentare tale dati

E importante ribadire che nel file ` .mod vengono effettuate le dichiarazioni di

insiemi e parametri, mentre nel file .dat vengono effettuate le assegnazioni.

.mod .dat

Set P; Set P:= bottiglie, lattine, cartoni, scatole, barattoli;

param vett (prezzo); param vett := bottiglie 10 lattine 4 cartoni 2 scatole 3 barattoli

5;

Illustrare i principali operatori per gli insiemi disponibili in AMPL

I principali operatori per gli insiemi sono UNION, DIFF, INTER, SYMDIFF . Per cui dati due insiemi A

e B A UNION B restituisce l’unione, così vale per l’operatore differenza, intersezione e differenza

simmetrica (symdiff )

pag. 38 39

Spiegare le principali differenze tra insiemi e parametri in AMPL

Gli insiemi definiscono gli elementi di base con i quali si possono indicizzare variabili, parametri e

vincoli del modello, I parametri rappresentano i dati di un problema.

Un insieme contiene 0 oppure più elementi, ogni elemento deve essere distinto dagli altri e

ciascun elemento è una lista ordinata, tutti gli elementi devono avere per lunghezza della lista

detta dimensione. I parametri sono i dati del problema il cui valore resta sempre costante. Insiemi

e parametri vanno dichiarati e definiti.

Formulare il problema di flusso di costo minimo come problema di Programmazione Matematica

pag. 39 40

Illustrare il problema del flusso di costo minimo (MCF)

Dare la definizione di flusso e di rete di flusso

pag. 40 41

Descrivere come è possibile formulare il problema di flusso di costo minimo in AMPL

pag. 41 42

Descrivere le istruzioni utili al caricamento e soluzione di un modello in AMPL

Per caricare un modello usiamo le istruzioni model e data:

L’istruzione model seguita dal nome del file contenente le dichiarazioni serve per acquisire la

struttura del modello ampl: model MCF.mod;

L’istruzione data seguita dal nome del file contenente le definizioni serve per acquisire i dati del

modello ampl: data MCF.dat;

A questo punto è stato caricato:1. il modello di Programmazione lineare del problema MCF 2. I

dati relativi a un’istanza del problema MCF

il solutore di default è MINOS

Per risolvere il problema MCF scegliamo come solutore CPLEX

Per indicare all’interprete AMPL di utilizzare CPLEX come solutore, utilizziamo l’istruzione option

seguita dal parametro di cui vogliamo cambiare il valore (in questo caso, il solutore quindi il

parametro è solver) seguito dal nuovo valore del parametro (in questo caso cplex)

ampl: option solver cplex;

Illustrare le principali istruzioni AMPL per la dichiarazione di variabili, funzione obiettivo e

vincoli

pag. 42 43

Descrivere le istruzioni utili alla dichiarazione del problema di flusso di costo minimo in AMPL

Set e param per definire insiemi e parametri

var x {j in ARCHI} >= 0, <= capacita[j];

subject to Incidenza {i in NODI}:

sum {j in ARCHI} M[i,j] * x[j] = domanda[i];

pag. 43 44

Definire il problema del cammino di costo minimo da s a t

Dimostrare che il problema del cammino di costo minimo da s a t è un caso particolare di

problema di flusso di costo minimo

Spiegare la differenza tra una rete di flusso e una rete di flusso con i nodi speciali pozzo e

destinazione

A differenza della rete di flusso, una rete di flusso con i nodi speciali pozzo e destinazioni aggiunge

una coppia di nodi speciali…

pag. 44 45

Descrivere come è possibile formulare il problema del cammino di costo minimo da s a t in

AMPL

pag. 45 46

Descrivere le istruzioni utili alla dichiarazione del problema del cammino di costo minimo da s a

t in AMPL

La dichiarazione di insiemi e parametri che descrivono la rete di flusso (G,c,x,d,w):

• gli insiemi N e A e il parametro a due dimensioni M

• i vettori c, d e w

• la dichiarazione delle variabili: parametro a una dimensione x

• la struttura e la definizione della funzione obiettivo wTx

• la struttura e la descrizione dei vincoli: M x = d, 0|A| ≤ x ≤ c

i valori dei coefficienti del modello SP che sono diversi dai coefficienti del modello MCF in quanto

• le domande d sono pari a -1 per il nodo s, 1 per il nodo t e 0 per tutti gli altri nodi in N

• le capacità c sono pari a infinito per tutti gli archi in A

pag. 46 47

Scrivere la formulazione del problema del massimo flusso da s a t

Premessa se vuoi allungare il brodo:

pag. 47 48

Definire il problema del massimo flusso da s a t

Dimostrare che il problema del massimo flusso da s a t è un caso particolare di problema di

flusso di costo minimo

Definire le istruzioni MODEL e DATA in AMPL e descrivere ruolo e caratteristiche dei file .mod e

.dat

L’istruzione model seguita dal nome del file contenente le dichiarazioni serve per acquisire la

struttura del modello ampl: model MF.mod;

L’istruzione data seguita dal nome del file contenente le definizioni serve per acquisire i dati del

modello

ampl: data MF.dat;

MCF.mod contiene le dichiarazioni relative alla struttura del modello ovvero: insiemi e parametri,

variabili, vincoli e funzione obiettivo.

MF.dat contiene i valori dei coefficienti del modello come le domande, le capacità, i costi

pag. 48 49

Definire le istruzioni SOLVE e DISPLAY in AMPL

Una volta caricati modello e valori dei coefficienti e selezionato un opportuno solutore, per

invocare l’impiego del solutore per risolvere l’istanza di problema corrente usiamo l’istruzione

solve

ampl: solve;

Una volta portata a termine l’istruzione, il compilatore visualizza le informazioni di log restituite

dal solutore per l’invocazione precedente

Una volta risolto il problema, se è stata determinata la soluzione ottima (come in questo caso), il

valore delle variabili corrispondenti alla soluzione ottima possono essere visualizzati tramite

l’istruzione display seguita dal nome della o delle variabili che vogliamo visualizzare (in questo

caso il parametro di una dimensione x)

ampl: display x;

Descrivere come è possibile formulare il problema del massimo flusso da s a t in AMPL

Per poter formulare il problema del massimo flusso da s a t in AMPL,nel file .mod dove dichiariamo

tutti gli elementi che definiscono la struttura del modello, cioè insiemi e parametri. In questo caso

dobbiamo considerare il grafo G’ contiene l’arco (t,s) che il grafo originale G non aveva

•gli insiemi N e A’ e il parametro a due dimensioni M

•i vettori c, d e w

Quindi nel dile .dat andiamo a definire insiemi e parametri che descrivono la rete di flusso

(G’,c,x,d,w), cioè i coefficienti del modello con domande tutte uguali a 0 e costo pari a 1 solo pe