数学建模社区-数学中国

标题: 求助：单纯形法的程序(c或其它语言都可) [打印本页]

作者: lauqt1980612 时间: 2004-8-3 22:01
标题: 求助：单纯形法的程序(c或其它语言都可)
急需啊，谁有啊。感激不尽啊!!!

作者: lauqt1980612 时间: 2004-8-3 22:09
最好是C语言的!

作者: julysea 时间: 2004-9-16 01:10
以前遍了一个小程序，可惜只能解某个特定问题。。。。

作者: candid 时间: 2004-11-28 21:08
<

>不知以下这个程序满不满足你的要求<

>#include<stdio.h>
#include<math.h>
#define X 5
#define Y 7
void xi_max(int *m2,int *mn1,float *c,int *is,int *ir,int *j0,float (*a)[X][Y])
{
 int j;
 *c=0;
 for(j=1;j<=*is;j++)
{
 if((*a)[*ir][j]-*c>0)
{
 *c=(*a)[*ir][j];
 *j0=j;
}
 }
}<

> /***************** 参数说明 **********************/
 /* m_约束方程个数(基变量个数),n_非基变量个数 */
 /* m2-m+2整个变量,(*a)[X][Y]存放初始数据 */
 /* (*k)[]存放基变量脚标,(*x)存放基变量最优值 */
 /********* <a href="http://happyyangxu.home.sunbo.net*******/" target="_blank" >http://happyyangxu.home.sunbo.net*******/</A>
int xi_sm(int m,int n,int m2,int mn1,int l1,float (*a)[X][Y],
 int(*k)[],float(*x)[])
{
 int i,m1,mn,j0,i0,j;
 float c,g;
 m1=m+1;
 mn=m+n;
 for(i=1;i<=m;i++)
(*k)=n+i;
8 t, w2 [$ |$ N) I5 C# H& O+ uleap1:
5 g' z! E# m2 _6 ?0 b* ^' ?8 b0 V if(l1-1==0)
5 N- N6 v2 {$ h h0 R! G xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);
+ H$ A$ C$ F$ r" } else" E' Z+ v; \2 \( \8 e6 M6 |& E2 M9 m5 f
 {8 Z: \, U% w- k
leap2: if(l1-50==0)& W$ Q" Q6 C9 ?- R; k1 |
 xi_max(&m2,&mn,&c,&n,&m2,&j0,a);) e# S% J2 T6 H( j
 else
: e/ d. P0 q3 j/ C xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);
6 A1 ?5 B% ~3 l* U/ p } U$ _- a# M$ W9 v7 h6 [# D3 ~
c-=1e-8;
. J$ ~. a- B/ r0 {/ _- ] if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))
/ @+ ~5 n! b: J& @1 Y {8 j- a% b% e9 c" n8 a* Z& z- M- N
printf("\n\t*********Not min&&No solution**********\n");7 g9 z7 a- q( |( O2 {. [$ a4 H; U
return(-1);
* Q4 N% d- c. D$ \ }7 U- u9 C x1 o6 ]1 l- ]' a
if((c<0)&&(l1==1))- ~& T6 H6 f+ V$ i y
 {
! |/ q' i+ Y/ Y$ N l1=50;! R9 e* A6 {; F4 v6 l- f) v
 goto leap2;
! n6 t$ c) V, l0 ~, M }! Z7 T" j" C9 D& M8 l
if(c<=0)4 h# e G, h7 x6 |/ b
 {
! b6 e' y9 p" V: n: d2 v9 K/ B! ? for(i=1;i<=m;i++)4 [8 a/ y" Q+ L
 (*x)=(*a)[mn1];
% P \! }+ _0 E3 [ printf("\n\t********Optimal solution********\n");6 M/ d7 o( b, v$ Z9 ~
 for(i=1;i<=m;i++)
7 [& K5 M1 U$ U, D, y# g printf("\ni=%d,x=%f\n",(*k),(*x));& {8 h L6 Q' S7 y
 printf("\nF=%f\n",(*a)[m2][mn1]);
4 T- T% C2 c4 d; M1 ~% I return 0;. J) p3 @2 N0 \! K; ~7 C3 @
}) V; j# I& i v. v
 c=1e8;
- Y) }" L# f" J- ^& _; Q0 c for(i=1;i<=m;i++)1 X! @# Y% g! m" b
 {
* X) G6 d' b8 q4 Q# ]0 |& u9 N6 \. \ if((*a)[j0]>1e-8)% F3 v/ D0 t2 R/ j' G
 {
/ c6 ~7 p2 _: ?; } g=(*a)[mn1]/(*a)[j0];% Q% X, t3 L- \0 a0 A. C
 if(g-c<0);2 W2 r) a* R" p- t |6 _1 w
 {
- \( e1 `* H0 } @$ h- W c=g;
4 d4 Z8 t0 Y% Q j i0=i;
# h, b0 T: J. X! G }2 E+ y0 D2 k" L9 O: I& X' m( g
 }
 {9 t/ L! i7 ?: \ }* }. |9 b+ ?* @/ b1 t
 if(c==1e+8)2 u. F9 i) S$ c6 ]2 v
{
' a- v: J5 |% b# q4 P printf("\n\t*******Lp no solution********\n");( q- }( T5 C* O: I) o8 x+ K6 L; U
 return -3;
: k# @/ n# w& P# e$ g6 T. }$ P }
8 r' f8 E) @6 ?/ n) C% | (*k)[i0]=j0;/ ~) O/ r! D' q) G' [% b/ i) H
 for(j=1;j<=mn1;j++)
* o* z0 Q& L, ^9 P. D0 R. t) M6 ^4 h- k {; {: Q( ^5 s h
 if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))
- t7 q* @. \4 h& } continue;
- A2 Y/ d9 }3 P& i& X+ B2 o g=(*a)[i0][j]/(*a)[i0][j0]; R- y# j& o2 `0 E; ^
 (*a)[i0][j]=g;
& c( P4 G) t( A2 U# L ^+ I" j7 [. d for(i=1;i<=m2;i++)# [; o/ T# {9 O4 J0 X) [! J$ D
 {2 }0 {. m" J7 m f
 if((i==i0)||(!(l1==1)&(i==m1)))
& z& n2 d4 _/ ~0 z' O% j6 f continue;! j) \( p, e7 ?3 r# M6 K9 ?9 F2 W& L
 (*a)[j]=(*a)[j]-(*a)[j0]*g;
( R' P! T: ^% A7 p& K }# s& W/ T' Z5 T Y5 n
 }3 [6 n; w+ l" [- |0 A# Z3 S7 o
 for(i=1;i<=m2;i++)' j1 B( x' r' H
 (*a)[j0]=0;& \& f2 D, Y1 c( ?
 (*a)[i0][j0]=1;& L1 N4 X4 i: t" m
 goto leap1;* k" F$ B1 c' g2 T6 t. J6 X
} ( o- a; G' k3 b7 d( ]; M( k& |
main()! U7 o/ {' l, K6 w
{
* J: G' l* K v* A G float a[5][7]={{0,0,0, 0, 0,0,0},
4 N9 k0 G( z. @+ @3 f {0,3,-4,3, 1,0,12},. s* A3 E6 b" T/ z. I6 F
 {0,3,0, 6, 0,1,12},
; V# ^+ D, T- D4 X+ H$ m9 s {0,0,0, 0, 0,0,0},
" \7 [9 w+ y1 h9 p {0,69,0,144,0,0,300}};
: Z) m, _7 x1 ]' B, h5 m int k[3];
; C9 z8 @- z Q0 M float x[3];
1 y; i) z- ~2 [ M N3 x clrscr();9 C0 Z9 L3 f7 D- e! o/ M/ |7 |! Q
 xi_sm(2,3,4,6,0,&a,&k,&x);
2 A- b; V& o' {6 ^}& N: o! {2 s: S4 ~

作者: plgatc 时间: 2005-4-25 18:00
<>/*************************************************************************
6 h( \% a' f( c 单纯型法解线性规划问题（两阶段法）
: T# R7 j. G" h' ^
" _" Z3 z8 Q9 X 编程环境：VC++6.0 ) _8 N5 U8 n6 R R/ a! B( G
方程组输入说明：4 c5 \$ |- u: J$ Q7 l3 z
变量非负，按提示输入相关参数。' U* l- J. s5 `" _( A7 D. c8 z
*************************************************************************/ K. B& T( }2 ?8 k
#include <stdio.h>
0 z4 ~' G% k' O8 E#include <stdlib.h> E4 ^" @$ ?6 S3 w7 p7 b8 Z$ o
#define MAX 100
/ O7 p; Z' B$ X: ^: \#define STP 100
- l/ @8 A: [' V<>int stop=1; //迭代记数变量, ~' |1 N1 f7 }8 J0 [
int status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数
3 G+ k# [* |; l4 g5 x: Gint step=1; //目前阶段
; T r* G- w+ J9 C) @<>double a[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0; //方程组相关系数
. B; w0 z+ d& O; M4 @: P; |int num_x; //变量个数 5 _6 E6 _% m& k* J
int num_st; //约束方程数
2 f E2 j1 [$ Lint num_ar=0; //人工变量个数 k7 \$ B( H+ e6 Y& A0 U
int arti[MAX]; //人工变量下标
' D( K0 B ^( D2 q# L- eint base[MAX]; //基变量下标$ s, ?1 l, r* u7 b
int ma_mi; //1为求最大值，2为求最小值
5 W/ V5 }* K9 B1 M<>void create(); //建立方程组
/ k4 _- H: }* K$ P. n$ ovoid iterative(); //单纯型法迭代
" u9 R9 R2 t5 ovoid output(); //输出结果
% }% a/ p. ~: i7 o$ [4 Yvoid banner(); //打印程序标题
& X% z9 z* a/ o Y* _; D4 d1 U8 yvoid exchange(); //交换两阶段价值系数9 z: w! ]. Q( D4 w* G8 J: S
void show(); //输出方程组
: s" \# {7 s2 P% Z<>void main() {! z0 e A( D2 E- S2 g3 t G
int i,j,k;# u' n3 }: M# m
banner();
' @7 c9 f: }+ `" x7 N6 j create();
1 L2 C9 B& s/ n j9 K2 z1 |/ L; D //保存原价值系数，转换为第一阶段价值系数
& T6 e4 S7 Y0 W# Y" d for(i=1;i<=num_x;i++) {
5 R: N6 ?; T% s, D9 a" ^ k=0;
 z1 T5 c$ i9 X* ~4 x' q for(j=1;j<=num_ar;j++) if(i==arti[j]) k=1;
" I7 h9 f/ O/ \( R7 C' A if(k==1) temp_c=-1;: v. r6 ]* l' B; O# T
 else temp_c=0;
7 B, F, s ~1 F3 x G9 W. U }7 t' w* X9 x7 I/ c9 i* X7 f
exchange(c,temp_c);
5 A5 R+ b( Q* f* z4 U: Q7 e<> printf("\n\n第一阶段问题为：\n\n");4 i7 A9 Y7 P4 P [
show();8 k' ^4 N0 d- R$ J7 |: u
step++;0 R5 c6 X6 S: e( Z* v- `6 K6 ?
printf("\n\n按回车开始第一阶段迭代");% M( k d* F0 X `6 {5 }; @ S
getchar();
' ]& X4 Z8 ]2 P, n( ` getchar();/ F8 S: W9 n) \' O, b7 T0 V
iterative();
+ U7 f: I3 U3 f5 e5 P if(status==-2) {
* ~. ^$ |7 J( X' ?" F5 m puts("迭代超过限制次数强行终止！\n");
5 G2 ^; ~% \: f% J) m4 C' L puts("\n按回车结束");
' A% ]+ Q7 k2 ~$ c: s0 o) e getchar();2 Y! U9 A5 }; u$ A9 p
 exit(0);* C5 f- E- Y7 I6 J" I! }
}1 d3 I6 S& k6 C9 T
output();2 W. j- k( f$ H# l, N* F4 I
<> if(max!=0) {6 k9 d& ^1 ~1 @" [; K: |# S) w
 puts("\n\n原问题无可行解。\n");
8 m: U, @7 s9 M) ` puts("\n按回车结束");
: l$ }) F M* q" ~ getchar();
+ \- Q, V2 O) s0 I7 N+ F# S. H0 N exit(0);- [, j/ c3 L% O+ }* \2 |9 R" y
}) R n) L! ]3 {3 @9 m
<> //转换为第二阶段价值系数
 _( i7 t# V* {5 { exchange(c,temp_c);
1 Q& H* ^; a: q4 Z( |0 U8 x //把人工变量列全设为06 z j a4 C0 b% N, n
for(i=1;i<=num_ar;i++) {
5 a( E5 k; {3 T$ B) z c[arti]=0;9 h6 x" D9 n& G" x% @
 for(j=1;j<=num_st;j++) a[j][arti]=0;
' _# y+ \' S8 _! H, z8 \ }( {2 F. j7 x8 G
<> puts("\n\n第二阶段问题为：\n\n");
. j- c9 O2 j, Z8 l( M y show();
% c: @8 {9 n5 H8 g: }6 `& C puts("\n\n按回车开始第二阶段迭代");+ j/ a0 s( s6 a' T. a
getchar();
9 H) v0 H* G) P! o. G1 E iterative();
& }3 w, Z- C- q) l5 C7 i* Z. Q switch(status) {) D& q- R# ?9 C: h! Z
case 1:
3 Z2 J9 D( m0 I output();
 c+ J2 t- N0 C2 J2 g& R2 m puts("\n\n原问题有唯一最优解。\n");
* ?" A, F6 q8 d. w# k% q' E puts("\n按回车结束");" a! x# Y8 ^; j/ n) I. b8 r
 getchar();# E) p0 y5 S% G( {) y( d% R
 exit(0);# I! a) X( C8 S& F w
case 0:
2 i8 P4 ]: a' G: K1 z( l; n2 `/ l% Z puts("\n\n原问题为无界解。\n");
5 r1 O B! C l" G B puts("\n按回车结束");
0 H3 @5 l+ \- H1 @- _ getchar();
$ W; j9 N( q3 X' C- T7 T exit(0);
3 @( T+ N9 D p0 ? case -1:9 }# L- c5 v* S1 M [& D+ M
 output();0 L/ K3 M2 T ?% x
 puts("\n\n原问题有无穷多最优解。\n");9 u$ o6 y/ G3 c* ]* R
 puts("\n按回车结束");
/ M s v! Y/ c, q, v7 x getchar();
3 ~& j- |0 g' R+ f0 V) Y exit(0);) p3 Z. C! z7 P7 }+ }
case -2:
5 M0 m9 _3 @+ g: f# w! K+ ] puts("迭代超过限制次数强行终止！\n");) [. m7 K' h9 n* u; R
 puts("\n按回车结束");
: }& Y; O! h9 M getchar();" v* b# ~/ x. s* X9 }
 exit(0);
: r p+ Z7 l- W$ x; O }//switch
" p7 b9 A3 X% l7 I! l0 S}( g* x) g( F2 Y8 K9 ]
<>void banner() {/ a% j+ s B, }0 L$ [& `4 w4 C
printf("\t\t****************************************\n");
0 ?# M, T: V) T# L% d/ R printf("\t\t 单纯型法解线性规划问题\n");' G. B& l% m g0 R
printf("\t\t 作者：Thunder\n");
 R' H; ~1 s. o& _& x- \3 H printf("\t\t****************************************\n");
( m1 `# a" o4 q printf("\n");
+ f: }5 o2 H; f}
: \4 B' K9 k0 `' ~<>void show() {$ v K# |" D% d% w( @+ m# Z
//对方程组以自然的格式输出，系数为零的x不显示6 @ \* A+ X- ?$ @% B n0 h
//为1的不显示系数1，-1系数只显示负号
4 w# b8 I, I" u( C$ e }" E. H int i,j,k;0 d( Q I# I* q4 B7 A0 m
switch(step) {
 c( }7 M, X' K' q case 1: [& x7 r* r; B! l: n
 printf("min z= ");
/ t. J( i- d8 ^ l printf("x[%d]",arti[1]);% e7 r E2 L1 F
 for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);9 w2 F4 M; `; |0 ?7 W1 V
 break;1 ^7 _& s. ^' d+ G3 P: K; w& Y
case 2:
0 D1 c5 P r' |" i printf("max z= ");8 T1 i: e' U1 A+ G0 r
printf("%lg x[%d]",c[1],1);/ ?$ ?# W9 u) \' H+ Z6 ]
for(i=2;i<=num_x;i++) { e! ~3 U2 e- F' E0 l
 if(c==1) printf(" + x[%d]",i);8 U* i# M e) e. w
 else if(c==-1) printf(" - x[%d]",i);2 i8 C) m" i U2 | {
 else if(c>=0) printf(" +%lg x[%d]",c,i);' H( D6 \1 e& n$ Z2 |
 else printf(" %lg x[%d]",c,i);
) w( v- d2 n4 J$ S! K3 G, S0 ? Z) ` }
+ j. }5 ~! v( x5 \7 U. S% ~. ~ I break;
* R. u# ~- K' p& Z8 i& K: @6 { }% I* |4 j; H" ]1 \
<> printf("\nst:\n");) q1 c1 R9 P4 d2 I
for(i=1;i<=num_st;i++) {
, B" s7 b$ M" p( j k=0;
, ^; w {6 G4 ] o for(j=1;j<=num_x;j++) { A w+ g( Z M1 C6 n( e8 x
if(a[j]!=0) {
, z( x4 _* f& W/ v/ @ if(a[j]==1&&k!=0) printf(" + x[%d]",j);
 \) o, O0 k% ]5 T% y6 X else if(a[j]==1&&k==0) printf(" x[%d]",j);
! k/ a3 p$ Y3 L! y( V2 y; b else if(a[j]==-1) printf(" - x[%d]",j);
1 ^" l% K- e8 ?) x1 l, U! {% J else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
& N* v3 X. h- T& x1 Y7 B2 I else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
! e+ X# y, h3 y* ] w' S; R7 H else printf(" %lg x[%d]",a[j],j);: V* t3 \( c7 R
k=1;4 u9 t2 o5 r) O5 F" ~$ m4 x7 c1 I
}
) b6 n& T& u/ l: K- |; @6 \ }
2 u. y5 V4 B+ @# |0 ]0 P) | printf(" == %lg\n",b);
& |( q: z9 \! x: Y7 ` }1 p9 P6 z" D4 k* t7 ~) Q
printf(" x[1]~x[%d]>=0",num_x);- a4 T2 b6 C4 V2 Q
}# {! a: m* f1 h2 N3 C' z2 a
<>void exchange() {
: k: J) N5 ]; K& C) W/ J- {( r int i;
 O" B$ s! \3 Q7 r9 S5 X/ \/ u$ L double temp[MAX];/ a H0 @8 y; P+ o
for(i=1;i<=num_x;i++) {
4 |) S) c: Q8 u3 P. \ temp=temp_c;
3 B& l' \3 M. l( R temp_c=c;
# D! I- n$ u0 |3 d/ N* R b c=temp;
* y. w; F8 ]0 {# @8 W' |$ h }
: ]) g/ l# ~8 w( [% n" _. w3 N" @}
4 s1 ]/ i% s) n% D0 ^, W' X% P/ C2 F" S<>void create() {( n4 G1 W7 c/ j5 I3 U
//输入方程组系数，每个方程输完后回显确认4 I3 {& y' D0 N+ |0 u
int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;
9 R" q8 y( A7 ^: ]2 C% x: t* I char confirm;
; H% @) t5 _2 _
$ Y$ u+ J) `3 Q$ | while(1) {
7 J2 F6 v/ J* x* s printf("请选择：1、求最大值，2、求最小值：(1/2)");
2 {: M! t# W n$ m scanf("%d",&ma_mi);
5 ~, x$ W" S- Z2 [: y s; F2 @* m( w if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");
$ ^5 S6 t: N. K! H# \; g- C else break;0 c) Z! ^) E( \6 h5 R: n4 l3 a
}
/ s7 A5 P/ }/ p 8 j$ K) T$ h, k8 m* `: A
while(1) {
: E( c7 Z0 V F6 _( ~4 J printf("指定变量个数：");
' E5 l! C' r4 r4 o) @! b scanf("%d",&num_x);' y5 }! z5 T( {3 H. N- }4 M7 d( V2 \/ @
 printf("输入价值系数c1-c%d:\n",num_x);# i( c$ T9 x( a8 a" E& `
 for(i=1;i<=num_x;i++) {
3 g2 H" n* J" \, O1 W( z1 Q# D printf("c%d=",i);* a+ D4 l( n$ |7 `
scanf("%lf",&c);5 C) y* k1 y8 L) Z+ y7 D( c
 }/ T. S- T% j. _3 q( W+ X* [& O
 if(ma_mi==1) printf("max z= ");3 u1 h9 S8 S9 r: D/ i. e
 else printf("min z= ");0 F8 f# B, X8 x( z3 I/ z- v
 printf("%lg x[%d]",c[1],1);
3 E. ~) Q4 w2 I* Z# h e9 w# p for(i=2;i<=num_x;i++) {+ f4 p6 X: c# d d* h l
if(c>=0) printf(" +%lg x[%d]",c,i);
" b8 u) E2 h, @7 [ else printf(" %lg x[%d]",c,i);
3 j" R; s7 p6 g) p r+ ` }
0 Y1 M& i+ j7 k, ~ printf("\n正确吗？：(y/n)");. r" E7 q8 H6 t7 j+ O. Q h
getchar();
+ @0 k2 c$ ~5 M$ T3 b confirm=getchar();
) ~ j2 U4 P$ e# z/ _9 v8 W if (confirm=='y') break;1 ^; l2 U3 b) J+ p V9 v
else if(confirm=='n') continue;
0 i5 z, G" y* [6 R- I }
% ?' P: ^( j0 X+ | H4 D<> printf("输入约束方程组个数：");
: o3 F3 }$ I) [6 D2 Y! p# |2 L scanf("%d",&num_st);( @# P' F: i( U+ P
for(i=1;i<=num_st;i++) {3 l! B/ a& v4 h3 h% L" H
 printf("st.%d:\n",i);2 j: ?2 K; X4 B- Y( i
 while(1) {" q4 Q: d8 A6 O$ I+ `# y; Q! \
printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");
, `) K1 s- A* G scanf("%d",&re_st);
3 d2 O2 r( S2 `! x' j2 k if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");& M2 u9 f, I, K
else break; A3 }- z& d5 z' [7 O6 m
 }
1 A% D5 m" b& Y- E+ [! N printf("输入技术系数：\n");" |: l$ q/ l: M: [
 for(j=1;j<=num_x;j++) { ( x- T" e- T( C/ |2 e+ L
printf("a%d=",j);
" H/ S/ e4 N; S scanf("%lf",&a[j]);* V) U2 e6 e o/ Q: K6 h
 }% @9 ]2 ]7 s( W3 E; O4 p- R; A
 printf("输入资源拥有量：\nb%d=",i);
. Q3 b, } x3 L scanf("%lf",&b);% b8 e \/ R, J) V6 o

 Z' T' `5 x+ d) x( E A6 D printf("st.%i:\n",i);' n+ p9 w$ z1 n! V$ L K
 printf("%lg x[%d]",a[1],1);# A) U" R) _& h, Y
 for(j=2;j<=num_x;j++) {2 g( W5 j A8 G b/ v- j/ k
if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);
' c; k( k+ W1 x2 F# q$ \/ \ else printf(" %lg x[%d]",a[j],j);
3 L \5 s$ ~- N/ b: C" I }
7 c+ O% q ~) X- y& g switch(re_st) {, m# w' g( v |
case 1: printf(" == %lg",b); break;7 F* y6 e, Z! [+ f8 U
case 2: printf(" >= %lg",b); break;3 u3 n, U) I/ ? ^1 W
case 3: printf(" <= %lg",b); break;
% J7 |) G4 N$ ], x% m* S }
' w; x" B) s& K! o( ?5 S) X<> while(1) {
, @2 V0 w( N5 ?; M7 D9 u printf("\n正确吗？(y/n)");
, a* N( I$ n4 w0 ~4 F! b getchar();4 x9 c0 y! K* X' _( x
confirm=getchar();
. `. I& x0 v R. y) q if (confirm=='y') break;0 }8 C0 E* r/ w
else if(confirm=='n') {i-=1; break;}0 N1 C' A# {% r* [0 C" }
 }
" T+ W* x3 C- n+ w: r, u: I }. E3 Z- Q8 }+ i4 @0 }
<>//显示输入的方程组0 ?3 Q" \: r4 c6 B& c% C0 ?1 L
printf("\n原问题为：\n\n");
' ^! S) Y+ z; ~% p# T' q3 f2 Q if(ma_mi==1) printf("max z= ");
6 c' ?- o+ \$ T2 J5 e2 r else printf("min z= ");: h- G( ]* o& b; S9 K
printf("%lg x[%d]",c[1],1);( b+ `& N8 G& W
for(i=2;i<=num_x;i++) {3 \) Z* z- H' F( B6 r: g ?6 ^
 if(c==1) printf(" + x[%d]",i);
& Y! l6 c! \, x; j- X1 B& ^9 S else if(c==-1) printf(" - x[%d]",i);
; g, @. T, l1 S! Q else if(c>=0) printf(" +%lg x[%d]",c,i);
& a2 V' V- z1 O5 @' L else printf(" %lg x[%d]",c,i);6 D9 y+ w# ?' ^2 l3 t
}+ `4 P6 _8 u L! `; ]$ y8 i$ x) A
<> printf("\nst:\n"); m# U+ {. G( G
for(i=1;i<=num_st;i++) {
3 h4 ^2 G6 [/ g g$ _ k=0;. p* q9 n7 J! q! _4 P2 G! `
 for(j=1;j<=num_x;j++) {1 F& h" }% F( v4 _% s
if(a[j]!=0) {& l/ {8 l/ o1 s: t+ |. x4 h
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
1 r; V/ [5 G$ @ else if(a[j]==1&&k==0) printf(" x[%d]",j);
( A9 Y0 u' C! L else if(a[j]==-1) printf(" - x[%d]",j);
) G% {5 m- ?/ g, O else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);8 `4 w; S0 [5 o6 ` v! P
else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);; W2 L j( C# F, X# E, `
else printf(" %lg x[%d]",a[j],j);
+ Q+ O* m* a$ o k=1;
" V+ B" c! P; ?8 m3 z- ? }6 b: i" d: I s5 j: T# }
 }
' N! M) r* [4 L) h! f switch(re_st) {1 U7 H' D; ?: ^- r4 |
case 1: ' h5 S' N; b4 I$ M
printf(" == %lg\n",b);
" Z& K5 I" D. C0 ]: O break;1 d0 {% C1 L1 G4 c) V6 x
case 2:
9 U: o& z2 Q% |& k2 j: E) K printf(" >= %lg\n",b);
4 A3 u, C( R' h; S0 r5 V break;
% X1 h9 ]' ]; r6 J7 J7 \! `# P case 3: & z, Q- E0 m( _! }/ m1 a3 n
printf(" <= %lg\n",b);
+ ?/ Q3 E. |) C5 c9 L break;
; @4 ?" k8 }% u# R }
* l5 j3 D1 |' f7 [ @: m" L }
, J/ q+ h2 Z- ` printf(" x[1]~x[%d]>=0\n",num_x);* H3 k' t" ~/ @
<> tnum_x=num_x;; ~2 A+ i5 L L* w' P, c
for(i=1;i<=num_st;i++) {
3 Z, i3 X! U1 M# }% H/ q) k switch(re_st) {
7 }+ G) x% O) R2 L case 1:5 {8 R0 `# ~" F1 o: w3 \
 case 3:* ^. j4 R- e s3 }* q f
num_x+=1;
* {0 H2 d' b% `0 h break;( J# d. r1 u- z5 W" \, }9 F
 case 2:
) Z* v& Y1 L4 K# n4 k; u num_x+=2;1 a0 n [" U, i
break;$ V- I& q8 a3 s: v1 S4 \# p
 }
; u- E% I4 ^* q3 h8 t) m6 l& X }0 c% |/ U5 O0 ]: L- z' l. j
<>//化为标准形式
/ j# d/ P' J6 y6 z# s* I if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数 N3 ?' Y. M; l# Z( ?
for(i=1;i<=num_st;i++) {* L$ i* s5 q! b0 E: R+ L! R
 switch(re_st) {
2 _9 T2 K e$ c0 k! h# [ case 1:
5 I6 E0 a; `* v- D# G num_addv++;2 I5 ~7 Y% l2 n: g6 O }
num_ba++;/ J+ ]7 P0 f( A4 t5 V& h9 @
num_ar++;9 ]3 t/ [3 _ ~: B
c[tnum_x+num_addv]=0; ~0 W3 `" _5 s. M' d
base[num_ba]=arti[num_ar]=tnum_x+num_addv;5 s& Y0 l: _: d
for(j=tnum_x+1;j<=num_x;j++) / U: R: r8 E( h: P" T) S
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;* H, c/ A$ x1 S8 c
 else a[j]=0;
) ^8 X) R. a4 @( S break;: l& z' r: z( t; D) W9 \7 u
case 2:- {$ G& i8 I# I( g% l) R
num_addv++;
- {$ D- {9 k! v c[tnum_x+num_addv]=0;; a v2 x @8 f2 J
num_addv++;
2 q: I8 I* O/ m+ k$ b3 W% d$ t/ P num_ba++;: T" Z% g/ b! g8 y" {
num_ar++;( z X' {) S& i; f' }
c[tnum_x+num_addv]=0; : G% U A! Q; Z0 k# m4 _6 X
base[num_ba]=arti[num_ar]=tnum_x+num_addv;
5 K) W- }; F1 u9 M! e0 H) k$ i8 S! g for(j=tnum_x+1;j<=num_x;j++) ( S# n9 B2 k& S$ {
 if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;
+ B v8 M3 b& ^ Z8 K, x! @* N else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;, h/ Q+ d* d3 v5 ^
 else a[j]=0; g3 Z7 @# O$ p- r
break;
+ S9 R* o% E1 b# }5 Z case 3:0 d+ {# E: x; E$ ~
num_addv++;. `, t1 a6 i- g& J8 b Y! i" s
num_ba++;% l0 T" u; C7 U, e, y
c[tnum_x+num_addv]=0;
5 n5 T# e0 s5 j$ B U* U base[num_ba]=tnum_x+num_addv;% e! l: a; Z, R9 o: D8 C' @5 b
for(j=tnum_x+1;j<=num_x;j++) 0 E2 H L: t0 h, \2 v S6 |
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;- v3 F6 S) o& Y
 else a[j]=0;
% m1 D2 r/ h X break;, b7 |3 D4 B$ O, Z3 g
 }//switch
- U$ I8 x/ f. n7 V }//增加松弛变量、剩余变量、人工变量、确定基变量
5 r, n1 \# N, K. J5 y<>//显示标准化后的方程组& T- ~$ d" z" k: N) U' l6 g
printf("\n化为标准形式后：\n\n");
9 E; D; Z3 E6 N2 _; D7 I if(ma_mi==1) printf("max z= ");/ f$ G$ I7 W( v; c- `4 D
else printf("max z'= ");
" x: Q6 s( h( C( G5 j% c' R printf("%lg x[%d]",c[1],1);& w# c8 x% U/ w0 e/ h! S2 `8 w
for(i=2;i<=num_x;i++) {
; }# Q# p: h: Q3 L) Q9 d6 r k=0;
6 K8 n/ [4 h: t for(j=1;j<=num_ar;j++)
$ o5 l7 y# a1 w( Y% e1 i if(i==arti[j]) k=1;
. V# O1 ?( r% x: }0 ? if(k==1) printf(" -M x[%d]",i);
" J) H: H- k' ^6 b( [ else if(c==1) printf(" + x[%d]",i);3 K; r0 I6 I9 k! c% `- U
 else if(c==-1) printf(" - x[%d]",i);
5 ~ H# u7 A# Q. W2 Y5 R2 |3 d else if(c>=0) printf(" +%lg x[%d]",c,i);
) H/ R9 z5 j9 @% F1 [9 H else printf(" %lg x[%d]",c,i);
; P' o+ p' L s! t8 x. k( g9 [. d }
2 B) J; R: x' z2 j+ e<> printf("\nst:\n");; c2 B6 A5 \; Q9 u
for(i=1;i<=num_st;i++) {
- x$ |4 z$ u. L+ n k=0;; u; G2 G9 A4 f
 for(j=1;j<=num_x;j++) {" t" o) L! Z; i5 v d" U
if(a[j]!=0) {7 P! c* P6 G8 I
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
( q& U$ h p) d+ W Z7 B( S else if(a[j]==1&&k==0) printf(" x[%d]",j);5 s7 m% ~ x/ ?, X, l- ?
else if(a[j]==-1) printf(" - x[%d]",j);
, e+ O3 c0 v4 r% {, I% i. y B else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
% `9 H! e1 q" f else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
0 @' Z- g6 e2 c! W else printf(" %lg x[%d]",a[j],j);% x( o4 w3 b! [# s O
k=1;
8 g O* y, j+ F$ P% j }
2 s, B8 V/ q" @' ?" D }/ `* Y5 m3 X9 i+ o# k
 printf(" == %lg\n",b); % P) F1 c3 C' d7 a
}% ^% v g" B' F. N
printf(" x[1]~x[%d]>=0",num_x);! s9 k) w* ~- w) c+ |1 u
}
# o' L$ z* M+ m" `4 n<>void iterative() {
8 E$ N- i: A8 t4 \ int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果
" E7 V/ c6 m/ X6 O. g' D0 }4 [' D& R int base_elem; x1 B4 Q5 }4 O9 e1 b" ?
int base_out,base_in;: O/ w. b" j9 m: x4 `
double sigma[MAX],temp;; _& Q# q. l+ N1 W, N3 }, f, C6 y# {
double value_be; //高斯消元里保存主元素值. Y3 Y5 R/ x1 n: Y# Y
<> printf("\n\n第%d次迭代：\n\n",stop); , u0 ~ A8 X! H9 O2 b5 o& r
for(i=1;i<=num_st;i++) {3 B+ C l- \3 D: g+ e2 X0 [
 printf("c%d=%lg\t",base,c[base]);
7 C+ f) S- v! @ printf("b%d=%lg\t",i,b);
+ N3 s9 x7 } c! c<> switch(step) {3 p! V8 L& w( [; p
case 1:
$ Z' _0 r3 ~: X3 t for(j=1;j<=num_x;j++)& {3 [8 p, \6 U7 ^* i2 R
{
7 p9 t) }" A4 ]9 H3 h/ g2 ?0 D3 E printf("a[%d][%d]=%lg\t",i,j,a[j]);
8 F. I2 A$ p7 D! ^1 c$ o: \ }
7 {) ^- ^2 S2 w printf("\n");
7 y( R: H! P$ [7 l1 g break;
1 y {6 |' a% G0 t! H case 2:7 T3 a; C7 J7 U+ {
for(j=1;j<=num_x;j++) {
7 N0 y; v5 p" S; i" ` k_a=0;$ e' M2 x& K& h, D
 for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;
5 a+ V9 m$ Y0 b! A- k- Z+ A1 r if(k_a!=1) printf("a[%d][%d]=%lg\t",i,j,a[j]);' p1 S1 F: c( G D
} p; Y- A y9 y' U
printf("\n");. V0 N. L; }+ t9 s" m
break;
6 a9 v2 C/ i: T ?1 R }
3 X! U& a! |' Y. y* \( z6 | }' ]# y+ C. ~5 e o; h, a
//求检验数sigma
: ^5 E" V5 g3 `5 I& a+ E" R for(i=1;i<=num_x;i++) {5 y' M# N" b! n6 p& y+ Z. q
 sigma=c;4 s$ @5 G( i* v6 J, M/ m
 for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];
4 W: ~+ F, @ c; T B for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;
/ H6 @ B: ~& Z2 A8 E switch(step) {
) Z4 w9 M! Q3 x% F2 w. \2 W case 1:
 B; _5 s; I6 B2 f1 y; _% _ printf("sigma[%d]=%lg\t",i,sigma);
6 Z, s3 s) \( N break;# y1 t! }* E! v. a# q1 ?
case 2:
& c, z7 l/ g$ d$ k! }6 D k_a=0;& p. Q q) V3 u- E- T4 H* Q# g
for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;$ C: k: [' k1 y# H# H+ E
if(k_a!=1) printf("sigma[%d]=%lg\t",i,sigma);
- W0 }7 M+ h8 x break;
- _1 n0 `' Z+ A2 @6 J4 T4 s" ?/ C }6 f5 x% k: r2 l @
}0 X6 ]3 p9 X% @7 v2 R0 Q4 V) a
putchar('\n');
6 H$ Q, J; I, U9 h//检验检验数sigma是否全小于等于0
5 v; | b4 \4 I7 O k=0;7 H4 Q5 w o9 z
for(i=1;i<=num_x;i++) {
. J0 r, E$ s3 f8 Q2 D' ? if(sigma>0)
; [& Q2 o8 J# k) R( P+ Q k=1;+ o: E8 @# }% X
}
" o; }. \8 e6 c, |7 [. s if(k==0) {* n" l# ~- h% Z* j
 //sigma是全小于等于0时，检查是否为无穷多最优解
8 Y% w% c& n% G; G# @ for(i=1;i<=num_x;i++) { 0 r& f% f" f; \, K
k_f=k_a=0;3 y# Z0 b! E) e: {, ~& u& E
for(j=1;j<=num_ar;j++)
! n- r8 D: F. H+ c# z if(i==arti[j]) k_a=1;
- p4 u+ V1 w+ `% H. E2 n' | if(sigma==0&&k_a!=1) {
9 \+ p- `: ~" {6 ]) ] for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;
9 [& X9 }, l/ m& r ^: {7 L if(k_f==0) {status=-1; return;}5 S" c, n" k2 b$ S6 E' \, d
}2 V' {! |/ b7 X k2 ]
 }, R* H* i/ X1 ^/ F0 y4 ?+ h, Y
 status=1; $ J F; o8 [. [3 d
 return;& n5 n/ S! `1 ~8 O5 w0 m/ _& F. z, |
}
% _: {% b* S* C- j//检查是否为无界解0 r# |2 W+ u( F' }/ { ]
for(i=1;i<=num_x;i++) { & f( Y: g% U4 g* k0 |3 D
 k_f=0;
0 \' J# f2 e) F if(sigma>0) {; X9 Q, x1 }5 V2 V) n
for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;
( x" j# J: ?/ L/ ^5 _ if(k_f!=1) {status=0; return;}
$ V* G. M) \2 ]$ T+ W# } }
1 Q1 j1 T* y) I; p( s2 H' R! N }4 E6 D2 Z/ q2 n U* y4 C6 ] d
<>//确定换入变量
; o8 k" S8 n' ^" B for(i=1;i<=num_x;i++) {
! q3 G" \3 L2 N; H* O k=0;$ q2 h! K5 N+ j& P3 t
 for(j=1;j<=num_st;j++) if(i==base[j]) k=1;
/ T5 y, T* g v, s6 [) O; l if(k==0&&sigma>0) temp=sigma-1;
# g( U: m1 _$ L7 y }//temp赋初值4 s% K- |2 W/ M1 h% [! o
for(i=1;i<=num_x;i++) {
& M1 D8 ?# b/ g/ L k=0;
6 O: u1 l+ c$ {1 Z; W& T for(j=1;j<=num_st;j++) if(i==base[j]) k=1;
2 P' K6 v m& H) z1 { if(k==0)
: Y( B2 ~4 ?1 X6 o if(sigma>temp&&sigma>0) {
" k/ x. [! ?4 h8 @3 E) f9 [ base_in=i;
& D/ m9 ^" d! V" B! v temp=sigma;
5 A! I& E' X2 K) X' i2 ^# m2 i }
& u! W+ r& w* h9 F }
( E& F# c5 j- v# b, |$ r4 V<>//确定换出变量: O( d3 V* X A/ f- ^6 n
for(i=1;i<=num_st;i++)
- D/ D/ C( c. i if(a[base_in]>0) {! f; Y- ^, c) L6 h$ N
temp=b/a[base_in]+1;
3 C! r: u8 Q+ J# U break;& }7 X, L: Z: Y8 p g
 }//temp赋初值! L3 x- O! k w6 ^. b' z% Z: J* j ]
for(i=1;i<=num_st;i++) {
. r) a6 Z8 j M8 a: V2 m if(b/a[base_in]<=temp&&a[base_in]>0) {& e6 q. z/ I/ [4 b2 c. P$ M' F
for(j=1;j<=num_ar;j++)5 x* U$ y+ t) J/ [
if(base==arti[j]) { ) V4 v2 c6 m4 h/ g% p1 T1 U4 F
 base_out=base;
7 m! W0 {) a4 q* q, ^: { base_elem=i;( @3 ~+ d U+ w" d
 temp=b/a[base_in];
0 _ z" |* W: N0 o break;
4 P& u2 |" U6 x1 a, `" s) _ }
& D. q# E. |, ^; d& D }//人工变量优先换出5 n3 o2 M" j+ {& ^" _& ?) Z( ]5 y
 if(b/a[base_in]<temp&&a[base_in]>0) {
8 U$ V, P6 u0 R* r base_out=base;6 i; O" B( s* d% s) Z. W- W
base_elem=i;
+ K5 g1 l; A* e) N# ^: X temp=b/a[base_in];3 m* @! h$ `- X7 f# O
 }
; K# e& o, g, q }4 j, l, T) T0 q
<> printf(" 基变量：");
6 D3 ~* t( h) I% S2 L! q2 s- Z1 l for(i=1;i<=num_st;i++) printf("x[%d] ",base);
( U- |+ c1 v$ @, e: u! c: J printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);
, k2 ~, c( ^, c" V1 f$ g//基变量变换，进行新方程初始化后迭代
8 g; L- Q- v$ {0 `% S0 Y# [/ \8 i for(i=1;i<=num_st;i++) {
& { {) W: ?6 f: Q$ c* F7 y if(base==base_out) base=base_in;7 X2 p- O1 \1 $ o U
}
' [1 e- ~7 ?2 Y/ R$ ^# $ b//初始化主元素行系数
- B! g4 A! v. Y2 T value_be=a[base_elem][base_in];4 z |, t9 Z5 |8 @7 I( A
b[base_elem]/=value_be;$ D0 D i/ B- I- b' P7 N
for(i=1;i<=num_x;i++) a[base_elem]/=value_be;* u q; d# Y+ ]3 Z! j. j7 L% ?
<> for(i=1;i<=num_st;i++) {
+ T* U- D/ J3 ?- O if(i!=base_elem) {. Y/ p3 F! P3 u7 n: a. e- m& [# D
b-=b[base_elem]*a[base_in];9 b4 g- v( F- y0 P ^# M
value_be=a[base_in];
& U! s2 R& b# [ for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;
# }$ g2 z+ }; E3 w' Z) R }
2 o3 h" ?5 b% I3 n, I7 O0 G } o9 d" h- m' B
stop++;
+ H' ]2 @# W9 C! |$ K& j" x if(stop>STP) {status=-2; return;}- S; `) @0 n+ B+ S
iterative();
( J# q# r/ Y- a2 I}: d% D+ X: a2 f4 \7 i5 A& {2 U6 `! y" b- r
<>void output() {) {) o2 T* D7 T M8 B" g
int i,j;6 u1 k1 T0 t4 {/ s( q4 g
double X[MAX];; z" B6 H9 f0 M# X8 M& t
printf("\n结果如下：\n");& S: d D5 S$ [( k
printf("\nX=(");6 l$ I1 S7 ?/ x7 c" \* z
for(i=1;i<=num_x;i++) {
7 r! ^; S+ B; X: s6 f* [1 I6 V: r for(j=1;j<=num_st;j++)
1 p( k4 g1 G/ E% @1 Z: u: d if(i==base[j]) {X=b[j];break;}
7 a4 ]) P/ k3 W$ p else X=0;
7 p" I! r5 H* i: @6 c6 ] printf("%lg ",X);* m+ k/ L5 }& I l0 y1 J- r1 {
}2 ^. U/ n: n. f8 j m
printf(")");4 V7 @; @8 c9 Y4 I8 x$ C' c" H0 z& h& q1 y
for(i=1;i<=num_x;i++) max+=c*X;$ v% k, ` R: | R
if(ma_mi==1) printf("\nMax z= %lf\n",max);
, n( X: o2 w7 A9 K7 F else printf("\nMin z= %lf\n",-max);# B% U1 Z) c( P4 d
}
作者: sg47 时间: 2005-5-12 14:16
好详细！
作者: yqm10507 时间: 2005-5-12 19:50
<>very good.Well done.
作者: tw1982 时间: 2005-5-12 19:58
先谢谢了，我看看能不能用
作者: tw1982 时间: 2005-5-12 20:07
我用.net要出错，能不能提供一个.net的啊
作者: winzipftp 时间: 2005-8-29 11:55
是你吗？thunder？帅呆了

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5