Dualité en Programmation Linéaire

Algorithmes primal et dual du simplexe

Alain Faye
Option 3A
Optimisation 1

1
 Plan
• Dualité lagrangienne (rappels)
• Programmation linéaire et dualité
– Définition du dual d’un programme linéaire
– Théorème de dualité forte
• Algorithmes primal et dual du simplexe
• Annexes
– Interprétation des variables duales
– Théorème des écarts complémentaires

2
Dualité lagrangienne

3
 Dualité lagrangienne
𝑔𝑖 𝑥 ≤ 0, 𝑖 = 1, … , 𝑚
Problème Primal min 𝑓(𝑥) s.c. ൝
𝑥∈𝑋 ℎ𝑗 (𝑥) = 0, 𝑗 = 1, … , 𝑝

avec 𝑋𝑅𝑛

𝑚 𝑝
Fonction de Lagrange 𝐿 𝑥, 𝜆, 𝜇 = 𝑓 𝑥 + ෍ 𝑖 𝑔𝑖 𝑥 + ෍ 𝑗 ℎ𝑗 𝑥
𝑖=1 𝑗=1
𝑎𝑣𝑒𝑐 𝑖 ≥ 0 𝑖 = 1, … , 𝑚

Fonction duale 𝜃(, )=min 𝐿(𝑥, 𝜆, 𝜇)

𝑥∈𝑋

Problème Dual max 𝜃(, )

≥0, 
4
 Dualité lagrangienne

Théorème de dualité
𝑓 𝑥  𝜃(, )
𝑥𝑋 satisfaisant les contraintes du primal
≥0, 

Corollaire
Soit 𝑥 ∗ 𝑋 satisfaisant les contraintes du primal
et ∗ ≥0, ∗
tels que:
𝑓 𝑥 ∗ = 𝜃(∗ , ∗ )
Alors 𝑥 ∗ est solution du primal et (∗ , ∗ ) est solution du dual

5
Programmation Linéaire et dualité

6
Pb du pharmacien : fournir une potion contenant un minimum d’unités
en vitamines A, B, C
en utilisant les poudres fournies par 2 laboratoires

100g de poudre laboratoire 1 laboratoire 2

vitamine A 20 unités 5 unités
vitamine B 30 unités 20 unités
vitamine C 5 unités 10 unités
coût 6 9

Il lui faut au moins

25 unités de vitamine A
60 unités de vitamine B
15 unités de vitamine C

7
Pb du pharmacien : fournir une potion contenant un minimum d’unités
en vitamines A, B, C
en utilisant les poudres fournies par 2 laboratoires

100g de poudre laboratoire 1 laboratoire 2

vitamine A 20 unités 5 unités
vitamine B 30 unités 20 unités
vitamine C 5 unités 10 unités
coût 6 9
min 6 x1  9 x2
Il lui faut au moins  20 x1  5 x2  25
 30 x  20 x2  60
25 unités de vitamine A  1
s.c. 
60 unités de vitamine B  5 x1  10 x2  15
15 unités de vitamine C  x1  0 x2  0

8
 Majorants et minorants

Quelques solutions
x1 = 3, x2 = 0, z = 18

x1 = 2, x2 = 1, z = 21

Ce sont des solutions sous-optimales donc majorants de la valeur optimale z*

z* ≤ 18

Comment obtenir des minorants ?

? ≤ z*

9
• 3/10 × la contrainte vit.A  7,5 ≤ 6 x1 + 3/2 x2 ≤ 6 x1 + 9 x2 = z

Donc 7,5 ≤ z*

• 3/20 × vit.A + 1/10 × vit.B  75/20 + 6 ≤ 6 x1 + (15/20 + 2) x2 ≤ 6 x1 + 9 x2 = z

Donc 3,75 + 6 = 9,75 ≤ z*

• 2/10 × la contrainte vit.B  12 ≤ 6 x1 + 4 x2 ≤ 6 x1 + 9 x2 = z

Donc 12 ≤ z*

On sait dèjà que 12 ≤ z* ≤ 18

Peut-on faire mieux ?

10
Généralisons cette approche

Introduisons les variables

yA≥0 , yB≥0 , yC≥0

