La méthode du simplexe

Dr [Link] 1
 La méthode du simplexe
Introduction

 La résolution graphique des PL est inapplicable au-delà de deux variables.

 On doit recourir à une autre méthode.

 La méthode du simplexe (de Dantzig) est applicable pour des problèmes de maximisation
dont toutes les contraintes (autres que celles de positivité) sont des inéquations de types ≤ (PL
sous forme canonique).

2
 La méthode du simplexe
Forme standard

 On transforme les inégalités des contraintes en égalités par introduction des variables
supplémentaires positives ou nulles appelées variables d’écart.

PL sous forme canonique PL sous forme standard

Max z = c1 x1 + c2 x2 … + cn xn Max z = c1 x1 + c2 x2 … + cn xn
a11 x1 + a12 x2 … + a1n xn ≤ b1 a11 x1 + a12 x2 … + a1n xn +e1 = b1
a21 x1 + a22 x2 … + a2n xn ≤ b2 a21 x1 + a22 x2 … + a2n xn +e2 = b2
: :
am1 x1 + am2 x2 … + amn xn ≤ bm am1 x1 + am2 x2 … + amn xn +em = bm
x1 ≥ 0 x1 ≥ 0
x2 ≥ 0 x2 ≥ 0
xn ≥ 0 xn ≥ 0
e1 ≥ 0 , e2 ≥ 0 , … e m ≥ 0

3
 La méthode du simplexe
Solution initiale

 Pour démarrer la méthode du simplexe, il est nécessaire d’avoir une solution initiale.

 Dans le cas simple, l’origine et la solution initiale :

( x1 = 0, x2= 0, …, xn= 0 , e1 = b1 , e2 = b2 ,…, em = bm)

 ceci suppose que les bi ne soient pas négatifs pour satisfaire les contraintes de signe.

4
 La méthode du simplexe
Théorème du point extrême

 Le domaine de solutions admissibles du problème a un nombre fini de point extrême et si la

fonction objectif du problème admet un optimum,

 Cet optimum est atteint en l’un des points extrême c’est-à-dire en l’un des sommets du DSA.

 Pour un programme linéaire sur le domaine (T) :

1.) T contient une infinité de solutions mais en nombre fini points extrêmes.

2.) Si la fonction-objectif à optimiser sur le domaine (T) admet un optimum alors cet optimum
est atteint en l’un des points extrêmes.

5
 La méthode du simplexe
Théorème du point extrême

Définition
 Considérons un programme linéaire avec n variables de décisions et m contraintes principales
admettant donc m variables d’écart.

 On appelle point extrême du DSA toute solution (𝑥1,𝑥2,…,𝑥𝑛,𝑒1,𝑒2,…,𝑒𝑚) qui contient au

moins n zéros.

 L’algorithme du simplexe explore uniquement l’ensemble des points extrêmes du domaine de

solutions admissibles du problème.

 Il passe d’un point extrême à un autre en améliorant la valeur de la fonction objectif à chaque
étape jusqu’à ce que l’optimum soit atteint.

6
 La méthode du simplexe
Principe

 La méthode du Simplexe est une méthode algébrique itérative pour la résolution des PL.

 Elle parcoure les sommets du polyèdre convexe jusqu’à ce que la fonction objectif ne puisse
plus être améliorée.

 Elle permet d'améliorer la fonction objectif à chaque itération.

 Le processus se termine lorsque la solution optimale soit atteinte.

 Elle permet de trouver la solution exacte en un nombre fini d’étapes.

7
 La méthode du simplexe
Etapes de la méthode du simplexe pour un problème de maximisation

1. Ecrire un PL du problème

2. Ecrire le PL sous forme standard

3. Déterminer une solution initiale de base

4. Construire le premier tableau de simplexe de la solution initiale de base

5. Choisir une variable entrante dans la base qui a le plus grand effet net positif cj-zj

6. Choisir une variable sortante de la base qui a le plus petit ratio supérieur à zéro.

7. Construire le nouveau tableau :

8
 La méthode du simplexe
Etapes de la méthode du simplexe pour un problème de maximisation

7. Construire le nouveau tableau :

A. Détermination de la colonne-pivot et de la ligne-pivot :
 Colonne-Pivot: On cherche le plus grand coefficient de Z ( V: valeur entrante dans la base)
 Ligne-Pivot: On cherche le plus petit rapport positif non nul =b/VE (VS: valeur sortante de la
base)
 Pivot : Intersection de la ligne pivot et de la colonne pivot

B. Divise la ligne du pivot par le pivot

C. A chacune des variables de base, on associe la valeur 1 à l’intersection de la ligne et de la
colonne relative à cette même variable et dans le reste de la colonne on trouve des zéros.
D. Calculer les valeurs des autres lignes
8. Si tous les coefficients de la F.O pour les variables (hors base) sont négatifs ou nuls, la
solution obtenue est donc optimale. Sinon retourner à l’étape 5.

9
 La méthode du simplexe
Structure d’un tableau du simplexe

 Soit (P) un programme linéaire à n variable de décision et m variable d’écart (contrainte)

(il y aura m+n+2 colonne)
 Autant de ligne que de contrainte principale +2
 On continue les itérations tant qu’il existe un réel strictement positif sur la ligne de la
fonction économique (z). PL sous forme standard
Max z = c1 x1 + c2 x2 … + cn xn
a11 x1 + a12 x2 … + a1n xn +y1 = b1
a21 x1 + a22 x2 … + a2n xn +y2 = b2
:
am1 x1 + am2 x2 … + amn xn +ym = bm ais sont les
x1 ≥ 0
x2 ≥ 0
éléments de la
xn ≥ 0 colonne pivot
e1 ≥ 0 , e2 ≥ 0 , e3 ≥ 0

VB e1 e2 … em
y1
y2
...
ym
10
 La méthode du simplexe
Méthode

Mise à jour du tableau

- Les lignes correspondantes à la fonction objectif et aux titres resteront inchangées dans le nouveau tableau.

 Toutes les autres valeurs faudra les calculer comme suit :

 Dans la ligne d'élément pivot de chaque nouvel élément est calculée en tant que:

Élément ligne pivot = Élément ancienne ligne pivot / Pivot

 Dans les lignes restantes chaque élément est calculé:

Nouvel élément ligne =
Élément ancienne ligne - (Élément ancienne ligne en colonne pivot/pivot) * Nouvel élément ligne
pivot

- De cette façon, on atteint que tous les éléments de la colonne de la variable entrante sont nuls sauf celui
de la ligne de la variable sortante dont la valeur est 1.
(Ceci est analogue à utiliser la méthode de Gauss-Jordan pour la résolution des systèmes d'équations
linéaires).

11
 La méthode du simplexe
Méthode

 Le processus de résolution est le suivant :

1. Le problème est écrit sous forme standard.
2. Une solution est trouvée.
3. Trouver la colonne du pivot.
4. Trouver la ligne du pivot et effectuer la méthode de Gauss
5. STOP. Solution optimale trouvée ou pas de solution possible.

12
 La méthode du simplexe
Exemple

Max 100x1 + 200x2

s. c x1 + x2 ≤ 150 (1)
4x1 + 2x2 ≤ 440 (2)
x1 + 4x2 ≤ 480 (3)
x1 ≤ 90 (4)
x1, x2 ≥0 (5)

13
 La méthode du simplexe
Exemple : Mise sous forme standard

Max 100x1 + 200x2 Max 100x1 + 200x2

s. c x1 + x2 ≤ 150 (1) s. c x1 + x2 + e1 = 150 (1)
4x1 + 2x2 ≤ 440 (2) 4x1 + 2x2 + e2 = 440 (2)
x1 + 4x2 ≤ 480 (3) x1 + 4x2 + e3 = 480 (3)
x1 ≤ 90 (4) x1 + e4 = 90 (4)
x1, x2 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5)

14
 La méthode du simplexe
Exemple : Solution de base

 Simplexe nécessite la connaissance d'une solution initiale réalisable de base, au départ.

 On considère la solution réalisable de base avec x1 = 0 et x2 = 0 ( Point extrême de l’ensemble des
solutions réalisables qui est l’origine O).

Max 100x1 + 200x2

s. c x1 + x2 + e1 = 150 (1)
4x1 + 2x2 + e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3)
x1 + e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5)

Max 100x1 + 200x2 Max 100x1 + 200x2

s. c e1 = 150 - x1 - x2 (1) s. c e1 = 150 (1)
e2 = 440 - 4x1 - 2x2 (2) e2 = 440 (2)
e3 = 480 - x1 - 4x2 (3) e3 = 480 (3)
e4 = 90 - x1 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5)

15
 La méthode du simplexe
Exemple : Solution de base

 On considère la solution réalisable de base avec x1 = 0 et x2 = 0 ( Point extrême de l’ensemble des

solutions réalisables qui est l’origine O).
Max 100x1 + 200x2 Max 100x1 + 200x2
s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3)
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5)

Solution réalisable Générer Solution réalisable Solution

de base qui augmente la F.O optimale

Générer

16
 La méthode du simplexe
Exemple : Tableau de simplexe initial de la forme standard

Le tableau initial de la méthode du simplexe est composé par tous les coefficients des variables de décision
du problème original et les variables d’écart).

Max 100x1 + 200x2 Max 100x1 + 200x2

s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3)
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5)
Variables hors bases
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
4 lignes e3 1 4 0 0 1 0 480
(nb contraintes m)
e4 1 0 0 0 0 1 90
Z 100 200 0 0 0 0 0
Coefficients Solution
17
 La méthode du simplexe
Exemple : Variable entrante dans la base
 Choisir une variable hors base qui a le plus grand coefficient positif dans la ligne z.
Var
Max 100x1 + 200x2 Max 100x1 +200x2 Var de bases
x1 x2 e1 e2 e3 e4 bi
s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
e1 1 1 1 0 0 0 150
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3) e2 4 2 0 1 0 0 440
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5) e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100 200 0 0 0 0 0
Variable entrante
Variables hors bases
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100 200 0 0 0 0 0
Solution
Colonne du
18
pivot
 La méthode du simplexe
Exemple : Variable sortante de la base
 Choisir une variable de base qui a le plus grand coefficient positif dans la ligne z.
Var
Max 100x1 + 200x2 Max 100x1 +200x2 Var de bases
x1 x2 e1 e2 e3 e4
s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
e1 1 1 1 0 0 0 150
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3) e2 4 2 0 1 0 0 440
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5) e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100 200 0 0 0 0 0
Variable sortante Variable entrante
Variables hors bases
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi bi/aic
e1 1 1 1 0 0 0 150 150/1= 150
e2 4 2 0 1 0 0 440 440/2=220
e3 1 4 0 0 1 0 480 480/4=120
Plus petite
e4 1 0 0 0 0 1 90 90/0= +∞ valeur positive

Z 100 200 0 0 0 0 0
Solution
Ligne du Colonne du
19
pivot (l =3) pivot(c=2)
 La méthode du simplexe
Exemple : Déterminer le pivot
 Le pivot est l’intersection de la ligne du pivot et la colonne du pivot (pivot = aic)
Var
Max 100x1 + 200x2 Max 100x1 +200x2 Var de bases
x1 x2 e1 e2 e3 e4 bi
s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
e1 1 1 1 0 0 0 150
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3) e2 4 2 0 1 0 0 440
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5) e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Le pivot
Z 100 200 0 0 0 0 0

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100 200 0 0 0 0 0
Solution
Ligne du Colonne du
pivot (l =1) 20
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
1. Divise la ligne du pivot par le pivot (pivot = aic)
Var
Max 100x1 + 200x2 Max 100x1 +200x2 Var de bases
x1 x2 e1 e2 e3 e4 bi
s. c x1 + x2 + e1 = 150 (1) s. c e1 = 150 (1)
e1 1 1 1 0 0 0 150
4x1 + 2x2 + e2 = 440 (2) e2 = 440 (2)
x1 + 4x2 + e3 = 480 (3) e3 = 480 (3) e2 4 2 0 1 0 0 440
x1 + e4 = 90 (4) e4 = 90 (4)
x1, x2, e1, e2, e3, e4 ≥0 (5) x1, x2, e1, e2, e3, e4 ≥0 (5) e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
alj / alc Z 100 200 0 0 0 0 0
1/4=1/4
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 a31 / alc  1/4 =1/4
e2 a32 / alc  4/4=1
a33 / alc  0/4=0
x2 1/4 1 0 0 1/4 0 120 0/4=0
e4 1/4 =1/4
0/4=0
Z
Solution
Ligne du Colonne du
pivot (l =3) 21
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Déterminer les coefficients des variables de base
A chacune des variables de base, on associe la valeur 1 à l’intersection de la ligne et de la
colonne relative à cette même variable et dans le reste de la colonne la valeur 0 .
Var
Var de bases x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 0 1 0 0
e2 0 0 1 0
x2 1/4 1 0 0 1/4 0 120
e4 0 0 0 1
Z 0 0 0 0
Solution
Ligne du Colonne du
pivot (l =3) 22
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Calculer le reste des valeurs du tableau :
Le pivot
aij = aij – ( (aic /alc)* alj )

