[PDF] La Programmation Linéaire : Cours Exercices corrigés et Etude de

View - Download La Programmation Linéaire : Cours Exercices corrigés et Etude de

Previous PDF

Next PDF

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 96

Chapitre 9

Methode de simplexe

9.1 S

ERIE 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 33
x

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+2y18

4x+3y24

x; y0

1.Ecrire ce PL sous forme standard.

97

98CHAPITRE 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= 80

2x1+2x2+3x3+x5= 50

x

1+3x2+2x3+x6= 40

x

1; 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; y0

1.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 2500
x

3 1500

3x1+6x22x36750

x

10; 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+3x35

4x1+x2+2x311

3x1+4x2+2x38

x

1; 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 2M

3Piece 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 S

ERIE 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+2y4

2x+y12

x; y0

Maxz= 2x+y

s:c:2xy4 x+y1 x+2y4

2x+y12

x; y0

Maxz=x+2y

s:c:2xy4 x+y1 x+2y4

2x+y12

x; y0

Exo. 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; y0

9.2. S

ERIE 16 :101

Maxw=x+y+z

s:c: x+y+2z= 5 xy= 1 y+z= 2 x; y; z0

Minw=x+y+z

s:c: x+y+2z5 x+y 1 y+z2 x; y0

102CHAPITRE 9. METHODE DE SIMPLEXE

9.3 S

ERIE 17 :

Exo.??

Resoudre sans utiliser de variable articielles le probleme suivant :

Maxw=2x3y

s:c:2x+yz4

3xy+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 :PoidsVolumerapport

A101418

B22,54

C4610

D121218

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 a

44 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 P525

1. Comment doit-il faire son melange pour que la quantite d'azote soit maxi-

male? Exprimer le probleme sous forme d'un probleme de Programmation

Lineaire.

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+2y15

3x+4y21

y3 x; y0

1. 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+3y22

2y1+4y2+y32

y

1; 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 x

1; 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; y2IR

1. 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; y0e10

1. 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 x

1+x2+5x3= 12

x

1+2x2+6x3+x4= 13

x

1; 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= 6

4x+2y= 15

x; y0

2. 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+2x34x45

2x1+x23x3+5x47

4x1+2x2= 15

x

1; x2; x3; x4;0

Exo. 11.23Dualite et modcations de contraintes

Soit le programme lineaire suivant :

quotesdbs_dbs19.pdfusesText_25

[PDF] programmation linéaire exercices corrigés

[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