单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> 7 s4 D1 r% t) R% N6 k& {#include<math.h>4 T; A1 W5 s* i& `5 { float matrix[100][100],x[100]; 2 a; Z8 G' @5 s7 T# \int a[100]; - u, [! Y9 g; e' cint m,n,s,type;5 q; T$ X" ]4 Q; H( F( @4 h& ]" [ int indexe,indexl,indexg;# b l$ {' y" t( n* p% _ ///////////////////////////////// ' x" U+ G7 V7 g( k- Bvoid jckxj()//基础可行解 5 G2 @/ W) ^. F0 s' d{# _ H) e* |4 M+ X: @9 S: \ int i,j;- R4 {6 {/ Q/ b7 F' {( a* J for(i=0;i<n;i++)1 w& d7 ?3 n+ g- M- I+ R for(j=0;j<s;j++) ) ^9 y, R2 R- r# w6 B; ]* T if(matrix[j]==1&&a[j]==1) 0 P# v1 y" D3 z) Z% Z {+ R, P% Y) U7 W4 b; U x[j]=matrix~~;: w# z# `6 q( E. h j=s; 7 o1 [5 a; G. D3 a' a. d) W! F } 0 d9 @6 D ~: M( n for(i=0;i<s;i++)7 h1 F6 ~8 V5 L if(a==0)x=0;: e/ \* {, M2 Q }~~

' N" M! m1 n h
int rj()//基解矩阵 F- f3 i" x- x- D& K+ }4 h5 @ { ( q! D# e" d- Q# |+ s int i; 3 {7 ?" n) l( x* i" C for(i=0;i<s;i++) & U( \6 G$ l# c3 c, |; ]9 l% \ if(fabs(matrix[n])>=0.000001) $ L# ?: |( a$ P2 f% w" u; A: O if(matrix[n]<0)return 0; 8 q3 a; @+ o$ I0 S: X ~3 U/ H. Z return 1; `8 m, i; O& J( e+ J+ @# n- X} 4 S6 ~2 ~% G2 D' [* i6 c- zint Min()//求最小的7 s0 s( O# x, W/ C; ~& c. Z7 k {: v6 j3 R0 i4 i; @9 z9 `5 \ int i,temp=0; " A4 v" F5 v* p- M; U2 d float min=matrix[n][0];1 z2 |% u) q O% Y) r' { L for(i=1;i<s;i++) ' O7 r5 f! M$ J4 ^( Z if(min>matrix[n])! W, K' c7 n: m! c" o {- I8 p0 j1 t# S2 P2 A6 P+ S min=matrix[n]; e/ L8 ~, U2 R) m7 d2 `# V temp=i; I( n# i' E( v' b7 U2 Y0 g4 l6 L2 b } Y# K- A/ W8 O7 G6 ~6 T return temp;7 }2 s# D, |6 l6 C } : R4 X5 ~3 b8 U0 O# e; F8 H/////////////////////////////////% b) g5 ~4 P, j( t8 J5 `: k void JustArtificial()//人工变量! N/ c7 S% M2 l' R# Q+ X6 F$ p {7 l2 B* x; w$ \. b4 o int i; 0 r% u3 O; Y! R$ F% i/ q; v for(i=m+indexe+indexl;i<s;i++)% N, e9 u2 M9 Y5 T if(fabs(x)>=0.000001)8 a ~) N9 e8 p {# D( ~" k \ B, y0 x+ Q cout<<"NO Answer\n"; $ r- @* j2 w8 n8 \, \, p return; ) }( W M* f, P5 i% q; s } 9 s3 D% c2 M3 i( k, q' k9 U+ h} % u) S/ q4 L9 u///////////////////// 4 ?9 I2 t4 G" sint Check(int in)//检验4 I- E9 {. d; } { 4 b! H; ~- a1 N8 h: n5 x0 Q+ r8 b int i;# c, P0 R8 s$ L, R8 A float maxl=-1; 3 Y K9 E' t! D2 N5 g for(i=0;i<n;i++)2 k' b! n' ~+ t. D; H) N$ O, I5 Y# S if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])! i& N+ D- G; T; Z maxl=matrix/matrix[in]; $ t7 C8 T" g: Z' O2 x if(maxl<0) & {) @: E5 f3 `' Y return 1;* ^2 Z6 C$ M: G3 E return 0;/ ~4 j$ ?/ n2 L- }0 w } ( m# w4 J: p) b% ]% \' u6 F; Lint SearchOut(int *temp,int in)//出基变量" }6 M' h1 f } {( U* S# ]! T3 j- V( w int i;3 s x$ q/ n& [7 R$ H; W3 {# ` float min=10000;7 H& y/ b# A: u+ u' p. [ for(i=0;i<n;i++)! I* D2 a- a( P4 r0 c8 c if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 0 Q, A. _+ u6 v9 g6 K& t1 ~5 [ &&min>matrix/matrix[in])2 [3 N& P& P. v3 \+ F1 E3 ? {7 ~* i* P# s, B$ v9 ~( n$ ~# O min=matrix/matrix[in];& L5 `3 g: f8 f; {. ~& H *temp=i;/ b0 Z0 L7 C# }- |: ^6 F: l } ! k+ x+ V6 u A- Q# B for(i=0;i<s;i++)' ]: T- |9 g* ^' r+ O: Y, r( r if(a=1&&matrix[*temp]==1) % U O& P4 Q; ^$ q) H4 R4 c& \& v return i; ' \: N2 ]! [0 q5 A, \+ c; O4 X} " B! @ f/ [+ e///////////////////////////////// 6 v6 m1 w' q1 V6 K% bvoid Mto(int in,int temp) ! U5 H2 w& H( _( G# I# Y7 F{ 1 ~0 i- x! u0 y2 G( P int i; % [% |% y0 b' ^$ E C3 ~1 j for(i=0;i<=s;i++)5 }" E% ~4 y2 `5 o if(i!=in). y o4 e' p; ?5 Q matrix[temp]=matrix[temp]/matrix[temp][in]; 8 {, Z0 s C' j; h3 A1 d/ c matrix[temp][in]=1; % j5 } M5 H9 I+ E} ; z2 V z! c" K: u///////////////////////////// ( t- A# L& @3 Y4 \void Be(int temp,int in)//初等变换" T3 t5 Q P7 @. o: H" W { 3 G9 ~4 A' h8 O( D4 j% E6 \! _8 r int i,j; 3 t, w- ^" J n# N5 }7 m+ u" N float c;0 M0 c+ c" W: H. ` for(i=0;i<=n;i++), v# R4 `8 v, ?1 R- U6 e: Z% @ {' e2 }; S# W& E/ J) @ c=matrix[in]/matrix[temp][in];+ x i9 C/ A; B/ e, j0 n# n7 |' [ if(i!=temp) % T4 D7 \! `3 Y# I5 h for(j=0;j<=s;j++) . t E5 A2 O& u. s4 }# Y% k5 F- b+ F matrix[j]=matrix[j]-matrix[temp][j]*c; 0 q9 d. x, w/ s8 o8 ]0 b }6 `, \! z5 H0 G. p } 5 m- I2 Q3 R9 T7 g Z$ @6 `0 n////////////////////////// 4 S% g) }3 P& Q, U6 avoid Achange(int in,int out)//出基入基转换; e/ P# o! u6 | { ) [- p5 u! s. b: D3 Z! |" ~ int temp=a[in]; * e0 \6 a Q0 `0 X a[in]=a[out];: V* H: v, a1 g: O a[out]=temp;; t! h8 N' L0 r3 P; @# { } 8 ^! S# E: V# k3 {! w- x////////////////////////4 j0 G5 M6 x2 b) d; W) ]( I void Print() $ d. H3 `( j( _* T5 l- A* {{* m1 W; A: b! x s, O2 h5 b$ K$ a9 D( } int i,j,k,temp=0;2 N' L/ O* @& r+ o+ B/ H' X for(i=0;i<n;i++) 4 o9 a" N( o% q1 S3 O- a E1 z* F {! p+ K6 A( o' y8 f: M" z for(k=temp;k<s;k++)% T! |' i- Z& N' [ if(a[k]==1)! ]$ N: c; P/ j# j+ p7 Y1 C: k {' x' c. G: _4 V. I/ _6 ~. J cout<<k;# U6 X* X) r! ~, n temp=k+1; " @9 Q& X: F3 m- X; S" a' d k=s;1 y. A+ l) Z+ }" |: B0 b }+ D6 F3 x2 |% E9 k+ T2 O: F for(j=0;j<=s;j++) ' p# @2 [* G9 |& [+ E cout<<matrix[j]; ! ^7 T5 n" d/ j& k e4 v6 \ cout<<"\n";' k2 ~" i1 `; |+ ?( m } 8 q& u4 _6 K- @ N cout<<"Rj"; ( i" _! }& }* r E, h for(j=0;j<=s;j++)+ l0 |" j! ?9 P5 Z( V cout<<matrix[n][j];0 H" k$ Z8 g- f t9 L" I cout<<"\n";5 D# |8 Z& V6 x% F$ H* v$ I) N' ] } ; o) W7 n% A% h' _; b! I; y9 f////////////////////////# z8 u' \- Y; `6 _# E6 M; L void InitPrint() / J: _% U5 l6 `; `! O{. D; V9 `* q: l9 d% F" J# [2 ^0 @ int i; 8 |* b8 t* @* q$ M cout<<"X"; ; J/ R/ ?, f# M5 `7 Q for(i=0;i<s;i++). C2 ?& }3 R1 F0 w. g cout<<i;0 j1 q W4 w; ^9 C* i6 y cout<<"b\n"; ; K3 R/ D' E" m! @, ` cout<<" "; , S" B7 K, J. z0 M2 ` cout<<"\n"; & f+ S$ C7 T* f% c3 F}5 E. ]- {1 X' s //////////////////" b4 z" K @6 E! X- O void Result() / y4 a5 y6 T3 v3 g4 R% h{ / W0 P$ H. @& @ i1 U% c int i; . w1 U6 T1 l' o+ J0 F% ?2 x cout<<"("; 4 U* n `6 Y9 I7 Q' F$ ?# _ for(i=0;i<s;i++); d: s1 ]2 ]: F( X- h" Q! P, [8 c cout<<x;2 L0 S, \3 s' c$ R cout<<")"; : y' \# _( R7 E# _ if(type==1). F& ^/ S: z K! B2 L' E( s cout<<"Zmax="<<matrix[n]; & m* }) |) N8 ?& c else cout<<"Zmin="<<matrix[n];. s) G$ B) F: a; r& r } 0 i0 g3 W8 @" D7 p" e, M////////////////////// 1 s( @: N! w% s% G9 _2 f# `5 ?$ cvoid PrintResult() x: s" g- e) _2 `0 \& x/ t{/ M0 _7 W2 p9 Q8 ] if(type==0)' T2 }! ~+ c% T& o/ B cout<<"the Minimal:"<<matrix[n];2 J' N! Y4 O' @+ i5 ~ else cout<<"theMaximum:"<<matrix[n]; . R: F& @" U8 v2 ?3 t- w) r, W} & x- N. z a. `) x////////////////////////////////: o) c Z# m+ f5 _8 G3 B Z void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 5 T; t2 N3 m/ D7 c1 U{ 8 m1 r. e2 M4 ]& s" ~) ]7 v int i,j;2 m# G2 X2 ^4 A0 p: [7 E+ q for(i=0;i<n;i++) % {0 Y3 }6 k( T1 P1 Z { 2 o+ u- J$ G) o: Z" ? for(j=m;j<m+indexe;j++)1 \- P s" x) { if(nget[j-m]!=-1)matrix[j]=0; 1 N) ?9 r) @- f else matrix[j]=-1; " ~1 L' s! u: h for(j=m+indexe;j<m+indexe+indexl;j++)) m& z" ?4 Z+ {' w% t+ a# | if(nlet[j-m-indexe]!=1)matrix[j]=0; % x5 |0 D3 R8 B3 m% ^4 ] v* n. T else matrix[j]=1; 6 b' S# F! e: \& I, y for(j=m+indexe+indexl;j<s;j++)( ^; D7 m$ t$ ^, E+ s if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 8 q$ E1 ^! ?* @7 w" _0 F5 W. @ else matrix[j]=1; + s3 H1 ^% y" Y% F }# _% h8 U" m% P5 x1 s1 G: a for(i=m;i<m+indexe+indexl;i++) 0 B% z6 |5 E! R matrix[n]=0; " a) D, |& h# D/ n q. _* o for(i=m+indexe+indexl;i<s;i++)4 z$ r3 Y" }4 f& q matrix[n]=100; : Q$ w$ l; x* v. W! e/ ^4 `) | matrix[n]~~=0; $ `; S f8 c& a5 h}~~
R2 v; M7 }! p/ p$ A0 P4 x
///////////////////////////- l# O7 q% T8 }$ K void ProcessA()//初始a[]5 _" R3 O% Q9 h7 L { * c1 v/ N6 C+ W' C! t3 f int i; ) d6 Q4 m( y3 d ?9 T d for(i=0;i<m+indexe;i++)- V$ k! @% X; L$ o$ T7 O a=0;* ^% o- K1 T8 o G o for(i=m+indexe;i<s;i++)2 j0 Y/ |, x! R8 s. s9 \ a=1; n- y, X# p4 L% A}
: G) X1 y; I. j: W
////////////////////////////////( `( C/ S+ u: c5 c void Input(float b[],int code[]) 4 a7 Y5 g) z! r! P5 u{# c8 x$ G2 o; c( I5 r int i=0;int j=0; , {* c* w1 ~2 y& I. q cout<<"The equator variable and Restrictor\n";( e( p# s& }# m3 v cin>>m>>n;4 q7 r% J' m; A0 G/ n' N% J0 L for(i=0;i<n;i++) - L7 O7 m$ J$ u: ^: c, s {( R4 n" _3 J: t& O+ r5 b cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";# p6 i& B) e9 X% E8 P! e cin>>b>>code;* z$ x% z" h- G5 g( B! K, v cout<<"The 系数 \n";' n; t; _: M: _: @ S( v: R6 W. N6 I for(i=0;j<m;j++) 2 h! R6 g6 y+ M. { cin>>matrix[j];9 v! @- P+ b- X: ]" o }9 X0 {1 m. T( T3 Y! O7 T3 F/ Y cout<<"the type 0:Min 1:max\n";8 g: x: q2 c: S- E! v do{ $ ~$ Q+ u" o* L. N9 c cin>>type;7 J9 C' D7 ?1 E if(type!=0&&type!=1) ; C4 F, s1 ~4 r$ w( \. @0 l cout<<"error,ReInput!\n";! O. y; A! K. u' ~3 E# L }while(type!=0&&type!=1); 3 b4 a0 g" r0 q4 ` cout<<"the Z\n";9 x5 K+ N7 W/ ? i6 x( u for(i=0;i<m;i++)5 P1 d7 Z+ H' o1 r0 ^ cin>>matrix[n]; 7 _- q \; S. u, }# e7 m9 q if(type==1)0 I& _/ k- K# m' \- i4 ?, u6 }/ o' z0 B for(i=0;i<m;i++)8 K# x8 S1 H: v' ^/ s& }. H matrix[n]=-matrix[n];# i4 ~3 W7 S% [9 H9 m7 G6 s: D* a a }
6 ?7 A- M* A4 C! `4 T# J) R
1 J" K5 D6 L/ P- \////////////////// * {/ g' y1 G2 `3 x9 l' m( P# z' V! { void Xartificial()//消去人工变量" u) _4 p9 Q! Y' G9 n1 L+ {+ u { # k- [$ C! Y; A int i,j,k; 4 S5 v/ F Z) g) C& p' s7 J& y if(indexg!=0) - c$ G! x$ l* V, _ {4 J4 a; Q: }: H; }" q for(i=m+indexe+indexl;i<s;i++) , w; r- a F9 d( v* X+ S, q {7 O3 W: u6 I3 D for(j=0;j<n;j++)( ]- X( {( E4 M( [3 E- B if(matrix[j]==1)5 L: @0 X* t( y8 u5 g7 d1 H0 n { 9 u2 u3 Z( b; R; I; Z3 r7 S for(k=0;k<=s;k++) # N1 M/ G0 U3 K2 K7 u4 w# c matrix[n][k]=matrix[n][k]-matrix[j][k]*100;" {: Z/ y( p* Q5 p0 x/ s j=n; % g1 E9 k9 |2 b! @# H2 h$ W }6 y2 Q5 K4 @. A, i7 v } ( H, o& j4 N2 E! G5 \+ {$ t }) @( x# ]: U5 X$ j9 l# | }
% Q5 i7 f9 i! K4 n/ ^) O4 @
//////////////////////////////////////////////// 3 a4 r+ i4 G- d. r/ y, Wvoid Process(float c[][100],int row,int vol) 7 B2 K. x& ^& z n& v{6 E0 r, m) b, A h int i; 9 y. X' |% g8 V4 g1 Z# ^. n for(i=0;i<n;i++) ( q$ x) q, d" H/ r1 a if(i!=row)c[vol]=0; }# M7 Q. R* r5 C, Z- `2 G } # r( s) R# v' | @$ e3 o& A P//////////////////////2 R, l" ]. f, {' ~* P) i, e7 q void Start(float b[],int code[]) ) U0 Y* J+ C) ?, L{7 M& Z) }% y8 g, k' h ? int i;$ b% ~2 Y& l; z" g0 j float nget[100][100],nlet[100][100],net[100][100];# O: }$ x0 F8 U U! c' b indexe=indexl=indexg=0; + r+ p: B! _! C Q% W for(i=0;i<n;i++)/ N q X! X' E6 [) l% X5 Z+ p { P n) M4 P1 T7 d, y5 x+ a' O if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} ~4 Z3 N# C* F' ~% v$ q8 b5 F, W8 w if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}: D& E' h: v9 I9 p5 W3 X- X' w if(code==2){2 S/ l: F; S9 j* _) i( h net[indexg++]=1;) I0 m) d' t1 o: Z" j7 R nget[indexe++]=-1;& B9 x( [+ i. r! F% | Process(net,i,indexg-1)rocess(nlet,i,indexe-1); $ _/ A5 e5 Z) M. @* `$ Y8 n7 e }/ o! @1 S5 S; y9 E" Q } ( {# _+ d/ D4 e h; D s=indexe+indexl+indexg+m; - W) ]* ~7 r$ f% M Merge(nget,nlet,net,b); ) X3 m7 z# [7 d$ I) S ProcessA();6 q/ g0 d: Z6 Y; x# k' `- W InitPrint(); + @5 `7 k& G* o) W# d: o+ P+ x Xartificial(); , }% f5 \. y) U2 _}
2 ~/ u! k. C( L, [
void Simplix()//单纯形法% R; O2 M! w' G2 y8 R5 L3 M8 P { 8 y& b* P9 I+ q8 t) q5 t int in,out,temp=0; . @% \2 C5 y, Q% w& J while(1) J! j* _3 N5 P3 Y. \* z! D. f& F { ' b# Q; C' _- I9 F jckxj(); ! Y+ B }+ V7 a* t6 A# Z* p& n Print(); : P% Y: x m% G$ i+ ^, s: Y# W Result(); 0 p6 k8 q" U' j) d% h if(!rj()) in=Min(); : Q3 a5 o2 F# p b1 X else{' Z& i! ]" ~# V# o if(indexg!=0)6 ?$ R7 a6 o4 R: p- ^6 M JustArtificial(); / ^; E! l" c* M4 J5 w& p PrintResult();% h5 D: K8 s- [0 { return; % I7 }" I& B0 o } ; [% T. m$ J% N6 q( i if(Check(in))3 Q7 q; D; U5 g9 T* e8 u { - \4 i' x3 v% T/ Y1 l; Y) L cout<<"No Delimition\n"; 3 d+ q3 z' q1 T0 w# u return; , q6 U6 m' d' i5 J } 8 @; ]+ t+ V- X out=SearchOut(&temp,in);1 r0 U- w" ^1 \5 U5 A! ] Mto(in,temp); 2 ]' H. X# d0 g9 ^ Be(temp,in);3 m X* i0 ?. G0 M4 z2 O4 E" [ Achange(in,out);3 e2 X4 B5 w9 ?( g } 7 E6 s; Y6 O; l$ [6 l}
l( Z8 A' {" p6 W# ?/ E
void main() + |' \# v% p1 S/ ^" l" w0 O{. v8 Q7 G2 e+ i int code[100];//输入符号标记& `$ w6 O7 i: l( V* }/ } float b[100];! q& w) Y" M' W5 h Input(b,code);//初始化" k/ |+ B9 s" q. }" A Start(b,code);//标准化行 : x5 H$ ?& V, k- x, t1 l3 H8 } Simplix();( [: q. l4 s4 Q } 9 x! [0 w! f1 t6 o# j8 H