MODULE 3

SOLUTION POUR
K VARIABLES

Louis Houde
Département de Mathématiques et d’informatique
Université du Québec à Trois-Rivières
MODULE 3 Solution pour k vari-
ables

Le cas spécifique de 2 variables de décision a l’intérêt d’avoir une représentation graphique de

l’ensemble des solutions réalisables et de l’interaction entre la fonction objectif et cet ensemble.
La visualisation du problème permet de dégager quelques principes au niveau des solutions à
un problème général de PPL et au niveau des outils nécessaires à une résolution plus générale.
L’idée de la recherche de solutions sur un sommet du polygone des solutions réalisables est
généralisée aux problèmes à k variables et un algorithme est considéré pour effectuer le calcul
facilement par ordinateur.

Objectifs et compétences

L’objectif de cette section est de donner à l’étudiant les bases théoriques pour comprendre les
algorithmes de résolution des problèmes de programmation linéaire à plusieurs variables et
pour utiliser un logiciel pour trouver la solution optimale.

L’étudiant sera en mesure de

• Réécrire le problème de programmation linéaire dans sa forme standard

• Établir les variables d’écart et les interpréter
• Définir le nombre de solutions de base possibles
• Créer un ensemble de variables de base et hors base
• Trouver une solution de base
• Déternimer si la solution de base est réalisable
• Obtenir la solution optimale parmi toutes les solutions de base
• Comprendre le méchanisme de résolution par l’algorithme du simplexe
• Effectuer une résolution par EXCEL
• Comprendre les sorties EXCEL et les interpréter
2 MODULE 3 Solution pour k variables

3.1 Forme standard et variables d’écart

La représentation graphique a permis de déduire que si une solution existe elle est nécessaire-
ment sur un sommet de l’ensemble des solutions réalisables. Cela vient du fait que l’ensemble
solution est un polygone convexe formé de segments de droites et que la fonction objectif est
une droite qui se superpose à l’ensemble des solutions réalisables.

Le même principe s’applique à un PPL à k variables, la différence est qu’il est difficile à se
représenter et que le nombre de sommets à considérer peut devenir rapidement très grand. Voici
un polygone des solutions réalisables en 3 dimensions :

L’idée développée dans le module sur les solutions graphiques s’applique : la fonction objectif
est de la forme
z = c1 x1 + c2 x2 + c3 x3
soit une ligne dans un univers en trois dimensions. Cette droite peut se "promener" dans
l’espace ce qui détermine sa valeurs (z ) mais sa direction reste la même soit celle fixé par
les constantes ci .

Le principe reste donc le même puisque la "droite" représentant la fonction objectif va néces-
sairement quitter le polygone des solutions réalisables à un sommet : il suffit de "visiter" tous
les sommets du polygone en 3 dimensions pour obtenir toutes les possibilités et trouver le som-
met optimal. Le problème avec cette approche est qu’il est difficile de visualiser un polygone
à trois dimensions et impossible de le faire en k dimension.

Le principe de la solution d’un problème avec k variables est de modifier légèrement l’approche
pour obtenir les sommets comme étant l’intersection entre les droites et automatiser le proces-
sus pour qu’un ordinateur puisse facilement calculer chaque sommet. Cette approche "informa-
tique" ou algorithmique est basée sur le fait qu’il est facile de résoudre un système d’équations
linéaires ayant autant d’équations que de variables et que cela se fait facilement en inversant
une matrice. Cette dernière opération bien qu’étant longue et fastidieuse avec une calculatrice
et très bien maîtrisée par les logiciels de calcul.
 Forme standard et variables d’écart 3

Proposition 1.1 Soit un PPL à k variables. Si une solution existe, elle est nécessairement sur
la frontière de l’ensemble des solutions réalisables, soit à un sommet soit sur une arête de cet
ensemble.

Cette proposition signifie qu’il suffit de regarder sur les sommets de l’ensemble des solutions
réalisables pour trouver la ou les solutions optimales. Il reste cependant à définir ce qu’est cette
frontière d’un ensemble à k variables.

Variable d’écart

Pour automatiser le processus il faut transformer toutes les contraintes en égalités puisque les
outils mathématiques pour traiter des équations sont beaucoup plus faciles à manipuler que
ceux traitant des inéquations. Considérons un PPL dans lequel il y a des contraintes représen-
tées par des inégalités. Pour ne pas altérer l’ensemble des solutions, on fait appel à des variables
d’écart.

Définition 1.1 Une variable d’écart pour une contrainte linéaire est une variable non néga-
tive qui permet d’exprimer la contrainte comme une équation.

Il est toujours possible de remplacer une inéquation par une équation en ajoutant ou soustrayant
une variable d’écart positive. Deux cas se présentent selon le sens de l’inégalité ou de l’égalité
4 MODULE 3 Solution pour k variables
• Dans le cas d’une inégalité de type ≤ il faut ajouter une variable d’écart pour tenir compte
du chemin restant à parcourir. Ainsi l’inéquation
3x1 + 2x2 ≤ 4
peut s’écrire
3x1 + 2x2 + x3 = 4
où x3 ≥ 0 comme l’illustre la figure suivante :

Puisque 3x1 + 2x2 est plus petit ou égal à 4 cela veut dire que pour atteindre 4 il faut
ajouter une certaine quantité positive soit x3 . La variable x3 étant une variable qui donne
l’écart entre la valeur du membre de gauche de la contrainte et la constante 4, soit
x3 = 4 − (3x1 + 2x2 )
La valeur x3 est ce qui manque à 3x1 + 2x2 pour compléter à 4.
• Dans le cas d’une inégalité de type ≥ il faut soustraire une variable d’écart pour tenir
compte du surplus. Ainsi pour ce qui est d’une équation de la forme
3x1 + 2x2 ≥ 4
il est possible de changer l’inégalité par une égalité en soustrayant une variable positive :
3x1 + 2x2 − x3 = 4
comme l’illustre le graphique suivant :

La valeur x3 représente le surplus du membre de gauche de l’équation par rapport à 4.

Il est plus facile de se représenter cette notion avec un exemple concret. Considérons la con-
trainte qui donne le nombre maximum d’heures de travail en une semaine pour un employé en
fonction de deux tâches. La contrainte s’écrit
2x1 + 3x2 ≤ 40
C’est-à-dire que le produit x1 demande 2 heures de travail tandis que le produit x2 en demande
3. Si on fabrique 10 du premier et 5 du deuxième alors x1 = 10, x2 = 5 et
2x1 + 3x2 = 35
Il y aura 5 heures non travaillées par l’employé. C’est la variable d’écart qui permet d’écrire la
contrainte sous la forme
2x1 + 3x2 + x3 = 40
Dans cet exemple, x3 = 5, c’est le nombre d’heures non travaillées ou si on préfère la ressource
 Forme standard et variables d’écart 5

non utilisée.

Dans le cas d’un employé qui doit travailler au moins 40 heures semaine ( 2x1 + 3x2 ≥ 40)
et qu’après il doit être payé en temps et demi. S’il a travaillé 43 heures cela veut dire qu’il a
dépassé ses heures normales de 3 heures qui seront payées en temps et demi
2x1 + 3x2 − x3 = 40
c’est-à-dire qu’il a travaillé x3 = 3 heures de plus que la borne minimale et x3 représente les
heures supplémentaires.

Cette notion est importante pour l’interprétation d’une solution. Si la valeur d’une variable
d’écart est grande pour une solution optimale alors une partie importante de la ressource n’est
pas utilisée.

Exemple 1.1 ⋆Un artisant produit des colliers de perles. Il dispose de 50 perles noires, 120
perles blanches et 100 perles rouges. Il a deux modèles de collier, le premier demande 5 perles
noires, 3 perles blanches et 2 perles rouges tandis que le deuxième demande 3 perles noires
5 perles blanches et 7 perles rouges. Le premier modèle rapporte 35$ tandis que le deuxième
rapporte 45$. On cherche la production à faire pour maximiser les profits.
Variables de décision :

• x1 : nombre de colliers du premier modèle

• x2 : nombre de colliers du deuxième modèle

Fonction objectif: l’objectif est de maximiser les profits lors de la vente des colliers donc de
maximiser la fonction
z = 35x1 + 45x2
Contraintes

• Perles noires : il y a un maximun de 50 perles noires

5x1 + 3x2 ≤ 50
• Perles blanches : il y a un maximum de 120 perles blanches
3x1 + 5x2 ≤ 120
• Perles rouges : il y a un maximum de 100 perles rouges
2x1 + 7x2 ≤ 100

Les variables de décision sont toutes non négatives.

6 MODULE 3 Solution pour k variables

Le graphique de l’ensemble solution est donné par

où la ligne rouge représente la fonction objectif à son maximum.

La solution optimale est 50 , 400
29 29
, soit (1. 724 1, 13. 793). Il est évidemment impossible de
concevoir un nombre fractionnaire de colliers donc il faudra prendre 2 coliers de type 1 et 13
colliers de type 2. Avec ces valeurs la solution reste réalisable et elle est proche de l’optimal.
• Le membre de gauche de la première contraite donne 49 c’est dire qu’il reste 1 perle noire.
• Le membre de gauche de la deuxième contrainte donne 71 et ainsi il reste 49 perles blanches.
• Finalement le membre de gauche de la deuxième contrainte est de 95 donc il reste 5 perles
rouges .

Ces trois valeurs (1, 49, 5) correspondent à la ressource non utilisée c’est-à-dire aux valeurs
des variables d’écart.
Un bon conseil à l’artisant serait de modifier ses modèles de colliers pour mieux utiliser la
ressource puisqu’il reste en tout 55 perles, suffisamment pour fabriquer plusieurs colliers ou
de fabriquer d’autres éléments comme des boucles d’oreilles ou des bracelets pour écouler les
éléments restant.

Remarque 1.1 L’exemple précédant ne tient pas compte du coût des perles. Il est possible
de l’inclure dans le problème pour refléter le coût réel pour l’artisant des colliers et surtout du
coût d’un surplus de matière première.

Forme standard

Les variables d’écart ne servent pas seulement à l’interprétation des solutions mais permettent
de trouver un algorithme simple pour déterminer la solution optimale lorsque le nombre de
variables est grand. L’idée est de réécrire le PPL sous une forme impliquant uniquement des
équations et d’utiliser les outils informatiques permettant de résoudre ce type de relations de
façon automatique.
 Forme standard et variables d’écart 7

La forme du PPL qui ne contient que des égalités est appelée la forme standard du problème.

Définition 1.2 Un PPL sous forme standard est un système pour lequel toutes les contraintes
sont exprimées sous forme d’égalité et toutes les variables sont non-négatives.

La forme standard s’obtient en ajoutant autant de variables d’écart qu’il faut pour obtenir un en-
semble de contraintes sous forme d’égalités et en modifiant les variables pour s’assurer qu’elles
toutes non-négatives. Pour ce qui est de la dernière condition il suffit de remplacer une variable
négative xi par la variable x′i = −xi .1

Exemple 1.2 ⋆Le PPL ayant comme contraintes

x1 + x2 ≤ 70
150x1 + 100x2 ≤ 8000
x1 ≥ 20
x2 ≥ 10
donne, après avoir ajouté 4 variables d’écart, la forme standard suivante :
x1 + x2 + x3 = 70
150x1 + 100x2 + x4 = 8000
x1 − x5 = 20
x2 − x6 = 10
xi ≥ 0, i = 1, 2, 3, 4, 5, 6

Les variables d’écart sont notée xn+1 , xn+2 , xn+3 , · · · , où n est le nombre de variables déci-
sionnelles dans le problème initial.

Exemple 1.3 ⋆Une entreprise de montage fabrique deux types de télécommande, la régulière
rapporte des bénéfices nets de 1,50$ tandis que la "deluxe" rapporte 2$. Le temps de montage
de la télécommande "deluxe" est le double de celui de la régulière. L’entreprise a une capacité
de production équivalente à 1000 télécommandes ordinaires. L’approvisionnement est limité
puisqu’il ne peut y avoir de pièces que pour 400 "deluxes" et 700 "ordinaires".
Posons x1 le nombre de télécommandes régulières et x2 le nombre de télécommandes deluxes.
On cherche à maximiser
z = 1.5x1 + 2x2
sujet aux contraintes
x1 + 2x2 ≤ 1000
x1 ≤ 700
x2 ≤ 400
1
module 1
8 MODULE 3 Solution pour k variables

où x1 et x2 sont non négatifs.

Ce problème demande 3 variables d’écart pour se décliner sous sa forme standard puisqu’il
y a 3 contraintes en plus de la non-négativité des variables. Sous forme d’équations, les con-
traintes deviennent
x1 + 2x2 + x3 = 1000
x1 + x4 = 700
x2 + x5 = 400
avec x3 ≥ 0, x4 ≥ 0 et x5 ≥ 0.

Exemple 1.4 ⋆Considérons le PPL suivant : maximiser 7x1 + 10x2 sujet aux contraintes
4x1 − 2x2 ≤ 3
50x1 + 75x2 ≥ 500
x1 + x2 ≤ 50
avec xi ≥ 0
Le PPL sous forme standard donne les contraintes suivantes en ajoutant 3 variables d’écart :
4x1 − 2x2 + x3 = 3
50x1 + 75x2 − x4 = 500
x1 + x2 + x5 = 50
où xi ≥ 0

Exemple 1.5 ⋆Soit le PPL suivant : minimiser 8x1 + 3x2 + x4 + 4x5 sujet aux contraintes
x1 + x2 + x3 + x4 + x5 ≤ 70
4x1 − x5 ≥ 10
3x2 + 2x3 + 4x5 ≤ 100
x1 − 2x2 ≤ 0
avec xi ≥ 0
Pour obtenir la forme standard il faut utiliser 4 variables d’écart puisqu’il y a 4 contraintes
sous forme d’inéquation. On ajoute une variable d’écart pour les contraintes 1, 3 et 4 et on en
retranche une pour la contrainte 2. La forme standard est donnée par les contraintes
x1 + x2 + x3 + x 4 + x5 + x6 = 70
4x1 − x5 − x7 = 10
3x2 + 2x3 + 4x5 + x8 = 100
x1 − 2x2 + x9 = 0
où xi ≥ 0.
 Solution de base 9

Remarque 1.2 Les variables d’écart ont une signification très précise dans le problème :
c’est ce qui manque pour atteindre la borne de la ressource ou ce qu’il y a de plus que le
minimum requis. Dans un problème concret cela a une interprétation claire et très utile : y a-
t-il trop de matière première ou pas assez de ressources pour atteindre un bénifice2 acceptable
?

La forme standard permet d’obtenir toutes les solutions du PPL qui correspondent à des inter-
sections entre les contraintes. Ces solutions, pas toujours réalisables, sont appelées solutions
de base.

3.2 Solution de base

La solution optimale d’un PPL est nécessairement sur la frontière de l’ensemble des solu-
tions puisque le polygone des solutions est convexe, il suffit de trouver tous les sommets et
d’évaluer la fonction objectif pour obtenir l’optimum. La recherche des sommets est possibles
graphiquement pour deux variables de décision mais lorsque le nombre variables est grand,
c’est généralement trop complexe pour être fait à la main. L’idée des solutions de base est
d’obtenir une méthode pour trouver "automatiquement" tous les sommets même dans un con-
texte de plusieurs variables et d’implémenter cette méthode pour qu’un ordinateur puisse faire
le calcul facilement.

Solutions de base

La forme standard est équivalente à la forme initiale du point de vue des solutions mais elle est
plus facile à manipuler puisque si on est en présence d’un problème à k variables de décision a
priori et m contraintes toutes de la forme d’inégalités, on se retrouve avec k + m variables et
m équations3 . Or on sait que si une solution existe, un problème linéaire avec le même nombre
de variables que d’équations peut se résoudre si les équations ne sont pas redondantes : un des
résultats importants de la manipulation des formes linéaires est qu’il existe nécessairement une
et une seule solution à un problème à k variables et à k équations si elle ne sont pas redondantes.

Le problème de programmation linéaire sour la forme standard devient un problème de m

équations à n inconnues, où n inclus les variables de décision et les variables d’écart : m ≤ n.
Si le nombre d’équations est égal au nombre de variables et que les équations ne sont pas

2
Le bénifice étant évidemment de type "profit" pour un problème de maximisation et du type "perte" dans une
problème de minimisation.
3
Cela est vrai si toutes les contraintes a priori sont des inégalités.
10 MODULE 3 Solution pour k variables

redondantes4 alors on a nécessairement la solution au problème. On a alors autant de variables

que d’équations linéaires non redondantes. Cela voudrait dire qu’il n’y a qu’un élément dans
l’ensemble des solutions réalisables et trivialement ce serait la solution optimal.

