Algorithme de couverture de sommet minimum avec programmation linéaire

Question

Considérez l'algorithme suivant: donné un graphique $ g $ avec $ n $ sommets, mis en place Un problème de programmation linéaire lp où il y a une variable $ x_i $ pour chaque sommet $ v_i $ de $ g $ , chaque variable peut prendre la valeur $ \ geq 0 $ , pour chaque Edge $ V_AV_B $ de $ g $ Définissez la contrainte $ x_a + x_b \ geq 1 $ . La fonction objectif est $ \ min \ sum \ limites_ {1} ^ {n} {x_i} $ . Trouver la variable (ou l'une des variables) $ x_i $ , parmi les variables non définies sur $ 0 $ , qui définit sur 0 $ donne la valeur minimale de la fonction objectif. Ajoutez la contrainte $ x_i= 0 $ to lp . Répéter jusqu'à ce que la solution optimale de lp est entier (c'est-à-dire que chaque variable prend de la valeur dans $ \ \ {0; 1 \ droite \} $ >).

Je cherche un graphique où les sommets associés aux variables qui prennent la valeur 1 $ dans la solution optimale finale de lp sont Pas une couverture de sommet minimale de $ g $ (si elle existe).

Answer 1

considérer le graphique

  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

paramètre $ x_1, x_2, x_3, x_6 $ ou $ x_7 $ to 0 donne votre LPune valeur de 4, lors de la définition $ x_4 $ ou $ x_5 $ to 0 donne à votre lp une valeur de5. Toutefois, si vous définissez $ x_1= 0 $ , vous obtenez enfin une couverture de sommet de la taille 5, tandis que la couverture de sommet optimale est de taille 4.