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

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

2、）。当s·t均为“”形式时，以松驰变量做初始基本变量最快。（3）求X（0）中非基本变量xj的检验数j。若，则停止运算，X（0）=X*（表示最优解），否则转下一步。（4）由确定xk进基；由确定xl出基，其中alk称为主元素；利用初等变换将alk化为1，并利用alk将同列中其它元素化为0，得新解X（1）。（5）返回（3），直至求得最优解为止。（2）、程序图找出初始基可行解列出初始单纯形表计算校验数所有j<=0?对于某个j>0，是否存在Pj<=0确定为入基变量确定出基变量计算新的单纯形表已得最优解，结束无最优解，结束2、单纯形算法程序的规格说明各段代码功能描述：（1）、定

3、义程序中使用的变量#include<stdio.h>#include<math.h>#define m 3 /*定义约束条件方程组的个数*/#define n 5 /*定义未知量的个数*/float M=.0;float Amn; /*用于记录方程组的数目和系数;*/float Cn; /*用于存储目标函数中各个变量的系数*/float bm; /*用于存储常约束条件中的常数*/float CBm; /*用于存储基变量的系数*/float setam; /*存放出基与入基的变化情况*/float deltan; /*存储检验数矩阵*/float xn; /*存储决策变量

4、*/int numm; /*用于存放出基与进基变量的情况*/float ZB=0; /*记录目标函数值*/（2）、定义程序中使用的函数void input();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;i<n;i+)if(deltai<=0)flag=1;else fl

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

6、; return -1;for(i=0;i<m;i+) if(Aik>0) setai=bi/Aik; else setai=M;min=M;for(i=0;i<m;i+) if(min>=setai) min=setai;j=i;numj=k+1;CBj=Ck;return 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;j<n;j+)Acj

7、=Acj/temp1; for(i=0;i<m;i+) if(i!=c) if(Ail!=0) temp2=Ail; bi=bi-bc*temp2; for(j=0;j<n;j+) Aij=Aij-Acj*temp2; temp3=deltal;for(i=0;i<n;i+)deltai=deltai-Aci*temp3;(6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。void print()int i,j=0;printf("n-n");for(i=0;i<m;i+) prin

8、tf("%8.2ftX(%d) %8.2f ",CBi,numi,bi); for(j=0;j<n;j+) printf("%8.2f ",Aij); printf("n");printf("n-n");printf("ttt");for(i=0;i<n;i+)printf(" %8.2f",deltai);printf("n-n");void input()int i,j; /*循环变量*/int k;printf("请输入方程组的

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

10、构成的系数阵C:n");for(i=0;i<n;i+)scanf("%f",&Ci);for(i=0;i<n;i+)deltai=Ci;for(i=0;i<m;i+) k=numi-1; CBi=Ck;(7)、主函数，调用前面定义的函数。main()int i,j=0;int p,q,temp;input();printf("n-n");printf(" tCBtXBtbt");for(i=0;i<n;i+)printf(" X(%d)t",i+1);for(i=0;i&l

11、t;n;i+)xi=0;printf("n");while(1) q=danchunxing1(); if(q=-1) print(); printf("n所得解已经是最优解!n"); printf("n最优解为:n"); for(j=0;j<m;j+) temp=numj-1; xtemp=bj; for(i=0;i<n;i+) printf("x%d=%.2f ",i+1,xi); ZB=ZB+xi*Ci; printf("ZB=%.2f",ZB); break; print()

12、; 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(3行5列):2 2 1 0 04 0 0 1 00 5 0 0 1请输入初始基变量的数字代码num矩阵:3 4 5请输入方

13、程组右边的值矩阵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,q=1- 0.00 X(3) 6.00 2.00 0.00 1.00 0.00 -0.40 0.00 X(4) 16.00

14、 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.00 0.00 -0.20-P26 例5 程序运行结果- 0.00 0.00 -1.00 0.00 -0.20-所得解已经是最

15、优解!最优解为: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 1.00 0.00 0.50 0.00 -0.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00

16、 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.20 0.00 X(4) 4.00 0.00 0.00 -2.00 1.00 0.80 3.00 X(2) 3.00 0.0

17、0 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.00 -2.50 1.25 1.00 3.00 X(2) 2.00 0.00 1.00 0.50 -0.25 0.00-

18、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.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.00 0.00- -1.#J -1.#J -1.#J -1.#J -1.#J-输出：请输入方程组的系数矩阵A(3行5列