PRODUCTION DE PUISSANCE ACTIVE
DANS UN RESEAU D’ENERGIE ELECTRIQUE

FORMALISATION D’UN PROGRAMME LINEAIRE

Principe

La formalisation d’un programme linéaire est une tâche délicate mais essentielle car elle conditionne la découverte ultérieure de la bonne solution. Il faut d’abord bien comprendre le problème à résoudre puisque la formalisation comporte les mêmes étapes à savoir : 1. la détection du problème et l’identification des variables. Ces variables doivent correspondre exactement aux préoccupations du responsable de la décision. 2. la formulation des contraintes. Ce sont les limites que le responsable ne peut enfreindre. Elles revêtent la forme d’équations ou d’inéquations. 3. la formulation de la fonction économique (ou fonction objectif) traduisant les préférences du décideur sous la forme d’une fonction des variables identifiées. 6.2.2 Techniques de la formalisation Un programme linéaire se présente sous l’aspect d’un système de m équations linéaires à n inconnues et d’une fonction économique Z qui est une forme linéaire à optimiser, c’est-à-dire à maximiser ou à minimiser selon le contexte. De façon générale , un problème de programmation linéaire met en jeu quatre catégories d’éléments. Soient : – aij : la quantité de ressource i pour effectuer l’activité j, c’est le coefficient technique qui sera supposé constant. – bi : la quantité totale de ressource i disponible, c’est le facteur limitant. – xj : la quantité de produit j à fabriquer pour réaliser l’objectif : c’est l’inconnu. – cj : le coefficient économique pour une unité de l’activité j. Les contraintes relatives aux ressources disponibles sont formalisées par un système d’équations, une équation pour chaque ressource i : ≤ = = ≥ ∑= a x bi où i m n j ii j 1,2,…, 1 Les conditions suivantes sont à respecter : x j ≥ 0 pour j=1,..,n. 45 Selon le cas, la fonction économique est à minimiser ou à maximiser, on écrit alors : [ ] [ ] ∑ ∑ = = = = n j j j n j j j Min Z c x ou Max Z c x 1 1 En notation matricielle, on a : ƒ les contraintes sont : [A] [X] ≤ [B] ƒ sous les conditions : [X] ≥ 0 ƒ les fonctions économiques : [Max] Z = [C] [X] ou [Min] Z = [C] [X] avec : [X] : est le vecteur colonne des variables j x [A] : est la matrice des coefficients techniques :aij [B] : est le vecteur colonne des limites des ressources [C] : est le vecteur ligne des coefficients économiques cj. 6.3 METHODES DE RESOLUTION 6.3.1 Méthode graphique ou géométrique Cette méthode s’applique aux problèmes d’ordre peu élevé. Il s’agit de représenter graphiquement les équations traduisant les contraintes dans un repère orthonormé direct. Théorèmes généraux On admettra les théorèmes suivants : Théorème 1 Une intersection finie de demi-plan détermine un polygone convexe de sommets M1,M2,…Mn. Théorème 2 46 Si f(x1,x2) est une fonction affine de 2 variables (x1,x2) définie dans un polygone convexe (S)=M1,m2,…,Mn, alors le maximum et le minimum de f dans (S) sont atteints en des sommets de (S). 6.3.2 Méthode de SIMPLEXE 6.3.2.1 Méthode ALGEBRIQUE 1-Terminologie On appelle « écriture canonique » des programmes linéaires les formes suivantes : [Min] ou [Max] Z avec ∑= = n j j j Z c x 1 . sous les contraintes : ∑= ≤ n j ij j i a x b 1 . pour i=1,…,m et sous les conditions : x j ≥ 0 pour j=1,…,n L’ensemble des points M(x1,…,xn) qui vérifient les contraintes et les conditions de positivité est appelé « ensemble des solutions noté (S) ». Ils correspondent aux programmes de production qui sont possibles. Nous avons vu que (S) est un polygone convexe délimité par des crêtes. Dans la résolution algébrique d’un programme linéaire, lorsqu’il y a plus d’inconnues que d’équations, certaines inconnues seront considérées comme des paramètres. On retient les vocabulaires ci-après : • variable de base : une variable principale positive ou nulle. • Variable hors base : une variable non principale nulle. • Variable d’écart : des variables introduites pour transformer les inéquations en équations. • Solution de base : considérons un programme linéaire à n variables et m contraintes sous forme d’équations. Toute solution à ce système de contraintes, composé de m variables de base positives et (n-m) variables hors base est dite solution de base. • Solution de base dégénérée : une solution de base dont une variable de base au moins est nulle. 47 2-Les différents critères a) Critère de maximalité Un programme est maximal si dans l’expression de Z, tous les coefficients des variables hors base sont négatifs. b) Critère de choix de la variable entrante La variable hors base qui entrera dans le prochain programme (ou solution) de base est celle qui, dans l’expression de Z, aura le plus grand coefficient positif. c) Critère de choix de la variable sortante Pour choisir l’équation dans laquelle la nouvelle variable, notons xi0 entrera, on écrit d’abord le système d’équations en mettant les bj aux seconds membres, puis on divise bj par les coefficients positifs de xi0 et on prend l’équation donnant le plus petit quotient. 6.3.2.2 Méthode des TABLEAUX Cette méthode simplifiera beaucoup la présentation de la méthode du SIMPLEXE que nous avons déjà aperçue dans la méthode algébrique. Il faudra comprendre un tableau comme une représentation d’un système d’équations et pour passer d’un tableau à un autre, on appliquera les trois critères cités dans la méthode algébrique.