单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h>, C0 E* b2 N2 s6 ]4 l# J4 N; j #include<math.h>: ^/ j0 x5 V; l9 P- X) R/ m float matrix[100][100],x[100];4 N2 [+ D1 ]5 h, d int a[100]; ! V* U8 z# W$ ~* ]1 W8 p" y' nint m,n,s,type; v' r- [6 \+ W. O1 i0 o! V) Rint indexe,indexl,indexg;" u0 N4 c" J! h4 ~' {- z& i% g ///////////////////////////////// ; q0 J2 F: U5 U& L; b9 M# nvoid jckxj()//基础可行解( m. ~5 R: r1 k3 Z {. U8 D1 ~4 |* V) e5 s int i,j; : {, q) Z. S* ^' b+ G for(i=0;i<n;i++)2 a$ Z# d$ B9 i: v9 ^ for(j=0;j<s;j++) 2 B4 e- `0 }- b" K/ h/ Q" a) t if(matrix[j]==1&&a[j]==1) 9 G/ b, x) F* M$ V2 c { 6 P/ B( t$ T1 R" \9 y x[j]=matrix~~;7 h* m4 W3 P+ e, h" ]: U j=s;6 m9 u0 u' k8 {4 ] } ) L/ w# o5 Z" ^& r$ f. U for(i=0;i<s;i++)0 F5 G4 [& W8 a- z p if(a==0)x=0;* ^, f; _" A" W4 v7 ]' U }~~

