Td1&2-2020 Recherche opérationnelle PDF

Preview

Summary

Optimisation Linéraire et non-linéaire, Résolution graphique d’un programme linéaire, Le problème du restaurateur, Affectation de bureaux...

Description

Université de Lorraine, Master de mathématiques Optimisation Linéraire et non-linéaire

2015-2016

TD1 : Modélisation

Exercice 1. Résolution graphique d’un programme linéaire (pb de production) Une usine fabrique deux produits P1 et P2 en utilisant 4 machines M1 , · · · , M4 . Chacun de ces deux produits nécessite un temps de passage donné (en heures) sur chacune des 4 machines. Les temps de passage par unité de produit sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque machine n’est disponible que pendant une certaine durée, également indiquée dans le tableau. M1

M2

M3

M4

P1 P2

0h 3h

1,5h 4h

2h 3h

3h 0h

disponibilité

39h

60h

57h

57h

Les produits P1 et P2 rapportent respectivement les bénéfices B1 = 1700 euros et B2 = 3200 euros par unité. On cherche à déterminer le plan de production pour maximiser le bénéfice total. 1. Modéliser ce problème sous forme de programmation linéaire (PL). Donner la forme canonique pure et la forme standard du programme linéaire. 2. Résoudre graphiquement le PL.

Exercice 2. Le problème du restaurateur Un restaurateur a constaté que sa clientèle aime les coquillages. Lorsqu’il en propose dans son restaurant, ses clients les consomment jusqu’à épuisement de sa livraison du jour. Sa carte comporte deux plateaux : — un plateau "riche" à Pr euros qui comporte nr1 oursins, n2r palourdes, nr3 huîtres — un plateau "simple" à Ps euros qui comporte ns1 oursins, ns2 palourdes, ns3 huîtres 1. Un jour donné, son fournisseur lui a livré k1 oursins, k2 palourdes et k3 huitres. Comment doit-il répartir les coquillages entre les deux sortes de plateaux pour réaliser un chiffre d’affaire maximal ? Modéliser ce problème sous forme de programmation linéaire. Ecrire la forme canonique pure et la forme standard du PL. 2. En début de soirée, une de ses amies vient le trouver. Elle a plus d’invités que prévu et manque de coquillages alors que les magasins sont fermés. Elle lui propose de lui racheter tous ses coquillages. Quel prix minimum peut-elle proposer pour chaque oursin, chaque palourde et chaque huître afin qu’il ne soit pas tenté d’en conserver une partie pour composer quelques plateaux ? Modéliser ce nouveau problème et comparer-le au précédent.

1

Exercice 3. Répartition de tâches On découpe un programme en n procédures (tâches) que l’on veut exécuter sur un ordinateur possédant m processeurs. A chaque procédure effectuée sur un processeur donné, il correspond un coût en temps de calcul. Ainsi pour la procédure i effectuée sur le processeur j, le coût est cij > 0. Chacune des n tâches doit être effectuée par un et un seul processeur. Mais chaque processeur peut exécuter plusieurs tâches ou pas du tout. On cherche à minimiser le coût total d’exécution des n procédures. 1. Modéliser ce problème sous forme d’un problème de programmation linéaire faisant intervenir des variables binaires. Modéliser la variante suivante (plus réaliste...) qui consiste à minimiser le plus grand coût d’exécution. 2. Dans ce qui précède, on a négligé le coût de communication entre 2 procédures exécutées sur 2 processeurs différents. On considère à présent qu’il faut tenir compte d’un coût de communication supplémentaire d il > 0 si les procédures i et l sont exécutées sur des processeurs différents (on a d ii = 0). Modifier la modélisation précédente (sans changer de variables) pour minimiser le coût d’exécution et le coût de communication.

Exercice 4. Stockage Une entreprise de service vidéo à la demande (vod) stocke tous ses fichiers vidéos sur un ensemble de disques durs identiques qui ont tous la même taille. L’entreprise souhaite utiliser le minimum de disques durs pour le stockage. Elle dispose de n fichiers vidéo de taille c1 , · · · , cn avec m disques durs identiques de taille C. On stocke tous les fichiers sur les disques durs. Pour qu’un stockage soit admissible il faut que la somme des tailles des fichiers stockés sur un disque soit inférieure ou égale à C (on ne peut pas dépasser la capacité d’un disque...). De plus, un fichier n’est stocké qu’une seule fois sur un seul disque. Déterminer un stockage consiste alors à déterminer sur quel disque j est stocké le fichier i donné. On cherche à déterminer le stockage (admissible) des fichiers sur les disques durs de façon à minimiser le nombre de disques durs utilisés. En considérant (entre autres) les variables binaires yj pour indiquer si le disque dur j est utilisé ou non, modéliser ce problème par un programme linéaire portant uniquement sur des variables binaires.

Exercice 5. Affectation de bureaux Une entreprise va emménager dans de nouveaux locaux. Ceux-ci se composent de n bureaux identiques. Chacun de ces bureaux peut accueillir indistinctement l’un des n services de l’entreprise. La disposition des bureaux est connue et on note d jl la distance entre les bureaux j et l. L’entreprise a effectué dans les anciens locaux des statistiques sur les va-et-vient entre les n services à installer dans les n bureaux. Elle dispose du nombre cik de fois où des employés vont du service i au service k et où des employés vont du service k au service i. L’entreprise souhaite affecter les services aux bureaux de sorte que la distance totale parcourue par les employés soit la plus petite possible. 1. Combien y-a-t-il de possibilité d’affecter les n services aux n bureaux ? L’ordinateur dont vous disposez peut effectuer 1 milliard d’opérations à la seconde. Pour n = 30, estimer le temps mis pour obtenir par une méthode exhaustive (c’est-à-dire en essayant toutes les solutions), l’une des meilleures configurations donnant la distance totale parcourue minimale (indication : 30! ≃ 1032 ). 2. Modéliser le problème qui consiste à placer les services dans les bureaux de manière à minimiser la somme des distances parcourues par les employés. Vous pourrez introduire une variable binaire qui indique si un service donné est placé ou non dans un bureau donné. Vous obtiendrez ainsi un problème de programmation quadratique. 3. Transformer le modèle quadratique précédent en un problème de programmation linéaire en introduisant une variable à 4 indices.

2

Exercice 6. Problème d’une entreprise de vols "charter" Une compagnie aérienne de vols "charter" doit effectuer sur une plage de temps donné, un certain nombre de vols pour lesquels on connaît : — — — —

ADi l’aérogare de départ AAi l’aérogare d’arrivée HDi l’heure de départ HAi l’heure d’arrivée

Un avion peut effectuer un vol j à la suite d’un vol i à condition qu’un intervalle de temps suffisant existe entre l’arrivée de i à l’instant HAi en AAi et le départ de j à l’instant HDj en ADj de manière à permettre éventuellement son transfert en vol à vide de AAi à ADj qui dure Tij et la préparation du vol suivant qui dure p. Pour leur premier vol, on suppose les avions disponibles au bon endroit et après leur dernier vol, on les laisse là où ils viennent d’atterrir. 1. Un premier problème à résoudre consiste à minimiser le nombre total d’avions nécessaires. 2. Un deuxième problème consiste à fixer le nombre d’avions et à minimiser la durée des trajets à vide. Modéliser ces deux problèmes de programmation linéaire sous les formes canoniques et standards.

Exercice 7. Identification de paramètres et programmation linéaire On considère deux grandeurs physiques t et y qui sont liées entre-elles par une relation fonctionnelle du type y = f (t). On dispose d’un modèle pour la fonction f . On sait que f est une combinaison linéaire de n fonctions élémentaires φ1 , · · · , φn connues : f (t) = fx (t) = x1 φ1 (t) + · · · + xn φn (t) où x = (x1 , · · · , xn )⊤ ∈ Rn sont des paramètres réels qu’on cherche à identifier. Pour cela, on réalise une série de m mesures (ti , yi )1≤i≤m et on cherche à minimiser le plus grand écart absolu entre le modèle donné par fx et les mesures : (1) minn max |fx (ti ) − yi | x∈R 1≤i≤m

Remarques : si l’on remplace l’ob jectif (1) par la somme des carrés des écarts (i.e. min n x∈R

m X

|fx (ti ) − yi |2 ,

i=1

alors on obtient exactement la formulation en moindres carrés...). On notera kxk∞ = max1≤i≤n |xi | et kxk1 =

n X

|xi | les normes sur Rn d’un vecteur x = (x1 , · · · , xn )⊤ .

i=1

1. Ecrire le problème (1) sous la forme

min kAx − bk∞ := minn max |Axi − bi |

x∈Rn

x∈R 1≤i≤m

(2)

en précisant ce que valent le vecteur b = (b1 , · · · , bm )⊤ et la matrice A ∈ Mm×n . 2. Transformer le problème précédent en un problème de programmation linéaire sous forme canonique pure. (Indication : introduire la variable e = maxi |Axi − bi |). 3. On considère à présent la fonction ob jectif minn kAx − bk1 := minn

x∈R

x∈R

m X

|Axi − bi |

(3)

i=1

Transformer ce nouveau problème en un problème de programmation linéaire sous forme canonique pure. 3

Solution des exercices du TD 1 Exercice 1. 1) Variables : on note xj la quantité de produits Pj , j = 1, 2. Fonction objectif :

max(x1 ,x2 ) F (x1 , x2 ) = 1700x1 + 3200x2   3x2 ≤ 39     1  .5x1 + 4x2 ≤ 60 2x1 + 3x2 ≤ 57 Contraintes :   3x1 ≤ 57     x , x ≥ 0 (positivité des variables) 1 2 Il s’agit d’un P.L. sous forme canonique pure (uniquement des inégalités dans les contraintes)

Forme standard. On introduit les quatre variables d’écarts e1 , · · · , e4 . Les contraintes s’écrivent alors  3x2 + e1 = 39       1.5x1 + 4x2 + e2 = 60 2x1 + 3x2 + e3 = 57   3x1 + e4 = 57     x , x , e , · · · , e ≥ 0 (positivité des variables) 1 2 1 4

Sous forme matricielle, la forme standard s’écrit

max F (x) = c⊤ x  x Ax = b x≥0 avec

 1700  32000    0    ∈ R6 , c=   0   0  

  x1 x2    e1  6  x= e2  ∈ R ,   e3  e4 

0  1.5 A =  2 3

3 4 3 0

1 0 0 0

0

0 1 0 0

0 0 1 0

 39 60 4  b= 57 ∈ R , 

57

 0 0  ∈ M4×6 (R). 0 1

2) Résolution graphique On détermine l’intersection des 4 demi-plans définis par les contraintes sous forme canonique pure.

4

20

droite de coef. directeur (−1, 1700/3200)

15 13

x* 10

5

0 −5

0

5

10

15

19 20

25

La solution optimale x∗ obtenue correspond à l’intersection {1.5x1 + 4x2 = 60} et  des droites  13.71 {2x1 + 3x2 = 60} (2ième et 3ième contraintes). Elle vaut x∗ = . 9.85

Exercice 2. Problème du restaurateur 1) Variables :

xr est le nombre de plateaux riches. xs est le nombre de plateaux simples.

Remarque : les variables xr et xs sont entières. Fonction objectif :

max(xr ,xs ) F (xr , xs ) = Pr xr + Ps xs  r n 1 xr + ns1 xs ≤ k1 (oursins) (1)      nr2 xr + ns2 xs ≤ k2 (palourdes) (2) nr3 xr + ns3 xs ≤ k3 (huitres) Contraintes : (3)    xr , xs ≥ 0   xr , xs entiers Il s’agit d’un P.L. en nombres entiers sous forme canonique pure. 2) Variables :

y1 est le prix (unitaire) d’un oursin. y2 est le prix (unitaire) d’une palourde. y3 est le prix (unitaire) d’une huître.

Fonction objectif : Contraintes :

min(y1 ,y2 ,y3 ) G(y1 , y2 , y3 ) = k1 y1 + k2 y2 + k3 y3  r r r (4)  n 1 y1 + n 2 y2 + n3 y3 ≥ Pr (plateau riche) s y + ns y + ns y ≥ P (plateau simple) (5) n1 1 s 3 3 2 2  y1 , y2 , y3 ≥ 0

Il s’agit d’un P.L. sous forme canonique pure.

5

Forme standard. On introduit les deux variables d’écarts e1 , e2 . Les contraintes s’écrivent alors  r n1 y1 + n2r y2 + nr y3 − e1 = Pr    s y + ns y + ns3 y − e = P n1 1 2 s 3 3 2 2 y , y , y ≥ 0  1 2 3   e1 , e2 ≥ 0

Remarque. Si on multiplie l’équation (4) par xr , l’équation (5) par xs et qu’on fait la somme, on obtient (nr1 xr + ns1 xs )y1 + (nr2 xr + n2s xs )y2 + (nr3 xr + n3s xs )y3 ≥ Pr xr + Ps xs et compte tenu de (1), (2), (3), on obtient G(y1 , y2 , y3 ) = k1 y1 + k2 y2 + k3 y3 ≥ F (xr , xs ) = Pr xr + Ps xs . Autrement dit, ce que le restaurateur reçoit de son amie est toujours supérieur (ou égal) aux bénéfices qu’il ferait s’il vendait tous ses plateaux dans son restaurant. Il a donc intérêt à vendre sa marchandise à son amie. Le deuxième problème est le dual du premier. Si on oublie la contrainte d’intégrité sur les variables xr , xs dans le premier problème, alors on peut montrer qu’à l’optimum, on a G(y∗1 , y∗2 , y3∗) = F (xr∗, x∗s ). Mais avec la contrainte d’intégrité, en général on n’a pas égalité : G(y∗1 , y∗2 , y∗3 ) > F (xr∗, x∗s ).

Exercice 3. Repartition de tâches 1) On introduit la variable binaire  1 si la tâche i est effectuée par le processeur j , xij = 0 sinon Le programme linéaire s’écrit : min

m n X X

cij xij

i=1 j=1 m X

   ∀i, xij = 1 j=1   ∀i, ∀j, xij ∈ {0, 1}

(1) (2)

Variante du problème qui consiste à minimiser le plus grand coût d’exécution : min max

(xij ) 1≤j≤m

Remarque 1 : Les contraintes (1) et (2) précédentes sont équivalentes à  m X    xij = 1 (3) ∀i,  

n X

cij xij

i=1

j=1

 ∀i, ∀j, xij ≥ 0     ∀i, ∀j, xij entiers

(4)

(5)

Les contraintes (3) et (4) impliquent xij ∈ [0, 1], ∀i, ∀j et on conclut avec (5) que xij ∈ {0, 1}. Remarque 2 : On peut aussi s’affranchir de l’intégrité des variables. Les contraintes (3),(4),(5) précédentes sont encore équivalentes à  m X    ∀i, xij = 1 (6)     j=1 n X  xij ≤ n (7) ∀j,    i=1

∀i, ∀j, xij ≥ 0

  

6

(8)

On peut montrer que la matrice A associée à (6), (7) est unimodulaire et donc que la solution optimale (si elle existe) est nécessairement entière (cf. TD ?). 2) L’objectif devient min

m n X X

cij xij +

i=1 j=1

Les contraintes sont inchangées.

X

d il xij (1 − xlj )

l>i

!

Remarque : On a   0 si les tâches i et l sont effectuées sur le même processeur j   (dans ce cas, il n’y a pas de coût supplémentaire) xij (1 − xlj ) = 1 si la tâche i est effectuée par le processeur j mais pas la tâche l    (dans ce cas, le coût supplémentaire vaut d il )

Exercice 4. Stockage On introduit les variables binaires  1 yj = 0  1 xij = 0

si le disque j est utilisé, sinon. si le fichier i est stocké sur le disque j , sinon

Remarque importante : Les variables (yj ) et (xij ) sont liées : (1)

yj = 0 ⇒ (xij = 0, ∀i) i.e. si le disque j n’est pas utilisé (yj = 0) alors aucun fichier n’est stocké sur ce disque (xij = 0, ∀i). 1) Première formulation min

(P L1)

m X

yj

j=1 n X

    ci xij ≤ C, ∀j = 1, · · · , m     i=1  m   X   xij = 1, ∀i = 1, · · · , n j=1     xij ≤ yj , ∀i = 1, · · · , n; ∀j = 1, · · · , m     yj ∈ {0, 1}, ∀j = 1, · · · , m     xij ∈ {0, 1}, ∀i = 1, · · · , n

(2) (3) (4)

Les contraintes (2) traduisent le fait qu’on ne peut pas dépasser la capacité C d’un disque. Les contraintes (3) indiquent que chaque fichier est stocké une et une seule fois sur un seul disque. Enfin les contraintes (4) permettent de faire le lien entre les variables xij et yj et assurent la relation (1). Remarque. En plus de la relation (1), on doit avoir la réciproque, à savoir (xij = 0, ∀i) ⇒ yj = 0

(5)

