TP Recherche Opérationnelle Méthode du Simplexe · PDF filePréface : Le Simplexe est un des algorithmes fondamentaux pour la résolution des programmes linéaires, dont notamment

A. Taik TP SIMPLEXE RO-FI-GPE
Dpartement de Mathmatiques FST-Mohammedia (2006)
1
TP Recherche Oprationnelle
Mthode du Simplexe
Prface : Le Simplexe est un des algorithmes fondamentaux pour la rsolution des programmes linaires, dont notamment les problmes conomiques. Il a t mis au point par le mathmaticien amricain George Dantzig en 19471. Ainsi, lalgorithme permet de maximiser ou minimiser une relation conomique dite fonction objective de plusieurs variables sous certaines contraintes. Lobjectif du TP est de mettre en pratique cette mthode en utilisant le logiciel MATLAB.

2
INTRODUCTION :
La recherche oprationnelle (RO) vise l'amlioration du fonctionnement des entreprises et des organismes publics par l'application de l'approche scientifique. Reposant sur l'utilisation de mthodes scientifiques, de techniques spcialises et des ordinateurs, la RO permet d'obtenir une valuation quantitative des politiques, stratgies et actions possibles dans le cours des oprations d'une organisation ou d'un systme.
La RO est apparue en Grande-Bretagne durant la Seconde Guerre mondiale, lorsqu'on dcida d'employer des mthodes scientifiques pour tudier divers aspects des oprations militaires. Depuis lors, la RO est devenue un lment important du processus de prise de dcision dans de nombreux contextes commerciaux, industriels et gouvernementaux, car elle permet d'apprhender de faon systmatique la complexit toujours grandissante des problmes de gestion auxquels est confront tant le secteur priv que public.
la suite des succs obtenus dans le domaine militaire durant la Seconde Guerre mondiale, la RO a t applique durant de nombreuses annes des problmes de nature oprationnelle dans l'industrie et le secteur public. Depuis une dizaine d'annes, le champ d'application de la RO s'est largi des domaines comme l'conomie, la finance, le marketing et la planification d'entreprise. Plus rcemment, la RO a t utilise pour la gestion des systmes de sant et d'ducation, pour la rsolution de problmes environnementaux et dans d'autres domaines d'intrt public. Les principaux utilisateurs de la RO au Canada sont les entreprises de fabrication, de distribution et de commerce au dtail dans les secteurs miniers, de l'nergie, du transport et de la construction, les entreprises de service comme les banques, ainsi que de nombreux organismes gouvernementaux.

3
I Rsolution des programmes
linaires A laide de la
mthode graphique (drawfr):

4
La fonction DRAWFR : function drawfr(c, A, rel, b) % Graphs of the feasible region and the line level % of the LP problem with two legitimate variables % % min (max)z = c*x % Subject to Ax = b), % x >= 0 clc [m, n] = size(A); if n ~= 2 str = 'Number of the legitimate variables must be equal to 2'; msgbox(str,'Error Window','error') return end t = extrpts(A,rel,b); if isempty(t) disp(sprintf('\n Empty feasible region')) return end t = t(1:2,:); t = delcols(t); d = extrdir(A,rel,b); if ~isempty(d) msgbox('Unbounded feasible region','Warning Window','warn') disp(sprintf('\n Extreme direction(s) of the constraint set')) d disp(sprintf('\n Extreme points of the constraint set')) t return end t1 = t(1,:); t2 = t(2,:); z = convhull(t1,t2); hold on patch(t1(z),t2(z),'r') h = .25; mit1 = min(t1)-h; mat1 = max(t1)+h;

