两阶段法C程序.doc
《两阶段法C程序.doc》由会员分享，可在线阅读，更多相关《两阶段法C程序.doc（18页珍藏版）》请在冰点文库上搜索。
两阶段法C程序
/*************************************************************************
单纯型法解线性规划问题（两阶段法）
编程环境:
VC++6.0
方程组输入说明:
变量非负，按提示输入相关参数。
*************************************************************************/
#include#include#defineMAX100
#defineSTP100
intstop=1;//迭代记数变量
intstatus;//iterative迭代返回值:
1唯一最优，0无界解，-1无穷多最优解-2迭代超
过限制次数
intstep=1;//目前阶段
doublea[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0;//方程组相关系数
intnum_x;//变量个数
intnum_st;//约束方程数
intnum_ar=0;//人工变量个数
intarti[MAX];//人工变量下标
intbase[MAX];//基变量下标
intma_mi;//1为求最大值，2为求最小值
voidcreate（）;//建立方程组
voiditerative（）;//单纯型法迭代voidoutput（）;//输出结果
voidbanner（）;//打印程序标题
voidexchange（）;//交换两阶段价值系数voidshow（）;//输出方程组
voidmain（）{
inti,j,k;
banner（）;
create（）;
//保存原价值系数，转换为第一阶段价值系数for（i=1;i<=num_x;i++）{k=0;
for（j=1;j<=num_ar;j++）if（i==arti[j]）k=1;
if（k==1）temp_c=-1;elsetemp_c=0;
}
exchange（c,temp_c）;
printf（"\n\n第一阶段问题为:
\n\n"）;show（）;
step++;
printf（"\n\n按回车开始第一阶段迭代"）;getchar（）;
getchar（）;
iterative（）;
if（status==-2）{puts（"迭代超过限制次数强行终止～\n"）;puts（"\n按回车结束"）;
getchar（）;
exit（0）;
}
output（）;
if（max!
=0）{
puts（"\n\n原问题无可行解。
\n"）;puts（"\n按回车结束"）;
getchar（）;
exit（0）;
}
//转换为第二阶段价值系数
exchange（c,temp_c）;//把人工变量列全设为0
for（i=1;i<=num_ar;i++）{
c[arti]=0;
for（j=1;j<=num_st;j++）a[j][arti]=0;
}
puts（"\n\n第二阶段问题为:
\n\n"）;show（）;
puts（"\n\n按回车开始第二阶段迭代"）;getchar（）;
iterative（）;
switch（status）{case1:
output（）;
puts（"\n\n原问题有唯一最优解。
\n"）;puts（"\n按回车结束"）;
getchar（）;
exit（0）;
case0:
puts（"\n\n原问题为无界解。
\n"）;
puts（"\n按回车结束"）;
getchar（）;
exit（0）;
case-1:
output（）;
puts（"\n\n原问题有无穷多最优解。
\n"）;
puts（"\n按回车结束"）;
getchar（）;
exit（0）;
case-2:
puts（"迭代超过限制次数强行终止～\n"）;
puts（"\n按回车结束"）;
getchar（）;
exit（0）;
}//switch
}
voidbanner（）{
printf（"\t\t****************************************\n"）;
printf（"\t\t单纯型法解线性规划问题\n"）;
printf（"\t\t作者:
Thunder\n"）;
printf（"\t\t****************************************\n"）;
printf（"\n"）;
}
voidshow（）{
//对方程组以自然的格式输出，系数为零的x不显示//为1的不显示系数1，-1系数只显示负号
inti,j,k;
switch（step）{
case1:
printf（"minz="）;
printf（"x[%d]",arti[1]）;for（i=2;i<=num_ar;i++）printf（"+x[%d]",arti）;
break;
case2:
printf（"maxz="）;
printf（"%lgx[%d]",c[1],1）;for（i=2;i<=num_x;i++）{if（c==1）printf（"+x[%d]",i）;elseif（c==-1）printf（"-x[%d]",i）;
elseif（c>=0）printf（"+%lgx[%d]",c,i）;
elseprintf（"%lgx[%d]",c,i）;}
break;
}
printf（"\nst:
\n"）;
for（i=1;i<=num_st;i++）{
k=0;
for（j=1;j<=num_x;j++）{
if（a[j]!
=0）{
if（a[j]==1&&k!
=0）printf（"+x[%d]",j）;elseif（a[j]==1&&k==0）printf（"x[%d]",j）;
elseif（a[j]==-1）printf（"-x[%d]",j）;elseif（a[j]>=0&&k!
=0）printf（"+%lgx[%d]",a[j],j）;
elseif（a[j]>=0&&k==0）printf（"%lgx[%d]",a[j],j）;
elseprintf（"%lgx[%d]",a[j],j）;k=1;
}
}
printf（"==%lg\n",b）;
}
printf（"x[1]~x[%d]>=0",num_x）;}
voidexchange（）{
inti;
doubletemp[MAX];
for（i=1;i<=num_x;i++）{
temp=temp_c;
temp_c=c;
c=temp;
}
}
voidcreate（）
{
//输入方程组系数，每个方程输完后回显确认
inti,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;
charconfirm;
while
（1）
{
printf（"请选择:
1、求最大值，2、求最小值:
（1/2）"）;scanf（"%d",&ma_mi）;
if（ma_mi!
=1&&ma_mi!
=2）printf（"输入错误，重新选择。
"）;elsebreak;
}
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",&c）;
}
if（ma_mi==1）printf（"maxz="）;elseprintf（"minz="）;printf（"%lgx[%d]",c[1],1）;for（i=2;i<=num_x;i++）{if（c>=0）printf（"+%lgx[%d]",c,i）;
elseprintf（"%lgx[%d]",c,i）;}
printf（"\n正确吗,:
（y/n）"）;
getchar（）;
confirm=getchar（）;
if（confirm=='y'）break;elseif（confirm=='n'）continue;}
printf（"输入约束方程组个数:
"）;
scanf（"%d",&num_st）;
for（i=1;i<=num_st;i++）{printf（"st.%d:
\n",i）;
while
（1）{
printf（"请选择:
1、==，2、>=，3、<=:
（1/2/3）"）;scanf（"%d",&re_st）;
if（re_st!
=1&&re_st!
=2&&re_st!
=3）printf（"输入错误，请重新选择。
"）;
elsebreak;
}
printf（"输入技术系数:
\n"）;
for（j=1;j<=num_x;j++）{printf（"a%d=",j）;
scanf（"%lf",&a[j]）;
}
printf（"输入资源拥有量:
\nb%d=",i）;scanf（"%lf",&b）;
printf（"st.%i:
\n",i）;
printf（"%lgx[%d]",a[1],1）;
for（j=2;j<=num_x;j++）{
if（a[j]>=0）printf（"+%lgx[%d]",a[j],j）;elseprintf（"%lgx[%d]",a[j],j）;}
switch（re_st）{
case1:
printf（"==%lg",b）;break;case2:
printf（">=%lg",b）;break;case3:
printf（"<=%lg",b）;break;}
while
（1）{
printf（"\n正确吗,（y/n）"）;
getchar（）;
confirm=getchar（）;
if（confirm=='y'）break;
elseif（confirm=='n'）{i-=1;break;}}
}
//显示输入的方程组
printf（"\n原问题为:
\n\n"）;
if（ma_mi==1）printf（"maxz="）;elseprintf（"minz="）;
printf（"%lgx[%d]",c[1],1）;
for（i=2;i<=num_x;i++）{
if（c==1）printf（"+x[%d]",i）;elseif（c==-1）printf（"-x[%d]",i）;elseif（c>=0）printf（"+%lgx[%d]",c,i）;elseprintf（"%lgx[%d]",c,i）;}
printf（"\nst:
\n"）;
for（i=1;i<=num_st;i++）{
k=0;
for（j=1;j<=num_x;j++）{
if（a[j]!
=0）{
if（a[j]==1&&k!
=0）printf（"+x[%d]",j）;elseif（a[j]==1&&k==0）printf（"x[%d]",j）;elseif（a[j]==-1）printf（"-x[%d]",j）;elseif（a[j]>=0&&k!
=0）printf（"+%lgx[%d]",a[j],j）;
elseif（a[j]>=0&&k==0）printf（"%lgx[%d]",a[j],j）;
elseprintf（"%lgx[%d]",a[j],j）;k=1;
}
}
switch（re_st）{
case1:
printf（"==%lg\n",b）;break;
case2:
printf（">=%lg\n",b）;break;
case3:
printf（"<=%lg\n",b）;break;
}
}
printf（"x[1]~x[%d]>=0\n",num_x）;
tnum_x=num_x;
for（i=1;i<=num_st;i++）{switch（re_st）{
case1:
case3:
num_x+=1;
break;
case2:
num_x+=2;
break;
}
}
//化为标准形式
if（ma_mi==2）for（i=1;i<=tnum_x;i++）c*=-1;//求最小值时，系数变相反数
for（i=1;i<=num_st;i++）{switch（re_st）{
case1:
num_addv++;
num_ba++;
num_ar++;
c[tnum_x+num_addv]=0;base[num_ba]=arti[num_ar]=tnum_x+num_addv;
for（j=tnum_x+1;j<=num_x;j++）
if（j==tnum_x+num_addv）a[tnum_x+num_addv]=1;
elsea[j]=0;
break;
case2:
num_addv++;
c[tnum_x+num_addv]=0;
num_addv++;
num_ba++;
num_ar++;
c[tnum_x+num_addv]=0;
base[num_ba]=arti[num_ar]=tnum_x+num_addv;
for（j=tnum_x+1;j<=num_x;j++）if（j==tnum_x+num_addv-1）a[tnum_x+num_addv-1]=-1;
elseif（j==tnum_x+num_addv）a[tnum_x+num_addv]=1;
elsea[j]=0;
break;
case3:
num_addv++;
num_ba++;
c[tnum_x+num_addv]=0;
base[num_ba]=tnum_x+num_addv;for（j=tnum_x+1;j<=num_x;j++）if（j==tnum_x+num_addv）a[tnum_x+num_addv]=1;
elsea[j]=0;
break;
}//switch
}//增加松弛变量、剩余变量、人工变量、确定基变量
//显示标准化后的方程组
printf（"\n化为标准形式后:
\n\n"）;
if（ma_mi==1）printf（"maxz="）;elseprintf（"maxz'="）;
printf（"%lgx[%d]",c[1],1）;for（i=2;i<=num_x;i++）{
k=0;
for（j=1;j<=num_ar;j++）
if（i==arti[j]）k=1;
if（k==1）printf（"-Mx[%d]",i）;elseif（c==1）printf（"+x[%d]",i）;elseif（c==-1）printf（"-x[%d]",i）;elseif（c>=0）printf（"+%lgx[%d]",c,i）;
elseprintf（"%lgx[%d]",c,i）;}
printf（"\nst:
\n"）;
for（i=1;i<=num_st;i++）{
k=0;
for（j=1;j<=num_x;j++）{
if（a[j]!
=0）{
if（a[j]==1&&k!
=0）printf（"+x[%d]",j）;elseif（a[j]==1&&k==0）printf（"x[%d]",j）;elseif（a[j]==-1）printf（"-x[%d]",j）;elseif（a[j]>=0&&k!
=0）printf（"+%lgx[%d]",a[j],j）;
elseif（a[j]>=0&&k==0）printf（"%lgx[%d]",a[j],j）;
elseprintf（"%lgx[%d]",a[j],j）;k=1;
}
}
printf（"==%lg\n",b）;
}
printf（"x[1]~x[%d]>=0",num_x）;}
voiditerative（）{
inti,j,k,k_a,k_f,l;//k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果
intbase_elem;
intbase_out,base_in;
doublesigma[MAX],temp;
doublevalue_be;//高斯消元里保存主元素值
printf（"\n\n第%d次迭代:
\n\n",stop）;
for（i=1;i<=num_st;i++）{
printf（"c%d=%lg\t",base,c[base]）;printf（"b%d=%lg\t",i,b）;
switch（step）{
case1:
for（j=1;j<=num_x;j++）
{
printf（"a[%d][%d]=%lg\t",i,j,a[j]）;}
printf（"\n"）;
break;
case2:
for（j=1;j<=num_x;j++）{
k_a=0;
for（l=1;l<=num_ar;l++）if（j==arti[l]）k_a=1;if（k_a!
=1）printf（"a[%d][%d]=%lg\t",i,j,a[j]）;}
printf（"\n"）;
break;
}
}
//求检验数sigma
for（i=1;i<=num_x;i++）{
sigma=c;
for（j=1;j<=num_st;j++）sigma-=c[base[j]]*a[j];
for（j=1;j<=num_st;j++）if（i==base[j]）sigma=0;
switch（step）{
case1:
printf（"sigma[%d]=%lg\t",i,sigma）;break;
case2:
k_a=0;
for（l=1;l<=num_ar;l++）if（i==arti[l]）k_a=1;
if（k_a!
=1）printf（"sigma[%d]=%lg\t",i,sigma）;
break;
}
}
putchar（'\n'）;
//检验检验数sigma是否全小于等于0
k=0;
for（i=1;i<=num_x;i++）{
if（sigma>0）
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==arti[j]）k_a=1;
if（sigma==0&&k_a!
=1）{
for（j=1;j<=num_st;j++）if（i==base[j]）k_f=1;
if（k_f==0）{status=-1;return;}}
}
status=1;
return;
}
//检查是否为无界解
for（i=1;i<=num_x;i++）{
k_f=0;
if（sigma>0）{
for（j=1;j<=num_st;j++）if（a[j]>0）k_f=1;
if（k_f!
=1）{status=0;return;}
}
}
//确定换入变量
for（i=1;i<=num_x;i++）{k=0;
for（j=1;j<=num_st;j++）if（i==base[j]）k=1;
if（k==0&&sigma>0）temp=sigma-1;
}//temp赋初值
for（i=1;i<=num_x;i++）{k=0;
for（j=1;j<=num_st;j++）if（i==base[j]）k=1;
if（k==0）
if（sigma>temp&&sigma>0）{base_in=i;
temp=sigma;
}
}
//确定换出变量
for（i=1;i<=num_st;i++）if（a[base_in]>0）{
temp=b/a[base_in]+1;break;
}//temp赋初值
for（i=1;i<=num_st;i++）{if（b/a[base_in]<=temp&&a[base_in]>0）{
for（j=1;j<=num_ar;j++）if（base==arti[j]）{
base_out=base;
base_elem=i;
temp=b/a[base_in];
break;
}
}//人工变量优先换出
if（b/a[base_in]0）{
base_out=base;
base_elem=i;
temp=b/a[base_in];
}
}
printf（"基变量:
"）;
for（i=1;i<=num_st;i++）printf（"x[%d]",base）;
printf（"换入变量:
x[%d]换出变量:
x[%d]",base_in,base_out）;
//基变量变换，进行新方程初始化后迭代
for（i=1;i<=num_st;i++）{
if（base==base_out）base=base_in;}
//初始化主元素行系数
value_be=a[base_elem][base_in];b[base_elem]/=value_be;
for（i=1;i<=num_x;i++）a[base_elem]/=value_be;
for（i=1;i<=num_st;i++）{
if（i!
=base_elem）{
b-=b[base_elem]*a[base_in];value_be=a[base_in];
for（j=1;j<=num_x;j++）a[j]-=a[base_elem][j]*value_be;
}
}
stop+
升级会员 