วีดีโอ

Bonjour, Le bin-packing peut se voir comme un pb de packing en 1D (il n'y a qu'une dimension: la hauteur) et on peut s'y intéresser effectivement en 2D (packing de rectangles par exemple dans le plan) ou encore en 3D (Parallélépipèdes rectangle ou pavés droit avec des applications typique pour la construction de palettes en transport). Ces problèmes de packing mobilisent souvent des techniques plus avancées et sont vite très complexes à modéliser et résoudre. Cela va donc nettement au delà du contenu de cette vidéo et je ne peux pas les aborder aussi facilement :). Bonne continuation.

Tu ne peux pas avoir x1 = 1,5 car il y a une contrainte de décision (de branchement) indiquant x1 <= 1. Tu dois résoudre le PL originel avec les contraints x2 >=2, x1 <= 1 et x2 <=2 (suis le chemin dans l'arbre de branchement) donc plus simplement x2 =2, x1 <= 1. La solution optimale de la relaxation linéaire est bien (1,2) (avec ces contraintes additionnelles en plus). J'espère que ça t'aide !

Bonjour, Je suis désolé, je ne peux pas vous aider sur ce sujet et je n'ai pas le temps nécessaire pour m'y plonger. J'espère néanmoins que vous trouverez des éléments sur cette chaine pour vous aider à avancer !

Bonjour. Non la capa de l'arc cb dans le graphe résiduel est bien de 4 (car il y a 4 unités de flots circulant sur bc), la capa résiduelle de bc est bien 9-4=5 comme vous le dites mais le chemin emprunte cb (et non bc). On peut faire "revenir" au plus 4 unités de flot. Donc la capa min est bien 4. J'espère que ça vous aide.

@@rechercheoperationnelle8907 ohhh d'accord , Merci

Bonjour, il ne s'agit pas toujours d'un problème de chemin mais la transition du chemin vers le cas plus général est ok une fois le principe de la prog dyn pigé dans le cas du chemin. C'est vraiment un choix pédagogique de se focaliser d'abord sur le cas du chemin et l'équation de Bellman. Il me semble que tu as ici un exemple qui n'est pas un chemin: th-cam.com/video/W0Y02f-BpPo/w-d-xo.html

Bonjour, Merci ! Oui c'est vraiment pas évident, cela relève beaucoup de l'expérience. Il faut avoir cherché soi même et vu pas mal d'exemples pour s'en sortir soi même. J'espère que en trouveras suffisamment sur la chaîne, j'ai fait exprès pas mal de "corrections" pour que les étudiants puissent s'exercer. Bon cours !

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<=1. Compte tenu de la direction de la fonction objectif (la flèche en pointillé) je me rends compte (graphiquement) que le point qui maximise l'objectif sera à l'intersection des deux égalités 2x1 + 3x2 = 9 et x1 = 1 donc cela me donne tout de suite x2 = (9-2)/3 = 7/3. J'espère que ça t'aide !

Tu peux avoir un flot réalisable ayant du flot circulant sur un circuit mais tu obtiens un flot équivalent (de même valeur en sortie de la source ou en entrée du puits) en réduisant d'une unité ce "flot circulaire" puisque les contraintes de conservation et de capacité restent satisfaites. Tu peux réduire le flot circulant sur les circuits de cette façon unité par unité jusqu'à ne plus en avoir (jusqu'à ce que l'un des arcs du circuit tombe à 0 unité de flot) sans changer la valeur du flot total qui circule entre s et t. Si tu pars d'un flot nul partout, l'algorithme ne génère pas du flot sur tels circuits puisqu'il augmente toujours le flot total sur un chemin augmentant atteignant le puits. L'algorithme fonctionne bien en présence de circuits.

Tout à fait d'accord et rassure toi, je n'inflige pas le manège aux étudiants.

@@rechercheoperationnelle8907 Je met le lien de l'article pour ceux qui veulent: wexler.free.fr/library/files/held%20%281963%29%20movement-produced%20stimulation%20in%20the%20development%20of%20visually%20guided%20behavior.pdf

Merci :)

Bonjour. Cette vidéo accompagne un cours dans une école d'ingénieur mais ce n'est pas un cours ouvert à tous, il faut être étudiant dans l'école. Nous avons en revanche un cours "ouvert" de Recherche Opérationnelle sur notre plateforme caseine.org

Bonsoir, La coupe ({s,a,b,c,d},{t}) est réalisable et indique que tout flot à une valeur inférieure à 24. Effectivement cette coupe ne fournit pas le certificat d'optimalité (la preuve) de la valeur 23. Mais elle donne une garantie, une borne supérieure. Oui je pense que les algos de flots max jouent un rôle important en traitement d'images et notamment pour la segmentation mais je ne pas bien ces problèmes, je ne pourrai pas te renseigner davantage.

@@rechercheoperationnelle8907 D'accord, merci pour votre réponse, en tout cas votre vidéo est bien 👍

Merci :)

Bonsoir, Je ne travaille pas avec Zimpl désolé. Bonne année à vous !

Oui je suis d accord qu il faudrait clarifier davantage l obtention de la solution elle même.

Merci ! Bon courage pour vos examens.

Bonsoir, J'ai simplement pris plusieurs exemples. La capacité de toute coupe dont une borne supérieure de tout flot. Si tu trouves une coupe dont la capacité est égale à la valeur d'un flot réalisable, c'est que celui-çi est donc maximum. Pour avoir une méthode pour trouver une telle coupe minimale. Tu peux utiliser le graphe résiduel de la dernière itération de l'algorithme de Ford et Fulkerson. Dans ce dernier graphe, tu marques les sommets atteignables depuis la source s et tu obtiens la partition, la coupe prouvant l'optimalité du flot. Je dois l'expliquer ici: th-cam.com/video/G5H6M3fMVB0/w-d-xo.html J'espère que ça t'aide !

Bon courage pour l'examen !

Bonjour, oui je n'aborde pas l'extraction de la solution elle même dans cette vidéo. En fait, l'algorithme permet d'obtenir l'arborescence des plus courts chemins qui donne tous les PCCs de s vers tout autre sommet. Dans ce cas, on aurait l'arborescence ou "l'arbre orienté": {(s,c), (c,b), (b,e), (b,d)} donc on y trouve le PCC de s vers e: s->c->b->e mais aussi celui de s vers d: s->c->b->d et ainsi de suite. Pour avoir cette arborescence, il suffit de stocker dans une matrice P le prédécesseur de chaque sommet chaque fois qu'une mise à jour est faite. Ainsi quand la valeur phi[i,v] est mise à jour à partir de u, on stocke P[i,v] = u. Et la dernière ligne de cette matrice nous donne la solution (les PCC de s vers TOUT autre sommet): P[4,s] = -; P[4,b] = c; P[4,c] = s; P[4,d] = b; P[4,e] = b

Thanks a mil !

Bonjour Geunette, L'algorithme peut fonctionner à partir de n'importe quel flot réalisable au départ. Ici, pour l'exemple, nous avions mis un flot initial de valeur 19 avec une distribution depuis s en 11 (s->a) et 8 (s->c). Il faut simplement que ce flot soit bien réalisable (conservation à chaque sommet et respect des capacités). C'est tout à fait arbitraire, dans la réalité, le flot initial peut être nul (0 partout) pour démarrer l'algorithme. Mais pour le faire "à la main", c'est assez laborieux de partir de 0... C'est ok ? Cette vidéo là est plus claire je pense: th-cam.com/video/G5H6M3fMVB0/w-d-xo.html Voilà j'espère que cela t'aide et désolé pour le retard de ma réponse. Bon courage, Hadrien

Le problème est défini dans un graphe orienté. Si tu cherches des chemins dans un graphe non orienté, il faut que tu définisses l'orientation. Tu peux par exemple remplacer chaque arête de ton graphe non orienté par deux arcs pour autoriser les deux directions. Ensuite tu peux appliquer l'algorithme. Est ce que cela t'aide ? Bonne journée !

Bonjour Hind, Non v(f) = 17 n'est pas possible. Tu peux le constater en examinant cette coupe S = {s,2,4,5} et T={1,3,t} qui a une capacité de 13. Donc impossible de faire passer plus que 13 unités dans ce graphe. Hadrien

Bonjour Josh, Je ne comprends pas l'astuce en question. En quoi consiste elle précisément et en quoi permet elle de gagner du temps ? Quand tu exécutes l'algorithme à la main, tu peux partir de n'importe quel flot réalisable. L'algorithme peut être initialisé avec un tel flot. Donc si tu veux gagner du temps, tu peux essayer de construire très vite le plus gros flot possible "à la main", par exemple en cherchant juste des chemins qui ont une capa résiduelle positive dans le graphe d'origine et en les saturant de flot. Dès que tu ne voies plus comment augmenter un tel flot intuitivement, tu démarres l'algorithme et tu construits le graphe résiduel. Bon travail !

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.

Ravi de savoir que cela t'aide !