10-伪代码详解

7.2.3　伪代码详解

（1）找入基列

检验数是在第0行，第1～m列的元素，先令max1=0，然后用for循环查找所有的检验数，找到最大的正检验数，并用e记录该列，即入基列。

for(j=1;j<=m;j++)        //找入基列(最大正检验数对应的列) 
{
      if(max1<kernel[0][j]) 
      {
          max1=kernel[0][j]; 
          e=j; 
      }
}

（2）找离基行

找 常数列/入基列正比值最小 对应的行，即离基行。在找离基行循环里，检查入基列中除检验数外所有元素是否都小于0，如果是，则线性规划问题有无界解。

for(i=1;i<=n;i++)        //找离基行(常数列/入基列正比值最小对应的行) 
{
    if(max2<kernel[i][e]) 
    {
        max2=kernel[i][e]; 
    }
    float temp=kernel[i][0]/kernel[i][e]; //常数项在前,temp=fabs(temp); 
    if(temp>0&&temp<min) //找离基变量
    {
        min=temp; 
        k=i; 
    }
}
if(max2==0) 
    {
        cout<<"解无界"<<endl; 
        break; 
    }

（3）换基变换

换基变换（转轴变换），即将入基变量和离基变量交换位置。

   char temp=FJL[e]; 
   FJL[e]=JL[k]; 
   L[k]=temp;

（4）计算单纯形表

计算4个特殊位（入基列、离基行、c₀位、交叉位），其余的一般位采用十字交叉计算新值。

for(i=0;i<=n;i++)             //计算除入基列和离基行的所有位置的元素
{
    if(i!=k) 
    {
        for(j=0;j<=m;j++)
        {
            if(j!=e) 
            {
              if(i==0&&j==0)  //计算特殊位c0位,即目标函数的值
                  kernel[i][j]=kernel[i][j]+kernel[i][e]*kernel[k][j]/kernel [k][e]; 
              else            //一般位置
                  kernel[i][j]=kernel[i][j]-kernel[i][e]*kernel[k][j]/kernel [k][e]; 
              }
            }
        }
}
for(i=0;i<=n;i++)             //计算特殊位,离基行的元素
{
     if(i!=k) 
          kernel[i][e]=-kernel[i][e]/kernel[k][e]; 
}
for(j=0;j<=m;j++)             //计算特殊位,入基列的元素
{
    if(j!=e) 
       kernel[k][j]=kernel[k][j]/kernel[k][e]; 
  }
//计算特殊位,交叉位置
kernel[k][e]=1/kernel[k][e];