modelli di programmazione lineare - intranet...
TRANSCRIPT
![Page 1: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/1.jpg)
Modelli di Programmazione Lineare
PRTLC - Modelli
![Page 2: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/2.jpg)
Schema delle esercitazioni
◮ Come ricavare la soluzione ottima◮ Modelli◮ Solver
◮ Come ricavare una stima dell’ottimo◮ Rilassamento continuo - generazione di colonne◮ Rilassamento Lagrangiano e surrogato
◮ Come ricavare una soluzione ammissibile◮ Euristiche greedy◮ Euristiche di ricerca locale
![Page 3: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/3.jpg)
Flusso massimo: descrizione
Dati
◮ Un grafo orientato G = (N ,A).
◮ La capacita uij di ogni arco.
◮ Una coppia di nodi sorgente e destinazione, s, t.
Problema
Inviare la massima quantita di flusso dalla sorgente alla destinazionesenza violare le capacita degli archi
![Page 4: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/4.jpg)
Struttura del modello matematico
◮ I dati −→ i parametri
◮ Le decisioni (quanto flusso passa su ogni arco) −→ le variabili:◮ xij ≥ 0: flusso su ogni arco◮ v ≥ 0: flusso totale da s a t
◮ L’obiettivo (inviare il massimo flusso) −→ funzione obiettivo
◮ I requisiti che una soluzione deve soddisfare (non violare la capacita)−→ i vincoli che le variabili devono soddisfare
Programmazione Lineare
Funzione obiettivo e vincoli sono funzioni lineari
![Page 5: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/5.jpg)
Modello
Dati
◮ Insieme dei nodi
◮ insieme degli archi
◮ capacita sugli archi
Funzione obiettivo
max v
Vincolo di capacita
xij ≤ uij ∀(i , j) ∈ A
![Page 6: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/6.jpg)
Modello
Vincolo di bilanciamento
∑
k|(i ,k)∈A
xik −∑
j|(j,i)∈A
xji =
v i = s ,
−v i = t,
0 altrimenti.
∀i ∈ N
Dominio delle variabili
xij ≥ 0 ∀(i , j) ∈ A
v ≥ 0
![Page 7: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/7.jpg)
Flusso di costo minimo: descrizione
Dati
◮ Un grafo orientato G = (N ,A).
◮ La capacita uij , il costo cij , e il flusso minimo lij di ogni arco.
◮ Il bilancio associato ad ogni nodo i ∈ N , bi◮ bi > 0 il nodo offre del flusso alla rete (nodo sorgente)◮ bi < 0 il nodo richiede flusso dalla rete (nodo pozzo)◮ bi = 0 il nodo non richiede ne’ offre flusso (nodo di transito).
Problema
Inviare il flusso dalle sorgenti alle destinazioni a costo minimo, senzaviolare le capacita degli archi e soddisfacendo i flussi minimi su ogni arco.
![Page 8: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/8.jpg)
Modello
Variabili e dominio
xij ≥ 0 ∀(i , j) ∈ A : flusso sull’arco (i , j) ∈ A
Funzione obiettivo
min∑
(i ,j)∈A
cijxij
![Page 9: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/9.jpg)
Modello
Vincoli
◮ bilanciamento ai nodi:
∑
(i ,j)∈A
xij −∑
(j,i)∈A
xji = bi , ∀i ∈ N
◮ capacita degli archi:
xij ≤ uij , ∀(i , j) ∈ A
◮ limite inferiore di flusso sugli archi:
xij ≥ lij , ∀(i , j) ∈ A
![Page 10: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/10.jpg)
Variante
Vincolo modificato
Viene modificato il vincolo sul flusso inferiore richiedendo che se l’arco(i , j) viene usato il flusso instradato sia almeno pari a lij . A differenza chenel caso precedente, pero, viene lasciata la possibilita di non usare l’arco.
![Page 11: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/11.jpg)
Modello
Variabili e dominio
yij = 1 se sull’arco (i , j) ∈ A passa un flusso non nullo, cioe se l’arco eusato
yij ∈ {0, 1} ∀(i , j) ∈ A
Vincoli
xij ≤ uijyij , ∀(i , j) ∈ A
xij ≥ lijyij , ∀(i , j) ∈ A
![Page 12: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/12.jpg)
Cammino minimo
Problema
Trovare, dato un grafo G = (N ,A), con costi cij sugli archi, un nodosorgente s e un nodo destinazione t, il percorso di costo minimo tra s e t.
![Page 13: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/13.jpg)
Modello
Variabili
xij = 1 se il cammino passa per arco (i , j)
xij ∈ {0, 1} ∀(i , j) ∈ A
Funzione obiettivo
min∑
(i ,j)∈A
cijxij
![Page 14: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/14.jpg)
Modello
Vincoli
bilanciamento ai nodi:
∑
(i ,j)∈A
xij −∑
(j,i)∈A
xji =
1 se i = s
−1 se i = t
0 altrimenti (i 6= s, t)
∀i ∈ N
![Page 15: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/15.jpg)
Osservazione
Dominio
E necessario imporre xij ∈ {0, 1} o e sufficiente imporre xij ≥ 0?
![Page 16: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/16.jpg)
Albero dei cammino minimi
Problema
Trovare, dato un grafo G = (N ,A), con costi cij sugli archi, e un nodosorgente s, il percorso di costo minimo tra s e tutti gli altri nodi.
![Page 17: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/17.jpg)
Modello
Variabili
xij ≥ 0 ∀(i , j) ∈ A : numero di cammini che usano l’arco (flussosull’arco)
Funzione obiettivo
min∑
(i ,j)∈A
cijxij
![Page 18: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/18.jpg)
Modello
Vincoli
bilanciamento ai nodi:
∑
(i ,j)∈A
xij −∑
(j,i)∈A
xji =
{
|N | − 1 se i = s
−1 altrimenti∀i ∈ N
![Page 19: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/19.jpg)
Sottografo connesso
Problema
Dato un grafo non orientato G = (N ,E ), con costi we sui lati, trovarel’insieme dei lati che connette tutti i nodi del grafo a costo minimo.
![Page 20: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/20.jpg)
Modello
Variabili
◮ xe ∈ {0, 1} ∀e ∈ E : xe = 1 se il lato appartiene all’albero
Funzione obiettivo
min∑
e∈E
wexe
![Page 21: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/21.jpg)
Modello
Vincoli
connettivita:∑
e∈δ(S)
xe ≥ 1 ∀S ⊂ N : 1 ≤ |S | ≤ |N | − 1
S sottoinsieme dei nodi del grafoδ(S) insieme dei lati che hanno un estremo in S e l’altro fuori da S .
![Page 22: Modelli di Programmazione Lineare - Intranet DEIBhome.deib.polimi.it/carello/PRTLC/slide/ModelliRipasso.pdf · Schema delle esercitazioni Come ricavare la soluzione ottima Modelli](https://reader031.vdocumenti.com/reader031/viewer/2022022721/5c67423809d3f2bb148b6866/html5/thumbnails/22.jpg)
Osservazioni
Osservazioni
◮ Se we ≥ 0 ∀ e ∈ E?
◮ non ci sono cicli nella soluzione◮ la soluzione contiene |N| − 1 lati
=⇒ la soluzione e un albero
◮ Se we puo anche essere negativo e vogliamo un albero?◮ aggiungiamo il vincolo
∑
e∈E
xe = |N| − 1