Bonjour, nous sommes le 29/04/2025 et il est 09 h 07.

 

 

 

 

 

 

 

 

 

 

 

J

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

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

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

 

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

 

 

 

 

 

 

 

 

 

 

Eddy MUTOMBO SHANGA


 

 

 

REMERCIEMENTS

 

 

J

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

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

 

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

 

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

 

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

 

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

 

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

 

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


 

 

 

SIGLES ET ABBREVIATION

 

 

ALGO                           : Algorithme

 

I.D.E                             : Integrated Development Environment

 

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

PL                                 : Programmation Linéaire

 

P.O.O                            : Programmation Orienté Objet

 

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

 

Qt SDK                         : Framework

 

RO                                : Recherche Opérationnelle

 

SBR                               : Solution de base réalisable


 

 

 

Table des matières

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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


 

 

 

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

 

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

 

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

 

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

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

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

 

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

 

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

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

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

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

 

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

 

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

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

 

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

 

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


 

 

 

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

Chapitre troisième : PRESENTATION SUCCINCTE ET PRINCIPE DE

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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


 

 

 

INTRODUCTION

 

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

 

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

 

1. Problématique

 

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

 

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

 

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

 

Les fis à relever dans cette recherche sont les suivants :

 

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

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

(marche de la résolution).

 

 

2. Hypothèse

 

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

 

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


 

 

 

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

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

 

3. Objectifs du travail

 

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

 

 

4. Choix et intérêt du sujet

 

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

 

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

 

 

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

 

5. Méthodologie de la recherche

 

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


 

 

 

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

 

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

 

6. Délimitation du sujet

 

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

 

1.  Coloration des sommets et arêtes,

 

2.  Détection des composantes (fortement connexes)

 

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

 

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

 

5.  Ordonnancement des tâches et

 

6.  La programmation liaire.

 

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

 

7. Subdivision du travail

 

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

 

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

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

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


 

 

 

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

Recherche Opérationnelle.

 

 

I.1. Théorie de Graphe

 

I.1.1. Historique

 

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

 

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

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

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

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

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

 

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

 

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


 

 

 

I.1.2. Définitions

 

1.1.2.1.   Graphes Orientés

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G : X → P (X)

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

 

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

 

1.1.2.2.   Chemin

 

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

 

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

 

1.1.2.3.   Boucle               X

Est un arc du type (x, x)

 

1.1.2.4.   Circuit

 

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

 

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

 

1.1.2.5.   Chemin hamiltonien

 

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


 

 

 

 

1.1.2.6.   Hamiltonien

 

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

 

1.1.2.7.   Isthme

 

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

 

1.1.2.8.   Arc

 

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

 

1.1.2.9.   Boucle

 

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

 

1.1.2.10.  Coloration de graphe

 

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

 

1.1.2.11.  K-coloration

 

Coloration d'un graphe en k couleurs distinctes.

 

1.1.2.12.  Graphe connexe

 

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

 

1.1.2.13.  ud

 

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

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

 

1.1.2.14.  Nombre chromatique

 

Nombre minimum de couleurs pour colorer un graphe.


 

 

 

1.1.2.15.  Ordre

 

Nombre de sommets du graphe.

 

1.1.2.16.  Graphe planaire

 

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

 

1.1.2.17.  Graphe pondéré

 

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

 

1.1.2.18.  Graphe trivial

 

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

 

1.1.2.19.  Valuation

 

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

 

I.2. Recherche Opérationnelle

 

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

 

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


 

 

 

Chapitre

deuxième :      QUELQUES      ALGORITHMES

EN

 

THEORIE       DES      GRAPHES

ET


 

 

 

II.1. Théorie des graphes


RECHERCHE OPERATIONNELLE


 

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

 

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

 

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

les joignant à tous les autres sommets du graphe.

 

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

 

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

 

Définitions :

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

 

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

 

 

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


 

 

 

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

 

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

Kalaba sont satisfaisants.

 

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

 

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

 

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

 

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

 

 

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

 

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

réseau avec.

 

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

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

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

minimale (maximale). »

 

b.1. Algorithme de Dijkstra

 

 

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

 

1)  Enoncé de l’algorithme

 

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

 

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


 

 

 

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

nœuds, un booléen arret.

 


Initialisations

 

 

poids(x) = +;

pred(x) = x;

fin pour

 

 

poids(s) 0 ;

S←;

S’ ←X;

arret faux;


pour tout x X faire


 

 

Début

 

tant que (S X et  arret = faux) faire

arret = faux ;

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

si (poids(x) =+) alors

arret vrai;

