38890475-cours1

Recherche operationnelleStefan Balev

[email protected]

LIH – Universite du Havre

Licence Info 2003/2004 Recherche operationnelle – p.1/40

Introduction


Un peu d’histoire

1654 Pascal, Fermat esperance mathematique

Bernoulli, Waldegrave problemes de decision dans l’incertain

1776 Monge un probleme economique de nature

combinatoire – deblais et remblais

1838 Cournot theorie mathematique des richesses

1917 Erlang theorie des files d’attente

1921-25 Borel theorie des jeux

1936 Konig theorie des graphes

1939-45 Kantorovich programmation lineaire

1940 Blackett dirige la premiere equipe de RO


Un peu d’histoire

Blackett traite rapidement et avec succes difficiles questions, telles que :

implantation optimale de radars de surveillance

protection des convois de navires

. . .

L’efficacite de son equipe est du a:

composition heterogene, competences variees et complementaires

information et donnees completes et fiables

les decisions sont reservees aux commettants


Pourquoi une apparition si tardive ?

L’economie parvient a une certaine maturite et fait recours

aux mathematiques

Les problemes sont devenus complexes, en raison de la taille

croissante des entreprises et les liens entre elles

Les acquis theoriques ne seraient rien sans moyens de

calcul. Seuls les ordinateurs sont aptes a resoudre les

problemes pratiques.


(Tentative de) definition

La recherche operationnelle est l’ensemble de methodes et

techniques rationnelles d’analyse et de synthese des

phenomenes d’organisation utilisables pour elaborer de

meilleures decisions.

La RO ne s’occupe pas des problemes dans lesquels une

solution de bon sens intervient naturellement. Son domaine est

celui des situations dans lesquelles, le sens commun se revele

faible ou impuissant.


Domaines d’application

Problemes combinatoires : definition des investissements les

plus rentables; optimisation des niveaux d’activite, des

affectations, des transports; ordonnancements,. . .

Problemes stochastiques (c-a-d ou intervient le hasard) :

files d’attente; fiabilite et surete de fonctionnement des

equipements; gestion de la production,. . .

Problemes concurrentiels : definition de politiques

d’approvisionnement, de vente,. . .


Les problemes combinatoires

L’homme envisage difficilement la multiplicite des combinaisons

qui se presentent, meme dans les moindres faits de la vie,

lorsque plusieurs variables peuvent prendre, chacune, des etats

differents.

Exemple : Combien faut-il de temps a une famille de 8

personnes, prenant en commun deux repas journaliers, pour

epuiser toutes les possibilites de se grouper autour de la table

familiale ?



L’homme envisage difficilement la multiplicite des combinaisons

qui se presentent, meme dans les moindres faits de la vie,

lorsque plusieurs variables peuvent prendre, chacune, des etats

differents.

Exemple : Combien faut-il de temps a une famille de 8

personnes, prenant en commun deux repas journaliers, pour

epuiser toutes les possibilites de se grouper autour de la table

familiale ?



max{f(x) : x ∈ X}

f : X → R – fonction economique (objective)

X – ensemble de solutions possibles (realisables). X est un

ensemble fini, mais de taille enorme.



Probleme d’affectation : n taches doivent etre affectees a n

machines (1 tache par machine). Le cout d’execution de la tache

i par la machine j est cij . Trouver l’affectation qui minimise le

cout total.

Probleme du voyageur de commerce : Un voyageur de

commerce doit visiter n villes. La distance entre les villes i et j

est cij . Trouver le plus court trajet.

Les solutions possibles sont n!. Pour n = 20 l’enumeration des

affectations (trajets) possibles, a vitesse d’un million par seconde,

prendrait 77 096 ans !Licence Info 2003/2004 Recherche operationnelle – p.10/40

Les domaines de l’aleatoire

Exemple : Dans une grande entreprise, la moyenne des entrees

des personnels au bureau du correspondant de la securite

