Project management

Modelli di Knapsack

Modelli di scelta di investimenti senza vincoli legali

Questa è la forma più semplice di modello di scelta degli investimenti: massimizzare il rendimento totale sotto un (unico) vincolo di budget.

NOTA: nel modello di scelta degli investimenti appena formulato le variabili sono continue.

Come primo esempio di modello di PLI illustriamo proprio la versione del modello di scelta di investimenti con variabili intere (e alcune sue evoluzioni).

Nei contesti

applicativi reali occorre spesso "modellare" le quantità di investimento utilizzando binarie, variabili intere o a seconda del tipo di decisione da prendere. Per il problema di scelta di investimenti si ricorre ad una classe di modelli di PLI noti come (zaino, Modelli di Knapsack bisaccia). Si tratta di una classe molto importante perché i modelli sono: - Concettualmente semplici; - Di vasta applicazione nei problemi reali. Problema: un autostoppista deve riempire il suo zaino scegliendo quali tra n oggetti portare. Egli valuta sia il che peso a1 di ogni oggetto i. l'utilità r1 122. Il problema è dunque quello di riempire lo zaino massimizzando l'utilità totale degli oggetti scelti, ma tenendo anche conto del fatto che non è in grado di sopportare un peso totale dello zaino (che dovrà trasportare) superiore ad un certo peso massimo B. Se prendo gli oggetti con utilità più elevata approccio greedy (portafoglio).sacco a pelo).

Questa soluzione è ammissibile perché: peso totale 1700 e utilità totale 18.

È ottima questa scelta? No.

Se provo a prendere più oggetti con utilità più bassa approccio per tentativi.

Questa soluzione è migliore della precedente, ha una natura diversa: peso totale 1700, utilità totale 25.

Il modo per trovare la soluzione è riconoscere la natura del problema.

Il fatto che la variabile sia binaria non ha intaccato la capacità del modello lineare di attivare o disattivare delle componenti.

Il nome di modello di knapsack deriva dal problema appena illustrato, ma il modello può essere adottato in tutti i contesti in cui si ha il problema di "riempire contenitore" (nelle applicazioni: camion, container, magazzino, in modo ottimo un capitale) di dimensione limitata.

Consideriamo il caso generale di n oggetti, i=1,2,...,n ciascuno caratterizzato dal suo (peso, dimensione, utilità).

