单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ # a" O S9 j4 R; i- P- K8 Y$ Q 4 k; d5 R+ ~* {- M/ N

#include<iostream.h> #include<math.h> # z( b! v0 S, t8 y# b+ Z( bfloat matrix[100][100],x[100]; int a[100]; int m,n,s,type; ( N/ P V G( Y7 _( z, g8 Lint indexe,indexl,indexg; ( J: z( U: L0 I% c///////////////////////////////// / G; p6 d5 p w# {, x0 ~void jckxj()//基础可行解 1 z2 B5 W. B, h g7 z. ^{ int i,j; for(i=0;i<n;i++) for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) 3 d1 J, L; J. I1 r { x[j]=matrix; 2 V5 ?5 i. A4 L4 E5 l( T, e7 t5 Q f j=s; } ' X( a2 M, C/ S6 i1 a1 F for(i=0;i<s;i++) / ?1 h( J* I9 `% E' i) e% f) U if(a==0)x=0; }

int rj()//基解矩阵 ; k$ p# c: K: `8 E# X{ int i; : ~- E7 D r( U for(i=0;i<s;i++) . D/ A1 r0 L" d7 B8 ?! v* K: Z* I if(fabs(matrix[n])>=0.000001) 3 m; e9 K4 A" I3 @ s2 N if(matrix[n]<0)return 0; return 1; 0 }+ z' I8 Y a: n, f @5 V" [8 |} % w+ z5 e) L+ I0 ?6 Kint Min()//求最小的 { int i,temp=0; + f7 |+ s+ S3 y1 \- v4 k* m float min=matrix[n][0]; / K& W* e6 D1 d% n4 \ for(i=1;i<s;i++) , P$ } @# ^! m5 F if(min>matrix[n]) 9 a8 ^) ~1 D6 N3 y) C { min=matrix[n]; temp=i; } 4 d' q% {9 w: o return temp; % C, S1 J* {, M' L& D9 C; u} ) C2 c4 r# ~( x///////////////////////////////// void JustArtificial()//人工变量 { 4 D" l2 n9 \9 r$ Q int i; for(i=m+indexe+indexl;i<s;i++) , @3 s- f/ z2 d if(fabs(x)>=0.000001) / [* h% P; t, P) Z" b' ` { cout<<"NO Answer\n"; return; } } ///////////////////// $ F, A9 T7 \6 _: Q A: l$ z( Nint Check(int in)//检验 1 X+ |8 O+ D4 J# @{ int i; + G8 w' ~* S0 S) y/ K float maxl=-1; ! u! `9 S) ]0 u3 u for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) maxl=matrix/matrix[in]; - l* D" `8 |+ h# U9 g: w if(maxl<0) return 1; return 0; 5 Q; J& s0 s9 c. w} ' g) ]# H7 T! }- vint SearchOut(int *temp,int in)//出基变量 { # u% [; [2 b3 X& {0 w, L) u int i; float min=10000; 8 V" \: ~+ B4 z7 D for(i=0;i<n;i++) 4 s& C) R$ ~6 @, f7 o* \ if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) &&min>matrix/matrix[in]) 0 x. i5 V0 l, Z4 e { % q$ u/ s- D0 C3 N! r c. V min=matrix/matrix[in]; 4 c3 |8 c% s% ^ *temp=i; } 3 f* S2 m _3 L% t& a, c/ V for(i=0;i<s;i++) l5 L8 e4 r4 ^1 g if(a=1&&matrix[*temp]==1) return i; 7 ~$ \$ Y/ A; t* }( m4 Q2 {* |, O4 g} 6 U: q: d$ j) p7 @" L) m///////////////////////////////// " y) o$ _( v* @* z4 m+ @, F/ ]void Mto(int in,int temp) 9 @1 P/ W- D! }5 h$ T9 x. w6 ]{ int i; . k) |& ]" j) Q; i% N3 u$ ?! A/ k for(i=0;i<=s;i++) 4 q. O8 g! T. z( `8 M1 o8 }* K |' X) A if(i!=in) matrix[temp]=matrix[temp]/matrix[temp][in]; $ o. g9 ]6 U; K, ] matrix[temp][in]=1; } ///////////////////////////// & A7 a* C" x- e% wvoid Be(int temp,int in)//初等变换 { int i,j; float c; " [9 b" o/ n. s5 h5 e for(i=0;i<=n;i++) { * w9 X+ }2 ~# Y! p3 [3 q c=matrix[in]/matrix[temp][in]; if(i!=temp) y+ Z& H! a+ A8 ?7 C; Q6 F. r- b for(j=0;j<=s;j++) : T+ @6 K1 Z1 a' T) ^5 M8 h( M0 z8 A matrix[j]=matrix[j]-matrix[temp][j]*c; Z5 Q8 Y3 b' W- E } } / e* w: K! D( ?4 g////////////////////////// void Achange(int in,int out)//出基入基转换 / I5 g4 B, N8 _4 [{ int temp=a[in]; . _) d8 E- e+ b* H" g7 I a[in]=a[out]; a[out]=temp; } //////////////////////// . H5 J: U8 Q2 n5 Jvoid Print() { int i,j,k,temp=0; for(i=0;i<n;i++) { for(k=temp;k<s;k++) : Z5 N* U9 N# f! E; |5 r if(a[k]==1) ) N7 a* r7 ]4 O( I5 v { cout<<k; temp=k+1; % E" K$ S( O9 L+ p k=s; } # S' k6 b( l; B) E for(j=0;j<=s;j++) ) C& J$ a6 U! ^" ^2 n* N+ F cout<<matrix[j]; 7 y$ \4 n2 ?; q# \; E4 ~$ A cout<<"\n"; 3 e4 Z4 q5 ~4 u9 s, k1 v5 f# S2 ^ } cout<<"Rj"; + O! c, o- U4 z% d for(j=0;j<=s;j++) cout<<matrix[n][j]; 7 H% @/ i$ Y' L9 w cout<<"\n"; } * b( c) l5 f7 P//////////////////////// - _( I+ J# x9 b. S+ Hvoid InitPrint() { int i; $ O- t$ a4 @- s cout<<"X"; 6 d9 g& K% ^4 i( y& n for(i=0;i<s;i++) 5 X; C5 O/ F& a+ [2 m2 M6 ] cout<<i; cout<<"b\n"; - l& F% M* E* B- L' k& C cout<<" "; ( {7 D) C2 `1 \9 ^7 e j cout<<"\n"; } ////////////////// void Result() 8 p' D% y. ^; u{ int i; * u% X8 M1 N4 D1 _ cout<<"("; for(i=0;i<s;i++) cout<<x; + M# j# t0 K' z9 C9 K$ T0 l7 j" L% n cout<<")"; : S! b& w" G* l4 }8 Q7 r$ K if(type==1) cout<<"Zmax="<<matrix[n]; ) p1 S8 ?9 ^3 n) M$ z$ j else cout<<"Zmin="<<matrix[n]; } : b9 } v, A7 c1 _9 a, X" W- _9 v3 l////////////////////// 3 C6 ~9 T3 \' j3 Y5 ?! ovoid PrintResult() { if(type==0) cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; } 6 y5 R4 B! d3 N$ I- G' a//////////////////////////////// void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 * p9 e7 n3 w8 [6 A) u$ [6 G{ int i,j; for(i=0;i<n;i++) { for(j=m;j<m+indexe;j++) if(nget[j-m]!=-1)matrix[j]=0; # k! T8 \: Z+ S4 E/ L# {* Z3 B else matrix[j]=-1; $ X3 I9 V$ k' n* p7 w. s U" G for(j=m+indexe;j<m+indexe+indexl;j++) * M+ @9 g6 h1 R$ r) `2 u8 `. W) K if(nlet[j-m-indexe]!=1)matrix[j]=0; 6 f) H& n9 L/ ` v; e" r v else matrix[j]=1; 2 P% N2 l* f# @ for(j=m+indexe+indexl;j<s;j++) ! P% M* |* o! W if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 9 X. a% U6 ]; d) ^ else matrix[j]=1; 2 e" n9 |6 @0 N ~7 r% H% p' Q+ B } ' [6 a8 J! s9 c* V& j% P2 ?' l for(i=m;i<m+indexe+indexl;i++) . A# H4 n) N# w- `; d matrix[n]=0; + G, K* W/ c- r6 @' Y2 q for(i=m+indexe+indexl;i<s;i++) matrix[n]=100; 3 d @& J K- X5 C matrix[n]=0; " e% x8 X1 e1 h1 Y- Y3 i}

/////////////////////////// 6 k' h. t; A( e0 d# x4 Kvoid ProcessA()//初始a[] + P5 ]# J3 q6 S. n{ 3 D* z& }1 Y( M% q int i; . I, Q3 E2 ~' V+ \1 X) W/ w for(i=0;i<m+indexe;i++) a=0; for(i=m+indexe;i<s;i++) 4 J- p' V, e9 a( U1 d5 e a=1; 3 ~8 [6 L0 u% \3 u8 w}

2 k9 d' F% e5 k6 u' |

//////////////////////////////// void Input(float b[],int code[]) 3 U4 a/ V9 V' x7 J" l{ 7 A8 D& B- o9 Q0 B% d+ C' K1 p int i=0;int j=0; 2 t( I+ [' b1 l' `/ p3 T) m/ ^9 r cout<<"The equator variable and Restrictor\n"; cin>>m>>n; " v! w& c+ i& U0 T for(i=0;i<n;i++) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; , o# r# ` L5 `6 I8 {- ? cin>>b>>code; cout<<"The 系数 \n"; for(i=0;j<m;j++) 7 v0 \7 X# U, D& X) e/ V; H: F cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; do{ cin>>type; / o! E. S$ l7 x) B r0 J' o if(type!=0&&type!=1) cout<<"error,ReInput!\n"; 4 o- M& T, I8 W2 w5 a }while(type!=0&&type!=1); 3 f* c' G/ M! c5 ^& F0 _9 A# E cout<<"the Z\n"; for(i=0;i<m;i++) cin>>matrix[n]; if(type==1) & H3 p$ P2 F+ Q for(i=0;i<m;i++) ! D7 V5 Y3 U7 J3 B+ ~ matrix[n]=-matrix[n]; 8 [' W( P$ L3 `% y0 F( z/ q3 ]}

