Bonsoir, nous sommes le 19/08/2022 et il est 20 h 24.

 

 

 

 

 

 

 

 

 

 

 

J

 
e dédie ce travail à ceux qui sans leurs aide je ne serais peut-être à Mbanza- Ngungu c'est-à-dire ma Grande Sœur Nigelle MBOMBO SHANGA et à mon

frère jumeau Gabriel MWANGU SHANGA , qu'il me soit permis d'adresser une

dédicace spéciale à mon Père Denis SHANGA KAPINGA OSHANGA, mes frères et sœurs Hardy MAKOLON’S, Dorcas BULUNGU, Alégréa SHANGA,   sans oublier ma petite sœur Fadiv SHANGA. Mes nièces et neveux préférés : Cathy KAZAMBA, Bethem BULA, Carlos KABUANGA, Jacques KATANGA et Nicole KISANGA.

 

Enfin big dédicace à toi Gloire KADIMA pour tout ce que tu as fait pour moi.

 

 

 

 

 

 

 

 

 

 

Eddy MUTOMBO SHANGA


 

 

 

REMERCIEMENTS

 

 

J

 
e remercie Dieu Tout Puissant de m'avoir permis de mener à terme ce mini projet qui est pour moi le point de départ d'une merveilleuse aventure celle de recherche

source de remise en cause permanent et de perfectionnement perpétuelle.

 

Tout d'abord qu'il me soit permis de rendre un vibrant hommage à mon encadreur le Professeur Ruffin-Benoit NGOIE MPOY pour avoir bien voulu superviser ce modeste travail et de donner son temps et de son intellect à la réussite de ce projet qui pour moi représente un modèle de réussite et une source de motivation permanente, pour sa disponibilité, et son sens aigu de l'humanisme pédagogique.

 

Je profite de cette tribune pour remercier les personnes qui de passage, ont pu m'apporter leur contribution que ce soit au niveau des idées qu'à celui des conceptions. Qu'elles trouvent ici l'expression de ma sincère reconnaissance.

 

Je tiens à remercier les nombreuses personnes qui m'ont encouragé et aidé tout au long de ce travail Keneth MUSAU, Gaston KINGOLE, Roxy NABANGU, Kevine UKOLAMA, Lady MANGUFU, Stevie EFAFE, NDOMOY Maike.

 

L'aboutissement de ce travail doit beaucoup à ma famille et mes amis qui m'ont soutenu et encouragé durant ces durs moments.

 

Mes compagnons de lutte : Pladi IKWA, Bruno KABONGO, Esther BISUMBULA, Clara SHONGO ne peuvent être laissés sous silence.

 

Enfin, je remercie les membres du jury qui ont bien voulu accepter, de lire et évaluer ce modeste travail.


 

 

 

SIGLES ET ABBREVIATION

 

 

ALGO                           : Algorithme

 

I.D.E                             : Integrated Development Environment

 

M.P.M                           : Méthode Potentiel Métra OptSolver                      : Optimization Solver P.C.C    : Plus Court Chemin P.L.C      : Plus Long Chemin

PL                                 : Programmation Linéaire

 

P.O.O                            : Programmation Orienté Objet

 

Qt                                  : Bibliothèque pour le langage de programmation C++, elle permet de créer des fenêtres et menus, mais aussi d’utiliser les fonctionnalités réseau de la machine.

 

Qt SDK                         : Framework

 

RO                                : Recherche Opérationnelle

 

SBR                               : Solution de base réalisable


 

 

 

Table des matières

Table des matières ..........................................................................................................iv

 

INTRODUCTION...........................................................................................................7

 

1. Problématique ..........................................................................................................7

 

2. Hypotse ................................................................................................................7

 

3. But du travail ...........................................................................................................8

 

4. Choix et intérêt du sujet ...........................................................................................8

 

5. Méthodes et Techniques utilisées ............................................................................8

 

6. Délimitation du sujet................................................................................................9

 

7. Subdivision du travail ..............................................................................................9

 

Chapitre premier : Les Généralités sur la Théorie de Graphe et la Recherche

Orationnelle. ..............................................................................................................10

 

I.1. Théorie de Graphe ..................................................................................................10

 

I.1.1. Historique.............................................................................................................10

 

I.1.2. Définitions ...........................................................................................................11

 

1.1.2.1.     GRAPHES ORIENTES ...............................................................................11

 

1.1.2.2.     CHEMIN ......................................................................................................11

 

1.1.2.3.     BOUCLE ......................................................................................................11

 

1.1.2.4.     CIRCUIT ......................................................................................................11

 

1.1.2.5.     CHEMIN HAMILTONIEN .........................................................................11

 

1.1.2.6.     HAMILTONIEN ..........................................................................................12

 

1.1.2.7.     ISTHME .......................................................................................................12

 

1.1.2.8.     ARC..............................................................................................................12

 

1.1.2.9.     BOUCLE ......................................................................................................12

 

1.1.2.10.  COLORATION ............................................................................................12

 

1.1.2.11.  K-COLORATION........................................................................................12

 

1.1.2.12.  CONNEXE...................................................................................................12

 

1.1.2.13.  NŒUD..........................................................................................................12

 

1.1.2.14.  NOMBRE CHROMATIQUE ......................................................................12

 

1.1.2.15.  ORDRE ........................................................................................................13

 

1.1.2.16.  PLANAIRE ..................................................................................................13

 

1.1.2.17.  PONDERE ...................................................................................................13

 

1.1.2.18.  TRIVIAL ......................................................................................................13


 

 

 

1.1.2.19.  VALUATION ..............................................................................................13

 

I.2. Recherche Orationnelle .......................................................................................13

 

Chapitre deuxième : QUELQUES ALGORITHMES IMPLEMENTES DANS OPTSOLVER 1.0..........................................................................................................14

 

II.1. Théorie des graphes ...............................................................................................14 a.   Recherche du chemin optimal dans un réseau........................................................14

