单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ 5 o6 J! y; _2 S0 R% v8 h

#include<iostream.h> * S) W0 S* o6 s1 c/ L' m/ [( L" M#include<math.h> float matrix[100][100],x[100]; . V" G: B3 }5 N- ~int a[100]; * e8 E5 }* x" i5 O! Cint m,n,s,type; 2 T8 D/ L8 G' S' o9 N8 Cint indexe,indexl,indexg; ///////////////////////////////// void jckxj()//基础可行解 { 0 A- {: A% i. {2 h/ \ int i,j; T9 x i0 i9 G for(i=0;i<n;i++) , }8 N1 J. _1 a! u; A for(j=0;j<s;j++) ; G4 w, q( k4 \ if(matrix[j]==1&&a[j]==1) { - L$ F5 G- W0 a4 e5 P9 t1 a5 N x[j]=matrix; j=s; 8 q6 d, O( @1 [1 G } for(i=0;i<s;i++) if(a==0)x=0; }

int rj()//基解矩阵 2 k& {* c7 f% O{ int i; / |" T( A/ y6 O; e+ f! t# b4 C1 R for(i=0;i<s;i++) / z$ }& ^4 N& r8 ]- W' l( g if(fabs(matrix[n])>=0.000001) & \8 o9 S" e y: R if(matrix[n]<0)return 0; . M, Q, y% I$ @5 ]% E return 1; 7 Y' O. |' W6 ^. _ A/ M( V} + Y: H5 `* V5 t( I7 }5 y5 Nint Min()//求最小的 9 p: d- s9 ]' X: O2 k{ . C; B: u) N# S# T int i,temp=0; + e) A I p2 v float min=matrix[n][0]; for(i=1;i<s;i++) ' @6 `9 F2 ^9 d" _1 k$ f( i0 B if(min>matrix[n]) { min=matrix[n]; # K! b5 \) f9 r# P6 X temp=i; } . Y! @7 U S6 o/ d6 t* e return temp; } ( B3 Z1 e. ~; T% e! `% M///////////////////////////////// $ V# ?* V9 }; z: T7 uvoid JustArtificial()//人工变量 { int i; 4 }& }9 u) W: n. v. k for(i=m+indexe+indexl;i<s;i++) if(fabs(x)>=0.000001) { cout<<"NO Answer\n"; & f- |8 r, Q8 @) [* z- `& o return; 4 d) f( q1 @5 c4 D w/ ^2 Z% R } } - K5 a, x7 P+ o///////////////////// int Check(int in)//检验 8 ~) p9 Z0 Z0 s9 K{ int i; float maxl=-1; + Q% N [5 L/ _8 ]3 } for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) : z4 d U' p, z1 n4 j9 G+ I( \ maxl=matrix/matrix[in]; 5 K8 h6 s+ ]6 [/ l if(maxl<0) ( y; D! N, o* u+ V! F return 1; return 0; $ C* t( j# k& ~+ ?, }} int SearchOut(int *temp,int in)//出基变量 { , d% Z" @: \9 N1 s int i; 8 m% q' Q2 `( v2 x float min=10000; l, Q# d ^- e9 I/ a for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) % L n5 F# B" w1 y &&min>matrix/matrix[in]) 7 o) s$ v4 h; A { - {: j2 e( m- X. l* J- O, _" g min=matrix/matrix[in]; *temp=i; } for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) % C/ H; W2 ^0 h' f( U: p return i; } ///////////////////////////////// ; d5 q" o/ @" x* l, pvoid Mto(int in,int temp) ( Q& d6 F4 U# ]: C( v- G1 l7 |{ 3 U+ j( o$ z- D1 I' t* M& | int i; ! M8 d* g3 O' ~/ j$ u2 { for(i=0;i<=s;i++) if(i!=in) 0 V% N& i6 B' V+ M* k6 {0 | matrix[temp]=matrix[temp]/matrix[temp][in]; matrix[temp][in]=1; } ///////////////////////////// # g6 Y5 x) r5 x, x6 u: [void Be(int temp,int in)//初等变换 5 |% l- S$ A. g5 ?( p7 ?) t: r{ int i,j; float c; 8 }: C h6 N& f" a" q: L; ~ for(i=0;i<=n;i++) { 4 }+ _# R* D/ c" _) K# J/ j c=matrix[in]/matrix[temp][in]; if(i!=temp) 6 B$ K/ D; {7 o/ i. F p for(j=0;j<=s;j++) matrix[j]=matrix[j]-matrix[temp][j]*c; } . b/ i" m$ Y+ B( J$ J) ^. Z8 {9 ^} / ^0 Q# R: ^: \! ]; q6 g////////////////////////// - ]8 C" X. T# I! ^, h$ yvoid Achange(int in,int out)//出基入基转换 { # L" x9 M, j- I3 e int temp=a[in]; 7 m$ a2 A: Q4 O7 X; _2 D a[in]=a[out]; 3 P' L$ I/ @4 u6 e" g a[out]=temp; } //////////////////////// 9 h1 y4 g& k+ c+ ?- Lvoid Print() { int i,j,k,temp=0; for(i=0;i<n;i++) { : q& r3 F" K/ F for(k=temp;k<s;k++) if(a[k]==1) { : O$ i3 W# b2 C+ \$ r cout<<k; ' z4 R; y2 Z; b. T3 Q temp=k+1; k=s; 4 v9 }& ?1 V" X. R& i6 V } for(j=0;j<=s;j++) cout<<matrix[j]; cout<<"\n"; } ( J! P9 M% Q2 e( n" y5 T6 D- Z cout<<"Rj"; for(j=0;j<=s;j++) cout<<matrix[n][j]; 9 V' j8 \2 A$ s1 ]* b cout<<"\n"; } ' }0 j4 _1 }) q* c- `5 N9 s: ^( M//////////////////////// void InitPrint() { int i; cout<<"X"; for(i=0;i<s;i++) 3 C$ [# f# ]' W& M cout<<i; . X% X; `) i$ {# ]1 M' s# J cout<<"b\n"; cout<<" "; cout<<"\n"; # i) a4 g/ I0 b} % S$ h+ t5 a" V5 ]( m- }////////////////// g* _8 W, e$ D/ D) N7 m9 yvoid Result() { * F# l$ b- e; V, B& j1 y# V int i; ; D5 q& F: l4 M Z7 m0 l6 E+ ` cout<<"("; ( B$ D1 ^4 i# Y W for(i=0;i<s;i++) cout<<x; , |# h" t0 Z3 q2 h3 V5 M+ G cout<<")"; $ M8 f' z4 H2 I# R# P, P. o8 w if(type==1) cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; } ////////////////////// # L+ ^6 e6 E3 O5 Xvoid PrintResult() { if(type==0) cout<<"the Minimal:"<<matrix[n]; 3 N% t3 {7 M1 v/ _7 b" D else cout<<"theMaximum:"<<matrix[n]; ! Y6 p4 W) {$ I8 S3 p" z- g} $ q' N) I0 w U//////////////////////////////// / U- m6 {1 j; _# r7 S, Qvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 { / r* w0 Z: m d9 e% k int i,j; * s0 r* l/ j3 F+ C4 u# @ for(i=0;i<n;i++) + U/ M: X, K O { for(j=m;j<m+indexe;j++) - v" J7 N- x- L5 M if(nget[j-m]!=-1)matrix[j]=0; ' ]4 S2 E. i& a0 }" G Y else matrix[j]=-1; for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; else matrix[j]=1; for(j=m+indexe+indexl;j<s;j++) if(net[j-m-indexe-indexl]!=1)matrix[j]=0; else matrix[j]=1; 7 p1 y) C# h: R+ F3 F9 R: [ } . q" X6 O( Z: W$ l6 t, l for(i=m;i<m+indexe+indexl;i++) 1 W2 G4 D* w( F& ^7 r0 }9 ] matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) matrix[n]=100; ' V: ^2 h, ?' l3 } matrix[n]=0; }

6 d- u2 X% I J5 ~; J1 I

/////////////////////////// 3 v. o% J& p0 Z# ]void ProcessA()//初始a[] { 2 X2 ~; o5 K( u! b5 m int i; ( a7 T6 P# m2 P for(i=0;i<m+indexe;i++) 9 J% R$ d( q1 a* _& }) ~ a=0; for(i=m+indexe;i<s;i++) a=1; }

+ }5 F, t, T6 i, i }/ N0 s" o- L

//////////////////////////////// 9 C& C' d1 p: {3 J* kvoid Input(float b[],int code[]) $ k0 h# ~7 L# `' C: L. H4 i{ : O- O( N, B& [" X int i=0;int j=0; - x; j1 Z; x2 h5 p, ` cout<<"The equator variable and Restrictor\n"; cin>>m>>n; 1 A: h0 b6 c+ V- T5 s for(i=0;i<n;i++) # C8 c' v2 M p { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; cout<<"The 系数 \n"; + T& a# { J, f y$ p. F2 l! T for(i=0;j<m;j++) - [5 Y: [5 W# ~& c2 I* M' \ cin>>matrix[j]; } ( X/ G- V9 E3 H8 Q$ E ? cout<<"the type 0:Min 1:max\n"; 8 ], T! H) @, b9 l6 {! J do{ cin>>type; 6 Q& O' i8 i2 x2 x if(type!=0&&type!=1) 1 ~5 G* v( G# @9 _+ k* W" K cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); ! e& D: X6 r" P7 w- ~ cout<<"the Z\n"; & C# e, W5 W( I$ F- l for(i=0;i<m;i++) cin>>matrix[n]; * P& K) `4 G+ p: ^& B if(type==1) for(i=0;i<m;i++) $ C& a; O7 O+ L. r matrix[n]=-matrix[n]; }

