Résolution d’un programme linéaire à

l’aide de logiciels
 Optimisation des systèmes de
Résolution d’un programme linéaire à l’aide de logiciels

1. Introduction

Il existe plusieurs logiciels sur le marché qui peuvent résoudre un PL en utilisant la méthode simplex.
On peut citer :

- MS Excel : en utilisant SOLVEUR d’Excel, on peut résoudre un PL. L’avantage est qu’il s’agit
d’un outil gratuit et disponible.
- Des langages de modélisations de programmes mathématiques : se sont des logiciels
spécifiques développés pour formuler des programmes mathématiques. Ces logiciels sont
utilisés essentiellement dans le cas de la formulation de programme de grande taille (des
centaines à des milliers de variables et de contraintes). L’utilisation de ces logiciels nécessite
l’octroi d’une licence et la connaissance de leur langage de programmation. On peut citer
MPL : www.maximal-usa.com , Lingo : www.lindo.com et cplex : www.ilog.com
Dans ce chapitre, nous allons nous limiter à l’utilisation de MS Excel et de Lingo pour résoudre des
programmes linéaires multi-dimensionnels.

2. L’utilisation du logiciel MS Excel

2.1 Programmation d’un PL avec Excel

Le logiciel d’usage courant MS Excel possède un sous-programme nommé SOLVEUR capable d’utiliser
l’algorithme du simplex. Pour en faire la démonstration, nous allons revenir à l’exemple de Glass SA.

Max Z=3 x1 + 5 x2
s.c. :
x1 4
2 x2 12
3 x1 + 2 x2  18
x1  0, x2  0

Les étapes à suivre sont comme suit :

2
 Résolution d’un programme linéaire à l’aide de logiciels

1. Rentrer les données du problème sur une feuille de calcul Excel. Il s’agit de rentrer les données
du problème de la façon la plus simple possible (cf. figure 1) :
- Introduire les cœfficients de la fonction objectif (case C8 et D8).
- Entrer les variables de décision x1 et x2. La Ligne « Solution » permettra d’enregistrer la
valeur des variables de décision. Au départ, On peut fixer les valeurs à 0.
- Ecrire l’équation des contraintes. Pour cela, nous avons introduit la colonne total afin
d’enregistrer la partie gauche des contraintes. Par exemple, dans la case E7, nous avons
introduit la troisième contrainte en fonction des cœfficients d’utilisation des ressources : E7
= C7*C9 + D7*D9
 Astuce : Ces équations impliquent la somme de produits. On peut utiliser la
fonction prédéfinie d’Excel SOMMEPROD qui permet de faire la somme des
produits de termes appartenant à des cellules différentes : E7 =
SOMMEPROD(C7:D7;C9:D9). L’avantage d’utiliser cette fonction est de
simplifier la programmation du modèle dans le cas d’une dimension plus
importante du modèle.
- Ecrire les limites des équations des contraintes (Colonne G). Par ailleurs, nous avons introduit
également la colonne F dans laquelle nous avons mentionné le sens d’inégalité des
contraintes. En effet, ce fichier peut servir pour tester la faisablité d’une solution donnée (en
introduisant des valeurs différentes dans la ligne solution, on peut tester si une solution
donnée est réalisable et vérifie donc l’ensemble des contraintes)
- Ecrire la fonction objectif. Nous avons dédié la cellule E8 pour stocker la valeur de la fonction
objectif. L’équation écrite pour la cellule E8 est =SOMMEPROD(C8:D8;C9:D9)
A ce stade, ce fichier ainsi introduit permet d’analyser différentes solutions en testant leur
faisabilité et évaluer le profit qu’elle pourrait générer. Ainsi, on peut s’amuser à changer les
paramètres du modèle sans changer la programmation du modèle lui-même (Fonction objectif et
contraintes).

Pour trouver directement la solution optimale, il faudra poursuivre les étapes suivantes.

