yunchou.txt

运筹学算法

 
2、运筹学
 （1）BRANCH：分枝定界算法
#include <stdio.h> 
#define len sizeof(struct node)
typedef struct node{
   float bound;
   int  staus[50];
   struct node *next;
   }node;
int item[50],wl,n,state[50];
float value[50],weight[50],max_value,ratio[50];

void dele(node *father,node *current){
 if(current->next==NULL)
  {father->next=NULL;
  return;
  }
 father->next=current->next;
}

void init(node *father,node *son){
 int i;
 father->next=son;
 for(i=0;i<n;i++)
  son->staus[i]=0;
 son->next=NULL;
}

void branch(){
 int i,t,j;
 float diff,sum=0,sum_value=0;
 node *head,*sonbrother,*father,*son,*prenode,*p,*q;
 head=prenode=(node *)malloc(len);
 father=(node *)malloc(len);
 init(prenode,father);
 father->bound=32768;
 while(head->next!=NULL)
  {
 /*1*/   son=(node *)malloc(len);
  init(father,son);
  for(i=0;i<n&&father->staus[i]!=0;i++)
   son->staus[i]=father->staus[i];
  t=i;
  son->staus[t]=-(t+1);
  sum=0;
  sum_value=0;
  for(j=0;j<t+1&&son->staus[j]!=0;j++)
   if(son->staus[j]>0)
   {sum=sum+weight[item[j]];
   sum_value=sum_value+value[item[j]];
   }
  while(sum!=wl&&son->staus[n-1]==0)
   {diff=wl-(sum+weight[item[j]]);
   if(diff>=0)
    {sum=sum+weight[item[j]];
    sum_value=sum_value+value[item[j]];
    }
   else
    {sum=wl;
    sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];
    }
   j++;
   }
  son->bound=sum_value;
      /*2*/     sonbrother=(node *)malloc(len);
  init(son,sonbrother);
  for(i=0;i<t;i++)
   sonbrother->staus[i]=father->staus[i];
  sonbrother->staus[t]=t+1;
  sum=0;
  sum_value=0;
  for(j=0;j<t+1&&sonbrother->staus[j]!=0;j++)
   if(sonbrother->staus[j]>0)
   {sum=sum+weight[item[j]];
   sum_value=sum_value+value[item[j]];
   }
  if(sum>wl)
   {sonbrother->bound=-32768;
   dele(son,sonbrother);
   }
  else
   {while(sum!=wl&&sonbrother->staus[n-1]==0)
    {diff=wl-(sum+weight[item[j]]);
    if(diff>=0)
     {sum=sum+weight[item[j]];
     sum_value=sum_value+value[item[j]];
     }
    else
     {sum=wl;
     sum_value=sum_value+(1+diff/weight[item[j]])*value[item[j]];
     }
    j++;
    }
   sonbrother->bound=sum_value;
   }
  dele(prenode,father);
  father=prenode->next;
  if(son->staus[n-1]!=0)
   {if(son->next!=NULL)
    {max_value=sonbrother->bound;
    for(i=0;i<n;i++)
     state[i]=sonbrother->staus[i];
    dele(son,sonbrother);
    dele(prenode,father);
    father=prenode->next;
    }
   else
    {max_value=son->bound;
    for(i=0;i<n;i++)
     state[i]=son->staus[i];
    dele(prenode,father);
    }
   q=head;
   p=head->next;
   while((p!=NULL)&&(p->bound<=max_value))
    {dele(q,p);
     p=q->next;
      }
   if(p!=NULL)
    {prenode=q;
    father=p;
    }
    else
    return;
   }
  else
   if(father->next!=NULL)
    {prenode=prenode->next;
    father=father->next;
    }
  }
 return;
}

int getmin(){
 int i;
 float amin=weight[0];
 for(i=1;i<n;i++)
  if(amin>weight[i])
   amin=weight[i];
 return amin;
}

void sort(){
 int i,j,exchange=1;
 float temp1,temp2;
 for(i=0;i<n;i++)
  ratio[i]=value[i]/weight[i];
 for(j=n-1;j>=0&&exchange==1;j--)
  {exchange=0;
  for(i=0;i<j;i++)
   if(ratio[i+1]>ratio[i])
    {exchange=1;
    temp1=ratio[i+1];ratio[i+1]=ratio[i];ratio[i]=temp1;
    temp2=item[i+1];item[i+1]=item[i];item[i]=temp2;
    }
  }

}

void main(){
 int i,j;
 float sum=0;
 clrscr();
 printf(" Welcome to the BRANCH_BOUND system! ");
 printf("number of the materials=?         ");
 scanf("%d",&n);
 printf("maximun weigh of the problem=?    ");
 scanf("%d",&wl);
 for(i=0;i<n;i++)
  {item[i]=i;
  printf(" ******************* ");
  printf("input item%d data! ",i+1);
  printf("******************* ");
  printf("weight %d=?      ",i+1);
  scanf("%f",&weight[i]);
  printf("value %d=?       ",i+1);
  scanf("%f",&value[i]);
  }
 if((getmin())>wl)
  {printf(" There is no solution of the problem!");
  exit(0);
  }
 for(i=0;i<n;i++)
  sum=sum+weight[i];
 if(sum<=wl)
  {printf(" All the materials can be loaded!");
  exit(0);
  }
 sort();
 branch();
 printf(" The maximum value of the materials is  %f   ",max_value);
 printf(" including the following materials ");
 sum=0;
 for(i=0;i<n;i++)
  if(state[i]>0)
   {sum=sum+weight[item[i]];
   printf("%d ",item[i]+1);
   }
 printf(" The weight of the materials is  %f   ",sum);
 getch();
}

 （2）CHAIN：马尔可夫链算法
#include <stdio.h>
#include <math.h>

double a[10][10];

void Guass(int n){
 int i,j,k;
 double t;
 for(k=0;k<n-1;k++)
  {t=a[k][k];
  for(j=k;j<n;j++)
   a[k][j]=a[k][j]/t;
  for(i=0;i<n-1;i++)
   if(i!=k)
    {t=a[i][k]/a[k][k];
    for(j=k;j<n;j++)
     a[i][j]=a[i][j]-a[k][j]*t;
    }
  }
 return;
}


void chain(){
 static double p[10][10],pr[10],diff,table[100][10],pnew[10][10],ptemp[10][10],temp[10],exr[10][10];
 int n,i,j,k,s,m,found,inr,inc;
 printf("Welcome to the MARKOV CHAIN ANALYSIS system! ");
 printf("how many states =?        ");
 scanf("%d",&n);
 printf(" the steady transmit possibility of step 1 ? ");
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   scanf("%lf",&p[i][j]);
 printf(" the initiate state of step 1 ? ");
 for(i=0;i<n;i++)
  scanf("%lf",&pr[i]);
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   pnew[i][j]=p[i][j];
 for(i=0;i<n;i++)
  table[0][i]=pr[i];
 printf("  step 1");
 for(i=0;i<n;i++)
  {printf(" ");
  for(j=0;j<n;j++)
   printf("%f ",p[i][j]);
  }
 printf(" ");
 for(k=2;k<100;k++)
  {for(j=0;j<n;j++)
   {temp[j]=0;
   for(i=0;i<n;i++)
    temp[j]=temp[j]+pr[i]*pnew[i][j];
   }
  for(i=0;i<n;i++)
   table[k-1][i]=temp[i];
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    {ptemp[i][j]=0;
    for(m=0;m<n;m++)
     ptemp[i][j]=ptemp[i][j]+p[i][m]*pnew[m][j];
    }
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    pnew[i][j]=ptemp[i][j];
  for(j=0;j<n;j++)
   {for(i=0;i<n-1;i++)
    {
    for(m=i+1;m<n;m++)
     {diff=pnew[i][j]-pnew[m][j];
     if(diff<0)
      diff=-diff;
     if(diff>0.001)
      {found=0;
      break;
      }
     found=1;
     }
    if(diff>0.001) break;
    }
   if(diff>0.0001) break;
   }
  if(found==0)
   {if(k%5==0)
    {printf("  step %d",k);
    for(i=0;i<n;i++)
     {printf(" ");
     for(j=0;j<n;j++)
      printf("%f ",pnew[i][j]);
     }
    getch();
    }
   if(k>=100)
    {printf(" steady_state probability have not been detained in 100");
    return;
    }
   }
  else
   {printf(" step %d",k);
   for(i=0;i<n;i++)
    {printf(" ");
    for(j=0;j<n;j++)
     printf("%f ",pnew[i][j]);
    }
   break;
   }
  }
        for(j=0;j<n;j++)
   {temp[j]=0;
   for(i=0;i<n;i++)
    temp[j]=temp[j]+pr[i]*pnew[i][j];
   }
  for(i=0;i<n;i++)
   table[k][i]=temp[i];
  printf(" The steady-state probability of being in  ");
  for(j=0;j<n;j++)
   printf("state %d  is %f ",j,pnew[n-1][j]);
  printf("probability of being in state ");
  for(i=0;i<=k;i++)
   {printf("%d",i);
   for(j=0;j<n;j++)
    printf(" %f",table[i][j]);
   printf(" ");
   if(i%10==0) getch();
   }

  for(s=0;s<n;s++)
   { inr=0;
   for(j=0;j<n;j++)
    if(j==s)
     continue;
    else
     {inc=0;
     for(i=0;i<n;i++)
      if(i==s)
       continue;
      else
       {
       a[inr][inc]=-p[j][i];
       if(j==i)
        a[inr][inc]=1+a[inr][inc];
       inc++;
       }
     inr++;
     }
   for(i=0;i<n-1;i++)
    a[i][n-1]=1;
   Guass(n);
   i=0;
   for(j=0;j<n;j++)
    if(j!=s)
     exr[j][s]=a[i++][n-1];
    else
     exr[j][s]=1/pnew[n-1][s];
   }
  printf(" Table of expected first passage times and recurrence times");
  for(i=0;i<n;i++)
   {printf(" %d",i);
   for(j=0;j<n;j++)
    printf(" %f",exr[i][j]);
   }
}

void main(){
 clrscr();
 chain();
 getch();
}

 （3）DECISION：贝叶斯决策方法
#include <stdio.h>
#include <math.h>

#define pi 3.14159
#define p(x,t) exp(-(x-t)*(x-t)/20)/sqrt(20*pi)

void decision(){
 int i,j,type,m,n,flag,state[5],index;
 float xx,a[5][5],p[5],e[5],sum,decision;
 printf("Welcome to the DECISION_STSTEM!");
 printf(" type of the problem,max(key ?0?)or min(key ?1?)?   ");
 scanf("%d",&type);
 printf("type of the decision,without data(key?0?)or with data(key?1?)?   ");