Ricerca operativa

Ricerca operativa

Simone Belli

1

Indice

1 Introduzione 4

1.1 Problemi di ottimizzazione . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Primo esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Prodotto scalare . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Problemi di programmazione lineare 9

2.1 Poliedri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Esempio: calcolo dei vertici . . . . . . . . . . . . . . . . . . . . . 13

2.3 Ultime considerazioni . . . . . . . . . . . . . . . . . . . . . . . . 14

2.4 Teorema fondamentale della PL . . . . . . . . . . . . . . . . . . . 15

3 Teoria della dualità 16

3.1 Teorema della dualità debole . . . . . . . . . . . . . . . . . . . . 17

3.2 Conseguenze del teorema della dualità debole . . . . . . . . . . . 18

3.3 Teorema della dualità forte . . . . . . . . . . . . . . . . . . . . . 18

3.4 Scrittura dei problemi duali . . . . . . . . . . . . . . . . . . . . . 19

3.5 Condizioni di complementarietà . . . . . . . . . . . . . . . . . . . 19

3.5.1 Caso generale . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5.2 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Metodo del simplesso 22

4.1 Forma standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3 Matrici di base e fuori base . . . . . . . . . . . . . . . . . . . . . 24

4.4 Procedura per calcolare SBA . . . . . . . . . . . . . . . . . . . . 26

4.4.1 Schema riepilogativo . . . . . . . . . . . . . . . . . . . . . 26

4.5 Criterio sufficiente di ottimalità . . . . . . . . . . . . . . . . . . . 27

4.6 Criterio di illimitatezza . . . . . . . . . . . . . . . . . . . . . . . 30

4.7 Costruzione di una nuova SBA . . . . . . . . . . . . . . . . . . . 32

4.7.1 Regola anticiclaggio di Bland . . . . . . . . . . . . . . . . 33

4.8 Algoritmo metodo del simplesso . . . . . . . . . . . . . . . . . . . 34

4.9 Operazione di Pivot . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Modelli di programmazione lineare 38

5.1 Modelli di allocazione ottima di risorse . . . . . . . . . . . . . . . 38

5.1.1 Schema generale . . . . . . . . . . . . . . . . . . . . . . . 38

5.1.2 Risorse concorrenti . . . . . . . . . . . . . . . . . . . . . . 39

5.1.3 Risorse alternative . . . . . . . . . . . . . . . . . . . . . . 40

5.2 Modelli di miscelazione . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2.1 Schema generale . . . . . . . . . . . . . . . . . . . . . . . 41

5.3 Modelli di pianificazione dei trasporti . . . . . . . . . . . . . . . 41

5.4 Modelli di programmazione lineare intera . . . . . . . . . . . . . 44

5.4.1 Problema dello zaino . . . . . . . . . . . . . . . . . . . . . 44

5.4.2 Problema dell’assegnamento . . . . . . . . . . . . . . . . . 45

2

5.5 Vincoli logici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.6 Variabili binarie come variabili indicatrici . . . . . . . . . . . . . 46

5.7 Costi fissi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.7.1 Problemi di gestione delle scorte . . . . . . . . . . . . . . 49

5.7.2 Problema di localizzazione di impianti . . . . . . . . . . . 50

3

1 Introduzione

Cosa è la ricerca operativa? Il termine Ricerca Operativa deriva dal termine

inglese “Operational Research”, ed è una disciplina che tratta dello sviluppo

e dell’applicazione di metodi scientifici per la risoluzione di problemi di tipo

decisionale. In un problema decisionale si è di fronte a vari possibili scenari, e

ovviamente quel che si vuol fare è scegliere in modo ottimale.

La ricerca operativa si fonda sul cosiddetto approccio modellistico, che for-

nisce una base scientifica per l’analisi di problemi decisionali.

L’approccio modellistico si fonda su due fasi:

• Rappresentazione attraverso un modello matematico.

– Analisi del problema: si va a capire, tramite un’attenta analisi del

problema stesso, come trovarne una soluzione che sia ottima.

– Costruzione del modello: si procede verso la ricerca della soluzione

ottima, costruendo il modello che rappresenta (da un punto di vista

matematico) il problema che si ha di fronte.

– Analisi del modello: occorre chiaramente capire in modo rigoroso se il

modello costruito descrive correttamente il problema e se può essere

ulteriormente migliorato ai fini della ricerca della soluzione.

• Risoluzione attraverso un metodo matematico.

– Soluzione numerica: trattandosi di un problema risolto da un punto

di vista matematico, esso deve ammettere una soluzione numerica.

