;

Département de Mathématiques et Informatique

;
École Nationale Supérieure d’Arts et Métiers
Université Moulay Ismaïl
Meknès

Cours et travaux dirigés de Mathématiques

Intitulé de module : Programmation Linéaire & Statistiques
Intitulé de l’élément de module :

Programmation Linéaire

Filière : Génie civil

Volume horaire de l’élément de module : 20h

Année universitaire : 2022/2023

Mohamed BENDAOUD
Email : [Link]@[Link]

..........................................................................................................................
École Nationale Supérieure d’Arts et Métiers, Marjane II, B.P. 15290, Al Mansour, Meknès
Tél : +212(0)535457160/61- +212(0)648313896
Fax : +212(0)535467163
Table des matières

Introduction 4

1 Programmation linéaire 6
1.1 Introduction à la recherche opérationnelle . . . . . . . . . . . . . . . . . 6
1.1.1 Enjeux de la recherche opérationnelle . . . . . . . . . . . . . . . 8
1.1.2 Formulation d’un problème d’optimisation . . . . . . . . . . . . 8
1.1.3 Méthodes et outils de la recherche opérationnelle . . . . . . . . . 9
1.2 Modélisation d’un programme linéaire . . . . . . . . . . . . . . . . . . . 9
1.3 Méthode graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.1 Algorithme du Simplexe . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Tableaux Simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.3 Détérmination d’une solution de base admissible . . . . . . . . . 35
1.4.4 Utilisation de la méthode du simplexe dans un problème de mini-
misation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.5 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.5.1 Définition et exemples . . . . . . . . . . . . . . . . . . . . . . . 40
1.5.2 Propriétés de la dualité . . . . . . . . . . . . . . . . . . . . . . . 42
1.5.3 Correspondances entre les tableaux simplexes optimaux Dual et
Primal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.5.4 Interprétation économique de la dualité . . . . . . . . . . . . . . 44
1.6 Analyse de sensitivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.6.2 Paramétrisation de la fonction économique . . . . . . . . . . . . 46
1.6.3 Paramétrisation du second membre des contraintes . . . . . . . . 47
1.7 Mises-en oeuvre sur un solveur . . . . . . . . . . . . . . . . . . . . . . . 49

2 Programmation en nombres entiers 53

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.2 La méthode de séparation et d’évaluation (Branch and Bound) . . . . . . 54
2.2.1 Relaxation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2.2 Démarche de résolution . . . . . . . . . . . . . . . . . . . . . . 54
Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2
Table des figures

1.1 La ville de Königsberg et ses 7 ponts. . . . . . . . . . . . . . . . . . . . 6

1.2 Graphe associé au problème des ponts de Königsberg . . . . . . . . . . . 7
1.3 Régionnement du plan par une contrainte. . . . . . . . . . . . . . . . . . 17
1.4 Région réalisable d’un problème. . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Problème ayant une solution maximale unique. . . . . . . . . . . . . . . 18
1.6 Polyèdre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Problème ayant une infinité de solutions maximales. . . . . . . . . . . . . 20
1.8 Problème à solution minimale unique. . . . . . . . . . . . . . . . . . . . 21
1.9 Problème à solution minimale unique. . . . . . . . . . . . . . . . . . . . 22
1.10 Problème à solution impossible. . . . . . . . . . . . . . . . . . . . . . . 22
1.11 Problème à solution rejeté à l’infini. . . . . . . . . . . . . . . . . . . . . 23
1.12 Problème à région réalisable ne contenant pas l’origine. . . . . . . . . . . 35
1.13 Intervalles de stabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.1 Arbre d’un programme linéaire à variables entières. . . . . . . . . . . . . 55

2.2 Branchement du PL à variables entières . . . . . . . . . . . . . . . . . . 57
2.3 Arbre associée à un PL à variables entières . . . . . . . . . . . . . . . . . 57
2.4 Branchement d’un PL à variables entières . . . . . . . . . . . . . . . . . 58

3
 Introduction

Introduction
La recherche opérationnelle est une discipline qui a pour rôle d’assurer la compré-
hension et la modélisation des systèmes industriels et du secteur public et de les traduire
au monde théorique fondé principalement par des mathématiques, des statistiques et de
l’informatique.

L’employabilité de la recherche opérationnelle est composée de deux phases. La pre-

mière consiste à formuler mathématiquement un problème qui demande une analyse dé-
taillée et suffisamment précise pour recueillir les caractéristiques essentielles du problème
posé en plus d’un savoir-faire et d’une certaine expérience. La deuxième phase s’intéresse
à la résolution du problème par l’utilisation d’algorithmes rigoureux et bien déterminés.

Comme objectif de ce cours est de présenter l’un des méthodes de recherche opéra-
tionnelle à savoir la programmation linéaire. Le premier objectif de ce cours est de ce
concentrer sur la formulation et la modélisation des problèmes d’optimisation continue
ou discrètes où les contraintes et le critère (ou la fonction objective) s’expriment linéai-
rement. Dans cette partie, nous commencerons par la collecte des données et des infor-
mations fournies par le problème traité. Ensuite nous présentons les différentes étapes à
suivre pour donner une vision mathématique globale. Le deuxième objectif concerne la
présentation des différentes techniques de résolution de ces problèmes dont le but est de
trouver la meilleure solution (appelée solution optimale) ou pour le problème étudié.

Le premier chapitre est est organisé en cinq sections. La première section est des-
tiné à la présentation de la recherche opérationnelle, son utilisation et les domaines qui
font appel à cette discipline. Les autres sections sont consacré à la formulation et la ré-
solution d’une programmation linéaire, c’est-à-dire les problèmes où les contraintes et la
fonction objective sont linéaires. Dans ce chapitre nous apprendrons comment translater
et formuler des problèmes sous forme d’un programme linéaire, puis nous présenterons
les méthodes de résolution d’un programme linéaire à savoir la résolution graphique et la
résolution analytique, plus précisément l’algorithme du simplexe qui est la méthode prin-
cipale pour la résolution de programmes linéaires en nombres réels. Nous conclurons en
donnant un petit aperçu sur la dualité et ses principales applications dans les programmes
linéaires. L’analyse de la sensibilité ainsi que et la mise en oeuvre un solveur libre et/ou
professionnel sont aussi présentées.

Le deuxième chapitre traitera des problèmes en nombres entiers. La résolution de ces

problèmes fait appel à des techniques et des algorithmes de résolution. Parmi eux nous
présenterons dans un premier temps l’approche par énumération, suivie par une présenta-
tion de la méthode de branch and bound pour les valeurs entières. On parle de la résolution
en nombres entiers lorsque les valeurs des variables doivent être entières, par rapport à la
résolution en nombres réels.

Les notes de ce cours se composent à la fois de cours magistraux et de séances de

travaux dirigés.

Mohamed BENDAOUD 4
Chapitre 1 1.1 Introduction à la recherche opérationnelle

Ce cours de RO s’adresse aux étudiants de la troisième année de L’ENSAM-Meknès

de la filière Génie Civil, à l’Université de Moulay Ismaïl. Bien évidemment, de nombreux
aspects ne sont pas étudiés faute de temps et de volume horaire. Cependant, les notions
de base choisies dans ce cours permettent aux étudiants d’acquérir des connaissances et
un savoir-faire en Recherche Opérationnelle pour traiter divers problèmes.
Ce support de cours comporte également une annexe consacrée à des rappels d’al-
gèbre linéaire et quelques notions algorithmiques, qui constituent les pré-requis à une
bonne compréhension des premières parties du cours.

Ces notes de cours ne vous seront profitables que si vous préparez régulièrement et
sérieusement les T.D.s et ne vous dispensent bien évidement pas d’assister au cours.

Mohamed BENDAOUD 5
Chapitre 1

Programmation linéaire

1.1 Introduction à la recherche opérationnelle

La Recherche Opérationnelle (RO) est une discipline qui permet de formuler des pro-
blèmes par des supports scientifiques, mathématiques et informatiques pour aider à mieux
décider. La RO est donc un outil d’aide à la décision.

Autrement définie, la RO traduit des énoncés ou des cahiers de charges liés à des
problématiques spécifiques sous forme de méthodes et des démarches à base d’équation
mathématique, des algorithmes et des outils statistiques.

Comme premier exemple d’application de la RO, on cite le problème des ponts de

Königsberg ci-dessous :
Exemple 1.1.1 (Euler 1735)

F IGURE 1.1 – La ville de Königsberg et ses 7 ponts.

Deux îles de la ville de Königsberg sont reliées entre elles par 1 pont. D’autre part
6 autres ponts relient les îles à la ville. La question posée est la suivante : à partir d’un

6
Chapitre 1 1.1 Introduction à la recherche opérationnelle

point de départ quelconque, existe-t-il un chemin passant une et une seule fois par chaque
pont et qui revient au point de départ ?

La réponse (apportée par Euler) est non. La preuve utilise un graphe : les arêtes
du graphe représentent les ponts et les sommets correspondent aux différents endroits
de la ville (les rives gauche et droite et les deux îles ; voir figure Figure 1.2 ci-dessous).
Supposons qu’un tel chemin existe. Un tel chemin est appelé chemin eulérien. Alors né-
cessairement en chacun des noeuds du graphe il y a toujours un nombre pair d’arêtes
reliées au noeud : s’il y a une arête qui arrive au noeud, il y en a nécessairement une
autre (différente) qui le quitte. Or, on constate que le graphe possède des noeuds (tous
en fait !) reliés à un nombre impair d’arêtes. Par conséquent, il n’existe pas de chemin
eulérien.

F IGURE 1.2 – Graphe associé au problème des ponts de Königsberg

La RO permet d’assurer la communication entre le milieu industriel (les secteurs ex-

térieurs) et les applications théoriques dans le but de proposer les solutions les mieux
adaptées à une situation donnée.

La procédure utilisée par la RO peut être schématisée comme suit :

Mohamed BENDAOUD 7
Chapitre 1 1.1 Introduction à la recherche opérationnelle

Problème concret

Modélisation

Résolution par une méthode de R.O

Interprétation des résultats

Prise de décision

La R0 est utilisée dans les domaines ou la prise de décision fait appel à la résolution
des problèmes d’optimisation, qui sont des problèmes d’analyse fonctionnelle qui cherche
l’extremum d’une fonction, telle que les problèmes de :
• Dimensionnement,
• localisation
• Détection de dysfonctionnements : diagnostics, réparation, maintenance.
• Gestion de ressources
• Partage des ressources
• Rentabilisation des investissements
• Etc...

1.1.1 Enjeux de la recherche opérationnelle

L’utilisation de la RO devient de plus en plus sollicitée dans la vie quotidienne et à
différents niveaux puisqu’elle offre plusieurs avantages et traite plusieurs points tels que :
• elle propose les meilleures décisions stratégiques ;
• l’accession à l’innovation ;
• fournit une meilleure gestion des ressources.
• l’amélioration de la compétitivité des entreprises ;
• Etc...

1.1.2 Formulation d’un problème d’optimisation

La formulation d’un problème d’optimisation ou le passage du texte vers les équations
mathématiques doit passer par : l’analyse, la modélisation et le critère à optimiser décrit
comme suit :

• Analyse : Dans cette phase, on commence toujours par l’identification des don-
nées nécessaires à la résolution du problème, les valeurs de consommations ou les
fiches techniques des articles, la quantité des ressources disponibles, les coûts de
transport, la capacité de production, les gains engendrés par chaque article ou les

Mohamed BENDAOUD 8
Chapitre 1 1.2 Modélisation d’un programme linéaire

dépenses établies pour la réalisation d’une action. Dans cette phase, on détermine
les composantes, les enjeux et les limites du problème.

• Modélisation : L’optimisation repose toujours sur des modèles mathématiques.

Pour définir le modèle d’un système, on définit :
i) Les variables : On détermine les variables ou les inconnues du système qui re-
présente les décisions à prendre et qui doivent répondre à un certain nombre de
questions : que faut-il réaliser et en quelle quantité ? Combien doit-on acheter ?
...
ii) Les contraintes : Les objets mathématiques qui assurent l’interaction et la
liaison des variables par rapport aux ressources disponibles et aux données du
problème sont appelées contraintes.

• Critère a optimisé : Représente l’objectif ou le but attendu du problème. Il peut

être une fonction de minimisation lorsqu’il s’agit d’une dépense, d’un investisse-
ment ou une fonction de maximisation lorsqu’il s’agit d’un profit ou de gain.

1.1.3 Méthodes et outils de la recherche opérationnelle

Parmi les méthodes les plus courantes en recherche opérationnelle on pet citer :

• Programmation linéaire : permet de résoudre les problèmes d’optimisation où la

fonction objective et les contraintes sont toutes linéaires.
• Programmation non linéaire : traite les problèmes non linéaires.
• Programmation dynamique : adaptée au problèmes du plus court chemin et des
problèmes combinatoires difficiles.
• Processus stochastiques : concerne les problèmes aléatoires, ’problèmes de fiabi-
lité, ...
• Théorie des graphes : s’intéresse à la résolution des problèmes d’ordonnancement
et d’optimisation à l’aide des graphes.
• Heuristiques et métaheuristiques : concerne les problèmes où la solution ne peut
être obtenue en temps raisonnable.

Comme outils, on peut citer de nombreux logiciels payants ou libres pour la résolution
des problèmes de de la recherche opérationnelle :

• Logiciels d’aide à la décision : MATLAB, SAP, Produit ILOG, ...

• Logiciels d’optimisation : MATLAB, excel, cplex, xpress, glpk, gurobi, ...
• Logiciel de simulation : qnap, simula, ...
• Les API C++ ou java, ...

1.2 Modélisation d’un programme linéaire

Les problèmes de programmation linéaire (PL) sont des problèmes d’optimisation où :
• les variables de décision du problème sont positives ;

Mohamed BENDAOUD 9
Chapitre 1 1.2 Modélisation d’un programme linéaire

• la fonction objectif (ou le critère de selection de la meilleure décision) doit être

une fonction linéaire de ces variables ;
• les contraintes ou les restrictions relatives aux variables de décision (exemple :
limitations de ressources) doivent être exprimés par un ensemble d’équations li-
néaires.

La modélisation d’un PL ou le passage du texte vers les équations mathématiques doit

passer par les étapes suivantes :
• Identifier les variables (ou les inconnues) du problème et les représenter sous
forme symbolique (exemple : x1 , x2 , ... )
• Formuler les contraintes et les exprimer par un système d’équations linéaires.
• Formuler la fonction objectif (ou la fonction économique), traduisant les préfé-
rences du décideur, sous forme linéaire en fonction de variables de décision. Puis
spécifier si la fonction objectif est à maximiser ou à minimiser.
Exemple 1.2.1 (Problème de ciment)
Une usine produit deux types ciments C1 et C2 , rapportant 500 DH et 700 DH par
tonne. Une tonne de C1 nécessite 40min de calcination dans un four à chaux et 20min de
broyage. Une tonne de C2 nécessite 30min de calcination dans un four à chaux et 30min
de broyage.

Le four et l’atelier de broyage sont disponibles 6h et 8h par jour. Combien de ciment

de chaque type peut-on produire par jour pour maximiser le bénéfice ?
Solution.
• Choix des variables :
x1 et x2 sont respectivement les quantités de C1 et C2 à produir par jour.
• Formulation des contraintes :
Disponibilité du four : 40x1 + 30x2 ≤ 360.
Disponibilité du broyeur : 20x1 + 30x2 ≤ 480.
Positivité des variables : x1 , x2 ≥ 0.
• La fonction objective à maximiser est z(x1 , x2 ) = 500x1 + 700x2 .
Ainsi, le problème de production se modélise sous forme :

maxz = 500x1 + 700x2

 40x1 + 30x2 ≤ 360
s.c. 20x1 + 30x2 ≤ 480
x1 , x2 ≥0


Exemple 1.2.2 Une entreprise fabrique des tables et des chaises à partir de deux ma-
tières : le bois et la peinture, sachant que la réalisation d’une table nécessite 3 m de bois
et 4 kg de peinture la réalisation d’une chaise nécessitent 2 m de bois et 1 kg de peinture.
Les moyens financiers de l’entreprise acceptent un approvisionnement de 100 m de bois
et 120 kg de peinture par semaine. Les produits ainsi fabriqués fournissent un bénéfice de
500 DH par table et 300 DH par chaise vendu.
On souhaite maximiser le bénéfice total de l’entreprise venant de la vente des tables et
des chaises.
Question : formuler le problème.

Mohamed BENDAOUD 10
Chapitre 1 1.2 Modélisation d’un programme linéaire

Solution. Reprenons les données de l’exemple sur le tableau suivant :

Table Chaise Stock

bois 3 2 100
peinture 4 1 120
Gain 500 300

• Choix des variables :

x1 : représente la quantité des tables ;
x2 : représente la quantité des chaises.
• Formulation des contraintes :
Pour le bois : 3x1 + 2x2 ≤ 100.
Pour la peinture : 4x1 + x2 ≤ 120.
En tenons compte de la non-négativité des variables, on ajoute la contrainte
supplémentaire au problème : x1 , x2 ≥ 0.
• Fonction objectif :

Le gain : z(x1 , x2 ) = 500x1 + 300x2 =⇒ L’objectif : max z = 500x1 + 300x2 .

Ainsi, le programme linéaire qui modélise ce problème est :

maxz = 500x1 + 300x2

 3x1 + 2x2 ≤ 100
s.c. 4x1 + x2 ≤ 120
x1 , x2 ≥0


Exemple 1.2.3 (Problème de Production)

Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de ressources :
post opératoire (machine), main-d’oeuvre et emballage. Ces besoins sont indiqués dans
le tableau ci-dessous. Les ressource sont disponibles en quantités limitées comme suit :

P1 P2 Ressource disponible
Heure / Machine 3 9 81
main d’oevre 4 5 55
emballage 2 1 20

Les deux produits P1 et P2 rapportent à la vente respectivement des profits de 600 DH

et 400 DH par unité. Quelles quantités de produits P1 et P2 , doit produire l’usine afin de
maximiser le bénéfice total venant de la vente des deux produits ?
Solution.
• Choix des variables :
x1 et x2 sont respectivement les quantités des produits P1 et P2 à fabriquer
(x1 , x2 ∈ N).
• Formulation des contraintes : 
 3x1 + 9x2 ≤ 81
La disponibilité des ressources s’écrit : 4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20

Positivité des variables : x1 , x2 ≥ 0.

Mohamed BENDAOUD 11
Chapitre 1 1.2 Modélisation d’un programme linéaire

• La fonction objective z(x1 , x2 ) correspond au bénéfice total qui vaut

z(x1 , x2 ) = 600x1 + 400x2 ,

et le profit à maximiser est :

max z = 600x1 + 400x2 .

Ainsi, le problème de production se modélise sous forme :

maxz = 600x1 + 400x2


 3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55

s.c.

 2x1 + x2 ≤ 20
x1 , x2 ≥ 0.


Exemple 1.2.4 (Problème d’Alimentation)

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 alimentaires principales D1 , D2 et trois éléments nutritifs, les vitamines V ,
les calories C et les protéines P . Le nombre d’éléments nutritifs par unité d’aliment sont
comme suit : Une unité de D1 contient 1 unité de V , 1 unité de C et 3 unités de P . Une
unité de D2 contient 5 unité de V , 2 unité de C et 2 unités de P . 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 et 25 pour D2 .

Solution.
• Choix des variables :
x1 et x2 sont respectivement les quantités de D1 et D2 dans le menu à compo-
ser.
• Formulation des contraintes :
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 et 25 pour
D2 . 
 x1 + 5x2 ≥ 5
Réalisation du menu : x1 + 2x2 ≥ 4
3x1 + 2x2 ≥ 6

Positivité des variables : x1 , x2 ≥ 0.
• La fonction objective à minimiser est z(x1 , x2 ) = 20x1 + 25x2 .
Ainsi, le problème de d’alimentation se modélise sous forme :

min z = 20x1 + 25x2


 x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4

s.c.

 3x1 + 2x2 ≥ 6
x1 , x2 ≥ 0.


Exemple 1.2.5 (Réseaux de transport)

Supposons que 250 (resp. 450) containers sont disponibles au dépôt D1 (resp. au dépôt

Mohamed BENDAOUD 12
Chapitre 1 1.2 Modélisation d’un programme linéaire

D2) et que les magasins A, B et C ont commandés 200 containers chacun. Les coûts de
transport par containers sont les suivants :

Magasin A Magasin B Magasin C

Dépot D1 3,4 2,2 2,9
Dépot D2 3,4 2,4 2,5

Le but est de minimiser le coût total de transport des containers des dépôts vers les ma-
gasins en respectant les disponibilités et les demandes. Formuler mathématiquement le
problème.
Solution.
• Choix des variables :
xij le nombre de containers transportés du dépôt i vers le magasin j (i = 1, 2
et j = A, B, C).
• Formulation des contraintes
 :
x1A + x1B + x1C ≤ 250
Disponibilité :
 x2A + x2B + x2C ≤ 450
 x1A + x2A = 200
Demande : x1B + x2B = 200
x1C + x2C = 200

Positivité des variables : xij ≥ 0, à valeurs entières.
• La fonction objective à minimiser

z(xij , i = 1, 2, j = A, B, C) = 3, 4x1A +2, 2x1B +2, 9x1C +3, 4x2A +2, 4x2B +2, 5x2C .

Ainsi, le problème de réseaux de transport se modélise sous forme :

min z = 3, 4x1A + 2, 2x1B + 2, 9x1C + 3, 4x2A + 2, 4x2B + 2, 5x2C


 x1A + x1B + x1C ≤ 250
x2A + x2B + x2C ≤ 450




x1A + x2A = 200

s.c.

 x1B + x2B = 200
x + x2C = 200

 1C



xij ≥ 0, i = 1, 2, j = A, B, C.

Exemple 1.2.6 (Problème du sac à dos)

Dans ce problème on dispose de n objets et d’un sac à dos pouvant supporter un poids
maximal P . A chaque objet est associé un poids et une valeur. On souhaite remplir le sac
de sorte à maximiser la somme des valeurs des objets qu’il contient sans dépasser le poids
total autorisé.
Solution.
• n le nombre d’objets ;
• vi la valeur de l’objet i = 1, 2, . . . n ;
• pi le poids de l’objet i = 1, 2, . . . n ;
• P le poids total supporté par le sac ;
• xi la variable de décision qui vaut 1 si l’objet i est choisi, 0 sinon.

Mohamed BENDAOUD 13
Chapitre 1 1.2 Modélisation d’un programme linéaire

Le problème du sac à dos se modélise comme suit :

n
X
max z = vi xi
 n i=1
 Xp x

≤P
i i
s.c. i=1

 x ∈ {0, 1}, i=1, 2, . . .n.
i

Remarque 1.2.7 (Forme générale d’un PL)

De façon générale, un problème de programmation linéaire ou un programme linéaire met
en jeu les variables, les ressources et les contraintes (capacités) du problème. Considérons
(xi )1≤i≤n variables (produits) nécessitant l’utilisation de m sources. Pour 1 ≤ i ≤ n et
1 ≤ j ≤ m, notons par ci la marge unitaire du produit i et bj la quantité de ressource
j disponible et par aij la quantité de ressource i consommée pour produire une unité de
produit j. Les donnés du problème peuvent être résumées dans le tableau suit ci-dessous

Ressources Variables Contraintes

x1 x2 ... xn
1 a11 a12 ... a1n b1
2 b2
. .
. .
. .
m am1 am2 ... amn bm
Marge c1 c2 ... cn
et la forme générale du PL s’écrit :

max(min)z
 = c1 x1 + ... + cn xn

 a11 x1 + ... + a1n xn ≤ (ou = ou ≥) b1
a21 x1 + ... + a2n xn ≤ (ou = ou ≥) b2




. .



s.c. . .
. .




a x + ... + amn xn ≤ (ou = ou ≥) bm

 m1 1



x1 , ..., xn ≥ 0.
En tenant compte du fait que, pour tout a, b ∈ R,
• min z = − max(−z),
• a = b ⇐⇒ a ≤ b et a ≥ b,
• a ≥ b ⇐⇒ −a ≤ −b,
on en déduit que le PL s’écrit sous la forme suivante dite forme canonique :

max z = ct x
s.c. Ax ≤ b
x≥0

Mohamed BENDAOUD 14
Chapitre 1 1.3 Méthode graphique

       
x1 a11 a12 ··· a1n b1 c1
 x2   a21 a22 ··· a2n   b2   c2 
où x =  , A =  , b =  , c =   et ct
       
.. .. .. ... .. .. ..
 .   . . .   .   . 
xn am1 am2 · · · amn bm cn
désigne le transposé du vecteur c.
Résoudre le programme linéaire consiste à déterminer les n-uplets (x1 , x2 , ..., xn ) qui
optimisent z (c.-à-d., maximisent ou minimisent z).
Définition 1.2.8 On appelle :
• solution réalisable (ou admissible) du PL tout n-uplet (x1 , x2 , ..., xn ) vérifiant le
système d’inéquations précédent ;
• solution optimale toute solution réalisable qui optimise z ;
• fonction objectif la forme linéaire z(x1 , x2 , ..., xn ) = c1 x1 + c2 x2 + ... + cn xn ;
• polyèdre de Rn tout partie Q de Rn qui s’écrit sous la forme Q = {x ∈ Rn :
Ax ≤ b} où A est une matrice m × n et b ∈ Rm .
L’ensemble des solutions réalisables du PL est appelé domaine des solutions réalisables.
Lorsque ce domaine est non vide, on dit que le PL est réalisable.
Définition 1.2.9 On dit qu’un PL est sous forme standard s’il s’écrit sous la forme
max z = ct x
s.c. Ax = b
x ≥ 0.
Proposition 1.2.10 Tout PL sous forme standard s’écrit de façon équivalente en un PL
sous forme canonique et inversement.
Exemple 1.2.11 Formuler le programme linéaire suivant sous forme canonique et stan-
dard.
minz = 2x1 − x2
 4x1 + x2 ≥ 55
s.c. x1 + 3x2 = 27
x1 ≥ 0, x2 ∈ R.


Solution : Forme canonique :

−
maxz = −2x1 + x+ 2 − x2
−
 −4x1 − x+ 2 + x2 ≤ −55
−
 +
x1 + 3x2 − 3x2 ≤ 27

s.c. −
 −x 1 − 3x 2 + 3x 2 ≤ −27
−
 +
x1 , x2 , x2 ≥ 0;


− −
où z = −z et x2 = x+ +
2 − x2 avec x2 = max(x, 0) et x2 = − min(x, 0).
Forme standard :
−
maxz = −2x1 + x+ 2 − x2
+ −
 −4x1 − x2 + x2 + e1 = −55
−
s.c. x1 + 3x+ 2 − 3x2 = 27
+ −
x1 , x2 , x2 ≥ 0;


− −
où x2 = x+ +
2 − x2 , z = −z et e1 = −55 − (−4x1 − x2 + x2 ) appelé variable d’écart.

Mohamed BENDAOUD 15
Chapitre 1 1.3 Méthode graphique

1.3 Méthode graphique

La méthode de la résolution graphique d’un problème linéaire à deux variables est
simple et repose sur le régionnement du plan, mais elle est la plus limitée puisque dès
lors que le nombre des variables dépasse 2, elle devient impraticable. Cette méthode
consiste à tracer la droite qui sépare les demi-plans pour chaque contrainte tout en conser-
vant le demi-plan acceptable, c’est-à dire, le demi-plan des solutions réalisables pour la
contrainte. L’intersection des différents demi-plans de toutes les contraintes sans oublier
les contraintes de positivité forme le polygone des solutions (polyèdre convexe), appelé
aussi "région des solutions admissibles" ou "région réalisable".

Exemple 1.3.1 Soit le programme linéaire suivant :

maxz = 600x1 + 400x2


 4x1 + 5x2 ≤ 55
x1 + 3x2 ≤ 27

s.c.

 2x1 + x2 ≤ 20
x1 , x2 ≥ 0.


Le problème possède trois contraintes plus la contrainte de positivité. On commence à

tracer chaque contrainte séparément.

On prend la première contrainte du système 4x1 + 5x2 ≤ 55 et on remplace l’inégalité

par une égalité. L’équation résultante correspond à une droite d’équation 4x1 + 5x2 = 55.
Pour tracer cette droite, il faudrait déterminer deux points de celle ci :
• Pour x1 = 0, on a x2 = 11, et le premier point de cette droite est (x1 , x2 ) = (0, 11).
• Pour x2 = 0, on a x1 = 55/4 = 13, 75, et le deuxième point est (x1 , x2 ) =
(55/4, 0).

