CHAPITRE PREMIER
Genéralités sur la programmation
mathématique à deux niveaux
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji
c~UYI 2007-2008
Introduction
La programmation mathématique à deux niveaux
(PBN) est une branche de la programmation mathématique qui résoud
des problèmes ayant une structure hiérarchique constituée
de deux unités indépendantes de prise de décision. Chaque
unité de la hiérarchie souhaite minimiser (ou maximiser) sa
fonction objectif, en tenant compte du contrôle partiel exercé
à l'autre niveau de prise de décision. La PBN modélise des
problèmes de prise de décision qui exigent des compromis parmi
les objectifs de deux individus ou entités qui interagissent. Un
décideur se voit assigner le rôle de meneur (ou leader ou
décideur du premier plan) et prend sa décision en fonction de la
(ou des) décision(s) éventuelle(s) d'un décideur de second
plan appelé suiveur. La première utilisation d'un modèle
hiérarchique date de 1934 et a été faite
par H.V Stackelberg [2] dans une monographie sur l'économie de
marché, pour décrire la situation de plusieurs décideurs
qui veulent réaliser leurs objectifs respectifs mais ne peuvent le faire
indépendamment les uns des autres. Cependant les toutes premières
formulations liées aux PBN proprement dit sont l'oeuvre d'auteurs tels
que Kornaj et Liptack [3] en 1965, Ross [4], Simaan et Cruz [5] ou Bracken et
McGill [6]. Toutefois, Candler et Norton [7, 8] furent les premiers à
utiliser la terminologie programmation à deux niveaux
ou à plusieurs niveaux dans un rapport de la banque mondiale.
C'est finalement au début des années 1980 que, vu ses
applications dans la résolution d'une multitude de problèmes
concrets (problèmes de gestion, de planification économique, de
contrôle de systèmes, de chimie, de sciences
environnementales,....), la PBN a commencé à susciter une
attention particulière. Motivés par la théorie des jeux de
H.V Sta-ckelberg [2], plusieurs auteurs se sont lancés dans
l'étude de la PBN; ce qui a permis son essor dans la communauté
de la programmation mathématique.
Dans ce chapitre, après avoir donné une
présentation générale et quelques propriétés
des PBN, nous présenterons des résultats d'optimisation
paramétrique généralement utilisés pour leur
résolution. Ensuite, nous donnerons quelques conditions sous lesquelles
les PBN admettent des solutions dans le cas de l'unicité de la solution
du problème du suiveur; ce qui nous permettra de présenter des
algorithmes développés afin de construire de manière
effective ces solutions. Nous terminerons en donnant quelques unes des
nombreuses applications de la PBN.
Genéralités sur la programmation
mathématique à deux niveaux 2
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji
c~UYI 2007-2008
1.1 Formulation générale des PBN
1.1.1 Définition et présentation
Un problème de programmation mathématique à
deux niveaux peut être défini comme un problème
d'optimisation dont l'une des contraintes est un autre problème
d'optimisation. La formulation générale d'un PBN est la suivante
:
|
min F(x,y)
|
(1.1)
|
|
y
|
|
|
sujet à : G(x,y) = 0
|
(1.2)
|
|
min f(x,y)
x
|
(1.3)
|
|
sujet à : g(x,y) = 0
|
(1.4)
|
La fonction F : Rn
× Rm -? R ;
n, in ? N représente la fonction objectif du leader tandis que
la fonction f : Rn ×
Rm -? R ; n, in ? N
représente celle du suiveur.
Les fonctions G : Rn
×Rm -?
Rp et g : Rn
×Rm -?
Rq sont respectivement les contraintes du
problème du leader et du problème du suiveur.
Le leader est le décideur qui à la
possibilité de prendre une décision sans tenir compte des
opinions d'autres décideurs que lui. Mais étant donné
(comme c'est le cas dans plusieurs problèmes d'optimisations concret)
que la possibilité de prendre une décision optimale (i.e celle
qui minimise sa fonction objectif) ne dépend pas uniquement de sa
personne, le leader se voit contraint de prendre en compte les réactions
d'un autre décideur qu'on appelle le suiveur.
les vecteurs x et y qui apparaissent dans le
problème (1.1) - (1.4) sont respectivement appelés variable du
problème du suiveur et variable du problème du leader.
La structure hiérarchique du problème (1.1) -
(1.4) suggère que le problème du leader (1.1) - (1.2) ne peut
être résolu si l'on ne connaît pas la (ou les ) solutions du
problème du suiveur (1.3) - (1.4); ce qui permet de définir une
autre formulation du PBN comme suit :
|
«min
y
|
{ }
» F (x, y) : G(x, y) = 0 et x ? (y)
(1.5)
|
avec pour y fixé dans Rm
:
{ }
(y) := Argmin f(x, y) : g(x, y) = 0
(1.6)
x
(y) représente l'ensemble des solutions du
problème d'optimisation paramétrique (1.3) - (1.4). Les
guillemets dans (1.5) expriment l'incertitude de la définition du PBN
dans le cas où (y) n'est pas réduit à un
singleton ( non unicité de la solution du problème du suiveur) La
formulation (1.5) - (1.6) est celle que nous utiliserons tout au long de cet
exposé.
Pour y fixé dans Rm
, l'ensemble M(y) := {x ?
Rn : g(x, y) = 0}
représente l'ensemble des
décisions admissibles du suiveur ( ou encore la
région réalisable du suiveur ).
{ }
L'ensemble R := (x, y) ? Rn
× Rm : G(x,
y) = 0 et x ? (y)est la région réalisable
du
leader.
Le PBN peut encore se mettre sous la forme :
Définissons à présent ce qu'on entend par
solution d'un PBN
Genéralités sur la programmation
mathématique à deux niveaux 3
Mémoire de DEA * Laboratoire d'analyse
numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008
n o
Définition 1.1.1. On considère le problème
(1.5) - (1.6) On pose Y = y E 1[8m :
G(y) < 0 .
On suppose que Ø(y) est réduit à un
singleton pour tout y E Y .
Un point (x*, y*) E 1[8n
x 1[8m est appelé solution optimale locale du
problème (1.5) - (1.6) si y* E Y, x*
E Ø(y*) et il existe une boule ouverte
centrée en y*
(Uä(y*), 8 > 0) avec
F(x, y) > F(x*,
y*) pour tout (x, y) satisfaisant y E Y
n Uä(y*) , x E
Ø(y).
(x*, y*) est solution optimale
globale si 8 = oo.
Remarques 1.1.1.
1) Si le problème (1.3) - (1.4) admet une solution
unique x(y) pour chaque paramètre y
vérifiant les contraintes du leader, alors sous des
hypothèses de régularité sur les fonctions contraintes du
second plan [ 9,10 ], la fonction
x : 1[8m -? 1[8n y H
x(y)
est continue. avec {x(y)} =
Ø(y) .
2) Si le problème (1.3) - (1.4) n'admet pas une
solution unique pour tout paramètre y vérifiant les
contraintes du premier niveau, alors le leader se trouve face à un
dilemme [11] en ce sens que même s'il connaît sa région
réalisable, il ne sait pas quelle sera la décision du suiveur.
L'analyse des différentes approches permettant d'attaquer (1.1) - (1.4)
dans ce cas de figure fera l'objet du chapitre suivant.
3) Les contraintes du leader sont dites couplées
lorsque la fonction contrainte du premier niveau G dépend
effectivement de la variable x contrôlée par le suiveur.
Rechercher les solutions réalisables qui vérifient ces
contraintes en étant compatibles avec la reaction du suiveur est aussi
difficile que la résolution du PBN lui même [10].
Nous allons maintenant présenter quelques
propriétés caractéristiques des PBN :
| 
