查看: 6437|回复: 9

求助：单纯形法的程序(c或其它语言都可)

字体大小: 正常放大

lauqt1980612

2 主题	0 听众	23 积分

升级 18.95%

该用户从未签到

电梯直达

1^#

发表于 2004-8-3 22:01 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

急需啊，谁有啊。感激不尽啊!!!

zan

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

使用道具举报

lauqt1980612

2 主题	0 听众	23 积分

升级 18.95%

该用户从未签到

2^#

发表于 2004-8-3 22:09 |只看该作者 |招呼Ta 关注Ta

最好是C语言的!

我也说一句

发表

使用道具举报

julysea

0 主题	0 听众	19 积分

升级 14.74%

该用户从未签到

3^#

发表于 2004-9-16 01:10 |只看该作者 |招呼Ta 关注Ta

以前遍了一个小程序，可惜只能解某个特定问题。。。。

我也说一句

发表

使用道具举报

candid

1 主题	0 听众	20 积分

升级 15.79%

该用户从未签到

4^#

发表于 2004-11-28 21:08 |只看该作者 |招呼Ta 关注Ta

<

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

>#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; l1 W- [5 H P0 G; z
leap1:# u' Q \1 O: V6 B
 if(l1-1==0)
- i5 h, Q! U0 f2 x, ~1 J5 L3 g* F xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);
9 H, V5 ?( X/ i else
$ D* ?" o3 G- q- L {
( j0 |' k$ b U" ]( ]leap2: if(l1-50==0)
" G# f' n6 r# K* ]& w# k xi_max(&m2,&mn,&c,&n,&m2,&j0,a);* k+ f2 h( R/ O+ U1 I F+ m
 else
; |* \6 R1 w& ?6 ~( q xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);5 G, [. ?# V5 N C4 b
 }
7 R& ]1 C; |7 k; Q6 z6 u c-=1e-8;
4 A1 F& J, G3 O: K5 d if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))4 b/ i8 Y3 x7 N% h) @; X/ M7 V
 {
; T) X1 F! j6 U, Q printf("\n\t*********Not min&&No solution**********\n");
$ ?2 Z6 N. G9 n& h. z: s5 n return(-1);
& O6 y T4 _2 b, z" {1 u+ ?. x+ t }
; v, t$ r5 R6 \: v3 w if((c<0)&&(l1==1))4 |; x, b- g/ K
 {
+ `) q, O7 B" A% e l1=50;
7 O; Y4 m! f c0 X3 A* Q goto leap2;
5 p' g" t- l: _0 m4 M }
. C- ?2 _* w" g3 x" n& u9 t4 \6 T6 q if(c<=0)& T% Y' {" z& l' x
 {5 y% N& v) M# B& J' G4 b, s- N
 for(i=1;i<=m;i++)
1 p* ^% W& p! k4 S8 F (*x)=(*a)[mn1];
8 A8 t6 E( @3 v V' p+ o2 Y printf("\n\t********Optimal solution********\n");, x1 P+ W- p9 r$ G- W
 for(i=1;i<=m;i++)0 A% n, [( U2 ]4 i5 U* e
 printf("\ni=%d,x=%f\n",(*k),(*x));6 ]# `/ I) o9 L3 l/ o& {% j
 printf("\nF=%f\n",(*a)[m2][mn1]);7 l8 a1 b) G4 q) g5 B
 return 0;
7 m2 k2 e, F. ?$ X2 U6 { }* s6 ?- E3 T" [% D$ k, [
 c=1e8;
6 x/ M6 X$ `" R3 j2 [/ E! W" n for(i=1;i<=m;i++)! f( O) O1 n" |6 [. b) _* x
 {1 b* L5 L" ]6 E! B6 R7 c, }
 if((*a)[j0]>1e-8)9 w1 k9 n$ t. P8 _5 Z
 {& a0 C: B- g4 H
 g=(*a)[mn1]/(*a)[j0];
$ d$ |4 O' S, N$ c# T if(g-c<0);- J( [6 o# N/ ~) K" {0 ?- n- k0 I
 {% u3 `5 F: S9 C8 g
 c=g;
5 n2 Z: V0 \% U3 E" L4 N: R* V5 n% n4 ? i0=i;8 ~! k m7 b0 E0 S
 }7 d4 I& P1 u* B6 @. p/ F0 |6 K6 @
 }
 x. ]+ T$ d4 d/ ]3 x7 c }
