Domande aperte Ricerca Operativa

LEZ 2

14. Quali sono gli elementi distintivi di un problema di

decisione

Un problema di scelta in cui si deve prendere una decisione tra un

elevato numero di soluzioni (ammissibili), alternative tra loro, sulla

base di uno o più criteri. Ogni soluzione ammissibile rappresenta

una decisione ed è caratterizzata da un costo (da minimizzare) o da

un vantaggio (da massimizzare)

15. Qual è la differenza tra analisi del problema decisionale

e identificazione del modello nell'approccio modellistico?

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

16. Quali sono i passi previsti per l'identificazione del

modello nell'approccio modellistico?

L’identificazione del modello prevede i seguenti passi

– Definizione di opportune variabili di decisione, dette anche

incognite del problema: occorre definirne una per ogni grandezza

reale del problema

– Definizione della funzione obiettivo da massimizzare o da

minimizzare che sia funzione delle variabili di decisioni

– Definizione dell’insieme dei vincoli del problema: ciascun vincolo

(o famiglia di vincoli) esprime matematicamente i legami esistenti

tra le variabili di decisioni e le limitazioni cui tali variabili sono

soggette

18. Descrivere in maniera sintetica l'approccio modellistico

per la risoluzione di problemi di decisione

Si modella la famiglia delle soluzioni ammissibili come un insieme di

soluzioni di un problema matematico, detto modello. Le fasi della

modellazione sono:

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

ottimalità 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.

LEZ 03

20. 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, cioè se risulta vuoto l’insieme delle

soluzioni ammissibili X = Ø(insieme vuoto).

Un problema di minimizzazione [massimizzazione] si dice illimitato

inferiormente [superiormente] se comunque scelto un valore M

esiste una soluzione ammissibile x € X t.c. f(x) < M [f(x) > M]

21. Dare la definizione di problema di ottimizzazione, di

soluzione ammissibile e soluzione ottima

Consideriamo un insieme non vuoto X != Ø(insieme vuoto), sia nota

una funzione f: X -> R che a ogni elemento dell’insieme X associ un

valore reale in R. Si definisce problema di minimizzazione MIN(X,f)

associato alla coppia (X, f) il problema di determinare (se esiste)

l’elemento x dell’insieme X in cui la funzione f assume il valore

minimo, vale a dire f(x(trattino sopra)) <= f(x) per ogni x € X

L’elemento x(trattino sopra) viene detto punto di minimo di f in X.

Min f(x) x € X

x

L’insieme X in cui le variabili del problema sono definite viene detta

insieme delle soluzioni ammissibili mentre la funzione f è detta

funzione obiettivo.

In molti casi di pratico interesse, l’insieme delle soluzioni

ammissibili X è definito come l’insieme delle soluzioni di un sistema

di disequazioni ed equazioni dette vincoli del problema.

Si definisce problema di massimizzazione MAX(X,f) associato alla

coppia(X,f) il problema di determinare qualora esistesse, la

soluzione ottima. La soluzione ottima del problema di

massimizzazione MAX(X,f) è l’elemento x(trattino sopra)

dell’insieme X in cui la funzione f assume il valore massimo, vale a

dire: f(x(trattino sopra)) >= f(x) per ogni x € X

L’elemento x(trattino sopra) viene detto punto di massimo di f in X.

Il problema di massimizzazione associato alla coppia (X,f) è

equivalente al problema di minimizzazione associato alla coppia (X,-

f).

22. Dimostrare che il problema di massimizzazione MAX(X,f)

associato alla coppia (X,f) è equivalente al problema di

minimizzazione associato alla coppia (X,-f)

Il problema di massimizzazione MAX(X,f) associato alla coppia (X,f)

equivale al problema di determinare, qualora esistesse, l’elemento

x(trattino sopra) dell’insieme X in cui la funzione f assume il valore

massimo. Abbiamo 3 casi possibili:

1. MAX(X,f) è inammissibile

In questo caso, X = Ø(insieme vuoto) e quindi per definizione

anche MIN(X,f) è inammissibile.

2. MAX(X,f) è illimitato superiormente

In questo caso, comunque scelto un valore M esiste una

soluzione ammissibile x(trattino sopra) € X t.c. f(x(trattino sopra))

