ArcTan

dfs
随笔 - 16, 文章 - 117, 评论 - 6, 引用 - 0
数据加载中……

LinerProgramming(单纯型法---1)

LinerProgramming,线性规划。是运筹学的一个重要分支。
1947年单捷格(G.B.Dantzing)提出了一般LP规划问题的求解方法———单纯型法(simplex algorithm)。
这里是用到没有改进的单纯型法,输入数据的标准型^..^

该学学改进的单纯型法了。

线性规划问题还是有很多用的,是个好模型!!!
#include<stdio.h>
#include
<string.h>
#include
<math.h>
#define inf 10000000.0
int n,m;
int g[1005],q[1005],p[1005];
double b[1005],c[1005],x[1005],a[1005][1005];

//********数据输入、初始化*************
int init()
{
    
int i,j;
//********数组初始化**********
    memset(a,0,sizeof(a));
    memset(b,
0,sizeof(b));
    memset(c,
0,sizeof(c));
    memset(x,
0,sizeof(x));
    memset(q,
0,sizeof(q));
    printf(
"请输入单纯型表的标准型:\n");
//********输入数据************
    scanf("%d%d",&m,&n);
    
for (i=1; i<=n ; i++ )
        scanf(
"%lf",&c[i]);
    
for (i=1; i<=n ; i++ )
        scanf(
"%d",&p[i]);
    
for (i=1; i<=m ; i++ )
    {
        
for (j=1; j<=n ; j++ )
            scanf(
"%lf",&a[i][j]);
        scanf(
"%lf",&b[i]);
    }
//**********初始化单纯型表****
    for (i=1; i<=m ; i++ )
        g[i]
=i,q[i]=1,a[i][n+1]=b[i],x[i]=b[i];
    
for (j=1; j<=n ; j++ )
        a[m
+1][j]=c[j];
    
for (j=n+1; j>m ; j-- )
    {
        
for (i=1; i<=m ; i++ )
            a[m
+1][j]-=c[i]*a[i][j];
    }
}
//**********结果输出********************
int print(int result)
{
    
int i;
    
double sum;
    
if (result==-1)
    {
        printf(
"无可行解\n");
        
return ;
    }
    
if (result==-2)
    {
        printf(
"无界解\n");
        
return ;
    }
    
if (result==-3)
    {
        printf(
"无穷多最优解。其中一个是:\n");
        sum
=0.0;
        
for (i=1; i<=n ; i++ )
            sum
+=x[i]*c[i];
        
for (i=1; i<n ; i++ )
            printf(
"%.4lf ",x[i]);
        printf(
"%.4lf\n",x[n]);
        
return ;
    }
    printf(
"有最优解:\n");
    sum
=0.0;
    
for (i=1; i<=n ; i++ )
        sum
+=x[i]*c[i];
    printf(
"%.4lf\n",sum);
    
for (i=1; i<n ; i++ )
        printf(
"%.4lf ",x[i]);
    printf(
"%.4lf\n\n",x[n]);
    
return ;
}
//***********检查单纯型表***************
int check()
{
    
int i,j,flag,flg,mj;
    
double max;
    flag
=0;
    flg
=0;
    
for (j=1; j<=n ; j++ )
    {
        
if (a[m+1][j]>0.0)
        {
            flag
=1;
            max
=0.0;
            
for (i=1; i<=m ; i++ )
                
if (a[i][j]>max)
                    max
=a[i][j],mj=j;
            
if (max>0.0)
                flg
=1;
        }
    }
    
if (!flag)
    {
        
for (i=1; i<=m ; i++ ) //判断是否无可行解
        {
            
if (p[g[i]]&&a[i][n+1]!=0.0)
                
return -1;
        }

        
for (j=1; j<=n ; j++ ) //判断是否有无穷多最优解
            if (!q[j]&&a[m+1][j]==0.0)
                
return -3;
        
return 0;//唯一最优解
    }
    
if (!flg)
        
return -2;//无界解

    
return mj;//找到最大的那个a[m+1][j]作为换入变量
}
//*********找到最小的那个数*************总是能找到的????
int f_min(int r)
{
    
int i,mi;
    
double min;
    min
=inf;
    
for (i=1; i<=m ; i++ )
        
if (a[i][r]!=0.0&&a[i][n+1]/a[i][r]>0&&a[i][n+1]/a[i][r]<min)
            min
=a[i][n+1]/a[i][r],mi=i;
    printf(
"%.4lf ",min);
    
return mi;//确定为换出变量
}
//********guass消元法进行迭代***********
int guass(int k,int r)
{
    
int i,j;
    
for (j=n+1; j>=1 ; j-- ) //行变换
        if (j!=r)
            a[k][j]
/=a[k][r];
    a[k][r]
=1.0;
    
for (i=1; i<=m+1 ; i++ ) //每一行进行变换
        if (i!=k)
        {
            
for (j=1; j<=n+1 ; j++ )
                
if (j!=r)
                    a[i][j]
-=a[k][j]*a[i][r];
            a[i][r]
=0.0;
        }
    q[g[k]]
=0;
    g[k]
=r;
    q[r]
=1;
    memset(x,
0,sizeof(x));
    
for (i=1; i<=m ; i++ )
        x[g[i]]
=a[i][n+1];
}
int work()
{
    
int i,j,r,k;
    
while (1)
    {
        
for (i=1; i<=m+1 ; i++ )
        {
            
for (j=1; j<=n+1 ; j++ )
                printf(
"%.4lf ",a[i][j]);
            printf(
"%d\n",g[i]);
        }
        
for (j=1; j<=n ; j++ )
            printf(
"%.4lf ",x[j]);
        printf(
"%.4lf\n",x[j]);
        r
=check();
        
if (r<=0)
            
return r;
        k
=f_min(r);
        printf(
"%d %d\n\n",k,r);

        guass(k,r);
    }
}
int main()
{
    
int result;
    init();
    result
=work();
    print(result);
    
return 0;
}


有时间得去poj,zoj上找找线性规划的题目来下写写。嘿嘿,

posted on 2012-04-05 14:35 wangs 阅读(520) 评论(0)  编辑 收藏 引用 所属分类: ACM-模拟


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理