#include<iostream.h>' Y) i c' H1 {7 B0 m4 }% W3 |6 t
#include<math.h>
float matrix[100][100],x[100];
int a[100];4 l5 b0 j' P" I7 I* t' Y( x
int m,n,s,type;6 T; T; [3 h4 e1 [
int indexe,indexl,indexg;3 N$ d4 ^% |: f" S5 f- g! }9 e
/////////////////////////////////
void jckxj()//基础可行解
{
int i,j;/ m: B9 q1 @/ Z5 i2 N8 Z
for(i=0;i<n;i++)
for(j=0;j<s;j++)
if(matrix[j]==1&&a[j]==1), E! v6 T% a+ T4 P' C/ r; g1 d
{
x[j]=matrix;% o7 J; g# X) e; G
j=s;
}4 a; t% o3 `' Y6 N; H' k
for(i=0;i<s;i++)
if(a==0)x=0;" {. s' B; `" c8 r
}
int rj()//基解矩阵0 o! e7 Y7 C: ]2 ]% l+ I# \
{, Y: O. m4 l$ A v" Z- i
int i;4 Z9 C# T/ `! x% R
for(i=0;i<s;i++)
if(fabs(matrix[n])>=0.000001)& ~1 \& X; m) J2 I) a
if(matrix[n]<0)return 0;3 p1 h4 M4 ?9 @2 j5 F! o3 _- F
return 1;
}
int Min()//求最小的
{( U- a7 T' b9 O- @
int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++). N2 b" v3 N3 ]; p( V1 z8 g
if(min>matrix[n])
{, l$ U- N. [. M( i/ y
min=matrix[n];# m) y! @" H+ b6 M+ O1 F/ d# i) _0 h
temp=i;
}' e" f! k- x8 ] S- j/ s
return temp;. G; e9 S: X# P" z8 Z: c' N
}& W# m, n! `# N& B
/////////////////////////////////3 _8 J3 q1 _3 u/ o0 {6 |' J/ \( `
void JustArtificial()//人工变量$ L+ @! s7 W2 i- G6 Q9 z& N' P
{" \4 I8 @) a) ?; D4 {! f5 P
int i;, r* G T2 U. [: X6 o
for(i=m+indexe+indexl;i<s;i++)5 H. B* X( \) ~: t4 ~& x8 T( m+ o
if(fabs(x)>=0.000001)
{1 c! m+ P6 X& W. @! _3 H
cout<<"NO Answer\n";4 {3 A* b6 e1 r, O: @8 w
return;+ S* ?: R# d0 j5 d1 p* G
}" n% `1 t9 G. A9 }( T6 Z t
}
/////////////////////3 B! h' m e7 y. W# z. N
int Check(int in)//检验$ ^ X9 a# y' c" A$ K% l* A
{
int i;$ Q7 C" Z1 d; a. Y# {* r
float maxl=-1;$ a- R# B" H; ~3 B2 z6 K: J
for(i=0;i<n;i++)' x& S; B" v8 }/ R' Q
if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])/ Y; h' }) |+ g! u+ a7 {2 v1 |" S6 ^
maxl=matrix/matrix[in];! ?8 r* k& a2 f( @& y/ O0 p
if(maxl<0)6 r2 @6 ]3 k% ]" Y) Z, ?
return 1;8 q6 Z: G$ A8 V7 m3 [7 U
return 0;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;! b- c. v; w8 ?* ?9 Z+ J7 b2 q
for(i=0;i<n;i++)7 A% k% g9 D2 z
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)2 E# [5 b( ?: j
&&min>matrix/matrix[in])* ]$ x2 E5 M# w/ ]4 K, _2 j
{) ~& G6 X+ |$ z7 ^, g; @
min=matrix/matrix[in];
*temp=i;1 G9 |* _2 G2 A
}
for(i=0;i<s;i++)
if(a=1&&matrix[*temp]==1)2 k- R0 x/ @% n! D5 w- \1 }
return i;
}
/////////////////////////////////- J( v, W: C- X }
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++), Q% Y% l) v: Q" I, u- c! m
if(i!=in)6 c9 c$ ~, r0 [/ y' q# T
matrix[temp]=matrix[temp]/matrix[temp][in];7 d4 F% N- }% h4 n* j" W' S3 L
matrix[temp][in]=1;$ q' q8 S+ H0 |" q! h5 {$ D* M, T" N
}
/////////////////////////////
void Be(int temp,int in)//初等变换6 S5 t- x, B3 f" x ]
{
int i,j;" G/ _+ G, |: N S& C
float c;( Z5 ]5 R! w, E+ ^/ k
for(i=0;i<=n;i++)
{
c=matrix[in]/matrix[temp][in];4 Q; o3 z) \3 J" _9 Q5 g
if(i!=temp)
for(j=0;j<=s;j++)9 ?1 k; |- K1 C! ]9 y1 X9 ~
matrix[j]=matrix[j]-matrix[temp][j]*c;
}
}8 z% p- a8 ?$ q
//////////////////////////: }. k% b, E2 m1 |
void Achange(int in,int out)//出基入基转换4 T$ o. [' L2 K3 E- M9 s; \
{" |. D" O% h" `
int temp=a[in];
a[in]=a[out];# \6 d3 W) G1 I9 @4 ?. \! |
a[out]=temp;
}
////////////////////////6 _2 u! w# d- z9 |3 \8 x) v |
void Print()" V& M5 X) o2 n: k9 z6 v
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
for(k=temp;k<s;k++)9 b3 p0 Y8 K! e
if(a[k]==1)6 Y' \4 a0 C" _) b9 Q
{
cout<<k;* ]' J& ~' W& p5 R1 K5 e
temp=k+1;! [7 ]0 X/ f! E% r; S+ H2 U& ?
k=s;! A1 E( T# J# [& P
}
for(j=0;j<=s;j++)
cout<<matrix[j];2 l- N3 K0 j3 Q& H% l+ {8 P' e
cout<<"\n";; k3 c# y' ]1 \% C$ N2 O
}
cout<<"Rj";0 [( j5 W) _1 L" h" t
for(j=0;j<=s;j++)
cout<<matrix[n][j];, F2 `* p5 d3 O. N% A- x( m N+ \$ e
cout<<"\n";
}
////////////////////////" J* A( \. d. q. Z5 V2 s
void InitPrint()$ t4 Z5 _/ U& I/ M0 `+ \7 o% W
{ ?- O V: H: v! w! l8 V* ?
int i;& I. r4 }7 u: A, x- W2 i, T* H# K: |
cout<<"X";
for(i=0;i<s;i++)
cout<<i;
cout<<"b\n";$ u1 h, P [" S, D
cout<<" ";8 W u; S8 ~% [3 q
cout<<"\n";
}% o+ X. N% @- o7 V5 @* r# O
//////////////////
void Result() A; l' ?- i2 R
{, q; q3 F7 k6 {0 C
int i;
cout<<"(";; C+ [% p S/ q6 F7 E! R. H+ Z+ U
for(i=0;i<s;i++)8 R/ n/ _ Z( q! w4 X
cout<<x;
cout<<")";" y& C; _. `3 G/ R- F: ^
if(type==1)3 S! S5 Z% t- D- U! `5 ^
cout<<"Zmax="<<matrix[n];
else cout<<"Zmin="<<matrix[n];8 ^+ h Y4 }5 I. U
}
//////////////////////
void PrintResult()
{
if(type==0)
cout<<"the Minimal:"<<matrix[n];8 [( }3 c& z& P9 ~2 W5 G5 G- T
else cout<<"theMaximum:"<<matrix[n];
}
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并. }, K- m; z( [- ^. y: N
{
int i,j;
for(i=0;i<n;i++)
{ t2 x# Y8 J0 T
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;$ p# a5 N+ k Y1 X0 }2 X
else matrix[j]=1;0 A. B9 K) L9 k7 g
for(j=m+indexe+indexl;j<s;j++)2 [+ S% D- t5 Q3 T* d% g. G$ N5 K9 F
if(net[j-m-indexe-indexl]!=1)matrix[j]=0; ~; w! c; X3 |" r" I8 D! v& c1 \
else matrix[j]=1;" f8 _; _' _8 R7 C+ r2 n/ M
}
for(i=m;i<m+indexe+indexl;i++)
matrix[n]=0;& E9 ~# S( e- p
for(i=m+indexe+indexl;i<s;i++)
matrix[n]=100;
matrix[n]=0;' B# P6 g% n; h! k. K* z. A8 X
}
/////////////////////////// void ProcessA()//初始a[]& F1 I l" n1 A4 D* x* D { int i; for(i=0;i<m+indexe;i++) a=0; for(i=m+indexe;i<s;i++)4 M8 k" [7 y& `* h2 | a=1;1 J& P6 b9 l6 g9 B# E# w s: m$ U }
//////////////////////////////// void Input(float b[],int code[])1 X+ L5 I- S1 h& O {$ I! A3 j' r% R+ \$ k/ D2 | int i=0;int j=0;9 \: N" K5 Z H6 ]: E* R cout<<"The equator variable and Restrictor\n"; cin>>m>>n;' ~6 r8 R' d* O, U' U' ^( r for(i=0;i<n;i++)9 F! D; W. O. {4 a f { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";, P) d9 ^; a7 B6 a* R- l( G8 l* V cin>>b>>code;! Z5 {& p X1 M cout<<"The 系数 \n"; for(i=0;j<m;j++) cin>>matrix[j];6 S, g: I$ R0 P. h4 w7 O0 _* I } cout<<"the type 0:Min 1:max\n"; do{ cin>>type; if(type!=0&&type!=1); k! C+ }. m# m# X cout<<"error,ReInput!\n"; }while(type!=0&&type!=1);8 g( r) `4 R/ Z1 i, q l' S- Q9 B cout<<"the Z\n"; for(i=0;i<m;i++)1 m2 r& R; n6 A1 c, {) x" l cin>>matrix[n];: O* k4 ^- ]* X# d+ A9 s if(type==1) for(i=0;i<m;i++)& b) }) L$ H- l- n9 t: z matrix[n]=-matrix[n]; }
, {. l0 ^. H! { ////////////////// 2 l8 A) a. N. [" c6 k, F( O void Xartificial()//消去人工变量4 ^# ?- L1 n7 |$ G1 n) u, ? {3 J/ b; \3 R M9 ?4 r) t int i,j,k;7 q1 a- E, c" c6 v if(indexg!=0) {. g3 T+ s- Q8 o! h) w for(i=m+indexe+indexl;i<s;i++)! G3 m4 v2 i5 E: s2 { {' T' r' j. E3 G! } for(j=0;j<n;j++) if(matrix[j]==1) {$ @* I& F5 z- ]% J: q0 K for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100;7 O3 p; b6 y0 [ j=n; } }$ U# }# L% p- Z m3 ? } }
* m7 X% J1 m) r9 ~9 }( t////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)9 `+ T7 k# J$ s: q! m, K" J
{
int i;
for(i=0;i<n;i++)- Q2 D6 Y2 i; B4 Q, U1 n2 g$ M! d
if(i!=row)c[vol]=0;/ X1 ]7 W; d6 d4 \5 H
}
////////////////////// J" f$ a) C3 c8 S* `7 u3 c$ h
void Start(float b[],int code[])
{
int i;. n; d$ ~, B" C4 R; A
float nget[100][100],nlet[100][100],net[100][100];* z- U: d; W5 U' l2 M j
indexe=indexl=indexg=0;# A9 T1 n: ?! O; _! T4 R0 u
for(i=0;i<n;i++)- |% C) E2 p$ k; H# _2 B7 A; J$ e
{
if(code==0){nlet[indexl++]=1
rocess(nlet,i,indexl-1);}
if(code==1){net[indexl++]=1
rocess(net,i,indexg-1);}% @* X) ^1 r0 I0 d4 p# @" I
if(code==2){
net[indexg++]=1;- S+ ` g, a! m* m2 T
nget[indexe++]=-1;
Process(net,i,indexg-1)
rocess(nlet,i,indexe-1);
}* c1 q2 ?, V4 }! M, F
}3 F+ R; g; D/ w1 V8 ~ B
s=indexe+indexl+indexg+m;" O# c5 g$ b7 ?0 M' Y7 u& Y U$ Q
Merge(nget,nlet,net,b);$ j1 H8 b" E1 j! e
ProcessA();
InitPrint();
Xartificial();; {) u& g! P- [8 ^0 T* y4 V/ t
}
void Simplix()//单纯形法5 M. o5 u6 O4 H% | { int in,out,temp=0;: r# v6 I/ a: @3 Z% ?" j0 p while(1) {% D0 L# K' n/ J& z$ N jckxj(); Print();, P0 Y& F5 F3 G9 c( F Result(); if(!rj()) in=Min();# ]: B) X& v- y+ U' R# T else{ if(indexg!=0) d! W* t" }; Y8 O/ z JustArtificial();1 _9 C' M. Q7 t. {/ u6 H0 m0 K PrintResult(); return; } if(Check(in))1 P) L2 i$ r3 V2 ?: b6 V8 N {* p3 D* c! t+ W0 |2 ^. [' }8 e cout<<"No Delimition\n";% p& }8 E" x0 j1 Q5 y return; } out=SearchOut(&temp,in);& r1 F0 T a! A: w9 A4 ^ Mto(in,temp); Be(temp,in); Achange(in,out); }4 W+ m* ^0 X4 y2 f }
, J1 d5 j- |1 ?- }; M' X; N0 h ?void main() {, k* b/ ~- X \2 [7 Q+ M% [ int code[100];//输入符号标记. g9 \# a6 D( ?$ |# J6 G2 \ float b[100];7 S0 e4 z5 E7 v7 l5 z8 _" b Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); }6 P' n. X$ e) b7 i- l& H# U
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 |