Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Recherche Opérationnelle Programmation linéaire Notes de cours Imed KHEMILI / 2

Recherche Opérationnelle Programmation linéaire Notes de cours Imed KHEMILI / 2014 1 1. PROGRAMMATION LINÉAIRE La programmation linéaire est une des techniques les plus remarquables utilisées en recherche opérationnelle. Depuis quelques dizaines d’années elle s’est développée à une vitesse foudroyante pour devenir un outil de gestion indispensable dans plusieurs entreprises modernes et dans différents domaines tels que la gestion de production, l’informatique, la télécommunication,… Elle consiste à l’optimisation d’un problème industriel ou économique modélisé par un modèle mathématique linéaire. Plus précisément, la programmation linéaire consiste à optimiser une fonction économique linéaire (fonction objectif), tout en respectant un certain nombre d’équations ou d’inéquations linéaires (contraintes). En effet, lorsque toutes les fonctions du problème mathématique général :   0 min (max) ( ) ( ) , , , 1,..., sujet à i i f g b i m X X X      sont linéaires, on dit qu’on a un problème de programmation linéaire, ou plus familièrement, un programme linéaire (PL). Dans ce cours, on étudie en détails une méthode itérative très efficace pour obtenir la solution optimale d’un problème de programmation linéaire. Elle a été développée par George DANTZIG en 1974 et elle est connue sous le nom de « méthode du simplexe ». 1.1 Forme générale d’un programme linéaire Le problème de programmation linéaire général peut être formulé comme suit : on désire trouver la valeur de n variables de décision non négatives, , 1,..., j x j n  , satisfaisant m équations ou inéquations linéaires (contraintes) : 11 1 12 2 1 1 1 1 2 2 1,1 1 1,2 2 1, 1 ... ... ... n n k k kn n k k k k n n k a x a x a x b a x a x a x b a x a x a x b                 1 1 2 2 1,1 1 1,2 2 1, 1 1 1 2 2 ... ... ... n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b                 (1.1) tout en minimisant ou maximisant une fonction économique linéaire : 1 1 2 2 1 ... n j j n n j Z c x c x c x c x        . (1.2) Tous les paramètres ( , , ij i j a b c ) sont des constantes connues. Recherche Opérationnelle Programmation linéaire Notes de cours Imed KHEMILI / 2014 2 1.2 Forme canonique et standard d’un programme linéaire 1.2.1 Forme canonique On dit qu’un programme linéaire est sous la forme canonique si on a un problème de maximisation, toutes les contraintes sont du type “  ” et les variables de décisions sont non négatives, soit le modèle suivant : 1 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 ... ... ... 0 sujet à : n j j j n n n n m m mn n m j Max Z c x a x a x a x b a x a x a x b a x a x a x b x                              (1.3) Remarque : tout problème de programmation linéaire peut être mis sous la forme canonique grâce aux transformations suivantes : - Transformer les variables négatives en variables positives, en remplaçant i x par ' i i x x  . S’il y a des variables sans contraintes de signes, on pose i i i x x x     où max( ,0) i i x x  et max( ,0). i i x x   Les nouvelles variables , i i x x  sont évidemment positives. - Transformer les contraintes de type “  ” en inégalités de type “  ” en les multipliant par -1. - Remplacer les contraintes de type “  ” par deux contraintes une de type “  ”, l’autre de type “  ”. - Passer de Min vers Max (si l’optimisation est une minimisation) en posantW Z  . On aura donc ( ) ( ) Min Z Max Z Max W    . Exemple : 1 3 1 2 3 2 3 1 3 2 3 2 3 2 4 5 0 0 sujet à : , Min Z x x x x x x x x x x                      1 3 ' 1 2 3 ' 2 3 ' 2 3 ' 1 2 3 3 2 3 2 4 5 4 5 , , 0 sujet à : Max W x x x x x x x x x x x x                       . 1.2.2 Forme standard On dit qu’un programme linéaire est sous la forme standard si on a un problème de maximisation, toutes les contraintes sont du type “ ” et les variables de décisions sont non négatives, soit le modèle suivant : Recherche Opérationnelle Programmation linéaire Notes de cours Imed KHEMILI / 2014 3 1 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 ... ... ... 0 sujet à : n j j j n n n n m m mn n m j Max Z c x a x a x a x b a x a x a x b a x a x a x b x                              Remarque : Pour pouvoir résoudre un programme linéaire, il faut passer obligatoirement par la forme standard. Ce passage (de forme canonique vers la forme standard) nécessite l’utilisation de ce qu’on appelle variables d’écarts (positives ou nulles). Tout problème de programmation linéaire peut être mis sous la forme standard grâce aux transformations suivantes : - Transformer les variables négatives en variables positives comme on a présenté précédemment. - Transformer les contraintes de type “  ” en inégalités de type “  ” en les multipliant par -1. - Transformer les contraintes de type “  ” en égalités de type “ = ” en introduisant une nouvelle variable positive, n i x  dite variable d’écart, dans la contrainte i. - Pondérer les variables d’écarts par zéro dans la fonction objectif. La forme standard du modèle (1.3) est : 1 1 2 2 1 1 11 1 12 2 1 1 1 21 1 22 2 2 2 2 ... 0 ... 0 ... ... sujet à : n m j j n n n n m j n n n n n n Max Z c x c x c x c x x x a x a x a x x b a x a x a x x b                          1 1 2 2 ... 0 m m mn n n m m j a x a x a x x b x                     (1.4) Exemple : Soit le (PL) : 1 2 1 2 1 2 1 2 3 2 2 4 5 0 sujet à : , Max Z x x x x x x x x                  la forme standard est : 1 2 1 2 3 1 2 4 1 2 3 4 3 2 2 4 5 , 0 sujet à : , , Max Z x x x x x x x x x x x x                   . Recherche Opérationnelle Programmation linéaire Notes de cours Imed KHEMILI / 2014 4 1.3 Écriture matricielle d’un programme linéaire En écriture matricielle, la forme canonique d’un programme linéaire est la suivante : : 0 T Max Z Sujet à           C X AX B X . Pour le programme linéaire (1.3) : 1 n c c       uploads/s3/ chap-1-formulation-d-x27-un-programme-lineaire.pdf