Cours Programmation Linéaire 5 1 .pdf



Nom original: Cours Programmation Linéaire 5-1.pdf
Titre: Diapositive 1
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 1394 fois.
Taille du document: 1.2 Mo (62 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


Algorithme du Simplexe
1. Matrices et vecteurs
2. Systèmes d’égalités linéaires
3. Systèmes d’inégalités linéaires
4. Algorithme du simplexe

1

© K. Jabeur 2008

Matrices et vecteurs : Définitions
• Matrice: tableau rectangulaire, ordonné, de nombres réels
 a11
a
A   21


 am1

am 2

5 3.3 7 
F 

2
8.5
1



0 2 
G   1 0


 3 5 

A : m  n  A a m lignes, n colonnes, mn éléments.

F : 23

F12  3.3

a2 n 



amn 

a22

•Dimensions:

• Éléments:

a1n 

a12

G : 3 2

Aij est l'élément (nombre) en ligne i et colonne j

G21  1

F31 n'existe pas
2

© K. Jabeur 2008

 Transposée : soit A : m  n. Sa transposée est une matrice A : n  m
telle que:

 Aij  Aji

 i  1,

, n, j  1,

,m

2
5
F   3.3 8.5


1 
 7

• Matrices particulières
0
Matrice nulle (m  n): 0 = 

0

0



0 

Matrice carrée: de dimension k  k (# lignes = # colonnes)
1
Matrice identité : matrice carrée I  

 0
3

0

  I ii  1 i
 
I ij  0 i  j

1

© K. Jabeur 2008

• Vecteur: matrice formée d’une ligne (vecteur-ligne) ou d’une
colonne (vecteur-colonne)
a   2 5 1

a3  1

Vecteur de variables: x   x1

x2

xn 

1 0
Vecteur unitaire: un "1" et des "0"  0  ,  0  ,  0
0 1
0 0

Vecteur nul:  0

0 1

0

4

© K. Jabeur 2008

Opérations sur les matrices (et vecteurs)
• Comparaisons , ,  entre matrices

Une relation (, , ) entre 2 matrices n’a de sens que si elles
sont de même dimensions. La comparaison s’effectue position
par position: la relation est vraie si elle est vérifiée par chaque
paire d’éléments en même position.
 5 4 10 
P
F

 2 10 5 

6 5 10 
Q
,  ,  F

5 10 0 

5

© K. Jabeur 2008

x  0  x1  0, x2  0,

, xn  0

(n égalités)

• Addition / soustraction de 2 matrices
N’ont de sens que si les matrices sont de même dimensions.
Effectuées position par position.
4 
 5
5 4.3 10 
 2.3 8.5

F  G  
G

F




0
8.5
6


4 
 4

6

© K. Jabeur 2008

•Multiplication par un scalaire (nombre)
Multiplier tous les éléments par ce nombre.
50 33 70 
10 F  

 20 85 19 

•Produit scalaire de 2 vecteurs
Si x est un vecteur ligne de dimension 1xn, y un vecteur colonne de
dimension nx1, leur produit scalaire est:
x  y   i 1 xi yi
n

5
8 
1 0 2 1     1 5  0  8  2  1  (1)  2  5
1 
 
2
7

© K. Jabeur 2008

• Produit de 2 matrices
Le produit AB de deux matrices A et B n'est défini que si
(# colonnes de A)  (# lignes de B).
Si A est de dimension m  p et B est de dimension p  n, le produit
C  AB est une matrice de dimension m  n définie par:
p
Cij   k 1 Aik Bkj  (i eme ligne de A)  ( j eme colonne de B) i, j
 24.3 25
FG  

11.5 1 

 4
GF   5

 25

8

17
3.3
52.4

2 
7

26 

© K. Jabeur 2008

a
a
Si: A  

a


11

a12

21

a22

m1

am 2


a 
 ( m  n),


a 
a1 n

2n

mn

 a11 x1  a12 x2 
 a x a x 
22 2
alors: Ax   21 1


 am1 x1  am 2 x2 

 x1 
x 
x   2  ( n  1)
 
x 
 n

 a1n xn 
 a2 n xn 



 amn xn 

9

de dimension ( m 1).

© K. Jabeur 2008

Systèmes d’égalités linéaires
• Un système de m égalités linéaires en n variables est de la forme
Ax = b
où A (mxn) est une matrice de coefficients,
x (nx1) est un vecteur de variables,
b (mx1) un vecteur de cotés droits.
• Une solution du système est un choix de valeurs pour
x = (x1, x2,…,xn)’ satisfaisant simultanément les m égalités.
• Opérations permises (ne modifiant pas l’ensemble des
solutions):
– permuter des équations
– multiplier une équation par un nombre non nul
– ajouter une équation à une autre
– et toute combinaison des opérations précédentes (e.g.
retrancher k fois une équation d’une autre).
10

© K. Jabeur 2008

Exemple 1
3x1  2 x2  4

7 x1  5 x2  6

3x1  2 x2  4

7 x1  5 x2  6
 x1  23 x2  43

7 x1  5 x2  6
2

 x1  3 x2 

1
x 

3 2


4
3

10
3

 x1  23 x2  43

x2  10

 x1  8

 x2  10



 x1  ?

 x2  ?



1x1  ? x2  ?

7 x1  5 x2  6



 x1  23 x2  43

0 x1  ? x2  ?

NL2 = AL2  7L1



 x1  23 x2  43

1x2  ?


NL2 = 3  AL2



 x1  0 x2  ?

x2  10


11

NL1 = AL1/3

NL1 = AL1  (2/3)L2

© K. Jabeur 2008

Représentation en tableau (sans variables)
3x1  2 x2  4

7 x1  5 x2  6

 3 2 4
7 5 6 



1 0 ? 
 

0
1
?



3x1  2 x2  4

7 x1  5 x2  6

 3 2 4
7 5 6 



1 ? ? 
 

7
5
6



 x1  23 x2  43

7 x1  5 x2  6

1
7


5


6

1
 
0

 x1  23 x2 

1x 
3 2


1

0

2
3
1
3

4 
3
10 
3 

1 23
 
0 1

4
3

10
3

 x1  23 x2  43

x2  10

 x1  8

 x2  10

2
3

4
3

2
3

?

NL1 = AL1/3

4
3


?

NL2 = AL2  7L1

4
3


?

NL2 = 3  AL2

4 
?  NL1 = AL1  (2/3)L2
1 23
1 0
3
0
  0 1 10 
1 10



8 
1 0
0 1 10 


12

© K. Jabeur 2008

Exemple 2
 3x1  2 x2  x3  4

7 x1  5 x2  4 x3  6

3 2 1 4
7 5 4 6 


1

0

2
3
1
3

1
3
5
3

4 
3
10 
3 

1 0 3 8 
0 1 5 10 





 x1  ?

 x2  ?



1 ? ? ? 
0 ? ? ?



1) NL1 = AL1/3
2) NL2 = AL2  7NL1



1 0 ? ? 
0 1 ? ?



2) NL1 = AL1  (2/3)NL2
1) NL2 = 3  AL2

 x1  8  3x3

 x2  10  5 x3

