Couverture Page de titre Notations et conventions 1. CONCEPTS BASIQUES 1.1. PROGRAMME LINÉAIRE 1.2. EXEMPLE DE PROGRAMME LINÉAIRE 1.3. FORMES D'UN PROGRAMME LINEAIRE 1.4. SOLUTION RÉALISABLE ET SOLUTION OPTIMALE 1.5. MÉTHODE DIT GRADIENT 1.6. MÉTHODE ALGÉBRIQUE 1.7. FONCTION OBJECTIF CONVEXE LINÉAIRE PAR MORCEAUX 1.8. EXERCICES 2. GEOMÉTRIE DES PROGRAMMES LINÉAIRES 2.1. ENSEMBLES CONVEXES 2.2. ENVELOPPE CONVEXE ET ENVELOPPE CONIQUE 2.3. POINTS EXTRÊMES ET DIRECTIONS EXTRÊMES 2.4. HYPERPLAN ET DEMI-ESPACE FERMÉ 2.5. POLYÈDRE ET CÔNE POLYÉDRAL 2.6. POINTS EXTRÊMES. DIRECTIONS EXTRÊMES ET FACES D'UN POLYÈDRE 2.7. REPRÉSENTATION D'UN POLYÈDRE 2.8. EXERCICES 3. THÉORIE FONDAMENTALE 3.1. CONDITIONS D'EXISTENCE D'UN POINT DANS UN POLYÈDRE 3.2. HYPOTHÈSE DE PLEIN RANG DE LA MATRICE DES CONTRAINTES 3.3. SOLUTION DE BASE RÉALISABLE 3.4. THÉORÈMES FONDAMENTAUX 3.5. UN ALGORITHME DE FORCE BRUTE 3.6. EXERCICES 4. ALGORITHME DU SIMPLEXE 4.1. DESCRIPTION DE L'ALGORITHME DU SIMPLEXE 4.2. CORRECTION DE L'ALGORITHME DU SIMPLEXE 4.3. FINITUDE DE L'ALGORITHME DU SIMPLEXE 4.4. OBTENTION D'UNE SOLUTION DE BASE RÉALISABLE INITIALE 4.5. COMPLEXITÉ DE L'ALGORITHME DU SIMPLEXE 4.6. EXERCICES 5. ALGORITHME DU SIMPLEXE RÉVISÉ 5.1 MOTIVATION 5.2. ÉNONCÉ DE L'ALGORITHME RÉVISÉ 5.3. PREMIÈRE VERSION. PIVOTAGE DANS UN TABLEAU 5.4. MATRICE ÉLÉMENTAIRE ET INVERSION 5.5. SECONDE VERSION: FORME PRODUIT DE L'INVERSE 5.6. EXERCICES 6. DUALITÉ 6.1. MOTIVATION 6.2. DÉFINITION ET RÈGLES D'ÉCRITURE DU DUAL 6.3. THÉORÈME FONDAMENTAL DE LA DUALITÉ 6.4. ÉCARTS COMPLÉMENTAIRES 6.5 . CERTIFICAT D' OPTIMALITÉ 6.6. EXERCICES 7. COMPLEXITÉ DE LA PROGRAMMATION LINÉAIRE 7.1. BISECTION RÉCURSIVE 7.2 PROGRAMME LINÉAIRE ET PROBLÈME DE DÉCISION ASSOCIÉ 7.3 SYSTÈME D'INÉGALITÉS LINÉAIRES 7.4 QUELQUES FAITS CONCERNANT LES ELLIPSOÏDES 7.5 MÉTHODE DES ELLIPSOÏDES 7.6 EXERCICES ANNEXE. PRÉREQUIS D'ALGÈBRE LINÉAIRE 1. SOUS-ESPACES VECTORIELS LINÉAIRES 2. MATRICES ET VECTEURS 3. MATRICES INVERSIBLES ET INVERSION DE MATRICES 4. DÉTERMINANT 5. SOUS-ESPACES AFFINES 6. MATRICES DÉFINIES POSITIVES ET NORMES BIBLIOGRAPHIE INDEX « Cet ouvrage est destiné à un public universitaire de niveau avancé en licence et en master. Les domaines ciblés sont essentiellement : Mathématiques-Informatique, Ingénierie, Économie, Management. Ce livre met l'accent aussi bien sur l'aspect théorique que sur l'algorithmique, ainsi que sur les questions liées à la complexité. Le chapitre 1 introduit ce qu'est un programme linéaire (PL) et quelques faits basiques afférents. L'ensemble de toutes les solutions d'un PL est un polyèdre et le chapitre 2 étudie la géométrie de ce dernier. Le chapitre 3 étudie la théorie fondamentale sous-jacente. Cette théorie permet la conception de l'algorithme du simplexe présenté et analysé sous tous ses aspects (correction, finitude et complexité) au chapitre central numéro 4. En quête de plus d'efficacité, le chapitre 5 propose une méthode dite révisée, qui consiste en une version "implémentable" de l'algorithme du simplexe. Le chapitre 6 étudie la théorie de la dualité pour finir avec un moyen d'obtention d'un certificat d'optimalité en temps polynomial. Enfin, on montre que le problème de la PL est "facile" en proposant une description succincte d'un algorithme polynomial : la méthode des ellipsoïdes. Une annexe est destinée à rappeler quelques faits utiles d'algèbre linéaire »--Quatrième de couverture
