Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
Cours 2 : Résolution des Programmes Linéaires
1. Récapitulons
La recherche opérationnelle (RO) est un domaine apparu dans les années 1940 dans l’armée
américaine. Cette discipline avait pour objectifs d’effectuer des recherches afin de fournir de
nouvelles méthodes et outils plus performants que celles proposées par les mathématiques
classiques, notamment en termes de temps de calcul sur machines, et ce afin d’être beaucoup
plus opérationnel sur le terrain. L’objectif ultime étant de prendre la meilleure décision très
rapidement. Très vite, cette branche fut utilisée dans le secteur économique où les décideurs
économiques sont soumis à la même contrainte d’efficacité et d’efficience que les décideurs
militaires.
La programmation mathématique est probablement l’une des branches les mieux développées
et la plus exploitée de la recherche opérationnelle (RO). La programmation mathématique
étudie l’allocation optimale des ressources limitées sur des activités concurrentes, sous divers
contraintes dépendant de la nature du problème étudié. Ces contraintes peuvent être d’ordre
financier, technologique, organisationnel, marketing….etc. cette branche est appelée
programmation car elle pour but de planifier une allocation de ressources et donc de fournir
un plan ou programme de production, transport…etc. Si les fonctions utilisées en
programmation mathématiques sont exclusivement linéaires, nous parlons de programmation
linéaire (PL).
Un PL se présente sous la forme suivante :
Fonction Objectif : Max Z = ∑
Contraintes : ∑ ≤ avec j allant de 1 à m.
Les variables de décision : ≥0 1à (appelé contrainte de non-
négativité des variables).
2. Exemple de Formulation en PL
Reprendre l’exercice 4 de la série 1.
Solution :
Dans l’énoncé, on nous parle d’un aliment pour bétail obtenu avec l’orge, l’arachide et le
sésame. Cet aliment à des exigences en termes de contenance de matières grasses et de
protéines. Nous avons les données sur la contenance de l’orge, l’arachide et le sésame en
protéines et matières grasses. Nous avons également le coût unitaire de l’orge, l’arachide et
le sésame. On nous demande de chercher la meilleure composition de l’aliment.
La première chose à identifier est la/les variables de décision. Elles sont facilement
reconnaissables car elles sont sous le contrôle du décideur. Dans cet exercice, le problème
consiste à chercher la meilleure composition de l’aliment. Or, toujours d’après l’énoncé,
l’aliment est composé et obtenu à partir de l’orge, sésame et arachide. Le pourcentage
d’orge, sésame et arachide dans l’aliment sont les seules variables à pouvoir être contrôlé
directement par le décideur. Nous avons donc :
: Le pourcentage d’orge présent dans l’aliment.
: Le pourcentage d’arachide présent dans l’aliment.
1
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
: Le pourcentage de sésame présent dans l’aliment.
Pourquoi le pourcentage en protéine et en matières grasses ne peut être considéré comme
variables de décision ?
Nous n’avons pas la possibilité de fixer la présence des protéines et des matières grasses
directement. Ceci ne peut se faire indirectement qu’à travers la présence dans l’aliment
d’orge, d’arachide et de sésame qui contiennent les protéines et les matières grasses. De plus,
le décideur ne peut choisir les quantités de protéines et de la matière grasse dans l’aliment
librement vu l’existence de contraintes sur la composition de l’aliment. Donc la présence de
protéines et de matières grasses sont considérées comme étant des contraintes.
12 + 52 + 42 ≥ 22 (Contrainte sur le pourcentage de protéines)
2 + 2 + 10 ≥ 3.6 (Contrainte sur le pourcentage de graisses)
≥ 0, ≥ 0, ≥ 0 (Le pourcentage d’orge, arachide et sésame sont positifs)
L’objectif du décideur est de déterminer une composition alimentaire qui respecte les
contraintes ci-dessus et qui soit la meilleure possible. Dans cet énoncé, on nous parle de coût
unitaire de chaque aliment : orge, arachide et sésame. Entre deux composition différentes et
respectant les contraintes ci-dessous, le décideur va choisir la moins coûteuse. L’objectif du
décideur sera donc de minimiser les coûts relatifs à la composition de l’aliment.
La fonction Objectif sera donc : Min(Z)= 25 + 41 + 39
Notre PL sera formulé comme suit :
Min(Z)= 25 + 41 + 39
12 + 52 + 42 ≥ 22
2 + 2 + 10 ≥ 3.6
≥ 0, ≥ 0, ≥ 0
3. Résolution Graphique
La résolution d’un programme linéaire par la méthode graphique exploite la translation d’une
droite sur un espace de solution. L’idée est translater la droite de manière continue jusqu’à ce
la droite chevauche un point optimal. Avant de décrire dans le détail le mécanisme, nous
allons commencer par un petit lexique des termes utilisés :
• Solution d’un PL: Ce sont des valeurs qu’on affecte aux variables de décision et qui
correspondent à une allocation donnée de ressources.
• Solution réalisable : une solution qui respecte toutes les contraintes du problème.
• Domaine réalisable / Espace de solution réalisable: Ensemble de solutions réalisables.
• Solution optimale : solution qui donne la meilleure valeur possible de la fonction
objectif.
• Résolution d’un PL : ce sont les étapes qu’on conduit pour déterminer une solution
optimale et réalisable au PL.
[Link] de la résolution graphique
La résolution graphique est utilisée pour les PLs à deux. Dans ce cours, nous l’appliquerons
pour les PLs à deux variables de décision. Les variables de décision seront représentées
comme des axes : abscisses et ordonnées. Chaque point de ce plan sera considéré comme une
solution potentielle. Les contraintes sont des inéquations. Chaque contrainte sera transformée
en droite et en fonction de l’opérateur de l’inéquation, nous délimiterons l’ensemble des
solutions qui respectent la contrainte. L’intersection des ensembles de solution de chaque
2
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
contrainte formera le domaine réalisable du PL. la fonction objectif sera également modélisée
sous forme de droite. Cette droite sera translatée sur le domaine réalisable jusqu’à obtention
d’une solution optimale. En général, la droite correspondant à la fonction objectif commence
son exploration à partir de la solution initiale (0,0).
Résolution Graphique du PL suivant :
Max(Z)= 3 5
3 2 18
4
2 12
0, 0
Figure 1: Domaine Réalisable du PL
Figure 2: Translation de la fonction objectif
La solution optimale est le point (2.6). Le choix optimal est : % 2, %6
[Link] particulier : Domaine réalisable vide
Ceci matérialise le cas où l’espace de solutions réalisables est vide. Autrement dit, il n’existe
pas de solution réalisable. Les contraintes ne peuvent pas être satisfaites en même temps. Le
décideur est donc face à un problème d’optimisation où il n’y pas de solution.
Soit le PL précédent, nous lui ajoutons une nouvelle contrainte.
Figure 3:Domaine Réalisable Vide
3
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
[Link] particulier : objectif non borné
L’espace de solution réalisable n’est pas borné. Il existe donc une variable de décision qui
peut varier à l’infini. Par conséquent, la fonction objectif peut varier à l’infini.
Nous reprenons le PL précédent. Nous remarquons que la variable de décision ne figure
dans aucune contrainte ci-dessous. Ainsi, elle peut varier à l’infini.
Figure 4: Objectif non borné
[Link] particulier : Infinité de solution optimale
Ceci se produit si la solution optimale est matérialisée par un segment de droite. D’un point de
vue graphique, nous constatons ce cas lorsque la fonction objectif au cours de sa translation se
superpose sur une droite dont les points appartiennent au domaine réalisable.
Figure 5: Infinité de solution optimale
[Link] : Existence d’une solution optimale et réalisable unique
Théorème
Supposons qu’un modèle de PL a un domaine réalisable non vide et borné; alors il existe au
moins une solution optimale correspondant à un point extrême du domaine réalisable.
4
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
4. Algorithme du simplexe
L’algorithme du simplexe a été proposé par George B. Dantzig et ses associés du département
des forces de l’air des Etats Unis d’Amérique en 1947. L’idée du simplexe est d’améliorer
itérativement la valeur de l’objectif en passant d’une solution réalisable à une autre.
L’algorithme du simplexe se termine au bout d’un nombre fini d’itérations.
Le simplexe a été très largement adopté et programmé sur machine pour résoudre différents
types de problèmes. Les avantages du simplexe sont :
Robustesse : cet algorithme est considéré comme étant robuste car :
Il résous n’importe quel programme linéaire.
Il détecte les contraintes redondantes dans la formulation.
Il identifie les cas où l’objectif est non borné.
Il résous les problèmes à une ou plusieurs solutions optimales.
Il s’auto-génère une solution pour démarrer la résolution dans le cas où on n’a
pas de solution initiale et réalisable.
Plus que de fournir une solution optimale, le simplexe évalue comment l’objectif varie
en fonction des données du problème (analyse sensitive et post-optimale).
[Link]érentes formes de PL
Un PL est écrit sous forme canonique si :
Max Z= CX
AX ≤ B
X≥0
Théorème
Tout programme linéaire peut s’écrire sous forme canonique.
Démonstration
Tout PL peut être exprimé sous forme canonique. Le cas échéant, il peut être converti.
a) Cas de minimisation
Toute fonction de minimisation peut être exprimée en maximisation inverse. Supposons que
la fonction objectif Z doit être minimisé. On a min (Z)= - Max(-Z).
b) Cas d’inégalité « ≥ »
On multiplie par (-1).
c) Cas d’équation
L’équation se transforme en deux inégalités ≥ et ≤ et on transforme l’inéquation « ≥ » comme
vu dans (b).
5
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
Un PL est écrit sous forme standard si :
Max Z= CX
AX = B
X≥0
Théorème
Tout programme linéaire peut s’écrire sous forme standard.
Démonstration
Tout PL peut être exprimé sous forme standard. Le cas échéant, il peut être converti.
a) Cas de minimisation
Toute fonction de minimisation peut être exprimée en maximisation inverse. Supposons que
la fonction objectif Z doit être minimisé. On a min (Z)= - Max(-Z).
b) Cas d’inégalité « ≥ »
On retranche une variable d’écart.
c) Cas d’inégalité « ≤»
On ajoute une variable d’écart.
Pour appliquer le simplexe, il faudrait que :
a) Toutes les variables soient positives
b) Les contraintes soient exprimées sous forme d’équation
c) Tous les membres droits des contraintes soient positifs
[Link] de l’algorithme
On désigne par la matrice A l’ensemble des coefficients mesurant le degré de consommation
d’une ressource pour une activité donnée, le vecteur colonne B désigne les limites des
contraintes des ressources, le vecteur ligne C désigne les coefficients des variables de décision
dans la fonction objectif qu’on appelle également vecteur de coût et le vecteur colonne X
désigne l’ensemble des variables de décision.
Pour appliquer l’algorithme du simplexe, il faut que le PL soit sous forme canonique avec une
base réalisable. Les étapes à suivre sont :
i. Choix de la variable à introduire dans la base : on choisit souvent celle dont le
coefficient est le plus élevé dans la fonction objectif.
ii. Choix de la variable qui quitte la base pour déterminer le pivot, on prend l’élément
tel que & soit le minimum des rapports.
iii. Effectuer l’opération de pivotage. Refaire les étapes i,ii et iii jusqu’à ce que tous les
éléments du vecteur C soient négatifs ou nuls.
6
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
rième ligne '(
sième colonne
Rappels sur le pivotage
Le pivotage consiste à déterminer un élément pivot et calculer les nouvelles valeurs de la
matrice à partir de ce pivot. Le nouveau système linéaire obtenu par le pivotage est équivalent
au précédent. Lorsqu’on choisit comme pivot un élément '( , cela aboutit à faire sortir de la
base la rième variable et à introduire la sième variable.
Pour effectuer le pivotage, on procède comme suit :
* '
i. Diviser la ligne du pivot (la rième ligne)par le pivot, c’est-à-dire, ∀ ' , ' = & '(
*
ii. Modifier les éléments des autres lignes comme suit : ∀ , = − ( ∗ ′'
avec (i ≠ r).
iii. Modifier les vecteurs B et C de la même façon que l’étape ii.
[Link] particulier du simplex
L’algorithme du simplexe permet de montrer qu’un PL a une solution et que cette solution est
soit unique, a une infinité de solutions ou que le PL n’est pas borné ou encore qu’il n’admet
pas de solution.
Rappelons qu’un PL admet une solution optimale et réalisable unique si pour toutes les
variables hors base les coefficients sont négatifs.
[Link] d’un optimum infini (également appelé solution non bornée)
On est dans ce cas si pour une variable hors base candidate à entrer dans la base, a toute sa
colonne dans la matrice A négative ou nulle.
[Link] à infinité de solutions
Ceci se produit si l’on trouve une solution optimale et qu’une variable hors base a son
coefficient dans le vecteur C nul.