Metodi e modelli di ottimizzazione - Appunti

Modelli di programmazione lineare (PL)

Assiomi alla base della PL

 Proporzionalità: Il contributo di una variabile di decisione in ogni funzione è proporzionale secondo una costante moltiplicativa alla quantità rappresentata dalla variabile stessa.

 Additività: Il contributo di più variabili di decisione in ogni funzione è dato dalla somma dei contributi di ogni singola variabile.

 Continuità: Una variabile di decisione può assumere tutti i valori reali (nel suo intervallo di ammissibilità) e quindi le variabili possono avere valore frazionario.

 Certezza: I valori dei parametri che definiscono un problema (input) sono considerati certi (veri) e quindi il modello e la sua soluzione sono strettamente legati ad essi.

Funzioni lineari

Una funzione reale di n variabili reali si dice lineare se valgono le seguenti condizioni:

• Per ogni coppia di vettori reali x, y si ha: f(x+y) = f(x) + f(y)
• Per ogni vettore reale x e scalare λ si ha: f(λx) = λf(x)

Proposizione: T+…+c

Una qualsiasi funzione lineare si può scrivere nella forma f(x)=c x1 + … + c x_n n

Dimostrazione: Sia f(x) una funzione che soddisfa le condizioni i e ii e sia {e1, e2, ..., en} la base canonica dello spazio vettoriale Rⁿ per cui, per ogni x in R si ha:

…+x = x e + x e … + x e

Utilizzando le proprietà di linearità si può scrivere:

f(x) = f(x e1 + x e2 + ... + x en)

= f(x e1) + f(x e2) + ... + f(x en)

= x f(e1) + x f(e2) + ... + x f(en)

= x c1 + x c2 + ... + x cn

Modello generale di PL

Costruzione

1. Definizione delle variabili del modello (variabili decisionali) che sono le quantità incognite sulle quali si deve prendere la decisione. Le n variabili si indicano con x1, x2, ..., x_j, ..., x_n, j=1,2,...,n.
2. Formulazione dei vincoli del modello che sono funzioni delle variabili decisionali.
3. Formulazione della funzione obiettivo che è una funzione delle variabili decisionali. A seconda del tipo di problema la funzione obiettivo dovrà essere massimizzata o minimizzata.

Modello di PL di riferimento

Minimizzazione dell'input (risorse) per realizzare un prefissato livello di output (prestazione) minimo richiesto.

Massimizzazione dell'output (prestazione) ottenibile da una prefissata quantità di input (risorse) massima disponibile.

Modello in forma arbitraria

Le forme (1) e (2) possono essere considerate forme di riferimento in quanto un problema di PL in forma arbitraria può sempre essere riscritto equivalentemente in queste due forme.

Vantaggi e svantaggi della PL

Vantaggi

• I modelli di PL hanno carattere universale e si adattano a molte realtà applicative
• Sono facilmente comprensibili e interpretabili
• Gli algoritmi di PL permettono di risolvere problemi anche di grande dimensione
• È possibile eseguire analisi di sensibilità per studiare la dipendenza dell'ottimo del problema da variazioni marginali dei parametri

Svantaggi

Non sempre nelle applicazioni è possibile ricorrere a problemi di PL. Se l'ipotesi non soddisfatta è la continuità, si deve ricorrere a problemi di PLI. Se invece non tutte le funzioni sono lineari, si ricorre a problemi PNL.

Modello di allocazione ottima di risorse (produzione)

Un problema di produzione consiste nel determinare le quantità da fabbricare di ciascun prodotto in modo da massimizzare il profitto rispettando i vincoli delle risorse disponibili o sui livelli di produzione richiesti.

Prodotti P1, P2, ..., P_n

Risorse R1, R2, ..., R_m

(i=1, ..., n; j=1, ..., m) Quantità della risorsa R_i necessaria per fabbricare una unità del prodotto P_j: a_ij

(i=1, ..., m) Quantità di risorsa R_i disponibile: b_i

(j=1, ..., n) Profitto netto unitario per il prodotto P_j: c_j

Esistono due formulazioni:

• Risorse concorrenti: il bene fabbricato per essere finito e pronto per la vendita deve utilizzare tutte le risorse
• Risorse alternative: il bene fabbricato per essere finito e pronto per la vendita necessita esclusivamente di una risorsa

Modello di produzione con risorse concorrenti

• Variabili non negative
• Funzione obiettivo
• Vincoli sulle risorse

Modello di produzione con risorse alternative

• Variabili non negative
• Funzione obiettivo
• Vincoli sulle risorse

L'unica differenza tra le due formulazioni sta nella definizione del vettore delle variabili.

Modello di miscelazione

Si tratta di problemi in cui si hanno a disposizione un certo numero di sostanze ciascuna delle quali ha un certo costo ed un determinato contenuto di componenti utili. Si vuole ottenere la miscela più economica di queste sostanze in modo che contenga una certa quantità di ciascuno dei componenti utili.

Sostanze S1, ..., S_n

Componenti C1, ..., C_m (contenuti nelle sostanze)

(j=1, ..., n) Costo unitario della sostanza j: c_j

(i=1, ..., m) Fabbisogno (quantità minima di componente i): b_i

(i=1, ..., m; j=1, ..., n) Quantità di componente i presente in una unità di sostanza j: a_ij

Nota: in un modello di miscelazione possono essere presenti anche limitazioni superiori (upper bound) sulle variabili j.

Per uno o più componenti C_i, può essere richiesto che una miscela contenga una quantità non superiore ad una certa quantità massima d_i.

Modelli di trasporto

Si tratta di modelli in cui si hanno un certo numero di località (origini) ciascuna delle quali ha una quantità fissata di merce disponibile e un certo numero di clienti residenti in altre località (destinazioni) i quali richiedono quantitativi precisi di merce. Quindi, conoscendo il costo unitario del trasporto della merce da ciascuna origine a ciascuna destinazione è necessario pianificare i trasporti in modo da soddisfare l'ordine dei clienti minimizzando il costo complessivo derivante dai trasporti.

Origini O1, ..., O_m

Destinazioni D1, ..., D_n

(i=1, ..., m) Quantità disponibile all'origine i: a_i

(j=1, ..., n) Quantità richiesta dalla destinazione j: b_j

Costo unitario di trasporto dall'origine i alla destinazione j: c_ij

Il modello con ipotesi assenza di giacenze è il seguente:

Teorema

Il modello del trasporto M1 ammette soluzioni ammissibili se e solo se l'offerta totale eguaglia la domanda totale, nel qual caso il problema di trasporto si dice bilanciato.

Offerta totale = domanda totale

Dimostrazione necessità: Se esiste una soluzione ammissibile x_ij allora la condizione (*) deve essere verificata; poiché le x_ij devono soddisfare i vincoli, dalle equazioni di questi ultimi si ottiene: CVD.

Dimostrazione sufficienza: Supponiamo che valga la (*) e poniamo; si vuole dimostrare che esiste una soluzione ammissibile.

Infatti sia x_ij ora definito è una soluzione ammissibile per il problema del trasporto. Infatti x_ij ≥ 0 per la non negatività e inoltre x_ij soddisfa i vincoli del problema, è una soluzione ammissibile.

Se il problema non è bilanciato

• CASO 1: Offerta totale > domanda totale

In questo caso c'è possibilità di soddisfare pienamente la domanda. Tuttavia, se la quantità di materiale prodotto in eccesso non verrà inviata alle città, si verificheranno giacenze nelle origini, mentre, se tutto il materiale prodotto verrà inviato fuori dalle origini, la quantità in eccesso andrà persa perché non verrà utilizzata dalle città. In questo caso si dice che si genereranno giacenze nelle destinazioni.

• CASO 2: Offerta totale < domanda totale

In questo caso NON c'è possibilità di soddisfare tutte le domande delle città perché nelle origini considerate non si produce materiale a sufficienza.

Nel CASO 1 è possibile formulare un problema diverso da M1 in cui i vincoli permettono il verificarsi di giacenze. Le variabili di M2 sono le stesse di M1. M1 e M2 differiscono solo per la forma dei vincoli alle origini e alle destinazioni, invece di essere equazioni (M1) sono disequazioni (M2).

Nota: M2 è più generale di M1 e nel caso di problema bilanciato avrà la stessa soluzione ottima di M1. In questo caso tutti i vincoli di domanda e di offerta di M2 risulteranno attivi, cioè in corrispondenza della soluzione ottima, saranno comunque soddisfatti anche con l'uguaglianza. In generale, invece, in corrispondenza della soluzione ottima qualche vincolo sarà non attivo.

Nel CASO 2 il problema è NON AMMISSIBILE: si deve trovare un modo per produrre più offerta di materiale:

