| Titre : | Éléments de Programmation linéaire avec application aux graphes |
| Auteurs : | Dominique De Werra, Auteur |
| Type de document : | Monographie imprimée |
| Editeur : | Lausanne [Suisse] : Presses Polytechniques et Universitaires Romandes, 1990 |
| ISBN/ISSN/EAN : | 978-2-88074-176-1 |
| Format : | 1 vol. (XII-306 p.) / couv. ill. en coul. / 24 cm |
| Langues: | Français |
| Index. décimale : | 519. 72 |
| Résumé : | Généralement, on appelle programmation mathématique la recherche de l'optimum d'une fonction de plusieurs variables liées entre elles par des contraintes. |
| Sommaire : |
Avant-propos
Introduction Chapitre 1 Convexité et optimisation linéaire 1.1 Définitions générales 11 1.2 Hyperplans d'appui 14 1.3 Optimisation de fonctions convexes • 19 1.4 Formulation du problème de programmation linéaire 23 1.5 Interprétation géométrique 25 1.6 Interprétation économique de la P.L 25 1.7 Inégalités linéaires 26 1.8 Exercices 30 Chapitre 2 Dualité 33 2.1 Dual d'un problème de P.L. 33 2.2 Interprétation économique de la dualité 35 2.3 Théorème de dualité 35 2.4 Théorème des écarts complémentaires 39 2.5 Exercices 41 Chapitre 3 Résolution du problème de programmation linéaire 45 3.1 Rappel sur les égalités linéaires 45 3.2 Propriétés fondamentales de la programmation linéaire 47 3.3 Méthode de Gauss—Jordan 54 3.3.1 Opération de pivotage 54 3.3.2 La forme tableau 61 3.3.3 Passage à une base "voisine" admissible 63 3.4 Algorithme du simplexe 65 3.5 Exemples 69 3.5.1 Un bon exemple 69 3.5.2 Absence de solutions optimales finies 71 3.5.3 Apparition de la dégénérescence 3.5.4 Unicité de la solution optimale 3.6 Exercices Chapitre 4 Compléments sur l'algorithme du simplexe 4.1 Algorithme fini du simplexe 83 4.2 Initialisation de l'algorithme du simplexe 86 4.3 Algorithme dual du simplexe 91 4.4 Retour à l'interprétation économique 98 4.5 Lecture des variables duales dans le tableau du simplexe 100 4.6 Exercices 101 Chapitre 5 Variations sur le simplexe 103 5.1 Algorithme du simplexe avec variables bornées 103 5.2 Postoptimisation et analyse de sensibilité 108 5.2.1 Introduction 108 5.2.2 Modification du second membre b 109 5.2.3 Addition d'une nouvelle contrainte 112 5.2.4 Modification des coefficients de la fonction économique 113 5.2.5 Eléments d'analyse de sensibilité 114 5.3 Programmation paramétrique 116 5.4 Exercices 119 Chapitre 6 Autres algorithmes pour la programmation Jineaire 121 6.1 Méthode révisée du simplexe 121 6.1.1 Eta factorisation de la base 121 6.1.2 Algorithme révisé du simplexe 122 6.2 Algorithme primal-dual 126 6.2.1 Notions de base 126 6.2.2 Formulation 127 6.2.3 Justification de l'algorithme 128 6.2.4 Un exemple 129 6.3 Méthode de décomposition de Dantzig—Wolfe 132 6.3.1 Généralités 132 6.3.2 Formulation de l'algorithme 135 6.3.3 Un exemple numérique 136 6.4 Minimisation de fonctions convexes séparables 139 6.5 Exercices 142 Chapitre 7 Eléments de théorie des graphes 143 7.1 Concepts fondamentaux de théorie des graphes 143 7.2 Représentations d'un graphe 146 7.2.1 Matrice d'incidence sommets-arcs 146 7.2.2 Listes d'adjacence 149 7.3 Exploration d'un graphe 150 7.4 Recherche d'un plus court chemin dans un réseau. . 154 7.5 Exercices 165 Chapitre 8 La méthode du simplexe dans les réseaux 169 8.1 Le problème de transbordement 169 8.1.1 La méthode du simplexe 172 8.1.2 Calculs des 2i 177 8.1.3 Dégénérescence 178 8.1.4 Détermination d'une solution-arbre admissible initiale 180 8.2 Algorithme fini du simplexe pour les réseaux 183 8.3 Le problème de transport 186 8.3.1 Formulation 186 8.3.2 Construction d'une solution-arbre admissible initiale 188 8.3.3 Exemple d'application de l'algorithme du transbordement particularisé au problème de transport 189 8.3.4 Dégénérescence 192 8.4 Théorème des valeurs entières 195 8.5 Implantation de l'algorithme du simplexe dans les réseaux 199 8.5.1 Choix de l'arc entrant dans T 199 8.5.2 Modification de x et 2 200 8.5.3 Modification de T 204 8.6 Exercices 208 Chapitre 9 Flot de valeur maximum 211 9.1 Le problème du flot maximum 211 9.1.1 Formulation et propriétés 211 9.1.2 Algorithme de Ford—Fulkerson 213 9.1.3 Justification de l'algorithme 216 9.2 Algorithme MKM de flot maximum 218 9.2.1 Idée et formulation de l'algorithme 218 9.2.2 Analyse de la complexité de l'algorithme 226 9.3 Applications de la notion de flot 228 9.4 Exercices 237 Chapitre 10 Flots à coût minimum et flots compatibles 241 10.1 Algorithme primal—dual pour le problème de transport 241 10.2 Flot à coût minimum 242 10.2.1 Formulation et propriétés 242 10.2.2 Deux algorithmes 252 10.3 Le problème de transbordement avec capacités et bornes de flot 259 10.4 Circulation dans un réseau avec capacités et bornes inférieures de flot 266 10.5 Exercices 269 Chapitre 11 273 11.1 Arbre de poids minimum 273 11.2 Propriétés supplémentaires des arbres optimaux 279 11.3 Matroïdes 281 11.4 Exercices 284 Appendice: Conditions d'optimalité 287 Bibliographie Solutions 295 Lexique 303 |
Portail documentaire de l'universitè Mohamed Khider Biskra
- Accueil
- infos pratiques
- Services aux adhèrants
- Accès aux ressources
-
Accès aux bibliothèques
- Bibliothéque centrale Chetma
- Faculté sciences exactes
- Faculté lettres et langues
- Faculté sciences économiques
- Département sciences de la vie
- Faculté sciences humaines
- Faculté droit et science politique
- Institut education physique
- Département d'agronomie
- Département d'architecture
- Faculté sciences et technologie
- Services aux professionels
Portail documentaire de l'université Mohamed Khider-Biskra Bibliothèque de la faculté sciences exactes
Portail documentaire de l'université Mohamed Khider-Biskra Bibliothèque de la faculté sciences exactes
- Accueil
- infos pratiques
- Services aux adhèrants
- Accès aux ressources
-
Accès aux bibliothèques
- Bibliothéque centrale Chetma
- Faculté sciences exactes
- Faculté lettres et langues
- Faculté sciences économiques
- Département sciences de la vie
- Faculté sciences humaines
- Faculté droit et science politique
- Institut education physique
- Département d'agronomie
- Département d'architecture
- Faculté sciences et technologie
- Services aux professionels
Retour a la page d'accueil
Compte d'adhesion
Coordonnées bibliothéque
Portail documentaire de l'universitè Mohamed Khider Biskra7000 Biskra
Algerie
033 54 32 99
Recherche documentaire
Thèses en ligne sur e-print
Afin de permetre une visibilité et accéssibilité du patrimoine scientifique de l'université l'université déja publié sur le portail national de thèses aux chercheurs ,le portail offre la possibilité