Extrait du document

> Retrouvez également les cours de mathématiques.

Plan du document :

I. Introduction

II. Historique et évolution de Programmation linéaire

III. Notions de base

     1. Modélisation
     2. Les étapes de modélisation

IV. Les différentes méthodes pour résoudre un problème linéaire

     1. Méthode des facteurs rares
     2. Méthode graphique
     3. Méthode simplexe

V. Développement de méthode graphique

I. Formation et structure

Une partie importante de problèmes de décision que rencontrent les dirigeants dans la pratique sont sans aucun doute les problèmes d’optimisation linéaire ou programmes linéaires.

La résolution d’un problème de la programmation linéaire ne pose incontestablement aucune difficulté car il y a des méthodes pratiques pour le résoudre ,plus cela on peut utiliser des logiciels très efficaces pour la résolution tel que MATLAB , EXCEL SOLVER ,LINDO ,…etc.

II. Historique et évolution de Programmation linéaire

• les premiers mathématiciens qui se sont occupés de problèmes, que l'on ne nommait pas encore à l'époque « programmes linéaires » (P.L.), sont : LAPLACE (1749-1827) et le baron FOURIER.

• le russe KANTOROVITCH en 1939 a imahiné une émthode inspirée des multiplicateurs de LAGRANGE, classiques en mécanique, pour résoudre des « programmes de transport »

• la contribution décisive a été l'invention de l'algorithme du SIMPLEXE, développé à partir de 1947 notamment par G.B. DANTZIG et le mathématicien VON NEUMANN. 

• Au milieu des années 80, l'indien KARMARKAR a proposé une nouvelle méthode créée aux Bell Laboratories qui permettait de résoudre de très gros problème linéaires, par une démarche « intérieure » au polyèdre des solutions admissibles.

Définition de programmation linéaire (PL) : 

Selon William J. BAUMAUL, la programmation linéaire est une technique mathématique d'optimisation (maximisation ou minimisation) de fonction à objectif linéaire sous des contraintes ayant la forme d'inéquations linéaires. Elle vise à sélectionner parmi différentes actions celle qui atteindra le plus probablement l'objectif visé.

Robert DORFMAN et Paul Samuelson, ajoutent que la programmation linéaire est une méthode de détermination du meilleur plan d'action pour réaliser des objectifs donnés dans une situation où les ressources sont limitées. C'est donc une méthode de résolution du problème économique, soit dans le cadre d'une économie globale, soit dans celui du secteur public, soit dans une entreprise particulière .

III. Notions de base

1. Modélisation

La modélisation d’un problème linéaire consiste a identifier:

• les variables 

• les différentes contraites auquelles sont soumises ces variables 

• l'objectif visé (optimisation)

2. Les étapes de modélisation

 ? Cette partie est disponible sur le document à télécharger gratuitement 

IV. Les différentes méthodes pour résoudre un problème linéaire

Il existe plusieurs méthodes pour la résolution d’un problème linéaire .

Dans notre éxposé on va s’interesser juste au trois méthodes tel que:

1. Méthode des facteurs rares

> Définition du facteur rare : 

Un facteur rare est un moyen de production (matiére premiére , main d’oeuvre , heure machine)dans la quelle on est limité .

> Exemple : 

On a une entreprise qui fabrique deux produit A et B a l’aide d’une seul machine .

Alors pour fabriquer A il faut 2H de machine et pour fabriquer B il faut 3 heure .

La machine ne peut tourner plus de 100 heure .

Donc pour choisir entre ces deux produits sous contrainte de capacité, les décideurs doivent privilégier le produit pour lequel la marge par unité de facteur rare est maximale.

2. Méthode graphique

L'utilisation de cette méthode est restreinte aux (PL) ayant un nombre de variables au plus égal à 3.

Il existe 2 façon pour résoudre un PL a partir de la méthode graphique:

> la méthode d'énumération des sommets 

> la méthode des droits parallèles

3. Méthode simplexe

Dans la plupart des problèmes réels, on a plus que deux variables à déterminer. Une procédure algébrique pour résoudre les programmes linéaires avec plus que deux variables. C'est la méthode de simplexe.

Une application de cette procédure à permis de résoudre des programmes avec un peu plus de quelques milliers de variables. Le programme Lindo supporte au plus 200 variables et 100 contraintes.

La mise sous forme standard consiste à introduire des variables supplémentaires(une pour chaque contrainte) de manière a réécrire les inégalités (? ) sous la forme d'égalités. Chacune de ces variables représente le nombre de ressources non utilisés. On les appelle variable d'écart. La forme standard s'écrit donc :

MAX(MIN) Z=10X+20Y  

 ? La suite de cette partie est disponible sur le document à télécharger gratuitement 

V. Développement de méthode graphique

Principe de méthode graphique : 

Le principe de cette méthode se base sur la représentation des données (contraintes+fonction objectif) d'une manière graphiquement. 

 ? La suite de cette partie est disponible sur le document à télécharger gratuitement 

.