Présentation succincte et Principe de fonctionnement d’OptSolver

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

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. Hypothèse ................................................................................................................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

Opérationnelle. ..............................................................................................................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 Opérationnelle .......................................................................................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 d’optimisation des programmes linéaires .........................................20

II.2.1 Définition d’un programme linéaire ....................................................................20

II.2.2 Notation d’un programme linéaire ......................................................................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 d’un 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 d’un programme linéaire ..................................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 linéaire (Programme Primal et Dual) ..........................36 d.2. Conditions d’application de l’algorithme 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 D’OptSolver ............................................................................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 linéaires....................................................................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

L’homme é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 à d’autres domaines connexes, afin d’augmenter le gain de travail et avoir des résultats fiables dans un temps très réduit.

Faire de la Recherche Opérationnelle 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 l’expérience (certains parlent d’art). Pour la seconde, on dispose d’algorithmes rigoureux. La discipline s’est développée avec l’informatique : modéliser mathématiquement des problèmes complexes ne servirait à rien si on ne disposait pas d’ordinateurs 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 Opérationnelle, un défi de taille reste le temps de calcul nécessaire à la résolution du problème considéré.

Ce dé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 lorsqu’un nombre trop élevé d’arêtes et de sommets doit être pris en compte.

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

Les dé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 Opérationnelle en un temps raisonnable ;

• Reprendre pour l’utilisateur les traces de la résolution des problèmes traités

(démarche de la résolution).

2. Hypothèse

Les problèmes traités en théorie des graphes et en Recherche Opérationnelle 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, c’est-à- dire sans laquelle la résolution du problème est impossible.

Ainsi, pour relever les défis lancés, d’une part, par les exigences en termes de temps de calcul et, d’autre part, par le besoin de comprendre la dé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 Opérationnelle serait idéale 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 d’en monter la démarche.

3. Objectifs du travail

Ce travail a pour but de collectionner les algorithmes étudiés dans le cadre du cours de Recherche Opérationnelle 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 d’applications d’optimisation et solveur en Recherche Opérationnelle est un sujet à la mode ! En feuilletant les catalogues des éditeurs informatiques, on est un peu submergé par le nombre d’ouvrages qui y sont consacrés et la liste n’a pas l’air de vouloir s’arrê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 mathématique est une traduction de la réalité pour pouvoir lui appliquer les outils, les techniques et les théories mathématiques, 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 décideurs en matière de calcul, détails de calcul, ainsi que d’une représentation réelle ou exacte des graphes. La plupart de ces problèmes étant dédiés à l’optimisation, les dé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 Opérationnelle 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 d’obtenir un outil répondant aux normes ergonomiques.

6. Délimitation du sujet

Ce travail intervient aux aspects de la Recherche Opérationnelle : on s’initie à la modélisation mathématique de problèmes qu’on 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 linéaire.

C’est pour ainsi dire que les problèmes traités sont d’optimisation 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 Opérationnelle. Ce chapitre aborde les notions générales sur la théorie des graphes et celles de la Recherche Opérationnelle ;

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

• Chapitre 3 : Présentation succincte et Principe de fonctionnement d’OptSolver. Ce chapitre se focalise sur la description et le comment utiliser l’OptSolver 1.0.

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

Recherche Opérationnelle.

I.1. Théorie de Graphe

I.1.1. Historique

Tout le monde s’accorde à considérer que la théorie des graphes est née en 1736 avec la communication d’Euler (1707 – 1783) dans laquelle il proposait une solution au célèbre problème des points de Königsberg (aujourd’hui Kaliningrad, ville Russe) qui consistait, à partir d’une 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 d’un « dessin » et montra qu’il é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 synthèse 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 d’une théorie 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 à l’apparition des calculateurs, au sein d’un ensemble plus vaste d’outils 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, s’est 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 d’applications 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 Opérationnelle.

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 considère 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. Nœ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é/valué 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 théorè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 mathématiques, même si, des grands mathématiciens mettent la main à la pâte. Par la suite, la théorie connaît un développement explosif, principalement à cause du développement de l’informatique. C’est 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 d’avoir 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 n’est pas une méthode acceptable si le temps né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 qu’on peut résoudre le problème A en résolvant le problème B.

Définitions :

• Longueur d’un chemin : La longueur d’un chemin (d’une chaîne, d’un circuit ou d’un 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 n’a 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, où C = ()1≤i, j≤n 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’ (l’ensemble 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 qu’il 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, c’est – à – 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 l’algorithme.

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 réseau. L’obtention de l’arborescence 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 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 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 d’optimisation 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 d’un 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+a12x2 +…+a1n xn < b1

a21x1+a22x2 +…+a2n xn < b2

am1x1+am2x2 +…+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

{ 2�1 − �2 + �3 ≤ 16

2�1 + �2 + 5�3 ≤ 26

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

�²1 + �2 − �3 ≤ 8

2�1 − 𝐼�(�2 ) + �3 ≤ 16

2�1 + �2 + 5�1�3 ≤ 26

�

�1 + �2 − ≥ 1

{ 3

3. Fonction économique :

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

b. Min z = �1 − 2�2 + �3 (signifie minimiser z)

II.2.2 Notation d’un 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

{ 2�1 − �2 + �3 ≤ 16

2�1 + �2 + 5�3 ≤ 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 −��1�1 − ��2�2 − ⋯ − �� ≥ −�� .

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

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 + 2�2 ≤ 40

{ �1 − �2 ≤ 9

2�1 + �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 + 2�2 + �1 = 40

�1 − �2 + �2 = 9

2�1 + �2 − �3 = 35

�1 + �2 = 29

�1 ≥ 0, �2 ≥ 0, �1 ≥ 0, �2 ≥ 0, �3 ≥ 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 d’un 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 ré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 dé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 , … , ��′)T 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 de résolution d’un 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, c’est – à – 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. Sélectionner les solutions de base réalisable.

Etape 3. Sé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.

Exemple

16!4!

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

max z = �1 + 2�2

Sous les contraintes

�1 + 3�2 ≤ 21

−�1 + 3�2 ≤ 18

{

�1 − �2 ≤ 5

�1 ≥ 0, �2 ≥ 0

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

�1 + 3�2 = 21

{ −�1 + 3�2 = 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 + 3�2 + �1 = 21

{−�1 + 3�2 + �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éorèmes

• 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 l’algorithme

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 )

⋯

cm+1

⋯

cn+n’

Base(B)

⋯

Pm+1

⋯

Pn+n’

⋯

x1,m+1

⋯

x1,k

⋯

x1,n+n’

⋯

x2,m+1

⋯

x2,k

⋯

x2,n+n’

⋮

⋯

xr,m+1

⋯

xr,k

⋯

xr,n+n’

⋮

⋯

xm,m+1

⋯

xm,k

⋯

xm,n+n’

PL à max

- z0

⋯

cm+1

- zm+1

⋯

ck -

⋯

cn - zn

PL à min

⋯

zm+1

- cm+1

⋯

zk -

⋯

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 + 2�2

Sous les contraintes

�1 + 3�2 ≤ 21

{ −�1 + 3�2 ≤ 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, �3 = 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

Breaking News