Programmation linéaire

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