Recherche Opérationnelle
La dualité
3_Dual: Dual d’un programme linéaire
Exercice 3_Dual: Dual d’un programme linéaire
Exercice
• Le concept de dualité consiste à considérer un même
problème d’optimisation sous deux angles :
(cid:1) sous l’angle des activités;
(cid:1) et sous l’angle des ressources.
• A tout programme linéaire nous pouvons en effet faire
correspondre un autre programme, intrinsèquement lié au
premier, que l’on appellera programme dual.
• Le premier programme considéré sera appelé programme
primal.
Pour situer, très schématiquement la relation entre programme
primal et programme dual, on peut dire que, si le primal vise la
maximisation d’un profit sous des contraintes de disponibilité
des ressources, alors le dual vise la minimisation des coûts de
ressources,
sous des contraintes de contribution de ces
ressources à la production économique de l’exploitation.
Problème Primal
Problème Primal
Problème Dual
Problème Dual
ZMax
=
n
∑
=
1
j
j xc
j
Min
W
=
m
∑
=
1
i
ib
l
i
j
Advertisement
b
i
,
L=
,2,1
,
m
i
m
∑
=
1
i
a
ij
l
i
c
j
,
L=
,2,1
,
n
j
n
∑
=
1
j
xa
ij
xj
,0
L=
,2,1
,
n
j
‡
‡
£
Exemple
• Une famille utilise 6 produits alimentaires comme source de
vitamine A et C. le tableau suivant indique les valeurs
nutritionnelles de chaque produit du vitamine A et C ainsi que
Advertisement
le coût respectif par kg
Problème Primal
• Le but de la famille étant de minimiser le coût
de son régime alimentaire tout en satisfaisant
les besoins nutritionnels
• Modélisation
• Modélisation
(cid:1)(cid:2)(cid:3) (cid:5) = (cid:7)(cid:8)(cid:9)(cid:10) + (cid:7)(cid:12)(cid:9)(cid:13) + (cid:14)(cid:12)(cid:9)(cid:7) + (cid:8)(cid:12)(cid:9)(cid:15) + (cid:13)(cid:16)(cid:9)(cid:8) + (cid:13)(cid:13)(cid:9)(cid:14)
S/C (cid:9)(cid:10) + (cid:13)(cid:9)(cid:7) + (cid:13)(cid:9)(cid:15) + (cid:9)(cid:8) + (cid:13)(cid:9)(cid:14) ≥ (cid:18)
(cid:9)(cid:13) + (cid:7)(cid:9)(cid:7) + (cid:9)(cid:15) + (cid:7)(cid:9)(cid:8) + (cid:13)(cid:9)(cid:14) ≥ (cid:10)(cid:18)
(cid:9)(cid:19) ≥ (cid:12);(cid:19) = (cid:10),…,(cid:14)
Problème Dual
• Un producteur de cachets de vitamine synthétique veut convaincre la
famille d'acheter ses vitamines.
• Quel prix de vente (cid:23)1 et (cid:23)2 pour être compétitif Et maximiser le profit ?
• Modélisation
(cid:1)(cid:24)(cid:9) (cid:25) = (cid:18)(cid:23)1 + (cid:10)(cid:18)(cid:23)(cid:13)
S/C (cid:23)(cid:10) ≤ (cid:7)(cid:8)
(cid:23)(cid:13) ≤ (cid:7)(cid:12)
2(cid:23)(cid:10) + (cid:7)(cid:23)(cid:13) ≤ (cid:14)(cid:12)
2(cid:23)(cid:10) + (cid:23)(cid:13) ≤ (cid:8)(cid:12)
(cid:23)(cid:10) + (cid:7)(cid:23)(cid:13) ≤ (cid:13)(cid:16)
2(cid:23)(cid:10) + (cid:13)(cid:23)(cid:13) ≤ 2
(cid:23)(cid:2) ≥ (cid:12); (cid:2) = (cid:10), 2
Exemple à résoudre par la méthode du simplexe
(cid:1)(cid:24)(cid:9) (cid:5) = (cid:8)(cid:9)(cid:10) + (cid:7)(cid:9)(cid:13)
S/C (cid:7)(cid:9)(cid:10) + (cid:8)(cid:9)(cid:13) ≤ (cid:10)(cid:8)
La forme standard
(cid:8)(cid:9)(cid:10) + (cid:13)(cid:9)(cid:13) ≤ (cid:10)(cid:12)
(cid:9)(cid:19) ≥ (cid:12); (cid:19) = (cid:10), (cid:13)
(cid:9)(cid:19) ≥ (cid:12); (cid:19) = (cid:10), (cid:13)
(cid:1)(cid:24)(cid:9) (cid:5) = (cid:8)(cid:9)(cid:10) + (cid:7)(cid:9)(cid:13)
S/C (cid:7)(cid:9)(cid:10) + (cid:8)(cid:9)(cid:13) + (cid:29)(cid:10) = (cid:10)(cid:8)
(cid:8)(cid:9)(cid:10) + (cid:13)(cid:9)(cid:13) + (cid:29)(cid:13) = (cid:10)(cid:12)
(cid:9)(cid:19); (cid:29)(cid:2) ≥ (cid:12); (cid:19) = (cid:10), (cid:13) ; i=1,2
Premier tableau du Simplexe
Variables
X1
X2
E1
E2
Solution
bi/aik
Cj
Base
E1
Advertisement
E2
5
3
5
3
5
2
0
1
0
0
0
1
0
15
10
15/3=5
10/5=2
Deuxième tableau du Simplexe
Variables
X1
Cj
Base
E1
X1
0
0
1
X2
1
19/5
2/5
E1
0
1
0
E2
-1
-3/5
1/5
Solution
bi/aik
10
9
2
9*5/19
Advertisement
2*5/2
Le coefficient associé à x2 demeure encore positif (1). En plus les coefficients de la
deuxième colonne ne sont pas tous négatifs ou nuls; ce qui implique que la solution
n'est pas optimale mais que on peut avoir une solution optimale lors des itérations
suivantes:
Troisième tableau du Simplexe
Variables
X1
X2
E1
E2
Solution
bi/aik
Cj
Base
X2
X1
0
0
1
0
1
0
-5/19
-16/19
235/19
5/19
-3/19
45/19
-2/19
5/19
20/19
La base optimale est {x1,x2,}={20/19,45/19}==> Z= 520/19+3*45/19=235/19
Dual
(cid:1)(cid:2)(cid:3) (cid:25) = (cid:10)(cid:8)(cid:23)1 + (cid:10)(cid:12)(cid:23)(cid:13)
S/C (cid:7)(cid:23)(cid:10) + (cid:8)(cid:23)(cid:13) ≥ (cid:8)
(cid:8)(cid:23)(cid:10) + (cid:13)(cid:23)(cid:13) ≥ (cid:7)
(cid:8)(cid:23)(cid:10) + (cid:13)(cid:23)(cid:13) ≥ (cid:7)
(cid:23)(cid:10); (cid:23)(cid:13) ≥ (cid:12)
(cid:23)(cid:10); (cid:23)(cid:13) ≥ (cid:12)
W= 155/19+1016/19=235/19