Universit Ibn Zohr

Facult des Sciences Juridiques conomiques et Sociales

Travaux

Dirigs e

Programmation Linaire
Mohamed HACHIMI
FILIRE SCIENCES CONOMIQUES ET GESTION TROISIME ANNEE

EG

Semestre 5
2010

Facult des Sciences Juridiques conomiques et Sociales

Modlisation

Mettre sous forme de programmes linaires, sans les rsoudre, les exercices suivants : Exercice 1.1 Un atelier fabrique des tables et des bureaux. Chaque table ncessite 2, 5 h pour lassemblage, 3 h pour le polissage et 1 h pour la mise en caisse. Chaque bureau exige 1 h pour lassemblage, 3 h pour le polissage et 2 h pour la mise en caisse. Lentreprise ne peut disposer, chaque semaine, de plus de 10 h pour lassemblage, de 15 h pour le polissage et de 8 h pour la mise en caisse. Sa marge de prot est de 30 dh par table et de 40 dh par bureau. Combien de tables et de bureaux doit-on produire an dobtenir un prot hebdomadaires maximal ? Exercice 1.2 Un agriculteur souhaite mlanger des engrais de faon obtenir au minimum 15 units de potasse, 20 units de nitrates et 3 units de phosphates. Il achte deux types dengrais. Le type 1 procure 3 units de potasse, 1 unit de nitrates et 3 units de phosphates. Il cote 120 dh. Le type 2 procure 1 units de potasse, 5 unit de nitrates et 2 units de phosphates. Il cote 60 dh. Exprimer laide dun programme linaire la combainaison dengrais qui remplira les conditions exiges au moindre cot. Exercice 1.3 Un maracher, vendant des citrons et des oranges, veut les grouper par lots de vente. Le premier lot contient 5 citrons et 1 orange, et se vend 4 Dh. Le deuxime lot contient 1 citron et 10 oranges, et se vend 6 Dh. Il dispose au total de 60 citrons et 110 oranges. Quelle est la rpartition la plus avantageuse pour lui, entre les deux types de lots ? Exercice 1.4 On donne ci-aprs les caractristiques de 3 gaz : A, B, C : A Teneur en souffre (g/m3 ) Prix (Dh/m ) Pouvoir calorique (kcal/m )
3 3

B 2 25 2 000

C 4 15 1 500

6 10 1 000

Raliser le mlange qui donne le plus grand pouvoir calorique en respectant les contraintes suivantes : La teneur en souffre doit tre au plus de 3 g/m3 , Le prix ne doit pas dpasser 22 Dh/m3 .

HACHIMI T.D Semestre 5 2009

Modlisation

Exercice 1.5 On dcide de rorganiser le trac entre deux villes A et B. On vous demande conseil sur le problme suivant : Il y a 12 routes entre A et B. Certaines dentre elles vont tre mises en sens unique de A vers B, dautres de B vers A, dautres encore seront maintenues double sens, dautres enn seront abandonnes. Le dbit dune route sens unique de A vers B est de 60 vhicules la minute. De mme pour une route sens unique de B vers A. Le dbit dune route double sens est de 20 vhicules la minute de A vers B et 30 vhicules la minute de B vers A. Lquipement dune route sens unique de A vers B cote 200 Dh. Pour route sens unique de B vers A ce cot est de 400 Dh, et pour une route double sens : 300 Dh. On veut assurer au moindre cot un dbit total de 300 vhicules la minute dans chaque sens. Exercice 1.6 Une entreprise dispose de trois usines localises diffrents endroits au pays. production annuelle de chaque usine est la suivante : Usine Usine 1 Usine 2 Usine 3 Production annuelle 15 000 units 12 000 units 23 000 units La

Ces usines alimentent quatre points de vente dont la demande annuelle est la suivante : Points de vente A B C D Demande annuelle 10 000 units 5 000 units 20 000 units 15 000 units

Les cots unitaires de transport de chaque usine chaque point de vente sont indiqus dans le tableau suivant : Points de ventes Usine 1 Usine 2 Usine 3 A 5 11 12 B 6 9 7 C 6 4 8 D 8 7 5

