0% ont trouvé ce document utile (0 vote)

17 vues87 pages

Modélisation et Programmation Linéaire

Le document présente un cours sur la modélisation et la programmation linéaire, destiné aux étudiants de deuxième année en génie industriel. Il aborde des concepts fondamentaux tels que la modélisation de problèmes de gestion, la résolution graphique de modèles linéaires, l'algorithme du simplexe et l'analyse postoptimale. Des exemples pratiques, comme la production de chaises, illustrent l'application de ces techniques dans un contexte industriel.

Transféré par

ツEscape

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

17 vues87 pages

Modélisation et Programmation Linéaire

Transféré par

ツEscape

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université Mohammed V

École Mohammadia d’Ingénieurs

Département de Génie Industriel

=================================================

Modélisation et Programmation Linéaire

=================================================

(Deuxième année-S3)

Année universitaire : 2018/2019

————————————————————————————————————————————–
Nizar EL HACHEMI
————————————————————————————————————————————–
1

Modélisation et Programmation Linéaire

N. EL HACHEMI UM5-EMI
Table des matières

1 Modélisation 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 La modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Quelques exemples de base . . . . . . . . . . . . . . . . . . . . 5

2 Résolution graphique de modèles linéaires continus comportant

deux variables de décision 26
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Un premier exemple : La fonderie rivière-bleue . . . . . . . . . . . . . 26
2.2.1 Description du problème . . . . . . . . . . . . . . . . . . . . . 26
2.2.2 Le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 La résoluion d’un deuxième exemple . . . . . . . . . . . . . . . . . . . 34
2.4 Les caractéristiques de l’ensemble des solutions admissibles . . . . . . 35
2.5 Une typologie des régions admissibles . . . . . . . . . . . . . . . . . . 37
2.6 Régions admissibles pour modèle linéaire . . . . . . . . . . . . . . . . 38
2.7 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.8 Régions admissibles non bornée . . . . . . . . . . . . . . . . . . . . . 39
2.9 Une typologie des solutions admissibles . . . . . . . . . . . . . . . . . 40
2.10 Les caractérisriques des solutions optimales . . . . . . . . . . . . . . . 41
2.11 Les caractérisriques des solutions optimales . . . . . . . . . . . . . . . 42

3 L’algorithme du simplexe 43
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Les variables d’écart et les variables d’excédent . . . . . . . . . . . . 43
3.3 Les Solutions de Base Admissibles . . . . . . . . . . . . . . . . . . . . 45
3.4 Modèle linéaire sous forme (PLS) . . . . . . . . . . . . . . . . . . . . 45
3.5 La caractéristique algébrique des points extrêmes . . . . . . . . . . . 46

2
3 Modélisation et Programmation Linéaire

3.6 Les solutions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.7 La résolution des modèles sous forme (PLS) . . . . . . . . . . . . . . 48
3.7.1 La construction du tableau initial . . . . . . . . . . . . . . . . 51
3.7.2 Le choix de la variable entrante . . . . . . . . . . . . . . . . . 52
3.7.3 Arrêt du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.7.4 Le choix de la variable sortante . . . . . . . . . . . . . . . . . 53
3.7.5 Tableau du simplexe sous forme canonique . . . . . . . . . . . 54
3.7.6 Choix de la variable sortante et pivotage jusqu’à la convergence 54
3.7.7 Description de l’algorithme du simplexe . . . . . . . . . . . . . 58
3.8 Le modèle PLC et la construction d’un tableau initial . . . . . . . . . 60
3.8.1 La méthode en deux phases . . . . . . . . . . . . . . . . . . . 63
3.8.2 Transition et Cas pathologiques . . . . . . . . . . . . . . . . . 67
3.8.3 La méthode du grand M . . . . . . . . . . . . . . . . . . . . . 72

4 L’analyse postoptimale 74
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2 La modification d’un coefficient cj . . . . . . . . . . . . . . . . . . . . 74
4.3 La modification d’un coefficient bj . . . . . . . . . . . . . . . . . . . . 75
4.4 Le champ de l’analyse postoptimale proposée . . . . . . . . . . . . . . 76
4.4.1 La modification du cj d’une variable originale hors base . . . . 77
4.4.2 La modification du cj d’une variable de base . . . . . . . . . . 78
4.4.3 La modification d’un bi : Signe d’inéquation . . . . . . . . . . 79
4.5 La dualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.5.1 La construction et l’interprétation du modèle dual . . . . . . . 83

N. EL HACHEMI UM5-EMI
Chapitre 1

Modélisation

1.1 Introduction
La Recherche Opérationnelle (RO) s’alimente à un développement fort actif en
recherche, mais elle jouit aussi d’un héritage de plusieurs acquis et réussites. Ses
origines historiques diverses vont permettre d’une brosser par touches successives le
portrait. En effet, à propos de la RO, on a parlé d’une méthode, d’une approche,
d’un ensemble de techniques, d’une activité née d’une collaboration multidiscipli-
naire, d’un prolongement des mathématiques, de la statistique, de l’économie et de
l’ingénierie. La RO, c’est tout cela et un peu plus, mais c’est surtout la recherche
d’optimisation d’un processus.
En 1945, on comptait en RO plus de 1000 personnes dans les groupes
américains et près de 400 dans les groupes anglais. L’industrie civile
américaine n’adopta pas tout de suite la méthodlogie RO. La résistance
au changement y fut très forte. En fait, le vent vint de l’Angleterre où,
après la guerre, la nationalisation de grandes industries (charbon, gaz,
électricité, rail et transport routier) donna le banc d’essai que nécessitait
l’implantation de cette ’philosophie’. Beaucoup de scientifiques, mis au
courant de la nouvelle approche dont le secret avait été bien gardé durant
la guerre, y adhérèrent avec la ferveur qui convient pour une idée dont
le temps est venu. Aux États-Unis, la conversion à la RO se fit d’abord
dans les universités, où les services armés financèrent la poursuite de re-

4
5 Modélisation et Programmation Linéaire

cherches amorcées pendant la guerre. C’est là qu’en 1947 Georges Dantzig
mit au point l’algorithme du simplexe, qui permit de résoudre des pro-
grammes linéaires continus proposant l’allocation optimale de ressources
rares à la production des bien manufacturés.

1.2 La modélisation
On peut résumer la modélisation à l’habileté à traduire divers problèmes
par des relations mathématiques. Les relations mathématiques obtenues
ne constituent que des modèles des problèmes considérés. Connaı̂tre une
solution optimale d’un modèle permet souvent au gestionnaire d’obtenir
de précieuses indications sur la façon de se comporter pour tirer au mieux
son épingle du jeu.
L’approche pédagogique retenue ici est empirique : nous présentons
d’entrée de jeu de nombreux exemples de problèmes de gestion ; nous
en tirons des modèles, tout en truffant notre propos de remarques et
d’observations sur lesquelles viendrons s’appuyer les généralisations et
les définitions que nous donnerons par la suite. C’est à ce moment que
nous tenterons de cerner de plus près ce processus, qui relève à la fois de
l’art, de l’expérience, de la culture mathématique et générale, qu’est la
modélisation.

1.2.1 Quelques exemples de base

Les chaises de M. Eugène

M. Eugène a adapté pour la production en courtes séries, deux modèles

d’un créteur de renom : la chaise en porte-à-faux et la chaise Barcelone.
M. Eugène les a pourvues d’une armature métallique dont les pièces sont
assemblées par brasage puis enduites de laques isolantes, ce qui confère au
métal un toucher chaud. Dossiers et sièges sont ensuite recouverts de cuirs
de Cordoue capitonnés. M. Eugène s’est engagé à livrer d’ici 3 semaines
42 chaises en porte-à-faux et 53 chaises Barcelone. Il estime à 100 unités
le marché potentiel pour chaque type. M. Eugène se propose de consacrer

N. EL HACHEMI UM5-EMI
6 Modélisation et Programmation Linéaire

à la fabrication de ces chaises toutes les heures de main d’oeuvre dont il

disposera dans son atelier pendant les prochaines 3 semaines. Le Tableau
1.1 présente les données afférentes à ce problème de production.

Opération Porte-à-faux Barcelone Heures disponibles

Brasage 1,5 (h) 2 (h) 250 (h)
Laquage 30 min 45 min 100 (h)
Capitonnage 2 (h) 3 (h) 327 (h)
Profit par chaise 450 $ 800 $

Table 1.1 – Résumé des données de fabrication

Quelles sont les informations dont doit disposer M. Eugène pour considérer
que son problème est résolu ? Il lui suffit de connaı̂tre le nombre de chaises
de chaque type à fabriquer d’ici 3 semaines, n’est-ce pas ? Agissons comme
si ces nombres nous étaient connus et dénotons-les par :
— xA : nombre de chaises ’porte-à-faux’ à fabriquer d’ici 3 semaines.
— xB : nombre de chaises ’Barcelone’ à fabriquer d’ici 3 semaines.
Quel profit M. Eugène retirera-t-il de la vente de ces chaises ? Il s’agit
d’additionner les bénéfices à tirer de chacun des 2 types de chaises. Le
profit total à tirer des chaises fabriquées s’élève donc à : z = 450xA +800xB .
Ici z est une fonction qui, à chaque plan de production, associe le nombre
de dollars que M. Eugène retirerait comme profit s’il adoptait ce plan.
Cette fonction z, qui traduit l’objectif de notre problème s’appelle ’fonc-
tion objectif ’. Dans ce cas, puisqu’il s’agit d’un profit, alors on cherchera
à le maximiser.
Il y a bien sûr des empêchements naturels, appelés ’contraintes’, qui
freinent le rêve d’un profit infini.
Les contraintes de la demande sont :
— xA ≥ 42
— xB ≥ 53
Les contraintes associées au fait de ne pas dépasser le marché potentiel
sont :

N. EL HACHEMI UM5-EMI
7 Modélisation et Programmation Linéaire

— xA ≤ 100
— xB ≥ 100
Les contraintes associées au temps disponible durant les 3 semaines à
venir sont :
— Contrainte de brasage : 1, 5xA + 2xB ≤ 250.
— Contrainte de laquage : 0, 5xA + 0, 75xB ≤ 100.
— Contrainte de capitonnage : 2xA + 3xB ≤ 327.
Contraintes de non-négativité et d’intégrité : xA , xB ≥ 0 et entiers.
Le modèle se résume ainsi :

M ax 450xA + 800xB (1.1)

subject to : (1.2)
42 ≤ xA ≤ 100 (1.3)
53 ≤ xB ≤ 100 (1.4)
1, 5xA + 2xB ≤ 250 (1.5)
0, 5xA + 0, 75xB ≤ 100 (1.6)
2xA + 3xB ≤ 327 (1.7)
xA , xB ≥ 0 (1.8)
xA , xB entiers (1.9)

Forme générale d’un modèle linéaire

X
Max (Min)z = ci x i (1.10)
i
subject to : (1.11)
 
X ≤
∀i, aij xj  =  bi (1.12)
 

≥
∀i, xi ≥ 0 (1.13)

N. EL HACHEMI UM5-EMI
8 Modélisation et Programmation Linéaire

Les conditions de linéarité

1. Le modèle comporte une fonction-objectif qu’il s’agit soit de maxi-

miser, soit de minimiser.
2. La fonction-objectif de même que les membres gauches des contraintes
s’écrivent comme des sommes dont chaque terme est un produit
d’une constant et une variable.
3. Chaque variable est soumise à une contrainte de non-négativité.
4. Le modèle ne comporte pas de contraintes écrites sous forme d’inéquations
strictes.
5. On suppose que tous les paramètres qui apparaissent dans le modèle
sont déterministes et sont connus avec précision.

Un problème de comptabilité de gestion

Vincent pratique le métier ébéniste, sa spécialité est la fabrication de

tables à langer et les berceaux en bois précieux. Aujourd’hui, le 1er Juin,
Vincent dispose d’assez de bois et de fournitures pour fabriquer 100 tables
à langer et 100 berceaux. Une table se vend 500$ et un berceau, 800$. Les
coûts de main-d’oeuvre sont de 250$ pour une table et de 350$ pour un
berceau. Le bois et les fournitures lui coûtent 75$ pour une table et 160$
pour un berceau. Une grande part de la main-d’oeuvre est occasionnelle,
elle vient principalement d’une école d’ébinisterie. Le nombre d’apprentis
disponible sera réduit au cours de la période estivale qui débute, ce qui
limite sa production de juin à un maximum de 50 tables et de 30 berceaux.
Le Tableau 1.2 présente un résumé de la situation financière de Vincent
au premier juin.
Vincent doit établir combien de tables et de berceaux il lui faut fa-
briquer au cours du mois de juin. Sa clientèle ne paie toutefois jamais
comptant : les meubles vendus en juin ne seront payés qu’au début du
mois d’août. En juin, Vincent doit recevoir 13.850$ de comptes clients et
il devra payer 1.600$ pour le loyer de son atelier. Il aura à rembourser une
partie de l’emprunt bancaire, soit 4.350$. La dernière semaine de juin,
il recevra une livraison de bois précieux valant 26.500$, qu’il lui faudra

N. EL HACHEMI UM5-EMI
9 Modélisation et Programmation Linéaire

Actif Passif
Encaisse 20.000$
Comptes clients 37.000$
Stocks* 23.500$
Emprunt bancaire 30.000$
* 23500 = (100*75)+(100*160)

Table 1.2 – Résumé de la situation financière

payer en août. Vincent veut disposer, au début de juillet, d’au moins

15.900$ pour acheter en payant comptant. Le banquier de Vincent exige
que le ratio actif/passif soit, au début de juillet égal au moins 2. Malgré
toutes ces contraintes, Vincent veut maximiser avec sa production de juin
la contribution au profit, et il se demande comment y arriver. Définissons
comme suit les variables de décision associées à ce problème :
— x1 : nombre de tables à langer à fabriquer et à vendre en juin.
— x2 : nombre de berceaux à fabriquer et à vendre en juin.
L’objectif de Vincent consiste à maximiser le profit qu’il retirera de la
production de juin. Pour une table à langer le profit est : 500 − 250 − 75 =
$175 alors que le profit d’un berceau est 800 − 350 − 160 = $290. Ainsi, le
profit consiste à maximiser z = 175x1 + 290x2 .
Considérons maintenant les contraintes du modèle :
— Contrainte de main d’oeuvre : x1 ≤ 50.
— Contrainte de main d’oeuvre : x2 ≤ 50.
— Contrainte de fournitures : x1 ≤ 100.
— Contrainte de fournitures : x2 ≤ 100.
Une contrainte est dite redondante lorsqu’elle est satisfaite par toute
solution qui vérifie les autres contraintes. Ainsi les contraintes de fourni-
tures sont redondantes.

Il faut noter qu’il faut garantir au moins 15.900$ en banque au début

de juillet, 20.000 + 13.850 − 4.350 − 1.600 − 250x1 − 350x2 ≥ 15.900. Aussi, le

N. EL HACHEMI UM5-EMI
10 Modélisation et Programmation Linéaire

ratio actif/passif doit être supérieur à 2.

— Contrainte d’encaisse : 250x1 + 350x2 ≤ 12.000.
— Contrainte de ration actif/passif : Au début de juillet, ce ratio doit
être ≥ 2.
— Encaisse = 27.900 − 250x1 − 350x2 .
— Comptes clients = 37.000 + 500x1 + 800x2 − 13.850.
— Stocks = 23.500 − (75x1 + 160x2 ) + 26.500.
— Actif = Encaisse + comptes clients + Stocks, qu’on peut écrire
comme suit : 101.050 + 175x1 + 290x2
— Passif = 30.000 − 4.350 + 26.500 = 52.150.
— La contrainte s’écrit donc comme suit : 101.050+175x52.150
1 +290x2
≥ 2.
— Ce qui se traduit par 175x1 + 290x2 ≥ 3.250.
Contraintes de non-négativité et d’intégrité : x1 , x1 ≥ 0 et entiers.
Le modèle se résume ainsi :

M ax 175x1 + 290x2 (1.14)

subject to : (1.15)
x1 ≤ 50 (1.16)
x2 ≤ 30 (1.17)
250x1 + 350x2 ≤ 12.000 (1.18)
175x1 + 350x2 ≤ 3.250 (1.19)
x1 , x2 ≥ 0 (1.20)
x1 , x2 entiers (1.21)

Le chocolatier-confiseur

Un chocolatier-confiseur reçoit une commande de 3.000 assortiments

de chocolats. Pour les confectionner, il a convenu d’y placer 3 sortes de
chocolats, dénotés chocolats 1,2 et 3, dont chaque kg lui coûte 4$, 1,45$ et
2,40$ respectivement. Chaque assortiment doit peser un kg et se vendra
8$.
Les chocolats 1 doivent représenter entre 10% et 20% du poids d’un as-

N. EL HACHEMI UM5-EMI
11 Modélisation et Programmation Linéaire

sortiment. Les chocolats 1 et 2 présents dans un assortiment ne doivent

pas peser plus de 800 g. Au moins la moitié du poids d’un assortiment
doit provenir des chocolats 1 et 3.
On cherche une recette qui est optimale pour tous les assortiments (les
3.000 assortiments seront confectionnés de la même manière). Les quan-
tités achetés, s’obtiennent en multipliant par 3.000 cette recette opti-
male. Et réciproquement, pour résoudre le problème, il suffit de connaı̂tre
le nombre de kg à acheter de chaque sorte. De ces remarques découle
immédiatement la définition des 3 variables de décision suivantes :
— xj = nombre de kg de chocolats j que se procurera le chocolatier-
confiseur, j allant de 1 à 3.
Le chocolatier-confiseur poursuit l’objectif de maximiser les profits
qu’il tirera de la vente des 3000 assortiments qu’il s’est engagé à fournir.
Un kg de chocolats se vend toujours 8$, puisque c’est là le prix de vente
de chaque assortiment et que chaque assortiment pèse 1 kg. Mais le prix
d’achat varie d’une sorte de chocolats à l’autre. C’est ainsi que le profit
réalisé sur un kg de chocolats 1 s’établit à 8$ - 4$ = 4$, de même 1
kg de chocolats 2 rapportera 8$ - 1,45$ = 6,55$ et finalement, 1 kg de
chocolats 3 rapportera 8$ - 2,4$ = 5,6$. La fonction objectif qui représente
les profits s’écrit donc :
— Max z = 4x1 + 6, 55x2 + 5, 6x3
Les contraintes du problème sont :
— Contrainte de la demande : x1 + x2 + x3 = 3000.
— Contrainte associée au poids du chocolats 1 (au moins 10%) :
x1
x1 +x2 +x3
≥ 0, 1.
— Simplification de la contrainte (poids du chocolats 1) : 0, 9x1 −0, 1x2 −
0, 1x3 ≥ 0.
— Contrainte associée au poids du chocolats 1 (au plus 20%) : 0, 8x1 −
0, 2x2 − 0, 2x3 ≤ 0.
— Contrainte associée au poids du chocolats 1 et 2 par assortirment
( au plus 800 grammes) : 0, 2x1 + 0, 2x2 − 0, 8x3 ≤ 0.
— Contrainte du poids du chocolats 1 et 3 (au moins 50%) : 0, 5x1 −
0, 5x2 + 0, 5x3 ≥ 0.

N. EL HACHEMI UM5-EMI
12 Modélisation et Programmation Linéaire

— Contraintes de non-négativité : x1 , x2 , x3 ≥ 0.
Le modèle se résume ainsi :

M ax 4x1 + 6, 55x2 + 5, 60x3 (1.22)

subject to : (1.23)
x1 + x2 + x3 = 3000 (1.24)
x1 ≥ 300 (1.25)
x1 ≤ 600 (1.26)
x1 + x2 ≤ 2400 (1.27)
x1 + x3 ≥ 1500 (1.28)
x1 , x2 , x3 ≥ 0 (1.29)

Problème d’affectation : la rotation du personnel

À intervalles réguliers, l’armée organise la rotation d’une partie de son

personnel technique entre les différentes bases militaires. Elle a plusieurs
raisons d’agir ainsi : permettre l’acquisition d’une expérience de travail
diversifiée, donner l’occasion de suivre des cours, accéder aux demandes
de mutation vers des postes où le climat est plus favorable, récompenser
ou punir certains comportements. Supposons, à titre d’exemple, que
l’armée dispose d’une liste de 10 sergents d’état-major, spécialistes de
la mécanique des chars d’assaut, et qu’elle souhaite réaffecter chacun au
poste de l’un de ses 9 collègues. Certains de ces militaires sont célibataires,
d’autres sont mariés mais n’ont pas d’enfants, d’autres encore sont mariés
et ont des enfants... L’armée a évalué pour chacun les coûts de mutation à
chaque poste. L’objectif est d’assurer au moindre coût que chaque sergent
occupe un nouveau poste et que tous les postes soient comblés.
Dénotons les sergents par les lettres A, B, ..., H, M et N. Et désignons
par i le poste occupé présentement par le sergent d’état-major I : le
sergent A occupe présentement le poste a, et ainsi de suite. Le Tableau
1.3 présente la matrice des coûts de mutation de chaque sergent à chacun
des postes.

N. EL HACHEMI UM5-EMI
13 Modélisation et Programmation Linéaire

Poste
Sergent a b c d e f g h m n
A * 12 15 11 17 15 11 12 10 10
B 6 * 14 12 16 11 17 18 18 16
C 8 17 * 21 17 16 14 12 10 15
D 7 16 9 * 12 18 18 14 11 14
E 7 13 8 12 * 22 19 12 13 12
F 8 8 11 14 12 * 12 17 9 18
G 6 9 13 9 11 16 * 14 13 16
H 7 14 16 11 16 22 15 * 14 18
M 11 16 17 15 17 18 21 22 * 11
N 8 9 8 13 9 7 8 9 8 *

Table 1.3 – Coûts des affectations possibles

Comme il n’est pas permis qu’un sergent conserve le poste qu’il oc-
cupe présentement, on remplace chaque astérisque de la diagonale par un
montant M, largement supérieur à ceux qui sont en jeu pour les mutations
envisagées, en marquant ainsi l’impossibilité de maintenir un sergent dans
son poste actuel. Posons, par exemple : M = 500.
Définissons les variables de décision binaires suivantes :
— vIj = 1 si le sergent I est muté du poste i au poste j.
— La fonction-objectif s’écrit comme suit : M inz = 500vAa + 12vAb +
15vAc + ... + 9vN h + 8vN m + 500vN n
Les contraintes qu’il faut considérer sont :
— Á chaque sergent on doit attribuer un poste.
— Chaque poste doit être comblé.
Á titre d’exemples :
— La contrainte associée au sergent A est : vAa + vAb + vAc + ... + vAn = 1.
— La contrainte associée au poste a est : vAa + vBa + vCa + ... + vN a = 1.
— Par analogie, on peut déduire les contraintes associées aux autres
sergents et postes.

N. EL HACHEMI UM5-EMI
14 Modélisation et Programmation Linéaire

Une solution optimale de ce problème est donnée dans le Tableau 1.4.

Sergent A B C D E F G H M N
Poste m f h e c b d a n g

Table 1.4 – Solution optimale ’rotation des sergents’

Les conditions logiques : l’équipe d’arpenteurs-géomètres

Une firme d’exploration minière veut recruter 6 personnes pour com-

bler les postes vacants dans une équipe d’arpenteurs-géomètres qui doit
se rendre pour de longues périodes dans le Grand Nord. On a retenu,
parmi les dossiers reçus, 12 candidatures valables. Les émoluments an-
nuels exigés par ces personnes apparaissent au Tableau 1.5.

Candidat Émoluments
1 56.000$
2 55.000$
3 54.000$
4 57.000$
5 49.000$
6 51.000$
7 54.000$
8 56.000$
9 52.000$
10 55.000$
11 53.000$
12 50.000$

Table 1.5 – Émoluments annuels exigés par les candidats

La cohésion de l’équipe est de prime importance. Des tests de person-

nalité et des séances d’interaction entre les 12 candidats menés par des

N. EL HACHEMI UM5-EMI
15 Modélisation et Programmation Linéaire

psychologues ont révélé que certaines combinaisons de candidats n’étaient

pas souhaitables. En particulier, on désire respecter les contraintes de
cohésion suivantes :
— Si les candidats 3 et 8 sont embauchés, le candidat 9 ne peut l’être.
— Si on embauche le candidat 2, il convient d’embaucher le candidat
11, et réciproquement, puisqu’ils sont mari et femme.
— Le candidat 7 est en conflit avec les candidats 4 et 5, et on ne veut
pas retenir ses services si l’un des candidats 4 ou 5, ou les deux,
sont embauchés.
— On ne peut embaucher plus de trois des cinq candidats suivants :
1, 3, 6, 10, 12.
— On doit embaucher un et un seul des trois candidats 3, 5 et 12.
Pour déterminer les variables de décision, il faudrait répondre à la
question suivante : Quels candidats faut-il embaucher ? Nous pouvons
répondre à cette question en déterminant pour chaque candidat s’il sera
embauché ou non. Ainsi, les variables de décision sont les variables bi-
naires vj (1 ≤ j ≤ 12), où vj = 1 si le candidat j est embauché. La fonction
objectif qu’il faut minimiser est la somme des émoluments de tous les
candidats embauchés.
— La fonction objectif s’écrit comme suit : M in z = 56v1 + 55v2 + 54v3 +
... + 50v12 .
Les contraintes du problème sont :
P
— Embaucher exactement 6 candidats : 1≤j≤12 vj = 6.
— Contrainte associée aux candidats 3, 8 et 9 se traduit par : v3 + v8 +
v9 ≤ 2.
— Contrainte associée aux candidats 2 et 11 se traduit par : v2 −v11 = 0.
— Contraintes associées aux candidats 4, 5 et 7 s’expriment par :
v4 + v7 ≤ 1 et v5 + v7 ≤ 1.
— On peut remplacer les deux inéquations par une seule, qui est
équivaut aux 2 précédentes : v4 + v5 + 2v7 ≤ 2
— Les dernières contraintes de qualification donnent lieu à :
1. v1 + v3 + v6 + v10 + v12 ≤ 3.
2. v3 + v5 + v12 = 1.

N. EL HACHEMI UM5-EMI
16 Modélisation et Programmation Linéaire

Une solution optimale consiste à embaucher les candidats 2, 6, 7, 9,

11 et 12, pour un coût total de 315 milliers de dollars.

La verrerie Grand Siècle

La verrerie Grand Siècle exploite une usine de verre dépoli dans cha-
cune des 5 villes suivantes : A, B, C, D et E. Le procédé de fabrication
exige de l’acide fluorhydrique que, jusqu’à maintenant, Grand Siècle en-
treposait sur l’emplacement même de ses usines. Le ministère de l’En-
vironnement exige qu’à compter de l’an prochain les fûts l’acide soient
entreposés à la campagne en des endroits où d’éventuelles émanations
accidentelles se diffuseraient dans l’atmosphère.
Grand Siècle a repéré 4 emplacements, qui ont reçu l’agrément du
Ministère, où il serait possible de stocker les fûts en attendant de les
acheminer un à un, au fur et à mesure des besoins, vers les différents
usines. Les coûts reliés à l’acquisition des terrains et à la construction
des installations de stockage varient très peu d’un emplacement à l’autre ;
une fois répartis sur la vie utile des installations, ils correspondent, se-
lon les comptables de Grand Siècle, à une dépense annuelle de 85.000 $
par emplacement. Par contre, les coûts d’entretien des chemins d’accés
différeraient de façon notable. Le Tableau 1.6 donne, pour les 4 emplace-
ments envisagés, les coûts annuels d’entretien de ces chemins d’accés.

Emplacement Coût
1 12.000$
2 4.000$
3 4.000$
4 10.000$

Table 1.6 – Coûts annuels d’entretien

Le Tableau 1.7 donne les coûts annuels, en milliers de dollars, d’ache-

minement des fûts de chacun de ces emplacements.

N. EL HACHEMI UM5-EMI
17 Modélisation et Programmation Linéaire

Emplacement A B C D E
1 7 13 11 6 11
2 9 18 5 10 23
3 16 8 5 17 15
4 12 8 7 12 8

Table 1.7 – Coût de transport en millier de $

L’objectif de Grand Siècle est de minimiser les coûts des opérations

( approvisionnement annuel des usines en fûts d’acide fluorhydrique).
Il est convenu que chaque usine sera approvisionnée à partir d’un seul
emplacement. La direction se pose deux questions :
— Sur quel(s) emplacement(s) faut-il construire des installations de
stockage ?
— Quelles sont les usines qui seront approvisionnées en acide à partir
de chaque emplacement où des installations de stockage auront été
construites ?
Répondre à la première question revient à déterminer, pour chaque
emplacement, si oui ou non, on y construira des installations de stockage.
De plus, pour qu’une usine puisse être approvisionnée à partir d’un em-
placement, il faut que les installations de stockage y aient été aménagées
et que le chemin d’accés soit entretenu. On est donc amené à introduire
les variables de décision binaires suivantes :
— vi = 1 si Grand Siècle construit un entrepôt sur l’emplacement i.
— wiJ = 1 si l’entrepôt de l’emplacement i alimente en fûts l’usine de
la ville J.
La fonction objectif consiste à minimiser z obtenue en additionnant
l’amortissement annuel, coûts annuels d’entretien des chemins d’accés et
coûts d’acheminement des fûts.
— z = 85(v1 + v2 + v3 + v4 ) + 12v1 + 4v2 + 4v3 + 10v4 + 7w1A + 13w1B + ... + 8w4E
Les contraintes technologiques se regroupent en deux groupes. Le pre-
mier, traduit la contrainte qu’une usine J peut être approvisionnée à

N. EL HACHEMI UM5-EMI
18 Modélisation et Programmation Linéaire

partir d’un emplacement i seulement lorsque des installations de sto-

ckage existent sur cet emplacement. Les contraintes du deuxième groupe
traduisent le fait que chaque usine est approvisionnée à partir d’un seul
emplacement.
— Contraintes du groupe 1 : wiJ ≤ vi , ∀i, ∀J
— Contraintes du groupe 2 : w1J + w2J + w3J + w4J = 1, ∀J
Les variables binaires sont souvent utilisées conjointement avec des
variables réelles non négatives pour traduire en modèles linéaires des
problèmes qui, a priori, semblent non linéaires. Nous allons voir quelques
exemples simples qui illustrent comment le recours astucieux à des va-
roables binaires permet d’agrandir considérablement le champ d’applica-
tion des modèles linéaires.

Électro

En périodes de basses eaux, ou durant l’hiver pour faire face à une

demande accrue, Électro, un fournisseur d’énergie électrique, fait appel à
des centrales thermiques alimentées au mazout et regroupées sur un em-
placement situé prés d’une grande ville où une bonne part de sa clientèle.
Dans chacune des 4 centrales thermiques d’Électro, des brûleurs génèrent
dans une chaudière la vapeur nécessaire à l’entraı̂nement du groupe tur-
boalternateur qui produit l’électricité convoyée par les lignes de transport
vers les consommateurs. Chez Électro, la vapeur produite par l’une ou
l’autre des 4 chaudières peut être acheminée sans perte conséquente vers
l’un ou l’autre des 4 groupes turboalternateurs, cette configuration a été
adoptée pour faire face aux nombreuses pannes et aux fréquents arrêts
nécessités par entretiens.
Électro a construit ces centrales au fur et à mesure que son réseau
grandissait, de sorte que certaines centrales sont plus modernes et, par-
tant, plus rentables que d’autres. Chaudières et groupes alternateurs ont
des plages d’exploitation en dehors desquelles leur fonctionnement n’est
ni économique ni sécuritaire. Le respect de ces plages assure de plus une
vie utile prolongée à l’équipement. Les Tableaux 1.8 et 1.9 présentent
les données pertinentes en relation avec les 4 chaudières et les 4 groupes

N. EL HACHEMI UM5-EMI
19 Modélisation et Programmation Linéaire

alternateurs.

Chaudière tonnage minimal tonnage maximale coût

de vapeur produite de vapeur produite par tonne
A 800 1200 9,00
B 650 900 8,50
C 425 675 7,75
D 360 600 7,25

Table 1.8 – Données associées aux chaudières

Groupe tonnage tonnage kWh par tonne coût par

minimal maximale de vapeur tonne
1 500 800 4 3,00
2 900 1300 3 3,40
3 600 900 4 3,25
4 500 800 3 4,00

Table 1.9 – Données associées aux groupes

Le problème d’aujourd’hui consiste à produire 8312 kWh en période

de pointe tout en minimisant les coûts. Combien de vapeur produira cha-
cune des chaudières ? Et de quelle façon sera répartie la vapeur entre les
groupes ? Sachant qu’il possible que certaines chaudières ou que certains
groupes soient inutilisés.
Les variables de décision sont :
— vI = 1 si la chaudière I est active et vI = 0 sinon.
— wj = 1 si le groupe j est mis à contribution et wj = 0.
— xI est la quantité de tonnes de vapeur produites par la chaudière
I.
— yj est la quantité de tonnes de vapeur utilisées par le groupe j.
Les contraintes du problème sont :

N. EL HACHEMI UM5-EMI
20 Modélisation et Programmation Linéaire

— Contrainte de produire au moins 8312 kwh : 4y1 +3y2 +4y3 +3y4 ≥ 8312
— Contrainte permettant d’assurer que la vapeur consommée par les
groupes est produite au niveau des chaudières : xA + xB + xC + xD ≥
y1 + y2 + y3 + y4
Pour chaque chaudière I, il faut forcer la variable xI , à être nulle,
soit dans l’intervalle admissible. Par exemple, pour la chaudière A,
on pose :
— Contrainte qui impose que xI = 0 ou à appartenir à l’intervalle
admissible : 800vA ≤ xA ≤ 1200vA (exemple de la chaudière A).
— Contrainte qui ompose que yj = 0 ou à appartenir à l’intervalle
admissible : 500w1 ≤ y1 ≤ 800w1 (exemple du groupe 1).
Pour plus de détails, se référer au modèle suivant :

Minz = 9xA + ... + 7, 25xD + 3y1 + ... + 4y4 (1.30)

subject to : (1.31)
4y1 + 3y2 + 4y3 + 3y4 ≥ 8312 (1.32)
xA + xB + xC + xD − y1 − y2 − y3 − y4 ≥ 0 (1.33)
800vA ≤ xA ≤ 1200vA (1.34)
650vB ≤ xB ≤ 900vB (1.35)
425vC ≤ xC ≤ 675vC (1.36)
360vD ≤ xD ≤ 600vD (1.37)
500w1 ≤ y1 ≤ 800w1 (1.38)
900w2 ≤ y2 ≤ 1300w2 (1.39)
600w3 ≤ y3 ≤ 900w3 (1.40)
500w4 ≤ y4 ≤ 800w4 (1.41)
vI , wj ∈ {0, 1} (1.42)
xI , yj ≥ 0 (1.43)

N. EL HACHEMI UM5-EMI
21 Modélisation et Programmation Linéaire

Problème de la coupe de bobines-mères