Un cas plus intéressant se présente lorsque le nombre d’équations est plus petit que le nombre
de variables. La technique pour trouver les sommets consiste à mettre un certain nombre de
variables à 0 pour obtenir un système d’équations équilibré qui donne une solution unique puis
à déterminer la solution de ce problème spécifique. Cela donne un sommet potentiel.

Si dans un PPL il y a 4 variables de décision a priori et 3 contraintes d’inégalité, sans considérer

les contraintes de non négativité, cela veut dire qu’il y a dans la formulation standard du modèle
7 variables de décision et 3 équations. Pour résoudre ce système il faut mettre 4 variables de
décision à 0 puis solutionner le système linéaire à 3 variables et 3 équations.

Cette idée est le principe des solutions de base. On doit simplifier le problème pour résoudre
un système d’équations avec autant d’inconnues que de variables. Ce type de système lorsque
non dégénéré est très facilement résolu par des programmes informatiques.

Définition 2.1 Solution de base : soit un PPL sous forme standard comportant n variables
de décision au total, une solution de base est une solution obtenue en posant n − m variables
à 0, où m est le nombre de contraintes hormi les contraintes de non négativité.

Définition 2.2 Les variables qui sont posées a priori à 0 dans une solution de base sont dites
"variable hors base" tandis que les autres variables sont les variables "de base".

Pour mieux visualiser le concept, prenons le PPL consistant à maximiser

z = x1 + x2
sujet à la contrainte 3x1 + 2x2 ≤ 6 et à la non négativité des variables de décision.

La forme standard de ce PPL est de maximiser z sujet à la contrainte

3x1 + 2x2 + x3 = 6
Il y a trois variables et une équation ce qui veut dire que chaque solution de base est obtenu en
posant 2 variables à 0 a priori et en solutionnant pour la troisième variable. Les possibilités

4
Le terme "redondante" signifie linéairement dépendante. c’est-à-dire qu’au moins une des équations peut se
déduire des autres.
 Solution de base 11

sont les suivantes

Variables à 0 Variables à solutionner solution
x 1 , x2 x3 (0, 0, 6)
x 1 , x3 x2 (0, 3, 0)
x 2 , x3 x1 (2, 0, 0)
Une solution pour ce problème est un triplet (x1 , x2 , x3 ) et si on veut les sommets il faut
prendre les deux variables de décision, (x1 , x2 ), le but étant de trouver le ou les sommets pour
lesquels la fonction objectif est optimale. Les sommets du polygone des solutions réalisables
sont donc (0, 0), (0, 3) et (2, 0). Les variables d’écart ne sont que des "cataliseurs" permettant
de trouver les sommets automatiquement.

On doit remarquer que cette façon de procéder revient à trouver toutes les intersections entre
les droites. Dans les exemples sur les solutions graphiques on pouvait remarquer que certaines
intersections n’étaient pas utiles puisque hors du polygone des solutions réalisables. Dans le
contexte d’une application d’un algorithme automatique pour trouver la solution optimale il
est préférable de calculer ces sommets potentiels puis de vérifier s’ils sont dans l’ensemble des
solutions réalisables.

Le principe des solutions de base peut conduire à des équations incompatibles : ces sommets
sont alors écartés de la liste des solutions potentielles. Cela veut dire que toutes les solutions
de base pour lesquels il y a une valeur négative pour une des variables de base doivent être
rejetées ainsi que les systèmes menant à des incompatibilités pour les équations.

Pour facilité la lecture des solutions de base, les résultats sont présentés dans un tableau ayant
la forme suivante

hors base base Solution Réalisable Objectif

x 1 , x2 x3 (0, 0, 6) oui 0
x 1 , x3 x2 (0, 3, 0) oui 3
x 2 , x3 x1 (2, 0, 0) oui 2

où "hors base" est la colonne qui donne les variables qui sont a priori égale à 0, "base" donne les
autres variables du système, "solution" donne la solution complète pour chaque combinaison et
pour toutes les variables (décision et écart), "réalisable" indique si les valeurs sont dans l’espace
des solutions réalisables et finalement "objectif" donne la valeur de la fonction objectif pour la
solution trouvée. Il est à noter que le qualificatif "incompatible" dans la colonne "Réalisable"
signifie que les équations sont incompatibles c’est-à-dire que le système n’a pas de solution
comme dans le cas suivant : x1 = 0, x2 = 0, x3 ≥ 0 et l’équation
2x1 + 4x2 − x3 = 4.
12 MODULE 3 Solution pour k variables

On obtient le système −x3 = 4 avec x3 comme variable non négative. Cela est impossible
donc c’est incompatible avec la définition de la variable hors base.

Il est possible de quantifier le nombre de solutions de base qui doivent être examinées pour un
problème donné :

Proposition 2.1 Dans un problème de programmation linéaire à m contraintes et à n vari-

ables (variables de décision + variables
 d’écart), il y a au plus
n n!
=
m m! (n − m)!
solutions de base5 . De plus, la valeur optimale se trouve nécessairement à une des solutions
de base.

Ce nombre augmente très rapidement avec le nombre de contraintes et le nombre de variables

de décision. Ainsi pour un PPL avec 2 variables de décision et 4 contraintes, n = 6 et m = 4
il faut regarder
 
6 6! 6∗5∗4∗3∗2∗1
= =
4 2!4! 2∗1∗4∗3∗2∗1
6 ∗ 5 ∗ 4/ ∗ 3/ ∗ 2/ 6∗5
= = = 15
2 ∗ 4/ ∗ 3/ ∗ 2/ 2
possibilités tandis que pour un PPL avec 3 variables de décision et 5 contraintes, n = 8 et
m = 5 il faut regarder  
8 8! 8∗7∗6∗5∗4∗3∗2∗1
= =
5 5!3! 5∗4∗3∗2∗1∗3∗2∗1
8 ∗ 7 ∗ 6 ∗ 5/ ∗ 4/ ∗ 3/ ∗ 2/ 8∗7∗6
= =
5/ ∗ 4/ ∗ 3/ ∗ 2/ ∗ 3 ∗ 2 3∗2
8 ∗ 7 ∗ 6/
= = 8 ∗ 7 = 56
3/ ∗ 2/
possibilités.

Remarque 2.1 Certains PPL peuvent contenir des containtes sous forme d’égalité, posons
l le nombre de ces contraintes parmi les m contraintes. Dans un tel cas il y a k variables
initiales et m − l variables d’écart. On se retrouve avec n = k + m − l variables au total et
m contraintes. Le nombre de solutions de base potentielles
 est
k+m−l
m

5
n! = n ∗ (n − 1) ∗ (n − 2) ∗ · · · ∗ 2 ∗ 1. La valeur de 5! est donc 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120
 Solution de base 13

Exemple 2.1 Soit le PPL suivant : maximiser z = 3x1 + 4x2 + 25x3 sujet aux contraintes
2x1 − 4x2 ≤ 7
x1 + x2 + x3 = 10
x2 − x3 ≥ 0
xi ≥ 0
La forme standard est donnée par : maximiser z = 3x1 + 4x2 + 25x3 sujet aux contraintes
2x1 − 4x2 + x4 = 7
x1 + x2 + x3 = 10
x2 − x3 − x5 = 0
xi ≥ 0
Il y a donc 5 variables au total et 3 équations.
  Cela veut dire qu’il y a
5
= 10
3
solutions potentielles. Dans cet exemple on a k = 3, m = 3 et l = 1 puisqu’une des con-
traintes est déjà sous forme d’équation.

Méthode pour trouver les solutions de base

1. Écrire le PPL sous sa forme standard
2. Établir le nombre de variables de décision a priori k , le nombre de contraintes

m,
le
n
nombre total de variables n et le nombre de solutions de base possibles ( m ou k+m−l
m
)

3. Écrire, pour chaque solution de base possible, les variables de base et les variables hors
base.
4. Pour chaque solution de base possible
a. Trouver une solution à la forme standard si possible
b. Vérifier si cette solution est réalisable
c. Si la solution est réalisable calculer la valeur de la fonction objectif

5. Créer un tableau des solutions de base.

Remarque 2.2 LES VARIABLES D’ÉCART SONT TOUJOURS NON NÉGATIVES DONC
DÈS QU’IL Y A UNE DE CES VARIABLES NÉGATIVE DANS LA SOLUTION C’EST QU’ELLE
N’EST PAS RÉALISABLE.

Remarque 2.3 La liste des variables de base et hors base peut être très délicate à formuler
et une attention particulière doit être prise pour faire cette énumération. Il est préférable
14 MODULE 3 Solution pour k variables

