Ric oper def - ricerca operativa in ordine alfabetico PDF

Preview

Summary

ricerca operativa in ordine alfabetico...

Description

•

AMPL è ? Un linguaggio di programmazione che permette di definire un qualsiasi problema di programmazione matematica

•

AMPL è ? Un linguaggio di programmazione che permette la modellazione di problemi di programmazione matematica lineari e non lineari , caratterizzati da variabili intere e continue

•

Anche nel caso in cui non si conosca il valore ottimo di un problema (PL01) , la conoscenza del limite inferiore per il problema ci permette di stabilire? Quanto sia "buona" una qualsiasi soluzione ammissibile

•

Applicando il criterio di ottimalità alla soluzione di base relativa alle colonne B= (1,5) del problema di seguito caratterizzato .. MAX 2X1-X3; X1+X2=0? il numero di soluzioni di base ammissibili è ? 2

•

Dato il seguente problema di PL MAX 2x1 ; 5x2=3 ; x1,x2>=0. il numero di soluzioni di base massimo è ? 6

•

Dato il seguente problema di PL?. MAX 2x1 ; 5x2=3 ; x1,x2>=0..il numero di soluzioni di base è? 5

•

Dato il seguente problema di PL? MAX 2x1 ; 5x2=3 ; x1,x2>=0...il numero di soluzioni di base non ammissibili è ? 3

•

Dato un problema di PL01 di minimizzazione con insieme delle soluzioni S a n componenti e vettore dei costi c ? L'insieme delle soluzioni ammissibili è incluso in [0,1] n

•

Dato un problema di PL01 con insieme delle soluzioni ammissibili S , una formulazione lineare del problema? Consente sempre di separare i vettori a componenti [0,1] corrispondenti a soluzioni ammissibili in S dai vettori a componenti [0,1] che non appartengono a S

•

Dato un limite inferiore LB per un problema di PL01 di minimizzazione ? Tanto più il valore di una soluzione ammissibile è vicino a LB , tanto migliore è la soluzione

•

Dato un limite inferiore LB per un problema di PL01 di minimizzazione? la differenza (gap) tra valore di una soluzione ammissibile e limite inferiore (LB) , ci permette di capire quanto la soluzione ammissibile sia lontana dalla soluzione ottima del problema PL01

•

Dato un insieme non vuoto C e una funzione f definita in C a valori reali (f:C->R), il problema di massimizzazione associato alla coppia (C,f) consiste in? Determinare, se esiste, un elemento x* in C tale che f(x*) >= f(x) per ogni x in C Dato un insieme non vuoto C e una funzione f definita in C a valori reali (f:C->R), il problema di minimizzazione associato alla coppia (C,f) consiste in? Determinare, se esiste, un elemento x* in C tale che f(x*) =2 ; X2>=1 ; X1,X2>=0... Applicando il criterio di illimitatezza alla seguente soluzione di base relativa alle colonne B=(2,1).... possiamo concludere che ? il problema è illimitato Si consideri il seguente problema di PL in forma standard..... applicando il criterio di ottimalità alla seguente soluzione di base....... possiamo concludere che ? Occorre determinare un'altra soluzione di base Si consideri un problema di PL in 4 variabili con costi ridotti (0,0,1,1) ? possiamo concludere che la soluzione di base corrente sia ottima

•

Si consideri un problema di PL in 5 variabili con costi ridotti (-1,0,1,0,1)? non possiamo concludere che la soluzione di base corrente sia ottima

•

Si consideri il grafo G(N,A) in figura e si determini il valore della componente M ( a,ce ), della matrice di incidenza nodi archi di G(N,A)? 0

•

Si consideri il grafo G(N,A) in figura e si determini il valore della componente M ( e,ce ), della matrice di incidenza nodi archi di G(N,A)? 1

•

Si consideri il grafo G(N,A) in figura e si determini il valore della componente M ( c ,ce ), della matrice di incidenza nodi archi di G(N,A)? -1

•

Si consideri il grafo G(N,A) in figura e si consideri le componenti della riga della matrice di incidenza nodi archi M di G(N,A) relativa al nodo c ? Nella riga ci saranno 3 componenti di valore -1 e 2 di valore 1 e

•

Si consideri il grafo G(N,A) in figura e si consideri le componenti della riga della matrice di incidenza nodi archi M di G(N,A) relativa al nodo e ? Nella riga compariranno solo i valori 0 e 1

•

Si consideri il grafo G(N,A) in figura e si consideri le componenti della colonna della matrice di incidenza nodi archi M di G(N,A) relativa all'arco cf? Nella colonna ci sarà il valore 1 in corrispondenza della riga relativa al nodo f e il valore -1 in corrispondenza della riga relativa al nodo c

• •

Si consideri la matrice 2x2 I2. La sottomatrice ottenuta eliminando la seconda riga è? (1 0)

