CHAPITRE III: L’Algorithme du simplexe

Dans la vie de toute entreprise, les managers sont appelés à prendre des décisions de choix
entre plusieurs alternatives qui leur permettent d’atteindre certains objectifs : maximiser leurs
profits ou minimiser leurs coûts, et ce en tenant compte d’un certain nombre de contraintes
auxquelles l’entreprise est soumise.
En général, le problèmes auxquels ils sont confrontés, consistent à répartir des ressources
(par exemple de l’argent, des matières premières, de la main d’œuvre, etc.) entre différentes unités
économiques de telle sorte que la marge soit la plus grande possible, ou bien le coût total soit le plus
petit possible.
La programmation linéaire a pour objet de déterminer la meilleure des solutions qui satisfont
aux contraintes de ces problèmes.
La méthode dite du simplexe, exposée en 1947 par l’Américain DANTZIG Georges Bernard
est une technique à la fois fondamentale et très populaire pour résoudre les problèmes de
programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur n variables réelles,
l'algorithme du simplexe permet de trouver la solution optimale pour une fonction objective, qui est
elle aussi linéaire

Dans ce chapitre, on présentera d’abord le principe de cette méthode, ensuite on l’appliquera

à des exemples concrets.

La méthode du simplexe donc, consiste à trouver un premier programme de base puis à

construire une suite de programmes de base améliorant constamment la fonction économique (ou
objectif) et donc conduisant à l’optimum.

I-Principe de l’algorithme du simplexe :

Le principe de l’algorithme est le suivant :
1. Déterminer une première solution de base réalisable ;
2. Cheminer de solution de base réalisable en solution de base réalisable en augmentant à
chaque itération la valeur de la fonction objective ;
3. Arrêter la procédure lorsqu’il n’est plus possible d’accroitre la valeur de la fonction
objective ; la dernière solution de base réalisable obtenue est dés lors solution optimale.
Lorsque l’ensemble polyédrique convexe des solutions réalisable est borné, la même procédure
est appliquée .Dans ce cas l’algorithme permet de voir si la solution optimale est finie ou non
 I- Le tableau simplexe :
La résolution d’un programme linéaire par la méthode du simplexe est généralement présentée
sous forme de tableaux simplexes successifs.
Le premier tableau simplexe reprend les éléments du problème sous la forme standard c'est-à-dire
Contraintes mises sous forme d’égalité et fonction objective.
Le tableau de simplexe initial
On utilise la terminologie suivante.
Solution : tout n- uple satisfait à (1)
Solution réalisable : toute solution satisfaisant (2)
Base : tout ensemble de m variable prises parmi x1 , x2 , … , xn tel que le déterminant des
coefficients aij associés à ces m variables soit différent de 0 (autrement dit, les vecteurs Pj
associés à ces m variables forment une base de l’espace à m dimensions des contraintes).
Solution de base : toute solution comprend n − m variables nulles, et telle que les m autres
variables forment une base. On parle alors, respectivement, de variable de (en) base et de
variables hors base.
Notons que pour obtenir une solution de base, on annule n − m variables et on recherche les
valeurs des m autres variables en résolvant un système de Cramerm × m.
Solution de base réalisable (SBR) : toute solution de base satisfaisant à (2)
Solution optimale : toute solution réalisable qui optimise Z.

Exemple : Problème de maximisation :

On considère le programme linéaire P: AX≤b
C X = Z(Max)
X ≥0

Pour pouvoir appliquer l’algorithme du simplexe au programme P, il faut que les conditions
suivantes soient vérifiées :
AJ : Matrice unité à permutation près des colonnes.
J : base ; b≥0 ; CJ=0
A b
(0) Soit la matrice des coefficients :
C 0

(1) Si le CJ≤0, alors cette solution de base est optimale, on arrête le traitement.

(2) Si CJ >0, alors trouver s (numéro de colonne) tel que Cs = Max C j

j∈ J
S’il en existe plusieurs, choisir l’un d’eux.
(3) Choisir r (numéro de la ligne) tel que :

br  bi 
=Min  s
/ Ai
s
> 0 
Ars  Ai 

Si tous les A i ≤0, alors on arrête le traitement et le problème n’admet pas de solution
optimale.

(4)- Si r existe, alors : X s va rentrer dans la base et la variable correspondante qui se trouve sur
la ligne r va sortir.

(5)- Ensuite, on complète les calculs par :

- Mettre 0 sur la colonne s et 1 dans la ligne A rs ;

- Diviser la ligne r par A rs ;

- Recopier les colonnes de la base restante.
Ais . Arj
X ij * = X ij -
Ars

C s .br
Z* = Z -
Ars
Ceci est une itération du simplexe, puis, on reprend l’étape (1), et on refait les mêmes étapes
jusqu’à l’arrêt :
o Soit on trouve une solution optimale.
o Soit le problème n’admet pas une solution optimale.
Afin de mieux comprendre les différentes approches théoriques de la méthode du simplexe,
nous allons donner des exemples numériques ou elles seront successivement utilisées.
Les premiers exemples seront détaillés tandis que seule la solution des autres sera donnée
afin qu’ils puissent servir d’exercices.
 Etude de cas

Une entreprise pouvant fabriquer trois produits P 1 , P 2 et P 3 en utilisant une ligne de production
travaillant jusqu’à 450 heures par semaine dégage pour chaque unité de produit un profit : de 40
n.m. pour P 1 , 120 n.m. pour P 2 et 30 n.m. pour P 3 .
La capacité de production de la ligne utilisée est respectivement de 500, 250 et 750 unités par heure
pour les trois produits.
Une étude de marché a montré que les possibilités de vente ne dépassent pas 10000 unités de P 1 ,
5000 unités de P 2 et 15000 unités de P 3 .
Le problème qui se pose est de répartir la capacité de production entre les trois produits, de manière
à maximiser le profit hebdomadaire.

Formulation du problème en un PL :
Mettons le problème sous forme algébrique.
Appelons x 1 , x 2 et x 3 les quantités respectives des produits P 1 , P 2 et P 3 que nous avons à fabriquer
pour maximiser le profit. Ces quantités ne doivent pas dépasser respectivement 10000, 5000 et
15000 par semaine. Ce qui permet d’écrire :
x 1 ≤10000
x 2 ≤5000
x 3 ≤15000

D’autre part, le temps employé pour produire x 1 unités de P 1 est en heures : x 1 ×1/500 R R R R R R

Celui qui correspond à la fabrication de x 2 unités de P 2 est en heures : x 2 ×1/250 et enfin pour R R R R R R

produire x 3 unités de P 3 est : x 3 ×1/750

R R R R R R

La somme des temps de fabrication ne doit pas dépasser 45 h, disponibilité totale de la

machine. On aura donc :
1 1
x1 + 1 x2R R R
+
R R x 3 ≤ 450 R R

50 25 R
75

Cette contrainte peut être réécrite comme suit :

3x 1 + 6x 2 + 2x 3 ≤67500
R R R R R R

De plus, du fait la non négativité des quantités produites, on a les contraintes suivantes :
x 1 ≥0, x 2 ≥0, x 3 ≥0
R R R R R R

L’objet du problème est de choisir x 1 , x 2 et x 3 de manière à ce que le profit soit maximal, le profit R R R R R R R R R R

étant égal à 40x 1 + 120 x 2 +30 x 3 unités monétaires.

R R R R R R
 Ainsi, le programme linéaire peut être écrit comme suit :
Max Z= 40x 1 + 120 x 2 +30 x 3
S/C:
x1 ≤10000
x2 ≤5000
x 3 ≤15000

30x 1 + 60x 2 + 20x 3 ≤67500

x 1 ≥0, x 2 ≥0, x 3 ≥0

Mise sous forme standard

Transformer le PL en forme standard consiste à introduire des variables d’écarts pour chaque
contrainte de manière a réécrire les inégalités ≤ sous la forme d’égalités =
Chacune de ces variables d’écart représente le nombre de ressources non utilisés .

S/C:
x 1 + + x4 = 10000
x2 + x5 = 5000
x3 + x6 = 15000
30x 1 + 60x 2 + 20x 3 + x 7 = 67500
x 1 , x 2 , x 3 , x 4, x 5 , x 6, x 7 ≥ 0

La fonction objective ne change pas

Max Z= 4x 1 + 12 x 2 +3 x 3
Solution de base est :
X 4 =10 000, X 5 = 5000, X 6 = 15000, X 7 =67500