13

© K. Jabeur 2008

Définitions
• Le système est sous forme canonique lorsque, par des
opérations permises, on a obtenu le plus grand nombre
possible de vecteurs unitaires distincts dans les
colonnes de coefficients.
• Dans une forme canonique,
– Les variables de base sont celles associées à des vecteurs
unitaires (distincts). La base est l’ensemble des variables de
base.
– Les variables hors base sont les autres variables.

14

© K. Jabeur 2008

• Une forme canonique exprime les variables de base (dépendantes)
comme des fonctions des variables hors base (indépendantes).
Exemple:

 x1  8  3x3

 x2  10  5 x3

• On a
– une solution générale lorsqu’on laisse les variables hors base à l’état
de variables;
– une solution particulière lorsqu’on choisit une valeur pour les
variables hors base;
– une solution de base lorsqu’on choisit la valeur 0 pour toutes les
variables hors base.
Solution

Solution

particuliere

générale
 x1 
x   x2 
 
x 
 3

 8  3 x3 
 10  5 x 
3



x3


15

Solution

(x3 =  1)

de base

 5 
 5 
 
 1 
 

 8 
 10 


 0 


© K. Jabeur 2008

Exemple 2 (suite)
Trouver toutes les solutions de base du système précédent.
1 0 3 8 
0 1 5 10  



? 0 1 ? 
? 1 0 ? 



1) NL1 = AL1/(3)
2) NL2 = AL2  5NL1

  13
 5
 3

0 ? 1 ?
1 ? 0 ? 



