Remerciez-le!

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

Probleme de decoupe suite pdf 1

Licence d'informatique L - Programmation Linéaire TP - Problème de Découpe suite E Dans la première partie du TP nous avons vu que la di culté du problème E était due au nombre important de motifs et au fait qu'il est di cile de les énumérer tous Nous avions alors limité la résolution à un nombre réduit et arbitraire de motifs Nous allons dans cette partie prendre en compte tous les motifs essentiels Pour cela nous utilisons une procédure qui détermine un motif intéressant c'est-à-dire une colonne à ajouter au programme linéaire Cette procédure est la suivante Algorithme de résolution du problème de découpe Initialisation Choisir un sous-ensemble de n motifs Étape Résoudre le programme linéaire P ci-dessous pour les motifs courants n Z xj j n sous aijxj ? bi j xj ? M in ??i ??j n Soit y y y y y la solution duale optimale obtenue Résoudre le programme linéaire en nombre entier PE suivant W y a y a y a y a M ax sous a a a a ? aj ? ??j aj entiers ??j Notons w ? la valeur optimale obtenue Étape si w ? la solution obtenue fournie un nouveau motif donc une nouvelle variable à introduire dans le programme linéaire P Retour à l'Étape sinon Arrêt La solution courrante du problème P est optimale Raskmey Phan - Arnaud Mary - Pierre Bouges C Implémentation Réaliser une fonction qui résout le sous-problème Cette C fonction prend en paramètre un vecteur y y y y y qui dé nit les E coe cients de la fonction objective et renvoie un vecteur a a a a a E représentant les coe cients de la nouvelle variable dans P Remarquons que a est un vecteur d'entiers Mettre en ? uvre l'algorithme de résolution du D problème de découpe proposé Pour aller plus loin Étudiez l'in uence des motifs initiaux utilisés Quelle est la condition sur les motifs initiaux pour que l'algorithme converge vers la solution optimale Que représente le problème PE par rapport au problème P Quelle interprétation peut-on donner aux variables y y y y Rapport Vous devez rendre un rapport au format pdf et le code source de votre programme au plus tard le avril Passé cette date une forte pénalité sera appliquée Le rapport comportera une dizaine de pages et doit au moins contenir les parties suivantes introduction présentation du problème et de la méthode de résolution explication des structures de données utilisées et des fonctions importantes de votre pro- gramme résultats réponses aux questions conclusion Le code source doit se trouver dans une archive nommée nom C nom tar Les chiers devront s'extraire dans le répertoire Nom Nom L'exécutable doit s'appeler decoupe Le code source devra aussi contenir un Make ?le dont les règles suivantes sont nécessaires all crée le programme demandé clean nettoie tout ce qui a été généré pendant la compilation du programme Raskmey Phan - Arnaud Mary - Pierre Bouges C