Programmation Linéaire

Problèmes de transport

Fabian Bastin
DIRO
Université de Montréal

1 / 52
 Problèmes de transport
Beaucoup de problèmes linéaires présentent certaines structures qui
simplifient grandement leur résolution.

Supposons que nous avons m origines contenant certains quantités

d’une marchandise qui doit etre transportée à n destinations pour
satisfaires certaines demandes :
• origine i : contient la quantité ai ;
• destination j : présente une demande bj .

Nous supposons le problème équilibré, i.e. l’offre totale est égale à

la demande totale :
Xm X n
ai = bj .
i=1 j=1

2 / 52
 Formulation

Les nombres ai et bj , i = 1, 2, . . . , m, j = 1, 2, . . . , n, sont

supposés non-négatifs, et de plus, souvent entiers.

cij : coût de transport d’une unité de marchandise de l’origine i à

la destination j.

On veut déterminer les quantitiés à transporter pour chaque paire

(i, j).

3 / 52
 Formulation

Programme mathématique :
m X
X n
min cij xij
x
i=1 j=1
Xn
s.à. xij = ai , i = 1, 2, . . . , m
j=1
m
X
xij = bj , j = 1, 2, . . . , n
i=1
xij ≥ 0, ∀ i, j.

4 / 52
 Formulation

Réécrivons les contraintes d’égalité :

x11 + . . . + x1n = a1
x21 + . . . + x2n = a2
..
.
xm1 + . . . + xmn = am
x11 +x21 +xm1 = b1
x12 +x22 +xm2 = b2
..
.
x1n +x2n +xmn = bn

5 / 52
 Formulation
En d’autres termes, la matrice A a la structure
 T 
1

 1T 

A=
 .
. 
 . 

 T
1 
I I ... I

où I est la matrice identité (n × n).

Notation plus compacte :

 
c11 c12 . . . c1n
 c21 c22 . . . c2n 
a = (a1 , a2 , . . . , am )
C= .
 
.. .. .. 
b = (b1 , b2 , . . . , an )  .. . . . 
cm1 cm2 . . . cmn
6 / 52
 Exemple

 
3 4 6 8 9
a = (30, 80, 10, 60) 2 2 4 5 5
C= 
b = (10, 50, 20, 80, 20) 2 2 2 3 2
3 3 2 4 2

La somme de l’offre, ainsi que de la demande, est 180.

7 / 52
 Généralisation
Il est facile d’étendre la formulation au cas plus réaliste où
n
X m
X
xij ≤ ai , i = 1, . . . , m, xij ≥ bj , j = 1, . . . , n,
j=1 i=1

donnant lieu au problème

m X
X n
min cij xij
x
i=1 j=1
n
X
s.à. xij ≤ ai , i = 1, 2, . . . , m
j=1
Xm
xij ≥ bj , j = 1, 2, . . . , n
i=1
xij ≥ 0, ∀ i, j.
8 / 52
 Généralisation
Nous pouvons considérons un excédent de production au travers de
variables d’écart qui vont désservir une destination virtuelle, à coût
nul, permettant dePtenir comptePn de ce surplus, en considérant une
demande bn+1 = m i=1 ai − j=1 bj :
m X
X n
min cij xij
x
i=1 j=1
n
X
s.à. xij + si,n+1 = ai , i = 1, 2, . . . , m
j=1
Xm
xij = bj , j = 1, 2, . . . , n
i=1
m
X
si,n+1 = bn+1
i=1
xij ≥ 0, ∀ i, j, si,n+1 ≥ 0, ∀ i.
9 / 52
 Réalisabilité et optimalité
Première étape : montrer que le problème est réalisable.

Soit P
S la demandePntotale (et donc, l’offre totale) :
S= m i=1 a i = j=1 bj .
ai bj
xij0 = , i = 1, 2, . . . , m, j = 1, 2, . . . , n,
S
est réalisable :
n n
X X ai b j
xij0 = = ai
S
j=1 j=1
m m
X X ai bj
xij0 = = bj
S
i=1 i=1

De plus, xij est bornée par ai (et bj ). Un programme avec un

ensemble réalisable et borné a toujours une solution optimale. Dès
lors, un problème de transport a toujours une solution optimale.
10 / 52
 Redondance
Nous avons un ensemble de m + n contraintes linéaires. Toutefois,
m X
X n m
X m X
X n n
X
xij = ai , xij = bj .
i=1 j=1 i=1 i=1 j=1 j=1

On a formé deux combinaisons linéaires distinctes des contraintes,

pour former des termes de gauche identiques (et les termes de
droite sont également identiques en vertu de l’hypothèse de
départ).

Considérons la première contrainte :

n
X m X
X n m X
X n n
X m
X
x1j = a1 ⇔ xij − xij = bj − ai
j=1 i=1 j=1 2=1 j=1 j=1 i=2

11 / 52
 Redondance

Autrement dit, nous avons pu réécrire la première contrainte

comme une combinaison linéaire des autres contraintes.

On pourrait faire la même chose avec n’importe quelle contrainte.

Il y a donc une contrainte redondante.

On va établir qu’on ne peut trouver qu’une redondance, et donc

ramener le problème à un ensemble de m + n − 1 vecteurs. Une
solution de base réalisable non-dégénérée consistera de m + n − 1
variables de base.

12 / 52
 Théorème

Un problème de transport a toujours une solution, mais il y a

exactement une constrainte d’égalité redondante. Quand on retire
n’importe laquelle des contraintes d’égalité, le système restant de
n + m − 1 contraintes d’égalité est linéairement indépendant.

Preuve

L’existence d’une solution et la redondance ont déjà été établis. La

somme de toutes les contraintes d’origine moins la somme de
toutes les contraintes de destination est égale à zéro, et n’importe
quelle contrainte peut être exprimée comme une combinaison
linéaire des autres. On peut donc retirer n’importe laquelle de ces
contraintes. Supposons qu’on retire la dernière.

13 / 52
 Théorème
Nous avons donc le système d’équations
n
X
x1j − a1 = 0
j=1
n
X
x2j − a2 = 0
j=1

..
.
n
X
xmj − am = 0
j=1
m
X
xi1 − b1 = 0
i=1
..
.
m
X
xi,n−1 − bn−1 = 0
i=1

14 / 52
 Théorème
Supposons par l’absurde qu’il existe une combinaison linéaire des
équations restantes qui soit nulle.
Notons les coefficients d’une telle combinaison αi , i = 1, 2, . . . , m,
et βj , j = 1, 2, . . . , n − 1 :
 
m n n−1 m
!
X X X X
αi  xij − ai  + βj xij − bj = 0.
i=1 j=1 j=1 i=1

Comme nous avons écarté la dernière contrainte, xin ,

i = 1, 2, . . . , m apparaı̂t seulement dans la i e équation, de sorte que
 
m m n−1 n−1 m
!
X X X X X
αi xin + αi  xij − ai  + βj xij − bj = 0.
i=1 i=1 j=1 j=1 i=1

Dès lors, αi = 0, i = 1, 2, . . . , m.
15 / 52
 Théorème

Il reste
n−1 m
!
X X
βj xij − bj = 0.
j=1 i=1

Autrement dit, chaque xij n’apparaı̂t que dans une équation

(jamais si j = n), aussi βj = 0, j = 1, 2, . . . , n − 1.

Dès lors, l’ensemble d’équations est linéairement indépendant.

16 / 52
 Découverte d’une solution réalisable de base
Du théorème précédent, on voit qu’une base pour le problème de
transport consiste de m + n − 1 vecteurs, et qu’un solution
réalisable de base-non dégénérée consiste de m + n − 1 variables.

Tableau de solution :
x11 x12 x13 ... x1n a1
x21 x22 x23 ... x2n a2
.. .. .. .. .. ..
. . . . . .
xm1 xm2 xm3 ... xmn am
b1 b2 b3 ... bn

Les éléments individuels du tableau apparaissent dans des cellules

et représentent une solution. Une cellule vide dénote une valeur
nulle.
17 / 52
 Règle du coin Nord-Ouest

Etape 0. Le tableau est créé, avec toutes les cellules vides.

Etape 1. On sélectionne la cellule dans le coin supérieur
gauche (d’où le nom de la méthode).
Etape 2. On alloue le montant maximum réalisable compatible
avec les exigences de sommes sur la ligne et la
colonne impliquant cette colonne (au moins une de
ces exigences sera remplie).
Etape 3. On se déplace d’une cellule vers la droite s’il reste des
exigences de ligne à satisfaire (offre). Autrement, on
se déplace d’une cellule vers le bas. Si toutes les
exigences sont remplies, arrêt. Sinon, retour à l’étape
2.

