Aller au contenu

Graphes et Recherche Op´erationnelle

Programmation linéaire cours La programmation linéaire est une méthode utilisée en recherche opérationnelle pour optimiser un objectif sous des contraintes linéaires. Ce cours aborde la modélisation de problèmes, la résolution graphique, et les différentes formes d'un programme linéaire. Des exemples concrets, tels que des problèmes de production, illustrent les concepts clés.

D'après le document Graphes et Recherche Op´erationnelle

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Graphes et Recherche Op´erationnelle

Document source

Graphes et Recherche Op´erationnelle

Programming, Math, Optimization · PDF · 35 pages · 2012

Afficher l'aperçu du document

Consulter le document original →

Programmation linéaire cours

La programmation linéaire est une méthode utilisée en recherche opérationnelle pour optimiser un objectif sous des contraintes linéaires. Ce cours aborde la modélisation de problèmes, la résolution graphique, et les différentes formes d'un programme linéaire. Des exemples concrets, tels que des problèmes de production, illustrent les concepts clés. Les étudiants apprendront également la méthode du simplexe pour résoudre efficacement des problèmes de programmation linéaire.

Modélisation d'un problème de programmation linéaire

En recherche opérationnelle, modéliser un problème consiste à identifier les éléments suivants :

  • Variables intrinsèques : Ce sont les inconnues que l'on cherche à déterminer.
  • Contraintes : Ce sont les limitations auxquelles sont soumises les variables.
  • Objectif : C'est ce que l'on cherche à optimiser, souvent sous forme d'une fonction linéaire.

Par exemple, considérons une usine qui fabrique deux produits, P1 et P2. L'objectif est de maximiser le bénéfice total provenant de la vente de ces produits. Les ressources disponibles (équipement, main-d'œuvre, matières premières) sont limitées, ce qui constitue les contraintes du problème.

Exemple d'un problème de production

Une usine fabrique deux produits P1 et P2, nécessitant des ressources d'équipement, de main-d'œuvre et de matières premières disponibles en quantité limitée :

Ressources P1 P2 Disponibilité
Équipement 3 4 81
Main d'œuvre 2 9 55
Matière première 5 1 20

Les produits rapportent respectivement 6 euros pour P1 et 4 euros pour P2. Nous devons déterminer les quantités de P1 et P2 à produire pour maximiser le bénéfice total.

Fonction objectif et contraintes

La fonction objectif à maximiser est :

F(x1, x2) = 6x1 + 4x2

Les contraintes sont :

  • 3x1 + 9x2 ≤ 81
  • 4x1 + 5x2 ≤ 55
  • 2x1 + x2 ≤ 20
  • x1, x2 ≥ 0

Nous cherchons donc à maximiser F sous ces contraintes.

Résolution graphique de la programmation linéaire

Pour résoudre un problème de programmation linéaire à deux variables, on peut utiliser une méthode graphique. Les contraintes, représentées par des inégalités, correspondent géométriquement à des demi-plans. L'intersection de ces demi-plans forme un polygone convexe, qui représente l'ensemble des solutions réalisables.

Détermination du maximum de F

Pour déterminer le maximum de F, on fait glisser la droite de la fonction objectif (translation parallèle) jusqu'à rencontrer l'ensemble des variables satisfaisant les contraintes. La solution optimale est atteinte en un sommet du polygone convexe des contraintes.

Dans notre exemple, la solution optimale est :

(x1, x2) = (15/2, 5) avec max(F) = 65.

Formes générales d'un programme linéaire

Un programme linéaire peut être exprimé sous plusieurs formes :

Forme canonique mixte

Un programme linéaire sous forme canonique mixte s'écrit :

max (x1, ..., xn)
F(x1, ..., xn) = c1x1 + ... + cnxn
sous les contraintes :
    aij xj ≤ bi (pour i ∈ I1)
    aij xj = bi (pour i ∈ I2)
    xj ≥ 0 (pour j ∈ J1)

Forme canonique pure

Un programme linéaire est dit sous forme canonique pure s'il s'écrit :

max x
F(x) = c^T x
sous les contraintes :
    Ax ≤ b
    x ≥ 0

Forme standard

Un programme linéaire est dit sous forme standard s'il s'écrit :

max x
F(x) = c^T x
sous les contraintes :
    Ax = b
    x ≥ 0

Méthode du simplexe

La méthode du simplexe est une technique efficace pour résoudre des problèmes de programmation linéaire. Elle explore uniquement les sommets qui permettent d'augmenter la fonction objectif, réduisant ainsi le nombre de solutions de base à examiner.

Il existe trois situations possibles lors de l'application de la méthode :

  1. DR = ∅ : le programme linéaire n'a pas de solution.
  2. DR ≠ ∅ mais la fonction objectif F n'est pas majorée : le maximum de F vaut +∞.
  3. DR ≠ ∅ et la fonction objectif F est majorée : le programme linéaire admet une solution optimale.

Solutions de base réalisables

Une solution de base réalisable est un vecteur qui satisfait les contraintes du programme linéaire. Pour un programme sous forme standard, on note :

DR = {x ∈ R^n | Ax = b, x ≥ 0}

Le nombre de solutions de base réalisables est limité, et la méthode du simplexe permet de les explorer efficacement.

Points clés à retenir

  • La programmation linéaire optimise une fonction sous des contraintes linéaires.
  • La méthode graphique permet de visualiser les solutions réalisables.
  • La méthode du simplexe est efficace pour trouver des solutions optimales.

Glossaire des termes clés

  • Programmation linéaire : Méthode d'optimisation sous contraintes linéaires.
  • Fonction objectif : Fonction à maximiser ou minimiser.
  • Contraintes : Limitations imposées aux variables.
  • Solutions de base : Solutions réalisables correspondant aux sommets du polyèdre.

Questions fréquentes

Qu'est-ce que la programmation linéaire ?

La programmation linéaire est une méthode d'optimisation qui permet de maximiser ou minimiser une fonction linéaire sous des contraintes également linéaires.

Comment résoudre un problème de programmation linéaire ?

Un problème de programmation linéaire peut être résolu graphiquement pour deux variables ou par la méthode du simplexe pour des problèmes plus complexes.

Quelles sont les différentes formes d'un programme linéaire ?

Les programmes linéaires peuvent être exprimés sous forme canonique mixte, canonique pure, ou standard, selon la nature des contraintes.

Qu'est-ce qu'une solution de base réalisable ?

Une solution de base réalisable est un vecteur qui satisfait les contraintes d'un programme linéaire, souvent associé à un sommet du polyèdre des solutions réalisables.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions