Oodoc change de nom : découvrez tousLesDocs

X

Accéder à ce doc

Le sommaire
  ACCÉDER à ce doc

I) Introduction : un exemple de problème d'allocation de ressources

II) Formalisation du P.L. - Terminologie

III) Modélisation : exemples de modélisation et applications

A. L'entreprise CRM
B. Modélisation : variables de décision à double indice
C. Un problème de mélange
D. Choix d'une fonction objectif : le papetier
E. Utilisation de variables binaires : le chemin le plus court dans un réseau orienté
F. Le parcours des éboueurs

IV) Résolution graphique d'un modèle linéaire continu

A. Un exemple : la fonderie
B. Construction de la région admissible
C. Recherche de la solution optimale
D. Typologie des régions admissibles
E. Typologie des solutions admissibles
F. Caractéristiques des solutions optimales

V) L'algorithme du simplexe

A. Variables d'écart et variables d'excédent
B. Solutions de base admissibles
C. Résolution du modèle par pivotage
D. La méthode du rectangle

Conclusion : les étapes de l'algorithme du simplexe
Annexe : tableau
ACCÉDER à ce doc  

Résumé du document
  ACCÉDER à ce doc

Lorsque les variables du modèle sont astreintes aux valeurs entières, on aura un programme linéaire en nombres entiers (PLNE), lorsque chaque variable de décision peut prendre toutes les valeurs d'un intervalle, on aura un programme linéaire continu.
Une solution (xa, xo) est dite admissible si elle satisfait toutes les contraintes, inadmissible dans le cas contraire. Une solution admissible est dite optimale lorsque la valeur que prend alors la fonction objectif z est optimale ()

Extraits

[...] Les tronçons suivants deviennent à sens unique et ne peuvent plus être parcourus que dans le sens : 6 7 ; 5 4 ; 8 7. Cela se traduit par l’introduction des nouvelles contraintes dans le modèle : ; ; Les tronçons 4 5 et 3 8 doivent être parcourus deux fois, une dans chaque sens . Il suffit d’ajouter au modèle les contraintes suivantes : ; et ; Ce qui rend les contraintes et redondantes, on dit aussi qu’elles sont dominées par les contraintes ajoutées. [...]


[...] Nous allons définir ces deux termes : Considérons la droite associée à la contrainte d’équation . Cette droite divise le plan en 2 parties dénommées demi-plans ou, plus généralement, demi-espaces. En 2 dimensions, la frontière d’un demi-espace est une droite. En 3 dimensions, la frontière d’un demi-espace est un plan . En n dimensions, la frontière d’un demi-espace est appelée un hyperplan Un demi-espace est dit fermé ou ouvert selon que sa frontière en fait partie ou non : s’il est fermé, il contient sa frontière. [...]


