La recherche opérationnelle est une science qui, après avoir pris son essor au cours de la Seconde Guerre mondiale, joue une rôle important dans nos sociétés.
Elle sert notamment à l’élaboration d’horaires, l’établissement d’itinéraires optimaux pour des camions, planifier la production, définir le trajet du ramassage des poubelles, etc.
Cette science fait appel aux mathématiques et permet donc d’optimiser toute une série d’activités.

Dans ce travail d’approfondissement, je vais exposer différentes techniques pour résoudre des problèmes de recherche opérationnelle. Mais je ne vais évidemment pas aborder toutes les applications possibles ni toutes les résolutions possibles, le domaine est bien trop vaste ; ce travail n’est donc qu’un aperçu de la recherche opérationnelle.

Tout d’abord je parlerai de la programmation linéaire de manière graphique de façon à comprendre le principe ; et, ensuite, de manière algébrique en détaillant l’algorithme du simplexe.

Par la suite, j’aborderai la programmation linéaire en nombres entiers et la théorie des graphes.

Pour finir, je conclurai ce travail en détaillant la recherche d’extremums à l’aide du calcul de la dérivée première.

2. La résolution graphique de modèles linéaires continus comportant deux variables de décision

2.1. Introduction

Dans ce chapitre, je vais aborder la programmation linéaire de manière graphique en résolvant un problème. Je résoudrai le problème de manière algébrique dans le chapitre suivant en détaillant un algorithme.

2.2. Description du problème

« Les affiches de Vunéon » (problème pris du livre « La recherche opérationnelle » page 152) :

Vunéon produit, à la demande des publicitaires, de grandes affiches autocollantes destinées aux panneaux d’affichages.

Chez Vunéon, on dispose hebdomadairement de 2500 heures de main-d’œuvre pour effectuer les travaux de montage et d’imprimerie des affiches. Dans l’atelier où s’effectuent les travaux de séparation des couleurs, il n’y a que 800 heures disponibles par semaine. Le contrôle de la qualité est effectué par un technicien qui assure 40 heures de présence par semaine.

Vunéon propose à sa clientèle 2 types d’affiches : la trois-couleurs et la sept-couleurs.

Voici les données pertinentes à la production de ces affiches :

Type	Profit	Séparation des couleurs (h)	Montage et imprimerie (h)	Contrôle de la qualité (h)
Trois-couleurs	50$	1	0,5	0,04
Sept-couleurs	75$	1,5	1	0,1
Heures disponibles		800	2500	40

Vunéon cherche à déterminer le meilleur plan de production hebdomadaire, c’est-à-dire celui qui assurera le profit le plus élevé.

2.3. La modélisation

Les variables de décision, qui sont les variables avec lesquelles nous pouvons influencer directement le problème, sont :

x₁= les affiches trois-couleurs

x₂= les affiches sept-couleurs

Il faut maximiser le profit, qu’on peut mettre en équation comme suit:

Max z = 50 x₁+ 75 x₂

Cette équation s’appelle fonction économique ou fonction objectif.

Avec les inéquations qui nous donnent une limite aux variables de décision qu’on appelle contraintes :

x₁+ 1,5 x₂ ≤ 800 , le temps disponible pour la séparation des couleurs (1)

0,5 x₁+ x₂≤ 2500 , le temps disponible de main-d’œuvre pour effectuer les travaux de montage et d’imprimerie des affiches. (2)

0,04 x₁+ 0,1 x₂≤ 40 , le temps disponible pour le contrôle de la qualité des affiches (3)

x₁, x₂ ≥ 0 , contrainte de non-négativité, en effet, Vunéon ne sait pas produire – x affiches. (4)

On associe à chaque couple de valeurs des variables de décision un point (x₁; x₂) dans un plan cartésien. Un point est dit admissible s’il satisfait à toutes les contraintes du modèle. Il est dit inadmissible s’il ne satisfait pas à au moins une contrainte.

Pour résoudre ce problème graphiquement il faut construire dans un plan cartésien la région de l’ensemble des solutions admissibles ; puis les repérer sur le graphe.

2.4. La construction de la région admissible

Nous allons construire dans le plan les droites associées aux contraintes en prenant la variable x₁ sur l’axe des abscisses et la variable x₂ sur l’axe des ordonnées.

Ces droites associées ont pour équation :

Pour la contrainte (1) : x₁+ 1,5 x₂ = 800 ; représentée par f1(x) en rouge.

Pour la contrainte (2) : 0,5 x₁+ x₂= 2500 ; représentée par f2(x) en bleu.

Pour la contrainte (3) : 0,04 x₁+ 0,1 x₂= 40 ; représentée par f3(x) en noir.
Et la contrainte (4) nous fixe à rester dans les nombres positifs et donc dans le premier quadrant.

Observons par exemple que :

