Dispensa PL 1 - dispense PDF

Preview

Summary

Cattedra diMetodi Quantitativi per ilManagement e la FinanzaParte I:appuntidiPROGRAMMAZIONE LINEAREP. Fersini, G. Foschini, G. Olivieria. 2009-Indice 1INTRODUZIONE 2ILPROBLEMAGENERALEDIASSEGNAZIONE 3LADETERMINAZIONEDELLESOLUZIONI 4LALOGICADELSIMPLESSO 5LASOLUZIONEGRAFICA 6LADETERMINAZIONEDELLESOLUZI...

Description

Cattedra di Metodi Quantitativi per il Management e la Finanza

Parte I: appunti di PROGRAMMAZIONE LINEARE P. Fersini, G. Foschini, G. Olivieri a.a. 2009-2010

1

Indice 1 INTRODUZIONE

3

2 IL PROBLEMA GENERALE DI ASSEGNAZIONE

4

3 LA DETERMINAZIONE DELLE SOLUZIONI

7

4 LA LOGICA DEL SIMPLESSO

9

5 LA SOLUZIONE GRAFICA

12

6 LA DETERMINAZIONE DELLE SOLUZIONI IN EXCEL 16 7 QUALCHE RICHIAMO TEORICO

22

8 ALCUNE COMPLICAZIONI NELLíUSO DEL SIMPLESSO 28 9 PRIMALE E DUALE 31 9.1 Analisi di sensibilit‡ . . . . . . . . . . . . . . . . . . . . . . . 38 10 Esercizi proposti

40

2

1

INTRODUZIONE

La programmazione lineare Ë parte della ìprogrammazione matematicaî, ovvero quellíinsieme di regole e di tecniche che hanno la Önalit‡ di ottimizzare determinate attivit‡ da svolgere con risorse limitate, come ad es., la produzione di un bene in cui le risorse (materie prime, ore lavorative, capitali, etc.) sono limitate. La programmazione matematica si pone líobiettivo di trovare la combinazione ottima di risorse che permettono di ottenere il massimo proÖtto per líazienda, o il minimo costo, e cosÏ via. La programmazione matematica puÚ essere: ! con funzioni di tipo continuo (funzioni continue di variabili continue) o discrete1 ; ! con funzioni lineari o non lineari, a seconda se godono o meno della propriet‡ di proporzionalit‡; ! statica, se si studia il problema a sÈ stante, o dinamica, se lo studio si evolve nel tempo; ! deterministica, se tutti gli elementi del problema sono noti o determinabili a priori o probabilistica altrimenti. La diversa combinazione di tali argomenti identiÖca diverse branche della programmazione matematica. Ci occuperemo in questa sede di programmazione lineare, che risolve i problemi lineari, continui, statici e deterministici di ottimizzazione2 . In generale, in un problema di ottimizzazione si cerca di massimizzare (o minimizzare) una speciÖca quantit‡ (obiettivo) che dipende da un numero Önito di variabili di input, che possono essere dipendenti o indipendenti fra loro o possono essere collegate da uno o pi˘ vincoli. Esempio 1 il problema sotto i vincoli

min Z = x12 + x22 !

x1 " x2 = 3 x2 # 2

1

Particolare interesse riveste il cosiddetto ìprogramma interoî, in cui le variabili di input possono assumere solo valori interi. 2 Ricor f (x) e f (x+y) = f (x)+ f (y), dove x

3

Ë un problema di ottimizzazione rispetto allíobiettivo Z. Le variabili di input sono x1 e x2 e i vincoli speciÖcano che la variabile x1 deve sempre essere maggiore di due unit‡ rispetto alla seconda variabile, che deve comunque essere non minore di 2. In ogni programma matematico si cerca una soluzione. Se esiste una serie di soluzioni ugualmente ottimali esse sono tutte ammissibili (solo la formulazione dei vincoli puÚ assegnare una speciÖca preferenza).

2

IL PROBLEMA GENERALE DI ASSEGNAZIONE

PuÚ essere esempliÖcato attraverso la determinazione di quali macchine dovrebbero essere impiegate per ottenere i prodotti che richiedono líuso alternativo di insiemi di risorse. Consideriamo, ad esempio, una fabbrica che produce n di§erenti prodotti in quantit‡ da determinare x1 ; x2 ; :::; xn utilizzando varie combinazioni di m di§erenti macchinari. Ogni unit‡ del prodotto j richiede ai;j unit‡ di tempo sulla macchina i, con j = 1; 2; : : : n; ed i = 1; 2; : : : ; m. Líammontare totale della disponibilit‡ (di tempo) per la prima macchina Ë b1 , per la seconda macchina Ë b2 ; : : : ; per lí i"esima Ë bi , . . . , per lím"esima Ë bm . Il guadagno per ogni unit‡ di prodotto venduto Ë cj . Appare subito chiaro che il modello Ë una rappresentazione astratta della real to caso líuso delle macchine, per o i utilizzo (non esistono economie di scala). Possiamo riassumere le informazioni in una tabella, detta schema generale di assegnazione.

4

Tabella 1: Lo schema generale di assegnazione Prodotti

R I S O R S E

1 2 3 ... i ... m

numero di ore disponibili*

1 a11 a21 a31 .. .

2 a12 a22 a32 ...

... ... ... ...

j a1j a2j a3j .. .

... ... ... ...

n a1n a2n a3n ...

b1 b2 b3

ai1 .. .

a12 ...

...

aij .. .

...

ain ...

bi ...

am1

a m2

... amj

... amn

bm

*nel periodo considerato Nella Tabella 1 líelemento aij indica la quantit‡ di risorsa ìiî necessaria a produrre il prodotto ìjî; colonna j Ë lo schema di produzione del prodotto 2 la 3 b1 ; il vettore

c =c = c1 c2 ::: cn Ë il vettore dei coe¢cienti della funzione obiettivo (ad esempio il guadagno associato alla vendita di ciascun prodotto). Sia il nostro obiettivo quello di massimizzare il guadagno totale (funzione obiettivo-FO). La FO Ë una funzione lineare, indichiamo con Z la variabile dipendente e con xj le variabili indipendenti: max Z =

n X

cj $ xj

(1)

j=1

o, in termini matriciali, indicando con c il vettore (riga) dei coe¢cienti della FO e con x il vettore (colonna) delle quantit‡ di produzione dei prodotti: max Z = c $ x

(2)

La FO, espressa dalla (1) o dalla (2) Ë soggetta a vincoli di disuguaglianza lineari:

5

8 > > > > > > > < > > > > > > > :

a11 x1 + a12 x2 + ::: + a1j xj + ::: + a1n xn % b1 a21 x1 + a22 x2 + ::: + a2j xj + ::: + a2n xn % b2 .. . ai1 x1 + ai2 x2 + ::: + aij xj + ::: + ain xn % bi .. .

(3)

am1 x1 + am2 x2 + ::: + amj xj + ::: + amn xn % bm

Inoltre, poichÈ le quantit‡ dei prodotti da produrre non possono essere negative, si devono aggiungere anche i ìvincoli di non negativit‡î: 8 x1 # 0 > > > > x2 # 0 > > > .. < . (4) xj # 0 > > > .. > > > . > : xn # 0 Indicando con A la matri 2 a11 a12 ... a1j 6 a21 a22 ... a2j 6 .. .. 6 ... . . 6 A =6 6 ai1 a12 ... aij 6 . .. .. 4 .. . . am1 am2 ... amj

... ... ...

a1n a2n ... ain ...

... amn

3 7 7 7 7 7 7 7 5

i vincoli (3) e (4) possono essere scritti in forma matriciale (5): ! A$x %b x#0

(5)

Il sistema (3) (4) o (5) prende il nome di sistema dei vincoli. Líinsieme dei valori x 2 Rn che soddisfa il sistema (3) prende il nome di soluzione del problema. Se líinsieme delle soluzioni soddisfano anche i vincoli di non negativit‡, si parla di so . Generalmente il numero delle disequazioni m Ë minore del numero delle variabili n; se ciÚ non accade non possiamo essere certi che esista una soluzione possibile. Il primo passo per trovare la soluzione ottima Ë quello di formalizzare il problema, ovvero pervenire alla scrittura della Tabella 1, del sistema dei vincoli e della FO.

6

Esempio 2 Uníazienda produce su commessa due tipologie di agende da regalo: il tipo ìtravelerî ñdi design sportivo- e il tipo ìexecutiveî ñdi design elegante. La lavorazione del tipo traveler richiede la met‡ delle ore lavorative richieste per la produzione del tipo executive. Se si producessero solo agende traveler, la capacit‡ produttiva sarebbe di 800 agende al giorno. Líazienda ha a disposizione cuoio per produrre non pi˘ di 600 agende in totale, ciascuna tipologia di agenda richiede la stessa quantit‡ impiegata di cuoio. Líazienda committente fornisce le altre materie prime e paga e5,00 per ogni agenda executive e e3,00 per ogni agenda traveler. Formalizzare matematicamente il problema, sapendo che líazienda ha líobiettivo di massimizzare il proprio guadagno. prodotti E T cuoio 1 1 600 ore lavorative 2 1 800 5 3 quindi il problema diviene: max Z = 8 5x1 + 3x2 x1 + x2 % 600 > > < 2x1 + x2 % 800 x1 # 0 > > : x2 # 0

3

LA DETERMINAZIONE DELLE SOLUZIONI

Un problema di PL Ë costituito da un sistema di disequazioni, che non puÚ essere risolto in modo ìautomaticoî: occorre trasformare le disequazioni in equazioni, introducendo delle ìvariabili aggiuntiveî o variabili slack, xn+1 ; xn+2 ; :::; xn+m , una per ciascuna disequazione del sistema dei vincoli: 8 a11 x1 + a12 x2 + ::: + a1j xj + ::: + a1n xn + xn+1 = b1 > > > > a21 x1 + a22 x2 + ::: + a2j xj + ::: + a2n xn + xn+2 = b2 > > > .. < . (6) a x + a x + ::: + a x > i1 1 i2 2 ij j + ::: + ain xn + xn+i = bi > > .. > > > . > : am1 x1 + am2 x2 + ::: + amj xj + ::: + amn xn + xn+m = bm 7

Le m variabili slack xn+1 ; xn+2 ; :::; xn+m rappresentano le quantit‡ eventualmente non utilizzate delle m risorse. I vincoli sono ora rappresentati da un sistema di m equazioni in n + m incognite, lineari: il sistema Ë dunque indeÖnito3; 4 . Per trovare la soluzione sceglieremo (casualmente) m incognite e calcoleremo la soluzione. Se otteniamo una soluzio Ë costituita da m variabili, le isfa anche i vinco ile. In altri termini, una base Ë un insieme di m delle n + m variabili tali che la matrice dei coe¢cienti A del relativo sistema di equazioni sia non singolare5 (il sistema cioË abbia soluzioni). Le variabili che formano la soluzione di base ammissibile si dicono variabili di base e le altre n variabili si dicono variabili non di base. Si osservi inÖne che per le funzioni lineari possiamo scrivere: max f (x) = " min ["f (x)] Per esse invece di massimizzare o minimizzare la f (x) si puÚ parlare di ottimizzare la f (x): una soluzione di base possibile ottima Ë una soluzione di base possibile che rende ottima la funzione obiettivo. Date le m equazioni nelle n + m incognite esistono inÖnite soluzioni al sistema considerato poichÈ abbiamo meno equazioni che incognite. Ma quante soluzioni di base esistono? Sono ìsoloî tutte le possibili combinazioni di (n + m) elementi a gruppi di m, ovvero Cn+m;m =

(n + m)! m! $ n!

