0% ont trouvé ce document utile (0 vote)

20 vues29 pages

Solution Initiale, Résolution D'un Système D'équations Et Tableau Du Simplexe

Le document traite de la résolution de systèmes d'équations linéaires et de l'utilisation du tableau du simplexe pour optimiser un programme linéaire. Il explique la forme standard d'un programme linéaire, les solutions admissibles, et les pivots nécessaires pour trouver la solution optimale. Des exemples illustrent la méthode du simplexe et les éléments du tableau associés.

Transféré par

nada el qaddoury

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

20 vues29 pages

Solution Initiale, Résolution D'un Système D'équations Et Tableau Du Simplexe

Transféré par

nada el qaddoury

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Solution initiale, résolution d’un système d’équations

et tableau du simplexe

Objectifs

Résoudre un système d’équations linéaires ;

Identifier et calculer tous les éléments d’un tableau du simplexe.

01
Solution initale, résolution d’un système
d’équations linéaires avec une infinité de
solutions et liens avec la fonction objectif.

02
Programme linéaire : Forme standard

Max 2 x1 + 3 x2 Max 2 x1 + 3 x2

x1 + x2 ≤ 5 x1 + x2 + e1 = 5

2x1 + x2 ≤ 8 2x1 + x2 + e2 = 8

x2 ≤ 4 x2 + e3 = 4

x1, x2 ≥ 0 x1, x2, e1 ,e2 ,e3 ≥ 0

03
Programme linéaire : Forme standard

Max 2 x1 + 3 x2
x1 + x2 + e1 = 5

2x1 + x2 + e2 = 8

x2 + e3 = 4

x1, x2, e1 , e2 , e3 ≥ 0

Système avec 3 équations et 5 inconnues

infinité de solutions
04
Système d’équations linéaires

x2
2
2x1 + x2 ≤ 8
x2 ≤ 4 x1 + x2 + e1 = 5
3
2x1 + x2 + e2 = 8

x2 + e3 = 4

x1 , x 2 , e 1 , e2 , e3 ≥ 0

x1
1
Infinité de solutions x1 + x2 ≤ 5

05
Système d’équations linéaires

x1 + x2 + e1 = 5

2x1 + x2 + e2 = 8

x2 + e3 = 4

1 1 1 0 0 5

2 1 0 1 0 8

0 1 0 0 1 4

06
Système d’équations linéaires

Les variables en base en fonction des variables hors-base

x1 + x2 + e1 = 5 e1 = 5 - x1 - x2
2x1 + x2 + e2 = 8 e2 = 8 - 2x1 - x2
x2 + e3 = 4 e3 = 4 - x2

Ici les variables e1 , e2 et e3 sont exprimées en fonction des

variables x1 et x2 .

Pour certaines valeurs non négatives de x1 et x2 , on a une

solution admissible pour le programme linéaire.

Si on pose x1 et x2 égales à zéro, on obtient alors une solution 07

de base admissible.
Système d’équations linéaires

Les variables en base en fonction des variables hors-base

x1 + x2 + e1 = 5 e1 = 5 - x1 - x2
2x1 + x2 + e2 = 8 e2 = 8 - 2x1 - x2
x2 + e3 = 4 e3 = 4 - x2

Pour la solution de base où x1 et x2 sont égales à zéro,

on a Z = 0 puisque :
Max Z = 2 x1 + 3 x2
Cette solution est une solution de base admissible puisque
2 variables sont nulles et que les 5 variables sont non négatives.
08
Pivot et changement de solution

1 1 1 0 0 5 e1 = 5 - x1 - x2
2 1 0 1 0 8 e2 = 8 - 2x1 - x2
0 1 0 0 1 4 e3 = 4 - x2

Si on effectue un pivot sur cet élément

1 0 1 0 -1 1 e1 = 5 - x1 + e3

2 0 0 1 -1 4 e2 = 4 - 2x1 + e3

0 1 0 0 1 4 x2 = 4 - e3

09
Système d’équations linéaires

1 0 1 0 -1 1 e1 = 1 - x1 + e3

2 0 0 1 -1 4 e2 = 4 - 2x1 + e3

0 1 0 0 1 4 x2 = 4 - e3

Si on pose x1 et e3 égales à zéro, on obtient une solution de base

admissible.

10
Système d’équations linéaires

1 0 1 0 -1 1 e1 = 1 - x1 + e3

2 0 0 1 -1 4 e2 = 4 - 2x1 + e3

0 1 0 0 1 4 x2 = 4 - e3

Si on exprime Z en fonction des variables hors-base on obtient :

Z = 2 x1 + 3 x2 = 2 x1 + 3 (4 - e3 ) = 12 + 2 x1 -3 e3

11
Z = 12 + 2 x1 -3 e3 (*)

Lorsque x1 et e3 sont égales à zéro on obtient une solution

de base admissible et la valeur de cette solution est Z = 12.

De l’équation (*), on observe toutefois que si la valeur de

la variable x1 augmente, alors la valeur de Z augmentera.

On peut donc conclure que la solution de base admissible

actuelle n’est pas la solution optimale!

12
Un autre pivot et une autre solution !!!

1 1 1 0 0 5 e1 = 5 - x1 - x2
2 1 0 1 0 8 e2 = 8 - 2x1 - x2
0 1 0 0 1 4 e3 = 4 - x2

Si on effectue un pivot sur cet élément

1 1 1 0 0 5 x 2 = 5 - x 1 - e1

1 0 -1 1 0 3 e2 = 3 - x1 + e1

-1 0 -1 0 1 -1 e3 = -1 + x1 + e1

13
1 1 1 0 0 5 x 2 = 5 - x 1 - e1

1 0 -1 1 0 3 e2 = 3 - x1 + e1

-1 0 -1 0 1 -1 e3 = -1 + x1 + e1

Si x1 et e1 sont deux variables hors-base et lorsqu’elles sont

égales à zéro on obtient une solution de base non
admissible car e3 = -1.

On ne peut pas faire des pivots sur tous

les éléments!

14
Tableau du simplexe et
introduction à l’algorithme du simplexe

15
Méthode du simplexe

Solution initiale

Solution Oui
optimale ? Fin
Non

Variable entrante

∅
Variable sortante Fin

Pivot
16
Description du tableau du simplexe

Max 2 x1 + 3 x2

x1 + x2 + e1 = 5

2x1 + x2 + e2 = 8

x2 + e3 = 4

x 1, x2, e1 , e2 , e3 ≥ 0

Base 2 3 0 0 0
Coeff Var x1 x2 e1 e2 e3 Valeur
0 e1 1 1 1 0 0 5
0 e2 2 1 0 1 0 8
0 e3 0 1 0 0 1 4
zj 0 0 0 0 0
0
cj - zj 2 3 0 0 0 17
Description du tableau du simplexe