de choisir l’ensemble contenant le moins de variables (de base ou hors base) pour faire
l’énumération puisque de toutes façons ces deux ensembles sont complémentaires.

Pour trouver une solution de base il faut réécrire le système sous sa forme standard et éliminer
toutes entrées dont les coefficients sont hors base. Par la suite il reste m équations linéaires
avec m variables dont certaines sont plus difficiles que d’autres à résoudre. Prendre le temps
de solutionner les plus simples en premier puisque chaque équation résolue simplifie celles qui
restent.
Lorsque le problème consiste à trouver seulement une seule solution de base, il existe souvent
au moins une combinaison de variables hors base qui rend les calculs très simples. Il faut
prendre le temps de chercher la combinaison qui élimine le plus d’entrées dans le système.
Dans certains cas le choix des variables de base ou hors base mène à une incompatibilité c’est-
à-dire qu’il ne peut y avoir de solution. Si une contrainte du système s’écrit
x1 − x5 = 20
et que les deux variables, x1 , x5 sont des variables hors bases alors il y a incompatibilité : cette
équation devient impossible. Dans la colonne des solutions il suffit de marquer "incompatibil-
ité".

Exemple 2.2 ⋆Considéront le PPL ayant les équations suivantes dans la forme standard
x1 + x2 + x3 = 70
150x1 + 100x2 + x4 = 8000
x1 − x5 = 20
x2 − x6 = 10
xi ≥ 0, i = 1, 2, 3, 4, 5, 6
Il y a une 6 variables et 4 contraintes donc 15 solutions de base potentielles.
Le choix des variables hors bases donne comme possibilités : (x1 , x2 ), (x1 , x3 ), (x1 , x4 ),
(x1 , x5 ), (x1 , x6 ) (x2 , x3 ), (x2 , x4 ), (x2 , x5 ), (x2 , x6 ), (x3 , x4 ), (x3 , x5 ), (x3 , x6 ), (x4 , x5 ),
(x4 , x6 ), (x5 , x6 )
• Si on considère les variables hors bases x1 et x2 alors elles sont égales à 0 et le système
d’équations devient
0 + 0 + x3 = 70
0 + 0 + x4 = 8000
0 − x5 = 20
0 − x6 = 10
xi ≥ 0, i = 1, 2, 3, 4, 5, 6
On déduit directement que x5 = −20 , x6 = −10, x4 = 8000 et que x3 = 70. On a
donc la solution de base suivante : (0, 0, 70, 8000, −20, −10). Les variables x1 et x2 sont
 Solution de base 15

des variables hors base pour cette solution tandis que les variables x3 , x4 , x5 et x6 sont des
variables de base pour cette solution. La solution n’est pas réalisable puisque x5 et x6 sont
négatifs dans cette solutions et que ce sont des variables d’écart.
• Si les variables x1 et x3 sont égales à 0 alors on obtient directement x5 = −20 et x2 = 70.
On se retrouve avec les équations
100 × 70 + x4 = 8000
70 − x6 = 10
d’où x6 = 60 et x4 = 1000. La solution de base est (0, 70, 0, 1000, −20, 60). La solution
n’est pas réalisable pour raison d’incompatibilité avec les contraintes de non négativité des
variables d’écart.
• Si les variables x1 et x4 sont égales à 0 alors on obtient directement que x2 = 80 et
x5 = −20. On peut ainsi déduire que x3 = −10 et que x6 = 70. La solution de base est
(0, 80, −10, 0, −20, 70). La solution n’est pas acceptable pour raison d’incompatibilité
avec les contraintes de non négativité des variables d’écart.
• Si les variables x1 et x5 sont égales à 0 alors on obtient une imcompatibilité puisque la
troisième contrainte ne peut être respectée.
• Si les variables x1 et x6 sont égales à 0 alors on obtient directement x2 = 10 et x5 = −20.
On déduit que x3 = 60 et que x4 = 7000. La solution de base est (0, 10, 60, 7000, −20, 0).
La solution n’est pas acceptable pour raison d’incompatibilité avec les contraintes de non
négativité des variables d’écart.
• Si les variables x2 et x3 sont égales à 0 alors on obtient directement que x1 = 70 et
x6 = −10. On peut alors déduire que x4 = 0 et que x5 = −20. La solution de base
est (70, 2, 2, 2, −20, −10). La solution n’est pas acceptable pour raison d’incompatibilité
avec les contraintes de non négativité des variables d’écart.
• Si les variables x2 et x4 sont égales à 0 alors on obtient la même solution qu’en 5. Si les
variables x1 et x4 sont égales à 0 alors on obtient directement que x2 = 80 et x5 = −20.
La solution n’est pas acceptable pour raison d’incompatibilité avec les contraintes de non
négativité des variables d’écart.
• Si les variables x2 et x5 sont égales à 0 alors on a une incompatibilité.
• Si les variables x2 et x6 sont égales à 0 alors on a une incompatibilité.
• Si les variables x3 et x4 sont égales à 0 alors on a le système d’équations suivant :
x1 + x2 = 70
150x1 + 100x2 = 8000
x1 − x5 = 20
x2 − x6 = 10
et on obtient des deux premières équations x1 = 20, x2 = 50 et finalement x5 = 0, x6 =
40. La solution est alors (20, 50, 0, 0, 0, 40).
• Si les variables x3 et x5 sont égales à 0 alors on obtient x1 = 20 et on peut déduire que
x2 = 50, x4 = 2700 et x6 = 30. La solution est alors (20, 50, 0, 2700, 0, 30).
• Si les variables x3 et x6 sont égales à 0 alors on obtient x2 = 10 et on déduit que x1 = 60,
x4 = −500 et x5 = 30. La solution de base est (60, 10, 0, −500, 30, 0). La solution n’est
16 MODULE 3 Solution pour k variables

pas acceptable pour raison d’incompatibilité avec les contraintes de non négativité.
• Si les variables x4 et x5 sont égales à 0 alors on obtient directement que x1 = 20, x2 = 50
et x3 = 0.
• Si les variables x4 et x6 sont égales à 0 alors on obtient x2 = 10 et on
peut déduire
x1 = 140/3, x3 = 40 3
, x5 = 803 . La solution de base est 140
3
, 10, 40
3
, 0, 80
3
,0
• Si les variables x5 et x6 sont égales à 0 alors on obtient x1 = 20, x2 = 10 et on déduit que
x3 = 40 et x4 = 4000. La solution est (20, 10, 40, 4000, 0, 0).

Dans l’exemple précédant il y a une possibilité de 15 solutions de base et, parmi ces solutions,
il y en a qui sont incompatibles avec les contraintes primaires, d’autres qui sont incompatibles
avec les contraintes de non-négativités des variables d’écarts et seulement 3 des solutions sont
des solutions qui respectent toutes les contraintes. Cela veut dire que ce PPL a un polygone
des solutions réalisables déterminé par 3 sommets (un triangle).

Remarque 2.4 Il est à noter que si on regarde la solution graphique pour les variables orig-
inales, (x1 , x2 ) il y a trois valeurs différentes pour les solutions réalisables soient (20, 10),
(140/3, 10) et (20, 50). Cela correspond exactement aux solutions retenues pour ce même
problème en utilisant la méthode de résolution graphique.

Définition 2.3 Une solution de base est dite dgnre si au moins une des variables de base est
égale à 0.

On remarquera que la solution (20, 50, 0, 0, 0, 40) de l’exemple précédant est dégénérée puisque
en plus des deux variables hors base, il y a une autre variable qui est égale à 0.

Exemple 2.3 ⋆Une compagnie fabrique deux types d’acier : Acier trempé (T) et l’acier
détrempé (D). Le profit sur une tonne d’acier est de 6k$ pour l’acier T et 4k$ pour l’acier
D. Il faut respectivement 2 et 3 tonnes de matières premières pour les aciers T et D tandis que
le temps de production est respectivement de 6 et 4 unités. La compagnie dispose de 120 tonnes
de matières premières et de 100 unités de temps. Maximiser les profits par méthode graphique
et déterminer les solutions de base pour ce problème
Solution : Posons x1 : le nombre de tonnes d’acier trempé et x2 : le nombre de tonnes d’acier
détrempé. Le PPL correspondant est de maximiser
z = 6x1 + 4x2
sujet aux contraintes
2x1 + 3x2 ≤ 120
6x1 + 4x2 ≤ 100
 Solution de base 17