> M

Ambo i membri della diseguaglianza sono numeri reali.

Moltiplicandoli per il valore -1 otteniamo -f(x(trattino sopra)) <

-M

Definendo M(trattino sopra) = -M, avremo –f(x(trattino sopra)) <

M(trattino sopra)

Quindi esiste sempre una soluzione x(trattino sopra) € X t.c. –

f(x(trattino saopra)) < M(trattino sopra) per ogni valore M e, per

definizione, MIN(X,-f) è illimitato inferiormente.

3. MAX(X,f) ammette una soluzione ottima

In questo caso esiste una soluzione ammissibile x(trattino sopra)

€ X in cui la funzione f assume il valore massimo f(x(trattino

sopra)) >= f(x) per ogni x € X

Ambo i membri della diseguaglianza sono numeri reali.

Moltiplicandoli per il valore -1 otteniamo -f(x(trattino sopra))

<= -f(x) per ogni x € X

Abbiamo quindi determinato un punto x(trattino sopra) € X in cui

la funzione –f assume il valore minimo, che è equivalente al

problema di minimizzazione MIN(X,-f)

LEZ 04

15. Dare la definizione di combinazione lineare, incolucro

lineare e base di un insieme

n

Un vettore y € R si definisce combinazione lineare di k vettori

n

{x ……,x } appartenenti a R se e solo se esistono k numeri reali

1 k

alfa ,…..,alfa t.c. y = sommatoria da i = 1 a k alfa x

1 k i i

m mxn

Il vettore y € R ottenuto dal prodotto della matrice A € R e del

n

vettore x € R y = Ax è la combinazione lineare a coefficienti x ,

1

…..,x delle n colonne della matrice A

n

Ax = [y = sommatoria da j=1 a n a x ]i=1,….,m T

i ij j

L’insieme di tutte le possibili combinazioni lineari di vettori

n

appartenenti a un insieme S di R viene detto involucro lineare di S

e indicato con lin(S)

- lin(S) è l’insieme di tutte le combinazioni lineari di una generica

base di B di S

- quindi B è una base di lin(S)

- quindi rango(lin(S)) = rango(S) n

Un sottoinsieme B ⊆ S di un insieme S ⊆ R è una base di S se e

solo se

a) B è linearmente indipendente

b) B U {x} è linearmente dipendente per ogni x € S – B n

Un insieme B = { b ,…..,b } è una base di un insieme S di R se e

1 j

solo se ogni vettore x € S è esprimibile univocamente come

combinazione lineare dei vettori b ,…..,b di B

1 j

LEZ 5

17. Risolvere con il metodo Guass-Jordan il seguente

sistema di equazioni lineari

INCOMPATIBILE rank(A) diverso rank(A,b)

18. Risolvere con il metodo Guass-Jordan il seguente

sistema di equazioni lineari

Quando ci troviamo di fronte ad un SISTEMA nel quale il numero

delle equazioni è inferiore rispetto al numero delle incognite

normalmente il sistema è indeterminato dato che ammette infinite

soluzioni. Quindi è irrisolvibile.

19. Risolvere con il metodo per sostituzione il seguente

sistema di equazioni lineari INCOMPATIBILE rank(A) diverso

rank(A,b)

20. Risolvere con il metodo per sostituzione il seguente

sistema di equazioni lineari

Quando ci troviamo di fronte ad un SISTEMA nel quale il numero

delle equazioni è inferiore rispetto al numero delle incognite

normalmente il sistema è indeterminato dato che ammette infinite

soluzioni. Quindi è irrisolvibile.

LEZ 07

15. Dimostrare che un problema di ottimizzazione può

essere sempre scritto nella sua forma generale

Un problema di ottimizzazione può essere sempre scritto nella sua

n

forma generale max(x sotto){f(x): x € R : g (x) <= 0,i = 1,…..,m}

i

E’ possibile il simbolo x sotto l’operatore max.

Dim.

1. Se il problema è di minimizzazione, possiamo infatti usare il

risultato di equivalenza tra problemi di minimizzazione e

massimizzazione min(x sotto) f(x) = -max(x sotto) – f(x)

2. Se abbiamo un vincolo di maggiore o uguale g(x) >= 0,

possiamo riscrivere il vincolo come vincolo di minore o uguale

