Chapitre 16

Chapitre XVI
PROGRAMMATION LINÉAIRE
La programmation linéaire1 est une branche de la programmation mathéma-

tique qui s’occupe de problèmes d’optimisations sous contraintes. Cette discipline
a longtemps fait l’objet de communications dont les apports se situaient essentiel-
lement au niveau de la performance des algorithmes proposés. Depuis la fin des
années quatre-vingt, des approches innovantes d’utilisation de ces techniques sont
disponibles et, combinées aux progrès spectaculaires réalisés en micro-informa-
tique, rendent accessibles ces approches au traitement de problèmes complexes,
dans des conditions raisonnables de temps et de coût de traitement. On commen-
cera par une présentation des techniques de base de la programmation linéaire
(section I) avant d’examiner (section II, page 1132) quelques extensions de ces
approches qui permettent de traiter des problèmes réalistes complexes et de tirer
pleinement parti des nouveaux outils disponibles.
Table des
matières
SECTION I PRÉSENTATION DES BASES TECHNIQUES DE LA

PROGRAMMATION LINÉAIRE
thématique
Seul le cas des variables continues sera étudié dans cette section. On commen-
Index
cera par exposer les fondements de la programmation linéaire qui sont simples et
non susceptibles d’améliorations (§ I-1). On examinera ensuite l’interprétation
économique des résultats, ce qui est important pour l’usage de cette technique en
gestion (§ I-2, page 1109), avant d’aborder (§ I-3, page 1111) l’analyse post-opti-
male intégrée dans les programmes de traitement informatique des problèmes de
programmation linéaire. Cet exposé rapide des fondements de l’analyse post-opti-
male est nécessaire car, en gestion, les paramètres utilisés sont connus avec une
certaine plage d’incertitude et toute présentation de solution ponctuelle a intérêt à
être relativisée par une étude de sensibilité. On présentera enfin (§ I-4, page 1117)
la méthode du simplexe utilisée pour résoudre numériquement le problème d’opti-
misation linéaire faisant intervenir des variables continues ; de nos jours, son
intérêt est plus de faciliter la compréhension des résultats et celle des analyses de
sensibilité que strictement opérationnel car, comme on le verra, les tableurs sont
dotés de fonctionnalités permettant de traiter facilement des problèmes de dimen-
sion modeste.
1. L’ouvrage, un peu ancien, de Wagner [435] reste l’un des plus clairs et complet (voir chapitres II à V) dans ce
domaine (l’exemple numérique de la première section de ce chapitre est tiré de cet ouvrage). La lecture de ce
texte peut être complétée, notamment en ce qui concerne les outils actuellement disponibles, par l’ouvrage
d’Eric Jacquet-Lagrèze [241].
1106 Gestion de la production et des flux
I-1 Les fondements de la programmation linéaire

Nous rappellerons successivement la formulation du problème (§ I-1.1) et sa
solution analytique (§ I-1.2, page 1106).
I-1.1 Formulation du problème
Sur le plan mathématique, le problème posé peut toujours se ramener à celui de
l’optimisation d’une fonction de forme linéaire, en respectant un ensemble de
contraintes linéaires, fonctions des mêmes variables, lesquelles doivent être posi-
tives ou nulles.
Dans cette forme, dite canonique, le problème s’écrit, s’il s’agit d’un problème
de maximisation:
n
• Max ∑ c j x j
j=1
n
• sous m contraintes : ∑ aij x j ≤ bi , pour i = 1, …, m
1
j=1
• avec x j ≥ 0 = ? , pour j = 1, …, n
Si le problème posé est un problème de minimisation, on se ramène au cas
n
précédent en maximisant ∑ ( –c j x j ) .
Table des
matières
j=1
Le problème peut être posé également sous une forme dite standard qui ne
diffère de la forme canonique que par la transformation des inégalités en égalités.
Ceci n’est possible qu’au prix de la création d’une variable d’écart xn + i , par
thématique
contrainte i. Le coefficient aij affecté à cette variable d’écart est nul dans toutes les
Index
contraintes, sauf celle concernée par cette variable, et, dans ce dernier cas, est égal
à + 1 si l’inégalité est du type «inférieur ou égal», et à –1 dans le cas contraire.
Au problème posé, appelé problème primal correspond un problème dit dual
dans lequel:
- la fonction à minimiser (si le problème primal est un problème de maximum)
est une combinaison linéaire des bi ,
- cet optimum est lié à un ensemble de contraintes qui sont aussi des fonctions
linéaires des aij, mais bornées cette fois par les c j .
L’intérêt de l’examen simultané des problèmes dual et primal réside dans le fait
que des relations caractéristiques unissent leurs solutions et, en particulier, que la
valeur optimale prise par les deux fonctions à optimiser est la même. Ces deux
problèmes peuvent être présentés dans le tableau synoptique de la page 1107, ces
diverses notations y seront illustrées par un exemple numérique.
I-1.2 Solution analytique du problème
L’examen de la formulation standard du problème primal montre que les
contraintes se traduisent par un système comportant m équations et m + n incon-
1. Cette formulation «classique» est restrictive car il suffit qu’une seule de ces m contraintes soit du type ≤ ou =
pour que le problème de maximisation sous contrainte puisse être posé.
Chapitre XVI - Programmation linéaire 1107
TABLEAU 340
Formulations du problème
Problème primal Problème dual
Notation notation
matricielle en sommation en sommation matricielle
fonction à
optimiser
Max x0 , avec: Min y0 , avec:

Max x0 , avec: x0 = cx n m Min y0 , avec: y0 = y b
Forme canonique
x0 = ∑ c j x j y0 = ∑ bi yi
j=1 i=1
.x ≥ 0 .x ≥ 0 , pour j = 1, ... , . y ≥ 0 , pour i = 1, ... , . y ≥ 0

sous contraintes
j i
. Ax ≤ b avec: n m
. yA ≤ c avec:
A; x ; b
(m, n) (n, 1)(m, 1)
. ∑ x a ≤ b , pour i . ∑ y a ≤ c , pour j y; A; b
n
j=1
j ij i
m
i=1
i ij j
(1, m) (m, n) (1, n)
= 1, ... , m = 1, ... , n
Max x0 , avec: Min y0 , avec:
Max x0 Min y0
.x = ∑ c x n+m
. y = ∑ by n+m
fonction à
optimiser
avec x0 = cx et 0 j j 0 i i avec y0 = yb et
j=1 i=1
; b
c ; x
(1, n + m) (n + m, 1) . c = 0, ∀ j tel que . b = 0, ∀ i tel que
j i
y
(1, m + n) (m + n, 1)
n+1≤ j≤n+m 1≤i≤n

Table des
matières
. x≥0 . x ≥0
j . y ≥0
i . y≥0
. Dx = b, avec: . ∑ d x =b
n+m
ij j i . ∑ g y =c
n+m
ij i
. yG = c, avec:
j
Forme standard
j=1 i=1
D = [ A, I ] et I . avec: . avec: G = –I et I
thématique
Sous contraintes
(m, n + m) (m, m) A (m, m)

i = 1, ... , m i = 1, ... , m + n
Index
. et:j = 1, ... , n + m j = 1, ... , n

. et: (m, n + m)
* dij = aij , pour ∀i * gij = ah j , pour ∀ j

et j = 1, ... , n i = n+h
* dij = 1 , pour ∀i et et 
 h = 1, …, m
j=n+ i
* dij = 0 , pour ∀i et * gij = –1 , pour ∀ j
j≠n+i>n et i = j ≤ n
* gij = 0 , pour ∀ j et
i≠ j>n
Remarque
Les x j tels que Les yi tels que

j = n + 1, ... , n + m i = 1, ... , n
sont les variables sont les variables
d’écart du primal d’écart du dual
nues. Le système peut toujours être satisfait avec n variables nulles, les m restantes
étant normalement non nulles, ce dernier ensemble constituant une base. Il est
intuitivement évident que x0 sera optimal pour une combinaison de variables non
nulles comportant le moins de variables possibles, c’est-à-dire m. Si nous permu-
tons alors les colonnes de la matrice D, de façon qu’aux m premières, correspon-
dent les variables constitutives de l’une des bases possibles et désignons par B
cette sous-matrice de D, et N la sous-matrice résiduelle, l’équation matricielle

devient alors, en indiçant en conséquence x par B et par N (⇒ xB et xN ):
xB
Dx = [B,N] = BxB + NxN = b relation 472
xN
Comme xN est nul, il en résulte que la solution du système est:
–1
xB = B b relation 473
–1
La valeur prise par la fonction-objectif est alors cBB b , mais nous ignorons si
cette valeur de la fonction-objectif constitue l’optimum recherché (lequel, souli-
gnons-le, peut être obtenu pour plusieurs bases différentes). Pour répondre à cette
question, il faudrait, a priori, rechercher la valeur prise par la fonction-objectif
( n + m )!
pour chacune des ------------------- bases possibles (= combinaisons de m éléments pris
m!n!
parmi m + n).
Pour éviter d’explorer l’ensemble des combinaisons possibles, ce qui devient
rapidement impossible lorsque n et m dépassent quelques dizaines, divers algo-
rithmes ont été mis au point. Le plus général, proposé dans les années cinquante
par Dantzig, est connu sous le nom de la méthode du simplexe et n’est rien d’autre
que l’utilisation de la méthode d’élimination de Gauss pour la résolution d’un
système d’équations, combinée avec l’utilisation d’un critère de sélection de bases
Table des
matières
et d’un indicateur permettant de dire si l’optimum est atteint. L’algorithme, qui
sera présenté brièvement au § I-4, page 1117, calcule simultanément les solutions
des problèmes primal et dual (si elles existent), puisque le critère utilisé nécessite1
le calcul de la solution du problème dual (sous sa forme standard), que l’on
démontre être:
thématique
Index
–1 –1
y = [ c B B A – c, c B B ] relation 474
et qui, à l’optimum2, doit être positif ou nul. L’optimum n’est atteint que si y ≥ 0 .
Le premier bloc de ce vecteur ligne (noté yc ) correspond aux valeurs prises par
les variables d’écart dans le problème dual, tandis que le second bloc (noté ye )
correspond aux valeurs prises par les variables qui n’interviennent que dans la
011 –c 01 m
1. Le tableau de simplexe du départ se présente matriciellement: , où 0pq est une matrice de 0 à p
b A Im
lignes et q colonnes et Im une matrice unité de rang m. À n’importe quelle itération (et donc pour n’importe
–1
1 –cB
quelle base), le tableau du simplexe s’obtient en prémultipliant la matrice précédente par , ce qui
0m1 B
c B B –1 b c B B –1 A – c c B B –1
donne . La méthode du simplexe fournit donc simultanément une solution opti-
B –1 b B –1 A B –1
male au problème primal (en donnant les seules valeurs non nulles de ce problème) et une solution au problème
dual (en fournissant toutes les valeurs des variables).
2. On peut remplacer À par N ou D, ce qui, à une permutation près (pour N) ou quelques zéros supplémentaires
(pour D), fournit les mêmes conditions mais ne correspond plus immédiatement à y tel que nous l’avons défini.
formulation canonique du problème, en conséquence de quoi, la valeur prise par

y0 est, pour une solution optimale y0* :
–1
y0* = y * b = cB B b = x0* relation 475
Nous vérifions donc ici la propriété énoncée plus haut et selon laquelle les fonc-
tions à optimiser des deux problèmes dual et primal ont à l’optimum la même
valeur.
Le grand intérêt de la méthode du simplexe est l’interprétation immédiate
donnée à ce vecteur y, dont chaque composante yi indique de combien diminue la
valeur optimale x0* lorsque l’on accroît d’une unité1 la variable correspondante xi
ou, ce qui revient au même, de combien s’accroît x0* lorsque l’on diminue d’une
unité la variable correspondante. Or, une propriété importante lie les problèmes
dual et primal: à l’optimum, lorsqu’une variable d’écart est positive, la variable
duale correspondante est nulle, et réciproquement. Autrement dit, à la marge, le
resserrement d’une contrainte non saturée n’a aucune incidence sur x0 tandis que
celui d’une contrainte saturée diminue (comme intuitivement on pouvait s’y
attendre) la valeur optimale de x0. L’introduction d’une unité d’une variable hors
base xi diminue aussi cette valeur optimale x0* de yi (on a alors m + 1 valeurs de
variables supérieures à zéro). L’analyse post-optimale (cf. § I-3, page 1111)
permet de pousser plus loin cette étude. Les tableaux 341 à 343 fournissent une
illustration numérique des différents points évoqués jusqu’ici.
I-2 Interprétation économique des résultats
Table des
matières
Dans une première catégorie de problèmes économiques, le vecteur x est un

vecteur de production, le vecteur c un vecteur de profit unitaire et le vecteur b un
vecteur de contraintes portant sur des ressources limitées. La matrice A est une
matrice de coefficients techniques dans laquelle l’élément aij indique la quantité
thématique
de ressources i, nécessaire à la production d’une unité du produit j.

Index
La signification prise par x0 est donc une valorisation de quantités. À

l’optimum, on a x0* = y0* , autrement dit, y0* s’analyse aussi comme une valorisa-
tion de quantités. Cette dernière expression correspond au produit scalaire yb dans
lequel le vecteur b s’analyse déjà comme un vecteur de quantités. Il s’ensuit que
y est nécessairement un vecteur de prix ou de coûts pour que y0 conserve la signi-
fication d’une valorisation de quantités.
Compte tenu de l’interprétation mathématique de y dans la variation de la valeur
prise par x0 au voisinage de l’optimum, c’est plutôt à une notion de coût que l’on
fait appel et, compte tenu de leur caractère fictif, l’usage veut qu’on les appelle
coûts-fantômes. Les variables duales correspondant aux contraintes du problème
primal sont appelées aussi prix-fantômes.
D’autres problèmes économiques cherchent à satisfaire un ensemble de
demandes définies par des seuils minimaux représentés par un vecteur b, à l’aide
de facteurs productifs en quantité x (à déterminer) dont le coût est c, et tel que
l’utilisation d’une unité de facteur productif permet de satisfaire aij de la
demande i. Le problème est alors un problème de minimisation du coût global de
production et s’écrit:
1. En toute rigueur, il s’agit de la dérivée de la fonction-objectif, par rapport à la contrainte.
TABLEAU 343
Résultat du simplexe et interprétation des résultats
. Tableau numérique initial

Résultats du simplexe
. Tableau numérique final
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
695 0 3 11 13 5
0 –4 –5 –9 –11 0 0 0 ---------
7
---
7
0 ------
7
------
7
0 ---
7
50 5 –5 10 –1
15 1 1 1 1 1 0 0 ------ 1 --- 0 ------ ------
7
0 ------
7 7 7 7
325 0 –6 13 –61 4
120 7 5 3 2 0 1 0 --------- ------ 0 ------ --------- 1 ---
7 7 7 7 7
55 0 2 12 –3 1
------ --- ------ ------ 0 ---
100 3 5 10 15 0 0 1 7 7 1 7 7 7
Tableau analytique correspondant Tableau analytique correspondant

y*
011 -c 01 m cB B –1 b cB B –1 A – c cB B –1 x0* = y0*
yc* ye*
=
b A Im B –1 b B –1 A B –1 xB* B –1 A B –1
. Tableau numérique initial après permutation des colonnes pour «isoler» la base (l’ordre retenu pour les
variables rentrant dans la base doit être tel que l’on ait B –1 B = I )
0 2 4 5 7 1 6 3
0 –5 –11 0 0 –4 0 9 taleau analytique correspondant
15 1 1 1 0 1 0 1
011 –cN –cB
b N B
120 5 2 0 0 7 1 3
100 3 15 0 1 3 0 10
Interprétation des résultats pour le problème primal

