TD Recherche Opérationnelle [PDF]

Zitiervorschau

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

1) CONCEPTS GENERAUX EN THEORIE DES GRAPHES Exercice 1 : 1. Définir les mots et expressions suivants : Graphe, Chemin, Arc, Arête, Chaîne, Cycle, Chemin, Circuit, Graphe orientés ; Graphe non orientés ; 2. Quand dit-on qu’un graphe est connexe ? qu’un graphe est fortement connexe Qu’est ce qu’un composant connexe ? 3. Représentations d’un graphe Donner la Matrice d’adjacence et la Matrice d’incidence du graphe suivant :

4. Soit le graphe suivant :

a. Donner un circuit partant de A et passant par G b. Donner un circuit élémentaire à partir de A c. En considérant le graphe comme non orienté idem question (a) et (b) 1/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

Exercice 2 : Cinq étudiants : A, B, C, D, et E doivent passer certains examens parmi les suivants : UE1, UE2, UE3 , UE4, UE5 et UE6. Les examens ne se tiennent qu’une seule fois. Chaque étudiant ne peut passer qu’un examen par jour. La liste des inscriptions aux examens est la suivante : A UE1, UE2, UE5 B UE3, UE4 C UE2, UE6 D UE3, UE4, UE5 E UE3, UE6 1. Combien d’examens peut-on effectuer par jour ? 2. Quel est le nombre minimal de jours nécessaires pour faire passer tous les examens ? Exercice 3 : 1. Soit le graphe suivant muni d’une valuation des arcs. Donner la séquence de nœuds formant le chemin entre A et J dont la somme des valuations des arcs est la plus faible. Vous préciserez alors sa valeur.

2/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

2. Soit, la représentation des routes à sens unique entres les villes V0 et V5. Trouver à l’aide de l’algorithme de Dantzig le plus court chemin pour quitter de la ville V 0 à la ville V5.

2 V1

3 6

V3

7

2

6

V5

1

V0

8

2

1

V2

V4

Exercice 4 : La méthode matricielle (N x N) est définie comme permettant de déterminer les longueurs des plus courts chemins entre tout couple de nœuds d’un graphe. λij : longueur du plus court chemin du nœud i au nœud j et  i , j

(m )

la longueur du plus

court chemin contenant au maximum m arcs de i à j. A(ai,j) la matrice des liens directs. Définition :   i ,i

(0)

=0

i

et  i , j

(0)

 

=0

i  j

 Itération (jusqu’à m = 1 .. N – 1):  ij

(m )



 Min  ij

( m 1 )

,  ik

( m 1 )

 a kj

 k  1,..., n

 i,j

Déterminer par la méthode matricielle la longueur des plus courts chemins entre chaque couple de nœuds du graphe suivant : 4 A 8

B

3 -6 3

4

4

2 D

C 5

3/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

2) LE PROBLEME CENTRAL DE L’ORDONNANCEMENT Exercice 1 On considère un projet formé de 6 activités élémentaires. Le tableau qui suit indique leur durée, leurs contraintes d'antériorités et leur utilisation de ressources par jour.

1. Calculer les dates au plus tôt et au plus tard des débuts des tâches. 2. Calculer les marges totales des activités. 3. Préciser, pour l'ordonnancement au plus tôt, la courbe donnant l'histogramme des ressources utilisées en fonction du temps. 4. Proposez des dates d'ordonnancement des tâches, respectant la durée minimale du projet avec histogrammes des ressources "plus équilibrées". Exercice 2 •

La marge totale d’une tâche i est le retard total qu’on peut se permettre sur i sans remettre en cause la date de fin du projet MT(i)=dptard(i)-dptôt(i).

•

Les tâches critiques ont une marge nulle. Tout retard sur leur exécution entraîne un retard global sur le projet

•

Un chemin est critique s’il relie Début à Fin et s’il ne contient que des tâches critiques

Vous êtes chargé de la planification d'un chantier qui nécessite le traitement de 9 tâches décrites dans le tableau suivant. Il p eut être nécessaire, pour traiter une tâche donnée, (par ex. F) que le traitement d'autres tâches soit terminé (ici C et E). De plus, on peut choisir d'accélérer le traitement d'une tâche donnée, moyennant un surcoût par jours de réduction ; le nombre maximum de jours de réduction et le surcout dépendent de la tâche. 4/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

Tâches Dépendances Durées (Jrs) Réd. Max (Jrs) A 2 1 B A 7 2 C D 4 3 D 2 0 E A 3 1 F C, E 2 1 G A, F 3 1 H F, D 3 2 I B, H 3 0 1. Quelle est la durée minimale du chantier sans surcoût ?