sociale est d’une personne par 4 min. Un employe peut servir, en

moyenne, une personne toutes les 3 min 20 sec. Combien

d’employes faut-il embaucher dans le bureau ?


Les situations de concurrenceLe choix d’une strategie, dans une situation donnee depend des decisions des

concurrents. Il s’agit, a la fois, d’un probleme combinatoire et d’une situation

de hasard.

Exemple : Un fabricant A hesite, a chaque campagne de vente, entre la

hausse, le maintien et la diminution de ses prix de vente, sachant que son

concurrent peut lui opposer les memes strategies. Les gains de chaque paire

de choix sont :

A concurrent

+ = -

+ 10 -1 -4

= 6 0 -2

- 10 -1 2Licence Info 2003/2004 Recherche operationnelle – p.12/40

RO — une discipline-carrefour

analyse économiqueéconomie d’entreprise

ECONOMIE

algorithmesstructures de données

bases de données

INFORMATIQUE

théorie des systèmesméthodes d’optimisation

méthodes statistiques

MATHEMATIQUES

traitementdu modèle

interprétationdes résultats

élaborationdu modèle

RECHERCHEOPERATIONELLE


Contenu du coursProgrammation lineaire

aspect geometrique

algorithme du simplexe

dualite

applications

Theorie des flots

flot maximum et coupe minimum

algorithme de Ford et Fulkerson

applications

problemes de transport et d’affectation


Contenu du coursProgrammation en nombres entiers

methodes de troncatures

methodes par separation et evaluation (branch-and-bound)

relaxation lagrangienne

Programmation dynamique

Algorithmes heuristiques


Bibliographie

R. Faure, B. Lemaire, C. Picouleau. Precis de recherche

operationnelle

I. Charon, A. Germa, O. Hudry. Methodes d’optimisation

combinatoire

M. Sakarovitch. Optimisation combinatoire

G. Nemhauser, A. Wolsey. Integer and combinatorial

optimization


Programmation lineaire


La forme standard du PPL

Maximiser c1x1 + c2x2 + · · ·+ cnxn

s. c. a11x1 + a12x2 + · · ·+ a1nxn ≤ b1

a21x1 + a22x2 + · · ·+ a2nxn ≤ b2

......

......

am1x1 + am2x2 + · · ·+ amnxn ≤ bm

x1 ≥ 0, x2 ≥ 0, . . . , xn ≥ 0

n variables, m + n contraintes



Maximiser

n∑

j=1

cjxj

s. c.

n∑

j=1

aijxj ≤ bj, i = 1, . . . ,m

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



max{cx | Ax ≤ b, x ≥ 0}

ou

A =

a11 . . . a1n

......

am1 . . . amn

, x =

x1

...

xn

, b =

b1

...

bm

,

c = (c1 . . . cn)


Transformation en forme standard

Minimiserf ⇔ Maximiser − f

α ≥ β ⇔ −α ≤ −β

α = β ⇔ α ≤ β, −α ≤ −β

y ∈ R ⇔ y = y+ − y−, y+ ≥ 0, y− ≥ 0


Convexite

P = {x | Ax ≤ b, x ≥ 0} ⊆ Rn – solutions realisables

P est un polyedre convexe dans Rn (si x ∈ P , y ∈ P et

0 ≤ λ ≤ 1 alors λx + (1 − λ)y ∈ P )

convexe non convexe

Le maximum de la fonction objective, s’il existe, est atteint au

moins en un sommet de P .Licence Info 2003/2004 Recherche operationnelle – p.22/40

Les sommets de P

Chacune des m + n contraintes definit un hyperplan dans Rn

(ligne droite dans R2). Un sommet est l’intersection de n

hyperplans. Il y a au plus(

m+nn

)

sommets.

x1 + 3x2 ≤ 18

x1 + x2 ≤ 8

2x1 + x2 ≤ 14