Fonction à maximiser : x0 = 4 ( 50 ⁄ 7 ) + 9 ( 55 ⁄ 7 ) = 695 ⁄ 7
Contrainte 1: 1 ( 50 ⁄ 7 ) + 1 ( 55 ⁄ 7 ) = 15 (saturation)
À l’optimum on a
Contrainte 2: 7 ( 50 ⁄ 7 ) + 3 ( 55 ⁄ 7 ) = 515 ⁄ 7 (non saturation, reste 325/7)
Contrainte 3: 3 ( 50 ⁄ 7 ) + 10 ( 55 ⁄ 7 ) = 100 (saturation)
..
Interprétation mathématique des variables duales
Introduction supplémentaire d’une variable hors base dans la solution: exemple 1x2
x1 → 50 ⁄ 7 – 5 ⁄ 7 = 45 ⁄ 7 ; x6 → 325 ⁄ 7 + 6 ⁄ 7 = 331 ⁄ 7 ; x3 → 55 ⁄ 7 – 2 ⁄ 7 = 53 ⁄ 7
. contrainte 1: 1 ( 45 ⁄ 7 ) + 1 ( 1 ) + 1 ( 53 ⁄ 7 ) = 15 (saturation)
. contrainte 2: 7 ( 45 ⁄ 7 ) + 5 ( 1 ) + 3 ( 53 ⁄ 7 ) = 509 ⁄ 7 (non saturation, reste 331/7)
. contrainte 3: 3 ( 45 ⁄ 7 ) + 5 ( 1 ) + 10 ( 53 ⁄ 7 ) = 100 (saturation)
.
. fonction-objectif: 4 ( 45 ⁄ 7 ) + 5 ( 1 ) + 9 ( 53 ⁄ 7 ) = 692 ⁄ 7 (soit une perte de 3/7)
Resserrement d’une contrainte saturée: exemple b → 14 1
. x → 50 ⁄ 7 – 10 ⁄ 7 = 40 ⁄ 7 ; x → 325 ⁄ 7 + 61 ⁄ 7 = 386 ⁄ 7 ; x → 55 ⁄ 7 + 3 ⁄ 7 = 58 ⁄ 7
. contrainte 1: 1(40 ⁄ 7) + 1(58 ⁄ 7) = 14 (saturation)
1 6 3
. contrainte 2: 7 ( 40 ⁄ 7 ) + 3 ( 58 ⁄ 7 ) = 424 ⁄ 7 (non saturation, reste 386/7)

. contrainte 3: 3(40 ⁄ 7) + 10(58 ⁄ 7) = 100 (saturation)
. fonction-objectif: 4(40 ⁄ 7) + 9(58 ⁄ 7) = 682 ⁄ 7 (soit une perte de 13/7)
TABLEAU 341
Formulation du problème
PRIMAL DUAL
Formulation Formulation Formulation
matricielle explicite matricielle
Max x0 (=cx), avec Min y0 (= yb), avec
c = 4 5 9 11 0 0 0 y = y1 y2 y3 y4 y5 y6 y7
Fonction à
optimiser
Max x0, avec Min y0, avec
formulation
x’= x1 x2 x3 x4 x5 x6 x7 





... canonique
Dans la

 x0 = 4x1 + 5x2 + 9x3 + 11x4 y0 = 15y5 + 120y6 + 100y7 
formulation





 ... canonique






Dans la
  ... standard






 ... standard
A x ≤ b, avec
Forme canonique
1x1+1x2+1x3+1x4≤ 15 1y5 + 7y6 + 3y7 ≥ 4

1111 7x1+5x2+3x3+2x4≤ 120 1y5 + 5y6 + 5y7 ≥ 5
15
A= 7532 b = 120 3x1+5x2+10x3+15x4≤100 1y5 + 3y6 + 10y7 ≥ 9 yA ≥ c
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 ; 1 y5 + 2 y6 + 15 y7 ≥ 11
3 5 10 15 100
x4 ≥ 0 y5 ≥ 0 ; y6 ≥ 0 ; y7 ≥ 0
Sous contraintes
(1) 1x1+1x2+1x3+1x4+ x5 yG = c; avec:

Dx = b , avec
= 15 (1’) 1y5 + 7y6 + 3y7 –y1= 4 –1 0 0 0
Forme standard
D= 1 1 1 1 1 00
(2)7x 1+5x 2+3x 3+2x 4+x 6 (2’) 1y 5 + 5y 6 + 5y 7 –y 2= 5 0 –1 0 0 -I
7 5 3 2 0 1 0
= 120 (3’) 1 y + 3 y +10 y – y = 9 0 0 –1 0
Table des
3 5 10 15 0 0 1
matières
5 6 7 3
(3)3x 1+5x 2+10x 3+15x 4+x 7 G= 0 0 0 –1 =
15 (4’)1y 5 + 2y 6 +15y 7 – y 4=11
= 100 1 1 1 1
b= 120 yi ≥ 0, ∀i A
x j ≥ 0, ∀ j 7 5 3 2
100 3 5 10 15
thématique
Index
Min cx
sous contraintes Ax ≥ b et x ≥ 0
Les variables duales associées aux contraintes productives s’analysent comme
un système de prix correspondant à une tarification au coût marginal puisque
chaque yi représente l’accroissement du coût global résultant d’une extension
d’une unité de la ième contrainte, c’est-à-dire de la satisfaction d’une unité supplé-
mentaire de demande de i1. Ce système de prix en outre est tel qu’il assure juste
la couverture des coûts de production, propriété qui résulte de l’égalité à
l’optimum, des deux fonctions-objectifs.
I-3 Introduction à l’analyse post-optimale
L’analyse post-optimale consiste en une étude de sensibilité des résultats
ponctuels fournis par la résolution du programme linéaire, lorsque l’on fait varier
une ou plusieurs valeurs des paramètres de c, b ou A. En pratique, on réserve le
terme d’analyse post-optimale à la recherche des domaines de variation de ces
paramètres qui n’entraînent pas de remise en cause de la base retenue dans la solu-
1. Notons que si la demande à satisfaire pour certains produits est faible et que, dans le processus productif, il est
inévitable de les produire en assez grande quantité (productions dites fatales), les contraintes correspondantes
ont de fortes chances de ne pas être saturées, les variables duales associées sont alors nulles, et de ce fait les tarifs
correspondants le sont aussi, ce qui, commercialement parlant, peut poser quelques problèmes.
TABLEAU 342
Présentation de la solution
Primal Dual
Solution:
x B = B –1 b ; x N = 0 ;
x 0 = cB B –1 b
xB*' = x * x * x * = 50 325 55
1 6 3 ----- - --------- ------
7 7 7
1 0 1
B= 7 1 3
3 0 10
cB = La solution du problème
4 0 9 Solution optimale dual exprimé avec les résul-
xN*'= x * x * x * x * = 0 0 0 0 des problèmes primal et dual tats du primal est:
2 4 5 7
1 1 1 0
h 0 1 2 3 4 5 6 7 y * = cB B –1 A – c cB B –1
N= 5 2 0 0 50
xh* 695 55 325
--------- ------ 0 ------ 0 0 --------- 0





5 15 0 1





7 7 7 7 Variables Variables
695 3 d’écart canoniques
cN = 5 11 0 0 yh* --------- 0 --- 0 ------ ------ 0 5---
11 13 du dual du dual
7 7 7 7 7 soit ici:
Variable d’écart 
Solution optimale si y1* y2* y3* y4* y5* y6* y7*

Table des
.ou cB B–1 D – c ≥ 0 et cB B–1 ≥ 0
matières
du dual  y* = 0 3--- 0 11 13 0 5
------ ---
Variable d’écart 
(formulation standard) ------
7 7 7 7
.ou cB B–1 A – c ≥ 0 et cB B–1 ≥ 0 
du primal 





(formulation canonique) prix-fantômes
.ou cB B–1 N – cB ≥ 0 et cB B–1 ≥0 Lorsqu’une variable d’écart est nulle, la du primal





variable duale correspondante est positive et
thématique
avec réciproquement coûts-fantômes
Index
du primal
cB B –1 D – c = 0 3--- 0 11
------ 0 0 0
7 7
1234
cB B –1 A – c = 0 3--- 0 11
------
7 7
163
cB B –1 = 13 5
------ 0 ---
7 7
2457
cB B –1 N – cB = 3--- 11
------ 0 0
7 7
tion ponctuelle de départ, les valeurs prises dans la base pouvant changer. Le terme
d’analyse paramétrée est utilisé pour les analyses de sensibilité qui acceptent de
remettre en cause les solutions de départ. On ne s’attardera ici que sur les analyses
portant sur les vecteurs c et b, d’une part parce que ce sont celles qui nous intéres-
sent au premier chef et, d’autre part, parce que l’analyse post-optimale portant sur
les coefficients de la matrice A, simple dans ses fondements, nécessite dans sa
présentation de longs développements de calcul matriciel.
I-3.1 Modification de coefficients de la fonction-objectif

–1
La solution du programme linéaire est, nous l’avons vu, B b , expression qui
est indépendante des coefficients de la fonction-objectif et pour laquelle on est
assuré que les contraintes sont satisfaites. Mais cette modification du vecteur c qui
devient c + ∆c ne permet plus d’affirmer que la solution reste optimale et donc
inchangée. Pour qu’il en soit ainsi, il faut que les conditions d’optimalité
–1 –1
( cB B A – c ≥ 0 et cB B ≥ 0 ) restent satisfaites avec le nouveau vecteur c + ∆c,
c’est-à-dire que l’on ait (en désignant par yc* et ye* les valeurs optimales de y*
correspondant respectivement aux variables canoniques et aux variables d’écart
du problème primal):
–1 –1 –1
( cB + ∆cB )B A – ( c + ∆c ) = { cB B A – c } + ∆cB B A – ∆c
–1 –1
( cB + ∆cB )B A – ( c + ∆c ) = yc* – ∆c + ∆cB B A ≥ 0 relation 476
–1 –1 –1 –1
( cB + ∆cB )B = cB B + ∆cB B
= ye* + ∆cB B ≥ 0 relation 477
La lecture du tableau du simplexe nous indique que:
–1 –1
yc* = { cB B A – c } = [ 0, 3 ⁄ 7, 0, 11 ⁄ 7 ] ; ye* = cB B = [ 13 ⁄ 7, 0, 5 ⁄ 7 ]
1 5⁄7 0 –5 ⁄ 7 10 ⁄ 7 0 –1 ⁄ 7
–1 –1
B A= 0 –6 ⁄ 7 0 13 ⁄ 7 ; B = –61 ⁄ 7 1 4⁄7
0 2⁄7 1 12 ⁄ 7 –3 ⁄ 7 0 1⁄7
Table des
matières
L’examen de ces conditions nous mène à dissocier le cas des coefficients de

variables de la base, de celles qui ne sont pas dans la base. Nous examinerons
successivement ces 2 cas lorsqu’un seul coefficient peut varier. Nous aborderons
thématique
ensuite le cas général avec l’étude des implications de la variation simultanée de

Index
deux coefficients.
I-3.1.1 Modification d’un coefficient d’une variable hors base
Comme ∆cB est nul par hypothèse, les conditions se simplifient: la seconde
condition (relation 477) est toujours satisfaite, tandis que la première (relation
476) devient: yc* – ∆c ≥ 0 , d’où ∆c ≤ yc* .
Autrement dit, les coefficients des variables «hors base» peuvent varier sans
remettre en cause l’optimalité de la solution de départ, à condition que cette varia-
tion soit au plus égale à la valeur optimale duale correspondante s’il s’agit d’un
accroissement, et sans limitation si cette variation est négative.
Exemple : La variable x2 de notre exemple numérique est hors base, son coefficient peut
varier sans remettre en cause l’optimum x1* = ------ ; x6* = --------- ; x3* = ------ , si c2 ≤  5 + --- ou, ce
50 325 55 3
7 7 7 7
3
qui revient au même, si ∆ c2 ≤ --- .
7
I-3.1.2 Modification d’un coefficient d’une variable de la base
Dans ce cas, la valeur prise par l’optimum x0 change du fait de la variation des
–1
cB puisque x0 = cB B b , sans que l’on ait pour autant de modification des valeurs
prises par la base (comme nous l’avons vu ci-dessus). Si un seul coefficient c j
change, on a autant d’inéquations à une seule variable (∆ c j ) qu’il y a de variables

duales, l’intersection des domaines de validité fournit alors la réponse souhaitée.
Exemple: Supposons que le coefficient c 1 seul varie pour devenir c1 = 4 + ∆c1 , on a alors
∆c = [ ∆c1, ∆c2 = 0, ∆c3 = 0, ∆c4 = 0] = [ ∆c1, 0, 0, 0] et
∆cB = [ ∆c1, ∆c6 = 0, ∆c3 = 0] = [ ∆c1, 0, 0 ] et l’on peut écrire:
–1
( cB B A – c ) – ∆c = yc* – ∆c = [ 0, 3 ⁄ 7, 0, 11 ⁄ 7] – [ ∆c1, 0, 0, 0 ] = [ –∆c1, 3 ⁄ 7, 0, 11 ⁄ 7 ]
les conditions d’optimalité sont donc:
–1
• ∆ cB B A + yc* – ∆c ≥ 0
1 5 ⁄ 7 0 –5 ⁄ 7
[ ∆c1, 0, 0 ] ⋅ 3 11 ≥ 0
0 –6 ⁄ 7 0 13 ⁄ 7 + –∆c1, --7-, 0, -----7
-
0 2 ⁄ 7 1 12 ⁄ 7
3 5 11 5
c’est-à-dire: --- + --- ∆c1 ≥ 0 ; ------ – --- ∆c1 ≥ 0
7 7 7 7
–1
• ∆cB B + ye* ≥ 0
10 ⁄ 7 0 –1 ⁄ 7
13 5
[ ∆c1, 0, 0 ] ⋅ –61 ⁄ 7 1 4 ⁄ 7 + ----- -, 0, --- ≥ 0
7 7
–3 ⁄ 7 0 1⁄7
13 10 5 1
c’est-à-dire: ------ + ------ ∆c1 ≥ 0 ; --- – --- ∆c1 ≥ 0
7 7 7 7
Table des
matières
La réunion de ces conditions permet de définir le domaine suivant:
–3 ⁄ 5 ≤ ∆c1 ≤ 11 ⁄ 5
La valeur optimale varie dans cet intervalle de définition comme, x1* ∆c1 puisque x1* n’est pas
thématique
50 695 50
Index
affecté; c’est-à-dire que l’on a (voir figure 264): x0 = x0* + ------ ∆c1 = --------- + ------ ∆c1
7 7 7
FIGURE 264
Modification d’un coefficient d’une variable de la base
x0
805 = 115
7
110
50 ∆c 1
105 695 + 7
x0 = 7
100 695
95 7
∆c1
–1 –3/5 0 1 2 11/5
c1
3 3,4 4 5 6 6,2
I-3.1.3 Modification de plusieurs coefficients de la fonction-objectif

