UNIVERSITE SIDI MOHAMED BEN ABDELLAH

FACULTE DES SCIENCES ET TECHNIQUES

Département des Mathématiques

Projet de Fin d’Etudes

Licence Sciences et Techniques

MATHEMATIQUES ET APPLICATIONS

Minimisation de coût de transport d’eau potable

Réalisé par :
LAMSSIAH AHLAME
Encadré par :
- Pr. ETTAOUIL Mohammed. (FST- Fès)
- Mr. LAHLOU Mohamed. (L’ONEEP)
Soutenu le 17 Juin 2015 devant le jury composé de :

Pr. ETTAOUIL Mohammed.

Pr .CHAKIR Loqman.

Pr .EL KHOULANI Rachid.

Pr. GHANOU Youssef.

Stage effectué à l’ ONEEP

Année universitaire : 2014 /2015

FACULTE DES SCIENCES ET TECHNIQUES FES_SAIS

B.P.2202_Route d’Imouzzer_FES
212(0)53561186_Fax:212(0)535608214
Site web: http://www.fst-usmba.ac.m
W°w|vtvxá
Je dédie ce thème …

À MES PARENTS que c’est grâce à eux que j’ai pu faire ce

travail je ne trouve pas les mots pour les remerciés et pour
exprimer mon amour éternel et j’espère
j’espère que ce travail soit un beau
cadeau pour vous.

À MON CHER MARI qui a été trop patient avec moi tout au long de
mes études. Je lui dédie ce travail, même si aucune dédicace n’exprimera
ma considération et mon grand respect envers lui.

À MES CHERES
CHERES SOEURS Je vous dédie également ce travail en
vous souhaitant un avenir plein de réussite et de bonheur.

À MES CHÈR(E)S AMI(E)S Pour l’amitié sincère et l’affection

profonde que nous partageons, pour tous les moments heureux que nous
ayons passé ensemble,
ensemble, je vous dédie ce travail en vous souhaitant une
vie pleine de réussite, de santé et de bonheur.

À TOUTES LES PERSONNES qui ont participé de près ou de

loin à la réalisation de ce travail.

2
 Je tiens à remercier tous ceux qui
qui m’ont aidé à réaliser ce travail,
et ceux qui ont veillé à l’organisation de ce stage en particulier :
Au terme de ce rapport, je veux remercie mon encadrant de stage :
Mr LAHLOU MOHAMED (chef Division Développement), Développement), pour ses
qualités de conseils
conseils et son orientation pour l’élaboration de ce travail.
Tous les membres du personnel de l’ONEE qui m’ont accueilli
chaleureusement durant ma période de stage.
Je remercie bien sur mes encadrant pédagogiques : Pr. CHAKIR
LOQMAN et Pr. ETTAOUIL MOHAMED MOHAMED,
HAMED, pour l’encadrement de ce
travail, pour tous le temps et l’aide qu’ils m’ont donné et aussi pour la
gentillesse et la spontanéité avec lesquelles vous avez
avez bien voulu diriger
ce travail.
travail.

Les membres du jury qui ont accepté d’évaluer ce travail , Mr.

CHAKIR LOQMAN (Pr. A l’école Supérieure de Technologie de
Meknès), Mr. ETTAOUIL Mohamed (Pr. A la Faculté des
Sciences et Techniques de Fès), Mr.
Mr. ELKHOULANI RACHID
(Pr. A la Faculté des Sciences et Techniques de Fès), et Mr.
GHANOU YOUSSEF (Pr. A l’école Supérieure de Technologie de
Meknès).
Meknès).

Enfin, je profite de cette occasion pour exprimer mes remerciements et

mes respects envers tous mes amis et ma famille.
famille.

3
Dédicaces……………………………………………………………………………………………………..2
Remerciement………………………………………………………………………………………………3
Introduction générale…………………………………………………………………………………..6
Chapitre 1.................................................................................................................... 7
Présentation de l’ONEEP ............................................................................................... 7
1-Présentation de générale l’ONEE ............................................................................................ 7
2-Objectifs de l’ONEE ................................................................................................................ 7
3-Missions de l’ONEE ................................................................................................................ 8
4-Les principales activités de l’ONEEP ........................................................................................ 8
5-L’organigramme générale de l’ONEEP..................................................................................... 9
6-Les directions régionales de l’ONEEP .................................................................................... 10
7-La direction régionale du centre nord Fès ............................................................................. 11
A-L’organigramme de la direction centre nord Fès <<DR5>> ...................................................................... 12
B-Missions de la DR5 .................................................................................................................................... 13
C-Ressources utilisées .................................................................................................................................. 13
D-Complexe de production d’Oued Sebou ................................................................................................... 13

Chapitre 2.................................................................................................................. 14
L’alimentation en eau potable .................................................................................. 14

1-définition ............................................................................................................................ 14
2-Description d'un réseau d'A.E.P............................................................................................ 14

Chapitre3 ................................................................................................................... 18
Problème de transport d’eau ..................................................................................... 18
1-Présentation de problème de transport................................................................................ 18
2-formulation du problème ..................................................................................................... 18
3-Modélisation générale du problème de transport ................................................................. 20
Exemple : ...................................................................................................................................................... 20
Modélisation ................................................................................................................................................ 20

4-la résolution du problème .................................................................................................... 22

Chapitre4 ................................................................................................................... 34
Traitement de données ................................................................................................ 34
1-Les logiciels utilisés : ............................................................................................................ 34
2-Langage utilisé : ................................................................................................................... 35
3-le programme du problème de transport en java .................................................................. 36

4
 4-la solution obtenu par le programme ................................................................................... 39
Conclusion……………………………………………………………………………………………………..40

Bibliographie…………………………………………………………………………………………………………………..41

Liste des figures

Figure 1 : schéma général d'un réseau d'A.E.P........................................................................... 13
Figure 2 : la représentation du problème sous forme d’un graphe.......................................... 18
Figure 3 : la représentation de la solution de base sous forme d’un graphe bipartie ........... 24
Figure 4 : l’algorithme de Stepping-Stone................................................................................25
Figure 5 : 1er graphe de potentiel ………………………..................................................................26
Figure 6 : 1ere chaine de substitution…...................................................................................27
Figure 7 : 2eme chaine de substitution....................................................................................28
Figure 8 : 2eme graphe de potentiel........................................................................................29
Figure 9 : la chaine de substitution..........................................................................................30
Figure 10 : graphe de potentiel................................................................................................31

5
 L'eau est une ressource essentielle pour l'humanité ; elle est nécessaire
aux besoins humains fonctionnels, consacrée à l'agriculture, elle est à la base
de l'alimentation humaine, elle contribue à de nombreuses activités
économiques, notamment dans le secteur industriel où elles sont les plus
importantes. Considérée comme un maillon primordial dans les équilibres
biologiques et écologiques : l'eau est donc au cœur de la problématique du
développement durable.

L‘évolution spectaculaire que connaît l’environnement urbain et industriel

pose, dans de nombreux pays : le problème de l’eau.

Aujourd’hui, il nous suffit d’ouvrir le robinet pour profiter à volonté d’une

eau de qualité. Après avoir été traitée, et stockée, l’eau est distribuée grâce à
des réseaux de canalisations.
Cela peut vous paraître simple et naturel, pourtant ses progrès sont récents.

Dans ce travail on va voir les étapes de conduction de cette matière brute et

on va s’intéresser au problème de distribution d’eau sous forme d’un problème
mathématique de transport, afin de minimiser le coût de distribution.

6
Chapitre 1

Présentation de l’ONEEP

1-Présentation de générale l’ONEEP

L’ONEE (Office Nationale de l’électricité et de l’Eau Potable) créé en 1972,

est un établissement public à caractère industriel et commercial, doté de la
personnalité civile et de l’autonomie financière, placé sous la tutelle du ministère
de l’Equipement.
Acteur principal dans le secteur de l'eau potable et de l'assainissement, les
missions principales de l'Office vont de la planification de l'approvisionnement en
eau potable jusqu'à sa distribution en passant par les phases, études, conception,
réalisation, gestion, exploitation des unités de production, de distribution et
d'assainissement liquide et enfin du contrôle de la qualité des eaux jusqu'à la
protection de la ressource.

2-Objectifs de l’ONEEP

La qualité des services de l’ONEE n’est pas seulement un enjeu économique,

c’est une mission dont l’objectif principale est la satisfaction d’une besoins vital :
garantir, en continu, la disponibilité d’une eau potable.

En effet, la politique de l’ONEE, se base sur les critères :

 La mise à disposition de l’eau en quantité suffisante et à coût

économiquement acceptable.
 Le respect des normes de qualité en vigueur.
 L’information et la sensibilisation.
 Le traitement des réclamations.

Pour atteindre ces objectifs, les efforts étaient et sont constamment déployés
pour trouver les meilleurs compromis entre les exigences du consommateur,
l’optimisation des coûts de production, la maîtrise totale des processus et la
garantie de l’adhésion des ressources humaines par la motivation et la
reconnaissance.

Mais, compte tenu de la complexité technique de la criticité du produit, la

nécessité d’une démarche informative n’a pas tardé à se faire sentir.

7
3-Missions de l’ONEEP

Les missions de l’ONEE sont :

Planification de l'approvisionnement en eau potable (AEP) à l’échelle nationale.

Production de l'eau potable.
Distribution de l'eau potable pour le compte des collectivités locales
Gestion de l'assainissement liquide pour le compte des C.L
Contrôle de la qualité des eaux
Pérenniser, Sécuriser et renforcer l'AEP en milieu urbain
Généraliser l’accès à l’eau potable en milieu rural
Rattraper le retard en matière d'Assainissement liquide

4-Les principales activités de l’ONEEP

PLANIFIER : L’approvisionnement en eau potable du Royaume et la

programmation des projets.

ETUDIER : L’approvisionnement en eau potable et assurer l’exécution des

travaux des unités de production.

GERER : La production d’eau potable et assure la distribution pour le comte

des commandes qui le souhaitent

CONTROLE : La qualité des eaux produites et distribuées et la pollution des

eaux susceptibles d’être utilisées pour l’alimentation humaine.

ASSISTER : En matière de surveillance de la qualité de l’eau.

PARTICIPER : Aux études, en liaison avec les ministres intéressés, des

projets de textes législatifs et réglementaire nécessaires à l’accomplissement
de sa mission

8
 5-L’organigramme générale de l’ONEEP

Direction Coopération et Conseil Stratégique

Communication
(2 directeurs)

Direction Audit et Chargé de Mission

DIRECTION
Organisation

Division contrôle des Chargé d'Etude

Opérations Equipement

Division contrôle des Services Corps des

Opérations Fonctionnement Chargés d'Etude

Direction Central du Pôle Direction Centrale du Pôle Direction Centrale du Pôle Direction Centrale du Pôle
Finances Ressources Industriel Développement

Direction Financière Direction des Direction Direction

Ressources Patrimoine Planification et
Humaines Stratégie

Direction Contrôle de Direction Direction Contrôle Direction

Gestion et Système Approvisionnements Qualité Technique et
d'Information Marchés Ingénierie

Direction des Division Projet Direction

Direction Moyens Communs Décentralisation Généralisation AEP
Commercial et
Marketing
Directions
Direction du Centre de Régionales Direction
Formation aux Assainissement et
(9Direction)
Techniques de l'Eau Environnement

Directions
provinciale et Division Unité de
agences Gestion Projet Eau
et Assainissement
en Milieu Rural
Centres Productions et
Mixtes

9
 6-Les directions régionales de l’ONEEP
Le nouveau découpage de l’ONEP au niveau régional a donné naissance à neuf
directions régionales selon l’ordre suivant :

Directions Régionales
ONEE

Direction Régionale du Direction Régionale du

Sud Agadir Centre Nord Fès
(DR1) (DR5)

Direction Régionale du Direction Régionale de

Tensift Marrakech l’Oriental Oujda
(DR2) (DR6)

Direction Régionale du Direction Régionale du

Centre Khouribga Centre Sud Meknès
(DR3) (DR7)

Direction Régionale des

Direction Régionale du
Provinces Sahariennes
Nord Ouest Kenitra
Laayoun
(DR4)

Direction Régionale de
la cote Atlantique Rabat
(DRC)

10
7-La direction régionale du centre nord Fès

La Direction Régionale du Centre Nord a été créée en juillet 1979 dans le cadre de la
décentralisation, elle a pour mission l’alimentation
l’alimentation en eau potable des zones dépendantes
de son territoire.

Cette Direction supervise aussi l’exploitation et la maintenance de l’ensemble des

installations existantes dans les centres de production et de distribution sous sa
responsabilité.

La Direction couvre la cinquième région économique du Royaume (DR5) regroupe deux

Régions : Région de FES - BOULMANE et Région de AL HOUCIMA – TAOUNATE - TAZA qui
comprennent la Préfecture de FES et les provinces d’AL HOCEIMA, TAOUNATE, TAZA,
SEFROU et BOULEMANE.

La Direction Régionale de FES (DR5) dispose actuellement 3 Directions Provinciales et une

Agence Mixte :

Direction Provinciale d’AL HOUCEIMA DR5/1

Direction Provinciale de TAOUNATE DR5/2
Direction Provinciale
ciale de TAZA DR5/3
Agence Mixte de FES -MOULAY YACOUB – SEFROU AM5/1

DIRECTION REGIONALE DU
CENTRE NORD
DR5

DIRECTION PROVINCIALE D’AL DIRECTION PROVINCIALE DE AGENCE MIXTE De FES -MOULAY

DIRECTION PROVINCIALE DE TAZA
HOCEIMA TAOUNATE YACOUB – SEFROU
DR5/3
DR5/1 DR5/2 AM5/1

L'organisation
ganisation administrative de la DR5 est constituée de quatre divisions qui comprennent
elles aussi des services, des bureaux et des cellules.
cellul

11
 A-L’organigramme de la direction centre nord Fès <<DR5>>

5 »DR5

DIRECTION REGIONALE

Sce. Contrôle des

Opérations

DIVISION DIVISION DIVISION DIVISION

DEVELOPPEMENT INDUSTRIELLE SUPPORT FINANCES

Sce. Sce. Exploitation Sce. Achats

Programmation et Sce.
Etudes d’AEP Eau Potable Comptabilité et
Finances

Sce. Travaux
Sce. Exploitation Sce. Règlement Sce.
d’AEP
Assainissement des Achats Commercial

Sce. Etudes Sce. Contrôle de Sce. Sce. Contrôle de

d’Assainissement la Qualité Administratif Gestion et SI

Sce. Travaux Sce. Sce. Moyens Sce. Juridique et

Actions
Assainissement Maintenance Communs
Foncières

Sce. Gestion des

Stocks

12
B-Missions de la DR5

Diriger les activités dans la région et plus particulièrement :

 Représenter le directeur général et l’ONEEP dans la région en vue, notamment, de