Les papetiers fabriquent des rouleaux de papier dont la largeur est

fixée par les caractéristiques des machines qu’ils utilisent. Ils les désignent
sous le vocable de bobines-mères. Par contre, leurs clients réclament des
rouleaux de divers largeurs et parfois de diverses longueurs. Comme il
est fréquent que ni la largeur ni la longueur des bobines-mères ne soient
des multiples de celles des rouleaux commandés, les papetiers encourent
souvent, pour satisfaire les commandes de leur clientèle, des pertes de
papier qu’ils désignent sous le nom de chutes. Supposons que toutes les
bobines-mères dont dispose un papetier ont une largeur de 215 cm et une
longueur de 250 m, et qu’il a accepté les commandes données au Tableau
1.10.

Largeur (en cm) Longueur (en m) Nombre de rouleaux

64 250 360
60 250 180
35 250 180

Table 1.10 – Dimensions acceptées

Comme la longueur des rouleaux commandés est identique à celle

des bobines-mères, il suffit d’assurer la coupe transversale d’un certain
nombre de bobines-mères. Quel est l’objectif poursuivi par le papetier ?
s’agit-il pour lui de satisfaire les commandes acceptées ? Si tel était le
cas, il lui suffirait de tailler tout bonnement un seul rouleau par bobine-
mère : les commandes des clients seraient évidemment satisfaites, mais
exigeraient 720 bobines-mères, ce qui constituerait un gaspillage de pa-
pier. Il faut se rendre à l’évidence : l’objectif poursuivi n’est pas unique-
ment de remplir les commandes. Si le papetier se propose d’utiliser le
moins possible de bobines-mères pour s’acquitter des commandes, com-
ment peut-il atteindre cet objectif ? Et s’il cherche plutôt à minimiser
les chutes tout en remplissant les commandes, s’agit-il du même objec-
tif, formulé différemment, ou d’un second objectif totalement distinct du

N. EL HACHEMI UM5-EMI
22 Modélisation et Programmation Linéaire

premier ? Et si ces objectifs s’avèrent distincts, lequel faut-il privilégier ?

Voilà des questions auxquelles nous nous proposons d’apporter réponses.
Déterminons tous les plans de coupe, voir le Tableau 1.11.

Largeur (en cm) Plans de coupe

1 2 3 4 5 6 7 8 9 10
64 3 2 2 1 1 1 0 0 0 0
60 0 1 0 2 1 0 3 2 1 0
35 0 0 2 0 2 4 1 2 4 6
Chutes 23 27 17 31 21 11 0 25 15 5

Table 1.11 – Plan de coupe

L’objectif du papetier est de remplir les commandes soit en minimi-

sant les chutes (pertes), soit en minimisant le nombre de bobines-mères
utilisées. Le papetier doit déterminer quels plans de coupe retenir et com-
bien de fois mettre chacun en oeuvre de façon à atteindre l’un ou l’autre
objectifs.
Énonçons tout d’abord le premier objectif visé : minimiser le nombre
de bobines-mères à découper pour satisfaire les commandes. Nous nous
préoccuperons plus loin de l’autre objectif. Comme il s’agit de déterminer
les plans de coupes à retenir et le nombre de mises en oeuvre pour chacun,
posons :
— xj est le nombre de mises en oeuvre du plan numéro j.
Dire que le plan de coupe numéro j n’est pas retenu, revient à exiger
que la variable de décision xj est nulle. Puisque chaque mise en oeuvre
d’un plan de coupe implique la découpe transversale d’une bobine-mère,
l’objectif visé consiste à minimiser la somme des mises en oeuvre des
diverses coupes. Ainsi, le modèle qui en découle est :

N. EL HACHEMI UM5-EMI
23 Modélisation et Programmation Linéaire

X
Min z = xi (1.44)
i≤10
subject to : (1.45)
3x1 + 2x2 + 2x3 + x4 + x5 + x6 ≥ 360 (1.46)
x2 + 2x4 + x5 + 3x7 + 2x8 + x9 ≥ 180 (1.47)
2x3 + 2x5 + 4x6 + x7 + 2x8 + 4x9 + 6x10 ≥ 180 (1.48)
∀i, xi est entier (1.49)

Ce modèle admet plusieurs solutions optimales. En voici 3, qui pro-

posent chacune d’utiliser 200 bobines-mères et qui, sans qu’on l’ait exigé,
occasionnent toutes la même longueur totale de chutes, soit 2860 cm.
Voir le Tableau 1.12 pour plus de détails.

Largeur (en cm) Longueur (en m) Nombre de rouleaux

Solution A Solution B Solution C
x1 = 120 x1 = 80 x1 = 110
x7 = 60 x3 = 60 x6 = 30
x10 = 20 x7 = 60 x7 = 60
z = 200 z = 200 z = 200
Chutes = 2860 cm Chutes = 2860 cm Chutes = 2860 cm

Table 1.12 – Solutions optimales

Retournons maintenant au second objectif proposé, soit la minimisa-

tion des chutes obtenues en satisfaisant les commandes. Le modèles s’écrit
comme suit :

N. EL HACHEMI UM5-EMI
24 Modélisation et Programmation Linéaire

Minw = 23x1 + 27x2 + ... + 5x10 (1.50)

subject to : (1.51)
3x1 + 2x2 + 2x3 + x4 + x5 + x6 ≥ 360 (1.52)
x2 + 2x4 + x5 + 3x7 + 2x8 + x9 ≥ 180 (1.53)
2x3 + 2x5 + 4x6 + x7 + 2x8 + 4x9 + 6x10 ≥ 180 (1.54)
∀i, xi est entier (1.55)

L’unique solution optimale de ce modèle est :

— x1 = 120
— x7 = 180
— w = 2760
Si on s’appuie sur la solution optimale du dernier modèle, le papetier
découpe plus de bobines-mères, produit davantage de rouleaux 60 cm,
mais engendre des chutes totales moins élevées que s’il applique l’une ou
l’autre des solutions optimales du premier modèle. Comment expliquer ce
paradoxe ? Tout simplement par le fait qu’aucune pénalité ne s’applique
à la production de rouleaux qui ne sont pas essentiels à l’exécution des
commandes. Le bon modèle s’écrit :

Min t = w + Exc64 + Exc60 + Exc35 (1.56)

subject to : (1.57)
3x1 + 2x2 + 2x3 + x4 + x5 + x6 ≥ 360 (1.58)
x2 + 2x4 + x5 + 3x7 + 2x8 + x9 ≥ 180 (1.59)
2x3 + 2x5 + 4x6 + x7 + 2x8 + 4x9 + 6x10 ≥ 180 (1.60)
∀i, xi est entier (1.61)

Où :
— w = 23x1 + 27x2 + ... + 5x10
— Exc64 = 64(3x1 + 2x2 + 2x3 + x4 + x5 + x6 − 360)
— Exc60 = 60(x2 + 2x4 + x5 + 3x7 + 2x8 + x9 − 180)

N. EL HACHEMI UM5-EMI
25 Modélisation et Programmation Linéaire

— Exc35 = 35(2x3 + 2x5 + 4x6 + x7 + 2x8 + 4x9 + 6x10 − 180)

La recherche opérationnelle se préoccupe surtout de la construction
et de l’étude des modèles abstraits dans le but d’optimiser un processus.
Ces modèles sont le plus souvent mathématiques, construits à l’aide du
symbolisme algébrique par lequel on traduit les relations existant entre
les objets mis en cause dans le phénomène à modéliser. Notre étude de
la modélisation se confine aux modèles mathématiques. Nous cherchons
un ensemble de relations (équations, inéquations, dépendances logiques,
etc.) qui correspondent, dans la réalité, aux lois du marché, à la dispo-
sition physique des lieux, aux contraintes de marketing, au respect des
disponibilités en ressources ou en main-d’oeuvre, etc.

N. EL HACHEMI UM5-EMI
Chapitre 2

Résolution graphique de modèles

linéaires continus comportant
deux variables de décision

2.1 Introduction
La représentation graphique de modèles linéaires continus comportant
deux variables de décison permet de développer l’intuition de la résolution
et facilite l’acquisition des définitions et des concepts nécessaires à l’abord
de modèles linéaires réalistes. C’est également par l’étude de ces modèles
linéaires simples qu’il apprendra à repérer ceux qui admettent une ou
plusieurs solutions optimales et à détrminer les caractéristiques de ces
solutions optimales.

2.2 Un premier exemple : La fonderie rivière-bleue

2.2.1 Description du problème
La fonderie en pleine planification des opérations a enregistré la se-
maine prochaine les commandes suivantes : 34 tonnes de tuyauterie et
14 tonnes de gueuses. La semaine prochaine, la main-d’oeuvre disponible
sera de 200 heures dans l’atelier d’ébarbage et de 60 heures dans l’atelier

26
27 Modélisation et Programmation Linéaire

de peinture. Il faut compter 10 heures la tonne pour l’ébarbage de tuyau-

terie et 5 heures la tonne pour celui de gueuses. Á l’atelier de peinture,
on requiert 2 heures la tonne pour la tuyauterie et 3 heures la tonne
pour les gueuses. La contribution aux coûts d’exploitation et au profit
d’une tonne de tuyauterie est de 1000 $. La tonne de gueuses apporte
une contribution de 1200$.

2.2.2 Le modèle linéaire

M ax z = 1000x1 + 1200x2
subject to :
10x1 + 5x2 ≤ 200 (2.1)
2x1 + 3x2 ≤ 60 (2.2)
x1 ≤ 34 (2.3)
x2 ≤ 14 (2.4)
x1 , x2 ≥ 0 (2.5)

Où :
— x1 est le nombre de tonnes de tuyauterie traitées.
— x2 est le nombre de tonnes de gueuses traitées.
À chaque couple de valeurs des variables de décision x1 et x2 ) on associe
un point (x1 ; x2 ) du plan cartésien : le point (x1 ; x2 ) s’interprète comme
la proposition d’un plan de production. On peut parler du point (x1 ; x2 )
comme s’il s’agissait du plan de production (x1 ; x2 ) ou encore de la solution
(x1 ; x2 ), Bien que l’idéal soit de réserver le terme point à la représentation
géométrique, le terme solution à l’approche algébrique et le terme plan
de production à l’interprétation du modèle dans la réalité.
Un point, solution ou plan de production (x1 ; x2 )) est dit admissible
s’il satisfait à chacune des contraintes du modèle linéaire. Dans le cas
contraire, le point, solution ou plan de production est dit inadmissible.
Par exemple, le point (14 ; 5) est admissible selon le modèle proposé

N. EL HACHEMI UM5-EMI
28 Modélisation et Programmation Linéaire

pour la Fonderie. Mais le point (24 ; 2) n’est pas admissible. Trouver

graphiquement une solution optimale d’un modèle linéaire continu à 2
variables de décision suppose qu’on puisse :
— Construire le graphique de la région admissible, c’est à dire l’en-
semble des solutions admissibles ;
— Repérer sur ce graphique une solution optimale.
Nous cherchons, en un premier temps, à nous doter d’une représentation
graphique de l’ensemble des solutions admissibles. Notons d’abord que
les contraintes de non-négativité fixent 0 comme borne inférieure des va-
riables de décision x1 et x2 . Elles ont pour effet de cantonner au premier
quadrant la recherche des points admissibles. Ces contraintes accom-
pagnent la plupart des modèles linéaires, et ce sont habituellement les
premières que l’on prend en considération lors du tracé d’un graphique
des solutions admissibles. Notons également que toutes les contraintes
du modèle précédent, y inclus les contraintes de non-négativité, peuvent
s’écrire sous la forme suivante :
— ax1 + bx2 ≤ c
Pour préciser l’approche qui mène à la représentation graphique des
points vérifiant ce type de contrainte, choisissons tout d’abord la première
contrainte du modèle de la fonderie. Et considérons la droite (L) 10x1 +
5x2 = 200 que l’on appelle droite associée à ladite contrainte. La représentation
graphique de cette droite s’obtient en repérant 2 points qui vérifient
l’équation 10x1 + 5x2 = 200, puis en traçant la droite qui passe par ces
points.
Tout point situé sous la droite (L) appartient à une droite parallèle à
(L), dont l’équation est de la forme : 10x1 + 5x2 = d où d < 200. Au fur et
à mesure que croit la valeur de d, les droites occupent des positions de
plus en plus élevées tout en demeurant parallèles à la droite (L), comme
le montre la Figure 2.1.
Les points qui vérifient la première contrainte du modèle appartiennent
soit à la droite associée (L) (on dit alors que la contrainte est satisfaite
comme équation), soit à l’ensemble des points situés sous la droite (L) (on
dit que la contrainte est satisfaite comme inéquation). La région associée

N. EL HACHEMI UM5-EMI
29 Modélisation et Programmation Linéaire

Figure 2.1 – Courbe de niveau de la première contrainte

est représente sur la Figure 2.2.

Puisque toutes les contraintes du modèle linéaire sont de la même
forme, il suffit de les prendre en considération tour à tour, en répétant
pour chacune les même opérations que celles effectuées pour la contrainte
précédente. Il s’agit, pour chaque contrainte :
— De déterminer 2 points de la droite associée, puis de tracer cette
droite ;
— De déterminer de quel côté de la droite associée se trouvent les
points pour lesquels la contrainte est satisfaite comme inéquation ;
— De tracer une flèche pointant vers ce côté.
Illustrons à nouveau ce procédé à l’aide de la contrainte 2x1 + 3x2 ≤ 60
associée au deuxième atelier :

N. EL HACHEMI UM5-EMI
30 Modélisation et Programmation Linéaire

Figure 2.2 – Prise en considération de la première contrainte

— les points (30 ; 0) et (0 ; 20) appartiennent à la droite associèe à la

contrainte 2x1 + 3x2 ≤ 60 ;
— l’origine O = (0 ; 0) vérifie cette dernière ; les points admissibles
selon la seule contrainte 2x1 + 3x2 ≤ 60 se trouvent sous la droite
tracée ;
— la flèche est donc placée sous la droite. La Figure 2.3 représente
graphiquement la région admissible relative aux deux premières
contraintes du modèle
La prise en considération de toutes les contraintes du modèle linéaire
de la fonderie permet d’établir l’ensemble des solutions, cet ensemble est
illustré à la Figure 2.4 et représente la région admissible associée à notre
modèle.
En résumé, le repérage graphique de l’ensemble des solutions admis-

N. EL HACHEMI UM5-EMI
31 Modélisation et Programmation Linéaire

Figure 2.3 – Prise en considération des 2 premières contraintes

sibles d’un modèle linéaire comportant 2 variables de décision se fait par

la prise en considération successive des contraintes. L’ensemble des points
non éliminés lorsque ce processus prend fin constitue la région admissible,
c’est-à-dire l’ensemble des points qui vérifient toutes les contraintes du
modèle linéaire.
La construction de la région admissible est un premier pas vers l’obten-
tion d’une solution optimale et permet souvent de faire des remarques
pertinentes à propos du problème posé.
Nous venons de construire la région admissible du modèle linéaire
associé au problème de la Fonderie. Cet ensemble contient un nombre in-
fini des points. Nous indiquons maintenant comment repérer une solution
optimale, c’est-à-dire un point (x∗1 ; x∗2 ) vérifiant toutes les contraintes et

N. EL HACHEMI UM5-EMI
32 Modélisation et Programmation Linéaire

Figure 2.4 – Région admissible

permettant à 1000x∗1 + 1200x∗2 de prendre sa meilleure valeur dans ces cir-

constances. En fixant z à une valeur p choisie arbitrairement, on obtient
la droite
— 1000x∗1 + 1200x∗2 = p
Cette droite est appelée courbe de niveau ou encore courbe d’indifférence
de la fonction z. Elle représente les points du plan qui donnent à z la valeur
p. Voir la Figure 2.5 pour plus de détails.
Tracer une première courbe de niveau permet d’obtenir une illustra-
tion de la pente de z qui dépend du rapport des coefficient 1000 et 1200
de x1 et x2 . En tracer une deuxième permet de déterminer la direction
selon laquelle la valeur de z augmente. Ainsi, en augmentant petit à petit
la valeur de p, on obtient des droites parallèles, chacune plus à droite et
plus haute que les précédentes.
Comme on cherche ici à maximiser la fonction-objectif z, on détermine

N. EL HACHEMI UM5-EMI
33 Modélisation et Programmation Linéaire

Figure 2.5 – Courbes de niveau de la fonction-objectif

une solution optimale en cherchant la courbe de niveau la plus élevée qui

comporte au moins un point de l’ensemble des points admissibles. Cette
recherche donne le résultat illustré à la Figure 2.6.
Il n’y a ici qu’une solution optimale : elle se trouve à l’intersection des
droites associées aux deux premières contraintes associées aux deux ate-
liers. Par conséquent, ce point (x∗1 ; x∗2 ) vérifie les équations de ces droites :
— 10x∗1 + 5x∗2 = 200
— 2x∗1 + 3x∗2 = 60
— Il s’ensuit que x∗1 = 15 et x∗2 = 10
— En ce point, la fonction objectif z prend la valeur 27000
— p∗ = 1000 ∗ 15 + 1200 ∗ 12 = 27000

N. EL HACHEMI UM5-EMI
34 Modélisation et Programmation Linéaire

Figure 2.6 – Repérage graphique de la solution optimale

2.3 La résoluion d’un deuxième exemple

Ce second exemple diffère du premier sous 2 aspects : l’objectif pro-
pose la minimisation d’une fonction linéaire ; certaines contraintes tech-
nologiques sont de signe ≥ et l’origine O = (0, 0) du plan n’est pas une
solution admissible.

M in z = 3x1 + 4x2
subject to :
x1 + x2 ≥ 9 (2.6)
x1 − x2 ≤ 9 (2.7)
x1 + 3x2 ≥ 17 (2.8)
x1 ≥ 3 (2.9)
x2 ≤ 10 (2.10)
x1 , x2 ≥ 0 (2.11)

En premier temps, nous construisons la région admissible. Les contraintes

de non-négativité garantissent que les solutions admissibles appartiennent
toutes au premier quadrant. L’analyse graphique peut donc se limiter à
cette portion du plan. La Figure 2.7 illustre la région admissible associée
aux différentes contraintes technologiques.

N. EL HACHEMI UM5-EMI
35 Modélisation et Programmation Linéaire

Figure 2.7 – Construction de la région admissible

Le polygone ABCDE, qui constitue la région admissible, est reproduit

à la figure suivante, accompagné des courbes de niveau z = 56 et z = 31.
Comme l’objectif est de minimiser la fonction z, l’optimum s’atteint en
cherchant la courbe de niveau la plus à gauche et la plus basse possible
qui a un point commun avec la région admissible. Le graphique indique
que le sommet E = (5; 4) comme celui où s’obtient la solution optimale
recherchée (Voir la Figure 2.8).

2.4 Les caractéristiques de l’ensemble des solu-

tions admissibles
Nous indiquons comment caractériser l’ensemble des solutions admis-
sibles de modèles linéaires continus dont les contraintes adoptent la forme
générale :

N. EL HACHEMI UM5-EMI
36 Modélisation et Programmation Linéaire

Figure 2.8 – Repérage graphique de la solution optimale

 
X ≤
∀i = 1, .., m, aij xj  =  bi (α) (2.12)
 

≥
∀j = 1, ...n, xj ≥ 0 (β) (2.13)

Les m contraintes technologiques et les n contraintes de non-négativité

font intervenir n variables de décision x1 ,..., xn . Les coefficients aij et bi
sont des nombres réels.

N. EL HACHEMI UM5-EMI
37 Modélisation et Programmation Linéaire

2.5 Une typologie des régions admissibles

L’ensemble des solutions admissibles, lorsqu’il n’est pas vide. détermine
un polyèdre convexe. Nous définissons ci-dessous ces 2 termes. Mais au-
paravant, considérons la première contrainte du modèle de la Fonderie :
— 10x1 + 5x2 ≤ 200
La droite associée, d’équation 10x1 + 5x2 = 200, divise le plan en 2 parties
que l’on dénomme demi-plans ou, plus généralement, demi-espaces.
Un demi-espace est dit fermé ou ouvert selon que sa frontière fait
partie ou non. Par exemple, les demi-espaces V et W de la Figure 2.9 sont
fermés. Par contre, le demi-espace défini par 10x1 + 5x2 < 200 est ouvert,
puisque les points de la droite-frontière 10x1 + 5x2 = 200 ne vérifient pas
cette inéquation stricte.

Figure 2.9 – Demi-espaces associés à une inéquation

À chacune des contraintes (α) et (β) de signe ≤ ou ≥ correspond un

N. EL HACHEMI UM5-EMI
38 Modélisation et Programmation Linéaire

demi-espace fermé constitué de l’ensemble des points qui la vérifient.

Une contrainte (α) de signe = peut être remplacée par la conjonction
de deux inéquatins, l’une de signe ≤ et l’autre de ≥ ; l’ensemble des
points qui satisfont à cette équation est donc l’intersection de deux demi-
espaces fermés. Un point (x1 ; x2 ) vérifiant toutes les contraintes (α) et
(β) appartient donc à l’intersection d’un certain nombre de demi-espaces
fermés. Une telle intersection d’un nombre fini de demi-espaces fermés
est appelée polyèdre.
Un ensemble V est dit convexe si tout segment de droite dont les
extrémités appartiennent à V est inclus dans V. Dans la Figure 2.10, V
est convexe alors que W ne l’est pas.

Figure 2.10 – Définition graphique de la convexité

2.6 Régions admissibles pour modèle linéaire

L’ensemble des solutions admissibles d’un modèle linéaire continu consti-
tue toujours un ensemble convexe. La Figure 2.11 reproduit la région
admissible du modèle de la Fonderie.

2.7 Convexité
La convexité est à la fois une propriété importante de la région admis-
sible de tout modèle linéaire continu et un concept utile pour en trouver
une solution optimale. Imaginons qu’on n’ait pas encore tracé la région
admissible du modèle de la Fonderie, mais que l’on connaisse 2 plans de

N. EL HACHEMI UM5-EMI
39 Modélisation et Programmation Linéaire

Figure 2.11 – Convexité de la région admissible

production Q et Q0 , qui correspondent aux points admissibles Q = (7; 12)

et Q0 = (13; 8). Chaque point du segment reliant Q et Q0 peut s’écrire
comme suit :
— (7 + 6β; 12 − 4β) où β ∈ [0, 1]
On tire facilement la conclusion suivante : si l’ensemble des solutions
admissibles d’un modèle linéaire continu contient 2 points distincts, il en
contient une infinité !

2.8 Régions admissibles non bornée

Considérons un modèle linéaire continu dont les contraintes s’écrivent
sous la forme (α) et (β). La région admissible d’un modèle est dite non-
bornée si au moins une des variables de décision peut y prendre des
valeurs de plus en plus grandes sans violer aucune des contraintes tech-
nologiques. Dans le cas contraire, on dit que la région admissible est
bornée (Voir la Figure 2.12). Il existe alors des constantes sj , de manière
à ce que :
— xj ≤ sj j = 1, ..., n

N. EL HACHEMI UM5-EMI
40 Modélisation et Programmation Linéaire

Figure 2.12 – Exemple de région admissible non bornée

2.9 Une typologie des solutions admissibles

Supposons non vide l’ensemble des solutions admissibles qui vérifient
les contraintes (α) et (β). Et intéressons-nous aux points qui en font partie
plutôt qu’à l’ensemble lui-même.
L’ensemble des solutions admissibles du modèle linéaire de la Fonderie
comprend 3 types de points : intérieurs, frontières et extrêmes (Voir la
Figure 2.13).
— Les points intérieurs, tel E = (4; 4) ne satisfont comme équation
aucune des contraintes du modèle.
— Les points frontières satisfont comme équation au moins 1 des
contraintes du modèle linéaire. Le point F = (16 ; 8) en fait partie.
— Les points extrêmes sont O, A, B, C et D. Chaque point extrême
de ce modèle se trouve à l’intersection des droites associées à 2
contraintes.
Les points extrêmes sont des éléments clés de la programmation linéaire.

N. EL HACHEMI UM5-EMI
41 Modélisation et Programmation Linéaire

Figure 2.13 – Types de points

Dans le modèle de la Fonderie,tout plan de production admissible s’ex-

prime comme une somme pondérée des 5 plans de production correspon-
dant aux points extrêmes, excutés chacun dans une certaine proportion,
la somme de ces proportions étant égale à 1. Ainsi, les plans de production
E et F s’écrivent comme suit :
— E = (4; 4) = 72 A + 15 D + 18
35
O
— F = (16; 8) = 45 C + 15 D

2.10 Les caractérisriques des solutions optimales

Nous nous proposons de justifier intuitivement un résultat appelé
théorème fondamental de la programmation linéaire. Soit la fonction-
objectif suivante soumise aux contraintes (α) et (β) :
— M ax z = nj=1 cj xj
P

— Le théorème fondamental de la programmation linéaire s’énonce

comme suit : Si un modèle linéaire continu admet au moins une
solution optimale, l’une d’entre elles correspond à un point extrême

N. EL HACHEMI UM5-EMI
42 Modélisation et Programmation Linéaire

2.11 Les caractérisriques des solutions optimales

La Figure 2.14 illustre la région admissible et la courbe de niveau
z = 12000 du modèle linéaire proposé pour résoudre le problème de la
Fonderie. Les courbes de niveau correspondant à des valeurs supérieures
de z sont des droites parallèles à celle qui est tracé. Celle qui correspond
à la plus grande valeur que puisse prendre z dans l’ensemble des points
admissibles passe par le point C : ainsi, C est une solution optimale. Et,
conformément au théorème précédent, C est un point extrême.

Figure 2.14 – Région admissible et courbe de niveau de z

N. EL HACHEMI UM5-EMI
Chapitre 3

L’algorithme du simplexe

3.1 Introduction
L’algorithme du simplexe est la méthode la plus utilisée de la re-
cherche opérationnelle. C’est G.B. Dantzig qui, dans un article paru en
1949, a décrit cet algorithme, qui constitue l’épine dorsale de la recherche
opérationnelle. Depuis, cet algorithme a fait l’objet de centaines d’articles
scientifiques et a servi à la résolution de nombreux modèles linéaires rela-
tifs à des problèmes de gestion, de diétique, de transport, d’affectation...
L’objectif de ce chapitre est double :
— Présenter les concepts qui sous-tendent l’algorithme du simplexe ;
— Décrire, à l’aide d’exemples numériques simples, comment résoudre
un modèle linéaire par l’algorithme du simplexe.

3.2 Les variables d’écart et les variables d’excédent

L’algorithme du simplexe permet d’optimiser les modèles linéaires
continus dont les variables sont non-négatives et dont les contraintes sont
écrites sous formes d’équations. Beaucoup de problèmes pratiques, tou-
tefois, se modélisent de telle façon que plusieurs contraintes s’écrivent
sous forme d’inéquations. Afin de pouvoir utiliser l’algorithme du sim-
plexe pour résoudre ces problèmes, nous indiquons comment transformer
un modèle comportant des contraintes des signes ≤ ou ≥ en un modèle

43
44 Modélisation et Programmation Linéaire

équivalent dont toutes les contraintes, sauf celles de non-négativité, sont

de signe =.
Retournons au modèle de la Fonderie. Rappelons qu’une contrainte
du modèle s’écrit comme :
— 10x1 + 5x2 ≤ 200
Et introduisons une nouvelle variables e1 définie ainsi :
— e1 = 200 − (10x1 + 5x2 )
La variable e1 est qualifiée de variable d’écart. Elle représente dans ce cas
le temps inutilisé à l’atelier lorsqu’on retient le plan de production (x1 ; x2 ).
La contrainte 10x1 + 5x2 ≤ 200 est équivalente à la formule suivante :
— e1 = 200 − (10x1 + 5x2 ) et e1 ≥ 0
En programmation linéaire, l’écriture des contraintes respecte généralement
la covention suivante : les termes impliquent une variable sont tous placés
à gauche du symbole relationnel (=, ≤, ≥) ; le terme constant est isolé à
droite et est non négatif. Ainsi, l’équation ou la contrainte s’écrit le plus
souvent sous la forme
— (10x1 + 5x2 ) + e1 = 200
Les variables d’excédent servent à transformer en équations les contraintes
de signe ≥. Supposons qu’une entente entre la direction de la Fonderie et
les employés stipule que l’atelier fonctionnera au moins 150 heures par
semaine. Un plan de production (x1 ; x2 ), pour être admissible, doit alors
satisfaire l’inéquation
— 10x1 + 5x2 ≥ 150
Introduisons une nouvelle variable e5 , dit variable d’excédent, qui est
définie comme suit :
— e5 = 10x1 + 5x2 − 150
Il est facile de vérifier que (x1 ; x2 ) satisfait la contrainte 10x1 + 5x2 ≥ 150
si et seulement si e5 ≥ 0. En résumé, l’inéquation 10x1 + 5x2 ≥ 150 est
équivalente à e5 = 10x1 + 5x2 − 150 et e5 ≥ 0.

N. EL HACHEMI UM5-EMI
45 Modélisation et Programmation Linéaire

3.3 Les Solutions de Base Admissibles

Le théorème fondamental de la programmation linéaire souligne l’im-
portance des points extrêmes dans la recherche d’une solution optimale
d’un modèle continu. Dans un plan cartésien, ces points sont faciles à
repérer ; mais dès que le nombre de variables de décision est supérieur à
3, il devient impossible de le déterminer graphiquement. Or, la plupart
des modèles linéaires rencontrés dans la pratique mettent en jeu un grand
nombre de variables. Il faut donc traduire en langage algébrique la notion
géométrique de point extrême.

3.4 Modèle linéaire sous forme (PLS)

Un modèle linéaire sous forme (PLS) est un modèle linéaire continu
qui se présente sous la forme suivante :

M ax z = c1 x1 + c2 x2 + ... + cn xn (3.1)
subject to : (3.2)
ai1 x1 + ai2 x2 + ... + ain xn ≤ bi , ∀ i (3.3)
x1 , x2 , x3 , ..., xn ≥ 0 (3.4)

où les constantes bi sont non négatives. La solution xj = 0 (0 ≤ j ≤ n), qui

correspond à l’origine O, est une solution admissible de de tout modèle
(PLS).
Le modèle (PLS) comporte n variables de décision et (m+n) contraintes.
Les n dernières sont des contraintes de non-négativité. Les m premières,
dont le membre de droit est noté bi sont qualifiées de contraintes techno-
logiques.
Le modèle (PLS) est équivalent au modèle (PLS=) obtenu en ajoutant
une variable d’écart à chaque contrainte technologique, selon le procédé
décrit auparavant.
La Figure 3.1 représente les droites associées à chacune des contraintes

N. EL HACHEMI UM5-EMI
46 Modélisation et Programmation Linéaire

technologiques du problème de la Fonderie, ainsi que la région admissible

OABCD.

Figure 3.1 – Contraintes du problème de la Fonderie et prolongement des droites

3.5 La caractéristique algébrique des points extrêmes

Revenons au modèle de la Fonderie, on peut l’écrire sous la forme d’un
PLS= comme suit :

M ax z = 1000x1 + 1200x2 (3.5)

subject to : (3.6)
10x1 + 5x2 + e1 = 200 (3.7)
2x1 + 3x2 + e2 = 60 (3.8)
x1 + e3 = 34 (3.9)
x2 + e4 = 14 (3.10)
x1 , x2 , e1 , e2 , e3 , e4 ≥ 0 (3.11)

N. EL HACHEMI UM5-EMI
47 Modélisation et Programmation Linéaire

Ignorons pour l’instant les contraintes de non-négativité. Le système

des 4 contraintes technologiques met en jeu 6 variables. Un tel système,
dont le nombre de variables est supérieur au nombre d’équations admet
une infinité de solutions ou bien n’en admet aucune. Si dans ce modèle on
donne à 2 des 6 variables la valeur 0, le système résultant qui comportera
4 équations et 4 variables admet une solution ou bien n’en admet aucune.
Or, il existe 6*5/2 = 15 façons de choisir 2 variables parmi les 6 du modèle
(Plus de détails dans la Figure/Tableau 3.2).

Figure 3.2 – Intersections des droites associées aux contraintes/points extrêmes

3.6 Les solutions de base

Considérons un modèle (PLS) quelconque ; et notons n0 = m + n le
nombre total de variables apparaissant dans (PLS=).
Soit (x1 ; ...; xn ; e1 ; ...; em ) une solution vérifiant les m contraintes technolo-
giques de (P LS =). On dira qu’il s’agit d’une solution de base de (PLS=)
si au moins (n’-m) de ses coordonnées sont égales à 0. Par exemple, les
solutions de base du modèle de la Fonderie correspondent aux points O,

N. EL HACHEMI UM5-EMI
48 Modélisation et Programmation Linéaire

A, B,..., L du tableau précédent.

Une solution de base dont toutes les coordonnées sont non négatives est
dite solution de base admissible.

Théorème 3.1 Si (x1 , ..., xn ; e1 ; ...; em ) est une solution de base admissible
de (PLS=), alors (x1 , ..., xn ) est un point extrême de (PLS). De plus,
tout point extrême de (PLS) s’obtient de cette façon d’une solution de
base de (PLS=).

Cette caractéristique algébrique des points extrêmes permet de tra-

duire en langage algébrique les résultats du chapitre précédent, dont le
théorème fondamental de la programmation linéaire.

Théorème 3.2 Si (PLS=) admet une solution optimale, il existe une

solution de base admissible qui est solution optimale de (PLS=).

La recherche d’une solution optimale de (PLS) pourra, en vertu du

théorème 2, se confiner à l’examen des solutions de base admissibles de
n
(PLS=), dont le nombre ne peut exécer Cm+n . Malheureusement, la va-
n
leur Cm+n est souvent énorme dans la pratique. L’algorithme du simplexe
permet de déterminer si un modèle (PLS) admet une solution optimale
et, le cas échéant, d’en trouver une, en examinant un nombre de solutions
de base qui, sauf exceptions, est relativement petit.

3.7 La résolution des modèles sous forme (PLS)

L’algorithme du simplexe choisit d’abord un sommet initial, puis effec-
tue une opération itérative, dite pivotage, qui habituellement correspond
à passer d’un sommet à un sommet adjacent plus ”rentable”. En un pre-
mier temps, nous nous limitons aux modèles de la forme (PLS) dont la
structure spéciale fournit le point de départ évident qu’est l’origine O =
(0 ;... ;0).
Nous décrirons le fonctionnement de l’algorithme du simplexe en l’ap-
pliquant au modèle de la Fonderie (Voir le modèle ci-après).

N. EL HACHEMI UM5-EMI
49 Modélisation et Programmation Linéaire

M ax z = 1000x1 + 1200x2 (3.12)

subject to : (3.13)
10x1 + 5x2 + e1 = 200 (3.14)
2x1 + 3x2 + e2 = 60 (3.15)
x1 + e3 = 34 (3.16)
x2 + e4 = 14 (3.17)
x1 , x2 , e1 , e2 , e3 , e4 ≥ 0 (3.18)