Que la variation porte sur un ou plusieurs coefficients, les conditions d’optima-
lité doivent rester satisfaites avec le nouveau vecteur c + ∆c, c’est-à-dire que l’on
–1 –1
doit avoir: yc* – ∆c + ∆cB B A ≥ 0 et ye* + ∆cB B ≥ 0 .
Supposons que l’on admette une variation simultanée des coefficients c1 et c3
(qui tous deux appartiennent à la base, mais le raisonnement général resterait le
même s’il n’en était pas ainsi); on a donc:
∆c = [ ∆c1, ∆c2 = 0, ∆c3, ∆c4 = 0 ] = [ ∆c1, 0, ∆c3, 0 ] relation 478
∆cB = [ ∆c1, ∆c6 = 0, ∆c3 ] = [ ∆c1, 0, ∆c3 ] relation 479
Dans notre exemple, la première des deux conditions d’optimalité implique donc:
1 5 ⁄ 7 0 –5 ⁄ 7
[ 0, 3 ⁄ 7, 0, 11 ⁄ 7] – [ ∆c1, 0, ∆c3, 0 ] + [ ∆c1, 0, ∆c3 ] 0 –6 ⁄ 7 0 13 ⁄ 7 ≥ 0
0 2 ⁄ 7 1 12 ⁄ 7
[ –∆c1, 3 ⁄ 7, –∆c3, 11 ⁄ 7 ] + [ ∆c1, ( 5∆c1 + 2∆c3 ) ⁄ 7, ∆c3, ( – 5∆c1 + 12∆c3 ) ⁄ 7 ] ≥ 0
[ 0, ( 3 + 5∆c1 + 2∆c3 ) ⁄ 7, 0, ( 11 – 5∆c1 + 12∆c3 ) ⁄ 7 ] ≥ 0 ,
3 + 5∆c1 + 2∆c3 ≥ 0
ce qui conduit au premier système de contraintes: .
11 – 5∆c1 + 12∆c3 ≥ 0
La seconde des deux conditions d’optimalité implique que l’on ait:
10 ⁄ 7 0 –1 ⁄ 7
Table des
matières
[ 13 ⁄ 7, 0, 5 ⁄ 7 ] + [ ∆c1, 0, ∆c3 ] –61 ⁄ 7 1 4⁄7 ≥0

–3 ⁄ 7 0 1⁄7
[ 13 ⁄ 7, 0, 5 ⁄ 7 ] + [ ( 10∆c1 – 3∆c3 ) ⁄ 7, 0, ( – ∆c1 + ∆c3 ) ⁄ 7 ] ≥ 0
[ ( 13 + 10∆c1 – 3∆c3 ) ⁄ 7, 0, ( 5 – ∆c1 + ∆c3 ) ⁄ 7 ] ≥ 0 ,
thématique
Index
1 3 13 + 10∆c – 3∆c ≥ 0
ce qui conduit au second système de contraintes: 5 – ∆c + ∆c ≥ 0
1 3
Ces systèmes de contraintes se traduisent graphiquement par le domaine de validité défini par
la zone en bleu pâle de la figure 265, page 1116.
Les valeurs de x1 et de x3 restant inchangées, la valeur prise par la fonction-objectif est:
50 55 695 50 55
x0 = x0* + ------ ∆c1 + ------ ∆c3 = --------- + ------ ∆c1 + ------ ∆c3 . Ajoutons, pour en terminer sur ce point, que
7 7 7 7 7
la généralisation à plus de deux coefficients, ne pose qu’un problème de «visualisation» du
domaine de validité des variations simultanées de ces coefficients.
I-3.2 Modification du second membre d’une contrainte
On remarque tout d’abord que cette analyse peut être effectuée à partir du
problème dual puisque les constantes des seconds membres des contraintes sont
aussi les coefficients de la fonction-objectif du dual. On peut toutefois faire sans
difficulté l’analyse directe de ce cas. En effet, les conditions d’optimalité (= coûts-
fantômes y*) ne font pas intervenir le vecteur b, on est donc assuré que la solution
est optimale, mais rien ne garantit alors que cette solution (= B–1b) reste faisable,
c’est-à-dire que toutes les composantes du vecteur x restent positives. On doit
donc avoir:
–1 –1
B ( b + ∆b ) = xB* + B ∆b ≥ 0 relation 480
FIGURE 265
Modification simultanée de plusieurs coefficients de la fonction-objectif
3+ ∆c3
3+
5∆c 1
13/3
5∆c 1
+ 2
+ 2
∆c 3
∆c 3
>0
>0
<0
c3
1 12∆
+
5 ∆c 1 <0
c3
-9/5 1 11 -
+ 12∆
5∆c 1
11 - 5 ∆c1
0
<0
> 0
>0
-5/5
∆c 3 <
3
3
+ ∆c
- 3∆c
3
- 3∆c
c 1 +
- ∆ ∆c 1
5 -
1
10∆c
1
10∆c
Table des
matières
13 +
-5
13 +
I-3.2.1 Cas d’une contrainte non saturée
thématique
Un raisonnement direct fournit la réponse au problème posé, mais on peut aussi
Index
utiliser l’inéquation matricielle 480.
- Raisonnement direct. La base de la solution optimale de départ intègre les
variables d’écart correspondant à ces contraintes. Pour qu’une variable
d’écart reste dans la base, il est donc nécessaire que la diminution du seuil,
dans le cas présenté de contraintes de type < (ou de leur accroissement dans
le cas contraire), ne soit pas supérieure à la valeur optimale d’origine de la
variable d’écart, puisqu’au mieux la contrainte est saturée. Par contre, on
pourra toujours desserrer une contrainte déjà non saturée. Il est évident que
la variation d’une variable d’écart est sans incidence sur l’optimum, puisque
le coefficient qui lui est associé dans la fonction-objectif est nul.
Exemple: La variable x6 de notre exemple numérique appartient à la base et sa valeur à
l’optimum est x6 = 325 ⁄ 7 . Le seuil b2 de la contrainte correspondante peut donc varier
de telle sorte que: ∆b2 ≤ 325 ⁄ 7 . La solution optimale reste donc inchangée tant que l’on
a: b2 ≤ 515 ⁄ 7 .
- Application de la condition formulée. Si une seule contrainte non saturée k
varie, les autres inéquations sont satisfaites car l’écart ∆bi correspondant est
nul, il ne reste donc plus qu’à voir si l’inéquation correspondante k est satis-
faite. On peut montrer d’après l’algorithme du simplexe que l’élément de la
–1
kème ligne et de la kème colonne de la matrice B est forcément égal à 1, il
s’ensuit que l’inéquation qui nous intéresse a pour formulation: xk* + ∆bk ≥ 0
Exemple: En reprenant notre exemple, on peut écrire:
50 ⁄ 7 10 ⁄ 7 0 –1 ⁄ 7 0 50 ⁄ 7 0
* + B –1 ∆b =
xB 325 ⁄ 7 –61 ⁄ 7 1 4 ⁄ 7
+ ⋅ ∆b 2 = 325 ⁄ 7 + ∆b 2 ≥ 0
55 ⁄ 7 –3 ⁄ 7 0 1 ⁄ 7 0 55 ⁄ 7 0
ce qui entraîne: ∆b2 ≤ 325 ⁄ 7 .
I-3.2.2 Cas de contrainte saturée

Supposons là encore qu’une seule contrainte varie. L’application de la condi-
tion formulée entraîne une série de m inéquations à une inconnue, d’où la
définition d’un domaine de validité, et une nouvelle valeur de l’optimum qui
–1
devient: x0* + cB B ∆b .
Exemple : Examinons le cas de la première contrainte de notre exemple numérique dont le
seuil devient 15 + ∆b1 . La solution reste optimale si:
50 ⁄ 7 10 ⁄ 7 0 –1 ⁄ 7 ∆b 50 ⁄ 7 + ∆b1 ( 10 ⁄ 7 )
–1 1
0 = 325 ⁄ 7 + ∆b1 ( –61 ⁄ 7 ) ≥ 0
* + B ∆b =
xB 325 ⁄ 7 + –61 ⁄ 7 1 4 ⁄ 7 ⋅
55 ⁄ 7 –3 ⁄ 7 0 1 ⁄ 7 0 55 ⁄ 7 + ∆b1 ( –3 ⁄ 7 )
Le domaine de variation de ∆b1 , qui permet à la solution d’être faisable, est donc :
–5 ≤ ∆b1 ≤ 325 ⁄ 61 . On peut vérifier que, si l’on se situe immédiatement en dessous de la borne
inférieure, x1 devient négatif et que, si l’on se situe au-dessus de la borne supérieure, c’est x6
qui devient négatif. L’optimum, qui est une fonction de ∆b1 , a pour expression:
10 ⁄ 7 0 –1 ⁄ 7 ∆b1
–1 695 13
x0 = x0* + cB B ∆b = 625 + [ 4, 0, 9 ] ⋅ –61 ⁄ 7 1 4 ⁄ 7 ⋅ 0 d’où: x0 = --------- + ------ ∆b1 .
7 7
–3 ⁄ 7 0 1 ⁄ 7
Table des
matières
0
FIGURE 266
Analyse post-optimale d’une contrainte saturée
thématique
x0
Index
46620
427
13 ∆b 1
695 + 7
x0 = 7
695
90 7
∆b1
-5 0 325/61
b1
10 15 20,33
I-4 Résolution d’un programme linéaire par l’algorithme du

simplexe
L’algorithme du simplexe, mis au point par Dantzig, est l’algorithme qui
s’avère être le plus efficace pour résoudre les problèmes généraux d’optimisation
sous contraintes dans lesquels:
- la fonction à optimiser, et que l’on appelle également fonction-objectif,

comporte plusieurs variables x j et est linéaire, c’est-à-dire est de la forme
∑c jx j ;
j
- toutes les variables x j sont continues et ne peuvent prendre que des valeurs
positives ou nulles;
- toutes les contraintes (repérées par l’indice i) sont également linéaires, c’est-
à-dire de la forme ∑ aij x j ≤ bi , le signe ≤ pouvant être remplacé par ≥ ou =
j
pour n’importe laquelle de ces contraintes.
Cette classe de problèmes d’optimisation sous contraintes est qualifiée habi-
tuellement de programme linéaire, mais on parle encore de programmation
linéaire1. L’algorithme que l’on va présenter peut ne pas être le plus efficace si le
problème à résoudre revêt une structure particulière. Ce point sera évoqué au § I-
4.3, page 1128.
Nous examinerons tout d’abord (§ I-4.1) comment résoudre par l’algorithme du
simplexe un problème de maximisation dans lequel les contraintes sont toutes du
type «inférieur ou égal», puis nous verrons (§ I-4.2, page 1122) comment traiter
les autres cas de figure. Avant de commencer, il faut souligner que l’objectif pour-
suivi ici est la description d’une méthode et non sa justification.
I-4.1 Problème de maximisation avec contraintes du type ≤
Table des
matières
Nous illustrerons la démarche en nous appuyant sur l’exemple numérique
suivant:
- maximiser x0 , avec x0 = 4x1 + 5x2 + 9x3 + 11x4 (qui correspond à la fonc-
tion-objectif),
thématique
Index
- sous contraintes:
1x1 + 1x2 + 1x3 + 1x4 ≤ 15
7x1 + 5x2 + 3x3 + 2x4 ≤ 120
3x1 + 5x2 + 10x3 + 15x4 ≤ 100
x1 ≥ 0 ; x2 ≥ 0 ; x3 ≥ 0 ; x4 ≥ 0
Cette formulation retenue ici est la formulation canonique (voir page 1106).
L’utilisation de l’algorithme du simplexe nécessite une transformation préalable
des inégalités en égalités, par l’introduction de variables d’écart (elles-mêmes
positives ou nulles). L’introduction de la variable d’écart x5 dans la première
contrainte, par exemple, conduit à la formulation équivalente suivante:
1x1 + 1x2 + 1x3 + 1x4 + 1x5 = 15
1. Lorsque les variables x j , au lieu d’être toutes continues, ne peuvent prendre que des valeurs entières positives
ou nulles, on parle alors de programme linéaire en nombres entiers (ou de programmation linéaire en nombres
entiers). Lorsque certaines variables sont continues et que les autres variables ne peuvent prendre que des valeurs
entières positives ou nulles, le problème posé est alors habituellement qualifié de programme linéaire mixte.
Par exemple, si chacune des 4 premières variables prend la valeur 2, la variable

x5 prendra la valeur 7 pour que l’égalité soit satisfaite. Cette variable d’écart ne
sera nulle que si la contrainte est juste saturée.
Lorsque, dans le problème posé, les contraintes sont toutes des égalités, la
formulation du problème est qualifiée de forme standard. Notons que certaines
contraintes du problème initial (forme canonique) peuvent déjà être des égalités,
auquel cas il n’y a pas lieu de créer de variables d’écart, mais des variables artifi-
cielles comme nous le verrons à la page 1126. La forme standard du problème de
notre exemple introductif est donc:
- maximiser x0 , avec x0 = 4x1 + 5x2 + 9x3 + 11x4 + 0x5 + 0x6 + 0x7
= 4x1 + 5x2 + 9x3 + 11x4
- sous contraintes:
1 x1 + 1 x2 + 1 x3 + 1 x4 + 1 x5 = 15
7 x1 + 5 x2 + 3 x3 + 2 x4 + 1 x6 = 120
3 x1 + 5 x2 + 10 x3 +15 x4 + 1 x7 = 100
x j ≥ 0 pour j variant de 1 à 7.
Les 3 contraintes constituent un système de 3 équations à 7 inconnues dont on
lève l’indétermination en rendant nulles 4 des 7 variables, ce que l’on a intérêt à
faire car il est intuitivement évident que la fonction-objectif prendra la valeur la
Table des
plus forte possible pour une solution qui comportera le moins de variables posi-
matières
tives possibles (cette intuition peut être explicitée, comme on le verra ultérieure-
ment, à partir des taux marginaux de substitution et du taux de rentabilité
marginale, associés à toute variable candidate à entrée dans la base). On peut
ajouter que l’on ne peut rendre nulles a priori plus de 4 variables, faute de risquer
thématique
de se trouver en présence d’un système d’équations dont la solution est impos-

Index
sible. Notre problème se ramène donc à celui de la sélection de l’ensemble de 3

variables non nulles a priori, que l’on qualifie de variables de base, prises dans un
3
ensemble initial de 7 variables (il y a donc C7 = 7! ⁄ ( 3!4! ) = 45 solutions-
candidates possibles que l’on appelle encore base) et dont les valeurs, d’une part
sont une solution du système d’équations (si l’on tient compte du fait que les
valeurs prises par les variables non retenues, qualifiées de variables hors-base,
sont nécessairement nulles), et, d’autre part, maximisent la valeur de x0 (notons
qu’il n’est pas rare que l’optimum recherché soit obtenu par plusieurs-bases).
L’algorithme du simplexe permet, en un nombre limité d’itérations, de trouver
une solution optimale. La démarche est simple: elle consiste à partir de l’une quel-
conque des 45 bases possibles, prise comme solution initiale, et à améliorer
progressivement cette solution au cours d’une procédure itérative. Au cours d’une
itération quelconque, on remplace l’une des variables de la dernière base retenue,
qualifiée de variable sortante, par l’une des variables hors-base, qualifiée de
variable entrante; chaque itération conduit donc à l’étude d’une nouvelle base. La
sélection de ces deux variables (ou l’arrêt de la recherche, l’optimum étant atteint)
s’effectue à l’aide de critères faciles à mettre en œuvre.
Le choix d’une solution initiale ne pose guère de difficulté pour les problèmes
de ce § I-4.1, il suffit, en effet, de rendre nulles toutes les variables qui ne sont pas
des variables d’écart, la fonction-objectif prenant alors la valeur 0. On a donc
comme variables de base: x5 = 15, x6 = 120, x7 = 100 et comme variables hors-
base: x1 = 0, x2 = 0, x3 = 0 et x4 = 0.
Une fois trouvée cette solution initiale, la recherche progressive de la solution
optimale s’effectue en travaillant sur un tableau de calculs, appelé tableau du
simplexe, lequel est progressivement transformé en totalité au cours de chaque
itération qui comporte trois étapes de calcul. Le tableau initial du simplexe ne fait
que reprendre sous une forme tabulaire les coefficients du problème standard dont
l’indice est supérieur à zéro, après permutation des premiers et seconds membres
des contraintes, et après avoir regroupé dans un même membre les termes définis-
sant la fonction-objectif1. On part donc du problème suivant:
0 = – 4 x1 – 5 x2 – 9 x3 – 11 x4 – 0 x5 – 0 x6 – 0 x7 + x0
15 = + 1 x1 + 1 x2 + 1 x3 + 1 x4 + 1 x5 + 0 x6 + 0 x7
120 = + 7 x1 + 5 x2 + 3 x3 + 2 x4 + 0 x5 + 1 x6 + 0 x7
100 = + 3 x1 + 5 x2 + 10 x3 +15 x4 + 0 x5 + 0 x6 + 1 x7
pour aboutir au tableau initial du simplexe suivant:
x1 x2 x3 x4 x5 x6 x7
Table des
matières
0 –4 –5 –9 –11 0 0 0
15 1 1 1 1 1 0 0
thématique
Index
120 7 5 3 2 0 1 0
100 3 5 10 15 0 0 1
Le repérage des variables de base s’effectue au cours d’une itération quel-

