r1.c File Reference

#include <stdio.h>
#include "rproblem.h"
Include dependency graph for r1.c:

Go to the source code of this file.

Defines

#define FT   RR->ftrace
 =========================================================================
#define TRACE   RR->ntrace
#define A(i, j)   RR->a[i][j]
#define D   RR->d
#define E   RR->e
#define M1   RR->m
#define M2   RR->m2
#define MB   RR->mb
#define N1   RR->n
#define NB   RR->nb
#define NP   RR->np
#define J0   RR->j0
#define TESTP   RR->testp
#define DUAL   RR->meth
#define COPIE   RR->copie
#define BASE   RR->base
#define COST   RR->cost
#define RHS   RR->rhs
#define VRESULT   RR->vresult
#define ITER   RR->iter
#define ITEMAX   RR->tmax
#define X   RR->x
#define PI   RR->pi
#define B   RR->b
#define G   RR->g
#define INF   RR->inf
#define CONORM(A)   *(RR->pconor+A)
#define INFCOL(A)   *(RR->pinfcolonn+A)
#define VRNUL   VREPS
#define VARIABLELIBRE(v)   v>NP && v<=N1

Functions

static float absf (float vf)
static int fraction (struct rproblem *RR, float vf)
static int voir4 (struct rproblem *RR, int v, int i11, int j11)
static int voir (struct rproblem *RR, int v)
 fin voir
int realsimplex (Prproblem RR)
static void norm (struct rproblem *RR)
 cette procedure normalise la fonction cout, calcule les valeurs des seconds membres resultant d'une normalisation du tableau a, ou effectue ces deux operations
void elimination (Prproblem RR, int j1)
 fin norm()
static void retrait (struct rproblem *RR, int i1)
 fin elimination
static void reduction (struct rproblem *RR)
 fin retrait
static int validite (struct rproblem *RR)
 fin reduction()
static void precision (struct rproblem *RR, int i, int nx)
 fin validite
static void precisioncolonne (struct rproblem *RR, int j, int mx)
 fin precision
static int pivotage (struct rproblem *RR, int i1, int j1)
 fin precisioncolonne
static int simplexe (struct rproblem *RR, int i2, int bphase2, int *pj1, int *pbool1)
 fin pivotage
static int simplexedual (struct rproblem *RR, int j2, int bphase2, int *pi1, int *pbool1)
 fin simplexe
static int simbad (struct rproblem *RR)
 fin simplexedual

Define Documentation

#define A ( i,
j   )     RR->a[i][j]

Definition at line 20 of file r1.c.

#define B   RR->b

Definition at line 41 of file r1.c.

#define BASE   RR->base

Definition at line 33 of file r1.c.

Referenced by simbad().

#define CONORM ( A   )     *(RR->pconor+A)

Definition at line 44 of file r1.c.

Referenced by norm(), pivotage(), precisioncolonne(), and simbad().

#define COPIE   RR->copie

Definition at line 32 of file r1.c.

Referenced by realsimplex().

#define COST   RR->cost

Definition at line 34 of file r1.c.

Referenced by norm(), simbad(), and validite().

#define D   RR->d

Definition at line 21 of file r1.c.

#define DUAL   RR->meth

Definition at line 31 of file r1.c.

Referenced by realsimplex(), and simbad().

#define E   RR->e

Definition at line 22 of file r1.c.

#define FT   RR->ftrace

=========================================================================

SIMPLEXE for integer variables ALL-INTEGER METHODS Jean Claude SOGNO Projet CHLOE -- INRIA ROCQUENCOURT Juin 1994================================================================================================================================================== Duong NGUYEN QUE Adaption to abstract computation: janusvalue CRI-ENSMP=========================================================================

Definition at line 18 of file r1.c.

Referenced by realsimplex(), simbad(), and voir4().

#define G   RR->g

Definition at line 42 of file r1.c.

#define INF   RR->inf

Definition at line 43 of file r1.c.

Referenced by pivotage(), precision(), retrait(), sc_simplexe_feasibility_ofl_ctrl(), and simbad().

#define INFCOL ( A   )     *(RR->pinfcolonn+A)

Definition at line 45 of file r1.c.

Referenced by elimination(), pivotage(), precisioncolonne(), and simbad().

#define ITEMAX   RR->tmax

Definition at line 38 of file r1.c.

Referenced by pivotage(), and simbad().

#define ITER   RR->iter

Definition at line 37 of file r1.c.

Referenced by pivotage(), realsimplex(), simbad(), and voir4().

#define J0   RR->j0

Definition at line 29 of file r1.c.

Referenced by pivotage(), precision(), simbad(), simplexe(), and simplexedual().

#define M1   RR->m

Definition at line 23 of file r1.c.

Referenced by elimination(), norm(), pivotage(), realsimplex(), reduction(), simbad(), validite(), and voir4().

#define M2   RR->m2

Definition at line 24 of file r1.c.

Referenced by precision(), realsimplex(), simbad(), and voir4().

#define MB   RR->mb

Definition at line 25 of file r1.c.

Referenced by pivotage(), realsimplex(), retrait(), simbad(), simplexe(), simplexedual(), and voir4().

#define N1   RR->n

Definition at line 26 of file r1.c.

Referenced by norm(), pivotage(), precision(), precisioncolonne(), realsimplex(), reduction(), retrait(), simbad(), validite(), and voir4().

#define NB   RR->nb

Definition at line 27 of file r1.c.

Referenced by elimination(), pivotage(), realsimplex(), simbad(), simplexe(), simplexedual(), and voir4().

#define NP   RR->np

Definition at line 28 of file r1.c.

#define PI   RR->pi

Definition at line 40 of file r1.c.

Referenced by simbad().

#define RHS   RR->rhs

Definition at line 35 of file r1.c.

Referenced by norm(), simbad(), and validite().

#define TESTP   RR->testp

Definition at line 30 of file r1.c.

Referenced by pivotage(), realsimplex(), and simbad().

#define TRACE   RR->ntrace

Definition at line 19 of file r1.c.

Referenced by realsimplex(), simbad(), voir(), and voir4().

#define VARIABLELIBRE ( v   )     v>NP && v<=N1

Definition at line 47 of file r1.c.

Referenced by reduction(), and simbad().

#define VRESULT   RR->vresult

Definition at line 36 of file r1.c.

#define VRNUL   VREPS

Definition at line 46 of file r1.c.

Referenced by simbad().

#define X   RR->x

Definition at line 39 of file r1.c.

Referenced by outliner(), patch_outlined_reference(), realsimplex(), and simbad().

Function Documentation

static float absf ( float  vf  )  [static]

Definition at line 48 of file r1.c.

Referenced by norm(), pivotage(), precision(), precisioncolonne(), simbad(), simplexe(), and simplexedual().

00049 {       if (vf<0) return(-vf) ;
00050         return(vf) ;
00051 }

Here is the caller graph for this function:

void elimination ( Prproblem  RR,
int  j1 
)

fin norm()

taticcette procedure permute les colonnes j1 (qui sera eliminee) et NB

Definition at line 298 of file r1.c.

References A, B, i, INFCOL, M1, NB, and s.

Referenced by failuresp(), reduction(), and simbad().

00300 { 
00301         if (j1 != NB)
00302         {
00303                 int i ;
00304                 float s ;
00305                 s= INFCOL(j1) ; INFCOL(j1)= INFCOL(NB) ;
00306                 INFCOL(NB)=s ;
00307                 i=B[j1] ; B[j1]=B[NB] ; B[NB]=i ;
00308                 for (i=0 ; i<=M1 ; i++)
00309                 {
00310                         s= A(i,j1) ; A(i,j1)= A(i,NB) ; A(i,NB)=s ;
00311                 } ;
00312         } ;
00313         NB=NB-1 ;
00314 } /* fin elimination */ ;

