查看: 6529|回复: 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;1 R _) M% T3 f: c8 {
leap1:
 e1 R* `; _" v if(l1-1==0)
0 e4 j, y% o3 p: u8 n- Y7 ] xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);, \6 u! B3 |; r! X& n0 b
 else
8 B9 n0 n* ^) Y, s+ R" Q+ H {
 y7 C W8 E1 a( _1 `leap2: if(l1-50==0)
# O) _# K# L" e x" D0 e8 l xi_max(&m2,&mn,&c,&n,&m2,&j0,a);
- ]8 y4 q2 I( r3 s9 O% ^. n# Y- ` else) d3 j' z0 P1 z, q
 xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);9 J( Z5 ^ g w, q7 f% _4 e
 }
" M& P0 K3 b9 A' U; \ c-=1e-8; F/ L" w1 j/ K% J2 X) @+ a
if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))
0 d1 b. b) A( _( ]0 H$ x4 ? {
6 p- F) }. U& B, X2 h1 Q printf("\n\t*********Not min&&No solution**********\n");
0 _0 o8 `+ M/ o U return(-1);/ H( {3 Y% E9 q3 ?/ @
 }
# b9 i* G* ?* M if((c<0)&&(l1==1)) B9 Y2 l w% v1 Z+ m. b* V7 s; P
 {
" z0 W: Q8 c+ v" B( K/ f o l1=50;
( O3 h1 P5 X9 e, c4 Q( a goto leap2;
+ [$ \% P! M+ q9 i0 @ }
 x* B5 H' M: I if(c<=0) b" |+ Z5 J! b5 B% `- W. v
 {
; V, r$ B( p8 I9 l. c for(i=1;i<=m;i++)
( k" j: M( U, j6 H7 ]1 Q (*x)=(*a)[mn1];9 O3 }6 k4 m0 y/ v6 m
 printf("\n\t********Optimal solution********\n");0 i7 P8 C/ M' ~; o
 for(i=1;i<=m;i++), M0 S5 s$ E' W6 V- X0 G3 T
 printf("\ni=%d,x=%f\n",(*k),(*x));
! v2 E; q: s* d7 D* j, w printf("\nF=%f\n",(*a)[m2][mn1]);
7 x: w7 ^- j% q9 T. U; R4 E7 w0 } return 0; g2 g- T& @) e/ B0 i
}% l5 O# E5 R( r7 A9 a9 N
 c=1e8;
. D. _# V9 X& Z$ b+ o+ \5 d2 H for(i=1;i<=m;i++)( o1 ?. P$ l8 G8 Q( n
 {
2 T' C8 Z7 ~7 n( \2 o; V if((*a)[j0]>1e-8)- G* q9 }% ?6 D( w! \# y9 \0 B* L7 {) h
 {1 L+ R- R; k' h1 r: h! ^5 [
 g=(*a)[mn1]/(*a)[j0];/ d, Z' v2 S8 C' q0 g F
 if(g-c<0);
0 y. Y% T+ N' P* j& d; ?$ i {
. u; `( m" \! w$ O6 s5 R0 x c=g;
6 D3 r( x4 r6 V5 \8 K i0=i;6 Z, V" C- U" C0 M; F
 }
0 f) j; e8 n( W c% M }5 U: p. X4 T- M
}0 s; b7 U5 P; I* }8 _. H
 if(c==1e+8)" {8 G- b) I. J7 v8 {/ i3 T* q
{
( ?; c# k; r4 W4 j9 H printf("\n\t*******Lp no solution********\n");
& z: x& e6 R6 C( P! H& d return -3;2 F P( E9 t5 ]! v2 Q# k: z
 }
 Q. k7 J% d4 M3 j5 z (*k)[i0]=j0;
+ D: K4 }6 R- I. o( x2 C for(j=1;j<=mn1;j++)
5 m' ~/ z; _, f/ T4 \+ |( V {' x2 a5 `% k% v" i2 s# ?
 if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))
6 V3 y/ [, O8 C2 _ continue;2 V8 N. z4 w/ p/ X" X
 g=(*a)[i0][j]/(*a)[i0][j0];; X1 A$ c! W1 \
 (*a)[i0][j]=g;* @3 f9 P, @$ X% B! b
 for(i=1;i<=m2;i++)1 x" `( ~8 D& s# y
 {4 `7 v1 A. y4 l- _' e# ~4 k
 if((i==i0)||(!(l1==1)&(i==m1)))
; C0 j+ f+ {7 m+ } continue;
. X1 x7 [% k) s+ c' W+ y4 ~9 z (*a)[j]=(*a)[j]-(*a)[j0]*g;
$ _ C3 [8 H9 ]. N2 [3 J5 a' y }
, G: C) [6 X/ Q# [% W, q* m }
" R8 w" T8 p6 r9 e. G for(i=1;i<=m2;i++)( J" j' h1 E0 c' |6 S# T- ?1 U# D
 (*a)[j0]=0;
8 R* l/ K) N$ |1 t$ r2 B* w$ Q (*a)[i0][j0]=1;
* z/ e' x5 g: s goto leap1;
' G, j& ]8 e) X}
, f0 u+ N2 K1 fmain()
, c. O+ W$ d" J( e d9 Z3 q{: B: r: }( `0 Y6 \
 float a[5][7]={{0,0,0, 0, 0,0,0},
4 \% o# o$ T0 A, d# C+ b {0,3,-4,3, 1,0,12},
) L/ b' E6 k; D9 s1 f- l- L4 J9 R {0,3,0, 6, 0,1,12},
1 L2 M7 O+ A) `% } {0,0,0, 0, 0,0,0},- W- p( O. `9 D8 m/ g$ p1 j
 {0,69,0,144,0,0,300}};