Définitions :...................................................................................................................14 b.   Recherche du plus court chemin (du plus long chemin) ........................................15 b.1. Algorithme de Dijkstra ...........................................................................................15 b.2. Algorithme de Ford ................................................................................................17 b.3. Algorithme de Kalaba ............................................................................................18

II.2. Algorithmes doptimisation des programmes liaires .........................................20

 

II.2.1 Définition dun programme liaire ....................................................................20

 

II.2.2 Notation dun programme liaire ......................................................................22 a.   Notation canonique.................................................................................................22 b.   Notation matricielle ................................................................................................22 c.   Les variables décarts .............................................................................................23

II.3 Quelques autres définitions importantes ................................................................24 a.   Solutions dun programme linéaire ........................................................................24 b.  Bases.......................................................................................................................24 c.   Solution de Base(SB) .............................................................................................24 d.   Solution optimale ...................................................................................................25

II.4 Quelques méthodes de résolution dun programme liaire ..................................25 a.   La méthode de dénombrement des solutions .........................................................25 b.   La méthode du simplexe.........................................................................................27

1)   Théorèmes ..............................................................................................................27

 

2)   Principe de l’algorithme .........................................................................................27

 

3)   Texte de l’algorithme du simplexe .........................................................................30 c.   Méthode en deux phases.........................................................................................32

1. Introduction ...............................................................................................................32

 

2.   Principe de la méthode ...........................................................................................33

 

3.   Texte de l’algorithme .............................................................................................33 d.   La méthode du dual-simplexe ................................................................................36


 

 

 

d.1. Dualité en programmation liaire (Programme Primal et Dual) ..........................36 d.2. Conditions dapplication de lalgorithme du dual-simplexe ..................................37 d.3. Application et texte de l’algorithme du dual-simplexe ..........................................37

Chapitre troisième : PRESENTATION SUCCINCTE ET PRINCIPE DE

FONCTIONNEMENT DOptSolver ............................................................................39

 

1.1 Présentation..........................................................................................................39

 

1.2 Principe de fonctionnement .................................................................................39

 

1.3 Les principales interfaces.....................................................................................39

 

2.    Concepts..............................................................................................................40

 

3.    Présentations des éditeurs ...................................................................................41

 

3.1     Editeur des graphes en général ........................................................................42

 

3.2     Editeur des graphes pondérés ou réseaux ........................................................42

 

3.3     Editeur des graphes MPM ...............................................................................43

 

3.4     Editeur des graphes PERT ...............................................................................43

 

3.5     Editeur des tâches pour ordonnancement ........................................................44

 

3.6     Editeur des programmes liaires....................................................................44

 

4.    Editeur des graphes .............................................................................................45

 

4.1.    La barre d'objets graphiques ............................................................................45

 

4.2.    La zone de dessin.............................................................................................46

 

4.2.1.     Dessins de différents objets graphiques .......................................................46

 

4.2.2.     Manipulations dynamiques d'un graphe .......................................................50

 

4.2.3.     Supprimer - Renommer - Masquer/Démasquer ...........................................56

 

4.3.    La fenêtre d'objets dessinés .............................................................................56

 

4.4.    La fenêtre des propriétés..................................................................................58

 

Conclusion.....................................................................................................................60

 

Bibliographies: ..............................................................................................................61

 

Webographie : ...............................................................................................................62

 

Application ....................................................................................................................63

 

ANNEXES ....................................................................................................................64


 

 

 

INTRODUCTION

 

Lhomme étant continuellement à la quête de la perfection, a fait de l’informatique une nécessité dans tous les domaines de la vie, la science, l’économie, la technique et à dautres domaines connexes, afin daugmenter le gain de travail et avoir des résultats fiables dans un temps très réduit.

 

Faire de la Recherche Orationnelle consiste en pratique à modéliser mathématiquement un problème donné puis à résoudre le problème modélisé. La première étape demande du savoir faire et de lexpérience (certains parlent dart). Pour la seconde, on dispose dalgorithmes rigoureux. La discipline sest veloppée avec l’informatique : modéliser matmatiquement des problèmes complexes ne servirait à rien si on ne disposait pas dordinateurs pour mener les calculs.<

 

1. Problématique

 

Bien que plusieurs algorithmes soient conçus pour résoudre la pléthore de problèmes relatifs aux graphes et en Recherche Orationnelle, un défi de taille reste le temps de calcul nécessaire à la résolution du problème consiré.

 

Ce fi nous place au niveau de la remise en cause de certaines méthodes lorsque les données à traiter deviennent abondantes. Ainsi, pour un problème de graphe, par exemple, il peut devenir très fastidieux de le résoudre à la main lorsquun nombre trop élevé darêtes et de sommets doit être pris en compte.

 

De même, en Recherche Orationnelle, lorsque les variables de cision ainsi que les contraintes sont nombreuses, la résolution manuelle présente de sérieuses difficultés dans sa mise en œuvre.

 

Les fis à relever dans cette recherche sont les suivants :

 

    Concevoir un outil de résolution de quelques problèmes en Théorie des graphes et Recherche Orationnelle en un temps raisonnable ;

    Reprendre pour lutilisateur les traces de la résolution des problèmes traités

(marche de la résolution).

 

 

2. Hypothèse

 

Les problèmes traités en torie des graphes et en Recherche Orationnelle deviennent très compliqués, à l’échelle humaine, lorsque le nombre de données pertinentes est élevé. Par donnée pertinente, entendons toute information utile, cest-à- dire sans laquelle la résolution du problème est impossible.

 

Ainsi, pour relever les défis lancés, dune part, par les exigences en termes de temps de calcul et, dautre part, par le besoin de comprendre la marche de résolution des problèmes, nous présupposons ce qui suit :


 

 

 

    Une  application  informatique  mettant  en  œuvre  quelques  méthodes  de résolutions des problèmes en Théorie des graphes et Recherche Orationnelle serait iale pour répondre aux exigences temporelles dans les calculs ;

    Les  différentes  bibliothèques  et  autres  services  offerts  par  le  langage  de programmation C++ permettraient, non seulement de résoudre efficacement les problèmes considérés, mais aussi den monter la marche.

 

3. Objectifs du travail

 

Ce travail a pour but de collectionner les algorithmes étudiés dans le cadre du cours de Recherche Orationnelle et de Théorie des graphes ainsi que différents problèmes relatifs et d'appliquer les méthodes et les techniques de programmation afin de mettre en place un logiciel efficace de calcul. Un tel outil est voulu facile à utile et répondant aux exigences ergonomiques des utilisateurs finaux.

 

 

4. Choix et intérêt du sujet

 

La conception dapplications doptimisation et solveur en Recherche Orationnelle est un sujet à la mode ! En feuilletant les catalogues des éditeurs informatiques, on est un peu submer par le nombre douvrages qui y sont consacrés et la liste na pas l’air de vouloir sarrêter.

 

Cependant, quand on prend la peine de parcourir la table de matières de la grande majorité de ces livres, on est frappé de retrouver toujours les mêmes mots-clés : Ergonomie, Solver, AMPL, APL, OPL, TOMLAB, COIN-OR, COMET, PL, PCC, PLC, MPM, SBR, etc. Un modèle matmatique est une traduction de la réalité pour pouvoir lui appliquer les outils, les techniques et les théories matmatiques, puis généralement, en sens inverse, la traduction des résultats mathématiques obtenus en prédictions ou opérations dans le monde réel.

 

 

En qualité de technicien en informatique de Gestion, ce sujet ne pouvait nous intéresser qu'à juste titre. Il a développé notre esprit de recherche et nous a permis de cerner les problèmes cruciaux que rencontrent les cideurs en matière de calcul, détails de calcul, ainsi que dune représentation réelle ou exacte des graphes. La plupart de ces problèmes étant dédiés à l’optimisation, les cideurs y accordent une attention particulière.

 

5. Méthodologie de la recherche

 

Pour atteindre les objectifs assignés à notre recherche, nous avons adopter une démarche scientifique rigoureuse assorties de moyens scientifiquement justifiables.


 

 

 

Notre recherche a été axée sur la collection, l’implémentation, ainsi que l’assemblage dans une interface ergonomique de quelques algorithmes en Recherche Orationnelle et Théorie des graphes, le tout orienté vers une approche pratique.

 

Une telle démarche a été soutenue par une documentation permettant l’exploitation des documents et certains ouvrages mis à notre disposition ; mais aussi des entretiens avec des utilisateurs finaux ont permis de récolter leurs desiderata et objectifs du futur système. Ceci nous a finalement permis dobtenir un outil répondant aux normes ergonomiques.

 

6. Délimitation du sujet

 

Ce travail intervient aux aspects de la Recherche Orationnelle : on s’initie à la modélisation matmatique de problèmes quon résout par un logiciel que nous avons conçu pour implémenter les problèmes ci – après :

 

1.  Coloration des sommets et arêtes,

 

2.  Détection des composantes (fortement connexes)

 

3.  Problème du plus court chemin (PCC),

 

4.  Problème du plus long chemin (PLC),

 

5.  Ordonnancement des tâches et

 

6.  La programmation liaire.

 

Cest pour ainsi dire que les problèmes traités sont doptimisation mono-objectifs à variables continues ou discrètes.

 

7. Subdivision du travail

 

Notre travail a trois chapitres hormis l’introduction et la conclusion :

 

    Chapitre  1 :  Généralités  sur  la  Théorie  de  Graphe  et  de  Recherche Orationnelle. Ce chapitre aborde les notions générales sur la théorie des graphes et celles de la Recherche Orationnelle ;

    Chapitre 2 : Quelques algorithmes  en  Théorie des graphes et Recherche Orationnelle. Celui-ci saccroche sur le récit explicatif des algorithmes à implémenter dans ce travail et les différents problèmes qui y sont liés ;

    Chapitr 3  Présentation   succinct e Principe   de   fonctionnement dOptSolver.  Ce chapitre se focalise sur la description et le comment utiliser l’OptSolver 1.0.


 

 

 

Chapitre premier : Les Généralis sur la Théorie de Graphe et la

Recherche Opérationnelle.

 

 

I.1. Théorie de Graphe

 

I.1.1. Historique

 

Tout le monde saccorde à consirer que la théorie des graphes est née en 1736 avec la communication dEuler (1707 1783) dans laquelle il proposait une solution au célèbre problème des points de Königsberg (aujourdhui Kaliningrad, ville Russe) qui consistait, à partir dune terre quelconque à traverser chacun des sept ponts une fois et une seule et à revenir à son point de départ (sans traverser la rivière à la nage !). Euler représenta cette situation à l’aide dun « dessin » et montra quil était impossible de traverser chacun de ces sept ponts une fois exactement et de revenir au point de départ.

 

A partir de 1946, la théorie des graphes a connu un développement intense sous

l’impulsion de chercheurs motivés par la résolution de problèmes concrets. Parmi ceux

ci, citons de manière privilégiée Kuhn (1995), Ford et Fulkerson (1956) et Roy (1959). Parallèlement, un important effort de syntse a été opéré en particulier par Claude Berge. Son ouvrage Théorie des graphes et ses applications publié en 1958 (Berge,

1958) marque sans doute l’avènement de l’ère moderne de la théorie des graphes par

l’introduction dune torie de graphe unifié et abstraite rassemblant de nombreux résultats épars dans la littérature. Depuis, cette théorie a pris sa place, en subissant de très nombreux développement essentiellement dus à lapparition des calculateurs, au sein dun ensemble plus vaste doutils et de méthodes généralement regroupées sous l’appellation « recherche opérationnelle » ou « mathématiques discrètes ».

 