Coût de réd. (1000/jr) 9 2 1 8 5 7 6

2. Peut-on effectuer le chantier en moins de 8 jours ? 3. Quelle est le coût minimal pour finir le chantier en 10 jours ? 4. Quelle est la durée minimale du chantier avec un surcoût de 15 au plus ? Exercice 3. Minimisation des coûts dans un problème d’ordonnancement. On considère un chantier qui fait intervenir les tâches A, B, C, D, E de durées respectives 10, 7, 1, 8 et 3 jours. La tâche A précède les tâches C et D, les tâches B et C précèdent la tâche E. Les tâches A, B, C, D, E supportent alors des frais directs (main d’œuvre, heures de machines, . . .) de 500, 200, 350, 150 et 200 Mille Franc CFA. D’autre part, l’entreprise supporte des frais indirects qui sont fonction de la durée du chantier tfin. Ces frais indirects comportent les salaires de l’encadrement, des frais de location de matériel, des frais d’assurance et des frais financiers. Le tout pour un montant de 200 + 40× tfin. Ils comprennent, en supplément du montant précédent, une pénalisation de 100 Mille Franc CFA par jour de retard au-delà du 16ième jour. 1. Tracer le graphe construit par la méthode des potentiels et déterminer le ou les chemin(s) critique(s). 2. Même question mais en utilisant cette fois la méthode PERT. 3. Ecrire le problème de calcul des dates au plus tôt sous forme de programme linéaire. 4. Les durées des tâches B, D,E peuvent être réduites jusqu’à 5,3 et 1 jours au prix d’accroissements des coûts de 120, 30 et 100 Mille Franc CFA par jour. En utilisant le graphe de la question 2, comment réduire progressivement la durée totale tfin des travaux de façon à ce que le coût direct soit toujours minimum. 5. Décrire par un graphique l’évolution du coût direct et du coût indirect en fonction de la durée tfin des travaux sur le chantier. Quelle valeur donner à cette durée ? 5/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

3) PROBLEME D’AFFECTATION Exercice 1 : Problème d’affectation : Des élèves (A, B, C, D, E) choisissent leur affectation dans des chambres (a, b, c, d, e) selon le tableau de préférence (dans l’ordre décroissant) suivant : A B C D E

a 1 1 3 1 2

b 2 4 2 2 1

c 3 2 1 3 4

d 4 5 5 5 3

e 5 3 4 4 5

Proposer une affectation permettant de satisfaire au mieux les demandes. 1. Selon une méthode consistant à faire apparaître un 0 (par exemple en ligne A). Sur quelle ligne apparaît-il un problème ? Quelle est la première affectation proposée? 2. Selon une méthode par modélisation sur un réseau de transport. a. Donner le réseau (que représentent les nœuds, que représentent les arcs ?). b. Donner la capacité des arcs. Prendre comme arcs saturés les 0 du tableau de la question (1). c. Quelle(s) conclusion(s) en tirez-vous ? 3. Selon la méthode hongroise. Quelles affectations proposez-vous ? Exercice 2 : Dans un groupe, il y a 7 filles et 7 garçons. Chaque fille établit une liste de garçons avec lesquels elle accepterait de se marier : Filles Anne Brigitte Christine Dorothée Florence Elodie Géraldine

Garçons choisis Olivier, Paul Marc, Noël Olivier, Raoul Thierry, Marc, Noël Thierry, Marc, Noël Thierry, Marc, Raoul Stéphane, Olivier

1. Reformuler le problème sous la forme d’un problème d’affectation. 2. A l'aide de la méthode hongroise, déterminer le nombre maximum de couples et leurs compositions dans ce problème d'affectation. 3. Retrouver les résultats précédents à l'aide d'un réseau de transport sur lequel on cherchera un flot complet en partant d'un flot au jugé nul sur chaque arc, puis un flot maximal à l'aide de l'algorithme de Ford-Fulkerson. 6/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

4) FLOT DANS UN RESEAU DE TRANSPORT Exercice 1. Pourvoi de postes administratifs. L’administration veut pourvoir, dans quatre villes, des postes correspondant à un certain niveau de qualification. Le personnel requis est issu de trois centres de formation qui s’adressent chacun à des candidats de profils différents (scientifiques, techniciens, littéraires). Ces centres notés S ; T et L peuvent former un maximum de 10; 15 et 16 personnes alors que les quatre villes notées A; B ; C et D disposent de 10; 10; 12 et 9 postes. Les services de chaque ville expriment des vœux concernant l’origine des agents. On obtient ainsi les souhaits des villes : – – – –

ville A : au moins 3 scientifiques et au plus 4 littéraires. ville B : au moins 3 scientifiques. ville C : au plus 5 techniciens et au plus 4 littéraires. ville D : au moins 2 scientifiques et au plus 3 littéraires.

1. Construire le graphe correspondant à ce problème d’affectation en encadrant les bornes inférieures sur les flux par des parenthèses et les bornes supérieures par des barres. Par exemple : |4| et (3). 2. On considère une première affectation dans laquelle :  Le centre S fournit resp. 3; 3; 2; 2 agents aux villes A; B ; C ; D  Centre T : 3; 3; 5; 4.  Centre L : 4; 4; 4; 3. Reconstituer sur le graphe le flot correspondant. En utilisant l’algorithme de marquage du flot maximum, cherché si on peut pourvoir tous les postes. 3. Étant donnés les résultats du marquage en fin d’algorithme, quels sont les arêtes pour lesquelles une réévaluation des bornes (supérieures ou inférieures) pourrait conduire à une augmentation du flot ? 4. L’administration demande aux services de la ville B de réduire à 2 leur demande en scientifiques. Peut-on alors pouvoir tous les postes ? Commenter, en termes de transferts de flots, l’opération correspondante.

7/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

Exercice 2: Adduction d’eau Trois villes J, K et L, sont alimentées en eau grâce à 4 réserves A, B, C et D. Les réserves journalières disponibles sont de 20, 15, 20 et 15 milliers de m3 respectivement pour A, B, C et D. Le réseau de distribution est schématisé par le graphe ci-dessous (les débits maximaux, en milliers de m3 par jour, sont indiqués sur chaque arc). 10

A

J

E

7

6 7

B

12

10 7

C

7 D

15

F

10

H

10 1

30

K

7 I

18

7

10 L

G

1. Déterminer un flot maximal pouvant passer dans le réseau actuel. 2. Déterminer la valeur du flot optimal pouvant passer dans le réseau actuel. 3. La valeur de ce flot est jugée nettement insuffisante, aussi le conseil intercommunal décide-t-il de refaire les canalisations (A, E) et (I, L). Déterminer les capacités à prévoir pour ces deux canalisations et la valeur du nouveau flot optimal. 4. Devant l’importance des travaux, le conseil intercommunal décide de ne pas refaire les deux canalisations en même temps. Dans quel ordre doit-on entreprendre leur réfection de façon à augmenter, après chaque tranche de travaux, la valeur du flot optimal passant dans le réseau? 5. Quelles sont, après chaque tranche de travaux, les valeurs des flots optimaux ? Exercice 3 : Réseau de télécommunication Soit un réseau de télécommunication composé de 6 nœuds A, B, C, D, E, F. Chaque lien du réseau est muni d'une bande passante (en Mo/s) et d'un coût de transmission unitaire. Les unités d'information qui circulent dans ce réseau doivent être acheminées de a et b vers e et f. On désire déterminer le débit maximum de ce réseau, tout en minimisant le coût total de transmission de l'information : formuler ce problème comme un problème vu en cours, puis le résoudre. Lien Bande passante Coût unitaire

(A, C) 3 2

(A, D) 2 1

(B, C) 2 2

(C, D) 2 2

(C, E) 5 6

(D, F) 3 3 8/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

5) PROBLEME DU TRANSPORT Exercice 1 : Soit une entreprise disposant de trois dépôts (A, B et C) contenant respectivement 20, 10 et 35 tonnes de marchandises. Elle dispose de trois magasins (D, E et F) qui ont besoin respectivement de 25, 20 et 20 tonnes de marchandises. L’objectif est d’établir le meilleur plan de transport des marchandises de A, B et C vers D, E et F. La matrice suivante représente les possibilités en transport en fonction des différents sites : D 15 5 10

A B C

E 10 0 5

F 0 10 5

1. A quel problème formel cet exercice se ramène-t-il ? 2. Proposer une modélisation en fonction de ce problème 3. Effectuer la résolution et expliciter votre raisonnement. Exercice 2 : Le problème qui se pose est celui des coûts de transport : il y a un coût unitaire de transport entre dépôts et magasins et ces coûts varient selon les départs et destinations. Par exemple le coût de transport d’une unité entre le dépôt D1 et le magasin B est de 5 mille francs CFA. Si vous devez transporter 70 unités entre ces deux lieux cela vous coûtera 500*70 = 35.000 Fcfa. Le tableau suivant donne à la fois les coûts unitaires de transport et rappelle les quantités désirées et disponibles : A

B

C

D

E

Disponible

D1

8

5

3

2

6

220

D2

4

2

3

5

8

440

D3

5

4

2

6

7

340

Demande 150 200 300 250 100 1. Proposer la "solution du coin Nord Ouest", puis dessiner son graphe de transport. 2. Passer de cette de solution de base à une autre, plus économique. Qu’elle est le coût ? 3. Utiliser la procédure de différence maximale (ou méthode de Bales-Hammer) pour trouver une autre solution de base. Qu’elle est son coût ? 9/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

6) PROGRAMMATION LINEAIRE Exercice 1 : On considère le problème suivant : (P) :

max Z= x1 +3x2 sous les contraintes x1 + x2 ≤ 5 x1 ≤ 4 x2 ≤ 3 x1, x2 ≥ 0 1) Trouver par la méthode de graphique la solution du problème. 2) Résoudre le problème par la méthode du simplexe. 3) On remplace la fonction objectif par : Z= 3x1 + 2x2. Déterminer la nouvelle solution. 4) Trouver le dual du problème (P) et présenter son tableau de simplexe. 5) Eliminer les variables artificiels du tableau de simplexe. Exercice 2 : Soit le problème de programmation linéaire: max Z = x1 - x2 Sous les contraintes  2 x1  x 2  4   x1  2 x 2  2   x1  x 2  5 x , x2  0  1

1. Résoudre graphiquement ce problème de programmation linéaire. 2. Résoudre maintenant par la méthode simplexe. 3. Écrire le problème dual associé. 4. Résoudre le problème dual et interpréter le résultat. Exercice 3:La route du sel Au quatorzième siècle, un Touareg compte gagner un peu d’or en investissant dans des dromadaires qu’il sait pouvoir revendre à Tombouctou. Comme sa route passe par Taoudeni, il pense aussi y acheter du sel pour tirer d’avantage de bénéfice de son voyage. Il sait qu’il pourra obtenir au terme de son voyage 10 po (pièce d’or) de bénéfice par dromadaire, et 1 pa 10/11

Université de Ngaoundéré Faculté des sciences Département de Mathématiques et Informatique

Année académique 2019/2020 Semestre 6

TD DE RECHERCHE OPERATIONNELLE

(pièce d’argent, 1 po = 10 pa) de bénéfice par kg de sel. Avant toute chose il faut déjà qu’il achète ces dromadaires et ce sel. Chaque dromadaire lui coûte 10 po, et chaque kg de sel 0,2 pa. Il peut investir 65 po. Sachant qu’un dromadaire peut transporter jusqu’à 150 kg de sel, comment ce Touareg doit investir son pécule pour tirer le bénéfice maximal de son investissement ? Exercice 4: Une histoire de fromage Une laiterie s’est spécialisée dans deux fromages. Le premier est un AOC qui exige plus d’heures de travail et un lait en provenance d’une région bien précise. Le second demande moins de travail, et peut être fabriqué avec n’importe quel lait. Par contre sa vente dégage une marge moindre. La laiterie dispose de 21 000 heures de travail annuel, elle reçoit 4 millions de litres de lait de la zone AOC, et 6 millions de litres d’autres zones. Le tableau suivant indique les ressources nécessaires pour produire 1 tonne de fromage. Fromage Fromage 1 (AOC)

heures de travail par tonne de fromage 30 h

litres de lait par tonne de fromage 10 000 L

15 h

7 500 L

Fromage 2

Sachant qu’un kilo du fromage AOC dégage une marge de 300 Fcfa et qu’un kilo de l’autre fromage seulement 100 Fcfa, quelle production doit fabriquer cette laiterie pour optimiser ses bénéfices ? Exercice 5 : Problème électrique Un revendeur d’électricité a promis à sa clientèle qu’au moins 25% de son électricité serait d’origine renouvelable. Il a calculé que pour l’année qui arrive il aura un marché de 18 TWh (térawattheure). Il a aussi présélectionné trois fournisseurs à qui il va acheter son électricité en gros. Voici les quantités (en TWh), le taux d’électricité renouvelable et la marge dégagée (en k euro/TWh) que peuvent lui fournir ces trois producteurs.

Producteur 1 Producteur 2 Producteur 3

% d’électricité renouvelable 10 % 46 % 100 %

Quantité d’électricité achetable (TWh) 25 6 4

Marge (k Euro/TWh) 900 700 500

11/11