Corrigé exercice recherche opérationnelle

Bonjour,

je suis étudiant en informatique en 1 ère année à l'INI en ALGÉRIE, j'aurai besoin de votre aide sur un sujet d'examen d'algorithmique. pouvez vous m'aider svp ?

Problème 1 (45 points au total) Le premier problème vous demande de formuler un programme linéaire à 3 variables de trois manières différentes (quatre si vous comptez également la formulation algébrique). Les deux premiers moyens sont assez naturels. La troisième voie est un peu complexe. Et la formulation algébrique peut sembler trop complexe. Dans la pratique, il ya des avantages à la formulation de programmes linéaires dans différents façons. Et il ya d'énormes avantages dans la formulation algébrique. (On peut exprimer des problèmes de grande taille efficacement sur un ordinateur en utilisant un langage de modélisation, qui est basé sur la formulation algébrique.) En outre, la formulation d'un PL de multiples façons donne un aperçu des modèles LP.

Accessoires & co. prévoit la production de trois types d'étuis pour les produits Apple: iPod, iPad, et iPhone. Les installations de production de l'entreprise sont telles que si nous consacrons toute la production à d'étuis à l'iPod, nous pouvons produire 6000 en une journée. Si nous consacrons la production pour iPhone ou iPad, nous pouvons produire 5000 ou 3000 étuis en un jour. Le calendrier de production est d'une semaine (5 jours de travail), et la production de la semaine doit être stockée avant distribution. Le stockage de 1000 étuis iPod (emballage inclus) prend jusqu'à 40 pieds cubes d'espace. Le stockage de 1000 étuis iPhone (emballage inclus) prend jusqu'à 45 pieds cubes d'espace, et stocker 1000 étuis iPad (emballage inclus) prend 210 pieds cubes d'espace. L'espace total de stockage disponible est de 6000 pieds cubes. En raison des accords commerciaux avec Apple, Accessoires & co. doit fournir au moins 5000 étuis iPod et 4000 étuis iPad par semaine afin de renforcer la diffusion du produit. Le département marketing estime que la demande hebdomadaire pour les étuis
2
iPod , iPhone, et iPad ne dépasse pas 10 000 et 15 000, et 8000 unités, respectivement, donc l'entreprise ne veut pas produire plus de ces quantités d'étuis pour iPod, iPhone et iPad. Enfin, le profit net par chaque étui iPod, iPhone, et iPad est de 4 $, 6 $, et 10 $, respectivement. L'objectif est de déterminer un horaire hebdomadaire de production qui maximise le bénéfice net total. (A) (10 points) Donnez une formulation de programmation linéaire pour le problème. Commencez par l'expression des hypothèses que vous faites. Préciser la nature de chaque contrainte (sauf celles de non négativité). Pour cette première formulation, les variables de décision devraient représenter la proportion de temps passé chaque jour sur la production de chacun des éléments:

x1 = Proportion de temps consacré chaque jour à la production de l'étui iPod,
x2 = Proportion de temps consacré chaque jour à la production de l'étui 'iPhone,
x3 = Proportion de temps consacré chaque jour à la production de l'étui iPad.

(Différentes formulations seront nécessaires pour les parties (b) et (c).) (B) (10 points) Donnez une seconde formulation du programme linéaire pour le problème. Préciser la nature de chaque contrainte (sauf celles de non négativité). Pour cette seconde formulation, les variables de décision devraient représenter le nombre d'éléments de chaque type de produit au cours de la semaine:

y1 = Nombre d'étuis iPod produits au cours de la semaine,
y2 = Nombre d'étuis iPhone produis au cours de la semaine,
y3 = Nombre d'étuis iPad produits au cours de la semaine.

Les données du problème sont les mêmes, mais vous devez vous assurer que tout correspond aux nouvelles variables de décision. (C) (5 points) Écrire une troisième formulation du programme linéaire pour le problème. Préciser la nature de chaque contrainte (sauf celles de non négativité). Supposons que chaque journée de travail dispose de 8 heures de travail. Pour cette troisième formulation, les variables de décision devraient être:3

z1 = Nombre d'heures consacrées à la production d'étuis iPod en une semaine,
z2 = Nombre d'heures consacrées à la production d'étuis iPhone en une semaine,
z3 = Nombre total d'heures de production employés au cours de la semaine.

Exprimez la fonction objectif en milliers de dollars. Les données du problème sont les mêmes mais vous devez vous assurer que tout correspond aux nouvelles variables de décision. (D) (5 points) Quelle est la relation entre les variables z1, z2, z3 de la partie (c), et les variables x1, X2, x3 de la partie (a) de ce problème? Donner une formule pour calculer z1, z2, z3 à partir de x1, x2, x3. (E) (5 points) Présentation Excel Résoudre le problème (A), en utilisant Excel Solver, en suivant les lignes directrices données dans le guide Excel Solver qui vient avec cet ensemble de problème. Faites attention à la formulation dans Excel : donner les Shadow Prices et interpréter. (F) (10 points) Donnez une formulation algébrique du problème de calendrier hebdomadaire de production décrit ci-dessus en utilisant la notation suivante:
* n est le nombre de types de produits,
* xj est le nombre de jours consacrés à la production de produits de type j,
* pj est le nombre d'éléments de type j qui peuvent être fabriqués en une seule journée, en supposant que le processus est consacrée à des produits de type j.
* P représente le nombre de jours de production en une semaine,
* sj est l'espace de stockage requis par un produit de type j,
* S est l'espace de stockage total disponible pour la production de la semaine,
* rj est le profit unitaire pour chaque produit de type j,
* dj est la demande maximale hebdomadaire pour un article de type j.
* bj est la demande hebdomadaire minimum à un envoi de type j.
4

merci par avance