Janssen Pierre                      
Notre Dame Des Champs            Année scolaire 2004-2005
Un aperçu de la recherche opérationnelle
  Table des matières

1. Introduction.

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

2.1. Introduction.

2.2. Description du problème.

2.3. La modélisation.

2.4. La construction de la région admissible.

2.5. La recherche d’une solution optimale.

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

3.1. Introduction.

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

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

3.3.2. Les variables d’écart

3.3.3. Les variables d’excédent

3.4. Points extrêmes.

3.5. La résolution.

3.6. Tableau du simplexe.

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

3.8. La modification du tableau du simplexe.

3.9. Critère d’optimalité.

3.10. Conclusion de ce chapitre.

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

4.1.1. Introduction.

4.1.2. Introduction à la théorie des graphes.

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

4.2.2. L’énoncé.

4.2.3. La modélisation.

4.3. Lien avec la programmation linéaire.

4.4.1. Heuristique.

4.4.2. Heuristique de construction d’itinéraire.

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

4.5. Conclusion de ce chapitre.

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

5.1. Introduction.

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

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

5.4. Comment distinguer la nature d’un extremum.

5.5. Exemple d’application.

5.6. Conclusion de ce chapitre.

6. Conclusion.

7. Sources.



1. Introduction


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 :

x1 = les affiches trois-couleurs

x2 = les affiches sept-couleurs

 

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

Max z = 50 x1 + 75 x2

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 :

x1 + 1,5 x2 ≤ 800 , le temps disponible pour la séparation des couleurs (1)

 

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

 

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

 

x1, x2 ≥ 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 (x1 ; x2) 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 x1 sur l’axe des abscisses et la variable x2 sur l’axe des ordonnées.

Ces droites associées ont pour équation :

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

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

Pour la contrainte (3) : 0,04 x1 + 0,1 x2 = 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 : x1 + 1,5x2 = 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 à x1 et à x2 et qui donne un profit maximum à z = 50 x1 + 75 x2.

En fixant à z une valeur p on obtient la droite : p = 50 x1 + 75 x2  ou x2  = (p –50x1)/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) :

x1 + 1,5 x2 ≤ 800

 

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

e1 = 800 – (x1 + 1,5 x2)  où e1 signifie le temps non utilisé pour la séparation des couleurs.

 

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

x1 + 1,5 x2 ≤ 800

              0 ≤ 800 –( x1 + 1,5 x2)

   0 ≤ e1

 

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

x1 + 1,5 x2 + e1  = 800

 

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

Max z = 50 x1 + 75 x2

 

x1 + 1,5 x2 + e1  = 800                                    (1)

 

0,5 x1 + x2 + e2  = 2500                                  (2)

 

0,04 x1 + 0,1 x2 + e3  = 40                                (3)

 

x1, x2, e1, e2, e3 ≥ 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

x1 = e3 = 0

e1 = 200

e2 = 2100

x2 = 400

30000

Oui

A

x1 = x2 = 0

e1 = 800

e2 = 2500

e3 = 40

0

Oui

O

x1 = e1 = 0

x2 = 533.333

e2 = 1966.666

e3 = -13.333

40000

Non

Aucun

x2 = e1 = 0

 

x1 = 800

e2 = 2100

e3 = 8

40000

Oui

C

x2 = e2 = 0

x1 = 5000

e1 = -4200

e3 = -160

250000

Non

Aucun

x2 = e3 = 0

x1 = 1000

e1 = -200

e2 = 2000

50000

Non

Aucun

x1 = e2 = 0

x2 = 2500

e1 = -2950

e3 = -210

187500

Non

Aucun

e1 = e2 = 0

x1 = -11800

x2 = 8400

e3 = -328

613600

Non

Aucun

e2 = e3 = 0

x1 = 21000

x2 = -8000

e1 = -8200

450000

Non

Aucun

e1 = e3 = 0

x1 = 500

x2 = 200

e2 = 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 x1 = x2 = 0 ; on obtient le point O :

 

Max z = 0

 

e1  = 800                                

e2  = 2500                              

e3  = 40                                    

x1, x2, e1, e2, e3 ≥ 0                    

 

x1 et x2 sont dites les variables hors bases - comme nous les annulons - et e1, e2, e3 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.

 

Cj

 

 

50

75

0

0

0

 

Variables de base

Valeurs des variables de base

x1

x2

e1

e2

e3

0

e1

800

1

1.5

1

0

0

0

e2

2500

0.5

1

0

1

0

0

e3

40

0.04

0.1

0

0

1

 

Zj

 

0

0

0

0

0

Cj - Zj

 

50

75

0

0

0

 

Sous chacune des variables x1, x2, e1, e2 et e3, on indique les coefficients (noté aij) 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 Cj on place les coefficients de variables de la fonction économique Z. Les Cj représentent la croissance de profit si on augmente la production d’une unité.

 

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

Pour calculer le Zj, on utilise cette formule :   

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

Ici Zj 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.

 

Cj - Zj 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 x2 ne sera pas égale à zéro puisque suivant la fonction Max z, x2 rapporte plus que x1. Nous pouvons le voir dans le tableau du simplexe ; en effet la valeur de Cj - Zj est la plus grande sous x2 (75).

 

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

Max z = 75 x2

 

1,5 x2 + e1  = 800

 

x2 + e2  = 2500

 

0,1 x2 + e3  = 40

 

x1, x2, e1, e2, e3 ≥ 0

 

Pour prouver que la première solution n’est pas optimale, il suffit de poser x2 é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 x2 augmente, trouvons la limite maximum que x2 peut prendre.

e1  = 800 - 1,5 x2 ≥ 0 ; donc x2 ≤ 1600/3                              

 

e2  = 2500 - x2 ≥ 0 ; donc x2 ≤ 2500                                     

 

e3  = 40- 0,1 x2 ≥ 0 ; donc x2 ≤ 400                             

 

Finalement x2 est limité à 400 par e3. Et donc e3 sera la variable sortante.

3.8. La modification du tableau du simplexe

Nous allons devoir modifier notre tableau du simplexe :

 

Cj

 

 

50

75

0

0

0

 

Variables de base

Valeurs des variables de base

x1

x2

e1

e2

e3

0

e1

800

1

1.5

1

0

0

0

e2

2500

0.5

1

0

1

0

0

e3

40

0.04

0.1

0

0

1

 

Zj

 

0

0

0

0

0

Cj - Zj

 

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ù L est l’élément de la ligne du pivot à remplacer  et P le pivot.

Exemple : Remplacer l’élément a31 (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 a21 (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:

 

Cj

 

 

50

75

0

0

0

 

Variables de base

Valeurs des variables de base

x1

x2

e1

e2

e3

0

e1

200

0.4

0

1

0

-15

0

e2

2100

0.1

0

0

1

-10

75

x2

400

0.4

1

0

0

10

 

Zj

 

30

75

0

0

750

Cj - Zj

 

20

0

0

0

-750

 

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

Max z = 50 x1 + 75 x2

 

0,4 x1 + e1 -15 e3 = 200

 

0,1 x1 + e2 -10 e3 = 2100

 

0,4 x1 + x2 + 10 e3  = 400

 

x1, x2, e1, e2, e3 ≥ 0

                     

Nous pouvons voir que dans cette solution, la valeur prise par x2 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 Cj - Zj 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 Cj - Zj  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 x1, vu que le Cj - Zj  de x1 est le plus grand.

 

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

 

0,4 x1 + e1  = 200 ≥ 0  ó x1 ≤ 500    

 

0,1 x1 + e2 = 2100 ≥ 0 ó x1 ≤ 21000

 

0,4 x1 + x2   = 400 ≥ 0 ó x1 ≤ 1000

 

x1 est limité par  e1. Donc e1 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.

 

Cj

 

 

50

75

0

0

0

 

Variables de base

Valeurs des variables de base

x1

x2

e1

e2

e3

50

x1

500

1

0

2,5

0

-37,5

0

e2

2050

0

0

-0,25

1

-6,25

75

x2

200

0

1

-1

0

25

 

Zj

 

50

75

50

0

0

Cj - Zj

 

0

0

-50

0

0

 

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

Dans cette solution, x1 prend la valeur 500 et x2 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:

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

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

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

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

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

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

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