500分重金求购现行规划单纯形算法(10分)

我会陆续把分数凑齐

分出的不少，无人问津。

有人否》？

是线性规划的单纯型法吗?

然

书上讲的很清楚啊
清华的运筹学

然。

is there somebody?

再加500

求购心切，不知用于商业，还是科研？是gis还是mis？

呵呵有否？

哇牙压！！！！
气四我也

明天再来看看，呵呵，在写呢，c语言的，
改进的单纯型---如果成了，就帖出来啦

书上讲的很清楚啊
清华的运筹学
没有用很久了，忘了[]

总算完成了，下面是代码。
又：因为我是计算机系的，运筹学并没有学过，这次凑巧帮管院一个同学写单纯形的代码，
所以就有了这个。是从昨天开始看书的，如果有错误，还请见谅------觉得那个运筹学还
真不容易呢，虽比不上咱们的离散：）~~~~~~~~
/*
*data.txt
*/

5 2 1 0 0
2 3 0 1 0
1 5 0 0 1
170 100 150
10 18 0 0 0
1 0 0
0 1 0
0 0 1
1 0 0
0 1 0
0 0 1
0 0 0
2 3 4

/*
本题的例子是：

max Z=10*x1+18*x2;
s.t. 5*x1+2*x2<=170
2*x1+3*x2<=100
x1+5*x2<=150
x1,x2>=0

本文件的数据是上式经过加入松弛变量后的标准形式的数据

*/
/*
*fmain.cpp
*/
#include <stdio.h>
#include <stdlib.h>
#define M 3
#define N 5
/* 解决形如
max z=cx
s.t. Ax=b,
x>=0
的线形规划问题
_B[M][M]是B[M][M]的逆阵
*/
float A[M][N],b[M],
c[N],B[M][M],
cn[M],X[M],Y[M],
Kao[N],P[M],
E[M][M],_B[M][M];
/*
解序号
*/
int Xcount[M];
float sita;
/*
进基变量，出基变量
*/
int xin,xout;
int init(FILE *pf);
void computeE();
void compute_B();
void computeXY();
int computeKao();
int computePsita();
void computeBcn();
int succ();
int fall();
void main()
{
FILE *pf;
float result=0.0;
if(!init(pf))
{
printf("Error:can't open data file,please check.../n");
exit(-1);
}
computeXY();
xin=computeKao();
while(!succ())
{
xout=computePsita();
if(fall())
{
printf("Fall...already exit.../n");
exit(0);
}
computeBcn();
computeE();
compute_B();
computeXY();
xin=computeKao();
}
printf("Successful:/n");
for(int i=0;i<M;i++)
printf("X[%d]=%f/t",Xcount+1,X);
for(int i=0;i<M;i++)
result+=c[Xcount]*X;
printf("/nmax Z=%f/n",result);
}
/*
用data.txt文件初始化，包括：
A,b,c,B,_B,cn,Xcount
*/
int init(FILE *pf)
{
pf=fopen("data.txt","r");
if(pf==NULL){
fclose(pf);
return 0;
}
/*input A[M][N]*/
for(int i=0;i<M;i++)
for(int j=0;j<N;j++){
fscanf(pf,"%f",&amp;A[j]);
}
/*input b[M]*/
for(int i=0;i<M;i++){
fscanf(pf,"%f",&amp;b);
}
/*input c[N]*/
for(int i=0;i<N;i++){
fscanf(pf,"%f",&amp;c);
}
/*input B[M][M]*/
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
fscanf(pf,"%f",&amp;B[j]);
/*input _B[M][M]*/
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
fscanf(pf,"%f",&amp;_B[j]);
}
/*input cn[M]*/
for(int i=0;i<M;i++)
fscanf(pf,"%f",&amp;cn);

/* input Xcount[M] */
for(int i=0;i<M;i++){
fscanf(pf,"%d",&amp;Xcount);
}
/*其它*/
for(int i=0;i<M;i++)
P=X=Y=0;
for(int i=0;i<N;i++)
Kao=0;
fclose(pf);
return 1;
}
/*
计算初等变换矩阵E
*/
void computeE()
{
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
{
E[j]=0;
if(i==j)
E[j]=1;
}
for(int i=0;i<M;i++)
E[xout]=-P/P[xout];
E[xout][xout]=1/P[xout];
}
/*
计算B逆矩阵_B
*/
void compute_B()
{
float __B[M][M];
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
__B[j]=0;
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
for(int k=0;k<M;k++)
__B[j]+=E[k]*_B[k][j];
for(int i=0;i<M;i++)
for(int j=0;j<M;j++){
_B[j]=__B[j];
}
}
/*
计算 X=_B*b ,Y=_B*cn
*/
void computeXY()
{
for(int i=0;i<M;i++)
P=X=Y=0;
for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
X+=_B[j]*b[j];
}
for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
Y+=cn[j]*_B[j];
}

}
/* 计算检验数 kao=c-cn*_B*A
xin<-return
*/
int computeKao()
{
float midval=0.0;
int k;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++)
midval+=Y[j]*A[j];
Kao=c-midval;
midval=0;
}
midval=Kao[0];
k=0;
for(int j=0;j<N;j++)
if(Kao[j]>midval){
midval=Kao[j];
k=j;
}
return k;
}
/*计算进基列向量P,判断出基变量
xout<-return
*/
int computePsita()
{
int k=0;
for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
P+=_B[j]*A[j][xin];
}
sita=X[0]/P[0];
for(int j=0;j<M;j++)
if(sita>X[j]/P[j])
{
sita=X[j]/P[j];
k=j;
}
return k;
}
/*
计算矩阵B,cn
*/
void computeBcn()
{
for(int i=0;i<M;i++)
B[xout]=A[xin];
cn[xout]=c[xin];
Xcount[xout]=xin;
}
/*
判断是否成功
*/
int succ()
{
int k=1;
for(int i=0;i<N;i++)
k=k&amp;&amp;(Kao<=0.0);
return k;
}
/*
算法失败，退出
*/
int fall()
{
int k=1;
for(int i=0;i<N;i++)
k=k&amp;&amp;(P<=0.0);
return k;
}

你再根据需要改吧。

测试结果：
Successful:
X[3]=77.142860 X[1]=7.142854 X[2]=28.571430
max Z=585.714294
Press any key to continue

是啊
所以我建议大家学一下 运筹学
可以响应的人太少
在一些学校 运筹学 是选修课
过些日子要考试了
可惜教的太少了

找本书看看自己写一个多好,自己的东西用起来都舒服，
又不是很难

*******************************************************
* 计算结果 *
*******************************************************
最大值 = 585.71429
最优解 数值 状态 费用系数
--------------------------------------------------
X( 1)= 7.14286 基变量 10.00000
X( 2)= 28.57143 基变量 18.00000
X( 3)= 77.14286 基变量 .00000
X( 4)= .00000 非基变量 .00000
X( 5)= .00000 非基变量 .00000
其中 X( 3)-X( 5)是松驰(或剩余)变量
第一阶段迭代次数= 0
第二阶段迭代次数= 2

各位高手，问一个很弱的问题，就是单纯型中怎么保证解的顺序，即最后的结果是按照x的顺序给，因为经过进基，出基之后，顺序乱了。能否告知如何得到x的原来的顺序。我的方法是设置一个数组记录x的下标，每进基，出基后，将下标相应顺序变换，最后输出时只输出基变量的值。但是结果不对，所以看到这里的帖子后，希望能指教一下！多谢！