réaliser les axes stratégiques de l’office dans la région.

 Assumer les délégations de pouvoir et des crédits autorisés par le directeur général
dans la région.

 Coordonner les différentes actions de toutes les autres représentations de l’ONEP

avec les autres intervenants dans la région.

 Développer la région, consolidée, coordonner l’ensemble des actions d’exploitation

et de maintenance des ouvrages dans la région.

C-Ressources utilisées

Les ressources utilisées par l’ONEEP de Fès, pour la production de l’eau potable sont :

 Ressources souterraines : principalement des forages situés dans la plaine du

Saïs.

 Ressources superficielles : les eaux d’oued Sebou.

D-Complexe de production d’Oued Sebou

Ce complexe comprend:

 La station de prétraitement et de pompage située à Sebou: sa mise en œuvre

remonte à 1989 ; le rôle de la station est d’extraire l’eau brute et de diminuer le
taux de matière en suspension jusqu’à une valeur inférieure à 2g/l et de la refouler
jusqu’à la station du Traitement.

 La station de traitement de Ain NOUKBI ; édifié le 19 mars 1987. la station assure :

 Le traitement des eaux reçues de la station de prétraitement selon une

série d’étapes.
 Le contrôle de la qualité des eaux traitées (dans le laboratoire régional).
 Refoulement des eaux vers le réservoir BAB HAMRA.

13
Chapitre 2
L’alimentation en eau potable

Le distributeur d'eau potable a toujours le souci de couvrir les besoins des

consommateurs, en quantité et qualité suffisantes. Il a aussi le souci de veiller à la bonne
gestion et à la perfection de toutes les infrastructures concourant l'approvisionnement en
eau.

Dans ce chapitre, on va présenter les différents maillons constituant un réseau

d'Alimentation en Eau Potable (A.E.P).

1-définition

L’alimentation en eau potable (AEP) est l’ensemble des équipements, des services et des
actions qui permettent, en partant d’une eau brute, de produire une eau conforme aux
normes de potabilité en vigueur, distribuée ensuite aux consommateurs.

2-Description d'un réseau d'A.E.P

Un réseau d'A.E.P constitue l'ensemble des moyens et infrastructures pour transporter

l'eau depuis la source jusqu'au consommateur.

Le transport de l'eau de la source jusqu'au point de distribution se fait suivant une chaîne
composée de quatre maillons principaux :

Distribution
Ressource

Production et
traitement
Stockage

Figure 1 : Schéma général d'un réseau d'A.E.P

14
 Maillon ressource :

La ressource est une structure permettant le captage de l'eau. La prise d'eau se fait
habituellement par un captage d'eau de surface (rivière, lac, barrage, etc.) ou on procède au
captage d'eau souterraine (forage, puits, galeries, sources, ...).

 Maillon production - traitement :

Ce maillon est un ensemble constitué d'une station de pompage et d'un dispositif

d'adduction (conduite et accessoires).

Le traitement de l'eau brute se passe généralement en trois étapes :

• La clarification
• La stérilisation
• L'affinage

 Maillon stockage :

Le réservoir de stockage est un bassin qui se remplit au cours des faibles consommations
et qui se vide pendant les périodes de fortes consommations journalières. Le réservoir
présente deux utilités (technique et économique).

 Le réseau de distribution :

Du réservoir de stockage sort une conduite principale de gros diamètre. Celle-ci, en se

prolongeant le long des rues de l'agglomération forme un ensemble de conduites
maîtresses. Sur chacune de ces dernières, sont branchées des conduites de diamètres
moindres dites conduites secondaires, tertiaires, etc.

L'ensemble de toutes ces différentes canalisations avec l'ensemble des équipements qui
les accompagnent forment le réseau de distribution. C'est l'infrastructure la plus
importante du réseau global, car il s'étend sur toute la surface de l'agglomération.

Voila un dessin pour découvrir quel est le voyage de l’eau, de la source au robinet.

C’est un résumé des étapes nécessaires pour que l’on puisse consommer cet or bleu :

15
16
C’est pour cela qu’on va s’intéresser au problème de coût de transport de cette de la partie
de distribution à partir des réservoirs passant par un réseau de galeries qui va jusqu’aux
robinets.

Donc on doit savoir :

Qu’est ce qu’un problème de transport ?

Qu’elles sont les méthodes utilisés pour pouvoir le résoudre?

Qu’elle est le langage utilisé pour le programmer?

Toutes ces informations on va les traiter dans le chapitre 3.

17
Chapitre3
Problème de transport d’eau

Toute les entreprises qu’elle que soit sa taille, son domaine d’activité est amenée à faire
face à des problèmes de gestion au quotidien.
Parmi ces problèmes, on cite le problème de transport qu’on va le traiter dans ce chapitre
et spécifiquement le problème de coût de transport d’eau potable et les méthodes utilisées
pour le résoudre.

1-Présentation de problème de transport

