Licence d'informatique L3 Programmation Linéaire 2010-2011 TP - Problème de Déc
Licence d'informatique L3 Programmation Linéaire 2010-2011 TP - Problème de Découpe (suite) Dans la première partie du TP, nous avons vu que la di culté du problème é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 1 : Résoudre le programme linéaire (P) ci-dessous, pour les motifs courants. Z = n X j=1 xj (Min) sous n X j=1 aijxj ≥bi ∀i = 1, . . . , 4 xj ≥0 ∀j = 1, . . . , n Soit y = (y1, y2, y3, y4) la solution duale optimale obtenue. Résoudre le programme linéaire en nombre entier (PE) suivant. W = y1a1 + y2a2 + y3a3 + y4a4 (Max) sous 45a1 + 36a2 + 31a3 + 14a4 ≤100 aj ≥0 ∀j = 1, . . . , 4 aj entiers ∀j = 1, . . . , 4 Notons w∗la valeur optimale obtenue. Étape 2 : si w∗> 1 : la solution obtenue fournie un nouveau motif, donc une nouvelle variable à introduire dans le programme linéaire (P). Retour à l'Étape 1 . sinon : Arrêt. La solution courrante du problème (P) est optimale. Raskmey Phan - Arnaud Mary - Pierre Bouges Implémentation Réaliser une fonction qui résout le sous-problème. Cette fonction prend en paramètre un vecteur y = (y1, y2, y3, y4) qui dé nit les coe cients de la fonction objective, et renvoie un vecteur a = (a1, a2, a3, a4) 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 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 ini- tiaux 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 y1, y2, y3, y4 ? Rapport Vous devez rendre un rapport (au format .pdf) et le code source de votre programme au plus tard le 22 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 : nom1_nom2.tar. Les chiers devront s'extraire dans le répertoire Nom1_Nom2. L'exécutable doit s'appeler decoupe. Le code source devra aussi contenir un Makefile 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 uploads/S4/ probleme-de-decoupe-suite-pdf.pdf
Documents similaires
-
22
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jan 04, 2021
- Catégorie Law / Droit
- Langue French
- Taille du fichier 0.1101MB