À partir de ces deux points on trace la première droite qui partage le plan en deux
demi-plans. Notons que pour tout point M (x1 , x2 ) appartenant au demi plan qui contient
le centre O(0, 0), on a 4x1 +5x2 ≤ 55 puisque pour le centre O on a 4×0+5×0 = 0 ≤ 55.
Ainsi, on conserve ce qui est en dessous de la droite, et on élimine la partie supérieure
puisque la contrainte est une contrainte d’infériorité ; voir figure Figure 1.3 ci-dessous :
On applique le même principe pour toutes les contraintes y compris les contraintes de
positivité. L’intersection de toutes les contraintes forme le domaine plan convexe, délimité
par le polygone OABCD, tel qu’il est donné par la partie hachurée dans la Figure 1.4.

La question qui se pose maintenant est : quel est le point qui donne la valeur optimale
pour ce problème ? C.-à-d., quels sont les couples (x1 , x2 ) de solutions réalisables tels que
z(x1 , x2 ) = 600x1 + 400x2 soit maximum ?

Pour répondre à cette question, on suit la procédure suivante : Pour tout nombre z, on
note Dz la droite d’équation z = 600x1 + 400x2 ou encore x2 = −3/2x1 + z/400 appe-
lée généralement droite d’isovaleur (ou de niveaux) de la fonction objectif. Cette droite a
pour coefficient directeur −3/2 et d’ordonnée à l’origine z/400.

Mohamed BENDAOUD 16
Chapitre 1 1.3 Méthode graphique

F IGURE 1.3 – Régionnement du plan par une contrainte.

F IGURE 1.4 – Région réalisable d’un problème.

Mohamed BENDAOUD 17
Chapitre 1 1.3 Méthode graphique

Lorsque z varie, ces droites Dz ayant même coefficient directeur sont parallèles entre
elles. L’ordonnée à l’origine des droites Dz est z/400. Maximiser z est équivalent à maxi-
miser z/400. Le problème consiste donc à déterminer une ou plusieurs droites Dz qui
rencontrent le domaine des solutions réalisables et ayant une ordonnée à l’origine maxi-
male. Lorsque z augmente, la droite Dz se déplace parallélement à elle même vers le haut.
Ainsi, on trace d’abord la droite D0 pour z = 0 qui est la plus petite valeur pour la fonc-
tion objective, puis on effectue une translation parallèle à la direction de la droite du bas
vers le haut jusqu’à rencontrer le dernier point de la région réalisable.
La droite Dz qui rencontre la région réalisable et qui a une ordonnée à l’origine maxi-
male est celle qui passe par le point B, voir Figure 1.5.
On obtient ainsi le point qui correspond à la solution optimale. Par la projection de ce
point sur les axes du repère (ou en utilisant le fait que B est l’intersection de la première
et la troisième contrainte) on obtient ces coordonnées : x1 = 7, 5 et x2 = 5.

F IGURE 1.5 – Problème ayant une solution maximale unique.

Ainsi, le programme linéaire a une seule solution maximale, le couple (7, 5; 5) qui est
un sommet de la région réalisable, pour laquelle la fonction objectif est optimale et vaut
z = 600x1 + 400x2 = 6500.
Les écarts de l’optimum sont données comme suit :

Contraintes Ressources Utilisations Ecarts

4x1 + 5x2 ≤ 55 55 55 0 Saturée
x1 + 3x2 ≤ 27 27 22,5 4,5 Marginale
2x1 + 20x2 ≤ 20 20 20 0 Saturée
Lorsque les contraintes sont de type ≥, on parle de surplus et non pas écart.

Définition 1.3.2 Soit P L un programme linéaire à deux variable et R sa région réali-

sable. On appelle solution de base réalisable de P L tout sommet de la région R.

Mohamed BENDAOUD 18
Chapitre 1 1.3 Méthode graphique

Proposition 1.3.3 Soit P L un programme linéaire à deux variables et R sa région réali-

sable. On admettra les résultats suivants :
1) R est soit vide soit un polyèdre (une partie du plan délimitée par un polygone)
convexe.
2) L’optimum de la fonction objectif du P L, s’il existe, est atteint en au moins un
sommet de R.
3) Si P L admet deux solutions de base réalisables optimales, alors ces deux points
sont adjacentes.
4) On admettra que ces résultats se généralisent à un programme linéaire à n va-
riables. En particulier, le domaine des solutions réalisables de tout programme
linéaire à n variables est soit l’ensemble vide ∅ soit un polyèdre convexe de Rn .

F IGURE 1.6 – Polyèdre.

Remarque 1.3.4 Pour trouver la solution optimale d’un P L, il suffit d’évaluer la fonction
objective en chaque sommet de la région réalisable du problème, et de sélectionner la
solution optimale. Cette méthode s’appelle la méthode de l’énumération.
Exemple 1.3.5 Dans l’Exemple 1.3.1 ci-dessus, les sommets du polyèdre de la région
réalisable sont O(0; 0), A(10; 0), B(7, 5; 5), C(30/7; 53/7) et D(0; 10) et on a le tableau
suivant :
O A B C D
x1 0 10 7,5 30/7 0
x2 0 0 5 53/7 10
z 0 6000 6500 5600 4000
La solution optimale est alors obtenue au sommet B pour laquelle la fonction objective
vaut 6500.
Exemple 1.3.6 Soit le programme linéaire suivant :
maxz = 40x1 + 50x2

 4x1 + 5x2 ≤ 55
x1 + 3x2 ≤ 27

s.c.

 2x1 + x2 ≤ 20
x1 , x2 ≥ 0.


Mohamed BENDAOUD 19
Chapitre 1 1.3 Méthode graphique

La région réalisable du problème est donnée graphiquement par la Figure 1.7. 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 :

4x1 + 5x2 = 55
[BC] :
30/7 ≤ x1 ≤ 7, 5.

4x1 + 5x2 = 55
Tous les couples (x1 , x2 ) tels que sont des solutions optimales
30/7 ≤ x1 ≤ 7, 5
pour lesquelles la fonction objectif est maximale et vaut 550.

F IGURE 1.7 – Problème ayant une infinité de solutions maximales.

Exemple 1.3.7 Soit le programme linéaire suivant :

min z = −2x1 + 5x2


 4x1 + 5x2 ≥ 55
x1 + 3x2 ≤ 27

s.c.

 2x1 + x2 ≤ 20
x1 , x2 ≥ 0.


La région réalisable du problème est donnée graphiquement par la Figure 1.8.

La question qui se pose maintenant est : quels sont les couples (x1 , x2 ) de solutions
réalisables tels que z(x1 , x2 ) = −2x1 + 5x2 soit minimum ?

Pour tout nombre z, on note Dz la droite d’isovaleur de la fonction objectif d’équation

z = −2x1 + 5x2 ou encore x2 = 2/5x1 + z/5. Cette droite a pour coefficient directeur
2/5 et d’ordonnée à l’origine z/5.

Mohamed BENDAOUD 20
Chapitre 1 1.3 Méthode graphique

Lorsque z varie, ces droites Dz ayant même coefficient directeur sont parallèles entre
elles. L’ordonnée à l’origine des droites Dz est z/5. Minimiser z est équivalent à mi-
nimiser z/5. Le problème consiste donc à déterminer une ou plusieurs droites Dz qui
rencontrent la région réalisable et ayant une ordonnée à l’origine minimale.
La droite Dz qui rencontre la région réalisable et qui a une ordonnée à l’origine mini-
male est celle qui passe par le point A de coordonnées : x1 = 7, 5 et x2 = 5.
Ainsi, le programme linéaire a une seule solution minimale, le couple (7, 5; 5), pour
laquelle la fonction objectif est minimale et vaut z = −2x1 + 5x2 = 10.

F IGURE 1.8 – Problème à solution minimale unique.

Exemple 1.3.8 Soit le programme linéaire suivant :

min z = 20x1 + 25x2

 x1 + 5x2 ≥ 5
x1 + 2x2 ≥ 4

s.c.

 3x1 + 2x2 ≥ 6
x1 , x2 ≥ 0.


La région réalisable du problème est donnée graphiquement par la Figure 1.9.

Pour tout nombre z, on note Dz la droite d’isovaleur de la fonction objectif d’équa-
−5 z
tion z = 20x1 + 25x2 ou encore x2 = x1 + . Cette droite a pour vecteur directeur
→
− 4 25
v (−5/4, 1) et d’ordonnée à l’origine z/25.

La droite Dz qui rencontre la région réalisable et qui a une ordonnée à l’origine mini-
3
male est celle qui passe par le point C(1, ).
2
3
Ainsi, le programme linéaire a une seule solution minimale, le couple (1; ), pour
2
3 115
laquelle la fonction objectif est minimale et vaut z = 20 × 1 + 25 × = .
2 2

Mohamed BENDAOUD 21
Chapitre 1 1.3 Méthode graphique

F IGURE 1.9 – Problème à solution minimale unique.

Exemple 1.3.9 Soit le programme linéaire suivant :

maxz = 3x1 + 5x2

4x1 + 5x2 ≥ 55
s.c.
8x1 + 10x2 ≤ 50

La région réalisable du problème est vide, voir Figure 1.10. Ce programme n’a pas donc
de solution réalisable, et le problème est à solution impossible.

F IGURE 1.10 – Problème à solution impossible.

Mohamed BENDAOUD 22
Chapitre 1 1.4 Méthode du simplexe

Exemple 1.3.10 Soit le programme linéaire suivant :

maxz = 5x1 + x2
4x1 + 5x2 ≥ 55
s.c.
−5x1 + 7x2 ≥ 35

La région réalisable du problème est non bornée Figure 1.11, et la fonction objective est
alors non bornée.

F IGURE 1.11 – Problème à solution rejeté à l’infini.

La méthode graphique pour la résolution d’un problème linéaire à deux variables est
très facile à appliquer. Sa difficulté augmente par l’augmentation des variables dans le
système. Elle devient difficile pour trois variables et, voire impossible, au delà de trois
inconnus dans le système étudié.

Afin d’ôter la difficulté du fait que la méthode graphique est limitée à deux variables,
une méthode appelée méthode du simplexe a été développée afin de résoudre des pro-
blèmes de programmation linéaire avec plusieurs variables ; ceci ferra l’objet de la section
suivante.

1.4 Méthode du simplexe

L’algorithme du simplexe fut proposé en 1947 par Dantzig comme méthode de ré-
solution algébrique des programmes linéaires à plusieurs variables. La solution optimale
étant une solution de base (point extrême ou sommet de la région réalisable), la méthode
du simplexe est une méthode itérative et consiste à partir d’un sommet vers un sommet
adjacent de manière à améliorer la fonction objective à chaque itération jusqu’à aboutir à

Mohamed BENDAOUD 23
Chapitre 1 1.4 Méthode du simplexe

la solution optimale.

Le nombre des sommets pour un PL à n variables et m contraintes est de l’ordre

n!
m!(n−m)!
qui est assez grand pour m et n relativement grands. Le principe de la méthode
du simplexe propose de n’explorer qu’un nombre limité de sommets parmi lesqueles se
trouve à coup sûr la solution optimale.

L’algorithme du simplexe consiste à :

1. mettre le programme sous une forme standard,
2. déterminer une solution de base (ou bien détecter l’impossibilité),
3. faire subir un test d’optimalité à cette solution de base pour déterminer s’il s’agit
ou non de la solution optimale,
- s’il s’agit de la solution optimale, le problème est terminé,
- s’il ne s’agit pas de la solution optimale, on passe à l’étape 4.,
4. changer de solution de base puis reprendre la procédure au 3. jusqu’à l’obtention
de la solution optimale (ou bien détecter une fonction objectif non bornée).
Chaque changement de solution de base constitue une itération.

Nous présenterons dans cette section une résolution analytique en détaillant deux pro-
cédures : méthode (ou algorithme) Simplexe et tableaux Simplexe.

1.4.1 Algorithme du Simplexe

Exemple 1.4.1
1. Enoncé :
Une usine fabrique des bureaux sous forme standard ou luxe. Des études de mar-
ché ont montré que pour l’année à venir, les possibilités de vente s’élève à 400
unités pour le modèle standard. L’approvisionnement en bois est suffisant pour
fabriquer annuellement 500 bureaux quel que soit le type. Par ailleurs, le temps
de fabrication d’un modèle luxe est le double de celui d’un bureau de modèle
standard. La capacité annuelle de fabrication est telle que, si tous les bureaux fa-
briqués étaient de type standard, on pourrait en fabriquer 700 au maximum. La
vente d’un bureau sous le modèle luxe conduit à une marge unitaire sur coût va-
riable égale à 7, celle d’un bureau de type standard égale à 5. On se propose de
rechercher le programme annuel de fabrication conduisant au profit global maxi-
mum.
2. Mise en équation :
Soit x1 le nombre de bureaux de type luxe, x2 le nombre de bureaux de type stan-
dard. Le programme linéaire est

maxz = 7x1 + 5x2


 x2 ≤ 400
x1 + x2 ≤ 500

s.c.

 2x1 + x2 ≤ 700
x1 , x2 ≥ 0.


Mohamed BENDAOUD 24
Chapitre 1 1.4 Méthode du simplexe

3. Région réalisable :

4. Forme standard :
On introduit les variables d’écart ei avec i ∈ {1, 2, 3} positives ou nulles.

maxz = 7x1 + 5x2


 x2 + e1 = 400
x1 + x2 + e2 = 500

s.c.

 2x1 + x2 + e3 = 700
x1 , x2 , e1 , e2 , e3 ≥ 0.


5. Variables hors-base, variable dans la base :

Toute solution de base comporte deux catégories de variables.
- Des variables ayant une valeur prédéterminée nulle : ces variables nulles sont
dites variables hors base VHB (ou variables exclues).
- Des variables ayant une valeur non nulle : ce sont les variables dans la base
VDB (ou variables retenues).

Pour amorcer l’algorithme du simplexe, il est nécessaire de connaître une solution

de base.

La solution de base de départ de l’usine consiste à ne rien produire : x1 =

x2 = 0. Ces variables x1 et x2 qui sont nulles sont hors-base. Dans ce cas,
e1 = 400, e2 = 500 et e3 = 700. Les variables e1 , e2 et e3 non nulles sont dans
la base. Cette solution conduit au sommet O(0, 0) pour lequel la fonction écono-
mique vaut z(0, 0) = 7 × 0 + 5 × 0 = 0.

