Cours RO Master1

Cours Recherche Opérationnelle:
Université Cheikh Anta Diop (UCAD) de Dakar

Faculté des Sciences Economiques et de Gestion (FASEG)
Département de Mathématiques de la Décision (DMD)
Master 1 Sciences Économiques et de Gestion
Pr. Babacar Mbaye NDIAYE - Dr. Mouhamadou A.M.T. Baldé, Année 2020-2021.
Laboratoire de Mathématiques de la Désicion et d’Analyse Numérique (LMDAN)
[email protected], http://lmdan.ucad.sn
Notes
Ces notes de cours correspondent à un enseignement de quatrième année de la FASEG. Ce cours est
le résultat d’une réflexion technique pédagogique dont nous espèrons qu’il apportera aux étudiants
une stimulation intellectuelle et un encouragement à persévérer, chaque fois que la compréhension
d’un phénomène économique leur posera des difficultés.
Bien qu’ayant relu attentivement toutes les notes, il reste plusieurs imperfections. Nous demandons
aux étudiants de nous en excuser, et de nous les signaler afin d’en améliorer la qualité. Leurs
camarades de l’année prochaine leur en seront reconnaissants.
1
Contents
1 PROGRAMMATION LINÉAIRE EN VARIABLES CONTINUES: MODÉLI-
SATION ET RÉSOLUTION 4
1.1 Petits exemples pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Définition et formulation d’un problème de programmation linéaire . 8
1.2.1 Définition d’un programmation linéaire . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Forme algébrique d’un programme linéaire . . . . . . . . . . . . . . . . . . . 10
1.2.3 Forme matricielle d’un programme linéaire . . . . . . . . . . . . . . . . . . . 11
1.3 Interprétation économique d’un programme linéaire . . . . . . . . . . . 12
1.4 Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2 Correspondance base-sommet, changement de base, itération . . . . . . . . . 22
1.5.3 Principe de la méthode: un peu de théorie . . . . . . . . . . . . . . . . . . . 24
1.5.4 Critères de Dantzig et test d’optimalité . . . . . . . . . . . . . . . . . . . . . 26
1.5.5 Application à l’exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.5.6 Cas particuliers et compléments . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5.7 Base de départ et variables artificielles . . . . . . . . . . . . . . . . . . . . . 31
1.6 Dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6.1 Variable duale associée à une contrainte . . . . . . . . . . . . . . . . . . . . 37
1.6.2 Dual d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.6.3 Théorème de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.6.4 Application à l’exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.7 Analyse de sensibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.7.1 Variation d’un coefficient de la fonction objectif . . . . . . . . . . . . . . . . 41
1.7.2 Variation d’un coefficient du second membre . . . . . . . . . . . . . . . . . . 42
2 PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS 44

2.1 Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2 Coupes de gomory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3 Problème du sac-à-dos simple . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4 Problème du sac-à-dos multidimensionnel . . . . . . . . . . . . . . . . . . . 57
2.5 Problèmes de tournées de véhicules . . . . . . . . . . . . . . . . . . . . . . 57
2
2.6 Problème de localisation (location/allocation problem) . . . . . . . . 58
2.7 Problèmes de recouvrement (Set Covering Problem - SCP) . . . . . . . 60
A Exercices corrigés 62
B Quelques exercices 68
C Quelques devoirs et examens corrigés 75
D Les principaux solvers - modeleurs 93

D.1 Solveurs libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
D.2 Solveurs commerciaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
D.3 Modeleurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3
1 PROGRAMMATION LINÉAIRE EN VARIABLES CON-
TINUES: MODÉLISATION ET RÉSOLUTION
Nous abordons dans ce chapitre un type particulier de modélisation. A l’opposé du modèle économique,
un problème d’optimisation va être représenté par un problème de programmation mathéma-
tique : les variables de décision sont des variables numériques, la représentation des décisions
possibles et du critère fait appel à des équations ou fonctions mathématiques. Plus précisément,
nous introduisons ici le problème particulier de programmation linéaire en variables continues (dans
l’ensemble des réels Rn ).
Dans la section 1.1 nous énonçons quelques exemples d’application, suivi de la section 1.2 où
nous présentons la définition d’un problème de programmation linéaire en variables continues.
L’interprétation économique de ce programme linéaire sera donnée dans la section 1.3. Lorsqu’il
n’y a que deux (2) variables de décision, un problème linéaire peut être résolu de manière purement
graphique. C’est ce que nous verrons dans la section 1.4. Lorsqu’il y a un plus grand nombre de
variables (supérieur ou égal à trois (3)), un algorithme mis en oeuvre sous la forme d’un programme
informatique s’avère nécessaire. Nous choisissons l’algorithme du Simplexe que nous verrons dans
la section 1.5. Dans la section 1.6, nous examinerons la dualité en programmation linéaire. En-
fin, la section 1.7 traite une question très importante, à savoir la sensibilité de la solution à des
modifications de données. On parle d’analyse post-optimale.
1.1 Petits exemples pratiques
Le modèle type de programmation linéaire peut être retenu pour représenter de nombreux prob-
lèmes. Dans la suite de cette section, nous illustrons trois (3) exemples de modèle (de dimension
2) permettant de comprendre les types de programmes que nous aurons à étudier dans ce chapitre.
D’autres exemples (de dimension 2, 3 ou plus) sont ajoutés en Annexe de ce cours et en Travaux
Dirigés (TD).
Exemple 1 : L’entreprise SIMPA (Société Industrielle et Moderne des Plastiques Africains) du

Sénégal fabrique deux(2) types de produits P1 et P2 (Flexible film/Sacherie et Rigide/Semi-rigide)
à partir de deux(2) ressources: la main d’oeuvre (employés/machines) et des matériaux (poly-
téréphtalate d’éthylène (PET)). Par ailleurs, chaque ressource est disponible en quantité limitée.
L’entreprise SIMPA ne dispose que de 200 heures pour la main d’oeuvre et 150 kg de matériaux
par jour. La main d’oeuvre et les matériaux nécessaire pour la production d’une unité des produit
4
est donné dans le tableau suivant:
P1 P2 disponibilité
main d’oeuvre (h/unité) 7 3 200
matériaux (Kg/unité) 4 4 150
Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 40 000 FCFA et
20 000 FCFA par unité.
Question: Quelles quantités de produits P1 et P2 doit produire l’entreprise SIMPA afin de maximiser
le bénéfice total venant de la vente des 2 produits ?
Formuler le problème sous forme de programme linéaire permettant à l’entreprise SIMPA de max-
imiser le profit quotidien venant de la vente des 2 produits.
X Modélisation du problème: Nous examinons dans l’ordre la représentation des variables de

décisions, des contraintes et du critère à optimiser.
Les variables de décisions: nous appelons par x1 et x2 les quantités de produits P1 et P2 à
fabriquées, respectivement.
Les contraintes: il s’agit des contraintes limitant la production des produits. La première est
la limitation du nombre d’heures de main d’oeuvre: il faut 7 heures pour fabriquer une unité de
produit P1 et 3 heures pour fabriquer une unité de produit P2 . Le nombre d’heures total disponible
pour la fabrication de ces 2 produits est de 200 heures. On doit donc imposer : 7x1 + 3x2 ≤ 200.
De même, il faut 4 kg de matériaux pour fabriquer chacun des produits P1 et P2 , et le nombre de
matérieux total disponible pour leur fabrication est de 150. Ce qui se traduit par : 4x1 + 4x2 ≤ 150.
L’ensemble des décisions possibles est caractérisé par l’ensemble des valeurs de x1 et x2 vérifiant :
7x1 + 3x2 ≤ 200
4x1 + 4x2 ≤ 150
x1 ≥ 0, x2 ≥ 0
Le critère : on souhaite maximiser le profit quotidien de l’entreprise SIMPA (venant de la vente

des 2 produits) représenté par : 40000x1 + 20000x2 .
5
Le problème est donc modélisé par le problème de programmation mathématique suivant :
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 ≤ 200
4x1 + 4x2 ≤ 150
x1 ≥ 0, x2 ≥ 0
Exemple 2 : Une entreprise spécialisée dans la fabrication de matériels informatiques, propose à

son catalogue d’ordinateurs des centaines de référence. Pour simplifier, on ne s’intéresse ici qu’à
deux types d’ordinateurs : le Core i3 et le Core i7. Chacun d’eux comporte un processeur (le
même) mais les deux modèles diffèrent en particulier par le nombre de barrettes mémoires. Plus
précisément, le Core i3 comporte 2 barrettes alors que le Core i7 en comporte 6. Le marché pour ces
composants est tel qu’on ne peut espérer acheter auprès des fournisseurs habituels plus de 10 000
processeurs pour le trimestre à venir et plus de 48 000 barrettes. Une autre limitation intervient sur
la production: l’assemblage est caractérisé, en particulier, par une opération délicate, qui pour le
Core i3 est de 3 minutes alors que pour le Core i7 elle n’est que d’une minute. On ne dispose a priori
pour l’assemblage de ces deux types de machines que de 24 000 minutes pour le trimestre à venir.
Enfin, compte tenu des conditions actuelles du marché, on peut espérer retirer un profit de 40 000
FCFA sur le Core i3 et de 80 000 FCFA sur le Core i7. L’objectif est de déterminer les quantités
de chacun des deux types d’ordinateurs à fabriquer de manière à obtenir le plus grand profit possible.

Les variables de décisions: les décisions concernent les quantités à fabriquer, ce qui se représente
naturellement par deux nombres positifs x1 pour le Core i3 et x2 pour le Core i7.
Soit : x1 la quantité pour le Core i3 à fabriquer et x2 la quantité pour le Core i7 à fabriquer.
Les contraintes: il s’agit de représenter les différentes contraintes limitant la production de ces
deux types d’ordinateur. La première porte sur la limitation du nombre de processeurs disponibles
: chaque machine utilise un processeur et on peut en disposer de 10000. On doit donc imposer : x1
+ x2 ≤ 10000.
De même, le nombre de barrettes est limité. Compte tenu du nombre de barrettes dans chacun
des 2 ordinateurs et du nombre de barrettes disponibles, cette contrainte se traduit par : 2x1 +
6x2 ≤ 48000. Enfin, la contrainte portant sur le temps d’assemblage s’écrit : 3x1 + x2 ≤ 24000.
L’ensemble des décisions possibles est donc caractérisé par l’ensemble des valeurs de x1 et x2 vérifiant
6
:
x1 + x2 ≤ 10000
2x1 + 6x2 ≤ 48000
3x1 + x2 ≤ 24000
x1 ≥ 0, x2 ≥ 0
Le critère : on souhaite maximiser le profit de l’entreprise représenté par : 40000x1 + 80000x2 .
Le problème initial est donc modélisé par le problème de programmation mathématique suivant
:
max f (x) = 40000x1 + 80000x2
s.c. x1 + x2 ≤ 10000
2x1 + 6x2 ≤ 48000
3x1 + x2 ≤ 24000
x1 ≥ 0, x2 ≥ 0
Exemple 3 : Un groupement d’intérêt économique (GIE) peut fabriquer un même bien selon
deux techniques différentes de production utilisant les services d’une même machine et de la main
d’oeuvre. Le nombre d’heures nécessaire pour la production d’une unité de bien est donné dans le
tableau suivant:
machine main d’oeuvre

première technique 0.5 2
deuxième technique 1.5 1.5
On suppose que la capacité d’usinage de la machine est de 12 heures et que le nombre d’heures de
travail disponibles est de 15 heures. Le GIE cherche à maximiser sa marge sur coût variable. Les
marges unitaires sont de 190000 FCFA, 260000 FCFA selon que le bien est fabriqué à l’aide de la
première ou deuxième technique.

Les variables de décisions: nous appelons par x1 et x2 les quantités de bien fabriquées selon
l’une des deux techniques.
Les contraintes: il s’agit de représenter les différentes contraintes limitant la production de bien.
7
La première est la limitation du nombre d’heures d’usinage de la machine : la première technique
nécessite une demi heure, la deuxième une heure et demi et on peut en disposer de 12 heures. On
doit donc imposer : 0.5x1 + 1.5x2 ≤ 12.
De même, le nombre d’heures de main d’oeuvre est limité à 15 heures. La première technique
nécessite deux heures tandis que la deuxième d’une heure et demi. Ce qui se traduit par : 2x1 +
1.5x2 ≤ 15.
L’ensemble des décisions possibles est donc caractérisé par l’ensemble des valeurs de x1 et x2 vérifiant
:
0.5x1 + 1.5x2 ≤ 12
2x1 + 1.5x2 ≤ 15
x1 ≥ 0, x2 ≥ 0
Le critère : le GIE cherche à maximiser sa marge sur coût variable représenté par : 190000x1 +
260000x2 .
Le problème initial est donc modélisé par le problème de programmation mathématique suivant
:
max f (x) = 190000x1 + 260000x2
s.c. 0.5x1 + 1.5x2 ≤ 12
2x1 + 1.5x2 ≤ 15
x1 ≥ 0, x2 ≥ 0
• Tous les trois(3) modèles obtenus sont des exemples de problème de programmation linéaire.
1.2 Définition et formulation d’un problème de programmation

linéaire
1.2.1 Définition d’un programmation linéaire
En mathématiques, les problèmes de Programmation Linéaire (PL) sont des problèmes d’optimisation
où la fonction objectif et les contraintes sont toutes linéaires. La programmation linéaire
désigne également la manière de résoudre les problèmes de PL.
C’est un domaine central de l’optimisation, car les problèmes de PL sont les problèmes d’optimisation
les plus faciles (toutes les contraintes y étant linéaires). Beaucoup de problèmes réels de recherche
opérationnelle peuvent être exprimés comme un problème de PL (comme les trois exemples de la
8
section 1.1). Pour cette raison un grand nombre d’algorithmes pour la résolution d’autres problèmes
d’optimisation sont fondés sur la résolution de problèmes linéaires.
Remarque 1.1. Le terme Programmation Linéaire suppose que les solutions à trouver doivent
être représentées en variables réelles. S’il est nécessaire d’utiliser des variables discrètes dans la
modélisation du problème, on parle alors de Programmation Linéaire en Nombres Entiers (PLNE).
Il est important de savoir que ces derniers sont nettement plus difficiles à résoudre que les PL à
variables continues.
La formulation d’un problème d’optimisation comporte toujours les trois étapes suivantes :
1. choix des variables du modèle,
2. formulation de l’objectif (ou critère),
3. formulation des contraintes.
X La première étape consiste à choisir les variables du problème.
Définition 1.1. On appelle variable toute quantité utile à la résolution du problème dont le modèle
doit déterminer la valeur.
Cette définition permet de différencier les variables des paramètres, qui sont des données qui peu-
vent varier, par exemple d’une période à l’autre ou d’un scénario à l’autre.
X La deuxième étape consiste à formuler mathématiquement l’objectif.
Définition 1.2. On appelle fonction objectif d’un problème d’optimisation le critère de choix entre
les diverses solutions possibles.
X La troisième étape est la formulation les contraintes du problème.
Définition 1.3. On appelle contraintes du problème toutes les relations limitant le choix des valeurs
possibles des variables.
Ces relations peuvent être de simples bornes sur les variables. Par exemple, les quantités produites
ne peuvent être négatives. Mathématiquement, on peut écrire : x1 , x2 ≥ 0.
Elles peuvent être plus complexes comme les contraintes de capacité des ressources.
9
1.2.2 Forme algébrique d’un programme linéaire
Un problème sera modélisé par un problème de programmation linéaire si :
• les décisions peuvent être représentées par des nombres réels (généralement positifs),
• les contraintes portant sur ces variables peuvent être représentées par des équations ou des
inéquations linéaires c’est à dire que les variables n’interviennent qu’au premier degré (pas de
carrés, pas de produit de variables),
• le critère de choix peut être représenté par une fonction linéaire des variables que l’on souhait-
era minimiser ou maximiser.
La forme générale d’un problème de programmation linéaire de n variables et p contraintes est :

min ou max f (x) = c1 x1 + c2 x2 + ... + cn xn
sous les contraintes
ai1 x1 + ai2 x2 + ... + ain xn ≤, ≥ ou = bi pour i = 1, ..., p
xj ≥0, pour j = 1, ..., n
Les coefficients cj de la fonction objectif, les coefficients aij du premier membre des contraintes et
les seconds membres bi des contraintes sont des données du problème. Les xj sont les variables
du problème. Enfin, i représente l’indice de la iieme contrainte (i = 1, ..., p) et j l’indice de la j ieme
variable (j = 1, ..., n).
On notera, dans la suite, ce problème par (P).
Définition 1.4. Une solution réalisable est un n-uplet (x1 , ..., xn ) vérifiant toutes les contraintes.
Définition 1.5. Une solution optimale est une solution réalisable qui donne à la fonction objectif la
plus grande (problème de maximisation) ou la plus petite valeur possible (problème de minimisation)
sur l’ensemble des solutions réalisables.
Définition 1.6. La valeur maximale (resp : minimale) de la fonction objectif (à ne pas confondre
avec la solution optimale) est la plus grande valeur (resp : la plus petite) que peut prendre la fonction
objectif sur l’ensemble des solutions réalisables.
X La PL est essentiellement appliquée pour résoudre des problèmes d’optimisation à moyen et

long terme (problèmes stratégiques et tactiques, dans le vocabulaire de la recherche opérationnelle).
10
Les domaines d’application de ces problèmes sont très nombreux aussi bien dans la nature des
problèmes abordés (planification et contrôle de la production, distribution dans des réseaux) que
dans les secteurs d’industrie: industrie manufacturière, énergie (pétrole, gaz, électricité, nucléaire),
transports (aériens, routiers et ferroviaires), télécommunications, industrie forestière, finance.
Les exemples de problème qui relèvent de la programmation linéaire sont fort nombreux. On peut
citer :
• les problèmes de mélange : quelle est la composition optimale d’un produit ?
• les problèmes de détermination optimale de production d’une raffinerie,
• les problèmes de planification de production : quand et à quel moment doit-on planifier la

production d’un bien,
• les problèmes de transport, généralisation du problème de transport classique,
• les problèmes de planification d’horaires,
• les problèmes de fonctionnement d’une flotte de tankers et la mise en place des produits,
• les problèmes de découpe industrielle,
• etc.
S’il est nécessaire d’utiliser des variables discrètes dans la modélisation du problème, on parle alors
de Programmation Linéaire en Nombres Entiers (PLNE).
Un problème de PLNE est un programme linéaire dans lequel il y a la contrainte supplémentaire
que les variables sont entières. Lorsque les variables entières ne peuvent être que 0 ou 1, on parle
de programmation linéaire 0-1 ou binaire.
On parle de programme linéaire mixte lorsque seul un sous-ensemble de variables doivent être
entières et les autres réelles.
1.2.3 Forme matricielle d’un programme linéaire
La propriété de linéarité de la fonction objectif et des contraintes permet de représenter un pro-

gramme linéaire sous forme matricielle. Cette représentation est utile car elle permet d’une part,
de mieux comprendre les problèmes rencontrés lors de l’informatisation d’un algorithme du sim-
plexe. D’autre part, elle permet d’expliquer de façon plus synthétique certains développements plus
théoriques liés à la méthode du simplexe (cf. section 1.5) et aux propriétés de la dualité (cf. section
11
1.6).
Soit n le nombre de variables et p le nombre de contraintes. Posons: cT = (c1 , c2 , ..., cn )1 le vecteur
des coefficients de la fonction objectif; bT = (b1 , b2 , ..., bp ) le vecteur du second membre, c’est à dire
des bornes supérieures. Soit A la matrice de p lignes et n contraintes, notée A(p, n):
 
a a12 . . . a1n
 11 
 
 a21 a21 . . . a2n 
A=  .. .. .. 

 . . . 
 
ap1 ap2 . . . apn
et xT = (x1 , x2 , ..., xn ) le vecteur des variables de décision.

La forme matricielle d’un programme linéaire s’écrit alors en trois (3) lignes:
max cT x
s.c. Ax ≤ b
x≥0
Définition 1.7. L’ensemble réalisable C est l’ensemble défini par:
C = {x ∈ Rn : Ax ≤ b et x ≥ 0}
Remarque 1.2. L’ensemble réalisable C est appelé hyperplan de Rn . C’est une intersection finie
d’hyperplans.
Remarque 1.3. On peut aussi écrire le problème (P) sous la forme:
max cT x
s.c.
x∈C
1.3 Interprétation économique d’un programme linéaire
On considère le problème de programmation linéaire (P) mis sous la forme:

n
X
max z = cj x j
j=1
n
X
s.c. aij xj ≤ bi ∀i = 1, ..., p
j=1
xj ≥ 0, ∀j = 1, ..., n
1 T
c désigne la transposé du vecteur c
12
Cette formulation correspond à la situation suivante:
Une entreprise exerce un ensemble de n activités j. Chacune de ces activités consomme une certaine
quantité de ressources i. On connait la quantité bi de ressource i disponible pour chacune des m
ressources. Chaque activité j peut être exercée avec une quantité xj et on donne la consommation
aij de la ressource i utilisée pour la production d’une unité de l’activité j. Et cj est le profit unitaire
que l’on tire de l’activité j.
Résoudre le problème (P), c’est déterminer les quantités xj (non négatives) auxquelles il faut exercer
les activités j de manière que:
n
• pour toute ressource i la quantité aij xj de ressource i ne dépasse pas bi (ne pas consommer
P
j=1
plus de ressources que l’on en dispose).
n
• le profit total cj xj soit maximum (maximiser le profit de la vente).
P
j=1
1.4 Résolution graphique
De manière très générale, la résolution d’un problème de programmation linéaire nécessite la mise
en oeuvre d’un algorithme. Nous en verrons le principe dans la section 1.5 suivante.
Lorsqu’il n’y a que deux variables de décision, un problème linéaire peut être résolu de manière
purement graphique. C’est ce que nous verrons dans cette partie.
Cette résolution graphique permet de mettre en évidence certaines propriétés que possède n’importe
quel problème de programmation linéaire.
X Considérons le problème de l’exemple 1 :
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 ≤ 200
4x1 + 4x2 ≤ 150
x1 ≥ 0, x2 ≥ 0
Souvenez vous, vous avez certainement représenté au collège des droites dans le plan.
Peut-être avez vous appris à cette époque la notion de coefficient directeur dans la
représentation.
A chaque couple de variables x1 et x2 , on associe un point du plan dont les coordonnées correspon-
dent aux valeurs des variables. Les variables étant positives, ces points sont situés dans l’orthant
positif (le quart Nord-Est du plan) ou R2+ = {(x1 , x2 ) ∈ R × R : x1 ≥ 0, x2 ≥ 0}.
13
Chaque contrainte permet de délimiter une partie du plan. Par exemple, la droite (∆1 ) d’équation
7x1 + 3x2 = 200 définit 2 demi-plans. Au-dessus de cette droite (∆1 ), les coordonnées des points
du plan vérifient 7x1 + 3x2 > 200. On est donc conduit à exclure ces points.
On fait de même pour l’autre contrainte, et on trace la droite d’équation:
∆2 : 4x1 + 4x2 = 150 et on élimine les points situés au dessus de cette droite.
Les solutions réalisables du problème correspondent aux points du plan situés à l’intérieur du
polyèdre (appelée domaine admissible ou domaine réalisable) et sur ses bords.
Il s’agit maintenant de déterminer parmi tous ces points celui ou ceux qui correspondent à la plus
grande valeur possible pour la fonction objectif z = f (x) = f (x1 , x2 ) = 40000x1 + 20000x2 .
Considérons la droite d’équation ∆ : 40000x1 + 20000x2 = k où k est une constante. Tous les
points situés sur cette droite donnent à l’expression 40000x1 + 20000x2 la même valeur k. Ils sont
équivalents du point de vue du profit.
Si on déplace cette droite vers la droite, la valeur de k augmente. Lavaleur limite
  pour k est

175/8 21.875
obtenue pour la droite passant par le point A qui a pour coordonnées  = .
125/8 15.625
La valeur optimale est de f (A) = 40000 ∗ 175/8 + 20000 ∗ 125/8 = 875000 + 312500= 1 187 500.
Remarque 1.4. Graphiquement, ce sont les points correspondant aux points d’intersection des
droites qui définissent la région réalisable:
14
Les solutions (ou points) situées sur le bord (ou frontière) de l’ensemble admissible sont appelés
des solutions de base possibles (admissibles) et non admissibles s’ils sont à l’extérieur du domaine
admissible. Au moins une des solutions admissibles est une solution optimale. Si deux solutions
sont ensuite admissibles, alors tous les points sur le bord reliant ces deux solutions le sont également.
X Interprétation: Pour l’entreprise SIMPA, ceci signifie que la répartition optimale entre les
deux types de produits est de 21.875 pour le produit P1 et 15.625 pour le produit P2 . Le profit
quotidien est de 1 187 500 FCFA.
Nous obtenons pour les contraintes de la main d’oeuvre et des matériaux: (7×175/8)+(3×125/8) =
(1225+375)/8 = 200 (main d’oeuvre), (4×175/8)+(4×125/8) = (175+125)/2 = 150 (matériaux).
On dit que les deux contraintes sont saturées ou liées : elles sont vérifiées avec égalité à l’optimum.
Tout le nombre d’heures de main d’oeuvre et tous les matériaux disponibles sont utilisés.
X Pour l’exemple 2 :
max f (x) = 40000x1 + 80000x2
s.c. x1 + x2 ≤ 10000
2x1 + 6x2 ≤ 48000
3x1 + x2 ≤ 24000
x1 ≥ 0, x2 ≥ 0
15
x1 + x2 = 10000 définit 2 demi-plans. Au-dessus de cette droite (∆1 ), les coordonnées des points
du plan vérifient x1 + x2 > 10000. On est donc conduit à exclure ces points.
On fait de même pour les 2 autres contraintes. On trace les droites d’équation:
∆2 : 2x1 + 6x2 = 48000 et ∆3 : 3x1 + x2 = 24000 et on élimine les points situés au dessus de ces
droites.
polyèdre OABCD et sur ses bords.
grande valeur possible pour la fonction objectif z = f (x) = f (x1 , x2 ) = 40000x1 + 80000x2
Si on déplace cette droite vers la droite, la valeur de k augmente. La valeur limite pour k est
obtenue pour la droite passant par le point B.
On peut conclure que sur l’ensemble du domaine des solutions réalisables, celle qui donne la plus
grande valeur à la fonction objectif correspond au point B dont les coordonnées peuvent être cal-
culées, comme point d’intersection des droites ∆1 et ∆2 (∆1 ∩ ∆2 ={B = (3000, 7000)}. Ainsi,
16
la solution optimale du problème est x1 = 3000, x2 = 7000. Nous noterons la solution optimale
par (x∗1 , x∗2 ) = (3000, 7000). La valeur maximale de la fonction objectif est : z = f (x∗1 , x∗2 ) =
(40000 ∗ 3000) + (80000 ∗ 7000)=600 800 000.
X Interprétation: Pour l’entreprise, ceci signifie que la répartition optimale entre les deux types
d’ordinateurs est de 3 000 ordinateurs de type Core i3 et 7 000 ordinateurs de type Core i7 avec un
profit maximal de 600 800 000 A
C.
Nous obtenons pour les ressources: 3000 + 7000 = 10000 (processeurs), (2 × 3000) + (6 × 7000) =
6000 + 42000 = 48000 (barettes) et (3 × 3000) + 7000 = 10000 < 24000 (assemblage).
On dit que les deux premières contraintes sont saturées ou liées : elles sont vérifiées avec égalité à
l’optimum alors que la troisième contrainte est non saturée ou non liée : il y a une marge entre la
valeur de son premier et celle de son second membre à l’optimum.
L’analyse de cette solution montre que tous les processeurs et toutes les barrettes sont utilisés, mais
qu’il reste du temps d’assemblage disponible.
X Pour l’exemple 3 :
max f (x) = 190000x1 + 260000x2
s.c. 0.5x1 + 1.5x2 ≤ 12
2x1 + 1.5x2 ≤ 15
x1 ≥ 0, x2 ≥ 0
A chaque couple de variables x1 et x2 , on associe un point du plan dont les coordonnées correspon-
dent aux valeurs des variables. Les variables étant positives, ces points sont situés dans l’orthant
positif (le quart Nord-Est du plan) ou R2+ = {(x1 , x2 ) ∈ R × R : x1 ≥ 0, x2 ≥ 0}.
0.5x1 +1.5x2 = 12 définit 2 demi-plans. Au-dessus de cette droite (∆1 ), les coordonnées des points
du plan vérifient 0.5x1 +1.5x2 > 12. On est donc conduit à exclure ces points.
On fait de même pour l’autre contrainte, et on trace la droite d’équation:
∆2 : 2x1 + 1.5x2 = 15 et on élimine les points situés au dessus de cette droite.
polyèdre (appelée domaine admissible ou domaine réalisable) et sur ses bords.
17
grande valeur possible pour la fonction objectif z = f (x) = f (x1 , x2 ) = 190000x1 + 260000x2 .
Si on déplace cette droite vers la droite, la valeur de k augmente. La valeur limite
 pourk est
2 2
obtenue pour la droite passant par le point A qui a pour coordonnées  =  . La
22/3 7.33
valeur optimale est de f (A) = 190000 ∗ 2 + 260000 ∗ 22/3 = 380000 + 1906600.67= 2 200 866.67.
X Interprétation: Pour le GIE, ceci signifie que la répartition optimale du bien est de 2 biens
selon la première technique et 22/3 selon la deuxième technique. Le profit maximal est de 2 200
866.67 FCFA.
Nous obtenons pour les contraintes de la machine et de la main d’oeuvre: (0.5 × 2) + (1.5 × 22/3) =
1 + 11 = 12 (usinage machine), (2 × 2) + (1.5 × 22/3) = 4 + 11 = 15 (main d’oeuvre).
On dit que les deux contraintes sont saturées ou liées : elles sont vérifiées avec égalité à l’optimum.
Tout le temps disponible (nombre d’heures nécessaire) pour la production d’une unité de bien est
utilisé.
18
1.5 Méthode du simplexe
La résolution graphique ne concerne que des problèmes avec 2 variables alors que les problèmes
réels peuvent en avoir plusieurs milliers, voire centaine de milliers. Nous allons dans cette section,
illustrer le principe d’un algorithme de résolution : l’algorithme du simplexe, du à Dantzig ([5, 6]).
On considère le problème de l’exemple 1 de la section 1.1 :
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 ≤ 200
4x1 + 4x2 ≤ 150
x1 ≥ 0, x2 ≥ 0
Cette formulation est appelé forme canonique sous la forme (max, ≤). Les variables x1 et x2 sont
appelées « variables initiales ».
Nous verrons dans cette section ci-dessous, la mise du problème sous forme standard.
1.5.1 Forme standard
Dans un premier temps, on transforme le problème pour qu’il n’y ait que des contraintes d’égalité
afin de manipuler des systèmes d’équations et non d’inéquations.
Définition 1.8. Un problème de programmation linéaire est dit sous forme standard si toutes les
contraintes sont des contraintes d’égalité et toutes les variables sont positives.
Considérons la première contrainte :

7x1 + 3x2 ≤ 200
On introduit une variable positive x3 appelée « variable d’écart » qui mesure l’écart entre le
deuxième et le premier membre de l’inégalité. On obtient :
7x1 + 3x2 + x3 = 200 avec x3 ≥ 0.
On fait de même dans la seconde contrainte :
• 4x1 + 4x2 ≤ 150 devient 4x1 + 4x2 + x4 = 150 avec x4 ≥ 0
Le problème initial est maintenant sous forme standard :
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 + x3 = 200
4x1 + 4x2 + x4 = 150
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
19
Remarque 1.5. Les coefficients des variables d’écart dans la fonction objectif sont nuls.
X Généralisation
Pour simplifier les notations, on peut noter les variables d’écarts par xn+i ∀i = 1, ..., p.
Si le problème d’optimisation comporte n variables et p contraintes de type ≤, alors la forme générale
de la forme standard est :
n+p
X
min ou max f (x) = cj xj = c1 x1 + c2 x2 + ... + cn xn + ... + cn+p xn+p
j=1
sous les contraintes

n
X
aij xj + xn+i = ai1 x1 + ai2 x2 + ... + ain xn + xn+i = bi pour i = 1, ..., p
j=1
xj ≥0, pour j = 1, ..., n + p
ou encore sous forme matricielle :

min ou max cT x
s.c. Ax = b
x≥0
avec c, x ∈ Rn+p , b ∈ Rp et A(p, n + p).
n
Si une contrainte (i) est de type ≥, c’est à dire: aij xj ≥ bi . Alors en introduisant une variable
P
j=1
d’écart xn+i positive ou nulle au premier membre, on obtient une condition équivalente s’écrivant
sous la forme d’une égalité:
n
X
aij xj − xn+i = bi
j=1
La recherche de solutions pour ce type de contrainte sera étudiée dans la section 1.5.7.
X Exemple : Soit le programme suivant:
max z = x1 + x2
s.c. − 8x1 + x2 ≥ −40
x1 + x2 ≥ 8
− x1 − 2x2 ≥ −10
x1 ≥ 0, x2 ≥ 0
On voit que ce programme présente des contraintes d’inégalités du type “≥”, donc pour l’écrire sous
forme standard il suffit, pour chaque contrainte de ce type, d’ajouter une variable d’écart dans le
20
second membre puis de le transposer dans le premier membre ou plus simplement de retrancher une
variable d’écart dans le premier membre. Ainsi on obtient la forme standard :
max z = x1 + x2
s.c. − 8x1 + x2 − x3 = −40
x1 + x2 − x 4 = 8
− x1 − 2x2 − x5 = −10
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
L’ajout des variables dites artificielles sera étudié dans la section section 1.5.7
Proposition 1.1. Tout problème de programmation linéaire peut se mettre au choix sous la forme
canonique ou sous la forme standard.
Preuve: Il suffit de faire les observations suivantes.
1. Minimiser f (x) c’est maximiser −f (x) et changer le signe du résultat obtenu.

n n
2. L’inégalité aij xj ≤ bi est équivalente à l’égalité aij xj + xn+i = bi avec xn+i ≥ 0.
P P
j=1 j=1
n n n
3. L’égalité aij xj = bi est équivalente aux deux inégalités aij xj ≤ bi et − aij xj ≤ −bi .
P P P
j=1 j=1 j=1
0 00 0
4. Si xj est une variable de signe quelconque, on peut lui substituer la différence xj − xj (xj ≥ 0
00
et xj ≥ 0).
X Pour l’étude de solutions particulières, on peut considérons le système d’équations :
7x1 + 3x2 + x3 = 200
4x1 + 4x2 + x4 = 150
Ce système possède une infinité de solutions. Les solutions réalisables du problème sont les solutions
positives de ce système d’équations.
On peut considérer une première solution réalisable, obtenue en donnant à x1 et x2 la valeur 0.
Première solution:
x1 = 0, x2 = 0, x3 = 200 et x4 = 150 et z = 0.
Test d’optimalité pour la première solution: En examinant la fonction objectif (z = 40000x1 +
20000x2 ), on constate que si on augmente la valeur de x1 ou celle de x2 ou celle de x3 , la valeur de
21
la fonction augmentera : la première solution n’est pas optimale.
Construction de la deuxième solution: On construit une nouvelle solution en augmentant une
seule des deux variables x1 ou x2 laissant les deux autres nulles. Le choix entre x1 et x2 peut être
fait en considérant leur coefficient dans la fonction objectif.
Le coefficient de x1 est de 200 (c’est le plus grand) alors que celui de x2 n’est que de 150.
En application du «premier critère de Dantzig» (qu’on verra dans la section 1.5.4), on choisit
d’augmenter x1 tout en laissant x2 nulle.
1.5.2 Correspondance base-sommet, changement de base, itération
X Correspondance base-sommet: l’algorithme du simplexe et les solveurs (programmes informa-

tiques le mettant en oeuvre) ne travaillent que sur des contraintes à l’égalité, donc sur la forme
standard2 .
Dans la méthode du simplexe, le cheminement se fait en se déplaçant d’un sommet du polyèdre au
sommet suivant. Ce cheminement est possible sur les plans algorithmique et informatique car l’on
s’est faire correspondre à tout sommet une base.
On considère le problème de programmation linéaire (P) mis sous la forme :
max z = f (x) = cT x
s.c. Ax = b
x≥0
Définition 1.9. On appelle base associée à (P) toute sous matrice B de A carrée d’ordre p et
inversible.
On notera par N l’ensemble complémentaire (variables hors base).
B variables de base
N variables hors base
Si on isole ces p variables et si on retient les p égalités correspondant aux p contraintes, on a un

système comprenant p inconnus et p équations. Si le système n’est pas dégénéré, il admet une
solution unique.
Souvenez vous, vous avez certainement résolu au lycée des systèmes de deux(2) équations à deux(2)
inconnus et sans doute de trois(3) équations à trois(3) inconnus en utilisant une méthode d’élimination
progressive des variables (méthode de gauss). Peut-être avez vous apris à cette époque la notion
2
la mise en forme standard est faite automatiquement par le solveur qui ajoute les variables d’écart nécessaires.
22
de pivot dans ce processus d’élimination.
Lorsque qu’on choisit p variables (au hasard, pourquoi pas), on définit donc implicitement un sys-
tème de p équation à p inconnues. On peut résoudre ce système à condition de choisir arbitrairement
la valeur de (n + p) - p = n variables.
Si on fixe à zéro (0) les n variables hors base, on obtient une solution qui correspond à un sommet
(une intersection de p hyperplans).
Supposons réordonnée la matrice de A du programme linéaire de façon à ce que les p variables
de base soient au début (idem pour x), et introduisont les notations suivantes: A = [B, N ] et
x = [xB , xN ].
L’équation matricielle Ax = b devient BxB + N xN = b.
Définition 1.10. On appelle solution de base associée à la base B,  la solution particulière du
B1b
système BxB + N xN = b, lorsque xN = 0 c’est à dire x =   . Cette solution de base est
0
dite admissible si xB = B 1 b ≥ 0. On dit aussi que B est une base admissible.
Définition 1.11. Si l’une au moins des composantes de xB est nulle, on dit que la solution de base
est dégénérée. De même on parlera de solution de base admissible dégénérée.
Comme une solution de base est obtenue en mettant à zéro(0) les variables hors base, avec ces
notations, elle est donc caractérisée par les équations suivantes:
n+p
X
aij xj = bi ∀ i = 1, ..., p (1)
j=n+1
X Changement de base: supposons que l’on parte d’une base réalisable. Pour les problèmes pour
lesquels l’origine x = 0 est réalisable, la base correspondante sera constituée par les p variables
d’écart xn+i , ∀i = 1, ..., p. Pour changer de base, on se contentera d’un déplacement local défini de
la façon suivante. On change de base en faisant entrer une variable dans la base et en faisant sortir
de la base une autre variable initialement dans la base.
BxB + N xN = b
xN = 0
xB = B −1 b
X Itération: le processus d’échange entre deux (2) variables revient à se déplacer le long d’une arête
du polyèdre. Chaque changement de base correspond à une itération de l’algorithme du simplexe
et met en oeuvre une opération de pivotage.
23
1.5.3 Principe de la méthode: un peu de théorie
La méthode du simplexe consiste :
• à se donner une solution de base quelconque (par exemple l’origine des coordonnées, si elle
appartient au polyhèdre des solutions) qui correspond à un sommet du polyhèdre;
• et à cheminer le long des arêtes du polyhèdre en se déplaçant d’un sommet à un sommet

adjacent, jusqu’à ce qu’il ne soit plus possible d’améliorer la valeur de la fonction objectif.
Comme le polyhèdre est convexe, on est assuré d’atteindre le maximum (ou le minimum) de
la fonction objectif.
Nous reprenons les p équations initiales :

n
X
aij xj + xn+i = bi ∀ i = 1, ..., p
j=1
et la fonction objectif :
n+p
X
z= cj x j
j=1
En notation matricielle, on a:
Ax = b et cT x = z
avec:
   
x c1
 1
 .. .. 
      
a11 . . . a1n 1 0 ... 0 b1  . . 
 
 
.. .. 
       
. . 
      
 a21 . . . a2n 0 1  b2   xn   cn 
A= .. . . . .. .. ..
, b = 
..
, x=  et c =  
. . .. . . . .
       
 0     xn+1   0 
 .. .. 
       
 . . 
 
ap1 . . . apn 0 . . . 0 1 bp  
   
xn+p 0
où x1 , ..., xn sont les variables initiales et xn+1 , ..., xn+p les variables d’écart.
Soit Ai la iieme colonne de la matirce A, et considérons la solution de base, définie par (1):
n+p
X
Ai xi = b (2)
i=n+1
C’est par définition une solution pour laquelle les variables initiales sont nulles et les variables
d’écart positives ou nulles. Elle donne une valeur notée z0 de la fonction objectif:
n+p
X
z = z0 = ci x i
i=n+1
24
On peut exprimer n’importe quel vecteur Ak (1 ≤ k ≤ n) en fonction des p vecteurs Ai qui
constituent une base de l’espace vectoriel à p dimensions puisqu’ils sont linèairement indépendants.
Ainsi, on a:
n+p
X
Ak = tik Ai , ∀k = 1, ..., n (3)
i=n+1
où les coefficients tik sont les éléments de l’inverse de la matrice formée par les p vecteurs de la base.
Soit k l’accroissement de z qui correspond à Ak :
n+p
X
k = tik ci (4)
i=n+1
On a d’autre part, soit λ un scalaire positif, en multipliant les équations (3) et (4) par λ, on obtient:
n+p n+p
X X
λAk = λtik Ai et λk = λtik ci (5)
i=n+1 i=n+1
En exprimant la solution de base dans (2), on a (on ajoute et retranche λAk ):

n+p n+p
X X
Ai xi = b = Ai xi + λAk − λAk (6)
i=n+1 i=n+1
En utilisant (5) dans (6) et en factorisant par Ai , on obtient:

n+p n+p n+p n+p
X X X X
Ai xi = Ai xi + λAk − λtik Ai = λAk + (xi − λtik )Ai (7)
i=n+1 i=n+1 i=n+1 i=n+1
De même pour la fonction objectif, on a:

n+p
X
z0 + λ(ck − k ) = ci xi + λ(ck − k ) (8)
i=n+1
On obtient finalement, en remplaçant λk par sa valeur:

n+p
X
z0 + λ(ck − k ) = λck + (xi − λtik )ci (9)
i=n+1
D’aprés les équations (7) et (9), la solution de base et le coût réduit peuvent tous s’exprimer en
fonction de xi − λtik (xi − λtik = 0 =⇒ λ = xi
tik
).
X A condition qu’un tik au moins ne soit pas négatif et que λ ne soit pas nul, si l’on donne à λ la
plus petite valeur positive des rapports xi
tik
, i.e.
xi
λ = λ∗ = min
i={n+1,...,n+p} tik
25
tous les termes xi − λ∗ tik sont positifs, sauf un qui est nul, et pour lequel i = i∗ .
On peut alors faire sortir de la base le vecteur Ai∗ et le remplacer par Ak . Il en résulte ainsi une
nouvelle solution de base qui est distincte de la précédente.
Reste à choisir Ak : le changement de base va entrainer une variation de la valeur de z0 égale à
λ(ck − k ). Pour maximiser cette variation, on détermine:
max (ck − k )
k={1,...,n}
et l’on obtient k = k ∗ .
Remarque 1.6. Les k − ck représentent la variation unitaire de la fonction objectif quand on

passe d’une base à l’autre, c’est à dire les coûts marginaux des variables xk .
1.5.4 Critères de Dantzig et test d’optimalité
• Premier critère: On fait entrer dans la base le vecteur Ak tel que la quantité k − ck (si l’on
maximise la fonction objectif) ou ck − k (si on minimise) soit en valeur absolue aussi grande
que possible.
• Deuxième critère: On fait sortir de la base le vecteur Ai pour lequel λ = xi

tik
est aussi petit
que possible (mais positif).
Remarque 1.7. En faisant cette transformation, on transforme la solution initiale en améliorant

la valeur de z.
Test d’optimalité: Cette transformation est à faire jusqu’à ce que tous les coûts marginaux des
variables xk soient négatives ou nulles.
1.5.5 Application à l’exemple 1
La forme standard de l’exemple 1 est donné par :
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 + x3 = 200
4x1 + 4x2 + x4 = 150
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Ainsi, on obtient n = 4 (nombre de variables) et p = 2 (nombre de contraintes). Le premier

tableau (initialisation) du simplexe est donné par le tableau 23.
26
Pour simplifier les calculs, on factorise la fonction objectif par 10 000; et on résout le programme
suivant; et la valeur obtenue à la fin sera multipliée par les 10 000.
max f (x) = 4x1 + 2x2
s.c. 7x1 + 3x2 + x3 = 200
4x1 + 4x2 + x4 = 150
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
i A1 A2 A3 A4
3 7
○ 3 1 0 200 L1
4 4 4 0 1 150 L2
z 4 2 0 0 0 L3
Table 1: premier tableau du simplexe
En appliquant le premier critère de Dantzig, on obtient: le côut le plus élevé est 4 qui correspond
à x1 , donc c’est x1 qui va entrer dans la base (k ∗ =1).
Le deuxième critère de Dantzig donne: min( 200
7
, 150
4
)= 150
4
, qui correspond à x3 qui va sortir de la
base (i∗ = 3).
Tous les coûts marginaux ne sont pas négatifs ou nuls, donc on continue la procédure (le test d’arrêt
n’est pas atteint).
L’élément de la matrice encerclé dans le tableau correspond au pivot (pour i∗ = 3 et k ∗ = 1). C’est
l’élément a31 de la matrice A. Ce sont les formules de Gauss-Jordan[19] que nous allons appliquer
aux éléments de A, b et z.
Le deuxième tableau du simplexe est donné par le tableau 24:

On applique le premier critère de Dantzig, dans le deuxième tableau, on obtient: le côut le plus
élevé est 2
7
qui correspond à x2 , donc c’est x2 qui va entrer dans la base (k ∗ =2).
200 250
3 , 7
16 ) = min( 200
3
, 250
16
)= 250
16
, qui correspond à x4 qui
7 7
va sortir de la base (i∗ = 4).

Tous les coûts marginaux ne sont pas négatifs ou nuls, donc on continue toujours la procédure, et
on passe au tableau suivant.
Le troisième tableau du simplexe est donné par le tableau 25:
Tous les coûts marginaux sont négatifs ou nuls, donc l’algorithme s’arrête. L’optimum est atteint
au point x∗1 = 175
8
et x∗2 = 125
8
, avec une valeur optimale de 475
4
= 118.75.
27
(1) b3
b3 =
a31
(1) a3j
a3j = (∀j)
a31
(1) (1)
bi = bi − ai1 b3 (∀i 6= 3)
(1) (1)
aij = aij − ai1 a3j (∀j, ∀i 6= 3)
(1) (1)
zj = zj − z1 a3j (∀j) valeur des coûts réduits
(1)
z̄ (1) = z̄ + z1 b3 valeur de la fonction objectif
Table 2: Formule de calcul de la nouvelle base, des nouveaux coûts réduits, de la valeur de la
fonction objectif
i A1 A2 A3 A4
0
1 1 3
7
1
7
0 200
7
L1 = L71
0 0
4 0 ○16
7 − 74 1 250
7
L2 =L2 -4L1
0 0
z 0 2
7
− 47 0 − 800
7
L3 =L3 -4L1
Table 3: deuxième tableau du simplexe
i A1 A2 A3 A4
00 0 00
1 1 0 1
4
3
− 16 175
8
L1 =L1 - 37 L2
00 0
2 0 1 − 41 7
16
125
8
L2 = 16
7
L2
00 0 00
z 0 0 − 21 − 81 − 475
4
L3 =L3 - 27 L2
Table 4: troixième tableau du simplexe
Ensuite, on multiplie par les 10 000 qu’on avait factorisé. Ca devient 1 187 500.
Le cheminement de l’algorithme du simplexe (sommet après sommet) est illustré dans le graphique
suivant:
28
Remarque 1.8. • Attention: Le nombre d’itérations n’est pas forcément égale au nombre de
variables initiales ni au nombre de variables d’écart. En pratique, on observe que le nombre
d’itérations requises est de l’ordre de 23 m où m est le nombre de contraintes (ne dépend donc
pas du nombre de variables).
• On constate que dans les tableaux la case dédiée à la fonction objectif indique une valeur
opposée à celle de la fonction objectif correspondant à la solution de base du tableau. Pour
faire en sorte que cette case indique exactement la bonne valeur il faut faire les calculs avec la
formule “valeur de la fonction objectif ” dans le tableau 2. Par exemple dans le tableau 24 de
800
l’exemple précédent pour avoir la valeur de la fonction objectif qui est de 7
, on calcule avec
0 0
la formule L3 =L3 +4L1 .
X Pour l’exemple 2, son tableau du simplexe est donné par le tableau 5. Les calculs sont laissés
aux étudiants sous forme d’exercice.
29
i A1 A2 A3 A4 A5
3 1 1 1 0 0 10000 L1
4 2 6
○ 0 1 0 48000 L2
5 3 1 0 0 1 24000 L3
z 400 800 0 0 0 0 L4
0 0
3 ○23 0 1 - 16 0 2000 L1 =L1 -L2
0
2 1
3
1 0 1
6
0 8000 L2 = 16 L2
0 0
5 8
3
0 0 - 16 1 16000 L3 =L3 -L2
0 0
z 400
3
0 0 - 400
3
0 -6 400 000 L4 =L4 -800L2
00 0
1 1 0 3
2
- 14 0 3000 L1 = 23 L1
00 0 00
2 0 1 - 12 1
4
0 7000 L2 =L2 - 31 L1
00 0 00
5 0 0 -4 1
2
1 8000 L3 =L3 - 38 L1
00 0 00
z 0 0 -200 -100 0 -6 800 000 L4 =L4 - 400
3 1
L
Table 5: Tableau du simplexe de l’exemple 2
1.5.6 Cas particuliers et compléments
1. Problème infaisable:
Un programme linèaire n’admet pas de solution si les contraintes sont incompatibes entre
elles. Ainsi, le problème:
max z = x1 + x2
s.c. − 8x1 + x2 ≥ −40
x1 + x2 ≥ 8
− x1 − 2x2 ≥ −10
x1 ≥ 0, x2 ≥ 0
est insoluble.
2. Il peut y avoir indétermination sur le choix des variables à faire entrer dans la
base : il suffit que l’une des quantités des coûts marginaux soient égales. Faute de critère
raisonnable, on choisit généralement de façon arbitraire. Toutefois, ceci peut allonger le temps
de résolution du programme.
3. Il peut y avoir également indétermination sur le choix des variables à faire sortir
30
de la base. On est alors dans le cas de la dégénérescence et c’est une infinité de solutions
optimales qu’admet le programme.
4. Optimum non borné.

Le problème suivant n’admet pas un optimum borné.
max z = x1 + 2x2
s.c. − 2x1 + x2 ≤ 2
− x1 + 2x2 ≤ 5
x1 − 4x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
1.5.7 Base de départ et variables artificielles
Lorsque l’origine (x = 0) ne correspond pas au programme réalisable, on ajoute automatiquement

des variables artificielles de façon à ce que l’on puisse toujours constituer aisément une base
initiale réalisable à partir de l’origine.
n
Supposons une contrainte initiale de type inférieure ou égale (i.e. aij xj ≤ bi ∀i = 1, ..., p) et telle
P
j=1
que bi > 0. Aprés introduction de la variables d’écart, cette contrainte s’écrit, on l’a vu, sous la
forme suivante (programme linéaire sous forme standard):
n
X
aij xj + xn+i = bi ∀ i = 1, ..., p
j=1
Pour construire une base initiale, on peut dans ce cas choisir la variable xn+i dans la base. En effet,
en posant xj = 0 pour tout j (variables hors base) on obtient xn+i = bi avec xn+i > 0.
n
X En revanche, adopter la même procédure pour une contrainte supérieure de type
P
aij xj > bi
j=1
conduirait à une base non réalisable (ei = −bi ):
n
X
aij xj − xn+i = bi et xn+i ≥ 0
j=1
On introduit dans ce cas la variable artificielle ei > 0, de façon à pouvoir l’inclure dans la base
initiale.
n
X
aij xj − xn+i + ei = bi et xn+i ≥ 0 et ei ≥ 0
j=1
La base initiale est construite en posant xj = 0, xn+i = 0 ( variables hors base) et ei = bi (ei dans
la base).
31
Dans une première variante de la méthode du simplexe (la méthode du grand M), on fixe des
pénalités (coûts) très élevés aux variables artificielles (M nombre réel positif très grand).
Dans le cadre d’une maximisation, on pose:
n
X
max cj x j − M e i
j=1
Pour une minimisation:

n
X
min cj x j + M e i
j=1
Au cours des itérations, l’algorithme du simplexe va progressivement annuler les variables artifi-
cielles.
• Si toutes les variables artificielles s’annulent au cours du déroulement de l’algorithme, le pro-
gramme devient réalisable au regard des contraintes initiales.
• Si à l’optimum, au moins une variable artificielle reste strictement positive, alors le problème
initiale n’a pas de solution optimale.
X Dans une autre implantation plus classique de la méthode du simplexe, on met en oeuvre la
méthode des deux phases. Dans une première phase, on prend comme fonction objectif la
somme des variables artificielles que l’on minimise cherchant ainsi à les annuler. Si la somme est
nulle, on aborde la deuxième phase en supprimant les variables artificielles devenues inutiles puis
on change de critère en reprenant la fonction objectif du problème initial.
Remarque 1.9. Pour diminuer le nombre d’itérations et gagner ainsi du temps de résolution de
l’algorithme du simplexe, on a intérêt à construire une base de départ la plus intéressante possible.
Cette phase technique s’appelle recherche d’une base avancée ou crashing.
X Exemple : Soit le programme suivant:
max f (x) = x2
s.c. 3x1 + 4x2 ≥ 9
5x1 + 2x2 = 8
3x1 − x2 ≤ 0
x1 ≥ 0, x2 ≥ 0
32
L’introduction des variables d’écart et artificielles donne:
3x1 + 4x2 − x3 + x4 = 9
5x1 + 2x2 + x5 = 8
3x1 − x2 + x6 = 0
x1 ≥ 0, x2 ≥ 0, ..., x6 ≥ 0
1. Méthode du grand M . On résout le programme suivant :
max x2 − M x4 − M x5
s.c. 3x1 + 4x2 − x3 + x4 = 9
5x1 + 2x2 + x5 = 8
3x1 − x2 + x6 = 0
x1 ≥ 0, x2 ≥ 0, ..., x6 ≥ 0
On obtient les tableaux du simplexe suivants avec les variables artificielles :
i A1 A2 A3 A4 A5 A6
4 3 4 -1 1 0 0 9 L1
5 5 2 0 0 1 0 8 L2
6 3 -1 0 0 0 1 0 L3
z 8M 1+6M -M 0 0 0 17M L5
Table 6: Initialisation
i A1 A2 A3 A4 A5 A6
0 0
4 0 5 -1 1 0 -1 9 L1 =L1 − 3L3
0 0
5 0 11/3 0 0 1 -5/3 8 L2 =L2 − 5L3
0
1 1 -1/3 0 0 0 1/3 0 L3 =L3 /3
0 0
z 0 1+26M/3 -M 0 0 -8M/3 17M L5 =L5 − 8M L3
Table 7: Itération 1
33
i A1 A2 A3 A4 A5 A6
00 0
2 0 1 -0.2 0.2 0 -0.2 1.8 L1 =L1 /5
00 0 00
5 0 0 -14/15 -11/15 1 -14/15 1.4 L2 =L2 − (11/3)L1
00 0 00
1 1 0 4/15 1/15 0 4/15 0.6 L3 =L3 + (1/3)L1
00 0 00
z 0 0 (3+11M)/15 (-3-26M)/15 0 (3-14M)/15 (9-7M)/5 L5 =L5 − (1 + 26M )/3)L1
i A1 A2 A3 A4 A5 A6
000 00 000
2 0 1 0 0 3/11 -5/11 24/11 L1 =L1 + 0.2L2
000 00
3 0 0 1 -1 15/11 -14/11 21/11 L2 =L2 /(11/15)
000 00 000
1 1 0 0 0 1/11 2/11 8/11 L3 =L3 + (1/15)L2
000 00 000
z 0 0 0 -M -(11M+3)/11 5/11 24/11 L5 =L5 − (3 + 11M )/15)L2
i A1 A2 A3 A4 A5 A6
0000 000 0000
2 2.5 1 0 0 1/2 -5/11 4 L1 =L1 + (5/11)L3
0000 000 0000
3 7 0 1 -1 2 -14/11 7 L2 =L2 + (14/11)L3
0000 000
6 11/2 0 0 0 1/2 2/11 4 L3 =L3 /(2/11)
0000 000 0000
z -2.5 0 0 0 -M-0.5 0 4 L4 =L4 − (5/11)L3
2. Méthode à deux phases. On résout le programme en deux phases :
• Phase 1: On résout le programme
min x4 + x5
s.c. 3x1 + 4x2 − x3 + x4 = 9
5x1 + 2x2 + x5 = 8
3x1 − x2 + x6 = 0
x1 ≥ 0, x2 ≥ 0, ..., x6 ≥ 0,
Dans le tableau du début on introduit la contrainte Z = x2 ⇐⇒ − x2 + Z = 0 pour

