Esami

5/26/2018 Esami

1/24

SI RICORDA CHE LE SOLUZIONI NON

COSTITUISCONO L'ESERCIZIARIO DI

RIFERIMENTO DEL CORSO IN QUANTO

MATERIALE REDATTO NON AI FINI DI

UNA PUBBLICAZIONE. GLI ESERCIZI

DI PREPARAZIONE AL CORSO

RIMANGONO SEMPRE E COMUNQUE GLI

ESERCIZI PROPOSTI NEI TESTI

CONSIGLIATI NEL CORSO.LESOLUZIONI SONO FORNITE SOLO PER

DARE AGLI STUDENTI UN

ORIENTAMENTO GENERALE SU COME

IMPOSTARE LA SOLUZIONE DEL

COMPITO.

5/26/2018 Esami

2/24

Appello del 11 Dicembre 2008

Domani verr pubblicato un avviso con la data della verbalizzazione.

Gli esercizi hanno attribuito tutti il medesimo punteggio.

Esercizio 1 (Formulazione)

Si consideri il problema di dover ricavare delle metrature di stoffa da alcuni rotoli di lunghezzaprefissata. In particolare necessario tagliare degli spezzoni di 30,38,42,48,49,51,51,57 metri apartire da rotoli di lunghezza pari a 100, 120, 150, 180. Si desidera determinare da quali rotoliprelevare i diversi spezzoni, con lobiettivo di minimizzare il massimo sfrido ( per sfrido si intendela rimanenza: se sul primo rotolo si tagliano i primi due spezzoni lo sfrido 100-30-38=32 metri).Formulare un modello di programmazione lineare intera adatto indicando esplicitamente variabili,vincoli, parametric ed obiettivo.

SOLUZIONE

Xij= variabile booleana pari a 1 se lo spezzone i (i=1,..,8) tagliato dal rotolo j (j=1,..,4)Ymax= Massimo sfrido

Min ymaxs.v.

Lj" x

ij

i=1

8

# $ ymax j=1,..,4

xij

j=

1

4

# =1 i =1,..,8

x ij% 0,1{ }

ymax$ 0

Esercizio 2 (Programmazione lineare)

Max x1+x2s.v.-4x1+5x2!5

6x1+5x2!30x2!3x1,x2"0

1. Disegnare la regione ammissibile e determinare per via grafica (con il metodo del gradiente)la soluzione ottima. Individuare una sequenza di soluzioni di base che il simplesso avrebbevisitato.

2. Etichettare i vertici del politopo con lettere A,B,C, partendo dallorigine e procedendo insenso orario. Mediante semplici considerazioni stabilire, per ciascun vertice del politopo,quali variabili appartengono alla base nella soluzione di base ammissibile corrispondente.

3. Per ogni soluzione di base indicare per ogni variabile il segno dei coefficienti della riga 0del tableau corrispondente.

SOLUZIONE

5/26/2018 Esami

3/24

La regione ammissibile per motivi grafici non viene riportata. Verr qui di seguito caratterizzatacon i suoi 5 vertici ammissibili

etichetta X_1 X_2 VALOREF.O.

A 0 0 0B 0 1 1C 2,5 3 5,5D 5 0 5

La soluzione ottima nel punto C. Il metodo del simplesso ha come soluzione ammissibile di basela soluzione corrispondente al vertice A. Una possibile sequenza sarebbe stata A,D,C scegliendo ilcoefficiente di costo ridotto negativo pi piccolo ( nella convenzione di aver convertito la funzioneobiettivo in forma di minimo).Per caratterizzare le soluzioni di base necessario portare il sistema dei vincoli in forma diuguaglianza. Ci comporter lintroduzione di 3 variabili di slack: x3, per il primo vincolo;x4, per il secondo vincolo; x5, per il terzo vincolo. Il numero di soluzioni di base ammissibiliassociate al problema pari a 6. Infatti il vertice C, come si pu vedere dal grafico, individuatodallintersezione di tutti e tre i vincoli pertanto ad esso corrisponderanno 3 soluzioni di baseammissibili. Le soluzioni di base sono caratterizzate nella seguente tabella.

BFS Vertice X_1 X_2 X_3 X_4 X_5S1 A FB FB B B BS2 B FB B FB B BS3 C B B B FB FB

S4 C B B FB B FBS5 C B B FB FB BS6 D B FB B FB B

Ricordiamo che il segno dei coefficienti nella riga 0 del tableau sono nulli in corrispondenza dellevariabili in base mentre il segno dei coefficienti delle variabili fuori base indica per ognuna di esseil segno della variazione della funzione obiettivo, qualora la relativa variabile dovesse entrare in

base:un segno negativo indica un decremento della funzione obiettivo, un segno positiva indica unincremento, valore nullo indica che non ci sar variazione. Nellipotesi che il simplesso siaapplicato al problema riportato in forma standard in cui la funzione obiettivo in forma di minimo

