PL Novembre 2018 [PDF]

Zitiervorschau

Programmation linéaire Semestre : 1

2

Session : Principale Module : Programmation linéaire Enseignant(s) : Sifi Sami Classe(s) : 4GL1-2 Documents autorisés  : OUI

Rattrapage

NON

Date : 21/11/2018

Heure : 13h30

Durée : 1 h 30 min

Exercice 1 : Une usine de pièces électroniques produit trois types de produits P1, P2, P3 et P4. Les prix unitaires et les contraintes de production sont les suivantes : Produit P1 P2 P3 P4     

Prix unitaire (TND) 25 75 110 200

Contrainte 1 : La production d’une unité du produit P1 nécessite 3 heures de main d’œuvre. Contrainte 2 : La production d’une unité du produit P2 nécessite 5 heures de main d’œuvre en plus de deux unités du produit P1 Contrainte 3 : La production d’une unité du produit P3 nécessite 4 heures de main d’œuvre en plus d’une unité du produit P2 et trois unités de P1. Contrainte 4 : La production d’une unité du produit P4 nécessite six heures de main d’œuvre en plus deux unités du produit P3 et deux unités de P1. L’usine dispose de 400 heures de main d’œuvre par semaine.

Donner le programme linéaire qui permet à l’usine de déterminer le nombre d’unités des produits (P1, P2, P3, P4) maximisant le revenu. Exercice 2 Soit le programme linéaire P suivant : max( z )  2 x1  x2  x1  x2  2  x  x  2  1 2   x1  x2  4  xi  0 1- Représenter le domaine de faisabilité de programme linéaire P. 2- Résoudre le programme P en utilisant la méthode du simplexe. 3- Décrire sur le graphe de P, l’ordre de parcours des points extrêmes associés à la méthode 1/2

du simplexe. Exercice 3 Une galerie d'art envisage l'installation d'un système de sécurité de caméras vidéo afin de réduire ses primes d'assurance. Le diagramme des huit salles d'exposition que la galerie utilise pour ses expositions est illustré ci-dessous ; les ouvertures entre les salles sont numérotées de 1 à 13. Une société de sécurité a proposé que des caméras (à deux sens) soient installées à certaines ouvertures de salles. Chaque caméra a la capacité de surveiller les deux pièces entre lesquelles elle s’y trouve. Par exemple, si une caméra est située á l’ouverture numéro 4, les chambres 1 et 3 seront couvertes ; si une caméra est située à l'ouverture 11, les chambres 6 et 8 seront couvertes ; etc. La direction a décidé de ne pas installer des caméras à l'entrée aux salles d’exposition. L'objectif est de fournir une couverture de sécurité pour l'ensemble des huit salles avec un coût minimal. Formuler ce problème comme un problème de PL en définissant les éléments suivants : Les Variables de Décision, La Fonction Objectif, Les Contraintes.

Diagramme des salles d’exposition Question 4 (5 points) Soit le programme linéaire P suivant :

max : 2 x1  x2  x3 3 x1  x2  x3  60  x  x  2 x  10  1 2 3   x1  x2  x3  20  xi  0 On note e1, e2 et e3 les variables d’écarts associées aux trois contraintes. 2/2

Le tableau suivant est associé à l’itération (i) de la méthode du simplexe : x1 x2 x3 e1 e2 e3 Valeur (=) e1

0

0

1

1

-1

-2

10

x1

1

0

1/2

0

1/2

1/2

15

x2

0

1

-3/2

0

-1/2

1/2

5

Donner les valeurs des xi et ej et étudier l’optimalité de la solution en cours.

3/2