数学建模社区-数学中国

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

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

#include<iostream.h>' Y) i c' H1 {7 B0 m4 }% W3 |6 t #include<math.h> 2 D' T7 q* v/ g( \float matrix[100][100],x[100]; 7 A1 u! E7 ^$ e* `8 P! \$ \int a[100];4 l5 b0 j' P" I7 I* t' Y( x int m,n,s,type;6 T; T; [3 h4 e1 [ int indexe,indexl,indexg;3 N$ d4 ^% |: f" S5 f- g! }9 e ///////////////////////////////// " S8 F( t1 j5 d# q& W# ivoid jckxj()//基础可行解 - w1 F, h4 L% j+ x7 x" U( P4 N! a{ 0 `7 i' b$ p1 y int i,j;/ m: B9 q1 @/ Z5 i2 N8 Z for(i=0;i<n;i++) 6 w' L& S- c' r. T/ z1 H for(j=0;j<s;j++) Z6 @+ |3 [, i; W( c: r, E" W if(matrix[j]==1&&a[j]==1), E! v6 T% a+ T4 P' C/ r; g1 d { 8 c z4 T5 }" C. J' P x[j]=matrix~~;% o7 J; g# X) e; G j=s; 9 e: q% r5 v* Z. \) S }4 a; t% o3 `' Y6 N; H' k for(i=0;i<s;i++) 8 e+ j H9 g/ i1 F if(a==0)x=0;" {. s' B; `" c8 r }~~