il segno dei coefficienti il seguente. In corrispondenza delle 3 soluzioni di base degeneri (S3-S4-S5) il segno dei coefficienti delle variabili fuori base indeterminato. Si consideri il genericotableau del simplesso corrispondente ad una delle soluzioni di base degeneri. Nella colonna deitermini noti ci sar un valore nullo e supponiamo che esso sia nella riga i. Sia aijil coefficiente nellamatrice nel tableau del simplesso corrispondente alla variabile fuori base j e alla riga i-esima in cuiil termine noto nullo. Se aij0, il coefficiente potrebbe essere negativo, positivo nullo.BFS Vertice X_1 X_2 X_3 X_4 X_5

S1 A - - 0 0 0S2 B - 0 + 0 0S3 C 0 0 0 +,-,0 +,-,0S4 C 0 0 +,-,0 0 +,-,0

5/26/2018 Esami

4/24

S5 C 0 0 +,-,0 +,-,0 0S6 D 0 - 0 + 0

Esercizio 3 (Programmazione Lineare Intera)

Sia dato il seguente problema (attenzione solo la variabile x2pu assumere valori interi) Risolvere ilproblema con lalgoritmo del Branch and Bound.

Max z

z = 20x1 + 15x2 + x3 +3x4 +2x5

s.v.

24x1 + 6x2 + 2x3 + 2x4 + 1.5x5 ! 10

x1, x2, x3, x4, x5, " 0 interi

X4, ! 1

Si valuti lalbero decisionale finale del Branch and Bound: il numero di iterazioni del branch and

bound ottenuto il minimo possibile ? Giustificare la rispostaSOLUZIONEE possibile risolvere questo problema come un pb di knapsack, moltiplicando il vincolo per 10 inmodo da avere tutti i coefficienti interi..Valutando il valore specifico delle variabili ( oggetti) otteniamo il seguente ordinamento e quindire-indicizzazione delle variabili decisionaliX1=y4X2=y1X3=y5X4=y2

X5=y3

Introducendo la variabile slack y6 in corrispondenza del vincolo il problema pu essere riformulatocome segue.

Max Z

Z = 15y1 + 3y2 + 2y3 +20y4 +y5

s.v.

60y1 + 20y2 + 15y3 + 240y4 + 20y5 +y6 =100

y1, y2, y3, y4, y5, y6 " 0 interi

Y2 ! 1

Saturando al massimo il sacco con loggetto pi prezioso, il rilassato continuo ha come soluzione[10/6,0,0,0,0,0]. Arrotondando per difetto il valore di y1si otiene il seguente primo incombente[1,0,0,0,0,40] zI=15. Lalbero decisionale del Branch and Bound il seguente con soluzione ottima

pari a Z=20 con [1,1,1,0,0,5].Nellalgoritmo del branch and bound il numero di iterazioni funzione delle scelte effettuate inmerito a: (scelta 1)su quale variabile frazionaria effettuare il branching; (scelta 2) lordine con cui isottoproblemi sono estratti dalla lista. noto che non esiste una regola di scelta 1 e 2 ottima ovveroche garantisca un numero minimo di iterazioni del branch and bound. Differenti scelte 1 e 2definiscono una traiettoria di esplorazione della regione ammissibile differente e quindi un numero

di iterazioni differente.Il minimo numero di iterazioni di Branch and bound nel problema in oggetto pari a 7 per iseguenti due motivi:

5/26/2018 Esami

5/24

1. ogni iterazione ha prodotto nella soluzione del rilassato al pi una variabile frazionariarendendo univoco il branching ovvero la scelta 1

2. Se si selezionano in sequenza P0, P3,P5,P7 si ottiene la soluzione ottima con Z=20. Aquesto punto i nodi rimasti sono o inammissibili o con un valore del rilassato strettamenteinferiore a 21.

ITERAZIONI STATO DELLA LISTA1. L={P0}. Estrai P0 e risolvi il rilassato: soluzione frazionaria, effettuo branching su y1;genero P1 e P2 e li inserisco nella lista.

2. L={P1,P2}. Estrai P2 e risolvi il rilassato: INAMMISSIBILE. Chiudo il nodo3. L={P1}. Estrai P1, risolvi il rilassato: soluzione frazionaria, effettuo Branching su y3;

genero P3 e P4 e li inserisco nella lista L.4. L={P3,P4}. Estrai P3 e risolvi il rilassato: soluzione frazionaria, effettuo Branching su y4;

genero P5 e P6 e li inserisco nella lista L.5. L={P4,P5,P6}. Estrai P5 e risolvi il rilassato: soluzione frazionaria, effettuo Branching su

y5; genero P7 e P8 e li inserisco nella lista L.6. L={P4,P6,P7,P8}. Estrai P7 e risolvi il rilassato: soluzione intera migliore dellincombente

aggiorno z_I, chiudi il nodo.7. L={P4,P6,P8}. Estrai P8 e risolvi il rilassato: soluzione frazionaria con valore dela funzione

obiettivo peggiore dellincombente, chiudo il nodo.8. L={P4,P6}. Estrai P6 e risolvi il rilassato: INAMMISSIBILE. Chiudo il nodo9. L={P4}. Estrai P2 e risolvi il rilassato: soluzione frazionaria con valore dela funzione