et aux contraintes de non négativité x1 ≥ 0 et x2 ≥ 0. Le polygone des solutions réalisables

est donné par la figure suivante :

Les trois sommets du polygone sont (0,0), (0,25) et (100/6,0) et les valeurs de la fonction
objectif sont respectivement 0, 100 et 100. Cela veut dire qu’il y a une infinité de solutions
optimales. <
La forme standard pour ce problème donne les équations suivantes :
2x1 + 3x2 + x3 = 120
6x1 + 4x2 +
x4 = 100
donc le tableau des solutions de base aura 42 = 6 entrées :
Base Hors base Solution réalisable z
(x1 , x2 ) (x3 , x4 ) (−18, 52, 0, 0) non
(x1 , x3 ) (x2 , x4 ) (100/6, 0, 260/3, 0) oui 100
(x2 , x3 ) (x1 , x4 ) (0, 25, 45, 0) oui 100
(x1 , x4 ) (x2 , x3 ) (60, 0, 0, −260) non
(x2 , x4 ) (x1 , x3 ) (0, 40, 0, −60) non
(x3 , x4 ) (x1 , x2 ) (0, 0, 120, 100) oui 0

Remarque 2.5 Dans l’exemple précédant la solution graphique est la méthode des solutions
de base donne le même résultat. On regarde les mêmes sommets du polygone des solutions
réalisables (100/6,0), (0,25) et (0,0) mais pour y arriver la méthode des solutions de base
demande d’évaluer 6 intersections. C’est plus de travail mais c’est aussi un travail qui peut
facilement être automatisé.

Exemple 2.4 ⋆Une entreprise de montage fabrique deux types de télécommande, la régulière
donne des bénéfices nets de 1,50$ tandis que la deluxe donne 2$. Le temps de montage de la
télécommande de luxe est le double du temps de la régulière et l’entreprise a une capacité
de production équivalente à 1000 télécommandes ordinaires. L’approvisionnement est limité
puisqu’il ne peut y avoir de pièces que pour 400 deluxes et 700 ordinaires. Donner les solu-
tions de base pour ce problème, le nombre de sommet du polygone des solutions réalisables et
la solution optimale.
18 MODULE 3 Solution pour k variables

Solution : Soit x1 : le nombre de télécommandes ordinaires et x2 : le nombre de télécomman-

des deluxe. Le PPL est de maximiser
z = 1.5x1 + 2x2
sujet aux contraintes
x1 + 2x2 ≤ 1000
x1 ≤ 700
x2 ≤ 400
avec x1 ≥ 0 et x2 ≥ 0. Le polygone des solutions réalisables est donné par

Le polygone des solutions réalisables a 5 sommets : (0,0), (0,400), (200,400), (700,0) et

(700,150). Les valeurs respectives de la fonction objectif sont 0, 800, 1100, 1150 et 1350.
Si on regarde la méthode des solutions de base on a les contraintes de la forme standard :
x1 + 2x2 + x3 = 1000
x1 + x4 = 700

x2 + x5 = 400
Il y a une possibilité de 53 = 10 solutions, ce qui donne le tableau suivant :
Base Hors base Solution réalisable z
(x1 , x2 , x3 ) (x4 , x5 ) (700, 400, −500, 0, 0) non
(x1 , x2 , x4 ) (x3 , x5 ) (200, 400, 0, 500, 0) oui 1100
(x1 , x2 , x5 ) (x3 , x4 ) (700, 150, 0, 0, 250) oui 1350
(x1 , x3 , x4 ) (x2 , x5 ) incompatible
(x1 , x3 , x5 ) (x2 , x4 ) (700, 0, 300, 0, 400) oui 1050
(x1 , x4 , x5 ) (x2 , x3 ) (1000, 0, 0, −300, 400) non
(x2 , x3 , x4 ) (x1 , x5 ) (0, 400, 200, 700, 0) oui 800
(x2 , x3 , x5 ) (x1 , x4 ) incompatible
(x2 , x4 , x5 ) (x1 , x3 ) (0, 500, 0, 700, −100) non
(x3 , x4 , x5 ) (x1 , x2 ) (0, 0, 1000, 700, 400) oui 0
La solution optimale est (700,150,0,0,250) c’est-à-dire x1 = 700 et x2 = 150.
La solution est effectivement la même que celle trouvée par la méthode graphique. On re-
 Solution de base 19

marque qu’il y a exactement 5 solutions réalisables et elles correspondent aux sommets du

polygone trouvé par la méthode graphique. On constate donc que les deux méthodes font la
même chose mais celle des solutions de base est exploitable pour plus de deux variables de
décision.

Exemple 2.5 ⋆Un contracteur doit faire exécuter 5000 heures de travaux de menuiserie par
trois sous-traitants dont les taux horaires sont respectivement de 25$, 30$ et 32$. Pour des
raisons de subvention à l’entreprise locale, il ne faut pas qu’un des sous-traitants puisse faire
plus de 2 fois le nombre d’heures d’un autre. Le contracteur veut évidemment minimiser ses
coûts.

Solution : Soit xi : le nombre d’heures données au sous-traitant i pour i = 1, 2, 3. La fonction

objectif à minimiser est
25x1 + 30x2 + 32x3
et les contraintes sont
x1 + x2 + x3 ≥ 5000
x1 − 2x2 ≤ 0
x1 − 2x3 ≤ 0
x2 − 2x1 ≤ 0
x2 − 2x3 ≤ 0
x3 − 2x1 ≤ 0
x3 − 2x2 ≤ 0
avec non négativité pour les variables de dé[Link] Standard :
x1 + x2 + x3 − x4 = 5000
x1 − 2x2 + x5 = 0
x1 − 2x3 + x6 = 0
x2 − 2x1 + x7 = 0
x2 − 2x3 + x8 = 0
x3 − 2x1 + x9 = 0
x3 − 2x2 + x10 = 0
avec xi ≥ 0. On observe le nombre
de variables n = 10 et le nombre d’équations m = 7.
Cela donne une possibilité de 7 = 120 solutions avec 3 variables hors base et 7 variables
10

de base.

Si on veut un exemple de solution de base il suffit de choisir trois variables puis de les posées
20 MODULE 3 Solution pour k variables

à 0. En posant les trois premières variables hors base on obtient les équations :
0 + 0 + 0 − x4 = 5000
0 − 2 ∗ 0 + x5 = 0
0 − 2 ∗ 0 + x6 = 0
0 − 2 ∗ 0 + x7 = 0
0 − 2 ∗ 0 + x8 = 0
0 − 2 ∗ 0 + x9 = 0
0 − 2 ∗ 0 + x10 = 0
La solution de base est
(0, 0, 0, −5000, 0, 0, 0, 0, 0, 0)
On a pour cette solution 6 variables dégénérées.

3.3 Algorithme du simplexe

La solution graphique est très efficace pour solutionner les problèmes ayant deux variables
de décision mais elle reste inutilisable avec des problèmes plus complexes. Pour trouver des
solutions à ces problèmes il faut avoir recours à la méthode des solutions de base et hors base.
Cette dernière n’est praticable à la main que si le nombre de variables et de contraintes sont
relativement petits.

La méthode des solutions de base est particulièrement bien adaptée à un calcul automatique
par l’ordinateur. Si certains problèmes peuvent être résolus à la main comme l’exemple des
téléviseurs et des machines à laver, d’autres demandent nécessairement l’utilisation d’un or-
dinateur. Prenons l’exemple d’un problème pour lequel il y a 5 variables et 5 contraintes au
départ. Il y aura 5 variables d’écart donc un total de 10 variables et 5 équations pour la forme
standard. Cela donne  
10 10!
= = 252
5 5!5!
solutions de base possibles à explorer. Un ordinateur peut facilement et rapidement faire ce
calcul.

Dans la majorité des cas "réels" la méthode des solutions de base bien que théoriquement pos-
sible n’est pas applicable même à l’aide d’un ordinateur. Prenons le cas réaliste pour l’industrie
d’un problème qui comporte 50 variables et 25 contraintes au départ, le nombre de solutions
de base à explorer sera de
 
75 75!
= = 5. 258 9 × 1019
50 50!25!
C’est-à-dire
52589000000000000000
 Algorithme du simplexe 21

