12 3 / 3 页下一页

查看: 12488|回复: 25

单纯形算法程序

[复制链接]

字体大小: 正常放大

zhyi

4 主题	2 听众	25 积分

升级 21.05%

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

#include<iostream.h> ( |1 i' }; K% e#include<math.h> 2 o& z3 K! \* J. b5 ~. {- |float matrix[100][100],x[100];4 k- e# X) D6 P3 } int a[100]; 5 f9 U9 l% \6 U C0 p! N0 w5 {# Bint m,n,s,type; 3 j* k- l4 r8 |int indexe,indexl,indexg; 6 I6 M) R* P2 K" A///////////////////////////////// & f! f/ s1 j# j l$ _" qvoid jckxj()//基础可行解 $ j" M9 @0 v3 _4 f2 K# j{ 3 V$ W) D, |! t6 m/ r1 W int i,j; 3 ]! a1 R0 @" D. S2 X for(i=0;i<n;i++) / `! o. x) b6 ?* k* A) h for(j=0;j<s;j++) 1 K: @ ~" M- {- K if(matrix[j]==1&&a[j]==1). e0 D) J& z0 c3 N4 p( o { 2 k9 E* `) s9 [, t$ r; h x[j]=matrix~~;' n3 K5 \+ @7 Y5 }! P5 f1 O+ E j=s;* y# o5 W+ z6 I' Q$ x5 X }. r$ n( @% H$ j* n for(i=0;i<s;i++) 6 a" Y- q. K# R8 M; y" l if(a==0)x=0;) a7 o. u0 w" p' ? q }~~