Comme on l’a vu précédemment, les points extrêmes correspondent

aux solutions de base admissible de (FRB=). Celles-ci sont obtenues en
annulant 2 des 6 variables x1 , x2 , e1 , e2 , e3 et e4 . Par exemple, poser x1 =
x2 = 0 conduit à un système d’équations trivial à résoudre, notamment :
— e1 = 200
— e2 = 60
— e3 = 34
— e4 = 14
La solution (x1 ; x2 ; e1 ; e2 ; e3 ; e4 ) = (0; 0; 200; 60; 34; 14) satisfait aux 4 contraintes
technologiques du modèle de la Fonderie et, puisque toutes les variables
sont non-négatives, cette solution constitue une solution de base admis-
sible. Graphiquement, cette solution correspond au sommet O (l’ori-
gine). Toute autre paire de variables posées égales à 0 conduit à un
système d’équations qui est plus difficile à résoudre que le système asocié
à x1 = x2 = 0. À titre d’exemple, si on posait e2 = e3 = 0, il viendrait
— 10x1 + 5x2 + e1 = 200
— 2x1 + 3x2 = 60
— x1 = 34
— x2 + e4 = 14
En général, la solution de base admissible initiale de (PLS=) s’obtient
en posant x1 = x2 = ... = xn = 0. Le système d’équations qui en résulte se
résout immédiatement puisqu’il s’écrit
— ei = bi , ∀i = 1, ..., m

N. EL HACHEMI UM5-EMI
50 Modélisation et Programmation Linéaire

On voit ici la nécessité de supposer que les membres droits bi de (PLS=)

sont non négatifs : cette hypothèse garantit que, lorsque les variables
originales (les xj ) sont posées égales à 0, les ei sont non négatives et
la solution (x1 ; ...; xn ; e1 ; ...; em ) est admissible. La Figure 3.3 présente un
organigramme de l’algorithme du simplexe, cas d’un PLS.

Figure 3.3 – Organigramme de l’algorithme du simplexe dans le cas (PLS)

N. EL HACHEMI UM5-EMI
51 Modélisation et Programmation Linéaire

3.7.1 La construction du tableau initial

On sait, à partir de l’analyse géométrique, que le sommet O n’est pas
solution optimale de (FRB). Il faut donc modifier cette solution initiale de
façon à augmenter la valeur prise par la fonction objectif z. L’algorithme
du simplexe procède par itérations, chacune correspondant au passage
d’un sommet de la région admissible à un sommet adjacent de cette
région.
L’exemple de la Fonderie exigera 3 itérations : on passera successivement
de O à A, puis de A à B, et enfin de B à C où l’on s’arrêtera, puisque C
est l’optimum.
Les calculs nécessités par l’algorithme du simplexe s’effectuent plus
facilement et plus rapidement lorsque le modèle linéaire est disposé sous
forme de tableau simplexe. Un tel tableau présente, de façon visuelle et
structurée, les variables et les coefficients du modèle. De plus, chaque
tableau met en évidence une solution de base particulière du modèle
linéaire, dite solution de base associée, ou encore solution canonique as-
sociée. La Figure 3.4 présente le tableau initial du simplexe associé au
problème de la Fonderie.

Figure 3.4 – Modèle (FRB) : tableau initial

Chaque tableau du simplexe partitionne les variables en 2 groupes : les

variables de base et les variables hors base. Dans un tableau de (FRB=),

N. EL HACHEMI UM5-EMI
52 Modélisation et Programmation Linéaire

les variables de base sont les 4 variables apparaissant dans la section

gauche, et les variables hors base sont les 2 autres. Par exemple, les
variables hors base du tableau précédent sont x1 et x2 . De façon générale,
la solution de base associée à un tableau de (FRB=) s’obtient en posant
égales à 0 les deux variables hors base et donnant à chacune des variables
de base la valeur apparaissant sur la même ligne.
Un tableau du simplexe contient une foule d’informations : il faut y
voir plus qu’un simple alignement de nombres, car on y retrouve l’essen-
tiel des données reliées au problème de la Fonderie. Par contre, un tableau
ne réfère nulle part à la non-négativité des variables : comme celles-ci
doivent toutes être non négatives, il n’est pas nécessaire d’en faire men-
tion explicitement. Cependant, l’algorithme du simplexe en tient compte
lors du test d’optimilité et lors de l’étape C.

3.7.2 Le choix de la variable entrante

La solution de base initiale du modèle FRB n’est pas optimale. Com-
ment s’en convaincre par des arguments strictement algébriques ? S’il
n’est pas optimale, il faut augmenter la valeur de l’une ou l’autre de ces
variables x1 ; x2 . Laquelle, ou lesquelles choisir ? Laissons-nous guider par
l’intuition : on augmentera la variable qui rapporte le plus x2 . Et afin de
simplifier l’analyse, supposons que x1 garde pour le moment la valeur 0.
Le modèle devient :

M ax z = 1200x2 (3.19)
subject to : (3.20)
5x2 + e1 = 200 (3.21)
3x2 + e2 = 60 (3.22)
e3 = 34 (3.23)
x2 + e4 = 14 (3.24)
x2 , e1 , e2 , e3 , e4 ≥ 0 (3.25)

Pour vérifier que la solution initiale n’était pas optimale, il a donc suffi

N. EL HACHEMI UM5-EMI
53 Modélisation et Programmation Linéaire

de mettre en parallèle les 2 observations suivantes :

— La dernière ligne, qui correspond à l’équation z = 1000x1 + 1200x2 + 0
contient au moins un coefficient positif, par exemple celui de la
colonne x2 ;
— La variable hors base x2 peut être augmentée pour donner une
solution admissible (par exemple en posant x2 = 1).

3.7.3 Arrêt du simplexe

En générale, les nombres de la ligne cj −zj permettent de déterminer si
l’algorithme du simplexe s’arrêtera avec le tableau courant ou s’il conti-
nuera : lorsque au moins l’un des coûts marginaux cj − zj est positif et
que l’objectif consiste à maximiser z, le tableau courant est considéré non
optimal et un autre tableau sera construit par pivotage (étape D). Nous
conviendrons, dans un problème de maximisation, c’est la variable hors
base dont le coefficient cj − zj est le plus grand qui sera choisie.

3.7.4 Le choix de la variable sortante

C’est décidé : la variable x2 entrera dans la base et x1 restera nulle.
Puisque z augmente lorsque x2 augmente, il est naturel de chercher une
solution de base où x2 prend la plus grande valeur positive permise. Mais
jusqu’où peut augmenter la valeur de x2 ? Puisque les variables de base
du tableau initial doivent être non négatives il résulte que :
— e1 = 200 − 5x2 ≥ 0 d’où x2 ≤ 40
— e2 = 60 − 3x2 ≥ 0 d’où x2 ≤ 20
— e3 = 34 − 0x2 ≥ 0 ici x2 n’est pas limitée
— e4 = 14 − 1x2 ≥ 0 d’où x2 ≤ 14
La variable x2 ne peut dépasser la plus petite de ces bornes supérieures ;
et comme il est rentable d’augmenter la valeur x2 le plus possible, il est
naturel de poser : x2 = 14. La variable de base e4 prendra alors la valeur
0 et sera dite variable sortante. Noter que la variable sortante e4 est la
variable de base correspondant à la plus petite limite.
Il résulte que (x1 ; x2 ; e1 ; e2 ; e3 ; e4 ) = (0; 14; 130; 18; 34; 0).

N. EL HACHEMI UM5-EMI
54 Modélisation et Programmation Linéaire

3.7.5 Tableau du simplexe sous forme canonique

Le tableau présenté avant a en effet 3 caractéristiques qui ont facilité
le passage de la solution initiale à la solution actuelle :
— à chacune des lignes de la section centrale est associée une variable
de base dont le coefficient est 1 dans cette ligne et 0 dans les autres
lignes de la section centrale ;
— les coefficients des variables de base sont nuls dans la ligne cj − zj ;
— toutes les valeurs de la section droite sont non négatives.
On dit d’un tableau de simplexe, possédant ces 3 caractéristiques qu’il
est sous forme canonique.

3.7.6 Choix de la variable sortante et pivotage jusqu’à la

convergence
Avant de tester l’optimalité de la solution 1 (x1 ; x2 ; e1 ; e2 ; e3 ; e4 ) = (0; 14; 130; 18; 34; 0),
il faut construire son tableau canonique associé. Dans ce nouveau tableau,
la variable sortante e4 sera nulle et hors base, tandis que la variable en-
trante x2 sera positive et fera partie de la base. En fait, x2 prendra la place
de e4 et sera variable de base associée à la 4e ligne. Le Tableau/Figure 3.5
représentera la solution 1.
On remarque que, pour une variable de base, le coefficient cj − zj est
nul et que sa colonne comporte, dans la section centrale, des 0 sur toutes
les lignes sauf celle où elle est inscrite comme variable de base et où son
coefficient est 1.
Les calculs à effectuer font intervenir comme nombre clé l’élément du
tableau initial situé à l’intersection de la 4e ligne, où se trouve la variable
sortante et de la colonne x2 de la variable entrante. On dit que cet élément
est le pivot du passage de deux tableaux de simplexe successifs. Les calculs
se regroupent en 3 opérations.
— La première opération vise à inscrire le nombre 1 à la position du
pivot.
— La deuxième opération consiste à modifier les autres lignes de la
section centrale de façon à pouvoir inscrire le nombre 0 dans la

N. EL HACHEMI UM5-EMI
55 Modélisation et Programmation Linéaire

Figure 3.5 – Tableau de la solution 1

colonne du pivot, tout en laissant inchangé l’ensemble des solutions

admissibles.
— La troisième opération est analogue à la deuxième, mais elle concerne
la ligne cj − zj , z est exprimée en fonction des variables hors base.
— x2 = 14 − e4
— 10x1 + 5(14 − e4 ) + e1 = 200
— 2x1 + 3(14 − e4 ) + e2 = 60
— z = 1000x1 + 1200(14 − e4 )
— x2 + e4 = 14
— 10x1 + e1 − 5e4 = 130
— 2x1 + e2 − 3e4 = 18
Le Tableau/Figure 3.6 illustre le résultat obtenu après une itération.
La solution (0; 14; 130; 18; 34; 0), dite solution de base associée, s’obtient
en déclarant nulles a priori les variables hors base x1 et e4 puis en posant
chaque variable de base églale à la valeur apparaisant à droite, sur la
ligne. Cette solution correspond au sommet A de la région admissible.
La solution de base précédente n’est pas optimale puisque puisque l’un
des coefficients cj −zj est positif. En effet, la ligne cj −zj du tableau associé
résume l’équation M ax z = 1000x1 − 1200e4 + 16800.

N. EL HACHEMI UM5-EMI
56 Modélisation et Programmation Linéaire

Figure 3.6 – Tableau canonique de la solution 1

Il résulte immédiatement de cette équation que z augmente lorsqu’on fait

croı̂tre x1 tout en maintenant e4 à 0. Ainsi, x1 sera la variable entrante.
Il faut déterminer jusqu’où l’on peut croı̂tre x1 tout en maintenant e4
à 0. Les équations associées au tableau dernier permettent de conclure
que :
— 10x1 + e1 − 5e4 = 130 ainsi : x1 ≤ 13 car (e1 = 130 − 10x1 ≥ 0)
— 2x1 + e2 − 3e4 = 18 ainsi : x1 ≤ 9 car (e2 = 18 − 2x2 ≥ 0)
— e3 = 34 − 1x1 ≥ 0 d’où x1 ≤ 34
— x2 = 14 − 0x1 ≥ 0 d’où x1 n’est pas limitée
Le tableau de simplexe après une nouvelle itération est illustré dans
la Figure 3.7
Le calcul des coûts marginaux de la ligne cj − zj d’un tableau peu s’ef-
fectuer directement à partir des valeurs numériques de la section centrale
de ce tableau, sans recourir au tableau précédent ni aux équations.
En considérant le dernier tableau. La valeur 25800 de la fonction objec-
tif z s’obtient comme la somme des coefficients de base à gauche et des
valeurs correspondantes.
— z = 9 ∗ 1000 + 14 ∗ 1200 = 25800
Les variables d’écart e1 et e3 n’ayant pas de valeur économique leurs

N. EL HACHEMI UM5-EMI
57 Modélisation et Programmation Linéaire

Figure 3.7 – Tableau canonique de la solution 2

valeurs dans la solution de base sont multipliées par 0.

Le calcul du coefficient zj de la colonne e4 du dernier tableau s’effectue
en multipliant chaque coefficient de base par le coefficient correspondant
de la colonne e4 puis en additionnant les produits. Enfin, le coefficient
cj − zj s’obtient en retranchant le zj ainsi calculé du coefficient de e4 dans
la ligne supérieure du tableau.
Les coefficients cj − zj des variables de base sont tous nuls en vertu de la
condition évoquée auparavant. Pour plus de détails, voir la Figure 3.8.

Figure 3.8 – Calcul du coefficient zj d’une variable

Finalement, on peut constater que le tableau précédent n’est pas opti-

N. EL HACHEMI UM5-EMI
58 Modélisation et Programmation Linéaire

mal, une nouvelle itération du simplexe s’impose. Le Tableau/Figure 3.9

illustre la solution obtenue après cette dernière itération.

Figure 3.9 – Tableau Final

Pour automatiser les calculs associés au pivotage nous pouvons utiliser

la méthode du réctangle, voir la Figure 3.10.
— a0 = a − pivot
b∗c

3.7.7 Description de l’algorithme du simplexe

La construction du tableau initial. Dans le cas d’un modèle (PLS), on
réécrit d’abord le modèle sous forme équivalente (PLS=), puis on choisit
la variable d’écart ei comme variable de base de l’équation i ; dans la
solution de base associée, les variables de décision xj (1 ≤ j ≤ n) sont nulles
et chaque variable d’écart ei est égale au membre droit bi correspondant.
La solution de base asscociée au tableau courant est optimale quand
les coûts marginaux des variables hors base sont tous ≤ dans le cas d’un
modèle de maximisation, et tous ≥ dans un cas de minimisation. L’algo-
rithme prend fin alors. Tant que l’un des coûts marginaux ne respecte
pas la condition précédente, on passe à l’étape B.
Le choix de la variable entrante : Le critère MCM (meilleur coût margi-
nal) recommande de sélectionner la variable entrante de façon à améliorer
z au rythme le plus rapide possible : ainsi, dans le cas d’un modèle de

N. EL HACHEMI UM5-EMI
59 Modélisation et Programmation Linéaire

Figure 3.10 – Méthode du réctangle

maximisation, la variable entrante est telle que son coût marginal est
positif et maximal. En cas d’égalité, on choisit, au hasard ou selon un
critère jugé approprié, parmi les variables qui partagent le meilleur coût
marginal.
Le choix de la variable sortante : Notons xp la variable entrante ; a0ip
le coefficient qui, dans le tableau courant, est situé à l’intersection de la
ligne i et de la colonne xp ; et b0i la valeur de la ligne i dans le tableau
courant. On calcule d’abord, pour chaque variable de base xi dont le
b0
coefficient a0ip est positif, le quotient a0i . La variable sortante est celle qui
ip
minimise ces quotients. En cas d’égalité, on choisit une, au hasard ou
selon un critère jugé approprié, parmi celles qui à la fois admettent en
colonne xp un coefficient positif et minimisent les quotients.
Notons xk la variable sortante. On remplace, dans la section gauche du
tableau, la variable xk et son coefficient de base par la variable entrante xp
et le coefficient cp de cette variable dans la fonction-objectif originale (ce
coefficient apparaı̂t dans la colonne xp au dessus du nom de la variable).
Le pivotage : cette étape comprend 3 opérations. La première consiste
à diviser par le pivot les èlements de la ligne où se trouve le pivot. La
deuxième vise à réécrire chacune des autres lignes de la section centrale

N. EL HACHEMI UM5-EMI
60 Modélisation et Programmation Linéaire

sous une forme équivalente de façon à y inscrire le nombre 0 dans la

colonne du pivot ; la nouvelle version s’obtient de l’ancienne en lui ad-
ditionnant un multiple approprié de la ligne du pivot. (La méthode du
rectangle donne une formule de calcul de ces nouveaux coefficients).
Enfin, pour déterminer le coût marginal de la variable xj , on procède
ainsi : on calcule d’abord un coefficient zj en multipliant, ligne par ligne,
les coefficients de base et les éléments de la colonne xj , puis en addition-
nant les m produits obtenus ; le coût marginal est égal à la différence
cj − zj .
Une fois le pivotage complété, on revient au critère d’optimalité.

3.8 Le modèle PLC et la construction d’un ta-

bleau initial
Les modèles linéaires étudiés jusqu’ici sont de la forme PLS. L’étape
A de l’algorithme du simplexe, consacrée à la construction d’un tableau
initial, s’exécute aisément dans un tel cas.
Abordons la résolution de modèles linéaires continus où apparaissent,
avant l’introduction des variables d’écart ou d’excédent appropriées, des
contraintes de signe ≥ ou =. Ces modèles se présentent sous la forme
générale suivante :

X
Max (Min)z = ci x i (3.26)
i
subject to : (3.27)
 
X ≤
∀i, aij xj  =  bi (3.28)
 

≥
∀i, xi ≥ 0 (3.29)

Pour trouver un modèle linéaire équivalent à (PLC), noté (PLC=),

où chaque contrainte technologique se présente sous forme d’équation, il
suffit d’ajouter contrainte de signe ≤ une variable d’écart, et à chaque

N. EL HACHEMI UM5-EMI
61 Modélisation et Programmation Linéaire

