Recherche opérationnelle

Master 2 LT, MPM, MIR

Université du Littoral - Côte d’Opale, Pôle Lamartine
Laurent SMOCH
([email protected])
Septembre 2013

Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville

Université du Littoral, zone universitaire de la Mi-Voix, bâtiment H. Poincarré
50, rue F. Buisson, BP 699, F-62228 Calais cedex
2
Table des matières

0 Introduction générale 1

1 La programmation linéaire - Méthode graphique 7

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Modélisation d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Formule générale d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Méthode graphique : problème à deux inconnues . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Régionnement du plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.2 Les ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Résolution de systèmes d’inéquations - Exemples . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Résolution de programmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.5 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

I
II TABLE DES MATIÈRES
Chapitre 0

Introduction générale

La recherche opérationnelle (aussi appelée “aide à la décision”) peut être définie comme l’ensemble des
méthodes et techniques rationnelles orientées vers la recherche de la meilleure façon d’opérer des choix en
vue d’aboutir au résultat visé ou au meilleur résultat possible.
Elle fait partie des “aides à la décision” dans la mesure où elle propose des modèles conceptuels en vue d’ana-
lyser et de maı̂triser des situations complexes pour permettre aux décideurs de comprendre et d’évaluer les
enjeux et d’arbitrer et/ou de faire les choix les plus efficaces.
Ce domaine fait largement appel au raisonnement mathématique (logique, probabilités, analyse des données)
et à la modélisation des processus. Il est fortement lié à l’ingénierie des systèmes, ainsi qu’au management
du système d’information.

La recherche opérationnelle trouve son origine au début du XXe siècle dans l’étude de la gestion de stock avec
la formule du lot économique (dite formule de Wilson) proposée par Harris en 1913. Mais ce n’est qu’avec la
seconde guerre mondiale que la pratique va s’organiser pour la première fois et acquérir son nom. En 1940,
Patrick Blackett est appelé par l’état-major anglais à diriger la première équipe de recherche opérationnelle,
pour résoudre certains problèmes tels que l’implantation optimale de radars de surveillance ou la gestion
des convois d’approvisionnement. Le qualificatif “opérationnelle” vient du fait que la première application
d’un groupe de travail organisé dans cette discipline avait trait aux opérations militaires.
Après la guerre, les techniques de RO-AD se sont considérablement développées grâce, notamment, à l’ex-
plosion des capacités de calcul des ordinateurs. Les domaines d’application se sont également multipliés.

Citons quelques méthodes :

• Plus court chemin (Shortest path) : En théorie des graphes, l’algorithme de Dijkstra sert à résoudre
le problème du plus court chemin. Il permet par exemple, de déterminer le plus court chemin pour
se rendre d’une ville à une autre connaissant le réseau routier d’une région. Il s’applique à un graphe
connexe dont le poids lié aux arêtes est un réel positif. L’algorithme porte le nom de son inventeur,
l’informaticien néerlandais Edsger Dijkstra et a été publié en 1959.
Exemple 0.0.1 Un “serial traveller” américain recherche le plus court chemin entre Boston et Los
Angeles. On donne dans la carte ci-dessous les différents axes qu’il souhaite emprunter.

Figure 1 – Carte des États-Unis

Quel est le trajet optimal ?

1
2 CHAPITRE 0. INTRODUCTION GÉNÉRALE

• Voyageur de commerce (TSP - Traveling-Salesman Problem) : En partant d’un groupe de villes

données, il consiste à visiter une fois chacune des villes (une seule et unique fois) tout en minimi-
sant la distance de vos déplacements. Ce problème qui paraı̂t à tord élémentaire est effectivement
anodin pour un petit nombre de villes, mais, lorsque vous ajoutez d’autres villes, le nombre de che-
mins possibles crève le plafond. Il ne faut donc pas s’étonner si le problème du voyageur de commerce
est classé dans la catégorie des problèmes NP-complets. Dans ce problème, le nombre de chemins
hamiltoniens est égal à n!/2 où n correspond au nombre de villes qui composent le problème. Une so-
lution générale efficiente n’a pas encore été découverte. Les mathématiciens ont conclu que le meilleur
moyen était d’utiliser un algorithme avec des polynômes variant en rapport avec le nombre de villes.
À l’heure actuelle, la meilleure solution varie de façon exponentielle en fonction du nombre de villes.
Exemple 0.0.2 Un voyageur de commerce, basé à Toulon, doit visiter ses clients à travers la France :

Figure 2 – Localisation géographique des clients

Quelle tournée le voyageur de commerce doit-il effectuer afin qu’elle soit la plus courte possible ?

• Mariages stables (Stable Marriage problem) : On se donne deux ensembles A et B ayant chacun n
éléments. On se donne aussi, pour chaque élément de A et B, une fonction de préférence, qui classe
les éléments de l’autre ensemble. On cherche alors à associer de façon bijective les éléments de A avec
ceux de B, pour qu’il n’existe pas a ∈ A et b ∈ B tels que a préfère b à l’élément qui lui est associé,
et b préfère a à l’élément qui lui est associé.
Exemple 0.0.3 On considère 3 femmes (Alice, Bénédicte et Camille) et 3 hommes (Dominique, Elie
et François) dont voici les préférences respectives :

Préférences des femmes Préférences des hommes

A: F D E D: A B C
B: E D F E: B C A
C: F D E F: A C B

Table 1 – Préférences des femmes et des hommes

Comment doit-on organiser les couples ?

• L’optimisation des flux et l’algorithme de Ford-Fulkerson : L’algorithme de Ford-Fulkerson, du nom de

ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer
un flot (ou flux) de valeur maximale (ou minimale) à partir d’un flot constaté. Ce problème d’op-
timisation peut être représenté par un graphe comportant une entrée (à gauche) et une sortie (à
droite). Le flot représente la circulation de l’entrée vers la sortie d’où l’utilisation de cet algorithme
dans les problèmes de réseaux. Les applications sont multiples : problèmes informatiques, routiers,
ferroviaires, . . . . Il s’applique également à tous les autres problèmes de transferts comme les importa-
tions/exportations, les flux migratoires, démographiques mais aussi sur les flux plus abstraits tels que
 3

les transferts financiers.

Exemple 0.0.4 Avant d’établir un projet de construction d’autoroute on désire étudier la capacité
du réseau autoroutier, représenté par le graphe suivant. On y a évalué le nombre maximal de véhicules
que chaque route peut écouler par heure, compte tenu des ralentissements aux traversées des villes
et villages, des arrêts aux feux,. . . Ces évaluations sont indiquées en centaines de véhicules par heure
sur les arcs du graphe (nombres entre crochets). Les temps de parcours entre villes sont tels que les
automobilistes n’emprunteront que les chemins représentés par le graphe.

Figure 3 – Réseau autoroutier et capacités

Quel est le débit horaire total maximum de véhicules susceptibles de s’écouler entre les villes E et S ?

• L’ordonnancement et la gestion de projets : De nombreux travaux traitent de l’ordonnancement et

de la gestion de projets, mais aussi de logistique (tournées de véhicules, conditionnement. . . ), de
planification, et de problèmes d’emploi du temps.
– La gestion de projet est une démarche visant à organiser de bout en bout le bon déroulement d’un
projet. Lorsque la gestion de projet porte sur un ensemble de projets concourant à un même objectif,
on parle de gestion de programme.
– La théorie de l’ordonnancement est une branche de la recherche opérationnelle qui s’intéresse au
calcul de dates d’exécution optimales de tâches. Pour cela, il est très souvent nécessaire d’affecter en
même temps les ressources nécessaires à l’exécution de ces tâches. Un problème d’ordonnancement
peut être considéré comme un sous-problème de planification dans lequel il s’agit de décider de
l’exécution opérationnelle des tâches planifiées. Les méthodes couramment utilisées pour ordonnan-
cer un projet sont les méthodes MPM et PERT.
Exemple 0.0.5 La société SGTB (Société des Grands Travaux de la Bièvre) a reçu la maı̂trise
d’œuvre de la construction d’une piscine olympique sur un campus universitaire. Le tableau des
antériorités des tâches est le suivant :