x 1 =x 2 =x 3 =0 , Z=0
Donc Solution de base réalisable
Reprenons ce programme sous forme de tableau :

X1 X2 X3 X4 X5 X6 X7 bi
X4 1 0 0 1 0 0 0 10000
X5 0 1 0 0 1 0 0 5000
X6 0 0 1 0 0 1 0 15000
X7 3 6 2 0 0 0 1 67500
C j 40 120 30 0 0 0 0 0

La base est constituée des vecteurs : X 4 , X 5 , X 6 et X 7

Variable Hors Base(VHB)=0 Variable de Base (VB)

X 4= 10 000
x 1 =0 X 5= 5 000
x 2 =0
x 3 =0 X 6 = 15 000
X 7 = 67 500
Z=0
Le plus grand coefficient positif de Z est 120, celui qui correspond à X 2 :
C’est donc A 2 que nous allons faire entrer dans la base.

- Nous rapportons les éléments de b à ceux de X 2 , et choisissons le plus petit rapport positif, qui est
b 2 /a 22 égal à 5000.
C’est donc le vecteur X 5 correspondant à la ligne 2 que nous allons faire sortir de la base.
L’élément a 22 et le pivot de la transformation qu’implique la sortie de X 5 de l’ancienne base, et
l’entrée de X 2 dans la nouvelle.
Pour déterminer les nouveaux éléments du tableau, nous appliquons les ce qui suit :
- Mettre 0 sur la colonne 2 et 1 à la place de l’élément a 22 ;
- Diviser la ligne 2 par a 22 ;
- ²Recopier les colonnes de la base restante en utilisant les formules :
Ai2 . A2 j
X ij * = X ij -
A22

C 2 .b2
Z* = Z -
A22
Ceci permet d’avoir le tableau suivant :

X1 X2 X3 X4 X5 X6 X7 bi
X4 1 0 0 1 0 0 0 10000
X2 0 1 0 0 1 0 0 5000
X6 0 0 1 0 0 1 0 15000
X7 3 0 2 0 -6 0 1 67500
cj 40 0 30 0 -120 0 0 60000

La nouvelle solution est donc:

x 1 =0
x 2 =5000
x 3 =0
Z=60000

Poursuivons l’algorithme.
Au 2ème pas, le pivot est b 11 =1.
En appliquons les mêmes étapes de l’itération précédente, nous obtenons le tableau :

X1 X2 X3 X4 X5 X6 X7 bi
X1 1 0 0 1 0 0 0 10000
X2 0 1 0 0 1 0 0 5000
X6 0 0 1 0 0 1 0 15000

X7 0 0 2 -3 -6 0 1 7500

cj 0 0 30 -40 -120 0 0 100000

La nouvelle solution est :

x 1 =10000
x 2 =5000
x 3 =0
Z=100 000
Au 3ème pas, le pivot est b 43 =2, ce qui donne le tableau suivant :

X1 X2 X3 X4 X5 X6 X7 bi
X1 1 0 0 1 0 0 0 10000
X2 0 1 0 0 1 0 0 5000
X6 0 0 0 3/2 3 1 -1/2 11250
X3 0 0 1 -3/2 -3 0 1/2 3750
cj 0 0 0 1/2 -30 0 -3/2 111250
La nouvelle solution est :
x 1 =10000
x 2 =5000
x 3 =3750
Z=111 250
Enfin, le pivot est b 34 =3/2 , ce qui donne le tableau suivant :

X1 X2 X3 X4 X5 X6 X7 bi
X1 1 0 0 0 -2 -2/3 1/3 2500
X2 0 1 0 0 1 0 0 5000
X4 0 0 0 1 2 2/3 -1/3 7500
X3 0 0 1 0 0 1 0 15000
cj 0 0 0 0 -40 -1/3 -4/3 115000

La nouvelle solution est : Z=115 000

x 1 =2500
x 2 =5000
x 3 =15000

Cette solution est optimale car tous les Cj sont négatifs ou nuls.
Exemple

Nous supposerons le problème écrit sous forme de la maximisation de la fonction objectif.

Soit le programme linéaire suivant :

𝑀𝑀𝑀𝑀𝑀𝑀(𝑍𝑍) = 9𝑋𝑋1 + 7𝑋𝑋2

10𝑥𝑥1 + 5𝑥𝑥2 ≤ 50
(𝐷𝐷) �
6𝑥𝑥1 + 6𝑥𝑥2 ≤ 36
45𝑥𝑥1 + 18𝑥𝑥2 ≤ 81
𝑥𝑥1 ≥ 0, 𝑥𝑥2 ≥ 0

Nous allons d’abord introduire les variables d’écart

– 𝑥𝑥3 , 𝑥𝑥4 𝑒𝑒𝑒𝑒 𝑥𝑥5 à𝑓𝑓𝑓𝑓𝑓𝑓 𝑑𝑑𝑑𝑑 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑛𝑛𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖é𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔é𝑠𝑠 𝑜𝑜𝑜𝑜 é𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔é𝑠𝑠 𝑒𝑒𝑒𝑒 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
𝑙𝑙𝑙𝑙 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑒𝑒𝑒𝑒 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠, 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 :
Mise sous Forme standard :
10𝑥𝑥1 + 5𝑥𝑥2 + 𝑥𝑥3 = 50
6𝑥𝑥1 + 6𝑥𝑥2 + 𝑥𝑥4 = 36
45𝑥𝑥1 + 18𝑥𝑥2 + 𝑥𝑥5 = 81
𝑀𝑀𝑀𝑀𝑀𝑀(𝑍𝑍) = 9𝑋𝑋1 + 7𝑋𝑋2 + 0𝑋𝑋3 + 0𝑋𝑋4 + 0𝑋𝑋5
Solution de base
VHB=0 VB

𝑥𝑥1 = 0 𝑥𝑥3 = 0 𝑍𝑍 = 0 solution de base réalisable

𝑥𝑥2 = 0 𝑥𝑥4 = 36
𝑥𝑥5 = 18

x1 x2 x3 x4 x5 bi Ratios

x3 10 5 1 0 0 50 50�10
x4 6 6 0 1 0 36 36�6
𝑥𝑥5 45 18 0 0 1 81 81�45
𝐶𝐶𝑗𝑗 − 𝑍𝑍 9 7 0 0 0 0
↓ 𝑐𝑐𝑐𝑐
 x1 x2 x3 x4 x5 bi Ratios
x1 1 1 1 0 0 5 8
�1�
2 10 2
x4 0 3 −6 1 0 6 6�
3
10
𝑥𝑥5 0 15,75 -0,45 0 1 58,5 58,5�
15,75
𝐶𝐶𝑗𝑗 − 𝑍𝑍 0 5 ↑ 𝑐𝑐𝑐𝑐 −9 0 0 0
2 10

x1 x2 x3 x4 x5 bi
x1 1 0 2 −1 0 4
10 6
x4 0 1 −2 1 0 2
10 3
𝑥𝑥5 0 0 -2,7 -5,25 1 27
𝐶𝐶𝑗𝑗 − 𝑍𝑍 0 0 −4 −5 0 -50
10 6
Tous les Cj ≤ donc c ′ est la solution optimale: 𝑍𝑍 = 50
𝑥𝑥1 = 4 𝑥𝑥3 = 0
𝑥𝑥2 = 2 𝑥𝑥4 = 0
𝑥𝑥5 = 27
 L’application de la méthode du simplexe à la résolution des programmes linéaire suppose
La connaissance préalable d’une solution de base réalisable (initiation)
Lorsque cette dernière c'est-à-dire la solution initiale ne peut s’obtenir, on peut avoir recours à deux
méthodes :

La méthode M (Big M)
La méthode en deux phases
Reposent sur l’introduction de variables artificielles, qui permettent d’avoir une solution de base
réalisable de départ.

METHODE M (Big M)
Cette méthode permet de tenir compte des variables artificielles. On les pénalise en leur
affectant un coefficient de valeur très élevée dans la fonction économique (- M pour un problème à
maximum, + M pour un problème à minimum). Les pénalités ont pour objet de provoquer
l’élimination des variables artificielles au fil des itérations. Normalement, à l'optimum (s'il existe)
les variables artificielles sont hors base. Si celles-ci sont à l'optimum dans la base, avec une valeur
non nulle, le programme n'a pas de solution.

Exemple de résolution : Problème de minimisation

Soit le PL suivant :
Min Z = 10 x 1 + 22 x 2
S/c
x 1 + x 2 ≥ 20
3x 1 + 5x 2 ≥ 75
x 1 + 3x 2 ≥ 30

Mise sous Forme standard

x1 + x2 – x3
3x 1 + 5x 2
R R R R - x4R R = 75
x 1 + 3x 2
R R R R -x 5 = 30
R R

Matricielle ment, le programme s’écrit:

Min Z = 10 x 1 + 22 x 2
R R R R

s/c
U

1 1 −1 0 0 x1
x2 20
3 5 0 −1 0 . x3 = 75
1 3 0 0 −1 x4 30
x5
 Il n’y a pas de solution réalisable de base afférente à cause des variables : x 3 , x 4 , x 5 qui son
affectées de signes négatifs.
On introduit alors des variables artificielles positive : x 6 , x 7 , x 8 dans les 3 équations, ce qui
donne :
x1 + x2 – x3 + v1
3x 1 + 5x 2 R R R R - x4 R R + v2 R R = 75
x 1 + 3x 2 R R R R -x 5 R R +v 3 = 30
R R

Le nouveau programme s’écrit donc :

Min Z = 10 x 1 + 22 x 2 R R R R

s/c
U

x1
x2
1 1 −1 0 0 1 0 0 x3 20
3 5 0 −1 0 0 1 0 . x4 = 75
x5
1 3 0 0 −1 0 0 1 30
V1
v2
v3

Les variables de base sont les variables artificielles.

Les variables hors base sont les variables principales et les variables d’écart.
Les variables artificielles constituant une sur estimation, on procède donc à la pénalisation de la
fonction objective Z, comme suit :

Soit Z* la fonction objectif pénalisée.

Min Z* = 10 x 1 + 22 x 2 +M ( v 1 + v 2 + v 3 ) R R R R R R R R R R

M : coefficient très grand.

= 20en fonction des variables principales et des variables d’écart :

On écrit les variables artificielles
v 1 = 20- x 1 - x 2 + x 3
R R R R R R R R

v 2 = 75- 3x 1 - 5x 2 + x 4
R R R R R R R

v 3 = 30- x 1 - 3x 2 +x 5
R R R R R R R

On remplace ces valeurs dans la fonction objective pénalisée :

Min Z* = 10 x 1 + 22 x 2 +M (v 1+ v 2 + v 3 ) R R R R R R R R R R R

Min Z* = 10 x 1 + 22 x 2 +M (20- x 1 - x 2 + x 3 + 75- 3x 1 - 5x 2 + x 4 + 30- x 1 - 3x 2 +x 5 )

R R R R R R R R R R R R R R R R R R R R R R R

Min Z* = 10 x 1 + 22 x 2 + 20M- Mx 1 - M x 2 + Mx 3 + 75M- 3Mx 1 – 5Mx 2 + Mx 4 + 30M- M x 1

R R R R R R R R R R R R R R R R R

R R – 3Mx 2 +Mx 5 R R R
Min Z* = 10 x 1 + 22 x 2 + 125M - 5Mx 1 - 9M x 2 + Mx 3 + Mx 4 +Mx 5
Min Z* = (10 – 5M) x 1 + (22 – 9M) x 2 + Mx 3 + Mx 4 +Mx 5

La mise en œuvre du tableau de =l’algorithme

20 du simplexe se fait sur le programme linéaire
pénalisé.
Quand les variables artificielles sortiront de la base, leurs valeurs s’annuleront et disparaîtront
de la fonction objective.
A l’optimum, la fonction objective ne doit plus être pénalisée

X1 X2 X3 X4 X5 v1 v2 v3 bi
v1 1 1 -1 0 0 1 0 0 20
v2 3 5 0 -1 0 0 1 0 75
v3 1 3 0 0 -1 0 0 1 30
C j-Z 10-5M 22-9M M M M 0 0 0 -125M

Pour choisir la colonne pivot, on prend: Max {10 − 5M ;22 − 9 M }= 22-9M

Pour choisir la ligne pivot, on prend : Min {20 / 1;75 / 5;30 / 3}= 30/3
Le pivot est donc l’élément 3, en effectuant les calculs :
Ais . Arj C s .br
X ij * = X ij - ; Z* = Z - ,
Ars Ars

On obtient le tableau suivant :

X1 X2 X3 X4 X5 v1 v2 v3 bi
v1 2/3 0 -1 0 1/3 1 0 -1/3 20
v2 4/3 0 0 -1 5/3 0 1 -5/3 75
X2 1/3 1 0 0 -1/3 0 0 1/3 30
cj 8/3-2M 0 M M 22/3-2M 0 0 3M-22/3 -220-35M

Le pivot est donc l’élément 2/3 , ce qui donne le tableau suivant :

 X1 X2 X3 X4 X5 v1 v2 v3 bi
X1 1 0 -3/2 0 ½ 3/2 0 -1/2 15
v2 0 0 2 -1 1 -2 1 -1 5
X2 0 1 1/2 0 -1/2 -1/2 0 -1/2 5

c j-Z 0 0 4-2M M 6-M 3M-4 0 2M-6 -260-5M

Le pivot est donc l’élément 2, ce qui donne le tableau suivant :

X1 X2 X3 X4 X5 v1 v2 v3 bi
X1 1 0 0 -3/4 5/4 0 3/4 -5/4 75/4
X3 0 0 1 -1/2 ½ -1 1/2 -1/2 5/2
X2 0 1 0 ¼ -3/4 0 -1/4 3/4 15/4

c j-Z 0 0 0 2 4 M M-2 M-4 -270

Tous les éléments C j sont positifs ou nuls, l’optimum est atteint.

Z* = 270
X 1 * = 75/4, X4* = 0
X 2 * = 15/4, v3* = 0
X 3 * = 5/2, v2* = 0
X5* = 0 n v1* = 0
Exemple N°2 :

𝑀𝑀𝑀𝑀𝑀𝑀 (𝑍𝑍) = 5𝑋𝑋1 + 6𝑋𝑋2 + 7𝑋𝑋3

𝑆𝑆/𝐶𝐶
𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 1000
𝑥𝑥 ≤ 300
� 1
𝑥𝑥2 ≥ 150
𝑥𝑥3 ≥ 200

La forme standard :
𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 + 𝑉𝑉1 = 1000 → 𝑉𝑉1 = 1000 − 𝑥𝑥1 − 𝑥𝑥2 − 𝑥𝑥3
𝑥𝑥1 + 𝑥𝑥4 ≤ 300
𝑥𝑥2 − 𝑥𝑥5 + 𝑉𝑉2 = 150 → 𝑉𝑉2 = 150 − 𝑥𝑥2 − 𝑥𝑥5
𝑥𝑥3 + 𝑥𝑥6 + 𝑉𝑉3 = 200 → 𝑉𝑉3 = 200 − 𝑥𝑥3 − 𝑥𝑥6

𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 5𝑥𝑥1 + 6𝑥𝑥2 + 7𝑥𝑥3 + 0𝑥𝑥4 + 0𝑥𝑥5 + 0𝑥𝑥6 + 𝑀𝑀(𝑉𝑉1 + 𝑉𝑉2 + 𝑉𝑉3)
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 5𝑥𝑥1 + 6𝑥𝑥2 + 7𝑥𝑥3 + 𝑀𝑀(1350 − 𝑥𝑥1 − 2𝑥𝑥2 − 2𝑥𝑥3 − 𝑥𝑥5 − 𝑥𝑥6 )
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 5𝑥𝑥1 + 6𝑥𝑥2 + 7𝑥𝑥3 + 1350𝑀𝑀 − 𝑀𝑀𝑥𝑥1 − 2𝑀𝑀𝑥𝑥2 − 2𝑀𝑀𝑥𝑥3 − 𝑀𝑀𝑥𝑥5 − 𝑀𝑀𝑀𝑀6
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = (5 − 𝑀𝑀)𝑥𝑥1 + (6 − 2𝑀𝑀)𝑥𝑥2 + (7 − 2𝑀𝑀)𝑥𝑥3 − 𝑀𝑀𝑥𝑥5 − 𝑀𝑀𝑀𝑀6 + 1350𝑀𝑀
Donc
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = (5 − 𝑀𝑀)𝑥𝑥1 + (6 − 2𝑀𝑀)𝑥𝑥2 + (7 − 2𝑀𝑀)𝑥𝑥3 − 𝑀𝑀𝑥𝑥5 − 𝑀𝑀𝑀𝑀6 + 1350𝑀𝑀
S/C
𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 + 𝑉𝑉1 = 1000𝑥𝑥3
𝑥𝑥1 + 𝑥𝑥4 = 300
𝑥𝑥2 − 𝑥𝑥5 + 𝑉𝑉2 = 150
𝑥𝑥3 + 𝑥𝑥6 + 𝑉𝑉3 = 200
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑥𝑥5 , 𝑥𝑥6 , 𝑉𝑉1, 𝑉𝑉2, 𝑉𝑉3 ≥ 𝑂𝑂

𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 𝑑𝑑𝑑𝑑 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏:

𝑥𝑥1 = 0 𝑉𝑉1 = 1000 𝑍𝑍 = 1350𝑀𝑀

𝑥𝑥2 = 0 𝑥𝑥 = 300 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑑𝑑𝑑𝑑 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 𝑟𝑟é𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎
� 4 �
𝑥𝑥3 = 0 𝑉𝑉2 = 150
𝑉𝑉3 = 200
 x1 x2 x3 x4 x5 x6 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3 bi Ratios
V1 1 1 1 0 0 0 1 0 0 1000 1000�
2
x4 1 0 0 1 0 0 0 0 0 300

𝑥𝑥2 0 1 𝑃𝑃 0 0 -1 0 0 1 0 150 150 ← 𝐿𝐿𝐿𝐿

𝑉𝑉3 0 0 1 0 0 -1 0 0 1 200
𝐶𝐶𝑗𝑗 − 𝑍𝑍 𝑆𝑆 − 𝑀𝑀 6-2M 7-2M 0 -M -M 0 0 0 -1350M
↑ 𝑐𝑐𝑐𝑐

x1 x2 x3 x4 x5 x6 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3 bi Ratios

V1 1 0 1 0 0 0 1 0 850 850
x4 1 0 0 1 0 0 0 0 300
𝑥𝑥2 0 1 0 0 -1 0 0 0 150
𝑉𝑉3 0 0 1 𝑃𝑃 0 0 -1 0 1 200 200 ← 𝐿𝐿𝐿𝐿
𝐶𝐶𝑗𝑗 − 𝑍𝑍 𝑆𝑆 − 𝑀𝑀 0 7 − 2𝑀𝑀 0 6-M -M 0 0 -1050M-900
↑ 𝑐𝑐𝑐𝑐

x1 x2 x3 x4 x5 x6 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3 bi Ratios

V1 1 0 0 0 0 0 1 650 650
x4 1 𝑃𝑃 0 0 1 0 0 0 300 300 ← 𝐿𝐿𝐿𝐿
𝑥𝑥2 0 1 0 0 -1 0 0 150
𝑥𝑥3 0 0 1 0 0 -1 0 200
𝐶𝐶𝑗𝑗 − 𝑍𝑍 𝑆𝑆 − 𝑀𝑀 0 0 0 6-M 7-M 0 +2300-650M
↑ 𝑐𝑐𝑐𝑐

x1 x2 x3 x4 x5 x6 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3 bi Ratios

V1 0 0 0 -1 1 𝑃𝑃 1 1 350 350 ← 𝐿𝐿𝐿𝐿
x1 1 0 0 1 0 0 0 300
x2 0 1 0 0 -1 0 0 150 −150
x3 0 0 1 0 0 -1 0 200
𝐶𝐶𝑗𝑗 − 𝑍𝑍 𝑆𝑆 − 𝑀𝑀 0 0 -5+M 6 − 𝑀𝑀 7-M 0 +3800-350M
↑ 𝑐𝑐𝑐𝑐
 x1 x2 x3 x4 x5 x6 𝑉𝑉1 𝑉𝑉2 𝑉𝑉3 bi
x5 0 0 0 -1 1 1 350
x1 1 0 0 +1 0 0 300
x2 0 1 0 -1 0 0 500
x3 0 0 1 0 0 -1 200
𝐶𝐶𝑗𝑗 − 𝑍𝑍 0 0 0 0 0 -1 -5900

Tous les 𝐶𝐶𝑗𝑗 ≥ 0 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑐𝑐 ′ 𝑒𝑒𝑒𝑒𝑒𝑒 𝑙𝑙𝑙𝑙 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 : 𝑍𝑍 = 1350𝑀𝑀