obiettivo peggiore dellincombente, chiudo il nodo.10.L={}. Lista vuota stop. Lattuale incombente la soluzione ottima

11.Esercizio 4 Programmazione Non Lineare

Si consideri il seguente problema di Programmaz. Quadratica:= ! + !

+ "

# #

2 2

1 1 2 2

1 2

1 2

max ( ) 8 4

s.a.

2

0 0

f x x x x x

x x

x x

5/26/2018 Esami

6/24

Si usino le condizioni KKT per ricavare una soluzione ottima. Si applichi il metodo modificato del simplesso al problema formulato al punto precedente.

SOLUZIONECondizioni KKT

1 j=1 8-2x_1-u_1

5/26/2018 Esami

7/24

piscine coperta. Per accedere alla piscine coperta Paolo pu decidere di acquistare alliniziodellestate, un abbonamento stagionale al costo di 75 euro. Se non acquista labbonamento, deve

pagare 5 euro ogni volt ache utilizza la piscine coperta. Lanalisi della serie storica degli ultimi 10anni indica che c il 70% di possibilit che lestate sia soleggiata (ovvero Paolo pu aspettarsi 5giorni piovosi nel corso della stagione estiva); altrimenti lestate sar piovosa (con 30 giorni di

pioggia nel corso della stagione estiva). Prima che lestate cominci Paolo pu consultare un suo ziometereologo dilettante il quale in passato, nelle estati piovose, aveva previsto una brutta stagione incirca il 70% dei casi, mentre nelle estati soleggiate, aveva previsto una bella stagione nel 90% deicasi. Si costruisca lalbero delle decisioni che aiuta Paolo a prendere la decisione pi economica.Qual il valore dellinformazione dello zio?

SOLUZIONELe decisioni che Paolo deve prendere sono due:

Acquistare (A1) o meno (A2) labbonamento Consultare (C1) o meno (C2) lo zio metereologo

Gli stati di natura (eventi) sono di due tipi: La stagione pu essere piovosa (SP) o soleggiata (SS) La consultazione con lo zio pu dare due esiti: estate piovosa (ZP) ; estate soleggiata (ZS).

Se Paolo dovesse decidere di non consultare lo zio la sua tabella decisioni stato di natura sarebbe

SP SSA1 75 75A2 150 25Probabilit 0.3 0.7

In merito alla caratterizzazione probabilistica circa lesito della consultazione con lo zio sono notele probabilit aposteriori ovveroP(ZP|SP)=0.7P(ZS|SP)=0.3P(ZP|SS)=0.1P(ZS|SS)=0.9La probabilit che lo zio dia come esito della consultazione unestate piovosa o soleggiata ottenibile applicando il teorema della probabilit totale ovvero:P(ZP)=P(SP) P(ZP|SP)+P(SS)P(ZP|SS)=0.3*0.7+0.7*0.1=0.21+0.07=0.28P(ZS)=P(SS)P(ZS|SP)+P(SP)P(ZS|SS)=0.3*0.3+0.7*0.9=0.09+0.63=0.72

Rimangono da determinare le probabilit a priori ovvero grazie al teorema di Bayes possiamoaffermare che

P SP ZP( ) =P SP( )P Z P SP( )

P ZP( )=

0.3*0.7

0.28=0,75

P S S ZP( ) =P SS( )P ZP SS ( )

P ZP( )=

0.7*0.1

0.28=0,25

P SP ZS ( ) =P SP( )P ZS SP( )

P ZS( )=

0.3*0.3

0.72=0,125

P S S ZS ( ) =P SS( )P ZS SS ( )

P ZS( )=

0.7*0.9

0.72=0,875

5/26/2018 Esami

8/24

A QUESTO PUNTO POSSIBILE COSTRUIRE lalbero delle decisioni ed applicare la foldbackanalysis

La strategia ottima consultare lo zio. In caso lo zio dia indicazione che la stagione piovosaconviene acquistare labbonamento, in caso lo zio dia indicazione che la stagione soleggiataconviene non acquistare labbonamento. Il valore dellinfomrazione data dallo zio pari a 12,25euro.

Esercizio 6 ( Elementi di statistica)

Unazienda produce serie di lampadine decorative per lalbero di Natale. Le serie sono difettose con

probabilit 5%, indipendentemente luna dallaltra. Le lampadine sono vendute in confezioni da 5serie, con garanzia di rimborso in caso vi sia pi di una serie difettosa. Che percentuale delleconfezioni viene ritornata? Se si comprano 3 confezioni, qual la probabilit di ritornarneesattamente una?SOLUZIONEEsperimento: aprire una confezione ed individuare un pezzo difettosoRipetuto 5 volteProbabilit di successo=0.05X= numero dei pezzi difettosi in una scatola di 5 confezioniX v.a. binomiale (n,p)=(5,0.01)Supponendo che tutti i clienti sfruttino la garanzia

( ) ( ) ( )1011 =!=!=> XPXPXP

5/26/2018 Esami

9/24

P X >1( ) =1" 5

0

#

$%

&

'() 0,05

0 ) 0,955 " 5

1

#

$%

&

'() 0,05

1 ) 0,954 = 0,0226 = 2,26%