Usines

Formuler le modle de programmation linaire qui permettrait dobtenir un plan de transport un cot minimum.

HACHIMI T.D Semestre 5 2009

Facult des Sciences Juridiques conomiques et Sociales

Mthode graphique

Exercice 2.1 Reprendre les Exercices 1.1, 1.2 et 1.3 de la feuille de TD1, et trouver les solutions optimales laide de la mthode graphique. Exercice 2.2 On considre le programme linaire suivant : max z = 2x1 + 6x2 x1 + x2 8 x1 x2 3 x + 4x 16 1 2 x1 0, x2 0 1 2 3 4 Tracer les contraintes et dterminer la rgion ralisable. La rgion ralisable comportent combien de points extrmes ? Dterminer la solution optimale avec la mthode graphique. Quelles sont les contraintes qui sont satisfaites avec une stricte galit ? Exercice 2.3 On considre le programme linaire suivant : min z = 4x1 + 2x2 4x1 + x2 10 2x1 + x2 7 x + 6x 9 1 2 x1 0, x2 0 1 Dterminer la solution optimale avec la mthode graphique. 2 Est-ce que la solution optimale est unique ? Exercice 2.4 On considre le programme linaire suivant : max z = 4x1 + 6x2 3x1 + 2x2 12 x1 + x2 8 x x 0 1 2 x1 0, x2 0 1 Tracer les contraintes et dterminer la rgion ralisable. 2 Combien existe-t-il de points extrmes ? 3 Peut-on dterminer une solution optimale nie au programme linaire ?
HACHIMI T.D Semestre 5 2009

Mthode graphique

Exercice 2.5 On considre le programme linaire (P) suivant : max z = 6x1 + 5x2 x1 + x2 8 2x1 + 3x2 6 x1 x2 2 x1 0, x2 0 1 Rsoudre graphiquement le problme (P). 2 En introduisant un paramtre dans la fonction objectif z, le programme scrit : max z = (6 2)x1 + (5 + )x2 x1 + x2 8 2x1 + 3x2 6 x1 x2 2 x1 0, x2 0 a) Rsoudre ce programme suivant les valeurs de . b) Parmi les solutions ralisables trouves dans la premire question, quelles sont celles qui ne sont jamais solutions optimales ?. c) Pour quelles valeurs de , ce programme admet une innit de solutions optimales ?

HACHIMI T.D Semestre 5 2009

Facult des Sciences Juridiques conomiques et Sociales

Mthode du simplexe (I)

Exercice 3.1 Un entreprise fabrique son produit dans deux atelier. Les capacits de production sont de 7 units pour le premier atelier et de 10 pour le second. Dautre part, le nombre total dheures de main duvre quon peut affecter cette production est 60. Or, chaque unit de production ncessite 10 h de main duvre dans le premier atelier et 5 h dans le second. Enn la production doit permettre de satisfaire au moins une demande de 8. Sachant que les cots unitaires sont de 2 pour le premier atelier et 3 pour le second, lentreprise dsire produire cot minimum. 1 Ecrire le programme (P) correspondant. Que pensez vous a priori de la contrainte de demande loptimum ? 2 Mettre (P) sous forme standard. Montrer quon peut dnir un sommet A de la rgion ralisable qui corresponde une production maximale du second atelier sans production du premier. 3 Rsoudre (P) en partant de A et en utilisant la mthode du simplexe. Exercice 3.2 On considre le programme linaire (P) suivant : max z = 3x1 + 4x2 + 10x3 x1 + 2x3 6 x2 + x3 6 x1 0, x2 0, x3 0 1 Montrer que le point A = (0, 0, 3) est un sommet de la rgion ralisable. 2 Rsoudre (P) par la mthode du simplexe en partant du sommet A. 3 Ayant ainsi trouv un sommet optimal B, montrer quil existe un autre sommet optimal C et le dterminer. Exercice 3.3 On considre le programme linaire (P) suivant : max z = 4x1 + 2x2 + x3 x1 + x2 1 x1 + x3 1 x1 0, x2 0, x3 0 1 Rsoudre (P) par la mthode du simplexe. On parvient ainsi en un sommet A dont on considrera toutes les bases possibles. Que pensez-vous de lusage du critre doptimalit de la mthode ? 2 Dessiner en perspective, dans lespace R3 la rgion ralisable. Commenter la situation du sommet A.
HACHIMI T.D Semestre 5 2009

