单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h>8 e( E8 v" O( X; q2 Y& K5 { #include<math.h>' i7 @' G* D: g9 M- T4 s& H# o float matrix[100][100],x[100]; $ ]; s4 R- ^& p2 S" W) Y# vint a[100];1 r6 O% |0 Y1 S3 h) N int m,n,s,type;" a2 U( K( W. E& O int indexe,indexl,indexg; - x, z+ u5 J. b$ A; d* T///////////////////////////////// 6 ~- K: D# b! pvoid jckxj()//基础可行解 3 I( Y- x2 t0 V' _& i{ % S/ X5 n/ }/ a. U$ I int i,j; ' N& W4 r8 Y( i2 t7 J" I7 [: J& l for(i=0;i<n;i++)# e4 q' a& r0 y2 n# [ for(j=0;j<s;j++) 7 @) g, T& J* }9 u4 C; ^7 Q if(matrix[j]==1&&a[j]==1), ^6 ]! X- Y& c9 `% U { + d, R, Z, d! p) a6 s$ Q9 k7 g x[j]=matrix~~; & @7 n# w, Z0 ?' Z9 h j=s;" b H' D4 s9 l7 ^5 p5 }3 o6 \ }) _) S9 m7 S7 T H! S for(i=0;i<s;i++): j/ T. F: o: K" Q2 u$ A8 v% B7 k/ B if(a==0)x=0; + \; {: _: U& U5 m9 D}~~