• Aumentare la produzione negli impianti disponibili
• Individuare un nuovo impianto che possa produrre la quantità di materiale mancante

Il modello M2 con la presenza di giacenze è il seguente:

Rappresentazione geometrica dei problemi di PL

Consideriamo un vettore x=(x1, x2, ..., x_n) e un punto x₀ nello spazio Rⁿ, si ha:

 Δx = x - x₀ la direzione con punto di partenza x₀ (origine degli assi)

 La lunghezza (norma) del vettore definita come

Definizione:

Si definisce spazio vettoriale di dimensione n (S_n) un insieme di vettori in Rⁿ chiuso rispetto alle operazioni di:

1. Somma tra due vettori
2. Moltiplicazione di un vettore per uno scalare

Operazioni tra vettori:

Moltiplicazione di uno scalare per un vettore in Rⁿ produce un nuovo vettore in Rⁿ. Consideriamo il vettore x=(4,1) e lo scalare 2 si ha 2x = (2*4, 2*1) = (8,2).

Somma algebrica tra due vettori di Rⁿ produce un nuovo vettore in Rⁿ. Consideriamo il vettore x'=(2,-3) e x=(4,1) si ha x'+x = (2+4, -3+1) = (6, -2).

Sottrazione algebrica tra due vettori in Rⁿ produce un nuovo vettore in Rⁿ. Consideriamo il vettore x'=(2,-3) e x=(4,1) si ha x'-x = (2-4, -3-1) = (-2, -4).

Combinazione lineare di due vettori in Rⁿ produce un nuovo vettore in Rⁿ. Consideriamo due vettori x'=(2,-3) e x=(4,1) si ha x'+0.5x = (2+2, -3+0.5) = (4, -2.5).

Considerando i vettori in R² come punti nello spazio bidimensionale, un modello di PL in due variabili può essere risolto con il seguente metodo geometrico:

• Passo 1. Si rappresentano le condizioni di non-negatività e i vincoli “strutturali” (come semipiani chiusi);
• Passo 2. Si individua la regione ammissibile;
• Passo 3. Si rappresenta la funzione obiettivo (curve di isoprofitto/isocosto);
• Passo 4. Si individua la soluzione ottima.

La regione ammissibile è sempre convessa (poligono/poliedro) anche se può avere forme e caratteristiche diverse. Si possono presentare diverse situazioni:

• Ottimo finito unico
• Ottimo finito multiplo
• Ottimo illimitato
• L'ottimo non esiste (il problema non è ammissibile)

Dal teorema di Weirstrass: la regione ammissibile P è chiusa e limitata, l'ottimo si consegue su uno dei vertici.

Dal teorema fondamentale della PL.

Metodi di soluzione

Metodo enumerativo

Valutare la funzione obiettivo in tutti i vertici analizzando tutti i punti di intersezione tra le rette, una strategia per la valutazione sistematica dei vertici della regione P.

Metodo del Simplesso

A partire da un vertice ammissibile, viene generata una sequenza di vertici ammissibili adiacenti, che corrispondono cioè a estremi opposti dello stesso spigolo. Nota: la strategia del metodo del simplesso è migliore di quella del motodo enumerativo.

Lemma T

Sia data la seguente famiglia di rette parallele a1x1+a2x2 = c (equiv. a^Tx = c) con a1 e a2 reali fissati e c in R. Il vettore a = (a1, a2) individua una direzione ortogonale alle rette della famiglia a1x1+a2x2 = c ed è orientato dalla parte in cui si trovano le rette della famiglia ottenute per valori crescenti di c, cioè dalla parte in cui ci si sposta dalla retta a1x1+a2x2 = c verso nel semipiano a1x1+a2x2 ≥ c.

Dimostrazione:

1. Il vettore a = (a1, a2) individua una direzione ortogonale alle rette a^Tx = c, c R.
2. Fissato c, il vettore a = (a1, a2) è orientato da a^Tx = c verso il semipiano a^Tx ≥ c.

Dim 1. Il vettore a = (a1, a2) individua una direzione ortogonale alle rette a^Tx = c. Consideriamo un valore c fissato e due punti v e w appartenenti alla retta a^Tx = c: a^Tv = c e a^Tw = c. Sottraendo membro a membro, si ottiene: a^T(v-w)=0. a^T è ortogonale al vettore (v-w); infatti a^T(v-w)=0 cosϑ = 0, ϑ è l’angolo formato da a e (v-w) è di 90°.

Dim 2. Fissato c, il vettore a = (a1, a2) è orientato da a^Tx = c verso a^Tx ≥ c. Consideriamo un valore c fissato e un punto y tale che a^Ty ≥ c. Si ha a^Ty ≥ c e a^Tw = c. Sottraendo membro a membro si ottiene a^T(y-w) ≥ 0, a e (y-w) formano un angolo acuto infatti a^T(y-w) cosϑ ≥ 0, ϑ ≤ 90°.

Ricorda: dati i vettori a e b per l’angolo ϑ da essi formato si ha cosϑ= a^Tb/||a|| ||b||.

Dal lemma: data la famiglia a^Tx = c, c R, il vettore a individua due direzioni:

• Direzione di a=(a1, a2) --------> gradiente di f(x)= a^Tx, Vincolo a^Ty ≥ c, F.O max a^Tx
• Direzione di a=(a1, a2) --------> antigradiente di f(x)= a^Tx, Vincolo a^Ty ≤ c, F.O min a^Tx

Lezione sull’algebra lineare

Dipendenza e indipendenza lineare

Definizione: Un vettore b∈Rⁿ è combinazione lineare dei vettori a1,..,a_k in Rⁿ se esistono k reali λ1, ..., λ_k tali che:

• Se λ1 +…+ λ_k = 1 la combinazione si dice AFFINE
• Se λ1 ≥ 0, …, λ_k ≥ 0 la combinazione si dice CONICA
• Se λ1 +…+ λ_k = 1 e λ1 ≥ 0, …, λ_k ≥ 0 la combinazione si dice CONVESSA

Definizione: L’involucro lineare (affine, conico o convesso) dei vettori a1, .., a_k in Rⁿ è l’insieme delle combinazioni lineari (affini, coniche, convesse) di a1, .., a_k.

Definizione: I vettori a1, .., a_k in Rⁿ si dicono linearmente dipendenti se esistono k reali non tutti nulli tali che λ1a1 + … + λ_ka_k = 0.

Proprietà: I vettori a1, .., a_k in Rⁿ sono linearmente dipendenti se e solo se almeno uno di essi è esprimibile come combinazione lineare degli altri.

Definizione: I vettori a1, .., a_k in Rⁿ si dicono linearmente indipendenti se non sono linearmente dipendenti.

Teorema 1

In uno spazio vettoriale di dimensione n, S contenuto in Rⁿ, esistono infinite n-uple di vettori linearmente indipendenti; ogni insieme di n+1 (o più) vettori in S è sempre linearmente dipendente. In S il massimo numero di vettori linearmente indipendenti è n.

Esempio:

• Spazio unidimensionale S₁ (retta). Il massimo numero di vettori linearmente indipendenti è 1. Comunque si prendano 2 vettori in S₁ essi risultano linearmente dipendenti. Nota: i due vettori giacciono sulla stessa retta.
• Spazio bidimensionale S₂ (piano). Il massimo numero di vettori linearmente indipendenti è 2. Comunque si prendano 3 vettori in S₁ essi risultano linearmente dipendenti. Nota: i due vettori giacciono sullo stesso piano e esiste un sottospazio di dimensione inferiore a n vettori linearmente dipendenti che li contiene tutti.

Teorema 2

Dati n vettori linearmente indipendenti in S_n, un qualsiasi altro vettore dello stesso spazio è esprimibile come combinazione di tali vettori in modo univoco (cioè con λ1, ..., λ_n unici).

Definizione: n vettori linearmente indipendenti in S_n costituiscono una BASE per S_n e tale base genera tutti i vettori di S_n, ciascuno come combinazione lineare degli n elementi della base con coefficienti λ1, ..., λ_n unici.

Definizione il rango ρ Dato un insieme {a1, ..., a_m} di m vettori in S_n, di tale insieme ρ è il massimo numero di vettori linearmente indipendenti che possono essere estratti da {a1, ..., a_m}.

• ρ = n ≤ m: se esistono in {a1, ..., a_m} vettori che formano una base di S_n.
• ρ = m ≤ n: se gli m vettori a1, ..., a_m sono linearmente indipendenti e generano un sottospazio vettoriale di S_n di dimensione m.
• ρ < m ≤ n ρ < n: se esistono in {a1, ..., a_m} vettori linearmente indipendenti che generano un sottospazio vettoriale di S_n di dimensione ρ.

Matrici

Definizione: Data una matrice A, si definisce minore di ordine k il determinante di una matrice estratta da A_mxn quadrata.