Codes Tâches Antériorités Durée (en jours) Suivants

A Excavation – 5 B,F
B Fondation A 2 C
C Pose de canalisations B 4 D
D Essais en pression C,G 8 E
E Etanchéité D 9 J

Table 2 – Tableau des tâches et antériorités (Partie 1)

4 CHAPITRE 0. INTRODUCTION GÉNÉRALE

Codes Tâches Antériorités Durée (en jours) Suivants

F Mise en place de la station d’épuration A 6 G

G Mise en place du chauffage F 5 D,H
H Raccordement électrique G 4 I
I Sonorisation sous-marine H 5 J
J Dallage E,I 6 K,L
K Construction des vestiaires J 8 M
L Construction du solarium J 2 M
M Mise en eau K,L 3 –

Table 3 – Tableau des tâches et antériorités (Partie 2)

Les travaux débutent le 1er avril. Chaque mois comporte 20 jours ouvrables. L’inauguration peut-elle
avoir lieu comme prévu le 15 juin ?

Beaucoup d’autres problèmes de recherche opérationnelle peuvent être exprimés comme des problèmes
d’optimisation linéaire. En optimisation, qui est une branche des mathématiques, un problème d’optimisation
linéaire est un problème d’optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe.
La fonction-coût et les contraintes peuvent donc être décrites par des fonctions linéaires (on devrait dire
affines), d’où vient le nom donné à ces problèmes. Ceux-ci ne sont cependant pas linéaires dans le sens
où leurs solutions dépendraient linéairement de certaines données ; une non-linéarité importante est en effet
induite par la présence des inégalités définissant les contraintes (en l’absence d’inégalités, le problème devient
linéaire dans ce sens, mais est alors trivial : soit il n’y a pas de solution, soit tous les points admissibles sont
solutions). L’optimisation linéaire (OL) est la discipline qui étudie ces problèmes.
Parmi les problèmes d’optimisation avec contraintes d’inégalités, les problèmes linéaires sont simples à
résoudre numériquement. On connaı̂t en effet des algorithmes polynomiaux efficaces, requérant donc un
nombre d’itérations qui est majoré par un polynôme, fonction des dimensions du problème.
Dans certains problèmes d’OL, on requiert en plus que les variables ne prennent que des valeurs entières
(contraintes dites d’intégrité), voire que les valeurs 0 ou 1. On parle alors de problème d’optimisation linéaire
en nombres entiers (OLNE). Ces derniers problèmes sont beaucoup plus difficiles à résoudre que les problèmes
d’OL à variables continues.

Dans la première partie du cours, nous nous concentrerons sur les problèmes linéaires, c’est-à-dire les
problèmes où la fonction objectif et les contraintes sont purement linéaires. Lorsqu’il n’y a que deux variables
de décision, un problème linéaire peut être résolu de manière purement graphique. C’est ce que nous verrons
dans le chapitre 1. Lorsqu’il y a un plus grand nombre de variables, un algorithme mis en œuvre sous la
forme d’un programme informatique s’avère nécessaire. Il s’agit de l’algorithme du simplexe que nous verrons
au chapitre 2 sous forme algébrique. Le chapitre 3 est dédié à la traduction matricielle de la méthode du
simplexe. Au chapitre 4, nous examinerons une question très importante : à savoir la sensibilité de la solution
à des modifications de données. On parle d’analyse post-optimale.
L’objet de la deuxième partie du cours porte sur les problèmes en nombres entiers. On devrait à proprement
parler de problèmes linéaires en nombres entiers car on impose, en plus, aux contraintes et à la fonction
objectif d’être linéaires. Nous examinerons la question de la formulation de tels problèmes au chapitre 5
tandis que nous verrons au chapitre 6 une technique de résolution de ces problèmes : il s’agit de la méthode
de branch and bound.
Lorsque les contraintes et/ou la fonction objectif sont non linéaires, on parle de problèmes non linéaires.
C’est l’objet de la troisième partie du cours. Nous verrons au chapitre 7 la formulation et les conditions
 5

d’optimalité d’un problème non linéaire tandis quelques méthodes de résolution de ces problèmes seront
présentées au chapitre 8. Il est à remarquer que toutes ces méthodes de résolution étant mises en œuvre
dans des logiciels commerciaux, il ne viendrait plus à l’idée de les programmer soi-même. Par exemple, le
solveur d’Excel dispose d’une implémentation de ces algorithmes.
6 CHAPITRE 0. INTRODUCTION GÉNÉRALE
Chapitre 1

La programmation linéaire - Méthode

graphique

1.1 Introduction
La programmation mathématique recouvre un ensemble de techniques d’optimisation sous contraintes
qui permettent de déterminer dans quelles conditions on peut rendre maximum ou minimum une fonction
objectif Z(Xj ) de n variables Xj liées par m relations ou contraintes Hi (Xj ) ≤ 0.
De nombreux problèmes de l’entreprise peuvent s’exprimer en termes d’optimisation contrainte, aussi ren-
contre t-on de multiples applications de la programmation mathématique et ceci dans pratiquement tous les
domaines de la gestion.
La gestion de production est le domaine où ces applications sont les plus nombreuses. On citera entre-autres :
– l’élaboration de plans de production et de stockage,
– le choix de techniques de production,
– l’affectation de moyens de production,
– la détermination de la composition de produits.
Les applications sont également nombreuses dans le domaine du marketing avec, en particulier :
– le choix de plans-média,
– la détermination de politiques de prix,
– la répartition des efforts de la force de vente,
– la sélection des caractéristiques du produit.
On citera encore des applications en matière financière (choix de programmes d’investissements), en matière
logistique (gestion des transports) et en matière de gestion des ressources humaines (affectation de person-
nel).
Si les applications de la programmation mathématique sont aussi nombreuses, on doit l’attribuer en grande
partie à la souplesse de ses techniques en ce qui concerne leur formulation mais aussi à la relative simplicité
des méthodes de résolution utilisables dans les cas les plus courants et pour lesquelles existent des pro-
grammes informatiques largement répandus.

Parmi les techniques de programmation mathématique la programmation linéaire est la plus classique.

1.2 Modélisation d’un programme linéaire

La formalisation d’un programme est une tâche délicate mais essentielle car elle conditionne la découverte
ultérieure de la bonne solution. Elle comporte les mêmes phases quelles que soient les techniques requises
ultérieurement pour le traitement (programmation linéaire ou programmation non linéaire) :
1. La détection du problème et l’identification des variables. Ces variables doivent correspondre exacte-
ment aux préoccupations du responsable de la décision. En programmation mathématique, les variables
sont des variables décisionnelles.
2. La formulation de la fonction économique (ou fonction objectif) traduisant les préférences du décideur
exprimées sous la forme d’une fonction des variables identifiées.

7
8 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

3. La formulation des contraintes. Il est bien rare qu’un responsable dispose de toute liberté d’action. Le
plus souvent il existe des limites à ne pas dépasser qui revêtent la forme d’équations ou d’inéquations
mathématiques.

