Bonjour, Oui tout à fait, tu peux brancher sur n'importe quelle variable fractionnaire, donc x1 ou x2 sont possibles ici à la racine de l'arbre. Bonne fin d'année !
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, 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)).
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 :) : th-cam.com/video/ec0Lm65Oa-k/w-d-xo.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 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
@@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
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.
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.
@@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.
I hope you managed to get something out of it. I have never found the time to do proper english subtitles, I am not even sure if youtube is generating any automatically. Regards.
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
tres clair merci
Merci infiniment c'est très clair et ça m'a bien aidé pour mon partiel d'optimisation. Bonne continuation.
Merci beaucoup, vous m'avez énormément aidé ! ^^'
Super, c'est le but :) ! Bon courage à toi.
Merci pour l'explication de qualité. Juste une petite question peut-on décider de commencer par brancher sur 9/4 ? Merci encore
Bonjour,
Oui tout à fait, tu peux brancher sur n'importe quelle variable fractionnaire, donc x1 ou x2 sont possibles ici à la racine de l'arbre. Bonne fin d'année !
Très bien expliqué
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
Très clair, merci
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 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, 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 :) : th-cam.com/video/ec0Lm65Oa-k/w-d-xo.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 !
merci
merci infiniment
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" ?
I dont know French but watching
I hope you managed to get something out of it. I have never found the time to do proper english subtitles, I am not even sure if youtube is generating any automatically. Regards.
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