Mini-projet de Recherche Oprationnelle
Mthode simplexe & mthode de DJIKSTA24/04/2012 RALIS PAR :
LABZAR Fadoua, SMOUH Mohamed Amine & SENHAJI Hamza OPTION :
MCQ
Mini-projet de Recherche Oprationnelle cole Nationale de
lIndustrie Minrale
2011/2012
Mthode simplexe
Ralis par : LABZAR Fadoua, SMOUH Mohamed Amine & SENHAJI
Hamza Encadr par : Mr ELBAHJA
Page 2
Mini-projet de Recherche Oprationnelle cole Nationale de
lIndustrie Minrale
2011/2012
Introduction:Loptimisation est devenue une ncessit de nos jours
.Afin de rduire les frais et de rpondre le plus vite possible aux
attentes et aux exigences de plus en plus pointues des clients, il
est aujourdhui impratif de savoir optimiser au mieux les diffrents
paramtres qui conditionnent notre travail et notre productivit. Il
sagit dune mthode danalyse scientifique du problme pos, mthode
particulirement tourn vers la recherche de la meilleure faon de
faire dapprhender les faits, et de prendre des dcisions
susceptibles de dboucher sur des meilleurs rsultats .Elle se sert,
entre autres, de sciences exactes et de sciences humaines.
Signalons cet gard : 1- La part croissante des mathmatiques avec la
thorie des systmes, les diffrentes mthodes doptimisation, et les
mthodes statistiques; 2- Lconomie, plus particulirement lconomie et
organisation des entreprises et lanalyse conomique; 3-
Linformatique avec des nombreuses applications. On peut dire, pour
lessentiel, que les problmes traits par la recherche oprationnelle
se rsument en problme de types combinatoire (difficult dnumration
de toute les solutions possibles partir dun certain seuil et sous
certaines conditions), alatoires (dcisions dans lincertain) et
concurrentiels (prise de dcision dans le duel ou situation de
concurrence dans laquelle il faut faire face aux diverses stratgies
de ladversaire).
But :Le but de cette mthode est de trouver la solution d'un
problme de minimisation.
Analyse du problme:Nous allons faire une programmation de
lalgorithme Simplexe dans le cas gnral :
Min CT.X A.X < B X>0
Ralis par : LABZAR Fadoua, SMOUH Mohamed Amine & SENHAJI
Hamza Encadr par : Mr ELBAHJA
Page 3
Mini-projet de Recherche Oprationnelle cole Nationale de
lIndustrie Minrale
2011/2012
La mthode du simplex consiste passer dune solution de base
admissible une autre solution de base admissible en amliorant la
fonction objective. On dmarre d'une solution de base admissible
quelconque. En introduisant les variables dcart le problme linaire
deviendra de la forme suivante : Min( Z= c1x1+c2x2+.+cnxn)
a11x1+a12x2+.+a1nxn+s1=b1 a21x1+a22x2+.+a2nxn+s2=b2 . . .. ..
an1x1+an2x2+.+annxn+sn=bn xi 0 ; i=1 ;2 ;. ;n
On choisit parmi les variables hors base, la variables xq, telle
que : q=Min(i ; i=1 ;2 ;.. ;n) avec i =ci-zi
On dtermine parmi les variables de base la variable sortante xp
telle que: (bp/apq)=Min{ bi/aiq ; i=1 ;2 ;.. ;n} On limine xq par
pivotage (limination de Gauss): 1. diviser la contrainte p par le
pivot xpq 2. modifier la contrainte i, pour tout i p , en
remultipliant la contrainte p par aiq et en la soustrayant de la
contrainte i 3. modifier la fonction conomique en remultipliant la
contrainte p par cq et en la soustrayant de l'expression de z. La
solution optimale est atteinte lorsque tous les i sont 0.
Ralis par : LABZAR Fadoua, SMOUH Mohamed Amine & SENHAJI
Hamza Encadr par : Mr ELBAHJA
Page 4
Mini-projet de Recherche Oprationnelle cole Nationale de
lIndustrie Minrale
2011/2012
Programme principal :Le programme en langage C, se prsente ainsi
:
#include #include #include #include #include #include #include
#include int resolutionSimplexe(); float a,b,c; int
pl_aps_entrant(double a[6][6],int hb[6],int m,int n,int phase) {
int i,j,k,l; double d,s,max; k=0; max=0.0; if(phase==2)l=0; else
l=m+1; for(j=1;j0)&&(hb[j]!=n+m)) { for(i=1;imax) {
max=d;
Ralis par : LABZAR Fadoua, SMOUH Mohamed Amine & SENHAJI
Hamza Encadr par : Mr ELBAHJA
Page 5
Mini-projet de Recherche Oprationnelle cole Nationale de
lIndustrie Minrale
2011/2012
k=j; } } } return(k); } int pl_aps_sortant(double a[6][6],int
m,int k) { int i,l; double rap,min; min=1e308; l=0; for(i=1;i0) {
rap=a[i][0]/a[i][k]; if(rap
