Chap 0 [PDF]

Zitiervorschau

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Introduction Zakia ANKHILI Université Cadi Ayyad ENSA, Marrakech

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

1/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Introduction En partant de situations concrètes, nous construirons des modèles mathématiques représentant les propriétés fondamentales des systèmes considérés. La modélisation mathématique consiste en trois étapes : 1 Identification des variables de décisions. Ce sont les paramètres sur lesquels l’agent de décision peut agir pour faire évoluer le système considéré. 2 Détermination de l’objectif visé exprimé sous forme d’une fonction mathématique (appelée fonction objectif). 3 Description des contraintes définissant la nature du système à étudier.

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

2/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Le problème d’optimisation consiste alors à déterminer les variables de décision conduisant aux meilleures conditions de fonctionnement du système (ce qui revient à minimiser ou maximiser la fonction objectif), tout en respectant les contraintes d’utilisation définies à l’étape 3. Exemple 1 (Problème de transport) Une entreprise dispose de deux entrepôts (A1 , A2 ) pour des articles destinés à satisfaire la demande de trois clients (B1 , B2 , B3 ). Le nombre d’article disponible à chaque entrepôt et la demande des clients sont spécifiés dans le tableau ci-dessous qui contient également le coût du transport d’un article de chaque usine à chaque client. Le problème est de déterminer quelle quantité chaque client reçoit de chaque entrepôt pour minimiser le coût total tout en satisfaisant les contraintes. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

3/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Le problème d’optimisation consiste alors à déterminer les variables de décision conduisant aux meilleures conditions de fonctionnement du système (ce qui revient à minimiser ou maximiser la fonction objectif), tout en respectant les contraintes d’utilisation définies à l’étape 3. Exemple 1 (Problème de transport) Une entreprise dispose de deux entrepôts (A1 , A2 ) pour des articles destinés à satisfaire la demande de trois clients (B1 , B2 , B3 ). Le nombre d’article disponible à chaque entrepôt et la demande des clients sont spécifiés dans le tableau ci-dessous qui contient également le coût du transport d’un article de chaque usine à chaque client. Le problème est de déterminer quelle quantité chaque client reçoit de chaque entrepôt pour minimiser le coût total tout en satisfaisant les contraintes. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

3/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

A1 A2 demande

B1 1 6 200

B2 4 8 400

B3 9 4 100

Disponibilité 200 500

Posons xij le nombre d’articles que Ai envoie à Bj (i = 1, 2, j = 1, 2, 3) Fonction objectif : min x11 +4x12 +9x13 +6x21 +8x22 +4x23 Les contraintes : x11 + x12 + x13 ≤ 200 x21 + x22 + x23 ≤ 500 x11 + x21 = 200 x12 + x22 = 400 x13 + x23 = 100 xij ≥ 0, ∀i, j Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

4/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

A1 A2 demande

B1 1 6 200

B2 4 8 400

B3 9 4 100

Disponibilité 200 500

Posons xij le nombre d’articles que Ai envoie à Bj (i = 1, 2, j = 1, 2, 3) Fonction objectif : min x11 +4x12 +9x13 +6x21 +8x22 +4x23 Les contraintes : x11 + x12 + x13 ≤ 200 x21 + x22 + x23 ≤ 500 x11 + x21 = 200 x12 + x22 = 400 x13 + x23 = 100 xij ≥ 0, ∀i, j Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

4/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Considérons le problème d’entreposer une commodité pour vente futur. Le problème s’échelonne sur 3 périodes successives. A chaque période nous pouvons acheter et/ou vendre et le prix de vente est égale au prix unitaire d’achat tel que spécifié dans le tableau ci dessous. De plus, le coût d’entreposage est de 1 Euro par unité et la capacité de l’entrepôt est de 6O unités. Période (t) 1 2 3

Zakia ANKHILI

Chapitre 1

Prix unitaire 4 9 6

Cours d’optimisation

ENSA (Marrakech) 2015/2016

5/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Le problème consiste à déterminer les quantités à acheter, entreposer et vendre pour maximiser les profits au cours des 3 périodes. On suppose que 30 unités sont disponibles au départ. Les variables : xi quantité achetée à la période i yi quantité vendue à la période i Fonction objectif −4x1 + 4y1 − 1(30 + x1 − y1 ) −9x2 + 9y2 − 1(30 + x1 − y1 + x2 − y2 ) −6x3 + 6y3 − 1(30 + x1 − y1 + x2 − y2 + x3 − y3 ) = −7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 90

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

6/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Exemple 2 (Problème d’entreposage) Les contraintes : 30 + x1 − y1 ≤ 60 30 + x1 − y1 + x2 − y2 ≤ 60 30 + x1 − y1 + x2 − y2 + x3 − y3 ≤ 60 xi , yi ≥ 0, (i = 1, 2, 3) Le problème s’écrit alors,         

max sà

−7x1 + 7y1 − 11x2 + 11y2 − 7x3 + 7y3 − 9

30+x1 −y1 ≤60

30+x1 −y1 +x2 −y2 ≤60      30+x 1 −y1 +x2 −y2 +x3 −y3 ≤60    xi , yi ≥0, (i=1,2,3)

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

7/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Définition Soient f : IRn → IR, gi : IRn → IR , i = 1, ..., m, hj : IRn → IR j = 1, ..., p des fonctions. Un problème d’optimisation ou problème de programmation mathématique (P ) consiste à minimiser ou maximiser la fonction f sous les contraintes : gi (x) ≤ 0,

i = 1, ..., m.

hj (x) = 0,

j = 1, ..., p.

Le problème s’écrit :    

min f (x) s.à (P ) gi (x) ≤ 0, i = 1, ..., m.    h (x) = 0, j = 1, ..., p. j Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

8/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

D’une façon équivalente, le problème (P ) s’écrit : (

(P )

min f (x) s.à x∈D

où D = {x ∈ IRn / gi (x) ≤ 0, i = 1, ..., m., hj (x) = 0, j = 1, ..., p}

La fonction f est appelée fonction objectif. L’ensemble D est appelé ensemble admissible ou ensemble réalisable. On peut remplacer min par max selon la nature du problème considéré. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

9/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

D’une façon équivalente, le problème (P ) s’écrit : (

(P )

min f (x) s.à x∈D

où D = {x ∈ IRn / gi (x) ≤ 0, i = 1, ..., m., hj (x) = 0, j = 1, ..., p}

La fonction f est appelée fonction objectif. L’ensemble D est appelé ensemble admissible ou ensemble réalisable. On peut remplacer min par max selon la nature du problème considéré. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

9/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

D’une façon équivalente, le problème (P ) s’écrit : (

(P )

min f (x) s.à x∈D

où D = {x ∈ IRn / gi (x) ≤ 0, i = 1, ..., m., hj (x) = 0, j = 1, ..., p}

La fonction f est appelée fonction objectif. L’ensemble D est appelé ensemble admissible ou ensemble réalisable. On peut remplacer min par max selon la nature du problème considéré. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

9/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

D’une façon équivalente, le problème (P ) s’écrit : (

(P )

min f (x) s.à x∈D

où D = {x ∈ IRn / gi (x) ≤ 0, i = 1, ..., m., hj (x) = 0, j = 1, ..., p}

La fonction f est appelée fonction objectif. L’ensemble D est appelé ensemble admissible ou ensemble réalisable. On peut remplacer min par max selon la nature du problème considéré. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

9/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

D’une façon équivalente, le problème (P ) s’écrit : (

(P )

min f (x) s.à x∈D

où D = {x ∈ IRn / gi (x) ≤ 0, i = 1, ..., m., hj (x) = 0, j = 1, ..., p}

La fonction f est appelée fonction objectif. L’ensemble D est appelé ensemble admissible ou ensemble réalisable. On peut remplacer min par max selon la nature du problème considéré. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

9/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Classification des problèmes d’optimisation 1

Suivant les propriétés de la fonction objectif : fonction fonction fonction fonction fonction

2

linéaire quadratique convexe non linéaire continûment dérivable. non linéaire non dérivable.

Suivant les propriétés des contraintes : pas de contraintes. simple bornes. fonction linéaire. fonction convexe. fonctions non linéaires continûment dérivables. fonctions non linéaires non dérivables.

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

10/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Classification des problèmes d’optimisation 1

Suivant les propriétés de la fonction objectif : fonction fonction fonction fonction fonction

2

linéaire quadratique convexe non linéaire continûment dérivable. non linéaire non dérivable.

Suivant les propriétés des contraintes : pas de contraintes. simple bornes. fonction linéaire. fonction convexe. fonctions non linéaires continûment dérivables. fonctions non linéaires non dérivables.

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

10/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Terminologie Optimisation linéaire :  

min cT x s.à  x ∈ D = {x/ Ax ≤ b} Optimisation quadratique : 1 T min x Dx − bT x 2 s.à  x ∈ D = {x/ Ax ≤ b}  

Optimisation convexe : f est une fonction convexe et D est un ensemble convexe. Optimisation non linéaire: f , gi et hj sont des fonctions non linéaires. Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

11/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

L’objectif de ce cours est de répondre aux questions suivantes: 1 Existe-t-il une solution du problème (P) ? si oui, a-t-on unicité ? 2 Comment la caractériser ? ( conditions d’optimalité). 3 Comment la calculer ? (algorithmes de calcul)

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

12/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

L’objectif de ce cours est de répondre aux questions suivantes: 1 Existe-t-il une solution du problème (P) ? si oui, a-t-on unicité ? 2 Comment la caractériser ? ( conditions d’optimalité). 3 Comment la calculer ? (algorithmes de calcul)

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

12/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

L’objectif de ce cours est de répondre aux questions suivantes: 1 Existe-t-il une solution du problème (P) ? si oui, a-t-on unicité ? 2 Comment la caractériser ? ( conditions d’optimalité). 3 Comment la calculer ? (algorithmes de calcul)

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

12/13

Rappels mathématiques Problèmes d’optimisation sans contraintes Problèmes d’optimisation avec contraintes Méthodes d’optimisa

Plan

1

Rappels mathématiques

2

Problèmes d’optimisation sans contraintes

3

Problèmes d’optimisation avec contraintes

4

Méthodes d’optimisation

Zakia ANKHILI

Chapitre 1

Cours d’optimisation

ENSA (Marrakech) 2015/2016

13/13