Le responsable d’une décision ne dispose que de sa compétence pour réaliser une formalisation correcte
du problème posé car il n’existe pas de méthode en la matière. Un moyen d’acquérir cette compétence est
l’apprentissage comme proposé dans les exemples suivants :

1.2.1 Exemples

Exemple 1.2.1 Une usine fabrique deux produits P1 et P2 à l’aide de trois matières premières M1 , M2
et M3 dont on dispose en quantité limitée. On se pose le problème de l’utilisation optimale de ce stock de
matières premières c’est-à-dire la détermination d’un schéma, d’un programme de fabrication tel que :
– les contraintes de ressources en matières premières soient respectées,
– le bénéfice réalisé par la vente de la production soit maximum.

Modèle mathématique :
– Données numériques des contraintes. La disponibilité en matières premières est de 18 unités de M1 , 8
unités de M2 et 14 unités de M3 .
– Caractéristiques de fabrication. Elles sont données dans le tableau ci-dessous :
M1 M2 M3
P1 1 1 2
P2 3 1 1

– Hypothèses de linéarité du modèle. La fabrication est à rendement constant, c’est-à-dire que pour
fabriquer x1 unités de P1 , il faut 1 × x1 unités de M1 , 1 × x1 unités de M2 et 2 × x1 unités de M3 , de
même pour la fabrication de x2 unités de P2 .
– Linéarité de la fonction économique. On suppose que le bénéfice peut s’exprimer à l’aide des bénéfices
unitaires c1 , c2 sous la forme :
Z(x1 , x2 ) = c1 x1 + c2 x2

– Réalisation d’un schéma de production. Un schéma de production est un couple (x1 , x2 ), x1 et x2

désignant respectivement les quantités de P1 et P2 fabriquées donc vendues, qui doit vérifier les
contraintes x1 ≥ 0, x2 ≥ 0. Deux questions se posent : un tel schéma est-il réalisable ? A-t-on suffi-
samment de matières premières pour assurer une telle production ?
– Le programme linéaire : 

 x1 ≥ 0, x2 ≥ 0


 x1 + 3x2 ≤ 18
x1 + x2 ≤ 8



 2x1 + x2 ≤ 14

Z(x1 , x2 ) = c1 x1 + c2 x2
où Z est une fonction économique ou fonction objectif qu’il faut maximiser.

Exemple 1.2.2 L’intendant d’un lycée doit composer un menu qui doit contenir un minimum d’éléments
nutritifs et qui doit être le moins coûteux possible. On se limite à une situation simple, deux denrées ali-
mentaires principales D1 , D2 et trois éléments nutritifs, les vitamines V, les calories C et les protéines P.

Le tableau suivant indique le nombre d’éléments nutritifs par unité d’aliment :

1.2. MODÉLISATION D’UN PROGRAMME LINÉAIRE 9

V C P
D1 1 1 3
D2 5 2 2

Une unité de D1 contient 1 unité de V, 1 unité de C et 3 unités de P.

Modèle mathématique :

– Contraintes diététiques. Le menu doit comporter au minimum 5 unités de V, 4 unités de C, 6 unités

de P. Les coûts unitaires sont 20 pour D1 , 25 pour D2 .

– Réalisation du menu. Un menu contenant x1 unités de D1 , x2 unités de D2 est réalisable si le couple

(x1 , x2 ) vérifie :


 x1 ≥ 0, x2 ≥ 0

x1 + 5x2 ≥ 5

 x + 2x2 ≥ 4
 1
3x1 + x2 ≥ 6
– Le programme linéaire. Le problème consiste à déterminer deux nombres x1 et x2 tels que :


 x1 ≥ 0, x2 ≥ 0


 x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4



 3x1 + x2 ≥ 6

Z(x1 , x2 ) = 20x1 + 25x2
où Z est la fonction objectif à minimiser.

1.2.2 Formule générale d’un programme linéaire

De façon générale, un problème de programmation mathématique met en jeu quatre catégories d’éléments :
– des variables ou activités,
– des coefficients économiques,
– des ressources,
– des coefficients techniques.
Les activités sont les variables de décision du problème étudié. Il s’agit pour l’entreprise de sélectionner le
meilleur programme d’activités X = (x1 , . . . , xn ), c’est-à-dire celui qui est le plus conforme à ses objectifs.
Les coefficients économiques mesurent le degré de réalisation de l’objectif de l’entreprise, associé à une
valeur unitaire de chacune des variables. À chaque variable xj est ainsi associé un coefficient économique cj .
L’évaluation des coefficients cj dépend du type d’objectif poursuivi : selon le cas ce sera un prix de vente,
une marge brute, un coût variable unitaire, etc.
Les ressources peuvent être également de nature très diverse selon le problème rencontré. Dans tous les
cas, ce sont les éléments qui limitent le calcul économique de l’entreprise : des capacités de production
limitées, des normes à respecter, des potentiels de vente, etc. Dans tout problème, il faudra ainsi prendre en
considèration un vecteur de ressources B = (b1 , . . . , bm ) donné.
Par coefficient technique on désignera le degré de consommation d’une ressource par une activité. À la
ressource i et à l’activité j correspondra le coefficient technique aij . Dans la mesure où le problème étudié
met en jeu n activités et m ressources, il faudra considérer m × n coefficients techniques que l’on pourra
regrouper dans un tableau du type suivant :
10 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

```
```
```Activités 1 ... j ... n
Ressources ```
``
1 a11 ... a1j ... a1n
.. .. .. .. .. ..
. . . . . .
i ai1 ... aij ... ain
.. .. .. .. ..
. . . . . ...
m am1 ... amj ... amn

Si les variables sont continues, si les coefficients économiques et techniques sont indépendants des valeurs
des variables, alors le problème peut être formalisé à l’aide d’un programme linéaire.
Un même programme peut être traduit sous une forme canonique ou sous une forme standard ; l’une et
l’autre pouvant adopter soit la notation algébrique classique soit la notation matricielle que l’on ne traitera
pas ici.

Voyons tout d’abord la forme canonique. Elle se caractérise par des contraintes présentées sous la forme
d’inéquations telles que


 x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0



 a11 x1 + a12 x2 + . . . + a1n xn ≤ ou ≥ ou = b1


 ..
.

 ai1 x1 + ai2 x2 + . . . + ain xn ≤ ou ≥ ou = bi



 ..

 .

am1 x1 + am2 x2 + . . . + amn xn ≤ ou ≥ ou = bm
(1.1)

et par une forme linéaire

Z(x1 , x2 , . . . , xn ) = c1 x1 + c2 x2 + . . . + cn xn
(1.2)
Résoudre le programme linéaire consiste à déterminer les n-uplets (x1 , x2 , . . . , xn ) qui optimisent Z (maxi-
misent ou minimisent) Z ou à montrer que de tels n-uplets n’existent pas.

On se donne les définitions suivantes :

Définition 1.2.1
– On appelle solution réalisable tout n-uplet (x1 , x2 , . . . , xn ) vérifiant le système d’inéquations précédent.
– On appelle solution optimale toute solution réalisable qui optimise Z.
– On appelle fonction objectif la forme linéaire
Z(x1 , x2 , . . . , xn ) = c1 x1 + c2 x2 + . . . + cn xn
– L’ensemble des solutions réalisables du programme linéaire P est appelé domaine des solutions
réalisables. Lorsque ce domaine est non vide, on dit que P est réalisable.