La théorie des graphes constitue un domaine des mathématiques qui, historiquement, sest aussi développé au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie (génome), les sciences sociales (modélisation des relations) ou en vue dapplications industrielles (problème du voyageur de commerce).

 

Elle constitue l’un des instruments les plus courants et les plus efficaces pour résoudre des problèmes discrets posés en Recherche Orationnelle.


 

 

 

I.1.2. Définitions

 

1.1.2.1.   Graphes Orientés

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G : X → P (X)

x → G(x) = {successeurs de x}

 

EXEMPLE(suite) : G1(b) = {a, c} G1(f)={Ø} G1(d)={e}

 

1.1.2.2.   Chemin

 

Est suite d'arcs telle que l'extrémité terminale d'un arc coïncide avec l'extrémité initiale de l'arc suivant.

 

EXEMPLE (suite) : ((a, b), (b, c), (c, d)) ou (a, b, c, d)

 

1.1.2.3.   Boucle               X

Est un arc du type (x, x)

 

1.1.2.4.   Circuit

 

Est un chemin dont le premier sommet coïncide avec le dernier

 

EXEMPLE (suite) : (a, b, c, a) circuit de G1

 

1.1.2.5.   Chemin hamiltonien

 

Est un chemin qui passe une fois et une seule par chaque sommet. EXEMPLE (suite) : (a, b, c, d, e, f)


 

 

 

 

1.1.2.6.   Hamiltonien

 

Un graphe est dit hamiltonien s'il a au moins un cycle passant par tous les sommets exactement une fois, et ce cycle est appelé cycle hamiltonien. Un cycle hamiltonien est aussi un cycle élémentaire de même ordre que le graphe.

 

1.1.2.7.   Isthme

 

Arête d'un graphe dont l'élimination augmente le nombre de composantes connexes du graphe.

 

1.1.2.8.   Arc

 

Arête dans un graphe orienté. Autre formulation : couple (ensemble ordonné de deux éléments) de sommets reliés par une arête dans un graphe non orienté.

 

1.1.2.9.   Boucle

 

Arête partant d'un sommet et arrivant sur lui-même.

 

1.1.2.10.  Coloration de graphe

 

Est une fonction associant à tout sommet (respectivement toute arête) une couleur, tels que deux sommets adjacents (respectivement deux arêtes consécutives) aient une couleur différente (c'est-à-dire on partitionne les sommets/arêtes en ensembles indépendants).

 

1.1.2.11.  K-coloration

 

Coloration d'un graphe en k couleurs distinctes.

 

1.1.2.12.  Graphe connexe

 

Un graphe est connexe s'il existe un chemin entre tout couple de sommets. Quand on parle de connexité pour un graphe orienté, on consire non pas ce graphe mais le graphe non-orienté correspondant. On peut déterminer ceci par exemple avec un algorithme de parcours en profondeur. Un graphe orienté est dit fortement connexe si, pour tout couple de sommets (u.v.) du graphe, il existe un chemin de u à v et de v à u.

 

1.1.2.13.  ud

 

Sommet dans un réseau. Un nœud interne est un sommet dans un arbre de degré

supérieur à 1, c'est-à-dire n'étant pas une feuille.

 

1.1.2.14.  Nombre chromatique

 

Nombre minimum de couleurs pour colorer un graphe.


 

 

 

1.1.2.15.  Ordre

 

Nombre de sommets du graphe.

 

1.1.2.16.  Graphe planaire

 

Un graphe est planaire si on peut le dessiner dans un plan sans croiser deux arêtes.

 

1.1.2.17.  Graphe pondéré

 

Un graphe pondéré est un graphe auquel on adjoint une fonction de valuation. Un graphe peut être pondéré/val sur ses sommets comme sur ses arêtes.

 

1.1.2.18.  Graphe trivial

 

Un graphe est trivial s'il a un seul (graphe singleton) ou aucun sommet (graphe nul). On peut utiliser un graphe trivial pour commencer une preuve par récurrence, mais ils sont implicitement exclus des torèmes dont ils constitueraient parfois des contre- exemples inintéressants.

 

1.1.2.19.  Valuation

 

Fonction associant un poids à chaque arête et/ou sommet du graphe. On parle alors de graphe valué. Voir la définition de graphe pondéré plus haut dans cette page.

 

I.2. Recherche Opérationnelle

 

Jusquà la deuxième guerre mondiale, les travaux sur les graphes se présentent comme des récréations matmatiques, même si, des grands mathématiciens mettent la main à la te. Par la suite, la torie connaît un développement explosif, principalement à cause du développement de linformatique. Cest dire que la théorie est indissolublement liée aux algorithmes utilisés pour résoudre les problèmes, ainsi quà leurs performances.

 

La notion de problème résoluble a beaucoup évolué au XXème siècle. En effet, il ne suffit plus de savoir que la réponse existe, ni davoir une méthode pour la calculer ; il faut pouvoir la trouver dans un temps raisonnable. Pour un problème dont le nombre de solutions est fini, l’énumération complète nest pas une méthode acceptable si le temps cessaire pour l’accomplir est exponentiel (ou pire) en la taille du problème (Cf. le problème du voyageur de commerce).


 

 

 

Chapitre

deuxième :      QUELQUES      ALGORITHMES

EN

 

THEORIE       DES      GRAPHES

ET


 

 

 

II.1. Théorie des graphes


RECHERCHE OPERATIONNELLE


 

II.1.1. Recherche du chemin optimal dans un réseau

 

Dans un réseau G = (X, U, C), la recherche du chemin optimal peut être opérée pour divers objectifs :

 

A. Pour deux sommets donnés, déterminer le plus court ou le plus long chemin. B. Pour un sommet donné, déterminer les plus courts ou les plus longs chemins

les joignant à tous les autres sommets du graphe.

 

C. Déterminer pour chaque couple des sommets, le plus long ou le plus court chemin.

 

Il est bien clair quon peut résoudre le problème A en résolvant le problème B.

 

Définitions :

    Longueur dun chemin : La longueur dun chemin (dune chaîne, dun circuit ou dun cycle) est la somme des longueurs de chaque arc (arête) qui le (la) compose.

 

    Circuit absorbant : Un circuit absorbant est un circuit dont la longueur est négative.

 

 

Exemple : Le circuit suivant de longueur -2 est un circuit absorbant


 

 

 

Il existe plusieurs algorithmes pour résoudre le problème B, chacun donna les résultats escomptés moyennant certaines conditions remplies par la structure du réseau, par exemple :

 

    Si le réseau est sans circuit absorbant, les algorithmes Bellman - Ford, Bellman

Kalaba sont satisfaisants.

 

    Si le réseau na que des longueurs positives ou nulles (Réseau de transport), l’algorithme de Dijkstra est très efficace.

 

Tous les algorithmes de résolution du problème B (plus courts ou plus longs chemins entre un sommet et les restes) se servent du principe d’optimalité de Richards Bellman qui s’énonce comme suit :

 

« Tout chemin optimal (minimal ou maximal) est composé des chemins partiels optimaux. »

 

a. Recherche du plus court chemin (du plus long chemin)

 

 

Comme dit ci-haut, il nous est question ici de présenter des algorithmes permettant de trouver les plus courts (longs) chemins entre un sommet donné et le reste des sommets du réseau.

 

Soit G = (X, U, C) un réseau, C = ()1i, jn est la matrice de pondération du

réseau avec.

 

Le problème du plus court (long) chemin (PCC(PLC)) se formule comme suit :

« Pour un réseau donné comme ci-avant, trouver un chemin μ allant d’un sommet x

à un autre sommet y tel que la longueur de μ, Longueur μ= (i,j) μ, Cij soit

minimale (maximale). »

 

b.1. Algorithme de Dijkstra

 

 

Si G est un réseau de transport c’est à dire, si tous les éléments de sont positifs, alors on peut utiliser l’algorithme de Dijkstra pour résoudre le problème des PCC entre un sommet donné et le reste des sommets du réseau.

 

1)  Enoncé de l’algorithme

 