////////////////// 0 f) i. E# R' O- W3 pvoid Xartificial()//消去人工变量 { 1 F9 _) x6 w2 p2 e int i,j,k; if(indexg!=0) { for(i=m+indexe+indexl;i<s;i++) { for(j=0;j<n;j++) ! b1 y) [% ~1 J3 p if(matrix[j]==1) { / J( K& k1 U2 F- l4 o% \1 x* g for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; s8 Q, F% V$ g j=n; $ O. j2 L' U H; C4 o1 B } } $ t3 y" j7 L% L7 G } }

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) % K; b5 v, c% B% S, m) q! G9 D1 Q4 B{ 0 Z& T2 F+ L2 ^7 X9 [7 u int i; ) y( }3 K& C7 N% z2 ?* _ for(i=0;i<n;i++) 9 R$ k7 u" d' X" `% u" `# o if(i!=row)c[vol]=0; } ////////////////////// void Start(float b[],int code[]) . Y1 p# S! r/ {{ : h# I5 r }4 i+ Y int i; float nget[100][100],nlet[100][100],net[100][100]; & ?( t6 G2 u! e$ o# {; ]7 n indexe=indexl=indexg=0; + Z' o1 ?" k3 T9 l* ?5 v for(i=0;i<n;i++) " Y) @8 Y: Z1 z' \& O { 5 Z5 s! J- t0 f" M$ n# K0 R if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} ' O) i$ @% j) b: _% i+ z; g9 J3 p if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} 0 A+ r( Y% q1 q if(code==2){ ) y0 Q* U4 z0 d4 `3 \* m net[indexg++]=1; nget[indexe++]=-1; & c9 l' H5 T0 f7 s. \0 v8 y9 q Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 8 H( w7 Z' k7 t. T3 o } % r( f( B6 }9 J: U6 J" w3 A1 f6 j- b: F9 { } s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); : _) Z6 D" H* G2 P& ]7 e7 Q7 l ProcessA(); InitPrint(); Xartificial(); " X; q! W( M% K4 o9 u+ K" W}

" i0 L* Y- I7 u& R3 w1 H( X' [; x/ j

void Simplix()//单纯形法 { : S5 d, D! p( A0 S! D int in,out,temp=0; & ?6 W9 l" c; P" h while(1) . M2 e8 X. p) O8 J { jckxj(); 4 n- k* U( m" A; Y+ e5 {* H Print(); Result(); $ p- U. ?. X8 n* ?1 o if(!rj()) in=Min(); else{ if(indexg!=0) 1 d" B( Z% n2 K# n# s6 H- F8 N JustArtificial(); % v0 d# T1 f l PrintResult(); return; } : F4 H0 L7 P9 i& \% r5 b _ if(Check(in)) : Q# o- @" y3 \+ |3 X { cout<<"No Delimition\n"; return; } 3 z# W6 Z- \1 H* T. P6 M out=SearchOut(&temp,in); Mto(in,temp); Be(temp,in); t3 \! L: X% R( @5 T Achange(in,out); } % |& @5 e1 z2 w% ^- K3 n0 v}

void main() { 3 i* p, Y) U6 O u1 k- p/ u- w& H int code[100];//输入符号标记 float b[100]; 0 _! o$ g/ ?$ E3 S Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); 8 s) z+ i& x1 ~8 |1 a) j3 ?2 G} : z0 l7 X& k6 Z$ ^$ S- F

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!