𝑥𝑥1 = 300 𝑥𝑥4 = 0
𝑥𝑥2 = 500 𝑥𝑥6 = 0
𝑥𝑥3 = 200 𝑉𝑉1 = 0
𝑉𝑉2 = 0
𝑉𝑉3 = 0
Exemple N°3:

Mise sous Forme standard

𝑥𝑥1 + 𝑥𝑥2 + 𝑉𝑉1 = 200 → 𝑉𝑉1 = 200 − 𝑥𝑥1 − 𝑥𝑥2

𝑥𝑥1 + 𝑥𝑥3 = 80
𝑥𝑥2 − 𝑥𝑥4 + 𝑉𝑉5 = 60 → 𝑉𝑉2 = 60 − 𝑥𝑥2 + 𝑥𝑥4
𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , 𝑥𝑥4 , 𝑉𝑉1 , 𝑉𝑉2 ≥ 0 𝑉𝑉1 + 𝑉𝑉2 = 262 − 𝑥𝑥1 − 2𝑥𝑥2 + 𝑥𝑥4

𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 3𝑥𝑥1 + 8𝑥𝑥2 − 𝑀𝑀(𝑉𝑉1 + 𝑉𝑉2 )

𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 3𝑥𝑥1 + 8𝑥𝑥2 − 𝑀𝑀(260 − 𝑥𝑥1 − 2𝑥𝑥2 + 𝑥𝑥4 )
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = 3𝑥𝑥1 + 8𝑥𝑥2 − 260𝑀𝑀 + 𝑀𝑀𝑥𝑥1 + 2𝑀𝑀𝑥𝑥2 − 𝑀𝑀𝑥𝑥4
𝑀𝑀𝑀𝑀𝑀𝑀[𝑍𝑍] = (3 + 𝑀𝑀)𝑥𝑥1 + (8 + 2𝑀𝑀)𝑥𝑥2 − 𝑀𝑀𝑥𝑥4 − 260𝑀𝑀

Solution de base réalisable est:

VHB VB
𝑥𝑥1 = 0 𝑉𝑉1 = 200
𝑥𝑥2 = 0 𝑥𝑥3 = 80
𝑥𝑥4 = 0 𝑉𝑉2 = 60
𝑍𝑍 = 260𝑀𝑀

x1 x2 x3 x4 𝑉𝑉1 V2 bi Ratios
V1 1 1 0 0 1 0 200 200
x3 1 0 1 0 0 0 80
𝑉𝑉2 0 1 𝑝𝑝 0 -1 0 1 60 60 ← 𝐿𝐿𝐿𝐿
𝐶𝐶𝑗𝑗 − 𝑍𝑍 3 + 𝑀𝑀 8 + 2𝑀𝑀 0 -M 0 0 -260M
↑

x1 x2 x3 x4 𝑉𝑉1 V2 bi Ratio
V1 1 0 0 1 1 140 140
x3 1 𝑝𝑝 0 1 0 0 80 80 ← 𝐿𝐿𝐿𝐿
𝑥𝑥2 0 1 0 -1 0 60
𝐶𝐶𝑗𝑗 − 𝑍𝑍 3 + 𝑀𝑀 0 0 −8 + 𝑀𝑀 0 -140M-486
↑
 x1 x2 x3 x4 𝑉𝑉1 V2 bi Ratio
x4 0 0 -1 1 𝑝𝑝 1 60 60 ← 𝐿𝐿𝐿𝐿
x1 1 0 1 0 0 80
𝑥𝑥2 0 1 0 -1 0 60
𝐶𝐶𝑗𝑗 − 𝑍𝑍 0 0 −𝑀𝑀 − 3 −8 + 𝑀𝑀 0 60M-720
↑

x1 x2 x3 x4 𝑉𝑉1 V2 bi
𝑥𝑥4 0 0 -1 1 60
x1 1 0 -1 0 80
𝑥𝑥2 0 1 -1 0 120
𝐶𝐶𝑗𝑗 − 𝑍𝑍 0 0 -5 0 -1200

Tous les 𝐶𝐶𝑗𝑗 ≥ 0 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑐𝑐 ′ 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 : 𝑍𝑍 = 1200

𝑥𝑥4 = 60 𝑥𝑥3 = 0
𝑥𝑥1 = 80 𝑉𝑉1 = 𝑉𝑉2 = 0
𝑥𝑥2 = 120