– Validazione del modello: questa fase, come facilmente intuibile, è

una conseguenza positiva alla costruzione ed all’analisi del modello

costruito. 4

In base allo spazio delle variabili X e alla struttura dell’insieme S, si distin-

guono le seguenti classi di problemi:

• n

X = problemi di ottimizzazione continua.

R n

– S = problemi di ottimizzazione continua non vincolata.

R n

⊂

– S problemi di ottimizzazione continua vincolata.

R

• n

X = problemi di ottimizzazione discreta

Z n

⊆

– S problemi di programmazione a numeri interi.

Z n

⊆ {0,

– S 1} problemi di programmazione combinatoria.

I modelli che analizzeremo in questo corso sono modelli di programmazione li-

neare. In tali modelli è esplicitamente definito un obiettivo, espresso attraverso

una funzione lineare, da minimizzare o massimizzare e le variabili sono vincolate

ad appartenere ad un insieme prefissato, descritto anch’esso da funzioni lineari.

5

1.1 Problemi di ottimizzazione

Un problema di programmazione matematica (o problema di ottimizzazione) è

definito come: min f (x)

∈ ⊆

con x S, ove S X rappresenta l’insieme dei vincoli e X rappresenta lo spazio

n n

delle variabili (X può quindi essere oppure ).

R Z ∗ ∈

Risolvere questo problema significa determinare, se esiste, un x S tale

∗ ≤ ∀x ∈

che f (x ) f (x) S. ≡

N.B. max f(x) - min (−f (x))

1.2 Primo esempio

Un’industria chimica fabbrica 4 tipi di fertilizzanti F1, F2, F3, F4, la cui lavo-

razione è affidata a due reparti dell’industria: il reparto produzione e il reparto

confezionamento.

Per ciascun tipo di fertilizzante i tempi (in ore) di lavorazione in ogni reparto

per avere una tonnellata di fertilizzante sono i seguenti:

Ciascuna tonnellata di fertilizzante dà i seguenti profitti:

Determinare le quantità che si devono produrre settimanalmente di ciascun ti-

po di fertilizzante in modo da massimizzare il profitto complessivo, sapendo che

ogni settimana il reparto produzione e il reparto confezionamento hanno una

capacità lavorativa massima rispettivamente di 100 e 50 ore.

Le ore utilizzate per la produzione di F1, F2, F3 e F4 è data da:

· · · · ≤

2 F 1 + 1.5 F 2 + 0.5 F 3 + 2.5 F 4 100

Le ore utilizzate per il confezionamento dei fertilizzanti F1. F2, F3 e F4 è data

da: · · · ≤

0.5 F 1 + 0.25 F 2 + 0.25 F 3 + G4 50

6

La mia funzione obiettivo (da massimizzare) sarà:

250F 1 + 230F 2 + 110F 3 + 350F 4

ed essa rappresenta il profitto complessivo che vogliamo sia il più alto possibile.

4

Avendo 4 variabili (n = 4) il problema vive in . Prendiamo come variabili

R

x le tonnellate di fertilizzante F prodotto. Ecco che possiamo quindi scrivere

i i

il problema in modo più matematico in cui scriviamo la funzione obiettivo ed i

vincoli nel seguente modo:

max 250x + 230x + 110x + 350x

1 2 3 4

≤

2x + 1.5x + 0.5x + 2.5x 100

1 2 3 4 ≤

0.5x + 0.25x + 0.25x + x 50

1 2 3 4

x > 0

i

L’ultimo vincolo, ovvero x > 0 ci dice che le 4 variabili che abbiamo devono

i

essere tutte positive, e questo è ovvio se si pensa che le x le abbiamo definite

i

come le tonnellate di fertilizzante F prodotto (che per ovvie ragioni non può

i

essere nè negativo, nè nullo).

Questo tipo di vincolo prende il nome di vincolo di non negatività.

4

Il problema appena visto vive in . Se vogliamo scriverlo in modo più compatto,

R

abbiamo bisogno del prodotto scalare.

1.3 Prodotto scalare n

Vediamo il prodotto scalare in , definito come:

R n n 7−→

π : x

R R R  

y

1 n

y

2

  X

T

7−→ x x ... x

(x, y) x y = = x y



 .

1 2 n i i

..

 

  i=1

y

n

 

x 1

x 2

 

4

∈

Torniamo all’esempio: se x , e cioè x = ci chiediamo chi è c tale

R  

. . .

 

x n

T

per cui c x sia la funzione obiettivo del nostro modello. La risposta è data dai

coefficienti!    

c 250

1

c 230

2

   

c = =

   

c 110

3

   

c 350

