Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



Cours Programmation Linéaire 7 1 .pdf



Nom original: Cours Programmation Linéaire 7-1.pdf
Titre: Programmes linéaires duaux
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 1043 fois.
Taille du document: 279 Ko (32 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Programmes linéaires duaux







Définition et règles de construction du problème
dual
Propriétés
Théorème de la dualité faible et forte
Théorème des écarts complémentaires
Interprétation
© K. Jabeur 2008

1

1. Définition
• Un programme linéaire est sous forme normale si
– toutes les variables sont positives ou nulles ( 0) , et

• l’objectif est à maximiser et les contraintes générales
(autres que les restrictions de signe) sont toutes des
inégalités de type ,
ou
• l’objectif est à minimiser et les contraintes générales

(autres que les restrictions de signe) sont toutes des
inégalités de type .

© K. Jabeur 2008

2

Règles de construction du problème dual

© K. Jabeur 2008

3

Exemple 1

(P)
Max

Z  2 x1  x2  4 x3

S.l.c. x1  x2  3 x3  10
 x1  2 x2  5 x3  30
x1  0
x2  0
x3  0

© K. Jabeur 2008

4

Exemple 1

(D)

(P)
Max
S.l.c.

Z  2 x1  1x2  4 x3

Min

 1x1  1x2  3 x3  10

S.l.c.

 1x1  2 x2  5 x3  30

Z   10 y1  30 y2
y1  0
y2  0
 1 y1  1 y2  2

x1  0

 1 y1  2 y2  1

x2  0

 3 y1  5 y2  4

x3  0

© K. Jabeur 2008

5

Exemple 1

(D)

(P)
Max
S.l.c.

Z  2 x1  1x2  4 x3

Min

 1x1  1x2  3 x3  10

S.l.c.

 1x1  2 x2  5 x3  30

Z   10 y1  30 y2
y1  0
y2  0
 1 y1  1 y2  2

x1  0

 1 y1  2 y2  1

x2  0

 3 y1  5 y2  4

x3  0

© K. Jabeur 2008

6

Exemple 1

(D)

(P)
Max
S.l.c.

Z  2 x1  1x2  4 x3

Min

 1x1  1x2  3x3  10

S.l.c.

 1x1  2 x2  5 x3  30

Z   10 y1  30 y2
y1  0
y2  0
 1 y1  1 y2  2

x1  0

 1 y1  2 y2  1

x2  0

 3 y1  5 y2  4

x3  0

© K. Jabeur 2008

7

Exemple 1

(D)

(P)
Max

Z  2 x1  x2  4 x3

Min

S.l.c. x1  x2  3 x3  10

S.l.c.

Z   10 y1  30 y2
y1  0

 x1  2 x2  5 x3  30

y2  0

x1  0

y1  y2  2

x2  0

 y1  2 y2  1

x3  0

3 y1  5 y2  4

© K. Jabeur 2008

8

Exemple 2

(D)

(P)
Max

Z  2 x1  x2  4 x3

Min

S.l.c. x1  x2  3 x3  10

S.l.c.

Z   10 y1  30 y2
( y1 libre)

 x1  2 x2  5 x3  30

y2  0

x1  0

y1  y2  2

( x2 libre)

 y1  2 y2  1

x3  0

3 y1  5 y2  4

© K. Jabeur 2008

9

Exemple 3

(D)

(P)
Min

Z  2 x1  x2  4 x3

Max

S.l.c. x1  x2  3x3  10

S.l.c.

Z   10 y1  30 y2  7 y3
( y1 libre)

 x1  2 x2  5 x3  30

y2  0

3 x1  x2  x3  7

y3  0

x1  0

y1  y2  3 y3  2

( x2 libre)

 y1  2 y2  y3  1

x3  0

3 y1  5 y2  y3  4

© K. Jabeur 2008

10

Exemple 4

(D)

(P)
Max

Z  x1  x2  2 x3

S.l.c. 3 x1  x2  x3  5

Min
S.l.c.

Z   5 y1  10 y2  2 y3
( y1 libre)

x1  x2  2 x3  10

y2  0

2 x1  x2  4 x3  2

y3  0

x1  0

3 y1  y2  2 y3  1

( x2 libre)

 y1  y2  y3  1

x3  0

 y1  2 y2  4 y3  2

© K. Jabeur 2008

11

2. Propriétés
2.1 Relations entre le primal et son dual
Propriété 1:
(P) est le dual de (D) si et seulement si (D) est le dual de (P).
(« Le dual du dual de (P), c’est (P) ! »).

© K. Jabeur 2008

12

2. Propriétés (suite)
2.2 Relations entre la solution du primal et celle de son dual
Propriété 2: seuls les cas suivants sont possibles:

cas
intéressant

Primal

Dual

Pas de solution réalisable

Pas de solution réalisable

Solution sans borne

Pas de solution réalisable

Pas de solution réalisable

Solution sans borne

Une ou plusieurs solutions
optimales finies

Une ou plusieurs solutions
optimales finies

(plusieurs solutions optimales)

(solution optimale dégénérée)

© K. Jabeur 2008

13

3. Théorèmes de la dualité faible et forte
Théorème 1: Théorème de la dualité faible
Si x est une solution réalisable du primal et y est une solution
réalisable du dual alors:
cT x  bT y (primal à maximiser)
bT y  cT x (primal à minimiser)

Cela signifie que n'importe quelle solution réalisable pour le
problème primal définit une borne sur la valeur la fonction
objective du problème dual, et vice versa.

© K. Jabeur 2008

14

3. Exemple d’application du théorème de la dualité
faible
 Max x1  2 x2
 x  4 x  24
2
 1
( P)   x1  x2  1
x  4
 1
 x1 , x2  0
1.
2.
3.
4.

Trouver une solution réalisable de (P)
Formuler le dual (D) de (P)
Trouver une solution réalisable de (D)
Vérifier si les solutions réalisables de (P) et (D) respectent le théorème
de la dualité faible.

© K. Jabeur 2008

15

4. Théorèmes de la dualité faible et forte
Théorème 2: Théorème de la dualité forte
Si un des deux problèmes primal ou dual possède une solution
optimale finie, alors la même chose est vraie pour l’autre
problème, et les valeurs optimales des objectifs des deux
problèmes sont égales. Si un des deux problèmes n’est pas
borné, alors le domaine réalisable de l’autre problème est
vide.

© K. Jabeur 2008

16

Théorème des écarts complémentaires
Problème primal

Problème dual
Z *  Min Z   bT y
S.l.c.: AT y  c
y0

Z *  Max Z  cT x
S.l.c.: Ax  b
x0
Problème primal

Problème dual
Z *  Min Z   bT y
S.l.c.: AT y  r  c
y,r  0

Z *  Max Z  cT x
S.l.c.: Ax  s  b
x,s  0

© K. Jabeur 2008

17

Théorème des écarts complémentaires
Définition : Écarts complémentaires

Soient (x, s) une solution réalisable pour le problème primal et (y, r) une
solution réalisable pour le problème dual. Cette paire de solutions
satisfait les écarts complémentaires si :

rj  x j  0 j  1, ,n

si  yi  0 i  1, ,m

© K. Jabeur 2008

18

Théorème des écarts complémentaires
Théorème des écarts complémentaires
i.

Si (x, s) est une solution optimale de (P) et si (y, r) est une
solution optimale de (D), alors cette paire de solutions satisfait
les écarts complémentaires.

ii. Si (x, s) est une solution réalisable de (P), si (y, r) est une
solution réalisable de (D), et si cette a paire de solutions satisfait
les écarts complémentaires, alors
– (x, s) est une solution optimale de (P), et
– (y, r) est une solution optimale de (D).

© K. Jabeur 2008

19

4. Exemple d’application du théorème de la dualité
forte
 Max x1  2 x2
 x  4 x  24
2
 1
( P)   x1  x2  1
x  4
 1
 x1 , x2  0
1.
2.
3.

Résoudre le problème (P) en utilisant l’algorithme du simplexe
Formuler le dual (D) de (P)
Sans résoudre le problème dual, trouver sa solution optimale en
utilisant le théorème des écarts complémentaires.

© K. Jabeur 2008

20

5. Interprétation du problème dual et de sa solution :
Exemple de PizzaVite
Le restaurant Pizzavite sert 2 types de pizza pour le dîner. Les informations
relatives aux deux pizzas sont présentées dans le tableau suivant :
Pizza
Végétarienne
Prix de vente
28 $
Coût des ingrédients (par pizza)
7$
Coût de la main d'oeuvre (par
6$
pizza)
Temps d'emballage
2 minute
Temps de cuisson
1 minutes
Temps de préparation
3 minutes

Italienne
25 $
9$
7$
1 minute
1 minute
2 minutes

On a 100 minutes d'emballage, 80 minutes de cuisson et 200 minutes de
préparation disponibles. Formuler un PL qui aidera Pizzavite à maximiser son
profit?

© K. Jabeur 2008

21

3. Interprétation du problème dual et de sa solution
Exemple: « Pizzavite »
Max Z =

15 x1

+

9 x2

S.l.c. :

2 x1

+

1 x2



100

1 x1

+

1 x2



80

3 x1

+

2 x2



200



0



0

x1
x2
© K. Jabeur 2008

22

Activités

Max Z =
$

S.l.c. :

15 x1

+

2 x1

+

$
pv pv

me pv
pv

1 x1

9 x2

$
pi pi

1 x2
me pi
pi

+

mc pv
pv

3 x1

Ressources
disponibles

1 x2
mc pi
pi

+

mp pv
pv

2 x2



me



Ressources utilisées
par une unité
de l’activité 1

x2

80
mc



mp pi
pi

x1

100

200
mp



0



0

23
© K. Jabeur 2008

On a 3 ressources:
 b1 = 100 minutes d’emballage
 b2 = 80 minutes de cuisson
 b3 = 200 minutes de préparation
Chaque variable duale yi est associée à une contrainte du problème primal.

Chaque variable duale yi représente un prix unitaire associé à la ième ressource
(= le côté droit de la ième contrainte).

24
© K. Jabeur 2008

Ressources
disponibles
Max Z =
$

S.l.c. :

15 x1

+

$ pv
pv

2 x1

+

1 x2



me pi
pi

+

mc pv
pv

3 x1

9 x2
$ pi
pi

me pv
pv

1 x1

Prix

1 x2



mc pi
pi

+

mp pv
pv

2 x2



mp pi
pi

x1

Ressources utilisées
par une unité
de l’activité 1

x2




100

y1

me

$/me

80

y2

mc

$/mc

200

y3

mp

$/mp

0
0

25
© K. Jabeur 2008

Pizzavite: problème dual

Min Z = 100 y1 + 80 y2 + 200 y3
$

$
me me

S.l.c. :

$
mc mc

mp

$

mp

y1
y2
y3
2 y1 + 1 y2 +
me $
pv me

1

mc $
pv mc

y1 + 1 y2 +

me $
pi me

mc $
pi mc

3
mp
pv

2
mp
pi



0




0
0

y3  15
$
mp

$
pv

y3 

9

$

$
pi

mp

Valeur (en $) des ressources utilisées pour faire 1 unité de l’activité j
≥ profit sur l’activité j

26
© K. Jabeur 2008

Prix implicites
Définition:

Prix implicites = solution optimale du problème dual.

27
© K. Jabeur 2008

Rapport Tora : Exemple Pizzavite

28
© K. Jabeur 2008

Pizzavite: Réinterprétation du primal
Primal:
Z  15 x1  9 x2

s1  100  (2 x1  1x2 )

Max

s2  80  (1x1  1x2 )

S.l.c.: 2 x1  1x2  s1  100
1x1  1x2  s2  80

s3  200  (3x1  2 x2 )

3 x1  2 x2  s3  200
x1 , x2 , s1 , s2 , s3  0

quantités quantités
disponibles utilisées
si  quantité inutilisée (surplus, excédent)
de la ressource i

© K. Jabeur 2008

29

Pizzavite: Réinterprétation du dual
r1  (2 y1  1y2  3 y3 )  15
r2  (1y1  1y2  2 y3 )  9

rj = coût réduit de l’activité j
valeur des ressources profit unitaire
utilisées pour une
de l’activité
unité de l’activité
Min

Dual
Z   100 y1  80 y2  200 y3

S.l.c.: 2 y1  1 y2  3 y3  r1  15
1 y1  1 y2  2 y3  r2  9
y1 , y2 , y3 , r1 , r2  0
© K. Jabeur 2008

30

Évaluation d’une nouvelle activité
• Pizzavite envisage l’introduction d’une nouvelle variété de pizza,
la « Post-moderne », dont le profit unitaire serait 13 $, et qui
consommerait 1,5 minutes d’emballage , 2 minutes de cuisson et
3 minutes de préparation par unité. La demande serait illimitée.
Faut-il produire de cette nouvelle pizza ?
• Coût réduit =
(valeur des ressources consommées – profit) / unité
 1.5 y1  2 y2  13  2$
Chaque unité ferait perdre 2$ à Pizzavite. La variété « Postmoderne » n’est pas rentable comparativement aux autres.

© K. Jabeur 2008

31

Révision 1
Soit le programme linéaire:

 Min
S.l.c.:
P 



Z  2 x1  x2  3x3
x1  2 x2  x3  10
7 x1  8x2  4
x2 ,x3  0

1. Écrire un programme linéaire dual.

2. Dans le problème (P), x1 est en mètres (m), x2 en litres (l.), x3 en kilogrammes
(kg); l’objectif Z en hectares (ha), le premier côté droit (10) en secondes (s), le
deuxième côté droit (-4) en Watts (w). Indiquez dans quelles unités sont
mesurées les variables, l’objectif et les côtés droits dans votre problème dual.

© K. Jabeur 2008

32


Documents similaires


cours programmation lineaire 7 1
analyse et optimisation convexe professeur benzine rachid
dossier spadaro
vdc
ro licence
cours programmation lineaire 4 1


Sur le même sujet..