184787880 Programmation lineaire ppt .pdf



Nom original: 184787880-Programmation-lineaire-ppt.pdfTitre: Chapitre I€: Théorie des graphes Auteur: FAC

Ce document au format PDF 1.5 a été généré par www.convertapi.com / www.convertapi.com , et a été envoyé sur fichier-pdf.fr le 10/11/2017 à 15:28, depuis l'adresse IP 160.177.x.x. La présente page de téléchargement du fichier a été vue 315 fois.
Taille du document: 1.3 Mo (57 pages).
Confidentialité: fichier public

Aperçu du document


Partie I : Programmation
linéaire

Pr : E. EL GUARMAH

1

Principe :






Forme canonique
Résolution graphique
Méthode du simplexe
Dualité
Complément : variables artificielles

2

Principe :

La programmation linéaire a pour objet de résoudre un problème
économique :
• Optimiser (recherche d’un maximum ou d’un minimum) une
fonction économique de forme linéaire,

• Compte tenu de contraintes (équations et/ou inéquations
linéaires).

3

I. Forme canonique
Il s’agit de l’étape la plus importante de la résolution. Elle consiste à
exprimer sous une forme mathéamtiques un problème énoncé de façon
littéraire.

Forme canonique
(Mathématisation du problème)
1- Définir de façon précise les variables.
2- Exprimer les contraintes.
3- Exprimer la fonction économique.

4

I. Exemple 1 : problème de maximisation comportant
deux variables
Une entreprise fabrique deux produits P1 et P2. les ressources requises
pour la fabrication d’une tonne de chaque produit et le profit unitaire
sont données par le tableau suivant :
Ressources

Produit P1

Produit P2

Disponibilité de
chaque ressource

Espace (m2)
Main d’ouvre
(homme - semaine)
Matériaux (tonne)
Matériaux2

2
1

1
2

10
10

1
1

1
3

6
12

Profit sur chaque
produit

1

2

Question : Quelle quantité de chaque produit l’entreprise devrait
elle fabriquer afin de maximiser son profit ?
5

I. Modélisation du problème
• Définition des variables :

Soit : x : le nombre de tonne de P1 qu’on fabrique
y : le nombre de tonne de P2 qu’on fabrique
• Contraintes :

(1)
(2)
(3)
(4)
(5)
(6)

2x  y  10
x  2 y  10
x y 6
x  3 y  12
x0
y0

dites évidentes ou implicites

• Fonction économique :
Maximiser

x + 2y
6

I. Forme canonique du problème
D’où la forme canonique :

Maximiser x  2 y
2 x  y  10

 x  2 y  10

x  y  6
 x  3 y  12

x  0
y  0


Ce programme est dit linéaire car les contraintes et
la fonction économique sont du premier degré

7

I. Exemple 2 : problème de minimisation comportant
deux variables
La Saudel envisage de confier à son unité de production du Nord-Est,
l’élaboration des coussinets (A) et des paliers (B) demandés par
certains industriels; cette fabrication devra répondre aux contraintes
mensuelles suivantes :
Fabrication minimale :
. Coussinets (A) : 4 000 unités
. Paliers (B) : 5 000 unités
-

La matière première sera livré par l’unsine principale à l’unité de
production qui devra traiter un minimum de 36 000 kg de matière,

-

En ce qui concerne la main d’oeuvre, et compte tenu des perspectives
de développement ultérieur, le maximum sera fixé à 10 000 heures.

8

I. Exemple 2 : problème de minimisation comportant
deux variables
Renseignement complémentaires :
Matière première par produit
Main d’œuvre par produit
Poids du produit fini

A

B

2 kg
1 Heure

3 kg
0,5 Heure

1,5 kg

2 kg

La société souhaite déterminer le programme mensuel de
farication des coussinets (A) et des paliers (B), sachant que
le coût des transports mis en place entre l’unité de
production et l’usine principale pour l’acheminement des
matières premières et le retour des produits finis devra être
rendu minimal; le prix de ce transport a été estimé à 2
Euros par kilo de matière ou de produit fini transporté.
Présenter la forme canonique du programme
9

I. Modélisation du problème
• Définition des variables :

Soit : x : le nombre de coussinets A à produire chaque mois
y : le nombre de paliers B à produire chaque mois.
• Contraintes :
- Contraintes de positivité :

x  0
y  0

- Contraintes de marché :

x  4 000
y  5 000
- Contraintes techniques :

2 x  3 y  36 000
x  0,5 y  10 000
10

• Fonction économique :
Coût du poids transporté pour un produit A : (2+1,5)2 = 7 Euros
Coût du poids transporté pour un produit B : (3+2)2 = 10 Euros
Minimiser 7x+10y

11

I. Forme canonique du problème
D’où la forme canonique :
Minimiser 7 x  10 y
 x  4 000

 y  5 000

2 x  3 y  36 000
 x  0,5 y  10 000

x  0
y  0

Ce programme est dit linéaire car les contraintes et
la fonction économique sont du premier degré

12

I. Forme canonique du problème
La programmation mathématique suppose l’écriture d’un
modèle d’optimisation sous contrainte. On la considère
souvent comme un ensemble de techniques permettant la
résolution de tels modèles:
Minimiser F ( x)
sous les contraintes

 g ( x)  0 i  1,...,n
 i
 x  S  n

x=(x1,….,xn) : sont des inconnues du problème
F est appelé la fonction objectif (on dit aussi fonction économique)
et l’ensemble des conditions gi(x)≤0 (i=1,….,n) et

xS

Sont les contraintes du problème.

13

II. Résolution graphique
La résolution graphique est à privilégier pour les programmes linéaires
à deux variables.
II.1- Détermination du Domaine des Solutions Acceptables (DSA)
Chaque contrainte partage le plan en deux parties. L’étude du point (0,0)
permet de définir :
• Le demi-plan qui respecte la contrainte.
Si l’inéquation est vérifié pour (0,0), le demi-plan fait partie du domaine des
solutions acceptables.
Quand l’inégalité est au sens large, les points de la droite font partie du
Domaine des Solutions Acceptables (D.S.A)
Y
200

6 x  5 y  900

150
100
50
0
0

50

100

150

200

X

14

II. Résolution graphique

• Le demi-plan qui ne respecte pas la contrainte.
Si l’inéquation n’est pas vérifié pour (0,0), on hachure cette partie qui
ne fait pas partie du domaine des solutions acceptables.
Y
200

x  y  80

150
100
50
0
0

50

100

150

200

X

Le Domaine des Solutions Acceptables (D.S.A) est
l’ensemble des combinaisons (x,y) qui respecte les
contraintes du programme linéaire.
15

II. Résolution graphique
II.2- Tracement de la fonction économique
Pour tracer une fonction économique (ax+by), il faut étudier ax+by=k,
en donnant une valeur à k (généralement 0).
a
b

Il s’agit d’une famille de droites parallèles de coefficients directeur  x
Exemple : étudier la fonction x+2y

Fonction
passe par
et par
valeur de F

K=0

K=100

K=200

x+2y=0
(0;0)
(100;-50)
F=0

x+2y=100
(0;50)
(100;0)
F=100

x+2y=200
(0;100)
(200;0)
F=200

16

100

50

50

100

200

K=100

K=200

K=0

Plus la valeur k augmente (diminue), plus la parallèle
de F est éloignée (proche) de l’origine et plus la
valeur de l’objectif augmente (diminue)
17

II. Résolution graphique
II.3- Recherche de l’optimum
Le résultat suivant sera admis : s’il existe au moins une solution optimale, il y a un
sommet du D.S.A qui correspond à une solution optimale.
Deux méthodes de recherche sont possibles :

• Méthode analytique
La valeur de la fonction économique ax+by doit être optimale

MAXIMISATION

MINIMISATION

Plus la valeur k est grande,
meilleur est le résultat

Plus la valeur k est petite,
meilleur est le résultat

La solution maximale est donc
le sommet par lequel passe la
parallèle de F la plus éloignée
du point d’origine (0;0)

La solution minimale est donc
le sommet par lequel passe la
parallèle de F la plus proche
du point d’origine (0;0)
18

I. Langage élémentaire des graphes
• Méthode énumérative
La méthode énumérative consiste à calculer la valeur de F en chacun
des sommets du domaine des solutions acceptables et à retenir la
solution optimale.
Cette méthode est à utiliser en complément de la précédente, lorsque
la translation de la fonction économique laisse un doute entre des
sommets proches.
Exemple : résolution graphique des problèmes présentés
en paragraphe 1.

19

II. Résolution graphique
II.4- Cas particulier : dégénérescence
Quand la fonction économique est parallèle à un coté du domaine des solutions
acceptables et ne passe plus par un seul sommet, la solution optimale n’est pas unique
et le cas est dit dégénéré.
L’ensemble des solutions optimales est infini et se compose de toutes les combinaisons
situés sur le segment du domaine des solutions acceptables parallèles à la fonction
économique.
Exemple : présentation d’un cas dégénéré

 Min F  400x  600 y
x  0


y  0

2 x  3 y  600
 x  50


 y  100
20

III. Méthode du simplexe
Cette méthode, applicable quel que soit le nombre de variables, sera présenté dans
ce paragraphe pour des problèmes de maximation dont les contraintes (autres que
celles de positivité) sont de type ≤.
Exemple : problème de maximisation comportant trois variables.
La société BETA fabrique trois modèles de meubles : classique, rustique, moderne.
Les standards unitaires de production sont résumés dans le tableau suivant :

Bois
Main d’œuvre
Centre finition
Marges sur coûts
variables

Modèle
Modèle Modèle
Classique Rustique Moderne

Capacités
maximales

5
1
2
1000

900
516
200

8
2
2
960

5
3
0
1200

La société BETA souhaite déterminer les quantités à produire pour maximiser
son résultat.

21

III. Méthode du simplexe
Forme canonique de ce programme :

 x  0; y  0; z  0
5 x  8 y  5 z  900

1x  2 y  3z  516
2 x  2 y  0 z  200

 F  100x  960 y  1200z ( MAX )
22

3.1 Forme standard

La méthode du simplexe nécessite une mise sous forme standard :

Les inégalités sont transformées en égalités grâce à l’introduction de
variables d’écarts positives ou nulles notées ei.

Il y a une variables d’écart pour chaque contrainte autre que contrainte de positivité

23

3.1 Forme standard
Forme canonique :
 x  0; y  0; z  0
5 x  8 y  5 z  900


1x  2 y  3 z  516
2 x  2 y  0 z  200


 F  100x  960 y  1200z

( MAX )

Forme standard :
 x  0; y  0; z  0; e1  0; e2  0; e3  0
5 x  8 y  5 z  e  900
1


1x  2 y  3 z  e2  516
2 x  2 y  0 z  e  200
3


 F  100x  960 y  1200z ( MAX )
24

3.2 Recherche de la solution optimale
Les calculs sont présentés dans des tableaux en utilisant la méthode du pivot de
Gauss

3.2.1 Interprétation d’un tableau

3.2.2 Solution de départ : premier tableau

3.2.3 Détermination du pivot

3.2.4 Progression jusqu’à la solution optimale

25

3.2.1 Interprétation d’un tableau

QUEL QUE SOIT LE TABLEAU

• Les variables hors - base sont égales à zéro,
• La valeur des variables dans la base est lue dans la colonne B,
• L’optimum est atteint si tous les coefficients de la dernière
ligne sont négatifs ou nuls

26

3.2.2 Solution de départ : premier tableau

Le premier tableau reprend les coefficients de la forme standard

Hors base

x

y

z

.

.

.

Lecture du tableau

B

En base

Variables

Variables

hors base

dans la base

e1
e2
e3

5
1
2

8
2
2

5
3
0

1
0
0

0
1
0

0
0
1

900
516
200

x=0

e1=900

y=0

e2=516

F

1000

960

1200

0

0

0

0

z=0

e3=200
F=0

27

Interprétation du tableau

• Il s’agit de la solution admissible de départ qui
respecte toutes les contraintes.
• La production est donc nulle (x=0;y=0;z=0) et la
valeur de la fonction objectif est égale à 0.
• Cette solution peut être améliorée puisque les
coefficients de la ligne F ne sont pas négatifs ou
nuls.
28

3.2.3 Détermination du pivot
• La variable qui entre dans la base est celle dont le coefficient positif
de dernière ligne est le plus grand.
• La variable qui sort de la base est celle dont la résultante (R) positive
est la plus petite.
• Le pivot est situé à l’intersection de la variable entrante et de la variable
sortante.

Remarque : si un zéro apparaît dans la colonne B et qu’il faut déterminer
une variable sortante, il faut le remplacer par un nombre positif infiniment
petit, noté ε, et continuer les calculs avec cette valeur. A l’optimum, cette
valeur ε sera considérée comme égale à zéro.

29

3.2.3 Détermination du pivot

Hors base

x

y

z

.

.

.

B

L3

e1
e2
e3

5
1
2

8
2
2

5
33
0

1
0
0

0
1
0

0
0
1

900
516
200

L4

F

1000

960

1200

0

0

0

0

R

En base
L1

L2

900/5=180
516/3=172

e2 sort de la base

200/ε = ∞

z entre dans la base

30

3.2.4 Progression jusqu’à la solution optimale
Deuxième tableau

z est entré dans la base, tandis que e2 en est sorti
Hors base

x

y

.

.

e2

.

B

14/3
2/3
2

0
1
0

1
0
0

-5/3
1/3
0

0
0
1

40
172
200

160

0

0

-400

0

-206 400

En base
L’1=L1-5L’p

e1

L’2=L’p=L1/3

z

L’3=L3-0L’p

e3

10/3
1/3
2

L’4=L4-1200L’p

F

600

Valeur de F au signe près

31

Interprétation du tableau

• Les variables hors base sont nulles : x=y=e2=0.
• Les variables en base sont e1=40,z=172 et e3=200
• La production est donc égale à 172 produits z.
• L’objectif est égal à 206 400 Euros.
• Cette solution peut être améliorée puisque les
coefficients de la ligne F ne sont pas négatifs ou
nuls.
32

3.2.3 Détermination du pivot

Hors base

x

y

.

.

e2

.

B

R

1
0
0

-5/3
1/3
0

0
0
1

40
172
200

12

0

-400

0

-206 400

En base
L’1

L’2

e1

10/3 14/3

z

2/3
2

0
1
0

160

0

L’3

e3

1/3
2

L’4

F

600

e1 sort de la base

516
100

x entre dans la base

33

3.2.4 Progression jusqu’à la solution optimale
Troisième tableau

Hors base

x

y

.

e1

e2

.

B

1,4
0,2
-0,8

0
1
0

0,3
-0,1
-0,6

-0,5
0,5
1

0
0
1

12
168
176

-680

0

-180

-100

0

-213 600

En base
L ’’1=L’’p=L’1/(10/3)

x

L’’2=L’2-(1/3)L’’p

z

L’’3=L’3-2L’’p

e3

1
0
0

L’’4=L’4-600L’’p

F

0

Valeur de F au signe près

34

Interprétation du tableau

• Les variables hors base sont nulles : y=e1=e2=0.
• Les variables en base sont x=12,z=168 et e3=176
• Il s’agit de la solution optimale puisque tous
coefficients de la dernière ligne (ou taux marginaux
de substitution) sont négatifs ou nuls.
• La solution optimale est la production de 12
modèles classiques, 0 modèle rustique et 168
modèles modernes pour une marge sur coûts
variables maximales de 213 600 Euros.
35

IV. Dualité
Exemple :

 x  0; y  0; z  0
1x  2 y  1z  16

2.5 x  1y  1.5 z  10


MIN F  195x  160 y  120z

1- La résolution graphique n’est pas
applicable puisque le programme
comporte plus de deux variables
2-La méthode du simplexe n’a été
présentée que pour des contraintes ≤

36

IV. 1 Du programme primal au programme dual
La dualité permet de résoudre les problèmes de minimisation dont les contraintes
(autres que celles de positivité) sont de sens ≥ :
ELABORATION DU DUAL
• Le nombre de variables du dual est égal au nombre de contraintes
(autres que celles de positivité) du primal. Elles doivent être différenciées
de celles du primal.

• Le nombre de contraintes du dual est égal au nombre de variables du
primal.
• Les coefficients des colonnes (lignes) du primal sont les coefficients des
lignes (colonnes) du dual.
• Les inégalités du dual sont de sens opposé à celles du primal.
• Les coefficients de la fonction économique du primal sont les contraintes
du dual.
• Si le primal est une minimisation, le dual est une maximisation, et inversement.
• Les coefficients de la fonction économique du dual sont les contraintes du primal.
Remarque : le dual du dual est le primal
37

IV. 1 Du programme primal au programme dual

PRIMAL : Le programme à résoudre est dit programme primal
 x  0; y  0; z  0
a x  a y  a z  A
1
2
3


b1 x  b2 y  b3 z  B
c x  c y  c z  C
2
3
1

MIN (d1 x  d 2 y  d 3 z )
DUAL
u  0; v  0; w  0
a u  b v  c w  d
1
1
1
1


a2u  b2 v  c2 w  d 2
a u  b v  c w  d
3
3
3
 3

 MAX ( Au  Bv  Cw)
La résolution du dual impose de retrouver les solutions du primal
38

IV. 2 Interprétation du problème dual

PRIMAL
 x  0; y  0; z  0
1x  2 y  1z  16


2.5 x  1 y  1.5 z  10

MIN (195x  160 y  120z )
DUAL
u  0; v  0
1u  2.5v  195


2u  1v  160
1u  1.5v  120


MAX (16u  10v)
39

IV. 3 Résolution du problème
Il s’agit de résoudre le primal. Il faudra donc déterminer la solution du
programme primal à partir de la résolution du programme dual.

Forme standard du dual :
u  0; v  0
e  0; e  0; e  0
2
3
 1

1u  2.5v  e1  195

2u  1v  e2  160
1u  1.5v  e3  120


MAX (16u  10v  0e1  0e2  0e3 )

40

Premier tableau

Hors base

u

v

.

.

.

B

1

L3

e1
e2
e3

1

2.5
1
1.5

1
0
0

0
1
0

0
0
1

195
160
120

L4

F

16

10

0

0

0

0

R

En base
L1

L2

2

195/1=195
160/2=80

e2 sort de la base

120/1 = 120

u entre dans la base

41

Deuxième tableau

Hors base

.

v

.

e2

.

B

0
1
0

2
0.5

L’3=L3-1L’p

e1
u
e3

1

1
0
0

-0.5
0.5
-0.5

0
0
1

115
80
40

L’4=L4-16L’p

F

0

2

0

-8

0

-1280

R

En base
L’1=L1-1L’p

L’2= L’p=L2/2

115/2=57,5
80/0,5=160

40/1 = 40 e3 sort de la base

u entre dans la base

42

Troisième tableau

Hors base

.

.

.

e2

e3

B

e1
u
v

0
1
0

0
0
1

1
0
0

-0.5
0.5
-0.5

0
0
1

35
60
40

F

0

0

0

-7

-2 -1360

x

y

z

En base
L ’’1=L’1-2L’’p
L’’2= L’2-0,5L’’p
L’’3=L’’p=L’3/1

L’’4=L’4-2L’’p

43

IV. 3 Résolution du problème
L’optimum du dual est atteint, mais il s’agit de résoudre le programme primal :
SOLUTIONS DU PRIMAL
• A l’optimum, la solution du programme primal est, au signe près, lue sur la
dernière ligne du tableau dans les colonnes des variables d’écart.
Remarque : à l’optimum, la valeur de la fonction économique du dual est égale à
celle du primal.
La solution du primal est donc :
x=0

y=7
z=2
F=1360
44

V. COMPLEMENT : VARIABLES ARTIFICIELLES
L’introduction de variables artificielles permet de résoudre le problème posé
Par les contraintes ≥ :
VARIABLES ARTIFICIELLES

1- Introduire une variable artificielle par contrainte ≥.
La variable d’écart de la contrainte, affectée du coefficient -1, est mise hors base.
2- Elles permettent simplement l’égalité dans la forme standard et ne sont pas une
donnée du problème. En conséquence, elles doivent être nulles à l’optimum.
Pour cela, il faut les faire sortir de la base en leur donnant un coefficient fortement
Pénalisant dans la fonction économique :
• S’il s’agit d’une maximisation, le coefficient affecté à la variable est très négatif : -M.
• S’il s’agit d’une minimisation, le coefficient affecté à la variable est très positif : +M

45

V.1 Résolution d’une maximisation
Soit le programme linéaire :
 x  0; y  0; z  0;

1x  3 y  z  10000
2 x  1 y  z  5000

Max( F )  100x  500 y  200z

La forme standard de ce programme est :
 x  0; y  0; z  0;
e  0; e  0; a  0;
1
2
1

1x  3 y  z  e1  10000

2 x  1 y  z  e2  a1  5000
Max( F )  100x  500 y  200z  0e1  0e2  Ma1
46

V.1 Résolution d’une maximisation
D’après la deuxième contrainte : a1=5000-2x-y-z+e2
D’où

F=100x+500y+200z+0e1+0e2-M(5000-2x-y-z+e2)
F=100x+500y+200z+0e1+0e2+2xM+yM+zM-e2M-5000M

47

Premier tableau

Hors base

x

y

z

.

e2

.

B

1

3
1

1
1

1
0

0
-1

0
1

10000
5000

500
+1M

200
+1M

0

0
-1M

0

0
+5000M

R

En base

e1
a1
F

2
100
+2M

10000/1=10000
5000/2=2500
Changer le signe
puisque F est lue
au signe près

2M est le plus fort coefficient.

48

Deuxième tableau

Hors base

.

y

z

.

e2

a1

B

e1
x

0
1

2,5
0,5

1
0,5

1
0

0,5
-0,5

-0,5
0,5

7500
2500

F

0

450
+0M

150
+0M

0

0
+0M

-50
-M

-250 000
+0M

R

En base

7500/2,5=3000
2500/0,5=5000

450 est le plus fort coefficient positif.

La sortie de la base d’une variable artificielle étant définitive, sa
colonne peut être supprimée.
49

Troisième tableau

Hors base

.

.

z

e1

e2

B

y
x

0
1

1
0

0,4
0,3

0,4
-0,2

0,2
-0,6

3000
1000

F

0

0

-30

-180

-40

-1 600 000

En base

La solution optimale est atteinte : x=1 000; y=3 000; z=0 et F= 1 600 000.

50


184787880-Programmation-lineaire-ppt.pdf - page 1/57
 
184787880-Programmation-lineaire-ppt.pdf - page 2/57
184787880-Programmation-lineaire-ppt.pdf - page 3/57
184787880-Programmation-lineaire-ppt.pdf - page 4/57
184787880-Programmation-lineaire-ppt.pdf - page 5/57
184787880-Programmation-lineaire-ppt.pdf - page 6/57
 




Télécharger le fichier (PDF)

184787880-Programmation-lineaire-ppt.pdf (PDF, 1.3 Mo)

Télécharger
Formats alternatifs: ZIP




Documents similaires


r vision
ro
6obo6j8
analyse et optimisation convexe professeur benzine rachid
chapitre4
essentiel langage c

Sur le même sujet..