Mohamed BENDAOUD 25
Chapitre 1 1.4 Méthode du simplexe

Tableau initial : x1 et x2 sont des VHB, et e1 , e2 et e3 sont des VDB.

VDB x1 x2 e1 e2 e3 constante
e1 0 1 1 0 0 400
e2 1 1 0 1 0 500
e3 2 1 0 0 1 700
z 7 5 0 0 0 0

6. Première itération :
La solution de base de départ consiste à ne rien produire soit x1 = x2 = 0. On
étudie ensuite, à partir de cette solution, jusqu’à quel niveau on peut porter x1 ou
x2 conformément aux contraintes de façon à accroître au maximum le profit. Il se
pose le problème du choix de la variable x1 ou x2 qui va passer de la valeur 0 à
une valeur strictement positive. La variable choisie sera appelée variable entrante.
- Critère de sélection de la variable entrante :
Cette sélection doit s’accompagner d’une augmentation de la fonction écono-
mique
z(x1 , x2 ) = 7x1 + 5x2 .
La sélection portera sur x1 qui par unité rapporte le plus. Cette règle est ap-
pelée règle du plus grand gain marginal :
Le critère de sélection de Dantzig de la variable entrante consiste, dans la
fonction économique exprimée exclusivement en fonction des variables
hors-base, à sélectionner la variable affectée du coefficient strictement
positif le plus élevé.
- On exprime ensuite e1 , e2 , e3 et z en fonction des variables hors-base x1 et x2 :


 e1 = 400 − x2
e2 = 500 − x1 − x2


 e 3 = 700 − 2x1 − x2
z = 7x1 + 5x2 .


La variable x2 reste hors-base donc nulle, la variable x1 entre en base. On

reporte x2 = 0 dans ce système, on obtient :


 e1 = 400
e2 = 500 − x1


 e3 = 700 − 2x1
z = 7x1 .


On cherche jusqu’à quel niveau il est possible de porter x1 , de façon compa-

tible avec les contraintes e1 ≥ 0, e2 ≥ 0 et e3 ≥ 0. Les contraintes de positivité
donnent
x1 ≤ 500 et x1 ≤ 350.
La valeur maximale prise par x1 est donc 350. On remplace x1 par 350 dans
le système et on obtient

e1 = 400, e2 = 150, e3 = 0 et z(350, 0) = 2450.

Mohamed BENDAOUD 26
Chapitre 1 1.4 Méthode du simplexe

La variable e3 est devenue nulle, elle est sortie de la base, e3 est appelée va-
riable sortante. Les variables x1 et e3 ont permuté.

On exprime le programme standard en fonction des nouvelles variables hors-

base x2 et e3 (on peut utiliser la méthode du pivot de Gauss, pour obtenir
le nouveau système, ici, on divise le coefficient de x1 par 2 dans la troisième
contrainte et on remplace x1 par 350 − 1/2x2 − 1/2e3 dans les deux autres) :

 

 x2 + e1 = 400 
 e1 = 400 − x2
x1 + x2 + e 2 = 500 e2 = 500 − (350 − 12 x2 − 12 e3 ) − x2
 
⇔

 2x 1 + x 2 + e 3 = 700 
 x1 = 350 − 12 x2 − 12 e3
1 1
z = 7x1 + 5x2 .  z = 7(350 − 2 x2 − 2 e3 ) + 5x2 .
 

 x2 + e1 = 400
 1 1
x
2 2
+ e2 − e
2 3
= 150
⇔ 1 1

 x1 + 2 x2 + 2 e 3 = 350
z = 32 x2 − 27 e3 + 2450.


On exprime ce nouveau programme à l’aide d’un second tableau. Pour l’obtenir,

on remplace impérativement dans le premier tableau la variable e3 par la variable
x1 (x1 et e3 ont permuté) et ceci dans la colonne VDB.

VDB x1 x2 e1 e2 e3 cste
e1 0 1 1 0 0 400
e2 0 1/2 0 1 -1/2 150
x1 1 1/2 0 0 1/2 350
z 0 3/2 0 0 -7/2 - 2450
On a pris la colonne des VDB du premier tableau et on y a remplacé e3 par x1 .
Pour la fonction économique z, le coefficient constant 2450 est affecté impérative-
ment du signe "-" et on place −2450.
Cette itération conduit au sommet A1 (350, 0) pour lequel la fonction économique
vaut 2450.
7. Deuxième itération :

- Sélection de la variable entrante :

3 7
z = x2 − e3 + 2450.
2 2
On sélectionne x2 ; en effet, toute augmentation de e3 provoquerait une dimi-
nution de la fonction économique z.
- Sélection de la variable sortante :
la variable e3 reste hors-base donc nulle, on remplace e3 par 0 dans le système
précédent, on obtient
1 1
e1 = 400 − x2 ≥ 0, e2 = 150 − x2 ≥ 0 et x1 = 350 − x2 ≥ 0.
2 2

Mohamed BENDAOUD 27
Chapitre 1 1.4 Méthode du simplexe

Les contraintes de positivité imposent

x2 ≤ 400, x2 ≤ 300 et x2 ≤ 700.

Jusqu’à quel niveau peut-on porter x2 ? La valeur maximale prise par x2 est
300. Dans ce cas,
e1 = 100, e2 = 0 et x1 = 200.
La variable sortante est e2 .

Les variables hors-base sont alors e2 et e3 , les variables dans la base sont x1 , x2
et e1 . Cette itération conduit au sommet A2 (200, 300) pour lequel la fonction éco-
nomique vaut 2900.

x2 et e2 ont permuté. On exprime les variables dans la base en fonction des nou-
velles variables hors-base e2 et e3 :
 

 x 2 + e1 = 400 
 e1 = 400 − (300 − 2e2 + e3 )
x1 + x2 + e2 = 500 x1 = 200 + e2 − e3
 
⇔

 2x1 + x2 + e3 = 700 
 x2 = 300 + 2e2 − e3
z = 7x1 + 5x2 .  z = 7(200 + e2 − e3 ) + 5(300 + 2e2 − e3 ).
 

 e1 − 2e2 + e3 = 100
x2 + 2e2 − e3 = 300

⇔

 x 1 − e 2 + e3 = 200
z = −3e2 − 2e3 + 2900.


On obtient le troisième tableau suivant :

VDB x1 x2 e1 e2 e3 cste
e1 0 0 1 -2 1 100
x2 0 1 0 2 -1 300
x1 1 0 0 -1 1 200
z 0 0 0 -3 -2 - 2900
On a pris la colonne des VDB du deuxième tableau et on y a remplacé e2 par x2 .
Pour la fonction économique z, le coefficient constant 2900 est affecté du signe "-"
et on place −2900.

Conclusion :
z = 2900 − 3e2 − 2e3 ,
e2 et e3 sont hors-base donc nulles, toute augmentation de e2 ou e3 entraîne une
diminution de z. Il n’est plus possible d’améliorer la fonction économique, la so-
lution (x1 = 200, x2 = 300) est la solution optimale.
On interprète les résultats de la manière suivante :
• x1 = 200 bureaux de modèle luxe,
• x2 = 300 bureaux de modèle standard,
• e1 = 100, il reste une possibilité de fabriquer 100 bureaux de modèle standard,

Mohamed BENDAOUD 28
Chapitre 1 1.4 Méthode du simplexe

• e2 = 0, tout le bois disponible est utilisé,

• e3 = 0, tout le temps disponible est utilisé.
z est maximum pour x1 = 200, x2 = 300 et vaut 2900.

Le coefficient δxj de la ligne z correspondant à la variable xj s’appelle le coût

réduit de xj et mesure la contribution nette de xj dans la valeur de z lorsque xj
devient une VDB. Par exemple δe2 = −3 signifie qu’une augmentation de e2 d’une
unité supplémentaire vaut une augmentation de z de 3.
Il est facile de voir que, dans le cas général d’un PL sous forme standard

maxz = ct x
Ax = b
s.c.
x ≥ 0,
on a
δxj = cj − zj , ∀j = 1, 2, ..., n,
m
X
où zj = ci aij est appelé le coût fictif (ou d’opportunité) associé à la variable
i=1
correspondante j.

1.4.2 Tableaux Simplexe

Afin de systématiser et de simplifier les calculs, la procédure de la méthode du sim-
plexe présentée dans la section ci-dessus peut être présentée sous forme de tableaux. Un
tableau correspond à une solution de base et une itération représente une modification du
tableau.
1. Tableau initial :

VDB x1 x2 e1 e2 e3 cste
e1 0 1 1 0 0 400
e2 1 1 0 1 0 500
e3 2 1 0 0 1 700
z 7 5 0 0 0 0
x1 = x2 = 0 représente le sommet origine et z = 0. On a de plus, e1 = 400,
e2 = 500 et e3 = 700.
On sélectionne dans la fonction économique z = 7x1 + 5x2 la variable affectée du
coefficient strictement positif le plus grand (le plus grand coût réduit). La variable
x1 entre en base. Quelle est la variable sortante ?
On considère la colonne RT (ratio test) obtenue en divisant les coefficients constants
par la colonne des coefficients de la variable x1 qui entre en base.

x1 constante RT
e1 0 400 400/0 = +∞
e2 1 500 500/1 = 500
e3 2 700 700/2 = 350.

Mohamed BENDAOUD 29
Chapitre 1 1.4 Méthode du simplexe

On sélectionne dans cette colonne le plus petit nombre strictement positif 350. La
variable e3 sort de la base. Les deux variables x1 et e3 ont permuté. La colonne de
la variable entrante x1 s’appelle la colonne pivot, et la ligne de la variable sortante
e3 s’appelle la ligne pivot. L’intersection de la colonne pivot et de la ligne pivot
s’appelle le pivot et est égal à 2.
2. Deuxième tableau :
Impérativement dans la colonne des variables dans la base du tableau initial, on
remplace la variable e3 qui sort de la base par la variable x1 qui entre en base, on
recopie les autres variables d’où la disposition du second tableau

VDB x1 x2 e1 e2 e3 cste
e1
e2
x1
z

Comment remplit-on le tableau ?

On utilise la méthode du pivot de Gauss pour remplir le nouveau tableau. On divise
la ligne pivot Lp par le pivot a = 2,
1
Lp 1 1/2 0 0 1/2 350
2
et on recopie cette nouvelle ligne dans la ligne Lx1 :

L x1 1 1/2 0 0 1/2 350

On doit exprimer le programme en fonction des nouvelles variables hors-base x2

et e3 . Par une combinaison linéaire de la ligne Lp et des autres lignes, on élimine
la variable x1 qui est entrée en base :
• Pour la ligne Le1 ,

x1 x2 e1 e2 e3 cste
Le1 0 1 1 0 0 400
1
Lp 1 1/2 0 0 1/2 350
2
1
Le1 − 0 × Lp 0 1 1 0 0 400
2
On recopie cette nouvelle ligne Le1 :

x2 + x3 = 400.

• Pour la ligne Le2 ,

x1 x2 e1 e2 e3 cste
Le2 1 1 0 1 0 500
1
Lp 1 1/2 0 0 1/2 350
2
1
Le2 − 1 × Lp 0 1/2 0 1 -1/2 150
2

Mohamed BENDAOUD 30
Chapitre 1 1.4 Méthode du simplexe

On recopie cette nouvelle ligne Le2 :

1 1
x2 + e2 − e3 = 150.
2 2
• Pour la ligne de la fonction économique Lz ,
x1 x2 e1 e2 e3 cste
Lz 7 5 0 0 0 0
1
Lp 1 1/2 0 0 1/2 350
2
1
Lz − 7 × Lp 0 3/2 0 0 -7/2 - 2450
2
d’où la fonction économique exprimée en fonction des variables hors-base :
3 7
z = x2 − e3 + 2450.
2 2
On obtient donc le second tableau :
VDB x1 x2 e1 e2 e3 cste
e1 0 1 1 0 0 400
e2 0 1/2 0 1 -1/2 150
x1 1 1/2 0 0 1/2 350
z 0 3/2 0 0 -7/2 - 2450
On a x2 = e3 = 0. Comme x1 = 350, on atteint le sommet A1 (350, 0) et
z = 2450. On a de plus, e1 = 400 et e2 = 150.
3. Troisième tableau :
3 7
z = x2 − e3 + 2450.
2 2
La variable entrante est x2 (toute augmentation de e3 entraîne une diminution de
z). Déterminons la variable sortante : la colonne RT est donnée par
x2 constante RT
e1 1 400 400/1 = 400
e2 1/2 150 150/(1/2) = 300
x1 1/2 350 700/(1/2) = 700.
On sélectionne dans cette colonne RT le coefficient strictement positif le plus petit
c.-à-d., 300, la variable e2 sort de la base. Les variables x2 et e2 ont permuté. Le
1
pivot est , il est situé à l’intersection de la colonne x2 et de la ligne e2 .
2
On remplit le troisième tableau : dans la colonne des VDB du deuxième tableau,
on remplace la variable e2 qui sort de base par la variable x2 qui entre en base. On
1 Lp
divise la ligne pivot Lp par Le pivot , et on recopie la ligne 1 = 2LP dans la
2 2
ligne Lx2 :
VDB x1 x2 e1 e2 e3 cste
e1
x2 0 1 0 2 -1 300
x1
z

Mohamed BENDAOUD 31
Chapitre 1 1.4 Méthode du simplexe

Par des combinaisons avec la ligne pivot, on exprime le système en fonction des
variables hors-base e2 et e3 , c.-à-d., qu’on élimine la variable x2 qui est entrée en
base :
• Pour la ligne Le1 ,

x1 x2 e1 e2 e3 cste
Le1 0 1 1 0 0 400
2Lp 0 1 0 2 -1 300
Le1 − 1 × 2Lp 0 0 1 -2 1 100
• Pour la ligne Lx1 ,

x1 x2 e1 e2 e3 cste
Lx1 1 1/2 0 0 1/2 350
2Lp 0 1 0 2 -1 300
L x1 − (1/2) × 2Lp 1 0 0 -1 1 200
• Pour la ligne Lz ,
x1 x2 e1 e2 e3 cste
Lz 0 3/2 0 0 -7/2 -2450
2Lp 0 1 0 2 -1 300
3
Lz − × 2Lp 0 0 0 -3 -2 - 2900
2
On obtient donc le troisième tableau suivant :
VDB x1 x2 e1 e2 e3 cste
e1 0 0 1 -2 1 100
x2 0 1 0 2 -1 300
x1 1 0 0 -1 1 200
z 0 0 0 -3 -2 - 2900
Conclusion :
La fonction économique s’écrit z = 2900 − 3e2 − 2e3 ; où e2 et e3 sont les
variables hors-base donc nulles. Toute augmentation de e2 et e3 conduit à une
diminution de z. Donc x1 = 200, x2 = 300, e1 = 100, e2 = 100 et z = 2900.
La fonction économique atteint son maximum au point A2 (200, 300) et vaut
2900.

