单纯形算法程序

zhyi

单纯形法程序，在VC++6.0 下测试通过！

#include<iostream.h> $ z9 m' V8 b4 b0 b' A* R6 ~6 W#include<math.h> float matrix[100][100],x[100]; 7 o- W) s$ x" ]# `1 uint a[100]; # R0 B( K. }2 Lint m,n,s,type; int indexe,indexl,indexg; : r o$ e+ S6 Q: D& w* l5 y///////////////////////////////// 4 B' o: e- O Z! Ovoid jckxj()//基础可行解 3 s* q" g6 v3 ~9 `; _- C{ ' X( S1 N W9 O7 m4 F int i,j; for(i=0;i<n;i++) 2 h! R* G8 W; u, w! ? for(j=0;j<s;j++) 9 T, m% h& j5 f& q0 ]+ k if(matrix[j]==1&&a[j]==1) ; |9 } E$ N5 J* A) w, F! ~1 _ { x[j]=matrix; 8 l0 i p) N" o8 f% `7 a j=s; } M' R# U7 }2 ^2 N9 r$ w for(i=0;i<s;i++) 5 u& q, `' B+ s8 p9 d& @6 O# S if(a==0)x=0; % d1 A- [6 a9 I, |2 q}

5 W9 ]9 Q* E% @; D% N

int rj()//基解矩阵 { 1 R6 ]6 q' S7 y. G4 d# | int i; for(i=0;i<s;i++) if(fabs(matrix[n])>=0.000001) if(matrix[n]<0)return 0; # ~& _$ u2 x5 y* k8 q return 1; 9 ]0 M) {/ g0 V( J' f! E# Q} int Min()//求最小的 { " u# x2 K `! Y/ b2 w int i,temp=0; float min=matrix[n][0]; for(i=1;i<s;i++) if(min>matrix[n]) & P4 S/ p& }" O9 P) A; {8 z; R1 L { " a4 l% p) a/ U% n9 g min=matrix[n]; temp=i; } 6 T A) X* a. |7 q' F return temp; 1 j' B+ i1 @! A5 C$ y; X4 `# Z} 2 o# {9 w1 Y5 I% ?- @ e! B///////////////////////////////// 9 L$ ~# u" {7 F( i, ovoid JustArtificial()//人工变量 " v! F/ w6 O, S. a* b) z{ 8 Y( ?1 a: K+ z2 k int i; ) a6 I. @' @- \& e6 J0 Q+ w for(i=m+indexe+indexl;i<s;i++) + y! X( q1 e4 v3 }. B if(fabs(x)>=0.000001) { cout<<"NO Answer\n"; return; } $ ^; o" p7 P! P h5 A' V} ( J* n T% Y: I# v* R///////////////////// - ^/ Q& r+ D% W- Jint Check(int in)//检验 9 E6 p! ?& l6 `8 v{ int i; float maxl=-1; 5 r* x$ Z' n- f: c 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; , D( T* S Y7 w} int SearchOut(int *temp,int in)//出基变量 { int i; 8 H: F& P) P4 T' O float min=10000; $ c7 Q' A$ Z, g' g- s for(i=0;i<n;i++) ' S5 {, K* @+ I8 d( ~ if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) &&min>matrix/matrix[in]) + w5 l$ B- L4 d3 G, ~/ c3 t' j { 8 A; O* }, h. @+ `$ K min=matrix/matrix[in]; *temp=i; } for(i=0;i<s;i++) 4 V" Q6 l; d+ G$ a4 R# W0 U5 y if(a=1&&matrix[*temp]==1) return i; 5 l3 M7 ^2 T5 H} ///////////////////////////////// % q; P4 g0 H. o/ D( w& K2 B$ jvoid Mto(int in,int temp) { int i; }" q$ X+ k$ h1 Q for(i=0;i<=s;i++) if(i!=in) matrix[temp]=matrix[temp]/matrix[temp][in]; ; x- G: t' j, |4 B) m u s0 v' J i matrix[temp][in]=1; } ///////////////////////////// void Be(int temp,int in)//初等变换 1 S2 g6 t: R y! ?4 x{ int i,j; * C6 b3 C# Q, R+ M; v3 {7 t float c; : m2 [9 N* J) I( s) j: H5 v for(i=0;i<=n;i++) 4 _/ ^) c; q/ |' z { c=matrix[in]/matrix[temp][in]; ! N' N- t$ _& M2 J1 `$ ]- I% P if(i!=temp) & W, Q- b! U8 b for(j=0;j<=s;j++) matrix[j]=matrix[j]-matrix[temp][j]*c; 4 }! o; d" Z/ p4 G7 L( D } 4 a8 ?, Z- U4 r5 I& p+ J} ////////////////////////// void Achange(int in,int out)//出基入基转换 0 R+ R. ~8 }4 T{ int temp=a[in]; : K' t; a% k9 o; k a[in]=a[out]; a[out]=temp; } : q' s5 C% {+ c; G& D9 X//////////////////////// 2 `+ D6 _) i* j3 R8 nvoid Print() + a0 m) d, _) v7 ^0 d3 N{ int i,j,k,temp=0; for(i=0;i<n;i++) , u% `7 p' a* {3 |; c! t. u& Y { / R7 R9 G/ p7 W) D* ?6 [" I for(k=temp;k<s;k++) if(a[k]==1) { - j V* W! |& N3 O; k4 W cout<<k; temp=k+1; k=s; } for(j=0;j<=s;j++) cout<<matrix[j]; cout<<"\n"; } cout<<"Rj"; for(j=0;j<=s;j++) cout<<matrix[n][j]; 2 E5 w% O- E; b: r/ t! r cout<<"\n"; 0 i5 R6 c* X/ w: j. o( |+ X} //////////////////////// void InitPrint() ' J/ x1 [& U' \# e' t" |{ ; H) O2 N; S3 A* ` int i; cout<<"X"; : \) K% k+ |! s9 i* t6 L for(i=0;i<s;i++) cout<<i; cout<<"b\n"; : h4 i( G( J" F7 P cout<<" "; cout<<"\n"; - u, `; A) ]3 c% Q% D/ z; h} f1 Z5 W, w" p1 Y5 L8 p4 H9 [$ v////////////////// void Result() 9 W2 @5 f& s' f6 N; `: ^{ h, c! m" K$ S0 Q int i; cout<<"("; for(i=0;i<s;i++) cout<<x; + ~# c# y9 ?9 I6 [( K+ [ cout<<")"; if(type==1) cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; } ////////////////////// ; K, ?' D. s. Y8 z1 ?$ \void PrintResult() # p- ^5 M/ z3 w& ^{ if(type==0) cout<<"the Minimal:"<<matrix[n]; * c& H8 D9 h9 T) b7 c8 g# A- h else cout<<"theMaximum:"<<matrix[n]; ; c5 f+ e. o' ` {; N0 C} 8 w4 U' j0 E2 z# y3 F) }" T0 \' ?//////////////////////////////// void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 1 u6 I( e0 r2 T( K2 j: Y{ int i,j; for(i=0;i<n;i++) 8 n) O! `5 J( U+ J3 q6 ]; w% t { 1 L- `0 s, v. J3 }+ j for(j=m;j<m+indexe;j++) # \( m3 R. ^2 j if(nget[j-m]!=-1)matrix[j]=0; 7 {: |3 [9 K6 a% @ 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; / X; E. s/ o! u& n! Z for(j=m+indexe+indexl;j<s;j++) 4 Y* P$ _$ o# h( M' s# C A4 Z if(net[j-m-indexe-indexl]!=1)matrix[j]=0; ' f& z) G! R! O9 O! v else matrix[j]=1; : x4 W$ W! l" W9 X$ B } for(i=m;i<m+indexe+indexl;i++) matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) matrix[n]=100; * S+ `+ F& r! V* _ matrix[n]=0; }

$ H6 p5 F+ v t2 r6 ^

/////////////////////////// void ProcessA()//初始a[] { int i; for(i=0;i<m+indexe;i++) 8 m: P: J i; V2 t a=0; # B v/ y; k9 B' N1 G: z for(i=m+indexe;i<s;i++) a=1; 9 F, C; b; T1 n& k' d. V}