4 4

∈ R

7

 

2

1.5

  e b = 100 il primo vincolo posso scriverlo in forma

Utilizzando a = 1

1  

0.5

 

2.5

T ≤

compatta come a x b

1

1  

0.5

0.25

  e b = 50 il secondo vincolo lo scrivo in forma

Utilizzando invece a = 2

1  

0.25

 

1

T ≤

compatta come a x b

2

2 T

a b

1

2x4 1

∈

Posso quindi introdurre una matrice A A = e il vettore b =

R T b

a 2

2

e scrivere l’insieme ammissibile del modello come

4

{x ∈ | ≤ ≥

S = Ax b, x 0}

R

Ricordiamo che il problema dei fertilizzanti poco fa illustrato consisteva nel

T

massimizzare il profitto (max c x). Ebbene, risolvendo il problema con un

∗

software di ottimizzazione si giunge alla soluzione ottima x = (0, 0, 200, 0),

il che ci dice che per ottenere il profitto più alto possibile dalla vendita dei

fertilizzanti bisogna produrre 200 tonnellate del solo fertilizzante 3. Questo può

sembrare sorprendente se si nota che F3 è il fertilizzante che costa meno di tutti.

8

2 Problemi di programmazione lineare

n 7→

Definizione. Una funzione f : si dice lineare se:

R R

• ∀ ∈

f (x,y) = f (x) + f (y) x, y R

• n

· ∀λ ∈ ∀x ∈

f (λx) = λ f (x) e

R R n T

∃ ∈

Si dimostra che f è lineare se e solo se c tale che f (x) = c x.

R n

In generale un problema di programmazione lineare (PL) in sarà definito da:

R

• T n

∈

funzione obiettivo lineare c x (con c )

R

• m vincoli lineari (di disuguaglianza o di uguaglianza).

Ti

– Di disuguaglianza: a x < b

i

Tj

– Di uguaglianza: a x = b j n

≥ ∈

Ora, se pensiamo ai vincoli del tipo x 0, con x come possiamo esprimerli

R

i

T ≤

attraverso il prodotto scalare a x b? −x ≤

Per prima cosa cambiamo il segno al vincolo, cioè scriviamo 0.

i

n T

∈ −x

Ci chiediamo: chi è a tale che a x = ?

R i

Come facilmente intuibile, essa non è altro che l’i-esima componente della base

canonica, con un segno - davanti. 

 0

0



 

 1





−e −

a = =

i 

 . 

 

 . 

 0

Ti

−x ≤ 7−→ −e ≤

0 x 0

i

−e

dove a = e ovviamente b = 0.

i mxn

∈

Tornando quindi all’esempio precedente, la matrice A (dove m rap-

R

presenta il numero di vincoli del nostro problema e n rappresenta il numero di

variabili presenti) che esprime tutti i vincoli del problema è data da:

T

     

a 2 1.5 0.5 2.5 100

1

T  

a 0.5 0.25 0.25 1 x 50

1

     

2

     

T

−e −1 0 0 0 x 0

2

       

1 = =

       

T −1

−e 0 0 0 x 0

3

     

 

2

     

T −1

−e 0 0 0 x 0

4

     

3

T −1

−e 0 0 0 0

4

Definizione. Un problema di PL può anche non essere ammissibile. In

particolare è: 9

• {x ∈ | ≤

Non ammissibile, se la regione ammissibile S = Ax b} è

R

vuota

• T

∀M ≥ ∃ ∈ −M

Illimitato inferiormente, se 0 x S tale che c x <

Cadere in uno di questi due casi significa che il problema non ammette soluzione

ottima (o non esiste oppure è illimitata). Ovviamente il problema può avere

soluzione ottima.

• T T

∃ ∈ ≤ ∀x ∈

Ammette soluzione ottima se x* S tale che c x* c x S

N.B. Se un problema di minimizzazione ha la regione ammissibile illimitata

che il problema sia illimitato inferiormente (è quindi condizione ne-

può essere

cessaria e non sufficiente).

Se invece il problema di PL è illimitato inferiormente allora la regione ammissi-

bile è illimitata.

La stessa cosa ovviamente vale per problemi di massimizzazione, in cui la regione

ammissibile invece sarà illimitata superiormente.

2.1 Poliedri

Un insieme definito da disugualianze lineari mi va a definire un poliedro. Prima

di definirlo però, introduciamo altre nozioni fondamentali.

n

∈ ∈

Definizione. Sia a , b . L’insieme H dei punti

R R T

{x ∈ |

H = a x = b}

R

T

è detto iperpiano ed è definito da a x = b.

