Ricerca operativa

Ricerca operativa

Simone Belli

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 fornisce 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 distinguono le seguenti classi di problemi:

• nX = problemi di ottimizzazione continua. R n
• S = problemi di ottimizzazione continua non vincolata. R n⊂
• S problemi di ottimizzazione continua vincolata. R
• nX = 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 lineare. 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 lavorazione è 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 tipo 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 + 350x1 2 3 4

≤ 2x + 1.5x + 0.5x + 2.5x 1001 2 3 4

≤ 0.5x + 0.25x + 0.25x + x 501 2 3 4

x > 0i

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   y1 n y2   XT 7−→ x x ... x (x, y) x y = = x y   . 1 2 n i i ..   i=1 yn

  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 2 x 4 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 < bi
• 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 m x n ∈ 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 ammissibile è 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 disuguaglianze 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 così 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é definiti 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 m x n 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 concludere 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 definizione, 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 m x n 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 = bi Ti

Esso rappresenta quindi l&rs