Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



ANALYSE ET OPTIMISATION CONVEXE. PROFESSEUR BENZINE RACHID .pdf



Nom original: ANALYSE ET OPTIMISATION CONVEXE. PROFESSEUR BENZINE RACHID.pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.11a, et a été envoyé sur fichier-pdf.fr le 15/06/2016 à 01:41, depuis l'adresse IP 105.104.x.x. La présente page de téléchargement du fichier a été vue 3345 fois.
Taille du document: 2.6 Mo (68 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


ANALYSE ET OPTIMISATION
CONVEXE

**********************
PROFESSEUR BENZINE RACHID
15 juin 2016

1

Table des matières
1 NOTIONS GENERALES. QUELQUES MODELES CONCRETS
1.1 UN PEU D’HISTOIRE . . . . . . . . . . . . . . . . . . . . . . 4
1.2 CLASSIFICATION DES PROBLEMES D’OPTIMISATION . 5
1.2.1 Forme générale d’un problème d’optimisation . . . . . 5
1.2.2 Problème d’optimisation sans contraintes . . . . . . . . 5
1.2.3 Problème d’optimisation avec contraintes . . . . . . . . 6
1.3 QUELQUES MODELES . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Gestion Optimale des Centrales Electriques du réseau
Est Algérien . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Implantation optimale d’émetteurs GSM . . . . . . . . 18
2 ENSEMBLES CONVEXES ET THEOREMES
RATION
2.1 ENSEMBLES CONVEXES . . . . . . . . . . . .
2.1.1 Dé…nitions . . . . . . . . . . . . . . . . . .
2.1.2 Propriétés de l’enveloppe convexe . . . . .
2.1.3

DE SEPA28
. . . . . . . 28
. . . . . . . 28
. . . . . . . 29

Intérieur et fermeture d’un convexe . . . . . . . . . . . 30

2.1.4 Polytope et simplexe . . . . . .
2.2 THEOREMES DE SEPARATION . .
2.2.1 Dé…nitions . . . . . . . . . . . .
2.2.2 Séparation d’un convexe et d’un

. . . .
. . . .
. . . .
point

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

33
34
34
36

2.2.3 Support d’un ensemble . . . . . . . . .
2.2.4 Séparation de deux ensembles convexes
2.2.5 Applications . . . . . . . . . . . . . . .
2.3 EXERCICES . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

39
41
44
47

2

4

TABLE DES MATIÈRES
3 FONCTIONS CONVEXES
3.1 Dé…nitions et propriétés générales . . . . . . . . .
3.2 Sous gradient et sous di¤érentiel . . . . . . . . . .
3.3 Fonctions convexes et di¤érentiables . . . . . . . .
3.3.1 Fonctions convexes une fois di¤érentiables
3.3.2 Fonctions convexes deux fois di¤érentiables

3

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

4 OPTIMISATION CONVEXE. CAS GENERAL
4.1 Dé…nitions et exemples . . . . . . . . . . . . . . . . . . . . .
4.2 Propriétés fondamentales des programmes convexes . . . . .
4.3 Condtions d’optimalité des problèmes d’optimisation convexe :
cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Conditions d’optimalité des problèmes d’optimisation convexe
et di¤érentiable . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

49
49
52
57
57
59

62
. 62
. 63
. 65
. 67

Chapitre 1
NOTIONS GENERALES.
QUELQUES MODELES
CONCRETS
1.1

UN PEU D’HISTOIRE

Un modèle est un moyen pour mieux comprendre la réalité, il est utilisé pour représenter les propriétés fondamentales d’un certain phénomène.
Un modèle permet de simuler une situation réelle pour mieux la connaître
et l’analyser. Pour qu’un modèle soit complet, il doit re‡éter d’une façon
aussi …dèle que possible le comportement des composantes du phénomène
étudié. Beaucoup de problèmes posés par l’économie, la sociologie, la biologie, l’environnement, l’industrie, . . . ., se modélisent sous forme de problèmes
mathématiques. Lorsque le modèle obtenu est un problème de minimisation
ou de maximisation on dit qu’on a un problème d’optimisation ou de programmation mathématique.
La théorie de l’optimisation est une spécialité des mathématiques appliquées relativement jeune et qui a beaucoup d’applications dans divers domaines comme l’ingineerie, le management, le monde militaire et aérospatial.
L’optimisation pourrait être dé…nie comme étant la science de la détermination de la "meilleure" des solutions de certains problèmes mathématiquement
bien dé…nis et qui sont souvent des modèles tirés de la réalité physique. Il
s’agit de l’étude des critères d’optimalité, de la détermination des méthodes
algorithmiques pour la résolution de ces problèmes, l’étude de la structure
et l’experimentation numérique de ces méthodes. Il y’a un très large éventail
d’applications pratiques.
Mise à part la méthode de Newton et celle du gradient, qui étaient connues

4

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS5
et appliquées à des problèmes physiques depuis longtemps, peu de choses
étaient connues sur les méthodes numériques associées à l’optimisation des
fonctions de plusieurs variables avant 1940.
Il ne fait aucun doute que l’avènement de l’ordinateur a été primordial
dans le développement des méthodes d’optimisation et de l’analyse numérique. Les années 1940 et 1950 ont vu l’introduction et le développement
de la branche très importante de l’optimisation linéaire ou programmation
linéaire avec la publication et l’application de la méthode du simplexe due à
G.B. Dantzig([G.B.Dantzig1940]). Le vrai développement de l’optimisation a
commencé après la publication du travail de W.C. Davidon ([Davidon1959])
dans lequel il introduit les méthodes de métrique variable. En 1961 et au cours
d’un colloque de Mathématiques, beaucoup d’intervenants éprouvèrent la dif…culté de minimiser des fonctions de dix variables, alors que M.J.D Powell
([M.J.D. Powell 1961] programma une méthode basée sur l’idée de Davidon
et qui résout des problèmes de minimisation de cent variables. Depuis ce moment l’optimisation s’est développée de façon trés rapide et a englobé une
grande variété de problèmes et de méthodes de résolution.

1.2
1.2.1

CLASSIFICATION DES PROBLEMES
D’OPTIMISATION
Forme générale d’un problème d’optimisation

Etant donné un ensemble X Rn et une fonction f : X ! R; la forme
génerale d’un problème d’optimisation est la suivante
min ff (x) : x 2 Xg

(1.1)

où X
Rn est appelé ensemble des solutions admissibles ou réalisables,
x 2 Rn s’appelle variable de décision, f (x) s’appelle fonction économique ou
fonction objectif.

1.2.2

Problème d’optimisation sans contraintes

Si X = Rn ; le problème d’optimisation (0.1.1) s’appelle problème d’optimisation sans contraintes et aura donc la forme suivante
min ff (x) : x 2 Rn g

(1.2)

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS6
Problème d’optimisation sans contraintes non linéaire
Le problème (0.1.2) est un problème d’optimisation sans contraintes non
linéaire si f n’est pas a¢ ne.
Problème d’optimisation sans contraintes quadratique
Le problème (0.1.2) est un problème d’optimisation sans contraintes non
linéaire quadratique si
f (x) = xT Ax bx
(1.3)
où A est une matrice symetrique d’ordre (n; n); xT est le transposé du vecteur
x:

1.2.3

Problème d’optimisation avec contraintes

Si l’ensemble X est dé…ni par des équations ou des inéquations, le problème (0.1.1) s’appelle dans ce cas problème d’optimisation avec contraintes.
De façon plus précise étant donné un nombre mI + mE de fonctions
cj : Rn ! R;

j = 1; :::; mI + mE ;

le problème d’optimisation avec contraintes s’écrit
8
min f (x)
<
cj (x) 0; j 2 I
:
cj (x) = 0; j 2 E

(1.4)

I et E sont deux ensembles disjoints d’entiers, de cardinalités respectives
mI et mE : On a ainsi mI contraintes d’inégalité indicées dans I; et mE
contraintes d’égalité indicées dans E.
Problème d’optimisation linéaire avec contraintes
Le problème (0.1.4) s’appelle problème d’optimisation linéaire avec
contraintes si f est a¢ ne et toutes les contraintes (cj ; j 2 I [ E) sont a¢ nes.
Problème d’optimisation non linéaire avec contraintes
Le problème (0.1.4) s’appelle problème d’optimisation non linéaire avec
contraintes si f ou l’une des contraintes cj n’est pas a¢ ne.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS7
Problème d’optimisation non linéaire quadratique avec contraintes
Le problème (0.1.4) s’appelle problème d’optimisation non linéaire quadratique avec contraintes, si f est quadratique.

1.3
1.3.1

QUELQUES MODELES
Gestion Optimale des Centrales Electriques du
réseau Est Algérien

1.3.1.1 Le réseau haute tension géré par le centre de dispatching
de Annaba
Depuis sa création, SONELGAZ a développé son réseau de transport
d’énergie sur la totalité du territoire national. L’électricité est désormais présente dans toutes les régions, même dans les zones montagneuses les plus
inaccessibles. Le centre de dispatching qui assure la conduite de l’énergie
électrique à travers l’est Algérien se trouve à Annaba
Postes de distribution :
Les postes de distribution du réseau haute tension rattachés au centre de
dispatching de Annaba sont :
SKP : Skikda poste.
ZI : Zone industrielle Skikda.
RAV : Ramdane djamel ville.
SKV : Skikda ville.
BOUN : Bounour.
AN : Annaba.
SEY : Seybous.
EHD : Elhadjar.
EKA : Elkala.
GUE : Guelma.
MES : Medjes SFA.
ZAF : Zaafrania.
HAB : Hama Bouziane (cimenterie).
DDM : Didouche Mourad.
MAR : Mansorah.
COS : Constantine sud.
SON : Sonacom (client).
ASM : Ain Smara.
A.Bey : Ain Bey.
DJO : Djebel Onk.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS8
HAS : Hdjar Soud (cimenterie)
AZA : Azaba.
RAD : Ramdane Djemel.
SOV : Souk Ahras ville.
SOP : Souk Ahras poste.
EAO : El Aouinet.
TEB : Tebessa.
TEV : Tebessa ville.
OAT : Oued Elothmania.
KHB : Khroub .
AML : Ain Mlila.
OEB : Oum el bouaghi.
STCH : Asmidal.
1.3.1.2 Données du problème
L’énergie électrique qui alimente le réseau est Algérien est produite par
trois classes de centrales : les centrales dites à turbines à vapeur, celles à turbines à gaz et les centrals hydrauliques. On trouve dans les tableaux suivants
l’emplacement de ces centrales et leur puissance minimale et maximale.

Centrales à turbines à vapeur
Zone de production
Annaba GTA3
Annaba GTA4
Skikda GTA1
Skikda GTA2
Skikda GTAV1
Skikda GTAV2
Jijel GTA1
Jijel GTA2
Jijel GTA3

Puiss-Min
18 MW
18 MW
50 MW
50 MW
80 MW
80 MW
80 MW
80 MW
80 MW

Centrales à turbines à gaz

Puiss-Max
55 MW
72 MW
130 MW
130 MW
160 MW
160 MW
196 MW
196 MW
196 MW

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS9
Zone de production
Fkirina TG1
Fkirina TG2
Skikda TG1
Skikda TG2

Puiss-Min
100 MW
100 MW
140 MW
140 MW

Puiss-Max
160 MW
160 MW
280 MW
280 MW

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS10

Centrales hydrauliques
Zone de production
Darguinah GR1
Darguinah GR2
Darguinah GR3
Erraguene GR-ERA
Ighil-IEM1
Enda-IEM2
Monsoura MSO1
Monsoura MSO2

Puiss-Min
10 MW
10 MW
3 MW
6 MW
6 MW
6 MW
25 MW
25 MW

Puiss-Max
32.5 MW
32.5 MW
1.5 MW
12 MW
12 MW
12 MW
50 MW
50 MW

D’après les tableaux précedents, on remarque qu’il existe des centrales
appartenant à la même classe et possèdant les mêmes caracteristiques (appatenant à la même classe, même puissance minimale et maximale). On les
a donc regroupées et classées ensemble, par types, comme l’indiquent les
tableaux suivants. On a repertorié 11 types.

Type
1
2
3
4
5
6
7
8
9
10
11

Nbre
1
1
2
2
2
2
3
2
1
3
2

Puiss-Max
18
18
50
100
140
80
80
10
1.5
6
25

Puiss-Min
55
72
130
160
280
160
196
32.5
3
12
50

Ces centrales ont un coût de démarrage, un coût horaire de base quand
elles fonctionnent à la puissance minimale, et un coût horaire par Mégawatt supplémentaire au delà de cette puissance minimale. Ces données sont
fournies dans le tableau ci-dessous.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS11
Type
1
2
3
4
5
6
7
8
9
10
11

Coût-Base
3 106 DA=h
3 106 DA=h
1 106 DA=h
1 106 DA=h
1 106 DA=h
2 106 DA=h
1 106 DA=h
4 106 DA=h
4 106 DA=h
4 106 DA=h
4 106 DA=h

Coût-Supp
2:3 106 DA=h
2:3 106 DA=h
0:8 106 DA=h
0:9 106 DA=h
0:9 106 DA=h
1:5 106 DA=h
0:8 106 DA=h
3 106 DA=h
3 106 DA=h
3 106 DA=h
3 106 DA=h

Coût-Dem
5 106 DA
5 106 DA
3 106 DA
2 106 DA
2 106 DA
3 106 DA
3 106 DA
2 106 DA
2 106 DA
2 106 DA
2 106 DA

Une centrale ne peut être démarrée ou arrêtée qu’en début de période.
Contrairement au démarrage l’arrêt ne coûte rien. Les centrales en route
doivent pouvoir résister a une augmentation de 40 % de la demande prévue
(ce pourcentage est la reserve tournante de secours.).
On a divisé une journée de consommation en 3 périodes :
1. Heures pleines : de 7 h à 18 h.
2. Heures de pointes : de 18 h à 22 h.
3. Heures creuses : de 22 h à 07 h.
Le tableau suivant représente les demandes d’énergie en Méga Watts durant ces trois périodes de la journée. Le tableau ci-dessous indique la puissance électrique demandée en chaque période de la journée.
Période
Heures pleines
Heures de pointe
Heures creuses

Demande
521.46MW
654.63MW
471.77MW

1.3.1.3 Position du problème
En Algérie, comme dans tous les pays, il y’a production, distribution et
consommation de l’énergie électrique. La production se fait grâce à des centrales de di¤érents types (hydrauliques, à gaz, . . . ). Les consommateurs de

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS12
l’énergie électrique sont de trois type : les particuliers, l’industrie, l’agriculture et les services publics (éclairage public, collectivités locales, armée. . . ).
Normalement, et pour ne pas avoir de coupures électriques ou des délestages, la production de l’énergie électrique doit être supérieure à la consommation. Ceci se traduit par la construction d’un nombre su¢ sant de centrales électriques qui assurent cette production. Supposons qu’on a réglé ce
problème, c’est-à-dire qu’on a su¢ samment de centrales pour satisfaire toute
la consommation et avec un surplus de sureté.
Si la consommation de l’énergie électrique était constante et si on ne se
préoccupait pas du coût de la production, on ferait fonctionner toutes les
centrales à plein régime et on n’aurait aucun problème.
Malheureusement la consommation de l’énergie électrique varie non seulement selon la période de la journée mais aussi selon les saisons de l’année.
D’autre part Sonelgaz doit réduire au minimum les coûts de production et de
gestion, pour des raisons économiques évidentes (concurrence à venir, . . . ).
Pour toutes ces raisons, une gestion optimale des centrales électriques nourrissant le réseau de l’est Algérien, s’impose. Plus précisément connaissant la consommation de l’énergie électrique dans di¤érentes
périodes de la journée et prenant en considération les caractéristiques technique (puissance maximale, minimale, démarrage,. . . ) des di¤érents types
de centrales alimentant le réseau de l’est, on va étudier quels sont les centrales qu’on fera fonctionner à di¤érents régimes pour que les deux objectifs
suivants soient atteints :
Objectif1 : la consommation doit être assurée avec un régime
de sûreté acceptable
Objectif2 : le coût de production de l’énergie électrique doit être
minimal

1.3.1.4 Objectif à atteindre

Notre objectif est le suivant :
Quelles centrales faut il faire fonctionner dans chaque période de la journée de sorte que le coût total journalier soit minimal, et que la consommation
totale soit assurée avec le taux de sûreté requis.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS13
1.3.1.5 Démarche à suivre
Pour résoudre notre problème nous allons suivre comme nous le faisons
souvent dans tout problème d’optimisation les les quatres étapes suivantes :
a) Modélisation du problème. C’est-à-dire transformer le problème
économique et technique en un problème mathématique. C’est la phase la
plus délicate et la plus di¢ cile.
b) Résolution théorique du problème. Il s’agit d’identi…er quel type
de problème mathématique on a et de trouver les méthodes et les techniques
qui nous permettent de résoudre ce problème. On verra que dans notre cas
on aura a¤aire à un problème d’optimisation linéaire.
c) Résolution numérique ou informatique du problème. Si notre
modèle est de petite taille, on peut s’arrêter à l’étape b). Malheureusement
les problèmes concrets sont de grande taille et pour les résoudre il faut avoir
un logiciel de résolution. C’est ce que nous appliquerons à notre problème
avec le logiciel Visual Express.
d) Interprétation des résultats numériques Il s’agit d’interpréter les
resultats numériques trouvés en revenant au problème d’origine.
1.3.1.6 Modélisation du problème