x1 ≥ 0

x2 ≥ 0 (0,0) (7,0)

(8,0)(18,0)

(0,6)

(0,8)

(0,14)

(6,2)

(3,5)(4.8,4.4)


Approche naıve

Idee : On est s ur de trouver la solution optimale dans un sommet. Donc il suffit

de parcourir tous les sommets et de prendre le meilleur.

Generation d’un sommet : Choisir n parmi les m + n contraintes. Resoudre

le systeme lineaire ou les n contraintes choisies sont a egalite. Si le systeme

a une solution et si cette solution satisfait aux m contraintes restantes, cette

solution est un sommet de P .

Probleme : le nombre de sommets. Il faut resoudre(

m+n

n

)

systemes lineaires.

Exemple : pour m = 400 et n = 200 il faut resoudre environ 2, 5 × 10164

systemes lineaires, ce qui depasse le nombre estime des electrons et des

protons dans l’Univers !


Approche naıve

Idee : On est s ur de trouver la solution optimale dans un sommet. Donc il suffit

de parcourir tous les sommets et de prendre le meilleur.

Generation d’un sommet : Choisir n parmi les m + n contraintes. Resoudre

le systeme lineaire ou les n contraintes choisies sont a egalite. Si le systeme

a une solution et si cette solution satisfait aux m contraintes restantes, cette

solution est un sommet de P .

Probleme : le nombre de sommets. Il faut resoudre(

m+n

n

)

systemes lineaires.

Exemple : pour m = 400 et n = 200 il faut resoudre environ 2, 5 × 10164

systemes lineaires, ce qui depasse le nombre estime des electrons et des

protons dans l’Univers !


L’algorithme du simplexe

Idee : Parcourir les sommets de P de facon plus intelligente.

Passer iterativement d’un sommet a un sommet adjacent de

facon a augmenter la valeur de la fonction a optimiser jusqu’a

trouver un sommet ou le maximum est atteint.

0 140

180

180

210


L’algorithme du simplexe

Initialisation : Choisir un sommet x0 ∈ P , t = 1

Iteration t : Soient y1, . . . , yk tous les sommets voisins de

xt (les sommets relies avec xt par une arete).

Si cxt > cys, s = 1, . . . , k, stop. La solution optimale

est xt.

Sinon, choisir un voisin ys, tel que cys ≥ cxt. Poser

xt+1 = ys et passer a l’iteration t + 1.


Simplexe – pourquoi c a marche ?

Grace a la convexite du polyedre des contraintes et a la linearite

de la fonction objective, il n’y a pas de maxima locaux.

montagne convexe montagne non−convexe


Convergence de l’algorithme

On se deplace de sommet a sommet en augmentant la valeur de

la fonction z. Le nombre de sommets et fini (au plus(

m+nn

)

).

Si la fonction objective est bornee, on va finir par trouver le

maximum

Si elle ne est pas bornee, on va le detecter (pas de candidat

a entrer en base)


Degenerescence et cyclage

B b x1 x2 x3 x4 x5 x6

x3 1/2 0 0 1 1/2 0 0

x5 0 2 -4 0 -3 1 0

x6 0 -1 3 0 -2 0 1

z 4 2 -1 0 -4 0 0

x3 1/2 0 0 1 1/2 0 0

x1 0 1 - 2 0 -3/2 1/2 0

x6 0 0 1 0 - 7/2 1/2 1

z 4 0 3 0 -1 -1 0

La valeur de z ne change pas. On reste dans le sommet

(0, 0, 0.5).Licence Info 2003/2004 Recherche operationnelle – p.29/40

Degenerescence et cyclage

Les solutions de base realisables avec une ou plusieurs variables

de base a zero sont dites degenerees.

Si on fait sortir de la base une variable a zero, on ne change pas

la valeur de z. Apres quelques iterations on risque de retrouver

une base deja visitee.

