Langages recommandés : Java ou Python. Demandez-moi avant si vous souhaitez utiliser un autre langage de programmation.

I. Prise en main de lp_solve

Dans tout le TP, nous allons utiliser le programme "lp_solve", qui est un solveur de programmes linéaires.

Voilà un exemple de programme linéaire sous le format de base de lp_solve:

max: 2 x1 + x2;
x1 + 2 x2 <= 20;
3.2 x1 + x2 <= 15;

> lp_solve fichier.lp

Value of objective function: 12.77777778

Actual values of the variables:
x1                        1.85185
x2                        9.07407

int x1,x2;

Important : par défaut, lp_solve ne travaille qu'avec des variables positives. Si vous voulez autoriser les variables à prendre des valeurs négatives, il faut écrire :

free x1, x2;

Vous trouverez la documentation de lp_solve ici.

Question 1 : vérifiez que tout fonctionne correctement sur l'exemple ci-dessus. Quelles sont les valeurs optimales de x1 et x2 si on se restreint à des nombres entiers ?

Question 2 : Reprenez le cours et calculez

• La quantité de choux / carottes / concombres dans la ration alimentaire optimale.
• Le flot maximal dans l'exemple du cours (attention aux variables potentiellement négatives).

Question 3 : Reprenez le TD1

• Vérifiez que la solution graphique de l'exercice 1 est correcte.
• Prenez la spécification finale de l'exercice 2 et indiquez combien il faut fabriquer de pots, de vases, dépenser dans la publicité et payer d'heures supplémentaires.
• Donnez une répartition par tranche horaire dans l'exercice 4 qui optimise le nombre de policiers embauchés.

II. Un problème générique

On considère un problème plus général où l'on dispose de n types de marchandises M1, ..., Mn. Il y a k types de ressources utilisées pour confectionner les marchandises, R1, ... Rk. Chaque marchandise i rapporte un bénéfice de Bi pour chaque unité vendue.

Les différentes statistiques associées aux marchandises sont donnée dans un fichier texte formaté de la façon suivante :

M8|16|29|15|22|27|15|442
M9|28|12|25|15|19|24|436

Question 4 : En utilisant le fichier que vous pouvez récupérer ICI, écrivez un programme qui prend en entrée un tel fichier et écrit sur la sortie standard le programme linéaire associé, avec les contraintes que chacune des k ressources est limité à 1000 unités. Faîtes tourner le solveur dessus, quelle est le bénéfice optimal ? combien de marchandises différentes faut-il produire ? combien de temps a mis le solveur pour calculer la solution optimale ?

Question 5 : Rajoutez la contrainte qu'on ne peut plus faire de portions de marchandises, il faut en produire un nombre entier. Mêmes questions qu'à la question 3.

Question 6 : Essayez avec le fichier (beaucoup) plus volumineux que vous pouvez trouver ICI. Chaque ressource est maintenant limitée à 100.000 unités.

III. Un problème de découpe

Question 7 : Reprendre l'exercice de la feuille de TD sur la découpe de barres de métal et trouvez la solution optimale avec le solveur.

On considère maintenant que les tiges de bases font 5m et qu'on veut les découper en barres de longueurs 2m, 1.2m, 1m et 0.5m.

Question 8 : Ecrire un programme qui génère tous les découpages maximaux possibles. Adaptez-le pour générer le programme linéaire correspondant à une commande qui minimise le nombre de tiges utilisées pour produire 60 barres de 2m, 100 de 1.2m, 150 de 1m et 350 de 0.5m

Question 9 : Rendre générique votre programme de la Question 8 : on produit des barres de taille fixe T, et on a besoin de Ni barres mesurant Ti cm, pour i de 1 à n, donnés comme paramètres.

IV. Un problème de planification de tâches

On dispose de 9 tâches à effectuer, notée A, B, ..., I. Chacune prend un certain nombre de jours pour être réalisée. Il y a de plus des dépendances entre les tâches, certaines doivent attendre que d'autres soient achevées pour pouvoir commencer. Les dépendances et les temps sont récapitulées dans le tableau suivant :

Question 10 : On cherche à minimiser le temps total nécessaire à finir toutes les tâches. Modélisez le problème sous forme d'un programme linéaire, et résolvez-le avec lp_solve.

V. Approximation linéaire

On dispose d'un ensemble de points issus d'une expérience de chimie. On aimerait approximer le comportement des points par une droite, comme on l'a fait dans le cours. Le fichier contenant les points contient une ligne par point, avec d'abord son abscisse, puis son ordonnée :

89.43 270.86
47.91 146.5
61.69 187.64
57.33 174.77
3.47 13.39
...  

Question 11 : Ecrire un programme générique qui prend en entrée un nom de fichier contenant une liste de points, et la transforme en un programme linéaire pour calculer une droite d'approximation de la forme y=ax+b (vous pouvez simplement le sortir sur la sortie standard). On pourra l'essayer sur

• ce petit fichier.
• ce gros fichier.

Question 12 : Affichez les points et la solution optimale calculée par le solveur pour les deux exemples.