ingombro)costo aie da una (valore, profitto, guadagno) e sia dato un costo totale massimo B (peso totale, spazio totale disponibile).utilità ri 123 Modelli di Knapsack per i problemi di Capital Budgeting Modello di Capital Budgeting I modelli di Knapsack sono molto utilizzati per formulare e risolvere problemi di scelta di investimenti. In questo caso il modello viene solitamente chiamato Budgeting. Modello di Capital Problema: una società vuole investire su pacchetti di titoli di cui conosce i rendimenti r e i costi a , i=1,…,n. Con il suoi ibudget disponibile pari a B=16 la società deve decidere quali pacchetti di titoli acquistare per massimizzare il rendimento totale. NOTA: in questo modello si assume che i rendimenti ri, i=1,2,…,n siano tra loro indipendenti, ma questa è una ipotesi poco attendibile per il mercato finanziario. Il modello di Knapsack binario si adatta meglio ai problemi di nei quali un ente finanziatore deve Project Financing decidere.quali progetti finanziare tra n progetti possibili, i=1,2,..,n (indipendenti) sapendo che il finanziamento richiesto per il progetto i è pari ad a, e disponendo di una funzione di valutazione che assegna al progetto i un punteggio (o score) pari a r_i. Consideriamo il caso generale di n progetti, i=1,2,..,n ciascuno caratterizzato dal suo costo a e un punteggio r_i (peso totale, spazio totale disponibile). Il budget totale è B. Si chiama Knapsack proprio per il vincolo di budget che significa "far entrare il più possibile nel budget una selezione di entità, oggetti, investimenti che hanno ciascuno un loro costo unitario". L'accezione delle variabili binarie (0,1) e quindi la possibilità di codificare il SI e il NO, ci permette da un lato di trovare applicabilità nelle situazioni reali con le scelte di tipo SI e NO, dall'altro da un punto di vista numerico ci permette di gestire relazioni con variabili binarie attraverso relazioni.che rimangono lineari. Questo ci condurrà all'introduzione di modelli con variabili e vincoli logici. Questi sono tutti modelli monoperiodo (programmazione oggi per domani così come per la produzione e per la miscelazione). Nei modelli multiperiodo la programmazione si estende a più periodi. Il modello di capital budgeting si estende in quello di Project Financing. Modelli di scelta di investimenti multiperiodo (Project Financing) Project Financing su un solo periodo Il problema può essere generalizzato al caso multiperiodo, cioè quando la scelta riguarda progetti di investimento che si sviluppano su periodi. In questo caso si può continuare a sfruttare la struttura del modello di Knapsack, ma occorre più introdurre nel modello un vincolo di budget per ogni periodo considerato. La natura del problema deve rimanere la stessa. La caratteristica di questo modello è che si moltiplichino i vincoli di budget. Si consideri un arco ditempo composto da T periodi successivi, t=1,2,…,T e per ciascuno si supponga di avere a disposizione un budget (capitale, liquidità). Ogni progetto è caratterizzato dalla sequenza dei suoi flussi monetari netti (sequenza dei suoi flussi di cassa netti uscite al netto) che il progetto genera nei periodi T=1,2,…,T (attualizzate al tempo 0). Se il numero proiettato è positivo delle entrate vuol dire che le uscite sono maggiori delle entrate in quel periodo, se è negativo viceversa, se è nullo c'è un pareggio. Sulla base dei flussi di cassa netti, in corrispondenza dell'ultimo periodo T si può calcolare il rendimento totale netto dell'investimento risultante come somma di tutti i flussi di cassa netti generati da tale investimento nell'arco di tempo 1,2,..,T. N.B. - Numero positivo: uscita netta - Numero negativo: entrata netta Inoltre, l'ipotesi di base è che quello che si calcola.venga attualizzato al tempo iniziale. Non cambiano i termini di ragionamento, semplicemente il tutto si estende a più modelli, mi faccio più idee di progetti alternativi. Il progetto potrebbe essere una combinazione di più sub progetti. IMPORTANTE: se l'investitore sceglie di finanziare un progetto, si impegna oggi ad affrontare i costi che esso genera in TUTTI i periodi da 1 a T. In questa tabella organizzata per progetti e periodi, si può vedere cosa accade ad ogni progetto. Non posso dire che al periodo 1 faccio il progetto 1 e così via, ma se oggi periodo 0 programmo di fare il progetto 1 mi metto davanti la conseguenza che al tempo a 1 avrò un'uscita di 100, al tempo 4 un'entrata di 130 e così via. L'assunzione è che i flussi di cassa netti siano entrate. Ogni progetto ha il suo profilo temporale in termini di flussi di cassa netti e in ogni uscite - periodo un budget. Indichiamo con i=1,2,...,n iprogetti e con una uscita di capitale al tempo t per il progetto i (-a è un'entrata). Il del progetto i al tempo finale T è calcolabile come segue: rendimento totale netto NOTA: si sfrutta il segno della quantità a per indicare quando essa corrisponde a una uscita (segno +) e quando a un'entrata (segno -), ma comunque, nella sostanza, i parametri del modello sono gli stessi del modello di Knapsack, costi e rendimenti. Definiamo le variabili binarie: Primo passo: Definire le variabili quali e quante sono e la loro natura. Se scelgo il progetto si attiverà il parametro â di rendimento nella funzione obiettivo, altrimenti non genererà rendimenti nei vari periodi se non viene scelto. Il progetto va sostenuto con il budget, se viene scelto. Se invece non è un costo, ma ho un rendimento netto allora non è un problema in quanto a sarà negativo. Il problema di sforare il budget si ha se il contributo è positivo (costo).

altrimenti riduce il LHS e compensa un componente che quello stesso periodo per un altro progetto magari è di costo. La scelta delle x intervienetrasversalmente su tutti i vincoli (problema complesso ma matematicamente snello). Il è il seguente:modello di scelta degli investimenti multiperiodo

NOTA: si tratta di un modello di PLI con T vincoli di tipo "knapsack/budget".

Modelli di Project Financing (2 varianti)

Modelli multiperiodo con differimento di fondi

Le variabili trainanti di questo modello che descrivono la scelta dei progetti sono quelle di scelta degli investimenti chestanno sia nei vincoli sia nella funzione obiettivo. Anche nel problema del cash flow matching si è fatto una sorta di differimento. In questo modello se vogliamo differire i fondi bisogna calcolare l'avanzo di budget che bisogna quantificare. Si supponga che, se nel periodo t non viene utilizzato tutto il budget disponibile B, il budget residuo possa essere utilizzatot(Hp:

Possibilità di fondi). Nel periodo successivo differimento. Nel periodo t+1, oltre il budget B si dispone anche del budget residuo del periodo precedente (avanzo budget). Dit+1. Introduciamo le seguenti variabili aggiuntive (continua perché trattasi di un importo monetario): t=1,2,...,TW ≥ 0t. Che per un fissato t misurano il residuo di budget al tempo t. La quantità di w deriva dalla differenza del budget disponibile in quel periodo e il LHS. La differenza è incognita. 127. È lo stesso problema riscritto in forma equivalente standard. Ancora non è stato fatto alcun differimento di fondi. Se vogliamo differire qualcosa, bisogna contabilizzarlo. Per giungere a un modello differente posso pensare di cambiare le ipotesi. Di fronte a questa situazione, si può pensare di mettere incassa la quantità per il per.