单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h># T- G7 x5 e2 I0 H/ `5 }- r #include<math.h> 5 f0 R! M; C7 L b {7 `9 ]% F2 Hfloat matrix[100][100],x[100]; , G5 g" ~, W4 e7 ]int a[100]; , b; C6 e7 g$ gint m,n,s,type; " d1 t0 x! T C0 n7 ]% vint indexe,indexl,indexg;0 `" u8 c) S; b! X# q6 o0 C /////////////////////////////////7 R! b' H7 U* _) c2 G% S: E void jckxj()//基础可行解 L6 R- E% m! L" ^9 U' @" ^ Y8 s { : g$ B- ?( j& G @ int i,j; ) O1 c. |* l+ o9 A7 v for(i=0;i<n;i++). H4 Q% T% X0 Q6 I for(j=0;j<s;j++) 5 r, ?- s0 E% W$ R4 ~ if(matrix[j]==1&&a[j]==1) . g# r. a* X* i: W { ) T0 M. ]- b' Q. ] Z9 i x[j]=matrix~~;/ D0 W4 k: H2 }& U+ ?! V j=s; 6 H) f: S: T2 U- z) ~9 \, v } " W0 n3 S( q8 f. k( i0 [ for(i=0;i<s;i++) 0 }+ l2 Q* d) P6 V5 v. q+ q if(a==0)x=0; - G, q$ l/ M9 t+ Q' J. c/ G( R- ` T1 b}~~