Entrées         : G = (X, U, C) un réseau de transport, s un sommet.

 

Sorties          : une fonction poids () indiquant la plus courte distance qui sépare un point de s, une fonction pred () indiquant par quel arc on arrive à un point si on emprunte le plus court chemin à partir de s.


 

 

 

Variables intermédiaires : S et S’ deux sous-ensembles de sommets, x et y deux

nœuds, un booléen arret.

 


Initialisations

 

 

poids(x) = +;

pred(x) = x;

fin pour

 

 

poids(s) 0 ;

S←;

S’ ←X;

arret faux;


pour tout x X faire


 

 

Début

 

tant que (S X et  arret = faux) faire

arret = faux ;

choisir un sommet x S’tel que poids(x) = min{pos(y) | y S’} ;

si (poids(x) =+) alors

arret vrai;

finsi

 


si  (arret = faux) alors

S←S {x} ;


 

 

S←S’{x};


pour chaque arc u = (x, y)  tel que y S’ faire

si (poids(y) > poids(x) + d(u)) alors

poids(y) poids(x) + d(u) ;

pred(y) u ;


 

 

 

finsi fin tant que Fin


finsi finpour


 

 

2)  Explication

 

À chaque itération, l’algorithme de Dijkstra, ne considère que le sommet x

non encore exploré dont la valeur poids(x) est minimale afin de pouvoir minimiser

la distance poids(y) de chaque sommet y S’ (lensemble des sommets non explorés)

voisin de x. Pour qu’un sommet (nœud) x ait une distance poids(x) (la plus courte

distance de s à x) différente de +, il faut quil ait un de ses prédécesseurs dans S

(l’ensemble des sommets explorés). Chaque sommet x S a une valeur poids(x) dite


 

 

 

définitive, cest à dire qui ne peut plus être minimisée. Si au cours d’une itération,

l’algorithme détecte x S’ et poids(x) = min {poids(y) | y S’}  = + alors cela

signifie que tous les sommets de S’ n’ont pas de prédécesseurs dans S, donc le graphe

n’est pas connexe, l’on peut de ce fait arrêter lalgorithme.

 

Cet algorithme donne en partant du sommet s dite source, tous les plus courts chemins vers les autres sommets du graphe, ce qu’on appelle arborescence des PCC.

 

b.2. Algorithme de Ford

 

 

Cette algorithme permet non seulement de trouver l’arborescence des PCC(PLC), mais aussi de détecter la présence des circuits absorbants dans le seau. L’obtention de larborescence de PCC par application de l’algorithme de Ford nécessite que le réseau soit sans circuit de longueur négative (circuit absorbant). L’obtention de l’arborescence des PLC exige l’absence des circuits dans le réseau.

 

1)  Enoncé de l’algorithme :

 

Entrées : G = (X, U, C) un réseau, s un sommet.

 

Sorties : une fonction poids () indiquant la plus courte (longue) distance qui sépare un point de s, une fonction pred () indiquant par quel arc (arête) on arrive à un point si on emprunte le plus court (long) chemin à partir de s.

 

Variables intermédiaires : x et y deux nœuds, modif un booléen, n l’ordre du graphe, k un compteur d’itérations.

 

Initialisations

 

pour tout x X faire

poids(x) = +;

pred(x) = x;

fin pour

 

 

poids(s) 0 ; modif ← faux; n←#X;

k←0;


 

 

 

Début

 


faire


 

modif = faux ;

 

 

pour chaque sommet x ϵ X faire pour chaque arc u = (x, y) faire

si (poids(y) > poids(x) + d(u)) alors

[Pour le plus long chemin : si (poids(y) < poids(x) + d(u))

alors]


 

 

 

 

 

finsi finpour

finpour


poids(y) poids(x) + d(u) ;

pred(y) u ;

