Cours: OPTIMISATION COMBINATOIRE
Par: Madani BEZOUI,
I Résolution de problèmes de programmation linéaire en nombres entiers PLNE 5
1 Généralités sur les PLNE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1 Forme générale d'un programme linéaire en nombres entiers "PLNE" 7
2 Méthode de séparation évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Evaluation 9
2.2 La séparation 9
2.3 La stratégie de parcours 10
2.3.1 La largeur d'abord . . . . . . . . . .
2.3.2 La profondeur d'abord . . . . .
2.3.3 Le meilleur d'abord . . . . . .
3 Méthodes de coupes . .
3.1 Coupe de Gomory 15
3.2 Principe des méthodes de coupe