faciliter le passage de la phase 1 à la phase 2.
En effet cela permettra d’obtenir directement les coûts réduits de la phase 2.
34
On obtient les tableaux du simplexe suivants avec les variables artificielles :
i A1 A2 A3 A4 A5 A6 Z
4 3 4 -1 1 0 0 0 9 L1
5 5 2 0 0 1 0 0 8 L2
6 3 -1 0 0 0 1 0 0 L3
Z 0 -1 0 0 0 0 1 0 L4
z -8 -6 1 0 0 0 0 17 L5
Table 11: Initialisation
i A1 A2 A3 A4 A5 A6 Z
0 0
4 0 5 -1 1 0 -1 0 9 L1 =L1 − 3L3
0 0
5 0 11/3 0 0 1 -5/3 0 8 L2 =L2 − 5L3
0
1 1 -1/3 0 0 0 1/3 0 0 L3 =L3 /3
0 0
Z 0 -1 0 0 0 0 1 0 L4 =L4 − 0L3
0 0
z 0 -26/3 1 0 0 8/3 0 17 L5 =L5 + 8L3
i A1 A2 A3 A4 A5 A6 Z
00 0
2 0 1 -0.2 0.2 0 -0.2 0 1.8 L1 =L1 /5
00 0 00
5 0 0 -14/15 -11/15 1 -14/15 0 1.4 L2 =L2 − (11/3)L1
00 0 00
1 1 0 4/15 1/15 0 4/15 0 0.6 L3 =L3 + (1/3)L1
00 0 00
Z 0 0 -0.2 0.2 0 -0.2 1 1.8 L4 =L4 +L1
00 0 00
z 0 0 -11/15 26/15 0 14/15 0 1.4 L5 =L5 + (26/3)L1
35
i A1 A2 A3 A4 A5 A6 Z
000 00 000
2 0 1 0 0 3/11 -5/11 0 24/11 L1 =L1 + 0.2L2
000 00
3 0 0 1 -1 15/11 -14/11 0 21/11 L2 =L2 /(11/15)
000 00 000
1 1 0 0 0 1/11 2/11 0 8/11 L3 =L3 + (1/15)L2
000 00 000
Z 0 0 0 0 3/11 -5/11 1 24/11 L4 =L4 + 0.2L2
000 00 000
z 0 0 0 1 1 0 0 0 L5 =L5 + (11/15)L2
On constate qu’on a obtenu une valeur optimale nulle (les variables artificielles sont
toutes hors base) alors le problème admet une solution réalisable. On peut passer à la
phase 2.
• Phase 2: Lorsque les variables artificielles on été annulées dans la phase 1, on résout le
programme suivant:
max x2
s.c. 3x1 + 4x2 − x3 = 9
5x1 + 2x2 = 8
3x1 − x2 + x6 = 0
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x6 ≥ 0,
i A1 A2 A3 A6
000
2 0 1 0 -5/11 24/11 L1
000
3 0 0 1 -14/11 21/11 L2
000
1 1 0 0 2/11 8/11 L3
000
Z 0 0 0 5/11 24/11 L4
1.6 Dualité
La méthode du simplexe permet d’obtenir une solution optimale à tout programme linéaire en
variables continues (non entières). La théorie de la dualité donne d’autres informations caractérisant
une solution optimale.
36
i A1 A2 A3 A6
0000 000 0000
2 2.5 1 0 0 4 L1 =L1 + (5/11)L3
0000 000 0000
3 7 0 1 0 7 L2 =L2 + (14/11)L3
0000 000
6 5.5 0 0 1 4 L3 =L3 /(2/11)
0000 000 0000
Z -2.5 0 0 0 4 L4 =L4 + (5/11)L3
1.6.1 Variable duale associée à une contrainte
Nous considérons une solution optimale d’un programme linéaire et une de ses contraintes se présen-
tant sous la forme d’une inégalité. Dans ce cas deux (2) situations peuvent se présenter:
• cette contrainte n’est pas saturée (la variable d’écart correspondante est différente de zéro
(0)): donc toute modification locale du second membre ne modifiera ni la solution optimale
trouvée, ni bien sûr la valeur de la fonction objectif optimale.
• cette contrainte est saturée: lorsque le problème n’est pas dégénéré et si on la resserre davan-
tage, la solution optimale va se déplacer et la fonction objectif va se dégrader. Inversement,
si l’on relâche cette contrainte, la fonction objectif va s’améliorer.
Définition 1.12. On appelle valeur duale associée à une contrainte, la quantité dont varie la
fonction objectif lorsqu’on fait varier d’une unité la valeur du second membre.
Remarque 1.10. Si la fonction objectif est monétaire, la valeur duale représente un coût de la
ressource correspondante. Mais ce coût n’est pas une donnée, c’est un résultat de l’optimisation qui
tient compte de l’ensemble des contraintes saturées.
Ces valeurs sont donc très utiles dans l’analyse d’une solution optimale. Elles permettent de con-
naitre les contraintes les plus contraignantes, celles dont une modification permettrait le plus grand
gain marginal.
1.6.2 Dual d’un programme linéaire
A tout programme linéaire, on peut associer un autre programme linéaire appelé programme dual.
Considérons un programme linéaire sous forme canonique, ce programme sera appelé programme
37
primal.
n
X
max cj xj
j=1
n
X
s.c. aij xj ≤ bi ∀i = 1, ..., p (10)
j=1
xj ≥ 0, ∀j = 1, ..., n
Le programme linéaire dual est construit en associant à toute contrainte i du primal, une variable
duale yi et à toute variable j du primal, une contrainte. Les coûts associés aux variables du dual
sont les seconds membres du primal et les seconds membres du dual sont les coûts du primal.
p
X
min bi yi
i=1
n
X
s.c. yi aij ≥ cj ∀j = 1, ..., n (11)
i=1
yi ≥ 0, ∀i = 1, ..., p
Ou encore sous forme matricielle:

Primal:
max cT x
s.c. Ax ≤ b
x≥0
Dual:
min bT y
s.c. AT y ≥ c
y≥0
Remarque 1.11. Le dual du dual donne le primal.
La démonstration (facile) est laissée aux étudiants sous forme d’exercice.
X Interprétation du dual
Un acheteur souhaite acheter les ressources i, i ∈ {1, ..., p} à une entreprise (celle considérée dans
l’interprétation économique du problème primal de la section 1.3). L’acheteur cherche donc le prix
yi (non négatifs) d’une unité de ressource i qu’il est prêt à payer pour que:
38
p
• son prix total d’achat bi yi soit minimal
P
i=1
p
• l’entreprise accepte de vendre si: yi aij ≥ cj .
P
i=1
1.6.3 Théorème de la dualité
Ce théorème met en relation les solutions de ces deux (2) programmes linéaires (primal et dual):
de la solution de l’un on déduit celle de l’autre.
Théorème 1.1. Si les programmes primale et dual possèdent l’un et l’autre des solutions admissi-
∗
bles, alors le primal admet une solution optimale {x∗j , x∗n+i }, le dual une solution optimale {yi∗ , yp+j }
telles que:
n p
X X
cj x∗j = bi yi∗
j=1 i=1
yi∗ x∗n+i = 0
x∗j yp+j
∗
=0
Remarque 1.12. Grâce à la théorie de dualité, la méthode du simplexe donne toutes les valeurs
duales d’un programme linéaire lorsqu’on a une solution de base optimale.
1.6.4 Application à l’exemple 1
Nous rappelons le problème (primal) qui s’écrit:
max f (x) = 40000x1 + 20000x2
s.c. 7x1 + 3x2 ≤ 200
4x1 + 4x2 ≤ 150
x1 ≥ 0, x2 ≥ 0
Le problème dual est donné par:
min g(x) = 200y1 + 150y2
s.c. 7y1 + 4y2 ≥ 40000
3y1 + 4y2 ≥ 20000
y1 ≥ 0, y2 ≥ 0
XLa méthode du simplexe donne à l’optimum la solution du programme dual. Il s’agit là d’un
résultat d’une portée pratique considérable qui donne un avantage certain à la méthode du simplexe
39
sur toute autre méthode intérieur.
Ainsi:
• il n’est pas nécessaire de résoudre le programme dual pour connaitre les valeurs duales asso-
ciées.
• si le programme dual est plus facile à résoudre que le primal, il est plus intéressant de le
résoudre et on obtiendra à l’optimum la valeur du programme primal recherché en prenant les
valeurs duales du problème dual résolu (en effet, on a vu que le dual du dual est le primal).
Nous reprenons le dernier tableau du simplexe de l’exemple 1 (tableau 17). La solution optimale
i A1 A2 A3 A4
00 0 00
1 1 0 1
4
3
− 16 175
8
L1 =L1 - 37 L2
00 0
2 0 1 − 41 7
16
125
8
L2 = 16
7
L2
00 0 00
z 0 0 − 21 − 81 − 475
4
L3 =L3 - 27 L2
Table 17: troixième et dernier tableau du simplexe
du dual se trouve dans la ligne des coûts réduits (z); et les valeurs sont prises en valeurs absolues.
Il faut compter à partir des variables d’écart (donc colonne A3 ). On obtient:
1 1
y3 = , y4 =
2 8
XVérification du théorème de la dualité:

g(y) = (200 ∗ 21 ) + (150 ∗ 18 ) = 100 + 18.75 = 118.75. Reste uniquement à multiplier par les 10 000
qu’on avait factiorisé dans la résolution du primal. On retrouve la valeur optimale de 1 187 500.
1.7 Analyse de sensibilité
Nous abordons ici l’analyse de sensibilité3 de la résolution d’un problème de programmation linéaire.
Dans un premier temps nous étudions les conséquences d’une variation d’un coefficient de la fonction
objectif, puis celles du second membre d’une contrainte (ressources) donnée. Tout problème de
programmation linéaire donne lieu à ce type d’analyse et les résultats que nous allons obtenir ici
sont généraux.
En général, cette étude de sensibilité intervient lorsque :
3
pour une étude graphique, le cas général sera étudié en Travaux Pratiques
40
• on veut évaluer les conséquences d’un changement de politique modifiant certaines données
du problème,
• les données du problème ne sont pas exactement connues, où il faut déterminer dans quelle
circonstance cela affecte la solution proposée.
Nous changeons un peu d’exemple et reprenons l’exemple 3 de la section 1.1, où le GIE peut
fabriquer un même bien selon deux techniques différentes de production utilisant les services d’une
même machine et de la main d’oeuvre. Le formulation était donnée par:
max f (x) = 1900x1 + 2600x2
s.c. 0.5x1 + 1.5x2 ≤ 12
2x1 + 1.5x2 ≤ 15
x1 ≥ 0, x2 ≥ 0
   
2 2
Le point A solution du problème a pour coordonnées  = . La valeur optimale
22/3 7.33
est de f (A) = 1900 ∗ 2 + 2600 ∗ 22/3 = 22866.67.
1.7.1 Variation d’un coefficient de la fonction objectif
La modélisation et la résolution du modèle a été faite en supposant que la marge unitaire, selon
que le bien est fabriqué à l’aide de la première technique, était de 1900 FCFA. Faut-il produire
davantage de bien avec cette première technique quitte à dévaforiser la production via la deuxième
technique ? La marge p1 selon que le bien est fabriqué à l’aide de la première devient un paramètre
du problème qui s’écrit maintenant :
max f (x) = p1 x1 + 2600x2
s.c. 0.5x1 + 1.5x2 ≤ 12 (1)
2x1 + 1.5x2 ≤ 15 (2)
x1 ≥ 0, x2 ≥ 0
Analysons graphiquement les conséquences de la variation de la marge selon que le bien est produit
avec la première technique.
La droite représentative de la marge sur coût variable avait pour équation 1900x1 +2600x2 = con-
stante. La variation de la marge pour la production de bien avec la première technique implique
que le coefficient de x1 dans cette équation varie et donc que la pente de la droite représentative de
41
la marge varie.
Tant que la pente de cette droite reste comprise entre celle des droites (1) et (2)4 , le raisonnement
fait lors de la résolution graphique conduit à la conclusion que la solution associée au point A est
toujours optimale.
L’intervalle de variation de p1 est donné par :
1/3 ≤ p1 /2600 ≤ 4/3
Soit à:
2600/3 ≤ p1 ≤ 10400/3 ou encore 866.67 ≤ p1 ≤ 3466.67
On a donc mis en évidence un intervalle de variation du coefficient de x1 dans la fonction objectif

sur lequel la solution optimale n’est pas changée.
Ceci nous conduit à la conclusion suivante: tant que la marge selon que le bien est fabriqué à l’aide
de la première technique reste entre 2600/3 et 10400/3, il faut continuer à produire 2 unités de
biens avec la première technique et 22/3 à partir de la deuxième technique. Pour ces mêmes valeurs
de p1 , la valeur maximale du profit total sera égale à :
22 57200
2p1 + 2600 ∗ ( ) = 2p1 + = 2p1 + 19066, 67.
3 3
1.7.2 Variation d’un coefficient du second membre
Actuellement, la capacité d’usinage de la machine est de 12 heures. Mais l’incertitude sur le nombre
total d’heures disponible susceptible d’être ajouté est grande. On voudrait savoir quel serait l’impact
sur la production du même bien si cette quantitée est modifiée. L’analyse graphique peut nous
apporter une réponse. La contrainte portant sur la machine est représentée par la droite d’équation
0.5x1 + 1.5x2 = 12 passe à 0.5x1 + 1.5x2 = 12 + α (où α ∈ R). Graphiquement cela signifie que la
contrainte (1) se déplace parallèlement à elle-même, vers le haut si α est positif, vers le bas si α est
négatif.
On constate alors que le point A intersection des droites (1) et (2) en lequel se trouve actuellement
la solution optimale se déplace sur la droite (2). Comme les pentes des droites (1) et (2) ne sont pas
changées, la solution optimale reste à l’intersection des contraintes (1) et (2), à condition cependant
que ce point reste dans le domaine des solutions réalisables.
Dans ces conditions, pour avoir la solution optimale, il suffit de déterminer les coordonnées du point
4
l’optimum est donné par l’intersection des ces deux hyperplans
42
d’intersection des droites (1) et (2). On obtient :

 0.5x + 1.5x = 12 + α (1)
1 2
 2x + 1.5x = 15 (2)
1 2
L’opération (1)-(2) donne: 0.5x1 − 2x1 = 12 + α − 15 =⇒ − 32 x1 = −3 + α =⇒ x1 = 2 − 23 α.

En remplaçant dans (2) on a: 32 x2 = 15 − 2x1 = 15 − 2(2 − 32 α) = 11 + 43 α =⇒ x2 = 22
3
+ 89 α.
Ces
 valeurs correspondent
 à la solution optimale,
 à condition que cette solution soit réalisable.
 x ≥0  2 − 2α ≥ 0  α≤3
1 3
⇐⇒ ⇐⇒
 x ≥0  22 + 8 α ≥ 0  α ≥ − 33
2 3 9 4
Soit − 33
4
≤ α ≤ 3.
Tant que α reste compris entre −33/4 et 3, la solution optimale reste à l’intersection des contraintes
(1) et (2) : c’est à dire que les nombres d’heures de machine et de main d’oeuvre continuent tou-
jours d’être utilisés entièrement. Les quantités à fabriquer dépendent cependant de α, c’est à dire
du nombre d’heures de machine disponibles.
Pour α d’heures supplémentaires, la production selon que le bien est produit par le premier tech-
nique diminue de 23 α alors que selon qu’il est fabriqué par la deuxième technique augmente de 89 α.
La variation du profit sera alors égale à 1900 ∗ ( 23 α) + 2600 ∗ ( 98 α) = 32200
3
α.
Chaque heure d’usinage (de la machine) supplémentaire pourrait faire augmenter la marge sur
coût variable de 32200/3, ou au contraire, toute diminution de la capacité d’usinage de la machine
la fera diminuer de 32200/3 par heure en moins, et ceci sur un intervalle allant de −33/4 heures à
+3 heures.
De cette information on doit pouvoir tirer les conséquences sur l’intérêt que l’on pourrait avoir à
trouver un autre fournisseur susceptible de fournir lui-aussi cette heure machine à un prix qui, le cas
échéant, pourrait être supérieure à la marge actuelle, compte-tenu de ce que cela peut rapporter.
43
2 PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS
Nous abordons dans ce chapitre une nouvelle catégorie de problèmes : les problèmes de program-
mation linéaire en nombres entiers. Lorsqu’il n’y a que deux (2) variables de décision, ce problème
en variables entières peut être aussi résolu de manière graphique, mais le représentation diffère de
celle du chapitre précédent. Lorsqu’il y a un plus grand nombre de variables (supérieur ou égal à
trois (3)), nous choisissons l’algorithme global de plan coupant, les coupes de Gomory, que nous
verrons dans la section 2.2. Nous présenterons, dans les sections qui suivent, quelques-uns des très
nombreux problèmes susceptibles d’être modélisés par un problème de programmation linéaire en
nombres entiers, c’est à dire des problèmes d’optimisation dans lesquelles variables sont astreintes
à ne prendre que des valeurs entières (ou certaines valeurs entières).
Il s’agit là d’un des problèmes les plus riches et les plus actifs de la programmation mathématique.
2.1 Formulation
Définition 2.1. Un problème de Programmation Linéaire en Nombres Entiers (PLNE) est un

problème de Programmation Linéaire (PL) avec toutes ou une partie des variables qui doivent être
entières, voire restreintes à 0 et 1 comme valeur.
On dit que les variables sont soumises à des contraintes d’intégrité.

Dans certains problèmes, les variables de décision sont, par nature, entières, mais nous allons
voir que, dans de nombreux cas la modélisation nécessite l’introduction de variables booléennes,
c’est-à-dire qui ne peuvent prendre que la valeur 0 ou 1.
La forme matricielle d’un programme linéaire en nombres entiers pures noté (Pplne ) s’écrit en
trois (3) lignes:
max cT x
s.c. Ax ≤ b
x ≥ 0, xj entier (∀j = 1, ..., n)
On remarque que (Pplne ) est du même type que le problème du chapitre 1.2 et que dans ce cas
x ∈ Zn+ (c’est à dire xj ∈ Z+ ∀j = 1, ..., n).
Définition 2.2. Par opposition, le problème obtenu à partir de (Pplne ) en relaxant (en "oubliant")
les contraintes d’intégrité sera appelé la relaxation continue de (Pplne ).
44
X Il pourra se faire, dans certains cas, que toutes les variables ne soient pas astreintes à être en-
tières, mais seulement certaines d’entres elles. Dans ce cas on parle de programmation linéaire
mixte5 .
Lorsque toutes les variables sont 0 ou 1, on parle de programmation linéaire binaire.
Soit (P) le programme linéaire en nombres entiers suivant:
max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 ≤ 59
x1 , x2 entiers ≥ 0
Figure 1: Résolution graphique
La solution continue est donnée par: x1 = 5.9 et x2 = 0.

Cette solution n’étant pas entière, on va appliquer une méthode pour obtenir une solution entière.
5
Pour cette classe de problèmes, la méthode de partitionnement de Benders (1962) [3] permet de ramener de tels
problèmes à la résolution d’une séquence de programmes linéaires en nombres entiers purs (c’est à dire dans lesquels
toutes les variables sont astreintes à prendre des valeurs entières).
45
Tout d’abord on résout graphiquement la relaxation continue du programme.
Soit (D) : 10x1 + 12x2 = 59. On trace la droite puis on délimite le domaine réalisable pour obtenir
la solution optimale atteinte au point (5.9, 0) de valeur optimale 59. A présent pour trouver une
solution entière on teste parmi les points de coordonnées entières dans le domaine réalisable. Et
pour limiter les points à tester on trace la droite de la fonction objectif soit ∆ : 10x1 + 11x2 = 59.
Les points de coordonnées entières les plus proches de la droite ∆ sont les meilleurs candidats.
Ainsi on voit sur le graphique que les points (1, 4), (2, 3), (3, 2) et (4, 1) sont les proches de ∆. Pour
les départager on va calculer la valeur de la fonction objectif en ces points. On a: f (1, 4) = 54,
f (2, 3) = 53, f (3, 2) = 52 et f (4, 1) = 51. Ainsi on conclut que la solution optimale de (P) est
x∗1 = 1 et x∗2 = 4 (entière) avec f (x∗ ) = 54.
2.2 Coupes de gomory
On suppose avoir à résoudre un programme linéaire en variables entières qu’on peut définir comme
suit :
(P ) : min f (x)
s.c.
Ax = b
x ≥ 0 (entier).
Il s’agira dans un premier temps de résoudre la relaxation continue (Prel ) de ce programme (P). Si la
solution est entière alors on a aussi une solution optimale du PLNE initiale. Dans le cas contraire il
faudra trouver une bonne coupe qui permettra de restreindre le domaine de recherche de la solution
à un sous domaine ne contenant pas la solution optimale de la relaxation continue.
Soit B la base associée à la solution optimale de (Prel ). On sait déjà que lorsqu’on a une base
admissible, l’équation matricielle peut s’écrire sous la forme suivante :
BxB + N xN = b ⇒ xB = B −1 b − B −1 N xN (12)
On va noter b̄ = (b̄i ) = B −1 b et ᾱ = (ᾱij ) = B −1 N . Remarquons bien que b̄ est un vecteur et ᾱ est

une matrice autrement dit chaque ᾱi est une ligne i de la matrice B −1 N . On va donc regarder ce
qui se passe sur une ligne i. Ainsi le sur la ième ligne on a l’équation matricielle (12) qui s’écrit :
X
xiB + ᾱij xjN = b̄i (13)
j
On va introduire les notations suivantes :
46
• E(a) : la partie entière de a.
• {a} : la partie décimale c’est à dire {a} = a − E(a) > 0.
De (13) on tire :
X
xiB + (E(ᾱij ) + {ᾱij })xjN = E(b̄i ) + {b̄i }
j
X X
xiB + E(ᾱij )xjN + {ᾱij }xjN = E(b̄i ) + {b̄i } (14)
j j
avec {ᾱij } ≥ 0 et xjN ≥ 0.

De (14) on déduit :
X
xiB + E(ᾱij )xjN ≤ E(b̄i ) + {b̄i }
j
Si xiB et xjN sont des entiers alors on en déduit :

X
xiB + E(ᾱij )xjN ≤ E(b̄i ) + {b̄i } (15)
j
On fait la différence (15)-(14), on obtient :

X j j
− {ᾱi }xN ≤ −{b̄i }
j
X
{ᾱij }xjN ≥ {b̄i } ∀i (16)
j
(16) est appelé “Coupe de Gomory”. Elle sera ajoutée aux contraintes du problème initiale et on
résout la relaxation continue de ce nouveau problème obtenu par le simplexe. Si on trouve une so-
lution entière alors la solution optimale du problème initiale est trouvée sinon on répète le processus.
X Exemple Soit (P) le programme linéaire en nombres entiers suivant:
max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 ≤ 59
Résoudre avec les coupes de Gomory.

