单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！ / g' C! B! B6 B4 F

#include<iostream.h> + X- N, i/ y- q* r3 T: y#include<math.h> float matrix[100][100],x[100]; 6 X" K. h5 \6 p3 _3 iint a[100]; int m,n,s,type; 1 K3 k; H1 D- i- u3 N; `2 oint indexe,indexl,indexg; 8 c' X# [) ^7 K% N0 I/ \ X///////////////////////////////// ; X7 p; B% Q5 T* w! H5 e$ Tvoid jckxj()//基础可行解 { + T( q7 ^* t/ n O1 ^1 | int i,j; 2 b6 ]0 D1 |+ e' y; R v1 W for(i=0;i<n;i++) ( d5 B- ~6 g3 s6 a$ l for(j=0;j<s;j++) if(matrix[j]==1&&a[j]==1) { " [: E5 B' @- E8 A! _/ ~3 x/ k x[j]=matrix; j=s; } ' J6 m8 }# w2 v for(i=0;i<s;i++) 3 G/ v6 K) M7 W7 h, U1 w% q: W if(a==0)x=0; 3 |3 u. N6 {& `. X, ?9 ^$ d% D6 n}

) q/ ]3 x, g" y& Y3 N

int rj()//基解矩阵 . Z& Y; j2 h" H& O* d# [{ int i; for(i=0;i<s;i++) 7 c$ j; n4 M& v. c% U if(fabs(matrix[n])>=0.000001) 6 l1 n" X5 w* g- _0 E0 m: b- L' d if(matrix[n]<0)return 0; & e4 o9 }: O1 a4 i# { return 1; } r. a, u4 x i `% _# ^: [1 tint Min()//求最小的 { int i,temp=0; float min=matrix[n][0]; for(i=1;i<s;i++) ; S8 \: `5 G* k9 n( w: G if(min>matrix[n]) { " ~" k6 @; o9 s. _ min=matrix[n]; 5 O; C) b. x: j7 Y5 e temp=i; } 4 q# R7 ]1 B+ H$ B return temp; + |7 s) E) @0 B0 S} / K7 [; o7 d( F///////////////////////////////// + d: j9 L2 b/ F$ Y* \void JustArtificial()//人工变量 { 6 {* v* w+ B* V! c1 y int i; 6 R2 q y* \" z& a7 p3 M for(i=m+indexe+indexl;i<s;i++) 6 T, L; c2 B2 E# G+ } if(fabs(x)>=0.000001) : H: A1 F- `3 \, @/ F% p { cout<<"NO Answer\n"; return; ' a. [2 v, ^8 }2 T7 D# o7 K } } ///////////////////// . Q4 \* d) O- Q* l' {int Check(int in)//检验 7 b4 K! N. D# r$ g9 L0 m{ " e3 ?% N% @. t, P# U8 M! A int i; float maxl=-1; for(i=0;i<n;i++) ) U( e2 N# b) m( X if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) maxl=matrix/matrix[in]; ! j5 R5 R) F8 K* `# R$ b3 V if(maxl<0) ) G7 \* P v( H: u1 e return 1; 5 q3 n3 l8 k* J) n return 0; } / M) F5 Z( L" Z: D& nint SearchOut(int *temp,int in)//出基变量 * _' w- c- [' _) d{ int i; , d2 q- d- [3 V2 \5 q0 c float min=10000; + s7 C- G# }& x! H3 |5 e/ @, k for(i=0;i<n;i++) 3 a9 c7 q# q6 q( e* v4 p; o if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) &&min>matrix/matrix[in]) - \0 X- i9 X. a3 M" N+ O { min=matrix/matrix[in]; *temp=i; % {, R$ j: [3 i' `. ]/ O9 y } 3 r$ M: F$ p9 K7 c( D/ a for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) return i; } 0 M' H' P4 G% M6 Y+ z* o///////////////////////////////// $ L9 r, h1 g, E, i y1 @void Mto(int in,int temp) : P5 C3 U, V! I4 d# U, y{ 3 b Z* s$ R. t- |; a int i; for(i=0;i<=s;i++) , E) \# A8 I2 C+ D' p. p if(i!=in) & W) l' `& |4 L' l+ [+ w6 F: \ matrix[temp]=matrix[temp]/matrix[temp][in]; matrix[temp][in]=1; } ///////////////////////////// v) F, w% g& q5 r3 @( ]' hvoid Be(int temp,int in)//初等变换 / F: Q+ ]2 A$ @0 k1 p{ . }6 F. O+ n \" `& g* j int i,j; float c; for(i=0;i<=n;i++) { + {: _6 t. k$ P# \0 f, e c=matrix[in]/matrix[temp][in]; if(i!=temp) for(j=0;j<=s;j++) @4 E; o! R5 A# L( ^ matrix[j]=matrix[j]-matrix[temp][j]*c; . o6 f, \; V; a8 v; j( X- k: U } # y* ?7 j$ C, A! t7 l+ A8 @7 A} ; L: [, v1 n3 ^////////////////////////// ' ]# U5 T5 p/ c; g; Tvoid Achange(int in,int out)//出基入基转换 { int temp=a[in]; & H9 `1 _0 N9 S" y6 k. } a[in]=a[out]; a[out]=temp; 4 \! f! y( x5 \9 v1 t} 7 Z" L3 D5 K/ ]% \4 `' D/ N//////////////////////// void Print() 3 a Z" @$ T* J- m$ d5 N{ int i,j,k,temp=0; for(i=0;i<n;i++) ! ? c2 C) E9 h% b+ T! M8 z/ Y+ H { for(k=temp;k<s;k++) if(a[k]==1) { cout<<k; temp=k+1; k=s; : q% u' |6 F! ^+ t M } for(j=0;j<=s;j++) 3 O6 K& i- g) D' d, J% w) P) G g cout<<matrix[j]; cout<<"\n"; / l* e+ D- ^( X, T } / B9 a, A. L7 C cout<<"Rj"; for(j=0;j<=s;j++) 4 D9 H0 N" v E% P2 M4 O cout<<matrix[n][j]; - A' p" T2 |+ ~: x7 I8 \ cout<<"\n"; } : M- `8 A( U5 A! g& i//////////////////////// void InitPrint() { , @/ X) |) a- z( ~4 O) U: ~2 z int i; ; R# x2 D; L/ K% O cout<<"X"; ' U Y$ W5 P) r- O1 P: v; P4 x; e for(i=0;i<s;i++) cout<<i; cout<<"b\n"; cout<<" "; " ?+ [- X( `3 s- i3 A cout<<"\n"; } ; x% E' Z5 _0 v+ c) s- A////////////////// 9 T5 T& R% P2 P2 U3 w3 c4 qvoid Result() - u$ e5 ^7 i! D3 t0 j$ Z7 h{ ) ~5 |: G: m7 @1 ^' F" W( c8 n int i; ; L4 R# P! Q6 c: S cout<<"("; for(i=0;i<s;i++) cout<<x; cout<<")"; 8 W0 M* l& E4 t2 R6 `7 j if(type==1) cout<<"Zmax="<<matrix[n]; 5 D: t3 ^: r8 `' p2 t else cout<<"Zmin="<<matrix[n]; } ////////////////////// void PrintResult() { 8 g4 x) \( V' r7 c& l/ q1 Q if(type==0) cout<<"the Minimal:"<<matrix[n]; y- U, @" c; Q else cout<<"theMaximum:"<<matrix[n]; } //////////////////////////////// ' t! ?( L& f6 C5 q0 vvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 : f f5 d3 V, H# E{ - y* ]6 Q7 P. f8 ~ int i,j; # q" J! ]! E5 C 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; 9 F; A H3 |1 h0 T) t! | for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; else matrix[j]=1; 3 M# `; o5 z7 g; z; w" O! Z for(j=m+indexe+indexl;j<s;j++) ! ~1 B- J: ]4 S0 S) K3 ?% ?1 E* H if(net[j-m-indexe-indexl]!=1)matrix[j]=0; else matrix[j]=1; } & k1 b6 i3 ~$ t; F for(i=m;i<m+indexe+indexl;i++) o& R) s) F4 L+ P matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) 9 H0 V# z3 G- a( G/ m/ _3 k2 ^' Q matrix[n]=100; 4 D0 O, V: F, I1 \/ W0 [% O matrix[n]=0; $ ~: H2 d" j j$ i) m}

/////////////////////////// " k) ]7 T6 k* Ovoid ProcessA()//初始a[] { int i; for(i=0;i<m+indexe;i++) 9 W0 r7 c6 v6 m2 J4 T a=0; for(i=m+indexe;i<s;i++) a=1; }

3 N4 X9 k/ ^+ G* m2 Y$ Z

//////////////////////////////// void Input(float b[],int code[]) 0 W# S5 {+ t! u0 }" }{ int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; 5 x0 Y( j- R# m7 ^ cin>>m>>n; % W) Z) o/ i1 U for(i=0;i<n;i++) , o0 ^% h/ q8 R { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; ' _; P* q1 Y9 Y) Y cin>>b>>code; cout<<"The 系数 \n"; # f2 X- f' m4 L: k; N* W for(i=0;j<m;j++) cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; do{ , t+ I6 i. n# Z cin>>type; if(type!=0&&type!=1) 7 s4 V+ g& I, W" j cout<<"error,ReInput!\n"; ' Y2 v/ {: y9 W1 d J) | }while(type!=0&&type!=1); 8 D. k/ [3 S. z- B) w1 v cout<<"the Z\n"; for(i=0;i<m;i++) cin>>matrix[n]; + o2 I+ t" x! G4 S6 L; G( T' I if(type==1) for(i=0;i<m;i++) matrix[n]=-matrix[n]; 1 u- R: i q5 s}

" m+ |+ j5 D/ ?: P0 r. k

1 w- f3 Y$ r$ A0 c4 N! n& y, s////////////////// void Xartificial()//消去人工变量 ! l) l1 x. L4 i5 i1 a* N' g1 \{ int i,j,k; if(indexg!=0) { for(i=m+indexe+indexl;i<s;i++) { 7 A0 U# P8 }* d( g$ C7 ]9 K for(j=0;j<n;j++) 1 d" m% u( F- V$ d if(matrix[j]==1) { for(k=0;k<=s;k++) 0 o$ X0 ]) ?% Z7 k1 e' m# W# A W matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; % K* p' `# `" t6 t. _8 n/ l } } 9 i: K+ G7 z" l( R } : @. y0 l' F2 l( \}

, ?7 V& E' J: U7 j7 g

//////////////////////////////////////////////// , C0 y+ O/ j5 C" |) Ovoid Process(float c[][100],int row,int vol) & S/ z" r A X: W1 Z- d! {3 u{ ( t1 `7 i t; D: l) p. s5 ? int i; ; u, {0 O) @. a S3 Z. H for(i=0;i<n;i++) if(i!=row)c[vol]=0; } ////////////////////// : B7 O) C% [# z) `void Start(float b[],int code[]) { b+ @3 D, r" T int i; & x& f, ~- X9 e1 ]2 X, s9 H0 d0 W) n float nget[100][100],nlet[100][100],net[100][100]; 0 ^2 K0 w) X' j! d' Q; a3 D& X4 K( Q indexe=indexl=indexg=0; for(i=0;i<n;i++) { if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} 0 t; J: x" z* s1 H6 N# y7 p) A if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} if(code==2){ % K _" p$ _! }% U% J+ Z/ I net[indexg++]=1; nget[indexe++]=-1; 3 O4 U$ V% S% B/ I Process(net,i,indexg-1)rocess(nlet,i,indexe-1); 1 E# S( w2 G# r+ |" c& v4 L5 | } ( p, o1 P! a# T. P9 F } s=indexe+indexl+indexg+m; . B- z9 E4 ^+ B0 R4 a Merge(nget,nlet,net,b); 2 B f/ Z# E2 k ProcessA(); $ L; i! W2 H4 t# y+ M InitPrint(); ; z9 C- Z5 W0 M( a7 e5 y Xartificial(); }

$ L5 c: {0 H% u! t' y

void Simplix()//单纯形法 { int in,out,temp=0; while(1) { jckxj(); Print(); - I, m% Y5 [% ^; @5 a' X Result(); if(!rj()) in=Min(); else{ 4 U, h; u& C+ P# \ if(indexg!=0) JustArtificial(); PrintResult(); ' m, d! P* Y9 Y- Y: ~ return; ! P9 m1 }0 H' S } if(Check(in)) * U) ^6 }, P3 W$ f$ K { 9 E, |. L" w' T: c) p( k4 x- ^ cout<<"No Delimition\n"; return; } " T M: o( g+ x' Z# K out=SearchOut(&temp,in); 6 \! V. l: o. H, t Mto(in,temp); 8 I/ r0 T$ P" Y) n, Q' G Be(temp,in); ' {8 f( {6 }0 \+ ^* r4 ^ Achange(in,out); - [# K% v+ w, a8 ]+ v: [7 I, } } }

# D8 h0 M/ s+ {

void main() * B3 v8 x. _* _ l# Z0 e{ int code[100];//输入符号标记 0 `9 F9 R0 b) `9 H# ?1 V4 I' L float b[100]; * ?9 u/ m5 E: P8 @: T Input(b,code);//初始化 9 M$ l" A- T+ p/ H Start(b,code);//标准化行 ' T1 N- C1 Y8 l Simplix(); }

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!