# Linear programming
## 1) Contexte
#### Objectif :
Optimiser l'achat de blé. maximiser un gains sous un nombres de contraintes.

max 3x + y       <- fonction objectif
(P) 2x + 3y <= 5 <- contraintes d'inégaliés linéaires 
    x - y <= 2   <- "" "" ""
x,y >= 0         <- contraintes de positivités

## 2) Explication generale
#### Definition :
Un point (x, y) qui satisfait les contraintes d'inégalités est dit **admissible**.
La valeur que prend la fonction objectif en un point admissible est dite **valeur objectif** de ce point.
## L'ensemble des points admissible de [P] est dit **lieu admissible** de [P].

---

**Un programme linéaire** est un problême d'optimisation sous la forme [P] o l'on cherche la plus grande valeur prise par la fonction objectif sur le lieu admissible de [P]. Cette plus grande valeur, quand elle existe, s'appelle **valeur optimale**.
S'il existe un point admissible qui réalise cette valeur optimal il est appelé **point optimal**.

Résoudre [P] signifie trouver la plus grande valeur que prend la fonction objectif sur la partie colorié en rouge: lieu aissible de (P).

## 3) Etude de cas

max 3x + y
2x + 3y <= 5
x - y <= 2
x,y >= 0

Ce type de probleme n'est en rien quelque chose auquel vous n'avez jamais fait face:

Soit
| -1 | 2 | 10 | 0 | 1 | 4 | 66 | 2 |
| - | - | - | - | - | - | - | - | - |
le tableau L et *f(x) = -x + 3*.

*On cherche l'indice i de L pour lequel f(L[i]) est la plus grande valeur possible pour tout i.*

On peut chercher à résoudre (de manière approchée) [P] en effectuant un maillage du lieu admissible de [P] .
Malheureusement cette démarche pourra difficilement être généralisée de manière efficace à toute dimension. Il faut chercher une autre solution !

`Est-il possible de limiter la zone de recherche ?
`
`Est-ce qu'un point optimal peut être à l'intérieur du lieu admissible de [P] ?`


On peut représenter f restreint au diamètre du cercle (en bleu) pour son graphe qui est le graphe d'une fonction de R dans R.


On peut donc représenter le graphe de la restriction de f à 'ligne bleue' sous une forme à gauche.

Dans le cas 'ligne rouge' et 'ligne noire', on voit que (x*, y*) ne sera pas optimal. Ce sera également le cas s'il existe un diamètre 'ligne bleue' pour lequel ces situations apparaissent.

Reste à comprendre le cas où sur tout diamètre on se retrouve avec une restriction de f qui est constante.

Dans ce cas (une fonction affine est donnée par ses valeurs sur les éléments d'une base) la fonction objective est constante et tout point admissible est optimal.

**En conclusion, on trouvera toujours des points optimaux sur le bord.**

---

En raisonnant par récurrence sur la dimension, on se ramènera toujours à chercher des points optimaux sur les arêtes qui composent le bord du lieu admissible.
On peut en fait aller encore plus loin. On appelle point extrémal de A tout point du bord qui ne peut être le centre d'un intervalle ouvert contenu dans A.

Si on n'est pas au point extrémal en raisonant comme précédemment, on se retrouve dans une situation où on trouve des points optimaux dans notre voisinage.

**Ainsi, un point optimal, quand il existe, correspond à un point extrémal.**

---

` Combien de points extrémaux on retrouve dans le lieu admissible du programme linéaire ?`

max : $\Sigma_{i = 1}^n x_{i}$

(Cn) sujet à :
$x_{i} \leq 1$, ∀ i $\in$ {1, ..., n}
$x_{i} \geq 0$, ∀ i $\in$ {1, ..., n}


Points extrémaux de (Cn) sont les points de la forme ($x_{1}, x_{n}$) avec $x_{i} \in$ {0, 1}. Il y en a $2^{n}$.

> Lire les deux 1er jeux de slides.