•

Si consideri l'insieme convesso [1,2] di valori compresi tra 1 e 2 ? 1 è punto estremo

•

Siano x e y soluzioni ammissibili per un problem di Pl di minimizzazione e per il suo problema duale? il valore della soluzione x è non minore del valore della soluzione y

•

Siano x e y soluzioni ammissibili per un problem di Pl di minimizzazione e per il suo problema duale? se il loro valore è uguale allora x e y sono soluzioni ottime per i rispettivi problemi

•

Siano x e y soluzioni ammissibili per un problem di Pl di massimizzazione e per il suo problema duale? il valore della soluzione x è non maggiore del valore della soluzione y

•

Siano x e y soluzioni ammissibili per un problem di Pl di massimizzazione e per il suo problema duale? se il loro valore è uguale allora x e y sono soluzioni ottime per i rispettivi problemi

•

Se nel problema della dieta consideriamo 4 alimenti e 3 fattori nutritivi ? la formulazione matematica ha 4 variabili e 3 vincoli

•

Se nel problema della dieta consideriamo 3 alimenti e 2 fattori nutritivi ? la formulazione matematica ha 3 variabili non negative

•

Se una soluzione di base ammissibile x=(xb, xn) è degenere ? almeno una componente di Xb è nulla

•

• • •

Un modello matematico è? Indipendente dai dati specifici del problema

•

Un modello matematico può essere? O statico o dinamico, ma non entrambi

•

Un modello matematico può essere? O stocastico o deterministico, ma non entrambi

•

Un problema di ottimizzazione è inammissibile può? O ammettere soluzione ottima o essere inammissibile o essere illimitato (inferiormente o superiormente)

•

Un problema di ottimizzazione è inammissibile se? L'insieme delle soluzioni ammissibili è vuoto

•

Un problema di ottimizzazione di minimizzazione è inferiormente illimitato se? Preso un valore M esiste sempre una soluzione ammissibile di valore minore di M

•

Un problema di ottimizzazione di massimizzazione è superiormente illimitato se? Preso un

valore M esiste sempre una soluzione ammissibile di valore maggiore di M • •

Un problema di ottimizzazione è illimitato? O superiormente o inferiormente Un insieme può essere rappresentato? In forma implicita o in forma esplicita • Un insieme in AMPL ? Può assumere un valore di default • Un problema di Programmazione Lineare in forma generale è? Un problema di Programmazione Lineare di minimizzazione con vincoli di maggiore o uguale e variabili non negative • • • •

Un problema di Programmazione Lineare in forma Standard è ? un problema di Programmazione Lineare con vincoli di uguaglianza e con variabili non negative Un problema di PL di minimizzazione può essere? Illimitato inferiormente Un problema di PL di Massimizzazione può essere ? Illimitato superiormente Un problema di PL di massimizzazione si definisce illimitato superiormente se ? Comunque scelto un valore M esiste una soluzione ammissibile di valore Maggiore di M

•

Un problema di PL di minimizzazione si definisce illimitato inferiormente se? Comunque scelto un valore M esiste una soluzione ammissibile di valore minore di M

•

Un problema di PL inammissibile ? Non ammette soluzioni ammissibili

•

Un problema di ottimizzazione può essere sempre scritto nella sua forma generale? Vero

•

Un problema di Knapsak binario con 4 variabili di decisione ? Ammette al più 16 soluzioni ammissibli

•

Un problema di Knapsack binario con 5 variabili di decisione? Ammette al più 32 soluzioni ammissibili

•

Un poliedro è ? intersezione di un numero finito di semispazi chiusi

•

Un sistema Ax=b si definisce incompatibile se? L'insieme delle soluzioni del sistema Ax=b è vuoto

•

Un sistema Ax=b è compatibile se e solo se? Il vettore dei termini noti b è esprimibile come combinazione lineare di ogni base dell'insieme B dei vettori colonna matrice A

•

Un sistema Ax=b è compatibile se e solo se ? una base dell’insieme B dei vettori colonna della matrice A è anche una base dell’insieme dei vettori colonna della matrice (A,b)

•

Un sistema Ax=b è compatibile se e solo se? Il rango dell'insieme B dei vettori colonna della matrice A è pari al rango della matrice dei coefficienti estesa del sistema Ax=b

•

Un vettore Z si dice direzione di un poliedro se ? ogni semiretta con origine in un punto del poliedro e direzione z apparteniene al poliedro

•

Una soluzione di base x di un problema di PL in forma standard con m vincoli e n variabili si definisce degenere se ? la cardinalità dell'insieme delle componenti positive di x è minore di m

•

Una soluzione di base x di un problema di PL in forma standard è ammissibile se e solo se? le colonne della matrice A con indice nell'insieme di supporto S(x) sono linearmente indipendenti

•

Una sequenza di operazioni elementari effettuate a partire da una matrice A produce? Una matrice A' equivalente ad A

•

Una soluzione di base ammissibile di un problema di PL? è una soluzione di base a componenti non negative

•

Una soluzione di base di un problema di PL? è ammissibile se rispetta i vincoli di non negatività

• Una base di un problema di PL in forma standard? è sempre invertibile

•

Risolvendo il seguente sistema di equazioni lineari

si può concludere che? Il sistema è compatibile

• •

Risolvendo il seguente sistema di equazioni lineari si può concludere che? una soluzione del sistema è ( 0,2,0,4,8)

• Risolvendo il seguente sistema di equazioni lineari si può concludere che? il sistema non ammette soluzioni

•

• Risolvendo il seguente sistema di equazioni lineari

si può concludere che? il sistema ammette la soluzione ( 4,2,0,8,0)

• • Risolvendo il seguente sistema di equazioni lineari si può concludere che? il sistema è incompatibile

• Risolvendo il seguente sistema di equazioni lineari

si può concludere che? una riga del sistema è ridondante

• Risolvendo il seguente sistema di equazioni lineari si può concludere che ? Una soluzione del sistema è (0,0,1) •

Si considerino i due problemi di PL?

i due problemi sono equivalenti

•

Si considerino i due problemi di PL? i due problemi sono equivalenti

•

Si considerino i due problemi di PL? i due problemi sono equivalenti

Si considerino i due problemi di PL ? I due problemi non sono equivalenti Domande Aperte

•

Dati due formulazioni di un problema, definire l'equivalenza tra le due formulazioni?

• Dati due problemi di PL, definire l'equivalenza tra i due problemi

•

•

Descrivere la metodologia branch and bound per la soluzione di un problema di PL01?

Descrivere le possibili strategie di soluzione per il metodo branch and bound per la soluzione di un problema di PL01?

• Descrivere le possibili strategie di separazione per il metodo branch and bound per la soluzione di un problema di PL01

•

Descrivere in maniera sintetica l'approccio modellistico per la risoluzione di problemi di

decisione? Nell'approccio modellistico si modella la famiglia delle soluzioni ammissibili come un insieme di soluzioni di un problema matematico, detto modello Esso è composto dalle seguenti fasi: ANALISI DEL PROBLEMA DECISIONALE – Si analizza la struttura del problema decisionale per individuare i legami logici tra gli elementi della decisione e gli obiettivi da perseguire nel processo decisionale ; - IDENTIFICAZIONE DEL MODELLO – Si identifica il modello matematico e se ne descrivono le caratteristiche principali (variabili, vincoli e funzione obiettivo) in termini matematici; - ANALISI DEL MODELLO – In base al tipo di modello matematico, si derivano matematicamente (i) condizioni di esistenza e (eventualmente) unicità della soluzione ottima; (ii) condizioni di ottimali e (iii) stabilità delle soluzioni; - SOLUZIONE NUMERICA – In base al tipo di modello matematico, si seleziona e si adotta un algoritmo di calcolo (algoritmo di soluzione) che determini la soluzione ottima del problema decisionale; VALIDAZIONE DEL MODELLO – La soluzione ottima determinata viene interpretata dal punto di vista decisionale e validata attraverso una verifica sperimentale oppure tramite metodi di simulazione Se la soluzione ottima determinata non è accettabile oppure non ha rilievo pratico, occorre tenere conto di ulteriori vincoli nel problema decisionale.

•

•

Descrivere il problema della dieta e formularlo matematicamente

Descrivere il problema del trasporto e formularlo matematicamente

•

Dare la definizione di combinazione lineare, incolucro lineare e base di un insieme? Un vettore y ∈ ℝ si definisce combinazione lineare di k vettori {x1, x2, ..., xk} ∈ ℝ se e solo se n si definisce esistono k numeri reali a1, a2, ... , ak tali che y = ∑i aixi Dato un insieme S ∈ ℝ involucro lineare di S l'insieme di tutte le possibili combinazioni lineari dei vettori di S. Un insieme finito ={ 1,…, } con ≥2 è linearmente dipendente se e solo se esiste un vettore ∈ che può essere espresso come combinazione lineare degli altri

•

Dare la definizione di poliedro e dimostrare che è un insieme convesso

• Dare la definizione di direzione di un poliedro

•

Data una soluzione di base ammissibile non necessariamente ottima, illustrare come sia possibile determinare una nuova soluzione di base ammissibile di costo non superiore

•

Dare la definizione di problema di ottimizzazione inammissibile e di problema di ottimizzazione illimitato? Un problema di ottimizzazione si dice inammissibile o vuoto se