2) NL1 = AL1 + (1/3)NL2
1) NL2 = (3/5)  AL2

0

1

0 1  83 

10 
1 0 3 
1
5
3
5

Base

1 2 

0 2
Solution générale

Solution de base

 x1 , x2 , x3 

 x1 , x2 , x3 
8,  10, 0 

 x1 , x2  8  3x3 ,  10  5 x3 , x3 
 x2 , x3  x1 , 103  53 x1 ,  83  13 x1 
 x1 , x3

 0, 103 ,  83 

 2  53 x2 , x2 ,  2  15 x2 

 2, 0,  2 
16

© K. Jabeur 2008

Trouver une forme canonique: mécanique
de calcul
Exemple 2:

Tableau de départ

Tableau visé

1 0 ? ? 
0 1 ? ? 



 3 2 1 4
7 5 4 6 


1er pivot:

Départ

 3 2 1 4
7 5 4 6 



But
1 ?
0 ?


Étape 1: identifier l’élément « pivot »
= celui qui deviendra le « 1 » du
vecteur unitaire dans le prochain
tableau (il ne peut pas être nul)

? ?
? ? 

1 23 13 43  NL1 = AL1/3
7 5 4 6 



Étape 2: diviser la ligne du pivot
par le pivot

17

© K. Jabeur 2008

1

0

2
3
1
3

1
3
5
3

4 
3
10 
3 

2ième pivot: Départ
1

0

2
3
1
3

1
3
5
3

4 
3
10 
3 

Étape 3: dans toutes les autres
lignes, ajouter ou retrancher des
NL2 = AL2  7NL1 multiples de la ligne du pivot qu’il
faut pour obtenir les zéros du
vecteur unitaire
But
1 0 ? ? 
0 1 ? ? 



Étape 1: identifier l’élément « pivot » =
celui qui deviendra le « 1 » du vecteur
unitaire dans le prochain tableau

4 
1 23 13
3
0 1 5 10

 NL2 = 3  AL2

Étape 2: diviser la ligne du pivot
par le pivot

1 0 3 8  NL1 = AL1  (2/3)NL2
0 1 5 10



Finito !

 x1  8  3x3

 x2  10  5 x3
18

Étape 3: dans toutes les autres
lignes, ajouter ou retrancher les
multiples de la ligne du pivot qu’il
faut pour obtenir les zéros du
vecteur unitaire

© K. Jabeur 2008

Exercice
Soit le système d'équations:

 x1  5 x2  x3  2 x4  x5  7

 3x1  x2  x3  2 x4  x5  9
2 x  3 x  x  3x  2 x  4
2
3
4
5
 1
1 - Trouver une solution générale ayant pour base  x3 , x4 , x5 
2- Trouver, par pivots successifs, toutes les solutions de base

19

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

20

© K. Jabeur 2008

Exercice
Base

x1

x2

x3 pivot x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



?
?
?

?
?
?

1
0
0

?
?
?

?
?
?

?
?
?

21

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4




1
?
?

5
?
?

1
0
0

2
?
?

1
?
?

7
?
?

22

NL1 = AL1

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

NL2 = AL2  NL1
NL3 = AL3 + NL1

Remarque: toutes ces opérations sont faites sur des lignes entières

23

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

1
2
3

7
2
11

?
?
?

?
?
?

x3



1
4
1

5
6
2

1
0
0

2
4
1

x3
x4


?
?
?

?
?
?

1
0
0

0
1
0

24

pivot

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

x3

?
1
?

?
3/2
?

1
0
0

0
1
0

?
1/2
?

?
1/2
?



25

NL2 = AL2 / 4

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

x3
x4


1
1
0

2
3/2
7/2

1
0
0

0
1
0

0
1/2
7/2

8
1/2
21/2

26

NL1 = AL1 + 2NL2
NL3 = AL3  NL2

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

x3
x4


1
1
0

2
3/2
7/2

1
0
0

0
1
0

x3
x4
x5

?
?
?

?
?
?

1
0
0

0
1
0

27

0 pivot 8
1/2
1/2
7/2
21/2

0
0
1

?
?
?

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

x3
x4


1
1
0

2
3/2
7/2

1
0
0

0
1
0

0
1/2
7/2

8
1/2
21/2

x3
x4


?
?
0

?
?
1

1
0
0

0
1
0

0
0
1

?
?
3

28

NL3 = AL3 / (7/2)

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD





1
3
2

5
1
3

1
1
1

2
2
3

1
1
2

7
9
4

x3



1
4
1

5
6
2

1
0
0

2
4
1

1
2
3

7
2
11

x3
x4


1
1
0

2
3/2
7/2

1
0
0

0
1
0

0
1/2
7/2

8
1/2
21/2

x3
x4
x5

1
1
0

2
1
1

1
0
0

0
1
0

0
0
1

8
2
3

29

NL1 = AL1
NL2 = AL2 + (1/2)NL3

© K. Jabeur 2008

Exercice
Base

x1

x2

x3

x4

x5

CD

x3
x4
x5

1
1
0

2
1
1

1
0
0

0
1
0

0
0
1

8
2
3

 x3  8  x1  2 x2

Solution générale:  x4  2  x1  x2
x  3  x
2
 5

30

© K. Jabeur 2008

FORME CANONIQUE

SOLUTION DE BASE

Base
x3
x4
x5

x1
1
1
0

x2
2
-1
1

x3
1
0
0

x4
0
1
0

x5
0
0
1

CD
8
2
3

x3
x2
x5

3
-1
1

0
1
0

1
0
0

2
-1
1

0
0
1

x3
x1
x5

0
1
0

3
-1
1

1
0
0

-1
1
0

x4
x1
x5

0
1
0

-3
2
1

-1
1
0

1
0
0

x2
x1
x5

0
1
0

1
0
0

1/3 -1/3
1/3 2/3
-1/3 1/3
31

( x1, x2, x3, x4, x5 )
( 0, 0, 8, 2, 3 )

(A)

12
-2
5

( 0, -2, 12, 0, 5 )

(B)

0
0
1

6
2
3

( 2, 0, 6, 0, 3 )

(C)

0
0
1

-6
8
3

( 8, 0, 0, -6, 3 )

(D)

0
0
1

2
4
1

( 4, 2, 0, 0, 1 )

(E)

© K. Jabeur 2008

Définitions
• Deux bases sont voisines si elles ne diffèrent que par une
variable.
• Pour passer d’une base à une base voisine, on effectue. un
pivot L’élément pivot est celui qui se trouve dans la ligne de la
variable qui sortira de la base et dans la colonne de la variable
qui entrera dans la base (cet élément deviendra un « 1 » dans la
prochaine forme canonique).

32

© K. Jabeur 2008

Supposons qu'on veuille passer de la base  a  à la base voisine  b 
(où la variable b remplacera la variable a dans la base).

Forme canonique
de départ:

variable hors base b
 colonne j 


q1
variable de base a  ligne i  

p

pivot
 p  0

qm
q1

Étape 1:
NLi  ALi / p

1
qm

0

Étape 2: Pour toute
autre ligne k  i :
NLk  ALk  qk  NLi

1
0
33

© K. Jabeur 2008

FORME CANONIQUE

SOLUTION DE BASE

Base
x3
x4
x5

x1
1
1
0

x2
2
-1
1

x3
1
0
0

x4
0
1
0

x5
0
0
1

CD
8
2
3

x3
x2
x5

3
-1
1

0
1
0

1
0
0

2
-1
1

0
0
1

x3
x1
x5

0
1
0

3
-1
1

1
0
0

-1
1
0

x4
x1
x5

0
1
0

-3
2
1

-1
1
0

1
0
0

x2
x1
x5

0
1
0

1
0
0

1/3 -1/3
1/3 2/3
-1/3 1/3
34

( x1, x2, x3, x4, x5 )
( 0, 0, 8, 2, 3 )

(A)

12
-2
5

( 0, -2, 12, 0, 5 )

(B)

0
0
1

6
2
3

( 2, 0, 6, 0, 3 )

(C)

0
0
1

-6
8
3

( 8, 0, 0, -6, 3 )

(D)

0
0
1

2
4
1

( 4, 2, 0, 0, 1 )

(E)

© K. Jabeur 2008

FORME CANONIQUE

SOLUTION DE BASE

x2
x1
x3

0
1
0

1
0
0

0
0
1

0
1
-1

1
1
-3

3
5
-3

( 5, 3,-3, 0, 0 )

(F)

x2
x1
x4

0
1
0

1
0
0

0
1
-1

0
0
1

1
-2
3

3
2
3

( 2, 3, 0, 3, 0 )

(G)

x2
x5
x4

