Cours Programmation Linéaire 6 1 .pdf



Nom original: Cours Programmation Linéaire 6-1.pdf
Titre: Résolution de programmes linéaires généraux
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 1109 fois.
Taille du document: 195 Ko (19 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


Résolution de programmes linéaires généraux
Forme initiale pour l’algorithme du Simplexe
 Cotés droits  0
 Tous les x ont une restriction de signe  0
 Forme standard d’égalité
 Forme canonique
 Coûts réduits

© Khaled Jabeur 2008

1

Exemple 1
Min Z  3 x1  7 x2
S.l.c 2 x  3 x  12

1
2
(II) 
x1  2 x2  5


x1 , x2  0

Z  3 x1  7 x2

Min
S.l.c

(I) 



2 x1  3 x2  12
 x1  2 x2  5
x1 , x2  0

Min Z  3x1  7 x2
S.l.c 2 x  3 x  s  12

1
2
1
(III) 
x1  2 x2  s2  5


x1 , x2 , s1 , s2  0

x1
s1
Z

(I)  (II)  (III)

x2

s1

s2

2 3

1

0

12

1 2

0 1

5

0

0

3

7

0

2

x1

x2

s1

s2

s1

2 3

1

0

y

1 2

0 1

Z

3

7

0

y
0 12
1

5

0 -M

0

© Khaled Jabeur 2008

3

x1

x2

s1

s2

s1

2 3

1

0

y

1 2

0 1

Z

3

7

0

y
0 12
1

5

0 -M

0

Min Z  3x1  7 x2
S.l.c 2 x  3 x  s  12

1
2
1
(IV) 
x1  2 x2  s2  y  5


x1 , x2 , s1 , s2 , y  0

(III)  (IV) si et seulement si y  0 !!!
y  "variable artificielle"

© Khaled Jabeur 2008

4

x1

x2

s1

s2

s1

2 3

1

0

y

1 2

0 1

Z

3

7

0

y
0 12
1

5

0 -M

0

Min Z  3x1  7 x2  My
S.l.c 2 x  3 x  s  12

1
2
1
(IV) 
x1  2 x2  s2  y  5


x1 , x2 , s1 , s2 , y  0

© Khaled Jabeur 2008

5

x1

x2

s1

s2

s1

2 3

1

0

y

1 2

0 1

Z

3

7

0

Min Z  3x1  7 x2  My
S.l.c 2 x  3 x  s  12

1
2
1
(IV) 
x1  2 x2  s2  y  5


x1 , x2 , s1 , s2 , y  0

y
0 12
1

5

0 -M

0

Couts réduits:
x1

x2

s1

s2

y

s1

2

3

1

0

0

12

y

1

2

0

1

1

5

0

M 0 5M

Z

M  3 7  2M

© Khaled Jabeur 2008

6

x1

x2

s1

s2

y

s1

2

3

1

0

0

12

6

y

1

2

0

1

1

5

5

0

M 0 5M

Z

M  3 7  2M

© Khaled Jabeur 2008

7

x1

x2

s1

s2

y

s1

2

3

1

0

0

12

y

1

2

0

1

1

5

0

M 0 5M

Z

M  3 7  2M
x1

x2

s1

s2

y

s1

0

1

1

2

2

2

2

x1

1

2

0

1

1

5



Z

0

1

0

3 3  M 15

© Khaled Jabeur 2008

8

x1

x2

s1

s2

y

s1

2

3

1

0

0

12

y

1

2

0

1

1

5

0

M 0 5M

Z

M  3 7  2M
x1

x2

s1

s2

y

s1

0

1

1

2

2

2

x1

1

2

0

1

1

5

Z

0

1

0

3 3  M 15

x1

x2

s1

s2

y

x2

0

1

1

2

2

2

x1

1

0

2

3

3

9

Z

0

0

1 5 5  M 13

 x1   9 
 x   2
Solution
 2  
optimale  s1    0 
pour (IV):  s2   0 
   
 y  0
   

Comme y  0, cette solution est aussi optimale pour (III).

Z  13

9

Autre convention d’écriture (facultative)
y
x1
x2
s1
s2
s1
y
Z

2
1
3
0

3
2
7
0

1
0
0
0

0
1
0
0

0
1
0
M

12
5
0
0

s1
y
Z

2
1
3
M

3
2
7
2M

1
0
0
0

0
1
0
M

0
1
0
0

12
5
0
5M

s1
x1
Z

0
1
0
0

1
2
1
0

1
0
0
0

2
1
3
0

2
1
3
M

2
5
15
0

x1
x2
Z

0
1
0
0

1
0
0
0

1
2
1
0

2
3
5
0

2
3
5
M

2
9
13
0

10

Exemple 2
Max
S.l.c

(I) 



Max
S.l.c

 (III) 




Z  4 x1  x2
2 x1  x2  2
2 x1  2 x2  5
4 x1  3 x2  7
x1 , x2  0

Max
S.l.c

 (II) 




Z  4 x1  x2
2 x1  x2  2
2 x1  2 x2  5
4 x1  3 x2  7
x1 , x2  0

Z  4 x1  x2
2 x1  x2  s1  2
2 x1  2 x2  s2  5
4 x1  3 x2  7
x1 , x2 , s1 , s2  0

© Khaled Jabeur 2008

11

s1
s2
a
Z

x1

x2

s1

s2

a

2
2
4
4
0

1
2
3
1
0

1
0
0
0
0

0
1
0
0
0

0
0
1
0
M

© Khaled Jabeur 2008

2
5
7
0
0

12

s1
s2
a
Z

x1

x2

s1

s2

a

2
2
4
4
0

1
2
3
1
0

1
0
0
0
0

0
1
0
0
0

0
0
1
0
M

Max
S.l.c

(IV) 




2
5
7
0
0

Z  4 x1  x2
2 x1  x2  s1  2
2 x1  2 x2  s2  5
4 x1  3 x2  a  7
x1 , x2 , s1 , s2 , a  0

(IV)  (III) seulement si a  0
© Khaled Jabeur 2008

13

s1
s2
a
Z

x1

x2

s1

s2

a

2
2
4
4
0

1
2
3
1
0

1
0
0
0
0

0
1
0
0
0

0
0
1
0
M

Max
S.l.c

(IV) 




2
5
7
0
0

Z  4 x1  x2  Ma
2 x1  x2  s1  2
2 x1  2 x2  s2  5
4 x1  3 x2  a  7
x1 , x2 , s1 , s2 , a  0

(IV)  (III) seulement si a  0
© Khaled Jabeur 2008

14

s1
s2
a
Z

s1
s2
a
Z

x1

x2

s1

s2

a

2
2
4
4
0

1
2
3
1
0

1
0
0
0
0

0
1
0
0
0

0
0
1
0
M

x1

Coûts réduits :
x2
s1 s2 a

2
2
4
4
4M

1
2
3
1
3M

1
0
0
0
0

0
1
0
0
0

© Khaled Jabeur 2008

0
0
1
0
0

2
5
7
0
0

2
5
7
0
7M
15

s1
s2
a
Z

x1

x2

s1

s2

a

2
2
4
4
4M

1
2
3
1
3M

1
0
0
0
0

0
1
0
0
0

0
0
1
0
0

© Khaled Jabeur 2008

2
1

5
7 7/4
0
7M

16

x1

x2

s1

s2

a

s1
s2
a
Z

2
2
4
4
4M

1
2
3
1
3M

1
0
0
0
0

0
1
0
0
0

0
0
1
0
0

2
5
7
0
7M

x1
s2
a
Z

1
0
0
0
0

1/2
3
1
3
M

1/2
1
2
2
2M

0
1
0
0
0

0
0
1
0
0

1
7
3
4
3M

© Khaled Jabeur 2008

2
7/3

3

17

x2
s2
a
Z

x1

x2

s1

s2

a

2
6
2
6
2M

1
0
0
0
0

1
2
3
1
3M

0
1
0
0
0

0
0
1
0
0

Solution optimale
du probleme (IV):

 x1   0 
 x   2
 2  
 s1    0  ,
   
 s2   1 
 a  1
   

2
1
1
2
M

Z  2  M

Comme a = 1, le problème (III) n’a pas de solution réalisable.
© Khaled Jabeur 2008

18

Programmes linéaires: cas possibles de solution

1. Pas de solution
réalisable
Au moins une
variable artificielle
est > 0 dans la
solution optimale
du problème
transformé.

2. Solution(s)
sans borne
Aucune var. artif. > 0.
Au moins une variable
hors base a un coût réduit
< 0 (max)
> 0 (min)
et n’a aucun coefficient
> 0 dans les contraintes

3. Une ou plusieurs
solution(s) optimales finies
Aucune var. artif. > 0.
Toutes les variables hors
bases ont des coûts réduits
 0 (max)
 0 (min)

3.a Une
3.b Plusieurs
Toutes les variables
Au moins une
hors base ont des
variable hors base
coûts réduits  0 a un coût réduit = 0
© Khaled Jabeur 2008

19



Documents similaires


cours programmation lineaire 3 1
ro
cours programmation lineaire 4 1
cours programmation lineaire 2 1
cours programmation lineaire 7 1
cours programmation lineaire 6 1


Sur le même sujet..