non esistono soluzioni ammissibili, vale a dire se risulta vuoto l’insieme delle soluzioni ammissibili (X = ∅); Un problema di minimizzazione [massimizzazione] si dice illimitato inferiormente [superiormente] se comunque scelto un valore esiste una soluzione ammissibile € tale che  f(x) < M [ f(x) > M ] •

Dare la definizione di problema di ottimizzazione, di soluzione ammissibile e soluzione ottima? Data una funzione f ed un insieme X, un problema di Ottimizzazione consiste nel

determinare, se esiste, un punto di minimo della funzione f tra i punti dell’insieme X. La funzione f viene chiamata funzione obiettivo e l’insieme X insieme ammissibile cioè l’insieme delle possibili soluzioni del problema. Un punto x ∈ X si chiama soluzione ammissibile Un punto ammissibile ∈ è una soluzione ottima di un problema di ottimizzazione se f( x ) ≤ f( x )

• Dare la definizione di problema di PL inammissibile e di problema di PL illimitato? Dare la definizione di formulazione ottima di un problema di PL01

•

• Dare la definizione di formulazione lineare di un problema di PL01?

• Dare la definizione di lower bound di un problema di PL01?

• Dare la definizione di soluzione di base degenere? • Dare la definizione di base, soluzione di base e soluzione di base ammissibile?

•

Dimostrare che il problema di massimizzazione MAX(X,f) associato alla coppia (X,f) è equivalente al problema di minimizzazione associato alla coppia (X,-f) ? MAX( X,f ) ammette

una soluzione ottima. Quindi esiste una soluzione ammissibile ∈ ∈  in cui la funzione assume il valore massimo f( x)≥f (x )∀ x ∈ X Ambo i membri della diseguaglianza sono numeri reali. Moltiplicandoli per il valore 1 otteniamo -f( x)≤-f( )∀ x ∈ X Abbiamo quindi determinato un punto x∈ X in cui la funzione −f assume il valore minimo, che è equivalente al problema di minimizzazione MIN (X, -f) • Dimostrare che un problema di ottimizzazione può essere sempre scritto nella sua forma generale? Un problema di ottimizzazione può essere sempre scritto nella sua forma generale max{ ( ): ∈ ℝ : ( ) ≤ 0 , = 1, … , } - Se il problema è di minimizzazione, possiamo infatti usare il risultato di equivalenza tra problemi di minimizzazione e massimizzazione min f(x) = - max -f(x) - Se abbiamo un vincolo di maggiore o uguale ( ) ≥0, possiamo riscrivere il vincolo come vincolo di minore o uguale − ( )≤0 - Se abbiamo un vincolo di uguaglianza ℎ( )=0, possiamo riscrivere il vincolo come due vincoli separati ℎ( )≤0 e ℎ( )≥0

• Dimostrare che un vettore di un poliedro è una soluzione di base ammissibile se e solo se è un vertice del poliedro?

Dimostrare che se una soluzione di base ammissibile è non degenere allora esiste una e una sola base B tale che?

• Descrivere quali sono le principali differenze tra la Programmazione Lineare Intera e la Programmazione Lineare {0,1}

•

Dimostrare che un iperpiano è un insieme convesso

•

•

Dimostrare che un semispazio chiuso è un insieme convesso

Dimostrare che un vettore è una direzione del poliedro P {x∈Rn: Ax≥b} se e solo se è soluzione del sistema omogeneo Ax ≥ 0?

• Dimostrare che se il problema primale di minimizzazione è illimitato inferiormente allora il problema duale è inammissibile

•

Dimostrare che se x e y sono soluzioni ammissibili di una coppia primale/duale e il loro valore è uguale, allora x e y sono soluzioni ottime dei rispettivi problemi

•

Dimostrare che se il problema primale di massimizzazione è illimitato superiormente allora il problema duale è inammissibile

Dimostrare che il problema duale del duale è il problema primale?

•

Dimostrare che se il problema primale è inammissibile allora il problema duale è illimitato o inammissibile? Se il problema primale è inammissibile, allora il suo duale non può ammettere soluzione ottima. Infatti, se il duale ammette una soluzione ottima, per la proprietà 5. anche il primale ammette soluzione ottima. Quindi il problema duale non può ammettere soluzione ottima e quindi può essere illimitato oppure inammissibile.

• Definire il processo di formulazione di un problema di Programmazione Lineare Intera

• Definire la proprietà di equivalenza tra problemi di PL e fornire almeno un esempio di due problemi di PL equivalenti?

• Definire un criterio di ordinamento delle formulazioni di un problema di PL01?

•

Enunciare e dimostrare il criterio di illimitatezza?

• Enunciare e dimostrare il criterio di ottimalità di una soluzione di base ammissibile?

• Enunciare e dimostrare il teorema della dualità debole?

•

Enunciare e dimostrare le condizioni di complementarietà per la...