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;

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 : vérifiez que vous trouvez bien la même solution à l'exercice 1 de la feuille de TD avec le solveur que celle que l'on a determinée graphiquement.

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 3 : 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 4 : 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 5 : 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 6 : 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 7 : 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

IV. Problème de flot

On considère des graphes orientés et pondérés positivement qui sont encodés par leur matrice d'adjacence (0 représente le fait qu'il n'y a pas d'arc). Les poids sont des flottants. le format du graphe est le suivant :

• Le fichier contient la matrice ligne par ligne :

  0.0|2.1|3.2|0.0
  0.0|0.0|1.1|0.7
  0.0|0.0|0.0|4.3
  0.0|0.0|0.0|0.0
  

  correspond au graphe :
• La source est le sommet 0, s'il y a n sommet, c'est le sommet n-1 la destination.

Question 8 : Ecrire un programme qui prend en entrée un tel graphe, et écrit le programme linéaire qui calcule le flot maximal dans le graphe. En utilisant le solveur, vérifiez votre programme sur l'exemple (et l'exemple du cours).

Marchand de glace

Question 9 : Reprendre le problème du marchand de glace vu en cours. Trouver la solution optimale avec un coût de stockage de 20$ par tonne et un coût de réajustement de 50$ par tonne pour les demandes suivantes :

jan 350
fev 320
mar 440
avr 630
mai 630
jun 550
jui 680
aou 660
sep 350
oct 420
nov 380
dec 620

Question 10 : Observez le changement de stratégie à adopter quand le coût de stockage est nul.