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.
Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY
Correction page 42. 1.6 Programmation linéaire : le simplexe. Exercice 1.6.1 (Une histoire de fromage). Une laiterie s'
Programmation linéaire Jean-Philippe Javet
Exercice 2.6: Un corrigé peut être vu à votre demande. Exercice 2.7: Indications : ‚ Proposer dans un premier temps un raisonnement
Corrigé : Programmation linéaire II
Corrigé : Programmation linéaire II. Exercice 1. Au quatorzième siècle un Touareg compte gagner un peu d'or en investissant dans des.
Devoir de vacances de Programmation Linéaire
Les exercices se rapportent tous au programme linéaire (P) Néanmoins ils sont Exercice 1 Forme canonique forme standard et dual (2 points).
Programmation Linéaire Cours 1 : programmes linéaires
Programmation Linéaire. Cours 1 : programmes linéaires modélisation et résolution graphique. F. Clautiaux francois.clautiaux@math.u-bordeaux1.fr.
La Programmation Linéaire : Cours Exercices corrigés et Etude de
20-Nov-2016 est-ce une solution de base ? Exo. 15.6 ? Algorithme du simplexe pour un PL `a 2 variables. Résoudre le programme linéaire suivant avec l' ...
Programmation linéaire
Programmation linéaire. 1. Le problème un exemple. 2. Le cas b = 0. 3. Théorème de dualité. 4. L'algorithme du simplexe. 5. Problèmes équivalents.
Unité D Programmation linéaire Corrigé
Exercice 1 : Problèmes préliminaires - corrigé. Ces problèmes ont été conçus pour être effectués par les élève à l'aide de feuilles de calcul. Ils.
Programmation linéaire en nombres entiers : la méthode du simplexe
Programme linéaire entier facile : Un PLE qui en oubliant les contraintes d'intégrité
Unité D Programmation linéaire Corrigé - Province of Manitoba
Exercice 5 : Résolution de problèmes de programmation linéaire - corrigé Note à l’enseignant : La dernière partie de chaque problème permet à l’élève de découvrir que la meilleure solution se situe au sommet de la région des solutions réalisables 1 a) x + y 100 b) 10x + 30y 1 500 c)
Programmation Lin aire Cours 1 - u-bordeauxfr
180 CHAPITRE 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 George 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
Programmation linéaire
la programmation linéaire Nous étudierons 3 méthodes pour résoudre les di?érents types de problèmes de programmation linéaire; la première est basée sur une résolution graphique elle est donc limitée à 2 ou 3 variables
Searches related to programmation linéaire exercices corrigés pdf PDF
Chapitre : PROGRAMMATION LINÉAIRE 1ere ES Exercice2 Un artisan fabrique des objets A et des objets B La réalisation d’un objet A demande 30ede matière première et 125 de main-d’œuvre La réalisation d’un objet B demande 70ede matière première et 75 de main-d’œuvre
Qu'est-ce que la programmation lin'eaire?
Introduction a la programmation lin´eaire Un outil qui permet de : •mod´eliser •r´esoudre toute une classe de probl`emes d’optimisation. Existence de solveurs e?cace pour la PL
Quels sont les exercices de programmation linéaire ?
I Exercices de programmation linéaire (1, 2, 3, 4, 5.1 et 5.2) sont dans l’objectif minimum…. 1 Résoudre par la méthode graphique : Max [CA] : 4 xa + 6 xb (1) 6 xa + 5 xb ? 30 (2) 3 xa + 9 xb ? 27 (3) xa ? 5 (4) xb ? 4
Comment résoudre les problèmes de programmation linéaire ?
Re?soudre les proble?mes de programmation line?aire suivants a? l’aide de l’algorithme du simplexe (en introduisant si ne?cessaire des variables artificielles). Max z = 2x ?y s.c. x +y ? 2 y ? 2 x +y ? 4 x, y ? 0 9.2.
Quels sont les avantages de la programmation linéaire?
Ainsi qu`en deuxième lieu (S. HOUNDEDAKO et al, 2014)à utiliser le système HVDC (courant continu à haute tension) pour la synchronisation entre deux réseaux différents aussi que le transport de l`énergie électrique. De ce qui précède la programmation linéaire, nous permet de développer un système pour la transmission et le stockage de
Université Paris 13Institut GaliléeINFO2 - MI1 Année 2011-2012
Devoir de vacances de Programmation Linéaire
(Correction)À faire pour le 03 Janvier 2012
Soit le programme linéaire :
(P)max6x1+ 4x2 s.c4x1+ 5x215 (1) 12x1+x21 (2)
4x1+x212 (3)
2x1+x22 (4)
x1, x20
Les exercices se rapportent tous au programme linéaire(P)Néanmoins ils sont indépendants et peuvent être traités dans n"importe quel ordre.Exercice 1
Forme canonique, forme standard et dual(2 points)
1. Mettre le programme linéaire sous forme canonique.
2. Mettre le programme linéaire sous forme standard.
3. Donner le dual(D)du programme linéaire(P).
1. Sous forme canonique :
(Pc)max6x1+ 4x2 s.c4x1+ 5x215 12x1?x2 ?1
4x1+x212
?2x1?x2 ?2 x1, x20
2. Sous forme standard :
(Ps)max6x1+ 4x2 s.c4x1+ 5x2+x3= 15 12x1?x2+x4=?1
4x1+x2+x5= 12
?2x1?x2+x6=?2 x1, x2, x3, x4, x5, x60
3. Le dual(D)de(P).
(D)min15y1+y2+ 12y3+ 2y4 s.c4y1+12y2+ 4y3+ 2y46
5y1+y2+y3+y44
y1, y3,0
y2, y40
ou (D)min15y1?y2+ 12y3?2y4 s.c4y1?12y2+ 4y3?2y46
5y1?y2+y3?y44
y1, y2, y3, y40
Exercice 2
Résolution graphique(3 points)
Faire la résolution graphique du programme linéaire(P)pour déterminer sa solution optimale et sa valeurv(P). x= (4516,34)1 2 33
4 2 1 5¯x˜x
2x1+x22 (4)1
2x1+x21 (2)4x1+ 5x215 (1)
04 x 1x 24x1+x212 (3)
obj x: intersection entre (1) et (3)4x1+ 5x2= 15
4x1+x2= 12
x1=??????
15 512 1??????
?4 54 1??????=4516=4516etx2=??????
4 151216=34
d"oùx= (4516,34)pour une valeur de1598.
Exercice 3
Solutions de base et algorithme primal du simplexe sous forme tableau (8 points) Soientx3,x4,x5etx6les variables d"écart associées aux contraintes (1), (2), (3) et (4).1.Expliciter la solution de base˜xdéfinie par˜x1= 0et˜x2= 1(i.e. donner les valeurs de
¯x3,¯x4,¯x5et¯x6). À quelle base cette solution correspond-t-elle ?4 contraintes4 variables en base parmi 6.
C46= 15solutions de base potentielles.
˜xvérifie à l"égalité la contrainte12x1+x21donc˜x4= 0.
˜xcorrespond à la solution de base associée àx1=x4= 0 c"est-à-dire l"intersection entre les contraintesx1= 0etx4= 0. Cette solution correspond à la baseB=x2,x3,x5,x6.˜xdoit vérifier toutes les contraintes ?
On peut donc se servir de cette propriété pour trouver la valeur de˜x3,˜x5et˜x6.4˜x1+ 5˜x2+ ˜x3= 15˜x3= 15?5 = 10
4˜x1+ ˜x2+ ˜x5= 12˜x5= 12?1 = 11
?2˜x1?˜x2+ ˜x6=?2˜x6=?2 + 1 =?1 donc˜x= (0,1,10,0,11,?1).2.˜xest-elle une solution de base réalisable ?
Réalisabilité de˜x?
˜x1= ˜x4= 00
˜x2= 10
˜x3= 100
˜x5= 110
mais˜x6=?1<0
donc˜xn"est pas réalisable.3.˜xest-elle une solution de base optimale ?
Non réalisable donc non optimale.
4.Expliciter la solution de base¯xdéfinie par¯x1= 2et¯x2= 0(i.e. donner les valeurs de
¯x3,¯x4,¯x5et¯x6). À quelle base cette solution correspond-t-elle ?4 contraintes4 variables en base parmi 6.
C46= 15solutions de base potentielles.
¯xvérifie à l"égalité la contrainte12x1+x21donc¯x4= 0.
¯xcorrespond à la solution de base associée àx2=x4= 0 c"est-à-dire l"intersection entre les contraintesx2= 0etx4= 0. Cette solution correspond à la baseB=x1,x3,x5,x6.¯xdoit vérifier toutes les contraintes ?
On peut donc se servir de cette propriété pour trouver la valeur de¯x3,¯x5et¯x6.4¯x1+ 5¯x2+ ¯x3= 15¯x3= 15?8 = 7
4¯x1+ ¯x2+ ¯x5= 12¯x5= 12?8 = 4
?2¯x1?¯x2+ ¯x6=?2¯x6=?2 + 4 = 2 donc¯x= (2,0,7,0,4,2).5.¯xest-elle une solution de base réalisable ?
Réalisabilité de¯x?
¯x2= ¯x4= 00
¯x1= 20
¯x3= 70
¯x5= 40
¯x6= 20
¯x1,¯x3,¯x5,¯x60donc¯xest réalisable.6.¯xest-elle une solution de base optimale ?
Optimalité de¯x?
¯xcorrespond à la base¯B=x1,x3,x5,x6.
(on noteBà la place de¯Bpar abus de langage). Il faut calculer les coûts réduits des variables hors base cN?cB˜B1˜N
B=4 1 0 0
120 0 0
4 0 1 0
?2 0 0 1 , det˜B=121 0 00 1 00 0 112= 0, com˜B=0
1 20 0 ?1 4 4?2 0 0 1 20 0 0 0 1 2˜B1=0?2 0 0
1 8 0 0
0 8 1 0
0?4 0 1
N=5 0 ?1 1 1 0 ?1 0˜B1˜N=2?2
?3 8 ?7 8 3?4 c B=6 0 0 0
etcN= 4 0 cN?cB˜B1˜N=
4 0 12?12 ?8 12¯cx4>0
donc¯xn"est pas optimale.7.Donner une représentation du programme linéaire sous formetableau associée à l"une des
bases précédentes. xBxN˜B1bI˜B1˜N
?cB˜B1b0cN?cB˜B1˜N˜B1=0?2 0 0
1 8 0 0
0 8 1 0
0?4 0 1
b=15 ?1 12 ?2˜B1b=2742
c B=6 0 0 0
cBB1b= 12
Base¯bx1x3x5x6x2x4
x121 0 0 02?2 x370 1 0 0?3 8 x540 0 1 0?7 8 x620 0 0 13?4 ?¯z¯c?120 0 0 0?8 128.Trouver la solution de base optimale. Pour ce faire, appliquer l"algorithme primal du
simplexe en utilisant la forme tableau à partir de la base de la question précédente.Base¯bx1x2x3x4x5x6
x121 2 0?2 0 0 x370?3 1 8 0 0 x540?7 081 0 x620 3 0?4 0 1 ?¯z¯c?120?8 0 12 0 012>0doncx4entre en base.
7848doncx5sort de base.
Base¯bx1x2x3x4x5x6
x131 1/4 0 0 1/4 0 x33041 0?1 0 x41/20?7/8 0 1 1/8 0 x640?1/2 0 0 1/2 1 ?¯z¯c?180 5/2 0 0?3/2 0 52>0doncx2entre en base.
3 1434doncx3sort de base.
Base¯bx1x2x3x4x5x6
x145/161 0?1/16 0 5/16 0 x23/40 1 1/4 0?1/4 0 x437/320 0 7/32 1?3/32 0 x635/80 0 1/8 0 3/8 1 ?¯z¯c?159/80 0?5/8 0?7/8 0 tous les¯cN<0donc optimalité. x = (4516,34,0,3732,0,358)etz=1598. (cohérent avec exercice 2)
Exercice 4
Forme révisée de l"algorithme primal du simplexe(3 points) Appliquer l"algorithme du simplexe sous forme révisée pourrésoudre le programme linéaire (P). Soientx3,x4,x5etx6les variables d"écart associées aux contraintes (1), (2), (3) et (4). UtiliserB=x1,x3,x5,x6comme base réalisable de départ.Sous forme standard :
(Ps)max6x1+ 4x2 s.c4x1+ 5x2+x3= 15 12x1?x2+x4=?1
4x1+x2+x5= 12
?2x1?x2+x6=?2quotesdbs_dbs33.pdfusesText_39[PDF] programmation linéaire simplexe
[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf
[PDF] exercices recherche operationnelle
[PDF] theme astral chinois complet gratuit interpretation
[PDF] cours recherche opérationnelle methode de simplexe
[PDF] recherche opérationnelle simplexe exercices corrigés
[PDF] livre recherche opérationnelle pdf
[PDF] cours et exercices corrigés de recherche opérationnelle+pdf
[PDF] inpes
[PDF] methode boscher pdf download
[PDF] méthode boscher cahier de lecture pdf
[PDF] methode boscher en ligne
[PDF] méthode boscher gratuit
[PDF] méthode boscher cahier des sons pdf
