12 3 / 3 页下一页

查看: 12480|回复: 25

单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

发表于 2005-4-18 21:45 |只看该作者 |正序浏览

|招呼Ta 关注Ta

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

#include<iostream.h>. a5 L: p% W `8 o #include<math.h>8 C& ?. S% l* j1 @ float matrix[100][100],x[100]; 6 q1 c5 d. u) d2 X1 X, P+ R$ ?) iint a[100]; ) M: v% ^5 N2 ~: u7 qint m,n,s,type;$ [' E) H; [% `8 b8 s0 M0 W+ D int indexe,indexl,indexg;8 {) j# l4 F# r/ K$ j5 j& Q z, z5 [ /////////////////////////////////. e1 \7 h# f; b8 a! f void jckxj()//基础可行解+ i. e! C% M! ]- @% ?3 f8 ^; w {( ?9 q2 Z6 x- p! K% t" D int i,j; U0 F. H% |# n; _ for(i=0;i<n;i++) - ?% p0 p0 k: v. c2 \4 [5 J; u for(j=0;j<s;j++)' m& \: d( O L9 p& O if(matrix[j]==1&&a[j]==1) & ?+ P% z* W9 \7 C6 r { + h8 M* t& Z R' @+ A x[j]=matrix~~;9 j- \* f Q" v- n" U- V j=s; ( t4 D/ b/ t4 n/ B* _; s* _ } % [+ e1 ^0 z% R* b for(i=0;i<s;i++) t/ \! X9 `3 N, ?, V% k if(a==0)x=0;" t6 D9 J! }, R) G2 s. r; F2 L }~~

& N6 `7 Y( Q R2 D9 T
int rj()//基解矩阵 . a9 w% T& S) c2 d{ ; I. I& s: e* O. b int i;0 O. ~) J3 J: l, Q for(i=0;i<s;i++)7 u- `" @7 h5 M% q8 p5 \, B7 o if(fabs(matrix[n])>=0.000001)) k4 X. U! s/ U# y if(matrix[n]<0)return 0; # h9 _/ H/ W3 F) R. T return 1; : u5 u% Z5 {0 p7 c- g' J0 i: M} ; p; G& I$ h) d, U# sint Min()//求最小的3 {; n9 G7 Z& e; c) k {, x9 i# B( E6 ^7 n int i,temp=0;+ ^$ [: E. w! ~' i float min=matrix[n][0]; 5 X) P7 l5 v# z, _& T) d for(i=1;i<s;i++)$ o6 B3 m$ r6 ~, V if(min>matrix[n]) 7 a- @1 t0 ?0 y# C6 L* W5 g& t {! l* {* D# N* G& R! |9 z min=matrix[n]; ( u+ q2 S3 f) e5 t( X8 W( F temp=i; 5 ]3 c! U* _3 r. _ }$ n3 Y2 U2 l; P H+ ~ return temp; " M% P& B2 X9 S' V Y. y. A}) l% J6 h6 V9 w3 w. W ///////////////////////////////// . W9 {$ I" }2 V' }2 }) Svoid JustArtificial()//人工变量 ; c4 s/ i: m, \* h$ p{ * A" n+ C9 F! M. q' P8 ?1 Q0 e. V int i; : P0 k4 y' I& r. C& Z& G( ` for(i=m+indexe+indexl;i<s;i++)7 [/ v9 M8 Z4 u if(fabs(x)>=0.000001) ' `/ E) W4 q1 \' r# r6 g { Y* X2 `( L$ K" z9 p \" D8 ^ cout<<"NO Answer\n"; 2 b" m; I3 {" |5 g; T8 U return; 1 y7 b. V$ y. D. D" u } / s0 c/ l1 R. O9 p2 s( _0 p, ^4 B} ' V& @1 |$ v, z% |- \: q/////////////////////8 a4 y7 p2 W+ l9 n6 [+ `: D2 I int Check(int in)//检验 4 k+ H6 K, @, F% C6 m# \: o{ 1 ]0 H* n& k$ d- ] int i; 9 K/ |$ C! e# Q7 P; h! f float maxl=-1;# s3 p, N; d- m! x/ @# G& Z for(i=0;i<n;i++) . ^; }; a3 a1 r& h7 s& e0 k' P if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])/ u/ n6 \% u7 `! W* R; R. z0 h: @ maxl=matrix/matrix[in]; 8 W; u v( b* D8 |: z( g" c if(maxl<0) 6 {; `# m J8 l1 i- _ return 1;6 r* O$ b3 o2 C return 0; * u- x7 C# P$ C/ ~} . i0 L( A" I; v; u% xint SearchOut(int *temp,int in)//出基变量 # }3 c! ?: [7 o0 L6 g% S{4 ?+ Y# o2 D. B6 ] int i; ! S7 d- c3 s7 g& k7 A5 U float min=10000;6 Z0 c+ F0 `$ a2 C- p for(i=0;i<n;i++) ' |6 \, p0 g M+ i. M if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) ; v, u9 K4 _. T b0 U% H J &&min>matrix/matrix[in]), S# c0 v& |4 e- n* ~' v. a u {3 ]5 K5 p' f" Y( @ min=matrix/matrix[in];# l0 f* r1 T; ~0 [+ J* I *temp=i;3 M" ]! u+ |. S( o0 G } 2 C7 s# \9 n6 H9 i for(i=0;i<s;i++) / y1 @5 J( T* Y if(a=1&&matrix[*temp]==1)% ~: L G; J' V. [4 g return i;+ B0 o5 J5 ~7 J o; N } n) v& v* Q$ h$ \1 t /////////////////////////////////) }2 L1 I7 F5 [$ Z, N- V6 D void Mto(int in,int temp) ) `# J- S( ]0 s0 I2 B6 M{1 M% ] t' q: a" K1 o) q int i; & t1 t, Y: f' r: N+ N) K. @ for(i=0;i<=s;i++) 5 z. J: N8 r5 H5 I if(i!=in); s; T. Y% L/ o matrix[temp]=matrix[temp]/matrix[temp][in]; M+ b4 `7 m7 P# M; _ matrix[temp][in]=1; 2 f9 |% j" H7 _}8 D& T: _& ?; l' |; m0 l* b /////////////////////////////) v8 m; }7 m0 L% g void Be(int temp,int in)//初等变换/ G8 I2 l$ ~+ C8 B' z) m% J: _4 l { 2 y5 |5 z1 o, E& |4 w9 B1 G6 P; i int i,j; - B0 ~, `+ k' @0 f float c;% z9 {/ k, f$ y/ W2 {# ~ X7 P1 H+ B! u for(i=0;i<=n;i++) % _, ?$ t& m/ E# J2 [' ^/ k {" w7 o; M. p* K: a* d- U4 O c=matrix[in]/matrix[temp][in]; 3 G: g* ?1 u+ P if(i!=temp) 1 a6 t! h' s5 ?3 K. [& ^9 E for(j=0;j<=s;j++): X+ f4 @: l' A8 L8 ~# _ matrix[j]=matrix[j]-matrix[temp][j]*c;+ c! N$ t1 W5 Y- }; ?- ?; M2 ` }! k* c }; u( j- u% Z$ _ } 1 n: v0 x) t7 U////////////////////////// ( @/ D- A6 ?+ Z! rvoid Achange(int in,int out)//出基入基转换% z0 w5 Q$ L0 Y y9 E5 I {3 @- G+ ?& C. C int temp=a[in];1 x) J. n H, b a[in]=a[out]; - b8 A6 Y t" ?0 j/ f( g# H J a[out]=temp;) p- g/ M S$ N5 a% ~3 n }; I* c1 V. z& K [5 o( J. U ////////////////////////6 S) m8 F8 J2 h- ~/ j2 m# d void Print()2 C' y0 {' h( n# F {9 l$ Y- R- T( S% ~. i( a, W int i,j,k,temp=0; f1 C, \8 n- B4 E. R# E' `# L for(i=0;i<n;i++) 6 o$ U& Q0 I& y3 D: x0 _ {" X$ R; [* x. R8 ?! g for(k=temp;k<s;k++) # ] M1 E5 D# ~& d* W8 E if(a[k]==1) c5 A7 S" [3 {: p. l. _8 A {5 `3 }2 Q- M4 y/ G3 | cout<<k;! P2 p: o& D- I temp=k+1; 8 z3 G# F) C% k2 Q" L k=s;# X0 t% D. `! z2 ~4 C* H }- w) U2 Q h8 h0 g! ?1 H8 C. f8 L6 i& p for(j=0;j<=s;j++) # T8 m" o6 L' l& Y, k cout<<matrix[j]; 3 O) s. @$ c% L8 \ cout<<"\n"; ; i9 {* K) {0 k- l+ Y% x1 Q } 8 f( w( ~: _# C5 y* E, r' {' T cout<<"Rj";0 N" x8 B8 t7 A* g% G for(j=0;j<=s;j++) - E7 y3 w1 _* n0 b( W+ | cout<<matrix[n][j]; f1 ~& b9 N3 n) d2 a( ` cout<<"\n";+ R8 j" S% E% i7 R, H& m4 w5 _ }) T+ E0 Z( `& x ////////////////////////: h8 S/ ~' u: \- H$ s4 } void InitPrint()' K% h! F+ B8 H' ~5 ~' e {/ _& s( T4 |' Z. Q int i; : G _0 H4 h" p4 s$ A7 w3 Q cout<<"X";' H% K2 w/ D6 B8 s- T for(i=0;i<s;i++) + i4 F) `3 o) O" B% M cout<<i;" Y) L8 p- Q7 l) r cout<<"b\n"; 1 g0 N. C) V; c, U P# P) N cout<<" ";# X9 } D' [$ O! z2 h/ u* t cout<<"\n";6 a% c' A+ ~" ]3 u } 4 \6 p# M a8 C/ }, ~////////////////// $ K0 C* G' R/ t8 Tvoid Result() 6 R3 Z! q; F4 b{# g6 J7 |' J" P0 J int i; , m( x$ ]: x+ C9 _ cout<<"("; 5 ?: g& U( t. ?6 L! Q0 I9 P7 K for(i=0;i<s;i++)$ X3 W9 d5 Q" z- F cout<<x; 2 k8 @! j% J& E% D2 l+ ~ cout<<")";% ]6 u! I3 X) B4 K' m if(type==1)0 I I) L0 v% }4 [( E! R K cout<<"Zmax="<<matrix[n];+ _2 X! ~0 G& x4 Q2 J else cout<<"Zmin="<<matrix[n]; - s) w3 \1 k! J8 [}3 X. I' f7 H, W D ////////////////////// % {; Q j5 b( b0 ^' L( O' Qvoid PrintResult() 9 ~6 O; ^& h. A+ T9 S4 N& N, L$ Q{ * Y, B; y0 d8 V$ } if(type==0) 8 o3 ~! ]7 R' i4 \8 c& O' ~: `3 Y7 B cout<<"the Minimal:"<<matrix[n]; . F) v3 u% `9 n( i1 Z+ O2 u4 U else cout<<"theMaximum:"<<matrix[n];, $ U8 M, q& m7 j ^ }: e& `+ X' ^) ~: D( b ////////////////////////////////5 d# X# F1 U5 x( D: F# F) @/ T+ P9 N. w void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 % g& S+ F' n# s# \0 H& B* K7 {2 H{ - A9 Q" m( k- m int i,j; / }4 o3 {' Y* _( a/ ~5 y for(i=0;i<n;i++) % ]: G7 a: n, x1 `" o. t" _: ]" o' x { 3 p: O3 V! g. ? for(j=m;j<m+indexe;j++) . A( D* M+ [4 K3 `8 W if(nget[j-m]!=-1)matrix[j]=0;. d/ R( C) i* b$ Z. n9 Z4 { else matrix[j]=-1;9 q; F' }& Y& K7 ?8 ?+ u for(j=m+indexe;j<m+indexe+indexl;j++) 0 i5 M6 _* @" O, |8 {, O if(nlet[j-m-indexe]!=1)matrix[j]=0;" I" {- S; e- _4 h% N y5 M$ c else matrix[j]=1;5 \/ I% T/ _, O3 J/ _0 P for(j=m+indexe+indexl;j<s;j++) ; v P! @: G1 m }9 n3 g) \% t if(net[j-m-indexe-indexl]!=1)matrix[j]=0; 9 $ E5 h% z& [* @ R! M1 m else matrix[j]=1; * B! o5 W. {( S1 }8 w }+ \: k9 I( V% d8 k2 T2 i0 { for(i=m;i<m+indexe+indexl;i++) 0 F5 c5 B& X) {6 F" ?( b matrix[n]=0; - }0 C' U. j0 G" U for(i=m+indexe+indexl;i<s;i++)- G5 P2 T/ t4 ^* u9 a matrix[n]=100; / s, l) J; V) T* E9 j matrix[n]~~=0;8 }/ @, [9 c2 c v0 s }~~
5 c) z% p: v3 w4 I! o3 d/ o
/////////////////////////// / s. Q; g' l6 k9 Q6 G) ?void ProcessA()//初始a[] * N- _6 z8 o L7 y; v{$ w) V" S! c# Z- b2 o7 M1 Y, b int i;! k; J$ \7 Z, O0 k8 N+ H4 Y) z6 Z* H for(i=0;i<m+indexe;i++) 7 I; @, @, X, `- ]8 s r: K$ s a=0;" p4 j8 H j4 Y$ R; n4 w4 {$ L for(i=m+indexe;i<s;i++) " {8 o4 |& O" T* x5 z; T' p w a=1; 9 F" K& c6 z% w; X* X" ]}
) X. {8 e A$ K! ^4 _
////////////////////////////////9 f( _0 A& f9 R" I$ a void Input(float b[],int code[]) 1 C% s) N) [3 M, n; b{5 R/ Y8 _7 ]' ]8 r' D4 a7 `+ u int i=0;int j=0;/ B- j# ~ y+ B) Y1 g- G cout<<"The equator variable and Restrictor\n"; 8 x6 s7 Y, T) G4 W& V cin>>m>>n; 1 |& l9 D5 F( Y" i$ E( ?* | for(i=0;i<n;i++)4 X! U" E" }8 k% e" W7 Z { 1 O9 d) Y1 V. m6 s2 ^- G x! \ cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; 2 I( B0 n/ D" A f cin>>b>>code;: ?) W6 t* {. @5 s) t4 f cout<<"The 系数 \n";7 W% u1 s+ W- O/ K' ? for(i=0;j<m;j++) . k+ q$ j: b% A( w: h8 j cin>>matrix[j]; : |* ?* X9 s( W$ @* q; ] } 5 n s6 [3 Z1 S( p/ s9 S cout<<"the type 0:Min 1:max\n"; 4 F/ B' C7 w( ]) A do{8 i/ p4 }* D2 S$ E: T3 o9 ?6 N+ G4 F cin>>type; 8 x5 P8 N& I$ i k" B6 Y if(type!=0&&type!=1)4 m/ x V9 A8 e9 X cout<<"error,ReInput!\n"; % |' f/ a1 j; v; p O' i2 H }while(type!=0&&type!=1);( j0 h* g4 b( I5 G1 S: I cout<<"the Z\n";' F" n# y; n8 D" x4 n5 b9 G for(i=0;i<m;i++). d- q- B# T$ v' I- v3 f4 k cin>>matrix[n];' s3 c9 H. ~! b& z if(type==1)' x( t- ^5 {& m% O# D2 i! | for(i=0;i<m;i++)6 e4 w+ H; n1 N6 ~- d matrix[n]=-matrix[n]; : q5 P! o2 g' d2 n}
- q0 k6 a+ n' X, l
) @. b3 x, g. ?0 u////////////////// 2 V- f( \2 ^% g3 C+ t, f _ void Xartificial()//消去人工变量- U1 U6 i/ Y( X& x { # {+ I! f) F/ g, c8 j: p- p" p int i,j,k;0 Z$ M" t/ }8 \, b if(indexg!=0)& y& j8 ^3 R: Q- \# Y; F2 Y: s6 G2 N { * u Y, j& M8 ?5 l n& Q- v) d for(i=m+indexe+indexl;i<s;i++) ( {# G" f7 H* g6 L {* u, O8 n$ m1 _ s' t/ C) G for(j=0;j<n;j++) k! A9 P$ g; b( t if(matrix[j]==1)* C0 G0 R% N" B7 \ {& | m$ p" _+ M L7 w) ~ for(k=0;k<=s;k++)' j( [6 X' R3 d matrix[n][k]=matrix[n][k]-matrix[j][k]*100;) L1 I" R/ P9 K" K* m; V. o9 f j=n;6 D$ I, X0 ~3 |% S; o) k$ D } 1 r) P- z+ x, f. V" ^) E } # [1 f, I8 X D( F0 t1 r; X! o$ w } . ^" v; | G! _ u0 x. [7 U7 `! I3 l}
2 |% W6 Z, P p0 c$ l9 D
//////////////////////////////////////////////// 7 T, n/ q! S( O# N2 _. lvoid Process(float c[][100],int row,int vol) 0 @5 ^' w" b7 }" B, k1 k2 {1 Q{, ], X2 W4 \: K& ]* \2 v int i;! B. }# _+ g3 G; G4 H3 H: @ for(i=0;i<n;i++) % [* }1 K: L$ R# `. X% c if(i!=row)c[vol]=0; 7 R* X3 g* m+ }$ x; t( C} ; f1 L* Q2 ~4 |- v8 p0 q4 i////////////////////// : ~' A0 _9 I& n% J! ~8 Xvoid Start(float b[],int code[])( a% h$ V4 d& \: |" r { 5 P* ?4 o z1 O6 N int i; " K' f- _2 ~& r3 V. S float nget[100][100],nlet[100][100],net[100][100];6 X- U0 _1 D- [- m( o- D- U& V' Q: T1 M indexe=indexl=indexg=0;8 k3 V7 \6 z9 @: T for(i=0;i<n;i++). s, p$ o# C! }/ G. K { $ C* N7 ]8 V. [* r8 N8 q! O if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 7 O' n8 l8 ^0 M: p8 X2 _ if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}2 M+ U4 f( q- y$ p. a1 n if(code==2){ , g5 e( f1 Q) q, { net[indexg++]=1; ; g6 y" Y" j% e! P; | nget[indexe++]=-1; 4 j4 \3 u; B% M% Z% G3 y' o Process(net,i,indexg-1)rocess(nlet,i,indexe-1);) _3 F: ^( r6 Z2 @. L3 B: C } : g/ }2 b; S& C/ F9 ^; N% r } 1 ^" f- J! ]- U, P: v+ B- Q: p s=indexe+indexl+indexg+m; 5 I% ?; J" G6 }6 [8 D/ I Merge(nget,nlet,net,b);, ^, {3 a4 f, { ProcessA(); 4 H8 l, A5 {( V$ W2 I InitPrint(); % G `6 o& C) ^# Z& u. o: ]) d Xartificial(); - g* n" f/ g8 k1 f}
2 G" K) P2 G- ]* v
void Simplix()//单纯形法 % r# d. ~/ p4 T8 k5 t. k' m4 J2 t{4 a; X4 W4 s+ v! F q int in,out,temp=0;7 r1 f" N6 A* O: Y+ r; ~' y while(1)/ C$ O# Y; p$ l" H5 P, s+ C2 u6 I$ P { 0 l7 [; _# l( r; A/ g jckxj();- H+ J+ P7 G1 S" b6 d) P Print();5 a7 ~- }2 R1 u# H) e: A( i Result(); , |1 d, I2 e! f& y5 D- M7 q if(!rj()) in=Min(); ; h# P2 L" T9 [! D4 Q+ M; L, w# ?- X else{1 G' M3 @. y* X" {5 L if(indexg!=0)) U& F: d q2 b& \ JustArtificial();" n- x$ ? e$ j$ f5 x6 f PrintResult(); # ?- y) O* U/ z% k return; 0 G; Z8 W" j' m& \ } 5 q* O2 H# p& o; o if(Check(in))" B, h! Z0 ]2 F1 |0 c0 k {4 u& Z3 b: E8 r cout<<"No Delimition\n";6 f/ O6 M- w1 a! [# W1 p return; 9 [' u2 |7 l) J }# n& |. V* D: r5 ^( W. l+ n out=SearchOut(&temp,in); ) q2 ~ ~+ g! P% h+ c8 o5 P1 K- ~! N4 w Mto(in,temp);2 A5 [" W+ x: U& u3 c3 | Be(temp,in); - r* f8 A5 a+ s Achange(in,out); % A C8 W5 l# _8 P5 m8 p, t$ l }: k! X! H1 L* u }
) y+ _! m) v+ G$ U5 P
void main() : E M7 c" M9 a1 X) N{, J; Y6 s2 ^" ~$ N' n; b3 }1 S6 s int code[100];//输入符号标记 . {2 h9 V A7 |2 W float b[100];" t1 l& @8 c! ?) f0 |9 d Input(b,code);//初始化 5 g3 B+ k6 C9 I Start(b,code);//标准化行. _$ f8 t# ^$ L6 n/ z' t! f Simplix(); 8 w4 \6 l v) P( @9 q}. Z7 P( r' A. T1 r1 o+ Q7 H! ^/ e) \! J

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

Kadyniost

0 主题	4 听众	187 积分

升级 43.5%

该用户从未签到

26^#

发表于 2009-8-10 00:26 |只看该作者 |招呼Ta 关注Ta

。。。。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

aruisi

5 主题	3 听众	2288 积分

升级 9.6%

TA的每日心情

	奋斗 2013-12-6 19:59

签到天数: 565 天

[LV.9]以坛为家II

群组: 数学建模

群组: 大家

群组: Mathematica研究小组

群组: 安徽赛区

群组: 我行我数

25^#

发表于 2009-4-4 16:31 |只看该作者 |招呼Ta 关注Ta

我眼睛好花啊！

我也说一句

发表

使用道具举报

jkkjk

481 主题	6 听众	52 积分

升级 49.47%

TA的每日心情

	开心 2015-4-4 06:20

签到天数: 8 天

[LV.3]偶尔看看II

24^#

发表于 2009-2-14 04:34 |只看该作者 |招呼Ta 关注Ta

这么长！看不懂啊。

我也说一句

发表

使用道具举报

echo5183

0 主题	3 听众	24 积分

升级 20%

该用户从未签到

23^#

发表于 2006-12-4 12:19 |只看该作者 |招呼Ta 关注Ta

好

我也说一句

发表

使用道具举报

pytff7

0 主题	2 听众	21 积分

升级 16.84%

该用户从未签到

22^#

发表于 2006-11-18 15:45 |只看该作者 |招呼Ta 关注Ta

hai a 

我也说一句

发表

使用道具举报

hnus31

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

21^#

发表于 2006-11-11 09:46 |只看该作者 |招呼Ta 关注Ta

不错呀

我也说一句

发表

使用道具举报

999mmg

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

20^#

发表于 2006-11-3 13:55 |只看该作者 |招呼Ta 关注Ta

呵呵  绝对的好东西  我喜欢

我也说一句

发表

使用道具举报

hustyangyang

1 主题	0 听众	18 积分

升级 13.68%

该用户从未签到

19^#

发表于 2006-7-19 14:59 |只看该作者 |招呼Ta 关注Ta

楼上的的确是位高手，这两天由于写论文要用到单纯形法的程序，就拿来用了，但是发现有些错误，没有结果或者得出的答案有问题，于是我仔细看了一下这个程序，将楼上的笔误，和一些其他的小错误改正如下，
注意：我不是用纯 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
   }