Remerciez-le!

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

UNIVERSITE IBN ZOHR Ann´ ee Universitaire 2014-2015 Facult´ e des Sciences Juri

UNIVERSITE IBN ZOHR Ann´ ee Universitaire 2014-2015 Facult´ e des Sciences Juridiques Economiques et Sociales S5 Agadir Recherche Op´ erationnelle S´ erie2: R´ esolution par la m´ ethode alg´ ebrique Pr. O.Chadli Rappel sur le principe de la r´ esolution par la m´ ethode alg´ ebrique La m´ ethode alg´ ebrique est une recherche syst´ ematique de programmes de base (points sommets) jusqu’` a l’obtention d’un programme optimal. Il s’agit tout simplement d’un algorithme o` u chaque it´ eration fait passer d’une solution extˆ eme vers une autre tout en faisant augmenter la valeur de la fonction ´ economique. Pour ce faire, il s’agit: 1- De structurer le probl` eme sous forme d’un syst` eme d’´ equations en introduisant les vari- ables d’´ ecart requises. Il s’agira bien sˆ ur d’avoir pr´ ecis´ e pr´ ealablement les variables (principales et d’´ ecart) ainsi que la fonction ´ economique. 2- De d´ eterminer un programme de base qui servira de d´ epart au cheminement vers la solution optimale (programme optimal). 3- D’expliciter la fonction ´ economique et de d´ eterminer si elle peut ˆ etre am´ elior´ ee: recherche de l’´ eventuelle variable (hors programme) admettant le plus grand coeﬃcient positif. Dans la n´ egative, le programme est optimal. 4- En introduisant cette variable dans le programme, on choisira la plus petite valeur positive obtenue ` a l’aide du syst` eme d’´ equations calcul´ e lors de l’´ etape pr´ ec´ edente. Cel` a induira ´ egalement la variable sortante. 5- Pour d´ eterminer un nouveau programme de base, on doit transformer le syst` eme d’´ equations ainsi que l’expression de la fonction ´ economique en exprimant les vari- ables dans le programme de base en fonction des variables hors programme (par substitution). 6- Retourner ` a 3) jusqu’` a l’obtention du programme de base optimal. 7- Donner le programme optimal en pr´ ecisant la valeur de toutes les variables ainsi que la valeur optimis´ ee de la fonction ´ economique. Exercice 1 : La direction d’une usine de meubles a constat´ e qu’il y a des temps morts dans chacun des d´ epartements de l’usine. Pour rem´ edier ` a cette situation, elle d´ ecide d’utiliser ces temps morts pour fabriquer deux nouveaux mod` eles de bureaux, M1 et M2. Les temps de r´ ealisation pour chacun de ces mod` eles dans les ateliers de sciage, d’assemblage et de sablage ainsi que les temps libres dans chacun de 1 www.tifawt.com ces ateliers sont donn´ es dans le tableau ci-dessous. Ces temps repr´ esentent le nombre d’heures n´ ecessaires ` a un homme pour eﬀectuer le travail. Les proﬁts que la compagnie peut r´ ealiser pour chacun de ces mod` eles sont de 300 DH pour M1 et de 200 DH pour M2. M1 M2 Temps Libre Sciage 1 2 20 Assemblage 2 1 22 Sablage 1 1 12 1- Trouver le programme de l’entreprise par la m´ ethode alg´ ebrique. 2- Pr´ eciser les ateliers pour les quels il y a un temps mort. Exercice 2 : L’entreprise NewTech doit, dans son processus de fabrication de ses produits, utiliser trois phases successives d’op´ eration : l’usinage des pi` eces, l’assemblage et la ﬁnition. Pour simpliﬁer le probl` eme, supposons que l’entreprise fabrique trois produits que nous noterons P1, P2 et P3. Les diﬀ´ erentes phases d’op´ eration ne peuvent toutefois fonctionner que pendant un certain nombre d’heures. La main d’oeuvre actuelle limite le nombre d’heures disponibles aux valeurs suivantes: Usinage: 100 heures Assemblage: 120 heures Finition: 200 heures Le tableau suivant nous indique les temps de fabrication requis, en heures/unit´ e, aux diﬀ´ erentes phases d’op´ eration pour fabriquer les produits P1, P2 et P3. P1 P2 P3 Usinage 1 2 1 Assemblage 3 4 2 Finition 2 6 4 Le d´ epartement de compatibilit´ e de l’entreprise a estim´ e aux valeurs suivantes la contribution au b´ en´ eﬁce de chaque produit: Produit DH/ unit´ e P1 6 P2 7 P3 8 De plus, on suppose qu’il n’existe aucune restriction de march´ e ; il peut absorber toute la produc- tion. 1- D´ eterminer le programme de l’entreprise par la m´ ethode alg´ ebrique. 2- D´ eterminer les ateliers pour lesquels il y a pr´ esence d’un temps mort. Exercice 3 : L’entreprise MarocMecanique fabrique trois produits P1, P2 et P3 et pour r´ ealiser ce projet utilise trois centres de fabrication. Les temps op´ eratoires, en heure par unit´ e, ` a chaque centre de fabrication sont les suivants: 2 www.tifawt.com P1 P2 P3 Temps disponible Centre I 4 2 4 80 heures Centre II 2 2 3 50 heures Centre III 1 3 2 40 heures La contribution unitaire de chaque produit au b´ en´ eﬁce est la suivante: P1 P2 P3 5 DH 3 DH 4 DH 1- D´ eterminer, ` a l’aide de la m´ ethode alg´ ebrique, le programme de fabrication qui maximise les b´ en´ eﬁces. 3- Le centre II est-il pleinement utilis´ e? Exercice 4 : Trois esp` eces de crabes sont pˆ ech´ ees dans les eaux cˆ oti` eres de l’Alaska : le crabe royal (King crab), le crabe des neiges (Snow crab), le crabe Dungeness, en des lieux diﬀ´ erents, mais proches. Des bateaux sont am´ enag´ es pour pouvoir pˆ echer indiﬀ´ eremment les trois sortes de crabes; pour un mois donn´ e, dans la zone de Cook Inlet, la capacit´ e totale de pˆ eche des bateaux est de 1000 tonnes de crabes. A l’arriv´ ee des bateaux au port, un tri doit ˆ etre eﬀectu´ e sur la cargaison ce tri tient compte, suivant la p´ eriode de bataille, de la taille des carapaces des crabes, de leur qualit´ e, etc... Aussi, apr` es ce tri, ne peut-on utiliser en moyenne que 80% de la quantit´ e totale de crabes royal pˆ ech´ ee, 95% de celle de crabe des neiges et 90% de celle du crabe Dungeness. Les crabes ´ elimin´ es sont perdus. Intervient alors un conditionnement: diﬀ´ erents points sont situ´ es sur la cˆ ote, celui attribu´ e ` a la zone Cook Inlet pouvant conditionner au maximum 900 tonnes de crabes au total pour le mois consid´ er´ e. Le crabe royal est le plus demand´ e, mais aﬁn de respecter un certain ´ equilibre entre les esp` eces, il a ´ et´ e ´ etabli que la diﬀ´ erence entre la quantit´ e pˆ ech´ ee de crabe royal et le tonnage global des deux autres esp` eces doit ˆ etre inf´ erieure ` a 100 tonnes. Les pˆ echeurs connaissent les sites o` u ils peuvent attraper telle ou telle sorte de crabe (qui ne se m´ elangent pas: en un lieu donn´ e, on ne rencontre pas simultan´ ement des esp` eces diﬀ´ erentes). Le b´ en´ eﬁce r´ ealis´ e est: 12.5 unit´ es mon´ etaires (u.m.) par tonne de crabes royal pˆ ech´ ee et conditionn´ ee, 8.42 u.m. par tonne pour la seconde esp` ece et 7.78 u.m. par tonne pour la troisi` eme. 1- Formulez ce probl` eme ` a l’aide d’un mod` ele de programmation lin´ eaire 2- Etablir, en utilisant la m´ ethode alg´ ebrique, le plan de pˆ eche qui maximise le b´ en´ eﬁce. Exercice 5 : La compagnie ”XXY” vient de perdre un contrat de production d’aﬃches de prix pour des stations- service. Elle se retrouve avec des ressources exc´ edentaires qu’elle doit absolument utiliser ` a d’autres ﬁns. Ces ressources sont 300 kg de revˆ etement int´ erieur pour boˆ ıtes fortes et 120 kg de carton ﬁn. De plus, elle dispose de 10 heures de travail par jour. Elle peut utiliser ces ressources pour fabriquer des emballages de carton, des tubes et des boˆ ıtes. La fabrication de 100 emballages de carton requiert 150 kg de revˆ etement int´ erieur, 30 kg de carton ﬁn et 2 heures de travail. La fabrication de 600 tubes requiert 50 kg de revˆ etement int´ erieur, 30 kg de carton ﬁn et 2 heures de travail. Enﬁn, la fabrication de 100 boˆ ıtes requiert 60 kg de revˆ etement int´ erieur, 40 kg de carton ﬁn et 5 heures de travail. Le proﬁt est de 10 DH par boˆ ıte, de 1 DH par tube et de 4 DH par emballage. 3 www.tifawt.com 1- Formulez ce probl` eme ` a l’aide d’un mod` ele de programmation lin´ eaire 2- Comment la compagnie doit-elle utiliser ses ressources pour maximiser son proﬁt ? (Utilisez la m´ ethode alg´ ebrique) Probl` eme : Etude de cas (possibilit´ e d’avoir un sujet similaire en examen!!) Partie I. La soci´ et´ e Prima S. A. fabrique et vend notamment deux produits P1 et P2 dont les prix de vente respectifs sont de 400 DH et 300 DH hors taxe au tarif en vigueur. Le march´ e de ces deux produits est essentiellement r´ egional et porte sur 1 500 unit´ es de chacun des deux uploads/Industriel/ corrige-exercice-recherche-operationnelle.pdf