UNIVERSITÉ ABDELMALEK ESSAADI

Recherche Opérationnelle

Mohammed Bouchangour

May 13, 2023 FSTH, El Hoceïma

Dualité
 Introduction
Exemple
2

Une entreprise fabrique deux produits P1 et P2 .

M. Bouchangour | Recherche Opérationnelle

 Introduction
Exemple
2

Une entreprise fabrique deux produits P1 et P2 .La fabrication de

chaque produit nécessite trois ressources A, B et C disponibles en
quantités données.
L’entreprise cherche à maximiser le bénéfice total provenant de la
vente des deux produits.

M. Bouchangour | Recherche Opérationnelle

 Exemple
4

Le programme linéaire correspondant est



 Max z = 6x1 + 4x2



 4x1 + 9x2 ≤ 81

(PL) 4x1 + 5x2 ≤ 55



 2x1 + x2 ≤ 20


 x1 , x2 ≥ 0.

M. Bouchangour | Recherche Opérationnelle

 Forme standard d’un Programme Linéaire
5

Supposons à présent qu’un acheteur se présente pour acheter toutes

les ressources de l’entreprise. Il propose à l’entreprise les prix
unitaires y1 , y2 , y3 pour chacune des ressources.

Quels prix unitaires y1 , y2 , et y3 , l’acheteur doit-il proposer à

l’entreprise en question pour qu’elle accepte de vendre toutes ses
ressources?

L’entreprise acceptera de lui vendre toutes ses ressources

uniquement si elle obtient, pour chaque produit, un prix de vente
supérieur ou égal au profit qu’elle ferait en vendant ses produits.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
6

1 Pour le produit P1

• La valeur du paquet des RESSOURCES qui entre dans la

production d’une unité du produit P1 ?

La production d’une unité du produit P1 nécessite:

▶ 3 unités de la ressource A,
▶ 4 unités de la ressource B,
▶ 2 unités de la ressource C.
L’acheteur propose:
▶ y1 pour acheter 1 unité de A,

▶ y2 pour acheter 1 unité de B,

▶ y3 pour acheter 1 unité de C.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
7

La valeur de ce paquet des ressources consommées par le produit

P1 est donc:
3y1 + 4y2 + 2y3
• Le bénéfice provenant d’une unité du PRODUIT P1 ?

Ce bénéfice est : 6

L’entreprise n’acceptera pas de céder ce paquet de ressources pour

moins de 6. L’acheteur devra donc fixer les prix offerts pour les
ressources de l’entreprise de façon à ce que:

3y1 + 4y2 + 2y3 ≥ 6.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
8

2 Pour le produit P2
Similairement à ce qui précède, on écrit

9y1 + 5y2 + y3 ≥ 4.

Bien sur avec

y1 ≥ 0, y2 ≥ 0 et y3 ≥ 0.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
9

De son coté, l’acheteur cherche à minimiser le prix total d’achat des

ressources A (81), B (55), C (20).

Minw = 81y1 + 55y2 + 20y3 .

Finalement, pour déterminer les prix unitaires minimaux qu’il

proposera à l’entreprise, l’acheteur devrait résoudre le programme
linéaire suivant:


 Min w = 81y1 + 55y2 + 20y3

 3y1 + 4y2 + 2y3 ≥6
(PLD)

 9y1 + 5y2 + y3 ≥4


y1 , y2 , y3 ≥ 0.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
10

Les problèmes (PL) et (PLD) utilisent en fait exactement les mêmes

données numériques. On peut les lire directement à partir du tableau
ci-dessous;
(P) correspond à une lecture ligne par ligne, (D) à une lecture
colonne par colonne.

M. Bouchangour | Recherche Opérationnelle

 Primal & Dual
12

La dualité associe à tout problème linéaire un autre problème linéaire

qui est appelé problème dual du problème initial; par opposition le
problème initial est appelé problème primal.

M. Bouchangour | Recherche Opérationnelle

 Forme standard
13

Considérons un problème de maximisation sous forme canonique:

 ∑n

 Max ∑ z = j=1 cj xj
n
(PL)
 j=1 ai,j xj ≤ bi i = 1, . . . , m

xj ≥ 0 j = 1, . . . , n.

Le problème dual est le suivant:

 ∑m

 Min w = bi yi
∑n i=1
(PLD)
 i=1 i,j i ≥ cj j = 1, . . . , n
a y

yi ≥ 0 i = 1, . . . , m.

M. Bouchangour | Recherche Opérationnelle

 Règles de dualisation
14

M. Bouchangour | Recherche Opérationnelle

 Dualisation de programme linéaire sous forme
canonique 15