3
 Résolution d’un programme linéaire à l’aide de logiciels

Figure 1 : Feuille de calcul Excel pour Glass SA.

2. Installer SOLVEUR
SOLVEUR n’est pas installé par défaut sous Excel. Pour installer le SOLVEUR, avec Excel 2007 :

• Cliquez sur le Bouton Microsoft Office, puis sur Options Excel.

• Cliquez sur Compléments puis, dans la zone Gérer, sélectionnez Compléments Excel.

• Cliquez sur Atteindre.

• Dans la zone Macros complémentaires disponibles, activez la case à cocher Complément

Solveur, puis cliquez sur OK. Conseil Si le Complément Solveur ne figure pas dans la zone
Macros complémentaires disponibles, cliquez sur Parcourir pour le localiser.

• Si vous recevez un message vous indiquant qu'il n'est pas installé sur votre ordinateur,
cliquez sur Oui pour l'installer.

• Une fois le complément Solveur chargé, la commande Analyse des données apparaît dans le
groupe Analyse de l'onglet Données.

4
 Résolution d’un programme linéaire à l’aide de logiciels

La figure suivante présente la boîte de dialogue PARAMETRES DU SOLVEUR, laquelle vous permet d'entrer
les valeurs de la cellule cible, des cellules variables et des contraintes qui s'appliquent à votre modèle
d'optimisation

Figure 2 : Boîte de dialogue de Solveur

3. Paramétrer SOLVEUR
Avant que SOLVEUR applique l’algorithme simplex, il a besoin d’identifier l’emplacement de chaque
composant du modèle dans la feuille de calcul Excel.

Dans la boîte de dialogue PARAMETRE DU SOLVEUR :

- Dans le champ CELLULE CIBLE, indiquer la fonction objectif

- Définir le type de la fonction objectif. Par défaut, SOLVEUR utilise une fonction de
maximisation (Max)
- Dans la champ CELLULES VARIABLES, indiquer les variables de décision
- En cliquant sur AJOUTER, introduire les contraintes, entrer les contraintes l’une après l’autre
en suivant les directives du SOLVEUR et en choisissant les symboles appropriés pour chacune
d’elles : ≤ ;  ; =
- Une fois entrées toutes les contraintes, cliquer sur OK
Une fois tous les paramètres sont introduits on obtient la fenêtre suivante.

5
 Université Virtuelle de Tunis Optimisation des systèmes de production
Résolution d’un programme linéaire à l’aide de logiciels

Figure 3 : Paramétrage du Solveur pour Glass SA.

4. Vérifier les options du SOLVEUR. En cliquant sur option, on a la possibilité de modifier la façon
dont le problème sera résolu. Le plus important dans notre cas est de spécifier qu’il s’agit d’un
modèle linéaire et de variables non-négatives pour toutes las variables. Il faudra donc cocher les
cases correspondantes (cf. Figure 4) et cliquer sur OK. C’est ainsi que Simplex sera utilisé pour
résoudre notre problème.

Figure 4 : Définition des options du Solveur

5. Le tableau de PARAMETRES DU SOLVEUR réapparaît, cliquer sur Résoudre pour obtenir la solution
optimale. Cette dernière sera affichée dans le fichier Excel (cases en gris relatives à la fonction
objectif et aux variables de décision).

6
 Résolution d’un programme linéaire à l’aide de logiciels

Figure 5 : Solution optimale pour le problème de Glass SA. obtenue avec Solveur

2.2 Analyse de sensibilité avec Excel

En général les paramètres d’un programme linéaire (aij, bi et cj) ne sont pas fixes et sont sujets à des
variations. La question qui se pose est jusqu’à quelle limite de variation de ces paramètres la solution
optimale demeure inchangée. A titre d’exemple, si en raison de changement dans le marché le profit
unitaire de produit 2 est plus bas, est ce qu’il serait toujours intéressant de produire 6 lots de ce
produit. Ce genre d’analyse est appelé analyse de sensibilité. Le but d’une telle analyse est
d’identifier les paramètres sensibles du modèle c’est-à-dire les paramètres dont leur changement
implique automatiquement un changement de la solution optimale.