25 ≤ 20 x1 + 5 x2 × yA
60 ≤ 30 x1 + 20 x2 × yB
15 ≤ 5 x1 + 10 x2 × yC

25 yA + 60 yB + 15 yC ≤ x1 (20 yA + 30 yB + 5 yC ) + x2 (5 yA + 20 yB + 10 yC )

On impose
20 yA + 30 yB + 5 yC ≤ 6 (1)
5 yA + 20 yB + 10 yC ≤ 9 (2)

On a alors
25 yA + 60 yB + 15 yC ≤ 6 x1 + 9 x2 = z

Comme on veut le minorant le plus haut possible, il ne reste plus qu’à

maximiser 25 yA + 60 yB + 15 yC
sous contraintes (1) , (2)
et avec yA≥0 , yB≥0 , yC≥0

11
 Résumons
Problème dual (D)
Problème primal (P)
𝑚
𝑛 max 𝑤 = ෍ 𝑏𝑖 𝑦𝑖
min 𝑧 = ෍ 𝑐𝑗 𝑥𝑗 𝑖=1
𝑗=1
σ𝑚𝑖=1 𝑎𝑖𝑗 𝑦𝑖 ≤ 𝑐𝑗 (𝑗 = 1 à 𝑛)
σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 (𝑖 = 1 à 𝑚) s.c. ൝
s.c. ൝ 𝑦𝑖 ≥ 0 (𝑖 = 1 à 𝑚)
𝑥𝑗 ≥ 0 (𝑗 = 1 à 𝑛)

Exemple:

min 6 x1  9 x2 max 25 yA  60 yB  15 yC
 20 x1  5 x2  25  20 yA  30 yB  5 yC 6
 30 x  20 x2  60 
 1 s.c.  5 yA  20 yB  10 yC 9
s.c. 
 5 x1  10 x2  15 y  0 y  0
 A yC  0
 x1  0 x2  0 B

12
Dualité et programmation linéaire
Primal (P) min 𝑐𝑥 s.c. 𝐴𝑥 ≥ 𝑏
𝑥≥0

Dual (D) max 𝑦𝑏 s.c. 𝑦𝐴 ≤ 𝑐

𝑦≥0

Format des données et des variables

y
A b

c x

13
 Construction du dual
min cx max yb
 
(P)  Ax  b D  s.c.  yA  c
  x  0   y  0
s.c.
 

 20 5   25 
x     
c  6 9  x   1  A   30 20  y  yA yB yC  b   60 
 x2   5 10   15 
   

min 6 x1  9 x2 max 25 y A  60 y B  15 y C
 20 x1  5 x2  25  20 y A  30 y B  5 yC 6
 30 x 
 1  20 x2  60 s.c.  5 y A  20 y B  10 y C 9
s.c.  y  0 y  0
 5 x1  10 x2  15  A B yC  0
 x1  0 x2  0

14
 Définition du dual dans le cas général

On rajoute des contraintes d’égalités et des variables sans signe (≷0)

Tableau de correspondance primal – dual

minimisation maximisation
Fonction objectif min Fonction objectif max
Second membre Fonction objectif
A matrice des contraintes AT matrice des contraintes
Contrainte i type ≥ Variable yi ≥0
Contrainte i type = Variable yi sans signe
Variable xj ≥0 Contrainte j type ≤
Variable xj sans signe Contrainte j type =

On lit de gauche à droite quand le primal est en minimisation

De droite à gauche quand le primal est en maximisation

15
Remarque
Le dual de (D) est (P)
Pour le voir:
1- Ecrire (D) sous forme d’un problème de minimisation avec contraintes ≥
On note (D’) le problème obtenu,
2- Ecrire le dual de (D’) en utilisant la transformation matricielle précédente
Vérifier que le dual de (D’) est (P)

Il en résulte que l’on peut lire la transformation pour passer du primal au dual
de gauche à droite mais aussi de droite à gauche

Exemple : écrire le dual de ce PL

max v  25 yA  60 yB  15 yC

  20 yA  30 yB  5 yC 6
s.c.  5 yA  20 yB  10 yC 9
 
  yA  0 yB  0 yC  0

16
Dualité et programmation linéaire
Théorème de dualité faible
Pour toute solution x admissible de (P) et toute solution y admissible de (D)
l’objectif de (P) est supérieur ou égal à l’objectif de (D) : z  w

démonstration
z = cx ≥ (yA)x = y(Ax) ≥ yb = w
cyA Axb

17
Dualité et programmation linéaire
Théorème de dualité faible
Pour toute solution x admissible de (P) et toute solution y admissible de (D)
l’objectif de (P) est supérieur ou égal à l’objectif de (D) : z  w

démonstration
z = cx ≥ (yA)x = y(Ax) ≥ yb = w

cyA Axb

Corollaire
Soit x* solution admissible de (P) et z* = cx* la valeur de l’objectif de (P)
Soit y* solution admissible de (D) et w* = y*b la valeur de l’objectif de (D)
telles que z* = w*
Alors x* et z* sont solutions optimales de (P) et (D) respectivement.

18
 Exercice
Exercice
1- Ecrire le dual lagrangien de (P) avec y=0 comme variables duales
2- Donner les conditions sur y telles que ce dual lagrangien ait une valeur>-
3- En déduire que le dual lagrangien de (P) est le problème (D)

19
 Saut de dualité

Le résultat suivant est très important ;

- Si l’un des 2 problèmes a un optimum fini,

alors les valeurs optimales des 2 problèmes (P) et (D) coïncident.

- Si l’un des 2 problèmes a un optimum non fini,

alors l’autre problème n’a pas de solution réalisable

pas de saut entre les valeurs optimales des problèmes (P) et (D)

20
Absence de saut de dualité
Théorème de dualité forte

21
 Conditions de Karush-Kuhn-Tucker

Soit le programme mathématique suivant

min 𝑓(𝑥)
s.c. 𝑔𝑖 𝑥 ≤ 0 𝑖∈𝐼
Avec 𝐼 un ensemble fini d’indices
𝑓, 𝑔𝑖 𝑖 ∈ 𝐼 , fonctions de classe C1

Conditions nécessaires d’optimalité (Karush-Khun-Tucker)

Si x* « qualifié » est un minimiseur local alors il existe 𝑖 ≥ 0 𝑖 ∈ 𝐼 tels que

𝛻𝑓 𝑥 ∗ + ෍ 𝑖 𝛻𝑔𝑖 𝑥 ∗ = 0 (𝑐1)
𝑖∈𝐼
𝑖 𝑔𝑖 𝑥∗ =0 𝑖∈𝐼 (𝑐2)

(c1) est la généralisation de f(x)=0 (f désigne le gradient de f)

(c2) sont les conditions de complémentarité : une contrainte non saturée gi(x)<0  i=0
i iI sont appelés « multiplicateurs de Lagrange »
22
 Conditions de Karush-Kuhn-Tucker
Qualification de Arrow-Hurwicz-Uzawa

Théorème Arrow-Hurwicz-Uzawa
Soit x réalisable (satisfaisant les contraintes) et I(x) les indices des contraintes gi(x)≤0
saturées par x (i.e. gi(x)=0).
Si les gi iI(x) sont concaves alors x est qualifié.

Dans ce cas, les conditions KKT sont des conditions nécessaires d’optimalité.

Dans le cas de la PL, les fonctions définissant les contraintes sont affines donc concaves.
Donc tout x réalisable est qualifié et
les conditions KKT sont des conditions nécessaires d’optimalité

23
 Conditions KKT Exemple
𝑥1
Soit une bille de masse m sur des plans d’équation ai x ≥ bi avec 𝑥 = 𝑥
2
La bille cherche à minimiser son énergie potentielle
L’énergie potentielle z dépend de la hauteur x2 de la bille : z=mgx2
0
𝛻𝑧 =
𝑚𝑔
Considérons 3 plans : x1+x22 (1), -x1+2x2 0 (2) , -x1+x2 -2 (3)

1 −1 −1
𝑎1 = , 𝑎2 = , 𝑎3 =
1 2 1

24
 Conditions KKT Exemple

1. Dessiner les vecteurs ai i=1,2,3 et vérifier qu’ils sont orthogonaux aux plans (i)
respectivement.
6
2. Mettre la bille au point 𝑃1 = . La bille est supportée par le plan (3).
4
Ecrire les conditions KKT. Sont-elles satisfaites ?
4
3. Mettre la bille au point 𝑃2 = . Quels sont les 2 plans qui supportent la bille ?
2
Ecrire les conditions KKT. Sont-elles satisfaites ?
4
3
4. Mettre la bille au point 𝑃3 = 2 . Quels sont les 2 plans qui supportent la bille ?
3
Ecrire les conditions KKT. Sont-elles satisfaites ?
Vérifier que le poids mg de la bille est « compensé » par les vecteurs ai des plans
supportant la bille.

25
 Théorème de dualité

Théorème de dualité forte

Si le primal admet une solution optimale alors le dual admet une solution optimale ,
et les valeurs optimales des 2 problèmes coïncident.

26
 Théorème de dualité

Théorème de dualité forte

Si le primal admet une solution optimale alors le dual admet une solution optimale ,
et les valeurs optimales des 2 problèmes coïncident.

Démonstration
On peut faire une preuve à partir des conditions nécessaires d’optimalité de
Karush-Khun-Tucker
Soit x* la solution optimale de (P)
Il existe ≥0 associé aux contraintes b-Ax≤0, ≥0 associé aux contraintes -x≤0
tels que c-A-=0 et (Ax*-b)=0 et x*=0

27
 Théorème de dualité

Théorème de dualité forte

Si le primal admet une solution optimale alors le dual admet une solution optimale ,
et les valeurs optimales des 2 problèmes coïncident.

Démonstration
On peut faire une preuve à partir des conditions nécessaires d’optimalité de
Karush-Khun-Tucker
Soit x* la solution optimale de (P)
Il existe ≥0 associé aux contraintes b-Ax≤0, ≥0 associé aux contraintes -x≤0
tels que c-A-=0 et (Ax*-b)=0 et x*=0
-point 1. ≥0  c-A≥0  c ≥ A donc  satisfait les contraintes de (D)
-point 2. On multiplie c-A-=0 par x*  cx*-Ax*-x*=0  cx*= Ax* = b
Les valeurs des objectifs de (P) et (D) coïncident .

Donc  est solution optimale de (D) (cf corollaire du th. Dualité faible)

28
 Que se passe-t-il si l’un des 2 problèmes (primal ou dual) est non borné ?

Il résulte de l’inégalité zv (th. dualité faible) que

- si min z est non borné (-) alors max v= - c’est –à dire le dual n’a pas de solution
- et réciproquement si max v= + alors le primal n’a pas de solution

Exemple: soit le problème (P)

max 𝑣 = 𝑦1 + 2𝑦2
−2𝑦1 + 𝑦2 ≤ 2
−𝑦1 + 2𝑦2 ≤ 5
s.c.
𝑦1 − 4𝑦2 ≤ 4
𝑦1 ≥ 0, 𝑦2 ≥ 0
Ecrire le dual de ce problème. A-t-il une solution réalisable ?
Confirmer votre réponse en résolvant (P) par l’algorithme du simplexe.

29
Il résulte de l’inégalité zw (Th. dualité faible)

• Si (P) a un optimum non borné (-) alors le max de w vaut -  c’est-à-dire (D) pas de solution réalisable
Exemple: (P) min 𝑧 = −𝑥1 + 𝑥2
−𝑥 + 2𝑥2 ≥ 1
s.c. ቊ 1
𝑥1 ≥ 0, 𝑥2 ≥ 0
• Si (D) a un optimum non borné (+) alors le min de z vaut +  c’est-à-dire (P) pas de solution réalisable
Exemple: (D) max 𝑤 = 𝑦1 + 𝑦2
𝑦 − 2𝑦2 ≤ 1
s.c. ቊ 1
𝑦1 ≥ 0, 𝑦2 ≥ 0

(P) et (D) peuvent ne pas avoir de solution réalisable simultanément

Exemple : (P) min 𝑧 = 𝑥1 − 𝑥2
𝑥1 + 𝑥2 ≥ 1
s.c.ቐ −2𝑥1 ≥ 1
𝑥1 ≥ 0, 𝑥2 ≥ 0

30
Algorithmes primal et dual du simplexe

31
 Algorithmes primal et dual du simplexe
Problème (P) sous forme standard min 𝑐𝑥 s.c. 𝐴𝑥 = 𝑏
𝑥≥0
(contraintes =)

Problème (D) dual de (P) max 𝑦𝑏 s.c. 𝑦𝐴 ≤ 𝑐

𝑦

Attention pas de condition de signe sur y

32
 Algorithmes primal et dual du simplexe

Base

Quitte à déplacer les colonnes de A,

on partitionne A en une matrice carrée B inversible et une matrice N

A= 𝐵 𝑁

On partitionne de façon identique le vecteur x et le vecteur c

𝑥𝐵
𝑐𝑥 = 𝑐𝐵 𝑐𝑁
𝑥𝑁 = 𝑐𝐵 𝑥𝐵 + 𝑐𝑁 𝑥𝑁

𝑐𝐵 est le vecteur extrait de 𝑐 , correspondant aux colonnes de la matrice 𝐵

𝑐𝑁 est le vecteur extrait de 𝑐 , correspondant aux colonnes de la matrice 𝐵
Même chose pour le vecteur 𝑥
33
 Algorithmes primal et dual du simplexe
Solution de base de (P)
𝑥𝐵
𝐴𝑥 = 𝑏 ↔ 𝐵 𝑁 𝑥𝑁 = 𝐵𝑥𝐵 + 𝑁𝑥𝑁 = 𝑏

La solution de base (associée à B) est la solution du système particulière suivante:

𝑥𝑁 = 0, 𝑥𝐵 = 𝐵 −1 𝑏
Le coût de cette solution est 𝑐𝑥 = 𝑐𝐵 𝐵−1 𝑏

On pose 𝑦 = 𝑐𝐵 𝐵−1

On constate alors que: 𝑐𝑥 = 𝑦𝑏 Égalité entre l’objectif de (P) et (D)

Maintenant si x satisfait les contraintes de (P) et y les contraintes de (D)

Alors x et y sont solutions (optimales) de (P) et (D) respectivement.
Voir le théorème de dualité et son corollaire
34
Algorithmes primal et dual du simplexe

Coûts réduits
𝑐𝑥 = 𝑐𝐵 𝑥𝐵 + 𝑐𝑁 𝑥𝑁

𝐴𝑥 = 𝑏 , 𝐵𝑥𝐵 + 𝑁𝑥𝑁 = 𝑏 , 𝑥𝐵 + 𝐵 −1 𝑁𝑥𝑁 = 𝐵 −1 𝑏

𝑐𝑥 = 𝑐𝐵 𝑥𝐵 + 𝑐𝑁 𝑥𝑁 = 𝑐𝐵 𝐵−1 𝑏 + (𝑐𝑁 − 𝑐𝐵 𝐵−1 𝑁)𝑥𝑁

L’objectif de (P) est exprimé en fonction de 𝑥𝑁 (variables hors-base) uniquement

Les coefficients de 𝑥𝑁 sont les coûts réduits : 𝑐𝑁 − 𝑐𝐵 𝐵−1 𝑁

35
 Exemple
min 𝑧 = −𝑥1 − 2𝑥2
𝑥1 + 𝑥2 + 𝑥3 =3
𝑥1 + 𝑥4 =2
−𝑥1 + 𝑥2 + 𝑥5 = 1
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0

Prenons var. de base = x3, x4, x2

Donc hors-base = x1, x5

36
 Exemple (suite)
variables en base x3 , x4 , x2
variables hors-base x1 , x5
exprimons les variables de base en fonction des hors-base

1 0 1 1 0 1 0 −1 2 −1 2
−1 −1 −1
𝐵= 0 1 0 ,𝑁= 1 0 ,𝐵 = 0 1 0 ,𝐵 𝑁= 1 0 ,𝐵 𝑏 = 2
0 0 1 −1 1 0 0 1 −1 1 1

2𝑥1 + 𝑥3 −𝑥5 = 2
Ce qui donne le système: ൞ 𝑥1 + 𝑥4 =2
−𝑥1 𝑥2 + 𝑥5 = 1

37
 Exemple (suite)
Calculons les coûts réduits des variables hors-base x1 , x5

