非线性最优化理论与方法 实验报告

XIAN TECHNOLOGICAL UNIVERSITY课程设计报告课程名称 非线性最优化理论与方法 专 业： 数学与应用数学 班 级： 17100306 姓 名： 靳玉梅 学 号： 16100305120 指导教师： 张襄松 成 绩： 2018 年 11 月 28 日西安工业大学课程设计（论文）用纸第 页一、 实验目的（1）掌握计算步骤，并能熟练使用该方法求解线性规划问题。（2）了解算法算法程序实现的过程及方法二、 实验要求用c语言实现单纯形法、0.618法、最速下降法、Newton法、共轭梯度法中的FR方法、变度量法中的BFP算法，求解非线性规划问题，包括详细的接题步骤，运行程序，输出结果等。三、 实验环境Microsoft VisualC+6.0（绿色版）四、 实验内容及步骤、数据记录及处理（一）单纯形法（simplex method）Dantzing在1949年提出的单纯形法（simplex method）是一种行之有效的方法。基本自想是：从一个基本可行解出发，求出使目标函数值下降的另一个基本可行解。因此需要解决三个问题：（1） 求（LP）的初始基本可行解的方法；（2） 判别一个基本可行解是否为最优解的准则；（3） 从一个基本可行解转换到使目标数值下降的另一个基本可行解的方法。单纯形算法解线性规划的步骤及流程图：算法步骤（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），直至求得最优解为止。程序图找出初始基本可行解列出初始单纯形表计算校验数已得最优解结束所有i<=0?对于某个，j<0是否存在Pj<=0无最优解结束计算新的单纯形表确定为入基变量确定出基变量2、单纯形算法程序的规格说明各段代码功能描述：（1）、定义程序中使用的变量#include<stdio.h>#include<math.h>#define m 3 /*定义约束条件方程组的个数*/#define n 5 /*定义未知量的个数*/float M=1000000.0;float Amn; /*用于记录方程组的数目和系数;*/float Cn; /*用于存储目标函数中各个变量的系数*/float bm; /*用于存储常约束条件中的常数*/float CBm; /*用于存储基变量的系数*/float setam; /*存放出基与入基的变化情况*/float deltan; /*存储检验数矩阵*/float xn; /*存储决策变量*/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 flag=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"); 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=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+) printf("%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("请输入方程组的系数矩阵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请输入目标函数各个变量的系数所构成的系数阵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<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(); 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）、输出最优解为多少 例题：P96页例4.2.1求解线性规划问题解：问题有一个明显的可行基B=(P3,P4,P5)对应的初始基本可行解x=(0,0,5,0,21)T,编译得：所以：最优解x=(2.75, 2.25,