% p8 g1 c1 Q$ g2 }) r- u
int rj()//基解矩阵 : g/ u5 u a" y{& S+ \ x- N! F. ~' | int i;1 O. l$ b1 `* R5 r for(i=0;i<s;i++) ' u" P. j0 c! ]2 k' e1 `; D1 t- p; ] if(fabs(matrix[n])>=0.000001) , M, Y9 ^/ x, B8 x8 H6 g if(matrix[n]<0)return 0;9 e, u5 g9 Y: S7 x return 1; ! A& z+ e" e6 n$ |} 9 Z5 f5 @$ Y4 h4 u. o) u$ q/ V( s7 p' tint Min()//求最小的' M# S- R w2 `! D9 ^5 d { , Y3 p8 E3 ~( O- U: r int i,temp=0;$ Y3 d! r* i1 V6 J float min=matrix[n][0]; & h! g( K; D; l, _" U# _6 L3 r for(i=1;i<s;i++)% L# |* c2 D- ], B P if(min>matrix[n]) ) k6 n5 t$ _% c( z' C8 k& m2 R# ]+ @ {* r/ S% m* _. A1 G! v min=matrix[n]; * o) ]5 R; N; X: U2 E% Y& G temp=i;; _ U+ n6 i+ Z/ x# H }' E8 v1 q1 j. ]: R/ N return temp; " I7 M7 [; l; U: Q% i' }- ]8 C0 @}" D t& V0 n) }1 c /////////////////////////////////' H3 I4 ], z# l7 $ m void JustArtificial()//人工变量' X Q1 A2 $ P6 U2 b: E {4 e4 N& V& c* G2 B int i; . @9 S8 [) q$ T( } for(i=m+indexe+indexl;i<s;i++) g; l% n5 l- ^& \5 ?0 u if(fabs(x)>=0.000001) 4 I" M9 i0 H" F" m/ b3 n { * U0 t# S' K9 `/ U5 V" a cout<<"NO Answer\n"; 3 b( m0 K( q7 Y3 K } return;" c, p8 ]8 T* ?6 } }6 Q9 Z% A0 J4 _; i4 v7 M' a9 n } ' @+ R; b( v, l8 p. l% }///////////////////// ) F |! X) y2 A0 L; U! y2 iint Check(int in)//检验8 `, q/ R( U) h$ Y' V7 z9 v) E { p. O- P2 N5 E$ s+ K' c5 [" X int i;! `2 V" H; p, D2 x5 h; A0 o# e float maxl=-1; % G h8 W2 b/ K3 c. }! s# P& w' K8 M for(i=0;i<n;i++)( |1 B( F- g+ P: l if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])# c. L/ H$ p# r* s$ _* h L maxl=matrix/matrix[in];& D, t4 H% [4 ]: u) P f if(maxl<0), B$ E9 p! A5 p) _ D" ` return 1;' v6 g) A# f. {) d$ d0 @# B1 c return 0; 3 G- M Y9 X6 a( z9 U* r, n) F} 1 ]& [7 z% w- u! K5 S* c" ~8 Vint SearchOut(int *temp,int in)//出基变量 ! e5 m; v. g, J) Z& `{8 y6 C0 [: ? d* m( S- v' U& _ int i;% O& B9 B2 u6 X/ N# Z7 N2 ~2 r float min=10000; 4 J! V/ |1 }% k' e3 Q; N for(i=0;i<n;i++) * m4 q2 E3 n+ F, |1 C" U if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 0 [5 K1 r; Y7 \ &&min>matrix/matrix[in]) 8 w9 x0 [$ R: C {& p# |# b9 \, z. A* w H% Q min=matrix/matrix[in];; o. t I1 i! H *temp=i; ; f+ M/ @- |( N. ~$ b: B9 T } " D5 w* r! i; y5 O0 S for(i=0;i<s;i++): Q+ H; H# [' @5 j3 m. N) s if(a=1&&matrix[*temp]==1)) P- i& a9 E ]0 @' {! N" m return i;6 @6 H* N5 \& S# D$ M% u/ w } 4 H% g! R5 D! J; f/////////////////////////////////' N3 f g5 m6 f1 ^! G void Mto(int in,int temp) ! Z9 w3 c" _! X' l1 p# j{. Y# J; I% J" n, C+ F int i; # m# G' r5 ~* p) H9 l6 D4 f for(i=0;i<=s;i++); g" x' H& s0 c# \- v: n if(i!=in)& _7 Z9 { ]5 l; c' X% P i0 ?5 X6 k matrix[temp]=matrix[temp]/matrix[temp][in]; M2 j7 V- g7 `9 _" o matrix[temp][in]=1; 0 D7 P/ R3 }" h6 s}% U" g8 `" f% n( H; L% r ///////////////////////////// 0 x+ C p G5 l7 Z4 \void Be(int temp,int in)//初等变换8 ]9 S* ~& S8 Y! h) @ {$ C4 | W+ Q0 V8 W! A, v int i,j;9 a3 i E7 |" u; Y* q) b float c; . k9 M! `# _+ ~! a. v. J1 q2 G for(i=0;i<=n;i++) ( b) T/ I/ u' w { 5 S5 B: q: e' P c=matrix[in]/matrix[temp][in];; U( s: p2 y/ b' S; [ if(i!=temp) , j/ y$ U/ r, K for(j=0;j<=s;j++)" S1 ]# l- U5 ^$ l# `& g matrix[j]=matrix[j]-matrix[temp][j]*c; 9 O# U1 ?* x2 a) V* S" i' d }% `" N7 k& b/ Y }) L: O$ s( ^, W //////////////////////////, g' G {9 o% U: J/ \! B void Achange(int in,int out)//出基入基转换: b/ M$ T7 v, g* N7 _0 J {% l/ q: b- }0 `5 [$ N5 G5 Z8 j int temp=a[in]; : w- q' T% L8 Y. j a[in]=a[out];9 q0 d8 i5 h h& n$ r a[out]=temp; $ i1 _1 m) B* Z# d2 }} 9 X4 ~5 e F" `. d( }////////////////////////2 I/ \2 {$ @" w V% H; T void Print(), ?3 T n; a4 U" H& g' y" j" f { ; X+ r2 m: P. ~0 q; V int i,j,k,temp=0;3 c' X8 m2 Z4 ]. E for(i=0;i<n;i++)7 p3 X- w8 c% i5 z {( U: i- w0 b. O- E' _. W for(k=temp;k<s;k++) , C+ c% V0 p* w! y* y1 B/ Q$ l6 u if(a[k]==1) : {: n% i" L. ]1 a {4 h# p7 b9 g' ^! y3 P7 p cout<<k; 1 G3 V Y; P) Z. [4 K temp=k+1; % p) U! o F, @" t1 P9 C) h; G3 P k=s; % \+ M' l0 U/ X$ H( D( _ } / s9 f; L7 X4 ^, e( \& C! ^3 s for(j=0;j<=s;j++) 0 f C+ W: [$ q, r' s+ l" K6 ~ cout<<matrix[j]; . S2 D$ z% @' Z. j2 ] cout<<"\n";0 d: c* {* d" M* B } ( F% o" y+ o2 Q" Z; n0 c cout<<"Rj"; 3 V! B/ `9 f) H1 o6 u& v for(j=0;j<=s;j++): Q& Q1 }' {/ O3 Z' k cout<<matrix[n][j];5 z7 t! h7 L2 V4 u6 q cout<<"\n";7 V" Y0 i2 H7 n } ! M& V3 M0 m$ A) }1 k+ ]2 w8 f////////////////////////( z% y4 R9 k% d4 Q% ` void InitPrint()( b) `' D+ Z( }5 _3 i2 Q: P { " H* v k1 N# s6 |8 `6 ^ int i;$ ~$ o) H6 l( f" [; e }/ O cout<<"X"; G2 n5 r# Z3 ]- }- b/ p! Y# P for(i=0;i<s;i++) / i. A6 h" N% Z1 e5 p cout<<i;6 n ^3 }. L" @8 } cout<<"b\n";" ]3 C: Y, s3 n" r+ A/ L cout<<" "; 8 `( ^ g4 T; ~6 P6 n cout<<"\n";% r/ D! ^4 w+ v4 ~! X+ l2 c } 9 c" \. {& a' s d//////////////////- z0 A: _; U+ P5 v" ~ void Result() 8 k" m5 Q3 c( p; n{+ K# G8 T. f2 h! P# Q( ]4 [ int i; ( A! L4 h6 I% B# |% j8 E cout<<"(";' f: Y9 F p8 q1 S; h( C* c: d for(i=0;i<s;i++)5 L5 h1 c/ E8 v* Y# r7 g cout<<x; 5 D7 P9 `& _' b cout<<")";, A! ~' M$ Y- q/ E if(type==1) 6 T- ?% d9 G" `, K$ s cout<<"Zmax="<<matrix[n]; ; G/ v& X- j( V1 f8 U- h" | else cout<<"Zmin="<<matrix[n];6 p9 Q, n6 u) { w" T }) y) B6 H2 ]/ h9 E4 p9 F$ ]. ? //////////////////////8 o! U3 g0 F3 w7 o4 f void PrintResult() z, T, p# q( l! \6 n0 y* \" m{ & S: T) t+ C! V% m0 s if(type==0)! q. n' C" h: G. S# g$ k% {0 k cout<<"the Minimal:"<<matrix[n]; : O. X5 U0 D# z# I* m: H( V( O else cout<<"theMaximum:"<<matrix[n]; 8 F4 Z. {- y6 Z3 L# K} 1 O1 ^) n0 Q" T; u& g% G/ t//////////////////////////////// 6 b: w0 L, _8 }: T' L$ Gvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 9 H9 Y. j4 `3 Y9 S; G! N9 S{ 0 J* G' x1 w0 U' n! i int i,j; U- F* K! G8 K% j for(i=0;i<n;i++)2 |% m3 Q- S' S% m4 h; O+ c) g { 8 X. Z+ n* r3 O t for(j=m;j<m+indexe;j++)' W& _2 z( S9 Z2 w0 e" @+ k# x if(nget[j-m]!=-1)matrix[j]=0; / M; D# T. m+ l0 ^' M else matrix[j]=-1; 6 }% |# c& m' @1 e- C for(j=m+indexe;j<m+indexe+indexl;j++) * q. J7 M- {7 M ]: B, M if(nlet[j-m-indexe]!=1)matrix[j]=0; 0 r& P! g7 L. a4 W! t4 d7 t) Y else matrix[j]=1; & K* c9 Y/ ]+ u( J; L+ b for(j=m+indexe+indexl;j<s;j++) , f3 H' v* o; \ if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 5 U1 A. j/ |( ?2 d else matrix[j]=1; ' c5 b, T9 U9 o9 u- i }9 p, Y1 `! c4 V3 e' c& M for(i=m;i<m+indexe+indexl;i++)& |8 S+ s8 O, ~% I+ d matrix[n]=0;9 f4 b1 s' O e/ W& R for(i=m+indexe+indexl;i<s;i++) ' r3 a, m0 b s matrix[n]=100; ( G% Z9 O% I, {' j matrix[n]~~=0; X0 H; u+ Z% l) H}~~
# x. m: n- \" f( W0 T8 ~* a; P }: [
/////////////////////////// 1 T" F J) ^5 J, xvoid ProcessA()//初始a[], Z/ E8 A$ ?% k; k { . P: J* K" e t8 i5 K% y1 [& X int i;9 [' L0 q; f+ `) v f8 s for(i=0;i<m+indexe;i++) 3 _! Z# o% s u3 m a=0;8 F! U3 g: r% Y2 B ] for(i=m+indexe;i<s;i++) z) r" D6 d" P$ Y( j a=1; {+ N5 X5 y2 V9 V }
8 p. j; u2 d8 ?) r) T
////////////////////////////////0 `& V- s1 y) f+ j$ d void Input(float b[],int code[]) , [9 [ C5 }$ z1 t$ h% t{8 J. s, T) z- J( ^/ D0 c- Y int i=0;int j=0;. i& s- n7 Z# G9 F" u- ]" D cout<<"The equator variable and Restrictor\n"; ' J* X6 q! P G! f. ]+ a; u, ~( D cin>>m>>n;+ M* ^1 ~$ r* D& x- [9 B- Z6 N for(i=0;i<n;i++)* z8 t$ ^ U! y- M+ K { " k5 [5 Z/ I' U7 N cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";! w3 R p( r7 s+ t: F6 K" `! ] cin>>b>>code;6 ~. \, x. w7 u- O. W4 G- z: R cout<<"The 系数 \n";, B" S3 V% ]7 N for(i=0;j<m;j++) @( M4 _1 G a/ g4 ~5 W; Y cin>>matrix[j];) ~- c! q9 ~7 p! v) v" U }8 t) R6 m3 q8 D. D. C6 o" o& Y cout<<"the type 0:Min 1:max\n";5 G- w$ M6 {& @7 u0 f# l }' j# u% b do{; n! X2 V8 Q3 o/ d Y9 O) g cin>>type; & h- j0 ` i0 H8 Y% @; Q0 o if(type!=0&&type!=1) d4 {$ D% S: W0 c8 g% z cout<<"error,ReInput!\n";9 y3 a- f3 a; I }while(type!=0&&type!=1); ) d1 [: c" p2 T3 h4 B8 Z/ ~7 y cout<<"the Z\n"; ( [2 U# M) b; f3 |2 P9 v for(i=0;i<m;i++)7 P, b4 f b) f9 U) O cin>>matrix[n];* F" W$ U$ K- l. A7 E2 b if(type==1) 7 r! d4 a5 \* ~- x5 S9 t1 W0 l1 G( N for(i=0;i<m;i++) : k; K5 T1 i/ l0 L& |/ b6 j matrix[n]=-matrix[n]; , a. L8 f( C* o0 \}
+ U1 f6 M4 x2 y% X+ {, Y1 m9 Q
" l# i/ p- Y0 ?' V4 m ////////////////// % B! U ~4 f0 s( W# ` void Xartificial()//消去人工变量 $ ~1 u% v8 y# R+ G7 p u{# @9 f R+ o9 |: l5 q: T; _4 W( _# H int i,j,k;( I- L2 I4 b5 q7 a6 P) A# J1 c if(indexg!=0); Z+ i/ _& M4 N5 v+ u; C {- s& F6 `* O. G' F for(i=m+indexe+indexl;i<s;i++) - ~ G2 i+ q& L { % D% }; x( p. | for(j=0;j<n;j++) ; m( V* L9 e1 I) c% M( G if(matrix[j]==1) 1 r6 N! u) J9 X ^: i$ \1 c {& k" Z9 Y3 X* P6 o2 D9 o for(k=0;k<=s;k++) 4 R/ ^+ g( I7 N ?2 J% e8 J matrix[n][k]=matrix[n][k]-matrix[j][k]*100; : M; H) I2 [* F% t( p- G3 } j=n;- _+ b- V* W$ M2 X7 S* x1 ^ }8 w4 A+ F5 k! y3 M; @6 v }6 |% P/ K( a- C @- y& c& G/ Y& b }7 e9 Q1 `/ K7 ] }
+ @7 T" K" b q1 P: X
//////////////////////////////////////////////// ( x9 Z) }8 } H1 Hvoid Process(float c[][100],int row,int vol) 8 \* j$ X3 [$ m7 K{; L6 A3 F A3 A$ p. n" j: V int i;" ~+ ?% O! c* l; E0 D& g for(i=0;i<n;i++): |" a* d! g) |. h if(i!=row)c[vol]=0; & B0 a' s, _; q! W: _% c}3 L5 j! a) c. b8 b ////////////////////// $ J- M6 w2 _* x7 ~4 U5 c7 ~void Start(float b[],int code[])! p6 V1 V# m/ B0 j0 z {# M. r- I0 C/ k int i; + H! v+ b$ \3 t float nget[100][100],nlet[100][100],net[100][100];9 }+ _9 z( g1 T q; Q6 y indexe=indexl=indexg=0;+ v$ V1 h& j' u* q for(i=0;i<n;i++) : E6 R8 }' }& f* V) p* B4 O; |5 u {: R. R$ {1 f* }( @ if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}8 n5 X3 @% N' I& D' M3 b if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} # d9 ]2 y/ U* [2 X: D if(code==2){0 z9 W, B6 Z B0 T+ T' O net[indexg++]=1;+ U; M' \: s' D nget[indexe++]=-1;, L( i& E; I Z9 S5 q Process(net,i,indexg-1)rocess(nlet,i,indexe-1); / g" j: V4 T6 ^& C6 S& R }' |$ X+ G' `7 T0 n! S/ Z5 X } + @1 X- ^3 ^" |: c& N. M1 d s=indexe+indexl+indexg+m;# V, K9 Q5 b) f; }% F; r" P Merge(nget,nlet,net,b); " L" f" o, |5 h2 Y' Z8 Z ProcessA();6 M" N/ ]6 t( y: n, m, B5 @3 u InitPrint();' H1 g* U& {; p- E9 w$ q4 O Xartificial(); " Q) _/ e7 H, W) d" V) S j}
* Z) d, l, ^: | K" W9 @4 m
void Simplix()//单纯形法 7 n4 M+ b( D' k) j# }/ B{7 E6 ?- L+ Q% x5 P- n int in,out,temp=0; 5 y& i2 Z& E1 q) U( K0 z' B; f while(1) 0 d2 Y) x9 K4 K J6 v {7 n3 K- z- M' $ Q# `8 c9 r. T jckxj();" Y! u9 I- O, M Print(); ) z1 T% x6 f b8 V. Q1 u, E# F Result(); 2 K8 P* s9 U7 g& b' v; E6 @ if(!rj()) in=Min();, P, W5 u( c D; ^: z4 ^% E else{1 @6 }- m5 o# d if(indexg!=0)2 m$ T/ {, V Y( O8 D- t) _8 { JustArtificial();8 x- z$ v! ^; E% r' C PrintResult();% Y) C) m' T1 q5 d return;9 ^) @/ B2 C3 Z }) k K! N2 a$ M" j& r- z if(Check(in)) ' t, m: q5 $ Q* ^9 c& s7 ~ { 0 p* M& i+ [* U cout<<"No Delimition\n";7 i$ b3 S v; h% w! _% m# T$ B" ? return; G/ v9 c. ^2 c0 t }! Q2 Y& J4 Y: t5 ` out=SearchOut(&temp,in); ( u" S/ Y; E4 ~$ f Mto(in,temp);9 h2 P- ]8 |% p; r5 P* Y Be(temp,in); : x" q0 @2 p: m, h& j M& \5 i$ } Achange(in,out); 7 o; |' K+ T# L, [' _ } L6 N6 n; ^: s% y1 s" Y. b3 R }
. W9 W% `$ E' P2 L ~; _
void main() + \, {6 j0 S3 @3 z/ x% e{ ) Q7 |) b7 t; V- Q' G: } int code[100];//输入符号标记# \! h# F* S- T+ C5 m float b[100]; 9 D2 k/ c. G, X Input(b,code);//初始化 3 k4 I% c; Y& ]; o7 ~# a7 n; i7 a; p Start(b,code);//标准化行1 X4 E9 g6 n" O @* f0 s Simplix();( d: o$ H% A. h3 D } z" O$ J3 L9 E6 h! I7 }