Soutenance mémoire
Historique et évolution de Programmation linéaire
Les premiers mathématiciens qui se sont occupés dudit problèmes, que l’on ne nommait pas encore à l’époque « programmes linéaires » (P.L.), sont :
– Laplace (1749-1827) et le baron Fourier.
– Le russe Kantorovitch en 1939 a imaginé une méthode inspirée des multiplicateurs de Lagrange, classiques en mécanique, pour résoudre des « programmes de transport ».
– La contribution décisive a été l’invention de l’algorithme du SIMPLEXE, développé à partir de 1947 notamment par G.B. Dantzig et le mathématicien V. Neumann.
– Au milieu des années 80, l’indien N. Karmarkar a proposé une nouvelle méthode créée aux Bell Laboratories qui permettait de résoudre de très gros problèmes linéaires, par une démarche « intérieure » au polyèdre des solutions admisisibles.
Définition de programmation linéaire (PL)
Quelques définitions
Selon W.J. Baumaul [1.01], la programmation linéaire est une technique mathématique d’optimisation (maximisation ou minimisation) de fonction à objectif linéaire sous des contraintes ayant la forme d’inéquations linéaires. Elle vise à sélectionner parmi différentes actions celle qui atteindra le plus probablement l’objectif visé. R. Dorfman [1.02] et P. Samuelson [1.03], ajoutent que la programmation linéaire est une méthode de détermination du meilleur plan d’action pour réaliser des objectifs donnés dans une situation où les ressources sont limitées. C’est donc une méthode de résolution du problème économique, soit dans le cadre d’une économie globale, soit dans celui du secteur public, soit dans une entreprise particulière. Globalement et pratiquement, la programmation linéaire traite d’une manière générale d’un problème d’allocation de ressources limitées parmi des activités concurrentes et ce d’une façon optimale. La grande variété de situations auxquelles la programmation linéaire peut s’appliquer est remarquable. Cela va de l’affectation de personnel à certaines tâches au problème de la répartition de ressources brutes limitées pour la production de plusieurs objets. La programmation linéaire emploie un modèle mathématique qui décrit le problème réel. L’adjectif « linéaire » indique que toutes les fonctions mathématiques de ce modèle sont linéaires tandis que le terme « programmation » signifie essentiellement planification. Ainsi, la programmation linéaire consiste à planifier certaines activités soumises à des restrictions en vue d’un rendement optimal, c’est-à-dire en vue d’un résultat qui atteint le but visé parmi plusieurs solutions alternatives réalisables.
Notations et définitions
Le problème général de programmation linéaire est la recherche de l’optimum (minimum ou maximum) d’une fonction linéaire de n variables xj (j = 1,2,…,n) liées par des équations ou inéquations linéaires appelées contraintes. Parmi les contraintes, on distingue généralement celles du type xj ≥ 0 (ou xj ≤ 0), imposant à une partie ou à l’ensemble des variables d’être non négatives (ou non positives). Les variables peuvent prendre n’importe quelles valeurs réelles satisfaisant aux contraintes. On peut toujours supposer que certaines des inéquations ont été multipliées par -1 de façon que toutes les inégalités soient dans le même sens (≥ par exemple), et que certaines des variables ont été remplacées par leurs opposées pour que les contraintes du type xj ≥ 0 ou xj ≤ 0 soient toutes des conditions de non négativité.
Ce modèle de programmation linéaire est présenté de manière générale comme un problème d’allocation des ressources limitées parmi des activités concurrentes et ce d’une façon optimale. On y retrouve donc m types de ressources et n types d’activités; en général, m est beaucoup plus petit que n. Évidemment, les ressources sont nécessaires pour réaliser les activités et les premières sont en quantité limitée (le vecteur b); par conséquent, l’allocation des ressources doit être faite de manière optimale c’est-à-dire, de façon à optimiser la mesure de performance z. Dans ce modèle, les éléments aij, bi, et cj constituent la quantité de ressources dépensées de type i pour la réalisation d’une activité de type j, la quantité de ressources limitées de type i et la performance obtenue lors de la réalisation d’une activité de type j, respectivement. Tous les développements ultérieurs dans ce cours seront établis sous la condition fondamentale de non-négativité de l’ensemble des variables, condition qui est imposée a priori dans la plupart des problèmes économiques, et à laquelle on peut d’ailleurs toujours se ramener. Les méthodes de calcul s’appuient sur cette condition de non-négativité et font jouer aux contraintes xj ≥ 0 un rôle particulier.
Algorithme en programmation linéaire
En mathématiques, les problèmes de programmation linéaire PL sont des problèmes d’optimisation où la fonction objectif et les contraintes qui représentent les conditionnalités sont toutes linéaires. La programmation linéaire est alors un domaine central de l’optimisation, car les problèmes de PL sont les plus faciles du fait que toutes les contraintes y étant linéaires. Beaucoup de problèmes réels de la recherche opérationnelle peuvent être exprimés comme un problème de PL. Pour cette raison un grand nombre d’algorithmes pour la résolution d’autres problèmes d’optimisation sont fondés sur la résolution de problèmes linéaires. Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées en variables réelles. S’il est nécessaire d’utiliser des variables discrètes dans la modélisation du problème, on parle de programmation linéaire en nombres entiers. La programmation consiste alors à déterminer disons n-variables afin d’optimiser l’objectif linéaire sous différentes contraintes traduites dans la pratique sous forme d’inégalités ou égalités, étant donné que ces dernières nécessitent l’utilisation des ressources ou moyens limités dans l’obtention de l’objectif. Le nombre de contraintes allant de 1 à m. De telles contraintes permettent d’inclure des contraintes de signe, ou l’adoption de l’écriture matricielle. D’un point de vue géométrique, comme nous l’avons déja présenté plus haut, les contraintes linéaires forment un polyèdre convexe. Si la fonction objectif est elle aussi linéaire, tous les optimaux locaux sont également des optimaux globaux. De nombreuses difficultés peuvent se présenter dans la recherche ou le calcul de cet objectif, pour ne citer que les deux cas où il n’existe pas de solution optimale. Le premier est lorsque les contraintes se contredisent mutuellement (par exemple). Dans un tel cas, le polytope est vide et il n’y a pas de solution optimale puisqu’il n’y a pas de solution du tout. Le PL est alors infaisable ou incompatible. Une autre situation où le polyèdre est non-borné dans la direction définie par la fonction objectif. Dans ce cas, il n’y a pas de solution optimale puisqu’il est possible de construire des solutions satisfaisant les contraintes avec des valeurs arbitrairement élevées (ou basses) de la fonction objectif.
Genèse de l’algorithme de PPL
Quant à la recherche ou la détermination de l’objectif, l’algorithme du simplexe de G. Dantzig [1.04] est le plus connu pour résoudre les problèmes de PL en construisant tout d’abord une solution réalisable qui est un sommet du polytope puis en se déplacant selon les arêtes du polytope pour atteindre des sommets pour lesquels la valeur de l’objectif est de plus en plus grande, jusqu’à atteindre l’optimum. Bien que cet algorithme soit efficace en pratique et qu’il soit assuré de trouver l’optimum, sa démarche dans le pire cas peut être mauvaise. Il est ainsi possible de construire un PL pour lequel la méthode du simplexe requiert un nombre d’étapes exponentiel en la taille du problème. Le premier algorithme polynomial pour la PL a été proposé par L. Khachiyan [1.05] en 1979. Il est basé sur la méthode de l’ellipsoide en optimisation non linéaire précédemment proposée par N. Shor [1.06] . Cette méthode est elle-meme une généralisation de la méthode de l’ellipso¨ıde en optimisation convexe due à A. Nemirovski [1.07] . Cependant, l’efficacité pratique de l’algorithme de L. Khachiyan [1.08] est décevante : l’algorithme du simplexe est pratiquement toujours plus performant. En revanche, ce résultat a encouragé la recherche dans les méthodes de point intérieur. Par opposition à l’algorithme du simplexe qui considère uniquement la frontière du polytope définie par les contraintes, les méthodes de point intérieur évoluent à l’intérieur du polytope. En 1984, N. Karmarkar [1.09] propose la méthode projective. C’est le premier algorithme efficace à la fois en théorie et en pratique. Sa complexité dans le pire cas est polynomiale et les expérimentations sur les problèmes pratiques montrent que la méthode peut raisonnablement être comparée à l’algorithme du simplexe. Depuis lors, plusieurs méthodes de point intérieur ont été proposées et étudiées. Une des méthodes les plus célèbres est la méthode prédictive/corrective qui fonctionne très bien en pratique meme si son étude théorique est encore imparfaite. Pour la résolution pratique de problèmes de PL ordinaires, il est actuellement commun de considérer comme équivalentes les (bons) codes basés sur les méthodes dérivées du simplexe ou du point intérieur. De plus, pour la résolution de problèmes de grande taille, une technique comme la création de colonnes peut se révéler extrˆemement efficace. Les solveurs basés sur la PL sont de plus en plus utilisés pour l’optimisation de divers problèmes industriels tels que l’optimisation des flux de transports ou la planification de la production. Toutefois, les modèles de PL se révèlent insuffisants pour représenter de nombreux problèmes, la programmation linéaire en nombres entiers (PLNE) permet alors de modéliser un grand nombre de problèmes supplémentaires.
Quand on utilise le Solveur d’Excel, par exemple, pour résoudre les problèmes de Simplexe, on établit toutes les équations en donnant, par défaut, une valeur de 1, à tous les inconnus. Cela permet de calculer le bénéfice de la solution et l’utilisation des ressources dans les contraintes linéaires. C’est ensuite le travail du Solveur de changer les valeurs des variables pour maximiser, ou minimiser, selon le cas, la fonction objectif. L’avantage du Solveur d’Excel est qu’il est à la portée de tous et relativement facile à utiliser comparativement aux logiciels qui résolvent des problèmes de programmation linéaire comme ou Simplex, par l’entrée des données sous forme matricielle qui peut être rébarbative à beaucoup d’utilisateurs. Coté application, la programmation linéaire est essentiellement utilisée pour résoudre des problèmes d’optimisation à moyen et long terme (problèmes stratégiques et tactiques, dans le vocabulaire de la recherche opérationnelle). Les domaines d’application de ces problèmes sont très nombreux aussi bien dans la nature des problèmes abordés (planification et controle de la production, distribution dans des réseaux) que dans les secteurs d’industrie : industrie manufacturière, énergie (pétrole, gaz, électricité, nucléaire), transports (aériens, routiers et ferroviaires), télécommunications, industrie forestière, finance.
Les domaines d’application
La technique de la programmation linéaire est couramment appliquée dans l’industrie pétrolière. C’est l’une des industries, si ce n’est la principale qui utilise quotidiennement la PL (programmation linéaire). Elle est considérée comme l’outil qui permet au raffineur de faire la détermination optimale de production d’une raffinerie. Pour ce faire, le programme doit tenir compte d’un certain nombre de contraintes telles que :
– les bruts disponibles, leurs rendements et les qualités des coupes,
– les spécifications des produits àfabriquer,
– les limitations de débouchés pour certains produits,
– les capacités des unités,
– les modes de réglages des installations, – les capacités de stockage disponibles.
La PL peut également être utilisée dans d’autres domaines du raffinage, par exemple:
– les calculs de la composition optimale des mélanges de produits (carburants, gasoils, fuels) en tenant compte des spécifications.
– l’optimisation dans l’utilisation des installations,
– les calculs de l’obtention du meilleur préchauffage des bruts et des charges,
– la détermination du meilleur équilibre ”vapeur-électricité” d’une raffinerie. En dehors des raffineries, on peut utiliser la PL dans la recherche opérationnelle pour :
– batir des plans à long/moyen et court termes d’une compagnie pétrolière,
– optimiser le fonctionnement d’une flotte de tankers et la mise en place des produits. Ces différents éléments suscités et constatés nous ont emmenés à procéder à la réalisation de cette étude.
|
Table des matières
INTRODUCTION
CHAPITRE 1 THEORIES SUR L’OPTIMISATION SOUS CONTRAINTES
1.1 Introduction
1.2 Historique et évolution de Programmation linéaire
1.3 Définition de programmation linéaire (PL)
1.3.1 Quelques définitions
1.3.2 Notations et définitions
1.4 Géométrie de la programmation linéaire
1.4.1 Ensembles convexes, cônes, hyperplans, polyèdres et polytopes
1.4.2 Propriétés
1.4.3 Géométrie du programme linéaire
1.5 Optimisation sous contraintes
1.6 Algorithme en programmation linéaire
1.6.1 Genèse de l’algorithme de PPL
1.6.2 Les domaines d’application
1.6.3 Formulation ou modèlisation d’un PPL
1.7 Théorie de la complexité en programmation linéaire
1.7.1 Complexité
1.7.2 Complexité d’un problème et d’un algorithme
1.7.3 Classes de complexité
1.8 Identification des contraintes redondantes
1.8.1 Méthode des limites
1.8.2 Méthode de programmation linéaire
1.8.3 Méthode déterministe
1.8.4 Méthode heuristique
1.8.5 Earlier method
1.9 Conclusion
CHAPITRE 2 LES ELEMENTS DE BASE DE LA THEORIE TOPOGEOMETRIQUE MZ LES CLASSES D’OBJET DE MZ
2.1 Introduction
2.2 Les objectifs alimentés
2.2.1 Définitions et premiers exemples, ouverts
2.2.2 Les scalaires
2.2.3 Les indexes
2.3 Les objets élémentaires
2.3.1 Les espace des décisions
2.3.2 Postulat
2.4 Les opérations sur les décision-action
2.4.1 Amplificateur d’une décision-action
2.4.2 Addition de deux decision-actions
2.4.3 Axe de recherche partant d’une decision-action Xo et de direction le vecteur decisionaction V
2.4.4 Plan de recherche partant d’une decision-actions X0 et de directions V1 et V2
2.4.5 Cone de recherche de sommet X0 et de direction V1, V2,…., Vk où V1, V2,…., Vk sont des vecteurs decisions
2.5 Les contraintes techniques
2.6 Les contraintes de non-négativité
2.6.1 Cône de non-négativité
2.6.2 Face de non-négativité
2.6.3 Axes de non-négativité
2.7 Relation entre objet MZ
2.7.1 Relation entre un point-décision et une zone de contraintes techniques
2.7.2 Relation entre un axe de recherche R(X0, V) et une zone de contraintes technique ZCTi
2.7.3 Relation entre un cône plan de recherche C (Xo, V1, V2) avec V1 etV2 linéairement indépendants et une zone de contraintes technique ZCTi
2.7.4 Recherche suivant un axe R(Xo,V) dans la zone de non négativité ZNN
2.8 Conclusion
CHAPITRE 3 INTERSECTION ET PARALLELISME ENTRE CONTRAINTES TECHNIQUES ET LE CONE DE NON NEGATIVITE
3.1 Introduction
3.2 Projection de l’origine O sur la frontière de ZCTi
3.2.1 Cas où ?i se trouve a l’extérieur de C0+
3.2.2 Cas où JN≠∅ et JP≠∅
3.2.3 Cas où ?i se trouve à l’intérieur de C0+
3.3 Intersection entre ZCTi et l’axe de recherche R (O, Uk)
3.4 Parallélisme entre deux zones de contraintes techniques
3.5 Etude de cas de parallélisme entre deux zones de contraintes techniques différentes avec le langage MZ
3.5.1 cas où (?i∈C0+) et (?j∈C0+) et (?i≠ ?j) et (Aj=αAi avec α<0) et (?i plus proche de 0 que ?j)
3.5.2 Cas où (?i∈C0-) et (?j∈C0-) et (?i= ?j) et (Aj=αAi avec α>0 )
3.5.3 Cas où (?i∈C0-) et (?j∈C0-) et (?i= ?j) et (Aj=αAi avec α<0)
3.6 Conclusion
CHAPITRE 4 PSEUDO-PARALLELISME ENTRE DEUX ZONES DE CONTRAINTES TECHNIQUES DANS C0+
4.1 Introduction
4.2 Pseudo-parallélisme entre deux zones de contraintes techniques
4.3 Pseudo-parallélisme dans C0+
4.4 Intersection entre HP (Ai, bi) et R (O, Uk) ou R (O,-Uk)
4.4.1 Cas où ? i se trouve dans C0+ \ {0}
4.4.2 Cas où ?i ∈ (C0 / C0-) / {0}
4.5 Résumés
4.5.1 Résumé 1
4.5.2 Résumé 2
4.6 Pseudo- parallélisme pour une contrainte donnée « i »
4.6.1 Disposition de HP (Ai, bi) de ZCTi
4.6.2 Cas où HP(Ai, bi) intersecte tous les R (O, Uk)
4.6.3 Pseudo-parallélisme entre ZCTi et ZCTj plus proche de O
4.6.4 Pseudo-parallélisme entre ZCTi et ZCTj plus éloignés de O
4.6.5 Cas où HP (Ai, bi) intersecte R (O, Uk1), R(O, Uk2),…, R(O, Ukn) et pour les autres k
4.7 Conclusion
CONNCLUSION