Facult des Sciences Juridiques conomiques et Sociales

Mthode du simplexe (II)

Exercice 4.1 Rsoudre le programme suivant en utilisant la mthode du simplexe max z = 10x1 + 15x2 5x1 + 2x2 80 x1 + x2 20 x1 + 2x2 30 x1 0, x2 0 Exercice 4.2 Rsoudre le programme suivant en utilisant la mthode du simplexe max z = 120x1 + 108x2 + 75x3 x1 + x2 + x3 12 x1 5 8x1 + 7x2 + 5x3 145 x1 0, x2 0, x3 0 Exercice 4.3 Rsoudre le programme suivant en utilisant la mthode du simplexe max z = x1 x2 2x1 x2 4 x1 x2 4 x1 + x2 10 x1 0, x2 0 Exercice 4.4 Rsoudre le programme suivant en utilisant la mthode du simplexe max z = 10x1 + 14x2 x1 + x2 12 x1 8 x2 6 x1 0, x2 0 1 Montrer que x = (12, 0) est un sommet de la rgion ralisable. Mettre le programme sous forme standard, puis donner la solution de base ralisable y associe x. 2 Rsoudre ce programme par la mthode du simplexe en prenant comme point de dpart y .

HACHIMI T.D Semestre 5 2009

Facult des Sciences Juridiques conomiques et Sociales

Dualit

Exercice 5.1 Formuler le problme dual de chacun des programmes linaires suivants : max z = 2x1 + 4x2 + 3x3 max z = 3x1 + x2 2x3 3x1 + 4x2 + 2x3 60 x1 + 2x2 10 2x1 + x2 + 2x3 40 3x1 x2 + x3 = 7 (P1 ) (P2 ) x1 + 3x2 + 2x3 80 x1 + 3x3 8 x1 0, x2 0, x3 0 x2 0, x3 0 max z = 10x1 + 14x2 max z = 400x1 + 350x2 + 450x3 x1 + x2 12 2x1 3x2 + 2x3 120 x1 8 4x1 + 3x2 = 160 (P3 ) (P4 ) x2 6 3x1 2x2 + 4x3 100 x1 0, x2 0 x2 0 Exercice 5.2 Appliquer le thorme des carts complmentaires vue en cours pour vrier loptimalit de la solution propose. max z = 7x1 + 6x2 + 5x3 2x4 + 3x5 x1 + 3x2 + 5x3 2x4 + 2x5 4 4x1 + 2x2 2x3 + x4 + x5 3 2x1 + 4x2 + 4x3 2x4 + 5x5 5 3x1 + x2 + 2x3 x4 2x5 1 x1 0, x2 0, x3 0, x4 0, x5 0 Solution propose : Exercice 5.3 Appliquer le thorme des carts complmentaires vue en cours pour vrier loptimalit de la solution propose. max z = 4x1 + 5x2 + x3 + 3x4 5x5 + 8x6 x1 4x3 + 3x4 + x5 + x6 1 5x1 + 3x2 + x3 5x5 + 3x6 4 4x1 + 5x2 3x3 + 3x4 4x5 + x6 4 x2 + 2x4 + x5 5x6 5 2x1 + x2 + x3 + x4 + 2x5 + 2x6 7 2x1 3x2 + 2x3 x4 + 4x5 + 5x6 5 x1 0, x2 0, x3 0, x4 0, x5 0 Solution propose : (x1 , x2 , x3 , x4 , x5 , x6 ) = (0, 0, 5/2, 7/2, 0, 1/2) (x1 , x2 , x3 , x4 , x5 ) = (0, 4/3, 2/3, 5/3, 0)

HACHIMI T.D Semestre 5 2009