数学建模社区-数学中国

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

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

#include<iostream.h>2 F1 e- Q9 ~/ b! W. X" B9 J #include<math.h> * B1 m; s& R% v3 }: S0 Qfloat matrix[100][100],x[100]; , G; C: f# T) O. r# d2 cint a[100]; 6 x6 _" q) N8 lint m,n,s,type;/ ^. f6 h/ W/ w* }/ K9 O3 }* o int indexe,indexl,indexg;8 |" L+ n! f) ]* B- X, l /////////////////////////////////& g# r+ H" \7 P$ C& P6 D( x4 h void jckxj()//基础可行解 5 N5 ~" [% G ^# o9 b{! L p* m5 |7 b5 Z$ w+ {& M. T2 { int i,j; ; o! V! H% L/ L for(i=0;i<n;i++). [+ C6 v( @ x( E for(j=0;j<s;j++) , c) x6 E) g6 r$ N4 F6 Q if(matrix[j]==1&&a[j]==1)1 s$ A0 v$ F; u, y { * m; {; P4 i% \! |8 Q5 S! ] x[j]=matrix~~; & s; z/ G& T) J i j=s; ) ?% i8 s Q n2 c/ z; @' U0 J }& c! S' L3 B$ A8 b for(i=0;i<s;i++) ' O; |1 v5 d2 o4 m8 A3 B8 B if(a==0)x=0; 2 p6 Y9 \, ~% Z}~~