contrainte ≥ une variable d’excédent. Quant aux contraintes comportant

le signe =, leur écriture n’est pas modifiée pour l’instant. Généralement
toutefois, dès que (PLC) contient des contraintes de siges ≥ ou =, le
modèle linéaire (PLC=) correspondant n’est pas sous forme canonique.
En effet, une contrainte de la forme
— a1 x1 + a2 x2 + ... + an xn ≥ b où b > 0
s’écrira comme suit dans (PLC=)
— a1 x1 + a2 x2 + ... + an xn − e = b
Le signe négatif qui affecte la variable e l’empêche de jouer le rôle d’une
variable de base. De même, une contrainte de la forme :
— a1 x1 + a2 x2 + ... + an xn = b où b > 0
rend non admissible la solution x1 = x2 = ... = xn = 0
L’étape A de construction du tableau initial, aisément franchie dans
le cas d’un modèle linéaire sous forme (PLS), ne s’avère pas aussi simple
dans le cas du modèle général (PLC). Il est toutefois possible, en chan-
geant la fonction-objectif, de recourir à l’algorithme du simplexe pour
déterminer une solution admissible et construire un tableau initial. Nous
indiquons maintenant comment procédér à l’aide du problème de la Fon-
derie modifié.

M ax z = 1000x1 + 1200x2 (3.30)

subject to : (3.31)
10x1 + 5x2 ≤ 200 (3.32)
2x1 + 3x2 = 60 (3.33)
x1 ≤ 12 (3.34)
x2 ≥ 6 (3.35)
x1 , x2 ≥ 0 (3.36)

L’ajout de variables d’écart ou d’éxcédent transforme (PMF) en un

N. EL HACHEMI UM5-EMI
62 Modélisation et Programmation Linéaire

modèle (PMF=)

M ax z = 1000x1 + 1200x2 (3.37)

subject to : (3.38)
10x1 + 5x2 + e1 = 200 (3.39)
2x1 + 3x2 = 60 (3.40)
x1 + e3 = 12 (3.41)
x2 − e 4 = 6 (3.42)
x1 , x2 , e1 , e3 , e4 ≥ 0 (3.43)

Figure 3.11 – Région admissible (PMF=)

La région admissible de (PMF) apparaı̂t à la Figure 3.11 : elle se réduit

au segment d’extrémités F et P et comprend 2 points extrêmes seulement,
soit F et P. Il résulte du théorème fondamental de la programmation
linéaire que l’optimum de (PMF) est atteint soit en F, soit en P. Or :
— en F = (0 ; 20) : z = 1000 ∗ 0 + 1200 ∗ 20 = 24000
— en P = (12 ; 12) : z = 1000 ∗ 12 + 1200 ∗ 12 = 26400
— L’optimum est donc atteint en P = (12 ; 12)

N. EL HACHEMI UM5-EMI
63 Modélisation et Programmation Linéaire

L’approche géométrique utilisée ci-dessus pour trouver l’optimum de

(PMF) s’applique seulement aux modèles comportant 2 ou, au maximum,
3 variables de décision. La plupart des modèles rencontrés en pratique ne
satisfont pas à cette condition. Il existe une autre façon de procéder, de
nature algébrique, qui utilise astucieusement l’algorithme du simplexe et
permet de résoudre des modèles de taille quelconque.
D’abord, aux équations de (PMF=) qui proviennent de contraintes
technologiques de signe ≥ ou =, on ajoute des variables, dites artificielles,
qui initialement serviront de variables de base. Et on exige de ces nou-
velles variables, comme des autres déjà présentés dans (PMF=), qu’elles
soient non négatives. Le modèle prend la forme suivante :
L’ajout de variables d’écart ou d’éxcédent transforme (PMF) en un
modèle (PMF=)

M ax z = 1000x1 + 1200x2 (3.44)

subject to : (3.45)
10x1 + 5x2 + e1 = 200 (3.46)
2x1 + 3x2 + a2 = 60 (3.47)
x1 + e3 = 12 (3.48)
x 2 − e 4 + a4 = 6 (3.49)
x1 , x2 , e1 , e3 , e4 , a2 , a4 ≥ 0 (3.50)

3.8.1 La méthode en deux phases

Pour obtenir un modèle équivalent à (PMF=), il faudrait ajouter au
modèle précédent la double contrainte suivante :
— a2 = a4 = 0
ce qui nous ramènerait à la situation de départ !
Le truc consiste à ne inclure la double contrainte dans le modèle, mais à
utiliser une fonction-objectif qui pénalise le fait que les variables artifi-
cielles prennent des valeurs positives. On considère ici le modèle (P M FA )
obtenu du modèle précédent en substituant à z = 1000x1 + 1200x2 l’objectif
suivant :

N. EL HACHEMI UM5-EMI
64 Modélisation et Programmation Linéaire

— M in zA = a2 + a4
Toute solution admissible (x1 ; x2 ) de (PMF) détermine une et une seule
solution admissible (x1 ; x2 ; e1 ; e3 ; e4 ; a2 ; a4 ) de (P M FA ) où a2 = a4 = 0.
Le modèle linéaire (P M FA ) permet de trouver une solution admissible de
(PMF), s’il en existe. Supposons en effet que la valeur minimale de zA
soit 0 ; et considérons une solution de base optimale (x1 ; x2 ; e1 ; e3 ; e4 ; a2 ; a4 )
de (P M FA ). Alors a2 + a4 = 0.
Or, la somme de variables non négatives est nulle seulement si chacune
de ces variables est nulle : il résulte donc que :
— a2 = a4 = 0
Par conséquent, (x1 ; x2 ) est une solution admissible de (PMF).
La Figure/Tableau 3.12 présente le tableau initial associé à la phase
1.

Figure 3.12 – Tableau initial de la phase I

Le modèle (P M FA ) n’est pas tout à fait sous la forme canonique :

comme les variables artificielles a2 et a4 seront dans la base, leurs coeffi-
cients dans zA devraient être nuls. Il est possible de trouver une réécriture
équivalente de zA , où les coefficients de a2 et de a4 sont nuls. Il suffit d’iso-
ler a2 et a4 en fonction des variables hors base.
— a2 = 60 − 2x1 − 3x2
— a4 = 6 − x2 + e4
— a2 + a4 = 66 − 2x1 − 4x2 + e4

N. EL HACHEMI UM5-EMI
65 Modélisation et Programmation Linéaire

La solution de base associée s’obtient en déclarant nulles les variables

hors base et en posant chaque variable de base égale à la valeur apparais-
sant à droite, sur sa ligne :
— x1 = x2 = e 4 = 0
— e1 = 200, a2 = 60, e3 = 12, a4 = 6.
Cette solution correspond à l’origine O = (0; 0) et n’appartient pas à la
région admissible de (PMF=).
Le choix de la variable entrante : puisque l’objectif proposé en phase 1
est de minimiser la somme des variables artificielles a2 et a4 , les variables
susceptibles d’entrer dans la base sont celles dont le coût marginal est
négatif. Nous disposons de 2 variables candidates, soit x1 et x2 . Le taux
auquel décroit zA est de 2 quand x1 est augmenté, et de 4 quand x2
augmente.
Le choix de la variable sortante : La colonne supplémentaire, à la droite
du tableau donne les limites à l’accroissement de x2 découlant de la non-
négativité des différentes variables de base ; par exemple la limite de la
ligne 1 est égale au quotient 2005
, où 200 et 5 sont respectivement la valeur
et l’élément de la colonne x2 situés sur cette première ligne. Aucune limite
n’apparaı̂t à la troisième ligne, car le coefficient situé à l’intersection de
la troisième ligne et de la colonne x2 est nul. La borne 6 de la quatrième
ligne est la plus petite : ce sera la valeur que prendra la variable entrante
x2 . Et la variable a4 , qui était variable de base de cette quatrième ligne,
deviendra nulle et hors base dans le tableau suivant.
Le pivotage : Le pivot ici est le nombre 1 situé à l’intersection de
la colonne x2 et de la quatrième ligne. La première opération consiste
à diviser par le pivot les éléments de la ligne où se trouve celui-ci, ne
commande ici aucun calcul.
Les prochaines itérations de la phase I du simplexe sont présentées dans
les Figures/Tableaux 3.13 et 3.14
La solution de base associée au dernier tableau de simplexe de la phase
1 est :
— x 1 = a2 = a4 = 0
— e1 = 100, e4 = 14, e3 = 12, ; x2 = 20

N. EL HACHEMI UM5-EMI
66 Modélisation et Programmation Linéaire

Figure 3.13 – Tableaux de la phase I

Figure 3.14 – Tableau final de la phase I

Cette solution correspond au point F = (0; 20). Les coûts marginaux des
variables hors base sont tous ≥ 0, ce qui signifie que l’on a atteint un
minimum de la fonction-objectif artificielle zA . Les variables a2 et a4 dont
nulles : le point F appartient donc à la région admissible et peut servir
de solution initiale pour la phase II.
La phase II reprend l’objectif original qui était de maximiser z =
1000x1 + 1200x2 . Le tableau initial de la phase II s’obtient en modifiant le
dernier tableau de la première phase de la façon suivante :
— Les colonnes associées aux variables artificielles sont biffées ;
— La ligne supérieure et la colonne ”Coefficients de base” sont réécrites

N. EL HACHEMI UM5-EMI
67 Modélisation et Programmation Linéaire

en utilisant les coefficients cj de la fonction-objectif z ;

— Les lignes zj et cj − zj sont recalculées à partir des nouveaux coef-
ficients de base.
Le coût marginal de x1 étant positif, il est possible d’augmenter la
valeur z en entrant x1 dans la base. La plus petite limite se trouve sur la
ligne 3 : c’est donc la variable e3 qui sortira de la base. Le pivot est le
nombre 1 situé à l’intersection de la colonne x1 et la ligne 3. Les tableaux
suivant présentent le tableau initial de la phase II puis le tableau du
simplexe obtenu après pivotage (Voir Figure 3.15).

Figure 3.15 – Tableaux de la phase II

3.8.2 Transition et Cas pathologiques

Supposons que, lors de la phase I d’un modèle de type (PLC), on
ait effectué un certain nombres et que les coûts marginaux du dernier
tableau obtenu soient non négatifs. On a alors atteint un minimum de zA .
Si dans ce tableau, toutes les variables artificielles sont hors base, il suffit
de biffer les colonnes associées aux variables artificielles pour obtenir une
solution de base admissible de (PLC=). Avant d’entreprendre la première
itération de la phase II, il faudra inscrire les coefficients cj de la fonction-
objectif originale z à la place de ceux de zA , puis recalculer les coûts

N. EL HACHEMI UM5-EMI
68 Modélisation et Programmation Linéaire

marginaux.
Il arrive que la phase I se termine par un tableau dont la base contient
une ou plusieurs variables artificielles. Si l’une de ces variables artificielles
de base prend une valeur positive, la valeur minimale de zA est positive
et, par conséquent, le problème initial (PLC) n’a pas de solution admis-
sible.
Par contre, si toutes les variables artificielles de base ont une valeur nulle,
on tentera de les sortir de la base, afin d’écrire le problème initial sous
forme canonique. En effet, le dernier tableau I donne une solution ad-
missible de (PLC=), sans plus. Or, le but de la phase I est d’obtenir une
solution de base.
Considérons une variable artificielle as qui une variable de base as-
sociée à la ligne i du tableau du simplexe de la phase I dont la valeur de
zA est nulle. Deux cas peuvent survenir :
— Sur la ligne i de ce tableau, au moins une variable hors base non
artificielle admet un coefficient non nul. On peut donc faire sortir
as de la base en s’appuyant sur l’une des variables hors base non
artificielle dont le coefficient associé à la ligne i est non nul.
— Les coefficients associés à la ligne i des variables hors base non
artificielles sont tous nuls. Dans ce cas, une fois les variables hors
base artificielles soient biffées, la contrainte liée à la ligne i devient
as = 0.

Exemple 1 ’Cas pathologique 1’

M ax z = 2x1 + x2 (3.51)
subject to : (3.52)
x1 − 2x2 = 2 (3.53)
x1 − 3x2 ≥ 1 (3.54)
x1 − x2= 3 (3.55)
x1 , x2 ≥ 0 (3.56)

N. EL HACHEMI UM5-EMI
69 Modélisation et Programmation Linéaire

La formulation du modèle précédent sous forme de contraintes (=)

est :

M ax z = 2x1 + x2 (3.57)
subject to : (3.58)
x1 − 2x2 + a1 = 2 (3.59)
x1 − 3x2 − e2 + a2 = 1 (3.60)
x 1 − x 2 + a3 = 3 (3.61)
x1 , x2 , e2 , a1 , a2 , a3 ≥ 0 (3.62)

La résolution de la phase 1 comporte 4 tableaux du simple qu’on

présente ci-dessous :

0 0 0 1 1 1
Base
x1 x2 e2 a1 a2 a3 Valeur
1 a1 1 -2 0 1 0 0 2
1 a2 1 -3 -1 0 1 0 1
1 a3 1 -1 0 0 0 1 3
cj − zj -3 6 1 0 0 0 6

Table 3.1 – Tableau 1

0 0 0 1 1 1
Base
x1 x2 e2 a1 a2 a3 Valeur
1 a1 0 1 1 1 -1 0 1
0 x1 1 -3 -1 0 1 0 1
1 a3 0 2 1 0 -1 1 2
cj − zj 0 -3 -2 0 3 0 3

Table 3.2 – Tableau 2

Ainsi, la transition vers la phase II se fait simplement (Voir Tableau

3.5)

Exemple 2 ’Cas pathologique 2’

N. EL HACHEMI UM5-EMI
70 Modélisation et Programmation Linéaire

0 0 0 1 1 1
Base
x1 x2 e2 a1 a2 a3 Valeur
0 x2 0 1 1 1 -1 0 1
0 x1 1 0 2 3 -2 0 4
1 a3 0 0 -1 -2 1 1 0
cj − zj 0 0 1 3 0 0 0

Table 3.3 – Tableau 3

0 0 0 1 1 1
Base
x1 x2 e2 a1 a2 a3 Valeur
0 x2 0 1 0 -1 0 1 1
0 x1 1 0 0 -1 0 2 4
0 e2 0 0 1 2 -1 -1 0
cj − zj 0 0 0 1 1 1 0

Table 3.4 – Tableau 4 faisant sortir la variable artificielle de la base

2 1 0
Base
x1 x2 e2 Valeur
1 x2 0 1 0 1
2 x1 1 0 0 4
0 e2 0 0 1 0
cj − zj 0 0 0 9

Table 3.5 – Tableau 1 Phase II

M ax z = 6x11 + 5x12 + 7x21 + 4x22 (3.63)

subject to : (3.64)
x11 + x12 = 20 (3.65)
x21 + x22 = 10 (3.66)
x11 + x21 = 13 (3.67)
x12 + x22 = 17 (3.68)
x11 , x12 , x21 , x22 ≥ 0 (3.69)

La formulation du modèle précédent sous forme de contraintes (=)

N. EL HACHEMI UM5-EMI
71 Modélisation et Programmation Linéaire

est :

M ax z = 6x11 + 5x12 + 7x21 + 4x22 (3.70)

subject to : (3.71)
x11 + x12 + a1 = 20 (3.72)
x21 + x22 + a2 = 10 (3.73)
x11 + x21 + a3 = 13 (3.74)
x12 + x22 + a4 = 17 (3.75)
x11 , x12 , x21 , x22 , a1 , a2 , a3 , a4 ≥ 0 (3.76)

Comme on le verra dans les tableaux du simplexe qui suivront une des
variables artificielles restera dans les tableaux et pourtant le problème est
réalisable. En fait, la variable artificielle en question est nulle et on ne
peut pas la faire sortir de la base en la permutant avec une autre variable
du modèle.

0 0 0 0 1 1 1 1
Base
x11 x12 x21 x22 a1 a2 a3 a4 Valeur
1 a1 1 1 0 0 1 0 0 0 20
1 a2 0 0 1 1 0 1 0 0 10
1 a3 1 0 1 0 0 0 1 0 13
1 a4 0 1 0 1 0 0 0 1 17
cj − zj -2 -2 -2 -2 0 0 0 0 60

Table 3.6 – Tableau 1 de la Phase 1 : Cas 2

0 0 0 0 1 1 1 1
Base
x11 x12 x21 x22 a1 a2 a3 a4 Valeur
1 a1 0 1 -1 0 1 0 -1 0 7
1 a2 0 0 1 1 0 1 0 0 10
0 x11 1 0 1 0 0 0 1 0 13
1 a4 0 1 0 1 0 0 0 1 17
cj − zj 0 -2 0 -2 0 0 2 0 34

Table 3.7 – Tableau 2 de la Phase 1 : Cas 2

N. EL HACHEMI UM5-EMI
72 Modélisation et Programmation Linéaire

0 0 0 0 1 1 1 1
Base
x11 x12 x21 x22 a1 a2 a3 a4 Valeur
0 x12 0 1 -1 0 1 0 -1 0 7
1 a2 0 0 1 1 0 1 0 0 10
0 x11 1 0 1 0 0 0 1 0 13
1 a4 0 0 1 1 -1 0 1 1 10
cj − zj 0 0 -2 -2 2 0 0 0 20

Table 3.8 – Tableau 3 de la Phase 1 : Cas 2

0 0 0 0 1 1 1 1
Base
x11 x12 x21 x22 a1 a2 a3 a4 Valeur
0 x12 0 1 -1 0 1 0 -1 0 7
0 x22 0 0 1 1 0 1 0 0 10
0 x11 1 0 1 0 0 0 1 0 13
1 a4 0 0 0 0 -1 -1 1 1 0
cj − zj 0 0 0 0 2 2 0 0 0

