Chapitre 7

Dualité en programmation linéaire

Introduction

Dans ce chapitre on va voir comment on peut, à partir d'un programme linéaire donné (qui sera
appelé programme primal), construire un autre programme linéaire appelé programme dual. Entre
ces deux programmes il y a des liens très étroits : si un des deux a une solution optimale l'autre en
possède également une et les valeurs optimales des deux programmes coïncident. Des fois la
résolution du problème dual peut être plus simple que celle du problème primal (par exemple on
connaît une solution de base admissible pour le dual et on peut démarrer directement le simplexe,
tandis que pour le primal on est obligés d'utiliser les deux phases).
En plus de l'intérêt mathématique ou numérique pour l'étude du problème dual, un aspect autre très
important est l'interprétation économique des variables duales. Ces variables représentent des coûts
marginaux et peuvent être considérées comme l'augmentation maximale du revenu, par rapport à la
solution optimale, qui résulterait de l'utilisation d'une unité supplémentaire de l'un des biens.
Etant donné un PL du type,

on peut considérer qu’il concerne une entreprise E1 fabricant n biens j, j ∈{1, . . . , n} et faisant
intervenir m ressources i, i ∈ {1, . . . , m}. Le problème que peut se poser l’entreprise est le suivant :
Etant donnée la disponibilité bi pour chaque ressource i et le profit unitaire cj pour chacun des biens
j, quel doit être le niveau de production de chaque bien j pour que la quantité de bien i consommée
reste inférieure à la disponibilité bi et que le profit total soit maximal?
Supposons qu’une autre entreprise E2, en rupture de stock, désire racheter les ressources de la
première, le problème qu’elle va se poser et le suivant : Etant donné un prix unitaire cj pour chacun
n biens j et une disponibilité bi pour chacune des m ressources i, quel doit être le prix unitaire
minimum d’achat yi de chaque ressource i pour que la valeur totale des ressources consommées par
chaque bien j soit supérieure ou égale à cj (pour que cela rester intéressant pour l’entreprise E1 et
que le prix total d’achat des ressources disponible soit minimum?
Ce deuxième problème constitue le problème dual du premier, il peut se mettre sous la forme :
On voit aisément que les contraintes,

impliquent que le prix d’achat des ressources par l’entreprise E2 reste supérieur au profit que peut
en tirer l’entreprise E1, c’est à dire,

ce qui est conforme aux lois de l’économie, on voit donc intuitivement que le minimum atteint par
le deuxième problème doit être égal au maximum du premier problème. La théorie montre que c’est
le cas quand le problème a des solutions.

La construction du programme dual

Considérons un programme linéaire sous la forme canonique appelée programme primal :

Le programme dual a m variables notées ¸y1,…., ym on va ranger ces variables sous la forme d'un
vecteur ligne. A noter la différence par rapport aux variables primales qui sont données sous la
forme d’un vecteur colonne x. Alors le programme dual s’écrit sous forme matricielle :

Min w = Y b
YA≥ c
Y ≥ 0

Ou encore,
On constate la correspondance suivante entre les deux problèmes :

Problème primal Problème dual

maximisation minimisation
n variables (vecteur colonne) n contraintes
m contraintes m variables (vecteur ligne)
variable nº j ≥ 0 contrainte nº j ≥
contrainte nº i ≤ variable nº i ≥ 0
(ligne de) coefficients fonction objectif second membre
second membre (colonne de) coefficients fonction objectif

Enfin, on peut constater facilement que le dual du problème dual c'est le problème primal.

Exemple

Remarque : Le PL initial doit être mis sous forme canonique avant de déterminer son dual, ainsi
dans l’exemple qui suit,
Min (Z) = −2x1 + 4x2

On aura,
Propriétés de la dualité

On démontre facilement les résultats suivants:

– Le dual du problème dual c'est le problème primal.

– Si le primal est non borné, le dual est contradictoire. Si le primal est contradictoire, le
dual est non borné ou contradictoire. Si le primal admet une solution finie x* alors le dual
admet une solution optimale finie y* qui vérifie : z(x*) = w(y*).
– A toute variable d’écart primale (resp. duale) positive correspond une variable
structurelle duale (resp. primale) nulle. A toute variable structurelle primale (resp. duale)
positive correspond une variable d’écart duale (resp. primale) nulle. On note, xj (resp. yi)les
variables structurelles du primal (resp. dual) et ti (resp. uj) les variables d’écart du primal
(resp. dual).

Théorème : Soit y une solution admissible du dual et x une solution admissible

du primal. Alors on a z = cx ≤ yb = w
Autrement dit chaque valeur admissible du dual est un majorant pour chaque valeur
admissible du primal.

Démonstration. Soit x tel que Ax ≤ b; x ≥ 0 et soit y vérifiant yA ≥ c ; y ≥ 0: On a

z = cx ≤ y Ax ≤ y b = w

Corollaire 1. Soit x* une solution admissible du primal, et y* une solution admissible du

dual. Si c x* = y*b, alors x* est une solution optimale de (P) et y* une solution optimale de
(D).

A noter que la réciproque n'est pas évidente, à savoir que si x* est une solution optimale du
primal et y* une solution optimale du dual alors les valeurs optimales coïncident. C'est
l'objet du théorème suivant qui est un résultat central de la programmation linéaire.

Théorème : Si le problème primal (P) a une solution optimale x* alors le problème dual (D)
a une solution optimale y* et les valeurs optimales coïncident, c x* = y*b
Autrement dit z* = w*.

Passage du dernier tableau simplexe du primal au dernier tableau simplexe du

dual :
Au signe près, on a les correspondances suivantes :

Variable de base xj (resp. hors base tj) variable hors base uj (resp. de base yj)
ligne xj (resp. ti) en base colonne uj (resp.yi) hors base.
colonne xj (resp. ti) hors base ligne uj (resp.yi) en base.
ligne cj − zj (primal) ligne zi − bi.

Exemple

x1 x2 t1 t2 t3 B
x2 1 0 3/5 -1/5 0 6
x1 0 1 2/5 1/5 0 8
t3 0 0 -4/5 3/5 1 8
Z 0 0 -9/5 -2/5 0 30

En utilisant les correspondances ci-dessus, on obtient le dernier tableau simplexe du dual suivant:

y1 y2 y3 u1 u2 B
y2 1 0 4/5 -3/5 -2/5 9/5

y1 0 1 -3/5 1/5 -1/5 2/5

Z 0 0 -8 -6 -8 30

Exercice.

Considérons le problème
max z = 4x1 + 6x2 + 20x3 + 17x4

Ecrire le problème dual et le résoudre graphiquement. En déduire la solution optimale du problème

primal.
5