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=100×1+200×2 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 = (100×8)+(200×8) =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 :