..XX大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)實驗教學(xué)中心實驗報告第1頁共2頁大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)實驗教學(xué)中心實驗報告課程名稱：運籌學(xué)實驗學(xué)期：2012~2013學(xué)年第二學(xué)期成績：指導(dǎo)教師：瑜學(xué)生：盧富毓學(xué)生學(xué)號：實驗名稱：對偶單純形法編程實驗要求：必做實驗學(xué)時：2學(xué)時實驗編號：02實驗日期：201完成日期：2013/3/1學(xué)院：數(shù)學(xué)與統(tǒng)計學(xué)院專業(yè)：信息與計算科學(xué)年級：2010級一、實驗?zāi)康木幊虒崿F(xiàn)對偶〔改良〕單純形法求解線性規(guī)劃問題，加深對單純形法的理解和掌握二、實驗環(huán)境VS2010〔C++〕三、實驗容改良單純形法的實驗： 由于在一些情況下，當檢驗數(shù)Cj-Zj都小于零后了，但是其b的值卻存在有負數(shù)了。這樣的話，x中就會存在負值，這樣與約束條件中xi>0，就不符合。所以需要對單純形法改良，得到對偶單純形法。四、實驗過程A、對偶單純形法的算法思想先用單純形法計算，當檢驗數(shù)都為非正后，檢查b是否有存在負值，假設(shè)是有那么使用對偶單純形法。確定換出量，找到b中為負值的最小值。確定對應(yīng)的xi的換出。再對單純形表中的xi所在行的各系數(shù)進展檢查，假設(shè)所有Aij都大于零，那么表示無可行解。假設(shè)存在Aij小于零，那么計算，找到其所換入的列以保證的到的對偶問題仍有可行解。然后再按照原單純形算法經(jīng)行求解。重復(fù)上述步驟。B、編譯運行程序，輸入約束方程的系數(shù)矩陣A，常矩陣B,價值系數(shù)C,得到最優(yōu)解 為了保證得到的算法既能對特殊情形〔有bi<0〕的情況下能求解，也能對一般的問題求解。這里給出了一下兩組數(shù)據(jù)。 1、上一個實驗報告中的求解的數(shù)據(jù)。B=[2;14;2];X=[3-420-5500]2、參照課本P62例題6中的2-6表給出的數(shù)據(jù)X=[-2-3-400]D、運行結(jié)果如下列圖： 1〕下列圖表示的是第一個數(shù)據(jù)帶入后得到的結(jié)果。表示對偶單純形法對一般的數(shù)據(jù)成立2〕下列圖表示的對偶單純形法對b中存在負值時糾正的結(jié)果：a、初始化后的結(jié)果：b、優(yōu)化后的結(jié)果：c、最后得到的結(jié)果：最后得到的結(jié)果與書上例題所有的結(jié)果完全吻合。所以所編寫的算法為對偶單純形法。五、實驗總結(jié) 通過對對偶單純形法算法的程序編寫，進一步掌握了單純形法。 同時，在編寫的過程中，對，b的變換有了更加清晰的理解。 以及在求解過程中，對線性約束的標準型也有了明確的掌握。六、源代碼源代碼如下：#include<iostream>#include<iomanip>usingnamespacestd;#defineM-1000classDanChun{private:doubleA[100][120],B[30];//創(chuàng)立一個二維數(shù)組，用來存儲xi值以及b的值doubleC[110],CB[40];//定義一個C矩陣用來存儲x的價值系數(shù)doubleCZ[110];//CZ用來存儲cj-zj的值doublesita[30];//用來存儲sita的值intXB[30];//用來存XB的值doubleX[100];//用來存儲最后計算的X的值doublew[100];//Cj-Zj/X[i]的替換。public:intn,m;voidinit();//1.將不等式約束的各矩陣進展賦值boolFindE(inti,intj);//2.尋找A矩陣中的基向量voidFindCB();//3.尋找有用價值系數(shù)，Cj-Zj需要用到的intCj_Zj();//4.1求出cj-zj的值intC_sita(intk);//4.2計算sita的值void_DC();//4.用來計算單純形法的主函數(shù)void_E(intl,intk);//4.3求其單位向量boolP_CjZj();//4.4intBbool(doubleb[],intk);//判斷b中是否有負值存在intTH(intl);//b有負值是，進展替換操作voidDisplay();voidDisplay1();};voidDanChun::init(){inti=0,j=0; cout<<"請輸入m,n："; cin>>m; cin>>n; cout<<"請輸入線性約束矩陣："<<endl;for(i=0;i<m;i++){for(j=0;j<n+m;j++){if(j<n){ cin>>A[i][j]; }else{ A[i][j]=0;if(j==n+i){ A[i][j]=1; } } } } cout<<endl; cout<<"請輸入B的值："<<endl;for(i=0;i<m;i++){ cin>>B[i]; CB[i]=0; } cout<<endl; cout<<"請輸入價值系數(shù)C："<<endl;for(i=0;i<n+m;i++){if(i<n){ cin>>C[i]; }else{ C[i]=M; } X[i]=0; } n=m+n;}voidDanChun::Display(){inti,j; cout<<"價值系數(shù)C：";for(i=0;i<n;i++){ cout<<C[i]<<""; } cout<<endl; cout<<"B的值：";for(i=0;i<m;i++){ cout<<B[i]<<""; } cout<<endl; cout<<"線性約束矩陣A："<<endl;for(i=0;i<m;i++){for(j=0;j<n;j++){ printf("%0.3lf\t",A[i][j]); } cout<<endl; } cout<<endl; cout<<"價值系數(shù)CB：";for(i=0;i<m;i++){ cout<<CB[i]<<""; } cout<<endl;}boolDanChun::P_CjZj(){intj;for(j=0;j<n;j++){if(CZ[j]>0){returntrue; } }returnfalse;}intDanChun::TH(intl){inti=0,k=0;doublemin=1000;for(i=0;i<n;i++){ w[i]=0; }for(i=0;i<n;i++){if(A[l][i]>=0){ w[i]=-M; }else{ w[i]=CZ[i]/A[l][i]; } }for(i=0;i<n;i++){if(min>w[i]){ min=w[i]; k=i; } }returnk;}intDanChun::Bbool(doubleb[],intk){inti=0,l=0,s=0;doublemin=0;for(i=0;i<k;i++){if(min>b[i]){ min=b[i]; l=i;//找出行下標 } }if(min<0){returnl; }return-1;}voidDanChun::Display1(){inti,j=0,p=0;doublefavl=0;for(i=0;i<m;i++){ X[XB[i]]=B[i]; }for(i=0;i<n;i++){ favl+=C[i]*X[i]; } cout<<"當前為最優(yōu)解：favl="<<favl<<endl; cout<<"有最優(yōu)解時，x的取值如下："<<endl;for(i=0;i<n;i++){ j=i; cout<<"X["<<j+1<<"]="<<X[i]<<endl; }}voidDanChun::_DC(){inti,j=0,k,l,p=0;boolb;doublefavl=0;do{ b=true; k=Cj_Zj();//得到cj-zj的大于0的maxif(k==-1){if((l=Bbool(B,m))>=0){ k=TH(l); b=false; }else{ Display1();return; } }if(b){ l=C_sita(k);if(l==-1){ cout<<"無解！"<<endl;return; } } CB[l]=C[k]; XB[l]=k; _E(l,k);/*if(!b){ k=Cj_Zj(); }*/ p++; cout<<"第"<<p<<"次優(yōu)化開場"<<endl; cout<<endl<<"XB的值：";for(i=0;i<m;i++){ cout<<XB[i]<<""; } cout<<endl; Display(); cout<<"第"<<p<<"次優(yōu)化完畢"<<endl; }while(P_CjZj()||!b);}voidDanChun::_E(intl,intk){inti,j; B[l]=B[l]/A[l][k];for(j=0;j<n;j++){if(j==k)continue; A[l][j]=A[l][j]/A[l][k]; } A[l][k]=1;for(i=0;i<m;i++){if(i==l)continue;for(j=0;j<n;j++){if(j==k)continue; A[i][j]=A[i][j]-A[i][k]*A[l][j]; } B[i]=B[i]-A[i][k]*B[l]; A[i][k]=0; }}intDanChun::Cj_Zj(){inti,j,k=0;doublesum=0,max=0;for(j=0;j<n;j++){for(i=0;i<m;i++){ sum+=CB[i]*A[i][j]; } CZ[j]=C[j]-sum; sum=0; }for(j=0;j<n;j++){if(CZ[j]>max&&CZ[j]>0){ max=CZ[j]; k=j; } }if(max==0){return-1; }returnk;}intDanChun::C_sita(intk){inti,j=0;doublemin=-M;for(i=0;i<m;i++){if(A[i][k]>0){ sita[i]=B[i]/A[i][k]; j++; }else{ sita[i]=-M; } }if(j==0){//表示沒有一個A[i][k]是大于0的return-1; }for(i=0;i<m;i++){if(sita[i]<min){ min=sita[i]; k=i; } }returnk;}boolDanChun::FindE(inti,intj){//判斷是否是單位列intk=0;while(k<m){if(A[k][j]!=0&&k!=i){returnfalse; }else{ k++;if(k==i){continue; } } }returntrue;}vo