Forme matricielle Dualité Théorèmes

Programmation Linéaire - Cours 3

F. Clautiaux
[Link]@[Link]

Université Bordeaux 1
Bât A33 - Bur 265
Forme matricielle Dualité Théorèmes

Sommaire

Simplex : forme matricielle

Forme matricielle

Dualité

Dualité faible / forte

Forme matricielle Dualité Théorèmes

Notations matricielles
En forme standard :
max cx
s.c. Ax =b
x ≥ 0n+m
avec

c= (c1 c2 ... cn 0 0 ... 0)

|a1,1 a1,2 ... a1,n 1 | |b1 |

A= |a2,1 a2,2 ... a2,n 1 | b= |b2 |
. .. .. .. ..
|.. . . . | .
|am,1 am,2 ... am,n 1| |bm |

x= (x1 x2 ... xn xn+1 ... xn+m )

Forme matricielle Dualité Théorèmes

Partitionnement des indices

On peut partitionner les indices des variables en deux parties :
• Ceux des variables en base : B
• Ceux des variables hors-base : N
Cette partition peut-être effectuée dans chacune des contraintes :
Pn+m P P
j=1 ai,j xj = j∈B ai,j xj + j∈N ai,j xj = bi pour i = 1, . . . , n.

D’un point de vue matriciel : partition des colonnes de A et des

composantes des vecteurs c et x :

c = ( cB cN )
A = ( B N )
x = ( xB xN )
(on notera que B est une matrice carrée)
Forme matricielle Dualité Théorèmes

Dictionnaire au format matriciel

Exprimons les variables en base en fonction des variables

