单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> 9 Z* l3 l; p; C' A- J/ H#include<math.h>1 Y9 w8 W/ I# T' @ float matrix[100][100],x[100];; d; u: C7 b9 s! s$ x int a[100]; % I m2 A) E2 U, x1 J" [0 T( Zint m,n,s,type;3 G1 c9 h) S9 w) J int indexe,indexl,indexg; * x1 O! t* \7 S/ Y, d2 J///////////////////////////////// h }5 J) J) O" W void jckxj()//基础可行解% w; g. H- B0 V" u { , @, V2 e4 S) I8 I3 N& W. | int i,j; 1 F1 L# |* |# M% j+ p u7 t! e for(i=0;i<n;i++)5 |8 a) s0 H+ N! s for(j=0;j<s;j++) 7 j+ S' B$ A! F( w( O' p ^, ^2 ` if(matrix[j]==1&&a[j]==1) . c' z4 t" N+ R# I9 o* X { 2 b3 s' O" X7 [* G8 A x[j]=matrix~~; 3 C9 U5 B2 H8 F) j' e, M j=s; $ N! x& t C0 E+ m/ Y. D } ) ~( P! N! {- i& g" c1 A' s for(i=0;i<s;i++)+ |- I/ ^9 `& @- i \0 x& u& L if(a==0)x=0; , u! Q" H; J* ]0 r4 h}~~

