33 0 589KB
UNIVERSITE SIDI MOHAMMED BENABDELLAH
G GII
FACULTE DES SCIENCES ET TECHNIQUES DE FES
Travaux pratiques Matlab Recherche opérationnelle
COMPTE RENDU
REALISE PAR : BELHOUSSINE LAYLA
ENCADRER PAR : Mme.MOUNA.ABAR KAN
SOMMAIRE I-
Introduction…………………………………………………………………………………
II-
Algorithme de simplexe ……………………………………………………………….
III-
Méthode de simplexe sur Matlab…………………………………..……………. III-1 Ecriture de code sur Matlab……………………………………………………. III-2 Exemple d’application……….……………………………………………………. III-2-a Maximisation…….…………………………………………………………………. III-2-b Maximisation par la méthode de grand M……………..…………….. III-2-c Minimisation………………………………………………………………………….
IV-
Conclusion…………………………………………………………………………………….
I-
INTRODUCTION :
La méthode du simplexe a été présentée pour résoudre un programme linéaire dans lequel on cherche à maximiser une relation économique dite fonction objective de plusieurs variables sous certaines contraintes. Il a été mis au point par le mathématicien américain George Dantzig Il s'agit d'une méthode itérative qui consiste à examiner les sommets du polyèdre des contraintes permettant d'augmenter la fonction objective. La méthode du simplexe a été mise en œuvre de deux façons différentes, d'une part en utilisant les dictionnaires et d'autre part avec une méthode des tableaux consistant à mettre à jour l'inverse de la matrice de base des contraintes. Il a été mis au point par le mathématicien américain George Dantzig
L’objectif du TP est de mettre en pratique cette méthode en utilisant le logiciel MATLAB.
Définition du Matlab : Matlab est considéré actuellement Parmi les logiciels les plus convoités et les plus recherchés. Son aspect scientifique trouve des applications dans plusieurs champs disciplinaires touchant les sciences de l’ingénieur comme l’électronique, la mécanique. On trouve également des applications dans les domaines des statistiques, des finances et même de la biologie. Pour notre part nous appliquons Matlab en traitement du signal. Un intérêt particulier est donné à l’analyse et à la synthèse des filtres par Sptool. Une dernière partie est réservée à Simulink avec plusieurs exemples d’application.
II-
Algorithme de simplexe :
Voici l’algorithme du simplexe revisité :
Non
Oui
Y a-t-il de variables artificielles ?
Méthode des deux phases
Méthode de simplexe
Elaboration du premier tableau pour la minimisation de l’addition des variables artificielles
Elaboration du premier tableau
Oui
Oui
Condition d’arrêt ?
Condition d’arrêt ? Non
Non
Choix de la variable entrante
Choix de la variable entrante
Choix de la variable sortante
Choix de la variable sortante
Actualiser le tableau
Actualiser le tableau
Oui
Retour résultat
Supprimer les colonnes des V.A
Fonction objectif=0 ?
Non
Pas de solution
III-
Méthode simplexe sur Matlab
III-1 Ecriture de code sur Matlab : Le code ci-dessous permet d’étudier la maximisation et la minimisation d’un programme linéaire.
III-2 Exemple d’application : III-2-a Maximisation : Soit le programme linéaire suivant :
Max Z = 25x1+15x2 S.C 2x1+2x2 ≤ 240 3x1+x2≤140 x1,x2≥0
Après avoir exécuté le code sur Matlab, le programme nous demande d'abord de saisir les coefficients de la fonction objectif comme le montre la figure
Ensuite le programme nous demande de saisir les types de contraintes qu’on a dans le programme linéaire et il s’affiche 2 fois puisqu’on a 2 contraintes
Après il nous demande d’entrer la matrice des contraintes.
L’étape suivante nous permet d’entrer les valeurs qu’on a dans les contraintes
Et enfin le programme fait les calculs et nous donne la valeur maximale
Voilà le résultat affiché dans commande window par le programme
A la fin le programme affiche les résultats ci-dessous : X2 =110
X1=10
Max (x1 + 2x2)= 10+ (15*110)= 1900
III-2-b Maximisation par la méthode de grand M :
Soit le programme linéaire suivant : MaxZ= 3x1+x2 S.C -x1+x2≥1 x1+x2≥ 3 2x1+x2≤4 x1,x2≥ 0
Nous suivrons les mêmes étapes que pour le programme précédent mais ici, le programme appliquera la méthode de grand M et introduira des variables artificielles par lui-même.
Etape 1
Etape 2
Etape 3
Etape 4
Résultat final
Voilà le résultat affiché dans command Window par le programme
On remarque que le programme introduit par lui-même des variables artificielles pour résoudre le problème.