18 / 52
Règle du coin Nord-Ouest : exemple

a = (30, 80, 10, 60)

b = (10, 50, 20, 80, 20)

10 20 30
30 20 30 80
10 10
40 20 60
10 50 20 80 20

19 / 52
 Règle du coin Nord-Ouest : dégénérescence

Il existe la possibilité qu’à un certain point, les exigences de ligne et

de colonne correspondant à une cellule soient toutes deux remplies.

La prochaine entrée sera alors un zéro, indiquant une solution de

base dégénérée. Dans pareil cas, il y a un choix à faire quand à
l’endroit où place le zéro : à droite ou en-dessous.

30 30 30 30
20 20 40 20 20 0 40
0 20 20 20 20
20 40 60 20 40 60
50 20 40 40 50 20 40 40

20 / 52
 Solutions de base

• La règle du coin Nord-Ouest permet de trouver facilement une

solution de base réalisable.
• Comment caractériser les autres solutions de base ?
• Le simplexe peut-il se réinterpréter plus simplement dans ce
cadre ?

21 / 52
 Matrices triangulaires

Définition. Une matrice carrée M non singulière est dite

triangulaire si elle peut être mise sous la forme d’une matrice
triangulaire inférieure au moyen d’une permutation de ses lignes et
colonnes.

   
1 2 0 1 0 2 4 0 0 0 0 0
4 1 0 5 0 0 1 2 0 0 0 0
   
0 0 0 4 0 0 → 5 1 4 0 0 0

 
2 1 7 2 1 3 1 2 1 2 0 0
  
2 3 2 0 0 3 0 3 2 3 2 0
0 2 0 1 0 0 2 1 2 3 7 1

22 / 52
 Théorème de triangularité de base

Chaque base du problème de transport est triangulaire.

Pour le voir, repartons du système de contraintes

x11 + . . . + x1n = a1
x21 + . . . + x2n = a2
..
.
xm1 + . . . + xmn = am
x11 +x21 +xm1 = b1
x12 +x22 +xm2 = b2
..
.
x1n +x2n +xmn = bn

23 / 52
 Théorème de triangularité de base
Changeons le signe de la demi-partie supérieure du système ; la
matrice de coefficients consiste d’entrées égales à +1, -1 ou 0.

−x11 − . . . − x1n = −a1

−x21 − . . . − x2n = −a2
..
.
−xm1 − . . . − xmn = −am
x11 +x21 +xm1 = b1
x12 +x22 +xm2 = b2
..
.
x1n +x2n +xmn = bn

On peut également supprimer n’importe quelle de ces équations

pour éliminer la redondance.

24 / 52
 Théorème de triangularité de base
De la matrice de coefficients résultante, on forme une base B en
sélectionnant un sous-ensemble non singulier de m + n − 1
colonnes.

Chaque colonne de B contient au plus deux entrées non-nulles : un

+1 et un -1. Dès lors, il y a au plus 2(m + n − 1) entrées non
nulles dans la base.

Cependant, si chaque colonne contient deux entrées non nulles,

alors la somme de toutes les lignes serait zéro, contredisant la
non-singularité de B.

Dès lors, au moins une colonne de B doit contenir seulement une

seule entrée non nulle. Ceci signifie que le nombre totale d’entrées
non nulles dans B est inférieur à 2(m + n − 1).

25 / 52
 Théorème de triangularité de base

Dès lors, il y a au moins une ligne avec seulement une entrée

non-nulle, que l’on peut isoler pour créer la première ligne de la
matrice triangulaire.

Un argument similaire peut être appliqué à la sous-matrice de B

obtenue en supprimant la ligne contenant une seule entrée non
nulle et la colonne correspondant à cette entrée. Cette sous-matrice
doit également contenir une ligne avec une seule entrée non-nulle.
On repète l’argument jusqu’à obtenir B triangulaire.

26 / 52
 Théorème de triangularité de base : illustration

Considérons la solution réalisable

10 20 30
30 20 30 80
10 10
40 20 60
10 50 20 80 20
Nous allons réexprimer ce système en triangularisation la matrice
associée.

27 / 52
 Procédure de triangularisation

Étape 1. Trouver une ligne avec exactement une entrée

différente de zéro.
Étape 2. Former une sous-matrice de la matrice utilisée à
l’étape 1 en barrant la ligne trouvée à l’étape 1 et la
colonne correspondant à l’entrée différente de zéro
dans cette ligne. Revenir à l’étape 1 avec cette
sous-matrice.

