单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> ; J- T$ q# a9 ?0 b2 @1 z( m3 d#include<math.h> 9 l, _0 Q9 g% K! ~float matrix[100][100],x[100];/ K1 J* V8 |: U1 h int a[100];2 M4 ]) I; b" W9 ^) `5 E int m,n,s,type; " q3 O# H* ~2 u* j6 Rint indexe,indexl,indexg;4 F+ E5 L- j: X% N/ _& D ///////////////////////////////// * {4 q/ l" m2 O! U Cvoid jckxj()//基础可行解 8 U) c g B( O{2 \" I6 \- d2 C# g% N int i,j; n6 s7 q; F- \# A5 Y! L0 H. m$ v for(i=0;i<n;i++) & _* x. D3 `0 C' e; d) a1 O7 J! M for(j=0;j<s;j++) 5 [* K \4 k8 v! ] if(matrix[j]==1&&a[j]==1) + V+ i* l' @ a" a" N0 T {% v$ ]& B( C' R6 Y B x[j]=matrix~~; , z. } Z% \5 j# S' e2 ? I j=s;2 ^' m/ O j& H" j6 t }( U5 g7 @. I" D* m# e for(i=0;i<s;i++)9 M$ ^5 i3 Q- s) p( q if(a==0)x=0; ! [1 q# t3 p6 O8 f; o6 ?}~~