Here is the caller graph for this function:

static int fraction ( struct rproblem *  RR,
float  vf 
) [static]

Definition at line 52 of file r1.c.

References rproblem::epss.

Referenced by realsimplex().

00053 {       int vi ;
00054         float vfp ;
00055         if (vf<0) vfp= -vf ; else vfp= vf ;
00056         vi=vfp+RR->epss ;
00057         if (vfp-vi<RR->epss) return(0) ; return(1) ;
00058 }

Here is the caller graph for this function:

static void norm ( struct rproblem *  RR  )  [static]

cette procedure normalise la fonction cout, calcule les valeurs des seconds membres resultant d'une normalisation du tableau a, ou effectue ces deux operations

Definition at line 268 of file r1.c.

References A, absf(), CONORM, COST, D, i, M1, N1, RHS, and s.

Referenced by array_indices_communication(), build_sc_with_several_uniform_ref(), call_rwt(), eval_linear_expression(), free_guards(), get_const_off(), initialize_offsets(), loop_index_in_several_indices(), simbad(), and supported_ref_p().

00272 {
00273         float s; int i,j;
00274         if (COST || ! COST && ! RHS)
00275         {
00276                 s=0 ;
00277                 for (j=1 ; j<=N1 ; j++)
00278                 {
00279                         A(0,j)= A(0,j)* CONORM(j) ;
00280                         if (s < absf(A(0,j))) s=absf(A(0,j)) ;
00281                 } ;
00282                 if (s==0) s=1 ;
00283                 for (j=1 ; j<=N1 ; j++) A(0,j)= A(0,j)/s ;
00284                 CONORM(0)=s ;
00285         } ;
00286         if (RHS || ! COST && ! RHS)
00287         {
00288                 s=0 ;
00289                 for (i=1 ; i<=M1 ; i++)
00290                 {
00291                         D[i]= D[i]/ CONORM(N1+i) ;
00292                         if (s < absf(D[i])) s=absf(D[i]) ;
00293                 } ;
00294                 CONORM(-1)=s ;
00295         } ;
00296         D[0]= D[0]/ CONORM(0) ;
00297 } /* fin norm() */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

static int pivotage ( struct rproblem *  RR,
int  i1,
int  j1 
) [static]

fin precisioncolonne

le pivotage de la matrice a s'effectue a partir de la ligne i1 et de la colonne j1. Les numeros de la variable d'ecart (basique) de la ligne i1, et de la variable independante (hors-base) de la colonne j1, contenus respectivement dans les tableaux g et b, sont permutes. Dans le cas de l'elimination d'une egalite, l'operation equivaut a chasser de la base une variable d'ecart identiquement nulle

les quantites inferieures en valeurs absolue a la tolerance correspondante sont annulees

Definition at line 425 of file r1.c.

References A, absf(), B, CONORM, D, rproblem::eps2, rproblem::epss, G, i, INF, INFCOL, ITEMAX, ITER, J0, M1, MB, N1, NB, precision(), precisioncolonne(), s, rproblem::sommaire, TESTP, voir4(), VREPS, VRESULT, and VRINS.

Referenced by simbad(), simplexe(), and simplexedual().

00432 {
00433         float p1,p2,s ;
00434         int i,j,mx,nx ;
00435         if (ITER==ITEMAX) return(VRESULT=VRINS);
00436         s= A(i1,j1); if (absf(s)<RR->eps2) return(VRESULT=VREPS);
00437         nx=N1 ; mx=M1 ; if (TESTP>0) nx=NB ; if (TESTP>2) mx=MB ;
00438         ITER=ITER+1 ; p1=1/s ;
00439         j=B[j1] ; B[j1]=G[i1] ; G[i1]=j ;
00440         for (i=0 ; i<=mx ; i++)
00441         if (i != i1 && A(i,j1) !=0)
00442         {
00443                 p2= A(i,j1)*p1 ; D[i]= D[i]-D[i1]*p2 ;
00444                 if (RR->sommaire) if (absf(D[i])<RR->epss) D[i]=0 ;
00445                 for (j=J0 ; j<=nx ; j++)
00446                         if (j==j1) A(i,j)= -p2
00447                         ; else
00448                         if (A(i1,j) != 0)
00449                         {
00450                                 A(i,j)= A(i,j)-p2* A(i1,j) ;
00451                                 if (RR->sommaire)
00452                                         if (absf(A(i,j))<RR->epss) A(i,j)=0 ;
00453                         } ;
00454                 if (! RR->sommaire) precision(RR,i,nx) ;
00455         } ;
00456         D[i1]= D[i1]*p1 ;
00457         for (j=J0 ; j<=nx ; j++)
00458                 A(i1,j)=(j==j1) ? p1 : A(i1,j)*p1 ;
00459         if (RR->sommaire) goto finpivotage ;
00460         p1=absf(p1) ;
00461         INF[i1]=INF[i1]*p1 ;
00462         /* les quantites inferieures en valeurs absolue a la tolerance
00463                 correspondante sont annulees */
00464         if (D[i1] != 0)
00465         {       precisioncolonne(RR,-1,mx) ;
00466                 s= INFCOL(-1)* CONORM(-1) ;
00467                 for (i=0 ; i<=mx ; i++)
00468                 if (D[i] != 0)
00469                 {
00470                         if (D[i]* D[i] <= INF[i]*s) D[i]=0 ;
00471                 } ;
00472         } ;
00473         for (j=J0 ; j<=nx ; j++)
00474         if (j==j1) INFCOL(j)= INFCOL(j)*p1
00475         ; else
00476         if (A(i1,j) != 0)
00477         {       precisioncolonne(RR,j,mx) ;
00478                 s= INFCOL(j) ;
00479                 for (i=0 ; i<=mx ; i++)
00480                 if (A(i,j) != 0)
00481                 {
00482                         if (A(i,j)* A(i,j) <= INF[i]*s) A(i,j)=0 ;
00483                 } ;
00484         } ;
00485 finpivotage:
00486         voir4(RR,30,i1,j1) ;
00487         return(0);
00488 } /* fin pivotage */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

static void precision ( struct rproblem *  RR,
int  i,
int  nx 
) [static]

fin validite

Definition at line 380 of file r1.c.

References A, absf(), B, rproblem::eps1, G, INF, J0, M2, N1, and s.

Referenced by pivotage(), and simbad().

00384 {
00385         int j;
00386         float s ;
00387         if (i==0) s=1
00388         ; else
00389                 s=(i>M2 || G[i]>N1) ? 1 : 0 ;
00390         for (j=J0 ; j<=nx ; j++)
00391                 if (B[j]>N1) s=s+absf(A(i,j)) ;
00392         s=s*RR->eps1 ;
00393         if (s>INF[i]) INF[i]=s ;
00394 } /* fin precision */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

static void precisioncolonne ( struct rproblem *  RR,
int  j,
int  mx 
) [static]

fin precision

Definition at line 396 of file r1.c.

References A, absf(), B, CONORM, D, rproblem::eps1, G, i, INFCOL, N1, and s.

Referenced by pivotage(), and simbad().

