La programmation linéaire

Programmation linéaire

I/ Représentation graphique :

1/ Formulation du modèle mathématique linéaire :

La formulation du modèle mathématique est l’étape la plus délicate de la résolution d’un problème, elle nécessite un effort de conception qui doit aboutir à la détermination des 3 éléments suivants :

1-Les variables de décision pour lesquelles on doit décider du niveau à atteindre, tel que le niveau d’activité dans l’entreprise par exemple, on suppose dans un premier temps que ces variables peuvent prendre n’importe quelle valeur positive.

2-La fonction objectif qui décrit la relation linéaire représentant l’objectif de l’entreprise, à l’aide des variables de décision.

3-Les contraintes du modèle qui décrivent les relations linéaires entre les variables de décision représentant les restrictions auxquelles est sujette l’entreprise.

*Exemple 1 :

Une compagnie XYZ est spécialisée dans la production de 2 types de produits : des climatiseurs et des ventilateurs, les 2 produits nécessitent un certain nombre d’heures machine et un certain nombre d’heures de main d’œuvre.

Le tableau suivant donne l’information nécessaire sur les deux produits, c-à-d les nombres d’heures machine et d’heures main d’œuvre nécessaire à la fabrication d’une unité de chacun de ces produits,  ainsi que le profit généré par la production d’une unité de ce produit.

-On utilisera comme unité monétaire UM  le dinar : DA.

Le tableau nous donne le nombre total d’heures machines et d’heures main d’œuvre disponibles :

Solution :

1*Formulation du programme linéaire :

1-variable de décision : la compagnie veut décider du nombre de climatiseurs et du nombre de ventilateurs à produire pour maximiser le profit, ceci nous amène à choisir les deux variables de décision suivantes :

X1 : nombre de climatiseurs.

X2 : nombre de ventilateurs.

2-fonction objectif : l’objectif de l’entreprise est de déterminer le programme de production qui maximisera son profit, la fonction objectif s’écrit :

Max Z =  25x1 + 15 x2

3-contrainte du modèle : la limitation des ressources contraint l’entreprise de la manière suivante :

1/ contrainte heures machine     2x1+2x2 ≤  240

2/ contrainte main d’œuvre       3x1 + x2 ≤ 140

3/ contrainte de non-négativité :   x1 ≥ 0, x2 ≥ 0

*Modèle complet :

X1 : nombre de climatiseurs.

X2 : nombre de ventilateurs.

     Max Z =  25x1 + 15 x2

Sous    2x1+2x2 ≤  240

3x1 + x2 ≤ 140

x1 ≥ 0, x2 ≥ 0

*Remarque :

-Les fonctions représentant l’objectif et les contraintes sont toutes des applications linéaires de R dans R.

-une solution est dite réalisable si elle vérifie toutes les contraintes, et dite optimale si elle un meilleur profit.

2*Technique de résolution graphique :

1-Représenter les lignes de contraintes et l’ensemble des solutions réalisables :

On dessine les droites :

2x1+2x2 =  240    (D1)

3x1 + x2 = 140  (D2)

[pic 1]

Fig.1 Ensembles des solutions réalisables.

2-Localiser la solution optimale :

[pic 2]

Fig.2 Localisation de la solution optimale.

-C’est dans la zone d’intersection des deux droites (D1) et (D2).

3-Calculer la solution optimale :

Graphiquement de la Fig.2, on peut localiser la solution optimale, elle correspond au point d’intersection  B des deux droites (D1) et (D2) d’équations respectives :

2x1+2x2 =  240    (D1)

3x1 + x2 = 140  (D2)

Donc : x1= 10, x2= 110, Z*= 1900.

II/ Méthodes du simplexe :

II/ Méthodes du simplexe :

Définition :

La méthode du simplexe est un algorithme de recherche d’une solution optimale d’un programme linéaire donné.

La mise en œuvre de la méthode du simplexe peut être divisée en trois grandes parties :

1ere : mettre le modèle sous forme standard en y introduisant des variables d’écart qui ont pour rôle de transformer les inégalités en égalités.

2eme : établir le premier tableau de simplexe (tableau à l’origine).

3eme : procéder à une série d’itérations sur les tableaux de simplexe aboutissant à la solution optimale.

*La résolution par l’algorithme du simplexe se déroule selon 8 étapes avant un nouveau passage :

[pic 3]

Application :

Nous reprenons l’exemple précédent résolu graphiquement, la résolution par la méthode du simplexe se déroule comme suite :

...