Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

www.fsjesr.ac.ma Université Mohamed V—Agdal Faculté des Sciences Juridiques, Éc

www.fsjesr.ac.ma Université Mohamed V—Agdal Faculté des Sciences Juridiques, Économiques et Sociales, Rabat Filière de Sciences économiques et de Gestion Professeure : Amale LAHLOU Correction du Contrôle Final en Recherche Opérationnelle Semestre S5 / Option : Finance-Comptabilité Session Automne-Hiver 2006/2007 Page 1/6 P Pr ro ob bl lè èm me e d de e P Pr ro og gr ra am mm ma at ti io on n L Li in né éa ai ir re e 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 à 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ème type) ? 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 :        ≥ ≤ ≤ + ≤ + + = 0 , (3) ) en tissu stock ( 10 (2) ) bois en stock ( 16 ) 1 ( ) travail de heures ( 40 4 / 200 100 max 2 1 1 2 1 2 1 2 1 x x x x x x x c s x x z 2. Déterminons graphiquement la production optimale des chaises et des tables ; Le vecteur directeur de la droite représentant la fonction objectif 2 1 200 100 x x z + = est ( ) 100 , 200 − = u r ou encore ( ) 1 , 2 ' − = u r . La production optimale A est la solution du système suivant : ( ) UM z A x x x x x x x x x 2400 ) 8 ( 200 ) 8 ( 100 8 , 8 8 8 16 8 3 16 40 16 40 4 max 2 1 2 1 2 2 1 2 1 = + = = ⇒    = = ⇒      − = = − = ⇒    = + = + www.almohandiss.com Correction du Contrôle Final en Recherche Opérationnelle Semestre S5 / Option:Finance-Comptabilité Amale LAHLOU Page 2/6 2006/2007 ( 1) 40 4 2 1 = + x x x1 0 8 x2 10 8 (2) 16 2 1 = + x x x1 0 16 x2 16 0 (3) 10 1 = x droite verticale 3. L'interprétation économique des résultats : L’entreprise utilise toutes les heures de travail disponibles (la première contrainte est saturée 40 4 2 1 = + x x ) et tout le bois disponible (la deuxième contrainte est saturée 16 2 1 = + x x ) mais il lui reste 2 unités de tissu non utilisées (la troisième contrainte est non saturée 10 8 1 < = x ) pour produire 8 chaises et 8 tables par semaine ( ( ) 8 , 8 = A ) et ainsi réaliser un chiffre d’affaires maximal de 2400 UM ( 2400 ) 8 200 ( ) 8 100 ( max = × + × = z ). 4. Définition de la dégénérescence : il y a deux types de dégénérescence : 1er 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. 2iè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. 6. L’interprétation économique de chacune des variables d’écart : e1 : 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 : 5. Le passage de la forme canonique du programme primal à la forme standard se fait par l'ajout de trois variables d'écart 2 1,e e et 3 e :        ≥ = + = + + = + + + + + + = 0 , , , , 10 16 40 4 / 0 0 0 200 100 max 3 2 1 2 1 3 1 2 2 1 1 2 1 3 2 1 2 1 e e e x x e x e x x e x x c s e e e x x z -10 -5 0 5 10 15 20 -10 0 10 20 30 40 50 x1 x2 0 = z ) 8 , 8 ( = A 2400 max = z 8 8 (3) (1) (2) www.almohandiss.com Correction du Contrôle Final en Recherche Opérationnelle Semestre S5 / Option:Finance-Comptabilité Amale LAHLOU Page 3/6 2006/2007 B HB x1 x2 e1 e2 e3 C R e1 1 4 1 0 0 40 40/4 e2 1 1 0 1 0 16 16/1 e3 1 0 0 0 1 10 - -z 100 200 0 0 0 0 Tableau intermédiaire B HB x1 x2 e1 e2 e3 C R x2 1/4 1 1/4 0 0 10 40 e2 3/4 0 -1/4 1 0 6 8 1 0 0 0 1 10 10 -z 50 0 -50 0 0 -2000 B HB x1 x2 e1 e2 e3 C x2 0 1 1/3 -1/3 0 8 x1 1 0 -1/3 4/3 0 8 e3 0 0 1/3 -4/3 1 2 -z 0 0 -100/3 -200/3 0 -2400 Tableau final La solution de base admissible est ) 2 , 0 , 0 , 8 , 8 ( ) , , , , ( 3 2 1 2 1 = e e e x x . Donc la production optimale est ) 8 , 8 ( ) , ( 2 1 = x x et le chiffre d’affaires maximal est UM z 2400 max = 8. Supposons qu’on produit 10 tables. D’après le tableau intermédiaire de simplexe, la production de 4 chaises implique une diminution de la production des tables de 1 4 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 :        ≥ ≤ ≤ + ≤ + + = 0 , 10 16 40 4 / 200 100 max 2 1 1 2 1 2 1 2 1 x x x x x x x c s x x z      ≥ ≥ + ≥ + + + + = 0 , , 200 4 100 / 10 16 40 min 3 2 1 2 1 3 2 1 3 2 1 y y y y y y y y c s y y y w 10. Donnons le tableau final du programme dual à partir de celui du programme primal : HB B x1 x2 e1 e2 e3 C x2 0 1 1/3 -1/3 0 8 x1 1 0 -1/3 4/3 0 8 e3 0 0 1/3 -4/3 1 2 -z 0 0 -100/3 -200/3 0 -2400 Tableau final du programme primal www.almohandiss.com Correction du Contrôle Final en Recherche Opérationnelle Semestre S5 / Option:Finance-Comptabilité Amale LAHLOU Page 4/6 2006/2007 HB B y1 y2 y3 t1 t2 C y1 1 0 -1/3 1/3 -1/3 100/3 y2 0 1 4/3 -4/3 1/3 200/3 -w 0 0 -2 -8 -8 -2400 Tableau final du programme dual À l’optimum, 10 8 1 uploads/Management/ examcor20-pdf.pdf