Les analyses de sensibilités peuvent être effectués avec Excel. En effet, dans la fenêtre Résultat du
SOLVEUR indiquant l’obtention d’une solution optimale (cf figure 6), le logiciel donne la possibilité de
montrer trois rapport. En sélectionnant Sensibilité, on obtient une nouvelle feuille de calcul Excel
montrant le rapport de sensibilité de notre exemple (cf. figure 7)

7
 Résolution d’un programme linéaire à l’aide de logiciels

Figure 6 : Fenêtre obtenue après obtention de la solution optimale

Comment lire ce rapport ?

Le premier tableau indique les analyses de sensibilité sur les cœfficients des variables de décision
dans la fonction objectif (dans notre cas, il s’agit du profit unitaire).

Le deuxième table effectue une analyse similaire pour les cœfficients des contraintes et du second
membre.

Figure 7 : Rapport d’analyse de sensibilité de Glass SA.

Premier tableau :

8
 Résolution d’un programme linéaire à l’aide de logiciels

La première colonne indique la valeur des variables de décision obtenues à l’optimal. Les trois
dernières colonnes indiquent l’intervalle pour chaque cœfficient dans la fonction objectif pour lequel
la valeur de la solution optimale demeure inchangée. La troisième colonne indique les valeurs
actuelles pour ces coefficients. La quatrième et cinquième colonne indiquent respectivement
l’augmentation et la réduction admissible par rapport aux coefficients actuels et qui permettent de
maintenir la même solution optimale. Ainsi :

3-3 ≤ c1 ≤ 3 + 4,5 donc 0≤ c1 ≤ 7,5

Ainsi, même si le profit unitaire par rapport au produit 1 baisse, il serait toujours optimal de produire
2 lots de ce produit.

Le même raisonnement est effectué pour le produit 2, on obtient :

5-3 ≤ c2 ≤ 5 +  donc 2 ≤ c2

Ainsi, même le profit unitaire du produit 2 sera multiplié par 2, la solution optimale ne change pas
(produire 2 lots du produit 1 et 6 lots du produit 2). En effet, le modèle n’est pas sensible à
l’augmentation de ce paramètre à partir d’un profit de 2 MD/lot.

Second tableau :

Le second tableau donne les analyses de sensibilité par rapport aux paramètres des contraintes du
modèle. La première colonne indique la valeur de la partie gauche de chaque contrainte (colonne
total du fichier de calcul). La troisième colonne indique les coefficients considérés pour le second
membre. La quatrième et cinquième colonne indiquent respectivement l’augmentation et la
réduction admissible sur les valeurs actuels du second membre qui permettent de garantir que la
solution optimal obtenues avec les paramètres initiaux demeure réalisable dans cet intervalle. Ainsi,
pour notre cas, les intervalles sont :

2 ≤ b1

6 ≤ b2 ≤ 18

12 ≤ b3 ≤ 24

Par exemple, si nous choisissons b2 = 8, on obtiendra une nouvelle solution (x1 = 3,33 ; x2 = 4 ; S1 =
0,66 ; S2 = S3 = 0) mais qui est du même type que la solution optimale initiale (x1 = 2 et x2 = 6 ; S1 =

9
 Résolution d’un programme linéaire à l’aide de logiciels

2 ; S2 = S3 = 0) c’est dire à l’optimum, produire les deux types de produits en utilisant toutes les
ressources disponibles dans l’atelier 2 et 3 (S2 = S3 = 0). Par contre, si on choisit b2 = 3, à l’optimun,
c’est l’atelier 1 et 2 qui sont saturés ( la solution optimale dans ce cas est S1 = S2 = 0 ; x1 = 4 ; x2 = 1,5
, S3 = 3)

10