conque en cerclant le nombre 1 de la colonne de ces variables de base repérées en
tête de colonne (les autres éléments de ces colonnes étant toujours nuls). La valeur
prise par des variables de base se lit directement en tête de ligne, ce qui reste vrai
pour n’importe quelle itération. Rappelons, par ailleurs, que la valeur prise par une
variable hors-base est nécessairement nulle.
La valeur prise par l’élément de la première colonne de la première ligne du
tableau (ici 0) correspond à la valeur prise par la fonction-objectif pour la base
retenue (ici x4 = 15, x6 = 120 et x7 = 100). Cette interprétation reste valable
quelle que soit l’itération. Les valeurs suivantes de cette ligne s’analysent comme
la variation de la valeur prise par x0 (c’est-à-dire, ici, la diminution puisque ces
valeurs sont négatives), du fait de la non-introduction de la variable correspon-
dante (repérée en tête de colonne) au détriment, bien sûr, des variables précédem-
1. D’autres conventions sont également utilisées. Par rapport à celle retenue ici, elles placent en dernière ligne les
données de la première ligne et/ou en dernière colonne celles de la première colonne. L’adaptation de la méthode
présentée ici à ces conventions ne présente aucune difficulté.
ment retenues dans la base. En toute rigueur, ce raisonnement doit être tenu pour
des variations infiniment petites dx j , c’est-à-dire que le produit de cette valeur
pour la variable j par une variation infinitésimale dx j correspond à la variation
infinitésimale dx0 consécutive à la non-introduction de dx j . Ceci confère à ces
valeurs la signification de dérivées partielles de la fonction-objectif par rapport
aux variables, en un point défini par les valeurs des variables actuellement rete-
nues. Il faut souligner que ces interprétations restent valables au début de
n’importe quelle itération. Dès lors, le critère de sélection de la variable entrante,
utilisé à la première étape de calcul d’une itération de la méthode du simplexe,
s’interprète parfaitement : il consiste à « sélectionner la variable hors base à
laquelle est associée la plus faible valeur dans la première ligne du tableau, à
condition que celle-ci soit négative» (la variable entrante de la première itération
sera donc ici x4 ). Si au début d’une itération quelconque on ne trouve plus de
valeur négative, c’est qu’il n’existe plus de possibilité d’accroître la valeur prise
par la fonction-objectif et que l’optimum est atteint. Il y a alors lieu d’arrêter la
recherche.
Une fois sélectionnée la variable entrante, il faut déterminer la variable sortante.
Au cours d’une itération quelconque, les coefficients de la colonne d’une variable
hors base, à l’exception de celui de la première ligne, s’interprètent économique-
ment comme le taux marginal de substitution de la variable hors base et des
variables de la base (repérées, rappelons-le, par des 1 cerclés en jaune). Ici une
unité de la variable entrante x4 se substitue simultanément à 1 unité de la variable
Table des
x5 , à 2 unités, de la variable x6 et à 15 unités de la variable x7 . Il s’ensuit que si

matières
x4 se substituait en totalité à x6 , il prendrait comme valeur le quotient de 120

(valeur actuelle de x6 ) par 2 (taux marginal de substitution de x4 à x6 ), c’est-à-
dire 60. De même si x4 se substituait en totalité à x7 , il prendrait comme valeur le
quotient de 100 (valeur actuelle de x7 ) par 15 (taux marginal de substitution de x4
thématique
à x7 ), c’est-à-dire 100/15 = 20/3 ≈ 6,66. Enfin, si x4 se substituait en totalité à x5 ,

Index
il prendrait comme valeur 15/1 = 15. Il est bien évident que si la variable entrante
x4 doit prendre la place de l’une des variables de base, c’est l’une de ces trois
valeurs trouvées (15; 60; 20/3) qu’elle doit prendre. La valeur que l’on retiendra
ne peut être que la plus faible, c’est-à-dire ici 20/3, puisque l’introduction de x4
s’effectue au détriment de toutes les variables de base. Le critère de sélection de
la variable sortante utilisé au cours de la deuxième étape de calculs d’une itération
de la méthode du simplexe consiste à «choisir la variable de base dont le quotient
de la valeur par le taux marginal de substitution est le plus faible possible».
La troisième et dernière étape de calcul d’une itération a pour but de calculer le
tableau du simplexe qui découle du choix de la nouvelle base, c’est-à-dire les
nouvelles valeurs prises par les variables de base, les nouveaux taux marginaux de
substitution et les nouvelles dérivées partielles de la fonction-objectif par rapport
aux variables. Cette dernière étape, qualifiée de changement de base, s’effectue
en deux temps. On divise tout d’abord la ligne de la variable sortante par le taux
marginal de substitution de la variable entrante à la variable sortante, connu encore
sous le nom de pivot (ici le pivot est 15), pour obtenir la ligne de la variable
entrante (qui remplace la variable sortante) et que l’on appelle encore nouvelle
ligne du pivot. Dans un second temps, on retranche aux autres lignes du tableau,
la valeur prise par la variable entrante dans la ligne, multipliée par la nouvelle
ligne du pivot; par exemple, on retranchera à la ligne 1 la nouvelle ligne du pivot

préalablement multipliée par – 11.
Ces différentes étapes de calcul de la première itération sont reprises dans le
tableau 344, page 1123. Pour mieux suivre la transformation progressive du
tableau du simplexe, des conventions de couleurs ont été utilisées. Le tableau
obtenu à la fin de la première itération devient le tableau initial sur lequel on
travaille au début de la deuxième itération (et ainsi de suite…). Les calculs de la
deuxième, troisième et quatrième itérations sont fournis aux pages suivantes. On
constate que le choix de la variable x4 , effectué au début de la première itération,
a été remis en cause au début de la troisième itération. Ce genre de remise en cause
est assez fréquent dans l’utilisation de la méthode du simplexe et découle du fait
que l’on recherche «par tâtonnements» une combinaison de variables qui optimise
la fonction-objectif tout en respectant les contraintes du problème.
Ajoutons enfin que certains des calculs effectués ici (pour simplifier l’exposé de
la méthode) ne sont pas nécessaires: en effet, les colonnes des variables de base
autres que la variable sortante ne subissent aucune transformation. Cette observa-
tion est à prendre en compte au niveau d’une résolution manuelle par la méthode
du simplexe (ce qui conduit certains à supprimer purement et simplement les
colonnes des variables de base, lesquelles sont mentionnées en marge de la
première colonne).
I-4.2 Extensions de l’algorithme du simplexe
Table des
matières
Dans le § I-4.1 nous avons décrit l’utilisation de la méthode du simplexe pour
résoudre des programmes linéaires dans lesquels la fonction-objectif est à maxi-
miser et où les contraintes sont toutes du type ≤. Levons maintenant ces deux
restrictions.
thématique
L’adaptation de la méthode à un problème de minimisation sous contrainte ne
Index
soulève guère de difficulté. On sait, en effet, transcrire un problème de minimisa-
tion en un problème de maximisation: minimiser ∑ c j x j est équivalent à maxi-
j
miser ∑ ( –c j )x j . Il suffit donc de changer le signe de tous les coefficients de la
j
fonction-objectif à minimiser pour se ramener à un problème de maximisation, et
donc être en mesure d’utiliser l’algorithme du simplexe tel qu’il est décrit au § I-
4.1. On peut ajouter que les variables du problème étant nécessairement positives
ou nulles, la solution d’un problème de minimisation dans lequel les coefficients
de la fonction-objectif (avant changement de signes) seraient tous positifs ne peut
qu’être obtenue avec des valeurs nulles pour les variables intervenant dans la
forme canonique du problème.
TABLEAU 344
Exemple d’utilisation de la méthode du simplexe
.
ITÉRATION 1
Étape 1: sélection de la variable entrante
Min (–4, –5, –9, –11) = –11 choix de x4
. Étape 1: sélection de la –ariable sortante
0 1 2 3 4 5 6 7
15 / 1 = 15
x0 = 0 –4 –5 –9 –11 0 0 0
120 / 2 = 60 x5 = 15 1 1 1 1 1 0 0
100 / 15 minimum x
= 6,66 120 7 5 3 2 0 1 0
6=
x4 = 6,66 et x7 =0 (x7 variable sortante) x7 = 100 3 5 10 15 0 0 1
pivot = 15
.. Étape 3 : changement de base

Diviser la ligne du pivot par le pivot
0 1 2 3 4 5 6 7
x0 = 0 –4 –5 –9 –11 0 0 0
x5 = 15 1 1 1 1 1 0 0
Table des
matières
x6 = 120 7 5 3 2 0 1 0
x4 = 100 20 3 1 5 1 10 2 15 0 0 1 1 nouvelle
------- =------ --- = --- --- = --- ------ = --- ------ = 1 --- = 0 --- = 0 --- =------ ligne du
15 3 15 5 15 3 15 3 15 15 15 15 15 pivot
• Retrancher aux autres lignes du tableau la valeur prise par la variable entrante dans la
thématique
ligne, multipliée par la nouvelle ligne du pivot (ligne 4)

Index
- ligne 1: multiplier la ligne 4 par –11 et la retrancher à la ligne 1

- ligne 2: multiplier la ligne 4 par 1 et la retrancher à la ligne 2
- ligne 3: multiplier la ligne 4 par 2 et la retrancher à la ligne 3
0 1 2 3 4 5 6 7
------ ( –11 ) – 4 – --- ( –11) – 5 – --- ( –11) – 9 – --- ( –11) – 11 – 1 ( –11) 0 – 0 ( –11) 0 – 0 ( –11)
x0 = 0 – 20 1 1 2 1
0 – ------ ( –11 )
3 5 3 3 =0 =0 =0 15
= 220 ⁄ 3 = –9 ⁄ 5 = –4 ⁄ 3 = –5 ⁄ 3 = 11 ⁄ 15
x5 = 15 – 20 1
1 – --- ⋅ 1 1 2 1–1⋅1 1–0⋅1 0–0⋅1 1
------ ⋅ 1 1 – --- ⋅ 1 1 – --- ⋅ 1 0 – ------ ⋅ 1
3 5 3 3= 1 ⁄ 3 =1 15
= 25 ⁄ 3 = 4⁄5 = 2⁄3 =0 =0 = 1 ⁄ 25
x6 = 120 – 20 1 1 2 2–1⋅2 0–0⋅2 1–0⋅2 1
------ ⋅ 2 7 – --- ⋅ 2 5 – --- ⋅ 2 3 – --- ⋅ 2 0 – ------ ⋅ 2
3 5 3 3 = =1 15
= 320 ⁄ 3 = 33 ⁄ 5 = 13 ⁄ 3 = 5⁄3 0 =0 = –2 ⁄ 15
x4 = 1⁄3 ⁄ 1 ⁄ 15
20 ⁄ 3 1⁄5 2 3 1 0 0
D’où le tableau du simplexe à la fin de l’itération 1

0 1 2 3 4 5 6 7
220/3 –9/5 –4/3 –5/3 0 0 0 11/15
x5 = 25/3 4/5 2/3 1/3 0 1 0 –1/15

x6 = 320/3 33/5 13/3 5/3 0 0 1 –2/15
x4 = 20/3 1/5 1/3 2/3 1 0 0 1/15
ITÉRATION 2
. Étape 1: sélection de la variable entrante
Min – 9---, – 4---, – 5---, 11
- = – 9---
 5 5 3 ----- choix de x1
. 15 5
Étape 2: sélection de la variable sortante
x0 = 220/3
0
–9/5
1
–4/3
2
–5/3
3 4
0
5
0
6
0 11/15
7
25/3 / 4/5 = 125/12 minimum x5 = 25/3 4/5 2/3 1/3 0 1 0 –1/15
320/3 / 33/5 = 1600/99 x6 = 320/3 33/5 13/3 5/3 0 0 1 –2/15
20/3 / 1/5 = 100/3 x4 = 20/3 1/5 1/3 2/3 1 0 0 1/15
x1 = 125 ⁄ 12 et x5 = 0 (x5 variable sortante)
. pivot = 4/5
Étape 3: changement de base
.
0 1 2 3 4 5 6 7
x0 = 220/3 -9/5 -4/3 -5/3 0 0 0 11/5
x1 = 25 4 125 4 4 2 4 5 1 4 5 4 4 5 4 1 4 1 nouvelle
------ ⁄ --- = --------- --- ⁄ --- = 1 --- ⁄ --- = --- --- ⁄ --- = ------ 0 ⁄ --- = 0 1 ⁄ --- = --- 0 ⁄ --- = 0 –------ ⁄ --- =–------ ligne du
3 5 12 5 5 3 5 6 3 5 12 5 5 4 5 15 5 12 pivot
x6 = 320/3 33/5 13/3 5/3 0 0 1 -2/15
x4 = 20/3 1/5 1/3 2/3 1 0 0 1/15
- ligne 1: multiplier la ligne 2 par –9/5 et la retrancher à la ligne 1
- ligne 3: multiplier la ligne 2 par 33/5 et la retrancher à la ligne 3
0 1 2 3 4 5 6 7
220 125 –9 9 –9 4 5 –9 5 5 –9 0 + –0 ⋅ –-----9- 5 –9 –9 11 –1 –9
- – --------- ⋅------
x 0 = -------- – --- + –1 ⋅ ------ – --- + – --- ⋅------ --- – ------ ⋅------ 0 + – --- ⋅ ------ 0 + –0 ⋅ ------ ------ + – ------ ⋅ ------
3 12 5 5 5 3 6 5 3 12 5 5 4 5 5 15 12 5
= 1105 ⁄ 12 =0 = 1⁄6 = –11 ⁄ 12 =0 = 9⁄4 =0 = 7 ⁄ 12
x1 = 125 ⁄ 12 1 5⁄6 5 ⁄ 12 0 5⁄4 0 –1 ⁄ 12
320 125 33 33 33 13 5 33 5 5 33 33 5 33 33 –1 33
x6 = --------- – --------- ⋅ ------ ------ – 1 ⋅ ------ ------ – --- ⋅ ------ --- – ------ ⋅ ------ 0 – 0 ⋅ ------ 0 – --- ⋅ ------ 1 – 0 ⋅ ------ –-----2- – -----
- ⋅ ------
3 12 5 5 5 3 6 5 3 12 5 5 4 5 5 15 12 5
= 455 ⁄ 12 =0 = –7 ⁄ 6 = –13 ⁄ 12 =0 = –33 ⁄ 4 =1 = 5 ⁄ 12
20 125 1 1 1 1 5 1 5 1 1 5 1 1 1 –1 1
x4 = ------ – --------- ⋅ --- --- – 1 ⋅ --- --- – --- ⋅ --- 1 – ------ ⋅ --- 1 – 0 ⋅ --- 0 – --- ⋅ --- 0 – 0 ⋅ --- ------– ------ ⋅ ---
3 12 5 5 5 3 6 5 12 5 5 4 5 5 15 12 5
= 55 ⁄ 12 =0 = 1⁄6 = 7 ⁄ 12 =1 = –1 ⁄ 4 =0 = 1 ⁄ 12
0 1 2 3 4 5 6 7
x0 = 1105/12 0 1/6 –11/12 0 9/4 0 7/12
x1 = 125/12 1 5/6 5/12 0 5/4 0 –1/12
x6 = 455/12 0 -7/6 –13/12 0 –33/4 1 5/12
x4 = 55/12 0 1/6 7/12 1 –1/4 0 1/12
ITÉRATION 3
. Étape 1: sélection de la variable entrante
Min  ---, – ------, --- ,------ = – ------
1 11 9 7 11 choix de x3
. 6 12 4 12 12
Étape 2: sélection de la variable sortante
0
x0 = 1105/12
1
0
2
1/6 -11/12
3 4
0 9/4
5 6
0 7/12
7
125/12 / 5/12 = 25 x1 = 125/12 1 5/6 5/12 0 5/4 0 –1/12
455/12 / –13/12 <0 x6 = 455/12 0 –7/6 -13/12 0 –33/4 1 5/12
55/12 / 7/12 = 55/7 minimum x4 = 55/12 0 1/6 7/12 1 –1/4 0 1/12

(positif)
x3 = 55 ⁄ 7 et x4 = 0 ( x4 variable sortante)
pivot = 7/12
.. Étape 3 : changement de base
0 1 2 3 4 5 6 7
x0 = 1105/12 0 1/6 –11/12 0 9/4 0 7/12
x1 = 125/12 1 5/6 5/12 0 5/4 0 –1/12
x6 = 455/12 0 -7/6 –13/12 0 -33/4 1 5/12
55 7 55 1 7 7 7 7 12 7 7 1 7 nouvelle
x3 = ------ ⁄ ------ = ------ 0 ⁄ -----
7 2 1 –3 1
- = 0 --- ⁄ ------ = --- ------ ⁄ ------ = 1 1 ⁄ ------ = ------ – --- ⁄ ------ = ------ 0 ⁄ ------ = 0 –------ ⁄ ------ = --- ligne du
12 12 7 12 6 12 7 12 12 12 7 4 12 7 12 12 12 7 pivot
0 1 2 3 4 5 6 7
1105 55 –11 –11 1 2 –11 -------- –11 –11 12 –11 9 –3 –11 –11 7 1 –11
-– ------ ⋅ --------- 0 + –0 ⋅ --------
x0 = ----------- 12 --- – --- ⋅ --------- - –1 ⋅ --------- 0 + – ------ ⋅ --------- --- – ------ ⋅ --------- 0 + –0 ⋅ ---------
- ------ + –--- ⋅ ---------
12 7 12 6 7 12 12 12 7 12 4 7 12 12 12 7 12
= 695 ⁄ 7 =0 = 3⁄7 =0 = 11 ⁄ 7 = –13 ⁄ 7 =0 = 5⁄7
125 55 5 5 5 2 5 ----- 5 5 12 5 5 –3 5 5 1 1 5
x1 = -------- - – ------ ⋅ ------ 1 – 0 ⋅ ------ --- – --- ⋅ ------ - – 1 ⋅ ------ 0 – ------ ⋅ ------ --- – ------ ⋅ ------ 0 – 0 ⋅ ------ – ------ – --- ⋅ ------
12 7 12 12 6 7 12 12 12 7 12 4 7 12 12 12 7 12
= 50 ⁄ 7 =1 = 5⁄7 =0 = –5 ⁄ 12 = 10 ⁄ 7 =0 = –1 ⁄ 7
455 55 –13 – 13 7 2 –13 13 12 – 13 33 –3 –13 5 1 –13
x6 = --------
– 13 – 13
-– ------ ⋅ --------- 0 – 0 ⋅ --------- – --- – --- ⋅ --------- –------– 1 ⋅ --------- 0 – ------ ⋅ --------- –------ – ------ ⋅ --------- 1 – 0 ⋅ --------
- ------ – --- ⋅ ---------
12 7 12 12 6 7 12 12 12 7 12 4 7 12 12 12 7 12
= 325 ⁄ 7 =0 = –6 ⁄ 7 =0 = –13 ⁄ 7 = –61 ⁄ 7 =1 = 4⁄7
x3 = 55/7 0 2/7 1 12/7 -3/7 0 1/7
0 1 2 3 4 5 6 7
x0 = 695/7 0 3/7 0 11/7 13/7 0 5/7
x1 = 50/7 1 5/7 0 –5/12 10/7 0 –1/7
x6 = 325/7 0 –6/7 0 13/7 –61/7 1 4/7
x3 = 55/7 0 2/7 1 12/7 –3/7 0 1/7
Lorsque certaines contraintes du problème canonique sont des égalités, il n’y a

pas lieu de créer de variables d’écart. Mais le problème qui se pose alors est celui
de la détermination d’une solution initiale pour pouvoir utiliser la méthode du
simplexe. Dans cette perspective, on crée une variable artificielle yh qui est
affectée du coefficient 1 et ajoutée à l’égalité considérée (tout comme les variables
d’écart). La solution optimale devra nécessairement comporter des valeurs nulles
pour toutes les variables artificielles. Nous verrons ci-après comment garantir le
respect de cette condition par l’une des méthodes classiquement utilisées, la
méthode des pénalités (désignée sous le nom de big M Method dans la littérature
anglo-saxonne spécialisée).
Lorsqu’une contrainte du problème canonique comporte une inégalité du type
«≥», on la transforme tout d’abord en créant une variable d’écart1. Changeons, par
exemple, le sens de l’inégalité de la seconde contrainte de notre exemple
introductif:
7 x1 + 5 x2 + 3 x3 + 2 x4 ≥ 120
avec l’introduction de la variable d’écart, cette contrainte devient, sous sa forme
standard:
7 x1 + 5 x2 + 3 x3 + 2 x4 = 120 + x6
ce que l’on peut encore écrire, en regroupant dans le premier membre toutes les
variables:
7 x1 + 5 x2 + 3 x3 + 2 x4 – x6 = 120
Table des
matières
Reste posé le problème de la détermination d’une solution initiale car x6
s’analysant comme un « surplus » et non comme un « reliquat », on ne peut lui
donner de valeur positive que lorsque certaines variables canoniques sont déjà
positives, ce qui n’est habituellement pas le cas lorsque l’on amorce un calcul de
thématique
simplexe. Pour amorcer le calcul itératif, il faudra donc, là encore, créer une
Index
variable artificielle.
Illustrons par un exemple numérique simple l’utilisation des variables artifi-
cielles et leur élimination dans le but d’obtenir une solution initiale. L’élimination
préalable de ces variables est assurée par l’introduction de ces variables artifi-
cielles dans la fonction-objectif avec une très forte pénalité qui aura pour effet de
commencer par «chasser» ces variables artificielles dans l’utilisation de l’algo-
rithme du simplexe (rappelons que les variables d’écart n’interviennent pas dans
la fonction-objectif, ou plus exactement interviennent avec des coefficients nuls).
L’exemple numérique retenu est le suivant, sous sa forme canonique:
- maximiser x0 , avec x0 = 2 x1 + 5 x2 + 4 x3
- sous contraintes:
x1 + 2 x2 + x3 = 10
4 x1 + x2 + x3 ≥ 15;
Ce problème devient, sous sa forme standard, en associant une forte pénalité M
aux variables artificielles dans la fonction-objectif (cette pénalité pourrait être, par
exemple, de – 1000 dans l’exemple numérique retenu, compte tenu des valeurs
1. À moins que le coefficient de l’une des variables canoniques de cette contrainte ne soit égal à 1, auquel cas cette
variable est retenue dans la solution initiale (et, bien sûr, elle ne peut l’être qu’au titre d’une seule contrainte).
numériques du problème; on préférera cependant travailler ici, sous la forme litté-

rale, pour bien montrer comment cette pénalité «disparaît» lorsqu’une solution
initiale aura été trouvée).
0 = – 2 x1 – 5 x2 – 4 x3 – 0 x4 – M y1 – M y2
10 = 1 x1 + 2 x2 + 1 x3 + 0 x4 + 1 y1 + 0 y2
15 = 4 x1 + 1 x2 + 1 x3 – x4 + 0 y1 + 1 y2
On ne peut amorcer les calculs du simplexe, en gardant cette formulation du
problème puisque, compte tenu de l’interprétation des coefficients de la première
ligne du tableau du simplexe (dérivées partielles de la fonction-objectif par rapport
aux variables), il est nécessaire que les coefficients des variables de base soient
nuls. Pour qu’il en soit ainsi, on modifie la première équation en utilisant la
propriété classique qui veut que l’on ne modifie pas une égalité en ajoutant ou en
retranchant la même quantité aux deux membres de l’équation. Pour faire
disparaître y1 de la première équation, il suffit d’y ajouter membre à membre la
seconde équation préalablement multipliée par M. Pour faire ensuite disparaître
y2 , il suffit d’ajouter membre à membre au résultat obtenu la troisième équation
préalablement multipliée par M. La première équation devient donc:
( 10 + 15)M = { ( 1 + 4 )M – 2 }x1 + { ( 2 + 1 )M – 5 }x2 + { ( 1 + 1 )M – 4 }x3
+ { ( 0 – 1 )M – 0 }x4 + { ( 1 + 0 )M – M }y1 + { ( 0 + 1 )M – M }y2
25M = ( 5M – 2 )x1 + ( 3M – 5 )x2 + ( 2M – 4 )x3 – Mx4 + 0y1 + 0y2
Table des
matières
Le tableau initial du simplexe devient le tableau 345.

TABLEAU 345
Tableau initial du simplexe – exemple d’utilisation
de contraintes du type « ≥ » ou «=»
thématique
Index
x1 x2 x3 x4 x5 y1 y2
25M 5M–2 3M–5 2M–4 –M 0 0
y1 10 1 2 1 0 1 0
y2 4 1 1 1 –1 0 1
Étant donné que la pénalité M est très grande et négative (la fonction-objectif
étant à maximiser; elle aurait été positive si la fonction-objectif avait été à mini-
miser), la variable entrante de la première itération est x1 . La variable sortante est
alors y2 et le pivot est 4. Les tableaux du simplexe des deux premières itérations
sont donnés dans le tableau 346 de la page 1128.
L’élimination des variables artificielles conduit donc à la solution réalisable x1
= 20/7 et x2 = 25/7, les autres variables étant nulles. Cette solution n’est pas opti-
male puisque x3 a une dérivée partielle négative (– 11/7). Il faut donc poursuivre
les itérations du simplexe. La pénalité M étant très grande, il est inutile de pour-
suivre les calculs dans les colonnes correspondant aux variables artificielles. On
partira donc du tableau 347 de la page 1128 (dans lequel il apparaît qu’il faut pour-
suivre les itérations en introduisant x3 ):
TABLEAU 346
Tableau du simplexe à la fin des deux premières itérations
x1 x2 x3 x4 y1 y2
25 M 3M – 5 2M – 4 –M 0
PREMIÈRE ITÉRATION
1
–( 5 M – 2 )– ---
15 1 1 1 –( 5 M – 2 ) ---
–( 5 M – 2 ) ------ –( 5 M – 2 ) --- –( 5 M – 2 ) --- 4
4 0 4 4 4 0
5 M 15 7 M 18 3M 7 M 1 5M 1
= -------- + ------ = -------- – ------ = -------- – --- = ---- – --- = – -------- + ---
4 2 4 4 4 2 4 2 4 2
0 – 1 ⋅  – ---
15 1 1 1 1
10 – 1 ⋅ ------ 2 – 1 ⋅ --- 1 – 1 ⋅ --- 0 – 1 ⋅ ---
4 4 4 4 4
y1 0 1
25 7 3 1 1
= ------ = --- = --- = --- = – ---
4 4 4 4 4
x1 15 1 1 1 1
------ 1 --- --- – --- 0 ---
4 4 4 4 4
5 M 15 3M 7 M 1 5M 1
-------- + ------ -------- – --- ---- – --- 0 – -------- – ---
4 2 4 2 4 2 4 2
DEUXIÈME ITÉRATION
7 M 18 4
–-------- – ------ --- –-------- – ------ ---  4 4  7
7 M 18 25 7 M 18 3 7 M 18 1 – -------- – ------ ---
– -------- – ------  – ---
7M 18 1
–-------- – ------ ------ 0 0
4 4 7 4 4 7 4 4 7 4 4 7
18
165 11 1 = – M + ------ 1
= --------- = – ------ = --- 7 = – M – ---
7 7 7 7
x2 25 3 1 4 1
------ 0 1 --- --- --- – ---
7 7 7 7 7
Table des
matières
15 1 25
------ – --- ⋅ ------
1 1 1
– --- – --- ⋅ --- 1 1  1
--- – --- ⋅  – ---
4 4 7 1 1 3 1 4 4 7 1 4 1 4 4 7
x1 1 0 --- – --- ⋅ --- = --- 0 – --- ⋅ --- = – ---
20 4 4 7 7 2 4 7 7 2
= ------ = – --- = ---
7 7 7
thématique
TABLEAU 347
Index
Tableau du simplexe au début de la troisième itération
x1 x2 x3 x4
165/7 0 0 –11/7 1/7
x2 25/7 0 1 3/7 1/7
x1 20/7 1 0 1/7 -2/7
I-4.3 Cas particuliers

Nous ne discuterons pas ici le cas de problèmes numériques n’ayant pas de
solution, pour diverses raisons. On se contentera de signaler l’existence d’algo-
rithmes x j plus performants que celui du simplexe lorsque le problème posé revêt
une structure particulière. Deux cas de figure sont particulièrement intéressants.
Lorsque les variables sont toutes comprises entre 0 et 1, une adaptation de
l’algorithme du simplexe1 permet d’éviter d’expliciter les contraintes x j ≤ 1, ce
qui diminue d’autant le nombre de lignes du tableau du simplexe, et donc les
calculs à effectuer à chaque itération, ainsi que le nombre de ces itérations. De très
1. Voir, par exemple, Wagner (1975, [435]), p. 150-153, où l’algorithme modifié est présenté et illustré d’un
exemple numérique.
nombreux problèmes se caractérisent par l’existence de bornes supérieures