* x7 R" t4 P4 O" h int k[3];
4 ~ C/ e5 a9 D; r2 r float x[3];
5 c [9 `1 L; V T6 J/ b clrscr();: r, w, b l k6 F* a7 Q* y, d# f
 xi_sm(2,3,4,6,0,&a,&k,&x); x' ~ U6 y; m A0 ]
}
% i4 \& Y$ t% z, r4 w0 m

我也说一句

发表

使用道具举报

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;
# `- Q( i5 v% Q2 ?, M4 p. O else temp_c=0;, c' R* K1 {7 o$ _4 i
}
4 f( ^- r6 I& w/ w! t exchange(c,temp_c);
. R# v4 \% J$ T4 Z& `<> printf("\n\n第一阶段问题为：\n\n");
) N e) u& a. h$ D4 i show();
# x% G+ L6 T5 t0 [7 G( M3 m. } step++;3 }4 y8 t. B6 b+ B4 }0 j
printf("\n\n按回车开始第一阶段迭代");
% m+ }( i4 W: Q$ K+ {0 F" f( i: H getchar(); 0 {/ b- y1 p0 _* R: X7 p
getchar();
' T; Z$ s( N8 N- e1 h$ f iterative();- v8 V$ h* R% x/ i
if(status==-2) {: t* g- ]+ J& v6 |- f5 U2 n$ B" O/ W
 puts("迭代超过限制次数强行终止！\n");! N8 \, [% Y5 M- N2 Q+ \0 x( n
 puts("\n按回车结束");6 l0 Q1 o1 ?* ~6 I* ^ z+ M
 getchar();5 z- f# S5 \3 d3 K$ M. k
 exit(0);/ Q8 c' r! }# F4 b
}
$ u q0 M0 R2 C# B# A output();
; o* v' b1 I x: z0 J<> if(max!=0) {
# t3 z( W. y+ _0 [3 d/ D puts("\n\n原问题无可行解。\n");1 B& c6 v8 B3 P
 puts("\n按回车结束"); P; e1 t8 c9 r4 h$ e4 w$ s
 getchar();/ _3 s5 Q* d0 F* u9 F. `5 ^3 J, C
 exit(0);
; Y4 ]- { l" h6 p: J% K }
, w7 d; a y& A! n9 e) r* P* c<> //转换为第二阶段价值系数
: |1 x+ k' [; h7 P exchange(c,temp_c);
4 N0 K8 I0 \& P1 d4 t //把人工变量列全设为0+ q. J l! Z* C: r
for(i=1;i<=num_ar;i++) {
* s# \+ m1 m1 B c[arti]=0;
9 t" B+ I8 @7 _$ E9 F/ C for(j=1;j<=num_st;j++) a[j][arti]=0;
+ N) Q: m% m- U0 p }3 @0 g4 h2 l8 V2 S# U
<> puts("\n\n第二阶段问题为：\n\n"); j% A( v( ^: l( a8 G. R- b
show();) P. `$ @! M2 ~, X7 ?5 Z
puts("\n\n按回车开始第二阶段迭代");
+ f) D8 _/ D6 O- V getchar(); 0 C* ]; Z; E# R5 V, [" d/ b
iterative();
' Z, i+ H4 S2 o switch(status) {% k! z& |/ Z' r7 R
case 1:
! b4 [5 P4 f4 A1 k7 O& q output();
: |. u; r5 a* ?. }( B! M f puts("\n\n原问题有唯一最优解。\n");/ ~' @4 d: H. F1 y
 puts("\n按回车结束");
0 f- B# e1 n" O: }' h getchar();
; C, j8 E+ h4 c: {+ A1 X exit(0);: V T* ~' _! c& h9 _. a
case 0:
+ |; E& z6 {1 e. t- P: h# z puts("\n\n原问题为无界解。\n");
' E* E+ h$ j! ] H. S puts("\n按回车结束");( D& Y- Z3 W3 E7 D& I! N
 getchar();
5 g# U1 R, o% b& Y) X exit(0);& b4 |# |+ T/ X) g
case -1:) |$ s U% s+ ~! h- @
 output();% m8 E- n' @5 d' ^
 puts("\n\n原问题有无穷多最优解。\n");
" B, P+ n: S$ p1 ? puts("\n按回车结束");
 g% S4 n# G8 T# J" ?8 R8 x' B getchar();; I' G9 ]2 {# J
 exit(0);+ G5 X; G4 W- S+ x1 O% J7 D1 t- R( B
case -2:
3 K+ E2 X: @* R0 R- g puts("迭代超过限制次数强行终止！\n");
 puts("\n按回车结束");
# V @, N3 K; h& ] getchar();
+ S$ T+ [$ m6 k1 f0 f exit(0);% ~4 Y3 X. T5 n, X$ Q* m0 K
}//switch' p. a7 w5 C, U0 ~+ A$ H
}( R' b, S- X& G
<>void banner() {* D7 m+ k/ U, O5 K1 I
printf("\t\t****************************************\n");, y& E' D, H" [) w- G8 |7 A' k* g4 ]
printf("\t\t 单纯型法解线性规划问题\n");; I+ F% d/ ] D
printf("\t\t 作者：Thunder\n");! X0 M5 @9 z3 ?& q9 H
printf("\t\t****************************************\n");, k& o5 {- j. S6 G0 ]" o( \
printf("\n");
# E% B7 h0 w3 W9 w2 u}
- A# ]0 G3 R9 l; f/ A7 M<>void show() {
' E9 q( u; v/ ~! A3 {7 c6 D//对方程组以自然的格式输出，系数为零的x不显示
& {3 l: W5 T$ M6 H$ R! C//为1的不显示系数1，-1系数只显示负号- F' B4 t- I% x
int i,j,k;
( k5 O$ L6 M+ R5 j% C7 C6 U2 @ A switch(step) {
% T/ J3 Q7 L; `6 j7 e4 m case 1:: J- m( ~" O$ A3 N
 printf("min z= ");$ y9 c" |: Q, O2 K" h
 printf("x[%d]",arti[1]);( ?8 N, V7 l" V) |
 for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);
" ^6 e% }% z% B1 C% b* t# U4 e2 j break;5 Z3 o- _) ]* c* |! W& x
case 2:
: i0 N/ K- e w) { printf("max z= ");1 X9 f2 b4 B/ M' ~) x
printf("%lg x[%d]",c[1],1);8 s! ~ X- A- K" J3 y
for(i=2;i<=num_x;i++) {8 n7 s2 K( @# ~0 L- c
 if(c==1) printf(" + x[%d]",i);% N0 p6 X- J$ Y; U! @$ `1 o F
 else if(c==-1) printf(" - x[%d]",i);
8 m0 X; o- o1 n5 ^) j else if(c>=0) printf(" +%lg x[%d]",c,i);
1 Z: T" K5 u7 m' }; e9 E$ q else printf(" %lg x[%d]",c,i);0 z( \; ]! m% J8 J3 r/ ^& o: C
}
, y! A9 G" {- O t6 h break;
! D/ I, f$ l; x7 }8 D, c/ X" X }
1 [- G5 b3 i; k. ^' z<> printf("\nst:\n");
6 k9 i; Z9 z; y) }2 r' C d$ L for(i=1;i<=num_st;i++) {
5 Q! `7 F% X& H k=0;" Z" P1 n+ P" [# u: C! F1 @: Y
 for(j=1;j<=num_x;j++) {
" u* X8 W( J: U9 g+ E) o! X if(a[j]!=0) {" S* q2 g# j7 `) i4 V3 D8 N& I$ b
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
& d" ^2 X& G% y# o! F4 D else if(a[j]==1&&k==0) printf(" x[%d]",j);
% l0 |1 Y, y6 n/ j2 s/ v n3 ` else if(a[j]==-1) printf(" - x[%d]",j);" e" [6 U4 ^" c
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
* t7 Y! w- e) N9 S& V: M; ~ else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);$ n% H" @' J. U4 f( c1 E) L
else printf(" %lg x[%d]",a[j],j);
1 p& v: o/ E0 V1 k% X k=1;# U+ T9 y+ l; s( o( P9 L% z8 m
}
# c4 B0 e, W ?8 [1 { }
: J B6 @+ K2 A. c& O$ k4 p printf(" == %lg\n",b);
1 Q/ `0 J3 p# T+ y }
printf(" x[1]~x[%d]>=0",num_x);
& J+ G9 n) \6 O T$ C}$ G- l5 h* h N- W) n: t
<>void exchange() { A$ B' b& v6 q2 e/ W/ Q/ P
int i;
, r- s. G2 q5 p6 Z! q1 X4 b double temp[MAX];: K! J4 x3 O# j. a& g
for(i=1;i<=num_x;i++) {
* p: ~+ f2 J4 S; S" I temp=temp_c;9 g4 ?/ D- e( x) ~# Q3 `
 temp_c=c;
/ o$ k9 z! a: n; c$ X5 e5 A c=temp;
9 N9 B# r# G# R. r* c. o5 I }) V! `; g. p+ D( u I
}
) `1 @, U( k( `; w1 L2 O7 j5 z* [<>void create() {
* F# u6 f7 D; @4 i! a' h( H E//输入方程组系数，每个方程输完后回显确认
; N8 {( [ |$ e9 m+ E int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;4 V' R+ d3 m9 G# H3 r
char confirm;; v, L+ |3 E- } j) T9 e* S1 N

5 ^+ I2 J; D! p9 N1 h! S while(1) {
7 N3 N) M3 z3 j$ Q( N i1 F- E printf("请选择：1、求最大值，2、求最小值：(1/2)");
) Y! e+ Q" B2 I$ \ scanf("%d",&ma_mi);
. r1 n: A$ \* N: G# k3 r if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");
' D; q* Z. [$ @+ e5 [6 P d; R else break;
! n, J! g j. b. z. E6 @, h$ G6 D4 O }& _% t* i, q5 i2 \
0 p/ _: o5 D1 T1 N+ k
while(1) {
$ D. K* I! `6 R printf("指定变量个数：");. h4 C; u: a% S
 scanf("%d",&num_x);0 k$ o% A# [3 F2 N8 T
 printf("输入价值系数c1-c%d:\n",num_x);1 C) V& h) u1 L% Y7 [# q
 for(i=1;i<=num_x;i++) {
+ s# s5 ?# t# w- S: ]# N% W0 d" k printf("c%d=",i);- C. a7 K3 j Y# {7 g
scanf("%lf",&c);% \9 O* a- _& }+ E) o9 h
 }
: }# X+ V k. }4 f if(ma_mi==1) printf("max z= ");
 b, T K, Q. S, @9 e else printf("min z= ");( M9 D$ ]. y- D5 E
 printf("%lg x[%d]",c[1],1);
$ c% _# y& u( i( e& _! A for(i=2;i<=num_x;i++) {
; m0 O; x+ W( u if(c>=0) printf(" +%lg x[%d]",c,i);
4 o0 t" y) {" G else printf(" %lg x[%d]",c,i);
5 j7 }1 J& q6 U6 ~# k* ^; Y$ _ }
5 U; `" ^! v! ~ j _4 v printf("\n正确吗？：(y/n)");/ @$ H2 [; E% h" g4 z
getchar();7 J% K% }6 O! U$ B& N) E
confirm=getchar();3 d7 T8 p) g1 m3 ?
if (confirm=='y') break;
) t6 y8 n% |- }( }: { else if(confirm=='n') continue;$ ^( y& V/ L9 z( @" T- v6 D, c+ G
}8 z/ K" b9 H% J) f# h
<> printf("输入约束方程组个数："); s5 S# A/ m' B Z5 }* W7 T
scanf("%d",&num_st);) q8 C2 J# U9 }
for(i=1;i<=num_st;i++) {" f" ^$ F) G" k( K
 printf("st.%d:\n",i);
: F# t7 Y2 R; S. n while(1) {7 B1 K! n m5 H* F) F# ]
printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");# f8 b1 W% ]5 S3 T4 p m3 k
scanf("%d",&re_st);/ L. c3 s9 C! B* e
if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");/ v Q& }( R$ h% g J/ N, b
else break;
9 L3 ]* ?7 v+ z# \ }
 ~* d$ F: I- a printf("输入技术系数：\n"); E9 E4 H/ R4 o: ]- V2 U
 for(j=1;j<=num_x;j++) {
. O* f" B& x3 R; v# ^. R5 ?8 G printf("a%d=",j);) p+ ~* |4 z7 t `8 D2 R
scanf("%lf",&a[j]);3 g$ L0 i# g. b7 }; W2 J
 }/ e& }$ c" M# T5 X! y" k
 printf("输入资源拥有量：\nb%d=",i);
6 p) `1 G3 p9 t2 h; |' o+ d scanf("%lf",&b);
$ P1 c% s) R0 t9 C7 _4 Z1 M ; V0 i; \! N0 [7 }6 z( a
 printf("st.%i:\n",i);: V$ @+ x* p( V) y3 n6 V
 printf("%lg x[%d]",a[1],1);2 C1 x# F/ Z, Z' b/ V
 for(j=2;j<=num_x;j++) {5 _- B' k' |* k& l' l
if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);
5 S' @" ^0 D) P2 C else printf(" %lg x[%d]",a[j],j);
: y0 Q4 N" D ~& H# K5 E8 W. F }
" P" S+ J; s: d+ U& u switch(re_st) {( x4 f" r. a$ Q6 E9 G' _
case 1: printf(" == %lg",b); break;) E' s& C0 A" |; w5 j
case 2: printf(" >= %lg",b); break;% y! F" [/ X2 i" F- E9 p/ x
case 3: printf(" <= %lg",b); break;
. ?+ P' V9 v& e }6 ]# j9 B, p( t
<> while(1) {
/ \+ J( a4 p2 h3 S+ |! v printf("\n正确吗？(y/n)");7 W0 q2 R, m$ D0 A! C" u
getchar();
) L/ G3 {. P% ?9 ? confirm=getchar();
; Z7 O, m X3 P- [, A2 P if (confirm=='y') break;) F* V9 `$ B1 U
else if(confirm=='n') {i-=1; break;}& r- Q" W0 r) \7 J
 }
