72
Recherche opérationnelle
Théorème II : Les valeurs optimales des fonctions économiques d'un programme et
de son dual sont égales.
Après addition des variables d'écart, le programme primal s'écrit :
(I)
Soit une base du primal, donnée par un ensemble d'indices I (voir les notations du
chapitre précédent).
Effectuons les opérations classiques (voir chapitre précédent); après réordonnancement
des variables, (I)' se réécrit sous la forme :
qui permet d'arriver aux équations connues suivantes :
(5)
(6)
est le vecteur des gains marginaux.
Supposons alors que la base soit la base correspondant à l'optimum du programme (I').
On sait que l'on a dans ce cas :
(7)
Par ailleurs, on peut toujours écrire l'expression analogue pour l'ensemble d'indice ; en
effet on a évidemment :
(8)
Soit alors une des variables d'écart du programme primal,
, correspondant à la
contrainte du même programme.
Cette variable à l'optimum du primal, est, soit dans la base, soit hors base :
a) dans le premier cas, regardons l'équation (8). Supposons que
soit à la p
ième place
dans . Le p
ième élément de est égal à 0, puisque
est variable d'écart.