Approche de résolution par régularisation des problèmes de programmation mathématique à deux niveaux dans le cas de la non unicité de la solution du problème du suiveur

1.4 Conditions d'optimalités

1.4.1 Cas des PBN linéaires

Définition 1.4.1. Un PBN est dit linéaire si toutes les fonctions contraintes et les fonctions objectifs du leader et du suiveur respectivement sont linéaires. La formulation générale d'un PBN linéaire est la suivante :

{ }

min < d1,x > + < d2,y >: A3y = b,y = 0,x E Ø(y) . (1.10)

y

avec Ø(y) = Argmin x

{ } < c,x >: A1x < a - A2y,x = 0 où x E IIB^n,y E IIB^ma E IIBp,b E IIB^let

les matrices A1, A2,A3 ainsi que le vecteur c sont de dimensions appropriées. Ø(y) est l'ensemble des solutions du problème du suiveur donné par :

{ }

min < c,x >: A1 < a - A2y,x = 0 (1.11)

x

Définition 1.4.2. Une fonction : IIBp -? 2^Rq est dit polyédrique si son graphe

{ }

grph() := (x, y) E IIBp x IIBq : x E (y) s'écrit comme réunion finie d'ensemble convexes

polyédriques.

Un ensemble convexe polyédrique est une intersection finie de démi-espaces [15].

Théorème 1.4.1. La fonction

Ø(.) : IIB^m -? 2Rn

y H Argmin x

{ } < c, x >: A1x < a - A2y, x = 0 est polyédrique.

Genéralités sur la programmation mathématique à deux niveaux 13

Mémoire de DEA * Laboratoire d'analyse numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008

Corollaire

{ }

(x,y) : A1 + A2 < a, A3y = b, x > 0, y > 0

Si le problème (1.11) admet une solution unique pour chaque paramètre y, alors le problème (1.10) - (1.11) admet une solution optimale qui est le sommet du polyèdre que constitue l'ensemble

.

Si le problème du suiveur admet une solution unique pour chaque paramètre y alors, ces solutions définissent une application y i- " x(y) linéaire ; le PBN se reformule de la façon

suivante :

Preuve :

{ }

min < d1, x(y) > + < d2, y >: A3y = b, y > 0 y

ce qui est un problème de programmation linéaire simple dont on sait que la solution optimale est atteinte sur les sommets du polyèdre que constitue l'ensemble des contraintes.
·

1.4.2 Cas général

Définition 1.4.3. On suppose que card Ø(y) = 1 pour tout y E Y . On appelle fonction à valeur optimale la fonction

? : 1[8^m - " 1[8ⁿ

{ }

y i- " ?(y) = Argmin f(x, y) : g(x, y) < 0 et h(x, y) = 0

x

On convient de noter ?(y) = x(y) pour tout y E Y .

Théorème 1.4.2. Si les assertion (C), et (MFCQ) sont satisfaites, alors la fonction ø(.) est semi-continue supérieurement et la fonction à valeur optimale ?(.) est continue.

Ce theorème est démontré dans [11]

Théorème 1.4.3. On considère le PBN (1.7) - (1.8) et on suppose que les assertions (C) et (MFCQ) sont satisfaites en tout point (x, y) E 1[8ⁿ x Y , avec x E M(y) ; on suppose en plus que R =6 0 et que card Ø(y) = 1 pour tout y E Y . Alors le PBN admet une solution optimale globale.

Preuve :

Puisque card Ø(y) = 1 pour tout y E Y le problème (1.7) - (1.8) est équivalent au problème :

{F(x, y) = F(x(y), y), y E Y}

min . (1.12)

y

où Vy E Y, x(y) = ?(y) est la solution du problème du suiveur. La fonction F est continue et d'après le lemme, ?(.) est continue. D'autre part Y est un fermé borné de 1[8^m donc est compact ; d'où , (1.12) admet une solution optimale globale.

Genéralités sur la programmation mathématique à deux niveaux 14

Mémoire de DEA * Laboratoire d'analyse numérique * UYI Francisque.D.Fouodji (c)UYI 2007-2008

D'autres conditions d'optimalités des PBN peuvent être trouvées dans [11].

Maintenant que nous sommes en possession de quelques résultats nous permettant d'affirmer sous certaines conditions l'existence de solutions globales ou locales du PBN (1.7) - (1.8), il se pose la question de savoir : comment déterminer de façon effective ces solutions ?