数学建模社区-数学中国

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

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

#include<iostream.h> 4 Q ]% v, e2 c. V#include<math.h> 4 y' o; F, C$ l: }8 wfloat matrix[100][100],x[100];# s7 F% ~) e: E9 U7 L n int a[100];. l4 ]$ X0 k( ]& |, h1 a int m,n,s,type;) \7 o, b2 G$ ^ int indexe,indexl,indexg;: _: Z" A) \' F" ` ///////////////////////////////// 8 g8 w0 ], s/ W5 O. uvoid jckxj()//基础可行解 , x; i' S( X) i& ^{+ x. Q3 _2 n4 `- x int i,j; D M9 E% T2 ~$ d for(i=0;i<n;i++) 0 t. J' k3 t& P: I( T for(j=0;j<s;j++) 0 u1 c, z% A4 Y if(matrix[j]==1&&a[j]==1) 3 ?- ~( r0 Z" G( ^2 e6 o { ! L% P8 L& E! t# m& }# r) [- V x[j]=matrix~~;6 K" ^ d, E# h' D2 `$ _ j=s;5 m# D' [% H: ^9 I/ x }- `7 U* p! b2 M. | for(i=0;i<s;i++) ( o2 b/ D* d4 w; d) J if(a==0)x=0; - d0 ?% O% y( v8 N: M f" |" j}~~

( B( N( y$ y. n4 @: H
int rj()//基解矩阵3 F. Q! N: ^. }. S+ E' d {3 n# Z) F7 J) [ int i; ( d$ d4 e4 B* S for(i=0;i<s;i++)' M) {4 j2 R/ o$ W4 ?; R, y if(fabs(matrix[n])>=0.000001) $ q, {/ t: \" U, n if(matrix[n]<0)return 0; * `- U, w! Q3 E4 X1 f* Q$ } return 1; 2 g3 y% v% R2 ?, t} % x8 w7 c1 i, f+ l" e: Fint Min()//求最小的 0 B+ P t" T' ~, j& H `" `{, G2 ~0 v/ ~7 g/ L1 V- y8 C int i,temp=0;0 F1 y+ X5 f# N8 W2 Z float min=matrix[n][0]; 1 a; h/ r# G6 P$ U for(i=1;i<s;i++), J3 T6 Q* l. w5 }( N+ x if(min>matrix[n]) * l* N3 P: s9 L6 G8 X2 D {4 [& B% f$ b4 ?1 { min=matrix[n];# s' x* W' O8 _ Z& E+ I8 a temp=i; ; g8 F2 c3 v$ l2 {" @( {9 v } ' r8 ]6 u( A: Q return temp;& K6 W" Q4 G7 y9 e0 B2 b+ |, Z } 9 W4 a j) O! |5 C; I///////////////////////////////// $ d; C- P9 Y6 l- ?void JustArtificial()//人工变量, l9 Q6 P! {4 B! P! b4 f, p, @ {% o4 ]# W# j5 A" t, f* k/ x: b int i; ) e5 q9 ~" w+ y1 K- s1 z for(i=m+indexe+indexl;i<s;i++) * E6 D, e; b8 z if(fabs(x)>=0.000001) 4 q4 p8 A# A. M: d* l' r { 5 p* k+ m2 Z2 L cout<<"NO Answer\n";! r: r* W0 V& q9 } return; # a% t. r0 b! e! @3 p& ~$ K1 g# s } ) q3 }9 `! Y8 r5 V8 W} 3 s9 S, F& b4 I/////////////////////) g! ` {& d) k( F: x int Check(int in)//检验 . ?% q0 } f, W/ U: |{ / F; D& Y, C4 G/ k& j int i;! I1 y1 V" E2 u# } float maxl=-1; $ v! k/ S# c/ ` ^7 G for(i=0;i<n;i++) 7 I9 r7 _4 J+ i4 |. T7 g9 s if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])( d& M! q+ Q- h' e( T; m7 d! O maxl=matrix/matrix[in]; 1 h3 K0 b# x7 K! @+ G$ C0 v if(maxl<0)5 t( B: U. {/ v6 c% I$ _, O& y return 1; # a9 b! `) }5 V- T; S5 Q return 0; 4 V' }% [( u7 Q! R8 k} - T2 d8 w' N* Oint SearchOut(int *temp,int in)//出基变量 * ?( ~/ x+ v6 w2 R{ 1 J9 K" ^: m2 {" _ int i; 5 {7 g c O6 d. p) k float min=10000;1 \: Y5 {+ z' J- }* e! t7 }/ O1 k for(i=0;i<n;i++)' r5 v6 q; ]% }2 P: S if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)% x0 [' J+ i+ t) a x! } &&min>matrix/matrix[in]) 3 ^1 c9 k$ d* E0 b { + ]4 m+ e5 ]" D9 \# y: ` min=matrix/matrix[in];7 j+ ]/ a' S1 O' {# f0 g/ [% q *temp=i;5 D) ^$ d, b4 b/ ?( J& Q } % u! {1 n$ q% K$ A" v1 H" K$ i% ^ for(i=0;i<s;i++) : u) ?; ^9 H- n" Y if(a=1&&matrix[*temp]==1)! D5 ?3 k9 o4 s6 T return i; 3 W* u6 R3 ^# ^! G" w}" i) [8 |' n& b+ ~$ J* ?- i6 E ///////////////////////////////// " _4 J8 A8 |7 \void Mto(int in,int temp) $ I; H& n0 x+ D. j% j; Y{ * B' f' K4 ^* h9 Z int i; 6 l1 E" h# p6 S3 a for(i=0;i<=s;i++)* p3 i* c( H+ |% S- ^3 a if(i!=in)1 m, Q4 m7 h6 F+ L matrix[temp]=matrix[temp]/matrix[temp][in];7 ]4 u/ D, ~1 ~+ V' F* M1 W matrix[temp][in]=1;9 s0 c0 D/ x0 O6 w; I( R L } K* O3 Y1 _+ m6 A/////////////////////////////1 I7 o% `+ v; \ void Be(int temp,int in)//初等变换 4 \$ ~* E6 s" ] H! ` n{5 s/ O s6 n$ B @; ^: Q int i,j; 5 _2 h! T N6 Z' N: L8 w3 l# M# @ float c; e; Z% x6 \7 E0 W" t for(i=0;i<=n;i++) . ^# n2 b/ A/ D- R5 A1 k% I { : ^+ H) M0 R" `6 |: P" W# p; L$ t c=matrix[in]/matrix[temp][in]; - y7 ~% |8 f: Z$ x if(i!=temp)) ]" m; F S4 z for(j=0;j<=s;j++) 6 h t5 M5 |7 s* x3 E8 b2 F matrix[j]=matrix[j]-matrix[temp][j]*c; / d3 g8 R+ Q" M- K( X } : D& @6 Q* m6 c1 y0 U3 ], A2 S2 p} 1 `* A0 K6 ]+ z& \ [////////////////////////// $ L1 S# L o& U# xvoid Achange(int in,int out)//出基入基转换: o6 k+ D! A5 d- X {$ |/ i0 b4 t# I; r7 d" x) k/ a: q int temp=a[in]; `* R' f5 _$ u a[in]=a[out];5 C/ Y3 Y( ]) P- t+ D l a[out]=temp;4 `% \6 r. Y& u* w }. ]. K. c" Q) r) N5 T ////////////////////////: C% t f6 p9 Q) m6 i- r$ o void Print()6 y' H1 g/ V& n5 _, n1 Z { 1 D2 j( W% y. @. K7 t int i,j,k,temp=0; 5 T) z2 g& ^0 Z1 a4 c3 h* Q for(i=0;i<n;i++) 9 A* i' ~; A, W' p { 4 B" s/ m) |8 D5 X4 |7 U$ J3 R for(k=temp;k<s;k++)8 q# j2 S2 e. ? if(a[k]==1) ! v& v9 x3 E! O( n {( E/ M0 L5 \5 A7 l4 Z cout<<k; D- d2 _& J: T- G. d' G$ n temp=k+1; 8 r+ B# }! ?& e k=s; : R- Z# [ h2 U2 @! L/ m3 f }% t2 | p5 X0 f/ v for(j=0;j<=s;j++)5 i+ T- J7 O1 ^0 g- V9 L1 U2 y4 r cout<<matrix[j]; : H5 G, t5 ~( }4 e m3 a8 k cout<<"\n"; % E6 K8 U) j+ P3 O% X- L } 3 Q5 {: ?" r" m7 O3 o. u5 H. p cout<<"Rj"; 0 l+ K0 F0 a0 A* k4 L; j for(j=0;j<=s;j++)! E- s& G/ R3 o: Q/ r1 ^; @1 j* U cout<<matrix[n][j]; ) d2 H' k& ]1 r' [ cout<<"\n";1 g( K# ~/ _) E+ U2 t }) ?1 y x# ]% w0 ^2 R$ L ////////////////////////0 q+ k3 v6 n" o+ e8 R) i6 t5 Y7 ` void InitPrint() 2 g. _8 ?+ e' Q8 s& t{# i2 k4 k/ r: z6 K int i;5 e4 I8 P& I/ B! T# Q$ @ cout<<"X"; 4 K) R' P. _6 H, N3 g; @) O for(i=0;i<s;i++) ) ~9 c# v8 |. N9 f* T( ?/ Q* h cout<<i; / H- f! c* S& j7 `" P6 e: @ cout<<"b\n"; , q/ [- ]& V1 F! S! y+ Y cout<<" "; : k6 [' t/ F& ~- \1 I9 w cout<<"\n"; 4 j# \4 Y% o) J/ q- s' Q6 \} 3 T; x4 N+ C; u) O7 n5 Y' P//////////////////% a: s, k6 w3 L4 u. U5 D void Result() 4 F/ X$ ]6 K0 O; C{ 6 Y2 @7 Q. R i. d# ` int i; ( c5 x6 O+ f# t. y2 ~- {; q, p cout<<"(";# @& s: D! v( m3 ` for(i=0;i<s;i++) w; Y7 ?9 y$ ? cout<<x;+ p+ |* X, }( N7 U! Y! q" ` cout<<")";, @6 f; \" u9 A2 T$ S( |: r if(type==1) / T+ c% k! I- Y% ~6 x1 M! } cout<<"Zmax="<<matrix[n];- w7 m, @( ~5 c else cout<<"Zmin="<<matrix[n]; 7 y A, z6 d& X: v8 ~1 [1 e: n} % C% Z! b5 H- @- \' j% o) V4 a//////////////////////# v( r+ F# @( F* d void PrintResult()4 Z( n! F( Q; I7 B {9 [' B4 i* [) j( C* { if(type==0) 3 j( ]3 x; p; J! E cout<<"the Minimal:"<<matrix[n]; / T9 ^% |/ p* E else cout<<"theMaximum:"<<matrix[n];) Q h4 ]4 x( p }8 R( ~; p4 w" W2 l9 j" t" m, Q! r //////////////////////////////// 9 L9 A a5 M9 A% R, f9 ]& f0 avoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并2 g: [0 q+ J2 X, ^* i# g4 J4 ]3 V& c { ) `& V2 q# }; G2 M/ I# ?! U0 r int i,j; 4 T8 k9 S! V6 e N; c1 H6 [9 T for(i=0;i<n;i++) 6 N% |/ x+ C$ x {- o5 b! B' Z1 V( b7 P for(j=m;j<m+indexe;j++): }4 V G8 C" A9 W if(nget[j-m]!=-1)matrix[j]=0; 9 M9 O8 S7 i5 D5 n" q' x& F else matrix[j]=-1;! X4 E, J* B% p/ m; g7 i& X for(j=m+indexe;j<m+indexe+indexl;j++) |" k6 B- f; n' b; w& {7 F$ m if(nlet[j-m-indexe]!=1)matrix[j]=0; 7 `% B: f6 S, s- M else matrix[j]=1;6 d5 C V5 a, m# w' b for(j=m+indexe+indexl;j<s;j++) % p: s/ ^/ R9 I r if(net[j-m-indexe-indexl]!=1)matrix[j]=0;9 J+ J8 ^% |! d: a1 T0 X; d else matrix[j]=1;8 R' b) i) C5 t& K4 d } , |. l: J; ]3 E3 s1 I for(i=m;i<m+indexe+indexl;i++)1 h: u2 O6 \; V$ l# O, M( W# [1 t matrix[n]=0;, r- U" Y) w& s# C; g# z6 e7 H for(i=m+indexe+indexl;i<s;i++) & ?$ Q" v9 p/ D+ W: q: T+ f: \ matrix[n]=100;4 J# t' C+ ~+ G9 }1 }5 ?8 @ matrix[n]~~=0;' Z$ C1 I0 S0 V+ |/ X2 K; q }~~
& ~3 V4 P: l% a( ` Q
/////////////////////////// % l h4 W: m& B* Fvoid ProcessA()//初始a[] Q1 }, T+ e7 T* a{ 8 s* N- ^" B! X& E3 l int i; A# {$ Y7 s9 q: V. G for(i=0;i<m+indexe;i++) " O. A' p6 B! H3 m a=0;# v% A" |7 f* f) j( f$ Q for(i=m+indexe;i<s;i++); [, ]" L/ l. K3 X( R. ?3 B a=1; - P! i4 o4 _; A. Y, {9 c}
( q$ T# V8 x8 Y6 S- ]0 a
//////////////////////////////// w" U ^9 p# n2 [$ nvoid Input(float b[],int code[]) . U: p$ s( Y9 O' X y{ 8 J5 p1 @. P& I0 S7 C+ z int i=0;int j=0;" G" k5 Q8 F. i1 n- h cout<<"The equator variable and Restrictor\n";$ U, ]. j3 Z Z2 O cin>>m>>n;& h0 Z/ _7 K( F for(i=0;i<n;i++): D1 t3 f0 u1 |: ]) ^ { ( C2 M4 B! m5 T6 M% J5 I. G cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";8 C, u9 x0 [7 L cin>>b>>code;4 e- J: m. Y; {: ?& n: X cout<<"The 系数 \n";4 {7 U+ p8 y5 Z( `. w! m& a for(i=0;j<m;j++)6 u" W% X" n' }9 r: O4 N0 @* { cin>>matrix[j];' J# m, L, o y& D }1 z& D( |( |, h; O# f4 d cout<<"the type 0:Min 1:max\n";' {! L7 \1 X% S0 ]3 ]! r: q do{ - }2 C" Y3 X* s! | cin>>type; , Y& h3 K7 ^! ]! P if(type!=0&&type!=1)3 B4 O5 A/ R7 n6 K cout<<"error,ReInput!\n"; + V) e3 O' H- d }while(type!=0&&type!=1); . c: f$ |2 p; U8 R+ g1 b4 ` cout<<"the Z\n";6 G5 x7 k. V$ ]( L7 l for(i=0;i<m;i++)1 p; y4 P- y; B% B cin>>matrix[n]; {+ `; i8 N, Z6 Q1 d3 T if(type==1) + Z0 N. U: u9 N% Z; Y6 u& F for(i=0;i<m;i++)/ q- @! V* s6 O+ J matrix[n]=-matrix[n]; # y; n' ~0 v; L$ v6 M9 q}
( Q) k: I6 ]+ T3 k& O
+ q3 A" t- E0 [9 x4 O3 R////////////////// 7 S3 y. ^% Y! d* Ovoid Xartificial()//消去人工变量: d, W, S3 P/ Z2 T. s+ y4 L {2 Q. U( B: L' ^& L5 k int i,j,k;" A- n6 V* \6 x if(indexg!=0) . \2 f) G g2 R% E2 |! l: h- K {$ y/ n6 m) _6 S for(i=m+indexe+indexl;i<s;i++) 1 H8 G) e6 U8 ]+ g/ n { ) v8 T m, j, [ for(j=0;j<n;j++) : b5 N; S7 i, a3 q( Z/ n! C if(matrix[j]==1) * U* M% `* U5 b' r$ V { 0 _% \0 k3 P2 d for(k=0;k<=s;k++) - ]/ { w4 D; }. | matrix[n][k]=matrix[n][k]-matrix[j][k]*100; 8 z2 W4 J* c! k4 h1 a& z# ` d j=n; ( P/ V: ~, L& I1 q& A }$ M6 b! B( |4 I* V } ' J$ c9 l; q: T" ]9 h' m# D }5 |7 w. @! X4 O5 |9 M. B }
5 _ H" d3 x- F- @" H
////////////////////////////////////////////////8 L d( F7 P$ @$ W) U$ C) L S1 { void Process(float c[][100],int row,int vol)6 o2 w$ _" C$ b5 g* z {2 ]8 B0 V: n# W5 c3 I int i;5 G5 V0 H# Y5 D* \' n; G/ Y for(i=0;i<n;i++) # B8 T4 P+ P" Q5 a if(i!=row)c[vol]=0; 4 ?7 @ X( G9 e( I+ P} * V" R% ]+ S# g1 w4 y( l5 }1 n////////////////////// # l# V! u1 k* Avoid Start(float b[],int code[])* m: Q% r; V1 V9 I6 | { , _( d: z' _# C int i;; {6 n- D8 x0 B7 s; S/ m9 X: R float nget[100][100],nlet[100][100],net[100][100];' u O {& d+ k7 V1 X indexe=indexl=indexg=0;( N+ v, c+ m- O3 `/ L for(i=0;i<n;i++) 3 z# B3 T( I: y( G8 N" r) O+ h { 3 d& x" B! d1 R( a. Y! ]+ B if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}8 B- d4 {, W! ? if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} 4 @6 W; n1 k. O7 u if(code==2){5 H5 ?" @! Y) y net[indexg++]=1;: H, P/ [7 E% U: P" t; `6 U7 \ nget[indexe++]=-1; 7 r& ` E' ^, R/ T Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 5 H5 B/ L; @. N } ; F6 n( v: K4 r0 u+ R% V. M }3 c$ ~- E* O" _3 n s=indexe+indexl+indexg+m; ' E% O# L, R$ y, A2 b% } Merge(nget,nlet,net,b);$ Q) H; D5 y, S# B$ @ ProcessA(); ' {8 d6 Q9 i5 u9 v0 _ InitPrint();; |0 U3 g0 r3 x& O7 U7 h Xartificial();+ D8 }1 D' L' Z- o* R }
0 _8 f% t( T1 y _9 j4 B& P1 h
void Simplix()//单纯形法 & s4 k1 e; ?$ y% h9 p, e" D7 ~{2 n0 c" v) m4 I2 e' p" \' O f int in,out,temp=0;, g* V" U& `1 \) F4 u while(1) 3 Y9 m6 N; T( W, s {* V+ c* K& G, p jckxj();, X- v1 t+ z2 y0 A Print(); * _$ ~! b- ]) A2 f4 o2 v( l1 T* a" h Result(); - M* P( p% s7 [& C: N: ^ if(!rj()) in=Min();8 D ~9 ^5 w5 `9 y else{" ]% t2 W. H: ?3 A- ~ if(indexg!=0) ) g) i" w( j; J* O3 ]7 A; C; Q9 k, p JustArtificial(); , M9 n+ F2 e; s1 n/ V0 r A/ p PrintResult();" a d8 E' }, x+ q return;% V0 O; i% ~; x8 n- L/ S } . T1 H; G1 _% W3 ], I if(Check(in)) ( {( r: w& q T1 i" E3 I' o { 8 T( K. x+ Y+ {$ |0 b# b/ o9 ~ cout<<"No Delimition\n"; * m8 T) ^; c _5 d& k3 R/ P return;$ M: J: z4 K* L5 t$ e+ ] }% e. |& \0 _ _" d! a out=SearchOut(&temp,in); , N4 V' _2 ?* j; z Mto(in,temp);% e# v, n$ i) H7 j; }( }- N Be(temp,in); 0 n; z9 C5 B/ ^1 H, ] Achange(in,out); 8 V% H5 Q2 c' E* g" w V% C }( J/ I2 C+ j1 `! w3 p }
3 Q6 m" Y' |! u9 v0 l5 a
void main() - s# \ T+ F$ a9 K b5 N{ ; n* Y1 k5 A' ]$ S4 O, b int code[100];//输入符号标记# m+ L9 a7 ]9 O% a float b[100];3 t7 L7 t$ }% Z! j" u Input(b,code);//初始化 . t9 P9 c4 q5 O# L+ Q* | Start(b,code);//标准化行* i; V" L+ G# j+ x8 R Simplix();0 {! _# x3 w$ S/ B" K& J1 g P1 u }! P1 n/ b2 ?) Q8 O+ B: s7 q, S
作者: 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