Esercizi e prove d'esame svolte di Ricerca Operativa

F'

I

L

:

H

H

i-*

f*

l|,*

h-'

F

I

I

F

'-1

: ol ltol l.t

I lo

F "Federico

Università

degti Studi -

di Napoli If" Corso di Ricerca Operativa

Jng' Gest.

Prog. -

rnfr.

e (Prof. sterle c.) Prova scritta del 05/02

tztts

( nserci

zío

nJ

-a) =

si consideri -

la funzionef(x, -

y) o.zs i 0.5 + +

tox 2sy-r

v! riportatainFigura I del foglio allegat

brevemente iltustri

e si il percorso

deilLlgoritmo

sraficam,enfg punto

dal iniziale

xs(50,

3e frnoal

punto di ottimo

n) Si effettui analiticamente

1 step

dell'aigoritmo

di salit-a

ripida partire

a punto

dal iniziale rs(s1, 30).

Esercizio

n.2

siconsideri

il seguentesistemadi-vincoli:

x+y> I0 x+ y<30 )0,y

x 20

utilizzando

la figura 2 del

foglio allegato:

a) si disegni

il dominio

di ammissibilità

a) si determini

graficamente punto

il di massimo il punto

e di minimo vincolato proble

del ma e si verifichino grr

condizioni

di ottimalità;

-+) si rlisegni

il cono

delle

direzioni

ammissibili quello

e delle

direzioni

di miglioramento

in un vertice

del dominio;

si effettui

*>d) I step dell'algoritmo

a direzione

ammissibile

noto per la determinazione punto

del di minimo vincolat

un vertice

del dominio

di ammissibilità.

Esercizio

n.3

un'azienda produce

che finestre

deve

operare

il taglio di aste

della lunghez.zadi

l l metri per produrre

almeno

16 ba

1,5

metri e almeno

13 barre

B lunghe

2 metn.

Per motiyi èlossibile usare

solo gli schemi

lecnologici di taglio

ripor

(si ricordi la corispondenza

tra schqr4i

di taglio " utiliízate).-

ffi La. produzione

ha lnoltre necessità

di dett

soluzione

che utilizzi al massi*o (indi-pendentemente

SK$ dallo schema

- -'-

-barre di taglio

--e--- adotrato). vr

si vuole

'e\ determina

19

produzione

di A e B che minim:.z:zi

il numero

di utilizzate.

SI S2

A 4 2

B 2 J

*a) si formuli il modello

in programmazione

linearg desqrivendo

parametri,

variabili, vincoli funzione

e obietti,,

-b)sidisegniiIdominiodiammissibilitàdelproblemae@;

-\

.*c)siindichi,perciascunodeiverticide1dominio,la'o*ffionebasicaammissibi1eadessoi

-d) si risolva graficamente problema,

il individuando

il vertice

ottimo e calcolando

il valore

di variabili e funzio

Esercizio

n. 4

ta) si eliminino

eventuali

vincoli

ridondanti

dal modello

dell'esercizi.

n.3

si

*+b) risolva problema

il analiticamente

con I'algorilqo_fer

sirnplesso

standard

(Merodo

2 Fasi)

rilassando

i vincoli di

si

*d effettui

analiticamenfe graficamente

e l'ànalisi di stabiliià

su

un vincoloìi maggiore

o uguur,

u scelta.

n. 5

KEsercizio

risolva

$i con il metodo

del Branch

and Bound, il modello programmazione

cli lineare

dell,eserci

zio n.3 assumendr

crlme

intere

positive.

Esercizio

n.6

Si consideri

la rete in figura:

-(s) si scriva il modello di flusso single'commodity

senza

vincoli di capacità la

e tabella del simplesso

associai

figura, senza

ripofrare

le variabili artificiali.

(b) si determini prima

una soluzione

basica

ammissibile

per problema

il e ne

se calcoli

il costo.

Esercizio

n. 7

Si consideri

la rete dell'es.

6. si assumano

gli archi come

non orientati.

I valori sugli archi rappresentano

il costo

di costr

'3) Si scriva

il modello

dell'albero

minimo.

b) Si aggiunga

un vincolo che

impone

che I'arco

se 1-3 parte

fa dell'albero

minimo,

allora deve

farne (

parte

'b) anche

l,arco

Si,determini

I'albero

minimo con un algoritmo

noto.