Recherche Opérationnelle

Première Partie
Paul Feautrier

[email protected].

ENS Lyon

RO-MIM2 – 1/76
Plan

Introduction et principaux concepts

Optimisation continue sans contrainte
Programmation linéaire
Optimisation continue sous contrainte
Optimisation combinatoire
Programmation linéaire en nombres entiers.
Exploration
Métaheuristiques
Programamtion dynamique
Eléments de Complexité

RO-MIM2 – 2/76
Qu’est ce que la recherche opérationnelle ?

Vocabulaire : Recherche opérationnelle = programmation

mathématique = optimisation (mais pas optimisation de
programme).
Recherche opérationnelle = modélisation mathématique des
processus de prise de décision.

Inconnues : les variables de décision.

Evaluation de la décision = fonction économique ou fonction
« objectif ».
Trouver les valeurs des variables de décision qui minimisent
(ou maximisent) la fonction objectif.

RO-MIM2 – 3/76
Recherche opérationnelle

modélisation
optimisation action

La modélisation est un art, l’optimisation est une science.

Le schéma s’applique aussi bien à la planification du débarquement de Normandie qu’à

l’optimisation d’un programme de calcul intensif ou au choix de la meilleure façon d’investir
son argent.
Investissement en bourse = optimisation avec information incomplète ou aléatoire.
Planification d’une opération militaire = il y a un adversaire = théorie des jeux.
Optimisation d’un programme = en principe, on a une information complète.
Le cours est essentiellement consacré à l’optimisation avec information complète.

RO-MIM2 – 4/76
Informatique ou mathématique ?

Mathématique Informatique

Théorèmes d’existence Intelligence Algorithmes

Convergence Artificielle Preuves de terminaison

Recherche Opérationelle

Complexité

RO-MIM2 – 5/76
Vocabulaire

courbes de niveau de
la fonction objectif

optimum
Forme canonique :
trouver qui




minimise










contraintes

RO-MIM2 – 6/76
Optimum local, global

Minimum local : est un minimum local de s’il existe un voisinage de tel

que :





 




Minimum global : est un minimum global de dans ssi :






 




local

global

RO-MIM2 – 7/76
Convexité

Un ensemble est convexe si, pour toute paire de points de


 

, contient aussi le segment .








" 
#








! 







 



convexe convexe convexe non convexe

RO-MIM2 – 8/76
Fonction convexe


est convexe dans un ensemble convexe ssi :






















$

$
!

!


RO-MIM2 – 9/76
Intérêt de la convexité

Théorème 1 Si est convexe dans un ensemble convexe , alors tout minimum local de est un

&

%
minimum global.
Soit un minimum local, et l’ouvert contenant dans lequel :

(
'

'
,
-.

,
/ -
0
%

%
*

(+
)

'
,

,
-
Si on suppose qu’il existe un point tel que alors on a :

&

%
1

1
*

-2

'
3,

-
-7

,
-

-
,
/0-
%

%
6 3

6 3

1
4

4
,5

,5
'

'
Il est possible de trouver un suffisamment proche de 1 pour que
3
-

soit dans . En ce point :

3

6 3

(
4
,5
8)

'

,
-7

,
-

-
,
-7

,
90-
%

%
3

6 3

1
4
,5
)

'

'
une contradiction.

RO-MIM2 – 10/76
Classification

Selon la nature des variables de décision :

Optimisation continue.
Optimisation discrète ou optimisation combinatoire.
Selon la nature des contraintes :
Pas de contraintes ou contraintes faciles à satisfaire (un
segment de la droite réelle) : optimisation sans contraintes.
Optimisation sous contraintes : il est difficile de trouver un
point satisfaisant les contraintes.
Propriétés spéciales des éléments du problème : linéarité,
convexité.

RO-MIM2 – 11/76
Optimisation multicritère

Forme canonique : trouver qui minimise

5 

: 
;



"
"
"



5 





: 
;

"
"
"




Le problème est évidemment mal posé. Quel sens peut on lui
donner ?
Exemple : on doit concevoir un équipement électronique qui doit exécuter un
algorithme donné le plus vite possible et pour le moindre prix.
est le temps d’exécution de l’algorithme.
< =

est le prix de l’équipement.

> =

RO-MIM2 – 12/76
Domination

On se place dans le cas .

A
?@
La solution domine la solution ssi

$



5 

5 

: 
;

: 
;



$

$


"
La relation de domination est un ordre partiel. On ne peut donc
pas prouver l’unicité d’un minimum s’il existe.
L’optimum de Pareto (ou le Pareto) du problème est l’ensemble
des solutions non dominées.

RO-MIM2 – 13/76
Pareto

prix

domination

latence
Que faire avec un Pareto ?

RO-MIM2 – 14/76
Pondération

On attribue un poid à chaque objectif et on minimise l’objectif pondéré.

prix

optimum
pondéré

latence

RO-MIM2 – 15/76
Transformation objectif/contrainte

On fixe la valeur de l’une des fonctions objectif et on optimise l’autre.

Par exemple, le marketing décide du prix maximum de l’équipement.
prix

borne du prix

optimum

latence

