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.
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
Introduction à la programmation linéaire/exercices/corrigé/p1
Introduction à la programmation linéaire– Exercices -corrigé. I Dans un élevage de porcs on souhaite déterminer les quantités de différents.
- Exercices de TD - 1 Modélisation.
Traduire par un programme linéaire en forme canonique. b. Résoudre le probl`eme par une méthode graphique. c. Maximiser le gain de l'année par la méthode du
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.
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' ...
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.
Chapirte1 : Formulation dun programme linéaire (Modélisation) : 1
Question : Déterminer la fonction objective les contraintes structurelles et les contraintes de positivité. Exercice 2 : une entreprise dispose de 200Kgs de
Programmation linéaire T.D. N° 3 Simplexe forme Tableau Exercice
Simplexe forme Tableau Exercice corrigés. Exercice N° 1 : Soit le problème de Programmation linéaire suivant : Max Z = 3x1 + 2x2.
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).
Unité D Programmation linéaire Corrigé - Province of Manitoba
Exercice 5 : Résolution de problèmes de programmation linéaire - corrigé (suite) 3 a) 4x + 3y 120 b) 3x + y 60 c) d) Les solutions comprennent tous les points de la zone ombragée e) La meilleure solution se situe au point d’intersectoin des deux droites 4 a) 15x + 05y 30 b) x + 2y 70 c) d) Les solutions comprennent tous les points
174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
sation sous contraintes linéaires s’appuie sur l’algèbre linéaire et l’analyse convexe L’èremoderned’optimisationmathématiqueoriginedestravauxdeGeorgeBernardDant-zig sur la programmation linéaire à la ?n des années 1940 Le chapitre 4 en présente les résultats principaux
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
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
Qu'est-ce que la programmation linéaire ?
La programmation linéaire est une méthode de résolution d’une fonction économique (maximisation d’un profit ou minimisation d’un coût) compte tenu d’un ensemble de contraintes linéaires de marché, de stockage, de production, etc. et ne comportant pas plus de deux variables.
Quels sont les exercices corrigés de modélisation linéaire ?
Ci-dessus des exercices corrigés de modélisation linéaire. Une entreprise fabrique deux produits A et B, en utilisant une machine m et deux matières premières p et q. On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q. On suppose que :
Quels sont les exercices linéaires?
Les fonctions linéaires : orientation sciences et finances, le but des exercices est de réaliser la représentation graphique une fonction linéaire à partir d'une problématique. OEF Evalwims Proportionnalité cinquième, collection d'exercices sur la proportionnalité. OEF Initiation au tableur., exercices sur l'utilisation de base d'un tableur.
![La Programmation Linéaire : Cours Exercices corrigés et Etude de La Programmation Linéaire : Cours Exercices corrigés et Etude de](https://pdfprof.com/Listes/18/5659-18la-programmation-lineaire-cours-exercices-corriges-et-etude-de_pdf.pdf.jpg)
La Programmation Lineaire :
Cours, Exercices corriges et Etude de cas
Adil Bellabdaoui
adil.bellabdaoui@um5.ac.ma www.decision.ma/ensias/20 novembre 2016
2 96Chapitre 9
Methode de simplexe
9.1 SERIE 15 :
Exo. 15.1?forme d'un programme lineaire
Montrez que chaque programme lineaire en forme standart s'ecrit en forme ca- nonique et inversement.Exo. 15.2Solutions de base admissible
1. Soit le polygone suivant, deni par l'ensemble des points x tels que :
x 1+x25 x 2+x34 x 33x
1; x2; x30
La solution de base associee a la base (x1;x2;x3) est-elle admissible?Exo. 15.3
1. Soit le polygone suivant, deni par l'ensemble des points x tels que :
x+2y2 y3 x; y0 La solution de base associee a la base (x1;x2) est-elle admissible?2. Lister toutes les solutions de base admissibles du programme lineaire precedent.
Laquelle est optimale pour la fonction objectif maxx1+x2? Et pour la fonction objectif minx1+x2?Exo. 15.4Enumeration de solutions de base
Soit le programme lineaire suivant :
Maxz= 2x+3y
s:c:3x+2y184x+3y24
x; y01.Ecrire ce PL sous forme standard.
9798CHAPITRE 9. METHODE DE SIMPLEXE
2.Enumerer toutes les solutions de base en indiquant, pour chaque solution,
les variables qui sont dans la base, celles qui sont hors base, et si la solution est realisable ou non. On determinera egalement, pour chaque solution de base realisable, la valeur de la fonction objectif.3.Quelle solution optimise la fonction objectif?
4.Tracer les contraintes et determiner la region des solutions realisables. Indi-
quer sur le graphique ou sont situees les solutions de base.Exo. 15.5Solutions de base d'un PL
Soit le programme lineaire suivant en forme standard :Maxz= 5x1+3x2+4x3
s:c:4x1+2x2+4x3+x4= 802x1+2x2+3x3+x5= 50
x1+3x2+2x3+x6= 40
x1; x2; x3; x4; x5; x60
La solution S = (19; 2; 0; 0; 8; 15) est-elle admissible? est-ce une solution de base? Exo. 15.6?Algorithme du simplexe pour un PL a 2 variables Resoudre le programme lineaire suivant avec l'algorithme du simplexe :Maxz= 36x+24y
s:c:3x16 x+y27 2x10 x; y0 A chaque iteration, on fera entrer en base la variable candidate de plus grand co^ut reduit. Verier ensuite graphiquement.Exo. 15.7Algorithme du simplexe (cas favorable)
Soit le programme lineaire (P) suivant :
Maxz=x+2y
s:c: xy1 yx1 x; y01.Resoudre (P) a l'aide de l'algorithme du simplexe : a chaque iteration, on
fera entrer en base la variable candidate de plus petit indice.2.Resoudre (P) a l'aide de l'algorithme du simplexe : a chaque iteration, on
fera entrer en base la variable candidate de plus grand co^ut reduit.3.Verier ensuite graphiquement.
Exo. 15.8Algorithme du simplexe (cas favorable)
Resoudre le programme lineaire suivant avec l'algorithme du simplexe :9.1. S
ERIE 15 :99
Minz=4x112x2+3x3
s:c: x11000 x 2500x
3 1500
3x1+6x22x36750
x10; x20; x30
A chaque iteration, on fera entrer en base la variable candidate de plus grand co^ut reduit.Exo. 15.9
Soit le programme lineaire suivant a resoudre :Maxz= 5x1+4x2+3x3 s:c:2x1+3x2+3x354x1+x2+2x311
3x1+4x2+2x38
x1; x2; x30
1.Ecrivez le programme sous forme canonique.
2.Donnez une solution triviale realisable du probleme.
3.Trouvez une solution meilleure que la precedente si cela est possible.
4.Trouvez une solution optimale.
Exo. 15.10
Trois machinesM1,M2,M3peuvent produire chacune deux types de piecesP1 etP2. Le temps de fabrication d'une piece Pi sur la machineMjest reporte dans le tableau suivant (temps en heures) :M 1M 2M3Piece 1344
Piece 2465
On veut fabriquer au moindre co^ut 6 piecesP1et 8 piecesP2. La machineM1 est disponible 14 heures, les deux autres machines sont disponibles 24 heures. Le co^ut horaire deM1est 7, celui deM2est 5 et celui deM3, 6.1.Ecrire le programme lineaire associe.
2.Resoudre ce probleme en enumerant toutes les solutions entieres possibles.
100CHAPITRE 9. METHODE DE SIMPLEXE
9.2 SERIE 16 :
Exo. 16.9Algorithme du simplexe (methode des 2 phases Resoudre le programme lineaire suivant avec la methode des 2 phases de l'algo- rithme du simplexe :Maxz=x+2y
s:c: x1 x+y6 x+y= 3 x; y0 Verer ensuite en resolvant directement le PL algebriquement (sans simplexe ni resolution graphique). Que se passe-t-il si on cherche a mimimiser la fonction objectif?Exo. 16.10?
Resoudre les problemes de programmation lineaire suivants a l'aide de l'algo- rithme du simplexe. Eectuer l'interpretation graphique du deroulement du sim- plexe.Maxz= 3=2x+y
s:c:2xy4 x+y1 x+2y42x+y12
x; y0Maxz= 2x+y
s:c:2xy4 x+y1 x+2y42x+y12
x; y0Maxz=x+2y
s:c:2xy4 x+y1 x+2y42x+y12
x; y0Exo. 11.2??
Resoudre les problemes de programmation lineaire suivants a l'aide de l'algo- rithme du simplexe (en introduisant si necessaire des variables articielles).Maxz= 2xy
s:c: x+y2 y2 x+y4 x; y09.2. S
ERIE 16 :101
Maxw=x+y+z
s:c: x+y+2z= 5 xy= 1 y+z= 2 x; y; z0Minw=x+y+z
s:c: x+y+2z5 x+y 1 y+z2 x; y0102CHAPITRE 9. METHODE DE SIMPLEXE
9.3 SERIE 17 :
Exo.??
Resoudre sans utiliser de variable articielles le probleme suivant :Maxw=2x3y
s:c:2x+yz43xy+5z5
x; y; z0 En deduire la solution optimale du probleme dual associe.Exo. 11.??Charge de cargos
Un capitaine peut charger ses b^atiments avec dierents types de caissons dont les poids, les volumes et es rapports distincts sont les suivants :PoidsVolumerapportA101418
B22,54
C4610D121218
1. Le volume du premier cargo etant de 108 et la charge maximale de 112, com-
ment le charger pour obtenir le meilleur rapport? Indication :pour commencer, ne consideer qu'une seule des deux contraintes pour le choix du pivot.2. Le second cargo a un volume de 170 et une charge maximal de 82. Comment
charger ce second navire pour obtenir le meilleur rapport?Exo. 11.5?L'agriculteur intensif
Un agriculteur veut repandre sur ses prairies un engrais ayant une teneur maxi- male en azote (N). Les trois engrais dont il dispose contiennent egalement du phosphore (P) et du potassium (K). La teneur en potassium doit ^etre limitee a44 unites par hectare et celle en phosphore a 66 unites par hectare. Le tableau
suivant donne la quantite de N, P, K par engrais :Engrais 1Engrais 2Engrais 3 N346 K234 P5251. Comment doit-il faire son melange pour que la quantite d'azote soit maxi-
male? Exprimer le probleme sous forme d'un probleme de ProgrammationLineaire.
2. Calculer le probleme dual. Resoudre le graphiquement.
3. Ecrire les conditions du theoreme des ecarts complementaire et en deduire la
valeur d'une des variablesx1;x2;x3. En deduire la solution du probleme initial.Exo. 11.6?
On considere le probleme :
9.3. S
ERIE 17 :103
Maxz= 3x+2y
s:c:3x+2y153x+4y21
y3 x; y01. Calculer le dual de ce probleme.
2. Representer graphiquement l'ensemble des solutions admissibles du dual.
3. En supposant que le dual a une solution optimale unique, trouver celle-ci a
partir de la representation graphique. Verier alors que c'est bien une solution optimale.4. En utilisant la valeur trouvee pour l'optimum, montrer que le primal a au
moins une solution optimale (raisonner graphiquement sur l'ensemble des solu- tions admissibles). En a-t-il plusieurs?Exo. 11.7?
On considere le probleme :
Minw= 15y1+21y2+3y3
s:c:3y1+3y222y1+4y2+y32
y1; y2; y30
1. Calculer le dual de ce probleme.
2. Representer graphiquement l'ensemble des solutions admissibles du dual.
3. En utilisant le fait que l'ensemble des solutions admissibles du dual est un
polytope, en deduire l'optimum.4. En utilisant la valeur trouvee pour l'optimum du dual, montrer que le primal
a au moins une solution optimale (raisonner graphiquement sur l'ensemble des solutions admissibles). En a-t-il plusieurs?Exo. 16.8Ecart complementaire
Une compagnie fabrique deux types de sauces : une sauce tomate et une sauce aux legumes. Chacune est obtenue en melangeant des legumes et du concentre de tomates. Le concentre de tomates doit representer au moins la moitie de la composition de la sauce tomate. Les legumes doivent representer au moins le tiers de la composition de la sauce aux legumes. Chaque jour la compagnie peut acheter jusqu'a 4 tonnes de legumes a 50 dirhams le kg, et 3 tonnes de concentre de tomates a 30 dirhams le kg. La compagnie vend un kg de sauce tomate a 80 dirhams, et un kg de sauce aux legumes a 70 dirhams. La capacite d'absorption du marche est illimitee. La compagnie cherche a realiser le plus grand benece possible.1.Modeliser le probleme en un probl`eme de programmation lineaire (pas plus
de 4 variables. On le note (P).2.Ecrire le probleme (Q) dual de (P).
3.Trouver des bornes inferieures strictement positives pour deux des variables
duales. (On rappelle que les variables duales sont positives ou nulles).4.En utilisant le theoreme des ecarts complementaires, resoudre (P).
Exo. 11.9?
On considere le probleme de programmation lineaire (P) suivant :104CHAPITRE 9. METHODE DE SIMPLEXE
Maxz= 3x1+4x2+8x3
s:c: x1+2x2+3x315 x 1x3 1 x1; x2; x30
1. Mettre ce probleme en forme standart en introduisant des variables d'ecarts.
2. Introduire une variable articielle pour avoir une base admissible de depart.
3. Resoudre le probleme auxiliaire et le probleme initial (P). On donnera la
valeur optimale de z et les valeurs dex1,x2etx3correspondantes.Exo. 11.10?
On considere le probleme :
Minz= 12x+5y
s:c:2x+y4 3x+y5 x+y0 x; y2IR1. Calculer le probleme dual (ne pas oublier que le dual du dual est le pri-
mal).2. Resoudre le probleme dual par le simplexe.
3. Que vaut la fonction objectif du probleme initial a l'optimum? Pour quelles
valeurs cet optimum est-il atteint (utiliser les conditions d'optimalite primal- dual)?Exo. 11.11?
On considere le probleme :
Minz=3x+2y
s:c:xy+e1= 4 2x+y6 x+y0 x; y0e101. Transformer le probleme en un probleme en forme standard.
2. Resoudre le probleme en forme standard par l'algorithme du simplexe.
3. En considerant que la variablee0
1= -e1est une variable d'ecart rajoutee a
un probleme en forme canonique, donner le probleme canonique de depart et le resoudre graphiquement.4. Calculer le dual et en donner une solution. Est-elle unique?
Exo. 11.16Algorithme du simplexe (methode des 2 phases) Resoudre le programme lineaire suivant avec la methode des 2 phases de l'algo- rithme du simplexe :Minz=x+2y
s:c:2x+3y3 3x+y4 x; y0 A chaque iteration, on fera entrer en base la variable candidate de plus grand co^ut reduit. Verier ensuite graphiquement.9.3. S
ERIE 17 :105
Exo. 11.17Algorithme du simplexe (methode des 2 phases) Resoudre le PL suivant (en forme standard) avec la methode des 2 phases de l'algorithme du simplexe :Maxz=x1+x2+x3+x4
s:c:+2x2+x3= 2 x1+x2+5x3= 12
x1+2x2+6x3+x4= 13
x1; x2; x3; x40
On introduira le moins de variables articielles possible. De plus, a chaque iteration, on fera entrer en base la variable candidate de plus petit indice, et on fera sortir en priorite les variables articielles de la base (lors de la phase 1).Que peut-on observer?
Exo. 16.7Theoreme des ecarts complementaires
1. Donner le PL dual du PL suivant :Minz= 2x+7y
s:c: xy= 3 x+5y= 64x+2y= 15
x; y02. A l'aide du theoreme des ecarts complementaires, trouver une solution
optimale au PL dual.Exo. 11.22Dualite et resolution graphique
Resoudre le programme lineaire suivant graphiquement :Minz= 4x1+5x2+x3+6x4
s:c: x1+3x2+2x34x452x1+x23x3+5x47
4x1+2x2= 15
x1; x2; x3; x4;0
Exo. 11.23Dualite et modcations de contraintes
Soit le programme lineaire suivant :
Maxz= 2x+y
s:c:3x+2y9 y3 3xy12 x; y01. Calculer le tableau optimal du simplexe pour ce PL en le resolvant gra-
phiquement, puis en calculant algebriquement l'expression des variables de base en fonction des variables hors-base.2. La solution optimale obtenue reste-t-elle optimale si on modie la fonction
objectif en max3x1+ 5x2?3. Resoudre le programme lineaire suivant :
106CHAPITRE 9. METHODE DE SIMPLEXE
Minz= 9x1+3x2+12x3
s:c:3x1+3x322x1+x2x31
x1; x2x30
4. Que se passe-t-il si on remplace les valeurs 2 et 1 du second membre de
ce PL par 3 et 5 respectivement?quotesdbs_dbs33.pdfusesText_39[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
[PDF] adjectif pour acrostiche