Recherche opérationnelle et applications

0 1 0 0

0 0 1 0



  

0 0 0 1

, b =



  



  

24 6 2 1

Variables pouvant prendre des valeurs négatives

Exemple 5 (Vente de hamburgers). – Un fast-food vend des hamburgers et des cheeseburgers. Un hamburger utilise 125 g. de viande alors qu’un

cheeseburger n’en utilise que 100 g.

– Le fast-food démarre chaque journée avec 10 kg de viande mais peut commander de la viande supplémentaire

avec un coût additionnel de 2 EUR par kg pour la livraison.

– Le profit est de 0.02 EUR pour un hamburger et 0.015 EUR pour un cheeseburger. – La demande ne dépasse pas 900 sandwiches / jour, et les surplus de viande sont donnés au Restos du Coeur.

Combien le fast-food doit-il produire de sandwiches de chaque type par jour ?

Variables x1 = nombre de hamburgers / jour x2 = nombre de cheeseburgers / jour

Contraintes – Commande de viande supplémentaire :

– Le coût pour la viande supplémentaire apparaît seulement si x3 < 0.

125x1 + 100x2 + x3 = 10000,

x3non restreint

9

– Substitution de x3 par 2 variables non-négatives :

x3 = x+

3 − x−

125x1 + 100x2 + x+

3 , x+

3 , x− 3 − x−

3 ≥ 0 3 = 10000

– Borne supérieure sur les ventes : x1 + x2 ≤ 900.

Modèle complet

max z = 0.02x1 + 0.015x2 − 0.002x− 3 3 − x− 3

125x1 + 100x2 + x+

s.c.

x1 + x2 x1, x2, x+

3 , x− 3

= 10000

≤ 900

≥ 0

Remarque : Il existe une solution optimale telle que x+

3 = 0 ou x−

3 = 0.

3.4 Résolution de programmes linéaires

3.4.1 Résolution graphique

Représentation graphique

Production de peinture

sous les contraintes :

max z = 5x1 + 4x2

6x1 + 4x2 ≤ 24 x1 + 2x2 ≤ 6 x2 ≤ 2 x2 − x1 ≤ 1 x1 ≥ 0 x2 ≥ 0

10

(1)

(2)

(3)

(4)

(5)

(6)

(5)(1)(2)(6)(4)(3)Géométrie des solutions

Ensemble des solutions admissibles Polyèdre (ABCDEF)

Courbes de niveaux de l’objectif Ensemble de solutions ayant un profit (valeur de l’objectif) donné : intersection entre une droite et le polyèdre.

Amélioration de la solution Recherche d’une direction dans laquelle le profit z augmente.

Résolution graphique (Production de peinture)

Recherche de la solution optimale – La droite mobile doit garder une intersection avec l’ensemble des solutions admissibles. – Solution optimale : x1 = 3, x2 = 1.5 (E) – La solution optimale est un sommet du polyèdre. – Cette observation est la base de l’algorithme du simplexe.

11

ABCDEFz=10ABCDEFz=21Résolution graphique (Diet problem)

Diet problem

sous les contraintes

Solution optimale

min z = 0.0015x1 + 0.0045x2

x1 + x2 ≥ 400

0.21x1 − 0.30x2 ≤ 0 0.03x1 − 0.01x2 ≥ 0 x1 ≥ 0 x2 ≥ 0

x1 =

4000 17

(cid:39) 235.3 x2 =

2800 17

(cid:39) 164.7

z =

186 170

(cid:39) 1.094

3.4.2 La méthode du simplexe

Idées de base – Solution optimale : sommet (point extrême). – Idée fondamentale du simplexe : déplacement de sommet en sommet adjacent de manière à améliorer la fonction

objectif.

– Transformation des inégalités en égalités : forme standard du programme linéaire - système de m équations à

n inconnues (m < n).

– Identification algébrique des sommets : correspondance avec les bases d’un système d’équations.

Solutions de base – Système de m équations linéaires à n inconnues (m < n) : infinité de solutions. – Si on fixe à zéro n − m variables : système de m équations à m inconnues possédant une solution unique (si la

matrice est inversible). C’est une solution de base.

