Programmation Linéaire

inis ou autres suivants le secteur d’activité, ce qui explique le rôle de la raffinerie dans le fonctionnement de l’économie. Ainsi suivant la transformation, on peut obtenir différents types de produits finis comme l’essence, le gasoil et le fuel, qui font l’objet du sujet que l’on va traiter. Mais comme toute entreprise, la raffinerie va chercher à optimiser son processus de raffinage pour minimiser ses coûts ou bien maximiser son profit. Pour cela la programmation linéaire joue un rôle important dans les décisions des raffineries.

Les premières formalisations de problèmes de raffinage se sont développées dans les années 50 avec le développement de l’algorithme du simplexe par Dantzig (mathématicien américain d’origine russe, fondateur du « Centre de Recherche Opérationnel », élu membre de l’Académie nationale des sciences des Etats-Unis en 1977) en 1949.

D’autres algorithmes seront développés plus tard comme l’algorithme de Katchian. Cependant on constate que l’algorithme du simplexe demeure « beaucoup plus rapide »[2] jusqu’à maintenant. (Même si il n’est pas parfait d’un point de vue mathématique puisque qu’il tourne infiniment dans certains cas) [3]

Dans le sujet que l’on va traiter, nous allons chercher à modéliser le processus de raffinage d’une raffinerie afin d’optimiser son programme de production à l’aide de l’algorithme du simplexe. Il va falloir déterminer la fonction qui utilise de façon optimale les pétroles bruts disponibles en tenant compte des contraintes posées par les différentes demandes des produits finis. Les objectifs recherchés par la raffinerie dans ce mémoire sont :

- de pouvoir évaluer et comparer rapidement l’intérêt économique des différentes possibilités du raffineur en fonction des conditions du marché et de sa propre situation.

- d’évaluer l’intérêt économique des différents résultats obtenus afin d’estimer le processus d’optimisation le plus efficace.

- et d’expliquer les décisions prises par la firme en fonction de ces variations d’environnement économique.

Ainsi dans une première partie nous nous intéresserons à l’optimisation des dépenses de la raffinerie. On étudiera les effets de variations de demande des produits finis sur les coûts supportés par l’entreprise, de même que l’effet du progrès technique et du traitement des pétroles bruts sur les dépenses. Dans une deuxième partie, on s’intéressera au problème de maximisation du profit annuel de la raffinerie. Pour cela, on étudiera comme dans la première partie l’impact d’une modification des différentes variables que nous expliciterons par la suite. Enfin, nous comparerons ces deux stratégies (minimisation des dépenses et maximisation du profit annuel).

I. Minimisation des coûts de production d’une raffinerie

1) Modélisation du problème de minimisation des coûts de production

On pose :

x1 = Quantité de brut 1

x2 = Quantité de brut 2

x3 = Quantité de brut 3

x4 = Quantité de brut 4

a) Problème d’optimisation primal

Ainsi on peut écrire le problème d’optimisation du processus de raffinage sous la forme canonique suivante :

[pic] (1)

Sous forme matricielle, on a :

[pic] [pic]

[pic]

Pour pouvoir trouver les solutions optimales de notre problème on passe le problème d’optimisation sous forme standard (problème primal) et on obtient donc :

[pic] (2)

Où a1, a2, a3 sont des variables correspondant aux produits artificiels. (On les ôtera au fur et à mesure des itérations dans le tableau simplexe, mais on les considère très grandes de façon à ce qu’elles pénalisent l’objectif)

Cependant, pour résoudre notre problème par la méthode du simplexe, nous devons passer notre problème en Max au lieu de Min[4] :[pic]

[pic] (3)

Maintenant nous pouvons construire le premier tableau simplexe de notre problème d’optimisation. Pour simplifier les calculs, nous avons multiplié la matrice A par 10 afin d’éviter d’avoir des chiffres à virgule, et nous avons aussi simplifié le vecteur colonne b en divisant par 10 000. Ainsi on obtient le tableau suivant :

|x1 |x2 |x3 |x4 |e1 |e2 |e3 |a1 |a1 |a3 |b | |a1 |3 |5/2 |4 |2 |-1 |0 |0 |1 |0 |0 |125 | |a2 |4 |5/2 |3 |2 |0 |-1 |0 |0 |1 |0 |135 | |a3 |3 |5 |3 |6 |0 |0 |-1 |0 |0 |1 |180 | |∆ |-100+M |-90+M | - 104+10M |-88+10M |-M |-M |-M |0 |0 |0 |0 | |

Nous avons initialisé le tableau simplexe et nous avons obtenu au final un tableau optimal[5], mais pour répondre aux questions du mémoire nous sommes partis du problème dual pour faire nos calculs. (Le tableau dual optimal s’obtenant plus aisément en raison de l’absence de variables pénalisées à introduire)

