Opt Lin
Opt Lin
Opt Lin
1 2 3
Université de Sherbrooke
Optimisation linéaire
Jean-Pierre Dussault
27 novembre 2019
2
Optimisation linéaire1
Jean-Pierre Dussault2
27 novembre 2019
1.
Jean-Pierre
c Dussault 2019. Ce manuscrit est mis à disposition selon les termes de la Li-
cence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes
Conditions 4.0 International.
2. Professeur titulaire, département d’Informatique, Université de Sherbrooke, Sherbrooke, Ca-
nada J1K 2R1
2
Table des matières
Préface xi
Notation 1
Introduction 3
1 Modélisation 5
1.1 Premier modèle simple détaillé. . . . . . . . . . . . . . . . . . . . . 6
1.2 Modèles variés de recherche opérationnelle . . . . . . . . . . . . . . . . 10
1.2.1 Diète. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Modèle de production . . . . . . . . . . . . . . . . . . . . . 15
1.2.3 Problème de transport . . . . . . . . . . . . . . . . . . . . . 21
1.2.4 Problème d’entreposage . . . . . . . . . . . . . . . . . . . . . 24
1.2.5 Problème du barman . . . . . . . . . . . . . . . . . . . . . . 26
1.2.6 Situation plus complexe . . . . . . . . . . . . . . . . . . . . . 29
1.3 Modèles déguisés . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.1 Min-max . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.2 Normes polyédrales. . . . . . . . . . . . . . . . . . . . . . . 42
1.3.3 Modèles pour la compression d’images . . . . . . . . . . . . . . 44
1.4 Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.5 Extensions et références. . . . . . . . . . . . . . . . . . . . . . . . 45
i
ii TABLE DES MATIÈRES
3 Algorithme du simplexe 79
3.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . 80
3.2 Solutions de base réalisables . . . . . . . . . . . . . . . . . . . . . . 80
3.3 Condition d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 82
3.3.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.3.2 Équations des conditions d’optimalité . . . . . . . . . . . . . . . 84
3.4 Algorithme du simplexe. . . . . . . . . . . . . . . . . . . . . . . . 85
3.4.1 Organisation calculatoire : forme canonique d’un problème . . . . . . 86
3.4.2 Organisation calculatoire : pivots et tableaux. . . . . . . . . . . . 86
3.4.3 Organisation calculatoire : dictionnaires . . . . . . . . . . . . . . 91
3.5 Comment obtenir la première solution de base réalisable . . . . . . . . . . 92
3.5.1 Contraintes ď avec b ě 0 . . . . . . . . . . . . . . . . . . . . 92
3.5.2 Cas général . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.5.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.6 Simplexe révisé . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.7 Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.8 Extensions et références. . . . . . . . . . . . . . . . . . . . . . . . 101
3.9 Tous les exercices du chapitres . . . . . . . . . . . . . . . . . . . . . 102
4 Dualité 105
4.1 Théorie de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.1 Exemple du triangle . . . . . . . . . . . . . . . . . . . . . . 108
4.1.2 Diverses formulations de problèmes duaux . . . . . . . . . . . . . 109
4.1.3 Interprétations et conséquences du théorème de dualité . . . . . . . 112
4.1.4 Écarts complémentaires . . . . . . . . . . . . . . . . . . . . . 113
TABLE DES MATIÈRES iii
v
vi TABLE DES FIGURES
Table des algorithmes
vii
viii TABLE DES ALGORITHMES
Listings
ix
x LISTINGS
Préface
xi
xii PRÉFACE
Notation
1
2 NOTATION
Introduction
Ce texte est un document pédagogique pour introduire l’optimisation linéaire. Les sujets
sont présentés de manière élémentaire et ne nécessitent qu’une connaissance de l’algèbre
linéaire.
Dès que l’on utilise un des mots minimum, minimiser, minimal, maximal, maximum,
maximiser pour décrire une situation, il devient possible de formuler sous forme mathéma-
tique un problème d’optimisation. On parle de caractérisation ou de calcul d’un optimum,
d’une solution optimale, le terme optimum signifiant minimum ou maximum selon les cas.
La démarche permettant de décrire une situation donnée sous forme d’un problème d’opti-
misation mathématique se nomme modélisation.
Ce texte vise deux objectifs principaux : initier à la démarche de modélisation. Les mo-
dèles proviennent de plusieurs champs d’application. La recherche opérationnelle fournit une
grande variété de tels modèles.
L’autre objectif est d’étudier un algorithme célèbre, l’algorithme du simplexe, pour ré-
soudre les modèles d’optimisation linéaire. Cet algorithme fait partie de la liste des “top ten
algorithms in the twentieth century”.
En complément, nous esquisserons une autre famille d’algorithmes importants, les algo-
rithmes de points intérieurs. Ce texte d’introduction ne permet pas d’étudier ces algorithmes
en profondeur mais seulement d’en comprendre le fonctionnement sans pouvoir en étudier
les fondements. En effet, ces algorithmes relèvent d’algorithmes numériques s’appuyant sur
l’analyse mathématique vectorielle et l’analyse numérique, sujets que nous ne supposons pas
prérequis pour le présent texte.
Également en complément, nous introduirons la problématique résultant de quantités qui
doivent absolument prendre des valeurs entières et deux solutions algorithmiques simplistes
pour les résoudre.
3
4 INTRODUCTION
Chapitre 1
Modélisation
Sujets du chapitre
‚ Formalisation de modèles à partir de situations informelles.
‚ Description de modèles dans le langage AMPL.
‚ Utilisation naïve de logiciels de résolution.
5
6 MODÉLISATION
Introduction
On appelle modélisation la démarche qui considère une situation informelle et se pro-
pose de la traduire dans un langage mathématique approprié à l’obtention d’une solution
au problème sous-jacent à la situation informelle. Une partie de la démarche est de faire
abstraction d’aspects de détails au profit d’une représentation de l’essentiel de la situation.
La distinction entre l’essentiel et les détails moins pertinents relève de l’expérience.
Pour fixer les idées, nous considérons d’abord une situation informelle simple. Dans la
suite du chapitre, nous aborderons des patrons fréquents de modélisation. Ce premier chapitre
ne présuppose pas de connaissance avancée, mais tout de même un minimum d’algèbre
linéaire tel que rappelé à l’appendice A.
Situation à modéliser
Une entreprise utilise trois machines dénotées A, B, C pour fabriquer deux produits P1
et P2 . Chaque unité de P1 requiert une heure de la machine A et deux heures de la machine
B. Chaque unité de P2 requiert une heure de chacune des trois machines.
Les disponibilités mensuelles des machines A, B et C sont de 400, 600 et 300 heures respec-
tivement.
Si le profit unitaire est de 1, 50$ pour P1 et 1, 00$ pour P2 , combien l’entreprise doit-elle
fabriquer de chacun des produits pour maximiser ses profits ?
Modèle spécifique
Bien entendu, si aucune restriction n’était spécifiée, la solution serait de produire une
infinité de chacun des produits puisque le critère à optimiser (maximiser) est 32 x1 ` x2 où x1
et x2 représentent les quantités de P1 et P2 produites.
On formule trois contraintes pour représenter les restriction de disponibilité de chacune
des machines. Chaque contrainte stipule que la somme du temps requis par une machine
1.1. PREMIER MODÈLE SIMPLE DÉTAILLÉ 7
donnée pour les deux produits doit être inférieure ou égale à la disponibilité de la machine.
x1 ` x2 ď 400 (1.1)
2x1 ` x2 ď 600 (1.2)
x2 ď 300 (1.3)
On doit ajouter à nos restrictions le fait que la quantité produite e doit pas être négative, ce
qui nous amène à formuler le modèle complet suivant :
max2 1.5x1 ` x2 (1.4)
xPR
sujet à x1 ` x2 ď 400 (1.5)
2x1 ` x2 ď 600 (1.6)
x2 ď 300 (1.7)
x1 , x2 ě 0 (1.8)
La fonction qui sert de critère, ici 1.5x1 ` x2 se nomme critère, ou encore fonction objec-
tif, parfois fonction économique, également simplement “objectif”. Les autres inégalités sont
nommées contraintes. Les contraintes auraient aussi pu être des égalités, comme nous le
verrons plus tard.
Il faut faire attention, en anglais, le terme fonction objectif se traduit objective function
et c’est une faute (anglicisme) en français de dire “fonction objective”.
Les x qui satisfont à toutes les contraintes sont dits solution réalisables et l’ensemble
réalisable aussi nommé domaine réalisable est composé de toutes les solutions réalisables.
Parmi celles-ci, la solution recherchée se nomme solution optimale.
Modèle générique
Notre situation aurait fort bien pu comporter plus de deux produits, disons n. Similai-
rement, leur fabrication aurait pu nécessiter plus de trois machines, disons m. Dans ce cas,
il est commode de définir un vecteur de coûts c “ pc1 c2 . . . cn q qui regroupe tous les coûts
(profits) des n produits. Similairement, leur quantité est exprimée dans un vecteur x de n
composantes. Pour ce qui est des contraintes, nous aurons m expressions impliquant les n
quantités de produits, il est naturel de les spécifier dans une matrice m ˆ n, disons A. Enfin,
les limites de temps des machines auraient avantage à être regroupé dans un vecteur de
dimension m, disons b. Habituellement, les contraintes de non négativité sur les variables
x sont conservées telles quelles plutôt que d’être incorporées dans la matrice A. Le modèle
générique s’écrit alors comme suit.
ÿn
maxn cx “ ci x i (1.9)
xPR
i“1
sujet à Ax ď b (1.10)
x ě 0. (1.11)
8 MODÉLISATION
Pour un vecteur x ě 0 signifie que toutes ses composantes sont non-négatives, c’est-à-dire
xi ě 0, @i P t1, 2, . . . , nu. Similairement, une relation Ax ď b signifie pAxqj ď bj , @j P
t1, 2, . . . , mu.
On peut retrouver le modèle spécifique qui¨a débuté
˛ cette
¨ discussion
˛ en fixant les valeurs
` ˘ 400 1 1
appropriées n “ 2, m “ 3, c “ 1, 5 1 , b “ ˝600‚, A “ ˝2 1‚.
300 0 1
Langage de modélisation
Attardons-nous maintenant à transcrire le modèle dans un langage de modélisation,
AMPLTM ou de la version logiciel ouvert GLPK.
AMPLTM (A Mathematical Programming Language) est un langage algébrique de mo-
délisation très répandu. Ce langage peut être connecté sur des logiciels de résolution afin
d’obtenir effectivement la solution des modèles. GLPK (GNU Linear Programming toolKit)
offre l’essentiel des fonctionnalités de AMPLTM mais n’est lié à aucune contrainte commer-
ciale.
1 set machine ;
2 set produit ;
3
6 param b { machine };
7
8 param c { produit };
9
Le modèle a donc été spécifié sans tenir compte des données, c’est le modèle génériqe. Exac-
tement le même modèle pourrait servir avec cent produits et 2000 machines, les données
seulement seraient différentes. Les données se retrouvent dans le fichier suivant.
1 data ;
2
3 set machine := A B C ;
1.1. PREMIER MODÈLE SIMPLE DÉTAILLÉ 9
4 set produit := P1 P2 ;
5
8 param c := P1 1.5 P2 1;
9
10 param A : P1 P2 :=
11 A 1 1
12 B 2 1
13 C 0 1;
Maintenant, pour résoudre notre modèle, nous allons utiliser un outil en ligne de com-
mande. Avant d’examiner le résultat, tentez tout de même de résoudre le problème pour
identifier la production qui maximise les profits. Même pour un modèle jouet, cela nécessite
un peu de réflexion et d’habileté calculatoire.
4 ampl : solve ;
5 MINOS 5.51: optimal solution found .
6 2 iterations , objective 500
7 ampl : display x ;
8 x [*] :=
9 P1 200
10 P2 200
11 ;
12 ampl : quit
13 PROMPT >
On lit donc que la solution optimale est x1 “ x2 “ 200 et que la valeur de l’objectif est
500. Rappelons qu’en anglais, on dit “objective function” alors qu’en français, l’expression
correcte est “fonction objectif”.
Dans la suite du chapitre, nous allons traiter plusieurs exemples de moins en moins
simplistes. Nous utiliserons l’outil AMPL en ligne de commande pour en obtenir les solutions.
Plusieurs exercices seront proposés pour devenir efficaces dans la démarche de modélisation
de situations décrites informellement.
1.2.1 Diète
Situation à modéliser
Un éleveur dispose de trois types de grains pour nourrir ses animaux. Chaque type de
grain comporte différentes quantités de quatre éléments nutritifs. L’éleveur connaît la quan-
tité de chaque élément nutritif requis pour nourrir ses animaux ainsi que le coût au kilo de
chacun des grains, données résumées dans le tableau suivant.
L’éleveur veut déterminer la quantité de chaque grain pour constituer un mélange qui, na-
turellement, comblera tous les besoins en nutriments et ce, en minimisant le cout total.
1. https://fr.wikipedia.org/wiki/Recherche_opérationnelle
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 11
Modèle générique
La situation est déjà décrite dans une forme très proche du modèle générique. Considérons
n sortes de grains, m nutriments, Une matrice A de n colonnes et m lignes décrivant l’apport
de chaque grain à un nutriment donné, un vecteur b de besoins en nutriments et un vecteur
c de coûts des grains. Le modèle générique s’écrit alors comme suit.
min cx (1.12)
sujet à Ax ě b (1.13)
x ě 0. (1.14)
La différence avec notre premier modèle jouet est que l’objectif est ici de minimiser plutôt
que de maximiser et les contraintes sont de type “plus grand ou égal” plutôt que “plus petit
ou égal”.
On peut retrouver le modèle¨ spécifique
˛ ci-haut
¨ en fixant
˛ les valeurs appropriées n “ 3,
1250 2 3 7
` ˘ ˚ 250 ‹ ˚1 1 0‹
m “ 4, c “ 41 35 96 , b “ ˚ ˝ 900 ‚, A “ ˝ 5
‹ ˚ ‹.
3 0‚
232.5 1.5 1.2 1
Langage de modélisation
Ce modèle est tellement répandu que sa version générique fait partie des exemples de
AMPL. En fait, le modèle est un petit peu plus général car il incorpore des bornes des deux
côtés f_min ď x ď f_max et n_min ď Ax ď n_max.
1 set NUTR ;
2 set FOOD ;
3
13 var Buy { j in FOOD } >= f_min [ j ] , <= f_max [ j ]; # Buy est le x ...
14
Exercice 1.2.1 [Diète de AMPL] Adaptez les fichiers diet.mod et diet.dat aux no-
tations utilisées ci-haut, les vecteurs b et c, la matrice A. Validez votre adaptation en
résolvant les modèles à l’aide de l’outil AMPL en ligne de commande.
En ajustant les identificateurs, voici les données du modèle spécifique. Nous avons spécifié
des bornes infinies pour représenter notre modèle qui ne comporte aucune borne supérieure.
1
2 set NUTR := A B C D ;
3 set FOOD := grain1 grain2 grain3 ;
4
16 param amt :
17 grain1 grain2 grain3 :=
18 A 2 3 7
19 B 1 1 0
20 C 5 3 0
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 13
21 D 1.5 1.2 1;
La solution est :
14 PROMPT > ampl
15 ampl : model diet . mod ;
16 ampl : data dietH . dat ;
17 ampl : solve ;
18 MINOS 5.51: optimal solution found .
19 4 iterations , objective 14583.33333
20 ampl : display Buy ;
21 Buy [*] :=
22 grain1 0
23 grain2 416.667
24 grain3 0
2 set NUTR := A B1 B2 C ;
3 set FOOD := BEEF CHK FISH HAM MCH MTL SPG TUR ;
4
21 param amt ( tr ):
22 A C B1 B2 :=
23 BEEF 60 20 10 15
24 CHK 8 0 20 20
14 MODÉLISATION
25 FISH 8 10 15 10
26 HAM 40 40 35 10
27 MCH 15 35 15 15
28 MTL 70 30 15 15
29 SPG 25 50 25 15
30 TUR 60 20 15 10 ;
et sa solution
Les quantités bizarres de MTL et SPG sont dûes à des erreurs d’arrondi dans les calculs
numériques. Les ordinateurs calculent en général avec environ 16 décimales de précision et
des quantités de l’ordre de 10´15 sont en fait des 0 pollués d’erreurs d’arrondi. Donc, la
diète optimale ne comporte que des MCH (“Mac & Cheese”). Remarquons que dans les
deux exemples, la diète optimale ne comporte qu’un seul aliment. On pourrait qualifier
cette solution d’extrême. Le premier à s’intéresser à un tel modèle de diète fut Stigler [5].
Sa liste d’aliments comportait 77 items et il avait minimisé le coût d’alimentation annuelle
d’un homme de corpulence moyenne en assurant de combler ses besoins nutritionnels décrits
par les neuf nutriments calories, protéines, calcium, fer, vitamine A, thiamine, riboflavine,
niacine et acide ascorbique. Stigler a effectué son étude avant l’invention de l’algorithme du
simplexe, aussi avait-il utilisé des calculs intuitifs pour estimer le coût minimal de 39.93$.
Vous avez le modèle AMPL, la solution optimale est la suivante :
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 15
Modèle générique
Ce modèle est très semblable à notre premier modèle que nous avions détaillé. Profitons
en pour introduire un peu de terminologie.
16 MODÉLISATION
Objectif Tout d’abord, il nous faut établir quelle est la fonction objectif. Ce n’est pas
mentionné explicitement, on dit simplement “obtenir le programme optimal de fabrication”.
Doit-on réduire les coûts ? Non, car une valeur budgétaire sur les coûts a été pré-approuvée.
On doit donc maximiser les recettes de vente. Ceci dit, même si les coûts (main d’œuvre et
matière première) ont été pré-approuvés, il n’est pas certain que la meilleure solution utilise
la totalité du budget pré-approuvé. S’il reste du budget, ce sera encore mieux. On arrive
donc à une fonction objectif qui calcule les recettes et qui en déduit les coûts effectifs.
On pourrait imaginer que le décideur souhaite épuiser le budget pré-approuvé. On pour-
rait également imaginer que peu importe ce qui n’est pas dépensé du budget pré-approuvé,
seuls les revenus de vente doivent être maximisés. Nous avons opté pour l’interprétation qui
maximise les revenus de vente desquels on déduit les dépenses sans dépasser les montants
pré-approuvés.
Variables de décision Maintenant, sur quoi avons-nous le contrôle pour atteindre notre
objectif ? Ces quantités, dans notre exemple les quantités produites de chacun des produits,
sont nommées variable de décision. Les variables de décision sont au nombre de n “ 3 dans
notre exemple comportant la production de trois produits. Il est à noter que ces variables de
décision ne doivent pas être négatives, impliquant une borne de non-négativité. De plus, on
apprend qu’il faut produire au moins 4 000 items de P3 , donc les bornes inférieures sont soit
zéro, soit la quantité spécifiée.
Contraintes En plus des bornes notre situation fait état de limites sur l’utilisation de res-
sources. Quelles sont donc les ressources dont nous avons besoin pour réaliser la production ?
Il s’agit de temps sur m1 “ 3 machines, de limite de m2 “ 2 types de coûts :
1. de main d’œuvre
2. de matières premières.
Ceci totalise m “ m1 ` m2 “ 5 contraintes dans l’exemple.
AMPL
Examinons directement une formulation AMPL du modèle générique.
1 set machine ; # 3 machines dans notre exemple spécifique
2 set produit ; # 3 produits dans notre exemple spécifique
3
18 maximize profit_total :
19 sum { j in produit }( prix [ j ] - sum { i in frais } fp [i , j ])* qte [ j ];
20
21 subject to
22 tempsTot { i in machine }:
23 sum { j in produit } temps [i , j ] * qte [ j ] <= tdisponible [ i ];
24 depense { i in frais }:
25 sum { j in produit } fp [i , j ] * qte [ j ] <= budget [ i ];
Il suffit maintenant de préciser les valeurs du modèle spécifique dans le fichier approprié.
1 set machine := M1 M2 M3 ;
2 set produit := P1 P2 P3 ;
3
6 param temps : P1 P2 P3 :=
7 M1 2 4 3
8 M2 3 6 0
9 M3 1 3 2;
10
11 param fp : P1 P2 P3 :=
12 MOeuvre 0.25 0.50 0.25
13 Mpremiere 2.00 2.50 2.25;
14
15 param prix :=
16 P1 10.75
17 P2 15.00
18 P3 10.00;
19
20 param qmin :=
21 P1 0.0
22 P2 0.0
23 P3 4000.0;
18 MODÉLISATION
24
25 param budget :=
26 MOeuvre 10000
27 Mpremiere 80000;
28
29 param tdisponible :=
30 M1 90000
31 M2 84000
32 M3 52000;
On spécifie dans un fichier les commandes pour résoudre le modèle, ici le fichier ex1.2.cmd.
Solution entière
Cette solution n’est pas complètement satisfaisante ; en effet, la quantité optimale de P3
n’est pas entière. Pour un tel modèle jouet, on peut imaginer “arrondir” la solution, par
exemple produire 10 667 de P3 . Cependant, ce n’est pas mathématiquement rigoureux. Les
techniques pour aborder cette restriction supplémentaire que la solution doit être entière
seront survolées à la section 7.3.
On peut spécifier dans le modèle AMPL que la solution doit être entière. Remarquez que
l’unique différence est l’ajout du mot clef integer à la ligne de définition de la variable qte,
ligne 16 dans le listing suivant.
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 19
18 maximize profit_total :
19 sum { j in produit }( prix [ j ] - sum { i in frais } fp [i , j ])* qte [ j ];
20
21 subject to
22 tempsTot { i in machine }:
23 sum { j in produit } temps [i , j ] * qte [ j ] <= tdisponible [ i ];
24 depense { i in frais }:
25 sum { j in produit } fp [i , j ] * qte [ j ] <= budget [ i ];
On doit alors utiliser un logiciel de résolution capable de traiter ces nouveaux problèmes.
MINOS, le logiciel que AMPL utilise par défaut n’en est pas capable. Nous allons utiliser
“gurobi”.
1 model ex1 .2 bInt . mod ;
2 data ex1 .2 b . dat ;
3 option solver ’/ home / dussault / import / amplide . linux64 / gurobi ’;
4 solve ;
5 display qte ;
Listing 1.12 – Instructions pour résoudre le modèle avec solution entière; fichier: AM-
PL/ex1.2Int.cmd
Remarquons que tel que décrit dans la documentation, la matrice produite est la transpo-
sée de la matrice des contraintes dans une représentation de matrices creuses. full(At)
la converti dans le format usuel pour lecture par un humain.
On peut aussi voir le vecteur de coûts résultant de l’escompte des budgets pré-approuvés.
Ce vecteur est un vecteur colonne, sa transposée est la ligne.
10 -->c ’
11 c’ =
12 8.5 12. 7.5
B1 B2 B3 disponibilité
A1 1 4 9 200
A2 6 8 4 500
demande 200 400 100 700
22 MODÉLISATION
On désire déterminer quelle quantité chaque client reçoit de chaque entrepôt pour minimiser
le coût total de transport tout en satisfaisant les demandes. Remarquons que ce modèle
simpliste équilibre la quantité totale entreposée avec la demande totale des clients.
Modèle générique
Cette situation est tellement répandue que l’on peut trouver une solution AMPL parmis
les exemples de la documentation de AMPL.
On nomme habituellement origine les points de départ du transport, les entrepôts dans
notre exemple et destination les points d’arrivées, les clients de notre exemple. Il est avan-
tageux d’utiliser deux indices pour les variables de décision, xi,j qui représente la quantité
transportée de l’origine i vers la destination j. De même les coûts ci,j comportent deux in-
dices. On considère n1 origines et n2 destinations. On ajoute un vecteur de demande d P Rn1
et un vecteur de disponibilité b P Rn2 et le modèle complet s’écrit comme suit.
n1 ÿ
ÿ n2
min
n ˆn
cx “ ci,j xi,j (1.15)
xPR 1 2
i“1 j“1
n1
ÿ
sujet à xi,j “ dj , @j P t1 : n2 u (1.16)
i“1
ÿn2
xi,j “ bi , @i P t1 : n1 u (1.17)
j“1
x ě 0. (1.18)
AMPL
Ce modèle classique est un des exemple de AMPL.
1 set ORIG ; # origins
2 set DEST ; # destinations
3
12 minimize total_cost :
13 sum { i in ORIG , j in DEST } cost [i , j ] * Trans [i , j ];
14
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 23
Pour notre situation, il suffit de spécifier les données. Remarquons que les variables du modèle
sont nommées Trans plutôt que x, x Ø Trans.
1
2 param : ORIG : supply := # defines set " ORIG " and param " supply "
3 A1 200
4 A2 500;
5
6 param : DEST : demand := # defines " DEST " and " demand "
7 B1 200
8 B2 400
9 B3 100 ;
10
11 param cost :
12 B1 B2 B3 :=
13 A1 1 4 9
14 A2 6 8 4 ;
Modèle générique
On peut formuler directement le modèle pour un nombre de périodes arbitraire, disons
n. Quelles sont nos variables de décision ? Pour chaque période i P t1 : nu, les quantités
à entreposer ei , à acheter ai et à vendre vi . On a également une quantité initiale imposée,
nommons la e0 . Nous sommes en présence d’un modèle dynamique qui décrit ei “ ei´1 `ai ´vi ,
en mots, la quantité entreposée à la période i est celle entreposée à la période précédente
à laquelle on ajoute la quantité achetée à la période courante et de laquelle on retranche
la quantité vendue à la période courante. Par exemple, à la première période, la quantité
entreposée e1 est cette quantité imposée e0 “ 30 moins ce qu’on a vendu v1 plus ce qu’on a
acheté a1 .
Qu’est-ce que ces quantités changent à notre profit ? À la période i, on vend vi avec profit
ci mais on achète ai au coût ci , pour un bénéfice net ci pvi ´ ai q. Également, on doit payer
ei d’entreposage. Généralisons et nommons les frais d’entreposage fi , dans notre cas, fi “ 1.
Nous pouvons donc formuler le modèle complet. Les coût d’entreposage à la période “0” ne
font pas partie du modèle car nous n’avons aucune décision à prendre à leur sujet.
n
ÿ
max cpv ´ aq ´ f e “ pci pvi ´ ai q ´ fi ei q (1.19)
a,v,ePRn
i“1
sujet à ei “ ei´1 ` ai ´ vi , @i P t1 : nu (1.20)
e ď 60, (1.21)
e, a, v ě 0. (1.22)
Une simplification Remarquons que les variables a (achats) et v (ventes) sont toujours
utilisées ensemble selon la formule a ´ v. On pourrait définir une variable t (transaction)
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 25
telle que ti représente la quantité transigée à la période i, si positive, il s’agit d’une vente et
autrement, d’un achat. Donc, dans les faits, ti “ vi ´ ai et on peut reformuler notre modèle
comme suit, la variable t est libre, c’est-à-dire d’est pas contrainte à être positive.
n
ÿ
maxn ct ´ f e “ pci ti ´ fi ei q (1.23)
t,ePR
i“1
sujet à ei “ ei´1 ` ti , @i P t1 : nu (1.24)
e ď 60, (1.25)
e ě 0. (1.26)
AMPL
1 param N >0;
2
Pour notre situation, il suffit de spécifier les données. Remarquons que la capacité de l’en-
trepôt est représentée par le paramètre Cap.
1 param N := 3;
2
5 param c := 1 4
6 2 9
7 3 6;
26 MODÉLISATION
9 param f := 1 1
10 2 1
11 3 1;
12 maximize profit_total :
13 sum { j in recette } prix [ j ]* qte [ j ];
14
15 subject to
16 Réserve { i in alcool }:
17 sum { j in recette } ingredient [j , i ] * qte [ j ] <= qdisponible [ i ];
Maintenant, observons que les recettes ne spécifient pas la sorte de whisky, donc on peut
considérer un seul alcool de type whisky W dont on a deux litres, un litre de Ve et deux litres
de Gi. Les unités du modèle sont des millilitres et notre instance donne les données suivantes.
1 set alcool := W Ve Gi ;
2 set recette := WS Man Mar Sp ;
3
4 param ingredient : W Ve Gi :=
5 WS 30 0 0
6 Man 30 15 0
28 MODÉLISATION
7 Mar 0 15 30
8 Sp 30 0 30 ;
9
10 param prix :=
11 WS 7
12 Man 10
13 Mar 10
14 Sp 14;
15
16 param qdisponible :=
17 W 2000
18 Ve 1000
19 Gi 2000;
Nous connaissons maintenant deux logiciels, Minos et Gurobi pour résoudre notre modèle.
Voyons voir ce que ça donne.
1 MINOS 5.51: optimal solution found .
2 3 iterations , objective 1133.333333
3 qte [*] :=
4 Man 33.3333
5 Mar 33.3333
6 Sp 33.3333
7 WS 0
Ah, une autre solution, toujours fractionnaire, mais avec le même profit total. De plus, on
observe dans les deux solutions que au moins une recette n’est pas du tout produite. Ça n’a
pas de sens, on ne peut pas dire qu’il ne reste plus de Manhattan dès le début de la soirée !
Imposons donc que les solutions soient des entiers, et qu’au moins qmin = 10 de chacune
des recettes soit produite. Cette fois, nous devons utiliser Gurobi.
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 29
Exercice 1.2.3 [Solution entière avec seuil minimum] Modifiez le code barman1.mod et
barman1.dat pour incorporer les changements de spécifier des solutions entières avec au
moins qmin de chacune des recettes
Modèle spécifique
1. Variables de décision
30 MODÉLISATION
2. Contraintes
(a) non-négativité des variables :
x, y ě 0;
(b) budget :
700x4 ` 8x5 ď 30000;
(c) disponibilité des homme–heures pour l’hiver :
10x1 ` 35x2 ` 15x3 ` 100x4 ` 5x5 ď 3500;
3. Fonction objectif
Z “ 250x1 ` 550x2 ` 375x3 ` 800x4 ` 5x5 ` 4y1 ` 4.5y2 .
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 31
Exercice 1.2.5 [Production de café] Une compagnie dispose de 1000 kg de café Africain,
2000 kg de café Brésilien et 500 kg de café Colombien. Elle met en sachet (de 1 kg) deux
sortes de café : la 1ère sorte est un mélange à parties égales de café africain et brésilien et
se vend 16$ le kg. La 2e sorte est un mélange de trois parties de café brésilien pour une
partie de café colombien et se vend 19$ le kg.
Quelle quantité de chaque sorte de café la compagnie devrait-elle ensacher pour maximiser
son profit ?
coût unitaire de
Usine Coût unitaire Capacité
transport E1 E2 E3
U1 17$ 42 unités
U1 1 1 2
U2 15$ 37 unités
U2 1 2 4
l’entreprise est :
Un policier prend son service une fois par jour, et travaille 8 heures d’affilée. Les heures
de prise de service sont 0h, 4h, 8h, 12h, 16h et 20h.
a) Formulez le problème de déterminer le nombre de policiers minimal que la municipalité
doit embaucher pour satisfaire à ses besoins.
b) Supposons maintenant que tout policier peut se voir exiger d’effectuer, immédiatement
après ses 8 heures normales, un bloc de 4 heures de temps supplémentaire à temps
et demie. Formulez cette variante avec objectif de minimiser les salaires versés par la
municipalité.
c) Supposons maintenant que nous traitons la situation extrêmement simplifiée suivante
de planification pour une semaine : chaque policier prend son service 7 jours sur 7 à la
même heure, mais une contrainte oblige un policier à faire du temps supplémentaire un
jour sur trois au maximum. Formulez cette variante, toujours en minimisant les salaires
versés. On suppose que les besoins par tranche d’heure sont les mêmes à chaque jour de
la semaine.
Centre I Centre II
P1 3 2
P2 4 3
P3 2 5
Les trois produits sont fabriqués avec les mêmes matières premières mais la quantité requise
pour chaque produit est différente :
Quantité en unités
P1 8
P2 10
P3 12
Les matières premières coûtent $2 l’unité ; la main d’oeuvre est rémunérée au taux de $4
l’heure. De plus, chaque produit doit assumer une partie des frais d’administration ; chaque
unité (d’un produit) exige un nombre fixe d’heures d’administration égales à la somme du
nombre d’heures exigées par la main–d’oeuvre pour la fabriquer. Les coûts d’administration
sont évalués à $1 l’heure pour chaque produit. Les prix de vente sont de $60 l’unité pour P1 ,
$70 l’unité pour P2 et $75 l’unité pour P3 . Les disponibilités concernant la main d’oeuvre
sont de 2 500 heures pour le Centre I et de 3 000 heures pour le Centre II. De plus, la
quantité des matières premières est limitée à 2 000 unités et le nombre d’heures allouées à
l’administration ne doit pas excéder 5 000 heures.
On demande de formuler le programme linéaire qui permettrait d’obtenir le programme
de fabrication qui maximise le profit total.
Exercice 1.2.12 [Problème des skis] Une entreprise décide de se lancer dans la fabri-
cation de skis. D’après l’analyse du marché, plusieurs modèles de skis sont actuellement
en demande, entre autres, des skis de ran–donnée (plaisir et compétition ) et des skis al-
pins (plaisir et compétition ). La part du marché que l’entreprise pense atteindre serait
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 35
d’environ 15 000 paires de skis par année avec la répartition maximale suivante :
Modèles Paires
Ml : randonnée–plaisir 6 000
M2 : randonnée–compétition 2 500
M3 : alpin–plaisir 4 500
M4 : alpin–compétition 2 000
La fabrication de ces skis comporte principalement les phases suivantes : menuiserie, pein-
ture et pose de l’attelage. Le tableau suivant indique les temps requis, en minutes, par
paire, pour ces différentes phases :
Les prix de vente, par paire sont : 60 $ pour M1 , 75 $ pour M2 , 285 $ pour M3 et 100 $ pour
M4 . L’entreprise désire connaître les quantités de chaque modèle qu’elle doit fabriquer de
façon à maximiser ses bénéfices. Formuler le modèle linéaire associé à ce problème.
Exercice 1.2.13 [Aide humanitaire] L’Agence Internationale, F.A.O. (Food and Agri-
culture Organization) a décidé d’envoyer des experts en agriculture dans deux pays en voie
de développement. Le besoin le plus urgent de ces deux pays étant l’accroissement de leur
production alimentaire qui peut se faire en améliorant les techniques agricoles utilisées.
36 MODÉLISATION
Aussi, le rôle des experts consiste à développer un certains nombre de projets pilotes 0
de nouvelles techniques sont mises en pratique. Cependant, le nombre de tels projets est
déterminé par les disponibilités de trois ressources : l’équipement, les experts, l’enveloppe
budgétaire. La question qui se pose est la suivante : Combien de projets peut-on réaliser
dans chacun des deux pays de façon à utiliser le mieux possible les ressources disponibles.
On a estimé qu’un projet réalisé dans le pays 1 permettra d’augmenter suffisamment la
production pour nourrir 2 000 personnes additionnelles. De même un projet réalisé dans
le pays 2 permettra de nourrir 3 000 personnes additionnelles. Seulement, les ressources
nécessaires pour chaque projet différent d’un pays à l’autre. Les données pour chaque pays
sont résumées dans le tableau suivant :
quantité nécessaire par projet
Ressources pays 1 pays 2 disponibilité totale
Équipement 0 5 20
Experts 1 2 10
Budget $60 000 $20 000 $300 000
étant donné que la situation est dramatique pour les deux pays, la FAO a décidé d’ac-
croître la production le plus possible dans les deux pays. Ainsi, elle a opté pour maximiser
l’accroissement minimum de la production alimentaire dans les deux pays.
Formuler le problème comme un modèle d’optimisation linéaire.
Exercice 1.2.14 [Diète animale] Une société produit de la nourriture pour chiens et
chats. La demande hebdomadaire est d’au moins 600 livres pour les chiens et 250 livres pour
les chats. La nourriture produite pour chaque type d’animal doit contenir un pourcentage
minimal de quatre éléments nutritionnels A, B, C et D, comme l’indique le tableau ci-
dessous.
% minimal d’élément nutritionnel
A B C D
nourriture pour chiens 10 5 8 8
nourriture pour chats 8 16 5 12
La société dispose de six sortes de viande qu’elle peut combiner pour produire les deux types
de nourriture. La disponibilité, le coût et le pourcentage de chaque élément nutritionnel
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 37
contenu dans chaque sorte de viande sont résumés dans le tableau suivant :
La société désire connaitre la quantité de chaque sorte de viande qui compose chaque type
de nourriture (nourriture pour chien et nourriture pour chat) afin de minimiser ses coûts.
Modéliser le problème (on prendra soin de bien définir les variables, la fonction économique
et de donner la signification de chaque contrainte).
Exercice 1.2.15 [Excédent de production] Une firme a trois filiales ayant chacune un
excédent de capacité de production. La direction a décidé d’utiliser une partie de cet excé-
dent à la fabrication d’un nouveau produit de la façon suivante. Le produit peut être fait
en trois formats : grand, moyen et petit, qui donne un profit net unitaire de 12, 10 et 9$
respectivement.
Les filiales 1, 2 et 3 disposent d’un excédent d’heure–hommes et d’heure–machines pour
produire respectivement 500, 600 et 300 unités par jour de ce produit sans égard au format
ou à la combinaison de formats impliqués. Cependant l’espace d’entreposage dis- ponible
impose également une certaine limite sur le taux de production ; les filiales 1, 2 et 3 ayant 9
000, 8 000 et 3 500 pieds carrés d’espace d’entreposage disponible pour ce produit. Chaque
unité du grand format, du moyen format et du petit format, produite par jour, nécessite
20, 15 et 12 pieds carrés respectivement. La prévision des ventes indique que 600, 800 et
500 unités du grand, moyen et petit formats peuvent être vendues par jours.
Afin de maintenir une charge de travail uniforme entre les filiales et pour conserver une cer-
taine flexibilité, la direction a décidé que toute production additionnelle assignée à chaque
filiale doit utiliser le même poucentage d’excédent d’heure–hommes et d’heure–machines.
La direction désire connaître le nombre de chacun des formats devant être produit par
chaque filiale de façon à maximiser les profits.
Proposez à la direction un modèle qui pourrait lui permettre d’atteindre ses objectifs.
38 MODÉLISATION
Exercice 1.2.16 [Problème des hôtesses de l’air] M. Duvol est en charge de la formation
des hôtesses de l’air de la compagnie aérienne Air Voyage. La compagnie estime que
ses besoins en heures de vol d’hôtesses de l’air pour les a cinq prochains mois sont les
suivants : 8 000 heures en décembre, 9 000 en janvier, 8 000 en février, 10 050 en mars et
9 000 en avril. Au début du mois de décembre, soixante hôtesses de l’air sont employées
par Air Voyage. Chaque hôtesse de l’air peut travailler jusqu’à 150 heures par mois. Si
les besoins pendant un mois donné sont inférieurs au nombre maximum d’heures de vol
disponibles, chaque employée travaille moins d’heures pendant le mois et personne n’est
mis à pieds. L’expérience de la compagnie montre qu’en général a la fin du mois 10% des
hôtesses quittent Air Voyage. La compagnie peut engager du personnel, mais une nouvelle
employée doit suivre un stage de formation d’un mois avant qu’elle ne puisse devenir hô-
tesse de l’air. 80% des stagiaires réussissent la période de formation et deviennent hôtesses.
Exercice 1.2.17 [Problème des radios] Une entreprise d’électronique s’est engagée à faire
la livraison de 20 000 radios au cours des 4 prochaines semaines. Le client paiera
‚ 20$ chaque radio livrée à la fin de la première semaine,
‚ 18$ chaque radio livrée à la fin de la deuxième semaine,
‚ 16$ chaque radio livrée à la fin de la troisième semaine,
‚ 14$ chaque radio livrée à la fin de la quatrième semaine.
L’entreprise ne dispose que de 40 travailleurs, chacun capable de produire 50 radios par
semaine. Elle est donc dans l’obligation d’engager et d’entraîner des sumuméraires. N’im-
porte quel travailleur expérimenté (régulier ou sumuméraire) peut participer a la formation
de nouveaux sumuméraires. Après une semaine de formation chaque stagiaire devient soit
travailleur à la chaîne de production, soit entraîneur de nouveaux stagiaires. Un travailleur–
entraîneur peut assumer la formation de 3 stagiaires à la fois.
Puisque l’entreprise n’a qu’un contrat, il se peut que des travailleurs deviennent non pro-
ductifs une fois la livraison complétée. Tous les employés, réguliers ou surnuméraires,
doivent rester à l’emploi de la compagnie jusqu’à la fin de la quatrième semaine. Le salaire
hebdomadaire d’un travailleur, en production ou comme entraîneur, est 200$. Le salaire
hebdomadaire d’un stagiaire et de 100$. Les coûts de production, excluant les salaires,
1.2. MODÈLES VARIÉS DE RECHERCHE OPÉRATIONNELLE 39
1.3.1 Min-max
Un cas typique de minimiser une fonction qui n’est pas linéaire est de minimiser le
maximum de deux fonctions affines. Par exemple, f pxq “ maxp1 ´ 2x, x ` 1q. Il n’est pas
difficile de se convaincre que le minimum de f pxq est atteint en x “ 0 et la valeur f p0q “ 1.
Or, 1 ´ 2x et x ` 1 sont des fonctions affines, c’est-à-dire des fonctions linéaires plus un terme
constant. On peut transformer le problème min f pxq sous une forme d’optimisation linéaire.
En effet, il suffit d’utiliser une variable de plus, disons u et de restreindre u à à la fois plus
grande ou égale aux deux fonctions affines et ensuite de minimiser u. On se retrouve donc
avec le problème d’optimisation linéaire suivant qui comporte deux variables.
min u (1.29)
u,x
sujet à u ě maxp1 ´ 2x, x ` 1q. (1.30)
On ne semble pas avoir gagné grand chose puisque le “max” est encore là. Maintenant, une
contrainte plus grande ou égale au max de quantités peut se récrire comme plus grande ou
1.3. MODÈLES DÉGUISÉS 41
Si l’on retrouve un minimum de quantités dans les contraintes, il est possible de les trans-
former en contraintes linéaires
# +
u ď a1
u ď minpa1 , a2 q ðñ (1.31)
u ď a2 .
Remarquons que x peut être un vecteur de dimension arbitraire, pas forcément un scalaire.
Ici encore, les signes sont super importants, pas question de considérer “moins” un max, ni
un max de max...
Valeur absolue
Si une expression comporte un terme de valeur absolue, observons que
Norme `8 Une généralisation de la valeur absolue pour des vecteurs ~x P Rn est la suivante :
}~x}8 “ maxi“1,2,...,n |xi |. Vérifions qu’il s’agit bien d’une norme.
1. }~0}8 “ maxi“1,2,...,n |0| “ 0 ;
2. }α~x}8 “ maxi“1,2,...,n |αxi | “ |α| maxi“1,2,...,n |xi | “ |α|}~x}8 ;
3. }~x ` ~y }8 “ maxi“1,2,...,n |xi ` yi | ď maxi“1,2,...,n p|xi | ` |yi |q ď }~x}8 ` }~y }8 .
Nous avons déjà vu comment exprimer |x| “ maxpx, ´xq de sorte que }x}8 “ maxi maxpxi , ´xi q.
Nous savons déjà comment convertir un problème du type min }x}8 par l’astuce d’ajouter
une variable u et de la contraindre à être plus grande ou égale à tous les termes du max.
ř
Norme `1 La norme dite `1 s’écrit }~x}1 “ i |xi |. Vérifions qu’il s’agit bien d’une norme.
1. }~0}1 “ i |0| “ 0 ;
ř
ř ř ř
2. }α~x}1 “ i |αxi | “ i |α||xi | “ |α| i |xi | “ |α|}~x}1 ;
ř ř ř ř
3. }~x ` ~y }1 “ i |xi ` yi | ď i p|xi | ` |yi |q “ i |xi | ` i |yi | “ }~x}1 ` }~y }1 .
Nous avons déjà vu comment transformer un objectif d’une somme de max, la transformation
peut s’appliquer ici.
1.3. MODÈLES DÉGUISÉS 43
Exercice 1.3.1 [Ajustement aux données] Dans cet exercice, nous explorons un problème
d’ajustement de fonction. Les valeurs suivantes de x et y sont données :
x 0 1 2 3
y 0 0 3 9
est différent de logpNi q (réalité, logarithme du véritable nombre d’itérations pour le iième
problème). Nous voulons maintenant trouver des valeurs de α et β qui minimisent, dans
un certain sens, les erreurs de prédiction du modèle. On peut formuler cette minimisation
de plusieurs manières ; voici deux suggestions :
‚ minimiser la somme des valeurs absolues des différences entre les logpNi q et les logpTi q ;
c’est minimiser la somme des erreurs de la prédiction ;
n
ÿ
min | logpNi q ´ pα logp2q ` β logpmi ` ni qq|;
α,β
i“1
‚ minimiser le maximum sur les valeurs absolues des différences entre les logpNi q et les
logpTi q ; c’est minimiser la pire des erreurs de la prédiction ;
´ ¯
min max t| logpNi q ´ pα logp2q ` β logpmi ` ni qq|u .
α,β 1ďiďn
Formulez ces deux problèmes de minimisation sous la forme d’un modèle d’optimisation
linéaire.
Exercice 1.3.3 [PL équivalent] Considérez le problème minx }Ax ´ y}1 . Reformulez-le
sous la forme d’un modèle d’optimisation linéaire.
Si l’on suppose que A P Rmˆn avec m ą n, on peut constituer une matrice Z P Rpm´nqˆm
def
dont les lignes forment une base du noyau à gauche de A défini comme kerg A “ tz : zA “ 0u,
donc ZA “ 0. Par conséquent, ỹ “ Zy “ ZpAx ` eq “ Ze. Après analyse, on en arrive à la
formulation suivante, connue en anglais sous le nom basis pursuit.
min }e}1
e
(1.33)
sujet à Ze “ ỹ
Exercice 1.3.4 [PL équivalent] Considérez le problème minZe“ỹ }e}1 . Reformulez-le sous
la forme d’un modèle d’optimisation linéaire.
1.4 Résumé
La modélisation consiste en la traduction et adaptation d’une situation concrète plus
ou moins formelle en un ensemble de relations mathématiques propices à l’obtention d’une
solution. Nous avons examiné plusieurs exemples de situations et leur modélisation
Sujets du chapitre
‚ Observations sur la géométrie du problème.
‚ Formulations standard.
‚ Quelques propriétés théoriques.
47
48 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Introduction
L’optimisation, aussi nommée programmation, linéaire constitue l’origine de l’optimisa-
tion mathématique moderne. Son étude a été menée par George Bernard Dantzig à partir de
1947. L’algorithme du simplexe, que nous présentons dans ce chapitre, est considéré comme
un des dix algorithmes les plus importants du vingtième siècle. C’est la première fois qu’un
problème avec contraintes d’inégalité a été résolu formellement.
Dans ce chapitre, nous abordons l’étude directe des problèmes de minimisation de fonc-
tions linéaires dans un domaine défini par des contraintes linéaires. Par une suite d’observa-
tions de nature géométriques ou encore algébriques, nous déduirons des propriétés élémen-
taires des problèmes.
ÝÝÑ
4.5
Le vecteur AB “ p3, 2q
C
définit des droites per-
4
pendiculaires d’équation
3.5
3x ` 2y “ constante. On
F
3 voit les droites de constantes
2.5
2, 4, 6, 8, 10.
2
E H B Si le vecteur définit une
fonction objectif, celle-ci
1.5
peut augmenter à l’infini
D
1
dans la direction du vecteur
0.5 et diminuer à moins l’infini
A I dans la direction opposée.
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
-0.5
2 4 6 8 10
-1
Observons que la fonction objectif linéaire n’est pas bornée par elle même, sauf dans le cas
de la fonction triviale. Similairement, si toutes les contraintes sont des égalités, la fonction
objectif ne sera pas bornée à moins d’être constante sur le domaine réalisable qui est alors un
sous-espace affine. Donc, pour qu’un modèle d’optimisation linéaire soit intéressant, il faut
qu’il comporte des contraintes d’inégalité.
Un contrainte d’inégalité qui s’écrit a1 x1 `a2 x2 ď b décrit un demi-plan, plus généralement
un demi-espace. La frontière du demi-espace est la droite d’équation a1 x1 ` a2 x2 “ b. Dans
ce cas d’une contrainte plus petit ou égal, le demi-espace est situé sur le côté opposé à
l’orientation du vecteur a. Pour une contrainte plus grand ou égal, le demi-espace serait situé
sur le côté correspondant à l’orientation du vecteur a. Sur la figure 2.1, si une droite définit
une contrainte ě, on voit que la région sera un demi-plan qui s’éloigne dans la direction
du vecteur alors qu’une contrainte ď définit un demi-plan qui s’éloigne dans la direction
opposée au vecteur. Le domaine réalisable est constitué de l’intersection de tous les demi-
espaces décrits par chacune des contraintes.
Reprenons les contraintes (1.5) – (1.8).
x1 ` x2 ď 400
2x1 ` x2 ď 600
x2 ď 300
x1 , x2 ě 0
Il s’agit bien d’une intersection de cinq demi-plans dont deux qui définissent le quadrant
50 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
positif.
Le petit exemple suggère que la solution optimale (le point le plus élevé dans le plan
décrivant la fonction objectif) sera toujours un sommet du polygone des contraintes. En fait,
on peut imaginer une situation particulière où une arête entière est optimale, mais dans ce
cas, chacune de ses extrémités est un sommet.
qui n’est qu’une mise à l’échelle du problème de la section 1.1. On superpose les contraintes
aux droites de la figure 2.1. Ces droites sont les lignes de niveau constant de la fonction
objectif, qui était illustrée par un plan sur la figure 2.3. On voit également que si l’objectif
avait été de minimiser, en suivant les droites de niveau constant dans la direction opposée,
on aurait abouti à l’origine.
pentagone de l’exemple de F G
3
E H B
le point qui correspondait à 2
en utilisant Ampl. 1
D
0.5
A I
-3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
-0.5
2 4 6 8 10
-1
Lorsque les lignes de niveau constant de l’opjectif sont parallèles à une face des contraintes,
toute la face aura la même valeur de fonction objectif.
i f g h
On voit l’ensemble des solu-
6
E tions qui maximise 4x1 `2x2
est composée de tout le seg-
5
ment rp2, 2qt , p3, 0qt s.
D
4
F
3
f1
C H
G B
2
g1
u
1 h1
A i1 I
-4 -3 -2 -1 0 1 2 3 4 5 6
0
4 8 12
Le petit exemple définissait un domaine réalisable borné, un pentagone. Par contre, les
modèles de diète comportent un domaine réalisable qui n’est pas borné : en effet, si on inclus
une quantité arbitrairement grande de tous les aliments dans une diète, les besoins seront
certainement satisfaits. La fonction objectif sera également arbitrairement grande, ce qui
fait que le modèle est bien défini puisqu’on minimise l’objectif, qui évitera donc les solutions
arbitrairement grandes.
Mathématiquement, il est concevable que la fonction objectif puisse croître arbitraire-
ment, et donc que la valeur de la fonction objectif ne soit pas bornée. En général, une telle
situation découlerait d’une erreur de modélisation.
54 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
x1 ě 0 et x2 ě 0, ce qui fait 5
J
j
que la solution du problème 4.5
de maximisation ne change K
4
I
ment, ´8. 2
C H
1.5
1
u
c
0.5
G D
-4.5 -4 -3.5 -3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
-0.5
-4 -1 0 8 10
Vous avez constaté à l’exercice 1.2.2 que le fait d’obliger à utiliser l’entièreté du budget
conduisait au diagnostic que le problème est irréalisable. C’est que les contraintes ainsi
modifiées ne sont pas compatibles, il n’existe aucun point satisfaisant à toutes les contraintes.
2.2. RÉSULTAT DE LA RÉSOLUTION D’UN MODÈLE D’OPTIMISATION LINÉAIRE55
5
J
Ajoutons à notre exemple
4.5 trois contraintes, ´2x1 ´
4
C 2x2 ď ´11, 2x1 ď 7 et x2 ď
3.5
3. On voit qu’aucun point
F G L M
n’appartient aux contraintes
3
formés de l’intersection du
2.5
E H B K
pentagone et du triangle. On
2
dit alors que le problème
1.5
n’est pas réalisable. Dans ce
D
1 cas, par convention, on dira
0.5 que la valeur optimale est
-3 -2.5 -2 -1.5 -1 -0.5 0
A
0.5 1 1.5 2 2.5
I
3 3.5 4 4.5 5 5.5
´8 pour un problème de
-0.5
maximisation et `8 dans le
-1
2 4 6 8 10 cas de minimisation.
max x1 ` 2x2
sujet à x1 ` x2 ď 2
x1 ` 3x2 ď 3
x1 , x2 ě0
56 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
b)
max 45 x1 ` 3x2
sujet à 5x1 ` 10x2 ě 25
3x1 ` 4x2 ě 13
x1 , x2 ě0
c)
min ´2x1 ´ x2
sujet à x1 ` 83 x2 ď4
x 1 ` x2 ď2
2x1 ď3
x1 , x2 ě0
d)
min ´x1
sujet à ´2x1 ` x2 ď2
x1 ` x2 ď8
x1 ´ x2 ď4
x1 , x2 ě0
b) Supposons maintenant que la fonction objetif devient ´x1 ` cx2 . Déterminez les valeurs
du paramètre c pour que la solution optimale trouvée en (a) demeure optimale avec le
nouvel objectif.
2.3. FORMES STANDARD 57
a) En notant xi la fraction de tonne de produit brut i contenu dans une tonne d’aliment,
formulez un modèle spécifique de cette situation.
b) Montrez qu’il est possible de réduire la dimension du problème, il est possible d’exprimer
une des variables en fonction des deux autres. Résolvez le alors graphiquement.
min cx
xPRn
, (2.1)
sujet à Ax ď b P Rm
Dans cette forme, les variables proprement dites x ne sont pas spécifiées comme étant bornées.
Dans le jargon, on les décrit alors comme des variables libres.
Une inégalité “plus grand ou égal” ax ě b peut être multipliée par ´1 pour être convertie
en inégalité “plus petit ou égal” ´ax ď ´b.
58 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
min cx
xPRn
sujet à Ax “ b P Rm , (2.2)
xě0
Exercice 2.3.1 [Contraintes supérieures ou égales] Obtenez une contrainte d’égalité équi-
valente à la contrainte ax ě b.
2.3. FORMES STANDARD 59
Exercice 2.3.2 [Variable libre] Utilisez la seconde équation pour exprimer x3 et substituez
le tout dans la première équation
60 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Exemple
Examinons un petit exemple. Considérons le problème
min z “ x1 ´ x2
sujet à 2x1 ` x2 ě 2
(2.6)
x1 ` 3x2 ď 3
x1 , x2 ě 0
min z “ x1 ´ x2
sujet à 2x1 ` x2 ´ x3 “ 2
(2.7)
x1 ` 3x2 ` x4 “ 3
x1 , x2 , x3 , x4 ě 0
La figure 2.9 illustre le domaine réalisable, le triangle en traits épais. Comme mentionné
précédemment, notre intuition nous suggère que la solution optimale est sur un des sommets
du triangle. Un sommet du triangle en est un point extrême.
2.3. FORMES STANDARD 61
3
Les intersections des droites
encerclées en gras sont les
points extrêmes réalisables
correspondant aux solutions
2
de base réalisables de (2.7).
Les intersections encerclées
en mince ne sont pas réa-
lisables, mais sont tout de
1 même des solutions de base
de (2.7).
1 2 3
de calculer un sommet donné si on connaît les composantes qui sont nulles et celles qui
sont potentiellement non-nulles. Il suffit d’extraire la sous-matrice (carrée) correspondant
aux variables non nulles et de résoudre le système d’équations correspondant. Dans notre
exemple, les trois systèmes d’équations de chacun des trois sommets sont
ˆ ˙ˆ ˙ ˆ ˙ˆ ˙ ˆ ˙ˆ ˙ ˆ ˙
2 0 x1 2 ´1 x1 2 1 x1 2
“ “ “ . (2.8)
1 1 x4 1 0 x3 1 3 x2 3
Les matrice carrées correspondent aux colonnes appropriées de la matrice complète des
contraintes ˆ ˙
2 1 ´1 0
.
1 3 0 1
62 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Une telle solution associée à une sous-matrice carrée est nommée solution de base. Les trois
sommets du triangle sont les solutions de base réalisables. Il y a trois autres sous-matrices
carrées (2 ˆ 2) dans notre exemple, correspondant à trois autres solutions de base, mais non
réalisables.
On dénote par B l’ensemble des indices correspondant aux composantes non nulles d’une
solution de base, et par N l’ensemble des indices correspondant aux composantes nulles.
Cette partition des indices est notée rrB | N ss. On dénote également la sous-matrice carrée
par B et la sous matrice des autres variables par N . Dans notre exemple simple, N est
également une matrice carrée, mais ce n’est pas le cas en général. Selon cette notation, pour
une solution de base x, xN sont les composantes nulles et xB “ B ´1 b ě 0 les composantes
positives. Nous verrons plus tard les complications associées à des composantes nulles de xB ,
pour l’instant, considérons qu’elles sont positives. Résumons le tout formellement dans la
définition suivante.
Définition 2.3.1 Soit un ensemble décrit par des contraintes Ax “ b, x ě 0. Une solution
de base est une partition rrB | N ss de la matrice A telle que la sous-matrice B est inversible.
Alors, le x correspondant est xB “ B ´1 b et xN “ 0. Si de plus, xB ě 0, la solution de
base est dite réalisable. Si de plus xB ą 0, la solution réalisable est dite non dégénérée, en
d’autre termes, si au moins une des composantes de xB est nulle, la solution est dégénérée.
Les solutions de base du problème (2.7) peuvent être identifiées comme les points d’inter-
section entre deux droites sur le graphique bi-dimensionnel représentant le problème (2.6).
En effet, chacune des droites correspondant aux deux contraintes correspond à x3 “ 0 ou
x4 “ 0. Le point d’intersection des deux droites possède donc deux composantes nulles, les
composantes de N . L’intersection d’une des deux droites avec un axe canonique possède
aussi deux composantes nulles, celle de l’autre axe (l’intersection avec l’axe x1 est telle que
x2 “ 0) et sa propre variable d’écart nulle. Finalement, l’origine est telle que x1 “ x2 “ 0 et
les variables d’écart des deux droites sont non nulles puisque l’origine n’appartient pas aux
droites en question.
Exercice 2.3.3 [Forme standard du simplexe] Écrire les problèmes suivants sous forme
standard.
a)
min z “ 18x1 ` 12x2 ` 2x3 ` 6x4
sujet à 3x1 ` x2 ´ 2x3 ` x4 “ 2
x1 ` 3x2 ´ x4 ď 2
x1 ě 0
x2 , x4 ď 0
x3 libre.
2.3. FORMES STANDARD 63
b)
min z “ ´x1 ´ 4x2 ´ 3x3
sujet à 2x1 ` 2x2 ` x3 ď 4
x1 ` 2x2 ´ 2x3 ě 6
x1 , x2 ě 0
x3 libre.
c)
min z “ x1 ` 3x2 ` 4x3
sujet à x1 ` 2x2 ` x3 “ 5
2x1 ` 3x2 ` x3 “ 6
x2 , x3 ě 0
x1 libre.
d)
min z “ |x1 | ` |x2 | ` |x3 |
sujet à x1 ` 2x2 ď 1
2x1 ` x3 “ 3
x1 x2 x3 libres.
e)
max min t5x1 , 2x2 u
sujet à 2x1 ` x2 ` 3x3 ď 4
x2 ` 5x3 ď 6
x1 , x2 ě 0
x3 libre.
x1 ` 2x2 ` x3 “ 5
2x1 ` ax2 ` 3x3 “ 6 (2.9)
x1 , x2 , x3 ě 0.
d) Y a-t-il une(des) valeur(s) de a pour que toutes les solutions soient réalisables et non
dégénérées ?
e) Pour quelles valeurs de a une ou plusieurs solutions de base sont-elles dégénérées ?
Exercice 2.3.5 [Sommets et solutions de base] Considérez l’exemple (1.5) – (1.8) qui se
ramène sous la forme standard du simplexe comme
¨ ˛ ¨ ˛
1 1 1 0 0 400
˝2 1 0 1 0‚x “ ˝600‚
0 1 0 0 1 300
x ě 0.
5 ď 6x1 ´ x2 ` 3x3 ď 8.
6x1 ´ x2 ` 3x3 ` x4 “ 8
0 ď x4 ď 3.
min z “ cx
sujet à bi ď Ax ď bs
x ě 0
peut se reformuler avec des contraintes d’égalité, et des variables bornées supérieurement.
bi sont des bornes inférieures et bs des bornes supérieures, avec bi ď bs .
d) Mettez le programme en c) sous forme standard.
x1 x2 x3 x4 B ´1 b
´2 ´1 1 0 ´2 (2.10)
1 3 0 1 3
Ce tableau correspond à une solution de base, mais pas réalisable. En effet, la solution est
x1 “ x2 “ 0 qui n’appartient pas au domaine réalisable (le triangle).
66 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Nous avons vu qu’il y a exactement six solutions de base, dont trois réalisables. L’opéra-
tion de pivot permet de passer d’une solution de base à une autre solution de base adjacente.
Par exemple, passons à la solution B “ t2, 4u. Pour ce faire, nous déterminons l’élément du
tableau de la première ligne (associée à x3 ) dans la colonne 2.
x1 x2 x3 x4 B ´1 b
´2 -1 1 0 ´2 (2.11)
1 3 0 1 3
Maintenant, divisons la première ligne par l’élément pivot.
x1 x2 x3 x4 B ´1 b
2 1 ´1 0 2 (2.12)
1 3 0 1 3
Enfin, ajoutons le multiple approprié de la première ligne pour que le résultat annule toute la
colonne de l’élément pivot. Ici, il faut ajouter ´3 de la première ligne à la seconde pour que
l’élément de la seconde ligne, seconde colonne devienne nul. Le prochain tableau est donc :
x1 x2 x3 x4 B ´1 b
2 1 ´1 0 2 (2.13)
´5 0 3 1 ´3
Encore une fois, ce tableau correspond à une solution de base, mais pas réalisable, le point
x1 “ 0, x2 “ 2. Cette fois-ci, passons à B “ t1, 4u. Le pivot est donc sur la première ligne et
la première colonne. La première ligne est associée à x2 par colonne de matrice identité alors
que la première colonne correspond à la nouvelle variable de base pour le prochain tableau,
x1 .
x1 x2 x3 x4 B ´1 b
2 1 ´1 0 2 (2.14)
´5 0 3 1 ´3
Même recette maintenant, on divise la ligne par l’élément pivot et détermine les multiples
de la ligne ainsi divisée permettant de “zéroter” la colonne pivot. Donc, on divise la ligne 1
par 2 et ajoute 5 fois la ligne 1 ainsi divisée à la ligne 2 pour obtenir :
x1 x2 x3 x4 B ´1 b
1 12 ´ 12 0 1 (2.15)
5 1
0 2 2
1 2
Voilà enfin une solution de base réalisable. On détecte rapidement qu’elle est réalisable par
la colonne B ´1 b ą 0. Cette solution de base réalisable est le point x1 “ 1, x2 “ 0 qui est bel
et bien un sommet du triangle réalisable.
On remarque que la matrice B ´1 n’est jamais explicitement calculée, seulement B ´1 A et
B ´1 b.
2.5. QUELQUES PROPRIÉTÉS DES CONTRAINTES LINÉAIRES 67
Exercice 2.4.1 [Pratique de pivots 2 lignes] Nous avons calculé trois des six solutions
de base pour le petit exemple. Complétez le calcul des trois autres solutions de base en
effectuant des opérations de pivot appropriées à partir de l’un ou l’autre des tableaux
ci-haut calculés.
Exercice 2.4.2 [Pratique de pivots 3 lignes] Considérez les contraintes de l’exercice 2.3.5
et qui correspondent à la figure 2.2. Le domaine réalisable est le pentagone illustré. Il y a
déjà une identité dans la matrice, donc le tableau de départ peut correspondre aux indices
B “ t3, 4, 5u. C’est la solution de base réalisable x1 “ x2 “ 0. Effectuez des pivots pour
parcourir toutes les solutions de base réalisables. Utilisez la figure pour vous guider dans
le choix d’ordre de pivots.
Les ensembles réalisables définis par des contraintes linéaires sont des ensembles convexes.
Voici d’abord la définition d’un ensemble convexe.
Définition 2.5.1 Un ensemble E est dit convexe s’il contient le segment de droite reliant
une paire quelconque de ses points. Un ensemble E est dit affine s’il contient toute la
droite passant par une paire quelconque de ses points. Soient deux points x, y P E, et soit
ppθq “ θx ` p1 ´ θqy. E est affine si et seulement si ppθq P E, @θ et E est convexe si et
seulement si ppθq P E, @θ P r0, 1s.
68 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Preuve Soient deux points x et y satisfaisant chacune des contraintes définissant E. Pre-
nons une contrainte d’égalité. On a ax “ b et ay “ b, donc un point p du segment entre x et
y, spécifié par p “ θx`p1´θqy où θ P r0, 1s satisfait ap “ apθx`p1´θqyq “ θax`p1´θqay “
θb ` p1 ´ θqb “ b.
Le cas d’une contrainte d’inégalité est laissé en exercice.
Donc, E défini par un ensemble de contraintes linéaires d’égalité et d’inégalité est tel que
le segment entre deux points satisfaisant toutes les contraintes satisfait lui aussi toutes les
contraintes. l
Définition 2.5.2 Un point p d’un ensemble convexe E est un point extrême si et seule-
ment si en tentant d’exprimer p “ θx ` p1 ´ θqy pour x, y P E, θ P p0, 1q, on se retrouve
avec x “ y “ p.
En d’autres termes, p est un point extrême s’il ne fait partie d’aucun segment xy
¯ de E.
Les points extrêmes de polygones convexes dans le plan sont ses sommets.
2.5. QUELQUES PROPRIÉTÉS DES CONTRAINTES LINÉAIRES 69
Les notions de convexité, de point extrême sont facile à comprendre à l’aide d’exemples
géométriques dans le plan. La forme standard du simplexe est une écriture plus algébrique
et on peut développer ces notions à l’aide d’outils d’algèbre linéaire.
Considérons un point x P E qui n’est pas une solution de base réalisable. Il y a donc
trop de composantes positives, c’est-à-dire que les colonnes de la sous-matrice associée aux
composantes positives ne sont pas linéairement indépendantes. Nommons cette sous-matrice
B même si elle comporte moins que m colonnes. Puisque ses colonnes ne sont pas linéairement
indépendantes, son noyau n’est pas réduit à t0u, prenons donc un vecteur dB P ker B. On a
donc la situation suivante : xB ą 0, xN “ 0 et dB P ker B. Nous allons construire un nouveau
point qui aura une composante positive en moins. On a BxB “ b et BdB “ 0. Notre nouveau
point sera xB ` t̂dB ě avec une composante nulle. Laquelle ? on sépare les composantes de B
selon le signe de dB , dB ` ą 0, dB ´ ă 0 et dB 0 “ 0, B “ B ` Y B ´ Y B 0 . Alors, pour garantir
que xB ` tdB ě 0, on doit avoir
´xi
xi ` tdi ě 0, i P B ` ðñ t ě ă0
di
´xi
xi ` tdi ě 0, i P B ´ ðñ t ď ą 0.
di
t_max
Théorème 2.5.3 (Solutions extrêmes sous forme standard) Les points extrêmes
d’un ensemble défini par des contraintes linéaires sous la forme standard du simplexe sont
précisément ses solutions de base réalisables.
Preuve Soit x une solution de base réalisable associée à rrB | N ss. Puisque la sous-matrice
B est inversible, si on veut construire un segment de droite contenant x, il faudra que
d’autres composantes que celles de B soient positives. Or, toutes les composantes doivent
être non-négatives, donc ... Ce qui montre qu’une solution de base ne peut pas appartenir à
2.5. QUELQUES PROPRIÉTÉS DES CONTRAINTES LINÉAIRES 71
un segment réalisable sauf le segment dégénéré réduit au seul point x et ainsi toute solution
de base est un point extrême de l’ensemble réalisable.
Par ailleurs, soit x une solution qui n’est pas de base. La démonstration de la pro-
position 2.5.2 permet d’exhiber un segment d’extrémités xB ` maxptmin , ´1qdB et xB `
minptmax , 1qdB qui contient x. Donc, une solution pas de base n’est pas un point extrême de
l’ensemble réalisable. l
Preuve Si les colonnes associées aux composantes positives de x ne sont pas linéairement
indépendantes, il suffit d’appliquer la proposition 2.5.2 autant de fois qu’il faudra pour arriver
à une solution réalisable dont les composantes positives correspondent à des colonnes linéai-
rement indépendantes de la matrice A. À chaque application de la proposition, le nombre de
composantes positives est réduit d’au moins un, donc tôt ou tard, nous aurons obtenu une
solution de base réalisable.
Soit donc x une solution réalisable dont les composantes positives correspondent à des
colonnes de A linéairement indépendantes. S’il y a moins de m composantes positives, il
suffit de compléter ces colonnes pour obtenir m colonnes linéairement indépendantes et la
solution est alors une solution de base réalisable. C’est toujours possible de compléter les
colonnes puisque nous avons supposé que rangpAq “ m. l
a) Vérifiez que p1, 1, 13, 8qt est une solution réalisable. Appliquez la construction de la
démonstration du théorème 2.5.4 pour obtenir une solution de base réalisable.
b) Donnez toutes les solutions de base de ce problème.
c) Parmi les solutions de base, identifiez celles qui sont réalisables.
72 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
d) Les variables s sont des variables d’écart. Vérifiez que les solutions de base réalisables
énumérées en (c) correspondent bel et bien aux sommets du polygone de contraintes
d’inégalités en les seules variables x. Interprétez géométriquement les solutions de base
non-réalisables.
Dans ce dernier exercice, on converti une solution réalisable quelconque dans une solution
de base réalisable à l’aide d’un procédé qui avait été utilisé dans la démonstration du théo-
rème 2.5.4. Ce procédé, ou algorithme, n’a pas vraiment d’utilité pratique, le but de l’exercice
était de mieux comprendre la démonstration du théorème en appliquant sa construction sur
un exemple simple.
2.6 Résumé
Nous avons présenté la formulation d’un problème d’optimisation linéaire. Nous avons
déduit l’intuition géométrique permettant de résoudre de petites instances de ces problèmes.
Nous avons ensuite introduit plusieurs variantes de problèmes d’optimisation linéaire tout
en remarquant que toutes ces formes sont en quelque sorte équivalentes entre elles car on
peut passer d’une forme à l’autre. Nous avons caractérisé ce qu’on entend par solution d’un
modèle d’optimisation, soit une déclaration que le modèle n’est pas réalisable, soit qu’il n’est
pas borné, soit que l’on exhibe une solution optimale.
La forme dite “standard du simplexe” a permis de formuler un résultat mathématique
important qui stipule que si un modèle est réalisable, alors il possède une solution de base
réalisable.
max x1 ` 2x2
sujet à x1 ` x2 ď 2
x1 ` 3x2 ď 3
x1 , x2 ě0
2.7. TOUS LES EXERCICES DU CHAPITRES 73
b)
max 45 x1 ` 3x2
sujet à 5x1 ` 10x2 ě 25
3x1 ` 4x2 ě 13
x1 , x2 ě0
c)
min ´2x1 ´ x2
sujet à x1 ` 38 x2 ď4
x1 ` x 2 ď2
2x1 ď3
x1 , x2 ě0
d)
min ´x1
sujet à ´2x1 ` x2 ď2
x1 ` x2 ď8
x1 ´ x2 ď4
x1 , x2 ě0
b) Supposons maintenant que la fonction objetif devient ´x1 ` cx2 . Déterminez les valeurs
du paramètre c pour que la solution optimale trouvée en (a) demeure optimale avec le
nouvel objectif.
Les pourcentages de protéines et de graisse contenus dans chacun des ingrédients ainsi que
le coût par tonne de chaque produit sont indiqués dans le tableau suivant.
a) En notant xi la fraction de tonne de produit brut i contenu dans une tonne d’aliment,
formulez un modèle spécifique de cette situation.
b) Montrez qu’il est possible de réduire la dimension du problème, il est possible d’exprimer
une des variables en fonction des deux autres. Résolvez le alors graphiquement.
Exercice (2.3.1, page 58) [Contraintes supérieures ou égales] Obtenez une contrainte
d’égalité équivalente à la contrainte ax ě b.
Exercice (2.3.2, page 59) [Variable libre] Utilisez la seconde équation pour exprimer x3
et substituez le tout dans la première équation
Exercice (2.3.3, page 62) [Forme standard du simplexe] Écrire les problèmes suivants
sous forme standard.
a)
min z “ 18x1 ` 12x2 ` 2x3 ` 6x4
sujet à 3x1 ` x2 ´ 2x3 ` x4 “ 2
x1 ` 3x2 ´ x4 ď 2
x1 ě 0
x2 , x4 ď 0
x3 libre.
b)
min z “ ´x1 ´ 4x2 ´ 3x3
sujet à 2x1 ` 2x2 ` x3 ď 4
x1 ` 2x2 ´ 2x3 ě 6
x1 , x2 ě 0
x3 libre.
c)
min z “ x1 ` 3x2 ` 4x3
sujet à x1 ` 2x2 ` x3 “ 5
2x1 ` 3x2 ` x3 “ 6
x2 , x3 ě 0
x1 libre.
2.7. TOUS LES EXERCICES DU CHAPITRES 75
d)
min z “ |x1 | ` |x2 | ` |x3 |
sujet à x1 ` 2x2 ď 1
2x1 ` x3 “ 3
x1 x2 x3 libres.
e)
max min t5x1 , 2x2 u
sujet à 2x1 ` x2 ` 3x3 ď 4
x2 ` 5x3 ď 6
x1 , x2 ě 0
x3 libre.
Exercice (2.3.4, page 63) [Solutions de base] Considérez le système linéaire suivant.
x1 ` 2x2 ` x3 “ 5
2x1 ` ax2 ` 3x3 “ 6 (2.16)
x1 , x2 , x3 ě 0.
a) Pour quelles valeurs du paramètre a le système possède-t-il exactement trois bases ? Dé-
notons l’ensemble des valeurs D.
b) Déterminez les trois solutions de base identifiées en (a).
c) Pour chacune des solutions calculées en (b), énoncez des conditions sur a pour que cette
solution soit réalisable.
d) Y a-t-il une(des) valeur(s) de a pour que toutes les solutions soient réalisables et non
dégénérées ?
e) Pour quelles valeurs de a une ou plusieurs solutions de base sont-elles dégénérées ?
Exercice (2.3.5, page 64) [Sommets et solutions de base] Considérez l’exemple (1.5) –
(1.8) qui se ramène sous la forme standard du simplexe comme
¨ ˛ ¨ ˛
1 1 1 0 0 400
˝2 1 0 1 0‚x “ ˝600‚
0 1 0 0 1 300
x ě 0.
Exercice (2.4.2, page 67) [Pratique de pivots 3 lignes] Considérez les contraintes de l’exer-
cice 2.3.5 et qui correspondent à la figure 2.2. Le domaine réalisable est le pentagone illustré.
Il y a déjà une identité dans la matrice, donc le tableau de départ peut correspondre aux
indices B “ t3, 4, 5u. C’est la solution de base réalisable x1 “ x2 “ 0. Effectuez des pivots
pour parcourir toutes les solutions de base réalisables. Utilisez la figure pour vous guider
dans le choix d’ordre de pivots.
Exercice (2.5.1, page 68) [Inégalités] Complétez la démonstration pour une contrainte
d’inégalité.
Exercice (2.5.2, page 71) [Solutions réalisables et solutions de base] Considérez le pro-
blème suivant, sous forme standard :
a) Vérifiez que p1, 1, 13, 8qt est une solution réalisable. Appliquez la construction de la dé-
monstration du théorème 2.5.4 pour obtenir une solution de base réalisable.
b) Donnez toutes les solutions de base de ce problème.
c) Parmi les solutions de base, identifiez celles qui sont réalisables.
d) Les variables s sont des variables d’écart. Vérifiez que les solutions de base réalisables
énumérées en (c) correspondent bel et bien aux sommets du polygone de contraintes
d’inégalités en les seules variables x. Interprétez géométriquement les solutions de base
non-réalisables.
78 CHAPITRE 2. INTRODUCTION ET INTUITION GÉOMÉTRIQUE
Chapitre 3
Algorithme du simplexe
Sujets du chapitre
‚ Solutions de base.
‚ Conditions d’optimalité.
‚ Déduction de l’algorithme du simplexe.
‚ Organisation des calculs.
79
80 CHAPITRE 3. ALGORITHME DU SIMPLEXE
Introduction
Nous avons présenté quelques propriétés qui découlent d’une intuition géométrique sur
des exemples simples en petites dimensions. Une notion importante est celle de point extrême.
Nous allons maintenant justifier mathématiquement l’intuition qu’un problème d’optimisa-
tion linéaire admet une solution en un point extrême. Ceci constituera la base de l’algorithme
du simplexe, qui parcourre les points extrêmes jusqu’à identifier la solution.
de l’origine, ou encore d’une demi-droite, ou encore d’un segment de droite. Dans ce cas,
les points extrêmes appartiennent à un plan canonique (extrémités de la demi-droite ou du
segment).
Ces illustrations géométriques sont à la base de la caractérisation des solutions de base en
optimisation linéaire. En effet, en supposant que le domaine n’est pas vide, un sous-espace de
Rn de dimension n ´ m intersecte au moins un hyperplan canonique de dimension m. Dans
l’exemple de R3 , le plan intersecte au moins un axe canonique (hyperplan de dimension un)
alors que la droite intersecte au moins un des plans canoniques (xy, yz ou zx). Supposons
donc que les composantes d’un vecteur de Rn sont ordonnées de telle sorte que l’hyperplan
canonique qui contient un tel point d’intersection est formé des m premières composantes.
Ce point est donc de la forme px1 , x2 , . . . , xm , 0, 0, . . . , 0qt . Ordonnons conséquemment les
colonnes de la matrice A ainsi que les composantes du vecteur c, et écrivons :
ˆ ˙
xB
min cx “ rcB , cN s
x
ˆ N˙
xB
sujet à Ax “ rB, N s “ BxB ` N xN “ b
xN
xB ě 0
xN “ 0.
Maintenant, supposons que la matrice B est inversible et donc xB “ B ´1 b. Les colonnes de
la matrice B forment une base du sous-espace canonique de dimension m alors que le vecteur
xB constitue les coordonnées du vecteur b dans cette base. La partition rrB | N ss, ou encore
le vecteur x “ rxB , 0s est nommé solution de base réalisable.
Cette notation est universelle, malgré l’ambigüité de la signification des symboles B et N ,
qui réfèrent à la partition des composantes de Rn mais qui réfèrent aussi aux sous-matrices
correspondantes de la matrice A.
Avant de terminer cette introduction, revenons sur l’hypothèse que la matrice B soit
inversible. Puisque nous supposons que BxB “ b, même si la matrice B est singulière, le
système d’équations Bx “ b possède tout de même une solution. En fait, si la matrice B est
singulière, c’est que le système Bx “ b possède plusieurs solutions, dont certaines comportent
des composantes nulles. C’est une manifestation du phénomène de dégénérescence, que nous
traiterons plus tard.
Preuve La démonstration est la même que celle du théorème 2.5.4. En effet, la dé-
monstration de la proposition 2.5.2 utilise une direction dB avec un pas de déplacement
tmin ď t ď tmax qui peut être positif ou négatif puisque ´8 ď tmin ă 0 ă tmax ď 8. Puisque
le point réalisable est optimal, obligatoirement cpx ` tdq ě cx, donc cptdq ě 0 sinon ça
contredirait que cx est optimal. Donc, cd ě 0 et ´cd ě 0 entraîne que cd “ 0 et que le point
construit dans la proposition 2.5.2 possède la même valeur de fonction objectif et donc est
optimal. l
Nous examinons dans cette section les conditions sous lesquelles une solution rxB , 0s est
optimale pour le problème linéaire (2.2). Il semble clair que pour qu’une telle solution soit
optimale, il suffit de s’assurer qu’il est impossible de réduire la fonction objectif cB xB ` cN 0
en augmentant les composantes de xN . Profitons du fait que B est inversible pour écrire
xB “ B ´1 pb ´ N xN q. Cette dernière relation permet de mettre xB en fonction de xN . De
même, la fonction objectif peut se récrire comme
cB xB ` cN xN “ cB B ´1 pb ´ N xN q ` cN xN
“ pcN ´ cB B ´1 N qxN ` cB B ´1 b.
En fait, il est maintenant possible de reformuler le problème (2.2) en utilisant seulement les
composantes xN , donnant le problème réduit :
Théorème 3.3.2 (Condition suffisante d’optimalité) Soit une solution de base réa-
lisable x “ rxB xN s. Si pcN ´ cB B ´1 N q ě 0, alors x est une solution optimale.
Théorème 3.3.3 (Condition nécessaire d’optimalité) Soit une solution de base réa-
lisable et optimale x. Alors, il existe une décomposition x “ rxB xN s telle que pcN ´
cB B ´1 N q ě 0.
3.3.1 Exemple
Revenons à l’exemple (2.7), où nous avons énuméré les trois bases réalisables (2.8)
t1, 4u, t1, 3u, t1, 2u. Pour le vecteur de coût p1, ´1, 0, 0q, la résolution graphique nous donne
que la solution est x1 “ 35 , x2 “ 45 . Donc, la base optimale est B “ t1, 2u et N “ t3, 4u.
Calculonsˆdonc pcN˙´ cB B ´1 N q. cN “ 0, cB “ p1, ´1q et l’exercice 2.4.1 nous a fourni
´3 ´1
B ´1 N “ 15 25 . Donc pcN ´ cB B ´1 N q “ p 45 , 35 q ě 0, ce qui confirme que notre solution
5 5
de base satisfait à la condition d’optimalité.
L’exercice montre qu’il y a au moins une base décrivant la solution optimale pour laquelle
pcN ´ cB B ´1 N q ě 0 (il y en a deux). C’est la conclusion du théorème 3.3.3.
Ax “ b, (3.4)
x ě 0 (3.5)
πA ` s “ c, (3.6)
s ě 0 (3.7)
sx “ 0. (3.8)
Exercice 3.3.2 [Problèmes non bornés] Est-il possible que le problème (2.2) ainsi que le
problème max cx sous les mêmes contraintes soient tous deux non-bornés ? Justifiez.
xi
atteignent le mini:δxi ą0 p δxi
q. Nous supposons pour l’instant que ce min n’est atteint que
pour un seul indice ı̄ et de plus que xı̄ ą 0. Lorsque ce n’est pas le cas, c’est que le problème
comporte de la dégénérescence, et ce phénomène sera étudié plus tard.
xB xN
0 cN ´ zN ´cB xB (3.10)
I B ´1 N B ´1 b
Les opérations de pivot seront effectuées comme précédemment, en ajoutant le calcul pour
“zéroter” la nouvelle ligne dite “ligne zéro”. Un problème d’optimisation linéaire correspon-
dant à un tel tableau est dit de forme canonique.
L’algorithme du simplexe s’assure que la dernière colonne, B ´1 b ě 0 par le choix de ı̄
dit variable sortante car cet indice sera enlevé de B et ajouté dans N , cette variable sortira
de la base. La variable ̄ entrera dans la base et est nommée variable entrante. Les choix de
3.4. ALGORITHME DU SIMPLEXE 87
variables entrante et sortante détermine l’élément pivot du tableau et le calcul du pivot est
comme à la section 2.4.
L’algorithme du simplexe se résume aux trois étapes suivantes qui sont répétées jusqu’à
ce que c ´ z ě 0.
1. ̄ “ arg minjPN pcj ´ zj q ; indice minimisant la ligne zéro ;
xi
2. ı̄ “ arg mini:δxi ą0 p δx i
q ; c’est le rapport de la dernière colonne divisée par la colonne ̄ ;
3. mettre à jour le tableau selon l’élément pivot de la ligne ı̄ et colonne ̄.
Remarque 3.4.1 Une fois que c ´ z ě 0, on a que toutes les équations (3.4) –(3.8) sont
satisfaites, ce qui signifie que la partition est optimale.
Exemple simple
min z “ x1 ´ x2
sujet à 2x1 ` x2 ´ x3 “ 2
x1 ` 3x2 ` x4 “ 3
x1 , x2 , x3 , x4 ě 0
x1 x2 x3 x4
1 ´1 0 0 0
(3.11)
2 1 ´1 0 2
1 3 0 1 3
Ce tableau n’est pas sous forme canonique puisqu’il n’y apparaît pas de matrice identité.
Maintenant, rien d’évident pour obtenir une partition rrB | N ss telle que xB “ B ´1 b ě 0. Nous
verrons aux sections 3.5 et 6.2 des techniques systématique pour y parvenir. Pour l’instant,
t
remarquons par inspection
ˆ ˙ de l’exemple très simpleˆ que 1x “ 1p1 0 ˙0 2q est une solution
2 0 1 2 ´2 0 `˘
réalisable et B “ . Calculons donc B ´1 A “ 5 1 . xB “ B ´1 b “ 12 et
1 1 0 2 2 1
π “ cB B ´1 “ p 12 0q ce qui nous donne c ´ πA “ p0 ´ 23 21 0q. Enfin, en traitant la colonne b
comme une colonne de A, on retrouve 0 ´ πb “ ´1, ce qui nous donne sous forme de tableau
réalisable sous forme canonique, on a bel et bien une identité dans les colonnes 1 et 4, la
ligne zéro a des coefficients nuls dans ces colonnes et la dernière colonne est positive.
x1 x2 x3 x4
0 ´3{2 1{2 0 ´1
1 1{2 ´1{2 0 1
0 5{2 1{2 1 2
88 CHAPITRE 3. ALGORITHME DU SIMPLEXE
Ce que nous recherchons, c’est une partition rrB | N ss telle que le tableau ainsi calculé ait
sa zéroième ligne et sa dernière colonne non-négatives, exception faite du coin commun à la
zéroième ligne et première colonne. L’algorithme du simplexe recherche itérativement une
telle partition en maintenant la dernière colonne non-négative et en progressant pour amener
la première ligne non-négative également.
Appliquons-le. On remarque que la seconde colonne a un élément négatif. Nous allons
échanger x2 P N avec soit x1 , soit x4 . Comment choisir ? Utilisons le critère développé (3.9).
On calcule le quotient de la dernière colonne divisé par la deuxième colonne pour les élé-
ments positifs de la deuxième colonne. Ça donne 2 et 45 , donc on choisit la seconde ligne,
correspondant à x4 . Bref, notre itération va échanger x2 et x4 de partition. On effectue fi-
nalement une opération de pivot. L’élément pivot est à la seconde ligne et seconde colonne.
Il suffit d’effectuer des opérations élémentaires pour transformer la seconde colonne en une
portion d’identité, donc que l’élément pivot vaille un et le reste de la colonne zéro. On divise
la deuxième ligne par l’élément pivot et ajoute un multiple approprié de celle-ci aux autres
lignes pour obtenir :
x1 x2 x3 x4
0 0 4{5 3{5 1{5
(3.12)
1 0 ´3{5 ´1{5 3{5
0 1 1{5 2{5 4{5
Ce tableau est réalisable (dernière colonne non-négative) et optimal (première ligne non-
négative) et la valeur optimale est ´ 15 (élément première ligne et dernière colonne multiplié
par ´1).
Évidemment, sur des problèmes sérieux, beaucoup plus d’une itération seront nécessaires.
L’algorithme du simplexe primal passe d’un point extrême réalisable à l’autre en réduisant
la fonction objectif.
1. Trouvez une base initiale, et fournissez les valeurs des variables de la solution de base
associée.
x4 , x1 , x6 valent 10,2 et 6.
2. Mettez le programme sous forme canonique.
Exprimons la fonction objectif en fonction des variables hors-base. Seul le terme de x6
n’est pas nul, et de la troisième contrainte, on tire que x6 “ 6 ´ x2 ´ 15x3 ´ x5 , donc la
fonction objectif devient 6 ´ 10x2 ´ 16x3 ` x5 .
3. Votre solution de base initiale est-elle optimale ? Pourquoi ?
Non, car les coefficients de la fonction objectif réduite aux variables hors-base ne sont
pas tous non-négatifs.
4. Comment pouvez choisir une colonne pour effectuer une étape de l’algorithme du simplexe ?
Choisissez-en une.
On prend le plus négatif des coûts relatifs, donc on choisit x3 .
5. Comment pouvez-vous choisir une ligne ? Votre choix garantit-il que après le pivot, la
solution de base sera réalisable ? Expliquez.
Le quotient du membre de droite sur l’élément de la colonne de la variable entrante
nous donne l’augmentation maximale assurant que la variable de base correspondante
demeure non-négative. Ici, la première ligne correspond au plus petit quotient.
6. Serait-il possible qu’aucune ligne de puisse être choisie (pas forcément pour cet exemple) ?
Si oui, quelle information en tire-t-on ?
Le critère énoncé ci-haut ne s’applique qu’aux lignes dont la colonne choisie est positive.
Si aucun élément de la colonne choisie est positif, le problème est non-borné.
7. Effectuez l’opération de pivot pour la colonne et la ligne que vous avez déterminées en
(d) et (e). Vérifiez directement dans les équations originales que votre nouvelle solution de
base est réalisable.
x1 x2 x3 x4 x5 x6
´z 0 8{5 0 8{25 8{25 0 ´14{5
x3 0 1{10 1 1{50 1{50 0 1{5
x1 1 ´152{10 0 ´1{25 ´1{25 0 8{5
x6 0 ´1{2 0 ´3{2 ´1{2 1 3
Ainsi, x1 “ 8{5, x3 “ 1{5 et x6 “ 3. Dans les contraintes originales, la première ne
comporte que x3 , et et est satisfaite, la seconde donne 8{5 ` 2{5 “ 2 et la troisième
15p1{5q ` 3 “ 6. La fonction objectif vaut 3 ´ 1{5 “ 14{5.
8. Votre solution est-elle optimale maintenant ? Pourquoi ?
Oui, car les coûts relatifs sont tous positifs.
3.4. ALGORITHME DU SIMPLEXE 91
xB “ B ´1 b ´ B ´1 N xN .
xN
z “ cx cB xB cN ´ cB B ´1
xB B ´1 b ´ B ´1 N
x2 x3
z 1 ´3{2 1{2
x1 1 ´ 1{2 ´ ´1{2
x4 2 ´ 5{2 ´ 1{2
Il y a plusieurs outils disponibles sur internet pour faciliter les calculs de l’algorithme du
simplexe. Mon préféré
https://neos-guide.org/content/simple-pivot-tool
utilise justement la notion de dictionnaire. Si les données (éléments de la matrice A et des
vecteurs c et b) sont rationnels, alors toutes les quantités intermédiaires sont également ra-
tionnelles. Donc, on peut effectuer tous les calculs de manière exacte en utilisant des fractions
plutôt qu’une représentation approchée en décimales. Les calculs en décimales ne sont pas
exacts, mais sont seulement approchés car par exemple 13 n’admet pas de représentation
exacte en décimale, 13 “ 0.333 . . . que l’on approche avec un nombre fini de décimales, par
exemple 31 « 0.3333. Pour nos problèmes d’optimisation linéaire, tant que les données sont
rationnelles, il est possible d’effectuer les calculs et obtenir une solution exacte rationnelle.
Exercice 3.4.3 [Algorithme du simplexe papier] Encore avec l’outil informatique, générez
au moins quatre problèmes aléatoires et résolvez-les par l’algorithme du simplexe sur papier
dans la forme tableau plutôt que dictionnaire. Effectuez vos calculs en fractions. Utilisez
l’outil pour valider vos calculs.
3.5.3 Exemple
Reprenons notre exemple habituel pour lequel nous avions utilisé une méthode ad hoc
afin d’obtenir une première solution de base réalisable. Appliquons lui la méthodologie que
nous venons de présenter.
Phase I forme tableau avec variables artificielles
A“ „
2 1 ´1 0
1 3 0 1
Les données que nous utilisons pour la phase I incluant les variables artificielles sont comme
suit.
A“ „
2 1 ´1 0 1 0
1 3 0 1 0 1
c“ “ ‰
0 0 0 0 1 1
Après mise sous forme canonique, le vecteur c devient
c“ “ ‰
´3 ´4 1 ´1 0 0
On résout maintenant ce problème par l’algorithme du simplexe forme tableau
c“ “ ‰
´5 1 4
3
0 1 3
0 3
3.5. COMMENT OBTENIR LA PREMIÈRE SOLUTION DE BASE RÉALISABLE 95
bt “ “ ‰
1 1
A“ „
5 ´1 ´1
3
0 ´1 3
1 3
1 1 1
3
1 0 3
0 3
nouveau B = “ ‰
5 2
nouveau N = “ ‰
1 6 3 4
Itération 2 choix de la colonne : 1 dans N , 1 dans 1..n ; choix de la ligne : 1
c“ “ ‰
0 0 0 0 1 1
bt “ “ ‰
3 4
5 5
A“ „
´3 ´1 3 ´1
1 0 5 5 5 5
1 2 ´1 2
0 1 5 5 5 5
nouveau B = “ ‰
1 2
nouveau N = “ ‰
5 6 3 4
Itération 3
Solution optimale
La phase I est complétée.
Le hasard fait que la phase I termine avec la solution de base réalisable correspondant à
la solution optimale, donc la phase II se réduit à constater l’optimalité. En général, ce n’est
pas le cas.
Exercice 3.5.1 [Méthode des deux phase] Après les avoir mis sous forme standard, ré-
solvez ces programmes linéaires en utilisant une des deux variantes de la méthode des 2
phases du simplexe. Illustrez graphiquement les itérations de la phase 2.
a)
min z “ ´3x1 ´ 2x2
sujet à x1 ` x2 ď 10
x1 ě 4
x1 , x2 ě 0
b)
min z “ x1 ` x2
sujet à ´x1 ` x2 ď ´1
x1 ´ x2 ď ´1
x1 , x 2 ě 0
c)
min z “ x1 ` x2
sujet à 2x1 ` x2 ě 2
x1 ` 3x2 ě 3
x1 , x2 ě 0
3.6. SIMPLEXE RÉVISÉ 97
et en utilisant des opérations élémentaires sur les matrices (voir appendice A.2.1), il est
possible de transformer cette dernière en pI, Nı̄1 q.
Sans préciser davantage comment s’effectuent les calculs, nous pouvons énoncer l’algo-
rithme dit du simplexe révisé. Si le choix de la variable sortante est unique de même que
xB ą 0, il est clair que cet algorithme termine en un nombre fini de calculs car le nombre de
décomposition rrB | N ss est grand, mais fini et à chaque nouvelle décomposition examinée, la
fonction objectif décroît, empêchant d’en examiner aucune plus d’une fois. Cependant, nous
verrons plus tard qu’il faut préciser davantage l’algorithme pour garantir sa terminaison pour
des problèmes dégénérés.
Remarquons ici que l’algorithme du simplexe original (non révisé) consiste à manipuler un
tableau donné par la matrice Ā “ B ´1 rb, B, N s “ rxB , I, B ´1 N s en calculant explicitement
toute la matrice transformée. Le tableau comporte également une “zéroième” ligne c ´ πA
qui vaut zéro dans les colonnes B. En traitant la dernière colonne comme une colonne de A,
on peut utiliser l’élément de la ligne zéro en dernière colonne pour y inscrire ´πb.
La version révisée de l’algorithme présentée ici consiste à calculer au besoin seulement la
colonne B ´1 N̄ à partir d’une représentation de la matrice B ´1 .
On peut résumer une itération de la forme révisée de l’algorithme comme suit.
1. calculer xB “ B ´1 b ;
2. calculer π “ cB B ´1 ;
3. calculer c̄N “ cN ´ πN ;
4. choisir une colonne profitable ̄ telle que p̄cN q̄ ă 0 ;
5. calculer δx “ B ´1 N̄ ;
6. choisir une ligne ı̄ par le test du ratio ;
7. effectuer un pivot sur l’élement pı̄, ̄ de la matrice rB|δxs pour obtenir la nouvelle matrice
B.
98 CHAPITRE 3. ALGORITHME DU SIMPLEXE
Simplexe révisé
t Données : une partition rrB | N ss de Rn , une représentation u
t de la matrice B ´1 ainsi qu’une solution réalisable rxB , 0s. u
optimal Ð faux
non_borné Ð faux
répéter
t Production d’un vecteur de coûts réduits u
π Ð SOLUTION(πB “ cB )
zN Ð πN
d Ð cN ´ zN
t Choix d’une variable entrante u
si (d ą 0 ) alors optimal Ð vrai
sinon
̄ Ð Calcule_̄
δx Ð SOLUTION(Bδx “ N̄ )
t Choix d’une variable sortante u
si (δx ă 0 ) alors non_borné Ð vrai
sinon xi
ı̄ Ð arg mini:δxi ą0 p δxi
q
t Mises-à-jour diverses u
rrB | N ss Ð rrB Y t̄uztı̄u | N Y tı̄uzt̄uss
B ´1 Ð Mise_à_jourpB ´1 , rrB | N ss, ı̄, ̄q
En pratique, les deux résolutions de systèmes linéaires sont efficaces car la matrice B est
représentées par une décomposition appropriée à la solution. Cette décomposition est donc
mise à jour en même temps que la partition des composantes ; dans l’algorithme, nous avons
nommé cette représentation B ´1 , mais nous verrons qu’il s’agit plutôt d’une décomposition
de la matrice B “ LU
Algorithme 3.1: Simplexe révisé.
3.6. SIMPLEXE RÉVISÉ 99
3.6.1 Exemple
Reprenons l’exemple que nous venons tout juste de voir, la phase I de notre problème
habituel.
À partir du problème habituel (le triangle)
min z “ x1 ´ x2
sujet à 2x1 ` x2 ´ x3 “ 2
x1 ` 3x2 ` x4 “ 3
x1 , x2 , x3 , x4 ě 0
x1 x2 x3 x4
1 ´1 0 0 0
(3.18)
2 1 ´1 0 2
1 3 0 1 3
x1 x2 x3 x4 x5 x6
1 ´1 0 0 0 0 0
(3.19)
2 1 ´1 0 1 0 2
1 3 0 1 0 1 3
8. Mettons à jour B ´1 pour cette nouvelle base (nommons la nouvelle matrice B̄) :
1 0 1
B ´1 |δx “
0 1 3
on effectue le pivot :
1 ´1{3 0
B̄ ´1 |δx “
0 1{3 1
Nous sommes prêts pour l’itérationˆ 2. Les˙indices de base sont maintenant B “ t5, 2u et
1 ´1{3
cB “ p1, 0q, et la matrice B ´1 “ .
0 1{3
itération 2
`˘
1. xB “ B ´1 b “ 11 ;
2. π “ cB B ´1 “ p1, ´1{3q ;
3. c̄N “ p0, 0, 0, 1q ´ πN “ p´5{3, 1, 1{3, 4{3q ;
`2˘
4. On choisit la colonne 1 de N où le plus négatif (le seul négatif) des c̄N se trouve, N1 “ 1
;
` ˘
5. On calcule δx “ B ´1 N1 “ 5{3
1{3
;
6. Ayant xB et δx, le test du ratio nous informe que le pivot est sur la ligne 1.
7. La nouvelle base sera donc B “ t1, 2u ;
8. Mettons à jour B ´1 pour cette nouvelle base (nommons la nouvelle matrice B̄) :
1 ´1{3 5{3
B ´1 |δx “
0 1{3 1{3
on effectue le pivot :
3{5 ´1{5 1
B̄ ´1 |δx “
´1{5 2{5 0
Nous avons terminé la phase I puisque les variables artificielles x5 et x6 sont toutes deux
devenues hors-base.
Phase II Nous allons continuer avec seules les variables x1 , x2 , x3ˆet x4 originales.
˙ Le
3{5 ´1{5
vecteur c “ p1, ´1, 0, 0q. Puisque nous avons sous la main B ´1 “ , nous
´1{5 2{5
pouvons appliquer l’algorithme du simplexe dans sa version révisée. B “ t1, 2u et cB “
t1, ´1u.
` ˘
1. xB “ B ´1 b “ 3{5
4{5
;
2. π “ cB B ´1 “ p4{5, ´3{5q ;
3.7. RÉSUMÉ 101
3. c̄N “ p0, 0q ´ πN “ p4{5, 3{5q ; puisque c̄N ą 0, la base est optimale et le problème est
résolu.
L’algorithme dans sa forme révisée est un peu plus complexe à exécuter à la main, mais
il se prête à une implémentation plus efficace.
Exercice 3.6.2 [Algorithme du simplexe papier en version révisée] Reprenez les exemples
que vous avez utilisés dans l’exercice 3.4.3 mais cette fois-ci, utilisez la version révisée de
l’algorithme pour les résoudre. Effectuez vos calculs en fractions. Utilisez vos solutions
obtenues avec la version tableau de l’algorithme pour valider chacune des itérations.
Exercice 3.6.3 [Deux phases simplexe révisé] Refaites les exercices 3.5.1 avec la version
révisée de l’algorithme du simplexe.
3.7 Résumé
On analyse que s’il existe au moins une solution optimale, il suffit d’explorer les solutions
dites de base pour en trouver une. Le nombre de solutions de base étant fini, si on s’assure de
ne pas tourner en rond, on aura identifié la solution optimale en un nombre fini de calculs.
Exercice (3.3.1, page 83) [Plusieurs bases] Modifions légèrement l’exemple (2.7) :
min z “ x1 ´ x2
sujet à 2x1 ` x2 ě 2
(3.20)
x1 ` 3x2 ď 6
x1 , x2 ě 0
Exercice (3.3.2, page 85) [Problèmes non bornés] Est-il possible que le problème (2.2)
ainsi que le problème max cx sous les mêmes contraintes soient tous deux non-bornés ? Jus-
tifiez.
Exercice (3.4.3, page 92) [Algorithme du simplexe papier] Encore avec l’outil informa-
tique, générez au moins quatre problèmes aléatoires et résolvez-les par l’algorithme du sim-
plexe sur papier dans la forme tableau plutôt que dictionnaire. Effectuez vos calculs en
fractions. Utilisez l’outil pour valider vos calculs.
3.9. TOUS LES EXERCICES DU CHAPITRES 103
Exercice (3.5.1, page 96) [Méthode des deux phase] Après les avoir mis sous forme stan-
dard, résolvez ces programmes linéaires en utilisant une des deux variantes de la méthode
des 2 phases du simplexe. Illustrez graphiquement les itérations de la phase 2.
a)
min z “ ´3x1 ´ 2x2
sujet à x1 ` x2 ď 10
x1 ě 4
x1 , x2 ě 0
b)
min z “ x1 ` x2
sujet à ´x1 ` x2 ď ´1
x1 ´ x2 ď ´1
x1 , x 2 ě 0
c)
min z “ x1 ` x2
sujet à 2x1 ` x2 ě 2
x1 ` 3x2 ě 3
x1 , x2 ě 0
Exercice (3.6.1, page 101) [Autres choix de pivot] À l’étape 3 de la première itération
de la phase I, on aurait pu choisir 3 des 4 colonnes avec un coût relatif négatif. Nous avons
choisi la colonne 2, associée au plus négatif. Poursuivez l’algorithme avec les deux autres
choix. En particulier, si vous choisissez la colonne 4, puis à l’itération suivante la colonne 1,
vous passerez à la phase II avec les variables de base t1, 4u, exactement le cas traité dans les
notes de cours.
Exercice (3.6.2, page 101) [Algorithme du simplexe papier en version révisée] Reprenez
les exemples que vous avez utilisés dans l’exercice 3.4.3 mais cette fois-ci, utilisez la version
révisée de l’algorithme pour les résoudre. Effectuez vos calculs en fractions. Utilisez vos
solutions obtenues avec la version tableau de l’algorithme pour valider chacune des itérations.
Exercice (3.6.3, page 101) [Deux phases simplexe révisé] Refaites les exercices 3.5.1 avec
la version révisée de l’algorithme du simplexe.
104 CHAPITRE 3. ALGORITHME DU SIMPLEXE
Chapitre 4
Dualité
Sujets du chapitre
‚ Théorie de la dualité linéaire.
‚ Algorithme dual du simplexe.
‚ Un lien avec la théorie des jeux.
105
106 CHAPITRE 4. DUALITÉ
Introduction
Proposition 4.1.1 Si rxB , xN “ 0s est une solution de base optimale du problème (2.2),
alors π “ cB B ´1 est une solution réalisable au problème (nommé dual).
max πb
(4.1)
sujet à πA ď c
Examinons maintenant les deux problèmes (2.2) et (4.1). Soit x et π des solutions réalisables
de ces deux problèmes. On déduit directement l’importante relation que πb “ πAx ď cx.
Maintenant, si on injecte rxB , 0s solution optimale de (2.2) et π “ cB B ´1 dans (4.1), on
retrouve πb “ πBxB “ cB xB “ cx et donc l’égalité nous confirme que π “ cB B ´1 est
solution optimale de (4.1). Consignons ce résultat dans la proposition suivante.
Proposition 4.1.2 Si rxB , xN “ 0s est une solution de base optimale du problème (2.2),
alors π “ cB B ´1 est une solution optimale du problème (4.1)
.
Une propriété intuitive est que le dual du dual est le primal original.
.
Preuve Nous allons démontrer cette proposition en ramenant le problème (4.1) à la forme
standard. Cet exercice nous permet d’utiliser des manipulations classiques et d’en introduire
la notation habituelle. Pour transformer en égalités les contraintes d’inégalité, nous intro-
duisons des variables d’écart α ě 0 et récrivons πA ď c sous la forme πA ` α “ c. Pour
que toutes les variables qui définissent le problème soient non-négatives, nous remplaçons les
4.1. THÉORIE DE LA DUALITÉ 107
max pβ ` ´ β ´ qb
sujet à pβ ` ´ β ´ qA ` α “ c
β` ě 0 (4.2)
β´ ě 0
α ě 0.
Le problème (4.3) est de la forme standard du simplexe, nous pouvons donc écrire son dual
max cz
sujet à Az ď ´b
(4.4)
´ Az ďb
Iz ď 0,
Corollaire 4.1.1 [Écarts complémentaires] Ajoutons des variables d’écart s de telle sorte
que les contraintes du problème (4.1) deviennent yA ` s “ c avec s ě 0 ; alors, si x et ry, ss
sont des solutions optimales pour les problèmes (2.2) et (4.1) respectivement, sx “ 0.
Preuve La partie a) découle des propositions précédentes. De même, pour la partie c), si
un problème n’est pas réalisable, l’autre ne peut pas posséder de solution optimale car sinon,
de la contredirait la partie a). On laisse en exercice le soin de trouver un exemple où ni le
primal, ni le dual ne possèdent de solution réalisable.
Pour justifier la parties b), examinons le problème (4.1). Ses contraintes sont πA ď c,
et donc πAx ď cx pour tout vecteur π réalisable pour le problème (4.1). Maintenant, en
supposant que x est réalisable pour le problème (2.2), on retrouve Ax “ b de sorte que l’on
obtient πb ď cx, c’est-à-dire que toute solution réalisable pour le dual possède une valeur de
fonction objectif à la valeur de l’objectif primal pour une solution réalisable quelconque. Si
le primal n’est pas borné, c’est qu’aucun π ne satisfait πb ą ´8. l
Théorème 4.1.5 (Dualité forte) Si le problème (2.2) possède une solution optimale x˚ ,
alors le problème (4.1) possède une solution optimale π ˚ telle que cx˚ “ π ˚ b.
Ce dernier théorème est en fait une conséquence directe des théorèmes 3.3.3 et 4.1.4.
Nous allons maintenant ramener le dual sous forme standard du simplexe, c’est-à-dire avec
seulement des contraintes d’égalité et des variables non négatives. Pour ce faire, observons
que y1 est déjà non négative et y2 est non positive. Effectuons un changement de variable
ȳ2 “ ´y2 de sorte que ȳ2 est non négative. De plus, ajoutons des variables d’écart y3 ě 0,
y4 ě 0. Enfin, remplaçons le max par un min en changeant de signe les coefficients de la
fonction objectif. Tout ça nous donne :
min ´2y1 ` 3ȳ2
sujet à 2y1 ´ ȳ2 ` y3 “ 1
y1 ´ 3ȳ2 ` y4 “ ´1
y1 , ȳ2 , y3 , y4 ě 0
Obtenons maintenant le dual de ce dernier problème qui est sous forme standard.
max z1 ´ z2
sujet à 2z1 ` z2 ď ´2
´z1 ´ 3z2 ď 3
z1 ď 0
z2 ď 0.
Nos variables z sont non positives, effectuons le changement de variables z̄ “ ´z. De plus,
transformons le max en min en inversant les signes des coefficients. Donc, on inverse les z en
z̄ et on inverse les signes, deux inversions de signe se cancellent.
min z̄1 ´ z̄2
sujet à ´2z̄1 ´ z̄2 ď ´2
z̄1 ` 3z̄2 ď 3
z̄1 ě 0
z̄2 ě 0.
Finalement, inversons la première inégalité (multiplions la par ´1) et ajoutons une variable
de surplus z3 ě 0 et une d’écart z4 ě 0.
min z̄1 ´ z̄2
sujet à 2z̄1 ` z̄2 ´ z3 “ 2
z̄1 ` 3z̄2 ` z4 “ 3
z̄1 , z̄2 , z3 , z4 ě 0,
qui est exactement le problème (4.69).
min cx
sujet à Ax ď b
x ě 0,
max yb
sujet à yA ď c
yď0
En fait, on peut montrer que le dual peut être obtenu selon des règles sans passer à
chaque fois par la transformation en forme standard. Le tableau suivant énumère les règles.
Par exemple, la forme (2.2) comporte des contraintes de type “ et des variables de type
ě 0. Selon la table 4.1, les variables du dual sont libres et ses contraintes sont de type ď 0,
exactement le problème (4.1). Un autre exemple, l’exercice 4.1.1 : contraintes de type ď,
donc variables duales de type ď 0 ; variables de type ě 0, donc contraintes duales de type
ď.
primal dual
min max
c : coût b : coût
b : terme de droite c : terme de droite
contrainte i du type ě variable i du type ě 0
contrainte i du type “ variable i du type libre
contrainte i du type ď variable i du type ď 0
variable i du type ě contrainte i du type ď 0
variable i du type libre contrainte i du type “
variable i du type ď contrainte i du type ě 0
max x 1 ` x2
sujet à ´3x1 ` 2x2 ď ´1
(4.6)
x 1 ´ x2 ď 2
x1 , x2 ě 0.
Nous aurons deux variables duales car notre exemple comporte deux contraintes. La table 4.1
nous informe que pour un problème de maximisation, des contraintes de type “ď” corres-
pondent à des variables duales x ě 0 et des variables primales de type “ě 0" correspondent
à des contraintes du type “ě 0”, donc notre problème dual s’écrit
Exercice 4.1.2 [Formulation du problème dual] Reprenez les problèmes de l’exercice 2.3.3
page 62 et écrivez le dual de chacun en utilisant deux techniques :
a) à partir de la forme standard du simplexe et en simplifiant le dual ainsi obtenu ;
b) en utilisant la table 4.1.
Exercice 4.1.3 [Auto dual] Écrivez le dual du problème suivant en utilisant la table 4.1.
min c1 x1 ` c2 x2
sujet à A11 x1 ` A12 x2 ď b1
A21 x1 ` A22 x2 “ b2
x1 ě 0,
Exercice 4.1.6 [Irréalisable primal-dual] Fournissez une paire de programmes duaux pour
lesquels aucun n’est réalisable.
min cx
sujet à a ď Ax ď b
lď x ďu
Exercice 4.1.8 [AutoDual] Vérifiez que le programme suivant est son propre dual :
min c1 x 1 ´ c2 x 2
sujet à At x2 ď ct1
Ax1 “ ct2
x1 ě0
min ´2x1 ´ x2
8
sujet à x1 ` x
3 2
ď 4
x1 ` x2 ď 2
2x1 ď 3,
et
max x1 ` 2x2
sujet à 2x1 ` x2 ě 4
x1 ` x2 ď 8
´x1 ` x2 ď 4
x1 ď 5
x1 , x2 ě 0.
Pour chacun,
a) Résoudre graphiquement
b) Écrire le dual de ce problème.
c) Résoudre le dual en utilisant les écarts complémentaires.
4.2. ALGORITHME DUAL DU SIMPLEXE 115
x1 x2 x3 x4 x5
4 1 1 0 0 0
´1 ´1 0 1 0 ´8
´8 1 9 0 1 ´1
116 CHAPITRE 4. DUALITÉ
Choisissons donc ı̄ “ 1, la ligne ayant la valeur la plus négative dans la dernière colonne.
C’est donc la variable x4 qui quittera B. Deux colonnes de cette ligne numéro un ont un
élément négatif, alors le critère ̄ “ arg maxaı̄j ă0 p acı̄j̄ q s’applique aux colonnes un et deux. Les
quotients en question sont ´4 et ´1, le maximum est donc atteint pour la colonne deux et
c’est x2 qui entrera dans B. On effectue un pivot sur l’élément de première ligne et seconde
colonne.
x1 x2 x 3 x4 x5
3 0 1 1 0 ´8
1 1 0 ´1 0 8
´9 0 9 1 1 ´9
Il n’y a plus que la seconde ligne négative dans la dernière colonne. Il y a également une
seule colonne négative dans cette ligne numéro deux, la première. On effectue donc le pivot
sur l’élément de ligne deux, colonne un de valeur ´9.
x1 x2 x3 x4 x5
4 1
0 0 4 3 3
´11
8 1
0 1 1 ´9 9
7
1 0 ´1 ´ 19 ´ 91 1
Exercice 4.2.2 [Algorithme dual du simplexe papier] Encore avec l’outil informatique,
générez au moins quatre problèmes aléatoires dual réalisables et résolvez-les par l’algo-
rithme dual du simplexe sur papier dans la forme tableau plutôt que dictionnaire. Effectuez
vos calculs en fractions. Utilisez l’outil pour valider vos calculs.
4.2. ALGORITHME DUAL DU SIMPLEXE 117
Exercice 4.2.4 [Dual] Nous allons refaire le tout directement sur le dual.
a) Écrivez le dual du problème (2.6).
b) Ramenez le dual sous la forme standard de la forme (2.2).
c) Faites un graphique du dual et établissez la correspondance entre les intersections des
droites du primal (figure 2.9) et celles du dual.
d) Établissez la correspondance entre les solutions de base du primal et du dual, tous deux
standartisés.
e) Appliquez l’algorithme primal du simplexe à la formulation du dual standardisée.
f) Constatez que l’algorithme primal appliqué au dual est équivalent l’algorithme dual
appliqué au primal.
Ces observations simples sont cependant trompeuses. Nous avons choisi un exemple bi-
dimensionnel pour pouvoir en faire des illustrations. En général, le nombre de variables du
dual n’est pas égal au nombre de variables du primal. Il faut toujours garder en tête que
des illustrations nourrissent notre intuition, mais que la situation générale de dimension
plus grande que deux est considérablement plus complexe et que beaucoup d’aspects ne se
manifestent simplement pas en deux dimension. C’est le cas par exemple du phénomène de
cyclage de l’algorithme dont nous présenterons un exemple à la section 5.2 qui n’apparaît
pas en dimension inférieure à six.
On met sous forme canonique le problème et constate que la ligne des coûts est positive. On
peut alors appliquer l’algorithme dual du simplexe.
Ici encore, les solutions et mises-à-jour de B ´1 sont efficaces. Il est également possible de
mettre à jour les vecteurs c̄N plutôt que de les recalculer à partir d’un π réobtenu par le
système d’équations.
b“
“ ‰
´3 4 12 (4.11)
A“ » fi
3 ´1 1 ´2 0 0
– 2 1 0 1 1 0 fl (4.12)
´1 3 0 ´3 0 1
B ´1 “ » fi
1 0 0
– 0 1 0 fl (4.13)
0 0 1
iB “
“ ‰
3 5 6 (4.14)
iN =
“ ‰
1 2 4 (4.15)
Itération 1
1. xB “
“ ‰
´3 4 12
2. π “ cB B ´1
“ ‰
0 0 0 (4.16)
3. c̄N “ cN ´ πN “
“ ‰
11 11 1
8. B ´1 “ » fi
´1
2
0 0
1
–
2
1 0 fl
´3
2
0 1
Itération 2
1. xB “ “ ‰
3 5 33
2 2 2
2. π “ cB B ´1 “ ‰
´1
2
0 0 (4.17)
3. c̄N “ cN ´ πN “ “ ‰
25 21 1
2 2 2
Solution optimale.
c“ “ ‰
25 21 1
2 2 2
0 0 0
bt “ “ ‰
3 5 33
2 2 2
122 CHAPITRE 4. DUALITÉ
A“ » fi
´3 1 ´1
2 2 2
1 0 0
7 1 1
–
2 2 2
0 1 0 fl
´11 9 ´3
2 2 2
0 0 1
Itération 2
Solution otimale
solution primal-réalisable : » fi
1 1
0 2 2
0 ´1
– 1 1 ´1
2 2
0 1 fl (4.25)
5 1
0 2 2
1 2
remettons le coût : » fi
1 ´1 0 0 0
– 1 1 ´1
0 1 fl (4.26)
2 2
0 52 1
2
1 2
4.3. UN LIEN AVEC LA THÉORIE DES JEUX 123
forme canonique :
» ´3 1
fi
0 2 2
0 ´1
– 1 1 ´1
2 2
0 1 fl (4.27)
5 1
0 2 2
1 2
Notions de stratégie
Dans un tel jeu, on appelle stratégie pure le choix R, P ou C. Évidemment, aucun joueur
sensé n’utiliserait une stratégie pure, car l’autre s’en apercevrait, et aurait gain de cause
pour la suite des tours.
On appelle stratégie mixte une combinaison de stratégies pures, habituellement tirées au
hasard, et la stratégie mixte se représente par les probabilités d’utiliser une stratégie pure.
Dans notre exemple, une stratégie mixte est un vecteur ppR , pP , pC q de probabilités de choisir
R, P ou C, et donc pR ` pP ` pC “ 1.
Représentation matricielle
L’enjeu peut se résumer dans une matrice. Un joueur lit la matrice ligne par ligne, l’autre
colonne par colonne. Pour le jeu RPC, la matrice A est la suivante :
R P C
R 0 1 ´1
(4.29)
P ´1 0 1
C 1 ´1 0
Pour une stratégie pure donnée par joueur, par exemple x “ R “ p1, 0, 0qt et y “
C “ p0, 0, 1q, le résultat du jeu est yAx “ `1, indiquantř řque le joueur x gagne car la roche
émousse les ciseaux. Pour une stratégie mixte, yAx “ i j Aij xi yj correspond à la moyenne
attendue des gains.
Pour ce jeu simpliste, il semble évident qu’aucun des joueurs n’a d’avantage, qu’à long
terme, les pertes et les gains vont s’équilibrer, et que cette uniformité assure que la stratégie
mixte optimale est p1{3, 1{3, 1{3q pour chacun des 2 joueurs.
Cependant, supposons simplement que nous modifions la matrice des gains comme suit :
R P C
R 0 1 ´2
(4.30)
P ´3 0 4
C 5 ´6 0
Quelle est alors la stratégie optimale des 2 joueurs ? Le jeu est-il toujours équitable dans le
sens que les gains et les pertes vont tendre à s’équilibrer à la longue pour les deux joueurs ?
C’est à ces deux questions que nous pourrons répondre après avoir démontré le théorème
fondamental de la théorie des jeux.
La matrice des gains s’interprète comme suit. Supposons que le joueur x utilise la stratégie
pure R, p1, 0, 0qt ; Ax “ p0, ´1, 1qt , ce qui fait que le joueur y devrait normalement utiliser
la stratégie pure P p0, 1, 0q. Maintenant, intuitivement, pour le jeu original, la stratégie
optimale pour le joueur x est p1{3, 1{3, 1{3qt . Ax “ p0, 0, 0qt , ce qui signifie que le joueur y,
4.3. UN LIEN AVEC LA THÉORIE DES JEUX 125
étant donné le choix stratégique du joueur x, peut choisir n’importe quelle stratégie puisque
son gain espéré est nul pour toute stratégie.
Examinons ce qui se passe avec la matrice (4.30) pour le choix stratégique x “ p1{3, 1{3, 1{3qt .
Ax “ p´1{3, 1{3, ´1{3qt et le joueur y a à sa disposition deux stratégies pures avantageuses,
et leur mélange, R, C.
En résumé, si le joueur x adopte sa stratégie, alors le joueur y obtient sa stratégie optimale
par la solution du problème linéaire
miny yAx
sujet à ye “1 (4.31)
y ě 0.
Il est naturel ici de dénoter les stratégies du joueur x en colonne, et celles du joueur y en ligne.
Ceci rappelle la dualité. On nomme vecteur stochastique un vecteur dont les composantes
sont non-négatives, et somment à un, i.e. ye “ 1, y ě 0.
Avec la notation adoptée, le joueur y minimise ses pertes alors que le joueur x maximise
ses gains. Puisque le joueur y définit sa stratégie par le problème linéaire (4.31), le joueur x
devra maximiser la fonction
maxx miny yAx
sujet à ye “1
(4.32)
et x “ 1
x, y ě 0.
Étant donnée une stratégie x, le joueur y peut toujours choisir une stratégie pure, corres-
pondant à un point extrême, solution de base réalisable des contraintes ye “ 1, y ě 0. Soient
donc ei les stratégies pures, le joueur x doit
max v
sujet à v ď eti Ax @i
(4.34)
et x “ 1
x ě 0,
ou encore
max v
sujet à ve ď Ax
(4.35)
et x “ 1
x ě 0.
126 CHAPITRE 4. DUALITÉ
9 maximize val_jeux : w ;
10
11 subject to
12 ligne { i in coups }: sum { j in coups } A [i , j ]* x [ j ] >= w ;
13 sto : sum { j in coups } x [ j ] = 1;
Exercice 4.3.1 [Joueur y] Complétez les détails conduisant au problème (4.38) du joueur
y. Complétez l’exercice en formulant un modèle générique du joueur y en Ampl en imitant
le code ci haut.
4.3. UN LIEN AVEC LA THÉORIE DES JEUX 127
Dans notre exemple, avec la matrice (4.29), les stratégies optimales sont x “ p1{3, 1{3, 1{3qt
et y “ p1{3, 1{3, 1{3q. La valeur des problèmes est 0, on parle alors d’un jeu matriciel à somme
nulle. Cela revient à dire qu’aucun des 2 joueurs n’est avantagé par le jeu.
Avec la matrice (4.30), les choses se compliquent un tout petit peu, évidemment. Les
stratégies optimales ne sont plus les mêmes, mais plus important, la valeur du jeu devient
´16{102, indiquant que le joueur y possède un avantage dans ce jeu.
Exercice 4.3.3 [Jeux] Résolvez le jeu avec la matrice (4.30), obtenez les stratégies, et
8
vérifiez que la valeur du jeu est ´ 51 . À la fin du chapitre, on retrouve l’exécution sous
forme de tableau de l’algorithme du simplexe pour calculer la stratégie x˚ optimale pour le
jeu RPC Roche-Papier-Ciseaux. Examinez la solution et déduisez-en la stratégie optimale
8
y ˚ . Pour être bien certain que vous avez déniché le bon y ˚ , vérifiez que y ˚ A “ ´ 51 1, la
valeur du jeu.
Exercice 4.3.4 [Solution avec Ampl] Formulez le fichier “.dat” du jeu Roche-Papier-
Ciseaux avec les coûts modifiés et obtenez la solution du joueur x avec Ampl.
Exercice 4.3.5 [Solution du joueur y avec Ampl] Utilisez Ampl et votre modèle du joueur
y optimiser le joueur y et constatez que vous aviez le bon y ˚ . Ampl affiche ses résultats en
8
virgule flottante, il faut convertir avec les fractions, 51 « 0.1568627451.
128 CHAPITRE 4. DUALITÉ
Exercice 4.3.6 [Jeu simple] Deux joueurs cachent une piece de monnaie, un 5 ou un 10
sous. Si elles sont pareilles, le joueur A empoche les 2, autrement le joueur B empoche les
2. Pour chacune de ces variantes, déterminez qui a l’avantage dans ce jeu et donnez les
stratégies de chacun des joueurs.
a) les joueurs utilisent leur propre argent, donc lorsque chacun cache un cinq sous, un des
joueurs perd cinq sous alors que l’autre gagne cinq sous ;
b) il y a une pile de cinq et dix sous disponibles ; lorsque chacun cache un cinq sous, le
joueur A gagne dix sous. Cette variante ressemble au jeu «pair–impair» dans lequel
chaque joueur montre un ou deux doigts. Si la somme S est paire, le joueur A gagne
alors que si elle est impaire, le joueur B gagne et le montant du gain S.
c) Considérez la variante de «pair–impair» dans laquelle la valeur du gain est le produit
des nombres de doigts mais le gagnant est toujours déclaré selon la parité de la somme.
Exercice 4.3.7 [Jeu de Morra] On considère un jeu où les deux joueurs montrent simul-
tanément soit un, soit deux doigts. En même temps qu’ils montrent leur(s) doigt(s), ils
annoncent un chiffre pour prédire la somme des doitgs. Le seul cas où un joueur fait des
points est lorsqu’il est le seul à avoir prédit la bonne somme et la dite somme est aussi le
nombre de points qu’il fait. Si les deux ont prédit la bonne somme, ils font 0, de même
que si le joueur a prédit la mauvaise somme.
a) Combien d’actions (ou coups) sont possibles pour chaque joueur ? Les sommes possibles
sont 2, 3 et 4.
b) Bien que légal, un joueur n’aura jamais intérêt à montrer un seul doigt et prédire 4, c’est
impossible. Établissez la sous-liste des actions possibles.
c) Établissez la matrice de rendement de ce jeu en considérant seulement les actions pos-
sibles.
d) Quelle est la valeur de ce jeu ? Utilisez Ampl pour le résoudre et obtenir la valeur
optimale de v.
e) Il n’y a pas une stratégie optimale unique pour les joueurs dans ce jeu. Si on calcule
Ax˚ , on obtient un vecteur ě 0 qui indique que le joueur y n’a aucune possibilité de gain
face à la stratégie x˚ . On constate que la structure de x˚ est xpαq “ p0, α, p1 ´ αq, 0qt .
Déterminez les conditions sur α pour que Axpαq ě 0. Toute valeur de xpαq avec α
respectant ces condition constitue une stratégie optimale pour le joueur x.
4.3. UN LIEN AVEC LA THÉORIE DES JEUX 129
c“ “ ‰
´7 1 ´1 1
0 ´1 3 3 3
0 3
0 0 (4.44)
bt “ “ ‰
0 0 0 1 (4.45)
A“ » fi
0 ´1 2 1 ´1 1 0 0 0
— 1 0 ´4 1 ´1 1
3 3 3
0 3
0 0 ffi
—
– 0 6 ´20 8 ´8 5
ffi (4.46)
3 3 3
0 3
1 0 fl
7 ´1 1 ´1
0 1 3 3 3
0 3
0 1
nouveau B = “ ‰
6 1 8 9 (4.47)
nouveau N = “ ‰
7 2 3 4 5 (4.48)
Itération 2 choix de la colonne : 3 dans N , 3 dans 1..n ; choix de la ligne : 1
c“ “ ‰
´13 3 ´3 7 1
0 6
0 2 2 6 3
0 0 (4.49)
130 CHAPITRE 4. DUALITÉ
bt “ “ ‰
0 0 0 1 (4.50)
A“ » fi
´1 1 ´1 1
0 2
1 2 2 2
0 0 0
— 1 ´2 2 1
3
0 1 ´1 3 3
0 0 ffi
—
– 0 8 10 5
ffi (4.51)
3
0 6 ´6 3 3
1 0 fl
13 ´3 3 ´7 ´1
0 6
0 2 2 6 3
0 1
nouveau B = “ ‰
3 1 8 9 (4.52)
nouveau N = “ ‰
7 2 6 4 5 (4.53)
Itération 3 choix de la colonne : 2 dans N , 2 dans 1..n ; choix de la ligne : 3
c“ “ ‰
51 ´51 31 27 13
0 0 0 8 8 8 16 16
0 (4.54)
bt “ “ ‰
0 0 0 1 (4.55)
A“ » fi
13 ´13 9 5 3
0 0 1 8 8 8 16 16
0
— 1 5 ´5 3 3 1
0 0 2 2 2 4 4
0 ffi
—
– 0 9 ´9 5 5 3
ffi (4.56)
1 0 4 4 4 8 8
0 fl
´51 51 ´31 ´27 ´13
0 0 0 8 8 8 16 16
1
nouveau B = “ ‰
3 1 2 9 (4.57)
nouveau N = “ ‰
7 8 6 4 5 (4.58)
Itération 4 choix de la colonne : 5 dans N , 5 dans 1..n ; choix de la ligne : 4
c“ “ ‰
0 0 0 0 0 0 0 0 1 (4.59)
bt “ “ ‰
13 20 6 8
51 51 17 51
(4.60)
A“ » fi
7 ´2 ´1 13
0 0 1 0 0 51 17 51 51
— 1 ´1 3 ´7 20
0 0 0 0 51 34 102 51
ffi
—
– 0 ´2 1 3 6
ffi (4.61)
1 0 0 0 17 34 34 17
fl
´31 ´9 ´13 8
0 0 0 ´1 1 51 34 102 51
4.4. RÉSUMÉ 131
nouveau B = “ ‰
3 1 2 5 (4.62)
nouveau N = “ ‰
7 8 6 4 9 (4.63)
Itération 5
Solution optimale
B= “ ‰
3 1 2 5 (4.67)
N= “ ‰
4 6 7 8 (4.68)
Itération 1
Solution optimale
4.4 Résumé
Nous avons retenu de l’algorithme du simplexe qu’une solution de base optimale sera
telle que yA ď c. Nous avons défini un problème dual qui s’écrit maxy yb sujet à yA ď c.
Après avoir remis le problème dual sous forme standard du simplexe et avoir écrit le dual
résultant, nous avons constaté que le dual du dual est le primal de départ. Nous avons ensuite
présenté une table de règles permettant de passer d’un modèle primal à son dual. En fait,
puisque le dual du dual est le primal, il vaut mieux parler de deux problèmes en relation de
dualité. Il n’y en a pas un qui mérite le titre de primal, mais on en désigne un comme primal
arbitrairement.
132 CHAPITRE 4. DUALITÉ
Ensuite, nous avons proposé un algorithme utilisant encore les tableaux du simplexe
mais avec des règles différentes de l’algorithme du simplexe que nous nommons désormais
algorithme primal. L’algorithme dual maintient toujours que c̄ “ c ´ πA ě 0. L’algorithme
dual consiste en les étapes suivantes :
1. choisir une ligne ı selon un terme négatif du vecteur B ´1 b, habituellement le plus négatif ;
2. choisir une colonne selon un test de ratio avec les éléments négatifs de la ligne choisie ;
c’est ce test qui permet d’assurer que c̄ demeure héréditairement non négatif.
3. mettre à jour le tableau en effectuant un pivot sur l’élément ı̄, ̄.
L’algorithme termine soit lorsque B ´1 b ě 0, on dit alors que la base courante est duale-
optimale, soit lorsque la ligne ı est non-négative, auquel cas le problème n’est pas (primal)
réalisable. Puisque le problème est dual-réalisable, primal irréalisable équivaut à dual non
borné.
On retient que c̄ “ c ´ πA ě 0 est notre condition d’optimalité pour le problème primal,
mais la condition de réalisabilité pour le dual. De même le primal est réalisable lorsque
B ´1 b ě 0, ce qui équivaut à l’optimalité du dual.
Si on dispose d’une solution de base, peu importe qu’elle soit réalisable (primale ou duale)
ou non, on peut toujours combiner les algorithmes primal et dual pour résoudre le problème.
On a deux possibilités : Phase I duale et phase II primale ou l’inverse.
Jeux Enfin, nous avons exploré une application en établissant un lien serré avec la théorie
des jeux.
Pour compléter, mentionnons qu’une grande partie de la popularité de l’optimisation
linéaire provient d’interprétations économiques aussi instructives qu’utiles. En voici une ré-
sumée. Le problème de la diète consiste, pour un client à choisir des quantités d’aliments xi
(variables primales) qui minimisent le coût d’achat cx tout en satisfaisant des contraintes
diététiques ai x ě bi (contenu suffisant de chacun de plusieurs nutriments). Le dual s’in-
terprète du point de vue d’un vendeur de pilules de nutriments. Il veut fixer le prix πj de
ses pilules de telle sorte que, compte tenu de la demande en nutriments b, il maximise son
profit πb tout en s’assurant que le coût des nutriments contenus dans chacun des l’aliment
ne dépasse pas le coût de l’aliment πAj ď cj .
min cx
sujet à Ax ď b
x ě 0,
max yb
sujet à yA ď c
yď0
Exercice (4.1.2, page 111) [Formulation du problème dual] Reprenez les problèmes de
l’exercice 2.3.3 page 62 et écrivez le dual de chacun en utilisant deux techniques :
a) à partir de la forme standard du simplexe et en simplifiant le dual ainsi obtenu ;
b) en utilisant la table 4.1.
Exercice (4.1.3, page 111) [Auto dual] Écrivez le dual du problème suivant en utilisant
la table 4.1.
min x1 ´ x2 ´ 2x3 ` 3x4
sujet à 2x3 ´ x4 ď 1
x3 ´ 3x4 ď ´1
(4.69)
2x1 ` x2 ě 2
x1 ` 3x2 ď 3
x1 , x2 , x3 , x4 ě 0,
134 CHAPITRE 4. DUALITÉ
Vérifiez que le dual est équivalent au problème lui même, donc que ce problème est son
propre dual !
Exercice (4.1.4, page 112) [Dualité] Considérez le problème linéaire le plus général en-
visageable
min c1 x1 ` c2 x2
sujet à A11 x1 ` A12 x2 ď b1
A21 x1 ` A22 x2 “ b2
x1 ě 0,
Exercice (4.1.6, page 113) [Irréalisable primal-dual] Fournissez une paire de programmes
duaux pour lesquels aucun n’est réalisable.
Exercice (4.1.7, page 113) [Dual] Fournissez l’expression du dual du programme suivant :
min cx
sujet à a ď Ax ď b
lď x ďu
Exercice (4.1.8, page 113) [AutoDual] Vérifiez que le programme suivant est son propre
dual :
min c1 x 1 ´ c2 x 2
sujet à At x2 ď ct1
Ax1 “ ct2
x1 ě0
min ´2x1 ´ x2
8
sujet à x1 ` x
3 2
ď 4
x1 ` x2 ď 2
2x1 ď 3,
4.5. TOUS LES EXERCICES DU CHAPITRES 135
et
max x1 ` 2x2
sujet à 2x1 ` x2 ě 4
x1 ` x2 ď 8
´x1 ` x2 ď 4
x1 ď 5
x1 , x2 ě 0.
Pour chacun,
a) Résoudre graphiquement
b) Écrire le dual de ce problème.
c) Résoudre le dual en utilisant les écarts complémentaires.
Exercice (4.2.2, page 116) [Algorithme dual du simplexe papier] Encore avec l’outil in-
formatique, générez au moins quatre problèmes aléatoires dual réalisables et résolvez-les
par l’algorithme dual du simplexe sur papier dans la forme tableau plutôt que dictionnaire.
Effectuez vos calculs en fractions. Utilisez l’outil pour valider vos calculs.
Exercice (4.2.4, page 118) [Dual] Nous allons refaire le tout directement sur le dual.
a) Écrivez le dual du problème (2.6).
b) Ramenez le dual sous la forme standard de la forme (2.2).
c) Faites un graphique du dual et établissez la correspondance entre les intersections des
droites du primal (figure 2.9) et celles du dual.
d) Établissez la correspondance entre les solutions de base du primal et du dual, tous deux
standartisés.
e) Appliquez l’algorithme primal du simplexe à la formulation du dual standardisée.
f) Constatez que l’algorithme primal appliqué au dual est équivalent l’algorithme dual ap-
pliqué au primal.
136 CHAPITRE 4. DUALITÉ
Exercice (4.2.5, page 123) [Phase I primale—phase II duale] Reprenez l’exemple en uti-
lisant un membre de droite bidon pour faire une phase I primale, puis remettre le membre
de droite original et compléter la solution par une phase II duale.
Exercice (4.3.1, page 126) [Joueur y] Complétez les détails conduisant au problème (4.38)
du joueur y. Complétez l’exercice en formulant un modèle générique du joueur y en Ampl
en imitant le code ci haut.
Exercice (4.3.2, page 127) [Preuve] Fournissez les détails de la preuve
Exercice (4.3.3, page 127) [Jeux] Résolvez le jeu avec la matrice (4.30), obtenez les stra-
8
tégies, et vérifiez que la valeur du jeu est ´ 51 . À la fin du chapitre, on retrouve l’exécution
sous forme de tableau de l’algorithme du simplexe pour calculer la stratégie x˚ optimale pour
le jeu RPC Roche-Papier-Ciseaux. Examinez la solution et déduisez-en la stratégie optimale
8
y ˚ . Pour être bien certain que vous avez déniché le bon y ˚ , vérifiez que y ˚ A “ ´ 51 1, la valeur
du jeu.
Exercice (4.3.4, page 127) [Solution avec Ampl] Formulez le fichier “.dat” du jeu Roche-
Papier-Ciseaux avec les coûts modifiés et obtenez la solution du joueur x avec Ampl.
Exercice (4.3.5, page 127) [Solution du joueur y avec Ampl] Utilisez Ampl et votre
modèle du joueur y optimiser le joueur y et constatez que vous aviez le bon y ˚ . Ampl affiche
8
ses résultats en virgule flottante, il faut convertir avec les fractions, 51 « 0.1568627451.
Exercice (4.3.6, page 128) [Jeu simple] Deux joueurs cachent une piece de monnaie, un
5 ou un 10 sous. Si elles sont pareilles, le joueur A empoche les 2, autrement le joueur B
empoche les 2. Pour chacune de ces variantes, déterminez qui a l’avantage dans ce jeu et
donnez les stratégies de chacun des joueurs.
a) les joueurs utilisent leur propre argent, donc lorsque chacun cache un cinq sous, un des
joueurs perd cinq sous alors que l’autre gagne cinq sous ;
b) il y a une pile de cinq et dix sous disponibles ; lorsque chacun cache un cinq sous, le joueur
A gagne dix sous. Cette variante ressemble au jeu «pair–impair» dans lequel chaque joueur
montre un ou deux doigts. Si la somme S est paire, le joueur A gagne alors que si elle est
impaire, le joueur B gagne et le montant du gain S.
c) Considérez la variante de «pair–impair» dans laquelle la valeur du gain est le produit des
nombres de doigts mais le gagnant est toujours déclaré selon la parité de la somme.
Exercice (4.3.7, page 128) [Jeu de Morra] On considère un jeu où les deux joueurs montrent
simultanément soit un, soit deux doigts. En même temps qu’ils montrent leur(s) doigt(s),
ils annoncent un chiffre pour prédire la somme des doitgs. Le seul cas où un joueur fait des
points est lorsqu’il est le seul à avoir prédit la bonne somme et la dite somme est aussi le
nombre de points qu’il fait. Si les deux ont prédit la bonne somme, ils font 0, de même que
si le joueur a prédit la mauvaise somme.
4.5. TOUS LES EXERCICES DU CHAPITRES 137
a) Combien d’actions (ou coups) sont possibles pour chaque joueur ? Les sommes possibles
sont 2, 3 et 4.
b) Bien que légal, un joueur n’aura jamais intérêt à montrer un seul doigt et prédire 4, c’est
impossible. Établissez la sous-liste des actions possibles.
c) Établissez la matrice de rendement de ce jeu en considérant seulement les actions possibles.
d) Quelle est la valeur de ce jeu ? Utilisez Ampl pour le résoudre et obtenir la valeur optimale
de v.
e) Il n’y a pas une stratégie optimale unique pour les joueurs dans ce jeu. Si on calcule Ax˚ ,
on obtient un vecteur ě 0 qui indique que le joueur y n’a aucune possibilité de gain face à la
stratégie x˚ . On constate que la structure de x˚ est xpαq “ p0, α, p1 ´ αq, 0qt . Déterminez
les conditions sur α pour que Axpαq ě 0. Toute valeur de xpαq avec α respectant ces
condition constitue une stratégie optimale pour le joueur x.
138 CHAPITRE 4. DUALITÉ
Chapitre 5
Convergence de l’algorithme du simplexe
Sujets du chapitre
‚ Dégénérescence.
‚ Cyclage de l’algorithme du simplexe.
‚ Règles d’anti-cyclage.
‚ Convergence de l’algorithme du simplexe.
139
140 CHAPITRE 5. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE
Introduction
Nous avons justifié que les variantes de l’algorithme du simplexe étaient convergentes en
utiisant toujours l’hypothèse simplificatrice de non dégénérescence. Nous abordons dans ce
chapitre les difficultés associées à cette dégénérescence.
5.1 Dégénérescence
Jusqu’à maintenant, nous avons escamoté les difficultés causées par la dégénérescence en
supposant systématiquement que xB ą 0, et que le choix de la variable sortante était unique
dans l’algorithme 1.1. Penchons-nous maintenant sur le problème de la dégénérescence.
Ce phénomène peut se manifester pour le problème (2.2) tout comme pour son dual (4.1),
où il s’énonce comme suit : le vecteur de coût réduit cN ´πN associé à une solution réalisable
de base rxB , 0s possède une composante nulle.
Dans le cas de dégénérescence du problème primal (2.2), il est probable que l’on puisse
trouver une autre décomposition rrB | N ss décrivant la même solution réalisable xB puisque
sa composante nulle n’appartient pas naturellement aux composantes B. Dans le second
cas, il est possible de modifier la partition rrB | N ss en changeant la solution réalisable,
mais sans modifier la valeur de la fonction objectif. Dans chacun de ces cas, le fait de
changer de partition rrB | N ss n’entraîne pas de diminution de la fonction objectif, et il faut
raffiner l’algorithme pour pouvoir démontrer qu’il ne produit pas de cycle de partitions.
Nous illustrerons un tel cycle à la section prochaine, et proposerons une analyse d’une règle
permettant d’éviter ce phénomène de cyclage.
b) Est-il vrai que le problème (4.1) possède toujours plus d’une solution lorsque le pri-
mal (2.2) possède une solution dégénérée ?
xij ě 0, i “ 1, 2, . . . n, j “ 1, 2, . . . n.
Trouvez un vecteur c pour lequel ce problème possède des bases dégénérée simultanément
pour les problèmes (2.2) et (4.1).
En utilisant les tableaux pour représenter les itérations, après avoir ajouté des variables
x5 et x6 qui constituent nos variables de base de départ, nous obtenons un premier tableau.
x1 x2 x3 x4 x5 x6
´2.3 ´2.15 13.55 0.4 0
0.4 0.2 ´1.4 ´0.2 1 0
´7.8 ´1.4 7.8 0.4 1 0
La colonne x1 possède le coût le plus faible (-2.3) et l’élément positif de la colonne est sur la
142 CHAPITRE 5. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE
ligne un. On effectue une opération pivot sur cet élément (0.4) et obtient le second tableau.
x1 x2 x3 x4 x5 x6
´1 5.5 ´0.75 5.75 0
1 0.5 ´3.5 ´0.5 2.5 0
2.5 ´19.5 ´3.5 19.5 1 0
Ici, la seconde colonne a le coût le plus faible les deux lignes ont un élément positif et un
quotient nul ; comme souvent, on choisit la ligne avec le plus gros élement invoquant la
meilleure stabilité numérique.
x1 x2 x3 x4 x5 x6
´2.3 ´2.15 13.55 0.4 0
1 0.4 0.2 ´1.4 ´0.2 0
1 ´7.8 ´1.4 7.8 0.4 0
Maintenant, on peut observer que ce troisième tableau est un simple décalage circulaire (de
deux colonnes) du premier. Par conséquent, après deux autres itérations, nous retrouverons
un tableau encore décalé de deux colonnes, et finalement après un total de six itération, nous
retrouverons le tableau initial.
Il devrait être clair que les règles utilisées pour déterminer les variables entrantes et
sortantes influencent le comportement de l’algorithme du simplexe, et que l’exemple de
cyclage précédent ne vaut que pour notre règle d’entrer la variable de coût réduit minimum
et de sortir la première variable (si plusieurs peuvent sortir).
Cet exemple produit un cycle parce que deux variables de base sont nulles, et selon les
règles d’entrée et de sorties, aucun pivot ne change de valeur de x, mais les pivots changent
uniquement la décomposition rrB | N ss.
L’autre règle que nous présentons fait intervenir la notion d’ordre lexicographique de
vecteurs.
L
Définition 5.3.2 [Ordre lexicographique] Un vecteur v P Rn est dit lex-positif, noté v ě 0
L
si sa première composante non-nulle est positive ; v “ 0 est lex-zéro, noté v “ 0.
L
Utilisant cette définition, on peut comparer deux vecteurs par l’équivalence v ě u ðñ
L
v ´ u ě 0, et définir le lex-min d’un ensemble de vecteurs tvi u comme celui (ou ceux) pour
L
lesquels vi ě vı̄ , @i.
La règle de pivot lexicographique consiste à choisir parmi les indices i qui atteignent le
xi
mini:δxi ą0 p δxi
q celle dont la ligne complète pB ´1 N qi est lex-min de toutes les lignes telles que
δxi “ pB ´1 N̄ qi ą 0. Remarquons que l’ordre des composantes de Rn est important, et que
malgré que nous regroupions en deux ensembles les variables, les comparaisons lexicogra-
phiques doivent s’effectuer selon l’ordre des variables du problème original (2.2).
Définition 5.3.3 [Règle lexicographique d’anti-cyclage] Supposons que toutes les lignes de
L
la matrice A soient lex-positives : ai ě 0. On peut choisir toute colonne ̄ telle que c̄ ´z̄ ă 0 ;
la variable sortante est choisie selon le critère lex-min comme suit : soit Ā “ B ´1 rb : As, la
matrice transformée dont les lignes sont āi . ı̄ satisfait
āı̄ L āi
ă , @i : āī ą 0.
āı̄̄ āī
Remarquons que sous l’hypothèse que A est de rang m, aucune paire de lignes de A n’est
proportionnelle, et donc l’indice ı̄ ainsi défini est unique. Remarquons également qu’il est
toujours possible de démarrer l’algorithme du simplexe de sorte que les lignes de la matrice
Ā soient lex-positives.
Exercice 5.3.2 [Valeur optimale] Quelle est la valeur optimale du problème linéaire sur
l’exemple de cyclage ?
144 CHAPITRE 5. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE
Exercice 5.3.3 [Deux phases] Proposez une méthode, utilisant deux phases, permettant
que pour chacune des deux phases, le tableau initial comporte des lignes lex-positives.
puisque par hypothèse ā0̄ ă 0 (critère d’entrée) et toutes les lignes sont lex-positives. Par
conséquent l’algorithme ne peut pas cycler, car il ne peut pas réexaminer deux fois une même
base. l
Le résultat précédent permet de garantir que l’algorithme du simplexe ne termine pas avec
des coûts relatifs négatifs : en effet, la règle d’entrée choisit un indice de coût relatif négatif,
et la règle d’anti cyclage assure que la décomposition rrB | N ss ne sera jamais revisitée, donc
la seule possibilité est de terminer avec des coûts relatifs non-négatifs. Ceci démontre le
théorème de dualité forte.
Théorème 5.4.2 (Dualité forte) Si le problème (2.2) possède une solution optimale x˚ ,
alors le problème (4.1) possède une solution optimale π ˚ telle que cx˚ “ π ˚ b.
Preuve Soit x˚ la solution optimale obtenue par l’algorithme du simplexe utilisant une
règle d’anti-cyclage, rrB | N ss la partition optimale et π ˚ “ cB B ´1 les multiplicateurs associés.
Alors, les coûts relatifs c ´ π ˚ N sont non-négatifs. Par conséquent, π ˚ est une solution
réalisable pour le dual. De plus, π ˚ b “ cB B ´1 b “ cB x˚B “ cx˚ . l
5.5 Résumé
Nous avons présenté un exemple où l’algorithme du simplexe cycle, tourne en rond.
Nous avons introduit une variante de règle de pivot qui assure que l’algorithme résultant ne
cycle pas, ce qui permet de garantir sa terminaison en un point satisfaisant les conditions
nécessaires d’optimalité équivalentes au théorème de dualité forte.
La dégénérescence est le phénomène qu’une composante des indices de base i P B voit
la valeur égale à zéro (rB ´1 bsi “ 0). On parle de dégénérescence primale. La dégénérescence
duale est associée à une composante j P N telle que c̄j “ 0. Dans les deux cas, il y a moyen
d’échanger deux indice entre B et N et obtenir le même point x mais pas la même partition
de base.
146 CHAPITRE 5. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE
xij ě 0, i “ 1, 2, . . . n, j “ 1, 2, . . . n.
Trouvez un vecteur c pour lequel ce problème possède des bases dégénérée simultanément
pour les problèmes (2.2) et (4.1).
Exercice (5.3.2, page 143) [Valeur optimale] Quelle est la valeur optimale du problème
linéaire sur l’exemple de cyclage ?
Exercice (5.3.3, page 144) [Deux phases] Proposez une méthode, utilisant deux phases,
permettant que pour chacune des deux phases, le tableau initial comporte des lignes lex-
positives.
*Exercice (5.4.1, page 145) [Théorie] Démontrez la formule utilisée dans la preuve du
théorème 5.4.1 donnant la mise à jour de la ligne 0 après un pivot.
148 CHAPITRE 5. CONVERGENCE DE L’ALGORITHME DU SIMPLEXE
Chapitre 6
Analyse de sensibilité
Sujets du chapitre
‚ Analyse de sensibilité.
‚ Analyse post optimale.
‚ Algorithme paramétrique.
149
150 CHAPITRE 6. ANALYSE DE SENSIBILITÉ
Introduction
Une fois qu’il a résolu un modèle d’optimisation linéaire, l’utilisateur se pose souvent des
questions du genre
‚ que se passerait-il si le coût de telle ou telle ressource augmentait ?
‚ que se passerait-il si telle ressource était ajoutée au modèle à tel prix ?
‚ que se passerait-il si telle exigence était modifiée ?
On parle alors d’analyse post-optimale, aussi nommée analyse de sensibilité. Souvent, on
précise la question en demandant “jusqu’à quel point peut-on augmenter le coût de telle
ressource sans que le programme de production ne change”. Ce degré d’augmentation se
formulera à l’aide d’un paramètre et on s’intéressera à analyser la plage du paramètre qui
assure que le programme de production optimal ne change pas.
6.1 Un exemple
Revenons au tout premier modèle spécifique introduit à la section 1.1 et résolu par l’al-
gorithme du simplexe à la section 3.4.2.
min2 ´1.5x1 ´ x2
xPR
sujet à x1 ` x2 ď 400
2x1 ` x2 ď 600
x2 ď 300
x1 , x2 ě 0
x1 x2 x3 x4 x5
1 1
0 0 2 2
0 500
0 1 2 ´1 0 200 (6.1)
1 0 ´1 1 0 200
0 0 ´2 1 1 100
On peut
¨ voir dans
˛ ce tableau que les variables
¨ de base
˛ optimales sont B “ t2, 1, 5u, la matrice
1 1 0 2 ´1 0
B “ ˝1 2 0‚ et son inverse B ´1 “ ˝´1 1 0‚.
1 0 1 ´2 1 1
6.1. UN EXEMPLE 151
Exercice 6.1.2 [Ajout de variable] Complétez les calculs pour restaurer l’optimalité de
cet exemple.
x1 x2 x3 x4 x5 x6
1 1
0 0 2 2
0 0 500
0 1 2 ´1 0 0 200
(6.2)
1 0 ´1 1 0 0 200
0 0 ´2 1 1 0 100
1 2 0 0 0 1 500
6.1. UN EXEMPLE 153
Ce tableau n’est pas sous forme canonique, il faut introduire des zéros dans la nouvelle
contrainte aux positions 1 et 2.
x1 x2 x3 x4 x5 x6
1 1
0 0 2 2
0 0 500
0 1 2 ´1 0 0 200
(6.3)
1 0 ´1 1 0 0 200
0 0 ´2 1 1 0 100
0 0 ´3 1 0 1 ´100
Les conditions d’application de l’algorithme du simplexe dual sont satisfaites, ce qui permet-
tra de restaurer la réalisabilité.
Exercice 6.1.3 [Ajout de contrainte] Complétez les calculs pour restaurer la réalisabilité
de cet exemple.
x1 x2 x3 x 4 x5
0 1 1 0 2 20
(6.4)
0 ´1 5 1 ´1 20
1 4 ´1 0 1 10
d) On introduit une nouvelle variable x6 avec coefficients pc6 , a16 , a26 qt “ p´3, 1, 2qt .
i) Que devient alors le tableau (6.10) ?
ii) Le nouveau tableau est-il optimal ? Si non, déterminez une solution optimale du nou-
veau problème.
e) On introduit une nouvelle contrainte 2x1 ` 3x2 ` 3x3 ď 25 dans le problème original. Le
nouveau problème réalisable. Déterminez en une solution de base réalisable optimale.
f) On introduit une nouvelle contrainte 3x1 ` 2x2 ` 3x3 ď 25 dans le problème original. Le
nouveau problème n’est pas réalisable. Déterminez en une solution réalisable optimale.
Le tableau associé à la solution optimale est le suivant (x5 , x6 et x7 sont des variables
d’écart).
x1 x2 x3 x4 x5 x6 x7
7
5
0 0 12 5
1
5
4
5
0 11
3 4 2 1
10
1 0 5 5 10
0 4 (6.5)
1 2 1 3
´ 10 0 1 5 5 10 0 5
1
2
0 0 10 1 ´ 21 1 11
a) De quelle quantité faut-il modifier le coût c4 pour qu’il devienne avantageux de rendre
x4 positive ?
b) Déterminez l’intervalle de variation du coût c2 pour que la solution demeure optimale.
c) Déterminez l’intervalle de variation du terme de droite de la seconde contrainte (valeur
nominale de 12) pour que la base optimale demeure réalisable et optimale.
d) On introduit une nouvelle variable x8 ayant 1 comme coefficient dans chacune des trois
contraintes et un coût c8 “ ´2. Déterminez une solution optimale de ce nouveau pro-
blème.
e) On introduit une nouvelle contrainte x1 ` x2 ` x3 ` x4 ď 15 dans le problème original.
Le nouveau problème possède-t-il une solution réalisable ? Si oui, déterminez sa solution
optimale.
6.1. UN EXEMPLE 155
f) On suppose que les coefficients de la variable x1 dans le problème original sont a¨1 “
p3, ´3, 2qt . La solution du tableau (6.11) est-elle toujours optimale pour le nouveau
problème ? Si non, déterminez la solution optimale.
Exercice 6.1.7 [Sensibilité] Soit un problème sous forme standard pour lequel on aboutit
au tableau optimal suivant. La première ligne est le vecteur c original et la seconde la ligne
des coûts du tableau final.
x1 x2 x 3 x4 x5
´2 ´3 ´1 0 0
0 0 4 3 4 8 (6.6)
1 0 1 3 ´1 1
0 1 1 ´1 2 2
156 CHAPITRE 6. ANALYSE DE SENSIBILITÉ
On suppose que les variables x4 et x5 sont des variables d’écart de sorte que l’inverse de
la base optimale B ´1 se retrouve dans les colonnes 4 et 5 du tableau.
a) De combien faut-il augmenter c3 pour que la base courante cesse d’être optimale ? Trou-
vez une solution optimale pour c3 “ ´6.
b) De combien peut-on faire varier c1 pour que la base courante demeure optimale ?
c) Trouvez la plus grande et plus petite valeur de λ pour que la solution demeure optimale
si c est remplacé par c ` λp0, 0, ´1, 1, 2q.
d) De combien b2 (sa valeur originale) peut-il varier avant que la base courante cesse d’être
optimale ? (Note : pas besoin de calculer la valeur originale de b2 ).
e) Trouvez une solution réalisable et optimale par l’algorithme dual du simplexe quand b2
est augmenté de deux unités.
Exercice 6.1.8 [Sensibilité] Soit un problème sous forme standard pour lequel on aboutit
au tableau optimal suivant. La première ligne est le vecteur c original et la seconde la ligne
des coûts du tableau final.
x1 x2 x 3 x4 x5
´2 ´3 ´1 0 0
0 0 3 3 1 8 (6.7)
1 0 ´1 3 ´1 1
0 1 2 ´1 1 2
On suppose que les variables x4 et x5 sont des variables d’écart de sorte que l’inverse de
la base optimale B ´1 se retrouve dans les colonnes 4 et 5 du tableau.
a) Donnez un intervalle de variation de c2 pour que la solution reste optimale. Trouvez une
solution optimale pour c2 “ ´1.
b) Trouvez un intervalle de λ pour`que ˘ la base t1, 2u demeure optimale 1et réalisable si le
1
vecteur b est remplacé par b ` λ ´1 . Résoudre le problème pour λ “ 2 .
c) Trouvez une solution optimale si une nouvelle contrainte x1 ` x3 ě 2 est ajoutée au
problème original.
6.2. ALGORITHME AUTO-DUAL PARAMÉTRIQUE 157
Alors, la base courante est primal et dual-réalisable pour toute valeur de µ ě µ˚0 . Pour
µ “ µ˚ , soit on a un indice j P N tel que c̃j ` µ˚0 ĉj “ 0, soit on a un indice i P B tel que
xi ` µ˚0 x̂i “ 0. Dans le premier cas, on sélectionne j comme variable d’entrée, et on effectue
un pivot primal. Autrement, on sélectionne i comme variable de sortie, et effectue un pivot
dual. Après le pivot, on aura de nouvelles valeurs de x̃B , c̃N , x̂B , ĉN , et la relation (6.8)
nous donnera une nouvelle valeur de µ˚1 , et l’algorithme continue ainsi jusqu’à ce que µ˚k ă 0.
Comme alors la base courante sera optimale et réalisable pour toute valeur de µk´1 ě µ ě µ˚k ,
en particulier, la base sera optimale pour µ “ 0, ce que nous voulions obtenir.
min z “ x1 ´ x2
sujet à 2x1 ` x2 ě 2
x1 ` 3x2 ď 3
x1 , x2 ě 0
158 CHAPITRE 6. ANALYSE DE SENSIBILITÉ
Exercice 6.2.1 [Valeur de z] Complétez le tableau pour avoir une expression de la valeur
de ´z à chaque itération, et donc pour la solution optimale.
Exercice 6.2.2 [Intervalle final] Quel est l’intervalle de µ qui rend le tableau final réali-
sable et optimal ?
x1 x2 x3 x 4 x5
2µ ´ 1 0 3 ´ µ 0 0
´1 1 1 0 0 µ´1 (6.9)
´3 0 2 1 0 3µ ´ 4
´1 0 ´1 0 1 2
xB Ð x̃
Ici encore, on peut mettre à jour les ĉN et c̃N , et bien entendu, les solutions et mises-à-jour
de B ´1 sont efficaces.
Algorithme 6.1: Simplexe auto-dual paramétrique.
6.3. ANTI-CYCLAGE PROBABILISTE 161
entre 1{2 et 3{2, disons. Remarquons que cette fois-ci, la perturbation devient nulle dès que
l’algorithme atteint µ “ 0, et donc c’est bel et bien le problème original qui est alors résolu.
Rappelons que ainsi, l’algorithme auto dual paramétrique consistera à démarrer avec
un tableau initial sous forme canonique, dans lequel on remplace le vecteur c̄ “ c par un
vecteur paramétrique c̄ ` µc et le vecteur b̄ “ b par un vecteur paramétrique b̄ ` µb . c
et b sont des vecteurs de même dimension que c et b respectivement, dont les composantes
sont aléatoires, uniformes entre 1{2 et 3{2, disons. Alors, la plus petite valeur de µ pour
laquelle le tableau initial est optimal et réalisable est µ0 ě maxp´ mini c̄ci , ´ minj b̄bj , 0q.
i j
6.4 Résumé
Une fois résolu par une variante de la méthode du simplexe, une solution de base optimale
et réalisable est disponible pour un problème d’optimisation linéaire. Ceci nous permet aussi
de calculer une solution optimale et réalisable pour le problème dual.
Si on modifie certaines données du problème original, composantes du vecteur de coût
c, du membre de droite b ou même de la matrice A, il est possible que la base optimale
et réalisable demeure optimale et réalisable. Si ce n’est pas le cas, selon quel paramètre est
modifié, on peut restaurer l’optimalité ou la réalisabilité. Selon le cas,
‚ modification de c : la base courante demeure réalisable et on peut, si elle n’est pas optimale,
restaurer l’optimalité avec l’algorithme primal du simplexe ;
‚ modification de b : la base courante demeure optimale (dual-réalisable) et on peut, si elle
n’est pas réalisable (dual-optimale), restaurer la réalisabilité avec l’algorithme dual du
simplexe ;
‚ modification de A : si on modifie des éléments associés aux variables de la base, tout
changera et il vaut mieux résoudre le problème à nouveau. Si les éléments modifiés sont
hors-base, on peut recalculer c̄N “ cN ´ cB B ´1 et déterminer si l’optimalité est préservée ;
sinon, on n’a pas touché à la réalisabilité et on peut utiliser l’algorithme primal du simplexe
pour restaurer l’optimalité.
6.5. EXTENSIONS ET RÉFÉRENCES 163
On a aussi vu qu’on peut calculer une plage de modification pour un des paramètres pour
garantir que la base courante demeure optimale et réalisable.
Enfin, l’algorithme auto-dual paramétrique consiste à ajouter un vecteur paramétrique
µe à cN et b, choisir µ assez grand pour que le problème ainsi perturbé soit optimal et
réalisable et progressivement réduire le paramètre µ jusqu’à 0 qui nous donnera une solution
de base optimale et réalisable. La réduction passe par des itérations de simplexe primal ou
dual ; s’il n’est pas possible de réduire µ à zéro, ce sera parce que une itération primale a
exhibé une colonne choisie non-positive ou une itération duale une ligne choisie non-négative.
Dans les deux cas, on aura détecté la non-réalisabilité du problème. Puisqu’on ne suppose
jamais la réalisabilité primale ou duale, la non-réalisabilité de l’un n’entraîne pas forcément
la non-bornitude de l’autre.
Exercice (6.1.2, page 152) [Ajout de variable] Complétez les calculs pour restaurer l’op-
timalité de cet exemple.
Exercice (6.1.3, page 153) [Ajout de contrainte] Complétez les calculs pour restaurer la
réalisabilité de cet exemple.
a) Donnez un intervalle de variation du coût c1 pour que la solution au tableau (6.10) demeure
optimale.
164 CHAPITRE 6. ANALYSE DE SENSIBILITÉ
` ˘ ` ˘
b) On change le membre de droite 30 10
par 20
30
. Est-ce que la base actuelle demeure réalisable
et optimale ? Justifiez. Si non, déterminez une solution réalisable et optimale du nouveau
problème.
c) On change les coefficients pc3 , a13 , a23 qt “ p3, 4, ´1qt par p2, 3, ´2qt .
i) Que devient alors le tableau (6.10) ?
ii) Le nouveau tableau est-il optimal ? Si non, déterminez une solution optimale du nouveau
problème.
d) On introduit une nouvelle variable x6 avec coefficients pc6 , a16 , a26 qt “ p´3, 1, 2qt .
i) Que devient alors le tableau (6.10) ?
ii) Le nouveau tableau est-il optimal ? Si non, déterminez une solution optimale du nouveau
problème.
e) On introduit une nouvelle contrainte 2x1 ` 3x2 ` 3x3 ď 25 dans le problème original. Le
nouveau problème réalisable. Déterminez en une solution de base réalisable optimale.
f) On introduit une nouvelle contrainte 3x1 ` 2x2 ` 3x3 ď 25 dans le problème original. Le
nouveau problème n’est pas réalisable. Déterminez en une solution réalisable optimale.
Le tableau associé à la solution optimale est le suivant (x5 , x6 et x7 sont des variables d’écart).
x1 x 2 x3 x4 x5 x 6 x7
7
5
0 0 12 5
1
5
4
5
0 11
3 4 2 1
10
1 0 5 5 10 0 4 (6.11)
1
´ 10 0 1 25 15 10 3
0 5
1 1
2
0 0 10 1 ´ 2 1 11
a) De quelle quantité faut-il modifier le coût c4 pour qu’il devienne avantageux de rendre x4
positive ?
b) Déterminez l’intervalle de variation du coût c2 pour que la solution demeure optimale.
c) Déterminez l’intervalle de variation du terme de droite de la seconde contrainte (valeur
nominale de 12) pour que la base optimale demeure réalisable et optimale.
d) On introduit une nouvelle variable x8 ayant 1 comme coefficient dans chacune des trois
contraintes et un coût c8 “ ´2. Déterminez une solution optimale de ce nouveau problème.
6.6. TOUS LES EXERCICES DU CHAPITRES 165
a) De combien faut-il augmenter c3 pour que la base courante cesse d’être optimale ? Trouvez
une solution optimale pour c3 “ ´6.
b) De combien peut-on faire varier c1 pour que la base courante demeure optimale ?
c) Trouvez la plus grande et plus petite valeur de λ pour que la solution demeure optimale
si c est remplacé par c ` λp0, 0, ´1, 1, 2q.
d) De combien b2 (sa valeur originale) peut-il varier avant que la base courante cesse d’être
optimale ? (Note : pas besoin de calculer la valeur originale de b2 ).
e) Trouvez une solution réalisable et optimale par l’algorithme dual du simplexe quand b2
est augmenté de deux unités.
Exercice (6.1.8, page 156) [Sensibilité] Soit un problème sous forme standard pour le-
quel on aboutit au tableau optimal suivant. La première ligne est le vecteur c original et la
seconde la ligne des coûts du tableau final.
x1 x2 x3 x4 x5
´2 ´3 ´1 0 0
0 0 3 3 1 8 (6.13)
1 0 ´1 3 ´1 1
0 1 2 ´1 1 2
On suppose que les variables x4 et x5 sont des variables d’écart de sorte que l’inverse de la
base optimale B ´1 se retrouve dans les colonnes 4 et 5 du tableau.
a) Donnez un intervalle de variation de c2 pour que la solution reste optimale. Trouvez une
solution optimale pour c2 “ ´1.
b) Trouvez un intervalle de λ pour` que
˘ la base t1, 2u demeure optimale1 et réalisable si le
1
vecteur b est remplacé par b ` λ ´1 . Résoudre le problème pour λ “ 2 .
c) Trouvez une solution optimale si une nouvelle contrainte x1 ` x3 ě 2 est ajoutée au
problème original.
Exercice (6.2.1, page 159) [Valeur de z] Complétez le tableau pour avoir une expression
de la valeur de ´z à chaque itération, et donc pour la solution optimale.
Exercice (6.2.2, page 159) [Intervalle final] Quel est l’intervalle de µ qui rend le tableau
final réalisable et optimal ?
Exercice (6.2.3, page 159) [Illustration graphique] Illustrez graphiquement les itérations
de l’algorithme
6.6. TOUS LES EXERCICES DU CHAPITRES 167
Exercice (6.2.4, page 159) [Algorithme auto paramétrique] Considérez le tableau sui-
vant
x1 x2 x3 x4 x5
2µ ´ 1 0 3 ´ µ 0 0
´1 1 1 0 0 µ´1 (6.14)
´3 0 2 1 0 3µ ´ 4
´1 0 ´1 0 1 2
a) Pour quelles valeurs de µ ce tableau est-il réalisable et optimal ?
b) Si on applique l’algorithme auto dual, quelle variable entrera dans la base et quelle en
sortira ?
Exercice (6.2.5, page 161) [Application d’algorithme] Utilisez l’algorithme auto dual pa-
ramétrique pour résoudre les problèmes suivants.
a)
min 2x1 ´ 3x2
sujet à ´x1 ` x2 ď ´1
´x1 ´ 2x2 ď ´2
x2 ď 1
x1 , x2 ě 0.
b)
min ´3x1 ` x2
sujet à x1 ´ x2 ď 1
´x1 ` x2 ď ´4
x1 , x2 ě 0.
c)
min ´2x1 ` 6x2
sujet à ´x1 ´ x2 ´ x3 ď ´2
2x1 ´ x2 ` x3 ď 1
x1 , x2 , x3 ě 0.
168 CHAPITRE 6. ANALYSE DE SENSIBILITÉ
Chapitre 7
Quelques extensions
Sujets du chapitre
‚ Observations sur la géométrie du problème.
‚ Condition d’optimalité.
‚ Déduction de l’algorithme du simplexe.
‚ Théorie de la dualité linéaire.
‚ Dégénérescence.
‚ Aspects numériques.
169
170 CHAPITRE 7. QUELQUES EXTENSIONS
Introduction
7.1 Un algorithme de décomposition
Nous présentons dans cette section un algorithme de décomposition, dû à Dantzig et
Wolfe, qui introduit une technique qui s’est avérée importante et efficace nommée génération
de colonnes. Considérons un problème de la forme
min c1 x 1 ` c2 x 2
sujet à A1 x1 ` A2 x2 “ b0
B1 x1 “ b1 (7.1)
B2 x2 “ b2
x1 , x2 ě0
où x1 P Rn1 , x2 P Rn2 , b0 P Rm0 , b1 P Rm1 , b2 P Rm2 . On a donc n “ n1 ` n2 variables et
m “ m0 ` m1 ` m2 contraintes. Si ce n’était pas de la contrainte couplante A1 x1 ` A2 x2 “ b0
de dimension m0 , on serait en présence de deux problèmes indépendants,
min c1 x 1
sujet à B1 x1 “ b1 (7.2)
x1 ě0
comportant m1 contraintes et
min c2 x 2
sujet à B2 x2 “ b2 . (7.3)
x2 ě0
comportant m2 contraintes.
Supposons pour cette introduction que chacun des sous-problèmes (7.2) et (7.3) ont des
domaines réalisables bornés. Alors, il n’est pas difficile de se convaincre intuitivement que
le domaine réalisable est en fait une combinaison convexe des sommets du polyèdre, des
solutions de base réalisables des contraintes. En effet, tout point réalisable qui ne peut pas
s’exprimer comme combinaison de deux autres points réalisables est un point extrême, so-
lution de base. Donc, un point quelconque est soit un point extrême, soit une combinaison
de points réalisables. Les combinaisons de 2 points extrêmes nous donnent les arêtes du
polyèdre, de trois points des faces, et ainsi de suite, engendrant le polyèdre en entier. La dé-
monstration rigoureuse de cette propriété est délicate, aussi nous nous contenterons d’utiliser
le résultat suivant.
Théorème 7.1.1 Soit un ensemble borné décrit par des contraintes Ax “ b, x ě 0. Soient
p1 , p2 , . . . , pk l’ensemble des points extrêmes
ř ř(solutions de base réalisables) de l’ensemble.
Alors, tx : Ax “ b, x ě 0u “ tx : x “ αi pi , αi “ 1, α ě 0u.
7.1. UN ALGORITHME DE DÉCOMPOSITION 171
Par exemple, un triangle est l’ensemble des combinaisons convexes de ses sommets, et un
point d’un carré peut s’exprimer comme combinaison convexe des 2 (parfois plus) triangles
qui le contiennent. On voit alors que les multiples αi qui décrivent un point d’un carré ne
sont pas uniques. Ces valeurs αi sont nommées coordonnées barycentriques du point. Sous
certaines conditions (par exemple si le point est dans un triangle 2D, donc 3 points extrêmes),
cette représentation est unique, mais en général, plusieurs (en fait , une infinité) combinaisons
convexes de points extrêmes pourront décrire le même point.
Remarque 7.1.1 Le nombre de solutions de base réalisables est énorme, beaucoup plus
grand que n ou m. Par exemple, les contraintes simples 0 ď x ď 1 comportent n variables,
2n contraintes, et 2n sommets. pour n “ 20, on a 40 contraintes, mais 1 048 576 sommets.
Avec cette représentation, nous allons décrire les domaines réalisables des problèmes (7.2)
et (7.3) en utilisant des combinaisons convexes de leurs points extrêmes.
ř
x
ř 1 “ α i pi
αi “ 1 (7.4)
α ě0
et ř
x
ř2 “ βj q j
βj “1 (7.5)
β ě 0.
Sans les dénombrer explicitement, on suppose que les sommations sur i et j s’appliquent à
tous les points extrêmes de leur polyèdre respectifs.
Maintenant, récrivons le problème original (7.1) en utilisant les variables α et β, obtenant
ainsi le problème nommé problème maître.
ř ř
minα,β c1 p řαi pi q ` c2 p řβj qj q
sujet à ř A1 p αi pi q ` A2 p βj qj q “ b0
αi “1
ř (7.6)
βj “1
α ě0
β ě 0.
somme des α et β. Introduisons les notations ξi “ c1 pi , ξ est le vecteur de coût des variables
α. Similairement, µj “ c2 qj , µ est le vecteur de coût des variables β. Pour les contraintes,
introduisons Ψi “ A1 pi et Φj “ A2 qj . Les coûts relatifs de la colonne αi obéit donc à la
relation ¨ ˛
Ψi
ξ¯i “ ξi ´ py0 , y1 , y2 q ˝ 1 ‚ “ ξi ´ y0 Ψi ´ y1 , (7.7)
0
et les coûts relatifs de la colonne βj à la relation
¨ ˛
Φi
µ̄j “ µj ´ py0 , y1 , y2 q ˝ 0 ‚ “ µj ´ y0 Φj ´ y2 . (7.8)
1
Il faut donc trouver le minimum des ξ¯i , des µ̄j et prendre le minimum des 2. S’il est positif,
la solution est optimale, autrement, nous avons déterminé la variable d’entrée.
Maintenant, pour trouver le minimum des ξ¯i , utilisons (7.7) et remarquons que y1 et y2
ne dépendent pas de i (ni de j), et donc il suffit de minimiser ξi ´ y0 Ψi et µj ´ y0 Φj . En se
souvenant que ξi “ c1 pi et Ψi “ A1 pi , on constate qu’il faut minimiser pc1 ´y0 A1 qu pour tous
les points extrêmes u du domaine réalisable tx1 : B1 x1 “ b1 , x1 ě 0u. Or, on peut obtenir
cette minimisation sans connaître les pi car il suffit de résoudre
On peut le convertir sous forme standard du simplexe, même sous forme canonique comme
suit.
n
ÿ
max
x,s
xi
i“1
sujet à x1 ` s1 “1
k´1
ÿ
2 xi ` xk ` s k “2k ´ 1, k “ 2, 3, . . . , n,
i“1
x, s ě0.
-1 -1 -1 0 0 0 0
1 0 0 1 0 0 1
2 1 0 0 1 0 3
2 2 1 0 0 1 7
Pour cet exemple, puisque tous les coûts cN sont égaux, prenons la convention de choisir
le premier parmis ceux égaux au minimum. On vérifie que l’algorithme du simplexe prend
2n ´ 1 itérations pour aboutir à la solution.
où nous avons utilisé la notation que Sk majuscule est la matrice diagonale dont les com-
posantes sont celles du vecteur sk minuscule ; Sk xk est le produit composante par compo-
sante des vecteurs sk et xk . Maintenant, considérons le déplacement de wk “ pxk , yk , xk q à
wk`1 “ pxk`1 , yk`1 , xk`1 q, δk “ pδkx , δky , δks q. Idéalement, nous voudrions que le prochain point
ait un résidu nul pour la valeur de µk`1 .
Sauf pour la dernière équation qui comporte un terme quadratique ∆sk δkx , toutes les autres
équations sont linéaires. Négligeons donc ce terme quadratique pour calculer une approxi-
mation de δ qui satisfait aux équations linéaires suivantes :
´rkp
¨ ˛ ¨ x˛ ¨ ˛
A 0 0 δk
˝ 0 At I ‚˝δky ‚ “ ˝ ´rkd ‚ (7.32)
Sk 0 Xk s
δk µk`1 1 ´ rk
c
continue, le point F “ 7
p 94 , 15
4
qt ; le vecteur G est
l’opposé du vecteur coût, la 6
Si pour un exemple si simple de seulement deux variables les stratégies naïves d’arrondir
la solution continue ne fonctionne pas, ce sera évidemment encore plus problèmatique pour
des modèles réalistes !
7.3. TRAITEMENT DE VARIABLES ENTIÈRES 177
Cette approche est fondée sur l’observation suivante : si une composante de la solution
continue xci R Z, alors dans la solution optimale entière, soit on aura xi ď txci u, soit xi ě rxci s.
On sépare donc le problème en deux, c’est le branch dans le nom anglophone branch and
bound.
Séparation
G Soit x2 ď 3, soit x2 ě 4.
7
M1
5
P1
4
F 11
P
A
O
0 1 2 3 4 5 6 7 8 9 10 11
Maintenant, la solution avec x2 ď 3 est p3, 3qT , solution entière de valeur ´39. On ne
séparera plus cette portion puisqu’on y a identifié une solution optimale entière. Par contre,
la solution avec x2 ě 4 est p 95 , 4qt et donc nous effectuerons une autre séparation. x1 ě 2 n’a
pas de solution, donc cette séparation résulte en un seul nouvel ensemble x1 ď 1.
178 CHAPITRE 7. QUELQUES EXTENSIONS
x2 ě 4 et x1 ď 1, la solution
est p1, 40
9
qt . 5.2
4.8
4.6
4.4
4.2
3.8
-0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
Évaluation progressive
Évidemment, on ne peut pas effectuer tous les calculs à la fois et on privilégiera un ordre
pour déployer l’arbre d’énumération des séparations. À moins que x P Zn , un nœud donné
dans l’arbre n’est pas terminal et sera sujet à séparation future.
min2 ´x2
xPR
sujet à 3x1 ` 2x2 ď 6
(7.34)
´3x1 ` 2x2 ď 0
x1 , x2 ě 0, entiers,
7.3. TRAITEMENT DE VARIABLES ENTIÈRES 179
4
F
0 1 2 3 4 5 6 7 8 9 10 11
x “ p 94 , 15 t
4
q ,z “ ´41 14
x2 ď 3 x2 ě 4
G
G
7 7
6 6
M1 M1
5 5
V1
4 4
F
P F1
P
U
3 3
1 .. 2
0 1 2 3 4 5 6 7 8 9 10 11
. 0 1 2 3 4 5 6 7 8 9 10 11
x1 ď 1 x1 ě 2
5.2
4.8
Problème vide
4.6
4.4
4.2
3.8
-0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
40 t
xp1, 9
q ,z “ ´40 59
x2 ď 4 x2 ě 5
5.2 5.2
5 5
4.8 4.8
4.6 4.6
4.4 4.4
4.2 4.2
4 4
3.8 3.8
-0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 -0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6
7.3.2 Coupes
L’idée des algorithmes de la famille des plans de coupe est d’ajouter une ou plusieurs
contraintes pour éliminer une solution indésirable. Dans notre cas, une solution à coordon-
nées fractionnaires n’est pas désirable lorsque les variables sont spécifiées comme entières.
Examinons le tableau final de la solution fractionnaire.
5 3
0 0 4 4
41 41
9
1 0 4
´ 41 9
4
0 1 ´ 54 1
4
15
4
Par ailleurs, les variables hors base (dans N ) sont nulles en une solution de base, et donc en
une solution de base à coordonnées non entières, on a
ÿ` ˘
b̄i ´ tb̄i u ´ Āij ´ tĀij u xj “ b̄i ´ tb̄i u ą 0 (7.40)
jPN
7.3. TRAITEMENT DE VARIABLES ENTIÈRES 181
ce qui montre que la relation(7.42) n’est pas satisfaite pour une solution de base non entière.
Donc, cette relation est une contrainte nommée coupe, elle est satisfaite pour tout point
entier réalisable et élimine la solution de base fractionnaire courante.
Sur notre exemple, la contrainte (7.37) s’écrit
1 1 3
´ x3 ´ x4 ď 0 (7.41)
4 4 4
et on voit bien que la solution de base courante x3 “ x4 “ 0 ne satisfait pas cette coupe. On
ajoute donc une variable d’écart x5 et une contrainte ´ 14 x3 ´ 34 x4 ` x5 “ ´ 41
5 3 165
0 0 4 4
0 4
9
1 0 4
´ 14 0 9
4
0 1 ´ 45 1
4
0 15
4
0 0 ´ 41 ´ 34 1 ´ 14
Puisque x3 et x4 sont des variables d’écart du problème (7.33), on peut exprimer directement
dans les variables x1 et x2 la contrainte 4x1 ` 7x2 ď 35.
Exercice 7.3.3 [Une itération] Utilisez l’algorithme dual du simplexe pour restaurer la
réalisabilité de l’exemple.
On peut aussi utiliser la ligne “0” du tableau pour définir une coupe. Dans ce cas, la
coupe sera constituée des coefficients de la ligne 0 changés de signe (car notre problème est
un min) ÿ` ˘
¯ ´ t´zu ´
´z ´Ā0j ´ t´Ā0j u xj ď 0. (7.42)
jPN
3
qui, sur notre exemple, donne x
4 3
` 14 x4 ě 3
4
qui, dans les variables x1 et x2 équivaut à
2x1 ` 3x2 ď 15.
On voit d’après les illustrations que cette seconde coupe enlève une plus grande portion
du domaine réalisable que la première. Dans le jargon, on dit que la seconde coupe est plus
profonde que la première.
182 CHAPITRE 7. QUELQUES EXTENSIONS
7.3.3 Remarques
Nous venons de voir brièvement deux approches qui constituent la base de tout algorithme
pour résoudre des problèmes avec variables entières, les algorithmes de séparation et évalua-
tion progressive (beanch and bound) et les algorithmes de plans de coupe (cutting planes).
Les logiciels modernent utilisent une combinaison des deux approches avec d’innombrables
raffinements.
Contrairement à l’optimisation linéaire continue pour laquelle il existe un algorithme
polynomial, l’optimisation linéaire en nombres entiers est un problème reconnu comme NP-
difficile, ce qui signifie que fort probablement il n’existe pas d’algorithme polynomial pour sa
résolution. La question à savoir si des problèmes NP-difficiles peuvent être résolus en temps
polynomial est une question ouverte très importante en informatique théorique.
En pratique, donc, il faut s’attendre à être rapidement limité en termes de dimensions
des problèmes en présence de contraintes d’intégrité, nom donné aux contraintes imposant
des variables à prendre que des valeurs entières.
i´1 i`1 n i
Cette dernière matrice est nommée une matrice Hessenberg supérieure, et est presque déjà
triangularisée, à l’exception de quelques éléments sur la sous-diagonale. On voit donc qu’il
est possible de triangulariser cette matrice Hessenberg supérieure en utilisant n ´ i pivots de
la méthode d’élimination de Gauss. De plus, on peut utiliser la stratégie de pivot partiel de
manière très simple en examinant seulement l’élément diagonal, et l’élément sous-diagonal
car les autres éléments d’une colonne sont tous nuls. Soit donc M “ Mn Mm´1 . . . Mi`1 la
matrice qui représente les n ´ i pivots. On a M L´1 B 1 “ U 1 , de sorte que L1 “ LM ´1 .
Une autre stratégie de choix de pivot permet de profiter de la structure de zéros de la
matrice.
7.5 Résumé
Nous avons vu que l’ensemble réalisable E “ tx : Ax “ b, x ě 0u, s’il est borné,
peut s’exprimer comme l’ensemble des combinaisons convexes de ses points extrêmes. Dans
la forme standard du simplexe, les points extrêmes sont les solutions de base réalisables.
Exploitant cette représentation, nous avons présenté l’implémentation de l’algorithme dans sa
forme révisée en décomposant un problème avec structure en escalier et contrainte couplante.
Nous avons exhibé un exemple où l’algorithme du simplexe nécessite 2n ´ 1 itérations.
Un algorithme nécessitant une quantité exponentielle de calculs est considéré inefficace. Les
algorithmes de points intérieurs permettent de résoudre, en pire cas, un problème d’optimi-
sation linéaire avec une quantité de calculs bornée par un polynôme fonction de la taille du
problème. Une différence importante avec les algorithmes de type simplexe est que, dans le
cas dégénéré où il y a plusieurs solutions, l’algorithme du simplexe en identifie une de base
alors que les algorithmes de points intérieurs en identifient une “centrale”.
Exercice (7.3.2, page 181) [Illustration] Illustrez cette coupe sur la figure 7.1.
Exercice (7.3.3, page 181) [Une itération] Utilisez l’algorithme dual du simplexe pour
restaurer la réalisabilité de l’exemple.
Exercice (7.3.4, page 181) [Illustration] Illustrez cette coupe sur la figure 7.1.
Exercice (7.3.5, page 182) [Une autre coupe] Choisissez la seconde équation x2 ´ 45 x3 `
1
x “ 15
4 4 4
pour définir une coupe ; vérifiez que cette coupe est identique à celle définie à l’aide
de la ligne 0. Utilisez l’algorithme dual du simplexe pour restaurer la réalisabilité.
186 CHAPITRE 7. QUELQUES EXTENSIONS
Exercice (7.3.6, page 182) [Application de l’algorithme] Appliquez l’algorithme des plans
de coupe pour résoudre le problème de l’exercice 7.3.1.
Annexe A
Rappels mathématiques
Il est remarquable que seule la différentiabilité de f au point minimum suffit pour établir
cette condition nécessaire.
Théorème A.1.2 (Rolle) Soit une fonction f différentiable sur un intervalle ra, bs et telle
que f paq “ f pbq ; alors, il existe un point c P ra, bs tel que f 1 pcq “ 0.
Théorème A.1.3 (de la moyenne ou des accroissements finis) Soit f une fonction
différentiable sur un intervalle ra, bs. Alors, il existe un point c P ra, bs tel que f 1 pcq “
f pbq´f paq
b´a
.
187
188 ANNEXE A. RAPPELS MATHÉMATIQUES
en l’application d’opérations élémentaires (multiplier une ligne par une constante, ajouter
un multiple d’une ligne à une autre) simultanément à A et à une matrice identité.
Examinons un petit exemple pour calculer l’inverse d’une matrice 3 ˆ 3.
¨ ˛
3 0 2
A “ ˝2 0 ´2‚
0 1 1
La méthode, pratique pour de petites matrices à inverser sur papier consiste à constituer un
tableau où on juxtapose l’identité à la matrice A, rA|Is.
3 0 2 1 0 0
2 0 ´2 0 1 0
0 1 1 0 0 1
On commence par diviser la première ligne par 3 pour avoir notre un d’identitée en position
(1,1).
2 1
1 0 3 3
0 0
2 0 ´2 0 1 0
0 1 1 0 0 1
Ensuite, on ajoute ´2 fois la première ligne à la seconde.
2 1
1 0 3 3
0 0
0 0 ´ 10
3
´ 23 1 0
0 1 1 0 0 1
1 ´ 32 0 1
3
0 ´ 23
0 10
3
0 ´ 23 1 10
3
0 1 1 0 0 1
10
On divise maintenant la seconde ligne par 3
1 ´ 32 0 1
3
0 ´ 23
0 1 0 ´ 15 3
10
1
0 1 1 0 0 1
190 ANNEXE A. RAPPELS MATHÉMATIQUES
2
et enfin ajoute 3
fois la seconde ligne à la première, puis moins une fois à la troisième.
1 1
1 0 0 5 5
0
0 1 0 ´ 15 3
10
1
1 3
0 0 1 5
´ 10 0
Pourquoi ça marche ?
On peut représenter chacune des opérations élémentaires par la multiplication par une
matrice appropriée. Multiplier une ligne par une constante s’effectue en multipliant par une
matrice n ˆ n Si pf q, mise à l’échelle de la ligne i d’un facteur f , S pour scaling en anglais.
Pour n “ 3, ¨ ˛
1 0 0
S2 p3q “ ˝0 f 0‚.
0 0 1
En général, c’est une matrice identité où on remplace le un en ligne/colonne i par f . Ajouter
un multiple f d’une ligne i à une autre j s’écrit comme la multiplication par une matrice
disons Rij qui est l’identité à laquelle l’élément pj, iq (nul car i “ j) est remplacé par f .Pour
n “ 3, ¨ ˛
1 0 0
R23 pf q “ ˝0 1 0‚.
0 f 1
Alors, pour l’inverse calculé ci-haut, on a
2 10 2 10 1
I “ R12 p qR32 p´1qS2 p qR13 p´ qR23 p qR21 p´2qS1 p qA.
3 3 3 3 3
Par conséquent, puisqu’on a appliqué les mêmes opérations sur l’identité, on retrouve à la
place de l’identité la matrice
2 10 2 10 1
R12 p qR32 p´1qS2 p qR13 p´ qR23 p qR21 p´2qS1 p q “ A´1 .
3 3 3 3 3
Onservons que si on utilisait la stratégie de permuter deux lignes lorsqu’un malencontreux
zéro se présente sur la diagonale, une matrice de permutation permettrait de représenter
l’opération.
Annexe B
Solutions de quelques exercices
min c1 x1 ` c2 x2
sujet à A11 x1 ` A12 x2 ď b1
A21 x1 ` A22 x2 “ b2
x1 ě 0,
191
192 ANNEXE B. SOLUTIONS DE QUELQUES EXERCICES
ˆ ˙
b
b̄ “ 1 et un vecteur x̄ “ px1 , x` ´ t
2 , x2 , sq tels que le problème s’écrit :
b2
min c̄x̄
sujet à Āx̄ “ b̄
x̄ ě 0,
193