This linear programming course is a collaborative, open and shared course.
The objective of this course is to present Linear Programming. Activities allow to train modelling practical problems in Linear programming. Various tests help understanding how to solve a linear program, presenting the elements of Simplex algorithm. Then the duality section allows to understand in depth a solution of a linear program and of its dual. The sensitivity analysis section explains how the optimal solution is modified when changing the parameters of the linear program.
Ce cours de programmation dynamique pour la RO est un cours participatif, ouvert et partagé.
- Décrire le Modèle de chemin
- Ecrire la formule de récurrence
- Proposer un algorithme de résolution (itératif)
- Reconstruire la solution optimale obtenue par backtrack
- Programmer l'algorithme et le backtrack
- Connaitre les principaux modèles de résolution pour les problèmes classiques : plus court chemin, Sac-à-dos et extension...
- Connaitre les grands problèmes de RO qui se résolvent avec de la DP : maintenance, ordonnancement sur machine parallèle, gestion de couts fixes...
-
un cours rédigé qui s'appuie sur des vidéo youtube courtes;
-
des exercices avec corrections détaillées;
-
des activités de programmation auto-évaluées (l'étudiant peut lancer les tests prédéfinis) avec estimation expérimentale de la complexité de la fonction proposée par l'étudiant. Cette fonctionnalité permet de différentier non seulement un algorithme pseudo polynomial d'une énumération complète mais aussi d'identifier des heuristiques, par exemple à base de boucles for imbriquées qui permettent juste de passer les tests sans résoudre le problème en général.
-
Modèle de chemin et application au problème du sac-à-dos
-
Exercices résolus de DP en RO
-
Autour du sac-à-dos : sac-à-dos entier, subset sum, rendu de monnaie, équilibrage de charge
-
ordonnancement d'intervalles
-
Maintenance
-
Investissement
-
Exercices résolus de DP en Informatique pour acquérir de l'aisance de modélisation
-
multiplication de matrices
-
Alignement de séquences
-
Activités du programmation
-
Autour du sac-à-dos
-
Découpe
-
Keeping water
-
Hotels
-
Production systems
- Jeu
- Auteur : Nadia Brauner, Université Grenoble-Alpes
- Public : étudiants à partir du niveau L3 Math ou Info
- Prérequis : Algorithmique de base, Théorie des graphes
- Type de contenu : Banque de question
- Objectif : Modélisation, résolution de problème de graphe, gamification
Vous allez pénétrer en Graphistan. Vos connaissances en graphe, en modélisation, en optimisation seront mises à rude épreuve. Sauron, Voldemort et Palpatine guettent le moindre faux pas. Qu’Euler soit avec vous !
Ce cours propose des énigmes liées au graphes. La résolution d’une énigme ouvre des portes vers de nouvelles énigmes. Dans une ambiance moyenâgeuse, vous rencontrerez des chevaliers, des sorciers, des Gobelins, des Simurgh… Le jeu a été illustré par des étudiants et certains d’entre eux ont même créé les énigmes pour votre plaisir. Arriverez-vous à visiter le Graphistan et à en sortir un peu mieux armé sur les graphes ?