Optimisation en nombres entiers

Nombres entiers - Mathématique accueil – CSDM 2014 3 LES NOMBRES ENTIERS SUR LA DROITE NUMÉRIQUE Sur la droite numérique, un nombre entier situé à droite de zéro est positif

Optimisation en nombres entiers - TRANSP-OR

• Sur un chantier, il faut affecter 4 ouvriers à 4 tâches • L’ouvrier ieffectue la tâche jen cij heures : Ouvrier Tâche 1 Tâche 2 Tâche 3 Tâche 4 A 9 2 7 8 B 6 4 3 7 C 5 8 1 8 D 7 6 9 4 • Comment répartir les tâches pour que le nombre total d’heures soit le plus petit possible ? Optimisation en nombres entiers – p 32/83

Problèmes de la semaine (CM2)

2) A tous les deux, combien de pièces possèdent Tom et Anaïs ? PROBLEME 14 Mobiliser les résultats des tables de multiplication Décomposer un nombre entier en produit de deux nombres Lilou a réalisé un gros bloc avec des cubes sans laisser de trou 1) Combien Lilou a-t-elle utilisé de cubes pour réaliser son bloc ?

Mathématiques : Multiplier un nombre décimal par un nombre entier

Mathématiques : Multiplier un nombre décimal par un nombre entier 1) Petit problème Avant de répondre aux questions interroge-toi sur les opérations à effectuer Complète ensuite la ligne intitulée « Ordre de grandeur du résultat » du tableau (sans poser l’opération, c’est inutile)

Numération décimale (nombres entiers)

310, 320: l’élève ne onsidère pas 0 comme un chiffre comme les autres 7) Placer des nombres sur une ligne Procédures ① Placer ces repères précisément (grâce au comptage des graduations, par exemple) ② Placer ces repères de manière approximative quand les graduations ne permettent pas de placer le nombre précisément

fichier exercice maths CM2 - La classe de Mallory

7–Connaître les multiples et diviseurs d’un nombre Parmi les nombres suivants, entoure les multiples de 3 1 – 22 – 3 – 45 – 5 – 16 – 7 – 18 – 9 – 111 - 54 – 24 - 58 Parmi ces mêmes nombres trouve celui qui est multiple de 2, 3, 4, 6 et 8 en même temps : _____ Calc 8 – Diviser un entier par un nombre à un iffre

La division : cours de maths en 6ème - Mathovore

Un nombre entier est multiple de 5 si son chiffre des unités est 0 ou 5 divisible par 5 Règle 4 Un nombre entier est multiple de 9 si la somme de ses chiffres est dans la table de 9 divisible par 9 Règle 5 Un nombre entier est multiple de 4 si le nombre formé par les deux derniers chiffres est dans la table de 4

Optimisation en nombres entiers

Michel Bierlaire

michel.bierlaire@epfl.ch

EPFL - Laboratoire Transport et Mobilit

´e - ENAC

Optimisation en nombres entiers - p. 1/83

DéfinitionsOptimisation en nombres entiers

Un problème d'optimisation en nombres entiers est un problème d'optimisation dont toutes les variables sont contraintes à neprendre que des

valeurs entières.Variables discrètes : nombre d'objets à considérer, nombred'actions à effectuer, etc.

Nombres de vélos à installer sur le campus. Nombres d'ouvriers à affecter à un chantier. Variables binaires (0/1) : oui/non, allumer/éteindre, etc.

Utiliser la voiture ou pas.

Construire un pont ou pas.

Allumer la climatisation ou pas.

Optimisation en nombres entiers - p. 2/83

DéfinitionsOptimisation mixte en nombres entiers Un problème d'optimisation mixte en nombres entiers est un problème d'optimisation dontcertainesvariables sont contraintes à ne prendre que des valeurs entières.Mobilité : Décision binaire : acheter une seconde voiture ou non. Décision continue : nombre de kilomètres à effectuer.

Energie :

Décision binaire : installer une nouvelle chaudièreélectricité/gaz. Décision continue : quantité de gaz à brûler.

Optimisation en nombres entiers - p. 3/83

Introduction

Problème d'optimisation linéaire en nombres entiers min x?RncTx sous contraintes Ax=b x≥0 x?N

Optimisation en nombres entiers - p. 4/83

Introduction

Problème d'optimisation linéaire binaire min x?RncTx sous contraintes Ax=b x≥0 x? {0,1}

Optimisation en nombres entiers - p. 5/83

Introduction

Approche intuitive immédiate :

Ignorer les contraintes d'intégralité.

Résoudre le problème linéaire.

Si la solution n'est pas entière, arrondir à l'entier le plusproche.

En général, cela ne fonctionne pas !

Optimisation en nombres entiers - p. 6/83

Exemple

min x?R2-3x1-13x2 sous contraintes x

1,x2≥0

1,x2entiers

Optimisation en nombres entiers - p. 7/83

Exemple : polytope des contraintes012345

0 1 2 3 4 5 6 7 8 9 10

Optimisation en nombres entiers - p. 8/83