cB=(0 0 -2)
• Coût réduit de x1 = c1-cBB-1A1 (A1=colonne 1 de A)
2
-1-(0 0 -2) 1 =-1-2=-3
−1
• Coût réduit de x5 = c5-cBB-1A5 (A5=colonne 5 de A)
−1
0-(0 0 -2) 0 =0+2=2
1
2
• cBB b=(0 0 -2) 2 =-2
-1

D’où z = -2 -3x1 + 2x5

z = -2 sur la solution de base x3=2, x4 =2, x2=1, x1 =0, x5=0 (var. hors-base nulles)
38
 Algorithmes primal et dual du simplexe

Solution duale réalisable

𝑦𝐴 ≤ 𝑐 𝑦𝐵 ≤ 𝑐𝐵
ቊ →ቊ
𝑦𝑁 ≤ 𝑐𝑁

𝑐𝐵 𝐵−1 𝐵 ≤ 𝑐𝐵
En prenant 𝑦 = 𝑐𝐵 𝐵−1 , on obtient: ൝
𝑐𝐵 𝐵−1 𝑁 ≤ 𝑐𝑁

La première condition est toujours trivialement vérifiée.

La seconde est vérifiée si et seulement si 𝑐𝑁 − 𝑐𝐵 𝐵−1 𝑁 ≥ 0

La solution y est duale réalisable si et seulement si les coûts réduits sont positifs ou nuls

39
 Exemple (suite)

• Calculer y=cBB-1
1 0 −1
cB=(0 0 -2), 𝐵 −1 = 0 1 0
0 0 1

• Cet y satisfait-il les contraintes du dual ? Pouvait-on prévoir la réponse ?

40
Algorithmes primal et dual du simplexe

Résumé

1- La matrice B induit une solution dite de base : 𝑥𝐵 = 𝐵 −1 𝑏, 𝑥𝑁 = 0

La solution de base est primale réalisable (𝑥 ≥ 0) si et seulement si 𝐵 −1 𝑏 ≥ 0

2- La matrice B induit une solution 𝑦 = 𝑐𝐵 𝐵−1 duale réalisable

si et seulement si 𝑐𝑁 − 𝑐𝐵 𝐵−1 𝑁 ≥ 0 (coûts réduits ≥ 0)

3- Pour cette solution de base et cette solution y,

les objectifs du primal et du dual ont la même valeur = 𝑐𝐵 𝐵−1 𝑏

41
 Algorithmes primal et dual du simplexe

Algorithme primal
On passe de solution de base primale réalisable en solution de base primale réalisable
Et on stoppe dès que l’on a atteint une base B qui est duale réalisable (coûts réduits ≥ 0)

Algorithme dual
On passe de base duale réalisable en base duale réalisable
Et on stoppe dès que l’on a atteint une solution de base primale réalisable (𝐵−1 𝑏 ≥ 0)

42
Algorithmes primal et dual du simplexe
B’ et B adjacentes = ne diffèrent que d’une colonne

43
Algorithmes primal et dual du simplexe
Ecriture canonique de (P) relativement à une matrice de base B

min 𝑧 = 𝑐𝐵 𝐵−1 𝑏 + 𝑐𝑁 − 𝑐𝐵 𝐵−1 𝑁 𝑥𝑁

൞ 𝑥𝐵 + 𝐵 −1 𝑁𝑥𝑁 = 𝐵 −1 𝑏
𝑥𝐵 ≥ 0, 𝑥𝑁 ≥ 0

que l’on peut noter:

min 𝑧 = 𝑐𝐵 𝐵−1 𝑏 + ෍ ∆𝑗 𝑥𝑗
𝑗 ℎ𝑜𝑟𝑠−𝑏𝑎𝑠𝑒

𝑥𝑖 + ෍ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏ഥ𝑖 ∀𝑖 𝑒𝑛 𝑏𝑎𝑠𝑒

𝑗 ℎ𝑜𝑟𝑠−𝑏𝑎𝑠𝑒
𝑥𝐵 ≥ 0, 𝑥𝑁 ≥ 0
44
Algorithmes primal et dual du simplexe
Règles de pivotage (pour passer d’une base B à une base B’ adjacente)

