Tutti i test autovalutativi Ricerca Operativa per ICT

RICERCA OPERATIVA

• Lo scopo della ricerca operativa e’ determinare la decisione ottima dato un problema in presenza di

risorse limitate

• La ricerca operativa trova applicazione in ambito industriale-logico-progettazione ottima

• La definizione di un problema di controllo delle scorte e’ decidere quando e quanto, durante un

processo produttivo, si devono immagazzinare prodotti in modo da rispettare le consegne

minimizzando i costi

• Nell’ambito della ricerca operativa i problemi reali sono affrontati definendone una

rappresentazione quantitativa

• Aspetto fondamentale della ricerca operativa e’ identificare un modello matematico con cui

studiare in modo sistematica il problema decisionale

• La soluzione dei problemi di Ricerca operativa e’ effettuata utilizzando algoritmi di ottimazione

• La definizione di un problema di progettazione di reti e loro gestione e’ definire i collegamenti e

dimensionare le capacita’ di una rete stradale, di telecomunicazioni, di trasmissione dei dati, in

modo di garantire il traffico tra le varie origini e destinazioni e minimizzare il costo complessivo

• La ricerca operativa e’ nata negli anni ’40 per scopi bellici

• La ricerca operativa si occupa dello sviluppo e dell’applicazione di metodi matematici per la

soluzione di problemi di decisione che si presentano in molteplici e diversi settori della vita reale

• La ricerca operativa si e’ sviluppata grazie alla disponibilita’ di strumenti automatici di calcolo

RICERCA OPERATIVA DISPENSA 2

o La costruzione degli strumenti matematici necessari per la soluzione di problemi reali avviene

attraverso le seguenti fasi:

Analisi del problema

Costruzione del modello

Analisi del modello

Soluzione numerica

Validazione del modello

o Un algoritmo e’ una procedura iterativa costruttiva da un numero finito di passi

o Un problema i programmazione lineare (PL) e’ un problema di ottimizzazione caratterizzato dalle

seguenti proprieta’:

1. Un numero finito di variabili che possono assumere valori reali

( ) = ∈

2. Una funzione obiettivo lineare, cioe’ del tipo dove c e’ il vettore dei costi

∈

(fissato) ed e’ il vettore delle variabili =

3. L’insieme ammissibile e’ definito da un insieme finito di m vincoli lineari del tipo e/o

≤ ≥ ∈ ∈

e/o dove e

o Il simplesso e’ un algoritmo di ricerca al punto massimo/minimo di una funzione lineare

o L’analisi del modello matematico prevede la deduzione per via analitica, in riferimento a

determinate classi di problemi, di alcune importanti proprieta’ quali esistenza ed unicita’ della

soluzione ottima, condizioni di ottimalita’ e stabilita’ in caso di variazioni

o La soluzione numerica si individua mediante opportuni algoritmi di calcolo la cui soluzione deve

essere verificata dal punto di vista applicativo

o Un problema di decisione e’ processo i selezione tra piu’ alternative che possono essere di

cardinalita’ finita o infinita

o L’analisi del problema consiste nell’analisi della struttura del problema per indiviuare i legami logico

funzionale e gli obiettivi

o Nel processo di costruzione del modello si descrivono in termini matematici le caratteriche

principali del problema

o La validazione del modello avviene attraverso una verifica sperimentale oppure con metodi di

simulazione

3 dispensa

• La definizione di vettore e’: si definisce vettore ad n componenti reali una n-pla(si legge ennupla)

ordinata di numeri reali

• La definizione di vettore nullo e’: si definisce vettore nullo il vettore le cui componenti sono tutte

nulle

• La definizione di combinazione lineare tra vettori e’: un vettore y e’ combinazione lineare dei

, … , = + ⋯ +

vettori ; se esistono numeri reali tali che

1,…, 1 1

• , … ,

La definizione di spazio generato dai vettori e’: Un insieme di vettori di dimensione n

1

genera l’insieme di vettori in , se ogni vettore puo’ essere rappresentato come combinazione

lineare di k vettori

• (3; −1,5)

Il risultato della moltiplicazione del vettore per lo scalare 2 e’ (6; -2,10)

• Il risultato del prodotto interno di due vettori (1; 2) e (3; 4) e’ 11