3 Il teorema di RouchÈ-Capelli stabilisce che, a¢nchÈ un sistema di equazioni lineari sia compatibile (ovvero ammetta soluzioni), occo coe¢cienti sia uella cioË che si ottiene orlando la matrice dei e tale rango sia p. Indichiamo con n il numero delle incognite del sistema. Se p = n il sistema ammette uníunica soluzione, se p % n il sistema Ë indeÖnito, ammettendo 1n!p soluzioni. 4 Il sistema (6) Ë un sistema in cui il numero delle incognite Ë sicuramente maggiore del numero delle equazioni. PoichË tali equazioni rappresentano dei vincoli (ad esempio di produzione) possiamo ragionevolmente supporre le equazioni del sistema (6) non siano tra loro linearmente dipendenti (altrimenti saremmo in presenza di vincoli ridondanti) nË che il sistema dei vincoli sia incompatibile (se infatti stiamo esaminando un problema relativo ad una impresa che gi‡ produce un certo numero di beni Ë ovvio che almeno una combinazione produttiva deve essere fattibile). Il rango massimo della matrice dei coe¢cienti Ë (ovviamente) il min(m; n+m) ovvero il minimo tra il numero m di righe della matrice ed il numero (n + m) delle variabili, e cosÏ anche il rango della matrice completa (dimensionalmenta essa ha infatti solo una riga in pi˘ della precedente). Dunque i due ranghi dovranno essere uguali e il sistema ammetter‡ soluzioni. 5 Quindi det (A) 6= 0.

8

soluzioni di base6 . Basterebbe quindi calcolare queste Cn+m;m soluzioni e per ognuna calcolare la funzione obiettivo, per decidere quale di esse ottimizza la funzione obiettivo. Risulta evidente che gi‡ con 5 variabili (n) e 5 equazioni (m) Ë necessario risolvere 252 sistemi lineari di 5 equazioni in 5 incognite e man mano che crescono i vincoli questo numero aumenta notevolmente e anche i pi˘ potenti calcolatori faticano a determinare la soluzione cercata.

4

LA LOGICA DEL SIMPLESSO

Analizziamo con un semplice esempio come si puÚ pervenire alla soluzione ottima senza dover risolvere tutti i possibili sistemi. Esempio 3 Consideriamo il seguente problema di programmazione lineare: min Z = "x1 + x2 con vincoli:

8 "2x1 + x2 % 2 > > > > < x1 " 2x2 % 2 x1 + x2 % 5 > > x1 # 0 > > : x2 # 0

(7)

trasformiamo le disequazioni del sistema (7) in equazioni mediante líinserimento delle variabili slack: 8 "2x1 + x2 + x3 = 2 > > > > x1 " 2x2 + x4 = 2 > > > > > > x1 + x2 + x5 = 5 < x1 # 0 (8) x2 # 0 > > > > x3 # 0 > > > > x4 # 0 > > : x5 # 0 6

Ad esempio, se consideriamo una classe di 20 alunni, in quanti modi gli alunni possono sedersi a gruppi di 2? Dobbiamo calcolare le combinazioni di 20 elementi a gruppi di 2: 20! = 190, quindi esistono 190 modi possibili diversi per far sedere i 20 alunni nei 10 2!"18! banchi da 2 posti.

9

Una soluzione possibile di base Ë data da: / x1 = 0 vari x2 = 0 9 x3 = 2 = x4 = 2 variabili in base ; x5 = 5

Esprimiamo sia le equazioni che rappresentano i vincoli sia la funzione obiettivo esplicitando le variabili di base. Pertanto il sistema (8) diviene: 8 < x3 = 2 + 2x1 " x2 x = 2 " x1 + 2x2 : 4 x5 = 5 " x1 " x2

e la funzione obiettivo:

