Cours de recherche opérationnelle :

Chapitre I : programmation linéaire

Chapitre II : résolution de programme linéaire P.L par le solveur Excel

Chapitre I : programmation linéaire

L’objectif de ce chapitre est de montrer comment on peut résoudre un programme

linéaire (P.L) de façon graphique si on a deux variables de décision ou par un algorithme
(simplexe) dans le cas de plusieurs variables de décision dépassant 2. On commencera d’abord
par définir la notion de programme linéaire.

I. Définition d’un programme linéaire :

Un programme mathématique 𝑃 est composé de trois parties principales :

La première est la fonction « objectif », la deuxième correspond aux contraintes que doivent satisfaire
les variables de décision ( ) et enfin, selon que l’on a affaire à des coûts ou bénéfices préciser Min ou
Max.

Dans le cas d’un programme linéaire, la fonction « objectif » doit être linéaire (voir application
linéaire). De même, pour les contraintes sur les variables de décision doivent être linéaires eux aussi.

𝑀𝑎𝑥 𝑓(𝑥1 , 𝑥2 , 𝑥3 ) = 𝑥1 + 2𝑥1 𝑥2 + 𝑥3

𝑥1 + 2𝑥2 + 𝑥3 ≤ 4
𝑃1 : 𝑠𝑐 { 𝑥1 + 𝑥2 ≤ 3
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
{

Lorsqu’une application est linéaire, sa dérivée par rapport à 𝑥𝑖 donne une constante.

(𝑃1 ) n’est pas un programme linéaire car 𝑓 n’est pas linéaire même si les contraintes sont linéaires.

𝑀𝑖𝑛 𝑓(𝑥1 , 𝑥2 , 𝑥3 ) = 2𝑥1 + 4𝑥2

𝑥 + 𝑥22 + 𝑥3 ≥ 10
(𝑃2 ): 𝑠𝑐: { 1 (𝑃2 ) n’est pas un P.L car sa première contrainte n’est pas linéaire
𝑥1 + 𝑥2 ≥ 5
{ 𝑥1 , 𝑥2 , 𝑥3 ≥ 0

𝑓(𝑥1 , 𝑥2 , 𝑥3 ) = 10𝑥1 + 5𝑥2 + 4𝑥3

𝑥1 + 3𝑥2 + 2𝑥3 ≤ 20
(𝑃3 ): 𝑠𝑐 { 𝑥1 + 𝑥2 + 𝑥3 ≤ 10 est un P.L car la fonction « objectif » ainsi que les contraintes
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
{
sont linéaires.
 II. Résolution d’un programme linéaire par la méthode graphique :

Dans le cas d’un programme linéaire ayant deux variables de décision, il est possible de
travailler sur plan pour trouver la solution optimale du problème. Considérons l’exemple suivant :

𝑀𝑎𝑥 60𝑥1 + 40𝑥2

3𝑥1 + 9𝑥2 ≤ 90
𝑠𝑐: {4𝑥1 + 5𝑥2 ≤ 60
2𝑥1 + 𝑥2 ≤ 20
{ 𝑥1 , 𝑥2 ≥ 0

Ensemble

Admissible

(d) x Y
A 0 30
B 10 0
Pour obtenir la première droite correspondant à la première contrainte.

(L) x Y
C 0 15
D 12 0

(M) x Y
E 0 10
F 20 0
Le choix du point V(x,y) permet de déterminer la partie à hachurer : si le point vérifie l’inéquation le
versant qui le contient est le bon côté et on barre l’autre demi-plan. De manière classique on prend le
point V(0,0).

Les dérivées permettent de trouver des solutions dans l’ouvert (intervalle).

Etant donné qu’on a une fonction linéaire, alors la fonction « objectif » est strictement croissante
par rapport à chacune de ses composantes (ici 𝑥1 𝑒𝑡 𝑥2 ) ce qui veut dire que la solution optimale ne peut
pas être dans l’ouvert (pas nécessaire d’utiliser des dérivées). Il faudrait chercher donc la ou les solutions
optimales au niveau de la frontière de l’ensemble admissible.

C’est le fait qu’on a une fonction croissante qui permet de dire qu’il n’y a pas de solution dans
l’ouvert. Maintenant c’e st la linéarité qui nous permet que les solutions se trouvent en coin.

De plus, si la fonction est linéaire alors, on peut aller plus loin en affirmant que la solution
optimale fait partie des sommets du polygone admissible.

Soit M un point de la frontière admissible et qui n’est pas un sommet du polygone. Alors, il est
possible de trouver un segment du polygone qui passe par ce point. Notons par 𝑥 𝑒𝑡 𝑦 les extrémités du
segment passant par ce point. Deux cas peuvent se produire :

1er cas : 𝑓(𝑥) ≠ 𝑓(𝑦) on suppose, sans perte de généralité que 𝑓 (𝑥) > 𝑓(𝑦). Dans ce cas, le
point M ne peut être une solution optimale. En effet, ∃ 𝛾𝜖]0,1[𝑡𝑒𝑙 𝑞𝑢𝑒 𝑀 = 𝛾𝑀 𝑥 + (1 − 𝛾𝑀 )𝑦

𝑓 (𝑀) = 𝑓(𝛾𝑀 𝑥 + (1 − 𝛾𝑀 )𝑦

𝑓(𝑀) = 𝛾𝑀 𝑓(𝑥) + (1 − 𝛾𝑀 )𝑓(𝑦) (particulièrement valable pour les P.L)

Etant donné que 𝑓 (𝑦) < 𝑓(𝑥) 𝑒𝑡 (1 − 𝛾)𝑓(𝑦) < (1 − 𝛾𝑀 )𝑓(𝑥)

𝛾𝑀 𝑓 (𝑥) + (1 − 𝛾)𝑓(𝑦) < (1 − 𝛾𝑀 )𝑓 (𝑥) + 𝛾𝑀 𝑓(𝑥)

𝑓(𝑀) < 𝑓 (𝑥) on factorise par 𝑓(𝑥) a gauche pour aboutir au réultat

𝑥𝜖𝐴 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑓(𝑀) < 𝑓 (𝑥) entraîne que M n’est pas une solution optimale.

2ème cas : 𝑓(𝑥) = 𝑓(𝑦) alors 𝑓(𝑀) = 𝛾𝑀 𝑓 (𝑥) + (1 − 𝛾𝑀 )𝑓(𝑦) = 𝑓 (𝑥) = 𝑓 (𝑦)

Si 𝑥 𝑒𝑡 𝑦 sont des points non optimaux, alors M aussi l’est (non optimal).

Par contre, si on a deux points optimaux 𝑥 𝑒𝑡 𝑦 alors M l’est aussi. Dans ce cas, l’ensemble des
solutions correspond au segment [𝑥, 𝑦].

Pour un nombre de points optimaux supérieur n>2, on a une infinité de solutions (espace, plan).

Commençons par déterminer les coordonnées des sommets du polygone admissible.

 A(0,10), F(10,0), O(0,0).

3𝑎 + 9𝑏 = 90
Soit G(a,b) appartenant à D1 et D2 donc on aura : { la résolution du système par
4𝑎 + 5𝑏 = 60
30 60
substitution conduit aux solutions 𝑎 = 7
𝑒𝑡 𝑏 = 7
(éviter la projection)

De la même manière, les coordonnées du point H(x,y) seront obtenues grâce à la résolution du
4𝑥 + 5𝑦 = 60 (𝑑2 ) 20 20
système suivant par substitution :{ . Ainsi on obtient 𝑥 = 3 𝑒𝑡 𝑦 = 3 . Par
2𝑥 + 𝑦 = 20 (𝑑3 )
20 20
conséquent, 𝐻( , ).
3 3

C’est dans cette étape que l’on calcule la valeur de la fonction « objectif » suivant chaque
sommet :

2000
𝑓 (𝐴) = 400 ; 𝑓(0) = 0 ; 𝑓(𝐹 ) = 600; 𝐹(𝐺 ) = 600 𝑒𝑡 𝑓 (𝐻) = = 666,66
3
20 20
Le sommet qui maximise la fonction « objectif » est unique et est donné par 𝐻 ( , ) pour une
3 3
2000
valeur de .
3

Pour un programme linéaire, trois situations sont possibles :

 Si A est vide, alors pas de solutions, contraintes contradictoires

 Si A est non vide :
 𝑓 non bornée (il n’existe pas M/ quel que soit x appartenant à E, |𝑓(𝑥)| ≤ 𝑀)
entraine qu’il n’y pas de solution optimale car 𝑓(𝑥) va tendre vers +infini
 𝑓 bornée on l’existence au moins d’une solution (une solution ou une infinité de
solutions)

Il faut noter que si on a une P.M la fonction 𝑓 doit être bornée et fermée (compacte)

III. Résolution par l’algorithme simplexe :

Dans le cas d’un PL à trois variables ou plus, la représentation graphique n’est pas commode.
On utilise plutôt un algorithme dénommé simplexe qui consiste d’abord à se ramener à un programme
linéaire sous-forme standard puis à trouver une solution de base réalisable et enfin, on procède à des
itérations jusqu’à trouver l’optimum s’il existe.

1. Forme de programmes linéaire :

On distingue principalement trois formes programmes linéaires.

La première est dite forme canonique mixte.

 𝑀𝑎𝑥 50𝑥1 + 30𝑥2 + 70𝑥3 𝑀𝑖𝑛 25𝑥 + 35𝑦 + 10𝑧
2𝑥1 + 3𝑥2 + 5𝑥3 = 100 𝑥 + 2𝑦 ≥ 100
Exemple {𝑠𝑐 { ou encore { {
𝑥1 + 2𝑥2 + 3𝑥3 ≤ 55 𝑦 + 𝑧 = 50
𝑥1 , 𝑥2 ≥ 0 𝑒𝑡 𝑥3 ∈ ℝ 𝑥, 𝑦, 𝑧 ≥ 0

La forme canonique est formalisée par des inégalités inférieures ou égales en maximisant (≤, =
, 𝑀𝑎𝑥) et des inégalités supérieures ou égales en minimisant(≥, =, 𝑀𝑖𝑛). En outre, la mixité est traduite
par le mélange des inégalités inférieures ou égales ou, des inégalités supérieurs ou égales.

La deuxième forme d’un programme linéaire est celle dite programme ou forme canonique pure.
Ici, on exige d’avoir les mêmes inégalités au niveau des contraintes (≤, 𝑀𝑎𝑥)𝑜𝑢 (≥, 𝑀𝑖𝑛) mais aussi
toutes les variables de décisions doivent être positives (𝑥, 𝑦, 𝑧) ∈ ℝ+

𝑀𝑎𝑥 3𝑥1 + 5𝑥2 + 7𝑥3 𝑀𝑖𝑛 11𝑥 + 17𝑦 + 7𝑧

𝑥 + 2𝑥2 + 𝑥3 ≤ 40 𝑥 + 2𝑦 + 𝑧 ≥ 25
Exemple :{𝑠𝑐: { 1 { {
𝑥1 + 𝑥3 ≤ 20 𝑥 + 𝑦 ≥ 10
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 𝑥, 𝑦, 𝑧 ≥ 0

Remarque : 𝑚𝑖𝑛𝑓 = −𝑚𝑎 𝑥 (−𝑓) 𝑒𝑡 𝑚𝑎𝑥𝑓 = −𝑚𝑖𝑛(−𝑓)

La 3ème forme de PL est dite standard. Elle consiste à avoir des égalités partout dans les
contraintes mais aussi, à avoir des variables de décision qui sont toute positives (=, 𝑀𝑖𝑛)𝑜𝑢 (=, 𝑀𝑎𝑥)

𝑀𝑎𝑥 60𝑥 + 180𝑦 + 75𝑧

𝑥 + 𝑦 = 20
Exemple : { 𝑠𝑐: {
𝑥 + 𝑧 = 30
𝑥, 𝑦, 𝑧 ≥ 0

Pour un P.L mixte, on se ramène à une forme standard de la manière suivante :

𝑀𝑎𝑥 60𝑥1 + 30𝑥2 + 70𝑥3 𝑀𝑎𝑥 60𝑥1 + 30𝑥2 + 70𝑥3

2𝑥 + 3𝑥2 + 5𝑥3 = 100 2𝑥1 + 3𝑥2 + 5𝑥3 = 100
Exemple : {𝑠𝑐 { 1 donne 𝑠𝑐 {
𝑥1 + 2𝑥2 + 3𝑥3 + 𝑒1 = 55
𝑥1 + 2𝑥2 + 3𝑥3 ≤ 55
𝑥1 , 𝑥2 ≥ 0 𝑒𝑡 𝑥3 ∈ ℝ {𝑥1 , 𝑥2 , 𝑥3 = 𝑥31 − 𝑥32 , 𝑥31 , 𝑥32 , 𝑒1 ≥ 0

𝑀𝑎𝑥 60𝑥1 + 30𝑥2 + 70𝑥3

2𝑥1 + 3𝑥2 + 5(𝑥31 − 𝑥32 ) = 100
𝑠𝑐 {
𝑥1 + 2𝑥2 + 3(𝑥31 − 𝑥32 ) + 𝑒1 = 55
{ 𝑥1 , 𝑥2 , 𝑥31 , 𝑥32 , 𝑒1 ≥ 0 ℝ

La décomposition de 𝑥3 𝑒𝑛 𝑥3 = 𝑥31 − 𝑥32 permet de conserver la positivité des variables de décision (la
décomposition n’est pas unique. Par ailleurs, l’ajout de la variable « valeur d’écart » 𝑒1 permet de passer
à l’égalité sans changer le problème c’est-à-dire conserver l’équivalence, les conditions restent les
mêmes.

2. Solution de base réalisable

On considère un programme linéaire sous la forme standard :

 𝑀𝑎𝑥 𝑓 (𝑥) =𝑡 𝐶 ∗ 𝑥
{ 𝑠𝑐: 𝐴𝑚,𝑛 𝑥𝑛,1 = 𝑏
𝑥𝑛,1 ≥ 0ℝ4

𝑟𝑎𝑛𝑔𝐴 ≤ min(𝑚, 𝑛)

L’objectif pour une solution de base est d’extraire une matrice carrée d’ordre 𝑚, notée 𝐴𝑚 de
sorte que le déterminant de |𝐴𝑚 | soit différent de zéro. Au total on peut avoir 𝐶𝑛𝑚 candidat pour être une
solution de base. On notera par 𝑥𝐵 les variables choisies pour être dans la base et par 𝑥𝐻𝐵 les variables
non choisies pour être dans la base. On les posera nulles, 𝑥𝐻𝐵 = 0ℝ𝑛−𝑚 .

𝑥𝐵 𝑥𝐵
La solution de base consiste à choisir 𝑥𝐵 , 𝑥𝐻𝐵 alors 𝑥 = 𝑥 = ℝ𝑛−𝑚
𝐻𝐵 0

𝐴 = [𝐴𝐵 , 𝐴𝐻𝐵 ]

𝑥𝐵
𝐴𝑥 = [𝐴𝐵 , 𝐴𝐻𝐵 ]. 𝑥
𝐻𝐵

𝐴𝑥 = 𝐴𝐵 . 𝑥𝐵 + 𝐴𝐻𝐵 . 𝑥𝐻𝐵 = 𝑏

Or |𝐴𝐵 | ≠ 0 𝐴𝐵 est inversible donc 𝑏 = 𝐴𝐵 . 𝑥𝐵 par conséquent 𝑥𝐵 = 𝐴−1

𝐵 𝑏 (1)on dira que la

solution de base est réalisable si 𝑥𝐵 obtenu à partir de (1)est postive ou nulle (𝑥𝑖 ≥ 0, 𝑖𝜖𝐵).

Pour une solution de base 𝑥𝑖 = 0 𝑥2 = 0

𝑥𝐵 = (𝑒1 , 𝑒2 , 𝑒3 ) et 𝑥𝐻𝐵 = (0,0)

3. Déroulement de l’algorithme simplexe

Après avoir trouvé une solution de base réalisable, on peut alors commencer par dérouler
l’algorithme simplexe dont l’esprit d’un sommet du polygone admissible (solution de base réalisable) à
un autre (itération) jusqu’à de l’optimum.

lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1 𝑒1 3 9 1 0 0 90
L2 𝑒2 4 5 0 1 0 60
L3 𝑒3 2 1 0 0 1 20
CR CR 60 40 0 0 0 0
La base (e1, e2,e3) n’est pas optimal car on peut trouver des variables hors base qui puisse faire
mieux. Il est recommandé de choisir comme variable d’entrée 𝑥1 qui a un effet plus importatnt que 𝑥2
ssur la fonctioin « objectif ». Donc la variable entrante est 𝑥1

Pour trouver la variable sortante, on fixe la colonne de la variable entrante et on regarde le

𝑏 𝑏 𝑏 𝑏 90 60 20
minimum de {𝑎 𝑖 , 𝑎𝑖1 > 0} = min {𝑎 1 , 𝑎 2 , 𝑎 3 } = min { 3 , 4
, 2
} = 10 (cete donc 𝑒3 va sortir et 𝑥1
𝑖1 11 21 31

va entrer.
 Ainsi, notre

lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1’ 𝑒1 0 15/2 1 0 -3/2 60
L2’ 𝑒2 0 3 0 1 -2 20
L3’ 𝑥1 1 ½ 0 0 ½ 10
CR’ CR 0 10 0 0 -30 -600
L3’=L3/2 la méthode du pivot de Gauss permet d’obtenir la forme canonique de la base en
fixant la ligne de la variable entrée 𝑥1 au début pour obtenir le reste des valeurs du tableau.
L2’=L2-2L3
L1’=L1-3/2L3
CR’=CR-30L3
𝑥1 = 10 𝑒𝑡 𝑥2 = 0
La base (𝑒1 , 𝑒2 , 𝑥1 ) n’est pas optimal car le CR de 𝑥2 = 10 > 0 (𝑥2 𝑒ntrante)
𝑏 20
min {𝑎 𝑖 } = {8, 3
, 20}=20/3
𝑖2

lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1’’ 𝑒1 0 0 1 -5/2 7/2 10
L2’’ 𝑥2 0 1 0 1/3 -2/3 20/3
L3’’ 𝑥1 1 0 0 -1/6 5/6 20/3
CR’’ CR 0 0 0 -10/3 -70/3 -2000/3
L1’’=L1’-5/2L

L2’’=L2’/3 ( ligne de départ car contient la variable d’entrée)

L3’’=L3’-1/6L2’

CR’’=CR’-

La base (𝑒1 , 𝑥1 , 𝑥2 )𝑒𝑠𝑡 optimal car tous les CR des variables hors base sont négatifs.

Lorsqu’on a une variable HB avec le résultat trouvé en haut, on aura une infinité de solution
(cas du segment dans le cas).

Méthode recatangle :

lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1 𝑒1 3 9 1 0 0 90
L2 𝑒2 4 5 0 1 0 60
L3 𝑒3 2 1 0 0 1 20
CR CR 60 40 0 0 0 0
 lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1 𝑒1 0 𝛼=15/2 1 0 -3/2 60
L2 𝑒2 0 3 0 1 -2 20
L3 𝑥1 1 ½ 0 0 ½ 10
CR CR 0 10 0 0 -30 -600
On normalise pour la ligne pivot.

De même pour la base, on remplit la base canonique.

𝒑𝒓𝒐𝒅𝒖𝒊𝒕 𝒅𝒆𝒔 é𝒍é𝒎𝒆𝒏𝒕𝒔 𝒅𝒆 𝒍𝒂 𝒗𝒂𝒍𝒆𝒖𝒓 𝒏𝒆 𝒄𝒐𝒏𝒕𝒆𝒏𝒂𝒏𝒕 𝒑𝒂𝒔 𝒍𝒆 𝒑𝒊𝒗𝒐𝒕

𝜶 = 𝜶𝟏 −
𝒑𝒊𝒗𝒐𝒕

lignes Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
L1 𝑒1 0 0 1 -5/2 7/2 10
L2 𝑥2 0 1 0 1/3 -2/3 20/3
L3 𝑥1 1 0 0 -1/6 5/6 20/3
CR CR 0 0 0 -10/3 -70/3 -2000/3

4. Analyse post-optimal (analyse de la sensibilité) :

L’objectif pour une analyse post-optimal est de vérifier la robustesse de la solution optimale
trouvée face à des variations des paramètres du problème. Ici on s’intéressera au coefficient (c) de la
fonction « objectif » et au second membre (b).

a) Cas de la fonction « objectif » :

Supposons que le bénéfice coefficient de 𝑥1 passe de 60 à 60 + 𝛼

Quelles sont les valeurs possibles de 𝛼 permettant de conserver la solution optimale ?

lignes Base 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
𝑥𝐵
L1 𝑒1 0 0 1 -5/2 7/2 10
L2 𝑥2 0 1 0 1/3 -2/3 20/3
L3 𝑥1 1 0 0 -1/6 5/6 20/3
CR CR 𝛼 0 0 -10/3 -70/3 -2000/3
CR’=CR- CR 0 0 0 10 𝛼 70 5𝛼 2000 20𝛼
L3 − + − − − −
3 6 3 6 3 3

Pour conserver la solution de base optimale, on doit exiger que :

10 𝛼
− 3
+𝑏 ≤0 𝛼 ≤ 20
{ 70 5𝛼
{ 𝛼 ∈ [−28,20]
− − ≤0 𝛼 ≥ −28
3 𝑏

(60 + 𝛼) ∈ [32,80]

b) Cas du second membre :

 On suppose qu’il existe une perturbation au niveau de la disponibilité de la seconde contrainte.
Pour savoir les contraintes sur le paramètre 𝛽 on utilise la formule suivante.

𝑥𝑛∗ = 𝑥𝑎𝑛𝑐
∗
+ 𝛽 + 𝑒2∗

5 5𝛽
10 − 10 −
20 2 3
1 20 𝛽
3 +
𝑋𝑛∗ = 20 +𝛽 3 = 3 3
1 20 𝛽
3 − −
2000 6 3 6
(− 3 ) 10 2000 10𝛽
(− 3 ) (− 3 − 3 )

La solution demeure optimale, mais sa réalisation n’est pas garantie !!!

Pour que (x_2, x_1, e_1) soit réalisable, il faut que :

5
10 − 2𝛽 ≥0

20 𝛽
+ ≥0
3 3

20 𝛽
− ≥0
3 6

D’où on a:𝛽 ≤ 4, 𝛽 ≥ −20 𝑒𝑡 𝛽 ≤ 40, donc 𝛽 ∈ [−20,4]

Supposons que l’on veuille résoudre un premier problème appelé primal et noté (𝒫). Si ce
problème est difficile à résoudre, on peut passer à un second problème appelé Dual et noté (𝒫𝒟) qui est
plus simple à résoudre. La résolution du Dual nous permettrait de retrouver la solution du primal.

En guise d’intuition, on considère le problème suivant une entreprise fabriquer 2 produit P_1 et
P_2, utilisant chacun 3 ressources (matières premières) pour la fabrication.

Le tableau suivant donne les informations du tableau :

P_1 P_2 Disponibilité

Ress1 3 9 90

Ress2 4 5 60

Ress3 2 1 20

Bénéfice/produit 60 40

On aura ainsi
 𝑀𝑎𝑥 60
3𝑥1 + 9𝑥2 ≤ 90
{4𝑥1 + 5𝑥2 ≤ 60
2𝑥1 + 𝑥1 ≤ 20
{ 𝑥1 , 𝑥2 ≥ 0

DUAL

Notons par a, b et c les prix respectifs des ressources 1, 2 et 3.

Pour renoncer à la fabrication du produit 1, il faudrait que 3𝑎 + 4𝑏 + 2𝑐 ≥ 60. De la même manière,

on renoncera à produire P2 si, 9𝑎 + 5𝑏 + 𝑐 ≥ 40. (permet à l’entreprise de vendre les ressources sans
produire).

De l’autre côté, les prix des ressources ne doivent pas contraindre l’acheteur d’où la fonction
« objective » : 90𝑎 + 60𝑏 + 20𝑐 qu’on doit minimiser

𝑀𝑖𝑛 90𝑎 + 60𝑏 + 20𝑐

3𝑎 + 4𝑏 + 2𝑐 ≥ 60
{{
9𝑎 + 5𝑏 + 𝑐 ≥ 40
𝑥1 , 𝑥2 ≥ 0

En général on a :

𝑀𝑎𝑥: 𝑓(𝑥) =𝑡 𝐶1,𝑚 𝑥𝑚,1 𝑀𝑖𝑛 𝑓 ′ (𝑥) =𝑡 𝑏1,𝑚 𝑦𝑚,1

(𝒫) { 𝐴𝑥 ≤ 𝑏 (𝒫𝒟): { 𝑡
𝐴𝑚,𝑛 𝑦𝑚,1 ≥ 𝑆𝑛,1
𝑥≥0 𝑦≥0

Primal Dual

Max Min
m contraintes m variables de

A Transposé (A)

n variables de solution n contraintes

Propriété :soit (\scriptP) un problème donné :

 Alors Dual(Dual (𝒫) = (𝒫)

Propriété 2 :

Soit 𝑥0 un élément admissible du Primal (Max) et 𝑦0 un élément admissible du Dual (Min).

Alors on a :
 𝑓 (𝑥0 ) ≤ 𝑔(𝑦0 )

A l’optimum, on a :

𝑓 (𝑥 ∗) = 𝑔(𝑦 ∗)

où 𝑥 ∗ solution optimale 𝑥1 , 𝑥2 ≥ 0 𝑑𝑒 (𝒫) et 𝑦 ∗ solution optimal du Dual.

Dans le cas contraire, on a une inégalité stricte.

Propriété 3 :

Si le Primal admet une solution optimale, alors de Dual en possède également. Et vice versa.

Si le Primal ou le Dual n’est pas borné, alors l’autre problème a un ensemble admissible vide.

Application

𝑀𝑖𝑛 90𝑎 + 60𝑏 + 20𝑐

Résoudre }{𝑠𝑐: 3𝑎 + 4𝑏 + 2𝑐 ≥ 60
9𝑎 + 5𝑏 + 𝑐 ≥ 40

3𝑎 + 4𝑏 + 2𝑐 − 𝑒1 = 60
Le programme standard donne : { 9𝑎 + 5𝑏 + 𝑐−𝑒2 = 40 ( en utilisant le système de
𝑎, 𝑏, 𝑐, 𝑒1 , 𝑒2 ≥ 0
tatônnement, on risque de ne pas aboutir.

𝑀𝑎𝑥 60𝑥1 + 40𝑥2 𝑀𝑎𝑥 60𝑥1 + 40𝑥2

3𝑥1 + 9𝑥2 ≤ 90 3𝑥1 + 9𝑥2 − 𝑒1 = 90
Le problème Dual donne : {4𝑥1 + 5𝑥2 ≤ 60 → {4𝑥1 + 5𝑥2 − 𝑒2 = 60 la résolution du
2𝑥1 + 𝑥2 ≤ 20 2𝑥1 + 𝑥2 − 𝑒3 = 20
{ 𝑥1 , 𝑥2 ≥ 0 { 𝑥1 , 𝑥2 ≥ 0
problème donne :

Base 𝑥𝐵 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 b
𝑒1 0 0 1 -5/2 7/2 10
𝑥2 0 1 0 1/3 -2/3 20/3
𝑥1 1 0 0 -1/6 5/6 20/3
CR 0 0 0 -10/3 -70/3 -2000/3
10 70
Ainsi on a : 𝑎 ∗= 0, 𝑏 ∗= 𝑒𝑡 𝑐 ∗= on prend les || des bases initiales.
3 3

Autre méthode :

Primal a b c 𝑓1 𝑓2
Dual 𝑒1 =10 𝑒2 =0 𝑒3 =0 𝑥1 = 10 20
𝑥2 =
3
D’après lle théorème de complémentairté on a :

𝑎 × 𝑒1 = 0; 𝑏 × 𝑒2 = 0; 𝑐 × 𝑒3 = 0, 𝑓1 × 𝑥1 = 0 𝑒𝑡 𝑓2 × 𝑥2 = 0
 Cela signifie que les produits des éléments solutions directes sont toutes nulles d’où 𝑓1 =
20
0, 𝑓2 = 0 (𝑥1 = 10 𝑒𝑡 𝑥2 = ) 𝑒𝑡 𝑎 = 0 (𝑒1 = 10)
3

𝑓1 = 0 3𝑎 + 4𝑏 + 2𝑐 = 60 4𝑏 + 2𝑐 = 60 10 10
{𝑓2 = 0 → { 9𝑎 + 5𝑏 + 𝑐 = 40 → { 5𝑏 + 𝑐 = 40 → 𝑏 = 𝑒𝑡 𝑐 =
3 3
𝑎=0 𝑎=0 𝑎=0

Pour les problèmes Min, il est plus facile d’utiliser la dualité ≥ 𝑐𝑜𝑚𝑚𝑒 𝑐𝑜𝑛𝑡𝑟𝑎𝑖𝑛𝑡𝑒𝑠.

La méthode des deux phases : trouver à trouver une solution de base réalisable de façon simple
en rajoutant des variables artificielles 𝑎1 , 𝑎2 au niveau des contrainte pour trouver directement une
solution de base réalisable : éliminer les variables 𝑎1 𝑒𝑡 𝑎2 = 0 grâce à une itération (variables hors
base

Phase 2 : à la fin de la 1ère phase, rentrée de deux nouvelles variables qui prendront les places
de 𝑎1 𝑒𝑡 𝑎2