Remarque 1.4.2
1. Le tableau simplexe ne prend en compte que les variables positives x ≥ 0.
Si par exemple l’une des variables xi est ≤ 0 (resp. quelconque) on procède au
−
changement xi = −x0i avec x0i ≥ 0 (resp. xi = x+ i − xi ).
Aussi si par exemple −3x1 + 2x2 ≥ −2 est une contrainte à second membre
négatif, on peut la modifier avant de mettre le programme sous forme standard, et
la réécrire comme suit : 3x1 − 2x2 ≤ 2.
2. La présence d’un zéro dans la ligne pivot entraîne l’invariance de la colonne cor-
respondante.

Mohamed BENDAOUD 32
Chapitre 1 1.4 Méthode du simplexe

3. La présence d’un zéro dans la colonne du pivot entraîne l’invariance de la ligne

correspondante. On peut donc, sans effectuer de calculs, remplir certaines cases
du tableau.
4. Si à une itération donnée, par exemple, la fonction objective s’écrit

z = axi + bxj + c

avec a = 0 et b < 0, alors la variable xi peut entrer dans VDB et donner une
nouvelle solution (un autre sommet Ak+1 ) sans changer la valeur de la fonction
objective, c.-à-d., z est maximum pour deux sommets adjacents Ak et Ak+1 . Dans
ce cas, la fonction économique atteint son maximum en tous les points du segment
[Ak Ak+1 ], et en particulier la solution n’est pas unique.
5. Si touts les ratio test sont négatifs ou infinis, c.-à-d., la colonne RT ne donne
aucune valeur positive non infinie, alors on arrive pas à sélectionner la variable
sortante. Dans ce cas la variable entrante peut augmenter indéfiniment, et la fonc-
tion objectif z est non bornée.
6. Si à une certaine itération, la solution de base est dégénérée, c.-à-d., le sommet
correspondant Ak admet une composante (ou variable) de base nulle, alors on
peut avoir dans l’itération subséquente la même solution de base, c.-à-d., Ak+1 =
Ak : c’est le phénomène de cyclage qui peut empêcher l’algorithme de converger.
(Si un tel cas se produit pendant plusieurs itérations successives, il est possible
de retrouver une base déjà obtenue précédemment et, à partir de là, de cycler
indéfiniment sur une même séquence de bases).
7. On montre que si toutes les solutions de base produites par l’algorithme du sim-
plexe sont non dégénérées, alors l’algorithme du simplexe converge en un nombre
fini d’itérations.

Remarque 1.4.3 Si deux coefficients positifs dans la fonction économique sont égaux, on
pourra déterminer dans chaque colonne correspondante le pivot éventuel et le rapport
(ratio test) associé. On choisira comme pivot celui qui correspond au plus grand rapport
(ratio test).

Exemple 1.4.4 Si à une certain itération on a, par exemple, le tableau suivant

VDB x1 x2 e1 e2 e3 cste
e2 3 5 1 1 0 150
e3 1 4 2 0 1 80
z 2 2 1 0 0 - 2000

Si l’on choisit comme variable entrante x1 , la colonne RT est alors

x1 constante RT
e2 3 150 150/1 = 50
e3 1 80 80/1 = 80

La variable sortante est e2 , le pivot est égal à 3, le rapport vaut 50.

Mohamed BENDAOUD 33
Chapitre 1 1.4 Méthode du simplexe

Si l’on choisit comme variable entrante x2 , la colonne RT est alors

x2 constante RT
e2 5 150 150/1 = 30
e3 4 80 80/1 = 20

La variable sortante est e3 , le pivot est égal à 4, le rapport vaut 20.

On choisit comme variable sortante celle qui correspond au plus grand rapport. Dans
l’exemple, 50 > 20, la variable sortante est e2 , la variable entrante x1 , le pivot est 3.

Remarque 1.4.5
La règle d’entrée du plus grand gain marginal nous propose une méthode qui permet
d’obtenir la valeur optimale de z, mais rien n’indique que cette méthode propose le plus
court chemin.
Exemple 1.4.6 Il est facile de voir que la règle du plus grand gain marginal appliquée
au programme standard suivant :

maxz = 4x1 + 2x2 + x3


 x1 + x4 =5
4x1 + x2 + x5 = 25

s.c.

 8x1 + 4x2 + x3 + x6 = 125
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.


conduit au chemin 0A1 A2 A3 A4 A5 A6 A7 de coordonnées respectives (0, 0, 0), (5, 0, 0),

(5, 5, 0), (0, 25, 0), (0, 25, 25), (5, 5, 65), (5, 0, 85), (0, 0, 125), et que au 7ème itération,
la fonction économique s’écrit :

z = −4x1 − 2x2 − x6 + 125,

et les variables hors-base x1 , x2 et x6 sont affectées de coefficients négatifs, donc z atteint

son maximum au point A7 (0, 0, 125) et vaut 125.

Retour sur le tableau initial :

VDB x1 x2 x3 x4 x5 x6 cste RT
x4 1 0 0 1 0 0 5 +∞
x5 4 1 0 0 1 0 25 +∞
x6 8 4 1 0 0 1 125 125
z 4 2 1 0 0 0 0

Si on n’utilise pas la règle du plus grand gain marginal et si on décide de faire entrer x3
en base, x6 sort de base et le pivot est 1 :

VDB x1 x2 x3 x4 x5 x6 cste
x4 1 0 0 1 0 0 5
x5 4 1 0 0 1 0 25
x3 8 4 1 0 0 1 125
z -4 -2 0 0 0 -1 -125

Mohamed BENDAOUD 34
Chapitre 1 1.4 Méthode du simplexe

Les variables hors-base x1 , x2 et x6 sont affectées de coefficients négatifs, z atteint son

maximum au point A7 (0, 0, 125) et vaut 125. Le résultat est cette fois-ci atteint en une
seule itération à l’aide de ce qu’on appelle la règle du plus petit gain marginal. Il convien-
dra de choisir alors parmi les deux règles proposées afin de minimiser les temps de cal-
culs.

1.4.3 Détérmination d’une solution de base admissible

On considère l’exemple suivant :

Exemple 1.4.7 Soit le PL

maxz = 3x1 − 2x2


 x1 − x2 = 20
−x1 + 2x2 ≤ 40

s.c.

 x 1 ≥ 30
x1 , x2 ≥ 0.


1) Dessinez la région réalisable de ce PL, puis résoudre ce PL par la méthode d’énu-

mération.
2) Résoudre ce PL par la méthode du simplexe.

Solution : 1) La région réalisable du problème est donnée graphiquement par la Fi-

gure 1.12 ci-dessous qui est le segment [AB]. Cette région réalisable n’a que deux som-
mets à savoir A(30, 10) et B(80, 60) pour lesquels la fonction objective vaut zA = 70 et
zB = 120, respectivement. Ainsi, par la méthode d’énumération, la solution optimale est
(80, 60) pour laquelle la fonction objective vaut z = 120.

F IGURE 1.12 – Problème à région réalisable ne contenant pas l’origine.

Mohamed BENDAOUD 35
Chapitre 1 1.4 Méthode du simplexe

2) Ce programme s’écrit sous sa forme standard comme :

maxz = 3x1 − 2x2


 x1 − x2 = 20
−x1 + 2x2 + e1 = 40

s.c.

 x1 − e2 = 30
x1 , x2 , e1 , e2 ≥ 0.


On remarque qu’il n’existe pas de base naturelle évidente pour amorcer les calculs puisque
si x1 = x2 = 0, la première contrainte n’est pas vérifiée, de plus la troisième contrainte
entraine que e2 = −30 < 0 ; ce qui contredit la de non-négativité des variables.
C’est pourquoi une procédure plus méthodique consiste :

1. A introduire dans chaque contrainte k qui pose problème une variable artificielle
ak affectée d’un coefficient égal à 1.
2. A infliger à chaque variable artificielle une pénalité sous la forme d’un coefficient
négatif (dans le cas d’un problème de maximisation) et de valeur absolue très élevée
−G dans la fonction économique originelle.

Ainsi, l’introduction de variables artificielles permet de déterminer simplement une

base, certes artificielle, mais admissible pour amorcer l’algorithme. Les pénalités ont pour
objet de provoquer l’élimination des variables artificielles au fil des itérations. La méthode
consiste donc ensuite
3. A retenir comme solution de base initiale la base artificielle telle que :
- toutes les variables artificielles sont en base (c.-à-d., non nulles) ;
- toutes les autres variables des contraintes où figurent des variables artificielles (réelles
et d’écart) sont hors base (c.-à-d., nulles).
4. A appliquer l’algorithme du simplexe jusqu’à ce que toutes les variables artificielles
soient supprimées.

Dans le cas étudié, après introduction des variables artificielles a1 et a2 respectivement

dans la première et la troisième contrainte, le problème s’écrit :

maxz = 3x1 − 2x2 − Ga1 − Ga2


 x 1 − x 2 + a1 = 20
−x1 + 2x2 + e1 = 40

s.c.

 x 1 − e 2 + a 2 = 30
x1 , x2 , e1 , e2 , a1 , a2 ≥ 0.


En substituant a1 = 20 − x1 + x2 et a2 = 30 − x1 + e2 dans la fonction objectif, on

obtient z = (3 + 2G)x1 + (−2 − G)x2 − Ge2 − 50G. Les tableaux ci-dessous montrent
qu’après deux itérations, une solution de base admissible est obtenue.

VDB x1 x2 e1 e2 a1 a2 cste RT
a1 1 -1 0 0 1 0 20 20
e1 -1 2 1 0 0 0 40 -40
a2 1 0 0 -1 0 1 30 30
z 3 + 2G -2 -G 0 -G 0 0 50G

Mohamed BENDAOUD 36
Chapitre 1 1.4 Méthode du simplexe

VDB x1 x2 e 1 e2 a1 a2 cste RT
x1 1 -1 0 0 1 0 20 -20
e1 0 1 1 0 1 0 60 60
a1 0 1 0 -1 -1 1 10 10
z 0 1+G 0 -G -3 - 2G 0 -60 + 10G
VDB x1 x2 e1 e2 a1 a2 cste RT
x1 1 0 0 -1 0 1 30 -30
e1 0 0 1 1 2 -1 50 50
x2 0 1 0 -1 -1 1 10 -10
z 0 0 0 1 -2 - G - 1 - G -70
Ainsi, les variables artificielles a1 et a2 sont hors base et une solution de base admis-
sible est obtenue : x1 = 30, x2 = 10, e1 = 50 et e2 = 0. Cette solution de base n’est plus
artificielle mais réelle.
Les couts réduits des variables artificielles a1 et a2 sont négatifs et de valeurs absolus
très grands, donc elles ne pourront pas être sélectionnées ultérieurement. Par suite, on peut
supprimer du tableau les colonnes correspondants à a1 et a2 et poursuivre la procédure
jusqu’à l’obtention de l’optimum.

VDB x1 x2 e1 e2 cste
x1 1 0 1 0 80
e2 0 0 1 1 50
x2 0 1 1 0 60
z 0 0 -1 0 -120
Le tableau ci-dessus est alors optimale, la solution optimale est x1 = 80 et x2 = 60
pour laquelle la fonction objective est maximale et vaut z = 120.

Remarque 1.4.8 Si le tableau final du simplexe appliqué au programme PLG (contenant

la variable G) comporte un ou plusieurs ai > 0, alors le programme initial PL n’a pas de
solutions de base réalisables et donc n’a pas pas de solutions réalisables.
En effet : Si PL possède une solution de base réalisable, le G supposé assez grand aurait
fait sortir tous les ai > 0 de la base en les posant égal à zéro.

1.4.4 Utilisation de la méthode du simplexe dans un problème de mi-

nimisation
Les tableaux du simplexe s’appliquent aux problèmes de minimisation de la même
manière expliquée dans la section précédente pour les problèmes de maximisation. La
seule différence c’est que la variable entrante est celle à laquelle on associe le plus petit
coefficient strictement négative de la ligne z de la fonction objective (des coûts réduits).
De telle choix va nous amener à changer la règle d’arrêt de la procédure du simplexe et
de définir le tableau optimal comme celui où tous les coefficients de la ligne z (les coûts
réduits) sont positifs ou nuls.

Mohamed BENDAOUD 37
Chapitre 1 1.4 Méthode du simplexe

Exemple 1.4.9 On considère le PL suivant

minz = −2x1 + x2
 x1 − 3x2 ≥ −1
s.c. x1 − x2 ≤ 1
x1 , x2 ≥ 0.


qui s’écrit sous forme standard

minz = −2x1 + x2
 −x1 + 3x2 + e1 = 1
s.c. x1 − x2 + e2 =1
x1 , x2 , e1 , e2 ≥ 0.


En appliquons l’algorithme du simplexe à cet exemple et en partant de la solution de

base (x1 , x2 ) = (0, 0), on obtient les tableaux successifs suivants :
VDB x1 x2 e1 e2 cste RT
e1 -1 3 1 0 1 -1
e2 1 -1 0 1 1 1
z -2 1 0 0 0

VDB x1 x2 e1 e2 cste RT
e1 0 2 1 1 2 1
x1 1 -1 0 1 1 -1
z 0 -1 0 2 2
VDB x1 x2 e1 e2 cste
x2 0 1 1/2 1/2 1
x1 1 0 1/2 3/2 2
z 0 0 1/2 3/2 3
L’algorithme s’arrête, la solution optimale est x1 = 2 et x2 = 1 pour laquelle la fonction
objective vaut z = −3.

On peut aussi transformer ce problème de minimisation en problème de maximisation

en utilisant le fait que
min z = − max(−z).
Le PL ci-dessus de minimisation devra donc être transformé en un problème de maxi-
misation soit
max(−z)
 = 2x1 − x2
 1 3x2 ≥ −1
x −
s.c. x1 − x2 ≤ 1
x1 , x2 ≥0


qui s’écrit sous forme standard

max(−z)
 = 2x1 − x2
 x1 − 3x2 − e1 = −1
s.c. x1 − x2 + e2 = 1
x1 , x2 , e1 , e2 ≥ 0.


Mohamed BENDAOUD 38
Chapitre 1 1.5 Dualité

Il n’est pas nécessaire de réécrire la première contrainte sous forme −x1 + 3x2 + e2 = 1
afin d’avoir le second membre positive.
En appliquons l’algorithme du simplexe à cet exemple et en partant de la solution de
base (x1 , x2 ) = (0, 0), on obtient les tableaux successifs suivants :
VDB x1 x2 e1 e2 cste RT
e1 1 -3 -1 0 -1 -1
e2 1 -1 0 1 1 1
-z 2 -1 0 0 0
VDB x1 x2 e1 e2 cste RT
e1 0 -2 -1 -1 -2 1
x1 1 -1 0 1 1 -1
-z 0 1 0 -2 -2
VDB x1 x2 e1 e2 cste
x2 0 1 1/2 1/2 1
x1 1 0 1/2 3/2 2
-z 0 0 -1/2 -5/2 -3
L’algorithme s’arrête, la solution maximale est −z = 3 si x1 = 2 et x2 = 1. La solution
minimale sera donc z = −3 si x1 = 2 et x2 = 1.

Exercice. Résoudre par la méthode du simplexe le PL suivant :

maxz = 2x1 + x2 − x3
 x1 + x 2 ≤ 20
s.c. −2x2 + x3 ≥ −10
x1 , x2 ≥ 0.


Solution. Le PL s’écrit sous sa forme standard :

maxz = 2x1 + x2 − x3
 x1 + x2 + e1 = 20
s.c. 2x2 − x3 + e2 = 10
x1 , x2 , e1 , e2 ≥ 0.


En appliquons l’algorithme du simplexe à cet exemple et en partant de la solution de base

(x1 , x2 , x3 ) = (0, 0, 0), on obtient les tableaux successifs suivants :
VDB x1 x2 x3 e1 e2 cste RT
e1 1 2 0 1 0 20 20
e2 0 2 -1 0 1 10 +∞
z 2 1 -1 0 0 0
VDB x1 x2 x3 e1 e2 cste RT
x1 1 2 0 1 0 20
e2 0 2 -1 0 1 10
z 0 -3 -1 -2 0 -40
L’algorithme s’arrête, la solution optimale est (x1 , x2 , x3 ) = (20, 0, 0) pourlaquelle la
fonction objective vaut z = 40.

Mohamed BENDAOUD 39
Chapitre 1 1.5 Dualité

1.5 Dualité
La dualité est un concept fondamental en programmation linéaire et conduit à des
résultats de grande portée théorique et pratique.

1.5.1 Définition et exemples

Soit le PL sous forme canonique suivant :

maxz = ct x
Ax ≤ b
s.c.
x ≥ 0,
Supposons, par exemple, que ce PL est issu d’un problème de production pour une
entreprise E1 , fabricant n biens j, j ∈ {1, ..., n} et faisant intervenir m ressources i,
i ∈ {1, ..., m}, qui veut maximaliser son profit z sachant la disponibilité bi pour chaque
ressource i et le profit unitaire cj pour chacun des biens j. Alors le PL s’écrit
n
X
max z = cj x j
 nj=1
 X
 aij xj ≤ bi ; i = 1, 2, ..., m
s.c. j=1

xj ≥ 0, j = 1, 2, ..., n


Soit E2 une autre entreprise, en rupture de stock, veut racheter les ressources de l’en-
treprise E1 . A quels prix doit-elle le faire pour tout racheter au coût w minimum ?
On note yi le prix de la ressource i. E2 doit fixer les yi de manière à ce que
m
X
aij yi ≥ cj ; j = 1, 2, ..., n.
i=1

En effet, pour tout j, cela garantit que E1 a intérêt à vendre les ressources nécessaires
pour produire une unité de j plutôt que de la produire. D’où le programme mathématique
suivant auquel se trouve confronté E2 .
m
X
min w = bi y i
 m i=1
 X a y ≥ c ; j = 1, 2, ..., n

ij i j
s.c. i=1

 yi ≥ 0, i = 1, 2, ..., m

qui s’écrit sous forme canonique

min w = bt y
At y ≥ c
s.c.
y ≥ 0.
Ce deuxième PL s’appelle le PL dual du premier, et le premier s’appelle le PL primal.

Mohamed BENDAOUD 40
Chapitre 1 1.5 Dualité

On voit aisément que les contraintes du PL dual impliquent que

n
X m
X
z= cj x j ≤ bi yi = w,
j=1 i=1

et par suite
max z ≤ min w. (1)
Intuitivement on voit que le minimum atteint par le dual doit être égal au maximum
du primal. La théorie montre que c’est le cas quand le problème a des solutions. Dans ce
cas, résoudre le primal est équivalent à résoudre le dual, et parfois, il est plus simple de
résoudre le dual que de résoudre le primal.

Exemple 1.5.1

Primal
Dual
maxz = x1 + 3x2
minw = 14y1 + 12y2 + 12y3
x1 + x2 ≤ 14
 y1 − 2y2 + 2y3 ≥ 1


−2x1 + 3x2 ≤ 12

s.c. s.c. y1 + 3y − y3 ≥3
2x1 − x2 ≤ 12
y1 , y2 , y3 ≥ 0.

 
x1 , x2 ≥ 0.


Remarque 1.5.2 En général le primal n’est pas sous sa forme canonique. En écrivant le
primal sous forme canonique avant de déterminer son dual, on obtient le tableau suivant
qui résume toutes les situations possibles pour les correspondances primal/dual :

Maximisation ←→ Minimisation
Nombre de variables Nombre de contraintes
Nombre de contraintes Nombre de variables
Matrice A Matrice At
Membre de droite b Membre de droite c
Fonction objective max c x Fonction objective min bt y
t

ième contrainte ≥ ième variable yi ≤ 0

≤ ≥0
= yi ∈ R
jème variable xj ≥ 0 jème contrainte ≥
xj ≤ 0 ≤
xj ∈ R =

Exemple 1.5.3

Primal
Dual
maxz = 2x1 − 3x2
minw = 12y1 − 8y2 + 16y3
2x1 + x2 ≥ 12
 2y1 − 4y2 + y3 ≥ 12


−4x1 + 3x2 ≤ −8

s.c. s.c. y1 + 3y + y3 =9
x1 + x2 = 16
y1 ≤ 0, y2 ≥ 0, y3 ∈ R.

 
x1 ≥ 0, x2 ∈ R.


Mohamed BENDAOUD 41
Chapitre 1 1.5 Dualité

Exemple 1.5.4
Primal
Dual
min z = −2x1 + 9x2
maxw = 10y1 + 8y2 − 6y3
3x1 + x2 ≥ 10
 3y1 + 4y2 − y3 ≤ −2


4x1 − 3x2 ≤ 8

s.c. s.c. y1 − 3y2 + y3 ≤9
−x1 + x2 ≥ −6
y1 ≥ 0, y2 ≤ 0, y3 ≥ 0.

 
x1 , x2 ≥ 0.


1.5.2 Propriétés de la dualité

Dans cette section, nous donnons les liens entre les solutions des programmes en dua-
lité.

Remarque 1.5.5 Clairement, le dual du dual est le primal.

Le résultat suivant n’est autre que l’inégalité (1).

Théorème 1.5.6 (Théorème faible du dualité )

Si z (resp., w) est la fonction objective du primal (resp., du dual), alors max z ≤ min w.

Nous admettons les résultats suivants :

Théorème 1.5.7 (Théorème forte du dualité )

Si le primal admet une solution réalisable optimale, alors le dual admet aussi une solution
réalisable optimale et max z = min w.

Théorème 1.5.8 Etant donné un problème primal et son dual, une et une seule des trois
situations suivantes peut se produire.
(i) les deux problèmes possèdent chacun des solutions optimales (à l’optimum, les
coûts sont égaux).
(ii) un des problèmes possède une solution rèalisable avec un optimum infini, l’autre
n’a pas de solution.
(iii) aucun des deux problèmes ne possède de solution réalisable.

1.5.3 Correspondances entre les tableaux simplexes optimaux Dual

et Primal
Dans l’exemple suivant l’Exemple 1.4.1, on examine le passage du dernier tableau
simplexe du primal au dernier tableau simplexe du dual.

Exemple 1.5.9

Primal
Dual
maxz = 7x1 + 5x2
minw = 400y1 + 500y2 + 700y3
x2 ≤ 400
 y2 + 2y3 ≥7


x1 + x2 ≤ 500

s.c. s.c. y1 + y2 + y3 ≥ 5
2x1 + x2 ≤ 700
y1 , y2 , y3 ≥ 0.

 
x1 , x2 ≥ 0.


Mohamed BENDAOUD 42
Chapitre 1 1.5 Dualité

Les tableaux optimaux simplexes du dual et du primal sont les suivants :

Primal
Dual
VDB x1 x2 e1 e2 e3 cste
VDB y1 y2 y3 u1 u2 cste
e1 0 0 1 -2 1 100
y2 2 1 0 1 -2 3
x2 0 1 0 2 -1 300
y3 -1 0 1 -1 3 2
x1 1 0 0 -1 1 200
w 100 0 0 200 300 - 2900
z 0 0 0 -3 -2 - 2900

Remarque 1.5.10 La solution optimale du dual peut être déduite à un signe près de celle
du primal comme suit :
Dual ←→ Primal
y1 = 0 ←→ δe1 = 0
y2 = 3 ←→ δe2 = −3
y3 = 2 ←→ δe3 = −2
u1 = 0 ←→ δx1 = 0
u2 = 0 ←→ δx2 = 0
δy1 = 100 ←→ e1 = 100
δy2 = 0 ←→ e2 = 0
δy3 = 0 ←→ e3 = 0
δu1 = 200 ←→ x1 = 200
δu2 = 300 ←→ x2 = 300
w = 2900 ←→ z = 2900

D’après le tableau ci-dessus, on remarque que :

1. A toute variable d’écart primale (resp. duale) strictement positive correspond une
variable structurelle duale (resp., primale) nulle.
2. A toute variable structurelle primale (resp., duale) strictement positive correspond
une variable d’écart duale (resp., primale) nulle.
En fait ces remarques s’exprime, dans le théorème ci-dessous, sous forme des règles
de complémentarité des écarts comme suit :

Théorème 1.5.11 (Complémentarité des écarts)

Soit x∗ et y ∗ des solution réalisables d’un PL primal et de son dual, respectivement. Alors
x∗ et y ∗ sont des solutions optimales si et seulement si les conditions suivantes, dites de
complémentarité des écarts, sont vérifiées :
 ∗ ∗
ei yi = 0, ∀i = 1, 2, ..., m
u∗j x∗j = 0, ∀i = 1, 2, ..., n

où e∗j et u∗i sont respectivement les variables d’écarts des PL primal et dual.

Les règles complémentarité des écarts permettent de trouver une solution optimale y ∗
du dual à partir de la connaissance de celle x∗ du primal.

Mohamed BENDAOUD 43
Chapitre 1 1.5 Dualité

Exemple 1.5.12 Le problème dual d’un PL s’écrit :

minw = 81y1 + 55y2 + 20y3 minw = 81y1 + 55y2 + 20y3

 3y1 + 4y2 + 2y3 ≥ 6  3y1 + 4y2 + 2y3 + u1 = 6
de forme standard
s.c. 9y1 + 5y2 + y3 ≥ 4 s.c. 9y1 + 5y2 + y3 + u2 = 4
y1 , y2 , y3 ≥0 y1 , y2 , y3 ≥ 0.
 

En utilisant les règles complémentarité et sachant que le problème primal PL admet la

solution optimale x∗ = (x∗1 , x∗2 , e∗1 , e∗2 , e∗3 ) = (15/2, 5, 27/2, 0, 0), on aura
 ∗
e >0  ∗
 1∗  y1 = 0


x1 > 0
∗ ⇒ 3y1∗ + 4y2∗ + 2y3∗ = 6 (car u∗1 = 0)
x > 0
 ∗2 9y1∗ + 5y2∗ + y3∗ = 4 (car u∗2 = 0).

 
e2 = e∗3 = 0

En résolvant le système pour y, on obtient la solution optimale du problème dual

(y1∗ , y2∗ , y3∗ ) = (0, 1/3, 7/3).

1.5.4 Interprétation économique de la dualité

La forme canonique d’un PL peut être interprétée comme un problème d’allocation de
ressources.

Primal Dual
min z = ct x min w = bt y
s.c. Ax ≤ b s.c. At y ≥ c
x ≥ 0. y ≥ 0.
• Données :
— cj : profit par unité d’activité j.
— bi : disponibilité de la ressource i.
— aij : consommation de la ressource i par unité d’activité j.
• Variables :
— xj : niveau d’activité j.
— yi : valeur d’une unité de la ressource i.
• Dualité :
— faible : z ≤ w, c.-à-d., profit ≤ valeur des ressources.
— forte : Le profit maximal est atteint si les ressources ont été exploitées complè-
tement, c.-à-d., jusqu’à épuisement de leur valeur.
• Si le PL est à :
— maximiser un profit, on parle de gain marginal.
— minimiser un coût, on parle de coût marginal.
• Coûts réduits :
— Le coût réduit δxj est la valeur marginale de l’activité j, c.-à-d., la variation de
z suite à l’augmentation d’une unité de cette activité j.

Mohamed BENDAOUD 44
Chapitre 1 1.6 Analyse de sensitivité

— Le coût réduit δei de la variable d’écart ei détermine la valeur de la variable

dual yi∗ (voir les tableaux simplexes optimaux), il est appelé aussi prix fictif
(Shadow price en anglais).
— Si δei 6= 0, alors la contrainte correspondante est saturée puisque, dans ce cas,
e∗i = 0.

Exemple 1.5.13 Dans le PL du ciment de l’Exemple 1.2.1, on a le tableau optimal sim-

plexe du primal suivant :

Primal
VDB x1 x2 e1 e2 cste
x2 4/3 1 1/30 0 12
e2 -20 0 -1 1 120
z -1300/3 0 -70/3 0 -8400

x∗1 = 0, x∗2 = 12, δe1 = −70/3, δe2 = 0, z∗ = 8400

y1∗ = 70/3, y2∗ = 0, w∗ = 8400.
• δe∗1 = −70/30 : Pour avoir une minute supplémentaire de four, je suis près à payer
au maximum de y1∗ = 70/3 en plus de sa valeur sur le marché.
Le prix d’une minute de four y1∗ = 70/3 : le temps de four est utilisé pleinement.
Vendre une minute revient à perdre 1 minute de production et donc diminue le
profit total. Pour retrouver le même profit, il faut exiger un prix de vente égale au
coût réduit. Donc le fonctionnement de l’usine permet de définir des prix pour les
différentes matières premières sur le marché, c’est un prix marginale.
• δe∗2 = 0 : Pour avoir une minute supplémentaire de broyeur, je ne suis pas près à
payer une somme d’argent en plus de sa valeur sur le marché puisque l’augmen-
tation de cette ressources n’apporte aucun profit supplémentaire, et donc on n’a
pas intérêt à augmenter la disponibilité du broyeur.
Le prix d’une minute du broyeur y2∗ = 0 : L’usine n’exige rien pour une minute
du broyeur louée ou vendue aux clients car il lui reste du temps de broyage non
utilisé.
• y1∗ = 70/30 , y2∗ = 0 sont les prix marginaux, et correspondent à la solution
optimale du dual de ce PL.

1.6 Analyse de sensitivité

1.6.1 Introduction
Dans la pratique, on a à faire face aux situations suivantes :
- Le profit unitaire de chaque activité peut varier soit à cause de la conjoncture, soit
qu’il ait mal été estimé.
- Les disponibilités peuvent varier et ainsi modifier les valeurs des seconds membres
des contraintes.

Mohamed BENDAOUD 45
Chapitre 1 1.6 Analyse de sensitivité

Grâce à la dualité on pourra se contenter de traiter le premier type de problème. On sup-

pose que l’on a affaire à un PL sous forme standard admettant des solutions optimales
réalisables. Dans cette configuration, si l’on remplace le coefficient ci d’une variable hors
base xi par c0i = ci + α, il se peut que la quantité c0i − zi0 correspondante ne soit plus né-
gative et que la solution obtenue ne soit plus optimale. La variable xi sera candidate pour
entrer en base. La plus petite valeur |α| telle que, lorsque ci est remplacé par c0i , la variable
xi est candidate à rentrer en base, est appelée coût réduit de la variable xi . La signification
économique est que pour les variables hors base, la valeur est nulle, ce qui veut dire que
les activités correspondantes ne sont pas profitables, le problème est donc de savoir pour
quelles valeurs des coefficients de la fonction économique elles le deviennent.

1.6.2 Paramétrisation de la fonction économique

Considérons le PL suivant :
Xn
max z = cj x j
 j=1
n
 X
 aij xj ≤ bi , i = 1, 2, ..., m
s.c. j=1

xj ≥ 0, j = 1, 2, ..., n


Posons cj = c0j + λc00j , j = 1, 2, ..., n. La fonction économique devient une fonction de

λ: n
X
z(λ) = (c0j + λc00j )xj .
j=1

Le domaine de variation de λ peut être découpé en un nombre fini d’intervalles pour

chacun desquels correspond une solution optimale différente. Ces intervalles sont appelés
intervalles de stabilité.
Supposons qu’il existe une solution optimale x∗ (λ0 ) du PL pour la valeur λ = λ0 .
A cette solution correspond un tableau final du simplexe pour lequel toutes les quan-
tités cj − zj sont négatives. Comme
m
X m
X
zj = ci aij = (c0i + λ0 c00i )aij , j = 1, 2, ..., n
i=1 i=1

On en déduit que
m
X m
X
λ0 (c00j − c00i aij ) + (c0j − c0i aij ) ≤ 0, j = 1, 2, ..., n.
i=1 i=1
Pm Pm
Posons Cj0 = c0j − i=1 c0i aij et Cj00 = c00j − i=1 c00i aij .
La solution x∗ (λ) restera optimale si toutes les quantités correspondantes zj − cj restent
négatives, c.-à-d., pour toutes les valeurs de λ qui vérifient :
0

 λ ≤ αj = −C00j , pour tout j = 1, 2, ..., n avec Cj00 > 0
C j
−Cj0
 λ ≥ βj =
Cj00
, pour tout j = 1, 2, ..., n avec Cj00 < 0

Mohamed BENDAOUD 46
Chapitre 1 1.6 Analyse de sensitivité

En posant a0 = minj αj et b0 = maxj βj , l’intervalle de stabilité de la solution x∗ (λ0 )

est [a0 , b0 ]. Pour toute valeur de λ prise dans cet intervalle, x∗ (λ) reste une solution opti-
male.

Dans la pratique, on construit les intervalles de stabilité de proche en proche à par-

tir d’une valeur λ0 déterminée (souvent 0), qui correspond à un PL sans paramètre. On
poursuit le processus jusqu’à ce que les intervalles de stabilité recouvrent le domaine de
variation de λ tout entier.

Remarque 1.6.1 Le changement des coûts ci ne modifie pas la région admissible, seule
la fonction économique varie. Dans le cas d ?un problème à deux variables, si un point
extrême P est solution optimale, on cherche la pente des droites définies par la fonction
économique pour lesquels P reste une solution optimale.

1.6.3 Paramétrisation du second membre des contraintes

Considérons le PL suivant :
Xn
max z = cj x j
 j=1
n
X
aij xj ≤ bi + λb00i , i = 1, 2, ..., m,

 λ∈R
s.c. j=1

xj ≥ 0, j = 1, 2, ..., n


Par dualité on peut se ramener au cas de la paramétrisation de la fonction économique. Le

dual s’écrit en effet :
m
X
min z = (bi + λb00i )yi
 i=1
m
 X a y ≥ c , j = 1, 2, ..., n,

λ∈R
ij i j
s.c. i=1

 yi ≥ 0, i = 1, 2, ..., m

que l’on résout comme à la section précédente.

Exemple 1.6.2 On considère le PL suivant :

maxz = x1 + (3 − 3λ)x2

 x1 + x 2 ≤ 14
−2x1 + 3x2 ≤ 12

s.c.

 2x1 − x2 ≤ 12
x1 , x2 ≥ 0,


Pour λ = 0 la solution optimale a déjà été calculée. Sur chaque intervalle de stabilité, les
valeurs de x1 et x2 sont fixées, la valeur optimale de la fonction économique devient donc
une fonction affine par morceaux de la variable λ.

Mohamed BENDAOUD 47
Chapitre 1 1.6 Analyse de sensitivité

Le premier tableau s’obtient tout en écrivant la fonction économique en fonction de

λ et en supposant que λ prend la valeur 0 pour déterminer le pivot de chaque itération
jusqu’à obtenir toutes les coûts réduits négatifs ou nuls si λ = 0.

VDB x1 x2 e1 e2 e3 cste
x1 1 0 3/5 -1/5 0 6
x2 0 1 2/5 1/5 0 8
e3 0 0 -4/5 3/5 1 8
z 0 0 (−9 + 6λ)/5 (−2 + 3λ)/5 0 −30 + 24λ


(−9 + 6λ)/5 ≤ 0
⇒ 0 ≤ λ ≤ 2/3, (x1 , x2 ) = (6, 8), z = 30 − 24λ.
(−2 + 3λ)/5 ≤ 0

Le premier intervalle de stabilité est donc : [0, 2/3].

La colonne pivot de cette itération est celle qui a le plus grand coût réduit en suppo-
sons maintenant que λ ≥ 2/3 ; ce qui donne le deuxième tableau suivant :

VDB x1 x2 e1 e2 e3 cste
x1 1 0 -1/3 0 1/3 26/3
x2 0 1 2/3 0 -1/3 16/3
e2 0 0 -4/3 3/5 0 5/3
z 0 0 −7/3 + 2λ 0 2/3 − λ −74/3 + 16λ


−7/3 + 2λ ≤ 0
⇒ 2/3 ≤ λ ≤ 7/6, (x1 , x2 ) = (26/3, 16/3), z = 74/3 − 16λ.
2/3 − λ ≤ 0

Le deuxième intervalle de stabilité est donc : [2/3, 7/6].

De même on a le troisième tableau suivant :

VDB x1 x2 e1 e2 e3 cste
x1 1 -1/2 0 0 1/2 6
e1 0 3/2 1 0 -1/2 8
e2 0 2 0 1 1 24
z 0 −7/2 + 3λ 0 0 -1/2 - 6

λ ≥ 7/6, (x1 , x2 ) = (6, 0), z = 6.

