Tiêu đề °TD Recherche opérationnelle SMI5 FSR RABAT 20 21.pdf ✅

Universit ́e Mohammed V de Rabat Recherche Op ́erationnelle Facult ́e des Sciences Fili`ere : SMI 5 D ́epartement de Math ́ematiques 2020-2021 S ́erie N◦1 (Programmation Lin ́eaire) Exercice 1. Dans une entreprise de construction de mat ́eriel ́electrique, on dispose de 1200 h machine par mois et 1500 h ouvrier par mois. Les contacteurs n ́ecessitent 15 h par machine, 12 h par ouvrier et rapportent 20 dh par unit ́e. Les disjoncteurs n ́ecessitent 30 h par machine, 30 h par ouvrier et rapportent 45 dh par unit ́e. Les compteurs n ́ecessitent 20 h par machine, 25 h par ouvrier et rapportent 40 dh par unit ́e. Formuler ce probl`eme en terme de programmation lin ́eaire. Exercice 2. Un transporteur ind ́ependant dispose d’un camion de 5 tonnes de charge utile of- frant une capacit ́e maximale de 10 m3 . On lui propose de transf ́erer `a une certaine destination des marchandises en vrac diff ́erentes M1 et M2 pour lesquelles on lui offre 30 dh par tonne pour M1 et 20 dh par m3 pour M2. Les poids sp ́ecifiques sont de 1 tonne par m3 pour M1 et 0.25 tonne par m3 pour M2. Formuler ce probl`eme en un probl`eme de programmation lin ́eaire et donner une r ́esolution graphique. Exercice 3. `A faire `a domicile Une entreprise poss`ede 540 kg de cacahou`etes, 150 kg d’amandes et 90 kg de pis- taches. Elle pr ́epare et vend 4 types de paquets form ́es `a partir d’un m ́elange des 3 fruits secs. Le poids de chaque paquet est ́egal `a 0,5 kg. On donne : Type de paquet Contenance Prix de vente unitaire (en Dh) 1 Cacahou`etes seulement 26 2 Au maximum 50% de cacahou`etes Au moins 15% d’amandes 40 Au moins 10% de pistaches 3 Amandes seulement 51 4 Au moins 30% de cacahou`etes Au moins 20% d’amandes 52 Au moins 30% de pistaches Tous les paquets produits peuvent ˆetre vendus aux prix unitaire indiqu ́es ci-dessus. L’entreprise cherche `a d ́eterminer le m ́elange exact pour chaque type de produit ainsi que le nombre de paquets `a produire de chaque type. Formuler le probl`eme par la programmation lin ́eaire. Exercice 4. Une entreprise travaille seulement quatre jours par semaine (Jeudi, Vendredi, Sa- medi et Dimanche) pour fabriquer des tables m ́etalliques. La fabrication d’une table mobilise un ouvrier qualifi ́e pendant une p ́eriode de 30 minutes. Un ouvrier ne peut travailler que deux jours par semaine. Les deux jours travaill ́es par un ouvrier ne sont pas n ́ecessairement cons ́ecutifs ou ́eloign ́es l’un de l’autre. La dur ́ee de travail par jour est de 8 heures. 1
L’entreprise cherche `a minimiser le nombre d’ouvriers recrut ́es par semaine tout en assurant la fabrication d’au moins 560, 800, 700 et 900 tables respectivement le Jeudi, Vendredi, Samedi et Dimanche. Formuler le probl`eme sous forme d’un programme lin ́eaire. Exercice 5. On consid`ere le programme lin ́eaire :    M ax x1 − x2 + 4x3 + x4 2x1 − 2x2 + 2x3 + x4 = 4 x1 − x2 − x4 = 1 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 a) D ́eterminer tous les points extr ́emaux. b) En d ́eduire une solution optimale. Exercice 6. Utiliser la m ́ethode de simplexe pour r ́esoudre les programmes lin ́eaires suivants : a)    M ax 3x1 + 2x2 2x1 + x2 ≤ 2 3x1 + 4x2 ≥ 12 x1 ≥ 0, x2 ≥ 0 b)    M ax 3x1 + 2x2 + 3x3 2x1 + x2 + x3 ≤ 2 3x1 + 4x2 + 2x3 ≥ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 c)  `A faire `a domicile   M ax 5x1 + 3x2 + 3x3 3x1 + 2x2 + x3 = 9 4x1 + 3x2 + x3 = 13 13x1 + 9x2 + 4x3 = 40 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Exercice 7. D ́eterminer le programme lin ́eaire dual du programme lin ́eaire suivant :    M in 2x1 + 3x2 − 5x3 x1 + x2 − x3 ≥ 5 2x1 − x2 ≤ 4 x1 + x3 = 6 x1 ≥ 0, x2 ≤ 0 Exercice 8. Soit le probl`eme suivant :    M ax x1 + x2 + 3x3 x1 + x2 ≤ 4 x2 + x3 ≤ 6 x1 + x3 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Sans utiliser l’algorithme de simplexe, v ́erifier si la solution x1 = 2, x2 = 0, x3 = 6 est optimale. 2
Exercice 9. `A faire `a domicile Un agriculteur doit choisir entre deux types d’engrais A et B pour fertiliser ses terres. Ses terres requi`erent par hectare au moins 60 kg de potassium, 120 kg de calcium et 90 kg de sodium, et que d’autre part les paquets de A et B contiennent respectivement 1 kg de potassium, 3 kg de calcium, 3 kg de sodium et 2 kg de potassium, 2 kg de calcium et 1 kg de sodium. 1. Quelles sont dans ces conditions, les quantit ́es optimales de A et B `a utiliser par hectare lorsque les paquets de A et de B valent chacun 100 dh ? 2. Ecrire le programme lin ́eaire dual du programme lin ́eaire obtenu. Quelle est la ́ signification de ce programme lin ́eaire dual ? Exercice 10. Soit le programme lin ́eaire suivant :    M ax 2x1 + 5x2 + 9x3 x1 + x3 ≤ 4 x2 + 2x3 ≤ 6 x1 + x2 + 5x3 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Le tableau final de la m ́ethode de simplexe est : Variables de base x1 x2 x3 s1 s2 s3 Solution s1 0 0 -2 1 1 -1 2 x2 0 1 2 0 1 0 6 x1 1 0 3 0 -1 1 2 ∆j 0 0 -7 0 -3 -2 -34 D ́eterminer l’intervalle dans lequel on peut faire varier sans que la base optimale change dans les cas suivants : 1. b devient : b 0T = (4 + λ, 6, 8), 2. c devient : c 0T = (2 + λ, 5, 9), `A faire `a domicile 3. b devient : b 0T = (4, 6, 8 + λ) ou b 0T = (4, 6 + λ, 8 − λ). 4. c devient : c 0T = (2, 5, 9 + λ) ou c 0T = (2 − 2λ, 5 − λ, 9) 3
Universit ́e Mohammed V de Rabat Recherche Op ́erationnelle Facult ́e des Sciences Fili`ere : SMI 5 D ́epartement de Math ́ematiques 2020-2021 S ́erie N◦2 (Programmation Lin ́eaire en Nombres Entiers) Exercice 11. Soit le programme lin ́eaire Entier avec variables binaires suivant : (P E1)    M ax 16x1 + 18x2 + 15x3 x1 + 4x2 + 3x3 ≤ 7 x1; x2; x3 ∈ {0, 1} 1. R ́esoudre le PE1 par la m ́ethode de coupe de Gomory 2. R ́esoudre le PE1 par la m ́ethode de s ́eparation et ́evaluation `A faire `a domicile Exercice 12. Soit le programme lin ́eaire Entier suivant : (P E2)    M ax 5x1 + 4x2 x1 + x2 ≤ 5 10x1 + 6x2 ≤ 45 x1 ≥ 0, x2 ≥ 0 entiers 1. R ́esoudre le PE2 par la m ́ethode de coupe de Gomory `A faire `a domicile 2. R ́esoudre le PE2 par la m ́ethode de s ́eparation et ́evaluation 4