Rappels sur l’algèbre linéaire et la géométrie des polyèdres convexes 

Rappels sur l’algèbre linéaire et la géométrie des polyèdres convexes 

Particularité des modèles en variables entières et mixtes

La programmation linéaire en nombres mixtes permet de modéliser de très nombreuses contraintes complexes qui seraient intraitables sans variables entières. De nombreuses contraintes, en apparence non linéaires, peuvent être linéarisées grâce à des variables entières. Ces possibilités augmentent énormément le champ d’application de la programmation linéaire. Même si les programmes linéaires obtenus sont souvent difficiles à résoudre, la programmation linéaire en nombres mixtes est déjà très utile comme langage de modélisation : elle permet de décrire de façon concise des problèmes discrets d’optimisation

Méthode d’arrondi

Hormis des cas très particuliers, une solution de (PL) comportera généralement des composantes fractionnaires.
La première idée qui vient à l’esprit, lorsqu’on se trouve confronté à un problème en nombres entiers, est d’utiliser une méthode d’arrondi, par exemple en remplaçant, dans la solution optimale continue, chaque composante fractionnaire par l’entier le plus proche.
L’exemple suivant montre clairement l’insuffisance de telles méthodes et permet de mieux saisir la difficulté inhérente aux problèmes de programmation en nombres entiers.

Complexité

Le problème général de la programmation linéaire en variables entières (PLE) ou (PLM) est d’une difficulté beaucoup plus grande, réellement d’une autre nature, que le problème de programmation linéaire en variables continues (PL).
Même si le problème (PLE) ne contient qu’un nombre fini de solutions (si le polyèdre S est borné), alors que le problème (PL) contient une infinité non dénombrable de solutions admissibles, le premier problème est beaucoup plus difficile que le second. En effet, l’étude initiale du problème (PL) nous a montré immédiatement :
– que l’obtention de la solution optimale ne nécessite de s’intéresser qu’à un nombre fini de solutions, à savoir les seuls sommets du polyèdre X ;
– que ces sommets sont facilement caractérisables (ce sont des solutions de base admissibles) et qu’ils peuvent donc être aisément déterminés.
Par contre, dans les situations (PLE) ou (PLM), la solution optimale n’est, en général, pas un sommet de S et peut donc être un point quelconque de S (point intérieur, point frontière ou point extrême). On perd ainsi toute caractérisation particulière de la solution optimale qui est, pour cette raison, bien plus difficile à déterminer.

Méthodes des plans sécants

L’idée de base sur laquelle se fondent ces méthodes est la suivante : on commence par résoudre le programme linéaire continu (P L) ; si la solution optimale obtenue est un point extrême à coordonnées entières, celle-ci est une solution optimale de (P LE).
Dans le cas contraire, il est facile de voir que l’on peut toujours tronquer le domaine des solutions (en rajoutant une contrainte supplémentaire au problème) de façon à éliminer ce point extrême sans exclure aucune solution réalisable entière. Une telle contrainte est appelée une coupe (on dit encore : une troncature).
Reprenons l’exemple précèdent  : l’optimum continu était le point extrême (5.9, 0). La contrainte supplémentaire x1 ≤ 5 élimine ce point sans exclure aucune solution entière. De même, toute contrainte supplémentaire du type x1 + x2 ≤ α, avec 5 ≤ α < 5.9 est une coupe.
Après avoir rajouté une coupe (ou éventuellement plusieurs), le programme linéaire augmenté des contraintes correspondantes est de nouveau résolu en continu. Si la solution optimale de ce nouveau problème est entière, on obtient alors une solution optimale du (PLE). Sinon, on cherchera une nouvelle coupe que l’on rajoutera à l’ensemble des contraintes ; puis le programme linéaire ainsi augmenté sera optimisé de nouveau, etc.

Les méthodes de recherche arborescente par séparation et évaluation

Cette approche a été proposée par Little et al. pour résoudre le problème du voyageur de commerce puis, repris par d’autres sous différentes variantes.
Essentiellement, il s’agit de diviser, c’est-`a-dire séparer l’ensemble de toutes les solutions réalisables en sous-ensembles plus petits (régions réalisables plus restreintes) et mutuellement exclusifs et en tentant d’identifier et d’éliminer de l’ensemble des solutions réalisables du programme linéaire, certaines parties qui ne contiennent pas des solutions entières réalisables.L’implémentation de l’algorithme de Branch and Bound peut être vu comme un arbre avec au nœud de la racine le problème original (P LE). L’arbre est construit d’une manière itérative avec de nouveaux nœuds formés par la séparation d’un nœud existant dont lequel la solution optimale du problème relaxé associé n’est pas entière.

Algorithme de résolution d’un (PLE) par la méthode de support

Le but de cet algorithme est de construire un plan optimal pour le problème . Le principe est le même que celui des algorithmes de plans sécants. A savoir, on commence par résoudre le problème relaxé  à l’aide de l’algorithme direct de support.
Si la solution optimale du (PL) contient uniquement des composantes entières, elle est également une solution optimale du (PLE) ; dans ce cas, la résolution est terminée.
Sinon, si une ou plusieurs variables ne sont pas entières, on doit générer alors une coupe valide. Cette contrainte supplémentaire est ajoutée au programme (PL) et on résout de nouveau le problème résultant. Si la solution obtenue est à valeurs entières, la résolution est terminée. Sinon, on génère une nouvelle coupe et on répète la procédure jusqu’à l’obtention d’une solution optimale à valeurs entières.

 

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction générale
1 Rappels sur l’algèbre linéaire et la géométrie des polyèdres convexes 
1.1 Rappels sur la géométrie de Rn
1.1.1 Espaces vectoriels
1.1.2 Distance, Boule, Voisinage et Ensemble Ouvert
1.2 Matrices 
1.3 Eléments d’analyse convexe
1.3.1 Inégalités Valides, Faces et Facettes
1.4 Fonction linéaire et fonction convexe 
1.5 Séparation des ensembles convexes 
1.5.1 Hyperplan dans l’espace Rn
1.5.2 Séparation de deux ensembles par un hyperplan
1.5.3 Hyperplan d’appui
1.5.4 Théorèmes de séparation des ensembles convexes
1.6 Cône polyédrique convexe et inéquations linéaires 
1.7 Points extrêmes et rayons extrêmes 
1.8 Polyèdres dont les points extrêmes sont entiers 
1.8.1 Systèmes totalement duaux entiers (TDE)
1.9 Partie entière et partie fractionnaire d’un nombre 
1.10 Lien polyédral entre un programme linéaire et un programme linéaire en nombres entiers
2 Programmation linéaire en nombres entiers et mixtes 
2.1 Particularité des modèles en variables entières et mixtes
2.1.1 Exemples de problèmes
2.1.2 Formulation des problèmes
2.2 (PLEs) avec matrices totalement unimodulaires
2.3 Méthode d’arrondi, Optimalité, Relaxation et Dualité 
2.3.1 Méthode d’arrondi
2.3.2 Réduction à un problème en variables bivalentes (0 ou 1)
2.3.3 Optimalité et relaxation
2.3.4 Dualité
2.3.5 Complexité
2.4 Méthodes des plans sécants 
2.4.1 Inégalités valides pour un programme linéaire
2.4.2 Inégalités valides pour un programme linéaire en nombres entiers
2.4.3 Algorithme des plans sécants
2.4.4 Inégalités valides pour un programme linéaire en nombres entiers et mixtes
2.4.5 Les coupes de Gomory en nombres entiers et mixtes
2.4.6 Procédure d’arrondi en nombres entiers et mixtes (MIR)
2.5 Les méthodes de recherche arborescente par séparation et évaluation
2.6 Branch and cut 
2.7 Décomposition de Benders
3 Méthode de support pour la résolution d’un problème de programmation linéaire en nombres entiers 
3.1 Position du problème 
3.2 Méthode directe de support pour la résolution d’un problème de programmation linéaire à variables bornées 
3.2.1 Formule d’accroissement de la fonction objectif
3.2.2 Algorithme de résolution 
3.3 Algorithme de résolution d’un (PLE) par la méthode de support
Conclusion Générale

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *