4
Dédicace……………………………………………………………………………………………………………2
Remerciement………………………………………………………………………………………………………3
Sommaire………………………………………………………………………...………………………………...4
Liste des figures…………………………………………………………………………………………………….6
Introduction générale………………………………………………………….……………………………………7
Chapitre 1 : Notions de base …………………………………………..…………………………………………...9
1. Eléments de Théorie des graphes……...…………….……………………………………….. ……...9
1.1 Un graphe :…………………………………………………………………………………9
1.2 Ordre, orientation et multiplicité d’un graphe…………………………………………….10
1.3 Qualificatifs des graphes………………………………………………………………….11
1.4 Matrices associées à un graphe :………………………………………………….………12
1.5 Vocabulaire lié a la connexité…………………………………………………………….14
2. Programmation linéaire ……………………………………………………………………………..15
2.1 Forme générale d’un programme linéaire………………………………………………...15
2.2 Formes matricielles classiques et conventions………………………………………........15
2.3 Interprétation économique………………………………………………………………...16
2.4 La méthode de simplexe…………………………………………………………………..16
Chapitre 2 : Problème de transport………………………………………………………………………………..18
1. Positionnement de problème…………………………………………………………………………18
2. Modélisation …………………………………………………………………………………………18
2.1 Les variables de décision………………………………………………………………….19
2.2 La fonction objective………………………………………………………………….......19
2.3 Les contraintes ……………………………………………………………………………19
2.4 Formulation mathématique………………………………………………………………..20
3. Problème de transport non équilibré…………………………………………………………………21
4. Tableaux de transport………………………………………………………………………………...21
5. Réseau de transport………………………………………………………………………………......22
6. Dégénérescence en problème de transport …………………………………………………………..23