Table 3.9 – Tableau 4 de la Phase 1 : Cas 2

6 5 7 4 0
Base
x11 x12 x21 x22 a4 Valeur
5 x12 0 1 -1 0 0 7
4 x22 0 0 1 1 0 10
6 x11 1 0 1 0 0 13
0 a4 0 0 0 0 1 0
cj − zj 0 0 2 0 0 153

Table 3.10 – Tableau 1 de la Phase 2 : Cas 2

6 5 7 4 0
Base
x11 x12 x21 x22 a4 Valeur
5 x12 0 1 0 1 0 17
7 x21 0 0 1 1 0 10
6 x11 1 0 0 -1 0 3
0 a4 0 0 0 0 1 0
cj − zj 0 0 0 -2 0 173

Table 3.11 – Tableau 2 de la Phase 2 : Cas 2

3.8.3 La méthode du grand M

On peut résoudre les modèles de type (PLC) par une autre méthode,
dite du grand M. On commence ici encore par ajouter une variable artifi-
cielle dans chaque contrainte technologique de signe = ou ≥. mais, plutôt
que de scinder la résolution en 2 phases dont la première est consacrée

N. EL HACHEMI UM5-EMI
73 Modélisation et Programmation Linéaire

à minimiser la somme des variables artificielles, on adjoint à la fonction-

objectif z un terme de pénalité pour chaque variable artificielle et on
procède en une phase unique.
Illustrons la méthode par l’exemple (PMF). Une fois les variables
artificielles ajoutées, le modèle à ajouter est constitué, comme dans la
méthode en 2 phases. Mais l’objectif est ici remplacé par le suivant :
— M ax zM = 1000x1 + 1200x2 − M a2 − M a4
où M est une constante positive, dont la valeur, sans être précisée, dépasse
largement tous les autres nombres dans le modèle.
Les calculs s’effectuent avec le symbole M , dont la valeur n’est jamais
précisée. Il serait possible de donner à M une valeur précise, à condi-
tion de l’adapter à chaque situation. Nous optons pour l’approche tra-
ditionnelle, qui consiste à considérer M comme un paramètres supposé
beaucoup plus grand que tous les autres nombres apparaissant dans le
modèle.
Avec la méthode du grand M , ou bien toutes les variables artificielles
prennent la valeur 0 à l’optimum et l’on obtient une solution admissible
te optimale, ou bien certaines d’entre elles prennent une valeur positive
et alors le modèle linéaire (PLC) n’a pas de solution admissible.

N. EL HACHEMI UM5-EMI
Chapitre 4

L’analyse postoptimale

4.1 Introduction
L’objectif de ce chapitre est de décrire l’impact sur la solution optimale
chaque changement apporté à l’un ou l’autre des paramètres du modèle.
Afin d’éviter de longs et fastidieux calculs.
On comprend qu’il faille investir sur la sensibilité des solutions optimales
aux changements envisageables dans la valeur des paramètres aij , cj et
bi . Cette analyse à laquelle nous soumettrons les modèles porte le nom
d’analyse postoptimale.

4.2 La modification d’un coefficient cj

Reprenons le modèle de la Fonderie, écrivons la nouvelle fonction-
objectif z 0 du modèle sous la forme suivante :
— z 0 = (1000 + ∆)x1 + 1200x2 = z + ∆x1
Considérons le tableau (Voir Figure 4.1 ) qui reproduit le tableau final
de la Fonderie modifié de la façon suivante : 1000 + ∆ a été substitué
au coefficient de x1 a été substitué au coefficient de x1 dans la fonction-
objectif ; deux lignes ont été ajoutées, où sont inscrits les zj0 et les coûts
marginaux de la fonction-objectif z 0 .
La solution de base associée au tableau présenté à la Figure/Tableau
4.1 est optimale pour z 0 si et seulement si, sur la dernière ligne, les coûts

74
75 Modélisation et Programmation Linéaire

Figure 4.1 – Tableau final de (P’)

marginaux des variables hors base sont tous ≤, c’est-à-dire :

— si et seulement si −30 − 0, 15∆ ≤ 0 et −350 + 0, 25∆ ≤ 0
−30 350
— si et seulement si ∆ ≥ 0,15 et ∆ ≤ 0,25
— si et seulement −200 ≤ ∆ ≤ 1400
— si et seulement si 800 ≤ 1000 + ∆ ≤ 2400

4.3 La modification d’un coefficient bj

Reprenons le modèle de la Fonderie, écrivons la nouvelle contrainte
associée au nombre d’heures disponible dans l’atelier. Le paramètres ∆
représente l’écart entre les heures réellement disponibles et les 200 heures
tenues pour acquises dans le modèle d’origine. Le tableau initial du sim-
plexe de (P”) s’écrit sous la forme prśentée à la Figure/Tableau 4.2.
On observe que, dans la partie centrale de ce tableau initial, les co-
lonnes associées au paramètre ∆ et à la variable d’écart e1 sont identiques.
Cette propriété sera conservé d’une itération à l’autre. Par conséquent,
le tableau final sera sous la forme décrite à la Figure/Tableau 4.3.
La solution de base présentée à la Figure/Tableau 4.3 sera optimale
pourvu qu’elle soit admissible. Et elle sera admissible pourvu que chacune
des 4 variables de base soit non nǵatives, c’est-à-dire :

N. EL HACHEMI UM5-EMI
76 Modélisation et Programmation Linéaire

Figure 4.2 – Tableau initial de (P”)

Figure 4.3 – Tableau final de (P”)

— e4 = 4 + 0, 1∆ ≥ 0 c’est-à-dire ∆ ≥ −40
— x1 = 15 + 0, 15∆ ≥ 0 c’est-à-dire ∆ ≥ −100
— e3 = 19 − 0, 15∆ ≥ 0 c’est-à-dire ∆ ≤ 126, 67
— x2 = 10 − 0, 1∆ ≥ 0 c’est-à-dire ∆ ≤ 100
En résumé : la solution de base associée au tableau précédent est admis-
sible (et optimale) pourvu que −40 ≤ ∆ ≤ 100.

4.4 Le champ de l’analyse postoptimale proposée

L’analyse postoptimale s’intéressera à l’impact sur la solution opti-
male des modifications apportées à la valeur d’un seul bi ou d’un seul cj .
Convenons d’une notation pour les modifications envisagées :

N. EL HACHEMI UM5-EMI
77 Modélisation et Programmation Linéaire

— Écrire c0j = cj + ∆
— Écrire b0i = bi + ∆
Considérons le modèle d’illustration suivant :

M ax 10x1 + 6x2 + 6x3 + 8x4 (4.1)

subject to : (4.2)
x1 + x2 + x3 + x4 ≤ 200 (4.3)
2x2 + 4x2 + 6x3 + 3x4 ≤ 360 (4.4)
2x1 + 5x2 + 4x3 + 3x4 ≤ 450 (4.5)
2x1 + 5x2 + 4x3 + 3x4 ≥ 300 (4.6)
x2 ≥ 30 (4.7)
x1 ≥ 20 (4.8)
x1 ≤ 170 (4.9)
x1 , x2 , x3 , x4 ≥ 0 (4.10)

4.4.1 La modification du cj d’une variable originale hors

base
Considérons le cas de la variable x3 dont le cj = 6. La solution opti-
male recommande de ne produire aucune unité de P3 comme indiqué à la
Figure/Tableau 4.4
On voudra connaı̂tre les modifications à apporter aux paramètres as-
sociés à P3 pour entreprendre d’en fabriquer, nous allons déterminer l’in-
tervalle auquel le coefficient c3 doit appartenir pour éviter de devoir re-
manier la base optimale du modèle original. Commençons par remplacer
c3 par c03 = c3 + ∆ = 6 + ∆. Les conséquences de cette modifications sur
l’écriture du tableau final sont consignées à la Figure/Tableau 4.4.
La modification apportée à c3 affecte une seule autre entrée du tableau,
le coût marginal cj − zj de la variable x3 , qui devient −24 + ∆. Pour que le
tableau précédent (Voir Figure/Tableau 4.4) soit optimal, il faudra que :
— −24 + ∆ ≤ 0, c’est-à-dire ∆ ≤ 24.

N. EL HACHEMI UM5-EMI
78 Modélisation et Programmation Linéaire

Figure 4.4 – Impact de la modification du cj de x3

Le profit unitaire c3 de P3 est présentement trop faible : il faudrait l’aug-

menter d’au moins 24 dollars pour qu’il soit rentable d’enclencher la
production de P3 .

4.4.2 La modification du cj d’une variable de base

Considérons le cj de x1 qui est égal à 10 dans le modèle original. La
présence de x1 dans la base optimale montre que le profit associé à la vente
d’une unité de P1 est suffisamment élevé pour en assurer une production
de 120 unités. Est-il possible qu’une modification de c1 entraı̂ne une nou-
velle solution optimale ? Le tableau qui suivra (Voir Figure/Tableau 4.5)
présente les modifications sur le tableau optimal lorsque c01 = 10 + ∆.
En conclusion, une modification du cj d’une variable de base peut
entraı̂ner la modification des zj et des cj − zj associés aux variables hors
base. Pour que tableau précédent (Voir Figure/Tableau 4.5) soit optimal,
il faut que tous les coûts marginaux associés aux variables hors base soient
non positifs.
— −24 − 3∆ ≤ 0 c’est-à-dire ∆ ≥ −8
— −7 − 1, 5∆ ≤ 0 c’est-à-dire ∆ ≥ −4, 67
— −5 − 0, 5∆ ≤ 0 c’est-à-dire ∆ ≥ −10

N. EL HACHEMI UM5-EMI
79 Modélisation et Programmation Linéaire

Figure 4.5 – Impact de la modification du cj de x1

