个人写的运输问题算法，还望指教
<P>/*************************************************************************表上作业法解运输问题
编程环境：VC++6.0
程序说明：
Vogel法求初始解，位势法检验是否最优，递归搜索闭回路改进解。
*************************************************************************/
#include <stdio.h>
#include <stdlib.h></P>
<P>#define MAX 100
#define M 999999</P>
<P>int status; //1唯一最优解，-1无穷多最优解</P>
<P>int num_a,num_b;
double a,b,temp_a,temp_b;
double u,v,pu,pv;
double ab,temp_ab;
double base;
int pbase;
struct element {
int r;
int c;
double value;
};
enum direction {mid,up,down,left,right};</P>
<P>void create();
void banner();
double dabs(double d);
void findinit();
void computeuv();
int check();
int circle(enum direction dir,struct element cir[],int *t);
void improve();
void output();</P>
<P>void main() {
banner();
create();
printf("\n按回车确认后开始求解");
getchar();
getchar();
findinit();
improve();
switch(status) {
case 1:
output();
puts("\n原问题有唯一最优解。\n");
puts("\n按回车结束");
getchar();
exit(0);
case -1:
output();
puts("\n原问题有无穷多最优解。\n");
puts("\n按回车结束");
getchar();
exit(0);
}
}</P>
<P>void banner() {
printf("\t\t****************************************\n");
printf("\t\t 表上作业法解运输问题\n");
printf("\t\t Thunder\n");
printf("\t\t****************************************\n");
printf("\n");
}</P>
<P>void create() {
int i,j;
double sum_a,sum_b;
char confirm;
while(1) {
printf("请输入产地个数：");
scanf("%d",&num_a);
for(i=1;i<=num_a;i++) {
printf("A%d产量：",i);
scanf("%lf",&a);
}
for(i=1;i<=num_a;i++) printf("A%d产量：%lg\t",i,a);
printf("\n正确吗？：(y/n)");
getchar();
confirm=getchar();
if (confirm=='y') break;
else if(confirm=='n') continue;
}
while(1) {
printf("\n请输入销地个数：");
scanf("%d",&num_b);
for(i=1;i<=num_b;i++) {
printf("B%d销量：",i);
scanf("%lf",&b);
}
for(i=1;i<=num_b;i++) printf("B%d销量：%lg\t",i,b);
printf("\n正确吗？：(y/n)");
getchar();
confirm=getchar();
if (confirm=='y') break;
else if(confirm=='n') continue;
}
putchar('\n');
for(i=1;i<=num_a;i++) {
for(j=1;j<=num_b;j++) {
printf("A%d到B%d运价：",i,j);
scanf("%lf",&ab);
}
for(j=1;j<=num_b;j++) printf("A%d到B%d：%lg\t",i,j,ab);
printf("\n正确吗？：(y/n)");
getchar();
confirm=getchar();
if(confirm=='n') i--;
putchar('\n');
}
//处理产销不平衡的情况
sum_a=sum_b=0;
for(i=1;i<=num_a;i++) sum_a+=a;
for(i=1;i<=num_b;i++) sum_b+=b;</P>
<P> printf("总产量：%lg\t总销量：%lg",sum_a,sum_b);
if(sum_a==sum_b) printf("\t产销平衡。");
else if(sum_a>sum_b) {
printf("\t供大于求，增加假想销地B%d。\n",++num_b);
b=sum_a-sum_b;
for(i=1;i<=num_a;i++) ab=0;
}
else if(sum_a<sum_b){
printf("\t供不应求，增加假想产地A%d。\n",++num_a);
a=sum_b-sum_a;
for(i=1;i<=num_b;i++) ab=0;
}
//求解前的准备
for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++)
base=pbase=0;
for(i=1;i<=num_a;i++) temp_a=a;
for(i=1;i<=num_b;i++) temp_b=b;
for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++) temp_ab=ab;
//回显问题
printf("\n\n原问题为：\n\n");
printf("产量：\n ");
for(i=1;i<=num_a;i++) printf("A%d:%lg\t",i,a);
printf("\n运量：\n ");
for(i=1;i<=num_b;i++) printf("B%d:%lg\t",i,b);
printf("\n运价为：\n");
for(i=1;i<=num_a;i++) {
putchar(' ');
for(j=1;j<=num_b;j++)
printf("A%d->B%d:%lg\t",i,j,ab);
putchar('\n');
}
}</P>
<P>double dabs(double d) {
if(d>=0) return d;
else return -d;
}</P>
<P>void findinit() {
int i,j,k;
double r_penum,c_penum;
struct largest {
char rc;
int num;
double value;
};
struct largest lar1,lar2;
int r=0,c=0;
double a1,a2,b1,b2,temp;</P>
<P> for(i=1;i<=num_a;i++) {
temp=temp_ab;
for(j=1;j<=num_b;j++)
if(temp_ab>temp) temp=temp_ab;
a1=a2=temp;
for(j=1;j<=num_b;j++)
if(temp_ab<=a1) {
a2=a1;
a1=temp_ab;
}
else if(temp_ab<=a2) a2=temp_ab;
r_penum=dabs(a1-a2);
}</P>
<P> for(i=1;i<=num_b;i++) {
temp=temp_ab;
for(j=1;j<=num_a;j++)
if(temp_ab>temp) temp=temp_ab;
b1=b2=temp;
for(j=1;j<=num_a;j++)
if(temp_ab<=b1) {
b2=b1;
b1=temp_ab;
}
else if(temp_ab<=b2) b2=temp_ab;
c_penum=dabs(b1-b2);
}
/*
for(i=1;i<=num_a;i++) printf("pa%d=%lg ",i,r_penum);
putchar('\n');
for(i=1;i<=num_b;i++) printf("pb%d=%lg ",i,c_penum);
*/
temp=r_penum;
for(i=1;i<=num_a;i++) if(r_penum<temp) temp=r_penum;
for(i=1;i<=num_b;i++) if(c_penum<temp) temp=c_penum;</P>
<P> //考虑了有两个罚数相等的情况，大于两个相等只取其中两个进行比较
lar1.value=lar2.value=temp;
lar1.num=lar2.num=1;
lar1.rc=lar2.rc='r';
for(i=1;i<=num_a;i++)
if(r_penum>=lar1.value) {
lar2=lar1;
lar1.rc='r';
lar1.num=i;
lar1.value=r_penum;
}
else if(r_penum>=lar2.value) {
lar2.rc='r';
lar2.num=i;
lar2.value=r_penum;
}</P>
<P> for(i=1;i<=num_b;i++)
if(c_penum>=lar1.value) {
lar2=lar1;
lar1.rc='c';
lar1.num=i;
lar1.value=c_penum;
}
else if(c_penum>=lar2.value) {
lar2.rc='c';
lar2.num=i;
lar2.value=c_penum;
}</P>
<P> if(lar1.value==lar2.value&&(lar1.num!=lar2.num||lar1.rc!=lar2.rc)) {
if(lar1.rc=='r'&&lar2.rc=='r') {
temp=temp_ab;
r=lar1.num;
c=1;
for(i=1;i<=num_b;i++) {
if(temp_ab<temp) {
temp=temp_ab;
r=lar1.num;
c=i;
}
if(temp_ab<temp) {
temp=temp_ab;
r=lar2.num;
c=i;
}
}
}
if(lar1.rc=='c'&&lar2.rc=='c') {
temp=temp_ab;
r=1;
c=lar1.num;
for(i=1;i<=num_a-1;i++) {
if(temp_ab<temp) {
temp=temp_ab;
c=lar1.num;
r=i;
}
if(temp_ab<temp) {
temp=temp_ab;
c=lar2.num;
r=i;
}
}
}
if(lar1.rc=='r'&&lar2.rc=='c') {
temp=temp_ab;
r=lar1.num;
c=1;
for(i=1;i<=num_b;i++)
if(temp_ab<temp) {
temp=temp_ab;
r=lar1.num;
c=i;
}
for(i=1;i<=num_a;i++)
if(temp_ab<temp) {
temp=temp_ab;
c=lar2.num;
r=i;
}
}
if(lar1.rc=='c'&&lar2.rc=='r') {
temp=temp_ab;
r=1;
c=lar1.num;
for(i=1;i<=num_b;i++)
if(temp_ab<temp) {
temp=temp_ab;
r=lar2.num;
c=i;
}
for(i=1;i<=num_a;i++)
if(temp_ab<temp) {
temp=temp_ab;
c=lar1.num;
r=i;
}
}
}
else {
if(lar1.rc=='r') {
r=lar1.num;
c=1;
temp=temp_ab;
for(i=1;i<=num_b;i++)
if(temp_ab<temp) {
c=i;
temp=temp_ab;
}
}
else {
r=1;
c=lar1.num;
temp=temp_ab;
for(i=1;i<=num_a;i++)
if(temp_ab<temp) {
r=i;
temp=temp_ab;
}
}
}
pbase=1;
if(temp_a>temp_b) {
base=temp_b;
temp_a=temp_a-temp_b;
temp_b=0;
for(i=1;i<=num_a;i++) temp_ab=M;
}
else if(temp_a<temp_b) {
base=temp_a;
temp_b=temp_b-temp_a;
temp_a=0;
for(i=1;i<=num_b;i++) temp_ab=M;
}
else if(temp_a==temp_b) {
base=temp_a;
temp_a=temp_b=0;
for(i=1;i<=num_a;i++) temp_ab=M;
for(i=1;i<=num_b;i++) temp_ab=M;
k=0;
for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;
for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;
if(k!=0) {
k=0;
for(i=1;i<=num_a;i++) if(pbase!=1) {k=1;break;}
for(j=1;j<=num_b;j++) if(pbase!=1) {k=2;break;}
if(k==1) pbase=1;
else if(k==2) pbase=1;
}
}
k=0;
for(i=1;i<=num_a;i++) if(temp_a!=0) k=1;
for(i=1;i<=num_b;i++) if(temp_b!=0) k=1;
if(k==0) return;
findinit();
}</P>
<P>void computeuv() {
int i,j,k;
for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++)
if(pbase==1) {
if(pu==1) {v=ab-u; pv=1;}
if(pv==1) {u=ab-v; pu=1;}
}
k=0;
for(i=1;i<=num_a;i++) if(pu==0) k=1;
for(i=1;i<=num_b;i++) if(pv==0) k=1;
if(k==1) computeuv();
}</P>
<P>int check() {
int i,j,k,l;
k=l=0;
for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++)
if(pbase==0) {
base=ab-u-v;
if(base<0) k=1;
else if(base==0) l=1;
}
/* for(i=1;i<=num_a;i++){
for(j=1;j<=num_b;j++) printf("base %lg\t",base);
putchar('\n');}
for(i=1;i<=num_a;i++){
for(j=1;j<=num_b;j++) printf("pbase %d\t",pbase);
putchar('\n');}
*/
if(k==0&&l==0) {status=1; return 1;}
else if(k==0&&l!=0) {status=-1; return 1;}
else return 0;
}</P>
<P>int circle(enum direction dir,struct element cir[],int *t) {
int i,j,k;
/*
putchar('\n');
for(i=1;i<=*t;i++) printf("%d: r%d c%d\t",i, cir.r,cir.c);
putchar('\n');
*/
if((*t)!=1&&cir[(*t)].r==cir.r&&cir[*t].c==cir.c) {
t--;
return 1;
}
if(dir!=down) {
k=0;
for(i=cir[*t].r-1;i>=1;i--)
if(pbase.c]==1||(i==cir.r&&cir[*t].c==cir.c)) {k=1; break;}
for(j=2;j<=*t;j++) if(i==cir.r&&cir[*t].c==cir.c) k=0;
if(k==1) {
if(dir==up) cir[*t].value=0;
else cir[*t].value=1;
(*t)++;
cir[*t].r=i;
cir[*t].c=cir[(*t)-1].c;
if(circle(up,cir,t)) return 1;
}
}
if(dir!=up) {
k=0;
for(i=cir[*t].r+1;i<=num_a;i++)
if(pbase.c]==1||(i==cir.r&&cir[*t].c==cir.c)) {k=1; break;}
for(j=2;j<=*t;j++) if(i==cir.r&&cir[*t].c==cir.c) k=0;
if(k==1) {
if(dir==down) cir[*t].value=0;
else cir[*t].value=1;
(*t)++;
cir[*t].r=i;
cir[*t].c=cir[(*t)-1].c;
if(circle(down,cir,t)) return 1;
}
}
if(dir!=right) {
k=0;
for(i=cir[*t].c-1;i>=1;i--)
if(pbase.r]==1||(cir[*t].r==cir.r&&i==cir.c)) {k=1; break;}
for(j=2;j<=*t;j++) if(cir[*t].r==cir.r&&i==cir.c) k=0;
if(k==1) {
if(dir==left) cir[*t].value=0;
else cir[*t].value=1;
(*t)++;
cir[*t].r=cir[(*t)-1].r;
cir[*t].c=i;
if(circle(left,cir,t)) return 1;
}
}
if(dir!=left) {
k=0;
for(i=cir[*t].c+1;i<=num_b;i++)
if(pbase.r]==1||(cir[*t].r==cir.r&&i==cir.c)) {k=1; break;}
for(j=2;j<=*t;j++) if(cir[*t].r==cir.r&&i==cir.c) k=0;
if(k==1) {
if(dir==right) cir[*t].value=0;
else cir[*t].value=1;
(*t)++;
cir[*t].r=cir[(*t)-1].r;
cir[*t].c=i;
if(circle(right,cir,t)) return 1;
}
}
(*t)--;
return 0;
}</P>
<P>void improve() {
int i,j,k,t;
struct element base_in,base_out,cir;</P>
<P> for(i=1;i<=num_a;i++) pu=0;
for(i=1;i<=num_b;i++) pv=0;
u=0; pu=1;
computeuv();
if(check()) return;
for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++)
if(pbase==0) break;
base_in.r=i;
base_in.c=j;
base_in.value=base;</P>
<P> for(i=1;i<=num_a;i++)
for(j=1;j<=num_b;j++)
if(pbase==0&&base<base_in.value) {
base_in.r=i;
base_in.c=j;
base_in.value=base;
}</P>
<P> t=1;
cir.r=base_in.r;
cir.c=base_in.c;
cir.value=1;
if(!circle(mid,cir,&t)) {
printf("程序出错！按回车结束");
getchar();
exit(0);
}
t--;
// for(i=1;i<=t;i++) printf("%d:r%d c%d v%lg\t",i,cir.r,cir.c,cir.value);
// putchar('\n');</P>
<P> for(i=2;i<=t;i++) if(cir.value==1) break;
base_out=cir;
base_out.value=base.r].c];
k=1;
for(i=1;i<=t;i++)
if(k%2==0&&cir.value==1&&base.r].c]<base_out.value) {
base_out=cir;
base_out.value=base.r].c];
k++;
}
else if(cir.value==1) k++;
base.r].c]=0;
k=1;
for(i=1;i<=t;i++) {
if(k%2==1&&cir.value==1) {
base.r].c]+=base_out.value;
k++;
}
else if(k%2==0&&cir.value==1) {
base.r].c]-=base_out.value;
k++;
}
}
pbase=0;
pbase=1;</P>
<P> improve();
}</P>
<P>void output() {
int i,j;
double sum=0;
printf("\n运量为：\n");
for(i=1;i<=num_a;i++) {
putchar(' ');
for(j=1;j<=num_b;j++)
if(pbase==1) {
printf("A%d->B%d:%lg\t",i,j,base);
sum+=base*ab;
}
else printf("A%d->B%d:0\t",i,j);
putchar('\n');
}
printf("\n最低总运费为：%lg\n",sum);
}
</P> good! 就是希望下次把格式稍稍注意下，这样可读性太差了呀~ 太乱了吧！！！！！！！！！！:L 乱了让人不想看了。。。。。。。。:funk: 好！顶顶！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
页:
[1]