5
mit2 = min(t2)-h; mat2 = max(t2)+h; if c(1) ~= 0 & c(2) ~= 0 sl = -c(1)/c(2); if sl > 0 z = c(:)'*[mit1;mit2]; a1 = [mit1 mat1]; b1 = [mit2 (z-c(1)*mat1)/c(2)]; else z = c(:)'*[mat1;mit2]; a1 = [mit1 mat1]; b1 = [(z-c(1)*mit1)/c(2) mit2]; end elseif c(1) == 0 & c(2) ~= 0 z = 0; a1 = [mit1 mat1]; b1 = [0,0]; else z = 0; a1 = [0 0]; b1 = [mit2 mat2]; end h = plot(a1,b1); set(h,'linestyle','--') set(h,'linewidth',2) str = 'Feasible region and a level line with the objective value = '; title([str,num2str(z)]) axis([mit1 mat1 mit2 mat2]) h = get(gca,'Title'); set(h,'FontSize',11) xlabel('x_1') h = get(gca,'xlabel'); set(h,'FontSize',11) ylabel('x_2') h = get(gca,'ylabel'); set(h,'FontSize',11) grid hold off

6
LA RESOLUTION DES PROGRAMME LINEAIRE DE LA SERIE DES EXERCICES :
Programme n1 :
Max Z= X+3Y
2X+3Y

7
x(1)= 0.000000 x(2)= 4.000000 Objective value at the optimal point: z= 12.000000
Programme n2:
Max Z= 7X+5Y
X

8
Problem has a finite optimal solution Values of the legitimate variables: x(1)= 200.000000 x(2)= 300.000000 Objective value at the optimal point: z= 2900.000000
Le programme n3
Max Z= 9X+3Y
5X+Y>=180
5X+Y>=110
X, Y>=0
Le programme dans lditeur de Matlab est : clear
c=[9 3];
A=[5 1;5 1];
rel='>>';
b= [180;110]
drawfr(c, A, rel, b)
Unbounded optimal solution with z= Inf
Le programme n4:
Max Z= 12X+20Y
-3 /2*X+Y

9
c=[12;20];
A=[-3/2 1;1 -3/2;1 5/6;1 0;0 1];
rel='

10
Le programme n5:
Max Z= X+2Y
X+3Y>=12
2X+Y>=14
4X+Y>=8
X, Y>=0
c=[1 2];
A=[1 3;2 1;4 1];
rel='>>>';
b=[12;14;8]
drawfr(c, A, rel, b)
Problem has a finite optimal solution Values of the legitimate variables: x(1)= 6.000000 x(2)= 2.000000 Objective value at the optimal point: z= 10.000000
Le programme n6:
Max Z= 5X+7Y
2X+Y

11
c=[5 7];
A=[2 1;2 -1;-4 5];
rel='

12
II Rsolution des programmes linaires
A laide du simplex2P.m:

13
LA FONCTION SIMPLEX2P:
function simplex2p(type, c, A, rel, b) % The Two-Phase Method for solving the LP problem % min(or max) z = c*x % Subject to Ax rel b % x >= 0 % The input parameter type holds information about type of the LP % problem to be solved. For the minimization problem type = 'min' % and for the maximization problem type = 'max'. % The input parameter rel is a string holding the relation signs. % For instance, if rel = '', then the constraint system consists % of one inequality =. if (type == 'min') mm = 0; else mm = 1; c = -c; end b = b(:); c = c(:)'; [m, n] = size(A); n1 = n; les = 0; neq = 0; red = 0; if length(c) < n c = [c zeros(1,n-length(c))]; end for i=1:m if(rel(i) == '') A = [A -vr(m,i)]; else neq = neq + 1; end

14
end ncol = length(A); if les == m c = [c zeros(1,ncol-length(c))]; A = [A;c]; A = [A [b;0]]; [subs, A, z, p1] = loop(A, n1+1:ncol, mm, 1, 1); disp(' End of Phase 1') disp(' *********************************') else A = [A eye(m) b]; if m > 1 w = -sum(A(1:m,1:ncol)); else w = -A(1,1:ncol); end c = [c zeros(1,length(A)-length(c))]; A = [A;c]; A = [A;[w zeros(1,m) -sum(b)]]; subs = ncol+1:ncol+m; av = subs; [subs, A, z, p1] = loop(A, subs, mm, 2, 1); if p1 == 'y' disp(' End of Phase 1') disp('

Documents

TP Recherche Opérationnelle Méthode du Simplexe · PDF filePréface : Le Simplexe est un des algorithmes fondamentaux pour la résolution des programmes linéaires, dont notamment