' M2 m; j* f+ B
int rj()//基解矩阵9 R \- G4 d* b- z {; C- S( o! l; `, X int i;: ^. U- D( X) Z3 Y# ? for(i=0;i<s;i++)/ u! x8 g3 {. }. |4 j# n2 {& A if(fabs(matrix[n])>=0.000001)3 N+ {. x' t. E if(matrix[n]<0)return 0; 1 ]2 t$ B* g( D& ?+ v# d return 1;7 R9 W( F$ S1 F$ _; b } 5 _% n. B3 a' r* sint Min()//求最小的; Q6 { S& a) b: _: M0 `7 Q { + m$ e2 G, U5 J9 `" M1 _ int i,temp=0;2 [' t4 _* u3 G% q# a float min=matrix[n][0];3 r/ Q5 y+ p1 e for(i=1;i<s;i++)$ V; Z2 p8 r) M: d5 o4 o; S5 E if(min>matrix[n]) $ v- f( V& A& u5 S& w { , t) ]* |7 [6 N z min=matrix[n]; ! w" R, s+ O6 R1 s8 G8 n temp=i;( B% z2 V! t+ @3 ?) l( O9 S, V }$ S6 Y3 r, t3 f- I return temp;, n8 G, l/ n6 _! y. l' {" ~ } * N, t' d8 b% h: `; W5 L; b; z/////////////////////////////////" G9 ?: o# M4 I! l) ] void JustArtificial()//人工变量* c0 ^0 @) r ~+ W7 ~ {( U- m- \9 C% b, n" W int i; 6 V+ H1 }. |! H for(i=m+indexe+indexl;i<s;i++) 3 R1 y! s! z( O, v7 s if(fabs(x)>=0.000001) ' z* Y2 R/ C8 n { ( U) J' U# |- m6 ^+ H cout<<"NO Answer\n"; * K& _- I; }" \) m3 R return; 5 T; ?" U6 K k5 m6 V, p5 g3 s } : Y( }# `' F u5 {! x! F} 1 ^% F2 d: z ?2 o6 E3 m3 N1 w& d4 z/////////////////////9 h, S& o9 T# b# S7 w int Check(int in)//检验 1 n; r9 d P% W$ Z) }5 B8 L{ ( D& [, |3 X$ ^0 C int i; 4 m6 N* M$ A3 h- x7 g/ X float maxl=-1;( ?2 X" [+ K! a e for(i=0;i<n;i++) Q5 R3 z' K# u8 `" a8 v3 S3 | if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])5 @) M: n3 v; _, m' m% G maxl=matrix/matrix[in]; 8 S/ Z$ `+ N. C& P if(maxl<0) 1 y3 t" R- i: o) t return 1;5 v3 r6 ^; B/ f3 Y return 0;4 Y2 }4 f% H! a5 s5 `1 q } - v3 ?- n' f% ]/ t mint SearchOut(int *temp,int in)//出基变量 8 }% x9 h5 S2 L7 f{ 2 }. m9 p0 @- x' M: K int i;2 O( ~- O7 \: t" b$ W s float min=10000;0 U1 ?. T7 o9 x# c- u% c+ G3 Y for(i=0;i<n;i++)4 z+ t# F) t- Q5 P& Z' x if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) - e ~! r' M+ ` I &&min>matrix/matrix[in])+ D7 a5 X. }4 X5 G9 l {6 G3 O: N( _) A min=matrix/matrix[in]; ) B. u. r( Y. U3 C3 x3 } *temp=i;, C0 I2 f; M( `& K' Z1 ]; f }/ j& ~& ?! e# _ for(i=0;i<s;i++) ! D4 v, j6 f' P: [ if(a=1&&matrix[*temp]==1) : G' Z4 y" A9 K9 h4 j3 V. t return i;- U( g+ E* q; ^9 u% V } , D) Z3 @5 x2 P0 F, h u) v- @/////////////////////////////////) I. |0 k% G5 M# C- j1 ? void Mto(int in,int temp) , J& v, L$ {$ X z; k{2 k$ ]$ C& f* j, N/ ` int i; 5 k& H$ w; a2 d7 u2 ]% T8 i for(i=0;i<=s;i++) 6 B8 ?; W8 Q1 B: y1 b3 U# [0 ` if(i!=in)4 h2 E3 V/ o+ ?5 R matrix[temp]=matrix[temp]/matrix[temp][in]; " |/ R9 X ] U% [* p: L2 P matrix[temp][in]=1; * C# I8 l( ^* a} 0 p8 b- k2 h% x) [; Q/////////////////////////////% z+ C- w' g) G& z. s' K' }: r void Be(int temp,int in)//初等变换$ W: f9 f5 J' v8 @3 i: S/ n/ I {& i, n# X( ]; G" Q/ I+ C, e int i,j;0 U" K4 v5 O& y+ v- ?; K: _ float c; ; v, y. y' d, ~8 f for(i=0;i<=n;i++)- t n7 D8 T; n( Y { 6 g# n8 w) p# P( X c=matrix[in]/matrix[temp][in]; N( Z" c4 I& q% l5 _ u& N Y if(i!=temp) 7 Q3 H. H2 b! h; s for(j=0;j<=s;j++) 5 @1 {: c# j Z* z3 Z( d- B4 U matrix[j]=matrix[j]-matrix[temp][j]*c;2 u* _* f) H( V3 S } / s3 r/ ?9 H$ a/ _8 P- ^}. p& S( i- i2 } ////////////////////////// % N e5 _% M" \7 q# Ovoid Achange(int in,int out)//出基入基转换 ; H$ R, r( t% ]# ^{2 C+ Q/ b( y. U- W( f int temp=a[in];. U+ F5 R& }' V$ p( C a[in]=a[out];/ b; J; O" K7 v# V: V+ y$ C a[out]=temp;* k- E0 U9 v5 E8 M' D } " H+ p& P: x2 J+ n////////////////////////7 O0 R& q+ p$ D void Print()8 ]# G; q l+ [: E* E {' t8 A& d1 `9 L. E int i,j,k,temp=0; 4 e" v- ~. o# j C for(i=0;i<n;i++)# K) L: \6 I& ?$ i+ O/ L. O0 T* F {7 E6 }: m/ c8 M9 `7 y6 |& G" P/ V$ h for(k=temp;k<s;k++) 9 r4 E* Q% a+ u) C0 }4 W. y: M if(a[k]==1) 5 d& h) p3 L+ S( V% Y9 O. }( r { h. Y+ _) [; X" q6 H cout<<k;+ ~7 ?% y9 R8 K! J, i8 w+ E+ k temp=k+1; * J% P; ]0 g; `2 u) A k=s; ( |6 _4 n& R1 Y5 l }: w) T2 r1 S7 {+ ~0 j, F for(j=0;j<=s;j++) ; U$ F9 B! x, A8 g cout<<matrix[j];, x% q! e$ `/ _. \ cout<<"\n"; : z8 \ y+ K. Z } * B8 m- Z; M. H. b cout<<"Rj"; ) T; W* L: G4 n5 j) h$ b# a! D* P( a for(j=0;j<=s;j++)5 r8 z0 J0 R1 `2 G% H* w$ Y' s+ n; U cout<<matrix[n][j]; # |( T) i3 }5 \. J0 i/ H6 a cout<<"\n"; 0 O$ _: t/ _% j# q# ~( T q} + F I/ Q/ ^7 u' H* x, D8 A4 p/ Z: p////////////////////////3 B1 P& P0 i1 R$ B3 c. T( D void InitPrint()0 c( I0 ^$ a& M0 f {" p0 S5 X& k2 j$ y! Z int i; , C5 i! m8 V( E* t6 q. ?& {; s cout<<"X"; ) V: e" g3 ~) J& n" I for(i=0;i<s;i++) 4 u. u1 j' E7 b @/ [ cout<<i; 4 g6 L, Y$ C5 |6 U0 Y+ m cout<<"b\n";- J1 E! ^% ~! C* u cout<<" "; & o* z! Y7 d- F5 a" T: U, V cout<<"\n"; ( O, m2 H8 Y( F3 [9 i} 6 x* z1 s5 I' K7 D////////////////// " z& M0 w9 q$ j" }void Result()$ h0 d, h1 r5 D8 [9 n4 K {/ c- w, W4 C' I+ D, d int i;; U5 {/ {5 t& W# X: E" z: Y5 Z; \ cout<<"("; 1 L( t9 r' Z& q9 W3 p3 v for(i=0;i<s;i++)" V& _8 R! ~2 B4 [' w% Z$ R cout<<x; % r+ R$ q& B; j% s6 M! m cout<<")";) X* f* s- Q) c( R if(type==1)8 ]$ j. o3 O1 ~$ E$ [ cout<<"Zmax="<<matrix[n];2 u! J) g' l S: Q7 J else cout<<"Zmin="<<matrix[n];2 B1 D, i$ u1 d: D }0 i- v5 o% \) V+ W& F; h& A" }) a2 A //////////////////////4 N% E! j% t7 z2 i void PrintResult(): P2 h4 P% r- {5 h! _! L$ F { 4 @9 f" Z* G# N if(type==0)9 A- k, E8 s: [7 O7 g7 d, S) W cout<<"the Minimal:"<<matrix[n]; 7 t6 M/ z% V. T8 H, G else cout<<"theMaximum:"<<matrix[n]; 7 U! n9 _8 t5 u} : k. C1 q. H1 G* N7 d G//////////////////////////////// . H. u" Z* w {$ l, |" R1 H6 z) |7 avoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并& s2 @! L- L6 T0 R1 c {3 F* W' I3 F+ b' t: d! e* c5 v int i,j;) D/ ]: n, V$ f: ~ for(i=0;i<n;i++) 7 X6 Z6 O. r! A+ G- |& n {) i" n% ?% Q u4 n: d for(j=m;j<m+indexe;j++)/ f4 I) b! a7 a6 q3 O3 U7 T5 p/ b if(nget[j-m]!=-1)matrix[j]=0;& O ^ z9 Z* w" d" w else matrix[j]=-1;% |& g, X& n1 b, @ for(j=m+indexe;j<m+indexe+indexl;j++)9 e7 v- W0 N2 x- x+ u- D if(nlet[j-m-indexe]!=1)matrix[j]=0;& p0 z( a; S8 B) V f+ F, \ else matrix[j]=1;2 N. {" h$ s6 h6 G" ?& ^2 t/ T for(j=m+indexe+indexl;j<s;j++)! P9 V$ g+ y L. y' p y if(net[j-m-indexe-indexl]!=1)matrix[j]=0; \8 e5 t) `. [) W& E4 h j else matrix[j]=1;: W, ?6 _4 l4 h" p }7 W) Z$ K, t% n- ^0 k! S2 ]# f5 A for(i=m;i<m+indexe+indexl;i++) 4 J& y: O D$ I, J% G matrix[n]=0;/ `" p( o& p7 P# H' f& B* T for(i=m+indexe+indexl;i<s;i++) |& @' }% t, V/ \! J matrix[n]=100; , ^- O8 i/ Z2 M1 R matrix[n]~~=0; * ~8 u* G- `# @}~~
2 S+ F, b. n3 G
/////////////////////////// t' H9 F+ K+ cvoid ProcessA()//初始a[]# K- L' @* |) c y3 M {: d8 R& `) X9 H* Q9 K int i;+ T! L# I6 I8 s+ S for(i=0;i<m+indexe;i++)3 G6 N! g: n& V' M; y a=0; H& l: @0 P, p) ? for(i=m+indexe;i<s;i++) 6 n# `2 X7 S7 k5 M% @( L a=1; $ y8 r' B* ? p% A}
& u1 A& Y0 D3 w, e5 l5 m$ y
////////////////////////////////- X, I# U# `: N1 l3 y3 O void Input(float b[],int code[])' D" Y) L- J9 ?" _: L4 m2 t5 a0 E { ) A1 N: v3 L5 {1 s. S! j int i=0;int j=0;- M, B& V6 n: K2 S cout<<"The equator variable and Restrictor\n";- r" H" R2 U# H& P+ x w cin>>m>>n;6 y' [; @5 U( R( M for(i=0;i<n;i++) 3 Z, q) A" i; t9 M: P {3 L) W2 q0 Z2 L6 } g* H$ M cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; : d3 K6 }; D I! ^. X, M7 o cin>>b>>code; % z" [6 N4 n$ l' p' f cout<<"The 系数 \n";% [2 N) K7 L2 Z4 i+ m for(i=0;j<m;j++) ! ]7 ?- {' ?# h1 ?3 j cin>>matrix[j];0 W: [4 w% J0 U# {% ^8 p0 n }# F7 J5 U$ |0 Z. I cout<<"the type 0:Min 1:max\n";0 U' `* V+ |/ M8 o% [' ~& r do{% s+ @- p$ N' e, s7 {# ^7 n cin>>type;& J/ W+ F2 G4 Y/ }0 O* Q if(type!=0&&type!=1)9 _# W- b. i/ h% y4 o0 m cout<<"error,ReInput!\n"; 3 u8 K0 x" d6 \ }while(type!=0&&type!=1);* {, J# }" \" M) C/ B cout<<"the Z\n";: c3 @8 \' A- c for(i=0;i<m;i++), ?( R2 a3 ^# u( g cin>>matrix[n];6 J w z. d* N3 t if(type==1) ; c1 M* R7 T! f4 s T" I# ]3 R3 ? for(i=0;i<m;i++) 6 K) L! L4 [; y5 B3 T! z matrix[n]=-matrix[n];8 F; P. [0 K& t" q }
a/ L5 j2 O" `+ O6 W: u, X
2 H6 w C% M$ F! ^, s5 b. l1 S0 {////////////////// " J% k6 w. S$ r* T, _void Xartificial()//消去人工变量" ^/ J: m1 ]2 f, r l2 f" }" @ { 9 V5 W# t1 L; n2 s4 G. h$ d( c int i,j,k; + z* ^1 O- K. Q3 o! q if(indexg!=0); W" \2 A! D b5 S$ P/ K) E. d9 Z9 f {5 p6 C! f2 x5 B/ o0 E" H' t q for(i=m+indexe+indexl;i<s;i++). f. ]. l6 |3 G0 N2 i$ K3 i {4 E9 J# D7 C/ {9 b1 ~/ n for(j=0;j<n;j++). w; O4 D V' Y. R if(matrix[j]==1)9 h, C, V6 |0 ]+ ^3 z) ~ {: Y1 t8 Y* y& v0 f4 T. s3 a3 l for(k=0;k<=s;k++)! w4 v$ B# B4 O matrix[n][k]=matrix[n][k]-matrix[j][k]*100; - {1 o0 W. v' d& j. { j=n; & D' k* v$ i6 Z' h2 c& s' _ } , ?# k- ^( n) C; m" j Q }+ a3 H$ [: J" L' T } 3 E! t4 f/ o6 j}
; K/ |; U$ z* E7 J) D3 b& o
//////////////////////////////////////////////// . J! |8 l( `! c3 {void Process(float c[][100],int row,int vol) q6 K! u: i! Y9 E8 B! [ {4 n! C6 K$ C% T' ^8 p9 R int i; 5 J% T1 f+ e! r. m/ K0 [9 ?0 ` for(i=0;i<n;i++) / n9 A2 w1 R9 ?: m" i% {( { if(i!=row)c[vol]=0; - Z8 \ p9 G; v" F' F6 t9 Q* p4 X} " L+ N8 M# r; f* Z////////////////////// * D4 u; T3 s) `- _* [2 p) ^& L# Z. Xvoid Start(float b[],int code[]) 4 @& |( [) U3 `3 f2 A0 a{7 r/ D9 v" H( ]( P% h0 a1 Y$ X% d& d int i; 0 j3 q5 z! F( Q7 r( Y- j float nget[100][100],nlet[100][100],net[100][100];0 Z* T6 P @' f2 M* i indexe=indexl=indexg=0;3 W. F$ c3 D* S+ W+ U7 o for(i=0;i<n;i++) 3 g1 E9 I+ F2 x |! F( V {0 {# u# T# {" T. X7 w7 B2 i: |4 y if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}! r/ ]# B9 R5 z1 e- m+ b$ `3 T, h/ [ if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} # r- `' J8 } w- s- y) Y+ ?' { if(code==2){, {; u+ {+ K y7 U( \ net[indexg++]=1;1 a3 }# G' T t; m nget[indexe++]=-1; * v; J; l0 ]. ~- ~3 }2 I0 I/ E Process(net,i,indexg-1)rocess(nlet,i,indexe-1); & N0 e9 C5 i2 @7 k) R7 n$ c' s }$ T8 _4 b, F% n1 V, q } , A d& B1 P! i' ]) U7 I$ l4 F s=indexe+indexl+indexg+m; 2 D6 S1 X2 O* j# `+ H; m Merge(nget,nlet,net,b);9 s( B# d1 {# U6 V; L ProcessA(); 9 a, b+ F3 R8 X* k0 ]; o% ` InitPrint(); * ~7 m5 m" ^! n1 w7 O! } Xartificial(); - _5 ^& G9 K* `}
/ q! i; {# O. |
void Simplix()//单纯形法* j% \. |- Q4 r: Q1 _ { 0 d" D4 U' B ?5 j* _" x int in,out,temp=0; ! O; I- |) Y C while(1)/ q: d6 J2 d8 `$ Z; [+ \+ G {! ?, ]1 ^4 P6 G. t i% y. ?2 u jckxj();1 J, p( ?; I# K Print(); . B! N& ?; s% z. m; p0 O8 x- u Result();8 `, g4 d T- I/ U) Z5 K- ` if(!rj()) in=Min(); : u1 \9 N: W% X3 `- r else{ ; Z6 U+ R5 @' i5 S i% x/ u6 X if(indexg!=0)4 V) F7 e0 A6 ]' h, v% v3 D3 J JustArtificial(); 2 l* h% {; ?! d7 u: l% g PrintResult();3 ]- b9 A. o, m' f return;& y$ \% R7 z5 l V: F }' x& a, H0 h3 e" g5 _* b ` if(Check(in)) 7 A9 M; X2 N8 L' p! J3 W$ c: i9 ~ { $ t( r% ~) V$ M: `2 z# U cout<<"No Delimition\n"; / T; T: ~$ v, z' P9 `) ?% P return;1 p( j) j' u) Y } 6 z0 N$ Y; Z8 c6 X- o- V out=SearchOut(&temp,in);* _5 D4 b" D, o4 o Mto(in,temp); " |4 ~) Z1 t, K6 ]* ]7 V Be(temp,in);8 U0 |0 J1 E! O8 S1 |+ q2 N' c5 V' K Achange(in,out);4 A- n7 H0 G( M& d* @( S } 7 f% w) S8 Y) x2 n! a% G8 z" q" m# J0 E}
1 C. Q* ^2 V- E( G+ G9 M6 f! t
void main() ; h8 H0 N% S& C7 y- g0 t2 U{: f0 E. U" }- r& C) |! _3 | int code[100];//输入符号标记/ Q# _. j* i$ V6 O1 c float b[100];: P1 E% M* A, T" W) L* [3 ^ Input(b,code);//初始化# N! ?3 M% F( U% F$ F Start(b,code);//标准化行) a5 G2 U8 k9 p; _3 [7 v) l. T Simplix();/ l- { G: M! O6 A* ? y }. ? Q1 E! J* L+ ~, I& _ o5 N2 e/ }