tdcxq.h

这是一个求解线性规划问题的程序

//---------------------------------------------------------------------------
#ifndef TDcxQH
#define TDcxQH

#include "Matrix.h"
#include "Vector.h"
#include "TList.h"
//---------------------------------------------------------------------------

//线性规划问题类
class TDcxQuestion
{
public:
   TMatrix * mMatA ;                    //系数矩阵
   TCVector * mCVetI, * mCVetb;         //标号集,条件向量
   TCVector * mCVetc, * mCVetsign;      //费用向量,符号约束

   TCVector *mCVetx;                    //某一基可行解

public:
   //构造函数
   TDcxQuestion(unsigned int aRowCount,unsigned int aColCount)
   {
      mMatA = new TMatrix(aRowCount,aColCount);     //系数矩阵
      mCVetI = new TCVector(aRowCount);             //标号集
      mCVetb  = new TCVector(aRowCount);            //条件向量

      mCVetc  = new TCVector(aColCount);            //费用向量
      mCVetsign=new TCVector(aColCount);            //符号约束

      mCVetx = new TCVector(aColCount);
   }

   //拷贝构造函数
   TDcxQuestion(TDcxQuestion& aDcxQ)
   {
      mMatA = new TMatrix(*aDcxQ.mMatA);        //系数矩阵
      mCVetI = new TCVector(*aDcxQ.mCVetI);     //标号集
      mCVetb  = new TCVector(*aDcxQ.mCVetb);    //条件向量

      mCVetc  = new TCVector(*aDcxQ.mCVetc);    //费用向量
      mCVetsign=new TCVector(*aDcxQ.mCVetsign); //符号约束

      mCVetx = new TCVector(*aDcxQ.mCVetx);
   }

   //重载等号操作符
   TDcxQuestion operator=(TDcxQuestion& aDcxQ)
   {
      Reset(aDcxQ.mMatA->GetRowCount(),aDcxQ.mMatA->GetColCount());

      *mMatA = *aDcxQ.mMatA;
      *mCVetI = *aDcxQ.mCVetI;
      *mCVetb = *aDcxQ.mCVetb;

      *mCVetc = *aDcxQ.mCVetc;
      *mCVetsign = *aDcxQ.mCVetsign;

      *mCVetx = *aDcxQ.mCVetx;

      return *this;
   }

   ~TDcxQuestion()
   {
      delete mMatA;          //系数矩阵
      delete mCVetI;         //标号集
      delete mCVetb;         //条件向量
      delete mCVetc;         //费用向量
      delete mCVetsign;      //符号约束
      delete mCVetx;
   }

   void Reset(unsigned int aRowCount,unsigned int aColCount)
   {
      mMatA->Reset(aRowCount,aColCount);     //系数矩阵
      mCVetI->Reset(aRowCount);             //标号集
      mCVetb->Reset(aRowCount);            //条件向量

      mCVetc->Reset(aColCount);            //费用向量
      mCVetsign->Reset(aColCount);            //符号约束

      mCVetx->Reset(aColCount);
   }

   //判断本问题是不是规范型
   bool IsRule()
   {
      for (unsigned int i=1;i<=mCVetI->GetDimCount();i++) {
         if ((*mCVetI)(i) != 0)
            return false;
      }
      for (unsigned int i=1;i<=mCVetsign->GetDimCount();i++) {
         if ((*mCVetsign)(i) != 0)
            return false;
      }
      return true;
   }

   //得到规范型的问题aDcxQ,并取得规范型到原问题的变换矩阵aMatTranForm
   bool GenRule(TDcxQuestion* aDcxQ,TMatrix* aMatTranForm)
   {
      //自由变量的个数(引入相应的非负变量: x1 = u1 - u2)
      int lFreeCount=0;
      for (unsigned int i=1;i<=mCVetsign->GetDimCount();i++) {
         if ((*mCVetsign)(i) != 0)  // != '>='
            lFreeCount = lFreeCount + 1;
      }


      //不等式的个数(引入相应的非负松弛变量:  >= : -x1    <= : +x1)
      int lInequationCount = 0;
      for (unsigned int i=1;i<=mCVetI->GetDimCount();i++) {
         if ((*mCVetI)(i) != 0)
            lInequationCount = lInequationCount + 1;
      }

      //如果本身已是规范型
      if (lFreeCount==0 && lInequationCount==0) {
         *aDcxQ = *this;
         //单位变换矩阵
         aMatTranForm->Reset(mMatA->GetColCount(),aDcxQ->mMatA->GetColCount());
         for (unsigned int i=1;i<=aMatTranForm->GetRowCount();i++)
            for (unsigned int j=1;j<=aMatTranForm->GetColCount();j++)
               if (i==j)
                  (*aMatTranForm)(i,j)=1;
               else
                  (*aMatTranForm)(i,j)=0;

         return true;
      }

      //构造规范型的问题和变换矩阵
      aDcxQ->Reset(mMatA->GetRowCount(),mMatA->GetColCount()+lFreeCount+lInequationCount);
      aMatTranForm->Reset(mMatA->GetColCount(),aDcxQ->mMatA->GetColCount());

      //1.自由变量,引入相应的非负变量: x1 = u1 - u2
      unsigned int jj=1; //新系数矩阵的列
      for (unsigned int j=1;j<=mMatA->GetColCount();j++) {
         if ((*mCVetsign)(j)!=0) {  //自由变量,引入相应的非负变量: x1 = u1 - u2
            (*aMatTranForm)(j,jj) = 1;
            jj = jj+1;
            (*aMatTranForm)(j,jj) = -1;

            (*aDcxQ->mCVetc)(jj-1) = (*mCVetc)(j);
            (*aDcxQ->mCVetc)(jj) = -(*mCVetc)(j);
            for (unsigned int i=1;i<=mMatA->GetRowCount();i++) {
               (*aDcxQ->mMatA)(i,jj-1) = (*mMatA)(i,j);
               (*aDcxQ->mMatA)(i,jj) = -(*mMatA)(i,j);
            }
         }
         else {  //非负变量,引入相应的变量: x1 = u1
            (*aMatTranForm)(j,jj) = 1;
            (*aDcxQ->mCVetc)(jj) = (*mCVetc)(j);
            for (unsigned int i=1;i<=mMatA->GetRowCount();i++)
               (*aDcxQ->mMatA)(i,jj) = (*mMatA)(i,j);
         }

         jj = jj+1;
      }

      //2.不等式的个数(引入相应的非负松弛变量:  >= : -x1    <= : +x1)
      for (unsigned int i=1;i<=mCVetI->GetDimCount();i++){
         if ((*mCVetI)(i) == 1) {   // >= : -x1
           (*aDcxQ->mMatA)(i,jj) = -1;
           jj = jj+1;
         }
         else if ((*mCVetI)(i) == -1) {   // <= : +x1
           (*aDcxQ->mMatA)(i,jj) = 1;
           jj = jj+1;
         }
      }

      *aDcxQ->mCVetb = *mCVetb;

      return true;
   }

