Algoritmo minimo della copertura del vertice con programmazione lineare
-
29-09-2020 - |
Domanda
Considera il seguente algoritmo: dato un grafico $ G $ con $ n $ Vertici, impostare Un problema di programmazione lineare lp dove c'è una variabile $ x_i $ per ogni vertice $ v_i $ di $ G $ , ogni variabile può prendere valore $ \ geq 0 $ , per ciascuno Edge $ v_av_b $ di $ G $ Imposta il vincolo $ x_a + x_b \ geq 1 $ . La funzione obiettivo è $ \ min \ sum \ limits_ {1} ^ {n} {x_i} $ . Trova la variabile (o una delle variabili) $ x_i $ , tra le variabili non impostati su $ 0 $ , che impostato su $ 0 $ dà il valore minimo della funzione obiettivo. Aggiungere il vincolo $ x_i= 0 $ a lp . Ripeti fino a quando la soluzione ottimale di lp è integer (che ciascuna variabile prende valore in $ \ sinistra \ {0; 1 \ destra \} $ ).
Sto cercando un grafico in cui i vertici associati alle variabili che prendono valore $ 1 $ nella soluzione finale ottimale di lp sono Non una copertura di vertice minima di $ G $ (se esiste).
Soluzione
Considera il grafico
2-4---7
/ |\ /|
1 | × |
\ |/ \|
3-5---6
.
Impostazione $ x_1, x_2, x_3, x_6 $ o $ x_7 $ su 0 dà il tuo LPUn valore di 4, mentre impostando $ x_4 $ o $ x_5 $ su 0 dà il tuo Valore del tuo LP un valore di5. Tuttavia, se si imposta $ x_1= 0 $ , verrà finalmente ottenuto una copertura vertice della taglia 5, mentre il coperchio ottimale del vertice è di dimensioni 4.
.