RO-MIM2 – 16/76
Optimisation continue sans contrainte

Une seule variable



EDC
B

FG

H
Si on connaît la dérivée de , le problème se ramène à trouver les racines de
H

, puis à les tester une par une pour savoir si elles sont un minimum, un
maximum ou un point d’inflexion.
On peut utiliser pour cela des méthodes classiques : itération de Newton (si on
peut calculer la dérivée seconde), dichotomie, méthode de la sécante.
Si on ne connaît pas la dérivée, la première chose à faire est de trouver un
encadrement du minimum. Il n’y a pas de méthode générale, on utilise les
renseignements que l’on peut avoir sur .

RO-MIM2 – 17/76
Fonctions unimodales

J
Une fonction est unimodale dans l’intervalle s’il existe un

 




point tel que si alors et si


LK




K 

M


$



alors .





K

J
Il est évident que si est unimodale dans , alors est un

 


K
minimum global.

J
Théorème 2 Si 
est continue convexe dans , alors est


 

unimodale.

Soit le minimum de , et et qui violent la


K

$
condition d’unimodalité, par exemple et


K

$


. Soit tel que

K 





ON

N
$

. Par convexité on doit avoir



! 

K

$
@


mais aussi


K 




! 


$


une contradiction. 
K 




! 




ON
$

RO-MIM2 – 18/76
Méthode par trichotomie

a c d b a c d b

J
On divise l’intervalle en trois parties égales à l’aide des
 



points . On calcule et .

K 


NP

P
N

N
K

On détermine le minimum de parmi les 4 points .



P
 K


Le minimum continu appartient à l’intervalle encadrant le
minimim discret.
L’intervalle est réduit au moins par un facteur . On poursuit

A
QR
jusqu’à la précision voulue.

RO-MIM2 – 19/76
Améliorations

Vitesse de convergence : la taille de l’intervalle est multippliée

:U
T
:
par après évaluations de la fonction.

?
S

La division en segment égaux n’est pas optimale. On a intérêt à

agrandir les segments extrêmes.
On peut passer à un découpage en 4 parties égales. Il faut
évaluer trois fois à chaque étape, mais l’intervalle est au moins


SU
T
5
divisé par 2. La convergence est en donc plus rapide.

RO-MIM2 – 20/76
Méthodes par exploration

J
Il est toujours indispensable de connaître une encadrement

 
du minimum.
On suppose toujours que est unimodale. On choisit un pas


d’exploration . On calcule aux points jusqu’à


P

X
P
VW


@

"



trouver soit une configuration , soit jusqu’à



V

54
atteindre le point .

On fait et on recommence.

Z
Y 

Y P

P
Y
@

@
V

54
6 5



est le facteur de convergence.
NZ

On s’arrète quand est devenu suffisamment petit.

P

La méthode peut s’appliquer à une fonction non unimodale. On

obtient alors un optimum local sans garantie qu’il soit global.

RO-MIM2 – 21/76
L’algorithme converge

'
Le nombre de pas d’exploration est au plus . L’exploration

6
1
s’arrète en un temps fini.
I

J
Soit le -ième intervalle d’exploration et le -ième


P


?
T

T
pas d’exploration. On a et .

Z
P

P
T

A

T @

!
T

T
I

Les forment une suite d’intervalles emboités dont la



T

longueur tend vers 0. Ils convergent donc vers une limite .

K
RO-MIM2 – 22/76
Optimisation à plusieurs variables

Forme du problème :


 