— −14 − 2∆ ≤ 0 c’est-à-dire ∆ ≥ −7
En résumé, tous les cj − zj sont non positifs
— pourvu que ∆ ≥ −4, 67
— pourvu que c0j = cj + ∆ ≥ 10 − 4, 67 = 5, 33
L’intervalle de variation de c1 est donc [5, 33; +∞[, si le profit initial associé
à la vente d’une unité de P1 chute de 4,67 dollars, aucune unité de P1
excédentaire aux unités obligatoires ne sera fabriquée.

4.4.3 La modification d’un bi : Signe d’inéquation

Le signe d’inéquation d’une contrainte technologique et le classement
de la variable d’écart ou d’excédent associée comme variable de base ou
hors base dans le tableau optimal sont les deux facteurs principaux à
considérer dans l’analyse postoptimale d’une modification apportée à bi .
Contrainte de signe ≤ et variable ei hors base

La variable d’écart e2 est hors base dans le tableau optimal. Analysons

l’impact qu’a, sur la solution optimale, le remplacement de b2 par b02 = b2 +
∆. Le tableau suivant (Voir Figure/Tableau 4.6) donne le tableau initial
de (P’=) lorsque ∆ est traité comme une variable spéciale. On constate
que, les colonnes associées à e2 et à ∆ sont identiques. Les pivotages

N. EL HACHEMI UM5-EMI
80 Modélisation et Programmation Linéaire

qui mèneront au tableau final provoqueront dans ces deux colonnes les
mêmes opérations arithmétiques. On les retrouvera donc identiques l’une
à l’autre dans chacun des tableaux intermédiaires et dans le tableau final.

Figure 4.6 – Impact de la modification de b2 dans le tableau initial

Les modifications apportées à un membre droit n’affectent pas les

coûts marginaux. Toutefois, les valeurs de certaines variables de base
pourront changer. En donnant aux variables hors base leur valeur 0. Le
tableau suivant (Voir Figure/Tableau 4.7) correspond au tableau final du
simplexe.

Figure 4.7 – Impact de la modification de b2 dans le tableau final

— e1 = 50 − 0, 5∆
— x1 = 120 + 0, 5∆
— e3 = 60 − ∆

N. EL HACHEMI UM5-EMI
81 Modélisation et Programmation Linéaire

— e4 = 90 + ∆
— x2 = 30
— e6 = 100 + 0, 5∆
— e7 = 50 − 0, 5∆
Ces équations permettent de recalculer la valeur des variables de base
à la suite de la modification d’un bi par l’ajout de ∆.
— e1 = 50 − 0, 5∆ c’est-à-dire ∆ ≤ 100
— x1 = 120 + 0, 5∆ c’est-à-dire ∆ ≥ −240
— e3 = 60 − ∆ c’est-à-dire ∆ ≤ 60
— e4 = 90 + ∆ c’est-à-dire ∆ ≥ −90
— x2 = 30 aucune restriction
— e6 = 100 + 0, 5∆ c’est-à-dire ∆ ≥ −200
— e7 = 50 − 0, 5∆ c’est-à-dire ∆ ≤ 100
On tire des inéquations que ∆ doit appartenir à [-90 ; 60] pour que
les valeurs des variables de base données par les équations restent non
négatives. Comme les valeurs des cj − zj sont indifférentes à toute mo-
dification acceptable d’un bi , les variables de base adoptent des valeurs
optimales chaque fois que ∆ appartient à [-90 ; 60].
Considérons l’impact sur le profit de la modification de bi et supposons
que ∆ = 20, selon les équations précédente, il en découle que x1 = 130 et
x2 = 30. Les variables x3 et x4 restent hors base. Cette nouvelle solution
engendre un profit de 10 ∗ 130 + 6 ∗ 30 = 1480. Pour calculer le profit en
fonction de ∆, on reprend l’expression de la fonction objectif z = 10x1 +
6x2 + 6x3 + 8x4 . Étant donné que x3 et x4 sont hors base alors z = 10(120 +
0, 5∆) + 6(30) = 1380 + 5∆
Contrainte de signe ≤ et variable ei dans la base

Pour analyser l’impact sur la solution optimale du remplacement de

b1 par b01 = b1 + ∆, établissons les équations d’ajustement relatives à la
colonne de la variable e1 correspondante au tableau final du simplexe. On
obtient e1 = 50 + ∆.
Le fait que e1 ≥ 0 lorsque ∆ ≥ −50 entraı̂ne que l’intervalle de variation
de b1 est [150 ; +∞[. Le plan demeure admissible tant qu’on dispose d’au

N. EL HACHEMI UM5-EMI
82 Modélisation et Programmation Linéaire

moins 150 heures dans cet atelier ; et il demeure optimal puisque aucun
cj − zj ne change de signe.
Contrainte de signe ≥ et variable ei hors base

Pour analyser l’impact d’une modification de ∆ au membre droit bi

d’une contrainte de signe ≥, on serait porté à remplacer bi par b0i = bi + ∆.
On ferait face alors à une petite difficulté. La colonne de ∆ contient les
mêmes valeurs que la colonne ei , mais les signes des deux colonnes sont
inversés.
Il suffit de remarquer que la relation entre ∆ et ei sera préservée d’une
itération à l’autre et que, dans le tableau final, les colonnes ∆ et ei contien-
dront les mêmes valeurs, mais les signes en seront inversés...
Il existe une autre approche, que nous préférerons. Supposons que l’on
veuille donner une nouvelle valeur à bi . On écrira b0i = bi − ∆
Dénotons par (P’) le modèle obtenu en modifiant le membre droit de
la contrainte suivante : x2 ≥ 30 − ∆, le tableau initial de (P’) est le suivant
(Voir Figure/Tableau 4.8) :

Figure 4.8 – Impact de la modification de b5 dans le tableau initial

— e1 = 50 − ∆ ⇒ ∆ ≤ 50
— x1 = 120 + 2∆ ⇒ ∆ ≥ −60
— e3 = 60 + ∆ ⇒ ∆ ≥ −60
— e4 = 90 − ∆ ⇒ ∆ ≤ 90
— x2 = 30 − ∆ ⇒ ∆ ≤ 30
— e6 = 100 + 2∆ ⇒ ∆ ≥ −50

N. EL HACHEMI UM5-EMI
83 Modélisation et Programmation Linéaire

— e7 = 50 − 2∆ ⇒ ∆ ≤ 25
En résumé, les nouvelles valeurs des variables de base sont non négatives
et constituent une solution optimale de (P’), pourvu que ∆ est dans [-50 ;
25].
Contrainte de signe ≥ et variable ei dans la base

Lorsqu’on décide de remplacer b6 par b06 = b6 − ∆. Les équations d’ajus-

tement, sauf celle associée à e6 , disent simplement que la valeur de la
variable de base est inchangée, ce qui implique qu’elle reste non négative.
L’équation d’ajustement associée à la colonne de e6 s’écrit : e6 = 100∆.
Par conséquent, la valeur de la variable de base e6 demeure non négative
pourvu que 100 + ∆ ≥ 0 ⇒ −∆ ≤ 100.

4.5 La dualité
4.5.1 La construction et l’interprétation du modèle dual
On reprend le problème de la Fonderie décrit auparavant. Henri, pro-
priétaire d’une fonderie concurrente, se propose de racheter les ressources
de la Fonderie Rivière-Blue. Henri connaı̂t bien les paramètres du modèle
de la Fonderie, qu’il sait formuler mais sans savoir le résoudre.
Les prix p1 dollars et p2 dollars sont les montants unitaires qu’Henri pro-
posera au propriétaire de la Fonderie pour s’approprier chaque heure de
production des ateliers 1 et 2. Henri offrira une compensation de p3 dol-
lars la tonne en échange du droit de vendre de la tuyauterie à la clientèle
acquise à la Fonderie. En contrepartie du droit de vendre des gueuses à
cette clientèle, il offrira p4 dollars la tonne.
Henri veut débourser le moins possible pour l’achat de la totalité des
quatres ressources, il cherche donc à minimiser : w = 200p1 +60p2 +34p3 +14p4
tout en proposant au propriétaire de la Fonderie une offre équitable.
Ainsi, quand le propriétaire de la Fonderie vend une tonne de tuyauterie,
il empoche 1000 dollars. Mais pour vendre une tonne de tuyauterie, il
lui faut consacrer à sa production et à sa vente 10 heures de ressources

N. EL HACHEMI UM5-EMI
84 Modélisation et Programmation Linéaire

de l’atelier 1, 2 heures de celles de l’atelier 2 et une unité de sa part de

marché pour ce produit. Henri estime que le propriétaire n’acceptera pas
céder ce paquet de ressources pour moins de 1000 dollars. Donc :
— 10p1 + 2p2 + 1p3 ≥ 1000.
Une démarche similaire à propos de l’autre produit l’amène à écrire
que :
— 5p1 + 3p2 + 1p4 ≥ 1200.
Et il est raisonnable de penser que :
— p1 , p2 , p3 , p4 ≥ 0.
Pour déterminer les prix unitaires minimaux qu’il faut proposer aux
propriétaire, Henri devrait résoudre le modèle linéaire suivant :

M in 200p1 + 60p2 + 34p3 + 14p4 (4.11)

subject to : (4.12)
10p1 + 2p2 + 1p3 ≥ 1000 (4.13)
5p1 + 3p2 + 1p4 ≥ 1200 (4.14)
p1 , p2 , p3 , p4 ≥ 0 (4.15)

Le modèle précédent, que nous dénoterons (D), s’appelle le dual de

(P). La création du modèle dual (D) a une action en retour : (P) reçoit le
nom de modèle primal. Il y a plusieurs résultats mathématiques concer-
nant les relations entre un modèle primal et son dual. Nous allons en
indiquer quelques-uns. Bien que ces résultats puissent s’énoncer de façon
générale, nous nous contenterons de les illustrer en mettant en scène les
modèle (P) et (D).

Théorème 4.1 Le théorème de la dualité faible

Si (x01 ; x02 ) et (p01 ; p02 ; p03 ; p04 ) sont des solutions admissibles de (P) et (D)
respectivement, alors :
— 1000x01 + 1200x02 ≤ 200p01 + 60p02 + 34p03 + 14p04
En d’autres mots, toute solution admissible du primal donne à la fonction-
objectif z une valeur inférieure ou égale à la valeur que prend la fonction-
objectif w du dual en n’importe laquelle de ses solutions admissibles.

N. EL HACHEMI UM5-EMI
85 Modélisation et Programmation Linéaire

Corollaire 4.1 Si une solution admissible du problème primal et une so-

lution admissible du problème dual donnent à leur fonction-objectif res-
pective la même valeur, alors elles sont toutes deux optimales.

Corollaire 4.2 Si le problème primal est non borné, alors le problème

dual n’a pas de solution admissible.

Théorème 4.2 Le théorème de la dualité forte

Si le problème primal possède une solution optimale, alors le problème

en possède une aussi ; de plus, les valeurs optimales des 2 modèles sont
égales. Ce théorème est plus fort que le précédent, car seule l’exis-
tence d’une solution optimale du modèle primal est supposée. Ainsi,
en sachant que le plan de production (15 ; 10), qui assure un profit de
27.000 $, est optimal pour (P), on sait que (D) admet forcément une
solution optimale pour laquelle la fonction-objectif w de (D) prend la
valeur 27.000.

Théorème 4.3 Le théorème des écarts complémentaires

Soient x0 = (x01 ; x02 ) une solution admissible du modèle primal (P) ; et

e0 = (e01 ; e02 ; e03 ; e04 ) les valeurs des variables d’écart associées à x0 . Soient
également p0 = (p01 ; p02 ; p03 ; p04 ) une solution admissible du modèle dual (D) ;
et s0 = (s01 ; s02 ) les valeurs des variables d’excédent associées à p0 .
Le théorème des écarts complémentaires :
Les solutions admissibles x0 et p0 sont optimales si et seulement si :
— e0i p0i = 0 pour i = 1, 2, 3, 4
— s0j x0j = 0 pour j = 1, 2

N. EL HACHEMI UM5-EMI
86 Modélisation et Programmation Linéaire

L’illustration des résultats obtenus à partir du théorème des écarts

complémentaires est disponible à la Figure 4.9. D’autres techniques qui
consistent à exploiter les résultats du dernier tableau de simplexe per-
mettent aussi de relier les deux problèmes primal et dual.

Figure 4.9 – Illustration du théorème des écarts complémentaires

N. EL HACHEMI UM5-EMI

Vous aimerez peut-être aussi

Compression d'images optimisée
Pas encore d'évaluation
Compression d'images optimisée
18 pages
Algorithmes de compression d'image
Pas encore d'évaluation
Algorithmes de compression d'image
17 pages
TP - PowerBI - SupplyChain Rapport Stage Salma Battach
Pas encore d'évaluation
TP - PowerBI - SupplyChain Rapport Stage Salma Battach
22 pages
TD de Probabilités et Processus Stochastiques
Pas encore d'évaluation
TD de Probabilités et Processus Stochastiques
7 pages
Résolution de Sudoku par recuit simulé
Pas encore d'évaluation
Résolution de Sudoku par recuit simulé
10 pages
Problème de routage VRP et solutions
Pas encore d'évaluation
Problème de routage VRP et solutions
52 pages
Optimisation de production en scierie
Pas encore d'évaluation
Optimisation de production en scierie
3 pages
Épreuve Informatique MP 2020
Pas encore d'évaluation
Épreuve Informatique MP 2020
9 pages
Optimisation Non Linéaire avec Contraintes
Pas encore d'évaluation
Optimisation Non Linéaire avec Contraintes
14 pages
Recherche Opérationnelle : Graphes et Dijkstra
Pas encore d'évaluation
Recherche Opérationnelle : Graphes et Dijkstra
1 page
Sujets TIPE en Maths et Informatique
Pas encore d'évaluation
Sujets TIPE en Maths et Informatique
5 pages
Probabilités et Statistiques Appliquées 2022-2023
Pas encore d'évaluation
Probabilités et Statistiques Appliquées 2022-2023
2 pages
Comment Gagner Au Monopoly
Pas encore d'évaluation
Comment Gagner Au Monopoly
7 pages
Algorithmes Gloutons en Optimisation
Pas encore d'évaluation
Algorithmes Gloutons en Optimisation
4 pages
Corrigé CNC 2015 Mathématiques MP
Pas encore d'évaluation
Corrigé CNC 2015 Mathématiques MP
5 pages
Épreuve Informatique MP 2024
Pas encore d'évaluation
Épreuve Informatique MP 2024
13 pages
Filière Génie Logiciel au Maroc
Pas encore d'évaluation
Filière Génie Logiciel au Maroc
2 pages
Cours IPT MP - Python et Algorithmique
Pas encore d'évaluation
Cours IPT MP - Python et Algorithmique
35 pages
Modélisation d'une chaîne de pendules
Pas encore d'évaluation
Modélisation d'une chaîne de pendules
6 pages
Chemin le plus court pour tramway Fès
Pas encore d'évaluation
Chemin le plus court pour tramway Fès
7 pages
CV pour stage d'observation en industrie
Pas encore d'évaluation
CV pour stage d'observation en industrie
1 page
Résumé de la théorie des graphes
Pas encore d'évaluation
Résumé de la théorie des graphes
47 pages
CCP MP 1999 Corrigé
Pas encore d'évaluation
CCP MP 1999 Corrigé
6 pages
Math de L'ingenieur Cycle Ingenieur 1 Ere
100% (1)
Math de L'ingenieur Cycle Ingenieur 1 Ere
31 pages
Introduction aux Arbres Binaires
Pas encore d'évaluation
Introduction aux Arbres Binaires
11 pages
DS7 1
Pas encore d'évaluation
DS7 1
4 pages
Densité de courant en électromagnétisme
Pas encore d'évaluation
Densité de courant en électromagnétisme
11 pages
Coloration des graphes et applications
Pas encore d'évaluation
Coloration des graphes et applications
34 pages
Exercices Corrigés Oscillateur Colpitts
Pas encore d'évaluation
Exercices Corrigés Oscillateur Colpitts
6 pages
A - Cours Systèmes Manufacturiers Part 1&2
Pas encore d'évaluation
A - Cours Systèmes Manufacturiers Part 1&2
43 pages
Vérification des entiers distincts en Python
Pas encore d'évaluation
Vérification des entiers distincts en Python
6 pages
CCMP MP PC PSI Info 2022 Magnetisme CorrigePriveUPSTI
Pas encore d'évaluation
CCMP MP PC PSI Info 2022 Magnetisme CorrigePriveUPSTI
6 pages
Épreuve de Physique I - Concours 2010 PSI
Pas encore d'évaluation
Épreuve de Physique I - Concours 2010 PSI
8 pages
TP Informatique : Traitement d'Images CPGE
Pas encore d'évaluation
TP Informatique : Traitement d'Images CPGE
1 page
Épreuve d'Informatique : Diffusion Thermique
Pas encore d'évaluation
Épreuve d'Informatique : Diffusion Thermique
43 pages
Introduction à la théorie des jeux
100% (1)
Introduction à la théorie des jeux
10 pages
Corrigé Maths 1 Mines 2021
Pas encore d'évaluation
Corrigé Maths 1 Mines 2021
7 pages
Optimisation ACO pour TSP et VRP
Pas encore d'évaluation
Optimisation ACO pour TSP et VRP
13 pages
Résultats concours agrégation 2022
Pas encore d'évaluation
Résultats concours agrégation 2022
1 page
Constante d'acidité et acido-bases
100% (2)
Constante d'acidité et acido-bases
15 pages
Programme Grande École ENSAM 2021-2022
100% (1)
Programme Grande École ENSAM 2021-2022
7 pages
Méta-heuristiques et Recuit Simulé
Pas encore d'évaluation
Méta-heuristiques et Recuit Simulé
23 pages
Programmation Linéaire en C : Méthodes et Code
Pas encore d'évaluation
Programmation Linéaire en C : Méthodes et Code
10 pages
Apprentissage Supervisé : Régression et KNN
Pas encore d'évaluation
Apprentissage Supervisé : Régression et KNN
2 pages
Analyse Numérique : Méthodes et Résolutions
Pas encore d'évaluation
Analyse Numérique : Méthodes et Résolutions
35 pages
Auto-Spotter : Sécurité en bench-press
Pas encore d'évaluation
Auto-Spotter : Sécurité en bench-press
5 pages
Séminaires en Génie Industriel 2023
Pas encore d'évaluation
Séminaires en Génie Industriel 2023
23 pages
Éléments de correction EMLYON 2015 S
Pas encore d'évaluation
Éléments de correction EMLYON 2015 S
6 pages
Recherche de chemins et algorithmes associés
Pas encore d'évaluation
Recherche de chemins et algorithmes associés
37 pages
Dôme de Fer : Interception et rétroaction
Pas encore d'évaluation
Dôme de Fer : Interception et rétroaction
13 pages
Épreuve Informatique CNC 2011
Pas encore d'évaluation
Épreuve Informatique CNC 2011
6 pages
Tableau de contingence et test Khi-2
Pas encore d'évaluation
Tableau de contingence et test Khi-2
18 pages
Indice de nilpotence des endomorphismes
Pas encore d'évaluation
Indice de nilpotence des endomorphismes
2 pages
Filière Génie Modélisation et Informatique
Pas encore d'évaluation
Filière Génie Modélisation et Informatique
3 pages
Tri des Fréquences et Algorithmes
Pas encore d'évaluation
Tri des Fréquences et Algorithmes
3 pages
Examen Mécanique des Fluides 2018
Pas encore d'évaluation
Examen Mécanique des Fluides 2018
2 pages
Compléments en Théorie des Ensembles
Pas encore d'évaluation
Compléments en Théorie des Ensembles
31 pages
Exercices Corrigés d'Algorithmique
Pas encore d'évaluation
Exercices Corrigés d'Algorithmique
71 pages
Énoncé Maths CNC 2020 MP
Pas encore d'évaluation
Énoncé Maths CNC 2020 MP
6 pages
Cours de Recherche Opérationnelle INF 316
Pas encore d'évaluation
Cours de Recherche Opérationnelle INF 316
33 pages
Histoire et influence de la Fed
Pas encore d'évaluation
Histoire et influence de la Fed
2 pages
Dosage Potentiométrique des Échantillons
Pas encore d'évaluation
Dosage Potentiométrique des Échantillons
1 page
Projet d'Étude Technique Électrique
Pas encore d'évaluation
Projet d'Étude Technique Électrique
58 pages
Économie marocaine : Concepts et critiques
Pas encore d'évaluation
Économie marocaine : Concepts et critiques
4 pages
Cours d'Électronique pour ESG2E Oran
Pas encore d'évaluation
Cours d'Électronique pour ESG2E Oran
136 pages
Gestion des Opérations par A. Berrado
Pas encore d'évaluation
Gestion des Opérations par A. Berrado
28 pages
Agriculture et industrialisation en Corée du Sud
Pas encore d'évaluation
Agriculture et industrialisation en Corée du Sud
16 pages
Puissance Cycliste et Résistance de l'Air
Pas encore d'évaluation
Puissance Cycliste et Résistance de l'Air
6 pages
Liaisons équivalentes en mécanique PSI/TSI
Pas encore d'évaluation
Liaisons équivalentes en mécanique PSI/TSI
8 pages
Règle du gamma en acide-base
Pas encore d'évaluation
Règle du gamma en acide-base
16 pages
Corrigé CNC 2009 Math 1 MP
Pas encore d'évaluation
Corrigé CNC 2009 Math 1 MP
7 pages
Corrigé TP1 : Initiation à Matlab
Pas encore d'évaluation
Corrigé TP1 : Initiation à Matlab
20 pages
Exercices sur les Matrices - 6C
Pas encore d'évaluation
Exercices sur les Matrices - 6C
1 page
Examen Blanc Mathématiques 2024
Pas encore d'évaluation
Examen Blanc Mathématiques 2024
3 pages
Suites numériques : majorées et convergentes
Pas encore d'évaluation
Suites numériques : majorées et convergentes
5 pages
Baccalauréat Blanc Mathématiques 2023
100% (1)
Baccalauréat Blanc Mathématiques 2023
4 pages
Épreuve de Maths - Seconde C 2009
100% (1)
Épreuve de Maths - Seconde C 2009
2 pages
Formules de Taylor et Optimisation
Pas encore d'évaluation
Formules de Taylor et Optimisation
3 pages
Mouvements de Particules Chargees: Dans Les Champs Electrique Et Magnetique
Pas encore d'évaluation
Mouvements de Particules Chargees: Dans Les Champs Electrique Et Magnetique
4 pages
Foxta v3 - Partiei Tasplaq
100% (1)
Foxta v3 - Partiei Tasplaq
174 pages
Test Signaux et Systèmes - Licence 3
Pas encore d'évaluation
Test Signaux et Systèmes - Licence 3
2 pages
Répartition Semestrielle Maths 3ème
100% (1)
Répartition Semestrielle Maths 3ème
2 pages
Tangentes et courbes paramétrées
Pas encore d'évaluation
Tangentes et courbes paramétrées
17 pages
Introduction à la géométrie plane
Pas encore d'évaluation
Introduction à la géométrie plane
252 pages
Étude des fonctions numériques 1 Bac
Pas encore d'évaluation
Étude des fonctions numériques 1 Bac
9 pages
Introduction aux équations du premier degré
Pas encore d'évaluation
Introduction aux équations du premier degré
7 pages
Arbres Syntaxiques et Automates
Pas encore d'évaluation
Arbres Syntaxiques et Automates
9 pages
Exercices de Nombres Complexes et Géométrie
Pas encore d'évaluation
Exercices de Nombres Complexes et Géométrie
2 pages
Signification de GDB et Repos en Automatique
Pas encore d'évaluation
Signification de GDB et Repos en Automatique
119 pages
Prepa Bac Maths Serie D 2026 by Tehua
Pas encore d'évaluation
Prepa Bac Maths Serie D 2026 by Tehua
22 pages
Corrigé TD3 : Équations Différentielles
Pas encore d'évaluation
Corrigé TD3 : Équations Différentielles
4 pages
Méthodes de calcul de la population future
Pas encore d'évaluation
Méthodes de calcul de la population future
15 pages
Exercices sur les Nombres Complexes
Pas encore d'évaluation
Exercices sur les Nombres Complexes
4 pages
Correction Maths Appliquées EDHEC 2023
Pas encore d'évaluation
Correction Maths Appliquées EDHEC 2023
12 pages
Introduction à la Théorie de l'Information
Pas encore d'évaluation
Introduction à la Théorie de l'Information
43 pages
Chimie appliquée : Notation et Évaluation
Pas encore d'évaluation
Chimie appliquée : Notation et Évaluation
38 pages
Méthode des arbres sémantiques en logique
Pas encore d'évaluation
Méthode des arbres sémantiques en logique
43 pages
Fractions et Produit en Croix en Maths
Pas encore d'évaluation
Fractions et Produit en Croix en Maths
9 pages
Mathématiques 6e : Fractions et Proportionalité
Pas encore d'évaluation
Mathématiques 6e : Fractions et Proportionalité
58 pages
Problèmes de Coloration en Recherche Opérationnelle
Pas encore d'évaluation
Problèmes de Coloration en Recherche Opérationnelle
31 pages
Cours sur les Équations aux Dérivées Partielles
Pas encore d'évaluation
Cours sur les Équations aux Dérivées Partielles
1 page