Variables utilisées :
Pour modéliser notre problème nous avons besoin des variables suivantes :
Indices
t : Type de centrale ( t varie dans notre cas de 1 à 11 )
p : Période d’une journée.
Constantes
nt : Le nombre de types de centrales (nt = 11 dans notre problème )
np : Le nombre de périodes d’une journée ( np = 3 dans notre cas ).
Variables
largp : La largeur en heures de la tranche horaire. Dans notre cas : larg1 =
11heures; larg2 = 4 heures; larg3 = 6 heures:
Demap : La puissance électrique demandée par le réseau pour chaque période. Dans notre cas on a :
Dema1 = 521; 46M W; Dema2 = 654; 63M W; Dema3 = 471; 77M W
P mint : La puissance minimale de la centrale de type t. Dans notre cas :
P min1 = 18M W; :::; P min11 = 25M W (voir tableau 0.2)

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS14
P maxt : La puissance maximale de la centrale de type t. Dans notre cas :
P max1 = 55M W; :::; P max11 = 50M W (voir tableau 0.2)
N dist : Le nombre de centrales disponibles de type t. Dans notre cas :
N dis1 = 1; :::; N dis11 = 2 (voir tableau 0.2)
Cdemt : Le coût de démarrage de la centrale de type t. Dans notre cas :
Cdem1 = 5 106 DA; :::; Cdem11 = 2 106 DA (voir tableau 0.2)
Cmint : Le coût de base horaire, quand les centrales fonctionnent à la
puissance minimale. Dans notre cas : Cmin1 = 3 106 DA; :::; Cmin11 =
4 106 DA (voir tableau 0.2)
Csupt : Le coût horaire par mégawatt supplémentaire au delà de la
puissance minimale. Dans notre cas : Csup1 = 2:3 106 DA; :::; Csup11 =
3 106 DA (voir tableau 0.2)