Résoudre un programme linéaire consiste à déterminer les valeurs des variables qui permettent d’optimiser
la fonction économique.
Il existe diverses techniques de résolution parmi lesquelles la méthode graphique se montre à l’évidence
la plus rapide et la plus simple mais aussi la plus limitée, car dès lors que le nombre de variables ou de
contraintes dépasse 2, elle devient impraticable. C’est pourquoi divers chercheurs se sont efforcés de mettre
au point une méthode de calcul algorithmique qui permet de détecter la solution optimale (si elle existe)
quel que soit le nombre des variables et des contraintes.
Bien que très efficace, cette méthode connue sous le nom d’algorithme du simplexe, exige des calculs longs
et fastidieux. C’est pourquoi ceux-ci sont de plus en plus confiés à l’outil informatique. Dès lors une question
se pose : puisque les logiciels correspondants sont largement répandus, est-il nécessaire pour appliquer la
méthode, d’en connaı̂tre les ressorts ? Deux raisons essentielles justifient une réponse affirmative :
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 11

– d’abord, la compréhension des principes de résolution est une aide précieuse pour, en amont, analyser
et formaliser le problème et pour, en aval, interpréter et exploiter la solution obtenue ;
– ensuite parce que la démarche algorithmique présente en elle-même un intérêt formateur non négligeable.

1.3 Méthode graphique : problème à deux inconnues

1.3.1 Régionnement du plan

Le régionnement du plan revient à étudier le signe de ax + by + c avec (a, b) ̸= (0, 0).

Si on considère la droite D dont une équation est ax + by + c = 0 avec a ̸= 0 ou b ̸= 0, cette droite

partage le plan en deux demi-plans (I) et (II) de frontière D :

– Pour tout point M (x, y) situé sur D, on a ax + by + c = 0 .

– Pour tous les points M (x, y) situés dans le demi-plan (I), ax+by+c a le même signe et si ax+by+c > 0
(respectivement < 0) alors tous les points N (x, y) situés dans le demi-plan (II) vérifient ax+by +c < 0
(respectivement > 0).

Exemple 1.3.1

– Signe de x + y − 1 :

On trace la droite d’équation x + y − 1 = 0. À l’origine, x + y − 1 = (0) + (0) − 1 = −1 < 0 donc pour

tous les points M (x, y) situés dans le demi-plan (II), x + y − 1 < 0 et pour tous les points N (x, y)
situés dans le demi-plan (I), x + y − 1 > 0. Pour les points P (x, y) de la droite D, x + y − 1 prend la
valeur 0.

– Signe de −x + y :
On trace la droite D d’équation −x + y = 0, cette droite contient l’origine du repère. Pour le point
A(1, 0), x − y = 1 > 0 donc pour tous les points M (x, y) situés dans le demi-plan (I), x − y > 0 et
pour tous les points N (x, y) situés dans le demi-plan (II), x − y < 0. Pour les points P (x, y) de la
droie D, x − y prend la valeur 0.
12 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

1.3.2 Les ensembles convexes

Définition 1.3.1 Un ensemble E est dit convexe si pour M1 et M2 deux points quelconques de E, tous les
points du segment [M1 , M2 ] appartiennent à E.

Exemple 1.3.2
• Le disque est un ensemble convexe :

• Le rectangle est un ensemble convexe :