X Correction Il faut tout d’abord résoudre la relaxation continue du programme qui est donnée
par :
(Prel ) : max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 ≤ 59
x1 , x2 ≥ 0
47
Et la forme standard est donnée par :
max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 + x3 = 59
x1 , x2 , x3 ≥ 0
Une solution initiale de base est donnée par x1 = x2 = 0 et x3 = 59. Le dernier tableau du simplexe
est donné par :
i A1 A2 A3
1 1 1.2 0.1 5.9
z 0 1 1 -59
Table 18: Dernier tableau
Ainsi la solution de base est x1 = 59, x2 = 0.

On a : ᾱ1 = (1.2, 0.1) et b̄ = 5.9.
On va déterminer la coupe (ici une seule puisqu’on a une seule ligne) :
{1.2}x2 + {0.1}x3 ≥ {5.9}
0.2x2 + 0.1x3 ≥ 0.9
On déduit de la forme standard x3 = −10x1 −12x2 +59 puis on remplace dans l’équation précédente
:
0.2x2 + 0.1(−10x1 − 12x2 + 59) ≥ 0.9
x1 + x 2 ≤ 5
On ajoute cette dernière équation au programme (Prel ) on obtient :
0
(Prel ) : max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 ≤ 59
x1 + x2 ≤ 5
x1 , x2 ≥ 0
On résout le programme et on trouve le dernier tableau du simplexe : La solution optimale est
48
i A1 A2 A3 A4
2 1 1 0.5 -5 4.5
1 1 0 -0.5 6 0.5
z 0 0 0.5 5 -54.5
donnée par : x1 = 4.5, x2 = 0.5 et la valeur optimale est de 54.5. On constate que cette solution
optimale n’est pas entière on refait le processus de coupe.
• Coupe 1 :
{0.5}x3 + {−5}x4 ≥ {4.5}
0.5x3 ≥ 0.5
x3 ≥ 1
En remplaçant x3 = −10x1 − 12x2 + 59 dans l’inégalité précédente on obtient :
−10x1 − 12x2 + 59 ≥ 1
10x1 + 12x2 ≤ 58
• Coupe 2 :
{−0.5}x3 + {6}x4 ≥ {0.5}
0.5x3 ≥ 0.5
x3 ≥ 1
En effet {−0.5} = −0.5 − E(−0.5) = −0.5 − (−1) = 0.5.

Finalement on trouve :
10x1 + 12x2 − 59 ≥ 1
10x1 + 12x2 ≤ 58
On trouve la même coupe pour les deux lignes : 10x1 + 12x2 ≤ 58.
49
On l’ajoute dans le programme (Prel ) :
00
(Prel ) : max f (x) = 10x1 + 11x2
s.c. 10x1 + 12x2 ≤ 59
x1 + x2 ≤ 5
10x1 + 12x2 ≤ 58
x1 , x2 ≥ 0
En résolvant ce nouveau programme on trouve le dernier tableau du simplexe : On trouve la solution
i A1 A2 A3 A4 A5
3 0 0 1 0 -1 1
1 1 0 0 6 -0.5 1
2 0 1 0 -5 0.5 4
z 0 0 0 5 0.5 -54
optimale x1 = 1, x2 = 4 et la valeur optimale 54. La solution est entière donc il s’agit aussi d’une
solution optimale du programme (P).
Remarque 2.1. • Il peut arriver d’effectuer plusieurs itérations de coupe avant de trouver la
solution optimale d’un PLNE par les coupes de Gomory. D’où l’implémentation d’algorithme
de coupe et de solveurs.
• Lorsque les contraintes et variables sont rationnelles (à fortiori entière), les coupes de Gomory
convergent vers la solution optimale en temps fini.
• Les coupes gardent le domaine convexe, et peuvent être inefficaces dans certaines configura-
tions.
• On peut aussi utiliser d’autres techniques pour résoudre le PLNE, comme la méthode de sé-
paration et évaluation progressive (ou Branch-and-Bound en anglais).
• Il peut arriver qu’en ajoutant une coupe qu’une ou plusieurs contraintes puissent être éliminées
du problème à résoudre. En effet dans l’exemple précédent la coupe trouvée est 10x1 + 12x2 ≤
58, or toute solution admissible satisfaisant à la coupe satisfait aussi à la contrainte 10x1 +
12x2 ≤ 59.
50
X Exemple Soit (P) le programme linéaire en nombres entiers suivant:
max f (x) = 3x1 + x2
s.c. 2x1 + 2x2 ≤ 5
− 4x1 + 5x2 ≥ 9
Résoudre avec les coupes de Gomory.

X Correction On résout la relaxation continue du programme qui est donnée par :
(Prel ) : max f (x) = 3x1 + x2
s.c. 2x1 + 2x2 ≤ 5
− 4x1 + 5x2 ≥ 9
x1 , x2 ≥ 0
On donne la forme standard pénalisée :
max f (x) = 3x1 + x2 − M x5
s.c. 2x1 + 2x2 + x3 = 5
− 4x1 + 5x2 − x4 + x5 = 9
x1 , x2 , x3 , x4 , x5 ≥ 0
Une solution initiale de base est donnée par x1 = x2 = x4 = 0 et x3 = 5, x5 = 9. Le dernier tableau

du simplexe est donné par :
i A1 A2 A3 A4 A5
1 1 0 5/18 1/9 -1/9 7/18
2 0 1 2/9 -1/9 1/9 19/9
z 0 0 -M+2/9 -19/18 -2/9 59/18
Ainsi la solution de base est x1 = 7/18, x2 = 19/9.

On a (on peut ne pas considérer la variable artificielle) : ᾱ1 = (−1/9, 5/18, 1/9) et b̄1 = 7/18,
ᾱ2 = (1/9, 2/9, −1/9) et b̄2 = 19/9 .
On va déterminer deux coupes :
51
• Coupe 1 :
{−1/9}x5 + {5/18}x3 + {1/9}x3 ≥ {7/18}
8/9x5 + 5/18x3 + 1/9x4 ≥ 7/18
16/18x5 + 5/18(5 − 2x1 − 2x2 ) + 2/18(−4x1 + 5x2 + x5 − 9) ≥ 7/18
7 + 18x5 − 18x1 ≥ 7
x1 − x5 ≤ 0
On peut éliminer x5 et ne considérer que x1 ≤ 0.
• Coupe 2 :
{1/9}x5 + {2/9}x3 + {−1/9}x3 ≥ {19/9}
1/9x5 + 2/9x3 + 8/9x4 ≥ 19/9
1/9x5 + 2/9(5 − 2x1 − 2x2 ) + 8/9(−4x1 + 5x2 + x5 − 9) ≥ 1/9
−62 + 9x5 − 36x1 + 36x2 ≥ 1
−4x1 + 4x2 + x5 ≥ 7
La coupe 2 est donc −4x1 + 4x2 ≥ 7.
On ajoute ces deux inéquations au programme (Prel ) on obtient :
0
(Prel ) : max f (x) = 3x1 + x2
s.c. 2x1 + 2x2 ≤ 5
− 4x1 + 5x2 ≥ 9
x1 ≤ 0
− 4x1 + 4x2 ≥ 7
x1 , x2 ≥ 0
52
On donne la forme standard pénalisée :
max f (x) = 3x1 + x2 − M x5 − M x8
s.c. 2x1 + 2x2 + x3 = 5
− 4x1 + 5x2 − x4 + x5 = 9
x1 + x6 = 0
− 4x1 + 4x2 − x7 + x8 = 7
x1 , x2 , x3 · · · , x8 ≥ 0
Puis on résout le programme et on trouve le dernier tableau du simplexe :
i A1 A2 A3 A4 A5 A6 A7 A8
3 0 0 1 0.4 -0.4 -0.4 -3.6 0 1.4
7 0 0 0 -0.8 0.8 -0.8 1 -1 0.2
1 1 0 0 0 0 1 1 0 0
2 0 1 0 -0.2 0.2 0.8 0 0 1.8
Z 0 0 0 0.2 -M-0.2 -3.8 0 -M 1.8
La solution optimale est donnée par : x1 = 0, x2 = 1.8 et la valeur optimale est de 1.8. On constate
que cette solution optimale n’est pas entière on refait le processus de coupe.
• Coupe 1 :
{−1}x5 + {0}x8 + {2.5}x3 + {−9}x6 ≥ {3.5}
0.5x3 ≥ 0.5
x3 ≥ 1
5 − 2x1 − 2x2 ≥ 1
x1 + x2 ≤ 2
D’où la coupe 1 est x1 + x2 ≤ 2.
53
• Coupe 2 :
{0}x5 + {−1}x8 + {2}x3 + {−8}x6 ≥ {3}
0≥0
Pas de coupe 2.
• Coupe 3 : De même on a pas de coupe (0 ≥ 0).
• Coupe 4 :
{0}x5 + {0}x8 + {0.5}x3 + {−1}x6 ≥ {2.5}
0.5x3 ≥ 0.5
x3 ≥ 1
5 − 2x1 − 2x2 ≥ 1
x1 + x2 ≤ 2
On trouve finalement une seule coupe à ajouter : x1 + x2 ≤ 2.

0
On l’ajoute dans le programme (Prel ) :
00
(Prel ) : max f (x) = 3x1 + x2
s.c. 2x1 + 2x2 ≤ 5
− 4x1 + 5x2 ≥ 9
x1 ≤ 0
− 4x1 + 4x2 ≥ 7
x1 + x2 ≤ 2
x1 , x2 ≥ 0
En résolvant ce nouveau programme la solution optimale x1 = 0, x2 = 2 et la valeur optimale 2. La

solution est entière donc il s’agit aussi d’une solution optimale du programme (P).
Remarque 2.2. On peut résumer la méthode de coupe de Gomory sous forme d’algorithme :
54
• Etape 1: Résoudre la relaxation continue du PLNE.
• Etape 2 :
– si la solution optimale de la relaxation continue est entière c’est aussi la solution optimale
du PLNE. Dans ce cas Fin.
– si la solution n’est plus entière c’est à dire est fractionnaire, alors on cherche des coupes
de Gomory.
• Etape 3 : Ajout des coupes dans le PLNE et reconsidérer la relaxation continue de ce nouveau
PLNE. Puis aller à Etape 1.
On répète le processus jusqu’à ce que la solution soit entière.
XDans la sous-section suivante, on y présente des exemples qui font référence à des situations
réelles.
2.3 Problème du sac-à-dos simple
Ce problème est l’exemple le plus simple de problème de programmation linéaire en nombres entiers.
Un alpiniste se préparant à partir en expédition est confronté au douloureux problème de savoir ce
qu’il doit mettre dans son sac. Chaque objet présente pour lui une utilité plus ou moins importante
et le poids total du sac est limité. La modélisation de ce problème est a priori très simple. On
connaît pour chaque objet son poids pi , ainsi que l’utilité ci que l’on peut en retirer. On connaît
aussi le poids maximum P du sac. Les décisions concernent le nombre de chacun des objets à mettre
dans le sac. Elles sont représentées par des variables xi qui valent 1 si l’objet i est choisi et 0 sinon.
La seule contrainte porte sur le poids des objets, c’est à dire:
n
X
p i xi ≤ P
i=1
L’objectif concerne la maximisation de l’utilité totale (en faisant l’hypothèse que pour chaque type
d’objets, l’utilité est proportionnelle au nombre d’objets); on a
n
X
max ci x i
i=1
Entrées:
• un ensemble {1, 2, ..., n} d’objets
• le poids maximum P
55
• le revenu ci associé à chaque objet i = 1, 2, ..., n
• le poids pi associé à chaque objet i = 1, 2, ..., n
Les quelques autres applications du problème de sac à dos concernent aussi:
• le choix d’investissements
• l’optimisation d’un portfolio d’actions
X On a, a priori, un problème très simple de programmation linéaire, donné par le problème

d’optimisation suivant: trouver un ensemble S ∗ d’objets qui maximise le revenu total et dont la
somme des poids soit inférieure à P .
n
P
max ci x i
i=1
s.c.
Pn
p i xi ≤ P
i=1
xi = 0 ou 1 ∀ i = 1, ..., n
Le nombre de sous-ensembles d’objets est 2n et donc pour des problèmes de grande taille il est
impossible de trouver la meilleure solution en explorant toutes les possibilités, même
en utilisant une machine parallèle puissante.
Exemple 2.1.
max 8x1 + 16x2 + 20x3 + 12x4 + 6x5 + 9x6 + 2x7
s.c. 3x1 + 7x2 + 9x3 + 6x4 + 3x5 + 5x6 + 2x7 ≤ 17
x1 , ..., x7 = 0 ou 1
Pour la résolution, on pourra se référer aux tehchinques d’optimisation tels que Branch and Bound,
cutting plane, branch and cut, etc. (voir en Travaux Pratiques).
56
2.4 Problème du sac-à-dos multidimensionnel
Le problème du sac-à-dos multidimensionnel en variables 0-1 est une généralisation du problème.

Il correspond au cas où le nombre de contraintes de capacité est strictement supérieur à 1.
n
X
max cj x j
j=1
s.c.
n
X
pij xj ≤ Pi ∀ i = 1, ..., m
j=1
xj ∈{0, 1} ∀ j = 1, ..., n
On peut prendre des instances, en considèrant les données dans OR-Library de J.E. Beasley http:
//people.brunel.ac.uk/~mastjjb/jeb/info.html.
2.5 Problèmes de tournées de véhicules
Ce problème consiste à déterminer les trajets qui doivent être faits par chaque véhicule, de façon à
minimiser les coûts. On doit couvrir un ensemble de clients par un ensemble de tournées, chaque
tournée correspond à un véhicule.
Par exemple des voyageurs de commerce doivent visiter leurs clients à travers le Sénégal. Ils souhait-
ent effectuer, chacun, la tournée la plus courte possible sur les n villes; tournée visitant chaque ville
une et une seule fois et revenant à leur point de départ.
Le figure 2 est l’exemple de 3 tournées devant quitter et revenir le dépôt.
Figure 2: tournées avec 3 véhicules.
Les quelques applications concernent:
• la confection des horaires des chauffeurs d’autobus,
57
• le transport scolaire,
• le transport de handicapés,
• le transport de marchandises,
• l’affectation des tripulations aux vols dans les transports aériens,
• l’affectation des avions aux vols,
• l’affectation des vols aux portes d’embarquement dans les aéroports,
• etc.
Remarque 2.3. Le cas le plus simple est le problème sans contraintes.
X S’il existe un seul véhicule (une seule tournée doit être réalisée) il s’agit du problème du voyageur
de commerce (TSP: Travelling Salesman Problem).
Il peut être vu comme un cas particulier du problème de localisation-routage dont la somme des
demandes n’excède pas la capacité d’un véhicule et où un seul dépôt est disponible.
Le but est de trouver un cycle de longueur totale minimale qui passe exactement une fois par chaque
point.
En considérant un graphe G = (S, A) un ensemble de noeuds (ou sommets) S et d’arcs A de coût
cij , le problème peut se formuler ainsi, avec les variables binaires xij qui valent 1 si l’arc (i, j) ∈ A
est utilisé et 0 sinon.
XX
min cij xij
i∈S j>i
s.c.
X
xij = 1 ∀j∈S
i:(i,j)∈A
X
xij = 1 ∀i∈S
j:(i,j)∈A
X
xij ≥ 1 ∀ V ⊂ S, avec 2 ≤ |V | < |S| − 2
(i,j)∈A:i∈V,j∈S\V
xij ∈{0, 1} ∀ (i, j) ∈ A
2.6 Problème de localisation (location/allocation problem)
Dans ce type bien particulier de problème, l’objectif général est de déterminer l’emplacement optimal
d’un certain nombre d’installations sur un ensemble de sites possibles, de manière à :
58
• minimiser le nombre d’installations pour couvrir toutes les demandes,
• ou maximiser la demande couverte avec un nombre fixé d’installations,
• ou minimiser les coûts, etc.
Les questions à résoudre sont : Combien d’installations ? Où les placer ? Comment affecter
les demandes aux sites ?
Parmi les nombreuses applications, nous pouvons en citer: localisation de centres d’intervention
d’urgence, de centres sociaux, de centres de distribution, de centres de service, de concentrateurs
dans les réseaux, etc.
Les raisons: les marchés sont plus étendus, mais souvent avec une clientèle plus dispersée, les
livraisons plus faciles grâce à l’ouverture de sites, des frontières, de centrales, de hub, etc.
Par exemple, afin d’approvisionner ces principaux centres de distribution, la SENELEC a décidé
d’implanter plusieurs centrales. Pour cela, elle a identifié plusieurs sites susceptibles de convenir
parmi lesquels il faudra en choisir au maximum un certain nombre.
On connaît le coût d’implantation des centrales en fonction du site. Le coût de raccordement d’un
centre à une centrale est également connu. Le problème est de sélectionner les sites à retenir et,
pour chaque centre, la centrale qui le desservira de manière à minimiser le coût total.
Pour modéliser ce problème, nous disposons des données sur les sites et les centres: n sites j = 1, ..., n
et p centres i = 1, ..., p. On note par fj le coût d’implantation d’une usine sur le site j, cij le coût
de raccordement du centre de distribution i au site j et K le nombre maximum d’usines.
Choix des variables:

Pour chaque site, il s’agit de savoir si on y construit ou non une usine. Cette décision peut être
représentée par une variable booléenne qui aura l’interprétation suivante : si elle vaut 1 c’est "oui",
si elle vaut 0, c’est "non". 
 1 si le site j est retenu
yj =
 0 sinon
Pour le raccordement des centres aux usines, la décision est de même nature. Pour chacun des
centres i et pour chaque usine située sur le site j, il s’agit de savoir si le centre est, ou non, raccordé
à l’usine. Une variable booléenne xij permet de représenter cette décision.

 1 si le centre i est affecté au site j
xij =
 0 sinon
59
Les contraintes:
Elles concernent d’abord le fait qu’on ne veut pas plus de K usines construites. Cette contrainte se
traduit par : au maximum K variables yj peuvent prendre la valeur 1, c’est à dire:
n
X
yj = K
j=1
Chaque centre est affecté à une seule usine c’est-à-dire que, pour chaque i, une seule variable xij
vaut 1 :
n
X
xij = 1 ∀ i = 1, ..., p
j=1
Un centre ne peut être raccordé qu’à une usine construite. Si xij vaut 1 alors yj doit valoir 1, ce
qui s’exprime encore par : si yj vaut 0 alors xij vaut 0. Cette contrainte peut être traduite par:
xij ≤ yj ∀ i = 1, ..., p ∀ j = 1, ..., n
La fonction objectif:
Deux(2) types de coût sont pris en compte. Pour chaque usine, son coût d’implantation sur le site
j vaut fj si elle est construite, donc si yj est égal à 1, et 0 sinon. Il en est de même pour le coût
de raccordement d’un centre i à une usine. Il vaut soit cij si xij vaut 1, soit 0 si xij vaut 0. D’où
l’expression de l’objectif à minimiser :
p n n
X X X
cij xij + fj y j
i=1 j=1 j=1
Le problème de localisation est donc modélisé par le PLNE suivant :

p n n
X X X
min cij xij + fj y j
i=1 j=1 j=1
s.c.
n
X
yj = K
j=1
n
X
xij = 1 ∀ i = 1, ..., p
j=1
xij ≤ yj ∀ i = 1, ..., p ∀ j = 1, ..., n
xij ∈{0, 1} ∀ i = 1, ..., p ∀ j = 1, ..., n
yj ∈{0, 1} ∀ j = 1, ..., n
2.7 Problèmes de recouvrement (Set Covering Problem - SCP)
Il s’agit de trouver les sites à ouvrir afin de couvrir les clients au moindre coût. Nous définissons:
60
• une matrice de recouvrement A, avec chaque élément représentant une donnée binaire aij = 1
si le site i peut couvrir le client j,
• un coût d’ouverture du dépôt i comme ci ,
• et des variables de décision booléennes telles que xi vaille 1 si le site i est ouvert, et 0 sinon;

 1 si le site i est retenu
xi =
 0 sinon
Par exemple, afin de satisfaire le demande d’intervention on décide d’implanter des casernes de
pompiers dans une ville. La ville est découpée en quartiers. Par ailleurs, un certain nombre de
localisations possibles pour les casernes ont été identifiées ainsi que le coût d’implantation corre-
spondant. Le problème est de localiser les casernes de manière à ce que chaque quartier soit à moins
de 5 minutes au moins d’une caserne. Et ceci au moindre coût ! Pour chaque quartier, on évalue
donc s’il est ou non, à moins de 5 minutes de chacun des différents sites.
Ce problème de recouvrement peut aussi bien concerner la localisation de sirènes que d’émetteurs
de télévisions ou bien d’autres choses du moment qu’il s’agit de couvrir des zones, d’où son nom.
La représentation de l’objectif est immédiate ; le coût total d’implantation est égal à :

m
X
ci x i
i=1
Pour les contraintes, il s’agit d’exprimer que chaque client sera bien couvert: parmi les sites qui
intéressent le client j, il doit en avoir au moins 1 de retenu (xi = 1).
Le problème peut se formuler de la manière suivante:
m
X
min ci x i
i=1
s.c.
m
X
aji xi ≥ 1 ∀ j = 1, ..., n
i=1
xi ∈{0, 1} ∀ i = 1, ..., m
X Les problèmes de PLNE font partie des problèmes pour lesquels on ne dispose pas d’algorithmes
dont le temps de calcul croit de manière polynomiale avec la taille du problème.
Lorsque la taille du problème le permet, on peut le résoudre avec des méthodes de résolution basées
61
sur une exploration intelligente du domaine des solutions. Les techniques les plus utilisées sont :
Branch-and-Bound ou Séparation et Evaluation progressive, Cutting plane ou plan coupant, Branch
& cut, etc.
Remarque 2.4. Il arrive aussi que, dans certains (rares) cas, la solution obtenue sans tenir
compte des contraintes d’intégrité, par exemple avec l’algorithme du simplexe, soit a posteriori
entière; le problème est alors résolu.
A Exercices corrigés
Exercice A.1. Une industrie automobile fabrique 3 types de modèles de voitures (vt ) v1 , v2 et v3
qui lui rapportent respectivement des profits de 160 000 FCFA, 300 000 FCFA et 500 000 FCFA.
Les niveaux maxima de production pour une semaine sont de 100 pour v1 , 150 pour v2 et 75 pour
v3 . Chaque quinzaine de vt de type j requiert un temps Fj pour la fabrication, un temps Aj pour
l’assemblage et un temps Ej pour l’emballage.
v1 v2 v3
Fj 3 3.5 5
Aj 4 5 8
Ej 1 1.5 3
Pendant la semaine à venir, l’entreprise aura 150 heures disponibles pour la fabrication, 200 pour
l’assemblage et 60 pour l’emballage.
L’entreprise veut donner un plan de production qui maximise son profit net.
X Modélisation du problème: En premier, nous examinons dans l’ordre la représentation des

Les variables de décisions: les décisions concernent les quantités de modèle de voitures vi , pour
tout i = 1, 2, 3. Alors, on pose : xi = le nombre de modèle de voitures vi (i = 1, 2, 3) à fabriquer.
Les contraintes: il s’agit de représenter les différentes contraintes limitant les heures disponibles
pour la fabrication, l’assemblage et l’emballage; mais aussi sur les niveaux maxima de production.
Comme les temps Fj , Aj et Ej sont donnés par quinzaine (d’un modèle de type vi ), on doit forcément
convertir les données. Le plus simple (pour éviter de diviser partout par 15) revient à multiplier les
ressources par 15. Les disponibilités Fj , Aj et Ej sont alors de 2250 (=150 × 15), 3000 (= 200 × 15)
et 900 (= 60 × 15), respectivement.
La première contrainte porte sur la fabrication des voitures: chaque modèle de voiture requiert un
62
temps pour la fabrication et on en dispose 2250 heures. On doit donc imposer : 3x1 + 3.5x2 + 5x3
≤ 2250.
De même pour la deuxième contrainte, le nombre d’heures pour l’assemblage est limité. Vu le temps
requis par chaque type de voitures, cette contrainte se traduit par : 4x1 + 5x2 + 8x2 ≤ 3000. De
même pour la troisième contrainte, avec le même raisonnement pour l’emballage, on obtient : x1 +
1.5x2 + 3x2 ≤ 900.
Les autres contraintes concernent les niveaux maxima de production. Elles s’expriment, respective-
ment, pour la fabrication, l’assemblage et l’emballage : par x1 ≤ 100, x2 ≤ 150 et x3 ≤ 75.
L’ensemble des décisions possibles est donc caractérisé par l’ensemble des valeurs de x1 , x2 et x3
vérifiant :
3x1 + 3.5x2 + 5x3 ≤ 2250
4x1 + 5x2 + 8x3 ≤ 3000
x1 + 1.5x2 + 3x3 ≤ 900
x1 ≤ 100
x2 ≤ 150
x3 ≤ 75
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Le critère : l’objectif est de donner le plan de production qui maximise le profit net de l’entreprise.
Ce qui est représenté par : 160x1 + 300x2 + 500x3 .
Le problème est donc modélisé par le problème de programmation mathématique suivant :

max f (x) = 160x1 + 300x2 + 500x3
s.c. 3x1 + 3.5x2 + 5x3 ≤ 2250
4x1 + 5x2 + 8x3 ≤ 3000
x1 + 1.5x2 + 3x3 ≤ 900
x1 ≤ 100
x2 ≤ 150
x3 ≤ 75
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
63
La forme standard est donné par :
max f (x) = 160x1 + 300x2 + 500x3
s.c. 3x1 + 3.5x2 + 5x3 + x4 = 2250
4x1 + 5x2 + 8x2 + x5 = 3000
x1 + 1.5x2 + 3x2 + x6 = 900
x1 + x7 = 100
x2 + x8 = 150
x3 + x9 = 75
x1 ≥ 0, ..., x9 ≥ 0
Ainsi, on obtient n = 9 (nombre de variables) et p = 6 (nombre de contraintes). Le premier

tableau (initialisation) du simplexe est donné par le tableau 23.
i A1 A2 A3 A4 A5 A6 A7 A8 A9
4 3 3.5 5 1 0 0 0 0 0 2250 L1
5 4 5 8 0 1 0 0 0 0 3000 L2
6 1 1.5 3 0 0 1 0 0 0 900 L3
7 1 0 0 0 0 0 1 0 0 100 L4
8 0 1 0 0 0 0 0 1 0 150 L5
9 0 0 1
○ 0 0 0 0 0 1 75 L6
z 160 300 500 0 0 0 0 0 0 0 L7
Table 23: premier tableau du simplexe
En appliquant le premier critère de Dantzig, on obtient: le côut le plus élevé est 500 qui correspond
à x3 , donc c’est x3 qui va entrer dans la base (k ∗ =3).
5
, 3000
8
, 900
3
, 75
1
)=75, qui correspond à x9 qui va sortir
de la base (i∗ = 9).
Tous les coûts marginaux ne sont pas négatifs ou nuls, donc on continue la procédure (le test d’arrêt
n’est pas atteint).
L’élément de la matrice encerclé dans le tableau correspond au pivot (pour i∗ = 9 et k ∗ = 3). C’est
l’élément a63 de la matrice A.
Le deuxième tableau du simplexe est donné par le tableau 24:
64
i A1 A2 A3 A4 A5 A6 A7 A8 A9
0 0
4 3 3.5 0 1 0 0 0 0 -5 1875 L1 =L1 -5L6
0 0
5 4 5 0 0 1 0 0 0 -8 2400 L2 =L2 -8L6
0 0
6 1 1.5 0 0 0 1 0 0 -3 675 L3 =L3 -3L6
0
7 1 0 0 0 0 0 1 0 0 100 L4 =L4
1
0
8 0 ○ 0 0 0 0 0 1 0 150 L5 =L5
0
3 0 0 1 0 0 0 0 0 1 75 L6 =L6
0 0
z 160 300 0 0 0 0 0 0 -500 -37500 L7 =L7 -500L6
Table 24: deuxième tableau du simplexe
On applique le premier critère de Dantzig, dans le deuxième tableau, on obtient: le côut le plus
élevé est 300 qui correspond à x2 , donc c’est x2 qui va entrer dans la base (k ∗ =2).
3.5
, 2400
5
, 675
1.5
, 150
1
)=150, qui correspond à x8 qui va
sortir de la base (i∗ = 8).
Tous les coûts marginaux ne sont pas négatifs ou nuls, donc on continue toujours la procédure, et
on passe au tableau suivant.
Le troisième tableau du simplexe est donné par le tableau 25: On applique le premier critère de
i A1 A2 A3 A4 A5 A6 A7 A8 A9
00 0 00
4 3 0 0 1 0 0 0 -3.5 -5 1350 L1 =L1 - 27 L5
00 0 00
5 4 0 0 0 1 0 0 -5 -8 1650 L2 =L2 -5L5
00 0 00
6 1 0 0 0 0 1 0 -1.5 -3 450 L3 =L3 - 23 L5
1
00 0
7 ○ 0 0 0 0 0 1 0 0 100 L4 =L4
00 0
2 0 1 0 0 0 0 0 1 0 150 L5 =L5
00 0
3 0 0 1 0 0 0 0 0 1 75 L6 =L6
00 0 00
z 160 0 0 0 0 0 0 -300 -500 -82500 L7 =L7 -300L5
Table 25: troixième tableau du simplexe
Dantzig, dans le troisième tableau, on obtient: le côut le plus élevé est 160 qui correspond à x1 ,
donc c’est x1 qui va entrer dans la base (k ∗ =1).
3
, 1650
4
, 450
1
, 100
1
)=100, qui correspond à x7 qui va
sortir de la base (i∗ = 7).
Tous les coûts marginaux ne sont pas négatifs ou nuls, donc on continue toujours la procédure.
65
Le quatrième tableau du simplexe est donné par le tableau 26:
i A1 A2 A3 A4 A5 A6 A7 A8 A9
000 00 000
4 3 0 0 1 0 0 0 -3.5 -5 1050 L1 =L1 -3L4
000 00 000
5 4 0 0 0 1 0 0 -5 -8 1250 L2 =L2 -4L4
000 00 000
6 1 0 0 0 0 1 0 -1.5 -3 350 L3 =L3 -L4
000 00
1 1 0 0 0 0 0 1 0 0 100 L4 =L4
000 00
2 0 1 0 0 0 0 0 1 0 150 L5 =L5
000 00
3 0 0 1 0 0 0 0 0 1 75 L6 =L6
000 00 000
z 0 0 0 0 0 0 -160 -300 -500 -82500 L7 =L7 -160L4
Table 26: quatrième tableau du simplexe
XLe problème dual est donné par:
min g(x) = 2250y1 + 3000y2 + 900y3 + 100y4 + 150y5 + 75y6
s.c. 3y1 + 4y2 + y3 + y4 ≥ 160
3.5y1 + 5y2 + 1.5y3 + y5 ≥ 300
5y1 + 8y2 + 3y3 + y6 ≥ 500
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0, y6 ≥ 0
La solution optimale du dual se trouve dans la ligne des coûts réduits (z). Il faut compter à partir
des variables d’écart (donc colonne A4 ). On obtient:
y1 = 0, y2 = 0, y3 = 0
y4 = 160, y5 = 300, y6 = 500
Les valeurs sont prises en valeurs absolues.

Vérification du théorème de la dualité:
g(y) = 2250 ∗ 0 + 3000 ∗ 0 + 900 ∗ 0 + 100 ∗ 160 + 150 ∗ 300 + 75 ∗ 500 = 82500
Exercice A.2. Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de ressources :
équipement, main d’oeuvre, matières premières. Ces besoins sont indiqués dans le tableau ci-dessous.
Par ailleurs, chaque ressource est disponible en quantité limitée (cf. tableau).
66
P1 P2 disponibilité
équipement 3 9 81
main d’oeuvre 4 5 55
matière première 2 1 20
Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 3900 F et 2600 F par
unité. Formuler le problème sous forme de programme linéaire permettant à l’usine de maximiser
le bénéfice total venant de la vente des 2 produits.
Pour formuler le problème en programme linéaire, il faut commencer par déterminer les inconnues
du problème. On cherche à connaître la quantité des produits P1 et P2 à fabriquer.
Les variables:
Soient x1 et x2 les quantités respectives de produits P1 et P2 à fabriquer.
La fonction objectif:
On cherche à maximiser le bénéfice total venant de la vente des 2 produits. Ainsi la fonction objectif
à maximiser est l’expression mathématique du bénéfice total des deux produits :
f (x) = 3900x1 + 2600x2 .
Les contraintes:
D’une manière générale les contraintes traduisent des conditions à satisfaire par les variables, des
relations entre les variables. Ainsi dans cette exemple, les contraintes sont les expressions mathé-
matiques des limitations des ressources de l’usine :
• contraintes sur l’équipement : 3x1 + 9x2 ≤ 81.
• contraintes sur la main d’œuvre : 4x1 + 5x2 ≤ 55.
• contraintes sur les matières premières : 2x1 + x2 ≤ 20.
L’expression du programme linéaire est :
max z = f (x) = 3900x1 + 2600x2
s.c. 3x1 + 9x2 + ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20
x1 ≥ 0, x2 ≥ 0
67
B Quelques exercices
Exercice B.1. Une entreprise est capable de produire deux biens b1 et b2 . Ces productions font
intervenir deux facteurs fixes : la main d’œuvre et des équipements. L’emploi de la main d’œuvre
est rigide à la hausse et à la baisse, la quantité disponible étant égale à 2. La capacité de production
des équipements est égale à 1 et ils n’interviennent que pour la production du second bien. On veut
maximiser la marge sur coût variable, les marges unitaires étant de 15000 FCFA et 10000 FCFA,
respectivement. La main d’œuvre et les équipements nécessaire pour la production d’une unité des
biens sont donnés dans le tableau suivant:
main d’oeuvre équipements

b1 2 -
b2 1 1
1. Formuler le problème sous la forme d’un programme linéaire
2. Écrire le programme obtenu sous forme matricielle.
3. Résoudre graphiquement le programme obtenu.
4. En déduire le programme de production optimal.
5. Si la capacité de production des équipements passe de 1 à 3, analyser graphiquement si la

solution optimale change. Si oui, donner la nouvelle valeur obtenue.
Exercice B.2. Une firme fabrique pour des entreprises de quincaillerie des pièces en inox. Ces
pièces sont de trois types A, B, C. Elles sont fabriquées par lot de 50 dans un atelier où sont rassem-
blées deux machines pour la découpe de l’inox, une machine pour l’embouteillage, deux machines
pour le polissage et la finition. Chaque machine fonctionne 120 heures par mois. Les caractéristiques
de fabrication sont rassemblées dans le tableau:
Coût de l’heure lot A lot B lot C

Découpage 20 F 1 1,5 1,5
Embouteillage 30 F 0,5 - 1
Polissage et finition 40 F 2 1 1
Inox 50 F 85 F 68 F
Prix de vente (H.T.) 200 F 200 F 210 F
Quel est le programme de production optimal (pour un mois) ? (On utilisera la méthode des
tableaux).
68
Exercice B.3. Un vendeur de farces et attrapes dispose d’un stock de 3 articles différents: 300 sacs
de confettis, 180 chapeaux, 240 paquets de serpentins. Il désire, pour écouler cette marchandise,
composer deux types de lots L1 et L2 comprenant:
L1 : 5 sacs de confettis, 1 chapeau et 2 paquets de serpentins.
L2 : 3 sacs de confettis, 3 chapeaux et 3 paquets de serpentins.
Pour chaque lot de type 1 vendu, le bénéfice réalisé est de 6 F contre 12 F pour un lot de type 2.
Question: Combien de lots de chaque type doit-on composer pour maximiser le bénéfice total ?
(On utilisera la méthode graphique).
Exercice B.4. Le gouvernement a décidé de réaliser une campagne de lutte contre l’alcoolisme en
faisant diffuser des messages par la télévision (T), la radio (R) et la presse (P). Pour être efficace,
cette campagne doit toucher au moins 50% des jeunes entre 15 et 25 ans, au moins 75% des adultes
entre 25 et 60 ans et au moins 30% des adultes de plus de 60 ans. Dans le tableau suivant sont
regroupées les estimations en millions du nombre des personnes des 3 catégories sensibilisées par le
passage d’un message selon le moyen de diffusion.
Catégories 15-25 25-60 60 et plus coût

T 10 25 9 10000
R 5 30 8 7000
P 1 10 11 5000
pop.totale 9100 25000 9000
1. Connaissant pour chaque catégorie sa population totale et le coût moyen de diffusion d’un
message par chaque média, on demande de déterminer le PL permettant de réaliser une cam-
pagne efficace au moindre coût, sachant que le nombre de messages diffusés par la télévision
ne doit pas être plus du triple du nombre des messages diffusés par les autres médias.
2. La diffusion des messages par la presse n’étant pas jugé rentable, on demande de déterminer
et de résoudre graphiquement le PL associé à la nouvelle campagne, les autres données n’ayant
pas changé.
Exercice B.5. L’entreprise chimique «ChimSN» est spécialisé dans la production d’un agent AP
pouvant neutraliser les déchets polluant déversés par les usines dans les cours d’eau. Pour être
efficace, le produit doit contenir les quantités minimales suivantes de 6 composantes chimiques:
A,B,C,D,E,F.
Composant A B C D E F
Quantité en kg 0.2 0.6 0.84 2.88 3.48 1.24
69
Il existe sur le marché 2 produits X et Y qui contiennent, pour un kg ces composants en quantités
variables (exprimées en %).
Produits A B C D E F
X 10 0 12 24 18 4
Y 0 20 4 18 30 16
Un kg de X est vendu 16 F et un kg de Y est vendu 28 F. L’entreprise souhaitant fabriquer son

agent au moindre coût, on demande de réaliser le travail suivant:
1. Ecrire le programme linéaire correspondant au problème de l’entreprise. Ce programme est

t-il sous la forme canonique ?
2. Ecrire le dual. Quelle interprétation peut on donner à ce programme ?
3. Résoudre le P.L. du dual par l’algorithme du simplexe. Donner toutes les interprétations à
l’optimum.
Exercice B.6. Une industrie automobile fabrique 3 modèles de voitures (vt ) v1 , v2 et v3 qui lui
rapportent des profits de 160, 300 et 500 francs. Les niveaux maxima de production pour une
semaine sont de 100 pour v1 , 150 pour v2 et 75 pour v3 . Chaque quinzaine de vt de type j requiert
un temps Fj pour la fabrication, un temps Aj pour l’assemblage et un temps Ej pour l’emballage.
v1 v2 v3
Fj 3 3.5 5
Aj 4 5 8
Ej 1 1.5 3
Pendant la semaine à venir, l’entreprise aura 150 heures disponibles pour la fabrication, 60 pour
l’emballage et 200 pour l’assemblage. L’entreprise veut donner un plan de production qui maximise
le profit de la compagnie.
1. Formuler un modèle sous la forme d’un programme linéaire qui donne le plan de production
de la compagnie (choix des variables, de la fonction objectif et des contraintes).
2. Résoudre le programme obtenu par la méthode du simplexe.
3. En déduire le plan de production maximisant le profit.
4. Déterminer le programme dual ainsi que la solution pour ce problème.
70
Exercice B.7. Une raffinerie doit fournir chaque jour deux qualités A et B d’essence à partir
des constituants 1, 2 et 3. on dispose des données suivantes, avec la quantité maximale disponible
quotidiennement notée Qmax :
constituant Qmax coût unitaire
1 3000 3
2 2000 6
3 4000 4
essence spécification prix de vente unitaire

A ≤ 30% de 1 5.5
≥ 40% de 2
≤ 50% de 3
B ≤ 50% de 1 4.5
≥ 10% de 2
Donner un modèle permettant de déterminer la composition des mélanges et les quantités produire
pour maximiser la recette (toute la production pourra être écoulée). Peut-on se ramener à un
problème de programmation linèaire ?
Exercice B.8. Un agriculture veut répandre sur ses terrains un engrais ayant une teneur en azote
(N ). Malheureusement, les trois engrais dont il dispose contiennent également les éléments K et P .
Il doit absolument limiter à 44 et 66 unités par hectare l’apport de K et P . Comment doit-il faire
son mélange pour que la quantité d’azote réparti à l’hectare soit maximale . Quelle est la quantité
d’azote ainsi répandue et quelle est la production N : P : K du mélange ? On donne dans le tableau
ci-dessous la quantité de N , P , K présente dans chacun des engrais (par unité d’engrais).
engrais 1 engrais 2 engrais 3

N 3 4 6
P 2 3 4
K 5 2 5
1. Résoudre avec un code de programme linéaire, et en déduire la quantité d’azote ainsi répandue
ainsi que la production N : P : K du mélange.
2. Formuler le problème dual, calculer les variables duales à l’optimum.
3. Interpréter le problème dual.
71
Exercice B.9. Une entreprise chimique veut disposer des produits A et B contenant des éléments
I, II, et III en Pourcentages donnés par le tableau ci-dessous. Elle peut créer des mélanges de
produits ayant des contenus minimaux prescrits d’éléments I, II et III.
A B besoin (en kg)

en éléments
élément I 20 40 7
II 30 50 2
III 30 10 5
prix(par kg) 10 5
du produit
1. Calculer les quantités de produits A et B à mélanger pour satisfaire au prix minimum les
besoins en éléments I, II et III donnés dans le tableau.
2. Formuler le dual de ce problème, l’interpréter.
Exercice B.10. Une entreprise fabrique des produits I, II et III à partir de ressources. Le tableau
ci-dessous donne les consommations par unité de produit fabriqué.
I II III disponibilité
des ressources
heure-machine 2 3 1 10
matière première 1 4 3 15
Les recettes fournies par unité de produit fabriqué sont respectivement 6, 4 et 5 kFCFA.
1. Déterminer un plan de production qui maximise la recette.
2. Est-il unique ?
3. Interpréter les variables duales du problème; peut-on les trouver dans le tableau optimal du
simplexe ?
4. L’entreprise pourrait disposer d’une heure-machine supplémentaire au prix de 3 kFCFA; a-t-

elle intérêt à accepter cette offre ? et si on lui propose plutôt une unité de matière première
au prix de 1/2 kFCFA ?
72
Exercice B.11. Montrer que le programme linéaire suivant peut être résolu par l’algorithme du
Simplexe moyennant l’introduction de variables artificielles.
max f (x) =350x1 + 400x2
s.c. x1 + x2 ≤ 700
x1 + x2 ≥ 500
3x1 + 4x2 ≤ 2400
2x1 − x2 ≤ 0
x1 ≥ 0, x2 ≥ 0
On écrira le programme sous la forme standard puis sous la forme standard pénalisée.
Résoudre ensuite le programme par la méthode des tableaux puis vérifier graphiquement le résultat.
Exercice B.12. Une entreprise produit 2 articles A et B à l’aide de 4 méthodes de production (2

par article). Sa production est limitée par des disponibilités en matières premières: α ≤ 120 kg et
β ≤ 100 kg par semaine; et par des disponibilités en main d’oeuvre : 15 ouvriers travaillant 40
heures par semaine. Les contraintes de fabrication sont les suivantes (un ouvrier par article):
article A article B Disponi-

Méthode I Méthode II Méthode III Méthode IV bilités
Main d’oeuvre 1 ouvrier 1 ouvrier 1 ouvrier 1 ouvrier 15
α, en kg 7 8 10 12 120
β, en kg 3 2 4 3 100
Revenu unitaire 6 11/2 7 8
Dans le tableau, le revenu unitaire est donné en millier de FCFA, et la main d’oeuvre par semaine.
L’entreprise se propose d’embaucher de nouveaux ouvriers ou d’augmenter la durée de travail heb-
domadaire.
En supposant les variations d’emploi sans influence sur les revenus unitaires, indiquer, en prenant
pour critère celui de maximisation du revenu total de l’entreprise, s’il ya lieu ou non d’augmenter
la durée de travail hebdomadaire et, dans l’affirmative, de combien.
Exercice B.13. La firme ONJOB est spécialisée dans la production de deux types de produits P1
et P2 à partir de deux machines M1 et M2 . Une unité de P1 nécessite 2 heures de machine M1 et 1
heure de machine M2 . Pour le produit P2 , une unité requiert 1 heure de machine M1 et 3 heures de
machine M2 . Les revenus par unité des produits P1 et P2 sont de 30 A
C et 20 A
C, respectivement. Le
73
temps total de fabrication disponible pour chaque machine est de 8 heures. L’entreprise souhaitant
fabriquer son agent au moindre coût, on demande de réaliser le travail suivant:
1. Formuler un modèle sous la forme d’un programme linéaire qui donne le plan de production
de la firme. Justifier le choix des variables, de la fonction objectif et des contraintes.
2. Ce programme est t-il sous la forme canonique ?
3. Résoudre le programme obtenu par la méthode du simplexe. Donner toutes les interprétations
à l’optimum.
4. Déterminer le plan de production qui maximise le profit de ONJOB.
5. Ecrire le programme dual. Quelle interprétation peut-on donner à ce programme ?
6. En déduire la solution pour ce problème. Interpréter.
7. Analyse de sensibilité : l’objectif est d’analyser graphiquement la sensibilité de la solu-

tion optimale lorsque des changements sont effectués sur la capacité horaire d’une des deux
machines M1 ou M2 .
(a) Utiliser la méthode graphique pour résoudre le programme obtenu dans la question 1.
(b) Si la capacité horaire h de la machine M1 est passé de 8 heures à 9 heures; analyser

graphiquement la nouvelle solution optimale (on explicitera ce point sur le graphique).
(c) L’entreprise ONJOB a-t-elle intérêt à accepter cette heure-machine supplémentaire ?

Justifier.
(d) Le ratio du changement de l’optimum z résultant du changement de la disponibilité de la

∆z
machine peut être calculé comme suit : r = ∆h
. Calculer le ratio obtenu. Analyser et
interpréter le résultat obtenue.
Exercice B.14. On considère le problème primal suivant:
min f (x) =16500x1 + 2500x2 + 21300x3
s.c. 5x1 + x2 + 9x3 ≥ 3
7x1 + x2 + 7x3 ≥ 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1. Calculer le problème dual et le mettre sous forme standard. Donner le type et le rôle des
variables utilisées.
74
2. En appelant y3 , y4 et y5 les variables d’écart dans le dual, montrer que l’ensemble {y3 , y4 , y5 }
constitue une base réalisable.
3. Résoudre le problème dual par la méthode du simplexe.
4. Que vaut la fonction objectif du problème initial à l’optimum ? Pour quelles valeurs cet
optimum est-il atteint (utiliser le théorème de la dualité) ?
Exercice B.15. Nous reprenons le modèle de l’exercice B.1.
1. Si les deux biens produits sont entiers, faite une représentation faisant apparaître l’ensemble
admissible.
2. En déduire le programme de production optimal en nombres entiers.
Exercice B.16. Résoudre par la méthode graphique le programme linéaire en nombres entiers suiv-
ant:
max f (x) = 3x1 + 5x2
s.c. x1 + 2x2 ≤ 3
6x1 + 8x2 ≤ 15
C Quelques devoirs et examens corrigés

Devoir C.1.
Exercice C.1. On considère le problème primal suivant:
min f (x) =16500x1 + 2500x2 + 21300x3
s.c. 5x1 + x2 + 9x3 ≥ 3
7x1 + x2 + 7x3 ≥ 4
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1. Calculer le problème dual et le mettre sous forme standard. Donner le type et le rôle des
variables utilisées. 3 points
Réponse: (1 point pour le dual + 1 point pour forme standard + 0.5 point le type + 0.5 point
75
le rôle)
Le problème dual est donné par :
max g(y) =3y1 + 4y2
s.c. 5y1 + 7y2 ≤ 16500
y1 + y2 ≤ 2500
9y1 + 7y2 ≤ 21300
y1 ≥ 0, y2 ≥ 0
La forme standard est obtenu par l’introduction des variables d’écart notées y3 , y4 et y5 . Ainsi
on obtient:
max g(y) =3y1 + 4y2
s.c. 5y1 + 7y2 + y3 = 16500
y1 + y2 + y4 = 2500
9y1 + 7y2 + y5 = 21300
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0
Type: variables d’écart. Rôle: Les variables d’écart permettent de saturer les contraintes (mais
aussi d’avoir une solution de base réalisable).
2. En appelant y3 , y4 et y5 les variables d’écart dans le dual, montrer que l’ensemble {y3 , y4 , y5 }
constitue une base réalisable. 1.5 points
Réponse: 
 5y + 7y2 + y3 = 16500
 1


Le système y1 + y2 + y4 = 2500 possède une infinité de solutions. Les solutions réal-



 9y + 7y + y = 21300
1 2 5
isables du problème sont les solutions positives de ce système d’équations (car y1 ≥ 0, y2 ≥
0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0).
On peut considérer une première solution réalisable, celle obtenue en donnant à y1 et y2 la
valeur 0. Ainsi: une solution de base réalisable est donnée par y1 = y2 = 0, y3 = 16500,
y4 = 2500 et y5 = 21300.
3. Résoudre le problème dual par la méthode du simplexe. 2 points

Réponse:
76
i y1 y2 y3 y4 y5
3 5 7 1 0 0 16500 L1
4 1 1 0 1 0 2500 L2
5 9 7 0 0 1 21300 L3
z 3 4 0 0 0 0 L4
0
2 5
7
1 1
7
0 0 16500
7
L1 = 17 L1
0 0
4 2
7
0 - 17 1 0 1000
7
L2 =L2 -L1
0 0
5 4 0 -1 0 1 4800 L3 =L3 -7L1
0 0
z 1
7
0 - 47 0 0 − 66000
7
L4 =L4 -4L1
00 0 00
2 0 1 1
2
- 52 0 2000 L1 =L1 - 75 L2
00 0
1 1 0 - 12 7
2
0 500 L2 = 72 L2
00 0 00
5 0 0 1 -14 1 2800 L3 =L3 -4L2
00 0 00
z 0 0 - 12 - 21 0 −9500 L2 =L4 - 71 L2
Table 27: Tableau du simplexe de l’exercice 1.
La tableau du simplexe est donné par le tableau 27. On en tire la solution optimale. On
obtient: y1∗ = 500, y2∗ = 2000, y3∗ = y4∗ = 0 et y5∗ = 2800. La valeur optimale est g(y ∗ ) = 9500.
4. Que vaut la fonction objectif du problème initial à l’optimum ? Pour quelles valeurs cet opti-
mum est-il atteint (utiliser le théorème de la dualité) ? 1 point
Réponse: (0.5 point + 0.5 point)
La fonction objectif du problème initial à l’optimum est f (x∗ ) = 9500.
Dans le dernier tableau du simplexe, on tire les valeurs pour lesquelles cet optimum est atteint
(solution optimale). On a: x∗1 = 21 , x∗2 = 1
2
et x∗3 = 0.
Exercice C.2. Une entreprise est capable de produire deux biens b1 et b2 . Ces productions font
intervenir deux facteurs fixes : la main d’oeuvre et des équipements. L’emploi de la main d’oeuvre
est rigide à la hausse et à la baisse, la quantité disponible étant égale à 2. La capacité de production
des équipements est égale à 1 et ils n’interviennent que pour la production du second bien. On veut
maximiser la marge sur coût variable, les marges unitaires étant de 15000 FCFA et 10000 FCFA,
respectivement.
La main d’oeuvre et les équipements nécessaire pour la production d’une unité des biens est donné
77
dans le tableau suivant:
main d’oeuvre équipements

b1 2 -
b2 1 1
1. Ecrire le programme correspondant. Le mettre sous forme matricielle. 4 points

Réponse: (3 points pour le programme (1 point pour les variables, 1 point pour les contraintes
et 1 point pour la fonction objectif ) + 1 point pour forme matricielle)
variables: Soient xi = la quantité de biens bi à fabriquer, i = 1, 2.
fonction objectif: max 15 000x1 + 10 000x2
contraintes:
2x1 + x2 ≤ 2 (main d’oeuvre)
x2 ≤ 1 (équipements)
Le programme à résoudre est le suivant:
max f (x) =15 000x1 + 10 000x2
s.c. 2x1 + x2 ≤ 2
x2 ≤ 1
x1 ≥ 0, x2 ≥ 0
Matriciellement, on peut écrire le programme sous la forme:
max cT x
s.c. Ax ≤ b
x≥0
       
x1 15 000 2 1 2
avec x =  , c =  , A =   et b =  .
x2 10 000 0 1 1
2. Résoudre graphiquement le programme obtenu. En déduire le programme de production opti-

mal. 2 points
Réponse:
78
 est représentée sur la figure. La solution est au point B qui a pour
La résolutiongraphique
1/2
coordonnées  . La valeur optimale est de f (B) = 15000 ∗ 1 + 10000 ∗ 1 = 17 500.
2
1
NB: Mon échelle est par 1 c = 0.1 cm en abscisse et 1 c = 0.2 cm en ordonnée.
3. Résoudre le programme numériquement en utilisant l’algorithme du simplexe. 2.5 points

Réponse: (0.5 point pour la forme standard + 2 points pour la résolution)
La forme standard est obtenu par l’introduction des variables d’écart notées x3 et x4 . Ainsi
on obtient:
max f (x) =15 000x1 + 10 000x2
s.c. 2x1 + x2 + x3 = 2
x2 + x4 = 1
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
La tableau du simplexe est donné par le tableau 28. On en tire la solution optimale. On
obtient: x∗1 = 21 , x∗2 = 1 et x∗3 = x∗4 = 0. La valeur optimale est f (x∗ ) = 17500.
4. Illustrer sur le graphique le chemin suivi par l’algorithme du simplexe. 1 point

Réponse:
79
i x1 x2 x3 x4
3 2 1 1 0 2 L1
4 0 1 0 1 1 L2
z 15000 10000 0 0 0 L3
0 0
1 1 1
2
1
2
0 1 L1 = 21 L1
0
4 0 1 0 1 1 L2 =L2
0 0
z 0 2500 -7500 0 -15000 L3 =L3 -15000L1
00 0 00
1 1 0 1
2
- 21 1
2
L1 =L1 - 21 L2
00 0
2 0 1 0 1 1 L2 =L2
00 0 00
z 0 0 -7500 -2500 −17500 L3 =L3 -2500L2
Table 28: Tableau du simplexe de l’exercice 2.
Le
 chemin
 suivi par
 le  figure. Les points parcourus sont O =
simplexe est illustré dans la 
0 1 1/2
 , puis A =   et ensuite l’optimum B =  .
0 0 1
5. Ecrire le dual. Interpréter ce programme et en déduire sa solution optimale. 1.5 points

Réponse: (1 point + 1 point + 0.5 point)
Le programme dual est donné par: (1 point)
min g(y) =2y1 + y2
s.c. 2y1 ≥ 15 000
y1 + y2 ≥ 10 000
y1 ≥ 0, y2 ≥ 0
Interprétation: (1 point)
Ici, on miminime l’utilisation des ressources constituées des facteurs fixes que sont la main
d’oeuvre et les équipements.
Solution: (0.5 point)
Elle est déduite à partir du dernier tableau du simplexe. On a: y1∗ = 7500, y2∗ = 2500 et
g(y ∗ ) = 17500.
6. Si la capacité de production des équipements passe de 1 à 3, analyser graphiquement si la

solution optimale change. Si oui, donner la nouvelle valeur obtenue. 2 points
80
Réponse: (1 point + 1 point)
On doit résoudre dans ce cas le problème suivant:
max f (x) =15 000x1 + 10 000x2
s.c. 2x1 + x2 ≤ 2
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
La résolution graphique est représentée sur la figure suivante: (1 point)
Oui, la solution change. (1 point)  

0
ELle est maintenant au point D qui a pour coordonnées  . La valeur optimale est de
2
f (D) = 15000 ∗ 0 + 10000 ∗ 2 = 20 000.
Devoir C.2.
Exercice C.3. Une entreprise familiale basée à Ngaye Mékhé, dans la région de Thiès, vend des
chaussures de fabrication artisanale. Malick et ses deux soeurs, Adama et Astou, travaillent à
la fabrication et à la vente de deux types de chaussures : des sandales et des mocassins. Malick
s’occupe de l’assemblage de chaque chaussure, Adama fabrique les composants de chaque chaussure,
81
alors que Astou est en charge de la prise de commandes et de la livraison des chaussures. Malick
et Adama sont disponibles jusqu’à 40 heures par semaine, alors que Astou peut travailler jusqu’à
20 heures par semaine dans l’entreprise familiale. Les temps requis pour chaque tâche en fonction
du type de chaussures, de même que les profits pour chaque type de chaussure, sont donnés dans le
tableau suivant. Le problème consiste à déterminer combien de sandales et mocassins doivent être
Tâche sandales (heures/unité) mocassins (heures/unité)

assemblage 6 4
fabrication des composants 8 4
prise de commandes et livraison 3 3
profit/unité(A
C) 350 250
fabriqués à chaque semaine de façon à maximiser le profit total.
1. Formulez ce problème à l’aide d’un modèle de programmation linéaire. 4 points

Solution:
Soient x1 = le nombre d’unités de chaussures sandales à fabriquer et x2 = le nombre d’unités
de chaussures mocassins à fabriquer.
Le problème est donc modélisé par le problème de programmation mathématique suivant:
max f (x) = 350x1 + 250x2
s.c. 6x1 + 4x2 ≤ 40
8x1 + 4x2 ≤ 40
3x1 + 3x2 ≤ 20
x1 ≥ 0, x2 ≥ 0
2. Donnez l’écriture matricielle du programme obtenu. 2 points

Solution:
Matriciellement, on peut écrire le programme sous la forme:
max cT x
s.c. Ax ≤ b
x≥0
82
   
   6  4 40
x1 350   
avec x =  , c =  , A =  8 4  et b =  40 .
   
x2 250    
3 3 20
3. Donnez la forme standard du programme. 1 point

Solution:
La forme standard est donnée par:
max f (x) = 350x1 + 250x2
s.c. 6x1 + 4x2 + x3 = 40
8x1 + 4x2 + x4 = 40
3x1 + 3x2 + x5 = 20
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
avec x1 , x2 les variables initiales; et x3 , x4 , x5 les variables d’écart.
4. Résolution avec l’algorithme du simplexe. 4 points

Solution:
Le dernier tableau du simplexe est donné par le tableau suivant:
3 0 0 1 - 12 - 20
3
20
3
1 1 0 0 1
4
- 10
3
10
3
2 0 1 0 - 14 20
3
10
3
z 0 0 0 -25 -50 -2000
On en tire la solution optimale. On obtient: x∗1 = 10

3
, x∗2 = 10
3
, x3 = 20
3
et x∗4 = x∗5 = 0. La
valeur optimale est f (x∗ ) = 2000.
5. En déduire le programme de production optimal de l’entreprise familiale. 1 point

Solution:
Pour maximiser son profit total, l’entreprise familiale doit plutôt chercher à fabriquer une
quatité de 10
3
de sandales et 10
3
de mocassins. Le profit total est de 2000 A
C.
NB: On pourrait penser à prendre la partie entière (±1) pour la production des sandales et
des mocassins.
6. Formulez le dual de ce problème et proposez une interprétation de la signification des variables

duales. En déduire sa solution optimale. 3 points
83
Solution:
1.5 points programme dual:
min g(y) = 40y1 + 40y2 + 20y3
s.c. 6y1 + 8y2 + 3y3 ≥ 350
4y1 + 4y2 + 3y3 ≥ 250
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
0.5 point Interprétation: ici on minimise l’utilisation des ressources humaines en nombre
d’heures de Malick, Adama et Astou.
1 point Solution du dual: elle est déduite à partir du dernier tableau du simplexe. On a:
y1∗ = 0, y2∗ = 25, y3∗ = 50 et g(y ∗ ) = 2000.
Exercice C.4. On considère le problème de programmation linéaire suivant:
max f (x) = 3x1 + 2x2
s.c. 2x1 + x2 ≤ 6
x1 + 2x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
1. Utilisez la méthode graphique pour résoudre ce programme. 3 points

Solution:
2 points Le domaine réalisable est représentée sur la figure.
84
 
2
1 point La solution est au point A de coordonnées  . La valeur optimale est de
2
f (B) = (3 ∗ 2) + (2 ∗ 2) = 6 + 4 = 10.
2. On suppose que la capacité de la deuxième contrainte est passée de 6 à 7. Etudier graphique-

