单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ ; {( F' D! l7 R7 x. f% L & t7 t! O$ W' k7 W6 ^

#include<iostream.h> #include<math.h> float matrix[100][100],x[100]; ' g% h1 F0 ^" g* ~int a[100]; int m,n,s,type; int indexe,indexl,indexg; ///////////////////////////////// * I9 x+ D" o+ }3 I @void jckxj()//基础可行解 , E4 i; G ?1 V4 d6 D$ c* y{ int i,j; ( u0 | Z3 \8 S4 L; H" d2 H for(i=0;i<n;i++) for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) 3 L( F7 z! G, X( p+ q j4 l: j { $ _/ c/ l% X, @ x[j]=matrix; 0 Z4 e }. w5 W" z( r; V j=s; " L# `, m. O- [. W" H7 e1 W: } } ( G- ]1 ?& {4 [/ V, W for(i=0;i<s;i++) if(a==0)x=0; 4 `9 x. R; S# @9 y5 s7 U* k}

int rj()//基解矩阵 1 [, O3 x; `. b, f, n0 R8 y{ int i; for(i=0;i<s;i++) if(fabs(matrix[n])>=0.000001) & U* R, H' T* i X6 g% E if(matrix[n]<0)return 0; 9 t: c9 C2 t( |' a6 f- ? return 1; } int Min()//求最小的 : p( x) S9 Z3 G! u$ \{ int i,temp=0; % e! C/ A5 _# R# h float min=matrix[n][0]; 4 y' {4 U/ c% Y$ G* E' D for(i=1;i<s;i++) if(min>matrix[n]) { 6 s/ o9 l& T1 [" ~ min=matrix[n]; ; m* K$ f0 a( A4 c* E: Y temp=i; - l/ X& }% V2 a6 M& w" \# B } return temp; } ///////////////////////////////// void JustArtificial()//人工变量 { int i; for(i=m+indexe+indexl;i<s;i++) " ?$ v/ g* n* @+ R/ z1 S- C if(fabs(x)>=0.000001) : |" ~. Y$ j7 {- u { $ N/ T, w9 `: ?2 N! R& r8 v cout<<"NO Answer\n"; return; : U, t' A! p4 ?+ ]+ x# ?0 H9 z } # L7 v- z% n2 _0 U* L} ///////////////////// & w4 N7 m9 F3 R% c$ p( o% T2 Yint Check(int in)//检验 { # F1 K& e- g. H9 j int i; float maxl=-1; : m6 F, c. o6 T$ ~ for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) / W% ]( g9 z7 p, N: R maxl=matrix/matrix[in]; $ D; q1 w8 ?8 S2 J" m/ P3 ?% r+ C if(maxl<0) . W+ f, U1 {3 m; u! Z; _" v return 1; 2 C/ V% ?* r/ v0 e8 D X return 0; } int SearchOut(int *temp,int in)//出基变量 { int i; float min=10000; 0 }/ Y3 V0 F! X3 w' l; F for(i=0;i<n;i++) 9 e1 F3 K! g3 y1 }/ C if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 5 l( r1 _* M! k' i+ B( Z; ` &&min>matrix/matrix[in]) " A9 X9 o) `, x; Y { 4 I1 Y% q q& s2 ] min=matrix/matrix[in]; " b3 a4 }* S$ \7 U! e *temp=i; } ! B8 _7 [4 @* Y! j for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) : b' ^. v( \( w/ n" \6 r return i; } " N' t' r- D0 v) b) ^% {///////////////////////////////// void Mto(int in,int temp) L; z4 I* ~& B0 B D{ ' f' Y) e# W R2 Y% S0 J/ y int i; for(i=0;i<=s;i++) if(i!=in) 1 f# c# ]) V: y6 d matrix[temp]=matrix[temp]/matrix[temp][in]; , ?, d- N3 n$ M9 i5 A matrix[temp][in]=1; - t* f- z* l. g4 c8 X6 F% }} % f/ Y1 _$ ^4 c8 ~ O( {7 x2 H///////////////////////////// void Be(int temp,int in)//初等变换 - ?+ V. ?3 p2 J' R+ h. H0 w+ Q{ 6 F# Q* G% w6 b& k int i,j; float c; & L# O( c6 J4 x# U! X for(i=0;i<=n;i++) 8 s( P+ {! u9 Q1 N; W+ v { c=matrix[in]/matrix[temp][in]; 6 }* ^" X8 V1 O/ j. f4 U; `) T/ W if(i!=temp) / [( F+ L4 f4 c for(j=0;j<=s;j++) . H- n3 V2 g4 k0 z R matrix[j]=matrix[j]-matrix[temp][j]*c; } } + Y. n+ p" F. |7 `6 [3 z( w) X( R* S F////////////////////////// ' p- u) L! @9 T3 C; {void Achange(int in,int out)//出基入基转换 6 J+ L2 d4 M4 b( o+ s* M0 u# V{ 4 P5 |- o6 u" f, V6 B6 }$ J' a int temp=a[in]; ' `- I0 J8 `+ H- R a[in]=a[out]; 6 a! r4 [6 e3 Q! Q+ T a[out]=temp; 3 A6 U+ t& b2 _9 P} 8 N2 x3 U7 l+ m//////////////////////// . E( R0 a+ v8 s! j4 f0 M& tvoid Print() % f6 g1 t0 l+ C9 l$ V{ " U$ P3 H, ^4 z" t( h! @7 v: b) L int i,j,k,temp=0; for(i=0;i<n;i++) { 6 ^$ c4 {7 K c- m! ~2 _5 q9 m: S for(k=temp;k<s;k++) if(a[k]==1) 9 b S ~: H7 T7 Z# v { cout<<k; 9 u* @; `5 |1 s9 z1 J- _ temp=k+1; 9 Q) h; s4 J2 l( \ o; p% J k=s; } ! C$ j: [4 o; G' B for(j=0;j<=s;j++) cout<<matrix[j]; & f" T' s9 w7 u* ?# R; s cout<<"\n"; } cout<<"Rj"; % A/ u. e O4 u for(j=0;j<=s;j++) cout<<matrix[n][j]; * w2 S9 T( h F# ~. v+ _8 n cout<<"\n"; . Z* R+ A s' M' q} 8 F6 @" F# Z* d- t1 b0 l//////////////////////// void InitPrint() ) w5 n7 L! c! x& D{ int i; cout<<"X"; for(i=0;i<s;i++) cout<<i; # l( `/ F. M* |3 Q4 Y( e cout<<"b\n"; & W4 z) I. A T8 o* c/ d5 k$ f" K cout<<" "; cout<<"\n"; ) t' D) X2 K6 [$ F& q3 {8 S} ( W6 d s- Z2 G. I% v////////////////// void Result() 4 i+ p# w2 Z; n: W{ ; m, { }6 R1 x; U; H int i; cout<<"("; * i8 E' i& B3 w1 w7 a for(i=0;i<s;i++) cout<<x; cout<<")"; 2 P, k" u$ P s6 C# N if(type==1) cout<<"Zmax="<<matrix[n]; # p; A- |- X& _( a @5 w, h& r' C else cout<<"Zmin="<<matrix[n]; } ////////////////////// $ a& l8 R' N( S: s3 j. avoid PrintResult() { . K4 i: g& X! d0 I1 o1 R if(type==0) + @, ^2 f8 Q" W2 X" @6 c! K cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; 9 Y- F) s" E2 Z} //////////////////////////////// 8 \$ S7 J- o) T2 ]void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 { int i,j; 0 j& o ^4 x$ r4 B- r for(i=0;i<n;i++) ' g% k# E. `& F& A { for(j=m;j<m+indexe;j++) , {0 L: V# r$ s& G. ~! G) ? if(nget[j-m]!=-1)matrix[j]=0; else matrix[j]=-1; for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; + S; D6 y. H. F% F- X$ h. s+ k else matrix[j]=1; ( v7 z4 q0 z# @. r for(j=m+indexe+indexl;j<s;j++) 2 M. k. L: ~* P( a% f+ V. V1 }. ? if(net[j-m-indexe-indexl]!=1)matrix[j]=0; ; d. }, N( R. m3 @2 X else matrix[j]=1; ; j' v% u9 R2 \ } - X- Q7 |& H2 E8 N4 A for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) 9 A2 z6 R N/ N6 O, Z/ I matrix[n]=100; matrix[n]=0; ) n; u$ L1 J: w}

/////////////////////////// void ProcessA()//初始a[] 6 P4 Q' @* a2 z, x{ int i; & T1 s5 I4 G! u) m% Y for(i=0;i<m+indexe;i++) a=0; ) g% o" S0 k8 c1 o& i% o+ L for(i=m+indexe;i<s;i++) a=1; }

//////////////////////////////// void Input(float b[],int code[]) 1 j. k/ z4 d# S2 k; L{ * U2 C* ]$ _8 R: M# r! o int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; cin>>m>>n; , l. Y! z. [% w5 ^ L- i- a for(i=0;i<n;i++) " L+ e* F- K9 l. e. [ { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; . m; l1 _0 c# H% }, ? cin>>b>>code; # m7 v8 p) t5 @0 K cout<<"The 系数 \n"; * ^, {. c6 n0 T4 F' T1 Q for(i=0;j<m;j++) cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; do{ cin>>type; if(type!=0&&type!=1) . T+ a- T$ Q* f7 a& ^ cout<<"error,ReInput!\n"; * M+ x$ W3 i( C, D0 q- T$ S1 w }while(type!=0&&type!=1); cout<<"the Z\n"; ' T9 z$ \# f) d for(i=0;i<m;i++) ( I. i( k7 ?2 t6 | cin>>matrix[n]; ( e& e$ n1 U/ s( |7 X! m if(type==1) # E2 i) H6 B9 w( L8 A6 M for(i=0;i<m;i++) matrix[n]=-matrix[n]; + `& ]9 L: V( S2 F. Q}

+ W. Z( X$ O$ i0 Q////////////////// void Xartificial()//消去人工变量 & l/ {1 b( y) _" u9 n# G; n{ int i,j,k; if(indexg!=0) { $ O( F5 E6 p; D for(i=m+indexe+indexl;i<s;i++) { . Q) Z8 _' L9 l0 L for(j=0;j<n;j++) if(matrix[j]==1) { for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; / \8 ?$ r* T% v* u; F" F j=n; } ) E+ y1 [ s ^5 V. l: {. s& K8 \ } % c- g% q, D) ?& c" @ } % S' u3 \6 \4 e3 o# l9 T* F' j7 c+ x/ u}

* D u8 L7 I7 X# R

//////////////////////////////////////////////// ) U& O K. f4 C* S, ?0 A, Zvoid Process(float c[][100],int row,int vol) { int i; for(i=0;i<n;i++) if(i!=row)c[vol]=0; } 4 b" \' k5 I* e1 ~////////////////////// void Start(float b[],int code[]) , J+ ~& z8 X. _9 E% W{ int i; float nget[100][100],nlet[100][100],net[100][100]; $ p: J) U% w; Q& p; _8 R& F1 C indexe=indexl=indexg=0; : r+ F. e1 Q2 T& W for(i=0;i<n;i++) + j! c3 h; V( @* ^ { + }/ J* l7 g" Q8 K6 L7 F if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} 6 H; v) w/ f2 L if(code==2){ @: \- e1 H, ?$ Z net[indexg++]=1; nget[indexe++]=-1; ) p& I: l. \$ m) K Process(net,i,indexg-1)rocess(nlet,i,indexe-1); } } 5 V4 ? m% D( l, A, y. h B4 o+ C s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); ProcessA(); InitPrint(); Xartificial(); }

void Simplix()//单纯形法 9 T A& f+ W$ o2 d2 R/ C" N: c{ ( u$ P5 a. }3 C$ f% i int in,out,temp=0; / U1 W R' _8 M& f while(1) { jckxj(); % A& T/ [; K9 D( J Print(); Result(); 6 K* e+ F3 l* l" e/ H6 Q if(!rj()) in=Min(); else{ if(indexg!=0) JustArtificial(); PrintResult(); ; P% A: t' m: _! T: g& W: ^4 P return; + n2 p4 u% j/ R7 E) T6 i5 e. C } if(Check(in)) ; B/ s( A5 D I) p5 D0 R0 \ { cout<<"No Delimition\n"; return; 9 N d. M+ W( i } out=SearchOut(&temp,in); 0 E) v x; V+ }' ~- Y- x Mto(in,temp); 2 C9 M! v. j- E" a7 j8 X: o7 _. m Be(temp,in); $ k6 k i" m7 S Achange(in,out); } ) S- s* r' ^1 r4 B; ^* z}

void main() { int code[100];//输入符号标记 float b[100]; - s% o# S& V8 U' M0 h Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); 2 k/ b7 r, o# O- K} ! m( u( _* ]5 i6 r$ C( S4 q) v

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!