Corso Completo Ricerca Operativa 2

Ricerca Operativa 2

2018-2019

Introduzione alla Programmazione Lineare a Numeri Interi (PLI):

• Relazione fra PL e PLI
• Formulazioni equivalenti
• Rilassamenti
• Matrici totalmente unimodulari
• Tecniche standard per la formulazione di problemi di PLI.

Formulazione di tipici problemi di ottimizzazione:

• Localizzazione di impianti
• Scelta di investimenti
• Sequenziamento di attività
• Ottimizzazione su reti
• Trasporti
• Set covering
• Set Partitioning
• Set Packing
• Turni del personale.

Soluzione esatta di problemi di Programmazione Lineare a numeri interi:

• Branch and bound
• Il problema di knapsack
• Piani di taglio.

Metodi di Programmazione Dinamica (PD):

• Algoritmo di PD per il knapsack capacitat
• Algoritmo di PD per il knapsack intero non capacitat.

Ottimizzazione su grafi:

• Matching
• Minimo vertex cover
• Massimo Flusso
• Massimo stabile
• Grafi euleriani e grafi bipartiti.

Utilizzo di un software commerciale per la soluzione di problemi di programmazione matematica.

Testi di riferimento:

[1] M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995. (Cap. 2, 5, parte del 6 e del 7).

[2] R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993. (pg. 189-191, 473-475, 494-496)

[3] Dispense fornite dal docente e/o disponibili sul web.

2 Ottobre 2018

PROCESSO DECISIONALE

1. Definizione del problema attraverso una descrizione formale di un contesto reale qualsiasi.
2. Osservazione e raccolta dei dati: che variabili include ogni task? A che tipo? Vi è determinismo o stocasticità? (nel corso assumiamo questo passo già effettuato)
3. Formulazione di un modello: va trovata una rappresentazione rigorosa, attraverso PLI o grafo.
4. Verifica della validità, è la parte fondamentale nella realtà.
5. Decisione: va trovata una soluzione, è un passo matematico che sfrutta algoritmi risolutivi.
6. Presentazione dei risultati, importante ma non trattato qui.
7. Implementazione della decisione.

Programmazione lineare mista PLI

PLI GENERICO

• min C^Tx
• s.a. Ax > b
• x > 0
• x INTERO

È accavabile la forma standard.

• ⇒ PL mista se alcune variabili sono intere
• ⇒ PLI (pura) tutte le variabili sono intere
• ⇒ PI01 binaria se tutte le variabili sono binarie

F. OBIETTIVO: min pl

ESEMPI

1. PL MISTA: una compagnia di trasporti ha vetture che richiedono delle risorse → UMANE (variabili intere)MATERIALI (variabili continue)
2. PIL PURA: ad esempio quante unità di beni vanno prodotte. I beni non possono esser prodotti in metà
3. PL01: 0 / 1 → NO/SÌ. Va distribuita la sorveglianza in strada.Vado a numerare gli incroci x_i; i = 0...nPOLIZIOTTO PRESENTE x_i=1POLIZIOTTO ASSENTE x_i=0

Ci si pone sotto le ipotesi:

• A, b interi (qualora non lo fosse si trova una costante moltiplicativa che li renda interi)
• P: {x > 0 / Ax > b} = il poliedro limitato non vuoto delle soluzioni ammissibili
• PER UN PLI X = P ∩ ℤⁿ con n dimensioni del poliedro PSi avrà di conseguenza un numero limitato di soluzioni.

La ricerca dell'ottimo con approccio enumerativo è possibile ma non è efficiente nella pratica.

Rilassamento lineare

Vi sono due conversioni importanti tra problemi di PL e PLI.

Il rilassamento lineare è ottenuto rimuovendo il vincolo di interezza delle x.

Ciò equivale all'allargamento del dominio di ammissibilità delle soluzioni, da un insieme discreto a quello continuo

z_2PL è il valore du cui ottimo del rilassamento linearez_2PL è il valore du cui ottimo del problema intero