Variables supplémentaires :
Nous aurons besoin aussi des 3 variables supplémentaires suivantes :
N demtp
N f ontp
P suptp

N demtp : Désigne le nombre de centrales de type t démarrées en
début de période p.
N f ontp : Désigne le nombre de centrales de type t qui fonctionnent
en période p. Ce dernier ne doit pas dépasser le nombre des centrales disponibles de type t.
P suptp : Désigne le nombre total de mégawatts fournis en plus du
minimum technique par les centrales de type t en période p.

Fonction économique
Rappelons que notre but est de minimiser le coût total journalier de toutes
les centrales éléctriques du réseau. En respectant les données du problème,
ce cout total est bien sur égal à :
Co^
ut total journalier = co^
ut de demarrage + co^
ut de base + co^
ut supplem:
Le coût de base et le coût supplémentaire sont proportionnels aux largeurs
des périodes.
Calculons maintenant chacun de ces trois coûts avec les variables qu’on
a introduit avant.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS15
Coût de démarrage de toutes les centrales activées durant une journée .
np nt
X
X

Cdemt :N demtp

p=1 t=1

Coût de base de toutes les centrales qui fonctionnent durant une la journée.
np nt
X
X

largp :Cmint :N f ontp

p=1 t=1

Coût supplémentaire de toutes les centrales durant toute la journée.
np nt
X
X

largp :Csupt :P suptp

p=1 t=1

La fonction économique à minimiser est donc la suivante :
( np nt
)
XX
min
Cdemt :N demtp + largp :Cmint :N f ontp + largp :Csupt :P suptp
p=1 t=1

Contraintes liées au problème
Remarquons d’abord qu’il est évident que les variables suivantes soient
entières :
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; N demtp 2 N;
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; N f ontp 2 f0; 1; 2; :::; N dist g ;
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; P suptp

0

Remarque :
Notons par P ft = (P maxt P mint ); la puissance fournie au delà du
niveau de base (minimum technique) pour une centrale de type t. Par conséquent le nombre total de mégawatts fournis en plus du minimum doit être
inférieur ou égale à la puissance fournie au delà du niveau de base multiplié
par le nombre de centrales qui fonctionnent pour chaque période et pour
chaque type. Ceci se traduit par les contraintes suivantes :
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; P suptp
Maintenant remarquons que :

(P maxt

P mint ):N f ontp

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS16
Pnt

P mint :N f ontp est la puissance totale de base fournie par les centrales
de di¤erents types,
Pnt
t=1 P suptp est la puissance totale délivrée au delà du niveau de base,
durant la période p:Donc pour satisfaire la demande de chaque période il faut
que les contraintes suivantes soient satisfaites
t=1

8p 2 f1; :::; npg ;

nt
X

P mint :N f ontp +

t=1

nt
X

P suptp

Demap

t=1

De P
la même manière, notons que :
nt
t=1 P maxt :N f ontp est la puissance maximale totale fournie par les centrales qui sont en marche, durant la période p:
Sans démarrer d’autres centrales, celles qui sont en marche doivent résister
à une augmentation de 40% de la demande prévue. Ceci se traduit par les
contraintes suivantes :
8p 2 f1; :::; npg ;
ou encore

nt
X

P maxt :N f ontp

Demap + 0:40:Demap

t=1

8p 2 f1; :::; npg ;

nt
X

P maxt :N f ontp

1:40:Demap :

t=1

Signalons aussi que
N f ontp N f ont;p 1 représente le nombre de centrales démarrées en période p. S’il n’y avait pas d’arrêts, les centrales en marche dans la période
(p 1) sont toujours en fonctionnement durant toute la période p alors :
N demtp = N f ontp

N f ont;p 1 :

Et comme il y a des arrêts, le nombre de centrales démarrées doit véri…er
les contraintes suivantes :
N demtp

N f ontp

N f ont;p 1 ; 8t 2 f1; :::; ntg ; 8p 2 f2; :::; npg

Si on prend maintenant en considération le fait que le nombre de centrales
démarrées à la première période du jour, est supérieur ou égale à la di¤érence
du nombre de centrales qui sont en marche dans la première période du jour,
par rapport à la dernière période du jour précédant. Ceci nous ramène à tenir
compte des contraintes suivantes :
N demt;1

N f ont;1

N f ont;3 ;

8t 2 f1; :::; ntg

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS17

Forme …nale du modèle : fonction économique et contraintes

min

( np nt
XX

Cdemt :N demtp + largp :Cmint :N f ontp + largp :Csupt :P suptp

p=1 t=1

Sous les contraintes :

1.Puissance limitée
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; P suptp

(P maxt

P mint ):N f ontp

2.Nombre de centrales démarrées sur un jour glissant
N demtp

N f ontp
N demt;1

N f ont;p 1 ; 8t 2 f1; :::; ntg ; 8p 2 f2; :::; npg
N f ont;1

N f ont;3 ;

8t 2 f1; :::; ntg

3.Satisfaction des demandes
8p 2 f1; :::; npg ;

nt
X

P mint :N f ontp +

t=1

nt
X

P suptp

Demap

t=1

4. La réserve de 40%
8p 2 f1; :::; npg ;

nt
X

P maxt :N f ontp

1:40:Demap :

t=1

5. La non négativité des contraintes
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; N demtp 2 N;
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; N f ontp 2 f0; 1; 2; :::; N dist g ;
8t 2 f1; :::; ntg ; 8p 2 f1; :::; npg ; P suptp

0

)

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS18

1.3.2

Implantation optimale d’émetteurs GSM

1.3.2.1 Position du problème
Supposons que l’opérateur de téléphonie mobile Algérie Mobilis veut couvrir une certaine région (wilaya ou commune) avec des antennes emeteurs
GSM, de sorte que les deux objectifs suivants soient atteints :
Objectif 1 : La couverture en question doit atteindre le maximum
d’habitants pour que le gain engendré par une telle couverture soit maximal.
Objectif 2 : Pour e¤ectuer une telle couverture, on ne doit jamais
dépasser un certain budget …xé à l’avance.
Remarque1 : Si le budget alloué à une telle couverture était illimité, on
couvrirait toute la population et on n’aurait pas besoin de problème d’optimisation. Ceci est impossible car si une entreprise sérieuse investit dans une
opération économique, elle espère en tirer pro…t. Donc elle doit investir le
moins pour en tirer le plus de pro…t.

