Solutions — Chapitre 1 : Optimisation Combinatoire

Basé sur : Présentation_Chapitre_1_Optimisation_Combinatoire.pdf

Méziane Aïder (2021)

Référence du cours : voir le fichier de cours fourni pour les définitions et hypothèses. filecite-
turn0file0

Introduction
Ce document fournit des formulations et solutions aux exercices du chapitre 1. Pour chaque
exercice, on donne une formulation en variables binaires ou entières, une courte explication des
étapes, et lorsque pertinent, la solution numérique.

Exercice 1
Énoncé résumé : Sélection d’investissements parmi {1, . . . , 7}. Variables binaires xj ∈ {0, 1}.
Solutions – formulations :
• (1) 7j=1 xj ≤ 6.
P

• (2) 7j=1 xj ≥ 1.
P

• (3) x1 + x3 ≤ 1.
• (4) x4 ≤ x2 .
• (5) x1 = x5 .
• (6) j∈{1,2,3} xj ≥ 1 ou
P P
j∈{2,4,5,6} xj ≥ 2.
Remarque : Pour représenter la disjonction (öu¨), utiliser une variable binaire auxiliaire y et
une constante M suffisamment grande.

Exercice 2
Enoncé : stocker produits ai dans réservoirs bj ; minimiser nombre réservoirs utilisés.
Formulation (a) : yj = 1 si réservoir j utilisé, xij = 1 si produit i dans réservoir j.
n
X
min yj
j=1
Xn
s.t. xij = 1, i = 1, . . . , m
j=1
Xm
ai xij ≤ bj yj , j = 1, . . . , n
i=1
xij ∈ {0, 1}, yj ∈ {0, 1}.

1
(b) Dual : On peut écrire le dual du relaxé (PL) en introduisant multiplicateurs πi pour les
contraintes d’affectation et µj pour les capacités; le dual min/max dépend de la forme choisie –
voir cours pour détail formel.

Exercice 3
Bin packing : Formulation (PL entier) : Variables : yk ∈ {0, 1} si boîte k utilisée,
xik ∈ {0, 1} si objet i dans boîte k.
n
X
min yk
k=1
n
X
s.t. xik = 1, ∀i
k=1
n
X
wi xik ≤ Cyk , ∀k
i=1
xik ∈ {0, 1}, yk ∈ {0, 1}.

Remarque : On peut restreindre le nombre de boîtes à n (au pire une par objet).

Exercice 4
Feux tricolores : Modélisation proposée : Représenter chaque mouvement par une variable
binaire; imposer des contraintes d’exclusion pour mouvements conflictuels. Construire des phases
compatibles et déterminer durées optimales des phases (PL mixte).

Exercice 5
Tournoi : Construire le graphe des rencontres restantes; problème équivalent au coloriage
d’arêtes (ou sommets selon modélisation) pour minimiser semaines. Donner une coloration par
inspection ou via algorithme glouton.

Exercice 6
Horaire étudiant : Formulation : Variables xik = 1 si section P (i, k) choisie. Contraintes :
exactement 1 section par cours, pas de chevauchement, maximiser pik xik . Pour limiter à au
plus 2 cours consécutifs, ajouter contraintes sur fenêtres temporelles de 3 heures : sections
P
dans fenêtre ≤ 2. Pour commencer le plus tard possible, minimiser la plus petite heure choisie
via variables auxiliaires.

2
Exercice 7
Décentralisation : Formulation (transport + investissement) :
X X
min fi yi + cij xij
i i,j
X
s.t. xij = bj , ∀j
i
X
xij ≤ ai yi , ∀i
j

xij ≥ 0, yi ∈ {0, 1}.

Si on n’ouvre au plus p unités, ajouter i yi ≤ p.

Exercice 8
Découpe motif répété : Modéliser positions possibles pour chaque morceau, variables bi-
naires pour choix, contraintes de non-chevauchement; objectif : minimiser somme des chutes.
(Formulation classique de découpe en 1D.)

Exercice 9
Naftal : problème d’ouverture d’entrepôts avec contraintes de capacité et coût fixe.
Formulation : même que le problème de localisation (yj ouverture, xij quantit),
P minimisercotf ixe+
transport, contraintesdecapacitsetcouverturedesdemandes, ventuellement yj ≤ p.

Exercice 10
Usine deux pièces : (a) Formulation : variables entières x1 , x2 nombres de pièces p1 et p2.

max 2x1 + x2
s.t. 3x1 + 4x2 ≤ 15 (M 1)
(contrainte sur M 2 selon interprétation de l’énoncé)
x1 , x2 ∈ Z≥0 .

(b,c,d,e) : L’énoncé contient une contrainte mal précisée pour M2; il faut préciser les temps de
mobilisation sur M2 pour compléter.

Exercice 11
Exercice 11 : Sac à dos (données) Weights a = (19, 17, 15, 13), capacity b = 30, values
c = (9, 7, 5, 4). (a) Formulation (K) :

max 9x1 + 7x2 + 5x3 + 4x4

(b) Relaxation continue (fractionnaire) : x1 = 1.0000, x2 = 0.6471, x3 = 0.0000, x4 =

3
x = (0, 0, 0, 0), poids = 0, valeur = 0. x = (1, 0, 0, 0), poids = 19, valeur = 9. x =
(0, 1, 0, 0), poids = 17, valeur = 7. x = (0, 0, 1, 0), poids = 15, valeur = 5. x =
(0, 0, 0, 1), poids = 13, valeur = 4. x = (0, 1, 0, 1), poids = 30, valeur = 11. x =
(0, 0, 1, 1), poids = 28, valeur = 9. Solution entière optimale : x∗ = (0, 1, 0, 1) avec
valeur 11.

Exercice 12
PVC invariances : Voir démonstrations : (a) multiplication par facteur positif préserve l’ordre;
(b) ajout d’une constante à toutes les distances ajoute la même constante à la longueur de chaque
tournée; (c,d,e) arguments analogues par considération des termes constants et permutations.

Exercice 13
(a) y = max(x1 , x2 ) : imposer y ≥ x1 , y ≥ x2 et y ≤ x1 + M z, y ≤ x2 + M (1 − z) avec
z ∈ {0, 1}. (b) y = min(x1 , . . . , xn ) : imposer y ≤ xi pour tout i et maximiser y; pour égalité
utiliser variables auxiliaires et contraintes complémentaires.

Exercice 14
Contraintes logiques (groupes) : Utiliser variables indicatrices binaires et M -big-M pour
convertir les implications en contraintes linéaires.

Exercice 15
Au moins k ensemblesP contiennent x : Introduire yi ∈ {0, 1} indiquant si x ∈ Si (activation
de gi (x) ≥ 0) et imposer m
i=1 yi ≥ k.

Exercice 16
(a) Variables bornées entières ⇒ bivalentes : développer chaque variable bornée en somme
de variables binaires (codage en base binaire). (b) Réduction en sac à dos : regrouper bornes
et coefficients pour obtenir une instance de sac à dos via transformations linéaires; voir preuve
constructive en cours.

Exercice 17
(a-b)
P Formulation générale : Variables xij =
P1 si tâche Ti affectée à machine Mj ; contraintes
: j xij = 1, i xij = n; introduire T tel que i cij xij ≤ T pour chaque machine et minimiser
P
T . (c) Cas numérique n=2 : Meilleur makespan trouvé par énumération exhaustive : 33.
assign = (1, 1, 2, 2), temps M 1 = 33, M 2 = 30.

Exercice 18
Propriétés : (a) Si une solution optimale du relaxé est entière, elle est aussi optimale pour
l’entier. (b) Si le domaine relaxé est borné, alors l’ensemble des solutions entières est fini. (c)
Exemples et contre-exemples se traitent par construction; voir cours pour détails.