Optimisation - Partie Linéaire - Examen de Janvier 2015
Cet examen est à livre fermé. Aucun appareil électronique n’est autorisé.
Les IG et INFO répondent à toutes les questions, les Mines aux questions 1-2-3 et les ELEC 1-2.
1. Vrai ou faux? Justifiez votre réponse ou donnez un contre-exemple.
(a) [5 points] Soit un polyèdre en dimension n défini au moyen de m contraintes d’inégalité.
Si vous disposez d’un sommet de ce polyèdre, alors
toutm!problème d’optimisation linéaire
sur ce polyèdre peut être résolu avec au plus m
n = (m−n)!n! pivotages de la méthode du
simplexe.
(b) [5 points] En toute solution optimale d’un problème d’optimisation linéaire de n variables
et dont la valeur optimale est bornée, il y a au moins n contraintes actives.
(c) [5 points] Le point (x1 , x2 , x3 ) = (−1, 0, 1) est un sommet dégénéré du polyèdre défini par
les inégalité suivantes
x1 + x2 + x3 ≤ 0, x1 + x2 ≤ 1, x1 + x3 ≤ 0, x2 + x3 ≤ 1, x2 ≥ 0 et x3 ≥ 0.
(d) [5 points] Soit le tableau simplexe suivant:
x1 x2 x3 x4 x5
0 0 1 1 0 z
0 1 −1 −1 0 8
0 0 −1 −2 1 0
1 0 2 −3 0 10
On peut en déduire que, pour le problème d’optimisation correspondant, la solution (10, 8,
0, 0, 0) est optimale, et correspond à un sommet dégénéré du polyèdre correspondant.
(e) [5 points] Pour avoir un sommet, un polyèdre en n dimensions sous forme géométrique doit
avoir au moins n inégalités.
2. [25 points] Distribution optimale de ressources. Vous êtes producteur de téléphones portables
et vous en produisez deux types: un portable ‘normal’ et un smartphone. Pour produire un
portable ‘normal’, on a besoin de 1 unité de verre, 2 unités de métal et 3 unités de plastique;
pour un smartphone, 3 unités de verre, 2 unités de métal et 1 unité de plastique. Le portable
‘normal’ se vend au prix de 100e et le smartphone de 200e. Vous disposez de 120 unités de
verre, de 180 unités de métal et 240 unité de plastique. Vous désirez maximiser votre profit.
(a) Modélisez ce problème comme un problème d’optimisation linéaire. (Pour simplifier, on
suppose que l’on peut produire un nombre non entier de téléphones.)
(b) Résolvez ce problème en utilisant la méthode du simplexe. Combien de téléphones portables
de chaque type allez-vous produire? Justifiez votre réponse. Que pouvez-vous dire sur le
sommet optimal obtenu?
1
3. [25 points] Soit le problème d’optimisation suivant
min 10x2 + 10x3
(x1 ,x2 ,x3 )∈R3
tel que 3x1 + 2x2 + x3 ≥ 30,
− x1 − 2x2 + 3x3 ≥ 20, et
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
(a) Ecrivez le dual de ce problème.
(b) Pour ce problème, énoncez le théorème de la dualité faible, et prouvez le.
Enoncez également le théorème de la dualité forte appliquée à ce problème.
(c) Calculez la solution optimale du dual (utilisez la méthode de votre choix), et déduisez-en
la solution optimale du primal en utilisant la complémentarité. Justifiez votre réponse.
(d) On remplace le membre de droite de la deuxième contrainte par 20 − pour ∈ R. En
utilisant la dualité faible, donnez une borne inférieure de la valeur optimale du problème
modifié en fonction de .
(e) Quelles conditions sont nécessaires pour fournir une valeur exacte de la valeur optimale en
fonction de à partir de la valeur optimale du problème original? Quelle est cette valeur?
(f) Votre patronne ne fait pas confiance aux ordinateurs, n’a pas jamais suivi de cours d’optimisation
mais maı̂trise parfaitement l’arithmétique. Comment pourriez-vous la convaincre qu’il
n’existe pas de solution meilleure que celle que vous avez calculée?
4. [25 points] On dispose d’un sac capable de supporter un poids maximal de 8kg et d’un ensemble
d’objets ayant chacun un poids (en kg) et une valeur (en euro). L’objectif est de remplir le sac
d’objets sans dépasser le poids maximal tout en maximisant la somme des valeurs des objets
qu’il contient. Vous disposez de 5 objets de poids respectifs 4, 3, 3, 2 et 2 kg et de valeurs
respectives 3, 5, 2, 2 et 3 e.
(a) Formulez ce problème comme un problème linéaire en nombres binaires.
(b) Ecrivez la relaxation linéaire de ce problème et résolvez la.
(c) Calculez toutes les solutions optimales de ce problème par branch and bound en utilisant
les relaxations linéaires (suivez strictement les étapes du branch and bound –n’utilisez pas
par exemple de solutions admissibles que vous auriez calculées à la main) et dessinez l’abre
de recherche. Quels objets allez-vous emporter?
(d) Combien de relaxations linéaires au minimum auriez-vous eu besoin pour trouver une seule
solution optimale (en considérant le cas le plus favorable)? Justifiez.