Définition 7 (Solution de base). Une solution de base d’un programme linéaire est la solution unique du système de m équations à m inconnues obtenu en fixant à zéro n − m variables (pourvu que la matrice du système soit inversible). Les variables fixées à zéro sont appelées variables hors base et les autres variables en base.

12

Exemple 6 (Production de peinture). Prenons B = {s1, s2, s3, s4}.

z = 0 +5x1 +4x2 s1 = 24 −6x1 −4x2 s2 = 6 −x1 −2x2 s3 = 2 −x2 s4 = 1 +x1 −x2

Si x1 = x2 = 0, alors s1 = 24, s2 = 6, s3 = 2, s4 = 1. Toutes ces valeurs sont non-négatives et la solution est réalisable.

Définition 8 (Solution de base réalisable). Une solution de base telle que toutes les variables prennent des valeurs non-négatives est appelée solution de base réalisable.

Géométrie des solutions de base

– Prenons B = {s1, s2, s3, s4} ⇒ x1 = x2 = 0, s1 = 24, s2 = 6, s3 = 2, s4 = 1. – Cette solution de base réalisable correspond au sommet (0, 0).

Base {s1, s2, s3, s4} {x1, s2, s3, s4} {s1, x1, s3, s4} {x1, x2, s3, s4}

Solution Objectif

(0, 0) (4, 0) (6, 0) (3, 1.5)

0 20 − 21

Sommet A F Non réalisable E

Théorème 2. Toute solution de base réalisable correspond à un sommet du polyèdre.

Détermination de la solution de base optimale n! – Nombre maximum de solutions de base : m!(n−m)! – Algorithme "bête et méchant" : énumération de toutes les bases. – Méthode du simplexe : partir d’une solution de base admissible et passer à une solution de base voisine qui

améliore la valeur de l’objectif.

– Solution voisine : changement d’une variable en base. – 3 etapes :

1. Détermination de la variable entrante.

2. Détermination de la variable sortante.

3. Pivotage.

L’algorithme du simplexe

Variable entrante

z = 0 +5x1 +4x2 s1 = 24 −6x1 −4x2 s2 = 6 −x1 −2x2 s3 = 2 −x2 s4 = 1 +x1 −x2

– Si x1 (ou x2) augmente (entre en base), la valeur de la fonction objectif z augmente. – Quelle est la valeur maximale de x1 ?

13

ABCDEF– Contraintes : les autres variables doivent rester positives.

Variable sortante

s1 = 24 −6x1 ≥ 0 → x1 ≤ 4 s2 = 6 −x1 ≥ 0 → x1 ≤ 6 ≥ 0 → 2 ≥ 0 s3 = 2 s4 = 1 +x1 ≥ 0 → x1 ≥ −1

⇒ x1 ≤ 4

toujours! toujours!

Pivotage – Si x1 = 4, alors s1 = 0. – x1 entre en base, s1 sort de la base. – Substitution :

– Nouveau système :

x1 = 4 −

1 6

s1 −

2 3

x2

z = 20 − 5 x1 = 4 − 1 s2 = 2 + 1 s3 = 2 s4 = 5 − 1

6 s1 + 2 6 s1 − 2 6 s1 − 4

3 x2 3 x2 3 x2 −x2 3 x2

6 s1 − 5

Equations du simplexe – B = indices des variables en base, N = indices des variables hors base. – Notation :

z = z +

xl = bl −

(cid:88)

k∈N (cid:88)

k∈N

ckxk

alkxk

l ∈ B

– ck : profit marginal ou coût réduit.

Règles de pivotage

Variable entrante Choisir la variable k hors base avec le profit marginal maximum (max z) ou le coût réduit minimum (min z).

max z → k = arg max i∈N min z → k = arg min i∈N

ci

ci

Si ck ≤ 0 (max) ou ck ≥ 0 (min) pour tout k ∈ N , solution optimale, STOP.

Variable sortante Choisir la variable l en base telle que

