对偶单纯形法C语言实现.doc

1、程序源代码：#include#include#define MAX_N 100#define M 1000000.0;int m, n;double AMAX_NMAX_N, CMAX_N, bMAX_N, setaMAX_N, CZMAX_N; int numMAX_N; int GetOutCow() /求换出基int i,k;int flag;double min = 0;for (i = 0; i = 0)flag = 1;else flag = 0;break;if (flag = 1)return -1;for (i = 0; i bi)min = bi;k = i;return

2、k;int GetInCow(int p) /求换入基int i, j;int flag = 0;double min;for (j = 0; j = 0)flag = 1;else flag = 0;break;if (flag = 1)printf(“n 原线性规划问题无可行解!n“);return -1;for (j = 0; j = setaj)min = setaj;i = j;nump = i + 1;return i;void change(int p, int q) /计算新的单纯形表int i, j;double temp1, temp2, temp3;temp1 = Apq

3、;for (i = 0; i m; i +)if (i != p)if (Aiq != 0)temp2 = Aiq / temp1;for (j = 0; j n; j +)Aij = Aij - Apj * temp2;bi = bi - bp * temp2;temp3 = CZq / temp1;for (i = 0; i n; i +)CZi = CZi - Api * temp3;for (j = 0; j n; j +)Apj = Apj / temp1;bp = bp / temp1;void print1()int i;printf(“n-n“);printf(“t“);for

4、(i = 1; i = n; i +)printf(“X(%d)t“, i);printf(“RHSn“);printf(“-n“);printf(“t“);for (i = 0; i n; i +)printf(“%.3lft“, -Ci); printf(“n-n“);void print2()int i, j;printf(“n-n“);for (i = 0; i m; i +)printf(“x(%d)t“, numi);for(j = 0; j n; j +)printf(“%.3lft“, Aij);printf(“%.3lfn“, bi);printf(“-n“);printf(

5、“cj-zjt“);for (i = 0; i n; i +)printf(“%.3lft“, CZi);printf(“n-n“);void Input()int i, j;printf(“请输入约束条件的个数：n“);scanf(“%d“, printf(“请输入变量的个数：n“);scanf(“%d“, printf(“请输入方程组的系数矩阵 A(%d 行%d 列):n“, m, n);for (i = 0; i m; i +)for (j = 0; j n; j +)scanf(“%lf“, printf(“n 请输入初始基变量的数字代码 num 矩阵:n“);for (i =0; i

6、 m; i +)scanf(“%d“, printf(“n 请输入方程组右边的值矩阵 b:n“);for (i = 0; i m; i +)scanf(“%lf“, printf(“n 请输入目标函数各个变量的系数所构成的系数阵 C:n“);for (i = 0; i n; i +)scanf(“%lf“, void main()int i, j;int p, q;double z = 0;Input();for (i = 0; i m; i +)bi = -bi;for (j = 0; j n; j +)Aij = -Aij;for (i = 0; i n; i +)CZi = -Ci;pr

7、int1();print2();while(1)p = GetOutCow(b);if(p = -1)printf(“n 所得解已经是最优解!n“);for (i = 0; i m; i +)z += bi * Cnumi - 1;for(i = 0; i m; i +)printf(“x(%d) = %.3lft“, i + 1, bi);printf(“z = %.3lfn“, z);break;q = GetInCow(p);if (q = -1)break;change(p, q);print2();运行实例 3,2104.minixxtsz先将其化为标准型3,21054.minixx

8、tsz运行结果：请输入约束条件的个数：2请输入变量的个数：5请输入方程组的系数矩阵 A(2 行 5 列):3 1 1 -1 0-1 4 1 0 -1请输入初始基变量的数字代码 num 矩阵:4 5请输入方程组右边的值矩阵 b:1 2请输入目标函数各个变量的系数所构成的系数阵 C:1 1 1 0 0-X(1) X(2) X(3) X(4) X(5) RHS-1.000 -1.000 -1.000 0.000 0.000-x(4) -3.000 -1.000 -1.000 1.000 0.000 -1.000x(5) 1.000 -4.000 -1.000 0.000 1.000 -2.000-c

9、j-zj -1.000 -1.000 -1.000 0.000 0.000-x(4) -3.250 0.000 -0.750 1.000 -0.250 -0.500x(2) -0.250 1.000 0.250 0.000 -0.250 0.500-cj-zj -1.250 0.000 -0.750 0.000 -0.250-x(1) 1.000 0.000 0.231 -0.308 0.077 0.154x(2) 0.000 1.000 0.308 -0.077 -0.231 0.538-cj-zj 0.000 0.000 -0.462 -0.385 -0.154-所得解已经是最优解!x(1) = 0.154 x(2) = 0.538 z = 0.692