Dédicace

Dédicace
Du profond de mon cœur, je dédie ce travail à tous
ceux qui me sont chers,

A MA FAMILLE

Que ce modeste travail soit l’expression de ma

reconnaissance pour leur soutien moral qu’elle n’a
cessé de prodiguer

A MES AMIS

Pour l’amour et le respect qu’ils m’apportent, pour

leurs aides, leurs encouragements et leurs
disponibilités.

EL-ALI

Un petit dessin vaut mieux

qu’un grand discours,

Napoléon.

Projet de Fin d’Etudes Page | 1

Remerciements

Remerciements
Au terme de cette mémoire de projet de fin d’études, je
tiens à remercier mon encadrant Mr : Youssef AKDIM pour
ses orientations tout au long de l’élaboration de ce travail,
ses qualités de conseils et ses encouragements.

J’exprime mes sincères remerciements à tous les

enseignants des filières SMI-SMA pour la qualité de
formation qu’ils m’ont fournie tout au long de ce cursus et
pour leurs dévouements.

J’adresse mes sincères remerciements à tous les membres

de jury qui me font le grand honneur d’évaluer ce modeste
travail.

Projet de Fin d’Etudes Page | 2

Introduction générale

Table des matières

DEDICACE ________________________________________________________________________________ 1

REMERCIEMENTS ________________________________________________________________________ 2

TABLE DES MATIERES ____________________________________________________________________ 3

INTRODUCTION GENERALE ______________________________________________________________ 5

1. TENTATIVE DE DEFINITION__________________________________________________________ 7

2. DOMAINE D’APPLICATION ___________________________________________________________ 7

2.1. DOMAINE COMBINATOIRE :____________________________________________________________ 7

2.2. DOMAINE ALEATOIRE _______________________________________________________________ 8
2.3. DOMAINE COMBINATOIRE CONTINU ____________________________________________________ 8

CHAPITRE I : THEORIE DES GRAPHES ____________________________________________________ 9

INTRODUCTION _________________________________________________________________________ 10

1. VOCABULAIRES DE LA THEORIE DES GRAPHES _______________________________________ 10

1.1 GRAPHE __________________________________________________________________________ 10

1.2 RESEAU DE TRANSPORT [FIGURE 1] ____________________________________________________ 11
1.3 GRAPHE BIPARTI [FIGURE 2] _________________________________________________________ 11
1.4 PROBLEME DE COUPLAGE MAXIMUM DANS UN GRAPHE BIPARTI _____________________________ 12

2. TECHNOLOGIES UTILISEES _________________________________________________________ 13

2.1 LANGAGE JAVA ____________________________________________________________________ 13

2.2 ECLIPSE __________________________________________________________________________ 13

CHAPITRE II : PROBLEME D’AFFECTATION______________________________________________ 15

INTRODUCTION _________________________________________________________________________ 16

1. MODELISATION ____________________________________________________________________ 16

2. PROBLEME D’AFFECTATION ________________________________________________________ 16

2.1 FORMULATION DE PROBLEME_________________________________________________________ 17

3. RESOLUTION PAR LA METHODE HONGROISE (KUHN, EGERVARY, KÖNIG) _____________ 18

3.1. PRINCIPE DE LA METHODE HONGROISE _________________________________________________ 18

3.2. ALGORITHME HONGROIS ____________________________________________________________ 19
3.3 APPLICATION DE L’ALGORITHME HONGROIS : EXEMPLE ____________________________________ 21

CHAPITRE III : PROGRAMMES DE TRANSPORT __________________________________________ 30

INTRODUCTION : ________________________________________________________________________ 31

Projet de Fin d’Etudes Page | 3

Introduction générale
1. PRESENTATION DU PROBLEME DE TRANSPORT _____________________________________ 31

2. FORMULATION DU PROBLEME _____________________________________________________ 31

3. RESOLUTION DU PROBLEME _______________________________________________________ 33

3.1. LA RESOLUTION DU PROBLEME PAR LA METHODE DE COIN NORD-OUEST ______________________ 34

3.2. OBTENTION D’UNE SOLUTION DE BASE PAR LA METHODE DE BALAS-HAMMER __________________ 46

CHAPITRE IV : IMPLEMENTATION ______________________________________________________ 52

INTRODUCTION _________________________________________________________________________ 53

1. PRESENTATION DE L’APPLICATION_________________________________________________ 53

1.1. MENU PRINCIPAL __________________________________________________________________ 53

2. PROBLEME D’AFFECTATION __________________________________________________________ 53

2.1. CHOISIR LA TAILLE DU TABLEAU ______________________________________________________ 53

2.2. PARCOURIR LE FICHIER DES DONNEES __________________________________________________ 54
2.3. CHARGER LE FICHIER DATA __________________________________________________________ 54
2.4. LANCER LA RESOLUTION DU PROBLEME _________________________________________________ 55
2.5 RESOLUTION DU PROBLEME D’AFFECTATION _____________________________________________ 56

3. PROBLEME DE TRANSPORT___________________________________________________________ 56

3.1. PARCOURIR LE FICHIER DES DONNEES ___________________________________________________ 56

3.2. CHARGER LE FICHIER DE DONNEES _____________________________________________________ 57
3.3. LANCER LA RESOLUTION PAR LA METHODE COIN NORD-OUEST ______________________________ 57
3.4. LANCER LA RESOLUTION PAR LA METHODE STEPPING STONE ________________________________ 58

CONCLUSION ___________________________________________________________________________ 59

ANNEXE_________________________________________________________________________________ 60

REFERENCES BIBLIOGRAPHIQUES ______________________________________________________ 61

REFERENCES NETOGRAPHIQUES _______________________________________________________ 61

Projet de Fin d’Etudes Page | 4

Introduction générale

Introduction
Générale

Projet de Fin d’Etudes Page | 5

Introduction générale
out projets de petite ou grande envergure, est amené à faire face à des problèmes

T qui nécessitent la mise en œuvre d’un procédé d’optimisation et de prise de

décision dans de nombreux domaines (économique, industriel, militaire, sciences
sociales …etc.)

Au quotidien, des problèmes combinatoires complexes, particulièrement, relatifs à la gestion

des ressources des systèmes étudiés émergent lors des phases de planification et de gestion.
Ces problèmes présentent des caractéristiques communes en termes de problématiques et de
contraintes, liées à une forte limitation des ressources disponibles, du temps et à la
dynamique des systèmes. De plus en plus, les approches de résolution de ces problèmes font
appel aux méthodes et techniques issues des domaines de la Recherche Opérationnelle et de
l’Intelligence Artificielle. Parmi ces problèmes on cite les problèmes d’affectation et de
transport.
La théorie des graphes est un très vaste domaine, en évolution constante ; elle offre un
grand intérêt pédagogique certain. En effet les graphes modélisent de très nombreuses
situations. Du fait de l’importance que revêt l’aspect algorithmique dans le domaine
informatique, les graphes constituent donc une méthode de pensée qui permet de modéliser
une grande variante de problèmes complexes en les ramenant à des problèmes connus.
Ce projet a pour but de créer une application permettant de résoudre le problème
d’affectation et le problème de transport. L’utilisateur qui va bénéficier de ce service
disponible dans notre application va pouvoir trouver la solution optimale de ces deux
problèmes.
Donc notre premier objectif est d’affecter un ensemble de tâches, telle que le coût total
d’affectation soit minimal.
Notre deuxième objectif est de trouver la quantité transportée de chaque origine (ou usine)
vers les destinations (ou clients), de telle manière que le coût totale de transport soit
minimal.
Pour cette raison, dans ce travail, nous nous intéressons à la modélisation et à la résolution
de ces problèmes d’optimisations combinatoires issues de la gestion des ressources. Et pour
cela nous avons divisé notre travail en quatre parties, ou nous allons aborder en premier
temps la théorie des graphes ensuite nous allons traiter le problème d’affectation, nous
étudions aussi les programmes de transport et en fin nous allons exposer l’implémentation
des algorithmes spécifiques en nous appuyant sur les points communs qui existent dans les
problématiques et les contraintes de ces problèmes.

Projet de Fin d’Etudes Page | 6

Introduction générale

1. Tentative de définition
La recherche opérationnelle est l’ensemble des méthodes et techniques rationnelles
d’analyse et de synthèse des phénomènes d’organisation utilisable pour élaborer de
meilleures décisions ; chaque fois que l’homme, la machine, et les produits se trouvent en
relations actives.

