单纯形算法程序

zhyi

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

#include<iostream.h> % g8 j- f% `& E& `# [7 Q#include<math.h> , n7 S, j, ~- D# o0 \) ffloat matrix[100][100],x[100]; ' A6 X+ b" `( j. ]8 Vint a[100]; ; T0 b* {( O0 e1 R3 c8 I& cint m,n,s,type; int indexe,indexl,indexg; ///////////////////////////////// 1 R( t4 X1 T- V$ z7 }7 _' Mvoid jckxj()//基础可行解 # J; W7 B! B6 I$ z# H" I% E{ int i,j; for(i=0;i<n;i++) 3 R3 o$ G; |$ [* S3 y- v- I) a for(j=0;j<s;j++) $ _& c. D# ~# l3 `- I1 p6 ? if(matrix[j]==1&&a[j]==1) { 9 J3 `: A1 {$ ?% r+ p" D9 g x[j]=matrix; : E9 r/ q1 v6 C" [4 w2 E$ e j=s; X; `% ^8 x2 Y7 @! c } for(i=0;i<s;i++) if(a==0)x=0; 8 v. _7 c. G t B; M7 K" }* R" W" u}

int rj()//基解矩阵 { int i; # J6 n( r, d+ R$ A6 \- b. h& \ for(i=0;i<s;i++) ) d! O+ v2 E2 s if(fabs(matrix[n])>=0.000001) ' \; F$ v' g3 J$ e6 [" ^ if(matrix[n]<0)return 0; return 1; } ; a4 u! w+ n* B" n- oint Min()//求最小的 { int i,temp=0; float min=matrix[n][0]; ! l! q) C7 s0 q* c, H; g# \ for(i=1;i<s;i++) if(min>matrix[n]) { min=matrix[n]; temp=i; } % ^, T2 t' |& h5 y return temp; } ' P! I* v% a( o1 @0 n9 c$ L) M///////////////////////////////// * `6 _5 w6 @4 S. T& R$ Nvoid JustArtificial()//人工变量 ( f2 D+ O& {4 f- }{ int i; , }- H2 h2 P9 ~. j) J8 N' f" U7 D for(i=m+indexe+indexl;i<s;i++) ! E4 H V2 w/ R `5 Z$ ~, { if(fabs(x)>=0.000001) { 5 f1 X3 `6 i% T# g& l cout<<"NO Answer\n"; return; 4 x* V/ h$ _+ ~5 s9 g) u } } * v% P7 u) n( T) t& W///////////////////// 2 R2 F. z- z; Xint Check(int in)//检验 { 6 t+ ]2 T& O9 B, x- B# v int i; float maxl=-1; L( F, j; P( m# q for(i=0;i<n;i++) & ^3 ]3 G# v6 f: H [ if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]) maxl=matrix/matrix[in]; if(maxl<0) return 1; ) R" Q2 B% h5 a8 l3 j; Q return 0; } 3 h% ^1 O! m hint SearchOut(int *temp,int in)//出基变量 { int i; float min=10000; for(i=0;i<n;i++) ' D) i5 C0 D( `, M, z if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) 8 I. [0 }* c* G |2 f, P &&min>matrix/matrix[in]) { min=matrix/matrix[in]; *temp=i; + P$ q& U; Y2 t/ V2 i" j# V } ! q9 a& E% h7 l. t3 K: t8 l for(i=0;i<s;i++) if(a=1&&matrix[*temp]==1) return i; & r" T8 D: [8 W# J0 l} ///////////////////////////////// # `1 C& A. `" ^. O: u7 _# K" D( Tvoid Mto(int in,int temp) { int i; 2 {- t9 q4 q) L0 p& C$ Z for(i=0;i<=s;i++) % `; n; g% q% a" n. b if(i!=in) matrix[temp]=matrix[temp]/matrix[temp][in]; matrix[temp][in]=1; % }! O: u" ^) m6 {% X} ///////////////////////////// void Be(int temp,int in)//初等变换 . z" [9 ?1 F( g1 D! f, |{ int i,j; 1 N' e) y5 Z- L float c; for(i=0;i<=n;i++) { c=matrix[in]/matrix[temp][in]; ( o7 U# B+ b' T& K if(i!=temp) for(j=0;j<=s;j++) matrix[j]=matrix[j]-matrix[temp][j]*c; 8 y( t& @+ L W5 T/ b } } ////////////////////////// 8 ?5 x5 C& i+ |6 ]$ |( dvoid Achange(int in,int out)//出基入基转换 { int temp=a[in]; a[in]=a[out]; ! ^% C9 O2 n. P4 c5 `% _, y. w a[out]=temp; } ; t6 A# m5 P5 U$ c: w( x//////////////////////// $ P0 B } X1 g* p& P" Jvoid Print() $ R L0 x: N' J0 v& Z0 e, ^{ 0 Q; V/ f. x5 a7 N8 U# k int i,j,k,temp=0; ' K' U0 ?0 O# F. u2 `2 `0 t9 Q for(i=0;i<n;i++) 5 ~" A, F0 F9 e+ _; X { / J; u t, H8 S% t d for(k=temp;k<s;k++) if(a[k]==1) { cout<<k; temp=k+1; , d! b: S% n8 K4 N* f k=s; 2 T) O2 K8 k2 o, e0 _ } for(j=0;j<=s;j++) cout<<matrix[j]; 9 r- V4 e' }& y \5 o! C cout<<"\n"; } 1 N" v( x- ] {0 o6 M7 ?3 K cout<<"Rj"; 7 m, G3 L+ J# Z, C- W for(j=0;j<=s;j++) cout<<matrix[n][j]; cout<<"\n"; } $ N6 e* ]% I7 Y; M( p- p1 `//////////////////////// void InitPrint() { 1 H' L9 w8 S; B5 c9 ?' H) X( G# F int i; 9 y9 y5 O* o9 N( A4 B: G cout<<"X"; for(i=0;i<s;i++) , J2 O& S& V& V cout<<i; $ `- y1 B: K; c, J( \ cout<<"b\n"; cout<<" "; cout<<"\n"; 1 n$ ]3 b7 G% P+ S0 B- Y( e. d; u* [} / u) }: A6 x B, n5 L q! v////////////////// 3 i. T0 ^3 L0 T' _9 ]& w4 \void Result() # y6 }" ]& V" \/ q4 n( O{ 2 z$ v) c+ l8 o. V( r7 i int i; cout<<"("; - M) d2 a' @6 k1 Z' L4 M- D for(i=0;i<s;i++) , a9 a: Y; w: J& @/ E2 v cout<<x; cout<<")"; if(type==1) ' a4 [2 M. c' v7 V6 b8 F0 }( X7 z cout<<"Zmax="<<matrix[n]; else cout<<"Zmin="<<matrix[n]; # e& k" `- T7 u% r; s& K' J0 q} " G4 Y' ]: }" [////////////////////// / }! G" d1 G+ n) |void PrintResult() / m/ q- J: L5 `5 J+ c8 P{ if(type==0) % H, U$ f) g# T0 ]: f/ L cout<<"the Minimal:"<<matrix[n]; else cout<<"theMaximum:"<<matrix[n]; } # L7 r0 [. \# i+ ~( a: R//////////////////////////////// ; L" D8 u' P, H8 d7 Jvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 , m0 C# l" c* p$ n( V{ / L7 G9 K& b" w int i,j; * _4 R4 q" ^% V( L# K4 e. x! { for(i=0;i<n;i++) a# ]# U+ f! H/ o1 l4 q3 h& { { for(j=m;j<m+indexe;j++) if(nget[j-m]!=-1)matrix[j]=0; else matrix[j]=-1; - O9 x7 P; v/ Z" Z0 k) ~- Y7 f for(j=m+indexe;j<m+indexe+indexl;j++) if(nlet[j-m-indexe]!=1)matrix[j]=0; 3 x# X% p! p, T# A* { 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; 7 o; y9 h% W) R, R z } for(i=m;i<m+indexe+indexl;i++) 8 z8 p0 h6 `( ~ matrix[n]=0; for(i=m+indexe+indexl;i<s;i++) ) t4 t' `6 t- s G matrix[n]=100; 7 @& j! y, X( J4 t matrix[n]=0; $ ?& K5 J- ^. C! |* ?}