• Le cercle n’est pas un ensemble convexe : les points du segment ]M1 , M2 [ n’appartiennent pas au cercle.

• Cet ensemble n’est pas convexe.

1.3.3 Résolution de systèmes d’inéquations - Exemples

Exemple 1.3.3 On considère le système suivant :


 x1 ≥ 0, x2 ≥ 0

−x1 − x2 ≤ −1

 x + 4x2 ≤ 2
 1
6x1 + x2 ≤ 2

Comme x1 ≥ 0 et x2 ≥ 0, les points M (x1 , x2 ) seront choisis dans le quart du plan :

1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 13

L’ensemble des solutions est représenté par la surface grise.

On considère ensuite le système partiel
{
x1 ≥ 0, x2 ≥ 0
x1 + 4x2 ≤ 2

On trace la droite D1 d’équation x1 + 4x2 = 2. Comment déterminer le demi-plan qui convient ? Il suffit de
prendre un point quelconque du plan et d’observer si ses coordonnées vérifient l’inéquation. Si c’est le cas,
le point se situe dans le bon demi-plan. Considérons par exemple l’origine, x1 + 4x2 = 0 + 4 × 0 = 0 ≤ 2
donc l’origine est solution et tous les points situés dans le demi-plan contenant l’origine sont solutions.

On considère ensuite le système


 x1 ≥ 0, x2 ≥ 0
x1 + 4x2 ≤ 2

−x1 − x2 ≤ −1

On trace la droite D2 d’équation −x1 − x2 = −1. Considérons l’origine, −x1 − x2 = 0 − 0 = 0 > −1 donc
l’origine n’est pas solution, les solutions
( du
) système sont par conséquent les points du triangle ABC et son
2 1
intérieur avec A(1, 0), B(2, 0) et C , .
3 3

On considère enfin le système de départ



 x1 ≥ 0, x2 ≥ 0

x1 + 4x2 ≤ 2

 −x1 − x2 ≤ −1

6x1 + x2 ≤ 2
14 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

On trace la droite D3 d’équation 6x1 + x2 = 2. Considérons le point origine, 6x1 + x2 = 6 × 0 + 0 = 0 < 2

donc l’origine est solution de l’inéquation. On sélectionne le demi-plan qui convient et on observe finalement
que le système n’admet pas de solution (la partie grise est inexistante).

Exemple 1.3.4 On considère le système suivant :


 x1 ≥ 0, x2 ≥ 0
x1 + x2 ≤ 1

−3x1 + x2 ≤ −3

On sélectionne l’intersection des deux demi-plans x1 ≥ 0 et x2 ≥ 0.

On considère la droite d’équation D1 : x1 + x2 = 1. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.

On considère la droite d’équation D2 : −3x1 + x2 = −3. Le demi-plan qui convient est repéré une fois de
plus grâce à l’origine. L’ensemble solution se restreint à un seul point, le couple solution (1, 0).
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 15

Exemple 1.3.5 On considère le système suivant :



 x1 ≥ 0, x2 ≥ 0

x1 + 5x2 ≥ 5
 x1 + 2x2 ≥ 4


3x1 + 2x2 ≥ 6

Comme x1 ≥ 0 et x2 ≥ 0, les points M (x1 , x2 ) seront choisis dans le quart du plan :

On considère la droite d’équation D1 : x1 +5x2 = 5. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.

On considère la droite d’équation D2 : x1 +2x2 = 4. Le demi-plan qui convient est repéré grâce, par exemple,
à l’origine.

On considère la droite d’équation D3 : 3x1 + 2x2 = 6. Le demi-plan qui convient est repéré grâce, par
exemple, à l’origine.
16 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

Exemple 1.3.6 On considère le système suivant :



 x1 ≥ 0, x2 ≥ 0

x1 + 3x2 ≤ 18

 x + x2 ≤ 8
 1
2x1 + x2 ≤ 14
Soient les droites d’équations respectives
D1 : x1 + 3x2 = 18, D2 : x1 + x2 = 8 et D3 : 2x1 + x2 = 14.
L’ensemble solution est un polyèdre convexe limité par la ligne polygonale OABCD.

1.3.4 Résolution de programmes linéaires

Exemple 1.3.7 On reprend le système de l’exemple 1.3.4 auquel on ajoute une fonction objectif :


 x1 ≥ 0, x2 ≥ 0

−3x1 + x2 ≤ −3

 x + x2 ≤ 1
 1
Z(x1 , x2 ) = 3x1 + x2 à maximiser
On rappelle que le domaine des solutions réalisables est donné graphiquement par :

Le programme linéaire admet une unique solution réalisable (1, 0) qui est d’ailleurs la solution optimale. Z
est maximum pour le couple (1, 0) et vaut Z(1, 0) = 3 × 1 + 0 = 3.

Exemple 1.3.8 On reprend le système de l’exemple 1.3.3 auquel on ajoute une fonction objectif :


 x1 ≥ 0, x2 ≥ 0


 x1 + 4x2 ≤ 2
−x1 − x2 ≤ −1



 6x1 + x2 ≤ 2

Z(x1 , x2 ) = 6x1 + x2 à maximiser
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 17

L’ensemble solution est donné graphiquement par :

Ce programme n’a pas de solution réalisable. Le domaine des solutions réalisables est le vide.

Exemple 1.3.9 On reprend le système de l’exemple 1.3.6 auquel on ajoute une fonction objectif :


 x1 ≥ 0, x2 ≥ 0


 x1 + 3x2 ≤ 18
x1 + x2 ≤ 8



 2x1 + x2 ≤ 14

Z(x1 , x2 ) = 2x1 + 4x2 à maximiser

Le domaine des solutions réalisables est donné graphiquement par :

Le domaine des solutions réalisables est un domaine plan, délimité par le polygone OABCD. Le domaine
plan est un ensemble convexe.

On détermine ensuite les couples (x1 , x2 ) de solutions réalisables tels que Z(x1 , x2 ) = 2x1 + 4x2 soit maxi-
mum. Pour tout nombre Z, on note DZ la droite d’équation

Z = 2x1 + 4x2

appelée
( généralement
) ( droite
) d’isovaleur de la fonction objectif. Un vecteur directeur de cette droite DZ est
−4 −2 1 1 Z
⃗v ou w ⃗ . Son coefficient directeur est − . En effet, x2 = − x1 + . Lorsque Z varie, ces
2 1 2 2 4
droites DZ ayant même coefficient directeur sont parallèles entre elles. L’ordonnée à l’origine des droites DZ
Z Z
est . Maximiser Z est équivalent à maximiser . Le problème consiste donc à déterminer une ou plusieurs
4 4
droites DZ qui rencontrent le domaine des solutions réalisables et ayant une ordonnée à l’origine maximale.
Lorsque Z augmente, la droite DZ se déplace parallèlement à elle même vers le haut :
18 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

La droite DZ qui rencontre le domaine des solutions réalisables et qui a une ordonnée à l’origine maximale
est celle qui contient le point C.
Le programme linéaire a une seule solution maximale, le couple (3, 5).
En conclusion, pour x1 = 3, x2 = 5, la fonction objectif est maximale et vaut
Z(3, 5) = 2 × 3 + 4 × 5 = 26.

Remarque 1.3.1 La fonction objectif atteint son maximum en un des sommets du polygone.

Exemple 1.3.10 On considère le système



 x1 ≥ 0, x2 ≥ 0

x1 + x2 ≥ 2

 2x1 + x2 ≥ 3

Z(x1 , x2 ) = −x1 + x2 à minimiser
Le domaine des solutions réalisables est donné graphiquement par :

Le domaine des solutions réalisables est convexe. Minimisons la fonction objectif : pour Z donné, on trace
) DZ d’équation −x1 + x2 = Z ⇔ x2 = x1 + Z. Lorsque Z varie, ces droites DZ de vecteur directeur
la droite
(
1
(de coefficient directeur 1) sont parallèles entre elles. On recherche une ou plusieurs droites DZ ayant
1
une ordonnée à l’origine Z minimale. Pour toute valeur de Z (∈ R), DZ rencontre le domaine des solutions
réalisables. Le programme linéaire n’a pas de solution minimale.
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 19

Exemple 1.3.11 On reprend le système de l’exemple 1.3.5 auquel on ajoute une fonction objectif :


 x1 ≥ 0, x2 ≥ 0


 x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4



 3x1 + 2x2 ≥ 6

Z(x1 , x2 ) = 20x1 + 25x2 à minimiser

Le domaine des solutions réalisables est donné graphiquement par :

4 Z
Pour Z donné, on trace la droite DZ d’équation Z(x1 , x2 ) = 20x1 + 25x2 ou encore x2 = − x1 + . Cette
( ) ( ) 5 25
4 −25 −5
droite DZ a pour coefficient directeur − , pour vecteur directeur ⃗v ou w
⃗ et pour ordonnée
5 20 4
Z 4
à l’origine . On trace des droites DZ de coefficient directeur − et on recherche une ou plusieurs droites
25 5
Z
DZ , rencontrant le domaine des solutions réalisables et ayant une ordonnée à l’origine minimale. La
25
droite DZ rencontrant le domaine
( ) des solutions réalisables et ayant une ordonnée à l’origine( minimale
) est
3 3
celle qui contient le point C 1, . La fonction objectif atteint son minimum pour le couple 1, et vaut
( ) 2 2
3 3 115
Z 1, = 20 × 1 + 25 × = .
2 2 2

Exemple 1.3.12 On considère le système mis en place dans le cadre de l’exemple 1.3.6 :


 x1 ≥ 0, x2 ≥ 0


 x1 + 3x2 ≤ 18
x1 + x2 ≤ 8



 2x1 + x2 ≤ 14

Z(x1 , x2 ) = c1 x1 + c2 x2

où Z est une fonction économique ou fonction objectif qu’il faut maximiser et c1 et c2 sont les bénéfices
unitaires.

Résolvons ce problème linéaire, on discutera bien-sûr des valeurs attribuées à c1 et c2 .

Le domaine des solutions réalisables est le domaine convexe délimité par le polygone OABCD. Les co-
ordonnées des sommets sont obtenues en déterminant les intersections des droites donc en résolvant des
systèmes de deux équations à deux inconnues.

Étude de cas particuliers

• c1 = 1, c2 = 4 : on trace les droites DZ d’équations :
1 Z
x1 + 4x2 = Z ⇔ x2 = − x1 +
4 4
20 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

( )
−4
de vecteur directeur v⃗1 . La droite qui a une ordonnée à l’origine maximale est celle qui contient
1
( )
0
le point D . La fonction objectif est maximale pour le couple (0, 6) et vaut Z(0, 6) = 0+4×6 = 24.
6
• c1 = 2, c2 = 4 : on trace les droites DZ d’équations :
1 Z
2x1 + 4x2 = Z ⇔ x2 = − x1 +
( ) 2 4
−2
de vecteur directeur v⃗2 . La droite qui a une ordonnée à l’origine maximale est celle qui
1
( )
3
contient le point C . La fonction objectif atteint son maximum au point (3, 5) et vaut Z(3, 5) =
5
2 × 3 + 4 × 5 = 26.
• c1 = 2, c2 = 2 : on trace les droites DZ d’équations :
Z
2x1 + 2x2 = Z ⇔ x2 = −x1 +
( ) 2
−1
de vecteur directeur v⃗3 . Cette droite DZ est parallèle au côté (BC) du polygone. La fonction
1
objectif atteint son maximum en tous les points du côté (BC). La fonction objectif atteint donc ce
maximum pour tous les couples (x1 , x2 ) tels que x1 +x2 = 8 et 3 ≤ x1 ≤ 6. Z vaut alors 2x1 +2x2 = 16.
• c1 = 3, c2 = 2 : on trace les droites DZ d’équations :
3 Z
3x1 + 2x2 = Z ⇔ x2 = − x1 +
( ) 2 2
−2
de vecteur directeur v⃗4 . La droite qui a une ordonnée à l’origine maximale est celle qui
3
( )
6
contient le point B . La fonction objectif atteint son maximum au point (6, 2) et vaut Z(6, 2) =
2
3 × 6 + 2 × 2 = 22.
• c1 = 5, c2 = 1 : on trace les droites DZ d’équations :
( ) 5x1 + x2 = Z ⇔ x2 = −5x1 + Z
−1
de vecteur directeur v⃗5 . La droite qui a une ordonnée à l’origine maximale est celle qui
5
( )
7
contient le point A . La fonction objectif atteint son maximum au point (7, 0) et vaut Z(7, 0) =
0
5 × 7 + 1 × 0 = 35.

Remarque 1.3.2 En fonction des différentes valeurs attribuées à c1 et c2 , la fonction objectif atteint son
maximum en différents sommets du polygone. Le programme linéaire a soit une unique solution soit une
infinité de solutions (lorsque la droite DZ est parallèle à l’un des côtés du polygone).

Étude du cas général

L’équation de DZ est donnée par :
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 21

c1 Z
DZ : c1 x1 + c2 x2 = Z ⇔ x2 = − x1 + avec c1 > 0, c2 > 0.
c2 c2
( )
−c2 c1
Ces droites DZ ont pour vecteur directeur ⃗v , pour coefficient directeur m = − et pour ordonnée
c1 c2
Z
à l’origine p = .
c2
Z
Maximiser Z est équivalent à maximiser . On recherche une ou plusieurs droites DZ rencontrant le domaine
c2
des solutions réalisables et ayant une ordonnée à l’origine maximale.
– Le côté (AB) a pour équation 2x1 + x2 = 14, le coefficient directeur est −2 et 6 ≤ x1 ≤ 7.
– Le côté (BC) a pour équation x1 + x2 = 8, le coefficient directeur est −1 et 3 ≤ x1 ≤ 6.
1
– Le côté (CD) a pour équation x1 + 3x2 = 18, le coefficient directeur est − et 0 ≤ x1 ≤ 3.
3
c1
La droite DZ a pour coefficient directeur − , on compare ensuite ce coefficient aux pentes des droites
c2
contenant les côtés (AB), (BC) et (CD).

c1 c1
• − < −2 ⇔ > 2 ⇔ c1 > 2c2
c2 c2
Dans ce cas, la droite des bénéfices est plus “pointue” que le côté (AB). Le maximum est atteint
au point A(7, 0) et en ce point seulement. Le programme linéaire admet une seule solution maximale
(7, 0) qui est un sommet, avec x2 = 0 on ne produit que P1 .
c1
• − = −2 ⇔ c1 = 2c2
c2
−2 est la pente du côté (AB). Les droites DZ : c1 x1 + c2 x2 = Z sont parallèles au côté (AB). Il y a
une infinité de solutions optimales représentées { par tous les points du segment [AB] défini par :
2x1 + x2 = 14
[AB] :
6 ≤ x1 ≤ 7
{
6 ≤ x1 ≤ 7
Tous les couples (x1 , x2 ) tels que sont solutions optimales, le bénéfice vaut alors
2x1 + x2 = 14
14c2 . En effet, Z(x1 , x2 ) = c1 x1 + c2 x2 = 2c2 x1 + c2 x2 = c2 (2x1 + x2 ).
c1 c1
• −2 < − < −1 ⇔ 1 < <2
c2 c2
−1 est la pente du côté (BC), −2 celle de (AB). Le maximum est atteint en un seul point B qui est
aussi un sommet.
c1 c1
• − = −1 ⇔ = 1 ⇔ c1 = c2
c2 c2
Les droites DZ sont parallèles au côté (BC). Il y a une infinité de solutions optimales représentées par
tous les points du segment [BC] défini par : {
x1 + x2 = 8
[BC] :
3 ≤ x1 ≤ 6
{
3 ≤ x1 ≤ 6
Tous les couples (x1 , x2 ) tels que sont solutions optimales, le bénéfice vaut alors 8c1 .
x1 + x2 = 8
c1 1
• −1 < − < −
c2 3
1
− est la pente du côté (CD), −1 celle du côté (BC). Le programme linéaire a un seule solution
3
optimale soit le point C(3, 5) qui est un sommet.
c1 1
• − = − ⇔ c2 = 3c1
c2 3
Les solutions optimales sont tous les points du{segment [CD] d’où une infinité de solutions.
x1 + 3x2 = 18
[CD] :
0 ≤ x1 ≤ 3
La fonction objectif atteint son maximum{pour tous les couples (x1 , x2 ) tels que
x1 + 3x2 = 18
0 ≤ x1 ≤ 3
et le bénéfice vaut Z = 18c1 .
 22 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

1 c1 c1 1
• − <− <0⇔0< <
3 c2 c2 3
Il existe une seule solution optimale c’est-à-dire le point D(0, 6) qui est un sommet ; x1 étant nul, on
ne produit que P2 .

Exemple 1.3.13 Considérons l’exemple suivant faisant intervenir trois dimensions :


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
2x1 + x2 + 2x3 ≤ 4

Z(x1 , x2 , x3 ) = x1 + x2 à maximiser

On 
tracele plan
 d’équation
 2x1 
+ x2 + 2x3 = 4. Ce plan rencontre les axes de coordonnées aux points
2 0 0
M1  0 , M2  4 , M3  0 .
0 0 2

Le domaine des solutions réalisables est représenté par l’intérieur de la pyramide OM1 M2 M3 . La fonction
objectif est Z(x1 , x2 , x3 ) = x1 + x2 . Lorsque Z varie, x1 + x2 = Z est l’équation d’un plan parallèle à (0, ⃗k),
ce plan rencontre le plan (O,⃗i, ⃗j) suivant la droite d’équation Z = 0 et x1 +x2 = Z. Le plan PZ qui rencontre

0
le domaine des solutions réalisables et tel que Z soit maximum est celui qui contient le point M  4 . La
0
fonction objectif atteint son maximum en un seul point qui est d’ailleurs un des sommets, c’est-à-dire M2 .

1.3.5 Cas général

Soit un programme linéaire P. On admettra les résultats suivants :
1. Le domaine des solutions réalisables de tout programme linéaire à n variables est soit l’ensemble vide
∅ soit une partie convexe de Rn .
2. Dans le cas d’un programme linéaire à deux variables, le domaine des solutions réalisables, lorsqu’il
n’est pas vide, est une partie D du plan délimité par un polygone convexe, possédant éventuellement
des côtés de longueur infinie.
Dans chaque cas, l’ensemble des solutions optimales (lorsqu’il n’est pas vide) contient un sommet de
D, c’est-à-dire que si la fonction objectif a un maximum ou un minimum, il est atteint en au moins
un des sommets du polygone délimitant le domaine des solutions réalisables.
3. On admettra que ces résultats se généralisent à un programme linéaire à n variables.

1.3.6 Exercices

 
Exercice 1  Formaliser les situations suivantes :
1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 23

1. La société Bonvin, S.A., qui pratique le négoce en vins propose à sa clientèle deux vins de table : l’un
est dénommé “Extra”, l’autre “Supérieur”. Ces produits sont obtenus par coupage de crus issus de
diverses régions : un vin de l’Hérault, un vin du Bordelais et un vin d’Italie.
Les coupages sont réalisés selon les proportions fixes suivantes :

Vin “Extra” Vin “Supérieur”

Vin de l’Hérault 0,5 0,2
Vin du Bordelais 0,3 0,6
Vin d’Italie 0,2 0,2
Total 1 1

Après les vendanges, la société dispose en stock dans ses cuves des quantités suivantes de crus d’origine :
Vin de l’Hérault .. 13600 hectolitres
Vin du Bordelais .. 12000 hectolitres
Vin d’Italie ... 10400 hectolitres
Ces quantités constituent les ressources disponibles pour la production de l’année à venir. En outre,
compte tenu des capacités techniques de mise en bouteille existantes, cette production ne peut pas
dépasser 36000 hectolitres au total dans l’année.
L’activité de cette entreprise comporte des coûts qui ont été classés en deux catégories :
– Une partie est considérée comme fixe ; elle correspond aux approvisionnements, puisque ceux-ci sont
déja constitués, ainsi qu’aux frais de personnel. Ces coûts s’élèvent à 12000000 euros pour l’année.
– L’autre partie correspond aux frais de mise en bouteille, d’emballage et de commercialisation. Cette
seconde partie est proportionnelle aux quantités produites : soit 100 euros par hectolitre de vin
quelle que soit la qualité de celui-ci.
Une étude de marché révèle que celui-ci ne saurait absorber plus de
– 20000 hectolitres de vin “Extra” à 500 euros par hectolitre,
– et 16000 hectolitres de vin “Supérieur” à 600 euros l’hectolitre.
Le problème de cette entreprise peut être formulé ainsi :
Quelles quantités faut-il produire de vin “Extra” et “Supérieur” afin de rendre maximum le bénéfice
total ?
2. Considérons désormais :
– que le vin “Extra” doit contenir au moins 30% de cru du Bordelais et au plus 20% de cru d’Italie,
– et que le vin “Supérieur” doit être composé d’au moins 60% de cru du Bordelais et d’au moins 20%
de cru de l’Hérault.
Toutes les autres caractéristiques du problème restent identiques au cas précédent.
Le problème peut s’exprimer sous la forme :
Quelle quantité de chaque vin d’origine affecter à chaque qualité de produit fini ?
3. On considère un coût d’approvisionnement qui n’est plus fixe. Transport inclus, il s’élève à :
vin de l’Hérault : 230 euros l’hectolitre,
vin du Bordelais : 250 euros l’hectolitre,
vin d’Italie : 180 euros l’hectolitre.
Il subsiste néanmoins un coût fixe constitué pour l’essentiel de frais de personnel, égal à 4000000 euros.
Le problème présent comporte trois questions :
}
- Quelle quantité produire
pour chaque vin, “Extra” et “Supérieur”,
- Quelle composition adopter
- Quelle quantité de matières premières acquérir auprès des fournisseurs ?
Remarque 1.3.3 Ces trois questions sont liées et on peut constater que le fait de connaı̂tre la quantité
de chaque matière première incorporée dans chaque produit permet de déterminer simultanément
l’approvisionnement nécessaire, la composition adéquate des produits et la quantité à produire.
 24 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

4. Les produits de la société sont conditionnés dans des récipients de 0, 75 litre et de 3 litres. Afin de
pouvoir satisfaire la clientèle, Bonvin se fixe comme objectif annuel de disposer d’au moins 400000
bouteilles de 3 litres et d’au moins 3200000 bouteilles de 0,75 litre.
Pour produire ces récipients Bonvin dispose de deux ateliers dont les rendements sont différents :
Nombre de récipients par heure de fonctionnement
Atelier A Atelier B
0,75 litre ... 500 400
3 litres ..... 400 320

Chaque atelier fonctionne au maximum 4000 heures dans l’année. Les prévisions de coût variable de
production de chaque type de récipient donnent comme résultats :
Coûts variables de production
Atelier A Atelier B
0,75 litre ... 0,4 0,55
3 litres ..... 0,75 0,85

Mais Bonvin peut également sous-traiter la fabrication de ces récipients à la société Corec qui propose
comme tarif :
0,5 euro la bouteille de 0,75 litre
1 euro la bouteille de 3 litres
Les dirigeants de Bonvin S.A. se posent trois questions
– faut-il produire des bouteilles et en quelles quantités ?
– en utilisant quelle technique de production (atelier A et/ou atelier B) ?
– faut-il sous-traiter tout ou partie de la production à Corec ?
qui peuvent être condensées en une seule :
Quelles filières utiliser pour obtenir les bouteilles nécessaires ?

 
Exercice
 2  Une entreprise stocke successivement deux types de polystyrènes A1 et A2 dans trois en-
trepôts distincts E1 , E2 et E3 afin qu’ils y subissent des traitements particuliers. Le coût de fonctionnement
de l’entrepôt E1 est de 200 euros par jour, celui de l’entrepôt E2 est de 400 euros et celui de l’entrepôt E3
est de 300 euros. Les temps de stockage pour une tonne de polystyrène A1 sont de 3 jours dans l’entrepôt
E1 , de 1 jour dans l’entrepôt E2 et d’une demi-journée dans l’entrepôt E3 . Ils sont pour le polystyrène A2
de 2 jours dans chacun des 3 entrepôts.
Les coûts de fabrication des polystyrènes A1 et A2 sont respectivement de 600 euros et 400 euros la tonne.
Les prix de vente d’une tonne des polystyrènes fabriqués sont de 1950 euros pour A1 et de 2440 euros pour
A2 .
1. (a) Calculer le coût de stockage d’une tonne de polystyrène A1 et d’une tonne de polystyrène A2 .
(b) Déterminer le bénéfice réalisé par la fabrication, le stockage et la vente d’une tonne de chacun
des produits.
(c) En déduire que le bénéfice total Z pour la production, le stockage et la vente de x tonnes de
polystyrène A1 et de y tonnes de polysytyrène A2 est donné par Z(x, y) = 200x + 240y.
2. La logistique des stockages est telle que l’entrepôt E1 peut fonctionner au maximum 360 jours dans
l’année, l’entrepôt E2 peut fonctionner au maximum 160 jours par an, l’entrepôt E3 ne peut fonctionner
annuellement plus de 120 jours.
La demande est telle que la production de polystyrène A1 ne peut dépasser 120 tonnes, celle de A2 50
tonnes.
(a) Déterminer les nombres x et y de tonnes des deux produits fabriqués pour que l’entrepôt E1
fonctionne exactement 360 jours et l’entrepôt E3 exactement 120 jours. Cette production est-elle
possible ?
 1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 25

(b) On veut maintenant déterminer les nombres x et y de tonnes des deux produits fabriqués, stockés
et vendus qui donneraient à l’entreprise le bénéfice maximum.
i. Donner les 7 contraintes de production ainsi que la fonction à maximiser sous la forme d’un
programme linéaire du type


 x ≤ · · · et/ou ≥ · · ·

 y ≤ · · · et/ou ≥ · · ·
 ..

 .

Z(x, y) = · · · à maximiser
ii. Représenter sur le graphique ci-joint le domaine des solutions réalisables en justifiant.
iii. À l’aide d’une résolution graphique, déterminer en justifiant la production qui assurera le
bénéfice maximal. Quel sera alors son prix ?

 
Exercice
 3  Une entreprise possède deux unités de production U1 et U2 . Elle commercialise ses produits à
l’aide de trois entrepôts distincts E1 , E2 et E3 situés dans différentes zones de consommation. Le tableau ci-
dessous indique pour chaque entrepôt, les proportions de stockage d’unités x et y provenant respectivement
de U1 et U2 .

HH Ei
H E1 E2 E3
Ui HHH
U1 1 2 1
U2 2 3 1

Ces valeurs signifient par exemple que les structures de l’entrepôt E1 permettent de stocker 2 fois plus
d’unités provenant de U2 que d’unités provenant de U1 .
 26 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

L’organisation actuelle des entrepôts est telle que E1 ne peut stocker au total plus de 120 unités, E2 ne peut
stocker au total plus 200 unités et E3 ne peut stocker au total plus 90 unités.
Les productions journalières de U1 et de U2 sont limitées respectivement à 80 et 50 unités.
On sait que le bénéfice réalisé par l’entreprise est de 50 euros pour la vente d’une unité de U1 et 80 euros
pour la vente d’une unité de U2 .
On veut déterminer maintenant les nombres x et y d’unités provenant de U1 et U2 , qui permettraient à
l’entreprise de réaliser un bénéfice journalier maximum.
1. Donner les 7 contraintes portant sur x et y ainsi que la fonction à maximiser sous la forme d’un
programme linéaire
2. Résolution graphique
(a) Représenter sur le graphique de la page suivante, le domaine des solutions réalisables en justifiant
vos démarches.
(b) À l’aide d’une résolution graphique, déterminer en justifiant, la production qui assurera le bénéfice
maximal. À quoi sera alors égal ce bénéfice ?

 
Exercice 4  Le gérant d’un entrepôt souhaite renouveler le matériel de sécurité de son établissement.
Il a besoin au minimum de
– 90 paires de chaussures de sécurité,
– 240 casques de sécurité,
– 240 paires de gants.
Une première entreprise de vente lui propose un lot A comprenant 2 paires de chaussures, 4 casques et
8 paires de gants pour 200 euros. Une deuxième entreprise vend pour 400 euros un lot B de 3 paires de
chaussures, 12 casques et 6 paires de gants.
Pour répondre à ses besoins, le gérant achète x lots A et y lots B.
1. Traduire par un système d’inéquations les contraintes auxquelles satisfont x et y.
 1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 27

On considère un plan P rapporté à un repère orthonormé (O,⃗i, ⃗j). A tout couple (x, y) on associe le point
M de P de coordonnées (x, y), en prenant comme unité 1 cm pour 10 lots.
2. Représenter dans P l’ensemble des points M (x, y) satisfaisant aux inéquations :


 x ≥ 0 et y ≥ 0

2x + 3y ≥ 90

 x + 3y ≥ 60

4x + 3y ≥ 120
On hachurera la partie du plan formée des points pour lesquels les contraintes ne sont pas respectées.
3. Exprimer en fonction de x et de y la dépense en euros occasionnée par l’achat de x lots A et de y lots
B.
4. Est-il possible de procéder aux achats nécessaires avec 5000 euros ? Justifier la réponse.
5. Déterminer graphiquement, en précisant la démarche suivie, le nombres de lots A et de lots B à acheter
pour avoir une dépense minimale.
6. Quelle est cette dépense minimale ?

 
Exercice
 5  Un artisan fabrique des objets A et des objets B. On dispose des informations suivantes :
– La réalisation d’un objet A demande 30 euros de matière première et 125 euros de main-d’œuvre.
– La réalisation des objets B demande 70 euros de matière première et 75 euros de mains-d’œuvre.
– Les profits réalisés sont de 54 euros par objets A, et de 45 euros par objet B.
On note x le nombre d’objets A fabriqués et y le nombre d’objets B fabriqués, en une journée. La dépense
journalière en matière première ne doit pas dépasser 560 euros. La dépense journalière en main-d’œuvre ne
doit pas dépasser 1250 euros.
1. Traduire mathématiquement ces deux hypothèses.
2. Le plan est rapporté à un repère orthonormé (unité graphique = 1 cm). Représenter graphiquement
l’ensemble des points M (x, y) dont les coordonnées vérifient ces hypothèses. Exprimer le bénéfice
 28 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE

journalier Z de l’entreprise en fonction de x et de y, puis la production journalière d’objets A et B

qui assurerait un bénéfice maximum. On précisera, graphiquement, et par le calcul, cette production
journalière.
3. En déduire le montant de ce bénéfice.

 
Exercice 6  Résoudre le problème de la société Bonvin S.A. dans sa forme initiale à l’aide de la méthode
graphique.
 
Exercice
 7  Nous prenons un exemple tiré de Hillier et Lieberman. Il s’agit d’une entreprise de fabri-
cation de chassis qui envisage la production de deux nouveaux modèles au moyen des capacités résiduelles
de ses trois ateliers. Il s’agit respectivement d’un chassis en aluminium et d’un chassis en bois. Le premier
produit nécessite le passage dans le premier atelier pour fabriquer le cadre en aluminium et dans le troisième
atelier où le verre est monté sur le chassis. Tandis que le second produit nécessite le passage dans le deuxième
atelier pour fabriquer le cadre en bois et dans le troisième atelier où le verre est monté sur le chassis. Les
marges unitaires, les temps de fabrication de chacun des produits dans chacun des ateliers ainsi que les capa-
cités hebdomadaires résiduelles de ces ateliers sont donnés au tableau ci-dessous. Combien faut-il produire

Produit 1 Produit 2 Capacité disponible

(heures/produit) (heures/produit) (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3$ 5$

de chassis de chaque type par semaine pour maximiser le profit net ?

 1.3. MÉTHODE GRAPHIQUE : PROBLÈME À DEUX INCONNUES 29

 
Exercice 8  Une société de tri de déchets et recyclage de papier peut se fournir en déchets auprès de
deux villes. Son rôle consiste à séparer les listes d’ordinateur et les journaux. La répartition entre ménages
et sociétés est différente d’une ville à l’autre expliquant un pourcentage différent de listes d’ordinateur et de
journaux dans les déchets. Ces pourcentages ainsi que la quantité maximum de déchets que peuvent fournir
par an ces deux villes sont reprises au tableau suivant : La société offre aux villes un prix de 35e par tonne

Listes (%) Journaux (%) Offre (tonnes par an)

Ville 1 5 20 10000
Ville 2 15 30 20000

de déchet. Elle doit décider du montant optimal de déchets à acheter à chaque ville pour minimiser son coût
d’achat. Pour couvrir ses frais fixes, la société doit au moins collecter 1500 tonnes de listing d’ordinateur par
an. La société ne desire pas collecter plus de 6000 tonnes de journaux par an. Combien la société doit-elle
acheter de déchets par an à chacune des villes ?
1. Formuler mathématiquement le problème (choix des variables, expression des contraintes et de l’ob-
jectif).
2. Déterminer graphiquement le plan d’achat optimal et en déduire le coût d’achat minimum.
 
Exercice
 9  Une entreprise fabrique deux produits P1 et P2 . Chaque produit doit passer les deux ateliers
d’usinage et de finition. Le mois dernier, 500 unités de P1 ont été produites grâce à 750 heures d’usinage
et 250 heures de finition. De même, 700 unités de P2 ont été produites, nécessitant 700 heures d’usinage et
350 heures de finition. Une partie du coût de production est indépendante du nombre d’heures passées à
la production (les frais fixes), une partie est directement proportionnelle au nombre d’heures passées à la
production (les frais variables). Le mois passé, on a observé la répartition suivante entre frais fixes et frais
variables : Il y a un coût de conditionnement de 8e l’unité pour P1 et de 6e pour P2 . Les prix de vente sont

Section Frais fixes Frais variables

Usinage 60000 11600
Finition 40000 6000

de 55e et 43e respectivement.

1. Calculer les marges sur coûts variables (différence entre prix de vente et coût variable de production)
par unité de chacun des deux produits. Indication : calculer d’abord le prix de l’heure dans chacun
des ateliers et le temps nécessaire dans chacun des ateliers par produit.
2. Les capacités de production sont de 1200 heures par mois pour l’usinage et de 500 heures pour la fini-
tion. Formuler le programme linéaire correspondant à la maximisation de la marge sur coûts variables.
3. Déterminer graphiquement la solution optimale.
30 CHAPITRE 1. LA PROGRAMMATION LINÉAIRE - MÉTHODE GRAPHIQUE