Exercice corrigé recherche opérationnelle



Problème de Programmation linéaire


L’entreprise AMLAS produit des chaises et des petites tables à partir d'un stock de 16 unités de bois,10 unités de tissu et emploie un ouvrier qui fournit 40 heures de travail par semaine. Pour produire une chaise il faut 1 heure de travail, une unité de bois et une unité de tissu ; tandis que pour une table il faut 4 heures de travail et 1 unité de bois. Le prix d'une chaise est de 100 Unités-Monétaire (UM) et celui d'une table de 200 UM. L'entrepreneur désire déterminer la production hebdomadaire des chaises et des tables permettant de maximiser son chiffre d'affaires.

Travail a faire

1. Donnez la formalisation mathématique, sous forme canonique, du présent programme linéaire (programme primal);
2. Déterminez graphiquement la production optimale des chaises et des tables;
3. Quelle est l'interprétation économique de ces résultats ?
4. La production optimale est-elle dégénérée (donnez la définition de la dégénérescence du 1er et du 2ièmetype) ?
5. Écrivez le programme primal sous forme standard ;
6. Le passage de la forme canonique à la forme standard se fait par l'ajout des variables d'écart. Quelle est l'interprétation économique de chacune d’entres elles ?
7. Retrouvez la production optimale via l'algorithme de simplexe (écrivez les chiffres à l'intérieur des trois tableaux de simplexe sous forme de fractions) ;
8. Si on produit 10 tables, de combien faudrait-il réduire cette production pour produire 4 chaises ?
9. Écrivez le dual du programme primal ;
10. Donnez le tableau final du programme dual à partir de celui du programme primal

Réponse

1. Donnons la formalisation mathématique, sous forme canonique, du programme primal. Soient : 
X1 : nombre de chaises produites par semaine 
X2 : nombre de tables produites par semaine Nous sommes en



 Présence d’un programme linéaire :





2. Déterminons graphiquement la production Optimale des chaises et des tables ;
Le vecteur directeur de la droite représentant la fonction objectif Z=100x1+200x2 est u = (-200,100) ou encore u=(-2,1). La production optimale A est la solution du système suivant :







3. L'interprétation économique des résultats

   L’entreprise utilise toutes les heures de travail disponible 
(la première contrainte est saturée x1 + 4x2 = 40 ) et tout le bois disponible 
(la deuxième contrainte est saturée x1 + x2 = 16) mais il lui reste 2 unités de tissu non utilisées 
(la troisième contrainte est non saturée x1=8<10 ) Pour produire 8 chaises et 8 tables par semaine (A=8,8))  et ainsi  réaliser  un  chiffre  d’affaires maximal  de  2400  UM 
( Zmax = (100x8)+(200x8) =24 ) .



 4. Définition de la dégénérescence
il y a deux types de dégénérescence : 
1 er type : C’est le cas où le coefficient directeur de la droite représentant la fonction économique est identique à celui de la droite représentant une contrainte non redondante. Il existe donc une infinité de solutions. Ce n’est pas le cas dans notre exemple.
2 iéme type : Une solution optimale est dite dégénérée si plus de deux contraintes concourent en ce point. Ce n’est pas le cas dans notre exemple. 

5. Le passage de la forme canonique du programme primal à la forme standard se fait par l'ajout de trois variables d'écart e1 , e2 et e3  :


6.L’interprétation économique de chacune des variables d’écart : 
e3 : les heures de travail disponibles par semaine et non utilisées 
e2 : la quantité de bois disponible par semaine et non utilisée 
e3 : la quantité de tissu disponible par semaine et non utilisée 

7.Retrouvons la production optimale via l'algorithme du simplexe :


La solution de base admissible est (x1,x2,e1,e2,e3) = (8,8,0,0,2). donc la production optimale est (x1,x2)= (8,8) et le chiffre d'affaire maximale est Zmax=2400 Um.

8. Supposons qu’on produit 10 tables. D’après le table au intermédiaire de simplexe, la production de 4 chaises implique une diminution de la production des tables de 1/4 x 4 =1 . Ainsi, pour produire 4 chaises on doit réduire la production des tables d’une unité, c’est-à-dire, ne produire rien que 9 tables. 

9. Écrivons le programme dual :

10.Donnons le tableau final du programme dual à partir de celui du programme primal




À l’optimum,


Donc la solution du programme dual est :



edit cepat

Smiley face


0 commentaires:

Enregistrer un commentaire

Exercice corrigé recherche opérationnelle