22 #define TRACE RR->ntrace
23 #define A(i,j) RR->a[i][j]
33 #define TESTP RR->testp
35 #define COPIE RR->copie
39 #define VRESULT RR->vresult
41 #define ITEMAX RR->tmax
47 #define CONORM(A) *(RR->pconor+A)
48 #define INFCOL(A) *(RR->pinfcolonn+A)
50 #define VARIABLELIBRE(v) v>NP && v<=N1
51 static float absf(
float vf)
52 {
if (vf<0)
return(-vf) ;
58 if (vf<0) vfp= -vf ;
else vfp= vf ;
60 if (vfp-vi<RR->epss)
return(0) ;
return(1) ;
64 if (
TRACE<2)
return(0) ;
if (
TRACE<3&&v!=30)
return(0) ;
68 if (v==1)
fprintf(
FT,
"situation initiale, contraintes <= , = , >=");
69 if (v==2)
fprintf(
FT,
"forme standard, contraintes <= , =") ;
70 if (v==3)
fprintf(
FT,
"lignes ont ete normalisees") ;
71 if (v==4)
fprintf(
FT,
"colonnes ont ete normalisees") ;
73 if (v==6)
fprintf(
FT,
"forme standard normalisee") ;
74 if (v==7)
fprintf(
FT,
"egalites eliminees, forme canonique <=") ;
76 if (v==8) {
fprintf(
FT,
"methode primale\n") ;
return(0) ; } ;
78 if (v==10)
fprintf(
FT,
"variable artificielle primal introduite") ;
79 if (v==11) {
fprintf(
FT,
"algorithme simplexe primal ph. 1\n");
return(0);};
81 if (v==13) {
fprintf(
FT,
"methode duale\n") ;
return(0) ; } ;
83 if (v==15)
fprintf(
FT,
"variable artificielle phase 1 dual introduite");
84 if (v==16) {
fprintf(
FT,
"algorithme simplexe dual ph. 1\n");
return(0);};
85 if (v==17)
fprintf(
FT,
"ligne artificielle inutile deplacee") ;
86 if (v==18)
fprintf(
FT,
"retour necessaire de dual a primal") ;
89 if (v==30) {
fprintf(
FT,
"pivot(%2d,%2d):%6.3f",i11,j11,1/
A(i11,j11));
90 fprintf(
FT,
" variables %2d <-> %2d",
B[j11],
G[i11]) ; };
94 {
for ( i=0 ; i <=
M1 ; i++)
102 for ( j=1 ; j <=
N1 ; j++)
103 {
if (
A(i,j) == 0) continue ;
105 if (j < 10)
fprintf(
FT,
"%6.3fx%1d ",
A(i,j),j) ;
123 fprintf(
FT,
"variables hors-base toutes de signe quelconque\n") ;
125 (
FT,
"%3d variables hors-base >=0 ,%3d variables libres \n",
NP,
N1-
NP) ;
127 if (
TRACE<4)
return(0) ;
128 if (
TRACE<5 && (v!=1 ) )
return(0) ;
129 if (
TRACE<6 && (v!=1 && v!=6 ) )
return(0) ;
130 if (
TRACE<7 && (v!=1 && v!=6 && v!=30) )
return(0) ;
132 for ( j=0 ; j <=
NB ; j++)
136 for ( i=0 ; i <=
M2 ; i++)
138 for ( j=0 ; j <=
NB ; j++)
161 RR->pconor= &
RR->tconor[1] ;
162 RR->pinfcolonn= &
RR->tinfcolonn[1] ;
166 {
fprintf(
FT,
"%3d contraintes%3d variables%3d variables non-negatives\n",
186 for (ii=0 ; ii<=
M1 ; ii++)
188 for (jj=nvt ; jj>= 1 ; jj--)
189 {
float s; s=
A(ii,jj);
190 if (jj>
NP)
A(ii,jk--)= -s;
199 {
fprintf(
FT,
"resultat simplexe apres %d iterations: ",
ITER) ;
213 {
int jj,jk ;
float xf ;
214 for (jj=0 ; jj<=
N1+
M1 ; jj++)
223 {
fprintf(
FT,
" sans signification pour variables libres:\n");
229 for (jj=1 ; jj<= nvt+mee ; jj++)
231 if (jj>
NP && jj<=nvt)
232 { jk++ ;
if (xf==0) xf= -
X[jk] ;
236 fprintf(
FT,
"resultats probleme initial:\n") ;
237 for (jj=0 ; jj<= nvt+mee ; jj++)
251 {
int bfract, jj ; bfract=0 ;
252 for (jj=0 ; jj<=
N1 ; jj++)
255 {
if (!bfract)
fprintf(
FT,
" variables non entieres: ");
262 else fprintf(
FT,
" certitude variables toutes entieres\n");
264 RR->rfrac=0 ;
if (bfract)
RR->rfrac=1 ;
280 for (j=1 ; j<=
N1 ; j++)
286 for (j=1 ; j<=
N1 ; j++)
A(0,j)=
A(0,j)/s ;
292 for (i=1 ; i<=
M1 ; i++)
311 for (i=0 ; i<=
M1 ; i++)
313 s=
A(i,j1) ;
A(i,j1)=
A(i,
NB) ;
A(i,
NB)=s ;
328 for (j=0 ; j<=
N1 ; j++)
330 s=
A(i1,j) ;
A(i1,j)=
A(
MB,j) ;
A(
MB,j)=s ;
340 for (j=
N1 ; j>=1 ; j--)
345 for (j=
M1 ; j>=1 ; j--)
354 for (i=1 ; i<=
M1 ; i++)
358 for (j=i+1 ; j<=
M1 ; j++)
362 for (j=1 ; j<=
N1 ; j++)
366 if (
G[i]>
N1 &&
G[i]!=
N1+i)
373 for (j=1 ; j<=
N1 ; j++)
377 for (i=j+1 ; i<=
N1 ; i++)
392 s=(i>
M2 ||
G[i]>
N1) ? 1 : 0 ;
393 for (j=
J0 ; j<=nx ; j++)
409 s=(
B[j]>
N1) ? 0 : 1 ;
410 for (i=1 ; i<=mx ; i++)
413 if (
A(i,j) != 0) s=s+
absf(
A(i,j)) ;
419 for (i=1 ; i<=mx ; i++)
422 if (
D[i] != 0) s=s+
absf(
D[i]) ;
442 j=
B[j1] ;
B[j1]=
G[i1] ;
G[i1]=j ;
443 for (i=0 ; i<=mx ; i++)
444 if (i != i1 &&
A(i,j1) !=0)
446 p2=
A(i,j1)*p1 ;
D[i]=
D[i]-
D[i1]*p2 ;
447 if (
RR->sommaire)
if (
absf(
D[i])<
RR->epss)
D[i]=0 ;
448 for (j=
J0 ; j<=nx ; j++)
449 if (j==j1)
A(i,j)= -p2
453 A(i,j)=
A(i,j)-p2*
A(i1,j) ;
455 if (
absf(
A(i,j))<
RR->epss)
A(i,j)=0 ;
460 for (j=
J0 ; j<=nx ; j++)
461 A(i1,j)=(j==j1) ? p1 :
A(i1,j)*p1 ;
462 if (
RR->sommaire)
goto finpivotage ;
470 for (i=0 ; i<=mx ; i++)
473 if (
D[i]*
D[i] <=
INF[i]*s)
D[i]=0 ;
476 for (j=
J0 ; j<=nx ; j++)
482 for (i=0 ; i<=mx ; i++)
485 if (
A(i,j)*
A(i,j) <=
INF[i]*s)
A(i,j)=0 ;
498 float gamma,teta,c1,c2,zeta,tet,
pivot ;
511 *pbool1=1 ; c1=0 ; tet=0 ;
512 for (j=
J0 ; j<=
NB ; j++)
514 teta=(bphase2) ?
A(i2,j) : -
A(i2,j) ;
517 *pbool1=1 ;
pivot=0 ;
518 for (i=1 ; i<=
MB ; i++)
524 || zeta==alpha &&
pivot<
A(i,j))
527 alpha=zeta ; i3=i ;
pivot=
A(i,j) ;
532 if (c2<c1 || c2==c1 && teta<tet)
534 c1=c2 ; *pj1=j ; i1=i3 ; tet=teta ;
538 if (*pbool1)
goto optimum ;
542 if (i1==i2)
goto sortie ;
543 if (bphase2 ||
D[i2]>0)
goto choix ;
546 if (bphase2)
goto sortie ;
549 for (j=
J0 ; j<=
NB ; j++)
550 if (
absf(
A(i2,j))>gamma)
552 gamma=
absf(
A(i2,j)) ; *pj1=j ;
565 float gamma,teta,c1,c2,zeta,tet,
pivot ;
569 *pbool1=1 ; c1=0 ; tet=0 ;
570 for (i=1 ; i<=
MB ; i++)
572 teta=(bphase2) ?
D[i] :
A(i,j2) ;
576 for (j=1 ; j<=
NB ; j++)
578 zeta=
A(0,j)/
A(i,j) ;
583 || zeta==alpha &&
pivot>
A(i,j))
586 alpha=zeta ; j3=j ;
pivot=
A(i,j) ;
591 if (c2>c1 || c2==c1 && teta<tet)
593 c1=c2 ; *pi1=i ; j1=j3 ; tet=teta ;
597 if (*pbool1)
goto optimum ;
599 if (j1==j2)
goto sortie ;
600 if (bphase2 ||
A(0,j2)>0)
goto choix ;
602 if (bphase2)
goto sortie ;
606 for (i=1 ; i<=
MB ; i++)
607 if (gamma <
absf(
A(i,j2)))
609 gamma=
absf(
A(i,j2)) ; *pi1=i ;
616 int i,j,i1,j1,bphase2,bool1,risqueinfini;
float s,gamma,
pivot;
617 RR->sommaire=(
TESTP>1) ? 1 : 0 ;
631 RR->eps2=
RR->eps*100 ;
RR->epss=
RR->eps*10 ;
636 if (
E[0]<0)
E[0]= -1;
643 for (j=1 ; j<=
N1 ; j++)
B[j]=j ;
645 for (i=0 ; i<=
M1 ; i++)
652 for (j=1 ; j<=
N1 ; j++)
A(i,j)= -
A(i,j) ;
657 for (i=1 ; i<=
M1 ; i++)
661 for (j=1 ; j<=
N1 ; j++)
664 for (j=1 ; j<=
N1 ; j++)
669 for (j=1 ; j<=
N1 ; j++)
673 for (i=1 ; i<=
M1 ; i++)
678 for (i=1 ; i<=
M1 ; i++)
687 for (i=0 ; i<=
M1+1 ; i++)
INF[i]=0 ;
688 for (j= -1 ; j<=
N1 ; j++)
INFCOL(j)=0 ;
694 for (i=1 ; i<=
M1 ; i++)
698 for (i1=i ; i1<=
M1 ; i1++)
701 if (s <=
absf(
A(i,
G[i1])))
703 s=
absf(
A(i,
G[i1])) ; j=i1 ;
706 j1=
G[j] ;
G[j]=
G[i] ;
G[i]=
N1+i ;
709 for (i1=i+1 ; i1<=
M1 ; i1++)
720 for (i=1 ; i<=
M1 ; i++)
G[i]=
N1+i ;
728 if (
E[0]== -1)
D[0]= -
D[0] ;
734 for (j=1 ; j<=
N1 ; j++)
735 PI[j]=(
E[0]== -1) ? -
A(0,j) :
A(0,j) ;
736 for (j=1 ; j<=
N1 ; j++)
738 A(0,j)=(
B[j]>
N1) ? 0 :
PI[
B[j]] ;
739 for (i=1 ; i<=
M1 ; i++)
741 A(0,j)=
A(0,j)-
A(i,j)*
PI[
G[i]];
745 for (j=1 ; j<=
N1 ; j++)
746 if (
A(0,j)*
A(0,j) <= s*
INFCOL(j))
A(0,j)=0 ;
753 for (i=1 ; i<=
M1 ; i++)
754 X[i]=(
E[i]== -1) ? -
D[i] :
D[i] ;
755 for (i=0 ; i<=
M1 ; i++)
759 for (j=1 ; j<=
N1 ; j++)
765 for (i=1 ; i<=
M1 ; i++)
766 if (
D[i]*
D[i] <= s*
INF[i])
D[i]=0 ;
769 for (i=1 ; i<=
M1 ; i++)
771 D[0]=
D[0]-
D[i]*
PI[
G[i]] ;
776 for (i=
M1 ; i>=1 ; i--)
777 if (
E[i]==0 &&
G[i]==
N1+i)
780 for (j=
NB ; j>=1 ; j--)
818 for (j=
NB ; j>=1 ; j--)
822 for (i=
MB ; i>=1 ; i--)
835 if (
A(0,j) != 0) risqueinfini=1 ;
847 if (
DUAL)
goto methodeduale ;
851 for (i=1 ; i<=
MB ; i++)
854 bphase2=0 ; gamma=
D[i] ; i1=i ;
856 if (bphase2)
goto phase2 ;
863 for (i=1 ; i<=
M1 ; i++)
864 A(i,0)=(
D[i]<0 && i<=
MB) ? -1 : 0 ;
870 for (i=0 ; i<=
M1 ; i++)
A(i,j1)=
A(i,0) ;
882 for (j=1 ; j<=
NB ; j++)
885 bphase2=0 ; gamma=
A(0,j) ; j1=j ;
887 if (bphase2)
goto phase2dual ;
897 for (j=1 ; j<=
N1 ; j++)
A(
M1,j)=
A(
MB,j) ;
900 for (j=1 ; j<=
NB ; j++)
901 A(
MB,j)=(
A(0,j)<0) ? 1 : 0 ;
902 for (j=
NB+1 ; j<=
N1 ; j++)
A(
MB,j)=0 ;
910 for (j=1 ; j<=
N1 ; j++)
A(i1,j)=
A(
MB,j) ;
915 for (j=1 ; j<=
N1 ; j++)
A(
MB,j)=
A(
M1,j) ;
935 for (i=1 ; i<=
M1+
N1 ; i++)
X[i]=0 ;
938 for (i=1 ; i<=
M1 ; i++)
X[
G[i]]=
D[i] ;
943 for (i=1 ; i<=
M1 ; i++)
947 if (
E[0]== -1)
X[0]= -
X[0] ;
948 for (j=1 ; j<=
N1+
M1 ; j++)
PI[j]=0 ;
950 for (j=1 ; j<=
N1 ; j++)
953 for (j=1 ; j<=
N1 ; j++)
#define VRFIN
.....................
static int phase2(Pproblem XX, struct rproblem *RR, int rvar, int mini)
static int validite(struct rproblem *RR)
fin reduction()
int realsimplex(Prproblem RR)
static void precisioncolonne(struct rproblem *RR, int j, int mx)
fin precision
static int simplexedual(struct rproblem *RR, int j2, int bphase2, int *pi1, int *pbool1)
fin simplexe
static void norm(struct rproblem *RR)
cette procedure normalise la fonction cout, calcule les valeurs des seconds membres resultant d'une n...
static float absf(float vf)
static void precision(struct rproblem *RR, int i, int nx)
fin validite
void elimination(Prproblem RR, int j1)
fin norm()
static int voir4(struct rproblem *RR, int v, int i11, int j11)
static int pivotage(struct rproblem *RR, int i1, int j1)
fin precisioncolonne
static int fraction(struct rproblem *RR, float vf)
static void retrait(struct rproblem *RR, int i1)
fin elimination
static int voir(struct rproblem *RR, int v)
fin voir
static int simplexe(struct rproblem *RR, int i2, int bphase2, int *pj1, int *pbool1)
fin pivotage
static void reduction(struct rproblem *RR)
fin retrait
static int simbad(struct rproblem *RR)
fin simplexedual
#define FT
=========================================================================
#define RMAXCOLONNES
=========================================================================
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
void pivot(frac *X, frac A, frac B, frac C, frac D, bool ofl_ctrl)