modif = vrai ;


 

si(modif = vrai)

k  k+1;

finsi

tant que(modif = vrai etk <n)

 

Fin

 

2) Explications

 

À chaque itération, l’algorithme de Ford procède à peu près comme celui de Ford, il parcourt tous les sommets et enregistre dans la variable modif la valeur vraie si au moins une variable a vue sont poids modifié. Si à la fin d’une itération, modif vaut faux, c’est – à – dire plus aucun poids ne peut plus être amélioré, alors l’algorithme prend fin. Si l’algorithme tourne jusqu’à l’itération k = n alors il existe au moins un circuit absorbant dans le réseau et donc l’algorithme ne donne pas le bon résultat.

 

b.3. Algorithme de Kalaba

 

 

Comme l’algorithme de Ford, celui de Kalaba permet aussi de déterminer les PCC et PLC et de déceler la présence des circuits absorbants dans le réseau. Les conditions de bonnes applications restant les mêmes.

 

1)  Enoncé de lalgorithme :

 

Entrées : G = (X, U, C) un réseau, s un sommet.


 

 

 

Sorties : une fonction poids() indiquant la plus courte (longue) distance qui sépare un point de s, une fonction pred() indiquant par quel arc on arrive à un point si on emprunte le plus court (long) chemin à partir de s.

 

Variables intermédiaires : S un sous ensemble de X contenant les sommets explorés,

x et y deux nœuds, stab un booléen, n l’ordre du graphe, k un compteur d’itérations.

 

Initialisations

 

poids(s) 0 ;

S {s} ;

pour tout arc u = ( x , y)  faire si x = s alors

poids(x) d(u) ;

pred(x) s ;

S S {x} ;

sinon

poids(x) +∞ ;

finsi fin pour

stab faux ;

k 0 ;

n #X ;

 

Début

 

Tant que stab = faux et k < n faire

stab ←  vrai ;

pour chaque sommet x ϵ X {s} faire

pour chaque arc u = (y, x) | y S faire

si (poids(x) > poids(y) + d(u)) alors

[Pour le plus long chemin : si (poids(x) < poids (y) +

d(u)) alors]

poids(x) poids(y) + d(u) ;

pred(x) y ;

stab = faux ;


 

 

 

 

 

 

 

 

 

 

 

Fin


finsi finpour

fin pour

si(modif = faux)

k k+1;

finsi

tant que(modif = vrai  et k < n)


 

 

 

2) Explications

 

Cet algorithme est très semblable à celui de Ford, la différence est qu’à chaque itération, il n’explore pas le sommet source s. Pour chaque sommet x sélectionné aucours d’une itération pour amélioration de poids(x), l’on ne considère que les y prédécesseurs de x appartenant à l’ensemble S des sommets traités au moins une fois.

 

II.2. Algorithmes doptimisation des programmes linéaires

 

 

La programmation linéaire est un outil très puissant de la Recherche Opérationnelle, qui permet de résoudre un grand nombre de problèmes modélisables mathématiquement. En effet, une fois un problème posé trouve sa modélisation mathématique sous la forme d’équations linéaires, la programmation linéaire offre plusieurs méthodes permettant de le résoudre de manière exacte.

 

II.2.1 Définition dun programme linéaire

 

 

Un programme linéaire (PL) est un tout formé par :

 

   Un système d’équations ou d’inéquations linéaires (c’est à dire que les équations sont des polynômes dont chaque terme contient une seule variable) appelées contraintes :

 

a11x1+a12x++a1n xn < b1

Zone de Texte: .	.	.a21x1+a22x2  ++a2n xn < b2

 

 

 

 

am1x1+am2x++amn xn < bm

x1>0, x2   >0,…, xn  > 0

 

 

   Une  fonction linéaire à optimiser (minimiser  ou maximiser) à partir des


=1

 
contraintes :  =


 


 

Dans les expressions ci-haut :

 

 Les paramètres a11, a12, ,a21, a22 ,…, amn ; b1, b2,,bm; c1, c1,, sont des

nombres réels donnés ;

 Les variables x1, x2, ,xn sont appelées variables structurelles.

 Le système des contraintes est formé de m+n contraintes :


 

 

 

   Les  m  premières  contraintes  sont  appelées  les  contraintes  liées

puisqu’elles lient les variables structurelles.

 

   Les n dernières contraintes sont appelées les contraintes libres de non négativité. Elles expriment le fait que les valeurs des variables structurelles sont considérées dans IR+.


=1

 
 La  fonction  linéaire  =


 


 

est  appelée fonction économique  ou


fonction objective.

 

S’il faut :

 

 Minimiser z (min z), il s’agit d’un programme linéaire à minimum (PL à min);

 Maximiser z (max z), alors il s’agit d’un programme linéaire à maximum (PL

à max).

 

Un PL à min peut être transformé en un PL à max (en effet min(z) = -max(-z)), moyennant la modification des formes des contraintes et réciproquement.

 

Exemples

 

1. Voici un système des contraintes linéaires :

 

1 + 2 3   8