1 L3 o: l/ }8 q8 t7 U( { if(c==1e+8)
- [( M; m& u# w+ m, m {9 D. G& B5 y2 l9 q# u- ?
 printf("\n\t*******Lp no solution********\n");7 k7 y b. c* I
 return -3;3 b) @6 i5 n( S- A- F* g, |
 }
$ I& d7 O" L/ V- J2 L (*k)[i0]=j0;
' ?) B6 E9 S8 B% _4 {. Z" c for(j=1;j<=mn1;j++)
/ X" D4 j* L" w/ ?4 j8 F {
' o* V. q0 l6 ^3 [- Z0 E+ F if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))+ n8 o3 i( S( R& R( P$ d
 continue;
' w! j& H0 H: Y) z a* s4 u4 F g=(*a)[i0][j]/(*a)[i0][j0];
. z3 C* k) f2 s' F) V9 v* S7 K! B, N (*a)[i0][j]=g;
+ Z& [- e2 U8 v2 _ for(i=1;i<=m2;i++)/ X1 K9 _5 A0 d+ ]
 {
. O4 K' T1 f0 o' H! c if((i==i0)||(!(l1==1)&(i==m1)))' F, s5 ]1 M$ Q
 continue;2 o+ U4 ^# N3 U+ }( U
 (*a)[j]=(*a)[j]-(*a)[j0]*g;) c" X8 j! n9 e
 }. B; ?! e v P' S& {$ H
 }
9 p, v" B( `! e1 `5 R4 W' S/ X( n for(i=1;i<=m2;i++)
1 w3 _$ c7 V9 q& V8 w (*a)[j0]=0;( G5 u6 m* Q# G6 i
 (*a)[i0][j0]=1;* g# N9 ]' n) A/ O; r) H) h" k
 goto leap1;, J9 l* O( ?0 ^
}
- [: N& ^. C8 zmain()
- u- b9 P5 V. Z+ l{" \- P9 T X# b, w! i
 float a[5][7]={{0,0,0, 0, 0,0,0},
1 r# G* o* A. i5 D* k2 E, |% C {0,3,-4,3, 1,0,12},5 r/ |2 @* X. r- i( O5 d6 j& ^! [
 {0,3,0, 6, 0,1,12},8 \/ L" x! U0 `# }2 C. Q
 {0,0,0, 0, 0,0,0},3 K" [8 R8 V6 m$ X
 {0,69,0,144,0,0,300}};
9 [' \5 Q, j9 E# H! J int k[3];; D+ i$ W, j7 s
 float x[3];
5 j! ~# H5 w7 `! f2 g+ n clrscr();
& W; C4 |7 J% [3 b xi_sm(2,3,4,6,0,&a,&k,&x);
" Q) ^1 Q- W" A* C. i}
5 _. ^8 X' D6 {# T4 C% i

我也说一句

发表

使用道具举报

plgatc

4 主题	2 听众	19 积分

升级 14.74%

该用户从未签到

5^#

发表于 2005-4-25 18:00 |只看该作者 |招呼Ta 关注Ta

<

>/*************************************************************************
单纯型法解线性规划问题（两阶段法）

编程环境：VC++6.0
方程组输入说明：
变量非负，按提示输入相关参数。
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define STP 100
<

>int stop=1; //迭代记数变量
int status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数
int step=1; //目前阶段
<

>double a[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0; //方程组相关系数
int num_x; //变量个数
int num_st; //约束方程数
int num_ar=0; //人工变量个数
int arti[MAX]; //人工变量下标
int base[MAX]; //基变量下标
int ma_mi; //1为求最大值，2为求最小值
<

>void create(); //建立方程组
void iterative(); //单纯型法迭代
void output(); //输出结果
void banner(); //打印程序标题
void exchange(); //交换两阶段价值系数
void show(); //输出方程组
<

>void main() {
int i,j,k;
banner();
create();
//保存原价值系数，转换为第一阶段价值系数
for(i=1;i<=num_x;i++) {
 k=0;
 for(j=1;j<=num_ar;j++) if(i==arti[j]) k=1;
 if(k==1) temp_c=-1;0 C1 Y4 g8 B1 _4 j( [
 else temp_c=0;& O+ R# K7 ^8 q- c9 B- y
}
( a) q3 g/ n+ o: B2 K! R1 O' y exchange(c,temp_c);
* r0 o0 g2 K2 z( N<> printf("\n\n第一阶段问题为：\n\n");" [! l5 V, v! }8 A5 s) _ V
show();
. o( m5 u3 I: f& x# d% z9 c4 O8 H8 { step++;8 t ?6 Z( S! c+ ?% ^1 s
printf("\n\n按回车开始第一阶段迭代");
1 ?% t( A# [1 G3 p6 W+ ~ getchar(); # ? u' M% R1 i1 E2 g7 ~$ {; R
getchar(); F* m6 b$ L+ I: v. R) s0 z1 |
iterative();. l% P" X& z+ _- b5 Q
if(status==-2) {$ t6 h; K8 K [; Z/ h- M
 puts("迭代超过限制次数强行终止！\n");
1 x, O: |6 [ y% \& k: N; \ puts("\n按回车结束");
+ q) _# ^# A+ V getchar();3 D2 j& m6 g5 E4 k; j- G0 m* D
 exit(0);, \ F- z4 s& V
}
; O" T* S/ m1 v/ u8 I0 @ output();
. q: w" u3 C+ t1 I4 l4 D0 l, R<> if(max!=0) {& q! ]+ h) n" s: g( A% Q
 puts("\n\n原问题无可行解。\n");% b( Q- f2 Y0 o$ L& d
 puts("\n按回车结束");4 j3 ^! W" l' u/ w, R$ W f4 w
 getchar();% p9 R5 t/ R' |- A8 a* M! }
 exit(0);' ?+ W1 I& p. ?) n+ G1 @0 A0 K9 w
}
/ J0 ]. a& |5 l. ?. ~" g; L<> //转换为第二阶段价值系数# S$ M1 X Q) {% ~! c H
exchange(c,temp_c);
; ^ A8 h" I3 b: B //把人工变量列全设为0( K0 z8 F# F5 P9 O- q. I% E
for(i=1;i<=num_ar;i++) {
' }+ V, t% D0 {! W2 P } c[arti]=0;
/ \7 r! m5 U. B$ W3 ?5 f for(j=1;j<=num_st;j++) a[j][arti]=0;
% l* t) h# i( v7 c; n% G }
1 Q! }2 A/ J! v) m& z/ {<> puts("\n\n第二阶段问题为：\n\n");$ |3 i/ C8 T+ A! l3 c
show();( _$ F$ Q; ?+ {: @
puts("\n\n按回车开始第二阶段迭代");$ X9 L% |& ]( N H' m6 X
getchar(); ' B3 X1 q, V4 ~" y1 t
iterative();
+ G6 ~/ D/ K, N! f: W- l switch(status) {5 m) E* B) l! a# W# D5 B
case 1:
8 x$ l% r! I! L J; W output();
' E( q/ K# ]" V/ s puts("\n\n原问题有唯一最优解。\n");
 Q c3 s6 f: x puts("\n按回车结束");5 @" b& n" [1 ]
 getchar();( t8 i. I' D, @9 a4 a
 exit(0);8 o: p- P& k* j
case 0:) l& |3 R, o; C: h: z
 puts("\n\n原问题为无界解。\n");
! F* e" y0 P& c" U; j puts("\n按回车结束");$ f- Q J' L$ U- Y+ G/ _
 getchar();* y$ i" i' m$ E" w1 t
 exit(0);: t/ F" a: B4 W( K
case -1:
$ |1 z+ y" e7 [# N output();1 c% n) x6 ^6 G; J
 puts("\n\n原问题有无穷多最优解。\n");) i8 {% h# Q; h
 puts("\n按回车结束");; |+ D4 Y/ S0 z. w D/ y
 getchar();/ o# {5 n3 f, k6 u% r6 b( q% F5 V/ M
 exit(0);# A: @" D' C# p2 n% g
case -2:
4 H; n# \9 [4 g% _+ I" e puts("迭代超过限制次数强行终止！\n");" W& q+ o, A" W6 A2 u1 `0 G' p
 puts("\n按回车结束");: ?% f$ O3 a$ B% ]1 V1 s0 z8 }
 getchar();
5 u4 O8 S0 m+ N; ~! Y" n exit(0);
% l0 k+ U% s0 {/ ^+ i9 j8 [8 u+ ]: k }//switch
$ a* G) l+ n* o1 l) c}- W; t' j( A1 K: o& |
<>void banner() {
! M; a+ u+ q( [4 f printf("\t\t****************************************\n");
" b, S9 {- n5 m/ S/ I printf("\t\t 单纯型法解线性规划问题\n");9 n: C0 K+ z' Q# |6 Q/ [6 X
printf("\t\t 作者：Thunder\n");
# x+ o; G, K3 l2 R printf("\t\t****************************************\n");
8 K9 x; b$ k8 ?) }* z/ ] printf("\n");; N8 Y. h7 Q% H& Z
}
# v5 i2 l$ Y ?& r" _<>void show() {
# m, h0 w6 a! X* I+ u" L1 F//对方程组以自然的格式输出，系数为零的x不显示! @' B/ \. e& i4 Y& B4 P
//为1的不显示系数1，-1系数只显示负号
: {2 i! V! |7 j C6 V% I int i,j,k;
7 |" ^/ D; o" P switch(step) {
0 ~, [$ F% q: S, K5 b case 1:8 F- M+ m, R! x9 \# l
 printf("min z= ");
4 U8 o0 C' S* s7 y printf("x[%d]",arti[1]);
0 L [3 g2 K. h: s% I for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);
& p/ K: }2 N: O' j8 [ break;
+ s& R+ M6 K, l7 z9 b case 2:
7 G4 j' d" t/ U; c7 @! } printf("max z= ");( F" X2 ^2 h% O( U6 z: M# M
printf("%lg x[%d]",c[1],1);
: r& t( k8 p! P# w( y. N for(i=2;i<=num_x;i++) {7 Z5 c+ }( U# R- u
 if(c==1) printf(" + x[%d]",i);
1 F& n: `# d- `3 e: e! j+ v* u else if(c==-1) printf(" - x[%d]",i);# k6 ?- a* L3 O' b7 O0 {8 g
 else if(c>=0) printf(" +%lg x[%d]",c,i);
2 J/ G0 T+ s. u& S$ {/ n7 Q else printf(" %lg x[%d]",c,i);- ]; h+ S5 `' T' O
}7 D0 r6 q" ~$ d: X
break;
; u- M' b" R. K }: n/ q( G) V8 i1 R
<> printf("\nst:\n");) X. Z; k5 V9 P) E6 R
for(i=1;i<=num_st;i++) {
( W# [9 Z. E& i8 O9 A) ^5 r k=0;
3 S9 S; i4 R5 @( J for(j=1;j<=num_x;j++) {
' |8 x+ W: f, L1 j, }9 t if(a[j]!=0) {& C4 @& D$ d1 ?7 W6 N, S5 O9 A1 s3 G
if(a[j]==1&&k!=0) printf(" + x[%d]",j);2 _6 V9 W2 e9 m1 q$ M! j( B
else if(a[j]==1&&k==0) printf(" x[%d]",j);
/ v0 b \. Y/ _) q, v else if(a[j]==-1) printf(" - x[%d]",j);% x, L! f$ w0 g( o+ o; E
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
8 k/ H! v5 U6 q8 Q# l0 ~+ x else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
/ L- X" O# m0 y" a" q { else printf(" %lg x[%d]",a[j],j); x' I: N% p. P# Y
k=1;2 m! R5 G+ [$ C$ k% D! k7 y
}
/ a8 S/ x9 ]# t( y }; {2 Y( o( E! U
 printf(" == %lg\n",b); 6 t6 L* Q+ L- p T
}
% W3 D# y/ X* u/ ^$ h& `1 D printf(" x[1]~x[%d]>=0",num_x);/ M& y5 D, { U. c
}( @$ ^& T" Z( e! I8 J8 p2 v1 W
<>void exchange() {* Y, R+ `; K' G& Y4 {# e
int i;9 Y) z5 J6 ~, n6 t/ i' k
double temp[MAX];
/ Z) @8 C( ]" ]3 M! E for(i=1;i<=num_x;i++) {' `/ s+ m& _& S" S* m% K \$ [
 temp=temp_c;+ w6 W+ x* m4 K3 B( ]" `
 temp_c=c;
" o) y0 C$ u( t, Q1 w0 ^: @7 I c=temp;3 q3 J8 U8 p1 R8 |! R" y
}) |$ q+ k1 d. v9 z% @5 @4 ~6 P& ~9 f
}" ]4 ^2 v9 t2 Y* q
<>void create() {: n7 L1 Y0 ?6 A) [& h
//输入方程组系数，每个方程输完后回显确认7 m( P" i/ c; \1 h
int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;
2 [( D7 U3 w* @0 g9 o- ] char confirm;, B2 @7 p) F1 m* n5 m- T
% _& k) a+ L; z& C, ~' L3 z4 p
while(1) {
. P8 ]0 I# i0 X/ H6 ^0 \/ D/ _ printf("请选择：1、求最大值，2、求最小值：(1/2)");
4 r" o1 t6 ~" a scanf("%d",&ma_mi);
% ^* c8 Z4 C0 h# [( I7 a if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");
; O$ h, r1 |1 U$ o7 ^' b& B3 | else break;2 |0 X8 C% u( r2 f. g+ y8 e- \$ q1 s
}
9 A( f C7 ?3 @3 \
5 q; o- w$ Y7 I) d& m while(1) {4 G4 t! j2 x/ T& G6 ?/ s
 printf("指定变量个数：");6 J% M$ B4 r" |4 g9 z
 scanf("%d",&num_x);
7 U/ Z0 X" p* Z# N& S: y2 l' m printf("输入价值系数c1-c%d:\n",num_x);7 V) Y: b# |7 V, @
 for(i=1;i<=num_x;i++) { * J! I7 x6 k t
printf("c%d=",i);1 y* Z7 |$ @* ?' j5 ^7 D5 g
scanf("%lf",&c);. ]/ R5 p* ?! L
 }- z# p. v0 N$ u. V
 if(ma_mi==1) printf("max z= ");( f+ g8 f8 D. L: D# Q9 E! ]
 else printf("min z= ");
- ^. C* o5 f1 {/ J' r+ [ printf("%lg x[%d]",c[1],1);1 r0 H- u9 U3 r# q% \6 x- X$ L
 for(i=2;i<=num_x;i++) {/ G; j3 e, y& h8 P
if(c>=0) printf(" +%lg x[%d]",c,i);( @9 L& N; |+ K, u
else printf(" %lg x[%d]",c,i);) p/ ^7 q' k7 N& ]0 @
 }
1 o! A2 |1 X \* n printf("\n正确吗？：(y/n)");0 K6 m+ g1 u' G D4 x# ~
getchar();1 p% J. Z# b0 w/ F( O/ j
confirm=getchar();
; \2 `# J, k3 ^' Z% N if (confirm=='y') break;
6 \8 e* D+ y! Y( \, ^% N" f else if(confirm=='n') continue;
( f# F/ W+ L* `- M2 ? }
# s8 C1 U7 q( ~2 d" o$ v5 |<> printf("输入约束方程组个数：");
( x. Q1 D- v3 j: o+ c scanf("%d",&num_st);3 s+ ]$ j! a" K0 o
for(i=1;i<=num_st;i++) {
2 ^& g' \- g- F9 X% k( _$ s printf("st.%d:\n",i);
8 {( F7 q5 q5 k4 c while(1) {
2 K( U0 @% c! P2 w) @! g) H8 x printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");
# @& [' ~2 \! ^9 B scanf("%d",&re_st);4 J! F5 K' B; M9 w% g/ R7 x
if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");5 y" C1 f& J' ^' @
else break;
; ]/ M- Q5 P; w }
; ^7 F9 G. K, e printf("输入技术系数：\n");
1 ~ y+ u3 V( w6 { for(j=1;j<=num_x;j++) { 4 L6 M( [) \! R& p& F
printf("a%d=",j);! d4 |# G9 q1 J3 Z7 T$ a
scanf("%lf",&a[j]);- k* _; j8 u Y$ G7 \0 A# y
 }
. ~ y6 d9 _4 m9 _ printf("输入资源拥有量：\nb%d=",i);* s6 p. g. u/ L3 l8 T' K
 scanf("%lf",&b);8 T8 e, z4 q5 t

4 S3 J5 ?% i3 o* Q printf("st.%i:\n",i);- O) x& u0 y: v9 a& G* M8 j! W! g
 printf("%lg x[%d]",a[1],1);
5 G* t l; d# }" j+ K# g for(j=2;j<=num_x;j++) {$ T1 B1 g% {! G) d, _ [
if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);
5 h% e. V2 B) h7 k else printf(" %lg x[%d]",a[j],j);
% }% _, Y. Q" z# F/ Y. v, }0 p }
: F. V- v9 X$ R* Y5 T7 h8 g! q! J switch(re_st) {
, d$ z- d3 W$ S5 m5 x: j8 c( t case 1: printf(" == %lg",b); break;! x9 t6 i: X, D# P- Q
case 2: printf(" >= %lg",b); break;6 u5 p0 R+ L& Z" N/ I+ F5 I6 B
case 3: printf(" <= %lg",b); break;" T- B- a+ u$ M$ e# B B
 }
* _+ _! f; m q* Z<> while(1) {! y( l" W/ C( B" J
printf("\n正确吗？(y/n)");
7 n0 }1 N$ J$ K2 S5 i! i* D" } getchar();5 V& C* K6 h2 L3 O9 q7 O! K
confirm=getchar();
5 w4 v/ ?* @) v r, {+ _ if (confirm=='y') break;+ g9 d4 H, I* B% r. T* o
else if(confirm=='n') {i-=1; break;}
& o% f: j6 v5 v u; V1 K2 | }7 k2 I7 }4 b. A# n9 [: a
}
( {+ L% |8 b7 m: f! P! X) M<>//显示输入的方程组
; G0 @; U# g0 U+ f; B printf("\n原问题为：\n\n");7 ^; k; A2 ?* ]# Z
if(ma_mi==1) printf("max z= ");* ]& g" @- ]4 D8 U3 \7 L' @3 e) b0 S$ r
else printf("min z= ");+ Y: p5 ^5 o' S4 G. ?
printf("%lg x[%d]",c[1],1);% u9 R8 L( W8 {3 R: n# {* J( E
for(i=2;i<=num_x;i++) {
/ `1 n' W; X1 _* q: w, H' z/ s if(c==1) printf(" + x[%d]",i);
9 ~" e* P- F. X9 ^/ M else if(c==-1) printf(" - x[%d]",i);
& L) G B# @8 Z2 V" f else if(c>=0) printf(" +%lg x[%d]",c,i);
, I+ z; h/ ~ J1 ~ else printf(" %lg x[%d]",c,i);
, A* H" [* v- e# J) W* ? }8 D5 b& A/ e E' `" J4 B8 o
<> printf("\nst:\n");) e- n9 s3 v- K" i+ v
for(i=1;i<=num_st;i++) {
! B# `4 H3 N0 E k=0;5 P7 ?& O1 L8 B0 n. ^
 for(j=1;j<=num_x;j++) {# V3 Q! G# }" i) G
if(a[j]!=0) {
9 |- C, T3 c; e [4 h2 K! m, W if(a[j]==1&&k!=0) printf(" + x[%d]",j);
' _; \/ w; Y& E2 F( e else if(a[j]==1&&k==0) printf(" x[%d]",j);
% f% V% v9 F5 i else if(a[j]==-1) printf(" - x[%d]",j);: N1 p3 `! G* |0 h
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
$ ^: c" B' w0 E/ q4 t) y else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
: n; Q8 o6 z4 u: F1 d else printf(" %lg x[%d]",a[j],j);
# D- w3 X t- @9 s; H" T k=1;
1 p/ K' ~+ `7 n9 l }
6 Z# V, l* P% o* i0 k1 H6 ? }
8 N0 f) k Z7 o3 ^5 A0 j+ e switch(re_st) {8 t" w' v, C) _3 C9 K' q
case 1:
# w. o, a0 Y, k/ i printf(" == %lg\n",b);
. F- k0 D- U3 N6 n5 W. J break;
3 l: r/ C& V* T7 ^ case 2:
+ p! @8 w5 ~! j! ?: @ printf(" >= %lg\n",b); 6 Z7 M& A3 O6 j( _% G5 j
break;6 E8 R' h3 e( {
case 3:
5 A# d8 [& T- G9 g4 j/ i0 L printf(" <= %lg\n",b);
4 s3 _2 ]! o6 _; Q/ h" P break;
$ F e! Y0 ]! x' ` }
% [3 e3 `# v, n: E9 V: H7 l }
; G& J' {) {3 B6 | printf(" x[1]~x[%d]>=0\n",num_x);$ _! V* H% T! ~8 a5 j; N% |
<> tnum_x=num_x;
' B7 ]% c0 }5 S( M for(i=1;i<=num_st;i++) {
) Q' W6 z0 E: b6 k9 B switch(re_st) {
. g9 i' V- d8 a9 D* [' T case 1:
3 l5 M' `/ L- R1 V/ G case 3:& t1 \" J& v& F% W- N$ \
num_x+=1;
 s# K* T; O6 G8 G( a' w$ }8 G" R, Q break;
4 B3 }" o3 w1 b' t case 2:) m$ g% ]/ D8 H. v, F) \
num_x+=2;* A, Z& t0 T6 h! d
break;! Q' i( e8 ~1 `
 }
6 F h- Y, J1 o/ |7 @$ A }
$ N) g+ h5 Z+ J5 `; H<>//化为标准形式9 ^- X4 V3 P* D) F" u% ]3 g9 w
if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数. E. e7 |4 S7 T9 \
for(i=1;i<=num_st;i++) {
 A" c) L+ k2 a6 F. F+ ` switch(re_st) {
& l6 }- A9 J8 ^1 } case 1:
7 A' n A8 j- l num_addv++;
0 s6 G) X+ {" m$ u- S num_ba++;
4 n% ^3 G2 @# K, n5 J Y num_ar++;' n, s4 S. z7 X2 u( N' y
c[tnum_x+num_addv]=0; 3 c& o! ]' f$ p7 y3 W5 q
base[num_ba]=arti[num_ar]=tnum_x+num_addv;$ u+ z2 F/ I3 t. N
for(j=tnum_x+1;j<=num_x;j++)
! x9 |6 |0 o _6 E if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
9 m3 I7 }3 `5 n1 o else a[j]=0;% u+ W# F9 v6 E
break;
; v$ R' F! t3 k+ |- J* ` case 2:
: x! o! N& P# c! e num_addv++;
 n, }& O5 O$ r+ }: X/ ` c[tnum_x+num_addv]=0;) U3 H) y! B! P3 s- ^
num_addv++;$ D9 }) B0 a: F
num_ba++;; |, ^4 b. {$ _8 N
num_ar++;
0 }5 R4 h" l: w" p$ d/ s: I9 C c[tnum_x+num_addv]=0; & N, _/ z& Q4 m6 R+ O; r( T
base[num_ba]=arti[num_ar]=tnum_x+num_addv;
, {; C# k4 C. I0 N' b' [ for(j=tnum_x+1;j<=num_x;j++)
: ]% F/ \( [! j9 u+ k c if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;
# H: f/ i' }- ^# w; f8 b6 b5 h else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;8 d$ _ r" m* ^( X4 m" i2 W4 ?; f
 else a[j]=0;. L+ n5 {8 c1 q3 z5 q
break;! Y1 `" m) r# l: Z" c) `
case 3:% F F( f" x! `2 o8 i
num_addv++;
2 C1 ~2 l' m3 y7 e" Q num_ba++;$ {9 J, W+ a7 w- e8 V' i O2 V
c[tnum_x+num_addv]=0; I/ v1 C" u& U! Q/ k. A! ?
base[num_ba]=tnum_x+num_addv;
- X4 d& g& v/ A6 N; ]8 k for(j=tnum_x+1;j<=num_x;j++)
5 t! w" g! g5 W. a# k' h( Q if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
7 W" }( h3 Q% A; c else a[j]=0;8 Q/ L( M: X* N& ?# i7 c* J6 q) ^
break;6 F- v w* O) ^+ u
 }//switch
/ [1 o. _! K$ Y' \4 ] }//增加松弛变量、剩余变量、人工变量、确定基变量
, S" r* z- k0 e3 T0 d' S0 r<>//显示标准化后的方程组
8 K, _/ ^' z$ g printf("\n化为标准形式后：\n\n");
- w. ^7 ]3 i7 U- {( e6 ~ if(ma_mi==1) printf("max z= ");
. W' A+ t6 F2 i w6 N else printf("max z'= ");0 ]2 ]/ P3 i# U2 }
printf("%lg x[%d]",c[1],1);
4 U/ X6 f8 D- z9 ?3 i3 c for(i=2;i<=num_x;i++) {
+ E: f& y( o2 j$ M4 p5 D# F k=0;3 v4 Z: Y3 l1 S7 b2 E) E
 for(j=1;j<=num_ar;j++)( S' m r' H8 q% k, h7 r0 F5 @/ J
 if(i==arti[j]) k=1;# ~8 ?. N$ Y" Z
 if(k==1) printf(" -M x[%d]",i);
; B% `, v% D$ w+ }" m, K else if(c==1) printf(" + x[%d]",i);
' \8 e# V+ \& J9 |. t8 R else if(c==-1) printf(" - x[%d]",i);* N. ?' B! P$ D. b' m( p ]" Z6 m* l) _
 else if(c>=0) printf(" +%lg x[%d]",c,i);4 Q. J1 P+ ?; p# {5 ]
 else printf(" %lg x[%d]",c,i);
# R$ W9 g* K8 H/ X) q' I# |% g }$ q4 h( q. @6 l: N/ |: j3 @- ]
<> printf("\nst:\n");* k3 @. t: a/ ]% p7 r: w# |
for(i=1;i<=num_st;i++) {
& j3 q( W/ f( P! c* p k=0;
* \; r7 X' F) _. r* \ for(j=1;j<=num_x;j++) {1 }! b7 n' ]( ?1 ?
if(a[j]!=0) {- D& I$ f% E, O. @# ^0 l/ C4 B: {" L5 D
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
8 \- C% Y: K0 d4 M1 Y else if(a[j]==1&&k==0) printf(" x[%d]",j);
' B- D8 N& ?% I5 h else if(a[j]==-1) printf(" - x[%d]",j);6 _1 a: c& a" K A$ }
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);5 N1 A) v( D! E5 ]/ s+ P5 D( J2 i
else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
) E, z) y$ j, n$ }# y" [0 R else printf(" %lg x[%d]",a[j],j);
 i/ s* C% J6 l0 T. H k=1;1 P, q4 L+ |& c* H7 ?
}! j* d9 Q7 A1 X! e! e3 Y
 }* @7 Z7 I. k* s2 m- W% |" W
 printf(" == %lg\n",b); . l5 R9 x: U& r( B2 ]- P" r" I! _
}
; O# m' F* T) M1 B4 W' O printf(" x[1]~x[%d]>=0",num_x); ~7 Z% G2 M9 O/ a
}
* ?3 d D/ \0 d& \0 n! f2 h1 Q7 m<>void iterative() {
* n: X9 @( O8 d int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果- [2 a3 T4 [4 Q$ O( h
int base_elem;
! E- b8 X5 a+ L- u int base_out,base_in;- D. E5 z: S& _6 o+ O
double sigma[MAX],temp;
( H1 N7 O- j$ d. ~3 f4 ]4 F double value_be; //高斯消元里保存主元素值# }: t9 U2 ]6 s' r y. J; T. z
<> printf("\n\n第%d次迭代：\n\n",stop); 9 g) Z, R! N* i4 [* T$ S: j
for(i=1;i<=num_st;i++) {
; ~( R# s: ^1 J+ z: e, E4 a% B0 L/ } printf("c%d=%lg\t",base,c[base]);
0 P% e6 K2 d: J' n7 n printf("b%d=%lg\t",i,b);
) H) ?. H e: c' W# T! V<> switch(step) {
 k4 f* X; u/ C- g) J case 1:
# K2 S* a9 u# d& z5 ]3 j for(j=1;j<=num_x;j++)
2 f3 e/ |0 ]* I, H {
4 P5 l. ?' {5 u+ h5 H+ U; ~ printf("a[%d][%d]=%lg\t",i,j,a[j]);
6 \2 t1 a I2 r* ? }9 a0 r9 \' u! ]
printf("\n");; }+ G0 X7 V7 ]3 ~
break;5 z* V% o. W W! r4 T
case 2:
0 {' G6 ^& O3 b5 o# s3 C) A1 E* v for(j=1;j<=num_x;j++) {8 a+ r, e1 D. B# `2 Z
 k_a=0;
' a* Q0 g; p5 y5 { k" S) V5 { for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;/ K7 H {$ k% |# \# L
 if(k_a!=1) printf("a[%d][%d]=%lg\t",i,j,a[j]);: _* j5 i% o) d+ d7 \7 Z3 W
}
0 _. n% b& z# @# J) ?5 g printf("\n");
 K9 t4 X' l7 u2 i' i- X break;* s2 M9 |9 j1 V/ f$ L/ z5 D9 ^" C
 }
- Z$ j3 H' a4 Q+ v; x* F# Z }
- r( V- i& M6 F7 t% y& q//求检验数sigma
3 T$ M, i4 o/ ` for(i=1;i<=num_x;i++) {/ K" P2 S% C, E# M" l) @7 k
 sigma=c;& y6 l6 m, _" Q
 for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];
7 }: }3 l: T9 U* `6 E' s/ k9 F; m for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;7 u+ s0 I' R) [0 b
 switch(step) {! ^. r' C' j1 P2 n
case 1:
) k' X! O2 B6 k printf("sigma[%d]=%lg\t",i,sigma);
- i- I# o, `- [+ D: {( w, A break;
, |/ @3 K6 e4 N1 r& b6 [6 R& i case 2:( j, s j( }+ J- Z+ i3 U
k_a=0;- ?5 }3 K; d/ C# Z
for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;
2 q1 y% A* D' Z: A3 G: G if(k_a!=1) printf("sigma[%d]=%lg\t",i,sigma);/ R- Y3 u* E" E2 l# p# c
break;
6 s4 s5 t) A5 C( u8 Y } D# V5 `9 x. P, u
}
# `" O) `& e& |2 Q5 Z& S putchar('\n');
* V) S7 q5 l* N9 \//检验检验数sigma是否全小于等于0
7 |/ [# A& R! O+ F+ p9 h k=0;
: U/ Q7 H D) E3 w- L. x; A2 | } for(i=1;i<=num_x;i++) {9 L+ [% k' \: c. }) t) k3 K
 if(sigma>0) 4 c. T0 ^# r: V8 s+ Z& f0 O
 k=1;
0 z" t1 r- Y6 V }
5 Z6 N6 f `* ^1 _2 _- _! I" l. K if(k==0) {
3 ]3 ?+ S/ F2 [9 }6 p" W, e //sigma是全小于等于0时，检查是否为无穷多最优解
$ }( a" J4 t5 T) \5 t& X for(i=1;i<=num_x;i++) { 1 d: A2 C; O3 i& j% h5 s- J
k_f=k_a=0;
 b7 W% w& n' S) a' t for(j=1;j<=num_ar;j++)- L$ p) w5 F" D
if(i==arti[j]) k_a=1;8 U5 z8 R7 E, g: v B
if(sigma==0&&k_a!=1) {
4 F" h7 c3 o4 q; {% ~ for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;2 @2 p- s' N: \& I; a9 a
if(k_f==0) {status=-1; return;}! O: h5 j% l% z- r2 a
}
# q; k, n' A1 f: c: _4 ~' T" F1 s4 ] }7 j, I# O$ o7 ~1 a2 ^
 status=1;
' \4 V$ j* i( [5 e0 }/ |8 d return;
8 ~0 l/ |: X- f9 H' C+ o) p+ P }8 T3 I% H; Q% H, j# |) p; E% ]- q
//检查是否为无界解/ R" ?' H+ { D2 M V* O8 r
for(i=1;i<=num_x;i++) {
+ |1 n: E* O" @/ t k_f=0;
7 y: z7 |; W9 E0 b" W if(sigma>0) {
3 d* T3 s* K+ b: A for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;/ @( P& Q$ D' B
if(k_f!=1) {status=0; return;}5 {! y5 b6 @$ I+ Q s
 }
 W" q1 I0 l: g2 @ }
/ ?; n& T8 a$ U& s1 R* ]& c. v<>//确定换入变量
6 S% w4 w- Z2 i for(i=1;i<=num_x;i++) { ' M( ?* `3 z& U
 k=0;# |& Q' D. E2 R
 for(j=1;j<=num_st;j++) if(i==base[j]) k=1;
* F4 j# h+ }0 ?! I4 J if(k==0&&sigma>0) temp=sigma-1;/ F& E1 w. Z* Y1 \/ ?
}//temp赋初值" U: E" J; S% ]3 W0 k
for(i=1;i<=num_x;i++) {
0 y6 Y* T( G8 b" S k=0;
6 _: G6 o( o7 m$ w7 Z& e6 \, _ L" f for(j=1;j<=num_st;j++) if(i==base[j]) k=1;
. j" R7 X$ G+ u1 H5 E if(k==0)4 M: s2 T) v6 M, D' m
if(sigma>temp&&sigma>0) {0 O9 ^, A- F9 a! |/ @3 t) E) k
base_in=i;
( h& r/ V9 H# r0 M o7 m& w" t( c temp=sigma;) b3 |; U a9 o0 Q. r I! a5 U
}
4 T& Y a% {! v, ~3 E# Z+ x }
- Y4 h! x# n! ~9 S<>//确定换出变量
: z( d! W% a; x for(i=1;i<=num_st;i++)
7 q; D8 i- F, T" L5 q7 k8 R if(a[base_in]>0) {
; S4 p9 c+ U: @% b4 i! a temp=b/a[base_in]+1;* E6 f) c6 Q" b5 N0 ]7 k5 z7 ?
break;& y+ u, z* B$ I$ \
 }//temp赋初值3 m" `+ f) p" V# |8 |/ _% X. }
for(i=1;i<=num_st;i++) {: m: c$ {7 B3 _; z' V
 if(b/a[base_in]<=temp&&a[base_in]>0) {
: y8 l- m {, r& _4 I& N for(j=1;j<=num_ar;j++)" @. Z* j) X2 u4 o/ G/ q+ ?; e* }; [9 X
if(base==arti[j]) {
; [, a/ j6 V3 M! Z2 Q base_out=base;
( p) ^1 L# `. H base_elem=i;
. s/ j1 n* v; f/ }% ^( H R& [ temp=b/a[base_in];
2 `& @2 P3 d2 J' I- p- Z3 q4 |& a break;
6 m6 d$ B! g) U& { f/ a- H }
, Z, @" u6 Z: C% _0 N* |7 W# t }//人工变量优先换出
! S% g9 U# S: [! q. M; Z if(b/a[base_in]<temp&&a[base_in]>0) {
. y# L0 F: ?" w9 }% k base_out=base;
3 i1 `- Y* L. g7 I8 f' Y! N base_elem=i; b7 Q, ^6 o0 t
temp=b/a[base_in];
/ F$ A' Z$ ]* ]* l }% x8 x; a+ Z' a ~5 C- L0 Q
}- s) e. d! U7 q! P
<> printf(" 基变量：");3 D( m R! `9 _: y
for(i=1;i<=num_st;i++) printf("x[%d] ",base);
+ k$ }+ B; d5 c printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);
$ ~% s6 G! B3 ~; M//基变量变换，进行新方程初始化后迭代
; J# F+ k" X- I0 m. V for(i=1;i<=num_st;i++) {) M3 d7 ]7 S! N) D7 [: y
 if(base==base_out) base=base_in;5 X0 D5 B' n% s( C( x: `* w6 n" o
}
3 V0 a" I4 B. y A//初始化主元素行系数( k/ |* ?- S, f! W7 `* n+ @* A& Z
value_be=a[base_elem][base_in];2 }# o* O6 h% J1 ?0 @1 O
b[base_elem]/=value_be;# F* y$ Z+ S6 p1 T) X% t3 I. O S Q
for(i=1;i<=num_x;i++) a[base_elem]/=value_be;; G# N9 W1 n$ T" @
<> for(i=1;i<=num_st;i++) {
" |2 X) X; ]- D% z. w6 k if(i!=base_elem) {( t" N& G5 d$ @) v% a( T
b-=b[base_elem]*a[base_in];
: d+ i+ E4 {) Y, a: P- p& e value_be=a[base_in];
) }" h4 H( x* F4 N for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;
) z2 W7 b! F5 f0 h }) @7 d& @. ]) v" H: ?, N# M! c
}0 E7 J0 J: f$ w" w
stop++;9 ~! \6 j L1 V% r" m& R" l# G5 l
if(stop>STP) {status=-2; return;}
; O6 U) H/ a! a- L+ b! L u iterative();: z; O& H) M- B( w- i
}/ J( e% [* [0 ^% p# b1 U. h3 Z- S W1 r
<>void output() {4 u( Y8 \4 E6 l2 ^0 N
int i,j;
; a" g3 W$ H8 e* p9 Q+ R double X[MAX];6 \( o$ E* a1 l4 u
printf("\n结果如下：\n");
) }4 x* B# T8 `4 z+ n7 T5 V printf("\nX=(");
7 E$ O* ~. E; s1 g4 K2 W3 H3 E4 l for(i=1;i<=num_x;i++) {1 [, _) o1 O) N' T' Z% L
 for(j=1;j<=num_st;j++)
5 l" F% H ~3 s6 L; N if(i==base[j]) {X=b[j];break;}. n/ F w! S. y& d1 M8 @+ _
 else X=0;- ?2 D' {+ S: b* j1 W7 F
 printf("%lg ",X);
% x; ^! L9 v6 D3 X/ {) K }
+ S% \; X3 P# q" { printf(")");- v( j% t5 w# Z, A% R! v. L. {0 U& g
for(i=1;i<=num_x;i++) max+=c*X;3 M) r8 Z) g2 a0 ?" X, K" A f" y& F
if(ma_mi==1) printf("\nMax z= %lf\n",max);
4 w. _ `3 c2 S" d1 d% n- V6 E else printf("\nMin z= %lf\n",-max);3 `, i g5 k% z) O+ V
}