imposées aux variables (à l’exclusion de bornes inférieures non nulles). Il est dans
ce cas toujours possible de transformer le problème initial en un problème où
toutes les variables sont comprises entre 0 et 1, et donc d’utiliser l’algorithme
modifié du simplexe.
Le second cas de figure, que l’on rencontre dans certains problèmes de trans-
port, se caractérise par des variables (flux de transport, par exemple) se différen-
ciant par leur rattachement à l’une des modalités i d’un caractère qualitatif
(localisation d’origine, par exemple) et leur attachement à l’une des modalités j
d’un autre caractère qualitatif (localisation d’arrivée, par exemple). Un exemple
de cette nature est traité à la page 553. Les variables utilisées (flux transportés de
i vers j, par exemple) comportent alors 2 indices (xij). La fonction-objectif est
alors du type: maximiser x0 , ou minimiser x0 , avec x0 = x0 = ∑ ∑ cij xij . Si, en
i j
outre, les contraintes sont du type1 : ∑ xij = bi , ∑ xij = b j et ∑ b j = ∑ bi . L’algo-
j i j i
rithme du simplexe est alors adapté pour tenir compte de cette structure
particulière, avec des performances très supérieures2.
I-4.4 Exemple de résolution par Excel
Examinons maintenant comment traiter notre exemple en utilisant la fonction
«Solveur» du menu «Outils» du tableur Excel. Il convient d’abord de saisir dans
Table des
matières
une feuille de calcul les paramètres (aij, bi, cj) du problème, d’y ajouter des valeurs
initiales (par exemple 0) pour les variables xj du problème, de calculer dans des
cellules les valeurs prises par les premiers membres des contraintes, pour les
valeurs assignées aux xj, ainsi que la valeur x0 prise par la fonction-objectif. Le
thématique
premier écran de la figure 267, page 1130 montre la saisie effectuée pour les para-
Index
mètres (les couleurs ont été ajoutées pour vous permettre de mieux repérer la
structure du problème soumis) et le second écran est une variante du premier qui
affiche les formules des cellules calculées pour vous permettre de mieux
comprendre la façon de poser le problème.
Le lancement du solveur provoque l’affichage de la fenêtre de définition du
problème à résoudre de la figure 268. On y définit la cellule correspondant à la
fonction objectif (ici x0 mis dans la cellule B1), les cellules correspondant aux
variables xj (ici les cellules B3 à E3) et les contraintes, en commençant par celles
qui imposent aux xj d’être non négatifs (contenu de la cellule F4 devant être infé-
rieur ou égal au contenu de la cellule G4, pour la première contrainte, etc.).
Une fois le problème spécifié, il faut déclencher la résolution en appuyant sur
le boutant correspondant (cf. figure 268), ce qui provoque l’affichage de la fenêtre
de la figure 269, dans laquelle il faut sélectionner le résultat et les rapports des
résultats de l’optimisation. Ceux-ci sont reproduits dans les écrans des figures 270
à 274. On retrouve les résultats du tableau 343 de la page 1110. Pour aider à faire
1. Ces contraintes s’interprètent, dans l’exemple de certains problèmes de transport, comme l’exigence que les flux
partant de i aient une destination j, que ceux arrivant en j aient une origine i et que la somme des flux de départ
soit égale à celle des flux d’arrivée.
2. Voir, par exemple, Wagner (1975, [435]), p. 186-195.
FIGURE 267
Initialisation de la procédure
Table des
matières
FIGURE 268
Définition du problème (paramètres du solveur)
thématique
Index
le rapprochement, les valeurs fractionnaires des résultats sont ajoutées à ces copies
d’écran. Le résultat de l’optimisation donne les valeurs optimales des xj et la
comparaison entre les premiers et seconds membres des contraintes montre que
seule la seconde contrainte n’est pas saturée.
FIGURE 269
Sélection des affichages de résultats
FIGURE 270
Résultat de l’optimisation
x1* = 50 ⁄ 7 x2* x3* = 55 ⁄ 7 x4*

695/7
Table des
matières
thématique
Index
4 4 4
∑ a1 j x j ∑ a2 j x j ∑ a3 j x j
J=1 J=1 J=1
Le premier rapport (figure 271, page 1132) ne fournit comme information addi-
tionnelle que les valeurs prises par les variables d’écart des contraintes non
saturées (ce qui présente un intérêt limité).
Le deuxième rapport (figure 272, page 1133) est plus intéressant car il fournit
les valeurs optimales des variables duales. La terminologie employée est un peu
différente de celle habituellement utilisée et retenue dans ce chapitre.
Le troisième rapport (figure 273, page 1133) n’amène pas d’information
nouvelle puisqu’il se contente d’indiquer que l’on ne peut pas augmenter la valeur
optimale d’une variable de la base sans dégrader l’optimum. La seconde informa-
tion fournie est quelque peu trompeuse: elle fournit la valeur de x0 lorsque l’une
des variables de la base est rendue nulle mais, implicitement sans modifier les
valeurs prises par les autres variables. Prenons l’exemple de x1 ; si l’on rend nulle
sa valeur, la poursuite des calculs dans le tableau du simplexe montre que les
ressources que ce choix dégage permettent non seulement d’introduire x2 (=10)
mais encore conduit à diminuer la valeur prise par x3 (qui tombe alors à 5) pour
FIGURE 271
Premier rapport sur la solution optimale trouvée
695/7
x1* = 50 ⁄ 7
x2*
x3* = 55 ⁄ 7
x4*
4
4 4 Non saturée
∑ a1 j x j ∑ a2 j x j ∑ a3 j x j
J=1
J=1 J=1
x6* = 325 ⁄ 7
Saturée
Saturée
Table des
matières
thématique
Index
éviter de trop dégrader l’optimum, qui tombe à 95 et non 70,72 comme pourrait le
laisser comprendre ce rapport.
SECTION II GÉNÉRALISATION
II-1 Un nouveau contexte pour la programmation linéaire
Ce sont des problèmes de production qui sont à l’origine de la programmation
linéaire, il y a une cinquantaine d’années1 mais, jusqu’à une époque récente, sa
mise en œuvre pour résoudre des problèmes d’une certaine complexité ne pouvait
être que le fait de grandes entreprises en raison de la puissance de calcul requise
et des techniques utilisées pour définir le problème à résoudre par le programme
informatique. Ce contexte a bien changé.
Il n’est pas besoin d’insister sur le fait que l’évolution de la micro-informatique
se caractérise par une croissance importante et continue des puissances de traite-
ment et des capacités de stockage, par une baisse constante des coûts des matériels
et logiciels et par une réelle amélioration des facilités d’utilisation de ces moyens
informatiques, les mettant à portée de tous. Toutes les entreprises disposent main-
1. Voir Jacquet-Lagrèze (1997, [241]), p. 14.

FIGURE 272
Deuxième rapport sur la solution optimale trouvée
x1* = 50 ⁄ 7
y1* – y2* = 3 ⁄ 7
x2*
y3*
x4*
4
∑ a3 j x j – y4* = 11 ⁄ 7
Prix-fantômes
J=1
x3* = 55 ⁄ 7
y5* = 13 ⁄ 7
y6* = 0
y7* = 5 ⁄ 7
FIGURE 273
Table des
matières
Troisième rapport sur la solution optimale trouvée

thématique
Index
x3* = 55 ⁄ 7
x1* = 50 ⁄ 7
x4*
x2*
55 55
4 × 0 + 5 × 0 + 9 × ------ + 11 × 0 4 × ------ + 5 × 0 + 9 × 0 + 11 × 0
7 7
tenant, à un coût abordable, d’une puissance de traitements informatiques sans

