Cours Programmation Linéaire 3 1 .pdf



Nom original: Cours Programmation Linéaire 3-1.pdf
Titre: Problèmes de réseaux
Auteur: FSA

Ce document au format PDF 1.5 a été généré par Microsoft® Office PowerPoint® 2007, et a été envoyé sur fichier-pdf.fr le 03/02/2013 à 15:07, depuis l'adresse IP 197.15.x.x. La présente page de téléchargement du fichier a été vue 1572 fois.
Taille du document: 338 Ko (31 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


Chapitre 2

Résolution graphique d’un programme
linéaire





Représentation d’éléments
Représentation d’un programme linéaire
Exemples
Propriétés des programmes linéaires

© Khaled Jabeur 2012

Cours Programmation Linéaire

1

Représentation graphique d’un programme linéaire
• On peut représenter un programme linéaire graphiquement s’il a
deux variables (ou moins…), par exemple x1, x2.
• Dans ce cas, chaque décision (choix de valeurs pour x1, x2) peut
être représentée par un point ou un vecteur dans le plan cartésien

x2

x2

x 
x  1
 x2 

x1
© Khaled Jabeur 2012

x1
2

Graphe d’une fonction de 2 variables
• Soit f(x1, x2) une fonction de 2 variables x1, x2. Son graphe peut
être vu comme une surface dans un espace à 3 dimensions:
f ( x1 , x2 )

15

x2
B
C
0
A

x1

3

Un contour ou une courbe de niveau du graphe est un ensemble de
points x1, x2 sur lesquels la fonction garde une valeur constante.

f ( x1 , x2 )

15

x2
B
C

0
A

x1

4

Un contour ou une courbe de niveau du graphe est un ensemble de
points x1, x2 sur lesquels la fonction garde une valeur constante.

f ( x1 , x2 )

15

x2
B

Courbe de niveau
C

0
A

x1

5

Le gradient d’une fonction f (x) en un point xº est le vecteur formé par
les dérivées partielles de f en ce point:

 f  x
 x1
f  x   

 f  x
 xn









Si la fonction f (x) est affine, son gradient est constant (il est indépendant
du point xº) :
 a1 
f  x   a1x1  a2 x2   an xn  b  f  x    
a 
 n
Exemple :

f  x1,x2   5x1  7x2  3

5

 f  x1 ,x2    
 7 
© Khaled Jabeur 2012

5
−7

gradient
6

Le gradient de f en un point indique dans quelle direction la fonction
s’accroît le plus vite. Il est toujours perpendiculaire au contour en ce point.

f ( x1 , x2 )

15

x2
B

Courbe de niveau
C

0
A

gradient de f au point C

x1
© Khaled Jabeur 2012

7

Fonction affine de 2 variables: son graphe est un plan.

f ( x1 , x2 )  a1 x1  a2 x2  b

Morceau
du graphe
15

x2

b
B

0
A

x1

8

Ses courbes de niveau sont des droites parallèles entre elles

f ( x1 , x2 )  a1 x1  a2 x2  b

16

15

x2

b
B

Courbe de niveau
C

0
A

x1

9

Son gradient est constant (et perpendiculaire aux courbes de niveau)

f ( x1 , x2 )  a1 x1  a2 x2  b

15

x2
a 
gradient de f au point B   1 
 a2 

b
B
C

0
A

a 
gradient de f au point C   a1 
 2
x1

10

Soit c une constante. L’ensemble des points (x1,x2) tels que f(x1,x2)  c
est un demi-plan.

f ( x1 , x2 )  a1 x1  a2 x2  b

15

x2

b
B
C

0
A

x1

11

L’ensemble des points (x1,x2) tels que f(x1,x2)  c est un demi-plan.

f ( x1 , x2 )  a1 x1  a2 x2  b

15

x2

b
B
C

0
A

x1

12

Égalités et inégalités linéaires
f ( x1 , x2 )  a1 x1  a2 x2
c une constante donnée
x2

f ( x1 , x2 )  c

f ( x1 , x2 )  c

f ( x1 , x2 )  c

a1
a2

x1

© Khaled Jabeur 2012

13

Programme linéaire: exemple 1
Max Z  x1  x2
S.l.c.: x1  2 x2  6
x1  4
x2  2
x1  0
x2  0

1.
2.
3.
4.

Dessiner les contraintes
Identifier le domaine réalisable
Examiner les valeurs de l’objectif dans le domaine réalisable
Trouver toutes les solutions optimales

© Khaled Jabeur 2012

14

Contrainte: x1+2x2  6
Frontière: x1+2x2 = 6 Droite: trouver 2 points
0
6
x1  0  x2  3  P   
x2  0  x1  6  Q   
 3
0
x2

P

x1  2 x2  6

2
1

0

Q
© P. Lang H2006

x1
15

Contrainte: x1+2x2  6
Inégalité: demi-plan

Zone interdite:

x2

x1  2 x2  6

x1

0
© P. Lang H2006

16

Autres contraintes
x1  4

x2  2

x1  0

x2  0

x1  4

x2  2

x1  0

x2  0

x2

x1

0
© P. Lang H2006

17

Domaine réalisable
Points A, B, C, D, E situés aux « coins » du domaine réalisable
= points extrêmes.

x2

B

C
Domaine
réalisable

A

D
E

0
© P. Lang H2006

x1
18

Valeurs possibles de la fonction objectif
•Si on fixe l’objectif à une valeur k, on obtient une courbe de niveau = droite.
•Si la droite contient des points réalisables, la valeur k peut être atteinte par
l’objectif.

x2

C réalisables tels que Z = 3
Points
B

A
0

Points réalisables tels que Z = 1
D

x1  x2  1

x1  x2 x1 E x2
© P.3Lang H2006
4

Décision optimale
x1  4
x2  1
Z 5

x1  x2  5

x1
19

Si on change l’objectif…
…on change l’orientation des courbes de niveau et du gradient.

x2

C

Décision optimale

B

D
A
0

E
© P. Lang H2006

x1
20

Si on change l’objectif…
…on change l’orientation des courbes de niveau et du gradient.

x2

Décision optimale

C
B

D
A
0

E
© P. Lang H2006

x1
21

Cas particulier
L’objectif est: Max Z  x1  2 x2

x2

C

Décisions optimales multiples

B

D
A
0

E
© P. Lang H2006

x1
22

Exemple 2
Max Z  x1  x2
S.l.c.: 2 x1  x2  1
x1  2 x2  1
x1  0
x2  0

© Khaled Jabeur 2012

23

2 x1  x2  1

x1  2 x2  1

x1  0

© Khaled Jabeur 2012

x2  0

24

Max Z  x1  x2

Solution sans borne

© Khaled Jabeur 2012

25

Exemple 3
Max Z  x1  x2
S.l.c.:  x1  2 x2  2
2 x1  x2  2
x1  x2  2

© Khaled Jabeur 2012

26

Exemple 3
Max Z  x1  x2
S.l.c.:  x1  2 x2  2
2 x1  x2  2
x1  x2  2

© Khaled Jabeur 2012

27

Exemple 3
Max Z  x1  x2
S.l.c.:  x1  2 x2  2
2 x1  x2  2
x1  x2  2

Aucune décision
n’est réalisable.
Le domaine réalisable
est vide.

© Khaled Jabeur 2012

28

Programmes linéaires: cas possibles de solution
(« Solution » = décision)

1. Pas de solution
réalisable

2. Solution(s)
sans borne

3. Une ou plusieurs
solution(s) optimales finies

3.a Une
Le problème n’est
pas réalisable.

3.b Plusieurs

Le problème est réalisable.

© Khaled Jabeur 2012

29

Propriétés fondamentales
Propriété 1 (solutions optimales)
S’il existe une (ou plusieurs) solutions optimales finies (cas 3),
et si le domaine réalisable a (au moins) un point extrême,
alors il existe (au moins) un point extrême qui est optimal.
Propriété 2 (existence de points extrêmes)
Si le domaine réalisable est borné et non vide, alors il a au moins un point
extrême.

© Khaled Jabeur 2012

30

Conséquence: si le domaine réalisable est borné et non vide, pour trouver
une solution optimale, il suffit d’inspecter tous les points extrêmes.
Exemple 1:

Point extreme
A
B
C
D
E

Coordonnées ( x1 , x2 )
(0,0)
(0, 2)
(2, 2)
(4,1)
(4,0)

Z  x1  x2
0
2
4
5 Solution optimale unique
4

© Khaled Jabeur 2012

31



Documents similaires


cours programmation lineaire 3 1
cours programmation lineaire 1 1
maths
cours programmation lineaire 2 1
gradient conjugue cas quadratique et non quadratique
professeur benzine rachid optimisation sans contraintes tome1


Sur le même sujet..