T
[\


Les inconnues sont les composantes du vecteur .
?
La notion de fonction unimodale ne se généralise pas.

RO-MIM2 – 23/76
Recherche directionnelle

On se ramène au cas à une seule variable. Pour cela on choisit

un point de départ et une direction .

P



On minimise la fonction à une variable à l’aide de

P
" ]

l’une des méthodes vues plus haut.
Si le déplacement est suffisamment petit, on arrète.

P
" ]
Sinon, on change de direction et on recommence.
Le point important est le choix des directions.

RO-MIM2 – 24/76
Recherche suivant les axes

On prend comme directions

les vecteurs canoniques de la
base. Ceci revient à fixer

! 
?
variables de la fonction , et


à optimiser suivant la -ième.

?
On passe ensuite à la variable
suivante.
La méthode est très lente et
peut même ne pas converger
si les courbes de niveau sont
à peu près parallèles aux dia-
gonales.
On peut l’accélérer en effec-
tuant pas puis en utilisant
^

la direction .
`_

ba
!

RO-MIM2 – 25/76
Gradient

On suppose que la fonction a une dérivée.

dc

dc

j



g 





Le gradient de au point est le vecteur . On le note




g
f Oec

ihOec



.
k

On a le développement de Taylor :

n=






m

m
k
l

 l




Ceci montre que 
est la direction dans laquelle décroit le plus
k
o

rapidement (steepest descent).

D’où l’algorithme :



1. Calculer le gradient .
k




2. Minimiser la fonction à une variable .

k
o
3. Si le critère de convergence n’est pas vérifié, recommencer en 1.

RO-MIM2 – 26/76
Propriété

Théorème 3 Dans l’algorithme ci-dessus, les directions de recherche

successives sont orthogonales.
Soit le point de départ d’une re-
cherche unidimensionnelle suivant la direc-



tion et son point d’arrivée. La dé-

p
k
rivée de la fonction à minimiser est :




q

k
o


 



 

k

k
n

o
q
a b

En p cette dérivée est nulle, d’où la propriété.

RO-MIM2 – 27/76
Directions conjuguées

Une matrice de dimension est définie positive ssi :

s
?

?
u
r
t


Y

"
Une matrice définie positive définit un produit scalaire.
Deux vecteurs sont conjugués par rapport à ssi :

r
 v


w
u

. C’est une généralisation de la notion d’orthogonalité.

r


v

w@

Soit vecteurs mutuellement conjugués :

5 P

P
?

T

"
"
"


{" u
|
y

r
@ x

}~P




@
"

"
u

u


Soit la fonction . Si on la minimise

r





K
@

successivement suivant les directions 5 P , on atteint le

P
T

"
"
"

minimum exact en étapes.
?

RO-MIM2 – 28/76
Notations

V,
-
Soit les minimas successifs.

@ X





"
"
"
V,

@ -

V,
-
54
.

V P
V
Le gradient de en est .

r



D’après la propriété ci-dessus et la congugaison des , on a :

V P
-
u

,a

r
P


V


@
V

"
u
r
V P

V P
V,
-

Les coordonnées de sont données par la formule :

V
V,
-

-
,a

P
@

{
"{
{
5
8

RO-MIM2 – 29/76
Preuve

€

Lemme 4 En tout point le gradient de est orthogonal au sous-espace engendré par

%
)
.
‚

€ ‚
f
9
/
/
/
9

€


€

Le gradient en est ou encore :

1
4
)

†€
f
„

ƒ

Šƒ
3

/ 1
4

4
)

‡
ˆ‰f ‡
Si on multiplie par et qu’on remplace par sa valeur il vient :
‚

3
‡

‡
„

‡ ‹
,

-
ƒ
‚

1
4
)
„


‹
,

‡ -
ƒ

ƒ
‚

81
4

a
)
‡

‡
/

/
‡ ‹
ƒ
‚

‚
‡


) h

Théorème 5 Le point est le minimum de .

%


) h

En effet, le gradient en doit être conjugué de vecteurs linéairement

T
indépendants, et donc doit être nul.

RO-MIM2 – 30/76
Gradient conjugué

C’est la transposition de la méthode ci-dessus au cas où la fonction est

quelconque, mais où on sait calculer son gradient.


On part d’un point et on pose .

Πq

k
n
Œ

Œ
o
Supposons que l’on soit parvenu en un point avec la direction . On

 q




minimise . Soit la solution obtenue.
 Ž
 q

 Ž
l


On pose :

 Ž

 q
l
n




<

g
‘>
‘
‘


‘
k



<
 

g
‘>
‘
‘


‘
k




 
 q

 q
k

l
n


<

<
o


On montre que si est quadratique définie positive, la méthode est identique à
celle des directions conjugués et converge en étapes.
D

RO-MIM2 – 31/76
Recherche aléatoire

Au lieu de calculer la direction de recherche optimale pour une

approximation quadratique de , on peut la choisir aléatoirement

I

J
en tirant nombres au hasard dans l’intervalle .

 
?
La méthode ne nécessite pas le calcul du gradient. Elle
fonctionne même si n’est pas dérivable.


Mais en général, sa convergence est beaucoup plus lente.

RO-MIM2 – 32/76
Test d’arrêt

Le choix d’un test d’arrêt est difficile.

Si est dérivable, son gradient doit être nul à l’optimum. On peut


’
N’
donc utiliser comme test d’arrêt.


’“

V

”
Sinon, on peut arréter les itérations quand la solution ne change
’
’

’
N’
plus : .
V

V

”
54

doit refléter la précision requise. Il ne doit pas être plus petit

”

que la précision des calculs sous peine de blocage.

Il est prudent d’attendre que le test ait été satisfait plusieurs fois
avant d’arrêter.
En général, la valeur du minimum est mieux définie que sa
position.

RO-MIM2 – 33/76
Programmation linéaire

x
•

?
K
"
r


M


est le vecteur des inconnues, de dimension .

?
est la matrice des contraintes, de dimension .
r

s
•

?
est le terme constant, de dimension .


•
de dimension est le gradient de la fonction objectif.
K

RO-MIM2 – 34/76
Autres formes d’un programme linéaire

Un programme linéaire peut se mettre sous de multiples formes, toutes équivalentes.

On peut changer le sens de l’inégalité, ou passer le terme constant de gauche à droite.

On peut remplacer les inégalités par des égalités en introduisant des variables d’écart toutes
posistives :

1.

— .
ƒ

1
4

4
a

a
–
)

8—
6

/
On peut imposer que toutes les variables sont positives, en posant

a
8)

)
6

/
On peut enfin transposer le programme :

.™
1.
ƒ

1
4

4
a

a
–
)

RO-MIM2 – 35/76
Polyèdre Convexe

œ
L’ensemble est convexe. On l’appelle un

M
@ š


polyèdre convexe ou simplement un polyèdre.
La fonction est trivialement convexe.
K
"
Donc, si un programme linéaire a un minimum local, c’est un
minimum global.

RO-MIM2 – 36/76
Test de faisabilité

Pour trouver un minimum, il faut que le polyèdre :

p
n 

Ÿ
n
soit non vide, ou encore qu’il existe au moins un point qui satisfasse toute les

Œ
p
inégalités .
¡

Ÿ
On peut vérifier cette condition à l’aide du test de Fourier-Motzkin.
On élimine successivement toutes les inconnues de jusqu’à trouver un système
sans inconnues, dont la faisabilité se teste par inspection.
¤£¢
¥

Notations : le vecteur amputé de ses premières composantes.

D
n ¥
¢Œ

.
£¤¢
¥
¤£¢
¥

£¤¢
¥

le système obtenu aprés l’élimination de variables.

¡

p
l

D
RO-MIM2 – 37/76
Test de Fourier-Motzkin

Soit à éliminer . On réparti les contraintes en trois classes :

5
X
ssi .
a ¦



V

@
5
ssi .
X



§
V
4

5
ssi .
X



N
V
5
6

Dans une contrainte de , l’inconnue est déja éliminée.

a ¦

RO-MIM2 – 38/76
Test de Fourier-Motzkin, II

Une contrainte donne une borne inférieure de :

¨
*

)
˜

f
€ 1

/ 4
© €'

)
ª

«
«

/
/
.
)

¬
f

f€ '
Une contrainte donne une borne supérieure de :
V

¨
*

)
f
€ 1

/ 4
)
© '€
ª

«
«

/
/
7
)

¬
f

f€ '
6
Pour éliminer , il suffit d’écrire que chaque borne inférieure est inférieure à chaque borne
)
f

supérieure.

On poursuit jusqu’à élimination de toutes les variables. Au bout de étapes, le système est

T
de la forme :

. 
1h

a
9

qu’il suffit d’inspecter.

RO-MIM2 – 39/76
Correction

,
M-
On dit que le test réussit si , et qu’il échoue dans le cas


T


contraire.
Théorème 6 Si le test échoue, alors le système initial est infaisable.
Supposons a contrario que le système initial a une solution . Les

­
transformations effectuées sur les contraintes sont de simples
manipulations algébriques valides ; on en conclu que les intervalles obtenus
en comparant une borne inférieure et une borne supérieure sont non vides,

<¢
¥


et donc que le système ¡ est faisable.

p
®

®

Ÿ
En poursuivant l’élimination, on en arrive au système d’ordre , qui

o ®
D
n’a plus qu’une seule inconnue et qui est également faisable. Mais le
£
£¢
°¯¥

fait que l’un des indique que l’un des intervalles de variation de
p

est vide, une contradiction.

£

RO-MIM2 – 40/76
Complétude

Théorème 7 Si le test réussit, le système initial est faisable.

On exhibe une solution du système initial en la
construisant de proche en proche à partir de sa dernière
composante. On part du système

M -
6 5

6 5

6 5
T

T
r


"
,
M-

Le fait que les garantit que l’intervalle des


T


valeurs possibles de est non vide. On en choisit une
T

arbitrairement et on la reporte dans le système d’ordre

. Ce système n’a plus qu’une inconnue, , dont
A
?

6 5
!

T
l’intervalle des valeurs possibles est non vide. On poursuit
ainsi jusqu’à avoir donné une valeur à toutes les
composantes de .

RO-MIM2 – 41/76
Remarques

Si on s’astreint à choisir à chaque pas la solution la plus petite,

i.e. la borne inférieure de l’intervalle de variation, on obtient le em
minimum lexicographique de P, les inconnues étant prises dans
l’ordre .

i5
T
"
"
"

Il n’est pas obligatoire de poursuive l’élimination jusqu’à la fin. Si

E²,
-
on s’arrète à l’étape , les variables de deviennent des

² ,
M-
paramètres. Les conditions délimitent les valeurs des


paramètres pour lesquelles le système est faisable. Enfin, le
procédé de sélection ci-dessus donne la valeur paramétrique de
la solution.
L’algorithme peut s’exécuter sans division. La combinaison de la
contrainte et de la contrainte se fait en multipliant
z

X
¦

¦

4

6
la première par et l’autre par et en



§

§
V

}
5

5
!

additionnant.

RO-MIM2 – 42/76
Complexité

On évalue d’abord une borne du nombre de contraintes à l’étape

, soit .

s
 ±

² •

² •
@

4
a
Comme , prend sa valeur maximum

² •

² •
6 @
4
a

6 5
pour  et , à condition que .

³
§
² •

² •
@

4@

6 @
a

6 5

6 5
µ¶´

:
f

Pour le cas le pire, on a donc la récurrence dont

² •
@

:
:h

´
la solution est . C’est aussi une borne du travail à
•
T @

:
effectuer.
La complexité est donc énorme sauf pour les petits systèmes.
Mais la redondance est également énorme, surtout si le système
est creux (a beaucoup de coefficients nuls).
Enfin, il est possible que l’algoritme se termine prématurément.
L’algorithme de Fourier-Motzkin est très simple à programmer,
mais il doit être réservé à de petits problèmes.

RO-MIM2 – 43/76
Un exemple, I

Soit le code :
for(j=i+1; j<n; j++)
for(k=i+1; k<n; k++)
a[j][k] -= a[j][i]*a[i][k]/a[i][i];

L’exécution de ces deux boucles modifie-t-elle le terme a[i][i] (le

pivot) ?
Réponse : le système :

»
¹
·¸

¾½¼

¿
º

À
¹
·¸

¾½¼

¿
·

¿ »
Á
·

À
Á

est il faisable ?

RO-MIM2 – 44/76
 
Y 

Bingo !
Y !Y
Y Y
z
 ? X ? z
Y
! ! ! ! !
X Â
x x X x z x
!
! ! !  !  !  ! 
A
x X z
M M M M M M M
Un exemple, II

      
"      


!Y
Y Y

? ? X
!Y
 !
! !
Y
x x X x

 ! ! !  ! 
!
A X
M M M M M

    
"    
RO-MIM2 – 45/76
Algorithme de Fourier-Motzkin étendu

On peut au cours de l’exécution du test, garder la trace des

combinaisons effectuées. On voit alors que chaque contrainte du
système d’ordre est une combinaison linéaire à coefficients

±
positifs d’au plus deux contraintes du système d’ordre .

! 
±
En généralisant, toute contrainte figurant dans l’algorithme est
combinaison linéaire positive de lignes de . Soit le

$ M


vecteur des coefficients.
Comme dans le système d’ordre toutes les variables ont été

?
éliminées, on en déduit .
@ r
Ã


$

RO-MIM2 – 46/76
Lemme de Farkas

Théorème 8


r

@ r
Ä

M

$ M

M



Å


Y$

$
Y

"
De gauche à droite soit tel que . Soit un

M


v

$

quelconque tel que et . On a .

@ r
Ã

r
$ M


M



$

$
Mais

r

r


@ 


$

$
@

"
De droite à gauche, on exécute l’algorithme de
Fourier-Motzkin étendu. On en tire un tel que

$ M


. On en déduit que , ce qui veut dire que le
@ r

M



$

test a réussi et qu’il est possible de construire un tel que

v
.
r

M


v

RO-MIM2 – 47/76
Programmation linéaire, I

On adjoint au système la contrainte , où

M

Æ M


Æ
"
est une nouvelle variable.
On exécute l’algorithme de Fourier-Motzkin en prenant soin
d’éliminer en dernier.
Æ

Si l’algorithme échoue, le problème n’est pas faisable.

Sinon, la valeur de dans la solution donne la valeur minimum
de . Æ
K
"

Le reste de la solution caractérise un point ou ce minimum est

atteint.

RO-MIM2 – 48/76
Lemme de Farkas affine

p
Théorème 9 Si le système est faisable, alors :

Ÿ
Ç

Êi

Ë

Ç



 

p

q

Ž
¡

¡
Œ Ž

n q

Œ Ž

p
l

ȟ

l
É

É
È

È
g
L’implication de droite à gauche est évidente. De gauche à droite,

p
l’hypothèse revient à dire que le système n’a

¯q
l

g ɟ

Ÿ
pas de solution. D’aprés le lemme de Farkas, ceci implique l’existence de
Ž

tel que et . De plus, ne peut

¡
Ž

Ž
p

¯q
Ÿ

Ÿ
Œ ÌÉ

ŒÌ
n
̌

̌
o

o
g

p
être nul car cela impliquerait que n’a pas de solution. On peut

Ÿ
donc prendre . On pose et il vient :
Ž
p

n q

Œ Ž

Œ Ž
®

Ÿ
Í
n
̌

g



¡
Ž

n q

Ž
p

n q

Œ Ž
l

oÉ

g
d’où la conclusion du théorème.

RO-MIM2 – 49/76
Cones

Un cone est un polyèdre convexe dont les contraintes sont de la

Î
forme .
r
M


Propriété fondamentale : .

Î

Î
Ï M




 v


Ï
w



›

’

œ
Théorème 10 L’objet est un cone.


v
{

{
{
Il suffit de considérer le système :


v

@
{

{
!


{


{

"
et d’utiliser la méthode de Fourier-Motzkin pour éliminer les
. Ce qui reste est un système de contraintes linéaires en


, qui définisssent bien un polyèdre.

RO-MIM2 – 50/76
Réciproque


Théorème 11 Tout cone est engendré par un système fini de

¡
n Ð

Ÿ
rayons .
<­

ÒÑ­
g



g

‘
Ì 
On considère l’objet . est un cone dont on

n Ó

Ó
¡
Ð

Ô
Ÿ
Ì
peut déterminer les contraintes comme ci-dessus :

n Ó

ž
É ‘

Õ
Ð

Ÿ
É


Comme quelque soit , Ì 
appartient à , on en déduit

Ó
Ð
Ÿ
Ì
Õ

. Comme on peut prendre pour les vecteurs unitaires, on en

¡

Ÿ
Ì

B
Õ

déduit ce qui signifie que les vecteurs colonnes de

¡

Õ
Ÿ

appartiennent à .
Ð

Ì 
Soit maintenant un vecteur quelconque de . Pour tout on a

Ÿ


Õ
. En d’autre termes, pour tout tel que , on a
 ¡

Ÿ
Ì

 Ì

É
n


Ž
. On peut donc appliquer le lemme de Farkas affine : il existe
Ÿ

Ÿ
É

tel que . est donc engendré par les vecteurs colonnes de .

Ž

Ð
Õ

Õ
n

RO-MIM2 – 51/76
Théorème de Minkovsky

Théorème 12 Tout polyèdre peut être mis sous la forme :

Ð
n 

g ×
l

l
où est un polytope (polyèdre borné), est un cone et un sous espace linéaire.
Ö

×
ž

p
Soit . On considère le cone
¡
n 

Ÿ
ž

p
où est une nouvelle variable. Il est clair que
¡
n Ø

Ÿ
Ù

Ù
g

ž
est l’ intersection de avec l’hyperplan . On construit les


®
nÙ
rayons de . Ceux dont la coordonnées n’est pas nulle engendrent .

Ö
Ø

Ù
Les rayons dont l’opposé est également un rayon engendrent . Enfin,

×
ceux qui restent engendrent .
Ð

On peut écrire :
ž

Ž

Ú 
 Ž

n Ž
n 

g Ÿ

Ÿ
­

 Ú
Û

 Ü

g
Les sont les sommets, les les rayons et les les lignes.
­

RO-MIM2 – 52/76
Programmation linéaire, II

Le minimum de sous la contrainte est atteint en l’un

Ð
n 

×
l

l

É

des sommets de à condition que soit vide et que .

Ð
×


É
En effet on peut écrire :

l
É

É
Ú

É
Ü

 Ý
n



Puisque n’est pas contraint, on peut faire décroitre a volonté s’il existe un
Ü

É


Ú 
. Il en est de même s’il existe un tel que , puisque . Si est

×
Ÿ

Ÿ
Û¯
Ý

É

vide, le dernier terme n’existe pas, et si , on minimise en prenant

Ð

É

É

.
Ÿ
nÚ

Soit un sommet où est minimum, et un sommet où .

ÉÍ
É

<­

<­
­Œ

­Œ



Supposons que dans l’expression de ait un coefficient non nul. Le point

< Ž
<­
g


est dans et sa fonction objectif a diminué. On en déduit que

< Ž


<­

­Œ
o

la solution d’un programme linéaire est l’un quelconque des sommets de où

Ö
atteint son minimum.
É


RO-MIM2 – 53/76
Critique

La méthode ci-dessus est inefficace car il faut utiliser

Fourier-Motzkin pour trouver la décomposition de , et aussi

š
parce que le nombre de sommets peut être très grand (de l’ordre
de , le coefficient du binome).
Þ
T ´

Il existe un algorithme plus efficaces que Fourier-Motzkin pour

décomposer un polyèdre, l’algorithme de Chernikova, mais le
nombre de sommets ne change pas.

RO-MIM2 – 54/76
Dualité, I

œ
Théorème 13 Si les deux ensembles et



›

œ
sont non vides, on a :

@ r
$ M


$

K


@ œ

@ œ
r

@ r
Ã
@ ß





$ M


áà


" â

Soit par exemple (resp. ) un point de l’ensemble de gauche
ã

ã
$
(resp. de droite). On a :
@ ã

ã
r


K

$
"

"
"
Il en résulte que et existent et que .
ß


â

RO-MIM2 – 55/76
Dualité, II

On peut supposer que (resp. ) est le point où le maximum (resp.

ã
$
le minimum) est atteint. En tout point tel que on sait que

r



!
, on peut donc appliquer le lemme de Farkas affine :
ã


K

!K
"

"

r
Ä



M




!K
Y

@
a

!


"

"

"
On en déduit et . Il en résulte que fait

r
@ ã


K

K
@
a
"

partie de l’ensemble de droite :

ß


@ 

! 


â

a
"

"
On en déduit .
@ ß

RO-MIM2 – 56/76
Analyse de sensibilité

’
Variation de

r



áà
ä

K
@
œ
avec ?

’
Par dualité,




M
ä

$
@
œ
. Or ce polyèdre ne dépend

@ r


K

pas de . Interprétation géométrique :


aussi longtemps que reste dans le cone


des directions admissibles, l’optimum

ã
$
ne change pas. Donc :
cone des optimum

ã



ä

$
@

"
"
directions
admissibles

Pour en savoir plus, il faut faire de la pro-

grammation linéaire paramétrique.

RO-MIM2 – 57/76
Complémentarité

Théorème 14

åær
t
Y z

} 


}$

@
}
!
"

"

"
ã


@ ã
r

r



$

$
@
!

!
"

"

"

"

"

ã

@ ã

@ ã
r


K

$
@

!
"

"

"

"

"

Mais chaque terme du produit scalaire est

r
ã

ã
$

!
"

"
positif, donc si la somme est nulle chaque terme est nul.

RO-MIM2 – 58/76
Dualité généralisée

Il existe une très grande variété de théorèmes de dualité, suivant la

nature des contraintes et le signe des variables. En première
approximation, on peut utiliser le tableau suivant :

Primal Dual
objectif (Min) second membre
second membre objectif (Max)

j
¡

¡



Contrainte : variable
C

Ÿ
­ç
Contrainte : variable non contrainte en signe
C
n


ê
Variable contrainte :

é
Ÿ
è

Variable non contrainte en signe contrainte :

é
n
è

On trouvera dans Schrijver une formulation plus précise.

RO-MIM2 – 59/76
Algorithme du Simplexe, I

« Trouver le point le plus bas d’un vase ». Fourier, 1828.

Formalisation par Danzig, 1950.

RO-MIM2 – 60/76
Méthodes externes, méthodes internes

optimum

Méthodes internes : il faut connaître un point faisable. On peut

arréter la recherche avant l’optimum.
Méthodes externes : il n’y a pas besoin de connaître un point
faisable.

RO-MIM2 – 61/76
Ordre lexicographique

Définition :

Y X
ë

N
5$

V$
$@

@
V

WV
5

6 5

6 5


"
ì
9 ìì

ì
9 ìì
9

9
est un ordre total.
ë

L’ordre par composantes n’est pas total.

n’est pas un ordre.
N
K

$
"

"

D’où l’intérêt de remplacer par .



 

K

í
"
On peut toujours ajouter une nouvelle variable et la contrainte

v
à condition que soit la première inconnue.
v M

v
"

Cette technique évite les problèmes bien connus de

dégénérescence.

RO-MIM2 – 62/76
Algorithme du simplexe externe ou dual

Généralisation :
Résoudre :

ñ Eðï
î
ò
ñ Eðï
î
ò


ô

õl

Ÿ
nÌ

Ù


Ÿ
Ù

¡

p
l

Ÿ
Tailles : , , .
È ¡

È p
ó
D

B
È

Au commencement,

÷ ö
ø

Ÿ
n ô

õ
nÙ

n
g


¡

RO-MIM2 – 63/76
Invariants

Les vecteurs colonnes de sont lexicopositifs au démarrage et


le restent tout au long de l’algorithme.
est un sous-ensemble de . La condition est donc

Æ M


Æ

$

toujours vérifiée.
D’une étape à l’autre, croît dans l’ordre lexicographique.

]
Ces invariants sont vérifiés au début de l’algorithme.

RO-MIM2 – 64/76
Cas de base

Si , on a trouvé la solution. Il suffit de faire , ce qui

]M


Æ@
satisfait les contraintes. On a .

5 ]
@

T
ì
9 ìì
9
De plus, c’est le minimum lexicographique : toute autre valeur
positive de ajoute à un vecteur lexicopositif.
Æ

Soit . Si , le problème n’a pas de solution.


t
Y z





]
N
{

}
{

RO-MIM2 – 65/76
Changement de variable

Soit et (le pivot). On élimine en faveur de :





]
N

}Æ

$
{

}
{

{
Q

Q


ú 

ú 
]
}Æ

Æ
@

}
{

}
{
ú

"{
!

!
}û
ú
8


Q
Vú 

V 

ú 

V 

V 


V ]

]
V$

}Æ
@

}
{
ú

}
{

}
"{
!

!
}û
ú
8

Remarquer que est positif, et que est lexicopositif.



V 
]
{

}
{

}
!

Donc, croit selon l’ordre lexicographique.

]

Comme , le vecteur colonne reste lexicopositif.



z

§
}
{

Il reste à garantir que le vecteur colonne reste lexicopositif.

RO-MIM2 – 66/76
Choix du pivot

Si est négatif, il n’y a pas de problème.

ú 
{
Sinon le nouveau vecteur colonne est égal, à un coefficient positif
près, à :

Q
åú 

ú 


{

}
"{
!
å
Il faut donc choisir pour que et que le « vecteur réduit »


z


§
}
{
Q

soit le plus petit possible.




}

}
{
å

Un tel choix est toujours possible sauf si on est dans le cas d’un
système infaisable.

RO-MIM2 – 67/76
Convergence

Observer que l’état de l’agorithme est entièrement déterminé

quand on sait quelles sont les composantes de qui sont dans

Æ
(les variables en base).
Or est de taille et de taille , il n’y a donc que

Þ
T
$

4
´

T
ombinaisons possibles.
L’algorithme ne peut pas boucler, car croit dans l’ordre

]
lexicographique.
Comme n’est pas un polynome en et , l’algorithme
Þ
T

•
4
´

n’est pas polynomial.

On peut construire des cas pathologiques qui demandent un
temps exponentiel.
Mais en pratique (et en probabilité) le nombre d’opérations est en
? :


.
ü

RO-MIM2 – 68/76
Questions numériques, I

Du point de vue numérique, l’algorithme du Simplexe est

analogue à la méthode de Gauss, avec une règle particulière
pour le choix du pivot.
Si l’on connaît la matrice des inconnues de base, l’algorithme ne
fait qu’inverser celle-ci, tout en appliquant les mêmes
transformations aux inconnues hors base.
Les résultats sont donc donnés par des formules de Cramer.
On peut faire les calculs en virgule flottante. Il y a alors
accumulation d’erreurs d’arrondi, qui peuvent faire que la solution
finale n’est pas faisable (en particulier pour les contraintes
saturées).
Il faut alors développer des méthodes de correction. En général
la solution est faisable, mais l’optimalité n’est pas garantie.

RO-MIM2 – 69/76
Questions numériques, II

On peut rendre la matrice des contraintes entières, et essayer de

mener les calculs exactement (algorithmes « tout entiers »).
Les nombres à manipuler sont des déterminants de Cramer. On
peut donc les borner à l’aide de l’inégalité de Hadamard :

’
r

5 r

r
LýP


]

T
"
"
"


où les sont les vecteurs colonnes (ou les vecteurs lignes) de
r
{

.
r

Il en résulte que la taille des nombres à manipuler est bornée par

fois la taille du plus grand élément de . Cette borne est

r
?

rarement atteinte.
Il faut utiliser des arithmétiques en précision arbitraire, telle la
librairie GMP.

RO-MIM2 – 70/76
Algorithme primal

On prend le problème sous la forme équivalente suivante :







K
@

"
r


@
M


On peut supposer que les lignes de la matrice des contraintes

r
sont linéairement indépendantes : on peut éliminer les lignes
redondantes.
est de dimension avec nécessairement .
r

•N
s
•

?
Dans le cas contraire, le système aurait au plus une solution et
¡

p
n

le problème serait trivial.

RO-MIM2 – 71/76
Base

Une « base » est une matrice carrée extraite de

r
s
?

?
inversible. On partitionne en deux blocs , la base, et le

^
ÿ

_
reste de la matrice. On partitionne de même en et en

K

 K ÿ

.
K

u
6 5

La solution associée à une base est le vecteur . Il


þ



satisfait évidemment à la contrainte .


@
La base B est réalisable ssi la solution correspondante satisfait

6 5
également à la contrainte , c’est-à-dire si .
M

M
þ



@
A une base réalisable correspond une valeur de l’objectif,
ÿ

6 5

.

þ
K

"

_
Est-il possible d’améliorer cet objectif en faisant varier ?

RO-MIM2 – 72/76
Recherche de l’optimum, I

_
Si n’est plus nul, on a :

6 5


T

þ

^
@

!
ÿ

ÿ
6 5

6 5


T



þ

^
K

!K
@

"

"
_

6 5
Le vecteur est le vecteur des coûts réduits.

^
K

!K
@

"
Si fait partie de , comme il est nul on ne peut que
T
{

l’augmenter pour que la solution reste faisable. Ceci fait décroitre



à condition que .



N
K

Si tous les coûts réduits sont positifs, on a trouvé l’optimum.

Sinon, on choisit un dont le coût réduit est négatif (par
{

exemple celui dont le coût réduit est minimum).

RO-MIM2 – 73/76
Recherche de l’optimum, II

_
Puisque on fait croitre et que les autres composantes de

{
restent nulles, la seule contrainte sur la valeur de est

{
6 5


. Il y a deux cas possibles :

M
þ


!

6 5
Toutes les composantes de la colonne de sont

@ þ

^
négatives. Alors n’est pas borné, et le minimum est .

!
Sinon, à chaque composante correspond la borne


§
{
V
Q

. Soit l’indice de la plus petite de ces bornes.



z
þ
{

{
V

Q
Le point correspondant à sauf pour :

@ X

þ

@

@
}

}
{

est faisable et la valeur de  est inférieure à celle du point de
départ.

RO-MIM2 – 74/76
Recherche de l’optimum, III

La base qui correspond au nouveau point courant s’obtient en

remplaçant dans le colonne par la colonne .

z
On poursuit l’algorithme en inversant la nouvelle base et en
calculant la nouvelle solution et les nouveaux coûts réduits.
L’algorithme se termine si à chaque pas la valeur de l’objectif
décroît strictement.
En effet il n’y a que
£ Ô


bases possibles et la condition de décroissance
stricte empèche tout bouclage.
Cependant l’algorithme peut boucler en cas de dégénérescence
(il semble que ce soit très rare).
Comme pour l’algorithme dual, on peut mener les calculs de
façon incrémentale (il suffit d’un seul pivot de Gauss pour
inverser la nouvelle base).

RO-MIM2 – 75/76
Recherche du point faisable initial

‘



Il s’agit de trouver un point dans le polyèdre . Soit

p


g Ÿ

®
n
le vecteur dont tous les éléments sont égaux à 1, et soit un nouveau vecteur de

Ì
même taille que . On considére le problème :

Eðï

®
î

Ì



Ÿ


Ÿ
Ì


¡

p
l
Ì


Il est facile de voir que le point est faisable. On est donc

g p
g Ÿ

Ÿ

nÌ

î

n

en position d’appliquer l’algorithme précédent.

Si , il est facile de voir que le point .
n Ó


Ÿ


Ì

Réciproquement, si , alors est faisable pour le problème

Ó

Ó


g Ÿ


augmenté, donc le minimum est nul. Si inversement le minimum n’est pas nul,


est vide.

RO-MIM2 – 76/76