–g(x) <= 0

3. Se abbiamo un vincolo di uguaglianza h(x) = 0, possiamo

riscrivere il vincolo come due vincoli separati h(x) <= 0 e h(x)

>= 0

16. Definire la proprietà di equivalenza tra problemi di PL e

fornire almeno un esempio di due problemi di PL equivalenti

Due problemi (P ) e (P ) di PL, con regioni ammissibili X e X

1 2 1 2

rispettivamente si definiscono equivalenti se

- sono entrambi inammissibili

- sono entrambi illimitati

- ammetto entrambi soluzioni ottime finite ed esistono due

trasformazioni f: X -> X

1 2

g: X -> X

2 1

tale che

per ogni soluzione ottima x di P il vettore f(x ) è soluzione ottime

1 1 1

di P

2

per ogni soluzione ottima x di P il vettore f(x ) è soluzione ottima

2 2 2

di P

1

(P ) min5x – 2x (P ) min5x – 2x

2 1 2 1 1

x + 2x <=8 2x + 4x <= 16

1 2 1 2

3x – 3x <= 12 x – x <= 4

1 2 1 2

x ,x >= 0 x ,x >= 0

1 2 1 2

17. Scrivere la forma generale di un problema di PL e

dimostrare come qualsiasi problema di PL si possa ridurre

nella forma generale

Un problema di programmazione lineare può essere sempre scritto

nella sua forma generale T

min c x

s.t. Ax>=b

x=>0

DIM T

1. Se il problema di PL è un problema di massimizzazione max c x

T

 -min(-c) x

2. Se il problema di PL ha vincoli di disuguaglianza con minore o

uguale, allora Ax<=b -AX >= -b



3. Se il problema di PL ha vincoli di uguaglianza, allora Ax = b 

Ax <= b and –Ax <= -b

4. Se il problema di PL ha una variabile non positiva, allora x<= 0

-x>=0



5. Se il problema di PL ha una variabile non vincolata, quindi non

vincolata in segno, allora possiamo definire due variabili y e z

vincolate in segno e porre x € R (sistema){ x=y-z (a



capo)y>=0 (a capo)z>=0

18. Dare la definizione di problema di PL inammissibile e di

problema di PL illimitato

Un problema di PL può essere inammissibile, in particolare se

l’insieme delle soluzioni ammissibili P è vuoto, il problema di PL si

dice inammissibile, in tal caso:

n

P = {x € R : Ax >= b,x>=0 }=Ø(insieme vuoto)

n

Un problema di PL può essere illimitato inferiormente

[superiormente] se di minimizzazione [massimizzazione] In

particolare, in riferimento a un problema di PL in forma canonica, se

comunque scelto un valore M esiste una soluzione ammissibile x € P

t.c. T

c x<M

il problema di PL si dice illimitato inferiormente

19. Scrivere la forma standard di un problema di PL e

dimostrare come qualsiasi problema di PL si possa ridurre

nella forma standard

Nello studio dei problemi di PL un’altra forma è molto utile è la

cosiddetta forma standard T

min c x

s.t. Ax = b

x >= 0

Ogni problema di PL può essere trasformato in un problema

equivalente in forma standard

DIM. T

1. Se il problema di PL è un problema di massimizzazione maxc x

T

-min(-c) x



2. Se il problema di PL ha m vincoli di disuguaglianza con minore

o uguale, allora possiamo introdurre m variabili non negative

u>=0 t.c. Ax <= b Ax + l u = b,u>=0

 m

Le variabili y vengono dette variabili di slack

3. Se il problema di PL ha m vincoli di disuguaglianza con

maggiore o uguale, allora possiamo introdurre m variabili non

negative v>=0 t.c.

Ax >= b Ax – l v = b,v>=0

 m

Le variabili y vengono dette variabili di surplus

4. Se il problema di PL ha una variabile non positiva, allora

X<=0 -x>=0



5. Se il problema di PL ha una variabile non vincolata in segno,

allora possiamo definire due variabili u e v vincolate in segno o

porre

x € R x=u-v (a capo)u>=0 (a capo)v>=0

(sistema){

20. Dire se i seguenti problemi di PL siano equivalenti o

meno motivando la risposta

Due problemi con la stessa regione ammissibile (�1=�2) e con

funzione obiettivo cambiata di segno (�1=−�2), se sono di

massimizzazione e di minimizzazione, sono equivalenti

21. Dire se i seguenti problemi di PL siano equivalenti o

meno motivando la risposta

Due problemi con la stessa regione ammissibile (�1=�2) e con

funzione obiettivo cambiata di segno (�1=−�2) sono equivalenti

22. Dato un problema di Programmazione Lineare nella

forma generale

mostrare come si possa trasformare in un problema in

forma standard

Un problema di Programmazione Lineare può essere sempre scritto

nella sua forma standard

�

min � �

�.�. �=�

�≥0 �

Se il problema di PL è un problema di massimizzazione max � � ⇔

�

−min(−�) �

Se il problema di PL ha � vincoli di disuguaglianza con minore o

uguale, allora possiamo introdurre � variabili non negative �≥0 tali

che

�≤ � ⇔ �

+ � = �, � ≥ 0



Le variabili � vengono dette variabili di slack

Se il problema di PL ha�� vincoli di disuguaglianza con maggiore o

uguale, allora possiamo introdurre � variabili non negative �≥0 tali

che

�≥ � ⇔ �

− � = �,

� ≥ 0



Le variabili � vengono dette variabili di surplus

Se il problema di PL ha una variabile non positiva, allora

�≤0 ⇔ −�≥0

Se il problema di PL ha una variabile non vincolata in segno, allora

possiamo definire due variabili � e � vincolate in segno e porre

� ∈ℝ ⇔ �=�−� �≥0 �≥0

LEZ 08

10. Dare la definizione di poliedro e dimostrare che è un

insieme convesso

Risposta: considerato un problema di Programmazione lineare in

forma generale T

Min c x

s.t. Ax ≥ b

x ≥ 0

la regione ammissibile n

P = {x € R : Ax ≥ b, x ≥ 0 }

n

rappresenta geometricamente l’intersezione di m semispazi chiusi

n

di R .

P si definisce poliedro in quanto intersezione di un numero finito (m)

di semispazi chiusi

P = S ∩ S ∩ ... ∩ S ∩ { x ≥ 0 }

1 2 m n

Ciascuno degli m semispazi chiusi S è un insieme convesso.

i

Pertanto un poliedro P è un insieme convesso in quanto intersezione

di insiemi convessi.

11. Dimostrare che un iperpiano è un insieme convesso

n n

Risposta: Sia a € R un vettore di R e b € R un numero reale.

Consideriamo l’iperpiano n T

H = {x € R : a x = b}

L’iperpiano H è l’intersezione di due semispazi chiusi definiti dalle

disequazioni T T

a x ≥ b e a x <= b

Dal momento che l’intersezione di un numero finito di insiemi

>= <=

convessi è un insieme convesso, H = S ∩ S è convesso.

12. Dimostrare che un semispazio chiuso è un insieme

convesso n n

Risposta: Sia a € R un vettore di R e b € R un numero reale.

Consideriamo il semispazio chiuso

>= n T

S = { x € R : a x >= b}

<=

Analoga dimostrazione per il caso S >=

Vogliamo dimostrare che per ogni coppia di vettori u, v € S e ogni

valore alfa € [0,1] >=

alfa u + (1 – alfa) v € S

>=

u, v € S implica che

T T

a u >= b e a v >= b

si noti che per ogni alfa € [0,1]

T T

alfa a u >= alfa b e alfa a v >= alfa b

Sia w = alfa u + (1 – alfa)v . Dal momento che u, v € S>= per ogni

alfa € [0,1] possiamo scrivere

T T T T

a W = a (alfa u + (1 – alfa)v) = alfa a u + (1 – alfa)a v = ≥ alfa b

+ (1 – alfa)b = b. >= >=

Quindi w = alfa u + (1 – alfa)v € S e possiamo concludere che S

è un insieme convesso.

13. Dare la definizione di direzione di un poliedro

n n

Risposta: Un vettore y € R si dice direzione di un poliedro P ⊆ R

se e solo se ogni vettore x € P l’insieme

n

{z € R : z = x + alfa y, alfa >= 0}

è contenuto nel poliedro P

n

{z € R : z = x + alfa y, alfa