数学建模社区-数学中国
标题: 单纯形算法程序 [打印本页]
作者: zhyi 时间: 2005-4-18 21:45
标题: 单纯形算法程序
单纯形法程序，在VC++6.0 下测试通过！ - `5 u9 M2 X5 ]
q( {9 x0 C* ^0 D- @# u- w! b
9 u1 l- @# t7 B! _#include<iostream.h>
2 d" `' {) v; `' c% e#include<math.h>- E& N+ }% r- m" N
float matrix[100][100],x[100];9 B1 K. @0 W, O4 L, n) g; C0 N7 Z
int a[100];
A# L2 Q9 w+ q/ vint m,n,s,type;
: g% }8 a9 f: c5 ?! R; S* Lint indexe,indexl,indexg;
& O3 G+ B0 @2 Z, H7 n* r4 c0 G* O/////////////////////////////////; ]( Z6 J: }# R
void jckxj()//基础可行解
' R# p/ P8 G* L" r{
: t) n* H2 ?, }) B5 X+ X int i,j;
) z5 f6 m) x! l. ]* i for(i=0;i<n;i++)7 |3 e8 q& x/ t! \8 k. X
for(j=0;j<s;j++)
4 a R3 G6 f" A6 ^! v& h4 \7 J* l if(matrix[j]==1&&a[j]==1)8 S' j9 Y7 X# @, F: P
{
$ x: j7 z/ ~) q, L3 Q" ? a x[j]=matrix;( A; w, r I' T D
j=s;( k! e- S: G* \5 ?* m
}9 ^. j) r! ^ w" F" {+ N& B* E
for(i=0;i<s;i++)
8 D- F# V, {$ F0 ~! _ if(a==0)x=0;
! z% K& c- A" e9 S5 Y}
+ `) x4 a1 {' V
int rj()//基解矩阵
* w0 Y- m4 _1 F* U5 A, D{
7 X$ y6 m X, _6 t3 c int i;2 C3 A6 C8 O# W k; v
for(i=0;i<s;i++)
2 E; c: m' R L& e; t. H [: I if(fabs(matrix[n])>=0.000001)6 s( U8 }8 r+ V/ N$ h
if(matrix[n]<0)return 0;' ^9 s. K8 b& X8 m5 }/ P' X
return 1;. z% q" ?6 i. l# Q
}6 g- d9 D. b$ c6 a( t; W
int Min()//求最小的2 |* W1 N( \# w1 g4 @
{
' l# A( U) f6 \3 U5 [; a+ W int i,temp=0;7 L4 W& [# `; X
float min=matrix[n][0];+ z L5 p8 q4 i+ A' _( u [
for(i=1;i<s;i++)
, R% L. i3 X6 Q0 Z, u if(min>matrix[n])
* F; t& r) p1 u {) _1 F! z0 o* y* A8 A
min=matrix[n];
2 c- F# N( v. d3 g temp=i;
- H3 \, e( z3 c3 x }
( U6 @) g |2 D1 r return temp;! y& H3 i) B! z3 w* O) r
}4 S' N4 A: G0 p4 ~+ x
/////////////////////////////////9 _% n/ G3 j0 Z! _, [' q+ E2 U5 Z, J
void JustArtificial()//人工变量
+ c/ |6 J' l, q+ F4 H6 _2 M6 j{1 ^9 y6 ]* z. ]6 @5 N
int i;
: w, J. `$ @0 y for(i=m+indexe+indexl;i<s;i++)) U L) K @7 h
if(fabs(x)>=0.000001)- g2 N [$ R, I8 @" H; P* Z
{* \4 ?0 v1 x: m1 R' q
cout<<"NO Answer\n";/ H3 K) d( p8 G0 T9 ]/ K3 Y
return;
7 H; o( T. D: Q" C4 y }
% b; E" T" N6 C o( m: P& g}
; h) q) _7 S/ C) ^+ `: n2 x' J" j3 w/////////////////////
; |3 e& E7 u5 b* A: W S" lint Check(int in)//检验
2 O' @+ G$ `* ]: G' ]{
3 [) j0 J/ |# D! m int i; q+ u: A" Y7 U& ^2 k5 p
float maxl=-1;0 c, g' [; d9 Y* \3 ^( s! ~
for(i=0;i<n;i++)% K+ m& q( p s
if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])
+ h2 o9 h) m, Y. P maxl=matrix/matrix[in];/ }9 y4 g, t8 i, x, f* i, C
if(maxl<0)" D& a8 j/ r4 s$ F
return 1;
* i; B D) E' w+ d return 0; _. o! `4 m1 v+ b5 V9 j; h
}& B3 v5 c) [+ k( z
int SearchOut(int *temp,int in)//出基变量( |3 O& l6 s; P$ K/ ~# f
{) e2 Y3 S3 J: A; b$ x
int i;1 q4 Y9 H' K' `( A
float min=10000;8 Q2 F/ u$ G" s# ?
for(i=0;i<n;i++), K8 A. y0 j) d' B1 \8 `5 @
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)
5 ?1 G' @+ Z1 z ]: a. w &&min>matrix/matrix[in])7 e3 j; n7 v8 I5 e( n# ^2 s Q* \
{$ |; G; W4 t5 m) e9 B
min=matrix/matrix[in];
! H1 C- ]6 A* v. Y+ l0 E* ] *temp=i;
) |! g! @5 f2 }2 `/ Y1 m- F }+ y, }7 a+ J1 a1 ^* s- _
for(i=0;i<s;i++)
* J# @! J7 f/ j& m! J" }$ Y) t if(a=1&&matrix[*temp]==1)0 \0 R% Q7 h& n
return i;$ z" a; T$ |2 D
}
g' F% o' a e4 g w/////////////////////////////////- _5 _4 G0 Z( c0 X
void Mto(int in,int temp)- D! B3 t. P7 C# Q5 M" U8 h5 `
{
+ K1 p8 _/ k' R _& ~ int i;
6 q1 J6 I S- d3 [- B. x7 s for(i=0;i<=s;i++)
7 q! o: ]4 s; e4 M: [ if(i!=in)
& G8 s- b$ F# b' r @( R matrix[temp]=matrix[temp]/matrix[temp][in]; p% I+ a3 E7 R
matrix[temp][in]=1;
; K9 I; E. G4 [1 y}- _3 Q* v, D; t
/////////////////////////////' ~1 d2 @! p9 x7 h. M
void Be(int temp,int in)//初等变换4 z; l, u/ [) k( d6 u9 O5 n
{
6 z" R' _ o+ ~2 E int i,j;
) E) k3 \9 j8 } float c;
8 y. c* v- ^! Q* h for(i=0;i<=n;i++)
5 {% E; N: G8 N( a* ? {
# [! }/ E# H, K1 c. q c=matrix[in]/matrix[temp][in];. l$ D# F$ K1 x6 O x3 _
if(i!=temp)
$ F* Y3 f- o; k for(j=0;j<=s;j++)# `( ?. H# D* p0 W
matrix[j]=matrix[j]-matrix[temp][j]*c;
" k7 q/ W4 s1 E# \6 ~+ T }. K5 |- ^4 c6 t4 H, z5 m
}
* B+ E7 k! Q# Q2 G" S" a//////////////////////////; w6 ~ A4 o) }9 y/ g3 o% A+ E
void Achange(int in,int out)//出基入基转换+ z; m; A& C5 \# Y
{. U7 _+ f5 A" y7 o& S
int temp=a[in];5 z( \3 L0 W4 [: V9 k
a[in]=a[out];
Q" `" D2 Z, N7 S a[out]=temp;
9 t: ]% Y3 Z: W& b# Z% e}
* O( p2 _- l- ?////////////////////////; O: g: E9 C& r/ Z: q. l; y( e
void Print()! F% n# V3 j1 T/ Q- b' e
{
, U; t1 S! E( G/ f" J. P int i,j,k,temp=0;4 o/ c( R3 o% r A" [" Q0 o4 |5 o
for(i=0;i<n;i++)
6 d: |. A- N9 {$ O {; u- ]$ V; U# Z4 O% P
for(k=temp;k<s;k++), m0 w! c% D% |! l6 z
if(a[k]==1)
7 S; L [, g1 A' S, U3 t" [ {5 w. f5 n4 F7 R2 [ i" y1 x2 m
cout<<k;& B; O: m: Y% M% `# L7 \, n7 P
temp=k+1;
Y$ A5 K* G% Y: ~ k=s;9 U* H8 R4 \% [; c# s
}% N U I+ j5 `* I: S" L
for(j=0;j<=s;j++)
3 j8 v3 z* t: S* e1 F. @ cout<<matrix[j];) \9 [3 [. L$ W2 K/ T& H. ~2 }# M
cout<<"\n";
; I& n8 M4 ?9 ^$ c& T }
Y1 o% @; c! C5 ~8 U8 u cout<<"Rj";! ^- W M, j7 K1 \5 {( s2 X9 {
for(j=0;j<=s;j++)% D1 S7 n1 V7 s* @; f9 \4 n
cout<<matrix[n][j];
0 r. ?; E& |4 l) r/ Y4 A cout<<"\n";, a1 B! a, m. r+ M/ e D$ {
}
" W2 M8 a+ ?" k* B# H, g" D8 h////////////////////////
- P' ]: t, m! l) uvoid InitPrint()
; I) `, ]1 S& P$ F* r1 E6 c{
: Z* y9 r, [9 o; P" e) { int i;6 k$ w4 z9 j, k1 L8 J
cout<<"X";/ }- H6 a8 S0 ~
for(i=0;i<s;i++)# ?/ M9 B; e0 E; e
cout<<i;2 e6 |( R/ ~& ^7 \* R4 }0 Y
cout<<"b\n";# g8 i4 E( f( d5 h
cout<<" ";
5 s! v5 ?- t* @; g' v cout<<"\n";9 u+ g: Y1 R4 y2 B* b [
}0 f% `4 G* R/ Q& W) D
//////////////////& L# N q1 @+ o; A' C2 u& I' ~: `% R
void Result()2 M' e4 }; R- a# A
{
% e' a3 t( d- K' q int i;$ Z9 S! J1 Q( Q
cout<<"(";, }7 Q8 o- G5 P7 E5 c/ F$ F
for(i=0;i<s;i++)! c6 S3 U# {3 c: R \
cout<<x;
' W% Y0 p. z6 | cout<<")";
: i. y$ G5 ^- B! {7 { if(type==1)
U* v- K6 e I% W. C1 j% c cout<<"Zmax="<<matrix[n];
) w& R5 @, V* m+ c, r else cout<<"Zmin="<<matrix[n];9 Y1 e' o2 p& A. w
}
- b* I( p" _: r! p9 m+ K7 k//////////////////////
/ q+ o2 c5 q6 U* G& ?* {& lvoid PrintResult()
/ u$ F9 K+ `* p1 m: r* x* |5 r{5 N% P/ C" O0 {/ ~
if(type==0)
( u2 Q7 [3 u' e) ]* } cout<<"the Minimal:"<<matrix[n];. Z0 |- i; V4 w0 J: Z$ S* I
else cout<<"theMaximum:"<<matrix[n];
$ @. q" W6 c9 z3 e5 E7 u}
5 @3 v* r6 I4 }////////////////////////////////. Y$ B, r& E) J; {- z
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
6 m. C5 S$ P# ~3 k{
6 n4 X# y0 B0 b' E int i,j;
4 Q. m' V8 J8 j4 J! ^ k for(i=0;i<n;i++)
2 ^8 W, u$ ?! c& d0 g {
: q, i3 ] w" F for(j=m;j<m+indexe;j++)
5 V7 m. p& w V; g* I$ t9 U! W if(nget[j-m]!=-1)matrix[j]=0;
/ ^ c% A: g: L5 ]* u else matrix[j]=-1;
+ D/ X) X/ h. r% ?5 V% V for(j=m+indexe;j<m+indexe+indexl;j++)
' y1 P8 T) q- M if(nlet[j-m-indexe]!=1)matrix[j]=0;0 j; U8 n5 F1 ?* E2 F" N
else matrix[j]=1;8 o. I4 z! n" J
for(j=m+indexe+indexl;j<s;j++)
$ q( ^7 q. g B if(net[j-m-indexe-indexl]!=1)matrix[j]=0;7 Y/ K: k8 m" K7 z) S1 {
else matrix[j]=1;
c5 g! C. c5 y$ n/ W( f6 }, U ] }# ]' g8 e3 {0 h d. S3 Q5 S. M
for(i=m;i<m+indexe+indexl;i++)" u7 ]0 f1 [3 i) j. ?
matrix[n]=0;& [' z, W; H& c
for(i=m+indexe+indexl;i<s;i++)8 h1 E$ }% F! u5 Q6 k
matrix[n]=100;
# u* |: k- Q2 X. f3 ?0 I" C, M matrix[n]=0;( J2 [! d- R' j# P
}
8 K+ v- c. q5 a4 ^& l# S///////////////////////////
7 @. ^7 t+ H. I+ T) D, |, Tvoid ProcessA()//初始a[]
' x. s$ `: e u: W{2 H- ]3 e9 U0 V0 U$ @
int i;
b; m( z3 x+ x! d, r1 r3 w for(i=0;i<m+indexe;i++)# R+ x/ L) v: B4 l* w7 L
a=0;( k) I( T# v1 M; k0 g
for(i=m+indexe;i<s;i++)7 l* A7 T6 [# J* H
a=1;
" X8 M6 o/ N$ |4 p; W. m3 y+ W}
3 }3 ]5 g7 O3 p: L////////////////////////////////+ Q: l% {4 V; C3 l4 z% N4 o
void Input(float b[],int code[])
) ?4 ]# X& ? U' d{5 q" k2 e4 V; @4 C0 r+ {
int i=0;int j=0;) L' `% }" ~, q9 M; v9 z3 x
cout<<"The equator variable and Restrictor\n";
6 E4 q% I4 H* R! E7 i cin>>m>>n;
" {' g4 m* f4 J9 x+ d& X5 C5 m' g: v for(i=0;i<n;i++)
/ J5 r ^. Z3 e6 e {3 h- I* q! w" Z/ \! Y) I5 p. k
cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n";
@" F4 P: w. i) k' u cin>>b>>code;
. \) o6 c6 {' f1 w$ ~' C cout<<"The 系数 \n";
, e2 x5 U" Q. z0 g for(i=0;j<m;j++)8 ]" H( U0 w: B, T1 ^; C& r% W
cin>>matrix[j];2 H+ p1 F6 P" s. A7 i
}" I$ {; S+ K, \
cout<<"the type 0:Min 1:max\n";
2 s7 S7 n" @4 j+ u do{
& c! n9 O& c. N# }3 f, ?5 l3 p cin>>type;
! f% J6 m) k+ D4 \( V$ G4 i if(type!=0&&type!=1)8 x" k% w4 H4 k& z
cout<<"error,ReInput!\n";0 n# c$ b7 v6 ?7 S, z5 c; z
}while(type!=0&&type!=1);+ |* _/ s2 ^: F' c1 F0 x( b2 ?
cout<<"the Z\n";! {) W. H, W4 o% z8 {
for(i=0;i<m;i++) M$ T2 j. v0 \$ |
cin>>matrix[n];1 G5 B% H- h m/ y3 `6 z' A
if(type==1)
% M k e J) Q: f3 w( P for(i=0;i<m;i++)
% a& H% O5 _: R1 ~ matrix[n]=-matrix[n];' t) Q& Y* B" F6 f
}
: S1 z q# N% H4 a: g3 Q/ s) ^. w3 g% T- L8 n0 s0 m, y7 j, b
//////////////////
7 r7 v6 S% i+ f# M0 m4 |' w- _void Xartificial()//消去人工变量0 r% i5 e, j! H7 F. r) Y: E
{" P# Q# p' x* e) S0 W2 y/ w
int i,j,k;# \' q: _, S* r6 Y* |5 {0 }3 X
if(indexg!=0)
6 _- I+ @- c: P# X* C2 x {* p. S1 _& ^ V, `, N' e3 e
for(i=m+indexe+indexl;i<s;i++)/ z/ Y4 g" D. Q- ]9 d
{
7 m: N. H9 t5 J* e5 a" a$ p for(j=0;j<n;j++)* Y o5 B1 @" O/ A. o
if(matrix[j]==1)% T( H6 f" N+ h
{1 P+ L" m. B' ]( B$ r
for(k=0;k<=s;k++)* |+ y j6 q- w+ {( p4 P0 E. T
matrix[n][k]=matrix[n][k]-matrix[j][k]*100;
0 |+ c9 h& x" t4 {) P3 K j=n;
R/ [/ ~5 o5 O* I5 G: S }. N- B: r2 d& @: I/ L3 `3 \, N6 V7 e
}
/ @3 [) E6 r: g- O( @/ w/ a2 P }& L3 B; Y" R" P- g2 o
}
- i2 ~" w: r6 L0 F/ f+ d
////////////////////////////////////////////////5 S, S2 K# N3 p
void Process(float c[][100],int row,int vol)
+ ]0 _, ^9 ^3 K- o4 x K& K- m{
9 D% j5 r4 B# c2 i& p! J, X/ w int i;/ z% \4 M' F& `9 \) V" W5 |) P6 [
for(i=0;i<n;i++)
5 s- z3 R% O' H9 X! Y- G# c if(i!=row)c[vol]=0;
h4 E" q. Q$ C, D5 Y}
8 D: j2 P8 k( M* X//////////////////////
8 i# I2 \7 \2 Uvoid Start(float b[],int code[])
( A6 a& y, b9 U{
) a/ e, b8 ^3 \% p6 O. D int i;
+ r7 R7 h5 s- K float nget[100][100],nlet[100][100],net[100][100];$ D! i$ }$ ^" M! x3 `
indexe=indexl=indexg=0;7 A7 y5 ]5 B `, i0 F
for(i=0;i<n;i++)
& X* C( }& @5 m) r. J {6 X2 ]3 |6 u+ j2 |
if(code==0){nlet[indexl++]=1
rocess(nlet,i,indexl-1);}$ d: A! K1 H, x5 r' ^1 V* g1 ~* ~
if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}: t3 W: m& Q1 O- ^2 a
if(code==2){4 W8 t+ `' k$ _ m. z9 b/ a; Y& m$ T
net[indexg++]=1;) ]; @+ r& u5 F+ ^4 |( s5 }& K' z
nget[indexe++]=-1;
. A# Q9 c! {! \0 l! o$ k Process(net,i,indexg-1)rocess(nlet,i,indexe-1);
8 E. ]. A% H" C, P* f, ? }( [& B% i- Y _ s. f
}1 Q3 J; @9 B$ H
s=indexe+indexl+indexg+m;
3 J5 D8 }! L8 G2 U' L, C Merge(nget,nlet,net,b);( {$ y! p* O( v, g: R
ProcessA();
$ u% ^$ u9 m0 J" K/ f- P InitPrint();! O, p2 e& z9 D! \ b& _
Xartificial();
' ~, h1 A+ p5 G; h* r* }7 t! b# h}
0 @5 t& k3 d; C# X- y: j; Mvoid Simplix()//单纯形法
% a* c' F" T: x{5 u) q/ A9 ]0 y. F& F& L* R7 `
int in,out,temp=0;
2 H1 W0 s+ b8 S+ U( T) C( t7 F4 ?2 Z while(1)
/ m; k* N6 F g {
; _' Y+ g0 v; |* G2 H1 {( g5 @ jckxj();
; \/ N7 [. y D; E8 L Print();
5 D, q! Z2 v0 ?* x6 S7 J0 c4 j" T7 d$ j Result();: f3 h% x6 {% Q, K" X! i
if(!rj()) in=Min();6 S. A- y* s1 r- u
else{6 S6 Q( J' o. A: \6 `' E% i6 g, S
if(indexg!=0)
0 q6 ^+ F' Q7 j4 T7 p5 ^ G) r( M) p JustArtificial();/ N) H2 z" d8 @; ` T
PrintResult();4 n/ C5 z' `& V7 L/ _; X
return;: Q1 ^% V9 z: N, s L* v
}
; C1 ?3 S3 B; z+ b+ {5 Q if(Check(in))" K3 U c( {! ]7 S8 h
{5 r, ^% ^- {" O/ f+ X+ a
cout<<"No Delimition\n";+ V9 S, _# J! o% g
return;
Z% Q7 i* T {, Y* e* c9 w }
* ?# Q( ^5 z1 h9 [$ w out=SearchOut(&temp,in);2 ?' _4 @; P5 g+ w, Z6 ~
Mto(in,temp);
, b. v. ?: Y$ q V, x: i Be(temp,in);0 t# N; M% m; c1 |2 |1 M0 h/ X( j
Achange(in,out);
/ F. U. i1 j8 g4 d. d/ a5 |9 c% H4 B. H- Q }0 t# _2 e9 C, u
}
s& }( e- X( |& r; fvoid main()- M S6 K' ^) Z |
{
0 ]+ t4 E4 h4 k7 y int code[100];//输入符号标记
6 Y4 k4 ]! z; @$ { float b[100];
8 m& n, u# r% h5 c2 T( h Input(b,code);//初始化# t! X/ w3 V6 X4 N) K7 M8 X: A# j
Start(b,code);//标准化行
- l2 ?4 X% m8 P/ _4 B9 d Simplix();
: ?5 j1 @/ p3 I9 g' q! U; x} P* R: o" n1 B# |, z
作者: lvming 时间: 2005-4-25 22:44
谢了
作者: M_Tramp 时间: 2005-4-29 18:10
不错啊！！
作者: pangaogao 时间: 2005-5-4 00:15
Good!
作者: 那时花开 时间: 2005-6-3 22:57
好用不？
作者: 那时花开 时间: 2005-6-3 22:58
资源分配问题可以用这个程序吗？
作者: monkeytail 时间: 2005-6-10 01:42
哇，楼主强人！
作者: monkeytail 时间: 2005-6-10 01:43
单纯行算法是指数算法啊！
作者: bnulj 时间: 2005-6-11 13:14
这么长！看不懂啊。
作者: mengfanqi 时间: 2005-9-6 19:41
so well!
作者: 天亮 时间: 2005-9-17 11:45
zhyi,你好.我有一问题请你指教阿.有一个10维的有约束的函数,现在我已经有了一些可行点,其数目可能大于或者小于10,可行点之间的关系不知道,请问怎样运用单纯行法求函数的最小值.
作者: chenbilian158 时间: 2006-3-7 19:14
试试
作者: luom 时间: 2006-3-15 13:43
还有其他算法吗关于仿生算法的谢谢
作者: jixian 时间: 2006-4-16 10:42
顶
作者: 海云边缘 时间: 2006-5-5 21:44
有C語言的嗎？我要C語言的
作者: suolunga 时间: 2006-5-8 20:07
[em01][em01][em01]
作者: sfhnlgdx 时间: 2006-5-13 09:15
谢谢，我正在找这个程序，终于找到了！
作者: chz0829 时间: 2006-6-3 00:41
看不懂
作者: hustyangyang 时间: 2006-7-19 14:59
楼上的的确是位高手，这两天由于写论文要用到单纯形法的程序，就拿来用了，但是发现有些错误，没有结果或者得出的答案有问题，于是我仔细看了一下这个程序，将楼上的笔误，和一些其他的小错误改正如下，
注意： 我不是用纯 VC++ 我的输出函数用的是 printf (),这样可以动态观察结果输出，以便于修改，这个程序是我花了一天的时间改的，太长也太烦琐，我看的也不是很清楚，只对 限制条件是 <= 的情况进行了详细的察看，和修改，其他的情况就没有看了，程序中相应的部分有比较详细的注解，如果有需要可以和我联系，我们一起共同探讨。谢谢！QQ：116490942
#include<stdio.h>
#include<iostream.h>
#include<math.h>
float matrix[100][100],x[100];
int a[100];
int m,n,s,type;
int indexe,indexl,indexg;
/////////////////////////////////
void jckxj()//基础可行解
{
int i,j; //基础可行解即为 非基变量对应的x=b, 基变量对应的解为0
for(i=0;i<n;i++)
for(j=0;j<s;j++)
if(matrix[j]==1&&a[j]==1)
{
x[j]=matrix;
j=s;
}
for(i=0;i<s;i++)
if(a==0)x=0;
}
int rj()//基解矩阵
{
int i;
for(i=0;i<s;i++)
if(fabs(matrix[n])>=0.000001)
if(matrix[n]<0)return 0;
return 1;
}
int Min()//求最小的
{
int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++)
if(min>matrix[n])
{
min=matrix[n];
temp=i;
}
return temp;
}
/////////////////////////////////
void JustArtificial()//人工变量
{
int i;
for(i=m+indexe+indexl;i<s;i++)
if(fabs(x)>=0.000001)
{
cout<<"NO Answer\n";
return;
}
}
/////////////////////
int Check(int in)//检验
{
int i;
float maxl=-1;
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;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;
for(i=0;i<n;i++)
if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)
&&min>matrix/matrix[in])
{
min=matrix/matrix[in];
*temp=i;
}
for(i=0;i<s;i++)
if(a=1&&matrix[*temp]==1)
return i;
}
/////////////////////////////////
void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
if(i!=in)
matrix[temp]=matrix[temp]/matrix[temp][in];
matrix[temp][in]=1;
}
/////////////////////////////
void Be(int temp,int in)//初等变换
{
int i,j;
float c;
for(i=0;i<=n;i++)
{
c=matrix[in]/matrix[temp][in];
if(i!=temp)
for(j=0;j<=s;j++)
matrix[j]=matrix[j]-matrix[temp][j]*c;
}
}
//////////////////////////
void Achange(int in,int out)//出基入基转换
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
////////////////////////
void Print()
{
int i,j,k,temp=0;
for(i=0;i<n;i++)
{
for(k=temp;k<s;k++)
if(a[k]==1)
{
printf(" %d ",k);
temp=k+1;
k=s;
}
for(j=0;j<=s;j++)
printf( " %.0f ",matrix[j] );
printf("\n");
}
printf("Rj\n");
for(j=0;j<=s;j++)
printf(" %.0f ",matrix[n][j] );
printf("\n");
}
////////////////////////
void InitPrint()
{
int i;
printf(" X ");
for(i=0;i<s;i++)
printf(" %d ",i);
printf(" b \n" );
printf(" " );
printf("\n" );
}
//////////////////
void Result()
{
int i;
printf( "(" );
for(i=0;i<s;i++)
printf( "%.0f",x );
printf( ")" );
if(type==1)
printf("\nZmax= %.0f\n" ,matrix[n] );
else printf("\nZmin=%.0f\n", matrix[n] );
}
//////////////////////
void PrintResult()
{
if(type==0)
printf("the Minimal: %.2f\n", matrix[n] );
else
printf("the Maximum: %.2f\n", matrix[n] );
}
////////////////////////////////
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
{
//置成我们需要的矩阵，最后一列置成0
// 1 2 1 0 0 0
// 4 0 0 1 0 0
// 0 4 0 0 1 0
//-2 -3 0 0 0 0
int i,j;
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;
for(j=m+indexe;j<m+indexe+indexl;j++)
if(nlet[j-m-indexe]!=1)matrix[j]=0;
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;
}
for(i=m;i<m+indexe+indexl;i++) //将目标函数中人工变量的系数补为0
matrix[n]=0;
for(i=m+indexe+indexl;i<s;i++)
matrix[n]=100; //置成M
for(i=0;i<n;i++) //把b[]的值赋给matrix
matrix=b;
matrix[n]=0;
}
///////////////////////////
void ProcessA()//初始a[] a[]是标记基变量，若为基变量则为0，若为非基变量则为1
{
int i;
for(i=0;i<m+indexe;i++)
a=0;
for(i=m+indexe;i<s;i++)
a=1;
}
////////////////////////////////
void Input(float b[],int code[])
{
int i=0;int j=0;
cout<<"The equator variable and Restrictor\n";
cin>>m>>n;
for(i=0;i<n;i++)
{
cout<<"Inputb[] and Restrictor code 0:<= 1:= 2:>=\n";//输入b[]和限制符号 <= ,= ,>=
cin>>b>>code; //分别输入到b 和 code 中
cout<<"The 系数 \n"; //提示输入每个限制条件的系数
for(j=0;j<m;j++)
cin>>matrix[j];
}
cout<<"the type 0:Min 1:max\n";//输入要求是类型极大还是极小 0:Min 1:max
do{
cin>>type;
if(type!=0&&type!=1)
cout<<"error,ReInput!\n";
}while(type!=0&&type!=1);
cout<<"the Z\n";
for(i=0;i<m;i++)
cin>>matrix[n];
if(type==1) //如果是求极大，把它转化为极小来做，系数全部反号
for(i=0;i<m;i++)
matrix[n]=-matrix[n];
}
//////////////////
void Xartificial()//消去人工变量
{
int i,j,k;
if(indexg!=0)
{
for(i=m+indexe+indexl;i<s;i++)
{
for(j=0;j<n;j++)
if(matrix[j]==1)
{
for(k=0;k<=s;k++)
matrix[n][k]=matrix[n][k]-matrix[j][k]*100;
j=n;
}
}
}
}
////////////////////////////////////////////////
void Process(float c[][100],int row,int vol)
{
int i;
for(i=0;i<n;i++) //i =0 时置第一列为 1 0 0 i=1 时置第2列为 0 1 0
if(i!=row)c[vol]=0;
}
//////////////////////
void Start(float b[],int code[])
{
int i;
float nget[100][100],nlet[100][100],net[100][100];
indexe=indexl=indexg=0; //indexl 表示松弛变量数 indexg 表示人工变量数， indexe表示减去的松弛变量数
for(i=0;i<n;i++)
{
if(code==0) //如果是<=
{
nlet[indexl++]=1; //松弛变量数+1 且置成相应的标记
rocess(nlet,i,indexl-1);//传 net, 行号，indexl-1 过去
}
if(code==1)
{
net[indexg++]=1; //人工变量数+1且置成相应的标记
rocess(net,i,indexg-1); //将刚加入的列单位化
}
if(code==2)
{
net[indexg++]=1; //人工变量数+1 且置成相应的标记
nget[indexe++]=-1; //剩余变量数+1 且置成相应的标记
Process(net,i,indexg-1)rocess(nlet,i,indexe-1);
}
}
s=indexe+indexl+indexg+m; //变量总个数
Merge(nget,nlet,net,b);
rocessA();
InitPrint();
Xartificial();
}
void Simplix()//单纯形法
{
int in,out,temp=0;
while(1)
{
jckxj();
rint();
Result();
if(!rj()) in=Min();
else
{
if(indexg!=0)
JustArtificial();
rintResult();
return;
}
if(Check(in))
{
cout<<"No Delimition\n";
return;
}
out=SearchOut(&temp,in);
Mto(in,temp);
Be(temp,in);
Achange(in,out);
}
}
void main()
{
int code[100];//输入符号标记
float b[100];
Input(b,code);//初始化
Start(b,code);//标准化行
Simplix();
}
/*模拟输入数据
max z=2 x1 + 3 x2
s.t {
x1 + 2 x2 <=8
4 x1 <=16
4 x2<=12
x1,x2>=0
}
2 3 8 0 1 2 16 0 4 0 12 0 0 4
*/
作者: 999mmg 时间: 2006-11-3 13:55
呵呵 绝对的好东西 我喜欢
作者: hnus31 时间: 2006-11-11 09:46
不错呀
作者: pytff7 时间: 2006-11-18 15:45
hai a
作者: echo5183 时间: 2006-12-4 12:19
好
作者: jkkjk 时间: 2009-2-14 04:34
这么长！看不懂啊。
作者: aruisi 时间: 2009-4-4 16:31
我眼睛好花啊！
作者: Kadyniost 时间: 2009-8-10 00:26
。。。。。。。。。。。。。。。。
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |