/*************************************************************************************************************************************/
/* */
/* R E S O L U T I O N D ' U N S Y S T E M E L I N E A I R E D E D E U X E Q U A T I O N S */
/* E T D E D E U X I N E Q U A T I O N S A ' N ' I N C O N N U E S */
/* P A R U N E M E T H O D E D U T Y P E " R E C U I T S I M U L E " : */
/* */
/* */
/* Fonction : */
/* */
/* Ce programme resoud le systeme */
/* suivant d'equations : */
/* */
/* i=N-1 */
/* S (V ) = SV */
/* i=0 i */
/* */
/* i=N-1 */
/* S (C1 .V ) = SC1V */
/* i=0 i i */
/* */
/* i=N-1 i=N-1 */
/* S (C2 .V ) <= SC2V < S (C2 .V ) */
/* i=0 i-1 i i=0 i i */
/* */
/* Author of '$xtc/recuit_si.21$c' : */
/* */
/* Jean-Francois Colonna (LACTAMME, AAAAMMJJhhmmss). */
/* */
/*************************************************************************************************************************************/
#include "INCLUDES.01.I"
/* Introduit le 20051116102057... */
/*************************************************************************************************************************************/
/* */
/* P A R A M E T R E S D E C O N T R O L E ( O U P A R A M E T R E S " P R I M A I R E S " ) : */
/* */
/*************************************************************************************************************************************/
#define Nvariables \
8 \
/* Nombre de variables. */
#define FACTEUR_DE_L_INCREMENT \
2.00 \
/* Facteur de calcul de 'facteur_de_l_increment'... */
#define PROBABILITE \
0.8 \
/* Probabilite d'agir sur l'une des variables lors de la perturbation aleatoire. ATTENTION, */ \
/* les conventions sont inversees (c'est-a-dire que plus 'PROBABILITE' est proche de 0, */ \
/* plus il y a de chance de perturber la variable courante, alors que plus elle est proche */ \
/* de 1, moins il y a de chance...). */
#define ITERATIONS \
2000000 \
/* Nombre maximal d'iterations avant d'arreter le programme. */
#define PRECIS \
double \
/* Doit-on travailler en entier ('int') ou non ('double') ? */
/*************************************************************************************************************************************/
/* */
/* P A R A M E T R E S D E R I V E E S ( O U P A R A M E T R E S " S E C O N D A I R E S " ) : */
/* */
/*************************************************************************************************************************************/
#define NON_CONVERGENCE \
(ITERATIONS/20) \
/* Nombre maximal d'iterations avant de detecter la non convergence, et de reinitialiser */ \
/* partiellement. */
/*************************************************************************************************************************************/
/* */
/* C O N S T A N T E S : */
/* */
/*************************************************************************************************************************************/
#define INDEX0 \
0
/*************************************************************************************************************************************/
/* */
/* P R O C E D U R E S U T I L E S : */
/* */
/*************************************************************************************************************************************/
#define INTE(x) \
((int)(x)) \
/* Partie entiere. */
#define FLOT(x) \
((double)(x)) \
/* Conversion flottante. */
#define DEBUG(sequence) \
; \
/* Pour n'executer 'sequence' qu'en cas de besoin... */
#define TEST(sequence) \
; \
/* Pour n'executer 'sequence' qu'en cas de besoin... */
#define SOMME_REELLE_MAXIMALE_VARIABLES \
1000 \
/* Valeur maximale a priori de la somme theorique des variables pour generer le cas reel. */
#define REINITIALISATION(probabilite) \
{ \
DEBUG(printf("\n\n reinitialisation :\n");); \
\
SommeVariables=0; \
SommeCoefficients1Variables=0; \
SommeCoefficients2SupVariables=0; \
SommeCoefficients2InfVariables=0; \
\
for (index1=INDEX0 ; index1<Nvariables ; index1++) \
{ \
if (ALEATOIRE_0_p1>=probabilite) \
{ \
switch (methode) \
{ \
case 1: \
{ \
Variables[index1]=INTE(ALEATOIRE_0_p1*(ExacteSommeVariables/Nvariables)); \
break; \
} \
case 2: \
{ \
Variables[index1]=INTE(SOMME_REELLE_MAXIMALE_VARIABLES/Nvariables); \
break; \
} \
case 3: \
{ \
Variables[index1]=INTE((SOMME_REELLE_MAXIMALE_VARIABLES/Nvariables) \
*(-((double)index1/((double)(Nvariables-1)))+1) \
); \
break; \
} \
default: \
{ \
printf("\n methode non implementee"); \
break; \
} \
} \
\
BestVariables[index1]=Variables[index1]; \
/* Initialisation des "meilleures" valeurs rencontrees. */ \
\
SommeVariables=SommeVariables+Variables[index1]; \
SommeCoefficients1Variables=SommeCoefficients1Variables \
+(Variables[index1]*Coefficients1[index1]); \
SommeCoefficients2SupVariables=SommeCoefficients2SupVariables \
+(Variables[index1]*Coefficients2[index1]); \
if (index1>INDEX0) \
{ \
SommeCoefficients2InfVariables=SommeCoefficients2InfVariables \
+(Variables[index1]*Coefficients2[index1-1]); \
} \
else \
{ \
} \
} \
else \
{ \
} \
} \
\
DEBUG(printf("\n somme des variables=%d",SommeVariables);); \
DEBUG(printf("\n somme ponderee 1 des variables=%f",FLOT(SommeCoefficients1Variables));); \
DEBUG(printf("\n somme ponderee 2 des variables=%f",FLOT(SommeCoefficients2SupVariables));); \
DEBUG(printf("\n somme ponderee 3 des variables=%f",FLOT(SommeCoefficients2InfVariables));); \
} \
/* Reinitialisation des variables partielle ou globale... */
#define CumulVariables(somme) \
{ \
somme=somme+Variables[index1]; \
}
#define CumulCoefficients1Variables(somme) \
{ \
somme=somme+(Coefficients1[index1]*Variables[index1]); \
}
#define CumulCoefficients2SupVariables(somme) \
{ \
somme=somme+(Coefficients2[index1]*Variables[index1]); \
}
#define CumulCoefficients2InfVariables(somme) \
{ \
if (index1>INDEX0) \
{ \
somme=somme+(Coefficients2[index1-1]*Variables[index1]); \
} \
else \
{ \
} \
}
/* Procedures diverses de cumul. */
#define StoreVecteur(vecteur,index,valeur) \
{ \
if ((index>=INDEX0) && (index<Nvariables)) \
{ \
vecteur[index]=valeur; \
} \
else \
{ \
printf("\n ATTENTION : un index (%d) sort des limites [%d,%d]",index,INDEX0,Nvariables-1); \
} \
}
/* Rangement avec validation d'un element d'un vecteur. */
/*************************************************************************************************************************************/
/* */
/* G E N E R A T E U R A L E A T O I R E : */
/* */
/*************************************************************************************************************************************/
#define TOUJOURS \
0.00
#define PARFOIS \
0.75
#define JAMAIS \
1.00
/* Quelques probabilites utiles. ATTENTION, les conventions sont inversees (c'est-a-dire */
/* que plus on est proche de 0, plus l'evenement est probable, alors que plus on est proche */
/* de 1, moins l'evenement est probable...). */
extern double srand48();
extern double drand48();
#define ALEATOIRE \
(random())
#define ALEATOIRE_0_p1 \
(ALEATOIRE)
#define ALEATOIRE_m1_p1 \
(2.0*(ALEATOIRE-0.5))
/* Valeur aleatoire dans [0,+1] et dans [-1,+1]. Utilise 'drand48()' ou 'random()'. */
int initialiser_random=VRAI;
int taux=3.0;
double valeur_random=0.5;
double random()
{
int index;
for (index=1 ; index<=((initialiser_random==VRAI) ? 200 : 1) ; index++)
{
int iterer=VRAI;
while (iterer==VRAI)
{
valeur_random=((taux+1)*valeur_random)-(taux*valeur_random*valeur_random);
if ((valeur_random>=0.0) && (valeur_random<=1.0))
{
iterer=FAUX;
}
else
{
}
}
}
initialiser_random=FAUX;
return(valeur_random);
}
/*************************************************************************************************************************************/
/* */
/* P R O G R A M M E : */
/* */
/*************************************************************************************************************************************/
main()
{
int methode=1;
int iteration,iterer,non_convergence;
int index1,index2;
int Variables[Nvariables],SaveVariables[Nvariables],BestVariables[Nvariables];
int ExacteSommeVariables;
int SommeVariables,SaveSommeVariables;
int increment;
PRECIS Coefficients1[Nvariables];
PRECIS ExacteSommeCoefficients1Variables;
PRECIS SommeCoefficients1Variables,SaveSommeCoefficients1Variables;
PRECIS Coefficients2[Nvariables];
PRECIS ExacteSommeCoefficients2Variables;
PRECIS SommeCoefficients2SupVariables;
PRECIS SommeCoefficients2InfVariables;
double facteur_de_l_increment;
StoreVecteur(Coefficients1,0,300);
StoreVecteur(Coefficients1,1,450);
StoreVecteur(Coefficients1,2,670);
StoreVecteur(Coefficients1,3,1150);
StoreVecteur(Coefficients1,4,1600);
StoreVecteur(Coefficients1,5,2100);
StoreVecteur(Coefficients1,6,2800);
StoreVecteur(Coefficients1,7,3300);
StoreVecteur(Coefficients2,0,20);
StoreVecteur(Coefficients2,1,50);
StoreVecteur(Coefficients2,2,100);
StoreVecteur(Coefficients2,3,250);
StoreVecteur(Coefficients2,4,500);
StoreVecteur(Coefficients2,5,1000);
StoreVecteur(Coefficients2,6,2000);
StoreVecteur(Coefficients2,7,3000);
/* Definition a priori des coefficients. ATTENTION, le nombre de ces initialisations ne */
/* peut etre parametrer par 'Nvariables'... */
/*************************************************************************************************************************************/
/* */
/* C O N S T R U C T I O N D E L A S O L U T I O N E X A C T E Q U I S E R A */
/* E N S U I T E R E C H E R C H E E I T E R A T I V E M E N T : */
/* */
/*************************************************************************************************************************************/
printf("\n solution exacte :\n");
ExacteSommeVariables=0;
ExacteSommeCoefficients1Variables=0;
ExacteSommeCoefficients2Variables=0;
for (index1=INDEX0 ; index1<Nvariables ; index1++)
{
int ListeTest[Nvariables]={6,3,1,2,0,0,0,0};
/* Cette liste, associee a 'TEST(...)' permet de forcer les valeurs de 'variable'. */
int variable=INTE(ALEATOIRE_0_p1*(SOMME_REELLE_MAXIMALE_VARIABLES/Nvariables));
TEST(variable=ListeTest[index1];);
printf("\n variables(%d)=%d",index1,variable);
ExacteSommeVariables=ExacteSommeVariables+variable;
ExacteSommeCoefficients1Variables=ExacteSommeCoefficients1Variables+(variable*Coefficients1[index1]);
for (index2=INDEX0 ; index2<variable ; index2++)
{
PRECIS increment=INTE(ALEATOIRE_0_p1*Coefficients2[index1]);
if ((index1>INDEX0) && (increment<=Coefficients2[index1-1]))
{
increment=Coefficients2[index1-1]+1;
}
else
{
}
ExacteSommeCoefficients2Variables=ExacteSommeCoefficients2Variables+increment;
}
}
printf("\n\n somme des variables=%d",ExacteSommeVariables);
printf("\n somme reelle ponderee 1 des variables=%f",FLOT(ExacteSommeCoefficients1Variables));
printf("\n somme reelle ponderee 2 des variables=%f",FLOT(ExacteSommeCoefficients2Variables));
printf("\n");
/*************************************************************************************************************************************/
/* */
/* I N I T I A L I S A T I O N D E L A R E S O L U T I O N I T E R A T I V E : */
/* */
/*************************************************************************************************************************************/
DEBUG(printf("\n\n\n iterations :"););
facteur_de_l_increment=FACTEUR_DE_L_INCREMENT*FLOT(ExacteSommeVariables)/FLOT(Nvariables);
if (facteur_de_l_increment<2.0)
{
printf("\n\n ATTENTION : afin que le calcul de 'increment' ne redonne pas toujours la meme valeur, on majore");
printf("\n facteur=%f",facteur_de_l_increment);
facteur_de_l_increment=2.0;
}
else
{
}
REINITIALISATION(TOUJOURS);
/*************************************************************************************************************************************/
/* */
/* R E S O L U T I O N I T E R A T I V E : */
/* */
/*************************************************************************************************************************************/
iterer=VRAI;
iteration=0;
non_convergence=0;
while (iterer==VRAI)
{
iteration=iteration+1;
if (iteration>ITERATIONS)
{
iterer=FAUX;
/* Trop d'iterations ont ete effectuees. */
}
else
{
}
SommeVariables=0;
SommeCoefficients1Variables=0;
SommeCoefficients2SupVariables=0;
SommeCoefficients2InfVariables=0;
SaveSommeVariables=0;
SaveSommeCoefficients1Variables=0;
for (index1=INDEX0 ; index1<Nvariables ; index1++)
{
CumulVariables(SaveSommeVariables);
CumulCoefficients1Variables(SaveSommeCoefficients1Variables);
SaveVariables[index1]=Variables[index1];
/* Sauvegarde de l'etat avant la perturbation... */
if (ALEATOIRE_0_p1>PROBABILITE)
{
increment=INTE(facteur_de_l_increment*ALEATOIRE_m1_p1);
/* Calcul de la perturbation aleatoire de la variable courante... */
if ((Variables[index1]+increment)>0)
{
Variables[index1]=Variables[index1]+increment;
/* Perturbation aleatoire... */
}
else
{
}
}
else
{
}
CumulVariables(SommeVariables);
CumulCoefficients1Variables(SommeCoefficients1Variables);
CumulCoefficients2SupVariables(SommeCoefficients2SupVariables);
CumulCoefficients2InfVariables(SommeCoefficients2InfVariables);
}
if ( (ABSO(SommeCoefficients1Variables-ExacteSommeCoefficients1Variables)
>=ABSO(SaveSommeCoefficients1Variables-ExacteSommeCoefficients1Variables)
)
|| (ABSO(SommeVariables-ExacteSommeVariables)
>=ABSO(SaveSommeVariables-ExacteSommeVariables)
)
|| ( (ExacteSommeCoefficients2Variables>=SommeCoefficients2SupVariables)
|| (ExacteSommeCoefficients2Variables<SommeCoefficients2InfVariables)
)
)
/* Cas ou l'etat perturbe est moins bon que l'etat anterieur : */
{
non_convergence=non_convergence+1;
/* Detecteur de non convergence. */
if (non_convergence < NON_CONVERGENCE)
{
for (index1=INDEX0 ; index1<Nvariables ; index1++)
{
Variables[index1]=SaveVariables[index1];
/* On revient alors a l'etat anterieur... */
}
}
else
{
REINITIALISATION(PARFOIS);
}
}
else
/* Cas ou l'etat perturbe est meilleur que l'etat anterieur : */
{
non_convergence=0;
/* Reinitialisation du detecteur de non convergence. */
if ( (ExacteSommeCoefficients2Variables<SommeCoefficients2SupVariables)
&& (ExacteSommeCoefficients2Variables>=SommeCoefficients2InfVariables)
)
{
for (index1=INDEX0 ; index1<Nvariables ; index1++)
{
BestVariables[index1]=Variables[index1];
/* En tout etat de cause, on memorise ce resultat... */
}
DEBUG(printf("\n iteration=%d",iteration););
DEBUG(printf("\n somme des variables=%d",SommeVariables););
DEBUG(printf("\n somme ponderee 1 des variables=%f",FLOT(SommeCoefficients1Variables)););
DEBUG(printf("\n somme ponderee 2 des variables=%f",FLOT(SommeCoefficients2SupVariables)););
DEBUG(printf("\n somme ponderee 3 des variables=%f",FLOT(SommeCoefficients2InfVariables)););
}
else
{
}
if ( (SommeCoefficients1Variables==ExacteSommeCoefficients1Variables)
&& (SommeVariables==ExacteSommeVariables)
&& (ExacteSommeCoefficients2Variables<SommeCoefficients2SupVariables)
&& (ExacteSommeCoefficients2Variables>=SommeCoefficients2InfVariables)
)
{
printf("\n\n une solution exacte a ete trouvee\n");
iterer=FAUX;
/* S'il correspond a l'etat "reel", on peut s'arreter... */
}
else
{
}
}
}
/*************************************************************************************************************************************/
/* */
/* E D I T I O N D E L A S O L U T I O N T R O U V E E : */
/* */
/*************************************************************************************************************************************/
printf("\n\n meilleurs resultats :\n");
SommeVariables=0;
SommeCoefficients1Variables=0;
SommeCoefficients2SupVariables=0;
SommeCoefficients2InfVariables=0;
for (index1=INDEX0 ; index1<Nvariables ; index1++)
{
printf("\n variables(%d)=%d",index1,BestVariables[index1]);
CumulVariables(SommeVariables);
CumulCoefficients1Variables(SommeCoefficients1Variables);
CumulCoefficients2SupVariables(SommeCoefficients2SupVariables);
CumulCoefficients2InfVariables(SommeCoefficients2InfVariables);
}
printf("\n somme des variables=%d",SommeVariables);
printf("\n somme ponderee 1 des variables=%f",FLOT(SommeCoefficients1Variables));
printf("\n somme ponderee 2 des variables=%f",FLOT(SommeCoefficients2SupVariables));
printf("\n somme ponderee 3 des variables=%f",FLOT(SommeCoefficients2InfVariables));
if ( (ExacteSommeCoefficients2Variables<SommeCoefficients2SupVariables)
&& (ExacteSommeCoefficients2Variables>=SommeCoefficients2InfVariables)
)
{
}
else
{
printf("\n les relations d'inegalite ne sont pas satisfaites");
}
printf("\n");
}