1/2
-1/2
3/2

1
0
0

1/2
-1/2
1/2

0
0
1

0
1
0

4
-1
6

( 0, 4, 0, 6, -1 )

(H)

x2
x3
x4

0
1
1

1
0
0

0
1
0

0
0
1

1
-2
1

3
2
5

( 0, 3, 2, 5, 0 )

(I)

35

© K. Jabeur 2008

Systèmes d’inégalités linéaires
• Un système de m inégalités linéaires en n variables est de la forme
Ax  b , où A (mxn) est une matrice de coefficients, x (nx1) est un
vecteur de variables, b (mx1) un vecteur de cotés droits.
• Une solution réalisable du système est un choix de valeurs pour
x = (x1, x2,…,xn)’ satisfaisant simultanément les m inégalités. Le
domaine réalisable est l’ensemble des solutions réalisables.
• Opérations permises (ne modifiant pas le domaine réalisable):
– permuter des inégalités
– multiplier une inégalité par un nombre strictement positif
– multiplier une inégalité par un nombre strictement négatif en
changeant le sens de l’inégalité
– PAS ajouter ou retrancher une inégalité à une autre !
36

© K. Jabeur 2008

Forme standard d’égalité
• On appelle forme standard d’égalité un système d’égalités linéaires et
de restrictions de signe:
 Ax  b

 x j  0 j  J

