Cours de Recherche opérationnelle (niveau Licence)

Abdelwahed A.

Commandez une rédaction : Cours en Mathématiques sur mesure

Devis en ligne gratuit

Cours Format .pdf

Cours de Recherche opérationnelle (niveau Licence)

Télécharger

Lire un extrait

Lecture
Résumé
Sommaire
Extraits

Résumé du document

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.

(...)

Sommaire

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)

Accédez gratuitement au plan de ce document en vous connectant.

Extraits

[...] 2x1 e1 + = 15 x1 + x2 = 10 2x1 x2 + s3 = 20 x1, x2, e1, 0 Résultats possibles de la phase I : Cas 1 : z1 0 au moins unesi 0 PL non réalisable Cas 2 : z1 = 0 et aucune variable artificielle n‟est une VB. Dans ce cas: on élimine toutes les colonnes du tableau optimal de la phase qui correspondent aux variables artificielles. On introduit la fonction objectif de avec les autres lignes de ce tableau. On met à jour la dernière ligne de telle manière à avoir = 0 pour les VB. d‟où le tableau canonique initial de (PL). [...]

[...] xn a1,e as,e am,n Valeurs des var de base . cB B-1b = e . n Questions : quelle est la variable entrante ? Pour déterminer une nouvelle SBR on choisit de considérer la solution de base réalisable adjacente correspondant à la base et contenant xj / Δj = Max {Δk, k = m+1 n } étant un indice relatif à une variable Hors Base) 1er critère de DANTZIG xj est appelée variable entrante note xe) xj prendra la place d‟une autre variable de base dans la base B. [...]

[...] Le critère de choix de la variable entrante est celle qui correspond au coût réduit le plus négatif Méthode du simplexe à deux phases La méthode simplexe part PL sous la forme canonique. Cela suppose qu‟on peut facilement identifier une SBR initiale. Parfois ce n‟est pas évident de trouver une SBR initiale. Dans ce cas, on applique la méthode du simplexe à deux phases Soit le : Max Z = 4x1 + 3x2 s.c. 2x1 - x2 15 x1 + x2 = 10 2x1 - x2 20 x1, x2 0 La forme standard est : Max z = 4x1 + 3x2 s.c. [...]

[...] Le graphe identique à µ sauf pour la partie µ1 qui est remplacée par µ2, est alors de longueur inférieure à celle de µ ; ce qui contredit l‟hypothèse de départ Hanen Bouchriha et Cherif Sadfi Cours de recherche opérationnelle Problème du plus court chemin Illustration : Soit : La longueur du plus court chemin entre 1 et 5 = min + l25 ; + l35 ; + l45} 3.2 Classification des algorithmes de recherche de PCC Les algorithmes de résolution du problème de recherche du plus court chemin seront différents suivant. les propriétés du graphe : - graphe valué par des longueurs positives. - graphe valué par des longueurs de signes quelconques. - graphe sans circuit. le problème considéré : - recherche du plus court chemin sommet à un autre. - recherche du plus court chemin sommet à tous les autres. [...]

[...] p est la pénalité de reporter une unité de la demande pendant une période. Déterminer le plan d‟approvisionnement à coût minimal Hanen Bouchriha et Cherif Sadfi Cours de recherche opérationnelle Problème du plus court chemin Le problème peut être représenté par un graphe comme suit : S 3 p T p p - X = S t = sommets) Un arc correspond à la décision d‟acheter en la période t. lst = Tout sommet t = est relié à t+1. [...]

pdf