00401 {
00402         int i ;
00403         float s ;
00404         if (j != -1)
00405         {
00406                 s=(B[j]>N1) ? 0 : 1 ;
00407                 for (i=1 ; i<=mx ; i++)
00408                 if (G[i] <= N1)
00409                 {
00410                         if (A(i,j) != 0) s=s+absf(A(i,j)) ;
00411                 }
00412         }
00413         else
00414         {
00415                 s= CONORM(-1) ;
00416                 for (i=1 ; i<=mx ; i++)
00417                 if (G[i] <= N1)
00418                 {
00419                         if (D[i] != 0) s=s+absf(D[i]) ;
00420                 } ;
00421         } ;
00422         s=s*RR->eps1 ;
00423         if (s > INFCOL(j)) INFCOL(j)=s ;
00424 } /* fin precisioncolonne */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

int realsimplex ( Prproblem  RR  ) 

pconor utilise par macro CONORM

utilise par macro INFCOL

peut-etre a modifier 0.0000001 0.0000003

lse fprintf(FT,",memes colonnes" );

f (TESTP==0) fprintf(FT,", tests precision pousses\n" ); if (TESTP==1) fprintf(FT,", tests precision moyens\n" ); if (TESTP==2) fprintf(FT,", tests precision sommaires\n" ); if (TESTP>2) fprintf(FT,",sommaire,entiers inconnus\n");

9

variables rendues toutes >=0

f (simbad(RR)) return(VRESULT);

9

printf(FT,"x[%2d] =%9.3f\n",jj,X[jj] );

if (NP!=nvp)

9

examen si variables fractionnaires utilisation marginale

if (mx==M1)

AUX

RAI

f (TRACE) fprintf(FT,"\\end{document}\n");

Definition at line 149 of file r1.c.

References A, COPIE, DUAL, rproblem::eps, fprintf(), fraction(), FT, G, ITER, M1, M2, MB, rproblem::mcontr, N1, NB, NP, rproblem::nvar, rproblem::nvpos, rproblem::pconor, rproblem::pinfcolonn, rproblem::rfrac, RMAXCOLONNES, RMAXLIGNES, s, simbad(), rproblem::tconor, TESTP, rproblem::tfrac, rproblem::tinfcolonn, TRACE, voir(), VRBUG, VRCAL, VRDEB, VREPS, VRESULT, VRFIN, VRINF, VRINS, VRVID, and X.

Referenced by localnewrsimplex(), phase1(), and phase2().

