数学建模社区-数学中国
标题: 单纯形算法程序 [打印本页]
作者: zhyi 时间: 2005-4-18 21:45
标题: 单纯形算法程序
单纯形法程序，在VC++6.0 下测试通过！ : m9 a5 t2 e# k5 Y# A a
5 Z& H# d5 `- ?
2 t% k; Z2 c- o+ ?, i; X6 h$ _, p
#include<iostream.h>' @+ j% I% `" @& e3 D5 [9 Y$ K
#include<math.h>
" w6 C9 P0 R" A1 Y( b0 x$ Rfloat matrix[100][100],x[100];& h& o7 H2 P+ x/ A( ?
int a[100];; z1 T; b$ \1 ]* s' C
int m,n,s,type;9 t1 t5 r: l& d
int indexe,indexl,indexg;
2 T* X9 q; c$ c) e( a3 z/////////////////////////////////
5 E# x8 v% g9 ]7 {- Cvoid jckxj()//基础可行解" q! Y' |" e/ B" a" h w
{
- k ^4 ^# `; c% P( j) ` int i,j;" h$ M) Q s! T y
for(i=0;i<n;i++)7 @* R8 c* ~! q6 R0 e
for(j=0;j<s;j++)
: F Q- Z5 W: b# Z if(matrix[j]==1&&a[j]==1)
2 W: E: K: U* H# A {
9 b, f3 W+ _9 c x[j]=matrix;8 f! w' s4 e7 H, r1 u8 R
j=s;& [) M9 k+ O. i2 M5 G
}5 f0 O, t, a4 M0 N7 P. @* h
for(i=0;i<s;i++)/ m; a0 ?1 P1 g! c5 `; X/ f+ F; Y
if(a==0)x=0;
" t' }# S; f. N# F6 Z0 \5 {+ D}
0 j+ E! H# t, s# I4 Lint rj()//基解矩阵! Q/ z+ `8 Q+ f7 g1 Z
{) p! n( i, e& ^8 i$ f
int i;
8 t1 L& s% c- G5 ^( M8 ` for(i=0;i<s;i++)
6 U9 U: `8 [ h5 a if(fabs(matrix[n])>=0.000001), a5 }& ]# P/ g* A$ S8 Q0 R
if(matrix[n]<0)return 0;
/ z5 P+ V0 \/ c: ^; Z return 1;) q, p" @9 e/ R* o. x7 c j0 E
}5 `3 q# f$ b" B; O6 o
int Min()//求最小的$ k5 X( x9 S. i, |7 N" k5 }
{
- t- @% @' p% o int i,temp=0;1 B! `* m- V1 h/ M# r6 q
float min=matrix[n][0];, P& }' T% i5 O/ h9 l' y3 D( b% e a
for(i=1;i<s;i++)
- k8 d, K# Y1 I, O! r) f. @ if(min>matrix[n])
: V4 s2 x$ y1 O {
. V5 d( e4 \ H( e5 f min=matrix[n];
; j' |. {# f# ~7 x/ y temp=i;
0 q. |5 f3 o0 R$ {2 \+ v4 ? }
- u* Z1 E# c( Q0 B return temp;# j1 e. y i: j# H+ K, ?
}% q5 x2 A, \9 B& G
/////////////////////////////////
/ D. j9 c0 K9 h, ^1 Y2 Z2 L" Jvoid JustArtificial()//人工变量
; K: P5 K0 ], P( }# C( T{/ N }* l( \) a* H
int i;1 T. T- ~% E" b& a% I
for(i=m+indexe+indexl;i<s;i++); W) x% I2 u$ e5 Q
if(fabs(x)>=0.000001)
: Y' W$ w2 Z7 D2 W, u2 q' j, W+ S$ G {
8 m( {5 y# O0 j6 P" m; w5 B cout<<"NO Answer\n";* y2 a6 A3 i5 |+ m: R: V- L
return;
3 l+ O ] |+ _+ E0 F }
; L( g( f& J5 i9 H! q( K}/ D5 p8 ^: V0 {
/////////////////////
) R, ?8 [# u2 Qint Check(int in)//检验" V; y7 w: K$ ?, E+ E
{+ O1 ^3 G. ~" v) k: c
int i;6 I' p4 ~6 _ {0 V' `
float maxl=-1;
6 W4 T/ S `% `3 Z- w I for(i=0;i<n;i++)
, [9 }9 ?0 R6 T( A4 O' G& i if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in]). y( h P; i$ \7 l+ w& b& g' f
maxl=matrix/matrix[in];* l) y" S9 @. W5 C. J O3 d
if(maxl<0)
. ?1 e2 Q) S& A" a. {' T/ v$ D o return 1;. i4 i F2 S" O& e
return 0;
" ?# K- H* T* ^/ P}
& q" M1 r4 q7 r" A- L2 @6 xint SearchOut(int *temp,int in)//出基变量% V. D. n" A$ w7 v) f
{+ p! \7 _; f& k6 h6 g5 T
int i;, q+ R8 H0 y# x0 w$ \
float min=10000;% Q) Z$ c) a s5 D% x
for(i=0;i<n;i++)
# F5 r: Z& b, V4 Q$ [0 A V/ { if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0)2 N. h6 ]" D4 v; s3 B
&&min>matrix/matrix[in]); ]6 o% E2 P6 k8 Q) | f3 g
{9 w: a+ i3 [& H$ J% L% B+ l; b
min=matrix/matrix[in];
% D4 @) h; ?1 o5 s9 C7 D& C- i* Y *temp=i;8 @# n1 N" x+ f1 G% X) m
}4 A! |9 V' k1 {1 |2 W6 Q! n
for(i=0;i<s;i++)
- m. R/ k$ F& T: U* L* t0 A# I if(a=1&&matrix[*temp]==1)
$ X3 t, h) m. J5 ]" O% I: O return i;
( w: ?. c2 ^! w7 [4 q5 l+ H" c2 W! y8 _}
3 w& }6 V6 n4 Q. Y/////////////////////////////////( ]" i( ]$ _, p8 c' v2 m8 a
void Mto(int in,int temp)& G* e, F) [. D! g$ R% m
{& [5 i% r& n0 I E" `
int i;
! c/ D3 ] B9 G x3 j' I5 T) r for(i=0;i<=s;i++); ^ O% i% E% e" `, [
if(i!=in)
" ~, o7 V$ G2 P$ a2 c/ c; g: S matrix[temp]=matrix[temp]/matrix[temp][in];
! |- j2 u6 E; S7 p4 U( j! m matrix[temp][in]=1;$ w" m* Z4 f9 e& w" z( f
}; m9 ], {( ~9 k) }+ q
/////////////////////////////
+ ? a. T& Q3 }void Be(int temp,int in)//初等变换
) \# K# H' b* f: A8 w' L, _9 d! @{9 k& h( R! y7 d$ N' a- B- C
int i,j;
% B6 F: {& } N" r3 |2 X$ I float c;7 N; F; T {/ G/ E+ _. z$ l
for(i=0;i<=n;i++); F: a+ K, x7 {2 w! S8 b
{
! l. ], H; c9 |6 a' f c=matrix[in]/matrix[temp][in];) U$ Q" L$ Y* G7 t
if(i!=temp)7 A- g2 r8 I0 {; e( y5 g: w. ^6 v- i
for(j=0;j<=s;j++)$ Z) E/ {8 g# b
matrix[j]=matrix[j]-matrix[temp][j]*c;$ _' \) M N) t9 G" F+ g6 f8 Q5 w8 D
}. z6 G" Y V# O9 Y
}
! p6 P7 Q5 }) Y. A/ i$ A |//////////////////////////7 d) o% z: Z1 L& `7 B* n ~9 D9 R
void Achange(int in,int out)//出基入基转换
; k6 ]/ ]2 M6 h& p/ c2 }{ H# N3 {, I' Z) N7 U. |
int temp=a[in];* Y' R/ Z# @' @
a[in]=a[out];
7 Y3 P1 }9 y U5 p5 b a[out]=temp;8 x. Z d; B: w6 [, {. L
}! T2 N6 q$ r y5 D# A G% }
////////////////////////
7 L) S) p/ M- ?8 ]$ f4 U' ]void Print()+ Y) q8 u9 x! `( j) Q
{
& b0 H1 B, l% ^; C, t int i,j,k,temp=0;0 Z5 G* X+ e; x# O1 D
for(i=0;i<n;i++), o$ } e/ u! |# H
{% x( i" U+ {' S/ T5 a' p, g
for(k=temp;k<s;k++)8 i, g5 [: ?6 Q3 L
if(a[k]==1)
' w1 I/ T6 E5 u1 h# i. | {
; _) O: k# l) g1 Q; ^% u cout<<k;1 o A( `0 N: v$ ]3 J
temp=k+1;( t" w* g$ I) M3 C
k=s;
5 p) x/ s& o' q }
0 b4 v0 M. y& h: w t5 T0 ? for(j=0;j<=s;j++)
8 k5 G8 b8 R$ f" ] cout<<matrix[j];$ H; w1 l" s1 w+ L7 ?7 H- ]
cout<<"\n";
0 r& N6 K" Z) T5 F3 { }
3 N5 Z' C! K( V" u cout<<"Rj";
1 p, [9 Q3 y/ _- ^$ R9 ` for(j=0;j<=s;j++): p Q9 s; L: C3 h @
cout<<matrix[n][j];
6 v9 F4 D* U# i) {0 O5 m H cout<<"\n";
) d% W) B* s2 o" p% P}8 Q5 m' m$ S! s. i' W6 U4 m
////////////////////////
- {: y! m5 d4 \, C$ w3 Wvoid InitPrint()
5 L/ R6 Q# K3 T8 D, }{
4 n- M( L- }% B& s" O& n4 l int i;
0 l6 D `& K4 C6 x L, W- { cout<<"X";
* E3 r, e g' t' l for(i=0;i<s;i++)- Y) o* m2 ?' E
cout<<i;5 [3 [- V2 q/ S4 p8 f: [! M* }* J
cout<<"b\n";: m( F9 r# |+ ]0 A" f0 }0 L- ^# X$ M
cout<<" ";. X- K3 g; q2 M' N( W) ]# M- t
cout<<"\n";
" n8 l* S7 J6 \& l$ m}
- e/ w0 b% d. d A//////////////////4 S; Q X' e W' b$ v; Y9 N
void Result(). X5 {, [- ~2 k4 W. Y
{, Q3 G$ T( @! r$ Y
int i;
; \+ ~( E% g: t5 K; F cout<<"(";- s. T- |# T, P* G9 t
for(i=0;i<s;i++)
& f% B9 q4 t$ w cout<<x;
; }" A8 }- G; X$ C# R% n& {4 l% n cout<<")";8 w0 h5 B F; [ c: w5 |
if(type==1)% i. H& q$ S. Y( I+ h- q
cout<<"Zmax="<<matrix[n];
6 L; b& [( n, U else cout<<"Zmin="<<matrix[n];% l) ^% j9 y% {6 @/ s" p
}/ w+ _, i) s# }, m$ x4 Z- W
//////////////////////& K+ f" {0 s. {+ v; Q* z
void PrintResult()
* f: g' s& h( _4 }{
1 _4 J8 h6 W, J) J' ^ if(type==0)' D- v' A0 {( _
cout<<"the Minimal:"<<matrix[n];
% R, @& K4 o) s9 |1 K- j) ~* y6 ` else cout<<"theMaximum:"<<matrix[n];' h: h& B9 k9 Y7 a* e& f
}
5 U2 h3 _2 [2 s+ ]7 I# w( _////////////////////////////////
% Y2 I `) B4 q$ Kvoid Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并
0 [& N! t9 K# `{7 _9 } I/ \: }3 n3 p
int i,j;$ G: k2 k" u$ T M6 B( o+ R
for(i=0;i<n;i++)
" Z b. y& e( A6 [$ P {
1 {: Z. Z7 h/ ^9 s! ^4 w+ h7 R* U for(j=m;j<m+indexe;j++)
2 V1 r1 h* g7 V: i0 f if(nget[j-m]!=-1)matrix[j]=0;
# D, O0 [9 Y2 o' h7 M; | else matrix[j]=-1;
4 z- D0 d# N' t; {. S for(j=m+indexe;j<m+indexe+indexl;j++)
# \; p: T# ^9 y if(nlet[j-m-indexe]!=1)matrix[j]=0;
5 o/ r0 b8 {, `0 j6 W/ w9 L else matrix[j]=1;6 W) a' s+ j9 S) q/ o
for(j=m+indexe+indexl;j<s;j++)
" n c* H( b5 m0 a9 T, h$ y if(net[j-m-indexe-indexl]!=1)matrix[j]=0;7 h: @7 p% I+ W* J3 Q% _0 P0 ^
else matrix[j]=1;3 t! M! g. x# i$ F8 Q
}
% L$ R; x$ x2 l for(i=m;i<m+indexe+indexl;i++)
: T& I. T, Q! J matrix[n]=0;* j, \' L; C" C- Y$ {0 I x/ o5 B
for(i=m+indexe+indexl;i<s;i++)
# w. C7 W- ~( u3 j0 N' t matrix[n]=100;1 r$ E1 N8 W b4 W1 k
matrix[n]=0;
+ f5 G) x) \( _& P t! P}
/ G4 i8 O" K& \///////////////////////////9 y: c3 B5 D6 S: S3 f
void ProcessA()//初始a[]& b& v) [, p4 D
{
5 `" |0 I, h$ h2 A( D int i;6 G' @: m2 B- v0 C+ q
for(i=0;i<m+indexe;i++)
& e+ S: B3 O4 h7 l a=0;$ A1 V. r" N3 y/ k: Z
for(i=m+indexe;i<s;i++)) ?# l# A6 v+ n2 k
a=1;1 }: T. L s! A, v9 }4 Z8 A+ ]
}
% B$ C% x6 d9 l
////////////////////////////////
( L9 A6 z5 {; F" X0 {6 ^$ |void Input(float b[],int code[])# ]% H) ?5 f7 |
{
$ h9 i8 M' l. J* X int i=0;int j=0;" L# j0 `4 C$ H
cout<<"The equator variable and Restrictor\n";
) l+ O* s$ f4 o cin>>m>>n;! m' F6 k) y9 v% j
for(i=0;i<n;i++)
?& {0 c( {) k5 l6 d {
4 w0 d% }& V" C' E cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; a8 n8 C' J- E) _: M' e1 a
cin>>b>>code;" |+ t* o/ E8 I# d0 h
cout<<"The 系数 \n";8 E9 p& @6 n7 M
for(i=0;j<m;j++)
/ i7 y& Z4 v# { B) \ cin>>matrix[j];, Y) ^8 x7 U6 K
}
* t1 F- H+ p# g# u cout<<"the type 0:Min 1:max\n";
+ K/ B2 I$ x. a2 a. _ do{
/ o V; I- x# M. U cin>>type;
. A3 _* U$ S8 k4 I0 H if(type!=0&&type!=1)7 d% t, \( p& P
cout<<"error,ReInput!\n";* D6 ]3 ~' r) j0 Z( a8 }
}while(type!=0&&type!=1);
0 o, P- S ~/ X/ B cout<<"the Z\n";7 A" C# ^& w4 ]0 o. H6 D' X% }
for(i=0;i<m;i++)
, K( _; J& E, E6 C cin>>matrix[n];% {+ I; _2 k. p8 \3 p1 n
if(type==1)7 ~' F+ c6 p+ x. d
for(i=0;i<m;i++)
5 S2 N+ f1 }* {7 V; M8 }0 Y matrix[n]=-matrix[n];
- o: X+ E3 m# k. \0 c7 n}
7 _5 T( J' Z( x, I% X, N; _- i6 b7 C( p( {; @7 _' x0 @
////////////////// 4 ?# A7 }' o" }3 I
void Xartificial()//消去人工变量 S- V g- K* I5 J
{ u" o, s7 Z: J3 J, e" R& o. D
int i,j,k;; g \0 P+ i% p. v* Z- h" X
if(indexg!=0)
' ?' U) T; P/ a8 z" l V4 m {
% e9 q4 q+ d9 L, w4 N for(i=m+indexe+indexl;i<s;i++)8 ~6 ]8 C8 h+ `
{
. C: h5 ]+ y; u8 f+ c for(j=0;j<n;j++)+ O( I/ V( l) L8 E$ W- Z
if(matrix[j]==1)* u0 P) r8 Y* O9 G C
{
# N1 i+ D' T7 r6 w for(k=0;k<=s;k++)
5 _; \) j' z% `* h( I6 u% r6 O matrix[n][k]=matrix[n][k]-matrix[j][k]*100;* |$ E7 {, B1 M: u9 ]
j=n;4 k6 d! W. Z; l
}' B! f: d$ _" @
}& J+ ^, B# S) Z8 V9 e0 A D' d
}* b! n* e! M( O2 j9 \% I1 A
}
1 n" q8 V) t4 }- @& W. h///////////////////////////////////////////////// X" B( E- U- |+ H Q, S
void Process(float c[][100],int row,int vol)
, @* f* Q" ]- m{6 i) m1 X* _' E; X. U$ L6 ~
int i;
/ c7 ^% X( `" }$ u4 A& t; f0 ] for(i=0;i<n;i++)" m4 a0 H+ K: [! _5 q7 G' G" S
if(i!=row)c[vol]=0;
: L) g' q+ o& _7 `3 S$ e}5 `" v* w5 z' }+ x) v$ U
//////////////////////
2 w3 h. x! d% v+ k& C; w5 u) Cvoid Start(float b[],int code[]); e; x7 {8 |; G2 g+ Z
{
6 R" K4 I% t1 b# s2 `' x int i;3 K( U# }- M$ H
float nget[100][100],nlet[100][100],net[100][100];6 N" _& Z# J( C6 U: Y6 K/ d* d; D
indexe=indexl=indexg=0;8 D9 g; ^1 o6 L/ Z' |7 s7 H
for(i=0;i<n;i++)& l- B$ ~4 j% ?7 I. g
{
/ l& k3 _! e# P- x$ U3 i4 @+ R6 ?. t if(code==0){nlet[indexl++]=1
rocess(nlet,i,indexl-1);} t* A# F e) l4 t7 U7 o H1 p
if(code==1){net[indexl++]=1rocess(net,i,indexg-1);}+ C5 i' w2 H% F) `$ s( t
if(code==2){3 B4 G3 x" B+ h# s. h- I
net[indexg++]=1;& W5 \: u6 O* k+ k$ k/ }
nget[indexe++]=-1;
1 S5 M" l" U0 V$ _0 U0 @ Process(net,i,indexg-1)rocess(nlet,i,indexe-1); I7 P' M! G9 {1 x
}! A i+ b5 G* {0 d" [3 L( V
}- F- k# W" ?1 {% ^# H
s=indexe+indexl+indexg+m;5 {6 s, T- f1 ] M+ l+ f4 i
Merge(nget,nlet,net,b);
. J! _* f1 X$ E$ K# X, O ProcessA();2 E' P% {0 b* [8 ^2 B6 n
InitPrint();
$ u+ {2 q- D' V# l; C Xartificial();
$ u2 o" L9 }& w& B, q6 P& j}
3 l' r; R* e( nvoid Simplix()//单纯形法
7 @- |1 M. ^0 R0 q) T! a- s( |) l{
3 g/ H, r' |2 V; s/ a int in,out,temp=0;0 ^' ^: J) r/ x
while(1)
" y g! U' W' s2 |1 { {
0 e1 E. d6 @+ v" M2 {# P6 g2 o jckxj();
# m- V2 A2 b7 c7 G* M, I Print();, g! F0 H" V8 Q, C$ F
Result();
( m9 x# w5 W. H+ ` if(!rj()) in=Min();. V5 d K' g0 R- r; k0 L3 g/ b/ d
else{) |, J( A1 Y& k* M ~( a
if(indexg!=0)
9 b: x. Y$ V3 W1 s( p8 I JustArtificial();
5 G3 x: j/ \$ Q @4 P3 P PrintResult();/ t$ ~$ u0 m" b- O
return;
) r! @7 s3 m8 k$ X% x }* V: c5 Y& C7 a( s8 J m9 R$ c
if(Check(in))1 ]( L7 e, |7 f2 X8 J( C1 I( ^; a
{
3 i0 @( o8 N( s cout<<"No Delimition\n";
8 \4 j4 A, j8 r! o! ] return;
4 s& K3 [9 }7 ~- q }, P# T; L+ l8 h
out=SearchOut(&temp,in);" _" N5 @( Z) m7 u# x( ~" w1 x
Mto(in,temp);
2 u) `" D2 p: l' C0 k Be(temp,in);
n& v, ~0 z6 z$ V8 c! m, D+ i Achange(in,out);
- S- |6 V h3 E) C }, `+ K! C+ b, S N$ b
}
% d2 ]- O% ?1 {+ m6 u8 }
void main()3 b1 g( d$ \8 s' J
{4 W8 n9 Y- ]& H& ^% V8 T0 X
int code[100];//输入符号标记6 v/ H1 n( J, a9 e; q6 x
float b[100];
, z) M" D$ D! q$ m$ s8 l Input(b,code);//初始化& {2 n# B# J! F3 ?
Start(b,code);//标准化行. P8 Y0 W, \5 L: Q% j# Y& F
Simplix();1 ?. A4 I! }* g7 ^- _2 u9 k
}- f& ]6 H1 y: {9 i7 i
作者: 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 |