单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ 4 _; S/ Y! z/ ^; T1 X; ?2 q ) K! @( ^& g8 u8 D8 M; k& ? ( h5 t+ I: L: @0 z" ]# p. U

#include<iostream.h> #include<math.h> float matrix[100][100],x[100]; # K6 q/ q% w# _, H! Q6 v! m! Oint a[100]; int m,n,s,type; : ]% W$ U* s+ a9 Cint indexe,indexl,indexg; ///////////////////////////////// void jckxj()//基础可行解 { 7 Q) W/ f0 Y6 s. f5 ? int i,j; for(i=0;i<n;i++) 7 m) E" `, W* F2 ~; Y- j0 g4 B3 S2 x for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) ' q: V& C& N* S( z( f) m& D, { { x[j]=matrix; . N5 @" E) m4 |9 l! ~ j=s; } % V1 H! y# j5 r; ?4 Q7 ] for(i=0;i<s;i++) 7 m" ?" Z/ T' l if(a==0)x=0; 1 v4 I+ ^1 i. Y! n" n# {+ l0 _4 f}

5 O/ S3 K9 h; N' g

int rj()//基解矩阵 { int i; for(i=0;i<s;i++) . \8 t) g! _2 P4 K1 Y if(fabs(matrix[n])>=0.000001) if(matrix[n]<0)return 0; % a: [: I. }5 x! m. ?) x% T# _3 b return 1; } int Min()//求最小的 & r6 g3 c2 R* w# N9 @{ int i,temp=0; float min=matrix[n][0]; for(i=1;i<s;i++) if(min>matrix[n]) # C! W9 i0 l' ~# Q) g. w+ U { ( n( W( A/ }" h) J" J( j+ Y min=matrix[n]; ; X; Q* u# I7 c" N* B D temp=i; } return temp; * I$ N4 N6 B2 M. }} ///////////////////////////////// void JustArtificial()//人工变量 { int i; for(i=m+indexe+indexl;i<s;i++) ( k: z' G" u+ J9 r% |& H* P( c6 v if(fabs(x)>=0.000001) 2 T* _7 M1 w& [% w { cout<<"NO Answer\n"; return; ; z9 @- D* a; C' e5 S7 ]: b; z: d } / E$ o; d% n) r0 ]! G$ b' m} ' c( _, X7 ~$ s) f///////////////////// int Check(int in)//检验 { int i; float maxl=-1; 6 _/ i, |/ G ~) E- q% y for(i=0;i<n;i++) 3 |3 d( w4 `9 m$ t( W# w5 \ if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) ; P; X" I7 D$ y8 B1 P1 D maxl=matrix/matrix[in]; ) ]+ b3 C! _) h7 _' V if(maxl<0) return 1; return 0; ( q( W# c. `2 w; }& k% h} ) I; n$ g7 h6 rint SearchOut(int *temp,int in)//出基变量 7 M$ a- ], v. y! |3 k! r- y- B{ int i; ; ]" l# i! J h: ^( o float min=10000; : Q+ o: z4 G. ]& s; {* A4 } for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) + T; G7 Y4 o" T% N+ o &&min>matrix/matrix[in]) * s" ]8 @, {$ F { % f# o) E9 I" ~# U4 [" n, c min=matrix/matrix[in]; . N8 H' x, r9 H *temp=i; } . T& X9 ?, ^' A$ {( a; D for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) ) J$ ] a! |! p( Y1 ]7 F return i; } ///////////////////////////////// void Mto(int in,int temp) * n$ p+ ]* S9 b+ L& V, [6 t- s{ / W; x: j7 V3 S2 R7 j$ j int i; * R8 B7 P4 }# O' G* f for(i=0;i<=s;i++) - [9 ?4 F" [. @# ` p( r if(i!=in) + f! I& ~0 Q0 e6 k. P" B matrix[temp]=matrix[temp]/matrix[temp][in]; 8 }. i- U% Y% \& k- {# L$ A4 X matrix[temp][in]=1; 1 R9 @& c3 T7 w% P" O} ///////////////////////////// 0 V" B$ i7 e" L8 J0 `; \! @8 T cvoid Be(int temp,int in)//初等变换 * ~( @: {- W7 M* } P{ ; U$ ~3 F ?# }3 [" s* b int i,j; 6 s6 `! f Y( A( W9 N% j# M float c; for(i=0;i<=n;i++) / l A' p1 z; i7 O; v/ G# S { c=matrix[in]/matrix[temp][in]; ' |1 `. e& R' w5 z if(i!=temp) for(j=0;j<=s;j++) 1 F$ J4 y: S9 }, g1 g! e' I matrix[j]=matrix[j]-matrix[temp][j]*c; 5 }( W" J6 C7 X } } ////////////////////////// void Achange(int in,int out)//出基入基转换 { int temp=a[in]; a[in]=a[out]; a[out]=temp; } F$ x9 @/ \2 a+ @- n7 F% ?//////////////////////// void Print() 1 i5 k: h1 e7 x0 z( \{ : l$ c5 G: C$ ?! m; Z6 O int i,j,k,temp=0; for(i=0;i<n;i++) |5 K( N) ]4 P6 V { for(k=temp;k<s;k++) . h$ r% L4 U) k+ X* a) k) C" G if(a[k]==1) - I& J' s- T& P3 R5 `$ r { ' {2 S, [0 E. | cout<<k; 1 d- K9 Y% @7 F6 q F5 q" a3 ] temp=k+1; k=s; } ) ^# N0 {" v, R1 d% ` for(j=0;j<=s;j++) 0 [1 e% @0 W( B$ ?. G5 N6 b cout<<matrix[j]; 3 y: h4 }* r9 K cout<<"\n"; 1 s2 \% I% u p7 Z1 g } cout<<"Rj"; for(j=0;j<=s;j++) cout<<matrix[n][j]; . e9 l9 W: m; j2 U5 f# ` cout<<"\n"; } 7 U) M9 K O3 k# u1 t' o: Z( j//////////////////////// void InitPrint() { int i; * n+ T* y# U4 [2 W; w3 c cout<<"X"; # N: @1 P4 w* b7 e" R: R for(i=0;i<s;i++) ; K; f; U; |; x9 k: x cout<<i; . G, ?5 ]( Q. |3 G3 u# Q cout<<"b\n"; cout<<" "; cout<<"\n"; } - M3 X" I$ P+ e& ?% C s7 S# H e////////////////// * y0 M, [$ Y" L* i- c, ~/ ]void Result() { int i; cout<<"("; for(i=0;i<s;i++) cout<<x; 2 [: r, o7 X( K; g" I cout<<")"; if(type==1) cout<<"Zmax="<<matrix[n]; * D0 t, v j6 K/ C" V4 k7 A/ S+ } else cout<<"Zmin="<<matrix[n]; } ////////////////////// 5 J; i+ w9 g( l3 r) _3 Nvoid PrintResult() { if(type==0) cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; } 4 k) x0 `3 U' r//////////////////////////////// 5 j9 v& x4 A% Y4 _0 t c+ Svoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 / P9 t( S6 Q+ Q: y8 i- ~{ 9 R4 L2 z' L, Y2 r3 z& e- S int i,j; 2 n" e& o5 M# \- n* a A0 C for(i=0;i<n;i++) { # V" ?2 m. x$ c( r$ [& \3 N for(j=m;j<m+indexe;j++) " ~) Y4 `; g. y r5 P& `6 l) q) d if(nget[j-m]!=-1)matrix[j]=0; . g( ?9 v0 N5 g" b+ s 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; / i. ]( [# l' }& W } for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) matrix[n]=100; . S* `/ s, W% L0 q: ?( g matrix[n]=0; 1 f- D A5 _8 N* `7 w}

' ^& K) @' M# s+ f4 N5 v

/////////////////////////// % C- p7 x- p. f+ L" N7 gvoid ProcessA()//初始a[] { int i; ! k8 z) V) n1 O R for(i=0;i<m+indexe;i++) a=0; for(i=m+indexe;i<s;i++) a=1; 4 G4 d6 ?" N3 y: c3 s. P+ B}

5 J5 U$ w+ o$ t6 j

//////////////////////////////// void Input(float b[],int code[]) " _1 q, A4 A9 @5 l# g8 B" j+ J$ `{ 6 m1 K! T+ S- H5 t6 q* E* _ int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; cin>>m>>n; $ ^1 e, T# g' X$ {7 g7 b. u/ Q for(i=0;i<n;i++) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; cout<<"The 系数 \n"; ) F$ x4 V/ C, J6 N for(i=0;j<m;j++) cin>>matrix[j]; } / k3 i: {( V2 U: `$ w6 T% }( \ cout<<"the type 0:Min 1:max\n"; do{ cin>>type; & U$ c. t8 B* M/ z7 ^- U9 K if(type!=0&&type!=1) cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); " U3 w5 v. N) N cout<<"the Z\n"; 7 x: Y* l+ D; u4 @1 C for(i=0;i<m;i++) cin>>matrix[n]; " H4 Q, S9 R8 ^& u$ R" E. l3 e' R7 c if(type==1) 9 E v) D) ?9 J- J: \" \ for(i=0;i<m;i++) matrix[n]=-matrix[n]; 0 d, @, _6 V, j1 Y) t8 Z}

: k; V9 i, @: w( t& y! d

////////////////// void Xartificial()//消去人工变量 7 U/ v/ Q7 Y; P1 o I{ / p: |) d" t7 H' b' I; k; t, s int i,j,k; _1 ]. A/ L# \+ Z: ?& J% x3 y if(indexg!=0) { for(i=m+indexe+indexl;i<s;i++) 7 M* |' z" o- y7 ~5 g' x { for(j=0;j<n;j++) - K8 _" t* ?9 k& e" o% w7 y) w if(matrix[j]==1) / l0 y1 G: ]% W! T: o9 s { for(k=0;k<=s;k++) ) T- ^7 o9 H4 y% o matrix[n][k]=matrix[n][k]-matrix[j][k]*100; - O% s( R7 E# q3 M% r# n' m, r j=n; 9 d+ C& f# }2 A, F } } ; b" ?! U& k( H0 F. F } 1 q9 P \' R6 ]}

1 ^: W8 j) @7 v n( m0 {

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) # X* p* h2 u! d{ int i; ! k, F- ?* K# u" } for(i=0;i<n;i++) ; D* z+ {- p. X' ?1 b if(i!=row)c[vol]=0; } ////////////////////// void Start(float b[],int code[]) ( P/ P) B8 i6 \' S{ int i; float nget[100][100],nlet[100][100],net[100][100]; indexe=indexl=indexg=0; / ~: ]1 ?) a+ F; } for(i=0;i<n;i++) 3 ]7 m1 {7 W4 J% {4 B4 R+ W { 4 m) g1 I4 \0 Q! \ if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} . Y6 l; Y+ E" h) W f0 c2 B/ r if(code==2){ * Z: [+ Q: p( m$ |% b$ p: v* y ~ net[indexg++]=1; nget[indexe++]=-1; " l5 Z1 k- m0 ], z) h. t Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 6 E% J! N/ ]& `: k. y' a* E } } s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); . `' \( n( t# i4 u+ b, u( ~" L1 l ProcessA(); InitPrint(); 7 s! X+ x7 m3 O Xartificial(); : c; O( [7 U2 _8 o! c}

t! q* T. t6 H5 h4 ?9 b u+ U6 f

void Simplix()//单纯形法 % [- B2 b. U* m. O. I0 C1 L{ . ^$ [/ W# y- H& d6 v int in,out,temp=0; while(1) 2 S# ^, ^0 j h6 b' H { jckxj(); " r, @" ^0 V2 Z+ t5 r9 V2 C Print(); * S: @4 [# B2 a$ O- K/ @$ G Result(); if(!rj()) in=Min(); else{ / ?) N3 `+ k/ g% N. |" j0 n. } if(indexg!=0) & R- _: C3 ~! e6 ]- ?" P JustArtificial(); PrintResult(); return; 4 \( H6 ] d; J8 y6 h } if(Check(in)) * ]$ C& u/ y! B: V! V o" }& d$ p { cout<<"No Delimition\n"; % ?4 ]# f% Z0 E" p( D3 M! l return; } 5 R b1 h$ ~. T3 e out=SearchOut(&temp,in); 9 c3 E- r5 ?8 Q" D/ p; z9 B P Mto(in,temp); Be(temp,in); / d' L6 A7 O& | [6 A* F% B+ t Achange(in,out); } }

void main() { int code[100];//输入符号标记 float b[100]; 3 x' e1 c, e9 F' o# |3 w$ | Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); }

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!