5 c+ M; ?# F3 Z& m

/////////////////////////// void ProcessA()//初始a[] 9 z# b3 H4 A" G1 ]# U6 N{ int i; for(i=0;i<m+indexe;i++) a=0; for(i=m+indexe;i<s;i++) ; G _8 [, m. `9 V a=1; " d1 j1 Q/ m1 |) N$ H}

4 j5 d) o% f" t' s7 q- u5 X. C& M

//////////////////////////////// void Input(float b[],int code[]) { * ^% Y7 m0 B! {% ]& N7 n2 A$ P- m int i=0;int j=0; cout<<"The equator variable and Restrictor\n"; cin>>m>>n; 8 q' J9 g; G) F/ \$ K# ^4 Y7 @ for(i=0;i<n;i++) 1 E3 F) N" s0 P ^7 x { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; 3 L+ s5 C; X$ E/ ] cin>>b>>code; + d4 s P4 x2 o( q cout<<"The 系数 \n"; for(i=0;j<m;j++) cin>>matrix[j]; } cout<<"the type 0:Min 1:max\n"; do{ cin>>type; 2 `) F# I' d: V5 h3 e" n if(type!=0&&type!=1) cout<<"error,ReInput!\n"; }while(type!=0&&type!=1); cout<<"the Z\n"; $ `: S+ k4 b4 R0 Y( g k. X, [ for(i=0;i<m;i++) 8 t. [: t: N1 ^9 \+ c# ^% B+ l* I/ i% L cin>>matrix[n]; if(type==1) 6 i4 i; I6 I# B for(i=0;i<m;i++) matrix[n]=-matrix[n]; }