Tout point se trouvant sur la droite associée à la contrainte (1) utilisera toutes les heures disponibles de séparation des couleurs.

Tout point situé sous la droite associée à la contrainte (1) appartiennent à une droite parallèle à cette même droite dont l’équation est de forme : x₁+ 1,5x₂ = d et qui n’utilise pas toutes les heures disponibles. Où d est strictement inférieur à 800.

Les points qui satisfont à la contrainte (1) appartiennent à la droite associée ou à l’ensembles des points situés en dessous de la droite associée puisque si d est inférieur à 800 il satisfait toujours à la contrainte. Cet ensemble des points admissibles est appelé région admissible de la contrainte (1).

Après avoir tracé toutes les droites associées et avoir déterminé que les régions admissibles pour chacune des contraintes étaient en dessous des droites associées(car les inégalités sont de type plus petit ou égal), nous pouvons déterminer la région admissible des quatre contraintes (symbolisée par les flèches sur le graphique).

Nous pouvons observer facilement que :

- si Vunéon veut produire uniquement des affiches trois-couleurs, elle est limitée à 800 et gagnera : 800 . 50 = 40000 $

- si Vunéon veut produire uniquement des affiches septs-couleurs, elle est limitée à 400 et aura un profit de : 400. 75 = 30000 $

- qu’il est impossible que Vunéon produise des affiches en utilisant toutes ses heures disponibles de main-d’œuvre pour effectuer les travaux de montage et d’imprimerie des affiches.

Et que 4 points se démarquent : les points A, B, C et O ; intersection de deux droites qui sont appelées point extrême.

2.5. La recherche d’une solution optimale

La solution optimale est celle qui donne une valeur admissible à x₁et à x₂ et qui donne un profit maximum à z = 50 x₁+ 75 x₂.

En fixant à z une valeur p on obtient la droite : p = 50 x₁+ 75 x₂ ou x₂ = (p –50x₁)/75

Cette droite est appelée courbe de niveau.

Le coefficient de direction reste toujours le même (-50/75) et suivant que p augmente, on obtient des droites parallèles, toutes décalées plus à droite et plus hautes que la précédente.

Par exemple, si le paramètre p prend la valeur 122500, nous obtenons la droite en jaune sur le graphique.

On détermine une solution optimale en cherchant la courbe de niveau la plus élevée qui comporte au moins un point de la région admissible.

Ici, p prend la valeur 40000 et cette courbe de niveau comporte plusieurs solutions admissibles : le segment du point B au point C. (la courbe de niveau correspond à f4(x) sur le graphique et est confondue avec la droite f1(x))

La firme Vunéon doit produire 500 affiches trois-couleurs et 200 sept-couleurs pour avoir un profit maximal. De cette manière tout son temps de séparation des couleurs et de contrôle de qualité sera épuisé.

Elle aura un profit de 40000 $.

Ou bien Vunéon produit 800 affiches trois-couleurs et aucune sept-couleurs. Ainsi tout son temps de séparation des couleurs sera utilisé. Et elle aura aussi un profit de 40000 $.

Ou encore tous les points qui se trouvent sur le segment du point B au point C qui utilisent chacun différemment leur nombre d’heures disponibles.

3. La résolution algébrique de modèles linéaires continus comportant deux variables de décision

3.1. Introduction

Nous allons voir dans ce chapitre comment résoudre algébriquement un modèle linéaire comportant deux variables de décision par l’algorithme appelé « simplexe ».

Cet algorithme a été conçu par G. Dantzig en 1947. La méthode du simplexe est actuellement toujours la plus populaire pour résoudre des problèmes de programmation linéaire.

3.2. Un aperçu de l’algorithme du simplexe

Prenons l’exemple de ce pentagone, chacune de ces arrêtes est une droite associée à une contrainte, et sa surface représente sa région admissible (zone qui satisfait à toutes les contraintes).

Chacun de ces sommets est un point extrême (dans ce cas, point qui est à la limite de deux contraintes).

L’algorithme du simplexe va commencer à l’un des sommets du polygone des solutions réalisables, et progresser de sommet adjacent en sommet adjacent tant que la valeur la fonction à optimiser ne décroît pas (pour un problème de maximisation). Jusqu’à atteindre le sommet optimal. Car, Dantzig a montré que l’optimum est situé sur un des sommets du polygone (voir sous chapitre « 3.4 Points extrêmes »).

Pour expliquer la méthode du simplexe, je vais reprendre l’exemple des affiches de Vunéon vu au chapitre précédent.

3.3.1. Les variables d’écart et les variables d’excédent

L’algorithme du simplexe est une méthode qui permet d’optimiser des modèles linéaires continus dont les variables sont non négatives et dont les contraintes sont écrites sous forme d’équation.

Le modèle des contraintes est souvent écrit sous forme d’inéquation et il faut transformer ces inéquations en équations en introduisant des variables d’écart et d’excédent pour pouvoir utiliser l’algorithme du simplexe.

3.3.2. Les variables d’écart

Reprenons l’exemple des affiches de Vunéon.

La contrainte (1) :

x₁+ 1,5 x₂ ≤ 800

Pour transformer cette inéquation nous allons introduire une nouvelle variable e₁définie comme suit :

e₁ = 800 – (x₁ + 1,5 x₂) où e₁ signifie le temps non utilisé pour la séparation des couleurs.

Nous pouvons établir la non négativité de e₁ facilement sachant que :

x₁+ 1,5 x₂ ≤ 800

0 ≤ 800 –( x₁+ 1,5 x₂)

0 ≤ e₁

On peut finalement réécrire la contrainte (1) en équation :

x₁ + 1,5 x₂ + e₁ = 800

En faisant de même avec les autres contraintes, le système des affiches de Vunéon s’écrit :

Max z = 50 x₁+ 75 x₂

x₁+ 1,5 x₂ + e₁ = 800 (1)

0,5 x₁+ x₂+ e₂ = 2500 (2)

0,04 x₁+ 0,1 x₂+ e₃ = 40 (3)

x₁, x₂, e₁, e₂, e₃ ≥ 0 (4)

3.3.3. Les variables d’excédent

Les variables d’excédent suivent le même principe que les variables d’écart.

Sauf que les ajouts de variables d’écart se font dans le cas d’inéquation de type ax + by ≤ c et pour les variables d’excédent dans le cas d’inéquation de type ax + by ≥ c.

Par exemple ; l’inéquation 8x + 9 y ≥ 60 avec x, y ≥ 0

Deviendrait : 8x + 9 y – e = 60 avec x, y, e ≥ 0

Où e est la variable d’excédent.

3.4. Points extrêmes

Tout d’abord, je vais définir ce qu’est un point extrême : un point extrême, dans un système à n variable de décision, est un sommet (intersection d’au moins n arrêtes d’un polyèdre) d’un polyèdre à n dimension dont les facettes (qui sont a n-1 dimension) du polyèdre sont les contraintes du programme linéaire.
Dans notre exemple à deux dimensions, les points extrêmes sont l’intersection de au moins deux droites.

La recherche des points extrêmes est très importante pour la recherche d’une solution optimale. En effet, un des théorèmes fondamentaux de la recherche opérationnelle nous dit que : « Si un modèle linéaire continu admet au moins une solution optimale, l’une d’entre elles correspond à un point extrême ». Et ces points extrêmes se trouvent en annulant n-m variables (n le nombre d’inconnues, m le nombre de contraintes hors contraintes de non négativité).

Or si le nombre de variables de décision devient supérieur à 3, il devient impossible de trouver ces points extrêmes graphiquement car on ne peut représenter un espace à plus de 3 dimensions ; d’où la nécessité de pouvoir trouver ces points de manière algébrique.

Le modèle des affiches de Vunéon comporte 5 inconnues et 3 contraintes sans compter les contraintes de non négativité, pour trouver les points extrêmes il faut annuler deux inconnues pour que le système ait une solution ou n’en ait pas.

Ce qui définit si une solution est réalisable ou irréalisable est le respect des contraintes de non négativité.

J’ai fait un tableau récapitulatif de toutes les combinaisons de 2 variables à égaler à zéro parmi 5.

Variables hors base	Variables de base	Valeur de la fonction Objectif Z	Solution de base réalisable	Point représentatif sur le graphique
x₁ = e₃ = 0	e₁ = 200 e₂ = 2100 x₂ = 400	30000	Oui	A
x₁ = x₂ = 0	e₁ = 800 e₂ = 2500 e₃ = 40	0	Oui	O
x₁ = e₁ = 0	x₂ = 533.333 e₂ = 1966.666 e₃ = -13.333	40000	Non	Aucun
x₂ = e₁ = 0	x₁ = 800 e₂ = 2100 e₃ = 8	40000	Oui	C
x₂ = e₂ = 0	x₁ = 5000 e₁ = -4200 e₃ = -160	250000	Non	Aucun
x₂ = e₃ = 0	x₁ = 1000 e₁ = -200 e₂ = 2000	50000	Non	Aucun
x₁ = e₂ = 0	x₂ = 2500 e₁ = -2950 e₃ = -210	187500	Non	Aucun
e₁ = e₂ = 0	x₁ = -11800 x₂ = 8400 e₃ = -328	613600	Non	Aucun
e₂ = e₃ = 0	x₁ = 21000 x₂ = -8000 e₁ = -8200	450000	Non	Aucun
e₁ = e₃ = 0	x₁ = 500 x₂ = 200 e₂ = 2050	40000	Oui	B

On voit bien la lourdeur de l’opération, et s’il faut effectuer toutes les combinaisons possibles pour des cas plus concrets avec plus de variables et de contraintes, on peut obtenir un nombre gigantesque de solutions. De plus, ce calcul prend en compte des solutions non admissible. (Avec des valeurs des variables négatives). Même un ordinateur prendrait beaucoup de temps avant de résoudre de cette manière un problème de ce type.

3.5. La résolution

Pour résoudre suivant la méthode du simplexe, comme nous l’avons vu précédemment, il faut donc poser n – m variables égales à zéro (n le nombre d’inconnues, m le nombre de contraintes hors contrainte de non négativité) de manière à trouver des solutions admissibles.

Il faut d’abord trouver une solution admissible pour commencer à utiliser l’algorithme.
La solution admissible la plus facile à trouver est de poser les variables de décisions égale à zéro.

Dans l’exemple des affiches, si on pose x₁= x₂ = 0 ; on obtient le point O :

Max z = 0

e₁ = 800

e₂ = 2500

e₃ = 40

x₁, x₂, e₁, e₂, e₃ ≥ 0

x₁ et x₂ sont dites les variables hors bases - comme nous les annulons - et e₁, e₂, e₃ sont dites variables de base - car on ne les annule pas -.

Les variables hors bases sont celles qu’on annule pour trouver une solution de base.

Ce point O est un point acceptable au modèle. Mais n’est probablement pas une solution optimale puisque le profit est nul.

3.6. Tableau du simplexe

Ce tableau est utilisé pour avoir une meilleure visualisation du problème et le résoudre de manière bien plus rapide que l’énumération de toutes les solutions possibles.

C_j			50	75	0	0	0
	Variables de base	Valeurs des variables de base	x₁	x₂	e₁	e₂	e₃
0	e₁	800	1	1.5	1	0	0
0	e₂	2500	0.5	1	0	1	0
0	e₃	40	0.04	0.1	0	0	1
	Z_j		0	0	0	0	0
	C_j - Z_j		50	75	0	0	0

Sous chacune des variables x₁, x₂, e₁, e₂et e₃, on indique les coefficients (noté a_ij) de ces variables dans les différentes contraintes du problème mises sous forme d’équations numérotées de 1 à i (sans prendre les contraintes de non négativité). j est le numéro d’ordre des variables de 1 à j. Dans la colonne « valeurs des variables de base » on place la valeur que prend chacune des variables de bases lorsqu’on annule les variables hors base (ces valeurs ne peuvent être négative).

Sur la ligne et la colonne C_j on place les coefficients de variables de la fonction économique Z. Les C_j représentent la croissance de profit si on augmente la production d’une unité.

La ligne Z_j représente la perte de profit résultant de l’introduction de la variable associée.

Pour calculer le Z_j, on utilise cette formule :

Où n représente le nombre de variables de base ; i, la ligne de la matrice, a_ij le coefficient des variables de chaque contraintes et j la colonne de la matrice.

Ici Z_j est partout égal à zéro car comme le profit final est déjà à zéro, on ne sait pas perdre plus d’argent qu’actuellement.

C_j - Z_j représente le gain de profit net ou la perte nette quand on augmente d’une unité la variable associée à j.

3.7. Le choix de la variable entrante et de la variable sortante

Pour faire évoluer ce profit et trouver un autre point extrême, il va falloir choisir une nouvelle variable entrante et une sortante pour « sauter » sur le point extrême le plus proche.

Pour augmenter ce profit on va définir que x₂ ne sera pas égale à zéro puisque suivant la fonction Max z, x₂rapporte plus que x₁. Nous pouvons le voir dans le tableau du simplexe ; en effet la valeur de C_j - Z_j est la plus grande sous x₂(75).

Si x₂devient variable de base (ou variable entrante), on obtient ce système :

Max z = 75 x₂

1,5 x₂ + e₁ = 800

x₂+ e₂ = 2500

0,1 x₂+ e₃ = 40

x₁, x₂, e₁, e₂, e₃ ≥ 0

Pour prouver que la première solution n’est pas optimale, il suffit de poser x₂ égal à un.

On obtient alors un profit de 75 $ qui est supérieur à la première solution.

Mais quelle autre annuler de manière à trouver une solution ? En d’autres termes, quelle variable sortante allons nous choisir ?

Comme le profit augmente quand x₂ augmente, trouvons la limite maximum que x₂ peut prendre.

e₁ = 800 - 1,5 x₂ ≥ 0 ; donc x₂ ≤ 1600/3

e₂ = 2500 - x₂ ≥ 0 ; donc x₂ ≤ 2500

e₃ = 40- 0,1 x₂≥ 0; donc x₂ ≤ 400

Finalement x₂ est limité à 400 par e₃. Et donc e₃ sera la variable sortante.

3.8. La modification du tableau du simplexe

Nous allons devoir modifier notre tableau du simplexe :

C_j			50	75	0	0	0
	Variables de base	Valeurs des variables de base	x₁	x₂	e₁	e₂	e₃
0	e₁	800	1	1.5	1	0	0
0	e₂	2500	0.5	1	0	1	0
0	e₃	40	0.04	0.1	0	0	1
	Z_j		0	0	0	0	0
	C_j - Z_j		50	75	0	0	0

A l’intersection de la ligne de la variable sortante et de la colonne de la variable entrante, se trouve ce qu’on appelle le pivot (qu’on note P). Ici, P = 0.1

Pour modifier la ligne sur laquelle se trouve le pivot, nous utilisons la formule suivante :

Où Lest l’élément de la ligne du pivot à remplacer et P le pivot.

Exemple : Remplacer l’élément a₃₁ (0.04) :

La formule utilisée pour remplacer les éléments du reste de la matrice est la suivante :

Où E est l’élément à remplacer ; L est l’élément situé sur la même ligne que le pivot et sur la colonne de l’élément à remplacer ; C est l’élément situé sur la même colonne que le pivot et sur la ligne de l’élément à remplacer ; et P est le pivot.

Exemple : Remplacer l’élément a₂₁(0.5) :

Remarquons que le pivot sera toujours égal à 1 après transformation, en effet dans ce cas,
L = P et donc . Remarquons aussi que les autres éléments sur la colonne du pivot seront toujours égal à zéro ; en effet dans ce cas, L = P et C = E et l’équation devient :

Note : ces formules ont été trouvées par Dantzig et nous les considérons comme admises.

Finalement, le tableau devient:

C_j			50	75	0	0	0
	Variables de base	Valeurs des variables de base	x₁	x₂	e₁	e₂	e₃
0	e₁	200	0.4	0	1	0	-15
0	e₂	2100	0.1	0	0	1	-10
75	x₂	400	0.4	1	0	0	10
	Z_j		30	75	0	0	750
	C_j - Z_j		20	0	0	0	-750

Après cette opération, le système est devenu :

Max z = 50 x₁+ 75 x₂

0,4 x₁+ e₁ -15 e₃ = 200

0,1 x₁+ e₂ -10 e₃ = 2100

0,4 x₁+ x₂+ 10 e₃ = 400

x₁, x₂, e₁, e₂, e₃ ≥ 0

Nous pouvons voir que dans cette solution, la valeur prise par x₂est de 400. Donc, Cette solution assure à Vunéon un profit de 30000 $ et correspond au point A du graphique.

3.9. Critère d’optimalité

Comment sait-on que ce point n’est pas optimal ?

Si l’objectif est de maximiser la fonction économique, il faut que chaque nombre situé sur la ligne C_j - Z_j soit inférieur ou égal à zéro. Puisque à ce moment là, si on augmente une variable, nous aurions une diminution du profit et que donc il n’y a plus moyen de faire mieux que la solution trouvée.

Si c’est un problème de minimisation, il faut que la ligne C_j - Z_j soit supérieure ou égal à zéro.

Donc nous savons que la solution actuelle n’est pas optimale. Il faut donc recommencer le raisonnement.

Comme variable entrante, nous allons choisir x₁, vu que le C_j - Z_j de x₁est le plus grand.

Déterminons la variable sortante. Comme précédemment, il faut trouver les bornes de la variable entrante (x₁).

0,4 x₁+ e₁ = 200 ≥ 0 ó x₁≤ 500

0,1 x₁+ e₂ = 2100 ≥ 0 ó x₁≤ 21000

0,4 x₁+ x₂ = 400 ≥ 0 ó x₁≤ 1000

x₁est limité par e₁. Donc e₁sera la variable sortante.

L’intersection de la colonne de la variable entrante et de la ligne de la variable sortante, nous donne le pivot : P = 0,4.

A l’aide des formules énoncées précédemment, nous dressons le nouveau tableau du simplexe.

C_j			50	75	0	0	0
	Variables de base	Valeurs des variables de base	x₁	x₂	e₁	e₂	e₃
50	x₁	500	1	0	2,5	0	-37,5
0	e₂	2050	0	0	-0,25	1	-6,25
75	x₂	200	0	1	-1	0	25
	Z_j		50	75	50	0	0
	C_j - Z_j		0	0	-50	0	0

Comme toutes les valeurs des C_j - Z_j sont inférieures ou égale à zéro, la solution est une solution optimale.

Dans cette solution, x₁prend la valeur 500 et x₂ la valeur 200 de manière a donner à la fonction économique la valeur de 40 000$. Cette solution optimale correspond au point B du graphique.
Vunéon devra produire 500 affiches trois-couleurs et 200 affiches sept-couleurs pour obtenir ce profit.

3.10. Conclusion de ce chapitre

On voit bien la rapidité du procédé, en 3 calculs nous avons trouvé la solution au lieu de 10 sans utiliser l’algorithme. De plus, cet algorithme est facile à informatiser car cette construction sous forme de matrice est facile à utiliser pour un ordinateur.

Néanmoins, la résolution par cet algorithme peut donner des nombres décimaux alors que, dans des cas concrets, il faut une solution en nombre entier pour qu’elle soit réalisable. C’est pourquoi, il existe la programmation linéaire en nombre entier, qui utilise d’autres algorithmes que pour la programmation linéaire. Dans le chapitre suivant, j’aborderai ce type de recherche opérationnelle.

4. Un aperçu de la programmation linéaire en nombres entiers et de la théorie des graphes

4.1.1. Introduction

Dans ce chapitre, je vais utiliser l’exemple du problème du représentant de commerce pour aborder la théorie des graphes et la programmation linéaire en nombres entiers. Je ne vais pas expliquer en détail un algorithme pour résoudre ce problème, mais je vais exposer des heuristiques et une modélisation du problème.

4.1.2. Introduction à la théorie des graphes

Un graphe est une manière de modéliser un problème. Il est constitué d'un ensemble de sommets et d'une famille de liens (orientés ou non), appelés arêtes ou arcs, entre des couples de sommets choisis.
Un graphe est valué si, à tout arc qui le constitue, on associe une valeur numérique qu’on superpose sur le schéma. Par exemple, ces valeurs peuvent avoir la signification d’un temps à voyager d’un endroit à un autre, la distance d’un endroit à un autre, la quantité transportée, le débit, etc.

4.2.1. Le problème du représentant de commerce

4.2.2. L’énoncé

Considérons un représentant de commerce qui doit visiter n villes avant de retourner dans sa ville de départ. Il connait la distance entre chacune des villes et souhaite réduire au minimum la distance à parcourir tout en visitant chacune des villes. Dans quel ordre devra-t-il visiter les villes?

4.2.3. La modélisation

Disons ici qu’il y a n villes, numérotées de 1 à n. Pour chaque paire de villes ( i , j), nous donnons la valeur qui représente la distance de parcours de la ville i à la ville j et vice-versa. Donnons la valeur qui représente le nombre de fois que le représentant de commerce emprunte la route qui va de la ville i à la ville j ou de la ville j à la ville i.

Ce problème est dit symétrique. Dans le problème dit asymétrique, la valeur d’un arc peut être différente suivant que l’on va de la ville i à j ou de la ville j à i.

L'objectif est de minimiser ceci:

La première contrainte est que chaque ville doit être visitée une fois. Cette contrainte n’est pas suffisante, puisqu’il est possible de passer plus d’une fois par chaque ville de manière à faire un sous-itinéraire. Les contraintes deviennent donc que pour chaque sous-ensemble de villes , le représentant de commerce doit entrer et sortir de ce sous ensemble.

Notons cependant que ce problème est bien de la programmation linéaire en nombres entiers car la variable doit être en nombre entier ; puisque le représentant de commerce ne peut emprunter que des arcs entiers.
Notons aussi qu’il y a un nombre énorme de contraintes: pour notre problème de 20 villes, ce nombre est approximativement de 524 288.

4.3. Lien avec la programmation linéaire

Voici un modèle de programmation linéaire en nombre entier (que je vais noter PE pour problème en nombres entiers).

(PE) Minimiser (ou maximiser) cx
Avec les contraintes Ax = b
x ≥ 0 et entier

Il y a un programme linéaire associé appelé la relaxation linéaire (RL) qui constitue à laisser tomber les restrictions de nombre entier:

(RL) Minimiser (ou maximiser) cx
Avec les contraintes Ax = b
x ≥ 0

De cette manière nous pouvons, par exemple, trouver la solution à (RL) en utilisant la méthode du simplexe puisque le problème de programmation linéaire en nombre entier devient un problème de programmation linéaire simple.

Puisque (RL) est moins contraignant que (PE), ce qui suit est immédiat:

Si (PE) est une minimisation, la valeur optimale pour (RL) est inférieure ou égale à l'objectif optimal pour (PE).
Si (PE) est une maximisation, la valeur optimale pour (RL) est supérieure ou égale à celle de (PE).
Si (RL) est irréalisable, alors (PE) l’est aussi.
Si (RL) est optimisé par des variables entières, alors cette solution est réalisable et optimale pour (PE).
Si les coefficients de la fonction objectif sont des nombres entiers, pour une minimisation, l'objectif optimal pour (PE) est supérieur ou égal à l’arrondi vers le haut de l'objectif optimal pour (RL).
Pour une maximisation, l'objectif optimal pour (PE) est inférieur ou égal à l’arrondi vers le bas de l'objectif optimal pour (RL).

Ainsi la solution de (RL) fournit des informations: elle donne une limite sur la valeur optimale, et, si nous sommes chanceux, peut donner la solution optimale à (PE).
Par contre, pour quelques problèmes il est difficile d’arrondir et d’obtenir une solution réalisable.