Algorithme primal
Variable entrant dans la base
- Variable entrant dans la base : 𝑥𝑒 𝑡𝑒𝑙 𝑞𝑢𝑒 ∆𝑒 < 0 et le plus petit

Variable sortant de la base

- Si tous les 𝑎𝑖𝑒 ≤ 0 (dans la colonne e) alors minimum non borné (-)
(on peut augmenter indéfiniment la variable 𝑥𝑒 )
𝑏𝑖
Sinon variable 𝑥𝑠 sortant de la base où 𝑠 = argmin : ∀𝑖 𝑡. 𝑞. 𝑎𝑖𝑒 > 0
𝑖 𝑎𝑖𝑒
ത
(cette règle permet de maintenir le second membre 𝑏≥0)

45
Algorithmes primal et dual du simplexe

Règles de pivotage (pour passer d’une base B à une base B’ adjacente)

Algorithme dual
Variable sortant de la base
- Variable sortant de la base : 𝑥𝑠 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑏ത𝑠 < 0 et le plus petit

Variable entrant dans la base

- Si tous les 𝑎𝑠𝑗 ≥ 0 (dans la ligne s) alors primal non réalisable
(en ligne s, on a une équation avec membre gauche0 et membre droit <0)
∆𝑗
Sinon variable 𝑥𝑒 entrant dans la base où 𝑒 = argmax : ∀𝑗 𝑡. 𝑞. 𝑎𝑠𝑗 < 0
𝑗 𝑎𝑠𝑗
(cette règle permet de maintenir les coûts réduits ≥0)

46
 Exercice

min 𝑧 = 2𝑥1 + 3𝑥2

4𝑥1 + 𝑥2 ≥ 8
𝑥1 + 4𝑥2 ≥ 8
s.c
7𝑥1 + 10𝑥2 ≥ 47
𝑥1 ≥ 0, 𝑥2 ≥ 0

1-Mettre ce problème sous forme standard

2-Trouver une base duale réalisable évidente
3-Partant de cette base, résoudre le problème par l’algorithme dual du simplexe

47
 Annexes
• Dualité – Interprétation économique
• Ecarts complémentaires

48
Pb du pharmacien :
100g de poudre laboratoire 1 laboratoire 2 Il lui faut au moins
vitamine A 20 unités 5 unités 25 unités de vitamine A
vitamine B 30 unités 20 unités 60 unités de vitamine B
vitamine C 5 unités 10 unités 15 unités de vitamine C
coût 6 9

Un 3ème laboratoire décide de commercialiser les vitamines A, B, C séparément.

Il lui faut trouver le prix yA, yB, yC pour chaque unité de vitamine.
Pour être concurrentiel avec le laboratoire 1 il faut : 20yA+30yB+5yC6
Si le pharmacien achète la préparation du 3è laboratoire, il ne paiera pas plus cher que pour la potion
du laboratoire 1

49
Pb du pharmacien :
100g de poudre laboratoire 1 laboratoire 2 Il lui faut au moins
vitamine A 20 unités 5 unités 25 unités de vitamine A
vitamine B 30 unités 20 unités 60 unités de vitamine B
vitamine C 5 unités 10 unités 15 unités de vitamine C
coût 6 9

Un 3ème laboratoire décide de commercialiser les vitamines A, B, C séparément.

Il lui faut trouver le prix yA, yB, yC pour chaque unité de vitamine.
Pour être concurrentiel avec le laboratoire 1 il faut : 20yA+30yB+5yC6
Si le pharmacien achète la préparation du 3è laboratoire, il ne paiera pas plus cher que pour la potion
du laboratoire 1
Pour être concurrentiel avec le laboratoire 2 il faut : 5yA+20yB+10yC9.

50
Pb du pharmacien :
100g de poudre laboratoire 1 laboratoire 2 Il lui faut au moins
vitamine A 20 unités 5 unités 25 unités de vitamine A
vitamine B 30 unités 20 unités 60 unités de vitamine B
vitamine C 5 unités 10 unités 15 unités de vitamine C
coût 6 9

Un 3ème laboratoire décide de commercialiser les vitamines A, B, C séparément.