C’est en 1941 que Frank Lauren Hitchcock à formulé pour la première fois le problème de
transport, et en suite par le mathématicien français Gaspard Monge en 1781.
D'importants développements ont été réalisés dans ce domaine pendant la Seconde Guerre
Mondiale par le mathématicien et l’économiste russe Leonid Kantorovitch [5]. Ce problème
consiste à minimiser le coût de transport total d’un plan d’expédition. Le fait de minimiser à
la fois la distance totale et le coût de transport fait partie de la théorie des flux de réseaux.
Le problème de transport « classique »est en fait un cas particulier d’un problème de flux de
réseaux.

Le problème de transport est un problème linéaire que 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éaire qu'on va présenter par la suite.

Un problème de transport peut être défini comme l’action de transporter des

marchandises ou des produits fabriqués par m origines vers n destinations, d’une manière
que le coût total de transport soit minimal.

Donc, la résolution d’un problème de transport consiste à organiser le transport de façon à

minimiser le coût total de transport.

2-formulation du problème

Avant de commencer la formulation du problème, considérant la notation suivante :

 = la quantité disponible du produit à l’origine i.

 = la quantité requise à la destination j.
 = quantité transportée des unités de l’origine i vers la destination j.
 = le coût de transport d’une unité de l’origine i vers la destination j.

18
 On peut d’écrire un problème de transport de la façon suivante :
Une quantité donnée d’un produit uniforme est disponible à chacune des origines (par
exemple des dépôts ou usines). Il s’agit d’envoyer des quantités spécifiées à chacune des
destinations (par exemple des points de vente). 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 minimal de m origines vers n destinations.

La variable  représentera le nombre d’unités expédiées de l’origine i vers la destination j.

Nous supposerons qu’il y a m origines et n destinations.

 ≥ 0 pour tout i, j.

 différents.
Pour chaque origine i donnée, il y a n valeurs de j possibles ; cela implique qu’il y a (m × n)

Donc on peut résumer le problème de transport par le graphe suivant :

C11 X11
a1 1 1 b1

2 b2
a2 2

 

 m n 

L’ensemble des L’ensemble des

Origines destinations

Figure 2: la représentation du problème sous forme d’un graphe

19
3-Modélisation générale du problème de transport

On peut modéliser le problème de transport de la manière suivante :


min  =    

 

 
 


 
 =   ∀ i ∈ 1, … , m , ∀ j ∈ 1, … , n
  


  =
 ∀ i ∈ 1, … , m
 
 
   =  ∀ j ∈ 1, … , n
 

∈ N ; ∀ i ∈ 1, … , m
 
  ∈ N ; ∀ j ∈ 1, … , n

 ∈ N ; ∀ i ∈ 1, … , m , ∀ j ∈ 1, … , n

Exemple : (Distribution d’eau potable)

On veut alimenter trois douars en eau potable à partir de trois réservoirs afin de minimiser le
coût total de transport d’eau, telle que :

 = les capacités de fourniture d’eau par jour de chaque réservoir i.

 = les demandes de chaque douar j par jour.

 = le cout de transport d’eau à partir d’un réservoir i vers le douar j.

 = la quantité d’eau envoyée du réservoir i vers douar j.

Modélisation
Données :

Les réservoirs i Capacité

Res.1 5000 m3 /jour
Res.2 2000 m3 /jour
Res.3 3000 m3 /jour

20
 Les douars j Les demandes
D1 2200 m3 /jour
D2 2500 m3 /jour
D3 5300 m3 /jour

Les coûts de transport (en DH/ 100 m3) sont résumer dans le tableau suivant :

i j D1 D2 D3
Res.1 8 5 6
Res.2 15 10 12
Res.3 3 9 10

Contraintes :

• Contraintes de production

x11 + x12 + x13 = 5000

x21 + x22 + x23 = 2000

x31 + x32 + x33 = 3000

• Contraintes de consommation

x11 + x21 + x31 = 2200

x12 + x22 + x32 = 2500

x13 + x23 + x33 = 5300

• Plus les contraintes habituelles ( ≥ 0)

Fonction objectif :

Min z = 8 x11 + 5 x12+ 6 x13+ 15 x21+ 10 x22+ 12 x23+ 3 x31+ 9 x32+ 10 x33

21
Modèle mathématique :

Min  = 8 + 5 + 6 + 15 + 10 + 812 + 3 + 9 + 10
  % ' % %% %' ' '% ''

  + % + ' = 5000

  +  +  = 2000
 % %% %'

' + '% + '' = 3000

  + % + ' = 2200

 % + %% + '% = 2500


 ' + %' + '' = 5300


 ≥ 0

4-la résolution du problème

La résolution du problème passe par deux étapes essentielles :

• La première c’est de trouver une solution de base initiale.

• La deuxième étape est de trouver la solution optimale à partir de la solution de
base.

4.1-Recherche d’une solution de base initiale

4.1.1. Définition:

On appelle solution de base une solution vérifiant les contraintes du problème et qui
comporte exactement (m-1) (n-1) flux nuls.

4.1.2. Obtention d’une solution de base par la méthode du coin Nord-Ouest :

C’est la méthode la plus rapide et la plus simple pour déterminer 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.

22
4.1.3. Règle du coin Nord-Ouest :