. c7 m& I T' Q- G6 R- x/ n X, [; z
int rj()//基解矩阵; r- Y9 x4 i' ? {2 Q& [3 t y! h6 X- _: G int i;1 Y5 t6 }+ J8 i$ [ for(i=0;i<s;i++): Y* ^" _) ]8 w if(fabs(matrix[n])>=0.000001)' W/ l# O+ S/ B# n+ ?+ G, A, B if(matrix[n]<0)return 0;1 A- [" x% Y; h: B4 | return 1;/ _4 d: h- a9 d4 T2 |+ K3 ? } * A5 {" x' I; p/ Aint Min()//求最小的1 R. ?8 n& U8 W# m {% o5 L* I! m0 J' J4 U int i,temp=0;/ L& W. T1 e; O/ N% U4 o& R0 R float min=matrix[n][0];5 S* H! x3 W+ a: g for(i=1;i<s;i++)! x. a" q0 p( P% n2 \0 ~: ? if(min>matrix[n]) l( W+ Y- J+ I% P3 y2 t { * U1 E5 i7 K6 w* C; f min=matrix[n];4 w- {9 ~( H9 p" `7 S! a0 k7 y& H temp=i; ! T( ?$ n" I/ A. X! o# `2 m! e } N: x% [* v! u. ~" ~/ l5 r return temp; / Y3 V* f6 ^( F/ [) ~} , a' S/ K- V Q$ X# G3 `+ H; L n$ K; s///////////////////////////////// 5 h* m6 G$ r8 R( N# lvoid JustArtificial()//人工变量) z9 u8 b7 H9 G { ( A1 ?, \1 j" h( L% A# W! g3 @. z int i;/ @7 y0 `, G$ u; _" o- T for(i=m+indexe+indexl;i<s;i++)" |- \' n( `) X( S5 J; Z R2 c3 G9 ~5 R if(fabs(x)>=0.000001)# h0 N7 ^* n' r4 K3 j {' {! k0 L( |, p2 R/ i cout<<"NO Answer\n";% @; @% b# P. h$ i return; / Y7 r& e) I1 y) A3 y# w, b }2 L. p' h9 M; A- i! v2 ] } $ _6 J2 P6 T2 Q; K" G///////////////////// p$ [( H! o, e' e+ J* {int Check(int in)//检验) b: ?6 J5 u% D! H- j$ O& } { 4 ]7 i2 ?! r/ f9 j* E int i; 0 R' j y1 W* ~+ N% F float maxl=-1; ) S% v! K- W$ ?: h for(i=0;i<n;i++)0 W1 m6 ], c1 T! J9 ], f if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])$ h( _" e5 X; ` maxl=matrix/matrix[in]; + G" A3 B3 C% T* | if(maxl<0) : p2 r/ M2 b8 W$ T* Q return 1;' j1 L3 ^- Y" f! E* K6 A" ^ return 0;- t' w" b7 T5 P- S) b9 u }! t' H3 T. }0 @9 v int SearchOut(int *temp,int in)//出基变量4 @. t7 s( _! E6 k9 L7 C {5 s- \% q! ^+ O Z& L% s! g$ S int i; . h. A4 J* I- a float min=10000;6 D% N+ ?) W; Q for(i=0;i<n;i++) 3 g0 y, h; J; q if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) : i: S% @% N8 S &&min>matrix/matrix[in])/ }- t* b) P8 ~2 U" a {( k z* ]$ w/ P4 w8 V: P2 C ]; ~ M min=matrix/matrix[in]; ' ?9 k9 ?% d2 [. i *temp=i; - \4 z; b. z- M+ M( B- Z } ; R# u# Z5 m, ^ L% Q Y& b" v for(i=0;i<s;i++)3 I; Z& z" \5 k if(a=1&&matrix[*temp]==1)9 R5 \% D5 Z1 ]; g+ B" A7 n return i; ) M; { j8 U) G( M$ ~6 e} 8 P3 l. i4 r2 ] o2 y2 S8 d; B4 |/////////////////////////////////. L3 x* }( c& g% i) [5 i void Mto(int in,int temp) : s0 f* I. r* U0 m0 d{9 w% V+ U, t) _/ ?" [; j int i;+ F' Y+ M0 ~ n for(i=0;i<=s;i++)3 I- ^; T' w6 r' [4 a4 \ if(i!=in)5 \2 T2 \8 ?8 ~. V# V2 o matrix[temp]=matrix[temp]/matrix[temp][in]; $ k( P/ i3 Y2 R matrix[temp][in]=1; ) F' G9 e3 ~' ^+ R: t3 \1 J}, `8 H' V3 i L5 l /////////////////////////////# G r, [- L7 h8 I( J void Be(int temp,int in)//初等变换 _! {) z- J6 E& d* J5 M {9 o. Y( ]. l( D( ] int i,j; . e% x6 ?! Z9 r4 a' T float c; ' j# ]" }# Z0 }# F- G# D5 V2 k for(i=0;i<=n;i++) . H( E! y+ l) h3 a1 e( z {1 E9 S Y- r1 q+ c; M c=matrix[in]/matrix[temp][in];% l1 M# X; g& h2 J* z+ A, h f. R4 v if(i!=temp) 4 ?* w) m7 B# { for(j=0;j<=s;j++)/ |1 ~% N( Y. P% i- Z matrix[j]=matrix[j]-matrix[temp][j]*c; 3 O* J% l6 w8 m+ d& f }1 D2 a) K, D2 X! z. K. f# i4 ~2 _ }8 ]% p4 L `! e( C6 G ////////////////////////// ! X, W; I- u7 F8 k+ u, e8 ?$ Mvoid Achange(int in,int out)//出基入基转换# s) r+ Z x' h) x$ }- k3 E V {& Z. k ?& R$ t! Y' o( h# G3 T int temp=a[in];5 y; k' I8 }2 v& H4 m a[in]=a[out];! Q; N+ C( b9 S/ d7 W" X1 d3 D a[out]=temp; + z! h0 ~% y% Z/ w& f. n2 U K}2 G9 F7 q! y6 h //////////////////////// * c' Q( i: C8 Cvoid Print() 4 O: g Z% F: r# ?- h. w1 S{ t/ X8 k' X3 M% p4 i int i,j,k,temp=0;+ {* ~( v" f. H" q% n, q for(i=0;i<n;i++) ) O$ m9 K) c# k6 v- b' t+ m { ! Y( z4 \0 G: F" b for(k=temp;k<s;k++)" I8 B0 w8 s" u% Q# \; | if(a[k]==1) 2 R# j c, ]0 \5 s1 ] {- e/ d8 G* Y( O* s cout<<k;% F( ^* ~, \" b3 D2 I temp=k+1; & Y# Y5 V& r$ j. U1 ~" t2 | k=s; 6 p: }- P& X3 o) a } 2 d Z5 Z5 j: q# R+ q. J for(j=0;j<=s;j++) / [4 w# ]7 ?% N, a2 J4 j cout<<matrix[j]; 4 r; b' H+ a7 I/ K cout<<"\n"; ) [1 }& T* W& c }4 A& M0 X* s5 Z% V7 g% m cout<<"Rj"; 2 R4 T7 ]9 ]! E8 i for(j=0;j<=s;j++)* J( i; X) \+ ?- U cout<<matrix[n][j]; 6 M, d( s9 D) B. X& a { cout<<"\n";- s8 ?0 |5 T! K } + S* p7 M2 X& T* |& ~# z; [////////////////////////! ~; ?: G3 q% Q; i" U void InitPrint() ; `2 P W; s. ]{ E& _4 @& V2 ^( [# b! Q7 K int i; 3 \ Z& x/ k8 A, l: i+ D7 u cout<<"X"; / @" S$ ^' Y9 U for(i=0;i<s;i++)! Z$ _5 K5 I. z2 F' U cout<<i;5 Y, q! K- ]! x3 h/ D cout<<"b\n";: e8 `9 e% [: G3 \ cout<<" ";! ^5 E* x: G& g* o% h8 n cout<<"\n";2 V5 w. r: H, h9 @8 z }8 t0 z6 [: p0 q# y7 N //////////////////$ X- a- B4 v, k! m# g( l void Result()) X7 g/ M% p- [6 x4 j { & F7 i. ?. e% X- f: W, a8 O$ c int i;. W7 V1 `! X: H \; Z5 J0 s* Q! L cout<<"(";; O1 w9 c7 S( y; y' _ for(i=0;i<s;i++)2 `2 W+ F0 g M) J' q9 S$ O cout<<x;/ L$ o! N8 O, S: w cout<<")"; * b- H. F; W$ \4 j8 {9 d if(type==1) , A; b1 u- Z) N1 {. @ cout<<"Zmax="<<matrix[n];9 w: M/ Z# [1 Q9 ?) ? else cout<<"Zmin="<<matrix[n];9 V2 m" i7 G. L7 _ } ! G Z& H' |( v! Y////////////////////// * q+ b2 T' f* q5 k! Uvoid PrintResult()3 v! z$ P: ~' S1 O, w4 c { . X5 d, [$ b' S if(type==0)2 G3 c$ D: A$ H1 ]. M cout<<"the Minimal:"<<matrix[n]; 7 Z; J5 _9 I+ n8 p: q8 {. n8 ^ else cout<<"theMaximum:"<<matrix[n];+ H9 }4 F9 g7 B9 k6 L } 1 D& F' U. u* n1 E' O U////////////////////////////////% p6 R3 s( j) J7 j1 V1 v7 d+ e/ y void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并, D5 Q( O1 \; E0 `7 V {" L& a; ~ v4 y% v int i,j; / \9 x4 P! R2 v% T* S for(i=0;i<n;i++)& y$ F7 w: _* w; ~ {" z) r6 G& Y, {' C/ L for(j=m;j<m+indexe;j++) 3 W) p! V4 ^( w+ r% e5 |7 I+ f if(nget[j-m]!=-1)matrix[j]=0; 1 N5 }+ f5 c A9 p/ W else matrix[j]=-1; 1 \# q' X" |5 e. Q for(j=m+indexe;j<m+indexe+indexl;j++) Y1 _, K) \' f+ S, B# { if(nlet[j-m-indexe]!=1)matrix[j]=0;6 Y& k3 a2 S$ L else matrix[j]=1; 7 O' I5 m! ?% v% ` for(j=m+indexe+indexl;j<s;j++) 3 X, Y1 L3 k6 k5 O E if(net[j-m-indexe-indexl]!=1)matrix[j]=0; . ]" M, B9 K1 X4 i4 F2 B else matrix[j]=1; g% P! Z0 g. N; w2 o } ( Z8 m7 W1 z# } for(i=m;i<m+indexe+indexl;i++) ( Z( a$ ]+ W% u2 d5 y% R matrix[n]=0; + W$ ~/ @$ ?" y for(i=m+indexe+indexl;i<s;i++), h5 T" m+ ~* y matrix[n]=100; : M& w& e) g x$ f3 T# g- S matrix[n]~~=0;# Z* ]5 R0 S6 \ n }~~
$ y6 w) s8 B7 N/ B1 x# j& Y& `, t& X
/////////////////////////// ) ~, h3 S, f3 U4 z- Nvoid ProcessA()//初始a[] , I+ c& }! F+ P{ 3 R, M: R, I* i0 M F8 r b0 ^ int i;3 H5 X5 u. }# C3 G' C/ g' n- | for(i=0;i<m+indexe;i++) & H9 y) r9 p* o4 A# R a=0;9 o8 D+ d% J6 d' z for(i=m+indexe;i<s;i++)8 L+ z. C: j9 U a=1; & U0 `) z/ P; ^& s}
: T' u! p4 H. C6 v- @# y3 p
//////////////////////////////// , h+ _* o; A4 R1 ?' w/ U3 f7 kvoid Input(float b[],int code[]) - K4 q2 M5 Q; i/ y0 P{ $ l. d+ ~( P2 V- I7 ~5 t7 G; { int i=0;int j=0; / T# @1 }4 N; }' v cout<<"The equator variable and Restrictor\n"; # R$ m$ t* h0 C cin>>m>>n;' B( U5 O" D* t for(i=0;i<n;i++)5 H9 l7 u0 {, v+ ? { 9 l; y( P% J6 |' C- q cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; ; m+ ]& ]5 ]/ Z; F" {- w cin>>b>>code; 3 `; U' n/ Z$ }4 K cout<<"The 系数 \n"; l' p7 u& @4 t7 Z for(i=0;j<m;j++) + M' e* r# t9 B- P% k0 { cin>>matrix[j];0 Z# C) h( C* c! R7 Z6 P) }( ? } - {4 }+ i8 R3 P6 B1 Q cout<<"the type 0:Min 1:max\n";5 | V5 V2 E9 w6 W do{: u# a8 l: a. Y& i6 a cin>>type; ) A$ o, ? u: U* a% W# M if(type!=0&&type!=1) + ~7 k2 Y7 f. d% t cout<<"error,ReInput!\n";$ } @4 I, c/ f `6 G }while(type!=0&&type!=1); 6 Y! V; `8 A% k3 g. S% Y5 U3 a1 M, Y cout<<"the Z\n";( Z7 p' [6 V8 N* J, C; ? for(i=0;i<m;i++)% `% L# P+ l9 Q cin>>matrix[n]; ! S* V5 C- K% I( y! a/ l# G, X if(type==1) 0 U9 q. g! S% T, x for(i=0;i<m;i++)/ R( I" K# b" E& P matrix[n]=-matrix[n]; 6 A# y) W9 D" r: A3 D% z& r3 `}
9 k a5 f% L5 N5 M+ ?
, y: |: f! e& r3 G: t ////////////////// # c% ^6 F! e* }$ Vvoid Xartificial()//消去人工变量 1 U' }4 [/ j! |- o' ]{ + d& J' r! F, T int i,j,k; + e2 m8 Q! \0 R, G/ d if(indexg!=0) 2 e6 e7 U, t( ^$ L {5 W2 U5 ]2 V, k for(i=m+indexe+indexl;i<s;i++) - b" W+ U2 q+ [' q ~$ E { 5 K) }! r5 h, Y; h4 g/ N" } for(j=0;j<n;j++)' F: o* [0 i+ N4 [1 M0 @! ] if(matrix[j]==1) # T( m+ V" g6 Z$ b {+ F4 b3 t1 `/ T9 L# b( H: d9 v for(k=0;k<=s;k++)% `. Y6 C0 v% n matrix[n][k]=matrix[n][k]-matrix[j][k]*100;- S, ?+ t% I' q" }/ k j=n; ' B, u. P; L' x0 { } ( a* w* W% L3 {; [6 N! G4 a0 S }1 H+ K0 m: }; u1 ]# y8 x W) t4 ^ } 2 a5 x7 u) I- p2 J" t}
; e5 {6 y/ p. V( u; e$ u
//////////////////////////////////////////////// 8 d. m) ^1 y3 k' Z+ avoid Process(float c[][100],int row,int vol)" Q H/ x4 t8 K {1 l8 v F! t) y. ~ int i;# m& d( S% \# A* w for(i=0;i<n;i++); d) ]' w9 R* h3 W8 D2 k; } if(i!=row)c[vol]=0; 5 Z9 x/ H9 S7 D, v7 W}- ]& O1 i* _3 z) h! }. Z ////////////////////// / C' Q2 n! w l8 Y7 ?6 F) ]5 s' ?( N5 Lvoid Start(float b[],int code[])* H! S! S+ L+ f9 V% w3 F { 4 o+ \3 G5 x+ }6 e: G3 w0 g. G* c int i; 6 W. z6 r; a( Q. c2 e! l. o float nget[100][100],nlet[100][100],net[100][100];; J0 ~0 W; }+ r# l indexe=indexl=indexg=0; 4 b: |( X/ O5 O$ C& l+ D for(i=0;i<n;i++) , r& N$ y' @8 u, w# x: N0 w- I: |6 G {* H2 R( o! u$ o0 C. { if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}8 A9 j _$ `6 ?9 L) X8 y9 ~ if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} $ q* \* P) B* x+ J3 ] if(code==2){1 y3 N u7 y9 e. I% V+ J$ ?7 Z net[indexg++]=1; , Y/ T# V$ V \ nget[indexe++]=-1;, q: }3 ]7 C2 t8 W) |+ ~0 I" N7 u Process(net,i,indexg-1)rocess(nlet,i,indexe-1);) H) W; U0 ^3 s6 `4 K } + E; f# z8 x! D } ! W8 ]% ~( ]5 v g+ q% l8 W; B s=indexe+indexl+indexg+m;2 k7 J6 l; ^: Q" Q1 }- ?6 T Merge(nget,nlet,net,b); 8 a. _. N' ^. l ProcessA(); * |& r; k; G* p. C' a+ g InitPrint(); * N- v3 g. G! g1 g _3 m1 C Xartificial(); 0 K" A$ y, V/ |% e9 M& s6 j- `( i}
3 s, |. n, K7 J
void Simplix()//单纯形法$ }8 {' u3 L/ K) ]0 u {2 d4 e) f8 b* ~8 X int in,out,temp=0; + i! B. i% f4 f while(1) + I+ @/ B, n) ~3 V' I$ k {- q) R* x: F9 r; N/ q. g jckxj();2 a) I4 Z0 |% b Print();: ]6 k/ ` H* i; e6 q* c4 r Result();7 O$ h& Y3 q0 e& _ if(!rj()) in=Min();% g2 K( o& q4 I2 B6 `8 M else{4 r9 ~: H3 V; o, v" H% m if(indexg!=0)9 p; p. S' a& g! u- v w& V: e0 e* `! Y JustArtificial(); 3 B7 y5 ^2 t, b! E2 n3 q PrintResult(); " {2 n. r; x) @2 u% E% j return;7 P5 r% M4 J! O } 3 I. N) [ z" A( F% F if(Check(in)) 5 i c" ^" G. P! ]$ ~" d& ^ {' T7 i- K# d! I' j cout<<"No Delimition\n";: P# M5 M2 c V0 \0 A) F return; : N' }# u! c9 x2 g7 A# }4 @/ n } % @' O0 c, t% l$ Y4 H) p4 _% N out=SearchOut(&temp,in); . t& {: w6 s& D M6 b1 _6 ]" P Mto(in,temp);, {$ t) N& s- g+ H$ n! n Be(temp,in); $ O* X3 Q# {" s, l. `$ L$ ~ Achange(in,out); + P) r" }% v$ C" c } $ t( ]" I7 f& G8 I0 M}
0 T9 G% u @- W, t+ n4 F: V& y
void main()+ q3 ^" ] w, i2 c. K { 2 V/ V$ W6 O |0 F* p int code[100];//输入符号标记; q7 S. W& _, w! K# @ float b[100];" o: Q; i- q5 R' E, F0 W& u$ R6 F Input(b,code);//初始化0 Y4 q# g$ r2 }/ G1 e6 Z Start(b,code);//标准化行 4 a) i7 G: n7 J5 a/ M# G Simplix();& M& U# x- o, A$ g9 ^8 ~ } 5 y( j5 k( }5 Z' b( ~0 E) i
作者: 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