Il lui faut trouver le prix yA, yB, yC pour chaque unité de vitamine.
Pour être concurrentiel avec le laboratoire 1 il faut : 20yA+30yB+5yC6
Si le pharmacien achète la préparation du 3è laboratoire, il ne paiera pas plus cher que pour la potion
du laboratoire 1
Pour être concurrentiel avec le laboratoire 2 il faut : 5yA+20yB+10yC9.
Le laboratoire désire maximiser les gains en vendant ses vitamines au
pharmacien
maximiser 25 yA + 60 yB + 15 yC
51
Pb du pharmacien : se fournissant auprès des laboratoires 1 et 2
préparer sa potion à un moindre coût
min 6 x1  9 x2
 20 x1  5 x2  25
pb primal  30 x  20 x2  60
 1
s.c. 
 5 x1  10 x2  15
 x1  0 x2  0

Pb du concurrent des laboratoires 1 et 2 : trouver le juste prix des vitamines

max 25 y A  60 y B  15 y C
pb dual  20 y A  30 y B  5 yC 6

s.c.  5 y A  20 y B  10 y C 9
y  0 y  0 yC  0
 A B

52
 Ecarts complémentaires
Propriété.
Soit x une solution réalisable de (P) c’est-à-dire x vérifie les contraintes de (P) et
y une solution réalisable de (D) c’est-à-dire y vérifie les contraintes de (D).
x et y sont solutions optimales de (P) et (D) respectivement
si et seulement si y(Ax-b)=0 et (c-yA)x=0.

Vérifions la propriété sur le pb du pharmacien:

yA(20x1+5x2-25) +
yB(30x1+20x2-60) +
yC(5x1+10x2-15) + termes0 si la somme=0 ils sont tous nuls
x1(6-20yA-30yB-5yC) +
x2(9-5yA-20yB-10yC) =0

 6x1+9x2 -25yA-60yB-15yC= 0  l’objectif (P)=l’objectif de (D)  x et y solutions

de (P) et (D)

53
il résulte du théorème des écarts complémentaires que
une contrainte lâche (non saturée) correspond à une variable duale nulle
et ceci pour les 2 problèmes primal et dual

Exemple du problème pharmacien

Une solution de (P) x1 = 1, x2 = 3/2

Une solution de (D) yA = 1/5, yB = 1/30, yC = 1/5
La contrainte (vit.A) de (P) est non saturée (33,75 > 25) donc yA devrait être nulle
La contrainte (2) de (D) est non saturée (3+2/3 < 9) donc x2 devrait être nulle.
Ces solutions ne satisfont pas les écarts complémentaires donc non optimales

Une solution de (P) x1 = 3/2, x2 = 3/4

Une solution de (D) yA = 0, yB = 3/40, yC = ¾
Elles vérifient les écarts complémentaires donc optimales pour (P) et (D) respectivement

54
 Ecarts complémentaires

Exercice
Soit 𝑥 ≥ 0 satisfaisant les contraintes de (P)
et 𝑦 ≥ 0 satisfaisant les contraintes de (D)

Montrer que :

𝑐𝑥 = 𝑦𝑏 si et seulement si
𝑦 𝑏 − 𝐴𝑥 = 0 et 𝑐 − 𝑦𝐴 𝑥 = 0

55
 Interprétation des variables duales

Soit (P) pb de type minimiser et son dual (D).

A l ’optimum de (P) et (D) on a z*=v*=yb

De combien varie l ’optimum de (P)

lorsque b le second membre des contraintes varie ?

z*=yb si b pas trop grand

sinon z*yb les valeurs des var. duales y n ’étant plus optimales

Faisons varier un bi uniquement z*=yibi  z*bi=yi

yi représente le prix à payer quand on fait varier la contrainte i

56
 Exemple : si le pharmacien fait varier ses demandes en vitamines A, B, C

Solution du dual:
yA = 0 , yB = 340 , yC = 34 , v = 634

min z  6 x1  9 x2

  20 x1  5 x2  25 25+  z= yA   = 0  
P    30 x1  20 x2  60
s.c. 
  5 x1  10 x2  15 60+  z= yB   = 340  
 x  0 x  0
  1 2
15+  z= yC   = 34  

La vitamine A pas d’effet sur le coût, B un peu d’effet, C 10 fois plus d’effet

57