min Z = "x1 + x2 Il valore di Z con la soluzione possibile di base appena trovata Ë Z = 0. PoichÈ dobbiamo minimizzare Z (quindi determinare il valore pi˘ piccolo possibile di Z), osservando la forma funzionale di Z ci accorgiamo che, aumentando il valore di x1 possiamo diminuire Z: infatti il coe¢ciente della variabile x1 Ë "1 per cui, aumentando il valore della variabile x1 , il valore di Z diminuisce. Non possiamo perÚ aumentare il valore di x1 senza tener conto dei vincoli: occorre veriÖcare che líaumento del valore di x1 non renda le altre variabili negative. Eí immediato veriÖcare che: aumentando x1 "! aumenta x3 aumentando x1 "! diminuisce x4 aumentando x1 "! diminuisce x5 x4 diventa negativo quando x1 # 2; x5 diventa negativo quando x1 # 5. Dei due vincoli il primo Ë pi˘ ìstringenteî, per cui x1 puÚ aumentare Öno al valore ì2î. Quindi conviene ìfar entrareî in base la variabile x1 e far uscire x4 . Il sistema diventa: 8 x3 = 2 + 2x1 " x2 > > > > x > 1 = 2 + 2x2 " x4 > > > x5 = 5 " x1 " x2 > > < x1 # 0 (9) x2 # 0 > > > > x3 # 0 > > > > x4 # 0 > > : x5 # 0 10

Esprimiamo le variabili in base (x1 ; x3 ; x 5 ) in funzione delle sole variabili fuori base (x2 ; x4 ). Il sistema (9) diviene quindi: 8 x3 = 6 + 3x2 " 2x4 > > > > x1 = 2 + 2x2 " x4 > > > > x5 = 3 " 3x2 + x4 > > < x1 # 0 x2 # 0 > > > > x3 # 0 > > > > x4 # 0 > > : x5 # 0 La nuova soluzione possibile di base Ë: 9 x1 = 2 = x3 = 6 variabili di base x5 = 3 ; / x2 = 0 variabili non di base x4 = 0

e la funzione obiettivo diviene: Z = " (2 + 2x2 " x4 ) + x2 = = "2 " x2 + x4 e vale Z = "2. Osservando la funzione obiettivo si nota che possiamo diminuire ulteriormente il valore di Z aumentando il valore di x2 . Eí immediato veriÖcare che: aumentando x2 "! aumenta x1 aumentando x2 "! aumenta x3 aumentando x2 "! diminuisce x5 x5 diventa 0 quando x2 assume valore 1 (ricordiamo che x4 = 0). Quindi il sistema diviene: 8 x3 = 9 " x4 " x5 > > > 1 1 > x > 2 = 1 + 3 x4 " 3 x5 > > > x1 = 4 " 13 x4 " 32x5 > > < x1 # 0 x2 # 0 > > > > x3 # 0 > > > > x4 # 0 > > : x5 # 0 11

La nuova soluzione di base possibile Ë: 9 x1 = 4 = x2 = 1 variabili di base x3 = 9 ; / x4 = 0 variabili non di base x5 = 0 La funzione obiettivo diviene: 1 2 Z = "3 + x4 + x5 3 3 il valore di Z con questa soluzione possibile di base Ë Z = "3. Osserviamo ora che, poichÈ i coe¢cienti che appaiono nella funzione obiettivo delle variabili ivi coinvolte sono tutti positivi, nessun aumento dal valore 0 di tali variabili produce una diminuzione di Z. Per cui la soluzione possibile di base raggiunta Ë la soluzione possibile di base ottima. Abbiamo cosÏ risolto il problema di programmazione lineare risolvendo 3 sistemi invece di 10 (C5;3 ), semplicemente ìragionandoî su quali sistemi conviene risolvere. Tale ìtecnica risolutivaî, nota come ìmetodo del simplessoî Ë dovuta a Dantzig (1947).

5

LA SOLUZIONE GRAFICA

Quanto abbiamo ora espresso analiticamente puÚ essere rappresentato geometricamente. Consideriamo il problema dellíesempio 3: min Z = "x1 + x2 con vincoli:

8 "2x1 + x2 % 2 > > > > < x1 " 2x2 % 2 x1 + x2 % 5 > > x1 # 0 > > : x2 # 0

Disegniamo i graÖci delle corrispondenti funzioni lineari nel sistema di assi ortogonali x1 ; x2 . x2 = 2x1 + 2

