单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ / o* q W$ e& s. N# m& u" P

#include<iostream.h> #include<math.h> float matrix[100][100],x[100]; int a[100]; int m,n,s,type; 8 Z& x; U3 }; O7 p( F1 k3 h/ Zint indexe,indexl,indexg; , M$ v' v& f. d {+ i///////////////////////////////// void jckxj()//基础可行解 { & P! H* o( F8 Y$ T0 Z6 U" j6 w int i,j; for(i=0;i<n;i++) for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) { $ S7 b+ V/ a* a2 _5 t5 J ? x[j]=matrix; & `' u+ [& I0 b. J) @ j=s; } 0 y$ L& n+ q$ Y" S! `% {+ n& X) G for(i=0;i<s;i++) / l6 D% f6 x1 S, g8 c! ? if(a==0)x=0; }

int rj()//基解矩阵 7 i) J0 n& u/ _9 Y4 z. a{ x. ~- I/ N. r$ j int i; 9 z. s) f# S8 m$ c8 w for(i=0;i<s;i++) if(fabs(matrix[n])>=0.000001) * B% v2 V; C( { if(matrix[n]<0)return 0; return 1; } 7 E4 O7 ~7 x ^6 Jint Min()//求最小的 1 W+ F- L; v) ^( u# ?* X) Y{ $ x1 l2 n* f p1 W( D2 S int i,temp=0; 2 n3 f8 C. x! l4 M. f float min=matrix[n][0]; $ Y, v, R* C/ o for(i=1;i<s;i++) + p; N7 ? B1 ]# q if(min>matrix[n]) % W2 J# W( v; Z K { $ C2 ]3 u; u* \9 x5 i. L min=matrix[n]; temp=i; } return temp; } & o, C% ^& x E9 \% r1 n7 U5 k///////////////////////////////// ! {8 A) \5 w8 `# q+ Zvoid JustArtificial()//人工变量 { # U& _9 t, p/ u4 w; R' [; T) O2 t int i; for(i=m+indexe+indexl;i<s;i++) 7 d! J x, t4 ?+ C2 J' q* T if(fabs(x)>=0.000001) / Q+ t5 D9 b+ ]( t! E! s { ( s b9 j- U& K% y) x cout<<"NO Answer\n"; return; : D, Y. o( b1 r6 {" I; c J } * c2 ]1 n2 h6 f5 ?) A* S a" n/ n} ( b# ~7 K$ M( h* [9 k2 ^///////////////////// 9 e# J/ I/ e/ ]0 eint Check(int in)//检验 ' _" R U/ g0 n* h, O6 K9 |# I/ y{ int i; float maxl=-1; for(i=0;i<n;i++) 9 W$ c5 W* w* R5 Z0 Z/ q! m0 C; a! B if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) 5 ]3 n; c; E+ J+ Z% h maxl=matrix/matrix[in]; if(maxl<0) + U( \4 S* c# Y# j. I& F- y: B return 1; return 0; } int SearchOut(int *temp,int in)//出基变量 ; y+ Q* `: C$ d# E* O8 `2 F) h5 K{ ! Z+ f4 W* ~" |" m int i; float min=10000; 1 w6 b+ ~6 O) A/ ~* ` for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) - M8 r" h5 \/ V9 L/ ] &&min>matrix/matrix[in]) { min=matrix/matrix[in]; *temp=i; * H# C) s" W. y* j: l; ]. s } for(i=0;i<s;i++) / e+ D/ A2 b3 L" o' s2 V0 C if(a=1&&matrix[*temp]==1) " y% @0 @6 g( N5 C/ j9 X Z return i; } ///////////////////////////////// void Mto(int in,int temp) { 8 J' X2 k8 C ]' P int i; for(i=0;i<=s;i++) if(i!=in) 2 h; J1 x2 p. g( W. L8 J matrix[temp]=matrix[temp]/matrix[temp][in]; a+ b- w, {* ? ]6 k matrix[temp][in]=1; } 9 [4 P" }# @2 p! w, D, r& p- h' N+ K///////////////////////////// void Be(int temp,int in)//初等变换 { int i,j; float c; for(i=0;i<=n;i++) * y1 _& T5 q6 W7 Q: T6 c8 q$ t { c=matrix[in]/matrix[temp][in]; 9 m9 b# C2 | {4 m) e- f if(i!=temp) for(j=0;j<=s;j++) matrix[j]=matrix[j]-matrix[temp][j]*c; J) j+ p) j( J; z& x% I } 7 L6 i3 K6 ^+ v% Q' H1 E: {1 j} # I3 I% N: j H0 j////////////////////////// void Achange(int in,int out)//出基入基转换 { : [3 ^3 ^% u+ y# w. t int temp=a[in]; a[in]=a[out]; a[out]=temp; 7 D8 i* X; U. j/ R r q} //////////////////////// void Print() { int i,j,k,temp=0; for(i=0;i<n;i++) { for(k=temp;k<s;k++) if(a[k]==1) 7 |0 K# A* T: H" f { cout<<k; 2 S- G9 h: r! L9 L& Q temp=k+1; / |4 P! [5 E4 V6 T, F k=s; } ! b' n. `1 Z; g+ c7 v for(j=0;j<=s;j++) cout<<matrix[j]; . G0 ~0 j: N2 z cout<<"\n"; * o) k, G( e- F" M$ l d f } cout<<"Rj"; for(j=0;j<=s;j++) 4 Z8 E/ @9 g) l cout<<matrix[n][j]; ) i7 c5 W. v$ |" w- _* U cout<<"\n"; } //////////////////////// + J8 T7 _" _% u# w/ }void InitPrint() ) r; ~4 Y( I) ^. ]( m{ + i, [0 e; z) } int i; cout<<"X"; ; N" X5 \7 t; {, J2 u% P for(i=0;i<s;i++) % @% H" l" l7 ~4 z- d cout<<i; 7 T; d8 x4 Q: J5 U6 e4 b3 k! Z) B9 A( h; } cout<<"b\n"; % U i! o5 U# N4 Q( ~/ s/ J+ l cout<<" "; cout<<"\n"; } 6 a. Z- t) e" e( [" f( | x6 c////////////////// void Result() : E& l. T+ b8 Q; ?" Q: |) S2 j{ int i; cout<<"("; 0 |; `! ~. U! t. `0 D3 O9 W: o: D for(i=0;i<s;i++) cout<<x; cout<<")"; if(type==1) % j2 r& G& d- |* H1 B cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; 5 j7 |8 J2 B# G; O2 i} : V$ r B, ~' H9 x6 n$ w////////////////////// void PrintResult() { if(type==0) cout<<"the Minimal:"<<matrix[n]; 4 S* a2 Q3 H/ t3 Z9 d else cout<<"theMaximum:"<<matrix[n]; 0 |& [8 m- W. a l+ G7 Z} ( u. U' [) x7 \1 p; H//////////////////////////////// 7 w- a/ y+ } r7 a; lvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 { int i,j; for(i=0;i<n;i++) { for(j=m;j<m+indexe;j++) 6 e7 P; U( R: E- D+ m if(nget[j-m]!=-1)matrix[j]=0; else matrix[j]=-1; 3 F% ]1 h$ d) W$ ^. H5 \ for(j=m+indexe;j<m+indexe+indexl;j++) & d" S7 ?6 p# | if(nlet[j-m-indexe]!=1)matrix[j]=0; ! ~% b6 v: f3 d& r; ^% P 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; [% X! }7 _5 C2 K } 3 m/ K) \& S# z, i for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; . c2 l' `% B" P5 A+ a. w for(i=m+indexe+indexl;i<s;i++) matrix[n]=100; 3 [& v: E; k/ X5 i5 b2 a matrix[n]=0; : \2 R- |0 S o% q" |6 o5 V( [}

/////////////////////////// : b4 M4 O) J; I0 ?4 h! T: _8 Jvoid ProcessA()//初始a[] { int i; for(i=0;i<m+indexe;i++) 6 C/ o9 L) L- x& I. [. L a=0; for(i=m+indexe;i<s;i++) * Z# D: D1 p+ l# @ ^% _ a=1; }

- Z, A7 I/ o% s$ w# {% l M& K

//////////////////////////////// % I0 S* Z, O* r3 B8 fvoid Input(float b[],int code[]) / F- C+ }5 r0 K7 {1 ~) {{ 7 w$ y6 O4 J0 S% P9 A int i=0;int j=0; 8 y' H/ T, O* M( C8 q cout<<"The equator variable and Restrictor\n"; cin>>m>>n; for(i=0;i<n;i++) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; ( E+ _" z+ A% i0 x$ _ cout<<"The 系数 \n"; for(i=0;j<m;j++) 7 P C( x6 F( w! R/ F cin>>matrix[j]; " S# q8 _5 M, S, F! | } cout<<"the type 0:Min 1:max\n"; do{ 3 y- c( M4 N1 A cin>>type; & D. ?: ^. G! B: J* | if(type!=0&&type!=1) : k, ~) K' I% k& `: K& l cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n"; for(i=0;i<m;i++) / r- F# X/ v5 L" S/ Q cin>>matrix[n]; 7 e3 ?; C% J& t9 ^" k4 \ if(type==1) - ^; G$ Z5 `- T( a" W, Z, w6 y6 ^0 Y2 F for(i=0;i<m;i++) matrix[n]=-matrix[n]; }

////////////////// + \$ K1 B6 W( J) [4 ~& g$ w' o, _1 avoid Xartificial()//消去人工变量 { int i,j,k; + M5 ^2 z) C4 Y, F1 S( F. s if(indexg!=0) 7 a. Z& j% F6 D. b; O- ]' h { for(i=m+indexe+indexl;i<s;i++) { for(j=0;j<n;j++) ! z8 s& U2 J2 _/ ~3 x" h3 {" Z' e if(matrix[j]==1) { for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; } : q k" ~* K" I P1 u } 8 F2 P) ~& I5 p4 e+ c } $ p3 S; J2 T2 G" ~: C2 r}

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) 9 [- H- r* ?2 k" [" e{ + f7 f: I& }+ X4 U j* H3 p int i; for(i=0;i<n;i++) if(i!=row)c[vol]=0; } % u: P X" _5 x////////////////////// - j: I5 M( U! }" ?void Start(float b[],int code[]) { % a* d$ I" Z6 b! O$ m8 r int i; : o, f) I; J6 [4 _ float nget[100][100],nlet[100][100],net[100][100]; / k! d( _% N' o6 i, D6 o indexe=indexl=indexg=0; % Z4 V* Q, x- I for(i=0;i<n;i++) 1 J9 \7 m+ P2 e7 B, K { if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} . U C) \8 `% x8 ?6 z8 b if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} ! u9 `: }8 d6 u, l6 w2 ]* S, d) u- R if(code==2){ e0 |: s U1 |5 g net[indexg++]=1; 3 L; z, s1 S0 {- z a, l6 M3 Q nget[indexe++]=-1; 8 I8 G/ a! m. \& t4 Y9 n* Z Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 2 m/ H, Q( u9 L2 s$ D+ M1 Z } } * B5 Q1 Q& u0 U) n s=indexe+indexl+indexg+m; : _ i* b, R v+ I/ {7 `% ~ Merge(nget,nlet,net,b); ' t8 M) v/ }- P( G( ? ProcessA(); InitPrint(); Xartificial(); }

8 v1 i6 v8 o0 i

void Simplix()//单纯形法 & n* B) Q9 n4 M E{ int in,out,temp=0; 7 Z, L' t/ m2 ^7 O, p" n& O while(1) { jckxj(); + b: E. u4 \' N8 V. G4 V Print(); - v- k+ n' @6 Q) G- G7 d9 y Result(); if(!rj()) in=Min(); else{ if(indexg!=0) JustArtificial(); 0 L7 j/ [8 a4 I PrintResult(); return; ' x3 r3 p4 n1 a# U/ y: Y } 5 } S' [5 e. ~0 @ if(Check(in)) 2 ~8 x6 I9 @$ } { 7 X# [) s8 P* k8 ], R$ C cout<<"No Delimition\n"; return; } ; I$ D& e* l( r, z: I C out=SearchOut(&temp,in); 7 G" V( V/ B, F3 D% ` Mto(in,temp); ' e9 L0 ^& e+ ^' w4 a Be(temp,in); Achange(in,out); - y K2 `- Q! z; I! \/ M" }# ` } }

) P t9 H+ j! q; D7 L! ^( k

void main() o0 c* m* i4 @1 X{ int code[100];//输入符号标记 9 G3 z- g+ g4 g+ K6 y9 J2 G float b[100]; Input(b,code);//初始化 Start(b,code);//标准化行 Simplix(); $ A8 i7 K; [& }) j; f p} * F: Q+ y" |3 G: `) \

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

资源分配问题可以用这个程序吗？

monkeytail

哇，楼主强人！

monkeytail

单纯行算法是指数算法啊！

bnulj

这么长！看不懂啊。

mengfanqi

so well!