Scribd
Importer
64 vues3 pages

Programmation Linéaire

Ce document décrit la programmation linéaire, y compris les variables, la fonction objectif, les contraintes, et les différents types de programmes linéaires. Il fournit également des exemples pour illustrer la résolution graphique d'un problème de programmation linéaire à deux variables.

Transféré par

Douaa Ghazouani
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
64 vues3 pages

Programmation Linéaire

Ce document décrit la programmation linéaire, y compris les variables, la fonction objectif, les contraintes, et les différents types de programmes linéaires. Il fournit également des exemples pour illustrer la résolution graphique d'un problème de programmation linéaire à deux variables.

Transféré par

Douaa Ghazouani
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

PROGRAMMATION LINEAIRE (PL)

1. Modélisation
En Recherche Opérationnelle (RO), modéliser un problème consiste à identifier: les variables
intrinsèques (inconnues) les différentes contraintes auxquelles sont soumises ces variables l’objectif
visé (optimisation). Dans un problème de programmation linéaire (PL) les contraintes et l’objectif
sont des fonctions linéaires des variables. On parle aussi de programme linéaire.

Un programme linéaire est défini par :

Les variables de décision : sont les inconnues à trouver pour apporter une solution au
problème.
Fonction objectif : c’est la fonction qui présente l’objectif à optimiser. C’est une fonction
linéaire des variables de décision.
Les contraintes : sont les empêchements naturels du problème.

On distingue 4 types de programmes linéaires :


PL continu : le cas où les variables de décision sont continues.
PL en nombres entiers : le cas où les variables de décision sont des nombres entiers.
PL linéaire en 0-1 : le cas où les variables de décision valent uniquement 0 et 1 (binaires).
PL mixte : le cas où quelques variables de décision sont continues et les autres sont en
nombres entiers ou binaires.

Exemple 1 :

1
2. Résolution graphique (PL à deux variables)
Les contraintes où apparaissent des inégalités correspondent géométriquement à des demi-plans.
L’intersection de ces demi-plans présente l’ensemble des variables satisfaisant à toutes les
contraintes.

Tracer les droites représentant la fonction objectif, fonction objectif=0 et fonction


objectif=1, pour déterminer le sens de l’évolution de la fonction.
Ensuite, on fait translater la droite représentant la fonction objectif dans le sens qui vient
d’être déterminé.

2
La solution optimale appartient la dernière intersection de la droite de la fonction objectif
avec l’intersection des demi-plans présentant l’ensemble des solutions réalisables.
Pour l’exemple 1 précédent la solution est :

L’optimum = (x1,x2)=(7.5,15).

Exemple2 :
Une entreprise fournit deux types de métaux. Chaque tonne de métal vendue lui rapporte
100 dinars. Une tonne de fer nécessite 2 heures de main d’œuvre, et 1 tonne d’acier
nécessite 3 heures de main d’œuvre. La main d’œuvre est disponible 6h/jour.
Le directeur de l’entreprise sait qu’il ne peut pas vendre plus qu’une tonne et demi d’acier
par jour. De plus, il exige que la quantité de fer fabriquée quotidiennement ne dépasse pas
celle de l’acier de plus que 2 tonnes.
Quelles sont les quantités à produire quotidiennement de chaque type de métal de tel sorte
que le profit soit maximal ?

Vous aimerez peut-être aussi