soufiane-1-10
soufiane-1-10
soufiane-1-10
Rapport de mini-projet
Sujet :
Programmation linéaire en nombres entiers
avec la méthode de Branch and Bound
1.Introduction
2. Définition et principes de la méthode de Branch
and Bound
2.1. Définition de la méthode.
2.2. Les étapes principales :
Branchement (Branching)
Bornes (Bounding)
2.3. Avantages et limites de cette méthode.
3. Détails de la méthodologie
3.1. Relaxation linéaire
3.2. Algorithme de Branch and Bound
4. Application pratique : Énergies renouvelables
4.1. Problématique
4.2. Modélisation mathématique
4.3. Résolution avec Branch and Bound
5. Conclusion
Bornes (Bounding)
EXEMPLE:
Avantages :
Offre une solution exacte pour les problèmes de PLNE.
Réduit le temps de calcul en élaguant les branches non
prometteuses.
Limites :
Peut être inefficace pour les problèmes très complexes ou de grande taille.
Nécessite des ressources importantes en mémoire et en temps de
calcul.
4.1. Problématique
Contraintes :
Formulation
Sous les contraintes
2x+3y≤17,
10x+3y≤45,x,y≥0
Étape 2 : Branchement :
Les variables doivent être entières. Nous créons deux branches :
y≤3
y≥4
Sous-problème 1 (y≤3) :
Fixons y=3y = 3y=3 et résolvons :
maxZ=5x+2(3)=5x+6\max Z = 5x + 2(3) = 5x + 6maxZ=5x+2(3)=5x+6
Sous-problème 2 (y≥4y) :
Fixons y=4y = 4y=4 et résolvons :
maxZ=5x+2(4)=5x+8\max Z = 5x + 2(4) = 5x + 8maxZ=5x+2(4)=5x+8
La valeur entière maximale de xxx est x=2x = 2x=2, mais cela viole les
contraintes. Ce sous-problème est non réalisable.
Solution optimale