28 / 52
 Théorème de triangularité de base : illustration
Sont dans la base : x11 , x12 , x22 , x23 , x24 , x34 , x44 , x45 , pour le
système d’équations

x11 + x12 = 30
x22 + x23 + x24 = 80
x34 = 10
x44 + x45 = 60
x11 = 10
x12 + x22 = 50
x23 = 20
x24 + x34 + x44 = 80
x45
 =
20


29 / 52
 Théorème de triangularité de base : illustration

Sous forme matricielle, en laissant tomber la dernière contrainte,

nous avons
    
1 1 0 0 0 0 0 0 x11 30
0 0 1 1 1 0 0 0 x12  80
   
 
0 0 0 0 0 1 0 0
 x22  10
   

0 0 0 0 0 0 1 1
 x23  = 60
   

1 0 0 0 0 0 0 0 
x24  10
   

0 1 1 0 0 0 0 0 x34 
 50
   

0 0 0 1 0 0 0 0 x44  20
0 0 0 0 1 1 1 0 x45 80

30 / 52
 Théorème de triangularité de base : illustration

La cinquième ligne a un seul élément non-nul. Nous la permutons

avec la première ligne, ce qui donne
    
1 0 0 0 0 0 0 0 x11 10
0 0 1 1 1 0 0 0 x12  80
    
0 0 0 0 0 1 0 0 x22  10
    
0 0 0 0 0 0 1 1 x23  60
1 1 0 0 0 0 0 0 x24  = 30
    
    
0 1 1 0 0 0 0 0 x34  50
    
0 0 0 1 0 0 0 0 x44  20
0 0 0 0 1 1 1 0 x45 80

31 / 52
 Théorème de triangularité de base : illustration

La première ligne est fixée, et nous devons identifier une ligne avec
un seul élément non nul dans les colonnes 2 à 8. C’est le cas de la
septième ligne, que nous permutons avec la première.
    
1 0 0 0 0 0 0 0 x11 10
0 0 0 1 0 0 0 0 x12  20
    
0 0 0 0 0 1 0 0 x22  10
    
0 0 0 0 0 0 1 1 x23  60
1 1 0 0 0 0 0 0 x24  = 30
    
    
0 1 1 0 0 0 0 0 x34  50
    
0 0 1 1 1 0 0 0 x44  80
0 0 0 0 1 1 1 0 x45 80

32 / 52
 Théorème de triangularité de base : illustration

Permutons maintenant la deuxième et la quatrième colonnes pour

allumer le 1 sur la deuxième colonne. L’ordre des variables s’en
trouve aussi modifiée.
    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
    
0 0 0 0 0 1 0 0 x22  10
    
0 0 0 0 0 0 1 1 x12  60
1 0 0 1 0 0 0 0 x24  = 30
    
    
0 0 1 1 0 0 0 0 x34  50
    
0 1 1 0 1 0 0 0 x44  80
0 0 0 0 1 1 1 0 x45 80

33 / 52
 Théorème de triangularité de base : illustration

Nous continuons en permutant la troisième et la sixième colonne.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
   
 
0 0 1 0 0 0 0 0  x34  10
   

0 0 0 0 0 0 1 1  x12  = 60
   

1 0 0 1 0 0 0 0  x24  30
   

0 0 0 1 0 1 0 0  x22  50
   

0 1 0 0 1 1 0 0 x44  80

0 0 1 0 1 0 1 0 x45 80

34 / 52
 Théorème de triangularité de base : illustration

Permutons à présent la cinquième et la quatrième ligne.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
   
 
0 0 1 0 0 0 0 0  x34  10
   

1 0 0 1 0 0 0 0  x12  = 30
   

0 0 0 0 0 0 1 1  x24  60
   

0 0 0 1 0 1 0 0  x22  50
   

0 1 0 0 1 1 0 0 x44  80

0 0 1 0 1 0 1 0 x45 80

35 / 52
 Théorème de triangularité de base : illustration

Permutons à présent la sixième et la cinquième ligne.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
   
 
0 0 1 0 0 0 0 0  x34  10
   

1 0 0 1 0 0 0 0  x12  = 30
   

0 0 0 1 0 1 0 0  x24  50
   

0 0 0 0 0 0 1 1  x22  60
   

