CHAP 1 (Suite) Programmation linéaire : Résolution par la méthode du simplexe d’un programme

linéaire

C’est une méthode basée sur des itérations successives en vue de se rapprocher au mieux des solutions
optimales du programme.

A-2-1 Principe généraux du simplexe

Nous insisterons sur les éléments les plus importants : d’abord la notion de variables d’écart, qui sont
des variables qui permettent de transformer les contraintes d’inégalité en contraintes d’égalité. Elle est
généralement notée 𝑆𝑖 . Elle n’a aucune influence sur la fonction- objectif. Ensuite la notion de
variables artificielles. Elles sont introduites lorsque le système d’équations standard ne permet de
dégager une base de l’espace vectoriel. En effet avant de commencer les itérations l’on doit s’assurer
que la matrice des équations standard contient une partie de la matrice identité. Elles sont notées 𝐴𝑖
et sont introduites dans le but de corriger les 𝑆𝑖 .

En resumé la configuration des variables Artificiel 𝐴𝑖 en fonction des variables 𝑆𝑖 est la suivante :

Type d’inégalité Contraintes Coefficient de Z

Maximisation Minimisation

≥ S (coefficient -1) 0 0

A (coefficient +1) -M +M

= A (coefficient +1) -M +M

≤ S (coefficient +1) 0 0

Le tableau du simplexe est donc configuré de la manière suivante :

𝐶𝑗 Valeurs de Cj
 Base Noms des variables Valeurs
(Xj , Si , Ai)

Liste des
variables de base
bi
(de la matrice
identité)

