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 et 5 correspondants respectivement

aux variables �1 , �2 , et �3 dans la solution de base réalisable trouvée plus avant.

L’on peut réécrire le système des contraintes liées précédent de la façon suivante :

�1 + 3�2 + �1 + 0 ∗ �2 + 0 ∗ �3 = 21

{−�1 + 3�2 + 0 ∗ �1 + �2 + 0 ∗ �3 = 18

�1 − �2 + 0 ∗ �1 + 0 ∗ �2 + �3 = 5

Qui nous permet de compléter les autres cellules de la 3è à 5è ligne.

Quant à la dernière ligne nous avons

�0 = 0 ∗ 21 + 0 ∗ 18 + 0 ∗ 5 = 0

�1 = 0 ∗ 1 + 0 ∗ (−1) + 0 ∗ 1 = 0, �1 − �1 = 1

�2 = 0 ∗ 3 + 0 ∗ 3 + 0 ∗ (−1) = 0, �2 − �2 = 2

�3 = 0 ∗ 1 + 0 ∗ 0 + 0 ∗ 0 = 0, �3 − �3 = 0

�4 = 0 ∗ 0 + 0 ∗ 0 + 0 ∗ 1 = 0, �1 − �1 = 0

�5 = 0 ∗ 0 + 0 ∗ 0 + 0 ∗ 1 = 0, �1 − �1 = 0

En notant P3 = Pt1, P4 = Pt2 et P5 = Pt3, on a enfin le premier tableau simplexe que

voici :

Max			1	2	0	0	0
B	CB	P0	P1	P2	Pt1	Pt2	Pt3
Pt1	0	21	1	3	1	0	0
Pt2	0	18	-1	3	0	1	0
Pt3	0	5	1	-1	0	0	1
Cj - Zj		0	1	2	0	0	0

3) Texte de l’algorithme du simplexe

Pour un Pl à max, on a :

1) Mise des contraintes sous forme d’égalités ;

2) Recherche d’une première solution de base réalisable ;

3) Construction du 1er tableau simplexe ;

4) Si tous les �� − �� ≤ 0, alors la solution optimale est atteinte, aller à 9);

5) Si pout tout �� − �� > 0 les �� ≤ 0, alors le problème admet une infinité des

solutions, aller à 9) ;

6) Changement de base :

• Le vecteur entrant dans la base :

P k entre si �� − �� = ma�� {�� − �� | �� − �� > 0} ;

• Le vecteur sortant de la base :

P r sort si

��𝑟

=minj{

𝑥�

| ��

>0} ;

��𝑟�

𝑥��

��

�𝑟� est appelé pivot

7) Construction du nouveau tableau simplexe :

𝑥

• Diviser la ligne �𝑟 du pivot par le pivot : �𝑟 ←

𝑟�

* �𝑟 ;

• Pour toute autre ligne � (i ≠ r) : � ← − ��

� � ��𝑟�

* �𝑟 ;

• −�0 = −�0 −

��−��

��𝑟�

* �𝑟

��−��

• (�� − �� ) ← (�� − �� ) −

8) Aller à 4) ;

9) Fin.

��𝑟�

* �𝑟�

Pour un problème à min, même démarche en changeant simplement à l’étape 7) :

• −�0 = −�0 −

��− ��

��𝑟�

* �𝑟 par �0 = �0 −

��−��

��𝑟�

* �𝑟 et

• (�� − �� ) ← (�� − �� ) −

��𝑟�

* �𝑟� par

��− ��

(�� − �� ) ← (�� −�� ) −

��𝑟�

* �𝑟�

De cette façon, on peut continuer la résolution du PL précédent comme suit :

Max			1	2	0	0	0
B	CB	P0	P1	P2	Pt1	Pt2	Pt3
Pt1	0	21	1	3	1	0	0
← Pt2	0	18	-1	3	0	1	0
Pt3	0	5	1	-1	0	0	1
Cj – Zj		0	1	2↑	0	0	0
← Pt1	0	3	2	0	1	-1	0
P2	2	6	-1/3	1	0	1/3	0
Pt3	0	11	2/3	0	0	1/3	1
Cj – Zj		-12	5/3↑	0	0	-2/3	0
P1	1	3/2	1	0	½	-1/2	0
P2	2	13/2	0	1	1/6	1/6	0
← Pt3	0	10	0	0	-1/3	2/3	1
Cj – Zj		-29/2	0	0	-5/6	1/6↑	0
P1	1	9	1	0	¼	0	3/4
P2	2	4	0	1	¼	0	-1/4
Pt2	0	15	0	0	-1/2	1	3/2
Cj – Zj		-17	0	0	-3/4	0	-1/4

Les flèches ↑ et ← indiquant respectivement les vecteurs entrant et sortant.

Au dernier tableau, on trouve que tous les Cj - Zj ≤ 0, aucun vecteur ne peut entrer en base sans diminuer la fonction économique de sa valeur actuelle qui vaut 17, donc la valeur maximale de z vaut 17.

On a donc comme solution optimale �1 = 9, �2 = 4 et max z = 17

c. Méthode en deux phases

1. Introduction

L’algorithme du simplexe ne peut être démarré que si l’on dispose d’une première solution de base réalisable, ce qui n’arrive pas toujours aussi facilement que dans l’exemple précédent.

En effet, si l’on peut remarquer que les inégalités de certaines contraintes sont ≥ et les termes indépendants correspondants sont positifs, alors il est évident qu’en annulant n + n’ – m variables de décisions, l’on trouve une solution avec des valeurs négatives.

Par exemple : pour le PL suivant :

max z = 3�1 + �2

Sous les contraintes

−�1 + �2 ≥ 1

{ �1 + �2 ≥ 3

2�1 + �2 ≥ 4

�1 ≥ 0, �2 ≥ 0,

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

−�1 + �2 − �1 = 1

{ �1 + �2 − �2 = 3

2�1 + �2 + �3 = 4

�1 ≥ 0, �2 ≥ 0, �1 ≥ 0, �2 ≥ 0, �3 ≥ 0

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

�1 = −1

Prenons �1 = �2 = 0, on a {�2 = −3, d’où l’on tire la solution (0, 0, -1, -3, 4) qui

�3 = 4

n’est pas une solution de base réalisable. De ce fait l’on ne peut pas démarrer

directement l’algorithme du simplexe.

Pour remédier à cette difficulté, nous allons recourir à la méthode dite en deux phases.

2. Principe de la méthode

La méthode en deux phases n’est en réalité que l’application de l’algorithme du

simplexe en deux phases :

• La première phase consiste à déterminer une première solution de base réalisable pour le PL donnée :

✓ On introduit des variables dites artificielles dans les contraintes qui empêchent de trouver la première SBR pour le PL originale.

✓ On forme une nouvelle fonction économique composée des variables artificielles uniquement :

✓ On détermine sans problème une première SBR du PL intermédiaire ainsi obtenu.

✓ On applique l’algorithme du simplexe.

• La deuxième phase est l’application proprement dite de l’algorithme du

simplexe au PL originale à partir de la SBR obtenue grâce à la phase I.

3. Texte de l’algorithme

Pour un PL à max :

1) Mettre les contraintes sous forme d’égalités ;

2) Rendre positifs les seconds membres des contraintes ;

3) Introduire les variables d’écarts :

� �′

{∑ ��,� �� + ∑ ��,�+� �� = ��

� =1

�=0

�� , �� , �� ≥ 0; � = 1,2, … , �

4) Introduire des variables artificielles dans les contraintes à problème :

∑� = 1��,� �� + ∑�′ = 1��,�+� �� + ∑�′′ = 1��,�+�′+� �� = ��

(∗){ � � �

�� , �� , �� ≥ 0; � = 1,2, … , �

5) Phase I : Résoudre le PL suivant par la méthode du simplexe :

�=0

�� = − ∑�′′ ��

Sous les contraintes (∗) de l’étape 4).

6) Si certaines variables artificielles sont dans la base du dernier tableau simplexe de la phase I alors, le problème de départ n’admet point de solution réalisable, aller à 8) ;

7) Phase II : Le premier tableau simplexe de la deuxième phase sera déduit du dernier tableau simplexe de la première phase de la façon suivante :

✓ On élimine les colonnes des variables artificielles ;

✓ La première ligne désormais est formé des coefficients de la fonction économique du PL d’originale ;

✓ Les autres lignes restent inchangées ;

✓ Les �� − �� doivent être recalculés du fait que les �� sont tirés

maintenant de fonction économique du PL originale.

✓ Exécuter ainsi l’algorithme du simplexe sur ce premier tableau de la phase II ;