   //判断某个解mCVetx是否是规范型问题的基可行解
   bool IsBasex()
   {
      if (!IsRule())
         return false;

      //是不是解
      if (!((*mMatA)*(*((TMatrix*)mCVetx)) == (*((TMatrix*)mCVetb))))
         return false;

      //是不是基解
      KTList<unsigned int>* lLB = new KTList<unsigned int>;
      for (unsigned int i=1;i<=mCVetx->GetDimCount();i++){
         if ((*mCVetx)(i) > 0)
             lLB->Append(i);
      }

      if ((unsigned int)lLB->GetCount() != mMatA->GetRowCount()){
         delete lLB;
         return false;
      }   

      //构造基矩阵
      TMatrix lMatM(mMatA->GetRowCount(),mMatA->GetRowCount());
      unsigned int i,j,k;
      for (k=1,lLB->First();!lLB->IsEof();lLB->Next(),k++) {
         j=lLB->GetData();
         for (i=1;i<=mMatA->GetRowCount();i++)
            lMatM(i,k) = (*mMatA)(i,j);
      }

      delete lLB;

      //不满秩
      if ((unsigned int)lMatM.Rank() != mMatA->GetRowCount())
         return false;

      return true;
   }

   //判断规范型问题是否退化
   bool IsDegrade()
   {
      if (!IsRule())
         return false;

      return !((unsigned int)mMatA->Rank()==mMatA->GetRowCount());
   }

   //构造规范型的辅助问题
   bool GenAssistant(TDcxQuestion *aDcxQ)
   {
      if (!IsRule())
        return false;

      aDcxQ->Reset(mMatA->GetRowCount(),mMatA->GetRowCount()+mMatA->GetColCount());

      //原矩阵
      for (unsigned int i=1;i<=mMatA->GetRowCount();i++)
         for (unsigned int j=1;j<=mMatA->GetColCount();j++)
            (*aDcxQ->mMatA)(i,j) = (*mMatA)(i,j);

      //条件向量b
      *aDcxQ->mCVetb = *mCVetb;
      //系数矩阵c
      for (unsigned int i=mCVetc->GetDimCount()+1;i<=aDcxQ->mCVetc->GetDimCount();i++)
         (*aDcxQ->mCVetc)(i) = 1;

      //把b的各元素变成正数
      for (unsigned int i=1;i<=aDcxQ->mCVetb->GetDimCount();i++)
         if ((*mCVetb)(i) < 0) {
            for (unsigned int j=1;j<=mMatA->GetColCount();j++)
               (*aDcxQ->mMatA)(i,j) = -(*aDcxQ->mMatA)(i,j);
            (*aDcxQ->mCVetb)(i) = -(*aDcxQ->mCVetb)(i);
         }


      //辅助变量的系数矩阵
      for (unsigned int i=1;i<=mMatA->GetRowCount();i++)
         for (unsigned int j=mMatA->GetColCount()+1;j<=aDcxQ->mMatA->GetColCount();j++) {
            if (i == j-mMatA->GetColCount())
               (*aDcxQ->mMatA)(i,j) = 1;
         }

      //初始基可行解   
      for (unsigned int i=1;i<=mCVetb->GetDimCount();i++)
         (*aDcxQ->mCVetx)(mMatA->GetColCount()+i) = (*aDcxQ->mCVetb)(i);

      return true;
   }

   //判断某个解是否是规范型问题的最尤解
   bool IsBestx()
   {
      return true;
   }

};


#endif