PROGRAMMATION LINÉAIRE
1. Complexité
1.1. NP-Complétude
2. Partie entière
3. Algorithme d'Héron
4. Algorithme d'Archimède
5. Calcul du nombre d'Euler
6. Systèmes d'équations linéaires
6.1. Une équation à une inconnue
6.2. Deux équations à deux inconnues
6.3. Trois équations à trois inconnues
6.4. N équations à n inconnues
7. Polynômes
8. Régressions et interpolations
8.1. Régression linéaire à une variable explicative
8.1.1. Droite de régression
8.1.2. Méthodes des moindres carrés
8.1.3. Analyse de la variance de la régression
8.2. Régression logistique
8.3. Interpolation polynômiale
8.3.1. Courbes de Bézier
8.3.2. Méthodes d'Euler
8.3.3. Polynôme de collocation
9.1. Méthodes des parties proportionnelles
9.2. Méthode de la bissection
9.3. Méthode de la sécante (Regula Falsi)
9.4. Méthode de Newton
10. Aires et sommes de riemann
10.1. Méthode des rectangles
10.2. Méthode des trapèzes
11.1. Algorithme du simplexe
12. Méthode de Monte-Carlo
12.1. Calcul d'une intégrale
12.2. Calcul de PI
12.3. Dichotomie
13. Analyse en composantes principales (A.C.P.)
14. Analyse factorielle des correspondances (A.F.C.)
16. Méthode des différences finies
17. Réseaux de neurones formels
17.1. Modèle de neurone
17.2. Fonctions de transfert
17.3. Architecture de réseau
18.1. Codage et population initiale
18.2. Les opérateurs
18.2.1. Opérateur de sélection
18.2.2. Opérateur de croisement
18.2.3. Opérateur de mutation
L'objectif de la programmation linéaire (P.L.) est de trouver la valeur optimale d'une fonction linéaire sous un système d'équations d'inégalités de contraintes linéaires. La fonction à optimiser est baptisée "fonction économique" (utilisée en économie dans le cadre d'optimisations) et on la résout en utilisant une méthode dite "méthode simplexe" (voir plus loin) dont la représentation graphique consiste en un "polygone des contraintes".
R1. La programmation linéaire est beaucoup utilisée (pour ne citer que les cas les plus connus) dans la logistique, la finance d'entreprise ou encore aussi en théorie de la décision lorsque nous devons résoudre un jeu à stratégie mixte (voir le chapitre de Théorie de la décision et des jeux pour un exemple pratique). C'est pour cette raison que MS Excel intègre un outil appelé le "solveur" dans lequel il existe une option appelée "modèle supposé linéaire" qui alors impose l'utilisation du modèle du simplexe que nous allons voir ci-après (dans MS Excel 2010, celle-ci est nommée "Simplex PL").
R2. Dans le cadre de résolution de problèmes où interviennent des produits de deux variables nous parlons alors logiquement "programmation quadratique". C'est typiquement le cas en économétrie dans la modélisation des portefeuilles (cf. chapitre d'Econométrie). C'est pour cette raison que MS Excel intègre un outil appelé le "solveur" dans lequel il existe une option appelée "estimation quadratique".
R3. La programmation quadratique et linéaire sont réunies dans l'étude générale de ce que nous appelons la "recherche opérationnelle".
La recherche opérationnelle à pour domaine l'étude de l'optimisation de processus quels qu'ils soient. Il existe de nombreux algorithmes s'inspirant des problèmes du type exposés lors de notre étude de la programmation linéaire. Nous nous attarderons en particulier sur l'algorithme le plus utilisé qui est "l'algorithme du simplexe".
Lorsqu'on peut modéliser un problème sous forme d'une fonction économique à maximiser dans le respect de certaines contraintes, alors on est typiquement dans le cadre de la programmation linéaire.
Soit une fonction économique Z telle que:
(57.244)
où les
sont
des variables qui influent sur la valeur de Z, et les
les
poids respectifs de ces variables modélisant l'importance relative
de chacune de ces variables sur la valeur de la fonction économique.
Les contraintes relatives aux variables s'expriment par le système linéaire suivant:
(57.245)
Sous forme générale et matricielle ce genre de problème s'écrit:
(57.246)
Voyons un exemple qui consiste à résoudre le problème simple suivant:
Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d'usinage sont pour P1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2 et pour P2 de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2.
Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160 heures et celui de l'atelier A2 de 180 heures.
La marge bénéficiaire est de 1'200.- pour une pièce P1 et 1'000.- pour une pièce P2.
Quelle production de chaque type doit-on fabriquer pour maximiser la marge hebdomadaire?
Le problème peut se formaliser de la façon suivante:
(57.247)
La fonction économique étant:
(57.248)
à maximiser.
Résolution graphique du problème (ou méthode du "polygone des contraintes"): les contraintes économiques et de signe sont représentées graphiquement par des demi-plans. Les solutions, si elles existent appartiennent donc à cet ensemble appelé "région des solutions admissibles" :
(57.249)
Pour trouver les coordonnées des sommets, on peut utiliser le graphique si les points sont faciles à déterminer.
Il s'agit donc de chercher à l'intérieur de ce domaine
(connexe), le couple
maximisant la fonction économique.
Or, l'équation Z est représentée par une droite de pente constante
(-1.2) dont tous les points fournissent
la même valeur Z pour la fonction économique.
En particulier, la droite
passe
par l'origine et donne une valeur nulle à la fonction économique.
Pour augmenter la valeur de Z et donc la fonction économique, il suffit d'éloigner
de l'origine (dans le quart de plan
)
la droite de pente -1.2.
Pour respecter les contraintes, cette droite sera déplacée, jusqu'à l'extrême limite où il n'y aura plus qu'un point d'intersection (éventuellement un segment) avec la région des solutions admissibles.
(57.250)
La solution optimale se trouve donc nécessairement sur le pourtour de la région des solutions admissibles et les parallèles formées par la translation de la fonction économique s'appellent les "droites isoquantes" ou "droites isocoûts"...
Voyons maintenant comment résoudre ce problème de manière analytique avant de passer à la partie théorique.
Nous avons donc le "système canonique" :
(57.251)
avec :
(57.252)
Nous introduisons d'abord
la "variable d'écart"
afin de transformer les 3 inégalités par des égalités.
Le système d'équations devient alors une "forme
standard"
:
(57.253)
La situation peut se résumer dans le tableau suivant (nous omettons la représentation de la variable d'écart dans le tableau-matrice qui ne sert qu'à égaliser les équations) :
|
Contraintes |
||
|
|
Total |
|
|
3 |
4 |
160 |
|
6 |
3 |
180 |
Fonction économique |
1'200 |
1'000 |
Nous déterminons maintenant le pivot (voir plus loin la méthode du pivot), pour cela nous choisissons la colonne où le coefficient économique est le plus grand. Ici c'est la colonne 1.
Ensuite, nous effectuons les procédures suivantes :
1. Le pivot est remplacé par son inverse
2. On divise les éléments de la ligne du pivot (pivot exclu) par le pivot
3. On divise les éléments de la colonne du pivot (pivot exclu) par le pivot mais on change leur signe ensuite
4. Pour les autres éléments de la première ligne : élément de la ligne 1 diminué de l'élément correspondant sur la ligne de pivot multiplié par 3/6 (rapport des valeurs dans la colonne de pivot)
Nous obtenons dès lors :
|
Contraintes |
||
|
|
Total |
|
|
|
|
|
|
|
|
|
Fonction économique |
|
|
Ce qui donne :
|
Contraintes |
||
|
|
Total |
|
|
0.5 |
2.5 |
70 |
|
0.166 |
0.5 |
30 |
Fonction économique |
-200 |
400 |
Nous n'atteignons la solution
optimale que lorsque tous les éléments de la marge
sont négatifs ou nuls. Il faut donc continuer (car il reste
400 dans la colonne )
... ici, on atteint déjà l'optimum au troisième
tableau, mais ce n'est pas une généralité (le
pivot est 2.5 cette fois). On recommence donc les opérations
:
|
Contraintes |
||
|
|
Total |
|
|
|
|
|
|
|
|
|
Fonction économique |
|
|
Ce qui donne :
|
Contraintes |
||
|
|
Total |
|
|
-0.2 |
0.4 |
28 |
|
0.266 |
-0.2 |
16 |
Fonction économique |
-120 |
-160 |
Le processus
est terminé car tous les termes de la fonction économique
sont négatifs. Le programme optimum est donc de
et
pour un résultat de :
(57.254)
ALGORITHME DU SIMPLEXE
Pour mettre en oeuvre cet algorithme, nous devons poser le problème sous une forme "standard" et introduire la notion de "programme de base" qui est l'expression algébrique correspondant à la notion de "point extrême du polyèdre des programmes admissibles" étudiée lors de la programmation linéaire (noté ci-après P.L.). En effet, nous verrons que la solution d'un problème de type P.L. si elle existe, peut toujours être obtenue en un programme de base. La méthode du simplexe va donc consister à trouver un premier programme de base puis à construire une suite de programmes de base améliorant constamment la fonction économique et donc conduisant à l'optimum.
Un problème de P.L. est donc mis sous sa "forme standard" s'il implique la recherche du minimum de la fonction objectif sous des contraintes ayant la forme d'équation linéaires et de conditions de non négativité des variables, c'est-à-dire s'il se pose sous la forme que nous avons vu lors de notre étude de la programmation linéaire:
(57.255)
C'est-à-dire aussi, en utilisant des notations matricielles:
(57.256)
où
les matrices correspondent,
respectivement, aux coefficients des niveaux d'activité dans
la fonction objectif, aux coefficients techniques des activités
et aux secondes membres des contraintes.
Nous allons voir maintenant comme un problème général de P.L. peut toujours être ramené à une forme standard. La notion de "variable d'écart" est essentielle pour effectuer cette "réduction".
Chercher le maximum d'une fonction f(x) revient à chercher le minimum de la fonction de signe opposé -f(x) . D'autre part une contrainte qui se présente comme une inéquation:
(57.257)
peut être remplacée par l'équation:
(57.258)
impliquant une variable supplémentaire, ,
appelée donc "variable d'écart", et soumise à la contrainte
de non-négativité,
.
Bien évidemment, dans un cas contraire tel où le système est du type:
(57.259)
Nous écrirons:
(57.260)
impliquant
donc également une variable supplémentaire et soumise à la contrainte
de non-négativité, .
Ce travail de mise en forme standard nous permet donc de retrouver un système d'équations linéaires à résoudre (nous avons vu précédemment sur le site comme résoudre ce genre de système avec l'algorithme du pivot).
La matrice A qui représente les composantes du système d'équations peut s'exprimer dans différentes variantes en fonction de la base vectorielle choisie (voir le chapitre d'Analyse vectorielle dans la section d'algèbre). Nous allons introduire la notion de "forme canonique utilisable" associée au choix d'une base et nous montrerons que cette reformulation du système de contraintes va nous permettre de progresser vers l'optimum.
La
matrice A peut,
après introduction des variables d'écart se décompenser en deux
sous-matrices ,
une contenant les variables initiales D et
l'autre comportant les variables d'écart B tel
que:
(57.261)
(57.262)
d'ajouter une variable d'écart tel que:
(57.263)
où
et
sur chaque ligne m, la variable d'écart ajoutée
doit
être différente de celles déjà insérées
dans le système. C'est
la raisons pour laquelle nous pouvons décomposer la matrice
en deux-sous matrices.
Les colonnes de la matrice B sont bien évidemment, par définition de la méthode, des colonnes unités, linéairement indépendantes. Ces colonnes forment une base de l'espace vectoriel des colonnes à m éléments (ou dimensions) - le nombre de lignes du système. Nous appelons B la "matrice de la base".
Les
variables associées aux composantes colonnes de la matrice B seront
dès maintenant appelées les "variables
de bases". Dans
ce cas, les variables de base sont donc essentiellement les variables
d'écart .
Les variables associées aux colonnes de la matrice D seront
appelées les "variables hors-base"; il s'agit des variables
.
En résumé, tout P.L. une fois mis sous forme standard est tel que:
-
il existe une sous-matrice carrée de la matrice A des
coefficients techniques, qui est appelée matrice de base
et qui est égale à la matrice carrée unité I de
dimension (effectivement
il y autant de variables d'écart que de lignes dans
le système
d'équations
original - au nombre de m -
et autant de colonnes puisque chaque variable d'écart à un
indice différent).
- les variables de base associées n'apparaissent pas dans l'expression de la fonction économique.
- le second membre des contraintes est constitué d'éléments non négatifs.
Nous disons que le problème est mis sous "forme canonique
utilisable associée à la base B, correspondant aux variables
de base ".
Il est maintenant commode d'introduire les notations suivantes:
(57.264)
qui sont respectivement les vecteurs des variables de base et le vecteur des variables hors-base.
Ainsi, le système d'équations décrivant les contraintes peut s'écrire indifféremment:
(57.265)
ou bien aussi:
(57.266)
Si
la matrice B est
une matrice de base, elle est non singulière et admet donc une
matrice inverse .
En multipliant cette équation, à gauche et à droite, par
nous
obtenons:
(57.267)
Le
système d'équations aura alors été mis sous une forme résolue en
.
Pour obtenir une forme canonique utilisable associée à la base B, correspondant aux variables de base, il ne reste plus qu'à éliminer les variables de base de l'expression de la fonction économique.
Ecrivons
cette fonction en séparant les vecteurs et
,
nous obtenons:
(57.268)
Nous
pouvons alors facilement exprimer en
fonction de
.
En utilisant le système d'équations mis sous forme résolue en
,
nous avons dans un premier temps:
(57.269)
que nous substituons dans la fonction économique, pour obtenir:
(57.270)
Nous
regroupons les termes en et
nous avons:
(57.271)
Nous avons alors toujours système d'équations mais ne comportant plus d'inégalités mais au contraire des égalités !!! Reste plus qu'à démontrer que la solution de ce système dit "programme base" par la méthode du pivot est optimale.
Définition: nous appelons coût réduit de l'activité hors base j,
le coefficient correspondant de
la ligne
.
Soit un problème de programmation linéaire sous forme standard:
(57.272)
La
matrice A à
m lignes
(autant qu'il y a de contraintes) et n colonnes,
avec .
Si nous sélectionnons m variables
de base et si nous annulons les
variables
hors base, la matrice A:
(57.273)
et le système se réduit à:
(57.274)
La
matrice B est
de dimension .
Si elle définit une base, elle admet une matrice inverse
.
Une solution du système est donc:
(57.275)
Si
l'expression est
non négative
,
nous avons une solution admissible qui vérifie les contraintes et
que nous appellerons un programme de base:
(57.276)
Le problème de programmation linéaire, s'écrit aussi sous la forme suivante, que nous appelons "forme canonique utilisable associée au programme de base":
(57.277)
Définition: Nous appelons "coût réduit" de
l'activité hors base j,
le coefficient correspondant de
chaque ligne j de
l'expression
A partir des développements effectués précédemment nous pouvons énoncer le résultat suivant:
Proposition
1: si dans la forme canonique utilisable associée à un programme
de base, tous les coûts réduits sont alors
le programme de base est optimal.
Proposition 2: La solution d'un problème de P.L., si elle existe, peut toujours être trouvée en un programme de base.
La démonstration précise de ce résultat est assez délicate. Nous pouvons cependant en avoir une intuition en considérant, une fois de plus, la notion de coût réduit.
En
effet, pour un programme de base donné, considérons la forme canonique
utilisable associée à la base. Sur cette forme nous pouvons vérifier
que, ou bien le programme de base est optimal (tous les coûts
réduits
sont ),
ou bien que le programme de base peut être amélioré et remplacé
par un nouveau programme de base donnant à z une
valeur plus petite (un coût réduit est négatif et la variable
hors-base associée peut être augmentée jusqu'à ce qu'une ancienne
variable de base s'annule). Comme il y a un nombre fini de programmes
de
base (au plus égal au nombre
),
la solution de P.L. se trouve nécessairement en un programme de
base.
MÉTHODE DE MONTE-CARLO
La méthode de Monte-Carlo est un moyen très efficace de contourner les problèmes mathématiques et physiques les plus complexes. Elle trouve ses applications dans des domaines variés dont voici quelques exemples:
- Aiguille de Buffon
- Problèmes de neutronique liés à la bombe atomique
- Calcul d'intégrale ou d'espérance de variables aléatoires
- Résolution d'équations elliptiques ou paraboliques
- Résolution de systèmes linéaires
- Résolution de problèmes d'optimisation (recherche opérationnelle, gestion de projets)
- Finance
Il existe 2 types de problèmes qui peuvent être traités par la méthode de Monte-Carlo: les problèmes probabilistes, qui ont un comportement aléatoire, et les problèmes déterministes, qui n'en ont pas.
Pour ce qui est du cas probabiliste, il consiste à observer le comportement d'une série de nombres aléatoires qui simule le fonctionnement du problème réel et à en tirer les solutions.
Pour le cas déterministe, le système étudié est complètement défini et on peut en principe prévoir son évolution, mais certains paramètres du problème peuvent être traités comme s'il s'agissait de variables aléatoires. Le problème déterministe devient alors probabiliste et ré solvable de façon numérique. On parle alors d'estimation de "Monte-Carlo" ou d'une approche de "MC élaborée".
La dénomination de méthode de "Monte-Carlo" date des alentours de 1944. Des chercheurs isolés ont cependant utilisé bien avant des méthodes statistiques du même genre: par exemple, Hall pour la détermination expérimentale de la vitesse de la lumière (1873), ou Kelvin dans une discussion de l'équation de Boltzmann (1901), mais la véritable utilisation des méthodes de Monte-Carlo commença avec les recherches sur la bombe atomique.
Au cours de l'immédiat après-guerre, Von Neumann, Fermi et Ulam avertirent le public scientifique des possibilités d'application de la méthode de Monte-Carlo (par exemple, pour l'approximation des valeurs propres de l'équation de Schrödinger). L'étude systématique en fut faite par Harris et Hermann Khan en 1948. Après une éclipse due à une utilisation trop intensive pendant les années 1950, la méthode de Monte-Carlo est revenue en faveur pour de nombreux problèmes: en sciences physiques, en sciences économiques, pour des prévisions électorales, etc., bref, partout où il est fructueux d'employer des procédés de simulation.
Le mieux pour comprendre la méthode de Monte-Carlo c'est d'abord d'avoir un très bon générateur de nombres aléatoire (ce qui est très difficile). Prenons comme exemple le générateur de Maple:
rand();
restart;rand();
Nous voyons donc que la fonction par défaut de générateur de nombres aléatoires de Maple est à utiliser avec la plus grande prudence puisqu'une réinitialisation du système suffit à retrouver des valeurs aléatoires... égales. Cependant il existe des libraires spécialisées dans Maple tel que:
restart;readlib(randomize):randomize():rand();
> restart;readlib(randomize):randomize():rand();
Epreuve à priori réussie (au fait, il nous faudrait faire un beaucoup plus grand nombre d'essais afin de bien vérifier que le générateur ne suive pas une loi de distribution connue... ce qui n'est malheureusement jamais le cas).
Une fois le générateur créé et testé, nous pouvons voir quelques résultats de la méthode de Monte-Carlo. Ainsi, dans le calcul des intégrales, celle-ci s'avère très utile et très rapide en termes de vitesse de convergence.
CALCUL D'UNE INTÉGRALE
Soit à calculer l'intégrale d'une fonction f définie et positive sur l'intervalle [a,b]:
(57.278)
Soit :
(57.279)
Nous considérons le rectangle englobant de la fonction
sur [a,b] défini
par les points .
Nous tirons un grand nombre N de
points au hasard dans ce rectangle. Pour chaque point, nous
testons
s'il est au-dessous de la courbe. Soit F la
proportion de points situés au-dessus, nous avons:
(57.280)
L'algorithme Maple est donné par:
intmonte:=proc(f,a,b,N)
local i,al,bl,m,F,aleaabs,aleaord,estaudessous;
m:=round(max(a,b)*10^4);
al:=round(a*10^4);
bl:=round(b*10^4);
aleaabs:=rand(al..bl);
aleaord:=rand(0..m);
F:=0;
for i from 1 to N do
estaudessous:=(f(aleaabs()/10^4)-aleaord()/10^4)>=0;
if
estaudessous then
F:=F+1;
fi
od:
RETURN((b-a)*max(a,b)*F/N)
end:
CALCUL DE PI
Pour
le calcul de le
principe est le même et constitue donc à utiliser la proportion
du nombre de points dans un quartier de cercle (cela permet de simplifier
l'algorithme en se restreignant aux coordonnées strictement positives)
inscrit dans un carré relativement au nombre de points total (pour
tester si un point est à l'extérieur du cercle, nous utilisons bien
évidemment le théorème de Pythagore) tel que:
(57.281)
L'algorithme Maple est donné par:
estalinterieur:=proc(x,y)
x^2+y^2<1 end:
calculepi:=proc(N)
local
i,F,abs,ord,alea,erreur,result;
alea:=rand(-10^4..10^4);
F:=0;
for i from 1 to N do
abs:=alea()/10^4;ord:=alea()/10^4;
if
estalinterieur(abs,ord) then
F:=F+1;
fi
od;
RETURN(4*F/N)
end:
DICHOTOMIE
La dichotomie consiste pour un objet de taille N à exécuter un algorithme de façon à réduire la recherche à un objet de taille N/2. On répète l'algorithme de réduction sur ce dernier objet. Ce type d'algorithme est souvent implémenté de manière récursive. Lorsque cette technique est utilisable, elle conduit à un algorithme très efficace et très lisible.
Un exemple simple est la recherche de la racine d'une fonction continue (nous avons déjà étudié différentes méthodes plus haut pour résoudre ce genre de problèmes). C'est-à-dire le point pour laquelle la fonction f s'annule.
Supposons qu'une fonction soit croissante et continue sur un intervalle [a,b] et tel la racine cherchée soit entre a et b. Nous avons donc par le fait que la fonction soit croissante dans l'intervalle:
(57.282)
et le fait que la racine se trouve dans l'intervalle:
(57.283)
Nous calculons:
(57.284)
Si alors
la racine est dans l'intervalle
sinon
elle est dans l'intervalle
.
Nous avons donc ramené le problème à une taille inférieure.
Nous arrêterons
l'algorithme quand la précision sera suffisante.
L'algorithme Maple est donné par:
zero:=proc(f,a,b,pre)
local
M;
M:=f((a+b)/2);
if abs(M)<pre then
RETURN((a+b)/2)
elif M>0 then
zero(f,a,(a+b)/2,pre)
else zero(f,(a+b)/2,b,pre)
fi
end:
et ce ne sont que quelques exemples auxquels la méthode est applicable!!
page suivante : 13. Analyse en composantes principales (A.C.P.)