O PTIMISATION D ISCR ÈTE Semestre de printemps 2013
P ROF. F. E ISENBRAND Examen blanc 27 juin 2013
Nom : Prénom :
Exercice : 1 2 3 4 5 6 Σ
Note maximale : 10 10 10 10 10 10 50
Points obtenus :
Exercices choisis :
Contrôlez si le sujet est complet : il doit se composer de 9 pages (Exercices 1–6). Inscrivez vos nom et
prénom sur la couverture. La réponse doit être rédigée sous l’exercice, et éventuellement au recto. Justi-
fiez les réponses et argumentez d’une manière claire et compréhensible. Si vous avez besoin de papier,
demandez-en à l’un des assistants. Indiquez sur chaque feuille supplémentaire votre nom et l’exercice cor-
respondant.
Utiliser un stylo de couleur autre de rouge, pas de crayon !
Durée : 3 heures
Notation :
Chaque exercice est noté sur 10 points et vous devez travailler sur 5 exercices.
Indiquer les 5 exercices choisis dans le tableau ci-dessus !
Aucune aide n’est permise pendant l’examen !
1
Exercice 1 : (QCM, chaque question est notée dans {−1, 0, 1}, l’exercice rapporte max{0, Σ})
Aucune justification nécessaire. Marquer ’oui’ ou ’non’.
Des réponses fausses entraı̂nent des points négatifs !
a) Soit A ∈ Rm×n , b ∈ Rm . S’il existe λ ∈ Rm tel que AT λ ≥ 0 et bT λ < 0, ◦ oui ◦ non
alors le système Ax = b, x ≥ 0 est inadmissible.
b) Étant donné A ∈ Rm×n , b ∈ Rm , c ∈ Rn , on a ◦ oui ◦ non
min{cT x | Ax = b, x ≥ 0} = max{bT y | AT y ≤ c}
si les deux PL sont admissibles.
c) Considérer un polyèdre P non-vide et supposer que pour chaque variable ◦ oui ◦ non
xi , on ajoute soit la contrainte xi ≥ 0 soit xi ≤ 0. Est-il vrai que le polyèdre
résultant a au moins une solution basique admissible ?
d) Pour tout graphe non-orienté G = (V, E), la matrice d’incidence sommets- ◦ oui ◦ non
arêtes est totalement unimodulaire.
e) Étant donné le PL max{cT x | Ax ≤ b}, avec A ∈ Zm×n , b ∈ Zm , c ∈ Rn , A de ◦ oui ◦ non
plein rang-colonne.
Si A est totalement unimodulaire, alors chaque solution basique du PL est
un vecteur intégral.
f) Le programme linéaire suivant a une solution optimale qui est intégrale. ◦ oui ◦ non
max 3x1 + 2x2 + 4x3
x1 + x2 ≤1
x1 + x3 ≤1
x2 + x3 ≤1
x1 , x2 , x3 ≥ 0
g) Étant donné un PL ◦ oui ◦ non
max{cT x | Ax ≤ b},
avec A ∈ Rm×n , b ∈ Rm , c ∈ Rn . Si x(1) et x(2) sont des solutions optimales
du PL, alors le vecteur λ x(1) + (1 − λ )x(2) est une solution optimale pour
tout 0 ≤ λ ≤ 1.
h) Étant donné le PL max{cT x | Ax ≤ b}, avec A ∈ Rm×n , b ∈ Rm , c ∈ Rn , soit ◦ oui ◦ non
j la contrainte qui entre dans la base pendant l’itération i de l’algorithme du
simplexe.
Alors cette contrainte ne peut pas sortir de la base pendant l’itération (i+1).
i) Soit G = (V, A) un graphe orienté avec une fonction de longueur ` : A → ◦ oui ◦ non
Z. On peut décider s’il existe un cycle négatif (par rapport à `) en temps
O(|V | · |A|).
j) Le problème du sac-à-dos peut être résolu en temps polynômial. ◦ oui ◦ non
2
Exercice 2 (Dualité, RC):
Considérer le programme linéaire suivant :
min 2x1 + 2x2 + 4x3
x1 + 2x2 + 4x3 = 20
−x1 + 3x3 ≤ 10
(1)
− 2x2 + x3 ≥ 3
4x1 + x2 ≤ 40
x1 − 10x2 + x3 ≥ −3
(a) Trouver le dual du PL (1).
(b) Montrer que x∗ := ( 19 9 33 T
8 , 16 , 8 ) est une solution optimale du PL (1) en donnant une solution admissible
sous la forme duale.
Indication : Utiliser le théorème vu comme exercice (relâchement complémentaire) : étant donnée une
solution optimale x∗ sous forme primale, il existe une solution optimale y∗ sous forme duale telle que
y∗i = 0 pour toute ligne i du PL primal qui n’est pas satisfaite avec égalité par x∗ .
Solution:
Utiliser le verso pour plus d’espace
3
Exercice 3 (Sommets):
Un polyèdre P = {x ∈ Rn : Ax ≤ b} contient une droite, s’il existe un vecteur v ∈ Rn non-nul et un point
x∗ ∈ Rn de sorte que pour tout λ ∈ R, on a x∗ + λ · v ∈ P. Démontrer qu’un polyèdre non-vide ne contient
pas de droite si et seulement si la matrice A est de plein rang-colonne.
Solution:
Utiliser le verso pour plus d’espace
4
Exercice 4 (Algorithme du Simplexe):
Considérons le programme linéaire suivant :
max y1 + 2y2 + 3y3
−y1 + 4y2 + 2y3 ≤ 5
2y1 − 6y2 − y3 ≤ 2
2y1 − 3y2 + 4y3 ≤ 1
−y1 ≤ 0
−y2 ≤ 0
−y3 ≤ 0
Résolvez le PL en utilisant l’algorithme du simplexe avec la règle de Bland.
Commencez avec la base B = {4, 5, 6} et le sommet (0, 0, 0).
Pour chaque itération de l’algorithme du simplexe, indiquer l’index de la contrainte qui entre dans la base,
l’index de la ligne qui sort de la base, la nouvelle base et la solution basique.
Donner une solution optimale et sa valeur.
Remarque : Pour l’examen, on vous donne les inverses de toutes les matrices qui correspondent à une base.
Solution:
Utiliser la page suivante pour plus d’espace
5
Exercice 5 (Modéliser un flot):
Soit G = (V, E) un graphe non-orienté biparti (c-à-d qu’il existe A, B ⊂ V de sorte que V = A ∪ B et
E ⊆ {{u, v} | u ∈ A, v ∈ B}).
Donner une manière de trouver une couverture minimum de sommets dans G qui s’exécute en temps
O(|V | · |E|), en utilisant des flots.
Rappel : Une couverture de sommets est un sous-ensemble des sommets qui contient (au moins) une ex-
trémité de chaque arête.
Solution:
Utiliser la page suivante pour plus d’espace
6
Exercise 6 (Programmation dynamique):
Considérer le jeu suivant (jeu de Nim ou Prends! ) :
Étant donné n tas d’allumettes de taille c1 , . . . , cn . À tour de rôle, chaque joueur choisit le tas de son choix,
et dans ce tas, prend le nombre d’allumettes qu’il veut, au moins une. Le vainqueur est celui qui peut jouer
en dernier, c’est-à-dire celui qui prend la dernière allumette.
Considérer ce jeu entre deux joueurs A et B où A commence. Donner un algorithme qui décide lequel des
deux peut obtenir la victoire de force (c’est-à-dire indépendant des décisions de l’autre, il rapporte le jeu).
Indication : Vous pouvez utiliser le fait qu’il existe toujours une stratégie gagnante pour un des deux joueurs.
Solution:
Utiliser le verso pour plus d’espace
