运筹学两阶段法C语言程序代码.doc

课 程 设 计 程 序 代 码 课程设计名称 运筹课程设计 专 业 信息管理与信息系统 班 级 140505班 学 生 姓 名 孙玉玲 王凤禹 王美玲 指 导 教 师 王亚君 2016年7月15日#include #include #define MAX 100#define STP 100int stop=1; /迭代记数变量int status; /iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数int step=1; /目前阶段double aMAXMAX,bMAX,cMAX,temp_cMAX,max=0; /方程组相关系数int num_x; /变量个数 int num_st; /约束方程数int num_ar=0; /人工变量个数int artiMAX; /人工变量下标int baseMAX; /基变量下标int ma_mi; /1为求最大值，2为求最小值void create(); /建立方程组void iterative(); /单纯型法迭代void output(); /输出结果void banner(); /打印程序标题void exchange(double cMAX,double temp_cMAX); /交换两阶段价值系数void show(); /输出方程组void main() int i,j,k;banner();create();/保存原价值系数，转换为第一阶段价值系数for(i=1;i=num_x;i+) k=0; for(j=1;j=num_ar;j+) if(i=artij) k=1; if(k=1) temp_ci=-1; else temp_ci=0;exchange(c,temp_c);printf(nn第一阶段问题为：nn);show();step+;printf(nn按回车开始第一阶段迭代);getchar(); getchar();iterative();if(status=-2) puts(迭代超过限制次数强行终止！n); puts(n按回车结束); getchar(); exit(0);output();if(max!=0) puts(nn原问题无可行解。n); puts(n按回车结束); getchar(); exit(0);/转换为第二阶段价值系数exchange(c,temp_c);/把人工变量列全设为0for(i=1;i=num_ar;i+) cartii=0; for(j=1;j=num_st;j+) ajartii=0;puts(nn第二阶段问题为：nn);show();puts(nn按回车开始第二阶段迭代);getchar(); iterative();switch(status) case 1: output(); puts(nn原问题有唯一最优解。n); puts(n按回车结束); getchar(); exit(0);case 0: puts(nn原问题为无界解。n); puts(n按回车结束); getchar(); exit(0);case -1: output(); puts(nn原问题有无穷多最优解。n); puts(n按回车结束); getchar(); exit(0);case -2: puts(迭代超过限制次数强行终止！n); puts(n按回车结束); getchar(); exit(0);/switchvoid banner() printf(tt*n);printf(tt 两阶段法解LP问题n);printf(tt*n);printf(n);void show() /对方程组以自然的格式输出，系数为零的x不显示/为1的不显示系数1，-1系数只显示负号int i,j,k;switch(step) case 1: printf(min z= ); printf(x%d,arti1); for(i=2;i=num_ar;i+) printf( + x%d,artii); break;case 2:printf(max z= );printf(%lg x%d,c1,1);for(i=2;i=0) printf( +%lg x%d,ci,i); else printf( %lg x%d,ci,i);break;printf(nst:n);for(i=1;i=num_st;i+) k=0; for(j=1;j=0&k!=0) printf( +%lg x%d,aij,j); else if(aij=0&k=0) printf( %lg x%d,aij,j); else printf( %lg x%d,aij,j); k=1; printf( = %lgn,bi); printf( x1x%d=0,num_x);void exchange(double cMAX,double temp_cMAX) int i;double tempMAX;for(i=1;i=num_x;i+) tempi=temp_ci; temp_ci=ci; ci=tempi;void create() /输入方程组系数，每个方程输完后回显确认int i,j,k,re_stMAX,tnum_x,num_addv=0,num_ba=0;char confirm;while(2) printf(请选择：1、求最大值，2、求最小值：(1/2); scanf(%d,&ma_mi); if(ma_mi!=1&ma_mi!=2) printf(输入错误，重新选择。); else break;while(1) printf(指定变量个数：); scanf(%d,&num_x); printf(输入价值系数c1-c%d:n,num_x); for(i=1;i=num_x;i+) printf(c%d=,i); scanf(%lf,&ci); if(ma_mi=1) printf(max z= ); else printf(min z= ); printf(%lg x%d,c1,1); for(i=2;i=0) printf( +%lg x%d,ci,i); else printf( %lg x%d,ci,i); printf(n正确吗？：(y/n);getchar();confirm=getchar();if (confirm=y) break;else if(confirm=n) continue;printf(输入约束方程组个数：);scanf(%d,&num_st);for(i=1;i=，3、= ：(1/2/3); scanf(%d,&re_sti); if(re_sti!=1&re_sti!=2&re_sti!=3) printf(输入错误，请重新选择。); else break; printf(输入技术系数：n); for(j=1;j=num_x;j+) printf(a%d=,j); scanf(%lf,&aij); printf(输入资源拥有量：nb%d=,i); scanf(%lf,&bi); printf(st.%i:n,i); printf(%lg x%d,ai1,1); for(j=2;j=0) printf( +%lg x%d,aij,j); else printf( %lg x%d,aij,j); switch(re_sti) case 1: printf( = %lg,bi); break; case 2: printf( = %lg,bi); break; case 3: printf( = %lg,bi); break; while(1) printf(n正确吗？(y/n); getchar(); confirm=getchar(); if (confirm=y) break; else if(confirm=n) i-=1; break; /显示输入的方程组printf(n原问题为：nn);if(ma_mi=1) printf(max z= );else printf(min z= );printf(%lg x%d,c1,1);for(i=2;i=0) printf( +%lg x%d,ci,i); else printf( %lg x%d,ci,i);printf(nst:n);for(i=1;i=num_st;i+) k=0; for(j=1;j=0&k!=0) printf( +%lg x%d,aij,j); else if(aij=0&k=0) printf( %lg x%d,aij,j); else printf( %lg x%d,aij,j); k=1; switch(re_sti) case 1: printf( = %lgn,bi); break; case 2: printf( = %lgn,bi); break; case 3: printf( =0n,num_x);tnum_x=num_x;for(i=1;i=num_st;i+) switch(re_sti) case 1: case 3: num_x+=1; break; case 2: num_x+=2; break; /化为标准形式if(ma_mi=2) for(i=1;i=tnum_x;i+) ci*=-1; /求最小值时，系数变相反数for(i=1;i=num_st;i+) switch(re_sti) case 1: num_addv+; num_ba+; num_ar+; ctnum_x+num_addv=0; basenum_ba=artinum_ar=tnum_x+num_addv; for(j=tnum_x+1;j=num_x;j+) if(j=tnum_x+num_addv) aitnum_x+num_addv=1; else aij=0; break; case 2: num_addv+; ctnum_x+num_addv=0; num_addv+; num_ba+; num_ar+; ctnum_x+num_addv=0; basenum_ba=artinum_ar=tnum_x+num_addv; for(j=tnum_x+1;j=num_x;j+) if(j=tnum_x+num_addv-1) aitnum_x+num_addv-1=-1; else if(j=tnum_x+num_addv) aitnum_x+num_addv=1; else aij=0; break; case 3: num_addv+; num_ba+; ctnum_x+num_addv=0; basenum_ba=tnum_x+num_addv; for(j=tnum_x+1;j=num_x;j+) if(j=tnum_x+num_addv) aitnum_x+num_addv=1; else aij=0; break; /switch/增加松弛变量、剩余变量、人工变量、确定基变量/显示标准化后的方程组printf(n化为标准形式后：nn);if(ma_mi=1) printf(max z= );else printf(max z= );printf(%lg x%d,c1,1);for(i=2;i=num_x;i+) k=0; for(j=1;j=0) printf( +%lg x%d,ci,i); else printf( %lg x%d,ci,i);printf(nst:n);for(i=1;i=num_st;i+) k=0; for(j=1;j=0&k!=0) printf( +%lg x%d,aij,j); else if(aij=0&k=0) printf( %lg x%d,aij,j); else printf( %lg x%d,aij,j); k=1; printf( = %lgn,bi); printf( x1x%d=0,num_x);void iterative() int i,j,k,k_a,k_f,l; /k_a,k_f值为0或1，记录当前下标在arti或base里的搜索结果int base_elem;int base_out,base_in;double sigmaMAX,temp;double value_be; /高斯消元里保存主元素值printf(nn第%d次迭代：nn,stop); for(i=1;i=num_st;i+) printf(c%d=%lgt,basei,cbasei); printf(b%d=%lgt,i,bi); switch(step) case 1: for(j=1;j=num_x;j+) printf(a%d%d=%lgt,i,j,aij); printf(n); break; case 2: for(j=1;j=num_x;j+) k_a=0; for(l=1;l=num_ar;l+) if(j=artil)k_a=1; if(k_a!=1) printf(a%d%d=%lgt,i,j,aij); printf(n); break; /求检验数sigmafor(i=1;i=num_x;i+) sigmai=ci; for(j=1;j=num_st;j+) sigmai-=cbasej*aji; for(j=1;j=num_st;j+) if(i=basej) sigmai=0; switch(step) case 1: printf(sigma%d=%lgt,i,sigmai); break; case 2: k_a=0; for(l=1;l=num_ar;l+) if(i=artil) k_a=1; if(k_a!=1) printf(sigma%d=%lgt,i,sigmai); break; putchar(n);/检验检验数sigma是否全小于等于0k=0;for(i=1;i0) k=1;if(k=0) /sigma是全小于等于0时，检查是否为无穷多最优解 for(i=1;i=num_x;i+) k_f=k_a=0; for(j=1;j=num_ar;j+) if(i=artij) k_a=1; if(sigmai=0&k_a!=1) for(j=1;j=num_st;j+) if(i=basej) k_f=1; if(k_f=0) status=-1; return; status=1; return;/检查是否为无界解for(i=1;i0) for(j=1;j0) k_f=1; if(k_f!=1) status=0; return; /确定换入变量for(i=1;i=num_x;i+) k=0; for(j=1;j0) temp=sigmai-1;/temp赋初值for(i=1;i=num_x;i+) k=0; for(j=1;jtemp&sigmai0) base_in=i; temp=sigmai; /确定换出变量for(i=1;i0) temp=bi/aibase_in+1; break; /temp赋初值for(i=1;i=num_st;i+) if(bi/aibase_in0) for(j=1;j=num_ar;j+) if(basei=artij) base_out=basei; base_elem=i; temp=bi/aibase_in; break; /人工变量优先换出 if(bi/aibase_in0)