Recherche Opérationnelle - Optimisation Linéaire - PDF

Recherche Opérationnelle Optimisation Linéaire Dr. Rodrique KAFANDO [email protected] 1 rodrique kafando, PhD Prog...

Recherche Opérationnelle Optimisation Linéaire Dr. Rodrique KAFANDO [email protected] 1 rodrique kafando, PhD Programmation Linéaire 2 rodrique kafando, PhD P. Linéaire Problème On veut acheter 4 types d'alimentations A, B, C et D qui ont chacun une teneur en calories et en vitamines comme suite : 3 rodrique kafando, PhD P. Linéaire But Le consommateur cherche à minimiser le coût sachant qu'il a besoin d'au moins 12 calories et 7 vitamines. Modélisation 4 rodrique kafando, PhD P. Linéaire Formulation Note: 5 rodrique kafando, PhD P. Linéaire Forme standard d’un PL 6 rodrique kafando, PhD P. Linéaire Exemple 7 rodrique kafando, PhD P. Linéaire Exemple Demo 8 rodrique kafando, PhD  9 rodrique kafando, PhD P. Linéaire Exemple Demo 10 rodrique kafando, PhD P. Linéaire Exemple Demo 11 rodrique kafando, PhD P. Linéaire Exemple Demo 12 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. 13 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. Forme standard 14 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Principe de la méthode simplex La résolution de (PL) se fait en se déplaçant de solution de base réalisable non optimale en solution de base réalisable et optimale. Forme standard 15 rodrique kafando, PhD  16 rodrique kafando, PhD  17 rodrique kafando, PhD  18 rodrique kafando, PhD  19 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition On appelle base tout sous-matrice carrée régulière (m × m) extrait de A (il existe au moins une, puisque rg(A) = m ) Soit I une base. Alors en permutant les colonnes de A, on peut toujours mettre A sous la forme où est la sous matrice formée par les colonnes de A qui ne sont pas dans la base. De même on peut partitionner la variable x en et la fonction coût f en comme il montre la figure 20 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition On appelle base tout sous-matrice carrée régulière (m × m) extrait de A (il existe au moins une, puisque rg(A) = m ) (1) On appel solution de base (associé à la base AI ), la solution particulière de (1) obtenue on faisant xI = 0. On peut alors déterminer xI de façon unique par la résolution du système : 21 rodrique kafando, PhD P. Linéaire Algorithme primal de Simplex Définition Une solution de base est dite réalisable si xI ≥ 0, autrement dit si : (AI )−1.b ≥ 0. Une base correspondant à une solution de base réalisable est appelée base réalisable. Une solution de base est dite dégénéré si le vecteur xI à des composantes nulles. On a: 22 rodrique kafando, PhD  23 rodrique kafando, PhD  24 rodrique kafando, PhD  25 rodrique kafando, PhD  26 rodrique kafando, PhD  27 rodrique kafando, PhD P. Linéaire Algorithme de Simplex Le but de cet algorithme est de calculer la solution optimale d'un programme linéaire (PL) et la valeur correspondante v(PL). 28 rodrique kafando, PhD P. Linéaire Dualité en PL En programmation linéaire, la dualité est un principe puissant qui établit une relation entre deux programmes linéaires : un problème primaire et son problème dual associé. Chaque contrainte dans le problème primaire correspond à une variable dans le problème dual, et chaque variable primaire correspond à une contrainte dans le dual. Le Théorème de dualité stipule que si le problème primaire a une solution optimale, alors le problème dual a également une solution optimale, et les valeurs des deux fonctions objectifs à ces solutions optimales sont égales. 29 rodrique kafando, PhD P. Linéaire Dualité en PL On considère un problème linéaire (PL) mis sous forme standard : A est une matrice d'ordre (m × n). On définit le dual de (PL) comme suit : 30 rodrique kafando, PhD P. Linéaire Dualité en PL Le problème dual (D) peut s'écrire sous forme : Modélisation de divers duaux : le dual associé La détermination du dual d'un programme linéaire présenté sous forme canonique Nécessite son écriture sous forme standard 31 rodrique kafando, PhD P. Linéaire Dualité en PL C'est un programme linéaire sous forme canonique en minimisation 32 rodrique kafando, PhD P. Linéaire Dualité en PL Note : En estimant que le nombre d'itération de l'algorithme du simplex est Θ(m) (m nombre de contrainte). Si A est d'ordre m × n avec m >> n, il est clair que le résolution du problème dual apporte un gain en nombre d'opération par rapport à la résolution de (P). Si on note x et u les solutions optimales respectives du problème (P) et de son dual (D). 33 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 34 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 35 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 1 36 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 37 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 2 38 rodrique kafando, PhD P. Linéaire Dualité en PL Exemple 2 39 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 40 rodrique kafando, PhD P. Linéaire Dualité en PL Théorème : Etant donné un problème de programme linéaire (P) et (D) son problème dual alors : le dual du dual du programme linéaire (P) est identique à (P). 41 rodrique kafando, PhD  Recherche Opérationnelle Optimisation Linéaire Dr. Rodrique KAFANDO [email protected] 42 rodrique kafando, PhD