Abstract (FR)

L’optimisation robuste est une méthodologie récente qui traite de problèmes d’optimisation dont certains paramètres sont incertains ou imprécis et non modélisés par des lois de probabilité. Le but recherché est la détermination de solutions, dites robustes, offrant de bons résultats dans la plupart des scénarios. En optimisation robuste, nous pouvons considérer deux contextes décisionnels distincts. Dans le premier contexte, nommé single-stage, le décideur doit choisir une solution avant la réalisation de l’incertain. Les solutions obtenues par ce type d’approches sont des solutions de pire cas (Soyster [5]) qui sont généralement trop restrictives et loin de la réalité. Le second contexte concerne les approches multi-stage, où l’incertitude est levée à plusieurs étapes et des décisions de recours peuvent être prises. Ces approches ont été introduites par Ben-Tal et. al. [2] dont les premiers travaux traitent des prises de décision en deux étapes sur des problèmes d’optimisation dont le domaine de solutions réalisables est incertain. Plus récemment, Atamturk et Zhang [1] suivent une approche 2- stage dans un problème de dimensionnement de réseaux. Il est à noter que les modèles obtenus par ces approches sont généralement non polynomiaux. Nous nous intéressons aux programmes linéaires dont le second membre des contraintes est incertain et modélisé par des intervalles continus. Dans un contexte single-stage, l’approche de Soyster [5] considère le programme linéaire avec le plus petit domaine réalisable quand les contraintes sont des inégalités ; alors que cette approche n’est pas applicable dans le cas de contraintes d’égalité. D’autres approches ont été développées pour traiter ces problèmes incertains. Nous pouvons citer l’approche de Chinnek et Ramadan [4] qui consiste à déterminer le meilleur ainsi que le pire optimum d’un programme linéaire incertain et donner l’intervalle de variation de la fonction objectif. Par ailleurs, Bertsimas et Sim [3] suggèrent une autre approche pour les programmes linéaires dont la matrice des contraintes est incertaine. En effet, dans leur modèle, chaque coefficient est modélisé par un intervalle dont la valeur centrale représente la valeur nominale du coefficient. Les auteurs stipulent que le pire scénario ne peut toucher simultanément tous les coefficients incertains, et introduisent de ce fait un nouveau paramètre ð€€€i pour toute contrainte, appelé budget d’incertitude qui représente le nombre maximum de coefficients déviant de la valeur nominale dans la contrainte en question. Le problème ainsi obtenu a l’avantage de garder la polynomialité du problème de départ tout en garantissant une forte probabilité de satisfaction des contraintes. L’approche de Bertsimas et Sim (BS) peut aussi s’appliquer quand seul le second membre des contraintes est incertain. Dans ce cas, chaque budget d’incertitude associé à une contrainte est compris entre 0 et 1. De plus, pour ð€€€i fixé, la pire valeur pour le ième second membre dépend du sens de la contrainte et le pire scénario est complètement induit par la valeur de ð€€€i. Par conséquent, l’application de l’approche BS sur un programme linéaire avec second membre incertain n’est pas pertinente puisqu’elle conduit à prendre une décision suivant un scénario unique. Nous proposons dans notre travail une autre approche qui considère un budget d’incertitude commun à toutes les contraintes, qui représente le nombre total de seconds membres déviant de la valeur nominale. Le but recherché est le calcul de la pire évaluation de la fonction objectif compte tenu de ce budget. Cette modélisation de l’incertitude a déjà été utilisée par Thiele et. al. [6] dans une formulation de type 2-stage pour un programme linéaire dont le second membre est inconnu. Le problème de seconde étape obtenu peut être interprété comme un problème de recherche de pire optimum que nous proposons de calculer. D’un point de vue pratique, nous obtenons suivant cette approche un problème bilinéaire, que nous linéarisons en un problème mixte. Par ailleurs, nous proposons l’application de cette approche au problème classique de transport comportant des demandes incertaines. Enfin, des expérimentations numériques ont été effectuées, d’une part sur l’évolution du pire optimum en fonction du budget d’incertitude considéré, et d’autre part sur le temps de calcul pour différentes bornes spécifiques au problème de transport.