数学建模社区-数学中国

标题: 单纯形算法程序 [打印本页]

作者: zhyi 时间: 2005-4-18 21:45
标题: 单纯形算法程序
单纯形法程序，在VC++6.0 下测试通过！

#include<iostream.h> 2 ~2 L# O* N* ]) R; Y#include<math.h> & Y" B# t% C% t! r( `float matrix[100][100],x[100]; & e& C' M+ t! X0 C* N8 dint a[100]; 8 X# Y2 n" H4 V. J) b g6 Yint m,n,s,type;3 d8 J& g' s# z! g, j int indexe,indexl,indexg;5 A% z6 p4 Y f ///////////////////////////////// # u+ M5 |% a/ T; @: J0 T1 r9 [, {void jckxj()//基础可行解 / b6 b2 C$ I7 K/ l- T8 q& t+ p{' q2 p0 u7 F' E/ S" O int i,j;4 W. j. @/ Q, f9 x for(i=0;i<n;i++)1 L% u1 l3 e, F/ b$ i$ U0 s for(j=0;j<s;j++)$ ]3 ?* |' ?4 P$ \+ W" z* P' n if(matrix[j]==1&&a[j]==1)% K1 q; D6 A* B9 W7 ^% I$ m# O {0 n8 O, d: i3 q! e! W' P( J x[j]=matrix~~;% c2 D- p6 A6 i# m j=s;. s* { G: a# S" i/ x' H } # \$ _2 s4 ] k9 i. ]* K for(i=0;i<s;i++)( U0 y: z2 ? o/ F/ p0 t' p if(a==0)x=0; % F ?. ^3 K7 G9 O! b8 d( C}~~

( n9 j! n: ?0 U6 h1 q2 t% s. Z
int rj()//基解矩阵 2 b. ^9 k% ?# q+ W/ L4 s3 V0 b{1 k5 m: Z# z8 M+ U int i; + Q: U) T0 n. s: m for(i=0;i<s;i++) 6 O4 T* [* x, Z! m: b if(fabs(matrix[n])>=0.000001) " d5 N9 b4 O1 s# m1 F) F if(matrix[n]<0)return 0; ( Z* ?* f# L) t( d u( v9 q t return 1;' g! i0 U: f! N" w Y }" C, `" g' R. O$ O8 Z0 r0 c int Min()//求最小的1 o3 U! M1 A; Q- l6 h- d$ @ {/ l1 z$ w b- d, G5 E% I! B int i,temp=0;( D: P3 U' n, x, R float min=matrix[n][0];0 b- f7 `9 n. l1 H; k+ f9 B for(i=1;i<s;i++); K9 U- z, ?& U( ]7 |0 x! d if(min>matrix[n])$ M' L, R1 T1 j/ @ {/ ~* i4 H; l( i0 T& {4 J- ^8 A min=matrix[n]; 7 ]. i! A' }7 e0 P- ] temp=i; + J: N9 E5 n+ ]3 q } $ g/ O; n) x# Q" [7 {, }; Q" R return temp; ; L3 U4 }3 s! t$ y! m8 k} ' N9 s% m* T2 @4 v6 S( Y% {, I///////////////////////////////// : T; F. b1 i2 |$ t \- [; gvoid JustArtificial()//人工变量 f1 a2 d3 Q0 G- f& K5 R0 \ {; L5 s4 H$ u! N6 K3 e/ m int i; ; `1 e6 j7 h6 X G& q8 K for(i=m+indexe+indexl;i<s;i++) . ?- m+ h- f4 t+ }3 a; m if(fabs(x)>=0.000001) - `, F( v# i7 [/ b" o0 H* G% F { / l1 t Q/ A7 I5 b. W cout<<"NO Answer\n";: r: [( U3 f) s, ]0 } return; 7 K, `3 T# s. S) P) I }; F2 \8 W0 ?! V" D }8 M2 ?1 m3 C/ S, X( ` /////////////////////, x; v3 {- b; d" q9 e% U int Check(int in)//检验( y/ T8 H; r& f+ \' o: p4 d {& A$ F& b8 E W int i;) q" i! S6 P2 N: `( ]# b. Q float maxl=-1; X/ Y% [! l. V8 A for(i=0;i<n;i++)" _- ^' x( _& O. }$ T0 e; H if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) r* J$ p8 H/ l* h: c maxl=matrix/matrix[in];9 l1 {& J5 m& Q$ I3 Q. E: O if(maxl<0) * n. i( C7 r. o% M; `/ y' G return 1;' C$ C4 R- z+ z& ~ return 0;0 a6 m% F5 j7 P9 p, `1 H }! v3 j5 }# s% a/ }0 a- N int SearchOut(int *temp,int in)//出基变量 2 }4 D) k/ c2 k. V- d; A k, W{! C& Z a. V; v0 y* \6 m% F& R int i;& C# g& D$ ~$ Q7 |3 p! P float min=10000; N* ?, N0 g( f, S& V for(i=0;i<n;i++)* T8 Y: n7 m; C7 g; b7 B if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0): d( H V9 s# Y( } &&min>matrix/matrix[in]) @* Z; e" v: k$ p { p! ^) C- M& U7 e/ n min=matrix/matrix[in];5 N6 `9 t6 m3 \. P8 \! e Y M+ } *temp=i;9 T% d7 B) h: R" p } 9 S9 \8 O/ }4 B; q* } for(i=0;i<s;i++): [4 [, y/ r: P+ @+ o7 Y9 V& C if(a=1&&matrix[*temp]==1) # j* {% w2 p' P, n6 O9 ~5 }( @& I return i;( I! K: Q0 @- f5 } }- u' z1 W# H7 L2 e6 b& R \ ///////////////////////////////// 6 Z8 L$ Z2 H' l3 _1 S( `6 rvoid Mto(int in,int temp) * M! w1 c/ h; D{5 [, I' a) r' H, `8 ~- I. m' I/ Q int i; ( x& ]1 n2 A' w for(i=0;i<=s;i++)3 G, U5 K7 M* r) U. ? if(i!=in)4 E$ S6 t- B. c8 u+ {2 Z* r4 V8 E matrix[temp]=matrix[temp]/matrix[temp][in];7 D/ O7 \& e5 q; F9 b! y4 _ matrix[temp][in]=1;/ b+ ]! R" [- a } . i3 t/ [# X( a% q///////////////////////////// # I+ s: s* L0 x0 O' X7 qvoid Be(int temp,int in)//初等变换* R* S# k( g w/ Q. ]8 b4 x" J { 8 I" B& x' J8 m: x3 R7 U, d int i,j; % Y# L3 y4 i, w9 h, Y0 `! i+ q float c; , e& I1 o9 k5 h) F& D for(i=0;i<=n;i++) , [" ^7 R1 |" a L6 Q O/ A {- k- g; M2 ?2 G) S1 } c=matrix[in]/matrix[temp][in];# o1 G: A# J8 A2 V: O if(i!=temp) 5 h% t1 y/ L" m! Y' e p- j4 C! I for(j=0;j<=s;j++) ; w" G& N2 A9 j1 p matrix[j]=matrix[j]-matrix[temp][j]*c; + s3 g3 J& W5 ]$ z: U2 k }" X3 b+ z$ J$ D, ^ } , ~- F/ d Z5 I% ^//////////////////////////. o5 ?# X3 q) d) `5 {* O void Achange(int in,int out)//出基入基转换 6 N8 b) G5 Y: @# ~$ @) z7 g{ - J8 b3 m6 @- ~1 M int temp=a[in]; 2 q$ Y9 T! }( t- H0 ^) C8 D a[in]=a[out]; & t8 `7 {6 E* o0 A8 o+ g a[out]=temp; ( a5 V$ o; N ^- _- e7 P) H} 7 _' h* K& Z e////////////////////////+ x! _% M# h; h$ b4 G$ v0 y S% X void Print() 6 H! ?$ x% Y0 I' o{) J8 Q1 c6 U5 K0 q; m+ [ int i,j,k,temp=0;7 ~' |9 z/ n3 J; D& N, \ for(i=0;i<n;i++)3 {5 g/ k \" p {" v: R, t0 c9 ^5 }# t# F0 l) B for(k=temp;k<s;k++) : ?6 _- p4 _3 S! q5 x0 k4 L if(a[k]==1) 7 {+ g4 Q* t, G. d& O8 I { - ^9 E# W/ Y& {; e+ R# \, r, M cout<<k; : g% H& K/ i6 V$ o/ @: Q: o. b temp=k+1; ! C h4 s* c! h$ k' r, V# u k=s;) D- K. n$ y t0 s7 `1 e5 x/ G } $ S7 b5 l. h4 i5 c* | for(j=0;j<=s;j++)/ ?4 O- }5 k/ W- `+ h( \9 A- w cout<<matrix[j]; , R* r# A$ h3 X9 h. E cout<<"\n"; % {6 ?% i" e7 N( [ }* P3 e; \# z3 J7 T1 p8 | cout<<"Rj";$ y3 Q# _7 x# ^9 l5 W for(j=0;j<=s;j++) ' Z% f# ~5 a! G! w cout<<matrix[n][j]; * l& J a; h$ `" B+ I* V, W cout<<"\n"; $ F) {5 j9 j& ^2 Z U} 2 |( Z' d1 v [4 d$ E8 ^! [; d1 m; t////////////////////////' P/ }& _: l# R' X$ I void InitPrint()( t. n/ D& a+ B# R6 [- a. t% k3 A {. u& u* p% W/ s [2 A ~ int i; % C3 [ |/ B, N" r cout<<"X";+ T6 [) `: T! x. A- |3 h for(i=0;i<s;i++) . A1 U7 f% C: m/ g) L \3 o0 h( i cout<<i;+ U( E; e0 i4 f7 V) a% R; g cout<<"b\n";5 x/ ?) _3 |) Y0 C. }& Y cout<<" "; " n& G+ T$ _$ n2 s cout<<"\n"; ; ]6 p) V. d# L* e ?} . l9 ?' f/ R9 B% C! Z- t+ i//////////////////* K8 @1 T& D' Q4 T' d void Result() * \4 k( W- e, S& S+ g{$ a8 X+ @* n2 z0 N int i;# A' Q% p) t4 G. D, ^ cout<<"("; ' r5 c1 u, q2 Z: A6 F for(i=0;i<s;i++)0 k m# C4 u6 F# w9 |7 \% O- I8 p' j cout<<x; ; V" w1 G9 I% q$ t4 f" j% ? cout<<")";( m! `/ y" [3 s) t! F! R4 ~+ b1 g' V6 _ if(type==1) 0 r! B7 J# q/ Z cout<<"Zmax="<<matrix[n]; * i# v7 i% k, e- o9 j; E' @ else cout<<"Zmin="<<matrix[n];: @0 o1 W3 v; W- Q! T2 H } ' r8 y' \" z, ]* R& A. `$ _1 q////////////////////// 2 V, J4 J* k F9 q$ P4 J/ Bvoid PrintResult() # Z# U2 R$ C) v: G$ F# D{' Q5 F2 ?5 d, D$ X2 u1 A: ~ if(type==0) # p/ J; @- z1 v* u3 W" w; z cout<<"the Minimal:"<<matrix[n]; 2 ^) `3 P1 y: l, g; u; Q else cout<<"theMaximum:"<<matrix[n];# v v0 h2 y9 `1 E- n7 g }4 O, O5 T: @) D ////////////////////////////////" b( b' s* L+ _ void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并5 B, n8 i S2 g' T { 2 g! B+ d ^0 X/ @) {) O8 z# ? int i,j; 1 l1 z9 C& a% Q/ o. h' A, l4 v for(i=0;i<n;i++); T' O9 A5 M7 ?. P { 4 R7 B* L9 E( {0 ] for(j=m;j<m+indexe;j++) ' |- c! |$ q# x+ d6 J: ? if(nget[j-m]!=-1)matrix[j]=0;' m# M* K6 g9 V$ t c else matrix[j]=-1; ) N$ y3 H5 m7 l for(j=m+indexe;j<m+indexe+indexl;j++) z" H( ^" } e if(nlet[j-m-indexe]!=1)matrix[j]=0;0 B+ f0 o7 f# @" I else matrix[j]=1; 2 ]" I0 ~1 D' \8 O$ y for(j=m+indexe+indexl;j<s;j++)& W, u" s+ |# C e. F+ A( w; _ if(net[j-m-indexe-indexl]!=1)matrix[j]=0; : M5 s' i- ~2 }9 u else matrix[j]=1; ! U# X) K, o- j4 f }- A% v6 f. Y) N5 E5 U1 y4 C( L for(i=m;i<m+indexe+indexl;i++)+ g3 U' F6 W& v# T matrix[n]=0; ( F9 E/ {, n. P& [2 F/ |/ K for(i=m+indexe+indexl;i<s;i++)9 L) `2 j8 x( W3 C- x matrix[n]=100;- c- N$ h! K6 M) T0 P matrix[n]~~=0;3 ~0 w, |- P8 R: T( O }~~
; _9 y$ t( F0 }6 r- g% ^
///////////////////////////, z K: }$ }( v: \ void ProcessA()//初始a[] % G" w$ x2 V5 x{ 6 o$ h; |# J V* e$ B# } int i; ) J( |" W/ I1 ~# P( U; y c for(i=0;i<m+indexe;i++) 8 `/ d O3 a7 n- Q5 J, } a=0; ! w; Y/ {% F4 [. } y for(i=m+indexe;i<s;i++)% `. J$ r: w9 I a=1;3 R3 i+ R4 m) Y. ~7 i7 _9 B }
6 r I; F3 u5 O& v0 G
////////////////////////////////) P& Z D: [1 ~- H* d& r void Input(float b[],int code[]) K1 E/ q# m" h# I a{& K& u. ]+ l3 ] \ int i=0;int j=0;1 t. w* c/ _& n4 S' C- X: W cout<<"The equator variable and Restrictor\n"; ' {. d" S! k$ D" M cin>>m>>n; & i( ~8 o7 x. ~8 N4 } for(i=0;i<n;i++) / I, r) p, \% s$ v {/ d9 J& S0 l! `2 c+ P$ @- g7 [9 A cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";; E x8 B6 b: b+ g! D cin>>b>>code;) l" `. a4 Z# c, Z, z cout<<"The 系数 \n"; . `) {! u( u1 H9 p for(i=0;j<m;j++)' j# O9 ]; D9 I+ `+ F cin>>matrix[j];: ?: f5 \! p/ \ }" s( |+ h7 X2 f cout<<"the type 0:Min 1:max\n";! _2 J0 u' B1 {$ d do{1 i4 ^6 S& A* x4 P cin>>type;+ e9 w5 p+ d; X7 K, F3 e; o! X if(type!=0&&type!=1) " I- b( H) h* q6 f& H+ |, h! { cout<<"error,ReInput!\n"; 7 _! O* Y( l5 E9 n7 q }while(type!=0&&type!=1);. J" o1 K) _) u cout<<"the Z\n";" s4 d" c& D! Y2 o2 W ~ m for(i=0;i<m;i++) ; B% T- F4 |! K. G" g- C+ D cin>>matrix[n]; . |8 S2 c! u# V1 L0 i& h( m+ f if(type==1)3 n& \1 k$ {, b( m9 ^( ? for(i=0;i<m;i++) 1 }. S) A# A" I3 _1 m- D g matrix[n]=-matrix[n];8 b' _0 m# Q1 M5 K) y }
3 y6 n& H% O% E2 E$ B* ^6 p
5 {( {/ }# H1 i+ b////////////////// 4 B6 X& {! Z9 k7 t% W2 Uvoid Xartificial()//消去人工变量 1 ~. t4 E8 x' t6 U7 M{ * u) \2 d% D3 a0 |+ o int i,j,k; ! Z/ i+ h; \7 N% v. @8 v- ~" t if(indexg!=0)5 v+ W! v0 ^/ U" Q# y {) Z; {8 ^: Q d5 ]; m W7 { for(i=m+indexe+indexl;i<s;i++)9 n; E) i1 l$ F& ^* u' G { ; R, f' D1 K9 f3 Q) D; c) r for(j=0;j<n;j++) 7 ~# B& {4 F* O) W# s+ i2 R# w if(matrix[j]==1)' z7 r! M8 T; `# z {3 z2 E0 g7 i# I E for(k=0;k<=s;k++)# F+ a5 W+ N2 H( i) f matrix[n][k]=matrix[n][k]-matrix[j][k]*100; 2 j* s- x, w/ i+ P8 _& q j=n; + L4 c, |) A: c+ O1 O$ `* _ }9 w$ {8 w: c2 k2 l9 ^1 _ }' G6 A# L" f3 X. z! ?3 M$ o* o }) L, {' z4 P/ V* ^1 q: Y }
" E/ D: `3 v# H4 q$ I
//////////////////////////////////////////////// F9 h0 C% M |+ C! Y- ?9 B8 d3 Mvoid Process(float c[][100],int row,int vol) `6 M X+ X5 f, W3 g{ ( Y( u1 H9 H4 ]$ ^0 B; b! u int i; # t) x0 D9 W/ m2 J9 z0 ?8 N for(i=0;i<n;i++)- T& }$ f) d# w8 O+ f, O if(i!=row)c[vol]=0; 9 @) z8 d1 T3 K3 L& C0 v$ m}5 b7 }2 K9 _% C. U+ ]. D$ u! }. l //////////////////////; w! h; Z% U7 z4 w+ b! V; k void Start(float b[],int code[]) A Y! F+ C- j: @) e. n- n { 7 D/ ~/ C G+ @/ J. X+ A, i int i;5 P& I. C/ i5 P* Y* D7 c float nget[100][100],nlet[100][100],net[100][100];/ D. ~: \* C$ S9 c3 P. w indexe=indexl=indexg=0;& d" M% W! o3 a% ^( G5 ` for(i=0;i<n;i++)9 n7 s+ a! N8 F6 L8 _ a% J# R {+ e A- c7 I1 \8 I$ R7 d if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}4 H) }4 I5 s* H/ Z if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}+ ]# K& q! @. K. O* |9 M. X) P& a if(code==2){% I8 o# X% `- ?: j, U! E net[indexg++]=1; 3 O1 A$ j1 `$ A nget[indexe++]=-1;1 I3 r% v$ Y) D2 k2 H Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 5 P6 U J Z0 R6 L) j! T: h; ] } 2 v' a5 T6 N0 d8 p- E }- S* W, O ?2 M# t! B s=indexe+indexl+indexg+m; 8 V) U: J# D' R9 C3 j Merge(nget,nlet,net,b);" x$ C1 \: U9 P0 z ProcessA(); # E F# ?2 B8 A4 q J4 g InitPrint();# ^& H1 Q% J- b Xartificial();7 W3 a: ~. z. K8 g- a+ t: u) R W }
" _% a9 L, l+ R; v/ i% B: N
void Simplix()//单纯形法9 R6 X( x7 h- {. K2 y0 Y; q {2 ?, _5 `- P$ z6 c int in,out,temp=0; 1 H5 |! l% c1 J. J while(1) ! ~: w6 N1 }/ z: f) F2 x3 r { 9 q1 b% p5 c5 u# e( I0 C, M/ r+ B jckxj(); 8 x* \0 F& {' @# _ Print();, C1 C7 r- c9 C) P: W Result(); : J2 `6 M; @6 X% [) Y if(!rj()) in=Min(); # S4 F$ c5 A z* i! [) M" u S v f else{1 Y" w( S1 l, B3 h+ W if(indexg!=0) ; @9 e6 P, Q& b/ W JustArtificial();1 r4 A F. X9 G7 c PrintResult(); ! [9 e! ]% ?! i7 o+ ~ f return;+ w u+ N' b e: Q8 C }# k i) a. j! D, _7 o. Y1 l3 O if(Check(in))9 x/ A# p* h( C8 y5 A9 K {0 `2 ?2 |5 M7 H; j/ G cout<<"No Delimition\n";' [- N! `9 R6 M3 `% h6 R+ j return; ; c: Q% G) x5 g0 v }* n: N1 C; Q3 j# ] out=SearchOut(&temp,in);3 e O, Y5 L) s+ X6 G( p! E+ v- S Mto(in,temp); 0 E9 Q/ v, f5 y* t! g; a Be(temp,in); ( i% y$ Q- B. ?0 i Achange(in,out); 9 a7 k& T5 g0 @1 J7 {) i. r } 7 }9 L1 }! ^8 P- ]% K0 q: \}
W8 L' x [) Z4 c& j2 }
void main() 0 Z Y$ A# H3 [8 L# }& c" F{2 D; h: G. M7 w+ ] int code[100];//输入符号标记( p u' w& T0 ~5 a float b[100]; " i: K, X( ]4 x# h6 |0 p& o Input(b,code);//初始化" b) E5 c4 C, i# X- H4 v1 @# ~ Start(b,code);//标准化行 9 ^7 \' g" U9 o4 A4 s9 }9 x Simplix();# H2 _- o7 e; |' n } 2 S# ^$ `0 p* ` B, b! B2 y
作者: lvming 时间: 2005-4-25 22:44
谢了
作者: M_Tramp 时间: 2005-4-29 18:10
不错啊！！
作者: pangaogao 时间: 2005-5-4 00:15
Good!
作者: 那时花开 时间: 2005-6-3 22:57
好用不？
作者: 那时花开 时间: 2005-6-3 22:58
资源分配问题可以用这个程序吗？
作者: monkeytail 时间: 2005-6-10 01:42
哇，楼主强人！
作者: monkeytail 时间: 2005-6-10 01:43
单纯行算法是指数算法啊！
作者: bnulj 时间: 2005-6-11 13:14
这么长！看不懂啊。
作者: mengfanqi 时间: 2005-9-6 19:41

so well!
作者: 天亮 时间: 2005-9-17 11:45
zhyi,你好.我有一问题请你指教阿.有一个10维的有约束的函数,现在我已经有了一些可行点,其数目可能大于或者小于10,可行点之间的关系不知道,请问怎样运用单纯行法求函数的最小值.
作者: chenbilian158 时间: 2006-3-7 19:14
试试
作者: luom 时间: 2006-3-15 13:43

还有其他算法吗关于仿生算法的谢谢
作者: jixian 时间: 2006-4-16 10:42
顶
作者: 海云边缘 时间: 2006-5-5 21:44

有C語言的嗎？我要C語言的
作者: suolunga 时间: 2006-5-8 20:07
[em01][em01][em01]
作者: sfhnlgdx 时间: 2006-5-13 09:15

谢谢，我正在找这个程序，终于找到了！
作者: chz0829 时间: 2006-6-3 00:41
看不懂
作者: hustyangyang 时间: 2006-7-19 14:59

楼上的的确是位高手，这两天由于写论文要用到单纯形法的程序，就拿来用了，但是发现有些错误，没有结果或者得出的答案有问题，于是我仔细看了一下这个程序，将楼上的笔误，和一些其他的小错误改正如下，
注意：我不是用纯 VC++ 我的输出函数用的是 printf (),这样可以动态观察结果输出，以便于修改，这个程序是我花了一天的时间改的，太长也太烦琐，我看的也不是很清楚，只对限制条件是 <= 的情况进行了详细的察看，和修改，其他的情况就没有看了，程序中相应的部分有比较详细的注解，如果有需要可以和我联系，我们一起共同探讨。谢谢！QQ：116490942

#include<stdio.h>
#include<iostream.h>
#include<math.h>
float matrix[100][100],x[100];
int a[100];
int m,n,s,type;
int indexe,indexl,indexg;
/////////////////////////////////
void jckxj()//基础可行解
{
int i,j;                        //基础可行解即为非基变量对应的x=b, 基变量对应的解为0
for(i=0;i<n;i++)
  for(j=0;j<s;j++)
   if(matrix[j]==1&&a[j]==1)
   {
    x[j]=matrix;
    j=s;
   }
   for(i=0;i<s;i++)
    if(a==0)x=0;
}
int rj()//基解矩阵
{
int i;
for(i=0;i<s;i++)
  if(fabs(matrix[n])>=0.000001)
   if(matrix[n]<0)return 0;
   return 1;
}
int Min()//求最小的
{
    int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++)
  if(min>matrix[n])
  {
   min=matrix[n];
   temp=i;
  }
return temp;
}
/////////////////////////////////
void JustArtificial()//人工变量
{
int i;
for(i=m+indexe+indexl;i<s;i++)
  if(fabs(x)>=0.000001)
  {
   cout<<"NO Answer\n";
   return;
  }
}
/////////////////////
int Check(int in)//检验
{
int i;
float maxl=-1;
for(i=0;i<n;i++)
  if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])
   maxl=matrix/matrix[in];
  if(maxl<0)
   return 1;
  return 0;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;
for(i=0;i<n;i++)
  if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)
   &&min>matrix/matrix[in])
  {
   min=matrix/matrix[in];
   *temp=i;
  }