0 1 0 0 1 1 0 0 x44  80

0 0 1 0 1 0 1 0 x45 80

36 / 52
 Théorème de triangularité de base : illustration

Nous devons permuter la cinquième et la sixième colonnes.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
   
 
0 0 1 0 0 0 0 0  x34  10
   

1 0 0 1 0 0 0 0  x12  = 30
   

0 0 0 1 1 0 0 0  x22  50
   

0 0 0 0 0 0 1 1  x24  60
   

0 1 0 0 1 1 0 0 x44  80

0 0 1 0 0 1 1 0 x45 80

37 / 52
 Théorème de triangularité de base : illustration

Permutons à présent la sixième et la septième lignes.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
   
 
0 0 1 0 0 0 0 0  x34  10
   

1 0 0 1 0 0 0 0  x12  = 30
   

0 0 0 1 1 0 0 0  x22  50
   

0 1 0 0 1 1 0 0  x24  80
   

0 0 0 0 0 0 1 1 x44  60

0 0 1 0 0 1 1 0 x45 80

38 / 52
 Théorème de triangularité de base : illustration

Enfin, nous permutons à présent la septième et la dernière lignes.

    
1 0 0 0 0 0 0 0 x11 10
0 1 0 0 0 0 0 0 x23  20
    
0 0 1 0 0 0 0 0  x34  10
   

1 0 0 1 0 0 0 0  x12  = 30
   

0 0 0 1 1 0 0 0  x22  50
   

0 1 0 0 1 1 0 0 x24   80
   

0 0 1 0 0 1 1 0 x44  80
0 0 0 0 0 0 1 1 x45 60

Comme nous n’avons fait que des permutations, nous avons le

même système d’équations qu’au départ.

39 / 52
 Solutions entières

Puisque n’importe quelle matrice de base est triangulaire, il suit

que le processus de substitution en arrière impliquera simplement
des additions et des soustractions de lignes et de colonnes. Aucune
multiplication n’est requise.

Il suit que si les lignes et les colonnes originales sont entières, les
valeurs de toutes les variables de base sont entières.

40 / 52
 Application du simplexe
Idée : exploiter le fait que les bases sont triangulaires.

On va décomposer le vecteur des multiplicateurs du simplexe en

écrivant
λ = (u, v )
ui est associé à la i e contrainte de ligne, et vj à la j e contrainte de
colonne. Une contrainte étant redondante, on peut associer une
valeur arbitraire à un des multiplicateurs. On va poser vn = 0.

Etant donnée une base B, nous allons développer l’équation

λT B = cBT .
Si xij est dans la base, la colonne correspondante de A (et donc de
B) aura exactement deux entrées égales à +1 (les autres sont
nulles), à la i e place de la portion supérieure, et la j e place de la
portion inférieure.
41 / 52
 Application du simplexe
Dès lors, le produit
λT ai = cij
va donner
ui + vj = cij .
Rappelons que nous avons posé vn = 0. Partant de là, nous
pouvons déterminer toutes les valeurs ui et vj par substitution. De
plus, nous avons le résultat suivant.

Théorème 1
Si les coûts cij d’un problème de transport sont tous entiers,
alors (en supposant qu’un multiplicateur du simplexe est posé ar-
bitrairement comme égal à un entier fixé), les multiplicateurs du
simplexe associés à n’importe quelle base sont entiers.

42 / 52
 Multiplicateurs du simplexe