Le dernier intervalle de stabilité est donc [7/6, +∞[, et la courbe de la fonction écono-
mique z en fonction de z est donnée par la Figure 1.13 ci-dessous :

Mohamed BENDAOUD 48
Chapitre 1 1.7 Mises-en oeuvre sur un solveur

F IGURE 1.13 – Intervalles de stabilité

1.7 Mises-en oeuvre sur un solveur

La disposition pratique de l’algorithme du simplexe suivant a été mis au point par
George Dantzig en 1947.

Mohamed BENDAOUD 49
Chapitre 1 1.7 Mises-en oeuvre sur un solveur

L’algorithme d’un PL à maximiser

Début
Mettre les contraintes sous forme d’égalités ;
Rechercher une première solution réalisable ;
Construire le premier tableau du simplexe ;
Tant que ∃j ∈ {1, ..., n} : (cj − zj ) > 0 Faire
Si ∃k ∈ {1, ..., n} : (ck − zk ) > 0 et aij < 0∀i ∈ {1, ..., m}
Alors max(z) = +∞ (pas de solution)
Sinon
Début
(Recherche des variables entrante et sortante)
xe entre en base si ce − ze = max(ck − zk ) ;
bs bi
xs sort si = min ( ) ;
ase aie >0 aie
(Construction du nouveau tableau, le pivot est ase )
(Ligne du pivot)
bs
b0e ←− (dans la colonne des constantes)
ase
asj
a0ej ←− (donc 1 pour a0es )
ase
(Autres lignes)
aie
b0i ←− bi − xs ;
ase
aie
a0ij ←− aij − ;
ase
xs
z00 ←− z0 + (ce − ze ) ;
ase
asj
cj − zj0 ←− cj − zj − (ce − ze ) ;
ase
Fin ;
Fin.
Notons que lorsqu’un problème est décrit comme un programme linéaire, il est inutile
de programmer un algorithme pour le résoudre : de nombreux logiciels, dont certains
libres, le font déjà avec d’excellentes performances. Même EXCEL dispose d’une implé-
mentation de l’algorithme du simplexe.

Comme solveurs de programmation linéaire, on peut citer de nombreux logiciels payants

ou libres :
• Payants : MATLAB, CPLEX, XPRESS, MINOS, ...
• Libres : GLPK, LPSOLVE, CLP, SCIP, SOPLEX, ...
• Langages de modélisation : AMPL, APL, OPL, TOMLAB, ...

Cette section portera sur l’utilisation de MATLAB pour résoudre certains PL.

Pour résoudre un programme linéaire à l’aide de MATLAB, tout d’abord il faut créer
un projet d’exécution MATLAB dans lequel on pourra définir notre PL. Pour cela dans
MATLAB il faut cliquer sur EDITOR / Nouveau "+". Une fenêtre s’ouvre. Enregistrer le

Mohamed BENDAOUD 50
Chapitre 1 1.7 Mises-en oeuvre sur un solveur

fichier sous MATLAB code files.m : entrez un nom de projet, choisissez son emplacement
(dossier parent) et cochez "enregistrer" (voir capture d’écran Figure 1 ci-dessosu).
Dans le fichier modèle (.m) on entre le PL : les variables, les contraintes et la fonction
objective (voir capture d’écran Figure 2 ci-dessous).
Pour lancer la résolution il faut faire un clic sur Exécuter "Run" situé à droite dans
l’onglet EDITOR. Le bouton exécuter "Run" dans la barre d’outils permet de lancer une
nouvelle fois la dernière configuration exécutée. Une fois le modèle résolu, la solution
du PL s’affiche dans l’onglet "Command Window" situés en bas de la fenêtre principale
(sous le fichier modèle (.m)).
Exemple 1.7.1 On considère le PL suivant :
maxz = 3x1 + 2x2 + 2x3 + x4

 x1 + x4 ≤4
 x2 ≤6


s.c. 6x1 + 4x2 ≤ 36
x3 ≤7




7x1 + 2x2 ≤ 47


Dans le fichier (.m) correspondant on entre le PL :

prob = optimproblem(0 ObjectiveSense0 ,0 max0 );
x = optimvar(0 x0 , 4, 1,0 LowerBound0 , 0);
[Link] = 3 ∗ x(1) + 2 ∗ x(2) + 2 ∗ x(3) + x(4);
cons1 = x(1) + x(4) <= 4;
cons2 = x(2) <= 6;
cons3 = 6 ∗ x(1) + 4 ∗ x(2) <= 36;
cons4 = x(3) <= 7;
cons5 = 7 ∗ x(1) + 2 ∗ x(2) <= 47;
[Link].cons1 = cons1;
[Link].cons2 = cons2;
[Link].cons3 = cons3;
[Link].cons4 = cons4;
[Link].cons5 = cons5;
sol = solve(prob);
sol.x
evaluate([Link], sol)
Après exécution on obtient :
ans =
2.0000
6.0000
7.0000
2.0000

ans =
34
c.-à-d., la première réponse "ans" donne le vecteur solution, et la deuxième "ans" donne
la valeur correspondante de la fonction objective : z = 34.

Mohamed BENDAOUD 51
Chapitre 1 1.7 Mises-en oeuvre sur un solveur

Exemple 1.7.2 On considère le PL suivant :

min z = 3x1 + 2x2 + 3x3 + x4


 x1 ≥4
x2 ≥6




x3 + x4 ≥ 15

s.c.

 x4 ≤ 10
6x + 4x + 5x ≥ 36

 1 2 3



x1 , x2 , x3 , x4 ≥ 0

Dans le fichier (.m) correspondant on entre le PL :

prob = optimproblem(0 ObjectiveSense0 ,0 min0 );

x = optimvar(0 x0 , 4, 1,0 LowerBound0 , 0);
[Link] = 3 ∗ x(1) + 2 ∗ x(2) + 3 ∗ x(3) + x(4);
cons1 = x(1) >= 4;
cons2 = x(2) >= 6;
cons3 = x(3) + x(4) >= 15;
cons4 = x(4) <= 10;
cons5 = 6 ∗ x(1) + 4 ∗ x(2) + 5 ∗ x(3) >= 36;
[Link].cons1 = cons1;
[Link].cons2 = cons2;
[Link].cons3 = cons3;
[Link].cons4 = cons4;
[Link].cons5 = cons5;
sol = solve(prob);
sol.x
evaluate([Link], sol)
Après exécution on obtient :

ans =
4.0000
6.0000
5.0000
10.0000

ans =
49.0000
c.-à-d., la première réponse "ans" donne le vecteur solution, et la deuxième "ans" donne
la valeur correspondante de la fonction objective : z = 49.0000.

Mohamed BENDAOUD 52
Chapitre 2

Programmation en nombres entiers

2.1 Introduction
Pour résoudre un programme linéaire de manière efficace, on utilise généralement
l’algorithme du simplexe. Cependant les solutions obtenues sont des valeurs réelles tandis
que, pour des raisons pratiques, dans un PL une solution à valeurs entières est souvent
exigée.
On pourrait penser que, pour avoir des valeurs entières à ce problème, il suffit de
faire un arrondi de la solution réelle obtenue. Ainsi et le problème serait réglé. Cette
technique d’arrondissement peut fournir directement la solution optimale pour certains
cas. Toutefois, pour d’autres cas, cette combine par arrondissement serait loin d’être la
solution optimale, voire désastreuse par rapport à la solution optimale apportée par la
résolution d’un programme linéaire en variables entières.

Exemple 2.1.1 On considère le PL suivant :

maxz = 10x1 + 11x2

10x1 + 12x2 ≤ 59
s.c.
x1 , x2 ≥ 0, x1 , x2 ∈ N

La solution optimale x est donnée par x = (x1 ; x2 ) = (5, 9; 0). En effet, x1 ≤ 5, 9−1, 2x2 ,
et on obtient la solution optimale en posant x1 = 5, 9 et x2 = 0. Mais la solution x0 =
(6, 0) n’est pas réalisable et la solution x00 = (5, 0) n’est pas optimale parmi les solutions
à valeurs entières. La solution optimale à valeurs entières est donnée par x = (1, 4).

En programmation en nombres entiers, on ne dispose pas d’un algorithme général

qui permette de résoudre efficacement tous les problèmes en nombres entiers. Cependant,
il existe plusieurs méthodes telle que la technique d’énumération pour l’exploration de
toutes les solutions possibles ou encore l’algorithme de "branch and bound" appelé mé-
thode de"séparation et évaluation". Cette méthode utilise le simplexe à plusieures reprises.

53
Chapitre 2 2.2 La méthode de séparation et d’évaluation (Branch and Bound)

2.2 La méthode de séparation et d’évaluation (Branch

and Bound)
La méthode de "branch and bound" appelée aussi méthode de séparation et évaluation
est destinée à résoudre les problèmes linéaires en nombre entier. Cette méthode consiste à
appliquer une énumération intelligente des solutions admissibles, en adoptant le principe
de "Diviser pour régner" qui délimite l’exploration de toutes les branches, et qui élimine
des solutions partielles ne menant pas à la solution optimale. Il s’agit essentiellement d’ef-
fectuer une décomposition du problème en sous problèmes plus simples. Puis on combine
la résolution de tous les sous problèmes pour obtenir la solution du problème original.

2.2.1 Relaxation linéaire

Définition 2.2.1 On appelle relaxation linéaire d’un programme linéaire P en nombres
entiers
maxz = ct x
Ax ≤ b
s.c.
x ≥ 0, x ∈ N
le programme linéaire P L
maxz = ct x
Ax ≤ b
s.c.
x≥0
obtenu en supprimant les contraintes d’intégralité sur les variables dans P .

Remarque 2.2.2
• La valeur de la solution optimale du P L est une borne supérieure sur la valeur de
la solution optimale de P .
• La valeur d’une solution admissible du P fournit une borne inférieure sur la valeur
de la solution optimale de P .
• Si la solution optimale du P L est entière (donc admissible pour P ), elle est éga-
lement la solution optimale de P .

2.2.2 Démarche de résolution

La démarche de résolution consiste à concevoir un arbre (une arborescence) qui, a
comme racine, la solution optimale du problème relaxé. Puis, on construit au fur et à
mesure, toutes les branches à exploiter en passant d’un sommet a un autre.

• Si la solution optimale du P L est entière, alors on s’arrête, elle est également la

solution optimale de P .
• Si la solution du P L n’est pas entière, soit xi une variable prenant une valeur
fractionnaire x∗i dans la solution optimale du P L.
- Le problème peut être divisé en deux sous-problèmes en imposant xi ≤ [x∗i ]
ou xi ≥ [x∗i ] + 1 ; où [x∗i ] désigne la partie entière de x∗i .

Mohamed BENDAOUD 54
Chapitre 2 2.2 La méthode de séparation et d’évaluation (Branch and Bound)

- La solution optimale de P est la meilleure des solutions optimales des deux

problèmes :
(P1 ) (P2 )
max z= ct x maxz = ct x
 Ax ≤ b et  Ax ≤ b
s.c. xi ≤ [x∗i ] s.c. xi ≥ [x∗i ] + 1
x ≥ 0, x ∈ N x ≥ 0, x ∈ N
 

Pour construire la première branche, s’il ya plusieurs variables fractionnaires dans

la solution optimale, on choisit une variable arbitrairement parmi les variables fraction-
naires. Par exemple on peut choisir la variable qui a la plus grande partie fractionnaire. Il
n’y a pas de règle générale pour le choix de la variable de branchement et de la branche
à examiner en premier. Le choix de telle ou telle variable n’influence pas sur la solution
finale. Par ailleurs, le nombre de branches et le nombre de sommets pour l’arbre définitif
varie différemment pour chaque variable choisie.
Exemple 2.2.3 On considère le programme linéaire P à variables entières suivant :
maxz = x1 + 4x2
 5x1 + 8x2 ≤ 40
s.c. −2x1 + 3x2 ≤ 9
x1 , x2 ≥ 0, x1 , x2 ∈ N


Arbre associée au programme :

F IGURE 2.1 – Arbre d’un programme linéaire à variables entières.

Etapes du branchement :

Mohamed BENDAOUD 55
Chapitre 2 2.2 La méthode de séparation et d’évaluation (Branch and Bound)

1) Résoudre P à l’aide du simplexe sans tenir compte de la contrainte x1 , x2 à valeurs

entières. Solution optimale : x = (x1 ; x2 ) = (1, 55; 4, 03) et z(x) = 17, 67.
Brancher par rapport à x1 : x1 ≤ 1 ou x1 ≥ 2.
2) Ajouter la contrainte x1 ≤ 1 à P et résoudre ce programme à l’aide du simplexe,
sans tenir compte de la contrainte x1 , x2 à valeurs entières. Solution optimale x =
(1; 3, 67) et z(x) = 15, 67.
Brancher par rapport à x2 : x2 ≤ 3 ou x2 ≥ 4.
3) Ajouter à P les contraintes x1 ≤ 1 et x2 ≤ 3. La solution optimale de ce pro-
gramme est à valeurs entières : x = (1; 3), z(x) = 13.
Borner à 13 (c.-à-d., ne pas poursuivre le branchement si on obtient des solutions
optimales < 13).
4) Ajouter à P les contraintes x1 ≤ 1 et x2 ≥ 4. Ce programme n’a pas de solutions
réalisables.
5) Ajouter à P la contrainte x1 ≥ 2. La solution optimale x = (2; 3.75) et z(x) = 17.
Brancher par rapport à x2 : x2 ≤ 3 ou x2 ≥ 4.
6) Ajouter à P les contraintes x1 ≥ 2 et x2 ≤ 3. Solution optimale x = (3, 2; 3) et
z(x) = 15, 2.
Brancher par rapport à x1 : x1 ≤ 3 ou x1 ≥ 4.
7) Ajouter à P les contraintes 2 ≤ x1 ≤ 3 et x2 ≤ 3. Solution optimale x = (3; 3) et
z(x) = 15. Borner à 15.
8) Ajouter à P les contraintes x1 ≥ 4 et x2 ≤ 3. Cas sans intérêt parce que z(x) =
14 < 15 pour la solution optimale x = (4; 2, 5).
9) Ajouter à P les contraintes x1 ≥ 2 et x2 ≥ 4. Pas de solutions réalisables.
La solution optimale à valeurs entières est donc celle trouvée en 7) : x1 = x2 = 3
pour laquelle z(x) = 15.

Remarque 2.2.4 On peut obtenir l’arbre associée au programme ci-dessus en utilisant

la résolution graphique, voir la Figure 2.2 ci-dessous.

Mohamed BENDAOUD 56
Chapitre 2 2.2 La méthode de séparation et d’évaluation (Branch and Bound)

Solutions rélisables à valeurs

ent!ères

−2x1 + 3x2 = 9
5
B(1,55; 4,03) 5x1 + 8x2 = 40

3
C(0; 3)
2

z=0 1

0 1 2 3 4 8
A(8; 0)

F IGURE 2.2 – Branchement du PL à variables entières

Exemple 2.2.5 On considère le programme linéaire à variables entières suivant :

maxz = 5x1 + 4x2

 x1 + x2 ≤5
s.c. 10x1 + 6x2 ≤ 45
x1 , x2 ≥ 0, x1 , x2 ∈ N


Le programme linéaire relaxé LP a pour solution x1 = 3, 75, x2 = 1, 25 pour laquelle

z = 23, 75. Par exemple on peut choisir la variable qui a la plus grande partie fractionnaire
à savoir x1 pour le premier branchement, voir la Figure 2.3 cidessous.
Arbre associée au programme :

F IGURE 2.3 – Arbre associée à un PL à variables entières

Mohamed BENDAOUD 57
Chapitre 2 2.2 La méthode de séparation et d’évaluation (Branch and Bound)

On peut obtenir l’arbre associée au programme ci-dessus en utilisant la résolution

graphique, voir la Figure 2.4 ci-dessous.
10x1 + 6x2 = 45
Solutions rélisables à valeurs
ent!ères

x1 + x2 = 5

0 3 4

z=0

F IGURE 2.4 – Branchement d’un PL à variables entières

- La solution de LP1 est une solution admissible de P et donc z = 23 est une borne
inférieure de la valeur de la solution optimale de P .
- Le noeud correspondant peut être éliminé vu qu’une solution entière optimale sa-
tisfaisant x1 ≤ 3 a été trouvée (solution de LP1 ).
- La valeur de la solution de LP , z = 23, 75 est une borne supérieure de la valeur
de la solution optimale de P .
- Vu que tout les coefficients sont entiers, on peut en déduire que la valeur de la
solution optimale de P est inférieure ou égale à 23.
- La solution de LP1 est donc optimale pour P . Ainsi, la solution optimale à valeurs
entières est donc x = (3, 2) pour laquelle z(x) = 23.

Remarque 2.2.6 La méthode par séparation et évaluation n’intervient pas seulement en

programmation linéaire, mais dans tous les problèmes d’optimisation, où on travaille avec
des arbres de décision.

Mohamed BENDAOUD 58
Chapitre 2 Exercices

Exercices

Exercice 1. Une usine fabrique deux types de ciments : un ciment pour les constructions
personnelles C1 et un pour les ouvrages d’art C2 . L’usine a pour cela une ligne de pro-
duction et deux matières premières M1 et M2 . Les deux types de ciments passent par la
même ligne et utilisent M1 et M2 selon le tableau suivant :

Quantité utilisée par tonne Quantité disponible par jour

Ciment C1 Ciment C2
M1 6 4 24
M2 1 2 6
Profit net par tonne 5 4

De plus la capacité de la ligne pour le ciment C2 ne dépasse pas 2 tonnes par jour et la
production de C2 ne peut dépasser celle de C1 que d’une tonne par jour.
1. Ecrire le modèle en PL qui maximisera le profit de l’usine.
2. Résoudre le PL graphiquement.
3. Résoudre le PL par la méthode d’énumération.
4. Résoudre le PL par la méthode du simplexe, et spécifier à chaque itération le point
extrème (ou le sommet) visité.
5. Trouver la solution optimale dans le cas où l’usine s’impose de ne produire que
des quantités entières (en tonnes par jour) des ciments C1 et C2 en utilisant la mé-
thode de Branch and Bound.

Exercice 2. Une entreprise fabrique une certaine pièce qui nécessite, au stade de l’assem-
blage final, trois parties. Ces trois parties peuvent être produites par deux unités différentes
et parallèlles, comme indiqué ci-dessous :

Taux de production (unités / heures)

Partie 1 Partie 2 Partie 3 coût (100 DM/Heure)
Unité 1 7 6 9 25
Unité 2 6 11 5 12,5

N.B. Chaque unité est conçue pour produire les trois paties et ne peut être dédiée à 1 ou 2
parties seulement. C’est à dire pendant une heure de travail l’unité 1 produit exactement
7 unités de la partie 1, 6 unités de la partie 2 et 9 unité de la partie 3. Il en est de même
pour l’unité 2.
Supposons que cette semaine, 1050 produits finis (assemblés) sont nécessaires pour
satisfaire les commandes (mais on peut en produire jusqu’à 1200 maximum si nécessaire).
Supposons, de plus, que l’unité 1 dispose de 100 heures de travail et que l’unité 2 en
dispose 110.

Mohamed BENDAOUD 59
Chapitre 2 Exercices

Formuler sans résoudre, le problème de minimisation des coûts de production des

produits finis (assemblés) nécessaires cette semaine en tant que PL avec une contrainte
supplémentaire qui est due à la capacité de stock : seulement un total de 200 pièces non
assemblées (de tous types) peut être stocké à la fin de la semaine.

Solution de l’exercice 2 : Soit x1 et x2 respectivement le nombre d’heures utilisées dans

l’unité 1 et l’unité 2, et soit x le nombre de pièces assemblées (produits finis). Le nombre
total des parties produites est (7x1 + 6x2 ) + (6x1 + 11x2 ) + (9x1 + 5x2 ) = 22x1 + 22x2 , et
le nombre (le reste) des pièces non assemblées (de tous types) est alors 22x1 + 22x2 − 3x ;
ce qui donne la contrainte du stock 22x1 + 22x2 − 3x ≤ 200. Ainsi, Le PL se modélise
sous forme :
min z = 25x1 + 12, 5x2

 7x1 + 6x2 ≥x
6x + 11x ≥x

1 2



9x1 + 5x2 ≥x




x1 ≤ 100

s.c.

 x2 ≤ 110
22x1 + 22x2 − 3x ≤ 200




1050 ≤ x ≤ 1200




x1 , x2 , x ≥ 0.


Mohamed BENDAOUD 60