2 3

In un iperpiano è chiaramente una retta, mentre in è un piano e cosi via.

R R

A partire da un iperpiano possiamo distinguere due semispazi. Infatti, dato

T

l’iperpiano a x = b si definiscono gli insiemi

• ≥ n T

{x ∈ | ≥

S = a x b}

R

• ≤ n T

{x ∈ | ≤

S = a x b}

R

Questi insiemi sono appunto detti semispazi, e sono insiemi chiusi (perchè de-

≥ ≤).

finiti dalle operazioni e n

⊆

Definizione. Un poliedro P è un insieme definito come intersezione

R

finita (cioè di un numero finito) di semispazi chiusi e di iperpiani.

Algebricamente può essere rappresentato come:

n

{x ∈ | ≤

P = Ax b}

R

mxn m

∈ ∈

con A e b .

R R

N.B. Un iperpiano si può vedere come intersezione di due semispazi:

n T n T T n T T

{x ∈ | {x ∈ | ≤ ≥ {x ∈ | ≤ −a ≤ −b}

a x = b} = a x b, a x b} = a x b, x

R R R

10

n

∈

Definizione. Dati x, y , l’insieme dei punti definiti come:

R

n

{z ∈ | − ∈

z = αx + (1 α)y, α [0, 1]}

R

è detto segmento chiuso di estremi x, y e si può indicare con [x, y].

n

⊆ ∀ ∈ ⊆

Definizione. Un insieme C è convesso se x, y C si ha [x, y] C,

R

− ∈ ∀ ∈

ovvero se αx + (1 α)y C α [0, 1]

La convessità dunque vuole che comunque presi due punti x e y in un insieme

C, il segmento che unisce i due estremi x e y deve essere tutto contenuto in C.

n

⊆

Proposizione. Dati C, D convessi, la loro intersezione è un insieme

R

convesso. ∈ ∩ ⊆ ∩

Dimostrazione. Siano x, y C D, vogliamo dimostrare che [x, y] C D:

• ∈ ⊆

x, y C e C convesso =⇒ [x, y] C

• ∈ ⊆

x, y D e D convesso =⇒ [x, y] D

⊆

Di conseguenza, poichè [x, y] C, D esso appartiene anche alla loro intersezione

⊆ ∩

(che è anche essa convessa), e quindi [x, y] C D

n T

{x ∈ | ≤

Proposizione. Un semispazio chiuso a x b} è un insieme convesso.

R

Corollario. Anche un iperpiano è un insieme convesso perchè intersezione

di due insiemi convessi.

Di conseguenza, da queste ultime due affermazioni possiamo chiaramente con-

cludere che anche un poliedro è un insieme convesso dato che, come abbiamo già

detto quando abbiamo definito un poliedro, esso non è altro che l’intersezione di

un numero finito di semispazi (chiusi) e iperpiani. Quindi, essendo questi ultimi

degli insiemi convessi, anche un poliedro è un insieme convesso.

T n

≤ ∈ ∈

Definizione. Una disuguaglianza del tipo m x δ, con m e δ

R R,

n

⊆ ∈

si dice valida per un insieme P se è soddisfatta da ogni punto x P.

R n

⊆

Definizione. Una faccia di un poliedro P è l’insieme definito F come

R

n T

{x ∈ | ∩

F = m x = δ} P

R

T

̸ ∅,

N.B. Se F = l’iperpiano m x = δ è detto iperpiano di supporto di P.

Notiamo che l’intersezione tra un iperpiano ed un poliedro (e quindi, per defi-

nizione, una faccia del poliedro) può essere vuota oppure può rappresentare un

solo vertice o ancora una faccia vera e propria del poliedro.

11

N.B. La faccia di un poliedro è ancora un poliedro.

n

⊆ ∈ ̸ ∃ ∈

Definizione. Sia P , si definisce x P punto estremo di P se x , x

R 1 2

̸ ̸ −

P (con x = x, x = x) tale che x = αx + (1 α)x per qualche

1 2 1 2

∈

α [0,1]. ̸ ∃

In altre parole questo è vero se x , x tali per cui x appartiene al segmento

1 2

che congiunge x e x .

1 2

• Nei poliedri i punti estremi sono i vertici.

n

{x ∈ | ≤

Definizione. Sia P = Ax b} un poliedro, definito quindi da

R

mxn m

∈ ∈

A e b .

R R

∈

Dato x P si definisce l’insieme dei vincoli attivi in x l’insieme

Ti

{i ∈ {1, | }

I(x) = 2, ..., n} a x = b

i Ti

Esso rappresenta quindi l&rs