De
rDT = cDT − λT D,
nous avons
(
cij − ui − vj si xij est hors base,
rij =
0 si xij est variable de base.

On peut facilement calculer les coûts réduits en considérant le

tableau
c11 c12 c13 ... c1n u1
c21 c22 c23 ... c2n u2
.. .. .. .. .. ..
. . . . . .
cm1 cm2 cm3 ... cmn um
v1 v2 v3 ... vn

43 / 52
 Multiplicateurs du simplexe

Étape 1 Affecter une valeur arbitraire à un des multiplicateurs.

Étape 2 Sélectionner un cij associé à une variable de base xij
pour lequel soit ui , soit vj n’a pas encore été
determiné, mais l’un des deux multiplicateurs a une
valeur connue.
Étape 3 Calculer le multiplicateur inconnu à partir de
l’équation
cij = ui + vj .
Si tous les multiplicateurs ont été déterminés, arrêt.
Sinon, retour à l’étape 2.

44 / 52
 Exemple
En reprenant l’exemple précédant, et en posant (arbitrairement)
v5 = 0
3 4 6 8 9 x
2 2 4 5 5 x
2 2 2 3 2 x
3 3 2 4 2 x
x x x x 0
On parcourt alors le tableau à la recherche d’un élément dont un
seul multiplicateur est inconnu. Il s’agit ici de l’élément inférieur
droit, ce qui donne
3 4 6 8 9 x
2 2 4 5 5 x
2 2 2 3 2 x
3 3 2 4 2 2
x x x x 0
45 / 52
 Exemple

En continuant de la sorte, nous obtenons le tableau

3 4 6 8 9 5
2 2 4 5 5 3
2 2 2 3 2 1
3 3 2 4 2 2
-2 -1 1 2 0

46 / 52
 Expression des colonnes hors base

Théorème 2
Soit B une base de A (en ignorant une ligne) et soit d une
colonne hors-base de A. Si y = B −1 d, alors yi ∈ {−1, 0, +1},
i = 1, . . . , n.

• Lorsqu’une unité d’une nouvelle variable est ajoutée, les

variables de base actuelles changeront chacune de +1, −1, ou
0.
• Si la nouvelle variable a une valeur θ, les variables de base
change de +θ, -θ, ou 0. Il suffit donc de déterminer les signes
de changement.
• Cela revient à redistribuer les flux sur le réseau.

47 / 52
 Échange de variables : exemple
Considérons le tableau où le + indique que nous faisons entrer la
variable x53 .

100 10
20− 10+ 30
20+ 100 30− 60
100 10
10− + 400 50
40 10 30 40 40

En déterminant quelles lignes/colonnes n’ont qu’une entrée dont le

signe de changement n’est pas déterminé, nous voyons que l’ordre
de considération des variables est x13 , x23 , x25 , x35 , x32 , x31 , x41 ,
x51 , x54 .
La plus petite variable avec le signe moins est x51 = 10, aussi
θ = 10.
48 / 52
 Algorithme
Nous sommes à présent en mesure de décrire l’algorithme complet.
Étape 1 Calculer une solution réalisable de base initiale à
l’aide de la règle du coin nord-ouest ou une autre
méthode.
Étape 2 Calculer les multiplicateurs du simplexe et les
coefficients de coût relatifs. Si les coefficients de coût
relatifs sont non négatifs, arrêt : la solution est
optimale. Autrement, passer à l’étape 3.
Étape 3 Sélectionner une variable hors base de coût réduit
négatif pour entre la base. Calculer le cycle de
changement et poser la valeur de la variable à la plus
petite variable de base avec un moins qui lui est
attribuée. Mettre à jour la solution. Retour à l’étape
2.

49 / 52
 Exemple : coûts réduits
Repartons de l’exemple de départ. Le tableau des multiplicateurs
du simplexe donnait
3 4 6 8 9 5
2 2 4 5 5 3
2 2 2 3 2 1
3 3 2 4 2 2
-2 -1 1 2 0
Les coûts réduits sont obtenus en calculant rij = cij − ui − vj ,
menant au tableau.
0 0 0 1 4 5
1 0 0 0 2 3
4 2 0 0 1 1
3 2 -1 0 0 2
-2 -1 1 2 0
50 / 52
 Exemple : échange de variables

Il y a un seul coût réduit négatif, et donc nous faisons entrer x43

dans la base, en utilisant le tableau ci-dessous.

10 20 30
30 20− 30+ 80
100 10
+ 40− 200 60
10 50 20 80 20

Note : on peut s’arrêter dès qu’un cycle est déterminé.

51 / 52
 Exemple : échange de variables

La plus petite variable de base avec le signe moins est x23 = 20.
Nous échangeons donc x43 et x23 pour obtenir

10 20 30
30 50 80
10 10
20 20 20 60
10 50 20 80 20

52 / 52
 Exemple : coûts réduits
Nous calculons d’abord les multiplicateurs associées à la nouvelle
base.
3 4 6 8 9 5
2 2 4 5 5 3
2 2 2 3 2 1
3 3 2 4 2 2
-2 -1 0 2 0
Les coûts réduits sont
0 0 1 1 4 5
1 0 1 0 2 3
3 2 1 0 1 1
3 2 0 0 0 2
-2 -1 0 2 0
Aucun coûts réduits négatif : la solution est optimale.
53 / 52