#include<iostream.h>
#include<math.h>
float matrix[100][100],x[100];# s7 F% ~) e: E9 U7 L n
int a[100];. l4 ]$ X0 k( ]& |, h1 a
int m,n,s,type;) \7 o, b2 G$ ^
int indexe,indexl,indexg;: _: Z" A) \' F" `
/////////////////////////////////
void jckxj()//基础可行解
{+ x. Q3 _2 n4 `- x
int i,j; D M9 E% T2 ~$ d
for(i=0;i<n;i++)
for(j=0;j<s;j++)
if(matrix[j]==1&&a[j]==1)
{
x[j]=matrix;6 K" ^ d, E# h' D2 `$ _
j=s;5 m# D' [% H: ^9 I/ x
}- `7 U* p! b2 M. |
for(i=0;i<s;i++)
if(a==0)x=0;
}
int rj()//基解矩阵3 F. Q! N: ^. }. S+ E' d
{3 n# Z) F7 J) [
int i;
for(i=0;i<s;i++)' M) {4 j2 R/ o$ W4 ?; R, y
if(fabs(matrix[n])>=0.000001)
if(matrix[n]<0)return 0;
return 1;
}
int Min()//求最小的
{, G2 ~0 v/ ~7 g/ L1 V- y8 C
int i,temp=0;0 F1 y+ X5 f# N8 W2 Z
float min=matrix[n][0];
for(i=1;i<s;i++), J3 T6 Q* l. w5 }( N+ x
if(min>matrix[n])
{4 [& B% f$ b4 ?1 {
min=matrix[n];# s' x* W' O8 _ Z& E+ I8 a
temp=i;
}
return temp;& K6 W" Q4 G7 y9 e0 B2 b+ |, Z
}
/////////////////////////////////
void JustArtificial()//人工变量, l9 Q6 P! {4 B! P! b4 f, p, @
{% o4 ]# W# j5 A" t, f* k/ x: b
int i;
for(i=m+indexe+indexl;i<s;i++)
if(fabs(x)>=0.000001)
{
cout<<"NO Answer\n";! r: r* W0 V& q9 }
return;
}
}
/////////////////////) g! ` {& d) k( F: x
int Check(int in)//检验
{
int i;! I1 y1 V" E2 u# }
float maxl=-1;
for(i=0;i<n;i++)
if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])( d& M! q+ Q- h' e( T; m7 d! O
maxl=matrix/matrix[in];
if(maxl<0)5 t( B: U. {/ v6 c% I$ _, O& y
return 1;
return 0;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;1 \: Y5 {+ z' J- }* e! t7 }/ O1 k
for(i=0;i<n;i++)' r5 v6 q; ]% }2 P: S
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)% x0 [' J+ i+ t) a x! }
&&min>matrix/matrix[in])
{
min=matrix/matrix[in];7 j+ ]/ a' S1 O' {# f0 g/ [% q
*temp=i;5 D) ^$ d, b4 b/ ?( J& Q
}
for(i=0;i<s;i++)
if(a=1&&matrix[*temp]==1)! D5 ?3 k9 o4 s6 T
return i;
}" i) [8 |' n& b+ ~$ J* ?- i6 E
/////////////////////////////////
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)* p3 i* c( H+ |% S- ^3 a
if(i!=in)1 m, Q4 m7 h6 F+ L
matrix[temp]=matrix[temp]/matrix[temp][in];7 ]4 u/ D, ~1 ~+ V' F* M1 W
matrix[temp][in]=1;9 s0 c0 D/ x0 O6 w; I( R L
}
/////////////////////////////1 I7 o% `+ v; \
void Be(int temp,int in)//初等变换
{5 s/ O s6 n$ B @; ^: Q
int i,j;
float c; e; Z% x6 \7 E0 W" t
for(i=0;i<=n;i++)
{
c=matrix[in]/matrix[temp][in];
if(i!=temp)) ]" m; F S4 z
for(j=0;j<=s;j++)
matrix[j]=matrix[j]-matrix[temp][j]*c;
}
}
//////////////////////////
void Achange(int in,int out)//出基入基转换: o6 k+ D! A5 d- X
{$ |/ i0 b4 t# I; r7 d" x) k/ a: q
int temp=a[in]; `* R' f5 _$ u
a[in]=a[out];5 C/ Y3 Y( ]) P- t+ D l
a[out]=temp;4 `% \6 r. Y& u* w
}. ]. K. c" Q) r) N5 T
////////////////////////: C% t f6 p9 Q) m6 i- r$ o
void Print()6 y' H1 g/ V& n5 _, n1 Z
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
for(k=temp;k<s;k++)8 q# j2 S2 e. ?
if(a[k]==1)
{( E/ M0 L5 \5 A7 l4 Z
cout<<k; D- d2 _& J: T- G. d' G$ n
temp=k+1;
k=s;
}% t2 | p5 X0 f/ v
for(j=0;j<=s;j++)5 i+ T- J7 O1 ^0 g- V9 L1 U2 y4 r
cout<<matrix[j];
cout<<"\n";
}
cout<<"Rj";
for(j=0;j<=s;j++)! E- s& G/ R3 o: Q/ r1 ^; @1 j* U
cout<<matrix[n][j];
cout<<"\n";1 g( K# ~/ _) E+ U2 t
}) ?1 y x# ]% w0 ^2 R$ L
////////////////////////0 q+ k3 v6 n" o+ e8 R) i6 t5 Y7 `
void InitPrint()
{# i2 k4 k/ r: z6 K
int i;5 e4 I8 P& I/ B! T# Q$ @
cout<<"X";
for(i=0;i<s;i++)
cout<<i;
cout<<"b\n";
cout<<" ";
cout<<"\n";
}
//////////////////% a: s, k6 w3 L4 u. U5 D
void Result()
{
int i;
cout<<"(";# @& s: D! v( m3 `
for(i=0;i<s;i++) w; Y7 ?9 y$ ?
cout<<x;+ p+ |* X, }( N7 U! Y! q" `
cout<<")";, @6 f; \" u9 A2 T$ S( |: r
if(type==1)
cout<<"Zmax="<<matrix[n];- w7 m, @( ~5 c
else cout<<"Zmin="<<matrix[n];
}
//////////////////////# v( r+ F# @( F* d
void PrintResult()4 Z( n! F( Q; I7 B
{9 [' B4 i* [) j( C* {
if(type==0)
cout<<"the Minimal:"<<matrix[n];
else cout<<"theMaximum:"<<matrix[n];) Q h4 ]4 x( p
}8 R( ~; p4 w" W2 l9 j" t" m, Q! r
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并2 g: [0 q+ J2 X, ^* i# g4 J4 ]3 V& c
{
int i,j;
for(i=0;i<n;i++)
{- o5 b! B' Z1 V( b7 P
for(j=m;j<m+indexe;j++): }4 V G8 C" A9 W
if(nget[j-m]!=-1)matrix[j]=0;
else matrix[j]=-1;! X4 E, J* B% p/ m; g7 i& X
for(j=m+indexe;j<m+indexe+indexl;j++)
if(nlet[j-m-indexe]!=1)matrix[j]=0;
else matrix[j]=1;6 d5 C V5 a, m# w' b
for(j=m+indexe+indexl;j<s;j++)
if(net[j-m-indexe-indexl]!=1)matrix[j]=0;9 J+ J8 ^% |! d: a1 T0 X; d
else matrix[j]=1;8 R' b) i) C5 t& K4 d
}
for(i=m;i<m+indexe+indexl;i++)1 h: u2 O6 \; V$ l# O, M( W# [1 t
matrix[n]=0;, r- U" Y) w& s# C; g# z6 e7 H
for(i=m+indexe+indexl;i<s;i++)
matrix[n]=100;4 J# t' C+ ~+ G9 }1 }5 ?8 @
matrix[n]=0;' Z$ C1 I0 S0 V+ |/ X2 K; q
}
/////////////////////////// void ProcessA()//初始a[] { int i; A# {$ Y7 s9 q: V. G for(i=0;i<m+indexe;i++) a=0;# v% A" |7 f* f) j( f$ Q for(i=m+indexe;i<s;i++); [, ]" L/ l. K3 X( R. ?3 B a=1; }
//////////////////////////////// void Input(float b[],int code[]) { int i=0;int j=0;" G" k5 Q8 F. i1 n- h cout<<"The equator variable and Restrictor\n";$ U, ]. j3 Z Z2 O cin>>m>>n;& h0 Z/ _7 K( F for(i=0;i<n;i++): D1 t3 f0 u1 |: ]) ^ { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";8 C, u9 x0 [7 L cin>>b>>code;4 e- J: m. Y; {: ?& n: X cout<<"The 系数 \n";4 {7 U+ p8 y5 Z( `. w! m& a for(i=0;j<m;j++)6 u" W% X" n' }9 r: O4 N0 @* { cin>>matrix[j];' J# m, L, o y& D }1 z& D( |( |, h; O# f4 d cout<<"the type 0:Min 1:max\n";' {! L7 \1 X% S0 ]3 ]! r: q do{ cin>>type; if(type!=0&&type!=1)3 B4 O5 A/ R7 n6 K cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n";6 G5 x7 k. V$ ]( L7 l for(i=0;i<m;i++)1 p; y4 P- y; B% B cin>>matrix[n]; if(type==1) for(i=0;i<m;i++)/ q- @! V* s6 O+ J matrix[n]=-matrix[n]; }
////////////////// void Xartificial()//消去人工变量: d, W, S3 P/ Z2 T. s+ y4 L {2 Q. U( B: L' ^& L5 k int i,j,k;" A- n6 V* \6 x if(indexg!=0) {$ y/ n6 m) _6 S for(i=m+indexe+indexl;i<s;i++) { for(j=0;j<n;j++) if(matrix[j]==1) { for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; }$ M6 b! B( |4 I* V } }5 |7 w. @! X4 O5 |9 M. B }
5 _ H" d3 x- F- @" H////////////////////////////////////////////////8 L d( F7 P$ @$ W) U$ C) L S1 {
void Process(float c[][100],int row,int vol)6 o2 w$ _" C$ b5 g* z
{2 ]8 B0 V: n# W5 c3 I
int i;5 G5 V0 H# Y5 D* \' n; G/ Y
for(i=0;i<n;i++)
if(i!=row)c[vol]=0;
}
//////////////////////
void Start(float b[],int code[])* m: Q% r; V1 V9 I6 |
{
int i;; {6 n- D8 x0 B7 s; S/ m9 X: R
float nget[100][100],nlet[100][100],net[100][100];' u O {& d+ k7 V1 X
indexe=indexl=indexg=0;( N+ v, c+ m- O3 `/ L
for(i=0;i<n;i++)
{
if(code==0){nlet[indexl++]=1
rocess(nlet,i,indexl-1);}8 B- d4 {, W! ?
if(code==1){net[indexl++]=1
rocess(net,i,indexg-1);}
if(code==2){5 H5 ?" @! Y) y
net[indexg++]=1;: H, P/ [7 E% U: P" t; `6 U7 \
nget[indexe++]=-1;
Process(net,i,indexg-1)
rocess(nlet,i,indexe-1);
}
}3 c$ ~- E* O" _3 n
s=indexe+indexl+indexg+m;
Merge(nget,nlet,net,b);$ Q) H; D5 y, S# B$ @
ProcessA();
InitPrint();; |0 U3 g0 r3 x& O7 U7 h
Xartificial();+ D8 }1 D' L' Z- o* R
}
void Simplix()//单纯形法 {2 n0 c" v) m4 I2 e' p" \' O f int in,out,temp=0;, g* V" U& `1 \) F4 u while(1) {* V+ c* K& G, p jckxj();, X- v1 t+ z2 y0 A Print(); Result(); if(!rj()) in=Min();8 D ~9 ^5 w5 `9 y else{" ]% t2 W. H: ?3 A- ~ if(indexg!=0) JustArtificial(); PrintResult();" a d8 E' }, x+ q return;% V0 O; i% ~; x8 n- L/ S } if(Check(in)) { cout<<"No Delimition\n"; return;$ M: J: z4 K* L5 t$ e+ ] }% e. |& \0 _ _" d! a out=SearchOut(&temp,in); Mto(in,temp);% e# v, n$ i) H7 j; }( }- N Be(temp,in); Achange(in,out); }( J/ I2 C+ j1 `! w3 p }
3 Q6 m" Y' |! u9 v0 l5 avoid main() { int code[100];//输入符号标记# m+ L9 a7 ]9 O% a float b[100];3 t7 L7 t$ }% Z! j" u Input(b,code);//初始化 Start(b,code);//标准化行* i; V" L+ G# j+ x8 R Simplix();0 {! _# x3 w$ S/ B" K& J1 g P1 u }! P1 n/ b2 ?) Q8 O+ B: s7 q, S
so well!
还有其他算法吗关于仿生算法的谢谢
有C語言的嗎?我要C語言的
谢谢,我正在找这个程序,终于找到了!
楼上的的确是位高手,这两天由于写论文要用到单纯形法的程序,就拿来用了,但是发现有些错误,没有结果或者得出的答案有问题,于是我仔细看了一下这个程序,将楼上的笔误,和一些其他的小错误改正如下,
注意: 我不是用纯 VC++ 我的输出函数用的是 printf (),这样可以动态观察结果输出,以便于修改,这个程序是我花了一天的时间改的,太长也太烦琐,我看的也不是很清楚,只对 限制条件是 <= 的情况进行了详细的察看,和修改,其他的情况就没有看了,程序中相应的部分有比较详细的注解,如果有需要可以和我联系,我们一起共同探讨。谢谢!QQ:116490942
#include<stdio.h>
#include<iostream.h>
#include<math.h>
float matrix[100][100],x[100];
int a[100];
int m,n,s,type;
int indexe,indexl,indexg;
/////////////////////////////////
void jckxj()//基础可行解
{
int i,j; //基础可行解即为 非基变量对应的x=b, 基变量对应的解为0
for(i=0;i<n;i++)
for(j=0;j<s;j++)
if(matrix[j]==1&&a[j]==1)
{
x[j]=matrix;
j=s;
}
for(i=0;i<s;i++)
if(a==0)x=0;
}
int rj()//基解矩阵
{
int i;
for(i=0;i<s;i++)
if(fabs(matrix[n])>=0.000001)
if(matrix[n]<0)return 0;
return 1;
}
int Min()//求最小的
{
int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++)
if(min>matrix[n])
{
min=matrix[n];
temp=i;
}
return temp;
}
/////////////////////////////////
void JustArtificial()//人工变量
{
int i;
for(i=m+indexe+indexl;i<s;i++)
if(fabs(x)>=0.000001)
{
cout<<"NO Answer\n";
return;
}
}
/////////////////////
int Check(int in)//检验
{
int i;
float maxl=-1;
for(i=0;i<n;i++)
if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])
maxl=matrix/matrix[in];
if(maxl<0)
return 1;
return 0;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;
for(i=0;i<n;i++)
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)
&&min>matrix/matrix[in])
{
min=matrix/matrix[in];
*temp=i;
}
for(i=0;i<s;i++)
if(a=1&&matrix[*temp]==1)
return i;
}
/////////////////////////////////
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
if(i!=in)
matrix[temp]=matrix[temp]/matrix[temp][in];
matrix[temp][in]=1;
}
/////////////////////////////
void Be(int temp,int in)//初等变换
{
int i,j;
float c;
for(i=0;i<=n;i++)
{
c=matrix[in]/matrix[temp][in];
if(i!=temp)
for(j=0;j<=s;j++)
matrix[j]=matrix[j]-matrix[temp][j]*c;
}
}
//////////////////////////
void Achange(int in,int out)//出基入基转换
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
////////////////////////
void Print()
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
for(k=temp;k<s;k++)
if(a[k]==1)
{
printf(" %d ",k);
temp=k+1;
k=s;
}
for(j=0;j<=s;j++)
printf( " %.0f ",matrix[j] );
printf("\n");
}
printf("Rj\n");
for(j=0;j<=s;j++)
printf(" %.0f ",matrix[n][j] );
printf("\n");
}
////////////////////////
void InitPrint()
{
int i;
printf(" X ");
for(i=0;i<s;i++)
printf(" %d ",i);
printf(" b \n" );
printf(" " );
printf("\n" );
}
//////////////////
void Result()
{
int i;
printf( "(" );
for(i=0;i<s;i++)
printf( "%.0f",x );
printf( ")" );
if(type==1)
printf("\nZmax= %.0f\n" ,matrix[n] );
else printf("\nZmin=%.0f\n", matrix[n] );
}
//////////////////////
void PrintResult()
{
if(type==0)
printf("the Minimal: %.2f\n", matrix[n] );
else
printf("the Maximum: %.2f\n", matrix[n] );
}
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
{
//置成我们需要的矩阵,最后一列置成0
// 1 2 1 0 0 0
// 4 0 0 1 0 0
// 0 4 0 0 1 0
//-2 -3 0 0 0 0
int i,j;
for(i=0;i<n;i++)
{
for(j=m;j<m+indexe;j++)
if(nget[j-m]!=-1)matrix[j]=0;
else matrix[j]=-1;
for(j=m+indexe;j<m+indexe+indexl;j++)
if(nlet[j-m-indexe]!=1)matrix[j]=0;
else matrix[j]=1;
for(j=m+indexe+indexl;j<s;j++)
if(net[j-m-indexe-indexl]!=1)matrix[j]=0;
else matrix[j]=1;
}
for(i=m;i<m+indexe+indexl;i++) //将目标函数中人工变量的系数补为0
matrix[n]=0;
for(i=m+indexe+indexl;i<s;i++)
matrix[n]=100; //置成M
for(i=0;i<n;i++) //把b[]的值赋给matrix
matrix=b;
matrix[n]=0;
}
///////////////////////////
void ProcessA()//初始a[] a[]是标记基变量,若为基变量则为0,若为非基变量则为1
{
int i;
for(i=0;i<m+indexe;i++)
a=0;
for(i=m+indexe;i<s;i++)
a=1;
}
////////////////////////////////
void Input(float b[],int code[])
{
int i=0;int j=0;
cout<<"The equator variable and Restrictor\n";
cin>>m>>n;
for(i=0;i<n;i++)
{
cout<<"Inputb[] and Restrictor code 0:<= 1:= 2:>=\n";//输入b[]和限制符号 <= ,= ,>=
cin>>b>>code; //分别输入到b 和 code 中
cout<<"The 系数 \n"; //提示输入每个限制条件的系数
for(j=0;j<m;j++)
cin>>matrix[j];
}
cout<<"the type 0:Min 1:max\n";//输入要求是类型极大还是极小 0:Min 1:max
do{
cin>>type;
if(type!=0&&type!=1)
cout<<"error,ReInput!\n";
}while(type!=0&&type!=1);
cout<<"the Z\n";
for(i=0;i<m;i++)
cin>>matrix[n];
if(type==1) //如果是求极大,把它转化为极小来做,系数全部反号
for(i=0;i<m;i++)
matrix[n]=-matrix[n];
}
//////////////////
void Xartificial()//消去人工变量
{
int i,j,k;
if(indexg!=0)
{
for(i=m+indexe+indexl;i<s;i++)
{
for(j=0;j<n;j++)
if(matrix[j]==1)
{
for(k=0;k<=s;k++)
matrix[n][k]=matrix[n][k]-matrix[j][k]*100;
j=n;
}
}
}
}
////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)
{
int i;
for(i=0;i<n;i++) //i =0 时置第一列为 1 0 0 i=1 时置第2列为 0 1 0
if(i!=row)c[vol]=0;
}
//////////////////////
void Start(float b[],int code[])
{
int i;
float nget[100][100],nlet[100][100],net[100][100];
indexe=indexl=indexg=0; //indexl 表示松弛变量数 indexg 表示人工变量数, indexe表示减去的松弛变量数
for(i=0;i<n;i++)
{
if(code==0) //如果是<=
{
nlet[indexl++]=1; //松弛变量数+1 且置成相应的标记
 
rocess(nlet,i,indexl-1);//传 net, 行号,indexl-1 过去
}
if(code==1)
{
net[indexg++]=1; //人工变量数+1且置成相应的标记
 
rocess(net,i,indexg-1); //将刚加入的列单位化
}
if(code==2)
{
net[indexg++]=1; //人工变量数+1 且置成相应的标记
nget[indexe++]=-1; //剩余变量数+1 且置成相应的标记
Process(net,i,indexg-1)
rocess(nlet,i,indexe-1);
}
}
s=indexe+indexl+indexg+m; //变量总个数
Merge(nget,nlet,net,b);
 
rocessA();
InitPrint();
Xartificial();
}
void Simplix()//单纯形法
{
int in,out,temp=0;
while(1)
{
jckxj();
 
rint();
Result();
if(!rj()) in=Min();
else
{
if(indexg!=0)
JustArtificial();
 
rintResult();
return;
}
if(Check(in))
{
cout<<"No Delimition\n";
return;
}
out=SearchOut(&temp,in);
Mto(in,temp);
Be(temp,in);
Achange(in,out);
}
}
void main()
{
int code[100];//输入符号标记
float b[100];
Input(b,code);//初始化
Start(b,code);//标准化行
Simplix();
}
/*模拟输入数据
max z=2 x1 + 3 x2
s.t {
x1 + 2 x2 <=8
4 x1 <=16
4 x2<=12
x1,x2>=0
}
2 3 8 0 1 2 16 0 4 0 12 0 0 4
*/
好
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |