soufiane-1-10

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 10

Université Abdelmalek Essaadi

Ecole Nationale des Sciences Appliquées d’Al Hoceima

Rapport de mini-projet
Sujet :
Programmation linéaire en nombres entiers
avec la méthode de Branch and Bound

Elaboré par : Encadré par :


MAHI Oualid PR. ABOU EL HANOUNE
AZARKANE Soufiane YOUNES
WASSOU Ayoub
Année universitaire 2024
Sommaire:

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

Année universitaire 2024


Introduction
La programmation linéaire en nombres entiers (PLNE) est une
méthode d’optimisation combinatoire qui impose que certaines ou
toutes les variables soient des entiers. Elle est largement utilisée dans
des domaines tels que la gestion des ressources, la planification
industrielle et la logistique.

Cependant, les problèmes de PLNE sont souvent plus complexes à


résoudre que ceux de la programmation linéaire classique, car la
contrainte d’intégralité augmente significativement l’espace de
recherche.

La méthode de Branch and Bound offre une solution efficace pour


ces problèmes en explorant intelligemment les solutions possibles
tout en réduisant les calculs inutiles.

Année universitaire 2024


2. Définition et principes de la méthode de
Branch and Bound

2.1. Définition de la méthode


La méthode de Branch and Bound est une approche algorithmique
systématique pour résoudre des problèmes d’optimisation en divisant
le problème initial en sous-problèmes plus simples.
Chaque sous-problème est évalué pour déterminer s’il peut fournir
une solution optimale ou si une autre branche doit être explorée.

Année universitaire 2024


2.2. Les étapes principales
Branchement (Branching) :

Cette étape consiste à diviser le problème principal en plusieurs


sous-problèmes en fixant des valeurs pour certaines variables (par
exemple, ou ).
Cela permet d’explorer l’espace de recherche de manière structurée.

Bornes (Bounding)

Chaque sous-problème est évalué en calculant une borne


(supérieure ou inférieure) pour son objectif. Si une branche ne peut
pas fournir une meilleure solution que celle déjà trouvée, elle est
élaguée.

EXEMPLE:

Année universitaire 2024


2.3. Avantages et limites de cette méthode
Avantages :

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.

Année universitaire 2024


3. Détails de la méthodologie
3.1. Relaxation linéaire

La relaxation linéaire consiste à supprimer la contrainte d’intégralité


des variables pour obtenir un problème de programmation linéaire
classique.

La solution optimale de ce problème relaxé sert de point de départ pour


la méthode de Branch and Bound.

3.2. Algorithme de Branch and Bound

L’algorithme suit ces étapes :

Initialisation : Résoudre la relaxation linéaire pour obtenir une


solution initiale et une borne.

Branchement : Diviser le problème en sous-problèmes en fixant des


valeurs entiers aux variables.

Bounding : Calculer les bornes pour chaque sous-problème et


déterminer s’il est nécessaire de continuer l’exploration.

Répétition : Continuer jusqu’à trouver la solution optimale.

Année universitaire 2024


4. Application pratique : Énergies
renouvelables

4.1. Problématique

Une entreprise souhaite investir dans deux sources d’énergie


renouvelable :

Solaires () : Bénéfice de 5 M€, coût d’installation de 2 M€, et surface


de 10 km².
Éoliennes () : Bénéfice de 2 M€, coût d’installation de 3 M€, et surface
de 3 km².

Contraintes :

1. Budget maximal de 17 M€.


2. Superficie maximale de 45 km².

Objectif : Maximiser les bénéfices en respectant les contraintes.

4.2. Modélisation mathématique

Formulation
Sous les contraintes

4.3. Résolution avec Branch and Bound


Étape 1 : Relaxation linéaire
Résolvons le problème :
maxZ=5x+2y
Sous les contraintes :

2x+3y≤17,
10x+3y≤45,x,y≥0

Année universitaire 2024


Les points d'intersection des contraintes et des axes sont :

2x+3y=172x + 3y = 172x+3y=17 → Intersection avec l'axe xxx : x=8.5x = 8.5x=8.5, y=0


y = 0y=0, et avec yyy : y=5.67y = 5.67y=5.67, x=0x = 0x=0.
10x+3y=4510x + 3y = 4510x+3y=45 → Intersection avec l'axe xxx : x=4.5x = 4.5x=4.5,
y=0y = 0y=0, et avec yyy : y=15y = 15y=15, x=0x = 0x=0.

En résolvant les deux équations pour trouver leur point d'intersection :

2x+3y=17,10x+3y=452x + 3y = 17, \quad 10x + 3y = 452x+3y=17,10x+3y=45

En soustrayant, nous trouvons :

8x=28 ⟹ x=3.5, y=3.338x = 28 \implies x = 3.5, \, y = 3.338x=28⟹x=3.5,y=3.33

Ainsi, la solution optimale relaxée est :

x=3.5x = 3.5x=3.5, y=3.33y = 3.33y=3.33, Z=5(3.5)+2(3.33)=24.16Z = 5(3.5) + 2(3.33)


= 24.16Z=5(3.5)+2(3.33)=24.16.

É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 :
max⁡Z=5x+2(3)=5x+6\max Z = 5x + 2(3) = 5x + 6maxZ=5x+2(3)=5x+6

La valeur entière maximale de xxx est x=3x = 3x=3, donc :


x=4x = 4x=4, y=3y = 3y=3, Z=5(4)+2(3)=22Z = 5(4) + 2(3) = 22Z=5(4)+2(3)=22.

Sous-problème 2 (y≥4y) :
Fixons y=4y = 4y=4 et résolvons :
max⁡Z=5x+2(4)=5x+8\max Z = 5x + 2(4) = 5x + 8maxZ=5x+2(4)=5x+8

Année universitaire 2024


Sous les contraintes :

2x+3(4)≤17 ⟹ 2x≤5 ⟹ x≤2.52x + 3(4)


2.52x+3(4)≤17⟹2x≤5⟹x≤2.510x+3(4)≤45 ⟹ 10x≤33 ⟹ x≤3.310x + 3(4)
3.310x+3(4)≤45⟹10x≤33⟹x≤3.3

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

La solution optimale est :


x=4x = 4x=4, y=1y = 1y=1, Z=22Z = 22Z=22.

Année universitaire 2024

Vous aimerez peut-être aussi