单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> : q2 G1 j- g# W; X" I#include<math.h>1 c! m# A! {: ?, s7 m9 e float matrix[100][100],x[100]; + h; W9 X3 L7 b& k0 ?int a[100];. a9 J5 T: O7 Z8 o4 J int m,n,s,type; 5 c' y2 H- T* k! T2 j, z- v7 oint indexe,indexl,indexg;/ J4 k. K7 p4 A8 [: R ///////////////////////////////// 6 F) l6 b: z8 @/ o6 Jvoid jckxj()//基础可行解2 L! w' z e: W$ F$ {* S { ! E: v+ W3 V- j0 x int i,j;8 p, w' B: _6 g4 B& D# a7 Q: d' ?) N for(i=0;i<n;i++)9 X" _- Y" E9 ~$ o3 @% D9 d; Y for(j=0;j<s;j++) 6 b% _8 k! K0 e: Z" L2 x( Q: ~ if(matrix[j]==1&&a[j]==1) T1 @- n, g, f {+ Z2 B: |2 s. T! y; Y: r3 O x[j]=matrix~~;9 e3 f1 j8 l0 y. r j=s; , R) V4 |# P! K3 l } $ B- u+ b1 E- n2 v for(i=0;i<s;i++)4 Z3 q. S8 D9 n) d/ t* {# O if(a==0)x=0; ; T$ z8 b& \$ p; e: D6 K}~~