1 n% ~7 t v7 f% X3 ?0 s/ Z }9 }. u9 O! U- g+ [3 e+ K v3 X
<>//显示输入的方程组
1 {3 o# n: o7 Q% S0 I- V0 c. L8 O printf("\n原问题为：\n\n");1 P2 q; x8 [# E, Z) p
if(ma_mi==1) printf("max z= ");7 z% F- I9 P6 i# G
else printf("min z= ");
! A5 z( e/ C* Y/ ?# t& U% b printf("%lg x[%d]",c[1],1);
# P. T2 n: O2 Q& p, L; }9 Y/ G for(i=2;i<=num_x;i++) {) s* j; u; D/ O
 if(c==1) printf(" + x[%d]",i);3 H4 z- g( m! t$ N X4 m* G
 else if(c==-1) printf(" - x[%d]",i);6 {9 B; B L; _7 Y6 Z/ Q/ I
 else if(c>=0) printf(" +%lg x[%d]",c,i);
& P2 L5 B3 g& n# v, M else printf(" %lg x[%d]",c,i);
4 s' F: ]; t8 M" p) l9 I- m }+ K& F& L* O: e3 {. Q
<> printf("\nst:\n");
+ M9 k. A# u, d, W4 @, f6 Z" ^1 a for(i=1;i<=num_st;i++) { ' B. u) E8 J9 {
 k=0;
% A6 e" w4 S/ j" O1 J for(j=1;j<=num_x;j++) {
; D' F1 h2 y$ ^ if(a[j]!=0) {
" u4 ^) L; [, ? t% C if(a[j]==1&&k!=0) printf(" + x[%d]",j);' K5 |% P' Q9 e6 b! l
else if(a[j]==1&&k==0) printf(" x[%d]",j);4 m9 @: r A9 ^$ F
else if(a[j]==-1) printf(" - x[%d]",j);
) q/ |6 t* l; V+ G+ M4 p. A else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);; P0 M& Q% l+ v1 D1 Y8 K' C' D, a2 U
else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);: \* R* j' T/ ]/ V+ i% u! z/ E1 N* h& u
else printf(" %lg x[%d]",a[j],j);
, y! G9 c2 i- _: } k=1;5 r8 H7 \% X- W& }
}3 c8 B! f4 g! a4 e$ T! b
 }, F3 c( {0 S- Q U' }) Q8 ~) D
 switch(re_st) {
$ e% k. Z( F5 C; B8 |% \ case 1:
$ W) v) m; U \* V8 _ printf(" == %lg\n",b);
; K5 M% ]1 D: U, Q$ L$ K break;" w& x4 A; O, |5 E; j. g8 u" _
case 2:
 \: V& J/ W7 [4 ]9 l printf(" >= %lg\n",b);
: F( Z2 p% D6 i) u1 |$ F break;
$ w- D: \! d1 v" ?: N5 X: o case 3:
! f* u0 P/ d: i+ t9 s printf(" <= %lg\n",b); 9 h7 |0 ?& s* O( J! c5 n0 f
break;
; w g" ?. b. |. w1 x2 ` }6 W/ v/ B" W* p; j) E
}; E- F' e$ |! _3 b/ ] i7 A7 X
printf(" x[1]~x[%d]>=0\n",num_x);
) N! k. t' `+ ~& O) G6 h" a<> tnum_x=num_x;
/ z: M+ L: \& Q5 l F8 r for(i=1;i<=num_st;i++) {5 \$ D/ q z0 D4 h9 }. M
 switch(re_st) {! ~% w4 U7 M5 r( \( g7 u g& Y
 case 1:. n3 V* o7 I) K- E M* G& q7 o* s
 case 3:
5 }3 k* |4 s( I/ |. X num_x+=1;: Q [. Y# Q& } T
break;
9 v4 S9 ]0 t" W4 `6 K9 T% X5 K case 2:
# Z j$ y# ^( G2 D num_x+=2;
, Y: U% l1 V; P) x) e: v9 b break;* i% Z- y9 o1 w+ r3 h! n) B" h) K$ v
 }0 ?/ j- |! ]/ c; `
}( v9 D" k! C }; G7 b
<>//化为标准形式
. l, O, F& @3 U. d; W' n if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数% ]) F; s$ O4 c3 D' H
for(i=1;i<=num_st;i++) {; K1 P& G9 m2 M6 f
 switch(re_st) {
# s1 @, r* p- _$ P" t) Z; ] case 1:
' t# ?5 M, ^% _. N num_addv++;6 I# H& A+ I7 D% I) e9 S0 k' `
num_ba++;
$ f6 M( N& y% X+ c( [' f num_ar++;) Y+ L# _9 u. }# @
c[tnum_x+num_addv]=0;
; ], a" J a2 \1 x8 ` base[num_ba]=arti[num_ar]=tnum_x+num_addv;
* ]1 c+ r8 K7 p! q+ z4 n: t4 O for(j=tnum_x+1;j<=num_x;j++) 3 {* S9 A) ]! J: E' b/ v
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;# m2 a% Y/ q' [
 else a[j]=0;# f4 b* Y$ L$ Y1 p& W6 b$ w( |
