EPFL RECHERCHE OPERATIONNELLE

Institut de Mathematiques GC

M. Bierlaire ETE 2006

CORRIGE DE LA SERIE D’EXERCICES 1

Probleme 1

a) Soient les variables du probleme :

x1 : nombre de litres d’essence de bergamote produits en une semaine avectraitement des dechets,

x2 : nombre de litres d’essence de bergamote produits en une semaine sanstraitement des dechets.

On obtient le probleme suivant :

Maximiser z = −0.4 · 5x1 − 15(0.4 · 0.2x1 + 0.4x2) + 110(x1 + x2)− 20(x1 + x2)s.c. 0.4x1 ≤ 8000

0.4 · 0.2x1 + 0.4x2 ≤ 2800x1 , x2 ≥ 0

Apres simplification et mise sous forme d’un probleme de minimisation avec des contraintesd’inegalite inferieures et variables positives :

Minimiser z = −86.8x1 − 84x2

s.c. 0.4x1 − 8000 ≤ 00.08x1 + 0.4x2 − 2800 ≤ 0

x1 , x2 ≥ 0

b) Soient les variables du probleme :

x1 = nombre de bouteilles d’oeil-de-perdrix produitesx2 = nombre de bouteilles de pinot noir produites

On obtient le probleme suivant :

max z = x1(21−2·x1

100) + x2(23 −

x2

100)− 2 · x1 − 3,5 · x2 − 3 · (x1 + x2)

s.c.

x1 + x2 ≤ 1000x1 ≥ 0x2 ≥ 0

Mis sous forme d’un probleme de minimisation avec des contraintes d’egalite et variablespositives:

min z = x1

(

2·x1

100− 16

)

+ x2

(

x2

100− 16,5

)

s.c.

x1 + x2 − 1000 + x3 = 0x1 ≥ 0x2 ≥ 0x3 ≥ 0

1

www.almohandiss.com

c) Definissons les variables du probleme suivantes :

x1 : montant (en francs) investi en obligations ;

x2 : montant (en francs) alloue aux prets immobiliers ;

x3 : montant (en francs) alloue aux leasing ;

x4 : montant (en francs) alloue aux prets personnels.

Le rendement du portefeuille defini par x1,x2,x3,x4 est :

z = 0.06x1 + 0.10x2 + 0.08x3 + 0.13x4.

Les contraintes a satisfaire sont :

a) x4 ≤1

2x1

b) x2 ≤ x3

c) x4 ≤1

5(

4∑

i=1

xi)

d)

4∑

i=1

xi ≤ 1′000′000

Le programme lineaire que doit resoudre la banque est donc :

Maximiser z = 3

50x1 + 1

10x2 + 4

50x3 + 13

100x4

s.c. −1

2x1 + x4 ≤ 0

x2 − x3 ≤ 0−1

5x1 − 1

5x2 − 1

5x3 + 4

5x4 ≤ 0

x1 + x2 + x3 + x4 ≤ 1′000′000x1 , x2 , x3 , x4 ≥ 0

Mis sous la forme d’un probleme de minimisation avec des contraintes d’inegalite superieures,on obtient :

Minimiser z = − 3

50x1 − 1

10x2 − 4

50x3 − 13

100x4

s.c. 1

2x1 + −x4 ≥ 0

−x2 + x3 ≥ 01

5x1 + 1

5x2 + 1

5x3 − 4

5x4 ≥ 0

−x1 − x2 − x3 − x4 + 1′000′000 ≥ 0x1 , x2 , x3 , x4 ≥ 0

Probleme 2

a) y : R 7→ R : y(x) = 1− x2 est concave:

λy(x1) + (1− λ)y(x2) = 1− λx2

1− (1− λ)x2

2

y(λx1 + (1− λ)x2) = 1− λ2x21− (1− λ)2x2

2− 2λ(1− λ)x1x2

En soustrayant ces deux equations et en factorisant:

y(λx1 + (1− λ)x2)− λy(x1)− (1− λ)y(x2) = λ(1− λ)(x1 − x2)2 ≥ 0

Ce dont on deduit que y est concave.

2

www.almohandiss.com

b) y : R 7→ R : y(x) = x2 − 1 est convexe:

λy(x1) + (1− λ)y(x2) = λx21+ (1− λ)x2

2− 1

y(λx1 + (1− λ)x2) = λ2x2

1+ (1− λ)2x2

2+ 2λ(1 − λ)x1x2 − 1

En soustrayant ces deux equations et en factorisant:

y(λx1 + (1− λ)x2)− λy(x1)− (1− λ)y(x2) = −λ(1− λ)(x1 − x2)2 ≤ 0

Ce dont on deduit que y est convexe.

c) La fonction z : R2 7→ R : z(x,y) =

√

x2 + y2 est convexe. Il suffit de remarquer que z(x,y) = ‖(x,y)‖2

ou ‖ . ‖2 est la norme euclidienne sur R2. Donc, d’apres l’inegalite triangulaire et d’apres

l’homogeneite de la norme pour les scalaires positifs:

z(λ(x1,y1) + (1− λ)(x2,y2)) ≤ λz(x1,y1) + (1− λ)z(x2,y2)

24 mars 2006 – mbi/mt/mts

3

www.almohandiss.com