使用C语言实现单纯形法求解线性规划问题

1、上 机 实 验 报 告班级：自动化班专业/方向：自动化姓名：实 验 成 绩(10分制)学号：上机实验名称：使用C语言实现单纯形法求解线性规划问题上机时间：2015年5月20日上机地点：信自234一、实验目的和要求1、目的：l 掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。l 了解算法程序实现的过程和方法。2、要求：l 使用熟悉的编程语言编制单纯形算法的程序。l 独立编程，完成实验，撰写实验报告并总结。二、实验内容和结果1、单纯形算法的步骤及程序流程图。（1）、算法步骤（1）将线性规划化为标准形。（2）用最快的方法确定一个初始基本可行解X（0）。当st均为“”形式时，以松驰变量做

2、初始基本变量最快。（3）求X（0）中非基本变量xj的检验数j。若，则停止运算，X（0）=X*（表示最优解），否则转下一步。（4）由确定xk进基；由确定xl出基，其中alk称为主元素；利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。（5）返回（3），直至求得最优解为止。（2）、程序图找出初始基可行解列出初始单纯形表计算校验数所有j0，是否存在Pj=0确定为入基变量确定出基变量计算新的单纯形表已得最优解，结束无最优解，结束2、单纯形算法程序的规格说明各段代码功能描述：（1）、定义程序中使用的变量#include#include#define m 3 /*定义约束条件

3、方程组的个数*/#define n 5 /*定义未知量的个数*/float M=.0;float Amn; /*用于记录方程组的数目和系数;*/float Cn; /*用于存储目标函数中各个变量的系数*/float bm; /*用于存储常约束条件中的常数*/float CBm; /*用于存储基变量的系数*/float setam; /*存放出基与入基的变化情况*/float deltan; /*存储检验数矩阵*/float xn; /*存储决策变量*/int numm; /*用于存放出基与进基变量的情况*/float ZB=0; /*记录目标函数值*/（2）、定义程序中使用的函数void in

4、put();void print();int danchunxing1();int danchunxing2(int a);void danchunxing3(int a,int b);(3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。int danchunxing1()int i,k=0;int flag=0;float max=0;for(i=0;in;i+)if(deltai=0)flag=1;else flag=0;break;if(flag=1)return -1;for(i=0;in;i+) if(max deltai) max =deltai;k=i;retur

5、n k;(4)、确定出基变量，如果某个大于0的校验数，对应的列向量中所有元素小于等于0，则线性规划问题无解。int danchunxing2(int a)int i,k,j;int flag=0;float min;k=a;for(i=0;im;i+)if(Aik=0)flag=1;else flag=0;break;if(flag=1)printf(n该线性规划无最优解!n); return -1;for(i=0;i0) setai=bi/Aik; else setai=M;min=M;for(i=0;i=setai) min=setai;j=i;numj=k+1;CBj=Ck;return

6、 j;(5)、迭代运算，计算新的单纯形表。void danchunxing3(int p,int q)int i,j,c,l;float temp1,temp2,temp3;c=p;/*行号*/l=q;/*列号*/temp1=Acl;bc=bc/temp1;for(j=0;jn;j+)Acj=Acj/temp1; for(i=0;im;i+) if(i!=c) if(Ail!=0) temp2=Ail; bi=bi-bc*temp2; for(j=0;jn;j+) Aij=Aij-Acj*temp2; temp3=deltal;for(i=0;in;i+)deltai=deltai-Aci*t

7、emp3;(6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。void print()int i,j=0;printf(n-n);for(i=0;im;i+) printf(%8.2ftX(%d) %8.2f ,CBi,numi,bi); for(j=0;jn;j+) printf(%8.2f ,Aij); printf(n);printf(n-n);printf(ttt);for(i=0;in;i+)printf( %8.2f,deltai);printf(n-n);void input()int i,j; /*循环变量*/

8、int k;printf(请输入方程组的系数矩阵A(%d行%d列):n,m,n);for(i=0;im;i+)for(j=0;jn;j+)scanf(%f,&Aij);printf(n请输入初始基变量的数字代码num矩阵:n);for(i=0;im;i+)scanf(%d,&numi);printf(n请输入方程组右边的值矩阵b:n);for(i=0;im;i+)scanf(%f,&bi);printf(n请输入目标函数各个变量的系数所构成的系数阵C:n);for(i=0;in;i+)scanf(%f,&Ci);for(i=0;in;i+)deltai=Ci;for(i=0;im;i+) k=

9、numi-1; CBi=Ck;(7)、主函数，调用前面定义的函数。main()int i,j=0;int p,q,temp;input();printf(n-n);printf( tCBtXBtbt);for(i=0;in;i+)printf( X(%d)t,i+1);for(i=0;in;i+)xi=0;printf(n);while(1) q=danchunxing1(); if(q=-1) print(); printf(n所得解已经是最优解!n); printf(n最优解为:n); for(j=0;jm;j+) temp=numj-1; xtemp=bj; for(i=0;in;i+)

10、 printf(x%d=%.2f ,i+1,xi); ZB=ZB+xi*Ci; printf(ZB=%.2f,ZB); break; print(); p=danchunxing2(q); printf(np=%d,q=%d,p,q); if(q=-1) break; danchunxing3(p,q);输入:（1）、输入方程组的系数矩阵A(3行5列)（2）、输入初始基变量的数字代码num矩阵（3）、输入方程组右边的值矩阵b（4）、输入目标函数各个变量的系数所构成的系数阵C输出：（1）、输出是否为最优解（2）、输出最优解为多少3、使用所编程序求解如下LP问题并给出结果。请输入方程组的系数矩阵A

11、(3行5列):2 2 1 0 04 0 0 1 00 5 0 0 1请输入初始基变量的数字代码num矩阵:3 4 5请输入方程组右边的值矩阵b:12 16 15请输入目标函数各个变量的系数所构成的系数阵C:2 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)- 0.00 X(3) 12.00 2.00 2.00 1.00 0.00 0.00 0.00 X(4) 16.00 4.00 0.00 0.00 1.00 0.00 0.00 X(5) 15.00 0.00 5.00 0.00 0.00 1.00- 2.00 3.00 0.00 0.00 0.00-p=2

12、,q=1- 0.00 X(3) 6.00 2.00 0.00 1.00 0.00 -0.40 0.00 X(4) 16.00 4.00 0.00 0.00 1.00 0.00 3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20 2.00 0.00 0.00 0.00 -0.60-p=0,q=0- 2.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20- 0.00 0.00 -1.0

13、0 0.00 -0.20-P26 例5 程序运行结果- 0.00 0.00 -1.00 0.00 -0.20-所得解已经是最优解!最优解为:x1=3.00 x2=3.00 x3=0.00 x4=4.00 x5=0.00 ZB=15.00输出：请输入方程组的系数矩阵A(3行5列):1 0 0.5 0 -0.20 0 -2 1 0.80 1 0 0 0.2请输入初始基变量的数字代码num矩阵:3 4 5请输入方程组右边的值矩阵b:3 4 3请输入目标函数各个变量的系数所构成的系数阵C:3 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)0.00 X(3) 3.00