M. Bouchangour | Recherche Opérationnelle

 Dualisation de programme linéaire sous forme
canonique 16

Remarque
1. Le dual d’un problème linéaire de minimisation est un problème
linéaire de maximisation.
2. Le dual du problème dual est le problème primal.
3. Le programme linéaire initial doit être mis sous forme canonique
avant de déterminer son dual.

M. Bouchangour | Recherche Opérationnelle

 Exercice
17

Donner le PL dual associé aux PL primale suivant:



 Min z = 3x1 + 4x2



 x1 + 4x2 ≥ 8

2x1 + 3x2 ≥ 12



 2x1 + x2 ≥ 6


 x1 , x2 ≥ 0.

M. Bouchangour | Recherche Opérationnelle

Propriétés de la dualité
 Dualité forte
19

Théorème
Le primal possède une solution optimale (x1∗ , . . . , xn∗ )
si et seulement si
le dual possède une solution optimale (y1∗ , . . . , ym∗ ).

Dans ce cas, les fonctions objectifs z et w ont la même valeur

optimale,

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

M. Bouchangour | Recherche Opérationnelle

 Théorème des écarts complémentaires
20

Théorème
Soit (x1∗ , . . . , xn∗ ) une solution réalisable d’un problème primale. Alors
(x1∗ , . . . , xn∗ ) est optimale si et seulement si, il existe (y1∗ , . . . , ym∗ ) tel
que (y1∗ , . . . , ym∗ ) est une solution réalisable du problème duale,

∑
n
cj xj∗ ≤ bi ⇒ yi∗ = 0, ∀i = 1, . . . , m
j=1

et
∑
m
xj∗ > 0 ⇒ ai,j yi∗ = cj , ∀j = 1, . . . , n.
i=1

M. Bouchangour | Recherche Opérationnelle

 Théorème des écarts complémentaires
21

Autrement-dit:
▶ La i ème contrainte primale n’est pas saturée ⇒ la i ème variable
(de décision) duale est nulle.
▶ La j ème variable (de décision) primale est non nulle ⇒ la j ème
contrainte duale est saturée.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
22

Appliquons le TEC au problème linéaire suivant:




 Max z = 15x1 + 25x2


 x1 + 3x2 ≤ 96

(PL) x1 + x2 ≤ 40



 7x1 + 4x2 ≤ 238


 x1 , x2 ≥ 0.

Soit la solution primale x1 = 0 et x2 = 32. Cette solution est elle

optimale ?

M. Bouchangour | Recherche Opérationnelle

 Exemple:
23

Le problème linéaire dual de (PL) est:



 Min w = 96y1 + 40y2 + 238y3

 y1 + y2 + 7y3 ≥ 15
(PL)

 3y + y2 + 4y3 ≥ 25


1
y1 , y2 , y3 ≥ 0.

Cherchons y1 , y2 et y3 vérifiant le théorème des écarts

complémentaires. S’ils existent alors la solution primale proposée est
optimale. Sinon alors la solution primale proposée n’est pas optimale.

M. Bouchangour | Recherche Opérationnelle

 Exemple:
24

1 On a:

• La 2ème contrainte primale n’est pas saturée ⇒ la 2ème variable

duale est nulle. D’où: y2 = 0.

• La 3ème contrainte primale n’est pas saturée ⇒ la 3ème variable

duale est nulle. D’où: y3 = 0.

2 La 2ème variable primale n’est pas nulle ⇒ la 2ème contrainte duale

est saturée. Ainsi:

3y1 + y2 + 4y3 = 25
⇒ 3y1 = 25 car y2 = y3 = 0
25
⇒ y1 =
3

M. Bouchangour | Recherche Opérationnelle

 Exemple:
25

3 Cette solution y2 = y3 = 0, y1 = 25/3 ne satisfait pas la 1ère

contrainte duale y1 + y2 + 7y3 ≥ 15.

Et par suite elle nest pas réalisable.

La solution primale précédente x1 = 0, x2 = 32 n’est donc pas

optimale.

M. Bouchangour | Recherche Opérationnelle

 Exercice:
26

Vérifier que (x1 , x2 , x3 , x4 ) = (3, 0, 7, 0) est une solution réalisable

optimale en appliquant le Théorème des écarts complémentaires.


 Max z = 7x1 + 9x2 + 18x3 +17x4



 2x1 + 4x2 +5x3 +7x4 ≤ 42

x1 + x2 + 2x3 +2x4 ≤ 17



 x1 + 2x2 + 3x3 +3x4 ≤ 24


 x1 , x2 , x3 x4 ≥ 0.

M. Bouchangour | Recherche Opérationnelle

Merci pour votre attention