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

资源描述

上机实验报告班级：自动化班专业/方向：自动化姓名：实验成绩 (10分制) 学号：上机实验名称：使用C语言实现单纯形法求解线性规划问题上机时间：2015年5月20日上机地点：信自234 一、实验目的和要求 1、目的： l 掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。 l 了解算法à程序实现的过程和方法。 2、要求： l 使用熟悉的编程语言编制单纯形算法的程序。 l 独立编程，完成实验，撰写实验报告并总结。二、实验内容和结果 1、单纯形算法的步骤及程序流程图。（1）、算法步骤（1）将线性规划化为标准形。（2）用最快的方法确定一个初始基本可行解X（0）。当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）、定义程序中使用的变量 #include<stdio.h> #include<math.h> #define m 3 /*定义约束条件方程组的个数*/ #define n 5 /*定义未知量的个数*/ float M=1000000.0; float A[m][n]; /*用于记录方程组的数目和系数;*/ float C[n]; /*用于存储目标函数中各个变量的系数*/ float b[m]; /*用于存储常约束条件中的常数*/ float CB[m]; /*用于存储基变量的系数*/ float seta[m]; /*存放出基和入基的变化情况*/ float delta[n]; /*存储检验数矩阵*/ float x[n]; /*存储决策变量*/ int num[m]; /*用于存放出基和进基变量的情况*/ 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(delta[i]<=0) flag=1; else {flag=0;break;} if(flag==1) return -1; for(i=0;i<n;i++){ if(max <delta[i]) { max =delta[i];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(A[i][k]<=0) flag=1; else {flag=0;break;} if(flag==1) {printf("\n该线性规划无最优解!\n"); return -1;} for(i=0;i<m;i++) { if(A[i][k]>0) seta[i]=b[i]/A[i][k]; else seta[i]=M; } min=M; for(i=0;i<m;i++) { if(min>=seta[i]) {min=seta[i];j=i;} } num[j]=k+1; CB[j]=C[k]; return j; } (5)、迭代运算，计算新的单纯形表。 void danchunxing3(int p,int q) { int i,j,c,l; float temp1,temp2,temp3; c=p;/*行号*/ l=q;/*列号*/ temp1=A[c][l]; b[c]=b[c]/temp1; for(j=0;j<n;j++) A[c][j]=A[c][j]/temp1; for(i=0;i<m;i++) { if(i!=c) if(A[i][l]!=0) { temp2=A[i][l]; b[i]=b[i]-b[c]*temp2; for(j=0;j<n;j++) A[i][j]=A[i][j]-A[c][j]*temp2; } } temp3=delta[l]; for(i=0;i<n;i++) delta[i]=delta[i]-A[c][i]*temp3; } (6)、输入函数，输入方程组的系数矩阵、初始基变量的数字代码、方程组右边的值矩阵、目标函数各个变量的系数所构成的系数阵。 void print() { int i,j=0; printf("\n--------------------------------------------------------------------------\n"); for(i=0;i<m;i++) { printf("%8.2f\tX(%d) %8.2f ",CB[i],num[i],b[i]); for(j=0;j<n;j++) printf("%8.2f ",A[i][j]); printf("\n"); } printf("\n--------------------------------------------------------------------------\n"); printf("\t\t\t"); for(i=0;i<n;i++) printf(" %8.2f",delta[i]); printf("\n--------------------------------------------------------------------------\n"); } void input() { int i,j; /*循环变量*/ int k; printf("请输入方程组的系数矩阵A(%d行%d列):\n",m,n); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%f",&A[i][j]); printf("\n请输入初始基变量的数字代码num矩阵:\n"); for(i=0;i<m;i++) scanf("%d",&num[i]); printf("\n请输入方程组右边的值矩阵b:\n"); for(i=0;i<m;i++) scanf("%f",&b[i]); printf("\n请输入目标函数各个变量的系数所构成的系数阵C:\n"); for(i=0;i<n;i++) scanf("%f",&C[i]); for(i=0;i<n;i++) delta[i]=C[i]; for(i=0;i<m;i++) { k=num[i]-1; CB[i]=C[k]; }} (7)、主函数，调用前面定义的函数。 main() { int i,j=0; int p,q,temp; input(); printf("\n--------------------------------------------------------------------------\n"); printf(" \tCB\tXB\tb\t"); for(i=0;i<n;i++) printf(" X(%d)\t",i+1); for(i=0;i<n;i++) x[i]=0; printf("\n"); while(1) { q=danchunxing1(); if(q==-1) { print(); printf("\n所得解已经是最优解!\n"); printf("\n最优解为:\n"); for(j=0;j<m;j++) { temp=num[j]-1; x[temp]=b[j]; } for(i=0;i<n;i++) { printf("x%d=%.2f ",i+1,x[i]); ZB=ZB+x[i]*C[i]; } 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(3行5列): 2 2 1 0 0 4 0 0 1 0 0 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,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.00 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.2 0 0 -2 1 0.8 0 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 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.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.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 0 0 0 0 0 0 0 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列): 2 2 1 0 0 1 2 0 -1 1 0 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.00 2 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.00 0.00 -------------------------------------------------------------------------- 2.00 3.00 0.00 0.00 0.00 -------------------------------------------------------------------------- p=0,q=1 -------------------------------------------------------------------------- 3.00 X(2) 6.00 1.00 1.00 0.50 0.00 0.00 0.00 X(4) 2.00 -1.00 0.00 -1.00 -1.00 1.00 0.00 X(5) 0.00 0.00 0.00 0.00 0.00 0.00 -------------------------------------------------------------------------- -1.00 0.00 -1.50 0.00 0.00 -------------------------------------------------------------------------- 输出：三、实验总结通过使用C语言实现单纯形法求解线性规划问题和用matlab优化工具箱求解LP问题，使得问题的求解更加简单和容易，而且也更加快速的求解问题，我们也对这两种方法有了更深刻的了解。 17 / 17

展开阅读全文