EPFL RECHERCHE OPERATIONNELLE

Institut de Mathematiques GC

M. Bierlaire ETE 2006

SERIE D’EXERCICES 1

Vous trouverez les enonces des series d’exercices, les notes de cours ainsi que bien d’autresinformations sur le cours sur votre site ouebe prefere :

http://roso.epfl.ch/cours/rogc

– Probleme-type :1-a), 2-a)

– Problemes a resoudre :1-b), 2-b)

– Problemes supplementaires :1-c), 2-c)

Probleme 1

a) Une distillerie produit de l’essence de bergamote pour les parfumeurs de la region. La fa-brication d’un litre d’essence de bergamote genere 0.4 litres de dechets polluants liquides.La distillerie peut soit faire traiter ces dechets par une station d’epuration avant de lesdeverser dans la riviere, soit les deverser directement dans la riviere. La station d’epurationtraite au plus 8000 litres de dechets par semaine. Le processus d’epuration n’est pas parfait :20% des dechets traites par la station d’epuration et deverses ensuite dans la riviere sontencore polluants. 5 frs sont factures a la distillerie pour chaque litre de dechets transitantpar la station d’epuration. L’Etat percoit une taxe de 15 frs par litre de dechets polluantsdeverse dans la riviere, qu’on ait tente de les traiter ou pas. La loi limite a 2800 le nombrede litres de dechets polluants pouvant etre deverses dans la riviere chaque semaine. Le prixde vente d’un litre d’essence de bergamote est de 110 frs et le cout des matieres premierespour cette essence est de 20 frs/litre.

La distillerie souhaite maximiser son profit hebdomadaire. En supposant que la distilleriereussit toujours a vendre tout ce qu’elle produit, enoncer ce probleme sous la forme d’unprobleme de minimisation avec des contraintes d’inegalite inferieures et variables positives.

b) Un encaveur peut acheter jusqu’a 1 tonne de pinot, un raisin rouge, a un vigneron en lepayant 3 CHF/kilo. Il pourra ensuite vinifier ces raisins de deux facons : soit a la maniered’un vin blanc afin d’obtenir de l’oeil-de-perdrix, un vin rose, soit a la maniere d’un vinrouge afin d’obtenir du pinot noir, un vin rouge corse. Pour vinifier de l’oeil-de-perdrix calui coute 2 CHF par kilo de raisin alors que pour vinifier du pinot noir ca lui coute 3,50CHF par kilo de raisin.

Par economie d’echelle, l’encaveur pourra vendre ses bouteilles d’oeil-de-perdrix au prixunitaire de 21 CHF moins 2 % du nombre de bouteilles de rose produites, de meme ilvendra les bouteilles de pinot noir au prix unitaire de 23 CHF moins 1 % du nombre debouteilles de rouge produites.

1

www.almohandiss.com

L’encaveur desire maximiser son gain. En sachant qu’avec un kilo de raisin on produit0,7 litre de vin et qu’une bouteille de vin contient 7 decilitres, enoncer ce probleme sousla forme d’un probleme de minimisation avec des contraintes d’egalite et variables positives.

c) Une banque veut determiner comment investir ses avoirs pour l’annee a venir. Actuelle-ment, la banque dispose d’un million de francs qu’elle peut investir dans des obligations,des prets immobiliers, des leasing ou des prets personnels. Les taux d’interet annuels desdifferents types d’investissement sont de 6 % pour les obligations, 10 % pour les pretsimmobiliers, 8 % pour les leasing et de 13 % pour les prets personnels.

Afin de limiter les risques, le portefeuille choisi par la banque doit satisfaire les restrictionssuivantes :

i) Le montant alloue aux prets personnels ne doit pas depasser la moitie de celui investien obligations.

ii) Le montant alloue aux prets immobiliers ne doit pas depasser celui alloue aux leasing.

iii) Au plus 20 % du montant total investi peut etre alloue aux prets personnels.

Sachant que la banque souhaite maximiser le rendement ( i.e. le taux d’interet annuel) deson portefeuille, formuler ce probleme sous la forme d’un probleme de minimisation avecdes contraintes d’inegalite superieures.

Probleme 2

Parmi les fonctions suivantes, lesquelles sont convexes? Lesquelles sont concaves? Justifier votrereponse.

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

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

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

√

x2 + y2

RAPPEL :

• Une fonction f : Rn 7→ R est convexe si et seulement si pour tout couple de points (x,y)

et pour tout λ ∈ [0,1], λf(x) + (1− λ)f(y) ≥ f(λx + (1− λ)y).

• Une fonction f : Rn 7→ R est concave si et seulement si pour tout couple de points (x,y)

et pour tout λ ∈ [0,1], λf(x) + (1− λ)f(y) ≤ f(λx + (1− λ)y).

• Une fonction affine, encore appelee lineaire, est a la fois convexe et concave.

23 mars 2006 – mbi/mt/mts

2

www.almohandiss.com