0 e& g9 m9 W) @
int rj()//基解矩阵7 \: q# ~6 y& ~' ~3 B { ! q( \$ Y' V# D8 m' E int i;/ x" b* S6 V4 ^% M1 l7 \: V for(i=0;i<s;i++) 6 g$ [ B' k- }* s( i if(fabs(matrix[n])>=0.000001) W" l) L- x; F2 R# Y# G, p if(matrix[n]<0)return 0;+ F4 G$ V9 N/ ^* M2 a) } return 1;: J. `# G: A `$ ?6 R. t4 L }9 K" I; M! m6 f/ t- Y; {( Z0 M int Min()//求最小的8 a( b4 A4 [6 g0 v" ] { + C$ X" f# {. Y4 q5 H int i,temp=0; u/ {) i9 K* X+ |' Y b+ G+ t float min=matrix[n][0]; 0 [7 t) [6 W5 g% Z# g( l. g9 q for(i=1;i<s;i++) & p. q- v8 L( ~8 z! o2 b if(min>matrix[n])9 k3 u( V: s1 i; e4 L9 Y- w8 j& R { $ L; i( b9 ]) ?* N1 o min=matrix[n]; , z' q- G/ m7 C; b1 `7 n temp=i;2 R8 j" T9 _' x } . d+ [& l6 a& m4 w0 _% D) @ return temp; : j2 t F6 h* [- U2 u# ]6 k}7 C; m) W0 J* c' i) W( [ /////////////////////////////////( q! t6 Y: b& ~ void JustArtificial()//人工变量 7 x. s3 N9 x" ?8 g1 n* J{" ?% P2 I( @ a" z5 E int i;' Y( ?# t, O! P% {2 } for(i=m+indexe+indexl;i<s;i++) ! R/ x% P, i* P L if(fabs(x)>=0.000001) ! r# `8 z, g# g { { ' b$ L' p5 i/ d2 O5 l C cout<<"NO Answer\n"; , U% ]+ r6 q) i& \) Q3 T3 [ return; % a+ r2 y7 C3 y9 c. e/ s+ W } X/ u& y/ R; }. Q$ r4 ~5 \ } 9 v9 `4 o( N* R" A/////////////////////* f! H3 n$ O2 O* D% f$ W7 E int Check(int in)//检验% s% j/ ~! U' c& X { ; M1 A" l5 [$ h2 K2 C/ X int i; ( d9 c3 j5 t8 Q$ \: c, U float maxl=-1;6 M, Y/ I% V2 U' C- ~ for(i=0;i<n;i++) 1 H( x. s. {8 ^- W* o' m- I if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) 8 q* G# H/ x3 A }1 V; B9 R maxl=matrix/matrix[in]; 7 J5 Z4 _0 P& A" ^3 L if(maxl<0) 4 c$ V- ^$ ~; W- |6 i0 ? return 1;% c( v' I* h+ {2 F: l+ z3 H) s7 ^ return 0;) `/ H$ Z3 d6 c& B' _5 M } 5 ]) _1 T, l$ [! s5 _( c/ e5 O0 _5 jint SearchOut(int *temp,int in)//出基变量 2 E4 x3 f9 w- z{ 3 G' k% f4 U3 ^. B9 W# \ int i;/ e/ e7 I9 r+ X3 r* ~ float min=10000;3 Y: p5 O! S% _ for(i=0;i<n;i++) }; [' A* o- c$ V. P7 j if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) ) e- I, o: c9 O6 [2 u3 R5 G &&min>matrix/matrix[in])3 F2 U& R m3 f8 q7 c {0 R I7 y3 E) ^+ H( `# p min=matrix/matrix[in];4 Y+ h2 T: v3 E *temp=i; / w o$ O# L( `& J1 Q7 u0 H, E# B: @ }; J9 g% w8 m8 u" f/ e# T' g, C for(i=0;i<s;i++). D5 {4 t e8 T/ @ if(a=1&&matrix[*temp]==1) z) J$ c7 R( T q3 e: { return i; * I% G9 ~& O# m3 I. ]+ I2 `5 w} o6 X0 C9 { y$ h: I /////////////////////////////////# h6 h$ I8 n: D& K! y void Mto(int in,int temp) ' I: ~2 S9 G1 [) j& v{ 7 b m5 L9 b; p) {9 u5 X. c int i;1 ~0 i% H9 v- a5 I0 d. f, B% b for(i=0;i<=s;i++); ]1 D' J3 o( w1 Z* E7 {% C if(i!=in) ) J) t H( } Z) m3 q matrix[temp]=matrix[temp]/matrix[temp][in]; + ~) G0 ^' \0 U0 I matrix[temp][in]=1; ) _% a7 V3 s5 D& Q) F' [} 0 `) Y$ e3 Q, Z6 ~# R///////////////////////////// 2 R S1 ?7 Z( ?/ }void Be(int temp,int in)//初等变换' M: G- f5 w, P9 y {/ F& _8 e$ j* S! C+ | int i,j;5 H- J7 n% n% Z$ a0 ~ float c;; q/ R6 \" a# h, {/ w for(i=0;i<=n;i++) * `, P3 m1 [1 n/ l" _9 ]; k {2 h3 R& M4 g& x$ c- a8 \ c=matrix[in]/matrix[temp][in];, U) [4 q# H) H6 D( |3 G" U& L0 m if(i!=temp) 2 k% M2 p2 z/ @" H% x for(j=0;j<=s;j++)& g$ a$ \( W; J0 ` matrix[j]=matrix[j]-matrix[temp][j]*c; # \2 D! x9 d; L1 u- V }1 C$ Z( d; y0 U$ r+ W }* l( Y s f% l' m8 q4 B% p, ] ////////////////////////// % l2 |3 ~2 e( I0 e. [* i7 ^' ^void Achange(int in,int out)//出基入基转换 + c3 x+ T3 |" \6 a' i{2 f/ O8 D! {$ v Y! {0 S int temp=a[in]; ) X6 @0 f9 J S% Y a[in]=a[out];, t3 m |/ \7 g6 l% [# D7 H a[out]=temp; $ t) Y" \5 G& v$ ?, e6 ~) y6 Y}( h. j8 h% \* ] e* w0 Q //////////////////////// ' F5 p% t* c2 [void Print() 0 n+ N: g. _, _2 R4 z{/ y/ b& ?$ x% B; t int i,j,k,temp=0;! L2 W$ N, M/ j& m( W# A for(i=0;i<n;i++) / G2 F: X9 s& O) B) L( s { & p4 S/ C! F, z- Q for(k=temp;k<s;k++); B) }3 p8 z) z6 e: ? if(a[k]==1)2 y O) g. s0 G$ h" L/ o9 ]6 J; B( j {& r" j2 e* G) c& Z4 I6 M cout<<k;2 b% O% G+ K n- ]' Y, v* l8 f temp=k+1;. n" u8 `" _% Q6 n k=s; - c' f: A6 |, I! M) ~/ | }7 x Q, c8 A' g v5 q for(j=0;j<=s;j++). {6 J8 |% S; c cout<<matrix[j];3 n: O( D; c7 y; Q" M9 P& N6 d } cout<<"\n"; , c( c2 ?: K) I/ W- A } I" w* f T9 J# ]3 M cout<<"Rj"; + A! k2 I1 K! Q: d* h# M! S# S for(j=0;j<=s;j++) - k" D2 P: t7 P9 N6 S cout<<matrix[n][j];; F: F8 x+ x9 @0 a, @$ M cout<<"\n"; J) G: W1 U- g5 U+ q} $ r; C8 @2 V2 k" k8 G \////////////////////////4 R" ^3 U3 L' G: ]& E. k9 T- ^9 x void InitPrint(). j( x" |; j+ o, _9 D ^& T5 g {$ U; N; c: P% g2 u* Q) {! _6 _4 r int i; cout<<"X";5 ]! @% F5 M& _# ^; C- @ for(i=0;i<s;i++) 6 |7 m# A# w. N cout<<i; # r( R& y1 r. K/ W) m; r cout<<"b\n"; ' a0 @! k; P: I5 P9 K2 [ cout<<" ";, Y/ _8 m* j* F, R9 q$ U cout<<"\n";5 U, \# Z7 Y& q7 j' a' {( s } # |6 V# S7 s. `7 i, I* ^. x5 a' H( J//////////////////6 Q" @* Q9 t4 w& }+ v void Result()1 q2 O# D" \! e7 J { - t8 r. S* P- N int i; 2 k" j' G, [/ R, K% l0 _: [' e& G cout<<"(";' A, B/ Z3 j ~) S for(i=0;i<s;i++) 7 f6 h: F3 o/ M- X' Q cout<<x; 5 `7 w# H5 G6 D5 W& F cout<<")";/ @4 c- A1 }6 ?, U9 } y1 g if(type==1) % j1 H" _8 ]2 o# e& ~: w) G+ x l cout<<"Zmax="<<matrix[n];3 m& ~5 r7 X# u0 `! k+ w else cout<<"Zmin="<<matrix[n];3 A1 E k; b- T- _* v" q: ?6 p7 S }! B' i {& E' A //////////////////////) @+ V% W% Y: r e6 O0 p void PrintResult()5 P& {1 Z Y8 t {$ ^1 Z% Z5 S+ V8 [9 y9 U$ A if(type==0)' {8 r" V9 w2 `. h* } W cout<<"the Minimal:"<<matrix[n];: O; g$ h' U! y6 q& } n2 B else cout<<"theMaximum:"<<matrix[n]; 0 j; L' A) j6 g} " z- W; }0 [0 H" g& R2 J////////////////////////////////% O. _6 _1 _6 u9 u8 l. Y } void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并) A" u+ `+ |/ v; _, a; G7 G {+ O5 y. O- t/ h int i,j;% D' K; o+ @6 f; X for(i=0;i<n;i++)% ]; G# D9 L, ?1 L {$ D7 u; c) D7 O- m% C: ] for(j=m;j<m+indexe;j++)" d; M' `6 a, Q/ E if(nget[j-m]!=-1)matrix[j]=0; $ u4 |: |3 ~! a2 s' s else matrix[j]=-1; 1 x+ v7 y; y. L/ m* F for(j=m+indexe;j<m+indexe+indexl;j++) ' I; H6 e5 E6 B3 j7 \/ j/ d if(nlet[j-m-indexe]!=1)matrix[j]=0;" k5 s' g* S; S' o: X7 B else matrix[j]=1;& q; }" u/ b6 w3 \ for(j=m+indexe+indexl;j<s;j++) # \# k4 w4 v9 Z if(net[j-m-indexe-indexl]!=1)matrix[j]=0;* r% J- I0 |; c else matrix[j]=1; : H: _# @0 H0 B } - o' U: N( o4 |7 ~6 X for(i=m;i<m+indexe+indexl;i++)( m4 } E. ^: `0 I2 M* l$ Q. ~3 r% f matrix[n]=0;- V5 m: {! Q/ ^$ [1 B9 u for(i=m+indexe+indexl;i<s;i++) ! X6 |- m2 |! a matrix[n]=100;0 ?2 ~; b1 z- x/ F8 P3 h2 g matrix[n]~~=0;$ n" X& Q2 A) B: g. K c8 z8 c- c }~~
\1 f$ m4 W. v4 X+ F/ @0 Q J
/////////////////////////// # L% d2 `$ D2 Uvoid ProcessA()//初始a[] # r, e8 o3 o. S2 r% L4 E{ * i7 e' ~3 W# g- ]6 s/ q% k int i; # q! f0 E, _5 V* R/ y( X0 o for(i=0;i<m+indexe;i++) 4 V; \& W- ?+ I9 G a=0; , W8 d1 ?3 \5 C8 k for(i=m+indexe;i<s;i++). P( [6 J4 o1 x4 o& N4 K a=1; $ P3 e W/ Y# e. R% O! F' [" f& C}
) ?: }* | L9 u9 Q3 L+ H
///////////////////////////////// a; Q; t, l( A) m2 T% h7 ] void Input(float b[],int code[]), @( I1 u. T$ N) t& H# A2 K { 6 [; U6 \6 f* E4 y int i=0;int j=0; v" _& b x; t. [0 _6 ~7 A0 I& E cout<<"The equator variable and Restrictor\n"; - n8 D1 m! X& t cin>>m>>n;1 W' C2 J& \/ t2 `! j; v for(i=0;i<n;i++)" e) k4 p0 s; G `! @# t {7 G" F6 F* ^( [: @; k$ M cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";" B( H- L$ i$ m cin>>b>>code;3 N4 i, s$ P# v cout<<"The 系数 \n";( P6 c, v2 u% G for(i=0;j<m;j++)& Y! @/ P k: L/ t1 v+ D P# {; P$ b cin>>matrix[j]; ( U1 ]5 C, W8 n1 W }1 ]) G9 B3 C- G& | cout<<"the type 0:Min 1:max\n";' R. W% z n8 F2 f. l; h do{ 1 `) R# }3 `3 ?2 b0 J cin>>type;. R6 A7 x4 @- G6 Z2 c if(type!=0&&type!=1)) n9 l# G0 N3 l5 @5 U cout<<"error,ReInput!\n";" c3 P8 Q1 P6 m0 A! C }while(type!=0&&type!=1);7 P) I$ _ @- d. v$ x cout<<"the Z\n"; + M! }+ o' l, [/ A; _ for(i=0;i<m;i++), n0 ?( m- k5 U cin>>matrix[n];- F9 O5 k7 [( k% x1 Z4 `6 \8 A if(type==1)) l5 [' i3 R0 s6 p/ s$ o. f for(i=0;i<m;i++)/ E/ T( z1 {+ `/ s matrix[n]=-matrix[n]; 3 u- U* e0 X: J7 w& J}
9 t( v7 x9 h- U z: E! R/ H \
% f4 F6 M2 ]- w3 \$ f; { ////////////////// 6 _9 }" d( M( I, z! Qvoid Xartificial()//消去人工变量 5 m% L* ]0 _( @. l# a{ ; b0 Y6 x1 _7 m. L int i,j,k; * V$ ^) w5 Q5 I" U* j3 i: r if(indexg!=0) 0 A- H) v' W+ N! Q1 v; y { 2 r* u( }/ R$ N1 r5 d4 S4 f for(i=m+indexe+indexl;i<s;i++) , d9 f- Y$ K& y% A v {. L- V1 W* s, `( c2 Z for(j=0;j<n;j++)9 N, L$ K3 L/ G0 B if(matrix[j]==1); Z8 W2 S% X) n3 p( }. U( S- n {4 r* M% l8 E2 G+ Z for(k=0;k<=s;k++)6 I- A3 u; W! b8 X j. e matrix[n][k]=matrix[n][k]-matrix[j][k]*100;% g# g' x+ M$ u( U& t& ~0 W) v8 h$ v4 R* z j=n;" f6 H7 F5 M0 [3 [7 E } 4 M+ Y' c6 D* I( m2 U' K; A* y# m. m& S }4 s* _2 a, J k I; W9 g- M } % h2 K$ ]* N# l: v2 I4 Z}
$ s" ]) `( ?; d- H
////////////////////////////////////////////////0 b5 L; Y$ _5 |1 p; R3 F void Process(float c[][100],int row,int vol) * H5 \5 P' E x4 h& h{% P( a5 c+ k' q) B int i; 7 X# J. Z0 |1 T6 E c/ [ for(i=0;i<n;i++) ( l+ ^: d3 @# e" z( h if(i!=row)c[vol]=0;$ k( A t$ f( m: A } 5 l# s9 K$ p. T1 t4 @4 J1 z//////////////////////" o2 C$ h# j0 X' M void Start(float b[],int code[]) ; O) O! D$ V' N5 M6 P{( s0 @# c s5 U( E9 j6 W, { int i;; _& m5 a+ j! B! { float nget[100][100],nlet[100][100],net[100][100]; 9 U, Q# h+ I/ I$ }! O1 D indexe=indexl=indexg=0; ( C/ m) s3 k2 |, p for(i=0;i<n;i++) : m! K( N+ V# d4 {" N { 9 B0 T1 K) ^" ~/ F8 _' c if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}, N: g; R, U' p3 L/ U& b: ? if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}, z2 B- s4 j9 s. i& } if(code==2){ 2 D; m- U$ l5 ~: A* ^7 l: r net[indexg++]=1; + Y/ o C0 g' H2 s& j nget[indexe++]=-1;: M7 d& I5 c& ?# a Process(net,i,indexg-1)rocess(nlet,i,indexe-1);, H6 U* c# e- _/ w, M: a: ^% G }! g5 i! _: l; E/ K }- \4 R. R) `% K& Q8 U s=indexe+indexl+indexg+m;6 _- Q9 G' Y$ t4 \ Merge(nget,nlet,net,b); 8 C0 j1 V6 b+ b$ b ProcessA(); ! U2 D; k9 C. @+ l2 T+ x4 X InitPrint(); # t% h4 ~/ e2 Z4 E Xartificial();% I3 m% U: b6 r9 j }
/ K" R( j5 y; S; t: T# O
void Simplix()//单纯形法 ( {, l% Y/ [" {, y) K# R5 m{ 6 U+ z. h. C9 O! t1 A: i7 W4 V int in,out,temp=0;/ G. |. V" ?7 h7 @& v while(1) ( k# m! i' D) D) Y& g7 e- Z' B { # s! H! [, Y3 d% n. [7 ` jckxj();; N6 Y" j8 @" I2 S) o2 t Print(); 1 J0 r N* y; V. H Result();5 Y5 D! W! f! }4 | O: j if(!rj()) in=Min(); " S m: x2 @- z& M; v" n else{ / K5 `& c+ F3 Y1 @6 z if(indexg!=0) * K$ W! |: W3 s. Y1 S1 i JustArtificial();+ b' D; r$ `, y" [4 X PrintResult();- c M- D0 X0 G return; 5 @$ v' z& ^3 a8 \, j. ~: Y } Q4 f' I9 A5 l% H: T if(Check(in)), g! D. `. p6 I1 A# f {; K9 b0 I" v: P& n8 p cout<<"No Delimition\n"; Y8 Q& W2 D! `( M6 q) T return; " |% M! w5 b, @& l& o }6 O# @# R" \: ^4 Q out=SearchOut(&temp,in); / M- ^- ]; H2 a: Y, B, @3 Z Mto(in,temp);; `0 h+ W5 v2 g$ }+ Z Be(temp,in);0 Q7 T) V, k+ X# ]; t% G Achange(in,out); ; S9 _& M" r- |' K8 f% p }! W( K# P. r* o, W6 ~% |$ M }
6 V, |; H& Y6 m2 p
void main()' V6 H; v5 R, A- B {! h. |* I8 U- @4 T' F3 J$ F+ l int code[100];//输入符号标记$ ]( G& w2 e. t2 d0 w float b[100]; " D4 \0 U* {5 Y" b$ M Input(b,code);//初始化2 _7 E* Y- s! `; Z) o3 ]: q% ?" v# w5 ~ Start(b,code);//标准化行8 r/ |5 G8 a: l! g E4 N Simplix(); , F) ~& H, j' d} E/ _* g) w q+ i2 {# m