5 n! O8 G0 y0 ^; o* B: T g" J
int rj()//基解矩阵 7 M) f) g' Q' |{ 3 [* Y9 B: s# ]& }# d int i; 1 m; s; Z h% E! M) _) B# ]. {# O3 X for(i=0;i<s;i++)0 O2 Y' Y& P; [- D8 _ if(fabs(matrix[n])>=0.000001) $ t* k# Y4 e4 ?: o8 V if(matrix[n]<0)return 0; . O& M1 x( @8 J; N, h7 Z6 j return 1;, @$ W% K" E/ i3 C: a. ^+ _( T } # }+ T, z) Y- v; F8 X0 kint Min()//求最小的 ; m1 }3 k3 p3 w$ e, r{ 8 @( S3 ~+ i+ {' y5 w. `. j int i,temp=0;$ Y) H! |9 u& l, G: f float min=matrix[n][0];3 |; }' C3 \! e# j for(i=1;i<s;i++) & X; i9 }: l4 A5 N6 G# b if(min>matrix[n])% ]# U3 _9 X {, K {* G$ S- B' w' A4 D. }& `4 T min=matrix[n];5 T( \4 d2 X6 }6 q0 y& h. |4 B temp=i; 9 a" @2 ~4 Y" B1 o) {! C5 X D } ; h! o6 ] [3 a' d! ?3 a! I$ u return temp; 8 V9 u( s) l( B m} - o5 w& l5 |% G. W, L% t5 H* ` {3 f///////////////////////////////// 4 ^6 K! S! n0 i z6 zvoid JustArtificial()//人工变量2 V+ m' t5 U7 u" F1 @( [ {/ E) x W* G; z0 h& {+ z9 Y int i;# F' i9 c5 Q, S4 m( o z2 B8 m for(i=m+indexe+indexl;i<s;i++)' T2 t7 x) v. l/ l if(fabs(x)>=0.000001)9 t* ^: V2 F+ G$ |. ~ {: v1 s5 P/ S. d( t5 d+ k3 C cout<<"NO Answer\n";% U [: k2 K" s ^* _ return; : [6 b' v5 H" K* Z {2 O3 I } 3 t i0 \( c6 F& _} ! V+ I6 I+ T' g///////////////////// ) J. L4 ?* G/ {5 c, Z Q' Oint Check(int in)//检验 J" s9 _! ?+ r! w& t1 n7 A{8 Y1 C' u) |6 g8 O0 a d int i; + ]5 y7 t; K; m float maxl=-1; & L4 G+ x9 U# J+ X: r6 w0 t for(i=0;i<n;i++) ( L+ U! o$ o0 B2 O# C3 u if(fabs(matrix[in])>=0.000001&&maxl<matrix/matrix[in])7 l9 J9 o- F$ i1 C% L) v7 ?8 j maxl=matrix/matrix[in]; : X6 c8 ^. d& K6 n if(maxl<0)4 Z& h. t) Q4 \( V) d1 M( y return 1; 0 r1 B) e6 K3 h! F: h5 _ return 0;; D y- I' k' B; c! q, O: W } 3 X2 k9 ]7 c+ a; G# G4 j/ Yint SearchOut(int *temp,int in)//出基变量 4 r/ u* ~8 `2 U- I& a{; d, }+ Y& o& h) K int i;* o- G' C3 r* M2 z) e y float min=10000;' s4 J9 Z, b; G4 O H) _; b for(i=0;i<n;i++) . K% }- J+ p1 ^0 W2 | if(fabs(matrix[in])>=0.000001&&(matrix/matrix[in]>=0) . m, V! q4 \2 I$ t6 I* N &&min>matrix/matrix[in])' e$ E9 F$ G2 w6 z- a+ i8 @; r { - v3 k: w4 Q- }! H min=matrix/matrix[in]; ; W- I' |* A, B; w, ~6 {7 l *temp=i;: ` D6 H1 T( T- A: N } * f1 U9 k! \3 B0 R' q0 T; o for(i=0;i<s;i++): Q/ ]( J |# ~2 e2 \* |% Z if(a=1&&matrix[*temp]==1) $ f* y3 e6 t& Y( C+ b) M V return i; j/ t3 N- [1 N" H } 3 E9 n2 d; J' s0 t) [+ W///////////////////////////////// , i' O" w6 {+ e+ f& m$ o: tvoid Mto(int in,int temp)' j/ a6 ~6 ]# o9 u { : l7 {% [' m- _0 g! O9 b+ ^ int i;' k: v* N% n; T) c$ p/ N8 ^% i for(i=0;i<=s;i++)' |) a; g2 z- f/ O q if(i!=in) * _$ \9 _# m+ x2 m matrix[temp]=matrix[temp]/matrix[temp][in];* h. j' O( \: Z3 G matrix[temp][in]=1;- c1 y4 {" W7 @# p5 y! ] } 1 H" ?' }7 X9 K* K. I: Y/////////////////////////////- s: Z! _) h6 V, Q9 a* E4 o0 R6 p void Be(int temp,int in)//初等变换 5 d" g6 ~# p! r0 f0 x) \) P; _{ / E/ w. H9 u. P1 ^+ Y int i,j;1 I& R3 U2 Z' @/ n# T0 q7 M2 \ float c;$ l h" ]) ?; [ for(i=0;i<=n;i++)% {* I9 B' L4 y' V9 Z( v- U { ) n( i% W L* a4 M c=matrix[in]/matrix[temp][in]; " a4 j R) r1 H* H' ]; Y; O& J if(i!=temp) # ]" F$ h0 T( f: E for(j=0;j<=s;j++) # q! j$ @6 c, n9 n" X% B+ i matrix[j]=matrix[j]-matrix[temp][j]*c; 7 }3 {& ]$ G( g6 R' T9 i8 W& B } $ @! }, l# V; |2 F' k, M} + T7 x- p7 X( I1 H3 Q; n//////////////////////////& q$ ^2 w' m$ T# B, l$ ~: H void Achange(int in,int out)//出基入基转换& G( l' L. f% y$ P {' k V0 s3 D' k int temp=a[in];. T+ y0 l1 V1 c! z$ I8 O1 _ a[in]=a[out];4 d- [3 D. r1 p7 g8 L+ G+ [ a[out]=temp;) E) n& h/ P; r R& u5 o/ k } + @- J4 ]& \' X* f% r" c////////////////////////! n( R/ K7 }4 w4 |* z) U void Print()) k. V3 x4 [. E) B2 d8 l) _, ]0 ~ {5 R6 @' d" m3 u2 C3 Q' S, k int i,j,k,temp=0; 4 @/ f' b- z8 F% k7 O6 i; P! S for(i=0;i<n;i++), A+ k: E( `& L5 |3 F J p9 f {: `! P* q; t: c# w4 r; ` for(k=temp;k<s;k++) ! Y7 J d2 b3 |, \ if(a[k]==1) & B3 q {( o# U3 k0 k4 W$ q' a { / V! H5 h9 k! T: h1 K% X) J cout<<k;& N" S# o, k. T: Y/ K. f" a1 b temp=k+1; 4 U- f- `% f$ M E* _ k=s; 7 ~3 |8 @. d, u, a: d* w3 u }. s& r3 J: f; b7 C% H# M for(j=0;j<=s;j++) ! S2 Y) h( D- E: X) E0 Q. P! } cout<<matrix[j];$ m. }9 u4 Q# _ cout<<"\n";: a$ e- ^& p- r9 w! k& s' s( w1 t( D }; ^ d9 q9 E2 k cout<<"Rj"; 6 _) b5 s$ o1 c* D. g% U for(j=0;j<=s;j++)7 c$ Y$ \; }6 ]5 o7 x4 _4 G: M cout<<matrix[n][j]; @* p3 w& Q2 q9 i9 F. G, j9 s, y cout<<"\n"; {" I' M! T4 r0 K$ W' t5 p$ ~}9 v9 m% |, ^+ x* ^! r //////////////////////// 9 M) `8 v; n/ h9 R {5 d1 dvoid InitPrint() " u9 U& z4 L/ k( t* \* t! `: k{ 2 c1 w+ A- ^- U0 S6 e2 Q int i; + b! K: O2 ?' {0 i cout<<"X";" R9 m" `: n M* T for(i=0;i<s;i++), Y1 |1 W8 n7 w+ B4 @* K; @ cout<<i;7 O6 h! q2 s# n0 X) W+ ] cout<<"b\n"; # R2 p9 v( P7 B9 F cout<<" ";. X: j$ ~- Z" ^4 s1 a$ B cout<<"\n"; 1 C; S1 K' `# O0 ?( {}/ m: i X1 k8 n7 ^+ v ////////////////// , w% Z$ C, o0 J" @0 lvoid Result() ' c& n1 }5 x& L Y. T& h{. q( A' l6 ^- Z2 Z+ |/ g int i; 2 i3 a/ s/ c1 k) s/ H7 N! j! C/ b4 i cout<<"("; 3 N' ?3 ~7 u) a* q" d# ^ for(i=0;i<s;i++)+ M0 l8 k! |( {' R+ i& H2 u cout<<x; ' @8 A$ \( ]6 y ^) J cout<<")"; + L" v" }& g( M$ h- J# h( F if(type==1)% `( I6 K: `. z8 E) N, f6 K/ j cout<<"Zmax="<<matrix[n]; M8 [* o4 q* e4 S! ^! v$ C6 V else cout<<"Zmin="<<matrix[n]; 3 ~! j/ y3 f( X( }. g: q}+ `9 P$ e/ c! d3 N' G/ `- Y$ U ////////////////////// - y% i! a3 I# mvoid PrintResult()/ k- N, |3 R; A' g9 _ {9 l' { i6 I# Q) s if(type==0)$ o r8 Z$ Z R* W cout<<"the Minimal:"<<matrix[n];4 S# R2 H- }* B; N$ p* s# O9 M else cout<<"theMaximum:"<<matrix[n]; * ^- B) b% E5 s& @7 v; Y7 D/ f}6 y- t8 h) s0 a7 g' U8 b3 ? ////////////////////////////////" w4 t; g8 R# ]8 {; \/ m/ `- M& A# ? void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并6 S v; b, M% d* c; M: ? { # L3 B6 ?8 z1 L' g) G+ c! o F int i,j;+ W3 `. U2 H' w- P, \ for(i=0;i<n;i++)+ _& d4 s. T6 E+ O {3 J$ A V3 v) c( v for(j=m;j<m+indexe;j++) % f5 Q; P q5 Z% w# e if(nget[j-m]!=-1)matrix[j]=0;1 I. I& B8 O: G2 @; r7 I else matrix[j]=-1; M: O2 q; S) L3 p" X1 A1 T for(j=m+indexe;j<m+indexe+indexl;j++)# }! x( ]* B9 t if(nlet[j-m-indexe]!=1)matrix[j]=0;/ Y# S2 i1 l% T else matrix[j]=1;5 m" s+ s z& G0 u' r" } for(j=m+indexe+indexl;j<s;j++) " { \+ @% X3 ^' N$ B5 v if(net[j-m-indexe-indexl]!=1)matrix[j]=0;4 X0 F5 T5 o" \ else matrix[j]=1; 7 ?! d0 F7 d- n& |7 N+ P } 0 {' D8 y& ~- d* H+ j1 Y) k- B for(i=m;i<m+indexe+indexl;i++)6 I, c; L8 M8 V& {# I- ~ matrix[n]=0; ' \9 Z3 Z( ]2 ^! t for(i=m+indexe+indexl;i<s;i++)1 J5 M1 V5 a1 w: n5 Y' ~2 n( D M/ t# _ matrix[n]=100; & A) N& y& g# O' ^ matrix[n]~~=0; ! m- q" z9 x# S' Q8 X! p5 g A( H}~~
1 Y$ U- n5 [, {% B) ]& j6 i( j
/////////////////////////// 1 P8 o, o) ^: }) V; ]' _" Svoid ProcessA()//初始a[] 8 M( L6 m% X [7 w9 W3 v{: H* _8 d' v; ^& X8 n- r int i; 9 A0 M+ Y6 K* q! `/ @/ g for(i=0;i<m+indexe;i++) 0 ~1 x- [% v. q2 I; r a=0; ' s9 H/ ~ D# Z$ U6 | for(i=m+indexe;i<s;i++)7 U+ X. q, a, ?' |3 ^9 e Z a=1; 3 D1 ]! `1 B3 D* w3 M2 s}
# B; L7 e5 {7 u1 J
////////////////////////////////0 { }5 S3 ~& v) o; Y void Input(float b[],int code[]), Z# L8 z; L( z4 ^ { . @' F( |1 K* w+ k0 A+ q$ j5 |+ t int i=0;int j=0;8 [2 v, l- a- [& y- M$ G cout<<"The equator variable and Restrictor\n";! g5 @1 ^( q& c cin>>m>>n;( z! v% @- Q9 v* N for(i=0;i<n;i++)( F6 T' m! b& W5 X" Y3 O, Y3 r {( [4 i: _" ?# ^6 I( q cout<<"Inputb[] and Restrictor code0:<=1 1:= 2:>=\n"; & }. j. f% i+ j/ }% ~ cin>>b>>code;6 Q2 [" v' F) m cout<<"The 系数 \n";0 R1 u7 z) W; q% T6 e& L1 h! { for(i=0;j<m;j++)8 V# K$ R' Q" [1 U6 X; y* j cin>>matrix[j];" e5 I1 |2 _/ P- P: D4 w } : _5 ^; n' S5 J, D2 ` cout<<"the type 0:Min 1:max\n";* C2 l9 O9 b: `1 h" k4 U0 n do{- L: o; @- `) D! N9 B g+ L4 d cin>>type;: l; e' {( N& H# p0 `0 h if(type!=0&&type!=1)* }9 o2 G6 N5 T; {5 z- C5 _4 K k2 P cout<<"error,ReInput!\n"; o* c5 r! o7 ?, S }while(type!=0&&type!=1);: L& K+ [6 J+ C' s( }1 \: d5 J cout<<"the Z\n"; 0 D: `# H9 K& a. @6 U for(i=0;i<m;i++) + e8 K5 S# v! O2 d9 U" y. d* S& |, J cin>>matrix[n]; " N; F5 g4 b4 f' u0 c& @ if(type==1)3 t& J% x+ W' `: | for(i=0;i<m;i++)3 J, ]8 H( {0 \) k, v u" T matrix[n]=-matrix[n]; 6 \) s$ v5 a! y8 u6 X, a}
& C/ w! a: r* k: F& |. r3 r& |
7 i: `4 j" a0 U3 A' m# [: J( F ////////////////// 0 O) t8 j0 j1 ^" x/ A hvoid Xartificial()//消去人工变量 $ R: l% d4 l; I6 d" T2 r{# z& d$ _' [1 p* o y2 p5 s int i,j,k; E0 d( N& o1 m @ if(indexg!=0) 9 R T) K1 W+ ` {" ~4 v+ m1 D+ O) z, T- f7 \ z for(i=m+indexe+indexl;i<s;i++) $ r; u3 V) ?3 ?" l3 i0 N- H {& ?' q; g" @4 X for(j=0;j<n;j++)8 ?8 i8 A, K+ ? g) N3 S$ t5 ~ if(matrix[j]==1)5 l: g+ M( H$ g {' \3 D/ ~3 Z" c* x for(k=0;k<=s;k++). @" |# p, d/ p# G matrix[n][k]=matrix[n][k]-matrix[j][k]*100; # D: p( h+ q' e& z1 Z j=n; # ?, A7 ?; a% ] } ; B& f) |( }5 V } + }+ V: ^0 o: X }0 I4 L( e8 R7 b0 m }
7 ~- I3 Q2 V- V/ L# F: S
////////////////////////////////////////////////6 G# S3 O2 Z* A% ?! a. W; @ void Process(float c[][100],int row,int vol) 8 s$ s, u+ o# v; |* R{ " A h1 R, u7 P k, d7 W int i; 5 ^6 B7 U2 q% ^- C for(i=0;i<n;i++). y" r) p9 G: U3 i3 U( { if(i!=row)c[vol]=0; % z5 q% T$ A; o) T4 W' R} ) {( `9 {2 G7 j////////////////////// + G) T) h: D9 Q7 @( `) N! W; b4 m* tvoid Start(float b[],int code[]) 6 }6 S2 O- d9 M: b& O' @{ * W' G5 N. j6 X. i/ o+ u' { int i; 2 J' f, R! D8 q. P0 _* d A1 @ float nget[100][100],nlet[100][100],net[100][100];- }( `2 A2 V6 V% P0 o/ u9 C L indexe=indexl=indexg=0;8 O- g! ?& B5 r" y, V9 o# v for(i=0;i<n;i++)$ k7 w% p1 a; z) u4 @5 ? {$ d d, a' u- D1 Z if(code==0){nlet[indexl++]=1rocess(nlet,i,indexl-1);}2 ~1 F: |* Y8 T1 e" Y. | if(code==1){net[indexl++]=1rocess(net,i,indexg-1);} 8 p$ f# B4 q) [* O if(code==2){2 K3 I! k1 L0 ~3 A; ~" h( Y net[indexg++]=1; * F8 K( q$ t; O% e) ^' f8 T nget[indexe++]=-1;* O* d, J* x; [/ H Process(net,i,indexg-1)rocess(nlet,i,indexe-1);4 e/ Z, C/ l. K/ Z. ^ } # q% _0 T$ G6 @& R7 o3 L1 p y; k$ u! { }0 q( T7 b1 g5 U" X& } s=indexe+indexl+indexg+m; 7 r8 U; X: [ J( \ Merge(nget,nlet,net,b); ( h' r; z/ b7 r8 s ProcessA(); ; f0 [8 k8 L7 [9 | InitPrint(); 9 a: e. e1 U" x% [8 ^ Xartificial(); - Y/ _2 ?, S9 b. F9 e2 Q5 A6 f}
% q" D# }' P" H0 B/ w0 Y8 c
void Simplix()//单纯形法: {. H+ ]; l& t( t. i: j7 S { 9 b: k0 ?. g7 P int in,out,temp=0; / j" `0 ^: W+ z. r5 P; T- B while(1), l, e7 L/ I! z3 p5 z4 n- D/ c {" Q& j$ ]8 A E& ?( N jckxj(); 4 ]1 J5 F3 ~# d8 w& Q' P8 _ Print();* W' C, K% e" Q6 V4 j0 d4 M- O7 C Result(); 1 K+ i1 ^2 E: p2 @) k( l if(!rj()) in=Min(); 1 R! H( r& E; U' D2 v" n- W6 I" F else{- }2 l& j0 e! O8 f& ? if(indexg!=0)9 \% y( [" X6 `( D& K JustArtificial();' N g* d! W9 N. N: _ PrintResult();' i/ t' J3 h: A( n+ { return;. m" {' D/ L2 S/ n* U }# F" U" H0 W. ^ if(Check(in))! y' J5 o: g+ C6 T6 X$ |1 ] { 9 \% O! T8 |2 s7 v cout<<"No Delimition\n"; W/ V: { Z, G1 s return; 1 E1 I8 ^' _" J: ^6 @$ ] } * z- O- N7 |! E9 D5 j5 p out=SearchOut(&temp,in); $ }( c* \1 C3 F: B Mto(in,temp); 3 H; N! Z) |+ u& v3 g4 [ Be(temp,in); 2 O# g0 ^8 `5 A x5 n Achange(in,out); 2 U7 R( f8 o- }& _- b% x" d } 0 ^' R# j$ e0 r% q+ V5 M- }, u}
& c- m; _ D( f1 {2 x" f0 O/ `$ ^
void main() 0 i7 `; x9 s- u, {7 \. p' O{1 R$ k$ }3 G0 ~1 x" ]8 f; p int code[100];//输入符号标记# Y0 t# `! F; }4 |% f float b[100]; / P: A# l& `* s1 c! W Input(b,code);//初始化4 W9 J; o; F/ Y% M; Y2 ^ Start(b,code);//标准化行9 ]3 X7 H. ^( N% G. w Simplix();+ r1 q1 ?% r: r o! Z* M } . x# P% O; k" z4 a( y4 V

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

Kadyniost

0 主题	4 听众	187 积分

升级 43.5%

该用户从未签到

26^#

发表于 2009-8-10 00:26 |只看该作者 |招呼Ta 关注Ta

。。。。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

aruisi

5 主题	3 听众	2288 积分

升级 9.6%

TA的每日心情

	奋斗 2013-12-6 19:59

签到天数: 565 天

[LV.9]以坛为家II

群组: 数学建模

群组: 大家

群组: Mathematica研究小组

群组: 安徽赛区

群组: 我行我数

25^#

发表于 2009-4-4 16:31 |只看该作者 |招呼Ta 关注Ta

我眼睛好花啊！

我也说一句

发表

使用道具举报

jkkjk

481 主题	6 听众	52 积分

升级 49.47%

TA的每日心情

	开心 2015-4-4 06:20

签到天数: 8 天

[LV.3]偶尔看看II

24^#

发表于 2009-2-14 04:34 |只看该作者 |招呼Ta 关注Ta

这么长！看不懂啊。

我也说一句

发表

使用道具举报

echo5183

0 主题	3 听众	24 积分

升级 20%

该用户从未签到

23^#

发表于 2006-12-4 12:19 |只看该作者 |招呼Ta 关注Ta

好

我也说一句

发表

使用道具举报

pytff7

0 主题	2 听众	21 积分

升级 16.84%

该用户从未签到

22^#

发表于 2006-11-18 15:45 |只看该作者 |招呼Ta 关注Ta

hai a 

我也说一句

发表

使用道具举报

hnus31

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

21^#

发表于 2006-11-11 09:46 |只看该作者 |招呼Ta 关注Ta

不错呀

我也说一句

发表

使用道具举报

999mmg

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

20^#

发表于 2006-11-3 13:55 |只看该作者 |招呼Ta 关注Ta

呵呵  绝对的好东西  我喜欢

我也说一句

发表

使用道具举报

hustyangyang

1 主题	0 听众	18 积分

升级 13.68%

该用户从未签到

19^#

发表于 2006-7-19 14:59 |只看该作者 |招呼Ta 关注Ta

楼上的的确是位高手，这两天由于写论文要用到单纯形法的程序，就拿来用了，但是发现有些错误，没有结果或者得出的答案有问题，于是我仔细看了一下这个程序，将楼上的笔误，和一些其他的小错误改正如下，
注意：我不是用纯 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
   }