修正单纯形.cpp

一些比较难找的算法代码 中国剩余定理.cpp 高斯消元.cpp 红黑树.cpp 排序后第k位置数.cpp 修正单纯形.c

# include <iostream.h>
# include <stdlib.h>
# include "rat.h"
# define MAX 100
rat a[MAX][MAX],b[MAX],c_second[MAX],c[MAX],u[MAX][MAX],y[MAX],t[MAX],
col[MAX];
rat z0,sum,z,min,theta;
int B[MAX];
bool N[MAX];
int n,m,flag;
int s,r;
int digit(int a)
{
        if(a==0) return 1;
        int k=0;
        while(a){
                k++;
                a/=10;  
        }
        return k;       
}
int cal(rat x)
{
        int count=0;
        if(x<0) count++;
        if(x.Q!=1) count+=1+digit(x.Q);
        count+=digit(abs(x.P));
        return count;   
}
int output(rat num)
{
        int i;
        for(i=cal(num);i<=8;i++) cout<<' ';
        cout<<num;
        return 0;       
}
int table()
{
        int i,j;
        for(i=0;i<m;i++){
                output(t[i]);cout<<'|';
                for(j=0;j<m;j++) output(u[i][j]);
                cout<<endl;
        }
        output(z0); cout<<'|';
        for(i=0;i<m;i++)output(y[i]);
        cout<<endl;
        return 0;
}
int list()
{
        int i;
        for(i=0;i<m;i++) {
                        output(col[i]);
                        cout<<endl;
        }
        output(z);
        cout<<endl;
        return 0;
}
int main()
{
        int i,j;
        while(cin>>n>>m){
                for(i=0;i<m;i++)
                for(j=0;j<n;j++) cin>>a[i][j];
                for(i=0;i<n;i++) cin>>c_second[i];
                for(i=0;i<m;i++) cin>>b[i];
                //first stage;
                cout<<"第一阶段:"<<endl;
                for(i=0;i<n+m;i++) c[i]=(i<n?0:1);
                for(i=0;i<m;i++)
                for(j=n;j<n+m;j++) a[i][j]=(i==(j-n));
                for(i=0;i<m;i++)
                for(j=0;j<m;j++) u[i][j]=(i==j);
                for(i=0;i<m;i++) y[i]=1;
                for(i=0,z0=0;i<m;i++) {
                        t[i]=b[i];
                        z0=z0+b[i];
                }
                for(i=0;i<m;i++) B[i]=n+i;
                for(i=0;i<n+m;i++) N[i]=(i<n?0:1);
                n+=m;
                table();
                while(1){
                        z=0;s=-1;
                        for(i=0;i<n;i++)if(!N[i]) {
                                for(j=0,sum=0;j<m;j++) sum=sum+y[j]*a[j][i];                    
                                sum=sum-c[i];
                                if(sum>z) {
                                        z=sum;
                                        s=i;
                                }
                        }
                        if(s==-1){
                                //best solution found;
                                if(z0!=0) {
                                        cout<<"没有可行解"<<endl;
                                        flag=1;
                                }
                                break;
                        }
                        int mflag=0;r=-1;
                        for(i=0;i<m;i++) {
                                col[i]=0;
                                for(j=0;j<m;j++) 
                                        col[i]=col[i]+u[i][j]*a[j][s];
                                if(col[i]>0){
                                        if(!mflag||t[i]/col[i]<min){
                                                min=t[i]/col[i];
                                                mflag=1;
                                                r=i;
                                        }
                                }
                        }
                        cout<<"此时枢列"<<s+1<<"为："<<endl;
                        list();
                        //第一阶段下面情况不存在        
                        if(r==-1) {
                                cout<<"没有最优解，即趋于负无穷"<<endl; 
                                flag=1;
                                break;
                        }
                        cout<<"枢元素为："<<'L'<<r+1<<s+1<<endl;
                        //new table
                        for(i=0;i<m;i++)if(i!=r){
                                theta=col[i]/col[r];
                                for(j=0;j<m;j++) u[i][j]=u[i][j]-theta*u[r][j];
                                t[i]=t[i]-t[r]*theta;
                        }
                        theta=z/col[r];
                        for(i=0;i<m;i++) y[i]=y[i]-theta*u[r][i];
                        z0=z0-theta*t[r];
                        for(i=0;i<m;i++) u[r][i]=u[r][i]/col[r];
                        t[r]=t[r]/col[r];
                        N[B[r]]=0;B[r]=s;
                        cout<<"实行基转换，得新表:"<<endl;
                        table();
                }
                if(flag) break;
                //second stage;
                cout<<"下面进入第二阶段:"<<endl;
                n-=m;
                for(i=0;i<n;i++) c[i]=c_second[i];
                for(i=0,z0=0;i<m;i++) z0=z0+t[i]*c[B[i]];
                for(j=0;j<m;j++){
                        y[j]=0;
                        for(i=0;i<m;i++) y[j]=y[j]+u[i][j]*c[B[i]];
                }
                table();
                while(1){
                        z=0;s=-1;
                        for(i=0;i<n;i++)if(!N[i]) {
                                for(j=0,sum=0;j<m;j++) sum=sum+y[j]*a[j][i];                    
                                sum=sum-c[i];
                                if(sum>z) {
                                        z=sum;
                                        s=i;
                                }
                        }
                        if(s==-1){
                                //best solution found;
                                cout<<"最优值为: "<<z0<<endl;
                                cout<<"此时解为"<<endl;
                                for(i=0;i<m;i++) cout<<'x'<<B[i]+1<<" = "<<t[i]<<endl;
                                break;
                        }
                        int mflag=0;r=-1;
                        for(i=0;i<m;i++) {
                                col[i]=0;
                                for(j=0;j<m;j++) 
                                        col[i]=col[i]+u[i][j]*a[j][s];
                                if(col[i]>0){
                                        if(!mflag||t[i]/col[i]<min){
                                                min=t[i]/col[i];
                                                mflag=1;
                                                r=i;
                                        }
                                }
                        }
                        cout<<"此时枢列"<<s+1<<"为:"<<endl;
                        list();
                        //第一阶段下面情况不存在        
                        if(r==-1) {
                                cout<<"The optimal solution --> -oo"<<endl; 
                                flag=1;
                                break;
                        }
                        cout<<"枢元素为："<<'L'<<r+1<<s+1<<endl;
                        //new table
                        for(i=0;i<m;i++)if(i!=r){
                                theta=col[i]/col[r];
                                for(j=0;j<m;j++) u[i][j]=u[i][j]-theta*u[r][j];
                                t[i]=t[i]-t[r]*theta;
                        }
                        theta=z/col[r];
                        for(i=0;i<m;i++) y[i]=y[i]-theta*u[r][i];
                        z0=z0-theta*t[r];
                        for(i=0;i<m;i++) u[r][i]=u[r][i]/col[r];
                        t[r]=t[r]/col[r];
                        N[B[r]]=0;B[r]=s;
                        cout<<"实行基转换，得新表"<<endl;
                        table();
                }
        }
        return 0;
}