LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 1/6

Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
2022.6.3.461

1
PRÉNOM et NOM : NOMA

Question 1 - Optimisation d’un mix énergétique [∼7 points].

Sur un ı̂le inhabitée jusqu’ici, on décide d’installer de nouveaux moyens de production d’électricité.
Trois technologies sont disponibles, et on installe respectivement x1 , x2 et x3 (MW) de capacité dans chacune
d’elles (il s’agit de variables continues, positives ou nulles).
Chaque MW investi va produire annuellement un certain nombre de GWh, respectivement 1, 4 et 4 (GWh par
MW). La production totale doit être égale à 400 (GWh).
On dispose d’un budget total de 1200 (millions d’euros), qu’on peut utiliser totalement ou partiellement. Le coût
par MW investi est respectivement de 2, 40 et 10 (millions d’euros par MW) pour chaque technologie.
Chaque technologie émet une quantité de CO2 par MW investi, repectivement 2, 8 et 0 (millions de tonnes de CO2
par MW). Le total du CO2 émis ne peut dépasser 200 (millions de tonnes).
Enfin on cherche à minimiser le coût total de l’électricité produite : le coût unitaire par MW investi est respecti-
vement de 2, 80 et 10 (millions d’euros par MW) pour chaque technologie.
Ce problème d’optimisation peut-être formulé linéairement : on obtient le modèle (MIX) suivant



 x1 + 4x2 + 4x3 = 400 (production)

 2x + 40x + 10x
1 2 3 ≤ 1200 (budget)
min 2x1 + 80x2 + 10x3 tel que (MIX)
(x1 ,x2 ,x3 )  2x1 + 8x2

 ≤ 200 (CO2 )

 x ≥ 0, x ≥ 0, x ≥ 0
1 2 3

1a Reformulez ce problème sous la forme primale standard (appropriée pour appliquer l’algorithme du simplexe).

1b Supposez qu’on décide d’investir uniquement dans x3 (et donc x1 et x2 sont nulles).
Démontrez que cette solution correspond à une solution admissible de base et calculez toutes ses composantes.

1c Écrivez le tableau simplexe canonique correspondant à la solution admissible du point précédent.

 LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 2/6
Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
2022.6.3.461

2
1d Partez du tableau écrit au point précédent et appliquez la méthode du simplexe jusqu’à l’obtention d’une
solution optimale (peu de pivots sont nécessaires, mais n’écrivez pas trop grand).

Réponse finale : x1 = x2 = x3 =

1e Écrivez le dual du problème d’optimisation linéaire (MIX) qui vous a été fourni au départ (on ne demande pas le
dual du problème reformulé au point 1a, mais celui du problème original avant reformulation).

1f Que pouvez-vous déduire à propos de la solution optimale du problème dual obtenu au point 1e si vous savez
que la solution optimale du problème (MIX) n’utilise pas la totalité du budget ?

1g Que pouvez-vous déduire à propos de la solution optimale du problème dual obtenu au point 1e si vous savez
que la solution optimale du problème (MIX) utilise la première technologie (c’est-à-dire que x∗1 > 0) ?

1h Calculez la solution optimale du problème dual obtenu au point 1f (vous pouvez utiliser entre autres les informations
fournies aux points 1f et 1g, ou toute autre information déjà obtenue).

1i En utilisant une méthodologie vue au cours, proposez le prix (en euros) qu’on devrait être prêt à payer pour
diminuer d’une tonne les émissions de CO2 . Expliquez votre démarche.
 LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 3/6
Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
2022.6.3.461

3
PRÉNOM et NOM : NOMA

Question 2 - Modélisations linéaire [∼4 points].

Pour chacune des deux sous-questions ci-dessous, qui sont indépendantes, il est demandé de formuler le problème
d’optimisation à l’aide d’un modèle linéaire utilisant des variables continues ainsi que, uniquement si c’est nécessaire,
des variables entières ou binaires. Il n’est pas demandé d’expliquer le fonctionnement du modèle fourni.

2a Soit n un entier donné. On considère trois vecteurs donnés u, v et w, tous les trois dans Rn , et on cherche à
identifier un vecteur inconnu x, aussi dans Rn , qui soit le plus proche possible de ces trois vecteurs u, v et w.
Plus précisément, on mesure la distance entre le vecteur x à déterminer et chacun des vecteurs donnés à l’aide de la
norme `1 , qui se calcule selon les formules suivantes
Xn Xn Xn
kx − uk1 = |xi − ui |, kx − vk1 = |xi − vi |, kx − wk1 = |xi − wi |.
i=1 i=1 i=1
Le problème à résoudre consiste à calculer un vecteur x qui minimise la plus grande des trois distances kx − uk1 ,
kx − vk1 et kx − wk1 (on cherche donc à minimiser le maximum pris entre ces trois quantités).

2b Dans une variante du Sudoku, on doit remplir une grille 10 × 10 uniquement à l’aide des entiers 1, 2, 3, 4 et 5
(cinq valeurs possibles). Sur chaque ligne de la grille on doit trouver exactement deux entiers de chaque valeur. De
même, sur chaque colonne de la grille on doit trouver exactement deux entiers de chaque valeur. Enfin un ensemble
T de triplets (x, y, z) est fourni, où chaque triplet (x, y, z) fournit un indice de la forme “la valeur de la case (x, y)
n’est pas égale à z” (par exemple T pourrait être l’ensemble {(1, 1, 2), (5, 7, 3), (8, 9, 1)}).
On cherche alors une grille vérifiant les contraintes et dont la somme des valeurs aux quatre coins est maximale.
Commencez votre réponse par une description de la signification des variables de votre modèle.
 LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 4/6
Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
2022.6.3.461

4
Question 3 - Projection sur une boule [∼5 points]
Dans l’espace R3 on considère la boule B centrée à l’origine et de rayon R, correspondant à l’équation suivante
(une boule est une sphère avec son intérieur) :
B = {X = (x1 , x2 , x3 ) ∈ R3 tels que x21 + x22 + x23 ≤ R2 }.
Soit un point P = (p1 , p2 , p3 ) donné. On cherche, parmi tous les points X = (x1 , x2 , x3 ) de cette boule B, celui qui
se trouve le plus proche de P . Plus précisément, afin que la fonction objectif soit de classe C 1 , on va minimiser le
carré de la distance entre les points P et X. Remarque : la distance utilisée ici est la distance Euclidienne usuelle.

3a Formulez ce problème comme un problème de minimisation sous contrainte.

3b Déterminez si ce problème est convexe. Justifiez soigneusement.

3c Écrivez les conditions d’optimalité KKT relatives à ce problème.

3d Déterminez si les conditions KKT sont nécessaires pour ce problème. Justifiez.

3e Déterminez si les conditions KKT sont suffisantes pour ce problème. Justifiez.

3f A l’aide des conditons KKT mais sans les résoudre entièrement, démontrez que la solution optimale de ce
problème est toujours un multiple du vecteur P (c-à-d que le vecteur (x∗1 , x∗2 , x∗3 ) est multiple de (p1 , p2 , p3 )).

(suite de la Question 3 à la page suivante)

 LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 5/6
Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
2022.6.3.461

5
PRÉNOM et NOM : NOMA

3g Résolvez les conditions KKT, et exprimez la solution en fonction du point P = (p1 , p2 , p3 ).

Indice : il faut discuter deux cas distincts.

3h Décrivez sommairement une méthode d’optimisation qui, à l’aide de la solution du problème étudié ci-dessus,
serait capable de minimiser une fonction quelconque f (x1 , x2 , x3 ) (de classe C 1 ) sous la contrainte que (x1 , x2 , x3 ) ∈ B
(il est possible de répondre à cette sous-question sans avoir répondu aux précédentes).

Question 4 [∼2 points]

Soit la fonction d’une variable f (x) = x4 − x3 − 3x qu’on cherche à minimiser. x2 = 1.247222222222222

On décide de lui appliquer une certaine méthode d’optimisation vue au cours, à x3 = 1.238831009414959
partir de l’itéré initial x0 = 1. On obtient d’abord l’itéré x1 (non communiqué) x4 = 1.238754508894826
puis les itérés ci-contres (fournis avec 15 décimales) x5 = 1.238754502571373
x6 = 1.238754502571373

4a Déterminez à quel type de convergence on a affaire. Expliquez comment vous avez déterminé votre réponse.

4b Déduisez la méthode qui a été utilisée, puis calculez l’itéré x1 .

 LINMA1702 - Optimisation I – Examen – 3 juin 2022 – 3h – page 6/6 2022.6.3.461

Sans calculatrice – répondre dans les cadres aux 5 questions – pondération indicative
6
PRÉNOM et NOM : NOMA

Question 5 [∼2 points]

La figure ci-contre représente un problème d’optimisation

linéaire en nombres entiers, à deux variables (abscisse x 2.5
et ordonnée y). Les points entiers sont représentés par
les petits disques, et les contraintes linéaires définissent
la région grisée. La fonction objectif consiste à maximiser 2.0
l’abscisse (c’est-à-dire trouver le point se trouvant le plus
à droite possible).
1.5
Question 5a
Indiquez sur la figure à droite la solution optimale du 1.0
problème en nombres entiers (pointez avec une flèche
marquée “O”) et donnez sa valeur :
0.5
(x∗ , y ∗ ) =

Indiquez la solution optimale du problème relaxé (pointez 0.0

-0.5
avec une flèche marquée “R”) et donnez sa valeur :

(xR , yR ) = 0.0 0.5 1.0 1.5 2.0 2.5

Question 5b
Supposez qu’on applique l’algorithme Branch and Bound
à ce problème. Au premier nœud du problème, on décide
2.5
de brancher sur la seconde variable (l’ordonnée y).
Quelles seront les deux contraintes qu’on ajoutera
aux contraintes de départ pour créer ces deux sous- 2.0
problèmes ?

1.5

Question 5c
Représentez sur la figure à droite les deux régions corres- 1.0
pondant aux deux sous-problèmes créés par ce branche-
ment, et qu’il faut explorer après ce premier nœud.
Pour chacune d’elles hachurez la région définie par les 0.5
contraintes linéaire correspondantes. Indiquez pour cha-
cun de ces deux nœuds (de ces deux sous-problèmes) la
0.0
solution optimale du problème relaxé (pointez avec des

-0.5
flèches marquées “R”)
0.0 0.5 1.0 1.5 2.0 2.5

5d Décrivez en détail la suite du déroulement de l’algorithme Branch and Bound appliqué à ce problème.