wangdan.cpp

实现线性规划的单纯性法

// bbb.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include<iostream.h>

#include<math.h>

#define M 10000

//全局变量

 float matrix[30][30];//核心矩阵表

 int m=0,n=0,t=0;//m:结构向量的个数

                 //n:约束不等式个数

                 //t:目标函数类型：－1代表求求最小值，1代表求最大值

//输入接口函数

void premeter()

{

     //读入所求问题的基本条件

  cout<<"－－－－－－－－－－参 数 输 入－－－－－－－－－－－"<<endl;

  cout<<"请按提示输入下列参数："<<endl<<endl;

    cout<<"  结构向量数m:  "<<"   m=  ";

    cin>>m;

    cout<<endl<<"  约束不等式数n:"<<"   n=  ";

    cin>>n;

   int i,j;

   //初始化核心向量

   for (i=0;i<=n+1;i++)

    for (j=0;j<=m+n+n;j++) 

         matrix [i][j]=0;

   //读入约束条件

   cout<<endl<<"  约束方程矩阵的系数及不等式方向（1代表<=,-1代表>=）:"<<endl<<endl<<"          ";

   for (i=1;i<=m;i++)

       cout<<"   x"<<i;

       cout<<"  不等式方向 "<<" 常数项"<<endl;

   for (i=1;i<=n;i++) 

    { 

      cout<<"    不等式"<<i<<"  ";

      for (j=1;j<=m+2;j++) 

          cin>>matrix [i][j];

    }

 

  for (i=1;i<=n;i++)

     { 

       matrix [i][0]=matrix [i][m+2];

       matrix [i][m+2]=0;

     }

  //读入目标条件

  cout<<endl<<endl<<" 目标函数的系数及类型（求最小值:1；求最大值:-1）:"<<endl<<endl<<"                ";

   for(i=1;i<=m;i++)

        cout<<"x"<<i<<"   ";

  cout<<"类型"<<endl<<"  ";

  cout<<"  目标函数:   ";

   for (i=1;i<=m;i++)

     cin>>matrix [0][i];

     cin>>t;

  //矩阵调整

  if(t==-1) 

      for(i=1;i<=m;i++) 

          matrix [0][i]=(-1)*matrix [0][i];

  for(i=1;i<=n;i++)

  { 

      matrix [i][m+i]=matrix [i][m+1];

         if(i!=1)

             matrix [i][m+1]=0;

  }

}

 

//算法函数

void calculate()

{

    int i,j,flag,temp1,temp2,h,k=0,temp3[10];

    float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c;

    //初始化

  for(i=1;i<=n;i++) 

     temp3[i]=0;

   for(i=0;i<11;i++)

   {    temp4[i]=0;

       temp5[i]=0;

   }

    for(i=1;i<=n;i++)

  {

     if(matrix [i][m+i]==-1)

      {

        matrix [i][m+n+i]=1;

        matrix [0][m+n+i]=M;

        temp3[i]=m+n+i;

      }

     else 

         temp3[i]=m+i;

  }

     for(i=1;i<=n;i++)

           temp4[i]=matrix [0][temp3[i]];

 

     //循环求解

do{   

    for(i=1;i<=m+n+n;i++)

      {  

        a=0;

        for(j=1;j<=n;j++)

           a+=matrix [j][i]*temp4[j];

           matrix [n+1][i]=matrix [0][i]-a;

        }

    for(i=1;i<=m+n+n;i++)

         {

            if(matrix [n+1][i]>=0) flag=1;

             else 

             {  

                 flag=-1;

                 break;

             }

          }

    if(flag==1)

    {     for(i=1;i<=n;i++)

             { 

                  if(temp3[i]<=m+n) temp1=1;

                            else

                              { 

                                  temp1=-1;

                                  break;

                               }

              }

    //输出结果

    cout<<endl<<endl;

    cout<<"－－－－－－－－－－结 果 输 出－－－－－－－－－－－"<<endl<<endl;

        if(temp1==1)

           { 

              cout<<" 此线性规划的最优解存在!"<<endl<<endl<<"  最优解为："<<endl<<endl<<"     ";

              for(i=1;i<=n;i++)

                 temp5[temp3[i]]=matrix [i][0];

              for(i=1;i<=m;i++)

                 f+=t*matrix [0][i]*temp5[i];

             

              for(i=1;i<=m;i++) 

              {

                 cout<<"x"<<i<<" = "<<temp5[i];

                 if(i!=m)

                     cout<<"， ";

              }

              cout<<" ;"<<endl<<endl<<"     最优目标函数值f= "<<f<<endl<<endl;

              return ;

            }

            else 

            {   

                cout<<" 此线性规划无解"<<endl<<endl;

                return ;

            }

      }

   if(flag==-1)

   {   

       temp=100000;

       for(i=1;i<=m+n+n;i++)

          if(matrix [n+1][i]<temp)    

            {

              temp=matrix [n+1][i];

              h=i;                    

            }

             

        for(i=1;i<=n;i++)

          { 

            if(matrix [i][h]<=0) temp2=1;

                else { 

                              temp2=-1;

                              break;

                    }                       

          }

   }

    if(temp2==1)  

     { 

        cout<<"此线性规划无约束";

         return  ;

     }

   if(temp2==-1) 

   {   

      c=100000;

      for(i=1;i<=n;i++)

        {

           if(matrix [i][h]!=0)  b[i]=matrix [i][0]/matrix [i][h];

           if(matrix [i][h]==0)  b[i]=100000;

           if(b[i]<0)     b[i]=100000;

           if(b[i]<c) 

           {

               c=b[i];

               k=i;

           }

      }

         temp3[k]=h;

         temp4[k]=matrix [0][h];

         d=matrix [k][h];

      for(i=0;i<=m+n+n;i++)

        matrix [k][i]=matrix [k][i]/d;

      for(i=1;i<=n;i++)

      { if(i==k) 

         continue;

         aa=matrix [i][h];

         for(j=0;j<=m+n+n;j++)

            matrix [i][j]=matrix [i][j]-aa*matrix [k][j]; 

      }

   } 

   

}

while(1);

     return ;

}

 

//主函数

void main()

{ cout<<"-------------------单纯形算法程序----------------------"<<endl<<endl;

  premeter();

  calculate();

}