数学建模社区-数学中国

标题: 求助：单纯形法的程序(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;2 j2 F2 g; B" K5 P$ g
leap1:
4 {# [6 z+ B+ v% U! Z0 \9 e if(l1-1==0)
* t) ]9 I. I) }7 T xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);
7 q( ]( } |, X else
# ~6 s8 y- d N/ q6 Q- P a {
' B8 u6 U) f; T; B( zleap2: if(l1-50==0)7 l* ]; P) \& f6 z$ @/ A
 xi_max(&m2,&mn,&c,&n,&m2,&j0,a);9 Y% ~& `/ Q3 N. H+ \
 else! e. Z; b, J' p6 `2 P; G6 r
 xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);
' k- Q; C2 n' E8 I- | }8 D- Y# Y6 o" T% e: K" \: b% ]
c-=1e-8;) b. Q. q# j% H! q
if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))
! _2 I( k7 h" i5 o {7 g/ h8 _% c+ m
printf("\n\t*********Not min&&No solution**********\n");
 K: h# P) Q4 D$ g$ c return(-1);# h5 |9 p6 |2 j& b
 }
. C# D( Y n- } if((c<0)&&(l1==1))
9 {! D r) _; t! w: ^ {
' Z) ~) ~7 u s# Y0 t l1=50;4 ^( h, f1 o9 \0 a
 goto leap2;
% A5 i9 a! n' e }$ o+ Y6 L Q6 L8 T8 o2 Y
if(c<=0)
" h: x$ F/ o) I: I2 g1 T% A {
; F$ q# `5 }' z for(i=1;i<=m;i++)* h8 \2 }$ F- Q: _' }1 D- U
 (*x)=(*a)[mn1];& R8 u, I. z! G* U1 T# S' K
 printf("\n\t********Optimal solution********\n");
& b- p$ @" W/ f" `: h* m; i for(i=1;i<=m;i++)) q; j: A! z w n6 z* X
 printf("\ni=%d,x=%f\n",(*k),(*x));
4 G# \- B! R1 A* ], Q8 @ printf("\nF=%f\n",(*a)[m2][mn1]);& k C7 j, o4 K' V4 ]
 return 0;
/ u; L2 g! g" p: M" E T% {/ Z }
 M4 j3 O# i6 x" I9 ? c=1e8;
; g0 |! X2 Z4 N" ]; D5 e, x, Y for(i=1;i<=m;i++)
0 A2 a p, ?: q: ]" y {
' t0 {# [) N: ]: e: G2 l" O if((*a)[j0]>1e-8)4 T' C5 d" A6 K6 ~
 {
# @" {" h9 B$ Z. Y3 A g=(*a)[mn1]/(*a)[j0];
+ Z1 T% o2 R* a: d! F if(g-c<0);
( o8 @/ J5 ^8 X3 x. G! s' ? {2 d2 D/ J) c& L) d# j
 c=g;0 [* Z T. b R: |2 T, x
 i0=i;
' ?! u6 u; R, c8 Q f }
* m) M* @5 \' j' F2 W! M, \, @* Z }
 E" E+ w7 W% u) i' B. @. @ }
/ E7 L9 t& n8 q if(c==1e+8)
% y1 y$ S# d$ Z {
* S9 A+ J" p' w- [, B printf("\n\t*******Lp no solution********\n");
+ K" a& f0 r" b% G% _) n return -3;
( o. O# ?" a# B/ b* I+ h }
" l2 {9 I& V g) K f- c# C" \ (*k)[i0]=j0;
4 K" r5 Q3 d" [: L } for(j=1;j<=mn1;j++)' U/ Q& }+ C6 \' M# i- F
 {
# Q/ M. `1 a; c" M$ P- J, o# p if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))
7 u0 a9 ^: y& m" }5 a9 _& |! q continue;* z! X, H, x- G l
 g=(*a)[i0][j]/(*a)[i0][j0];
5 t& f1 S( h' [" x: k: m (*a)[i0][j]=g;9 M. c- Y4 Z' h+ w/ Q; \# N4 Z$ w
 for(i=1;i<=m2;i++)
( v% o y6 }/ g5 O' {, {$ u$ c6 w {2 ]6 {* _* Z7 A
 if((i==i0)||(!(l1==1)&(i==m1)))
: y# e- l; g* E$ O continue;9 W. s. u7 a2 O- s5 |
 (*a)[j]=(*a)[j]-(*a)[j0]*g;" O* N9 m" f. w* x+ I
 }
5 B- U* P4 r3 Y4 p }4 v: t, H( i% k5 T9 ~. B. w
 for(i=1;i<=m2;i++)
, t- c8 R5 L0 \* m% q# `, } (*a)[j0]=0;% k! g) C* Y1 ]3 e+ p {9 N
 (*a)[i0][j0]=1;
" Y9 s) P2 j: Z' c goto leap1;
' y7 W' j. P( q4 e' v2 _8 P} 7 i; c4 L; u4 ?9 P! h& p
main()
% `" t* |" E# ]5 G{! \% `+ [: B0 y5 K% [8 e$ ^2 Q# G
 float a[5][7]={{0,0,0, 0, 0,0,0},6 q# ?* E0 H( z: O! G6 A; w& E3 E
 {0,3,-4,3, 1,0,12},
' [: _* j) _: `$ s {0,3,0, 6, 0,1,12},/ F4 r9 n& f+ E, v! t, P
 {0,0,0, 0, 0,0,0},$ L- G V3 _; G
 {0,69,0,144,0,0,300}};
 u" K5 e4 C% B/ b% _. ~, a int k[3];' c% c* n. S5 N
 float x[3];
% o. F. W- M' s4 H" | clrscr();
4 \; z6 @/ |; ~9 j# S+ T% G4 t xi_sm(2,3,4,6,0,&a,&k,&x);" x( V; N) t3 ~' B* ^* Q* ?
}$ d4 T8 [* C% f" X

作者: plgatc 时间: 2005-4-25 18:00
<>/*************************************************************************
3 K. A) f3 F; |7 \9 D* V 单纯型法解线性规划问题（两阶段法） ( x+ s* s+ ]) V+ [

 V+ U2 g- Q# q1 n! S 编程环境：VC++6.0 & r& O6 Q( K; a$ M: S
方程组输入说明：
1 B, D; X. ^. l" S$ K 变量非负，按提示输入相关参数。. w/ y( h7 b8 r# l# l P4 s* f0 y- ~
*************************************************************************/
/ U4 L- [; h6 c2 I3 i) D8 B#include <stdio.h> N+ N& \6 t* G4 h4 x
#include <stdlib.h># z- u' O+ R: w* Z8 r4 i6 v7 p, z
#define MAX 100
2 B+ n7 ], i Q5 ^7 P#define STP 100
" E. H" s& B4 Q; e% \<>int stop=1; //迭代记数变量7 U, R# Q: z* R Q. ]9 }
int status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数% `% J3 ^- |# u& k$ E" G* {, R h
int step=1; //目前阶段
$ `& T- A8 W/ V* Q$ y5 E$ U$ i3 r<>double a[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0; //方程组相关系数6 f* J' Q+ k( ?: M1 {2 A
int num_x; //变量个数
3 H! k/ v' c. y& R, B! N) f( rint num_st; //约束方程数
$ y% F6 v$ L9 l0 z7 m9 p3 R8 ~int num_ar=0; //人工变量个数. Z% P' ~( a+ ?" l# O
int arti[MAX]; //人工变量下标6 j' J/ A, \0 Q. H) M
int base[MAX]; //基变量下标
' ^# H ~2 w, U, x* Fint ma_mi; //1为求最大值，2为求最小值
7 [: E7 A! ?" W" r+ t<>void create(); //建立方程组( R3 R& s! i3 s' B; s% S+ `
void iterative(); //单纯型法迭代 E" `& i n7 B) D) U
void output(); //输出结果
: r0 C( i# C, P4 W& X3 L. I mvoid banner(); //打印程序标题
6 c& B) W& |" H H" J! J, uvoid exchange(); //交换两阶段价值系数/ e w) ]' |. P1 g+ |6 k z
void show(); //输出方程组
2 @3 \9 u1 J% J, y4 N. A* C<>void main() {9 i9 o" d& m! `0 Z& L
int i,j,k;+ s0 N6 W1 [. b6 P
banner();: ?& Z% ]5 r& ]' h1 B8 t& x) S
create();8 E7 S" ]4 A# n
//保存原价值系数，转换为第一阶段价值系数
- j9 G, J& k- {3 W8 J for(i=1;i<=num_x;i++) {
9 m% J+ [ {3 n& v5 ~$ K/ _ k=0;6 i) K: m- Z& L1 L
 for(j=1;j<=num_ar;j++) if(i==arti[j]) k=1;$ o& z3 q2 L9 i# @. Z1 a$ V7 b" q1 x
 if(k==1) temp_c=-1;
! H, t5 h. Y9 V( } else temp_c=0;
) g) R+ c* c( ^+ ^8 q }/ z& c! ?; a3 \1 X0 r0 ~
exchange(c,temp_c);% B0 E' V' w, E s- a; q5 W
<> printf("\n\n第一阶段问题为：\n\n");
( d) _: y" ~6 k2 h5 c+ ~) N show();4 _5 g1 _* F3 w( e8 Z" d
step++;9 J* p8 E: [/ F' i0 _" C
printf("\n\n按回车开始第一阶段迭代");# r- Y7 B1 u$ T
getchar(); ' d0 P% I7 N$ |! F9 {- L. p/ ?
getchar();! Y4 X" c) \" u |3 N5 i
iterative();
5 R" T& J. U7 F' ]% n4 Q2 ] if(status==-2) {9 [! ]1 a/ B# p& r8 i* Z
 puts("迭代超过限制次数强行终止！\n");
! i; ]+ X) O i puts("\n按回车结束");6 I/ Y' g; E( _0 m
 getchar();. Q! n- v- x( f6 K3 o2 k
 exit(0);! R- B" \ @3 h* \
}7 p$ G+ a6 V* [3 G2 q( y
output();* N0 W) u0 K7 Y- a1 a5 j/ R: _9 m
<> if(max!=0) {% }0 u( d- E+ Q* b
 puts("\n\n原问题无可行解。\n");! n% d- ~4 P! y( {! ?6 Q
 puts("\n按回车结束");
, y r" c# P1 h |( P$ y getchar();
2 g! a9 T- E H- L( i$ O exit(0);
; |/ ]# c2 k$ V: I& c% m1 e }+ v" _( i: d" U7 B
<> //转换为第二阶段价值系数
5 U: }: o; w1 x2 J" l, M) x; c exchange(c,temp_c);
9 h# [. N/ m; g: N5 F* T+ Q //把人工变量列全设为0# d+ m% f5 F5 @6 T8 ~% T
for(i=1;i<=num_ar;i++) {- W( V* f w! Y0 U
 c[arti]=0; Y2 Z' B z; e/ e7 M! E
 for(j=1;j<=num_st;j++) a[j][arti]=0;
& y* w1 g+ S. }: R. V }- N& b4 z) \% g, T$ Y8 ~
<> puts("\n\n第二阶段问题为：\n\n");
3 w" g) r: w0 Y. ~. Y+ d6 q' F# } show();$ X0 o- P3 O# l; s+ F; A
puts("\n\n按回车开始第二阶段迭代");2 m- [9 u2 k' e
getchar();
4 ^2 `, r1 P4 m; q3 U iterative();
& I' R$ A7 i$ y2 m& o5 O' \; U5 s switch(status) {) |, H3 K) h. d: r; p8 W5 u y
case 1:
. M2 _. m; `& _ output();" O5 m+ v1 z) a4 B4 o% ]
 puts("\n\n原问题有唯一最优解。\n");
$ I1 s) u9 q$ G* W puts("\n按回车结束");& ^: V( [$ E- q6 b {
 getchar();
0 E" P& G: s L( U- c5 h exit(0);. a$ w& j! O3 \: Q4 b6 [
case 0:" s8 H! ?) Y9 s8 I
 puts("\n\n原问题为无界解。\n");$ ?8 M! b x; |7 s8 R0 j
 puts("\n按回车结束");2 C. }1 ^0 o& t
 getchar();& X+ X: n& `+ D' S1 h4 ]
 exit(0);' W) X2 D; h$ N' |) p3 U$ R
case -1:3 L$ D* I! S2 P: c4 X7 C |$ t
 output();
' o5 }0 L* {2 u7 G J puts("\n\n原问题有无穷多最优解。\n");
) Q2 U% M' D! R% p puts("\n按回车结束");$ a- G0 o. t9 i& J9 q3 v( M
 getchar();) ~. `4 S& U* W, l( _' x
 exit(0);9 n+ q; D8 g+ }' g) z& V+ y x& v
case -2:% M4 c' q o7 s( p7 u& X
 puts("迭代超过限制次数强行终止！\n");$ K( {: ~! e$ |5 z2 Z V2 p
 puts("\n按回车结束");
9 b; W5 a/ c/ m( ~# {) N getchar();
8 z" c" l/ G% H: }: t5 n exit(0);
2 |2 V2 T( l, {! ] }//switch
2 o5 \5 v% l0 Y% X0 U0 F" e; o}$ e: {) k! k+ {
<>void banner() {; s, E9 G$ @0 {' ]
printf("\t\t****************************************\n");
& t* i1 x( T, b% s0 `8 z printf("\t\t 单纯型法解线性规划问题\n");
& {* p. u5 r8 I0 y2 J, N. u printf("\t\t 作者：Thunder\n");3 T5 ]4 a8 f8 k: E+ u' q6 K8 w
printf("\t\t****************************************\n");; S) U; f: p n2 y( f4 v
printf("\n");
3 j3 m. C& [* n8 O& ?. ^}7 l$ w h& j9 p8 p5 I) z
<>void show() {' d0 z7 T8 c' T% I- T m7 f
//对方程组以自然的格式输出，系数为零的x不显示
: Q% S# r. X3 Z1 }//为1的不显示系数1，-1系数只显示负号+ P* C. ~( T& o8 e; i# @' j% K9 Q
int i,j,k;
9 {, u' s, H* Q$ D, T: { switch(step) {
5 W# L, @! H L7 @3 s case 1:
# _. P% S, D/ Z( d, ?4 \ printf("min z= ");
1 [" b+ x$ M& h9 o g printf("x[%d]",arti[1]);
* V' h" m' Z+ p4 W5 z for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);
, v7 {# p( D3 P V! ` break;/ {" ?. S% s; R" z$ [3 g( L; N
case 2:
) V& m; ?9 L) Y' j! k, I4 N7 E printf("max z= ");
, R) V+ `) [" B1 W printf("%lg x[%d]",c[1],1);$ q) u# V; I6 d4 U3 }) M/ u
for(i=2;i<=num_x;i++) {
1 h8 W7 \$ P) d6 d8 F5 u1 A- Z% Y N if(c==1) printf(" + x[%d]",i);, L5 `5 N+ f5 W. P" o
 else if(c==-1) printf(" - x[%d]",i);
3 _7 u* C x8 j+ j6 r else if(c>=0) printf(" +%lg x[%d]",c,i);+ V3 I5 b6 `. _$ w' p2 k4 S
 else printf(" %lg x[%d]",c,i);+ k, [8 L. _3 S1 k
}( ]8 [: z# _% n1 Y; N
break;
/ H. H( \* h' f0 l. J }
+ B: H1 A1 e5 P<> printf("\nst:\n");( J* e' v( Y( W, v2 y
for(i=1;i<=num_st;i++) {' M5 L% d+ f2 Y. }+ ~
 k=0;
6 a2 k; o+ i$ k) [/ k5 T- V for(j=1;j<=num_x;j++) {
5 \$ C$ r0 o; M* Q' P5 Q( u if(a[j]!=0) {+ s) ~' |5 A# V/ U r( ~) W9 V+ D
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
) K* Z" }1 P, F$ X" H else if(a[j]==1&&k==0) printf(" x[%d]",j);9 F9 t8 n" o, V% R3 {' Z
else if(a[j]==-1) printf(" - x[%d]",j);
1 P4 h2 i K O2 n/ z% m$ V0 N9 I else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
, a& s3 \7 I3 ~. k, S else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);7 t; c/ U9 S2 a. x7 o5 ?
else printf(" %lg x[%d]",a[j],j);
7 B2 X b2 \0 ^. J; d k=1;
% x. F- y2 T2 z! k3 K3 \ }: w: i d7 ?5 Z, L; k; c+ Z
 }1 a9 m6 ?7 p& e
 printf(" == %lg\n",b); 4 A, v5 e9 K: r2 L2 w
}6 n n1 m9 C; e
printf(" x[1]~x[%d]>=0",num_x);) W$ b7 a( v! v1 i
}# {/ T7 h' S8 _: ^
<>void exchange() {& Y% k8 z* ?" J9 S" T
int i;% h# U% [! U' J5 P: s1 ~
double temp[MAX];
9 t( y, D: u, b% T$ V* ?8 L for(i=1;i<=num_x;i++) {
8 x% N& R% ?( ^; n temp=temp_c;3 Q1 G F: j- {& O$ E: y
 temp_c=c;
& y4 L& j" v+ ~# b: C* W7 f4 N c=temp;2 t+ S. S j# }0 d* i9 H; S$ }
}
7 z7 X$ v6 K& x5 l6 k+ r}
9 w' f& ]( M3 I<>void create() {2 w- ]5 Y' b5 C# U% `% y0 t" n. D
//输入方程组系数，每个方程输完后回显确认
4 e, F6 z$ _/ i6 q3 O! O* I int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;
5 J6 \; r) ?# H6 U$ R char confirm;
+ U5 ^8 g2 f- i9 r
' Z$ p! y! r5 g) O" y. P while(1) {9 W2 b6 M! E- _1 w+ S/ v
 printf("请选择：1、求最大值，2、求最小值：(1/2)");
/ D. y5 \/ L3 ~8 Q+ i Z7 x9 | scanf("%d",&ma_mi);+ h0 H; Y% C5 y8 b7 Z8 X
 if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");
5 }4 P% }- s8 l4 u else break;% e) L3 W" u( ~8 F1 p" [' c: E5 i
}9 O: U9 i$ r/ x

* v; V; q5 M+ C: g4 W. J8 w7 c% g while(1) {9 I0 g6 w2 T7 @5 a4 ^+ y+ L4 v
 printf("指定变量个数：");+ H; F5 Y: v; a6 z- c4 K" V% D
 scanf("%d",&num_x);
9 `9 F, W5 F5 ~# I6 V0 g printf("输入价值系数c1-c%d:\n",num_x);6 M; _* A3 u2 w0 i
 for(i=1;i<=num_x;i++) { # D% Z) D) v) O# W1 ^
printf("c%d=",i);
9 P4 `4 @5 \3 V# }9 S- {6 `4 T4 x+ E scanf("%lf",&c);
0 ?! q* X1 U0 O. }( m! f8 A }- H$ U, D! O* y+ ^4 v/ [' N4 c
 if(ma_mi==1) printf("max z= ");5 ^! t/ X( w5 S' W. `4 A
 else printf("min z= ");
; ]- V4 H* @. J$ z8 B; W& o9 w+ @ printf("%lg x[%d]",c[1],1);
5 O# a" t9 l$ Q8 `2 K for(i=2;i<=num_x;i++) {
7 l4 Q! `7 F r( s! ~' ^! t if(c>=0) printf(" +%lg x[%d]",c,i);9 S" k3 }6 R4 s
else printf(" %lg x[%d]",c,i);
$ L2 a/ V T6 {9 P# P+ U }+ H. h$ p ?. T- _' R& E; W
printf("\n正确吗？：(y/n)");8 {4 ~: R' B% L4 K c( w4 U9 F+ U
getchar();
: N9 _& @6 k* `. Z confirm=getchar();
7 |3 g- @; Y9 E7 K if (confirm=='y') break;& \* P* {3 r& Z( j
else if(confirm=='n') continue;
# L. |% U+ E- h+ T$ Q/ n; E( Z Y }' h; B8 } d# U% D* a
<> printf("输入约束方程组个数：");# p, @! S" w% U3 o, t' ^ }
scanf("%d",&num_st);
7 y1 q0 K7 C( |! n! W for(i=1;i<=num_st;i++) {; R& H T/ g( g- C
 printf("st.%d:\n",i);
2 |5 i4 e( u5 v1 s" C: s6 ^& v while(1) {
2 Y( M( ^0 [7 s8 } printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");- V* V! d7 P! [* X& \7 x
scanf("%d",&re_st);
8 e0 x7 ?! K0 x9 L9 g3 [1 E if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");+ X/ _* q9 Z% ?0 n
else break;
' c$ h( j. D/ K+ K5 O% v/ X }' ]/ d+ t) q/ g1 L8 h5 S
 printf("输入技术系数：\n");
* W {. w2 l7 U- G: d' j for(j=1;j<=num_x;j++) { 7 w, l# z& h) s$ v
printf("a%d=",j);
9 U8 O+ L, @2 F# B! G scanf("%lf",&a[j]);
7 V& \# }( h3 U* n }$ x# K& l0 m6 I8 X2 t" R
 printf("输入资源拥有量：\nb%d=",i);6 W% ^& U; Y0 I0 R( W' m$ S
 scanf("%lf",&b);
+ @/ Z# w- W8 D3 Z" L
. L: Q. ]$ U' o( X8 f( h) s. K7 I4 i printf("st.%i:\n",i);9 g/ c: E) i& {/ Z6 {
 printf("%lg x[%d]",a[1],1);( M3 ]. ^5 E: d" d0 g
 for(j=2;j<=num_x;j++) {
' A F u; g+ t% I- E if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);0 Z! ~+ ^; {) `
else printf(" %lg x[%d]",a[j],j);
4 V: i9 Z b- x, [ }5 A* p: d. g6 a5 n2 W
 switch(re_st) {
3 X0 N% [) Y+ G& F( R case 1: printf(" == %lg",b); break;
( K# K2 `8 O0 q8 v* g6 I6 \; u case 2: printf(" >= %lg",b); break;0 o! F4 b( c+ n% m3 r* ^
case 3: printf(" <= %lg",b); break;
0 {2 q: [% R" K+ E$ B. I* i }" b, D2 C" ?& p0 e# y }6 w/ z
<> while(1) {
/ r6 \' _% r9 E! x" e printf("\n正确吗？(y/n)");& \& Z6 t, Q8 p' p# M% t
getchar();
0 z- @' N3 I% F: Z6 B: w2 P# a3 k/ Z confirm=getchar();
; S7 H% `, ?( J3 ]3 ?& g2 f if (confirm=='y') break;
4 |: S9 D. Y+ {# Y else if(confirm=='n') {i-=1; break;}
. f/ Z# c# ?$ K4 M: U* [8 Q }
; Y: X7 l( q9 [( U+ k! y9 ? }" O* y2 B8 @2 k+ U# ^; z1 D$ n4 p h
<>//显示输入的方程组
2 r2 Y3 l7 M2 w( p printf("\n原问题为：\n\n");8 t; y. X6 _7 U ?0 N
if(ma_mi==1) printf("max z= ");' n8 `9 u9 P3 h7 W
else printf("min z= ");
' C0 D% g$ P& L2 j: s printf("%lg x[%d]",c[1],1);8 }3 j8 S8 Y f
for(i=2;i<=num_x;i++) {
1 M! ]0 Q) Y6 x" G3 l# H9 z& u if(c==1) printf(" + x[%d]",i);
! J9 p& y* A; P; {" S else if(c==-1) printf(" - x[%d]",i);& D A$ X0 X, z6 U
 else if(c>=0) printf(" +%lg x[%d]",c,i);. h2 j( e! a3 h8 ?
 else printf(" %lg x[%d]",c,i);# m" J t3 t0 u
}* g/ o( [ n* X
<> printf("\nst:\n");1 w7 b) C- @" B% P' L/ f
for(i=1;i<=num_st;i++) {
1 l( Q1 K, t( Y% ]( W1 ] k=0;
 n& x. [" h7 S+ j3 q" k for(j=1;j<=num_x;j++) {& ]8 w* k6 f8 n4 [! ?# a3 y
if(a[j]!=0) {4 y/ q" f' c8 X* G
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
" E0 a. s1 z/ y% Z+ F5 W4 T else if(a[j]==1&&k==0) printf(" x[%d]",j);
- \. Y6 x8 F$ k9 n else if(a[j]==-1) printf(" - x[%d]",j);- H3 H; E: S1 w/ J7 R. m1 F) a% S
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
! t# |" y0 X! N6 b( ~ else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
# U9 @ Z& T% \" K/ i% [! c else printf(" %lg x[%d]",a[j],j);% s) @ r1 b0 W% q
k=1;. ?( L, ~; c+ j( @
}
$ z7 u2 D/ O% {$ Y }
& G3 l# {% V3 L# `" V switch(re_st) {
7 ^- {8 z: n; d A" C' ` case 1:
# j% K) P+ p4 g% x$ w& p* Z4 r printf(" == %lg\n",b);
+ X! i. C8 Z% D5 J break;
6 a/ Q e# D8 Y( C# t case 2:
% T! {9 H: M8 u# L e; t# g, o2 C printf(" >= %lg\n",b);
. P% }5 w, @- ]/ \ break;+ s9 ?, a Z8 B3 I' }* Y0 G) p
case 3:
8 T7 m. Z! M, h ~" X2 I printf(" <= %lg\n",b);
4 k7 C, Q6 \" y' Y4 ]5 m; {9 } break;! t' W. M, r5 @" R6 g, W
 }
6 Y# {: ?8 G" P! l }
3 H E M, a: T) K. n3 p printf(" x[1]~x[%d]>=0\n",num_x);
3 v) @% E/ d9 d( U6 @1 ^$ I- D8 ]9 k. u<> tnum_x=num_x;
2 } B* e# X5 a3 _- C, a8 \ for(i=1;i<=num_st;i++) {2 M/ Y1 L) m. ^( @
 switch(re_st) {
, \5 {* F) s! h9 ?' H- z! ` case 1:
" w& a9 R6 \# e* C case 3:
 b9 v4 C( l# ^$ ]0 E4 r& O num_x+=1;
& O" y, K, F5 P break;
) b! I9 u( K9 N' e. H$ s9 @' }/ h* B case 2:
! Z) E% D; ~8 n1 e3 G, i. P num_x+=2;
8 o+ V) R" {+ ^3 C& Z' @, }5 O break;+ X" w8 h0 {; d* |' |% ^
 }
; D! a* q$ s) n* y }
) O" B( Q/ l3 A9 n5 J! r<>//化为标准形式
) R: A m \2 |9 L2 p if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数5 _, M) I+ Y' ~0 r
for(i=1;i<=num_st;i++) { e1 o( n# G- I6 ^
 switch(re_st) {3 s2 F( c( y5 y$ O( j! r
case 1:0 [, j' p& I3 v
num_addv++;
7 x/ k# L& z7 a2 f' V7 s num_ba++;% m |9 o3 s4 c8 u9 B( c
num_ar++;
. w5 G' I- J) D4 f9 ]6 U c[tnum_x+num_addv]=0; . {9 d3 d' X! a0 Z E# N- w
base[num_ba]=arti[num_ar]=tnum_x+num_addv;
! g9 {2 {: h4 F* G2 M. l for(j=tnum_x+1;j<=num_x;j++) 5 Q; K; W) J6 y1 s/ o1 K, Q n
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;. X5 A6 B3 M* |9 m
 else a[j]=0;* A+ ?$ D. N; g
break;
# r: F' h( _+ {/ m! ^ case 2:$ H* S* b7 v ^! o5 [. l0 s' K
num_addv++;
# j8 ^9 U5 x' Y c[tnum_x+num_addv]=0;
1 Q9 }* \" H( ^, p num_addv++;6 l) _: q9 S7 {: Y/ u% F' H
num_ba++;
, R7 W1 O) S9 i+ g& t num_ar++;) Q( l3 |0 \4 ?; V6 N2 m
c[tnum_x+num_addv]=0;
0 a4 T+ |" A; P$ ~8 R7 A base[num_ba]=arti[num_ar]=tnum_x+num_addv;
1 j0 F* [ ?7 U* r) e# c for(j=tnum_x+1;j<=num_x;j++)
; B/ u% u" L, y( `1 L/ G4 r if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;! ~& ?; t: b; P
 else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
 m5 n/ h3 T2 h2 n* `' Z2 R else a[j]=0;6 N* O+ A3 J8 J" S7 s/ a" h9 L2 `
break;
% ~9 J* v0 {, c case 3:) ]% m$ A# [: `5 U4 h) g6 T* e
num_addv++;' g' o8 } I* h' B& y: l' d0 J
num_ba++;
+ I4 x* l h9 d2 Z' Y# j c[tnum_x+num_addv]=0;7 |% P/ b9 r% L5 f: o; q8 G
base[num_ba]=tnum_x+num_addv;
1 _; }( p- w+ y8 H7 v0 J9 v9 U for(j=tnum_x+1;j<=num_x;j++)
& Y! U1 Z+ `6 `2 `/ c2 w if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
3 l) V" `* w) M9 O else a[j]=0;
/ ~- Y% T7 r3 Z2 A% U break;
3 X& @5 _4 k! |/ O! ] }//switch
& U* D( |6 d1 K K, ` }//增加松弛变量、剩余变量、人工变量、确定基变量% Z( q* {- G1 p, F
<>//显示标准化后的方程组
* ]: Z9 K% O9 x# b1 ~ printf("\n化为标准形式后：\n\n");' |; _) l+ d$ r3 S. [5 S. A
if(ma_mi==1) printf("max z= ");
5 R% Z' Z" D% E! a3 ^ else printf("max z'= ");
0 a B' h% g5 g; D$ x* J8 ` printf("%lg x[%d]",c[1],1);; |8 K/ {8 C u: U, ^- e6 Y; j
for(i=2;i<=num_x;i++) { ! R" D/ m; [ d5 T$ T- l5 k
 k=0;6 o. o. W9 c6 T$ D: d
 for(j=1;j<=num_ar;j++)
, x. i) ]1 x {1 O if(i==arti[j]) k=1;
) e- f( J' A0 v* ?1 U" } if(k==1) printf(" -M x[%d]",i);6 E# E6 N0 ~2 V3 L, R! F7 ^' X
 else if(c==1) printf(" + x[%d]",i);2 d9 Z' U5 c) h g
 else if(c==-1) printf(" - x[%d]",i);; v0 N( X7 D- A
 else if(c>=0) printf(" +%lg x[%d]",c,i);
0 e6 w( j$ V; d! |2 h( O* D- H else printf(" %lg x[%d]",c,i);/ o+ Y ^, B- I7 v/ e0 G9 |& O8 E9 \$ h
}
: \& F) ^, E d, ^( j# }7 L8 R<> printf("\nst:\n");) |3 E" t' ]1 L% J: i( v
for(i=1;i<=num_st;i++) {
! u6 C# P" C. ? k=0;
9 C$ V; x' A% e3 d6 @0 r- C for(j=1;j<=num_x;j++) {
( h" x) R' C8 Z- G# Z if(a[j]!=0) {
1 F- [; ~3 k4 q if(a[j]==1&&k!=0) printf(" + x[%d]",j);5 m+ z+ Q; ?( e6 P l/ q; Z
else if(a[j]==1&&k==0) printf(" x[%d]",j);+ G3 ^# F, A7 F' E2 G# l/ B
else if(a[j]==-1) printf(" - x[%d]",j);5 [+ e% V" {) d3 v
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
$ m! D2 R' ~# r9 K else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j); v+ j' l1 @1 F. r
else printf(" %lg x[%d]",a[j],j);
1 } a/ M8 M% g4 ^& l k k=1;
 Q& T. b( o% T, k# w; g }1 j# ?! l* B- G5 W
 }$ q; m* c2 ?; F3 \
 printf(" == %lg\n",b); ' f# ^+ ^& {" z
}
% [* o6 x6 k0 E' { printf(" x[1]~x[%d]>=0",num_x);% }+ U: {( b0 n9 s' L
}
. B! Y! p7 h' A9 w" e<>void iterative() {
6 i, k' y: u+ `) E# D# @( r int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果
& E* y4 n4 u8 |1 j3 \ int base_elem;; Z' l% U( E" M/ |
int base_out,base_in;
: G1 b* \+ v7 g, d double sigma[MAX],temp;2 a+ e% [8 ^6 R3 s( B! }: C: ?
double value_be; //高斯消元里保存主元素值
6 J" i) Z; v7 l: P% p1 |<> printf("\n\n第%d次迭代：\n\n",stop);
6 K) ?4 ]! V2 b! J* t% d0 _ for(i=1;i<=num_st;i++) {
8 [: m. n; e. S' D: G5 P7 \ printf("c%d=%lg\t",base,c[base]);) D( q9 K0 p+ ~+ a5 r/ G6 v# E+ r
 printf("b%d=%lg\t",i,b);1 M9 P0 y% d) b7 g2 [
<> switch(step) {
% M7 v, q# p% o2 ~1 x case 1:
! y# y, f a( ^2 R% X( `! l4 U2 Y for(j=1;j<=num_x;j++)
# S5 r e; Q# b: k/ ] I d4 `* m {# Q, H8 m3 L/ V4 ]
 printf("a[%d][%d]=%lg\t",i,j,a[j]);& Q7 b) L% c& s
} J6 P' L) x) `( [" v
printf("\n");
5 ?2 n5 a( e) l. m% o break;' w1 w+ }2 ?! }& [3 ~
case 2:
, V5 C5 U0 Z3 |8 U) k8 b" O for(j=1;j<=num_x;j++) {
+ r! U3 [2 J; o6 c; X! v7 ^ k_a=0;
, n, i1 `) ]# l- P, x B for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;2 u# m! f0 z# b9 m& B
 if(k_a!=1) printf("a[%d][%d]=%lg\t",i,j,a[j]);- |& y4 ]9 z0 }% k
}
5 V- I# K/ M+ G3 \3 w printf("\n");
' U. u' v+ Y$ ~6 D break;9 V. r' P* \6 g
 }' u$ l. O% ~/ E
}
3 ?( K3 F' c# F) a//求检验数sigma3 c/ Z# S2 n- G$ D" x" n4 `6 s
for(i=1;i<=num_x;i++) {
4 |( |# H5 Z, S* D sigma=c;/ c/ e& B2 f7 W6 h. q
 for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];! P, v H1 G2 B/ z, I) G) O( x
 for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;
2 Y- p5 ]& ?- G( R1 W, ? switch(step) {% m% K( Q) i5 ]
case 1:* Q- ?! u. ]2 x3 ]4 X9 s& T
printf("sigma[%d]=%lg\t",i,sigma);' u5 w- t8 V( v: E/ j3 [
break;
* i4 V- R, M0 W6 @ a% F% a- { case 2:9 }* U8 n; l2 d) o% ^; e
k_a=0;
" J0 e- W6 q9 S9 K k* i0 d- D for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;# K4 o" N, v8 E2 ~5 w6 w
if(k_a!=1) printf("sigma[%d]=%lg\t",i,sigma);
2 @: Z4 ?5 Y" t3 y/ E1 c! h break;
! @5 s6 q1 L" ~! { }
/ l( a+ P6 J% e8 @, b- J }6 [2 m* u1 ~1 j9 q1 {- [/ s0 u
putchar('\n');) A( L5 ]4 D' z0 p b9 C2 W6 X
//检验检验数sigma是否全小于等于0 ?1 T! l$ U3 E* f3 B! @
k=0;
$ }; E; ^0 s m* P! o. d C# q* t for(i=1;i<=num_x;i++) {
8 ]1 ^4 D6 c$ I- u$ v* X! z if(sigma>0)
3 P# Y" g6 g4 ?7 q k=1;
" X. u9 b; l( U2 ]8 E }
8 k! d+ {. I( B' ~, R$ O. G if(k==0) {
- @' {4 e. x& i) l! L8 j- q //sigma是全小于等于0时，检查是否为无穷多最优解9 K+ T5 e% r/ \6 s1 E" Y7 d# x
 for(i=1;i<=num_x;i++) { - M8 E* C( W' d/ v# E, _
k_f=k_a=0;
9 c7 _' b s* }7 k' M1 r for(j=1;j<=num_ar;j++)! L9 ^2 A. H: n7 q
if(i==arti[j]) k_a=1;# _" T/ I2 M# J' F+ A4 I. d4 q+ t
if(sigma==0&&k_a!=1) {5 o2 T" \5 `! }" c% g4 h
for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;" R; W4 ?( }; I- x& R
if(k_f==0) {status=-1; return;}
6 ~$ I* q( l5 b# x w7 w }
/ j9 x5 ~( I9 b2 e; a. R }$ z2 A9 q# a# p2 d% U
 status=1;
9 B& [+ _1 N; j* r7 l& {. C; X return;
( D1 T5 i* d& { ~ }
( v2 B6 }. k5 n. }6 M% V//检查是否为无界解. c; e: t3 {7 B! g c: \ I& M7 D
for(i=1;i<=num_x;i++) { 1 O3 l$ i% ~; g/ e" _/ i
 k_f=0;
& m, h4 t# t6 w if(sigma>0) {9 w e0 `, I3 I) j4 Y1 C6 n- M
for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;' t1 I/ o! i0 n2 ~, ~7 i
if(k_f!=1) {status=0; return;}
5 Y7 l! I8 N. Y+ C8 d I7 o }
+ P3 u' Y- }) _2 N" e }& U$ F. N. V# h, ^: z0 P t' d( ~+ ?- [0 R
<>//确定换入变量. s. R# o( l: w7 r. N3 c
for(i=1;i<=num_x;i++) {
- r9 z4 p. o6 E k=0;
" D" h. p1 S- y" f" v( z1 K for(j=1;j<=num_st;j++) if(i==base[j]) k=1;" h! O# D2 u, c! m. R0 \0 E. q
 if(k==0&&sigma>0) temp=sigma-1; J: u C& Z, z+ o2 J6 j# k
}//temp赋初值7 G7 E! L! V9 h: [) X# ?$ y
for(i=1;i<=num_x;i++) {# H. C4 y% n# e/ g7 V$ ~; }& f$ C' N
 k=0;1 @6 E$ l$ O7 C% r
 for(j=1;j<=num_st;j++) if(i==base[j]) k=1;8 f* l+ t% ~1 n7 x! G
 if(k==0)
6 U- N" P! z, B6 }. H if(sigma>temp&&sigma>0) {7 V9 G* |% | S& m4 Q
base_in=i;, B0 K1 _0 H8 Q5 U3 f7 ]" J3 X
temp=sigma;
$ @" h8 ?8 `0 a4 J1 Y }
! G) ~& |9 F/ t/ B# X# F5 w }" |3 T. Y K6 V( z, |
<>//确定换出变量
1 j0 a* v$ a. _, F! b& F for(i=1;i<=num_st;i++)
! r* {! ?$ U" }( o9 C& {' I* K if(a[base_in]>0) {# `4 Y' @; p" x5 m
temp=b/a[base_in]+1;9 O+ n* l, N6 U
break;0 `% j8 M0 o* @- e [( M
 }//temp赋初值
# F; G" g0 k) s% S( ?% o for(i=1;i<=num_st;i++) {. |" D ]5 l& f- l, W: f
 if(b/a[base_in]<=temp&&a[base_in]>0) {6 n# k; a# F: n$ G- A" \9 J
for(j=1;j<=num_ar;j++)% A: O% G# T H0 l" v( C
if(base==arti[j]) {
) W# q! n; Q+ P1 f6 X& n' ` base_out=base;
! f. I. u* q- P base_elem=i;
8 c/ E- J% p. p; L temp=b/a[base_in];
; l- C+ Y2 x+ d- z' ~) X break;
9 b( ^4 p2 T) W }
0 j, w1 K% p0 A- O- W% E }//人工变量优先换出
( K5 K* a0 f0 B: r. `, M. ~ if(b/a[base_in]<temp&&a[base_in]>0) {/ X- }* { F! C
base_out=base;
0 D; e' k! [ q, S base_elem=i;
4 L1 t; n! x8 _' Y7 ] temp=b/a[base_in];' k" {( |. G) t# r5 c
 }3 w" K) Z3 |- ]: ?
}! |$ K, |& y( |! }
<> printf(" 基变量：");0 k) v! Y& v; H" P0 }* }+ K# M
for(i=1;i<=num_st;i++) printf("x[%d] ",base);* ]( [0 R# }% D. ^3 k
printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);" b" C F5 G+ I7 I5 i6 k% I- w
//基变量变换，进行新方程初始化后迭代; a$ T+ |( R& N) _; u
for(i=1;i<=num_st;i++) {5 x" O: g6 ~) C, F6 v4 `
 if(base==base_out) base=base_in;
) O8 C* r2 t* H% X }
) W0 d2 j* [( Y( G, K, f- D//初始化主元素行系数
( m: t: V+ S; D$ P, K3 q value_be=a[base_elem][base_in];
( F5 ~$ @& B% T: O b[base_elem]/=value_be;
6 U( u/ ^" L( Q' N* V, T( v0 Q0 `. |0 ? for(i=1;i<=num_x;i++) a[base_elem]/=value_be;
$ r" n* r4 B. N<> for(i=1;i<=num_st;i++) {
2 S- `3 ^# b. t5 d if(i!=base_elem) {0 _. p0 U$ j5 E# R# o' @
b-=b[base_elem]*a[base_in];* m8 Q" a/ ]; V) r. K
value_be=a[base_in];+ q( R) [0 W+ J2 H) `
for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;
, L! q) \5 v/ v ?4 O1 ~ }
/ g+ z( u& ?* C. P* R6 o }
4 b& Q% e# ]; O) g# t: Q' @! g% ? stop++;
1 R6 D& a- Y, g, j* ` w' [9 B if(stop>STP) {status=-2; return;}
. G3 X" V# \% o: B# M% I6 X# i iterative();
. a/ @1 X5 T! b7 ]% q}) a' ~: D3 S) M, g- L& h+ Y
<>void output() {* E/ F4 ? m( R: u5 N
int i,j;& L, E P. e4 @$ C
double X[MAX];9 j8 p8 m) y5 j' ?9 M' y8 {9 e
printf("\n结果如下：\n");, f% q$ N# i9 a+ b+ b
printf("\nX=(");
8 _0 Y7 M5 F% X$ ?! j for(i=1;i<=num_x;i++) {
2 ? |1 N( j. T4 o, d for(j=1;j<=num_st;j++)
' @% L! v6 f$ {/ i6 e2 |8 f0 b1 h if(i==base[j]) {X=b[j];break;}
7 e: |. |9 T6 I! D else X=0;$ d( d- q2 V5 M+ j4 ]/ m. {
 printf("%lg ",X);. Y. f3 {1 ?9 t
}1 w4 y* u7 ?* ^2 x# g# y
printf(")");
" G+ `( ?, x$ I3 i* c9 m for(i=1;i<=num_x;i++) max+=c*X;; m5 I$ W# o7 p5 z# i0 \
if(ma_mi==1) printf("\nMax z= %lf\n",max);
 V( S% b) c2 m else printf("\nMin z= %lf\n",-max);
1 w9 S6 l8 n$ n% c7 U, a}
作者: 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