Matlab Simplexe [PDF]

Zitiervorschau

BOUSEBA BADREDDINE – 4EME AUTOMATIQUE – 2018/2019 REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEITGNEMNT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE ECOLE NATIONALE POLYTECHNIQUE DE CONSTANTINE DEPARTEMENT EEA

COMPTE RENDU ~ OPTIMISATION ET RECHERCHE OPERATIONNELLE ~

‘TP 06’ SIMPLEXE

Encadré par :

Réalisé par :

Professeur Samir LADACI [email protected]

Badreddine BOUSEBA [email protected]

2ème Année Cycle Ingénieur Option Automatique Semestre II

Année Universitaire : 2018/2019

Page | 1

BOUSEBA BADREDDINE – 4EME AUTOMATIQUE – 2018/2019 I/ Introduction : L'algorithme du simplexe est un algorithme de résolution des problèmes d'optimisation linéaire. Il a été introduit par George Dantzig à partir de 1947. C'est probablement le premier algorithme permettant de minimiser une fonction sur un ensemble défini par des inégalités1. De ce fait, il a beaucoup contribué au démarrage de l'optimisation numérique. L'algorithme du simplexe a longtemps été la méthode la plus utilisée pour résoudre les problèmes d'optimisation linéaire.

II/ But du TP : Apprendre à comprendre la méthode, et suivre le bon raisonnement pour l’implémentation de cette méthode sur ordinateur pour permettre à l’utilisateur de trouver directement la solution en insérant les matrices nécessaires Il est demandé également de faire un organigramme, et un code Matlab bien détaillé.

Page | 2

BOUSEBA BADREDDINE – 4EME AUTOMATIQUE – 2018/2019 IV/ Organigramme : Début

Déclaration : A : Matrice des contraintes B : vecteur des contraintes C : fonction objective

Dictionnaire initiale

Vérification des coefficients positifs

Exists ?

Non

Oui Colonne Pivot Ligne Pivot Division de la ligne par le pivot Calcule des nouveaux coefficients

Afficiher le dictionnaire

Afficher la valeur optimale ainsi que les coefficients

Fin

Page | 3

BOUSEBA BADREDDINE – 4EME AUTOMATIQUE – 2018/2019 V/ Programmation sous Matlab : Voir les commentaires sous Matlab pour l’ explication de chaque étape utilisée. clear all; close all; clc A=input('Entrez b=input('Entrez c=input('Entrez [n,m]=size(A); D=[A eye(n) b;c H=D(n+1,:); for p=1:n+m if H(p)>0 break end end while p~=n+m ||

la matrice des contraintes A\n'); le vecteur b des contraintes\n'); le vecteur c ligne de la fonction objective\n'); zeros(1,n+m+1-length(c))];

H(n+m)>0

l=D(:,n+m+1)./D(:,p); for j=1:n if l(j)0 break end end D end disp('La valeur de Z optimal est') [nd,md]=size(D); disp(-1*D(nd,md))

Page | 4

BOUSEBA BADREDDINE – 4EME AUTOMATIQUE – 2018/2019 Affichage de l’exécution sous Matlab :

VI/ Conclusion : Ce TP m’a permis de bien raisonner en ce qui concerne des algorithmes mathématiques de complexité moyenne. La résolution mathématique est relativement facile mais l’implémentation sur ordinateur nécessite un peu de réflexion. En termes d’optimisation, j’ai arrivé à programmer l’une des méthodes très utilisées pour la recherche opérationnelle.

Page | 5