6 Y3 w0 W3 h1 b/ s/ Y
int rj()//基解矩阵3 e/ D3 f$ P& n o6 l8 U {& x0 y' h/ W! a/ t int i; ( e0 d; v) S) m9 C0 p for(i=0;i<s;i++)$ A7 V- C* \( f/ A( B3 Z if(fabs(matrix[n])>=0.000001) 5 S& v, v0 h" n1 r! J if(matrix[n]<0)return 0;7 I7 d. O5 ]$ {/ E7 q return 1;' Z P) k% ^. q } 9 n. [8 a& u5 \4 f/ W& y, Pint Min()//求最小的 ! p. @) G- z% N2 _$ H/ n{ 1 |, z! Z0 l2 e! v" i' k" j int i,temp=0; ' e+ s0 d" s5 \5 K% U3 } float min=matrix[n][0];/ @! D- k8 y1 [' R for(i=1;i<s;i++), K! G4 z: `7 m( Z if(min>matrix[n]) 2 d, j" |, _0 n4 Z {- ]* l0 W. \' w7 d6 a min=matrix[n];+ ]3 p9 }( @& ?- Q: }4 n temp=i; / \, Q: G; ?% y } 6 Y7 l. c( h4 v/ k$ H' |% l return temp; 1 {- O8 }6 g3 q4 m$ B L} ' k* P+ X% ?0 B. D' N v* y///////////////////////////////// i4 O* J1 h/ ~% x0 f$ M void JustArtificial()//人工变量9 u$ Y9 Q& h( [/ b+ s* @! L { . L! z( x+ }9 X) Z int i; - X- b0 b! t/ P for(i=m+indexe+indexl;i<s;i++)7 x' `# }* A- x) s if(fabs(x)>=0.000001)6 Y" H/ Z3 e/ U- M2 g6 X/ q, v( k { + ]2 K- v' x8 B/ T1 }+ P' G cout<<"NO Answer\n"; 6 |7 I4 p( i8 V/ }$ W return;4 d$ ^5 _' q% c6 L8 \( i. _ }1 V Y4 q6 O! w$ K7 W5 Y }8 t6 R+ [( @2 a- d ///////////////////// + k* p% c$ P" jint Check(int in)//检验, q9 |/ @/ Z* `- D) i {. m5 O5 f i! B4 k7 k, B int i; . b: Y* B9 _. c! c4 E( r* n float maxl=-1;; {* T5 A6 g8 W for(i=0;i<n;i++)8 d8 h( k9 m* f, _5 b3 v h. V8 r if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])! @$ _* a$ H8 s0 l6 z: N! q maxl=matrix/matrix[in]; " D$ g/ |* K/ E" ]1 P& l4 x0 Z/ ] if(maxl<0) " N9 k5 c0 x; o& i' T return 1;1 J8 q2 O6 w7 @ return 0;0 B2 S3 H; x0 K% M0 B0 E1 G }( l0 S! K/ c7 u* N# o, @ r$ W int SearchOut(int *temp,int in)//出基变量) x; e# f' X0 [) P# C { - y D# X5 ~$ L% L int i;9 v5 H* H+ j* l Z& q4 S float min=10000;, f3 l6 `4 r" Q! ^( k for(i=0;i<n;i++) 1 x# p! ^* c. q& n, a4 \2 x. U2 A9 N2 { if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)' f- C4 F+ I2 T2 [ &&min>matrix/matrix[in]) ; A2 e% D' i1 S; u: n$ E8 N {6 j+ H2 u& P1 U min=matrix/matrix[in];3 F7 B; U# ^7 H *temp=i;' n6 M7 r; Q) R" f1 }4 B }7 p' y! {) b* z1 C( v g for(i=0;i<s;i++) 8 N4 C4 i( M4 O7 x if(a=1&&matrix[*temp]==1) 7 Q# a- q: p# [ return i;% s5 l, x6 G- e( h } % q1 j; h: t9 I4 W* n; f% z% w///////////////////////////////// $ k' x) o, A/ W! P0 T3 S- T2 o( l8 |void Mto(int in,int temp)0 t* z0 c& R; i+ E, Q6 b% l; P/ Z { - s. @$ x, P, l* U# a5 {) e! H int i; ) K! q \7 }% c4 [9 p& I for(i=0;i<=s;i++): J) O5 ~1 l; s, S# H/ G if(i!=in) 9 b$ _! u4 r- ^* c3 O: W matrix[temp]=matrix[temp]/matrix[temp][in]; 2 b: e/ Z2 P9 Y/ Z2 O) F matrix[temp][in]=1;% p& v4 y1 C& c+ G9 j } ) N8 ^' w P' p$ r; u) |/////////////////////////////$ t2 V4 o0 T1 s void Be(int temp,int in)//初等变换. \( B9 n5 X. y; M8 R {, K- @! |" Z/ _$ X int i,j;2 ^, N: {8 a9 O( ] float c; * X: e2 y2 z7 c6 _/ A for(i=0;i<=n;i++) 4 V% F3 _4 t2 g, Q {2 e0 m6 j& |1 N9 d; l c=matrix[in]/matrix[temp][in];! u! N+ g( D3 [% Z if(i!=temp)" ] M( [ i' x# t for(j=0;j<=s;j++) - \: ~8 q6 u' w' B' ^( u1 @) y& ~! T matrix[j]=matrix[j]-matrix[temp][j]*c; s# k, q' J9 G- ]9 x }3 l$ c9 T2 [. X2 _4 S& R- P }1 S! Y4 h! x" o& A( z# l( I /////////////////////////// A( {; N2 N E" z; G5 o { void Achange(int in,int out)//出基入基转换9 L, n9 E% o& b3 y j { ) s( s* Y/ k4 F I6 _* r1 S int temp=a[in];/ {9 f3 u0 A& ]% c/ z1 V a[in]=a[out]; ; c. c( N$ A8 {+ y/ g* ~3 t a[out]=temp;7 U" z; f3 F% Y5 P }7 J# [7 H7 Y" g# P ////////////////////////' E$ l% l6 h9 ~- q, R, U7 p" Q1 I' R void Print() 3 ^0 u0 l B0 o2 F1 e; v& p- t3 q{ ' _' i4 l0 S5 X! m0 U2 q int i,j,k,temp=0; $ }# W# s0 j2 k: d3 n1 v" {) s for(i=0;i<n;i++) { 7 E) I" F* N: A" |( k5 e) [4 R for(k=temp;k<s;k++)3 l! [8 o5 Z1 a0 Z' A8 q6 r: u5 R# S if(a[k]==1) 1 t+ [5 d: a. ]1 g {% J" X9 H e6 A" _; I cout<<k; 3 ?' }; e# `0 E- B" ^% j! h temp=k+1;+ C# j! ?& s8 L% t- M k=s; ; @" p! }7 x2 U7 e- ?+ e }5 C' F+ i% Z+ Q& ~$ Z for(j=0;j<=s;j++)' ^: x: _! n* ?2 x A! t" g( y! } cout<<matrix[j];& _9 v4 b' [' u |% f7 a( Y6 v" {. \9 z cout<<"\n";6 x% l* d5 H5 N5 w# I6 g } 4 j7 y! K j, ^, Q6 w; b) H; o0 e cout<<"Rj"; 2 N/ D- n& _$ S& H0 J9 s for(j=0;j<=s;j++)9 N) Q+ ^$ I( {+ V$ o3 E cout<<matrix[n][j];) y4 S K5 V: J cout<<"\n";5 w% n" q: l3 C5 \ }, M- O4 r! \2 c0 \/ @- C- f1 w3 D ////////////////////////( I$ Y, n2 k* z: D( r6 B void InitPrint() " P* M2 N4 `" ]5 [' c$ ?% W{6 o( _& @0 E' h/ d4 P5 w5 V, v1 G) t$ ^ int i;/ [% P: v4 ]5 t5 ~5 g cout<<"X";: A. t% y$ f( m. b7 Z% N for(i=0;i<s;i++)7 v# k& _) i' |6 x cout<<i; 8 O1 ~ |! o9 Z: R cout<<"b\n"; 6 `* W5 x* n- b- N8 C; r cout<<" ";$ g" V0 j; m# v/ d! X cout<<"\n"; ) t" ?8 {. Q1 C}* q! r) t3 a) d$ s3 D //////////////////* e+ q+ o" B c) Y# `- |, P/ ] void Result() Y/ T; g5 j; @1 T! U {" Y4 j! ?+ j4 P% j int i; 8 j0 j0 a! `3 T1 l6 U cout<<"("; - q0 D8 |; { b, f for(i=0;i<s;i++) 4 `# i4 Q. v4 k* N+ \. T ] cout<<x;$ ~6 s% p `3 F$ _ cout<<")";4 L* v; H% Q2 e5 ~$ r" B" Z if(type==1) ' M; u* `) V& k, d5 Q I! F! I: o cout<<"Zmax="<<matrix[n];9 p* w0 [$ A8 W1 h# s else cout<<"Zmin="<<matrix[n]; ) ?4 e2 n! F9 Z& a/ K1 q} % d {% }" J" P$ ^5 E//////////////////////+ R5 N# ]. |. p* S; N& _: @) w+ f void PrintResult() 6 Y& {1 ]! h r( X5 S- |0 x{' P7 W* a( F5 L/ ~4 V% Q if(type==0)5 ~ p3 T8 \ g; }; h5 I/ X. y) r cout<<"the Minimal:"<<matrix[n]; # G$ S8 R( K2 [8 X3 ]# y else cout<<"theMaximum:"<<matrix[n]; 2 }% R9 R. k, ~; h) W} - @. n% L$ {% b3 I! F' W////////////////////////////////3 k, @& k# J( F+ }1 h void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并) c2 e) ]3 F% y {! w! z7 @) g5 n$ o$ W- m int i,j;& q4 i1 Z' S) f% K" [; u3 }0 M9 g for(i=0;i<n;i++) $ X; t. T. _7 y0 X! R b# ~ m { ! d9 t/ t/ N; x! Z2 t2 y: w for(j=m;j<m+indexe;j++); e( N* U( M" J2 E if(nget[j-m]!=-1)matrix[j]=0; : O4 |3 M A! n- `9 j9 J else matrix[j]=-1; 4 N; o4 o! ^# ^* s$ \ for(j=m+indexe;j<m+indexe+indexl;j++) ) Z- I, W2 n, S" | m) R/ S if(nlet[j-m-indexe]!=1)matrix[j]=0;1 Y+ H# _4 [% K9 Z4 R B6 y else matrix[j]=1; " Q8 g- d$ c4 \$ @ for(j=m+indexe+indexl;j<s;j++) ; L; E2 U: u6 S' h: a. o" W; U if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 8 |! ^- }. o: E# @1 ~# j0 ? else matrix[j]=1; : f- R! v5 ~. S } ) _# Z: q( z: M for(i=m;i<m+indexe+indexl;i++) # B; S! }; j5 M8 \0 ^& M matrix[n]=0; ( L6 o. W9 s, [3 O for(i=m+indexe+indexl;i<s;i++) 9 N1 w) _) n9 {6 j matrix[n]=100; 9 X% \* o! R) a0 z4 {, I matrix[n]~~=0; ) u% `8 ^9 w/ r7 L1 V}~~
2 |- [" `2 v* @+ |/ K& k3 z: f
/////////////////////////// 2 |/ Y+ [+ ~2 c0 r4 _: Gvoid ProcessA()//初始a[] 6 s b8 t7 r( e; T{ ! ]( M7 V9 i" O; m3 w7 {% b) w: j int i;$ V- U* W. w" V* _+ o for(i=0;i<m+indexe;i++) # {7 ^3 N' v q1 t5 ` a=0;& L* u; p, M' u: Y% Y2 M for(i=m+indexe;i<s;i++) 2 {: k% x0 G4 D3 [5 V9 s a=1; 4 y7 X* G3 U. h' Z: L}
r. w5 t# @* M$ a8 H8 r
//////////////////////////////// 7 ?5 I9 q9 e5 [0 D0 Vvoid Input(float b[],int code[]) . z- c# m' ?( f b{$ V# G' H: D7 y0 \- s int i=0;int j=0;8 v% K2 o& K( q cout<<"The equator variable and Restrictor\n";& O2 j! Y" @% h, ^$ ] cin>>m>>n;7 A4 N( y0 r; g) G- [ for(i=0;i<n;i++)4 A3 L/ U8 a& V {5 W/ {- f. }9 g6 }' G" z4 q cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; A9 n" `9 Q2 w- U cin>>b>>code; ' X) }1 N/ ~8 e2 K cout<<"The 系数 \n";+ Z3 r/ e/ r- } for(i=0;j<m;j++)# b; G7 G+ L( J" Q) B cin>>matrix[j]; 7 W6 A; A0 R0 d3 y7 x$ @5 S8 T* H }, n* w5 H4 y) K- K cout<<"the type 0:Min 1:max\n";. w; B9 @. w, K9 A5 K5 ~ do{ ( p s$ | D2 V, @ cin>>type;1 ?4 }; f8 ~, |1 l if(type!=0&&type!=1)1 S4 N+ a* Y$ s cout<<"error,ReInput!\n";- A n, o( q) Q: f }while(type!=0&&type!=1); ) k: B* ~* D6 d0 p cout<<"the Z\n"; . d5 M/ `; m( G for(i=0;i<m;i++). W: a( u: P# b* E# H. m- c4 t cin>>matrix[n];) f& C( ~3 M5 l5 | if(type==1)- n2 F: f3 l3 n* ?+ D3 N for(i=0;i<m;i++) " }+ k0 T' ]: j0 C6 w) C matrix[n]=-matrix[n]; % h' ?8 u7 z+ J}
0 T. S2 J5 M l* p$ \2 ], \7 s
9 Q' [& `' y" K+ k: D3 X$ N+ ^////////////////// $ Q- `# ]7 D% h, i$ g: ~+ t/ _void Xartificial()//消去人工变量 ) K) h; s' B* G{, m0 ~; o4 O# f. O/ c int i,j,k; . L5 y1 @- s( J+ [' S K1 t* @. {+ g if(indexg!=0)9 n1 p; B2 c6 J- R7 H3 Q, { {3 d- U6 k4 m B) Q) i1 _% x for(i=m+indexe+indexl;i<s;i++)3 ?" A% b/ P$ g# Y' ?" d% d {( _9 s' \6 Z$ U' J+ E) {6 M for(j=0;j<n;j++)$ \, f( P3 Q* |( F if(matrix[j]==1) , F6 R! C9 w) _0 F o! P) F { 9 D0 C' s( O4 D1 n) z for(k=0;k<=s;k++) + Q5 Z, f$ L4 r8 Y1 o" v2 g matrix[n][k]=matrix[n][k]-matrix[j][k]*100; o9 n. u2 Z& |4 L3 w1 R6 B j=n; " g3 P2 {* Y3 |6 T& R; m8 s# k# V# q } 9 |. q) n5 k. _8 o; O% P* [% D/ A& X6 [ } % @. a9 \, y" r' g* [9 k }8 f' @+ {5 h% J" d$ \' o" _ }
2 { `" C, r+ M/ |
//////////////////////////////////////////////// 4 D3 k5 y; Z+ Qvoid Process(float c[][100],int row,int vol)- [+ E: [, U9 D; y( Q { + o% Y) M. P' L9 p, O int i;2 O6 I$ y2 L( M* s; g, c( A# L( K4 k for(i=0;i<n;i++)# O$ P) B* y8 Q4 B if(i!=row)c[vol]=0; 2 X$ u- a( }2 D} # p* o! {: d9 P////////////////////// 5 i# c6 v$ F$ W3 a8 Lvoid Start(float b[],int code[]) 3 _! g+ {$ v9 l{ p+ `+ y1 |! v( M int i; 9 H' c2 b- P5 G% |$ N" B float nget[100][100],nlet[100][100],net[100][100];! R! p: A+ ?5 U8 \+ _' ^: H indexe=indexl=indexg=0; . \3 I) M, U7 t! e/ f& G5 J8 M% ` for(i=0;i<n;i++)6 Z- V# k- q* `9 q8 [8 m9 a9 p; V1 N { 1 m5 ]: l% P( s( V% p* | if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}' c+ Y9 H- M& t* C4 { if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}! l+ ~% P: C3 F: C H* T if(code==2){ 2 q/ r, n- D0 K! { w; Y7 F net[indexg++]=1; 4 A; H: _) o& [" o nget[indexe++]=-1;8 b# y- d! q! ?$ d Process(net,i,indexg-1)rocess(nlet,i,indexe-1);" q% c( J. f- s, j. f% ]: I9 x }* O" w" r2 t! O' D7 Q. x2 x; Y }+ d# r" z. Y" x- B0 V$ b3 C s=indexe+indexl+indexg+m;, B$ J2 f: f" Q. K9 F Merge(nget,nlet,net,b); % s/ e" N# m p5 H5 ` d( @ ProcessA();8 B0 x1 ]4 k6 ?+ K" f) k, U) O InitPrint();: c5 E ]3 K0 Y Xartificial();0 y f. |2 |9 ?) x' d5 f }
$ R4 [& _9 {9 y- [' ^% Q8 Y. d
void Simplix()//单纯形法 3 U% W$ b/ x" b' V4 g1 {' I/ ~/ ?{7 W3 `9 ^( @) X$ G9 C" g int in,out,temp=0; " G3 q. w; \, T9 l8 o while(1); G/ l! ?; z+ B { ! L! ?% k. H* X jckxj();1 N0 g) ]4 W" S5 x Print(); & |9 V8 @4 o8 N6 |" L" i3 \: f Result(); . E) b3 ]0 b0 M0 i if(!rj()) in=Min();3 O: I' c" Z2 E3 ^ else{ , a1 \& F/ T+ ` if(indexg!=0) ; \; v) N+ q* F JustArtificial();. u5 Z6 s, x/ Q/ \$ s2 C/ L0 [6 ]* I PrintResult(); ! W, _& i! \+ ^" V. w* j$ v, z- ^* _ m return; 7 e4 K/ R" [7 k' a0 [# {& S! y0 Z% n }& M4 n6 `7 e/ s if(Check(in)); N K- o! {* {% S- l/ `7 H3 W( P5 V { 6 G2 O8 J: A/ _. B cout<<"No Delimition\n"; ' h8 K" ^: M0 L3 D$ g" ~4 I return; " D$ U% u3 c1 D5 C } ; m5 O/ O# X1 I- e out=SearchOut(&temp,in); v$ Z7 J& P. H" f4 u2 q Mto(in,temp); : t% ^! W7 t; y ` Be(temp,in);; v/ n @# B; S4 c4 j5 M2 O' Z) d6 L Achange(in,out);% K7 Z/ a: V# T( Z5 `2 ^/ R } 2 A' O' N: P( v5 {1 m! t& ~! a}
' Q, ~; a- f2 z- `' K( d: f1 S' h
void main() ) h# R1 E- u# Q, S) y3 l; ?{1 b: f% o8 E+ g, C) a int code[100];//输入符号标记/ A" [3 @$ n1 O float b[100]; ' {3 U8 [, x! F. H! m2 c$ O* q Input(b,code);//初始化6 |5 @2 Z6 a! t. x* _( v0 Y7 _% d, r Start(b,code);//标准化行7 a& ?! L6 n5 O Simplix();. n) ?6 a8 {) K } " L8 U ]$ x. r