8) Fin

Pour un problème à min, c’est la même procédure sauf que l’on a la fonction

� =0

économique �� = ∑�′′ ��

au lieu de �� = − ∑�′′ ��

à la phase I, on

� =0

calcule �� − �� au lieu de �� − �� , et �0 au lieu de −�0 .

Exemple : appliquons la méthode en deux phases sur le PL précédent :

max z = 3�1 + �2

Sous les contraintes

−�1 + �2 ≥ 1

{ �1 + �2 ≥ 3

2�1 + �2 ≤ 4

�1 ≥ 0, �2 ≥ 0,

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

−�1 + �2 − �1 = 1

{ �1 + �2 − �2 = 3

2�1 + �2 + �3 = 4

�1 ≥ 0, �2 ≥ 0, �1 ≥ 0, �2 ≥ 0, �3 ≥ 0

Phase I :

Ajoutons les variables artificielles à la contrainte 1 et 2 :

−�1 + �2 − �1 + �1 = 1

{ �1 + �2 − �2 + �2 = 3

2�1 + �2 + �3 = 4

�1 ≥ 0, �2 ≥ 0, �1 ≥ 0, �2 ≥ 0, �3 ≥ 0, �1 ≥ 0, �2 ≥ 0

On a la fonction économique intermédiaire suivante : max z = −�1 − �2

On a n + n’ + n’’ = 6 et m = 3 et donc n + n’ + n’’ – m = 3 variables à annuler :

�1 = 1

Prenons �1 = �2 = �1 = �2 = 0, on a {�2 = 3

�3 = 4

, d’où l’on tire la solution (0,0,

0,0,1,3,4) qui est une solution de base réalisable. De ce fait l’on peut démarrer

directement l’algorithme du simplexe pour la première phase.

Max			0	0	0	0	0	-1	-1
B	CB	P0	P1	P2	Pt1	Pt2	Pt3	PV1	PV2
←PV1	-1	1	-1	1	-1	0	0	1	0
PV2	-1	3	1	1	0	-1	0	0	1
Pt3	0	4	2	1	0	0	1	0	0
Cj - Zj		4	0	2↑	-1	-1	0	0	0
P2	0	1	-1	1	-1	0	0	1	0
←PV2	-1	2	2	0	1	-1	0	-1	1
Pt3	0	3	3	0	1	0	1	-1	0
Cj - Zj		2	2↑	0	1	-1	0	-2	0
P2	0	2	0	1	-1/2	-1/2	0	1/2	½
P1	0	1	1	0	1/2	-1/2	0	-1/2	½
Pt3	0	0	0	0	-1/2	3/2	1	1/2	-3/2
Cj - Zj		0	0	0	0	0	0	-1	-1

Fin de la première phase, toutes les variables artificielles sont sorties de la base, c’est

– à – dire que le PL de départ est réalisable, la SBR cherchée est (1, 2, 0, 0, 0).

Phase II :

Max			3	1	0	0	0
B	CB	P0	P1	P2	Pt1	Pt2	Pt3
P2	1	2	0	1	-1/2	-1/2	0
P1	3	1	1	0	½	-1/2	0
←Pt3	0	0	0	0	-1/2	3/2	1

Cj – Zj		-5	0	0	-1	2↑	0
P2	1	2	0	1	-2/3	0	1/3
P1	3	1	1	0	1/3	0	1/3
Pt2	0	0	0	0	-1/3	1	2/3
Cj – Zj		-5	0	0	-1/3	0	-4/3

D’où la solution optimale est donnée par �1 = 1, �2 = 2 �� 𝑥 = 5.

d. La méthode du dual-simplexe

d.1. Dualité en programmation linéaire (Programme Primal et

Dual)

Soient les programmes linéaires suivants donnés sous forme canonique :

�=1

1. max � = ∑�

��

Sous les contraintes :

�=1

2. max � = ∑�

��

�

{∑ �� ≤ �� , � = 1,2, … , �

� =0

�� ≥ 0, � = 1,2, … , �

Sous les contraintes :

�

∑ �� ≤ �� , � = 1,2, … , �

{

� =0

�� ≥ 0, � = 1,2, … , �

Si le programme 1) est appelé programme linéaire Primal(P) (Dual), alors le

programme 2) est son programme Dual (D) (Primal).

Il existe une liaison étroite entre ces deux programmes : en effet,

✓ Les coefficients économiques du programme primal sont les termes indépendants du programme dual ;

✓ Les termes indépendants du programme primal sont les coefficients économiques

du programme dual ;

✓ La matrice technique du programme primal est la transposée du programme dual ;

✓ Le dual du dual est le primal ;

✓ Si le primal est non borné (admet une infinité des solutions) alors le dual est

contradictoire (n’admet pas de solutions réalisables) ;

✓ Si le primal admet une solution optimale finie alors le dual admet aussi une solution optimale finie et en ces solutions les deux fonctions économiques coïncident.

d.2. Conditions d’application de l’algorithme du dual-simplexe

L’algorithme du dual-simplexe s’applique à tout programme linéaire :

✓ Ne possédant pas une SBR de départ ;

�� − �� ≤ 0, � = 1,2, … , � (𝑃� à max)

�

✓ Tel que {

�

− ��

≤ 0, � = 1,2, … , � (𝑃� à min)

✓ Dont le Dual possède une SBR de départ.

d.3. Application et texte de l’algorithme du dual-simplexe

Dans l’algorithme du dual-simplexe, on détermine d’abord le vecteur sortant de la base et ensuite le vecteur entrant, contrairement à l’algorithme du simplexe qui procède inversement.

Pour un Pl à max, on a :

1. Mise des contraintes sous forme d’égalités ;

2. Recherche d’une première solution de base non réalisable telle

�� − �� ≤ 0;

3. Construction du 1er tableau simplexe ;

4. Si tous les �� ≥ 0, alors la solution optimale est atteinte, aller à 9) ;

5. S’il existe au moins �� < 0, tel que tous les �� ≤ 0, alors le

problème est non réalisable puisque les contraintes sont de ce fait

contradictoires, aller à 9) ;

6. Changement de base :

• Le vecteur sortant de la base :

𝑃𝑟 sort si �𝑟 = �� {�� |�� < 0} ;

• Le vecteur entrant dans la base :

�� −��

𝑃� entre si

��𝑟�

= �� {

��𝑟�

|�𝑟� < 0} ;

�𝑟� est appelé pivot

7. Construction du nouveau tableau simplexe : même procédure qu’au

simplexe ;

8. 8) Aller à 4) ;

9. 9) Fin.

Même procédure, mais en remplaçant −�0 �� 0 �� − �� − ��

Exemple :

Soit le programme linéaire suivant :

max z = 2�1 + 3�2

Sous les contraintes

4�1 + �2 − �1 = 8

{ �1 + 4�2 − �2 = 8

7�1 + 10�2 − �3 = 47

�1 ≥ 0, �2 ≥ 0, �1 ≥ 0, �2 ≥ 0, �3 ≥ 0

n + n’ = 5, m = 3, n + n’ – m = 2

Pour �1 = �2 = 0, (0,0,−8,−8,−47) qui n’est pas une SBR : démarrons donc le dual-

simplexe :

Min			2	3	0	0	0
B	CB	P0	P1	P2	Pt1	Pt2	Pt3
Pt1	0	-8	-4	-1	1	0	0
Pt2	0	-8	-1	-4	0	1	0
←Pt3	0	-47	-7	-10	0	0	1
Zj - Cj		0	-2↑	-3	0	0	0
Pt1	0	132/7	0	33/7	1	0	-4/7
←Pt2	0	-9/7	0	-18/7	0	1	-1/7
P1	2	47/7	1	10/7	0	0	-1/7
Zj - Cj		94/7	0	-1/7↑	0	0	-2/7
Pt1	0	33/2	0	0	1	11/6	-5/6
P2	3	½	0	1	0	-7/18	1/18
P1	2	6	1	0	0	5/9	-2/9
Zj - Cj		27/2	0	0	0	-1/18	-5/18

D’où la solution optimale est donnée par �1 = 6, �2 = 1/2 et �� = 27/2.

Chapitre troisième : PRESENTATION SUCCINCTE ET PRINCIPE DE FONCTIONNEMENT D’OptSolver

1.1 Présentation

OptSolver	(Optimization	Solver) est un logiciel
d'optimisation écrit en C++ par	nous sur La	collection, l’assemblage et

l’implémentation des algorithmes de R.O. OptSolver, rassemble assez

logiquement au sein d'une même interface ses implémentations des algorithmes d'optimisation dont la majorité appris dans le cadre du cours de recherche opérationnelle.

La principale motivation de la conception d'OptSolver fût le souci de disposer d'un logiciel de Recherche Opérationnel (R.O) qui non seulement résoud un problème mais aussi trace les étapes des calculs...

1.2 Principe de fonctionnement

OptSolver a été conçu dans la simplicité, sans intention de concurrencer les logiciels de référence en R.O. De ce fait, le fait simple de connaître un peu de R.O suffit pour utiliser ce logiciel. Toutes les interfaces graphiques sont si simples à utiliser qu'on peut même se passer de ces quelques lignes de documentation.

Pour chaque concept de R.O implémenté, OptSolver vous présente un éditeur. Ainsi pour les traitements des graphes, vous avez des éditeurs des graphes (Graphe, Réseaux, Graphes MPM, PERT, etc.) ; de même il y a un éditeur des programmes linéaires, un éditeur pour ordonnancement des tâches.

L'IHM de OptSolver est faite de façon que vous puissiez travailler avec plusieurs éditeurs, chacun dans un onglet.

Pour chaque problème, à quelques exceptions près, OptSolver vous propose plusieurs algorithmes de résolution, par exemple pour le problème du plus court chemin (PCC), 4 algorithmes-vous sont proposés : Dijkstra, Ford, Kalaba, Floyd.

1.3 Les principales interfaces

Voici la fenêtre principale d’OptSolver 1.0 que vous avez sous vos yeux lors du premier lancement.

P a g e | 40

Vous trouverez essentiellement dans la page d'accueil, les habituels boutons Nouveau et Ouvrir, une liste des liens aux fichiers enregistrés/ouverts récemment...

✓ Les menus

✓ La barre d'outils

Située juste en-dessous de la barre des menus, elle propose des raccourcis aux options couramment utilisées, entre autres Nouveau, Ouvrir, Enregistrer, etc.

2. Concepts

L'idée à l'origine du développement de OptSolver est de collectionner et implémenter le plus d'algorithmes de R.O possibles et assembler le tout de façon logique sous une même interface ergonomique.

Ainsi par exemple, vous remarquerez dans certains cas, pour un même problème OptSolver vous propose plusieurs méthodes de résolution.

implémentés sont :

Théorie des graphes

En tout et pour tout, les différents algorithmes de R.O

1. Quelques routines sur les propriétés élémentaires des graphes :

o Ordre,

o Degrés,

o Matrices (Sommet-Sommet, Sommet-Arc, Pondérations),

o Itshmes (Ponts),

o Centre de gravité,

o etc.

2. Coloration des sommets et arêtes. :

o Algorithme de Welsh – Powel

3. Détection des composantes (fortement) connexes

4. Problème du plus court chemin (PCC) :

4.1 Algorithmes tree bulider

o Dijkstra,

o Ford,

o Kalaba

4.2 Algorithmes matriciels

o Floyd

5. Problème du plus long chemin (PLC) :

5.1 Algorithmes tree bulider

o Ford,

o Kalaba.

5.2 Algorithmes matriciels

6. Ordonnancement des tâches

o Méthode Potentiel Métra (MPM).

7. Programmation linéaire

o Méthode graphique,

o Méthode de dénombrement,

o Algorithme du simplex (Avec techniques des perturbations

dans le cas d'un cyclage),

o Algorithme du simplex à deux phases,

o Algorithme du dual-simplex.

3. Présentations des éditeurs

OptSolver 1.0 compte au total 6 éditeurs, présentés ci – après :

3.1 Editeur des graphes en général

Avec celui-ci, vous avez des outils essentiels pour construire rapidement et simplement des jolis graphes orientés ou non, les sauvegarder, les exporter, etc... Voici ci-après une image illustrant les mots ci – avant :

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

C'est une simple extension de l'éditeur des graphes en général, il permet de dessiner des graphes pondérés, qu'on nomme souvent réseaux. En image :

3.3 Editeur des graphes MPM

Une variante de l'éditeur des graphes, il vous permet de dessiner vous-mêmes des graphes MPM, illustration :

3.4 Editeur des graphes PERT

Une variante de l'éditeur des graphes, il vous permet de dessiner vous-mêmes des graphes PERT, illustration :

3.5 Editeur des tâches pour ordonnancement

Celui-ci est destiné à vous permettre de saisir les différentes tâches d'un projet, suivant leurs dépendances temporelles, en vue d'un ordonnancement automatique.

3.6 Editeur des programmes linéaires

classiques.

Lui est faite pour la saisie des programmes linéaires

menu Opérations.

Pour exécuter une opération ou un algorithme, aller dans le

4. Editeur des graphes

graphe :

Ci-après, une image de la principale interface de dessin d'un

4.1. La barre d'objets graphiques

Vous y trouverez de gros boutons avec icônes représentant les objets qu'on peut dessiner dans la zone dessin ; à droite, il y a un champ de signification de chaque bouton. Vous pouvez la masquer/Démasquer via le menu fenêtre / Barre d'outils graphiques. Elle est également encrable /desanclable, il suffit de double-cliquer sur sa barre des titres ; vous pouvez aussi la déplacer...

Pour activer un bouton, il suffit de cliquer dessus, et opérer ensuite dans la zone de dessin. Il ne peut y avoir qu'un bouton actif à la fois, celui-ci a une couleur distincte de celle des autres. Sur l'image précédente, c'est le bouton en vert qui est actif.

de dessin.

Le rôle de chaque bouton est expliqué en pratique sur la zone

4.2. La zone de dessin

C'est ici que tout se dessine, simplement avec votre souris et/ou votre clavier. Cette section vous donne les principales procédures pour bien dessiner.

Vous pouvez changer certaines propriétés de la zone de dessin telles que couleur, afficher/masquer grille, axes, etc. via un menu contextuel :

Notez aussi qu'il est possible de "Annuler/Rétablir" des manipulations effectuées sur votre dessin. La profondeur de la pile "annuler/rétablir" est de 200 actions.

Vous trouverez "Annuler/Rétablir" dans le menu Edition ou sur la barre d'outils.

4.2.1.Dessins de différents objets graphiques

Pour dessiner un objet, commencez par activer le bouton correspondant sur la barre d'outils :

✓ Pour dessiner un point ou sommet

Sélectionner l'outil point se trouvant sur la barre d'outils

De cette façon, dessiner autant de points que vous souhaitez.

dessin

Faites ensuite un clic gauche de la souris à l'endroit voulu sur la zone

✓ Pour un segment de droite

Activer le bouton correspondant :

Sur votre souris, faites un clic gauche sur le point de départ, maintenez-le et faites glisser jusqu'au point d'arrivée et lâcher.

✓ Segments de droite consécutifs :

Activer le bouton associé :

Les segments consécutifs sont tels que l'extrémité finale de l'un est l'extrémité initiale du suivant. Faites simplement clic gauche (sans le maintenir) sur le point de départ et faites passer le segment dynamique qui apparaît sur le deuxième point (extrémité finale) en déplaçant le pointeur de la souris ; aussitôt fait, un nouveau segment dynamique apparaît, déplacez-le avec la souris jusqu'à son extrémité finale, et ainsi de suite. Pour finir le dessin, cliquer sur un espace vide de la zone ou appuyer sur le bouton echap.

✓ Pour une boucle

Sélectionner l'outil boucle

Faites ensuite un clic gauche sur un sommet, maintenez-le et déplacez le pointeur de la souris jusqu'à avoir une taille voulu puis relâcher.

✓ Pour un arc de cercle

Sélectionner l'outil arc de cercle

La procédure de dessin est la même que celle pour un segment de droite.

✓ Arcs de cercle consécutifs

Activer le bouton associé,

et procéder comme pour l'outil segments de droite consécutifs.

✓ Pour générer un graphe complet

Sélectionner l'outil :

Indiquer l'ordre du graphe

4.2.2. Manipulations dynamiques d'un graphe

Voici les différentes manipulations possibles :

✓ Sélectionner et déplacer (translation ordinaire)

Activer le bouton Sélection dont l'icône est un pointeur de souris :

Il vous permet de :

✓ Sélectionner un ou plusieurs éléments du graphe :

Faites un clic gauche sur un élément du graphe, il se met en surbrillance permanente (L'élément est sélectionné.)

Pour sélectionner d'autres éléments en plus, appuyer sur Ctrl et faites autant des clics sur ces derniers. Vous pouvez aussi sélectionner sur plage :

Il suffit de maintenir le clic gauche de la souris à partir d'un espace vide de la zone et déplacer le pointeur de la souris jusqu'à ce que le rectangle de sélection générée contienne entièrement les éléments que vous voulez sélectionner et enfin lâcher le clic.

Pour tout sélectionner il suffit de cliquer sur l'option "Edition/Tout sélectionner" ou via le raccourci Ctrl+A. Il est également possible d'inverser la sélection : "Edition/Inverser la sélection" ou Ctrl+Shift+A

Pour tout désélectionner, il suffit cliquer sur une zone vide.

Une fois des éléments en sélection, vous pouvez les supprimer

: "Edition/Effacer" ou appuyer sur la touche delete du clavier

✓ Déplacer un ou plusieurs éléments sélectionnés

Commencer par sélectionner les éléments à déplacer.

Ensuite, soit vous utilisez les touches directions de votre clavier (que vous pouvez combiner aussi avec Ctrl), soit vous cliquez de nouveau sur un des éléments sélectionnés (que vous voulez déplacer) ; maintenez le clic et déplacez le pointeur de la souris.

✓ Sélection et translation relativement au centre des points en sélection ("zoom") ...

Activer le bouton ayant l'icône suivant :

Chaque point sélectionné sera translaté linéairement suivant la direction passant par ce dernier et le centre des points en sélection :

✓ Sélectionner plusieurs points

o Ensuite, cliquer sur un point, maintenez le clic et déplacer le pointeur de la souris.... Le raccourci clavier est Ctrl + touche direction... Dans cet exemple on amoindrit le graphe...

o Résultat...

✓ Rotation autour du barycentre ou centre de gravité des points sélectionnés...

Activer le bouton ayant l'icône suivant :

rotation

Sélectionner les différents objets auxquels vous voulez appliquer la

Pour effectuer la rotation, la procédure est la même que pour la translation relatif sauf que le raccourci clavier approprié pour une rotation minutieuse est Shift + touche direction...

✓ Rotation autour d'un point quelconque

Soit le graphe suivant :

Activer ensuite le bouton correspondant à la "rotation autour d'un point quelconque" :

Définissez le point autour duquel se fera la rotation, vous pouvez sélectionner un des points existants, sur la liste déroulante, par défaut c'est le centre de gravité. Ici nous choisissons le point E comme centre de rotation.

Après une rotation anti-horaire, le graphe se présente comme suit :

4.2.3. Supprimer - Renommer - Masquer/Démasquer

Sur chaque objet dessiné (excepté les textes), un menu contextuel est disponible, sur ce dernier on trouve les options ci-après :

2. Supprimer : Sélectionner un objet, appuyer sur l'action Supprimer du menu contextuel.

3.Renommer

Sélectionner et appuyer sur l'action Renommer.

Astuce : sélectionner un texte et appuyer sur une touche alphanumérique ou numérique du clavier selon que le texte représente une chaîne des caractères ou un réel.

4.Masquer/Démasquer

Sélectionner un objet et appuyer sur l'action Afficher. Il y a également

une option Afficher l'étiquette.

Pour démasquer un objet, il faut le faire via la fenêtre d'objets dessinés ou via la fenêtre des propriétés.

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

Par défaut, elle se situe à gauche de la zone de dessin. Cette fenêtre est par défaut affichée, on peut la masquer en fermant sur la croix en haut en droite de cette fenêtre ou passer par le menu "Fenêtre/Objets dessinés". Notez que vous pouvez également la déplacer et la placer à l'endroit voulu.

Cette fenêtre comprend une liste sous forme d'arbre avec deux sections : Sommets et Arêtes.

Chaque section comprend des items. Chaque item représente un objet dessiné sur la zone de dessin. L'icône d'un item est soit un œil ouvert (l'objet est visible) soit un œil fermé (l'objet est masqué)

Un menu contextuel est disponible sur chaque item. Pour sélectionner des objets, utilisez la même procédure que sur la zone dessin. (Clic, Ctrl+clic, plage de sélection...) Pour sélectionner tous les items d'une section, cliquez sur l'entête de celle-ci.

Il est également possible d'effectuer une translation d'objets sélectionnés : utilisez les boutons directions du clavier.

✓ Sommets : comprend la liste des noms des différents sommets présent sur la zone de dessin (dont le nombre est affiché entre parenthèses) ainsi que leurs coordonnées. Pour sélectionner tous les sommets, il suffit de cliquer sur l'entête.

Il est possible d'éditer le nom ainsi que les coordonnées d'un sommet : double-cliquer sur un item et effectuer la modification au format "nom = (x, y)". Une fois terminée, veillez valider en appuyant sur "Enter."

✓ Arêtes:

✓

Comprend la liste d'arêtes présentes sur la zone de dessin (dont le nombre est affiché entre parenthèses)

Pour chaque item de cette section, il est possible d'éditer le nom ou l'étiquette de l'arête.

Aperçu :

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

Cette fenêtre vous permet d'éditer les propriétés des objets dessinés. Cette fenêtre est accessible de plusieurs façons. Via le menu contextuel (clic droit) d'un élément ou encore Edition/Propriétés.

✓ Présentation succincte des propriétés :

5.l'onglet Général

Changer une étiquette, une pondération, bref un objet de type texte.

Afficher/masquer un objet, un texte associé à un objet...

6.l'onglet Polices et couleurs

La couleur d'un objet, les polices et couleurs des textes associés, sont

modifiables dans cet onglet.

7.L’onglet style

Le style et la taille d'un objet sont modifiables ici.

Notez que la fenêtre des propriétés ne permet de modifier que le graphe en cours de dessin. Si vous souhaitez faire des modifications sur les propriétés par défaut, c'est dans le menu Outils/Options :

Conclusion

Bibliographies:

- A. Hertz and D. De Werra, Using tabu search techniques for graph coloring, Computing 39 (1987), 345-351.

- A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM Journal on Computing 24 (1995), 222{231.

- A.V. Goldberg and R.E. Tarjan, Finding minimum-cost circulations by cancelling negative cycles, Journal of the ACM 36 (1985), 873{886.

- B. Hajek, Cooling schedules for optimal annealing, Mathematics of

Operations Research 13 (1991), 311{329.

- B. KORTE, J. VYGEN, Optimisation Combinatoire, Théorie et Algorithmes, Springer-Verlag France, 2010.

- C. BERGE, Graphes et hypergraphes, Dunod, 1983.

- C. PRINS, Algorithmes de Graphes, Eyrolles, 1994.

- D. de Werra, T. M. Liebling, and Hêche J.-F., Recherche opérationnelle pour

ingénieurs, Presses polytechniques et universitaires romandes, 2003.

- D. Gale and L.S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly (1962), 9{15.

- Dominique de Werra, Thomas M. Liebling et Jean-François Hêche. Recherche

opérationnelle pour ingénieurs [archive] - Presses polytechniques et

universitaires romandes. 2003.

- E. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research 34 (1986), 250{256.

- Éric Jacquet - Lagrèze. Programmation Linéaire - Modélisation et mise en

œuvre informatique [archive] Collection : P.I.Q. Poche - Editeur : Economica

- J. Edmonds and R.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM 19 (1972),

248{264.

- J. G. Kemeny, A. Schleifer, J.L. Snell, G.L. Thompson, trad. par M. Didier, Les Mathématiques modernes dans la pratique des affaires, Paris, Dunod,

1964.

- J. Matousek and B. Gartner, Understanding and using linear programming, Sringer, Berlin Heidelberg New York, 2007.

- J. MATOUSEK, J. NESETRIL, Introduction aux Mathématiques Discrètes, Springer-Verlag France, 2004.

- J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Tech. report, University of California, Los Angeles, 1955.

- JC. FOURNIER, Théorie des Graphes et Applications, Lavoisier, 2006.

- JM. MÉNY, G. ALDON, L. XAVIER, Introduction à la Théorie des Graphes,

Butinage Graphique, CRDP, Académie de Lyon, 2005.

- Kuhn, (1955).

- M. GONDRAN, M. MINOUX, Graphes et Algorithmes, Eyrolles, 1979.

- M. Grotchel, L. Lovasz, and L. Schrijver, Geometric algorithms and

combinatorial optimization, 2nd edition, Springer, Heidelberg, 1994.

- M.R. Garey and D.S. Johson, Computers and intractability : A guide to the theory of np-completness.

- N. Garg and J. Konemann, Faster and simpler algorithms for multicommodity flow and other fractional packing problems, Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 300{309.

- O. COGIS, C. ROBERT, Théorie des Graphes, Problèmes, Théorèmes, Algorithmes, Vuibert, 2003.

- P. Brucker, An efficient algorithm for the job-shop problem with two jobs,

Computing 40 (1988), 353{359.

- R. Correa and C. Lemarechal, Convergence of some algorithms for convex minimization, Mathematical Programming 62 (1993), 261{275.

- R. DIESTEL, Graph Theory, Second Edition, Springer-Verlag, 2000.

- R.K. Ahuja, T.I. Magnanti, and J.B. Orlin, Network flows, Prentice Hall,

1993.

- R.M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Mathematics 23 (1978), 309{311.

- S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling- salesman problem, Operations Research 21 (1973), 498{516.

- S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks

(1972), 195{207.

- S.M. Jonson, Optimal two- and three-stage production schedules with setup

times included, Naval Res. Log. Quart 1 (1954), 61{68.

- T. Terlaky, An easy way to teach interior-point methods, European Journal of

Operational Research 130 (2001), 1{19

- TANGENTE, Les Graphes, Hors-Série N°12, Juin 2002.

- V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Mungala, and V. Pandit,

Local search heuristics for k-median and facility location problems, SIAM

Journal on Computing 33 (2004), 544{562.

- V. Chvatal, Linear programming, W. H. Freeman, New York, 1983.

Webographie :

- (http://www-neos.mcs.anl.gov)

- (http://www.coin-or.org/)

- (http://www.cs.brown.edu/people/pvh/comet/comet.html)

- (http://www.gnu.org/software/glpk/)

- (http://code.google.com/p/or-tools/)

- (http://gusek.sourceforge.net/gusek.html)

- (http://www.graphviz.org/)

- (http://groups.yahoo.com/group/lp solve/)

- (http://www.localsolver.com/)

- (http://OpsResearch.com/OR-Objects)

(http://www.dii.uchile.cl/daespino/)

- (http://www.tsp.gatech.edu/index.html)

- (http://scip.zib.de/doc/html/index.html)

Application

1. Jargon informatique

2. Comment ça Marche

3. Kiwix, Encyclopedie

4. Microsoft ® Encarta ® 2009

5. Grand Robert 2005

ANNEXES

Quelques illustrations des codes sources :

#pragma once

#include <cassert>

extern "C" {

#include "Opt.h"

}

#include "OptUtils.h"

#include "CudaArray.h"

#include "SolverIteration.h"

#include "cudaUtil.h"

#include "NamedParameters.h"

#include "SolverBase.h"

#include <cstdio>

#include <cstring>

static NamedParameters copyParametersAndConvertUnknownsToDouble(const

NamedParameters& original) { NamedParameters newParams(original);

std::vector<NamedParameters::Parameter> unknownParameters =

original.unknownParameters();

for (auto p : unknownParameters) {

auto gpuDoubleImage = copyImageTo(getDoubleImageFromFloatImage(copyImageTo(p.im, OptImage::Location::CPU)), OptImage::Location::GPU);

newParams.set(p.name, gpuDoubleImage);

}

return newParams;

}

static void copyUnknownsFromDoubleToFloat(const NamedParameters&

floatParams, const NamedParameters& doubleParams) {

std::vector<NamedParameters::Parameter> unknownParameters =

doubleParams.unknownParameters();

for (auto p : unknownParameters) {

auto cpuDoubleImage = copyImageTo(p.im, OptImage::Location::CPU); auto cpuFloatImage = getFloatImageFromDoubleImage(cpuDoubleImage); NamedParameters::Parameter param;

floatParams.get(p.name, param);

copyImage(param.im, cpuFloatImage);

}

class OptSolver : public SolverBase {

public:

OptSolver(const std::vector<unsigned int>& dimensions, const std::string& terraFile, const std::string& optName, bool doublePrecision = false) : m_optimizerState(nullptr), m_problem(nullptr), m_plan(nullptr), m_doublePrecision(doublePrecision)

{

Opt_InitializationParameters initParams;

memset(&initParams, 0, sizeof(Opt_InitializationParameters)); initParams.verbosityLevel = 1; initParams.collectPerKernelTimingInfo = 1; initParams.doublePrecision = (int)doublePrecision; m_optimizerState = Opt_NewState(initParams);

m_problem = Opt_ProblemDefine(m_optimizerState, terraFile.c_str(), optName.c_str());

m_plan = Opt_ProblemPlan(m_optimizerState, m_problem, (unsigned int*)dimensions.data());

assert(m_optimizerState); assert(m_problem); assert(m_plan);

}

~OptSolver()

{

if (m_plan) { Opt_PlanFree(m_optimizerState, m_plan);

}

if (m_problem) { Opt_ProblemDelete(m_optimizerState, m_problem);

}

virtual double solve(const NamedParameters& solverParameters, const NamedParameters& problemParameters, bool profiledSolve, std::vector<SolverIteration>& iters) override {

NamedParameters finalProblemParameters = problemParameters;

if (m_doublePrecision) {

finalProblemParameters =

copyParametersAndConvertUnknownsToDouble(problemParameters);

}

setAllSolverParameters(m_optimizerState, m_plan, solverParameters);

if (profiledSolve) {

launchProfiledSolve(m_optimizerState, m_plan, finalProblemParameters.data().data(), iters);

} else {

Opt_ProblemSolve(m_optimizerState, m_plan, finalProblemParameters.data().data());

}

m_finalCost = Opt_ProblemCurrentCost(m_optimizerState, m_plan);

if (m_doublePrecision) {

copyUnknownsFromDoubleToFloat(problemParameters, finalProblemParameters);

}

return m_finalCost;

}

Opt_State* m_optimizerState; Opt_Problem* m_problem; Opt_Plan* m_plan;

bool m_doublePrecision = false;

};

/******************************************************************/

/*fonction retournant le min d'une colonne*/

int min_col (struct mat_cout **mat, int col,int n)

{

int i;

int min=0;

min=mat[0][col].cout; //initialisation du cout min de la colonne for(i=1;i<n;i++)

{

}

return min;

}

if (mat[i][col].cout<min)

min=mat[i][col].cout; //nouveau cout minimum

/******************************************************************/

//fonction retournant la matrice aprés retrait du cout min d'une colonne donnée void col_modif(struct mat_cout **mat,int col,int n,int min)

{

int i;

for(i=0;i<n;i++)

if (mat[i][col].cout!=INFINI)

mat[i][col].cout=mat[i][col].cout-min;

}

/******************************************************************/

//fonction retournant la matrice aprés retrait du cout min de toutes les colonnes void cols_modif(struct mat_cout **mat,int n)

{

int i,min=0;

for(i=0;i<n;i++)

{

min=min_col (mat, i,n);

col_modif(mat,i,n,min);

}

/******************************************************************/

/*fonction retournant le min d'une ligne donnée*/

int min_lign (struct mat_cout **mat,int lign,int n)

{

int i;

int min=0;

min=mat[lign][0].cout; //initialisation du cout min de la ligne for(i=1;i<n;i++)

{

}

return min;

}

if (mat[lign][i].cout<min)

min=mat[lign][i].cout; //nouveau cout minimum

/******************************************************************/

//fonction retournant la matrice aprés retrait de cout min d'une ligne donnée void lign_modif(struct mat_cout **mat,int lign,int n,int min)

{

int i;

for(i=0;i<n;i++)

{

if (mat[lign][i].cout!=INFINI)

mat[lign][i].cout=mat[lign][i].cout-min;

}

/******************************************************************/

//fonction retournant la matrice aprés retrait du cout min dans toutes les lignes void ligns_modif(struct mat_cout **mat,int n)

{

int i,min=0;

for(i=0;i<n;i++)

{

min=min_lign (mat, i,n);

lign_modif(mat,i,n,min);

}

/******************************************************************/

void first_step(struct probleme *prob,struct mat_cout **mat,int n)

{

cols_modif(mat,n);

printf("La matrice apres retranchement des min sur les colonnes est :\n"); Affiche_matrice(mat,prob);

printf("\n");

ligns_modif(mat,n);

}

/******************************************************************/

/*fonction retournant la ligne contenant le nb min de zéro*/

int lign_min (struct probleme *prob)

{

int i,no_lign;

int min=INFINI;

no_lign=0;

for(i=0;i<prob->n;i++)

{

if ((prob->etat[i].o_lign<min)&&(prob->etat[i].o_lign!=0))

{

}

return no_lign;

}

min=prob->etat[i].o_lign; //nouveau ligne minimale no_lign=i;

/******************************************************************/

///rechercher le nb de zéro dans chaque lign et dans chaque col/////

void firstab_nbzero(struct mat_cout **mat,struct probleme *prob)

{

int i,j;

for (i=0; i<prob->n;i++)

{

prob->etat[i].o_lign=0;

prob->etat[i].o_col=0;

}

for(i=0;i<prob->n;i++)

{

for(j=0;j<prob->n;j++)

{

if (mat[i][j].cout==0)

{

prob->etat[i].o_lign++;

prob->etat[j].o_col++;

}

/******************************************************************/

void find_nbzero(struct mat_cout **mat,struct probleme *prob)

{

int i,j;

for (i=0; i<prob->n;i++)

{

prob->etat[i].o_lign=0;

prob->etat[i].o_col=0;

}

for(i=0;i<prob->n;i++)

{

for(j=0;j<prob->n;j++)

{

if ((mat[i][j].cout==0)&&(mat[i][j].encadre==1))

{

prob->etat[i].o_lign++;

prob->etat[j].o_col++;

}

/******************************************************************/

int firstest_opt(struct mat_cout **mat,struct probleme *prob)

{

int i,j,cpt=0,cptr=0; firstab_nbzero(mat,prob); for(i=0;i<prob->n;i++)

{

if(prob->etat[i].o_lign==1) cpt++;

if(prob->etat[i].o_col==1) cptr++;

}

if((cpt==prob->n)&&(cptr==prob->n))

return 1;

return 0;

}

/******************************************************************/

int test_opt(struct mat_cout **mat,struct probleme *prob)

{

int i,j,cpt=0,cptr=0;

find_nbzero(mat,prob);

for(i=0;i<prob->n;i++)

{

if(prob->etat[i].o_lign==1) cpt++;

if(prob->etat[i].o_col==1) cptr++;

}

if((cpt==prob->n)&&(cptr==prob->n))

return 1;

return 0;

}

/******************************************************************/

void search_affec(struct mat_cout **mat,struct probleme *prob)

{

int cpt,i,j,lignemin,indi_o,fine;

int termine;

{ lignemin=lign_min(prob); fine=0;

j=0;

if(prob->etat[lignemin].o_lign!=0)

{

if ((mat[lignemin][j].cout==0)&&(mat[lignemin][j].normal==0)) j++;

else

{

if ((mat[lignemin][j].cout==0)&&(mat[lignemin][j].normal==1))

{

}

j++;

}

mat[lignemin][j].encadre=1; mat[lignemin][j].normal=0; indi_o=j;

prob->etat[lignemin].oenca_lign++; prob->etat[indi_o].oenca_col++; prob->etat[lignemin].o_lign--;

prob->etat[indi_o].o_col--;

fine=1;

}while(fine!=1);

}

if(prob->etat[lignemin].o_lign!=0)

{

for(j=indi_o;j<prob->n;j++)

if ((mat[lignemin][j].cout==0)&&(mat[lignemin][j].normal==1))

{

mat[lignemin][j].barre=1; mat[lignemin][j].normal=0; prob->etat[lignemin].o_lign--;

prob->etat[lignemin].obarre_lign++;

prob->etat[j].obarre_col++;

prob->etat[j].o_col--;

}

if(prob->etat[indi_o].o_col!=0)

{

for(i=0;i<prob->n;i++)

if((mat[i][indi_o].cout==0)&&(mat[i][indi_o].normal==1))

{

mat[i][indi_o].barre=1; mat[i][indi_o].normal=0; prob->etat[i].o_lign--;

prob->etat[indi_o].o_col--;

prob->etat[i].obarre_lign++;

prob->etat[indi_o].obarre_col++;

}

termine = 0;

for(i=0;i<prob->n;i++)

if(prob->etat[i].o_lign==0) termine++;

}while(termine!=prob->n);

}

/******************************************************************/

int min_minitab(struct mat_cout **mat,struct probleme *prob)

{

int i,j,min=INFINI;

for(i=0;i<prob->n;i++)

{

while ((prob->etat[i].lign_mark!=1)&&(i<prob->n)) i++;

if (i==prob->n) break;

for(j=0;j<prob->n;j++)

{

while ((prob->etat[j].col_mark==1)&&(j<prob->n)) j++;

if(j!=prob->n) if(mat[i][j].cout<min)min=mat[i][j].cout;

}

return min;

}

/******************************************************************/

void mintab_act(struct mat_cout **mat,struct probleme *prob,int min)

{

int i,j;

//retrancher la val de min aux col non barrées for(j=0;j<prob->n;j++)

{

while ((prob->etat[j].col_mark==1)&&(j<prob->n))

{

j++;

};

if(j!=prob->n)

for(i=0;i<prob->n;i++)

if(mat[i][j].cout!=INFINI)

mat[i][j].cout-=min;

}

//ajouter la val de min aux lign barrées for(i=0;i<prob->n;i++)

{

while ((prob->etat[i].lign_mark==1)&&(i<prob->n))

{

i++;

};

if (i==prob->n) break;

for(j=0;j<prob->n;j++)

if(mat[i][j].cout!=INFINI)

mat[i][j].cout+=min;

}

/*************détermination des affectations interressentes*************/

int good_affec(struct mat_cout **mat,struct probleme *prob)

{

int i,j,finish,min_tab=0,termine=0;

/////////////marquer les lignes qui ne contiennent aucun zéro/////////////

for(i=0;i<prob->n;i++)

if(prob->etat[i].oenca_lign==0)

{

//printf("lign markee = %d \n",i+1); prob->etat[i].lign_mark=1; termine++;

}

if (termine==0) return 0;

else

{

finish=0;

for(i=0;i<prob->n;i++)

{

if(prob->etat[i].obarre_col!=0)

{

for(j=0;j<prob->n;j++)

if((mat[j][i].barre==1)&&(prob->etat[j].lign_mark==1)&&(prob-

>etat[i].col_mark==0))

{

prob->etat[i].col_mark=1;

finish++;

//printf("finish 1=%d\n",finish);

}

for(i=0;i<prob->n;i++)

{

if(prob->etat[i].oenca_lign!=0)

{

for(j=0;j<prob->n;j++)

if((mat[i][j].encadre==1)&&(prob->etat[j].col_mark==1)&&(prob-

>etat[i].lign_mark==0))

{

prob->etat[i].lign_mark=1;

finish++;

//printf("finish 2=%d\n",finish);

}

}while ((finish==1)||(finish==2));

min_tab=min_minitab(mat,prob);

mintab_act(mat,prob,min_tab);

}

return 1;

}

/*************détermination des affectations interressentes*************/

void sol_finale(struct mat_cout **mat,struct mat_cout **mat_ini,struct probleme

*prob)

{

int i,j,sol=0;

int *sol_vect;

sol_vect=(int*) malloc(prob->n * sizeof(int));

for(i=0;i<prob->n;i++)

{

for(j=0;j<prob->n;j++)

{

if ((mat[i][j].cout==0)&&(mat[i][j].encadre==1))

{

sol_vect[i]=j;

//printf("j = %d\n",j+1);

}

printf("la solution finale est :\n");

for(i=0;i<prob->n;i++)

{

printf("%d ",mat_ini[i][sol_vect[i]].cout);

sol+=mat_ini[i][sol_vect[i]].cout;

if (i!=prob->n-1) printf("+ ");

if (i==prob->n-1)

{

printf("= "); printf("%d",sol); printf("\n");

}

/******************************************************************/

void first_sol_finale(struct mat_cout **mat,struct mat_cout **mat_ini,struct probleme *prob)

{

int i,j,sol=0;

int *sol_vect;

sol_vect=(int*) malloc(prob->n * sizeof(int));

for(i=0;i<prob->n;i++)

{

for(j=0;j<prob->n;j++)

{

if (mat[i][j].cout==0)

}

sol_vect[i]=j;

}

printf("la solution finale est :\n");

for(i=0;i<prob->n;i++)

{

printf("%d ",mat_ini[i][sol_vect[i]].cout);

sol+=mat_ini[i][sol_vect[i]].cout;

if (i!=prob->n-1) printf("+ ");

if (i==prob->n-1)

{

printf("= "); printf("%d",sol); printf("\n");

}

/******************************************************************/

void final_step(struct mat_cout **mat,struct mat_cout **mat_ini,struct probleme

*prob)

{

int pass=0;

:\n");

{

printf("<---Dans l'iteration no %d---> \n",pass+1);

init_etat(prob); firstab_nbzero(mat,prob); search_affec(mat,prob);

printf("La matrice apres la recherche du maximum d'affectations est

Affiche_matrice(mat,prob);

printf("\n");

:\n");

if (good_affec(mat,prob)==0)break;

printf("La matrice apres la recherche des affectations interessentes est

Affiche_matrice(mat,prob);

printf("\n");

pass++;

}while(test_opt(mat,prob)==0);

sol_finale(mat,mat_ini,prob);

}

/******************************************************************/

struct tab_etat

{

int o_lign;//indique le nombre de zéro dans la ligne i int oenca_lign;

int obarre_lign;

int o_col;//indique le nombre de zéro dans la colonne i int oenca_col;

int obarre_col;

int lign_mark;//inique si la ligne i est marquée d'un astèrisque int col_mark;//inique si la colonne i est marquée d'un astèrisque

};

/******************************************************************/

struct mat_cout

{

int cout;//le cout de réalisation de la tàche i par la machine j

int normal;//prend 1 si oui, 0 sinon int encadre;//prend 1 si oui, 0 sinon int barre;//prend 1 si oui, 0 sinon

} ;

/******************************************************************/

struct probleme

lignes et les

{

int n;//nb de tàches ou de machines struct mat_cout **cout_affec;

struct tab_etat *etat; //le nombre de zéros dans chaque ligne

//et dans chaque colonne, les

//colonnes marqués

} ;

/******************************************************************/

//afficher la matrice : mat_cout

void Affiche_matrice(struct mat_cout **mat,struct probleme *prob)

{

int i,j;

for (i = 0; i < prob->n; i++)

{

>cout_affec[i][j].cout);

for(j = 0; j < prob->n; j++)

printf("%d \t",prob->cout_affec[i][j].cout);

//printf("cout %d %d= %d \t",i+1,j+1,prob-

printf("\n");

}

/******************************************************************/

void init_etat(struct probleme *prob)

{

int i,j;

prob->etat=(struct tab_etat *) malloc(prob->n * sizeof(struct tab_etat));

for (i=0; i<prob->n;i++)

for(j=0; j<prob->n; j++)

{

prob->cout_affec[i][j].normal=1; prob->cout_affec[i][j].encadre=0; prob->cout_affec[i][j].barre=0;

}

for (i=0; i<prob->n;i++)

{

prob->etat[i].oenca_lign=0; prob->etat[i].obarre_lign=0; prob->etat[i].oenca_col=0; prob->etat[i].obarre_col=0; prob->etat[i].lign_mark=0; prob->etat[i].col_mark=0;

}

/******************************************************************/

struct probleme *creer_pb(int n)

{

struct probleme *nouveau;

nouveau = (struct probleme *)malloc(sizeof(struct probleme));

if (nouveau!=NULL)

{

nouveau->n=n;

}

return nouveau;

}

/******************************************************************/

struct probleme * lecture(char * ch)

{

FILE *ftp;

struct probleme *prob;

int i,j,n;

if ((ftp=fopen(ch ,"r"))==NULL)

{

}

else

{

printf("erreur!!! impossible d\'ouvrir le fichier voulu\n");

fscanf(ftp,"%d",&n);

printf("le nombre de taches: %d \n",n);

prob= creer_pb(n);

//////////////***Allocation dynamique de la matrice***//////////////

prob->cout_affec=(struct mat_cout **) malloc(prob->n * sizeof(struct mat_cout*));

for (i = 0; i < prob->n; i++)

prob->cout_affec[i]= (struct mat_cout *) malloc(prob->n *

sizeof(struct mat_cout));

for (i=0; i<prob->n;i++)

for(j=0; j<prob->n; j++)

}

fclose(ftp);

fscanf(ftp,"%d",&prob->cout_affec[i][j].cout);

prob->etat=(struct tab_etat *) malloc(prob->n * sizeof(struct tab_etat));

return prob;

}

/******************************************************************/

struct mat_cout ** mat_ini(struct mat_cout **mat,struct probleme *prob)

{

int i,j;

struct mat_cout **mat_init;

mat_init=(struct mat_cout **) malloc(prob->n * sizeof(struct mat_cout*));

for (i = 0; i < prob->n; i++)

mat_init[i]= (struct mat_cout *) malloc(prob->n * sizeof(struct

mat_cout));

for (i=0; i<prob->n;i++)

for(j=0; j<prob->n; j++)

mat_init[i][j]=mat[i][j];

return mat_init;

}

/******************************************************************/

#include <stdio.h>

#include <iostream.h>

#include <malloc.h>

#define INF 100

int ini_mat(int **mat, int nb_sommet)

{

int i,j;

for (i = 1; i <= nb_sommet;i++)

{

for (j = 1; j <= nb_sommet;j++)

{

mat[i][j] = 0;

if (i != j)

{

sommet "<<j<<" : ";

}

return **mat;

cout<<"rentrer le cout entre le sommet "<<i<<" et le cin>>mat[i][j];

}

int ini_pere(int **pere, int nb_sommet)

{

int i,j;

for (i = 1; i <= nb_sommet;i++)

for (j = 1; j <= nb_sommet;j++)

pere[i][j] = i;

return **pere;

}

void affichage(int **mat,int nb_sommet)

{

int i,j;

for (i = 1; i <= nb_sommet;i++)

{

for (j = 1; j <= nb_sommet;j++)

{

cout<<mat[i][j]<<" ";

}

cout<<endl;

}

void floyd(int **mat,int **pere,int nb_sommet)

{

int i,j,k;

for (k = 1;k <= nb_sommet;k++)

{

for (i = 1;i <= nb_sommet;i++)

{

for (j = 1;j <= nb_sommet;j++)

{

if (mat[i][k] + mat[k][j] < mat[i][j])

{

mat[i][j] = mat[i][k] + mat[k][j];

pere[i][j] = pere[k][j];

}

void dijkstra(int **mat,int **pere,int nb_sommet)

{

int i,j,k,i_pp,pg,pp,fin;

pp = 0;

fin = 1;

i = 1;

for (k = 1;k <= nb_sommet;k++) cout<<pere[1][k]<<" ";

cout<<endl;

// for (i = 1;i <= nb_sommet;i++)

// {

while ((fin != 5) || (pg == INF))

{

pg = INF;

for (j = 1;j <= nb_sommet;j++)

{

if ((mat[i][j] <= pg) && (mat[i][j] > pp))

{

pg = mat[i][j];

i_pp = j;

}

cout<<"\npp : "<<pp<<" pg : "<<pg<<"\n";

pp = pg;

for (j = 1;j <= nb_sommet;j++)

{

if ((i_pp != j) && (mat[i_pp][j] < INF))

{

mat[i][j] = mat[i_pp][j] + pp;

pere[i][j] = pp;

}

// for (k = 1;k <= nb_sommet;k++) cout<<pere[1][k]<<" "; for (k = 1;k <= nb_sommet;k++) cout<<mat[1][k]<<" "; cout<<endl;

fin++;

// }

}

fin = 1;

void trace(int **pere, int nb_sommet)

{

int ent,sor,i;

{

cout<<"\nEntrer le sommet d entree : ";

cin>>ent;

if (ent == 0) break;

cout<<"\nEntrer le sommet de sortie : ";

cin>>sor;

cout<<"\nMoi, je vous affiche le chemin : ";

i = sor;

cout<<"S"<<sor;

while (pere[ent][i] != ent)

{

cout<<" <- S"<<pere[ent][i];

i = pere[ent][i];

}

cout<<" <- S"<<ent<<endl;

}while (ent != 0);

}

void main()

{

int nb_sommet;

int choix; int **mat; int **pere; int i;

cout<<"Quel algo voulez utiliser ?\n";

cout<<" 1°) Floyd\n";

cout<<" 2°) Dijkstra\n";

cout<<"Choix : "; cin>>choix; cout<<endl;

// cout<<"Nombre de sommet : ";

// cin>>nb_sommet;

nb_sommet = 6;

mat = (int **)malloc (sizeof(int)*(nb_sommet+1));

for (i = 0;i <= nb_sommet;i++) mat[i] = (int *)malloc

(sizeof(int)*(nb_sommet+1));

pere = (int **)malloc (sizeof(int)*(nb_sommet+1));

for (i = 0;i <= nb_sommet;i++) pere[i] = (int *)malloc

(sizeof(int)*(nb_sommet+1));

// **mat = ini_mat(mat,nb_sommet);

mat[1][1] = 0; mat[1][2] = 10; mat[1][3] = 3; mat[1][4] = INF; mat[1][5] = 6; mat[1][6] = INF;

mat[2][1] = 0; mat[2][2] = 0; mat[2][3] = INF; mat[2][4] = INF;

mat[2][5] = INF;

mat[2][6] = INF;

mat[3][1] = INF; mat[3][2] = 4; mat[3][3] = 0; mat[3][4] = INF; mat[3][5] = 2; mat[3][6] = INF;

mat[4][1] = INF; mat[4][2] = INF; mat[4][3] = 1; mat[4][4] = 0; mat[4][5] = 3; mat[4][6] = INF;

mat[5][1] = INF; mat[5][2] = 0; mat[5][3] = INF; mat[5][4] = INF; mat[5][5] = 0; mat[5][6] = 1;

mat[6][1] = 2; mat[6][2] = 1; mat[6][3] = INF; mat[6][4] = INF;

mat[6][5] = INF;

mat[6][6] = 0;

**pere = ini_pere(pere,nb_sommet);

if (choix == 1)

{

floyd(mat,pere,nb_sommet);

affichage(mat,nb_sommet);

cout<<endl;

affichage(pere,nb_sommet);

cout<<endl;

trace(pere,nb_sommet);

}

if (choix == 2)

{

dijkstra(mat,pere,nb_sommet);

}

/ /**************************************************************//

// proglin.cpp : Defines the entry point for the console application.//

#include "stdafx.h"

/********************************simplexe *************************/

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#include<string.h>

#include<math.h>

#include <conio.h>

enum { AUCUNE, FICHIER};

/*********************//***************main*//********************* //

main(int argc, char *argv[])

{

// variables FILE *fd; int i=0;

int erreur = AUCUNE;

char car;

int NbCont = 0; int NbVar = 0; float **Mat; float **Mat2; float *FctObj; float *FctObj2; int *base;

int chaine;

printf("Algorithme du simplexe : ");

printf("\n(voir aide.txt pour le format a respecter)");

printf("\nfichier ouvert : %s",argv[1]);

if(!(fd=fopen(argv[1],"r")))

{

printf("\n\n Erreur d'ouverture de fichier");

erreur = FICHIER;

}

if(erreur == AUCUNE)

{

// lecture du fichier car = getc(fd); if(car=='#')

{

while(car!='\n')

car=getc(fd);

printf("\n fin de ligne");

}

car = getc(fd); NbCont = car - 48;

car = getc(fd); // caractere fin de ligne car = getc(fd);

while(car!='\n')

car=getc(fd); car = getc(fd); NbVar = car - 48;

car = getc(fd); // caractere fin de ligne

// creation des matrices et tableaux

Mat = (float**)malloc(sizeof(float)*NbCont);

for(i=0; i<NbCont; i++)

{

Mat[i] = (float*)malloc((NbVar+1)*sizeof(float));

}

Mat2 = (float**)malloc(sizeof(float)*NbCont);

for(i=0; i<NbCont; i++)

{

Mat2[i] = (float*)malloc((NbVar+1)*sizeof(float));

}

FctObj2 = (float*)malloc(sizeof(float)*(NbVar+1)); FctObj = (float*)malloc(sizeof(float)*(NbVar+1)); base = (int*)malloc(sizeof(int)*NbCont);

// recuperation de la base

car = getc(fd); // caractere fin de ligne while(car!='\n')

car=getc(fd);

for(int j=0; j<NbCont;j++)

{

fscanf(fd,"%d",&chaine);

base[j] = (float)chaine;

car = getc(fd);

}

// recuperation des contraintes

car = getc(fd); // caractere fin de ligne while(car!='\n')

car=getc(fd);

for(int j=0; j<NbCont;j++)

{

i=0;

while(i<=NbVar)

{

fscanf(fd,"%d",&chaine);

Mat[j][i] = (float)chaine;

car = getc(fd);

i++;

}

car=getc(fd);

while(car!='\n')

car=getc(fd); car=getc(fd); for(i=0;i<=NbVar;i++)

{

FctObj2[i]=0; FctObj[i]=0;

}

i=0;

//recuperation de la fonction objectif while( (car!=EOF) )

{

if(car=='-')

{

car = getc(fd); FctObj[i] = -(car-48);

}

car = getc(fd);

}

//algo simplexe

i++;

// Choix de la var entrante float val = 0;

int *placeE;

int Entree = 0; int *choixPivot; int PVide = 1; int indMin = 0;

float valIndMin = 0;

float *temp;

float **temp2;

float valtemp;

int zero=1; // verifie si il a que des positifs ou pas dans fct obj placeE = (int*)malloc(sizeof(int)*NbVar);

choixPivot = (int*)malloc(sizeof(int)*NbCont);

while(zero!=0)

{

i = 0;

zero = 0;

while( i < NbVar )

{

val = FctObj[i];

if(val<0)

{

}

else

i++;

}

placeE[i] = i+1;

zero = 1;

placeE[i] = 0;

if( zero != 0 )

{

i = 0;

printf("\n\n Variables entrantes possibles : ");

while( i < NbVar )

{

if (placeE[i]!=0)

printf(" %d,",placeE[i]);

i++;

}

printf("\n\n Choix : ");

scanf("%d",&Entree);

// P = { i / Aie > 0 }

i = 0;

while( i < NbCont)

{

valtemp = Mat[i][Entree-1];

if( valtemp > 0 )

{

}

else

i++;

}

PVide = 0;

choixPivot[i] = i+1;

choixPivot[i] = 0;

// si P n'est pas vide on peut continuer l'algo if( PVide == 0 )

{

int deb = 1;

for( int i=0; i<NbCont; i++)

{

if( deb == 1)

{

if( choixPivot[i] > 0 )

Mat[i][Entree-1];

{

}

else

{

valIndMin = Mat[i][NbVar] /

indMin = i;

deb = 0;

if( choixPivot[i] > 0 )

{

Mat[i][Entree-1]) )

Mat[i][Entree-1];

if( valIndMin > (Mat[i][NbVar] /

{

valIndMin = Mat[i][NbVar] /

indMin = i;

}

valIndMin, indMin+1);

printf("\n\n Valeur indice minimum : %f , %d",

//pivotage

for(int i=0; i<NbCont; i++)

{

if( i != indMin )

{

for(int j=0; j<=NbVar; j++)

{

if(Mat[indMin][Entree-1] != 0)

Mat2[i][j] = Mat[i][j] - ((Mat[i][Entree-1]/Mat[indMin][Entree-1])*Mat[indMin][j]);

else

Mat2[i][j] = 0;

}

for(int j=0; j<=NbVar; j++)

{

valtemp = Mat[indMin][Entree-1];

if(valtemp != 0)

Mat2[indMin][j] = Mat[indMin][j]/valtemp;

else

}

Mat2[indMin][j] = 0;

for(int j=0; j<=NbVar; j++)

{

if(Mat[indMin][Entree-1] != 0)

FctObj2[j] = FctObj[j] - ((FctObj[Entree-

1]/Mat[indMin][Entree-1])*Mat[indMin][j]);

else

FctObj2[j] = 0;

}

temp = FctObj2; FctObj2 = FctObj; FctObj = temp;

temp2 = Mat2; Mat2 = Mat; Mat = temp2;

base[indMin] = Entree;

//fin

}

else

}

printf("\n\n Fonction non bornée");

printf("\n\n solution : ");

for(int i=0;i<NbCont;i++)

{

printf("\n X%d : %f",base[i],Mat[i][NbVar]);

}

getch();

}

//**************************************************************** //

// EXEMPLE AVEC UNE RECHERCHE DE CHEMIN MAXIMAL AVEC FLOYD

// Matrice source

string[,] baseMatrix = {

{"-","2","3","-","5","-","7","-"},

{"-","-","-","4","-","6","-","8"},

{"-","-","-","4","5","-","7","-"},

{"-","-","-","-","-","-","-","8"},

{"-","-","-","4","-","6","-","-"},

{"-","-","-","-","-","-","-","8"},

{"-","-","-","-","-","6","-","8"},

{"-","-","-","-","-","-","-","-"}

};

// Création de la manufacture d'algorithmes extrémaux

ExtremalAlgorithmFactory factory = new ExtremalAlgorithmFactory();

// Récupération de l'algorithme voulu, ici FLOYD grâce à une énumération. IExtremalAlgorithm algorithm = factory.GetAlgorithmMethod(EnumExtremalAlgo rithm.FLOYD);

// Envoi du calcul extrémal désiré sur la matrice passée en paramètre, ici MAXIMA L grâce à une énumération algorithm.Calculate(baseMatrix,EnumExtremalPathType.MAXIMAL);

// Récupération des résultats qui peuvent être exploités

int[,] floydMatrix = algorithm.GetMatrix(); // Matrice résultante int[,] floydFathers = algorithm.GetFathers(); // Pères des sommets

Travail disponible en pdf sur demande

Breaking News

Notre Bibliothèque

A propos de nous

Autres rubriques

Contact

Breaking News

Envoyez vos travaux sur WhatsApp

A propos de nous

Autres rubriques

Contact