单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> ; V/ q& X7 G7 [! X6 w+ Y#include<math.h> & v$ ^; }7 A& b! ]4 Q* kfloat matrix[100][100],x[100];+ |% E- n+ d6 I int a[100];$ ^0 N% k8 E7 C4 I5 W int m,n,s,type;, Z2 W2 j% q6 Z% q int indexe,indexl,indexg; ( N1 c- N; E' {5 u2 Y0 C! X0 q///////////////////////////////// " o7 E/ H2 S. Gvoid jckxj()//基础可行解5 N1 O" X( c1 p; b/ G1 b) \* t {% n4 F7 F4 G: n: G/ I# n2 V int i,j; / V+ |+ d- P8 x$ ~3 C for(i=0;i<n;i++) 6 v, i- S1 e% { for(j=0;j<s;j++)8 T: u( `7 ^! ?% T/ k, A& f5 p3 A, S if(matrix[j]==1&&a[j]==1) 0 u$ _; {' W8 D {/ {! h, w2 |5 g3 D/ i* L! q/ F. h x[j]=matrix~~;, q; T9 a# n8 s& ~- ? j=s; 0 K# R, t1 V- n% ] }; u! p I* u. s# ]" t% m8 S for(i=0;i<s;i++) 9 y( a, a' |2 X) V( ?; R a if(a==0)x=0;1 ^+ M2 }) _$ s/ |0 B }~~

7 O3 o+ R; L" M$ }! ^8 k! r2 l; V
int rj()//基解矩阵5 J8 Q: Z' F% k, E- U f6 N {) M# P9 G9 G( H# m1 L b9 a. u int i; ( O% k) O) @/ R5 |6 V: U for(i=0;i<s;i++) # j! p5 G9 F- X, H if(fabs(matrix[n])>=0.000001) ) F( P0 t7 B; b4 Q if(matrix[n]<0)return 0;: ~5 o8 s2 K) u; P return 1;( N7 O; ~& J! H, D- t) a } 2 ^% P) C K2 Dint Min()//求最小的# B( e$ M& y c6 G* D& n q9 k3 E7 W { 4 Y$ R3 i+ b; @ int i,temp=0;2 M! W# L4 x" O$ W* Y5 O- } float min=matrix[n][0];2 l: i% U% i5 N9 `. }: D& | for(i=1;i<s;i++)5 H0 {4 j' [' @/ L if(min>matrix[n]) ) \* C G) z! k, O% W {0 N8 ]1 |1 o) Q e0 x min=matrix[n]; O) w8 U/ ^% b. Q0 F temp=i; ! {) w4 ^9 b) v2 p. p0 f }* V) Q) T8 Q, I" U: K return temp;) c9 E* y( Z3 J, `, i }( s2 f5 \+ p' K. |+ U( w8 | C /////////////////////////////////" b, ?& x2 `$ j/ g7 c% B void JustArtificial()//人工变量 . H i6 q( G5 t! m; K{$ t! C& J2 T5 L6 y int i; - |# P3 n8 q' [ for(i=m+indexe+indexl;i<s;i++)' y! q/ ?2 `1 E7 H% ~ if(fabs(x)>=0.000001) ) n" y) T2 l" V7 z& _6 a# v+ z {% H) q3 u/ [- q* H$ m% E' b; _ cout<<"NO Answer\n"; * P/ d+ x: i7 y! C return; H6 H6 Q! N; ]: j2 x1 U2 J* O& z1 w }$ ~9 u( @: A& P1 n: A' N9 ^ } $ m; W! L% h$ A7 G4 r5 N! k/////////////////////5 L: b1 e2 I p* W1 Q int Check(int in)//检验5 l+ R# L+ O e' h {' `" N' F* _# B. M2 R0 h int i; * ~% W9 G" Y4 h% q/ S float maxl=-1; 9 E/ }2 B7 J0 ~# M7 v6 h for(i=0;i<n;i++)" S ^6 I' A, |0 Z8 {$ M if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) 6 G6 i8 K) T% M( I maxl=matrix/matrix[in]; 2 j% `" K' }- c, g if(maxl<0)# N# y! m# R; o/ g a3 {% T3 S return 1;0 T! m7 c+ j& ^! w2 R return 0;/ T. G! F+ l5 c3 R/ u }" S1 R5 h& S+ l. |8 K int SearchOut(int *temp,int in)//出基变量1 T* F! ]- Q0 {( {3 E3 ~ { 0 Z0 m3 o( h `1 D' `6 m2 j' w; B/ O int i; , l( Y! k& A, X: O5 y1 [0 I8 w2 t float min=10000;* L/ y' D3 \1 ` for(i=0;i<n;i++) ! q! D' \! x& K0 e- R' O* y if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 6 _( m5 c$ `- r2 c &&min>matrix/matrix[in]), v% G$ h8 b/ c1 k' @- ~4 u' C; m8 L { 3 J5 H" U3 J$ c) ?0 } min=matrix/matrix[in];: [, n- z G: o% U *temp=i; . z" n8 d/ g$ i } ( u6 |7 ]' {% }; x$ i for(i=0;i<s;i++)% g* h5 `6 o/ `; r if(a=1&&matrix[*temp]==1) : l8 Z' C. @- O return i; / c. p# V4 E5 n2 \}# m! p% G& T1 q: j! Z ///////////////////////////////// : w+ d0 N$ O2 q; P! z! y, ivoid Mto(int in,int temp)7 u6 v( _* ?% f- o& x* x { : d h8 i. Y: O. T, r! v& J- Y int i;4 n, }; ~- _$ A% l" I9 B3 b: i; { for(i=0;i<=s;i++) 4 \' F, v/ g( |+ V4 A' w/ M if(i!=in) : r# [# s G/ x) _- L4 n" y matrix[temp]=matrix[temp]/matrix[temp][in];9 @ u: D: J" W9 ]# c# B matrix[temp][in]=1;7 {; j- N% T8 U5 \3 K8 { } & ^- b# l8 c6 Y8 b F' T/////////////////////////////* I7 O2 j( d3 D1 F# ]' M# X void Be(int temp,int in)//初等变换9 C3 M" k: N h; ? { 3 c$ w3 x r( R# X3 Q' @ int i,j; 5 A7 H+ P. t6 O float c;/ x" h* ?4 N. J$ u for(i=0;i<=n;i++)2 o8 I7 F5 {9 L% v5 ~- f: T {) r- J) [; I. t/ m c=matrix[in]/matrix[temp][in];1 D4 [ j1 a" e if(i!=temp) $ X* O; x9 B) H7 ~, R for(j=0;j<=s;j++)+ l7 ~' ~; ~$ C/ x& v matrix[j]=matrix[j]-matrix[temp][j]*c; 4 d/ l( v! T. A0 j+ @" b' e }* w2 h4 z2 D+ f0 v g2 D& D" ?( q4 L }: F) J8 p1 U8 c: v- r1 j /////////////////////////// ]: [3 ? @- b void Achange(int in,int out)//出基入基转换; E0 c$ B; o9 T4 B7 ?+ D5 H {1 i# O3 m2 p# v) O' Z' A int temp=a[in]; 1 ^( k5 A$ k& A0 m a[in]=a[out];3 {! F7 p8 @' [1 Y a[out]=temp; 0 f; h0 a% n! g+ b}. f+ V, M1 _# i- @( L //////////////////////// 4 h4 K- C6 C, s# a1 j- Uvoid Print(): \0 l0 O- q: C { $ P9 k, t8 z2 s1 f int i,j,k,temp=0; , L; T. N2 k$ K. v for(i=0;i<n;i++) % R/ e: o2 H3 G% q! k4 v& {% U { 1 u+ H5 u2 p$ |7 p9 ?. W for(k=temp;k<s;k++)* E, n$ z3 e2 c. c- w if(a[k]==1)2 R5 i. B7 i1 r* O$ j. n { . P2 J- t) k8 E* K8 Y cout<<k; 0 j5 R8 ?/ z8 A* G' t! \' Q temp=k+1;: |1 z% A/ u9 a" S5 o k=s; * r; e) j4 X' \% _8 _6 q: [* M/ B: J }; d) {' @6 B' j; A9 Y for(j=0;j<=s;j++) 1 b3 ~ ~: d( _7 H; { cout<<matrix[j];9 A7 u( d# I1 \! I cout<<"\n"; 9 U- k# Z0 I6 E8 F }9 y& f* V: W3 R, ~$ R7 b cout<<"Rj"; 6 K! |( g) d, x: P* K1 C for(j=0;j<=s;j++) " m) @# G1 K# h& H cout<<matrix[n][j];0 E( g3 s* C( f, V! Y% k5 [& s cout<<"\n"; 6 Q9 ?) [) F9 O2 @4 L% H} ; {" R b# `' n$ }7 v, [+ l7 l////////////////////////! d0 S+ |* o0 T7 O- O void InitPrint()" O" X5 f& w. B: T {# i* V" W2 b( l8 | int i; 4 a: a: S. B8 c5 }( p# J% [0 M cout<<"X"; + b" j( _9 {9 U: F4 w9 H for(i=0;i<s;i++) ! H8 M* L- g1 z6 P cout<<i; ' u. m; F* f% @. z4 h cout<<"b\n"; 7 x1 w( [% W/ d, N4 @: z N cout<<" "; ; J2 c! }" K; G cout<<"\n";* d# C" v! q8 b$ B2 B+ T0 M }% v( B( ~' ^+ O- y+ u2 ~$ l `5 ~2 c. { //////////////////5 U8 c) D+ L" u# P. j void Result()$ P- A& P- K0 Y* F8 F { + G3 n6 q7 l8 t" U, V4 k& C int i; " n2 l" n$ j ^) y" X% H$ I8 y" ] cout<<"("; 0 R8 z' [; M! U9 r! J- P5 j for(i=0;i<s;i++) |! Q7 `6 c$ B: @1 F cout<<x;$ z- f+ A5 U" E+ l9 e8 J cout<<")";# c& U2 r6 ]' l" v' R. z. G) C1 D if(type==1)7 S9 o }5 k2 K/ H cout<<"Zmax="<<matrix[n];3 p3 B' F3 D- g6 A2 ]5 i* Q else cout<<"Zmin="<<matrix[n];5 l" l5 G/ S6 f" C) d$ n }* C( S; l4 y+ T //////////////////////6 c5 T& k& j& ~. p void PrintResult() 6 l- x; B, {2 W' d: M{* b5 S4 O$ o% k0 d+ { if(type==0) 0 r8 a3 \: K5 K* F* N8 T cout<<"the Minimal:"<<matrix[n];1 q/ e6 D6 s3 _7 \3 e- p8 L7 S else cout<<"theMaximum:"<<matrix[n]; + t# q1 l2 r$ |' N" Q. y& K}& _: F. s. W3 o9 ] ////////////////////////////////) L6 g# y. s9 c, C1 \' ` void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 & k" `6 X8 ?" L{ $ h: l) _7 X7 w5 F* ^1 J3 W4 ` k int i,j;- Z* P9 e6 m$ ?, A+ Q for(i=0;i<n;i++) $ ?4 T$ W( ~# A2 Y1 r# G { ' C' M* `* g \* J2 k. T" B' ] M for(j=m;j<m+indexe;j++) , N/ y) y$ Y3 i: s. Q3 d, \ if(nget[j-m]!=-1)matrix[j]=0; ( y- ^, `6 a6 G/ R$ { else matrix[j]=-1;, u# ?, w; o* n for(j=m+indexe;j<m+indexe+indexl;j++)' p4 _! D% U& ^/ {/ _% I0 d if(nlet[j-m-indexe]!=1)matrix[j]=0;1 |" M1 ?! s+ a- E else matrix[j]=1;+ i4 a5 t. { B, F+ C0 Y for(j=m+indexe+indexl;j<s;j++) 6 a' H' \& J! L" _9 a; P' q7 ]5 H if(net[j-m-indexe-indexl]!=1)matrix[j]=0;- T( P/ P0 r% ~$ ^3 } else matrix[j]=1; ! [. T: C- b8 A( S c2 w }# c( _5 {* ~$ l7 }6 F2 w$ R for(i=m;i<m+indexe+indexl;i++) 8 w, T% d- H9 E: {: [8 L# z3 U0 g matrix[n]=0; ! [/ ~* q9 x& K2 d4 j( R for(i=m+indexe+indexl;i<s;i++) ]: P( R( w! t) i matrix[n]=100;) r- h/ i d! O c$ D matrix[n]~~=0;! f2 d# t) b1 t }~~
& t) D: l/ `) V g* {$ _
/////////////////////////// 3 n) Q# y/ ^2 q7 \" }void ProcessA()//初始a[] q# z, e% }% Y( c {5 \5 u3 ]8 Z! i9 u int i;* e" o4 i& a6 y for(i=0;i<m+indexe;i++) 9 \1 O, D6 o# K$ K+ _1 ]/ u# @ a=0; 2 A7 S! S; n* Z4 C for(i=m+indexe;i<s;i++)' |5 ^" T9 C) y- m8 y a=1; + ?! H* U5 F7 u( R8 p; M}
2 V8 f4 n4 ]3 {0 v8 i
////////////////////////////////2 R. V q8 S1 G9 d, q% U j void Input(float b[],int code[]) & Z4 A9 r5 E l1 I% n! Q R+ O{ 6 I: T- V K T: x: q9 x8 h int i=0;int j=0; 5 y6 j5 _9 V: S' Q& G9 R cout<<"The equator variable and Restrictor\n"; + t$ y5 z6 p* s. \ b cin>>m>>n; ; M7 L$ C* g8 q* B, d' S for(i=0;i<n;i++)3 c# H5 Z, N3 y) v6 m3 h0 l6 H { - u% A& }; n0 X% I" M cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; 6 }% I1 z6 M, j: e* b5 ] cin>>b>>code; $ S. ]* j9 R5 R* {4 W cout<<"The 系数 \n"; L. F. L1 h1 c. g for(i=0;j<m;j++) # u2 Q9 e7 v0 a cin>>matrix[j]; ' I W# Y1 F" {( H }* ~: y$ p$ I4 u5 w/ @! Q/ j3 A% v cout<<"the type 0:Min 1:max\n"; * B3 j- V+ z+ R+ i0 v" _ do{ 7 \2 z- r7 }7 ]& P& @ cin>>type; ; H4 S# B8 M. L: M6 k if(type!=0&&type!=1); P/ a, |4 v6 G; r" o cout<<"error,ReInput!\n";" n$ s: J% m* X2 \ }while(type!=0&&type!=1);' I3 H% k! w) w% L: i1 C cout<<"the Z\n"; 8 X5 A' P8 R/ ~ ~ for(i=0;i<m;i++) 4 `4 h; G- j" G+ L+ C cin>>matrix[n]; 3 B, K: ?3 E2 T4 n if(type==1)4 X0 l4 T. r+ z) i for(i=0;i<m;i++), a3 B0 C9 P/ N1 D3 Q& b1 {& P matrix[n]=-matrix[n];6 H& m- ?- P* C* \0 k }
. a1 }8 O i2 y2 V6 k# P
) t5 c7 ?( H& Z W9 L ////////////////// + P& i& K) L: ^) `! ]8 h# t void Xartificial()//消去人工变量 * Q' k( V+ `6 ^( n{ & y7 e7 w2 H0 q {% ? h int i,j,k;( [$ Q- `, n( E, z, M& H" \ if(indexg!=0)6 \9 \$ e3 X3 _ { ' X/ J3 G h. K/ c$ [( n for(i=m+indexe+indexl;i<s;i++)$ _4 K% o5 n" O0 Y1 c0 { k {* R8 m* S& ?& ]1 d for(j=0;j<n;j++) # i) G# }3 g+ H5 A. U6 t if(matrix[j]==1) 8 h8 o8 ~5 I( C0 B; M1 i; j+ o { ' c3 c0 h8 T9 W6 C% Y for(k=0;k<=s;k++) 3 g) l" @: N6 ?& i' @, d8 d" G5 N matrix[n][k]=matrix[n][k]-matrix[j][k]*100;0 }2 ~# J' U* f& ~9 v9 @ j=n; ) \1 d, a' u$ u9 E+ p( N }5 d% L4 Y4 V5 q5 t8 I: | } & y( M& ~8 u; J; D& }( { }7 C' T6 z: z3 G; P' J }
7 |; ]7 `) a ~0 a' `' d
////////////////////////////////////////////////: D5 ]5 w1 {7 }2 ? void Process(float c[][100],int row,int vol) 4 k3 G' B( Y0 A( c{* f4 N6 J% a! n1 N) L4 V" D$ r int i; 6 W, d* O0 c1 D& ^; m9 C3 d for(i=0;i<n;i++)+ F% }. q A0 W5 o if(i!=row)c[vol]=0; ! b6 ]% i! F3 {# p' P/ }0 h" v}# N' [( Y) l, o/ } //////////////////////5 F8 } r# r3 h2 e3 y void Start(float b[],int code[])+ v+ h/ ]' G" W8 r1 q {' ]# x2 r+ e2 i( S, h6 C( u int i;/ ]# F2 E. q! v/ F8 \4 b. S: u float nget[100][100],nlet[100][100],net[100][100];0 d4 r7 N* z; \4 E indexe=indexl=indexg=0;1 B1 W6 \0 ]5 N7 h! w0 y) ^ for(i=0;i<n;i++) + Z) Q" D* Z, ] {/ W% f& ?! T/ O# C3 D) G if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}/ w! M: o! \$ S% K8 ?/ J9 u# ?) e if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} . M! l& o5 j+ P6 I, s* c3 m- J if(code==2){ & D6 j3 }9 q' X# _& ?3 j net[indexg++]=1; 7 U2 Y1 ~7 S' g% @' \. T6 z- _ nget[indexe++]=-1; ; B6 h' {0 ?0 c; ?6 p3 \- I Process(net,i,indexg-1)rocess(nlet,i,indexe-1);6 m& H6 v) }* g+ q! l3 M: v } ' B2 R1 n- y7 X }" v7 N" F" ^6 h2 P4 O* Y* ` s=indexe+indexl+indexg+m; 0 I4 r. b" L( W; ], P$ a6 d7 [ Merge(nget,nlet,net,b);8 }% Q' J* s8 W ProcessA();5 b+ C5 C2 B n1 b, G1 q/ ]4 T, Y2 _- S InitPrint(); * c x' C. L3 _( E4 D4 u Xartificial();$ M5 I1 o' Z7 x2 l" j! \ }
6 U( \& z4 U0 Q' p' J' s
void Simplix()//单纯形法 " j/ v. e8 J* f, c6 C; u# k0 I{ , o/ C7 k4 r. W1 j& F: C2 q# @ int in,out,temp=0;! v0 K% }$ i* h6 w while(1) p6 J# b- n0 |3 y. ^% u$ f K { $ I, b# i; q; r) k5 i0 H jckxj(); + A! P# [. f, x9 k' I: ?# | Print();, s# J" \5 |0 ^ Result();* M0 N$ a; J- ^' {, P if(!rj()) in=Min(); " ~ a& q6 C E5 z else{% k5 E& d4 a3 \ if(indexg!=0) 9 Z J3 W! h3 f$ ^$ p L! R JustArtificial(); 0 M% R7 G- c- e: M$ H7 m PrintResult(); 1 T; s* ~5 D4 m1 D return; $ [ W4 g! t; ~2 e0 a9 k% I } 0 N* a4 L9 U8 K( e# a3 M if(Check(in)). X# Z6 C9 a2 v; U6 I { : d* [4 \2 w& C% T" c9 |, X! j$ f cout<<"No Delimition\n"; - e- t6 _' Z/ K) S- Y return; & O! e6 O# Y) X }0 |4 C: r4 O* K/ L7 a; s! g out=SearchOut(&temp,in); 0 d# y/ \. D; u# F( r& S% b7 i Mto(in,temp); " u% j7 j" j) x6 H. }) l6 h5 [ Be(temp,in);( L" F9 m; }' h5 R- g# w Achange(in,out);2 j+ p" d0 q: Q( X }. f* X. g, r; V0 `; f }
9 K6 |; l' A3 [
void main() % o W: a) [$ r0 @2 w" d{ ; ^5 X2 l9 `% T' x5 @& ? int code[100];//输入符号标记5 f& {+ A& b# U* V0 U# l4 V float b[100]; # w3 D+ E1 H" J# e) {% Z( x Input(b,code);//初始化- t0 ~( k0 P0 q Start(b,code);//标准化行 7 o3 f! \( {$ J' y N% Q Simplix();7 a" r& k3 i8 j0 z }6 h* w5 q1 @8 ?4 C5 }' J/ X