Il est très utile de considérer les variables
comme les coordonnées d'un point dans un espace de dimension
.
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
) représente la division de l'espace
par un plan (dans l'exemple le plan
); 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
).
Dans le cas
, une contrainte n'est donnée par un plan mais
par une ligne droite; dans les cas
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 é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.
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
et
est donné par
pour une constante
avec
, on peut démontrer facilement que si une contrainte
linéaire est vérifiée à
et à
,
elle est vérifiée aussi aux solutions sur la ligne entre les deux.
équations linéaires en
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 des contraintes, en remplaçant le
de la contrainte
par
.
Autrement dit une solution de base est l'intersection de
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
des contraintes implicites
peuvent entrer dans les
é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.