d: [3 p4 `4 ~6 Q* ~2 I" Y

- l8 n) p" A L4 e////////////////// * Q2 e$ a% M7 H) C( q5 lvoid Xartificial()//消去人工变量 { x8 P* C! d0 w5 ^ int i,j,k; + x3 l4 |2 q' ~3 k2 [6 C! { if(indexg!=0) ' ]: E/ p/ h& r/ @6 G { 7 x" Z' {: Q( S* [ for(i=m+indexe+indexl;i<s;i++) , h# f$ K) p! ^; p, ]7 f) H$ w" W { 9 d v+ A e& p5 L0 ~" |% q1 M for(j=0;j<n;j++) if(matrix[j]==1) { ; ?( A& D5 q# Z+ X7 a) P, J$ J for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; } } } }

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) { 0 J+ r5 y, @% O; M; B3 P int i; for(i=0;i<n;i++) . {8 C$ q- j8 P; q6 ] if(i!=row)c[vol]=0; } . x! u" T& m' X4 p" D: C////////////////////// void Start(float b[],int code[]) 9 s& U' v+ r* z4 L) X8 e{ int i; float nget[100][100],nlet[100][100],net[100][100]; - b: S5 \" l/ ~( e5 m indexe=indexl=indexg=0; # `! K3 v: G$ Q for(i=0;i<n;i++) { 8 |) f8 T$ t% `: L' J if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 5 s' y$ ?8 O1 r4 t0 e$ L# ?1 } if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} % R! i1 N0 n7 W if(code==2){ G7 t) b4 {4 z$ F5 P1 X4 u, ]0 z net[indexg++]=1; " ]7 A: t6 U3 e- L) w4 p8 ?9 w nget[indexe++]=-1; / m' X9 e5 P2 t/ t& V) S9 r Process(net,i,indexg-1)rocess(nlet,i,indexe-1); } ) U( ]5 b$ A( R$ @6 g } s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); ProcessA(); $ s5 s* B$ C, G- [ InitPrint(); 5 ^) G& d+ Q$ ?5 f% F" m/ o% R; Y Xartificial(); 8 f& N+ T: C' s1 j' [! ^' K& X8 Y}

7 R, s- R9 N$ o

void Simplix()//单纯形法 { ( c0 N( W3 q+ {6 j int in,out,temp=0; while(1) & u8 P& N2 \8 t7 l! ~; b) [ { ' |; M, ]$ h; X( Q9 G jckxj(); " [( g- x7 ` n, w! g7 T P7 r o$ H Print(); ( n$ O; ?+ ^/ O* q Result(); $ \2 U7 A0 b% V1 `2 y if(!rj()) in=Min(); : y" w/ V. ^7 q0 E2 N$ W0 Z else{ 4 `: L8 v! Y$ u if(indexg!=0) JustArtificial(); PrintResult(); return; 5 A5 g r) M7 `$ J' w: t2 J } 9 x m- T: q$ W& c, j4 U if(Check(in)) { cout<<"No Delimition\n"; return; 8 Y/ @" p8 K' I2 r6 O0 S } # }; s7 B: O8 {( e! L# m" H( K* k4 Y out=SearchOut(&temp,in); Mto(in,temp); - G3 u P* ^* o+ E+ f: K Be(temp,in); ) ?2 T. |' G+ L9 h# S* g9 z% h Achange(in,out); 8 ]6 G \5 a$ Z9 G4 f } }

) X, F% U3 S& x. Y( }; t" a

void main() ) K* x4 |$ T( E' X& ?{ ; y) p' d9 I& ~; r int code[100];//输入符号标记 float b[100]; ! D+ m* L+ N3 ^( K$ V }1 p5 q% E Input(b,code);//初始化 - I, {% U- d* w& g* @ \1 |$ }) S' n Start(b,code);//标准化行 3 U' ~0 n- a' G9 O L; b Simplix(); } 3 c' V# m8 N3 L4 I3 O

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

资源分配问题可以用这个程序吗？

monkeytail

哇，楼主强人！

monkeytail

单纯行算法是指数算法啊！

bnulj

这么长！看不懂啊。

mengfanqi

so well!