#include<iostream.h>2 F1 e- Q9 ~/ b! W. X" B9 J
#include<math.h>
float matrix[100][100],x[100];
int a[100];
int m,n,s,type;/ ^. f6 h/ W/ w* }/ K9 O3 }* o
int indexe,indexl,indexg;8 |" L+ n! f) ]* B- X, l
/////////////////////////////////& g# r+ H" \7 P$ C& P6 D( x4 h
void jckxj()//基础可行解
{! L p* m5 |7 b5 Z$ w+ {& M. T2 {
int i,j;
for(i=0;i<n;i++). [+ C6 v( @ x( E
for(j=0;j<s;j++)
if(matrix[j]==1&&a[j]==1)1 s$ A0 v$ F; u, y
{
x[j]=matrix;
j=s;
}& c! S' L3 B$ A8 b
for(i=0;i<s;i++)
if(a==0)x=0;
}
int rj()//基解矩阵; r- Y9 x4 i' ?
{2 Q& [3 t y! h6 X- _: G
int i;1 Y5 t6 }+ J8 i$ [
for(i=0;i<s;i++): Y* ^" _) ]8 w
if(fabs(matrix[n])>=0.000001)' W/ l# O+ S/ B# n+ ?+ G, A, B
if(matrix[n]<0)return 0;1 A- [" x% Y; h: B4 |
return 1;/ _4 d: h- a9 d4 T2 |+ K3 ?
}
int Min()//求最小的1 R. ?8 n& U8 W# m
{% o5 L* I! m0 J' J4 U
int i,temp=0;/ L& W. T1 e; O/ N% U4 o& R0 R
float min=matrix[n][0];5 S* H! x3 W+ a: g
for(i=1;i<s;i++)! x. a" q0 p( P% n2 \0 ~: ?
if(min>matrix[n]) l( W+ Y- J+ I% P3 y2 t
{
min=matrix[n];4 w- {9 ~( H9 p" `7 S! a0 k7 y& H
temp=i;
}
return temp;
}
/////////////////////////////////
void JustArtificial()//人工变量) z9 u8 b7 H9 G
{
int i;/ @7 y0 `, G$ u; _" o- T
for(i=m+indexe+indexl;i<s;i++)" |- \' n( `) X( S5 J; Z R2 c3 G9 ~5 R
if(fabs(x)>=0.000001)# h0 N7 ^* n' r4 K3 j
{' {! k0 L( |, p2 R/ i
cout<<"NO Answer\n";% @; @% b# P. h$ i
return;
}2 L. p' h9 M; A- i! v2 ]
}
/////////////////////
int Check(int in)//检验) b: ?6 J5 u% D! H- j$ O& }
{
int i;
float maxl=-1;
for(i=0;i<n;i++)0 W1 m6 ], c1 T! J9 ], f
if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])$ h( _" e5 X; `
maxl=matrix/matrix[in];
if(maxl<0)
return 1;' j1 L3 ^- Y" f! E* K6 A" ^
return 0;- t' w" b7 T5 P- S) b9 u
}! t' H3 T. }0 @9 v
int SearchOut(int *temp,int in)//出基变量4 @. t7 s( _! E6 k9 L7 C
{5 s- \% q! ^+ O Z& L% s! g$ S
int i;
float min=10000;6 D% N+ ?) W; Q
for(i=0;i<n;i++)
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)
&&min>matrix/matrix[in])/ }- t* b) P8 ~2 U" a
{( k z* ]$ w/ P4 w8 V: P2 C ]; ~ M
min=matrix/matrix[in];
*temp=i;
}
for(i=0;i<s;i++)3 I; Z& z" \5 k
if(a=1&&matrix[*temp]==1)9 R5 \% D5 Z1 ]; g+ B" A7 n
return i;
}
/////////////////////////////////. L3 x* }( c& g% i) [5 i
void Mto(int in,int temp)
{9 w% V+ U, t) _/ ?" [; j
int i;+ F' Y+ M0 ~ n
for(i=0;i<=s;i++)3 I- ^; T' w6 r' [4 a4 \
if(i!=in)5 \2 T2 \8 ?8 ~. V# V2 o
matrix[temp]=matrix[temp]/matrix[temp][in];
matrix[temp][in]=1;
}, `8 H' V3 i L5 l
/////////////////////////////# G r, [- L7 h8 I( J
void Be(int temp,int in)//初等变换 _! {) z- J6 E& d* J5 M
{9 o. Y( ]. l( D( ]
int i,j;
float c;
for(i=0;i<=n;i++)
{1 E9 S Y- r1 q+ c; M
c=matrix[in]/matrix[temp][in];% l1 M# X; g& h2 J* z+ A, h f. R4 v
if(i!=temp)
for(j=0;j<=s;j++)/ |1 ~% N( Y. P% i- Z
matrix[j]=matrix[j]-matrix[temp][j]*c;
}1 D2 a) K, D2 X! z. K. f# i4 ~2 _
}8 ]% p4 L `! e( C6 G
//////////////////////////
void Achange(int in,int out)//出基入基转换# s) r+ Z x' h) x$ }- k3 E V
{& Z. k ?& R$ t! Y' o( h# G3 T
int temp=a[in];5 y; k' I8 }2 v& H4 m
a[in]=a[out];! Q; N+ C( b9 S/ d7 W" X1 d3 D
a[out]=temp;
}2 G9 F7 q! y6 h
////////////////////////
void Print()
{ t/ X8 k' X3 M% p4 i
int i,j,k,temp=0;+ {* ~( v" f. H" q% n, q
for(i=0;i<n;i++)
{
for(k=temp;k<s;k++)" I8 B0 w8 s" u% Q# \; |
if(a[k]==1)
{- e/ d8 G* Y( O* s
cout<<k;% F( ^* ~, \" b3 D2 I
temp=k+1;
k=s;
}
for(j=0;j<=s;j++)
cout<<matrix[j];
cout<<"\n";
}4 A& M0 X* s5 Z% V7 g% m
cout<<"Rj";
for(j=0;j<=s;j++)* J( i; X) \+ ?- U
cout<<matrix[n][j];
cout<<"\n";- s8 ?0 |5 T! K
}
////////////////////////! ~; ?: G3 q% Q; i" U
void InitPrint()
{ E& _4 @& V2 ^( [# b! Q7 K
int i;
cout<<"X";
for(i=0;i<s;i++)! Z$ _5 K5 I. z2 F' U
cout<<i;5 Y, q! K- ]! x3 h/ D
cout<<"b\n";: e8 `9 e% [: G3 \
cout<<" ";! ^5 E* x: G& g* o% h8 n
cout<<"\n";2 V5 w. r: H, h9 @8 z
}8 t0 z6 [: p0 q# y7 N
//////////////////$ X- a- B4 v, k! m# g( l
void Result()) X7 g/ M% p- [6 x4 j
{
int i;. W7 V1 `! X: H \; Z5 J0 s* Q! L
cout<<"(";; O1 w9 c7 S( y; y' _
for(i=0;i<s;i++)2 `2 W+ F0 g M) J' q9 S$ O
cout<<x;/ L$ o! N8 O, S: w
cout<<")";
if(type==1)
cout<<"Zmax="<<matrix[n];9 w: M/ Z# [1 Q9 ?) ?
else cout<<"Zmin="<<matrix[n];9 V2 m" i7 G. L7 _
}
//////////////////////
void PrintResult()3 v! z$ P: ~' S1 O, w4 c
{
if(type==0)2 G3 c$ D: A$ H1 ]. M
cout<<"the Minimal:"<<matrix[n];
else cout<<"theMaximum:"<<matrix[n];+ H9 }4 F9 g7 B9 k6 L
}
////////////////////////////////% p6 R3 s( j) J7 j1 V1 v7 d+ e/ y
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并, D5 Q( O1 \; E0 `7 V
{" L& a; ~ v4 y% v
int i,j;
for(i=0;i<n;i++)& y$ F7 w: _* w; ~
{" z) r6 G& Y, {' C/ L
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;6 Y& k3 a2 S$ L
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++)
matrix[n]=0;
for(i=m+indexe+indexl;i<s;i++), h5 T" m+ ~* y
matrix[n]=100;
matrix[n]=0;# Z* ]5 R0 S6 \ n
}
/////////////////////////// void ProcessA()//初始a[] { int i;3 H5 X5 u. }# C3 G' C/ g' n- | for(i=0;i<m+indexe;i++) a=0;9 o8 D+ d% J6 d' z for(i=m+indexe;i<s;i++)8 L+ z. C: j9 U a=1; }
: T' u! p4 H. C6 v- @# y3 p//////////////////////////////// void Input(float b[],int code[]) { int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; cin>>m>>n;' B( U5 O" D* t for(i=0;i<n;i++)5 H9 l7 u0 {, v+ ? { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; cout<<"The 系数 \n"; for(i=0;j<m;j++) cin>>matrix[j];0 Z# C) h( C* c! R7 Z6 P) }( ? } cout<<"the type 0:Min 1:max\n";5 | V5 V2 E9 w6 W do{: u# a8 l: a. Y& i6 a cin>>type; if(type!=0&&type!=1) cout<<"error,ReInput!\n";$ } @4 I, c/ f `6 G }while(type!=0&&type!=1); cout<<"the Z\n";( Z7 p' [6 V8 N* J, C; ? for(i=0;i<m;i++)% `% L# P+ l9 Q cin>>matrix[n]; if(type==1) for(i=0;i<m;i++)/ R( I" K# b" E& P matrix[n]=-matrix[n]; }
, y: |: f! e& r3 G: t ////////////////// void Xartificial()//消去人工变量 { int i,j,k; if(indexg!=0) {5 W2 U5 ]2 V, k for(i=m+indexe+indexl;i<s;i++) { for(j=0;j<n;j++)' F: o* [0 i+ N4 [1 M0 @! ] if(matrix[j]==1) {+ F4 b3 t1 `/ T9 L# b( H: d9 v for(k=0;k<=s;k++)% `. Y6 C0 v% n matrix[n][k]=matrix[n][k]-matrix[j][k]*100;- S, ?+ t% I' q" }/ k j=n; } }1 H+ K0 m: }; u1 ]# y8 x W) t4 ^ } }
////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)" Q H/ x4 t8 K
{1 l8 v F! t) y. ~
int i;# m& d( S% \# A* w
for(i=0;i<n;i++); d) ]' w9 R* h3 W8 D2 k; }
if(i!=row)c[vol]=0;
}- ]& O1 i* _3 z) h! }. Z
//////////////////////
void Start(float b[],int code[])* H! S! S+ L+ f9 V% w3 F
{
int i;
float nget[100][100],nlet[100][100],net[100][100];; J0 ~0 W; }+ r# l
indexe=indexl=indexg=0;
for(i=0;i<n;i++)
{* H2 R( o! u$ o0 C. {
if(code==0){nlet[indexl++]=1
rocess(nlet,i,indexl-1);}8 A9 j _$ `6 ?9 L) X8 y9 ~
if(code==1){net[indexl++]=1
rocess(net,i,indexg-1);}
if(code==2){1 y3 N u7 y9 e. I% V+ J$ ?7 Z
net[indexg++]=1;
nget[indexe++]=-1;, q: }3 ]7 C2 t8 W) |+ ~0 I" N7 u
Process(net,i,indexg-1)
rocess(nlet,i,indexe-1);) H) W; U0 ^3 s6 `4 K
}
}
s=indexe+indexl+indexg+m;2 k7 J6 l; ^: Q" Q1 }- ?6 T
Merge(nget,nlet,net,b);
ProcessA();
InitPrint();
Xartificial();
}
void Simplix()//单纯形法$ }8 {' u3 L/ K) ]0 u {2 d4 e) f8 b* ~8 X int in,out,temp=0; while(1) {- q) R* x: F9 r; N/ q. g jckxj();2 a) I4 Z0 |% b Print();: ]6 k/ ` H* i; e6 q* c4 r Result();7 O$ h& Y3 q0 e& _ if(!rj()) in=Min();% g2 K( o& q4 I2 B6 `8 M else{4 r9 ~: H3 V; o, v" H% m if(indexg!=0)9 p; p. S' a& g! u- v w& V: e0 e* `! Y JustArtificial(); PrintResult(); return;7 P5 r% M4 J! O } if(Check(in)) {' T7 i- K# d! I' j cout<<"No Delimition\n";: P# M5 M2 c V0 \0 A) F return; } out=SearchOut(&temp,in); Mto(in,temp);, {$ t) N& s- g+ H$ n! n Be(temp,in); Achange(in,out); } }
0 T9 G% u @- W, t+ n4 F: V& yvoid main()+ q3 ^" ] w, i2 c. K { int code[100];//输入符号标记; q7 S. W& _, w! K# @ float b[100];" o: Q; i- q5 R' E, F0 W& u$ R6 F Input(b,code);//初始化0 Y4 q# g$ r2 }/ G1 e6 Z Start(b,code);//标准化行 Simplix();& M& U# x- o, A$ g9 ^8 ~ }
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 |