Cours et Exercices

Voir la solution Déterminer les composantes fortement connexes des graphes orient´es suivants en utilisant un algorithme de marquage : Voir la solution

Voir la solution a) Donner la matrice d’incidence sommets-arêtes et la matrice d’adjacence sommets-sommets du graphe suivant : b) Donner la matrice d’incidence sommets-arcs et la matrice d’adjacence sommets-sommets du graphe suivant : c) Représenter graphiquement les graphes associés aux matrices d’incidence sommets-arcs suivantes : d) Représenter graphiquement le graphe associé `a la matrice d’adjacence sommets-sommets suivante : Voir la solution

Partie 1 On remarque que pour produire 1000 pièces, l’usine doit disposer d’au moins 1 tonne de M1, 0.6 tonne de M2 et 0.3 tonne de M3. Le dictionnaire D2 est optimal. On y lit qu’il faut commander x1 = 1/2 tonne d’alliage 1, x2 = 19/8 tonne d’alliage 2, et pas d’alliage 3. L’excédent de métal M2 est de 39/4 tonnes. Le Coût minimal d’achat est de 31/8 kFrs. Partie 2 a) Le plan de production optimal est de produire x1 = 1200 boîtes de type 1 et x2 = 3400 boîtes de type 2, ce qui donne un chiffre d’affaires de z = 20 600 CHF. b) i) Remarquons premièrement que, pour chaque minute de travail supplémentaire, le chiffre d’affaires augmente potentiellement de 1 CHF. Cette valeur correspond au prix marginal associé à la contrainte sur le nombre de minutes disponibles (variable duale   λ* 2 ) Comme l’étudiant demande à être payé 0.5 CHF (< 1 CHF) la minute, l’entreprise peut donc entrer en matière. Afin de déterminer la durée de l’engagement, il faut effectuer une analyse d...

INITIATION A L'ORGANISATION ET A LA RECHERCHE OPERATIONELLE Voir la solution Partie 1 Une usine sidérurgique doit produire 1000 pièces identiques nécessitant chacune, respectivement, 1, 0.6 et 0.3 kg de métaux M1, M2 et M3. Ces métaux sont présents dans différents alliages que l’usine achète sur le marché. Le prix et la composition (en %) de ces alliages sont précisés dans la table suivante : a) Modéliser le problème de la recherche d’un plan d’achat des alliages, minimisant les frais de l’usine et lui assurant de pouvoir produire les 1000 pièces demandées, sous forme d’un P.L. canonique (PLP). b) Etablir le dual PLD de PLP. c) Résoudre PLP en utilisant l’algorithme dual du simplexe (phase II). d) Donner la solution optimale de PLD. Partie 2 Une entreprise disposant de 8 000 m2 de carton en réserve fabrique et commercialise 2 types de boites en carton. La fabrication d’une boîte en carton de type 1 ou 2 requiert, respectivement, 1 et 2 m2 de carton ainsi que 2 et 3 mi...

Appliquant l’algorithme du simplexe, on obtient successivement 2) On commence par introduire les variables d’écart : On en déduit le dictionnaire de départ : Le dictionnaire D4 est optimal. La solution optimale est : Et la valeur optimale est z∗ = 37. Revenir à liste des exercices

Voir la solution 1) Résoudre le programme linéaire suivant à l’aide de l’algorithme du simplexe : Spécifier à chaque itération les variables basiques et hors base ainsi que le point extreme visité. 2) Résoudre le programme linéaire suivant à l’aide de l’algorithme du simplexe : Voir la solution Voir la liste des exercices

1) a) Le domaine des solutions admissibles est : b) On d´etermine la solution optimale graphiquement en représentant les lignes de niveau de la fonction objectif. La solution optimale est x = 3 et y = 2 et sa valeur est égale à 13. 2)  a) La représentation graphique du problème est la suivante :  b) Le problème dual associé se formule comme suit : Minimiser : Par le théorème des écarts complémentaires, on obtient : Voir la liste d'exercice