单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！

#include<iostream.h> #include<math.h> float matrix[100][100],x[100]; ; v" G% b' \9 u' a1 u2 U0 Cint a[100]; ; l% _0 i8 M" R4 eint m,n,s,type; int indexe,indexl,indexg; + _1 z D3 O9 D9 K$ S0 O t, ~///////////////////////////////// 8 j, u9 ]8 x+ L3 svoid jckxj()//基础可行解 { int i,j; 4 Y& p+ C# {& X) r. o/ J0 i for(i=0;i<n;i++) for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) { , T3 x+ G$ g, Z$ j% b5 V x[j]=matrix; ! P; a) D- I+ @/ {1 {6 C/ L j=s; } for(i=0;i<s;i++) 8 Z6 I0 }" r0 ?: z if(a==0)x=0; . L1 z. F2 f* H0 U! F( O; X}

" I; P+ G* X* @% O

int rj()//基解矩阵 { int i; for(i=0;i<s;i++) if(fabs(matrix[n])>=0.000001) if(matrix[n]<0)return 0; & U/ U, ]; ^. _6 }- q" d return 1; } int Min()//求最小的 { int i,temp=0; & K6 u( N0 a. d' V% @& ]7 c float min=matrix[n][0]; for(i=1;i<s;i++) / m2 N2 ^5 |$ Q+ U& o; Q7 U3 S% j if(min>matrix[n]) : E- b3 {3 j7 J { min=matrix[n]; $ h7 E: @% p1 h0 O9 A2 x9 k2 H" O8 C temp=i; / S4 r- ]7 D) T9 w } 3 d% o+ g" ~% r/ W$ s; |5 F return temp; } ///////////////////////////////// void JustArtificial()//人工变量 + T7 ]) ~% z" E1 `{ / C+ W4 }" j* O T" { D% Y int i; , B1 K8 a" _+ `: x/ E( Y for(i=m+indexe+indexl;i<s;i++) $ a9 h% F# M( B- c3 ^; f# z& q if(fabs(x)>=0.000001) { cout<<"NO Answer\n"; return; } } ///////////////////// % I+ |- a* H6 E( eint Check(int in)//检验 { 2 T, ]" _$ t3 A) T, I# A$ t int i; " q0 p _( m1 e" \ float maxl=-1; for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) maxl=matrix/matrix[in]; . S! ~& u7 D% \& c0 T6 L" Z P if(maxl<0) return 1; ! j4 ?5 u7 |2 e$ A1 C return 0; } 9 b1 T3 y- `7 Mint SearchOut(int *temp,int in)//出基变量 { ' g* v4 _1 }: C1 ?& H/ c; | int i; 6 K: ~# \4 j, S, T6 H float min=10000; 3 {# M" j+ ]: u5 q9 k: i( w5 W for(i=0;i<n;i++) 9 V: u! X$ P3 }. f if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) g/ H* i; g9 C &&min>matrix/matrix[in]) { 8 d- j; a9 F) `) H7 ~/ j/ L5 I min=matrix/matrix[in]; 7 C( t. h4 L' R* }0 x, W% l1 w *temp=i; 6 N9 y( Q; [$ N" U, n0 v- H } for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) return i; & @: t1 B5 b, ]* Q- g* {} ) |: H- f) j' s! N* c* o4 P$ A///////////////////////////////// void Mto(int in,int temp) / O( G7 C5 M+ o, W{ 0 p; Q+ F& T# u+ @- s% u int i; 8 |2 H( e* {' `! q2 q2 l for(i=0;i<=s;i++) if(i!=in) matrix[temp]=matrix[temp]/matrix[temp][in]; matrix[temp][in]=1; O& V0 Z1 i# x* C' t} ///////////////////////////// 7 W, V; i: a' i* G. Cvoid Be(int temp,int in)//初等变换 : b g1 }9 A; _/ d$ n{ 4 s% v, m; {, S8 c9 h int i,j; 1 U; z, Q+ A. A- z k7 ^$ | float c; for(i=0;i<=n;i++) { 6 v/ M& `( }6 A5 j5 \) g2 p6 ?9 S% y2 _ c=matrix[in]/matrix[temp][in]; if(i!=temp) 6 |* @8 V/ y$ ^" z for(j=0;j<=s;j++) matrix[j]=matrix[j]-matrix[temp][j]*c; } 0 e; |" |$ M# ^5 ]' |} P5 T; V$ u! B) i8 {) Q9 E////////////////////////// \7 G2 i! W& h0 A$ v) pvoid Achange(int in,int out)//出基入基转换 . R2 i- P0 {8 A l/ j5 |' E7 V{ , L# I7 { h2 A' n int temp=a[in]; a[in]=a[out]; a[out]=temp; } //////////////////////// 3 X; K7 R5 q5 c4 E2 F0 C: wvoid Print() { int i,j,k,temp=0; * O# n0 A+ H5 l7 j, Q for(i=0;i<n;i++) 3 ]5 \: K+ u/ \1 C! q' a$ ?" c. {6 a. Z { for(k=temp;k<s;k++) if(a[k]==1) 7 D4 M5 l) K/ z6 A5 y" c( p* U) b { + N6 @9 ]. A" x cout<<k; temp=k+1; k=s; : M( r; G& m0 B; X$ s ~9 T. k2 b } for(j=0;j<=s;j++) cout<<matrix[j]; cout<<"\n"; 0 @9 C5 e0 I. g0 ?- t0 O4 _ } cout<<"Rj"; & S- f; f/ ]6 {) o" O" R7 D for(j=0;j<=s;j++) ' P+ S# W, E6 o8 \- o cout<<matrix[n][j]; , l6 [2 V. {9 A( a8 H( r0 r+ y cout<<"\n"; } //////////////////////// void InitPrint() { / j% B( L# v5 A int i; cout<<"X"; 5 @4 q+ [1 v0 {$ p3 I4 }* @ for(i=0;i<s;i++) % x1 W- W: W# x' { cout<<i; # _' a$ l& f/ b cout<<"b\n"; 7 v$ n b; I; q3 G$ I cout<<" "; ( A( ]/ q7 l9 ^9 v* Q9 L! f8 W6 f0 @ cout<<"\n"; - ^2 f9 L9 e0 n$ W9 T$ L} ////////////////// + | ~- F+ H1 t/ Jvoid Result() { 5 c$ u, S* k! s8 D, ?2 M int i; ' H. O0 P, P2 Y2 y3 ~. U# P cout<<"("; for(i=0;i<s;i++) cout<<x; 9 m6 B# r# w5 F cout<<")"; - |0 ~# d9 I! p$ M+ i; z if(type==1) cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; ) Z+ c! \# {1 U& k/ W) \* n( n8 @} ////////////////////// void PrintResult() 1 d- I) K' M) ^. G; \3 ^" X{ 3 R n. s" h6 V' @6 \# c if(type==0) 6 X- a! f/ u4 L cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; } 9 ~4 t, J( M8 S//////////////////////////////// 6 U: [( C# U9 ^# @7 svoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 . R b& b3 X' J6 e5 ^: P{ int i,j; & W# c3 q' {& `+ U: ^. |5 v$ y" k for(i=0;i<n;i++) { * @, \' [3 l& P9 y7 w% I% c for(j=m;j<m+indexe;j++) ' a' h# V. ^. h) M+ `. n& D if(nget[j-m]!=-1)matrix[j]=0; 7 f" ?0 c {) f, k. H else matrix[j]=-1; for(j=m+indexe;j<m+indexe+indexl;j++) 4 y8 j8 e8 K6 v: [, C if(nlet[j-m-indexe]!=1)matrix[j]=0; / n" _6 p! v2 i" p* j: c else matrix[j]=1; for(j=m+indexe+indexl;j<s;j++) if(net[j-m-indexe-indexl]!=1)matrix[j]=0; ' l2 w! d4 s( I5 O' L% C& { else matrix[j]=1; } ! E8 P& |$ M7 E) A+ Z: t0 S for(i=m;i<m+indexe+indexl;i++) $ M2 H( F- \& v d4 I# b. O matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) 4 _0 @. p% @6 q5 u+ z) Y matrix[n]=100; matrix[n]=0; ; R5 \ V: T, |; }4 ?}

$ s! ]' D' |* w. Q' ?( o

/////////////////////////// void ProcessA()//初始a[] * K8 O" d! n" {% ?{ int i; for(i=0;i<m+indexe;i++) a=0; ! Q7 ~, q2 X' p4 l for(i=m+indexe;i<s;i++) ( i5 q. M4 w- h5 Q" G a=1; + O3 p# J' o/ b( U" Z}

//////////////////////////////// 9 w# r! e! X8 z5 A. ~2 K8 nvoid Input(float b[],int code[]) 6 y$ [% J7 ^3 ?2 a/ B% o{ int i=0;int j=0; $ [0 p& Y9 X2 Y {2 Q4 d cout<<"The equator variable and Restrictor\n"; + g+ N7 v& N! I$ l6 E/ T$ g! j cin>>m>>n; for(i=0;i<n;i++) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; 9 X( n8 ]! R! Q9 y: d3 [& ] cin>>b>>code; " _$ \! Z/ A( P: \ cout<<"The 系数 \n"; for(i=0;j<m;j++) : h5 Z. e k# [ cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; ; Z8 ]2 h1 ]7 [! i0 A do{ cin>>type; if(type!=0&&type!=1) 8 ~3 x) S& J& @9 c9 o cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n"; for(i=0;i<m;i++) cin>>matrix[n]; if(type==1) & ~ a% q) A4 m for(i=0;i<m;i++) matrix[n]=-matrix[n]; }