4.4.1. Heuristique

Lorsqu’il est impossible de calculer directement une solution optimale et que l’utilisation d’un algorithme pour résoudre ce problème prendrait trop de temps, on doit s’arranger pour trouver une bonne solution (mais pas nécessairement optimale). De telles procédures de solution s'appellent des heuristiques. L'heuristique a souvent une justification intuitive mais elle ne garanti pas de donner une solution optimale ni même une bonne solution.

Dans ce sous-chapitre, nous illustrons l'approche heuristique sur le problème du représentant de commerce.

Il y a deux principaux types d'heuristique pour le problème du représentant de commerce: celles qui établissent un itinéraire et celles qui améliorent un itinéraire précédemment obtenu.

4.4.2. Heuristique de construction d’itinéraire

Le voisin le plus proche: Une ville de départ est choisie au hasard. On construit l’itinéraire en partant de la ville où se trouve le représentant de commerce vers la ville la plus proche qui n'a pas été encore visitée et ainsi de suite. Quand la dernière ville est atteinte, le représentant de commerce revient à la ville de départ.
L'insertion la plus proche: On choisit 2 villes très proches l’une de l’autre et on les relie entre elles. Ensuite, les villes restantes sont insérées dans l’itinéraire en enlevant un arc de l’itinéraire existant et en rajoutant une ville à l’itinéraire. Cette ville ajoutée doit être choisie en prenant celle qui augmente le moins la longueur de trajet. On procède ainsi jusqu'à avoir rajouté à l’itinéraire toutes les villes.
Le balayage: Cette heuristique localise d’abord le centre de la carte. On fait tourner une demi droite autour de ce point central. Les villes sont visitées dans l'ordre dans lequel elles sont rencontrées par la demi droite.

4.4.3. Heuristique d'amélioration d'itinéraire

Optimisation 2 par 2: Cet heuristique regarde systématiquement chaque paire d’arcs non adjacents de l’itinéraire déjà construit, et détermine si la longueur de l’itinéraire serait diminuée en enlevant ces deux arcs et en ajoutant une autre paire possible d’arcs qui bouclerait l’itinéraire. Si oui, la modification est effectuée et on continue l’opération.
Optimisation 3 par 3: Cette heuristique est semblable à l’optimisation 2 par 2, sauf que trois arcs sont enlevés et trois sommets sont recombinés pour boucler l’itinéraire.
Lin-Kernighan: Un arc est enlevé de l’itinéraire déjà construit, créant de ce fait un cul-de-sac. Alors une extrémité de ce cul-de-sac est jointe à un sommet interne et un arc est à nouveau enlevé, créant de ce fait un nouveau cul de sac. Cette opération d’ajout et de retrait est alors répétée. On regarde après chaque étape si on diminue la longueur du trajet en procédant ainsi. L'opération d’ajout et de retrait continue aussi longtemps que l’itinéraire est raccourci. On répète le procédé jusqu'à trouver un trajet plus court.

4.5. Conclusion de ce chapitre

J’ai jugé ce problème de représentant de commerce intéressant car il fait appel à des notions de la théorie des graphes et de la programmation linéaire en nombres entiers.
Le problème du représentant de commerce est par exemple utilisé pour déterminer l’ordre dans lequel une pièce va être montée à l’usine.
La théorie des graphes peut servir par exemple, pour calculer le plus court chemin d’un point à un autre, trouver l’organisation des horaires dans une école, etc. Et enfin la programmation linéaire en nombre entier est utilisée pour optimiser des modèles avec contraintes ; comme, par exemple, déterminer le nombre d’unités à produire dans une usine pour obtenir un profit maximal.

5. Calcul d’extremum à partir de la dérivée première

5.1. Introduction

Nous allons voir de quelle manière trouver un extremum d’une fonction, c'est-à-dire un maximum ou minimum. Tout d’abord, je vais faire des rappels de ce qu’est un extremum et de quelle manière le trouver. Ensuite, je résoudrai un exemple.

5.2. Théorèmes à propos de la dérivée première

Rappelons tout d’abord quelques notions.

Théorème de Rolle

Soit f une fonction, soient a et b 2 réels

