Remerciez-le!

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

1/8 Chap. : Programmation linéaire 1. La programmation linéaire La programmatio

1/8 Chap. : Programmation linéaire 1. La programmation linéaire La programmation linéaire (P.L.) est un processus d’aide à la décision qui permet de trouver une solution optimale (si elle existe) grâce à la modélisation mathématique. La modélisation mathématique peut se décliner en plusieurs types d’optimisation : la programmation linéaire, la programmation non linéaire, le contrôle optimal… Nous traiterons ici la programmation linéaire. On aborde dans ce cours la programmation linéaire appliquée à l’économie et la gestion avec le but :  De modéliser un problème économique en un problème de programmation linéaire ;  D’optimiser une fonction sous contraintes ;  D’interpréter en terme économique les résultats fournis par la programmation linéaire. Un modèle est une représentation de la réalité qui capture « l’essence » de la réalité, i.e. l’angle qui nous intéresse. La programmation linéaire est un outil qui permet de résoudre les cas les plus simples. Le but essentiel est d’introduire le principe de modélisation et le rôle de la programmation mathématique. Dans la réalité, la programmation mathématique utilisée est souvent plus complexe que la programmation linéaire (programmation non linéaire, programmation probabiliste, contrôle optimal) et les calculs se font informatiquement. Formulation d’un problème de programmation linéaire (P.L.) : En P.L. la fonction à optimiser et les contraintes à respecter sont linéaires (variables au premier degré). La forme canonique générale d’un problème de P.L. est la suivante : Min ou Max    n j j jx c z 1 (1)   n j j ijx t 1  i d p i ,..., 1  (2)   n j j ijx t 1  i d m p i ,..., 1   (3) j x  0 q j ,... 1  (4) j x signe quelconque n q j ,..., 1   (5) Avec i j i j d t c , , constantes et j x variables. La fonction    n i j j x c z 1 s’appelle la fonction économique ou fonction objective ou critère. Les inéquations (2) et équations (3) sont les contraintes réelles. Les inéquations (4) sont les contraintes de non négativité. La fonction à optimiser peut être soit une fonction à minimiser, soit une fonction à maximiser. On présente ici les cas généraux de minimisation et de maximisation avec l’interprétation économique de chaque élément du programme. Exercice : Montrer que toutes les contraintes peuvent se mettre sous la forme (2) ou (3) seulement. 2/8 1.2.1 Minimisation d’un coût sous des obligations de fonctionnement    n j j jx c z 1 min   n j j ijx t 1  i d m i ,..., 1  j x  0 n j ,..., 1  1. Première interprétation : : i bien produit : j activité i d : demande de bien i à satisfaire ij t : taux de production du bien i par l’activité j : j c coût unitaire de l’activité j j x : niveau de l’activité j 2. Deuxième interprétation : : i activité : j bien consommé (matière premières) : i d niveau minimum de fonctionnement de l’activité i : ij t taux de fonctionnement de l’activité i pour la consommation du bien j : j c coût unitaire du bien j : j x quantité consommée de bien j 1.2.2 Maximisation d’un gain sous des contraintes de capacité    n j j jx c z 1 max   n j j ijx t 1  i d m i ,..., 1  j x  0 n j ,..., 1  1. Première interprétation : : i bien consommé et : j activité i d : quantité disponible de bien i ij t : taux d’utilisation du bien i par l’activité j : j c gain unitaire de l’activité j j x : niveau de l’activité j 3/8 2. Deuxième interprétation : : i activité : j bien produit i d : capacité maximum de fonctionnement de l’activité i ij t : taux de fonctionnement de l’activité i pour la production du bien j : j c gain unitaire du bien j j x : quantité produite de bien j 1.3 Caractérisation des solutions admissibles  Une solution est admissible ou réalisable si elle satisfait toutes les contraintes.  La région admissible est l’ensemble IP des solutions admissibles ou réalisables.  Une solution optimale est une solution admissible qui optimise la fonction d’optimisation. Définition (contrainte saturée ou serrée ou active) Une contrainte d’inégalité est dite saturée (ou serrée) pour une solution si elle est vérifiée avec le signe d’égalité et non saturée (ou non serrée) si elle est vérifiée avec le signe d’inégalité stricte. Définition : Un polyèdre convexe est l’intersection (éventuellement vide) d’un nombre fini de demi-espaces fermés et/ou d’hyperplans. Théorème 1 : L’ensemble des solutions IP admissibles d’un problème de programmation linéaire est soit :  un ensemble vide, (c’est-à-dire que le problème est mal posé et n’a pas de solution)  un polyèdre convexe, non vide borné ou non. 1.4.Caractérisation géométrique des solutions optimales Théorème 2 : 1. Si l’ensemble des solutions IP est un polyèdre convexe non vide :  Soit la solution optimale est unique et est située en un sommet de IP ;  Soit il existe une infinité de solutions optimales qui sont les points d’une face de IP ; ces solutions optimales sont donc combinaisons convexes d’un nombre fini de sommets. 2. Si IP est un ensemble vide, le problème n’a pas de solution optimale. 1.5. Résolution graphique d’un P.L. La résolution graphique d’un programme linéaire ne peut se faire que pour la dimension 2 (et éventuellement 3). Elle est donc peu efficace mais permet de bien comprendre le rôle de la programmation linéaire. Les étapes sont : 1. Tracer le domaine des solutions admissibles en traçant les droites frontières puis en hachurant les demi-plans non solution ; 2. La solution optimale est située en au moins un sommet du polyèdre des solutions admissibles ou réalisable IP. 3. Si IP est vide alors le problème n’a pas de solution. 4/8 2. Dualité A chaque contrainte, on peut associer un nombre positif appelé « prix dual ». Les prix duaux permettent de localier les modes d’extension les plus profitables. Définition : (Les prix duaux comme accroissement marginaux de la fonction économique) Le prix dual associé à la contrainte i est la variation de la fonction économique pour une variation unitaire du second membre de la contrainte i . Localisation de la marge et du profit sur les facteurs fixes On considère ici un problème de maximisation de marge sur coût variable. Les prix duaux sont donc la contribution marginale apportée par une extension de capacité. En terme de profit, pour savoir si une extension est profitable, il faut comparer le prix dual de la contrainte i à son prix d’usage unitaire, i.e. l’accroissement des coûts fixes (équipements,…) nécessaires pour l’extension d’une unité de la contrainte correspondante. On rappelle que cette règle de décision n’est valable que localement, dans le domaine de validité de l’extension. On a alors la règle de décision : Profit = Prix dual – Prix d’usage > 0 l’extension est profitable. Profit = Prix dual – Prix d’usage ≤ 0 l’extension n’est pas profitable. Définition : (Primal – dual) On considère le problème de maximisation suivant sous sa forme canonique: (P) :    n j j jx c z 1 max   n j j ijx t 1  i d m i ,..., 1  j x  0 n j ,..., 1  On appelle programme dual (canonique) de (P) le programme linéaire suivant : (D) :    m i i i y d z 1 ' min   m i i ji y t 1  cj n j ,..., 1  i y  0 m i ,..., 1  Les formes matricielles des programmes (P) et (D) s’écrivent respectivement : Primal : (P) :  x c z . max  (1) d x T  . (2) 0  x (3) Dual : (D) :  d y z . ' min  (4) c y T t t  . (5) 0  y (6) 5/8 Règles de détermination du dual en fonction du primal et vice versa : Les observations suivantes permettent d’obtenir le dual connaissant le primal et vice versa. 1°) Les programmes (P) et (D) sont dits primal et dual et vice versa. 2°) Si (P) est à maximiser alors (D) est à minimiser et vice versa. 3°) Les inégalités de (P) et (D) sont de sens opposés. 4°) Les seconds membres de (P) sont les coefficients de la fonction économique de (D) et vice versa 5°) Les coefficients des lignes des contraintes de (P) sont les coefficients des colonnes des contraintes de (D) et vice versa. 6°) Il y a autant de variables duales dans (D) que de contraintes dans le primal (P) uploads/Voyage/ chap-programmation-lineaire.pdf