Le funzioni obiettivo sono le stesse ma i valori appartengono a degli insiemi diversi. Essendo xPL = zPL ≤ zPLI, ciò vuol dire che la soluzione ottima del rilassamento è un lower bound per la soluzione ottima del problema intero.

DATO UN PROBLEMA DI OTTIMIZZAZIONE QUALSIASI CON F.O. DA MINIMIZZARE

min f(x), si dice rilassamento di min g(x) ∈ R

Tale che A⪯B⪯ e f(x)⪯g(x) ∀ x∈A

Se la soluzione ottima x* del PL è intera, allora è ottima anche per il problema di partenza PLI.

Dimostrazione:c^Tx_∗ = z_PL ≤ z_PLI e se x_∗^PL è intera = x_∗^PL ∈ Xne segue: 2PL ≤ Cx^T x ∀ x∈Xquindi 2PL ≤ Cx^Tx = 2PL

Per il rilassamento lineare non è lecito risolvere attraverso simplesso e poi anottornare eventualmente.

ESEMPIO: min -x - y

Annotando la componente x del vettore x_PL se esce fuori dal dominio in ogni caso

Unione di vincoli (Big M)

Caso in cui x deve soddisfare Ax ≥ b e almeno uno tra gli altri vincoli dati nel PL.

a^Tx ≤ f → d^Tx ≤ g

→ si introduce la variabile Big M costante sufficientemente grande che non viene mai raggiunta. Dipende dai dati del problema.

a^Tx ≤ M

d^Tx ≤ M

"almeno una delle due deve valere" y = 1 se vincolo 1 soddisfatto y = 0 se vincolo 2 soddisfatto

Nel caso ci si trovi nell'intersezione dei vincoli, la variabile y e' irrilevante quale valore assume.

a^Tx = f + M (1-y)d^Tx = g + M y

Esempio Big M: Scheduling con vincoli esclusivi

1 macchinan lavori di cui ognuno non può essere interrotto e deve essere eseguito uno alla volta.ti istante inizio jobPi tempo di processamento di un job.

A questo punto è un problema di sequenziamento: V coppia (i,j) di lavori va stabilito quale ci sia prima

se i precede j → t_j ≥ t_i + p_i istante di completamentose j precede i → t_i ≥ t_j + p_j

1 macchina → v_ij = {1 se i prima di j 0 altrimenti}n(n-1)―――――――――― variabili2introdotte

Formulazione finale:∀ i, j : { t_i ≤ t_j - p_i + M (1-y_ij) t_j ≤ t_i - p_j + M y_ij }

Nota: La costante Big M va scelta ad esempio maggiore del tempo di processamento di tutti i task, necessario a portare a termine tutte le lavorazioni.

2 VARIANTI SUL PROBLEMA DEI FACCHINI

1. VARIANTE SOCIALISTA: le concova bilanciato tra tutti i facchini

2. VARIANTE LIBERISTA: il carico va bilanciato solo tra i facchini con un carico.

Il carico ora va bilanciato minimizzando la differenza tra il facchino più carico e facchino meno carico.

1. Introduco 2 nuove variabili
• u: facchino più carico
• l: facchino meno carico

m.m. (U-L)

1. ∑_i=1^m a_ji ≥ 1    ∀ sacco j
2. ∑_j=1ⁿ p_j a_ji ≤ P    ∀ facchino i
3. ∑_j=1ⁿ v_j a_ji ≤ V   
4. ∑_j=1ⁿ p_j a_ji ≤ U    ∀ facchino i
5. ∑_j=1ⁿ p_j a_ji ≥ L    ∀ facchino i
6. a_ji ∈ {0, 1} intero

2. Usamo introducete limitazioni sull’unicolo n°5.

m.m. (U-L)

1. (1)
2. (2)
3. (3)
4. (4)
5. (5’)
   1. Definisco y_j:≥ a_ji    ∀ i ∀ j
   2. ∑_j=1^m p_j a_ji ≥ L - P(1-y_i)
6. (6)—> a_ji y_i ∈ {0,1} intee

U, L ≥ θ