for(i=0;i<s;i++)
  if(a=1&&matrix[*temp]==1)
return i;
}
/////////////////////////////////
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
  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;
for(i=0;i<=n;i++)
{
  c=matrix[in]/matrix[temp][in];
  if(i!=temp)
   for(j=0;j<=s;j++)
    matrix[j]=matrix[j]-matrix[temp][j]*c;
}
}
//////////////////////////
void Achange(int in,int out)//出基入基转换
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
////////////////////////
void Print()
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
  for(k=temp;k<s;k++)
   if(a[k]==1)
   {
    printf(" %d ",k);
    temp=k+1;
    k=s;
   }
  for(j=0;j<=s;j++)
   printf( " %.0f ",matrix[j] );
  printf("\n");
}
printf("Rj\n");
for(j=0;j<=s;j++)
  printf(" %.0f ",matrix[n][j] );
printf("\n");
}
////////////////////////
void InitPrint()
{
int i;
printf(" X ");
for(i=0;i<s;i++)
  printf(" %d ",i);
    printf(" b \n" );
printf(" " );
printf("\n" );
}
//////////////////
void Result()
{
int i;
printf( "(" );
for(i=0;i<s;i++)
  printf( "%.0f",x );
printf( ")" );
if(type==1)
  printf("\nZmax= %.0f\n" ,matrix[n] );
else printf("\nZmin=%.0f\n", matrix[n] );
}
//////////////////////
void PrintResult()
{
if(type==0)
  printf("the Minimal: %.2f\n", matrix[n] );
else
  printf("the Maximum: %.2f\n", matrix[n] );
}
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
{
                                                             //置成我们需要的矩阵，最后一列置成0
                                                             // 1 2 1 0 0 0
                                                             // 4 0 0 1 0 0
                                                             // 0 4 0 0 1 0
                                                             //-2 -3 0 0 0 0
int i,j;
for(i=0;i<n;i++)
{
  for(j=m;j<m+indexe;j++)
   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;
    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;
}
for(i=m;i<m+indexe+indexl;i++) //将目标函数中人工变量的系数补为0
  matrix[n]=0;
for(i=m+indexe+indexl;i<s;i++)
  matrix[n]=100;              //置成M
for(i=0;i<n;i++)                   //把b[]的值赋给matrix　
     matrix=b;
matrix[n]=0;
}

