La programmation linéaire
Par Andrea • 4 Décembre 2018 • 1 519 Mots (7 Pages) • 453 Vues
...
1ère étape : écrire le système sous forme standard
Il s’agit de convertir le programme établi sous forme canonique (système d’inéquation) ; sous la forme standard c-à-d système d’équation avec variables d’écarts.
Forme canonique Forme standard
Max Z = 25x1 + 15 x2 e1,e2, représentent les variables d’écart
Sous 2x1+2x2 ≤ 240 2x1+2x2+ e1 = 240
3x1 + x2 ≤ 140 3x1 + x2 + e2=140
Max Z = 25x1 + 15 x2 25x1 + 15 x2
x1 ≥ 0, x2 ≥ 0
2ème étape : construire le premier tableau correspondant à la forme standard
[pic 4][pic 5]
x1 x2 e1 e2 fonction second membre ou 2ème membre[pic 6]
e1 2 2 1 0 240
e2 3 1 0 1 140[pic 7]
Max 25 15 0 0 0
Fonction
Objectif
3ème étape : choisir les variables à introduire dans la base ; pour cela choisir le coefficient le plus grand de la fonction objectif ou (économique).
Le coefficient de la fonction objectif le plus grand est : 25 ; donc c’est la variable x1 qui rentre dans la base.
4ème étape : choisir la variable à enlever de la base (rapport : second membre /coefficient de la variable choisi) : retenir le plus faible.
On a :
240/2 ˃ 140/3, donc e2 sort de la base et sera remplacé par x1.
et le le pivot = 3.
5ème étape : encadrer le pivot
[pic 8][pic 9]
x1 x2 e1 e2 2ème membre[pic 10]
e1 2 2 1 0 240
x1 3 1 0 1 140[pic 11][pic 12][pic 13][pic 14][pic 15]
Max 25 15 0 0 0
6ème étape : Diviser la ligne du pivot par la valeur du pivot ; ou multiplier la ligne du pivot par le rapport (1/ valeur du pivot).
x1 x2 e1 e2 2ème membre[pic 16][pic 17][pic 18]
e1
x1 1 1/3 0 1/3 140/3[pic 19]
Max
7ème étape : calculer les valeurs des autres lignes
[pic 20]
Eij : coefficient à transformer.
Aij : coefficient de la ligne du pivot.
Cette opération consiste à transformer Eij des autres lignes en E’ij, nous effectuons un calcul matriciel
Calcule de la 1ère ligne :
(e1, x1) = 2 - [(2/3) * 3] = 0.
(e1, x2) = 2 - [(2/3) * 1] = 4/3.
(e1, e1) = 1 - [(2/3) * 0] = 1.
(e1, e2) = 0 - [(2/3) * 1] = -2/3.
(e1, 2ème membre) = 240 - [(2/3) * 140] = 440/3.
Calcule de la 2ère ligne : il est fait c’est la ligne pivot ; on a divisé la ligne du pivot par la valeur du pivot étape 6.
Calcule de la 3ère ligne :
(Max, x1) = 25 - [(25/3)*3] = 0.
(Max, x2) = 15 - [(25/3)*1] = 20/3.
(Max, e1 ) = 0 - [(25/3)*0] = 0.
(Max, e2) =0 - [(25/3)*1] = -25/3.
(Max, 2ème membre) =- [(25/3)*140] = -3500/3.
[pic 21][pic 22]
x1 x2 e1 e2 2ème membre[pic 23]
e1 0 4/3 1 -2/3 440/3
x1 1 1/3 0 1/3 140/3[pic 24]
Max 0 20/3 0 -25/3 -3500/3
8ème étape : les coefficients de la fonction objectif Max, sont ils tous nuls ou négatifs ?
Si oui : nous sommes à l’optimum ; si non nous effectuons un nouveau calcul.
Les coefficients de la fonction objectif Max, ne sont pas tous nul, il convient d’effectuer un nouveau calcul.
3ème étape : choisir les variables à introduire dans la base ; pour cela choisir le coefficient le plus grand de la fonction objectif ou (économique).
Le coefficient de la fonction objectif le plus grand est : 20/3 ; donc c’est la variable x2 qui rentre dans la base.
4ème étape : choisir la variable à enlever de la base (rapport : second membre /coefficient de la variable choisi) : retenir le plus faible.
On a :
[(440/3) / ( 4/3)]
110 e1 sort de la base et sera remplacé par x2.
Et le pivot = 4/3.
5ème étape : encadrer le pivot
[pic 25][pic 26]
x1 x2 e1 e2 2ème membre[pic 27][pic 28][pic 29][pic 30]
e1 0 4/3 1 -2/3 440/3[pic 31]
x1 1 1/3 0 1/3 140/3[pic 32]
Max 0 20/3 0 -25/3 -3500/3
6ème étape : Diviser la ligne du pivot par la valeur du pivot ; ou multiplier la ligne du pivot par le rapport (1/ valeur du pivot).
[pic 33][pic 34]
x1 x2 e1 e2 2ème membre[pic 35]
x2 0 1 3/4 -1/2 110
...