Ogni scatola indipendentemente dalle altre viene resa con probabilit 2,26%A lungo andare sar reso il 2,26% delle confezioniAcquistando 3 scatole il numero di quelle che verranno rese una v.a. Y binomiale di parametri(3,0.0226)

P Y =1( ) =3

1

"

#$

%

&'( 0,0226 ( 0,9774

2 )0,065

5/26/2018 Esami

10/24

DA CONSEGNARE AL DOCENTE

COGNOME___________________________ NOME________________________________

ESAME_____________ NUMERO CREDITI_______________________________________

CORSO DI LAUREA_______________________________________________________

Qual il compito che devi svolgere

EserciziCorso di appartenenza Tempo

1 2 3 4 5 6

Ricerca Operativa (5 crediti) 2 h X X X X

Ricerca Operativa I (6 crediti) 3 h X X X X X

Ricerca Operativa ed Elementi di Statistica (6 crediti) 3 h X X X X X X

5/26/2018 Esami

11/24

Appello del 12 Gennaio 2009


Agli esercizi verr attribuito il medesimo punteggio.


Uno studente di ricerca operativa vorrebbe attrezzarsi per portare con s allesame scritto alcunifoglietti di appunti della dimensione totale di 95 cm2. Lesame comprende 10 diversi argomenti e lostudente ha gi preparato per ciascuno di essi delle note riassuntive, che non possono essereulteriormente ridotte senza perdere di significato. La tabella seguente riporta lo spazio richiesto perogni argomento per tali note e il suo peso relativo nellambito dellesame.

Argomenti Spazio richiesto in cm2 Peso

1 10 52 18 103 22 154 16 105 14 106 20 57 32 208 12 59 12 1510 10 5

Lo studente poco preparato sulle note 2,3,7,8 e 9 e vorrebbe pertanto portare allesame le noteriassuntive di almeno 3 di essi. Inoltre ritiene poco utile avere contemporaneamente nei foglietti siale note relative allargomento 9, che quelle relative allargomento 10. Infine ha valutato che

risultano inutili le note dellargomento 5 a meno che non vengano incluse nel foglio anche le noterelative allargomento 4. Si formuli il modello di PL che selezioni linsieme di argomenti piconveniente per lo studente.SOLUZIONEXi= largomento i-esimo incluso nei fogliettini si (xi=1) no (xi=0) i=1,..,10vi= peso dellargometno i nella valutazionesi = spazio richiesto dallargomento i

Max vix

i

i=1

10

"

s.v.

six

i

i=1

10

" # 95

x2+ x

3+ x

7+ x

8+ x

9"3

x9+ x

10"1

x5" x

4

xi" 0,1{ } i =1,..,5


Risolvere il seguente problema sia graficamente che mediante lalgoritmo del simplesso.Max 3x1+5x2s.v.7x1-3x2

5/26/2018 Esami

12/24

x1, x2>=0Affinch lesercizio venga valutato positivamente, il candidato illustri in maniera chiara e breve leoperazioni effettuate sul tableau in termini di scelta della variabile entrante ed uscente.

I vertici ammissibili sono (0,0),(0,1),(5/4,)/4),(2/7,0). Le iterazioni del simplesso sono 3 e

producono i seguenti tableau

0 -3 -5 0 0 02 7 -3 1 0 01 -1 1 0 1 03 1 -3 0 0 1

6/7 0 -44/7 3/7 0 02/7 1 -3/7 1/7 0 09/7 0 4/7 1/7 1 019/7 0 -18/7 -1/7 0 1

15 0 0 2 11 05/4 1 0 ! " 09/4 0 1 ! 7/4 017/2 0 0 1/2 9/2 1


Si consideri il seguente problema di PLI

Min 2x1+ x2s.v.5x1+2x2>=82x1+2x2>=5-x1+2x2>=-1x1,x2>=0 interie lo si risolva utilizzando il Branch and Bound con le seguenti regole di esplorazione:1. si esplori per primo il problema con il lower bound minimo;2. a parit di lower bound si esplori per primo il problema definito dal vincolo di branching dimaggiore uguale.

Affinch lesercizio venga valutato positivamente, il candidato riporti lalbero del Branch andbound e per ogni iterazione indichi qual lo stato della lista dei sottoproblemi, il risultato delrilassato continuo e le considerazioni che ne derivano, in che maniera viene aggiornata la lista deisottoproblemi.

Esercizio 4 Programmazione Non Lineare

Assegnato un generico problema di ottimizzazione vincolata,

5/26/2018 Esami

13/24

( )

( )!!"

!!

#

$

%

