Cours de Recherche opérationnelle (niveau Licence)

Mathématiques | 53 pages | 23-08-2011 | Format : | Note : Non noté |

Résumé

Cours de Recherche opérationnelle niveau Licence : introduction à la programmation linéaire, résolution de programmes linéaires par la méthode du simplexe, etc.

Extrait:

1. Introduction

La programmation mathématique est une technique de la Recherche Opérationnelle (RO). Il est ainsi bon de préciser d'abord, même en peu de mots, ce qu'on entend par la RO. Il s'agit d'une discipline carrefour où se rencontrent aujourd'hui l'économie, les mathématiques et l'informatique. Elle représente une démarche scientifique permettant de prendre rationnellement les bonnes décisions à engager dans une situation donnée. Ce qui revient à construire un « modèle » de la réalité, de déterminer la « décision » permettant d'optimiser (minimiser ou maximiser) une certaine « fonction économique », en présence de « contraintes » multiples.

La programmation mathématique est la technique de la (RO) basée sur des modèles mathématiques. Elle met en jeu : (1) une fonction objectif, (2) des variables de décision à déterminer et (3) des contraintes à respecter. La programmation linéaire constitue la branche de la programmation mathématique pour laquelle toutes les fonctions du modèle (fonction objectif et contraintes) sont linéaires.

2. Exemple de Formulation de Programme Linéaire (PL)

L'entreprise VITRE SAR SA. fabrique des vitres de haute qualité pour portes et fenêtres. L'entreprise souhaite lancer deux nouveaux produits :
- Le produit 1 requiert des ressources dans l'atelier 1 et 3.
- Le produit 2 requiert des ressources dans l'atelier 2 et 3.

Dans l'atelier 1, il s'agit de construire des cadres en aluminium pour portes. Dans l'atelier 2, il s'agit de construire des cadres en bois pour fenêtres. L'assemblage des vitres sur les cadres se fait dans l'atelier 3 (...).

Les deux types de produits sont fabriqués en lots de 20 unités.

Les responsables de cette entreprise se posent aujourd'hui la question suivante : Quel serait le mix de produits 1 et 2 le plus profitable à réaliser dans l'atelier 3 ?

Afin de répondre à cette question, il faut disposer des données suivantes :
- Le nombre d'heures de production disponibles par semaine dans chaque atelier ; ce temps a été déterminé en tenant compte du temps déjà alloué aux autres produits.
- Le nombre d'heures de production nécessaires pour fabriquer un lot de produit donné dans chaque atelier.
- Le profit réalisé par la compagnie pour chaque lot de produit vendu.

(...)

Plan:

Chapitre 1. Introduction à la programmation linéaire

I) Introduction
II) Exemple de Formulation de Programme Linéaire (PL)
III) Définitions
IV) Résolution graphique d'un programme linéaire
V) Notions géométriques relatives aux programmes linéaires

Chapitre 2. Résolution de programmes linéaires par la méthode du simplexe

I) Introduction
II) Concepts liés à la solution recherchée
III) Concepts liés à la solution recherchée
IV) Solution de base
V) Tableau canonique
VI) Méthode du simplexe
VII) Exemple d'application
VIII) Algorithme simplexe (résumé)
IX) Méthode simplexe pour un problème de minimisation
X) Méthode du simplexe à deux phases
XI) Cas particulier

Chapitre 3. Dualité

I) Introduction
II) Interprétation économique de la dualité
III) Règles de détermination du dual à partir d'un programme linéaire
IV) Dualité et condition d'optimalité
V) Comment déterminer la solution du dual à partir du primal ?

Chapitre 4. Définition et concepts de base

I) Introduction
II) Définitions et concepts de base
III) Graphe partiel et sous graphe
IV) Chaîne - cycle - chemin - circuit
V) Matrices associées à un graphe

Chapitre 5. Problème du plus court chemin

I) Introduction
II) Exemples de modélisation par PCC
III) Algorithmes de résolution

Chapitre 6. Problème de planification de projet

I) Définition du problème
II) Le graphe potentiel des tâches
III) Méthode du chemin critique
IV) Méthode PERT (program evaluation and review technique)