TP : Optimisation.
Université de Med Boudiaf M’sila Année Universitaire 2016/2017
Faculté des Technologies Option : Fabrication et Construction
Département de Génie Mécanique Master 1ère Année
TP 4 : Résolution d’un problème d’optimisation
linéaire avec contraintes.
4.1 Introduction :
Généralement un programme linéaire est représenté sous la forme suivante :
Avec :
A : matrice des contraintes d’inégalité ;
B : matrice des contraintes d’égalité ;
c : le vecteur des coefficients de la fonction objet ;
a : le vecteur des contraintes d’inégalité ;
b : le vecteur des contraintes d’égalité ;
lb : la borne inférieure de x ;
ub : la borne supérieure de x.
4.2 Comment résoudre un PL en Matlab
Pour résoudre un problème linéaire en Matlab on a plusieurs syntaxes. Ou utilise la fenêtre du
MATLAB ou bien l'outil d'optimisation. On commence avec la première méthode ensuite la
deuxième méthode.
On a trois formes possibles comme illustré sur les exemples suivants :
La première forme :
Résoudre un problème linéaire simple définit uniquement par les contraintes d’inégalités, il est
donné par :
x = linprog(f,A,b)
Cela signifie; trouver le minimum de la fonction f (min f) sachant qu’il satisfit les contraintes
d’inégalités données par la relation suivante: A*x ≤ b. illustrant cela par l’exemple suivant :
Les contraintes sont :
1
TP : Optimisation.
Et la fonction objet : .
Ecrivant la matrice des contraintes d’inégalité comme suit :
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
Le vecteur des contraintes d’inégalités :
b = [2 1 2 1 -1 2];
La function objet:
f = [-1 -1/3];
Solvant le programme linéaire en utilisant l’instruction linprog comme suit.
x = linprog(f,A,b)
Optimal solution found.
x=
0.6667
1.3333
Remarque:
Si on veut afficher la solution optimale et la valeur de la fonction objet pour cette solution, on écrit :
[x,fval] = linprog(f,A,b)
Optimal solution found.
x=
0.6667
1.3333
fval = -1.1111
2
TP : Optimisation.
La deuxième forme :
Résoudre un problème linéaire définit par les contraintes d’inégalités et d’égalités, il est donné
par :
x = linprog(f,A,b,Aeq,beq)
Cela indique; trouver le minimum de la fonction f (min f) sachant qu’il satisfit les contraintes
d’inégalités données par la relation suivante: A*x ≤ b et les contraintes d’égalités Aeq*x = beq . Un
l’exemple illustratif est donné par :
Les contraintes d’inégalités sont :
Donc la matrice des contraintes d’inégalités A est égale à :
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
Le vecteur des contraintes d’inégalités b est donné par:
b = [2 1 2 1 -1 2];
Utilisant la contrainte d’égalité suivante: .
La matrice des contraintes d’égalités Aeq est égale à :
Aeq = [1 1/4];
Le vecteur des contraintes d’égalités est donné par :
beq = 1/2;
Soit la fonction objet suivante: .
f = [-1 -1/3]
Résolvant ce programme linéaire, en écrivant l’instruction suivante :
x = linprog(f,A,b,Aeq,beq)
La solution optimale trouvée est :
x= 0
2
La troisième forme :
Résoudre un problème linéaire définit par les contraintes d’inégalités, d’égalités et limitant la
variable x par une limite supérieure et une limite inférieure : lb ≤ x ≤ ub, il est donné par :
3
TP : Optimisation.
x = linprog(f,A,b,Aeq,beq,lb,ub)
Cela indique; trouver le minimum de la fonction f (min f) sachant qu’il satisfit les contraintes
d’inégalités données par la relation suivante: A*x ≤ b, les contraintes d’égalités Aeq*x = beq et la
variable x est comprise entre lb et ub : lb ≤ x ≤ ub .
Remarque :
Si on n’a pas de contraintes d’égalités on écrit :
Aeq = [] et beq = [].
Un exemple illustratif est donné par :
Les contraintes d’inégalités sont :
Donc la matrice des contraintes d’inégalités A est égale à :
A = [1 1
1 1/4
1 -1
-1/4 -1
-1 -1
-1 1];
Le vecteur des contraintes d’inégalités b est donné par:
b = [2 1 2 1 -1 2];
Utilisant la contrainte d’égalité suivante: .
La matrice des contraintes d’égalités Aeq est égale à :
Aeq = [1 1/4];
Le vecteur des contraintes d’égalités est donné par :
beq = 1/2;
Les limites des variables x(1) et x(2) sont données par :
Donc les bornes inferieures et supérieures sont données par :
lb = [-1,-0.5];
ub = [1.5,1.25];
Soit la fonction objet suivante: .
f = [-1 -1/3]
Résolvant ce programme linéaire, en écrivant l’instruction suivante :
x = linprog(f,A,b,Aeq,beq,lb,ub)
La solution optimale trouvée est :
x=
0.1875
1.2500
4
TP : Optimisation.