=(

0,..,1

..

max

ii

xmibxg

vs

xf

il candidato illustri perch possibile certificare lottimalit (globale o locale) di un punto x chesoddisfi le condizioni KKT.SOLUZIONE Fare riferimento ai luci a lezione.Esercizio 5 (Analisi Decisionale)

Unimpresa specializzata nel recupero dei relitti marini deve prendere una decisione in merito alproseguimento di un progetto intrapreso in una certa area nella quale si trova un relitto. Il progetto ad alto rischio, dal momento che si reputa pari al 0.1 la probabilit che si riesca a recuperare il

relitto. Qualora si prosegua il progetto e il relitto venga recuperato, si stima che il relativo guadagnosia pari a 10 milioni di euro. Viceversa, se si prosegue il progetto e il relitto non viene recuperato, larelativa perdita sar di 1 milione di euro. Infine, nel caso in cui si opti per labbandono del progettoe il concorrente non concluda positivamente il recupero, limpresa consegue un guadagno di 0,75milioni di euro.

Costruire la matrice dei guadagno dei differenti stati di natura. Sulla base del criterio di Bayes, indicare qual la scelta ottimale Si supponga di potersi avvalere della consulenza di un esperto circa la possibilit di

successo del recupero. Sulla base delle esperienze passate, la probabilit che lesperto diavalutazione affermativa circa la fattibilit del recupero dato che il relitto viene recuperato

pari a 80%; la probabilit che dia valutazione affermativa dato che il relitto non viene

recuperato 13%. Si costruisca un albero di decisione che rappresenti la nuova situazionedecisionale, indicando la strategia ottimale per limpresa. Se il costo dellesperto pari a 0,1 milioni di euro, pu risultare conveniente avvalersi della

sua consulenza? Giustificare la risposta.SOLUZIONE

Il problema caratterizzato da due alternative decisionali: A1: abbandono il progetto A2: effettua il progetto

Gli stati di natura sono 2: F: fallimento delliniziativa, il relitto non viene recuperato. Ci avviene con probabilit pari

a 0,9. S: successo delliniziativa, il relitto viene recuperato. Ci avviene con probabilit pari a 0,1.La tabella dei guadagni/probabilit dei differenti stati di natura.

S FA1 0 0,75 0,675A2 +10 -1 0,1Prob 0,1 0,9

Applicando il criterio di Bayes si ha che lalternativa migliore abbandonare il progetto.Costruiamo lalbero decisionale per valutare se chiedere la consulenza e se abbandonare il

progetto o effettuarlo.

5/26/2018 Esami

14/24

In particolare indichiamo con: D1: chiedere la consulenza; D2: non chiedere la consulenza; CS: esito della consulenza favorevole a effettuare il progetto; CN: : esito della consulenza favorevole allabbandono del progetto

Secondo quanto riportato nella traccia si ha:P(CS|S)=0,8P(CS|F)=0,13

P(CN|S)=0,2P(CN|F)=0,87

Applicando il teorema della probabilit totale e di Bayes si ha che:P(CS)=0,8*0,1+0,13*0,9=0,197P(CN)=1-0,197=0,803

P(S|CS)=P(CS|S)P(S)/P(CS)=0,8*0,1/0,197=0,406P(F|CS)= P(CS|F)P(F)/P(CS)=0,13*0,9/0,197=0,593P(S|CN)= P(CN|S)P(S)/P(CN)=0,2*0,1/0,803=0,025P(F|CN)= P(CN|F)P(F)/P(CN)=0,87*0,9/0,803=0,975

5/26/2018 Esami

15/24

La strategia ottima chiedere la consulenza. Se lesperto da parere favorevole si deve effettuareil progetto, si abbandona il progetto se lesperto da indicazioni negative.Il valore della consulenza 0,595; pertanto 0,1 milioni di euro un prezzo congruo.


La probabilit che una persona di 25 anni giunga in vita a 75 anni del 57% per una donna e del52% per un uomo. Due venticinquenni si sposano. Qual la probabilit che giunga in vita allet di75 anni:

Uno solo dei due; Almeno uno dei due; Nessuno dei due.Affinch lesercizio venga valutato positivamente il candidato deve motivare con chiarezza larisposta data.

5/26/2018 Esami

16/24

Esercizio 1

Il responsabile del personale di unazienda manifatturiera ha il compito di organizzare i turni dilavoro ad una catena di montaggio a ciclo continuo. Sono previste 6 fasce orarie per ognuna delle

quali richiesto un minimo numero di unit lavorative come riportato in tabella.

Fascia

Oraria

Numero

lavoratori

00.00-04.00 604.00-08.00 908.00-12.00 1412.00-16.00 916.00-20.00 1120.00-24.00 8

Inoltre, a seguito accordi sindacali, sono stati individuati 6 turni di lavoro ciascuno dei quali di 8 orelavorative:

Turno Orario

1 20.00-04.002 00.00-08.003 04.00-12.004 08.00-16.005 12.00-20.006 16.00-24.00

Si vuole determinare il numero di unit lavorative da assegnare ad ogni turno in modo tale daimpiegare la minor forza lavoro complessiva.

SOLUZIONEIndichiamo con

i=1,..,,6 lindice delle fasce orarie; piil numero di persone per ogni fascia oraria; j=1,..,6 lindice dei turni di lavoro; aijse il turno j copre la fascia oraria i xjil numero di persone allallocate al turno j.

Min x jj=1

6

"

s.v.

aijx jj=1

6

" # pi i =,1..,6

x j# 0 int j=1,..,6

Esercizio 2

Risolvere con il metodo grafico il seguente problema di PL:max ZZ=3x1+4x2

s.v.

5/26/2018 Esami

17/24

- 3x1+ 4x2!12x1+ x2!11

x1+ 2 x2!16x1,x2"0

Si riduca in forma standard il problema su enunciato. Rispetto a tale forma standard si indichi qualisono le soluzioni di base ammissibili. Si indichi in ognuna di tali soluzioni di base quale sono levariabili in base e quali quelle fuori base. Si individui inoltre la sequenza di soluzioni di base che ilmetodo del simplesso visiterebbe se fosse applicato per risolvere il problema.

SOLUZIONEI vertici ammissibili della regione ammissibile sono:A(0,0) z=0B(0,3) z=12C(4,6) z=36D(6,5) z=38E(11,0) z=33

La forma standard

max ZZ=3x1+4x2

s.v.- 3x1+ 4x2+ x3=12

x1+ x2+ x4= 11x1+ 2 x2+ x5= 16

x1,x2, x3,x4, x5"0

Le soluzione di base ammissibili sono

(x1,x2, x3,x4, x5)=(0,0,12,11,16)= (FB,FB,B,B,B)(x1,x2, x3,x4, x5)=(0,3,0,8,8) =(FB,B,FB,B,B)(x1,x2, x3,x4, x5)=(4,6,0,1,0) =(B,B,FB,B,FB)(x1,x2, x3,x4, x5)=(6,5,10,0,0) =(B,B,B,FB,FB)(x1,x2, x3,x4, x5)=(11,0,45,0,5) =(B,FB,B,FB,B)

A->B->C->D

SOLUZIONEEsercizio 3 (6 punti)

Sia dato il seguente problema di PL:

( )( )( )

0

4)5/2()5/1(

110/7)10/1(

610/3)10/1(

365/2)5/1(

max

54321

531

543

532

53

!

=+"

="+

=++

++"=

x,x,x,x,x

xxx

xxx

xxx

xxz

z

Si individuino:1. una soluzione di base ammissibile con valore di funzione obiettivo pari a 36.

5/26/2018 Esami

18/24

2. una soluzione di base ammissibile con valore di funzione obiettivo migliore di (36)3. una soluzione di base ammissibile con valore di funzione obiettivo peggiore di (36)4. una soluzione di base inammissibile con valore di funzione obiettivo migliore di 36

SOLUZIONE

1. (x1, x2, x3, x4, x5) =(4,6,0,1,0)2. (x1, x2, x3, x4, x5) =(0,3,0,8,10)3. (x1, x2, x3, x4, x5) =(6,5,10,0,0)4. (x1, x2, x3, x4, x5) =(-4,0,0,15,20)

Esercizio 4 (6 punti)

Si enunci lalgoritmo del Branch and Bound, evidenziandone i criteri di arresto. Si consideri ilproblema dellesercizio 2, si aggiungano i vincoli dinterezza e lo si risolva applicando il metododel Branch and Bound ed utilizzando il metodo di risoluzione grafica per risolvere i sottoproblemi.

DA CONSEGNARE AL DOCENTE

COGNOME___________________________ NOME________________________________

ESAME_____________ NUMERO CREDITI_______________________________________

CORSO DI LAUREA_______________________________________________________

5/26/2018 Esami

19/24

Appello del 3 Febbraio 2009 . Tempo a disposizione 2 ore


Agli esercizi verr attribuito il medesimo punteggio.


Avete deciso di organizzare una cena a casa vostra Poich siete troppo impegnati a studiare perl'esame di Ricerca Operativa, avete pensato bene di far cucinare i vostri amici, che d'altra parte sonoben lieti di aiutarvi. Dopo aver lungamente meditato sulle capacit culinarie dei vostri amici, sietegiunti a stilare la seguente tabella, dove la cifra indica il vostro giudizio sulla corrispondente

pietanza preparata dal vostro amico/a.

Il problema quello di decidere se e cosa far preparare a ognuno, considerando che la vostra cenaconsister di una pietanza di ciascun tipo (ossia un antipasto, un primo, un secondo etc.) e che perdiscrezione non intendete chiedere a nessuno di preparare pi di una pietanza.Formulare in terminidi programmazione lineare a numeri interi il problema di massimizzare la qualit della vostra cena.SOLUZIONESOLUZIONE

Sia i lindice assegnato al set delle pietanze (i=1,..,5)

Sia j lindice assegnato al set di amici (j=1,..,7)

Sia Xij una variabile binaria pari a 1 quando la pietanza i assegnata allamico/a jSi indichi con cijil vostro giudizio assegnato allamico/a j nella preparazione della pietanza i

Il problema pu essere cos formulato

max cijx

ij

j=1

7

"i=1

5

"

s.v.

xij

j=1

7

" #1 i =1,..,5 (I1)

xij

i=1

5

" =1 j=1,..,7 (I2)

xij$ 0,1{ } i =1,..,5 j=1,..,7

dove il primo vincolo esprime la condizione per cui ad una persona non deve essere assegnata pi diuna pietanza, mentre il secondo vincolo indica che tutte le pietanze devono essere preparate.Esercizio 2 (Programmazione lineare)

Assegnato un problema di Programmazione Lineare (P) e individuata il tableau del simplesso finale, per ognuna delle seguenti affermazioni dire se vera o falsa. I singoli punti sono valutatipositivamente se il candidato fornisce la motivazione della riasposta.

5/26/2018 Esami

20/24

1. Se il coefficiente di costo ridotto di una variabile fuori base nullo, allora la soluzione dibase individuata degenere. FALSO

2. Una soluzione di base ammissibile adiacente e migliore di quella corrente si ottiene facendoentrare in base una variabile con coefficiente di costo ridotto non nullo e facendo usciredalla base una qualsiasi delle variabili attualmente in base. FALSO

3. Una soluzione di base ammissibile adiacente con valore di funzione obiettivo uguale aquella corrente si ottiene solo se la soluzione di base corrente degenere. FALSO4. Il test del minimo rapporto si effettua selezionando tutti i coefficienti della matrice dei

vincoli corrispondenti alla colonna della variabile uscente dalla base. FALSO


Si risolva il seguente problema di PLI

Il problema Proposto un problema di Knapsack. Ordinando le variabili in ordine decrescenterispetto al loro valore specifico che porta al seguente ordinamento delle variabiliX1=y1X4=y2X3=y3X2=y4

max z = 2y1+ 6y

2+4y

3+3y

4

s.v.

y1+ 6y

2+ 5y

3+4y

4" 9

yi# 0,1{ }

(P0)

Il problema del Knackpasack ha la caratteristica per cui il rilassato continuo dei nodi del Branchand Bound posso essere risolti in tempo polinomiale secondo quanto segue.

Si consideri il problema (P0R) definito come rilassato continuo del problema (P0). Si indichi conCR la capacit residua del sacco ad ogni fixing delle variabiliY1=1 CR=8Y2=1 CR=2

Y3=2/5 CR=0Y4=0

Abbiamo ottenuto una soluzione frazionaria ed effettuiamo branching sulla variabili y3. Il nodoradice avr un LB = 9,75. E inoltre possibile individuare una prima soluzione ammissibileattraverso un arrotondamento per difetto di Y2. In questo modo Z_I=8 e la soluzione ammissibilecorrispondente sar (1,1,0,0).

Qui di seguito riportato lalbero del branch and bound mentre nella tabella per ogni sottoproblema sono riportati LB, se e quale criterio di fathoming si verificato, la soluzione intera ofrazionaria corrispondente.

UB soluzione FathomedP0r 9.75 (1,1,2/5,0) No, branching su y_3

5/26/2018 Esami

21/24

P1R 9,5 (1,1,0,1/2) No, branching su y_4P3R 8 (1,1,0,0) Si, soluzione intera. La

soluzione non miglioredellincombente che

quindi non aggiornato

P4R 9 (1,2/3,0,1) No, branching su y_2P5R 6 (1,0,0,1) Si, soluzione intera

peggioredellincombnte chequindi non aggiornato

P6R - - Si, problemainammissibile

P2R 9 (1,1/2,1,0) No, branching su y_2P7R - - Si, problema

inammissibileP8R 8,20 (1,0,1,3/4) Si, qualsiasi soluzione

intera avr valoreminore o uguale a 8 (icoefficineti dellafunzione obiettivosono interi). Quindinon possibile trovareuna soluzione intera

con valore maggiorestrettamente di 8 e cony_3=1 e y_2=0

5/26/2018 Esami

22/24


Si illustri in maniera chiara le motivazioni che consentono di affermare che assegnato un problemadi ottimizzazione vincolata, se una soluzione x soddisfa le condizioni KKT allora essa rappresenterun ottimo globale o locale del problema.

5/26/2018 Esami

23/24

Appello del 20 Aprile 2009


Gli esercizi hanno attribuito tutti il medesimo punteggio.


Una compagnia aerea sta valutando lacquisto di nuovi jet per passeggeri a lungo, medio e cortoraggio. Il prezzo di acquisto di 67 milioni di euro per ogni velivolo alungo raggio, 50 milioni dieuro per ogni velivolo a medio raggio e 35 milioni di euro per ogni velivolo a corto raggio. Ilconsiglio di amministrazione ha autorizzato una spesa massima di 1,5 miliardi di euro per questiacquisti. Indipendentemente da quali velivoli vengono acquistati, si vuole che questi aereoplanivengano comunque utilizzati alla capacit massima. Si stima che il profitto annuale netto (dopo aversottratto il costo relativo alla restituzione di capitale) di 4,2 milioni di euro per ogni velivolo alungo raggio, 3 milioni di euro per ogni velivolo e medio raggio e 2,3 milioni per ogni velivolo a

piccolo raggio. Si prevede per lazienda che siano disponibili un numero sufficiente di pilotiaddestrati per equipaggiare 30 nuovi aerei. Se fossero acquistati solo velivoli a corto raggio, leofficine potrebbero gestire fino a 40 aerei. Comunque ogni velivolo a medio raggio e lungo raggio

equivalgono rispettivamente ad un terzo e due terzi di un velivolo a corto raggio in termini digestione in officina. Si formuli un modello di PLI che determini il numero di velivoli di ciascun tipoda comprare per massimizzare il profitto.


Dire se ciascuna delle seguenti affermazioni vera o falsa. Le risposte verranno valutatepositivamente se e solo se le risposte verranno motivate.

a) La regola del metodo del simplesso per la scelta della variabile entrante usata perch essaconduce alla migliore BFS adiacente. FALSA: la regola per la variabile entrante effettuata