00150 { int mee,nvt;
00151 /*********************** initialisations **********************/
00152   M1=RR->mcontr ; N1=RR->nvar ; NP=RR->nvpos ;
00153   mee=M1; nvt=N1;
00154   if (M1>RMAXLIGNES) return(VRDEB) ;
00155   if (N1>RMAXCOLONNES) return(VRDEB) ;
00156   if (NP>nvt) return(VRDEB) ;
00157   VRESULT=0 ;
00158   RR->pconor= &RR->tconor[1] ;  /* pconor utilise par macro CONORM */
00159   RR->pinfcolonn= &RR->tinfcolonn[1] ;  /* utilise par macro INFCOL */
00160   RR->eps=0.0000001 ;  /* peut-etre a modifier 0.0000001  0.0000003 */
00161   NB=N1 ; M2=M1 ;
00162   if (TRACE>0)
00163     { fprintf(FT,"%3d contraintes%3d variables%3d variables non-negatives\n",
00164               M1,N1,NP) ;
00165       if (DUAL)fprintf(FT,"  dual"); else fprintf(FT,"  primal");
00166       if (COPIE) fprintf(FT,", doublage");
00167           /*else fprintf(FT,",memes colonnes" );*/
00168           /*if (TESTP==0) fprintf(FT,", tests precision pousses\n" );
00169       if (TESTP==1) fprintf(FT,", tests precision moyens\n" );
00170       if (TESTP==2) fprintf(FT,", tests precision sommaires\n" );
00171       if (TESTP>2) fprintf(FT,",sommaire,entiers inconnus\n");*/
00172       if (TESTP==0) fprintf(FT,", tests precision pousses" );
00173       if (TESTP==1) fprintf(FT,", tests precision moyens" );
00174       if (TESTP==2) fprintf(FT,", tests precision sommaires" );
00175       if (TESTP>2) fprintf(FT,",sommaire,entiers inconnus");
00176       fprintf(FT,", niveau trace: %d\\\\\n",TRACE); /*99*/
00177     }
00178   if (COPIE)
00179     { int ii,jj,jk ;
00180       if(TRACE)fprintf(FT,"systeme original contraintes\n"); voir(RR,1) ;
00181       if (TRACE) fprintf(FT,"systeme modifie contraintes double:\n");
00182       if ((N1=(2*nvt)-NP) >RMAXCOLONNES) return(VRDEB) ;
00183       for (ii=0 ; ii<= M1 ; ii++)
00184         { jk=N1 ;
00185           for (jj=nvt ; jj>= 1 ; jj--)
00186             { float s; s=A(ii,jj);
00187               if (jj>NP) A(ii,jk--)= -s;
00188               A(ii,jk--)= s;
00189             };
00190         } ;
00191       NP=N1 ;                   /* variables rendues toutes >=0 */
00192     }
00193       /*if (simbad(RR)) return(VRESULT);*/
00194   VRESULT=simbad(RR);
00195   if (TRACE)
00196     { fprintf(FT,"resultat simplexe apres %d iterations: ",ITER) ;
00197       if (VRESULT==VRFIN) fprintf(FT,"solution finie\n") ;
00198       if (VRESULT==VRVID) fprintf(FT,"polyedre vide\n") ;
00199       if (VRESULT==VRINF) fprintf(FT,"solution infinie\n") ;
00200       if (VRESULT==VRINS) fprintf(FT,"nombre insuffisant\n") ;
00201       if (VRESULT==VRDEB) fprintf(FT,"debordement tableaux\n") ;
00202       if (VRESULT==VRCAL) fprintf(FT,"appel errone\n") ;
00203       if (VRESULT==VREPS) fprintf(FT,"pivot anormalement petit\n") ;
00204       if (VRESULT==VRBUG) fprintf(FT,"bug de programmation\n") ;
00205       fprintf(FT,"\\\\\n") ; /*99*/
00206     }
00207   if (VRESULT) return(VRESULT);
00208 /******************** cas ou une solution finie est obtenue ******************/
00209   if (TRACE>1)
00210     { int jj,jk ; float xf ;
00211       for (jj=0 ; jj<= N1+M1 ; jj++)
00212         { if (X[jj] !=0)
00213             { if (jj<= N1) fprintf(FT," " );
00214                                   else fprintf(FT,"%2d: ",jj-N1 );
00215               /*fprintf(FT,"x[%2d] =%9.3f\n",jj,X[jj] );*/
00216               fprintf(FT,"x[%2d] =%13.6f\n",jj,X[jj] );
00217             } ;
00218         } ;
00219       if (TESTP>2 && MB!=M1)
00220         { fprintf(FT," sans signification pour variables libres:\n");
00221           for (jj=MB+1 ; jj<= M1 ; jj++) fprintf(FT," %3d",G[jj]);
00222           fprintf(FT,"\n");
00223         }
00224       if (COPIE && (nvt-NP)) /* if (NP!=nvp) */
00225         { jk=0 ;
00226           for (jj=1 ; jj<= nvt+mee ; jj++)
00227             { jk++ ; xf=X[jk] ;
00228               if (jj>NP && jj<=nvt)
00229                 { jk++ ; if (xf==0) xf= -X[jk] ;
00230                 };
00231               X[jj] = xf ;
00232             };
00233           fprintf(FT,"resultats probleme initial:\n") ;
00234           for (jj=0 ; jj<= nvt+mee ; jj++)
00235             if (X[jj] !=0)
00236               { if (jj <= nvt) fprintf(FT,"     " );
00237                 else fprintf(FT,"%2d:   ",jj-nvt );
00238                 fprintf(FT,"x[%2d] =%9.3f\n",jj,X[jj] );
00239               }
00240         };
00241       fprintf(FT,"\\\\\n"); /*99*/
00242     }
00243   VRESULT=VRFIN ;
00244   if (RR->tfrac==0) return(VRESULT) ;
00245   /* examen si variables fractionnaires utilisation marginale */
00246   if (TESTP<3)
00247     /*  if (mx==M1)*/
00248     { int bfract, jj ; bfract=0 ;/*FAUX*/
00249       for (jj=0 ; jj<= N1 ; jj++)
00250         if (fraction(RR,X[jj]))
00251           { if (TRACE>0)
00252               { if (!bfract) fprintf(FT," variables non entieres: ");
00253                 fprintf(FT," %2d",jj);
00254               } ;
00255             bfract=1 ;/*VRAI*/
00256           } ;
00257       if (TRACE>0){
00258         if (bfract) fprintf(FT,"\n");
00259         else fprintf(FT," certitude variables toutes entieres\n");
00260       }
00261       RR->rfrac=0 ; if (bfract) RR->rfrac=1 ; 
00262     } ;
00263       /*if (TRACE) fprintf(FT,"\\end{document}\n");*/
00264 return(VRESULT) ;
00265 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void reduction ( struct rproblem *  RR  )  [static]

fin retrait

cette procedure groupe les vecteurs provenant de l'elimination des egalites dans les colonnes NB+1 a n

Definition at line 333 of file r1.c.

References B, E, elimination(), G, M1, N1, retrait(), and VARIABLELIBRE.

00336 {       int j;
00337         for (j=N1 ; j>=1 ; j--)
00338         if (B[j] > N1)
00339         {
00340                 if (E[B[j]-N1] == 0) elimination(RR,j) ;
00341         } ;
00342         for (j=M1 ; j>=1 ; j--)
00343           if (VARIABLELIBRE(G[j])) retrait(RR,j) ;
00344 } /* fin reduction() */ ;

Here is the call graph for this function:

static void retrait ( struct rproblem *  RR,
int  i1 
) [static]

fin elimination

cette procedure permute les lignes i1 (qui sera eliminee) et mb

Definition at line 316 of file r1.c.

References A, D, G, INF, MB, N1, and s.

Referenced by reduction(), and simbad().

00318 { 
00319         if (i1 != MB)
00320         {
00321                 int j ; float s ;
00322                 s=INF[i1] ; INF[i1]=INF[MB] ; INF[MB]=s ;
00323                 s= D[i1] ; D[i1]= D[MB] ; D[MB]=s ;
00324                 j=G[i1] ; G[i1]=G[MB] ; G[MB]=j ;
00325                 for (j=0 ; j<=N1 ; j++)
00326                 {
00327                         s= A(i1,j) ; A(i1,j)= A(MB,j) ; A(MB,j)=s ;
00328                 } ;
00329         } ;
00330         MB=MB-1 ;
00331 } /* fin retrait */ ;

Here is the caller graph for this function:

static int simbad ( struct rproblem *  RR  )  [static]

fin simplexedual

apres modification directe de la matrice

on donne aux inequations le meme sens et on se ramene eventuellement a un probleme de minimisation

normalisation des lignes

normalisation des colonnes

include "base.c"

reprendre ................................................

include "corh.c"

calcul de la ligne de la nouvelle fonction cout a l'aide de l'inverse de la base du systeme dual. pi est utilise comme tableau auxiliaire

calcul de la colonne des nouveaux seconds membres a l'aide de l'inverse de la base (systeme primal). x est utilise comme tableau auxiliaire

reprendre ................................................

elimination des egalites

la premiere variable libre possible est choisie d'autorite,signalee par pivot

l'equation est surabondante ou incompatible

l'equation surabondante est ignoree

l'equation est changee en inequation dont la variable d'ecart provient du vecteur j1, qui entre dans la base

le systeme auquel on s'est ramene ne comporte que des inequations, dont le nombre de variables est egal a NB. dans les colonnes NB+1 a n ont ete groupes les vecteurs provenant des pivotages effectues au cours des eliminations des egalites ces vecteurs ne sont pas detruits, car ils appartiennent a l'inverse de la base, utilisee dans les tests de precision, et eventuellement dans le calcul de la colonne des nouveaux seconds membres

traitement variables libres

la variable n'intervient pas dans le domaine mais si le cout relatif n'est pas nul, il ne pourra exister de solution finie

on fait entrer dans la base la variable libre la variable d'ecart resultante sera desormais ignoree

une premiere phase est necessaire. une (seule) variable artificielle est introduite dans le systeme au moyen de la colonne 0 du tableau a

fin de la premiere phase avec obtention d'une solution realisable

une (seule) variable artificielle est ajoutee au systeme dual au moyen de la ligne mb+1 du tableau a

ligne conservee uniquement pour tests de precision

il n'existe pas de solution realisable dans le domaine dual, mais on ignore si cela correspond a un polyedre vide ou a une solution infinie pour le probleme primal

Definition at line 611 of file r1.c.

References A, absf(), B, BASE, CONORM, COST, D, DUAL, E, elimination(), rproblem::eps, rproblem::eps1, rproblem::eps2, rproblem::epss, fprintf(), FT, G, i, INF, INFCOL, ITEMAX, ITER, J0, M1, M2, MB, N1, NB, norm(), NP, phase2(), PI, pivotage(), precision(), precisioncolonne(), retrait(), RHS, s, simplexe(), simplexedual(), rproblem::sommaire, TESTP, TRACE, validite(), VARIABLELIBRE, voir(), VRCAL, VRESULT, VRFIN, VRINF, VRNUL, VRVID, and X.

Referenced by realsimplex().

00612 { 
00613 int i,j,i1,j1,bphase2,bool1,risqueinfini; float s,gamma,pivot;
00614         RR->sommaire=(TESTP>1) ? 1 : 0 ;
00615         if (NP<0)
00616           { if (TRACE) fprintf(FT,"Negative value for nvpos:%d\n",NP);
00617             return(VRCAL);
00618           }
00619         if (N1<NP)
00620           { if (TRACE)fprintf(FT,"nvar (%d) < nvpos (%d)\n",N1,NP);
00621             return(VRCAL);
00622           }
00623         if (M1<0)
00624           { if (TRACE) fprintf(FT,"Negative value for mcontr:%d\n",M1);
00625             return(VRCAL);
00626           }
00627         ITER=0 ; ITEMAX=2*M1+N1 ; RR->eps1=RR->eps*10 ;
00628         RR->eps2=RR->eps*100 ;RR->epss=RR->eps*10 ;
00629         J0=1 ; bphase2=1 ; NB=N1 ; M2=M1 ;
00630         MB=M1 ; VRESULT=0;
00631         risqueinfini=0 ;
00632         if (E[0]>0) E[0]=1;
00633         if (E[0]<0) E[0]= -1;
00634         if (COST<0) /* apres modification directe de la matrice */
00635           {
00636           }
00637         else
00638         if (! COST && ! RHS)
00639         {
00640                 for (j=1 ; j<=N1 ; j++) B[j]=j ;
00641                 voir(RR,1) ;
00642                 for (i=0 ; i<=M1 ; i++)
00643                 if (E[i]== -1)
00644                 {
00645                         /*      on donne aux inequations le meme sens et on
00646                                 se ramene eventuellement a un probleme de
00647                                 minimisation */
00648                         D[i]= -D[i] ;
00649                         for (j=1 ; j<=N1 ; j++) A(i,j)= -A(i,j) ;
00650                 } ;
00651                 voir(RR,2) ;
00652             if (! RR->sommaire)
00653             {
00654                 for (i=1 ; i<=M1 ; i++)
00655                 {
00656                         /* normalisation des lignes */
00657                         s=0 ;
00658                         for (j=1 ; j<=N1 ; j++)
00659                                 if (s < absf(A(i,j))) s=absf(A(i,j)) ;
00660                         if (s==0) s=1 ;
00661                         for (j=1 ; j<=N1 ; j++)
00662                                 A(i,j)= A(i,j)/s ;
00663                         CONORM(N1+i)=s ;
00664                 } ;
00665         voir(RR,3) ;
00666                 for (j=1 ; j<=N1 ; j++)
00667                 {
00668                         /* normalisation des colonnes */
00669                         s=0 ;
00670                         for (i=1 ; i<=M1 ; i++)
00671                                 if (s < absf(A(i,j))) s=absf(A(i,j)) ;
00672                         if (s==0) s=1 ;
00673                         if (s<1)
00674                         {
00675                                 for (i=1 ; i<=M1 ; i++)
00676                                         A(i,j)= A(i,j)/s ;
00677                                 CONORM(j)=1/s ;
00678                         }
00679                         else CONORM(j)=1 ;
00680                 } ;
00681         voir(RR,4) ;
00682                 norm(RR) ;
00683         voir(RR,5) ;
00684                 for (i=0 ; i<=M1+1 ; i++) INF[i]=0 ;
00685                 for (j= -1 ; j<=N1 ; j++) INFCOL(j)=0 ;
00686             } ;
00687 /*#include "base.c"*/
00688                 if (BASE)
00689                 {
00690                         if (validite(RR)) return(VRESULT) ;
00691                         for (i=1 ; i<=M1 ; i++)
00692                         if (G[i] <= N1)
00693                         {
00694                                 s=0 ;
00695                                 for (i1=i ; i1<=M1 ; i1++)
00696                                 if (G[i1] <= N1)
00697                                 {
00698                                         if (s <= absf(A(i,G[i1])))
00699                                         {
00700                                                 s=absf(A(i,G[i1])) ; j=i1 ;
00701                                         } ;
00702                                 } ;
00703                                 j1=G[j] ; G[j]=G[i] ; G[i]=N1+i ;
00704                                 if (s==0)
00705                                 {
00706                                         for (i1=i+1 ; i1<=M1 ; i1++)
00707                                                 G[i1]=N1+i1 ;
00708                                         return(VRESULT=VRNUL) ;
00709                                 } ;
00710                                 M2=i ;
00711                                 if (pivotage(RR,i,j1)) return(VRESULT);
00712                         } ;
00713                         reduction(RR) ;
00714                 }
00715                 else
00716 /* reprendre ................................................ */
00717                         for (i=1 ; i<=M1 ; i++) G[i]=N1+i ;
00718 /*#include "corh.c"*/
00719         }
00720         else
00721         {
00722                 if (validite(RR)) return(VRESULT) ;
00723                 reduction(RR) ;
00724                 norm(RR) ;
00725                 if (E[0]== -1) D[0]= -D[0] ;
00726                 if (COST)
00727                 {
00728                         /* calcul de la ligne de la nouvelle fonction
00729                         cout a l'aide de l'inverse de la base du systeme dual.
00730                         pi est utilise comme tableau auxiliaire */
00731                         for (j=1 ; j<=N1 ; j++)
00732                                 PI[j]=(E[0]== -1) ? -A(0,j) : A(0,j) ;
00733                         for (j=1 ; j<=N1 ; j++)
00734                         {
00735                                 A(0,j)=(B[j]>N1) ? 0 : PI[B[j]] ;
00736                                 for (i=1 ; i<=M1 ; i++)
00737                                 if (G[i] <= N1)
00738                                         A(0,j)= A(0,j)-A(i,j)*PI[G[i]];
00739                         } ;
00740                         INF[0]=0 ; precision(RR,0,N1) ;
00741                         s=INF[0] ;
00742                         for (j=1 ; j<=N1 ; j++)
00743                                 if (A(0,j)* A(0,j) <= s* INFCOL(j)) A(0,j)=0 ;
00744                 } ;
00745                 if (RHS)
00746                 {
00747                         /* calcul de la colonne des nouveaux seconds
00748                         membres a l'aide de l'inverse de la base (systeme
00749                         primal). x est utilise comme tableau auxiliaire */
00750                         for (i=1 ; i<=M1 ; i++)
00751                                 X[i]=(E[i]== -1) ? -D[i] : D[i] ;
00752                         for (i=0 ; i<=M1 ; i++)
00753                         {
00754                                 if (i != 0)
00755                                 D[i]=(G[i]>N1) ? X[G[i]-N1] : 0 ;
00756                                 for (j=1 ; j<=N1 ; j++)
00757                                         if (B[j]>N1)
00758                                                 D[i]= D[i]+A(i,j)*X[B[j]-N1] ;
00759                         } ;
00760                         INFCOL(-1)=0 ; precisioncolonne(RR,-1,M1) ;
00761                         s= INFCOL(-1)* CONORM(-1) ;
00762                         for (i=1 ; i<=M1 ; i++)
00763                                 if (D[i]* D[i] <= s*INF[i]) D[i]=0 ;
00764                 }
00765                 else
00766                 for (i=1 ; i<=M1 ; i++)
00767                         if (G[i] <= N1)
00768                                 D[0]= D[0]-D[i]*PI[G[i]] ;
00769 /* reprendre ................................................ */
00770         } ;
00771         voir(RR,6) ;
00772         /*      elimination des egalites */
00773         for (i=M1 ; i>=1 ; i--)
00774         if (E[i]==0 && G[i]==N1+i)
00775         {
00776                 pivot=0 ;
00777                 for (j=NB ; j>=1 ; j--)
00778                 if (pivot>=0)
00779                 {
00780                         s=absf(A(i,j)) ;
00781                         if (s>pivot)
00782                         {
00783                                 pivot=s ; j1=j ;
00784                                 /* la premiere variable libre possible est
00785                                         choisie d'autorite,signalee par pivot*/
00786                                 if (VARIABLELIBRE(B[j])) pivot= -1 ;
00787                         }
00788                 } ;
00789                 if (pivot==0)
00790                 {
00791                         /*      l'equation est surabondante ou incompatible */
00792                         if (D[i] != 0) return(VRESULT=VRVID);
00793                         /*      l'equation surabondante est ignoree */
00794                 }
00795                 else
00796                 {
00797                         /*      l'equation est changee en inequation dont la
00798                                 variable d'ecart provient du vecteur j1, qui
00799                                 entre dans la base */
00800                         if (pivotage(RR,i,j1)) return(VRESULT);
00801                         elimination(RR,j1) ;
00802                         if (pivot<0) retrait(RR,i) ;
00803                 } ;
00804         } ;
00805         voir(RR,7) ;
00806         /*      le systeme auquel on s'est ramene ne comporte que des
00807                 inequations, dont le nombre de variables est egal a NB. dans
00808                 les colonnes NB+1 a n ont ete groupes les vecteurs provenant
00809                 des pivotages effectues au cours des eliminations des egalites
00810                 ces vecteurs ne sont pas detruits, car ils appartiennent a
00811                 l'inverse de la base, utilisee dans les tests de precision, et
00812                 eventuellement dans le calcul de la colonne des nouveaux
00813                 seconds membres */
00814         /*      traitement variables libres */
00815         for (j=NB ; j>=1 ; j--)
00816         if (VARIABLELIBRE(B[j]))
00817         {
00818                 pivot=0 ;
00819                 for (i=MB ; i>=1 ; i--)
00820                 {
00821                         s=absf(A(i,j)) ;
00822                         if (s>pivot)
00823                         {
00824                                 pivot=s ; i1=i ;
00825                         } ;
00826                 } ;
00827                 if (pivot==0)
00828                 {
00829                         /*      la variable n'intervient pas dans le domaine
00830                                 mais si le cout relatif n'est pas nul, il ne
00831                                 pourra exister de solution finie */
00832                         if (A(0,j) != 0) risqueinfini=1 ;
00833                         elimination(RR,j) ;
00834                 }
00835                 else
00836                 {
00837                         /*      on fait entrer dans la base la variable libre
00838                                 la variable d'ecart resultante sera desormais
00839                                 ignoree */
00840                         if (pivotage(RR,i1,j)) return(VRESULT);
00841                         retrait(RR,i1) ;
00842                 } ;
00843         } ;
00844         if (DUAL) goto methodeduale ;
00845 methodeprimale:
00846         voir(RR,8) ;
00847         gamma=0 ;
00848         for (i=1 ; i<=MB ; i++)
00849         if (D[i]<gamma)
00850         {
00851                 bphase2=0 ; gamma= D[i] ; i1=i ;
00852         } ;
00853         if (bphase2) goto phase2 ;
00854         /*      une premiere phase est necessaire. une (seule) variable
00855                 artificielle est introduite dans le systeme au moyen de la
00856                 colonne 0 du tableau a */
00857         voir(RR,9) ;
00858         J0=0 ;
00859         B[0]=0 ; A(0,0)=0 ; INFCOL(0)=0 ;
00860         for (i=1 ; i<=M1 ; i++)
00861                 A(i,0)=(D[i]<0 && i<=MB) ? -1 : 0 ;
00862         voir(RR,10) ;
00863         if (pivotage(RR,i1,0)) return(VRESULT);
00864         voir(RR,11) ;
00865         (simplexe(RR,i1,bphase2,&j1,&bool1)) ; if (VRESULT) return(VRESULT);
00866         B[j1]=B[0] ; INFCOL(j1)= INFCOL(0) ;
00867         for (i=0 ; i<=M1 ; i++) A(i,j1)= A(i,0) ;
00868         if (bool1) return(VRESULT=VRVID);
00869         J0=1 ; bphase2=1 ;
00870         /* fin de la premiere phase avec obtention d'une solution
00871                 realisable */
00872 phase2:
00873         voir(RR,12) ;
00874         (simplexe(RR,0,bphase2,&j1,&bool1)) ; if (VRESULT) return(VRESULT);
00875         goto resultats ;
00876 methodeduale:
00877         voir(RR,13) ;
00878         gamma=0 ;
00879         for (j=1 ; j<=NB ; j++)
00880                 if (A(0,j)<gamma)
00881                 {
00882                         bphase2=0 ; gamma= A(0,j) ; j1=j ;
00883                 } ;
00884         if (bphase2) goto phase2dual ;
00885         /*      une (seule) variable artificielle est ajoutee au systeme dual
00886                 au moyen de la ligne mb+1 du tableau a */
00887         voir(RR,14) ;
00888         M2=M1=M1+1 ;
00889         MB=MB+1 ;
00890         /* ligne conservee uniquement pour tests de precision */
00891         if (MB!=M1)
00892         {
00893                 G[M1]=G[MB] ; D[M1]= D[MB] ; INF[M1]=INF[MB] ;
00894                 for (j=1 ; j<=N1 ; j++) A(M1,j)= A(MB,j) ;
00895         } ;
00896         G[MB]=M1+N1 ; D[MB]=0 ; INF[MB]=0 ;
00897         for (j=1 ; j<=NB ; j++)
00898                 A(MB,j)=(A(0,j)<0) ? 1 : 0 ;
00899         for (j=NB+1 ; j<=N1 ; j++) A(MB,j)=0 ;
00900         voir(RR,15) ;
00901         if (pivotage(RR,MB,j1)) return(VRESULT);
00902         voir(RR,16) ;
00903         simplexedual(RR,j1,bphase2,&i1,&bool1); if (VRESULT) return(VRESULT);
00904         if (i1 != MB)
00905         {
00906                 D[i1]= D[MB] ; G[i1]=G[MB] ; INF[i1]=INF[MB] ;
00907                 for (j=1 ; j<=N1 ; j++) A(i1,j)= A(MB,j) ;
00908         } ;
00909         if (MB != M1)
00910         {
00911                 D[MB]= D[M1] ; G[MB]=G[M1] ; INF[MB]=INF[M1] ;
00912                 for (j=1 ; j<=N1 ; j++) A(MB,j)= A(M1,j) ;
00913         } ;
00914         M2=M1=M1-1 ;
00915         MB=MB-1 ;
00916         voir(RR,17) ;
00917         bphase2=1 ;
00918         if (bool1)
00919         {
00920                 /*      il n'existe pas de solution realisable dans le domaine
00921                         dual, mais on ignore si cela correspond a un polyedre
00922                         vide ou a une solution infinie pour le probleme
00923                         primal*/
00924                 voir(RR,18) ;
00925                 ITEMAX=ITEMAX+ITER ; goto methodeprimale ;
00926         } ;
00927 phase2dual:
00928         voir(RR,19) ;
00929         simplexedual(RR,0,bphase2,&i1,&bool1); if (VRESULT) return(VRESULT);
00930 resultats:
00931         if (risqueinfini) return(VRESULT=VRINF);
00932         for (i=1 ; i<=M1+N1 ; i++) X[i]=0 ;
00933         if (RR->sommaire)
00934         {
00935                 for (i=1 ; i<=M1 ; i++) X[G[i]]= D[i] ;
00936                 X[0]= D[0] ;
00937         }
00938         else
00939         {
00940         for (i=1 ; i<=M1 ; i++)
00941                 X[G[i]]= D[i]* CONORM(G[i]) ;
00942         X[0]= D[0]* CONORM(0) ;
00943         } ;
00944         if (E[0]== -1) X[0]= -X[0] ;
00945         for (j=1 ; j<=N1+M1 ; j++) PI[j]=0 ;
00946         if (RR->sommaire)
00947           for (j=1 ; j<=N1 ; j++)
00948                 PI[B[j]]= A(0,j) ;
00949         else
00950           for (j=1 ; j<=N1 ; j++)
00951                 PI[B[j]]= A(0,j)* CONORM(0)/ CONORM(B[j]) ;
00952         return(VRESULT=VRFIN) ;
00953 } /* fin simbad */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

static int simplexe ( struct rproblem *  RR,
int  i2,
int  bphase2,
int *  pj1,
int *  pbool1 
) [static]

fin pivotage

Cette procedure minimise le cout defini dans la ligne i2 (s'il s'agit du cout artificiel, il est represente en valeur opposee)

en phase 1, bphase2 est faux

fin i

fin j

si la variable artificielle quitte la base, on sort de la procedure simplexe

le cout minimum est atteint

on chasse la variable artificielle de la base

en phase 1 le booleen bool1 indique si le polyedre est vide

Definition at line 489 of file r1.c.

References A, absf(), D, i, J0, MB, NB, pivotage(), VRESULT, and VRINF.

Referenced by simbad().

00492 {
00493         int i,j;
00494         int i1= 0,i3 =0;
00495         float gamma,teta,c1,c2,zeta,tet,pivot ;
00496         float alpha =0;
00497         /* en phase 1, bphase2 est faux */
00498 choix:
00499         /*
00500         Le pivot est choisi de facon a assurer la diminution la plus grande du
00501         cout. Si plusieurs pivots realisent cette condition (ce qui se produit
00502         essentiellement dans le cas d'un sommet multiple, la plus grande
00503         diminution possible pouvant etre nulle), on prendra celui situe dans
00504         la colonne dont le facteur de cout relatif est le plus negatif, et
00505         dans une meme colonne, le plus grand pivot. Si au cours de
00506         l'exploration d'une colonne aucun coefficient positif n'est rencontre,
00507         on se renvoie a l'etiquette solution infinie */
00508         *pbool1=1 ; c1=0 ; tet=0 ;
00509         for (j=J0 ; j<=NB ; j++)
00510         {
00511                 teta=(bphase2) ? A(i2,j) : -A(i2,j) ;
00512                 if (teta < 0)
00513                 {
00514                         *pbool1=1 ; pivot=0 ;
00515                         for (i=1 ; i<=MB ; i++)
00516                         if (A(i,j) > 0)
00517                         {
00518                                 zeta= D[i]/ A(i,j) ;
00519                                 if (*pbool1
00520                                 || zeta<alpha
00521                                 || zeta==alpha && pivot<A(i,j))
00522                                 {
00523                                         *pbool1=0;
00524                                         alpha=zeta ; i3=i ; pivot= A(i,j) ;
00525                                 }
00526                         } /* fin i */ ;
00527                         if (*pbool1) return(VRESULT=VRINF);
00528                         c2=alpha*teta ;
00529                         if (c2<c1 || c2==c1 && teta<tet)
00530                         {
00531                                 c1=c2 ; *pj1=j ; i1=i3 ; tet=teta ;
00532                         }
00533                 }
00534         } /* fin j */ ;
00535         if (*pbool1) goto optimum ;
00536         if (pivotage(RR, i1,*pj1)) return(VRESULT);
00537         /* si la variable artificielle quitte la base, on sort de la
00538                 procedure simplexe */
00539         if (i1==i2) goto sortie ;
00540         if (bphase2 || D[i2]>0) goto choix ;
00541 optimum:
00542         /* le cout minimum est atteint */
00543         if (bphase2) goto sortie ;
00544         /* on chasse la variable artificielle de la base */
00545         gamma=0 ;
00546         for (j=J0 ; j<=NB ; j++)
00547         if (absf(A(i2,j))>gamma)
00548         {
00549                 gamma=absf(A(i2,j)) ; *pj1=j ;
00550         } ;
00551         if (pivotage(RR, i2,*pj1)) return(VRESULT);
00552 sortie:
00553         /* en phase 1 le booleen bool1 indique si le polyedre est vide */
00554 } /* fin simplexe */

Here is the call graph for this function:

Here is the caller graph for this function:

static int simplexedual ( struct rproblem *  RR,
int  j2,
int  bphase2,
int *  pi1,
int *  pbool1 
) [static]

fin simplexe

cette procedure maximise dans le systeme dual soit le cout defini par la colonne des seconds membres (lorsque j2=0), soit le cout defini par la colonne j2

f (A(0,j)<0.0001) zeta=0; provisoire

printf(FT,"zetafoir d=%6.3f a=%15.9f\\\\\n",D[i],A(0,j)) ;

fin j

fin i

nulle ou non, la variable artificielle est chassee de la base duale

Definition at line 555 of file r1.c.

References A, absf(), D, i, J0, MB, NB, pivotage(), VRESULT, and VRVID.

Referenced by simbad().

00559 {
00560         int i,j;
00561         int j1 = 0 ,j3 = 0 ;
00562         float gamma,teta,c1,c2,zeta,tet,pivot ;
00563         float alpha=0;
00564         J0=1;
00565 choix:
00566         *pbool1=1 ; c1=0 ; tet=0 ;
00567         for (i=1 ; i<=MB ; i++)
00568         {
00569                 teta=(bphase2) ? D[i] : A(i,j2) ;
00570                 if (teta < 0)
00571                 {
00572                         *pbool1=1; pivot=0 ;
00573                         for (j=1 ; j<=NB ; j++)
00574                         if (A(i,j)<0) {
00575                           zeta= A(0,j)/ A(i,j) ;
00576                           /*if (A(0,j)<0.0001) zeta=0; provisoire*/
00577                           /*fprintf(FT,"zetafoir d=%6.3f a=%15.9f\\\\\n",D[i],A(0,j)) ;*/
00578                           if (*pbool1
00579                               || zeta>alpha
00580                               || zeta==alpha && pivot>A(i,j))
00581                             {
00582                               *pbool1=0 ;
00583                               alpha=zeta ; j3=j ; pivot= A(i,j) ;
00584                             }
00585                         } /* fin j */ ;
00586                         if (*pbool1) return(VRESULT=VRVID);
00587                         c2=alpha*teta ;
00588                         if (c2>c1 || c2==c1 && teta<tet)
00589                         {
00590                                 c1=c2 ; *pi1=i ; j1=j3 ; tet=teta ;
00591                         } ;
00592                 }
00593         } /* fin i */ ;
00594         if (*pbool1) goto optimum ;
00595         if (pivotage(RR,*pi1,j1)) return(VRESULT);
00596         if (j1==j2) goto sortie ;
00597         if (bphase2 || A(0,j2)>0) goto choix ;
00598 optimum:
00599         if (bphase2) goto sortie ;
00600         /* nulle ou non, la variable artificielle est chassee de la base
00601                         duale */
00602         gamma=0 ;
00603         for (i=1 ; i<=MB ; i++)
00604         if (gamma < absf(A(i,j2)))
00605         {
00606                 gamma=absf(A(i,j2)) ; *pi1=i ;
00607         } ;
00608         if (pivotage(RR,*pi1,j2)) return(VRESULT);
00609 sortie:
00610 } /* fin simplexedual */ ;

Here is the call graph for this function:

Here is the caller graph for this function:

static int validite ( struct rproblem *  RR  )  [static]

fin reduction()

cette procedure verifie, lorsque la base est donnee ou lorsqu'on utilise une matrice des contraintes ayant deja pivote, que le tableau g ou que les tableaux g et b fournis sont compatibles

Definition at line 346 of file r1.c.

References B, COST, G, i, M1, N1, RHS, VRCAL, and VRESULT.

Referenced by simbad().

00350 {       int i,j;
00351         for (i=1 ; i<=M1 ; i++)
00352         {
00353                 if (G[i]<1 || G[i]>N1+M1)
00354                         return(VRESULT=VRCAL) ;
00355                 for (j=i+1 ; j<=M1 ; j++)
00356                         if (G[j]==G[i]) return(VRESULT=VRCAL) ;
00357                 if (COST || RHS)
00358                 {
00359                         for (j=1 ; j<=N1 ; j++)
00360                           if (B[j]==G[i]) return(VRESULT=VRCAL);
00361                 }
00362                 else
00363                 if (G[i]>N1 && G[i]!=N1+i)
00364                 {
00365                         j=G[G[i]-N1] ; G[G[i]-N1]=G[i] ; G[i]=j ;
00366                         i=i-1 ;
00367                 } ;
00368         } ;
00369         if (COST || RHS)
00370         for (j=1 ; j<=N1 ; j++)
00371         {
00372                 if (B[j]<1 || B[j]>N1+M1)
00373                         return(VRESULT=VRCAL) ;
00374                 for (i=j+1 ; i<=N1 ; i++)
00375                         if (B[i]==B[j]) return(VRESULT=VRCAL) ;
00376         }
00377         return(0) ;
00378 } /* fin validite */ ;

Here is the caller graph for this function:

static int voir ( struct rproblem *  RR,
int  v 
) [static]

fin voir

Definition at line 143 of file r1.c.

References TRACE, and voir4().

Referenced by realsimplex(), and simbad().

00144 {//     int i,j ;
00145   if (TRACE<3) return(0) ; voir4(RR,v, 0,0); return(0);
00146 }

Here is the call graph for this function:

Here is the caller graph for this function:

static int voir4 ( struct rproblem *  RR,
int  v,
int  i11,
int  j11 
) [static]

9

appel avant les initialisations

f(v==30){fprintf(FT,"pppivot\(%2d,%2d\):%6.3f",i11,j11,1/ A(i11,j11));

printf(FT,"d=%6.3f a=%15.9f\\\\\n",D[i11],A(0,j11)) ;*provisoire

9

Definition at line 59 of file r1.c.

References A, B, D, E, fprintf(), FT, G, i, ITER, M1, M2, MB, N1, NB, NP, and TRACE.

Referenced by pivotage(), and voir().

00060 {       int i,j ;
00061         if (TRACE<2) return(0) ; if (TRACE<3&&v!=30) return(0) ; /*99*/
00062         if (v==0) { NB=N1 ; M2=M1 ; } ;/* appel avant les initialisations */
00063         fprintf(FT,"m=%2d mb=%2d nb=%2d t=%2d ",M1,MB,NB,ITER) ;
00064         if (v==0) fprintf(FT,"tout debut") ;
00065         if (v==1)fprintf(FT,"situation initiale, contraintes <= , = , >=");
00066         if (v==2) fprintf(FT,"forme standard, contraintes <= , =") ;
00067         if (v==3) fprintf(FT,"lignes ont ete normalisees") ;
00068         if (v==4) fprintf(FT,"colonnes ont ete normalisees") ;
00069         if (v==5) fprintf(FT,"apres norm") ;
00070         if (v==6) fprintf(FT,"forme standard normalisee") ;
00071         if (v==7) fprintf(FT,"egalites eliminees, forme canonique <=") ;
00072 
00073         if (v==8) { fprintf(FT,"methode primale\n") ; return(0) ; } ;
00074         if (v==9) fprintf(FT,"phase 1 primal") ;
00075         if (v==10) fprintf(FT,"variable artificielle primal introduite") ;
00076  if (v==11) {fprintf(FT,"algorithme simplexe primal ph. 1\n"); return(0);};
00077         if (v==12) fprintf(FT,"phase 2 primal") ;
00078         if (v==13) { fprintf(FT,"methode duale\n") ; return(0) ; } ;
00079         if (v==14) fprintf(FT,"phase 1 dual") ;
00080     if (v==15) fprintf(FT,"variable artificielle phase 1 dual introduite");
00081    if (v==16) {fprintf(FT,"algorithme simplexe dual ph. 1\n"); return(0);};
00082         if (v==17) fprintf(FT,"ligne artificielle inutile deplacee") ;
00083         if (v==18) fprintf(FT,"retour necessaire de dual a primal") ;
00084         if (v==19) fprintf(FT,"phase 2 dual") ;
00085 /*if(v==30){fprintf(FT,"pppivot\(%2d,%2d\):%6.3f",i11,j11,1/ A(i11,j11));*/
00086 if (v==30) {fprintf(FT,"pivot(%2d,%2d):%6.3f",i11,j11,1/ A(i11,j11));
00087         fprintf(FT," variables %2d <-> %2d",B[j11],G[i11]) ; };
00088     /*fprintf(FT,"d=%6.3f a=%15.9f\\\\\n",D[i11],A(0,j11)) ;*provisoire*/
00089                 fprintf(FT,"\\\\\n") ; /*99*/
00090 if (v==1)
00091 {       for ( i=0 ; i <= M1 ; i++)
00092         {       if (i==0)
00093                 {       if (E[i] ==1) fprintf(FT,"min   ") ;
00094                         else if (E[i] == -1) fprintf(FT,"max   ") ;
00095                         else fprintf(FT,"\?\?    ") ;
00096                 } else
00097                         if (i+N1 < 10) fprintf(FT," x%1d : ",i+N1) ;
00098                                 else fprintf(FT,"x%2d : ",i+N1) ;
00099                 for ( j=1 ; j <= N1 ; j++)
00100                 {       if (A(i,j) == 0) continue ;
00101                         if (A(i,j) > 0) fprintf(FT,"+") ;
00102                         if (j < 10) fprintf(FT,"%6.3fx%1d ",A(i,j),j) ;
00103                                 else fprintf(FT,"%6.3fx%2d ",A(i,j),j) ;
00104                 } ;
00105                 if (i>0)
00106                 {       if (E[i] ==1) fprintf(FT,"<= ") ;
00107                         else if (E[i] == -1) fprintf(FT,">= ") ;
00108                         else if (E[i] ==0) fprintf(FT,"= ") ;
00109                         fprintf(FT,"%7.3f",D[i]) ;
00110                 } 
00111                 else
00112                         if (D[i]!=0)
00113                         {       if (D[i]>0) fprintf(FT,"+") ;
00114                                 fprintf(FT,"%7.3f",D[i]) ;
00115                         }
00116                 fprintf(FT,"\n") ;
00117         } ;
00118         if (NP==N1) fprintf(FT,"variables hors-base toutes >=0\n") ;
00119         else if (NP==0)
00120            fprintf(FT,"variables hors-base toutes de signe quelconque\n") ;
00121         else fprintf
00122 (FT,"%3d variables hors-base >=0 ,%3d variables libres \n",NP,N1-NP) ;
00123 };
00124         if (TRACE<4) return(0) ;
00125         if (TRACE<5 && (v!=1 ) ) return(0) ;
00126         if (TRACE<6 && (v!=1 && v!=6 ) ) return(0) ;
00127         if (TRACE<7 && (v!=1 && v!=6 && v!=30) ) return(0) ;
00128                 fprintf(FT,"b   ") ;
00129                 for ( j=0 ; j <= NB ; j++)
00130                 { fprintf(FT,"[%2d]=%2d ",j,B[j]) ;
00131                 } ;
00132                 fprintf(FT,"\n") ;
00133         for ( i=0 ; i <= M2 ; i++)
00134         {       fprintf(FT,"g[%2d]=%2d ",i,G[i]) ;
00135                 for ( j=0 ; j <= NB ; j++)
00136                 {       fprintf(FT,"%6.3f       ",A(i,j)) ;
00137                 } ;
00138                 fprintf(FT,"e=%4d d=%7.3f",E[i],D[i]) ;
00139                 fprintf(FT,"\n") ;
00140         } ;
00141         return(0);
00142 } /* fin voir */

Here is the call graph for this function:

Here is the caller graph for this function:

Generated by  doxygen 1.6.2-20100208