单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

发表于 2005-4-18 21:45 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

#include<iostream.h> 3 s: J3 n" w, [, z* A! X) o6 P#include<math.h>6 F+ f. [5 q& K7 n g6 I7 f float matrix[100][100],x[100];" n. ?$ W4 l1 ]+ ?$ s) ? int a[100]; - ]1 w, f/ F0 d: |int m,n,s,type;& X" L. B8 K' V$ t int indexe,indexl,indexg; c4 ?, `! _ H///////////////////////////////// 2 [5 t' r- @7 p2 E1 C) J8 n! Jvoid jckxj()//基础可行解+ a: N' p! e) i& B { ; D4 e6 K. i1 [& l7 L5 E+ F: E/ L int i,j; . U+ |- X& }1 b( F0 `. e8 K: |; C for(i=0;i<n;i++)3 W; L4 {& K2 G' d% C9 h1 Y for(j=0;j<s;j++)1 \+ J( l# }# B) e$ v if(matrix[j]==1&&a[j]==1) 5 x) |! d# d l0 W# @, K# r+ S6 T {6 w- x2 E/ h6 y3 ^9 i% W0 H+ ] x[j]=matrix~~;1 E' C$ L" K$ W0 t7 Y2 d j=s;( v X7 t. t6 @6 s# G1 O$ f2 T }; V( i" t% I( ]+ u+ k s for(i=0;i<s;i++) ! y0 a! ?3 }9 J. p8 S' e if(a==0)x=0; ; @. h- V* h7 e. z3 L! j}~~