12

GraÖco di y=2x+2 PoichÈ si tratta di una disequazione: x2 % 2x1 + 2 la parte di piano che soddisfa tale disequazione Ë quella sottostante la retta. E pertanto possiamo ridisegnare il graÖco (si veda il graÖco seguente, la porzione di piano che veriÖca la disequazione Ë quella evidenziata):

GraÖco di x2 % 2x1 + 2

13

Il secondo vincolo Ë:

1 x2 # x1 " 1 2

GraÖco di x2 # 21 x1 " 1

Ed il terzo vincolo: x2 % 5 " x1

GraÖco di x2 % 5 " x1

14

I vincoli di non negativit‡: !

x1 # 0 x2 # 0

individuano il I quadrante del sistema di assi cartesiani ortogonali. Se uniamo i graÖci otteniamo líarea in cui possiamo trovare la soluzione (ottima), delimitata nel graÖco seguente dal poligono OABCD.

La regione delle soluzioni. Eí evidente che poichÈ le disequazioni debbono essere tutte soddisfatte simultaneamente esiste una parte del piano che esprime líinsieme delle soluzioni possibili. Anche la funzione obiettivo puÚ essere rappresentata da una retta: ponendo, ad esempio, Z = 0 si ha x2 = x1 e per valori di Z diversi da 0 si hanno altre rette parallele alla stessa.

15

La regione delle soluzioni e la FO Eí evidente che la soluzione ottima si ha solo sulla frontiera del poligono delle soluzioni possibili e, in pi˘, tale soluzione ottima Ë (nellíipotesi normale) su uno dei vertici del poligono stesso (OABCD), in caso contrario coincide con gli inÖniti valori dei punti di un lato del poligono. Il metodo analitico del simplesso di fatto calcola la funzione obiettivo nel punto O(0; 0) (Z = 0), prosegue traslando verso il basso la FO (perchÈ si vuole trovare il minimo della FO), calcolando il valore della stessa nel vertice A e nel vertice B. Nel metodo graÖco, invece, si calcola la FO in tutti e cinque i vertici del poligono che delimita le soluzioni ammissibili, scegliendo il vertice che ottimizza la FO. In sostanza il metodo del simplesso ci permette di decidere, trovandoci in un vertice, in quale vertice adiacente muoversi senza esaminare tutti i vertici adiacenti, e ponendosi come elemento discriminante il valore di Z che va migliorato. CiÚ Ë particolarmente utile quando ci si trova in uno spazio a pi˘ di 2 dimensioni e quindi, invece di un poligono, ci si trova di fronte ad un poliedro (le rette sono sostituite da iperpiani).

6

LA DETERMINAZIONE DELLE SOLUZIONI IN EXCEL

Consideriamo sempre líesempio 3. Scriviamo su excel i dati del nostro problema (si veda la Figura 1). Denominiamo i gruppi di celle (formule, 16

gestione nomi) rispettivamente con A (celle B2:C4), b (celle E2:E4) e c_vett (celle B6:C6).

Figura 1: Inserimento dei dati in excel Inseriamo il vettore (colonna) delle incognite7 (x) e impostiamo la funzione obiettivo, data dal prodotto tra il vettore c_vett ed il vettore x8 : min Z = !" c $ !" x In excel il prodotto tra due matrici9 si ottiene utilizzando la formula =matr.prodotto(matrice A; matrice B), preselezionando le celle dimensionalmente necesssarie ad accogliere il risultato e digitanto contemporaneamente i tasti ctrl+shift (")+invio (si veda la Ögura 2). 7 Per inserire il vettore delle incognite selezioniamo le celle necessarie (nellíesempio 2) e vi inseriamo 0: in excel, infatti, non possiamo lasciare le celle vuote. 8 Tale prodotto Ë compatibile, infatti il numero delle colonne della matrice che premoltiplica Ë uguale al numero delle righe della matrice che postmoltiplica. Dimensionalmente il risultato Ë una matrice che ha il numero di righe della matrice che premoltiplica ed il numero delle colo...