On considère à chaque étape, la case la plus Nord à l’Ouest de la matrice des coûts. On
part donc de la route (i1 ; j1) ; on sature soit la ligne i1 soit la colonne j1. Puis on recommence
sur la sous-grille formée des lignes et des colonnes non saturées.
Donc L’idée de la méthode est de remplir au maximum la case du tableau en haut, à gauche,
puis compléter sur la ligne ou la colonne (de façon à atteindre l’offre ou la demande) et
continuer ainsi à compléter les cases immédiatement à droite et en dessous
alternativement.
On peut résumer la méthode dans l’algorithme suivant :

4.1.4. Méthode :

2-  = min (
 ; ). Si  =
 passer à (3) sinon passer à (4).
1- i =1, j=1

3- Poser  =  -
 et i=i+1, si i ≤ n passer à (2) sinon fin.

4- Poser
 =
 –  et j=j+1, si j ≤ m passer à (2) sinon fin.

En appliquant la méthode sur l’exemple donné :

D1 D2 D3 ai
Res.1 8 5 6 5000
Res.2 15 10 12 2000


Res.3 3 9 10 3000
2200 2500 5300 10000

Dans le coin Nord-Ouest on met la plus grande valeur qui va soit satisfaire une demande ou
bien épuiser une disponibilité.

D1 D2 D3 ai
Res.1 2200 5000-2200=2800
Res.2 2000


Res.3 3000
2200-2200=0 2500 5300

En suite on refait la même chose, mais sur le nouveau sous tableau qu’on obtient après la
1ere modification.

23
 D1 D2 D3 ai
Res.1 2200 2500 2800-2500=300
Res.2 2000


Res.3 3000
2200-2200=0 2500-2500=0 5300

D1 D2 D3 ai
Res.1 2200 2500 300 300-300=0
Res.2 2000


Res.3 3000
0 0 5300-300=5000

D1 D2 D3 ai
Res.1 2200 2500 300 0
Res.2 2000 2000-2000=0


Res.3 3000
0 0 5000-2000=3000

D1 D2 D3 ai
Res.1 2200 2500 300 0
Res.2 2000 0


Réés.3 3000 3000-3000=0
0 0 3000-3000=0

A la fin on obtient notre solution de base qui vérifie les contraintes de problème, donc la
solution de base ainsi obtenue est représentée dans le tableau suivant :

D1 D2 D3 ai
Res.1 2200 2500 300 5000
Res.2 2000 2000


Res.3 3000 3000
2200 2500 5300

Le coût total de cette solution :

Z0 = (2200*8) + (2500*5) + (300*6) + (2000*12) + (3000*10) = 85900 DH/100 m3.

24
Comme on peut représenter la solution de base dans le graphe suivant :

8
Res. 1 D.1

5
Res .2 12 D.2
6

Res .3 D.3
10

Figure 3 : la représentation de la solution de base sous forme d’un graphe bipartie.

4.2- Recherche d’une solution Optimal

4.2.1. Méthode de Stepping-Stone :

Cette méthode est la plus connue parmi les méthodes de résolution du problème de
transport, on peut l’appliquée à n’importe quelle solution de base de notre problème, ainsi
on peut résumer l’algorithme dans les trois points suivants :

 Calcul des potentiels associés aux origines et aux destinations.

 Calcul des variations de coût unitaire (les coûts marginaux) pour chaque case vide(δ).

 Calcul de la quantité maximale (q) qu’on peut ajouter à la case vide.

On va expliquer par la suite ces trois points.

25
On peut écrire l’algorithme de Stepping-Stone comme suit :

Figure 4: l’algorithme de Stepping-Stone.

On va appliquer les étapes de l’algorithme à notre exemple.

D1 D2 D3 ai
Res.1 2200 2500 300 5000
Res.2 2000 2000


Res.3 3000 3000
2200 2500 5300

26
 On commence par le calcule des potentiels de chaque sommet (origine et destination)
du graphe biparti correspond à la solution.