///////////////////////////
void ProcessA()//初始a[]    a[]是标记基变量，若为基变量则为0，若为非基变量则为1
{
int i;
for(i=0;i<m+indexe;i++)
  a=0;
for(i=m+indexe;i<s;i++)
  a=1;
}
////////////////////////////////
void Input(float b[],int code[])
{
int i=0;int j=0;
cout<<"The equator variable and Restrictor\n";
cin>>m>>n;
for(i=0;i<n;i++)
{
  cout<<"Inputb[] and Restrictor code 0:<= 1:= 2:>=\n";//输入b[]和限制符号 <= ,= ,>=
  cin>>b>>code;           //分别输入到b 和 code 中
  cout<<"The 系数 \n";         //提示输入每个限制条件的系数
  for(j=0;j<m;j++)
   cin>>matrix[j];
}
cout<<"the type 0:Min 1:max\n";//输入要求是类型极大还是极小 0:Min 1:max
do{
  cin>>type;
  if(type!=0&&type!=1)
   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)                    //如果是求极大，把它转化为极小来做，系数全部反号
  for(i=0;i<m;i++)
   matrix[n]=-matrix[n];
}

//////////////////
void Xartificial()//消去人工变量
{
int i,j,k;

if(indexg!=0)
{
  for(i=m+indexe+indexl;i<s;i++)
  {
   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;
    }
  }
}
}
////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)
{
int i;
for(i=0;i<n;i++)     //i =0 时置第一列为 1 0 0     i=1 时置第2列为 0 1 0
  if(i!=row)c[vol]=0;
}
//////////////////////
void Start(float b[],int code[])
{
int i;
float nget[100][100],nlet[100][100],net[100][100];
indexe=indexl=indexg=0;               //indexl 表示松弛变量数   indexg 表示人工变量数， indexe表示减去的松弛变量数
for(i=0;i<n;i++)
{
  if(code==0)    //如果是<=
  {
   nlet[indexl++]=1;         //松弛变量数+1 且置成相应的标记
   rocess(nlet,i,indexl-1);//传 net, 行号，indexl-1 过去
  }
  if(code==1)
  {
   net[indexg++]=1;           //人工变量数+1且置成相应的标记
   rocess(net,i,indexg-1);      //将刚加入的列单位化
  }
  if(code==2)
  {
   net[indexg++]=1;         //人工变量数+1 且置成相应的标记
   nget[indexe++]=-1;       //剩余变量数+1 且置成相应的标记
            Process(net,i,indexg-1)rocess(nlet,i,indexe-1);
  }
}
s=indexe+indexl+indexg+m;   //变量总个数
Merge(nget,nlet,net,b);
rocessA();
InitPrint();
Xartificial();
}
void Simplix()//单纯形法
{
int in,out,temp=0;
while(1)
{
  jckxj();
  rint();
        Result();
        if(!rj()) in=Min();
  else
  {
   if(indexg!=0)
    JustArtificial();
   rintResult();
   return;
  }
  if(Check(in))
  {
   cout<<"No Delimition\n";
   return;
  }
  out=SearchOut(&temp,in);
  Mto(in,temp);
  Be(temp,in);
  Achange(in,out);
}
}
void main()
{
int code[100];//输入符号标记
float b[100];
Input(b,code);//初始化
Start(b,code);//标准化行
Simplix();
}
/*模拟输入数据
max z=2 x1 + 3 x2
      s.t {
        x1 + 2 x2 <=8
     4 x1      <=16
           4 x2<=12
            x1,x2>=0
   }
2 3 8 0 1 2 16 0 4 0 12 0 0 4
*/
作者: 999mmg 时间: 2006-11-3 13:55
呵呵  绝对的好东西  我喜欢
作者: hnus31 时间: 2006-11-11 09:46
不错呀
作者: pytff7 时间: 2006-11-18 15:45
hai a 
作者: echo5183 时间: 2006-12-4 12:19

好
作者: jkkjk 时间: 2009-2-14 04:34
这么长！看不懂啊。
作者: aruisi 时间: 2009-4-4 16:31
我眼睛好花啊！
作者: Kadyniost 时间: 2009-8-10 00:26
。。。。。。。。。。。。。。。。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5