14、 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 0.00 X(5) 3.00 0.00 1.00 0.00 0.00 0.20- 3.00 3.00 0.00 0.00 0.00-p=0,q=0- 3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 - 0.00 3.00 -1.50 0.00 0.60-p=2,q=1- 3.00 X(1) 3.00 1.00 0.00 0.50 0.00 -0.

15、20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20 P33 例7程序运行结果所得解已经是最优解!最优解为:x1=4.00 x2=2.00 x3=0.00 x4=0.00 x5=5.00 ZB=18.00输出：3.00 X(2) 3.00 0.00 1.00 0.00 0.00 0.20- 0.00 0.00 -1.50 0.00 0.00-p=1,q=4- 3.00 X(1) 4.00 1.00 0.00 -0.00 0.25 0.00 0.00 X(5) 5.00 0.00 0

16、.00 -2.50 1.25 1.00 3.00 X(2) 2.00 0.00 1.00 0.50 -0.25 0.00- 0.00 0.00 -1.50 -0.00 0.00-请输入方程组的系数矩阵A(3行5列):4 0 1 0 00 0 0 0 00 0 0 0 0请输入初始基变量的数字代码num矩阵:3 4 5请输入方程组右边的值矩阵b:16 0 0请输入目标函数各个变量的系数所构成的系数阵C:2 3 0 0 0- CB XB b X(1) X(2) X(3) X(4) X(5)P34例8程序运行结果所得解已经是最优解!最优解为:x1=0.00 x2=0.00 x3=16.00 x4=0

17、.00 x5=0.00 ZB=-1.# 0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00 0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00- 2.00 3.00 0.00 0.00 0.00-该线性规划无最优解!p=-1,q=1- 0.00 X(3) 16.00 4.00 0.00 1.00 0.00 0.00 0.00 X(4) 0.00 0.00 0.00 0.00 0.00 0.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.

18、00 0.00- -1.#J -1.#J -1.#J -1.#J -1.#J-输出：请输入方程组的系数矩阵A(3行5列):2 2 1 0 01 2 0 -1 10 0 0 0 0请输入初始基变量的数字代码num矩阵:3 4 5请输入方程组右边的值矩阵b:12 14 0请输入目标函数各个变量的系数所构成的系数阵C:P35 例9 程序运行结果所得解已经是最优解!最优解为:x1=0.00 x2=6.00 x3=0.00 x4=2.00 x5=0.00 ZB=18.002 3 0 0 -M- CB XB b X(1) X(2) X(3) X(4) X(5)- 0.00 X(3) 12.00 2.00 2.00 1.00 0.00 0.00 0.00 X(4) 14.00 1.00 2.00 0.00 -1.00 1.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.0