单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

发表于 2005-4-18 21:45 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

单纯形法程序，在VC++6.0 下测试通过！

#include<iostream.h> 7 ~5 z8 S9 b1 H0 P' ~3 J#include<math.h> " l1 J. t ^ V# z' Ifloat matrix[100][100],x[100]; . b p! V8 O. p5 `int a[100];! T( {3 t9 q. L+ U- C int m,n,s,type; , Y/ t: J p: C4 ?: bint indexe,indexl,indexg;1 P- u7 W% P- f; i /////////////////////////////////8 Y' w% a9 W, C5 o0 t void jckxj()//基础可行解 & y% H ?- J( c9 D: u" B5 m( }{ # t9 x# Q/ M/ b9 d" s int i,j; ; W. o$ v ` |- ]6 o for(i=0;i<n;i++)& z# ^( u+ G' x" k4 K9 w for(j=0;j<s;j++) + c0 [5 N% ~$ l# `6 C if(matrix[j]==1&&a[j]==1)# p; |2 c [9 s- _# Z {7 V8 @/ k2 [0 d0 m7 }7 \6 ` x[j]=matrix~~; ; P% E* j- r; W& U j=s; 5 Q" l$ q8 {% N8 _# I! D! {/ ? } f& ~8 _1 S! ?1 b9 d" n& ~ for(i=0;i<s;i++)# o& v7 L, B5 h if(a==0)x=0;$ l: F4 w( _3 _$ y$ U1 l) a) d }~~

' k* M; f; d8 |- ^% T* \
int rj()//基解矩阵 9 U! n' m3 @! u+ y8 V{% ~ l& i+ v3 u$ f, O8 e$ [3 ^ int i;; O0 M7 U) f* H for(i=0;i<s;i++)% J+ D4 t/ J* p# o- ]6 @ Q, O if(fabs(matrix[n])>=0.000001). W& W- P6 `6 J' v* _- Q if(matrix[n]<0)return 0; / O# \- e4 F+ F8 ~ return 1; |4 I1 X# S0 U- @ }. D# h4 A( Q% Z* M, c int Min()//求最小的 + t9 |/ X1 }: w+ k{: {9 P: j3 c$ x* j& ?# } int i,temp=0;: t0 r% T5 K4 J float min=matrix[n][0]; 5 y* i8 j4 t8 r4 L# b for(i=1;i<s;i++)8 _( a8 f, u; F$ C( w if(min>matrix[n])- U! \' ~" z& K* t* y# r6 K# G/ V { 1 V3 @+ c3 L. T% d0 ^. s min=matrix[n];% ]0 S* O H9 b* ]$ S& X temp=i; : Q/ @% G% g1 M( `1 A, n3 P7 F) Y n- { }/ T1 R% L1 T1 m. h4 m. T return temp;! J. ], b+ N0 ?4 h% h# W2 Z" V6 o) G }& b. I6 z8 A1 f t' y" o P1 g /////////////////////////////////4 x9 E0 @7 t; h( i void JustArtificial()//人工变量; J. h9 o/ Z# z/ `: [ { 5 M: J* {9 `. h* c" o int i;% x" O5 e" v0 f) b for(i=m+indexe+indexl;i<s;i++)2 C* s. N+ n2 y/ s" m/ o, }0 [ if(fabs(x)>=0.000001) , M6 q* f* W' C6 f9 ?; k {& B Q4 o* x8 S1 B9 ]( v, v8 F cout<<"NO Answer\n"; 8 y' _9 f; S: n return; 2 M8 Z( S- ^( z3 @. Y2 Q } % p* $ P. Z* M) k9 m}5 }: d* }) \1 D/ J ///////////////////// + C- Y5 z6 w5 v2 F5 Q: z/ c# yint Check(int in)//检验! ^( m0 S! ?1 B" N* j8 N { * f( d# g8 |3 E) U, | int i; 3 c; i+ Z& b6 r3 b: ]( H5 B" o' D' C float maxl=-1; 9 \4 D5 j1 M+ P( B, W! K9 J* d for(i=0;i<n;i++); n1 Z! ?6 d0 Y" Y8 i if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) ) n/ A1 j. x) K; t* Q3 D# P maxl=matrix/matrix[in];) m" _, p9 m6 q3 `* ], n if(maxl<0) $ j6 O( R, $ N# h return 1; 3 J" W9 Q, t7 s: j; ]( j0 b9 p ` return 0;* z. B; w" C$ a) f }8 D/ X5 ?6 ~% g5 s int SearchOut(int *temp,int in)//出基变量8 Z5 i# v3 N4 ?% c5 _! m, r {; j/ _* l, c1 H( y int i;; ~9 Q# G* q/ Y" J9 q- _0 L; w float min=10000; ' R0 u: b. P0 b) [1 l" x for(i=0;i<n;i++) 0 D0 Y6 b- h G, Z; e if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) & Y3 `8 \# e# A. n# O- Y7 K( z &&min>matrix/matrix[in]) 0 b& p& h/ e. H& y6 ~* u, l5 F {& Z, t0 g' n# z; @ min=matrix/matrix[in]; ' @5 l- T+ x e: v1 N8 P *temp=i;, G, l# S# m. F3 v# K }! y7 K! K" |* ]( H: l- b for(i=0;i<s;i++) ; H, d* m' @2 y# f& @! s8 [ if(a=1&&matrix[*temp]==1) " P( P1 E/ L1 q/ a& X8 d return i;7 |5 \* b H z6 { } / ^3 o$ c# l v2 J///////////////////////////////// * `) J, A; |! Wvoid Mto(int in,int temp)5 T0 `( v# V4 s {3 f5 i2 J7 h s( o" N4 i% P int i; ' F8 K+ w! G& Y6 d$ k for(i=0;i<=s;i++) 7 u4 V* M6 w" f$ | if(i!=in)- [ @! q; e0 ?2 f+ s6 J0 t matrix[temp]=matrix[temp]/matrix[temp][in];! D; h k7 W6 L3 e: Q) S7 { matrix[temp][in]=1; " w( P+ ]0 C6 W}3 x0 G7 i! U4 b1 ]. q0 {) W: y2 C! w /////////////////////////////+ h% O1 ]) p( A8 ]/ a2 [) _ void Be(int temp,int in)//初等变换( x# g, ?! W) M { ) ^; ^1 v# \0 T- C4 p int i,j;5 C: a9 a6 A0 a: ?8 m- U float c;# j4 f; o6 s! g8 L# G for(i=0;i<=n;i++) ( B; N0 C8 C; O0 @) H {) h! G6 \. Z" @3 l8 \ c=matrix[in]/matrix[temp][in]; ; B4 z. `- q" K& T% V if(i!=temp)9 Q; c) F: y/ W" c, s& N0 {! V, Y for(j=0;j<=s;j++)- J# t2 R8 R, x matrix[j]=matrix[j]-matrix[temp][j]*c; ) r* s/ Y& |1 r }; p, f, C: n) y; s1 `! u1 ? }1 W- L7 s' ~6 z4 t! M //////////////////////////, a9 [8 O, v* @6 }( Z9 L6 i void Achange(int in,int out)//出基入基转换& P4 z J& g, D9 |" ?" v {8 U) g7 ]) ?! J# E& ~. ` int temp=a[in]; 1 t$ f6 {5 M; W4 y a[in]=a[out]; * N9 A) x: H; ]; D a[out]=temp; ' S r: ]5 P6 a0 a+ t3 }1 M# X# |}3 E, |* a c7 k$ |' n ////////////////////////# U( b. @) d, y: B* R; s$ P void Print() ; e" q& P5 r2 D5 |9 b3 H{7 W: y; L) P3 [- j4 j; d int i,j,k,temp=0;8 O2 U+ G/ G) v5 c for(i=0;i<n;i++)4 j& W" ~% a" b { : D" T+ x# X( h9 W/ s, i6 J" N for(k=temp;k<s;k++) m' o: M% p" h if(a[k]==1) 7 o5 G# v* {9 ^5 U { & f5 j' f* r+ A cout<<k;: `. e$ Q( d; q temp=k+1; / ]( k' W) v2 p' ]( p0 N% d k=s; }! ^+ m' _3 L) @9 c- h/ ^7 b for(j=0;j<=s;j++)% q `. C4 ?$ X& p7 |3 P3 B3 r2 \ cout<<matrix[j]; ! n, M$ b' ]- l: c0 s cout<<"\n";: Y& Y' D- w( Y- M } 1 P2 p1 f: G: }$ b cout<<"Rj"; 4 V' l0 @: I( X3 `7 i7 Y( i( ] for(j=0;j<=s;j++) / ^9 Z: R! G6 P$ F cout<<matrix[n][j];, B# N3 }* N8 G, x, @9 l, H cout<<"\n"; % j1 O$ i3 I: [) c b' I9 B4 Q9 Y} . ?1 _" C& o0 d( L- N//////////////////////// & l2 Q) _2 u) M! Svoid InitPrint() / U( k6 h% l, u& K4 b{ 4 I1 x+ M+ D+ m1 t: G int i;; P* p, _* D) ^: f% F { cout<<"X";* @8 ~, c3 q# u for(i=0;i<s;i++)9 H" u! a0 J+ V& h" t9 q cout<<i;+ Y" R3 Z1 ]* n& Z) U cout<<"b\n";9 b, G( d. A" j cout<<" ";; n5 Q# w5 m. G/ |1 U% E: U0 g1 \7 b cout<<"\n";0 {% q, S6 ^9 Z: z8 g; d/ W }0 [9 T: G T0 `# {& G4 d3 L1 g( O //////////////////- S D* [" Z, C void Result() * X- m/ F. r; I9 F{# A9 z; e+ C, G/ i& f int i; % ^& x; X, S, m9 h/ V cout<<"("; - W1 Z* Q: p# @; G% R! G | for(i=0;i<s;i++)& }: j6 Z7 _! N c7 ] cout<<x; 8 N+ D. y$ j' W cout<<")";7 D3 E" C/ O5 h+ q8 n if(type==1)9 ]6 p; J# f0 O: O, j4 P% ` cout<<"Zmax="<<matrix[n]; 0 W( ]7 ]+ A3 F: q' q, m+ A$ b0 o0 G, b else cout<<"Zmin="<<matrix[n];, P/ N P: F7 Z } 4 K; C+ {1 o& P8 _+ p//////////////////////, |' Q- y6 m* ~% X! Q& W( P1 n void PrintResult()& c$ J$ b$ {6 Z' F# o: r3 t2 e* q; ` {% C/ R$ g% D7 ^$ l& r' Y: O& R if(type==0) 3 v5 m; R) b2 R! j( e# y; V cout<<"the Minimal:"<<matrix[n]; $ L$ E0 n4 a4 C% w else cout<<"theMaximum:"<<matrix[n]; . H: R- u: a1 c7 Y6 [/ g2 `}7 L1 D- k! j) Q" ~: O' R //////////////////////////////// 1 ]' G/ J. g6 v2 P! g/ Cvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 % r5 T+ n0 f r* R$ z{ ) u. d8 u4 _# P int i,j; 3 J# y3 A9 c' J2 v+ G+ h- | for(i=0;i<n;i++) . i( a3 d! e4 s& D. g T { 1 z4 a6 |4 N5 R9 w& Q! r for(j=m;j<m+indexe;j++) . c& |) \- d7 S2 O; }9 z( d if(nget[j-m]!=-1)matrix[j]=0;( _9 E( ^( e _. z, o* H; D( N else matrix[j]=-1; $ u4 A1 m3 {# @: k. b9 M$ X9 l for(j=m+indexe;j<m+indexe+indexl;j++)/ K+ |2 Y% Y! v( q4 H" m! w if(nlet[j-m-indexe]!=1)matrix[j]=0;) B2 R# F1 W. `3 n# ] else matrix[j]=1;: E* O5 M Q5 Q8 a: W for(j=m+indexe+indexl;j<s;j++) 0 U0 M; k3 u, Y5 P7 b if(net[j-m-indexe-indexl]!=1)matrix[j]=0; i3 Z+ W7 K; B) K( L! I" {1 W" G9 a else matrix[j]=1; ' \0 Z. N# }& Z6 [& }- V4 C' D }& Q0 H" D2 N: \1 ?5 ^0 d$ z) d for(i=m;i<m+indexe+indexl;i++) , s; ]& ~' h b' `) x matrix[n]=0; . S3 J! m0 c- g+ c8 R for(i=m+indexe+indexl;i<s;i++)% n* L7 J# T7 g& u matrix[n]=100; / v& j u+ M! P+ c matrix[n]~~=0;! \+ [7 w$ H3 `! B" F) l }~~
; ~7 z' D& Y! p3 b: \) M0 \
///////////////////////////7 O6 B1 o3 @! b7 ~" j3 C/ a void ProcessA()//初始a[]! j, \' M4 C& x0 } { , i. v6 Z. f+ P int i;7 r3 f2 X* F2 v for(i=0;i<m+indexe;i++) 0 G8 D ~8 j# Q* z a=0;4 [5 V' Z% B- [9 w; j0 v for(i=m+indexe;i<s;i++)( Z/ X1 B k& b a=1;1 \% c" h/ ?. a9 N- }. g }
" V! z& T! M7 {/ Y: B! z ?
//////////////////////////////// - \# x2 Y8 R7 M6 z) F3 I5 Jvoid Input(float b[],int code[]) ) K( n ?9 I! Y8 b. ]" l0 t3 L3 _{ 6 ^9 t+ r( y0 d! q2 M int i=0;int j=0;, M2 Z6 z, r0 E4 T ` cout<<"The equator variable and Restrictor\n";4 `: z, Y2 u$ K* S8 m& f# T cin>>m>>n; 9 Y7 G; Y- p+ t- t& Z4 y for(i=0;i<n;i++) 1 V7 |! O( H1 T% F) S. F$ G9 U {" N0 d( i# H: }7 I cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; ' T3 G! x% E" J# {# L8 n cin>>b>>code; l, k/ s+ H6 e5 F cout<<"The 系数 \n";! s$ O8 w" Z/ c3 b4 F! O9 ] for(i=0;j<m;j++)/ {* @" l; j. i% H cin>>matrix[j]; 1 B$ M( V3 c. @) v6 D% e1 o3 Q, @) n- s } # b$ g% ^2 @0 }) k% T cout<<"the type 0:Min 1:max\n"; / t2 e( U M$ z1 X0 a; ?2 w4 m do{ : x0 {: G3 Y5 b. `% z cin>>type; 0 }6 @- {6 Q. K9 C& @ if(type!=0&&type!=1)2 ?- B$ x Z, D" N6 f& x1 u" t cout<<"error,ReInput!\n"; : S7 O c& E R) U5 A4 r- E }while(type!=0&&type!=1);( y& B* w) R& S( t cout<<"the Z\n";) S6 M: H2 X/ L2 u2 z$ A for(i=0;i<m;i++) 6 j! }, U: k' i( z) k) j cin>>matrix[n];( O2 P7 @0 j* j2 _7 Q6 ] if(type==1) 4 k' c @" Y1 p, h; Q' H0 a+ f for(i=0;i<m;i++)- W& t" `: O7 G matrix[n]=-matrix[n];5 R! }# `& t$ z) E$ O }
4 {7 N0 h8 ^0 `/ s) L, p
& ^- T* {9 _. H ////////////////// , B$ v2 K7 g" r& w: Q6 [void Xartificial()//消去人工变量- z6 C- H1 @5 W. \2 Y/ D, S& r3 d {/ _8 i( b1 J8 V0 I$ h% u" h int i,j,k; & M2 @# Z. s' x if(indexg!=0) d1 }6 z& H6 G# k. @ { ) l3 k( ^$ j6 D' x4 A+ ^- B/ s for(i=m+indexe+indexl;i<s;i++)' `" ?1 C9 T" k0 U5 L {; m2 r1 |4 m. f& `0 l for(j=0;j<n;j++)0 v+ F3 D& g% t9 o1 p6 ]: w3 O; \ if(matrix[j]==1)* T% g# t- A% {& [7 Z, s" i% K& f { 2 \8 @$ Y1 z- R& r& ? for(k=0;k<=s;k++) ! y2 E/ \) c; c* v- H9 M matrix[n][k]=matrix[n][k]-matrix[j][k]*100; c$ X) c; E3 ^ j=n;8 c7 H/ z! s$ N' _8 W } 0 s* A8 b) d5 o8 Z- B1 a1 q. z }& J7 E9 M1 o, d% c( W3 ]6 l3 a } ' I$ v( E, L. F' l}
3 l' K$ q* E [0 g
////////////////////////////////////////////////. a, F& c. D; q& v void Process(float c[][100],int row,int vol)+ R6 P w) ]1 Q" t( Y; L& [ {0 F+ y; s3 } T# D% z. B1 r3 \ int i;# v0 ?- w6 Y3 g( c! R for(i=0;i<n;i++)" E: Z6 c# Q" h4 u2 ~7 t% i, E1 t if(i!=row)c[vol]=0;/ w% |/ H) G' I' q9 J } / J# P0 V4 s$ H& L$ p) ]. G//////////////////////+ ]- q6 \& X% O& t5 v void Start(float b[],int code[])# o* m- N% R8 A3 M7 v7 V% L {" l! c1 D7 j3 k4 c4 u1 A) @) V5 K int i; # h7 W7 P3 Q* u. W& Q float nget[100][100],nlet[100][100],net[100][100]; # M3 o+ a" k3 ~ indexe=indexl=indexg=0;& D* `; w% i4 _* X! P for(i=0;i<n;i++) / q3 N1 R8 N* x, [6 {; n { 4 V+ q. y# T4 V$ V" h5 R if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}1 ?( M5 h4 f7 |6 U if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} & n: j; G V) b8 J1 Z if(code==2){! A! d' s c4 e, ~( M! {, j net[indexg++]=1;( C/ J& W2 w# q) V) |: {1 R nget[indexe++]=-1; # ]1 K% e: ~2 L. m/ @ Process(net,i,indexg-1)rocess(nlet,i,indexe-1);5 X: P$ b$ Y, j; A7 X L0 @ }3 z$ V' b! L; `$ U' D- l- h' M# | } 8 j2 @) F" R9 { s=indexe+indexl+indexg+m; ! f+ G; E. K9 E3 p. ?- T8 P' p Merge(nget,nlet,net,b); / y& S% |% P: ]4 O" |/ s" e& p ProcessA(); - r! K6 T7 i4 Z& z InitPrint(); 4 b7 S. J6 Q* |0 C4 t j" v; _ Xartificial(); . N3 b8 B A# }}
# x) H* J0 E$ a! v9 n
void Simplix()//单纯形法0 G& R( G, o) r6 k { # ~) L9 @3 h* L& Y int in,out,temp=0; e M8 ]3 Z5 l4 l9 [+ b( H& A, [! H7 l while(1) - [7 T$ P1 O8 K8 B7 u3 c/ w { * K7 R; t' C" U- D6 d) v, S4 ]6 J3 m: c jckxj();$ |' L: \# j6 j3 f5 U Print(); ; e0 l+ V6 E& D0 f) |8 m Result();* r" D& T" d; V) w3 r if(!rj()) in=Min(); . r: G! Y8 k2 d else{ ! { w# N1 x3 S! E$ E! _ if(indexg!=0) ( H, f6 k5 X! a7 v JustArtificial();9 V C( y$ g) H/ G. K1 c PrintResult();* E9 W! R' k( I$ l, n return; + |3 m8 ~$ i V" ]$ p& \. r }% I5 C6 q6 d3 m7 I2 U7 O" } if(Check(in)) 7 ?% n, M& S& }% D7 w { " `! Y" j5 N5 J" D cout<<"No Delimition\n"; 3 p6 q- w1 n- c' y! m0 z return;9 k: y( B) h) {5 T }- w8 m/ C( |& Z9 c# @3 [ out=SearchOut(&temp,in);6 H% M0 F) v+ U4 y5 T8 h$ V2 T Mto(in,temp); 8 W/ g( D% V1 b/ u1 k r9 F Be(temp,in);6 _5 U P5 J% }$ p( ?6 c$ E Achange(in,out); 7 Y1 i! B, M' \( G1 x } 5 ]+ W+ T4 L% s& N$ s}
) H. T0 E M1 T8 v, V# w- J7 U
void main(). ~' a* d5 K) O3 U; f, u0 r. D {9 ^) {- p8 I# a int code[100];//输入符号标记2 R/ X* ?- G' `7 s& n7 {+ R8 ` float b[100];( U4 W Z' h/ R3 p' c5 v Input(b,code);//初始化 5 y$ z: U4 G7 }" x Start(b,code);//标准化行; m3 O) \( q" Y4 K2 @: }' Q Simplix();/ q0 X6 Z; d" a; g1 f" _) I8 e4 l } ! U) J) Z5 f7 Z# X# G" v. w. X4 D