Var
Var de bases x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
a11= a11-(a1c /alc)*al1 1 – ((1/4)*(1))= 3/4
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0
e2 0 0 1 0
x2 1/4 1 0 0 1/4 0 120
e4 0 0 0 1
Z 0 0 0 0

Ligne du Colonne du
pivot (l =3) 23
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Calculer le reste des valeurs du tableau :
aij = aij - (aic /alc)* alj
Le pivot
Var
Var de bases x1 X2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
a13= a13-(a1c/alc)*al30 – (1/4)*(1)=-1/4
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0
e2 0 0 1 0
x2 1/4 1 0 0 1/4 0 120
e4 0 0 0 1
Z 0 0 0 0

Ligne du Colonne du
pivot (l =3) 24
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Calculer le reste des valeurs du tableau :
aij = aij - (aic /alc)* alj
Le pivot
Var
Var de bases x1 x2 e1 e2 e3 e4 bi
((0 *4)-(1*1))/4=-1/4 e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0 30 150 – ( (1/4)*(480) )= 150- (120)=30
e2 0 0 1 0
x2 1/4 1 0 0 1/4 0 120 ( (150*4)-(480*1) )/4=
(600-480)/4=120/4=30
e4 0 0 0 1
Z 0 0 0 0

Ligne du
pivot Colonne
(l =3) du 25
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Calculer le reste des valeurs du tableau :
Méthode 2
Le pivot
Var
Var de bases x1 x2 e1 e2 e3 e4 bi
((0 *4)-(1*1))/4=-1/4 e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0 30 150 – ( (1/4)*(480) )= 150- (120)=30
e2 7/2 0 0 1 -1/2 0 200
x2 1/4 1 0 0 1/4 0 120 ( (150*4)-(480*1) )/4=
(600-480)/4=120/4=30
e4 1 0 0 0 0 1 90
Z 0 0 0 0

Ligne du Colonne du
pivot (l =3) 26
pivot(c=2)
 La méthode du simplexe
Exemple : Calcul du tableau suivant
2. Calculer le reste des valeurs du tableau :

Le pivot
Var
Var de bases x1 x2 e1 e2 e3 e4 bi
e1 1 1 1 0 0 0 150
e2 4 2 0 1 0 0 440
e3 1 4 0 0 1 0 480
e4 1 0 0 0 0 1 90
Z 100200 0 0 0 0 0
Var
Var de bases
x1 x2 e1 e2 e3 E4 bi bi/aic
e1 3/4 0 1 0 -1/4 0 30 150/1= 150
e2 7/2 0 0 1 -1/2 0 200 440/2=220
x2 1/4 1 0 0 1/4 0 120 480/4=120
e4 1 0 0 0 0 1 90 90/0= +∞
Z 50 0 0 0 -50 0

100 – ( (200/4)*(1) )= 27
100- (50)=50
 La méthode du simplexe
Exemple :
La nouvelle solution réalisable : Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0 30
x1 = 0
e2 7/2 0 0 1 -1/2 0 200
x2 = 120
x2 1/4 1 0 0 1/4 0 120
e1 = 30
e4 1 0 0 0 0 1 90
e2 = 200
Z 50 0 0 0 -50 0
e3 = 0
e4 = 90
x1, x2, e1, e2, e3, e4 ≥0

z = 100x1 + 200x2 
z= 100*0 + 200*120 
z=24000

28
 La méthode du simplexe
Exemple :
1. Divise la ligne du pivot par le pivot (pivot = aic)

Var x1 x2 e1 e2 e3 e4 bi
Var de bases
e1 3/4 0 1 0 -1/4 0 30
e2 7/2 0 0 1 -1/2 0 200
x2 1/4 1 0 0 1/4 0 120
e4 1 0 0 0 0 1 90
Variable sortante Variable entrante Le pivot
Z 50 0 0 0 -50 0

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 3/4 0 1 0 -1/4 0 30 40
Plus petite
e2 7/2 0 0 1 -1/2 0 200 400/7= valeur positive

57,14
x2 1/4 1 0 0 1/4 0 120 480
e4 1 0 0 0 0 1 90 90
Z 50 0 0 0 -50 0 24000
29
 La méthode du simplexe
Exemple :
La nouvelle solution réalisable :
 Le pivot est l’intersection de la ligne du pivot et la colonne du pivot (pivot = aic)
Var x1 x2 e1 e2 e3 e4 bi
Var de bases
E1 3/4 0 1 0 -1/4 0 30 40
e2 7/2 0 0 1 -1/2 0 200 400/7
x2 1/4 1 0 0 1/4 0 120 480
e4 1 0 0 0 0 1 90 90
Z 50 0 0 0 -50 0

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
x1 1 0 4/3 0 -1/3 0
e2
x2
e4
Z

30
 La méthode du simplexe
Exemple :
La nouvelle solution réalisable :
 Le pivot est l’intersection de la ligne du pivot et la colonne du pivot (pivot = aic)
Var x1 x2 e1 e2 e3 e4 bi
Var de bases
E1 3/4 0 1 0 -1/4 0 30 40
e2 7/2 0 0 1 -1/2 0 200 400/7
x2 1/4 1 0 0 1/4 0 120 480
e4 1 0 0 0 0 1 90 90
Z 50 0 0 0 -50 0

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
x1 1 0 4/3 0 -1/3 0
e2 0 0 1 0
x2 0 1 0 0
e4 0 0 0 1
Z

31
 La méthode du simplexe
Exemple :
La nouvelle solution réalisable :
 Le pivot est l’intersection de la ligne du pivot et la colonne du pivot (pivot = aic)
aij = aij - (aic /alc)* alj Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
E1 3/4 0 1 0 -1/4 0 30 40
e2 7/2 0 0 1 -1/2 0 200 400/7
x2 1/4 1 0 0 1/4 0 120 480
e4 1 0 0 0 0 1 90 90
Z 50 0 0 0 -50 0

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
x1 1 0 4/3 0 -1/3 0 40
e2 0 0 -14/3 1 2/3 0 60
x2 0 1 -1/3 0 1/3 0 110
e4 0 0 -4/3 0 1/3 1 50
Z

32
 La méthode du simplexe
Exemple :
La nouvelle solution réalisable et optimale :
x1 = 40
x2 = 110 aij = aij - (aic /alc)* alj Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
e1 = 0 E1 3/4 0 1 0 -1/4 0 30 40
e2 = 60 e2 7/2 0 0 1 -1/2 0 200 400/7
e3 = 0 x2 1/4 1 0 0 1/4 0 120 480
e4 = 50 e4 1 0 0 0 0 1 90 90
Z 50 0 0 0 -50 0
x1, x2, e1, e2, e3, e4 ≥0

z = 100x1 + 200x2  z= 100*40 + 200*110  z=26000

Var
Var de bases
x1 x2 e1 e2 e3 e4 bi
x1 1 0 4/3 0 -1/3 0 40
e2 0 0 -14/3 1 2/3 0 60
x2 0 1 -1/3 0 1/3 0 110
e4 0 0 -4/3 0 1/3 1 50
Z 0 0 -200/3 0 -100/3 0 26000

50-( ( 50/(3/4))*3/4 ) = 0-( ( 50/3/4 )*1)= - ( 200/3) -50-( ( 50/3/4 )*(-1/4))=-50-(( 200/3)*(-1/4))=
-50- (-200/12)= -50 – (-100/6)=(- 300+100)/6=
33
50-50 = 0 =- 200/3
-200/6 =-100/3