1. Programmation linéaire

1.1 Application linéaire tangente

Commençons par rappeler que la notion de fonction dérivée est issue de la notion de linéarisation, c'est à dire d'approximation par une fonction linéaire (FIG. 1.1).

1. La dérivée d'une fonction (dérivable) est la pente de la tangente à la courbe. En désignant par $\mathrm{d}x$ et $\mathrm{d}y$ les variations de coordonnées le long de la tangente, la relation
   $$\frac{\mathrm{d}y}{\mathrm{d}x}=p$$
   ne dépend pas du fait que $\mathrm{d}y$ soit petit ou non : une droite "va en ligne droite" sur toute sa longueur !

   FIG.: Distinguer $\Delta\, y$ et $\mathrm{d}y$ !

   

2. Par contre la relation $\frac{\Delta y}{\Delta x}\approx p$ dépend, elle, de ce que $\Delta x$ est supposé petit. Plus précisément, on a
   $$\Delta y=p\,\Delta x+\mathrm{o}\left(\Delta x\right)$$
   et cette formule n'est significative que dans un certain domaine de validité. En dehors de ce domaine, il faut changer de tangente.
3. Tout cela se généralise à des fonctions vectorielles d'une variable vectorielle. Dans ce cas la "pente" n'est plus un simple nombre, mais la matrice d'une application linéaire.

1.2 Un exemple caricatural

Voici un exemple d'optimisation sous contraintes. Cet exemple est deux fois caricatural. En premier lieu, il constitue un modèle bien trop simple pour pouvoir capturer la réalité d'un processus industriel réel. En second lieu, il est tellement simple que l'on peut en trouver la solution d'un seul coup, uniquement en traçant la figure correspondante. L'objectif poursuivi est simplement de décrire une problématique.

1. Soit à optimiser la production d'un atelier fabriquant deux sortes de produits. On se demande comment choisir les quantités $x_{1}$ et $x_{2}$ fabriquées de façon à optimiser le bénéfice $z=4\, x_{1}+12\, x_{2}$. Bien entendu, la réponse n'est pas $+\infty,\,+\infty$, car il y a inévitablement des contraintes sur les valeurs des $x_{j}$.
2. En premier lieu, il est clair que $x_{1}\geq0$ et que $x_{2}\geq0$.
3. Ensuite, on peut imaginer des contraintes liées à la saturation du marché, conduisant par exemple à $x_{1}\leq1000$ et $x_{2}\leq500$, et une contrainte de fabrication $3\, x_{1}+6\, x_{2}\leq4200$.
4. On voit tout de suite que $\left(0,\,0\right)$ est un point admissible (vérifiant toutes les contraintes). La question est de faire un meilleur bénéfice que 0 !
5. Chacune des contraintes a pour effet de séparer le plan en deux régions : un demi-plan ouvert où la contrainte n'est pas satisfaite et un demi-plan fermé (i.e. frontière comprise) où la contrainte est satisfaite. L'ensemble des points admissibles (i.e. vérifiant toutes les contraintes) est donc une surface polygonale convexe.
6. La FIG. 1.2 représente en grisé les régions du plan où l'une au moins des contraintes n'est pas satisfaite. L'ensemble des points admissibles apparaît en blanc sur la figure.

   FIG. 1.2: Polygone admissible.

   

7. Les deux droites de la FIG. 1.3 correspondent à $z=5000$ et $z=7600$. Il est clair que toutes les droites $z=Cte$ sont parallèles entre elles, et que $z$ augmentant, ces droites finissent par ne plus couper le polygone des points admissibles : le point cherché est donc le sommet $\left(400,\,500\right)$.

   FIG. 1.3: Point optimal.

   

1.3 Quelques remarques

Definition 1.3.1   Un système facile est un système tel que l'origine des coordonnées soit un point de fonctionnement du système (c.à.d. vérifie l'ensemble des contraintes). En pareil cas, le problème consiste à trouver le meilleur point de fonctionnement.

Remark 1.3.2   Lorsqu'un problème "n'est pas facile", il faut commencer par trouver un point de bon fonctionnement, ou bien démontrer qu'il ne peut exister de points de bon fonctionnement.

Remark 1.3.3   Contrainte égalité. Une égalité $f\left(M\right)=Cte$ ne peut pas être utilisée directement pour réduire le nombre de variables, car il faut continuer à exprimer les contraintes sur chaque variable.

Remark 1.3.4   Contrainte inégalité. Une telle contrainte peut être transformée en une égalité par introduction d'une nouvelle variable, en remplaçant $f\left(M\right)\leq Cte$ par $\left\{ f\left(M\right)+y=Cte\:;\:0\leq y\right\}$.

1.4 Ensembles convexes et "programmes linéaires"

Definition 1.4.1   Un "programme linéaire" est un modèle dans lequel à la fois les contraintes et la fonction objectif ont été modélisés par des fonctions du premier degré.

Definition 1.4.2   On dit qu'une partie $A$ de $\mathbb{R}^{n}$ est convexe lorsque $x,\, y\in A$ implique $\left[a,\, b\right]\subset A$.

Proposition 1.4.3   L'intersection d'un nombre quelconque de convexes est encore convexe (et éventuellement vide...).

Definition 1.4.4   L'enveloppe convexe d'un ensemble $A$ est le plus petit convexe contenant $A$. Cette enveloppe est l'intersection de tous les convexes contenant $A$.

Theorem 1.4.5   Le domaine de validation des contraintes d'un programme linéaire est un ensemble convexe à faces hyperplanes (polytope), et l'extremum de la fonction linéaire à optimiser est atteint en un ou plusieurs sommets du polytope.

Proposition 1.4.6   Le maximum est atteint par exactement tous les points appartenant à l'enveloppe convexe des sommets optimaux (hyper-arête du polytope).

Proposition 1.4.7   L'hyperplan $z=max$ est un hyperplan d'appui du polytope, c'est à dire qu'ils ont au moins un point en commun, et que tous leurs points communs sont des points frontière du polytope.