J
e dédie
ce travail à ceux qui sans leurs aide je ne serais peut-être à Mbanza- Ngungu
c'est-à-dire ma Grande Sœur Nigelle MBOMBO
SHANGA et à mon
frère jumeau Gabriel MWANGU SHANGA , qu'il me soit permis d'adresser une
dédicace spéciale à mon Père Denis SHANGA KAPINGA OSHANGA, mes frères et sœurs Hardy MAKOLON’S, Dorcas BULUNGU, Alégréa SHANGA, sans oublier ma petite sœur Fadiv SHANGA. Mes nièces et neveux préférés : Cathy KAZAMBA, Bethem BULA, Carlos KABUANGA, Jacques KATANGA et Nicole KISANGA.
Enfin big dédicace à toi Gloire KADIMA pour tout ce que tu as fait pour moi.
Eddy MUTOMBO SHANGA
REMERCIEMENTS
J
e remercie
Dieu Tout Puissant
de m'avoir permis de mener à terme ce mini projet qui est pour moi le point de départ
d'une merveilleuse aventure celle
de recherche
source de remise en cause permanent et de perfectionnement perpétuelle.
Tout d'abord qu'il me soit permis de rendre un vibrant hommage à mon encadreur le Professeur Ruffin-Benoit NGOIE MPOY pour avoir bien voulu superviser ce modeste travail et de donner son temps et de son intellect à la réussite de ce projet qui pour moi représente un modèle de réussite et une source de motivation permanente, pour sa disponibilité, et son sens aigu de l'humanisme pédagogique.
Je profite de cette tribune pour remercier les personnes qui de passage, ont pu m'apporter leur contribution que ce soit au niveau des idées qu'à celui des conceptions. Qu'elles trouvent ici l'expression de ma sincère reconnaissance.
Je tiens à remercier les nombreuses personnes qui m'ont encouragé et aidé tout au long de ce travail Keneth MUSAU, Gaston KINGOLE, Roxy NABANGU, Kevine UKOLAMA, Lady MANGUFU, Stevie EFAFE, NDOMOY Maike.
L'aboutissement de ce travail doit beaucoup à ma famille et mes amis qui m'ont soutenu et encouragé durant ces durs moments.
Mes compagnons de lutte : Pladi IKWA, Bruno KABONGO, Esther BISUMBULA, Clara SHONGO ne peuvent être laissés sous silence.
Enfin, je remercie les membres du jury qui ont bien voulu accepter, de lire et évaluer ce modeste travail.
SIGLES ET ABBREVIATION
ALGO : Algorithme
I.D.E : Integrated Development Environment
M.P.M : Méthode Potentiel Métra OptSolver : Optimization Solver P.C.C : Plus Court Chemin P.L.C : Plus Long Chemin
PL : Programmation Linéaire
P.O.O : Programmation Orienté Objet
Qt : Bibliothèque pour le langage de programmation C++, elle permet de créer des fenêtres et menus, mais aussi d’utiliser les fonctionnalités réseau de la machine.
Qt SDK : Framework
RO : Recherche Opérationnelle
SBR : Solution de base réalisable
Table des matières
Table des matières ..........................................................................................................iv
INTRODUCTION...........................................................................................................7
1. Problématique ..........................................................................................................7
2. 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
�
�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
0.
✓ 0 = ( . )
0
c. Les variables d’écarts
On peut remplacer les inéquations (les contraintes liées) par des équations
à l’aide d’un ensemble des variables qu’on appellera variables d’écarts :
En effet, soit par exemple le programme linéaire suivant :
max z = �1 + �2 + �3
Sous les contraintes
�1 + 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.
16
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 ) |
c1 |
c2 |
⋯ |
cr |
⋯ |
cm |
cm+1 |
⋯ |
ck |
⋯ |
cn+n’ |
||
Base(B) |
CB |
Po |
P1 |
P2 |
⋯ |
Pr |
⋯ |
Pm |
Pm+1 |
⋯ |
Pk |
⋯ |
Pn+n’ |
P1 |
c1 |
x1 |
1 |
0 |
⋯ |
0 |
⋯ |
0 |
x1,m+1 |
⋯ |
x1,k |
⋯ |
x1,n+n’ |
P2 |
c2 |
x2 |
0 |
1 |
⋯ |
0 |
⋯ |
0 |
x2,m+1 |
⋯ |
x2,k |
⋯ |
x2,n+n’ |
⋮ |
|
|
|
|
⋮ |
|
⋮ |
|
|
⋮ |
|
⋮ |
|
Pr |
cr |
xr |
0 |
0 |
⋯ |
1 |
⋯ |
0 |
xr,m+1 |
⋯ |
xr,k |
⋯ |
xr,n+n’ |
⋮ |
|
|
|
|
⋮ |
|
⋮ |
|
|
⋮ |
|
⋮ |
|
Pm |
cm |
xm |
0 |
0 |
⋯ |
0 |
⋯ |
1 |
xm,m+1 |
⋯ |
xm,k |
⋯ |
xm,n+n’ |
PL à max |
- z0 |
0 |
0 |
⋯ |
0 |
⋯ |
0 |
cm+1 - zm+1 |
⋯ |
ck - zk |
⋯ |
cn - zn |
|
PL à min |
z0 |
0 |
0 |
⋯ |
0 |
⋯ |
0 |
zm+1 - cm+1 |
⋯ |
zk - ck |
⋯ |
zk - ck |
Les notations employées sont :
• Pj { � ∈ {1,2, … , �}: ������� �� ����
� ∈ {� + 1, … , � + �′}: ������� ℎ��� ����
• �� , � = 1,2, … , �: ����������� ��� �� ���� �� �������� é��������� �;
• �� , � = 1,2, … , � ∶ ������� �� �� �������� �� ���� �� ��� ������é�é�;
• ��� (� = 1,2, … , �; � = � + 1, … , � + �′ ): ����������� �� �� �è��� ��������
���� �� ��� ����������.
• �� , � = 1,2, … , � + �′ ∶ �� = ∑ �� �� , � ∈ {1,2, … , � + �′}, �� é���� ���
�������� �� �� ���� �� �� �� ����������� ������������ ���� �� ��������
��������.
• �0, � ∈ {1,2, … , � + �′ }: �0 = ∑ �� �� , �� é���� ��� �������� �� �� ���� ��
�� �� ����������� ������������ ���� �� �������� ��������.
• La première colonne contient la liste des vecteurs de base (à l’étape considérée
; nous parlerons également de variables de base) ;
• La deuxième colonne contient les coefficients économiques associés aux variables de base ;
• La troisième colonne contient les valeurs prises par lesdites variables de base,
c’est – à – dire la solution de base correspondante ;
Ainsi si l’on considère par exemple le programme linéaire suivant :
max z = �1 + 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 :
1
𝑥
• 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.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://groups.yahoo.com/group/lp solve/)
- (http://www.localsolver.com/)
- (http://OpsResearch.com/OR-Objects)
(http://www.dii.uchile.cl/daespino/)
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;
do
{ lignemin=lign_min(prob); fine=0;
j=0;
if(prob->etat[lignemin].o_lign!=0)
{
do
{
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
{
do
{
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;
do
:\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;
do
{
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);
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