[...] sous les contraintes ; ; j = .,n 0 ; j = .,n C’est la forme dite canonique d’un programme linéaire, qui est un cas particulier, une forme simplifiée du modèle linéaire général (noté diffèrent de la forme simplifiée en deux principaux points : - Dans le modèle linéaire général (noté l’optimisation n’est pas forcément un problème de maximisation, - Les contraintes technologiques peuvent être du type , = ou La fonction linéaire à optimiser est appelée fonction objectif (parfois fonction objet). Dans le modèle il s’agit d’un problème de maximisation. Les variables sont appelées variables de décision du problème : Le modèle (PLS) comporte n variables de décision, qui sont toutes non- négatives. Le modèle comporte m+n contraintes : Les m premières sont qualifiées de contraintes technologiques. [...]


[...] Partant d’un sommet initial, l’algorithme effectue une opération itérative, dite pivotage, qui correspond à passer d’un sommet à un autre adjacent, plus rentable Nous limitant dans un 1er temps aux modèles de type dont le point de départ reste l’origine nous adapterons ensuite l’algorithme à un modèle linéaire quelconque. 1ère ITERATION ETAPE A : Mise en évidence d’une solution de base admissible initiale. Construction du tableau initial Nous avons obtenu le modèle : S.C. = 200 (1’) = 60 (2’) = 34 (3’) = 14 (4’) (5’) Les points extrêmes de (PLS) correspondent aux solutions de base admissibles de obtenues en annulant 2 des 6 variables de (PLS=). [...]


[...] = 18 = 34 = La dernière ligne du tableau correspond à la fonction objectif ; l’avant dernière ligne s’écrit en fonction de la première et de la dernière. 2ème ITERATION Un des coefficients de la dernière ligne du tableau étant positif, le sommet A auquel nous avons aboutit n’est pas optimal . Choix de la variable entrante : 13 9 34 n’est pas limité par la 4ème contrainte Choix de la variable sortante : Le pivot , ici égal à se situe à l’intersection de : - la colonne de la variable entrante : - la ligne de la variable sortante : Construction du 3ème tableau - les variables de base : - les variables hors base : Pour écrire le 3ème tableau, on doit exprimer notre modèle en fonction des variables hors base, ce qui revient à remplacer la variable entrante par son expression en fonction des variables hors base, ici et , utilisant pour cela la ligne où se trouve le pivot, que je dois transformer de manière à ce que le pivot soit égal à ce qui revient ici à diviser la ligne par valeur du pivot. [...]

ACCÉDER à ce doc  

Informations sur le doc

Date de publication
28/09/2009
Langue
français
Format
Word
Type
cours
Nombre de pages
27 pages
Niveau
grand public
Consulté
7 fois

Informations sur l'auteur Nicolas O. (étudiant)

Niveau
Grand public
Etude suivie
droit des...
Note du document :
         
ACCÉDER à ce doc  
La programmation linéaire

«Lorsque les variables du modèle sont astreintes aux valeurs entières, on aura un programme linéaire en nombres entiers (PLNE), lorsque chaque variable de décision peut prendre toutes les valeurs d'un intervalle, on aura un...»

Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .doc  |   27 pages  |   publié en 2009
Programmation linéaire multi-objectif (multicritère)

«La programmation linéaire est un outil simple et puissant de la Recherche Opérationnelle. Elle permet d'analyser plusieurs situations économiques dans lesquelles les variables de décisions ainsi que les paramètres c...»

Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .doc  |   5 pages  |   publié en 2009
Cours de Recherche opérationnelle (niveau Licence)

«1. Introduction La programmation mathématique est une technique de la Recherche Opérationnelle (RO). Il est ainsi bon de préciser d'abord, même en peu de mots, ce qu'on entend par la RO. Il s'agit d'une discipli...»

Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   53 pages  |   publié en 2011
Finance d'entreprise et équilibre microéconomique de la firme

«Si la satisfaction du consommateur est la finalité de l'économie, l'entreprise (ou firme) est à la source du système économique, puisqu'elle produit et distribue des biens et services en utilisant des facteurs de pr...»

Économie et Social   |  Économie générale  |   Dissertation  |   fr  |   .pdf  |   42 pages  |   publié en 2010
Etude d'Android, SDK de Google pour les téléphones, et réalisation d'une application de résolution d'équation

«Ce rapport a pour but de retracer l'évolution de mon projet pour le module de master 1 « Système d'aide à la décision » (SAD), depuis le choix du sujet jusqu'à la clôture du projet.Ainsi, les...»

Sciences et technologies   |  Informatique  |   Dissertation  |   fr  |   .pdf  |   36 pages  |   publié en 2008

Meilleures ventes en mathématiques

Derniers docs en mathématiques

Cours complet de mathématiques supérieures
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   271 pages  |   publié en 2007
Les mathématiques financières
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .doc  |   47 pages  |   publié en 2008
Fiches de remise à niveau en Mathématiques (CRPE)
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .doc  |   52 pages  |   publié en 2008
Le choix en univers aléatoire : analyse Bayesienne élémentaire
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   6 pages  |   publié en 2014
Fiche-méthode en Topologie
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   5 pages  |   publié en 2013
Analyse factorielle multiple
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   28 pages  |   publié en 2012
Probabilités et statistique
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .zip  |   58 pages  |   publié en 2012
Fiche de révision pour le Baccalauréat de Mathématiques
Sciences et technologies   |  Mathématiques  |   Cours  |   fr  |   .pdf  |   6 pages  |   publié en 2012