单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> p. O5 j1 w8 n6 G7 B( _6 \7 @ #include<math.h> ! u! J$ s1 o7 V/ `# E1 b7 wfloat matrix[100][100],x[100]; z0 `! a$ F+ R2 t3 r int a[100]; " V, z2 [; O- U% Iint m,n,s,type; v' [5 A- w+ @, D int indexe,indexl,indexg;3 @" ]* x0 m7 g e% i( ? /////////////////////////////////& v& E: j) M% n9 j" E void jckxj()//基础可行解 3 @2 R( o( s" q- y; u{ 5 @' y; U8 u; _& \0 Z int i,j; 0 s4 U1 Q6 E- Z: U2 Y& b for(i=0;i<n;i++)3 L9 y* O" g. g! \8 H for(j=0;j<s;j++) 0 a8 T6 q& i! l$ Y if(matrix[j]==1&&a[j]==1) ) m& f4 D% T. P1 O4 r9 n { 6 D- h& G8 r5 x4 s. F; L x[j]=matrix~~; 0 |# Q" `- F* q' i j=s; ; a5 K! D! t& j( r' u8 ?2 M } $ e; T$ J3 X! ^6 b! d- F* d for(i=0;i<s;i++)8 y/ o& d1 T' q1 R. w6 h5 L' e {3 o if(a==0)x=0; . V( L) Q- { w# C% F}~~

0 B$ R$ Z$ M4 D! ]$ z+ u
int rj()//基解矩阵 / M( B; }# ^8 M# z; R{- e5 x% Y o( H# K7 Y; v2 E% P1 f int i; 6 Q5 E, `2 r0 } for(i=0;i<s;i++)0 J) B# }1 b( a9 g if(fabs(matrix[n])>=0.000001) 1 T" M9 b8 | \+ a! {" _ if(matrix[n]<0)return 0; - M& a& U$ K- T6 N0 q8 y6 _1 i N return 1; : t2 O# W/ U0 C# J* A6 l$ G# q5 Q}0 F$ \& }; {/ w: n: s int Min()//求最小的; N9 D2 `& H1 G- F4 w {) z! L3 a/ c u+ ]0 Q# n% w% ] int i,temp=0;" V9 } M/ m# T3 p float min=matrix[n][0];( `* L4 C8 d( Y* t. [" X for(i=1;i<s;i++)' e: Z4 ]6 _ T, M if(min>matrix[n])& D8 `( S% {) p. h0 _2 M7 r { " f# B% Q6 X# o min=matrix[n];) T( r2 r+ G9 w* b$ U temp=i;% U$ R4 |& l1 ?; I. @ e }; a, W& u% K" H- o5 @( p8 M return temp;6 D% {+ h8 I8 i0 q# X0 n5 U }- E; A3 r @) _+ Z# S) r; Y0 F7 k ///////////////////////////////// 2 F) Z: b O# Vvoid JustArtificial()//人工变量 / g5 X0 w6 t3 g2 |{ / ^8 q" ^7 h9 q& }0 k int i; , U; Q. [ P3 G for(i=m+indexe+indexl;i<s;i++)0 }) f4 K4 ]- S! F- B, C2 z" z if(fabs(x)>=0.000001). Y1 G' E2 u& t { 0 p& W: p$ B8 Y0 q( v. g: Q cout<<"NO Answer\n"; ' i+ p( f3 o% h4 V9 I return;$ \9 u. [) w* d& d }: ~) [2 g/ V& K2 m' k* i7 u: @4 ? _" B }* V$ u; a1 X) O ///////////////////// 7 O3 N- u/ T$ b* {int Check(int in)//检验! b$ i, H7 w! V3 O& I { " b2 J, y0 _$ r. T) b2 R* b int i; ; e5 X; x- y! n6 m float maxl=-1;# `8 [; t! G- p* B r e7 h for(i=0;i<n;i++) 4 V0 x4 Z/ z6 } if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) ) ^' B& F5 M+ q7 C R$ A( q maxl=matrix/matrix[in]; + I6 |( `7 T0 e. z! ]! p if(maxl<0)# t' O9 ^ S6 B9 c2 |4 q return 1;0 D, b2 ?0 z% }; t return 0; 9 _* [+ o: ~1 ~9 \0 _" g$ W6 h}5 }. g" j$ N# T) `5 d int SearchOut(int *temp,int in)//出基变量 8 H( z: J4 p: Z6 {3 \: I{9 a9 p' E5 r; `: E! T int i; . g4 v( Q v* i, H float min=10000;( q; @! N. U# N for(i=0;i<n;i++) : `# _" Q, x: d J0 `+ V2 A9 l if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)0 G0 N' F# z8 u& S &&min>matrix/matrix[in])/ s) Z! O9 E8 E" t/ f0 s( w7 ] { # _: K! K) S! N& D% U min=matrix/matrix[in]; 6 Q, T: x" x& ] *temp=i; 3 [" m( B5 b4 ?4 b: ^ } $ X4 J9 S" ^) x5 y5 j for(i=0;i<s;i++) : D: }% r! x R% e if(a=1&&matrix[*temp]==1) - c x7 w/ Y; n return i;6 ?8 w- v% p3 p( h, u+ ]3 x( W } 1 Y& q' R e0 _! | L; M( l* ?///////////////////////////////// , h1 y/ {- ?! i& u" N8 uvoid Mto(int in,int temp)# G: h: v3 X' N# Z0 J( [! O { / k4 ]( {, M4 R int i;, Y6 f* N9 A" j for(i=0;i<=s;i++) + Y; L+ w4 p! Y6 T' x if(i!=in) 5 h/ f2 ?- k1 A6 L1 K$ u, U4 r matrix[temp]=matrix[temp]/matrix[temp][in];! \! G' y3 d) x6 k. O+ E! ?6 p matrix[temp][in]=1; c [2 E+ Q7 R8 I% ~8 V }3 T2 l- |1 }3 E, y& y( L6 s9 @" E m /////////////////////////////5 b7 V! j8 \. _) z/ R6 z9 l void Be(int temp,int in)//初等变换4 h: v& h8 C7 O, T& k { 3 t) Y: @5 y! C int i,j; [( g9 [; {0 H' S3 c5 u/ c4 D float c; 1 D; |1 V6 z! K1 ]; H( L for(i=0;i<=n;i++)& Y" @" ]2 P. w1 `. k" z {# H: A, Y, j2 U5 t/ R$ j) U4 r9 x c=matrix[in]/matrix[temp][in]; / q% q! r, [4 g7 K+ `7 ]2 Y if(i!=temp) . v' |8 v7 @0 L# ]# y for(j=0;j<=s;j++) : M: @$ W6 R, Q matrix[j]=matrix[j]-matrix[temp][j]*c; $ E9 k. \% Z" Q; U4 {( \* H- x4 C }" g* ~! R2 j" a* l }: Y+ o, y; a( R& d //////////////////////////: e) N* q& ^) K' n8 q9 J+ K void Achange(int in,int out)//出基入基转换9 f; _# L, J/ T7 j( d% l9 i { ( M" ?3 ?* E4 ]& I; s int temp=a[in];' L, c) C' Q ~7 X8 Y a[in]=a[out];5 _( V) b5 u0 w7 N* e/ s a[out]=temp; : a5 L5 P" A0 U0 Z! _: G}0 o- N. y5 p; \" A! J; }1 j1 a ////////////////////////9 x- }' F& Y+ d/ y! d! L. w void Print()' W# o# O5 x& I# S- X {7 a' Q5 {! l u0 ~" _3 F int i,j,k,temp=0;+ d' r7 a9 X" [" e# K! L8 z# ] for(i=0;i<n;i++)4 f; S5 i9 }4 _' f {8 u3 P6 p9 R- _ for(k=temp;k<s;k++) 0 G5 h% n7 ]: u+ R8 `% k if(a[k]==1)* I& i! q3 P1 m. v7 Y {) }! A2 S0 d0 w: ` cout<<k;8 p( E3 @8 m8 V. p temp=k+1; % K; N9 j, m7 A; A$ H" W0 T k=s; / Q' c" y- {4 C6 j9 k! v6 I }0 z! M( O/ x4 v6 x8 ^ for(j=0;j<=s;j++)! L: R8 @8 H) y( h+ h2 p cout<<matrix[j]; & I3 K+ q" i$ y cout<<"\n"; " W# N6 w6 ]; Y- m7 | }# c7 _6 G1 T9 u, F8 J; N cout<<"Rj";+ N% h/ K* V* z for(j=0;j<=s;j++)8 b; w; e, A2 q: G& [8 X+ Q0 R0 e, \ cout<<matrix[n][j]; ) S" Q# F9 B) [; a, ^/ ] cout<<"\n";4 q# G* h C5 Z, g6 d } / f% e$ ?% Y- C& K; J7 A////////////////////////% J7 G- c. {' [' A) Q! x0 c void InitPrint() ; L/ E: d% S8 \{ 8 w- x4 `, l6 B+ b8 x0 K, ] int i; ' Z2 k, ]3 a3 T& B+ q; ^+ ?& R cout<<"X"; ; g% I9 W* }6 `* [1 r2 F+ [) t' B for(i=0;i<s;i++)* x( S9 _9 ]/ [( z# f% x cout<<i; 2 E4 ]$ ]! L. A1 Y ~7 J- q) N cout<<"b\n";+ n7 f3 q, f8 s cout<<" "; . P% Q9 q% l& d1 S# C( V cout<<"\n"; E; L3 l" Z3 d$ f y}9 g1 ?( Q s* M# P# L0 _# C //////////////////9 o) n) `, Z& z2 k c void Result()* h; t, w. r( [1 a {3 l/ g Y6 M7 T5 e* I# l0 H; m int i;1 Z8 `9 E2 H9 P9 s8 M4 Q. E cout<<"("; " h2 \, B" {& k) ?0 q for(i=0;i<s;i++) 4 S& u/ Z" y: Z) z- R, N; ^ cout<<x;) k4 S6 m/ h7 y( `4 W; R+ Z0 x cout<<")"; . Q! H8 U9 ^8 V4 D& r7 y if(type==1)+ t3 u# i1 x! x5 N cout<<"Zmax="<<matrix[n];- b! W8 m8 e+ }- h8 i. ?5 g" ? else cout<<"Zmin="<<matrix[n]; ) l5 F" G1 e7 F% n}) k$ v" z& f: T: U7 [2 \! _) [ ////////////////////// ! c7 E- f& ~8 M! pvoid PrintResult() 7 l/ n' X" F1 \2 \% A4 F0 s, j9 {{ $ [9 X- n" U6 o( x' H# l( b0 ` if(type==0) Q; r& Y) y( M3 L1 p! M/ g( t cout<<"the Minimal:"<<matrix[n];' n; T2 J2 [3 n0 u6 D else cout<<"theMaximum:"<<matrix[n];. a% o. U/ c6 r }+ E$ L( Z. A7 y" J( ?9 f M ////////////////////////////////: g& R0 I( w5 t8 |! m o! S6 l void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并3 z* _3 s) \8 J { " _9 |, N. P% K' M3 T& f int i,j;3 P8 [& U" K4 u2 P: v for(i=0;i<n;i++): J! @: q6 L! G) i2 Z' x {) ~ I7 R D5 P* V% } for(j=m;j<m+indexe;j++)8 J3 d j) v- j/ x! N' Z if(nget[j-m]!=-1)matrix[j]=0; ; Y9 ] j- `! k/ E# E0 C else matrix[j]=-1;9 U; [+ j! }( u. ?* b& T" r for(j=m+indexe;j<m+indexe+indexl;j++)9 ?# n" G8 M3 o: z if(nlet[j-m-indexe]!=1)matrix[j]=0;) z1 @. J2 P" O else matrix[j]=1; , M8 O% ]: k) a& z+ O9 z for(j=m+indexe+indexl;j<s;j++) ; {4 H) r0 R; k( W. y4 y, S1 u- b if(net[j-m-indexe-indexl]!=1)matrix[j]=0;& F$ k. d9 K X) `, |7 Z else matrix[j]=1;& Z2 V5 ~9 S+ [0 P0 b9 g+ m- O/ u+ \ }2 p1 Y) J# W, \ B! h7 r& } for(i=m;i<m+indexe+indexl;i++) ! G! N9 w( K# p- z$ }- E, z! z matrix[n]=0; 6 f* I; ^2 l3 b2 e2 x for(i=m+indexe+indexl;i<s;i++) . Y9 w6 W# x9 x# p matrix[n]=100;. c5 ]( G7 V5 i W* a' Q matrix[n]~~=0; : f- @, l6 H3 T}~~
/ E+ s- |3 J- x! n! U( G4 b/ N
///////////////////////////, ~# }' H6 ? }7 i9 y void ProcessA()//初始a[] & n) y& Z, o x7 ^" V0 [{- Z4 t; p2 [9 { int i; * R2 y9 I" v- f0 K. ^ for(i=0;i<m+indexe;i++) - K, X9 i) X1 B: N- m5 J. z% H# c' W a=0; t5 D" U& ?% s% S9 C for(i=m+indexe;i<s;i++)% L* V" D( y& [2 h- R+ {( J/ n a=1; ) Z+ U4 h7 D9 N2 j' R( p$ z}
! [# f5 T' d% W& \0 L
//////////////////////////////// ; G; g1 o' [ f0 P' L0 }void Input(float b[],int code[])3 n, v |3 i7 ]& k8 f* U { $ m' C3 C) M; X6 W int i=0;int j=0;! g9 z7 o8 e5 _, i# S8 k/ x cout<<"The equator variable and Restrictor\n";. c6 W3 F5 v; R6 n) j, V6 Q" Y7 _ cin>>m>>n; , m% t0 Y" A4 W+ v for(i=0;i<n;i++)) n/ J& f3 Z p3 D* N' U7 z { 3 g3 w0 O' Q. F4 G. S cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; 7 n/ x, y4 \! ~$ m cin>>b>>code;1 I% _4 Y+ H5 c; L+ u8 | cout<<"The 系数 \n";- Z' U8 w9 r7 a6 i& c5 i, ]. x for(i=0;j<m;j++) 0 l/ Y. \5 [7 Q1 T5 r3 X8 k4 x, b cin>>matrix[j]; # x8 e# m5 a- w" s* e2 R* J }9 m# T7 Z' Z8 y: `' `1 C cout<<"the type 0:Min 1:max\n"; Y+ i! [& f' ^ ^7 Y. A do{ 1 o; H1 E7 ~' a$ G; U cin>>type;( Q6 d8 w! n$ H if(type!=0&&type!=1)' U7 j- ~5 S) o cout<<"error,ReInput!\n";( B) k4 t6 m8 I8 d A }while(type!=0&&type!=1); 3 N) n& ~0 \2 X$ D6 ^ cout<<"the Z\n"; 7 V$ a; ]9 T# I8 M' y! W2 ?# d/ y) J for(i=0;i<m;i++)1 y4 l# J$ i( Y5 F1 v9 E cin>>matrix[n];0 r0 n6 Q/ E* U' _ if(type==1)7 O& E3 W* d( @# F. f! E for(i=0;i<m;i++) 0 `6 u3 P0 t( J" o matrix[n]=-matrix[n];5 J/ B5 o3 H, C) B; k1 _ }
) {$ W. S. L3 @5 @$ P! G( }' P
5 h4 L( c( @( O1 L+ p2 @8 b ////////////////// ; c9 e9 V) g6 b' A Nvoid Xartificial()//消去人工变量 & [! n; C& S; c0 }0 x4 y{ ! M+ K- }6 t5 Z1 N t5 j8 G int i,j,k; . l$ V+ \; W! k( X& T7 C+ I' K if(indexg!=0)6 X( Y/ Y* x, c" M- q {0 S p9 W i6 W! o) m' X% c for(i=m+indexe+indexl;i<s;i++)3 H8 l) J, m6 k, n/ z5 \ { . h" R; N) K1 v for(j=0;j<n;j++)5 f9 d3 m) v" S C# M9 K if(matrix[j]==1)3 l9 A6 z$ M& k% L$ V- g) s {4 b9 h# n9 o1 B: g4 F# ? for(k=0;k<=s;k++) C# `3 t; `7 l4 ^) W" c matrix[n][k]=matrix[n][k]-matrix[j][k]*100;- s# [9 }8 y1 V& R j=n; " \9 z& p5 Z5 t3 X; A/ H }( X# h2 K! p& \& v3 A1 Z# m } # D; i- r$ J+ e3 Q }9 f3 l: l8 `+ D1 v! S& h, z0 g }
' T0 o6 Q: h' F U. X8 u7 Z
////////////////////////////////////////////////: `; f& O4 T7 C void Process(float c[][100],int row,int vol), F F; Y+ k* s, N* r0 V7 |* H {& {/ M/ m" B, k: l int i;6 I8 q) t* R) F8 S* k" o for(i=0;i<n;i++) Z* `- K9 O5 B0 |3 M if(i!=row)c[vol]=0;$ i) C# g5 N( \6 | } $ n' S, h; V5 _+ f! l) C//////////////////////7 W! a$ T6 G' n* z1 [* C7 s5 `4 f+ ? void Start(float b[],int code[]) # l2 M( ]; E' C+ L6 f& x( V{ E8 j$ ~$ V! i, X, b2 F, t, w, n int i; 5 }4 r# L% [% Q% D* D- {' }# _1 z float nget[100][100],nlet[100][100],net[100][100];' p1 f8 O2 n0 |' G/ A4 I% z( G indexe=indexl=indexg=0; : v5 h8 C( J, n for(i=0;i<n;i++) 3 L* F. ^. A# e4 R* V {% D* t& u& |4 s, \ if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}3 H8 K1 }4 L* q* K# v- I! Q% @ if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}8 e# U0 R7 U5 v2 R: [+ |1 i if(code==2){. r, N0 v' ~" p. Y: C/ j' c net[indexg++]=1;0 v% E+ z8 A, M nget[indexe++]=-1;& ^6 J- x5 l% X6 J* _: D1 Q Process(net,i,indexg-1)rocess(nlet,i,indexe-1);& ?9 R1 g G- n/ X7 e. N } 1 Q! l% v8 I+ S } ; D6 e) D/ G' }+ a s=indexe+indexl+indexg+m;6 W( h( _% D- r Merge(nget,nlet,net,b); 1 D: ]$ v: g0 u$ c( ?5 H: ^4 J ProcessA();0 G8 B$ m7 Z3 _% ]6 ]. k$ i- e InitPrint(); 6 ?/ I9 |& z' {% L0 q Xartificial();0 y8 N& i1 C! D0 K6 B- N4 z- w }
$ g$ Y) h% a& k) V( [, F
void Simplix()//单纯形法$ L% `1 v8 ]! O! x# | { 3 r [6 S$ p. S6 \' J% R int in,out,temp=0; : u. {8 z9 C/ L! C! c" `% ` while(1)- P, B0 _- `2 |. C. @9 i {6 B( w* a2 x6 T: u% G jckxj();* E8 S/ D5 u4 D3 j+ B* |+ v Print(); ' ^; b% C) K0 A+ C) ^ Result(); 4 f" D3 w/ ~0 C2 A& w if(!rj()) in=Min(); % N. @& q1 f; C: v8 r" f else{' Y4 I- y2 J4 X5 u1 K if(indexg!=0) - n. w- A# f3 p. X; y3 k JustArtificial();" [4 b3 j- E* z PrintResult();% K, }' X" a/ [6 Q1 k2 { return; 1 f t! y* C" X* k4 V }5 A5 p; f2 y! @+ n# A if(Check(in)) $ p% @9 [. a+ _4 }$ q) S {0 \; ~( x) O+ ], O cout<<"No Delimition\n";. f4 ]1 p& t7 }2 C0 x$ x. V return; 8 C/ L9 u& o1 Q, O; M } 3 B6 e8 H1 l9 m" S out=SearchOut(&temp,in); , L# V: A$ s2 Z% X& m& I Mto(in,temp);- F) b: w- c$ I' v; x Be(temp,in); N8 L8 _! o/ r3 F/ \9 b/ f Achange(in,out);& q/ b% a% _$ p } 9 ?6 h0 X2 t6 Z9 k+ e}
/ G; O4 F ]5 {5 M+ P; H2 k! u
void main()! G0 G9 j* X# T# r6 ^" h# _ { O2 R% l6 Z# ]4 D% s( P' t* ] int code[100];//输入符号标记 " U1 }( E7 L: @0 P% s( J4 g float b[100]; ! i5 i: [+ d( S3 I& E6 M) z8 u Input(b,code);//初始化 # p; H* k- H- ]( [( l Start(b,code);//标准化行" d( h6 E6 e `8 A# Z$ M/ Z Simplix();& r% H3 t- ~% H6 @ }7 s- i6 e! P( m4 s$ L. R, I9 ~