Module D108  : Programmation mathématique et optimsation
Programmation linéaire
Interprétation Géométrique

Point dans un espace
Interprétation de tous les concepts
Convexité
Solutions de base


Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 30 Janvier 2006

Point dans un espace

Il est très utile de considérer les $ n$ variables $ x_1,~\ldots,_n$ comme les coordonnées d'un point dans un espace de dimension $ n$. Ce point de vue permet souvent de comprendre mieux les problèmes et les algorithmes.

Interprétation de tous les concepts

Une solution n'est qu'un point dans l'espace.

Une contrainte (comme $ x_1+2x_2-x_3\le 0$) représente la division de l'espace par un plan (dans l'exemple le plan $ x_1+2x_2-x_3=0$); les points respectant la contrainte sont tous ceux sur le ``bon'' coté du plan plus ceux situés sur le plan (parce que la contrainte est du type $ \le $). Dans le cas $ n=2$, une contrainte n'est donnée par un plan mais par une ligne droite; dans les cas $ n>3$ c'est un hyperplan.

L'espace de toutes les solutions réalisables est l'intersection de tous les demi-espaces donnés par les contraintes; si cette intersection est vide le programme n'est pas faisable; s'il est fini l'intersection est un polygone (en dimension 2), un polyèdre (en dimension 3) ou un polytope (en dimension supérieure à 3); s'il est infini le programme risque de ne pas avoir une solution optimale parce qu'il n'y a pas de borne sur la fonction objective.

Maximiser la fonction objective correspond à aller le plus loin possible dans une direction préférée avec déplacements orthogonaux à cette direction permises; pour prendre un exemple simple en deux dimensions, maximiser $ x_1+x_2$ équivaut à se déplacer tant que possible dans le sens nord-est; toutes les directions plus à l'est que nord-ouest ou plus au nord que sud-est sont bonnes parce que leur composant dans le sens nord-est est strictement positif. Maintenant c'est clair que si l'espace de solutions faisables est fini, la fonction économique prend son maximum sur un bord de cet espace; on va voir davantage dans un instant.

Convexité

Quand l'espace de solutions réalisables n'est pas vide, il a une propriété importante, la convexité. Tout point situé sur le segment de ligne droite reliant deux solutions réalisables est lui-même aussi une solution réalisable. De la perspective géométrique ce fait est tout à fait évident; algébriquement, si on note qu'un point sur ce segment entre deux solutions $ x_1,\ldots,~x_n$ et $ y_1,\ldots,~y_n$ est donné par $ c*x_1+(1-c)*y_1,\ldots,~c*x_n+(1-c)*y_n$ pour une constante $ c$ avec $ 0\le c\le 1$, on peut démontrer facilement que si une contrainte linéaire est vérifiée à $ x_1,\ldots,~x_n$ et à $ y_1,\ldots,~y_n$, elle est vérifiée aussi aux solutions sur la ligne entre les deux.

Solutions de base

$ n$ équations linéaires en $ n$ variables, en général, déterminent une solution unique. ( D'autres cas sont possibles quand les équations ne sont pas linéairement indépendantes; soit aucune solution, soit plusieures.)
Une solution est de base si elle est la solution unique déterminée par $ n$ des contraintes, en remplaçant le $ \le $ de la contrainte par $ =$. Autrement dit une solution de base est l'intersection de $ n$ des plans (hyperplans) des contraintes; si les (hyper)plans n'ont pas un seul point comme intersection, ils ne donnent pas de solution de base.

Quand le programme est donné en forme canonique, les équations $ x_j=0$ des contraintes implicites $ x_j\ge 0$ peuvent entrer dans les $ n$ équations déterminant une solution de base.

Les solutions de base réalisables ne sont que les sommets (angles) du polytope de solutions réalisables.

Une propriété très importante pour la solution de programmes linéaires est que, (si le programme a une solution réalisable optimale), une des solutions réalisables de base est optimale. De la perspective géométrique cette propriété semble évidente.


 

Exercices

Questionnaire de compréhension immédiate

3 exercices