//////////////////////////////// void Input(float b[],int code[]) { int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; 5 u) H7 M" {, k1 o5 b" K cin>>m>>n; for(i=0;i<n;i++) { 1 c8 G" ^6 o( K* `" P% `" | cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; cin>>b>>code; cout<<"The 系数 \n"; for(i=0;j<m;j++) % d+ b' w- o- z; t$ j* I- r+ ~ cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; do{ cin>>type; / M( h) y: r2 {8 }$ v if(type!=0&&type!=1) ) ^( E7 o5 X2 J- V cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n"; 4 {& f$ I: `1 r M" J! f, x for(i=0;i<m;i++) # C+ N$ c/ E% M cin>>matrix[n]; if(type==1) for(i=0;i<m;i++) matrix[n]=-matrix[n]; 6 q! t8 q9 G5 m, [2 U}

: @0 w3 a; L4 }/ q! T( \$ W

. M- ?$ M) C$ r1 s: h+ O9 F7 e////////////////// void Xartificial()//消去人工变量 { int i,j,k; * A2 f$ z o) O- o if(indexg!=0) 4 i. @0 F6 W% |0 j% @ { ' m9 u' I: s6 F8 ~( C for(i=m+indexe+indexl;i<s;i++) 5 x" M3 m. T+ S% s { for(j=0;j<n;j++) # U& k9 F" X; d5 V# K1 @ if(matrix[j]==1) d4 ~% ?! g/ r) S0 j- J8 b1 R7 A3 S { for(k=0;k<=s;k++) matrix[n][k]=matrix[n][k]-matrix[j][k]*100; j=n; } ; S+ ~0 G- j& ^7 D$ g B5 q, k } } }

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) 3 ~. x1 [' t5 A. w( s6 f: u% {% R{ int i; 6 u: X, M8 Y: i$ L7 } for(i=0;i<n;i++) if(i!=row)c[vol]=0; } ( W. y8 |+ x8 u4 W" _& w////////////////////// * B6 Z8 N- Y6 I& Uvoid Start(float b[],int code[]) { int i; float nget[100][100],nlet[100][100],net[100][100]; indexe=indexl=indexg=0; 5 r! _$ K; | v4 B for(i=0;i<n;i++) { 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; 0 p5 f$ c2 ~; h) N0 C0 Y- m nget[indexe++]=-1; Process(net,i,indexg-1)rocess(nlet,i,indexe-1); } } ; J# F; B4 ]! Z" n2 M1 p, a5 J* e s=indexe+indexl+indexg+m; Merge(nget,nlet,net,b); - s! l [( {! ^& ] ProcessA(); InitPrint(); / a Q# l- l. b. s- _4 P8 D Xartificial(); }

void Simplix()//单纯形法 { int in,out,temp=0; while(1) { 8 g0 u' q; i5 V- ~/ o; K0 t- Q jckxj(); % w$ z1 p" i+ e) h Print(); ' ~' H3 X/ M+ X/ S Result(); if(!rj()) in=Min(); 3 A% j* m2 e+ j( N- m( q$ M3 y# G else{ if(indexg!=0) , C4 K2 r7 ~5 n k JustArtificial(); PrintResult(); ; q. X1 ^& F0 s! K return; } 2 _ m6 l( v1 Z if(Check(in)) { cout<<"No Delimition\n"; return; ' u& X9 B# X: n5 c } / |6 h' O1 a, S' v out=SearchOut(&temp,in); / x6 r& y6 @" G Mto(in,temp); & e' f( c: h4 t8 s! Z Be(temp,in); # {; a3 Q3 e% P* L Achange(in,out); } 3 O- x$ H' u7 O1 M8 B& C; v}

void main() % d6 ]9 k6 R3 M) r$ j{ * o2 `* J: ^4 A: w& ? int code[100];//输入符号标记 float b[100]; Input(b,code);//初始化 Start(b,code);//标准化行 ) Q4 ?& R8 I+ f- M, E Simplix(); . |$ ^8 I' P# K) @1 H}

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!