Soit f continue sur [ a ; b] et dérivable sur ] a ; b [

Si f (a) = f (b)

Alors il existe au moins un point c dans ] a ; b [ tel que f’(c) = 0

Ce théorème nous dit donc que si la fonction n’est pas linéaire, il existe un point où sa dérivée première s’annule.

5.3. Déterminer la croissance/décroissance et trouver un extremum d’une fonction

Si f est croissante sur [ a ; b]

Alors f’ (x) ≥ 0 en tout x de ] a ; b [

Si f est décroissante sur [ a ; b]

Alors f’ (x) ≤ 0 en tout x de ] a ; b [

Si la fonction f passe par un extremum en c de ] a ; b [

Alors f’ (c) = 0

Ces 3 théorèmes nous disent donc que si la dérivée première est négative, la fonction décroît ; si elle est positive, elle croît ; et que si elle est égale à zéro, c’est un extremum.

5.4. Comment distinguer la nature d’un extremum

Une fois les extremums trouvés, il reste à savoir si ces points sont des maximums ou des minimums. Pour ce faire, la manière la plus simple est de faire un graphique. Ou encore de voir lequel de ces points donne à la variable à optimiser, la valeur la plus grande ou la plus petite.

Une autre manière de distinguer un maximum d’un minimum est de voir la croissance/décroissance avant et après ce point.

Si la dérivée première est positive avant et négative après le point, le point est un maximum.

Si la dérivée première est négative avant et positive après le point, le point est un minimum.

Après, si il y a plusieurs maximum/minimum, il faut voir lequel des points donne à la fonction objectif la valeur la plus grande ou la plus petite.

5.5. Exemple d’application

De tout les triangles rectangles ayant une hypoténuse de 80 cm de longueur, quel est celui dont l’aire est maximale ?

Par le théorème de Pythagore qui nous dit que, dans un triangle rectangle, le carré de l’hypothénuse est égal à la somme des carrés des deux autres côtés. Nous pouvons écrire la relation suivante : 80² = x² + z²

Et nous avons la formule du calcul d’aire qui est la suivante : aire = (base. hauteur)/2

Ici elle s’écrit : aire = (x.z)/2

La fonction de l’aire du triangle peut s’écrire comme suit :
Son graphique est le suivant :

Maintenant il faut trouver le point maximal. Pour cela, nous allons calculer la dérivée première de f(x).

Et calculer le point où cette dérivée est égale à zéro.

Le est a rejeter car une longueur ne peut être négative.

Comme nous connaissons la valeur du côté x et l’hypoténuse, le côté z est de longueur ;

Le triangle est donc isocèle. Et son aire est de 1600 cm².

Le point (56.5 ; 1600) est bien un maximum, nous pouvons le voir sur le graphique.

Pour le prouver algébriquement, il convient de faire un tableau de signe de la dérivée première.

x	-56,5			56,5
f’(x)	-	0	+	+	0	-
f(x)	décroissant	minimum	croissant	croissant	maximum	décroissant

Nous voyons bien que lorsque x prend une valeur inférieure à 56,5 ; la dérivée est positive.

Et que lorsque x prend une valeur supérieure à 56,5 ; la dérivée est négative.

Le point est donc bien un maximum.

5.6. Conclusion de ce chapitre

Cette méthode permet d’optimiser des fonctions non linéaires dont la réponse peut être en nombre décimaux. Elle peut par exemple servir à maximiser le volume d’une contenant, la surface avec une certaine quantité de matière donnée, etc.

6. Conclusion

Nous avons pu voir que la recherche opérationnelle est un domaine très vaste. Elle fait appel à des connaissances mathématiques variées et est utile dans beaucoup de cas : l’optimisation de la productivité, la gestion des stocks, la taille optimale d’un convoi militaire, etc.

De plus, certaines de ces matières font appels à plusieurs méthodes de résolution, comme nous l’avons vu avec le problème du représentant de commerce.

Bien évidemment, il existe d’autres problèmes célèbres. Citons par exemple, le problème du postier chinois, qui passe deux fois par toutes les rues, de manière à faire les deux côtés de la chaussée ; le problème des ponts de Königsberg, résolu par Euler, qui consiste à visiter tout les quartiers de la ville de Königsberg en n’empruntant qu’une fois au maximum chaque pont de la ville ; le problème des quatre couleurs, résolu en 1976 par Appel et Haken : il suffit de 4 couleurs pour colorier une carte géographique de façon à ce que deux pays adjacents soient dans des couleurs différentes ; etc.

Il y a aussi d’autres types de recherches opérationnelles, d’autres algorithmes qui ont chacun leurs avantages et inconvénients.

7. Sources

Bibliographie

Yves NOBERT, Roch OUELLET et Régis PARENT, « La recherche opérationnelle », Montréal, Gaëtan Morin, 1995.

Miche NEDZELA, « Introduction à la science de la gestion », Québec,1986.

Nathalie NAKATANI et Francis NASSIET et Jean-Claude PERRINAUD, « Dimathème »,Paris , Didier, 1993.

Jean-Pierre BRANS, « Optimisation mathématique », Bruxelles, ULB, 1996.

« Les graphes au quotidien », Hadrien Mélot.

« Cours de mathématique, classe de cinquième », Tome I, Notre Dames Des Champs.

Webographie

http://mat.gsia.cmu.edu/orclass/integer/integer.html, consulté le 6 mars 2005, « A Tutorial on Integer Programming », Michael A. Trick.