8 Y; c2 l& K4 C' X
int rj()//基解矩阵0 o! e7 Y7 C: ]2 ]% l+ I# \ {, Y: O. m4 l$ A v" Z- i int i;4 Z9 C# T/ `! x% R for(i=0;i<s;i++) " v* S6 e/ V# q. r if(fabs(matrix[n])>=0.000001)& ~1 \& X; m) J2 I) a if(matrix[n]<0)return 0;3 p1 h4 M4 ?9 @2 j5 F! o3 _- F return 1; ) Y) L0 ^. |1 \8 t' t) n& ]( x} & s) _1 b! x9 Y1 @6 G* Yint Min()//求最小的 6 @3 Q4 ?: [: |8 v c{( U- a7 T' b9 O- @ int i,temp=0; . K& u' l& x- R1 Y2 M* Q float min=matrix[n][0]; ; o4 [ L U; G: D+ q7 g* ^ for(i=1;i<s;i++). N2 b" v3 N3 ]; p( V1 z8 g if(min>matrix[n]) 6 m( V% f" D" \7 z7 X- l' q {, l$ U- N. [. M( i/ y min=matrix[n];# m) y! @" H+ b6 M+ O1 F/ d# i) _0 h temp=i; , |- T3 L [7 W( a. u }' e" f! k- x8 ] S- j/ s return temp;. G; e9 S: X# P" z8 Z: c' N }& W# m, n! `# N& B /////////////////////////////////3 _8 J3 q1 _3 u/ o0 {6 |' J/ $ ` void JustArtificial()//人工变量$ L+ @! s7 W2 i- G6 Q9 z& N' P {" \4 I8 @) a) ?; D4 {! f5 P int i;, r* G T2 U. [: X6 o for(i=m+indexe+indexl;i<s;i++)5 H. B* X( $ ~: t4 ~& x8 T( m+ o if(fabs(x)>=0.000001) $ R; s1 v/ M- s( m) C {1 c! m+ P6 X& W. @! _3 H cout<<"NO Answer\n";4 {3 A* b6 e1 r, O: @8 w return;+ S* ?: R# d0 j5 d1 p* G }" n% `1 t9 G. A9 }( T6 Z t } 4 f3 s% O" {. `# r* g/////////////////////3 B! h' m e7 y. W# z. N int Check(int in)//检验$ ^ X9 a# y' c" A$ K% l* A { 0 d% i, V n' B: Y# X# k int i;$ Q7 C" Z1 d; a. Y# {* r float maxl=-1;$ a- R# B" H; ~3 B2 z6 K: J for(i=0;i<n;i++)' x& S; B" v8 }/ R' Q if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])/ Y; h' }) |+ g! u+ a7 {2 v1 |" S6 ^ maxl=matrix/matrix[in];! ?8 r* k& a2 f( @& y/ O0 p if(maxl<0)6 r2 @6 ]3 k% ]" Y) Z, ? return 1;8 q6 Z: G$ A8 V7 m3 [7 U return 0; / H/ y- w9 ~6 x+ x$ d. r r} * T8 n' u6 n2 y, f* N6 G) T+ Kint SearchOut(int *temp,int in)//出基变量 : x, S+ Z; \: N+ Z{ : ~" a/ q# p9 G. o int i; & ]7 A1 P7 p/ w: j float min=10000;! b- c. v; w8 ?* ?9 Z+ J7 b2 q for(i=0;i<n;i++)7 A% k% g9 D2 z if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)2 E# [5 b( ?: j &&min>matrix/matrix[in])* ]$ x2 E5 M# w/ ]4 K, _2 j {) ~& G6 X+ |$ z7 ^, g; @ min=matrix/matrix[in]; % ~$ \" Z# j, P8 z *temp=i;1 G9 |* _2 G2 A } , p4 }0 Q6 B% F/ t for(i=0;i<s;i++) 9 H6 v1 g! I9 t! W( b! l j if(a=1&&matrix[*temp]==1)2 k- R0 x/ @% n! D5 w- \1 } return i; ! }6 q' G& F2 K% s} " |& _. q5 D, \4 W6 s/////////////////////////////////- J( v, W: C- X } void Mto(int in,int temp) ! U* }; i4 p! R3 V{ 5 J2 j0 f8 u" O int i; * R/ r3 D1 Y; {+ ~& z for(i=0;i<=s;i++), Q% Y% l) v: Q" I, u- c! m if(i!=in)6 c9 c$ ~, r0 [/ y' q# T matrix[temp]=matrix[temp]/matrix[temp][in];7 d4 F% N- }% h4 n* j" W' S3 L matrix[temp][in]=1;$ q' q8 S+ H0 |" q! h5 {$ D* M, T" N } & f6 B/ b# A' }1 x7 N///////////////////////////// + t: {8 q3 p2 k$ f$ V4 E# ~void Be(int temp,int in)//初等变换6 S5 t- x, B3 f" x ] { . V6 G, F4 p( o$ Z# O int i,j;" G/ _+ G, |: N S& C float c;( Z5 ]5 R! w, E+ ^/ k for(i=0;i<=n;i++) ! _# V. [" t$ f2 M { 7 ?$ _# B! g8 D; b c=matrix[in]/matrix[temp][in];4 Q; o3 z) \3 J" _9 Q5 g if(i!=temp) # A1 k! Q3 W( W6 r2 d2 ?& g; L for(j=0;j<=s;j++)9 ?1 k; |- K1 C! ]9 y1 X9 ~ matrix[j]=matrix[j]-matrix[temp][j]*c; 2 X" G9 I3 }+ G0 E, b; [+ x0 U0 X/ f } : p( f: j9 k4 j! m: U) Z}8 z% p- a8 ?$ q //////////////////////////: }. k% b, E2 m1 | void Achange(int in,int out)//出基入基转换4 T$ o. [' L2 K3 E- M9 s; \ {" |. D" O% h" ` int temp=a[in]; 7 w% l& x0 V/ k" Z a[in]=a[out];# \6 d3 W) G1 I9 @4 ?. \! | a[out]=temp; % B0 p) z( Y/ S9 h6 @! v% G% K& x! G} " x, s6 G2 Z+ G: e8 b2 d# C1 V////////////////////////6 _2 u! w# d- z9 |3 \8 x) v | void Print()" V& M5 X) o2 n: k9 z6 v { 3 O9 Q) u; ?% ^ Z. T# W; v0 w int i,j,k,temp=0; " f; e7 t2 {, o1 P' O( H2 I { J7 I for(i=0;i<n;i++) % B: R6 r P& V { 0 @* Q0 ]6 f9 I4 S0 n4 \* S, I for(k=temp;k<s;k++)9 b3 p0 Y8 K! e if(a[k]==1)6 Y' \4 a0 C" _) b9 Q { 5 z& [4 b. y% C { cout<<k;* ]' J& ~' W& p5 R1 K5 e temp=k+1;! [7 ]0 X/ f! E% r; S+ H2 U& ? k=s;! A1 E( T# J# [& P } 9 Y+ M4 g! y) j5 A; z6 f for(j=0;j<=s;j++) : ^9 z% ^" K8 j+ H4 @ F1 _: E+ I3 O, C cout<<matrix[j];2 l- N3 K0 j3 Q& H% l+ {8 P' e cout<<"\n";; k3 c# y' ]1 \% C$ N2 O } - a% K, B, D2 W cout<<"Rj";0 [( j5 W) _1 L" h" t for(j=0;j<=s;j++) 9 }( A+ A2 u/ A- I3 a5 R cout<<matrix[n][j];, F2 `* p5 d3 O. N% A- x( m N+ \$ e cout<<"\n"; ( F& B) ?3 M3 A9 z6 o; G4 j} # |, ?: \5 _8 ^3 Q////////////////////////" J* A( \. d. q. Z5 V2 s void InitPrint()$ t4 Z5 _/ U& I/ M0 `+ \7 o% W { ?- O V: H: v! w! l8 V* ? int i;& I. r4 }7 u: A, x- W2 i, T* H# K: | cout<<"X"; 8 a- B O/ l. E! i for(i=0;i<s;i++) / f/ B& G5 F! c5 a* g: ]* B% [ cout<<i; / R1 N1 J$ k( F( e+ I" ` cout<<"b\n";$ u1 h, P [" S, D cout<<" ";8 W u; S8 ~% [3 q cout<<"\n"; 8 e# x+ }. q4 Q3 T6 R% u% D6 i}% o+ X. N% @- o7 V5 @* r# O ////////////////// . }# M' E5 j8 M7 j% Svoid Result() A; l' ?- i2 R {, q; q3 F7 k6 {0 C int i; " b6 j0 c0 C( ` cout<<"(";; C+ [% p S/ q6 F7 E! R. H+ Z+ U for(i=0;i<s;i++)8 R/ n/ _ Z( q! w4 X cout<<x; 5 y9 a. e5 E/ b' a cout<<")";" y& C; _. `3 G/ R- F: ^ if(type==1)3 S! S5 Z% t- D- U! `5 ^ cout<<"Zmax="<<matrix[n]; + j0 \5 T9 j# k else cout<<"Zmin="<<matrix[n];8 ^+ h Y4 }5 I. U } $ k. x, a0 r! p1 r% h d4 d6 W////////////////////// . J. z$ u6 `5 |# {void PrintResult() / b% Y$ Z; [% E- W& j{ & H1 H: Z: ^4 W* Q8 t& ~8 { if(type==0) $ z% l( U. m. X( E7 X, o( N1 Z cout<<"the Minimal:"<<matrix[n];8 [( }3 c& z& P9 ~2 W5 G5 G- T else cout<<"theMaximum:"<<matrix[n]; , M O0 Q( f# Q, a} ( G2 X) `4 i" Y' g& b//////////////////////////////// ) ]/ e& j" s- Q7 \1 }2 l2 O5 k' k2 T* evoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并. }, K- m; z( [- ^. y: N { 3 V) d4 U% a1 H3 V. ]& f7 u int i,j; ( h0 G d% c: x5 k; o/ } for(i=0;i<n;i++) 2 ^. v- j& R: B { t2 x# Y8 J0 T for(j=m;j<m+indexe;j++) * ]" G/ h I# L* l5 [3 @8 o if(nget[j-m]!=-1)matrix[j]=0; 3 Y9 V; O- K, r; o1 b( B else matrix[j]=-1; ) ]7 x+ H- a4 s for(j=m+indexe;j<m+indexe+indexl;j++) / J# y, B/ Q5 {! b w+ e if(nlet[j-m-indexe]!=1)matrix[j]=0;$ p# a5 N+ k Y1 X0 }2 X else matrix[j]=1;0 A. B9 K) L9 k7 g for(j=m+indexe+indexl;j<s;j++)2 [+ S% D- t5 Q3 T* d% g. G$ N5 K9 F if(net[j-m-indexe-indexl]!=1)matrix[j]=0; ~; w! c; X3 |" r" I8 D! v& c1 \ else matrix[j]=1;" f8 _; _' _8 R7 C+ r2 n/ M } . y) _$ \1 e4 K for(i=m;i<m+indexe+indexl;i++) - t* D3 Z& |6 A" ?' ` matrix[n]=0;& E9 ~# S( e- p for(i=m+indexe+indexl;i<s;i++) & H1 w9 i, E5 w4 l! i+ ?% b& W matrix[n]=100; 7 u. J1 W( q+ Q4 N9 `1 D3 t matrix[n]~~=0;' B# P6 g% n; h! k. K* z. A8 X }~~
0 p' ]6 }4 Z+ h# G% A+ c$ W7 w
/////////////////////////// " l$ M- W* \9 }- N: S( T) p+ {# o1 Nvoid ProcessA()//初始a[]& F1 I l" n1 A4 D* x* D { . c. q1 ^! k& Y0 G. _0 { int i; * X- E. S2 h Z' u$ t. B& r for(i=0;i<m+indexe;i++) + H6 v* \: |2 L4 O a=0; + u$ j4 p5 i" F for(i=m+indexe;i<s;i++)4 M8 k" [7 y& `* h2 | a=1;1 J& P6 b9 l6 g9 B# E# w s: m$ U }
5 F! q* n/ q( `3 J4 H
//////////////////////////////// ) C' e, J8 H4 L: i. x# N: {void Input(float b[],int code[])1 X+ L5 I- S1 h& O {$ I! A3 j' r% R+ \$ k/ D2 | int i=0;int j=0;9 \: N" K5 Z H6 ]: E* R cout<<"The equator variable and Restrictor\n"; % u* J! T+ M( A; V cin>>m>>n;' ~6 r8 R' d* O, U' U' ^( r for(i=0;i<n;i++)9 F! D; W. O. {4 a f { , Y% \2 U4 y$ F: C t/ n cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";, P) d9 ^; a7 B6 a* R- l( G8 l* V cin>>b>>code;! Z5 {& p X1 M cout<<"The 系数 \n"; 9 e B+ l4 P7 {6 b1 Z7 V/ ^7 E9 r for(i=0;j<m;j++) v; C* ]/ W t' e cin>>matrix[j];6 S, g: I$ R0 P. h4 w7 O0 _* I } ( _" q7 q7 i9 ]4 e% j cout<<"the type 0:Min 1:max\n"; - O! l+ Q1 I7 i3 z! f/ K% i1 O2 B do{ ; V5 D! ^, c& ~# J b& q$ m/ O cin>>type; / e( z1 D- U' P; S if(type!=0&&type!=1); k! C+ }. m# m# X cout<<"error,ReInput!\n"; 1 Y' C; R4 t' B) F7 |5 `- b' c }while(type!=0&&type!=1);8 g( r) `4 R/ Z1 i, q l' S- Q9 B cout<<"the Z\n"; 0 W/ e5 S' m( b: N3 W for(i=0;i<m;i++)1 m2 r& R; n6 A1 c, {) x" l cin>>matrix[n];: O* k4 ^- ]* X# d+ A9 s if(type==1) 1 r$ ~) t' U* S; u( J/ [+ |& ` for(i=0;i<m;i++)& b) }) L$ H- l- n9 t: z matrix[n]=-matrix[n]; 7 p3 i) k9 i2 E}
9 s, W( D& ~' B. p/ H% v
, {. l0 ^. H! { ////////////////// 2 l8 A) a. N. [" c6 k, F( O void Xartificial()//消去人工变量4 ^# ?- L1 n7 |$ G1 n) u, ? {3 J/ b; \3 R M9 ?4 r) t int i,j,k;7 q1 a- E, c" c6 v if(indexg!=0) ; N) N4 o* R0 i8 a {. g3 T+ s- Q8 o! h) w for(i=m+indexe+indexl;i<s;i++)! G3 m4 v2 i5 E: s2 { {' T' r' j. E3 G! } for(j=0;j<n;j++) & r: d+ o0 E _1 h' c. m* j if(matrix[j]==1) # J7 {9 u/ Z& F$ H$ J$ ^, b' R {$ @* I& F5 z- ]% J: q0 K for(k=0;k<=s;k++) 2 x; b! a5 f1 }9 w matrix[n][k]=matrix[n][k]-matrix[j][k]*100;7 O3 p; b6 y0 [ j=n; & B9 P0 S; h+ [: W$ e- S } 0 z$ U# g! W2 o7 a5 |) X }$ U# }# L% p- Z m3 ? } ( g* w) F1 E a9 T% K}
* m7 X% J1 m) r9 ~9 }( t
//////////////////////////////////////////////// ) g0 U) w) O, s9 M/ F$ @& `void Process(float c[][100],int row,int vol)9 `+ T7 k# J$ s: q! m, K" J { X# s/ u1 z2 A& V/ W) u int i; 3 o; P5 p( `/ b for(i=0;i<n;i++)- Q2 D6 Y2 i; B4 Q, U1 n2 g$ M! d if(i!=row)c[vol]=0;/ X1 ]7 W; d6 d4 \5 H } 0 C: C. B$ A6 z6 U////////////////////// J" f$ a) C3 c8 S* `7 u3 c$ h void Start(float b[],int code[]) ; A& t+ R; j2 |0 q/ `{ ; Q: o% @; [, o3 e int i;. n; d$ ~, B" C4 R; A float nget[100][100],nlet[100][100],net[100][100];* z- U: d; W5 U' l2 M j indexe=indexl=indexg=0;# A9 T1 n: ?! O; _! T4 R0 u for(i=0;i<n;i++)- |% C) E2 p$ k; H# _2 B7 A; J$ e { ' O6 l$ V+ O& H; @0 L) y$ k if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} . H$ b5 k+ P) [7 q4 y* l0 }2 b if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}% @* X) ^1 r0 I0 d4 p# @" I if(code==2){ / `/ k0 P2 [ S3 t9 V5 J net[indexg++]=1;- S+ ` g, a! m* m2 T nget[indexe++]=-1; & Z" ]) I8 w! k( Z' d5 j: d! K Process(net,i,indexg-1)rocess(nlet,i,indexe-1); ( c" k( m3 n; ?/ ]# ?: H }* c1 q2 ?, V4 }! M, F }3 F+ R; g; D/ w1 V8 ~ B s=indexe+indexl+indexg+m;" O# c5 g$ b7 ?0 M' Y7 u& Y U$ Q Merge(nget,nlet,net,b);$ j1 H8 b" E1 j! e ProcessA(); # G/ J: U1 `% Y" Y, i" X! w8 z InitPrint(); 3 K, Q/ c* E' H$ x$ o$ T0 H Xartificial();; {) u& g! P- [8 ^0 T* y4 V/ t }
( o9 Y% L. x2 \/ s
void Simplix()//单纯形法5 M. o5 u6 O4 H% | { 9 R$ v$ f# J" ^) [1 |% l* k" v int in,out,temp=0;: r# v6 I/ a: @3 Z% ?" j0 p while(1) 4 m/ E; y- S7 I2 d& H {% D0 L# K' n/ J& z$ N jckxj(); % f' J- J$ S" T+ n& t o% `: X Print();, P0 Y& F5 F3 G9 c( F Result(); ! b2 @& N0 ~) V if(!rj()) in=Min();# ]: B) X& v- y+ U' R# T else{ # R' F" }6 x: ]$ Q$ x if(indexg!=0) d! W* t" }; Y8 O/ z JustArtificial();1 _9 C' M. Q7 t. {/ u6 H0 m0 K PrintResult(); # L" \8 m5 d/ q, o8 z1 ? return; ' Q6 U0 W9 d+ U9 n( o4 K } 1 n2 O# R, u3 F, C) U) b: D. } if(Check(in))1 P) L2 i$ r3 V2 ?: b6 V8 N {* p3 D* c! t+ W0 |2 ^. [' }8 e cout<<"No Delimition\n";% p& }8 E" x0 j1 Q5 y return; 0 y p) z. K$ a" y, x: z8 A; P+ i } 7 V7 T. d! ?6 _7 |" ] out=SearchOut(&temp,in);& r1 F0 T a! A: w9 A4 ^ Mto(in,temp); 4 M q! Z ?; x* [ Be(temp,in); $ j: [# O% @: x0 W% j Z Achange(in,out); ( K% u3 `5 R4 q2 b' v }4 W+ m* ^0 X4 y2 f }
, J1 d5 j- |1 ?- }; M' X; N0 h ?
void main() 9 E1 D3 V" V6 v+ Z{, k* b/ ~- X \2 [7 Q+ M% [ int code[100];//输入符号标记. g9 \# a6 D( ?$ |# J6 G2 \ float b[100];7 S0 e4 z5 E7 v7 l5 z8 _" b Input(b,code);//初始化 - p5 d. h/ k `7 d2 W Start(b,code);//标准化行 5 x7 o( Z7 S- q; @9 W! d0 Q( R Simplix(); - {5 f- B& }% c" s& w# s}6 P' n. X$ e) b7 i- l& H# U
作者: 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