b) Problème d’optimisation dual

On pose :

[pic] [pic] [pic] [pic][pic]

Le problème dual s’écrit sous la forme suivante :[pic][pic]

On met le problème sous forme standard[6] et on résout le problème par la méthode du simplexe.

Le premier tableau du problème dual est alors donné par :

|v1 |v2 |v3 |ɛ1 |ɛ2 |ɛ3 |ɛ4 |b | |ɛ1 |3 |4 |3 |1 |0 |0 |0 |100 | |ɛ2 |5/2 |5/2 |5 |0 |1 |0 |0 |90 | |ɛ3 |4 |3 |3 |0 |0 |1 |0 |104 | |ɛ4 |2 |2 |6 |0 |0 |0 |1 |88 | |∆ |125 |135 |180 |0 |0 |0 |0 |-0 | |

A l’optimalité on obtient :

|v1 |v2 |v3 |ɛ1 |ɛ2 |ɛ3 |ɛ4 |b | |v2 |0 |1 |0 |5/8 |-3/20 |-3/8 |0 |10 | |v1 |1 |0 |0 |-3/8 |-3/20 |5/8 |0 |14 | |ɛ4 |0 |0 |0 |1/4 |-3/2 |1/4 |1 |4 | |v3 |0 |0 |1 |-1/8 |7/20 |-1/8 |0 |6 | |∆ |0 |0 |0 |-15 |-24 |-5 |0 |-4180 | |

Les coûts marginaux pour les différents produits sont de[7] :

- 15 euros pour l’essence

- 24 euros pour le gasoil

- 5 euros pour le fuel.

Par exemple, produire une tonne supplémentaire de fuel coûtera 5 euros a l’entreprise.

Les coefficients ∆ correspondent aux valeurs optimales du membre b dans le primal. On en dégage alors le programme de minimisation des coûts suivant :

A l’optimalité, l’entreprise traite 50 000 tonnes de Brut3, 150 000 tonnes de Brut1, et 240 000 tonnes de Brut2. Elle ne traite donc pas tous les bruts.

En se référant à la fonction objectif suivante : J(x) = 125 v1 + 135 v2 + 180 v3, on obtient alors une dépense de 41 800 000 euros.

2) Impact du progrès technique sur les dépenses de la raffinerie

L’amélioration des techniques d’exploitation va entraîner une baisse du prix de revient du pétrole brut4 venant d’Europe.

Le nouvelle objectif dans notre problème d’optimisation (1) est donné par :

[pic], où h correspond à la baisse du prix de revient du brut4.

Soit un changement d’objectif en max équivalent à :

[pic]

On a alors :

|x1 |x2 |x3 |x4 |e1 |e2 |e3 |b | |e1 |3 |5/2 |4 |2 |1 |0 |0 |125 | |e2 |4 |5/2 |3 |2 |0 |1 |0 |135 | |e3 |3 |5 |3 |6 |0 |0 |1 |180 | |∆ |-100 |-90 |-104 |-(88+h) |0 |0 |0 |0 | |

On prend le dernier tableau simplexe du problème primal, et on recalcule le Δ x4. N’étant pas en base, on ne recalcule pas les indicateurs d’optimalité x1, x2, x3.

[pic]

On a donc à l’optimalité :

|x1 |x2 |x3 |x4 |e1 |e2 |e3 |b | |x3 |0 |0 |1 |-1/4 |-5/8 |3/8 |1/8 |5 | |x1 |1 |0 |0 |-1/4 |3/8 |-5/8 |1/8 |15 | |x2 |0 |1 |0 |3/2 |3/20 |3/20 |-7/20 |24 | | ∆ |0 |0 |0 |-4-h |-14 |-10 |-6 |4180 | |

Pour rester optimal, [pic], h étant la baisse du prix de revient du brut 4. Si le coût de revient varie de 0 à 4 euros, la raffinerie ne changera pas ses dépenses, en d’autres termes cela signifie que l’amélioration des techniques d’exploitation du brut4 n’aura pas d’impact sur les coûts de production de la raffinerie. Pour un [pic], (soit une baisse du prix de revient du pétrole Brut4 supérieure à 4 euros) le tableau n’est donc plus optimal. x4 va rentrer en base et on obtiendra le nouveau programme suivant :

|x1 |x2 |x3 |x4 |e1 |e2 |e3 |b | |x3 |0 |1/6 |1 |0 |-3/5 |2/5 |1/15 |9 | |x1 |1 |1/6 |0 |0 |2/5 |-3/5 |1/15 |19 | |x4 |0 |2/3 |0 |1 |1/10 |1/10