Appunti Ottimizzazione Combinatoria Gestionale, Sapienza

1- PROBLEMI DI OC CON FUNZIONE OBIETTIVO LINEARE.

1. Definire i problemi di OC con funzione obiettivo lineare.

2. Spiegare dettagliatamente la relazione tra i problemi di OC con f.o lineare e problemi di

PL01.

3. Definire il problema di “Pianificazione degli investimenti”.

4. Presentare esempi di vincoli di relazioni tra Progetti.

5. Fornire un piccolo esempio di pianificazione degli investimenti e scriverne la formulazione

naturale.

SVOLGIMENTO.

1. Un problema di “Ottimizzazione Combinatoria” ha come obiettivo la

massimizzazione\minimizzazione di una certa funzione obiettivo f(x) soggetta a determinati

vincoli con particolari caratteristiche.

In generale dato un insieme di possibili alternative S, si deve trovare quell’alternativa che

soddisfi determinati requisiti. Per scegliere la S migliore, è necessario però stabilire un

criterio di scelta quantitativo che ci permetta di determinare l’alternativa migliore: tale

criterio è rappresentato da una funzione f(x), dove x è la variabile del problema.

Un modello di Ottimizzazione è composto quindi da un Problema di Decisione (ossia un

problema del tipo max {f(x) : x∈ S}), dove x è la variabile di decisione. La soluzione di tale

∗ ∗

problema è sarà un certo : f( )>f(x) per ogni x in S.

Il termine “Combinatoria” indica invece una condizione sull’insieme delle possibili

alternative S: nei problemi di OC, infatti, si assume che S sia un insieme discreto, e che la

cardinalità di S sia finita: 1< |S|<∞. Questo implica che la cardinalità dell’ insieme delle

Soluzioni Ammissibili per il nostro problema, debba essere necessariamente finita.

E’ quindi possibile determinare una soluzione del problema di decisione, procedendo per

enumerazione completa.

Modelli di OC con F.O. Lineare: è un particolare tipo di modello di OC, dove la funzione

obiettivo è di tipo lineare. Tale modello ha una struttura caratteristica e tipica di seguito

descritta.

Definito un “insieme base” (B), ossia la totalità dei possibili eventi elementari, si

definiscono soluzioni ammissibili S B l’insieme degli eventi che rispettano le condizioni

date e quindi l’insieme delle possibili alternative che possono essere attuate.

Ad ogni possibile evento si associa quindi un costo o vantaggio elementare , parametri

che permettono di determinare la funzione obiettivo o di costo c: S→R, con c(S)=∑ .

}.

Si vuole quindi trovare: min{ c(S): S∈

2. Definiti come PL i problemi di Ottimizzazione Combinatoria aventi funzione obiettivo

lineare, si definiscono PL01 quei problemi aventi tutte le caratteristiche dei PL, ma

caratterizzati da variabili decisionali x, necessariamente binarie.

Qualunque problema di OC con FO lineare può essere riscritto come problema di PL01.

Tale procedimento può avvenire, ad esempio, rappresentando le variabili decisionali sotto

forma di “vettori di incidenza”, ossia quei vettori che, dato B ed una sua soluzione

∈

ammissibile S, hanno componente i-esima pari a 1 se S e hanno componente nulla

altrimenti.

3. Un particolare problema di PL01 è quello di “pianificazione degli investimenti”.

Dato l’insieme degli investimenti I e i relativi indici di redditività , si vuole determinare, tra

i possibili investimenti effettuabili, quell’insieme di investimenti, che garantisca maggiori

guadagni. Tale insieme è vincolato dal budget dell’azienda nei diversi periodi j-esimi : dati

= ( , … ),

il vettore dei flussi di cassa associato all’investimento i-esimo la somma

1 2

dei flussi di cassa deve essere inferiore al budget di periodo.

∈ {0,1}

Le variabili di decisione sono le cui corrisponde o meno l’attivazione del

progetto i-esimo.

4. Inoltre può essere presente una relazione tra i vari progetti… per esempio l’attuazione di

un progetto i-esimo, è subordinata alla realizzazione di un progetto j-esimo..

ESEMPI:  < – se l’investimento j-esimo è attivato, i non può essere svolto.

 ≤ – i può essere attivato solo se j viene attivato.

 + < 1 – solo uno degli investimenti può essere attivato.

 = (− + 1) – i è svolto se j non viene svolto.

 ≤ + + (1 − ) – i può essere svolto o se j è attivato o se h è

ℎ

attivato o se k non è attivato (con il diviso 3 vale l’ ”e”).

5. Esempio con 3 investimenti e 7 periodi.

Flussi di cassa :

1 2 3 4 5 6 7

A 10 10 -12 10 -20 0 0

B -3 5 3 -20 10 -20 0

C 5 5 5 0 -5 -10 -20

:

Budget dei vari periodi b={11,20,20,20,20,0,0}.

+ +

max 1 1 2 2 3 3

10 − 3 + 5 ≤ 11 10 + 5 + 5 ≤ 20

1 2 3 1 2 3

−12 + 3 + 5 ≤ 20 10 − 20 + 0 ≤ 20

1 2 3 1 2 3

−20 + 10 − 5 ≤ 20 0 − 20 − 10 ≤ 0 0 + 0 − 20 ≤ 0

1 2 3 1 2 3 1 2 3

{0,1},

∈ = {1,2,3}

2- CLASSI DI COMPLESSITA’ P ED NP.

1. Introdurre i concetti relativi alla complessità computazionale.

2. Definire le classi di Complessità P e NP.

3. Spiegare le possibili relazioni tra le due classi.

SVOLGIMENTO.

1. Dato un problema di ottimizzazione combinatoria, si definiscono i relativi insiemi delle

Istanze “I” e delle soluzioni ammissibili “S”: tali insiemi determinano vincoli e variabili del

problema, la cui funzione obiettivo si può quindi definire come F(I).

Un modo per risolvere il problema, senza ricorrere all’enumerazione completa, è quello di

determinare un algoritmo che permetta di trovare una soluzione ottima per il problema di

massimizzazione o minimizzazione.

Tale algoritmo deve avere due caratteristiche fondamentali: deve essere corretto ed

efficiente.

Con “corretto” si intende la capacità propria dell’algoritmo di risolvere un dato problema.

L’efficienza ha come benchmark lo spazio e il tempo.

Per spazio si intendono il numero di bit utilizzati dall’algoritmo al fine di determinare una

soluzione di F(I); per tempo si intende invece il numero di passi che la macchina compie per

trovare la soluzione. La determinazione del numero di passi, e quindi il loro conteggio,

dipende dal modello di macchina usata: per esempio, nella Random Access Machine, il

conteggio si incrementa di un’unità ogni volta che viene compiuta un “operazione

elementare” (chiamata di funzioni, assegnazione di nomi a variabili, somma, divisione etc.).

Il numero di passi eseguiti dalla macchina determina il “Tempo di esecuzione”.

Maggiore sarà il tempo richiesto dalla macchina per lo svolgimento completo

dell’algoritmo, maggiore sarà la “complessità” dell’algoritmo stesso.

In termini quantitativi è possibile definire la complessità come il numero di passi necessari

per trovare la soluzione di un’istanza di dimensione SIZE(I), dove SIZE(I) corrisponde al

numero di celle necessario per rappresentare I. Essa sarà dunque una funzione avente

come variabile proprio la dimensione delle istanze – c(SIZE(I)).

Poiché non è nota a priori SIZE(I), e nemmeno la probabilità che si presenti una certa

istanza, si studiano due casi particolari: il “caso migliore” B(d) ed il “caso peggiore” W(d).

Il primo è di scarso interesse e si presenta rare volte.

Il secondo invece corrisponde ad un caso patologico, in presenza del quale la macchina

deve essere comunque in grado di risolvere il problema in tempi definiti.

Per semplificare la trattazione si studiano gli “Upper Bound”, ossia gli ordini, di SIZE(I).

Si dice che la “complessità nel caso peggiore” è O[g(SIZE(I))] se e solo se g(SIZE(I)) è Upper

Bound di W(SIZE(I)). A seconda del fattore all’interno di O() si definiscono due tipi di

complessità.



Complessità Polinomiale - O(SIZE() )

 Complessità Esponenziale – altrimenti

I problemi del primo tipo sono facilmente risolvibili, i secondi richiedono procedimenti e

tempi più lunghi.

2. Per ampliare la trattazione, senza limitarci quindi al modello della Random Access Machine,

si introduce il concetto di Macchina di Turing: tale macchina è composta da componenti

ideali:

o NASTRO: insieme infinito di celle (ad ognuna delle quali corrisponde un simbolo).

o TESTINA: strumento che legge o scrive sul Nastro.

o PROGRAMMA: uno strumento che dice alla macchina cosa fare per ogni stato e

simbolo in input.

o STATO: appartiene all’insieme dei possibili stati della macchina.

Essa può essere di due tipi diversi:

- Deterministica.

- Non Deterministica.

La prima, per ogni valore in ingresso, segue un comportamento predeterminato,

restituendo un certo output; la seconda dato un input, può scegliere tra divere opzioni, e

quindi restituire tipi diversi di output. In relazione a tale differenziazione si definiscono 3

classi di problemi:

o P: problemi Polinomiali risolvibili con MdT Deterministica.

o NP: problemi Polinomiali risolvibili con MdT non Deterministica

o ExpT: problemi Esponenziali risolvibili con MdT Deterministica.

≥

Un problema che abbia complessità si dice NP-Hard, un problema che sia NP e che

rientri in NP si dice NP-Completo.

3. Tra le 3 classi vige un regime di inclusione: è chiaro che un problema P, può essere risolto

anche con una MdT non Deterministica, non è scontato il contrario. Uno dei Millenium

Problems riguarda proprio questo aspetto: è possibile dire che P≡NP?

Tale fatto è di notevole importanza dal momento che molti problemi comuni (O.C. e PL01)

si trovano nell’insieme NP-P, e sono oggi risolvibili solo in tempo esponenziale. La PL

appartiene invece alla classe P.

3- FORMULAZIONI E RILASSAMENTO LINEARE.

1. Formulazione di un Problema di PL01.

2. Definizione di Rilassamento Lineare.

3. Definizione di Lower Bound e di Gap.

4. Definizione di Qualità di Formulazione.

5. Definizione di Formulazione Ottima.

6. Definizione Rilassamento della Formulazione Ottima.

7. Fornire un esempio numerico di Formulazione Naturale e di Formulazione Ottima per un

problema di Pianificazione degli Investimenti in un singolo periodo.

SVOLGIMENTO:

,

1. Un Problema di PL01 è caratterizzato da una funzione obiettivo lineare che si vuole

massimizzare o minimizzare, all’interno di determinati vincoli S, inoltre le variabili di

{0,1}

decisione x, sono vincolate ad assumere un valore binario x∈ .

: ≤ }:

Si definisce Formulazione di PL01 il nuovo insieme P= {x∈ la caratteristica

∩ {0,1} =

dell’insieme P è quella di dover soddisfare la seguente proprietà

Si ottiene così la seguente relazione:

∗ ∗

{0,1}

min{ : ∈ } = min { : ∈ ∩ = = ≥ min{ : ∈ } = ()

2. Un problema di PL01 potrebbe rientrare nella classe NP, e non sarebbe facile da risolvere.

Per poter semplificare i calcoli si applica quindi un Rilassamento Lineare sul problema di

PL01, ossia vengono eliminati i vincoli sulle variabili di decisione x, che può assumere valori

reali, non necessariamente binari. In tal modo si ci riconduce ad un problema di PL e quindi

ad una complessità di tipo P. ≤

3. Dato un insieme S, un Lower Bound (limitazione inferiore) è un valore di tutti gli

elementi di S, un Upper Bound si definisce specularmente. Nota una soluzione ammissibile

, il Lower Bound ci fornisce una certificazione di qualità relativa a tale soluzione.

Infatti studiando il “gap” che si instaura tra la soluzione ammissibile ed il LB, ossia la

differenza tra i due valori, si può avere una misura dell’errore che si sta commettendo

approssimando con .

Per migliorare il nostro algoritmo ci possono porre due distinti obiettivi:

o Miglioramento di LB

o

Miglioramento di

4. Minore sarà la distanza tra il LB(P) e una data soluzione ammissibile e maggiore sarà la

qualità della formulazione. Infatti la soluzione ottima del problema originario di PL01 si

trova all’interno dei due valori che stiamo rapportando. Minore sarà la loro distanza,

minore sarà l’errore che stiamo commettendo nella ricerca del valore ottimo.

Per rapportare due o più formulazioni si deve però determinare un criterio univoco che

non dipenda dalla funzione obiettivo. Tale criterio afferma come minore sarà la dimensione

del poliedro che applichiamo come limite sulla funzione obiettivo, e minore sarà il gap di

quella formulazione: ⊆

P è migliore di P -

1 2 1 2

5. Stabilito il criterio di qualità, è chiaro come una formulazione ottima possa essere definita

come tale, se è inclusa in ogni altra possibile formulazione. Stiamo quindi cercando quel

poliedro che sia contenuto in ogni altro possibile poliedro, in termini matematici:

= () ⊆ , ∀

Se la Formulazione Ottima rispetta tali requisiti, è chiaro che l’insieme S, corrisponde con

l’insieme dei vertici di Ma dal momento che la soluzione ottima su si trova in

corrispondenza dei vertici, è chiaro che la soluzione della Formulazione Ottima, sarà

proprio uguale alla soluzione del problema di PL01.

6. Purtroppo però non è immediata l’individuazione della formulazione ottima, talvolta è

= { ∈ : ≤ }

possibile però ricavarne un rilassamento, ovvero un poliedro che

abbia le seguenti caratteristiche:

o Il poliedro P è una formulazione di S.

o ≤

Il sistema è costituito da un insieme di famiglie di disequazioni

≤ .

appartenenti al sistema

Ciascun rilassamento produce un Lower Bound della Formulazione Ottima.

7. FORMULAZIONE NATURALE FORMULAZIONE OTTIMA

− − − −

1 1 2 2 1 1 2 2

4 + 2 ≤ 5 + ≤ 1

1 2 1 2

≤ 1 ≥ 0 ≤ 1 ≥ 0

1 2 1 2

4- ALGORITMI DI BRANCH & BOUND.

1. Spiegare che tipo di problemi risolve.

2. Introdurre i concetti di Branching e Bounding.

3. Fornire lo schema dell’algoritmo di Branch & Bound.

4. Commentare e motivare lo schema fornito.

5. Illustrare quelli scelte devono essere effettuate all’interno di tale schema e possibili criteri di

scelta.

SVOLGIMENTO:

1. L’algoritmo di Branch & Bound risolve problemi di PL01 (PLI).

Dato un problema di Programmazione Lineare Intera, o Binaria, si vuole trovare

∗

numericamente, nell’insieme ammissibile S, l’ottimo :

{min

∈

Dove S corrisponde all’insieme dei punti interi (o binari) all’interno di un poliedro P (che

corrisponde alla formulazione scelta).

{ ∈

{0,1})

∈ ( ∈

2. Dato che il numero di punti ammissibili è finito si poterebbe procedere per enumerazione

completa. Purtroppo però la cardinalità dell’insieme delle soluzioni ammissibili potrebbe

essere molto grande, e potremmo avere a che fare con un problema del tipo NP.

Si potrebbe

o cambiare il tipo di enumerazione.

o provare a migliorare la formulazione.

o approssimare o per difetto e per eccesso la soluzione in modo da ridurre il gap.

Non è detto però che arrotondando all’intero più vicino l’ottimo di un problema di PL, si

ottenga un valore ammissibile oppure ottimo per il rispettivo problema PL01.

Si cerca quindi di cambiare il tipo di enumerazione: si utilizzerà un approccio di soluzione

basato sull’enumerazione implicita. Le idee di base di tale tipo di enumerazione sono le

seguenti:

 Partizionamento dell’insieme ammissibile in insiemi più facili (sotto-problemi).

 Procurarsi una soluzione ammissibile per il singolo sotto-problema (ottimo

corrente).

 Continuare a risolvere i restanti sotto-problemi, aggiornando ogni volta l’ottimo

corrente, se necessario.

Tale concetto base si applica quindi mettendo in pratica 2 operazioni fondamentali:



BRANCHING – Tecniche per generare sotto-problemi .

Si vogliono generare sotto-problemi sufficientemente semplici, ma non troppo numerosi.

 BOUNDING – Tecniche per valutare quanto di meglio potrei ottenere su un sotto-

insieme .

Si cerca un compromesso tra velocità di calcolo e accuratezza del Lower Bound.

Il processo di Branching si applica, nella maggior parte dei casi, utilizzando il metodo del

“binario agli interi più vicino”: se risolvendo il rilassamento lineare si determina una

soluzione con componenti non intere (frazionarie), per esempio preso il vettore si

=

determina una componente con valore frazionario ( ), questo implica che il

sotto-problema non era sufficientemente facile.

,

Si procede partizionando in due sotto-problemi distinti ch