单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ ' r0 I2 g4 W/ h: Z7 y

#include<iostream.h> ( T% c4 x6 x" k+ r' o. p#include<math.h> float matrix[100][100],x[100]; $ z& q4 E- M& {/ N2 \" n. A! Iint a[100]; int m,n,s,type; int indexe,indexl,indexg; ///////////////////////////////// void jckxj()//基础可行解 { int i,j; 7 U' z1 {! n- W2 e) [, K, ~; i for(i=0;i<n;i++) + r6 F2 M8 b8 `! ~: O6 }, }7 n1 m for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) # X: Y/ S, o1 x { 6 {8 r; e- E6 p% d& M | x[j]=matrix; / g' G N) d2 T( u. |4 _& ~. S j=s; . D% l# R/ Q4 { } for(i=0;i<s;i++) 3 j2 [( ]; Q6 O5 n, `0 V. D if(a==0)x=0; }

2 h( ~: L3 V$ x1 F. f

int rj()//基解矩阵 { int i; for(i=0;i<s;i++) if(fabs(matrix[n])>=0.000001) 3 I- M% D( ]! I if(matrix[n]<0)return 0; % M o2 G1 l2 y; b return 1; } int Min()//求最小的 { int i,temp=0; 8 g! G; A7 C5 m3 U& c+ {$ [ float min=matrix[n][0]; 0 ?) G: @2 I+ e for(i=1;i<s;i++) I$ @ F, q* G4 l1 q9 D4 [" q* [- L if(min>matrix[n]) - f8 k8 p# c. `! F3 @ ]- L- q { min=matrix[n]; temp=i; } return temp; } 0 W; ^1 U5 J0 y5 z$ v3 {& @///////////////////////////////// 6 Q/ u: A5 _7 K9 V3 _4 Ovoid JustArtificial()//人工变量 { & j: p& g! M0 v; b int i; + z- Q4 r2 g. W4 K }9 y# s for(i=m+indexe+indexl;i<s;i++) # T e6 k( Y8 i; Z8 Y' N if(fabs(x)>=0.000001) . b# ?4 d% S8 L; c7 x { - `. \1 D8 d f. j; J+ s. d, _ cout<<"NO Answer\n"; return; 3 B. T0 a* N& f } } 1 e3 d' f% [7 p3 h0 b///////////////////// 0 A. u4 p3 z0 b% g" D. nint Check(int in)//检验 { ( i# N1 E) b4 E( t# u% ?7 P% X4 v H9 L0 i int i; float maxl=-1; & p, O4 s5 p* @* m2 x- r for(i=0;i<n;i++) if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) 2 B. P4 |2 }, `' @: F# N! S% j& x maxl=matrix/matrix[in]; if(maxl<0) # L5 k$ Q* N" ^& L/ W return 1; 8 p0 ^: f U# l: a5 e& D. G return 0; } int SearchOut(int *temp,int in)//出基变量 { ; K0 J+ i ^6 f" Y int i; float min=10000; 2 z, L8 v- h, a for(i=0;i<n;i++) ! J' n! x8 X2 C7 L2 m3 H$ k8 A if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) &&min>matrix/matrix[in]) { min=matrix/matrix[in]; ' S" b2 ^4 o& l& }5 g8 w5 m *temp=i; } + a% Y9 n5 I/ m) s0 h# r1 @ for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) return i; } 1 {; e3 u( P: n- C: Y0 Q& v///////////////////////////////// 2 {0 i+ @' {! N) P6 D9 [void Mto(int in,int temp) { % p( r7 X2 Y+ q- i/ D: T3 I int i; 2 i1 `0 Y$ Y' H6 E- n for(i=0;i<=s;i++) if(i!=in) 5 U1 t& n4 M( [6 P; \ matrix[temp]=matrix[temp]/matrix[temp][in]; : P1 _3 ?9 j' C8 v matrix[temp][in]=1; } ///////////////////////////// void Be(int temp,int in)//初等变换 8 b" Q: S' R4 n2 ~5 m( t{ # C7 G' Y2 z- W% ]! b" w& M int i,j; 5 p; B( u7 h( R* W6 Q% z0 `, e float c; " i8 u9 b" g9 M+ u; u4 J for(i=0;i<=n;i++) { 9 o# }0 i7 d( |" g [7 d c=matrix[in]/matrix[temp][in]; , R* X' e' U; L0 @) s8 D6 x if(i!=temp) * b9 G- ]: f5 ]$ g0 q& l! Z' N- ]3 \ for(j=0;j<=s;j++) 6 T/ A6 J& [4 A/ }% A matrix[j]=matrix[j]-matrix[temp][j]*c; 7 q, L2 i0 Z5 H- y9 F6 V5 A! a0 _; x } 0 F+ e& B+ w. m+ V/ d} ////////////////////////// % T6 l0 N5 ^* }void Achange(int in,int out)//出基入基转换 { int temp=a[in]; a[in]=a[out]; a[out]=temp; } //////////////////////// void Print() 9 W7 o# g4 {0 J1 {+ |4 J3 \{ 0 l+ L! U* l/ U# S& L int i,j,k,temp=0; for(i=0;i<n;i++) / t- L- ]' ~$ \3 ~0 C { for(k=temp;k<s;k++) 5 S) b! ]) A3 g: x+ E: f, S if(a[k]==1) { cout<<k; temp=k+1; : k; I, q( t' S0 z9 i j! x+ Y k=s; } for(j=0;j<=s;j++) cout<<matrix[j]; cout<<"\n"; + ~3 w$ @8 O. v0 v/ H } % p4 A: u. F( r j" F' d8 b cout<<"Rj"; . H: N, M3 ]) w1 | for(j=0;j<=s;j++) : g" N0 Q$ m# g1 J cout<<matrix[n][j]; 7 K: m0 m% F5 T% L2 B cout<<"\n"; } , G: I! D M4 ?- C0 V g//////////////////////// void InitPrint() $ y, U$ x. s' y6 N( U{ 8 `6 u" m5 J! }8 H4 B6 b, P int i; cout<<"X"; for(i=0;i<s;i++) % V# R( F, R8 o+ M2 \ cout<<i; cout<<"b\n"; cout<<" "; 7 o. I& J2 w3 @* U' x! B/ X h2 o6 S cout<<"\n"; } ////////////////// ) i5 l0 N9 U1 N5 R# f( \3 Zvoid Result() ' O" t" V9 ~. X; J, s* Q{ - n7 p7 A( j5 O! ` int i; cout<<"("; ) |) `$ z0 K# G4 U, h' @) m for(i=0;i<s;i++) 6 u. j) y. `; S8 z, c cout<<x; cout<<")"; 3 O8 G3 H( V( \6 W/ y/ A* V+ N if(type==1) cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; ! e" L; j' z& w+ c# Q} ////////////////////// % U5 J4 [, b; nvoid PrintResult() 4 O/ n. p% ~4 u- r* ?, v! s) m{ $ }+ X6 n2 V1 g% t if(type==0) 1 q9 ]( i8 t+ E$ @* E cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; } //////////////////////////////// * i1 ?% `$ | b* J! ovoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 . P6 j) B5 M, U# T{ 8 r/ ?% k* W D' J; I int i,j; for(i=0;i<n;i++) & |+ J: a9 L. O. | { 8 e I) r% F8 Y$ g for(j=m;j<m+indexe;j++) 5 I5 O0 ]# u' ^4 a if(nget[j-m]!=-1)matrix[j]=0; $ Y6 D: }. T; d else matrix[j]=-1; for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; ( w. k6 F" v2 H) E% v8 t else matrix[j]=1; for(j=m+indexe+indexl;j<s;j++) - p( d4 H5 o& X5 O( e if(net[j-m-indexe-indexl]!=1)matrix[j]=0; else matrix[j]=1; . y- Y5 _, y! o9 x1 w } for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) - T' D! _$ m! [ matrix[n]=100; 0 b0 P6 o' ^8 K( e matrix[n]=0; }

9 z- n. H! b$ B" F

/////////////////////////// & Z9 x3 v2 U- b/ c! e2 V1 ^void ProcessA()//初始a[] { int i; for(i=0;i<m+indexe;i++) a=0; e" @- L t1 W4 |# h1 T$ u for(i=m+indexe;i<s;i++) ; b: v. g; G' k& w, l a=1; # O( F8 Z8 ~! c" l7 X7 T8 ~; L J5 J}

% D; v' V3 a) ]

//////////////////////////////// void Input(float b[],int code[]) * K, u5 Z" v4 Y# ^- P/ ]3 k{ int i=0;int j=0; 4 o A# X( j3 ?) w, L cout<<"The equator variable and Restrictor\n"; 7 }, j5 T1 r, P. p cin>>m>>n; for(i=0;i<n;i++) ! w, g) X5 X$ f- o" o6 o! E { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; ( o: J _8 L$ s/ T* z cout<<"The 系数 \n"; for(i=0;j<m;j++) $ Y3 A/ m9 n8 _# n h4 |* |$ l$ ?4 ? cin>>matrix[j]; ( g; z6 z; ^& ^5 b+ s) H. T% E } 3 o6 J- q8 v4 ~3 S1 g$ S# C) h cout<<"the type 0:Min 1:max\n"; ( m! }3 z' j l- { N5 ~4 f do{ cin>>type; if(type!=0&&type!=1) 4 x W9 A2 j& Y6 k0 R* I cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); . r4 `8 i# s# ~/ x cout<<"the Z\n"; for(i=0;i<m;i++) " Z7 I9 v5 h y+ M. y cin>>matrix[n]; if(type==1) ) R9 M: s4 Q$ ~/ m0 c% v for(i=0;i<m;i++) ' ?' m6 ~* n, x* N! t matrix[n]=-matrix[n]; 7 ?* N7 [8 ]; T6 R}

! z7 k+ C( T7 }- a1 J////////////////// void Xartificial()//消去人工变量 2 _/ W5 _. Q: E+ |" i0 O% P{ 6 X/ Q: ]% E, u' C6 X int i,j,k; 9 b; t! H& z& v/ F9 o W2 O! S if(indexg!=0) ; E2 u" U. K# w2 Z7 ] { , R* `4 r4 C* V; O# }3 b- f for(i=m+indexe+indexl;i<s;i++) { + W8 X; C. h+ ^* `! q for(j=0;j<n;j++) if(matrix[j]==1) { # M: ?) z" p- [" k0 |4 a5 K for(k=0;k<=s;k++) 3 L4 J" O6 p$ ]) T! u! o% n1 v1 ^ 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++) ( b& W" D0 y# \ {7 V4 J if(i!=row)c[vol]=0; $ ?6 b, \9 x* P5 N, ?/ K4 b* _} / C8 }: c- c8 r9 p9 G/ Q6 ]////////////////////// " a8 Z6 Y0 a" O4 T: f7 ^void Start(float b[],int code[]) { int i; float nget[100][100],nlet[100][100],net[100][100]; 7 T% g6 }7 U" I) p3 z% Y: H0 i' j indexe=indexl=indexg=0; , Y% k3 V4 Z9 V2 Y; z3 L for(i=0;i<n;i++) { ; A5 E: B# k2 r7 _% l: R& J' u/ [ if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} if(code==2){ net[indexg++]=1; 5 j% s. Z) t1 q. x1 q nget[indexe++]=-1; Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 1 ]& ~/ D6 r; E } ( f9 }& F5 G+ M: k' P } * ^8 w; i0 ]" \0 q# j s=indexe+indexl+indexg+m; , X6 ]$ _5 L( c/ C' k) _ Merge(nget,nlet,net,b); . r; ]- l3 m) u6 p9 D ProcessA(); InitPrint(); Xartificial(); }

% q$ w7 d) Y: ]

void Simplix()//单纯形法 9 J. F2 j/ I% o/ l) K8 k( X{ 4 J1 {2 M2 v* G int in,out,temp=0; 4 u4 d( i9 i- I$ ?. q/ ^$ I while(1) 4 m# h9 P. J9 B { jckxj(); Print(); $ V" f. s! l# w Result(); : Y0 s3 l) O1 B0 p l if(!rj()) in=Min(); * S9 }; D# h# g3 `9 r( d else{ % Q5 Y; C3 z& l! L) ^% f. F* c) S if(indexg!=0) $ Q3 c1 t% X; E# Q% N& y; P JustArtificial(); PrintResult(); return; 7 ?% u( P; k: | } % Y! D6 F0 f: t1 Q7 w, _! _& w if(Check(in)) { 6 m) M- |( d; n$ a, E) x! c cout<<"No Delimition\n"; 4 [& e. p2 V$ d3 f* r G, f return; } out=SearchOut(&temp,in); 3 M+ v' d. W$ \4 b% m$ Q Mto(in,temp); ; y. m4 P* {2 u$ ` Be(temp,in); Achange(in,out); ) g, _, T7 v1 C% r/ q0 z+ Q } * Z. Y+ d. A" C% {" |$ q( e}

void main() { int code[100];//输入符号标记 2 W4 p G+ c8 ^ float b[100]; Input(b,code);//初始化 Start(b,code);//标准化行 , y: S8 r" d/ N: Z: @4 W Simplix(); ) G0 W7 |9 H9 A6 j/ Q4 k* T. z} - `0 Y% h2 v/ A' {# z9 x

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!