! V1 Q) X& s3 V0 b8 D& n
int rj()//基解矩阵: y& B" Z9 M& b2 K9 E- a* b { : g$ @9 h$ v: F! `' p8 V% ~ int i; {/ C Z8 b9 x% H0 q2 ^ for(i=0;i<s;i++)( ^; U0 @+ e3 ~+ T, Z4 r( }( Y9 M, P1 M! { if(fabs(matrix[n])>=0.000001)) y* x* `$ `" J5 l, S7 T if(matrix[n]<0)return 0;* z% h; M; d) _# V return 1;, |0 s" c7 c; }' P }# g8 a$ g# L' W/ U e int Min()//求最小的 ; `- E( e ?& p) i4 J{: N: @ E2 ]5 o0 f2 ?3 P int i,temp=0; + X9 l# N8 m2 U% C4 ~4 J7 a2 i float min=matrix[n][0];9 G# J1 Q* {" I for(i=1;i<s;i++) : ~/ X' `5 S: y if(min>matrix[n]) ! G* r1 P$ M- f2 e! w/ d { J1 \: E3 n; q- W+ @% ^) N- U min=matrix[n];, p2 I4 {- E: L temp=i;4 R# w* p1 h: Y: e# t, g5 C& u } # L, V5 C* K/ ]. x, Z" } return temp; 6 r& }4 }+ h# m6 R3 b} |& w; Q* A8 x+ i1 d2 D///////////////////////////////// C; u u8 e# u( [1 t: F9 ? void JustArtificial()//人工变量) m- X: N) E H" O( Q7 A7 y( }. r {9 Z p& J* i) o: M/ O! B int i;# I$ l" @% }6 H for(i=m+indexe+indexl;i<s;i++)3 V* I4 x; z2 `' |) g if(fabs(x)>=0.000001) & h& @; e/ G3 p: F A" h { # Q2 O% f' h3 w# f' P" h6 k cout<<"NO Answer\n"; $ \6 T- y2 h6 Z& a, ~! ]2 Q X return;6 `. ` e( @/ W& Q+ A& M: ~ } % n' h' d& B) C+ A} + T9 `, Y) x; i( c& {; y# k: B///////////////////// # E" m$ v4 d. r" K2 Z" L9 V3 yint Check(int in)//检验 : r$ _) k5 s O{ 9 W% t k3 ~8 A5 A int i; / e% ]' m+ p* R- e( Z5 ~5 s float maxl=-1;0 M1 k4 `. J( [ for(i=0;i<n;i++)8 I6 ^: R$ ^( Y6 S. y if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) # \% n# J- p3 M5 a maxl=matrix/matrix[in]; + p5 l' Q% r( z7 D! R4 t! _ if(maxl<0)1 m4 @5 X. Q; h% t V; e return 1;7 x j' Z g& d+ W: t return 0; b6 I8 I% U K9 b }* S, c2 H2 G& p$ T/ }' _ j int SearchOut(int *temp,int in)//出基变量( g* _) B; i& n$ m) M/ [! ] {9 X- j. W x) B* P int i;$ ]. ^1 M6 R; D! r- h: J float min=10000; 9 B5 Y( { J8 f! t; |' C for(i=0;i<n;i++) * c/ S0 A4 w$ S0 o if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)( ]5 a1 |7 j) [+ _# l$ @ u &&min>matrix/matrix[in])* z5 s. Q3 C; `3 s4 R$ G { \% P. z* u+ t) ?) w* S min=matrix/matrix[in]; T/ K$ \1 z# L) e a *temp=i;! A0 ?; ?2 }1 ` } q* ~+ {# H$ z& | for(i=0;i<s;i++)$ X! `3 R+ _) Y, D; g- v9 M3 { if(a=1&&matrix[*temp]==1)5 i% q5 h% l w return i;1 ]1 b& k+ {* @9 L }7 ]+ x% P4 d4 l( l: S /////////////////////////////////" _; a( X: K3 {/ w }& e8 E void Mto(int in,int temp) 3 E& W0 C9 ^2 x{ : ~. U+ |1 O( C: ^4 m int i; ) Z4 p' {: @6 h# j9 K for(i=0;i<=s;i++) - I8 ~6 y: Z$ B3 d" B# @1 H if(i!=in)/ I9 ~) B' t+ U- j2 W4 Z" u% W3 f! m matrix[temp]=matrix[temp]/matrix[temp][in];3 d& |$ ^' A6 t! n matrix[temp][in]=1; 1 t( z9 H3 ^. x& `} * M4 ~8 o0 n- K" l$ ]/////////////////////////////7 P9 Z8 o8 [9 k: y9 F void Be(int temp,int in)//初等变换 . b4 I- L4 w4 m' H. I3 M7 G{9 ]8 f( q2 t* E: { W) A int i,j; ) O d% P7 m3 y$ @5 Q4 G& h float c; ) i6 B" W; c4 [ for(i=0;i<=n;i++): w; J+ i+ Y1 I% |) G/ l5 \2 r* ^; C {- s1 u% n9 ?' ^# a8 }0 Y6 e) E+ e c=matrix[in]/matrix[temp][in]; ; g8 f, |4 |8 p/ }* I$ m% p6 e$ i7 @ if(i!=temp) 4 D, \4 |+ ?3 [+ T* o for(j=0;j<=s;j++)8 Y& _: l% y3 ]) c/ n& k! B7 x matrix[j]=matrix[j]-matrix[temp][j]*c; 2 m' x# E' J# I } 5 F4 T1 A( `& I2 q' b} : K& r' A% h, H8 C* a9 f6 R Y! }//////////////////////////$ o- K v* e1 h5 v( F" D. u void Achange(int in,int out)//出基入基转换9 g3 J$ u6 l# v: z {9 Z, I- a3 ]0 K int temp=a[in]; 9 d) z+ Q+ K4 ]8 `- t1 T a[in]=a[out];3 ?* a) I4 l6 L, f' u W a[out]=temp; 6 \3 ~) {# P" ~8 h' t& Q3 ?$ [) [8 K}9 ?2 L+ E$ [* u c ////////////////////////4 c, ~: u) {+ g9 D8 B5 k) | void Print() 8 {; X7 c9 q! M9 t6 ~# D5 u5 o{ 7 q( Y& H) E7 o3 c8 y1 ~ int i,j,k,temp=0; 3 r6 C$ g! t' K0 y for(i=0;i<n;i++)9 q4 x( e. v& s% `$ Q {/ n8 b' a+ c3 g7 {3 O2 d( U for(k=temp;k<s;k++) D, B; Z, Y* `- x if(a[k]==1) C8 s+ {6 v4 n7 X# o$ [6 Z7 v {! `7 C( C# D8 P+ Q9 T6 `& d- X5 F7 N cout<<k;/ ] G, Q: @* n* Q# M temp=k+1; 8 h, ~' l' g% C5 g# J3 V: |8 h k=s; 7 o& C" l: E7 H. s } 4 G! z Z0 c' K2 i0 S( f2 ?. j for(j=0;j<=s;j++)) }0 O) y& |! T' k7 T } cout<<matrix[j];+ e, b% M7 }, f i N cout<<"\n"; 8 R! L/ s5 F% b0 e }$ R6 A& u) A. B+ N5 _/ a cout<<"Rj";9 s2 {% i1 D* V for(j=0;j<=s;j++)# a X' b% M' ? cout<<matrix[n][j];3 s- q: X. Z! I' a: v% q cout<<"\n"; ~: i2 o! `. n- A# b% }}2 V2 e2 V3 D1 s' i7 k2 d1 {; W0 r //////////////////////// / o! i, A9 e, m/ r( M, @5 tvoid InitPrint()! I! V( P k$ U" D {8 Q" w6 D% v- ~ b int i;5 W1 b' u j" F. U2 W cout<<"X"; $ C2 J# G0 X" F7 e5 D2 X7 r for(i=0;i<s;i++). P5 F0 x% t3 N" x cout<<i;9 O g( \8 c% ^7 n" q( b cout<<"b\n";' m; Q! f w: R* k, @1 \ cout<<" "; ; P" n7 n/ F7 ^( h cout<<"\n"; 4 b+ b/ b) H B% ]$ g9 `4 u} 1 K# r9 o \" m6 G) F////////////////// , U: Z# `' h9 U2 E% Y7 [3 pvoid Result() 3 G. m7 L* T5 z5 F* L{ S7 B+ t) \; y% h& {$ ]2 } int i; 9 t+ c& q) s, N2 O% c, o, U cout<<"("; 8 F5 Y9 Y; N; e$ M7 ?) ~- ~; C for(i=0;i<s;i++)# ^* J6 _3 C% \: ^4 U: a3 N cout<<x; 3 [: ~: m3 F& P3 K2 ` cout<<")";9 n" p7 n8 p: m% L: y/ M2 Y' O; A7 q if(type==1) 8 g h) K3 ] C2 s cout<<"Zmax="<<matrix[n];/ n: e6 @9 m- E# [/ [: Y; X( L else cout<<"Zmin="<<matrix[n];1 P2 e8 N; z+ t7 C4 |: y3 K' k+ D }- y ?% @3 I3 z- v8 I4 W ////////////////////// + N: u5 t. K+ f. v7 v7 I# qvoid PrintResult() % y' N( _$ K/ t8 e9 M. Y+ @{ 7 m. w- ?( { R* X" J if(type==0)+ B4 L! f- Z; H/ B cout<<"the Minimal:"<<matrix[n]; # P3 [ l, B1 {$ L, d else cout<<"theMaximum:"<<matrix[n]; 1 \4 v9 j& b' N}/ L0 P" T) \# [2 F+ ?# ~ ////////////////////////////////9 l5 W5 c& p8 L3 D4 M& Y void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 % X+ O* W9 }6 |2 j+ n0 A/ w y- C{ 5 X# a- w/ {, ]* s6 Z int i,j;' y2 p4 L S! M for(i=0;i<n;i++) 1 A+ Q* z( N; w { ( I" U6 A: E7 j% S7 A7 a) X) B for(j=m;j<m+indexe;j++) ; @# m, D9 s1 q5 L# b8 l+ m if(nget[j-m]!=-1)matrix[j]=0;# T2 L1 l' ], n else matrix[j]=-1;9 _% N) z% T% N6 x5 D7 _ for(j=m+indexe;j<m+indexe+indexl;j++)1 M% ]# H- d1 Q, r$ f9 _$ U9 h if(nlet[j-m-indexe]!=1)matrix[j]=0;4 P- [+ v( C; |/ B, R) W" U else matrix[j]=1; ) S$ A# P$ R4 H6 b5 e+ t" j; \ for(j=m+indexe+indexl;j<s;j++)6 n) |$ _( @! t if(net[j-m-indexe-indexl]!=1)matrix[j]=0;+ R3 @: o r7 O" e6 ~2 U# f else matrix[j]=1; % l8 @% D( F, A- u; f8 i2 Y }! G# R9 x/ _6 C5 B for(i=m;i<m+indexe+indexl;i++) , F e/ h2 L- e S5 }/ ?+ E matrix[n]=0; * b. b8 D6 [0 [( c for(i=m+indexe+indexl;i<s;i++). Q/ s" j! Q# a6 H matrix[n]=100; $ C1 J# H' Z3 l" F7 n+ E. a% Y matrix[n]~~=0;2 }* e: @5 m$ p, q }~~
% t* R, ^0 i" w, ?3 u' C
///////////////////////////9 D6 j$ _# g- S; _ t void ProcessA()//初始a[]& s) i% Z2 {. t% c8 u7 d" t {0 v- h' z, \, @( j0 Y2 W4 b- M int i; , c- \* `0 {& _ for(i=0;i<m+indexe;i++) 2 n V8 P; a( W4 K# f a=0; & ~' v) u' Q( l& X* W5 B- b$ k for(i=m+indexe;i<s;i++) 2 N* q: }! q( K; c4 f a=1; 8 W4 K4 Z6 R7 n) y1 L}
* T. ?9 M8 _/ r% Y C9 Q
//////////////////////////////// ) D' A: Y G4 \void Input(float b[],int code[])2 o0 g! C2 [0 u; V! X1 J: K( ?& r+ M' r { 0 |( r3 [( Z' X, j" L( J: j/ _ int i=0;int j=0;# S1 K- X, j8 T# |& S$ U: I2 `4 v0 k cout<<"The equator variable and Restrictor\n"; , r: ]1 W$ W, A0 S3 ], }' f( J cin>>m>>n; % t" Y E8 _+ o& P for(i=0;i<n;i++)& ?% A, n4 |9 _" O1 U4 b {+ t& \0 _( c1 z, x. x cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; ' J+ u9 E6 I) z6 M& F7 \0 \/ R8 q" b cin>>b>>code; * Z1 ^" _0 \9 Y( B$ {, @8 Y5 w cout<<"The 系数 \n";: M5 M7 U5 O9 ~% B/ \( H/ A( B2 u for(i=0;j<m;j++) ; C3 l7 @) I- V$ s1 ^/ J cin>>matrix[j]; 6 i& B4 B: ?" t- | } 7 \1 i, N- v9 _' L+ @: n# l5 ? cout<<"the type 0:Min 1:max\n"; 3 ~' y- v* m& q# f9 W% E8 Z) k" F do{, ^/ `' h; U- s/ ? cin>>type; 2 B% q. y; N. [/ Y) @: a if(type!=0&&type!=1)* e+ h, j5 C3 T cout<<"error,ReInput!\n";2 U9 ~" L+ A6 `; O }while(type!=0&&type!=1);2 ^' c% r% R; _, I cout<<"the Z\n"; / z8 a" Z( A4 ]3 Z for(i=0;i<m;i++) 9 K I' n# h* f cin>>matrix[n]; & c& k; E% d$ a/ a1 G if(type==1) & Z) c/ V8 l8 R J- E0 v2 I9 a for(i=0;i<m;i++) 7 X& k% p$ \7 n8 K0 a: P Y matrix[n]=-matrix[n];4 T j3 l; w' H& u& S5 W1 n( g: I }
: k" k( h. p! @7 I" r b8 S& B
% X2 O q% z" P; W! D1 q& d////////////////// ) g5 {/ g4 m2 [/ F9 _) K void Xartificial()//消去人工变量1 J9 f! f" N B/ q( } {9 e I$ u( h0 J# q3 F int i,j,k; l, I8 i( Y4 b" A3 E4 q9 i8 f if(indexg!=0), I' B' R( t9 a6 j- S& B { + F) g1 [1 n2 U6 [8 y for(i=m+indexe+indexl;i<s;i++)1 @. o9 W9 O* E) s0 A { 4 A/ T2 b! ?' C( H$ Z for(j=0;j<n;j++)! ~& F8 T9 s% i. t3 B if(matrix[j]==1) ) J7 [# H- p% {) Z7 z; H { 2 F7 S; G* n7 F( H- J- d for(k=0;k<=s;k++)( \2 W$ f" U. R- n matrix[n][k]=matrix[n][k]-matrix[j][k]*100; 3 j) F F& [( c( D1 ~ j=n;2 A7 }8 e% A' p. J" y" e% T }( a4 Z8 f |5 P" L% F }$ l4 q, q' }6 J3 t7 K- F% i3 q } ( r4 w( p. i' R" r7 @}
8 S6 ?, Y, a2 _8 @4 o
///////////////////////////////////////////////// w6 U% ^% ^7 M3 D! | void Process(float c[][100],int row,int vol) g1 M5 J+ C/ _1 }0 m: u { ; P8 p. G" B% k+ F0 ^" W( [& I int i;# a a9 D# {! P2 _$ { for(i=0;i<n;i++) % D8 Y" z0 v7 f0 p8 f- o if(i!=row)c[vol]=0;: V1 Y1 ^. B7 U! @3 Z) I4 @# g } % H& @5 i0 H" n//////////////////////% ]$ g% B) w+ F void Start(float b[],int code[]) : L% ~. R4 N( y' p{ $ K5 m+ d4 d8 R9 Z9 T$ a3 z int i;2 w& L. o- H: U3 B5 \$ T) I/ Y3 e float nget[100][100],nlet[100][100],net[100][100];* S% ^% I9 |& I, f5 b indexe=indexl=indexg=0;7 x$ d' h7 O: B3 }9 ]) ?1 o for(i=0;i<n;i++) ! q& a) \/ K8 ^, m. q {9 s+ C6 ^: ]2 m: m6 ?. Y" N) r if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 8 g% y9 ~+ ? j if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} : w. {9 J/ b- }5 O6 b6 ^ x if(code==2){ $ G! S9 T( W6 _' | net[indexg++]=1;+ a' N5 W7 P( }% } nget[indexe++]=-1; - j7 g* B/ z9 ~2 u Process(net,i,indexg-1)rocess(nlet,i,indexe-1);0 B s4 A2 Q6 q1 F. f- x. b } ' z- u7 U+ Q/ b1 N( t }, H7 V6 v* J1 h7 O$ m s=indexe+indexl+indexg+m;% O: S0 s+ C7 {: R2 _; b V Merge(nget,nlet,net,b); ) o5 s! [9 g; A) F/ R3 l ProcessA();( a8 p* {; S9 P- p& e# Q1 I InitPrint();# b2 n- h; ]! l# T Xartificial();. t. r% Z [- G }
* k2 j) A7 @( @5 W" V/ b
void Simplix()//单纯形法 7 C- O$ S1 n# N5 N: |: p{/ E: b$ C# H# h' j. C- J int in,out,temp=0; ; m' f9 z. `# A* I* W+ ^ while(1)# d% ?( k: }. }* }( N9 L H' g {$ [ @* ~1 F1 Q1 F, ?7 S$ |6 l, d jckxj(); 4 v/ G% w" K& R6 X* w9 a& p$ G Print(); 4 s! o, B, w: {( z2 v Result();. N8 K: d6 c4 h" w# O- X6 m if(!rj()) in=Min(); ! ?* l3 B- j! R1 t5 _% {3 A else{ 8 F. l7 C0 H6 ?7 e% _& m if(indexg!=0), u" q# E, K) O- l: @( e; | JustArtificial(); # {9 Y q1 ]! A! `! ~ PrintResult();- O, U. y3 E6 ]4 ^ return;9 S1 e# H% Q+ U' T } ' W* L( F1 d1 w3 T$ K$ V8 @ if(Check(in)) 8 X5 y$ i: I6 I" p/ {: r# ` {6 B8 v |+ J$ I. ] cout<<"No Delimition\n"; . w' F" G6 E- W; @- P, |- V# @ return;- h6 m V# H+ Z } " B1 i$ z$ ^: A5 j m: }& H out=SearchOut(&temp,in);; C* J5 F O% ] Mto(in,temp);4 u' ]5 `: Q- S6 i Be(temp,in); + R! H4 H4 z6 {3 @ Achange(in,out); % M+ T/ _& Y* T }, E4 g+ X0 N$ A2 w [9 l }
. d/ Y& a d8 G
void main() ; p8 X, b0 {' g: C{ 1 w6 E0 |" D% E3 e int code[100];//输入符号标记 2 ~: I" [7 f: b' L' \ ]/ N6 ~ float b[100];, J' O* o' N. m6 J) X Input(b,code);//初始化) z c& r8 `5 I; m! t Start(b,code);//标准化行 c5 X7 q+ e. h i/ n3 D8 z Simplix(); 5 [5 X- _) {3 R" O4 j2 u8 }( Q$ i% I5 b} * k T% o- }) R: ?" f& r1 ^