Un ensemble de cours gratuits en ligne dans différents domaines de la science pour apprendre gratuitement.

Autres sites

Comment apprendre ?

Un site communautaire de questions réponses pédagogiques. Vous y trouverez des milliers de questions et des réponses séléctionnés en tant que meilleures réponses.

Cours en vidéo

Une sélection de cours et thèmes pédagogiques en vidéo.

Sources externes

De cours gratuits en ligne.

Abonnez-vous !

Voir aussi

Sur l'annuaire

• Cours d'économie
• Cours de comptabilité
• Cours de droit
• Cours de langue
• Cours de littérature
• Cours de marketing
• Cours de mathématiques
• Cours de philosophie
• Cours de sciences
• Cours de sciences - Géologie
• Cours de sciences physiques
• Cours de sociologie
• Cours de stratégie
• Cours financier
• Cours Informatique
• Cours de programmation

PROGRAMMATION LINÉAIRE

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". 

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)

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.)