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 4 1 .pdf



Nom original: Cours Programmation Linéaire 4-1.pdf
Titre: Formulation d’un programme linéaire
Auteur: Khaled

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 1381 fois.
Taille du document: 516 Ko (68 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Formulation d’un programme linéaire

Introduction

© K. Jabeur 2012

1

La modélisation: un art
• Pour un problème donné, plusieurs formulations
équivalentes
• Pas de méthode universelle
• Apprentissage par: pratique et réflexion
• Procéder méthodiquement

© K. Jabeur 2012

2

Produit final
• Variables de décision
– noms arbitraires
– unités !

• Programme linéaire
– formes linéaire (objectif et coté gauche des contraintes)
– conventions d’écritures

© K. Jabeur 2012

3

Forme d’un programme linéaire
Variables de
décision:

Objectif:

Contraintes
générales

Restrictions
de signe

x1 , x2 ,

, xn

Maximiser
/ Minimiser:

Z  c1 x1  c2 x2 

Sous les
contraintes:

a11 x1  a12 x2 

 a1n xn  /  /  b1

a21 x1  a22 x2 

 a2 n xn  /  /  b2

am1 x1  am 2 x2 

 amn xn  /  /  bm

 cn xn

x1  0
xn  0
© K. Jabeur 2012

4

Conseils …
1. « Modèle verbal » = inventaire
– ce qu’on souhaite faire: objectif
– ce qu’on ne contrôle pas: données, contraintes
– ce qu’on contrôle

2. Variables de décision
– unités

3. Modèle mathématique
– cohérent …
– pas nécessairement linéaire au départ
– faire des hypothèses si nécessaire

4. Forme linéaire, simplifications
© K. Jabeur 2012

5

Exercice 1

© K. Jabeur 2012

6

Exercice 1
Maïs

Blé

Pois

Tomates

Fèves

Prix
($/tonne)

120

150

60

80

55

Rendement
(tonnes/hectare)

10

4

4

8

6

Main-d’œuvre
requise
(heures/hectare)

120

150

100

80

120

 250t

 80t

© K. Jabeur 2012

 200 hectares

 18000h

7

Éléments
• Objectif:
– Maximiser le revenu de la production
• (Hypothèse: ce qui sera produit sera vendu)

• Contraintes:
– Surface disponible
– Heures de main d’œuvre disponibles
– Production minimale de maïs
– Production minimale de blé

© K. Jabeur 2012

8

Décisions
• Sur quoi portent les décisions à prendre dans cette situation ?
– Que cultiver
– Combien de chaque type.

• En quelles unités les variables seront-elles exprimées ?
– Hectares
– Tonnes

© K. Jabeur 2012

9

Formulation 1
• Variables de décision
– xi = nombre d’hectares réservés à la production de la culture i
(1  i  5), où :
i = 1 : maïs
i = 2 : blé
i = 3 : pois
i = 4 : tomates
i = 5 : fèves

© K. Jabeur 2012

10

Programme linéaire
Objectif: Max: Revenu total ($) =
Revenu
Revenu
Revenu
Revenu
Revenu
tiré du + tiré du + tiré des + tiré des + tiré des
maïs
blé
pois
tomates
fèves
Prix de
Quantité

vente
produite



1200
$
hect mais

x1
hect
mais

$

600
$
hect blé

x2

240x3

hect
blé

$

Max Z  1200 x1  600 x2  240 x3  640 x4  330 x5
© K. Jabeur 2012

11

Contraintes:
1. Surface disponible:
Surface utilisée
(hectares)



200
(hectares)

Surface
Surface
Surface
Surface
Surface
= utilisée pour + utilisée pour + utilisée pour + utilisée pour + utilisée pour
le maïs
le blé
les pois
les tomates
les fèves

x1
(hectares)

x2
(hectares)



x1  x2  x3  x4  x5  200
© K. Jabeur 2012

12

2. Heures de main d’œuvre disponibles
Heures de main d’œuvre utilisées
18000

(hres)
(hres)

HMdo
HMdo
HMdo
HMdo
HMdo
= utilisées + utilisées + utilisées + utilisées + utilisées
maïs
blé
pois
tomates
fèves
Hres
# hect
utilisées 
utilisés
par hect

120
hres mdo
hect mais



x1
hect
mais

hres mdo

150 
hres mdo
hect blé

x2

100x3

hect
blé

hres mdo

120 x1  150 x2  100 x3  80 x4  120 x5  18000
13
© K. Jabeur 2012

3. Production minimale de maïs

x1  25
hect

hect

4. Production minimale de blé

x2  20
hect

hect

© K. Jabeur 2012

14

Programme linéaire 1 - récapitulation
Max

Z  1200 x1  600 x2  240 x3  640 x4  330 x5

S.l.c.

x1  x2  x3  x4  x5  200
120 x1  150 x2  100 x3  80 x4  120 x5  18000
x1  25
x2  20
x3 , x4 , x5  0

© K. Jabeur 2012

15

Programme linéaire 1 - récapitulation
Max

Z  1200 x1  600 x2  240 x3  640 x4  330 x5

S.l.c.

x1  x2  x3  x4  x5  200
120 x1  150 x2  100 x3  80 x4  120 x5  18000
x1  25
x2  20
x3 , x4 , x5  0

© K. Jabeur 2012

16

Programme linéaire 1 - récapitulation
direction de
l’objectif

côtés
relations
droits

coeffficients de l’objectif

Max Z  1200 x1  600 x2  240 x3  640 x4  330 x5
S.l.c.:

1x1

coeff
120 x1
contraintes
1x1
générales
0 x1

restrictions
de signes



1x2



1x3



1x4



1x5



200

 150 x2

 100 x3 

80 x4

 120 x5  18000



0 x2



0 x3



0 x4



0 x5



25



1x2



0 x3



0 x4



0 x5



20

x3  0
x4  0
x5  0

© K. Jabeur 2012

17

Remarque
• 250 tonnes de maïs seront utilisées pour l’élevage, donc pas vendues.
• Dans le revenu total, on a compté 120  250 = 30 000 D en trop.

• Le vrai revenu est: Z  1200 x1  600 x2  240 x3  640 x4  330 x5  30000
• Mais: ajouter ou retrancher une constante à l’objectif ne change pas la
solution optimale.
• On n’écrira jamais de constante dans l’objectif.
• On retranchera les 30 000 $ après avoir résolu le programme linéaire.

© K. Jabeur 2012

18

Exercice 1: Formulation 2
• Variables de décision
– xi = nombre de tonnes de la culture i à produire (1  i  5)
• Programme linéaire:

Max

hect/tonne
Tonnes

Z  120 x1  150 x2  60 x3  80 x4  55 x5

1
1
1
1
1
S.l.c.
x1  x2  x3  x4  x5  200 Hectares
10
4
4
8
6
12 x1  37.5 x2  25 x3  10 x4  20 x5  18000
x1  250
x2  80
x3 , x4 , x5  0

© K. Jabeur 2012

19

Formulation d’un programme linéaire

Problèmes de mélanges

© K. Jabeur 2012

20

Exercice 2

© K. Jabeur 2012

21

Exercice 2
Éléments

Composés

A

C1

B

C2

Autres

C

C3

C4

Nouveau produit
© K. Jabeur 2012

22

Exercice 2 : éléments
• Objectif
Min coût des intrants utilisés pour faire un kg du nouveau
produit ($ / kg de nouveau produit).

• Contraintes
– Proportion de A ( = 20%)
– Proportion de B (  30%)
– Proportion de C (  20%)
– Proportion du composé 1 (  30%)
– Proportion du Composé 2 (  40%)

• Variables de décision
xi = # de kgs du composé i entrant dans la composition de 1 kg
du nouveau produit (1  i  4)
© K. Jabeur 2012

23

Objectif:

Min Z  20 x1  30 x2  20 x3  15 x4
D
kg de Ci
D
4
Z   ii


kg de Ci kg de NP kg de NP

Proportion de A:

0,3x1  0,2 x2  0,4 x3  0,2 x4  0,2
kg de Ci
kg de A
4 kg de A
 i i kg de C  kg de NP  kg de NP
i

Proportion de B:

0,2 x1  0,6 x2  0,3x3  0,4 x4  0,3

Proportion de C:

0,4 x1  0,15 x2  0,25 x3  0,3x4  0,2

Proportion de C1:

x1  0,3

Proportion de C2:

x2  0, 4
© K. Jabeur 2012

24

Exercice 2 – Une formulation possible
• Variables de décision :
xi = nombre de kgs du composé i (1  i  4) utilisés pour
faire 1 kg du nouveau produit.
• Programme Linéaire :
Min

Z  20 x1  30 x2  20 x3  15 x4

S.l.c.: 0.3 x1  0.2 x2  0.4 x3  0.2 x4  0.2
0.2 x1  0.6 x2  0.3 x3  0.4 x4  0.3
0.4 x1  0.15 x2  0.25 x3  0.3 x4  0.2
x1  0.3
x2  0.4
x1  x2  x3  x4  1
xi  0 (1  i  4)
© K. Jabeur 2012

25

Exercice 2 – Une formulation possible
Variables de décision :
xi = nombre de kgs du composé i (1  i  4) utilisés pour faire 1 kg
du nouveau produit.
Programme Linéaire :
Min

Z  20 x1  30 x2  20 x3  15 x4

S.l.c.: 0.3 x1  0.2 x2  0.4 x3  0.2 x4  0.2
0.2 x1  0.6 x2  0.3 x3  0.4 x4  0.3
0.4 x1  0.15 x2  0.25 x3  0.3 x4  0.2
x1  0.3
x2  0.4
x1  x2  x3  x4  1
xi  0 (1  i  4)
© K. Jabeur 2012

26

Exercice 2 – Une formulation possible
Variables de décision :
xi = nombre de kgs du composé i (1  i  4) utilisés pour faire 1 kg
du nouveau produit.
Programme Linéaire :
Min

Z  20 x1  30 x2  20 x3  15 x4

S.l.c.: 0.3 x1  0.2 x2  0.4 x3  0.2 x4  0.2
0.2 x1  0.6 x2  0.3 x3  0.4 x4  0.3
0.4 x1  0.15 x2  0.25 x3  0.3 x4  0.2
x1  0.3
x2  0.4
x1  x2  x3  x4  1

contrainte logique

xi  0 (1  i  4)
© K. Jabeur 2012

27

Exercice 3

© K. Jabeur 2012

28

Exercice 3


Objectif




Contraintes







Max audience
budget 10 000 D
a) personnes à revenu moy-élevé = au moins 50% audience
b) atteindre au moins 100 000 « hommes 25+ »
# min et max d’unités d’information: radio et TV

Variables de décision
xi = # d’unité d’information achetées sur le média i
(i = 1 : journal ; i = 2 : radio ; i = 3 : TV).

© K. Jabeur 2012

29

•Audience atteinte:

10000 x1  3000 x2  75000 x3

•Contrainte de budget:

250 x1  100 x2  2500 x3  10000

•Au moins 50% des personnes atteintes seront à revenu moyen ou élevé:
# personnes a revenu moy.-élevé atteintes
 0,5
# total de personnes atteintes
7000 x1  1000 x2  50000 x3
 0,5
10000 x1  3000 x2  75000 x3

7000 x1  1000 x2  50000 x3  5000 x1  1500 x2  37500 x3
2000 x1  500 x2  12500 x3  0
•Atteindre  100 000 H25+:

5000 x1  500 x2  25000 x3  100000

•Bornes radio:

7  x2  100

•Bornes TV:

2  x3  20
© K. Jabeur 2012

30

Programme linéaire: récapitulation
Max

Z  10000 x1  3000 x2  75000 x3

S.l.c.: 250 x1  100 x2  2500 x3  10000
2000 x1  500 x2  12500 x3  0
5000 x1  500 x2  25000 x3  100000
x2  7
x2  100
x3  2
x3  20
x1  0

© K. Jabeur 2012

31

Exercice 4

© K. Jabeur 2012

32

Exercice 4
Objectif:
Contraintes:

Max profit total tiré du transport (D)
Type
Quantités
disponibles
Capacité
en poids
Capacité
en volume

Équilibrage

Visant
A
B
Av
C
Ar
Av
C
Ar
Av vs. Ar
C vs. Av
C vs. Ar
C vs. Total
© K. Jabeur 2012

Unités
Tonnes
Tonnes
Tonnes
Tonnes
Tonnes
m3
m3
m3
Tonnes
Tonnes
Tonnes
Tonnes
33

Exercice 4
• Décider quoi ?
Combien transporter
– De chaque produit
– Dans chaque compartiment
–  2  3 = 6 variables

• Unités:
Tonnes

• Variables de décision:
xij = # de tonnes du produit i (i = 1 : A; i = 2 : B) transportées
dans le compartiment j (j = 1 : avant; j = 2 : centre; j = 3 :
arrière).

© K. Jabeur 2012

34

Exercice 4
Objectif:

Max Z  8x11  8x12  8x13  7 x21  7 x22  7 x23

Quantités disponibles:
A:
B:

Quantité transportée  quantité disponible
x11  x12  x13  5000

Capacité en poids:
Av:
C:
Ar:

Poids transporté  capacité en poids
x11  x21  2000
x12  x22  3000
x13  x23  1700

Capacité en volume:
Av:
C:
Ar:

Volume transporté  capacité en volume
60 x11  50 x21  100000
60 x12  50 x22  160000
60 x13  50 x23  60000

x21  x22  x23  3000

© K. Jabeur 2012

35

Exercice 4
Équilibrage: Av vs. Ar.

Poids Av
 1,3
Poids Ar
x11  x21
 1,3
x13  x23

x11  x21  1,3x13  1,3x23
x11  x21  1,3x13  1,3x23  0

© K. Jabeur 2012

36

Exercice 4
Équilibrage: C vs. Av.

Poids C
 1,3
Poids Av

x12  x22
 1,3
x11  x21

x12  x22  1,3x11  1,3x21

1,3x11  1,3x21  x12  x22  0

Équilibrage: C vs. Ar.

Poids C
 1,3
Poids Ar

x12  x22
 1,3
x13  x23

x12  x22  1,3x13  1,3x23

1,3x13  1,3x23  x12  x22  0

© K. Jabeur 2012

37

Exercice 4
Équilibrage: C vs. Total

Poids C
 0,9
Poids total
x12  x22
 0,9
x11  x21  x12  x22  x13  x23

x12  x22  0,9 x11  0,9 x21  0,9 x12  0,9 x22  0,9 x13  0,9 x23
0,9 x11  0,9 x21  0,1x12  0,1x22  0,9 x13  0,9 x23  0
Non-négativité

xij  0 1  i  2, 1  j  3
© K. Jabeur 2012

38

Formulation d’un programme linéaire
Problème de minimax

© K. Jabeur 2012

39

Problème de « Minimax »
Quatre produits (A, B, C, D) peuvent être fabriqués sur 3 machines
(1, 2, 3). Le tableau ci-dessous indique le débit de production (en
unités de produit par heure) de chaque machine pour chaque produit
(exemple: la machine 1 produit 10 unités de A à l’heure).
Machine 1
Machine 2
Machine 3

A
10
12
20

B
5
10
8

C
4
8
7

D
8
10
15

Les 3 machines sont actuellement disponibles. Un client vient de
passer une commande urgente composée de 40 unités de A, 20
unités de B, 30 unités de C, 10 unités de D. La commande sera
expédiée par camion dès la production achevée.
Formuler un programme linéaire qui permette de répartir les
productions sur les machines de façon à livrer le plus tôt possible.
© K. Jabeur 2012

40

Exemple de solution
Répartition
des unités
sur les
machines:

M1
M2
M3
Total

A

B

C

D

8
12
20
40

5
10
5
20

0
16
14
30

4
6
0
10

M1

M2
M3

0

T1 = 2,3h

T3 = 3,6+h

T2 = 4,6h heures

T  Max T1 , T2 , T3   4,6h
© K. Jabeur 2012

41

xij  # d'unités du produit i affectées a la machine j (i  A,B,C,D - j  1,2,3)
T j  date (en heures) a laquelle la machine j est libérée

T  date (en heures) a laquelle la commande part
x

x

x

A1
A2
A3
Satisfaire
xB1  xB 2  xB 3
les
x x x
demandes: C1 C 2 C 3

xD1  xD 2  xD3

T1
T2
T3






40
20
30
10

xij  0 i  A,B,C,D , j  1,2,3

1
1
1
1

x A1  xB1  xC1  xD1
10
5
4
8
1
1
1
1

x A2  xB 2  xC 2  xD 2
12
10
8
10
1
1
1
1

x A3  xB 3  xC 3  xD 3
20
8
7
15

T  Max T1 , T2 , T3 

Minimiser T
© K. Jabeur 2012

42

Min

Z T

S.l.c.: T  Max T1 , T2 , T3 
T1
T2
T3

1
1
1
1

x A1  xB1  xC1  xD1
10
5
4
8
1
1
1
1

x A2  xB 2  xC 2  xD 2
12
10
8
10
1
1
1
1

x A3  xB 3  xC 3  xD 3
20
8
7
15

x A1  x A2  x A3
xB1  xB 2  xB 3
xC1  xC 2  xC 3
xD1  xD 2  xD3






40
20
30
10

xij  0 i  A,B,C,D , j  1,2,3

© K. Jabeur 2012

43

Difficulté: la fonction Max n’est pas linéaire
Exemple: T  Max T1 , T2 

T  T2

T

T  T1

T2

Contour (T  cte)

T1
© K. Jabeur 2012

44

Min

Z T

S.l.c.: T  Max T1 , T2 , T3 
T1
T2
T3

1
1
1
1

x A1  xB1  xC1  xD1
10
5
4
8
1
1
1
1

x A2  xB 2  xC 2  xD 2
12
10
8
10
1
1
1
1

x A3  xB 3  xC 3  xD 3
20
8
7
15

x A1  x A2  x A3
xB1  xB 2  xB 3
xC1  xC 2  xC 3
xD1  xD 2  xD3






40
20
30
10

xij  0 i  A,B,C,D , j  1,2,3

© K. Jabeur 2012

45

Min

Z T

S.l.c.:

T  T1
T  T2
T  T3
T1
T2
T3

1
1
1
1
x A1  xB1  xC1  xD1
10
5
4
8
1
1
1
1

x A2  xB 2  xC 2  xD 2
12
10
8
10
1
1
1
1

x A3  xB 3  xC 3  xD 3
20
8
7
15


x A1  x A2  x A3
xB1  xB 2  xB 3
xC1  xC 2  xC 3
xD1  xD 2  xD3






40
20
30
10

xij  0 i  A,B,C,D , j  1,2,3
© K. Jabeur 2012

46

Min

Z T

S.l.c.: T
T
T

1
1
1
1
x A1  xB1  xC1  xD1
10
5
4
8
1
1
1
1

x A2  xB 2  xC 2  xD 2
12
10
8
10
1
1
1
1

x A3  xB 3  xC 3  xD 3
20
8
7
15


x A1  x A2  x A3
xB1  xB 2  xB 3
xC1  xC 2  xC 3
xD1  xD 2  xD3






40
20
30
10

xij  0 i  A,B,C,D , j  1,2,3

© K. Jabeur 2012

47

Min

Z T

S.l.c.:

1
1
1
1
x A1  xB1  xC1  xD1  T
10
5
4
8
1
1
1
1
x A2  xB 2  xC 2  xD 2  T
12
10
8
10
1
1
1
1
x A3  xB 3  xC 3  xD3  T
20
8
7
15
x A1  x A2  x A3  40
xB1  xB 2  xB 3  20
xC1  xC 2  xC 3  30
xD1  xD 2  xD3  10

 0
 0
 0

xij  0 i  A,B,C,D , j  1,2,3

© K. Jabeur 2012

48

Min

Z T

S.l.c.:

1
1
1
1
x A1  xB1  xC1  xD1  T
10
5
4
8
1
1
1
1
x A2  xB 2  xC 2  xD 2  T
12
10
8
10
1
1
1
1
x A3  xB 3  xC 3  xD3  T
20
8
7
15
x A1  x A2  x A3  40
xB1  xB 2  xB 3  20
xC1  xC 2  xC 3  30
xD1  xD 2  xD3  10

 0
 0
 0

xij  0 i  A,B,C,D , j  1,2,3

© K. Jabeur 2012

49


Documents similaires


cours programmation lineaire 4 1
cours programmation lineaire 7 1
cours programmation lineaire 2 1
cours programmation lineaire 3 1
184787880 programmation lineaire ppt
gainage


Sur le même sujet..