commune mesure avec celle dont disposaient les plus grosses entreprises il y a une
vingtaine d’années.
La formalisation d’un problème d’optimisation d’une certaine envergure
implique l’usage de matrices de données ne comportant qu’un pourcentage faible
de valeurs non nulles. Les premiers programmes ont été mis au point à l’époque
des cartes perforées pour résoudre des problèmes de structure stable. La descrip-
tion de ces problèmes s’effectue alors par un jeu de données décrivant simultané-
ment la structure du programme linéaire (variables, contraintes et fonction-
objectif) et les valeurs de paramètres retenues par un ensemble de triplets du type
«numéro de ligne – numéro de colonne – valeur du coefficient». Cette approche
présente deux inconvénients. Tout d’abord, les risques d’erreur dans le repérage
des données dans la matrice sont grands, en particulier lorsque les variables du
problème comportent plusieurs indices. Ensuite, et surtout, une transformation du
problème aussi marginale que la modification de la borne d’un indice peut
conduire à une réécriture complète des données du programme. Cette approche est
donc fortement consommatrice de temps, ce qui en limite l’intérêt.
Une nouvelle approche, apparue à la fin des années quatre-vingt1, résout ces
problèmes de manière très efficace en s’appuyant sur une séparation claire et nette
entre le modèle et les données utilisées, ce qui permet une mise au point très rapide
et une généralisation immédiate de la formulation obtenue à une classe de
problèmes. Cette nouvelle génération d’outils, connue sous le nom de modeleurs,
est en fait un programme de définition automatique des triplets s’appuyant sur une
analyse du modèle et des données et qu’un solveur (c’est-à-dire un programme de
résolution du problème d’optimisation posé) choisi pour résoudre le problème
utilisera. Les modeleurs s’appuient des langages non procéduraux (ou déclaratifs),
proches de la notation mathématique conventionnelle, permettant une description
concise du problème.
Table des
matières
- Le modèle consiste en une définition littérale préalable des indices, des varia-
bles et des paramètres puis par une description des contraintes et de la fonc-
tion-objectif, sous une forme traduisant, avec la même concision, ces
relations algébriques. Cette description utilise non seulement des variables
indicées, des coefficients, des opérateurs «+», «–», « x », «/» mais aussi les
thématique
opérateurs Σ et Π et les relations peuvent même être soumises à certaines
Index
conditions logiques. La compréhension de ce que fait le modèle est immé-
diate, contrairement aux approches antérieures qui obligeaient à un
décryptage fastidieux; il s’ensuit que sa maintenabilité, sa communicabilité
et sa portabilité sont fortes.
- La description des données commence par la liste des occurrences de chaque
indice, puis pour chaque coefficient (indicé), par la liste des valeurs numéri-
ques.
Dans ces conditions, la maintenance du programme linéaire est aisée.
- L’adjonction (ou la suppression) d’une contrainte se traduit par l’adjonction
(ou la suppression) d’une ligne du modèle et l’adjonction (ou la suppression)
1. Une présentation de cette approche par modeleur peut être trouvée dans Murphy, Stohr & Asthana (1992, [312]),
Rosenthal (1996, [366]), Jacquet-Lagrèze (1997, [241]) et Giard (1997, [184]). La viabilité technique et écono-
mique de cette approche est attestée par de très nombreuses réalisations (par exemple, deux importantes appli-
cations industrielles de ces approches ont été réalisées à l’IAE de Paris dans le cadre de contrats de recherche;
elles sont décrites dans Giard, Triomphe, André (1997, [201]), qui présente un exemple détaillé d’une utilisation
d’un modeleur intégré dans un SIAD, et dans Giard & Triomphe (1996, [199]). Plusieurs modeleurs sont dispo-
nibles sur le marché. Parmi les plus connus, on peut signaler GAMS (voir Brooke, Kendrick & Meeraus, 1988,
[68]) et XPRESS-MP. Plusieurs exemples de l’ouvrage de Jacquet-Lagrèze (1997, [241]) illustrent l’utilisation
de XPRESS-MP. Il comporte en outre une liste des principaux modeleurs et comporte les références bibliogra-
phiques de base.
d’un ensemble de coefficients. Ces transformations sont locales, c’est-à-dire

sans incidence sur le reste du modèle ou des données.
- Il suffit de changer tout ou partie des ensembles des indices ou des coeffi-
cients pour générer un nouveau programme linéaire et ce, sans toucher au
modèle.
Cette approche focalise l’attention sur l’essentiel, à savoir la définition de
problèmes pertinents. Elle permet de tester rapidement des idées sur un jeu de
données restreint, le passage à un jeu plus complet ne remettant pas en cause le
modèle. Il est intéressant de noter que ces modeleurs sont utilisés de plus en plus
par des SIAD (systèmes d’aide à la décision), sans que l’utilisateur en ait
conscience : le SIAD permet de sélectionner un modèle dans un portefeuille
restreint de modèles, gère la sélection ou la saisie des données du modèle et
présente les propositions de solutions sous une forme immédiatement exploitable
et propice à une réflexion sur une éventuelle amélioration de l’énoncé du
problème. Cette orientation transforme un peu le statut de la recherche opération-
nelle, qui a longtemps été utilisée en postulant implicitement que l’on était, a
priori, capable de formuler correctement un «problème pertinent», ce qui est rare-
ment le cas, le «problème isolé» s’intégrant en fait dans un système ouvert.
II-2 Le dépassement du modèle linéaire
Certains modèles présentés ultérieurement s’appuient sur des « astuces »
permettant de contourner les hypothèses de linéarité qui semblent limiter la
Table des
matières
démarche de modélisation dans sa tentative de «coller» à une réalité complexe.

Au préalable, il convient de préciser ce que peuvent représenter les variables
utilisées dans un programme linéaire destiné à améliorer la gestion des processus
productifs. En pratique, on rencontre deux types de variables: les variables de
thématique
commande du problème étudié et les variables indicatrices.

Index
- Les variables de commande correspondent à la traduction, dans le

programme linéaire, des décisions qu’il est possible de prendre: niveaux de
production, quantité de ressources requises, etc. Ces variables peuvent être
continues ou discrètes. Parmi les variables discrètes, il faut souligner le rôle
particulièrement important joué par les variables binaires (c’est-à-dire
susceptibles de prendre seulement les valeurs 0 et 1). En effet, elles sont asso-
ciées à des décisions du type «faire» (valeur 1) ou «ne pas faire» (valeur 0),
cette décision ayant un impact direct sur la fonction-objectif. Les décisions
de cette nature sont variées: exécuter ou non une commande ou une tâche,
dédier ou non une ressource à la satisfaction d’une demande, partir ou non
d’une localisation A pour se rendre dans une localisation B, retenir ou non
l’une des alternatives décisionnelles (choix d’un équipement, d’une
gamme, etc.).
- Les variables indicatrices sont définies ici comme des variables binaires
auxiliaires qui sont associées aux valeurs prises par une ou plusieurs varia-
bles de commande et permettent de s’affranchir partiellement des contraintes
de linéarité liant les variables de commande dans la programmation linéaire.
II-2.1 Analyse de la valeur prise par le premier membre d’une

contrainte
Certains problèmes imposent de savoir si la valeur prise par une variable ou par
une combinaison linéaire de variables appartient à un sous-ensemble E1 des
valeurs de z, ou au sous-ensemble complémentaire E2 de ces valeurs de z1. Cette
information est fournie par une variable indicatrice δ dont la valeur est liée à celle
prise par z par l’intermédiaire d’une contrainte additionnelle que toute solution
faisable devra respecter.
L’analyse de cette contrainte liant z et δ s’effectue facilement dans un tableau
croisant les deux ensembles de valeurs de z, avec les deux valeurs de δ. À l’inter-
section d’une ligne et d’une colonne, on examine si la contrainte retenue peut ou
non être respectée. Pour permettre l’interaction entre z et δ, la contrainte doit être
telle qu’elle ne puisse pas être satisfaite dans une seule des quatre combinaisons
analysées de valeurs prises par z et δ. En supposant par exemple, mais la géné-
ralisation est immédiate, que la contrainte n’est pas satisfaite pour la combinaison
«ensemble E2 et δ = 1», on peut tirer quatre propositions suivantes associées à
toute solution réalisable (satisfaisant donc cette contrainte):
- si δ = 1, alors la valeur de z appartient nécessairement à l’ensemble E1 ;
- si la valeur de z appartient à l’ensemble E2, alors δ vaut nécessairement 0;
- si δ = 0, alors la contrainte est respectée quelle que soit la valeur de z;
- si la valeur de z appartient à l’ensemble E1, alors la contrainte est respectée
quelle que soit la valeur de δ.
Table des
matières
TABLEAU 348
Relations entre la contrainte, z et δ
δ=1 δ=0
thématique
Index
z ∈ E1 Contrainte satisfaite Contrainte satisfaite
z ∈ E2 Contrainte non satisfaite Contrainte satisfaite
D’une manière générale, il sera nécessaire2 d’introduire deux contraintes liant

δ et deux ensembles complémentaires de valeurs de z si l’on veut pouvoir conclure
par la proposition «δ = 1 si, et seulement si, la valeur de z appartient à l’ensemble
E1 ».
On analysera dans les tableaux 350 à 353 un ensemble de huit contraintes
permettant de traiter les cas de figure habituellement rencontrés. Pour simplifier la
présentation des ensembles de valeurs prises par z, on convient3 de délimiter par
0 les deux ensembles E1 et E2 (ce qui revient à retrancher b à toutes les valeurs de
1. E1 et E2 sont complémentaires soit dans l’ensemble des réels, soit dans l’ensemble des réels positifs ou nuls (cas
du tableau 350, page 1137).
2. Pour qu’il en soit autrement, il faudrait que la contrainte ne puisse être satisfaite simultanément dans deux combi-
naisons situées dans l’une des diagonales du tableau. Il faut ajouter que, dans de nombreux problèmes, une seule
relation suffit. Par exemple, l’examen du tableau 350 montre que δ = 1 si z > 0 et que si z = 0, δ peut prendre
indifféremment les valeurs 0 ou 1; si le fait que δ soit positif entraîne, directement ou non, une dégradation de
la valeur de la fonction-objectif, δ aura alors «tendance» à rester nul et une seule contrainte sera suffisante.
3. Le cas d’ensembles E1 et E2 disjoints sera évoqué en note de la page 1140.
la variable ou de la combinaison linéaire de variables, si la valeur de partage des

ensembles est b). D’une manière générale, z peut prendre des valeurs comprises
entre m et (M – ε)1 et la valeur 0 sépare les deux ensembles; m est normalement
négatif, sauf si E2 ne comporte que la valeur 0, auquel cas (étudié dans le tableau
350) m est défini comme étant la plus faible valeur positive que peut prendre z dans
E1. Les hypothèses testées sont décrites dans le tableau 349.
TABLEAU 349
Grilles de présentation des contraintes liant les valeurs prises par z et δ
Tableaux Contraintes Définition de z (avec b ≠ 0) E1 E2
tableau 350, C1 : «z ≤ Mδ» z ≥ 0 avec

C2 : «z ≥ mδ» z = x ou z = x – b ou z = ∑ ai xi – b z>0 z=0
page 1137 i
tableau 351, C3 : «z ≤ M(1-δ)» z = x – b ou z = ∑ ai xi – b

page 1138 C4 : «z ≥ mδ + ε(1− δ)» i
z≤0 z>0
tableau 352, C5 : «z ≤ Mδ + ε (δ − 1)» z = x – b ou z = ∑ ai xi – b

page 1138 C6 : «z ≥ m(1 − δ)» i
z≥0 z<0
tableau 353, C7 : «z ≤ Mδ1 + ε(δ1 − 1)» z = x – b ou z = ∑ ai xi – b

C8 : «z ≥ mδ2 + ε(1 − δ2)» z=0 z≠0
page 1139 i
tableau 354, C1 : «z ≤ Mδ» z = x – b ou z = ∑ ai xi – b

C2 : «z ≥ mδ» z≠0 z=0
page 1140 i
Table des
matières
TABLEAU 350
Création de contraintes permettant d’associer la variable indicatrice δ à la
proposition «z > 0 ⇔ δ = 1» (avec z ≥ 0)
La contrainte C1 La contrainte C2 Les contraintes C1 et C2 sont
«z ≤ Mδ» est «z ≥ mδ» est
thématique
simultanément
Index
Si δ = 1 Si δ = 0 Si δ = 1 Si δ = 0 Si δ = 1 Si δ = 0
Conclusions Si z = 0 Si z > 0
satisfaite non satisfaite satisfaite satisfaite satisfaites non satisfaites
satisfaite satisfaite non satisfaite satisfaite non satisfaites satisfaites
Avec la seule contrainte Avec la seule contrainte Avec les 2 contraintes

«z ≤ δM»: «z ≥ δm»: «z ≤ δM» et «z ≥ δm»:
δ = 1 ⇒ z > 0 ou z = 0 δ=1⇒z>0 δ=1⇔z>0
δ=0⇒z=0 δ = 0 ⇒ z > 0 ou z = 0 et
z>0⇒δ=1 z=0⇒δ=0 δ=0⇔z=0
z = 0 ⇒ δ = 1 ou 0 z > 0 ⇒ δ = 1 ou 0
II-2.2 Prise en compte de contraintes logiques

On a indiqué, page 1135, que l’usage de variables binaires dans la modélisation
par la programmation linéaire permet de traiter de manière efficace un certain
nombre de contraintes logiques. Sachant que xi = 1 signifie, selon les cas, soit que
1. M est une constante positive dont la valeur est supérieure à toutes celles que peut prendre z; d’un point de vue
opérationnel, il est conseillé (voir Williams, [444], p. 38) de ne pas «surdimensionner» M, dans la mesure où il
est numériquement préférable de ne pas avoir de fortes variations des coefficients de la fonction-objectif.
TABLEAU 351
proposition «z ≤ 0 ⇔ δ = 1» (z quelconque)
«z ≤ M (1 – δ)» est «z ≥ mδ + ε (1− δ)» est simultanément
Conclusions (ou z ≥ ε) Si z ≤ 0
satisfaite satisfaite satisfaite non satisfaite satisfaites non satisfaites

Si z > 0
non satisfaite satisfaite satisfaite satisfaite non satisfaites satisfaites

«z ≤ M (1 – δ)»: «z ≥ mδ + ε (1 – δ)»: «z ≤ M (1 – δ)»
δ=1⇒z≤0 δ = 1 ⇒ z ≤ 0 ou z > 0 et «z ≥ mδ + ε (1 – δ)»
δ = 0 ⇒ z ≤ 0 ou z > 0 δ=0⇒z>0 z≤0⇔δ=1
z>0⇒δ=0 z > 0 ⇒ δ = 1 ou 0 et z > 0 ⇔ δ = 0
z ≤ 0 ⇒ δ = 1 ou 0 z≤0⇒δ=1
TABLEAU 352
†
proposition «z ≥ 0 ⇔ δ = 1» (z quelconque)
Table des
matières
«z ≤ Mδ + ε (δ – 1)» est «z ≥ m (1 – δ)» est simultanément
Conclusions (ou z ≤ – ε) Si z ≥ 0
thématique
Index
Si z < 0
satisfaite satisfaite non satisfaite satisfaite non satisfaites satisfaites

«z ≤ Mδ + ε (δ – 1)»: «z ≥ m (1 – δ)»: «z ≤ Mδ + ε (δ – 1)»
δ = 1 ⇒ z ≥ 0 ou z < 0 δ=1⇒z≥0 et «z ≥ m (1 – δ)»
δ=0⇒z<0 δ = 0 ⇒ z ≥ 0 ou z < 0 z≥0⇔δ=1
z≥0⇒δ=1 z ≥ 0 ⇒ δ = 1 ou 0 et z < 0 ⇔ δ = 0
z < 0 ⇒ δ = 1 ou 0 z<0⇒δ=0
†. Le problème posé est voisin de celui analysé au tableau 350, à ceci près que z, et donc m, peuvent maintenant
être négatifs; ceci explique les différences entre les contraintes C1 et C3 (les contraintes C2 et C6 étant similai-
res).
la décision élémentaire i est prise auquel cas xi est une variable de commande (cf.
page 1135), soit que la contrainte élémentaire i est satisfaite, on dira, pour plus de
généralité, que la proposition Pi est vraie. Dans ces conditions, six jeux de règles
assez évidentes peuvent être énoncés1. Les deux premiers portent sur la véracité
d’un sous-ensemble de propositions prises dans un ensemble; elles permettent,
1. L’appel à la logique prédicative peut, bien sûr, s’avérer judicieux pour traiter des cas plus complexes que ceux
évoqués ici (voir le chapitre IX de l’ouvrage de H. P. Williams, [444]).
TABLEAU 353
†
proposition «δ = 0 ⇒ z ≠ 0»‡ (z quelconque)
La contrainte C7 La contrainte C8 Conséquences de la prise en compte
«z ≤ Mδ1 + ε (δ1−1)» «z ≥ mδ2 + ε (1−δ2)» simultanée des contraintes C7 et C6
est est
Si δ1 = 1 Si δ1 = 0 Si δ2 = 1 Si δ2 = 0
• δ1 = 0 et δ2 = 1 ⇒ z < 0
Si z < 0 Si z = 0 Si z > 0
satisfaite non satisfaite satisfaite satisfaite • δ1 = 1 et δ2 = 0 ⇒ z > 0

•δ1 = 1 et δ2 = 1 ⇒ z quelconque
• δ1 = 0 et δ2 = 0 ⇒ impossible
satisfaite non satisfaite satisfaite non satisfaite • ⇒ seuls les 3 premiers cas
pourront être observés ⇒
δ1 + δ2 = 1 ou 2
satisfaite satisfaite satisfaite non satisfaite • avec la contrainte δ1 + δ2 ≤ 1 + δ,
on obtient δ = 0 si z ≠ 0
Avec la seule contrainte Avec la seule contrainte
«z ≤ Mδ1 + ε (δ1 – 1)»: «z ≥ mδ2 + ε (1 – δ2)»: Avec les 3 contraintes
Conclusions
«z ≤ Mδ1 + ε (δ1 – 1)»

δ1 = 1 ⇒ z = 0 ou z ≠ 0 δ2 = 1 ⇒ z = 0 ou z ≠ 0
«z ≥ mδ2 + ε (1 – δ2)»
δ1 = 0 ⇒ z < 0 δ2 = 0 ⇒ z > 0
z ≥ 0 ⇒ δ1 = 1 z > 0 ⇒ δ2 = 0 ou 1 δ 1 + δ2 ≤ 1 + δ
δ=0⇒z≠0
z < 0 ⇒ δ1 = 0 ou 1 z ≤ 0 ⇒ δ2 = 0
†. La contrainte C7 est identique à la contrainte C5 (tableau 352), au remplacement près de δ par δ1 ; la contrainte
Table des
matières
C8 est identique à la contrainte C4 (tableau 351), au remplacement près de δ par δ2.

‡. Attention, la proposition réciproque n’est pas vraie car (voir dernière colonne du tableau) car on peut avoir z = 0
aussi bien avec δ = 0 qu’avec δ = 1.
notamment, de définir des alternatives décisionnelles ou des contraintes

thématique
Index
disjonctives, c’est-à-dire excluant la réalisation simultanée de plusieurs proposi-

tions, avec les variables binaires créées dans les tableaux 350 à 353. Les deux jeux
suivants portent sur les relations causales entre deux propositions; elles permet-
tent, notamment, d’introduire des décisions conditionnelles. Les deux dernières
portent sur les conditions liant un groupe de propositions à une autre proposition
et permettent d’élargir le champ d’application des deux premiers jeux de règles.
- Règles 1: «parmi les propositions P1, …, Pn, au plus, une seule peut être
n
vraie1 » se traduit par la condition: ∑ xi ≤ 1 . Si «parmi les propositions P1,
i=1
…, Pn, au plus, k propositions peuvent être vraies», il suffit de remplacer 1
par k dans le second membre de la contrainte et si «parmi les propositions P1,
…, Pn, au moins, k propositions n doivent être vraies», il suffit de remplacer
≤ 1 par ≥ k dans la contrainte.
- Règles 2: «parmi les propositions P1, …, Pn, l’une d’entre elles, et une seule,
1. Cette proposition peut aussi s’énoncer sous la forme «P1 est vraie» ou «P2 est vraie» ou… «Pn est vraie»; dans
ce cas, on est en présence de ce que l’on appelle, en logique, un ou exclusif.
TABLEAU 354
Création de contraintes permettant d’associer la variable indicatrice δ aux
propositions « δ = 0 ⇒ z = 0»† et «z ≠ 0 ⇒ δ = 1»‡ (z quelconque)
La contrainte C7 La contrainte C8 Conséquences de la prise en compte
«z ≤ Mδ» est «z ≥ mδ» est simultanée des contraintes C7 et C6
Conclusions Si z < 0 Si z = 0 Si z > 0
satisfaite satisfaite satisfaite satisfaite satisfaites satisfaites
satisfaite satisfaite satisfaite non satisfaite satisfaites non satisfaites
Avec la seule contrainte Avec la seule contrainte

«z ≤ Mδ»: «z ≥ mδ»: Avec les 2 contraintes
δ = 1 ⇒ z ≠ 0 ou = 0 δ = 1 ⇒ z ≠ 0 ou = 0 «z ≤ Mδ» et «z ≥ mδ»
δ=0⇒z≤0 δ=0⇒z>0 δ = 1 ⇒ z ≠ 0 ou = 0
z>0⇒δ=1 z ≥ 0 ⇒ δ = 0 ou 1 δ=0⇒z≠0
z ≤ 0 ⇒ δ = 0 ou 1 z<0⇒δ=1
†. Attention, la proposition réciproque n’est pas vraie car (voir dernière colonne du tableau) car on peut avoir z = 0 aussi bien avec δ = 0
qu’avec δ = 1.
Table des
matières
‡. Attention, la proposition réciproque n’est pas vraie car (voir dernière colonne du tableau) car on peut avoir δ = 1 aussi bien avec z = 0
qu’avec z ≠ 0.
n
est nécessairement vraie» se traduit par la condition : ∑ xi = 1 . Si «parmi
1
thématique
i=1
les propositions P1, …, Pn, exactement k propositions (k ≤ n) doivent être
Index
vraies», il suffit de remplacer 1 par k dans le second membre de la contrainte;
si k = n, on retrouve une généralisation de la règle 4 ci-après.
- Règles 3: «si la proposition P1 est vraie, alors la proposition P2 doit être
vraie» se traduit par la condition: x1 ≤ x2 qui force x2 à prendre la valeur 1 si
x1 vaut 1; ceci n’empêche pas x2 à prendre la valeur 1 si x1 vaut 0, c’est-à-dire
que la proposition P2 peut être vraie alors que la proposition P1 est fausse. Si,
en outre, on a « P2 vrai » ⇒ « P3 vrai », il faudra ajouter x2 ≤ x3 ; la géné-
ralisation de ce raisonnement à une causalité en cascade est immédiate.
- Règle 4: «si la proposition P1 est vraie, alors la proposition P2 doit être vraie
et, réciproquement, si la proposition P2 est vraie, alors la proposition P1 doit
être vraie» se traduit par la condition: x1 = x2 qui oblige les deux propositions
à être simultanément vraies ou simultanément fausses. La généralisation à n
propositions devant être toutes simultanément vérifiées ou simultanément
non vérifiées se traduit par les n – 1 contraintes suivantes: x1 = x2 ; x2 = x3 ;
…; xn–1 = xn.
1. Un cas particulier de deux contraintes disjonctives est celui se traduisant par le fait que l’on ait soit z ≥ A, soit
z ≤ B, avec B < A. Dans ce cas, on introduit la variable binaire δ, valant 1 seulement si la première des deux
contraintes est satisfaite et 0 seulement dans le cas contraire, et les deux contraintes suivantes, où M est, comme
précédemment, une constante positive de valeur très élevée: z ≥ A – ( 1 – δ )M et z ≤ B + δM .
- Règles 5: «si la proposition P1 est vraie ou si la proposition P2 est vraie, alors

la proposition P3 doit être vraie» se traduit1 par la condition: x1 + x2 ≤ 2x3. La
généralisation est immédiate2 : «il suffit que l’une des propositions P1, …, Pn
soit vraie pour que la proposition Pn+1 soit vraie» se traduit par la condition:
n
∑ xi ≤ nxn + 1 ; dans ce dernier cas, plusieurs propositions Pi peuvent simulta-
i=1
nément être vraies (i ≤ n).
- Règles 6: «si la proposition P1 est vraie et si la proposition P2 est vraie, alors
la proposition P3 doit être vraie» se traduit par les conditions suivantes: x3 ≤
x1 ; x3 ≤ x2 et x1 + x2 ≤ 1 + x3. La généralisation est immédiate: «il est néces-
saire que toutes les propositions P1, …, Pn soient vraies pour que la proposi-
tion Pn + 1 soit vraie» se traduit par les n conditions «xn +1 ≤ xi » (i variant de
n
1 à n), auxquelles il faut ajouter la condition « ∑ xi ≤ n – 1 + xn+1 ». Des
i=1
adaptations de cette règle ont été utilisées à la page 139, dans des cas de
figures où la fonction-objectif incluait xn +1 sous une forme tendant à le rendre
nul dans un cas et égal à un dans l’autre, rendant inutiles les conditions «xn+1
≤ xi ».
II-2.3 Introduction des fonctions-objectifs non linéaires
Table des
matières
Dans les fonctions-objectifs utilisées jusqu’ici, la vision économique passait

principalement par une minimisation du coût d’un processus productif défini
comme une somme de coûts variables directs constants, liés aux valeurs prises par
les variables de commande. Par exemple, dans le cas simple d’une production x à
thématique
Index
laquelle est associé le coût variable unitaire c, la fonction-objectif est: z = cx.

Cette production peut être une somme de productions dédiées (pour des clients,
différents, pour des sites différents…), auquel cas, la fonction-objectif est: z =
c ∑ xi . La généralisation à la production de plusieurs produits ou services est
i
immédiate.
Cette vision économique n’est pas acceptable lorsque des charges fixes, variant
éventuellement par palier, existent ou que certains coûts variables directs (ou
recettes unitaires) ne sont pas les mêmes pour des plages disjointes de valeurs de
production (et/ou de vente). Les fonctions linéaires par morceau couvrent assez
bien les principaux cas de figure rencontrés3. On commencera par examiner le cas
le plus simple, celui de l’existence de charges fixes (§ II-2.3.1), avant de généra-
liser la démarche (§ II-2.3.2).
1. En appliquant la contrainte C1 du tableau 350, page 1137, avec M = 2. On peut ajouter que l’on est en présence
d’un ou inclusif, lequel n’exclut pas la réalisation simultanée des propositions (contrairement au «ou exclusif»).
2. Il s’agit d’une utilisation de la contrainte C1 du tableau 350, page 1137, avec M = n.
n n n
3. Certains problèmes nécessitent l’usage de fonctions-objectifs du type ∑ ∑ aij xi xi' + ∑ bi xi . Le lecteur est
i = 1 i' = 1 i=1
invité à se reporter à l’ouvrage de Jacquet-Lagrèze (1997, [241]), p. 33 et suivantes.
II-2.3.1 Introduction des charges fixes

Cette structure de coûts n’est pas acceptable dans un certain nombre de
problèmes où une décision de production implique d’avoir à supporter une charge
fixe, c’est-à-dire que le coût partiel de production du bien considéré est nul si la
production est nulle, et égal à cx + K, si x > 0. Pour obtenir ce résultat, on introduit
la variable y qui est telle que y = 0, si x = 0 et y = 1, seulement si x > 0, ce qui permet
d’introduire la charge fixe dans la fonction-objectif:
Min z, avec z = cx + Ky + … relation 481
La liaison entre x et y est obtenue (en application de la contrainte C1 du tableau
350 de la page 1137) avec la contrainte additionnelle suivante:
x ≤ My relation 482
où M est une constante supérieure ou égale à la valeur maximale que peut prendre
x.
II-2.3.2 Généralisation aux fonctions de coût (ou de recettes) linéaires par
morceau
La généralisation à toute fonction de coût linéaire par morceau, s’effectue sans
difficulté, en introduisant autant de productions fictives xi qu’il y a de plages k de
valeurs (comprise entre Mk–1 et Mk, la borne supérieure appartenant seule à l’inter-
valle, avec M0 = 0) sur lesquelles le coût variable est constant et qui sont toutes
nulles, sauf celle qui inclut la production x dans sa plage de valeurs et qui est, bien
entendu, égale à cette production (xk = x). La figure 274 illustre la fonction de coût
Table des
matières
utilisée qui, dans cet exemple, n’est ni concave (ce qui implique que le coût moyen
de production ne croisse jamais lorsque x croît), ni convexe (ce qui implique que
le coût moyen de production ne décroisse jamais lorsque x croît). Cette géné-
ralisation permet, notamment, de traiter le cas des rabais uniformes et rabais
thématique
progressifs en approvisionnement externe (figure 275, page 1143).
Index
FIGURE 274
Fonction de coût total quelconque
(cj1yj1 + Kj1zj1) + (cj2yj2 + Kj2zj2) + (cj3yj3 + Kj3zj3) + (cj4yj4 + Kj4zj4)
cj4
cj3
Kj4
Fonction du coût total cj2
Kj2
(ni concave ni convexe) Kj3 cj1 m Kj
Kj1
y j = ∑ di ⋅ xij = ∑ y jh
Mj0 = 0 Mj1 Mj2 Mj3 Mj4 i=1 h=1
Il faut remplacer, dans le reste du problème, x, par x1 + x2 + x3 + x4, plutôt que

d’introduire la contrainte x = x1 + x2 + x3 + x4. Dans ces conditions, la fonction-
objectif devient (pour la partie relative à ce coût de production):
Min z, avec z = (cj1yj1 + Kj1zj1) + (cj2yj2 + Kj2zj2) + (cj3yj3 + Kj3zj3) + (cj4yj4
+ Kj4zj4) + … relation 483
FIGURE 275
Fonction de coût total associée à un rabais progressif ou à un rabais uniforme
Rabais progressif Rabais uniforme
K3
K2
K1 = 0 K1 = K2 = K3 = 0
M0 = 0 M1 M2 x M0 = 0M1 M2 x
avec la série suivante de contraintes1 :

0 ≤ y j1 < M j1 z j1
M j1 z j2 ≤ y j2 < M j2 z j2
M j2 z j3 ≤ y j3 < M j3 z j3
M j3 z j4 ≤ y j4 < M j4 z j4
z j1 + z j2 + z j3 + z j4 = 1
Table des
matières
La dernière contrainte (en application de la règle 2, page 1139) permet d’activer

au plus l’une des fonctions de coût (ckxk + Kkyk), celle pour laquelle yk = 1 (mais
si l’on ne produit pas, tous les yk sont nuls). Les contraintes précédentes géné-
ralisent le cas initialement étudié en permettant de forcer à 0 les productions xk des
thématique
tranches non retenues (lorsque yk = 0, les deux bornes sont nulles, ce qui oblige la
Index
production correspondante xk à être nulle).

Remarques:
- si la fonction de coût est concave (fonction de coût total non décroissante;
voir illustration à la figure 276, page 1144), alors la « partie droite » des
doubles inéquations est inutilecar le coût total pour une quantité x0 croît avec
le numéro de tranche de coût, ce qui conduit à retenir la tranche de coûts
ayant le numéro d’ordre le plus faible possible;
- cette formulation reste valable même en cas de variation de charges fixes par
palier (ce qu’illustre l’exemple retenu);
- si x varie de manière discontinue, la plus faible variation pertinente pour la
fonction de coût étant notée ε, il faut alors décider clairement si la quantité x
= Mi relève de la plage i ou de la plage i + 1. Supposons, dans notre exemple,
que les bornes supérieures des classes soient exclues, on aura alors: 0 ≤ x1 ≤
(M1 – ε) y1 ; M1y2 ≤ x2 ≤ (M2y2 – ε); etc. On peut noter que la relation y1 + y2
+… = 1 empêche x de prendre une valeur comprise entre Mi – ε et Mi. La
1. Les variables étant non négatives, la première contrainte double se réduit en réalité à x1 ≤ M1y1 ; la formulation
retenue a pour seul avantage de permettre la généralisation du raisonnement; il s’ensuit qu’après développement
dans cet exemple, il y a 8 contraintes.
FIGURE 276
Fonction de coût total concave
K2 c3
K1 c2
c1
M1 M2 M3
transposition de ce qui vient d’être dit au cas de la borne inférieure est immé-
diate.
La généralisation du raisonnement à un nombre quelconque de plages de
valeurs est immédiate1 et conduit, dans le cas général, à créer un nombre de
contraintes égal à 2 x K contraintes mais il existe une formulation alternative plus
efficace numériquement lorsque le nombre de plages K est supérieur à 3,
puisqu’elle nécessite K + 1 contraintes (contre 2K – 1 contraintes) et la création
de K variables binaires additionnelles. Cette formulation s’appuie sur le fait que
toute valeur de x comprise entre Mk–1 et Mk peut encore s’écrire comme une
combinaison linéaire de ces bornes, c’est-à-dire: αk–1Mk–1 + αkMk, avec αk–1 + αk
= 1 et qu’il en est de même pour la fonction de coût qui, pour toute valeur de x
Table des
matières
comprise entre Mk–1 et Mk peut encore s’écrire αk–1Wk–1 + αkWk, où Wk est le coût
total pour la valeur de x prise à la borne k considérée; on remplace dans la formu-
lation les K variables xk, par K + 1 variables αk ; dans ces conditions, dans le reste
K
thématique
du problème, la production x est remplacée par ∑ αk Hk (avec Hk = Mk + Mk + 1)
Index
k=0
et, pour obliger à n’avoir au plus que deux valeurs non nulles de αk, de surcroît
pour deux bornes consécutives, il faut introduire K variables binaires βk, avec
K
∑ βk = 1 et K + 1 contraintes α0 ≤ β1 ; α1 ≤ β1 + β2 ; α2 ≤ β2 + β3 ; αk ≤ βk
k=1
+ βk+1 ; αK–1 ≤ βK–1 + βK ; αK ≤ βK.
Il faut ajouter que si la fonction-objectif consiste à maximiser une marge, au
lieu de minimiser un coût, l’utilisation de la technique proposée ici ne se justifie
pas, dès lors que la marge unitaire est une fonction non croissante (c’est-à-dire
concave) de la quantité produite.
En effet, la production totale est la somme des productions sur chacune des tran-
ches, c’est-à-dire x1 + x2 + x3, dans notre exemple (et, d’une manière générale,
∑ xi ), avec une contrainte de production pour chaque tranche: x1 < M1 ; x2 < M2 –
i
1. La fonction de coûts devient: z = ∑ ( ci xi + K i yi ) +…, sous contraintes: ∑ yi ≤ 1 et, pour chaque plage de valeurs i, délimitée par Mi-1
i i
et Mi (avec M0 = 0): M i – 1 y i ≤ x i ≤ M i y i .
M1 ; x3 < M3 – M2. La marge totale est: c1x1 + c2x2 + c3x3 (et, d’une manière géné-
rale, ∑ ci xi ). La fonction-objectif forcera donc l’utilisation prioritaire de la
i
production la plus rentable, ce qui fait qu’il n’y a pas besoin de variable dichoto-
mique comme dans le cas d’une fonction-objectif de coût quelconque.
Table des
matières
thématique
Index

Chapitre 16

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 16

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 16

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre XVI

La programmation linéaire1 est une branche de la programmation mathéma-

SECTION I PRÉSENTATION DES BASES TECHNIQUES DE LA

I-1 Les fondements de la programmation linéaire

Max x0 , avec: Min y0 , avec:

.x ≥ 0 .x ≥ 0 , pour j = 1, ... , . y ≥ 0 , pour i = 1, ... , . y ≥ 0

n+1≤ j≤n+m 1≤i≤n

(m, n + m) (m, m) A (m, m)

. et:j = 1, ... , n + m j = 1, ... , n

* dij = aij , pour ∀i * gij = ah j , pour ∀ j

Les x j tels que Les yi tels que

cette sous-matrice de D, et N la sous-matrice résiduelle, l’équation matricielle

formulation canonique du problème, en conséquence de quoi, la valeur prise par

Dans une première catégorie de problèmes économiques, le vecteur x est un

de ressources i, nécessaire à la production d’une unité du produit j.

La signiﬁcation prise par x0 est donc une valorisation de quantités. À

. Tableau numérique initial

Tableau analytique correspondant Tableau analytique correspondant

0 –5 –11 0 0 –4 0 9 taleau analytique correspondant

Interprétation des résultats pour le problème primal

. contrainte 2: 7 ( 40 ⁄ 7 ) + 3 ( 58 ⁄ 7 ) = 424 ⁄ 7 (non saturation, reste 386/7)

Max x0, avec Min y0, avec

1x1+1x2+1x3+1x4≤ 15 1y5 + 7y6 + 3y7 ≥ 4

(1) 1x1+1x2+1x3+1x4+ x5 yG = c; avec:

I-3.1 Modiﬁcation de coefﬁcients de la fonction-objectif

L’examen de ces conditions nous mène à dissocier le cas des coefﬁcients de

ensuite le cas général avec l’étude des implications de la variation simultanée de

change, on a autant d’inéquations à une seule variable (∆ c j ) qu’il y a de variables

I-3.1.3 Modiﬁcation de plusieurs coefﬁcients de la fonction-objectif

[ 13 ⁄ 7, 0, 5 ⁄ 7 ] + [ ∆c1, 0, ∆c3 ] –61 ⁄ 7 1 4⁄7 ≥0

I-3.2.1 Cas d’une contrainte non saturée

I-3.2.2 Cas de contrainte saturée

I-4 Résolution d’un programme linéaire par l’algorithme du

- la fonction à optimiser, et que l’on appelle également fonction-objectif,

Par exemple, si chacune des 4 premières variables prend la valeur 2, la variable

de se trouver en présence d’un système d’équations dont la solution est impos-

sible. Notre problème se ramène donc à celui de la sélection de l’ensemble de 3

Le repérage des variables de base s’effectue au cours d’une itération quel-

x5 , à 2 unités, de la variable x6 et à 15 unités de la variable x7 . Il s’ensuit que si

x4 se substituait en totalité à x6 , il prendrait comme valeur le quotient de 120

à x7 ), c’est-à-dire 100/15 = 20/3 ≈ 6,66. Enﬁn, si x4 se substituait en totalité à x5 ,