1.3.2.2 Couverture optimale de la commune d’El Bouni
On fera notre étude dans la commune d’El Bouni (Wilaya de Annaba),
qu’on supposera non couverte encore.
Mobilis a e¤ectué une étude technique et économique et a retenu tous les
sites potentiels sur lesquels on pourrait installer nos émetteurs. C’est l’objet
de la carte C1. On a retenu 10 sites potentiels. On les a notés S1 ; S1 ; :::; S10 .
Remarque1 : On ne pourrait pas implanter un émetteur dans chaque
site, car on est limité par le budget. Notre but est exactement de choisir
parmi l’ensemble de ces sites ceux qui couvriront le maximum de populations
et dont le coût ne dépasserait pas le budget alloué par l’entreprise.
La commune d’El Bouni est divisée en 19 zones géographiques (voir la
carte C2). Nous les avons notées Z1 ; Z2 ;. . . , Z19 . Le tableau T1 donne les
caractéristiques de ces zones (Nbre de populations).
Chaque émetteur pourra couvrir un certain nombre de zones. Le tableau
T2 présente ces zones.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS19

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS20
Tableau T1 : Zones Géographiques d’ElBouni
ZONES GEOGRAPHIQUES Nbre d’habitants
Z1 : Oued Zied
989
Z2 : Berka zarga
6484
Z3 : Oued-elnil
4753
Z4 : Essarouel
12790
Z5 : Ecotec
521
Z6 : Chabia
987
Z7 : Kharraza
12511
Z8 : Boussedra
1089
Z9 : Bouzaaroura
5846
Z10 : El-Bouni - I
15953
Z11 : El-Bouni - II
12310
Z12 : El-Bouni - III
7239
Z13 : Boukadra - I
13086
Z14 : Boukadra - II
4516
Z15 : Gharbi-Aissa
768
Z16 : Sidi -Salem
12933
Z17 : Boukmira
17937
Z18 : Chouli-Belkacem
530
Z19 : Aéroport Bitat
783
Tableau T2 :
SITES
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10

Répartition des zones couvertes
ZONES COUVERTES
Z1 ; Z2 ; Z3
Z3 ; Z4
Z4 ; Z5 ; Z6 ; Z7
Z8 ; Z10 ; Z11
Z9 ; Z11 ; Z12
Z11 ; Z12 ; Z13
Z13 ; Z14
Z15 ; Z16 ; Z17
Z15 ; Z16 ; Z18
Z18 ; Z19

1.3.2.3 Coût de l’implantation des émetteurs dans les di¤érents
sites potentiels Si
Chaque émeteur a un coût qui dépend de beaucoup de facteurs (location
de l’emplacement, énergie consommée, puissance. . . ). Le tableau T3 donne

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS21
le coût de l’émetteur placé dans le site correspondant.
Tab.T3 : Coût des émeteurs des di¤érents sites potentiels
SITES COUT EN MILLIARDS CENTIMES
S1
3
S2
2
S3
1:8
S4
1:6
S5
1:5
S6
1:3
S7
2:1
S8
1:9
S9
2:3
S10
2:8

1.3.2.4 Budget Total disponible
Pour e¤ectuer cette opération, Mobilis dispose d’un budjet total qu’on
note BudgT, de 10 Milliards de centimes qu’on ne devrait pas dépasser.
Remarque 3. Si on installe dans chaque site Si i = 1; 2; :::; 10, un émetteur, il nous faudrait alors (voir tableau T3) :
3+2+(1:8)+(1:6)+(1:5)+(1:3)+(2:1)+(1:9)+(2:3)+(2:8) = 20:3 M illiards cts
Cette somme dépasse de loin notre budget. Donc il nous faut choisir parmi
les dix sites potentiels, ceux qui couvriront le maximum de populations et
dont le coût ne dépasserait pas le budget alloué : 10 Milliards de centimes.

1.3.2.5 Résolution du problème
La résolution de ce problème s’e¤ectuera en deux phases :
Phase 1 : Modélisation du problème
Phase 2 : Résolution numérique et informatique du problème

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS22

Modélisation du problème
La modélisation de ce problème consiste à transformer ce problème économique en un problème mathématique. C’est une opération très délicate et
en général assez di¢ cile, sur laquelle repose toute la procédure de résolution.
Comme on le verra plus tard, la modélisation de notre problème de localisation d’émetteurs GSM va déboucher sur un problème d’optimisation linéaire
en nombres entiers.
Commençons donc la modélisation de notre problème.

1.3.2.6 Variables de décision, fonction objectif et contraintes associées au problème
Constantes associées au problème
Notons par :
n : le nombre de zones (dans notre cas n = 19)
m : nombre de sites potentiels pour l’implantation d’émetteurs (m = 10
dans notre cas)
Cj : le coût de l’implantation de l’émetteur j sur le site Sj ; j = 1; 2; :::; 10
(exemple C3 = 1:8 )
Pi : le nombre d’habitants de la zone Zi ; i = 1; 2; :::; 19 (exemple P2 =
6484 dans notre cas)
Nous introduisons aussi les constantes binaires Kj;i (j = 1; 2; : : : m; i =
1; 2; : : : n) suivantes :
Kj;i prend la valeur 1 si un émetteur placé sur le site Sj ; couvrirait la
zone Zi .
Kj;i prend la valeur 0 sinon.
Exemple : dans notre cas
K1;1 = 1, K1;2 = 1, K1;3 = 1, K1;4 = K1;5 = ::: = K1;19 = 0 (voir
tableau T3)
Variables de décision associées au problème
Pour modéliser notre problème nous avons besoin d’introduire des variables binaires Xj (j = 1; 2; : : : m) et Yi (i = 1; 2; : : : n); qui ne prennent
que les valeurs 0 ou 1.

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS23
Xj prendra la valeur 1 si une antenne est implantée sur le site Sj ; j =
1; 2; ::10
Xj vaut 0 sinon.
Yi vaut 1 si une zone Zi est couverte par une antenne GSM.
Yi vaut 0 sinon.
Remarque 4 : Si après résolution, on trouve que Xj = 1; j = 1; 2; : : : 10,
cela veut simplement dire qu’on peut mettre dans chaque site un émetteur.
Ceci est peu probable, car comme on l’a vu dans la remarque 3.3, entraînerait
un dépassement de budget. Donc dans notre solution optimale on aurait
sûrement des Xj qui prendraient la valeur 0 et ceci veut dire qu’on ne mettra
pas d’émetteurs dans les sites correspondants.
Fonction objectif
Avec ces variables, on est en mesure de dé…nir la fonction à maximiser.
Il s’agit de trouver le nombre maximal d’habitants couverts par les antennes
GSM, c’est-à-dire il s’agit de :
M aximiser

n
X
i=1

Yi :Pi +

m
X

0:Xj

j=1

Contraintes
a) Contraintes budgétaires
m
X

Cj :Xj

BudgT

j=1

Où BudgT est le budjet total alloué ( BudgT = 10 milliards de cts )
b) Contraintes liées à la couverture des zones
Il faut tenir compte de l’exigence de couverture suivante. La zone Zi reçoit
le signal GSM , au moins l’émetteur de l’un des sites couvrant cette zone
doit être construit , ou encore :
Yi = 1 , il existe au moins un j avec Kj;i :Xj = 1:

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS24
ou de façon équivalente :
8i = 1; 2; :::; n;

m
X

Kj;i :Xj

Yi

j=1

Remarque 4 : La contrainte précédente signi…e que :
1) Une ville peut être couverte par plus d’un émetteur.
2) On ne laissera pas à un Yi prendre la valeur 0; si des émetteurs qui le
couvrent sont construits.
c) Contraintes liées au fait que les variables sont binaires

8i = 1; 2; :::; n; Yi 2 f0; 1g
8j = 1; 2; :::; m; Xj 2 f0; 1g
Nous obtenons ainsi le modèle …nal suivant :

Forme …nale du modèle : fonction économique et contraintes

M aximiser
8
>
>
<
>
>
:

Pn

i=1

Yi :Pi +

Pm

j=1

0:Xj

avec les contraintes
Pm
BudgT
j
j=1 Cj :XP
m
Yi
8i = 1; 2; :::; n;
j=1 Kj;i :Xj
8i = 1; 2; :::; n; Yi 2 f0; 1g
8j = 1; 2; :::; m; Xj 2 f0; 1g

Résolution numérique du problème
Ce qui intéresse le plus l’entreprise Mobilis, c’est d’avoir une réponse
concrète au problème posé au début du problème, c’est-à-dire : choisir parmi
les dix sites Si proposés, ceux sur lesquels on implantera des émetteurs, tout
en respectant les deux objectifs …xés au début, c’est à dire :
# Couvrir le maximum de populations
# Ne pas dépasser le budget alloué.
Pour résoudre numériquement notre problème, nous utilisons le logiciel
Visual Express, qui après seize itérations nous livre les résultats suivants :

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS25
Xj
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10