2. Domaine d’application
L’activité de la capture des besoins consiste à identifier la plupart des cas d’utilisation et
les différents acteurs qui constituent l’environnement.

2.1. Domaine combinatoire :

 Chemin optimal dans un graphe valué :
Pour trouver le chemin le plus court/le plus long allant de A à B.
 Problème d’ordonnancement :

Pour la réalisation d’un projet consistant à accomplir des taches soumise à des contraintes
(trouver l’ordre des taches, les marges de réalisation des taches)
Les problèmes d’ordonnancement touchent tous les domaines de l’économie :
 La construction (suivi de projet).
 L’industrie (activité des ateliers en gestion de production et problèmes de logistiques).
 L’administration (emploi du temps).
 Problème de flot maximal :
Pour acheminer le plus possible de marchandises compte tenu des capacités de transport de
chaque arc dans un graphe valué.
Par exemple :
 Acheminement d’un produit depuis les centres de productions vers les centres de
distributions (réseau géographique)
 La répartition des communications téléphoniques.
 Circulation routière.
 Problème d’affectation :
Pour 25 personnes à affecter dans 25 postes, selon leurs compétences on cherche une
solution satisfaisante le plus possible de personnes.
 Problème de transport :
Pour trouver des quantités à transporter depuis (m) usines vers (n) distributeurs en
minimisant la somme des couts de transport.
Projet de Fin d’Etudes Page | 7
Introduction générale

2.2. Domaine aléatoire

 Files d’attente : Une file d'attente se crée pour chaque cas où des clients désirent
recevoir un service auprès d'un producteur. Une file d'attente peut s’appliquer à
différentes situations. (Chaînes et processus de Markov; processus de création et
destruction…).

2.3. Domaine combinatoire continu

 Programmation mathématiques linéaires : Un programme linéaire est un problème
dans lequel on est amené à maximiser (ou minimiser) une application linéaire sur un
ensemble d'équations et/ou d'inéquations linéaires, dites contraintes.
 Méthode de Simplexe : L'algorithme du simplexe est un procédé itératif qui
progresse dans un sens évolutif : il passe d'une solution de base réalisable non
optimale à une autre solution ayant une meilleure valeur d'objectif.
 Méthode de Dual : Il est plus avantageux, dans certaines circonstances,
de résoudre le problème dual. Ensuite, la solution du (PL) initial sera déduite
facilement par l'intermédiaire de la solution du dual.
 Programmation mathématiques non linéaires : La résolution de problèmes
combinatoires par des approches non linéaires est un domaine de recherche
actuellement très actif en optimisation combinatoire. Des outils numériques
performants sont à présent disponibles pour résoudre des classes particulières de
programmes non linéaires tels que les programmes quadratiques convexes et les
programmes semi définis.

Projet de Fin d’Etudes Page | 8

Chapitre I : Théorie des graphes

Chapitre I : Théorie
des graphes

Projet de Fin d’Etudes Page | 9

Chapitre I : Théorie des graphes

Introduction
La théorie des graphes est un très vaste domaine tant du point de vue des recherches
fondamentales que de celui des applications. Elle s'est alors développée dans diverses
disciplines telles que la chimie (isomères), la biologie, les sciences sociales (réseaux de
transports), gestion de projets, informatique (topologie des réseaux, complexité
algorithmique, protocoles de transferts), la physique quantique, etc.
Depuis le début du 20ème siècle, la théorie des graphes constitue une branche à part entière
des mathématiques, a connu un grand regain d'intérêt pour les informaticiens, vont plutôt
chercher à concevoir des algorithmes efficaces pour résoudre des problèmes faisant
intervenir des graphes (recherche du plus court chemin, problème d’ordonnancement,
recherche d’un arbre couvrant, ...etc.). Tout ceci forme un ensemble très vaste, dont nous
n’aborderons que quelques aspects, essentiellement de nature algorithmique (problèmes
d’affectation et de transport).

1. Vocabulaires de la théorie des graphes

1.1 Graphe
Définition I-1.
On appelle graphe = , la donnée d’un ensemble dont les éléments sont
appelés sommets et d’une partie de symétrique ( , ∈ ↔ , ∈ ) , dont
les éléments sont appelés arêtes.
En présence d’une arête = , qui peut être notée simplement , on dit que x
et y sont les extrémités de et que est incidente de , et que est un successeur ou
voisin de .
Définition I-2.
On appelle graphe orienté = , la donnée d’un ensemble dont les éléments
sont appelés sommets et d’une partie de × dont les éléments sont appelés arcs ou
arêtes.
En présence d’un arc = , qui peut être noté simplement , on dit que est
l’origine (ou extrémité initiale) et l’extrémité (terminale) de , que est sortant en
et incident en , et que est un successeur de tandis que est un prédécesseur de .
On dit aussi que et sont adjacents.

Projet de Fin d’Etudes Page | 10

Chapitre I : Théorie des graphes

Définition I-3.
Une chaıne est une séquence finie et alternée de sommets et d’arêtes, débutant et
finissant par des sommets, telle que chaque arête est incidente avec les sommets qui
l’encadre dans la séquence.
Une arête ne doit pas intervenir plusieurs fois dans la séquence contrairement à un
sommet.
Un cycle est une chaıne dont les extrémités coïncident.
Définition I-4.
Un arc est une ligne orientée qui relie deux nœuds ; et est lu dans le sens de la flèche.
Définition I-5.
Une boucle : arc partant d’un sommet allant vers lui-même.
1.2 Réseau de transport [figure 1]
Définition I-7.
Le réseau de transport est un graphe fini, sans boucle comportant une entrée (source)
et une sortie � (puits), telles que : depuis il existe un chemin vers tout autre sommet
et de tout sommet il existe un chemin vers . Tout arc = , est valué par
un entier positif nommé capacité de l’arc = , , qui présente une capacité de
transport associée à la liaison figurée par cet arc (Ex. tonnages disponibles sur des
bateaux, des camions, …)

Figure 1 : Graphe représente un réseau de transport

1.3 Graphe biparti [Figure 2]

Définition I-8.
Un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux
sous-ensembles et telle que chaque arête ait une extrémité dans et l'autre
dans .

Projet de Fin d’Etudes Page | 11

Chapitre I : Théorie des graphes

Remarque.
Un graphe biparti permet notamment de représenter une relation binaire.

Figure 2 : Exemple de graphe biparti quelconque

1.4 Problème de couplage maximum dans un graphe biparti

Définition I-9.
Un graphe biparti est un graphe non orienté , , où et sont des ensembles
disjoints de sommets, et chaque arête a une extrémité dans et l'autre dans . On appelle
couplage un ensemble d'arêtes n'ayant aucune extrémité en commun. Un couplage est
maximum s'il comporte un nombre maximum d'arêtes et il est parfait s'il recouvre tous les
sommets.
Remarque.
Ce problème peut être transformé en un problème de flot maximum. On rajoute une
source reliée aux sommets de X par des arcs de capacité 1, un puits relié aux sommets de Y
par des arcs de capacité1, on oriente toutes les arêtes de X vers Y et on leur donne une
capacité 1. Pour trouver un couplage maximum on cherche un flot maximum dans ce
graphe.
1.4. 1 Application :
Les étudiants d'une école appartiennent à différents clubs. On cherche à créer une
instance de coordination dans laquelle chaque club est représenté par une personne mais ce
représentant ne peut représenter qu'un club. Est-ce possible ?
On associe au problème un graphe biparti où est l'ensemble des étudiants, l'ensemble
des clubs, les arêtes indiquent l'appartenance d'un étudiant à un club. Il faut trouver un
couplage qui sature .

Projet de Fin d’Etudes Page | 12

Chapitre I : Théorie des graphes

2. Technologies utilisées
Les outils de programmation utilisés pour le développement de l’application sont Java et
Eclipse.

2.1 Langage java