calcul à faire. Ce nombre est tellement grand que même un superordinateur ne peut pas faire le
calcul de toutes les solutions de base possibles pour trouver celle qui optimise l’objectif : pour
s’en convaincre considérons un ordinateur qui peut trouver une solution de base en 0.001sec,
ce qui est relativement rapide du fait qu’il doit faire une inversion et une multiplication de
matrices, temps de calcul sera alors de
= 52589000000000000 sec
= 876480000000000 min
= 14608000000000 heures
= 1666400000 années
soit 1,6664 milliard d’années ou presque l’âge de la terre. Un super ordinateur travaillant 1M
de fois plus rapidement mettra tout de même 16 66 années pour résoudre le problème...

Ce petit exemple montre très bien qu’il est nécessaire de raffiner la méthode des solutions de
base pour diminuer le nombre de solutions à regarder et obtenir une solution optimale dans un
temps raisonnable.

Une étude attentive du processus conduisant à la solution optimale dans deux dimensions per-
met de noter deux propriétés fondamentales dans la recherche des solutions
• Si deux sommets adjacents ont deux valeurs différentes pour la fonction objectif alors il
faut déplacer la droite représentant la fonction objectif dans le sens requis pour rejoindre le
sommet donnant une valeur plus près de l’optimal. Le sens du déplacement restera toujours
le même comme l’illustre le graphique suivant :

• Le déplacement dans cette direction se fera jusqu’à ce que la fonction objectif ne touche
plus que la frontière de l’ensemble solution.

L’algorithme du simplexe utilise ces deux propriétés pour réduire le nombre de solutions de
base à explorer. Le principe est de déplacer une solution potentiellement optimale d’un sommet
à un autre tant que la fonction objectif est meilleure. On remarque aussi qu’il est inutile de
repasser sur un sommet pour lequel la fonction objectif a déjà été évaluée puisque l’algorithme
22 MODULE 3 Solution pour k variables

reprendra à un point déjà exploré.

Dans le cas de deux variables de décision l’algorithme du simplexe est assez facile à visualiser
mais pour plusieurs dimensions il faut définir la notion de sommets adjacents. Pour deux
dimensions il est assez facile de déterminer les deux sommets qui sont adjacents à un autre
sommet. Il suffit de suivre les deux lignes partant de ce sommet. Dans le graphique suivant

les sommets B et F sont adjacents à A.

Dans un univers à k dimensions une définition précise s’impose. Dans le graphique suivant en
3 dimensions

les sommets B, F et C sont adjacents à G. Pour se "promener" sur le polygone à partir d’un
sommet il suffit d’interchanger une variable hors base et une variable de base.

Définition 3.1 Considérons une solution de base obtenue en prenant m variables de base
et n − m variables hors base. Un sommet adjacent à cette solution de base est obtenu en
permutant une variable de base avec une variable hors base. Il y a m (n − m) sommets
adjacents à un sommet.

Considérons une solution de base déterminée en posant x1 x2 et x3 comme variables de base et

 Algorithme du simplexe 23

x4 comme variable hors base. Il y a 3 sommets adjacents qui sont déterminés par les solutions
de base obtenues en posant comme variables de base, x1 , x2 puis x4 ou x1 , x4 et x3 et finale-
ment x3 , x2 et x4 . Le tableau suivant illustre le passage du sommet ayant x4 comme variable
hors base à ses trois sommets adjacents.
Sommet Sommets adjacents
(x1 , x2 , x3 = 0, x4 )
(x1 , x2 , x3 , x4 = 0) =⇒ (x1 , x2 = 0, x3 , x4 )
(x1 = 0, x2 , x3 , x4 )

1 Algorithme du Simplexe
1. Prendre une solution de base quelconque et évaluer la fonction objectif. La valeur ainsi
déterminée est la "solution optimale potentielle".
2. Trouver chacun des sommets adjacents et calculer la solution et la fonction objectif pour
chacun.
3. Prendre la solution pour laquelle valeur de la fonction objectif qui est la plus grande pour
une maximisation ou la plus petite pour une minimisation.
• Si la valeur est meilleure que la solution optimale potentielle, cette nouvelle valeur
devient la "solution optimale potentielle". Reprendre l’étape 2.
• Si la valeurs est égale ou moins bonne que la solution optimale potentielle alors l’optimal
est la "solution optimale potentielle" et l’algorithme se termine.

Exemple 3.1 ⋆⋆Considérons l’exemple des télécommandes à fabriquer. Le PPL est de

maximiser
z = 1.5x1 + 2x2
sujet aux contraintes
x1 + 2x2 ≤ 1000
x1 ≤ 700
x2 ≤ 400
où x1 et x2 sont non négatifs.
Sous forme d’équations standards, les contraintes deviennent
x1 + 2x2 + x3 = 1000
x1 + x4 = 700
x2 + x5 = 400

Étape 1 Le principe de l’algorithme du simplexe est de prendre une solution de base quel-
conque en posant deux variables à 0 pour avoir le même nombre d’équations que de variables
24 MODULE 3 Solution pour k variables

"libres". Posons x3 = 0 et x5 = 0. Le système d’équations devient

x1 + 2x2 + 0 = 1000
x1 + x4 = 700
x2 + 0 = 400
On trouve x2 = 400, x1 = 200 et x4 = 500.
La solution (200, 400, 0, 500, 0) est la "solution optimale potentielle" et la valeur de la fonc-
tion objectif pour cette solution est de 1100, soit
z = 1.5 (200) + 2 (400)

Étape 2 Il y a 6 sommets adjacents à la "solution optimale potentielle", soit le nombre de

façons d’échanger une variable de base et une variable hors base. Le tableau suivant donne
les 6 possibilités de permutation d’une variable hors base et d’une variable de base pour ce
problème
Variables de base Variable hors base
(x2 , x3 , x4 ) (x1 , x5 )
(x1 , x3 , x4 ) (x2 , x5 )
(x2 , x2 , x3 ) (x4 , x5 )
(x2 , x4 , x5 ) (x3 , x1 )
(x1 , x4 , x5 ) (x3 , x2 )
(x1 , x2 , x5 ) (x3 , x4 )
Pour chacune de ces permutations il faut trouver la solution correspondante puis la valeur de
la fonction objectif :
de base hors base Solution de base z
(x2 , x3 , x4 ) (x1 , x5 ) (0, 400, 200, 700, 0) 800
(x1 , x3 , x4 ) (x2 , x5 ) impossible
(x1 , x2 , x3 ) (x4 , x5 ) (700, 400, −500, 0, 0) non réalisable
(x2 , x4 , x5 ) (x3 , x1 ) (0, 500, 0, 700, −100) non réalisable
(x1 , x4 , x5 ) (x2 , x3 ) (1000, 0, 0, −300, 400) non réalisable
(x1 , x2 , x5 ) (x3 , x4 ) (700, 150, 0, 0, 250) 1350

Étape 3. L’objectif est la maximisation de z et ainsi la solution qui est la meilleure est (700, 150, 0, 0, 250).
Étape 4. La valeur obtenu pour l’objectif est plus grande que la valeur précédante donc la
solution (700, 150, 0, 0, 250) devient la "solution optimale potentielle". Il faut retourner à
l’étape 2.
Étape 2 Il y a deux permutations de variables hors base et de base qui n’ont pas été "visitées",
soient
Variables de base Variable hors base
(x2 , x3 , x5 ) (x1 , x4 )
(x1 , x3 , x5 ) (x2 , x4 )
 Algorithme du simplexe 25

Les évaluations des solutions de base et de la fonction objectif pour ces deux sommets donnent
de base hors base Solution de base z
(x2 , x3 , x5 ) (x1 , x4 ) Impossible
(x1 , x3 , x5 ) (x2 , x4 ) (700, 0, 300, 0, 400) 1050
Étape 3 L’objectif est la maximisation de z et ainsi la solution qui est la meilleure est (700, 0, 300, 0, 400).
Étape 4 L’objectif est moins bon que pour la solution précédante donc l’algorithme se termine
et la solution optimale est (700, 150, 0, 0, 250) pour un profit de 1350$.

On obtient un profit maximum à x1 = 700 et x2 = 150. De plus, ce profit maximal est de

1350$.

Cette méthode est trop "lourde" pour être effectuée à la main mais elle est parfaitement adaptée
au calcul par ordinateur.

L’algorithme permet de trouver les valeurs optimales pour les variables de décision et pour
les variables d’écart. Le gestionnaire est intéressé principalement par la solution optimale en
fonction des variables de décision mais il est important de tenir compte des variables d’écarts
dans l’interprétation. La variable d’écart pour une contrainte de type ≤ représente l’écart entre
le membre de gauche et la borne. Si la borne est une quantité de ressources disponibles alors
la valeur de la variable d’écart à l’optimum est la quantité non utilisée de la ressource.

Exemple 3.2 Dans l’exemple de la fabrication des télécommandes, exemple ci-haut, le mod-
èle sous sa forme standard comporte 2 variables de décision et trois variables d’écart. La
solution optimale pour les variables d’écart est
x3 = 0, x4 = 0, x5 = 250
Cela veut dire que pour la première contrainte le membre de gauche est égal à la borne. Cette
contrainte donnée par
x1 + 2x2 ≤ 1000
représente la capacité de production de l’usine. Si on considère la variable d’écart, la con-
trainte est
x1 + 2x2 + x3 = 1000
soit la valeur atteinte par la solution optimale plus un "écart" non négatif représentant le
surplus de production encore accessible. Puisque la solution optimale donne x3 = 0 cela veut
dire que toute la capacité de production est utilisée.
La deuxième contrainte donnée par x1 ≤ 700, soit en terme de variable d’écart x4 = 0
donne le nombre maximum de télécommandes de type "ordinaire" qui peuvent être fabriquées.
Puisque la solution optimale donne x4 = 0, cela veut dire qu’il faut fabriquer toutes les
télécommandes "ordinaires" possibles.
Finalement la troisième contrainte donnée par x2 ≤ 400, soit la contrainte x2 + x5 = 400
donne le nombre maximum de télécommandes "deluxe" qui peuvent être fabriquées. La so-
lution optimale donne x5 = 250 cela veut dire qu’il faut fabriquer moins de cette sorte de
26 MODULE 3 Solution pour k variables

télécommande que ce qui est possible, 250 de moins que les 400 potentielles.
Une interprétation de ce résultat est qu’il serait possiblement plus rentable de tenir plus de
pièces pour la fabrication des télécommandes "ordinaires" et d’augmenter le temps disponible.

L’algorithme du simplexe a été créé pour que l’ordinateur puisse résoudre un problème de
programmation linéaire dans un temps raisonnable. Plusieurs logiciels utilisent cet algorithme
ou une variante pour résoudre les problèmes de PPL.

3.4 Solveur de EXCEL

La puissance des ordinateurs aidant, la méthode du simplexe est disponible dans plusieurs logi-
ciels "grand public" dont EXCEL. L’outil EXCEL pour solutionner un PPL est le "solveur"6 .
Lorsqu’il est chargé il devient disponible directement par l’onglet "Données". Cet outil per-
met de déterminer la solution du PPL par la méthode du simplexe et il donne une analyse des
résultats pour interprétation.

Définition des éléments du PPL

Pour effectuer l’algorithme du simplexe il faut fournir les informations relatives au PPL dans
un format qui permet aux macros du solveur d’effectuer les calculs. L’utilisation de l’outil se
fait en deux étapes :
• Définition des éléments du PPL dans la feuille EXCEL
• Exécution des macros du solveur pour faire les calculs.

Comme information minimale, il faut fournir les variables de décision, la fonction objectif et
la partie gauche des contraintes.

6
Cet outil d’analyse n’est pas présent par défaut, il faut le charger pour pouvoir l’utiliser. Pour ce faire il
faut aller dans le menu "outil", "macros complémentaires" et sélectionner "solveur". Il est possible que EXCEL
demande le CD Microsoft original pour effectuer l’installation. La dernière version d’EXCEL a une méthode un
peu différente de "charger" les macros complémentaires. Il faut alors demander l’aide de EXCEL et chercher sous
"macro complémentaire" pour trouver la procédure.
 Solveur de EXCEL 27

1. Variables de décision : il faut attribuer une cellule vide par variable de décision. Les
macros du solveur utilise ces cellules pour effectuer les calculs.
2. Fonction objectif : une cellule sera dédiée à la fonction objectif. Cette dernière doit être
une formule EXCEL valide7 qui utilise les cellules dédiées aux variables de décision pour
évaluer la fonction objectif.
3. Contraintes : une cellule par contrainte. Elle doit contenir une formule EXCEL valide
calculant la valeur du membre de gauche de la contrainte en utilisant des références aux
cellules dédiées aux variables de décision.

Préparation des données dans EXCEL

Considérons l’exemple des télécommandes. Il y a deux variables de décision, une fonction

objectif définie par z = 1.5x1 + 2x2 qu’il faut maximiser et trois contraintes :
x1 + 2x2 ≤ 1000
x1 ≤ 700
x2 ≤ 400

Voici une feuille Excel minimale contenant toutes ces informations

• Les cellules B2 et C2 représente les deux variables de décision.

• La fonction objectif est donnée dans la cellule B3. La formule donnera comme résultat 1.5
fois le contenu de B2 c’est-à-dire 1.5x1 plus 2 fois le contenu de la cellule C2, soit 2x2 .
• La cellule B5 donne le membre de gauche de la première contrainte tandis que les cellules
B6 et B7 donnent les membres de gauche de la deuxième et de la troisième contrainte.

L’information préalable est alors disponible dans le logiciel. L’étape suivante consiste à exé-
28 MODULE 3 Solution pour k variables

cuter l’outil solveur. La fenêtre est dialogue est la suivante :

• La section "Cellule cible à définir" donne la référence à la cellule qui contient la formule
pour calculer la fonction objectif.
• La plage "Cellules variables" donne la plage de valeurs correspondant aux variables de
décision.
• La section "Contraintes" donne chacune des contraintes en utilisant les formules entrées
dans EXCEL.
• La section "égal à" permet de choisir pour la fonction objectif un minimum, un maximum
ou une valeur précise.
• Le bouton "Options" permet de demander un modèle linéaire et de poser toutes les variables
comme étant positives. S’il n’y a que quelques variables qui sont non négatives alors il faut
utiliser la partie "Contraintes" pour le spécifier sur chacune des variables.
 Solveur de EXCEL 29

Après l’exécution de l’algorithme on obtient la sortie EXCEL suivante :

• Dans la section "cible" on retrouve la référence à la valeur initiale et finale de la fonction

objectif. En plus, il y a le type d’objectif (max ou min). Comme il est facile de faire une
erreur en selectionnant les options c’est important de s’assurer que c’est bien le sens espéré.
On indique la valeur de la fonction objectif au début de l’algorithme (valeur initiale) et à la
fin (valeur finale).
• Dans les sections "Cellules Variables" on a les valeurs des variables de décision au début
de l’algorithme (valeur initiale) puis à la fin (valeur finale).
• Finalement dans la section "Contraintes" on observe les formules définissant les con-
traintes; une indication si les variables sont liées c’est-à-dire si la valeur optimale est égale
à la contrainte (liée) ou si elle est différente et dans le cas échéant quelle est la différence
entre la contrainte et la valeur de la constante (marge).

Dans l’exemple des télécommandes on s’assure que l’objectif était bien une maximisation par
la suite il apparaît que la valeur optimale est obtenue lorsque les variables x1 et x2 sont égales
respectivement à 700 et 150. Cela veut dire qu’il faudrait fabriquer exactement 700 télécom-
mandes régulières et 150 "deluxe". De plus, pour les deux premières contraintes la valeur de
la marge étant de 0, cela veut dire que la variable d’écart lié à ces contraintes est nulle tandis
que la variable d’écart lié à la contrainte sur les télécommandes "deluxe" est de 250. La borne
donnée pour chacune des deux premières contraintes est atteinte tandis que pour la troisième
contrainte il y a un "reste" de 250 qui indique qu’il y a place pour fabriquer 250 télécommandes
de type "deluxe" selon cette contrainte.

Lorsque les constantes sont des ressources disponibles cela indique qu’il y aura une certaine
quantité de cette matière première qui ne sera pas utilisée si la solution optimale est mise en
application.
30 MODULE 3 Solution pour k variables

Remarque 4.1 Les données de base du logiciel permettent d’obtenir une solution sous la
forme du rapport de réponse mais il n’y a aucune information sur le type de variables de
décision ou sur les contraintes. Pour obtenir ces informations sur le rapport comme dans
l’exemple ci-haut il faut les ajouter dans la feuille EXCEL :
Voici une feuille modifiée pour le problème des télécommandes :
Normale Deluxe
700 150
Profit =1,5*B2+2*C2
Contraintes
Ressources =B2+2*C2
Max Normale =B2
MaX Deluxe =C2

et voici un exemple du rapport de réponse correspondant :

Cellule cible (Max)
Cellule Nom Valeur initiale Valeur finale
$B$3 Profit 1350 1350

