单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ 2 w( L4 ^! z, `5 g. p

#include<iostream.h> #include<math.h> float matrix[100][100],x[100]; 5 m( y# N* O1 E1 b& y8 W8 o, a' ^int a[100]; 6 J# }' I% R8 mint m,n,s,type; - X9 b* x$ ]8 J8 x. ^* f- Rint indexe,indexl,indexg; ! f, v* \: Z* w$ z7 @/ Z///////////////////////////////// void jckxj()//基础可行解 4 J- X A: a+ A+ T( n8 s{ + \$ N6 P. ~6 ~ D' K/ v* T0 V int i,j; for(i=0;i<n;i++) for(j=0;j<s;j++) 6 }0 W0 @* m. h/ Q0 g! E if(matrix[j]==1&&a[j]==1) 2 i" y! Y* H9 M+ M5 ?# B% G3 d { x[j]=matrix; 5 a" b* S, I) P( T/ d& r j=s; } for(i=0;i<s;i++) 0 m8 ~8 C7 {5 M if(a==0)x=0; : Z2 Q3 o9 o4 S}

int rj()//基解矩阵 7 Z/ j0 T6 ~& J, b{ int i; 6 O: ]1 C* s- Y) s1 D6 `' Y for(i=0;i<s;i++) . V2 @) l i# M( a3 o4 w if(fabs(matrix[n])>=0.000001) ! D% T. H9 P) R& X if(matrix[n]<0)return 0; ) p; R' D. g6 I1 Y# v1 P% m return 1; : N8 g+ _* j/ r. Q6 X0 W} @& F0 o/ w6 qint Min()//求最小的 % R. C% U% o' S9 e* M2 ]' {{ int i,temp=0; B) p( H) _- f9 s' M: x float min=matrix[n][0]; ; q) M1 k/ y* R I9 t1 W for(i=1;i<s;i++) 6 ]* G' Y1 q5 T if(min>matrix[n]) 3 Z. U- V) K I# r5 _ { 2 n1 V* a7 v* m/ } min=matrix[n]; $ b7 ~( d$ {: Z temp=i; - ?) q- J. R1 y5 a) p5 X } 6 ]2 X0 {( p% T7 u3 B$ m return temp; % Z0 B0 C q Q& [" Q$ v* O3 R1 E/ s} ///////////////////////////////// void JustArtificial()//人工变量 { ' D" w& k, C5 A$ B' _' K int i; for(i=m+indexe+indexl;i<s;i++) if(fabs(x)>=0.000001) 8 ]7 m/ y: c! [* S { cout<<"NO Answer\n"; $ W6 ~9 Q$ V3 |2 U' \0 m& @' ~ return; - C) u* A- e. R7 C; ^1 } } 0 N" H! U# O# B) e} ///////////////////// int Check(int in)//检验 , v* H( v7 r0 Z8 q8 F{ int i; float maxl=-1; for(i=0;i<n;i++) & T- u5 t1 b% u* D U- h3 O if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) maxl=matrix/matrix[in]; if(maxl<0) return 1; ! S. l$ g! J* J return 0; 9 c4 m- ?3 X6 z n K} ( |( L9 h9 H2 J/ cint SearchOut(int *temp,int in)//出基变量 0 \4 c, ~2 x! q/ j{ int i; float min=10000; for(i=0;i<n;i++) 4 S% E- V% F& k5 r" _5 N if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 8 b6 K2 F9 m# A& ? &&min>matrix/matrix[in]) 4 {/ {: i' C( {- z+ z5 ] { # P' e( G/ U, [+ U6 x5 M, J6 Q min=matrix/matrix[in]; 6 `+ H. @$ ]5 V! R \( j *temp=i; 9 B8 W% K* \0 V7 B } ' X# E# C7 h! R2 I# Q for(i=0;i<s;i++) 4 M5 n1 T5 n" O, B/ K/ U1 \- e if(a=1&&matrix[*temp]==1) ! S: s D9 \' J/ ~4 V return i; 1 z/ k' z( |$ H2 K( D) Y- b} ///////////////////////////////// . I5 Y- R# |4 U4 S' A" i. avoid Mto(int in,int temp) . ~$ ]7 Y7 R$ x{ 5 e! X$ f; r! [; b4 Z# e int i; ; V1 O( q% ~4 w for(i=0;i<=s;i++) , T: W& {" R, ~8 A: z if(i!=in) matrix[temp]=matrix[temp]/matrix[temp][in]; matrix[temp][in]=1; } ///////////////////////////// void Be(int temp,int in)//初等变换 { int i,j; float c; : m1 Y- s6 }* b% K% z$ F for(i=0;i<=n;i++) ; H8 |( i7 n) P4 z { c=matrix[in]/matrix[temp][in]; if(i!=temp) for(j=0;j<=s;j++) 6 [; X5 s# h O3 A- l matrix[j]=matrix[j]-matrix[temp][j]*c; } } ////////////////////////// void Achange(int in,int out)//出基入基转换 7 U+ Z8 ~: ?) D1 @{ - D7 t: p& p) R int temp=a[in]; 5 ]$ P' d# o. l0 m* M* r a[in]=a[out]; / V+ _$ S2 | Y: h: k) {& W! L2 e; k a[out]=temp; / V) r) u; M" D/ P& e& k) Y2 Z} ( v: @, D7 ?8 [7 y6 J//////////////////////// ' N9 ?: X% X6 Z+ evoid Print() 1 X2 O0 Z, \6 I2 o7 d# u9 E{ 0 e4 S( Z. q7 j int i,j,k,temp=0; for(i=0;i<n;i++) { for(k=temp;k<s;k++) if(a[k]==1) { cout<<k; ! W+ W1 p5 K$ e8 v temp=k+1; 9 {8 K$ y4 M l; h3 O) J+ F k=s; 3 W( a3 b. i% }9 r' A( x } for(j=0;j<=s;j++) cout<<matrix[j]; . i% n) n/ b% g: {- H cout<<"\n"; , l$ v. u+ S5 _2 } } 8 T; s- q' P' i* S* l" P: h' _$ Z cout<<"Rj"; 4 ]+ z- E, o$ R2 }/ @ for(j=0;j<=s;j++) : W& ]8 n+ D/ j. t4 F9 V, B cout<<matrix[n][j]; cout<<"\n"; : B1 i& ^8 w( s2 q8 D/ |} 4 w9 ]9 r, N5 P) R+ |//////////////////////// void InitPrint() { int i; ( m4 T5 _$ i" y7 Q$ x cout<<"X"; / i0 i* \' |* {$ ]5 u for(i=0;i<s;i++) cout<<i; cout<<"b\n"; cout<<" "; cout<<"\n"; } + o* p0 p8 o7 b5 l! F////////////////// void Result() { 7 a5 ~. a/ k+ w, o) A* [$ I, I& Y# U int i; ( T+ n* {" e5 ^ @' ^9 a cout<<"("; 9 h- D0 }7 a! i/ P for(i=0;i<s;i++) cout<<x; cout<<")"; . L5 W5 v# z. U; o, w; p m if(type==1) $ G( Q8 O- e# g cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; " c, {1 v' G( t3 {2 x: v5 N, U( |8 V} ////////////////////// 5 S) E3 y; _/ U: Mvoid PrintResult() { , K h- r# W0 v if(type==0) cout<<"the Minimal:"<<matrix[n]; . D. D; m. P( S( N else cout<<"theMaximum:"<<matrix[n]; } //////////////////////////////// void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 + o e; Q; g6 \+ [6 @" U" s) d5 ]# B{ ; F9 L: \9 k1 C int i,j; ' X+ M; a# |$ K" h }' K0 ?0 ?8 V for(i=0;i<n;i++) { for(j=m;j<m+indexe;j++) 9 r* m Z7 c& _ if(nget[j-m]!=-1)matrix[j]=0; else matrix[j]=-1; ' j f8 z9 `0 W& d4 S$ x6 ^ for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; ; ^3 N& o5 O2 C g' {) ^2 [" C else matrix[j]=1; * X& Z1 W+ z& e3 t* _3 Z. ` for(j=m+indexe+indexl;j<s;j++) 0 A* N" s0 V5 s0 } if(net[j-m-indexe-indexl]!=1)matrix[j]=0; else matrix[j]=1; 1 [8 m5 p5 c" j, s3 k } for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) 4 J7 I4 z: M8 |) k; Z: f: {4 u matrix[n]=100; & I/ N W# A2 h, N: \5 N matrix[n]=0; $ B7 D% \0 B4 n! {" o5 k8 Z$ x$ \, o}

/////////////////////////// & Z: X# p. p( d; svoid ProcessA()//初始a[] { ; g% j$ J% d, d1 b7 c: C int i; 1 U4 ]3 c# f1 y: Z for(i=0;i<m+indexe;i++) - K: x$ q4 |3 ~# B& | |7 F a=0; for(i=m+indexe;i<s;i++) ( u j' R4 m2 Y a=1; }

_9 k* p4 @: V! z7 k0 I

//////////////////////////////// void Input(float b[],int code[]) { int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; cin>>m>>n; 0 y: F: v3 D/ l5 P3 Z for(i=0;i<n;i++) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; cout<<"The 系数 \n"; for(i=0;j<m;j++) cin>>matrix[j]; 7 f7 T( A' l0 G# D! l; [+ B } cout<<"the type 0:Min 1:max\n"; do{ " ]$ }; h4 E, S6 A8 k. f0 n3 e$ ~- d cin>>type; if(type!=0&&type!=1) cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n"; % v/ t; \! ^" ]& {8 c for(i=0;i<m;i++) cin>>matrix[n]; . e% |' r5 p: Y. E" h8 ~+ \8 T; x A if(type==1) for(i=0;i<m;i++) matrix[n]=-matrix[n]; }

////////////////// void Xartificial()//消去人工变量 { & O, H7 g/ d/ G( I& y p" z; J int i,j,k; " Z8 e/ A. a( N6 L2 a) {& U if(indexg!=0) . U- E9 F! g3 m& t7 M: |3 K { ! j- _0 Y) N7 p) ]) y for(i=m+indexe+indexl;i<s;i++) { ' r9 T3 I7 |" I" C) j for(j=0;j<n;j++) if(matrix[j]==1) { 8 U; j' i+ ~, j5 q& |6 A+ I for(k=0;k<=s;k++) & ?( g5 D2 f1 _. d- S1 c matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; } } % I( `( F. h v! b8 [ } }

9 t9 o: l: N8 h. V- A5 x& u" u

//////////////////////////////////////////////// ) Z" X. G5 y' N2 t w( Avoid Process(float c[][100],int row,int vol) ( @& \) o5 C0 A; }{ ; x; z: z8 U$ J& S int i; ; P: @5 A% h0 [9 ]1 Y for(i=0;i<n;i++) 4 `9 l1 v$ K* M; H- \# J- a2 J if(i!=row)c[vol]=0; 9 p( Y- q* b; l& S5 t2 h; F} ////////////////////// 9 Z" \' N' R% ivoid Start(float b[],int code[]) $ K7 k4 f' N- v7 o! m$ N/ k+ v{ . r1 S7 S+ D \3 w; D int i; 8 u _- G3 P. j) a0 S/ O/ V; i float nget[100][100],nlet[100][100],net[100][100]; 9 J* V: O; a* e( y indexe=indexl=indexg=0; % I W; o) {* s for(i=0;i<n;i++) 8 b# A' e& k& F2 V: r { 0 t: h( l2 C, r2 j7 i. | if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 0 x! }) V5 Z x- Z0 X7 M if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} if(code==2){ " T" A! N$ _8 V8 [' f: {+ | net[indexg++]=1; nget[indexe++]=-1; , G Z/ A, n4 c) A9 T Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 1 D( a+ v' K" t. n, U } 5 C( b8 E/ H2 d$ i } s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); ) n7 R+ \7 N0 c ProcessA(); ! ~- ^1 A8 Z M0 k6 G' T1 H0 U" i InitPrint(); Xartificial(); }

( C- V& E1 S- D/ [) ~

void Simplix()//单纯形法 { - N4 t5 q7 d6 H. u int in,out,temp=0; while(1) { 2 O+ V# g1 H/ t9 G jckxj(); $ M' r: r- W; [7 ]: C; C Print(); 5 G, D; ?# r% F9 u/ O7 j) F Result(); 6 ^6 X3 d2 }, }) { i- T4 W I8 O8 h" U if(!rj()) in=Min(); / r- D) G& d( \" J; r else{ if(indexg!=0) $ l! H# i2 E1 V5 C JustArtificial(); PrintResult(); 6 Y9 `7 C4 v0 r' K8 I Y return; , j( a/ @1 C& K+ f8 l6 k6 g. d } / o6 a, C9 v! j- f if(Check(in)) { 2 W* i3 ]: c7 T cout<<"No Delimition\n"; 3 ~! H' w4 n/ l ?$ E return; } out=SearchOut(&temp,in); Mto(in,temp); Be(temp,in); Achange(in,out); & |5 q6 W8 @9 a) Z) S' } } % @+ d( j8 G. u( I% w0 e7 U# ?}

+ ?$ R6 p8 F; y2 W4 }9 a; F7 u

void main() { int code[100];//输入符号标记 + _! ~8 G. B. e) P" u7 V# I float b[100]; Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); " y4 v$ D6 [3 t. p}

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!