t, |: I. N# Z: k
int rj()//基解矩阵 2 P: d7 y/ s+ M{3 ~7 Z0 H8 \$ @* R6 m' N4 i. H int i; 3 z9 @$ u ^" w$ d! p for(i=0;i<s;i++) ) _) g4 Z. F1 f1 e, x# Y if(fabs(matrix[n])>=0.000001) 6 P# T2 J; E2 _" k if(matrix[n]<0)return 0;( Y( A0 r& K- Y# v; U: m( T return 1; ; _- {& z& v4 p- L} 7 v0 j) y' @ A: G) Dint Min()//求最小的 3 I/ E5 q0 \! P& m6 S/ Y: Y{5 d4 b" w* T" d8 S! G int i,temp=0; 6 S" M6 y4 R! v+ U9 q float min=matrix[n][0]; 3 w* K f5 `$ M$ @! [ for(i=1;i<s;i++) # q! G: `0 A n( S$ H if(min>matrix[n]). j5 }% j( e8 ]; ~( ^$ v1 O {) b. V) p+ h8 b( |' Q& {' W min=matrix[n];/ b" T; i1 G+ ~0 k+ E temp=i;6 ]8 ~2 W1 a. J8 m }2 s. w- I$ b$ G return temp;: r1 @: R, I$ B) G1 }2 U } : @7 k2 I/ V7 A7 z8 d; M/////////////////////////////////' V6 Q* b8 Y) U$ _' ^/ k4 W void JustArtificial()//人工变量3 N6 V: x; t3 A" x8 e {$ G* O! n R/ {. B int i;3 S' W" l+ u: }# k0 Q: u" u for(i=m+indexe+indexl;i<s;i++)6 z1 v. z* g9 ?! [8 ^% {3 g: u( N if(fabs(x)>=0.000001)5 `1 E1 A4 ~6 ^2 g { D8 J* w9 ]& c+ u% ] cout<<"NO Answer\n";/ o8 _/ {. v; C) {6 r return;4 w3 A' f! B6 v$ N# v# |9 P/ d V& g/ a4 ` }0 M6 C- Y! L+ l0 [. Q }; X4 l* p* i# r: o( J; y8 e: o ///////////////////// " p# A2 Y" I3 i B2 qint Check(int in)//检验 : e$ Q% Z; Y2 y/ {, R/ z{; n- h2 [) y" {7 E( G int i;/ r9 I* t4 L) ^# Z3 s float maxl=-1;, V; L$ Z# ^' K% U for(i=0;i<n;i++) ' u+ u( x; }* r4 @5 x- B. t( ?7 ~ if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])9 D1 u) Y0 I: K+ u; x# r; ]1 M maxl=matrix/matrix[in];. E6 ]& F# _5 a2 d! M6 _6 s9 o if(maxl<0) D6 D# v5 A9 h. r return 1; 3 D- |0 t e2 U* P7 V return 0; / J+ A3 r7 Y3 X, h A}$ W w1 R4 h) t" h int SearchOut(int *temp,int in)//出基变量5 w& l6 L2 v) q { $ i! f# @* X! Y2 C int i;9 F, e' m5 y4 u/ U% E float min=10000;2 Z1 R% ^/ P4 d4 l F$ B for(i=0;i<n;i++)5 U3 ~1 T1 w4 }9 ?9 N) @/ [+ n& C if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0). O# _( C6 j1 i3 |7 i &&min>matrix/matrix[in])' n2 h2 K1 D- M9 H {1 H3 B8 @* ]7 Z& y# ` min=matrix/matrix[in];5 i3 I' ~7 i: g" q6 j2 @, N$ W& c *temp=i;+ w' ^! h7 A+ t4 y. M# X, S }: E* f4 r H. \1 h9 F. D; P8 E0 v4 h for(i=0;i<s;i++) ) ~ ~% g b; e) m$ ` if(a=1&&matrix[*temp]==1)6 B& u/ y$ S8 g) v* b% e1 b6 r( C# M return i; }/ V1 I+ S8 u- d8 o2 a, P. J /////////////////////////////////+ |0 C7 j& m+ {, T: B% @ void Mto(int in,int temp); K Y7 v2 J! W7 M3 m, u {/ Q( Q' ~. [ o2 e* r6 S( m int i;( }/ J& @/ |2 ? for(i=0;i<=s;i++) # N4 V: r1 z% p6 \ if(i!=in)$ X5 _. `. X6 m1 E" r! I matrix[temp]=matrix[temp]/matrix[temp][in];) C2 H+ d* n9 V. ^ }4 j matrix[temp][in]=1;/ P. p, H( J! y! d/ B } ' t$ R5 w. E' }" J$ \' h/////////////////////////////" V$ l1 u, _; K void Be(int temp,int in)//初等变换 t3 i3 c* X$ J g! W2 o {% u/ y2 V6 T2 H# w7 A7 i; I! [ int i,j;$ u' X) t3 G# Q8 _ float c; 9 o5 r# k: t% g. }' g0 q for(i=0;i<=n;i++) % g' p# |5 y E/ p l { / L1 J) k2 \! ~2 c3 B* L c=matrix[in]/matrix[temp][in]; 3 L; F" _9 Y" h4 l+ Z if(i!=temp) , U9 E( u7 X. J5 \& a( I for(j=0;j<=s;j++)2 U* i U( [( ~ matrix[j]=matrix[j]-matrix[temp][j]*c;& ^+ n& R* p* a5 v8 L! V7 C! v } 6 k7 s4 q, R( z/ @2 }9 e: G} - n8 o% \+ Q+ u( f9 x- @* A//////////////////////////+ \. o0 o3 @% t' i4 y0 G ] void Achange(int in,int out)//出基入基转换; F7 Z8 G+ Q* l { 9 S: q! H! `* r int temp=a[in];0 t; f/ T; ?1 W, p a[in]=a[out];; Y+ g. {9 @& d/ a F a[out]=temp;: H, r5 ?% \) D* F& x3 |* B+ Q" \ } & q: ?4 |8 h+ {//////////////////////// / H2 q; u& E6 r, q. D5 _& ~% `void Print() / r* T0 X6 B" H% U9 ^{ ' @/ [9 C+ v R% Y/ z$ j int i,j,k,temp=0; , [/ x6 J2 E( I8 k$ O7 Y! L for(i=0;i<n;i++)" H+ G0 d/ Y5 r { v9 Z( ?4 d6 v' L7 B for(k=temp;k<s;k++) 0 c' d' p& } W, e if(a[k]==1). o) P* U( F; \ {, K- X% G3 V& a cout<<k;' J8 I; T; T0 C9 ], O2 a3 Y temp=k+1;& m, h9 m- n4 e. O4 i. r9 f' |5 Z k=s;; y% @" S* V% _( Y7 O' }8 x } 0 L. t# b8 u9 y+ F& S! ~/ t) n for(j=0;j<=s;j++) ! ~) C: t* }; e* e: H6 I% f' h cout<<matrix[j]; 2 m2 c! ^/ p# b$ f5 X# v9 w cout<<"\n"; ; k0 y7 W( Q* ]& ^! R! Q, E( a } 1 D5 Q4 v7 u$ P$ _* d cout<<"Rj"; 8 ^5 S% |/ @9 k6 A9 a8 J8 a for(j=0;j<=s;j++)% B# e B( L) b+ W' `4 S cout<<matrix[n][j]; % `, J5 g: Q( C" Z/ E# r, ] cout<<"\n"; 8 I, k$ |$ h* M. S$ j/ Q}& S& v I3 v& q6 Q& Q& { ////////////////////////3 e# T4 `& ~: k( z" z void InitPrint() ! A1 E; a3 h% \7 l{ " a) p8 T' h- g int i; - L( E4 H1 u; N- y5 [" [& K cout<<"X"; ; x4 G$ Q+ b3 } for(i=0;i<s;i++) Y6 Y8 K o/ | G cout<<i;, Y6 _: N6 ?$ i7 p @5 D* O cout<<"b\n"; $ T2 i$ K# L0 ]' R! t! o cout<<" ";0 ^/ B& M, h6 Q3 B8 X3 ~5 F, D cout<<"\n";8 U4 D3 Q( u# h }! Y: C, Z- X: T( Y7 M4 Q //////////////////% x$ T7 ~5 J4 h' m. i( _ void Result()8 L! P/ J0 X: F: ~ { 3 v- X# M9 B% a6 M int i;! D4 }: S3 `/ l5 C6 K; Z' a cout<<"("; . w2 p4 O' D% L" Q6 Q for(i=0;i<s;i++) ! i4 S( E" w' l5 _ cout<<x; 1 D0 L; y$ g+ p' M% [ cout<<")"; ! w4 I/ ~5 W' h0 M Y! z7 i. j if(type==1)2 X$ C/ m! y0 r) R3 Q cout<<"Zmax="<<matrix[n];7 j r6 R* R& k* F" I+ { else cout<<"Zmin="<<matrix[n];% x. B) M5 i6 a: ~ } ' M" L; E# I. a8 d- {- x+ K//////////////////////" S0 m# [6 \7 q7 s/ { void PrintResult()6 q1 m1 {9 t" Q* ] { ' |1 `/ d H0 S1 _ R/ p* D' [ if(type==0) 3 G4 [( `1 V" V& {5 A4 c cout<<"the Minimal:"<<matrix[n];0 E% \4 h3 u5 M6 Y4 Z( w else cout<<"theMaximum:"<<matrix[n];$ g2 H* o) U7 |3 H2 Q9 q1 s: O } & N" w& G6 x- F1 D, g+ g//////////////////////////////// " i% O( v5 L/ Rvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 ' c$ W5 H; c% g6 J# k0 U! P{ 2 U, ] u8 o$ U& e! v" K& i8 i; j int i,j;; e( n& ]$ U: _" k# k for(i=0;i<n;i++) 3 e" T9 _+ V" N {: b- |" Z2 R% m: N" i for(j=m;j<m+indexe;j++)3 d/ T: R7 g. H' S3 g, U if(nget[j-m]!=-1)matrix[j]=0; 0 X' p, r* {9 ~7 z" ^& W( a else matrix[j]=-1;% b7 ]0 q, q- Z1 Z for(j=m+indexe;j<m+indexe+indexl;j++)3 [: r3 r: y" K4 `, X/ O if(nlet[j-m-indexe]!=1)matrix[j]=0; ( w! Q2 Y& `. c& y) D6 E# k5 i else matrix[j]=1;. ?: E. V# S2 L6 O4 b for(j=m+indexe+indexl;j<s;j++)0 @& S: ~+ M @" F; s& I; @ if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 9 U ?; H; Z, H0 q else matrix[j]=1; " ~* w& k! |* x" w- M: {$ D }; r7 p& P& k) [/ o2 l& i for(i=m;i<m+indexe+indexl;i++) # w4 ]' L8 t; Y0 J, Q matrix[n]=0;8 h4 @$ j6 j' j" _: T2 J. |. S5 { for(i=m+indexe+indexl;i<s;i++) 0 b; I$ s& F) ^2 D matrix[n]=100;* x* Q5 o1 k$ ^ matrix[n]~~=0; . \; B# x* `5 j}~~
) f8 M6 [+ i- E* M. ]
/////////////////////////// / }# c3 ^3 u. ^1 `5 a( B' Dvoid ProcessA()//初始a[]/ Y" J# _( k) O" m" q) w { & k: |& e" ^7 v int i; / s4 q, r' P7 s; u3 Z+ |; o for(i=0;i<m+indexe;i++) # j; c4 c# {/ A) I4 f" f a=0; S4 \) [+ {6 I8 D% e for(i=m+indexe;i<s;i++)1 l4 K: U4 R4 V0 b2 s( } a=1;+ c" b9 Q: p Q; { }
( f( P0 @8 c6 E i* p- H
////////////////////////////////# A. J$ H! Z) J9 T& h. } void Input(float b[],int code[]) 6 [7 ~8 G4 V& A/ o( |. ]2 U% M{ % v* q* }+ i5 Y7 e# M, v5 ^ int i=0;int j=0; U/ l# A8 ^5 ^3 E2 J cout<<"The equator variable and Restrictor\n";9 x" B2 h9 E" h6 [6 C cin>>m>>n;; D* K+ w9 F* a: K4 C, C7 e for(i=0;i<n;i++)- ~& d: J2 F1 w1 D0 \ {* t7 s O3 c! x4 [% R* g5 X8 A2 O cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; o, T* R/ p# }: \$ D) o5 O cin>>b>>code;$ ], V* B; r& s" b! b4 |7 a cout<<"The 系数 \n";. z6 D- a4 p! i" b) T" j! k/ y5 ^ for(i=0;j<m;j++)9 c" Z1 ?$ h1 X! R! F! ] cin>>matrix[j]; ( ]4 K7 N4 Q! j! `. B( @, J5 j }4 j5 v& }2 [/ p; C8 P6 c! h cout<<"the type 0:Min 1:max\n";( F* w3 d* Z! L" u: f7 j do{! Z! p, P/ D5 K! y( T cin>>type;' u& j2 ?* Z* [$ |! T0 l/ p7 C if(type!=0&&type!=1): ^3 B/ m8 j# |* L, M9 I6 J; \4 N cout<<"error,ReInput!\n"; , L/ c+ H$ Z7 G1 r% R }while(type!=0&&type!=1); 9 R! X7 Q9 N2 y( V cout<<"the Z\n"; ) ]9 d' Z9 t# m6 j- H for(i=0;i<m;i++). i1 o3 F$ n4 o% k. N9 y cin>>matrix[n];; |6 \9 U" O( T/ B if(type==1)8 }5 I1 P# y# P5 K. d3 z4 y0 T for(i=0;i<m;i++)1 q$ ~6 l. n* j matrix[n]=-matrix[n]; - t* o( H' A, r: K# B}
/ y4 g- B& {# \" z0 y# E! A( g
$ M$ R7 Q6 ^8 C- ]6 I////////////////// & e4 g* x4 K, m0 J4 L void Xartificial()//消去人工变量 / o: w/ p) F& j8 N/ {1 i1 o7 a{ 5 i( a0 _* X; x3 r int i,j,k;) h) q# A4 j1 X, m/ H) R) n' |& d if(indexg!=0)2 i2 J2 K+ ]( e8 b: Q) O+ n {$ F+ A w" m( I for(i=m+indexe+indexl;i<s;i++) ) `- o% v) i: y4 v* `7 o9 n {3 a; T; v, |: b: G; U for(j=0;j<n;j++) ' K7 H* b* T: I! I if(matrix[j]==1)$ c( _% L8 ^- h! |( b2 A' V {2 @ K' J6 |, m+ _0 |. Q: H for(k=0;k<=s;k++) 8 }; K3 A/ _2 @8 @6 a: D matrix[n][k]=matrix[n][k]-matrix[j][k]*100;; f# z1 K8 a F( |. I% m j=n;/ b5 C1 A9 A0 _) [' g; h }, G$ g/ w1 Q; Z& F8 B* a# [ }* p, ^4 D. o5 u# E( h+ u) F9 _8 f }3 N) s1 z5 _: G9 |' I1 l }
' V6 K$ B1 C, }7 S& K4 U2 ?" Q
//////////////////////////////////////////////// 2 n# i% T+ t9 F& {% \' fvoid Process(float c[][100],int row,int vol)% z- n- a3 P7 b m o( c { & ^; e0 G$ [3 k& v1 c int i; " L8 {8 p* @2 Y& L for(i=0;i<n;i++), M& | }# p# j if(i!=row)c[vol]=0;. [* u* R4 P# Y) J2 P1 z+ a } $ A: S9 x% m# s" S! @# h( u////////////////////// # z' d# ^1 A* h) t, a& G2 v8 P( M& tvoid Start(float b[],int code[])6 v9 A% e* E b: x% i {5 ]6 _+ F4 I9 M! h( {0 ` int i;8 Q, \2 d2 ]' i0 ^1 s, z' R float nget[100][100],nlet[100][100],net[100][100]; 0 q1 i2 ^" J5 R indexe=indexl=indexg=0;* o) {& r: T9 J- y. Z) j2 P for(i=0;i<n;i++)0 ^( P; r( A1 X# L7 U8 X { / ~/ X% @/ ]* V8 r" i# Z if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} o3 ]" W+ s1 w; R) ] if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} ' j2 \, [: [' ]6 H# _6 c if(code==2){ E5 J' j# }2 ^ _( k- W# }( r9 j net[indexg++]=1; 8 m4 E2 s: O" N. {! o nget[indexe++]=-1;1 ]8 X9 u; g4 k3 @2 o1 e2 W% j) g Process(net,i,indexg-1)rocess(nlet,i,indexe-1);0 l. u3 T) ]* Y9 A z7 h/ c! i }; b- C l/ e+ r6 x) q } ' b7 M) M" i( ? h% F4 B" l s=indexe+indexl+indexg+m;, @+ a l$ \8 A. x1 s3 _ Merge(nget,nlet,net,b); ( u2 S' c3 X! `9 d3 ^5 K ProcessA();4 Z+ y Q+ Z8 P7 q' l InitPrint();# K7 `- h2 u. {( v, j* \ Xartificial(); ( ?, W3 u Y; i8 \) s}
9 \7 u, O8 D7 P2 p6 D% Q
void Simplix()//单纯形法# ?: t! o9 Z. P6 h* k1 { { c% u4 `9 r W int in,out,temp=0; * O8 V0 g' J1 n: Z5 [& N while(1) ! l2 _* \' k; P9 |' ]/ Q {; s ?9 z+ ^: @; ? jckxj(); ( _& f5 L1 @1 _7 E7 ?. e Print();; H. p* T' C; P Result();! F& y& L k) P* h% a" h if(!rj()) in=Min();" ]8 w" v) K* X: W/ E else{ d- |$ d9 w/ ?9 n if(indexg!=0) 6 T& [- N4 r( @& O, ], y JustArtificial(); 1 r3 d( i: a, Y& j% o PrintResult();! E1 }: G+ C+ W return;$ {1 S. a' Z* P } & a. g6 h/ K+ ` if(Check(in)) " R8 S! Z4 c9 M% A0 Z5 J { 0 `: p- e& S- q cout<<"No Delimition\n"; 6 M x$ t) _$ |4 m, Z% N return; $ f/ I1 T" B) @( S/ P, \ }( b+ A* k6 |1 m" j ~) Z% @8 P4 } out=SearchOut(&temp,in); ! m( \6 r5 q& C* Y Mto(in,temp);# G6 c: ~2 \2 O2 k4 e Be(temp,in); . Q5 t' r" S3 e9 L Achange(in,out); P' E( w& B* B' P }" E3 I' l; a* c- b# ]- k* x# ~1 e% E }
w% ?& Q# ?7 o% O* |
void main() : N$ J6 Y0 M4 C7 x. t1 e{ ! M0 ?& g8 H9 U- P& n int code[100];//输入符号标记& `. ~! J- n W! V) F float b[100];9 Z% j( V+ P: M5 K% V Input(b,code);//初始化9 _6 D$ B& |; q/ e9 @ Start(b,code);//标准化行 `% @. | `- w; X( f0 @ Simplix(); & ^4 `8 [2 b* h7 ~}0 L5 U! z, Q4 x