z = 0 +5x1 +4x2 s1 = 24 −6x1 −4x2 s2 = 6 −x1 −2x2 s3 = 2 −x2 s4 = 1 +x1 −x2

l = arg min

j∈B:ajk>0

bj ajk

Si alk ≤ 0 pour tout l ∈ B, problème non borné, STOP.

14

z = 0 +5x1 +4x2 s1 = 24 −6x1 −4x2 s2 = 6 −x1 −2x2 −x2 s3 = 2 s4 = 1 +x1 −x2

aij

(cid:48) =

(cid:48)

bi

=

 



 



alj alk aij −

bl alk

bi −

i = l

i (cid:54)= l

aikalj alk

i = l

i (cid:54)= l

aikbl alk

z = 20 − 5 x1 = 4 − 1

s2 = 2 + 1

s3 = 2 s4 = 5 − 1

6 s1 + 2 3 x2 6 s1 − 2 3 x2 4 3 −x2 6 s1 − 5 3 x2

6 s1 −

x2

Pivotage

z = 0 +5x1 +4x2 s1 = 24 −6x1 −4x2 s2 = 6 −x1 −2x2 s3 = 2 −x2 s4 = 1 +x1 −x2

z = 21 − 3 x1 = 3 − 1 2 + 1 x2 = 3 2 − 1 s3 = 1 2 − 3 s4 = 5

4 s1 − 1 4 s1 + 1 8 s1 − 3 8 s1 + 3 8 s1 + 5

2 s2 2 s2 4 s2 4 s2 4 s2

15

Présentation en tableau Présentation compacte pour effectuer les calculs sans répéter les systèmes d’équations.

Itération 1

Itération 2

Itération 3

s2 0 0 1 0 0

s2 0 0 1 0 0

s3 0 0 0 1 0

s3 0 0 0 1 0

s4 Solution 0 0 0 0 1

0 24 6 2 1

s4 Solution 0 0 0 0 1

−20 4 2 2 5

Var. en base z s1 s2 s3 s4

x1 z 5 −1 6 0 1 0 0 0 0 −1

x2 4 4 2 1 1

s1 0 1 0 0 0

x1 x2 2 0 1 0 0 0

2 3 4

s1 3 − 5

6

1 6

3 − 1 6 0 1 1 5 6 3

Var. en base z x1 s2 s3 s4

z −1 0 0 0 0

Var. en base z x1 x2 s3 s4

z −1 0 0 0 0

2

x1 x2 0 1 0 0 0

s1 s2 0 − 3 4 − 1 4 − 1 1 0 1 − 1 8 1 0 0

8 − 3 8 − 5

3 4

4

2

4

3

s3 0 0 0 1 0

s4 Solution 0 0 0 0 1

−21 3 3 2 1 2 5 2

3.4.3 La méthode des deux phases

Solution initiale artificielle – Une solution de base admissible n’est pas toujours connue a priori. – Certains problèmes n’admettent pas de solution admissible, donc il est impossible de trouver une base de départ. – La méthode des deux phases va permettre de déterminer une base admissible ou prouver que le problème est

impossible.

Exemple 7 (Méthode des 2 phases).

min z = 4x1 +x2 3x1 +x2 = 3 s.c. 4x1 +3x2 ≥ 6 x1 +2x2 ≤ 4 x1,

≥ 0

x2

Introduction des variables d’écart

min z = 4x1 +x2 3x1 +x2 s.c. 4x1 +3x2 −x3 x1 +2x2 x2, x1,

x3,

= 3 = 6 +x4 = 4 x4 ≥ 0

16

– Pas de base admissible "triviale". – On voudrait voir apparaître une matrice identité. – Introduction de variables artificielles.

+x2

Introduction des variables artificielles min z = 4x1 min r = min r = −7x1 −4x2 +x3 3x1 +x2 s.c. 4x1 +3x2 −x3 +2x2 x1 x2, x1,

R1 +R2

+R1

+R2

x3, R1, R2,

+9

= 3 = 6 +x4 = 4 x4 ≥ 0

