Optimisation fait partie de la recherche opérationnelle.
Programmation mathématiques = planification mathématiques
Programmation (mathématiques), synonyme d’optimisation, n’a rien à voir avec Programmation en
informatique, mais provient en fait du jargon militaire ou il signifie planification.
min 𝑓(𝑥)
∈
• L’ensemble D est appelé le domaine admissible, et la fonction f à minimiser la fonction coût, ou `à
maximiser la fonction objectif (ou fonction ´économique, etc...).
Un minimum (resp. maximum) de f est un maximum (resp. minimum) de −f et réciproquement, tandis la
valeur minimale (resp. maximale) de f est l’opposé de la valeur maximale (resp. minimale) de −f. Pour
cette raison on peut changer tout probl`eme de minimisation en un probl`eme de maximisation
´equivalent, et r´eciproquement.
Si D est discret (𝐷 ⊂ 𝑍 , fini ou dénombrable), on parle d’optimisation combinatoire. Les outils
proviennent essentiellement des mathématiques discrètes (théorie des graphes).
Si D est continu, et f est continue, on parle d’optimisation continue. Les outils proviennent
essentiellement de l’analyse (calcul différentiel, convexité) et de l’algèbre linéaire.
Problème d’optimisation continue :
Rappelons qu’une application ϕ est affine s’il existe une application constante ψ telle que φ − ψ soit
linéaire.
• Programmation linéaire : lorsque f, ϕ1, . . . , ϕp, ψ1, . . . , ψq sont des applications affines
et U = Rn
• Programmation quadratique : lorsque f est une application quadratique, ϕ1, . . . , ϕp, ψ1, . . . ,
ψq sont des applications affines et U = Rn
• Programmation convexe : problème de minimisation lorsque f et ϕ1, . . . , ϕp sont des
applications convexes, ψ1, . . . , ψq sont des applications affines, et U est convexe.
1
Programmation linéaire :
Un polytope généralise à toute dimension la notion de polygone dans R2 et de polyèdre dans R3. Ici ce
que l’on dénote par polytope, polygone, ou polyèdre est un peu plus général que la définition usuelle,
2
puisqu’il peut être non borné. Une définition rigoureuse d’un polytope convexe est : étant donné un
nombre fini de segments et de demi-droites, c’est le plus petit convexe de Rn les contenant.
Théorème I.1 En programmation linéaire, le domaine admissible, s’il est ni vide ni tout Rn , est un
polytope convexe. Si un extremum existe alors il est atteint sur l’un des sommets
La méthode du simplexe est une méthode algébrique systématique utilisée
uniquement pour résoudre un problème de programmation linéaire sous forme
normale.
En partant d’un sommet elle se déplace successivement sur des sommets voisins qui accroıt la valeur de
la fonction, jusqu’`a -si arrêt il y a- être parvenu sur un minimum local. La linéarité, et plus encore la
convexité, assure alors qu’il s’agit d’un minimum global.
Algorithme du simplexe I : préparation
a. On change chacune des p contraintes inégalitaires en une contrainte égalitaire en introduisant
une variable d’écart
(en présence de contraintes égalitaires, on les laisse inchangées).
b. On constitue la matrice suivante :
3
La première ligne est optionnelle et purement nominative ; la dernière ligne
s’appelle ligne résultat ; on travaillera sur cette dernière ainsi que sur la partie
centrale. Le trait vertical symbolise l’égalité ; il sépare la partie gauche de la
colonne droite.
4
5
6
Ecrire un problème de maximisation sous forme normale :
Dualité minimum/maximum :
7
Remarque : la Programmation linéaire en nombres entiers (PLNE), est un
domaine de recherche spécifique, utilisant ses outils propres, tout ce que l’on a
vu jusqu’`a présent ne s’applique pas !
Prendre un arrondi entier d’un optimum ne fournit pas en général l’optimum
en nombres entiers.
Pour les variable rationnels ∈ Q, ces méthodes s’appliquent dés lors que les
coefficients des fonctions sont rationnels. Et sinon, en prenant une
approximation rationnelle suffisamment proche de l’optimum réel trouve, on
peut se rapprocher autant que l’on veut d’un optimum rationnel ; d’ailleurs
pour cette raison lorsque l’optimum est non rationnel, un optimum restreint
aux rationnels n’existe pas, et on ne peut trouver qu’une approximation
rationnelle d’un optimum réel.