Application de l'algorithme de branch and bound (Programmation linéaire en nombres entiers)
Вставка
- Опубліковано 10 вер 2020
- Cette vidéo aborde l'algorithme de Branch and Bound en l'appliquant sur un petit exemple. On y parle de:
- Relaxation linéaire: relâcher les contraintes d'intégralité i.e autoriser les variables à prendre des valeurs fractionnaires
- Résolution graphique de la relaxation linéaire, comment être efficace
- Principe d'élagage de l'arbre s'appuyant sur la relaxation linéaire et la meilleure solution réalisable connue
- Premières intuitions sur la notion de qualité de formulation.
Le branch and bound peut réussir à trouver et prouver la solution optimale, c'est un algorithme exact. Il ne fait pas une exploration explicite toutes les combinaisons possibles des valeurs entières car c'est impossible en pratique mais réalise une exploration implicite de certaines parties de l'arbre. En élaguant un sous-arbre avec la relaxation linéaire, c'est comme si on l'avait exploré sans le faire vraiment, on prouve que le sous-arbre ne peut pas contenir de solutions améliorantes, c'est une exploration implicite (et beaucoup plus rapide...).
À voir après (qualité de formulation): • Qualité de formulation...
Merci infiniment c'est très clair et ça m'a bien aidé pour mon partiel d'optimisation. Bonne continuation.
tres clair merci
Merci beaucoup, vous m'avez énormément aidé ! ^^'
Super, c'est le but :) ! Bon courage à toi.
Très clair, merci
merci
Très bien expliqué
merci infiniment
Bonjour j' ai un question
Vous êtes comment choisir l'équation (1ou2) pour trouver la valeur de xi
Par exemple dans deuxième ligne de arbre où ( x1< 1) tu as remplacer x1 dans l'équation 2 qui vous êtes trouvé la valeur de x2 = 7/3 mais si on a remplacé dans la première équation x2 = 4
Ma question c'est ça vous êtes comment choisir l'équation pour remplacer les valeurs xi pour trouver autre xi est ce que il y a un règle exacte ?
Bonsoir,
J'essaye de résoudre graphiquement le programme linéaire incluant les contraintes de branchement. Dans le cas que tu indiques, on a ajouté x2 >=2 et x1
Bonjour, dites-moi svp comment vous avez fait pour simplifier le sytème PLNE (comment vous avez trouver P2) ?
Bonjour Melissa,
Pour trouver P2 sur ce petit exemple, j'ai calculé l'équation de la droite passant par les deux points extrêmes (0,3) et (3,0): x_1 + x_2 = 3. Comme le point (0,0) est dans la région réalisable, cela donne l'inégalité x_1 + x_2 = 0, x_2>=0, x_1 + x_2
@@rechercheoperationnelle8907 merci beaucoup pour votre retour ☺️
Oui c’est vrai avec votre exemple l’inégalité est simple à trouver, mais quand on a un système avec plusieurs contraintes, ça devient compliqué.. j’ai un exercice avec un système à 3 contraintes et conv(Dom(PLNE)) ressemble à un pentagone avec deux angles droit, donc je trouve que dans ce cas là, c’est plus facile de trouer la solution optimale en appliquant directement le B&B que d’essayer de simplifier le système d’abord
@@melissaammour6816 Oui il faut que tu sois à l'aise pour trouver vite l'équation d'une droite passant par deux points. Je ferai, je pense, une petite vidéo sur la qualité de formulation avec un exemple à deux variables un peu plus compliqué + un vrai problème à n variables et je reviendrai là dessus. Bon courage à toi.
@@rechercheoperationnelle8907 Parfait !! Ce serait très gentil si vous pouviez la publier avant jeudi prochain (le jour de mon examen), je pense que ça pourrait aider beaucoup d’étudiants aussi. Merci encore une fois ☺️
@@melissaammour6816 Voilà une petite vidéo :) : ua-cam.com/video/ec0Lm65Oa-k/v-deo.html
Bon je ne sais pas si cela va t'aider. Elle s'inscrit dans la suite du cours Branch and Bound en tout cas.
Bon courage pour Jeudi !
Bonjour svp la dernière ligne de l'arbre j'ai trouvé x=(1,5 ; 2) et vous avez trouvé x=(1;2) svp expliquez moi comment vous avez fait
Tu ne peux pas avoir x1 = 1,5 car il y a une contrainte de décision (de branchement) indiquant x1 =2, x1
Bonjour,
J'ai une question concernant la détermination des solutions pour l'étape x2>=2.
Quand j'applique le simplexe je trouve x1=1.5 (si je prends la seconde équation) x1=2 (si je prends la première).
Pourquoi prendre la deuxième plutôt que la première puisqu'elle nous donne une valeur entière ?
Bonsoir Emilie, la solution fractionnaire à cette étape est bien (x1=1.5, x2 = 2). Elle n'est pas "entière" et il faut continuer à "brancher" pour arbitrer les valeurs fractionnaires. On ne peut donc que brancher sur x1 ici car c'est la seule variable ayant une valeur fractionnaire.
Si on ajoutait x2=3, on raterait peut-être une solution entière ayant x2 = 2... (une telle solution existe d'ailleurs: (1,2)).
@@rechercheoperationnelle8907 Ah d'accord -, merci
Bonjour, je ne comprends pas pourquoi quand on est dans la branche avec x1>=2 la solution est irréalisable. Pouvez-vous m'expliquer svp?
Bonjour Yayou,
La région réalisable est indiquée en blanc. Dans le cas irréalisable dont tu parles, les contraintes x2 >= 2 puis x1 >= 2 ont été ajoutées. Sur la représentation graphique (dans laquelle on ne voit que x1
@@rechercheoperationnelle8907 Oui j'ai compris merci ! J'ai encore une question : quand au début on prend x2
@@yael6656 Je vois graphiquement que le point que je cherche est à l"intersection de la droite x2=1 et de la première équation du système (PAS la deuxième). Donc je remplace bien x2=1 dans la 1ère équation pour avoir la valeur de x1 correspondante
salut pourquoi tu choisis x2 et non x1 .ca passe aleatoire de choisir la variable dont on se base pour faire notre branch ou quoi ?
On peut prendre n'importe quelle variable fractionnaire pour brancher. L'algorithme reste correct.
En pratique, il y a des heuristiques choisissant les variables qui sont susceptibles de créer un "petit arbre" de recherche, par exemple, celles ayant le plus d'influence sur la relaxation linéaire.
Es que vous pouvez faire une autre vidéo pour le même algorithme pour le problème d'attribution de jobs ????
non ça va être difficile de faire ça ce moment :). Es tu sûre qu'il ne s'agit pas pour toi de faire un modèle PLNE de ce problème plutôt que de le résoudre toi même par branch and bound ? À moins que dans ton exercice précis la valeur de la relaxation linéaire s'obtienne facilement à la main, c'est assez pénible de faire un tel branch and bound à la main.
@@rechercheoperationnelle8907 est ce que je peux vous envoyer l'exercice , sûrement vous y verrez plus clair que moi ?????
@@ferdous.k6664 :) Je suis évidemment curieux de le voir. Mais je ne vais pas t'apporter la réponse quoi qu'il arrive. Je ne veux pas court-circuiter un autre enseignant. J'ignore tout du contexte dans lequel cet exercice est demandé et Il est important que tu te tournes vers ton encadrant de TD ou de cours.
Puis je avoir votre email ??
@@ferdous.k6664 Tu dois l'avoir par la chaîne non ? si tu cliques sur "À propos" ?
Comment il a trouvé z = 51/4
Bonjour Seifou,
J'ai calculé la valeur de l'objectif pour la solution optimale x1=9/4 et x2=3/2. Plus précisément, j'ai remplacé x1 et x2 par les valeurs x1=9/4 et x2=3/2 dans l'expression de la fonction objectif 3*x1 + 4*x2. Cela donne 3*9/4 + 4*3/2 = 51/4