Scribd
Importer
62 vues2 pages

Exercice 1: Méthode B & B

Le document présente des exercices sur la programmation linéaire en nombres entiers, incluant des problèmes d'optimisation tels que la maximisation ou la minimisation d'objectifs, ainsi que des affectations de chefs de service à des ateliers pour minimiser les coûts. Il aborde également le problème du voyageur de commerce, demandant une modélisation et l'utilisation de méthodes spécifiques pour trouver des solutions optimales. Chaque exercice requiert une analyse des contraintes et des décisions à prendre pour atteindre une solution optimale.

Transféré par

Dhib
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
62 vues2 pages

Exercice 1: Méthode B & B

Le document présente des exercices sur la programmation linéaire en nombres entiers, incluant des problèmes d'optimisation tels que la maximisation ou la minimisation d'objectifs, ainsi que des affectations de chefs de service à des ateliers pour minimiser les coûts. Il aborde également le problème du voyageur de commerce, demandant une modélisation et l'utilisation de méthodes spécifiques pour trouver des solutions optimales. Chaque exercice requiert une analyse des contraintes et des décisions à prendre pour atteindre une solution optimale.

Transféré par

Dhib
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TD2 2024-2025

Méthode B & B 2 G. Indus A/B


TAO Pr. Med DHIB

Exercice 1
Étant donné un certain problème de programmation linéaire en nombre entier avec la branche et l'arbre lié
suivants :

1. Déterminer si l’objectif du problème est de maximiser ou de minimiser.


2. Avons-nous atteint la solution optimale ? Si c'est le cas, expliquer pourquoi, sinon dites à partir de quel
nœud nous devrions créer une branche et avec quelles contraintes.

Exercice 2
Étant donné un certain problème de programmation linéaire en nombres entiers avec l'arbre de
branchement et de liaison suivant :

1. Écrire la contrainte ajoutée à chaque branche.


2. Avons-nous atteint la solution optimale ? Si tel est le cas, expliquer pourquoi, sinon dites à partir de quel
nœud nous devrions créer une branche et avec quelles contraintes.

1
Exercice 3
Les solutions suivantes ont été obtenues dans un problème de programmation linéaire en nombres entiers :

1. Écrire les contraintes qui ont été ajoutées à chaque branche.


2. Déterminer si la solution optimale a été trouvée. Si c'est le cas, dites de quoi il s'agit, sinon dites de quel
problème nous devrions dériver et avec quelles contraintes.

Exercice 4
La société Beta possédant quatre ateliers : fonte, moulage, laminage et traitement thermique, qu’on va
nommer respectivement F, M, L et T, pour lesquels elle veut affecter quatre chef de service polyvalents,
monsieur A, B, C et D.
Atelier \ Chef A B C D
F 60 130 50 120
M 170 200 300 90
L 330 200 170 250
T 360 400 250 200

1. Modéliser ce problème d’affectation, on appelle 𝑐 le coût que réalise l’atelier 𝑖 si il est affecté au chef 𝑗,
sachant qu’un chef est affecté à un atelier et un seul. 𝑥 désigne la variable de décision.
2. Comment organiser l’affectation de façon à minimiser le coût ?
Exercice 5
Considérons le problème du voyageur de commerce (PVC) représenté par le graphe ci-dessous.

1. Modéliser le problème PVC, on appelle dij la distance du sommet i au sommet j.


2. Utiliser une méthode par séparation et évaluation qui détermine la tournée optimale en commençant à
partir du sommet E et avec la contrainte : la visite de la ville B devrait être immédiatement après E.

Vous aimerez peut-être aussi