finsi

 


si  (arret = faux) alors

S←S {x} ;


 

 

S←S’{x};


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

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

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

pred(y) u ;


 

 

 

finsi fin tant que Fin


finsi finpour


 

 

2)  Explication

 

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

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

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

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

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

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


 

 

 

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

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

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

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

 

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

 

b.2. Algorithme de Ford

 

 

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

 

1)  Enoncé de l’algorithme :

 

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

 

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

 

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

 

Initialisations

 

pour tout x X faire

poids(x) = +;

pred(x) = x;

fin pour

 

 

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

k←0;


 

 

 

Début

 


faire


 

modif = faux ;

 

 

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

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

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

alors]


 

 

 

 

 

finsi finpour

finpour


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

pred(y) u ;

modif = vrai ;


 

si(modif = vrai)

k  k+1;

finsi

tant que(modif = vrai etk <n)

 

Fin

 

2) Explications

 

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

 

b.3. Algorithme de Kalaba

 

 

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

 

1)  Enoncé de lalgorithme :

 

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


 

 

 

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

 

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

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

 

Initialisations

 

poids(s) 0 ;

S {s} ;

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

poids(x) d(u) ;

pred(x) s ;

S S {x} ;

sinon

poids(x) +∞ ;

finsi fin pour

stab faux ;

k 0 ;

n #X ;

 

Début

 

Tant que stab = faux et k < n faire

stab ←  vrai ;

pour chaque sommet x ϵ X {s} faire

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

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

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

d(u)) alors]

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

pred(x) y ;

stab = faux ;


 

 

 

 

 

 

 

 

 

 

 

Fin


finsi finpour

fin pour

si(modif = faux)

k k+1;

finsi

tant que(modif = vrai  et k < n)


 

 

 

2) Explications

 

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

 

II.2. Algorithmes doptimisation des programmes linéaires

 

 

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

 

II.2.1 Définition dun programme linéaire

 

 

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

 

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

 

a11x1+a12x++a1n xn < b1

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

 

 

 

 

am1x1+am2x++amn xn < bm

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

 

 

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


=1

 
contraintes :  =


 


 

Dans les expressions ci-haut :

 

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

nombres réels donnés ;

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

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


 

 

 

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

puisqu’elles lient les variables structurelles.

 

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


=1

 
 La  fonction  linéaire  =


 


 

est  appelée fonction économique  ou


fonction objective.

 

S’il faut :

 

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

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

à max).

 

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

 

Exemples

 

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

 

1 + 2 3   8

{ 21 2 + 3   16

21 + 2 + 53   26

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

 

²1 + 2 3   8

21 𝐼(2 ) + 3   16

21 + 2 + 513   26

1

 
1 + 2 −      ≥ 1

{                             3

 


3. Fonction économique :


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

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


 

 

 

II.2.2 Notation dun programme linéaire

 

a. Notation canonique

 

 


La notation canonique d’un PL est la suivante :

=1

 
Optimiser      =


 


 

Sous les contraintes

 


 

{  =1


     ,  = 1,2, ,


   0  = 1,2, ,

Exemple : Voici un programme linéaire sous forme canonique

 

max z = 1 + 2 + 3

 


Sous les contraintes


1 + 2 3   8

{    21 2 + 3   16

21 + 2 + 53   26

1   0,  2   0,  3   0


 

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

 

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

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

 

 

 

b. Notation matricielle

 

 

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

Avec :

 


   C = (


1

2

.  )

𝑛


 

 

 


.

.

.

.

.

.

 

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


11 . . .


1

)


1 ��

 

La matrice A est appelée matrice technique.

 


 B = (


1

2

.  )

𝑛


 

 

0

0.

   0 = ( . )

0

 

 

c. Les variables d’écarts

 

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

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

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

max z = 1 + 2 + 3

 


Sous les contraintes


1 + 22   40

{    1   9

21 + 2   35

1   0,  2   0


 

Equivaut au programme linéaire

 

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

 

 

 


Sous les contraintes


1 + 22 +  = 40

1 2 + 2  = 9

21 + 2  = 35

1  + 2  = 29

1   0,   0,   0, 2   0,   0

{


 

 

 

Notons que :

 

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

car elles y interviennent avec des coefficients nuls.

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

variables des décisions.

 

II.3 Quelques autres définitions importantes

 

 


a.   Solutions dun programme linéaire

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


1

2

.

𝑛


)des  valeurs  de


 

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

 

 

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

 

 

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

ou maximise) la fonction économique.

 

b. Bases

 

 

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

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

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

 

 

 

c. Solution de Base(SB)

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

de Cramer obtenue.

 

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


 

 

 

d.  Solution optimale

 

 

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

 

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

 

 

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

 

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

 

 

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

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

 

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

 

Principe de la méthode :

 

Etape 1. Rechercher les solutions de base du PL :

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

résolvant le système de Cramer obtenu.

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

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

 

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

 

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


on a (20) = 20!


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


16

Exemple


16!4!


 

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

max z = 1 + 22


 

 

 


Sous les contraintes


1 + 32   21

1 + 32   18


{

1 2   5

1   0,  2   0

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

1 + 32  = 21

{                     1 + 32  = 18

1 2  = 5

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

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

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

1 + 32 + 1  = 21

{1 + 32 + 2  = 18

1 2 + 3  = 5

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

1 =21,        2  =18,       3 = 5

 


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


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


3          3!2!

 

ETAPE 1 : Rechercher les solutions de base du PL

 

 

Points

 

 

x1

 

 

x2

 

 

t1

 

 

t2

 

 

t3

 

 

S1

 

0

0

21

18

5

 

S2

 

0

7

0

-3

12

 

S3

 

0

6

3

0

11

 

S4

 

0

-5

36

33

0

 

S5

 

21

0

0

39

-16

 

S6

 

-18

0

39

0

23

 

S7

 

5

0

16

23

0

 

S8

 

3/2

13/2

0

0

10

 

S9

 

9

4

0

15

0

 

S10

 

33/2

23/2

-30

0

0


 

 

 

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

 

 

Points

 

 

x1

 

 

x2

 

 

t1

 

 

t2

 

 

t3

 

 

z

 

 

S1

 

0

0

21

18

5

 

0

 

 

S3

 

0

6

3

0

11

 

12

 

 

S7

 

5

0

16

23

0

 

5

 

 

S8

 

3/ 2

13/2

0

0

10

 

29/2

 

 

S9

 

9

4

0

1 5

0

 

17

 

 

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

 

 

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

 

b. La méthode du simplexe

 

1) Théomes

 

 

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

 

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

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

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

 

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

 

2) Principe de lalgorithme

 

 

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

 

Les étapes de l’algorithme sont :

 

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

 

 

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

minimiser) progressivement la valeur de la fonction économique ;


 

 

 

 

 

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

 

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

 

Max(Min )

c1

c2

cr

cm

cm+1

ck

cn+n’

Base(B)

CB

Po

P1

P2

Pr

Pm

Pm+1

Pk

Pn+n’

P1

c1

x1

1

0

0

0

x1,m+1

x1,k

x1,n+n’

P2

c2

x2

0

1

0

0

x2,m+1

x2,k

x2,n+n’

 

 

 

 

 

 

 

 

 

Pr

cr

xr

0

0

1

0

xr,m+1

xr,k

xr,n+n’

 

 

 

 

 

 

 

 

 

Pm

cm

xm

0

0

0

1

xm,m+1

xm,k

xm,n+n’

PL à max

- z0

0

0

0

0

cm+1

zm+1

ck      -

zk

cn -  zn

PL à min

z0

0

0

0

0

zm+1

cm+1

zk      -

ck

zk - ck

 

Les notations employées sont :

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

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

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

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

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

��� �� è���   .

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

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

é.

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

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

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

; nous parlerons également de variables de base) ;

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

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

c’est à dire la solution de base correspondante ;


 

 

 

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

max z = 1 + 22

 


Sous les contraintes


1 + 32   21

{ 1 + 32   18

1 2   5

1   0,  2   0,


 

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

 

 

 

 

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

1  = 21

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

3  = 5

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

simplexe).

 

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

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

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

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

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

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

Dans la colonne P0, on mettra les valeurs 21, 18 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 + 32 + 1 + 0 2 + 0 3  = 21

{1 + 32 + 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 à 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 lalgorithme 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 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 infini 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 = 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 = 31 + 2

 


Sous les contraintes


1 + 2   1

{     1 + 2   3

21 + 2   4

1   0,  2   0,


 

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

1 + 2 1  = 1

{                    1 + 2 2  = 3

21 + 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 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 lalgorithme

 

 

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 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  au lieu de .

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

 

max z = 31 + 2

 


Sous les contraintes


1 + 2   1

{     1 + 2   3

21 + 2   4


1   0,  2   0,

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

1 + 2 1  = 1

{                    1 + 2 2  = 3

21 + 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

21 + 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 dapplication de lalgorithme 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 lalgorithme 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 = 21 + 32

 


Sous les contraintes


41 + 2 1  = 8

{                  1 + 42 2  = 8

71 + 102 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 : 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 DOptSolver

 

 

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

 

 

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


 

 

 

Résultat...

 

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

 

Activer le bouton ayant l'icône suivant :

 

 

 


 

 

rotation


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


 

 

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

 

 Rotation autour d'un point quelconque

 

Soit le graphe suivant :


 

 

 

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

 

 

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

 

 

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

 

 


 

 

 

4.2.3. Supprimer - Renommer - Masquer/Démasquer

 

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

 

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

3.Renommer

Sélectionner         et         appuyer         sur         l'action Renommer.

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

4.Masquer/Démasquer

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

une                               option Afficher                               l'étiquette.

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

 

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

 

 

 

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


 

 

 

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

 

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

 

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

 

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

 

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

 

 

 

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

 

 Arêtes:

 

 

 

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

 


 

 

 

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

 

Aperçu :

 

 

 

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

 

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

 


 

 

 

 Présentation succincte des propriétés :

 

5.l'onglet Général

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

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

6.l'onglet Polices et couleurs

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

modifiables dans cet onglet.

7.L’onglet style

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

²

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

 


 

 

 

Conclusion


 

 

 

Bibliographies:

 

 

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

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

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

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

Operations Research 13 (1991), 311{329.

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

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

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

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

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

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

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

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

universitaires romandes. 2003.

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

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

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

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

248{264.

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

1964.

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

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

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

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

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

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

Kuhn, (1955).

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

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

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


 

 

 

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

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

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

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

Computing 40 (1988), 353{359.

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

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

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

1993.

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

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

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

(1972), 195{207.

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

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

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

Operational Research 130 (2001), 1{19

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

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

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

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

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

 

 

Webographie :

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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


 

 

 

Application

1. Jargon informatique

2. Comment ça Marche

3. Kiwix, Encyclopedie

4. Microsoft ® Encarta ® 2009

5. Grand Robert 2005


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ANNEXES


 

 

 

Quelques illustrations des codes sources :

 

#pragma once

 

#include <cassert>

 

extern "C" {

 

#include "Opt.h"

 

}

 

#include "OptUtils.h"

 

#include "CudaArray.h"

 

#include "SolverIteration.h"

 

#include "cudaUtil.h"

 

#include "NamedParameters.h"

 

#include "SolverBase.h"

 

#include <cstdio>

 

#include <cstring>

 

static NamedParameters copyParametersAndConvertUnknownsToDouble(const

NamedParameters& original) { NamedParameters newParams(original);

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

original.unknownParameters();

 

for (auto p : unknownParameters) {

 

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

 

newParams.set(p.name, gpuDoubleImage);

 

}

 

return newParams;

 

}

 

static void copyUnknownsFromDoubleToFloat(const NamedParameters&

floatParams, const NamedParameters& doubleParams) {


 

 

 

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

doubleParams.unknownParameters();

 

for (auto p : unknownParameters) {

 

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

floatParams.get(p.name, param);

 

copyImage(param.im, cpuFloatImage);

 

}

 

}

 

class OptSolver : public SolverBase {

 

public:

 

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

 

{

 

Opt_InitializationParameters initParams;

 

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

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

 

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

 

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


 

 

 

}

 

~OptSolver()

 

{

 

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

}

 

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

}

 

}

 

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

 

NamedParameters finalProblemParameters = problemParameters;

 

if (m_doublePrecision) {

 

finalProblemParameters =

copyParametersAndConvertUnknownsToDouble(problemParameters);

 

}

 

setAllSolverParameters(m_optimizerState, m_plan, solverParameters);

 

if (profiledSolve) {

 

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

 

} else {

 

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

 

}

 

m_finalCost = Opt_ProblemCurrentCost(m_optimizerState, m_plan);

 

if (m_doublePrecision) {

 

copyUnknownsFromDoubleToFloat(problemParameters, finalProblemParameters);

 

}


 

 

 

return m_finalCost;

 

}

 

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

bool m_doublePrecision = false;

 

};

 

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

 

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

 

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

 

{

 

int i;

 

int min=0;

 

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

{

 


 

 

 

 

 

}

 

return min;

 

}


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

 

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


 

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

 

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

{

 

int i;

 

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

 

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


 

 

 

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

 

}

 

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

 

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

{

 

int i,min=0;

 

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

 

{

 

min=min_col (mat, i,n);

 

col_modif(mat,i,n,min);

 

}

 

}

 

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

 

/*fonction retournant le min d'une ligne done*/

 

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

Travail disponible en pdf sur demande