per ottenere un miglioramento rispetto alla corrente BFS della funzione obiettivo; non vi alcuna garanzia che la BFS nuova sia la migliore fra quelle adiacenti.

b) La regola del rapporto minimo del metodo del simplesso per la scelta della variabile di baseuscente usata perch un rapporto pi grande fornirebbe una soluzione di base nonammissibile. VERA: il test del rapporto minimo determina qual il massimo valore ( equindi il massimo miglioramento per la funzione obiettivo) che la variabile entrante puassumere senza violare alcun vincolo.

c) Quando il metodo del simplesso determina la successiva BFS vengono eseguite delleoperazioni algebriche elementari per eliminare ogni variabile non di base da tutte leequazioni tranne una (la suaequazione ) ed assegnare a essa un coefficiente +1 in questaequazione. FALSO: le operazioni algebriche elementari, ovvero le operazioni di pivoting,su citate sono da riferirsi alla variabili entrante in base e non fuori base.

d) In una particolare iterazione del metodo del simplesso, se pi variabili di base possonoessere scelte come variabili uscenti, allora la BFS successiva deve avere almeno unavariabile uguale a zero.VERA: infatti le successive operazioni di pivoting in corrispondenzadella seconda variabile candidata ad uscire daranno un valore nullo sul temine noto. Sia (i,j)la coppia riga (variabile uscente) e colonna (variabile entrante ) nelloperazioni di pivotingse esiste unaltra coppia (k,j) tale per cui b_k/a_kj=b_i/a_ij allora nelloperazione di