Cellules variables
Cellule Nom Valeur initiale Valeur finale
$B$2 Normale 700 700
$C$2 Deluxe 150 150

Contraintes
Cellule Nom Valeur Formule État Marge
$B$5 Ressources Contraintes 1000 $B$5<=1000 Lié 0
$B$7 MaX Deluxe Contraintes 150 $B$7<=400 Non lié 250
$B$6 Max Normale Contraintes 700 $B$6<=700 Lié 0

Comme on peut voir ci-haut les commentaires dans la cellule au dessus de chaque variable de
décision sont reproduits dans le rapport.
On remarque qu’il y a quelques différences importantes pour la compréhension du rapport :
• La cellule cible utilise le commentaire à gauche et en haut pour donner le nom.
• Les cellules variables utilisent le commentaire à gauche et les commentaires en haut pour
donner un nom à la cellule.
• Les cellules contraintes utilisent le commentaire à gauche et les commentaires en haut pour
donner un nom à la cellule. La colonne "Valeur" utilise la borne donnée lors de la définition
de chaque contrainte.

Exemple 4.1 ⋆Un artisant doit produire trois types colliers. Le premier utilise 5 perles
blanches, 2 perles de corail et une dent de requin et il rapporte 25$. Le deuxième utilise 4
 Solveur de EXCEL 31

perles blanches, 5 perles de corail et 3 dents de requin et il rapporte 35 $. Le troisième utilise

5 perles blanches, 5 perles de corail et 5 dents de requin et il rapporte 45$. L’artisant dispose
de 175 perles blanches, 120 perles de corail et 95 dents de requin. Donner les quantités de
chaque type de collier pour optimiser le profit et interpréter la solution.
Solution : Posons xi la variable qui donne le nombre de colliers de type i. L’objectif est de
maximiser la fonction
z = 25x1 + 35x2 + 45x3
sujet aux contraintes
5x1 + 4x2 + 5x3 ≤ 175
2x1 + 5x2 + 5x3 ≤ 120
x1 + 3x2 + 5x3 ≤ 95
et xi ≥ 0.
La feuille EXCEL devrait ressemblée à
Colliers Type 1 Type 2 Type 3

Profits
=25*B2+35*C2+45*D2

Max
Blanche =5*B2+4*C2+5*D2
Corail =2*B2+5*C2+5*D2
Requin =B2+3*C2+5*D2

en considérant que les cellules correspondants aux variables de décision sont les cellules B2,
C2 et D2.

L’exécution du solveur donne le rapport de réponse :

Cellule cible (Max)
Cellule Nom Valeur initiale Valeur finale
$A$4 Profits 0 1186,428571

Cellules variables
Cellule Nom Valeur initiale Valeur finale
$B$2 Type 1 0 19,28571429
$C$2 Type 2 0 2,857142857
$D$2 Type 3 0 13,42857143

Contraintes
Cellule Nom Valeur Formule État Marge
$B$7 Blanche Max 175 $B$7<=175 Lié 0
$B$8 Corail Max 120 $B$8<=120 Lié 0
$B$9 Requin Max 95 $B$9<=95 Lié 0
32 MODULE 3 Solution pour k variables

Exemple 4.2 On obtient un profit maximal si le nombre de colliers de type I est de 19,29, le
nombre de colliers de type II est de 2,86 et le nombre de colliers de type III est 13,43. De plus,
selon cette répartition, il n’y a aucune perte sur les ressources puisque les marges à 0 indique
qu’il n’y a pas de quantité non utilisée.

Remarque 4.2 Une des hypothèses du modèle linéaire est la continuité sur les variables de
décision. Cela n’est généralement pas le cas surtout si les variables de décision sont définies
par "nombre de". La solution du simplexe est donnée en nombres réels tandis que la solution
demandée est souvent en nombres entiers. Pour trouver la solution effective il faut trouver les
entiers les plus proches qui sont succeptibles de donner une solution réalisable. Pour ce faire
il suffit de modifier les valeurs des variables de décision de la solution optimale dans EXCEL
pour que les valeurs soient entières et que les contraintes soient respectées.
Dans l’exemple des colliers, la solution optimale proposée est (19, 29, 2, 86, 13, 43). Pour
obtenir un nombre de colliers entier il faut remplacer par des valeurs entières jusqu’à ce les
contraintes soient respectées. Cela peut demander plusieurs manipulations si le nombre de
variables est grand mais une bonne stratégie est d’arrondir les valeurs optimales et commencer
la recherche à partir de ce point.

En considérant l’exemple des colliers, voici une première solution réaliste (en nombres entiers)
obtenue par arrondi :
Colliers Type 1 Type 2 Type 3
19 3 13
Profits
1165

Max
Blanche 172
Corail 118
Requin 93

On constate qu’en produisant exactement 19 colliers de type I, 3 colliers de type II et 13 colliers

de type III on obtient un profit de 1165$ et les contraintes sont respectées. Cela n’est pas trop
loin de la solution optimale obtenue en nombres réels.

En cherchant un peu plus il est possible de trouver une meilleure solution :

Colliers Type 1 Type 2 Type 3
19 2 14
Profits
1175

Max
Blanche 173
Corail 118
Requin 95
 Solveur de EXCEL 33

soit 19, 2 et 14 respectivement pour les trois types de colliers pour un profit de 1175$. Il n’y
a pas de méthode précise pour obtenir la solution en nombres entiers à partir de la solution en
nombres réels, il faut la trouver à tâtons.

Remarque 4.3 L’algorithme ne permet pas de déceler directement que le problème est non
borné. La valeur de l’optimal ou des variables de décision donneront des valeurs proches de
la limite acceptée par l’ordinateur ou il y aura un avertissement que l’algorithme ne converge
pas :

Remarque 4.4 Lorsqu’il n’y a pas de solution réalisable, l’algorithme donne le message
suivant :

Remarque 4.5 L’algorithme EXCEL permet de résoudre des modèles qui ne sont pas néces-
sairement linéaire et c’est l’option par défaut. Lorsque le problème n’est pas trop complexe
cela a peu d’importance mais dans le cas contraire cela peut mener a un temps de calcul ex-
orbitant. Il est donc plus sure de "cocher" l’option linéaire. Pour ce faire il faut sélectionner
"options" avant l’exécution du solveur et le bouton "supposé linéaire".
34 MODULE 3 Solution pour k variables

Remarque 4.6 Lorsque toutes les variables sont non négatives il y a une option qui permet de
toutes les définir comme telles. Si une ou plusieurs variables de décision peuvent être négative
alors il faut ajouter toutes les variables de décision dans la liste des contraintes.

Remarque 4.7 L’option "Afficher les itérations" du solveur permet de suivre toutes les itéra-
tions de l’algorithme du simplexe et vérifier s’il y a une solution multiple. Dans ce dernier cas
les dernières itérations donnent exactement la même valeur de la fonction objectif avec des
valeurs différentes pour les variables de décision.

3.5 Résumé

Dans ce module on s’intéresse à l’algorithme du simplexe pour trouver la solution optimale à

un PPL. L’idée est de créer un polygone des solutions réalisables dans un espace à k dimensions
et à chercher parmi tous les sommets celui ou ceux qui donne la valeur optimale de la fonction
objectif.
La technique pour ce faire est de créer la forme standard du PPL, soit la forme qui donne toutes
les contraintes sous forme d’égalité. Pour ce faire il faut ajouter ou soustraire des variables
d’écart aux inéquations.
Se basant sur la forme standard on peut trouver manuellement la solution au PPL en regardant
la valeur des variables de décision et de la fonction objectif à chaque sommet de ce polygone.
Pour ce faire il faut regarder toutes les possibilités de choisir autant de variables de décision
que d’équations dans le problème. S’il y a m équations et n variables de décision en comptant
n


les variables d’écart alors il y a m "sommets" à regarder. À chaque "sommet" il faut résoudre
le système d’équations linéaire qui est composé de m variables de base et n − m variables hors
base (égales à 0). Lorsque la solution de ce système est réalisable alors on la garde. Après
avoir effectuer la recherche de solution pour tous les sommets on choisit le sommet qui donne
l’optimal pour la fonction objectif.
Cette technique des solutions de base est la base de l’algorithme du simplexe qui permet de ne
regarder les sommets qui ont un avantage par rapport à ceux déjà trouvés. C’est cet algorithme
qui est utilisé par le "Solveur" du logiciel Excel : les données doivent être entrées dans le
logiciel selon le format demandé et le logiciel produit un rapport de réponse donnant la solution
lorsque celle-ci existe.