LA PROGRAMMATION LINEAIRE : ANALYSE DE SENSIBILITE
LA PROGRAMMATION LINEAIRE : ANALYSE DE SENSIBILITE. Nous abordons dans cette leçon la partie analyse de sensibilité de la résolution d'un problème de.
LA PROGRAMMATION LINEAIRE : UN OUTIL DE MODELISATION
La programmation linéaire : un outil de modélisation. 1. LA PROGRAMMATION LINEAIRE : UN OUTIL IV Etude graphique de l'analyse de sensibilité. Problème 1.
Programmation linéaire : analyse de sensibilité- Exercices
Contraintes. Cellule. Nom. Valeur. Formule. État. Marge. $F$10. Quantité max du bien 1. 500. $F$10<=$G$10. Lié. 0. $F$11. Quantité max du bien 2.
Max z = 4 x1 + p2 x2 x1+ x2? 10 2 x1+ 6 x2? 48 3x1+ x2? 24 x1
Programmation linéaire : analyse de sensibilité/exercices/corrigé/p1. Programmation linéaire : analyse de sensibilité – Exercices -corrigé.
MODULE LOGISTIQUE
4 Chapitre 4 : Optimisation du rythme d'approvisionnement par le calcul schéma 9 - Évolution linéaire du stock ... 4.1.4 Analyse de sensibilité.
Chapitre 3 Méthode du simplexe
égal à m. Selon le chapitre précédent nous savons que la solution optimale du problème d'optimisation linéaire max z = ctx
Les choix du consommateur
Pour cela nous allons restreindre à nouveau notre analyse au cas de deux biens : Les quantités de biens x(p
FEUILLES DEXERCICES 1
Analyser les propriétés de cette demande et l'exprimer en fonction d'une dotation Montrer que si ? = 1 on retrouve le cas d'une fonction linéaire
Traitement de données avec tableur appliqué à lEconomie et la
23 févr. 2010 Le problème le plus simple d'optimisation appartient au domaine de la programmation linéaire : • la fonction objectif est une combinaison ...
Organisation et gestion de la production industrielle
111-2-]-] méthodologie p ou r J'analyse de JiJ vu Lo u r IV-6 LA PROGRAMMATION ... 1- Dans l'aménagement linéaire (ou par produits ou par ligne de.
LA PROGRAMMATION LINEAIRE : ANALYSE DE SENSIBILITE - AUNEGe
Nous abordons dans cette leçon la partie analyse de sensibilité de la résolution d'un problème de programmation linéaire Il s'agit d'étudier les conséquences d'une variation d'un coefficient de la fonction objectif et du second membre d'une contrainte
Chapitre 5 Analyse de sensibilité - Université Laval
Programmation linéaire : analyse de sensibilité – Exercices -corrigé – Reprendre l'exemple du cours et avec le solveur étudier les conséquences d'une variation du profit de l'IM5 le profit de l'IM4 restant fixé à 400€ Max z = 4 x1 + p2 x2 x1+ x2? 10 2 x1+ 6 x2? 48 3x1+ x2? 24 x1 x2 ? 0 Pour p2 = 8 on a la solution x1
Programmation linéaire : analyse de sensibilité- Exercices
Programmation linéaire : analyse de sensibilité- Exercices I – Reprendre l'exemple du cours et avec le solveur étudier les conséquences d'une variation du profit de l'IM5 le profit de l'IM4 restant fixé à 400€ II Suite de l'exercice III de la leçon "résolution analytique d'un problème de PL"
LA PROGRAMMATION LINEAIRE : RESOLUTION ANALYTIQUE - AUNEGe
La programmation linéaire : Résolution analytique 1 LA PROGRAMMATION LINEAIRE : RESOLUTION ANALYTIQUE Dans cette leçon nous abordons un algorithme de résolution d'un problème de programmation linéaire : l'algorithme du simplexe Nous le présentons d'abord sur un exemple avant d'en donner le principe général
Searches related to la programmation lineaire analyse de sensibilite aunege
2 CHAPITRE 5 ANALYSE DE SENSIBILITÉ A N est la sous-matrice formée des colonnes correspondantes aux variables de N or-donnéesselonN Exemple5 1 1 Prenonsleproblème minz= 1100x 1 1400x 2 1500x 3 8 >> < >>: x 1 + 2 3 340; 2x 1 + 3x 2 + x 3 2400; x 1 + 2 2 + 3 3 560; x 1;x 2;x 3 0: LesystèmematricielAx= baveclesvariablesd’écartsest 2 4 1
Chapitre 3
Méthode du simplexe
Comme toujours, on suppose queAune matrice de formatmnetb2Rm. On notera les colonnes deApar[a1;a2;:::;an]. Aussi, on fera l"hypothèse que le rang de la matriceAestégal à m.
Selon le chapitre précédent, nous savons que la solution optimale du problème d"optimisation
linéairemaxz=ctx; Ax=b; x0:(3.1) se trouve en un sommet de l"ensemble convexe des solutions admissiblesK=fx0jAx= bg. De plus, nous savons que les sommets sont étroitement reliés aux solutions de base admis- sibles. Concrètement, cela signifie que si on choisit une liste de m variables dites de base B=fxj1;xj2;:::;xjmgassociées à des colonnesfaj1;aj2;:::;ajmgqui forment une base de l"espace-colonne, on peut calculer l"unique solution de bases du système Ax B=b en imposant que les variables hors-basexi= 0pour tous lesi6=j1;j2;:::;jm. SixB0, lasolution est admissible et sera appellée solution de base admissible ou réalisable. D"après le
chapitre précédent, la solution de basexBcorrespond à un sommet deK. Par conséquent, il suffit de calculer tous les sommets deKpour trouver la solution optimale.Mais le nombre de sommets est de l"ordre
n!m!(nm)!ce qui est beaucoup trop pour desnetm relativement grands. Le principe de la méthode du simplexe est d"éviter de calculer tous les sommets. A partir d"un sommet donné, la méthode calculera une suite de sommets adjacents l"un par rapport au précédent et qui améliore la fonction objective.3.1 Solutions de base adjacentes
Définition
3.1.1 Deux sommetsxetysont dits adjacents si les variables de base ne
diffèrent que d"un seul élément. 12CHAPITRE 3. MÉTHODE DU SIMPLEXE
Reprenons le problème modèle du premier chapitre écrit sous la forme canonique maxz= 5x1+ 4x2 x1+x3= 6
x1=4 +x2+x4= 6
3x1+ 2x2+x5= 22
x1;x2;x3;x4;x50
Le sommetx= (4;5;2;0;0)correspond aux variables de basefx1;x2;x3g. De même, le sommety= (6;2;0;2:5;0)est associé aux variables de basefx1;x2;x4g. Les deux sommets sont adjacents ce qui est conforme au graphique de l"ensembleKprojeté dansR2.Le système s"écrit
2 6641 0 1 0 0
1=4 1 0 1 0
3 2 0 0 13
7 7526 6664x
1 x 2 x 3 x 4 x 53
7
7775=2
6 6466 223
7 75
Pour calculer la solution de base(4;5;2;0;0), il suffit d"extraire les 3 colonnes de la matriceA
et de résoudre le système carré par la méthode d"élimination de Gauss. Toutefois, lorsque que
l"on voudra calculer la nouvelle solution de base(6;2;0;2:5;0), il faudra recommencer l"éli- mination de Gauss avec les nouvelles colonnes de base. Il est plus avantageux de poursuivre élimination de Gauss à partir du premier calcul.Voici un exemple de calcul.
a)En premier, on forme la matrice augmen tée
2 6641 0 1 0 0 6
1=4 1 0 1 0 6
3 2 0 0 1 223
7 75b) On applique l"élimination de Gauss-Jordan p ourles v ariablesde base fx1;x2;x3g. 2 6
641 0 04=5 2=5 4
0 1 0 6=51=10 5
0 0 1 4=52=5 23
7 75Donc x
1= 4 + 4=5x42=5x5
x2= 56=5x4+ 1=10x5
x3= 24=5x4+ 2=5x5
En posant les variables hors-basesx4=x5= 0, on obtient bien la solution de base x= (4;5;2;0;0).3.2. MÉTHODE DU SIMPLEXE : PHASE II3
c) Main tenant,on désire calculer la solution de base adjacen tel iéesaux v ariablesd ebase fx1;x2;x4g. Pour cela, on poursuit l"élimination de Gauss-Jordan à partir du pivot a 3;42 6641 0 1 0 0 6
0 13=2 0 1=2 2
0 0 5=4 11=2 5=23
7 75:Donc x
1= 6x3
x2= 2 + 3=2x31=2x5
x4= 5=25=4x3+ 1=2x5
En posant les variables hors-basesx3=x5= 0, on obtient bien la solution de base y= (6;2;0;2:5;0). d) P oursuivonsà u nautre sommet adjacen tz= (6;0;0;4:5;4)dont les variables de base sontfx1;x4;x5g. Ce sommet est adjacent àymais pas àx. Poursuivons l"élimination de Gauss-Jordan à partir du pivota2;5 2 6641 0 1 0 0 6
0 23 0 1 4
0 11=4 1 0 9=23
7 75:On obtient les relations
x1= 6x3
x5= 42x2+ 3x3
x4= 9=2x2+ 1=4x3
En posant les variables hors-basesx2=x3= 0, on obtient bien la solution de base z= (6;0;0;4:5;4). L"opération décrite ci-dessus est aussi connue sous le nom de pivotement. Cette stratégie sera à la base de la méthode du simplexe.3.2 Méthode du simplexe : Phase II
Dans cette section, nous allons présenter la Phase II de la méthode du simplexe. La PhaseI qui sert plus à initialiser la Phase II, sera aborder plus tard. Cette phase s"applique à des
problèmes du type maxz=ptx; Cxb; x0:ouminz=ptx; Cxb; x0:(3.2)4CHAPITRE 3. MÉTHODE DU SIMPLEXE
oùCest une matrice de formatmn. On fera l"hypothèse queb0. Cette supposition est cruciale pour la Phase II. Ceci garantie que02K=fx0jCxbg. De plus, nous savons que le point0est un sommet. Ce point servira de point de départ de l"algorithme du simplexe. En gros, l"algorithme va pivoter autour de ce point pour trouver un meilleur sommet. On poursuit l"algorithme jusqu"à l"obtention de la solution optimale.La méthode débute avec la forme canonique du problème (3.2) que l"on écrira sous la forme
maxz=ctx; Ax=b; x0:(3.3) Attention, nous avons inclus les variables d"écart dans la liste des variables, i.e.x2Rm+n.La matriceAetcsont données par
A= [C I]c=p
0L"idée de base de la méthode du simplexe consiste à appliquer l"élimination de Gauss-Jordan
à partir du système augmenté obtenu en ajoutant au systèmeAx=bla relation linéaire z=ctxAx=b; c txz= 0 Ce système peut s"écrire sous la forme matricielle A0 c t1 x z =b 0Nous allons illustrer la méthode sur l"exemple
maxz=x1+ 2x2 sous les contraintes 8< :2x1+x22; x1+ 3x23;
x1;x20:
Au préalable, on écrit le problème sous la forme canonique maxz=x1+ 2x2 sous les contraintes 8< :2x1+x2+x3= 2; x1+ 3x2+x4= 3;
x1;x2;x3;x40:
Voici les étapes de la méthode du simplexe.
3.2. MÉTHODE DU SIMPLEXE : PHASE II5
0.I nitialisation
On choisit la solution de base admissible(0;0;2;3)comme point de départ de l"algo- rithme. Les variables de base sontfx3;x4get les variables hors-base sontfx1;x2g. Ce choix est toujours possible sib0.On forme le tableau initialT.
2 6642 1 1 0 0 2
1 3 0 1 0 3
1 2 0 01 03
7 751.
Choix de la colonne de piv ot
On doit aller vers un sommet adjacent pour lequel la valeur de la fonction objectivez en ce sommet est supérieure. Pour cela, on choisira la variablexiqui fera augmenter le plus rapidementz. C"est-à-dire que l"on choisit l"indiceiqui maximise@z@x i=ci>0. Dans notre cas, la fonctionzvarie plus rapidement en fonction de la variablex2. Donc, on choisit la deuxième colonne comme colonne de pivot. La variablex2entrequotesdbs_dbs22.pdfusesText_28[PDF] Analyse de sensibilité des modèles de simulation - eccorev
[PDF] IFT 1575 Modèles de recherche opérationnelle - Département d
[PDF] Méthodes d 'analyse de sensibilité de modèles pour entrées - INRA
[PDF] la distance professionnelle en ehpad
[PDF] L 'analyse de la pratique - IFSI DIJON
[PDF] Présentation de la situation - Infirmierscom
[PDF] réflexion autour de la fiche d analyse de la pratique - Infirmierscom
[PDF] Analyses de sol et interprétation des résultats
[PDF] 30 fiches pour réussir les épreuves sur textes
[PDF] l 'analyse des textes littéraires : vingt méthodes - Revue Texto
[PDF] METHODOLOGIE D 'ANALYSE D 'UN TEXTE : I/ Avant la lecture : II
[PDF] Pour un définition de l 'analyse littéraire - Lettresorg
[PDF] Demain dès l 'aube » de Victor Hugo Fiche du professeur - Xtec
[PDF] Cours de Démographie- Hassen MATHLOUTHI - essai