Ottimizzazione combinatoria e
programmazione matematica
Università Roma Tre – Dipartimento di Matematica e Fisica IN440 – Ottimizzazione Combinatoria
Prof. Marco Liverani
Famiglie di problemi
Possiamo distinguere diverse famiglie di problemi sulla base del tipo di soluzione richiesta:
§
Problemi di decisione o di esistenza: si richiede di decidere se una soluzione esiste; la risposta è binaria, di tipo «sì/no», «vero/falso», «0/1»•
Esempi: Esiste uno zero della funzione f(x) nell’intervallo (a, b)? Esiste un cammino tra i vertici u e v del grafo G?•
Nota: non si richiede di esibire una soluzione, ma soltanto di decidere se almeno una soluzione esiste§
Problemi di ricerca: si richiede di esibire una soluzione del problema•
Esempi: Calcolare uno zero della funzione f(x) nell’intervallo (a, b). Trovare un cammino tra i vertici u e v del grafo G•
Nota: risolvere un problema di ricerca equivale a risolvere anche il problema di decisione corrispondente§
Problemi di enumerazione: si richiede di calcolare tutte le soluzioni del problema•
Esempi: Calcolare tutti gli zeri della funzione f(x) nell’intervallo (a, b). Trovare tutti i cammini tra i vertici u e v del grafo G•
Nota: risolvere un problema di enumerazione equivale a risolvere anche il problema di ricerca corrispondenteProblemi di ottimizzazione
§
I problemi di ottimizzazione richiedono di calcolare, se esiste, una soluzione tra quelle che rendono minimo o massimo (a seconda del problema) un determinato criterio di scelta della soluzione§
Il criterio di scelta è espresso mediante una funzione f(x), detta funzione obiettivo del problema:ottimizzare la funzione obiettivo significa trovare una soluzione x* del problema, la soluzione ottima, che renda minima o massima la funzione obiettivo
§
Formalmente un’istanza di un problema di ottimizzazione è definita mediante una coppia (A, f), dove A è l’insieme delle soluzioni ammissibili per il problema in esame e f: A⟶ℝ è la funzione obiettivo che si deve ottimizzare§
Si chiede di trovare i valori x* ∈ A tali che f(x*) ≤ f(x) per ogni x ∈ A (problema di minimizzazione)§
Tali valori di x* sono le soluzioni ottime globali; se invece f(x*) ≤ f(x) solo per i valori di x in un intorno di x*, allora x* è una soluzione ottima locale§
L’insieme delle soluzioni ammissibili è un sottoinsieme dello spazio delle soluzioni e in genere viene definito attraverso un insieme di vincoli che delimitano e circoscrivono l’insieme entro cui possono assumere i valori le variabili del problemaProblemi di programmazione matematica
§
Nei problemi di programmazione matematica i vincoli che circoscrivono l’insieme A delle soluzioni ammissibili, sono espressi attraverso un insieme di equazioni e disequazioni (anche molto numerose)§
Problema di programmazione matematica:minimizzare f(x) per x tale che gi(x) ≥ 0 per i = 1, 2, ..., m hj(x) = 0 per j = 1, 2, ..., p
§
dove le funzioni gi(x) e hj(x) costituiscono i vincoli del problemaCombinazione convessa
§
Dati due punti x, y ∈ ℝn una combinazione convessa di x e y è un punto z = 𝜆x + (1 – 𝜆)y, con 𝜆 ∈ ℝ e 0 ≤ 𝜆 ≤ 1§
Un insieme S ⊆ ℝn è convesso se contiene qualsiasi combinazione convessa di elementi di S:x, y ∈ S ⇒ 𝜆x + (1 – 𝜆)y ∈ S
§
Prop.: Se S1, ..., Sk sono insiemi convessi, allora anche è convessoS’ non convesso S convesso
<latexit sha1_base64="9xkoc0ec17oU18Qy7y6/Cf3G7AY=">AAACDnicbVDLSsNAFJ34rPUVdelmsAiuSiKiboSiG5cV7QPaGCbTSTt0MgkzN8US+g9+gFv9BHfi1l/wC/wNp20WtvXAhcM593IuJ0gE1+A439bS8srq2npho7i5tb2za+/t13WcKspqNBaxagZEM8ElqwEHwZqJYiQKBGsE/Zux3xgwpXksH2CYMC8iXclDTgkYybftNiWJn/Erd/TYx/c+9+2SU3YmwIvEzUkJ5aj69k+7E9M0YhKoIFq3XCcBLyMKOBVsVGynmiWE9kmXtQyVJGLayyafj/CxUTo4jJUZCXii/r3ISKT1MArMZkSgp+e9sfif10ohvPQyLpMUmKTToDAVGGI8rgF3uGIUxNAQQhU3v2LaI4pQMGXNpCRaEGBPo6Jpxp3vYZHUT8vuedm9OytVrvOOCugQHaET5KILVEG3qIpqiKIBekGv6M16tt6tD+tzurpk5TcHaAbW1y8P4ZwJ</latexit>
\ki=1Si
Programmazione convessa
§
Una funzione f: S ⟶ ℝ è convessa in S convesso se,per ogni x, y ∈ S, risulta f(𝜆x + (1 – 𝜆)y) ≤ 𝜆f(x) + (1 – 𝜆) f(y)
§
Prop.: Sia f(x) una funzione convessa nell’insieme convesso S; allora per ogni t ∈ ℝ l’insiemeSt = {x ∈ S: f(x) ≤ t} è convesso
§
Un problema di ottimizzazione formulato come un problema di programmazione matematicaminimizzare f(x) per x tale che gi(x) ≥ 0 per i = 1, 2, ..., m hj(x) = 0 per j = 1, 2, ..., p
§
è un problema di programmazione convessa se•
la funzione obiettivo f(x) è convessa•
le funzioni gi(x) sono concave (–gi(x) sono convesse)•
le funzioni hj(x) sono linearix y
f(x)
λf(x) + (1-λ)f(y)
f(y)
f(λx + (1-λ)y)
§
Prop.: In un problema di programmazione convessa ogni soluzione ottima locale è anche una soluzione ottima globaleProgrammazione lineare
§
Un problema di programmazione matematica in cui la funzione obiettivo e i vincoli delproblema sono espressi con funzioni lineari, è un problema di programmazione lineare (LP)
§
Se la funzione obiettivo è lineare, allora i suoi punti di minimo e di massimo si trovano sicuramente sulla frontiera dell’insieme A delle soluzioni ammissibili§
George Danzig nel 1947 propose un metodo generale per la risoluzione di problemi di programmazione lineare, noto come metodo del simplesso, basandosi su tale osservazione•
L’algoritmo di Dantzig opera su un simplesso, ossia un politopo di n dimensioni con n + 1 vertici (nel piano, lo spazio di dimensione n = 2, è un triangolo, nello spazio di dimensione n = 3 un simplesso è un tetraedro, ecc.)•
In un problema di programmazione lineare l’insieme A delle soluzioni ammissibili è un simplesso•
Il metodo del simplesso individua la soluzione ottima del problema di programmazione lineare, percorrendo gli spigoli del politopo di n dimensioni (il simplesso): la soluzione ottima si troverà su uno dei verticiGeorge Dantzig (1914 – 2005)
Programmazione Lineare Intera e Ottimizzazione Combinatoria
§
Nei problemi di programmazione lineare intera (PLI) alcune delle variabili del problema sono vincolate ad assumere valori interi•
in questo modo si riducono drasticamente i punti dello spazio delle soluzioni ammissibili•
se nel problema PLI si elimina il «vincolo di integrità» (le variabili possono essere tutte a valori reali, non solo interi) si ottiene un problema di PL detto rilassamento continuo del problema PLI corrispondete•
se il rilassamento continuo ha le stesse soluzioni del problema PLI corrispondente, allora si dice che gode della proprietà di integralità§
Nei problemi di programmazione lineare intera 0-1 alcune variabili possono assumere solo i valori nell’insieme {0, 1}§
Se tutte le variabili del problema di programmazione lineare sono vincolate ad assumere solo valori interi, il problema è di ottimizzazione combinatoriaProgrammazione Lineare: alcuni esempi
§
Problema della bisaccia (knapsack problem): abbiamo un sacco (una «bisaccia») che può reggere fino ad un peso P; dobbiamo usare il sacco per trasportare un certo numero di oggetti di peso diversoselezionandoli da una collezione di n elementi; ogni oggetto ha un costo/valore ci e un peso pi
§
Problema di ottimizzazione: voglio riempire il sacco senza superare la sua capacità P e massimizzando il valore degli oggetti selezionati§
Alle variabili xi ∈ {0, 1} (i = 1, ..., n) assegniamo il valore xi = 1 se l’oggetto i viene scelto e xi = 0 altrimenti§
Una soluzione del problema è il vettore x = (x1, ..., xn) ∈ {0, 1}n con cui può essere identificato il contenuto della bisaccia§
Possiamo formalizzare il problema di ottimizzazione come un problema di programmazione lineare:<latexit sha1_base64="1ubk2FDAfEXEzIeOJP+BbT+dyno=">AAACrHichVHbbhMxEPUutxJu4fLGy4gKqUhRtNsHQEiVKooEj0Fq2krxsvI6s6lV27vYsyjpsnwQD/wPX8Bv4CR9IC2CI1k6OjPHY58paq08JcnPKL52/cbNW1u3e3fu3rv/oP/w0ZGvGidxLCtduZNCeNTK4pgUaTypHQpTaDwuzg6W9eMv6Lyq7CEtasyMmFlVKikoSHn/BzdFNW+N8F4ZdX4uHEIH5c78BewB943JW7WXdp8syFzBPFec9779AxuWem0BrvEzjP7jXDUqC7xNBinvIEgQ7hnA7gD4tCI/ANvL+9vJMFkBrpL0gmzvv4fvPP86G+X9X8ErG4OWpA6fnKRJTVkrHCmpsevxxmMt5JmY4SRQKwz6rF3l2sHzoEyhrFw4lmCl/ulohfF+YYrQaQSd+su1pfi32qSh8nXWKls3hFauB5WNBqpguSSYKoeS9CIQIZ0KbwV5KpyQFFa5MaX2WhDOu2Uy6eUcrpKj3WH6cph+DBG9ZWtssafsGdthKXvF9tkHNmJjJqMn0ZvoIHoXD+PDeBJn69Y4uvA8ZhuIy9+dvNmc</latexit>
massimizzare f (x) =
Â
ni=1
cixi
Â
n i=1pixi P
x 2 {0,1} i = 1,2,...,n
Programmazione Lineare: alcuni esempi
§
Dato un grafo G = (V, E) un ricoprimento di vertici (vertex cover) è un sottoinsieme C ⊆ V tale che ogni spigolo di G abbia almeno un estremo in C§
Problema di ottimizzazione combinatoria: dato G calcolare il ricoprimento di vertici C di cardinalità minima§
Impostiamolo come problema di programmazione lineare intera:•
Le variabili del problema sono x1, ..., xn e sono definite in modo tale che per ogni vi ∈ V(G) sia xi = 1 se vi ∈ C e xi = 0 altrimenti (se vi ∉ C)•
La funzione obiettivo da minimizzare è•
C è un ricoprimento (una soluzione ammissibile) se per ogni spigolo(vi, vj) ∈ E(G) almeno uno dei due vertici vi e vj è in C, ossia se xi + xj ≥ 1
§
Problema di programmazione lineare intera:<latexit sha1_base64="fJMXma2Ymcxm52k4R7WWf/RMZ3k=">AAACJ3icbVDLSgMxFM3UV62vqks3wSK0UMqMiLoRim5cVrAPaMuQSTNtaCYzJHdKy9Bv8Dv8ALf6Ce5El678DdPHwrYeuHA4597c3ONFgmuw7S8rtba+sbmV3s7s7O7tH2QPj2o6jBVlVRqKUDU8opngklWBg2CNSDESeILVvf7dxK8PmNI8lI8wilg7IF3JfU4JGMnNFvz80HWKuNUJQRfx0JUFfINbOg7cZOBy3OIS18ZG5242Z5fsKfAqceYkh+aouNkf8yiNAyaBCqJ107EjaCdEAaeCjTOtWLOI0D7psqahkgRMt5PpSWN8ZpQO9kNlSgKeqn8nEhJoPQo80xkQ6OllbyL+5zVj8K/bCZdRDEzS2SI/FhhCPMkHd7hiFMTIEEIVN3/FtEcUoWBSXNgSaUGADccZk4yznMMqqZ2XnMuS83CRK9/OM0qjE3SK8shBV6iM7lEFVRFFT+gFvaI369l6tz6sz1lryprPHKMFWN+/Hfuk3w==</latexit>
f (x1, . . . ,xn) =
Â
vi2V
xi
<latexit sha1_base64="ZhsW+7EG9Se/bJWcAyDKbb6Qdcg=">AAACk3icbVFda9swFJXdfXTZR9ONPe1FWxh0awj2KF1hL6XbYC+DDpa0EAUjK9eOWll2peuQYNx/sR+3X7AfsZfJrh/6sQuCwzlHulfnxoWSFoPgt+dv3Lv/4OHmo97jJ0+fbfW3n09sXhoBY5Gr3JzG3IKSGsYoUcFpYYBnsYKT+Pxzo58swViZ65+4LmCW8VTLRAqOjor6v5iCBFnFYkilrrgxfF1Xqu6xTGpmyyyqlpFkUtNJvXKA9ViSG67UJd1xwpAuo7N3tNG/Di+pc+yuojOWwgUNr3udtTVNWk8LWRUMQ1Y3LtDzrjMzMl3gKOoPglHQFr0Lwg4MSFfHUf8Pm+eizECjUNzaaRgUOHOPohQK3G9KCwUX5zyFqYOaZ2BnVRtfTd86Zk7dqO5opC17/UbFM2vXWeycGceFva015P+0aYnJwaySuigRtLhqlJSKYk6bXdC5NCBQrR3gwkg3KxULbrhAt7EbXQqrOMKq7rlkwts53AWTD6NwfxT+2BscHnUZbZJX5A3ZISH5SA7JN3JMxkSQv95r772367/0P/lH/pcrq+91d16QG+V//wdVa8ln</latexit>
8<
:
minÂvi2V xi
8 (vi,vj) 2 E, xi+xj 1 8 vi 2 V xi 2 {0,1}
1
2 6
3 4
5
1 6
3 4
Programmazione Lineare: alcuni esempi
C§
Dato un grafo G = (V, E) una clique è un sottoinsieme C ⊆ V tale che ogni coppia di vertici in C sia collegata da uno spigolo in G (C induce un sottografo completo su G)§
Problema di ottimizzazione combinatoria: dato G individuare una clique di dimensione massima su G§
Impostiamolo come problema di programmazione lineare intera:•
Le variabili del problema sono x1, ..., xn e sono definite in modo tale cheper ogni vi ∈ V(G) sia xi = 1 se vi è nella clique C e xi = 0 altrimenti (se vi ∉ C)
•
La funzione obiettivo da massimizzare è•
C è una clique se per ogni coppia (vi, vj) ∉ E(G) risulta vi ∉ C o vj ∉ C; formalmente per ogni (vi, vj) ∉ E(G) risulta xi + xj ≤ 1•
Problema di programmazione lineare intera:<latexit sha1_base64="fJMXma2Ymcxm52k4R7WWf/RMZ3k=">AAACJ3icbVDLSgMxFM3UV62vqks3wSK0UMqMiLoRim5cVrAPaMuQSTNtaCYzJHdKy9Bv8Dv8ALf6Ce5El678DdPHwrYeuHA4597c3ONFgmuw7S8rtba+sbmV3s7s7O7tH2QPj2o6jBVlVRqKUDU8opngklWBg2CNSDESeILVvf7dxK8PmNI8lI8wilg7IF3JfU4JGMnNFvz80HWKuNUJQRfx0JUFfINbOg7cZOBy3OIS18ZG5242Z5fsKfAqceYkh+aouNkf8yiNAyaBCqJ107EjaCdEAaeCjTOtWLOI0D7psqahkgRMt5PpSWN8ZpQO9kNlSgKeqn8nEhJoPQo80xkQ6OllbyL+5zVj8K/bCZdRDEzS2SI/FhhCPMkHd7hiFMTIEEIVN3/FtEcUoWBSXNgSaUGADccZk4yznMMqqZ2XnMuS83CRK9/OM0qjE3SK8shBV6iM7lEFVRFFT+gFvaI369l6tz6sz1lryprPHKMFWN+/Hfuk3w==</latexit>
f (x1, . . . ,xn) =
Â
vi2V
xi
<latexit sha1_base64="LlS4qzJ1M0ptMirIFSQIgBZavao=">AAACl3icbVHbjtMwEHXCbSm3Ak+IF4tqpUVUIUEIeGMFAu3jrkS7K9VV5LiT1ru2E+xJ1SrK/gefxhfwGeBk87AXRrJ0dM6Zi2eyUkmHcfw7CG/dvnP33s79wYOHjx4/GT59NnVFZQVMRKEKe5JxB0oamKBEBSelBa4zBcfZ2ddWP16DdbIwP3BbwlzzpZG5FBw9lQ5/MQU5spplsJSm5tbybVOrZsA03zBX6bRep5JJQ6fNxgM2YHlhuVLndM8LY7pOT19TZgpsPd/G59S73mzSU1/3J00u+72ddoU6TwdZHY8T1rQuMIu+O7NyucIoHY7iKO6C3gRJD0akj8N0+IctClFpMCgUd26WxCXOfVGUQoH/UeWg5OKML2HmoeEa3LzuVtjQXc8sqB/VP4O0Yy9n1Fw7t9WZd2qOK3dda8n/abMK80/zWpqyQjDiolFeKYoFbe9BF9KCQLX1gAsr/axUrLjlAv3VrnQpneIIm2bgN5Nc38NNMH0XJR+i5Oj9aP9Lv6Md8pK8InskIR/JPjkgh2RCBPkb7AZR8DZ8EX4Ov4cHF9Yw6HOekysRHv0DmgfLQw==</latexit>
8< maxÂvi2V xi
1
6 2
5 3
7
4 1
2
7 6
Programmazione Lineare: alcuni esempi
§
Sia G = (V, E) un grafo con dei «costi» non negativi assegnati agli spigoli: per ogni (vi, vj) ∈ E(G) sia wij ≥ 0 il costo corrispondente§
Problema di ottimizzazione combinatoria: dati due vertici s, t ∈ V(G) si vuole trovare il cammino p di costo minimo da s a t§
Problema di programmazione lineare intera: per ogni spigolo (vi, vj) ∈ E(G) sia xij = 1 se (vi, vj) è sul cammino p: s ⤳ t, altrimenti xij = 0§
La funzione obiettivo da minimizzare è la seguente:§
Affinché p sia un cammino da s a t deve risultare:§
Formalizzazione come problema di programmazione lineare intera:<latexit sha1_base64="meqwkubbe/0cXxlr+gMG4OJ+uWg=">AAACM3icbVDLSsNAFJ3Ud33Fx87NYBEqSEkEHxuhKILLClYLTQiT6cROO5mEmUltCVnqT7jzH/wAt/oF4k4EV/6D08fCqgeGOZxzL/fe48eMSmVZr0ZuYnJqemZ2Lj+/sLi0bK6sXsooEZhUccQiUfORJIxyUlVUMVKLBUGhz8iV3z7p+1cdIiSN+IXqxcQN0TWnAcVIackz94KiEyLV9IO0m23DI+jIJPTSYsejO7DjtbahQzk8zeCNl9JWBruDzzMLVskaAP4l9ogUyrvrt+6DuKt45qfTiHASEq4wQ1LWbStWboqEopiRLO8kksQIt9E1qWvKUUikmw7Oy+CWVhowiIR+XMGB+rMjRaGUvdDXlf1T5G+vL/7n1RMVHLop5XGiCMfDQUHCoIpgPyvYoIJgxXqaICyo3hXiJhIIK53o2JRYMqRIN8vrZOzfOfwll7sle79kn9uF8jEYYhZsgE1QBDY4AGVwBiqgCjC4B0/gGbwYj8ab8W58DEtzxqhnDYzB+PoGTZ6thw==</latexit>
f (x) = Â(vi,vj)2E wi jxi j
<latexit sha1_base64="rTyAUUKrvlt1SHbuAxlf9Wca9Ts=">AAACq3icbVHbihNBEO0Zb2u8bHQffWkMygpJmPHBy8NiyCIIvqxosovpMPR0ajKd7ekZumtCwjAf4MeI3+MX+BWCPUlY3V0LGk6dU3WqqI4LJS0GwU/Pv3Hz1u07e3db9+4/eLjffvR4bPPSCBiJXOXmLOYWlNQwQokKzgoDPIsVnMbnx41+ugRjZa6/4LqAacbnWiZScHRU1P7ObJlF1eEykl26jNIXTGr6vl5FVbqoexfiohHlX1Eu6iOmIEFWsRjmUlfcGL6uK6XqVi/s0ueN2ZFlrHWRoEuCJmFJbrhSbDOQNp5jyixgJnVpKatsF1ntihno2c6XGTlPsR+1O0E/2AS9DsId6Aw+/v727sdwdRK1f7FZLsoMNArFrZ2EQYFTZ4pSKKhbrLRQcHHO5zBxUPMM7LTanLWmzxwzo25Z9zTSDftvR8Uza9dZ7Cozjqm9qjXk/7RJicmbaSV1USJosR2UlIpiTps/ojNpQKBaO8CFkW5XKlJuuED3k5emFFZxhFXdcpcJr97hOhi/7Iev+uGnsDMYkm3skSfkKTkkIXlNBuQDOSEjIrwD76039I79nv/Z/+qzbanv7XoOyKXw4Q9EvtPA</latexit>
Â(vi,vh)2E xh j Â(vj,vi)2E xi j = 8<
:
1, vh = s 1, vh = t
0, 8vh 2 V \ {s,t}
<latexit sha1_base64="NN4VgmXTGep372lrzk3z+9tHZZ0=">AAADlnicpVLLbhMxFHUyPEp4NIUNEhuLgFSkSTTDAropqkARLINE0kpxNPI4TuLU4xnZd9JG1uQz4LNY8wX8BcIziShps+uVbF3fc+6xdXzjTAoDQfCrVvfu3L13f+9B4+Gjx0/2mwdPBybNNeN9lspUn8XUcCkU74MAyc8yzWkSS34an38q8dMF10ak6hssMz5K6FSJiWAUXCk6qP0gkk+AWBLzqVCWak2XhZVFgyRCYWLyJLKHi0j4eBHN3xBX6xYXkRXz4rLaCWlsk2YbkoNn86L9D5yXoLgCXe9xO/SJjwnwS7DYcFyU/cfmVpo7JeFWksEOSVwyBs4gDs6o3GBijQ+k8mOSairlCl/5VrG7Pl7htWR1Jjbww3UHV+ON9USL6Qw6jajZCjpBFfhmEm6S1slw9ROPW997UfM3GacsT7gCJqkxwzDIYORUQTDJ3X/mhmeUndMpH7pU0YSbka0mqMCvXWWM3bvdUoCr6v8dlibGLJPYMRMKM3MdK4u7sGEOk6ORFSrLgSu2vmiSSwwpLscRj4XmDOTSJZRp4d6K2YxqysAN7dYtmZHUfUFROhNe9+FmMnjbCd91wq/Ooo9oHXvoBXqJDlGI3qMT9AX1UB+x2p/6q3q73vGeex+8rvd5Ta3XNj3P0FZ4vb9iXCdL</latexit>
8>
>>
><
>>
>>
:
minÂ(vi,vj)2E wi jxi j
Â(vi,vh)2E xh j Â(vj,vi)2E xi j = 1, se vh = s Â(vi,vh)2E xh j Â(vj,vi)2E xi j = 1, se vh = t
Â(vi,vh)2E xh j Â(vj,vi)2E xi j = 0, se vh 2 V \ {s,t}
Programmazione Lineare: alcuni esempi
§
Sia G = (V, E) un grafo con dei «costi» non negativi assegnati agli spigoli: per ogni (vi, vj) ∈ E(G) sia wij ≥ 0 il costo corrispondente§
Un albero ricoprente (spanning tree) di G è un sottografo T = (V, E’) tale che E’ ⊆ E(G) in modo che T sia connesso e aciclico (un albero)§
Problema di ottimizzazione: dato G trovare l’albero ricoprente di costo minimo; in altri termini si vuole trovare l’albero ricoprente T* del grafo G tale che§
Variabili per la formalizzazione del problema in termini di programmazione matematica: per ogni spigolo ei ∈ E(G), i = 1, ..., m, il cui costo è wi, definiamo la variabile xi = 1 se ei ∈ E(T), altrimenti xi = 0§
Possiamo così definire la funzione obiettivo da minimizzare: f(x) = w1 x1 + w2 x2 + ... + wm xm§
Problema di programmazione lineare intera:<latexit sha1_base64="I+IRj4SzPbqL5EHp0kuB9WW5t3I=">AAACYXicbZDLahRBFIZr2lsy3tq4zOZgECYShm4X6kYISlBwE2EmCUxPmuqaM0klVdVN1anWoelX8j30DdzqwqVb3VlzQUzigYKf/1z+4isqJR0lyddOdO36jZu31ta7t+/cvXc/frBx4EpvBQ5FqUp7VHCHShockiSFR5VFrguFh8X563n/sEbrZGkGNKtwrPmJkVMpOAUrj0XmvM6bXp3LHajzs23IpIG93uD4yXYLH/JGnrXwEjItTd4MICP8SA2IUwQrRRmioIU3Layu+J3674Hluq/bbh5vJf1kUXBVpCuxtfvuy97xp29sP49/ZJNSeI2GhOLOjdKkonHDLUmhsO1m3mHFxTk/wVGQhmt042YBo4XHwZnAtLThGYKF++9Gw7VzM12ESc3p1F3uzc3/9Uaepi/GjTSVJzRiGTT1CqiEOVmYSIuC1CwILqwMfw2cuOWCAv8LKZVTPIBckEkvc7gqDp7202f99H1A9Iota41tskesx1L2nO2yt2yfDZlgn9lP9ov97nyP1qM42liORp3VzkN2oaLNP3lHupE=</latexit>
(vi,vj
Â
)2E(T⇤)wi j = min
T che ricopre G
Â
(u,v)2E(T)
wuv
x1 x2
x3
1 1
1
x’ = (1, 0, 1)
x’’ = (1, 1, 0) x’’’ = (0, 1, 1)
v3
v1
v2 e = (3
v , v1 3 )
w(e) = 103
1e = ( 1v , v
2 ) w(e
1 ) = 20
e2 = (v2, v3) w(e2) = 30
Programmazione Lineare: alcuni esempi
§
Consideriamo un’istanza estremamente semplice del problema dell’albero ricoprente di costo minimo (minimum spanning tree):sia G = (V, E) con
•
V = {v1, v2, v3}•
E = {e1 = (v1, v2), e2 = (v2, v3), e3 = (v3, v1)}•
con w1 = w(e1) = 20, w2 = w(e2) = 30, w3 = w(e3) = 10§
Lo spazio delle soluzioni è costituito daA = { x’ = (1, 0, 1), x’’ = (1, 1, 0), x’’’ = (0, 1, 1)}
§
Effettuando il rilassamento continuo del problema diprogrammazione intera possiamo estendere A al politopo di dimensione 3