pivoting sulla riga k-esima in corrispondenza del termine noto si avr che(b_k-a_kj(b_ij/a_ij)) che chiaramente sar zero.

e) Se in uniterazione del metodo del simplesso non esiste alcuna variabile di base uscente,allora il problema non ammette soluzioni ammissibili. FALSO: in questo caso il problema illimitato

f) Se almeno una delle variabili di base ha un coefficiente nullo nella riga 0 della tabella finale,allora il problema ha soluzioni ottime multiple. FALSO: le variabili di base hanno sempre

5/26/2018 Esami

24/24

un cefficiente nullo sulla riga 0; tali discriminazioni sono fatte solo e soltanto sulle variabilifuori base.

g) Se il problema ha soluzioni ottime multiple, allora il problema deve avere regioneammissibile limitata. FALSO: la limitatezza della regione ammissibile non possibilerelazionarla allesistenza di soluzioni ottime multiple che da relazionarsi allesistenza di

uno spigolo parallelo alle curve di livello della funzione obiettivo; una regione ammissibileillimitata potrebbe avere tale spigolo.


Si enunci sottoforma di pseudo codice lalgoritmo del Branch and Bound, evidenziandone la fase diinizializzazione, la generica iterazione, i criteri di arresto e di fathoming. Inoltre dire se ciascunadelle seguenti affermazioni vera o falsa. Le risposte verranno valutate positivamente se e solo sele risposte verranno motivate.

