lp_solve est un programme permettant de résoudre les programmes linéaires, et les programmes linéaires en nombres entiers. Il permet de résoudre des petits programmes linéaires, mais n'est pas suffisant pour les besoins en entreprise, où il est nécessaire d'utiliser de meilleurs logiciels (comme cplex). Il est cependant suffisant pour les besoins de nos TPs.

Il est également possible de l'utiliser comme une bibliothèque ("library") pour des situations plus compliquées

Le but de ce premier TD est de prendre en main ce logiciel.

Les fichiers nécessaires sont ici.

lp_solve sous windows

Pour utiliser lp_solve sous Windows, il faut télécharger le binaire à l'adresse suivante:

version 32 bits

Les fichiers .lp

Le programme lp_solve permet de résoudre des programmes linéaires écrits dans un fichier au format .lp.

Attention Tous les solveurs de programme linéaire appellent leur format .lp mais le format .lp de lp_solve est différent de celui de cplex, qui est différent de celui de Xpress.

Voici un exemple de tel fichier

max: 5x1-3x2;
x1 - x2 >= 2;
2x1 + 3x2 <= 4;
-x1 + 6x2 = 10;

Recopier le programme précédent dans un fichier example1.lp puis lancer la commande
```
lp_solve example1.lp
```

Exercice 1

Récupérez dans l'archive TP1.zip le fichier brasseur.lp. Lancer la commande suivante et vérifiez que le tableau final est quasi identique au tableau vu en cours. Notez en particulier les différences.
```
lp_solve  -s0 -S7 brasseur.lp
```
Pour la majorité des problèmes, la commande suivante est suffisante:
```
lp_solve  -s0 -S4 brasseur.lp
```
Elle donne le même résultat sans le tableau.
Utiliser la commande pour répondre aux questions suivantes (questions vues en cours):
- A quel prix doit-on vendre la brune pour qu'il devienne intéressant d'en produire ?
- A quel prix doit-on vendre la blonde pour qu'il devienne intéressant de produire de la brune ?
- Quelle est la ressource critique ? A quel prix faut-il l'acheter si on souhaite produire plus ? Quelle quantité maximum doit-on en acheter, avant que le plan de production ne change ?

Exercice 2

Déterminer la solution optimale de l'exemple 1 ci-dessus.
Changer le sens de la 3ème contrainte pour obtenir -x1 + 6x2 <= 10.
Quelle est maintenant la valeur du problème ainsi que la valeur des variables ?
Déterminer la valeur des variables duales optimales

Entrer le nouveau problème suivant (appelé pb2):

  Max	x1 + 2x2 + 3x3 
  s.c.	−x1 + x2 + x3 <= 20
        x1 − 3x2 + x3 <= 30 
        0 <= x1 <= 40 , x2 >= 0

Déterminer la solution optimale du problème (pb2).
Ajouter la contrainte suivante à (pb2) : x1 + 2x2 + 3x3 <= 50
Quelle est la nouvelle solution optimale ?
Lire la documentation du format .lp (en particulier les exemples)
Résoudre les deux problèmes pb1 et pb2 en considérant désormais que les variables sont entières.

Exercice 3: Plan de production

A partir de maintenant, et pour tous les exercices, on se place dans les conditions du TP noté. Le rendu du TP noté est un fichier .t2t qui contient les réponses aux questions. Le fichier pour cet exercice s'appelle fichereponse.t2t et se trouve dans le .zip que vous avez téléchargé.

Pour chaque question des exercices, il faut donner en général deux réponses:

le fichier .lp s'il a été modifié (mettre uniquement les modifications), les commandes tapées et les lignes de l'affichage qui permettent d'obtenir la réponse
la réponse métier, c'est à dire une ou plusieurs phrases qui répondent très précisément aux questions demandées.

Une entreprise fabrique trois produits A, B et C. Chaque produit nécessite des matières premières et de la main-d’œuvre. Les quantités de matières premières et de main-d’œuvre nécessaires par unité de chaque produit sont données ci-dessous (données par semaine) :

Produit	Matières premières (kg)	Main d'oeuvre (h)	profit net (euros)
A	4	2	6
B	2	.5	2
C	1	3	4
Disponibilité	6000	4000

A cause de la capacité limitée d’entreposage, on ne peut pas fabriquer plus de 2500 unités des produits A, B et C au total. L’entreprise doit décider combien d’unités de chaque produit peut-elle fabriquer chaque semaine afin de maximiser le profit.

Montrer que ce problème peut être modélisé comme suit :

Max	6x1 + 2x2 + 4x3
s.c.	4x1 + 2x2 + x3 <= 6000
		2x1 + 0.5x2 + 3x3 <= 4000
		x1 + x2 + x3 <= 2500
		x1, x2, x3 >= 0

Décrire le plan de production optimal.
Déterminer les coûts marginaux (prix fictifs) des ressources.
Quel sera l’effet sur le profit total d’une diminution de 500 de la capacité d’entreposage ?
L’entreprise ne fabrique pas le produit B. L’une des raisons de cette situation est que le profit unitaire du produit B est trop faible. Quel est le profit unitaire minimal nécessaire pour envisager la fabrication du produit B ? Si ce niveau est atteint, quelle sera le nouveau plan de production optimal ?
Lire le fichier fichecorrige.t2t pour voir ce qui était attendu commes réponses à l'exercice.