, ]5 K6 m+ F4 V: g" \

r; x" ?4 S! \! o: w////////////////// void Xartificial()//消去人工变量 3 h o7 b" b: b2 c) G( w0 k{ int i,j,k; if(indexg!=0) " L" a+ I5 b; f$ y { for(i=m+indexe+indexl;i<s;i++) 1 S; }% } l* H- q: n* A% r { 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; j=n; } } } }

" k* j! h( r1 c" g2 Z

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) ! B3 i# d4 I @{ + L; Y R) G5 q, G int i; for(i=0;i<n;i++) ( I/ ]# C e7 Y& z if(i!=row)c[vol]=0; ! Z2 q7 \; \# A. c% s} ////////////////////// & u: Y) T4 z. m# Q0 H# }* k$ pvoid Start(float b[],int code[]) # A! W) ?1 n. n4 S0 K- I$ i{ 9 K# n5 I4 n2 p* h2 f, k int i; 9 x; j6 n2 I& [4 K& I/ Q float nget[100][100],nlet[100][100],net[100][100]; indexe=indexl=indexg=0; for(i=0;i<n;i++) : C3 l, j' F! F1 y { if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 8 |4 e; K1 f) U% S if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} - z% \* M3 N7 ~1 u if(code==2){ % r5 ~5 w9 o9 G7 B net[indexg++]=1; nget[indexe++]=-1; ! F: e( d# h/ G ] Process(net,i,indexg-1)rocess(nlet,i,indexe-1); } } 4 H/ [8 ^: {$ x* f g s=indexe+indexl+indexg+m; * ]0 m" X& L8 p& [4 A Merge(nget,nlet,net,b); ! l g" B- C1 Q! U' ^ ProcessA(); 1 m& a6 X4 r! Q# j" C5 j InitPrint(); 6 ~8 J& p% Q9 y Xartificial(); * f2 @" |& a5 O% A7 N! O}

void Simplix()//单纯形法 { int in,out,temp=0; while(1) / W" d5 J ] q# T) T/ d4 m( h { jckxj(); Print(); Result(); if(!rj()) in=Min(); % b9 _" b, \& \/ s, e; U! i7 l7 R7 @ else{ 7 G3 m2 |* v9 T& j if(indexg!=0) * i- t6 \* @! J) \; I& d JustArtificial(); 0 V7 W1 L" z/ w, n PrintResult(); return; " Z: ?9 G1 _' f* K) P( B8 h* O5 v: r } ; P2 a4 z6 M, k1 c if(Check(in)) % g5 g$ v5 p/ o/ b { cout<<"No Delimition\n"; 8 Y: b' p$ z& i( ?& C6 P+ B% s return; ' e* O$ X" P. B0 |5 X } + E, [8 W) t' r out=SearchOut(&temp,in); Mto(in,temp); 4 I# @- k4 X) `' L, h- w Be(temp,in); 3 G. T5 V/ R$ Z Achange(in,out); } }

void main() ! [/ H5 a/ N* f+ W x{ 9 {' S/ a+ a @. W; W int code[100];//输入符号标记 float b[100]; Input(b,code);//初始化 * f9 L- M/ n) N Start(b,code);//标准化行 Simplix(); 1 R% T5 C. `- k8 A/ l} ; M* B L2 S3 H9 r) e3 j

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!