Exemple : solution du problème continu012345

0 1 2 3 4 5 6 7 8 9 10

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 9/83

Exemple : contraintes d'intégralité012345

0 1 2 3 4 5 6 7 8 9 10

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 10/83

Exemple : voisins non admissibles012345

0 1 2 3 4 5 6 7 8 9 10

Voisins non admissibles

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 11/83

Exemple : solution du problème discret012345

0 1 2 3 4 5 6 7 8 9 10

Voisins non admissibles

Solution optimale non entière(9.2,2.4)

Solution optimale entière

Optimisation en nombres entiers - p. 12/83

Problèmes

Il y a2nfaçons d'arrondir une solution non entière. Laquelle choisir ? Arrondir une solution non entière peut générer une solutionnon admissible. La solution arrondie peut se trouver très loin de la solutionoptimale.

Optimisation en nombres entiers - p. 13/83

Problème d'investissement

Une société désire investir dans l'énergie hydro-électrique. Les ingénieurs ont identifié 4 sites potentiels pour laconstruction de barrages. Pour chaque site, ils ont évalué les coûts d'investissement, et le bénéfice attendu sur le long terme. La société a une capacité d'investissement de 1400 kCHF.

Quels barrages doit-elle construire ?

Barrage Coût Bénéfice Rendement

1 500 1600 3.20

2 700 2200 3.14

3 400 1200 3.00

4 300 800 2.67

Optimisation en nombres entiers - p. 14/83

Problème d'investissement

Modélisation :

Variables de décision:x1,x2,x3,x4.

x i=?

1si le barrageiest choisi,

0sinon.

Fonction objectif : maximiser le bénéfice max16x1+ 22x2+ 12x3+ 8x4

Contrainte : capacité d'investissement

Optimisation en nombres entiers - p. 15/83

Problème d'investissement

Problème linéaire continu :

max x?R416x1+ 22x2+ 12x3+ 8x4 sous contraintes x

1,x2,x3,x4≥0.

Solution optimale :

1= 2.8,x2= 0,x3= 0,x4= 0.

Optimisation en nombres entiers - p. 16/83

Problème d'investissement

Solution optimale :

1= 2.8,x2= 0,x3= 0,x4= 0.

Décision : ne construire que le barrage 1.

Coût : 500 kCHF

Somme non investie : 900 kCHF

Bénéfice : 1600 kCHF

Optimisation en nombres entiers - p. 17/83

Problème d'investissement

Problème linéaire continu 2 :

max x?R416x1+ 22x2+ 12x3+ 8x4 sous contraintes

Solution optimale :

1= 1,x2= 1,x3= 0.5,x4= 0.

Optimisation en nombres entiers - p. 18/83

Problème d'investissement

Solution optimale :

1= 1,x2= 1,x3= 0.5,x4= 0.

Décision : construire les barrages 1 et 2.

Barrage 3 : plus assez d'argent pour le construire.

Coût : 1200 kCHF

Somme non investie : 200 kCHF

Bénéfice : 3800 kCHF

Optimisation en nombres entiers - p. 19/83

Problème d'investissement

Problème linéaire discret :

max x?R416x1+ 22x2+ 12x3+ 8x4 sous contraintes x

1,x2,x3,x4? {0,1}

Solution optimale :

1= 0,x2= 1,x3= 1,x4= 1.

Optimisation en nombres entiers - p. 20/83

Problème d'investissement

Solution optimale :

1= 0,x2= 1,x3= 1,x4= 1.

Décision : construire les barrages 2, 3 et 4.

Coût : 1400 kCHF

Somme non investie : 0 kCHF

Bénéfice : 4200 kCHF

Le barrage correspondant au plus haut rendement n'est passélectionné. Conclusion : l'approche "intuitive" ne fonctionne pas.

Optimisation en nombres entiers - p. 21/83

Conditions d'optimalité

Il n'est pas possible de caractériser la solution optimale d'un problème d'optimisation en nombres entiers. Autrement dit, il n'y a pas de conditions d'optimalité pourl'optimisation discrète. Cela complique considérablement la résolution du problème. Il y a essentiellement deux manières d'aborder le problème.

Optimisation en nombres entiers - p. 22/83

Algorithmes

Méthodes exactes

la solution optimale est fournie,

mais le temps nécessaire pour la trouver est une fonctionexponentielle de la taille du problème.

Méthodes heuristiques

une "bonne" solution est fournie,

aucune garantie d'optimalité,

aucune mesure de qualité de la solution,

performances évaluées empiriquement sur des problèmesconnus.

Optimisation en nombres entiers - p. 23/83

Branch & bound

Idées :

Parcours systématique de l'ensemble admissible.

Diviser pour conquérir.

Utilisation de bornes sur le coût optimal pour éliminer desrégions admissibles sans les explorer.

Optimisation en nombres entiers - p. 24/83

Branch

Soit le problème d'optimisationP

minf(x) sous contraintes x?F

Fest l'ensemble des solutions admissibles.

Soit une partition deF

F=F1?...?FK.

Soitx?kla solution optimale du problèmePk

minf(x) sous contraintes x?Fk

Optimisation en nombres entiers - p. 25/83

Branch

Pour toutk,x?kest admissible pour le problèmeP.

Soititel que

Alors,x?iest la solution optimale du problèmeP. Motivation : chaque sous-problème est plus simple que leproblème initial. P P1 P2 PK

Optimisation en nombres entiers - p. 26/83

Branch

Et chaque problème peut à nouveau être partitionné. P P1 P2 P21 P22 P23 P231 P232 P233 .........PK

Optimisation en nombres entiers - p. 27/83

Branch

Le nombre de sous-problèmes devient vite très grand. Il faut éviter de passer toutes les combinaisons possibles en revue.

Idée : utiliser des bornes.

Optimisation en nombres entiers - p. 28/83

Bound

Soit le sous-problèmePk

minf(x) sous contraintes x?Fk On suppose que l'on peut calculer facilement une borneinférieurebk b Soity?Fune solution admissible du problèmeP.quotesdbs_dbs48.pdfusesText_48

[PDF] Optimisation en nombres entiers - TRANSP-OR

Optimisation en nombres entiers

Michel Bierlaire

EPFL - Laboratoire Transport et Mobilit

´e - ENAC

Optimisation en nombres entiers - p. 1/83

DéfinitionsOptimisation en nombres entiers

Utiliser la voiture ou pas.

Construire un pont ou pas.

Allumer la climatisation ou pas.

Optimisation en nombres entiers - p. 2/83

Energie :

Optimisation en nombres entiers - p. 3/83

Introduction

Optimisation en nombres entiers - p. 4/83

Introduction

Optimisation en nombres entiers - p. 5/83

Introduction

Approche intuitive immédiate :

Ignorer les contraintes d'intégralité.

Résoudre le problème linéaire.

En général, cela ne fonctionne pas !

Optimisation en nombres entiers - p. 6/83

Exemple

1,x2≥0

1,x2entiers

Optimisation en nombres entiers - p. 7/83

Exemple : polytope des contraintes012345

0 1 2 3 4 5 6 7 8 9 10

Optimisation en nombres entiers - p. 8/83

Exemple : solution du problème continu012345

0 1 2 3 4 5 6 7 8 9 10

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 9/83

Exemple : contraintes d'intégralité012345

0 1 2 3 4 5 6 7 8 9 10

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 10/83

Exemple : voisins non admissibles012345

0 1 2 3 4 5 6 7 8 9 10

Voisins non admissibles

Solution optimale non entière(9.2,2.4)

Optimisation en nombres entiers - p. 11/83

Exemple : solution du problème discret012345

0 1 2 3 4 5 6 7 8 9 10

Voisins non admissibles

Solution optimale non entière(9.2,2.4)

Solution optimale entière

Optimisation en nombres entiers - p. 12/83

Problèmes

Optimisation en nombres entiers - p. 13/83

Problème d'investissement

Quels barrages doit-elle construire ?

Barrage Coût Bénéfice Rendement

1 500 1600 3.20

2 700 2200 3.14

3 400 1200 3.00

4 300 800 2.67

Optimisation en nombres entiers - p. 14/83

Problème d'investissement

Modélisation :

Variables de décision:x1,x2,x3,x4.

1si le barrageiest choisi,

0sinon.

Contrainte : capacité d'investissement

Optimisation en nombres entiers - p. 15/83

Problème d'investissement

Problème linéaire continu :

1,x2,x3,x4≥0.

Solution optimale :

1= 2.8,x2= 0,x3= 0,x4= 0.

Optimisation en nombres entiers - p. 16/83

Problème d'investissement

Solution optimale :

1= 2.8,x2= 0,x3= 0,x4= 0.

Décision : ne construire que le barrage 1.

Coût : 500 kCHF

Somme non investie : 900 kCHF

Bénéfice : 1600 kCHF

Optimisation en nombres entiers - p. 17/83

Utiliser la voiture ou pas.

Construire un pont ou pas.

Allumer la climatisation ou pas.

Energie :

Ignorer les contraintes d'intégralité.

Résoudre le problème linéaire.

Quels barrages doit-elle construire ?

Variables de décision:x1,x2,x3,x4.

Contrainte : capacité d'investissement

Décision : ne construire que le barrage 1.

Coût : 500 kCHF

Somme non investie : 900 kCHF

Bénéfice : 1600 kCHF

Décision : construire les barrages 1 et 2.

Coût : 1200 kCHF

Somme non investie : 200 kCHF

Bénéfice : 3800 kCHF

Coût : 1400 kCHF

Somme non investie : 0 kCHF

Bénéfice : 4200 kCHF

la solution optimale est fournie,

une "bonne" solution est fournie,

aucune garantie d'optimalité,

aucune mesure de qualité de la solution,

Diviser pour conquérir.

Fest l'ensemble des solutions admissibles.

Soit une partition deF

Soitx?kla solution optimale du problèmePk

Soititel que

Idée : utiliser des bornes.