• Il risultato della somma del vettore (4; 5; 7) e (-1; 3; 4) e’ (3; 8; 11)

•

, … , in

La definizione di base di uno spazio e’: un insieme di vettori e’ una base di se

1 2,

valgono le ue seguenti condizioni:

, … ,

1. generani

1 2,

2. Se uno dei due vettori e’ rimosso, allora i rimanenti k-1 vettori non generano

2

• = (2, 8, 1) ( )

Dato il vettore il suo trasporto e’ 8

1

• La definizione di combinazione convessa tra vettori e’: un vettore y e’ combinazione convessa dei

, … , ⋋ ,⋋ , … ,⋋

vettori se esistono numeri reali tali che:

1 2, 1 2

⋋ ,⋋ , … ,⋋ ≥ 0

1. 1 2

⋋ + ⋋ , + ⋯ , + ⋋ = 1

2. 1 2

=⋋ +⋋ + ⋯ + ⋋

3. 1 1 2 2

4 Dispensa

•

La definizione di matrice e’ : prende nome matrice di ordine una tabella di elementi

ordinatamente disposti su m righe e n colonne

• L’operazione di addizione tra due matrici A e B e’ definita se le matrici hanno lo stesso rango

• = { }

L’operazione di moltiplicazione di una Matrice A per uno scalare k e’ data da

• La moltiplicazione tra due matrici e’ possibile se il numero di colonne A e’ uguale al numero di righe

B

• Il rango di riga di una matrice e’ il numero massimo di righe linearmente indipendenti

• Una matrice A ha rango pieno se Rango (A) = min (m,n)

• Per la soluzione di un sistema di equazioni lineari vale che se il Rango(A,b) > Rango (A) allora il

sistema non ammette soluzioni; se il rango (A,b) = Rango (A) allora il sistema ammette soluzioni

• Una matrice A si dice quadrata se il numero di righe e’ uguale al numero di colonne

1 2 3 2 1

• = =

3 4 1 1 1

2 1 −1 −1 4 1 15

= ∗ =

Date le due matrici, la matrice e’ 9 11

6 −1

3 1 4 1 3 3

• = =

6 −2 3 −1 7 6

1 5 2 4 0 3 4 4 7

′

= + e =

Date le due matrici, la matrice 5 5 9

5 5 5

5 Dispensa

• Un problema di ottimizzazione deve essere formulato definendo funzione obiettivo, vettore delle

variabili decisionali, insieme delle soluzioni ammissibili

• Un problema i ottimizzazione consiste nel determinare, se esiste, un punto minimo o di massimo

della funzione f tra gli elementi di x

• Un problema di programmazione matematica e’ lineare quando:

1. La funzione obiettivo e’ lineare

2. L’insieme x e’ espresso in termini di relazioni di eguaglianze/disuguaglianze lineare

• Un problema di programmazione lineare (PL) con m vincoli ed n variabili si dice in FORMA

CANONICA di minimo quando e’ formulato come segue

min 2 =

≥

≥0

∈

•

In un problema di programmazione lineare il vettore rappresenta: il vettore dei coefficienti di

costo della funzione obiettivo

• In un problema di programmazione lineare il vettore x rappresenta: il vettore delle variabili

decisionali

• In un problema di programmazione lineare il vettore A rappresenta la matrice dei coefficienti dei

vincoli

• Due problemi di programmazione lineare P e P’ di max/min si dicono equivalenti S per ogni

soluzione ammissibile i P esiste una soluzione ammissibile di P’ con lo stesso valore di funzione

obiettivo, e viceversa

• Se due problemi P1 e P2 sono equivalenti, le loro soluzione ottime hanno lo stesso valore

6 Dispensa

• +

= {: = }

Un insieme geometrico H e’ un iperpiano se e solo se con p vettore, k scalare

• Un insieme e’ convesso se e solo se dati due punti x,y appartenenti ad x ogni punto w generato

come loro combinazione convessa e’ tale che w appartiene ad x

• Un poliedro e’ l’intersezione di un numero finito di semispazi

• Un politopo e’ un poliedro chiuso e limitato

• l’oggetto in figura e’ un poliedro illimitato con x insieme convesso

• l’oggetto in figura e’ un politopo con x insieme convesso

