数学建模社区-数学中国

标题: 求助：单纯形法的程序(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;/ H9 v; w! N2 a+ h
leap1:
, Z$ a! a0 x! G1 g; l if(l1-1==0)
# t6 m# x" [0 p# n xi_max(&m2,&mn1,&c,&mn,&m1,&j0,a);) ]2 m9 c9 A. I$ w! W2 h I9 e
 else
& ]. |& R0 A8 g$ G! f {8 [. C8 I( ]- y6 { b! B
leap2: if(l1-50==0)
6 n$ J- T2 ~: U; ~7 v, V xi_max(&m2,&mn,&c,&n,&m2,&j0,a);
3 |8 m" ]3 {# S, R6 @ else
6 E8 _* X8 H8 ], B1 L7 K) S0 g v' S xi_max(&m2,&mn1,&c,&mn,&m2,&j0,a);
1 U0 b8 x) j) s* D }" q1 d1 f( d9 |3 u/ J" o6 c
c-=1e-8;/ Z8 r3 h. _2 N) G2 _
if((c<=0)&&(l1==1)&&((*a)[m1][mn1]-1e-8>0))
" L0 I/ ]0 e" k4 m, L {+ o. V/ Z8 X' @' y* J1 B
printf("\n\t*********Not min&&No solution**********\n");
* q2 B l4 c( @ return(-1);( n$ Z, I1 K! q8 R( u
 }" n$ @6 T% L& z0 q
if((c<0)&&(l1==1))5 Y% A5 C# \! C; j l7 q. T& o
 {9 P _" S; C% V
 l1=50;
8 `) b9 d2 w$ Q6 D; k goto leap2;- {6 F' q; H* ^1 Y1 p! }
 }
) c) p1 |, p/ P if(c<=0)
: F5 |$ b; k' H$ E' i' M {
$ N4 F/ \8 E/ L: p, I for(i=1;i<=m;i++)
1 |) n8 u" G9 M$ \ (*x)=(*a)[mn1]; F Q9 ~& V5 E
 printf("\n\t********Optimal solution********\n");
 for(i=1;i<=m;i++)6 H, p/ a# Q/ A7 P5 E# a
 printf("\ni=%d,x=%f\n",(*k),(*x));
- }1 i- z+ p( J1 B" O printf("\nF=%f\n",(*a)[m2][mn1]);7 Q2 w: w$ _7 `& X% W) W* ?; ^% x
 return 0;3 Q6 |, ~5 Q" \# n( m6 v
}
. |9 d3 I# [2 p c=1e8;; k; S' B$ ~! @# d& x+ u& o8 U& {# c
 for(i=1;i<=m;i++)
* o" Q8 }" V: x {% C* D2 M. @" N1 G7 m7 M
 if((*a)[j0]>1e-8)" d2 g! d( w& v! }
 {" a( a' X* u8 n6 u
 g=(*a)[mn1]/(*a)[j0];
8 }$ p' W7 b" O; ]; y3 f if(g-c<0);
; W: ]* U- W* f8 l/ E {
, f w5 ~8 D! P1 ^! }' P c=g;* Z& A* p+ p3 ^! H
 i0=i;8 v4 }5 {; Q7 k. T7 @8 h
 }! Z J; E5 y" {
 }0 O% {8 Q: D( j0 n: _
}- `# c3 Q8 @ v
 if(c==1e+8)
$ {9 v5 ? i; u/ ^2 j4 B, }( Y {
: G9 T6 `- z4 w! v! s& q) ] printf("\n\t*******Lp no solution********\n");
1 V- g0 p7 \% T( T5 U' s return -3;
; Z- `4 C- x3 Z }: l) P* R( q4 l- B3 F
 (*k)[i0]=j0;
. T$ A0 m0 M; k k for(j=1;j<=mn1;j++)
( ~: t1 K4 R& Y% Y {. ? A* R, b( [
 if((j==j0)||(l1==50)&&(n<j)&&(j<mn1))3 a. O) g; ?9 ~' C, @
 continue;
; g" {7 [% y& M# o T9 d" p' y g=(*a)[i0][j]/(*a)[i0][j0];
2 R7 ^! Q6 d4 L (*a)[i0][j]=g;
, r! L& D0 @. N$ k; F for(i=1;i<=m2;i++)
- h) w8 p6 }4 p3 u' y {( K3 h7 V6 p0 T
 if((i==i0)||(!(l1==1)&(i==m1)))
7 P1 X7 z/ s6 K6 P) ?; v K# X continue;
! T& J: z; r3 U5 l1 e7 w: O (*a)[j]=(*a)[j]-(*a)[j0]*g;
: w, I) [( T" l }
+ |* y2 y8 ~ j. S }1 h4 q, u( i9 @
 for(i=1;i<=m2;i++)
0 k- ?( ^. ^0 P7 _' m (*a)[j0]=0;
( g# u- Z: F$ C/ S5 H (*a)[i0][j0]=1;
* r; r. b0 U1 X% m, [/ H goto leap1;
/ {6 N" o8 k6 U5 k V} 5 g0 `9 e! u) M+ t
main() s% ?) u" |$ N. \
{3 B( N" ]6 S( I2 V" T6 W
 float a[5][7]={{0,0,0, 0, 0,0,0},9 @! v1 V9 v; V0 q
 {0,3,-4,3, 1,0,12},
- }( L+ d3 F6 P' C {0,3,0, 6, 0,1,12},
2 e# _: l) G/ Y2 Q {0,0,0, 0, 0,0,0},& ^" r/ ?# y' L
 {0,69,0,144,0,0,300}};
. l! |& f( a# `0 ?5 @+ u int k[3];& K1 G* F* y( ^$ _- h2 p2 s
 float x[3];3 M, S: l2 ~, j! g
 clrscr();
6 W, a, u" \2 V& x xi_sm(2,3,4,6,0,&a,&k,&x); Y' n! _0 X6 R! M- s" ~& W6 H
}
/ R3 c, ?; V$ `5 G" h ^
作者: plgatc 时间: 2005-4-25 18:00
<>/*************************************************************************# j. s1 `' U! O5 u9 j. Y
 单纯型法解线性规划问题（两阶段法）
0 }6 W* [! _) x1 |
$ g) G# X9 C1 F l7 n5 V$ b 编程环境：VC++6.0
4 a1 N! _7 O5 K6 R" b0 S B 方程组输入说明：
( s. L: D3 f+ r 变量非负，按提示输入相关参数。/ ?$ R4 A. V" I: _' N
*************************************************************************/) c! [& Y) K# z( D3 J1 U
#include <stdio.h>
1 G5 W8 I p' A: O$ C#include <stdlib.h>
5 {; v/ O) J7 \" Y R4 m7 p3 I#define MAX 100
+ ^# i. S" _" i# i. D#define STP 100
$ ^2 `: H/ M4 T# l- F<>int stop=1; //迭代记数变量
8 X" F; f# N" J, i. h5 Nint status; //iterative迭代返回值：1唯一最优，0无界解，-1无穷多最优解 -2迭代超过限制次数
) @, o9 E! f2 w$ C+ `1 Yint step=1; //目前阶段9 \( q$ K9 K2 N6 m: i1 }) v( b6 }% V
<>double a[MAX][MAX],b[MAX],c[MAX],temp_c[MAX],max=0; //方程组相关系数) Z* W/ ^" A3 [! }3 E" C$ _* L8 p
int num_x; //变量个数 7 N0 w/ _4 Y; t% O) s
int num_st; //约束方程数. G6 d7 {( Q. T4 E! h" v5 {
int num_ar=0; //人工变量个数 f% u5 e4 o& Z4 j* n/ V
int arti[MAX]; //人工变量下标/ s4 E% f( g- K1 }1 Z8 W# ?. Q% n
int base[MAX]; //基变量下标
" I9 H! ?4 H- R' jint ma_mi; //1为求最大值，2为求最小值7 m) I4 @, Z0 l4 Z
<>void create(); //建立方程组, E( E+ `/ ?2 W' q' {
void iterative(); //单纯型法迭代" a2 s/ `2 n2 p5 w
void output(); //输出结果
. r) Q4 [2 o* X! ?. W- \void banner(); //打印程序标题% I1 H' |" q% c% o
void exchange(); //交换两阶段价值系数, p0 T9 u9 E, c9 S; n/ m
void show(); //输出方程组
5 p& {" w1 W! q9 a8 `0 r" L9 t, y<>void main() {9 w# t9 z/ d, e: Z+ q
int i,j,k;% h, C6 K2 |- N. @4 D/ y$ N1 J4 V
banner();( f1 T3 N3 L3 v
create();2 F. A; _* Y+ ?% {
//保存原价值系数，转换为第一阶段价值系数" ~3 {; k9 i& ]7 E
for(i=1;i<=num_x;i++) {
2 Z8 { ^; p7 C9 U8 [9 @ k=0;6 d y' R; |- ^4 H
 for(j=1;j<=num_ar;j++) if(i==arti[j]) k=1;* U' x" C2 P8 Y
 if(k==1) temp_c=-1;
# B W3 a2 y; z7 | [- } else temp_c=0;
3 \) \3 p( `1 U8 U& f4 S8 K% f4 i } @( g! @) m @
exchange(c,temp_c);# v/ @# [9 Q) u- T' B% U6 Q
<> printf("\n\n第一阶段问题为：\n\n");* j/ d5 d) b$ M: u
show();6 Q/ R! D1 i: d2 P, ?8 X& X$ {
step++;
5 W# W ?; k7 q; k( H printf("\n\n按回车开始第一阶段迭代");% R8 a2 X& ^6 s' R/ \; d* Z$ e4 P
getchar(); ! U. X, f- `: N9 K1 N& R* ]) J
getchar();" T* H% S# n4 y# S0 S# ^
iterative();$ ~: G) A! P& x$ Z5 Z# i8 h, g
if(status==-2) {
5 o% `5 [" _/ X& `0 u puts("迭代超过限制次数强行终止！\n");
9 F# e$ |2 H7 E/ Y/ r+ Y puts("\n按回车结束");
" k/ c: a! }: o, D' G" ~ getchar();
' T/ _- y2 i" d5 }) d- }3 C exit(0);
8 M) ~' S7 K/ D* V" n6 p }
 r* U: R$ J1 B! { z output();1 u7 u5 k& s* A1 ~. t! Z7 ~
<> if(max!=0) {
+ P, T: z, V; Y6 y puts("\n\n原问题无可行解。\n");
5 G" j: {) }1 A; y! j7 L( s, y puts("\n按回车结束");+ J% j$ U8 S( ~5 Q! N
 getchar();7 V5 f# s& `) k) g: ]. P0 p' F
 exit(0);
; v! z3 R! X" d6 u: P' { }- d" v k5 k( p
<> //转换为第二阶段价值系数
$ Y a& ?3 A4 j9 W6 F& e( J; e exchange(c,temp_c);
$ P. s1 W \% S //把人工变量列全设为0
, i! N1 p) W5 V for(i=1;i<=num_ar;i++) {
3 |4 [; a: Y& \+ I c[arti]=0;: p+ N* C9 @& [! ]
 for(j=1;j<=num_st;j++) a[j][arti]=0;
/ d1 f; b+ @& C1 e. s9 r }
8 J' r* \0 d3 m% B2 k) `- h<> puts("\n\n第二阶段问题为：\n\n");9 N( |7 A. X: [3 k; H& i" W/ p
show();
% d+ E/ s& {5 L w6 @ puts("\n\n按回车开始第二阶段迭代");
" C8 K6 u& T- a& [ getchar();
2 A/ _+ q L+ L4 c' U iterative();' s. d; A5 _/ u: b1 y- h
switch(status) {
# r9 q( b" q( u6 w# j case 1:
: \9 ]+ v! G. j8 m output();
( A& |0 B1 i+ l puts("\n\n原问题有唯一最优解。\n");
% {2 @4 |3 k" }/ A/ S b O puts("\n按回车结束");1 C2 ?1 N O+ y2 N& u% W0 q
 getchar();
8 M0 o, M+ ]: g. V5 J exit(0);
( z3 W- f* @# [1 k case 0:
6 h" ]/ q& m: a3 F* ]5 ^. Y6 g puts("\n\n原问题为无界解。\n");
" v' @8 Q# J8 X! ^ puts("\n按回车结束");
0 J: L2 c! s* J% q- }7 I getchar();
8 w! d& a; E3 M1 j7 o exit(0);
$ N+ h& S" Q" d2 x7 A, i. T& g case -1:
' d/ ^# B& F4 c: e/ J% F4 z output();+ q. B7 c4 O3 u7 T( k, ^
 puts("\n\n原问题有无穷多最优解。\n");# ^! N9 C. _, h4 |. ]) f; e* P
 puts("\n按回车结束");" X8 M' U) \ j5 N
 getchar();
. {' d( S8 v: i, Q* {. B/ N. C8 D: J exit(0);2 {3 K- }* ^, x3 @+ w! A
case -2:
' I" U) Z( e3 P" R x puts("迭代超过限制次数强行终止！\n");" U# S. a: N' r9 s' V3 |( L7 p
 puts("\n按回车结束");
( V2 ^7 [( O# `, d' I( [* v; S, k getchar();
/ o* l s/ _1 j$ Z, M* ] exit(0);
, t* u! S7 o- g k+ v2 n }//switch
/ j7 {1 I6 ?" @+ J}
0 ?! r6 u" R2 t9 s% f<>void banner() {
! c6 S i7 l. a# m4 I2 H* d printf("\t\t****************************************\n");6 [" ]3 B0 b$ q9 Q2 Q
printf("\t\t 单纯型法解线性规划问题\n");
% s6 E: K; c; x8 p printf("\t\t 作者：Thunder\n");
- l$ u; d2 ~* ~. z/ l( n printf("\t\t****************************************\n");
0 h5 i) K6 p2 n+ o) r printf("\n");% r) z, V& r. x& K. U2 b3 z6 N0 A
}/ c. |+ r$ O H7 R; D" y% Z
<>void show() {
, z- V y- H) @! j6 r//对方程组以自然的格式输出，系数为零的x不显示
0 q7 m# t) p# J! C$ W, e" H$ g//为1的不显示系数1，-1系数只显示负号( x) E" J* s4 W
int i,j,k;
/ l2 \$ T5 o% T3 w. Z/ ^ switch(step) {
2 D0 `$ g; |) q case 1:
( ?" Y9 a9 V: a/ z. ? printf("min z= ");+ o- G4 w% h* K# |9 U( n
 printf("x[%d]",arti[1]);
" K8 P' _3 C' {0 j+ s for(i=2;i<=num_ar;i++) printf(" + x[%d]",arti);
" `. s+ C B) H1 b+ H* i( h! r) l break;" T0 r1 E. o; m \1 s$ N
case 2:7 O& K" T7 B+ [. n: m2 k! X
printf("max z= ");
8 d: e, W% F8 s6 ` p printf("%lg x[%d]",c[1],1);
% L; P) ^6 ~( u% q+ j F5 a8 R for(i=2;i<=num_x;i++) {, R% `% D/ B5 F7 m1 x* b: N! r
 if(c==1) printf(" + x[%d]",i);3 |( p# Q1 |$ h7 u
 else if(c==-1) printf(" - x[%d]",i);4 W' p7 M/ }0 W/ s- u% E& I* q5 Q
 else if(c>=0) printf(" +%lg x[%d]",c,i);" K3 K! @ Y2 J1 z* D+ E+ V
 else printf(" %lg x[%d]",c,i);' n& K; V% L8 n2 b) L: A: P% z
}
5 E+ w/ C: _) ], {5 B" S9 m break;0 ?! J& E$ _8 L
}
# L1 E/ i; H2 t<> printf("\nst:\n");
+ g$ e; K# o) W$ y for(i=1;i<=num_st;i++) {
- j' u5 h+ j! ]) f$ \ k=0;2 a8 t9 z- j7 X) `8 w) e
 for(j=1;j<=num_x;j++) { # K- N# B" e4 d6 z5 W
if(a[j]!=0) {- P" n% J8 U" {9 o0 q
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
6 g( Q1 f' E; F: c else if(a[j]==1&&k==0) printf(" x[%d]",j);+ a- m- O; k7 I& g) T# G
else if(a[j]==-1) printf(" - x[%d]",j);
! R* h6 A+ n! z6 ]$ H: [/ o else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
5 ?4 P F7 X: W4 q/ m# G7 X else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);; G; z! M/ {+ x% q
else printf(" %lg x[%d]",a[j],j);( w1 Y, {4 h; T4 E( g
k=1;' q* M O4 Y" d8 n
}# T8 Q$ M7 S! c @' N3 m, C0 z$ J8 e
 }
7 k8 b0 q: q$ W6 y2 J printf(" == %lg\n",b);
7 J$ m. `$ b3 K9 @* I }
3 U8 h8 y7 v) B printf(" x[1]~x[%d]>=0",num_x);
- q8 Z) Z& {) @8 E. r/ ~! q5 _}
, u. T; Y2 f2 z<>void exchange() {
7 _% A3 [- l: F" R3 N int i;/ [) H+ ?. |. C8 E4 f8 @* ^# L
double temp[MAX];) {% a" `5 x$ p+ E5 ?
for(i=1;i<=num_x;i++) {
& q7 I& i/ D* ^, o; P temp=temp_c;% E- T( t5 S; }: S
 temp_c=c;
' f4 y" h) K* j( G c=temp;& l+ K! H+ E; ]
}
% }0 f3 p$ y) q A- k. t; n}
! x ?; {2 e: O/ P3 V<>void create() {6 h0 K4 G5 P, b1 C8 q# S8 o
//输入方程组系数，每个方程输完后回显确认
3 G/ k1 X6 Y, k6 {) N8 V int i,j,k,re_st[MAX],tnum_x,num_addv=0,num_ba=0;; a9 \8 q2 N3 N1 }# Y( O
char confirm;
/ m# I; @: `1 l" ^6 t & s2 R9 H0 N; w3 [
while(1) {
% T A2 z7 N' L* C$ V8 v! H9 t printf("请选择：1、求最大值，2、求最小值：(1/2)");+ E. f! t; e( B% K
 scanf("%d",&ma_mi);8 e& ?% [. m5 l9 K$ B, q
 if(ma_mi!=1&&ma_mi!=2) printf("输入错误，重新选择。");
6 g& `' e) w0 O- F; ^ else break;
. ~3 T/ H3 R1 A( B& b. K }
/ ^3 t$ I$ \3 N
1 _; N# J& ^8 f u. s8 A# e, j, Q while(1) { q6 P/ I ~1 A0 `# z
 printf("指定变量个数：");: T5 X# ]/ N; h' K
 scanf("%d",&num_x); L+ R# z* ? X1 s# h3 _
 printf("输入价值系数c1-c%d:\n",num_x);
8 ]! {9 _4 I9 a, W. x for(i=1;i<=num_x;i++) { . _7 _" R1 g9 s" _
printf("c%d=",i);
! J4 i4 Y8 z* K: \ scanf("%lf",&c);* C& ^0 B7 r* z- ?
 }
- w1 o$ G1 L+ i0 M% E if(ma_mi==1) printf("max z= ");
6 d& W3 ^% _/ z) ~5 Z* k else printf("min z= ");
& U9 _8 \+ {! T' F; W- g printf("%lg x[%d]",c[1],1);
 I( I- j, q. y6 u; @1 ^ for(i=2;i<=num_x;i++) {
. R& X: l1 h9 e' s. d- H if(c>=0) printf(" +%lg x[%d]",c,i);
8 E% b% ~. s9 i0 v else printf(" %lg x[%d]",c,i);
: l0 P; x; Y) T3 F6 e% T" V }
: x, J2 { n6 @+ p- {; O/ W5 ? printf("\n正确吗？：(y/n)");2 [( s9 x/ q* e2 t+ T' E
getchar();
+ f2 g& r: P0 I- A9 V1 k confirm=getchar();8 a, N8 b8 b1 D5 t- O+ ]
if (confirm=='y') break;
- y M/ X- Y# o6 O2 { else if(confirm=='n') continue;1 ^# p- |4 L3 \0 l% p, x9 v8 d( S
}4 [: g, q$ W6 D0 R! {
<> printf("输入约束方程组个数：");. j) ~/ B3 O1 E& V) i
scanf("%d",&num_st);
- j4 ~4 {1 Z" K; M/ k% |/ V& ~ for(i=1;i<=num_st;i++) {
 printf("st.%d:\n",i);+ J5 J$ n4 I. I7 Z8 j
 while(1) {: l0 ^+ U/ _* _9 Q+ Y. C M
printf("请选择：1、==，2、>=，3、<= ：(1/2/3)");" G& C7 B G6 Z/ R+ P5 }9 J
scanf("%d",&re_st);
- J6 ^' e- u8 H& v- Z& J0 X if(re_st!=1&&re_st!=2&&re_st!=3) printf("输入错误，请重新选择。");
' A' ` a$ ^4 k3 l( {" ~ else break;
) W2 [1 i0 ]* @9 [: g }8 h+ a; ` d- B& u$ f
 printf("输入技术系数：\n");
: A) B z) G7 `) l; S7 K! Q for(j=1;j<=num_x;j++) {
1 ~9 \+ ?* f7 ~ printf("a%d=",j);+ I' f4 s, y/ B$ e. F. u* S
scanf("%lf",&a[j]);
3 J" |* m- d2 ^$ a }
& _5 g! j ~# c4 w printf("输入资源拥有量：\nb%d=",i);6 c* K% P; y" @
 scanf("%lf",&b);# v) y) w4 p2 S5 \, j

) J6 s; E8 I( j6 v4 C0 U printf("st.%i:\n",i);
" q# V6 T1 z- @1 g+ H. T( i. G printf("%lg x[%d]",a[1],1);
/ Z0 [1 H# T' C) Q3 z for(j=2;j<=num_x;j++) {
 s6 `0 n. |2 w( `, x( z if(a[j]>=0) printf(" +%lg x[%d]",a[j],j);( J& l: Q( @2 Q8 ~2 _# T
else printf(" %lg x[%d]",a[j],j);
! t: f, n4 C' s, R }
0 G. [/ y# w5 x! a" |6 s: i: E switch(re_st) {2 @) D6 z- x* P2 M, L
case 1: printf(" == %lg",b); break;" S7 _( W" D7 e. K4 P! f; w* z2 u+ G
case 2: printf(" >= %lg",b); break;, |2 Z: ]$ `) a/ y M3 {
case 3: printf(" <= %lg",b); break;
+ m/ N7 x' W7 c. P2 P# \7 s' L. e) \ }; i( ^6 |1 @1 x
<> while(1) {+ q5 i! P7 I8 X. ?
printf("\n正确吗？(y/n)");& q! }# F+ L, z
getchar();
 l/ w! S$ y/ Z, \- F+ g0 J confirm=getchar();
0 i$ g. m: J/ n: o0 Q0 X9 ?, g if (confirm=='y') break;
" b/ ]# H, i5 f+ e* A& g4 \ H else if(confirm=='n') {i-=1; break;}
; `6 w. b) c% v }
7 J& H) v) @' O3 _8 N }2 T: @: V' R. g
<>//显示输入的方程组
- |+ p1 O+ a) P. G! S printf("\n原问题为：\n\n");
0 _& p. Y+ c; i if(ma_mi==1) printf("max z= ");
* c6 _1 s3 n4 J4 O else printf("min z= ");
) }9 ?: E7 V2 a+ M7 m" p printf("%lg x[%d]",c[1],1);2 ~/ _! d( f' X& A: K- N
for(i=2;i<=num_x;i++) {
3 c7 a. A: }; o! V/ T9 i if(c==1) printf(" + x[%d]",i);
& B. O: Z" ^" {( u& F else if(c==-1) printf(" - x[%d]",i);
( I' Z' r0 }# r3 V) [0 o& p# N6 Y: k else if(c>=0) printf(" +%lg x[%d]",c,i);
7 H- ]4 K# a9 Z/ G* B, ~ else printf(" %lg x[%d]",c,i);
) P' d/ s% x/ [' j' P! m }
; c l. i( g+ c<> printf("\nst:\n");
$ o9 | O) G) }' E! K# S8 Z: V for(i=1;i<=num_st;i++) {
4 ] d9 i& c& e0 }! z; x k=0;
 x7 V0 `! X4 G& U2 Y/ O9 i% t for(j=1;j<=num_x;j++) {/ j0 y8 u. f: ?" t3 v. O" s, l- A6 R
if(a[j]!=0) {1 U( ^7 K+ B; t' |
if(a[j]==1&&k!=0) printf(" + x[%d]",j);
2 b- s ^# d8 o! H0 }, \ else if(a[j]==1&&k==0) printf(" x[%d]",j);
' T0 n) h6 g; W. l3 H% S) \ else if(a[j]==-1) printf(" - x[%d]",j);. X$ ^8 o7 w; v% L! {; p
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);
( H @; J! \& a9 R# F/ n5 ]: D else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);
# L1 R1 M2 K7 l3 U% ~ else printf(" %lg x[%d]",a[j],j);9 _2 U' O$ z4 P. Z2 ?
k=1;
- y2 @7 }' m+ k0 v }
$ P' S# j( h# O6 A }
8 \2 \3 [2 h6 d8 a switch(re_st) {% I2 M& {7 u0 _4 `
case 1: * ~+ Q' W3 S, J" W7 }9 a
printf(" == %lg\n",b);
- m9 C; k" Y% I) K break;' `9 U( x2 V/ ]* C( u2 ^1 P: J7 Q
case 2:
, _8 R# l0 J/ K* k' R* A1 ` printf(" >= %lg\n",b);
9 _. [2 |# B% D6 i break;: l: N9 y6 [( ` P% b
case 3:
# c" s s0 D0 V4 d printf(" <= %lg\n",b); * C' K+ H8 J+ X# W8 }! I6 v" L9 ^
break;; J3 `1 B9 A- ]/ U1 F# h
 }
$ f+ h& @; B j7 Y0 U }" f( q) o& i6 R# p. d
printf(" x[1]~x[%d]>=0\n",num_x);0 A; ~3 n' U- r
<> tnum_x=num_x;8 P7 J Y/ [3 ?! V1 ]
for(i=1;i<=num_st;i++) {
5 x4 {9 Q- z% I, I switch(re_st) {
# L& G8 j X" [9 V, ^ case 1:
. @+ z5 a8 F& i( l8 K9 q9 C case 3: F7 w v' f, a& |9 g# Z) B9 R
num_x+=1;
, O$ _9 }( \, O* {# S: O, w break;7 g S! O9 W0 Y7 u
 case 2:4 [1 H, C( S/ r
num_x+=2;5 U% X3 } U, m
break;( P" o0 K" G( o8 @
 }/ j" w0 E, E$ n* a: k+ O/ [& z! L+ [
}
& g8 n5 \% ]$ o5 ?1 a+ `. ^<>//化为标准形式: A1 K' `( `0 P! q- f+ T
if(ma_mi==2) for(i=1;i<=tnum_x;i++) c*=-1; //求最小值时，系数变相反数6 O! a4 l" Y1 R2 z9 E
for(i=1;i<=num_st;i++) {2 H1 X: L" v. C9 Q+ }% u! U1 i6 o' v7 n
 switch(re_st) {, G& H$ O- K: z2 R0 H% K3 q
case 1:+ U& k( h; E! A5 l. P- g: B
num_addv++;
! Y) G, E8 _: C5 U" P1 t num_ba++;% N/ `- k/ s" T
num_ar++;: _8 ^4 E8 f* p8 W" }, X
c[tnum_x+num_addv]=0; # S7 D5 u1 ^& y
base[num_ba]=arti[num_ar]=tnum_x+num_addv;% R: q( C% O6 [, W q
for(j=tnum_x+1;j<=num_x;j++)
7 w/ ^: g5 D* {! u% D; ]$ y if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
* Z# p& p& g% ^' r- y else a[j]=0;
) g1 C' H/ H9 r4 h7 J break;7 y* Y5 I3 u* I
case 2: B: i! ]- j* v' [4 q
num_addv++;
2 x7 v3 F& F' Z0 O' d# k: Z c[tnum_x+num_addv]=0;
4 r% w, v% l4 N( N- _- m! C2 \ num_addv++;
num_ba++;" `7 K0 f+ J( X& n. ~
num_ar++;3 f* s' [6 o* h. N T+ g) Q
c[tnum_x+num_addv]=0;
6 R) ?. t+ h, S" T& i base[num_ba]=arti[num_ar]=tnum_x+num_addv;
2 m0 J* x4 Y; g) T for(j=tnum_x+1;j<=num_x;j++)
 X, L7 A9 x' H" d4 n3 J0 \ if(j==tnum_x+num_addv-1) a[tnum_x+num_addv-1]=-1;
# r$ a/ R$ {, @$ q! l z- W" y else if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
7 H7 Y$ X. M9 | else a[j]=0;0 f. V1 w* C O" ~0 b
break;/ j6 `; I9 J8 f9 L: ?
case 3:
- J6 D( Z/ ~" ^/ v5 q o- W num_addv++;
; Z M* l D9 j6 l' B num_ba++;& P' i- z! s: c" W; ?: {2 _* a5 T& o
c[tnum_x+num_addv]=0;0 F7 \% G3 F% U2 i
base[num_ba]=tnum_x+num_addv;
- w4 V/ F- s! M5 [+ V: D, Q( R for(j=tnum_x+1;j<=num_x;j++) 3 ]5 A/ d; u$ M- ^/ J, X/ E6 c
 if(j==tnum_x+num_addv) a[tnum_x+num_addv]=1;
% X$ [$ {: K9 ]3 W2 _& W; n( b else a[j]=0;
: b% {- b8 e( T; T, l8 l& v/ w break;5 F& S6 i* k ^. U/ p& \9 Z
 }//switch
2 v3 w j" g4 k, E }//增加松弛变量、剩余变量、人工变量、确定基变量6 A/ H0 Z' Z. {9 D* J& O% }6 l# }
<>//显示标准化后的方程组
0 ?. ^/ j0 [% R8 t' [/ _) L3 \ printf("\n化为标准形式后：\n\n");
$ |' ?1 c) w$ r% s' v, ?- a( S) U if(ma_mi==1) printf("max z= ");
% D9 V# @( ?& ]. U else printf("max z'= ");
' v5 I& f3 c2 [, e" F' I printf("%lg x[%d]",c[1],1);/ J6 U1 L$ M$ i5 {! D8 a
for(i=2;i<=num_x;i++) { ) q( w- t, A5 m+ G4 O* |
 k=0;4 ~9 }# u6 @/ w9 X" ~+ B
 for(j=1;j<=num_ar;j++)
" }$ R/ h; R+ e3 b; ` if(i==arti[j]) k=1;
3 a# N/ V1 `( a1 x, p if(k==1) printf(" -M x[%d]",i);
. W9 `( X# W6 F2 [0 Y else if(c==1) printf(" + x[%d]",i);; L! b7 ?" A; B% k
 else if(c==-1) printf(" - x[%d]",i);) k- Q! [' R+ f8 T& W7 W
 else if(c>=0) printf(" +%lg x[%d]",c,i);( v8 j# Q; [" ~ B
 else printf(" %lg x[%d]",c,i);7 c, v" z7 G) i
}
/ u: G) H+ W$ R5 Y: r: ]/ m<> printf("\nst:\n"); H2 |. s6 D! ~/ j6 R4 M! y' A f
for(i=1;i<=num_st;i++) { [7 s( t* E5 R7 v4 c! u
 k=0;2 |* i: Q+ Q( t4 ]& Z3 p( l( R
 for(j=1;j<=num_x;j++) {2 R0 A1 _+ J' C6 p1 a& x5 h7 ~
if(a[j]!=0) {
) K1 ?$ |+ c+ u: U0 G if(a[j]==1&&k!=0) printf(" + x[%d]",j);! @) g, K+ X, d6 ]
else if(a[j]==1&&k==0) printf(" x[%d]",j);
8 I# O' U1 {7 U+ l2 k else if(a[j]==-1) printf(" - x[%d]",j);0 y! A5 y# {5 o ?' u0 o+ H5 y, [) o
else if(a[j]>=0&&k!=0) printf(" +%lg x[%d]",a[j],j);$ Q( M/ r7 z- G6 X+ F+ a9 k* g
else if(a[j]>=0&&k==0) printf(" %lg x[%d]",a[j],j);. U( p' p8 J$ t( _) F7 e. {
else printf(" %lg x[%d]",a[j],j);( x% g1 i+ s* g* X/ v
k=1;
" m9 Q' q5 ~4 K, @& \3 ] }% }0 j" l0 F/ L8 S
 }+ j% z' w8 Y: B$ F0 H. ~
 printf(" == %lg\n",b); 9 Y9 b: e; z1 s4 S. v
}: m! c3 w/ F; K+ q6 L4 ~
printf(" x[1]~x[%d]>=0",num_x);
+ Q3 L1 m+ `* \4 C% U' j. ?}: @9 z' i7 J- V& o5 F; `
<>void iterative() {% Z* S3 J- h) {
int i,j,k,k_a,k_f,l; //k_a,k_f值为0或1，记录当前下标在arti[]或base[]里的搜索结果& E3 u0 j, t; r/ b% W2 E% y
int base_elem;
8 V/ [" E6 N7 G' W6 C. N int base_out,base_in;8 R5 r2 f9 ~; L; n! H! o- b
double sigma[MAX],temp;% M( i. p6 F1 ^/ x8 A! D
double value_be; //高斯消元里保存主元素值
; Y/ M5 d/ n0 a$ E$ e8 Q<> printf("\n\n第%d次迭代：\n\n",stop);
- [- e8 f6 n. P: g% a0 n- D for(i=1;i<=num_st;i++) {
$ N- f1 z8 a- v' l. ? printf("c%d=%lg\t",base,c[base]);
9 M- `' d0 @1 ] printf("b%d=%lg\t",i,b);
' k% t( v- \- m" x0 L<> switch(step) {
: l3 h/ v5 Z7 c! @1 A* q. E case 1:
3 L4 e+ F) A' C; }# |: { for(j=1;j<=num_x;j++). [& _; V& A# V5 B8 N) X
{" }% G+ e# R4 |3 s5 N
 printf("a[%d][%d]=%lg\t",i,j,a[j]);1 _9 O4 Z8 I( X+ M; ?0 o; s) {
}, l2 j/ h# g F& W2 @
printf("\n");& R$ H) Z& u& W6 K, B1 e
break;7 ^5 j/ I, c @* O! T
case 2:3 ^6 C: B, o# W( o z6 o6 p
for(j=1;j<=num_x;j++) {' A @, K8 u! t- j X$ S8 ~
 k_a=0;
5 L$ v7 d3 x0 q/ {- }/ X; v for(l=1;l<=num_ar;l++) if(j==arti[l])k_a=1;- N3 W0 u9 G" y# I+ a
 if(k_a!=1) printf("a[%d][%d]=%lg\t",i,j,a[j]);) B* v# h e1 r+ S. W, N( T9 ^
}
0 t3 j+ G# ^5 K1 ^. j printf("\n");
/ u; ~7 h: S- @ break;
/ g! I* J2 k- h3 R1 P: k }. R, Q% _1 {+ V- U$ e
}
# {; O* d2 X4 n8 ?//求检验数sigma+ l/ ?! G' N" F, p8 o
for(i=1;i<=num_x;i++) {" a7 _: p: k5 G; e
 sigma=c;
% U9 j! a' d0 `! _& l4 M for(j=1;j<=num_st;j++) sigma-=c[base[j]]*a[j];
$ B9 P* j% ?7 ]) h* x4 e; r for(j=1;j<=num_st;j++) if(i==base[j]) sigma=0;
- }6 n, e* t; T0 I5 @ C switch(step) {
& m0 V6 ~2 D/ F; P case 1:
8 V+ y Z# E& `) t0 n9 b+ t printf("sigma[%d]=%lg\t",i,sigma);
+ s6 m. U; u6 N/ l break;
6 X- U$ v1 F; c R case 2:
. o; r, l6 H/ S, q; f k_a=0;" Z: V! ?7 A/ p5 t& w/ A, y
for(l=1;l<=num_ar;l++) if(i==arti[l]) k_a=1;- H, M9 V9 W" j
if(k_a!=1) printf("sigma[%d]=%lg\t",i,sigma);
# x* s. m& j, Y: p( Q6 L5 T break;
1 O- q" Q1 X( m' x7 W }. y* p1 u) w0 E! r/ e; Z t& D
}
( Y5 Q0 I; l4 E! b% A) ~2 E putchar('\n');% y1 I) J0 z8 ^4 a1 J3 G7 _
//检验检验数sigma是否全小于等于0
+ ]5 n. J6 b" |9 g3 R" ? k=0;
* Y' \* a4 I# C' C+ X0 B: I- l for(i=1;i<=num_x;i++) {
8 v8 q& {5 R& N if(sigma>0)
# X; ]: r, n4 ] k=1;; p5 x( O4 I' s- F3 h( E! h9 ?" m
}
$ Z- ~; P9 \6 ?1 D" n if(k==0) {
; x( W. T0 F3 ]0 c" ]4 ]0 ~ //sigma是全小于等于0时，检查是否为无穷多最优解* Y* m0 N3 i. B. q L) ~9 H
 for(i=1;i<=num_x;i++) { / [9 T6 y( G) |3 J8 g$ t) g/ }
k_f=k_a=0;9 g. M9 }3 P" q; x5 T$ U/ e% V9 c
for(j=1;j<=num_ar;j++)) I3 g" j& b( H
if(i==arti[j]) k_a=1;' t$ n2 n( G# P. w
if(sigma==0&&k_a!=1) {( p% [) y* w T6 F4 d# u: @
for(j=1;j<=num_st;j++) if(i==base[j]) k_f=1;+ l+ W( W5 E, z% p- I( ]; {
if(k_f==0) {status=-1; return;}
) r% t4 R5 F& T' _ }/ E: a- g* r9 \5 p0 q# S8 A+ J7 i
 }
, T2 `; ^4 O8 w; G8 T* Q status=1;
' {8 O/ M% t [, d2 W2 w return;
; H8 {. w+ s! S) k d! t3 o }
8 |4 A }1 N5 F) {1 G. c, ]) c8 t//检查是否为无界解
; j. C" Z4 T& K0 }8 C& Y" z for(i=1;i<=num_x;i++) { : y% i1 X# ^* B0 t! D z
 k_f=0;) X5 B8 ]5 s' J7 W
 if(sigma>0) {
+ ^4 r7 g& B- r; N! T for(j=1;j<=num_st;j++) if(a[j]>0) k_f=1;
6 D& X/ S1 V# V. [. k1 s j if(k_f!=1) {status=0; return;}
, _) O+ F; f6 U6 u+ S }
- f5 z; G7 r7 B9 f; G7 a }7 e4 I: t7 n" \" m( `
<>//确定换入变量! k$ F% v, }. Z: Q0 z I2 y
for(i=1;i<=num_x;i++) { ; O, ?% C0 b1 ]! H7 ?. G
 k=0;
: Y$ y3 ^ J) E" c* ]1 I9 B* L# { for(j=1;j<=num_st;j++) if(i==base[j]) k=1; }" Q# v( o; @* r. ~! [+ J
 if(k==0&&sigma>0) temp=sigma-1;
/ C5 l4 G' \5 V! x }//temp赋初值
 v7 B Y' _8 M( I% ^ for(i=1;i<=num_x;i++) {
# G3 H" y0 d7 V4 v1 e! f: X9 F k=0;" ?- z0 U0 k" F0 Z
 for(j=1;j<=num_st;j++) if(i==base[j]) k=1;$ t! P2 Y1 O" _* E! A$ O
 if(k==0)
3 J2 s) [3 M- V9 Z% V) @ if(sigma>temp&&sigma>0) {
' ^1 u1 l( W* r; Q, O& e4 _4 A& t: d base_in=i;
) E4 k! B2 y; f- R+ Z5 w5 N7 u temp=sigma;
; ]* o3 R0 ~4 F& U, _8 f }
0 J1 B! _4 h+ i- ~ }
- a% l8 P. c6 I<>//确定换出变量
3 }; d1 E1 ^5 I, q for(i=1;i<=num_st;i++) " d# \( Z4 M3 |/ ?6 [
 if(a[base_in]>0) {
0 i; I3 m+ Z) k temp=b/a[base_in]+1;
! `! c, E) B; ]$ u break;) I+ d5 K, |/ E+ g- X* M
 }//temp赋初值
+ m2 {. _) r' ?" }3 K for(i=1;i<=num_st;i++) {
) g: J% X) e5 B' P1 B9 A if(b/a[base_in]<=temp&&a[base_in]>0) {
. z2 v7 n* T* s( [7 U for(j=1;j<=num_ar;j++)1 O9 q0 r, i' T4 x
if(base==arti[j]) { 2 o E0 G# x4 D" N4 P' K( v. C
 base_out=base;
: C2 a3 D. b6 m8 {0 X% R6 K base_elem=i;) v! `3 b5 M# s N9 n
 temp=b/a[base_in];- V3 A% I, V; T; x& x5 F
 break;
9 \ O( U+ h Z/ G; o! _ }$ a8 c/ @( b" B' N6 O
 }//人工变量优先换出
$ F% y0 D' f# _ if(b/a[base_in]<temp&&a[base_in]>0) {8 Y- \, l& s% d
base_out=base;& w$ R# U3 O1 z7 @& b9 r( i
base_elem=i;
2 z1 g( f: P4 f2 q; A temp=b/a[base_in];7 w9 Q u. B0 U F
 }' Q2 K+ J" V4 V' H; k8 L
}
9 M! e$ b! l* I! g0 R<> printf(" 基变量：");2 Q+ V3 ]. n, `$ P
for(i=1;i<=num_st;i++) printf("x[%d] ",base);5 x3 W* B+ k9 ]8 J) V) _+ _
printf("换入变量：x[%d] 换出变量：x[%d]",base_in,base_out);. l; a% x2 a8 ~/ N6 Y6 l
//基变量变换，进行新方程初始化后迭代$ r% l( G' u+ A+ t- u2 D
for(i=1;i<=num_st;i++) {* Z3 K8 N- r% j/ O
 if(base==base_out) base=base_in;2 k( g4 M% E- w4 Y: {) x5 J
}
% ^) S* B5 ]. m# [/ x9 Z5 M6 i" G//初始化主元素行系数
 z: h& i$ }/ j8 p1 J! w value_be=a[base_elem][base_in];5 i+ ]' ]' x; U |/ Z x
b[base_elem]/=value_be;' z1 N6 I' E/ U' k" q' R
for(i=1;i<=num_x;i++) a[base_elem]/=value_be;$ f8 G0 o- L4 L) ]* J' K- }
<> for(i=1;i<=num_st;i++) {
2 }* w2 j& ?6 X$ J; P: D if(i!=base_elem) {
% I5 R- v9 \7 n& b/ ` b-=b[base_elem]*a[base_in];1 N ~* z* t; u# W: h
value_be=a[base_in];
. S. g6 d( @* g. v for(j=1;j<=num_x;j++) a[j]-=a[base_elem][j]*value_be;* F) G2 X+ [- C, I7 q/ z
 }# x' C, K3 o1 M1 J
}7 b% @) o g& Y1 }0 S' X* W
stop++;+ G( {( G' r& U4 c" w
if(stop>STP) {status=-2; return;}
4 N: Z$ u: Y+ I5 r% L* I" E iterative();0 ]* w# u. Y7 _2 ^
}4 X2 G! C, ~9 t: U
<>void output() {
% ], N1 ?4 F( s# F, m' J int i,j;
; w$ P0 r6 E! S. Y4 N' r double X[MAX];/ n& m% g8 J4 s9 ?; F( f# y/ F
printf("\n结果如下：\n");
0 o6 a9 y3 u. `0 E# x5 K/ U; ^ printf("\nX=(");
" g0 o; A/ x: d2 l# j y) F8 W for(i=1;i<=num_x;i++) {- x0 n) | h& A% h5 s0 e. |3 w
 for(j=1;j<=num_st;j++)
$ L( \; U7 |+ @+ X, L7 i if(i==base[j]) {X=b[j];break;}
/ U5 i. S6 t. a% g9 L4 {7 @) j else X=0;
: R0 P: x0 P- z" j$ u- ]9 b printf("%lg ",X);
+ [" j, B M, v4 Z9 j }
* o, `0 K, I) {/ L* l6 n1 l0 m# `; C printf(")");/ i% q2 V5 J6 Q# J0 h: k% [' \$ C
for(i=1;i<=num_x;i++) max+=c*X;1 i2 C6 t4 z3 L% j9 N; u! D
if(ma_mi==1) printf("\nMax z= %lf\n",max);
. _9 t: E" `6 c9 i else printf("\nMin z= %lf\n",-max);
2 d$ R% q2 z4 D% @1 o}
作者: 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