Scribd
Importer
179 vues3 pages

Optimisation en Programmation Linéaire

Ce document présente quatre exercices de programmation linéaire. L'exercice 1 décrit une usine produisant quatre produits avec des contraintes de production et demande de formuler le programme linéaire maximisant le revenu. L'exercice 2 concerne la résolution graphique et algébrique d'un programme linéaire. L'exercice 3 formule un problème de surveillance vidéo comme un problème de programmation linéaire. L'exercice 4 étudie l'optimalité d'une itération de la méthode du simplexe pour un programme donné.

Transféré par

slo
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
179 vues3 pages

Optimisation en Programmation Linéaire

Ce document présente quatre exercices de programmation linéaire. L'exercice 1 décrit une usine produisant quatre produits avec des contraintes de production et demande de formuler le programme linéaire maximisant le revenu. L'exercice 2 concerne la résolution graphique et algébrique d'un programme linéaire. L'exercice 3 formule un problème de surveillance vidéo comme un problème de programmation linéaire. L'exercice 4 étudie l'optimalité d'une itération de la méthode du simplexe pour un programme donné.

Transféré par

slo
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Programmation linéaire

Semestre : 1 2

Session : Principale Rattrapage

Module : Programmation linéaire


Enseignant(s) : Sifi Sami
Classe(s) : 4GL1-2
Documents autorisés  : OUI 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 Prix unitaire (TND)


P1 25
P2 75
P3 110
P4 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

Vous aimerez peut-être aussi