ment les conséquences sur la solution optimale. 3 points
Solution:
Si la capacité
 de ladeuxième contrainte passe de 6 à 7, la nouvelle solution est donnée par le
5/3
point B =  , avec comme valeur optimale f (B) = (3 ∗ 5 ) + (2 ∗ 8 ) = 31 = 10.3333.
3 3 3
8/3
La figure est donnée par:
85
NB: on peut représenter la nouvelle droite d’équation x1 + 2x2 = 7 sur la même figure que la
précédente.
Examen C.1.
Exercice C.5. Questions de cours: (5 points)
1. Donner les trois étapes de la formulation d’un problème d’optimisation. 1 point
2. Donner la forme matricielle d’un programme linéaire ainsi que son dual. 2 points
3. Énoncer les deux critères de Dantzig et le test d’optimalité de l’algorithme du simplexe. 2

points
Corrigé
1. La formulation d’un problème d’optimisation comporte toujours les trois étapes suivantes :
(a) choix des variables du modèle,
(b) formulation de l’objectif (ou critère),
(c) formulation des contraintes.
86
2. Soit n le nombre de variables et p le nombre de contraintes. Posons: cT = (c1 , c2 , ..., cn )6
le vecteur des coefficients de la fonction objectif; bT = (b1 , b2 , ..., bp ) le vecteur du second
membre, c’est à dire des bornes supérieures. Soit A la matrice de p lignes et n contraintes,
notée A(p, n):
 
a11 a12 . . . a1n
 
 
 a21 a21 . . . a2n 
A=
 .. .. .. 

 . . . 
 
ap1 ap2 . . . apn
et xT = (x1 , x2 , ..., xn ) le vecteur des variables de décision.

La forme matricielle d’un programme linéaire s’écrit alors en trois (3) lignes:
max cT x
s.c. Ax ≤ b
x≥0
3. • Premier critère: On fait entrer dans la base le vecteur Ak tel que la quantité k − ck
(si l’on maximise la fonction objectif ) ou ck − k (si on minimise) soit en valeur absolue
aussi grande que possible.
• Deuxième critère: On fait sortir de la base le vecteur Ai pour lequel λ = xi

tik
est aussi
petit que possible (mais positif ).
Test d’optimalité: Cette transformation est à faire jusqu’à ce que tous les coûts marginaux
des variables xk soient négatives ou nulles.
Exercice C.6. On considère le programme linéaire suivant:
max f (x) = − 9x1 + 25x2
s.c. 2x1 + 5x2 ≥ 12
− 2x1 + 5x2 ≤ 10
x1 − 2x2 ≥ 4
x1 ≥ 2
x1 ≤ 7
x2 ≥ 1
x2 ≤ 4
6 T
c désigne la transposé du vecteur c
87
1. Faire une résolution graphique soignée. On fera apparaître clairement la région réalisable et
la solution optimale. 2.5 points
2. En vous servant du graphique obtenu à la question 1., déterminer et justifier rapidement si

les points A(2, 1), B(5, 1) et C(6, 1) sont: (1.5 points)
• des solutions de base,
• des solutions de base réalisable.
3. Nous souhaitons à présent résoudre le problème avec l’algorithme du simplexe.
(a) Écrire le problème sous forme standard. 1.5 points
(b) Donner uniquement le premier tableau du simplexe. 1.5 points
Corrigé
1. Résolution graphique. (2.5 points)
88
La résolution
  graphique
  est représentée
  sur la figure, où nous avons 3 points candidats: E1 =
6 7 7
 , E2 =  , E3 =  , La solution est au point E3 qui a pour coordonnées
1 1 3/2
   
7 7
 . La valeur optimale est de f (E3 ) = f   = −9 ∗ 7 + 25 ∗ 3/2 = −25.5.
3/2 3/2
2. (0.5 
pointpar point) 
2 5
A =   et B =   ne sont pas réalisables car n’appartiennent pas au domaine ad-
1 1
missible. 
6
et C =   = E1 : est une solution de base réalisable.
1
3. La forme standard est donnée par (avec M très grand): (1.5 points)
max f (x) = − 9x1 + 25x2 − M (x4 + x7 + x9 + x12 )
s.c. 2x1 + 5x2 − x3 + x4 = 12
− 2x1 + 5x2 + x5 = 10
x1 − 2x2 − x6 + x7 = 4
x1 − x8 + x9 = 2
x1 + x10 = 7
x2 − x11 + x12 = 1
x2 + x13 = 4
x1 , x2 , ..., x13 ≥ 0
où:
x1 et x2 sont les variables initiales,
x3 , x5 , x6 , x8 , x10 , x11 et x13 sont les variables d’écart,
x4 , x7 , x9 et x12 sont les variables artificielles.
4. La forme standard peut aussi s’écrire en tirant les variables artificielles: (0.5 point)
x4 = 12 − 2x1 − 5x2 + x3 ,
x7 = 4 − x1 + 2x2 + x6 ,
x9 = 2 − x1 + x8 ,
89
x12 = 1 − x2 + x11 .
max f (x) =(−9 + 4M )x1 + (25 + 4M )x2 − M x3 − M x6 − M x8 − M x11 − 19M
s.c. 2x1 + 5x2 − x3 + x4 = 12
− 2x1 + 5x2 + x5 = 10
x1 − 2x2 − x6 + x7 = 4
x1 − x8 + x9 = 2
x1 + x10 = 7
x2 − x11 + x12 = 1
x2 + x13 = 4
x1 , x2 , ..., x13 ≥ 0
Le premier tableau du simplexe est le suivant: (1 point)
i x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13

4 2 5 -1 1 0 0 0 0 0 0 0 0 0 12 L1
5 -2 5 0 0 1 0 0 0 0 0 0 0 0 10 L2
7 1 -2 0 0 0 -1 1 0 0 0 0 0 0 4 L3
9 1 0 0 0 0 0 0 -1 1 0 0 0 0 2 L4
10 1 0 0 0 0 0 0 0 0 1 0 0 0 7 L5
12 0 1 0 0 0 0 0 0 0 0 -1 1 0 1 L6
13 0 1 0 0 0 0 0 0 0 0 0 0 1 4 L7
z -9+4M 25+4M -M 0 0 -M 0 -M 0 0 -M 0 0 0 L8
Remarque: On peut aussi représenter le tableau sans mettre les colonnes x4 , x7 , x9 et x12 .
Exercice C.7. Une entreprise fabrique des produits I, II et III à partir de ressources. Le tableau
ci-dessous donne les consommations par unité de produit fabriqué.
I II III disponibilité
des ressources
heure-machine 2 3 1 10
matière première 1 4 3 15
90
Les recettes fournies par unité de produit fabriqué sont respectivement 6, 4 et 5 kFCFA.
1. Formuler le problème sous la forme d’un programme linéaire qui maximise les recettes. 2
points
2. Résoudre le programme obtenu par la méthode du simplexe. En déduire un plan de production.

Est-il unique ? 3 points
3. Interpréter les variables duales du problème. Peut-on les trouver dans le tableau optimal du
simplexe ? 1.5 point
4. L’entreprise pourrait disposer d’une heure-machine supplémentaire au prix de 3 kFCFA; a-t-

elle intérêt à accepter cette offre ? et si on lui propose plutôt une unité de matière première
au prix de 1/2 kFCFA ? 1.5 points
Corrigé
1. variables: Soient xi = la quantité fabriquée pour le produit i avec i = 1, 2, 3.

fonction objectif: max 6x1 + 4x2 + 5x3
contraintes:
2x1 + 3x2 + x3 ≤ 10 (heure-machine)
x1 + 4x2 + 3x3 ≤ 15 (matière première)
Le programme à résoudre est le suivant:
max f (x) = 6x1 + 4x2 + 5x3
s.c. 2x1 + 3x2 + x3 ≤ 10
x1 + 4x2 + 3x3 ≤ 15
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
2. La forme standard ainsi que le tableau du simplexe sont donnés respectivement par : (2
points)
max f (x) = 6x1 + 4x2 + 5x3
s.c. 2x1 + 3x2 + x3 + x4 = 10
x1 + 4x2 + 3x3 + x5 = 15
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
91
i x1 x2 x3 x4 x5
4 2 3 1 1 0 10 L1
5 1 4 3 0 1 15 L2
z 6 4 5 0 0 0 L3
0
1 1 3
2
1
2
1
2
0 5 L1 = 12 L1
0 0
5 0 5
2
5
2
- 12 1 10 L2 =L2 -L1
0 0
z 0 -5 2 -3 0 -30 L3 =L3 -6L1
00 0 00
1 1 1 0 3
5
- 51 3 L1 =L1 - 12 L2
00 0
3 0 1 1 - 15 2
5
4 L2 = 25 L2
00 0 00
z 0 -7 0 - 13
5
- 45 -38 L3 =L3 -2L2
On a: x∗1 = 3, x∗2 = 0, x∗3 = 4 et f (x∗ ) = 38 × 103 = 38 000. (0.5 point)

D’où le plan de production: pour maximiser la recette, l’entreprise doit produire 3 quantités
du produit I, et 4 du produit III avec un profit de 38 000 FCFA.
On est en face d’un programme dont la résolution donne une solution unique (les coûts des
variables hors base sont négatives). (0.5 point).
3. Dans le dual on minimise l’utilisation des ressources utilisées pour la fabrication des produits
I, II, III.
Les variables y1 et y2 sont les nombres d’heures d’utilisation et de matières premières des
ressources 1 et 2. (1 point)
OUI, on
 peut bien les retrouver dans le tableau du simplexe. (0.5 point)
 y ∗ = 13 = 2.6
 1 5


On a: y2∗ = 45 = 0.8


 f (y ∗ ) = 38 000.

4. (a) Si l’entreprise dispose d’une heure-machine supplémentaire au prix de 3 kFCFA, on peut
92
résoudre le problème suivant:
max f (x) = 6x1 + 4x2 + 5x3 + 3x4
s.c. 2x1 + 3x2 + x3 + x4 ≤ 10
x1 + 4x2 + 3x3 ≤ 15
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
où la variable x4 représente un produit quelconque fabriqué à partir de l’heure machine sup-

plémentaire.



 x∗1 = 0


x∗2 = 0





La résolution donne (par le simplexe): x∗3 = 5


x∗4 = 5






f (y ∗ ) = 40 000 > 38 000.


Donc l’entreprise a intérêt à prendre cette offre. (1 point)
(b) Si on propose un unité de matière première au prix de 0.5 kFCFA, on résout :
max f (x) = 6x1 + 4x2 + 5x3 + 0.5x4
s.c. 2x1 + 3x2 + x3 ≤ 10
x1 + 4x2 + 3x3 + x4 ≤ 15
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0



 x∗1 = 3


x∗2 = 0





La résolution donne (par le simplexe): x∗3 = 4


x∗4 = 0






 f (y ∗ ) = 38 000.

La solution ne change pas =⇒ donc l’entreprise n’a pas intérêt à prendre. (0.5 point)
D Les principaux solvers - modeleurs

La résolution manuelle ne peut se faire que pour des petits problèmes. Le recours à l’informatique est
indispensable pour des problèmes de grande dimension. Pour les problèmes réels, les entreprises
93
font appel à des solveurs professionnels. On appelle solveur un programme (ou un sous programme)
informatique permettant de résoudre un problème d’optimisation sous contraintes. Nous en citons
quelques uns, qui ne concernent pas uniquement ceux de la programmation linéaire en variables
continues et de la programmation linéaire en nombres entiers étudiées dans ces chapitres.
D.1 Solveurs libres
• Couenne (Global Optimization and Mixed Integer Nonlinearly Constrained Optimization)
• GLPK (Linear Programming and Mixed Integer Programming)
• LP-SOLVE (Mixed Integer Linear Programming)
• IPOPT (Nonlinearly Constrained Optimization)
• Bonmin (Mixed Integer Nonlinearly Constrained Optimization)
• CLP (Linear Programming)
• R Project (Linear Programming and Nonlinearly Constrained Optimization)
• Python ((Linear Programming, Nonlinearly Unconstrained Optimization and Nonlinearly

Constrained Optimization)
• SoPlex80bit (Linear Programming)
• OCTAVE (Linear Programming and Nonlinearly Constrained Optimization)
• SCILAB (Linear Programming and Nonlinearly Constrained Optimization)
• etc.
D.2 Solveurs commerciaux
• CPLEX (Linear Programming, Mixed Integer Linear Programming and Second Order Conic
Programming )
• LOQO (Nonlinearly Constrained Optimization)
• GUROBI (Linear Programming, Mixed Integer Linear Programming and Second Order Conic
Programming)
94
• OOQP (Linear Programming)
• FICO-Xpress (Linear Programming, Mixed Integer Linear Programming, Nonlinearly Con-

strained Optimization and Second Order Conic Programming)
• MINOS (Nonlinearly Constrained Optimization)
• LINDOGlobal (Global Optimization and Mixed Integer Nonlinearly Constrained Optimiza-

tion)
• MATLAB (Linear Programming, Mixed Integer Linear Programming, Nonlinearly Uncon-

strained Optimization and Nonlinearly Constrained Optimization)
• SOLVER EXCEL (Linear Programming)
• LANCELOT (Nonlinearly Constrained Optimization)
• Knitro (Complementarity Problems, Mixed Integer Nonlinearly Constrained Optimization,

Mathematical Programs with Equilibrium Constraints and Nonlinearly Constrained Opti-
mization)
• etc.
D.3 Modeleurs
• OPL Studio
• AMPL
• GAMS
• AIMMS
• LINGO
• LP-TOOLKIT
• MathPro
• MINOPT
• MPL
95
• OMNI
• etc.
References
[1] J.C. Culioli, Introduction à l’optimisation, 2nd édition, 384 pages, Lybrairie Eyrolles, 2012.
[2] Horst, R., Pardalos, P. and Thoai, N., Introduction to Global Optimization, (eds.): 1995, Vol.
3 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht.
[3] Michel Minoux, Programmation linéaire. 2nd edition. edition Eyrolles, 2007.
[4] Horst, R. and Thy, H., Global Optimization: Deterministic Approaches, Springer, Berlin, 1990.
[5] Dantzig G.B., Maximisation of Linear Function of Variables Subject to Linear Inequalities.
Activity Analysis of Production and Allocation, T.C. Koopmans ed., New York, Wiley, 1951.
[6] Dantzig G.B., Computational Algorithm of the Revisited Simplex Method. Rand Report, R.M.
1266, 1953.
[7] I. Charon, O. Hudry Introduction à l’optimisation continue et discrète Avec exercices et prob-
lèmes corrigés, Hermès - Lavoisier, 502 pages, 2019.
[8] Eric Jacquet-Lagrèze, Programmation linéaire. Ed. Economica, 1998.
[9] Teghem Jacques, Recherche Opérationnelle - Tome 1 : Méthode d’optimisation. Edition Ellipse,
624 pages. Collection : Références sciences, 2012.
[10] Janos D. Pinter and Jnos D., Global Optimization: Scientific and Engineering Case Studies.,
Pintr., Springer, February 28, 2006.
[11] Dantzig, G. B., and Thapa, M. N., Linear Programming 2: Theory and Extensions. Springer-
Verlag, New York, 2003.
[12] François Phelizon, Méthodes et Modèles de la recherche opérationnelle de Jean. éd. Economia.
[13] Dewerra D., Liebling Th.M., Hêche J.F., Recherche opérationnelle pour ingénieurs tome 1 et
tome 2. éd. Presses polytechniques et universitaires romandes.
[14] Robert Faure, Précis de Recherche opérationnelle. éd. Dunod.
96
[15] Dominique Lacaze, Optimisation appliquée à l’économie et à la gestion. éd. Economia.
[16] Desbazeille G. Exercices et problèmes de Recherche opérationnelle. éd. Dunod.
[17] De Wolf D., Cours de Daniel DE WOLF Universités de Villeneuve d’Asq. Dunkerque, Lille.
[18] Vaivre S.B., Ficano C. Outils mathématiques de gestion. éd. Bréal.
[19] Ciarlet P.G., Introduction à l’analyse numérique matricielle et à l’optimisation cours et exer-
cices corrigés. Mathématiques appliquées pour la maîtrise. Dunod, 1998.
[20] Vincent Giard, Gestion de la production et des flux. éd. Economica.
[21] Vallin P., Vanderpooten D., Aide la Décision vue approche par les cas. éd. Ellipses.
[22] Beaumont C.M. Mathématiques financières et Recherche opérationnelle en Techniques quanti-

tatives de Gestion . éd. Ellipses.
97

Cours RO Master1

Transféré par

Droits d'auteur :

Formats disponibles

Cours RO Master1

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours RO Master1

Transféré par

Droits d'auteur :

Formats disponibles

Cours Recherche Opérationnelle:

Université Cheikh Anta Diop (UCAD) de Dakar

2 PROGRAMMATION LINÉAIRE EN NOMBRES ENTIERS 44

C Quelques devoirs et examens corrigés 75

D Les principaux solvers - modeleurs 93

1.1 Petits exemples pratiques

Exemple 1 : L’entreprise SIMPA (Société Industrielle et Moderne des Plastiques Africains) du

X Modélisation du problème: Nous examinons dans l’ordre la représentation des variables de

7x1 + 3x2 ≤ 200

4x1 + 4x2 ≤ 150

Le critère : on souhaite maximiser le profit quotidien de l’entreprise SIMPA (venant de la vente

max f (x) = 40000x1 + 20000x2

s.c. 7x1 + 3x2 ≤ 200

4x1 + 4x2 ≤ 150

Exemple 2 : Une entreprise spécialisée dans la fabrication de matériels informatiques, propose à

X Modélisation du problème: Nous examinons dans l’ordre la représentation des variables de

2x1 + 6x2 ≤ 48000

Le critère : on souhaite maximiser le profit de l’entreprise représenté par : 40000x1 + 80000x2 .

2x1 + 6x2 ≤ 48000

machine main d’oeuvre

X Modélisation du problème: Nous examinons dans l’ordre la représentation des variables de

s.c. 0.5x1 + 1.5x2 ≤ 12

1.2 Définition et formulation d’un problème de programmation

1.2.1 Définition d’un programmation linéaire

1. choix des variables du modèle,

2. formulation de l’objectif (ou critère),

3. formulation des contraintes.

X La première étape consiste à choisir les variables du problème.

X La deuxième étape consiste à formuler mathématiquement l’objectif.

X La troisième étape est la formulation les contraintes du problème.

Un problème sera modélisé par un problème de programmation linéaire si :

La forme générale d’un problème de programmation linéaire de n variables et p contraintes est :

sous les contraintes

ai1 x1 + ai2 x2 + ... + ain xn ≤, ≥ ou = bi pour i = 1, ..., p

xj ≥0, pour j = 1, ..., n

X La PL est essentiellement appliquée pour résoudre des problèmes d’optimisation à moyen et

• les problèmes de mélange : quelle est la composition optimale d’un produit ?

• les problèmes de détermination optimale de production d’une raffinerie,

• les problèmes de planification de production : quand et à quel moment doit-on planifier la

• les problèmes de transport, généralisation du problème de transport classique,

• les problèmes de planification d’horaires,

• les problèmes de découpe industrielle,

1.2.3 Forme matricielle d’un programme linéaire

La propriété de linéarité de la fonction objectif et des contraintes permet de représenter un pro-

et xT = (x1 , x2 , ..., xn ) le vecteur des variables de décision.

Définition 1.7. L’ensemble réalisable C est l’ensemble défini par:

Remarque 1.3. On peut aussi écrire le problème (P) sous la forme:

1.3 Interprétation économique d’un programme linéaire

On considère le problème de programmation linéaire (P) mis sous la forme:

1.4 Résolution graphique

max f (x) = 40000x1 + 20000x2

s.c. 7x1 + 3x2 ≤ 200

4x1 + 4x2 ≤ 150

max f (x) = 40000x1 + 80000x2

2x1 + 6x2 ≤ 48000

max f (x) = 190000x1 + 260000x2

s.c. 0.5x1 + 1.5x2 ≤ 12

max f (x) = 40000x1 + 20000x2

s.c. 7x1 + 3x2 ≤ 200

4x1 + 4x2 ≤ 150

On obtient finalement, en remplaçant λk par sa valeur:

Remarque 1.6. Les k − ck représentent la variation unitaire de la fonction objectif quand on