Pour mieux préparer au TP noté de la semaine prochaine, ce TP utilise le même format.

Exercice 1: Plan de production

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
```
- Réponse métier:
  - Variables de décision : x1 (resp. x2, x3) nombre d’unités du produit A (resp. B,C) >= 0.
  - Contraintes : Matières premières ; Main d’œuvre ; Stock.
  - Objectif : Maximiser le profit.
- Fichier .lp
```
max: 6 x1 + 2 x2 + 4 x3;
MatPrem:  4 x1 + 2   x2 +   x3 <= 6000;
MainOuvr: 2 x1 + 0.5 x2 + 3 x3 <= 4000;
Stock:      x1 +     x2 +   x3 <= 2500;  
```
Décrire le plan de production optimal.
- Commandes lp_solve et résultat lp_solve:
```
mamachine> lp_solve  toto.lp

Value of objective function: 10000

Actual values of the variables:
x1                           1400
x2                              0
x3                            400
```
- Réponse métier:
  Plan de production optimal :
  - 1400 unités du produit A
  - 400 unités du produit C
  - Aucune unité du produit B.
    Profit : 10 000.

Déterminer les coûts marginaux (prix fictifs) de chacune des ressources.

Commandes lp_solve et résultat lp_solve:

mamachine> lp_solve -S4 toto.lp
...
Dual values with from - till limits:
                           Dual value            From            Till
MatPrem                             1        1333.333            8000
MainOuvr                            1            3000        6333.333
Stock                               0          -1e+30           1e+30
x1                                  0          -1e+30           1e+30
x2                               -0.5           -2000        1076.923
x3                                  0          -1e+30           1e+30
...

Réponse métier: Le coût marginal d’une ressource correspond à la variable duale de la contrainte associée.
- Matière premières : 1.0
- Main d’œuvre : 1.0
- Stock : 0.0

Quel sera l’effet sur le profit total d’une diminution de 500 de la capacité d’entreposage ?
- Commandes lp_solve et résultat lp_solve:
```
mamachine> lp_solve -S4 toto.lp
...
Actual values of the constraints:
MatPrem                      6000
MainOuvr                     4000
Stock                        1800
```
- Réponse métier
  Si on diminue le stock de 500, il passe de 2500 à 2000. La solution courante utilise seulement 1800 de stock, donc la solution reste valide.
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 ?
- Commandes lp_solve et résultat lp_solve:
```
mamachine> lp_solve -s0 -S7 toto.lp
...
Tableau at iter 2:
             -4             -5              2
  1      0.3000000     -0.1000000      0.5500000   1400.0000000
  3     -0.2000000      0.4000000     -0.2000000    400.0000000
 -6     -0.1000000     -0.3000000      0.6500000    700.0000000
        -1.0000000     -1.0000000     -0.5000000  10000.0000000
...

puis

on modifie toto.lp en changeant la première ligne en:
max: 6 x1 + 3 x2 + 4 x3;
et on lance
mamachine> lp_solve toto.lp

Value of objective function: 10538.5

Actual values of the variables:
x1                        807.692
x2                        1076.92
x3                        615.385
```
- Réponse métier:
  Le coût réduit de la variable x2 vaut 0.5. Donc il faut l'augmenter au minimum de 0.5 pour que la solution actuelle ne soit plus valide. On décide donc de l'augmenter de 1 (elle passe donc de 2 à 3), et le nouveau plan de production devient:
  - 807.69 unités du produit A
  - 1076.92 unités du produit B
  - 615.38 unités du produit C
    pour un profit de 10538.46€

Note: Il y a d'autre solutions à cette dernière question. Si on lance

mamachine> lp_solve -S4 toto.lp

on peut également lire la réponse à deux endroits:

Objective function limits:
                                 From            Till       FromValue
x1                           5.090909              16          -1e+30
x2                             -1e+30             2.5        1076.923
x3                                1.5             6.5          -1e+30

Il faut donc augmenter x2 jusqu'à au moins 2.5 pour que la solution actuelle ne soit plus valide.

ou encore

Dual values with from - till limits:
                           Dual value            From            Till
MatPrem                             1        1333.333            8000
MainOuvr                            1            3000        6333.333
Stock                               0          -1e+30           1e+30
x1                                  0          -1e+30           1e+30
x2                               -0.5           -2000        1076.923
x3                                  0          -1e+30           1e+30

Le coût réduit de x2 se retrouve dans ce tableau, il vaut 0.5, donc il faut augmenter x2 d'au moins 0.5 pour que la solution ne soit plus valide.

Il est en général suffisant d'utiliser lp_solve -S4 pour donner les réponses aux questions.

TP1

Optimisation Combinatoire - Fiche réponse - corrigé

Exercice 1: Plan de production