hors-base :
Ax = b ⇔ BxB + NxN = b
⇔ xB = B −1 b − B −1 NxN
Possible uniquement si B est une matrice inversible.
En remplaçant xB dans l’objectif, on obtient :
z = cx = cB xB + cN xN
= cB (B −1 b − B −1 NxN + cN xN
= cB B −1 b + (cN − cB B −1 N)xN

On a : max z = cB B −1 b + (cN − cB B −1 N)xN

s.c. xB = B −1 b − B −1 NxN
xB , xN ≥ 0
Forme matricielle Dualité Théorèmes

Solutions de base

Toute sous-matrice carrée m × m de A inversible (B est une base

de Rm ) est appelée matrice de base.
À chaque matrice de base B est associée une solution de base
définie par un dictionnaire.

max z = cB B −1 b + (cN − cB B −1 N)xN

s.c. xB = B −1 b − B −1 NxN
xB , xN ≥ 0

Solution de base : xB = B −1 b
z = cB B −1 b
Condition de réalisabilité : B −1 b ≥ 0
Condition d’optimalité : cN − cB B −1 N ≤ 0
Forme matricielle Dualité Théorèmes

Algorithme du simplex matriciel

On commence avec une solution de base réalisable donnée par un
dictionnaire :
max z = cB B −1 b + (cN − cB B −1 N)xN
s.c. xB = B −1 b − B −1 NxN
xB , xN ≥ 0

1. Si c̄N = cN − cB B −1 N ≤ 0, alors cette solution est optimale,

STOP.
2. choisir une variable entrante k ∈ N telle que (c̄N )k > 0.
3. Si (āi,k )i=1,...,m = (B −1 N)k ≤ 0, le problème est non borné,
STOP.
4. Choisir une variable sortante s ∈ B telle que
 −1

b̄j Bj,. b
s = argminj∈B āj,k = B −1 N : āj,k > 0
j,. .,k

5. Pivoter : B = (B \ {s}) ∪ {k} et N = (N \ {k}) ∪ {s} et

retourner en 1.
Forme matricielle Dualité Théorèmes

Sommaire

Simplex : forme matricielle

Dualité
Motivation
Primal / dual

Dualité faible / forte

Forme matricielle Dualité Théorèmes

Motivation

Obtenir une borne supérieure sur le profit maximum

• Toute solution réalisable donne une borne inférieure (LB)

sur le profit maximum.
• Une borne supérieure (UB) est utile pour juger de la qualité
d’une solution réalisable (voire prouver son optimalité si LB =
UB).

Remarque :
Toute combinaison linéaire de contraintes du programme linéaire
donne une contrainte valide (satisfaite par toutes les solutions
réalisables)
Forme matricielle Dualité Théorèmes

Exemple du yaourt

max 4x1 + 5x2

2x1 + x2 ≤ 800 (1)
x1 + 2x2 ≤ 700 (2)
x2 ≤ 300 (3)
x1 , x2 ≥0
Forme matricielle Dualité Théorèmes

Exemple du yaourt

max 4x1 + 5x2

2x1 + x2 ≤ 800 (1)
x1 + 2x2 ≤ 700 (2)
x2 ≤ 300 (3)
x1 , x2 ≥0

5 ∗ (1) ⇒ 4x1 + 5x2 ≤ 10x1 + 5x2 ≤ 4000

4 ∗ (2) ⇒ 4x1 + 5x2 ≤ 4x1 + 8x2 ≤ 2800
2 ∗ (1) + 3 ∗ (3) ⇒ 4x1 + 5x2 ≤ 2500
Forme matricielle Dualité Théorèmes

Deuxième exemple

(le PL n’est pas sous forme normale)

max 4x1 + 2x2 −x3

x1 + x2 + x3 ≤ 10 (1)
x2 + x3 ≥6 (2)
x1 −x3 ≥0 (3)
x1 , x2 x3 ≥0

Par exemple 2 ∗ (1) − 2 ∗ (3)

Forme matricielle Dualité Théorèmes

Modélisation du problème

Problème : Trouver les meilleurs coefficients multiplicatifs pour

chaque contrainte afin d’obtenir la meilleure borne supérieure.
• A chaque contrainte i = 1, . . . , 3, on associe une variable yi .
• La combinaison linéaire doit être telle que le coefficient
obtenu pour chaque variable doit être plus grand que le
coefficient de la variable dans l’objectif.
• On cherche à minimiser le membre de droite de la contrainte
issue de la combinaison linéaire.
Forme matricielle Dualité Théorèmes

Modélisation du problème

Max 4x1 + 5x2

2x1 + x2 ≤ 800 (y1 )
x1 + 2x2 ≤ 700 (y2 )
x2 ≤ 300 (y3 )
x1 , x2 ≥0
Forme matricielle Dualité Théorèmes

Modélisation du problème

Max 4x1 + 5x2

2x1 + x2 ≤ 800 (y1 )
x1 + 2x2 ≤ 700 (y2 )
x2 ≤ 300 (y3 )
x1 , x2 ≥0

Min 800y1 + 700y2 + 300y3

2y1 + y2 ≥4
y1 + 2y2 + y3 ≥5
y1 , y2 , y3 ≥0
Forme matricielle Dualité Théorèmes

Modélisation du problème

Max 4x1 + 5x2

2x1 + x2 ≤ 800 (y1 )
x1 + 2x2 ≤ 700 (y2 )
x2 ≤ 300 (y3 )
x1 , x2 ≥0

Min 800y1 + 700y2 + 300y3

2y1 + y2 ≥4
y1 + 2y2 + y3 ≥5
y1 , y2 , y3 ≥0

Solution optimale : y1∗ = 1, y2∗ = 2, y3∗ = 0 et opt = 2200.

Forme matricielle Dualité Théorèmes

Primal / Dual

Les PL vont toujours par paires :

Primal :
P
max cx
Pj j j
s.c. j ai,j xj ≤ bi pour i = 1, . . . , m
xj ≥ 0 pour j = 1, . . . , n

Dual :
P
min Pi bi yi
s.c. i ai,j yi ≥ cj pour j = 1, . . . , n
yi ≥ 0 pour i = 1, . . . , m

A venir : si solutions optimales alors égales

Forme matricielle Dualité Théorèmes

Primal / Dual : forme matricielle

Les PL vont toujours par paires :

Primal :

max cx
s.c. Ax ≤b
x ≥ 0n

Dual :

min by
s.c. A> y ≥c
y ≥ 0m
Forme matricielle Dualité Théorèmes

Interprétation économique du dual

• Sans ressource, le profit serait nul. L’idée est d’essayer

d’évaluer la contribution de chaque ressource au profit
observé. Dans ce contexte, les variables
yi ≥ 0 pour i = 1, . . . , m
représentent les valeurs unitaires des ressources i : yi est la
mesure de la contribution d’une unité de i dans le profit. C’est
donc aussi le prix auquel on évalue la ressource i (prix auquel
on serait prêt à vendre la ressource au lieu de l’utiliser).
Forme matricielle Dualité Théorèmes

Interprétation économique du dual

• Un système de prix y (auquel on serait prêt à vendre nos

ressources) pour être acceptable doit compenser le profit
qu’on aurait pu faire en utilisant ces ressources. Il faut
P
i ai,j yi ≥ cj pour j = 1, . . . , n
ce qu’on interprète aussi comme le fait que la valeur des
ingrédients doit justifier entièrement le profit attribué à
chaque produit.
Forme matricielle Dualité Théorèmes

Interprétation économique du dual

• Un système de prix y (auquel on serait prêt à vendre nos

ressources) pour être acceptable doit compenser le profit
qu’on aurait pu faire en utilisant ces ressources. Il faut
P
i ai,j yi ≥ cj pour j = 1, . . . , n
ce qu’on interprète aussi comme le fait que la valeur des
ingrédients doit justifier entièrement le profit attribué à
chaque produit.
• L’acheteur de nos ressources veillera à minimiser le coût total
d’achat
P
Minimiser i bi y i
Forme matricielle Dualité Théorèmes

Int. éco. de la solution optimale du dual

A l’optimum :

z ∗ = j cj xj∗ b y∗
P P
=
P ∗
Pi i i ∗
j ai,j xj ≤ bi et i ai,j yi ≥ cj
Forme matricielle Dualité Théorèmes

Int. éco. de la solution optimale du dual

A l’optimum :

z ∗ = j cj xj∗ b y∗
P P
=
P ∗
Pi i i ∗
j ai,j xj ≤ bi et i ai,j yi ≥ cj

• Les multiplicateurs optimaux (solution optimale du dual)

expliquent la responsabilité de chacune des contraintes de
capacité en ressource dans la limitation du profit.
• Ces valeurs duales indiquent “localement” de combien
augmenterait le profit par unité d’augmentation des ressources
associées.
• yi∗ est une mesure de l’augmentation marginale du profit par
unité d’augmentation de bi .
∗ (b ∗ (b
yi∗ = lim→0 z i +)−z

i)
Forme matricielle Dualité Théorèmes

Théorème
Si le problème
 P
 max cx
P j j j
P s.c. j i,j xj
a ≤ bi i = 1, . . . , m
≥ 0

xj j = 1, . . . , n
admet une solution de base optimale non dégénérée de valeur z ∗ ,
alors ∃ > 0 tel que si |ti | ≤  pour i = 1, . . . , m, le problème
 P
 max P j cj xj
P0 s.c. j ai,j xj ≤ bi + ti i = 1, . . . , m
xj ≥ 0

j = 1, . . . , n
admet une solution optimale dont la valeur est

z∗ + m ∗
P
i=1 ti yi

où y ∗ est la solution (unique) au problème dual.

Forme matricielle Dualité Théorèmes

Retour dans le yaourt

Max 4x1 + 5x2

2x1 + x2 ≤ 800 Min 800y1 + 700y2 + 300y3
x1 + 2x2 ≤ 700 2y1 + y2 ≥4
x2 ≤ 300 y1 + 2y2 + y3 ≥5
x1 , x2 ≥0 y1 , y2 , y3 ≥0

Solution optimale : y1∗ = 1, y2∗ = 2, y3∗ = 0 et UB = 2200.

Prix de vente minimum d’une unité de ressource 1 : 1 euro.
Prix de vente minimum d’une unité de ressource 2 : 2 euros.
Prix de vente minimum d’une unité de ressource 3 : 0 euro.
Forme matricielle Dualité Théorèmes

Si le primal n’est pas borné

max5x + 3y
3x + y ≥ 3
x ≤5
x, y ≥ 0
Forme matricielle Dualité Théorèmes

Relations Primal / Dual

• Le dual du dual est le primal.

DUAL
optimal irréalisable non-borné
optimal possible impossible impossible
PRIMAL irréalisable impossible possible possible
non-borné impossible possible impossible

• On peut appliquer le simplex au dual au lieu du primal si le

dual a moins de contraintes que le primal (cf complexité
empirique du simplex).
Forme matricielle Dualité Théorèmes

Passage du primal au dual

Il n’est pas nécessaire de passer en forme normale pour écrire le
dual d’un programme linéaire.

Tableau de passage :

Primal (Max) Dual (Min)

Contraintes Variables
≤ ≥0
≥ ≤0
= non restreinte
Variables Contraintes
≥0 ≥
≤0 ≤
non restreinte =
Forme matricielle Dualité Théorèmes

Passage du primal au dual : exemple

max5x − 3y + 5z
x +y =2
2y + 3z ≤ 10
x + 5z ≥ 5
x ≤0
y, z ≥ 0

Cf. forme matricielle

Forme matricielle Dualité Théorèmes

Sommaire

Simplex : forme matricielle

Dualité

Dualité faible / forte

Forme matricielle Dualité Théorèmes

Dualité faible
Théorème
Dualité faible : Pour toute solution réalisable x du problème
primal et toute solution réalisable y du problème dual, on a
n
X m
X
cj xj ≤ bi yi .
j=1 i=1

Preuve :
On sait que Pm
P
i=1 aij yi ≥ cj , ∀j.
On sait que nj=1 aij xi ≤ bi , ∀i.
Pn Pn Pm
j=1 cj xj ≤ j=1 ( i=1 ai,j yi )xj

Pm Pn= Pm
i=1 ( j=1 ai,j xj )yi ≤ i=1 bi yi
Forme matricielle Dualité Théorèmes

Dualité faible

Corollaire
Si x̄ est une solution réalisable du problème primal et ȳ une
solution réalisable du problème dual tel que
Pn Pm
j=1 cj x̄j = i=1 bj ȳj ,

alors x̄ est optimale pour le primal et ȳ est optimale pour le dual.

Forme matricielle Dualité Théorèmes

Dualité faible

Preuve :
Supposons au contraire que x̄ n’est pas une solution optimale du
primal. Il existe donc une solution x ∗ telle que
Pn Pn ∗
j=1 cj x̄j < j=1 cj xj .

On a alors
Pm Pn ∗
i=1 bj ȳj < j=1 cj xj

ce qui est contraire au théorème de dualité faible.

La solution x̄ est donc optimale.

La preuve est similaire pour ȳ .

Forme matricielle Dualité Théorèmes

Dualité forte

Théorème
Dualité forte : Si le primal a une solution optimale
x ∗ = (x1∗ , . . . , xn∗ ), alors le dual a une solution optimale
y ∗ = (y1∗ , . . . , ym∗ ) telle que

n
X m
X
cj xj∗ = bi yi∗ .
j=1 i=1

Idée pour la preuve :

z ∗ = cB B −1 b = cx ∗
Forme matricielle Dualité Théorèmes

Dualité forte

Théorème
Dualité forte : Si le primal a une solution optimale
x ∗ = (x1∗ , . . . , xn∗ ), alors le dual a une solution optimale
y ∗ = (y1∗ , . . . , ym∗ ) telle que

n
X m
X
cj xj∗ = bi yi∗ .
j=1 i=1

Idée pour la preuve :

z ∗ = cB B −1 b = cx ∗ = y ∗ b
On devine qu’on doit avoir
(y1∗ , . . . , ym
∗ ) = c B −1 .
B

On va montrer que cette solution est réalisable et optimale pour le

dual.
Forme matricielle Dualité Théorèmes

Preuve dualité forte

Remarque sur les coûts réduits :

c̄x = (cB − cB B −1 B)xB + (cN − cB B −1 N)xN

Comme tous les coûts réduits sont négatifs ou nuls on a

cN − cB B −1 N ≤ 0 et donc cB B −1 N ≥ cN .
On a aussi cB B −1 B ≥ cB
Forme matricielle Dualité Théorèmes

Preuve dualité forte

Si on regroupe les indices entre var. de décision (AD ) et var.

d’écart (I ), on a :
cB B −1 AD ≥ c
cB B −1 I ≥ 0
On obtient directement y ∗ A ≥ c et y ∗ ≥ 0, qui sont les conditions
de réalisabilité du dual.
De plus : y ∗ b = cB B −1 b = cx ∗ .
Par le corollaire précédent, y ∗ est une solution optimale du dual.
Forme matricielle Dualité Théorèmes

Utilité de la dualité forte

Si on a une paire (x ∗ , y ∗ ) de solutions du primal et du dual, on

peut facilement vérifier
• la réalisabilité de x ∗ pour le problème primal,
• la réalisabilité de y ∗ pour le problème dual,
• l’égalité des deux objectifs.

On a alors un certificat d’optimalité pour la paire (x ∗ , y ∗ ).