i.e. si aucun fichier n’est stocké sur le disque j (xij = 0, ∀i) alors celui-ci n’est pas utilisé (yj = 0). Cette contrainte est nécessairement respectée à l’optimum car si xij = 0, ∀i, alors il n’y a plus de contrainte sur yj (à part yj ∈ {0, 1}) et comme on cherche le minimum de la somme on a nécessairement y∗j = 0 à l’optimum. 7

1) Deuxième formulation On peut s’affranchir des contraintes (4) dans (PL1). On prend en compte les disques utilisés dans les contraintes (2) en ajoutant la variable yj dans le terme de droite. Le problème s’écrit min

(P L2)

m X

yj

j=1 n X

   ci xij ≤ Cyj , ∀j = 1, · · · , m     i=1   m X xij = 1, ∀i = 1, · · · , n   j=1     yj ∈ {0, 1}, ∀j = 1, · · · , m    xij ∈ {0, 1}, ∀i = 1, · · · , n

(6) (7)

La présence de yj dans (6) permet d’assurer la relation (1) à savoir que yj = 0 ⇒ (xij = 0, ∀i). Remarque. Le problème (P L1) comporte 2(m + n) contraintes (autres que l’appartenance des variables à {0, 1}), alors que (P L2) en comporte 2 fois moins (n + m).

Exercice 5. Affectation de bureaux 1) Il y a n! affectations différentes des n services aux n bureaux. Avec n = 30 et l’approximation 30! ≃ 1032 , on obtient un temps de calcul de l’ordre de 1015 années, ce qui est supérieur à l’âge de l’univers (14 milliards d’années)... 2) distance

djl

bureau

bureau

bureau

bureau

b1

bj

bl

bn

service

service

Si

Sk

...

...

cik Variables : xij =



1 si on place le service Si dans le bureau bj . 0 sinon   

n n n X n X X  X     Fonction objectif : min  F = cik  d jl xij xkl  i=1 k=i+1

j=1 l=1 l6=j

Contraintes :

 n X    ∀i, xij = 1 ← chaque service occupe un et un seul bureau.    j=1  n X  ∀j, xij = 1 ← chaque bureau est occupé par un et un seul service.     i=1   ∀i, ∀j, xij ∈ {0, 1}.

Il s’agit d’un problème de programmation quadratique

2) Modélisation par un P.L. On introduit la variable binaire xkl ij = xij xkl 8

La fonction objectif devient alors linéaire. Elle s’écrit   min  F =

n X

n X

n X n X

i=1 k=i+1 j=1 l=1 l6=j



 kl  cik d jl xij 

Les contraintes deviennent  X X kl  xij = 1 ← "chaque couple de service est situé dans un seul couple de bureaux"  ∀i, ∀k,    j l  XX kl ∀j, ∀l, = 1 ← "chaque couple de bureaux est affecté à un seul couple de services" xij     k i   ∀i, ∀j, ∀k, ∀l, xkl ij ∈ {0, 1}.

Exercice 6. Plan de vols d’une compagnie "charter" vol j

vol i AD i

AAi

HDi

HAi

Tij +p

AD j

AA j

HDj

HAj

1) Minimiser le nombre total d’avions est équivalent à maximiser le nombre de réemplois immédiats car nb. de vols = nb d’avions + nb de réemplois et le nombre de vols est fixé.  1 si l’avion du vol i est réemployé pour le vol j Variables : xij = 0 sinon 

Fonction objectif : max F =

XX i

j



xij

Contraintes : on tient compte des réemplois possibles ou non à travers la matrice des réemplois possibles dont les éléments sont définis par  1 si HAi + Tij + p ≤ HDj mij = 0 sinon

La valeur mij indique si un réemploi du vol i vers le vol j est possible ou non. La variable xij est liée à la valeur mij par la condition suivante : Si mij = 0 alors xij = 0. Les contraintes s’écrivent :  X  ∀i, xij ≤ 1 pour chaque vol i, au plus un seul réemploi possible de l’avion     j  X   xij ≤ 1 chaque vol j est assuré par le réemploi d’un seul avion au plus ∀j, i    ∀i, ∀j, xij ≤ mij réemploi possible ou non      ∀i, ∀j, x ∈ {0, 1} ij

2) Variables : les mêmes qu’en 1).   nv nv X X Tij xij  où nv est...