La programmation linéaire constitue l'origine de l'optimisation mathématique moderne linéaire, l'algorithme du simplexe révisé, les notions de dualité, et
| Previous PDF | Next PDF |
[PDF] TD 5 Programmation linéaire et optimisation Dualité Exercice 1 - grug
Corrigé: Exercice 2 Dans le cas d'un problème de programmation linéaire ( minimisation) possédant une solution optimale finie, l'algorithme primal du simplexe
[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
La programmation linéaire constitue l'origine de l'optimisation mathématique moderne linéaire, l'algorithme du simplexe révisé, les notions de dualité, et
[PDF] Exercices de Programmation Linéaire – Modélisation –
exercice 1 : Résoudre le programme linéaire suivant par la méthode du simplexe Dualité – exercice 1 : Écrire le dual du programme linéaire suivant :
[PDF] Série 1: Programmation linéaire
Série 1: Programmation linéaire Formulation mathématique-résolution graphique Pour chaque exercice, formuler le probl`eme de programmation linéaire et le
[PDF] 1 Programmation linéaire
Master d'économie Cours de M Desgraupes Méthodes Numériques Document 4 : Corrigé des exercices d'optimisation linéaire 1 Programmation linéaire 1
[PDF] Exercices corrigés PROGRAMMATION LINÉAIRE
Optimisation discrète, Séance 5 : Exercices corrigés Quest 1 £ On a là un problème d'optimisation (linéaire)sous contraintes (linéaires) : ¤¦¥¨§ © #" $ ' ) (1 327/5 Phi Programmation linéaire et dualité Dualité Primal (P) Dual (D) S
[PDF] Programmation linéaire et recherche opérationnelle Recherche
maximiser le profit obtenu apr`es deux ans? 3/56 Introduction Méthode graphique Simplexe Dualité Des probl
[PDF] Dualité en Programmation Linéaire Algorithmes primal et - ENSIIE
Dualité et programmation linéaire 13 min ≥0 3- En déduire que le dual lagrangien de (P) est le problème (D) Exercice (th de dualité faible) Exercice
[PDF] Programmation linéaire - JavMathch
Vérifier ensuite que vous obtenez bien la même solution optimale avec la méthode graphique Exercice 6 3: Une entreprise envisage de fabriquer deux produits :
[PDF] Éléments de Cours, exercices et problèmes corrigés - Institut de
3 2 Dualité en programmation linéaire 3 2 1 Le théorème de dualité et quelques conséquences 49 Partie II Exercices et problèmes corrigés 7
[PDF] aide embauche pme heures supplémentaires
[PDF] structure par âge de la population mondiale
[PDF] prolongation aide embauche pme 2017
[PDF] structure démographique définition
[PDF] aide embauche pme batiment
[PDF] composition de la population mondiale
[PDF] aide embauche pme renouvellement cdd
[PDF] structure par age definition
[PDF] cumul aide embauche pme
[PDF] rsa socle et prime d'activité cumulable
[PDF] rsa et reprise d'activité 2017
[PDF] cumul rsa et salaire 2017
[PDF] cumul intégral rsa
[PDF] cumul rsa et salaire pendant 3 mois
174EXERCICES SUPPLÉMENTAIRES - PARTIE
IIPartieIII
Optimisation di
fférentiable avec
contraintes linéaires 175177
Le traitement des contraintes est simpli
fié si elles sont supposées linéa
ires. Les contraintes linéaires, d'égalité et/ou d'inégalité décrivent des ensemble convexes . La théorie de l'optimi- sation sous contraintes linéaires s'a ppuie sur l'algèbre linéaire et l'an alyse convexe.L'ère moderne d'optimisation mathématiq
ue origine des travaux de George Be rnard Dant- zig sur la programmation linéaire à la fi n des années 1940. Le chapitre 4 en présente les résultats principaux.Parmi les premiers développement, plusieurs travaux ont consisté à modéliser une fonction
objectif non linéaire en conservant la structure de contraintes linéair es. 178Chapitre4
Programmation linéaire
Sujets du chapitre
Observations sur la géométrie du problème.Condition d'optimalité.
Déduction de l'algorithme du simplexe.
Théorie de la dualité linéaire.
Dégénérescence.
Aspects numériques.
179180CHAPITRE 4. PROGRAMMATION LINÉAIRE
Introduction
La programmation linéaire constitue l'origine
de l'optimisation mathématique moderne.Son étude a été menée par Geo
rge Bernard Dantzig à partir de 1947 . L'algorithme du sim- plexe, que nous présentons dans ce chapitre, est considéré comme un des dix algorithmes les plus importants du vingtième siècle.C'est la première fois qu'un prob
lème avec contraintes d'inégalité a été résolu.Dans ce chapitre, nous abordons l'ét
ude directe des problèmes de minimisation de fonc tions linéaires dans un domaine dé fi ni par des contraintes linéaires. Par une suite d'observa-tions de nature géométriques ou encore algébriques, nous déduirons les conditions d'optima-
lité de la programmation linéaire, l'a lgorithme du simplexe révisé, les notions de dualité, et les variantes duales et primales-duales de l'algorithme du simplexe.4.1 Formulation du problème
Pour simpli
fi er l'exposé, nous considérons que le problème est formulé sous la forme dite standard , c'est-à-dire min cx sujet à Ax b x0,(4.1)
où c et x sont des vecteurs de R n b un vecteur de R m et A une matrice m n . Les lignes de la matrice A sont notées a i ,i 1 2 ,...,m alors que ses colonnes sont notée s A j ,j 1 2 ,...,n . De plus, nous faisons l'hypothès e que la matrice A est de rang m , c'est-à-dire que ses lignes sont linéairement indépendantes. Ainsi, les contraintes dé fi nissent l'intersection d'un sous-espace de R n de dimension n m avec l'orthant positif. Le vecteur c constitue le gradient de la fonction linéaire cx , et donc est un vecteur-ligne. Nous verrons plus tard que l'hypothèse que les lignes de A sont linéairement indépen- dantes n'est pas très restrictive.4.2 Solutions de base réalisables
Attardons-nous un instant sur la struc
ture du domaine réalisable, cette interse ction d'un sous-espace avec l'orthant positif. Plus particulièrement, essayons de caractériser les points d'intersection avec la frontière de l'orthant. Dans R 3 , par exemple, s'il n'y a qu'une seule contrainte (en plus des bornes qui dé fi nissent l'orthant), le domaine réali sable est l'intersec- tion d'un plan avec l'orthant. Selon la position de ce plan, l'i ntersection peut être vide, ou encore constituée seulement de l'origine, ou encore d'un demi-axe, ou d'un cône, ou fi nale- ment d'un triangle. Dans tous les cas où le domaine réalisable n'est pas vide, au moins un4.2. SOLUTIONS DE BASE RÉALISABLES181
point de la partie positive des axes canoniques en fait partie. C'es t une propriété importante. Nous verrons qu'un tel point appartenant à un axe canonique est un point extrême du do- maine réalisable, correspondant à ce que nous nommerons une solution de base . Complétons notre observation de R 3 en examinant l'intersection d'un sous -espace de dimension deux (une droite) avec l'orthant. Dans ce cas, si l'intersection n'est pa s vide, elle est constituée de l'origine, ou encore d'une demi-droit e, ou encore d'un segment de droite.Dans ce cas,
les points extrêmes appartiennent à un plan canonique (extrémités de la demi-droite ou du
segment). Ces illustrations géométriques sont à la base de la caractérisation des so lutions de base en programmation linéaire. En e ff et, en supposant que le domaine n'est pas vide, un sous-espace de R n de dimension n m intersecte au moins un hyperplan canonique de dimension m . Dans l'exemple de R 3 , le plan intersecte au moins un axe canonique (hyperplan de dimension un) alors que la droite intersecte au moi ns un des plans canoniques ( xy yz ou zx ). Supposons donc que les composantes d'un vecteur de R n sont ordonnées de telle sorte que l'hyperplan canonique qui contient un tel poi nt d'intersection est formé des m premières composantes.