Zj (Somme des lignes / colonnes Z* la valeur

finale de la
fonction -
objectif

Cj -Zj

Exemple : soit le programme linéaire ci- dessous à résoudre, dressez le tableau du simplexe.

−2𝑥1 + 𝑥2 ≤ 4
3𝑥1 + 4𝑥2 ≥ 2
5𝑥1 + 9𝑥2 = 8
Min 𝑍 = 𝑥1 + 𝑥2 sous contraintes
2𝑥1 + 𝑥2 ≥ −3
−3𝑥1 − 𝑥2 ≤ −2
{ 𝑥1 ≥ 0 , 𝑥2 ≥ 0

Avant de déterminer la forme standard l’on devrait d’abord préciser que les contraintes ne doivent
jamais être négatives, il serait donc nécessaire de les rendre positives avant de continuer : en
multipliant les deux dernières inéquations par le signe (-) on obtient le programme linéaire ci-dessous :

−2𝑥1 + 𝑥2 ≤ 4
3𝑥1 + 4𝑥2 ≥ 2
5𝑥1 + 9𝑥2 = 8
Min 𝑍 = 𝑥1 + 𝑥2 sous contraintes
−2𝑥1 − 𝑥2 ≤ 3
3𝑥1 + 𝑥2 ≥ 2
{𝑥1 ≥ 0 , 𝑥2 ≥ 0

On peut donc à présent déterminer la forme standard du programme en respectant les consignes
susmentionnées :
Min 𝑍 = 𝑥1 + 𝑥2 + 0𝑆1 + 0𝑆2 + 0𝑆3 + 0𝑆4 + 0𝑆5 + 𝑀𝐴2 + 𝑀𝐴3 + 𝑀𝐴5 sous contraintes
−2𝑥1 + 𝑥2 + 𝑆1 = 4
3𝑥1 + 4𝑥2 − 𝑆2 + 𝐴2 = 2
5𝑥1 + 9𝑥2 + 𝐴3 = 8
−2𝑥1 − 𝑥2 + 𝑆4 = 3
3𝑥1 + 𝑥2 − 𝑆5 + 𝐴5 = 2
{ 𝑥1 ≥ 0 , 𝑥2 ≥ 0

En ordonnant toutes les variables de notre programme linéaire, on obtient finalement le tableau :

𝐶𝑗 1 1 0 0 M M 0 0 M

Base 𝑥1 𝑥2 𝑆1 𝑆2 𝐴2 𝐴3 𝑆4 𝑆5 𝐴5 Valeurs

0 𝑆1 -2 1 1 0 0 0 0 0 0 4

M 𝐴2 3 4 0 -1 1 0 0 0 0 2

M 𝐴3 5 9 0 0 0 1 0 0 0 8

0 𝑆4 -2 -1 0 0 0 0 1 0 0 3

M 𝐴5 3 1 0 0 0 0 0 -1 1 2

Zj (Somme 11M 14M 0 -M M M 0 -M M Z*= 12 M

des lignes /
colonnes

1-11M 1-14M 0 -M 0 0 0 -M 0
Cj -Zj

Test d’optimalité :

Il permet de savoir que le tableau est optimal et que les solutions optimales sont bien connues. Deux
cas peuvent survenir selon que l’on soit en maximisation ou en minimisation.

Cas de maximisation (rendre Z le plus grand possible)

Si une variable à un 𝐶𝑗 − 𝑍𝑗 négatif, il n’y’a pas d’intérêt à la faire rentrer dans la base car elle
diminue 𝑍𝑗 . Les variables à faire rentrer dans la base doivent avoir 𝐶𝑗 − 𝑍𝑗 strictement [Link]
aucun 𝐶𝑗 − 𝑍𝑗 n’est positif (tous négatifs ou nuls) ; c’est que l’on a atteint le tableau optimal.

Cas de minimisation (rendre Z le plus petit possible)

Si une variable à un 𝐶𝑗 − 𝑍𝑗 positif, il n’y’a pas d’intérêt à la faire rentrer dans la base car elle
augmente 𝑍𝑗 . Les variables à faire rentrer dans la base doivent avoir 𝐶𝑗 − 𝑍𝑗 strictement négatif .Si
aucun 𝐶𝑗 − 𝑍𝑗 n’est négatif (tous positifs ou nuls) ; c’est que l’on a atteint le tableau optimal.

Exemple d’application : Reprenons l’exemple sur les camions et déterminons les quantités 𝑥1 𝑒𝑡 𝑥2
représentant la production pour chaque modèle de camions fabriqué.

Programme linéaire

Max Z = 3𝑥1 + 4𝑥2 sous la contrainte de :

2𝑥1 + 𝑥2 ≤ 12
{ 𝑥1 + 2𝑥2 ≤ 12
𝑥1 ≥ 0 𝑥2 ≤ 0

Forme standard

Max Z = 3𝑥1 + 4𝑥2 + 0𝑆1 + 0𝑆2 sous la contrainte de :

2𝑥1 + 𝑥2 + S1 = 12
𝑥1 + 2𝑥2 + S2 = 350
{
𝑥1 ≥ 0 𝑥2 ≤ 0

Tableau du simplexe :
 𝐶𝑗 3 4 0 0 0

Base 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Valeurs Ratios

0 𝑆1 2 1 1 0 0 12 12

0 𝑆2 1 2 0 1 0 12 6

Zj (Somme 0 0 0 0 0 0
des lignes /
colonnes

3 4 0 0 0
Cj -Zj

On fait rentrer en base la variable en colonne qui à le plus grand Cj -Zj positif ici (𝑥2 ) et on divise
toutes les valeurs par ses différents 𝑎2𝑗 ; la variable sortante en base sera donc celle qui aura le plus
petit ratio en ligne ici(𝑆2 ). Et on procède comme cela jusqu’à ce que l’on obtienne tous les Cj -Zj
négatifs ou nuls. On cherchera toute fois à rendre le vecteur de la variable qui entre en base semblable
à celui de la variable qui en sort. A cet effet la méthode de Gauss peut être d’une grande utilité.

2ième e itération

𝐶𝑗 3 4 0 0

Base 𝑥1 𝑥2 𝑆1 𝑆2 Valeurs Ratio

0 𝑠1 3/2 0 1 -1/2 6 4

4 𝑥2 1/2 1 0 1/2 6 12

Zj (Somme 2 4 0 0
des lignes /
colonnes

1 0 0 0
Cj -Zj

3ième e itération
 𝐶𝑗 3 4 0 0

Base 𝑥1 𝑥2 𝑆1 𝑆2 Valeurs

3 𝑥1 1 0 2/3 -1/3 4

4 𝑥2 0 1 1/3 2/3 4

Zj (Somme 3 4 2 /3 5 /3 Z*=28
des lignes /
colonnes

0 0 -2/3 -5/3
Cj -Zj
On obtient un tableau
dont tous les Cj -Zj sont
tous négatifs ou nuls, on a donc le tableau optimal avec
𝑥1 = 4 𝑒𝑡 𝑥2 = 4

CHAPITRE 4 (suite) La dualité

Jusqu’ici les programmes que l’on a eu à résoudre sont des programmes linéaires primaux. Un
programme linéaire primal est un programme formulé pour la résolution d’un problème. Ainsi si le
programme primal est de la forme :

𝑀𝑎𝑥 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 + ⋯ + 𝑐𝑛 𝑥𝑛

𝑎1 𝑥1 + 𝑎2 𝑥2 + 𝑎3 𝑥3 + ⋯ + 𝑎𝑛 𝑥𝑛 ≤ 𝑏1
𝑎1 ′𝑥1 + 𝑎2 ′𝑥2 + 𝑎3 ′𝑥3 + ⋯ + 𝑎𝑛 ′𝑥𝑛 ≤ 𝑏2
𝑎1 ′′𝑥1 + 𝑎2 ′′𝑥2 + 𝑎3 ′′𝑥3 + ⋯ + 𝑎𝑛 ′′𝑥𝑛 ≤ 𝑏3
S/C .
.
.
{𝑎1 ′′′𝑥1 + 𝑎2 ′′′𝑥2 + 𝑎3 ′′′𝑥3 + ⋯ + 𝑎𝑛′′′ 𝑥𝑛 ≤ 𝑏𝑛

Le programme dual sera de la forme :

𝑀𝑖𝑛 𝑍 = 𝑏1 𝑦1 + 𝑏2 𝑦2 + 𝑏3 𝑦3 + ⋯ + 𝑏𝑛 𝑦𝑛
 𝑎1 𝑦1 + 𝑎1 ′𝑦2 + 𝑎1 ′′𝑦3 + ⋯ + 𝑎1 ′′′𝑦𝑛 ≥ 𝑐1
𝑎2 𝑦1 + 𝑎2 ′𝑦2 + 𝑎2 ′′𝑦3 + ⋯ + 𝑎2 ′′′𝑦𝑛 ≥ 𝑐2
𝑎3 𝑦1 + 𝑎3 ′𝑦2 + 𝑎3 ′′𝑦3 + ⋯ + 𝑎3 ′′′𝑦𝑛 ≥ 𝑐3
S/C .
.
.
{𝑎𝑛 𝑦1 + 𝑎𝑛 ′𝑦2 + 𝑎𝑛 ′′𝑦3 + ⋯ + 𝑎𝑛 ′′′𝑦𝑛 ≥ 𝑐𝑛

Dans le tableau optimal du dual les solutions sont lues de manière normale, et les solutions du primal
sont lues sur les colonnes.

Importance du programme dual

Le programme dual permet de résoudre les programmes linéaires complexes à l’instar des
programmes de minimisation.

𝑀𝑖𝑛 𝑍 = 90𝑥1 + 100𝑥2

12𝑥1 + 9𝑥2 ≥ 108

S/C { 8𝑥1 + 12𝑥2 ≥ 96
𝑥1 , 𝑥2 ≥ 0

Le programme dual nous donnera :

𝑀𝑎𝑥 𝑍 = 108𝑦1 + 96𝑦2

12𝑦1 + 8𝑦2 ≤ 90
S/C {9𝑦1 + 12𝑦2 ≤ 100
𝑦1 , 𝑦2 ≥ 0
D’où la forme standard :

𝑀𝑎𝑥 𝑍 = 108𝑦1 + 96𝑦2 + 0𝑠1 + 0𝑠2

12𝑦1 + 8𝑦2 + 𝑠1 = 90
S/C {9𝑦1 + 12𝑦2 + 𝑠2 = 100
𝑦1 , 𝑦2 ≥ 0

Tableau 1

𝐶𝑗 108 96 0 0

Base 𝑦1 𝑦2 𝑠1 𝑠2 Valeurs Ratios

0 𝑆1 12 8 1 0 90 15/2

0 𝑆2 9 12 0 1 100 100/9

Zj (Somme 0 0 0 0 0
des lignes /
colonnes

108 96 0 0
Cj -Zj
Tableau 2

𝐶𝑗 108 96 0 0

Base 𝑦1 𝑦2 𝑠1 𝑠2 Valeurs Ratios

108 𝑦1 1 2/3 1/12 0 15/2 45/4

0 𝑆2 0 6 -3/4 1 65/2 65/12

Zj (Somme 108 72 9 0
des lignes /
colonnes

0 24 -9 0
Cj -Zj
Tableau 3

𝐶𝑗 108 96 0 0

Base 𝑦1 𝑦2 𝑠1 𝑠2 Valeurs

108 𝑦1 1 0 1/6 -1/9 35/9

96 𝑦2 0 1 -1/8 1/6 65/12

Zj (Somme 108 96 6 28 940

des lignes /
colonnes

0 0 -6 -4
On remarque alors que le
Cj -Zj
tableau est optimal (tous les
Cj -Zj sont négatifs ou nuls).
Les solutions du dual se lisent sur les lignes (normalement) et les sont les solutions des variables
d’écart, et les solutions du primal se lisent en colonne et sont les solutions des variables
décisionnelles.

35 65
Dans notre exemple, on aura 𝑠1 = 9 𝑠2 =12 𝑥1 =6 et 𝑥2 =4 𝑍 = 940