{ 21 2 + 3   16

21 + 2 + 53   26

2. Voici un système des contraintes non linéaires.

 

²1 + 2 3   8

21 𝐼(2 ) + 3   16

21 + 2 + 513   26

1

 
1 + 2 −      ≥ 1

{                             3

 


3. Fonction économique :


a.  Max z = 1 + 2 +  (signifie maximiser z)

b.  Min z = 1 22 + 3 (signifie minimiser z)


 

 

 

II.2.2 Notation dun programme linéaire

 

a. Notation canonique

 

 


La notation canonique d’un PL est la suivante :

=1

 
Optimiser      =


 


 

Sous les contraintes

 


 

{  =1


     ,  = 1,2, ,


   0  = 1,2, ,

Exemple : Voici un programme linéaire sous forme canonique

 

max z = 1 + 2 + 3

 


Sous les contraintes


1 + 2 3   8

{    21 2 + 3   16

21 + 2 + 53   26

1   0,  2   0,  3   0


 

Le plus souvent un programme linéaire est exprimé sous cette forme.

 

Notons toutefois qu’une contrainte 1 1 2 2 +        équivaut à la contrainte 11 22 −       .

Ainsi nous pouvons exprimer tout PL sous la forme canonique ci-avant.

 

 

 

b. Notation matricielle

 

 

Un programme linéaire peut se mettre sous la forme matricielle suivante : Optimiser {CX | AX B, X ≥ O}

Avec :

 


   C = (


1

2

.  )

𝑛


 

 

 


.

.

.

.

.

.

 

 
 A = ( )1 < i < m,   1< j< n = (


11 . . .


1

)


1 ��

 

La matrice A est appelée matrice technique.

 


 B = (


1

2

.  )

𝑛


 

 

0

0.

   0 = ( . )

0

 

 

c. Les variables d’écarts

 

On peut remplacer les inéquations (les contraintes liées) par des équations

à l’aide d’un ensemble des variables qu’on appellera variables d’écarts :

En effet, soit par exemple le programme linéaire suivant :

max z = 1 + 2 + 3

 


Sous les contraintes


1 + 22   40

{    1   9

21 + 2   35

1   0,  2   0


 

Equivaut au programme linéaire

 

max z = 1 + 2 + 0 1  + 0  2  + 0 3

 

 

 


Sous les contraintes


1 + 22 +  = 40

1 2 + 2  = 9

21 + 2  = 35

1  + 2  = 29

1   0,   0,   0, 2   0,   0

{


 

 

 

Notons que :

 

 Ainsi les variables d’écarts sont sans effet sur la fonction économique

car elles y interviennent avec des coefficients nuls.

 Les variables structurelles et les variables d’écarts sont appelées les

variables des décisions.

 

II.3 Quelques autres définitions importantes

 

 


a.   Solutions dun programme linéaire

Solution d’un PL        :  c’est  tout  vecteur  X  =  (


1

2

.

𝑛


)des  valeurs  de


 

variables structurelles qui satisfont les contraintes liées et les contraintes libres de non négativité et telles que les valeurs des variables d’écarts sont positives ou nulles.

 

 

Solution alisable     : c’est toute solution X telle que AX ≤ B et X ≥ O

 

 

Solution optimale       : c’est la solution réalisable qui optimise (minimise

ou maximise) la fonction économique.

 

b. Bases

 

 

Supposons que toutes les m contraintes liées sont mises sous forme d’égalités à l’aide de n’ variables d’écarts ; on a alors n + n variables de décisions et m< n+n’. On appelle base, le vecteur des variables de cisions (parmi les n+n) tel que la sous

matrice carrée d’ordre m de la matrice technique A, associée à ces variables soit

régulière, c’est à dire de déterminant non nul.

 

 

 

c. Solution de Base(SB)

C’est un vecteur SB =( 1, 2, ,  , 1, 2 , , ) des valeurs de  variables des décisions obtenues en posant nulles les variables hors base et en résolvant le système

de Cramer obtenue.

 

Si une solution de base est réalisable (c’est – à dire vérifie les contraintes libres de non négativité) alors elle est dite solution de base réalisable (SBR).


 

 

 

d.  Solution optimale

 

 

C’est la SBR qui optimise (maximise ou minimise) la fonction économique.

 

II.4 Quelques méthodes desolution dun programme linéaire

 

 

Il existe plusieurs méthodes permettant de résoudre un programme linéaire : La méthode graphique, La méthode de dénombrement, la méthode du simplexe, la méthode en deux phase, la méthode du dual-simplex, etc.

 

a. La méthode de dénombrement des solutions

 

 

Cette méthode est applicable si n + n m, cest à dire que s’il y a plus

ou autant de contraintes que des variables de décisions.

 

C’est la plus simple de toutes les 4 méthodes qui nous intéressent, mais elle devient vite ennuyante quand il faut résoudre des systèmes de Cramer qu’elle propose pour de gros programmes linéaires.

 

Principe de la méthode :

 

Etape 1. Rechercher les solutions de base du PL :

Ceci est fait en annulant chaque fois n + n’ m variables de décisions et en

résolvant le système de Cramer obtenu.

 
On a de ce fait (+) systèmes de Cramer à résoudre.

Etape 2. lectionner les solutions de base réalisable.

 

Etape 3. lectionner la solution optimale parmi les SBR obtenues à l’étape 2.

 

La méthode de dénombrement devient vite fastidieuse pour des PL ayant beaucoup des  variables  de  décisions.  Par  exemple,  si  n  +  n’  =  20  et  m  =  16  alors


on a (20) = 20!


= 4845 systèmes de Cramer à résoudre à l’étape 1.


16

Exemple


16!4!


 

Soit à résoudre le programme linéaire suivant par la méthode de dénombrement :

max z = 1 + 22


 

 

 


Sous les contraintes


1 + 32   21

1 + 32   18


{

1 2   5

1   0,  2   0

Mettons les contraintes sous formes d’égalités :

1 + 32  = 21

{                     1 + 32  = 18

1 2  = 5

1   0,  2   0, 1   0, 2   0, 3   0

On a n + n’ = 5 et m=3, donc on annulera chaque fois  n + n’ m = 2 variables de

décisions dans le système d’équations :

1 + 32 + 1  = 21

{1 + 32 + 2  = 18

1 2 + 3  = 5

Qu’on résoudra ensuite. Par exemple si 1= 2= 0, alors on trouve après résolution :

1 =21,        2  =18,       3 = 5

 


À l’étape 1, on a au total(5) = 5!


=10 systèmes de Cramer à résoudre :


3          3!2!

 

ETAPE 1 : Rechercher les solutions de base du PL

 

 

Points

 

 

x1

 

 

x2

 

 

t1

 

 

t2

 

 

t3

 

 

S1

 

0

0

21

18

5

 

S2

 

0

7

0

-3

12

 

S3

 

0

6

3

0

11

 

S4

 

0

-5

36

33

0

 

S5

 

21

0

0

39

-16

 

S6

 

-18

0

39

0

23

 

S7

 

5

0

16

23

0

 

S8

 

3/2

13/2

0

0

10

 

S9

 

9

4

0

15

0

 

S10

 

33/2

23/2

-30

0

0


 

 

 

ETAPE 2 et ETAPE 3 : Sélectionnons les solutions de base réalisable et la solution optimale.

 

 

Points

 

 

x1

 

 

x2

 

 

t1

 

 

t2

 

 

t3

 

 

z

 

 

S1

 

0

0

21

18

5

 

0

 

 

S3

 

0

6

3

0

11

 

12

 

 

S7

 

5

0

16

23

0

 

5

 

 

S8

 

3/ 2

13/2

0

0

10

 

29/2

 

 

S9

 

9

4

0

1 5

0

 

17

 

 

La solution optimale est le point S9 en jaune dans le tableau ci-avant avec

 

 

1= 9, 2= 4, 1 = 0, 2 = 15 et 3  = 0 , comme valeurs des variables de décisions qui maximisent la fonction économique avec la valeur z = 9+2*4 = 17.

 

b. La méthode du simplexe

 

1) Théomes

 

 

   Tout système d’inéquations peut admettre pour solution :

 

Un ensemble vide (les inéquations sont dites contradictoires) ;

Un polyèdre convexe (un corps solide à plusieurs faces contenant tout segment de droite joignant deux de ses points) fermé (borné) ;

Un polyèdre convexe non fermé, il existe alors une infinité des solutions.

 

   Si l’ensemble des solutions réalisables d’un programme linéaire est un polyèdre convexe, alors la fonction économique ne peut atteindre son optimum (maximum ou minimum) qu’en un des sommets dudit polyèdre.

 

2) Principe de lalgorithme

 

 

De manière générale, l’algorithme du simplexe consiste à se déplacer le long du polyèdre formé par les SBR du PL, de sommet en sommet adjacent jusqu’à trouver celui qui optimise la fonction économique selon le deuxième théorème ci – avant.

 

Les étapes de l’algorithme sont :

 

   Déterminer  une  première  solution  de  base  réalisable  du  programme linéaire à partir de laquelle on va démarrer l’algorithme du simplexe ;

 

 

   Aller  itérativement  de  SBR  en  SBR  afin  d’optimiser  (maximiser  ou

minimiser) progressivement la valeur de la fonction économique ;


 

 

 

 

 

   Arrêter l’algorithme aussitôt que l’on ne peut plus optimiser la valeur de la fonction économique. La toute dernière SBR qui a amélioré la fonction objective est la solution optimale.

 

L’application de la méthode du simplexe se fait facilement en classant les données dans un tableau de la manière suivante :

 

Max(Min )

c1

c2

cr

cm

cm+1

ck

cn+n’

Base(B)

CB

Po

P1

P2

Pr

Pm

Pm+1

Pk

Pn+n’

P1

c1

x1

1

0

0

0

x1,m+1

x1,k

x1,n+n’

P2

c2

x2

0

1

0

0

x2,m+1

x2,k

x2,n+n’

 

 

 

 

 

 

 

 

 

Pr

cr

xr

0

0

1

0

xr,m+1

xr,k

xr,n+n’

 

 

 

 

 

 

 

 

 

Pm

cm

xm

0

0

0

1

xm,m+1

xm,k

xm,n+n’

PL à max

- z0

0

0

0

0

cm+1

zm+1

ck      -

zk

cn -  zn

PL à min

z0

0

0

0

0

zm+1

cm+1

zk      -

ck

zk - ck

 

Les notations employées sont :

   Pj {         {1,2, , }: �� ��

{ + 1, , + �′}: �� �� ��

   , = 1,2, , : ���������� ��� �� ����� é�� ;

   , = 1,2, , ����� ��  ��� �� ���éé;

   ( = 1,2, , ; = + 1, , +  ): �������� �� è��

��� �� è���   .

   , = 1,2, , +      = ,    {1,2, , + �′} �   é��� ���

�� �� �� ��������� ������ ��� �� �����

é.

   0,   {1,2, , +  }: 0  = , �   é��� ��� �� �� ��

�� �������� �������� ��� �� ����� é.

   La première colonne contient la liste des vecteurs de base l’étape considérée

; nous parlerons également de variables de base) ;

   La  deuxième  colonne  contient  les  coefficients  économiques  associés  aux variables de base ;

   La troisième colonne contient les valeurs prises par lesdites variables de base,

c’est à dire la solution de base correspondante ;


 

 

 

Ainsi si l’on considère par exemple le programme linéaire suivant :

max z = 1 + 22

 


Sous les contraintes


1 + 32   21

{ 1 + 32   18

1 2   5

1   0,  2   0,


 

Mettons les contraintes sous formes d’égalités :

 

 

 

 

On n + n’ = 5 et m = 3 et donc n + n m = 2 variables à annuler :

1  = 21

Prenons 1= 2  = 0, on a {2  = 18, d’où l’on tire la solution (0, 0, 21, 18, 5) qui est

3  = 5

une  solution  de  base  réalisable  (nécessaire  pour  le  démarrage  l’algorithme  du

simplexe).

 

Voici comment se présente le premier tableau du simplexe :

1 = 1, 2 = 2, = 0, 4 = 0, 5 = 0

Les variables 1 , 2 , et 3  correspondants respectivement aux vecteurs P3, P4 et P5

seront dans la base c’est – à dire  que la colonne B comprendra P3, P4 et P5.

Dans la colonne CB on mettra les coefficients correspondants aux variables 1 , 2 , et

3  dans la fonction économique, ici 3, 4, 5.

Dans la colonne P0, on mettra les valeurs 21, 18