对偶单纯形法程序设计试验报告

对偶单纯形法程序设计试验报告F0307101班5030719012房智勇一.对偶问题min.st()1.,11.,210,1,2PncxjjjnaxbiMijjijnaxbiMijjijxjNjxjNj∑=≥∈∑==∈∑=≥∈∈原有问题无限制max.st()10,1,2.,11.,21PmbuiiiuiMiuiMimaucjNijijimaxcjNjijii∑=≥∈∈≤∈∑=∑=∈=对偶问题无限制其中：,{1,2,...,},,{1,2,...,},12121212MMOMMmNNONNn∩=∪=∩=∪=二、对偶单纯形方法与原单纯形方法的区别1、原单纯形方法从可行解和对偶问题不可行解出发，直到所有的检验数皆小于等于0，而对偶单纯形方法则从对偶可行解和原问题不可行解出发，直到原问题的解也变成可行。2、最优解的判定标准不一样。3、确定出入基变量的顺序不同。原单纯形方法，先确定入基变量后再确定出基变量，而对偶单纯形方法先确定出基变量后确定入基变量。4、确定出入基变量的方法不同。三、对偶单纯形方法的解的判定对偶性定理(1)对偶问题的对偶问题即是原有问题。(,,...,),(,,...,)(),()1212TTxxxxuuuuPDnmTTbucx==≤若分别是的可行解，则。推论:a.若(P)的可行解目标值无下界，则(D)无可行解。b.若(D)的可行解目标值无上界，则(P)无可行解。(2)如果应用单纯形法求得(LP)的一个基本最优解*x，并设它相应的基为B，那么关于基B的对偶解*u是(LD)的一个最优解，且**TTbucx=。(3)若(P),(D)其中一个有最优解，则另一个也一定有最优解，且两者之最优值相等。(4)(松弛互补条件)设x,u分别是的可行解。那么，分别为的最优解的充要条件为检验方法：1、B-1b≥0，表明已求出了原问题的最优解。2、B-1b中至少有一个负分量，且该负分量所在行的各元素都是非负数，则问题无最优解。()0,1,2,...1()0,1,2,...1nuaxbimiiijjjmxcaujnjjijii∑−==−∑−==−3、B-1b中至少有一个负分量，且该负分量所在行的元素中存在负数，则需要继续迭代。四计算步骤step1.选取(LP)的一个初始基B(应使T(B)中r0≥成立，定指标集DBII,，并求出单纯形表T(B)。step2.如果T(B)中0),...,(1≥=TmbbbGGG成立，则关于B之基本解0,==DBxbxG即为(LP)的一个最优解，0z即为最优值，算法终止。step3.定枢轴行指标k：},...2,1|min{mibbik==GG。step4.如果T(B)中0≥kjy)(DIj∈均成立，则(LP)不可行，算法终止。step5.定枢轴列指标},0|{max:DkjkjjkttIjyyryrt∈=。step6.以kty为枢轴元进行一次转轴，得到新的单纯形表T(B)和新的DBII,，转向step2。五原程序#includeiostream#includecmathusingnamespacestd;intx,nn,n1,i,j,n2,n,k,k1;doublekk,c[20],a[20][20],b[20],r[20],t[20];voidinput()//数据输入函数{charyes;do{cout目标函数是求最小值么(y/n)endl;cinyes;if(yes!='n'&&yes!='y')cout无效输入，请重新输入endl;}while(yes!='n'&&yes!='y');if(yes=='n')x=0;elsex=1;cout自变量个数:endl;cinn1;coutendl;cout目标函数系数:endl;for(i=0;in1;i++){cinc[i];if(x==0)c[i]=-c[i];}coutendl;cout约束条件个数endl;cinn2;coutendl;n=n1+n2;cout约束条件eg：3X1+4X2+5X30,输入3450endl;for(i=0;in2;i++){c[i+n1]=0.0;for(j=0;jn1;j++)cina[i][j];cinyes;cinb[i];if(yes==''){for(j=0;jn1;j++)a[i][j]=-a[i][j];b[i]=-b[i];}}}voidallesimplex()//对偶单纯型法计算函数{b[i]=0;for(j=0;jn2;j++)t[j]=j+1+n1;for(i=0;in2;i++)for(j=n1;jn;j++){if(j-n1==i)a[i][j]=1.0;elsea[i][j]=0.0;}for(nn=0;;nn++){k=0;x=0;kk=b[0];for(i=0;in2;i++){if(b[i]0.0){x=1;break;}}if(x==0){cout原问题有最优解endl;break;}for(i=1;in2;i++){if(b[i]0.0)if(b[i]kk){k=i;kk=b[i];}}x=2;for(i=0;in;i++){if(a[k][i]0.0){x=0;break;}}if(x==2){cout给定的线性规划无可行解endl;break;}for(i=0;in;i++){if(a[k][i]0.0)r[i]=c[i]/a[k][i];elser[i]=0.0;}k1=0;kk=-999999.0;for(i=0;in;i++){if(a[k][i]0.0)if(kkr[i]){k1=i;kk=r[i];}}b[n2]=b[n2]-b[k]*c[k1]/a[k][k1];for(j=0;jn2;j++){if(j==k)continue;elseb[j]=b[j]-a[j][k1]*b[k]/a[k][k1];}for(i=0;in2;i++){if(i==k)continue;else{for(j=0;jn;j++){if(j==k1)continue;elsea[i][j]=a[i][j]-a[i][k1]*a[k][j]/a[k][k1];}}}for(j=0;jn;j++){if(j==k1)continue;elsec[j]=c[j]-c[k1]*a[k][j]/a[k][k1];}kk=a[k][k1];for(j=0;jn;j++)a[k][j]/=kk;for(i=0;in2;i++)a[i][k1]=0.0;b[k]/=kk;a[k][k1]=1.0;c[k1]=0.0;t[k]=k1+1;}coutendl;if(x!=2){for(i=0;in1;i++){x=0;for(j=0;jn2;j++){if(i+1==t[j]){coutXi+1=b[j]endl;x=1;}}if(x==0)coutXi+1=0endl;}}cout目标函数最优解:-b[n2]endlendl;}voidmain(){cout对偶单纯型法程序试验byF03071015030719012房智勇endl;coutendlendlendl;input();allesimplex();}六计算验证Eg:MinW=2x1+3x2+7x3+9x4+13x5+3x6St2x1+4x543x1+3x2+5x3++5x5+3x65Xj0j=1,2,3,4,5,6对偶单纯型法程序试验byF03071015030719012房智勇目标函数是求最小值么（y/n）自变量个数:6目标函数系数:2379133约束条件个数2约束条件eg：3X1+4X2+5X30,输入345020004043350535原问题有最优解X1=2X2=0X3=0X4=0X5=0X6=0目标函数最优解:4