break;
, O E$ k! K: ^8 y. G case 2:
& l b1 l1 F( G- B$ t7 L( w' j2 q num_addv++;
3 k( E: o/ v% Q3 v0 o/ X c[tnum_x+num_addv]=0;
2 |' a2 L s$ ~: G# d* V num_addv++;
; N$ M* I) x# f* M, @9 Z num_ba++;
8 Z% y( q2 u& c num_ar++;
 e' ~- M6 f, I. J* | c[tnum_x+num_addv]=0;
: T. p; E; e2 K b2 ?5 D base[num_ba]=arti[num_ar]=tnum_x+num_addv;
% G. n) l9 @9 I9 E for(j=tnum_x+1;j<=num_x;j++)
( j z: W; ^6 J& l1 m if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;
3 b% M4 ?8 y3 ?( a8 ` else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
' H' {. F8 Z$ A3 T. k else a[j]=0;
. U7 C' Q A4 V$ C0 N: \1 I5 ^8 _7 Q break;
' Z7 \1 {# k/ g2 q, A case 3:/ P2 T. n1 l q
num_addv++;: h( R& h% P. q% r4 d. I0 H5 W
num_ba++;7 \# l9 O; ^, z: d8 P
c[tnum_x+num_addv]=0;+ j7 q" q9 F+ k- R
base[num_ba]=tnum_x+num_addv;
: L2 ~* K1 D! g for(j=tnum_x+1;j<=num_x;j++) 4 a. P* B b5 @ C% n
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
+ B* m4 S5 ]/ V9 H* ~ else a[j]=0;3 Y- m$ H. W2 S; ?% S/ \
break;
% O* b$ }( Y& `3 L8 X% e- h }//switch
" a5 }% F3 K! h% G }//增加松弛变量、剩余变量、人工变量、确定基变量
* O( s, \- s$ ]; W! |<>//显示标准化后的方程组/ [2 N9 {2 u8 i6 d6 u) ?' A' N
printf("\n化为标准形式后：\n\n");9 \0 |: q" x; d$ e, a
if(ma_mi==1) printf("max z= ");
& m! u8 E9 c; f0 | else printf("max z'= ");& O6 E9 k" a2 ?( y; r1 Q
printf("%lg x[%d]",c[1],1);
$ S+ X5 c5 z4 ~' V- C for(i=2;i<=num_x;i++) {
6 t5 ?0 p; y# F' k k=0;) r" Y" o p0 r6 F: o+ X+ q- o
 for(j=1;j<=num_ar;j++)
 if(i==arti[j]) k=1;% |& S# R- {2 g$ T0 z3 m6 N+ N
 if(k==1) printf(" -M x[%d]",i);9 V( w' X' D4 a; s' [1 B3 _
 else if(c==1) printf(" + x[%d]",i);6 n" _2 n! X( m( j( n5 {! f
 else if(c==-1) printf(" - x[%d]",i);: i0 D* B: R. n. E- ~
 else if(c>=0) printf(" +%lg x[%d]",c,i);3 Y8 v: h" E* c* o9 d2 J
 else printf(" %lg x[%d]",c,i);
+ c4 e6 [# L" K! ^' m. l }
/ I4 ^! x) d* I- l+ Q. q, }<> printf("\nst:\n");
7 i A I9 Y; `, N. R/ d2 W/ b for(i=1;i<=num_st;i++) {
. T( J1 u8 B% T5 j( b4 i0 n k=0;
: F5 i( L* ?+ C+ Y3 ]$ @ for(j=1;j<=num_x;j++) {6 F. o7 Y% L5 T4 q6 a
if(a[j]!=0) {
" H& Q* u5 a& r if(a[j]==1&&k!=0) printf(" + x[%d]",j);$ V& Q3 v* I, o& @( q
else if(a[j]==1&&k==0) printf(" x[%d]",j);
* v0 Y ~ y8 }4 s) _4 | else if(a[j]==-1) printf(" - x[%d]",j);
0 s5 ]& E! B$ L; u8 H- G6 b else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);( V1 n+ K2 V! U" y0 u7 V! [
else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);( B. c* [- H$ d; z
else printf(" %lg x[%d]",a[j],j);$ @* b& k. G O$ H; I
k=1;% j# l/ a6 E! A% u, l$ i/ y
}
4 P* q; Z: O6 x9 e8 }4 J }" V/ \3 x% a4 H# Z8 W+ N4 n. D2 v
 printf(" == %lg\n",b); % @( J/ v% V" A/ L4 G! V+ |( ?3 ^
}; d3 D* J6 Z* |& @+ L8 ?$ I" x
printf(" x[1]~x[%d]>=0",num_x);
( A- S# b. H, r3 x; [3 [& M}4 o5 G- |# ^9 m$ r: Q" n
<>void iterative() {4 v- p7 m& K9 J/ w3 g+ \2 k2 y) A
int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果8 z3 t( `5 u4 O. U, C( H
int base_elem;
' h* \" U" d* K* F( V int base_out,base_in;
( q! e: h2 l* G$ t double sigma[MAX],temp;
 a# g" b6 J/ r3 Q, ]3 A8 w8 G/ K double value_be; //高斯消元里保存主元素值
1 x; d, I; P" G/ t; K6 s4 E<> printf("\n\n第%d次迭代：\n\n",stop);
2 _! v; n$ X. x for(i=1;i<=num_st;i++) {/ m# M& t$ K1 [: r# n* N' e" W1 m
 printf("c%d=%lg\t",base,c[base]);: T9 K! D3 b9 b* ]# |7 `8 R
 printf("b%d=%lg\t",i,b);
8 }" l6 R8 U& A" J8 w1 U<> switch(step) {
7 b. K) M/ D& H& U case 1:6 J! g+ i! X( G3 w
for(j=1;j<=num_x;j++)" n1 V# |3 P+ ] p! U% L8 C
{: ?8 D, {7 `( y9 r0 Z, h( L
 printf("a[%d][%d]=%lg\t",i,j,a[j]); }" ]* H, F4 P' ?
}1 z( I6 X3 H; }/ q6 O& O
printf("\n");! x* R* j2 [* _# G4 Q+ d9 A
break;
! b, r5 p7 s3 \* [, L case 2:* u2 D( S$ w% j4 N! C" h& Y* d
for(j=1;j<=num_x;j++) {
5 E/ i& R8 N2 _# Q; ?3 Z3 j2 f7 g k_a=0;0 @, H- i7 O8 @7 s! t/ x
 for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;' H+ w+ r3 z+ J6 @! P- ]: D7 P. e
 if(k_a!=1) printf("a[%d][%d]=%lg\t",i,j,a[j]);
. b1 o" _* H' E8 k: i2 p }
9 m: N/ w( n( e printf("\n");- I% s" e# U% b
break;0 M) S: I1 f) n. ^* J
 }1 e+ @5 o1 c1 ]* M( c# y
} r# D9 F# t. Y1 Z( O% F
//求检验数sigma3 u/ v5 L, \% D T: ^
for(i=1;i<=num_x;i++) {
; q8 f% G" @. ] ^, W' | sigma=c;' l6 Y3 l' {, x& a8 @& I( p
 for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];
/ V! s9 m1 X, F$ q; b for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;
! Y% s/ ]9 f4 z+ ]" p switch(step) {% }$ r2 p0 k5 o
case 1:
5 G. g& ?, t2 M: [, M printf("sigma[%d]=%lg\t",i,sigma);
# K6 ^$ Q/ x! t break;
; ~& v* s p; ^8 E( R, Y* F case 2:
: e# c) O1 C7 }: f& y d* u8 s k_a=0;
& n9 v, ?& k4 q& V9 u1 ] for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;9 {9 B# Q; L% P+ T
if(k_a!=1) printf("sigma[%d]=%lg\t",i,sigma);' |( t( _. y+ f* v8 b& a) @+ {
break;
1 U7 E4 C: y' q/ s( ^ }% Y) u0 O+ Q6 B/ n
}0 W2 U) i$ J' Z$ \
putchar('\n');$ |% L) f; d. x- m8 {2 _4 P
//检验检验数sigma是否全小于等于0
3 z' F5 g8 a; }; g k=0;
' T# l$ w; ], G5 w- h9 Y; p for(i=1;i<=num_x;i++) {
' T- _' }. \8 m$ i/ N if(sigma>0)
# x. _. F$ h, G+ i, A8 S! D) M k=1;
. ], d) \0 {6 J }, v2 Z6 x8 ]& U! n2 Q3 V
if(k==0) {
# |3 n0 o( d4 h% i/ c3 ^9 ?( Y# b1 { //sigma是全小于等于0时，检查是否为无穷多最优解
* p& V' T: X. i) H7 B5 j: i for(i=1;i<=num_x;i++) {
, A/ o9 t* }; P/ S$ q' y* @) J k_f=k_a=0;
8 F0 N* q# c: d/ S" R& b for(j=1;j<=num_ar;j++)
8 J# m1 o% e! I$ A8 q if(i==arti[j]) k_a=1;8 G. j. f1 w( p! ?" w
if(sigma==0&&k_a!=1) {4 V; d: V2 N6 `5 N. A
for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;$ C' h& d# b+ g& X& c
if(k_f==0) {status=-1; return;}
: @: l) `! D/ ~, w0 ?2 n" M; F }
2 w, W/ h% X& j: e) C& F4 x- k }% b7 r/ s: C5 G r6 y, ]
 status=1; # h- p8 T9 K) y
 return;, n: R( `, V4 B, `/ O, @6 }
}
9 I2 F' ^" m6 r//检查是否为无界解
- M& {. Z+ h1 m- P Z5 i4 u- k for(i=1;i<=num_x;i++) { ! F- l" ]7 D" ]6 A
 k_f=0;7 ]0 O: }! P' |' l3 S- V& B
 if(sigma>0) {* {6 I/ S1 s) [3 A1 }! [: r
for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;" l6 a0 V' P0 C% y
if(k_f!=1) {status=0; return;}) l/ @1 H; E6 `8 \& {. `1 n5 X
 }
9 G+ s% ]& g6 k+ I }' u" |4 |, y) S, e4 M9 D+ u4 S
<>//确定换入变量 W3 r4 R# ~' G' a
for(i=1;i<=num_x;i++) {
$ K9 l0 L* N$ K4 ^- c k=0;9 r* _2 P; Y' }% g
 for(j=1;j<=num_st;j++) if(i==base[j]) k=1;
* ^) A, o7 C i' K2 E7 ~2 [1 J+ k; Y if(k==0&&sigma>0) temp=sigma-1;
- O( H) @5 I g9 \! G2 n }//temp赋初值# P6 G" a6 T" e+ @0 q- u, }
for(i=1;i<=num_x;i++) {3 \- U) ]3 J. s$ M6 R1 c5 V
 k=0;
' H |9 X' j$ ?; @; O* e for(j=1;j<=num_st;j++) if(i==base[j]) k=1;' I5 i% ~0 k% B
 if(k==0)+ K0 J! ?% j) O
if(sigma>temp&&sigma>0) {
% s7 }: }, ~6 ]! q! v# W base_in=i;& ^/ r }! c, o4 b1 ?) r
temp=sigma;
0 C. i$ N! R& w! x! X1 ~! t }5 y/ n0 q. ~# C: ]5 x/ K$ U
}( p3 V$ ~, f6 R6 r
<>//确定换出变量
 V: ]2 X( y- N for(i=1;i<=num_st;i++)
* Q. g0 W: k; S. J; f% v if(a[base_in]>0) {2 q6 F9 E6 y) q& S" }
temp=b/a[base_in]+1;% P' Y. \2 @0 ~: ^' m( T) R
break;( T: x t* n3 e' o% C5 \
 }//temp赋初值+ a! v$ `6 ^' G# p7 {
for(i=1;i<=num_st;i++) {
) k. V" n" V: u# V* a. D if(b/a[base_in]<=temp&&a[base_in]>0) {
( ~( M6 n* O2 F9 _ for(j=1;j<=num_ar;j++)) ]4 B l" a' u! y. G) M
if(base==arti[j]) { ' p0 o: i) d! n& f6 q
 base_out=base;
# j- }; B3 }5 [ base_elem=i;
& V+ }- z! r7 [1 o6 ?$ r temp=b/a[base_in];
! j& B6 }# ` W, s break;
* c! b& j0 Z, ?: q9 B }/ J6 X6 I A, u0 f1 k9 H1 @' Q$ ^9 C3 Z
 }//人工变量优先换出
& f6 l+ X# E5 o8 }1 x H& I# G" R; r if(b/a[base_in]<temp&&a[base_in]>0) {/ v+ @8 g4 b8 j8 I. z
base_out=base;
. F j) D$ ^4 `7 e( J, t base_elem=i;
( F1 H$ G1 @; _; o3 j+ R' l( R! } temp=b/a[base_in];
7 g: Z8 s( i8 R+ ?; t% o }
2 c: c. c( ~* { O! U- Z1 q& i }
8 ^/ A* [, e5 m ^# y- P: K- y<> printf(" 基变量：");* X! g$ Z1 M$ p8 W" a | i: E
for(i=1;i<=num_st;i++) printf("x[%d] ",base);' [8 F6 ~: U" w! M. `1 Y
printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);
) _, |6 |, n U x+ o4 D) h+ E% F//基变量变换，进行新方程初始化后迭代
8 _" L& H$ u4 h for(i=1;i<=num_st;i++) {
2 f3 g" A$ h8 P, v if(base==base_out) base=base_in;
& j, p& @0 r0 g9 z/ S }. F% b1 N% [- M
//初始化主元素行系数8 p% U+ I$ J* T4 H: b
value_be=a[base_elem][base_in];4 V- [# w9 N6 l# D( B, S
b[base_elem]/=value_be;
" h( @4 J. E9 m; B for(i=1;i<=num_x;i++) a[base_elem]/=value_be;2 U X3 i6 a A2 N+ P
<> for(i=1;i<=num_st;i++) {( w6 w2 z n6 }2 L U
 if(i!=base_elem) {
4 x3 w9 i6 D& t( G4 ^ b-=b[base_elem]*a[base_in];1 D6 z X5 G$ @. F. ?0 W
value_be=a[base_in];
* i- u' d& P* n3 v+ b for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;
9 \) ?9 r" A, {; F. `" X }
$ g2 B, l4 Y' O& E; m4 g% o/ R7 F }+ w; f* k; F7 N0 M. s j, \
stop++;8 A2 X9 c( j1 J T, q
if(stop>STP) {status=-2; return;}
% a6 s+ E& n& d( B4 n5 h iterative();5 @/ j# c$ m# ?0 c! h5 C- p, K& d
}$ c5 e, t, M4 n6 c; T3 ? V
<>void output() {
3 w% p9 E# ~" ?: r) `" ? int i,j;) @7 @# c- _" i+ D
double X[MAX];
, l0 c- t: U, w! C+ i6 E8 y3 ` printf("\n结果如下：\n");
$ d1 L1 ^. L( N- G5 K! G printf("\nX=(");
/ N5 O0 E, g9 n" b; y+ N. Z, L9 F for(i=1;i<=num_x;i++) {7 p7 A* A5 E: [5 O! ^! r) W
 for(j=1;j<=num_st;j++)( o* g) {: h/ B( M- c" g
 if(i==base[j]) {X=b[j];break;}" x- x4 l7 {, _' p
 else X=0;
, N7 l+ x# S a7 ^ printf("%lg ",X);& \; n6 Y& z. e$ c7 r6 v
}
 O# r. T7 N3 }; S printf(")");
3 o; m7 H% C8 H( e/ r" i for(i=1;i<=num_x;i++) max+=c*X;( }/ H+ }4 O1 |+ b
if(ma_mi==1) printf("\nMax z= %lf\n",max);& R+ I! ?% X# u
else printf("\nMin z= %lf\n",-max);
6 F5 x8 \6 l" M; ]! k- B}