線規(guī)劃C++實現(xiàn).docx

/* *aim:線性規(guī)劃,單純形算法實現(xiàn) *note:這里的實現(xiàn)比常規(guī)的實現(xiàn)相比，需要更大的存儲空間,但靈活性更強,所需要的代碼更少 *date:2015-6-11 *Author:小花熊 *Q:1198253149 */ #ifndef _SIMPLEX_H_ #define _SIMPLEX_H_ #includeCArray2D.h #includeCArray.h/單純型算法所需要的數(shù)據(jù)結(jié)構(gòu)/note:使用的規(guī)則/* *1:松弛約束表達式中第k個基本變量的下標是k,非基本變量的下標為m+i,m為基本變量的最大索引 *2:系數(shù)矩陣的行列(m+n,m+n),m為基本變量數(shù)目,n非基本變量的數(shù)目 */ struct CSimplex /記錄基本變量的索引 CArray *basicVariableIndexes;/記錄非基本變量得索引 CArray *nonbasicVariableIndexes;/記錄每個松弛約束中的常數(shù),其長度和nonbasicVariableIndexes+basicVariableIndexes相等 CArray *relaxConstants;/松弛約束表達式的矩形陣列 CArray2D *relaxExpressRestrict;/目標函數(shù),其內(nèi)容的長度為nonbasicVariableIndexes-size+bacsicVariableIndexes-size/計算目標函數(shù)的最大值 CArray *objectFunc;/目標函數(shù)中的常數(shù)項 float objectConstant;/ CSimplex(); CSimplex(int basicVariableSize,int nonVariableSize); CSimplex(); ; enum CSimplexType CSimplexTypeInvalide,/單純型輸入不可行 CSimplexTypeNoBound,/單純型算法所得到的結(jié)果是無界的 CSimplexTypeOK,/單純形算法可能得到一個正常的結(jié)果 ; /單純形算法實現(xiàn) /request:調(diào)用前simple已經(jīng)是松弛型的 /return:返回上面的枚舉類型中的一種,如果計算成功，則將結(jié)果寫入到result中 CSimplexType simplex_algorithm(CSimplex *simplex,float *result); #endif /* *aim:單純形算法實現(xiàn) *date:2015-6-11 18:59 */ #includesimplex.h #include #include /標準型轉(zhuǎn)換為松弛型 /注意,函數(shù)可能會修改src的內(nèi)容 static bool simplex_normal_switch_relax(CSimplex *src,CSimplex *dst); /注意,函數(shù)可能會修改simplex的內(nèi)容,如果初始現(xiàn)行約束不可行返回CSimplexTypeInvalide static CSimplexType init_simplex(CSimplex *simple); /構(gòu)造函數(shù)和析構(gòu)函數(shù) CSimplex:CSimplex() this-basicVariableIndexes=NULL; this-nonbasicVariableIndexes=NULL; this-relaxConstants=NULL; this-relaxExpressRestrict=NULL; this-objectFunc=NULL; this-objectConstant=0.0f; CSimplex:CSimplex(int basicVariableSize,int nonVariableSize) this-basicVariableIndexes=new CArray(basicVariableSize); this-nonbasicVariableIndexes=new CArray(nonVariableSize); this-objectFunc=new CArray(basicVariableSize+nonVariableSize); this-relaxExpressRestrict=new CArray2D(basicVariableSize+nonVariableSize,basicVariableSize+nonVariableSize); this-relaxConstants=new CArray(basicVariableSize+nonVariableSize); this-objectConstant=0.0f; CSimplex:CSimplex() delete basicVariableIndexes; delete nonbasicVariableIndexes; delete relaxConstants; delete relaxExpressRestrict; delete objectFunc; objectConstant=0.0f; /主元的交換,方程組之間的代換/主元的交換,方程組之間的代換/param:swap_out被換出的基本變量的索引,/param:swap_in被換入的非基本變量索引/交換后swap_in,swap_out的身份交換,基本變量和非基本變量的互換/request:relaxExpressRestrict-get(swap_out,swap_in)0 static void swap_pivot(CSimplex *simplex,int swap_out,int swap_in ) float factor; float relaxConstant; float coef; int i,j,k;/選擇目標約束行,更新約束中的常數(shù)因子 factor=simplex-relaxExpressRestrict-get(swap_out,swap_in); relaxConstant=simplex-relaxConstants-get(swap_out);/寫入新的位置swap_in,更新松弛約束中的常數(shù)項 relaxConstant/=factor; const float swap_in_constant=relaxConstant; simplex-relaxConstants-set(swap_in,relaxConstant);/更新swap_in行的松弛約束表達式/在新的松弛約束中加入swap_out非基本變量 simplex-relaxExpressRestrict-set(swap_in,swap_out,1.0f/factor); for(i=0;inonbasicVariableIndexes-size;+i) j=simplex-nonbasicVariableIndexes-get(i);/取出源松弛約束中的系數(shù) relaxConstant=simplex-relaxExpressRestrict-get(swap_out,j); relaxConstant/=factor;/寫入新的松弛約束行中 simplex-relaxExpressRestrict-set(swap_in,j,relaxConstant); /更新剩余的松弛約束行 for(i=0;ibasicVariableIndexes-size;+i) /首先加入新的swap_out非基本變量約束 k=simplex-basicVariableIndexes-get(i); if( k != swap_out ) relaxConstant=simplex-relaxConstants-get(k); relaxConstant-=simplex-relaxExpressRestrict-get(k,swap_in)*swap_in_constant; simplex-relaxConstants-arrayk=relaxConstant;/更新剩余的松弛約束中非基本變量的系數(shù) coef=simplex-relaxExpressRestrict-get(k,swap_in); for(j=0;jnonbasicVariableIndexes-size;+j) int column=simplex-nonbasicVariableIndexes-get(j); if( column != swap_in )/剔除掉換入變量 /查找系數(shù) relaxConstant=simplex-relaxExpressRestrict-get(k,column); relaxConstant-=simplex-relaxExpressRestrict-get(swap_in,column)*coef; simplex-relaxExpressRestrict-set(k,column,relaxConstant); /最后加上換出變量swap_out的系數(shù)約束 relaxConstant=-coef/factor; simplex-relaxExpressRestrict-set(k,swap_out,relaxConstant); /更新目標函數(shù)/1:常數(shù)項 simplex-objectConstant+=simplex-objectFunc-get(swap_in)*swap_in_constant;/更新剩余的目標函數(shù)中的常數(shù)項 relaxConstant=simplex-objectFunc-get(swap_in); simplex-objectFunc-arrayswap_out=-relaxConstant*1.0f/factor; for(i=0;inonbasicVariableIndexes-size;+i) k=simplex-nonbasicVariableIndexes-get(i); if( k !=swap_in ) coef=simplex-objectFunc-get(k); coef-=simplex-relaxExpressRestrict-get(swap_in,k)*relaxConstant; simplex-objectFunc-set(k,coef); /將swap_in從非基本變量集合中刪掉,swap_out從基本變量集合中刪掉/并將兩者相互添加到對方原來所在的集合中 for(i=0;inonbasicVariableIndexes-size;+i ) if( simplex-nonbasicVariableIndexes-get(i) = swap_in ) simplex-nonbasicVariableIndexes-set(i,swap_out); break; for(i=0;ibasicVariableIndexes-size;+i) if(simplex-basicVariableIndexes-get(i) = swap_out) simplex-basicVariableIndexes-set(i,swap_in); break; /檢測,目標函數(shù)中是否有一個系數(shù)大于0,如果有大于0并且是最大的的系數(shù),在idx中返回她的索引 static bool isCoefficientPositive(CSimplex *simplex,int *idx) /注意下面的尋址方式 int udx=-1; float factor=0.0f; for(int i=0;inonbasicVariableIndexes-size;+i) int k=simplex-nonbasicVariableIndexes-arrayi; if(simplex-objectFunc-arrayk factor ) factor=simplex-objectFunc-arrayk; udx=k; *idx=udx; return udx != -1; /單純形算法,如果運行成功，會在result中返回運算的最終結(jié)果 CSimplexType simplex_algorithm(CSimplex *simplex,float *result) const float einf=1e8; float factor,relax; int i,j,k; int idx;/首先初始化最初的標準型 if( init_simplex(simplex) = CSimplexTypeInvalide ) return CSimplexTypeInvalide;/ printf(init_simplex over -n); while( isCoefficientPositive(simplex,&idx) ) /在所有的松弛約束中,選擇一個最緊湊的一個 printf(!n); factor=einf; j=-1; for(i=0;ibasicVariableIndexes-size;+i) k=simplex-basicVariableIndexes-get(i); relax=simplex-relaxExpressRestrict-get(k,idx); if( relax0.0f ) float value=simplex-relaxConstants-get(k)/relax; if( valueobjectConstant;/注意,在剩下的解碼步驟中，將集合simplex-basicVariableIndexes中的基本變量設(shè)定為0就可以求出最后的解 return CSimplexTypeOK; /標準型轉(zhuǎn)換為松弛型/request:simplex的各個一維的列和二維數(shù)組的行列要比其中變量+松弛約束的數(shù)目之和大1,/request:否則會出現(xiàn)數(shù)組訪問越界,運行時異常 CSimplexType init_simplex(CSimplex *simplex) float factor=1e8; float coef,value; int i,j,k;/檢測常系數(shù) j=-1; for(i=0;ibasicVariableIndexes-size;+i) k=simplex-basicVariableIndexes-get(i); coef=simplex-relaxConstants-get(k); if( coef =0.0f) return CSimplexTypeOK;/否則,執(zhí)行變換/重新建立新的線性規(guī)劃數(shù)據(jù)結(jié)構(gòu),并使用新的結(jié)構(gòu)來判斷當前的結(jié)構(gòu)是否有最優(yōu)解,代碼稍后實現(xiàn)/加入新的非基變量(m+n-1),設(shè)定目標函數(shù)為max=-X(m+n-1),如果目標函數(shù)的最優(yōu)值不為0,則線性規(guī)劃是不可行的的 CSimplex asimplex; CSimplex *other=&asimplex; other-basicVariableIndexes=new CArray(simplex-basicVariableIndexes-size); other-nonbasicVariableIndexes=new CArray(simplex-nonbasicVariableIndexes-size+1); const int size=other-basicVariableIndexes-size+other-nonbasicVariableIndexes-size; other-relaxConstants=new CArray(size); other-relaxExpressRestrict=new CArray2D(size,size); other-objectFunc=new CArray(size);/使用源數(shù)據(jù)對新生成的數(shù)據(jù)結(jié)構(gòu)進行初始化/目標函數(shù) other-objectFunc-fillWith(0.0f); other-objectFunc-arraysize-1=-1;/基變量 other-basicVariableIndexes-copyWith(simplex-basicVariableIndexes);/非基變量 other-nonbasicVariableIndexes-copyWith(simplex-nonbasicVariableIndexes); other-nonbasicVariableIndexes-arrayi=size-1;/常數(shù)項 other-relaxConstants-copyWith(simplex-relaxConstants);/交換,求解當前的線性規(guī)劃是否有可行解 swap_pivot(other,j,size-1); int idx; while( isCoefficientPositive(other,&idx) ) factor=1e8; j=-1; for(i=0;ibasicVariableIndexes-size;+i) k=other-basicVariableIndexes-arrayi; coef=other-relaxExpressRestrict-get(k,idx); if(coef0) value=other-relaxConstants-arrayk/coef; if(valueobjectConstant objectFunc-copyWith(other-objectFunc,size-1); simplex-objectConstant=other-objectConstant;/從非基變量集合中將size-1剔除掉 for(j=0,i=0;inonbasicVariableIndexes-arrayi != size-1 ) simplex-nonbasicVariableIndexes-arrayj+=other-nonbasicVariableIndexes-arrayi; /嚴格地說，size-1不會在基變量集合中出現(xiàn), for( j=0,i=0;ibasicVariableIndexes-arrayi; if( k != size-1 ) simplex-basicVariableIndexes-arrayj+=k; /二維系數(shù)矩陣復制 for(i=0;isize-1;+i) for(j=0;jrelaxExpressRestrict-get(i,j); simplex-relaxExpressRestrict-set(i,j,factor); /松弛約束的常系數(shù) simplex-relaxConstants-copyWith(other-relaxConstants); return CSimplexTypeOK; / int main(int argc,char *argv) CSimplex asimplex; CSimplex *simplex=&asimplex;/系數(shù)矩陣,注意這是松弛型系數(shù) const int size=4; float coefficient44= 0,0,2,-1,0,0,1,-4 ;/松弛表達式的系數(shù)集合 float relaxConstants5=2,-4;/目標函數(shù) float objectFunc5=0,0,2,-1; float objectConstant=0.0f;/基本變量集合 int variableSize=2; int basicVariable2=0,1;/非基本變量集合 int nonVariableSize=2; int nonbasicVariable3=2,3;/創(chuàng)建單純型數(shù)據(jù)結(jié)構(gòu) int i,j,k; simplex-basicVariableIndexes=new CArray(variableSize); simplex-nonbasicVariableIndexes=new CArray(nonVariableSize); simplex-relaxConstants=new CArray(size); simplex-relaxExpressRestrict=new CArray2D(size,size); simplex-objectFunc=new CArray(size);/使用程序里面的數(shù)據(jù)寫入到單純型數(shù)據(jù)結(jié)構(gòu)中 for(i=0;ibasicVariableIndexes-size;+i) simplex-basicVariableIndexes-arrayi=basicVariablei; for(i=0;inonbasicVariableIndexes-size;+i) simplex-nonbasicVariableIndexes-arrayi=nonbasicVariablei;/常數(shù)項 for(i=0;irelaxConstants-size;+i) simplex-relaxConstants-arrayi=relaxConstantsi;/系數(shù)矩陣 for(i=0;irelaxExpressRestrict-rowCount();+i) for(j=0;jrelaxExpressRestrict-column