Regle de Bland: lorsque l’on a choix sur la variable entrante ou

sur la variable sortante, on choisit toujours celle de plus petit in-

dice.


Demarrage de l’algorithme

z = max{cx | Ax ≤ b, x ≥ 0}

Si b ≥ 0, il y a un dictionnaire evident (celui des variables

d’ecart).

xe = b − Ax

Sinon, il faut trouver une base realisable de depart.


Methode a deux phases

On introduit un probleme auxiliaire

z′ = min{x0 | Ax −

(

1...1

)

x0 ≤ b, x ≥ 0; x0 ≥ 0}

Evidement, ce probleme est admissible (x0 = −mini bi,

xj = 0, j = 1, . . . , n est une solution).

Si z′ = 0 alors nous avons une solution du probleme initial.

Si z′ > 0 alors le probleme initial est inadmissible


Methode a deux phases (exemple)

Maximiser x1 − x2 + x3

s. c. 2x1 − x2 + 2x3 ≤ 4

2x1 − 3x2 + x3 ≤ −5

−x1 + x2 − 2x3 ≤ −1

x1 , x2 , x3 ≥ 0


Forme matricielle

z = max{cx | Ax = b, x ≥ 0}

(contraintes de type “=” apres l’introduction de variables d’ecart)

Soit xB le vecteur de variables en base et xN le vecteur de variables hors base. Le

probleme s’ecrit

BxB + NxN = b, d’o u

xB + B−1NxN = B−1b = b

La fonction objective s’exprime comme

z = cBxB + cNxN = cBb + (cN − cBB−1N)xN


Dualite


Probleme dual

Probleme primal (P)

n∑

j=1

cjxj → max

n∑

j=1

aijxj ≤ bj , i = 1, . . . ,m

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

ou

max{cx | Ax ≤ b, x ≥ 0}

Probleme dual (D)

m∑

i=1

biyi → min

m∑

i=1

aijyi ≥ cj , j = 1, . . . , n

yi ≥ 0, i = 1, . . . ,m

ou

min{yb | yA ≥ c, y ≥ 0}

Proposition. Le dual du dual est le primal


Theoreme de dualite (1)

Proposition. Soit x une solution realisable de (P) et y une

solution realisable de (D). On a :

n∑

j=1

cjxj ≤

m∑

i=1

biyi

De plus, si les deux quantites sont egales, alors x est une

solution optimale de (P) et y est une solution optimale de (D).

Theoreme. Si (P) a une solution optimale x∗, alors (D) a une

solution optimale y∗ et cx∗ = y∗b.


Theoreme des ecarts complementaires

Theoreme. Une solution realisable x∗ de (P) est optimale si et

seulement s’il existe une solution realisable y∗ de (D), telle que:

si∑n

j=1 aijx∗j < bi, alors y∗i = 0;

si x∗j > 0, alors

∑mi=1 aijy

∗i = cj .


Interpretation economique du dual (1)

bi – la quantite totale de la ressource i;

aij – la quantite de la ressource i consommee pour fabriquer

une unite du produit j;

cj – la valeur unitaire du produit j.

yi represente la valeur unitaire de la ressource i. Elle est souvent

appelee prix implicite. C’est le montant maximum que l’on sera

pret a payer pour obtenir une unite supplementaire de la

ressource i ou encore le prix minimum auquel on serait pret a

vendre une unite de la ressource i.


Interpretation economique du dual (2)

Supposons que quelqu’un souhaite acquerir les ressources de l’entreprise.

Quel est le prix a proposer pour chaque ressource ?

Soit yi le prix propose pour une unite de la ressource i. Le prix total sera

m∑

i=1

biyi → min

Le prix propose doit etre tel que ce soit plus interessant pour l’entreprise de

vendre ses ressources que de fabriquer elle meme les produits:

m∑

i=1

aijyi ≥ cj, j = 1, . . . , n


Documents

38890475-cours1