ligne du pivot; par exemple, on retranchera à la ligne 1 la nouvelle ligne du pivot

.. Étape 3 : changement de base

ligne, multipliée par la nouvelle ligne du pivot (ligne 4)

- ligne 1: multiplier la ligne 4 par –11 et la retrancher à la ligne 1

D’où le tableau du simplexe à la fin de l’itération 1

x5 = 25/3 4/5 2/3 1/3 0 1 0 –1/15

25/3 / 4/5 = 125/12 minimum x5 = 25/3 4/5 2/3 1/3 0 1 0 –1/15

320/3 / 33/5 = 1600/99 x6 = 320/3 33/5 13/3 5/3 0 0 1 –2/15

20/3 / 1/5 = 100/3 x4 = 20/3 1/5 1/3 2/3 1 0 0 1/15

x1 = 125 ⁄ 12 et x5 = 0 (x5 variable sortante)

D’où le tableau du simplexe à la fin de l’itération 2

125/12 / 5/12 = 25 x1 = 125/12 1 5/6 5/12 0 5/4 0 –1/12

455/12 / –13/12 <0 x6 = 455/12 0 –7/6 -13/12 0 –33/4 1 5/12

55/12 / 7/12 = 55/7 minimum x4 = 55/12 0 1/6 7/12 1 –1/4 0 1/12

D’où le tableau du simplexe à la fin de l’itération 3

Lorsque certaines contraintes du problème canonique sont des égalités, il n’y a

numériques du problème; on préférera cependant travailler ici, sous la forme litté-

Le tableau initial du simplexe devient le tableau 345.