4 O. [& f* q) [! T7 K7 e7 e////////////////// void Xartificial()//消去人工变量 - v; e0 ~ U2 a9 N8 @6 P8 h9 q{ . h) X4 b6 `. M( v! u+ C int i,j,k; if(indexg!=0) 7 y% u$ W8 ?. E4 d { for(i=m+indexe+indexl;i<s;i++) 0 r: ]4 W) Y( u& _! j* p { for(j=0;j<n;j++) if(matrix[j]==1) { for(k=0;k<=s;k++) 7 m& M$ [" \6 r0 G% m& v6 f; u& a matrix[n][k]=matrix[n][k]-matrix[j][k]*100; / W) g5 J6 K3 H E j=n; } 9 y2 Y* V$ m( r* a$ f } } }

2 }( H9 H1 Z4 d

//////////////////////////////////////////////// void Process(float c[][100],int row,int vol) { 6 o& U2 D# G" W2 ^ r int i; for(i=0;i<n;i++) ) f1 H; R0 v, k& P4 r. C if(i!=row)c[vol]=0; } 0 ^3 G2 t+ h: N; ~. W2 W1 \' @////////////////////// 5 h% [4 A4 K; [) g9 y& bvoid Start(float b[],int code[]) & J& X/ }+ y5 y; G; t{ 3 C! u- T7 _5 a5 r* a0 b int i; 7 K" h# ?% p0 J2 C float nget[100][100],nlet[100][100],net[100][100]; indexe=indexl=indexg=0; 0 h' X8 m3 u9 n- V6 y' V6 c) N for(i=0;i<n;i++) { 8 q7 W- V Q+ B z8 G( S# c if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} ) t9 u3 l' t x% E' r9 \ if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} 0 c' D0 @, `9 F' O5 b if(code==2){ net[indexg++]=1; + z7 h+ F" E. Y% ] nget[indexe++]=-1; Process(net,i,indexg-1)rocess(nlet,i,indexe-1); } } s=indexe+indexl+indexg+m; + V: P8 x# v6 \6 y Merge(nget,nlet,net,b); ; M( { f! E1 f* K; P; ^0 w ProcessA(); 6 ?# B3 x" ^( Z! z1 F( h& N) T InitPrint(); Xartificial(); ; G* @+ @0 b7 s9 ~}

D, r- u) l/ n$ T

void Simplix()//单纯形法 { int in,out,temp=0; - E- b4 Z2 e/ K. Z while(1) & o2 a( ?7 Z! y { jckxj(); Print(); Result(); if(!rj()) in=Min(); % `0 G Y' v0 d2 u' P$ W2 V: g else{ if(indexg!=0) . Z! H2 s! | i4 x JustArtificial(); & @2 |8 h4 |9 b- j R: \ PrintResult(); 4 r& T9 L+ G1 o return; 8 x @- I' N8 @& p* V } if(Check(in)) " p+ d: K& t0 L1 x { cout<<"No Delimition\n"; return; } out=SearchOut(&temp,in); Mto(in,temp); Be(temp,in); Achange(in,out); # W a7 x- X9 i, ^* X+ B } }

. q9 ^) P0 l( O' P) l4 ?# D! [+ c

void main() . h) Z) @# M4 Y( {' o7 J{ + v& V* {8 o0 y+ ?/ F2 L6 L int code[100];//输入符号标记 float b[100]; $ B# L: u. g+ z) T$ l% N Input(b,code);//初始化 Start(b,code);//标准化行 8 a5 H* s0 I2 d j7 } Simplix(); 5 Z: A8 u: a% i' A" u}

lvming

谢了

M_Tramp

不错啊！！

pangaogao

Good!

那时花开

好用不？

那时花开

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

monkeytail

哇，楼主强人！

monkeytail

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

bnulj

这么长！看不懂啊。

mengfanqi

so well!