TABLE DES MATIERES
Introduction ..................................................................................................................... 5
Chapitre 1 Généralités sur la Programmation Linéaire ................................................ 13
1.1. UN EXEMPLE SIMPLE
13
1.2. ETUDE DU CAS GÉNÉRAL
16
1.3. THÉORÈMES GÉNÉRAUX SUR LES PROGRAMMES LINÉAIRES
20
1.4. INTRODUCTION À L'ALGORITHME DU SIMPLEXE
32
ANNEXE
40
Chapitre 2 Algorithme du simplexe ............................................................................. 45
2.1. UN EXEMPLE SIMPLE
45
2.2. CAS GÉNÉRAL. RÈGLES DU PIVOTAGE
56
2.3. RECHERCHE D'UNE SOLUTION DE BASE INITIALE
60
2.4. CAS DE LA DÉGÉNÉRESCENCE DU PREMIER TYPE
63
Chapitre 3 Dualité ........................................................................................................ 67
3.1. DÉFINITION
67
3.2. SIGNIFICATION ÉCONOMIQUE DU PROGRAMME DUAL
68
3.3. CORRESPONDANCE ENTRE VARIABLES DU PRIMAL ET VARIABLES DU DUAL
69
3.4. THÉORÈMES SUR LA DUALITÉ
71
3.5. PASSAGE DU PRIMAL AU DUAL SUR UN EXEMPLE
78
3.6. INTERPRÉTATION ÉCONOMIQUE DES VARIABLES DU DUAL
80
Chapitre 4 Paramétrisation .......................................................................................... 83
4.1. PARAMÉTRISATION DE LA FONCTION ÉCONOMIQUE
84
4.2. PARAMÉTRISATION DU SECOND MEMBRE
88
4.3. PARAMÉTRISATION D'UN COEFFICIENT DE LA MATRICE DES CONTRAINTES
93
Chapitre 5 Compléments et autres algorithmes ........................................................... 95
5.1. AUTRES MÉTHODES
95
5.2. PROLONGEMENTS
103
Chapitre 6 Problèmes de chemins .............................................................................. 107
6.1. DÉFINITION D'UN GRAPHE
107
6.2. ELÉMENTS DE VOCABULAIRE DE LA THÉORIE DES GRAPHES
109
6.3. PROBLÈMES DE CHEMINS
113
6.4. APPLICATION DE LA NOTION DE CHEMINEMENT DANS UN GRAPHE :
LES PROBLEMES D'ORDONNANCEMENT
132
6.5. LES AUTRES TYPES DE PROBLÈME
148
Chapitre 7 Arbres et arborescences ........................................................................... 149