1 Qu'est-ce qu'un programme linéaire

1.1 Application linéaire tangente

1. La dérivée d'une fonction (dérivable) est la pente de la tangente à la courbe. En désigne 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 !

   Figure: Distinguer $\Delta y\protect$ 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 Quelques rappels sur les symboles de Landau

1. Objectif : rappeler quelques propriétés des symboles $\mathrm{O}\left( f \right)$, $\mathrm{o}\left( f \right)$, $\sim$ et $\Theta$.
2. Caveat. La notation de Landau (qui s'est imposée comme standard de fait) n'est pas des plus heureuse. En effet les deux relations $g_{1}=f+\mathrm{o}\left( f \right)$ et $g_{2}=f+\mathrm{o}\left( f \right)$ n'impliquent pas que $g_{1}=g_{2}$. Il vaut mieux les lire et les comprendre comme $g_{1}-f\in \mathrm{o}\left( f \right)$ et $g_{2}-f\in \mathrm{o}\left( f \right)$, avec pour conséquence $g_{2}-g_{1}\in \mathrm{o}\left( f \right)$.
3. Définition $\sim$. La relation "$f\sim g$ quand $x\rightarrow 0$" est définie par :
   $$\forall x : \left( f\left( x\right) =0 \Leftrightarrow g... ...eft( x\right) }\right/ \mid x\rightarrow 0, f\left( x\right) \neq 0\right] =1$$
   exo 1.  Quelles sont les fonctions telles que $f\sim 0$ ?
   exo 2.  Montrer que cette définition équivaut à l'existence d'une fonction $q$ telle que $f\left( x\right) =g\left( x\right) \times q\left( x\right)$ avec $q\left( x\right) \rightarrow 1$.
4. Théorème $\sim$. La relation $\sim$ est une équivalence, et elle est compatible avec le produit.
5. Rappel : équivalence. Une relation d'équivalence est une relation reflexive, symétrique et transitive, i.e. :
   

   $$R : \forall x x\sim x$$

   $$S : \forall x, y x\sim y \implies y\sim x$$

   $$T : \forall x, y, z \left( x\sim y \mathrm{et} y\sim z\right) \implies x\sim z$$

   
   

6. Rappel : compatibilité. Dire qu'une relation d'équivalence est compatible avec une opération $\perp$est :
   $$\left( a\sim c \mathrm{et} b\sim d\right) \implies \left( a\perp b \sim c\perp d\right)$$
   Autrement dit, on peut remplacer des équivalents par des équivalents.
7. Définition $\mathrm{O}\left( f \right)$. La relation "$f$ contrôle $g$", notée $g\in \mathrm{O}\left( f \right)$, est définie par l'existence d'un facteur de contrôle, i.e.
   $$\forall x : \left\vert g\left( x\right) \right\vert \leq k \left\vert f\left( x\right) \right\vert$$
   exo 3.  Montrer que cette relation est RT, mais pas S.
8. Définition $\Theta$. On dit que deux fonctions sont du même ordre lorsque $f\in \mathrm{O}\left( g \right)$ et $g\in \mathrm{O}\left( f \right)$. exo 4.  Montrer que cette relation est RST, i.e. est une équivalence.
9. Définition $\mathrm{o}\left( f \right)$. La relation "$g$ est négligeable devant $f$", notée $g\in \mathrm{o}\left( f \right)$, est définie par l'existence d'une fonction de "négligeabilité" $\varepsilon$, i.e.
   $$\forall x : g\left( x\right) =f\left( x\right) \times \varepsilon \left( x\right) \; \mathrm{et}\; \varepsilon \left( x\right) \rightarrow 0$$
   exo 5.  Cette relation est elle R, S ou T ?
10. Théorème. Les ensembles $\mathrm{O}\left( f \right)$ et $\mathrm{o}\left( f \right)$ sont clos par combinaisons linéaires.

1.3 Un exemple caricatural

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}\geq 0$ et que $x_{2}\geq 0$.
3. Ensuite, on peut imaginer des contraintes liées à la saturation du marché, conduisant par exemple à $x_{1}\leq 1000$ et $x_{2}\leq 500$, et une contrainte de fabrication $3 x_{1}+6 x_{2}\leq 4200$.
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. 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.

   Figure 2: Polygone admissible.

   

7. Les deux droites de la FIG. 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)$.

   Figure 3: Point optimal.

   

1.4 Ensembles convexes

1. Définition. On dit qu'une partie $A$ de $\mathbb{R}^{n}$ est convexe lorsque $x, y\in A$ implique $\left[ a, b\right] \subset A$.
2. Propriété. L'intersection d'un nombre quelconque de convexes est encore convexe (et éventuellement vide...).
3. Définition. 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$.
4. Théorème. 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.
5. Remarque. Le maximum est atteint par exactement tous les points appartenant à l'enveloppe convexe des sommets optimaux (hyper-arête du polytope).
6. Remarque. 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.