• Il gradiente di un iperpiano rappresenta la direzione in crescita di un iperpiano

• (1 −⋋)

=⋋ + ⋋ [0,1]

Dati due vettori x e y la loro combinazione convessa e’

• Dato un iperpiano H ed un semispazio S vale che:

1. Un iperpiano e’ insieme convesso

2. Un semispazio e’ un insieme convesso

3. L’intersezione di iperpiani/semispazi produce un insieme convesso

• = {: + + ⋯ + = } l’insieme F definisce un iperpiano

1 1 2 2

7 Dispensa

• Dato un problema in forma generale di minimo di PL, un punto x* e’ un ottimo globale per la

∗

( ) ( )

≤ ∀ in

funzione f(x) se e solo se

• Una funzione f(x) si dice convessa su di un insieme convesso x se presi due punti qualsiasi x1 e x2 in

(⋋ (1 −⋋) ) ( ) (1 −⋋)(

+ ≤ ⋋ + )

X risulta che 1 2 1 2

• Se f e’ una funzione convessa in un insieme convesso x allora: ogni ottimo locale (se ne esistono) e’

anche ottimo globale

• Un punto di un poliedro X e’ un punto estremo se e solo se non puo’ essere espresso come

0 <⋋< 1)

combinazione convessa stretta (cioe’ con i altri punti di X

• = { + ⋋ ∶ ⋋≥ 0}

Un raggio R di vertice x0 e di direzione d e’ un insieme i punti della forma 0

• La definizione di CONO CONVESSO e’ un cono convesso C e’ un insieme convesso tale che se x

⋋ ⋋≥ 0

appartiene a C allora anche appartiene a C per ogni

•

≥ 0

La soluzione ottima di un problema di minimo e’ finita se e solo se per ogni direzione di

• Dato un poliedro X non vuoto con punti estremi Xi con i=1,...,k e direzioni estreme dj con j=1,...,t;

ogni punto x appartenente a x puo’ essere espresso come combinazione convessa dei punti estremi

di x e combinazione lineare non negativa (conica) delle sue direzioni estreme

• Una direzione d di un poliedro x, e’ una direzione estrema di x se e sono se non e’ esprimibile come

combinazione conica di altre direzione di x

• = {: ≤ , ≥ 0} (Poliedro

Dato un qualsiasi punto x appartenente ad x, il vettore d e’ una direzione del poliedro se:

( )

1. +⋋ ≤

2. +⋋ ≥ 0

3. ≠ 0

8 dispensa

• Data una matrice A di dimesione mxn, relativa ad un problema PL in forma standard di minimo, si

()

[ ]

= = <

puo’ partizionare come

• () ≠ 0

Data una matrice A di dimensione mxm e’ non singolare se

• −1

= >0

Dato una soluzione di base Xb, rappresenta anche una soluzione ammissibile se

!

• Il massimo numero di possibili matrici di base per una matrice A di dimensioni mxn e’ !(−)!

• Una soluzione e’ detta degenere se presenta qualche componente nulla

• Data una matrice A di dimensioni mxn, relativa ad un problema di PL in forma standard di minimo,

[ ]

=

partizionata come segue allora la matrice e’ composta da m colonne linearmente

indipendenti di A

• Una soluzione al sistema di equazioni Ax=b mxn corrisponde a determinare il valore delle m

variabili avendo fissato arbitrariamente il valore delle restanti n-m

• Data una matrice di A di dimensioni mxn, il numero delle possibili ‘estrazioni’ di sottomatrici

corrisponde ad un limite superiore al numero di soluzioni di base

• Secondo il Teorema Fondamentale della PL, dato un problema di PL in forma standard di minim,

con A matrice di dimensioni mxn con rango(A)=m ed m<n si ha:

1. Esiste una soluzione ammissibile se e solo se esiste una soluzione ammissibile di base

2. Esiste una soluzione ottima finita se e solo se esiste una soluzione ottima che e’ anche di

base

• ≥ 0,

Dato un insieme convesso X formato dall’insieme dei punti x tali che Ax=b con e’ un

punto estremo i x se e solo se e’ una soluzione di base ammissibile

9 dispensa

• Nella formazione della F.O. per l’algoritmo del simplesso, vengono detti ‘coefficienti di costo

( − )

ridotto’ i coefficienti:

• Una soluzione di base non degenere di un problema di PL è ottima se e solo se è una soluzione

ammissibile e non migliorabile

• Nel metodo del gradiente, per la scelta della variabile entrante, si sceglie la variabile fuori base che

localmente fa aumentare più rapidamente l’obbiettivo

• L’input dell’algoritmo del simplesso è un problema di PL in forma standard di minimo e una

soluzione ammissibile

• − ≤ 0

Il test di ottimalità dell’algoritmo del simplesso viene effettuato valutando se si ha la

soluzione ottima

• Il test di illimitatezza dell’algoritmo del simplesso viene effettuato valutando se yik per ogni i

=1,...,m

• Nell’algoritmo del simplesso, partendo da una soluzione di base ammissibile con valore associato di

∗

=

F.O. z, per valutare se una variabile fuori base xk migliora la funzione obiettivo se si considera

( )

− −

• Dal teorema sulla condizione di ottimalità una soluzione di base non degenere di un problema di PL

è ottima se e solo se la soluzione corrente è ammissibile e non migliorabile

• Nell’algoritmo del simplesso, partendo da una soluzione di base ammissibile con valore associato di

F.O. ; z per valutare quale tra le variabili attualmente in base deve uscire si sceglie quella che

supera il test dei minimi rapporti

• Nell’algoritmo del simplesso la soluzione ottima viene selezionata tra tutti i punti nell’insieme dei

numeri reali

10 dispensa

• La funzione obiettivo è una funzione scalare di cui stiamo cercando il valore minimo e massimo

• Un problema di programmazione lineare è un problema di ricerca del punto di minimo o di

massimo di una funzione lineare in presenza dei vincoli lineari

• min{ ( ): } {−( ):

| ∈ | |max ∈ }|

è equivalente a

• min{( ): }

∈ ≤ 2

Il seguente problema è un è un problema di programmazione interna

• ∈ {0,1}

La variabile rappresenta una variabile booleana

• Il seguente problema

12

+ 2

2

− + 3 ≤ 0

1 2

è un problema di programmazione non lineare vincolata

2

+ 21 − 3 = 0

• { il seguente sistema di equazioni definisce un punto

1 − 2 = 4

2 ≤ 3 − 1

• { 1 ≥ 0 il seguente sistema definisce una superficie chiusa e limitata

2 ≥ 0

2 − 21 − 4 ≥ 0

• { il seguente sistema definisce un insieme vuoto

22 − 41 + 3 ≤ 0

2

1 2

− + 3 ≤ 0

• min 2

1 + 2 − 6 ≤ 0

1, 2 ≥ 0

Risolvere il seguente problema di PL indicando il valore della funzione obiettivo all’ottimo

=3

11 dispensa

•

Con si intende un vettore riga

• 21 + 32 = 0 ; −41 − 62 = 3

La matrice costruita dal seguente sistema di equazioni è una

matrice singolare

• Dati i seguenti vettori

2

= =

1 4 0 1

3

Il loro prodotto scalare vale 11

• Data la seguente matrice

2 0 3

= 5 1 6

4 2 2

Il determinante è -2

• Dato un poliedro P e un punto generico X0, la retta perpendicolare al gradiente della funzione

obiettivo in quel punto rappresenta una direzione verso la quale non si hanno variazione della F.O.

• Data la seguente funzione f e il punto Xo, il modulo del gradiente di f in quel punto vale

2

( ) = 1 + 32 ; 0 = (2, −3) =3

• Risolvere il seguente problema di PL

−2

1 − 22 + 6 ≤ 0

min =-6

1 + 2 − 6 ≤ 0

1, 2 ≥ 0

• 1 − 22 + 6 ≥ 0

La trasformazione di dalla forma canonica a quella standard è

1 − 22 − 1 = 6

1 ≥ 0

• 21 − 2 − 3 = 1

La trasformazione di dalla forma standard a quella canonica è

21 − 2 − 3 ≥ 1

−21 + 2 + 3 ≥ −1

12 dispensa

• Data una matrice A=(mxn) ha rango pieno se ha m righe linearmente dipendenti

• Una matrice A è singolare se det(A)=0

• −1

= ≥ 0

è una soluzione del sistema

• Dato un problema di