– R1, R2 et x4 peuvent être utilisées comme base de départ admissible. – Base pour le système de départ si R1 = R2 = 0 (hors base). – Réécrire l’objectif en fonction des variables hors base !

3.4.4 Cas particuliers

Solutions optimales multiples – Si la fonction objectif est parallèle à une contrainte active pour la solution optimale, la même valeur de l’objectif

peut être prise par plusieurs solutions admissibles.

– Il y a une infinité de solutions optimales dans ce cas (toutes les combinaisons convexes de sommets optimaux). – Cela se traduit par un profit marginal nul pour une ou plusieurs variables hors base.

Exemple 8 (Solutions optimales multiples).

max z = 2x1 +4x2 s.c.

x1 +2x2 ≤ 5 ≤ 4 x1 +x2 ≥ 0 x2 x1,

Var. en base

z

x1 x2

s1

s2

Solution

z s1 s2

z x2 s2

z x2 x1

−1

0 0

−1

0 0

−1

0 0

2

1 1

0 1 2 1 2

0

0 1

4

2 1

0

1 0

0 −2 1 1 2 0 − 1 2

0 −2

0

0 1

0

0 1

0

1 0 −1

1 −1 2

0

5 4

−10 5 2 3 2

−10

1 3

Solution optimale :

x1 = 0α + 3(1 − α) = 3 − 3α 3 2

2 α + 1(1 − α) = 1 +

x2 = 5

α (0 ≤ α ≤ 1)

Problèmes non bornés – Certains problèmes sont non bornés dans une direction donnée. – Si cette direction est une direction d’amélioration de la fonction objectif, celle-ci peut prendre une valeur arbi-

trairement grande !

17

Exemple 9 (Problèmes non bornés).

max z = 2x1 +x2 s.c.

x1 −x2 ≤ 1 ≤ 4 2x1 x1,

x2 ≥ 0

Var. en base

z

z s1 s2

−1

0 0

x1

2

x2

1

1 −1 0 2

s1

s2

Solution

0

1 0

0

0 1

0

1 4

– Tous les coefficients (sauf le profit maginal) dans la colonne de x2 sont négatifs ou nuls. – Cela signifie que toutes les contraintes de non-négativité sont satisfaites quelle que soit la valeur de x2. – L’objectif peut donc augmenter indéfiniment.

Problèmes impossibles – Le système de contraintes peut n’avoir aucune solution. – Généralement, provient d’une mauvaise formulation du problème.

Exemple 10 (Problèmes impossibles).

max z = 3x1 +2x2 2x1 +x2 ≤ 2 s.c. 3x1 +4x2 ≥ 12 x1,

≥ 0

x2

18

4 Dualité

4.1 Le problème dual

Problème primal et problème dual

Problème primal

max

cT x

s.c. Ax = b x ≥ 0

n variables, m contraintes, m < n, c, x ∈ Rn,

b ∈ Rm, A ∈ Rm×n.

Problème dual

min

s.c.

bT y AT y ≥ c (y non restreint)

m variables, n contraintes, m < n, c ∈ Rn, Exemple 11 (Problème primal et dual - forme standard).

b, y ∈ Rm, A ∈ Rm×n.

Problème primal :

Problème dual :

max z = x1 +x2 s.c.

2x1 +x2 = 5 3x1 −x2 = 6 x2 ≥ 0 x1,

(y1) (y2)

min w = 5y1 +6y2

s.c

2y1 +3y2 ≥ 1 y1 −y2 ≥ 1

(x1) (x2)

Propriétés et règles de construction du dual

Théorème 3. Le problème dual du problème dual est le problème primal.

Règles de construction

Problème max Contrainte ≤ = Variable ≥ 0 non restreinte

Problème min Variable ≥ 0 non restreinte Contrainte ≥ =

Exemple 12 (Problème primal et dual - forme générale).

Problème primal :

max z = 5x1 +12x2 +4x3 s.c.

x1 +2x2 +x3 ≤ 10 2x1 −x2 +3x3 = 8 ≥ 0 x1,

x2,

x3

(y1) (y2)

19

Problème dual :

min w = 10y1 +8y2

s.c

y1 +2y2 ≥ 5 2y1 −y2 ≥ 12 y1 +3y2 ≥ 4 ≥ 0 y1

(x1) (x2) (x3)

4.2 Relations primal/dual

Théorème 4 (Dualité faible). Considérons la paire primale-duale :

max

cT x

s.c. Ax = b x ≥ 0

bT y

min s.c. AT y ≥ c

– Si x est une solution admissible du primal et y une solution admissible du dual, alors

cT x ≤ bT y

– S’il y a égalité, alors x est une solution optimale du primal et y une solution optimale du dual.

Théorème 5 (Dualité forte). Considérons la paire primale-duale :

max

cT x

s.c. Ax = b x ≥ 0

bT y

min s.c. AT y ≥ c

– Si le primal et le dual admettent tous les deux une solution admissible, ils ont tous deux une solution optimale

finie et la même valeur objectif optimale.

– Si le primal (dual) est non borné, le dual (primal) n’admet pas de solution admissible.

Théorème 6 (Complémentarité). Considérons la paire primale-duale :

max

cT x

s.c. Ax = b x ≥ 0

bT y

min s.c. AT y ≥ c

20

Si x est une solution optimale du primal et y une solution optimale du dual, alors

où ai est la i-ème colonne de A. En d’autres termes :

xi(aT

i y − ci) = 0.

xi > 0 ⇒ aT aT i y > ci ⇒ xi = 0.

i y = ci,

Exemple 13 (Résolution du dual par les règles de complémentarité). Primal (P ) :

max z = 5x1 +12x2 +4x3 s.c.

x1 +2x2 +x3 ≤ 10 2x1 −x2 +3x3 = 8 ≥ 0 x1,

x2,

x3

(y1) (y2)

Dual (D) :

Solution optimale de (P ) :

min w = 10y1 +8y2

s.c

y1 +2y2 ≥ 5 2y1 −y2 ≥ 12 y1 +3y2 ≥ 4 ≥ 0 y1

(x1) (x2) (x3)

(x1, x2, x3) =

z =

(cid:19)

,

12 5

, 0

(cid:18) 26 5 274 5

x1 > 0 ⇒ y1 + 2y2 = 5 x2 > 0 ⇒ 2y1 − y2 = 12

Solution optimale de (D) :

(y1, y2) =

, −

(cid:19)

2 5

(cid:18) 29 5 274 5

w =

4.3

Interprétation économique de la dualité

– La forme canonique d’un programme linéaire peut être interprétée comme un problème d’allocation de res-

sources.

– Paire primale-duale :

max

cT x

s.c. Ax ≤ b x ≥ 0

bT y

min s.c. AT y ≥ c

y ≥ 0

21

– Données :

cj : profit par unité d’activité j. bi : disponibilité de la ressource i. aij : consommation de la ressource i par unité d’activité j.

– Variables :

xj : niveau de l’activité j. yi : valeur d’une unité de la ressource i.

Interprétation de la dualité faible

z ≤ w :

profit ≤ valeur des ressources

Interprétation de la dualité forte Le profit maximal est atteint si les ressources ont été exploitées complètement, i.e. jusqu’à épuisement de leur valeur.

Exemple 14 (Dualité dans le problème de production de peinture).

max z = 5x1 +4x2

s.c

6x1 +4x2 ≤ 24 x1 +2x2 ≤ 6 ≤ 2 x2 −x1 +x2 ≤ 1 ≥ 0 x2 x1,

min w = 24y1 +6y2 +2y3 +y4

6y1 +y2 −y4 ≥ 5 4y1 +2y2 +y3 +y4 ≥ 4 y4 ≥ 0 y3, y1,

y2,

x1 = 3, x2 = 1.5, z = 21 y1 = 0.75, y2 = 0.5, y3 = y4 = 0, w = 21

– Le profit augmente de 0.75 par augmentation d’une tonne de M1 et de 0.5 par tonne de M2. (Localement. Dans

quelles limites ? Voir analyse de sensibilité)

– Les "ressources" 3 et 4 sont abondantes, augmenter ces ressources n’apporte aucun profit supplémentaire.

22

5 Solveurs et langages de modélisation

Exemple 15 (Production de jouets). – Une société de jouets produit des trains, des camions et des voitures, en utilisant 3 machines. – Les disponibilités quotidiennes des 3 machines sont 430, 460 et 420 minutes, et les profits par train, camion et

voiture sont respectivement EUR 3, EUR 2 et EUR 5.

– Les temps nécessaires sur chaque machine sont :

Machine 1 2 3

Train Camion Voiture 2 0 4

1 3 1

1 2 0

Primal

max z = 3x1 +2x2 +5x3

s.c.

x1 3x1 x1 x1,

+2x2 +x3 ≤ 430 +2x3 ≤ 460 ≤ 420 ≥ 0

+4x2 x2,

x3

Dual

x1 = 0 x2 = 100 x3 = 230 z = 1350

min w = 430y1 +460y2 +420y3

s.c.

y1 2y1 y1 y1,

+3y2

+2y2 y2,

+y3 ≥ 3 +4y3 ≥ 2 ≥ 5 ≥ 0

y3

y1 = 1 y2 = 2 y3 = 0

Var. en base z x2 x3 s3

x1 z −1 −4 0 − 1 4 3 0 2 2 0

x2 x3 0 1 0 0

s2 s1 0 −1 −2 2 − 1 1 0 0 1 0 −2

1 2 1

4

s3 Solution 0 −1350 0 0 1

100 230 20

Base : B = {x2, x3, s3}.

Solveurs Logiciels pour résoudre des programmes linéaires : – Indépendants :

– Commerciaux : CPLEX (www.ilog.com), XPRESS-MP (www.dash.co.uk), . . . – Gratuits : PCx, lpsolve, glpk, . . .

– Tableurs : La plupart des tableurs intègrent un outil de résolution de programmes linéaires (Excel, Gnumeric,

. . .)

– Langages de modélisation (ampl, GNU MathProg, mpl, OPL studio, mosel, . . .) : langages de haut niveau

permettant la séparation modèle/données, se chargeant de l’interface avec un solveur.

23

NAME ROWS L L L N

R0001 R0002 R0003 R0004

COLUMNS

C0001 C0001 C0001 C0001 C0002 C0002 C0002 C0003 C0003 C0003

RHS

B B B

ENDATA

toys

R0001 R0002 R0003 R0004 R0001 R0003 R0004 R0001 R0002 R0004

R0001 R0002 R0003

1 3 1 3 2 4 2 1 2 5

430 460 420

FIGURE 1 – Exemple de production de jouets au format MPS

Solveurs indépendants

Avantages – Puissance, efficacité – Intégrables dans des applications via des librairies

Désavantages – Formats de fichiers (MPS) – Pas de séparation modèle / données – Ré-utilisation difficile des modèles

Solveurs intégrés aux tableurs

Avantages – Disponibles sur (quasi) tous les ordinateurs – Interface facile d’utilisation – Présentation des données / résultats

Désavantages – Difficulté d’implémenter de grands modèles – Séparation modèle / données difficile – Solveurs moins efficaces (en général)

Langages de modélisation

Avantages – Séparation modèle / données – Ré-utilisabilité des modèles – Indépendance modèle / solveur

24

# Data definition #

set Toys; param nMachines; set Machines := 1..nMachines;

param profit {Toys}; param time {Machines,Toys}; param avail {Machines};

# Variables #

var prod {Toys} >= 0;

# Objective #

maximize total_profit: sum{t in Toys} profit[t]*prod[t];

# Constraints #

subject to machine_usage {m in Machines}: sum{t in Toys} time[m,t] * prod[t] <= avail[m];

FIGURE 2 – Exemple de production de jouets au format AMPL (modèle)

Désavantages – Apprentissage du langage – Prix des versions commerciales – Limitation en taille des versions d’essai gratuites – Moindre efficacité (actuellement) des solveurs gratuits

25

# Data #

data;

set Toys := Trains, Trucks, Cars ; param nMachines := 3;

param profit := Trains Trucks Cars

3 2 5 ;

param time : Trains Trucks Cars := 1 1 2 1 2 3 0 2 3 1 4 0 ;

430

param avail := 1 2 460 3 420 ;

end;

FIGURE 3 – Exemple de production de jouets au format AMPL (données)

26

Troisième partie Programmation en nombres entiers et optimisation combinatoire

6 Définitions et exemples

Programmation en nombres entiers – Programmes linéaires dans lesquels certaines (ou toutes les) variables sont restreintes à des valeurs entières. – Si seulement une partie des variables doivent être entières, on parle de programme mixte (MILP). – Optimisation combinatoire : choix d’une solution optimale parmi un ensemble fini d’alternatives. Peuvent gé-

néralement se formuler comme des programmes en nombres entiers.

– Problèmes très difficiles en pratique, mais solveurs de plus en plus performants.

Exemple 16 (Sélection de projets). 5 projets doivent être évalués sur 3 ans. Etant donné le coût de chaque projet pour chaque année et le profit obtenu par l’éxécution d’un projet, décider quels projets éxécuter sans dépasser le budget disponible pour chaque année.

Projet 1 2 3 4 5 Budget

Coût par année 2 1 1 5 7 4 9 3 4 7 6 8 25 25

3 8 10 2 1 10 25

Profit

20 40 20 15 30

xj =

(cid:26) 1 0

si le projet j est sélectionné, sinon.

max z = 20x1 +40x2 +20x3 +15x4 +30x5

s.c.

5x1 +4x2 +3x3 +7x4 +8x5 ≤ 25 +7x2 +9x3 +4x4 +6x5 ≤ 25 x1 +x4 +10x5 ≤ 25 8x1 +10x2 +2x3 x5 x4, x3, x2, x1,

∈ {0, 1}

Variables

Formulation

Exemple 17 (Problème avec coûts fixes). – 3 compagnies de téléphone offrent des tarifs différents pour les communications longue distance. Compagnie Abonnement

1 2 3 – Trouver le plan d’abonnement optimal pour 200 minutes de communication / mois.

16 25 18

Prix / minute 0.25 0.21 0.22

Variables

Formulation

xi : minutes de communication avec la compagnie i. (cid:26) 1 0

si un abonnement est pris auprès de la compagnie i, sinon.

yi =

27

min z = 0.25x1 +0.21x2 +0.22x3 +16y1 + 25y2 + 18y3

s.c.

x1 x1

x1, y1,

+x2

+x3

x2

x2, y2,

x3 x3 y3

= 200 ≤ 200y1 ≤ 200y2 ≤ 200y3 ≥ 0 ∈ {0, 1}

Exemple 18 (Voyageur de commerce). – Un représentant doit visiter n villes une et une seule fois, et revenir à sa ville de départ, en minimisant le coût

total du trajet.

– Le problème revient à trouver un tour de coût minimum passant une et une seule fois par chacun des noeuds

d’un graphe. Le coût d’utilisation de l’arc (i, j) est cij .

Variables

Contraintes

xij =

 



1

0

si l’arc (i, j) appartient au tour optimal, sinon.

n (cid:88)

j=1 n (cid:88)

i=1

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

Problème : apparition possible de sous-tours

(cid:88)

i,j∈S

xij ≤ |S| − 1,

∅ (cid:54)= S (cid:54)= {1, . . . , n}.

Formulation

min z =

n (cid:88)

n (cid:88)

cijxij

s.c.

j=1

i=1 n (cid:88)

j=1 n (cid:88)

i=1

xij = 1

i = 1, . . . , n

xij = 1

j = 1, . . . , n

(cid:88)

i,j∈S

xij ≤ |S| − 1

∅ (cid:54)= S (cid:54)= {1, . . . , n}

xij ∈ {0, 1}

i = 1, . . . , n, j = 1, . . . , n

28

SExemple 19 (Problème de couverture). Le département de sécurité d’un campus veut installer des téléphones d’urgence. Chaque rue doit être servie par un téléphone, le but étant de minimiser le nombre de téléphones à installer (installation aux carrefours).

Formulation

min z = x1 +x2 +x3 +x4 +x5 +x6 +x7 +x8

s.c. x1 +x2

x2 +x3

x4 +x5

x6 +x7

≥ 1 ≥ 1 ≥ 1 ≥ 1 x7 +x8 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1 +x8 ≥ 1 x8

x7,

+x7

∈ {0, 1}

x1

x2 x2

+x4 x4

x3

x1,

x2,

x3,

x4,

+x6 +x6

+x5 x5 x5,

x6,

Contraintes disjonctives – Dans un programme linéaire, toutes les contraintes doivent être satisfaites simultanément. – Parfois, il est nécessaire de modéliser le fait qu’une contrainte parmi un ensemble doit être satisfaite. Si les

contraintes de l’ensemble sont mutuellement incompatibles, on parle de contraintes disjonctives.

Exemple 20 (Contraintes disjonctives). – Une machine est utilisée pour 3 tâches différentes. Pour chaque tâches i, une durée pi et une date limite di sont

données, ainsi qu’une pénalité par jour de retard.

Tâche Durée Limite 5 20 15

25 22 35

1 2 3

Pénalité 19 12 34

– Comment arranger les tâches sur la machine pour minimiser la pénalité totale ?

– Variables : xi : temps de fin de la tâche i (xi ≥ pi). – Deux tâches i et j ne peuvent être éxécutées simultanément, donc

xi ≥ xj + pi ou xj ≥ xi + pj.

– Pour introduire ces contraintes disjonctives, nous faisons appel à des variables binaires auxiliaires :

yij =

(cid:26) 1 0

si i précède j si j précède i

29

12345876xi − xj + M yij ≥ pi xj − xi + M (1 − yij) ≥ pj

– Contrainte de date limite : introduction d’une variable d’écart non restreinte xi + si = di. – Une pénalité apparaît uniquement si si < 0. – Remplacement par deux variables non négatives représentant les parties positive et négative.

i − s− xi + s+ i , s− s+ i ≥ 0

i = di

Objectif : min z = 19s−

1 + 12s−

2 + 34s− 3

Formulation

min z = s.c.

x1 −x2 −x1 +x2 x1 −x1

−x3 +x3 x2 −x3 −x2 +x3

x1

x2

x3 x1, x2, x3, x1

x2

x3

+12s− 2

+34s− 3

19s− 1 +M y12 −M y12

+M y13 −M y13

≥ 5 ≥ 20 − M ≥ 5 ≥ 15 − M

+M y23 ≥ 20 −M y23 ≥ 15 − M

+s+

1 − s− 1

+s+

2 − s− 2

1 , s− s+ 1 ,

2 , s− s+ 2 ,

3 − s− +s+ 3 , s− s+

= 25 = 22 3 = 35 3 ≥ 0 ≥ 5 ≥ 20 ≥ 15 ∈ {0, 1}

y12,

y13,

y23

7 Complexité des problèmes et efficacité des algorithmes

Problèmes faciles et difficiles – La théorie de la complexité s’attache à classifier les problèmes selon leur difficulté. – Un problème est facile s’il existe un algorithme efficace pour le résoudre. – Exemples de problèmes “faciles” : programmation linéaire, affectation, plus courts chemins, . . . – Un problème est difficile s’il appartient à la classe des problèmes NP-complets, pour lesquels il est peu probable

de trouver un jour un algorithme efficace.

– Exemple de problèmes “difficiles” : programmes en nombres entiers, voyageur de commerce, . . .

Algorithmes efficaces et explosion combinatoire – L’efficacité d’un algorithme est mesurée par l’ordre de grandeur du nombre d’opérations élémentaires qu’il

effectue en fonction de la taille des données.

– Un algorithme sera efficace si le nombre d’opérations élémentaires est polynomial (i.e. borné supérieurement

par un polynôme) en la taille de problème.

n 1 2 3 5 10 20 50 100

ln n + 1 1.000 1.301 1.477 1.699 2.000 2.3