Généralités sur les problèmes d’optimisation

Généralités sur les problèmes d’optimisation

Nous avons brièvement discuté, dans le chapitre précédent, la difficulté associée à la résolution de plusieurs problèmes, avec objectifs différents, dans la planification de la chaîne logistique, et particulièrement lorsque l’on veut suivre une approche d’optimisation globale, comme établie par la matrice de planification des logiciels APS. Les problèmes associés aux étapes de planification de la chaîne logistique, dans tous les niveaux de décisions, peuvent être modélisés comme des problèmes d’optimisation, ayant une fonction objectif (par exemple, la minimisation du coût, la minimisation du retard, la minimisation du nombre de véhicules, etc.) et des contraintes (par exemple, la satisfaction de la demande, une capacité de production limitée, des lots de production avec une taille maximale, des véhicules limités, des fenêtres de temps pour la production ou pour la distribution, etc.). En pratique, avec toutes les données et les contraintes présentes dans les différents types de chaîne logistique, chacun des problèmes modélisant les étapes de planification, devient très difficile à résoudre, cette difficulté étant mesurable par un indicateur connu comme la complexité, que nous discutons dans ce qui suit. L’intégration ou la considération des contraintes de plusieurs étapes de planification dans un seul problème augmente encore plus la difficulté de résolution, raison pour laquelle, il est souvent impossible de déterminer la solution optimale d’un problème, et même d’obtenir une solution réalisable. C’est pourquoi les problèmes d’optimisation liés à la chaîne logistique nécessitent de combiner des techniques de recherche opérationnelle et la conception d’algorithmes sophistiqués, capables de résoudre des problèmes complexes dans des temps de calcul raisonnables et avec une utilisation limitée de ressources (processeur et mémoire physique des ordinateurs). 

Complexité

La complexité est un indicateur de l’effort de calcul, par rapport au temps d’exécution, nécessaire pour la résolution d’un problème d’optimisation. Une autre mesure de l’effort de calcul est l’utilisation ou la consommation de mémoire physique (RAM dans les ordinateurs) nécessaire pour garder les données des variables, issues de l’exploration de l’espace de solution (ou espace de recherche), dans une méthode d’optimisation. En théorie de la complexité [62], on peut distinguer la complexité de l’algorithme et la complexité du problème. La complexité du temps de calcul d’un algorithme est donnée par le nombre d’étapes nécessaires pour résoudre le problème. Étant donné que ce nombre peut varier en fonction de l’instance étudiée, la complexité de l’algorithme est définie par rapport au pire cas. La notation O est utilisée pour représenter cette complexité. Ainsi, un algorithme est applicable en temps polynomial si sa complexité est O (p (n)), ou p (n) est une fonction polynomiale de la taille de l’instance n (par exemple, le nombre de produits, le nombre de machines ou le nombre de périodes de planification). Donc, si p (n) = akn k + · · · + ajn j + · · · + a1n + a0, avec ak > 0 et aj ≥ 0 ∀ 1 ≤ j ≤ k − 1, l’algorithme a une complexité polynomiale de O peut être réduit à un problème de décision, dont la solution est de type binaire, c’est-à-dire ayant pour réponse oui ou non. Selon la complexité, les problèmes peuvent être organisés en plusieurs classes [62], dont les plus grandes et importantes sont P et N P. Une classe de complexité représente l’ensemble des problèmes qui peuvent être résolus avec une quantité déterminée de ressources. Ainsi, la classe P fait référence à l’ensemble de tous les problèmes de décision qui peuvent être résolus en temps polynomial, au moyen d’un algorithme déterministe. Un algorithme est déterministe si le nombre d’étapes nécessaires pour résoudre le problème peut être calculé à l’avance. D’autre part, la classe N P est associée à l’ensemble des problèmes de décision qui peuvent être résolus en temps polynomial par un algorithme non déterministe. La caractéristique d’un algorithme non déterministe est que l’on ne peut pas prédire avec certitude le nombre d’étapes nécessaires pour résoudre le problème. Une autre classe importante, contenue dans la classe N P est celle des problèmes N Pcomplets. Un problème de décision G est N P-complet si tous les problèmes de la classe N P peuvent être ramenés (réduits) en temps polynomial à G. Cela implique que l’on peut construire une instance de G, à partir de n’importe quelle instance d’un problème H ∈ N P, suivant une fonction polynomiale de la taille de l’instance de H. Le problème d’optimisation correspondant à un problème de décision N P-complet est dit N P-difficile, pour lequel la résolution se fait en temps exponentiel, c’est-à-dire que le temps d’exécution augmente de façon exponentielle en fonction de la taille de l’instance. La relation entre les classes mentionnées est illustrée dans la Figure 2.1.

Modélisation

Nous nous intéressons, dans ce travail, à la modélisation par programmation mathématique. D’autres types de modélisations, que nous ne décrivons pas dans ce travail, sont les modèles d’optimisation combinatoire, les modèles de satisfaction de contraintes et les modèles non analytiques. En programmation mathématique, les modèles peuvent être classés en : problèmes en nombres réels (continuous programs), problèmes en nombres entiers (IP ou integer programs) et problèmes en nombres entiers mixtes (MIP ou mixed integer programs). Le nom de chaque type de modèle fait référence à la nature des variables de décision utilisées dans la formulation. Ainsi par exemple, les modèles MIP comportent des variables de décision réelles (ou continues) et entières (ou discrètes). Ce type de modélisation peut être vue comme une sous-catégorie de la modélisation IP, car les méthodes de résolution pour des problèmes à nombres réels ne donnent pas des solutions réalisables pour ces modèles, contrairement aux méthodes dédiées pour des problèmes à nombres entiers. Un autre sous-ensemble des modèles IP est celui des modèles 0-1, où les variables de décision prennent uniquement des valeurs binaires (0 ou 1). Les modèles avec uniquement des variables de décision réelles sont plus faciles à résoudre, avec une complexité polynomiale quand la fonction objectif et les contraintes sont linéaires. La plupart des problèmes de dimensionnement de lots et d’ordonnancement sont modélisés par des programmes à variables mixtes, les variables entières étant souvent binaires, comme la variable de setup Yil qui vaut 1 si la production du produit i est lancée à la période l, ou 0 sinon. En général, l’inclusion de variables binaires dans la formulation mathématique rend plus difficile la résolution du problème. C’est pourquoi, des méthodes de relaxation et de décomposition sont utilisées pour ne pas considérer ou pour fixer ces variables. 

Cours gratuitTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

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