(A : m  n, x : n  1, J un ensemble d'indices)

• Une solution du système est un choix de valeurs pour x = (x1, x2,…, xn)’
satisfaisant simultanément les m égalités. Par suite, les définitions de
solution générale, solution particulière, et solution de base restent
inchangées
• Toute solution (satisfaisant les égalités) est dite réalisable si de plus elle
satisfait aussi les restrictions de signe. Le domaine réalisable est l’ensemble
des solutions réalisables.
• Tout système d’inégalités peut se réécrire facilement sous forme
standard d’égalité.
37

© K. Jabeur 2008

Exemple
 3x1  x2  x3  2

 x1  2 x2  x3  5



 3 x1  x2  x3  s1  2

 x1  2 x2  x3  s2  5

s1 , s2  0


Posons: s1  2  3 x1  x2  x3
L'inégalité 3 x1  x2  x3  2 est vérifiée si et seulement si s1  0.
Elle est donc équivalente a:
3 x1  x2  x3  s1  2

 s1  0
Posons: s2  x1  2 x2  x3  5
L'inégalité x1  2 x2  x3  5 est vérifiée si et seulement si s2  0.
Elle est donc équivalente a:
 x1  2 x2  x3  s2  5

 s2  0

s1 et s2 sont des variables d’écart.
38

© K. Jabeur 2008

Exercice
Soit le système d'inégalités suivant :

1.
2.
3.

4.
5.

6.

 x1  2 x2  8
x  x  2
 1 2
(I)  x2  3
x  0
 1
 x2  0

Identifier le domaine réalisable de ce système d’inégalités.
Écrire ce système sous une forme standard d’égalités.
Sur le graphique de (1), identifier les droites suivantes : x1=0, x2=0, s1=0,
s2=0 et s3=0. Notons que s1, s2 et s3 sont les variables d’écarts qu’on rajoute
aux 3 premières contraintes.
Identifiez sur le graphe de (1) toutes les solutions de base. Parmi ces solutions
de base, identifiez celles qui sont réalisables.
On veut maximiser la fonction: Z = 2x1 + 3x2 sous les contraintes du
système (I). Trouver sur le graphe la solution optimale.
Trouvez deux séquences de solutions de base réalisables voisines qui mènent
de la solution de base (A) à la solution optimale.

Exercice …(suite)
(1)

x1  0

x2

H
s3  0

G

I

F
E
s2  0

A

C
B

s1  0
x2  0

D

x1

Exercice …(suite)
(2)

 x1  2 x2  s1  8
x  x  s  2
 1 2 2
(II) 
 x2  s3  3
 x1 , x2 , s1 , s2 , s3  0

(3) Voir graphique précédent
(4) Les solutions de base sont notées de A à I, c’est-à-dire 9 solutions de base.
Parmi ces 9 solutions, il existe uniquement 5 solutions qui sont réalisables.
(5) La solution optimale est le point E (x1 = 4, x2 = 2, s1 = 0, s2 = 0, s3 = 1
et Z = 14)
(6) ACE et AIGE

Exercice …(suite)
(1)

x2
H

G

I

E

A

C
B

F

D

x1

Variables d’écart
L'analyse des variables d'écart nous permet d’identifier, à l'optimum,
deux types de contraintes : contraintes saturées (ou liées) et contraintes
lâches (ou non-saturées). En effet, lorsque :
 La variable d'écart de la contrainte (i) est nulle ⇒ la contrainte (i)
est dite saturée (ou liée);
 La variable d'écart de la contrainte (i) est non nulle ⇒ la contrainte
(i) est dite lâche (ou non saturée);
Les contraintes saturées sont intéressantes à mettre en évidence
puisqu’elles limitent l'augmentation de la fonction objectif. Pour
augmenter davantage la fonction objectif, il faudra "relâcher" ces
contraintes.

43

© K. Jabeur 2008

Coûts réduits
Définition: on a des coûts réduits lorsque la fonction objectif

est exprimée uniquement en termes des variables hors base
(lorsque les coefficients des variables de base sont annulés).
Les coûts réduits indiquent l’effet net des variables hors base sur
l’objectif. Sans coûts réduits, on ne peut pas connaître ces effets.

44

© K. Jabeur 2008

Algorithme du simplexe
• Qu’est-ce que c’est ?
– Algorithme = règle/procédure de calcul
– « Simplexe » = … (ensemble de n+1 points dans un espace à n
dimensions)
– Méthode de résolution très répandue
– Méthode itérative

• Principes généraux
1. Examiner des points extrêmes…
– « S’il existe une solution optimale, il existe un point extrême
optimal »
– Point extrême = solution de base réalisable
– Pas tous les points extrêmes …

2. …De voisin en voisin…
45

© K. Jabeur 2008

Forme d’un programme linéaire pour
l’algorithme du Simplexe
c : 1 n

Max/Min Z  cx
S.l.c.:

Ax  b

A: m n
x : n 1

x0

b : m 1

1.
2.

Côtés droits b  0
Forme standard d’égalité

3.
4.

Toutes les variables ont une restriction de signe
On a une forme canonique dans Ax = b
 on a une solution de base réalisable de départ.

5.

Coûts réduits
46

© K. Jabeur 2008

Exemple 1
Max

Z  2 x1  3 x2

Max

Z  2 x1  3 x2

S.l.c.: x1  2 x2  s1  8

S.l.c.: x1  2 x2  8
x1  x2  2

x1  x2  s2  2

x2  3

x2  s3  3

x1 , x2  0

x1 , x2 , s1 , s2 , s3  0

(1) Coté droit est positif

(2) Forme standard d’égalité

(3) Toutes les variables ont une
restriction de signe

(4) Forme canonique dans Ax = b
(5) Coûts réduits
47

© K. Jabeur 2008

Exemple 1
Base

x1

x2

s1

s2

s3

CD

s1

1

2

1

0

0

8

s2

1

-1

0

1

0

2

s3

0

1

0

0

1

3

Z

-2

-3

0

0

0

0

coûts réduits Z  2 x1  3x2  0

Contraintes implicites: x1 , x2 , s1 , s2 , s3  0
 x1   0 
 x2   0 
On a une solution de base de départ A :  x3    8  qui est réalisable
 x   2
 4  
 x5   3 
À ce point, on ne peut pas diminuer x1 ni x2; on peut les augmenter.
48

© K. Jabeur 2008

Choix d’une direction d’amélioration
• Partant d’une solution de base réalisable, une direction d’amélioration est un
déplacement extrême qui améliore l’objectif.
• On n’augmentera donc qu’une des variables hors base, les autres étant
maintenues à 0.
• Quelle variable hors base augmenter ?
Règle intuitive (pas nécessairement la plus efficace, mais elle
fonctionne): la variable qui produit le meilleur taux d’amélioration
par unité sur l’objectif, tel qu’exprimé par son coût réduit.
• Dans notre exemple, on part de la solution de base actuelle (A). Ici,
améliorer Z = l’augmenter.

Max Z  2 x1  3x2
plus grand taux d’augmentation:
augmenter x2, garder x1 = 0
49

© K. Jabeur 2008



Documents similaires


cours programmation lineaire 5 1
l1 maths fondamentales
tp exos corriges matlab
exercices informatique seance 1
td6 reduction des matrices
e3a 2013 mp b


Sur le même sujet..