-./0. = 0), en suite on calcule les autres potentiels en utilisant le principe suivant :
Pour cela on va donner un potentiel nul à une des origines du problème (par exemple ici

Soit - le potentiel au sommet, pour tout arc (i, j), on doit avoir 2 = 0 en d’autre terme il
faut que  = tj–ti donc pour calculer les potentiels il faut utiliser l’une des relations
suivantes :

- = + - pour calculer la potentiel d’une destination.

• - = - -  pour calculer la potentiel d’une origine.
•

Les potentiels calculés pour cette étape sont représentés dans le graphe suivant :

8 tD.1 =8+0=8
tres.1 =0

tres.2 = -6 tD.2 =5+0=5

6
12

tres.3 = -4 tD.3 =6+0=6

10

Figure 5 :1er graphe de potentiel.

Après le calcul des potentiels, on passe au calcul des coûts marginaux des cases vides dans le
tableau c.-à-d les arcs qui n’appartiennent pas au graphe précédent, donc on cherche s’il

Le calcul des coûts marginaux se fait par la relation suivant : 2 =  – (- - - ) quel que
existe une nouvelle liaison qui permettrait d’améliorer la solution précédente.

soit l’arc (i, j).

Les coûts marginaux sont :

- δres2-D1 = 15 – (8+6)= 1 - δres3-D1 = 3 – (8+4)= -9

- δres2-D2 = 10 – (5+6)= -1 - δres3-D2 = 9 – (5+4)= 0

27
Puisque il existe des coûts marginaux qui sont strictement négatifs donc la solution n’est pas
optimale et on peut l’améliorer grâce aux arcs (res2, D2) ou (res3, D1).

Donc on ajoute cette liaison dans le graphe pour construire la 1ere chaine de substitution :

tres.1 =0 tD.1 =8+0=8

-q
+q

tres.2 = -6 tD.2 =5+0=5

+q

-q

tres.3 = -4 tD.3 =6+0=6

Figure 6 : la 1ere chaine de substitution.

Après la détermination de la chaine de substitution, il nous reste que trouver la quantité q

qu’on peut transporter par la liaison qu’on a ajoutée, pour remplir une case vide il faut
diminuer une case pleine, donc constituer un circuit de cases pleines qu’on vide et remplir
alternativement :

D1 D2 D3 ai
Res.1 2200 2500 – q 300+q 5000
Res.2 +q 2000 -q 2000


Res.3 3000 3000
2200 2500 5300

28
D’où q représente la quantité maximale qu’on peut transporter sur la liaison ajoutée
(c.-à-d) : q = min (2500, 2000) = 2000

On ajoute la 2eme liaison dans le graphe pour construire la 2eme chaine de substitution :

-q
tres.1 =0 tD.1 =8+0=8

+q
+q

tres.2 = -6 tD.2 =5+0=5

tres.3 = -4 tD.3 =6+0=6

-q

Figure 7 : la 2eme chaine de substitution.

D1 D2 D3 Ai
Res.1 2200-q 2500 300+q 5000
Res.2 2000 2000
Res.3 Q 3000-q 3000
bj 2200 2500 5300

q = min (2200, 3000) = 2200

Le gain du 1ere chaine est : 2000*1=2000.

Le gain du 2eme chaine est : 2200*9=19800.

On a retenu la chaine qui réalise le plus fort gain (c.à.d.) la 2eme on obtient :

D1 D2 D3
Res.1 2500 2500
Res.2 2000
Res.3 2200 800

29
Le coût total de transport :

Z1 = (2500*5) + (2500*6) + (2000*12) + (2200*3) + (800*10) = 66100 DH/100 m3.

Donc on remarque que le coût total a diminué par rapport au coût de la solution de base
Z1< Z0 = 85900 DH/ 100 m3.

On refait les mêmes étapes précédentes sur la nouvelle solution :

tres.1 =0 tD.1 =-1

5

tres.2 = -6 12
tD.2 =5

tres.3 = -4 tD.3 =6
10

Figure 8 :2eme graphe de potentiel.

Les coûts marginaux sont :

- δres2-D1 = 15 – (-1+6)= 10 - δres1-D1 = 8 – (-1+0)= 9

- δres2-D2 = 10 – (5+6)= -1 - δres3-D2 = 9 – (5+4)= 0

30
On a un coût marginal strictement négatif donc la solution n’est pas optimale et on peut
l’améliorer grâce à l’arc (res2, D2) suivant :

tres.1 =0 tD.1 =-1

-q

+q
tres.2 = -6 tD.2 =5

+q

-q

tres.3 = -4 tD.3 =6

Figure 9 : la chaine de substitution.

D1 D2 D3
Res.1 2500-q 2500+q
Res.2 +q 2000-q
Res.3 2200 800

q = min (2500, 2000) = 2000.

Le gain est : 2000*1=2000.

On obtient la solution suivante :

D1 D2 D3
Res.1 500 4500
Res.2 2000
Res.3 2200 800

31
L’arbre associé est :

tres.1 =0 tD.1 =-1

5

tres.2 = -6 10
tD.2 =5

tres.3 = -4 tD.3 =6
10

Figure 10 : graphe de potentiel.

Le coût total de transport :

Z2 = (500*5) + (4500*6) + (2000*10) + (2200*3) + (800*10) = 64100 DH/100 m3.

Donc on remarque que le coût total a diminué par rapport au coût de la solution de base
Z2< Z1 =66100DH/ 100 m3.

Les coûts marginaux sont :

- δres2-D1 = 15 – (-1+5)= 11 - δres1-D1 = 8 – (-1+0)= 9

- δres2-D3 = 12 – (5+6)= 1 - δres3-D2 = 9 – (5+4)= 0

On a trouvé que tous les coûts sont positifs, stop la solution précédente est donc optimale.

D1 D2 D3 Ai
Res.1 500 4500 5000
Res.2 2000 2000
Res.3 2200 800 3000
bj 2200 2500 5300

32
On transportera donc :
A partir de Res.1 : 500 m3/j vers le douar.2 ; 4500 m3/j vers le douar.3.
A partir de Res.2 : 2000 m3/j vers le douar.2.
A partir de Res.3 : 2200 m3/j vers le douar.1 ; 800 m3/j vers le douar.3.

Le coût total de transport est :

Z = 64100 DH/100 m3

Remarque :

Si la 1ère contrainte n’est pas vérifier c.-à-d.


 ≠ ∑ 
∑

On pourra se ramener à l’énoncé précédent de la manière suivante :

- si :

∑

 > ∑ 

Il suffit d’ajouter une destination fictive de coût de transport infini dont la demande est :

 6 = ∑

 − ∑ 

- si :

∑

 < ∑ 

On ajoute une origine fictive de coût de transport infini, dont la disponibilité est :

6 =∑   − ∑



33
Chapitre4
Traitement de données

Dans ce chapitre on est intéressé d’utiliser des outils informatiques qui vont nous aider à
résoudre le problème d’une façon plus rapide.

1-Les logiciels utilisés :

 Eclipse :

Eclipse est un projet de la fondation Eclipse visant à développer tout un environnement

de développement libre, extensible, universel et polyvalent.

Son objectif est de produit et fournir divers outils gravitant autour de la réalisation de
logiciel, englobant les activités de codage logiciel proprement dites (avec notamment un
environnement de développement aussi de modélisation, de conception, de test, etc. Son
environnement de développement notamment vise à la généricité pour lui permettre de
supporter n’importe quel langage de programmation.

 Cplex :

ILOG CPLEX (plus communément appelé "CPLEX") est un outil

informatique d'optimisation. Son nom fait référence au langage C et à
l'algorithme du simplexe.

Il est composé d'un exécutable (CPLEX Interactif) et d'une bibliothèque

de fonctions pouvant s'interfacer avec différents langage de
programmation (CPLEX Callable Library) C, C++, C#, Java et Python.

34
2-Langage utilisé :

 Java :
Java est à la fois un langage de programmation informatique orienté
objet et un environnement d'exécution informatique
in portable crée par James
Gosling et Patrick Naughton employés de Sun Microsystems avec le soutien
de Bill Joy (cofondateur de Sun Microsystems en 1982), présenté
officiellement le 23 mai 1995 au SunWorld.
SunWorld

Java est à la fois un langage de programmation

programmation et un environnement d’exécution le
langage Java a la particularité principale que les logiciels écrits avec ce dernier sont très
facilement portables sur plusieurs systèmes d'exploitation tels qu’Unix, Microsoft Windows,
Mac OS ou Linux Pour cela, divers plateformes associés visent à guider, sinon garantir,
cette portabilité des applications développées en Java.

Le langage reprend en grande partie la syntaxe du langage C++, très utilisé par les
informaticiens. Néanmoins, Java a été épurée des concepts
cepts les plus subtils du C++ et à la fois
les plus déroutants, tels que les pointeurs et références remplacé par l'implémentation des
interfaces. Les concepteurs ont privilégié l'approche orientée objet de sorte qu'en Java, tout
est objet à l'exception dess types primitifs (nombres entiers, nombres à virgule flottante, etc.)

Java permet de développer des applications autonomes mais aussi, et surtout, des
applications client-serveur.
serveur. Côté client, les applets sont à l'origine de la notoriété du langage.
langag
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 (Java Server Pages)
peuvent se substituer à PHP, ASP et ASP.NET.

Les applications Java peuvent

uvent être exécutées sur tous les systèmes d'exploitation pour
lesquels a été développée une plate-forme
plate forme Java, dont le nom technique est JRE (Java
Runtime Environnement - Environnement d'exécution Java). Cette dernière est constituée
d'une JVM (Java Virtuall Machine - Machine Virtuelle Java), le programme qui interprète le
code Java et le convertit en code natif. Mais le JRE est surtout constitué d'une bibliothèque
standard à partir de laquelle doivent être développés tous les programmes en Java. C'est la
garantie de portabilité qui a fait la réussite de Java dans les architectures client-serveur
client en
facilitant la migration entre serveurs, très difficile pour les gros systèmes.

35
Exemple :
3-le programme du problème de transport en java

36
37
38
4-la solution obtenu par le programme

39
 Avant de parvenir au robinet du consommateur, l’eau brute subi
une série de galeries de conduites. Parmi ces derniers, on cite les
réservoirs, les canalisations, les stations etc.

L’objectif de ce travail est d’optimiser le coût de transport d’eau

potable, on a traité seulement le cas linéaire de problème de
transport, et on a essayé de minimiser le coût de transport d’eau en
appliquant des méthodes mathématiques et informatiques, et on a
réussi de trouver la même solution.

J’espère avoir traité dans ce rapport les points essentiels

concernant le problème de transport d’eau potable dans l’office.

A la fin je peux dire que ce travaille représente une base de départ

pour résoudre les problèmes généraux de transport.

40
Références bibliographiques

Cours de Mr. ETTAOUIL

http://fr.wikipedia.org/wiki/Eau_potable
http://www.onep.ma/
http://books.google.fr/
http://www.doc-etudiant.fr/
http://www.iecn.unancy.fr/~garet/cours/graphes/graphes
.pdf

41