V aleur
1
0
1
1
0
1
0
1
0
0

Yi
Y1
Y2
Y3
Y4
Y5
Y6
Y7
Y8
Y9
Y10
Y11
Y12
Y13
Y14
Y15
Y16
Y17
Y18
Y19

V aleur
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS26

Analyse des résultats
Sites Choisis pour implanter les émetteurs
Il s’agit des sites : S1 (X1 = 1); S3 (X3 = 1); S4 (X4 = 1); S6 (X6 =
1); S8 (X8 = 1)
Sites sur lesquels ne seront pas implantés des émetteurs
Il s’agit des sites : S2 (X2 = 0); S5 (X5 = 0); S7 (X7 = 0); S9 (X9 =
0); S10 (X10 = 0)
Zones couvertes par l’mplantation d’émetteurs dans les sites choisis
Zones couverte
Z1 : Oued Zied
Z2 : Berka zarga
Z3 : Oued-elnil
Z4 : Essarouel
Z5 : Ecotec
Z6 : Chabia
Z7 : Kharraza
Z8 : Boussedra
Z11 : El-Bouni –II
Z12 : El-Bouni - III
Z13 : Boukadra –I
Z15 : Gharbi-Aissa
Z16 : Sidi –Salem
Z17 : Boukmira
Nombre d’habitants couverts :

Nbre Populations
989
6484
4753
12790
521
987
12511
1089
12310
7239
13086
768
12933
17937

104375

Zones non couvertes par l’mplantation d’émetteurs dans les sites choisis
Zones non couvertes
Z9 : Bouzaaroura
Z10 : El-Bouni –I
Z14 : Boukadra - II
Z18 : Chouli-Belkacem
Z19 : Aéroport

Nbre Populations
5846
15953
4516
530
530

CHAPITRE 1. NOTIONS GENERALES. QUELQUES MODELES CONCRETS27
Nombre d’habitants non couverts : 27375
Pourcentage de la Popultaion couverte : 80 %
Budget consommé par l’implantation des émetteurs : 9,6 Milliards de centimes.

Chapitre 2
ENSEMBLES CONVEXES ET
THEOREMES DE
SEPARATION
2.1

ENSEMBLES CONVEXES

2.1.1

Dé…nitions

Dé…nition 2.1 Soit S un sous ensemble de Rn : S est dit convexe si et
seulement si 8x1 ; x2 2 S; 8 2 [0; 1]; x1 +(1 )x2 2 S: Soit x1 ; x2 ; :::; xk 2
k
P
Rn et
0 et
j telle que
j
j = 1: Toute expression de la forme
j=1

suivante :

k
P

j xj

s’appelle combinaison convexe des points xj ou barycentre.

j=1

Figure 2.1 : ensemble convexe et non convexe

28

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION29
Dé…nition 2.2 Soit S Rn . On appelle envelloppe convexe de S et on le
note H(S); l’ensemble de toutes les combinaisons convexes de S; en d’autre
termes :

x 2 H(S) , 9x1 ; x2 ; :::; xk 2 S et

1;

2 ; ::;

k

2 R+ tel que

k
X

j

= 1 et x =

j=1

j=1

(2.1)

S:

H(S):

Figure 2.2 : Exemple d’enveloppes covexes

2.1.2

Propriétés de l’enveloppe convexe

Proposition 2.1 Soit S
Rn quelconque, alors H(S) est un convexe,
c’est aussi le plus petit convexe qui contient S
Preuve de la Proposition 2.1
Soient x 2 H(S) et y 2 H(S): Alors il existe ( 1 ;
x1 ; ::; xp 2 S , y1 ; y2 ; :::; y` 2 S telles que

j

> 0;

j

2 ; :::;

> 0;

1 et
x=
Soit

1 x1

+ ::: +

p xp ;

y=

1 y1

+ ::: +

p );
p
P

( 1;
j

= 1;

j=1

2 ; :::;
`
P
j=1

` y`

2 [0; 1]
x + (1

)y =

1 x1

+ ::: +

p xp

+ (1

) 1 y1 + ::: + (1

k
X

) ` y`

` );
j

=

j xj

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION30
avec
(

1

+ ::: +

p)

+ (1

)(

1

+ ::: +

l)

=

+ (1

) = 1:

Donc x + (1
)y est un barycentre des points x1 ; ::; xp ; y1 ; y2 ; :::; y` appartenant à S: x + (1
)y appartient donc à H(S) et par suite H(S) est
convexe.
Notons par le plus petit convexe qui contient l’ensemble S: On doit démonter que H(S) = .
1.
H(S) car est le plus petit convexe qui contient S et H(S) est un
convexe contenant S aussi (si x 2 S; x = 1:x 2 H(S), donc S H(S)):
2. H(S)
: En e¤et. On a : S
) H(S) H( ) (voir exercice 2.4) et
H( ) = car est convexe (voir exercice 2.2).
Proposition 2.2 Soit S Rn : L’intersection de tous les convexes contenant S est le plus petit convexe qui contient S:
Preuve de la proposition 2.2
Notons par une telle intersection ;

=

T

Si ; Si convexe contenant S:

i2I

On a
a) est un ensemble convexe (voir exercice 2.1)
b) S
c) Soit S un convexe quelconque qui contient S: Alors 9i0 2 I tel que
S = Si0 : Donc
Si0 .

2.1.3

Intérieur et fermeture d’un convexe

Proposition 2.3
x2 2 int(S); alors :

Soit S

8 2 [0; 1[;

Rn un convexe non vide et x1 2 S et
x1 + (1

Preuve de la proposition 2.3
x2 2 int(S) ) 9" > 0 tel que, B0 (x2 ; ")
fz : kz

x2 k < "g

)x2 2 int(S)

S, ou en d’autres termes
y
x1
S: Considérons y = x1 + (1
)x2 () x2 =
)
1

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION31
Montrons qu’il existe "1 > 0 telle que B0 (y; "1 )
"1 = (1
)" et prouvons que
9
8
=
<
z : kz yk < (1
)"
| {z };
:

S: En e¤et choisissons

S:

"1

En e¤et considérons z tel que : kz
x1 2 S )

x : kx

yk < (1

x1 k <

(1

)"

kz

)"

yk

\ S 6= ;:

Plus particulièrement, il existe z1 2 S tel que
kz1

(1

x1 k <

kz

)"

yk

:

Soit z2 tel que :
z2 =

z
1

z1

) z = z1 + (1

)z2 :

Démontrons que
z2 2 B0 (x2 ; ")
ou encore : kz2
kz2

x2 k < ". En e¤et
z
1
z

x2 k =
=

1
1
<

1

1
< ":

z1

x2

z1 (y
1

x1 )

(kz

yk + kx1

(kz

yk +

(1

z1 k)
)"

Etant donné que " a été choisi de sorte que B0 (x2 ; ")
z2 2 S et z1 2 S:
S est convexe alors :
z1 + (1

)z2 = z 2 S:

Donc
9"1 > 0 : B0 (y; "1 )

S:

kz

yk

)

S et puisque z1 2 S

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION32
Ce qui veut dire exactement que y 2 int(S):

X2

y
X1
Z2

Z1

Z1

Figure 2.3 : Un ségement joignant un point interieur avec un
point frontière de S:
Rn tel que S est convexe et int(S) 6= ;. Alors

Corollaire 2.1 Soit S
int(S) est convexe.

Preuve du corollaire 2.1
Soit x1 2 int(S): Alors x1 2 S: Considérons un autre point x2 2 int(S):
D’après la proposition 2.3
x1 + (1

)x2 2 int(S):

Ce qui implique que int(S) est convexe.

Corollaire 2.2
convexe.

Rn ; S convexe et int(S) 6= ;; alors S est

Soit S

Preuve du corollaire 2.2
Soient x1 ; x2 2 S et z 2 int(S); d’après la proposition 2.3, x2 + (1
)z 2
int(S): Appliquons encore une fois la proposition 2.3 au point x1 2 S et au
point x2 + (1
)z 2 int(S); on aura pour 2 ]0; 1[
x1 + (1

)[ x2 + (1

Par passage à la limite quand

!1

x1 + (1
Ceci imlique que S est convexe.

)z] 2 int(S)
)x2 2 S:

S

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION33

2.1.4

Polytope et simplexe

Dé…nition 1.3 L’envelloppe convexe d’un nombre …ni de points x1 ; x2 ; :::; xk+1
dans Rn s’appelle polytope. Si x1 ; x2 ; :::; xk ; xk+1 sont tels que : x2 x1 ; x3
x1 ; :::; xk x1 ; xk+1 x1 sont linéairement indépendants alors H(x1 ; x2 ; :::; xk 1 ; xk ; xk+1 )
s’appelle simplexe avec les points x1 :::; xk ; xk+1 :

Remarque 1.1 Dans Rn il n’existe pas de simplexes avec plus de (n + 1)
points. Ceci est du au fait que dans Rn ; tout système formé de (n + 1) points
ou plus est nécessairement lié.

x5

x3

x4

x3

x6

x1

x2

(a) Polytope

x2

x1

(b) Simplexe

Figure 2.4 : Plytope et sipmlexe dans R2

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION34

2.2
2.2.1

THEOREMES DE SEPARATION
Dé…nitions

Dé…nition 2.4 Soit p 2 Rn non nul est 2 R: On appelle hyperplan H
l’ensemble suivant : H = x 2 Rn : p> x =
; p s’appelle vecteur normal
+
de H: A tout hyperplan H; on associe H et H
H + = x 2 Rn : p > x
: demi-espace superieur fermé
H = x 2 Rn : p > x
: demi-espace inferieur fermé
On peut associer aussi à H deux demi-espaces ouverts qu’on note Ho+ et
Ho
Ho+ = x 2 Rn : p> x >
:demi-espace superieur ouvert
n
>
Ho x 2 R : p x <
:demi-espace inferieur ouvert
Remarque 2.2 Si x^ 2 H; alors x^ véri…e p> x^ = : Puisque tout point
x 2 H véri…e la même équation on aura : p> (x x^) = 0; 8x 2 H: Donc
l’équation d’un hyperplan s’écrit aussi de la façon suivante quand on sait
qu’un point particulier appartient à H; H = x 2 Rn : p> (x x^) = 0 :
Dé…nition 2.5 a) Soit S1 et S2 deux ensembles non vides dans Rn : On
dit que l’hyperplan H = x : p> x =
sépare (simplement) S1 et S2 ; si et
seulement si
p> x
: 8x 2 S1 ; (S1 H + )
(2.2)
p> x
: 8x 2 S2 ; (S2 H )

S1
S2
Figure 2.5 : Séparation simple non propre

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION35
b) Si de plus de a) on a aussi S1 [ S2 * H, on dit que H sépare S1 et S2
proprement.

S1
S2

Figure 2.6 : Séparation propre
c) On dit que l’hyperplan H = x : p> x =
sépare strictement S1 et S2 si
et seulement si
p> x < : 8x 2 S2
(2.3)
p> x > : 8x 2 S1

H
S1
S2

Figure 2.7 : Séparation stricte
d) l’hyperplan H = x : p> x =
sépare fortement S1 et S2 si et seulement
si
9" > 0 : p> x
; 8x 2 S2 et p> x
+ "; 8x 2 S1
(2.4)

H
S1

S2

Figure 2.8 : Séparation forte

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION36

2.2.2

Séparation d’un convexe et d’un point

Avant d’énoncer le théorème 2.2 (Séparation d’un convexe férmé et d’un
point), rappelons d’abord le célèbre théorème de la meilleure approximation.
Pour la preuve de ce théorème et pour plus de détails sur la théorie de
l’approximation, voir par exemple l’excellent ouvrage de Pierre Jean Laurent
([P.J. Laurent : Approxiation et Optimisation]).
Théorème 2.1 ( Théorème de la meilleure approximation). Soit S Rn
non vide, convexe et fermé et y 2 Rn tel que y 2
= S: Alors il existe un point
x^ unique appartenant à S tel que
ky

x^k = min ky
x2S

xk :

(2.5)

x^ s’appelle la meilleure approximation de y dans S:D’autre part x^ est la
meilleure approximation de y dans S si et seulement si x^ véri…e
(y

x^)> (x

x^)

0; 8x 2 S

(2.6)

Théorème 2.2 ( Séparation d’un point et d’un convexe férmé). Soit
S Rn non vide convexe et fermé et y 2
= S: Alors il existe p 2 Rn ; non nul
!
( p 6= 0 ) et 2 R tel que
a) p> y >
et
b) p> x
8x 2 S
En d’autre termes il existe un hyperplan H de vecteur normal p et de
coé¢ cient qui sépare le point y et l’ensemble convexe férmé S:
Preuve du théorème 2.2
a) S Rn non vide convexe et fermé et y 2
= S: D’après le théorème de
la meilleure approximation 2.1, 9^
x 2 S tel que
(y

x^)> (x

x^)

0; 8x 2 S:

(2.7)

Considérons l’Hyperplan H suivant :
H = x 2 Rn : (y

x^)> (x

x^) = 0

D’après cette dé…nition de H, on remarque que le vecteur normal p associé
à H est p = y x^ 6= 0; la constante associée à l’hyperplan H est =
x^> (y x^)
p> x^: Ce choix étant fait, on obtient du fait de la la relation
(2.7)
p> x
; 8x 2 S;

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION37
c’est exactement la relation b). Reste à prouver a). On a
p> y

=
=
=
=
)

p> y p> x^
p> (y x^)
(y x^)> (y x^)
ky x^k2 > 0 ( y 6= x^ ) ky
p> y > .

x^k =
6 0)

Proposition 2.4 Soit S
Rn non vide convexe et fermé et y 2
= S:
Notons par (P1) (P2) et (P3) les trois propositions suivantes :
!
(P1) Il existe un vecteur p 2 Rn ; non nul ( p 6= 0 ) et 2 R; tel que :
p> y >
et p> x
8x 2 S:
!
(P2) Il existe un vecteur p 2 Rn ; non nul ( p 6= 0 ) tel que : p> y > sup
p> x : 8x 2 S :
!
(P3) Il existe un vecteur p 2 Rn ; non nul ( p 6= 0 ) tel que : p> y < inf
p> x : 8x 2 S
Preuve de la proposition 2.4
Montrons que (P1))(P2)
!
(P1) () il existe p 2 Rn ; ( p 6= 0 ) et 2 R tel que p> y >
et p> x
8x 2 S: Donc
p> y >
p> x; 8x 2 S;
(2.8)

(2.8) implique que est un majorant de l’ensemble p> x : x 2 S : Comme
le sup est le plus petit des majorants, on a :
p> y >

sup p> x : x 2 S :

d’où (P2).
Montrons maintenant que (P1))(P3):
!
(P1)() il existe p 2 Rn ; ( p 6= 0 ) et 2 R tel que p> y >
8x 2 S:Considérons
p1 = p et 1 =
:

et p> x

On obtiendra
p>
1y <

1

et p>
1x

1 ; 8x

2S

(2.9)

ou encore
p>
1y <

1

p>
1 x; 8x 2 S:

(2.10)

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION38
(2.10) implique que 1 est un minorant de l’ensemble p>
1 x; x 2 S : Si on
prend en considération que l’inf est le plus grand des minorants, on obtient :
p>
1y <

inf p>
1 x; x 2 S :

1

Ce qui donne (P3).
Montrons que (P2) ) (P1).
!
(P2)() Il existe un vecteur p 2 Rn ; non nul ( p 6= 0 ) tel que : p> y > sup
p> x : 8x 2 S :
Prenons
= sup p> x : x 2 S :

On a bien sur p> x
Ce qui donne (P1).

; 8x 2 S: D’autre part de (P2), on a aussi p> y > :

Montrons que (P3) ) (P1).
!
(P3)()Il existe un vecteur p 2 Rn ; non nul ( p 6= 0 ) tel que :
p> y < inf

p> x : 8x 2 S :

(2.11)

Prenons maintenant
p1 =

p et

1

=

=

inf p> x; x 2 S :

(2.12)

1:

(2.13)

(2.11) et (2.12) impliquent :
pT1 y >
Si on remarque que
inf p> x; x 2 S

p> x; 8x 2 S ;

et en prenant en considération (2.12), on a :
p>
1x
(2.13) et (2.14) donnent (P1).

1;

8x 2 S;

((2.14))

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION39

2.2.3

Support d’un ensemble

Dé…nition
Dé…nition 2.6 Soit S
Rn non vide, x 2 @S. L’hyperplan H =
p (x x) = 0 de vecteur normal p et passant par le point x s’appelle support de S au point x si seulement si S H + ou bien S H : Si S * H;
on dit que H est un support propre de S au point x:
>

H
H
S

S
H




x

S

x2


x1

Figure 1.9 : Support d’un ensemble

Conditions d’existence du support d’un ensemble
Comme on le verra dans le théorème suivant, le fait que l’ensemble S soit
convexe su¢ t pour prouver l’existence du support d’un ensemble S:
Théorème 2.3 Soit S
un vecteur p 6= 0 tel que

Rn ; S 6= ;, S convexe et x 2 @S: Alors il existe
p> (x

x)

0; 8x 2 S

(2.15)

Preuve du Théorème 2.3
x 2 @S; alors il existe une suite fyk g telle que
yk 2
= S et yk ! x

(2.16)

S est convexe férmé, yk 2
= S: Alors (voir Théorème 2.2), 8k 2 N, il existe
un hyperplan H (pk ; k ) ; de vecteur normal pk 2 Rn et de coé¢ cient k 2 R,
tel que :
>
p>
8x 2 S:
(2.17)
k
k yk > k et pk x

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION40
On peut toujours choisir fpk gk2N telle que kpk k = 1: D’autre part (2.17)
implique : Alors (théorème de séparation) ; 8k 2 N, 9pk 2 Rn tel que
p>
k yk

p>
k x;

fpk gk2N étant bornée, alors 9N1

8x 2 S

(2.18)

N tel que

pk ! p et kpk = 1

(2.19)

k2N1

Soit en passant à la limite (k ! 1; k 2 N1 ) dans la relation (2.18) et en
prenant en considération (2.16) et (2.19), on obtient :
p> x

p> x; 8x 2 S:

(2.20)

(2.20) implique bien sur (2.15), c’est à dire :
p> (x

0; 8x 2 S:

x)

Remarque 2.5 La relation (2.15) implique bien sûr qu’ il existe un
hyperplan H; support de S au point x
Remarque 2.6 Réciproquement supposons que H est support de S au
point x; alors par dé…nition il existe p 6= 0 tel que
p> (x

x)

0; 8x 2 S:

Prenons y 2 S, alors 9 fxn gn2N ; xn 2 S telle que xn ! y; On a bien sur
p> (xn

x)

0; 8n 2 N:

Par passage à la limite quand n ! 1; on aura
p> (y

x)

0; 8y 2 S:

Par conséquent on obtient la relation (2.15). On pourra par conséquent
prendre la relation (2.15) comme dé…nition.
Rn convexe et x^ 2
= int(S): alors, il existe un

Corollaire 2.5 Soit S
vecteur p non nul tel que

p> (x

x^)

0; 8x 2 S

Preuve du corollaire 2.5
!
Si x^ 2
= S ) 9p 6= 0 et 2 R tel que
p> x
p> x^ >

)

p> x
p> x^ <

Si x^ 2 @S (voir théorème 2.3).

) p> (x

x^)

0; 8x 2 S

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION41

2.2.4

Séparation de deux ensembles convexes

Séparation simple
Théorème 2.4 (Séparation simple) Soient S1 et S2 deux ensembles convexes
non vides tels que S1 \ S2 = ;: Alors il existe un hyperplan qui sépare S1
!
et S2 (séparation simple), ou ce qui est équivalent à 9p 2 Rn ; p 6= 0 tel
que :
inf p> x : x 2 S1
sup p> x : x 2 S2
(2.21)
Preuve du théorème 2.4
Considerons l’ensemble S dé…ni comme suit :
S = S1

S2 = fx1

x 2 : x 1 2 S1 ; x 2 2 S2 g :

S est convexe (voir exercice 2.3) et 0 2
= S. En e¤et, car dans le cas contraire,
9x1 2 S1 et x2 2 S2 tels que 0 = x1 x2 ) x1 = x2 : Par conséquent
S1 \ S2 6= ;. Ce qui est contraire à l’hypothèse.
!
D’après le corollaire 2.5, 9p 2 Rn ; p 6= 0 tel que :
p> x

0; 8x 2 S;

(2.22)

soit en prenant en considération la dé…nition de S; on obtient :
p> x1

p> x2 , 8x1 2 S1 ; 8x2 2 S2 :

Fixons x2 :D’après (2.23) on a :
8x1 2 S1 : p> x1

p> x2

(2.23)
(2.24)

(2.24) ) p> x2 est un minorant de l’ensemble p> x1 : x1 2 S1 : Puisque l’inf
d’un ensemble est le plus grand des minorants, on a donc :
inf p> x1 : x1 2 S

p> x2 :

(2.25)

La relation (2.25) est vraie pour tout x2 2 S2 : Donc inf p> x1 : x1 2 S1
est un majorant de l’ensemble p> x2 : x2 2 S2 :
Puisque le sup d’un ensemble est le plus petit des minorants, on aura donc
inf p> x1 : x1 2 S1

sup p> x : x 2 S2 ;

qui est exactement la relation (2.21). Reste à montrer que cette dernière
relation est équivalente à l’existence d’un hyperplan H(p; ) qui sépare simplement S1 et S2 . En e¤et. Posons :
= sup p> x : x 2 S2 :

(2.26)

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION42
La dé…nition du sup donne
8x 2 S2 : p> x

(2.27)

:

D’autre part la relation (2.21) implique
inf p> x1 : x1 2 S1

(2.28)

Par conséquent, en prenant en considération que l’inf d’un ensemble est aussi
un minorant de cet ensemble, on aura :
8x 2 S1 : p> x

inf p> x : x 2 S1

:

(2.29)

(2.27) et (2.29) impliquent que l’hyperplan H(p; ) de vecteur normal p et
de coé¢ cient sépare simplement S1 et S2 :
Remarque 2.6 Remarquons que dans la preuve de ce théorème on n’a
pas appliqué le théorème 2.2 car S convexe et 0 2
= S ne su¢ sent pas pour
appliquer le théorème 2.2 ( S n’est pas férmé).
Remarque 2.7 La séparation simple de deux ensembles disjoints n’exige
que la convexité de ce deux ensembles. La fermeture, et moins encore la
compacité, n’est pas exigée. Ceci n’est pas le cas dans la séparation forte de
deux ensembles S1 et S2 (voir le théorème 2.5 qui suit).

Séparation forte
Théorème 2.5 (Séparation forte) Soient S1 et S2 deux ensembles convexes
fermés non vides tels que S1 ou S2 est borné et S1 \ S2 = ;: Alors il existe
un hyperplan qui sépare S1 et S2 fortement ou ce qui est équivalent, il existe
!
p 2 Rn , p 6= 0 et " > 0 tels que
inf p> x : x 2 S1

" + sup p> x : x 2 S2

(2.30)

Preuve du théorème 2.5
Considerons l’ensemble S dé…ni comme suit :
S = S1

S2 = fx1

x 2 : x 1 2 S1 ; x 2 2 S2 g :

S est convexe et 0 2
= S (voir la preuve du théorème 2.4). On va démontrer
que S est fermé (Remarquons que S1 et S2 soient férmés n’implique pas que

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION43
S le soit aussi. Soit fxk gk2N une suite dans S qui converge vers x:Montrons
que x 2 S: En e¤et
xk = yk

zk ; yk 2 S1 ; zk 2 S2 :

(2.31)

Supposons par exemple que S1 est borné, S1 étant férmé devient compact et
par conséquent
9N1 N tel que yk ! y 2 S1 :
(2.32)
k2N1

Donc
yk

9
zk ! x =
k2N1

;

yk ! y
k2N1

) zk = yk

xk ! z

(2.33)

k2N1

S2 étant féemé par hypothèse, donc z 2 S2 :Par conséquent en prenant en
considération (2.33) on a :
x=y

z; avec ( y 2 S1 et z 2 S2 ) =) x 2 S1

S2 = S:

Donc S est fermé.
S est convexe et férmé 0 2
= S: Ceci nous permet d’appliquer le théorème
2.2, c’est à dire qu’il existe un hyperplan H(p; ") de vecteur normal p et de
coé¢ cient " tels que
p> x "; 8x 2 S
(2.34)
et

!
p> 0 < ":

(2.35)

L’inégalité (2.35) imlique que " > 0: Par conséquent et vu la dé…nition de
S on déduit :
!
9p 6= 0 et " > 0 tels que p> x1
Choisissons :

"+p> x2 ; 8x1 2 S1 et 8x2 2 S2 : (2.36)

= sup p> x : x 2 S2 : Bien sur on a
p> x

; 8x 2 S2

(2.37)

Considérons la relation (2.36). "+p> x2 est un minorant de l’ensemble p> x : x 2 S1 :
Soit en prenant en considération la dé…nition de l’inf d’un ensemble, on a
inf p> x : x 2 S1

p> x2 ; 8x2 2 S2 :

(2.38)

ou encore
inf p> x : x 2 S1

"

p> x2 ; 8x2 2 S2 :

(2.39)

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION44
(2.39) implique que le terme inf p> x : x 2 S1
" est un majorant de
>
l’ensemble p x2 : x2 2 S2 : Par conséquent on obtient
inf p> x : x 2 S1

"

sup p> x2 : x2 2 S2

(2.40)

inf p> x : x 2 S1

" + sup p> x2 : x2 2 S2

(2.41)

ou encore
La relation (2.41) implique
8x 2 S1 : p> x

inf p> x : x 2 S1

" + sup p> x2 : x2 2 S2 = " +
(2.42)

Finalement (2.37) et (2.42) donnent
8
9
: 8x 2 S2 =
< p> x
et
: >
;
p x " + : 8x 2 S1

(2.43)

(2.43) est exactement la dé…nition de la séparation forte des ensembles S1 et
S2 :

2.2.5

Applications

Parmi les applications des théorèmes de séparation, on peut citer le théorème dit de Farkas et le théorème de Gordan. Ces théorèmes que nous présentons maintenant, nous seront d’une grande utilité dans la partie conditions
d’optimalité des problèmes d’optimisation avec contraintes.
Théorème 2.6 (Farkas) Soit A une matrice d’ordre (m; n) et c un vecteur de Rn : Alors seulement une et une seule des deux propositions suivantes
a lieu :
(P1 ) Il existe x 2 Rn tel que Ax 0 et c> x > 0
(P2 ) il existe y 2 Rn tel que y 0 et A> y = c
Preuve du théorème 2.6
a) Supposons que (P2 ) admet une solution, alors
9y 2 Rn : y
Soit x 2 Rn tel que Ax

0 et A> y = c

(2.44)

0 montrons que
c> x

0:

(2.45)

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION45
En e¤et, d’après (2.44)
c> x = y > Ax

(2.46)

0

(2.46) ) (P1 ) n’a pas de solutions.
b) Supposons que (P2 ) n’a pas de solutions. Considérons alors l’ensemble S
suivant :
S = x 2 Rn : x = A> y; y 2 Rn ; y 0
(2.47)
S est non vide (car 0 2 S), convexe et fermé.
(P2 ) n’a pas de solution () c 2
= S:
!
D’après le théorème 2.1 9p 6= 0 ; 9 2 R tels que
p> c >

et p> x

; 8x 2 S

(2.48)

!
0 2 S: Par conséquent (2.48) implique
p> 0 = 0

:

(2.49)

> 0:

(2.50)

et
p> c >
D’autre part, d’après (2.48) aussi on a :
p > A> y

pour tout y

0:

(2.51)

La relation (2.51) est vraie si est seulement si
p > A>
(sinon 9 y > 0 tel que

0

(2.52)

< p> A> y) . Donc
Ap

0:

(2.52)

Conclusion, si (P2 ) n’a pas de solutions, alors il existe p 2 Rn tel que :
Ap

0 et cp> > 0;

(2.53)

et par conséquent (P1 ) est vraie.
Théorème 2.7 (Gordan) Soit A une matrice d’ordre (m; n), alors seulement un des deux systèmes suivants admet une solution
Système 1 :
9x 2 Rn : Ax < 0
(2.54)

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION46
Système 2 :
!
9!
y 2 Rn ; !
y =
6 0; !
y

!
0

et A> y = 0

Preuve
Considérons le système (2.54). Si A = (aij )1 i m;1 j
forme
8
a11 x1 + a12 x2 :::::a1n xn < 0
>
>
<
a21 x1 + a22 x2 :::::a2n xn < 0
::::::::::::::::::::::::::::::::
>
>
:
am1 x1 + am2 x2 :::::amn xn < 0
Dé…nissons s > 0 comme suit
s = min

1 i m

fai1 x1 + ai2 x2 :::::ain xn g =

n,

(2.55)

(2.54) s’écrit sous la

9
>
>
=
>
>
;

fai0 1 x1 + ai0 2 x2 :::::ai0 n xn g ; 1

(2.56)

i0

(2.57)
Avec ce choix de s (en supposant que le minimum est atteint en un seul point
i0 ); on obtient
8
9
a11 x1 + a12 x2 :::::a1n xn + s < 0 >
>
>
>
>
>
>
>
a
x
+
a
x
:::::a
x
+
s
<
0
>
>
21
1
22
2
2n
n
>
>
<
=
::::::::::::::::::::::::::::::::::
(2.58)
ai0 1 x1 + ai0 2 x2 :::::ai0 n xn + s = 0 >
>
>
>
>
>
>
>
:::::::::::::::::::::::::::::::::::
>
>
>
>
:
;
am1 x1 + am2 x2 :::::amn xn + s < 0
(2.58) s’écrit aussi sous la forme suivante
[A e]


0

B
B
[A; e] = B
B
@

a11
:
:
:
am1

:
:
:
:
:

:
:
:
:
:

x
s

: a1n
:
:
:
:
:
:
: amn

0,
1
1
1
1
1

(2.59)

1

C
C
C , e = (1; :::; 1) 2 Rm
C
A

e =.[A; e] , au point
On utilise le théorème de Farkas à la nouvelle matrice A
x
x
e=
et le point c suivant
s
0 1
0
B : C
B C
C
c=B
B : C
@ 0 A
1

m

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION47
On a bien sur

ex
A:e

cT :e
x = cT :

(2.60)

0
x
s

(2.61)

= s > 0:

(2.60) et (2.61) impliquent que la proposition (P1 ) du théorème de Farkas est
véri…ée. Ceci implique que ( d’après le théorème 2.6 ) que (P2 ) est impossible.
e =.[A; e] et cT = (0; 0; :::; 0; 1):
Explicitons (P2 ) avec nos nouveaux éléments A
On aura dans ce cas
il existe y 2 Rn tel que y
soit en explicitant

eT y = [A; e]> :y =
0 et A

il existe y 2 Rn tel que y

A>
e>

y = c; (2.62)

0 et A> y = 0 et eT y = 1:

(2.63)

(2.63) est équivalent au système (2) du théorème de Gordan, en remarquant
!
y = 1 implique que
que !
y
0 et eT !
!
y
Remarquons en…n que !
y

2.3

! ! !
0 et y =
6 0:

! ! !
0 et y =
6 0 n’est pas équivalent à !
y > 0:

EXERCICES

Exercice 2.1 Soient Si convexes ( i 2 I) , montrer que

T

Si est convexe.

i2I

Peut on a¢ rmer la même chose pour la réunion même …nie d’ensemble.

Exercice 2.2 Démontrer que si S est convexe alors H(S) = S:
Exercice 2.3 : Soient S1 et S2 deux ensembles convexes. Considérons
l’ensemble S suivant
S = S1

S2 = fx1

Montrer que S est aussi convexe.

x 2 : x 1 2 S1 ; x 2 2 S2 g :

CHAPITRE 2. ENSEMBLES CONVEXES ET THEOREMES DE SEPARATION48
Exercice 2.4 : Soient S1 et S2 deux sous ensembles non vides de Rn
tels que S1 S2 . Montrez que H(S1 ) H(S2 )
Exercice 2.5 Démontrer le corollaire 1.2 d’une autre façon ( en utilisant
les suites ).
Exercice 2.6 Démontrez que si S convexe avec int(S) 6= ;; alors :
a) int(S) = S
b) int(S) = int(S)
Exercice 2.7 Soit S Rn convexe et fermé. Montrer que S est l’intersection de tous les demi-espace fermés contenant S:
Aide Notons par L l’intersection en question.
a) S L
b) L S ? ( Supposez le contraire en prenant en considération le théorème
2.2)
Exercice 2.8 Soit S Rn non vide, et y 2
= H(S). Montrer qu’il existe
un hyperplan qui sépare fortement S et y:
Aide Appliquer le théorème 2.2 en faisant un bon choix se S:

Chapitre 3
FONCTIONS CONVEXES
3.1

Dé…nitions et propriétés générales

Dé…nition 3.1 Soient f : S ! R; où S est un ensemble convexe non
vide de Rn :
a) f est dite convexe dans S si et seulement si
f ( x1 + (1

)x2 )

f (x1 ) + (1

)f (x2 )

(3.1)

pour tout x1 ; x2 2 S et pour 2 [0; 1]
b) f est dite strictement convexe dans S si et seulement si
f ( x1 + (1

)x2 ) < f (x1 ) + (1

)f (x2 )

(3.2)

pour tout x1 6= x2 2 S et pour 2]0; 1[
c) f est dite fortement convexe ou uniformément convexe dans S si et
seulement si il existe une constante C > 0 tele que :
f ( x1 + (1

)x2 )

f (x1 ) + (1

)f (x2 )

1
C (1
2

) kx1

x2 k2 (3.3)

pour tout x1 ; x2 2 S et pour tout 2 [0; 1]
d) f est dite concave dans S (strictement concave dans S) si et seulement
si ( f ) est convexe (strictement convexe) dans S:

49


Documents similaires


analyse et optimisation convexe professeur benzine rachid
convexite et lipshitzianite
vickson rachmoulz
theoreme d arzela ascoli
r vision
fq1


Sur le même sujet..