a) Condizione sufficiente perch lalgoritmo del Branch and Bound sia caratterizzato da unasola iterazione che almeno uno dei vertici della regione ammissibile del rilassato continuo

sia a componenti intere. FALSO: condizione necessaria ma non sufficienteb) Condizione necessaria affinch un problema di PLI sia inammissibile che il rilassato

continuo sia inammissibile. FALSO: condizione sufficiente ma non necessariac) Un problema di PLI inammissibile pu avere un rilassato continuo con regione ammissbile

illimitata. VERO:in tale regione potrebbero non esserci punti a componenti intere


Si illustri in maniera chiara le motivazioni che consentono di affermare che assegnato un problemadi ottimizzazione vincolata, se una soluzione x soddisfa le condizioni KKT allora essa rappresenterun ottimo globale o locale del problema

Esercizio 5 (Analisi Decisionale)

Il proprietario di una libreria inglese deve decidere quante copie dellultimo bestseller tascabileacquistare. Ciascuna copia costa alla libreria 3 sterline e viene venduta a 7. Lesperienza passata haconsentito di raccogliere i i seguenti casi:

Domanda Occorrenza (n casi)2000 63000 184000 245000 12

Assumendo che la funzione di utilit del proprietario abbia la seguente forma:

U(M) =M+1000

100

essendo M il valore monetario, si ricavi la decisione ottima per la libreria.


Su un canale TV dalle 6 alle 9 e 30 del mattino sono trasmesse le previsioni meteo ogni 20 minuti.Se un telespettatore si sintonizza sul canale in un momento casuale con distribuzione uniforme tra le8 e le 8.30 si calcoli con che probabilit dovr aspettare di ascoltare le prossime previsioni meteo

Meno di 6 minuti Almeno 11 minuti

Esami

Documents

Transcript of Esami