C语言编单纯形法程序怎么写

发布网友发布时间：2022-04-23 14:30

共1个回答

热心网友时间：2023-05-06 14:19

#include<stdio.h>
#include<math.h>

intm;  //记录约束条件方程组的个数
intn;  //记录未知量的个数
floatM=1000000.0;
floatA[100][100];   //用于记录方程组的数目和系数
floatC[100];      //用于存储目标函数中各个变量的系数
floatb[100];      //用于存储常约束条件中的常数
floatCB[100];     //用于存储基变量的系数
floatseta[100];   //存放出基与入基的变化情况
floatcn[100];   //存储检验数矩阵
floatx[100];
intnum[100];    //用于存放出基与进基变量的情况
floatZ=0;   //记录目标函数值

voidshuru();
voidprint();
intmincz();
intfind_line(int a);
voidexchange(int a,int b);
intmain()
{
    int i,j=0;
    int p,q,temp;  //q：换入，p：换出
    shuru();
   printf("\n--------------------------------------------------------------------------\n");
    printf(" \tCB\tXB\tb\t");
    for(i=0; i<n; i++)
        printf(" X(%d)\t",i+1);
    for(i=0; i<n; i++)
        x[i]=0;
    printf("\n");
    while(1) {
        q=mincz();
        if(q==-1) {
            print();
            printf("\n所得解已经是最优解!\n");
            printf("\n最优解为:\n");
            for(j=0; j<m; j++) {
                temp=num[j]-1;
                x[temp]=b[j];
            }
            for(i=0; i<n; i++) {
                printf("x%d=%.2f",i+1,x[i]);
                Z=Z+x[i]*C[i];
            }
            printf("Z=%.2f",Z);
            break;
        }
        print();
        p=find_line(q);
        printf("\np=%d,q=%d",p,q);
        if(q==-1) break;
        exchange(p,q);
    }
    return 0;
}
intmincz()
{
    int i,k=0;
    int flag=0; //检验数标记
    float min=0;
    for(i=0; i<n; i++)
        if(cn[i]>=0)
            flag=1;
        else {
            flag=0;
            break;
        }
    if(flag==1)
        return -1;
        //进行到此处，说明存在<0的检验数
        //找到最小的检验数，作为换入变量
    for(i=0; i<n; i++) {
        if(min>cn[i]) {
            min=cn[i];
            k=i;
        }
    }
    return k;
}
intfind_line(int a)
{
    int i,k,j;
    int flag=0;
    float min;
    k=a;
    for(i=0; i<m; i++)
        if(A[i][k]<=0)
            flag=1;
        else {
            flag=0;
            break;
        }
    if(flag==1) {
        printf("\n该线性规划无最优解!\n");
        return -1;
    }
    for(i=0; i<m; i++) {
        if(A[i][k]>0)
            seta[i]=b[i]/A[i][k];
        else seta[i]=M;
    }
    min=M;
    for(i=0; i<m; i++) {
        if(min>=seta[i]) {
            min=seta[i];
            j=i;
        }
    }
    num[j]=k+1;
    CB[j]=C[k];
    return j;
}
voidexchange(int p,int q)
{
    int i,j,c,l;
    float temp1,temp2,temp3;
    c=p; //行号，换出
    l=q; //列号，换入
    temp1=A[c][l];  //A[c][l]主元
    b[c]=b[c]/temp1;
    for(j=0; j<n; j++)
        A[c][j]=A[c][j]/temp1;  //主元化为1
    for(i=0; i<m; i++) {
        if(i!=c)
            if(A[i][l]!=0) {
                temp2=A[i][l];
                b[i]=b[i]-b[c]*temp2;
                //主元所在列，其余元素化为0
                for(j=0; j<n; j++)
                    A[i][j]=A[i][j]-A[c][j]*temp2;
            }
    }
    temp3=cn[l];
    for(i=0; i<n; i++)
        cn[i]=cn[i]-A[c][i]*temp3;
}
voidprint()
{
    int i,j=0;
   printf("\n--------------------------------------------------------------------------\n");
    for(i=0; i<m; i++) {
        printf("%8.2f\tX(%d) %8.2f",CB[i],num[i],b[i]);
        for(j=0; j<n; j++)
            printf("%8.2f ",A[i][j]);
        printf("\n");
    }
   printf("\n--------------------------------------------------------------------------\n");
    printf("\t\t\t");
    for(i=0; i<n; i++)
        printf(" %8.2f",cn[i]);
   printf("\n--------------------------------------------------------------------------\n");
}
voidshuru()
{
    int i,j; //循环变量
    int k;
    printf("请输入线性规划问题的约束条件个数M：");
    scanf("%d",&m);
    printf("请输入线性规划问题的决策变量个数N：");
    scanf("%d",&n);
    printf("\n请输入方程组的系数矩阵A(%d行%d列):\n",m,n);
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
            scanf("%f",&A[i][j]);
    printf("\n请输入初始基变量的数字代码矩阵:\n");
    for(i=0; i<m; i++)
        scanf("%d",&num[i]);
    printf("\n请输入方程组右边的值矩阵b:\n");
    for(i=0; i<m; i++)
        scanf("%f",&b[i]);
    printf("\n请输入目标函数各个变量的系数所构成的系数阵C:\n");
    for(i=0; i<n; i++)
        scanf("%f",&C[i]);
    for(i=0; i<n; i++)
        cn[i]=-C[i];
    for(i=0; i<m; i++) {
        k=num[i]-1;
        CB[i]=C[k];
    }
  }