Remerciez-le!

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

GINF1/GSTR1 Matière : RO Année 2019/2020 I. Problèmes Linéaires Exercice 1 : Ré

GINF1/GSTR1 Matière : RO Année 2019/2020 I. Problèmes Linéaires Exercice 1 : Résoudre par la méthode du simplexe le programme linéaire suivant : 1 2 3 1 2 3 1 2 3 1 2 3 Maximiser z = 8x +8 x + 47 x sous les contraintes : 4x + x + 7 x 2 x + 4 x + 10 x 3 x 0 , x 0 , x 0 ⎧ ⎪ ⎪ ⎪ ≤ ⎨ ⎪ ≤ ⎪ ⎪ ≥ ≥ ≥ ⎩ Retrouver le résultat par Matlab Exercice 2 : Trois personnes P1, P2 et P3 sont associées dans une entreprise de terrassement. Les travaux nécessitent l'utilisation complémentaire de 3 engins. Chacun des 3 associés est spécialisé dans la conduite d'un de ces engins. La pénibilité de leur travail est différente et ils ne peuvent donc travailler le même nombre d'heures par jour. Un mois de travail est constitué respectivement pour chacun d'entre eux de 141,160 et 181 heures. Les différents travaux qu'ils peuvent effectuer sont de trois types T1, T2, T3. Le nombre d'heures de travail nécessaires pour la réalisation de chacun de ces types de travaux est donné dans le tableau ci-dessous : Les travaux T1, T2, T3 procurent une marge bénéficiaire de 200, 120 et 100 $.On note par x1, x2, x3 le nombre de travaux de chaque type T1, T2, T3, qu'ils doivent effectuer mensuellement pour maximiser leur bénéfice. 1. Ecrire le programme linéaire que les 3 associés sont amenés à résoudre. 2. Quel sera le bénéfice mensuel de leur entreprise ? 3. Quel est l'associé qui aura du temps libre pour s'occuper des taches de gestion ? 4. Si la personne P3 devait s'absenter 1 heure pendant le mois, quelle conséquence cela aurait-il sur le bénéfice optimal ? 5. Donner le problème dual de 1). 6. En déduire la solution optimale du dual à partir du tableau optimal du primal. P1 P2 P3 T1 3 4 5 T2 2 2 3 T3 3 2 2 Exercice 3 : Soit le programme linéaire suivant : Minimiser z = 2x1 + x2 +35x3 sous les contraintes : 4 x1 -2 x2- 6x3 ≥ 1 -3 x1 + x2+14x3 ≥ 2 x1 ≥0 , x2 ≥ 0, x3 ≥ 0 1. Donner le programme dual (PL)* de (PL). 2. Résoudre (PL)* par la méthode du simplexe. 3. En déduire le tableau optimal du (PL). Exercice 4 : Résoudre par la méthode de séparation & évaluation, le problème linéaire en nombre entier suivant : Exercice 5 : Le directeur financier d’une société décide d’investir une somme de 100 unités de manière à maximiser le revenu. Il considère les possibilités suivantes : Type d’investissement : 1 A 2 A 1 B 2 B 1 C 2 C Intérêts : 6% 5% 7% 8% 10% 9% Au moins 40% de la somme totale doit être investie en valeur de type A et au plus 35% dans l’un quelconque des deux autres types. 1. Ecrire la formulation mathématique du problème. 2. Résoudre le problème à l’aide de l’algorithme du simplexe. Exercice 6 : Dans une entreprise de transport, les demandes journalières en chauffeur sont présentées par le tableau suivant : Lu Ma Me Je Ve Sa Di 13 18 21 16 12 25 9 Les chauffeurs travaillent 5 jours d’affilée ( peuvent avoir leurs deux jours de congé n’importe quand dans la semaine ). Déterminer les effectifs formant les sept équipes possible de chauffeurs de manière à : 1. Couvrir tous les besoins 2. Engager un nombre minimum de chauffeurs. Exercice 7 : Une compagnie doit transporter du gravier vers trois sites de construction, S1, S2 et S3 ; La compagnie achète ce gravier de deux fournisseurs F1 et F2. La compagnie devra louer des camions pour assurer le transport du gravier des fournisseurs vers les sites de construction. Chaque camion coûte 50€ et peut transporter jusqu’à 5 tonnes du gravier. Les autres données du problème sont représentées dans le tableau suivant, qui indique : • Pour chaque site de construction et chaque fournisseur, le prix (en €) de chargement par tonne • Pour chaque fournisseur, l’offre, soit le nombre de tonnes de gravier disponibles • Pour site de construction, la demande, soit le nombre de tonnes de gravier demandées. Le problème consiste à minimiser le coût total afin de transporter le gravier des fournisseurs vers les sites de construction. On note par : le nombre de tonnes de gravier transportées entre le fournisseur et le site le nombre de camions utilisés pour transporter du gravier entre le fournisseur et le site 1. Modéliser le problème sous forme d’un PL en nombres entiers (en fonction de 2. Utiliser la méthode de séparation et évaluation pour trouver la solution du problème. Sites Fournisseurs S1 S2 S3 Offre (tonnes) F1 130 160 150 18 F2 180 150 160 14 Demandes (tonnes) 10 5 10 II. Problèmes non linéaires Exercice 8 : Un atelier peut fabriquer des articles de deux types A1 et A2, sur une machine donnée, disponible 100 heures par mois compte tenu des heures de réglage et d’entretien. Les articles de type A1 sont fabriqués à la cadence de 50 articles par heures, et les articles de type A2 sont fabriqués à la cadence de 25 articles par heure .La capacité d’absorption du marché étant limitée, on ne peut écouler par mois plus de 3000 articles de types A1, ni plus de 2000 articles de types A2. En raison d’un système de prix dégressifs consentis aux clients, le prix de chaque article décroît légèrement avec la quantité vendue: ainsi, un article de type A1 rapporte 30(1- x1/6000) dh lorsqu’on en vend x1 , et un article de type A2 rapporte 20(1- x2 /4000) dh lorsqu’on en vend x2 . Montrer que le problème de l’atelier peut être mis sous la forme d’un programme non linéaire (PNL) puis donner la solution optimale par Matlab. Exercice 9 : Une entreprise spécialisée en télécommunication voudrait installer une antenne pour connecter 4 nouveaux clients importants. Cette antenne doit se trouver au plus proche de chaque client, en donnant priorité aux meilleurs clients. Pour chaque client l’entreprise connait, selon le graphe suivant : ü Sa localisation (coordonnées (x,y)) ü Le nombre d’heures de communication par mois (0 ; 12) 200h (5 ; 10) 200h Antenne (x,y) * 150h (10 ;5) 300h (12 ;0) 1. Modéliser ce problème sous forme d’un programme non linéaire sans contraintes. 2. Donner la solution par Matlab. Supposons que l’entreprise veut installer une troisième antenne par rapport aux deux autres déjà installées dans les positions (-5 ;10) et (5 ;0). On interdit le placement de cette troisième antenne à moins de 10 km des antennes existantes. 3. Montrer que le nouveau problème se modélise sous forme d’un programme non linéaire sous contraintes inégalités (P). 4. Trouver la solution par Matlab. uploads/Finance/ tdtp.pdf