2 Q7 Z1 J( R9 o" }) Z4 }
int rj()//基解矩阵 0 e- Q8 ~; a5 n5 {$ t{* M- B/ ^6 j5 H( T+ A" R V! ^ int i; 3 }0 b5 @2 z0 c2 b for(i=0;i<s;i++) # n) H3 s. I# Q9 E8 Z if(fabs(matrix[n])>=0.000001)6 e, p' ]& z5 B if(matrix[n]<0)return 0;+ ?5 M6 H2 [3 Q1 k1 t. [0 G return 1;4 u8 u- ~* v d) m5 O6 J* o+ m" Z } 8 L- u$ L" a" ?4 m6 W8 i! v3 f" |int Min()//求最小的$ E! ~8 [+ |8 h! V' A5 E0 i( V { ! r5 q' U) w3 h5 P int i,temp=0;8 s# w/ J2 F9 f7 O1 {! c+ C8 U float min=matrix[n][0]; 8 b# Z8 _! Z7 v% [ for(i=1;i<s;i++)% _ q5 K, k! E! s if(min>matrix[n])) f* b! d% o9 x { , q2 k; [ z/ I7 [ min=matrix[n]; # \0 x5 I1 g2 T" n% F1 Q7 W' ^+ f temp=i;. c$ c# m( A6 z } ; ?5 o6 G; |2 V+ J return temp;. a P4 L' Z) x. b" I9 S }! S1 L5 t {; z! S9 C2 t+ T ///////////////////////////////// 3 g) B q& z5 Ivoid JustArtificial()//人工变量 ( [* F8 P% v* i7 w{" H: ?( y/ E! l3 I; T- {& c- C- N int i;. a2 Q. z* O" J" ^4 u: t: G for(i=m+indexe+indexl;i<s;i++) ! u( U$ Q1 v* B if(fabs(x)>=0.000001): _4 f8 o1 y9 D; G3 ]1 r% I8 l { / P' E5 o1 K: [ cout<<"NO Answer\n"; ) t- w. T; D1 Z* v return;3 Y- Z9 M# Y- c F5 J3 Q } ; _. y5 j, ^* P* S |}9 N& |4 u6 S% C/ {0 U" N' i2 M ///////////////////// ' J/ N+ l7 w6 j2 }$ y/ Iint Check(int in)//检验 5 G" T, }. |5 g- C2 t{+ H( m0 a; R6 _! q; Q0 G4 L int i;( t4 y( C- X3 |- W float maxl=-1;4 k ^6 t! F% I* k: U8 H for(i=0;i<n;i++)" q8 `4 H4 |' [. Q' u if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])1 f% a$ W) n' }1 @( a maxl=matrix/matrix[in];$ |) B1 ~, \3 s1 V- }) `# z if(maxl<0) 3 f- Z- w# t, `% _9 {) \ return 1;% a: ]& {" n" i( y& | return 0;9 S6 C0 o, {. T; q0 B0 c } m9 R- R' Q5 [9 @ int SearchOut(int *temp,int in)//出基变量0 v6 j: w5 c. b0 _6 x- K { 7 P* z, `; K+ S5 w int i;7 u l* e; X+ @3 a float min=10000;6 n, C1 E" m1 k3 h' N! M: S; M X for(i=0;i<n;i++)# v5 $ f. n" n# S if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0). [" R* @% F2 h7 C' m H; W. v( n- N &&min>matrix/matrix[in])4 w* g9 a* h2 i8 B {9 E0 f. t2 x/ l. P) v% G min=matrix/matrix[in];6 W x+ z% A- s9 d7 [# z' ~4 w7 _ *temp=i;) d! y" M {- u9 ~( Y( h } ) q. c4 c+ z( m/ G for(i=0;i<s;i++) ! F4 v( g; V8 ?5 w* I, C$ W# z if(a=1&&matrix[*temp]==1)7 $ b9 m9 V- r M* G return i;8 f1 S0 U- c# z4 D } 4 M) v+ y: Z. F* Z- `( [) r///////////////////////////////// ' S0 C5 H v, o! s3 _' U, ?void Mto(int in,int temp) + }! v5 B! K, Z/ D1 d p{ - e [/ k [+ W int i; 7 u6 J5 |+ K+ P, G: F8 z for(i=0;i<=s;i++)0 ?# I ]' P+ v% V, E: } if(i!=in) " J5 @, ^% N$ M matrix[temp]=matrix[temp]/matrix[temp][in]; ! r, r1 N6 C! S matrix[temp][in]=1; , F4 F7 Z; ?" |9 l1 b/ B} 2 C8 ~, p) Z6 a& N- b0 g///////////////////////////// / v0 k; G% I9 W1 p4 N' _void Be(int temp,int in)//初等变换3 I% ?2 e8 B# B# ` g {# P) Z/ k+ ?8 ^! ~0 ` y int i,j; $ i* n& g; D2 q6 p- `4 }2 d float c; & V% J' z, F0 A7 ?# F for(i=0;i<=n;i++)0 \5 `, T" [$ V; `; o6 M0 a { 1 c4 ^7 P0 z Y' y: [) s/ m0 q0 k9 f+ t c=matrix[in]/matrix[temp][in]; + M* n, k. ^% w/ c5 G2 H" ~ I" n if(i!=temp) $ F0 t$ B; m2 x9 M2 w0 T( [ for(j=0;j<=s;j++)9 }! G* E( P1 b( I8 }3 L matrix[j]=matrix[j]-matrix[temp][j]*c; * }" U, F3 t, x1 o } / T8 |* b. y* \" q; e$ s}/ j* x/ P ]8 @; S3 G2 J3 C //////////////////////////3 l% d6 k0 i* G void Achange(int in,int out)//出基入基转换* L" Y( O% K% r8 L {$ y* P! \+ U& C$ @ int temp=a[in];) s) I! @, M F ` a[in]=a[out]; ' H/ N h7 N1 z1 z- t a[out]=temp; ) [9 z6 h. o+ G9 k, Z# v' ?( i} 1 h4 l% [- `4 [' s: v: I: z5 R# i, N6 J//////////////////////// , H7 _% ^. D2 Y. _1 Nvoid Print()2 `2 ^, v1 F& _ { 3 x( s2 }5 @, Q# F6 F int i,j,k,temp=0;1 ]& @6 c- { z. O for(i=0;i<n;i++)" Z# p5 [2 Z/ ?3 T; | { O6 E! Y7 F# n0 P6 o for(k=temp;k<s;k++)- b) D$ {+ K r if(a[k]==1) ; ]! w$ V/ N/ z. Z {. f: B+ I" F2 {2 N7 I cout<<k; & A7 A' ]" w5 J7 K6 R temp=k+1;* Y/ B5 b" C" Q# Q3 p3 X k=s;! u4 e* w5 i7 C( y0 m } + @7 G5 Z+ a6 ^ for(j=0;j<=s;j++)3 q$ w6 m* G+ l( `% n4 j& | cout<<matrix[j]; ' m4 b7 Z5 k5 j, z: I cout<<"\n"; ( h+ C' u- ^) M( y }& T3 y. [: m0 `9 M cout<<"Rj"; - R1 o+ ~$ y9 p1 f9 m/ ]1 B for(j=0;j<=s;j++). O* d! u [5 U' S ~# b% H3 U cout<<matrix[n][j]; ; E, O' q/ U, J% p, F cout<<"\n";7 U3 A# h, N: k) k& U4 t. Z+ [ }5 r- t- J* g* X% h9 h% K$ m4 k //////////////////////// 1 M6 ~( \$ M X& [void InitPrint()4 U: O1 x9 r. _# P! i& F/ g: h, J* ? { 7 d" e, y8 O+ | int i;3 Y/ B% L, {" ^ L1 `; O3 F! Y cout<<"X";6 F9 i4 L1 P, c/ E4 V1 b) Q for(i=0;i<s;i++)0 p( O4 Y' F9 r* N; g cout<<i; 7 U$ @' C1 F& Q1 |1 b cout<<"b\n"; 5 q* f+ L7 x/ L; w$ X8 n, l# \ cout<<" "; ( ?7 d, i- l6 y# f- F0 { _ X cout<<"\n";" O3 r2 [* D( b: Y" F6 | }, k8 j3 [# [+ [/ g2 }( \5 u //////////////////$ E- h# g7 i4 J8 i" ^$ F/ r void Result() 9 p) h+ u5 @) l& c- W2 g{ 6 ?7 a8 V. W5 f" u1 }/ ]4 ^6 p/ { int i;8 b# g2 F8 q3 D: h2 Q$ w cout<<"(";2 C' Q1 m' d4 N- B for(i=0;i<s;i++) ! I# l4 C4 `1 S A cout<<x; ; z; q, l" u3 s5 o cout<<")"; h2 E7 D I7 N' d8 B; j3 z/ U if(type==1)0 ?$ s) O7 B; q cout<<"Zmax="<<matrix[n]; * v* F3 A/ f" ^! G& r# i- C+ b* H else cout<<"Zmin="<<matrix[n]; ( R- X7 v! t) f x6 k}& b; V3 B! A& I& ^/ G8 l2 ? ////////////////////// 2 M3 f7 S8 h+ q& R2 Gvoid PrintResult() - E- Q4 z/ v' v9 b+ f6 X- j{ 9 R2 A O g, T2 v( S if(type==0)4 {, I% p: H# e# P cout<<"the Minimal:"<<matrix[n]; % _% w# `- t6 D4 s5 e+ D else cout<<"theMaximum:"<<matrix[n]; q& R0 Y" y& ] } & ^3 k6 c9 {5 }' v, p( j//////////////////////////////// * C& F) x- V: M- F" }* ?void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 2 V4 |* n4 T. V" e* Q{3 I- }' G C" q; ?6 l+ m7 Y* H int i,j; 3 N; a- i6 l6 Y) U# ]5 l. } for(i=0;i<n;i++) $ b3 S0 x7 a; `: K { 6 V6 p6 c+ z% N* ^4 `, y) J for(j=m;j<m+indexe;j++) 3 Z. h, `* w2 ]1 T if(nget[j-m]!=-1)matrix[j]=0;7 B2 k7 l8 ~: X else matrix[j]=-1;! r3 q; _6 P% N1 @! H for(j=m+indexe;j<m+indexe+indexl;j++)/ B$ G: o" ]/ g. B+ [ if(nlet[j-m-indexe]!=1)matrix[j]=0;' j) K3 F0 F. {3 W( N" c else matrix[j]=1; 0 Q2 |; d0 ]$ A$ K( o for(j=m+indexe+indexl;j<s;j++) 3 d/ J" f2 S' S if(net[j-m-indexe-indexl]!=1)matrix[j]=0;% W4 L8 C8 H: b else matrix[j]=1; 9 i/ s' d9 K5 V7 ], j- k } 7 m, z+ l. F- P+ O6 d; ]/ a for(i=m;i<m+indexe+indexl;i++) 3 i/ d) _2 Y ?/ y" l matrix[n]=0; 4 _4 X3 N3 M" P( { for(i=m+indexe+indexl;i<s;i++) _! x. @/ J9 E/ P/ B& `) L# M matrix[n]=100; 4 ?" `8 b; l4 c& [) R4 y- x1 R matrix[n]~~=0; 4 H% f y* U8 R& n* U1 @; t}~~
4 P8 e8 Z4 K- [/ |! \2 k: d2 W
/////////////////////////// / `5 V8 ^; ?/ V% T7 j, `. cvoid ProcessA()//初始a[] s/ |- C5 R4 p1 }4 z/ Q! Q{1 J/ c) n- `" O& Y; m3 z2 z int i;; x/ |: q( g) I5 D/ L1 Y1 C for(i=0;i<m+indexe;i++)2 N* P) O a3 i$ P& h1 b' D a=0;2 K5 l4 M1 u; s5 z% d' K for(i=m+indexe;i<s;i++) 8 a) R# n6 x* C7 q! G9 T a=1; / e! N2 `& p7 I* U1 [% A}
/ ?1 k) C! i* m. l/ L% h/ y
//////////////////////////////// 7 Z$ V. V4 ?- x9 A) Wvoid Input(float b[],int code[])7 Y8 } S; y, D# c { 3 B: V9 E- y; Z+ n7 f& Z! @ int i=0;int j=0; M8 ?5 `7 l" X cout<<"The equator variable and Restrictor\n";% }: V6 T( W5 k3 ^1 q1 s0 H cin>>m>>n;$ b% Z+ H" D+ R% N- _3 D for(i=0;i<n;i++)+ T. q. q! O9 U1 l0 } H6 C { , Z. c: Y" L/ a q+ ?4 g) { cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";. h7 m) x* r/ k# x/ F* O cin>>b>>code;! L0 m" ~! p/ l& x+ S# } cout<<"The 系数 \n";( W- X/ [4 p/ u+ y; ^: `9 {" | for(i=0;j<m;j++), l3 a+ \/ N0 K cin>>matrix[j];3 x$ ^( e0 k/ u* E6 |4 C } ) N; y4 W5 X8 `+ o Z+ N cout<<"the type 0:Min 1:max\n"; # s; {. r( S3 b, Q5 G, Y$ [! p do{" ]* `/ p/ `" q4 t( ^7 `( t8 g cin>>type; ! P; H# M, U. N3 H if(type!=0&&type!=1)$ k: ?1 g% ]* Y2 r0 b8 a cout<<"error,ReInput!\n"; 9 ^( X3 [* t$ M; {6 v! v; V$ A }while(type!=0&&type!=1); ) f; u- j8 K0 h) J cout<<"the Z\n";8 Z. X U& ]) r for(i=0;i<m;i++)6 x3 y0 O/ s9 [; E cin>>matrix[n];3 Z c+ d$ ~$ e% m if(type==1): @" ^5 W0 e7 b for(i=0;i<m;i++)0 p B. S- r# O+ ]$ p matrix[n]=-matrix[n];8 U1 p; f2 h& H0 J/ ?8 p }
# |! w3 S8 ], i' ?6 ]+ K [+ f7 t u
: X/ F! \3 |) }& u6 {7 ]' x////////////////// - X" _. w2 `2 \, B void Xartificial()//消去人工变量$ {+ m( K$ L F/ D. r { 7 f0 {; Z _3 ?/ p# H G3 f/ A2 w int i,j,k;. Y% F* Y! e: r0 d3 b if(indexg!=0) / ^ A1 o1 I! q. p: K { - T4 R; u8 s( _1 E, l' C( C* N for(i=m+indexe+indexl;i<s;i++)9 e+ X- ?, I! g; E: Q/ m! J {; D! N, ^, Z7 s# n+ S: M1 ` for(j=0;j<n;j++) # ~4 e/ `' g; D' ^6 a, W if(matrix[j]==1)% M9 ?7 _! F( t! m { 7 E" S; y' T9 b+ u6 V, g1 b+ W for(k=0;k<=s;k++)- m1 Z! p. ?& ^0 ?& X8 f matrix[n][k]=matrix[n][k]-matrix[j][k]*100; . w; E' o9 l7 C. F N, ?" X7 k j=n;& _+ a$ J3 R0 ~) c% C y" ^* O }9 t- V! b: b6 k6 Q6 O1 g" g3 |( V }/ _! {8 \$ ^+ ~3 x8 E* C } ! J) L7 ~, `" Q1 H) z* z' K# y' Z}
: u( [& n' M3 t/ o( h3 Q" U
////////////////////////////////////////////////+ R6 C" m) @9 ?: X J2 N% V void Process(float c[][100],int row,int vol)7 l9 N0 |; l+ q; _& I {4 \$ B- w% u/ c' Y7 s$ l5 b: o int i;9 j! h1 ?& y7 X* ^$ c9 B% E for(i=0;i<n;i++) 1 u9 f" ^$ s5 ]& k6 m' ?) n1 B8 } if(i!=row)c[vol]=0; 5 W+ m# N: k) ~7 r# k1 C2 b" b& ?}! F# j8 N+ T7 G. d+ I5 V7 G //////////////////////) d5 y' B* d4 b4 [' h, K/ z3 g$ C' N6 H void Start(float b[],int code[]) # A/ _% H6 C$ B1 z: M8 m5 ~; y{) P- N7 V2 ~( A1 j int i;: T2 }& M: s5 O. ~ float nget[100][100],nlet[100][100],net[100][100]; ) G1 A' @! J, X, W1 } v6 e indexe=indexl=indexg=0;, @3 j' k8 \$ w) }9 s for(i=0;i<n;i++)# c) ?% F' t% c! M+ d" Q {) X: y/ d9 H$ w if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);} $ |. F9 f6 o7 o1 g" S if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}) q& i' r5 n# I: ? if(code==2){& m' s6 C- ^# ?! G j7 `" W+ K net[indexg++]=1; 8 i; P# ~4 k+ Z6 e nget[indexe++]=-1;( ]$ E9 V8 b8 z$ |/ w9 Z Process(net,i,indexg-1)rocess(nlet,i,indexe-1);+ e6 r8 j) E3 b; S6 ?- I# {! y } ; R: G/ S: p. N9 ^ Q) @, ? }) z5 i7 U& r0 _( e, J3 M7 m s=indexe+indexl+indexg+m;+ F) H4 _" P2 a2 t$ n Merge(nget,nlet,net,b);1 i' m$ z/ i- C, C G8 L: d5 a ProcessA(); : g* m0 [* n0 L" p6 v InitPrint(); 0 @9 \- r5 N: Y# Z" U Xartificial();! Z; T5 N* \ A b) F; r }
- ?# b$ ]/ f. c }9 t$ f( f
void Simplix()//单纯形法; `$ R! I! j; Q; `# l {2 v, j! G# _; j int in,out,temp=0;1 g% t& u, c7 Z8 H E+ k while(1)2 a$ k( J& |# U: y. H/ B { . ^9 J" y+ K ] jckxj();5 S, G' B& }: d. b Print();4 V" [% k# {$ ~2 U2 G8 S Result();8 M9 F" {7 a$ r if(!rj()) in=Min(); ) {$ Y* a3 e0 e3 g else{& g5 K/ X6 l M# h if(indexg!=0)0 i% b& b; X0 k JustArtificial();% s( ]9 U I" F. u1 P4 ^ PrintResult(); . k9 k7 ~3 i; f$ j e0 [# W4 _ return;. N. X1 C. ]5 F: B/ o } 8 C3 _# _" b8 k if(Check(in)) 3 l7 e- f1 m3 T* {! n! H3 d {7 v; M" T2 Y. A5 B cout<<"No Delimition\n";- T9 U: p$ }$ L- a2 i7 v# h return; 0 {9 c/ ?- q! e3 E u! S }" r$ n) s- [" j+ t/ r' ] out=SearchOut(&temp,in); ( N+ W7 @1 `) M5 n( m Mto(in,temp);1 }+ y$ {0 Y+ T6 L! D* _ Be(temp,in); 1 y/ S% B: K6 ]3 g5 g Achange(in,out); 6 N& c2 s0 I( L+ N( M+ h% t8 Z/ w2 V% r } O( z7 H; C8 j- h4 L: r }
+ f+ ]$ @6 m- Q: ?
void main() - F+ d! ^* }1 A$ ]& q3 O" B/ m$ L/ a{2 a B9 _8 a9 J( p' y1 K: ^, F int code[100];//输入符号标记 ( d( L* X7 _, K! A! e, H- _ float b[100]; / {" a% g* t8 E, N* A Input(b,code);//初始化 8 x- {0 F# M# p b0 I+ V1 _+ y8 g Start(b,code);//标准化行 & t. Y; H& q4 v- n. s Simplix();) a& u. l$ i) h [; ~8 @( p. [' B }3 P, U. X- b/ @8 t2 _0 l