Java est un langage de programmation orienté objet développé par Sun
Microsystems (aujourd'hui racheté par Oracle), très utilisé, notamment par un grand
nombre de programmeurs professionnels. Une de ses plus grandes forces est son excellente
portabilité .Cette portabilité du bytecode Java est assurée par la machine virtuelle Java, et
éventuellement par des bibliothèques standard incluses dans un JRE. Cette machine
virtuelle peut interpréter le bytecode ou le compiler à la volée en langage machine. La
portabilité est dépendante de la qualité de portage des JVM sur chaque OS : une fois votre
programme créé, il fonctionnera automatiquement sous plusieurs systèmes
d’exploitation tels que : Unix, Windows, Mac, Linux, etc.

Java permet de développer des applications client-serveur. Côté client, les applets sont à
l’origine de la notoriété du langage. C’est surtout côté serveur que Java s’est imposé dans
le milieu de l’entreprise grâce aux servlets, le pendant serveur des applets, et plus
récemment les JSP (JavaServer Pages) qui peuvent se substituer à PHP, ASP et ASP.NET.

Java a donné naissance à un système d'exploitation (JavaOS), à des environnements de

développement (eclipse/JDK), des machines virtuelles (MSJVM , JRE) applicatives
multiplate-forme (JVM), une déclinaison pour les périphériques mobiles/embarqués
(J2ME), une bibliothèque de conception d'interface graphique (AWT/Swing), des
applications lourdes (Jude, Oracle SQL Worksheet, etc.), des technologies web (servlets,
applets) et une déclinaison pour l'entreprise (J2EE).

2.2 Eclipse
Eclipse est un environnement de développement intégré (IDE) utilisé dans la
programmation informatique. Il contient un espace de travail de base et un système
extensible de plug-in pour personnaliser l'environnement.

Eclipse est écrit principalement en Java et son utilisation principale est pour le
développement d'applications Java, mais elle peut également être utilisée pour développer
des applications dans d'autres langages de programmation via des plug-ins, y compris Ada,

Projet de Fin d’Etudes Page | 13

Chapitre I : Théorie des graphes
ABAP, C, C ++, COBOL, D, Fortran, Haskell , JavaScript, Julia, Lasso, Lua, NATURAL,
Perl, PHP, Prolog, Python, R, Ruby , Rust, Scala….

Il peut également être utilisé pour développer des documents avec LaTeX (via un plug-in
TeXlipse) et des paquets pour le logiciel Mathematica.

Les environnements de développement comprennent les outils de développement Java

(JDT) d'Eclipse pour Java et Scala, Eclipse CDT pour C / C ++ et Eclipse PDT pour PHP,
entre autres.

Conclusion
La théorie des graphes constitue aujourd’hui un corpus de connaissances très importants. Les
graphes permettent de modéliser et de résoudre de nombreux problèmes dans de nombreuses
situations couvrant des modèles mathématiques de l’optimisation et grâce à l’informatique
ces problèmes seront grandement simplifiés.

Projet de Fin d’Etudes Page | 14

Chapitre II : Problème d’affectation

Chapitre II :
Problème
d’affectation

Projet de Fin d’Etudes Page | 15

Chapitre II : Problème d’affectation

Introduction
Le problème d’affectation appartient à une catégorie spéciale de programmes linéaires dans
laquelle la fonction économique consiste à affecter un nombre de sources (ou origines) au
même nombre de destinations à un coût minimum ou à un profit maximum. Ainsi, chaque
source est associée à une et une seule destination.

Cette spécificité implique deux particularités à ce programme linéaire :

 La fonction économique correspond à une matrice carrée.

 La solution optimale est telle qu’il y a une seule affectation dans chaque colonne et
chaque ligne.
Le problème d’affectation consiste à trouver les liens entre les éléments de deux ensembles
distincts, de manière à minimiser un coût et à respecter les contraintes d’unicité de lien.

1. Modélisation
Définition II-1:

La modélisation mathématique est définie comme la construction de modèles

mathématiques à partir de données expérimentales. Elle permet d’interpréter les différents
paramètres d’un problème donné et de les traduire dans un langage mathématique que
l’on peut manipuler et auquel on peut appliquer des outils et des méthodes de résolution.
Dans ce chapitre, nous allons modéliser le problème par le modèle le plus approprié
auquel on appliquera par la suite la méthode de Hongrois.
2. Problème d’affectation
On considère tâches et agents.
Pour tout couple , = ,, ; = ,, l’affectation de la tâche à entraîne un
coût de réalisation noté � ( � ≥ )Chaque tâche doit être réalisée exactement une fois et
chaque agent peut réaliser une et une seule tâche.
Le problème consiste à affecter les tâches aux agents, de façon à minimiser le coût total
de réalisation et en respectant les contraintes de réalisation des tâches et de disponibilité
des agents.
À tout couple tâche/agent , , on associe une variable d’affectation où :
′
� é
={

Le problème d’affectation peut être représenté sous forme d’un graphe biparti [figure 3]
de la manière suivante :

Projet de Fin d’Etudes Page | 16

Chapitre II : Problème d’affectation

Figure 3: Représentation du problème sous forme d’un graphe

2.1 Formulation de problème

On peut donc modéliser le problème d’affectation sous la forme de programme linéaire

standard :

� � =∑ ∑ � �
= =

∑ = = ,,
=
�
∑ = = ,,
=
∈{ , } = ,, = ,,
{

Variables :

� : Matrice des coûts d’affectation.

Contraintes :

 La première contrainte donne le nombre d’agents réalisant la tâche qui vaut à 1 pour
chaque = , ,
 La deuxième contrainte donne le nombre de tâches réalisées par l’agent qui vaut à 1
pour chaque = ,,

Projet de Fin d’Etudes Page | 17

Chapitre II : Problème d’affectation
Les contraintes de ce problème se retrouvent dans de nombreuses applications mettant en
jeu des problèmes d’allocation de ressources. Elles sont généralement appelées "contraintes
d’affectation".

But :

Le problème consiste à affecter les tâches aux agents, de façon à minimiser le coût total de
∑= ∑=
réalisation et en respectant les contraintes de réalisation des tâches et de

disponibilité des agents.

Remarques.
i. Le problème d’affectation est dit non standard, si on a agents et tâches avec
≠ . Mais on peut transformer ce problème non standard à un problème standard de la
manière suivante :
 Si > alors nous créons − agents fictifs.
 Si > alors nous créons − tâches fictives.

Le coût d’affectation de ces élément fictive est égale à (ou > ).

ii. Le problème standard d’affectation peut être résolu comme un problème de transport
ou les = = et les représentent les coûts unitaires de transport.
iii. Le problème d’affectation peut être défini comme un problème de maximisation.

=∑ ∑
= =

 Le problème consiste à affecter les taches aux agents de telle sorte que la
rentabilité totale soit maximale, et sous les mêmes contraintes du problème de
minimisation.
3. Résolution par la méthode Hongroise (Kuhn, Egervary, König)
3.1. Principe de la Méthode Hongroise
L'algorithme hongrois ou méthode hongroise parfois appelé aussi algorithme de Kuhn-
Munkres est un algorithme d'optimisation combinatoire, qui résout le problème
d'affectation en temps polynomial. Il a été proposé en 1955 par le mathématicien américain
Harold Kuhn, qui l'a baptisé « méthode hongroise » parce qu'il s'appuyait sur des travaux
antérieurs de deux mathématiciens hongrois : Dénes Kőnig et Jenő Egerváry.
James Munkres a revu l'algorithme en 1957 et a prouvé qu'il s'exécutait en temps
polynomial.

Projet de Fin d’Etudes Page | 18

Chapitre II : Problème d’affectation
Cet algorithme, sert à résoudre les problèmes d'affectation, problèmes qu'on peut résumer
de la manière suivante : considérant une matrice (appelée tableau de coûts), il faut choisir
un seul élément par ligne et par colonne de façon à rendre la somme optimale (minimal ou
maximal).
3.2. Algorithme Hongrois
Étape 1: Création de la matrice des coûts à partir du problème.
Si aucun des lignes n'est égal au nombre de colonnes et vice versa, une rangée fictive doit
être ajoutée. Le coût d'affectation pour les cellules fictives est zéro.
Étape 2: Réduction de la matrice des coûts.
1. Soustrayez le plus petit élément dans chaque ligne.
2. Soustrayez le plus petit élément dans chaque colonne.
3. Chaque ligne et colonne ont maintenant au moins une valeur zéro.
Étape 3: Réalisation d’une affectation dans la matrice des coûts.
1. Pour chaque ligne et / ou colonne, encadrer la valeur zéro pour dénoter une affectation.
2. Pour chaque valeur zéro encadré qui devient affecté, barrer tous autres zéros dans la
même ligne et / ou colonne.
3. Répétez 1 et 2 jusqu'à ce que tous les zéros en lignes / colonnes soient affectées.
Étape 4: Exécution d’un test d’optimalité.
1. Si le nombre de cellules d'affectation est égal au nombre de lignes / colonnes, c'est une
solution optimale, le coût total associé à cette solution est obtenu en sommant les valeurs
des coûts d'origines dans les cellules occupées.
2. Si aucune solution optimale n'est trouvée, passez à l'étape 5.
Étape 5: Création des zéros supplémentaires.
Rayez les lignes horizontales et verticales pour couvrir tous les zéros du coût obtenu à partir
de l'étape 3 en utilisant la procédure suivante.
1. Marquez (*) les lignes n’ayant pas de zéros encadrés.
2. Marquez (*) les colonnes ayant un zéro barré sur une ligne déjà marquée.
3. Marquez (*) les lignes ayant un zéro encadré dans une colonne marquée.
4. Rayez chaque colonne marquée et chaque ligne non marquée.
Si le nombre de ligne rayée est égal au format de la matrice, la solution actuelle est la
solution optimale, sinon passez à l'étape 6.

Projet de Fin d’Etudes Page | 19

Chapitre II : Problème d’affectation

Étape 6: Amélioration de la nouvelle matrice des coûts.

1. Choisissez le plus petit élément du reste des cellules non rayées.
2. Soustrayez- ce plus petit élément de chaque élément des cellules non rayées.
3. Ajoutez-le à chaque élément des cellules rayées deux fois.
Les éléments en cellules rayées une seule fois restent inchangés.
Étape 7: Répétition des étapes.
Répétez l'étape 3 à 6 jusqu'à obtention d'une solution optimale.

Figure 4 : Organigramme de l’algorithme Hongrois

Projet de Fin d’Etudes Page | 20

Chapitre II : Problème d’affectation

3.3 Application de l’algorithme Hongrois : Exemple

Etape 1 : Matrice des coûts originaux :
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6
Tâche 1
31 42 93 83 2 58

Tâche 2
24 49 40 38 83 57

Tâche 3
73 35 77 63 22 25

Tâche 4
37 55 97 24 80 41

Tâche 5
47 20 96 5 75 12

Tâche 6
84 40 50 10 9 82

Tableau 1 : Matrice des coûts originaux

Etape 2 : Réduction-lignes

L’opération de réduction-lignes consiste à retrancher de chaque coût d’une ligne la valeur

minimale de la ligne. Le tableau résultant est donné ci-dessous.

Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
29 40 91 81 0 56 (-2)

Tâche 2
0 25 16 14 59 33 (-24)

Tâche 3
51 13 55 41 0 3 (-22)

Tâche 4
13 31 73 0 56 17 (-24)

Tâche 5
42 15 91 0 70 7 (-5)

Tâche 6
75 31 41 1 0 73 (-9)

Tableau 2 : Réduction des lignes

Projet de Fin d’Etudes Page | 21

Chapitre II : Problème d’affectation
Etape 2 : Réduction-colonnes
L’opération de réduction-colonnes consiste à retrancher de chaque coût d’une colonne la
valeur minimale de la colonne. Le tableau résultant est donné ci-dessous.
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
29 27 75 81 0 53

Tâche 2
0 12 0 14 59 30

Tâche 3
51 0 39 41 0 0

Tâche 4
13 18 57 0 56 14

Tâche 5
42 2 75 0 70 4

Tâche 6
75 18 25 1 0 70

0 (-13) (-16) 0 0 (-3)

Tableau 3 : Réduction des colonnes

Etape 3 : Affectation de l’unique zéro à chaque ligne/colonne

Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
29 27 75 81 0 53

Tâche 2
0 12 Ø 14 59 30

Tâche 3
51 0 39 41 Ø Ø

Tâche 4
13 18 57 0 56 14

Tâche 5
42 2 75 Ø 70 4

Tâche 6
75 18 25 1 Ø 70

Tableau 4 : Dénotation de l’unique affectation

Projet de Fin d’Etudes Page | 22

Chapitre II : Problème d’affectation
Etape 4 : Effectuation du test d’optimalité
D’après le couplage obtenu par le graphe biparti, il y a deux sommets non-saturés, alors
l’affectation obtenue n’est pas optimale.

Figure 5 : Représentation de l’affectation obtenue par un couplage maximal.

Etape 5 : Création des zéros supplémentaires (Procédure de marquage)
On marque (*) toute ligne ne contenant aucun zéro encadré.
On marque (*) toute colonne ayant un zéro barré sur une ligne marquée.
On marque (*) toute ligne ayant un zéro encadré dans une colonne marquée.
* *
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
29 27 75 81 0 53

Tâche 2
0 12 Ø 14 59 30

Tâche 3
51 0 39 41 Ø Ø

Tâche 4 *
13 18 57 0 56 14

Tâche 5 *
42 2 75 Ø 70 4

Tâche 6 *
75 18 25 1 Ø 70

Tableau 5 : Procédure de marquage

Projet de Fin d’Etudes Page | 23

Chapitre II : Problème d’affectation
Etape 6:Amélioration de la nouvelle matrice des couts
Le plus petit nombre découvert est 2 (coloré en orange).
* *
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
29 27 75 81 0 53

Tâche 2
0 12 0 14 59 30

Tâche 3
51 0 39 41 0 0

Tâche 4 *
13 18 57 0 56 14

Tâche 5 *
42 2 75 0 70 4

Tâche 6 *
75 18 25 1 0 70

Tableau 6 : Amélioration de la nouvelle matrice [le plus petit nb découvert]

Etape 6: Amélioration de la nouvelle matrice des coûts
Nous soustrayons (2) de tous les éléments découverts et l'ajoutons à tous les éléments qui
sont couverts deux fois:
* *
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
27 25 73 81 0 51

Tâche 2
0 12 0 16 61 30

Tâche 3
51 0 39 43 2 0

Tâche 4 *
11 16 55 0 56 12

Tâche 5 *
40 0 73 0 70 2

Tâche 6 *
73 16 23 1 0 68

Tableau 7 : Amélioration de la nouvelle matrice [éléments couverts 2 fois]

Projet de Fin d’Etudes Page | 24

Chapitre II : Problème d’affectation
Etape 7 : Répétition des étapes 3 à 6
Une affectation complète n’est pas encore faite, alors on passe à l’étape 5 :
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
27 25 73 81 0 51

Tâche 2
0 12 Ø 16 61 30

Tâche 3
51 Ø 39 43 2 0

Tâche 4
11 16 55 0 56 12

Tâche 5
40 0 73 Ø 70 2

Tâche 6
73 16 23 1 Ø 68

Tableau 8 : Affectation non complète [répétition des étapes 3 à 6]

Etape 5-6: Création des zéros supplémentaires (Procédure de marquage)
Après procédure de marquage, le plus petit nombre découvert est 11.
* *
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
27 25 73 81 0 51

Tâche 2
0 12 0 16 61 30

Tâche 3
51 Ø 39 43 2 0

Tâche 4 *
11 16 55 0 56 12

Tâche 5
40 0 73 0 70 2

Tâche 6 *
73 16 23 1 0 68

Tableau 9 : Procédure de marquage et Détermination du plus petit élément découvert

Projet de Fin d’Etudes Page | 25

Chapitre II : Problème d’affectation
Etape 6: Amélioration de la nouvelle matrice des couts
Le nombre de lignes marquées est inférieur à 6. Le plus petit nombre découvert est 11. Nous
soustrayons ce nombre de tous les éléments découverts et l'ajoutons à tous les éléments qui
sont couverts deux fois:
* *
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
16 14 62 81 0 40

Tâche 2
0 12 0 27 72 30

Tâche 3
51 0 39 54 13 0

Tâche 4 *
0 5 44 0 56 1

Tâche 5
40 0 73 11 81 2

Tâche 6 *
62 5 12 1 0 57

Tableau 10 : Amélioration de la nouvelle matrice [éléments couverts 2 fois]

Etape 7 : Répétition des étapes 3 à 6
Une affectation complète n’est pas encore faite, alors on passe à l’étape 5 :
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
16 14 62 81 0 40

Tâche 2
Ø 12 0 27 72 30

Tâche 3
51 Ø 39 54 13 0

Tâche 4
Ø 5 44 0 56 1

Tâche 5
40 0 73 11 81 2

Tâche 6
62 5 12 1 Ø 57

Tableau 11 : Affectation non complète [répétition des étapes 3 à 6]

Projet de Fin d’Etudes Page | 26

Chapitre II : Problème d’affectation
Etape 5-6: Création des zéros supplémentaires (Procédure de marquage)
Après procédure de marquage, le plus petit nombre découvert est 1.
*
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
16 14 62 81 0 40

Tâche 2
0 12 0 27 72 30

Tâche 3
51 0 39 54 13 0

Tâche 4
0 5 44 0 56 1

Tâche 5
40 0 73 11 81 2

Tâche 6 *
62 5 12 1 0 57

Tableau 12 : Procédure de marquage et Détermination du plus petit élément découvert

Etape 6 : Amélioration de la nouvelle matrice des couts
Le nombre de lignes est inférieur à 6. Nous soustrayons 1 de tous les éléments découverts et
l'ajoutons à tous les éléments qui sont couverts deux fois:
*
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1 *
15 13 61 80 0 39

Tâche 2
0 12 0 27 73 30

Tâche 3
51 0 39 54 14 0

Tâche 4
0 5 44 0 57 1

Tâche 5
40 0 73 11 82 2

Tâche 6 *
61 4 11 0 0 56

Tableau 13 : Amélioration de la nouvelle matrice [éléments couverts 2 fois]

Projet de Fin d’Etudes Page | 27

Chapitre II : Problème d’affectation
Etape 7 : Répétition des étapes 3 à 6
Une affectation complète est bien faite, alors : chaque agent possède une affectation
(tache), donc la solution est optimale.
Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
15 13 61 80 0 39

Tâche 2
0 12 0 27 73 30

Tâche 3
51 0 39 54 14 0

Tâche 4
0 5 44 0 57 1

Tâche 5
40 0 73 11 82 2

Tâche 6
61 4 11 0 0 56

Tableau 14 : Affectation complète

Fin de L’algorithme : La valeur optimale est égale à 134.

Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Agent 6

Tâche 1
31 42 93 83 2 58

Tâche 2
24 49 40 38 83 57

Tâche 3
73 35 77 63 22 25

Tâche 4
37 55 97 24 80 41

Tâche 5
47 20 96 5 75 12

Tâche 6
84 40 50 10 9 82

Tableau 15 : Affectation des valeurs constituant la solution optimale

û = + + + + + =

Projet de Fin d’Etudes Page | 28

Chapitre II : Problème d’affectation
On remarque que le couplage obtenu par le graphe biparti est parfait, tous les sommets sont
saturés, donc l’affectation est totale et optimale.

Figure 6 : Représentation de la solution optimale

Conclusion
La méthode hongroise est un algorithme d’optimisation combinatoire, une des méthodes
privilégiées pour résoudre les problèmes d’affectation en temps polynomial, efficace et très
rapide par rapport à la méthode du simplexe qui conduit à des tableaux très grands d’ordre
(n) et la solution est fortement dégénérée : contient un nombre de variables soit (n).

Projet de Fin d’Etudes Page | 29

Chapitre III : Programmes de transport

Chapitre III :
Programmes de
transport

Projet de Fin d’Etudes Page | 30

Chapitre III : Programmes de transport

Introduction :
C’est en 1941 que Frank L. Hitchcock a formulé pour la première fois le problème de
transport, qui consiste à minimiser le coût de transport total d’un plan d’expédition. Le
problème de transport « classique » est en fait un cas particulier d’un problème de flux de
réseaux (minimiser à la fois la distance totale et le coût de transport)

Le problème de transport est un problème linéaire qui peut être représenté sous forme d’un
graphe et qu’on peut le résoudre en utilisant les différentes méthodes de résolution des
problèmes linéaires.

1. Présentation du problème de transport

On peut décrire un problème de transport de façon suivante : Une quantité donnée d’un
produit uniforme est disponible à chacune des origines (par exemple des dépôts). Il s’agit d’en
envoyer des quantités spécifiées à chacune des destinations (par exemple des points de vent).
On connait le coût de transport d’une unité de l’une des origines vers l’une des destinations.
En supposant qu’il est possible d’expédier des produits depuis n’importe quelle origine vers
n’importe quelle destination, il s’agit de déterminer le coût de transport minimum des origines
vers les points de destination.
2. Formulation du problème
 Par une matrice des coûts :

Tableau 16 : Matrice des débits

Projet de Fin d’Etudes Page | 31

Chapitre III : Programmes de transport

 Par un graphe biparti :

Figure 7 : Représentation du problème sous forme de graphe biparti

 Par un programme linéaire :

= ∑ ∑
= =

∑ =∑ ∀ = ,, ∀ = ,,
= =

∑ = = ,,
� =

∑ = = ,,
=

� ∀ = ,, ; � ∀ = ,,
{ � ∀ = ,, ∀ = ,,

Projet de Fin d’Etudes Page | 32

Chapitre III : Programmes de transport

But:
Le problème consiste à déterminer les quantités à transporter de façon que le coût total
de transport ∑ = ∑ = soit minimal.
Variables :
: La quantité à transporter de vers ∀ , ∈ { ,… , } × { ,… , }.
: Le coût unitaire de transporter de vers ∀ , ∈ { ,… , } × { ,… , }.
Contraintes :
 la quantité totale de marchandises partant de est égale à la disponibilité
∑ = � = ; ∀ = ,, .
 la quantité totale de marchandises reçue par est égale à la demande
∑= � = ; ∀ = ,, .
Remarque:
1. Pour résoudre le problème, on doit toujours vérifier que le total des quantités
disponibles correspond au total des quantités demandées, c’est-à-dire que l’offre globale soit
égale à la demande globale :
∑= =∑ = ∀ = ,, �� ∀ = , ,

On dit que le problème est équilibré.

2. Si ce n'est pas le cas, par exemple si :
 ∑= >∑ = ∀ = ,, �� ∀ = , , , l’offre est supérieure à la

demande [excès des disponibilités], il faut créer une destination fictive avec un offre
et attribuer un coût énorme ou nulle pour qu’aucune demande réelle ne puisse
satisfaire cette destination fictive.
 ∑= <∑ = ∀ = ,, �� ∀ = , , , la demande est supérieure à

l’offre [excès des demandes], il faut créer une origine fictive avec une demande et
attribuer un coût énorme ou nulle pour qu’aucun offre réel ne puisse satisfaire cette
origine fictive.
3. Résolution du problème
La résolution du problème par la méthode de Coin Nord-Ouest
La résolution du problème passe par deux étapes essentielles :
 La première étape : Méthode de Coin Nord-Ouest
C’est de trouvé une solution de base initiale.
 La deuxième étape : Méthode de Stepping Stone

Projet de Fin d’Etudes Page | 33

Chapitre III : Programmes de transport
C’est de trouvé la solution optimale à partir la solution de base.
La résolution du problème par la méthode de Balas Hammer
La résolution du problème passe par deux étapes essentielles :
 La première étape : Méthode de Balas Hammer
C’est de trouvé une solution de base initiale.
 La deuxième étape : Méthode de Stepping Stone
C’est de trouvé la solution optimale à partir la solution de base.
Remarque :
La procédure de Balas Hammer généralement très efficace, conduit à l’obtention d’un coût
total assez proche de l’optimum.
Définition III-1:
On appelle solution de base une solution vérifiant les contraintes du problème et qui
comporte exactement (m-1) (n-1) flux nuls.
Remarque :
En général, une solution de base comporte +  cases de base, où dénote le
nombre de lignes (origines du tableau), et le nombre de colonnes (destinations).
On peut schématiser la résolution du problème de transport comme suite :
3.1. La résolution du problème par la méthode de Coin Nord-Ouest
3.1.1. La première étape : Méthode de Coin Nord-Ouest
Définition III-2 :
C’est une heuristique qui est appliquée à la programmation linéaire, c’est la méthode
la plus rapide et la plus simple pour déterminé une solution de base car elle ne fait pas
entré les coûts de transport c’est à cette raisons là que généralement la solution
obtenue par cette méthode est loin de la solution optimale.
Définition III-3:
En optimisation combinatoire, une heuristique est un algorithme approché qui permet
d’identifier en temps polynomial au moins une solution réalisable rapide, pas
obligatoirement optimale. L’usage d’une heuristique est efficace pour calculer une
solution approchée d’un problème et ainsi accélérer le processus de résolution exacte.
Remarque :
Les heuristiques peuvent être classées en deux catégories :
 Méthodes constructives qui génèrent des solutions à partir d’une solution
initiale en essayant d’en ajouter petit à petit des éléments jusqu’à ce qu’une
solution complète soit obtenue.
Projet de Fin d’Etudes Page | 34
Chapitre III : Programmes de transport
 Méthodes de fouilles locales qui démarrent avec une solution initialement
complète (probablement moins intéressante), et de manière répétitive essaie
d’améliorer cette solution en explorant son voisinage.
3.1.2. Règles de la méthode Coin Nord-Ouest
Lors de chaque étape, nous attribuons à la case la plus nord à l’ouest de la matrice
des couts la valeur maximale afin de saturer soit la ligne soit la colonne ;
puis nous nous déplaçons d’une case vers la droite ou vers le bas.
L’idée de la méthode du Coin Nord-ouest est donc de remplir au maximum la case
de la matrice des couts en haut à gauche, puis compléter sur la ligne ou la colonne de
façon à atteindre l’offre ou la demande.
3.1.3. Algorithme de la méthode Coin Nord-Ouest
1. Amorcer la méthode avec la case située dans le coin supérieur gauche du tableau de
transport.
2. Attribuer le plus d'unités possible à la case courante.
3. Aller à une case adjacente à la case courante, en se déplaçant soit vers la
droite, soit vers le bas. Revenir à l'étape 2.
La méthode s'arrête une fois effectuée l'attribution à la case située dans le coin inférieur
droit.
3.1.4. Application
 exemple d’illustration
Une entreprise possède trois usines différentes et fournit trois clients.
On doit acheminer vers les clients le produit fabriqué.
Le cout du trajet pour expédier une unité de produit de chacune des industries vers
chacun des clients est donné dans le tableau suivant :

Tableau 17 : Plan de transport

Projet de Fin d’Etudes Page | 35

Chapitre III : Programmes de transport

a. Solution de base admissible initiale :

Le tableau suivant décrit la solution de base rencontrée lors de la résolution de ce
problème : la solution initiale découlant de la méthode de Coin Nord -Ouest.

Tableau 18 : Solution de base admissible

b. Cout total de cette solution :
Et son coût total est égal à 5750 DH
= ∗ + ∗ + ∗ + ∗ + ∗
=
c. Détermination de la solution par un graphe biparti :

Figure 8 : Représentation de la solution de base admissible sous forme d’un graphe biparti

3.2.1. La deuxième étape : Méthode de Stepping Stone

Définition III-4:
L’algorithme de Stepping Stone est une métaheuristique qui tente itérativement
d’améliorer la solution de base vers une solution optimale.
Remarque :
On peut appliquer l’algorithme à n’importe quelle solution de base.

Projet de Fin d’Etudes Page | 36

Chapitre III : Programmes de transport

Définition III-5:
Face aux difficultés rencontrées par les heuristiques pour avoir une solution
réalisable de bonne qualité pour des problèmes d’optimisation difficiles, les
métaheuristiques ont fait leur apparition. Ces algorithmes sont plus complets et
complexes qu’une simple heuristique, et généralement utilisent des processus
aléatoires et itératifs afin d’améliorer vers une solution optimale de très bonne
qualité.
3.2.2. Déroulement de l’algorithme de Stepping Stone
L’algorithme de Stepping Stone consiste à modifier la solution de base vers une
solution meilleure, donc à rendre non vide une case vide dans le tableau des
quantités.

Figure 9 : Organigramme de l’algorithme [Méthode Stepping Stone]

Définition III-6:
On appelle coût marginal la quantité qui s’ajoute au coût globale lorsqu’on veut
transporter une unité sur un arc de flux nul:
� = − − , avec − est la tension de l’arc , .
: S’appelle le potentiel du sommet de l’arc ,
3.2.3. Algorithme de la Méthode de Stepping Stone
1. Déterminer une solution de base.
2. Calculer les couts marginaux � = − − .

 Si tous les coûts marginaux sont positifs ou nuls � ≥

Projet de Fin d’Etudes Page | 37

Chapitre III : Programmes de transport
 Alors Fin : la solution est optimale.

 Sinon passer à (3).

3. Pour tous les coûts marginaux négatifs � < .
 Alors chercher la chaine de substitution
 Déterminer la quantité maximale qui peut être déplacée.
 Et passer à (4).
 Le gain correspondant est égal au produit de cette quantité par le coût marginale.
4. Retenir la substitution qui réalise la plus grande diminution du coût de transport :
 Effectuer la substitution.
 Et revenir à (2).
a) Détermination des potentiels [*]:
Pour calculer les potentiels on utilisera la relation suivante : � = en d’autre

terme il faut que = − avec le potentiel au sommet d’origine et le

potentiel au sommet de destination pour tout arc , :

 = + pour calculer le potentiel d’une destination.
 = − pour calculer le potentiel d’une origine.
 Itération 1 :
o Calcul des potentiels :
Le graphe biparti représente le calcul des potentiels da chaque sommet (origine et
destination) en respectant les règles de détermination des potentiels [*].

Figure 10 : Graphe de potentiel

Projet de Fin d’Etudes Page | 38

Chapitre III : Programmes de transport

o Calcul des coûts marginaux :

Apres le calcul des potentiels on passe au calcul des coûts marginaux des cases vides
dans le tableau. Donc on cherche s’il existe une nouvelle liaison qui permettra
d’améliorer la solution précédente.

Tableau 19 : Coûts marginaux

Puisque il existe un coût marginal qui est strictement négatif ; donc la solution n’est
pas optimale et on peut améliorer grâce à la liaison � , � ; alors on ajoute celle
liaison dans le graphe.
o Chaine de substitution :

Figure 11 : Graphe de liaison ajoutée Figure 12: Graphe de chaine de substitution

Le tableau suivant illustre le cycle de changement des coûts marginaux de différentes

cases. Pour chaque chemin tracé, on affecte un signe positif et un signe négatif de
manière alternative, en commençant par un signe positif à la cellule de départ

Projet de Fin d’Etudes Page | 39

Chapitre III : Programmes de transport

On calcule l’indice d’amélioration ou bien d’évaluation en ajoutant d' abord le

chiffre du coût unitaire trouvé dans chaque cellule contenant un signe plus + et

soustraire le coût unitaire dans chaque cellule contenant un signe moins − .

Tableau 20 : Cycle de changement

D 'ou q représente la quantité maximal qu’on peut transporter sur la liaison ajouté.
q = min (40, 50) = 40, donc après la modification on obtient la nouvelle solution
représentée dans le tableau suivant :

Tableau 21 : Nouvelle solution [Itération 1]

o Coût de transport :
Le cout de transport de la nouvelle solution est :

= ∗ + ∗ + ∗ + ∗ + ∗

= < =

 Itération 2 :
o Calcul des potentiels :
Le graphe biparti représente le calcul des potentiels da chaque sommet (origine et
destination) en respectant les règles de détermination des potentiels [*].

Projet de Fin d’Etudes Page | 40

Chapitre III : Programmes de transport

Figure 13 : Graphe de potentiel

o Calcul des coûts marginaux :

Apres le calcul des potentiels on passe au calcul des coûts marginaux des cases vides
dans le tableau. On cherche s’il existe une nouvelle liaison qui permettra d’améliorer
la solution précédente.

Tableau 22 : Coûts marginaux

Puisque les coûts marginaux ne sont pas tous positifs ; donc la solution précédente
n’est pas optimale et on peut améliorer grâce à la liaison � , � � � ,�
puisque les deux valeurs sont égaux; alors on ajoute la liaison � , � dans le
graphe.
Remarque :
Cas où il y a plus de deux coûts marginaux négatifs, alors on choisit le coût
marginal le plus négatif.
o Chaine de substitution :

Projet de Fin d’Etudes Page | 41

Chapitre III : Programmes de transport

Figure 14 : graphe de liaison ajoutée Figure 15 : graphe de chaine de substitution

Le tableau suivant illustre le cycle de changement des coûts marginaux de différentes

cases. Pour chaque chemin tracé

Tableau 23 : Cycle de changement

D 'ou q représente la quantité maximal qu’on peut transporter sur la liaison ajouté.
q = min (200, 100) = 100, donc après la modification on obtient la nouvelle solution
représentée dans le tableau suivant :

Tableau 24 : Nouvelle solution [Itération 2]

Projet de Fin d’Etudes Page | 42

Chapitre III : Programmes de transport

o Coût de transport :
Le cout de transport de la nouvelle solution est :
= ∗ + ∗ + ∗ + ∗ + ∗
= < = < =
 Itération 3 :
o Calcul des potentiels :
Le graphe biparti représente le calcul des potentiels da chaque sommet (origine et
destination) en respectant les règles de détermination des potentiels [*].

Figure 16 : Graphe de potentiel

o Calcul des coûts marginaux :
Apres le calcul des potentiels on passe au calcul des coûts marginaux des cases vides
dans le tableau. On cherche s’il existe une nouvelle liaison qui permettra d’améliorer
la solution précédente.

Tableau 25 : Coûts marginaux

Projet de Fin d’Etudes Page | 43

Chapitre III : Programmes de transport
Puisque les coûts marginaux ne sont pas tous positifs ; donc la solution précédente
n’est pas optimale et on peut améliorer grâce à la liaison � , � ; alors on ajoute
cette liaison dans le graphe.
Remarque :
Cas où il y a plus de deux coûts marginaux négatifs, alors on choisit le coût marginal
le plus négatif.
o Chaine de substitution :

Figure 17 : graphe de liaison ajoutée Figure 18 : graphe de chaine de substitution

Le tableau suivant illustre le cycle de changement des coûts marginaux de différentes
cases. Pour chaque chemin tracé

Tableau 26 : Cycle de changement

La quantité maximale qu’on peut transporter sur la liaison ajouté est :

= , =

Projet de Fin d’Etudes Page | 44

Chapitre III : Programmes de transport

Tableau 27 : Nouvelle solution [Itération 3]

o Coût de transport :
Le cout de transport de la nouvelle solution est :

= ∗ + ∗ + ∗ + ∗ + ∗

= < = < = < =

 Itération 4 :
o Calcul des potentiels :
Le graphe biparti représente le calcul des potentiels da chaque sommet (origine et
destination) en respectant les règles de détermination des potentiels [*].

Figure 19 : Graphe de potentiel

o Calcul des coûts marginaux :

Apres le calcul des potentiels on passe au calcul des coûts marginaux des cases vides
dans le tableau. On cherche s’il existe une nouvelle liaison qui permettra d’améliorer
la solution précédente.

Projet de Fin d’Etudes Page | 45

Chapitre III : Programmes de transport

Tableau 28 : Coûts marginaux

Tous les coûts marginaux sont positifs, donc la solution précédente est optimale et
on s’arrête.
 Donc la solution optimale est :

Tableau 29 : Solution optimale

 D’un coût égal à : =

3.2. Obtention d’une solution de base par la méthode de Balas-Hammer

Définition III-7:
La méthode Balas Hammer est basée sur le calcul des regrets. Le regret associé à une
ligne ou à une colonne est la différence entre le coût minimum et le coût immédiatement
supérieur dans cette ligne ou dans cette colonne. C’est une mesure de la priorité à
accorder aux transports de cette ligne ou de cette colonne, car un regret important
correspond à une pénalisation importante si on n’utilise pas la route de coût minimum.
Cette méthode, appelée aussi méthode de la différence maximale, fera intervenir les
coûts unitaires de transport et sera donc, en général, assez proche de l’optimum.

Projet de Fin d’Etudes Page | 46

Chapitre III : Programmes de transport
3.2.1. Principe de la méthode de Balas Hammer
D’abord, on calcule pour chaque rangée, ligne ou colonne, la différence entre le coût le
plus petit avec celui qui lui est immédiatement supérieur.
Ensuite on affecte à la relation de coût le plus petit correspondant à la rangée présentant
la différence maximale la quantité la plus élevée possible. Ce qui sature une ligne ou
une colonne.
Et on reprendre le processus jusqu'à ce que toutes les rangées soient saturées.

3.2.2. Algorithme de la méthode de Balas Hammer

∆ ligne : différence entre le coût mini et celui immédiatement supérieur sur une ligne.
∆ colonne : différence entre le coût mini et celui immédiatement supérieur sur une
colonne.
1. Calculer les différences ∆ ligne et ∆ colonne pour chaque ligne et colonnes.
2. Sélectionner la ligne ou la colonne ayant la ∆ ligne ou ∆ colonne maximale.
3. Choisir dans cette ligne ou colonne le coût le plus faible.
4. Attribuer à la relation ou case , correspondante le maximum possible de
matière transportable de façon à saturer soit la destination soit la disponibilité. Calculer
la quantité résiduelle soit demande soit en disponibilité
5. Eliminer la ligne ou la colonne ayant disponibilité ou demande satisfaite
SI ( le nombre de lignes ou colonnes > = 2 )
 retour en 2.
SINON affecter les quantités restantes aux liaisons
 FIN
3.2.3. Représentation graphique
On peut représenter le schéma de départ par un graphe biparti ou on a associe chaque
trajet par son coût unitaire.

Figure 20 : Représentation du problème sous forme de graphe biparti

Projet de Fin d’Etudes Page | 47

Chapitre III : Programmes de transport
3.2.4. Application de l’algorithme de Balas-Hammer
Reprenons l’exemple précédant, et cherchons une solution de base par l’algorithme
de Balas-Hammer.
Pour chaque rangée (ligne ou colonne) du tableau des coûts, on déterminera l’élément
le plus petit et celui qui lui est immédiatement supérieur et on calculera leur différence
é ∆

Tableau 30 : Calcul de ∆
Dans la rangée correspondant à la différence maximale (ici la ligne � ) on remplira
la case contenant le plus petit élément (ici la case � ) avec le minimum de l’offre de
la ligne et de la demande de la colonne.
Puis on recommencera le processus autant de fois que nécessaire en supprimant à
chaque fois l’origine dont l’offre est entièrement utilisée et/ou la destination dont la
demande est complètement satisfaite.
On prend le plus grand delta ∆ (ligne et colonne), c’est en � qui est égale 6.
On sature avec le plus petit coût qui est � = 5 , on met 150 dans � .

Tableau 31 : Sélection de ∆ maximale

Projet de Fin d’Etudes Page | 48

Chapitre III : Programmes de transport
L’offre est comblée, donc l’origine 3 ne peut plus approvisionner c’est fini on barre
cette ligne. Et on recalcule les deltas.

Tableau 32 : Saturation disponibilité 3

On prend le plus grand delta ∆ (ligne et colonne), c’est en qui est égale 7.
On sature avec le plus petit coût qui est � = , on met le reste qui est 90
dans � .
La demande est saturée, c’est fini on barre cette colonne, et on recalcule les deltas.

Tableau 33 : Saturation destination 1

On prend le plus grand delta ∆ (ligne et colonne), c’est en qui est égale 6.
On sature avec le plus petit coût qui est � = 8 , on met 100 dans � .
Et il ne reste plus qu’à saturer la ligne et cela revient à mettre 10 dans �
Et on recalcule les deltas.

Projet de Fin d’Etudes Page | 49

Chapitre III : Programmes de transport

Tableau 34 : Saturation disponibilité 1

On prend le plus grand delta ∆ (ligne et colonne), c’est en � qui est égale 5.
On sature avec le plus petit coût qui est � = , on met 150 dans � .

Tableau 35 : Saturation à la fois disponibilité 2 et destination 2

L’offre est comblée, et voilà c’est fini.

En fin la solution de base est représentée dans le tableau [Tableau 36 ] : et D’un coût
égal à :
= ∗ + ∗ + ∗ + ∗ + ∗
=

Projet de Fin d’Etudes Page | 50

Chapitre III : Programmes de transport

Tableau 36 : Solution de base admissible

Test d’optimisation
Le graphe biparti ne contient aucun cycle d’amélioration, donc on ne peut pas
améliorer en utilisant l’algorithme de Stepping Stone.

Figure 21 : Représentation de la solution sous forme de graphe biparti

Enfin la solution de base obtenue est une solution optimale.

= =
Conclusion
Le problème de transport est un problème linéaire qui peut être représenté sous forme d’un
graphe et qu’on peut le résoudre en utilisant les différentes méthodes de résolution des
problèmes linéaires. La solution de base initiale est obtenue par la méthode Coin Nord-Ouest
est très rapide mais ne fait pas intervenir les coûts, par contre la méthode de Balas Hammer
fait intervenir les coûts c’est pour cela est assez proche de l’optimum.
La méthode de Stepping Stone peut être appliquée à n’importe quelle solution de base, elle
consiste à modifier la solution de base admissible vers une solution meilleure.

Projet de Fin d’Etudes Page | 51

Chapitre IV : Implémentation

Chapitre IV :
Implémentation

Projet de Fin d’Etudes Page | 52

Chapitre IV : Implémentation

Introduction
Dans ce chapitre on va expliquer l’utilisation de l’application. Le modèle de test comprend
deux activités :
La première consiste à résoudre le problème d’affectation.
La deuxième consiste à évaluer les programmes de transport.

Donc dans ce qui suit, on va présenter les interfaces de l’application, qui vont détailler le
fonctionnement des deux problèmes.

Le test a prouvé la validité de l'utilisation de cette application pour trouver des solutions
optimales aux problèmes d’affectation et de transport.

1. Présentation de l’application
1.1. Menu principal
La première interface qui correspond au menu principal, est une interface qui donne la
possibilité d’effectuer le choix de l’un des deux problèmes par simple clic sur le
bouton correspondant.

Figure 22 : Interface Principale

2. Problème d’affectation
2.1. Choisir la taille du tableau
En cliquant sur le bouton Affectation, une boite de saisie s’ouvre et permet à
l’utilisateur de fournir la taille du tableau.

Projet de Fin d’Etudes Page | 53

Chapitre IV : Implémentation

Figure 23 : Fenêtre de saisie

2.2. Parcourir le fichier des données

Lorsque le choix de l’utilisateur a porté sur le bon fichier de données, vient par suite de
cliquer sur charger pour importer les données et lancer la résolution du problème.

Figure 24 : Ecran de parcours du fichier data

2.3. Charger le fichier data

Une fois les données apparaissent sur tableau, reste à lancer la résolution du problème
en cliquant sur le bouton Lancer.

Projet de Fin d’Etudes Page | 54

Chapitre IV : Implémentation

Figure 25 : Ecran de chargement des données

2.4. Lancer la résolution du problème

Cet écran visualise les différents choix de poursuivre la résolution du problème
d’affectation par la méthode hongroise représentés comme suit : par étape, par phase,
par augmentation des zéros et résoudre.

Figure 26 : Ecran visualisant les différents choix de résolution

Projet de Fin d’Etudes Page | 55

Chapitre IV : Implémentation

2.5 Résolution du problème d’affectation

Cet écran visualise la solution des affectations des tâches pour chaque agent.et le cout
optimale de cette affectation

Figure 27 : Ecran visualisant la solution finale

3. Problème de transport
3.1. Parcourir le fichier des données
Lorsque le choix de l’utilisateur a porté sur le problème de transport la fenêtre suivante
s’affiche, puis on lit les données qui sont déjà insérées sur un fichier bloc-notes.

Projet de Fin d’Etudes Page | 56

Chapitre IV : Implémentation
Figure 28 : Ecran visualisant l’accès aux données

3.2. Charger le fichier de données

Les données sont affichées comme suit : : Taille de la matrice des coûts unitaire.

: Offres. : Demandes. : Coûts unitaires.

Figure 29 : Ecran visualisant l’affichage des données

3.3. Lancer la résolution par la méthode Coin Nord-Ouest

Cet écran visualise la solution de base et le coût total obtenus par la méthode du Coin
Nord-Ouest

Figure 30 : Ecran visualisant la solution par Méthode du Coin Nord-Ouest

Projet de Fin d’Etudes Page | 57

Chapitre IV : Implémentation

3.4. Lancer la résolution par la méthode Stepping Stone

Cet écran visualise la solution optimale et le coût total obtenus par la méthode du Stepping
Stone.

Figure 31: Ecran visualisant la solution par Méthode de Stepping Stone

Projet de Fin d’Etudes Page | 58

Conclusion

Conclusion
Le problème de transport est une méthode qui permet d’optimiser certaines décisions
relatives à la planification de la production. Grace à l’informatique cet exercice est
aujourd’hui grandement simplifié. Mais comme cette méthode fait partie de la programmation
linéaire, on doit s’assurer, avant de l’appliquer, que la relation entre toutes les variables
utilisées est bien linéaire.
On peut dire que : Les problèmes de transport et d’affectation sont des cas particuliers de la
programmation linéaire, qu’on ne résout pas par le simplexe habituel. Il existe une méthode
de résolution plus simple, non matricielle. Si les coûts sont entiers, la solution est également
entière, donc si on peut formuler un problème sous forme de transport, la solution en entier est
également facilement calculable.

Projet de Fin d’Etudes Page | 59

 Annexe

Annexe
Dénes König [1884-1944]
Mathématicien hongrois.
En 1936, Auteur du premier manuel portant sur la théorie des graphes.
Ses résultats les plus connus sont le théorème de König et le lemme de König.

Harold William Kuhn [1925 –2014]

Mathématicien et économiste américain.
En 1 55, dans son célèbre papier : “ The Hungarian Method for the assignment problem, Naval
Research Logistic Quarterly, 1955, pp. 83- 97 ”, il mit au point l’algorithme hongrois.
Prix de théorie John von Neumann avec Albert Tucker en 1980.

Claude Berge [1926-2002]

Mathématicien et artiste français.
L’un des créateurs de la théorie des graphes.
Lauréat du prix Euler 1995.
Ouvrage majeur : Théorie des Graphes et ses Applications, Dunod, 1958.
Egerváry [1891-1958]
 Mathématicien hongrois .
 Egerváry, Jenő 1 31 , "Matrixok kombinatorius tulajdonságairól" [Sur les propriétés combinatoires des
matrices], Matematikai és Fizikai Lapok (en Hongrois),38 : 16-28
 Prix Gyula König en 1932 et le Prix Kossuth en 1949 et 1953.

Egon Balas [Cluj, Roumanie, le 7 Juin, 1922]

 Mathématicien appliqué et professeur d'administration industrielle et de mathématiques
appliquées à l'Université Carnegie Mellon.
 E. Balas, A. Saxena: Optimizing Over the Split Closure, Mathematical Programming 113, 2 (2008),
219–240.
 E. Balas: An Additive Algorithm for Linear Programming in Zero-One Variables, Operations
Research 13 (4), 1965; 517–546.
 Honorary Doctorate in Mathematics, University of Waterloo, 2005
 John von Neumann Theory Prize, INFORMS, 1995

Peter Ladislaw Hammer [Timisoara ,Roumanie, 1936-2006]

 Mathématicien en recherche opérationnelle et en mathématiques discrètes appliquées
 Méthodes booléennes en recherche opérationnelle, Dunod, Paris, 1970.
 Prix George Tzitzeica 1966
 Médaille d’Euler 1

Frank Lauren Hitchcock [1875-1957]

 Mathématicien et physicien américain
 En 1941, il formula le problème de transport
 Dr. Frank L. Hitchcock, Mathematician, Professor Emeritus at M.I.T., Dies at 82, The New York
Times, June 1, 1957, p. 17.
 Frank L. Hitchcock (1941) "The distribution of a product from several sources to numerous
localities", MIT Journal of Mathematics and Physics 20:224–230 MR0004469.
 1922: A Solution of the Linear Matrix Equation by Double Multiplication.

Projet de Fin d’Etudes Page | 60

Bibliothèque

REFERENCES BIBLIOGRAPHIQUES

 Robert Faure.,1996.,Précis de RECHERCHE OPEARTIONNELLE. -Méthodes

et exercices d’application. ,Dunod.
 SHWETA SINGH, G.C. DUBEY, RAJESH SHRIVASTAVA.,2012., A
Comparative Analysis of Assignment Problem., Volume 2., IOSR
 Cédrick TOMBOLA., 2011., RECHERCHE OPERATIONNELLE.-Les
problèmes combinatoires.
 Ahmed EL HILALI ALAOUI., 2009., initialisation à la RECHERCHE
OPERATIONNELLE.
 Didier MAQUIN.,2003., Elément de Théorie des Graphes. Ecole Nationale
Supérieure d’Electricité et de Mécanique.
 Yadolah Dodge-Sylvie Gonano-Weber et Jean-Pierre Renfer, 2002., Optimisation
appliquée., Springer

REFERENCES NETOGRAPHIQUES

 http://www.fredptitgars.net/informatique/rcp101-recherche-
operationnelle-et-aide-a-la-decision/
 http ://faculty.washington.edu\moishe\
 http://fr.wikipedia.org

Projet de Fin d’Etudes Page | 61