對(duì)偶單純形法編程

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